optimization and rewrite rules questions

Claus Reinke claus.reinke at talk21.com
Tue Feb 24 18:57:17 EST 2009

In the recently burried haskell-cafe thread "speed: ghc vs gcc",
Bulat pointed out some of the optimizations that GHC doesn't
do, such as loop unrolling. I suggested a way of experimenting 
with loop unrolling, using template haskell to bypass GHC's 
blindspot (it usually doesn't unfold recursive definitions
http://www.haskell.org/pipermail/glasgow-haskell-users/2007-July/012936.html ,
but if we unfold a loop combinator at compile time, GHC's
normal optimizations can take over from there):


While this is fine as far as it goes (it should really be handled
within GHC), and does offer some initial speedup, Bulat pointed 
out that GCC does further optimizations after unrolling, such as 
reassociating sums to expose potential for constant folding:


(since the ghc -ddump-simpl output doesn't show this optimization,
I assume that gcc handles it, and the "*ghc*" in that message is a
typo, but haven't checked - how would I do that, btw?). In this
case, GHC optimizations following the loop unrolling leave a sum
like (note the repeated variable interspersed with constants)

    (GHC.Prim.+# ww_s1lN 3)
        (GHC.Prim.+# ww_s1lN 2)
            (GHC.Prim.+# ww_s1lN 1)
            (GHC.Prim.+# (GHC.Prim.+# ww_s1lN 0) ww_s1lR))))))))

which can be simplified (assuming associativity and commutativity
of + here..) after sorting the variable references and constants into
separate groups.

We currently inherit such optimizations when using -fvia-C, even 
though GHC sometimes produces C code that GCC can't handle 
optimally. If I understand correctly, -fvia-C is on its way out - is 
that correct, and what plans are there for recovering the optimizations 
previously left to GCC?

The next thing I was looking at was rewrite rules, the obvious GHC
tool for implementing this kind of rule

    (var+const1)+(var+const2) ==> 2*var + const3

and I ran into more questions:

- can RULES left-hand sides test for variables (I don't want to
    reassociate sums randomly, that wouldn't terminate; instead,
    I want to float out subterms that are non-variable, and group
    repeated variables)?

- is there any way to control the rewrite strategy, similar to
    strategy combinators (if rules are applied all over the place,
    they introduce new structure not covered by rules; if I could
    limit the strategy to top-down, or bottom-up, I could at least
    cover some special cases)?

- how would one handle this kind of optimization in GHC in full
    generality? wait for compiler plugins? are there features of rewrite 
    rules that I'm missing? would it make sense to flag rewrite rules 
    system improvements as a GHC GSoC project, given that GHC 
    will have to pull its weight there when moving away from GCC?


More information about the Glasgow-haskell-users mailing list