Opened 8 years ago

Last modified 18 months ago

#5448 new bug

GHC stuck in infinite loop compiling with optimizations

Reported by: ronwalf Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.0.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time crash Test Case:
Blocked By: Blocking:
Related Tickets: #3872 #5400 Differential Rev(s):
Wiki Page:


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.

Attachments (1)

ghcloop.hs (480 bytes) - added by ronwalf 8 years ago.
Causes GHC crash with: $ ghc --make -O -c ghcloop.hs

Download all attachments as: .zip

Change History (15)

Changed 8 years ago by ronwalf

Attachment: ghcloop.hs added

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

comment:1 Changed 8 years ago by 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.

comment:2 Changed 8 years ago by simonpj

Sorry, the #3400 link was bogus.

comment:3 Changed 8 years ago by simonmar

Resolution: wontfix
Status: newclosed

So I presume we want to close this bug then?

comment:4 Changed 8 years ago by simonpj

Resolution: wontfix
Status: closednew

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

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.

comment:5 Changed 8 years ago by simonpj@…

commit 24a2353a77111e9f236325521edd233f35954328

Author: Simon Peyton Jones <>
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
    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(-)

comment:6 Changed 8 years ago by simonpj

Milestone: _|_

I've also added documentation

commit b347eff0cd771ab9e1f3a80c6c91615255e4fe41
Author: Simon Peyton Jones <>
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.


comment:7 Changed 8 years ago by simonpj

difficulty: Unknown

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

comment:8 Changed 5 years ago by thomie

Architecture: x86_64 (amd64)Unknown/Multiple
Operating System: MacOS XUnknown/Multiple

Although the file ghcloop.hs from the description compiles with HEAD (ghc-7.9.20141125 -O1), the testcase from comment:1 does not.

Last edited 5 years ago by thomie (previous) (diff)

comment:9 Changed 18 months ago by flip101

Seems that the solution is to prevent ghc from getting stuck in a loop. Since this is a longstanding bug, i guess it's difficult to fix. Alternatively .. could there perhaps be some detection that it's stuck in a loop and a message what part of the code is causing it?

comment:10 Changed 18 months ago by sgraf

Actually, this doesn't reproduce anymore, at least not in the way described. For GHC 8.2.1, the original ghcloop.hs elicits the following panic:

ghc.exe: panic! (the 'impossible' happened)
  (GHC version 8.2.1 for x86_64-unknown-mingw32):
        Simplifier ticks exhausted
  When trying RuleFired Class op funcEq
  To increase the limit, use -fsimpl-tick-factor=N (default 100)
  If you need to do this, let GHC HQ know, and what factor you needed
  To see detailed counts use -ddump-simpl-stats
  Total ticks: 15160
  Call stack:
      CallStack (from HasCallStack):
        prettyCurrentCallStack, called at compiler\utils\Outputable.hs:1133:58 in ghc:Outputable
        callStackDoc, called at compiler\utils\Outputable.hs:1137:37 in ghc:Outputable
        pprPanic, called at compiler\simplCore\SimplMonad.hs:199:31 in ghc:SimplMonad

That's better than looping forever, although I don't know why it's a panic rather than a warning. Note that it also includes which function was the culprit. I read somewhere that the Simplifier adopted its fuel-based approach in the meantime, which may be the reason this is 'fixed'.

The contravariant example doesn't reproduce at all.

comment:11 Changed 18 months ago by sgraf

comment:12 Changed 18 months ago by flip101

sgraf do you know where i can see this bug current status? When i search on this page i don't find "fixed" apart from your comment. What would be interesting is to test all the test cases (found in related bugs) with the last version of GHC 8.4.*

I think this Panic is very helpful. It could be further improved to give some tips on how the code can be rewritten to have it compiled correctly.

comment:13 Changed 18 months ago by sgraf

This ticket isn't marked as fixed and I'm not sure if others would consider it fixed (a compiler should never reject a program because of an optimization pass). That's why I put fixed in quotes above.

comment:14 Changed 18 months ago by simonpj

comment:5 make it panic (with a helpful message) rather than looping. So that's an improvement.

Better still would be to avoid looping or running out of fuel. But I have no idea how to do that.

A modest improvement would be to produce a more civilised halt rather than a panic. But I don't think it's trivial to do so, and it's cosmetic so perhaps not that important.

Note: See TracTickets for help on using tickets.