GHC: Ticket #5997: GHC fails to make function tail recursive
http://ghc.haskell.org/trac/ghc/ticket/5997
<p>
Sometimes GHC does not compile function as tail recursive despite it looks like tail recursive. Here is simplified example.
</p>
<pre class="wiki">{-# LANGUAGE BangPatterns #-}
incompleteBetaWorker :: Double -> Double
incompleteBetaWorker _ = loop 1 1 1 1
where
-- Constants
eps = 1e-15
-- Loop
loop :: Double -> Int -> Double -> Double -> Double
loop !psq !ns !term !betain
| done = betain'
| otherwise = loop psq' (ns - 1) term' betain'
where
-- New values
term' = term
betain' = betain
psq' = if ns < 0 then psq + 1 else psq
-- This condition cause stack overflow
done = db <= eps && db <= eps*betain' where db = abs term'
-- With this it loops endlessly
-- done = db <= eps * betain' where db = abs term'
main :: IO ()
main = print $ incompleteBetaWorker 0
</pre><p>
If second equation for done is used function is tail recursive and works in constant space. if first one (uncommented) is used it isn't. From looking at the it looks loop is converted to several corecursive functions.
</p>
<p>
Such loops appear frequently in numerical code and it's important to ensure that worker function is tail recursive since getting answer may require a lot of iteration.
</p>
<p>
I've tested it with GHC 7.2.2 and 7.4.1. Both are affected. Example was compiled with -O2.
</p>
en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/5997
Trac 1.0.1simonpjFri, 13 Apr 2012 18:53:33 GMTstatus changed; difficulty, resolution set
http://ghc.haskell.org/trac/ghc/ticket/5997#comment:1
http://ghc.haskell.org/trac/ghc/ticket/5997#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>difficulty</strong>
set to <em>Unknown</em>
</li>
<li><strong>resolution</strong>
set to <em>duplicate</em>
</li>
</ul>
<p>
Thanks. Turns out to be a dup of <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/5920" title="bug: stack overflow in strict function depending on return type (closed: fixed)">#5920</a>. But I'll add this as a second test case.
</p>
Ticketsimonpj@…Fri, 20 Apr 2012 16:44:17 GMT
http://ghc.haskell.org/trac/ghc/ticket/5997#comment:2
http://ghc.haskell.org/trac/ghc/ticket/5997#comment:2
<p>
commit <a class="changeset" href="http://ghc.haskell.org/trac/ghc/changeset/b8ff4448d899f783fc112f3774aab626979a4f22/ghc" title="Fix worker/wrapper for CPR functions
A long-standing and egregious bug in ...">b8ff4448d899f783fc112f3774aab626979a4f22</a>
</p>
<pre class="wiki">Author: Simon Peyton Jones <simonpj@microsoft.com>
Date: Fri Apr 13 17:38:32 2012 +0100
Fix worker/wrapper for CPR functions
A long-standing and egregious bug in the worker/wrapper code meant
that some functions with the CPR property weren't getting a CPR
w/w. And that had the effect of making a tail-recursive function not
tail recursive. As well as increasing allocation.
Fixes Trac #5920, and #5997.
Nofib results (highlights):
Program Size Allocs Runtime Elapsed TotalMem
--------------------------------------------------------------------------------
boyer2 -0.1% -15.3% 0.01 0.01 +0.0%
mandel2 -0.0% -8.1% 0.01 0.01 +0.0%
para -0.1% -11.8% -7.9% -7.8% +0.0%
--------------------------------------------------------------------------------
Min -0.1% -15.3% -7.9% -7.8% -33.3%
Max +0.0% +0.2% +6.3% +6.3% +3.7%
Geometric Mean -0.0% -0.4% +0.1% +0.1% -0.5%
Looks like a clear win. And I have not even recompiled the libraries, so
it'll probably be a bit better in the ed.
compiler/stranal/DmdAnal.lhs | 13 ++++++-------
compiler/stranal/WwLib.lhs | 25 ++++++++++++++++---------
2 files changed, 22 insertions(+), 16 deletions(-)
</pre>
TicketsimonpjTue, 24 Apr 2012 08:47:51 GMTtestcase set
http://ghc.haskell.org/trac/ghc/ticket/5997#comment:3
http://ghc.haskell.org/trac/ghc/ticket/5997#comment:3
<ul>
<li><strong>testcase</strong>
set to <em>simplCore/should_run/T5997</em>
</li>
</ul>
Ticket