[GHC] #15164: Slowdown in ghc compile times from GHC 8.0.2 to GHC 8.2.1 when doing Called arity analysis

[GHC]

#15164: Slowdown in ghc compile times from GHC 8.0.2 to GHC 8.2.1 when doing Called
arity analysis
-------------------------------------+-------------------------------------
        Reporter:  flip101           |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  highest           |            Milestone:  8.6.1
       Component:  Compiler          |              Version:  8.2.1
      Resolution:                    |             Keywords:
Operating System:  Linux             |         Architecture:  x86_64
 Type of failure:  Compile-time      |  (amd64)
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by nomeata):

 If I focus on this part of the code:
 {{{
 newtype ActualParameterPart = APP (NT AssociationList)
 instance Rule f AssociationList => Rule f ActualParameterPart where
   get = APP <$> n93
 }}}
 then with 8.0 I get this code for the instance method:
 {{{
 -- RHS size: {terms: 12, types: 18, coercions: 0}
 $cget_a1BB
   :: forall (f_a1By :: * -> *).
      (Rule f_a1By AssociationList, Decorator f_a1By) =>
      f_a1By ActualParameterPart
 [LclId, Str=DmdType]
 $cget_a1BB =
   \ (@ (f_a1By :: * -> *))
     ($dRule_a1Bz :: Rule f_a1By AssociationList)
     ($dDecorator_a1BD :: Decorator f_a1By) ->
     <$>
       @ f_a1By
       @ (NT AssociationList)
       @ ActualParameterPart
       (GHC.Base.$p1Applicative
          @ f_a1By
          (GHC.Base.$p1Monad
             @ f_a1By (Level4.$p1Decorator @ f_a1By $dDecorator_a1BD)))
       Level4.APP
       (n93 @ f_a1By $dDecorator_a1BD @ AssociationList $dRule_a1Bz)
 }}}
 but with 8.4 I get
 {{{
 -- RHS size: {terms: 2,474,
               types: 2,544,
               coercions: 0,
               joins: 0/630}
 $cget_a2E1 [Occ=LoopBreaker]
   :: forall (f :: * -> *).
      (Rule f AssociationList, Decorator f) =>
      f ActualParameterPart
 [LclId]
 $cget_a2E1
   = \ (@ (f_a2DY :: * -> *))
       _ [Occ=Dead]
       ($dDecorator_a2E4 :: Decorator f_a2DY) ->
       letrec {
         $dRule_a7WP :: Rule f_a2DY QualifiedExpression
         [LclId]
         $dRule_a7WP
           = Level4.$fRulefQualifiedExpression
               @ f_a2DY $dRule_a7Qw $dRule_a7Wx;
         $dRule_a7VU :: Rule f_a2DY FunctionCall
         [LclId]
         $dRule_a7VU = Level4.$fRulefFunctionCall @ f_a2DY $dRule_a7VQ;
 … thousands of lines omitted …
         $dRule_a7Qv [Occ=LoopBreaker] :: Rule f_a2DY Name
         [LclId]
         $dRule_a7Qv
           = Level4.$fRulefName
               @ f_a2DY $dRule_a7Ux $dRule_a7Uy $dRule_a7Uz; } in
       letrec {
         $dRule_a7Th :: Rule f_a2DY FunctionCall
         [LclId]
         $dRule_a7Th = Level4.$fRulefFunctionCall @ f_a2DY $dRule_a7Qy;
 … again thousands of lines omitted …
         $dRule_a7Qy [Occ=LoopBreaker] :: Rule f_a2DY Name
         [LclId]
         $dRule_a7Qy
           = Level4.$fRulefName
               @ f_a2DY $dRule_a7Te $dRule_a7Tf $dRule_a7Tg; } in
       letrec {
         $dRule_a7QO :: Rule f_a2DY TypeMark
         [LclId]
         $dRule_a7QO = Level4.$fRulefTypeMark @ f_a2DY $dRule_a7QB;
 … again …
         $dRule_a7Qx [Occ=LoopBreaker] :: Rule f_a2DY Expression
         [LclId]
         $dRule_a7Qx = Level4.$fRulefExpression @ f_a2DY $dRule_a7Qz; } in
       letrec {
         $dRule_a7Qo :: Rule f_a2DY QualifiedExpression
         [LclId]
         $dRule_a7Qo
           = Level4.$fRulefQualifiedExpression
               @ f_a2DY $dRule_a7ML $dRule_a7Q6;
 …
 … and a few more of those …
         $dRule_a7MM
           = Level4.$fRulefName
               @ f_a2DY $dRule_a7MN $dRule_a7MO $dRule_a7MP; } in
       <$>
         @ f_a2DY
         @ (NT AssociationList)
         @ ActualParameterPart
         (GHC.Base.$p1Applicative
            @ f_a2DY
            (GHC.Base.$p1Monad
               @ f_a2DY (Level4.$p1Decorator @ f_a2DY $dDecorator_a2E4)))
         Level4.APP
         (n93
            @ f_a2DY
            $dDecorator_a2E4
            @ AssociationList
            (Level4.$fRulefAssociationList
               @ f_a2DY
               (Level4.$fRulefAssociationElement
                  @ f_a2DY
                  (Level4.$fRulefFormalPart
                     @ f_a2DY
                     (Level4.$fRulefFormalDesignator @ f_a2DY $dRule_a7MM)
                     $dRule_a7MK
                     $dRule_a7ML)
                  (Level4.$fRulefActualPart
                     @ f_a2DY
                     (Level4.$fRulefActualDesignator @ f_a2DY $dRule_a7Qx
 $dRule_a7Qy)
                     $dRule_a7Qv
                     $dRule_a7Qw))))
 }}}

 The important change seems to be:
 * Previously, the code for `get` would use the dictionary for `Rule f_a1By
 AssociationList` passed to it, here named `$dRule_a1Bz`.
 * Now, it ''ignores'' the dictionary passed to it (note `_ [Occ=Dead]`)
 and instead seems to build the dictionary it passes to `n93` locally,
 using many very large local let-recs.

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/15164#comment:14>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler