explain why Glslang generates unconditional branch from a loop header into the loop body

[dneto0]

This question was asked and answered in the chat forum for WebGPU.

kvark

SPIR-V question. In http://shader-playground.timjones.io/48e30d8a7e8954dff2eb4c9e301ec2ca , why is it branch "OpBranch %6" (jumping to OpLoopMerge) at the end of the loop, and not "OpBranch %10" (jumping to the body of the loop)? Shader Playground Copy and paste this link × Copy Close Close ↓ Add compiler

dneto0

The block %9 is the back-edge block. That must branch to the block containing the OpLoopMerge. from definition of back edge: "Back Edge: A branch is a back edge if there is a depth-first search starting at the entry block of the CFG where the branch branches to one of its ancestors. A back-edge block is a block containing such a branch instruction."

Further clarification and elaboration in that definition: "Note: For a given function, if all its loops are structured, then each back edge corresponds to exactly one loop header, and vice versa. So the set of back-edges in the function is unique, regardless of the depth-first search used to find them. This is equivalent to the function’s CFG being reducible."

And structured control flow section (2.11) has rule: "all CFG back edges must branch to a loop header, with each loop header having exactly one back edge branching to it"

What you're probably thinking is "why didn't you do the load and comparison in the block with the OpLoopMerge?" In other words, why not glue block %6 and %10 together.

Well, you can but it ends up being more complicated for code generation for a subtle reason. And that is because 1. You want to have the same code generation for do loops, for loops and while loops.

You can have code like: do { if(cond) {something;} } while(cond2); Example at: http://shader-playground.timjones.io/6d4fc775d0218fb829c08a171494b705

If you jam the first block of the body into the loop header block, then you would have to put both OpLoopMerge and OpSelectionMerge (from 'if (cond)') into that single basic block. But you can't have two merge instructions in the same basic block. That's a spir-v rule. (The rule supports proper nesting)

From the shader playground link I just shared:

      %6 = OpLabel
           OpLoopMerge %8 %9 None
           OpBranch %7
      %7 = OpLabel
     %17 = OpAccessChain %_ptr_Output_float %fragColor %uint_0
     %18 = OpLoad %float %17
     %21 = OpFOrdGreaterThan %bool %18 %float_0_875
           OpSelectionMerge %23 None
           OpBranchConditional %21 %22 %26

%6 is the top of the do-loop. %7 is the first block in the body, and it implements 'if (cond) {'

So the easiest way to generate loop code correctly is to do an unconditional branch from the loop header. And that's the same as WGSL's 'loop {' construct.

If you're writing a SPIR-V reader you have to handle way more than that simple code pattern.