---
tags: mir, rustc
---

# Virtual locals scheme

Right now, places in MIR can have an infinite number of [projections](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/enum.ProjectionElem.html). These projections contain not just offset projections like

* field
* const index
* downcast (to enum variant)

but also

* `Deref` projections, which are problematic in several places, because they often require splitting the projection lists at the deref projections and running logic for the part between the derefs.
* `Index` projections, which are problematic because the *index* is a `Local` (in addition to the place's base `Local`), which makes `Index` the only projection that depends on a runtime value

We propose to eliminate place projections entirely, and instead have an `Rvalue::Project` for the static projections and custom `Rvalue`s for the other projections. If we did this the trivial way, basically expanding

let y = &x.field[42];

to

let y = &x.field;
let y = &y[42];

we would break the (successfully compiling on stable) code:

struct Foo {
    x: u32,
    y: u32
}

fn main() {
    let foos: &mut [Foo] = &mut [Foo { x: 0, y: 0 }, Foo { x: 0, y: 0 }];
    let p = &mut foos[0].x;
    let q = &mut foos[0].y;
    *q += 1;
    *p += 1;
}

which only works because borrowck is smart enough to figure out that `&mut foos[0].x` and `&mut foos[0].y` can't overlap (side note: this actually ignores the index, because that could be a runtime value, the decision is solely made on the fact that `x` and `y` are distinct fields). We could teach borrowck to just understand the expansion into single projections, but that is [essentially impossible without polonius](https://github.com/rust-lang/rust/issues/71265#issuecomment-621219223), so we're shelving that. Additionally the split into static and weird (deref/index) projections makes the weirdness explicit in all use sites, making our life easier because we don't accidentally overlook any special cases.

Thus, we propose to add virtual locals that don't actually have any own memory, but which are temporary variables for storing places. So we can transform our earlier example

let y = &x.field[42];

to

place a = x.field;
place b = a[42];
let y = &b;

In contrast to regular assignments, these assignments only work if the RHS is a place, you can't assign values. We would introduce a new MIR `StatementKind`: `StatementKind::Project`, which is like `StatementKind::Assign`, but the destination must be a `Local` and the value must be a `Local` + `ProjectionElem`. When we split `ProjectionElem`, we can reuse that split in the hypothetical `Rvalue::Projection`.

# How does this affect backends?

* miri: trivial, we just treat the special locals as real locals of pointer to actual type instead of the actual type. Each `StatementKind::Project` just behaves like `StatementKind::Assign` with an `Rvalue::Ref`. This will make all the stacked borrows logic work out, because miri already supports the case where we'd do the trivial split-to-locals transformation on projections.
* llvm
* ignore all virtual locals until an `Rvalue` refers to one. Then walk back in the current block (virtual locals can only be referred to from their current block) and collect the necessary data. Since virtual locals are always a linear chain, this should be very close to the currently processed statement and thus be very cheap.
* alternatively: build up the llvm projections as the virtual locals are being encountered and just take them out of a store whenever they are referenced.

# How does this affect algorithms?

Most notably, borrowck will need to be adjusted to be able to handle these projections. Since all we did is flatten a vector of projections into the statement list of the current block by creating single-element projections, we can do something similar to the llvm projection thing and build up our borrow knowledge as we encounter the `StatementKind::Project`. Since we know for a fact that these projections can only be a linear chain of projections, we can ignore all of the complex cases that would be able to occur if we had a general version of this.