Skip to content

StorageLive (and even StorageDead) may be unnecessary in MIR. #68622

Open
@eddyb

Description

@eddyb

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-MIRArea: Mid-level IR (MIR) - https://blog.rust-lang.org/2016/04/19/MIR.htmlC-cleanupCategory: PRs that clean code up or issues documenting cleanup.T-compilerRelevant to the compiler team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions