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).

Fixes #43704.

1 files changed, 36 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