Opened 10 years ago
Last modified 4 years ago
#701 new task
Better CSE optimisation
Reported by: | simonmar | Owned by: | michalt |
---|---|---|---|
Priority: | normal | Milestone: | ⊥ |
Component: | Compiler | Version: | 6.4.1 |
Keywords: | Cc: | Bulat.Ziganshin@…, pho@… | |
Operating System: | Unknown/Multiple | Architecture: | Unknown/Multiple |
Type of failure: | None/Unknown | Test Case: | N/A |
Blocked By: | Blocking: | ||
Related Tickets: | Differential Rev(s): | ||
Wiki Page: |
Description
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.
Change History (14)
comment:1 Changed 10 years ago by igloo
- Milestone set to 6.8
- Test Case set to N/A
comment:2 Changed 9 years ago by guest
- Cc Bulat.Ziganshin@… added
comment:3 Changed 9 years ago by simonmar
- Milestone changed from 6.8 branch to _|_
comment:4 Changed 8 years ago by simonmar
- Architecture changed from Unknown to Unknown/Multiple
comment:5 Changed 8 years ago by simonmar
- Operating System changed from Unknown to Unknown/Multiple
comment:6 Changed 7 years ago by PHO
- Cc pho@… added
comment:7 Changed 7 years ago by simonmar
- difficulty changed from Difficult (1 week) to Difficult (2-5 days)
comment:8 Changed 6 years ago by SamAnklesaria
- Owner set to SamAnklesaria
- Type of failure set to None/Unknown
comment:9 Changed 6 years ago by SamAnklesaria
- Owner SamAnklesaria deleted
comment:10 Changed 5 years ago by michalt
- Owner set to 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?
comment:11 Changed 5 years ago 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
comment:12 Changed 5 years ago by tibbe
You might also want to look into Global Value Numbering.
comment:13 Changed 4 years ago by morabbin
comment:14 Changed 4 years ago by 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.
we also can add pragma like
{-# CSE f #-}