[nll] make causal tracking lazy

[nikomatsakis]

Analyzing profiles on my latest branch, it appears that approximately 4% of total compilation time is spent managing the "causal hash map":

rust/src/librustc_mir/borrow_check/nll/region_infer/values.rs

Lines 187 to 191 in 01dbfda

	/// If cause tracking is enabled, maps from a pair (r, e)
	/// consisting of a region `r` that contains some element `e` to
	/// the reason that the element is contained. There should be an
	/// entry for every bit set to 1 in `SparseBitMatrix`.
	causes: Option<CauseMap>,

Currently, that map is only non-None for the "liveness" set, which stores, for each region variable R, each point P where R is directly live (meaning typically that there is some local variable X that has R in its type and which may be used at some point Q reachable from P). The "cause" tracks basically this point Q. It's accessed later when constructing error messages, here:

rust/src/librustc_mir/borrow_check/nll/region_infer/mod.rs

Lines 1067 to 1068 in 01dbfda

	// then return why `Y` was live at `elem`
	self.liveness_constraints.cause(region_sub, elem)

We should remove the causal hashmap altogether. Instead, when constructing an error, we can do a BFS over the MIR graph from elem (a Location), looking for points that may use the region region_sub that we are interested in.

[nikomatsakis]

cc @rust-lang/wg-compiler-nll -- possible 4% win

[nikomatsakis]

Here is a thread for chatting about this on zulip:

https://rust-lang.zulipchat.com/#narrow/stream/122657-wg-nll/topic/issue-51710-lazy-causal-tracking

[nikomatsakis]

So on Zulip @spastorino pointed out to me that we already have the BFS I described:

rust/src/librustc_mir/borrow_check/nll/explain_borrow/mod.rs

Lines 128 to 170 in 612c280

	fn find_regular_use<'gcx, 'tcx>(
	mir: &'gcx Mir,
	regioncx: &'tcx RegionInferenceContext,
	borrow: &'tcx BorrowData,
	start_point: Location,
	local: Local,
	) -> Option<Location> {
	let mut uf = UseFinder {
	mir,
	regioncx,
	borrow,
	start_point,
	local,
	liveness_mode: LivenessMode {
	include_regular_use: true,
	include_drops: false,
	},
	};
	uf.find()
	}
	fn find_drop_use<'gcx, 'tcx>(
	mir: &'gcx Mir,
	regioncx: &'tcx RegionInferenceContext,
	borrow: &'tcx BorrowData,
	start_point: Location,
	local: Local,
	) -> Option<Location> {
	let mut uf = UseFinder {
	mir,
	regioncx,
	borrow,
	start_point,
	local,
	liveness_mode: LivenessMode {
	include_regular_use: false,
	include_drops: true,
	},
	};
	uf.find()
	}

I think this perhaps suggests a simpler way to achieve the same goal. What I originally described was that we would use the BFS to basically "reproduce" the same return value we have now -- but that return value isn't ideal.

Let's step back to explain how things work today. We have this function explain_why_region_contains_point(R, P). It has the job of figuring out why the point P is part of the region R. What we are returning now is a cause like LiveLocal(X, P1), which says that the variable X may contain a reference to data in region R -- or possibly in some other region R1 where R: R1 -- and that it is live at P1. But being live isn't the same as being used -- being live just means it will be used in the future. So then we do a BFS to find the point where it is used, since that is what we want to show to the user. If we naively integrated the BFS into the current setup, we would wind up with two BFS's. That is a bit silly.

I can see two ways forward:

• Move the BFS from where it is now into explain_why_region_contains_point. This is basically what I described. We would be searching then not for a specific local variable X but rather for uses of any local variable that contains region_sub (R1 in my description above). We would then return both the variable name (X) and the point where it is used (P). This simplifies the code later since it isn't finding out where X is live but rather where it is used.

• Leave the BFS where it is, but modify the return value so that it retuns region_sub. This is basically the same as the previous paragraph, just differs in the precise info returned by each function.

I guess I lean towards the former. Feels 'more right' -- explain_why_region_contains_point is just doing a better job of finding the answer.

[nikomatsakis]

This has a pending PR, marking as Preview 2.