[GHC] #13208: Do two-phase inlining in simpleOptPgm

30 Jan 2017

      #13208: Do two-phase inlining in simpleOptPgm
-------------------------------------+-------------------------------------
           Reporter:  lukemaurer     |             Owner:
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.1
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 As of #12988, having `simpleOptPgm` leave β-redexes lying around is
 painful because it requires a special loophole in Core Lint to allow a
 jump inside a β-redex. We'd rather use a two-phase approach, mirroring the
 simplifier's `preInlineUnconditionally` and `postInlineUnconditionally`,
 so we can aggressively eliminate β-redexes without fear of exponential
 blowup.

 Consider:
 {{{
 joinrec j1 x = e1 in
 join j2 x y = jump j1 e2 in
 jump j2 e3 e4
 }}}

 Since `j2` is only used once, it gets inlined. But `simpleOptPgm` only
 performs inlining //after// a binding is simplified, so we end up here:
 {{{
    joinrec j1 x = e1' in
    (\x y -> jump j1 e2') e3' e4'
 }}}
 Since `e2'` was already simplified, performing the β-reduction here risks
 exponential blowup for the same reason it can happen in the simplifier
 (see the Secrets paper; `perf/compiler/T783` is a live example, increasing
 in allocs by over 80% if we re-simplify here). We //could// just
 `let`-bind `e3'` and `e4'` (carefully avoiding capturing free occurrences
 of `x` in `e4'`), but not if one them is actually a type argument. Well,
 okay, we //could// introduce a type `let`, but doing that here means the
 desugarer can now return a type `let` and we're not prepared for that.
 (Specifically, under certain circumstances, the simplifier never runs in
 between the desugarer and Float Out, and the latter breaks in the presence
 of type `let`.)

 So for the moment, we leave the β-redex there, but this needs a special
 rule just for β-redexes because normally you can't have a jump under a
 lambda (or an application, for that matter). In the long term, we'd prefer
 to take the simplifier's approach instead: If we want to inline something
 because it only occurs once (even though it may be big), we add it to the
 substitution //before// simplifying it so that we only simplify it once.
 This means the substitution has to carry lexical closures around, though,
 just like the simplifier does (see `SimplSR`'s `ContEx` disjunct), so it's
 not trivial.

 The `simpleOptPgm` β-redexes are the only reason for the special rule in
 Core Lint (see Note [Beta redexes] in `CoreLint.hs`), so once this is done
 we can be rid of that.

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

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

tags

participants (1)