Opened 3 years ago

Last modified 8 months 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: deSugar/should_compile/T13208
Blocked By: Blocking:
Related Tickets: Differential Rev(s): https://gitlab.haskell.org/ghc/ghc/merge_requests/394
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 (9)

comment:1 Changed 3 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 9 months 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 9 months ago by bjmprice

Cc: bjmprice added

comment:4 Changed 9 months ago by RyanGlScott

Differential Rev(s): https://gitlab.haskell.org/ghc/ghc/merge_requests/394
Test Case: deSugar/should_compile/T13208

simonpj, what is the status of this ticket post-5eeefe4c1e007ea2098f241634b48a4dada785a5?

comment:5 Changed 9 months ago by simonpj

Resolution: fixed
Status: newclosed

It's fixed! Thanks for reporting the infelicity in comment:2, @bjmprice. The commit mentioned in comment:4 fixes your problem.

Simon

comment:6 Changed 9 months ago by monoidal

I agree that comment:2 was addressed, but what about comment:1? It seems to me that this was not addressed and was the original reason for leaving the ticket open.

comment:7 Changed 8 months ago by Marge Bot <ben+marge-bot@…>

In 5eeefe4c/ghc:

Improve the very simple optimiser slightly

There was a missing case in the very simple optimiser,
CoreOpt.simpleOptExpr, which led to Trac #13208 comment:2.

In particular, in simple_app, if we find a Let, we should
just float it outwards. Otherwise we leave behind some
easy-to-reduce beta-redexes.

comment:8 Changed 8 months ago by simonpj

I agree that comment:2 was addressed, but what about comment:1? It seems to me that this was not addressed and was the original reason for leaving the ticket open.

Yes, you are right.

  • I'd like to get rid of Note [Beta redexes] in Core Lint.
  • The change to simpleOptPgm makes that more feasible.
  • But we do worker/wrapper join points, and currently w/w generates exactly these kind of beta redexes (contrary, I think, to the claim that it was only simpleOptPgm)

I'm not sure it matters all that much, but yes we should leave the ticket open

comment:9 Changed 8 months ago by monoidal

Resolution: fixed
Status: closednew
Note: See TracTickets for help on using tickets.