Considerations for Control flow hint implementation.

[Andreas Klebinger]

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/ac42f404/attachment.html>