consider optimizing how NLL region inference works to use bit sets

[nikomatsakis]

Right now, the main loop of NLL region inference actually performs a lot of depth-first searches across the control-flow graph:

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

Lines 468 to 494 in 0f9c784

	while changed {
	changed = false;
	debug!("propagate_constraints: --------------------");
	for constraint in &self.constraints {
	debug!("propagate_constraints: constraint={:?}", constraint);
	// Grow the value as needed to accommodate the
	// outlives constraint.
	let Ok(made_changes) = self.dfs(
	mir,
	CopyFromSourceToTarget {
	source_region: constraint.sub,
	target_region: constraint.sup,
	inferred_values: &mut inferred_values,
	constraint_point: constraint.point,
	constraint_span: constraint.span,
	},
	);
	if made_changes {
	debug!("propagate_constraints: sub={:?}", constraint.sub);
	debug!("propagate_constraints: sup={:?}", constraint.sup);
	changed = true;
	}
	}
	debug!("\n");
	}

Basically, if we have a relation that R1: R2 @ P, then we do a depth-first search in the control-flow graph, starting at P; so long as the nodes we visit are members of R2, we add that node into R1 (if not already present). That code is in dfs.rs:

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

Lines 46 to 89 in 0f9c784

	stack.push(op.start_point());
	while let Some(p) = stack.pop() {
	let point_index = self.elements.index(p);
	if !op.source_region_contains(point_index) {
	debug!(" not in from-region");
	continue;
	}
	if !visited.insert(p) {
	debug!(" already visited");
	continue;
	}
	let new = op.add_to_target_region(point_index)?;
	changed |= new;
	let block_data = &mir[p.block];
	let start_stack_len = stack.len();
	if p.statement_index < block_data.statements.len() {
	stack.push(Location {
	statement_index: p.statement_index + 1,
	..p
	});
	} else {
	stack.extend(block_data.terminator().successors().iter().map(
	|&basic_block| {
	Location {
	statement_index: 0,
	block: basic_block,
	}
	},
	));
	}
	if stack.len() == start_stack_len {
	// If we reach the END point in the graph, then copy
	// over any skolemized end points in the `from_region`
	// and make sure they are included in the `to_region`.
	changed |= op.add_universal_regions_outlived_by_source_to_target()?;
	}
	}

(There is also a bit of special treatment around the exit from the CFG.)

This is pretty naive. I think what we should be doing is probably more like this:

1. Compute a reachability relation as a big BitMatrix (there exists code to do this already in librustc_data_structures).
   • If a point P can reach the end point, include the free regions in the reachability set.
2. For a relation R1: R2 @ P, we can then intersect reachable(P) with R2 to get "those members of R2 reachable from P".
   • Does this work? There might be some danger of R2 containing a point that is reachable from P, but not without leaving R2, and which hence should not be included?

Anyway, before we do a specific solution, though, it'd be great to have some specific benchmarks.

[nikomatsakis]

Hmm, so I suspect we can do something smart like this, but just replacing the DFS with a bit-set intersection certainly won't work. I don't have an actual Rust example where it goes wrong, but it seems clear that if you have R1: R2 @ P and R2 has you can have things that are both reachable from P and contained within R2. It may be that it's better to just do a dirty list (#47602) and/or maybe use some caching (e.g., cache the bitset for R2 @ P for reuse).

[chrisvittal]

I'll take a look at this.

[nikomatsakis]

The latest profiles seem to suggest that DFS is not just not expensive.