Opened 8 years ago

Last modified 5 years ago

#5722 new bug

GHC inlines class method forever

Reported by: benmachine Owned by: simonpj
Priority: normal Milestone:
Component: Compiler Version: 7.2.1
Keywords: Cc: ireney.knapp@…, hvr@…, klao@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time crash Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

irene-knapp showed me this over IRC, I refined the test case a bit:

{-# LANGUAGE FlexibleContexts, MultiParamTypeClasses #-}
module Bug () where

class C a b where
  discord :: C a b => a b () -- Remove the constraint and it works
  rhyme :: a b ()

instance C (,) b => C (,) [b] where
  discord = discord
  rhyme = discord

GHC 7.2.2 compiling this with -O loops forever. I've worked out:

  • The C a b context in the class is completely superfluous but the bug isn't triggered without it.
  • The pattern of recursion in the two method signatures is fragile: rhyme = rhyme doesn't trigger the bug, for example.
  • Adding a NOINLINE discord stops the bug from triggering. Similarly, compiling without optimisations doesn't trigger the bug.
  • While it's looping, GHC slowly but steadily chews through all of your memory.

Change History (6)

comment:1 Changed 8 years ago by Irene

Cc: ireney.knapp@… added

comment:2 Changed 8 years ago by igloo

difficulty: Unknown
Milestone: 7.6.1
Owner: set to simonpj

comment:3 Changed 8 years ago by hvr

Cc: hvr@… added

Jfyi, GHC 7.4.0.20111219 (= RC 1) shows the same misbehaviour...

comment:4 Changed 8 years ago by simonpj

Milestone: 7.6.1_|_

Thanks. This is almost identical to #5448, but even simpler. For the record, here's an even simpler example

class C a b where
   discord :: C a b => a b () -- Remove the constraint and it works

instance C (,) b => C (,) [b] where
   discord = discord

foo :: C (,) b => (,) [b] ()
foo = discord

Here is how it plays out. We get this code (in reality the MkC stuff is a newtype, but that's irrelevant):

$cd d1 d2 = discord d2 d2
discord d = case d of MkC x -> x
$fC d = MkC ($cd d)

foo d = discord ($fC d) ($fC d)

None of these definitions are recursive. So when we simplify foo we get

discord ($fC d) ($fC d)
--> (case ($fC d) of MkC x -> x) ($fC d)
--> (case (MkC ($cd d)) of MkC x -> x) ($fC d)
--> $cd d ($fC d)
--> discord ($fC d) ($fC d)

and there is the loop.

The culprit is, as usual, the data type for the dictionary, which has itself appearing contravariantly:

data C a b = MkC (C a b => a b ())

The tick-count thing means that with 5.4 we get Simplifier ticks exhausted, and adding -ddump-simpl-stats points fairly clearly to the culprit. It's fixable by adding {-# NOINLINE discord #-} on the instance declaration.

None of this is satisfactory. The difficulty is that I do not know how to solve the problem in general -- at least not without hobbling the optimiser. I suppose that we could spot the special case of a class that mentions itself in the context of a class method, but that is a very special case.

comment:5 Changed 5 years ago by simonpj

See #9235 for another example.

comment:6 Changed 5 years ago by klao

Cc: klao@… added

One aspect in which the #9235 example is different, is that it triggers the bug even with -O0. (I'm not sure if this is important or not.)

Note: See TracTickets for help on using tickets.