Common subexpression elemination (CSE)

[Lennart Augustsson]

GHC doesn't normally do CSE.  CSE can cause space leaks, so you can't  
do it willy-nilly.
I'm sure there are some strict contexts where it could be done  
safely, but I don't think ghc uses that information (yet).

	-- Lennart

On Nov 27, 2006, at 08:34 , Christian Maeder wrote:

> the following code does not run as fast as expected:
>
> modexp a e n = if e <= 0 then 1 else
>    if even e
>    then mod (modexp a (div e 2) n * modexp a (div e 2) n) n
>    else mod (a * modexp a (e - 1) n) n
>
> it gets only fast if written as:
>
> modexp2 a e n = if e <= 0 then 1 else
>    if even e
>    then let d = modexp2 a (div e 2) n in mod (d * d) n
>    else mod (a * modexp2 a (e - 1) n) n
>
> I wonder, why the common subexpression "modexp a (div e 2) n" is not
> eliminated in the first case. Does CSE work at all?
>
> For testing the exponent "e" should have at least 10 digits.
>
> Cheers Christian
>
> P.S. Other alternatives are slower, too
>
> modexp1 a e n = if e <= 0 then 1 else
>     mod (a * modexp1 a (e - 1) n) n
>
> modexp3 a e n = mod (a ^ e) n
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users