RFC: Add Int8# and Word8#
Needs ReviewPublic

Authored by michalt on Mar 6 2018, 2:28 PM.

Details

Summary

This is the first step of implementing:
https://github.com/ghc-proposals/ghc-proposals/pull/74

The main highlights/changes:

  • primops.txt.pp gets two new sections for two new primitive types for signed and unsigned 8-bit integers (Int8# and Word8 respectively) along with basic arithmetic and comparison operations. PrimRep/RuntimeRep get two new constructors for them. All of the primops translate into the existing MachOPs.
  • For CmmCalls the codegen will now zero-extend the values at call site (so that they can be moved to the right register) and then truncate them back their original width.
  • x86 native codegen needed some updates, since it wasn't able to deal with the new widths, but all the changes are quite localized. LLVM backend seems to just work.

Signed-off-by: Michal Terepeta <michal.terepeta@gmail.com>

Test Plan

./validate with new tests

michalt created this revision.Mar 6 2018, 2:28 PM

This is probably not ready to be merged, but I'd love to get some feedback:

  • PrimRep/RuntimeRep - should we have a new constructor per new primitive type? That's what I went for since it's consistent with what we already had (we already have Int64Rep/Word64Rep)
  • How should we name the new primitive ops? In particular {zero,sign}-extending, truncating, narrowing? I'm currently using things like word8ToWord#, but I noticed that this will be quite confusing, since we already have word2Int# (also notice the To vs 2). So I was thinking of using extendWord8/narrowWord8/extendInt8#/narrowInt8#. What do you think?
  • The current version doesn't support literals for the new types (i.e., one must do wordToWord8# 42## to get a Word8#). This makes it impossible to support deriving Read/Show for anything that contains the new primitive types. But I'm not sure what syntax we should use? Relying on type-inference would not be backwards compatible, since a lot of code might become ambiguous (unless we default to the native-word width?)
  • I have no way of testing non-x86 native backends - what's our policy/approach to adding new primops/primitive types in such case? Based on the experience with x86, I doubt they would just work... :/
  • Any other concerns? Anything fundamental that is missing?

Thanks!

dfeuer added a subscriber: dfeuer.Mar 9 2018, 4:13 PM
  • PrimRep/RuntimeRep - should we have a new constructor per new primitive type? That's what I went for since it's consistent with what we already had (we already have Int64Rep/Word64Rep)
  • How should we name the new primitive ops? In particular {zero,sign}-extending, truncating, narrowing? I'm currently using things like word8ToWord#, but I noticed that this will be quite confusing, since we already have word2Int# (also notice the To vs 2). So I was thinking of using extendWord8/narrowWord8/extendInt8#/narrowInt8#. What do you think?

I think there's a significant risk of getting too many primops. When you extend a Word8, what do you
extend it to? A Word? Will we need separate primops to convert between Word8 and Int8, etc.?
One option (kind of gross) would be to use the same RuntimeRep for Int8 as Word8, etc., and then
offer primops that work on any types with the relevant RuntimeRep. Or would that be too horrible?

  • The current version doesn't support literals for the new types (i.e., one must do wordToWord8# 42## to get a Word8#). This makes it impossible to support deriving Read/Show for anything that contains the new primitive types. But I'm not sure what syntax we should use? Relying on type-inference would not be backwards compatible, since a lot of code might become ambiguous (unless we default to the native-word width?)

One option is to steal a page from containers and make the Show and Read instances include the
conversion. That is, given

data Foo = Foo Int8#

show (Foo (intToInt8# 5#)) would be "Foo (intToInt8# 5#)". It's not pretty, but at least it would
work. How hard would it be to add literals though? I would think 24#8 should be the Int8# for
24, and 25##16 should be the Word16# for 25.

  • PrimRep/RuntimeRep - should we have a new constructor per new primitive type? That's what I went for since it's consistent with what we already had (we already have Int64Rep/Word64Rep)
  • How should we name the new primitive ops? In particular {zero,sign}-extending, truncating, narrowing? I'm currently using things like word8ToWord#, but I noticed that this will be quite confusing, since we already have word2Int# (also notice the To vs 2). So I was thinking of using extendWord8/narrowWord8/extendInt8#/narrowInt8#. What do you think?

I think there's a significant risk of getting too many primops. When you extend a Word8, what do you
extend it to? A Word? Will we need separate primops to convert between Word8 and Int8, etc.?
One option (kind of gross) would be to use the same RuntimeRep for Int8 as Word8, etc., and then
offer primops that work on any types with the relevant RuntimeRep. Or would that be too horrible?

So far I was planning to have only conversions between the small type (e.g., Int8#) and the native
width one (e.g., Int#). Mostly due to simplicity. :) But that does make the conversion between
something like Int8# and Int16# a bit clumsy. (but could be probably optimized in the backend?)

Using the same RuntimeRep (and PrimRep?) would be quite different to what we currenly do, e.g.,
we already have Int64Rep and Word64Rep that different (or IntRep and WordRep). And I'm not
entirely sure what the consequences of this approach would be. :) AFAICS there are a few places in
the compiler where we use that their different, but they don't seem fundamendal at first sight...
(I haven't looked closely though)

But taking that idea a bit further - are there any reasons to keep the IntX# vs WordX# as
separate types in the first place? LLVM IR [1] doesn't differentiate between signed vs unsigned
values either - the integer type defines only its width and it's the operations on those data types
that define whether the values are treated as signed or unsigned. (in fact, the signed vs unsigned
split was removed this some time ago: [2,3])

So I'm wondering if we could simply get away with only having something like Integral#,
Integral8#, Integral16#, etc. I'm probably missing something important here. ;) But I'd be
really interested to learn if there are any strong reasons for the current split.

[1] https://llvm.org/docs/LangRef.html#integer-type
[2] https://bugs.llvm.org/show_bug.cgi?id=950
[3] http://nondot.org/~sabre/LLVMNotes/TypeSystemChanges.txt)

  • The current version doesn't support literals for the new types (i.e., one must do wordToWord8# 42## to get a Word8#). This makes it impossible to support deriving Read/Show for anything that contains the new primitive types. But I'm not sure what syntax we should use? Relying on type-inference would not be backwards compatible, since a lot of code might become ambiguous (unless we default to the native-word width?)

One option is to steal a page from containers and make the Show and Read instances include the
conversion. That is, given

data Foo = Foo Int8#

show (Foo (intToInt8# 5#)) would be "Foo (intToInt8# 5#)". It's not pretty, but at least it would
work. How hard would it be to add literals though? I would think 24#8 should be the Int8# for
24, and 25##16 should be the Word16# for 25.

Good idea - I think it makes sense to start with just printing the conversion functions! And
actually, we only need Show - we don't generate Read instances for types containing Int# or
Word#. (I think I'll keep it as a separate change though - the current diff is already quite
large)

dfeuer added inline comments.Mar 11 2018, 2:39 PM
compiler/codeGen/StgCmmArgRep.hs
74

Can you add a comment explaining why Int8Rep and Word8Rep are "word-sized"? Is this because the arguments are widened when passed to functions?

compiler/ghci/ByteCodeGen.hs
1578

Why not = case n of ... instead of all these guards? Also, you force the results of the recursive calls, but not the final results. One option:

data Boff a = Boff !a !ByteOff
pushPadding :: Int -> BcM (BCInstrList, ByteOff)
pushPadding !n = case go n (Boff nilOL 0) of Boff x y -> return (x, y)
  where
    go n acc@(Boff instrs off) =
      case n of
        0 -> acc
        1 -> Boff (instrs `mappend` unitOL PUSH_PAD8) (off + 1)
        2 -> Boff (instrs `mappend` unitOL PUSH_PAD16) (off + 2)
        3 -> go 1 (go 2 acc)
        4 -> Boff (instrs `mappend` unitOL PUSH_PAD32) (off + 4)
        _ -> go (n - 4) (go 4 acc)
compiler/nativeGen/X86/CodeGen.hs
2381

For some of these narrow divisions, I imagine we very likely want to widen and use multiplication instead when the divisor is known. Would it make sense to add rules to do this now? See https://ghc.haskell.org/trac/ghc/ticket/9786#comment:1.

compiler/utils/Binary.hs
660

This looks overly optimistic now.

libraries/ghc-prim/GHC/Types.hs
386

The order looks arbitrary. I suggest either Int, Int8, Int64, Word, Word8, Word64 or Int,Word,Int8,Word8,Int64,Word64.

michalt updated this revision to Diff 15733.Mar 12 2018, 3:09 PM
michalt marked 4 inline comments as done.
  • address comments from dfeuer
michalt marked an inline comment as done.Mar 12 2018, 3:10 PM
michalt added inline comments.
compiler/nativeGen/X86/CodeGen.hs
2381

I'd prefer to keep it separate from this diff (the nice property of this one is that it should not change anything for existing code)

Also, I'd intuitively do this kind of optimization at the Cmm level - is there some strong reason to do it at the level of nativeGen?

compiler/utils/Binary.hs
660

Yeah, I've started this a while ago ;)

Doh, I just noticed that this was never submitted. Sorry for the latency!

This is probably not ready to be merged, but I'd love to get some feedback:

  • PrimRep/RuntimeRep - should we have a new constructor per new primitive type? That's what I went for since it's consistent with what we already had (we already have Int64Rep/Word64Rep)

Yes, it seems that consistency would dictate that each of these should have a distinct RuntimeRep.

  • How should we name the new primitive ops? In particular {zero,sign}-extending, truncating, narrowing? I'm currently using things like word8ToWord#, but I noticed that this will be quite confusing, since we already have word2Int# (also notice the To vs 2). So I was thinking of using extendWord8/narrowWord8/extendInt8#/narrowInt8#. What do you think?
  • The current version doesn't support literals for the new types (i.e., one must do wordToWord8# 42## to get a Word8#). This makes it impossible to support deriving Read/Show for anything that contains the new primitive types. But I'm not sure what syntax we should use? Relying on type-inference would not be backwards compatible, since a lot of code might become ambiguous (unless we default to the native-word width?)

I suspect punting on literals is indeed the right way forward. Perhaps some day we will have a Num class which is polymorphic in the type's RuntimeRep, in which case we could use "normal" literal syntax. Until then I think requiring an explicit conversion is fine. Afterall, there are plenty of other (arguably more inconvenient) limitations that one encounters when working with unlifted types today.

  • I have no way of testing non-x86 native backends - what's our policy/approach to adding new primops/primitive types in such case? Based on the experience with x86, I doubt they would just work... :/

Yes, this is always a challenge.

  • Any other concerns? Anything fundamental that is missing?

    Thanks!
michalt planned changes to this revision.Apr 7 2018, 5:28 AM
michalt marked an inline comment as done.

@bgamari Thanks for comments! So the plan is to go ahead with printing the conversion functions and do a few renames for consistency. Sadly I'll be able to pick this up only in about 2-3 weeks - hope that's ok. I'll ping the diff once it's ready for another round.

michalt updated this revision to Diff 16363.May 10 2018, 10:50 AM
  • Some renaming of primops
  • Deriving of Show

@bgamari Thanks for comments! So the plan is to go ahead with printing the conversion functions and do a few renames for consistency. Sadly I'll be able to pick this up only in about 2-3 weeks - hope that's ok. I'll ping the diff once it's ready for another round.

I think this is ready for another round of review :)

(warning: this is a really old partial review that I only just discovered I forgot to submit)

This looks pretty good, though I didn't work through all the changes in the NCG in detail.

Yes I think we want new constructors in PrimRep. How are the new types handled by FFI calls?

compiler/cmm/MkGraph.hs
419

Maybe we could have a variant of MO_UU_Conv that isn't required to zero-extend, it can fill the upper bits with garbage. Backends can choose whether to implement it as zero-extension or garbage-filling.

compiler/codeGen/StgCmmPrim.hs
892–895

nit: please fix the long lines

michalt updated this revision to Diff 16544.May 27 2018, 7:03 AM

Address comments from simonmar

michalt marked 2 inline comments as done.May 27 2018, 7:04 AM
michalt added inline comments.
compiler/cmm/MkGraph.hs
419

Added MO_XX_Conv. (I'm open to better names :)

Let me know if that's what you had in mind!

michalt marked 4 inline comments as done.Mon, Jul 9, 2:28 PM

Hi all, could you have another look? I think I addressed all the concerns raised so far.

(also I'm resolving a few comments that were solved and I just forgot to mark them as done)