[nll] optimize redundant reborrows

[nikomatsakis]

When you have a borrow like this:

let x = &*y

where y: &T, then there is really no reason for the borrow checker to "record" the borrow or figure out its scope. The reason is that there is no action that one can do with y that would invalidate x. (Of course we still want to record the outlives relationship that forces y's lifetime to outlive x's lifetime.)

The old AST borrow checker did this same optimization. It ought to have a huge effect on html5ever: my profile measurements suggest that basically all of its time is spent with these very large borrow sets.

[nikomatsakis]

Let me leave a few notes here. I'm not 100% sure on what changes are needed, but this is the general vicinity.

We compute the "set of all borrows" into this BorrowSet data structure:

rust/src/librustc_mir/borrow_check/borrow_set.rs

Line 23 in ccb550f

crate struct BorrowSet<'tcx> {

In that data structure, we currently walk over the MIR and identify assignments of borrows (e.g., X = &<place>). For each of those, we allocate a borrow index... well, almost each of them. For some borrows, we don't bother -- in particular, borrows of "unsafe places":

rust/src/librustc_mir/borrow_check/borrow_set.rs

Lines 162 to 164 in ccb550f

	if borrowed_place.is_unsafe_place(self.tcx, self.mir) {
	return;
	}

An 'unsafe place' is something like the deref of a raw pointer:

https://github.com/rust-lang/rust/blob/master/src/librustc_mir/borrow_check/place_ext.rs#L27

I think we basically want to rename is_unsafe_place to something like ignore_borrow_of, and update the command like so:

/// Returns true if we can safely ignore borrows of this place.
/// This is true whenever there is no action that the user can do
/// to the place `self` that would invalidate the borrow. This is true
/// for borrows of raw pointer dereferents as well as shared references.
fn ignore_borrow_of(&self) -> bool {
    ...
}

then we will add [TyRef](https://doc.rust-lang.org/nightly/nightly-rustc/rustc/ty/enum.TypeVariants.html#variant.TyRef to this match here:

rust/src/librustc_mir/borrow_check/place_ext.rs

Lines 42 to 45 in ccb550f

	match ty.sty {
	ty::TyRawPtr(..) => true,
	_ => proj.base.is_unsafe_place(tcx, mir),
	}

Specifically, TyRef when the Mutability is MutImmutable.

[nikomatsakis]

So, I couldnt' help myself. I had a few minutes and that changed seemed so easy that I gave it a spin.