diff options
| -rw-r--r-- | compiler/rustc_data_structures/src/graph/dominators/mod.rs | 31 |
1 files changed, 21 insertions, 10 deletions
diff --git a/compiler/rustc_data_structures/src/graph/dominators/mod.rs b/compiler/rustc_data_structures/src/graph/dominators/mod.rs index b1f62636b89..eb6e2b296cd 100644 --- a/compiler/rustc_data_structures/src/graph/dominators/mod.rs +++ b/compiler/rustc_data_structures/src/graph/dominators/mod.rs @@ -65,16 +65,16 @@ fn dominators_given_rpo<G: ControlFlowGraph>(graph: G, rpo: &[G::Node]) -> Domin stack.pop(); } - let mut ancestor = IndexVec::from_elem_n(None, graph.num_nodes()); let mut idom = IndexVec::from_elem_n(graph.start_node(), graph.num_nodes()); let mut semi = IndexVec::from_fn_n(std::convert::identity, graph.num_nodes()); let mut label = semi.clone(); let mut bucket = IndexVec::from_elem_n(vec![], graph.num_nodes()); + let mut lastlinked = None; for &w in pre_order_nodes[1..].iter().rev() { semi[w] = w; for v in graph.predecessors(w) { - let x = eval(&pre_order_index, &mut ancestor, &semi, &mut label, v); + let x = eval(&pre_order_index, &mut parent, lastlinked, &semi, &mut label, v); semi[w] = if pre_order_index[semi[w]].unwrap() < pre_order_index[semi[x]].unwrap() { semi[w] } else { @@ -91,6 +91,10 @@ fn dominators_given_rpo<G: ControlFlowGraph>(graph: G, rpo: &[G::Node]) -> Domin let y = eval(&pre_order_index, &mut ancestor, &semi, &mut label, v); idom[v] = if pre_order_index[semi[y]] < pre_order_index[z] { y } else { z }; } + + // Optimization: We share the parent array between processed and not + // processed elements; lastlinked represents the divider. + lastlinked = Some(w); } for &w in pre_order_nodes.iter().skip(1) { if idom[w] != semi[w] { @@ -111,28 +115,39 @@ fn dominators_given_rpo<G: ControlFlowGraph>(graph: G, rpo: &[G::Node]) -> Domin fn eval<N: Idx>( pre_order_index: &IndexVec<N, Option<usize>>, ancestor: &mut IndexVec<N, Option<N>>, + lastlinked: Option<N>, semi: &IndexVec<N, N>, label: &mut IndexVec<N, N>, node: N, ) -> N { - if ancestor[node].is_some() { - compress(pre_order_index, ancestor, semi, label, node); + if is_processed(pre_order_index, node, lastlinked) { + compress(pre_order_index, ancestor, lastlinked, semi, label, node); label[node] } else { node } } +fn is_processed<N: Idx>( + pre_order_index: &IndexVec<N, Option<usize>>, + v: N, + lastlinked: Option<N>, +) -> bool { + if let Some(ll) = lastlinked { pre_order_index[v] >= pre_order_index[ll] } else { false } +} + fn compress<N: Idx>( pre_order_index: &IndexVec<N, Option<usize>>, ancestor: &mut IndexVec<N, Option<N>>, + lastlinked: Option<N>, semi: &IndexVec<N, N>, label: &mut IndexVec<N, N>, v: N, ) { + assert!(is_processed(pre_order_index, v, lastlinked)); let u = ancestor[v].unwrap(); - if ancestor[u].is_some() { - compress(pre_order_index, ancestor, semi, label, u); + if is_processed(pre_order_index, u, lastlinked) { + compress(pre_order_index, ancestor, lastlinked, semi, label, u); if pre_order_index[semi[label[u]]] < pre_order_index[semi[label[v]]] { label[v] = label[u]; } @@ -140,10 +155,6 @@ fn compress<N: Idx>( } } -fn link<N: Idx>(ancestor: &mut IndexVec<N, Option<N>>, parent: &IndexVec<N, Option<N>>, w: N) { - ancestor[w] = Some(parent[w].unwrap()); -} - #[derive(Clone, Debug)] pub struct Dominators<N: Idx> { post_order_rank: IndexVec<N, usize>, |