DmdAnal: Annotate some top-level bindings with demands (#18894)
It's useful to annotate a non-exported top-level function like g
in
module Lib (h) where
g :: Int -> Int -> (Int,Int)
g m 1 = (m, 0)
g m n = (2 * m, 2 `div` n)
{-# NOINLINE g #-}
h :: Int -> Int
h 1 = 0
h m
| odd m = snd (g m 2)
| otherwise = uncurry (+) (g 2 m)
with its demand UCU(CS(P(1P(U),SP(U))
, which tells us that whenever g
was
called, the second component of the returned pair was evaluated strictly.
Since #18903 (closed) we do so for local functions, where we can see all calls.
For top-level functions, we can assume that all exported functions are
demanded according to topDmd
and thus get sound demands for
non-exported top-level functions.
The demand on g
is crucial information for Nested CPR, which may the
go on and unbox g
for the second pair component. That is true even if
that pair component may diverge, as is the case for the call site g 13 0
, which throws a div-by-zero exception.
We only track bindings of function type in order not to risk huge compile-time
regressions, see isInterestingTopLevelFn
.
Fixes #18894 (closed).
Merge request reports
Activity
I think it would help to partition
DmdEnv
into entries which have a polymorphic demand liketopDmd
and those which don't.We do something similar for variables which have no entry in
DmdEnv
at all: In case of atopDiv
Divergence
(e.g.C_00 :* Poly C_00
), we give them absent demand and in the case of abotDiv
Divergence
, they have a bottom demand (e.g.C_10 :* Poly C_10
).We could track all variables that have
topDmd
in a separateVarSet
. That would makelubDmdEnv
/plusDmdEnv
a bit (a lot?) more complicated, but it's the only way I can think of to make top-level annotations work.Most of the free variables of an expression refers to are top-level bindings (citation needed, but it's clear from the fact that generally programs are a lot "longer" than they are "deep") and hence we are currently paying heavily.
The numbers of the last run are much better! It seems that restricting which bindings to annotate to functions was quite effective. Only there's a strange
ghc/alloc
explosion inT17836(b)
I'm failing to reproduce locally.Edit: Turns out that I stared at the job log for !4494 (closed). Duh.
Edited by Sebastian Grafmentioned in merge request !4494 (closed)
mentioned in issue #18894 (closed)
mentioned in commit 7cf09ab0
added 1 commit
- 2391fad6 - DmdAnal: Annotate top-level function bindings with demands (#18894 (closed))
added 1 commit
- 549af695 - Try to find all top-level bindings interesting
added 2 commits
- b853798a - DmdAnal: Annotate top-level function bindings with demands (#18894 (closed))
- 3a7344fb - Demand: Simplify `CU(U)` to `U` (#19005 (closed))
added demand analysis label
@simonpj this is now ready for review.
mentioned in merge request !4557 (closed)
- Resolved by Sebastian Graf
Check that we get eta-expansion.
Intriguing qn: what does Call Arity do that this doesn't?
added 2 commits
- 376834e2 - DmdAnal: Annotate top-level function bindings with demands (#18894 (closed))
- 46e64ccd - Demand: Simplify `CU(U)` to `U` (#19005 (closed))
added 2 commits
- ad874c06 - DmdAnal: Annotate top-level function bindings with demands (#18894 (closed))
- 829ecab3 - Demand: Simplify `CU(U)` to `U` (#19005 (closed))