Vulkan conformance test gets access violation in spvValidate about spirv-tools

[antiagainst]

Looping in @umar456 since he has better understanding of the validator.

[umar456]

Looking into it now

[antiagainst]

I haven't looked into this carefully, but I can reproduce a segfault using SDK 1.0.21 with VK_INSTANCE_LAYERS=VK_LAYER_LUNARG_standard_validation.

Test case dEQP-VK.glsl.functions.control_flow.return_in_loop_vertex triggers a segfault. Here is its source code. (Well, meta source code, maybe.)

[antiagainst]

And this is a .vert test case that will blow up the validator:

#version 310 es

float func (float a)
{
  while (a < 100.0)
    return -a;
  return 1.0;
}

void main()
{
  float t = func(50.0);
}

[umar456]

Thanks. I have reproduced the error. I should have a fix shortly

[antiagainst]

It seems to me that glslang is generating SPIR-V violating structured control flow rules.

Here is the disassembly of the above program:

               OpCapability Shader
          %1 = OpExtInstImport "GLSL.std.450"
               OpMemoryModel Logical GLSL450
               OpEntryPoint Vertex %main "main"
               OpSource ESSL 310
               OpSourceExtension "GL_GOOGLE_cpp_style_line_directive"
               OpSourceExtension "GL_GOOGLE_include_directive"
               OpName %main "main"
               OpName %func_f1_ "func(f1;"
               OpName %a "a"
               OpName %t "t"
               OpName %param "param"
       %void = OpTypeVoid
          %3 = OpTypeFunction %void
      %float = OpTypeFloat 32
%_ptr_Function_float = OpTypePointer Function %float
          %8 = OpTypeFunction %float %_ptr_Function_float
         %18 = OpConstant %float 100
       %bool = OpTypeBool
         %24 = OpConstant %float 1
         %28 = OpConstant %float 50
       %main = OpFunction %void None %3
          %5 = OpLabel
          %t = OpVariable %_ptr_Function_float Function
      %param = OpVariable %_ptr_Function_float Function
               OpStore %param %28
         %30 = OpFunctionCall %float %func_f1_ %param
               OpStore %t %30
               OpReturn
               OpFunctionEnd
   %func_f1_ = OpFunction %float None %8
          %a = OpFunctionParameter %_ptr_Function_float
         %11 = OpLabel
               OpBranch %12
         %12 = OpLabel
               OpLoopMerge %14 %15 None
               OpBranch %16
         %16 = OpLabel
         %17 = OpLoad %float %a
         %20 = OpFOrdLessThan %bool %17 %18
               OpBranchConditional %20 %13 %14
         %13 = OpLabel
         %21 = OpLoad %float %a
         %22 = OpFNegate %float %21
               OpReturnValue %22
         %15 = OpLabel
               OpBranch %12
         %14 = OpLabel
               OpReturnValue %24
               OpFunctionEnd

Loop header: %12
Merge block: %14
Continue target: %15

There is no continue block since there is no block "containing a branch to an OpLoopMerge instruction’s Continue Target."
There is no back edge block since Block %15 is not reachable at all, so doing a DF traversal from %11 won't encounter any back edge.

So, one SPIR-V structured control flow rules---all CFG back edges must branch to a loop header, with each loop header having exactly one back edge branching to it---is violated because of no back edge branching to the loop header.

With that said, the validator should still print an error instead of segfault.

But I feel I'm quite clumsy and dumb regarding interpreting the SPIR-V structured control flow spec. So it would be very nice if @johnkslang could shed some light on this issue.

[umar456]

Well %15 is the continue block because it is specified as the continue target of OpLoopMerge %14 %15 None and it is branching back to the loop header so it is a complete loop construct.

There doesn't seem to be a back-edge or a back-edge block as defined by the spec.

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.

The back-edge block should be %15 but the block cannot be reached in the CFG from the first block of the function. It should be reachable from the pseudo_entry block but this construct is not defined in the spec itself.

I don't know how else this function would be implemented in SPIR-V(unless we create an unconditionally false branch to the continue target which seems like a messy solution).

[antiagainst]

Hmm, my interpretation of "Continue Block: A block containing a branch to an OpLoopMerge instruction’s Continue Target" in the spec is, continuing block is the block jumping to the continue target, not the continue target block itself. For this case, %15 is the continue target, and it doesn't contain a branch to itself, so it is not the continue block.

[umar456]

Ahh sorry. You are right. I was confusing the continue construct with the continue block.

[dneto0]

Fixed with 6c61bf2

[johnkslang]

So, one SPIR-V structured control flow rules---all CFG back edges must branch to a loop header, with each loop header having exactly one back edge branching to it---is violated because of no back edge branching to the loop header.

I see the last instruction in the loop OpBranch %12 as a branch back up to the loop header. I'm not quite clear on where the spec. is being violated here. Further, the specification says

each loop header having exactly one back edge branching to it

I don't immediately see where it says that branch must be reachable. Does it say that?

Or, is the problem truly solved, with no remaining questions?

[umar456]

The back-edge is defined in a way that implies that it needs to be reachable. Here is the text:

/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.

The branch up to the loop header is not reachable from the first block of the function so it is not part of the back-edge set.

Open Question:
Is this an acceptable definition of the back-edge or is it too restrictive?
How should the shader that raised the issue be represented in SPIR-V with the current definition?

[antiagainst]

+1 to what @umar456 said. That's my interpretation of the spec too.

[johnkslang]

Okay, so this is a side effect of adding a definition that was not originally there, and having the definition be too restrictive (it wasn't part of the core rule set for making all this work). I don't yet see the real reason the back edge must be reachable.

[dneto0]

The validator crash is resolved (software issue).
Still open is whether the given module uses valid structured control flow.

My opinion is +1 to what @umar456 said.

The spec's definition for back-edge is non-standard. (My reference is https://en.wikipedia.org/wiki/Depth-first_search)
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.

[dneto0]

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.

[johnkslang]

@dneto0 sounds right; I'm transferring this to the headers project, at: KhronosGroup/SPIRV-Headers#16.

[dneto0]

+1 to moving the spec issue elsewhere.

While I still have this in my head:

• The validator uses the wikipedia sense of "back-edge".
• A couple of weeks ago (5065227 ) I changed the traversals in the validator to use an "augmented CFG" for the depth-first-search: add a pseudo-entry node before doing the DFS (a pseudo-exit node already existed). The point was to make the code and invariants more regular in the face of weird cases. In particular, unreachable nodes in the regular CFG end up being visited in the augmented CFG. And so the "back-edge" in the case given above ends up looking like a cross-edge in the augmented CFG, but also where the source is not dominated by the entry block.