Nested CPR analysis (#18174)wip/nested-cpr-2019

This commit extends CPR analysis to unbox nested constructors.
See `Note [Nested CPR]` for examples.

Unboxing a function's result beyond the first level risks making the
function more strict, rendering the transformation unsound.
See `Note [Nested CPR needs Termination information]`.
To justify unboxing anyway, Nested CPR interleaves a termination
analysis that is like a higher-order `exprOkForSpeculation`.

The termination analysis makes for the bulk of complexity in this patch.
In principle, we can use the results of that analysis in many more ways
in the future to do speculative execution.

Although there are quite a few examples in test cases that are now
properly optimised (e.g., `T1600`, `T18174`, `T18894`), the results on
NoFib are rather meager:

```
--------------------------------------------------------------------------------
        Program         Allocs    Instrs
--------------------------------------------------------------------------------
      cacheprof          -0.3%     -1.4%
      compress2          -1.9%     -0.9%
 fannkuch-redux           0.0%     -1.3%
         gamteb          -1.6%     -0.3%
       nucleic2          -1.2%     -0.6%
          sched          -0.0%     +0.9%
           x2n1          -0.0%     -5.0%
--------------------------------------------------------------------------------
            Min          -1.9%     -5.0%
            Max          +0.1%     +0.9%
 Geometric Mean          -0.1%     -0.1%
```

Allocation while compiling NoFib increases by 0.5%.
Binary sizes on NoFib increase by 0.7%.

This patch manages to fix a few tickets:
Fixes #1600, #18174, #18109

`ghc/alloc` performance generally increases.
`run/alloc` metrics improve throughout.

Justifications for metric increases:

  - `MultiLayerModules` increases due to #19293.
  - I could reproduce the 2.5% increase on `T13701` on fedora in a `-O0`
    perf-flavoured build. With `-fno-code` or `-O2` this patch is
    faster. I investigated `-v2` output, nothing obvious. It's very
    similar to #19293, so I'm just going to accept it.
  - The +15% `ghc/alloc` increase on `T15164` in a registerised,
    validate-flavoured build does not show up under `-dshow-passes` and
    has no impact on runtime. #19311
  - I verified that `T13253` simply does one more round of
    Simplification after Nested CPR
  - I looked at heap profiles for the `ghc/max_bytes_used` increases,
    which didn't show any obvious offenders.

Metric Decrease:
    T1969
    T9203
    T9233
    T9872a
    T9872b
    T9872c
    T9872d
    T12425
    T12545
Metric Increase ['bytes allocated']:
    T13253
    MultiLayerModules
Metric Increase ['bytes allocated'] (test_env='x86_64-linux-deb9-unreg-hadrian'):
    T15164
Metric Increase ['bytes allocated'] (test_env='x86_64-linux-fedora27'):
    T13701
Metric Increase ['max_bytes_used'] (test_env='x86_64-darwin'):
    T9675
Metric Increase ['max_bytes_used'] (test_env='x86_64-linux-deb9-dwarf'):
    T9675
Metric Increase ['max_bytes_used', 'peak_megabytes_allocated']:
    T10370

1 files changed, 9 insertions, 2 deletions

diff --git a/compiler/GHC/Iface/Syntax.hs b/compiler/GHC/Iface/Syntax.hs
index 73e8525589..e97299f171 100644
--- a/compiler/GHC/Iface/Syntax.hs
+++ b/compiler/GHC/Iface/Syntax.hs
@@ -52,6 +52,7 @@ import GHC.Iface.Recomp.Binary
 import GHC.Core( IsOrphan, isOrphan )
 import GHC.Types.Demand
 import GHC.Types.Cpr
+import GHC.Types.Termination
 import GHC.Core.Class
 import GHC.Types.FieldLabel
 import GHC.Types.Name.Set
@@ -349,6 +350,7 @@ type IfaceIdInfo = [IfaceInfoItem]
 data IfaceInfoItem
   = HsArity         Arity
   | HsStrictness    StrictSig
+  | HsTerm          TermSig
   | HsCpr           CprSig
   | HsInline        InlinePragma
   | HsUnfold        Bool             -- True <=> isStrongLoopBreaker is true
@@ -1466,6 +1468,7 @@ instance Outputable IfaceInfoItem where
   ppr (HsInline prag)       = text "Inline:" <+> ppr prag
   ppr (HsArity arity)       = text "Arity:" <+> int arity
   ppr (HsStrictness str)    = text "Strictness:" <+> ppr str
+  ppr (HsTerm term)         = text "Term:" <+> ppr term
   ppr (HsCpr cpr)           = text "CPR:" <+> ppr cpr
   ppr HsNoCafRefs           = text "HasNoCafRefs"
   ppr HsLevity              = text "Never levity-polymorphic"
@@ -2233,6 +2236,7 @@ instance Binary IfaceInfoItem where
     put_ bh HsLevity              = putByte bh 5
     put_ bh (HsCpr cpr)           = putByte bh 6 >> put_ bh cpr
     put_ bh (HsLFInfo lf_info)    = putByte bh 7 >> put_ bh lf_info
+    put_ bh (HsTerm cpr)          = putByte bh 8 >> put_ bh cpr
 
     get bh = do
         h <- getByte bh
@@ -2246,7 +2250,9 @@ instance Binary IfaceInfoItem where
             4 -> return HsNoCafRefs
             5 -> return HsLevity
             6 -> HsCpr <$> get bh
-            _ -> HsLFInfo <$> get bh
+            7 -> HsLFInfo <$> get bh
+            8 -> HsTerm <$> get bh
+            _ -> pprPanic "Binary IfaceInfoItem: Invalid tag" (int (fromIntegral h))
 
 instance Binary IfaceUnfolding where
     put_ bh (IfCoreUnfold s e) = do
@@ -2586,8 +2592,9 @@ instance NFData IfaceInfoItem where
     HsUnfold b unf -> rnf b `seq` rnf unf
     HsNoCafRefs -> ()
     HsLevity -> ()
-    HsCpr cpr -> cpr `seq` ()
+    HsCpr cpr -> seqCprSig cpr `seq` ()
     HsLFInfo lf_info -> lf_info `seq` () -- TODO: seq further?
+    HsTerm term -> seqTermSig term `seq` ()
 
 instance NFData IfaceUnfolding where
   rnf = \case