Vulkan conformance test gets access violation in spvValidate

[antiagainst]

Specifics
Windows 7, Nvidia GTX 660 Ti, Driver 368.39

Have Vulkan SDK 1.0.21 installed for validation layers and set environment variable VK_INSTANCE_LAYERS=VK_LAYER_LUNARG_standard_validation

To reproduce I run all of the dEQP-VK.glsl.functions.control_flow.* tests from the Vulkan Conformance Test Suite

Message:
Exception thrown: read access violation.
this was nullptr. (debugger confirms that variable "this" is NULL)

Location:
BasicBlock.h:

76 /// Returns true if the block is reachable in the CFG
77 bool reachable() const { return reachable_; }

Call Stack:

    VkLayer_core_validation.dll!libspirv::BasicBlock::reachable() Line 77   C++

    VkLayer_core_validation.dll!libspirv::StructuredControlFlowChecks(const libspirv::ValidationState_t & _, const libspirv::Function & function, const std::vector<std::pair<unsigned int,unsigned int>,std::allocator<std::pair<unsigned int,unsigned int> > > & back_edges) Line 349 C++

    VkLayer_core_validation.dll!libspirv::PerformCfgChecks(libspirv::ValidationState_t & _) Line 478    C++

    VkLayer_core_validation.dll!spvValidate(const spv_context_t * const context, spv_const_binary_t * const binary, spv_diagnostic_t * * pDiagnostic) Line 209  C++

    VkLayer_core_validation.dll!core_validation::CreateShaderModule(VkDevice_T * device, const VkShaderModuleCreateInfo * pCreateInfo, const VkAllocationCallbacks * pAllocator, VkShaderModule_T * * pShaderModule) Line 9069  C++

    VkLayer_object_tracker.dll!object_tracker::CreateShaderModule(VkDevice_T * device, const VkShaderModuleCreateInfo * pCreateInfo, const VkAllocationCallbacks * pAllocator, VkShaderModule_T * * pShaderModule) Line 3583    C++

    VkLayer_parameter_validation.dll!parameter_validation::CreateShaderModule(VkDevice_T * device, const VkShaderModuleCreateInfo * pCreateInfo, const VkAllocationCallbacks * pAllocator, VkShaderModule_T * * pShaderModule) Line 2621    C++

    VkLayer_threading.dll!threading::CreateShaderModule(VkDevice_T * device, const VkShaderModuleCreateInfo * pCreateInfo, const VkAllocationCallbacks * pAllocator, VkShaderModule_T * * pShaderModule) Line 1133  C++

    deqp-vk.exe!vk::DeviceDriver::createShaderModule(vk::VkDevice_s * device, const vk::VkShaderModuleCreateInfo * pCreateInfo, const vk::VkAllocationCallbacks * pAllocator, vk::Handle<14> * pShaderModule) Line 218  C++

    deqp-vk.exe!vk::createShaderModule(const vk::DeviceInterface & vk, vk::VkDevice_s * device, const vk::VkShaderModuleCreateInfo * pCreateInfo, const vk::VkAllocationCallbacks * pAllocator) Line 209    C++

    deqp-vk.exe!vk::createShaderModule(const vk::DeviceInterface & deviceInterface, vk::VkDevice_s * device, const vk::ProgramBinary & binary, unsigned int flags) Line 206 C++
    deqp-vk.exe!vkt::`anonymous namespace'::PipelineProgram::PipelineProgram(vkt::Context & context, const glu::sl::ShaderCaseSpecification & spec) Line 745    C++

    deqp-vk.exe!vkt::`anonymous namespace'::ShaderCaseInstance::ShaderCaseInstance(vkt::Context & context, const glu::sl::ShaderCaseSpecification & spec) Line 1410 C++

    deqp-vk.exe!vkt::`anonymous namespace'::ShaderCase::createInstance(vkt::Context & context) Line 1791    C++

    deqp-vk.exe!vkt::TestCaseExecutor::init(tcu::TestCase * testCase, const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & casePath) Line 246   C++

    deqp-vk.exe!tcu::TestSessionExecutor::enterTestCase(tcu::TestCase * testCase, const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & casePath) Line 181   C++

    deqp-vk.exe!tcu::TestSessionExecutor::iterate() Line 101    C++

    deqp-vk.exe!tcu::App::iterate() Line 172    C++

    deqp-vk.exe!main(int argc, const char * * argv) Line 55 C++
    [External Code] 

Bisected to spirv-tools commit: f61db0b
Validator structured flow checks: back-edge, constructs

Originally posted by @Tony-LunarG in google/shaderc#234:

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