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