<table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Issue</th>
<td>
<a href=https://github.com/llvm/llvm-project/issues/87763>87763</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>
[SPIR-V] OpSwitch doesn't represent original CFG
</td>
</tr>
<tr>
<th>Labels</th>
<td>
new issue
</td>
</tr>
<tr>
<th>Assignees</th>
<td>
VyacheslavLevytskyy
</td>
</tr>
<tr>
<th>Reporter</th>
<td>
VyacheslavLevytskyy
</td>
</tr>
</table>
<pre>
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
if.then.i: ; preds = %sw.epilog
br label %exit
for.cond.i: ; preds = %for.inc.i, %if.then.i
br label %exit
for.inc.i: ; preds = %for.cond.i
br label %exit
if.end.i: ; preds = %for.cond.i, %if.then.i
br label %exit
if.end18.thread.i: ; preds = %if.end.i
br label %5
for.cond8.i: ; preds = %for.inc14.i, %if.end.i
br label %exit
for.inc14.i: ; preds = %for.cond8.i
br label %exit
if.end18.i: ; preds = %for.cond8.i
br label %5
5: ; preds = %if.end18.i, %if.end18.thread.i
br label %for.cond25.i
for.cond25.i: ; preds = %for.body29.i, %5
br label %exit
for.cond.cleanup27.i: ; preds = %for.cond25.i
br label %for.cond41.i
for.body29.i: ; preds = %for.cond25.i
br label %for.cond25.i
for.cond41.i: ; preds = %for.body45.i, %for.cond.cleanup27.i
br label %exit
for.cond.cleanup43.i: ; preds = %for.cond41.i
br label %exit
for.body45.i: ; preds = %for.cond41.i
br label %for.cond41.i
exit:
ret void
}
```
will result into SPIR-V with -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".
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzEWVtv2zoS_jXKy8CCRUm-POQhbeAiQPeCttvXA4ocWTylSS1JJfX--gUpyZZl2XHa4JyicEtprt-MOBwOtVZsFeJ9lH-ICPm-p6xCK-nzZ3zeO_tjv48IifLHO9q4Spv7CYK7QvP9_UNdG01ZBU5DbXAmcUul-B91QivQJVCwL8KxCqyjDneoHAgLSjughUTPtUWFhjoEpo1B5uBf9deWRSjrTMO8KBvDkwOu0aqILB1QxnSjHJTagKFqixyY3tXUCKuVhZdKsAqoQaDyhe7tQQkH3hihtvD0BZyhysrWUuuwhoisLCJIUURk81Fz_IQqIptPUhdUPn1FGZHN05dvHZs2MavrKH1YJnlE1nE0f4zmD-3vE1DnPCoUmG5qiR4K_El3deuzq4QFYW2DYLDWxsXwpKAwAsuIfDwicHTYYG3Qevi0EVuhqISPm08gFDBq0XuMCobGAdPqGY2zA2BA2Bn-t6HS23AOWwzfqi4MttaKe5y8dJC0QGkDnlt0zj-X2jqvPXjiibzdQjHZBDYqrQaOJW2ka9ljeFAeFdzVLqjHF21-tPzUAgWpGZVQU--3LsFVeJ5QIUwlFTIEsoMSu-hKoH0yXuUXzqIsfUJFZGlB7GptreiycUdreKayQetXBbWCQSE1-9FBbPUuBLOj8ZBUgnNUPlsFx6D3DFoPzotwlW4c7LTB8EoKFjLS4o4qJxiVcg-sQq-rc-CYtsX-NLqcbk8yLlrMu79hybEUCsHWwvxRNorBsxYcomxeah2RlVhkoHSjOJYQkZxybkL8Ro9tRNYQLT-0MlE5s4_STiF4ijlE6SMI5ZyunQn8gS_sBs6AF2xryjAiqywi6wFrElilphzEyiufog86BkxsV7ca_X_s1oFYBVme_0BXGBBJR-1fhPTza1HGrkI1foaKD5HsqdIHiNIPPoe4DUojkrcQHO2hnMfebv96iw5l2OECFKrwQNpXnetgTwZSya3QdOoHjl_3yz9JH-D2P2cADCCcgMNWlOuXP8K3Ec9joQJbXYkQp_xDcK7j7SRBlD-GJ-3bZCg5vOukd1WkjfeZnpOQ2pe433l8desEgOedJWQ5psVaSL0dky3GZEWRjmnyc5psRJMk5zT5mGZ-TrMY0czX5zTLEc2EOasRSfY6Sfo6CZkQsz6lWU8Yk8zHciZ0JccPoQ9--9uFYOqrHOb66VcwCu9AUvb7H8KbdebvZv3i3SQt_wYcVtesP-wOZ4s36Vj_DX4l83cLS5K8k6huJ7wdjXfQ2T2ccmBgURvb3tvhaj5crYeL1XCxHC4Ww0U-XGTDRfpqSuFP4SaOA7F4Q0JNuX1aZq5pLH1noRVvVZ7J8q-FYrE4LaSxuFV2y_wb3gwMvA1AvOpMJ-oXvGlFJ6vYVQYpv8mrC_k9rTCfisvqemCSbOjMRdEXIhO4b43NRThXb8TvenAuSDsB51ptCwqGiAwj1goeyu3Vkrx_fYp_eH7J3kLzPVkf9OVv-uCYRKqamixfj8FFsI5Ww6RXWXLu1cHoa1F4TfAluILCGzPqIqRZfoB0Eq1fQDlLfwPlI4qvKz3Yfw3dSwIvhS0oOvbCBl1osTuS5eNkV97-vggpwaD1DYpQTsPXfz99mX0PFwT9AXyWZEAV96f6_vYl3Lj4Z7R0aMDgMxqLJ7dYTsPnz9__AU9fYK8beNGN5GARr1wUxHH8xgauL7vZqHXrS-v8F9u2ZPV6u5asr_dpZ69P25CzDmTUnh2bj-nWLCHX27LkrEU87ZSS_GqXlIy7vlGDlPQd36g1euNZd_rLWk3sxD3c7W97vH0nNdf0TJ99b-Ekv8w53Vnewpn1nP8MN-AcGVqrjY1IcgN3_o6YXlGz-ItCt_xlGKebwls415OcSd8rJP2GlfQ9QtL3B0nfGyT95pX011OHluTQjfSNyKRJ5GSHJ9ON4HH3ulAuDpvxZN14kFZ7G7QKN9Cfn76BQ-vs8bZb_4ksNFb--ckMw5eY7xHZFIYqVgm1jcimnzL8RxmkrKKFxFhKz85xp5V1hjq0QbSluyC_kLhr78GFA-uocTaUrSsF5lgDUuJBCLv_ybbWHPWPKkBK4HQDPhCeEiXXiY7b5RSsvqS21diGcvxbvpBzD0Yl5jajCmS0segr-eDS_8_GhkmQpAzbqUs_hwhnBwqinFm3l9iOEbxiq8FV1F0Zh0ht0XtealCIHHk7nZkxg9QhfNx8Ohk0zGaz4fJbm3i1tshBcKTt0K8UP0GEMcBx0gG4E24mlDNCWcFsq97Dv0UHRvA-kYXqR4EfN58OpniDu-HdRWfaCZZ11DXDz6K1rrMpIkSoZ7RObA9TyhKpFYWQwu0jQuI7fp_ydbqmd3ifLBOSJvP1cnVX3S-SjBVplqxLyvKCrtI043yO2bJkLKOL9Z24J3OSzbN5Pl_ni2QVZ6tVsVimLF3yvEwWWZTNcUeFjKV83sXabO_CGPB-tVwu0rv2qNcNZRW-tDPCbhRr7j3PrGi2NsrmUlhnj1KccDJMc9vDZJQ_3j5FvGuMvK-cq60_0ZJNRDZb4aqmiJneRWTjlXT_zA6bzCaYZiOyCab_PwAA__9av2jQ">