control flow path branching and block mangling

[sylware]

Hi, I may have missed something in the specs, but the OpBranchConditional will create 2 control flow paths. In the selection construct, you can have the blocks from those 2 control flow paths mangled. Namely, you can mangle the blocks from the 2 control flow paths and still follow the block domination rules. Is this mangling allowed by the specs, or did I miss something? Maybe some specs hardening on "branching" inside a construct at the same depth?

[johnkslang]

Is this about structured control flow?

If I understand correctly, if some control flow did that, that control flow would not satisfy being a select construct. You'd then have a mixture of structured control flow (that part that satisfies the constructs) and non-structured control flow.

Currently, OpenCL does not have structured control-flow requirements, while Vulkan and OpenGL require everything to be structured.

Does that address the question?

[sylware]

On Sat, Sep 17, 2016 at 02:24:01PM -0700, John Kessenich wrote:

Is this about structured control flow?

Since this is linked to control flow in a shader program, then I guess this is a concern related to structured control flow.

If I understand correctly, if some control flow did that, that control flow would not satisfy being a select construct. You'd then have a mixture of structured control flow (that part that satisfies the constructs) and non-structured control flow.

I'm going to reformulate with examples:

For instance an OpBranchSelection creates 2 control flow paths A and B:

Header block -> A0 -> A1 -> Merge block
Header block -> B0 -> B1 -> Merge block
(A0,A1,B0,B1 are members of the selection construct)

Is there a specs rule which does forbid the following SPIRV linear block sequencing ?

Header block, A0, B0, A1, B1, Merge block

Currently, OpenCL does not have structured control-flow requirements, while Vulkan and OpenGL require everything to be structured.

Does that address the question?

See above, but I have another similar question: a block shared by several control flow paths which is not the merge block but does branch to the merge block, and that without being an OpPhi block.

For instance an OpBranchSelection creates 2 control flom paths A and B, but in the selection constructs there is a shared block which is S: Header block -> A0 -> S -> Merge block Header block -> B0 -> S -> Merge block (A0,B0,S are members of the selection construct)

Is there a specs rule which does forbid the following SPIRV linear block sequencing?

Header block, A0, B0, S, Merge block

regards,

Sylvain

[sylware]

Ping? Is there a problem?

[ratchetfreak]

If I understand your question correctly you are asking if the paths through each branch are allowed to be interleaved or if they have to be grouped.

And the other question is whether control flow can merge before the marked merge block.

[sylware]

On Tue, Oct 04, 2016 at 01:40:33AM -0700, ratchetfreak wrote:

If I understand your question correctly you are asking if the paths through each branch are allowed to be interleaved or if they have to be grouped.

Yes. You can add the case of interleaved "dead code" blocks too. Are there rules to forbid this in the specs? For instance, in a selection construct, it would mean that control flow paths are cleanly grouped and packed.

There is the exception for the unreachable blocks, but for consistency and simplicity sake, wouldn't be nice to keep them grouped and packed in control flow paths?

And the other question is whether control flow can merge before the marked merge block.

Indeed. I cannot "see" a rule which mandates (must) control flow paths to merge only in explicitely declared merged blocks.

If I missed all those rules, I do serverly apologise for the loss of time.

best regards,

Sylvain

[johnkslang]

The specification does say a merge block is where control flow merges, that the constructs nest, and that they cannot share merge blocks. I'm not sure I know the exact definitions of "grouped" and "packed", but is there an example where control merges at a non merge block, and still satisfies these rules?

Regarding the physical ordering of blocks, I think the only rules are, of course, that non-forward reference rules, and also

The order of blocks in a function must satisfy the rule that blocks appear before all blocks they dominate.

The rules do intentionally stop short of laying out a canonical ordering for all forms of control flow, and instead give some minimum required constraints.

I'm curious if there is a example that seems to adhere to the specification but leads to an undesirable consequence. That gives a specific thing to check against the spec, or to suggest a modification to the spec, motivated by preventing the undesirable consequence.

[sylware]

On Tue, Oct 04, 2016 at 07:31:39PM -0700, John Kessenich wrote:

The specification does say a merge block is where control flow merges, that the constructs nest, and that they cannot share merge blocks. I'm not sure I know the exact definitions of "grouped" and "packed", but is there an example where control merges at a non merge block, and still satisfies these rules?

Ok, then I guess this is a must rule regarding control paths. That solves this issue of non-explicit merge blocks. Please, could you make the specs explicit about this must rule?

Regarding the physical ordering of blocks, I think the only rules are, of course, that non-forward reference rules, and also

The order of blocks in a function must satisfy the rule that blocks appear before all blocks they dominate.

The rules do intentionally stop short of laying out a canonical ordering for all forms of control flow, and instead give some minimum required constraints.

The "before" does not have any information on distance in the sprirv linear sequencing of blocks. This is what allows the block mangling of control flow paths.

I'm curious if there is a example that seems to adhere to the specification but leads to an undesirable consequence. That gives a specific thing to check against the spec, or to suggest a modification to the spec, motivated by preventing the undesirable consequence.

The big risk is to see spriv binaries including weird mangling of blocks from different control flow paths on purpose in order to be compiled only on some unreasonably complex "proprietary" spirv compiler components. This could foster vendor "lock-in" by (mandatory = non specs forbidden) non-pertinent complexity, which is a new naughty way of doing software nowadays.

