Opened 12 years ago
Last modified 6 months ago
#701 new task
Better CSE optimisation
Reported by: | simonmar | Owned by: | michalt |
---|---|---|---|
Priority: | normal | Milestone: | ⊥ |
Component: | Compiler | Version: | 6.4.1 |
Keywords: | CSE | 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 (15)
comment:1 Changed 11 years ago by
Milestone: | → 6.8 |
---|---|
Test Case: | → N/A |
comment:2 Changed 10 years ago by
Cc: | Bulat.Ziganshin@… added |
---|
comment:3 Changed 10 years ago by
Milestone: | 6.8 branch → _|_ |
---|
comment:4 Changed 9 years ago by
Architecture: | Unknown → Unknown/Multiple |
---|
comment:5 Changed 9 years ago by
Operating System: | Unknown → Unknown/Multiple |
---|
comment:6 Changed 8 years ago by
Cc: | pho@… added |
---|
comment:7 Changed 8 years ago by
difficulty: | Difficult (1 week) → Difficult (2-5 days) |
---|
comment:8 Changed 7 years ago by
Owner: | set to SamAnklesaria |
---|---|
Type of failure: | → None/Unknown |
comment:9 Changed 7 years ago by
Owner: | SamAnklesaria deleted |
---|
comment:10 Changed 6 years ago by
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 6 years ago by
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 wherex
is defined- The definitions of
x
andy
look different but are the same - Ditto the definitions of
a
andb
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:13 Changed 5 years ago by
comment:14 Changed 5 years ago by
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.
comment:15 Changed 6 months ago by
Keywords: | CSE added |
---|
we also can add pragma like
{-# CSE f #-}