Need to refine definition of a back edge used by structured control flow rules

[johnkslang]

The current definition of a back edge in SPIR-V is not quite correct:

Back Edge: If a depth-first traversal is done on a function’s CFG, starting from the first block of the function, a back edge is a branch to a previously visited block. A back-edge block is the block containing such a branch.

This was a late addition that doesn't quite work with the intent of the structured control flow rules.

Suggestions from @dneto0, in issue KhronosGroup/SPIRV-Tools#270 :

I think the spec's definition of back-edge incorrectly allows cross edges to be classified as back-edges. I think it should instead say the equivalent of "A back-edge is an edge in the CFG from a block B to a block C that dominates B. B may be the same as C."

But I think glslang's code generation is sensible, and if anything the spec should be amended to clearly allow unreachable continue-constructs.

For B-> C to be a back edge the "previously visited" phrasing to me means "I am currently visiting B, and the edge makes me want to visit C, but I have previously visited C". It's the "I am currently visiting B" part that is not satisfied if doing a DFS starting a the entry block of the function.

[dneto0]

I think we could use a new concept of "latch edge" and most current uses of "back edge" are replaced by "latch edge".

A "latch edge" is either:

• a back-edge (in the wikipedia sense) to the loop header. This is the case where the continue construct is dominated by the loop header.
• an edge from an unreachable block to a loop header.

Then we get these:

• a "latch-edge block" is a block containing a latch edge.
• (structured control flow rule): all CFG latch edges must branch to a loop header, with each loop header having exactly one latch edge branching to it.
• (structured control flow rule): for a given loop, its latch-edge block must post dominate the OpLoopMerge's Continue Target, and that Continue target must dominate the latch-edge block.
• a continue construct is: "the set of blocks dominated by an OpLoopMerge's Continue Target and post dominated by the corresponding latch-edge block."

Remove the concept of a back-edge blocks, since it would no longer be used.

I think we also want to say that unreachable continue constructs can't be shared: a latch-edge block ends with an unconditional branch. (E.g. it can't branch to two distinct loop headers.)

(Aside: An unreachable continue construct can be replaced by a trivial block that just has an OpLabel followed by its unconditional branch. Modulo dead decorations.)

Update: fixed the first sentence to say uses of back edge are replaced by latch edge.

[dneto0]

Hm. Given how a do-while loop would be generated (with a conditional branch at the end), I think it's too strong to say that an unreachable continue construct must end with an unconditional branch.
I'd have to think a bit more about whether continue constructs should be allowed to be shared between two different loops.

[dneto0]

Another weird case: What if the loop header itself is unreachable? Does that affect the conditions on the continue construct? I suspect it does not, except that in this case the continue construct is probably forced to be unreachable (?).

[dneto0]

I'm prototyping validator support to permit the extra case. It would be simplify book-keeping if we forced the (unreachable) latch block to appear after the loop header. For a reachable latch block, dominance already forces this condition.

[a2flo]

(Sorry if I'm hijacking this thread/issue, I can create a new issue if you want me to, but this seems trivial enough.)

Considering that a loop header can contain a conditional branch (-> OpLoopMerge description), the loop header block would also need to contain an OpSelectionMerge in addition to the OpLoopMerge, but this isn't currently allowed by the spec, because both state that (OpLoopMerge|OpSelectionMerge) "must be the second-to-last instruction in its block".

=> either remove OpBranchConditional from the OpLoopMerge description or refine the "second-to-last" text so that both merge operations can occur in a block.

If doing the latter: shouldn't OpLoopMerge allow OpSwitch as well then?

[ratchetfreak]

I'm not so sure that complicating the loop construct like that is a good idea. Conceptually a loop header should only branch to the entry point of the loop and optionally to the merge block of the loop. Allowing more targets from the header would only complicate matters.

[dneto0]

@a2flo: That's a distinct issue so please file it separately.

[johnkslang]

This is fixed in the just published Rev. 2 of SPIR-V 1.5 in the Khronos SPIR-V Registry.