[GHC] #13253: Exponential compilation time with RWST & ReaderT stack with `-02`

[GHC]

#13253: Exponential compilation time with RWST & ReaderT stack with `-02`
-------------------------------------+-------------------------------------
        Reporter:  phadej            |                Owner:  dfeuer
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:  8.4.1
       Component:  Compiler          |              Version:  8.0.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by mpickering):

 Looking at the n=2 case for simplicity.

 At one stage of the compilation we have some core which looks like

 {{{
 ($c<*>_a4dL
                (case x01_a2dZ of {
                   FormMissing -> FormMissing;
                   FormFailure errs_a2dS -> FormFailure errs_a2dS;
                   FormSuccess a_a2dU ->
                     FormSuccess
                       (\ dt_a2M6 ->
                          case a_a2dU of dt_X2M8 { PS ipv_s5JI ipv_s5JJ
 ipv_s5JK ipv_s5JL ->
                          case dt_a2M6 of dt_X2Ma { PS ipv_s5JO ipv_s5JP
 ipv_s5JQ ipv_s5JR ->
                          HugeStruct dt_X2M8 dt_X2Ma
                          }
                          })
                 })
                x02_a2e0
 }}}

 Next thing we know, the expression has been commuted and the call to $c<*>
 has been pushed into the branches !?

 {{{

  (case x01_a2dZ of {
                FormMissing -> $c<*>_a4dL FormMissing x02_a2e0;
                FormFailure errs_a2dS ->
                  $c<*>_a4dL (FormFailure errs_a2dS) x02_a2e0;
                FormSuccess a_a2dU ->
                  $c<*>_a4dL
                    (FormSuccess
                       (\ dt_a2M6 ->
                          case a_a2dU of dt_X2M8 { PS ipv_s5JI ipv_s5JJ
 ipv_s5JK ipv_s5JL ->
                          case dt_a2M6 of dt_X2Ma { PS ipv_s5JO ipv_s5JP
 ipv_s5JQ ipv_s5JR ->
                          HugeStruct a_a2dU dt_a2M6
                          }
                          }))
                    x02_a2e0
 }}}

 and then `$c<*>_a4dL` is inlined individually in each branch rather than
 once at the top level.

 I don't know where in the compiler performs this transformation, perhaps
 you know where it happens David?

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