Demand: Better representation (#19050)wip/T19050

In #19050, we identified several ways in which we could make more illegal
states irrepresentable. This patch introduces a few representation changes
around `Demand` and `Card` with a better and earlier-failing API exported
through pattern synonyms. Specifically,

1. The old enum definition of `Card` led to severely bloated code of operations
   on it. I switched to a bit vector representation; much nicer overall IMO.
   See Note [Bit vector representation for Card].

Most of the gripes with the old representation were related to where which kind
of `Card` was allowed and the fact that it doesn't make sense for an absent or
bottoming demand to carry a `SubDemand` that describes an evaluation context
that is never realised.

2. So I refactored the `Demand` representation so that it has two new data
   constructors for `AbsDmd` and `BotDmd`. The old `(:*)` data constructor
   becomes a pattern synonym which expands absent demands as needed, so that
   it still forms a complete match and a versatile builder. The new `Demand`
   data constructor now carries a `CardNonAbs` and only occurs in a very limited
   number of internal call sites.
3. Wherever a full-blown `Card` might end up in a `CardNonAbs` field (like that
   of `D` or `Call`), I assert the consistency. When the smart builder of `(:*)`
   is called with an absent `Card`, I assert that the `SubDemand` is the same
   that we would expand to in the matcher.
4. `Poly` now takes a `CardNonOnce` and encodes the previously noticed invariant
   that we never produce `Poly C_11` or `Poly C_01`. I made sure that we never
   construct a `Poly` with `C_11` or `C_01`.

Fixes #19050.

We lose a tiny bit of anal perf overall, probably because the new `Demand`
definition can't be unboxed. The biggest loser is WWRec, where allocations go
from 16MB to 26MB in DmdAnal, making up for a total increase of (merely) 1.6%.
It's all within acceptance thresholds.
There are even two ghc/alloc metric decreases. T11545 decreases by *67%*!

Metric Decrease:
    T11545
    T18304

1 files changed, 18 insertions, 7 deletions

diff --git a/compiler/GHC/Core/Opt/DmdAnal.hs b/compiler/GHC/Core/Opt/DmdAnal.hs
index bad3234ca9..5f209701a9 100644
--- a/compiler/GHC/Core/Opt/DmdAnal.hs
+++ b/compiler/GHC/Core/Opt/DmdAnal.hs
@@ -43,7 +43,8 @@ import GHC.Builtin.PrimOps
 import GHC.Builtin.Types.Prim ( realWorldStatePrimTy )
 import GHC.Types.Unique.Set
 
--- import GHC.Driver.Ppr
+import GHC.Utils.Trace
+_ = pprTrace -- Tired of commenting out the import all the time
 
 {-
 ************************************************************************
@@ -340,11 +341,12 @@ dmdAnalStar :: AnalEnv
             -> Demand   -- This one takes a *Demand*
             -> CoreExpr -- Should obey the let/app invariant
             -> (PlusDmdArg, CoreExpr)
-dmdAnalStar env (n :* cd) e
-  | WithDmdType dmd_ty e'    <- dmdAnal env cd e
+dmdAnalStar env (n :* sd) e
+  -- NB: (:*) expands AbsDmd and BotDmd as needed
+  -- See Note [Analysing with absent demand]
+  | WithDmdType dmd_ty e' <- dmdAnal env sd e
   = assertPpr (not (isUnliftedType (exprType e)) || exprOkForSpeculation e) (ppr e)
     -- The argument 'e' should satisfy the let/app invariant
-    -- See Note [Analysing with absent demand] in GHC.Types.Demand
     (toPlusDmdArg $ multDmdType n dmd_ty, e')
 
 -- Main Demand Analsysis machinery
@@ -427,7 +429,7 @@ dmdAnal' env dmd (Case scrut case_bndr ty [Alt alt bndrs rhs])
         WithDmdType alt_ty2 case_bndr_dmd = findBndrDmd env alt_ty1 case_bndr
         -- Evaluation cardinality on the case binder is irrelevant and a no-op.
         -- What matters is its nested sub-demand!
-        (_ :* case_bndr_sd)      = case_bndr_dmd
+        (_ :* case_bndr_sd) = case_bndr_dmd
         -- Compute demand on the scrutinee
         -- FORCE the result, otherwise thunks will end up retaining the
         -- whole DmdEnv
@@ -548,7 +550,7 @@ dmdAnalSumAlt env dmd case_bndr (Alt con bndrs rhs)
   , WithDmdType alt_ty dmds <- findBndrsDmds env rhs_ty bndrs
   , let (_ :* case_bndr_sd) = findIdDemand alt_ty case_bndr
         -- See Note [Demand on scrutinee of a product case]
-        id_dmds             = addCaseBndrDmd case_bndr_sd dmds
+        id_dmds              = addCaseBndrDmd case_bndr_sd dmds
         -- Do not put a thunk into the Alt
         !new_ids  = setBndrsDemandInfo bndrs id_dmds
   = WithDmdType alt_ty (Alt con new_ids rhs')
@@ -557,7 +559,7 @@ dmdAnalSumAlt env dmd case_bndr (Alt con bndrs rhs)
 Note [Analysing with absent demand]
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 Suppose we analyse an expression with demand A.  The "A" means
-"absent", so this expression will never be needed.  What should happen?
+"absent", so this expression will never be needed. What should happen?
 There are several wrinkles:
 
 * We *do* want to analyse the expression regardless.
@@ -566,6 +568,15 @@ There are several wrinkles:
   But we can post-process the results to ignore all the usage
   demands coming back. This is done by multDmdType.
 
+* Nevertheless, which sub-demand should we pick for analysis?
+  Since the demand was absent, any would do. Worker/wrapper will replace
+  absent bindings with an absent filler anyway, so annotations in the RHS
+  of an absent binding don't matter much.
+  Picking 'botSubDmd' would be the most useful, but would also look a bit
+  misleading in the Core output of DmdAnal, because all nested annotations would
+  be bottoming. Better pick 'seqSubDmd', so that we annotate many of those
+  nested bindings with A themselves.
+
 * In a previous incarnation of GHC we needed to be extra careful in the
   case of an *unlifted type*, because unlifted values are evaluated
   even if they are not used.  Example (see #9254):