[nll] hash borrows in scope for better performance

[nikomatsakis]

So I have an idea for how to improve performance in cases like html5ever where there are tons of borrows in scope at certain points. Right now, we have a pretty naive algorithm that implements over all borrows in scope:

rust/src/librustc_mir/borrow_check/path_utils.rs

Lines 40 to 52 in 18925de

	/// Encapsulates the idea of iterating over every borrow that involves a particular path
	pub(super) fn each_borrow_involving_path<'a, 'tcx, 'gcx: 'tcx, F, I, S> (
	s: &mut S,
	tcx: TyCtxt<'a, 'gcx, 'tcx>,
	mir: &Mir<'tcx>,
	_context: Context,
	access_place: (ShallowOrDeep, &Place<'tcx>),
	borrow_set: &BorrowSet<'tcx>,
	candidates: I,
	mut op: F,
	) where
	F: FnMut(&mut S, BorrowIndex, &BorrowData<'tcx>) -> Control,
	I: Iterator<Item=BorrowIndex>

I think we would do better if we stored the "borrows in scope" organized by the "root local" of the borrow:

rust/src/librustc_mir/borrow_check/place_ext.rs

Lines 20 to 23 in 18925de

	/// If this is a place like `x.f.g`, returns the local
	/// `x`. Returns `None` if this is based in a static.
	fn root_local(&self) -> Option<Local>;

In fact, I think we could do a "quick hack" to make this work. The BorrowSet already has an index of borrow indices based on their "root locals":

rust/src/librustc_mir/borrow_check/borrow_set.rs

Lines 44 to 45 in 18925de

	/// Map from local to all the borrows on that local
	crate local_map: FxHashMap<mir::Local, FxHashSet<BorrowIndex>>,

So what we can do is to modify each_borrow_involving_path. Instead of taking an iterator over borrows in scope, it would take some sort of is_borrow_in_scope: impl Fn(BorrowIndex) -> bool function. It would then find the root local (if any) of the access path, find all borrows that apply to that root local, and iterate over those, testing if each of them is in scope.

We could make this more efficient in many ways -- e.g., using bitsets and things -- but this basic change should already eliminate some of the horrible O(n^2) behavior.

[nikomatsakis]

This should be a big win for html5ever -- each_borrow_involving_path currently stands at 41% of borrowck time there!

[nikomatsakis]

This will likely not help html5ever as much once #53177 lands.

#53189 is also relevant, as it will also remove many uses of each_borrow_involving_path.

[nikomatsakis]

Zulip topic: https://rust-lang.zulipchat.com/#narrow/stream/122657-wg-nll/topic/.2353159.20hash.20borrows.20in.20scope