Reduce inlining in deeply-nested caseswip/T18730

This adds a new heuristic, controllable via two new flags to
better tune inlining behaviour.

The new flags are -funfolding-case-threshold and
-funfolding-case-scaling which are document both
in the user guide and in
Note [Avoid inlining into deeply nested cases].

Co-authored-by: Andreas Klebinger <klebinger.andreas@gmx.at>

2 files changed, 136 insertions, 0 deletions

diff --git a/docs/users_guide/hints.rst b/docs/users_guide/hints.rst
index cdec6a4f4c..5cb171ff69 100644
--- a/docs/users_guide/hints.rst
+++ b/docs/users_guide/hints.rst
@@ -368,3 +368,70 @@ discussed in the previous section. Strict functions get right down to
 business, rather than filling up the heap with closures (the system's
 notes to itself about how to evaluate something, should it eventually be
 required).
+
+.. _control-inlining:
+
+Controlling inlining via optimisation flags.
+--------------------------------------------
+
+.. index::
+    single: inlining, controlling
+    single: unfolding, controlling
+
+Inlining is one of the major optimizations GHC performs. Partially
+because inlining often allows other optimizations to be triggered.
+Sadly this is also a double edged sword. While inlining can often
+cut through runtime overheads this usually comes at the cost
+of not just program size, but also compiler performance. In
+extreme cases making it impossible to compile certain code.
+
+For this reason GHC offers various ways to tune inlining
+behaviour.
+
+Unfolding creation
+~~~~~~~~~~~~~~~~~~
+
+In order for a function from a different module to be inlined
+GHC requires the functions unfolding. The following flags can
+be used to control unfolding creation. Making their creation more
+or less likely:
+
+* :ghc-flag:`-fexpose-all-unfoldings`
+* :ghc-flag:`-funfolding-creation-threshold=⟨n⟩`
+
+Inlining decisions
+~~~~~~~~~~~~~~~~~~
+
+If a unfolding is available the following flags can impact GHC's
+decision about inlining a specific binding.
+
+* :ghc-flag:`-funfolding-use-threshold=⟨n⟩`
+* :ghc-flag:`-funfolding-case-threshold=⟨n⟩`
+* :ghc-flag:`-funfolding-case-scaling=⟨n⟩`
+* :ghc-flag:`-funfolding-dict-discount=⟨n⟩`
+* :ghc-flag:`-funfolding-fun-discount=⟨n⟩`
+
+Should the simplifier run out of ticks because of a inlining loop
+users are encouraged to try decreasing :ghc-flag:`-funfolding-case-threshold=⟨n⟩`
+or :ghc-flag:`-funfolding-case-scaling=⟨n⟩` to limit inlining into
+deeply nested expressions while allowing a higher tick factor.
+
+The defaults of these are tuned such that we don't expect regressions for most
+user programs. Using a :ghc-flag:`-funfolding-case-threshold=⟨n⟩` of 1-2 with a
+:ghc-flag:`-funfolding-case-scaling=⟨n⟩` of 15-25 can cause usually small runtime
+regressions but will prevent most inlining loops from getting out of control.
+
+In extreme cases lowering scaling and treshold further can be useful, but at that
+point it's very likely that beneficial inlining is prevented as well resulting
+in significant runtime regressions.
+
+In such cases it's recommended to move the problematic piece of code into it's own
+module and changing inline parameters for the offending module only.
+
+Inlining generics
+~~~~~~~~~~~~~~~~~
+
+There are also flags specific to the inlining of generics:
+
+:ghc-flag:`-finline-generics`
+:ghc-flag:`-finline-generics-aggressively`
diff --git a/docs/users_guide/using-optimisation.rst b/docs/users_guide/using-optimisation.rst
index ee5b1de95e..0bacf71eb8 100644
--- a/docs/users_guide/using-optimisation.rst
+++ b/docs/users_guide/using-optimisation.rst
@@ -1423,6 +1423,73 @@ by saying ``-fno-wombat``.
     determines if a function definition will be kept around at all for
     potential inlining.
 
+.. ghc-flag:: -funfolding-case-threshold=⟨n⟩
+    :shortdesc: *default: 2.* Reduce inlining for cases nested deeper than n.
+    :type: dynamic
+    :category:
+
+    :default: 2
+
+    .. index::
+       single: inlining, controlling
+       single: unfolding, controlling
+
+    GHC is in general quite eager to inline small functions. However sometimes
+    these functions will be expanded by more inlining after inlining. Since
+    they are now applied to "interesting" arguments. Even worse, their expanded
+    form might reference again a small function, which will be inlined and expanded
+    afterwards. This can repeat often and lead to explosive growth of programs.
+
+    As it happened in #18730.
+
+    Starting with GHC 9.0 we will be less eager to inline deep into nested cases.
+    We achieve this by applying a inlining penalty that increases as the nesting
+    gets deeper. However sometimes a specific (maybe quite high!) threshold of nesting
+    is to be expected.
+
+    In such cases this flag can be used to ignore the first ⟨n⟩ levels of nesting
+    when computing the penalty.
+
+    This flag in combination with :ghc-flag:`-funfolding-case-scaling=⟨n⟩` can
+    be used to break inlining loops without disabling inlining completely. For
+    this purpose a smaller value is more likely to break such loops although
+    often adjusting the scaling is enough and preferably.
+
+.. ghc-flag:: -funfolding-case-scaling=⟨n⟩
+    :shortdesc: *default: 30.* Apply a penalty of (inlining_cost * `1/n`) for each level of case nesting.
+    :type: dynamic
+    :category:
+
+    :default: 30
+
+    .. index::
+       single: inlining, controlling
+       single: unfolding, controlling
+
+    GHC is in general quite eager to inline small functions. However sometimes
+    these functions will be expanded by more inlining after inlining. Since
+    they are now applied to "interesting" arguments. Even worse, their expanded
+    form might reference again a small function, which will be inlined and expanded
+    afterwards. This can repeat often and lead to explosive growth of programs.
+
+    As it happened in #18730.
+
+    Starting with GHC 9.0 we will be less eager to inline deep into nested cases.
+    We achieve this by applying a inlining penalty that increases as the nesting
+    gets deeper. However sometimes we are ok with inlining a lot in the name of
+    performance.
+
+    In such cases this flag can be used to tune how hard we penalize inlining into
+    deeply nested cases beyond the threshold set by :ghc-flag:`-funfolding-case-threshold=⟨n⟩`.
+    Cases are only counted against the nesting level if they have more than one alternative.
+
+    We use 1/n to scale the penalty. That is a higher value gives a lower penalty.
+
+    This can be used to break inlining loops. For this purpose a lower value is
+    recommended. Values in the range 10 <= n <= 20 allow some inlining to take place
+    while still allowing GHC to compile modules containing such inlining loops.
+
+
 .. ghc-flag:: -fworker-wrapper
     :shortdesc: Enable the worker/wrapper transformation.
     :type: dynamic
@@ -1455,3 +1522,5 @@ by saying ``-fno-wombat``.
     This flag sets the size (in bytes) threshold above which the second approach
     is used. You can disable the second approach entirely by setting the
     threshold to 0.
+
+