GHC stuck in infinite loop compiling with optimizations
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.
Trac metadata
| Trac field | Value |
|---|---|
| Version | 7.0.3 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | Compiler |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | MacOS X |
| Architecture | x86_64 (amd64) |
Activity
mentioned in issue #3872
mentioned in issue #5400
added Tbug Trac import labels
Attached file
ghcloop.hs($622).Causes GHC crash with: $ ghc --make -O -c ghcloop.hs
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 == xThe 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 -- LoopsAnd that is what we get here: the dictionary for
FunEqlooks like this:data FunEq f = MkD (forall g. FuncEq g -> f (Expr g) -> f (Expr g) -> Bool)When
fandgboth 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 $funcEqNotSo 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 (closed), #3872.
Sorry, the #3400 (closed) link was bogus.
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,FuncEqis 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.
Trac metadata
Trac field Value Resolution ResolvedWon'tFix → Unresolved mentioned in commit 24a2353a
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
mentioned in issue #5722
Here is another, even simpler, example of a class with a contra-variant occurence of itself: #5722.
mentioned in issue #7057
mentioned in issue #7369 (closed)
mentioned in issue #8833 (closed)
Although the file
ghcloop.hsfrom the description compiles with HEAD (ghc-7.9.20141125 -O1), the testcase from ticket:5448#comment:54093 does not.Trac metadata
Trac field Value Operating system MacOS X → Unknown/Multiple Architecture x86_64 (amd64) → Unknown/Multiple mentioned in issue #11240 (closed)
mentioned in issue #11263
mentioned in issue #13011
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:SimplMonadThat'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.
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.
#5448 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.
added compiler crash label
mentioned in issue #16442
added Pnormal label
added Russell paradox label
marked this issue as related to #5400
FWIW we no longer panic but rather print the message:
(tmp) （╹◡╹）♡ ghc -O1 R.hs [1 of 1] Compiling GHCLoop ( R.hs, R.o ) [Optimisation flags changed] Simplifier ticks exhausted When trying UnfoldingDone $cfuncEq_aH9 To increase the limit, use -fsimpl-tick-factor=N (default 100). In addition try adjusting -funfolding-case-threshold=N and -funfolding-case-scaling=N for the module in question. Using threshold=1 and scaling=5 should break most inlining loops. If you need to increase the tick factor substantially, while also adjusting unfolding parameters please file a bug report and indicate the factor you needed. If GHC was unable to complete compilation even with a very large factor (a thousand or more), please consult the "Known bugs or infelicities" section in the Users Guide before filing a report. There are a few situations unlikely to occur in practical programs for which simplifier non-termination has been judged acceptable. To see detailed counts use -ddump-simpl-stats Total ticks: 11083Edited by Rodrigo Mesquita
