mergeBesideReturns ignores the edges into blocks that only lead to a return
when it looks for the merge of a selection whose arms do not meet. It only
recognized a straight run of single-predecessor blocks ending in a return,
so an arm whose return path branches again (an early return inside a
nested if/else) still counted as a block of its own, the arms had no
common post-dominator, and the whole program fell back to flag
structurization ("conditional block 0 has no structured merge").
A block now returns when it has one predecessor, is dominated by the
header and every successor returns. Flag structurization turns every
original block into a guarded region, and the register phis at the region
joins carry values from paths that never reach a later use: in Resident
Evil 4 (PPSA07411) pixel program 0x20762add00 the T# of an image_load
became Phi(0, load through Phi(user data, compare mask)) and resource
analysis refused it. Structured, the T# is the load through the user-data
pointer and the program prepares, captures and materializes.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Structurizing recomputes dominators after every CFG rewrite, and each block started from a vector of every block id. The same fixed point now runs on bitsets and still writes the sorted id lists.
Co-authored-by: Cursor <cursoragent@cursor.com>
The structurizer's attempts could spend more than 10 s on a graph of 20
blocks before they accepted or refused it; in a title that stalls shader
preparation. Nearly all of that time went to recomputing dominators and
post-dominator fixpoints while merge splitting grew the graph to
hundreds or thousands of blocks.
Dominators, post-dominators and the fixpoints in mergeBesideReturns,
iterationSelectionMerge and joinWithinIteration now sweep the blocks in
reverse post-order (dominators) or post-order (the others) instead of in
id order. Splitting appends its new blocks at the end, so id order needed
a sweep for almost every new block. Each fixpoint starts from the full
set and its equations are monotone, so every sweep order reaches the
same greatest fixed point and the result does not change.
Shared merge splitting also refuses an attempt once the graph has more
than 16 times its block count at the start of splitting (at least 64
blocks). Without it, splits that route through a new junction each round
grew some graphs past 4,000 blocks before the round budget ran out. A
refused attempt goes to the next attempt or to the reach-flag fallback,
as it does after the round budget.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
When every attempt of the structurizer ladder refuses a graph, the title
aborts. Rebuild such a graph from a hierarchical decomposition into
strongly connected components instead: each original block keeps one copy
and runs behind a guard on its own reach flag, and each component becomes
a loop with a single latch that repeats it while a back edge set its again
flag. Every edge sets the reach flag of its target, so exactly one flag
names the next original block and the blocks run in the input's order for
every branch decision. Irreducible and non-terminating graphs are handled
the same way, and no block is cloned.
The ladder runs first and its output is unchanged. The fallback only runs
when both attempt series refuse; if it cannot structure the graph, the
ladder's error is reported as before. Blocks that start the top-level
order unconditionally run unguarded, so the entry block's results reach
later blocks without a stale path. APS5_FORCE_STRUCTURIZER_FALLBACK=1
uses the construction for every supported graph, for tests.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
A selection outside loops whose one arm only returns and whose other arm
branches to a join it does not dominate gets an empty block on that edge
as its merge (splitOneReturnJoin), but only when every other predecessor
of the join dominates the selection or is dominated by it. When the
parent selection's other arm is a region that ends in the same join, the
selection has no structured merge and the shader fails to recompile.
When every structurization attempt fails, Structurize now runs them again
and accepts that split for any join the selection does not dominate. The
split only inserts an empty block on the edge from the selection to the
join. Graphs that structurize on main keep their result.
A synthetic CFG and a synthetic program cover the shape; both fail on main
with "conditional block N has no structured merge".
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01Fnrk5Dazjb2tLooVSpdRQq
Route semantic self-loops through a dedicated empty back-edge block. This prevents block merging from folding the continue target into the loop header when memory instructions emit nested selections. Add a synthetic loop-store regression that fails SPIR-V validation after optimization on main.
Seed each iteration-selection update from its first eligible successor
instead of rebuilding and intersecting the universe of block IDs.
Reuse the existing in-place intersection and sorted-insertion helpers
while preserving the original empty-successor and fixed-point behavior.
Keep a cache-neutral switch for same-binary output and timing comparisons.
Run the existing structurizer and control-flow fixtures in a separate
process with this optimization disabled as well as in their default mode.
Keep the AlxcBTW #24 fallback as a separate guarded attempt before enabling shared-exit and nested-continuation repairs. Add the reduced padded shader reported by orishamir on #2523 as an end-to-end regression; the abstract graph does not reproduce the same failure.
The third structurize pass, which routes loop exits that leave the loop
before they meet, runs only when the plain and the privatized pass
throw, and its result was used without a check. Merged with #2471, it
turns some of those budget failures into graphs that spirv-val
rejects. In this one, selection 12 of the result lies in the selection
at 7 and branches to 7's merge block 13:
{{1}, {2, 3}, {4}, {5}, {6, 7}, {}, {8, 9}, {10, 11}, {1}, {12, 4},
{5}, {13}, {8, 14}, {15, 16}, {7}, {13}, {4}}
block 12 exits the selection headed by block 12, but not via a
structured exit
hasStructuredConstructs checks the third pass's result against the
structured control-flow rules of the SPIR-V specification (2.11), with
dominance and post-dominance taken over branch, merge and continue
edges. Back edges come only from a loop's continue block. A conditional
without a merge breaks or continues its innermost loop. A header
strictly dominates its merge, and a loop header its continue block. A
construct contains the merge of every header inside it and is entered
only through its header. It is left only to its own merge or to the
innermost loop's merge or continue block, and a continue construct only
to its loop's header or merge. When the result fails, the second pass's
error is reported, as when the third pass throws. The first two passes
are unchanged.
Differential fuzz with the structured-program generator and random
reducible graphs. Oracle: exact post-dominators,
requireStructuredBranches, merges dominated by their headers, the
original's executions, and spirv-val (SPIRV-Tools v2026.4).
- Against 9fa7d06a: the same outcome and output on every graph. That
covers 100,000 random graphs at 0 words and with one block at 1000,
and 30,000 programs at 16 and at 1000 words per block, each also with
one block at 1000.
- Merged with #2471, the same 30,000 programs: the third pass had made
41, 42 and 45 of them invalid (16 words, 16 with one block at 1000,
1000 words). These end in #2471's own error again, and nothing else
changes. The 1, 1 and 18 graphs that d59a9167 merged with #2471
already structures invalidly come from the first two passes and stay
as they are.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
A loop whose exit paths leave the loop construct before they meet got
the nearest common post-dominator of its exits as merge, and
splitSharedMergeBlocks never separated it. An exit continues the
enclosing loop, so its path to that merge runs through the outer
header again, or an exit enters a block that a branch before the loop
also reaches. splitOneLoopMerge gave the loop a forwarding merge block
each round, the other path still bypassed it, and the post-dominator
stayed the same block until "CFG shared merge splitting exceeded
budget". These shapes from #2642 fail that way on main, on d59a9167,
with #2471 and with both:
{{1}, {2}, {3, 4}, {2, 5}, {}, {1}}
{{1}, {2, 3}, {4, 5}, {}, {3, 6}, {1}, {2}}
{{1, 3}, {2, 4}, {3, 1}, {4}, {}}
{{1, 2}, {3, 2}, {4}, {4, 1}, {}}
{{1, 2}, {4}, {3, 1}, {4, 2}, {}}
When the plain and the privatized pass both fail, Structurize now runs
a third pass. It routes such a loop's exits through one junction with
routeLoopExits, as loops whose exits have no common post-dominator are
routed already, and gives an outer loop whose only latch lies in an
inner loop its own continue block. In that pass a loop exit conditional
that is neither a direct break or continue nor has an exit tail of its
own is structured as a selection, and an exit tail that the other arm
reaches is not used as one. Without that, graphs the routing unblocks
keep a conditional without merge (the rule from #2762) or a selection
entered past its header. Graphs that the first two passes structure
are unchanged, and when the third pass fails too, the second pass's
error is reported.
Differential fuzz against main, reducible graphs with 5 to 9 blocks,
each with 0 estimated words per block and again with one block at 1000
words (the privatizeSharedReturns path). Oracle: exact post-dominators,
requireStructuredBranches, merges dominated by their headers, the same
executions as the original graph, and spirv-val (SPIRV-Tools v2026.4,
Vulkan 1.3) on a module emitted from the structured graph.
- 200,000 random graphs. main structures 178,743 (0 words) and 178,750
(1000 words); the output is identical on all of them. Of main's
14,256 and 14,311 budget failures 13,527 and 13,596 now structure,
and 2,576 and 2,565 of its refusals. No new output is invalid. The
invalid outputs are main's 530, plus at 1000 words one graph that
d59a9167 already turns from a budget failure into a back edge to a
block that is not a loop header.
- 24,000 structured programs from orishamir/anyps5-cfgfuzz's
generator (if/else, loops, break, continue, return). main structures
21,093 and 21,022; the output is identical. 619 of 2,448 and 634 of
2,429 budget failures now structure. No new output is invalid; the
invalid outputs are main's 92.
agc_structurizer has the five shapes; requireOriginalBranches now
follows route variables. agc_shader_control_flow has two RDNA programs
of the first two shapes. The non-GPU tests and the 253 agc_driver GPU
tests pass on Windows (RTX 5070 Laptop).
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
A selection in a loop whose arms both reach their nearest common
post-dominator within the iteration got that post-dominator as its
merge. When an arm can also continue the loop, the post-dominator
follows the back edge: the continuing path re-enters the loop header
and reaches the outer selection's merge without passing the block where
the arms meet. In the loop {1}, {2, 4}, {3, 4}, {4, 5}, {1, 6}, {1}, {}
from #2642 (latches 4 and 5) the selections at 1 and 2 both merged at 4.
splitSharedMergeBlocks gave 2 a forwarding merge block, recomputed 4 for
it because 3 continues through 5, and repeated until "CFG shared merge
splitting exceeded budget: originalBlocks=9 currentBlocks=45
splitBudget=36".
When that post-dominator is inside the loop construct, findSelectionMerge
now takes the arms' nearest common post-dominator over the paths of the
iteration that reach it, so paths that leave through the continue block
or the loop's merge no longer move the merge past the arms' join. When
no arm leaves early the result is the same block as before. The loop
structures with two forwarding blocks and no clones or route variables;
so do three latches, the selections on the false side, and an if-else
whose one arm continues.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Intersect copied fixed-point sets without allocating each intermediate.
Preserve sorted results and the existing analysis iteration order.
Compact oversized storage only when publishing a changed set.
Keep an allocating control switch outside the cache key.
Compare complete fixed points over empty intersections, loops and DAGs.
Register the same equivalence fixtures for the allocating control.
Both dominance analyses start from sorted unique sets and intersect them.
Insert the current block ID with lower_bound instead of sorting again.
Preserve every intermediate set and the existing ID-order iteration.
Keep the generic unsorted helper and all graph rewrite logic unchanged.
Compare both analyses against the original algorithms on six raw CFGs.
Cover finite loops, closed SCCs, unreachable islands and permuted IDs.
A pixel shader whose early discards branch to one small ending block
gave that block several conditional predecessors outside any loop, and
structurizing failed. When the regular pass throws, the structurizer
restarts from the original graph and first gives each conditional
predecessor its own copy of such a return block (within the clone word
floor and a budget of four clones per block).
Uncharted: Legacy of Thieves Collection (PPSA05684) stopped at such a pixel shader with "conditional block 15 has no structured merge".
computePostDominators iterates its sets to a fixed point, visiting the
blocks in id order. Post-dominance flows from a block's successors back to
it, and successors mostly have higher ids, so each pass moved the sets back
by about one block: a long program needed about as many passes as it has
blocks, each costing O(blocks^2). recomputeAnalyses runs it after every
split of splitSharedMergeBlocks, up to four times per block.
Visit the blocks in post-order of the CFG (successors first), then any the
entry does not reach. The sets start from every block and only shrink, so
the iteration still converges to the same greatest fixed point, now in a
few passes.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
toHexString, contains, intersectSorted, addUnique, sortUnique, remapId,
remapIds and rebuildPredecessors were defined with identical bodies in
the anonymous namespaces of two of ControlFlowGraph.cpp, GraphBuilder.cpp
and Structurizer.cpp. They are now declared in ControlFlowHelpers.hpp,
which only these three files include, and defined in ControlFlowGraph.cpp.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
A selection inside a loop whose arm either joins the other target or
continues/breaks (`if (a) { if (b) continue; x; }`) got the nearest
common post-dominator as its merge. When the loop exits after the outer
join, that is the outer selection's merge, so both selections shared
it. splitSharedMergeBlocks then inserted a forwarding block in front of
it, recomputed the same merge, and repeated until the budget ran out:
PPSA14632's compute shader 0x1a80ee0000 stopped with "CFG shared merge
splitting exceeded budget: originalBlocks=92 currentBlocks=460".
findSelectionMerge now picks the joined target when the other arm is a
conditional block with the header as its only predecessor, and every
successor of that arm is the joined target or the loop's continue or
merge block. The shader structures with 13 added blocks and no clones
or route variables.
In the result the outer selection header dominates the loop's continue
target, so the test's verifyStructured counted the continue target as a
selection member that branches outside (back to the loop header).
SPIR-V uses structural dominance, where the loop header's edge to its
continue target keeps it out of the selection, so verifyStructured now
skips the continue construct of an enclosing loop. spirv-val accepts
the new test's SPIR-V for both subgroup sizes.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
A loop whose exits have no common post-dominator, such as a normal exit
to one s_endpgm tail beside an early-out to a kill tail, got no merge
block, and Structurize threw "loop at block N has no structured
merge/continue". With three or more exits, detectNaturalLoops threw
first, on a lookup of InvalidControlFlowId.
Such a loop now leaves through one new merge block that dispatches on
route variables. They are cleared before the header and set on each
exit edge to a target other than the latch's exit. Inner loops are
routed first; a routing that would change the natural loops throws.
A loop-exit tail branch whose in-body target is the continue block no
longer merges there, which spirv-val rejects ("Header block ... is
contained in the loop construct ..., but its merge block ... is not").
A selection whose one arm only returns (kill or s_endpgm) and whose other
arm branches straight to the merge of an enclosing selection had no
structured merge, so the draw was skipped. PPSA21564's BotEye G-buffer
pixel shaders (eight variants) have this shape.
When no other split applies, the edge from such a header to the shared
join is now split into an empty block, which becomes the header's merge.
A conditional inside a loop with one target in the loop body and the
other outside it was taken for a break and emitted without a merge. When
the outside target is not the loop's merge but a tail of blocks that
reaches it, SPIR-V has no construct for that branch: spirv-val rejects
the module ("Selection must be structured") and the driver is free to
compile it into anything.
Such a branch now merges at its in-body target when the tail is private
to it (every tail block is dominated by the tail's first block, stays in
the loop construct and leaves only for the loop's merge), so the tail is
an "if (c) { tail; break; }" the loop already allows. Merges are given
to these after every other construct's, and one already taken leaves the
branch as before.
All 13 PPSA21564 programs whose V#s are read from GPU memory (the
deferred lighting and ray-traced passes) had two such branches in their
traversal loops. With this change none of the 74 dumped title programs
has one, and the 209 modules of a title-to-cinematic run validate apart
from three unrelated image-offset and entry-point errors.
Tests: agc_structurizer_tests structures a loop that exits through one
tail block and a loop with two exit tails, and requires every merge-less
conditional to target its loop's merge or continue.
A selection whose region (the blocks reachable from its arms before its
merge) is also entered from outside the header cannot be expressed as a
SPIR-V selection construct, and the structurizer gave up with "semantic
block cloning is disabled". Pixel shaders hit this through a shared
discard tail (s_mov_b64 exec, 0 / exp null / s_endpgm) that several
selections branch to, compute shaders through short-circuit conditions
that jump into a shared body, and ray-traced compute passes through an
s_cbranch_execz that skips past a join into the middle of a selection.
Such a region is made single-entry in one of two ways, chosen per region
by its estimated translated size:
- Cloning (node splitting): the blocks the outside edges reach inside the
region are copied and the outside edges redirected to the copies. When
the header's merge is a shared linear return tail, giving the header a
private copy of that tail is tried first. Each block now carries an
estimate of the SPIR-V words it translates to. The per-instruction
weights come from a fit of the recompiler's per-block output (before
spirv-opt, phis excluded) over 8,300 blocks of captured shaders: VALU
60, buffer and flat 120, SMEM 180, image 220, LDS 400. SALU (8) and
exports (20) fit near zero and keep a small weight. Lane ops (120) and
image_bvh_intersect_ray (2000) were too rare there to fit and are
weighted for the wave and traversal expansions they need. A region is cloned only when it is at most 1024 estimated
words and at most an eighth of the program (at least 256), and while
all clones stay within a quarter of the program.
- Routing through a junction, for larger regions: every edge into the
entered part (from outside, and from the header's own arms) and every
edge from the arms to the merge is sent through a new empty junction
block. Each rerouted edge first passes empty blocks that assign
Boolean route variables (the IR's goto variables); the junction tests
them in order to reach the edge's original target. The entered part
then follows the junction and is emitted once. Branch conditions are
still evaluated only at the end of their original blocks: a route
variable records the edge a block already took, so a later SCC, VCC or
EXEC write cannot change the route, and in the two-lane wave64 layout
the source branch is combined across both halves as before while the
route variable holds the same constant in both. Routing is refused
when a rerouted edge is a back edge or leaves an indirect branch, when
the region wraps around to a dominating block, or when it would change
the natural loops or make the graph irreducible; cloning bounded by the
program's estimated size is the fallback, and otherwise it throws with
the header, the entered block and both reasons.
Selections whose arms only meet again after private return tails had no
post-dominator merge. When the existing rules find none, the merge is
now looked up with edges into private return tails ignored, or taken as
the other arm when one arm only returns; the candidate must still exit
the construct only through the merge. applyBlockOrder also remaps
indirect branch targets.
agc_shader_control_flow_tests (under ctest) covers hand-assembled
gfx1030 programs: the cloned shapes above, and routed ones (an
s_cbranch_execz into an expensive region with a loop, a region inside a
loop, nested entered regions, a shared body reached after SCC is
overwritten, early returns beside an entered region, an arm that only
returns). It checks that every selection construct exits only through
its merge, follows route variables to check that the structured graph
runs the same instruction ranges under the same branch conditions as
the original, bounds the cloned instructions, recompiles each program
for 64- and 32-lane subgroups, and keeps the routed execz program within
10% of the SPIR-V of the same program without the entering branch.
Given .req files it checks their graphs instead. agc_shader_replay --cfg
prints a request's graph, now with each block's estimate, before and
after structurization.
Only the lines this branch added lose their comments; the commits before
keep them, with the reasoning behind each change, for whoever digs into
that code later.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
findSelectionMerge took the nearest common post-dominator of a selection's
targets, computed across the loop's back edge. When one arm only continues
(reaching that block in a later iteration) and the other target is shared
with an enclosing selection, the shared merge was split off the header, the
post-dominator stayed where it was, and splitting repeated until the budget
threw.
Inside a loop, an arm that reaches the post-dominator only past the continue
or merge block now leaves the selection by continuing, and the merge is the
other arm's target; after one split that is the header's own synthetic merge.
agc_structurizer_tests builds the smallest such graph; it hit the budget
before.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Adrià