Statically estimate execution frequency of Core case alternative
Consider
sum n = case n of
0 -> 0 :: Int
_ -> n + sum (n-1)Having an estimate that says that the recursive path is hotter than the non-recursive path is quite useful to a number of optimisations:
- The Simplifier could decide not to inline in the cold branch, having more code size to spend inlining in the second branch.
- The first branch may need some value boxed, but the second one doesn't. It may be more efficient to unbox the value and re-allocate the box in the first branch.
- Similarly, we could give 'sum' the CPR property, thereby unboxing its result and destroying the sharing of the (then floated out) 0 CAF.
- We may float out a binding from the second alternative, even if that means more allocation if we take the first alternative
- It would allow easy integration of https://github.com/AndreasPK/ghc-proposals/blob/master/proposals/0000-likelihood-annotations.rst, although that appears to be somewhat orthogonal
- (Feel free to add more...)
There's abundant literature on how to come up with such estimates for imperative IRs/control flow graphs. We just have to transfer the knowledge there to multi-way case alternatives.