Compile-time computations

[ajd]

$ cat Reduce3.hs 
module Reduce3
  where

foo = 1 + 2
$ cat Reduce4.hs 
module Reduce4
  where

foo = 3
$ ghc -c -O2 -fforce-recomp -ddump-simpl Reduce3.hs 

==================== Tidy Core ====================
Reduce3.lvl :: GHC.Num.Integer
[GlobalId]
[NoCafRefs]
Reduce3.lvl = GHC.Num.S# 1

Reduce3.lvl1 :: GHC.Num.Integer
[GlobalId]
[NoCafRefs]
Reduce3.lvl1 = GHC.Num.S# 2

Reduce3.foo :: GHC.Num.Integer
[GlobalId]
[Str: DmdType]
Reduce3.foo = GHC.Num.plusInteger Reduce3.lvl Reduce3.lvl1



==================== Tidy Core Rules ====================


$ ghc -c -O2 -fforce-recomp -ddump-simpl Reduce4.hs 

==================== Tidy Core ====================
Reduce4.foo :: GHC.Num.Integer
[GlobalId]
[NoCafRefs
 Str: DmdType]
Reduce4.foo = GHC.Num.S# 3




==================== Tidy Core Rules ====================

It would be nice if GHC could do the addition at compile time (since, after all, the result will always be the same) instead of at runtime.

[dons]

I think this is specific to Integer, which is a more complex type.

If you constrain your values to be machine Int,

module M where

foo :: Int
foo = 1 + 2

Then we see the +# rule fire,

1 RuleFired
    1 +#
4 BetaReduction
3 KnownBranch
9 SimplifierDone

------------------------------- Core -----------------------------------

M.foo :: Int
M.foo = I# 3

So perhaps it is a simple matter of adding these rules to the compiler.

[simonpj]

You have to be a bit careful. It's not always the case that

   S# x + S# y   =    S# (x+y)

If the sum is too big the result should be a J#.

I can think of two ways to do this.

• Add a BuiltInRule for plusInteger in prelude/PrelRules.lhs. But that would risk getting out of sync with the implementation in the integer package.

• Add a RULE for GHC.Integer.plusInteger of form

    plusInteger (S# x) (S# y) = plusIntegerS x y
  

  and add code to GHC.Integer to implement plusIntegerS. Something like

  plusIntegerS :: Int# -> Int# -> Integer
  plusIntegerS i j 
    = case addIntC# i j of
        (# r, c #) -> if c ==# 0#
                      then S# r
                      else plusInteger (toBigS i1) (toBigS i2)
  

  Check that plusIntegerS will inline when given literals as arguments. And add a BuiltInRule for the addIntC# primop.

The latter approach seems better, since it'll benefit all users of addIntC#, but it has the problem that the host platform and target platform might not have the same beliefs about word size, so it's not obvious how to do the Right Thing in the BuiltInRule for addIntC#. I'm not sure what a good way to solve that is.

Simon

[igloo]

Can we do the rule at an earlier point, i.e.

(fromInteger <numeric literal x>) + (fromInteger <numeric literal y>)
  ==>
(fromInteger <numeric literal (x + y)>)

where we have inferred that the type is Integer? Then we don't have to worry about any checking that we don't already do.

Re word size differences, we already have that problem when we transform

(fromInteger 3)

into

S# 3

[simonpj]

I don't think so. Here's the Num instance for Integer:

instance Num Integer where
  fromInteger x = x

The argument to fromInteger is, well, an Integer. So the desugarer converts 3 to smallInteger 3#, where 3# :: Int#. For bigger integers (and the desugarer must make a conservative (wrt word size) estimate of what "big" is), it converts 779988998 into

  (smallInteger 7799# `timesInteger` smallInteger 100000#) 
     `plusInteger` smallInteger 88998

or whatever. The function smallInteger comes from library GHC.Integer in packages integer.

Hmm. I suppose that we could use the BuiltInRule method thus

   smallInteger a `plusInteger` smallInteger b = smallInteger (a + #b)
       if (a +# b) is not "big"

using the same conservative estimate for "big" that the desugarer does. (A BuiltInRule can have a side condition such as the one above.)

To do that we'd have to ensure that smallInteger wasn't inlined too early...and we'd sadly miss any opportunities that arose after it was inlined.

Simon

[Isaac Dupree]

Couldn't the desugarer treat them as Integers and the code generator deal with it later? (this assumes that GHC's integers and the boot-lib integers are extensionally equivalent, which should be a reasonable assumption!) (I'm sure I'm just being naive here? But do we really necessarily lose out for treating Integers as a unit we can understand rather than a composition of Int#s?)

[batterseapower]

This works now because we added integer Literals to core.