Move post order walk to iterative approach

The previous recursive approach might overflow the stack when walking a
particularly deep, list-like, graph. In particular, dominator
calculation for borrow checking does such a traversal and very long
functions might lead to a region dependency graph with in this
problematic structure.

1 files changed, 20 insertions, 5 deletions

diff --git a/compiler/rustc_data_structures/src/graph/iterate/mod.rs b/compiler/rustc_data_structures/src/graph/iterate/mod.rs
index 5f42d46e285..1634c586316 100644
--- a/compiler/rustc_data_structures/src/graph/iterate/mod.rs
+++ b/compiler/rustc_data_structures/src/graph/iterate/mod.rs
@@ -33,16 +33,31 @@ fn post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>(
     result: &mut Vec<G::Node>,
     visited: &mut IndexVec<G::Node, bool>,
 ) {
+    struct PostOrderFrame<Node, Iter> {
+        node: Node,
+        iter: Iter,
+    }
+
     if visited[node] {
         return;
     }
-    visited[node] = true;
 
-    for successor in graph.successors(node) {
-        post_order_walk(graph, successor, result, visited);
-    }
+    let mut stack = vec![PostOrderFrame { node, iter: graph.successors(node) }];
+
+    'recurse: while let Some(frame) = stack.last_mut() {
+        let node = frame.node;
+        visited[node] = true;
 
-    result.push(node);
+        while let Some(successor) = frame.iter.next() {
+            if !visited[successor] {
+                stack.push(PostOrderFrame { node: successor, iter: graph.successors(successor) });
+                continue 'recurse;
+            }
+        }
+
+        let _ = stack.pop();
+        result.push(node);
+    }
 }
 
 pub fn reverse_post_order<G: DirectedGraph + WithSuccessors + WithNumNodes>(