# cvs commit: fptools/ghc/compiler/main CmdLineOpts.lhs DriverState.hs fptools/ghc/compiler/simplCore SimplCore.lhs fptools/ghc/compiler/specialise SpecConstr.lhs Rules.lhs Specialise.lhs

Simon Peyton Jones simonpj@glass.cse.ogi.edu
Wed, 28 Feb 2001 03:48:35 -0800

```simonpj     2001/02/28 03:48:35 PST

Modified files:
ghc/compiler/main    CmdLineOpts.lhs DriverState.hs
ghc/compiler/simplCore SimplCore.lhs
ghc/compiler/specialise Rules.lhs Specialise.lhs
ghc/compiler/specialise SpecConstr.lhs
Log:
Add most of the code for constructor specialisation.  The comment
below is reproduced from specialise/SpecConstr.lhs.

It doesn't quite work properly yet, because we need to have
rules in scope in a recursive function's own RHS, and that
entails a bit of fiddling I havn't yet completed.  But SpecConstr
itself is a nice neat 250 lines of code.

-----------------------------------------------------
Game plan
-----------------------------------------------------

Consider
drop n []     = []
drop 0 xs     = []
drop n (x:xs) = drop (n-1) xs

After the first time round, we could pass n unboxed.  This happens in
numerical code too.  Here's what it looks like in Core:

drop n xs = case xs of
[]     -> []
(y:ys) -> case n of
I# n# -> case n# of
0 -> []
_ -> drop (I# (n# -# 1#)) xs

Notice that the recursive call has an explicit constructor as argument.
Noticing this, we can make a specialised version of drop

RULE: drop (I# n#) xs ==> drop' n# xs

drop' n# xs = let n = I# n# in ...orig RHS...

Now the simplifier will apply the specialisation in the rhs of drop', giving

drop' n# xs = case xs of
[]     -> []
(y:ys) -> case n# of
0 -> []
_ -> drop (n# -# 1#) xs

Much better!

We'd also like to catch cases where a parameter is carried along unchanged,
but evaluated each time round the loop:

f i n = if i>0 || i>n then i else f (i*2) n

Here f isn't strict in n, but we'd like to avoid evaluating it each iteration.
In Core, by the time we've w/wd (f is strict in i) we get

f i# n = case i# ># 0 of
False -> I# i#
True  -> case n of n' { I# n# ->
case i# ># n# of
False -> I# i#
True  -> f (i# *# 2#) n'

At the call to f, we see that the argument, n is know to be (I# n#),
and n is evaluated elsewhere in the body of f, so we can play the same
trick as above.  However we don't want to do that if the boxed version
of n is needed (else we'd avoid the eval but pay more for re-boxing n).
So in this case we want that the *only* uses of n are in case statements.

So we look for

* A self-recursive function.  Ignore mutual recursion for now,
because it's less common, and the code is simpler for self-recursion.

* EITHER

a) At a recursive call, one or more parameters is an explicit
constructor application
AND
That same parameter is scrutinised by a case somewhere in
the RHS of the function

OR

b) At a recursive call, one or more parameters has an unfolding
that is an explicit constructor application
AND
That same parameter is scrutinised by a case somewhere in
the RHS of the function
AND
Those are the only uses of the parameter

Revision  Changes    Path
1.134     +1 -0      fptools/ghc/compiler/main/CmdLineOpts.lhs
1.30      +5 -1      fptools/ghc/compiler/main/DriverState.hs
1.91      +3 -0      fptools/ghc/compiler/simplCore/SimplCore.lhs
1.22      +5 -6      fptools/ghc/compiler/specialise/Rules.lhs
1.72      +11 -10    fptools/ghc/compiler/specialise/Specialise.lhs

```