Join points
ClosedPublic

Authored by lukemaurer on Dec 15 2016, 4:44 AM.

Details

Summary

This major patch implements Join Points, as described in https://ghc.haskell.org/trac/ghc/wiki/SequentCore. You have to read that page, and especially the paper it links to, to understand what's going on; but it is very cool.

It's Luke Maurer's work, but done in close collaboration with Simon PJ.

This Phab is a squash-merge of wip/join-points branch of
http://github.com/lukemaurer/ghc. There are many, many interdependent changes.

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
There are a very large number of changes, so older changes are hidden. Show Older Changes
Perhaps removing the LNE analysis from CoreToStg will help?

Luke, could we do that? Or does CoreToStg catch something that joint points do not?

I have only worked through about half of this, but it's a start

compiler/coreSyn/CoreLint.hs
1786

What does "join points that have left scope" mean. Give an example? In a Note

1843

I thought we changed this, so that the occurrence analyser doesn't make it into a real join point -- the simplifier does. So is this Note out of date? And the code it describes?

compiler/coreSyn/CorePrep.hs
443

Explain in a Note why join points need different treatment

551

As I say above, explain why join points need separete treatment, with an example.

compiler/coreSyn/CoreSubst.hs
1006

This all looks complicated and ad-hoc. Apart from anything else, it's the only call to the new (and rather complicated) mkParallelBindings.

I think instead we want

simpl_app subst (Var v) as
  | Just e <- simplVar_maybe subst v
  = simpl_app (zapSubst subst) e asa

Here zapSubsdt keeps the in-scope set but nothing else (because the range of the subst is OutExprs). Remember as are already OutExprs.

simplVar_mabye is like lookupIdSubst, but it returns a Maybe to say if it made progress. It can also do the compulsory-unfolding thing. We can use the same function in go (Var v) in simpleOptExpr.

compiler/coreSyn/CoreUnfold.hs
607

What's going on here. Explain!

compiler/simplCore/FloatIn.hs
50

Can you summarise in a Note how join points affect Float-in?

compiler/simplCore/FloatOut.hs
42

Again summarise in a Note how FloatOut is affected by join poitns.

721

What's going on here? We need that Note!

compiler/simplCore/LiberateCase.hs
237

Please give an example to explain what you mean

lukemaurer updated this revision to Diff 10554.Jan 20 2017, 4:23 AM
lukemaurer marked 5 inline comments as done.
lukemaurer edited edge metadata.
  • More patch cleanup and documentation
  • Take credit for perf/should_run/T9339 improvement
  • Revert changes to max residency benchmarks
  • Revert simplifying after Float In
  • Patch cleanup
  • Comments per Simon PJ's review
  • FloatIn: Remove silly new argument for sepBindsByDropPoint
simonpj added inline comments.Jan 20 2017, 10:37 AM
compiler/coreSyn/CoreLint.hs
1786

Aha. So give an example!

let j x = e in  f (j 2)

is not valid

simonpj added inline comments.Jan 20 2017, 10:38 AM
compiler/coreSyn/CoreLint.hs
1786

More precisely, j is "not valid" as a join point inside the argument to f

dfeuer requested changes to this revision.Jan 22 2017, 11:11 PM
dfeuer edited edge metadata.

A few more questions and comments.

compiler/basicTypes/BasicTypes.hs
852

Both of the functions below should be renamed to reflect the new constructor name.

967

Would it be possible to give AlwaysTailCalled a name reflecting what it ultimately means? It sounds like it really means that something can be made into a join point, right?

972

Is the fragile info visible from places where it's not reliable? Would it be possible to make it invisible from those places?

987

This isn't very clear to me. In what sense does j1 appear more than once per branch?

compiler/basicTypes/Id.hs
480

This can be written

isJoinId id = isId id &&
  case Var.idDetails id of
    JoinId {} -> True
    _ -> False

or as

isJoinId id
  | isId id , JoinId {} <- Var.idDetails id = True
  | otherwise = False

but why is it defined here and not in Var?

487

isJoinId_maybe should have a name indicating that it extracts arity. Why is it defined here rather than in Var?

compiler/basicTypes/IdInfo.hs
191

Do you really need this, or can you get away with just the Maybeish version?

554

This formatting is quite confusing, and surprisingly lazy-looking (not sure if it ends up actually lazy) for something that removes information. Some alternatives:

case occInfo info of
      occ | isAlwaysTailCalled occ -> Just $! (info `setOccInfo` safe_occ)
          | otherwise -> Nothing
          where
            safe_occ = occ { occ_tail = NoTailCallInfo }
zapTailCallInfo info = do
  let occ = occInfo info
  guard (isAlwaysTailCalled occ)
  let safe_occ = occ { occ_tail = NoTailCallInfo }
  pure $! info `setOccInfo` safe_occ
compiler/coreSyn/CoreArity.hs
974–1062

Can you document what etaInfoAppBind does? It's not terribly obvious.

compiler/coreSyn/CorePrep.hs
555

