[GHC] #12425: With -O1 and above causes ghc to use all available memory before being killed by OOM killer

[GHC]

#12425: With -O1 and above causes ghc to use all available memory before being
killed by OOM killer
-------------------------------------+-------------------------------------
        Reporter:  erikd             |                Owner:
            Type:  bug               |               Status:  new
        Priority:  high              |            Milestone:  8.0.3
       Component:  Compiler          |              Version:  8.0.1
      Resolution:                    |             Keywords:  Inlining
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Thomie, THANK YOU for the small repro case in comment:3.  With its help I
 rapidly nailed the bug.   Here's what is happening.

 Suppose we have
 {{{
 let rec { f = ...g...g...
         ; g = ...f...f... }
 in
 case x of
   True  -> ...f..
   False -> ..f...
 }}}
 In each iteration of the simplifier the occurrence analyser `OccAnal`
 chooses a loop breaker.  Suppose in iteration 1 it choose `g` as the loop
 breaker.  That means it is free to inline `f`.

 Suppose that GHC decides to inline `f` in the branches of the `case`, but
 (for some reason; eg it is not satureated) in the rhs of `g`. So we get
 {{{
 let rec { f = ...g...g...
         ; g = ...f...f... }
 in
 case x of
   True  -> ...g...g.....
   False -> ..g..g....
 }}}
 Now suppose that, for some reason, in the next iteraion the occurrence
 analyser chooses `f` as the loop breaker, so it can freely inling `g`.
 And again for some reason the simplifer inlines `g` at its calls in the
 `case` branches, but not in the RHS of `f`. Then we get
 {{{
 let rec { f = ...g...g...
         ; g = ...f...f... }
 in
 case x of
   True  -> ...(...f...f...)...(...f..f..).....
   False -> ..(...f...f...)...(..f..f...)....
 }}}
 You can see where this is going! Each iteration of the simplifier doubles
 the number of calls to `f` or `g`.  No wonder GHC is slow!

 (In the particular example in comment:3, `f` and `g` are the two mutually
 recursive `fmap` instances for `CondT` and `Result`.  They are both marked
 INLINE which, oddly, is why they don't inline in each other's RHS, because
 the call there is not saturated.)

 The root cause is that we flip-flop on our choice of loop breaker. I
 always thought it didn't matter, and indeed for any single iteration to
 terminate, it doesn't matter.  But when we iterate, it matters a lot!!

 I think this was not happening before because, by a fluke, we tended to
 always choose the same one.  But, perhaps as a resul of Bartosz's work on
 making GHC deterministic, the occurrence analyser now reliably flip-flops
 in each iteration, as above.

 Trac #12234 turns out to be ''exactly'' the same issue

 -------------------

 What to do?  We want the occurrence analyser to choose a loop breaker
 based on stable criteria, not arbitrary things.  Simple idea: if two or
 more potential loop breakers look equally plausible, ''choose the one that
 was a loop breaker in the previous iteration''.  That should make it
 stable.

 Stay tuned.  But I thought I'd explain what is happening in case I get
 distracted.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/12425#comment:12>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler