Panic Simplifier ticks exhausted with type families

I've tried to compile my vinyl-like records with 7.10.2-rc1 and got:

ghc: panic! (the 'impossible' happened)
  (GHC version 7.10.1.20150612 for x86_64-unknown-linux):
        Simplifier ticks exhausted
  When trying RuleFired Class op rreplace
  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: 225484

Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug

Attached self contained test compiles with 7.10.1, but fails with 7.10.2-rc1 when compiled with optimizations.

Trac metadata

Trac field	Value
Version	7.10.1-rc1
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

mentioned in issue #4945

mentioned in issue #5113 (closed)

changed weight to 5

added Tbug Trac import labels

Attached file Bug.hs ($1099).

testcase

changed milestone to %7.10.2

changed weight to 7

Confirmed regression from 7.10.1.

$ /opt/ghc/7.10.1/bin/ghc -O -fforce-recomp Bug.hs -fsimpl-tick-factor=50 
[1 of 1] Compiling Bug              ( Bug.hs, Bug.o )

$ /opt/ghc/7.10.2/bin/ghc -O -fforce-recomp Bug.hs -fsimpl-tick-factor=5000 
[1 of 1] Compiling Bug              ( Bug.hs, Bug.o )
ghc: panic! (the 'impossible' happened)
  (GHC version 7.10.1.20150609 for x86_64-unknown-linux):
	Simplifier ticks exhausted
  When trying UnfoldingDone $fFunctorConst_$cfmap
  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: 11274000

Trac metadata

Trac field	Value
Priority	normal → high

The default simpl-tick-factor is 100, so reducing it to 50 will not help. Does increasing it help? How much?

Simon

Neither increasing simpl-tick-factor to 5000 nor decreasing it to 10 helps.

changed weight to 10

Promoting as a regression over 7.10.1

Trac metadata

Trac field	Value
Priority	high → highest

assigned to @bgamari

mentioned in issue #10565 (closed)

I am still churning through this one but I think I finally have some traction. In 7.10.2 each field added to the records roughly doubles the simpl-tick-factor necessary to finish.

I am now comparing the sequences of inlinings performed by GHC 7.10.1 and 7.10.2. For those following along at home, it is enlightening (albeit verbose) to compile like this,

ghc -fforce-recomp -O -dverbose-core2core -ddump-simpl -ddump-to-file -dshow-passes -ddump-simpl-stats -ddump-inlinings Bug.hs -fsimpl-tick-factor=100 >|ghc.log 2>&1

Out pops a few hundred megabytes of text, but you now you have what you need.

You can then easily compare two of these dumps with,

paste <(grep -n "Inlining done" 7.10.1/ghc.log) <(grep -n "Inlining done" 7.10.2/ghc.log) | column -s $'\t' -t | less

One notices certain patterns in this output. In particular, one finds inlinings of Data.Functor.Identity.$fFoldableIdentity2 are performed far more often in 7.10.1 than 7.10.2. It is worth noting that whenever 7.10.2 considers inlining this definition it does so.

More analysis later.

Very early in the simplifier run I noticed this difference.

In 7.10.1,

Inlining done: Data.Functor.Identity.$fFoldableIdentity2
    Inlined fn:  \ (@ a4)
                   (ds [Occ=Once] :: Data.Functor.Identity.Identity a4) ->
                   ds
    Cont:   ApplyToTy (Bug.Rec ss)
            ApplyToVal nodup ((g x)
                              `cast` (Sym
                                        (Nth:0
                                           (<Data.Functor.Identity.Identity (Bug.Rec ss)>_R
                                            -> Data.Functor.Identity.NTCo:Identity[0]
                                                 <Bug.Rec ss>_R))
                                      :: Data.Functor.Identity.Identity (Bug.Rec ss)
                                         ~R# Data.Functor.Identity.Identity (Bug.Rec ss)))
            CastIt Nth:1
                     (<Data.Functor.Identity.Identity (Bug.Rec ss)>_R
                      -> Data.Functor.Identity.NTCo:Identity[0] <Bug.Rec ss>_R)
            Stop[BoringCtxt] Bug.Rec ss

In 7.10.2,

Inlining done: Data.Functor.Identity.$fFoldableIdentity2
    Inlined fn:  \ (@ a4)
                   (ds [Occ=Once] :: Data.Functor.Identity.Identity a4) ->
                   ds
    Cont:   ApplyToTy (Bug.Rec ss)
            ApplyToVal simpl ((g x)
                              `cast` (Sym
                                        (Nth:0
                                           (<Data.Functor.Identity.Identity (Bug.Rec ss)>_R
                                            -> Data.Functor.Identity.NTCo:Identity[0]
                                                 <Bug.Rec ss>_R))
                                      :: Data.Functor.Identity.Identity (Bug.Rec ss)
                                         ~R# Data.Functor.Identity.Identity (Bug.Rec ss)))
            CastIt Nth:1
                     (<Data.Functor.Identity.Identity (Bug.Rec ss)>_R
                      -> Data.Functor.Identity.NTCo:Identity[0] <Bug.Rec ss>_R)
            Stop[BoringCtxt] Bug.Rec ss

Notice the second "frame" of the context: ApplyToVal nodup ((g x) ...) (7.10.1) in contrast to ApplyToVal simpl ((g x) ...) (7.10.2). I'm not yet sure whether this is significant.

I have also noticed that GHC 7.10.1 often appears to by simplifying inside of a cast when 7.10.2 is just working inside of Const. For instance, it is common to see the SimplCont of 7.10.1 terminates with,

CastIt Nth:1
         (((forall a6 b.
            <Control.Applicative.Const a6 b>_R
            -> Control.Applicative.NTCo:Const[0] <a6>_R <b>_P)@"field1"
                                                               Bug.:-> Bug.Expr
                                                                         GHC.Types.Int)@Bug.Rec
                                                                                          '["field1"
                                                                                            Bug.:-> Bug.Expr
                                                                                                      GHC.Types.Int,
                                                                                            "field2"
                                                                                            Bug.:-> Bug.Expr
                                                                                                      GHC.Types.Int,
                                                                                            "id"
                                                                                            Bug.:-> Bug.Expr
                                                                                                      GHC.Types.Int,
                                                                                            "event_type"
                                                                                            Bug.:-> Bug.Expr
                                                                                                      GHC.Types.Int])
Stop[BoringCtxt] "field1" Bug.:-> Bug.Expr GHC.Types.Int

whereas 7.10.2 will end in,

Stop[BoringCtxt] Control.Applicative.Const
                   ("field1" Bug.:-> Bug.Expr GHC.Types.Int)
                   (Bug.Rec
                      '["field1" Bug.:-> Bug.Expr GHC.Types.Int,
                        "field2" Bug.:-> Bug.Expr GHC.Types.Int,
                        "id" Bug.:-> Bug.Expr GHC.Types.Int,
                        "event_type" Bug.:-> Bug.Expr GHC.Types.Int])

with the inner context being essentially identical.

Here I compare what the simplifier does to a term of type "event_type" :-> Int from my test program in GHC 7.10.1 and 7.10.2.

The test program (found here https://github.com/bgamari/ghc-T10527/blob/master/Bug2.hs) is cut down just enough so that it fails with 7.10.2 and succeeds with 7.10.1 with a sufficiently low simpl-tick-factor (10).

One obvious qualitative difference between the two simplifier trajectories is that the 7.10.2 emits its last SimplBind trace (for $s$crsubset_s2gQ) somewhere around 13% through the log (measured in lines). In contrast, 7.10.1 emits SimplBinds every regularly throughout the log. I suppose this means that 7.10.2 is spending most of its time playing with this one top-level binding?

Well, I quickly bisected get an idea of what I should be looking for. It seems like the regression was introduced by the fix for the huge space leak in the mighty simplifier (8af219ad). If I understand correctly this patch touched code surrounding the treatment of interesting arguments. Perhaps an inadvertent change here is now resulting in more inlining than we would like. I'll have another look after I've slept on it to see if this revelation gets us any closer to a fix.