"invert" borrow computation

[nikomatsakis]

I think we can make the process of checking borrows more efficient. Right now, we use a dataflow computation to compute the "borrows in scope" at each point. Then we walk over the MIR. At each point, whenever we access a path P1, we execute over the borrows in scope and look for any which conflict with P1. If we find any, we report an error.

I think what we should do instead is this: walk over all the borrows. For each borrow, do a DFS from the point of the borrow. Stop the DFS when we either (a) exit the borrow region or (b) detect that the path which was borrowed was overwritten. (We already do a very similar computation.) During that DFS, we look at the paths that are accessed by each statement we traverse, and check if they conflict with the borrow. (This will require us to efficiently index the paths that are accessed by a given location.)

This is a non-trivial amount of refactoring but I think it will be a win. We're already doing the DFS as part of the precompute_borrows_out_of_scope routine -- the only difference is that now we'll be checking the paths accessed by each statement as we go. But we can make that efficient by using a simple hashing scheme like the one described in #53159.

In exchange, we get to avoid doing an extra dataflow computation. This means one less dataflow to do and also one less thing to update.

[nikomatsakis]

Some notes on how NLL region computation is working today. After we finish computing the values of regions, we do a separate dataflow computation to compute the "borrows in scope" at each point:

rust/src/librustc_mir/borrow_check/mod.rs

Lines 224 to 232 in d5a448b

	let flow_borrows = FlowAtLocation::new(do_dataflow(
	tcx,
	mir,
	id,
	&attributes,
	&dead_unwinds,
	Borrows::new(tcx, mir, regioncx.clone(), def_id, body_id, &borrow_set),
	|rs, i| DebugFormatted::new(&rs.location(i)),
	));

The dataflow definition is very simple: it has a single "gen" bit -- each assignment x = &'r y will gen the bit for that particular borrow:

rust/src/librustc_mir/dataflow/impls/borrows.rs

Line 257 in d5a448b

sets.gen(&index);

The kill bits occur in two cases. First, when we execute the region 'r of the borrow. Second, when we overwrite the path that was borrowed (e.g., y = ...).

To handle the first case -- detecting the points where borrows go out of scope -- we execute precompute_borrows_out_of_scope:

rust/src/librustc_mir/dataflow/impls/borrows.rs

Lines 130 to 132 in d5a448b

	precompute_borrows_out_of_scope(mir, &nonlexical_regioncx,
	&mut borrows_out_of_scope_at_location,
	borrow_index, borrow_region, location);

This function does a depth-first search from the point of each borrow. The DFS stops whenever we reach a point that is not contained within the region of the borrow. It updates this borrows_out_of_scope_at_location map at the "borders" of the borrow -- basically, at each point where we exit the borrow region.

[nikomatsakis]

I'm going to drop this in priority -- my assessment is that this is not a major driver for the current bottlenecks in perf.

[nikomatsakis]

@spastorino I'm also unassigning you -- not because I don't want you to do it :) but rather because (afaik) you've not started and there might be higher priority items. We can always reassign.

[spastorino]

@nikomatsakis 👍, I was planning on work on this meanwhile I was stuck with the move outs computation lazily task, but ended with a lot of issues on my travel back and never got into the task. So 👍, and even more if there's more important stuff to do 😄

[arielb1]

I thought that back in the day we said it is possible to use an "SSA-graph" (i.e. iterated dominance frontier) based computation to propagate borrows in basically linear-in-CFG-size time, instead of the quadratic+heuristic time that is taken today.

[nikomatsakis]

Good point @arielb1 =) I have to think about that. Still, it may not be worth doing much here unless we want it in the short term. In particular, when we move to polonius, the architecture here will change and I don't know if we'll be doing this same analysis at all.

[nikomatsakis]

Removing from the milestone list. Doesn't feel like a blocker.

[arielb1]

In particular, when we move to polonius, the architecture here will change and I don't know if we'll be doing this same analysis at all.

I suspect that a similar SSA-style transformation would speed up polonius too, because it will allow the same skipping of "uninteresting CFG points".

[pnkfelix]

NLL premeeting triage. we are better off waiting until we've made more progress on Polonius before we invest much effort here. P-medium