GHC: Ticket #5722: GHC inlines class method forever
http://ghc.haskell.org/trac/ghc/ticket/5722
<p>
irene-knapp showed me this over IRC, I refined the test case a bit:
</p>
<pre class="wiki">{-# LANGUAGE FlexibleContexts, MultiParamTypeClasses #-}
module Bug () where
class C a b where
discord :: C a b => a b () -- Remove the constraint and it works
rhyme :: a b ()
instance C (,) b => C (,) [b] where
discord = discord
rhyme = discord
</pre><p>
GHC 7.2.2 compiling this with -O loops forever. I've worked out:
</p>
<ul><li>The <tt>C a b</tt> context in the class is completely superfluous but the bug isn't triggered without it.
</li><li>The pattern of recursion in the two method signatures is fragile: <tt>rhyme = rhyme</tt> doesn't trigger the bug, for example.
</li><li>Adding a <tt>NOINLINE discord</tt> stops the bug from triggering. Similarly, compiling without optimisations doesn't trigger the bug.
</li><li>While it's looping, GHC slowly but steadily chews through all of your memory.
</li></ul>en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/5722
Trac 1.0.1IreneSat, 24 Dec 2011 02:48:00 GMTcc set
http://ghc.haskell.org/trac/ghc/ticket/5722#comment:1
http://ghc.haskell.org/trac/ghc/ticket/5722#comment:1
<ul>
<li><strong>cc</strong>
<em>ireney.knapp@…</em> added
</li>
</ul>
TicketiglooSun, 25 Dec 2011 10:41:13 GMTowner, difficulty, milestone set
http://ghc.haskell.org/trac/ghc/ticket/5722#comment:2
http://ghc.haskell.org/trac/ghc/ticket/5722#comment:2
<ul>
<li><strong>owner</strong>
set to <em>simonpj</em>
</li>
<li><strong>difficulty</strong>
set to <em>Unknown</em>
</li>
<li><strong>milestone</strong>
set to <em>7.6.1</em>
</li>
</ul>
TickethvrSun, 25 Dec 2011 16:53:15 GMTcc changed
http://ghc.haskell.org/trac/ghc/ticket/5722#comment:3
http://ghc.haskell.org/trac/ghc/ticket/5722#comment:3
<ul>
<li><strong>cc</strong>
<em>hvr@…</em> added
</li>
</ul>
<p>
Jfyi, GHC 7.4.0.20111219 (= RC 1) shows the same misbehaviour...
</p>
TicketsimonpjWed, 28 Dec 2011 14:00:10 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/5722#comment:4
http://ghc.haskell.org/trac/ghc/ticket/5722#comment:4
<ul>
<li><strong>milestone</strong>
changed from <em>7.6.1</em> to <em>_|_</em>
</li>
</ul>
<p>
Thanks. This is almost identical to <a class="new ticket" href="http://ghc.haskell.org/trac/ghc/ticket/5448" title="bug: GHC stuck in infinite loop compiling with optimizations (new)">#5448</a>, but even simpler. For the record, here's an even simpler example
</p>
<pre class="wiki">class C a b where
discord :: C a b => a b () -- Remove the constraint and it works
instance C (,) b => C (,) [b] where
discord = discord
foo :: C (,) b => (,) [b] ()
foo = discord
</pre><p>
Here is how it plays out. We get this code (in reality the <tt>MkC</tt> stuff is a newtype, but that's irrelevant):
</p>
<pre class="wiki">$cd d1 d2 = discord d2 d2
discord d = case d of MkC x -> x
$fC d = MkC ($cd d)
foo d = discord ($fC d) ($fC d)
</pre><p>
None of these definitions are recursive. So when we simplify <tt>foo</tt> we get
</p>
<pre class="wiki">discord ($fC d) ($fC d)
--> (case ($fC d) of MkC x -> x) ($fC d)
--> (case (MkC ($cd d)) of MkC x -> x) ($fC d)
--> $cd d ($fC d)
--> discord ($fC d) ($fC d)
</pre><p>
and there is the loop.
</p>
<p>
The culprit is, as usual, the data type for the dictionary, which has itself appearing contravariantly:
</p>
<pre class="wiki">data C a b = MkC (C a b => a b ())
</pre><p>
The tick-count thing means that with 5.4 we get <tt>Simplifier ticks exhausted</tt>, and adding <tt>-ddump-simpl-stats</tt> points fairly clearly to the culprit. It's fixable by adding <tt>{-# NOINLINE discord #-}</tt> on the instance declaration.
</p>
<p>
None of this is satisfactory. The difficulty is that I do not know how to solve the problem in general -- at least not without hobbling the optimiser. I suppose that we could spot the special case of a class that mentions itself in the context of a class method, but that is a very special case.
</p>
TicketsimonpjMon, 30 Jun 2014 09:24:24 GMT
http://ghc.haskell.org/trac/ghc/ticket/5722#comment:5
http://ghc.haskell.org/trac/ghc/ticket/5722#comment:5
<p>
See <a class="new ticket" href="http://ghc.haskell.org/trac/ghc/ticket/9235" title="bug: Simplifier ticks exhausted on recursive class method (new)">#9235</a> for another example.
</p>
TicketklaoMon, 30 Jun 2014 09:42:06 GMTcc changed
http://ghc.haskell.org/trac/ghc/ticket/5722#comment:6
http://ghc.haskell.org/trac/ghc/ticket/5722#comment:6
<ul>
<li><strong>cc</strong>
<em>klao@…</em> added
</li>
</ul>
<p>
One aspect in which the <a class="new ticket" href="http://ghc.haskell.org/trac/ghc/ticket/9235" title="bug: Simplifier ticks exhausted on recursive class method (new)">#9235</a> example is different, is that it triggers the bug even with <tt>-O0</tt>. (I'm not sure if this is important or not.)
</p>
Ticket