tree db11359d7adf9759e43f02d7eb5c820ce8ef96fb
parent d70129a3d3409dac58e14f819b62620393afb652
author Ben Clayton <bclayton@google.com> 1560859940 +0100
committer Ben Clayton <bclayton@google.com> 1560894165 +0000

SpirvShader: Rework CFG traversal.

The previous traversal could create huge pending lists of duplicate-blocks, to just skip over them.
This was due a couple of factors, including BFS traversal and always appending the downstream blocks to the queue.

There's no particular reason to do BFS traversal, so perform DFS traversal instead, and check the downstream blocks haven't been processed already before enquing.

Fixes pending lists reaching counts as high as 1e7 for tests such as dEQP-VK.spirv_assembly.instruction.compute.opphi.nested -
making these tests much faster to pass and drastically reducing peak memory usage.

Bug: b/135512559
Change-Id: Ibbfa03e582f08d6b41e6c8496d05b8b4027b31b6
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/32951
Reviewed-by: Chris Forbes <chrisforbes@google.com>
Kokoro-Presubmit: kokoro <noreply+kokoro@google.com>
Tested-by: Ben Clayton <bclayton@google.com>