Considerations for Control flow hint implementation.

[Simon Peyton Jones]

Alternative 1: Putting the weights directly into the case alternative tuple

Rather than putting it in the tuple, you could put it in the AltCon

type Alt b = (AltCon, [b], Expr b)

data AltCon = DataAlt Freq DataCon | LitAlt Freq Literal | DEFAULT Freq

My guess is that a lot more current code pattern matches on those triples than pattern matches on the AltCon itself.  And AltCon isn't used for anything else

Simon


From: ghc-devs <ghc-devs-bounces at haskell.org> On Behalf Of Andreas Klebinger
Sent: 30 November 2018 11:37
To: ghc-devs at haskell.org
Subject: Considerations for Control flow hint implementation.

Hello Devs,

I've started thinking about the implementation of https://github.com/ghc-proposals/ghc-proposals/pull/182 recently. (Add control flow hint pragmas.)

For this purpose I've rebased D4327 "WIP: Add likelyhood to alternatives from stg onwards" which already does a lot of the work at the Cmm/Stg level.

The issue I ask you for feedback now is how to best attach branch weights to case alternatives in core.

My prefered approach would be to expand core data types to include them unconditionally.
While this is quite far reaching in the amount of code it touches it would be rather straight forward to implement:

Alternative 1: Putting the weights directly into the case alternative tuple:
+ It it's trivial to check which places manipulate case alternatives as they will initially fail to compile.
+ It's very mechanical, almost all use sites won't actually change the weight.
+ It's easy to keep this working going forward as any new optimizations can't "forget" they have to consider them.
- It will introduce a cost in compiler performance.
- New optimization who don't have to care about branchweights still have to at least pipe them through.
- While syntactically heavy in terms of real complexity it's a simply approach.

Alternative 2:  Putting the weights into the case constructor.
+ Might give better compiler performance as I expect us to rebuild cases less often than alternatives.
- Seems kind of clunky.
- Weaker coupling between case alternatives and their weights.

Or we could use ticks:
+ There is some machinery already there
+ Can be turned off for -O0
+ Can be ignored when convenient.
- Can be ignored when convenient.
- Very weak coupling between case alternatives and their weights.
- The existing machinery doesn't exactly match the needs of this.
- We would have to extend tick semantics to a degree where complexity might grow too large
  for me to successfully implement this.
- If new optimizations end up just removing these ticks because they are allowed to  then
  the whole exercise becomes rather pointless.
- Makes it harder to ensure all relevant code paths in GHC are actually updated.

In particular there is currently no tick category which can stick to case alternatives but just get's removed in case
it get's in the way of optimizations.
The closest match is SoftScope which allows ticks to be floated up, something that could impact performance quite badly
in this case. As then we might float something intended to mark a branch as unlikely into another branch that is actually
along the hot path.

I think the core variant(s) mostly stand and fall with the actual compile time impact. For -O0 the impact
would be negligible as the compile time is already dominated by codegen and typechecking. For the rest
it's hard to say.

So I'm looking for feedback on this. Maybe you have other suggestions I haven't considered?
How much compile time cost increase would be acceptable for what kind of performance boost?

Cheers,
Andreas Klebinger
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20181130/02ce8c48/attachment.html>