title: Specialization with Constraints
body: <p>I'm having problems getting GHC to specialize a function with a class constraint. I have a minimal example of my problem here: <a href="http://lpaste.net/98464" rel="nofollow noreferrer">Foo.hs</a> and  <a href="http://lpaste.net/98342" rel="nofollow noreferrer">Main.hs</a>. The two files compile (GHC 7.6.2, <code>ghc -O3 Main</code>) and run.</p>
  
  <p><strong>NOTE:</strong>
  <code>Foo.hs</code> is really stripped down. If you want to see why the constraint is needed, you can see a little more code <a href="http://lpaste.net/98840" rel="nofollow noreferrer">here</a>. If I put the code in a single file or make many other minor changes, GHC simply inlines the call to <code>plusFastCyc</code>. This will not happen in the real code because <code>plusFastCyc</code> is too large for GHC to inline, even when marked <code>INLINE</code>. The point is to <em>specialize</em> the call to <code>plusFastCyc</code>, not inline it. <code>plusFastCyc</code> is called in many places in the real code, so duplicating such a large function would not be desirable even if I could force GHC to do it.</p>
  
  <p>The code of interest is the <code>plusFastCyc</code> in <code>Foo.hs</code>, reproduced here:</p>
  
  <pre><code>{-# INLINEABLE plusFastCyc #-}
  {-# SPECIALIZE plusFastCyc :: 
           forall m . (Factored m Int) =&gt; 
                (FastCyc (VT U.Vector m) Int) -&gt; 
                     (FastCyc (VT U.Vector m) Int) -&gt; 
                          (FastCyc (VT U.Vector m) Int) #-}
  
  -- Although the next specialization makes `fcTest` fast,
  -- it isn't useful to me in my real program because the phantom type M is reified
  -- {-# SPECIALIZE plusFastCyc :: 
  --          FastCyc (VT U.Vector M) Int -&gt; 
  --               FastCyc (VT U.Vector M) Int -&gt; 
  --                    FastCyc (VT U.Vector M) Int #-}
  
  plusFastCyc :: (Num (t r)) =&gt; (FastCyc t r) -&gt; (FastCyc t r) -&gt; (FastCyc t r)
  plusFastCyc (PowBasis v1) (PowBasis v2) = PowBasis $ v1 + v2
  </code></pre>
  
  <p>The <code>Main.hs</code> file has two drivers: <code>vtTest</code>, which runs in ~3 seconds, and <code>fcTest</code>, which runs in ~83 seconds when compiled with -O3 using the <code>forall</code>'d specialization.</p>
  
  <p>The <a href="http://lpaste.net/98593" rel="nofollow noreferrer">core shows</a> that for the <code>vtTest</code> test, the addition code is being specialized to <code>Unboxed</code> vectors over <code>Int</code>s, etc, while generic vector code is used for <code>fcTest</code>.
  On line 10, you can see that GHC does write a specialized version of <code>plusFastCyc</code>, compared to the generic version on line 167.
  The rule for the specialization is on line 225. I believe this rule should fire on line 270. (<code>main6</code> calls <code>iterate main8 y</code>, so <code>main8</code> is where <code>plusFastCyc</code> should be specialized.)</p>
  
  <p>My goal is to make <code>fcTest</code> as fast as <code>vtTest</code> by specializing <code>plusFastCyc</code>. I've found two ways to do this:</p>
  
  <ol>
  <li>Explicity call <code>inline</code> from <code>GHC.Exts</code> in <code>fcTest</code>.</li>
  <li>Remove the <code>Factored m Int</code> constraint on <code>plusFastCyc</code>.</li>
  </ol>
  
  <p>Option 1 is unsatisfactory because in the actual code base <code>plusFastCyc</code> is a frequently used operation and a <em>very</em> large function, so it should not be inlined at every use. Rather, GHC should call a specialized version of <code>plusFastCyc</code>. Option 2 is not really an option because I need the constraint in the real code.</p>
  
  <p>I've tried a variety of options using (and not using) <code>INLINE</code>, <code>INLINABLE</code>, and <code>SPECIALIZE</code>, but nothing seems to work. (<strong>EDIT</strong>: I may have stripped out too much of <code>plusFastCyc</code> to make my example small, so <code>INLINE</code> might cause the function to be inlined. This doesn't happen in my real code because <code>plusFastCyc</code> is so large.) In this particular example, I'm not getting any <a href="http://web.archiveorange.com/archive/v/2B0uXzyXUnvOzzIApVfp" rel="nofollow noreferrer"><code>match_co: needs more cases</code></a> or <a href="https://stackoverflow.com/questions/18792388/haskell-ghc-specialize-causes-rule-left-hand-side-too-complicated-to"><code>RULE: LHS too complicated to desugar</code></a> (and <a href="https://ghc.haskell.org/trac/ghc/ticket/5821" rel="nofollow noreferrer">here</a>) warnings, though I was getting many <code>match_co</code> warnings before minimizing the example. Presumably, the "problem" is the <code>Factored m Int</code> constraint in the rule; if I make changes to that constraint, <code>fcTest</code> runs as fast as <code>vtTest</code>.</p>
  
  <p>Am I doing something GHC just doesn't like? Why won't GHC specialize the <code>plusFastCyc</code>, and how can I make it?</p>
  
  <p><strong>UPDATE</strong></p>
  
  <p>The problem persists in GHC 7.8.2, so this question is still relevant.</p>