optimize the way that loans are killed in borrowck dataflow

[nikomatsakis]

Profiling reveals that kill_loans_out_of_scope_at_location is a pretty major hot spot. It is pretty naive right now: for each point, it iterates over all borrows to check if that point is included. In fact, it seems to do that twice (@davidtwco opened #50891 to deal with that).

I am not sure the best way to handle this computation. One option that is not theoretically better but seems likely to be much better in practice would be:

• Iterate over each borrow expression B, with associated region 'a:
  • For each borrow B, do a depth-first search starting at the location of the borrow
  • When this DFS reaches a point P that is not in 'a, end the walk, but add B to kill set for P

This is still O(n^2), but I think it seems likely to be much better in practice, and I can't think of a better way.

[nikomatsakis]

What we would want to do is to build up a side-index somewhere of type

Location -> Set<BorrowIndex>

with this being the set of borrows that go out of scope on entry to the location. We'd probably store this in the Borrows structure:

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

Line 42 in 21b5367

pub struct Borrows<'a, 'gcx: 'tcx, 'tcx: 'a> {

We'd presumably compute it in Borrows::new:

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

Lines 55 to 62 in 21b5367

	crate fn new(
	tcx: TyCtxt<'a, 'gcx, 'tcx>,
	mir: &'a Mir<'tcx>,
	nonlexical_regioncx: Rc<RegionInferenceContext<'tcx>>,
	def_id: DefId,
	body_id: Option<hir::BodyId>,
	borrow_set: &Rc<BorrowSet<'tcx>>
	) -> Self {