Opened 3 years ago

Last modified 2 years ago

#13236 new bug

Improve floating for join points

Reported by: simonpj Owned by:
Priority: normal Milestone:
Component: Compiler Version: 8.0.1
Keywords: JoinPoints Cc: lukemaurer
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

Having looked at the code in SetLevels, am very uncomfortable. My nose tells me that there is far too much chuffing about; it all makes my head spin.

Question 1. Why do we ever "ruin" a join point? See

Note [When to ruin a join point]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Generally, we protect join points zealously. However, there are two situations
in which it can pay to promote a join point to a function:

1. If the join point has no value arguments, then floating it outward will make
   it a *thunk*, not a function, so we might get increased sharing.
2. If we float the join point all the way to the top level, it still won't be
   allocated, so the cost is much less.

Refusing to lose a join point in either of these cases can be disastrous---for
instance, allocation in imaginary/x2n1 *triples* because $w$s^ becomes too big
to inline, which prevents Float In from making a particular binding strictly
demanded.

But I don't agree at all. If we have

let-join j = e in b

then we can leave j in place as a join point. We can float e (via lvlMFE) if doing so would increase sharing. Indeed this applies uniformly to all join points. For example

f x = let g y = let-join j z1 z2 = expensive x
                in case y of
                   A p q -> j p q
                   B r   -> j r r
                   C     -> True

Here it would make sense to float (expensive x) out of the \y abstrction:

f x = let lvl = expensive x
          g y = let-join j z1 z2 = lvl
                in case y of
                   A p q -> j p q
                   B r   -> j r r
                   C     -> True

But doing so does not affect the join point j. Nullary join points are no different.

This includes floating to the top level. Incidentally the RHS of the join point then becomes tiny, so the join point will be inlined.

In short, I think we can just delete all this special code.

Question 2: Note [Join points and MFEs]. Whe do we ever float out a MFE that has a free join variable? SLPJ claim: if there is a free join variable, do not float it anywhere.

Question 3: Do we actually need to float join points at all? Why?

I thik the reason is just to make them small

let-join j1 x = let-join j2 y = y+1
                in ...

Here perhaps if we float j2 out of j1 that might make j1 small enough to inline. But if that is the only motivation (unlike most of FloatOut which is about saving work) we'd better say so loud and clear. And the question is a bit more complicated; e.g. we might want to abstract over Ids to achieve this. e.g.

let-join j1 x = let-join j2 y = x+y
                in ...
===>
let-join j2' x y = x+y
         j1 x = let-join j2 y = j2' x y
                in ...

Now we can inline j2. (The example would be more realistic if the x+y was a big expression.) It's not just join parameters; we can abstract over any free variables:

let-join j1 x = let p = x+y in
                let-join j2 z = p+z
                in ....

Here we could abstract j2 over p in order to float it.

It is not clear how best to do this; but I worry that we are asking FloatOut to do too much.

Change History (6)

comment:1 Changed 3 years ago by simonpj

Cc: lukemaurer added

comment:2 Changed 3 years ago by lukemaurer

Question 1. For nullary join points, yes, this would definitely be a better way to “ruin” them. It would just be a matter of calling lvlMFE instead of lvlExpr in lvlFloatRhs when looking at the RHS of a join point.

For going to top level, we could do something similar to perform the operation (have the join point delegate to a function), but to make the decision we still need special logic saying the function must be going either to top level or not above the join ceiling. Otherwise we can end up with:

f a b =
  joinrec j1 x y =
    join j2 z = ... a ... b ... {- no x or y -}
    in ...
  in ...

becoming:

f a b =
  let h z = ... a ... b ...
  joinrec j1 x y =
    join j2 z = h z
    in ...
  in ...

at which point j2 goes away and is effectively “ruined” just as if we weren't careful with join points at all.

Question 2. It happens, for instance in circsim, where a case branch that's a jump gets MFE'd. There's no more or less reason to float an MFE as a join point than to float an join point at all, AFAIK.

Question 3. There's a Note [Join points] in FloatOut (maybe should be SetLevels instead?) with an example. Note that the simplifier wouldn't be able to do the floating to flatten the nested cases, since it would need to know the free variables of j2 and j3 to float them.

comment:3 Changed 3 years ago by simonpj

Question 2: I'm not saying that we never have a candidate MFE that has a join point as a free var.

I AM saying that in that situation we should not float the MFE. How could it possibly be beneficial? Floating is mainly to get things outside a value lambda -- but that's invalid there's a free join point. Or to top level; ditto. Case closed.

Can you give an example where let-binding an MFE (as a join point of course) with a free variable is beneficial?

comment:4 Changed 3 years ago by simonpj

Question 3. Here's a concrete example

f b x
   = let j1 :: Integer -> Integer
         j1 y = let j2 z = if b && z>0 then z+z+z+z+z else j2 (z-1)
                in j2 y
     in
     if b then j1 x else j1 (x-1)

Currently j2 does not float out of j1. I agree that it should.

comment:5 Changed 2 years ago by lukemaurer

Yes, that's similar to the example in FloatOut with nested loops---which came directly from list-fusion code (filter of filter of filter). Floating to make things trivial (as the Simplifier does) is less important than floating to share computation, but it can be significant. (And the Simplifier can't do the floating in this case because it doesn't realize that j2 doesn't refer to y.)

comment:6 Changed 2 years ago by David Feuer <David.Feuer@…>

In 6eb52cfc/ghc:

Improve SetLevels for join points

C.f. Trac #13286, #13236

* Never destroy a join point unless it goes to top level
  See Note [Floating join point bindings]

* Never float a MFE if it has a free join variable
  Note [Free join points]

* Stop treating nullary join points specially

* Enforce the invariant that le_join_ceil >= le_ctxt_lvl
  (Needs more thought...)

Reviewers: austin, bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D3199
Note: See TracTickets for help on using tickets.