Commit Graph

4 Commits

Author SHA1 Message Date
Connor Abbott b8fc7a08f9 util/dag: Add dag_add_edge_max_data
This will be useful for when the edge data represents a delay of some
sort, like it will with ir3.

Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/13722>
2021-11-17 13:41:47 +00:00
Connor Abbott 508f917d8c util/dag: Make edge data a uintptr_t
Nobody was actually using it as a pointer, and I'm going to introduce a
shared function which relies on it not being a pointer so let's fix this
once and for all.

Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/13722>
2021-11-17 13:41:47 +00:00
Matt Turner dcf1d8d7a4 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@anholt.net>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/12232>
2021-08-17 17:54:09 +00:00
Eric Anholt 0533d2d95c util: Add a DAG datastructure.
I keep writing this for various schedulers.

Acked-by: Timothy Arceri <tarceri@itsqueeze.com>
2019-03-11 13:13:52 -07:00