Demand: Share code/concepts between opDmd and opSubDmd
Now that !7599 (merged) has landed, the similarity of a Demand
n :* sd
and a Call
SubDemand
Cn(sd)
becomes increasingly clear:
opDmdInl m@(l,u) (n1 :* sd1) (n2 :* sd2) =
opCard m n1 n2 :* case l of
Lub -> opSubDmd m sd1 sd2
-- For Plus, there are four special cases due to strictness demands and
-- Note [SubDemand denotes at least one evaluation]:
Plus -> case (isStrict n1, isStrict n2) of
(True, True) -> opSubDmd (Plus, u) sd1 sd2 -- (D1)
(True, False) -> opSubDmd (Plus, u) sd1 (lazifySubDmd sd2) -- (D2)
(False, True) -> opSubDmd (Plus, u) (lazifySubDmd sd1) sd2 -- (D2)
(False, False) -> opSubDmd (Lub, u) sd1 sd2 -- (D3)
opSubDmdInl m@(l, _) (Call n1 sd1) (viewCall -> Just (n2, sd2)) =
mkCall (opCard m n1 n2) $! case l of
Lub -> opSubDmd (Lub, Lub) sd1 sd2
-- For Plus, there are four special cases due to strictness demands and
-- Note [SubDemand denotes at least one evaluation]. Usage is always lubbed:
Plus -> case (isStrict n1, isStrict n2) of
(True, True) -> opSubDmd (Plus, Lub) sd1 sd2 -- (C3)
(False, True) -> opSubDmd (Plus, Lub) (lazifySubDmd sd1) sd2 -- (C2)
(True, False) -> opSubDmd (Plus, Lub) sd1 (lazifySubDmd sd2) -- (C2)
(False, False) -> opSubDmd (Lub, Lub) sd1 sd2 -- (C1)
In fact, they are so similar that it's simplest to enumerate the differences:
- Let's first start off with a non-difference: The two functions coincide for lower bounds/strictness! Which means we need the
(:*)
/Call
distinction entirely for upper bounds/usage. - Where
opDmd
passes down the genericu :: LubOrPlus
to the sub-demand, forCall
it always usesLub
, which yields a weaker approximation ifu
wasPlus
. It makes a difference forplusDmd
andplusSubDmd
, respectively.
To better understand (2), we need to understand the difference between doing Lub
and Plus
. There is only one such difference: 1 + 1 = ω
, whereas 1 ⊔ 1 = 1
.
We need to use Plus
on the nested SubDemand in plusDmd
because a thunk repeatedly returns the same expression.
We need to use Lub
on the nested SubDemand of a Call
in plusSubDmd
because the lambda body is instantiated multiple times, each time with fresh locals.
Here's an example doing both (because it's impossible to give an example that does plusSubDmd
without doing plusDmd
):
\f -> f x y * f y x
-- will do `f :-> plusDmd 1C1(C1(L)) 1C1(C1(L))` when analysing the (*) app
-- and then `f :-> plusSubDmd C1(C1(L)) C1(C1(L))` in the call to `plusDmd`
The resulting demand on f
is f :-> SCS(C1(L))
.
plusDmd
will do (plusCard 1 1 = S
to get the outer S..
shell, and) one level of plusSubDmd
(because it passes down u=Plus
), because we share the WHNF of f
and then call the same heap object twice (hence ..CS(..)
). But resulting PAP is never shared and the recursive call to plusLubSubDmd
in the Call
case of plusSubDmd
is with u=Lub
. Hence the inner call demand in the result is with cardinality 1.
It is kind of the inverse contract of memoisation: Sharing enables entering the same heap object multiple times and plusDmd
accounts for that.
To have some concrete action in this ticket that we can discuss, I propose to use the same code paths for Call
SubDemands as well as (:*)
demands. Not sure what to call the shared data-type... Perhaps Demand
is good and it should just carry another data Sharing = Shared | NotShared
flag.
This ticket is some further evidence that perhaps we might want to separate strictness and usage after all... Not sure.
@simonpj, let's discuss (here and/or in our next call).