Shouldn't there be some sort of assertion that this actually is a join point?

612

Making this let lazy seems a bit surprising. Is there a reason for that?

708

What does rhsToBodyNF do? A brief comment might help.

compiler/coreSyn/CoreSubst.hs
1037

If you don't want the info anymore, you can probably force the result here to actually get rid of it, rather than suspending that removal.

compiler/coreSyn/CoreSyn.hs
571

Could you emphasize the distinction between at least and exactly here? When I first read this, I thought they said the same thing. I imagine the reason for this distinction is in the paper? Or is this actually just a consequence of (1)?

573

It might not be bad to either mention what "return type" means or to point out that it is defined in the note below.

641

So why did you make this change from the paper? Is exprType incapable of handling the polymorphic result?

1970

This tail recursion feels forced. How about

collectNBinders orig_n orig_expr = go orig_n orig_expr
  where
    go 0 expr = ([], expr)
    go n (Lam b e) = first (b:) (go (n - 1) e)
    go _ _ = pprPanic ....
2134

The tail recursion feels forced here too. Why not

collectNAnnBndrs orig_n e = collect orig_n e
  where
    collect 0 body = ([], body)
    collect n (_, AnnLam b body) = first (b :) (collect (n - 1) body)
    collect _ _ = pprPanic ...
compiler/coreSyn/CoreUnfold.hs
730

Why is this the appropriate size?

compiler/coreSyn/MkCore.hs
247

foldr c n (reverse xs) is exactly the same as foldl (flip c) n xs. Since add_rename does (a little) work, that should probably be foldl' (flip add_rename) body rev_renames. If this is the only place add_rename is used, you can just flip its definition.

This revision now requires changes to proceed.Jan 22 2017, 11:11 PM
bgamari added inline comments.Jan 23 2017, 5:23 PM
compiler/basicTypes/BasicTypes.hs
839

Most of the "flag-ish" types above are just synonyms for Bool. If the answer is "yes" here then this should be done in another patch.

853–858

This is rather confusing. It seems like this function should likely be renamed since, as you mention above, there very well may be occurrence info in a ManyOccs constructor.

929–930

This could use a comment. What in particular is meant by fragile?

compiler/basicTypes/Id.hs
426

Why Var and not Id? Yes, they are synonyms but we should be consistent unless there is a good reason not to be.

637

Do you know what this comment refers to? I don't see any "old" strictnesses around.

bgamari added inline comments.Jan 23 2017, 6:54 PM
compiler/simplCore/Simplify.hs
214

Why are we not using the join j = ... in syntax used in the paper and elsewhere?

Also, what is E[...]? Does this denote just any evaluation context? If so then say so.

dfeuer added inline comments.Jan 23 2017, 7:17 PM
compiler/basicTypes/BasicTypes.hs
898

Can isAlwaysTailCalled_maybe be renamed to reflect the fact that it returns the JoinArity?

compiler/simplCore/OccurAnal.hs
730

Such an analysis could potentially affect other things. Suppose you have

f :: Num a => a -> Int -> Integer
f x y = ... (go x y) ...
  where
    go :: forall a . Num a => a -> Int -> Bool
    go p q = -- something recursive

Applying the type argument to go could (I believe) cause it to be specialized to the Num dictionary passed to f, which we may not want; the static argument transformation may be harmful in this case.

lukemaurer marked 5 inline comments as done.Jan 31 2017, 6:21 AM
lukemaurer added inline comments.
compiler/basicTypes/BasicTypes.hs
852

We still want something to be the safe default OccInfo; that used to be NoOccInfo. noOccInfo is really what the original NoOccInfo meant—there isn't any occ info (neither about cardinality nor about tail calls). We could also go with vanillaOccInfo (similar to vanillaCafInfo and vanillaIdInfo).

