[nll] introduce dirty list to dataflow

[nikomatsakis]

I've been examining profiling results of the clap-rs test case (I am profiling the #51538 branch, more specifically). One clear hot spot is the do_dataflow, which accounts for 18% of MIR borrow check time. It is a fairly naive "fixed point" iteration that propagate bits around. It can (probably) be improved by introducing a "dirty list" to avoid processing basic blocks whose contents have not changed.

[nikomatsakis]

A few tips into the code to get you started. do_dataflow is here:

rust/src/librustc_mir/dataflow/mod.rs

Lines 123 to 136 in 764232c

	pub(crate) fn do_dataflow<'a, 'gcx, 'tcx, BD, P>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
	mir: &'a Mir<'tcx>,
	node_id: ast::NodeId,
	attributes: &[ast::Attribute],
	dead_unwinds: &IdxSet<BasicBlock>,
	bd: BD,
	p: P)
	-> DataflowResults<BD>
	where BD: BitDenotation + InitialFlow,
	P: Fn(&BD, BD::Idx) -> DebugFormatted
	{
	let flow_state = DataflowAnalysis::new(mir, dead_unwinds, bd);
	flow_state.run(tcx, node_id, attributes, p)
	}

It invokes run which then invokes dataflow:

rust/src/librustc_mir/dataflow/mod.rs

Lines 77 to 81 in 764232c

	fn dataflow<P>(&mut self, p: P) where P: Fn(&BD, BD::Idx) -> DebugFormatted {
	let _ = p; // default implementation does not instrument process.
	self.build_sets();
	self.propagate();
	}

This in turn invokes propagate:

rust/src/librustc_mir/dataflow/mod.rs

Lines 184 to 194 in 764232c

	fn propagate(&mut self) {
	let mut temp = IdxSetBuf::new_empty(self.flow_state.sets.bits_per_block);
	let mut propcx = PropagationContext {
	builder: self,
	changed: true,
	};
	while propcx.changed {
	propcx.changed = false;
	propcx.walk_cfg(&mut temp);
	}
	}

which calls walk_cfg repeatedly:

rust/src/librustc_mir/dataflow/mod.rs

Line 238 in 764232c

fn walk_cfg(&mut self, in_out: &mut IdxSet<BD::Idx>) {

walk_cfg just iterates over all the basic blocks:

rust/src/librustc_mir/dataflow/mod.rs

Line 240 in 764232c

for (bb_idx, bb_data) in mir.basic_blocks().iter().enumerate() {

for each one, it takes the current "start point" and applies the gen-kill sets:

rust/src/librustc_mir/dataflow/mod.rs

Lines 243 to 247 in 764232c

	let sets = builder.flow_state.sets.for_block(bb_idx);
	debug_assert!(in_out.words().len() == sets.on_entry.words().len());
	in_out.clone_from(sets.on_entry);
	in_out.union(sets.gen_set);
	in_out.subtract(sets.kill_set);

Finally, it takes that result and pushes it into the "start set" for the successors (sometimes applying a diff along the way):

rust/src/librustc_mir/dataflow/mod.rs

Lines 249 to 250 in 764232c

	builder.propagate_bits_into_graph_successors_of(
	in_out, &mut self.changed, (mir::BasicBlock::new(bb_idx), bb_data));

Likely, it would be more efficient to keep some kind of "dirty bits" indicating which basic blocks may need to be processed at all. Things would be added to this list by that final function call -- i.e., instead of saying "changed = true", we would push onto the list. Then in the next round we start by processing the elements on that list, and we repeat this until the list comes back as empty. Or something like that.

[nikomatsakis]

UPDATE: I've moved the content of this comment, which discussed liveness, to bug #51819

[nikomatsakis]

(In principle, it might be a win to convert these computations to use datafrog as well, but that would require more intrusive changes, I imagine.)

[nikomatsakis]

@PramodBisht and I have been discussing how to fix this bug in a bit more detail on Zulip. Here is the thread devoted to this issue.

[nikomatsakis]

@PramodBisht opened #51900 -- this seems to do what I asked, however my local measurements suggest it is not a performance win. Curious. We may want to try other evaluation orders.

[nikomatsakis]

I cited this paper here:

https://pdfs.semanticscholar.org/db53/41a4bc653b84a12780139d795a910c1c8b60.pdf