Note [Call SubDemand vs. evaluation Demand]

GHC/Types/Demand.hs:1237 compiler 1 ticket

Although both evaluation Demands and Call SubDemands carry a (Card,SubDemand)
pair, their interpretation is quite different. Example:

  f x = fst x * snd x
    f :: <SP(1L,1L)>, because 1P(1L,A)+1P(A,1L) = SP(1L,1L)
  g x = fst (x 1) * snd (x 2)
    g :: <SC(S,P(ML,ML))>, because 1C(1,P(1L,A))+1C(1,P(A,1L)) = SC(S,P(ML,ML))

The point about this example is that both demands have P(A,1L)/P(1L,A) as
sub-expressions, but when these sub-demands occur

  1. under an evaluation demand, we combine with `plusSubDmd`
  2. whereas under a Call sub-demand, we combine with `lubSubDmd`

And thus (1) yields a stricter demand on the pair components than (2).

In #21717 we saw that we really need lub in (2), because otherwise we make an
unsound prediction in `g (\n -> if n == 1 then (1,1) else (bot,2))`; we'd say
that the `bot` expression is always evaluated, when it clearly is not.
Operationally, every call to `g` gives back a potentially distinct,
heap-allocated pair with potentially different contents, and we must `lubSubDmd`
over all such calls to approximate how any of those pairs might be used.

That is in stark contrast to f's argument `x`: Operationally, every eval of
`x` must yield the same pair and `f` evaluates both components of that pair.
The theorem "every eval of `x` returns the same heap object" is a very strong
MUST-alias property and we capitalise on that by using `plusSubDmd` in (1).

And indeed we *must* use `plusSubDmd` in (1) for sound upper bounds in an
analysis that assumes call-by-need (as opposed to the weaker call-by-name) for
let bindings. Consider

  h x = fst x * fst x
    h :: <SP(SL,A)>

And the expression `let a=1; p=(a,a)} in h p`. Here, *although* the RHS of `p`
is only evaluated once under call-by-need, `a` is still evaluated twice.
If we had used `lubSubDmd`, we'd see SP(1L,A) and the 1L unsoundly says "exactly
once".

If the analysis had assumed call-by-name, it would be sound to say "a is used
once in p": p is used multiple times and hence so would a, as if p was a
function. So using `plusSubDmd` does not only yield better strictness, it is
also "holding up the other end of the bargain" of the call-by-need assumption
for upper bounds.

(To SG's knowledge, the distinction between call-by-name and call-by-need does
not matter for strictness analysis/lower bounds, thus it would be sound to use
`lubSubDmd` all the time there.)

References 0

This Note does not link to any other.

Referenced by 2