[GHC] #12368: Demand Analyzer: Cunnig plan not adhered to with aborting fixpoint interation

6 Jul 2016

      #12368: Demand Analyzer: Cunnig plan not adhered to with aborting fixpoint
interation
-------------------------------------+-------------------------------------
           Reporter:  nomeata        |             Owner:
               Type:  bug            |            Status:  new
           Priority:  low            |         Milestone:
          Component:  Compiler       |           Version:  8.0.1
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 Not sure how relevant this is, but when reading both paper and code long
 enough, on inevitably finds some code smell.

 This is about nested recursion, as in this example
 {{{
   f [] = []
   f (x:xs) = let g []     = f xs
                  g (y:ys) = y+1 : g ys
               in g (h x)
 }}}
 The “cunning plan” of fixpoint iteration (see Note [Initialising
 strictness]) says that in the first time an inner recursive definition is
 looked at, its strictness is assumed to be `b` (`botSig`), and from then
 on, its `idInformation` (presumably from the previous iteration or the
 outer recursive definition) is used. A flag (`virgin`) in the analysis
 environment is used to detect that.

 The problem is that the fixpoint iteration code in `dmdFix` aborts after
 more than 10 iterations:
 {{{
     loop' n env pairs
       | found_fixpoint
       = (env', lazy_fv, pairs')
       | n >= 10
       = (env, lazy_fv, orig_pairs)      -- Safe output
 }}}
 This means that if the iteration does not terminate, we will “not” attach
 a strictness signature to the inner binders (`g` in the example above),
 but rather leave the binders untouched.

 Then, in the second iteration of finding a fixpoint for `f`, the `virgin`
 flag is `False`, and `idStrictness` is used, which in this case will
 simply be the default, namely `nopSig`.

 I could not produce an example where it matters. And it might be that it
 simply does not matter, so I’m not sure what to do with this information.

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12368
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler