change how MIR represents places

[nikomatsakis]

For efficiency reasons, but also others, it would be nice to change how MIR represents the Place data structure. Right now we have a tree-like structure:

rust/src/librustc/mir/mod.rs

Lines 1694 to 1709 in fefe816

	/// A path to a value; something that can be evaluated without
	/// changing or disturbing program state.
	#[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
	pub enum Place<'tcx> {
	/// local variable
	Local(Local),
	/// static or static mut variable
	Static(Box<Static<'tcx>>),
	/// Constant code promoted to an injected static
	Promoted(Box<(Promoted, Ty<'tcx>)>),
	/// projection out of a place (access a field, deref a pointer, etc)
	Projection(Box<PlaceProjection<'tcx>>),
	}

But this is not the most convenient and it can be an efficiency hazard. Instead, I propose a structure like this (inspired by something @eddyb said, and I imagine that they will have suggestions too):

struct Place<'tcx> {
    base: PlaceBase<'tcx>,
    elem: &'tcx Slice<ProjectionElem<'tcx>>,
}

enum PlaceBase<'tcx> {
    /// local variable
    Local(Local),

    /// static or static mut variable
    Static(Box<Static<'tcx>>),

    /// Constant code promoted to an injected static
    Promoted(Box<(Promoted, Ty<'tcx>)>),
}

where ProjectionElem is basically the same type as today:

rust/src/librustc/mir/mod.rs

Lines 1734 to 1770 in fefe816

	#[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
	pub enum ProjectionElem<'tcx, V, T> {
	Deref,
	Field(Field, T),
	Index(V),
	/// These indices are generated by slice patterns. Easiest to explain
	/// by example:
	///
	/// ```
	/// [X, _, .._, _, _] => { offset: 0, min_length: 4, from_end: false },
	/// [_, X, .._, _, _] => { offset: 1, min_length: 4, from_end: false },
	/// [_, _, .._, X, _] => { offset: 2, min_length: 4, from_end: true },
	/// [_, _, .._, _, X] => { offset: 1, min_length: 4, from_end: true },
	/// ```
	ConstantIndex {
	/// index or -index (in Python terms), depending on from_end
	offset: u32,
	/// thing being indexed must be at least this long
	min_length: u32,
	/// counting backwards from end?
	from_end: bool,
	},
	/// These indices are generated by slice patterns.
	///
	/// slice[from:-to] in Python terms.
	Subslice {
	from: u32,
	to: u32,
	},
	/// "Downcast" to a variant of an ADT. Currently, we only introduce
	/// this for ADTs with more than one variant. It may be better to
	/// just introduce it always, or always for enums.
	Downcast(&'tcx AdtDef, usize),
	}

In other words, instead of representing a.b.c as

• .c
  • .b
    • .a

we would represent it as (a, [b, c]) (here, [b, c] would be an interned slice).

The advantages of this setup:

• Place is now Copy, which is always nice
• You can figure out very quickly that a.b.c is disjoint from d.e.f
  • Right now we have to use these unroll_place calls

And it is a building block, I think, for other improvements to NLL performance.

cc @eddyb

[nnethercote]

For html5ever at least, there are zillions of calls to unroll_place but the Place chains are very shallow (typically 1, I think). I could be wrong, but I think it's the number of calls that's the real problem, rather than the representation.

[nikomatsakis]

@nnethercote ok, good to know. I intended this as a first step -- the second step would be to index the borrows by their initial variable, so that we avoid the N^2 iteration and replace it with effectively a hashing scheme

[eddyb]

Ohhh, using an interned slice there is really clever! I don't see any issues with it.

[nnethercote]

Note: unroll_place is no longer hot for html5ever with NLL. However, it is very hot for keccak with NLL, accounting for roughly 10% of execution, according to Cachegrind's instruction counts.

[nikomatsakis]

I'm marking this as NLL-deferred -- not because I don't want to see it done, but because I don't think it quite rises to the level of a milestone issue. @csmoe is still hard at work here though as far as I know!

[nnethercote]

unroll_place is no longer hot for keccak with HTML. However, it's incredibly hot for the new ucd benchmark. I was able to avoid a lot of the calls with a quick hack in #53733, but the remaining calls still take up about 50% of the entire execution time of a non-NLL ucd-check run. Changing the representation is probably necessary to make ucd's compile time reasonable.

Based on this I recommend that the NLL-deferred label be removed.