<table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Issue</th>
<td>
<a href=https://github.com/llvm/llvm-project/issues/55667>55667</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>
[SimplifyCFG] Missed opportunity to turn a switch into a table lookup
</td>
</tr>
<tr>
<th>Labels</th>
<td>
llvm:optimizations,
missed-optimization
</td>
</tr>
<tr>
<th>Assignees</th>
<td>
</td>
</tr>
<tr>
<th>Reporter</th>
<td>
lattner
</td>
</tr>
</table>
<pre>
The following IR should be changable into a lookup table, we currently leave it to the backend which generates a jump table which is less efficient:
```
%"class.Thing" = type { i8 }
define %"class.Thing"* @test(%"class.Thing"* returned %0, i64 %1) unnamed_addr #0 align 2 {
%3 = trunc i64 %1 to i8
switch i8 %3, label %18 [
i8 66, label %4
i8 -117, label %5
i8 -122, label %6
i8 -115, label %7
i8 1, label %8
i8 -119, label %9
i8 98, label %10
i8 -121, label %11
i8 65, label %12
i8 67, label %13
i8 99, label %14
i8 -116, label %15
i8 -118, label %16
i8 -120, label %17
]
4: ; preds = %2
br label %18
5: ; preds = %2
br label %18
6: ; preds = %2
br label %18
7: ; preds = %2
br label %18
8: ; preds = %2
br label %18
9: ; preds = %2
br label %18
10: ; preds = %2
br label %18
11: ; preds = %2
br label %18
12: ; preds = %2
br label %18
13: ; preds = %2
br label %18
14: ; preds = %2
br label %18
15: ; preds = %2
br label %18
16: ; preds = %2
br label %18
17: ; preds = %2
br label %18
18: ; preds = %2, %4, %5, %6, %7, %8, %9, %10, %11, %12, %13, %14, %15, %16, %17
%19 = phi i8 [ 17, %17 ], [ 16, %16 ], [ 13, %15 ], [ 12, %14 ], [ 11, %13 ], [ 10, %12 ], [ 9, %11 ], [ 8, %10 ], [ 7, %9 ], [ 6, %8 ], [ 4, %7 ], [ 3, %6 ], [ 2, %5 ], [ 1, %4 ], [ 0, %2 ]
%20 = getelementptr inbounds %"class.Thing", %"class.Thing"* %0, i64 0, i32 0
store i8 %19, i8* %20, align 1
ret %"class.Thing"* %0
}
attributes #0 = { nofree norecurse nounwind ssp willreturn writeonly "disable-tail-calls"="false" "frame-pointer"="non-leaf" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "probe-stack"="__chkstk_darwin" "stack-protector-buffer-size"="8" "target-cpu"="apple-m1" "target-features"="+aes,+crc,+crypto,+dotprod,+fp-armv8,+fp16fml,+fullfp16,+lse,+neon,+ras,+rcpc,+rdm,+sha2,+sha3,+sm4,+v8.5a,+zcm,+zcz" "unsafe-fp-math"="false" "use-soft-float"="false" }
```
Looks like it might just need a minor generalization:
```
$ opt x.ll -simplifycfg -S -o - -debug
Args: opt x.ll -simplifycfg -S -o - -debug
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
Looking to fold into
Can't fold, phi node in is conflicting with regard to common predecessor
```
LLC compiles this into 161 lines of .s on aarch64, most of which is a big jump table.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztWEtv2zgQ_jXyhZCht6WDD3mgiwW6l23vASVREhuKFEgq3uTX75B6VHTdZuuDgQUSBOZwZjgvUuI3KkX9evzaEdQIxsSJ8hb9-TdSnRhZjUqCqg7zFpeMIMq1QBgxIZ7HAWnD86IHdAKdUUrCNXtFjOAX0NQIVDUYLXH1THiNTh2tOtQSTiTWRIGZb2M_G5mFVMFqpRBpGlpRMOfFd17w6AXLbxbM_9M0Sr0oqhhWav-1g7Bhhrz4EenXgSDvcI9oDsPjpF2ThnJgX1jkRXfISwKISntR_jMNSfQoOamNicCkTbPE0KEXFWjkHPekfsJ1LYEZBwgz2nIUmTimAJBRjqcA5cirdb2pFM0XJXWi2tQit-rGD8MlYVYTeOlqDRmdLHM0Ekfoh-HBEadnYpPYRpydr04d8cERh44sP19aOOLCERe5m1ZwHpZrOwzdlN2owsiVuhmHsevZDSv8oV5uOcPzgoVnkZ9XLApc-VoyL33cnuQETjb6zT8vvkeDJLWyRwisr4mXcntGtn7SG_nJbuTncCM_-Y38FDfyA4_Ybzu6yk94Iz_RjfzEN_JzxQvhKj9XvBCu8nPFC-EqP1e8EK7yc8UL4YIfuBvsJT2N6Txm83iYx3wei3kMg4UIF2IxFcYLsRgNF6vhYnZzCcGksNEMHbUII71H4WHVs7eUmRj2ujxz2KvD1GGvASUOew04dthrQtGWveYbbrn5WoUtdwm62DKXkPMtcymMk92ShZPbkoOb2bJpW-YSf_T9XrfVjQJb3ZZowkgPAHbQEkBzKUZujsFFYPnwc0i6wZkTEUdoxUpKC0lmmDihLcCQ06oJhUwAdMVOAF9_7Wk67gtcnn6x1pKWo8HrFtTakwzAmotGEgKDJID8laFGDp1DjZQa0IkyNqFldJJUE8GhLwBXNVUG7fsaU-ZXmDFl_MdQ1qjBTBGL34GWAKX9QUC3QeSqwQX3obdoZiXTKPjweFVUEb8ZelxftNVTs6rFzH8hFVTMP9Fad6tqMKtx4VPeKDDk93gj35oCHdOx-LZjuRw5qHDM3zWjYGNI7b8RKd7V1RIPA-yUqwQNxKIzSFESX2los1bx01PVPSv9_FRjCbsya1odqJnQUynKsWmIhGjeyLoyn3U1lnCK_WoYVxHEAXvXh65GQzBs9KYeXnSPzfQBiEpWC_E6aDHRtdAQQz1NIHss-5d8mYVZ07N5MjJmGNPMFsUQHI7TREk8u5HVMPuRdT8RqsPRSsUz1ScT8ZLvUzyRb1W_EG9zYiNXuCG_3JcRzpwSDWTPBNYXVNyn6Lxvtb-foYmGfpc-22a5p22noSNWGnECPSYGDjxdc7_M6BvWFPJ-px9OkBg0-mfPGIJt7QdGm9eqaZH_BfkC-civSTm2k_adbJW51P7LCvQ9ZPN1APrVRrAaTd8DJtkDhl05aCswbx9zw3BRE6OETGdfCd4wWmljAFrcDl5ILZa1MVaJvhfcXpakguca8v5w-OHww-GHww-H_1uHl2-9zw9mxUABQiHdgWkbRpiFcBVy4IkG7eGXI4xl1WUWvfcCrkUQrF-JMSppu_l-vN_Vx7gu4gLvNNWMHAGkf5lvs4dPfwBIR39RpeBeFcMgpB451a_2A7XBqHj95jp93p4-SU8fuXejZMdO68HclV70Cf5byH8s95AFTBh7WQaDrL4BsoIp-BoNBvqUpll22HVHXJR5nmRFk2VpkcXFISnTqk6KmNRRWsbJzvadysRtsK0xGt_BzUz7-eZXa68AkNZk4m-lRpg-7ugxCgDTplESBEmU5PsmKosUN2kckpwccOolAekBfO-Nh72Q7U4ebehwxysQMqq0-i6ENsEgVVtOYx-PuhOwAroCQCU7m-XRpvgvW-Sm0Q">