Mesa (main): util: Replace recursive DFS with iterative implementation

[GitLab Mirror]

Module: Mesa
Branch: main
Commit: dcf1d8d7a4fe5657a24d4a6799532a39aa117977
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=dcf1d8d7a4fe5657a24d4a6799532a39aa117977

Author: Matt Turner <mattst88 at gmail.com>
Date:   Wed Aug  4 18:47:02 2021 -0700

util: Replace recursive DFS with iterative implementation

Doesn't fix, but improves the situation in issue #5163. The
VK.spirv_assembly.instruction.graphics.spirv_ids_abuse.lots_ids_* tests
emit about 160k instructions. ir3_sched blows out the stack after
dag_traverse_bottom_up_node reaches a depth of about 130k frames.

This patch replaces the recursively-implemented post-order traversal
with an iterative implementation using a stack, allowing us to process
DAGs as large as memory can hold.

Definitely makes you appreciate the elegance of recursion...

Reviewed-by: Emma Anholt <emma at anholt.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/12232>

---

 src/util/dag.c | 50 ++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 44 insertions(+), 6 deletions(-)

diff --git a/src/util/dag.c b/src/util/dag.c
index 8f7cdd6348e..8e8d2d68506 100644
--- a/src/util/dag.c
+++ b/src/util/dag.c
@@ -111,12 +111,50 @@ dag_traverse_bottom_up_node(struct dag_node *node,
    if (_mesa_set_search(state->seen, node))
       return;
 
-   util_dynarray_foreach(&node->edges, struct dag_edge, edge) {
-      dag_traverse_bottom_up_node(edge->child, cb, state);
-   }
-
-   cb(node, state->data);
-   _mesa_set_add(state->seen, node);
+   struct util_dynarray stack;
+   util_dynarray_init(&stack, NULL);
+
+   do {
+      assert(node);
+
+      while (node->edges.size != 0) {
+         util_dynarray_append(&stack, struct dag_node *, node);
+
+         /* Push unprocessed children onto stack in reverse order. Note that
+          * it's possible for any of the children nodes to already be on the
+          * stack.
+          */
+         util_dynarray_foreach_reverse(&node->edges, struct dag_edge, edge) {
+            if (!_mesa_set_search(state->seen, edge->child)) {
+               util_dynarray_append(&stack, struct dag_node *, edge->child);
+            }
+         }
+
+         /* Get last element pushed: either left-most child or current node.
+          * If it's the current node, that means that we've processed all its
+          * children already.
+          */
+         struct dag_node *top = util_dynarray_pop(&stack, struct dag_node *);
+         if (top == node)
+            break;
+         node = top;
+      }
+
+      /* Process the node */
+      cb(node, state->data);
+      _mesa_set_add(state->seen, node);
+
+      /* Find the next unprocessed node in the stack */
+      do {
+         node = NULL;
+         if (stack.size == 0)
+            break;
+
+         node = util_dynarray_pop(&stack, struct dag_node *);
+      } while (_mesa_set_search(state->seen, node));
+   } while (node);
+
+   util_dynarray_fini(&stack);
 }
 
 /**