CSE doesn't correctly handle shadowing.
Here is the relevant core input:
join {
exit_X2 :: Int# -> Array Int ()
exit_X2 (wild_X1 :: Int#)
= case $windexError
showSignedInt l_a12J u_a12K (I# wild_X1) (unpackCString# "Int"#)
of wild_00 {
} } in
joinrec {
go3_a1fA :: Int# -> State# RealWorld -> Array Int ()
go3_a1fA (x_a1fB :: Int#) (eta_B0 :: State# RealWorld)
= case x_a1fB of wild_X1 {
__DEFAULT ->
join {
$j_X2 :: Array Int ()
$j_X2 = jump exit_X2 wild_X1 } in
case <=# 1# wild_X1 of { ... };
1# -> jump go3_a1fA 2# eta_B0
}; } in
The tricky part here is that the first X2 exit_X2
and the second X2 $j_X2
have the same unique! It gets even tricker as the first exit_X2
is mentioned in the body of $j_X2
however X2
in this context refers to exit_X2
not $j_X2
.
While is this a very rare combination it's valid core.
CSE get's this wrong however.
After CSE we end up with this:
join {
exit_X2 :: Int# -> Array Int ()
exit_X2 (wild_X1 :: Int#)
= ... } in
joinrec {
go3_a1fA (x_a1fB :: Int#) (eta_B0 :: State# RealWorld)
= case x_a1fB of wild_X1 {
__DEFAULT ->
join {
$j_X6 :: Array Int ()
$j_X6 = jump $j_X6 x_a1fB }
in
....
However $j_X6 = jump $j_X6 x_a1fB
is neither correct nor does it compile as $j_X6
isn't in scope in $j_X6
s rhs. (Thankfully!)
This is because CSE is subtly broken. We have:
cseBind :: TopLevelFlag -> CSEnv -> CoreBind -> (CSEnv, CoreBind)
cseBind toplevel env (NonRec b e)
= (env2, NonRec b2 e2)
where
(env1, b1) = addBinder env b
(env2, (b2, e2)) = cse_bind toplevel env1 (b,e) b1
addBinder
is essentially substBndr
, we rename $j_X2
to $j_X6
and then in cse_bind
we process the rhs:
cse_bind :: TopLevelFlag -> CSEnv -> (InId, InExpr) -> OutId -> (CSEnv, (OutId, OutExpr))
cse_bind toplevel env (in_id, in_rhs) out_id
...
| Just arity <- isJoinId_maybe in_id
-- See Note [Look inside join-point binders]
= let (params, in_body) = collectNBinders arity in_rhs
(env', params') = addBinders env params
out_body = tryForCSE env' in_body
in (env, (out_id, mkLams params' out_body))
...
The problem is that we process the rhs with the substitution X2 -> $j_X6
active.
So in the rhs of $j_X2 = jump exit_X2 wild_X1
we end up replacing exit_X2
with $j_X6
because the code assumes it refers to $j_X2
. And we end up with $j_X6 = jump $j_X6 wild_X1
. In short it's a mess.
I think the solution is that we need to use addBinder
after we processed the rhs instead of before. Unless it's a recursive binder. This shouldn't be hard to fix I will write a patch.