[nll] teach SCC about 'static

[nikomatsakis]

Right now, if you have a region R where R: 'static, the SCC computation in NLL is not aware that this means that R = 'static. If we taught it that 'static: R for all R, though, it would put them in the same SCC. This might be a big win for things like html5ever, as it would collapse almost all the regions into one big SCC. (I was doing some profiling on html5ever using the branch from #53177, and it seemed like this would help further drop the overhead.)

[nikomatsakis]

@wesleywiser is going to take a look at this

[nikomatsakis]

Here are some relevant links.

This is where we compute the SCCs:

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

Line 237 in 63fe441

let constraint_sccs = Rc::new(constraints.compute_sccs(&constraint_graph));

This is the definition of that method:

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

Lines 50 to 56 in 63fe441

	crate fn compute_sccs(
	&self,
	constraint_graph: &graph::ConstraintGraph,
	) -> Sccs<RegionVid, ConstraintSccIndex> {
	let region_graph = &graph::RegionGraph::new(self, constraint_graph);
	Sccs::new(region_graph)
	}

It takes a ConstraintSet:

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

Lines 21 to 24 in 63fe441

	#[derive(Clone, Default)]
	crate struct ConstraintSet {
	constraints: IndexVec<ConstraintIndex, OutlivesConstraint>,
	}

as well as a ConstraintGraph, from which it builds a RegionGraph:

rust/src/librustc_mir/borrow_check/nll/constraints/graph.rs

Lines 72 to 75 in 63fe441

	crate struct RegionGraph<'s> {
	set: &'s ConstraintSet,
	constraint_graph: &'s ConstraintGraph,
	}

The RegionGraph has an edge R1 -> R2 if there is a constraint R1: R2. This is defined by this trait impl:

rust/src/librustc_mir/borrow_check/nll/constraints/graph.rs

Lines 122 to 129 in 63fe441

	impl<'s> graph::WithSuccessors for RegionGraph<'s> {
	fn successors<'graph>(
	&'graph self,
	node: Self::Node,
	) -> <Self as graph::GraphSuccessors<'graph>>::Iter {
	self.sub_regions(node)
	}
	}

To make the change, I think we want to supply an altered graph that adds additional edges. We know that (by definition) 'static: 'a for any region 'a. So basically we might extend region_graph so that, in the successors method, it checks if the region is 'static. If so, it just returns an iterator over every region. Otherwise, it returns the existing code.

Note that a lot of this code changes in my PR #53177 -- in particular, the graph is now parameterized so that R1: R2 can also mean an edge R1 <- R2 (a "reverse" edge). If we are in reverse, you would rather want to add 'static as an "extra successor" to every region. Alternatively, we could define an "augmented region graph" that only works for "normal" region graphs, since we only care for this extra edge when doing the SCC computation.

[nikomatsakis]

Zulip topic: https://rust-lang.zulipchat.com/#narrow/stream/122657-wg-nll/topic/.2353178.20optimize.20SCC.20computation