spirv-opt improper inlining OpKill into continue construct

[programmerjake]

@alan-baker asked me to open this issue here from KhronosGroup/SPIRV-Headers#86

Original issue:
Is a continue construct that consists of OpKill valid? If so, the rules on the header block post-dominating the continue construct need to be fixed. Otherwise, there's a bug in spirv-opt where kill() is improperly inlined.

http://shader-playground.timjones.io/1323167d9be3ec6d7a54996e098612de

spirv-opt output:

; SPIR-V
; Version: 1.0
; Generator: Khronos Glslang Reference Front End; 7
; Bound: 13
; Schema: 0
               OpCapability Shader
          %1 = OpExtInstImport "GLSL.std.450"
               OpMemoryModel Logical GLSL450
               OpEntryPoint Fragment %main "main"
               OpExecutionMode %main OriginUpperLeft
               OpSource GLSL 330
               OpName %main "main"
       %void = OpTypeVoid
          %3 = OpTypeFunction %void
       %main = OpFunction %void None %3
          %5 = OpLabel
               OpLoopMerge %11 %12 None
               OpBranch %12
         %12 = OpLabel
               OpKill
         %11 = OpLabel
               OpUnreachable
               OpFunctionEnd

spirv-opt input:

// Module Version 10000
// Generated by (magic number): 80007
// Id's are bound by 17

                              Capability Shader
               1:             ExtInstImport  "GLSL.std.450"
                              MemoryModel Logical GLSL450
                              EntryPoint Fragment 4  "main"
                              ExecutionMode 4 OriginUpperLeft
                              Source GLSL 330
                              Name 4  "main"
                              Name 6  "kill("
               2:             TypeVoid
               3:             TypeFunction 2
              14:             TypeBool
              15:    14(bool) ConstantTrue
         4(main):           2 Function None 3
               5:             Label
                              Branch 9
               9:             Label
                              LoopMerge 11 12 None
                              Branch 13
              13:             Label
                              BranchConditional 15 10 11
              10:               Label
                                Branch 12
              12:               Label
              16:           2   FunctionCall 6(kill()
                                Branch 9
              11:             Label
                              Return
                              FunctionEnd
        6(kill():           2 Function None 3
               7:             Label
                              Kill
                              FunctionEnd

[s-perron]

This is a complicated issue, and it is not clear how to handle this case. The problem is that before inlining it looks like the continue target branches back the to loop header, but it does not. The function never returns. Inlining keeps the same semantics, it just exposes that the function never returns.

No solutions seems obvious. We cannot create a new dummy continue target of the function call has no return because other parts of the code have to be able to jump to the continue target. Breaking from the loop and doing the OpKill out of the loop only works if it is executed unconditionally.

This will require some careful thought. I'll have to get back to it when I return from vacation in a couple weeks.

[programmerjake]

My preferred solution (and the one I implemented in Kazan) is to treat the continue construct like a case construct in that it can fall through to the loop header, jump to merge targets, execute OpKill, and execute OpReturn*.

Continue construct parsing in implementation of structure parser (structures somewhat modified but map directly to official structures):
https://salsa.debian.org/Kazan-team/kazan/blob/5f073ca0d589f73ee72597c232529414dee7bcf7/shader-compiler/src/cfg/structure_tree.rs#L706-728

[s-perron]

@programmerjake What code that does come from? I'm guessing that this is glsl code where the function in the continue contains an OpKill somewhere in the call tree. Is this a common pattern? From what I can tell, the current version of the spec allows the OpKill in the continue construct, but I don't believe it was intended. I'm trying to get clarification on this. Having an idea of what is done in real code might be useful.

[programmerjake]

@s-perron It does come from glsl that has a call inside a continue construct to a function that has discard in it. I don't have any real use-cases for such code, I was trying to determine the limits of what the SPIR-V to LLVM compiler I am writing would have to handle.

[s-perron]

There was a bug in the fix for this issue. I had to be reverted.

[s-perron]

The solution I had relies on two analysies: dominator trees and inst-to-block. Neither of which are kept up-to-date during inlining. So if we have A calls B class C. First we inline B into A. Then, when trying to inline C into A, the inst-to-block mapping it out of date and we get a segmentation fault.

[programmerjake]

The solution I had relies on two analysies: dominator trees and inst-to-block. Neither of which are kept up-to-date during inlining. So if we have A calls B class C. First we inline B into A. Then, when trying to inline C into A, the inst-to-block mapping it out of date and we get a segmentation fault.

maybe add a map with "function contains reachable OpKill" and track during inlining?

[s-perron]

My code had a map. The problem was determining if the function all is inside of a continue construct. To determine that, I need the basic block the function call belongs to (inst-to-block mapping) and know that it dominated by the continue target for the loop it is in (dominator-trees).

If I simply chose to not inline any function containing an OpKill, then many shader will be able to be correctly legalized. We would have to implement #2726 first.

I will see if there is another way to keep track of whether or not we are in a continue construct.

[programmerjake]

create a map tracking which call instructions are in continue constructs? that shouldn't be that hard to track and can be used in conjunction with the opkill-containing map to stop inlining.

another alternative is to create a separate function with a body that's just OpKill and replace all other opkills with a call to that function (edit: idea was already in #2726)