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, 3 insertions, 3 deletions

diff --git a/compiler/GHC/Core/Subst.hs b/compiler/GHC/Core/Subst.hs
index 83e91ad21a..309c985642 100644
--- a/compiler/GHC/Core/Subst.hs
+++ b/compiler/GHC/Core/Subst.hs
@@ -374,9 +374,9 @@ substExpr subst expr
                                  where
                                  (subst', bndr') = substBndr subst bndr
 
-    go_alt subst (Alt con bndrs rhs) = Alt con bndrs' (substExpr subst' rhs)
-                                 where
-                                   (subst', bndrs') = substBndrs subst bndrs
+    go_alt subst (Alt con freq bndrs rhs) = Alt con freq bndrs' (substExpr subst' rhs)
+                                          where
+                                            (subst', bndrs') = substBndrs subst bndrs
 
 -- | Apply a substitution to an entire 'CoreBind', additionally returning an updated 'Subst'
 -- that should be used by subsequent substitutions.