Auto merge of #43713 - arielb1:legacy-dataflow, r=eddyb

rustc::middle::dataflow - visit the CFG in RPO

We used to propagate bits in node-id order, which sometimes caused an
excessive number of iterations, especially when macros were present. As
everyone knows, visiting the CFG in RPO bounds the number of iterators
by 1 plus the depth of the most deeply nested loop (times the height of
the lattice, which is 1).

I have no idea how this affects borrowck perf in the non-worst-case, so it's probably a good idea to not roll this up so we can see the effects.

Fixes #43704.

r? @eddyb

2 files changed, 79 insertions, 0 deletions

diff --git a/src/librustc_data_structures/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs
index f94ed6b7209..f562ae0e3b8 100644
--- a/src/librustc_data_structures/graph/mod.rs
+++ b/src/librustc_data_structures/graph/mod.rs
@@ -308,6 +308,42 @@ impl<N: Debug, E: Debug> Graph<N, E> {
         DepthFirstTraversal::with_start_node(self, start, direction)
     }
 
+    pub fn nodes_in_postorder<'a>(&'a self,
+                                  direction: Direction,
+                                  entry_node: NodeIndex)
+                                  -> Vec<NodeIndex>
+    {
+        let mut visited = BitVector::new(self.len_nodes());
+        let mut stack = vec![];
+        let mut result = Vec::with_capacity(self.len_nodes());
+        let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
+            if visited.insert(node.0) {
+                stack.push((node, self.adjacent_edges(node, direction)));
+            }
+        };
+
+        for node in Some(entry_node).into_iter()
+            .chain(self.enumerated_nodes().map(|(node, _)| node))
+        {
+            push_node(&mut stack, node);
+            while let Some((node, mut iter)) = stack.pop() {
+                if let Some((_, child)) = iter.next() {
+                    let target = child.source_or_target(direction);
+                    // the current node needs more processing, so
+                    // add it back to the stack
+                    stack.push((node, iter));
+                    // and then push the new node
+                    push_node(&mut stack, target);
+                } else {
+                    result.push(node);
+                }
+            }
+        }
+
+        assert_eq!(result.len(), self.len_nodes());
+        result
+    }
+
     /// Whether or not a node can be reached from itself.
     pub fn is_node_cyclic(&self, starting_node_index: NodeIndex) -> bool {
         // This is similar to depth traversal below, but we
diff --git a/src/librustc_data_structures/graph/tests.rs b/src/librustc_data_structures/graph/tests.rs
index bdefc39a61a..b6a0d4cff5a 100644
--- a/src/librustc_data_structures/graph/tests.rs
+++ b/src/librustc_data_structures/graph/tests.rs
@@ -175,3 +175,46 @@ fn is_node_cyclic_b() {
     let graph = create_graph_with_cycle();
     assert!(graph.is_node_cyclic(NodeIndex(1)));
 }
+
+#[test]
+fn nodes_in_postorder() {
+    let expected = vec![
+        ("A", vec!["C", "E", "D", "B", "A", "F"]),
+        ("B", vec!["C", "E", "D", "B", "A", "F"]),
+        ("C", vec!["C", "E", "D", "B", "A", "F"]),
+        ("D", vec!["C", "E", "D", "B", "A", "F"]),
+        ("E", vec!["C", "E", "D", "B", "A", "F"]),
+        ("F", vec!["C", "E", "D", "B", "F", "A"])
+    ];
+
+    let graph = create_graph();
+
+    for ((idx, node), &(node_name, ref expected))
+        in graph.enumerated_nodes().zip(&expected)
+    {
+        assert_eq!(node.data, node_name);
+        assert_eq!(expected,
+                   &graph.nodes_in_postorder(OUTGOING, idx)
+                   .into_iter().map(|idx| *graph.node_data(idx))
+                   .collect::<Vec<&str>>());
+    }
+
+    let expected = vec![
+        ("A", vec!["D", "C", "B", "A"]),
+        ("B", vec!["D", "C", "B", "A"]),
+        ("C", vec!["B", "D", "C", "A"]),
+        ("D", vec!["C", "B", "D", "A"]),
+    ];
+
+    let graph = create_graph_with_cycle();
+
+    for ((idx, node), &(node_name, ref expected))
+        in graph.enumerated_nodes().zip(&expected)
+    {
+        assert_eq!(node.data, node_name);
+        assert_eq!(expected,
+                   &graph.nodes_in_postorder(OUTGOING, idx)
+                   .into_iter().map(|idx| *graph.node_data(idx))
+                   .collect::<Vec<&str>>());
+    }
+}