Skip to content

util: Replace recursive DFS with iterative implementation

Matt Turner requested to merge mattst88/mesa:dag into main

Doesn't fix, but improves the situation in issue #5163 (closed). 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...

Issue: #5163 (closed)

Edited by Matt Turner

Merge request reports