Description
A while back I was discussing Storage{Live,Dead}
and dominators, with @tmandry (in the context of generator layout optimizations), and came to the conclusion that StorageLive
pretty much has to dominate all uses (I doubt we ever added a check that it does so, though).
More recently, I was trying to figure out what the simplest "StorageLive
sinking" (i.e. moving the statement "later" in the CFG) optimization we could do was.
The conclusion I came to was that we might not need StorageLive
at all, because there might be a deterministic "best placement" we could compute (assuming we need exactly one llvm.lifetime.start
per alloca
).
That best placement would be the least (common) dominator of all mentions of a MIR local.
Even indirect accesses require a direct borrow beforehand, so this should cover everything.
(Assuming that, given CFG points x
, y
, z
, "x
is a common dominator of y
and z
" means "x
dominates both y
and z
", i.e. "to reach either y
or z
you must go through x
first", and the "least" such x
is the one not dominating other common dominators of y
and z
, i.e. it's "the closest to y
and z
")
This could be:
- just before the single assignment of that local
let x = x + y;
- at the end of a block branching into paths which all assign that local
let x = if c { a } else { b };
let x; if c { x = a; } else { x = b; }
(roughly equivalent)
I am not sure about interactions with loops, though.
But this doesn't have to remain theoretical, we could compute this "ideal StorageLive
position" and then compare it with the existing one (presumably one would dominate the other? not sure this would catch any loop issues though).
StorageDead
could also be similar ("least (common) post-dominator"?).
However, it also has the effect of invalidating borrows, so we would need to keep an InvalidateBorrows(x)
statement around, and consider it one of the mentions of x
.
Then "Storage{Live,Dead}
range shrinking" would simply boil down to hoisting InvalidateBorrows(x)
up past statements which couldn't indirectly access x
.
cc @nikomatsakis @ecstatic-morse @rust-lang/wg-mir-opt