1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup -S | FileCheck %s
3; RUN: opt < %s -passes='simplifycfg<switch-to-lookup>' -S | FileCheck %s
4
5target datalayout = "e-n32"
6
7define i32 @test1(i32 %a) {
8; CHECK-LABEL: @test1(
9; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
10; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
11; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
12; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
13; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 4
14; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
15; CHECK:       switch.lookup:
16; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], ptr @switch.table.test1, i32 0, i32 [[TMP4]]
17; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
18; CHECK-NEXT:    br label [[COMMON_RET]]
19; CHECK:       common.ret:
20; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
21; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
22;
23  switch i32 %a, label %def [
24  i32 97, label %one
25  i32 101, label %two
26  i32 105, label %three
27  i32 109, label %three
28  ]
29
30def:
31  ret i32 8867
32
33one:
34  ret i32 11984
35two:
36  ret i32 1143
37three:
38  ret i32 99783
39}
40
41; Optimization shouldn't trigger; bitwidth > 64
42define i128 @test2(i128 %a) {
43; CHECK-LABEL: @test2(
44; CHECK-NEXT:    switch i128 [[A:%.*]], label [[COMMON_RET:%.*]] [
45; CHECK-NEXT:    i128 97, label [[ONE:%.*]]
46; CHECK-NEXT:    i128 101, label [[TWO:%.*]]
47; CHECK-NEXT:    i128 105, label [[THREE:%.*]]
48; CHECK-NEXT:    i128 109, label [[THREE]]
49; CHECK-NEXT:    ]
50; CHECK:       common.ret:
51; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i128 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ]
52; CHECK-NEXT:    ret i128 [[COMMON_RET_OP]]
53; CHECK:       one:
54; CHECK-NEXT:    br label [[COMMON_RET]]
55; CHECK:       two:
56; CHECK-NEXT:    br label [[COMMON_RET]]
57; CHECK:       three:
58; CHECK-NEXT:    br label [[COMMON_RET]]
59;
60  switch i128 %a, label %def [
61  i128 97, label %one
62  i128 101, label %two
63  i128 105, label %three
64  i128 109, label %three
65  ]
66
67def:
68  ret i128 8867
69
70one:
71  ret i128 11984
72two:
73  ret i128 1143
74three:
75  ret i128 99783
76}
77
78; Optimization shouldn't trigger; no holes present
79define i32 @test3(i32 %a) {
80; CHECK-LABEL: @test3(
81; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[A:%.*]], 97
82; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 3
83; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
84; CHECK:       switch.lookup:
85; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32], ptr @switch.table.test3, i32 0, i32 [[SWITCH_TABLEIDX]]
86; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
87; CHECK-NEXT:    br label [[COMMON_RET]]
88; CHECK:       common.ret:
89; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
90; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
91;
92  switch i32 %a, label %def [
93  i32 97, label %one
94  i32 98, label %two
95  i32 99, label %three
96  ]
97
98def:
99  ret i32 8867
100
101one:
102  ret i32 11984
103two:
104  ret i32 1143
105three:
106  ret i32 99783
107}
108
109; Optimization shouldn't trigger; not an arithmetic progression
110define i32 @test4(i32 %a) {
111; CHECK-LABEL: @test4(
112; CHECK-NEXT:    switch i32 [[A:%.*]], label [[COMMON_RET:%.*]] [
113; CHECK-NEXT:    i32 97, label [[ONE:%.*]]
114; CHECK-NEXT:    i32 102, label [[TWO:%.*]]
115; CHECK-NEXT:    i32 105, label [[THREE:%.*]]
116; CHECK-NEXT:    i32 109, label [[THREE]]
117; CHECK-NEXT:    ]
118; CHECK:       common.ret:
119; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ]
120; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
121; CHECK:       one:
122; CHECK-NEXT:    br label [[COMMON_RET]]
123; CHECK:       two:
124; CHECK-NEXT:    br label [[COMMON_RET]]
125; CHECK:       three:
126; CHECK-NEXT:    br label [[COMMON_RET]]
127;
128  switch i32 %a, label %def [
129  i32 97, label %one
130  i32 102, label %two
131  i32 105, label %three
132  i32 109, label %three
133  ]
134
135def:
136  ret i32 8867
137
138one:
139  ret i32 11984
140two:
141  ret i32 1143
142three:
143  ret i32 99783
144}
145
146; Optimization shouldn't trigger; not a power of two
147define i32 @test5(i32 %a) {
148; CHECK-LABEL: @test5(
149; CHECK-NEXT:    switch i32 [[A:%.*]], label [[COMMON_RET:%.*]] [
150; CHECK-NEXT:    i32 97, label [[ONE:%.*]]
151; CHECK-NEXT:    i32 102, label [[TWO:%.*]]
152; CHECK-NEXT:    i32 107, label [[THREE:%.*]]
153; CHECK-NEXT:    i32 112, label [[THREE]]
154; CHECK-NEXT:    ]
155; CHECK:       common.ret:
156; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ]
157; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
158; CHECK:       one:
159; CHECK-NEXT:    br label [[COMMON_RET]]
160; CHECK:       two:
161; CHECK-NEXT:    br label [[COMMON_RET]]
162; CHECK:       three:
163; CHECK-NEXT:    br label [[COMMON_RET]]
164;
165  switch i32 %a, label %def [
166  i32 97, label %one
167  i32 102, label %two
168  i32 107, label %three
169  i32 112, label %three
170  ]
171
172def:
173  ret i32 8867
174
175one:
176  ret i32 11984
177two:
178  ret i32 1143
179three:
180  ret i32 99783
181}
182
183define i32 @test6(i32 %a) optsize {
184; CHECK-LABEL: @test6(
185; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], -109
186; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
187; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
188; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
189; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 4
190; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
191; CHECK:       switch.lookup:
192; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], ptr @switch.table.test6, i32 0, i32 [[TMP4]]
193; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
194; CHECK-NEXT:    br label [[COMMON_RET]]
195; CHECK:       common.ret:
196; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
197; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
198;
199  switch i32 %a, label %def [
200  i32 -97, label %one
201  i32 -101, label %two
202  i32 -105, label %three
203  i32 -109, label %three
204  ]
205
206def:
207  ret i32 8867
208
209one:
210  ret i32 11984
211two:
212  ret i32 1143
213three:
214  ret i32 99783
215}
216
217define i8 @test7(i8 %a) optsize {
218; CHECK-LABEL: @test7(
219; CHECK-NEXT:  common.ret:
220; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 [[A:%.*]], -36
221; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 [[TMP0]], 2
222; CHECK-NEXT:    [[TMP2:%.*]] = shl i8 [[TMP0]], 6
223; CHECK-NEXT:    [[TMP3:%.*]] = or i8 [[TMP1]], [[TMP2]]
224; CHECK-NEXT:    [[TMP4:%.*]] = icmp ult i8 [[TMP3]], 4
225; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i8 [[TMP3]] to i32
226; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i32 [[SWITCH_CAST]], 8
227; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i32 -943228976, [[SWITCH_SHIFTAMT]]
228; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i32 [[SWITCH_DOWNSHIFT]] to i8
229; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = select i1 [[TMP4]], i8 [[SWITCH_MASKED]], i8 -93
230; CHECK-NEXT:    ret i8 [[COMMON_RET_OP]]
231;
232  switch i8 %a, label %def [
233  i8 220, label %one
234  i8 224, label %two
235  i8 228, label %three
236  i8 232, label %three
237  ]
238
239def:
240  ret i8 8867
241
242one:
243  ret i8 11984
244two:
245  ret i8 1143
246three:
247  ret i8 99783
248}
249
250define i32 @test8(i32 %a) optsize {
251; CHECK-LABEL: @test8(
252; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
253; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
254; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
255; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
256; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 5
257; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
258; CHECK:       switch.lookup:
259; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [5 x i32], ptr @switch.table.test8, i32 0, i32 [[TMP4]]
260; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
261; CHECK-NEXT:    br label [[COMMON_RET]]
262; CHECK:       common.ret:
263; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
264; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
265;
266  switch i32 %a, label %def [
267  i32 97, label %one
268  i32 101, label %two
269  i32 105, label %three
270  i32 113, label %three
271  ]
272
273def:
274  ret i32 8867
275
276one:
277  ret i32 11984
278two:
279  ret i32 1143
280three:
281  ret i32 99783
282}
283
284define i32 @test9(i32 %a) {
285; CHECK-LABEL: @test9(
286; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 6
287; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 1
288; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 31
289; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
290; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 8
291; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
292; CHECK:       switch.lookup:
293; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i32], ptr @switch.table.test9, i32 0, i32 [[TMP4]]
294; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
295; CHECK-NEXT:    br label [[COMMON_RET]]
296; CHECK:       common.ret:
297; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
298; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
299;
300  switch i32 %a, label %def [
301  i32 18, label %one
302  i32 20, label %two
303  i32 6, label %three
304  i32 10, label %three
305  ]
306
307def:
308  ret i32 8867
309
310one:
311  ret i32 11984
312two:
313  ret i32 1143
314three:
315  ret i32 99783
316}
317
318