Better CSE optimisation

[simonmar]

GHC's CSE optimisation is pretty weedy. It looks for expressions like this:

   let x = e1 in e2

and replaces all occurrences of e1 in e2 with x. This doesn't do full CSE, but it does catch some cases. There have been case where full CSE would be significantly beneficial, though.

One possible way forward is to have a separate CSE pass that transformed expressions containing common subexpressions into the let-form above, and let the existing CSE pass do the final replacement.

We must be cautious, though: increasing sharing can introduce space leaks. Sometimes we can prove that this cannot happen, for example when the shared object is primitive, or has a bounded size.

[guest]

we also can add pragma like

{-# CSE f #-}

[michalt]

Interesting ticket. :)

One possible way forward is to have a separate CSE pass that transformed expressions containing common subexpressions into the let-form above, and let the existing CSE pass do the final replacement.

But how to identify those subexpressions that are common? Wouldn't that need another pass? I was thinking about sligthly modifying the idea: have one pass to identify common subexpressions and then a second one that is an improved version of current CSE, i.e. uses the information about what subexpressions could be shared to split more complex expressions and also does the elimination along the way. Like

  let x = e1 + e2
      y = e1 + e3         

So e1 would be identified as a common subexpression and then so we would transfor the above to:

  let z = e1     
      x = z + e2 
      y = z + e3 

What do you think?

[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

[tibbe]

You might also want to look into Global Value Numbering.

[morabbin]

Seems to be obsolete now, given the presence of #5996, #5344, #2940, and others indicating that CSE is being actively worked on, and with more specifics than here.

Recommend resolve as duplicate.

[simonmar]

Looking at the tickets, they don't completely overlap. This one is about spotting common subexpressions when they don't occur in the form let x = e in E[e]. #2940 would fix some of those cases, but not all.