GHC: Ticket #7109: Inlining depends on datatype size, even with INLINE pragmas
http://ghc.haskell.org/trac/ghc/ticket/7109
<p>
Consider the following code:
</p>
<pre class="wiki">data Logic = T | F
| Not Logic
instance GEq Logic
testEqLogic = geq (Not T) (Not F)
</pre><p>
With a proper definitions of generic equality <tt>geq</tt> in class <tt>GEq</tt>, and an <tt>instance Generic Logic</tt>, we get the following core code with -O1:
</p>
<pre class="wiki">Rec {
Bug.$fGEqLogic_$cgeq [Occ=LoopBreaker]
:: Bug.Logic -> Bug.Logic -> GHC.Types.Bool
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType SS]
Bug.$fGEqLogic_$cgeq =
\ (x_ap1 :: Bug.Logic) (y_ap2 :: Bug.Logic) ->
case x_ap1 of _ {
Bug.T ->
case y_ap2 of _ {
Bug.T -> GHC.Types.True;
Bug.F -> GHC.Types.False;
Bug.Not g1_aBc_ayJ -> GHC.Types.False
};
Bug.F ->
case y_ap2 of _ {
Bug.T -> GHC.Types.False;
Bug.F -> GHC.Types.True;
Bug.Not g1_aBc_ayJ -> GHC.Types.False
};
Bug.Not g1_aBc_ayJ ->
case y_ap2 of _ {
__DEFAULT -> GHC.Types.False;
Bug.Not g1_aBc1_XAu -> Bug.$fGEqLogic_$cgeq g1_aBc_ayJ g1_aBc1_XAu
}
}
end Rec }
</pre><p>
Nice and simple, looking just like what we would expect for an equality function for datatype <tt>Logic</tt>.
</p>
<p>
Now we add one more constructor to datatype <tt>Logic</tt> (and adapt the <tt>Generic</tt> instance accordingly):
</p>
<pre class="wiki">data Logic = T | F
| Not Logic
| And Logic Logic
</pre><p>
GHC (HEAD) now generates 3000 lines of core code for the <tt>Bug.$fGEqLogic_$cgeq</tt> function, instead of something only slightly longer than above.
</p>
<p>
Why is this? The second version of our <tt>Logic</tt> datatype is as easy to optimise as the first version; only the terms involved will be slightly longer. Attached file <tt>Bug2.hs</tt> is the input which gives the correct behaviour, while <tt>Bug3.hs</tt> is the input with one added constructor. (You might wonder if it has to do with the fact that the added constructor has more than one argument, but this is not the source of the problem.) Both files have <tt>INLINE</tt> pragmas pretty much everywhere (in fact, we're not <tt>deriving Generic</tt> so that we can put <tt>INLINE</tt> pragmas on <tt>to</tt> and <tt>from</tt>).
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/7109
Trac 1.0.1dreixelWed, 01 Aug 2012 13:12:22 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/7109
http://ghc.haskell.org/trac/ghc/ticket/7109
<ul>
<li><strong>attachment</strong>
set to <em>Bug2.hs</em>
</li>
</ul>
TicketdreixelWed, 01 Aug 2012 13:12:28 GMTattachment set
http://ghc.haskell.org/trac/ghc/ticket/7109
http://ghc.haskell.org/trac/ghc/ticket/7109
<ul>
<li><strong>attachment</strong>
set to <em>Bug3.hs</em>
</li>
</ul>
TicketnfrisbyTue, 21 Aug 2012 16:07:09 GMTcc set
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:1
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:1
<ul>
<li><strong>cc</strong>
<em>nfrisby</em> added
</li>
</ul>
TicketiglooSun, 14 Oct 2012 18:23:15 GMTowner, difficulty, milestone set
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:2
http://ghc.haskell.org/trac/ghc/ticket/7109#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.8.1</em>
</li>
</ul>
<p>
Simon, is some sort of heuristic coming into play?
</p>
TicketthoughtpoliceMon, 28 Apr 2014 12:41:18 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:3
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:3
<ul>
<li><strong>milestone</strong>
changed from <em>7.8.3</em> to <em>7.10.1</em>
</li>
</ul>
<p>
Moving to 7.10.1.
</p>
TicketthomieTue, 25 Nov 2014 04:16:16 GMTstatus changed
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:4
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>infoneeded</em>
</li>
</ul>
<p>
The function <tt>$fGEqLogic_$cgeq</tt> from the output of <tt>ghc -fforce-recomp -ddump-simpl -dsuppress-all -O1 Bug3.hs</tt> with ghc-7.9.20141121 (HEAD):
</p>
<pre class="wiki">Rec {
$fGEqLogic_$cgeq
$fGEqLogic_$cgeq =
\ x_aYx y_aYy ->
let {
$j_s1Y5
$j_s1Y5 =
\ a9_a1kB ->
case y_aYy of _ {
__DEFAULT -> False;
Not g1_aBh_a1kM ->
case a9_a1kB of _ {
L1 a10_a1kz -> $fGEqLogic_$cgeq (a10_a1kz `cast` ...) g1_aBh_a1kM;
R1 a10_X1o5 -> False
};
And g1_aBi_a1kN g2_aBj_a1kO ->
case a9_a1kB of _ {
L1 a10_a1kz -> False;
R1 a10_X1o5 ->
case a10_X1o5 `cast` ... of _ { :*: a11_a171 b1_a172 ->
case $fGEqLogic_$cgeq (a11_a171 `cast` ...) g1_aBi_a1kN of _ {
False -> False;
True -> $fGEqLogic_$cgeq (b1_a172 `cast` ...) g2_aBj_a1kO
}
}
}
} } in
case x_aYx of _ {
T ->
case y_aYy of _ {
T -> True;
F -> False;
Not g1_aBh_a1kM -> False;
And g1_aBi_a1kN g2_aBj_a1kO -> False
};
F ->
case y_aYy of _ {
__DEFAULT -> False;
F -> True
};
Not g1_aBh_a1kM -> $j_s1Y5 (L1 (g1_aBh_a1kM `cast` ...));
And g1_aBi_a1kN g2_aBj_a1kO ->
$j_s1Y5
(R1
((:*: (g1_aBi_a1kN `cast` ...) (g2_aBj_a1kO `cast` ...))
`cast` ...))
}
end Rec }
</pre><p>
Pedro: is that sufficiently small, or do you still think there is a bug somewhere?
</p>
TicketdreixelTue, 25 Nov 2014 13:43:02 GMT
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:5
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:5
<p>
Replying to <a class="infoneeded" href="http://ghc.haskell.org/trac/ghc/ticket/7109#comment:4" title="Comment 4 for Ticket #7109">thomie</a>:
</p>
<blockquote class="citation">
<p>
Pedro: is that sufficiently small, or do you still think there is a bug somewhere?
</p>
</blockquote>
<p>
I think there's still a problem. Let's look at the code for <tt>Bug2.hs</tt>, which simply has one fewer constructor:
</p>
<pre class="wiki">$fGEqLogic_$cgeq
$fGEqLogic_$cgeq =
\ x_aYs y_aYt ->
case x_aYs of _ {
T ->
case y_aYt of _ {
T -> True;
F -> False;
Not g1_aBc_a1kH -> False
};
F ->
case y_aYt of _ {
__DEFAULT -> False;
F -> True
};
Not g1_aBc_a1kH ->
case y_aYt of _ {
__DEFAULT -> False;
Not g1_aBc1_X1mN -> $fGEqLogic_$cgeq g1_aBc_a1kH g1_aBc1_X1mN
}
}
</pre><p>
This looks good. No casts, no <tt>L</tt>/<tt>R</tt>, just a perfectly specialised function.
</p>
<p>
In contrast, <tt>Bug3</tt> (which simply adds one constructor) has generic representation leftovers and casts all over the place. It still feels like something is behaving significantly different just because the datatype got slightly bigger, and I don't know how to tell GHC that it shouldn't be afraid of inlining stuff just because the terms are bigger.
</p>
TicketsimonpjWed, 03 Dec 2014 11:39:03 GMT
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:6
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:6
<p>
Replying to <a class="infoneeded" href="http://ghc.haskell.org/trac/ghc/ticket/7109#comment:5" title="Comment 5 for Ticket #7109">dreixel</a>:
</p>
<blockquote class="citation">
<p>
I don't know how to tell GHC that it shouldn't be afraid of inlining stuff just because the terms are bigger.
</p>
</blockquote>
<p>
Well that's precisely what INLINE pragmas are for. But you know that, so you must mean something else.
</p>
<p>
Pedro, can you be more precise/specific about how to reproduce the problem you are concerned about (perhaps <tt>ghc -O Bug3.hs -ddump-simpl</tt>? I assume you are going to say "I put an INLINE pragma here, but it doesn't work" or something like that. Fine! The more specific you can be, the better chance I have to understand and help.
</p>
<p>
Simon
</p>
TicketthoughtpoliceTue, 23 Dec 2014 13:34:10 GMTmilestone changed
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:7
http://ghc.haskell.org/trac/ghc/ticket/7109#comment:7
<ul>
<li><strong>milestone</strong>
changed from <em>7.10.1</em> to <em>7.12.1</em>
</li>
</ul>
<p>
Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.
</p>
Ticket