Violation of the requirement to have exactly one Parent ID operand for each parent block of the current block in the CFG

[VyacheslavLevytskyy]

It's a requirement of the SPIR-V specification (https://registry.khronos.org/SPIR-V/specs/unified1/SPIRV.html#OpPhi) that "There must be exactly one Parent i for each parent block of the current block in the CFG.". However, for the snippet %retval.0.i = phi i32 [ 0, %sw.default.i ], [ 1, %entry ], [ 1, %entry ] from the following reproducer

define spir_kernel void @foo(i8 %arg) {
entry:
  switch i8 %arg, label %sw.default.i [
    i8 -127, label %exit
    i8 -111, label %exit
  ]

sw.default.i:                                     ; preds = %entry
  br label %exit

exit: ; preds = %sw.default.i, %entry, %entry
  %retval.0.i = phi i32 [ 0, %sw.default.i ], [ 1, %entry ], [ 1, %entry ]
  ret void
}

Translator would generate invalid SPIR-V output containing the following fragment:

%retval_0_i = OpPhi %uint %uint_0 %sw_default_i %uint_1 %entry %uint_1 %entry

When validating Translator's output we get the following error:

$ llvm-as phi-multiple-preds.ll -o - | /localdisk2/vlevytsk/sycl/llvm/build/bin/llvm-spirv.bak -o - | spirv-val
error: line 26: OpPhi's number of incoming blocks (3) does not match block's predecessor count (3).
  %retval_0_i = OpPhi %uint %uint_0 %sw_default_i %uint_1 %entry %uint_1 %entry

SPIR-V Backend generates correctly %retval_0_i = OpPhi %uint %uint_0 %13 %uint_1 %12 where there is just one record per 2 original %entry predecessors, however, this output of SPIR-V Backend gets rejected by Translator's reverse conversion of SPIR-V to LLVM IR as the following:

$ llvm-spirv -r phi-preds.spv
Fails to verify module: PHINode should have one entry for each predecessor of its parent basic block!
  %retval.0.i = phi i32 [ 0, %2 ], [ 1, %0 ]

This error is caused by the 1:1 mapping of PHI operands back to LLVM IR so that llvm's machine verifier gets unhappy when it sees just 1 phi entry for two predecessors.

Original reproducer comes from new SYCL tests from AddressSanitizer/* that produce this specific case of multiple predecessors, showing the failure to meet the requirement of the SPIR-V specification. @MrSidims also has succeeded to create a C reproducer: https://godbolt.org/z/73cj6aE3n

[VyacheslavLevytskyy]

Full outputs, just for the reference:

$ llvm-as phi-multiple-preds.ll -o - | llvm-spirv -o - | spirv-dis
; SPIR-V
; Version: 1.0
; Generator: Khronos LLVM/SPIR-V Translator; 14
; Bound: 14
; Schema: 0
               OpCapability Addresses
               OpCapability Kernel
               OpCapability Int8
          %1 = OpExtInstImport "OpenCL.std"
               OpMemoryModel Physical64 OpenCL
               OpEntryPoint Kernel %5 "foo"
               OpSource Unknown 0
               OpName %arg "arg"
               OpName %entry "entry"
               OpName %sw_default_i "sw.default.i"
               OpName %exit "exit"
               OpName %retval_0_i "retval.0.i"
      %uchar = OpTypeInt 8 0
       %uint = OpTypeInt 32 0
     %uint_0 = OpConstant %uint 0
     %uint_1 = OpConstant %uint 1
       %void = OpTypeVoid
          %4 = OpTypeFunction %void %uchar
          %5 = OpFunction %void None %4
        %arg = OpFunctionParameter %uchar
      %entry = OpLabel
               OpSwitch %arg %sw_default_i 129 %exit 145 %exit
%sw_default_i = OpLabel
               OpBranch %exit
       %exit = OpLabel
 %retval_0_i = OpPhi %uint %uint_0 %sw_default_i %uint_1 %entry %uint_1 %entry
               OpReturn
               OpFunctionEnd
$ llvm-as phi-multiple-preds.ll -o - | llvm-spirv -o - | spirv-val
error: line 26: OpPhi's number of incoming blocks (3) does not match block's predecessor count (3).
  %retval_0_i = OpPhi %uint %uint_0 %sw_default_i %uint_1 %entry %uint_1 %entry

$ llc -O0 -mtriple=spirv64-unknown-unknown phi-multiple-preds.ll -o - --filetype=obj | spirv-dis
; SPIR-V
; Version: 1.4
; Generator: LLVM LLVM SPIR-V Backend; 20
; Bound: 27
; Schema: 0
               OpCapability Kernel
               OpCapability Addresses
               OpCapability Int8
               OpCapability Int64
          %1 = OpExtInstImport "OpenCL.std"
               OpMemoryModel Physical64 OpenCL
               OpEntryPoint Kernel %foo "foo"
               OpExecutionMode %foo ContractionOff
               OpSource OpenCL_CPP 100000
               OpName %arg "arg"
               OpName %foo "foo"
               OpName %retval_0_i "retval.0.i"
      %uchar = OpTypeInt 8 0
       %void = OpTypeVoid
          %4 = OpTypeFunction %void %uchar
       %uint = OpTypeInt 32 0
      %ulong = OpTypeInt 64 0
     %uint_1 = OpConstant %uint 1
     %uint_0 = OpConstant %uint 0
        %foo = OpFunction %void None %4
        %arg = OpFunctionParameter %uchar
         %12 = OpLabel
               OpSwitch %arg %13 129 %14 145 %14
         %13 = OpLabel
               OpBranch %14
         %14 = OpLabel
 %retval_0_i = OpPhi %uint %uint_0 %13 %uint_1 %12
               OpReturn
               OpFunctionEnd
$ llc -O0 -mtriple=spirv64-unknown-unknown phi-multiple-preds.ll -o - --filetype=obj | spirv-val

$ llc -O0 -mtriple=spirv64-unknown-unknown phi-multiple-preds.ll -o phi-multiple-preds.spv --filetype=obj
$ spirv-val phi-multiple-preds.spv
$ llvm-spirv -r phi-multiple-preds.spv
Fails to verify module: PHINode should have one entry for each predecessor of its parent basic block!
  %retval.0.i = phi i32 [ 0, %2 ], [ 1, %0 ]

[VyacheslavLevytskyy]

@bashbaug @MrSidims @asudarsa This is an interesting case when LLVM IR and SPIR-V differ so much in requirements. The former seemingly keeps a separate predecessor vertex per each reference from the parent block, representing them as individual phi's arguments. The latter requires that each reference from the parent block is represented by exactly one operand of OpPhi. I guess that Translator's troubles in this case of reverse translation are caused by the fact that it's not possible to generate LLVM IR output from the local context. E.g., OpPhi %uint %uint_0 %1 %uint_1 %2 has no hints to produce two identical phi entries for %2, Translator would need to analyze the global context to figure out the correct number of predecessors.
What do you think about this issue and possible fix options?

[MrSidims]

@MrSidims also has succeeded to create a C reproducer: https://godbolt.org/z/73cj6aE3n

Just to clarify (since it took some time for me to remember the context looking at the snippet): need to uncomment lines 12 and 13 :)