Opened 2 years ago

Last modified 10 days ago

#13208 new bug

Do two-phase inlining in simpleOptPgm

Reported by: lukemaurer Owned by:
Priority: normal Milestone:
Component: Compiler Version: 8.1
Keywords: JoinPoints Cc: bjmprice
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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.

Change History (3)

comment:1 Changed 2 years ago by simonpj

Keywords: JoinPoints added

Done!

commit 8e9593fb2147252ecb8b685ef6bf9c0237a71219
Author: Simon Peyton Jones <simonpj@microsoft.com>
Date:   Tue Feb 7 00:32:43 2017 +0000

    Improve the simple optimiser
    
    The previous version of the simple optimiser would leave
    beta-redexes, which was bad for join points.  E.g.
    
      join j x = ....   -- a join point
      in (\x. j x) y
    
    This would be ok if we beta-reduced the (\x) but not if
    we don't.
    
    This patch improves the simple optimiser, to follow the plan
    described in "Secrets of the GHC inliner", and implemented in
    the Mighty Simplifier.  It turns out not to be too hard to
    use the same plan here, and we get slightly better code as
    a result.

Luke, you say:

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.

but don't we sometimes generate some beta-redexes in worker/wrapper after strictness analysis? I have not yet changed this.

Adding keyword JoinPoints so we don't lose track of this. It'd be cool to finish it off. Ideally getting rid of type-lets too.

comment:2 Changed 10 days ago by bjmprice

What's the status of this ticket? I ask because in Note [The simple optimiser], it is claimed that "It thereby guarantees to leave no un-reduced beta-redexes.", but in 8.6.3 the Haskell beta = let f = \x -> x in f True gives rise to the Core beta = (\ (x_aVG :: Bool) -> x_aVG) GHC.Types.True, which seems to contradict that claim.

(This core is with -ddump-ds, which I think runs the simple optimiser. With -ddump-ds-preopt it is a let-binding, not a beta-redex.)

I guess that the Note could mean that "all beta-redexes in the input are reduced", rather than "there are no beta-redexes in the output", but this isn't how I understood the text.

comment:3 Changed 10 days ago by bjmprice

Cc: bjmprice added
Note: See TracTickets for help on using tickets.