WorkWrap/FloatOut: Float out strictly unboxed free variables
Consider
f :: (Int,Int) -> Int -> Int
f _ 0 = 0
f x y = g y
where
g y = case x of
(p,q) -> if p+y > 0 then 0
else g (y-1)
Note that f
is not strict in x
, but g
is and doesn't even need the box. With -O
(in the absence of LiberateCase), we fail to float out and unbox x
:
f = \ (ds_d1pt :: (Int, Int)) (ds1_d1pu :: Int) ->
case ds1_d1pu of { GHC.Types.I# ds2_d1px ->
case ds2_d1px of ds3_X2 {
__DEFAULT ->
joinrec {
$wg_s1re [InlPrag=NOUSERINLINE[2], Occ=LoopBreaker]
:: GHC.Prim.Int# -> Int
[LclId[JoinId(1)], Arity=1, Str=<L> {d1pt->S!P(S!P(L),A)}, Unf=OtherCon []]
$wg_s1re (ww_s1rc :: GHC.Prim.Int#)
= case ds_d1pt of { (p_atY, q_atZ) ->
case p_atY of { GHC.Types.I# x_a1q0 ->
case GHC.Prim.># (GHC.Prim.+# x_a1q0 ww_s1rc) 0# of {
__DEFAULT -> jump $wg_s1re (GHC.Prim.-# ww_s1rc 1#);
1# -> Lib.f1
}
}
}; } in
jump $wg_s1re ds3_X2;
0# -> Lib.f1
}
}
Hence we keep on switching over it in $wg
instead of just closing over the unboxed x_a1q0
.
We float lazy work inside lambdas called at most once; hence we should also float strict work outside lambdas known to be called strictly and possibly many times.
I'm not sure what the best place to do this would be and it seems we lack the information of the outermost possible context in which x
is used strictly.
But given we had that information, or at least knew "x
is used strictly in the whole joinrec
", then
- We could do the transformation in WW, wrapping an unboxing case around the
joinrec
and rebox it in$wg
's body, or - We could tweak FloatOut so that it floats out
case x of (p,q) ->
ifx
is strict and unboxed.
Inspired by #22303. In traditional Dataflow analysis terms, strictness analysis is like very busy expression analysis and FloatOut is like the code hoisting transformation https://ethz.ch/content/dam/ethz/special-interest/infk/inst-cs/lst-dam/documents/Education/Classes/Fall2015/210_Compiler_Design/Slides/extra.pdf.