Certainly isNoOcc should change (it sounds like you're asking about deadness anyway!).

967

I suppose PotentialJoinPoint would make sense, sure.

972

I don't really see a way, short of having occurAnalysePgm return an Expr (TaggedBinder TailCallInfo) or something like that, which would be major surgery.

987

In the lexical sense, since it appears both in j2 and in a case branch below it.

compiler/basicTypes/Id.hs
480

Seems better there, yes. Despite similar implementation, has more in common with isTyVar than isDataConWorkId.

487

The name tends to be quite suggestive in use:

foo bndr expr bar
  | Just join_arity <- isJoinId_maybe bndr
  = ... -- join var case
  | otherwise
  = ... -- value var case

Also it seemed to fit the pattern with isDataConWorkId_maybe, isFunTy_maybe, etc., though it's true that what's in the Maybe is more obvious with those.

compiler/basicTypes/IdInfo.hs
554

None of the surrounding code seems to be paying attention to laziness (the zapXInfo functions get applied by combinators anyway, so I suspect nothing ends up lazy). The otherwise formulation in certainly clearer, though.

compiler/coreSyn/CoreLint.hs
1843

Whoops. Yes, it's out of date.

compiler/coreSyn/CorePrep.hs
612

There isn't much care for strictness in the surrounding code. This doesn't seem likely to leak memory, at any rate.

compiler/coreSyn/CoreSyn.hs
641

Actually, exprType would be okay because of the extra type argument. Mostly it's just that the extra type argument to each jump would be jarring. That said, I'd be open to changing it (probably no time for 8.2 though). The paper's type system actually came second, so inertia was on the side of the implemented system.

1970

It's consistent with the surrounding code this way.

2134

Same; all the collect*Bndrs functions are tail-recursive (not entirely sure why).

compiler/coreSyn/CoreUnfold.hs
730

Not for much of a good reason besides that it makes things not go bad. Any bigger and we lose a 21% improvement in allocs for spectral/puzzle; any smaller and we reopen Trac #6028. (Adding a comment to this effect.)

lukemaurer marked 8 inline comments as done.Jan 31 2017, 6:57 AM
lukemaurer added inline comments.
compiler/basicTypes/BasicTypes.hs
898

Got rid of it instead; wasn't using it. (Just as easy to use a pattern guard.)

compiler/basicTypes/Id.hs
426

It's not just the type, it's the definition; the predicates work on any Var. At any rate, I moved these to the Var module where they're more at home (alongside isCoVar, which similarly just checks for the right IdDetails).

637

Does it mean historically? Like, it used to be the only strictness came from types?

compiler/simplCore/OccurAnal.hs
730

Won't it already be specialized due to the initial call?

lukemaurer updated this revision to Diff 10830.Jan 31 2017, 7:18 AM
lukemaurer edited edge metadata.
lukemaurer marked 2 inline comments as done.
  • Simplify: Remove special case for single-alt cases
  • OccurAnal: Keep RHS context under big lambda
  • Remove LNE analysis from CoreToStg
  • CorePrep: Code cleanup
  • CoreUnfold: Clarify size_up_bndr
  • CorePrep: Add note to cpeJoinPair
  • Improve comments in FloatIn, FloatOut
  • Eliminate mkParallelBindings in favor of type rule for beta redexes
  • Fix old syntax for join points in comment
  • OccurAnal: Fix silliness with tagBinder, setBinderOcc
  • OccurAnal: Cleanup, refactoring
  • Move isJoinId, isJoinId_maybe to Var
  • No CSE for join points
  • Zap tail call info when floating to top level
  • Downgrade ASSERT to WARN for failure to rediscover a join point
  • Zap tail call info whenever not needed
  • Allow high-arity join points again
  • Comments
  • Cleanups
bgamari added inline comments.Jan 31 2017, 6:08 PM
compiler/simplCore/OccurAnal.hs
685

Am I understanding correctly that this is something that we do not currently do? If so perhaps we should open a ticket to record this missed opportunity.

741

It's not clear to me what we are talking about here. Whose occurrence information are we supposed to be marking in the case of a lambda? Perhaps a small example would help?

2643

What is the 'RecFlag' for in this case? It would be good to state this explicitly.

compiler/simplCore/Simplify.hs
1518

This function could really use a comment. What are we matching? Against what?

compiler/stgSyn/CoreToStg.hs
808

It would be nice if this comment reflected the name CtsM (what does this stand for anyways?)

Sorry for the belated comments, @lukemaurer. I thought these had already been submitted but it seems I never actually hit the button.

lukemaurer marked 2 inline comments as done.Jan 31 2017, 8:53 PM
lukemaurer added inline comments.
compiler/stgSyn/CoreToStg.hs
808

Oops. Left over from when it was for the LNE pass. (Cts stands, rather unimaginatively, for core-to-STG; adding a comment.)

lukemaurer updated this revision to Diff 10848.Jan 31 2017, 9:00 PM
lukemaurer marked an inline comment as done.
lukemaurer edited edge metadata.
  • Merge branch 'master' into wip/join-points
  • Test changes following merge
  • Comments
  • Performance drift
lukemaurer updated this revision to Diff 10855.Feb 1 2017, 3:22 AM
lukemaurer edited edge metadata.
  • Performance drift in test
Closed by commit rGHC8d5cf8bf584f: Join points (authored by lukemaurer, committed by dfeuer). · Explain WhyFeb 1 2017, 12:46 PM
This revision was automatically updated to reflect the committed changes.

It looks like this was committed despite the performance regressions in perf/compiler/all.T. What's the plan here?

It looks like this was committed despite the performance regressions in perf/compiler/all.T. What's the plan here?

There's a ticket: Trac Trac #13220, which Luke is going to pursue.

All the regressions are modest, and there are quite a few that improve! The patch fixes a number of perf bugs too. So, given the 8.2 deadline, I just decided to accept the changes an pursue later.

compiler/coreSyn/CoreUnfold.hs
651

Call it size_up_alloc: commit is that it's counting the size of the code to allocat the closure. For unlifted, or for join points, clearly zero

730

Why not zero? You said that something bad happened if you made it zero. Write a Note!