owned this note
owned this note
Published
Linked with GitHub
---
title: Call 2022-10-27
tags: S+S, DmdAnal
---
# #22227 (join point loopification)
Top-level loopification blocked on #22274.
Idea: Do non-top-level first and unblock top-level through #22274
# #22274 (Exitification in OccurAnal)
https://gitlab.haskell.org/ghc/ghc/-/issues/22274
let's write here (about https://gitlab.haskell.org/ghc/ghc/-/issues/22274#note_459885)
```
blah = ... joinrec safe xs = .... case b of
True -> safe xs'
False -> {- exit path -}
if b' then go ys
else 42 : go ys ... in
in jump safe xs ...
```
Exitification should transform to
```
blah = ... join exit b' = if b' then go ys
else 42 : go ys ... in
joinrec safe xs = .... case b of
True -> safe xs'
False -> {- exit path -} exit b'
in jump safe xs ...
```
So the floated out `lvl` should inline back into that non-rec join point.
Danger: when we inline the exit join point again (which we now do) we might do a late float-out.
Original example from `queens`
```
let {
ds6 :: [[Int]]
[LclId]
ds6 = go1 ys1 } in
join {
exit :: [[Int]]
[LclId[JoinId(0)(Nothing)]]
exit
= GHC.Types.:
@[Int] (GHC.Types.: @Int y1 y) ds6 } in
joinrec {
safe [Occ=LoopBreaker, Dmd=SC(S,C(1,C(1,L)))]
:: Int -> Int -> [Int] -> [[Int]]
[LclId[JoinId(3)(Just [~, ~, !])],
Arity=3,
Str=<ML><ML><1L>,
Unf=OtherCon []]
safe (x1 :: Int) (d :: Int) (ds7 :: [Int])
= case ds7 of {
[] -> GHC.Types.: @[Int] (GHC.Types.: @Int y1 y);
: q l ->
case x1 of wild9 { GHC.Types.I# x2 ->
case q of { GHC.Types.I# y2 ->
case GHC.Prim./=# x2 y2 of {
__DEFAULT -> ds6;
1# ->
case d of { GHC.Types.I# y3 ->
case GHC.Prim./=#
x2 (GHC.Prim.+# y2 y3)
of {
__DEFAULT -> ds6;
1# ->
case GHC.Prim./=#
x2 (GHC.Prim.-# y2 y3)
of {
__DEFAULT -> ds6;
1# ->
jump safe
wild9
(GHC.Types.I#
(GHC.Prim.+# y3 1#))
l
}
}
}
}
}
}
}; } in
jump safe y1 lvl2 y
```
```
Rec {
-- RHS size: {terms: 49, types: 18, coercions: 0, joins: 0/0}
safe :: Int -> Int -> [Int] -> Bool
[GblId, Arity=3, Str=<ML><ML><1L>, Unf=OtherCon []]
safe
= \ (x :: Int) (d :: Int) (ds :: [Int]) ->
case ds of {
[] -> GHC.Types.True;
: q l ->
case x of wild1 { GHC.Types.I# x1 ->
case q of { GHC.Types.I# y ->
case GHC.Prim./=# x1 y of {
__DEFAULT -> GHC.Types.False;
1# ->
case d of { GHC.Types.I# y1 ->
case GHC.Prim./=# x1 (GHC.Prim.+# y y1) of {
__DEFAULT -> GHC.Types.False;
1# ->
case GHC.Prim./=# x1 (GHC.Prim.-# y y1) of {
__DEFAULT -> GHC.Types.False;
1# -> safe wild1 (GHC.Types.I# (GHC.Prim.+# y1 1#)) l
}
}
}
}
}
}
}
end Rec }
```
Demand analysis
```
let xs {- one-occ -} = go ys in case b of
A -> xs
B -> h xs
C -> h (2*xs)
D -> Just (case xs of ...) }
```
`h` may use its argument many times; but it's fine to inline `xs` at both its use sites.
TL;DR: souped up occurrence analysis
* Subsumes exitification
* Is better than exitification (queens ds6)
* Does the other examples in #22274
# Paper
## Syntax
- Abandoned φ (DmdEnv), it's all demand profile π now, a total map `Var -> Demand`
- New notation for Terminators b < ; < t
```
f = \x. x -- AbsVal \x.{x:->1#Xf};
Call (f y)
Var occ of f: {f:->1#X}\x.{x:->1#X}
Do beta thing {y:->X};
T[[ {y:->Xf} ]] Xc
```
Looks fine
```
const = \x y. x -- AbsVal \x y.{x:->1#X}
Call (const a b)
Var occ of const: {const:->1#X}\x y.{x:->1#X}
beta a: {const:->1#X}\y.{a:->1#X}
and then transform that
T[[ {const:->1#X}\y.{a:->1#X} ]] X = {const:->1#X} + T [[ \y.{a:->1#X} ]] X
T[[ \y.{a:->1#X} ]] X = let (n,sd) = Ap^-1[X] in {a:->n#sd}
dmdAnal const (Ap[1,Ap[1,X]])
sd ::= ... | symsd
symsd ::= X | App-1 symsd | ...
```
Hoping for
```
dmdAnal :: Env -> Expr -> AbsExpr
```
When analysing a call `(e x)` we know that in every evaluation, `e` is called with one argument. That suggests
```
dmdAnal :: Env -> Expr -> SymSubDmd -> AbsExpr
```
We start with `dmdAnal env e X` but
```
dmdAnal env (App e1 e2) ssd = let .. = dmdAnal env e1 (Call ssd)
```
Tracking incoming subdemand (as in GHC today) but with X in the corner.
## Why demand variables without "worst possible `SubDemand`" is not enough
See new analysis function F and transformer T.
What to do with X in T??? Also Ap^-1 and Cs^-1
SG's preferred fix: Store the worst possible sub-demand in X. Then it's possible to compute
## Idea: Abstract values for arguments
See the Note
## TODO/To be explained later:
* Sel does not support case-binders and default branches. Yet; think about adding.
* Demand case of T needs thought (line 239)
## Discussion
Google Drive
Gist
Clipboard
Sign in with Wallet
