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.

[lqd]

@nnethercote there's also #53643 (comment) for dealing with this ucd case

[pnkfelix]

NLL pre-meeting triage. This is an important topic (i.e. P-high) that some folks from both NLL and MIR 2.0 groups are looking at; but its not NLL specific at all, so I'm removing the NLL related tags.

[nnethercote]

One disadvantage of this change: the size of Place increases from 16 bytes to 24 bytes (on 64-bit platforms). This also increases the minimum size of mir::Statement by 8 bytes, and that's a type that contributes to peak memory usage, via BasicBlockData::statements.

[spastorino]

@nnethercote the change is not going to be done in the way stated in this issue.

The idea is to do something like ...

struct Place {
    base: PlaceBase,
    projection: PlaceProjection,
}
enum PlaceProjection {
    Base,
    Projection(Box<PlaceProjection>),
    Deref,
    Index(..),
    ...
}

[spastorino]

@nnethercote the change is not going to be done in the way stated in this issue.

The idea is to do something like ...

struct Place {
    base: PlaceBase,
    projection: PlaceProjection,
}
enum PlaceProjection {
    Base,
    Projection(Box<PlaceProjection>),
    Deref,
    Index(..),
    ...
}

[nnethercote]

That sounds even worse, in terms of size :(

IIUC Place would be at least 32 bytes in that case -- PlaceBase is 16 bytes, and PlaceProjection would be at least 16 bytes.

[nnethercote]

BTW, you can measure the size of types within rustc quite easily. See the "extra-special trick" here for instructions.

[spastorino]

Yes, sorry. I've pasted an intermediate step. The final layout is ...

struct Place<'tcx> {
    base: PlaceBase,
    projection: &'tcx [PlaceProjection],
}
enum PlaceProjection {
    Projection(Box<PlaceProjection>),
    Deref,
    Index(..),
    ...
}

[pnkfelix]

The described final layout still implies that Place is increasing from 16- to 24-bytes in size on 64-bit platforms. (Just trying to save @nnethercote the effort of repeating the original comment).

But I prefer to wait to see the final result and do some measurements on it before we worry about trying to address this in some manner.

[spastorino]

@pnkfelix yes, final layout will be 24-bytes. Sorry because I was adding some confusion around. See @eddyb comment here #58631 (comment)

[pnkfelix]

I'm happy to see work continue here, but I do not think the P-high priority makes sense. (Neither I nor the team needs to revisit the progress on this topic every week during the triage meeting.)

Revising to P-medium.

[spastorino]

@oli-obk @nikomatsakis should we close this issue?, there are a bunch of things to do about MIR 2.0 but tracked elsewhere. If I'm not wrong everything proposed in this issue is already implemented.

[nikomatsakis]

I think that's right. Closing!