---

I think spriv should enforce a canonical way to order blocks along control flow paths. Without this, control flow paths must be re-constructed from spirv linear sequence of blocks as control flow path mangling is allowed, since not "specs forbidden" or without a canonical block ordering definition.

It forces spirv compiler writting to be really less naive and simple.

If you want to keep allowing mangling of blocks from different control flow paths (thinking of selection constructs, mainly), it should be explicit in the specs as it is significant for compiler design (better very be warned about this), and remove the "one pass compilation" feature which seems more and more unreasonable (even if it's theorically do-able).

Then, what are your plans regarding those issues?

Best Regards.

[dneto0]

First, thanks @sylware for filing the issue in the right place and for being patient.

On Tue, Oct 04, 2016 at 07:31:39PM -0700, John Kessenich wrote: The specification does say a merge block is where control flow merges, that the constructs nest, and that they cannot share merge blocks. I'm not sure I know the exact definitions of "grouped" and "packed", but is there an example where control merges at a non merge block, and still satisfies these rules?

@sylware wrote:

Ok, then I guess this is a must rule regarding control paths. That solves this issue of non-explicit merge blocks. Please, could you make the specs explicit about this must rule?

I disagree with @johnkslang a bit here. The merge block is the last point where control flow will normally reconverge. But I think it's ok for control flow to get to a common block before the merge block. That is, this example of yours is valid:

    Header block -> A0 -> S -> Merge block
    Header block -> B0 -> S -> Merge block
    (A0,B0,S are members of the selection construct)

For one thing, such a rule allows a compiler to generate that kind of code when it is given code like this:

    Header block -> A0 -> A1 -> Merge block
    Header block -> B0 -> B1 -> Merge block
    (A0,B0,A1,B1 are members of the selection construct)

when it realizes that A1 and B1 have the same effect. (Of course, any OpPhi in the merge block have to be adjusted.)

I think the relaxed rule as it exists is ok, allowing freedom to implementors and optimizers. Now, there might be a quality tradeoff that encourages compilers to pull the merge block in as tightly as possible. That's a quality-of-results (e.g. performance) tradeoff rather than a correctness condition.

Secondly, about physical interleaving. There are Vulkan conformance tests that exercise weird but still valid interleavings. See the 100 lines or so starting at: https://github.com/KhronosGroup/Vulkan-CTS/blob/vulkan-cts-1.0-dev/external/vulkancts/modules/vulkan/spirv_assembly/vktSpvAsmInstructionTests.cpp#L1899

Any conformant Vulkan implementation must correctly handle that test. The strength of that test should help avoid the bad situation you're concerned about. There might be other tools that process SPIR-V modules that don't accept the more general block ordering, but I would consider that a bug in those tools.

[johnkslang]

I thought I was quoting the spec. 😄 Well, it says

These explicitly declare a header block before the control flow diverges and a merge block where control flow subsequently converges.

Do you want the spec to say control flow merges before or at the merge block, rather than implying just at the merge block?

[sylware]

On Wed, Oct 05, 2016 at 03:28:05PM -0700, John Kessenich wrote:

I thought I was quoting the spec. 😄 Well, it says

These explicitly declare a header block before the control flow diverges and a merge block where control flow subsequently converges.

Do you want the spec to say control flow merges before or at the merge block, rather than implying just at the merge block?

Not me, it's what David Neto wrote about this.

---

But it does not really matter now since:

On Wed, Oct 05, 2016 at 02:28:51PM -0700, David Neto wrote:

Secondly, about physical interleaving. There are Vulkan conformance tests that exercise weird but still valid interleavings. See the 100 lines or so starting at: https://github.com/KhronosGroup/Vulkan-CTS/blob/vulkan-cts-1.0-dev/external/vulkancts/modules/vulkan/spirv_assembly/vktSpvAsmInstructionTests.cpp#L1899

This is what I feared: you can mangle "hardcore" all the blocks, and implementations have to handle such complexity to be compliant. It means control flow paths must be reconstructed from a potential soup of blocks.

My personal opinion is spirv should have defined a canonical way to order blocks along control flow paths.

At least, the specs should warn, "violently and explicitely", implementors that they can face such a soup of blocks.

best regards.

[sylware]

Are you going to warn the implementors about the "soup of blocks" in an update of the current 1.x specs? (i.e. "you have to reconstruct the control flow paths"). Are you going to define a canonical way to order blocks (at least for programs with shader capability)? If so, what is the plan: SPIR-V 2.0 or 1.x?

[dneto0]

We discussed this at the SPIR working group. In the next revisions of 1.0 and 1.1 we plan to do the following:

In the validation rules for Control Flow Graph, after the sentence:

The order of blocks in a function must satisfy the rule that blocks appear before all blocks they dominate.

add a sentence

There are no further guarantees about block ordering.

[sylware]

It's a good thing as it will warn any futur implementors they have to reconstruct control flow paths as they cannot trust the block sequences.

Then for SPIR-V 1.2 or 2.0, a canonical way to order blocks, at least for programs with the shader capability, would be more than welcome as it would make possible to implement way more trivial and naïve (then more robust) spir-v compilers.

[sylware]

Still a thing or we can close this one?

[johnkslang]

We think this is adequately covered by the specification saying:

The order of blocks in a function must satisfy the rule that blocks appear before all blocks they dominate.