[SPIR-V] OpSwitch doesn't represent original CFG

[VyacheslavLevytskyy]

Approach to pre-legalization of a switch statement is not able to generate correct OpSwitch instructions. It doesn't account for ranged comparisons which are always generated during IR translation step (see lib/CodeGen/GlobalISel/IRTranslator.cpp:715).

I attach a couple of example to this issue report. In brief, OpSwitch doesn't represent original CFG in cases when IRTranslator converts comparison is-equal to ranged comparisons. The corresponding case labels are getting lost in this case, including also default label. An attempt to rework this as a local patch of the pre-legalization step failed due to the general approach of the pre-legalization step itself. It's impossible to map values to basic blocks when some of values are hidden inside the ranged comparison, without more complicated semantically checks of the generated by IRTranslator dag.

define spir_func void @foo(i64 noundef %addr, i64 noundef %as) {
entry:
  %0 = inttoptr i64 %as to ptr addrspace(4)
  %1 = load i8, ptr addrspace(4) %0
  %cmp = icmp sgt i8 %1, 0
  br i1 %cmp, label %if.then, label %if.end

if.then:                                          ; preds = %entry
  %add.ptr = getelementptr inbounds i8, ptr addrspace(4) %0, i64 1
  %2 = load i8, ptr addrspace(4) %add.ptr
  br label %if.end

if.end:                                           ; preds = %if.then, %entry
  %shadow_value.0.in = phi i8 [ %2, %if.then ], [ %1, %entry ]
  switch i8 %shadow_value.0.in, label %sw.default [
    i8 -127, label %sw.epilog
    i8 -126, label %sw.bb3
    i8 -125, label %sw.bb4
    i8 -111, label %sw.bb5
    i8 -110, label %sw.bb6
    i8 -109, label %sw.bb7
    i8 -15, label %sw.bb8
    i8 -14, label %sw.bb8
    i8 -13, label %sw.bb8
    i8 -124, label %sw.bb9
    i8 -95, label %sw.bb10
    i8 -123, label %sw.bb11
  ]

sw.bb3:                                           ; preds = %if.end
  br label %sw.epilog

sw.bb4:                                           ; preds = %if.end
  br label %sw.epilog

sw.bb5:                                           ; preds = %if.end
  br label %sw.epilog

sw.bb6:                                           ; preds = %if.end
  br label %sw.epilog

sw.bb7:                                           ; preds = %if.end
  br label %sw.epilog

sw.bb8:                                           ; preds = %if.end, %if.end, %if.end
  br label %sw.epilog

sw.bb9:                                           ; preds = %if.end
  br label %sw.epilog

sw.bb10:                                          ; preds = %if.end
  br label %sw.epilog

sw.bb11:                                          ; preds = %if.end
  br label %sw.epilog

sw.default:                                       ; preds = %if.end
  br label %sw.epilog

sw.epilog:                                        ; preds = %sw.default, %sw.bb11, %sw.bb10, %sw.bb9, %sw.bb8, %sw.bb7, %sw.bb6, %sw.bb5, %sw.bb4, %sw.bb3, %if.end
  br label %exit

exit:
  ret void
}

will result into SPIR-V with CFG broken and -13, -14 and -15 labels lost and after reverse translation to LLVM IR you would see

...
  %shadow_value.0.in = phi i8 [ %7, %4 ], [ %3, %0 ]
  switch i8 %shadow_value.0.in, label %18 [
    i8 -127, label %19
    i8 -126, label %9
    i8 -125, label %10
    i8 -111, label %11
    i8 -110, label %12
    i8 -109, label %13
    i8 -124, label %15
    i8 -95, label %16
    i8 -123, label %17
  ]

9:                                                ; preds = %8
  br label %19

10:                                               ; preds = %8
  br label %19

11:                                               ; preds = %8
  br label %19

12:                                               ; preds = %8
  br label %19

13:                                               ; preds = %8
  br label %19

14:                                               ; No predecessors!
  br label %19

15:                                               ; preds = %8
  br label %19

16:                                               ; preds = %8
  br label %19

17:                                               ; preds = %8
  br label %19

18:                                               ; preds = %8
  br label %19

19:                                               ; preds = %18, %17, %16, %15, %14, %13, %12, %11, %10, %9, %8
  br label %20

20:                                               ; preds = %19
  ret void
}
...

Also, one of LIT tests of the project, test/CodeGen/SPIRV/branching/OpSwitchUnreachable.ll, demonstrates the same problem when it starts with

  switch i32 %value, label %unreachable [
    i32 0, label %reachable
    i32 1, label %reachable
  ]

and results into

  switch i32 %value, label %2 [
    i32 1, label %1
  ]

because IR Translator just replaces case values with a if-style check, so that the pre-legalization step loses info needed to re-create CFG.

---

The proposed idea of a fix is to complicate emit-intrinsics step and get rid of the incorrect CFG re-creation during the pre-legalization step. The status of the proposed fix is "investigation of feasibility".

[VyacheslavLevytskyy]

Fixed by #87823