Common subexpression elemination (CSE)

[Simon Peyton-Jones]

GHC does a very simple form of CSE. If it sees
        let x = e in ....e....
it replaces the inner 'e' by x.  But that's all at the moment.

Simon

| -----Original Message-----
| From: glasgow-haskell-users-bounces at haskell.org [mailto:glasgow-haskell-users-bounces at haskell.org]
| On Behalf Of Lennart Augustsson
| Sent: 27 November 2006 13:40
| To: Christian Maeder
| Cc: GHC Users Mailing List
| Subject: Re: Common subexpression elemination (CSE)
|
| 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
|
| _______________________________________________
| Glasgow-haskell-users mailing list
| Glasgow-haskell-users at haskell.org
| http://www.haskell.org/mailman/listinfo/glasgow-haskell-users