Demand analysis: Wrong one-shot annotation due to fixed-point iteration
After quite a while of staring at the core of nofib’s fft2
benchmark, where my dynamic entry counting code (#10613), I found the problem. Here is a small example:
foo :: Int -> Int -> Int
foo 10 c = 0
foo n c =
let bar :: Int -> Int
bar n = n + c
{-# NOINLINE bar #-}
in bar n + foo (bar (n+1)) c
Clearly, bar
is not single-entry. But the demand analyzer believes it is:
Rec {
-- RHS size: {terms: 32, types: 12, coercions: 0}
foo [Occ=LoopBreaker] :: Int -> Int -> Int
[LclIdX,
Arity=2,
Str=<S(S),1*U(U)><L,U(U)>m,
Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True,
WorkFree=True, Expandable=True, Guidance=IF_ARGS [20 0] 192 20}]
foo =
\ (ds [Dmd=<S(S),1*U(U)>] :: Int) (c [Dmd=<L,U(U)>] :: Int) ->
case ds of wild [Dmd=<L,1*U(U)>] { I# ds [Dmd=<S,U>] ->
case ds of ds {
__DEFAULT ->
let {
bar [InlPrag=NOINLINE, Dmd=<C(S(S)),C(U(U))>] :: Int -> Int
[LclId,
Arity=1,
CallArity=1,
Str=<S(S),1*U(U)>m {axl-><S(S),1*U(U)>},
Unf=Unf{Src=<vanilla>, TopLvl=False, Value=True, ConLike=True,
WorkFree=True, Expandable=True, Guidance=IF_ARGS [0] 30 0}]
bar =
\ (n [Dmd=<S(S),1*U(U)>, OS=OneShot] :: Int) ->
$fNumInt_$c+ n c } in
case bar wild of _ [Occ=Dead, Dmd=<L,A>] { I# x [Dmd=<S,U>] ->
case foo (bar (I# (+# ds 1#))) c
of _ [Occ=Dead, Dmd=<L,A>] { I# y [Dmd=<S,U>] ->
I# (+# x y)
}
};
10# -> lvl
}
}
end Rec }
The reason is that during the first fixed-point iteration for foo
, foo
itself is assumed to not put any demand on its arguments. Under this assumption, it is correct to find that bar
is called at most once. This is then noted in the lambda binder. The second iteration corrects the demand, but not the one-shot annotation, because that is only added by the demand analyzer, never dropped:
setOneShotness :: Count -> Id -> Id
setOneShotness One bndr = setOneShotLambda bndr
setOneShotness Many bndr = bndr
This can be fixed by changing that code (from DmdAnal.hs
) to
setOneShotness :: Count -> Id -> Id
setOneShotness One bndr = setOneShotLambda bndr
setOneShotness Many bndr = clearOneShotLambda bndr
But this would have other consequences, e.g. erasing any possible manual one-shot annotations using oneShot
.
Or maybe setOneShotness
should not be set by the demand analyzer during its work, but once at the end, or maybe even the next simplifier pass should take care of that.
Trac metadata
Trac field | Value |
---|---|
Version | 8.1 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |