[nll] remove duplicate outlives edges

[nikomatsakis]

Solving region constraints currently accounts for 8% of MIR borrowck time in clap-rs. However, we are doing more work than we need to do. This part of the inference engine processes outlives constraints like 'a: 'b, which says that the region 'a outlives 'b and therefore should be a superset of the points in 'b. To process such a constraint we therefore take all the points in 'b and add them to 'a:

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

Lines 246 to 250 in 2808460

	/// Add all elements in `r_from` to `r_to` (because e.g. `r_to:
	/// r_from`).
	pub(super) fn add_region(&mut self, r_to: RegionVid, r_from: RegionVid) -> bool {
	self.matrix.merge(r_from, r_to)
	}

You can see therefore that a constraint like 'a: 'a is pretty uninteresting. It is also uninterested to have two of the same constraints ('b: 'c, 'b: 'c), since processing the first one will also solve the second one.

However, a cursory examination of the constraints from many examples reveals that we have both a lot of duplicates and a lot of X: X identity constraints. I find about ~30% of the constraints are duplicated.

Part of the reason for this is that, in the original NLL proposal and in Polonius, we distinguished not only 'a: 'b but also the location where it occurs ('a: 'b @ P). We are no longer using this P information so it would be good to discard it (and the next gen region inference engine, polonius, uses a different data structures for its constraints anyway). (Interestingly, even if we take the location P into account, it is still true that most of the constraints are duplicated, so there is likely a win here waiting for polonius as well at some future point.)

The constraints in question are instances of this struct:

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

Lines 120 to 146 in 2808460

	#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
	pub struct OutlivesConstraint {
	// NB. The ordering here is not significant for correctness, but
	// it is for convenience. Before we dump the constraints in the
	// debugging logs, we sort them, and we'd like the "super region"
	// to be first, etc. (In particular, span should remain last.)
	/// The region SUP must outlive SUB...
	pub sup: RegionVid,
	/// Region that must be outlived.
	pub sub: RegionVid,
	/// At this location.
	pub point: Location,
	/// Later on, we thread the constraints onto a linked list
	/// grouped by their `sub` field. So if you had:
	///
	/// Index | Constraint | Next Field
	/// ----- | ---------- | ----------
	/// 0 | `'a: 'b` | Some(2)
	/// 1 | `'b: 'c` | None
	/// 2 | `'c: 'b` | None
	pub next: Option<ConstraintIndex>,
	/// Where did this constraint arise?
	pub span: Span,

They are stored in a vector here:

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

Lines 70 to 71 in 2808460

	/// The constraints we have accumulated and used during solving.
	constraints: IndexVec<ConstraintIndex, OutlivesConstraint>,

Most elements of this vector I believe are given in RegionInferenceContext::new:

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

Line 272 in 2808460

constraints: IndexVec::from_raw(outlives_constraints),

but some are later added via add_outlives:

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

Lines 390 to 407 in 2808460

	/// Indicates that the region variable `sup` must outlive `sub` is live at the point `point`.
	pub(super) fn add_outlives(
	&mut self,
	span: Span,
	sup: RegionVid,
	sub: RegionVid,
	point: Location,
	) {
	debug!("add_outlives({:?}: {:?} @ {:?}", sup, sub, point);
	assert!(self.inferred_values.is_none(), "values already inferred");
	self.constraints.push(OutlivesConstraint {
	span,
	sup,
	sub,
	point,
	next: None,
	});
	}

The initial vector is populated by the MIR type check in this call here:

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

Lines 759 to 768 in 7008a95

	if let Some(borrowck_context) = &mut self.borrowck_context {
	constraint_conversion::ConstraintConversion::new(
	self.mir,
	borrowck_context.universal_regions,
	borrowck_context.location_table,
	&mut self.constraints.outlives_constraints,
	&mut self.constraints.type_tests,
	&mut borrowck_context.all_facts,
	).convert(locations, &data);
	}

So to solve this problem we would want to detect duplicates somehow, probably taking just sub+sup into account. The only reason to also include the location is that it may be useful in reporting errors later. It probably makes sense to do this by adding a FxHashSet<(RegionVid, RegionVid)> to detect duplicates, though it might make sense to extract the vector itself from both the RegionInferenceContext and the MIR type check into a common data structure (OutlivesConstraintSet or something) that keeps the FxHashSet and the Vec in one.

[nikomatsakis]

@Eh2406 is working on this

[Eh2406]

I was thinking, always dangerous, from the way you described things the field pub point: Location, is not important any more. Would it be a good cleanup to just remove it?

[nikomatsakis]

Fixed, basically.

[pnkfelix]

(for more info, read the comments on #51855; in particular, it seems like fixing this did not have as large a win as we expected, because the fn merge operation already detects self loops as a special case.)