Opened 11 years ago

Closed 8 years ago

#2325 closed bug (fixed)

Compile-time computations

Reported by: ajd Owned by:
Priority: low Milestone: 7.4.1
Component: Compiler Version: 6.8.2
Keywords: constant folding Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

$ 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.

Change History (15)

comment:1 Changed 11 years ago by dons

Keywords: constant folding added

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.

comment:2 Changed 11 years ago by simonpj

difficulty: Unknown

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

comment:3 Changed 11 years ago by igloo

Milestone: 6.10 branch

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

comment:4 Changed 11 years ago by 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

comment:5 Changed 11 years ago by 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?)

comment:6 Changed 11 years ago by simonmar

Architecture: UnknownUnknown/Multiple

comment:7 Changed 11 years ago by simonmar

Operating System: UnknownUnknown/Multiple

comment:8 Changed 10 years ago by igloo

Milestone: 6.10 branch6.12 branch

comment:9 Changed 10 years ago by simonmar

Type of failure: Runtime performance bug

comment:10 Changed 9 years ago by igloo

Milestone: 6.12 branch6.12.3

comment:11 Changed 9 years ago by igloo

Milestone: 6.12.36.14.1
Priority: normallow

comment:12 Changed 9 years ago by igloo

Milestone: 7.0.17.0.2

comment:13 Changed 9 years ago by igloo

Milestone: 7.0.27.2.1

comment:14 Changed 8 years ago by igloo

Milestone: 7.2.17.4.1

comment:15 Changed 8 years ago by batterseapower

Resolution: fixed
Status: newclosed

This works now because we added integer Literals to core.

Note: See TracTickets for help on using tickets.