Considerations for Control flow hint implementation.
klebinger.andreas at gmx.at
Fri Nov 30 11:36:55 UTC 2018
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
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
+ 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
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
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
How much compile time cost increase would be acceptable for what kind of
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the ghc-devs