GHC: Ticket #701: Better CSE optimisation
http://ghc.haskell.org/trac/ghc/ticket/701
<p>
GHC's CSE optimisation is pretty weedy. It looks for expressions like this:
</p>
<pre class="wiki"> let x = e1 in e2
</pre><p>
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.
</p>
<p>
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.
</p>
<p>
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.
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/701
Trac 1.0.7iglooFri, 20 Oct 2006 18:45:09 GMTtestcase, milestone set
http://ghc.haskell.org/trac/ghc/ticket/701#comment:1
http://ghc.haskell.org/trac/ghc/ticket/701#comment:1
<ul>
<li><strong>testcase</strong>
set to <em>N/A</em>
</li>
<li><strong>milestone</strong>
set to <em>6.8</em>
</li>
</ul>
TicketguestTue, 03 Jul 2007 10:15:15 GMTcc set
http://ghc.haskell.org/trac/ghc/ticket/701#comment:2
http://ghc.haskell.org/trac/ghc/ticket/701#comment:2
<ul>
<li><strong>cc</strong>
<em>Bulat.Ziganshin@…</em> added
</li>
</ul>
<p>
we also can add pragma like
</p>
<p>
{-# CSE f #-}
</p>
TicketsimonmarMon, 12 Nov 2007 14:08:35 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/701#comment:3
http://ghc.haskell.org/trac/ghc/ticket/701#comment:3
<ul>
<li><strong>milestone</strong>
changed from <em>6.8 branch</em> to <em>_|_</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:37:15 GMTarchitecture changed
http://ghc.haskell.org/trac/ghc/ticket/701#comment:4
http://ghc.haskell.org/trac/ghc/ticket/701#comment:4
<ul>
<li><strong>architecture</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:51:04 GMTos changed
http://ghc.haskell.org/trac/ghc/ticket/701#comment:5
http://ghc.haskell.org/trac/ghc/ticket/701#comment:5
<ul>
<li><strong>os</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketPHOMon, 16 Nov 2009 10:25:52 GMTcc changed
http://ghc.haskell.org/trac/ghc/ticket/701#comment:6
http://ghc.haskell.org/trac/ghc/ticket/701#comment:6
<ul>
<li><strong>cc</strong>
<em>pho@…</em> added
</li>
</ul>
TicketsimonmarMon, 16 Nov 2009 13:14:45 GMTdifficulty changed
http://ghc.haskell.org/trac/ghc/ticket/701#comment:7
http://ghc.haskell.org/trac/ghc/ticket/701#comment:7
<ul>
<li><strong>difficulty</strong>
changed from <em>Difficult (1 week)</em> to <em>Difficult (2-5 days)</em>
</li>
</ul>
TicketSamAnklesariaMon, 30 Aug 2010 03:41:20 GMTowner, failure set
http://ghc.haskell.org/trac/ghc/ticket/701#comment:8
http://ghc.haskell.org/trac/ghc/ticket/701#comment:8
<ul>
<li><strong>owner</strong>
set to <em>SamAnklesaria</em>
</li>
<li><strong>failure</strong>
set to <em>None/Unknown</em>
</li>
</ul>
TicketSamAnklesariaSun, 05 Sep 2010 23:19:29 GMTowner deleted
http://ghc.haskell.org/trac/ghc/ticket/701#comment:9
http://ghc.haskell.org/trac/ghc/ticket/701#comment:9
<ul>
<li><strong>owner</strong>
<em>SamAnklesaria</em> deleted
</li>
</ul>
TicketmichaltSun, 30 Oct 2011 20:44:19 GMTowner set
http://ghc.haskell.org/trac/ghc/ticket/701#comment:10
http://ghc.haskell.org/trac/ghc/ticket/701#comment:10
<ul>
<li><strong>owner</strong>
set to <em>michalt</em>
</li>
</ul>
<p>
Interesting ticket. :)
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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
</p>
<pre class="wiki"> let x = e1 + e2
y = e1 + e3
</pre><p>
So <tt>e1</tt> would be identified as a common subexpression and then so we would
transfor the above to:
</p>
<pre class="wiki"> let z = e1
x = z + e2
y = z + e3
</pre><p>
What do you think?
</p>
TicketsimonpjMon, 31 Oct 2011 20:48:08 GMT
http://ghc.haskell.org/trac/ghc/ticket/701#comment:11
http://ghc.haskell.org/trac/ghc/ticket/701#comment:11
<p>
Yes, something like that. Don't forget that CSE might reveal furhter opportunities for CSE.... for example
</p>
<pre class="wiki">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 ...
</pre><p>
Here, we can common-up <tt>x</tt> and <tt>y</tt>, and then in turn <tt>a</tt> and <tt>b</tt>. Note that
</p>
<ul><li><tt>v</tt> is not in scope where <tt>x</tt> is defined
</li><li>The definitions of <tt>x</tt> and <tt>y</tt> look different but are the same
</li><li>Ditto the definitions of <tt>a</tt> and <tt>b</tt>
</li></ul><p>
Here's the result we want:
</p>
<pre class="wiki">let v = p + q in
let x = v * r in
let y = x in
let a = x + v in
let b = a in ...
</pre><p>
I think the key word is <em>hash-consing</em>. Never build an expression that you have already built.
</p>
<p>
I'm sure there is a good literature on CSE if you look in compiler books.
</p>
<p>
Don't forget that CSE can make things worse by introducing a space leak. Consider
</p>
<pre class="wiki">f n = sum [1..n] / length [1..n]
</pre><p>
Doing CSE in <tt>[1..n]</tt> will change the space behaviour from constant to linear in n.
</p>
<p>
Simon
</p>
TickettibbeMon, 31 Oct 2011 21:01:46 GMT
http://ghc.haskell.org/trac/ghc/ticket/701#comment:12
http://ghc.haskell.org/trac/ghc/ticket/701#comment:12
<p>
You might also want to look into Global Value Numbering.
</p>
TicketmorabbinSun, 20 Jan 2013 23:02:10 GMT
http://ghc.haskell.org/trac/ghc/ticket/701#comment:13
http://ghc.haskell.org/trac/ghc/ticket/701#comment:13
<p>
Seems to be obsolete now, given the presence of <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/5996" title="bug: fix for CSE (closed: fixed)">#5996</a>, <a class="new ticket" href="http://ghc.haskell.org/trac/ghc/ticket/5344" title="feature request: CSE should look through coercions (new)">#5344</a>, <a class="new ticket" href="http://ghc.haskell.org/trac/ghc/ticket/2940" title="bug: Do CSE after CorePrep (new)">#2940</a>, and others indicating that CSE is being actively worked on, and with more specifics than here.
</p>
<p>
Recommend resolve as duplicate.
</p>
TicketsimonmarMon, 21 Jan 2013 05:43:22 GMT
http://ghc.haskell.org/trac/ghc/ticket/701#comment:14
http://ghc.haskell.org/trac/ghc/ticket/701#comment:14
<p>
Looking at the tickets, they don't completely overlap. This one is about spotting common subexpressions when they don't occur in the form <tt>let x = e in E[e]</tt>. <a class="new ticket" href="http://ghc.haskell.org/trac/ghc/ticket/2940" title="bug: Do CSE after CorePrep (new)">#2940</a> would fix some of those cases, but not all.
</p>
Ticket