DmdAnal: Implement Boxity Analysis (#19871)wip/T19871

This patch fixes some abundant reboxing of `DynFlags` in
`GHC.HsToCore.Match.Literal.warnAboutOverflowedLit` (which was the topic
of #19407) by introducing a Boxity analysis to GHC, done as part of demand
analysis. This allows to accurately capture ad-hoc unboxing decisions previously
made in worker/wrapper in demand analysis now, where the boxity info can
propagate through demand signatures.

See the new `Note [Boxity analysis]`. The actual fix for #19407 is described in
`Note [No lazy, Unboxed demand in demand signature]`, but
`Note [Finalising boxity for demand signature]` is probably a better entry-point.

To support the fix for #19407, I had to change (what was)
`Note [Add demands for strict constructors]` a bit
(now `Note [Unboxing evaluated arguments]`). In particular, we now take care of
it in `finaliseBoxity` (which is only called from demand analaysis) instead of
`wantToUnboxArg`.

I also had to resurrect `Note [Product demands for function body]` and rename
it to `Note [Unboxed demand on function bodies returning small products]` to
avoid huge regressions in `join004` and `join007`, thereby fixing #4267 again.
See the updated Note for details.

A nice side-effect is that the worker/wrapper transformation no longer needs to
look at strictness info and other bits such as `InsideInlineableFun` flags
(needed for `Note [Do not unbox class dictionaries]`) at all. It simply collects
boxity info from argument demands and interprets them with a severely simplified
`wantToUnboxArg`. All the smartness is in `finaliseBoxity`, which could be moved
to DmdAnal completely, if it wasn't for the call to `dubiousDataConInstArgTys`
which would be awkward to export.

I spent some time figuring out the reason for why `T16197` failed prior to my
amendments to `Note [Unboxing evaluated arguments]`. After having it figured
out, I minimised it a bit and added `T16197b`, which simply compares computed
strictness signatures and thus should be far simpler to eyeball.

The 12% ghc/alloc regression in T11545 is because of the additional `Boxity`
field in `Poly` and `Prod` that results in more allocation during `lubSubDmd`
and `plusSubDmd`. I made sure in the ticky profiles that the number of calls
to those functions stayed the same. We can bear such an increase here, as we
recently improved it by -68% (in b760c1f).
T18698* regress slightly because there is more unboxing of dictionaries
happening and that causes Lint (mostly) to allocate more.

Fixes #19871, #19407, #4267, #16859, #18907 and #13331.

Metric Increase:
    T11545
    T18698a
    T18698b

Metric Decrease:
    T12425
    T16577
    T18223
    T18282
    T4267
    T9961

1 files changed, 14 insertions, 22 deletions

diff --git a/compiler/GHC/Core/Opt/CprAnal.hs b/compiler/GHC/Core/Opt/CprAnal.hs
index d3f6a248ce..65468cd037 100644
--- a/compiler/GHC/Core/Opt/CprAnal.hs
+++ b/compiler/GHC/Core/Opt/CprAnal.hs
@@ -21,14 +21,13 @@ import GHC.Types.Id.Info
 import GHC.Types.Demand
 import GHC.Types.Cpr
 
-import GHC.Core.DataCon
 import GHC.Core.FamInstEnv
-import GHC.Core.Multiplicity
-import GHC.Core.Opt.WorkWrap.Utils
+import GHC.Core.DataCon
 import GHC.Core.Type
 import GHC.Core.Utils
 import GHC.Core
 import GHC.Core.Seq
+import GHC.Core.Opt.WorkWrap.Utils
 
 import GHC.Data.Graph.UnVar -- for UnVarSet
 
@@ -639,30 +638,23 @@ nonVirgin env = env { ae_virgin = False }
 -- See Note [CPR for binders that will be unboxed].
 extendSigEnvForArg :: AnalEnv -> Id -> AnalEnv
 extendSigEnvForArg env id
-  = extendSigEnv env id (CprSig (argCprType env (idType id) (idDemandInfo id)))
+  = extendSigEnv env id (CprSig (argCprType (idDemandInfo id)))
 
 -- | Produces a 'CprType' according to how a strict argument will be unboxed.
 -- Examples:
 --
---   * A head-strict demand @1L@ on @Int@ would translate to @1@
---   * A product demand @1P(1L,L)@ on @(Int, Bool)@ would translate to @1(1,)@
---   * A product demand @1P(1L,L)@ on @(a , Bool)@ would translate to @1(,)@,
---     because the unboxing strategy would not unbox the @a@.
-argCprType :: AnalEnv -> Type -> Demand -> CprType
-argCprType env arg_ty dmd = CprType 0 (go arg_ty dmd)
+--   * A head-strict demand @1!L@ would translate to @1@
+--   * A product demand @1!P(1!L,L)@ would translate to @1(1,)@
+--   * A product demand @1!P(1L,L)@ would translate to @1(,)@,
+--     because the first field will not be unboxed.
+argCprType :: Demand -> CprType
+argCprType dmd = CprType 0 (go dmd)
   where
-    go ty dmd
-      | Unbox (DataConPatContext { dcpc_dc = dc, dcpc_tc_args = tc_args }) ds
-          <- wantToUnboxArg (ae_fam_envs env) MaybeArgOfInlineableFun ty dmd
-      -- No existentials; see Note [Which types are unboxed?])
-      -- Otherwise we'd need to call dataConRepInstPat here and thread a
-      -- UniqSupply. So argCprType is a bit less aggressive than it could
-      -- be, for the sake of coding convenience.
-      , null (dataConExTyCoVars dc)
-      , let arg_tys = map scaledThing (dataConInstArgTys dc tc_args)
-      = ConCpr (dataConTag dc) (zipWith go arg_tys ds)
-      | otherwise
-      = topCpr
+    go (n :* sd)
+      | isAbs n               = topCpr
+      | Prod Unboxed ds <- sd = ConCpr fIRST_TAG (strictMap go ds)
+      | Poly Unboxed _  <- sd = ConCpr fIRST_TAG []
+      | otherwise             = topCpr
 
 {- Note [Safe abortion in the fixed-point iteration]
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~