#701: Better CSE optimisation
---------------------------------+------------------------------------------
Reporter: simonmar | Owner: michalt
Type: task | Status: new
Priority: normal | Milestone: _|_
Component: Compiler | Version: 6.4.1
Keywords: | Testcase: N/A
Blockedby: | Difficulty: Difficult (2-5 days)
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: None/Unknown
---------------------------------+------------------------------------------
Comment(by simonpj):
Yes, something like that. Don't forget that CSE might reveal furhter
opportunities for CSE.... for example
{{{
let x = (p+q) * r in
let v = p+q in
let y = v * r in
let a = y + v in
let b = x + v in ...
}}}
Here, we can common-up `x` and `y`, and then in turn `a` and `b`. Note
that
* `v` is not in scope where `x` is defined
* The definitions of `x` and `y` look different but are the same
* Ditto the definitions of `a` and `b`
Here's the result we want:
{{{
let v = p + q in
let x = v * r in
let y = x in
let a = x + v in
let b = a in ...
}}}
I think the key word is ''hash-consing''. Never build an expression that
you have already built.
I'm sure there is a good literature on CSE if you look in compiler books.
Don't forget that CSE can make things worse by introducing a space leak.
Consider
{{{
f n = sum [1..n] / length [1..n]
}}}
Doing CSE in `[1..n]` will change the space behaviour from constant to
linear in n.
Simon
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/701#comment:11>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
