GHC stuck in infinite loop compiling with optimizations

[ronwalf]

GHC gets stuck compiling the attached program. Removing 'deriving Eq' from the last line restores GHC's ability to terminate.

Is this the same as the  inliner loop bug? Who knows.

[ronwalf]

Causes GHC crash with: $ ghc --make -O -c ghcloop.hs

[simonpj]

Actually, yes, it is an example of the classic inliner-looping bug. Here's a very slightly simpler version (no need for deriving Eq):

module GHCLoop where

newtype Expr f = In (f (Expr f))

class FuncEq f where
    funcEq :: FuncEq g => f (Expr g) -> f (Expr g) -> Bool

instance (FuncEq f) => Eq (Expr f) where
    (In x) == (In y) = funcEq x y

data Not e = Not e

instance FuncEq Not where
    funcEq (Not x) (Not y) = x == y	-- x,y :: Expr g
    	   	   	       	  	-- Needs Eq (Expr g)
					--   = $c== (funcEq g)

foo :: Expr Not -> Bool
foo x = x == x

The classic bug shows up when you have a type declared with a contravariant occurrence of itself. Something like:

data T = MkT (T -> Int)

get (MkT f) = f
foo t = get t t    -- Loops

And that is what we get here: the dictionary for FunEq looks like this:

data FunEq f = MkD (forall g. FuncEq g -> f (Expr g) -> f (Expr g) -> Bool)

When f and g both get instantiated to the same type, we are in the contravariant situation, and that's exactly what happens here. Here are my notes on what happens (mainly for me):

Rule fired: Class op funcEq
Inlining done: $cfuncEq{v akX} [lid]
Inlining done: $c=={v alm} [lid]


$cfuncEq $dfuncEq = ...$c== $dfuncEq...
$c== $dfuncEq = ...funcEq $dfuncEq $dfuncEq...

$funcEqNot = MkD $cfuncEq

$sc== = ...funcEq $funcEqNot $funcEqNot...


funcEq $funcEqNot $funcEqNot
--> $cfuncEq $funcEqnot
--> $c== $funcEqNot 
--> funcEq $funcEqNot $funcEqNot

So this is the first time I've seen a real example of the bug. You can probably work around it with a judicious NOINLINE pragma. But really we need something better.

Your example is a more convincing version of #5400.

See also #3400, #3872.

[simonpj]

Sorry, the #3400 link was bogus.

[simonmar]

So I presume we want to close this bug then?

[simonpj]

Ron writes: There are now three more examples, at least two of which weren't 'contrived':

• #5448
• #5400
• #3872

It took me about 4-6 hours to track down this bug in my own code (#5448) since it required repeatedly bisecting a larger program until I had a small testcase. In the test program, I can get around it with {-# NOINLINE funcEq #-}. In the program it came from, though, FuncEq is an imported value, so I have to either compile with -O0, or change put the pragma in the imported library, where it will effect a fair amount of code that doesn't hit this bug.

If adding the check is too expensive, can the inliner have a configurable recursion count (ala -fcontext-stack)?

Simon responds: it's not that it's too expensive, more that I don't know a way to prevent divergence that isn't so conservative that it hobbles regular optimisation. Actually our new paper (Haskell Symposium 2011) "Termination combinators forever" may show the way -- but that will be expensive.

A count sounds like a reasonable idea; it would at least stop the compiler falling into an infinite loop.

[simonpj@…]

commit 24a2353a77111e9f236325521edd233f35954328

Author: Simon Peyton Jones <simonpj@microsoft.com>
Date:   Fri Sep 23 06:46:30 2011 +0100

    Add a transformation limit to the simplifier (Trac #5448)
    
    This addresses the rare cases where the simplifier diverges
    (see the above ticket).  We were already counting how many simplifier
    steps were taking place, but with no limit.  This patch adds a limit;
    at which point we halt compilation, and print out useful stats. The
    stats show what is begin inlined, and how often, which points you
    directly to the problem.  The limit is set based on the size of the
    program.
    
    Instead of halting compilation, we could instead just inhibit
    inlining, which would let compilation of the module complete. This is
    a bit harder to implement, and it's likely to mean that you unrolled
    the function 1143 times and then ran out of ticks; you probably don't
    want to complete parsing on this highly-unrolled program.
    
    Flags: -dsimpl-tick-factor=N.  Default is 100 (percent).
           A bigger number increases the allowed maximum tick count.

 compiler/main/DynFlags.hs         |    3 +
 compiler/simplCore/CoreMonad.lhs  |   44 +++--
 compiler/simplCore/SimplCore.lhs  |   10 +-
 compiler/simplCore/SimplMonad.lhs |  341 ++++++++++++++++++++-----------------
 compiler/simplCore/Simplify.lhs   |    4 +-
 5 files changed, 223 insertions(+), 179 deletions(-)

[simonpj]

I've also added documentation

commit b347eff0cd771ab9e1f3a80c6c91615255e4fe41
Author: Simon Peyton Jones <simonpj@microsoft.com>
Date:   Thu Sep 29 09:42:53 2011 +0100

    Document -fsimpl-tick-count

 docs/users_guide/flags.xml |  166 +++++++++++++++++++++++---------------------
 docs/users_guide/using.xml |   92 +++++++++++++++---------
 2 files changed, 144 insertions(+), 114 deletions(-)

I'll leave the ticket open to keep track of the main issue (that the compiler can loop), but with milestone of bottom.

Simon

[simonpj]

Here is another, even simpler, example of a class with a contra-variant occurence of itself: #5722.