From dcf1d8d7a4fe5657a24d4a6799532a39aa117977 Mon Sep 17 00:00:00 2001 From: Matt Turner Date: Wed, 4 Aug 2021 18:47:02 -0700 Subject: [PATCH] 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 Part-of: --- 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 8f7cdd6..8e8d2d6 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); } /** -- 2.7.4