Statically estimate execution frequency of CoreAlts (#20378)wip/exec-freq

This patch implements #20378. See `Note [Estimating CoreAlt frequencies]` in the
new module GHC.Core.Opt.ExecFreq for details.

These were the changes:

1. Introduce `newtype Freq = Freq Float` as a type that captures relative
   execution frequency and use it as an additional field in `CoreAlt`.
   The default when we have no estimate available is `NoFreq`, e.g., NaN.
   Otherwise, all `Freq`s of a `Case` should add up to 1.
   Then fix up a whole bunch of use sites.
2. Introduce a new enum `Comparison` for the different kinds of comparison
   operators (LessThan, GreaterOrEqual, NotEqual, ...). Then make `Compare`
   primops also declare what kind of `Comparison` they do. Then introduce a
   function `isComparisonApp_maybe` in GHC.Core.Utils that we can use for our
   estimates (see below).
3. Write a static analysis pass `estimateAltFreqs`, that annotates `CoreAlt`s
   with their relative execution `Freq`. These `Freq`s are determined by
   combining the estimates of different branch heuristics, one of which uses
   the new `isComparisonApp_maybe`.

The main function `estimateAltFreqs` is currently dead, but that is bound to
change in follow-up MRs.

Fixes #20378.

1 files changed, 2 insertions, 2 deletions

diff --git a/compiler/GHC/Core/Unfold.hs b/compiler/GHC/Core/Unfold.hs
index f8dadf8c16..0305cc9d19 100644
--- a/compiler/GHC/Core/Unfold.hs
+++ b/compiler/GHC/Core/Unfold.hs
@@ -224,7 +224,7 @@ inlineBoringOk e
                         , exprIsTrivial a  = go (credit-1) f
     go credit (Tick _ e)                   = go credit e -- dubious
     go credit (Cast e _)                   = go credit e
-    go credit (Case scrut _ _ [Alt _ _ rhs]) -- See Note [Inline unsafeCoerce]
+    go credit (Case scrut _ _ [Alt _ _ _ rhs]) -- See Note [Inline unsafeCoerce]
       | isUnsafeEqualityProof scrut        = go credit rhs
     go _      (Var {})                     = boringCxtOk
     go _      _                            = boringCxtNotOk
@@ -570,7 +570,7 @@ sizeExpr opts !bOMB_OUT_SIZE top_args expr
            _                -> funSize opts top_args fun (length val_args) voids
 
     ------------
-    size_up_alt (Alt _con _bndrs rhs) = size_up rhs `addSizeN` 10
+    size_up_alt (Alt _con _freq _bndrs rhs) = size_up rhs `addSizeN` 10
         -- Don't charge for args, so that wrappers look cheap
         -- (See comments about wrappers with Case)
         --