xref: /llvm-project/llvm/test/Transforms/SimplifyCFG/RISCV/switch-of-powers-of-two.ll (revision 540f68c44f4813c2c16f92ccbba5a15e8ff87c85) 
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -passes='simplifycfg<switch-to-lookup>' -simplifycfg-require-and-preserve-domtree=1 -S -mtriple=riscv64 < %s \
3; RUN: | FileCheck %s --check-prefixes=CHECK,RV64I
4; RUN: opt -passes='simplifycfg<switch-to-lookup>' -simplifycfg-require-and-preserve-domtree=1 -S -mtriple=riscv64 -mattr=+zbb < %s \
5; RUN: | FileCheck %s --check-prefixes=CHECK,RV64ZBB
6
7target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
8
9; Check that the range of switch of powers of two is reduced and switch itself is lowered to lookup-table.
10define i32 @switch_of_powers(i32 %x) {
11; RV64I-LABEL: @switch_of_powers(
12; RV64I-NEXT:  entry:
13; RV64I-NEXT:    switch i32 [[X:%.*]], label [[DEFAULT_CASE:%.*]] [
14; RV64I-NEXT:      i32 1, label [[RETURN:%.*]]
15; RV64I-NEXT:      i32 8, label [[BB2:%.*]]
16; RV64I-NEXT:      i32 16, label [[BB3:%.*]]
17; RV64I-NEXT:      i32 32, label [[BB4:%.*]]
18; RV64I-NEXT:      i32 64, label [[BB5:%.*]]
19; RV64I-NEXT:    ]
20; RV64I:       default_case:
21; RV64I-NEXT:    unreachable
22; RV64I:       bb2:
23; RV64I-NEXT:    br label [[RETURN]]
24; RV64I:       bb3:
25; RV64I-NEXT:    br label [[RETURN]]
26; RV64I:       bb4:
27; RV64I-NEXT:    br label [[RETURN]]
28; RV64I:       bb5:
29; RV64I-NEXT:    br label [[RETURN]]
30; RV64I:       return:
31; RV64I-NEXT:    [[P:%.*]] = phi i32 [ 2, [[BB2]] ], [ 1, [[BB3]] ], [ 0, [[BB4]] ], [ 42, [[BB5]] ], [ 3, [[ENTRY:%.*]] ]
32; RV64I-NEXT:    ret i32 [[P]]
33;
34; RV64ZBB-LABEL: @switch_of_powers(
35; RV64ZBB-NEXT:  entry:
36; RV64ZBB-NEXT:    [[TMP0:%.*]] = call i32 @llvm.cttz.i32(i32 [[X:%.*]], i1 true)
37; RV64ZBB-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [7 x i32], ptr @switch.table.switch_of_powers, i32 0, i32 [[TMP0]]
38; RV64ZBB-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
39; RV64ZBB-NEXT:    ret i32 [[SWITCH_LOAD]]
40;
41entry:
42  switch i32 %x, label %default_case [
43  i32 1,  label %bb1
44  i32 8,  label %bb2
45  i32 16, label %bb3
46  i32 32, label %bb4
47  i32 64, label %bb5
48  ]
49
50
51default_case: unreachable
52bb1: br label %return
53bb2: br label %return
54bb3: br label %return
55bb4: br label %return
56bb5: br label %return
57
58return:
59  %p = phi i32 [ 3, %bb1 ], [ 2, %bb2 ], [ 1, %bb3 ], [ 0, %bb4 ], [ 42, %bb5 ]
60  ret i32 %p
61}
62
63; Check that switch's of powers of two range is not reduced if default case is reachable
64define i32 @switch_of_powers_reachable_default(i32 %x) {
65; CHECK-LABEL: @switch_of_powers_reachable_default(
66; CHECK-NEXT:  entry:
67; CHECK-NEXT:    switch i32 [[X:%.*]], label [[RETURN:%.*]] [
68; CHECK-NEXT:      i32 1, label [[BB1:%.*]]
69; CHECK-NEXT:      i32 8, label [[BB2:%.*]]
70; CHECK-NEXT:      i32 16, label [[BB3:%.*]]
71; CHECK-NEXT:      i32 32, label [[BB4:%.*]]
72; CHECK-NEXT:      i32 64, label [[BB5:%.*]]
73; CHECK-NEXT:    ]
74; CHECK:       bb1:
75; CHECK-NEXT:    br label [[RETURN]]
76; CHECK:       bb2:
77; CHECK-NEXT:    br label [[RETURN]]
78; CHECK:       bb3:
79; CHECK-NEXT:    br label [[RETURN]]
80; CHECK:       bb4:
81; CHECK-NEXT:    br label [[RETURN]]
82; CHECK:       bb5:
83; CHECK-NEXT:    br label [[RETURN]]
84; CHECK:       return:
85; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 3, [[BB1]] ], [ 2, [[BB2]] ], [ 1, [[BB3]] ], [ 0, [[BB4]] ], [ 42, [[BB5]] ], [ -1, [[ENTRY:%.*]] ]
86; CHECK-NEXT:    ret i32 [[P]]
87;
88entry:
89  switch i32 %x, label %default_case [
90  i32 1,  label %bb1
91  i32 8,  label %bb2
92  i32 16, label %bb3
93  i32 32, label %bb4
94  i32 64, label %bb5
95  ]
96
97
98default_case: br label %return
99bb1: br label %return
100bb2: br label %return
101bb3: br label %return
102bb4: br label %return
103bb5: br label %return
104
105return:
106  %p = phi i32 [ 3, %bb1 ], [ 2, %bb2 ], [ 1, %bb3 ], [ 0, %bb4 ], [ 42, %bb5 ], [-1, %default_case]
107  ret i32 %p
108}
109
110; Check that switch with zero case is not considered as switch of powers of two
111define i32 @switch_of_non_powers(i32 %x) {
112; CHECK-LABEL: @switch_of_non_powers(
113; CHECK-NEXT:  entry:
114; CHECK-NEXT:    switch i32 [[X:%.*]], label [[DEFAULT_CASE:%.*]] [
115; CHECK-NEXT:      i32 0, label [[RETURN:%.*]]
116; CHECK-NEXT:      i32 1, label [[BB2:%.*]]
117; CHECK-NEXT:      i32 16, label [[BB3:%.*]]
118; CHECK-NEXT:      i32 32, label [[BB4:%.*]]
119; CHECK-NEXT:      i32 64, label [[BB5:%.*]]
120; CHECK-NEXT:    ]
121; CHECK:       default_case:
122; CHECK-NEXT:    unreachable
123; CHECK:       bb2:
124; CHECK-NEXT:    br label [[RETURN]]
125; CHECK:       bb3:
126; CHECK-NEXT:    br label [[RETURN]]
127; CHECK:       bb4:
128; CHECK-NEXT:    br label [[RETURN]]
129; CHECK:       bb5:
130; CHECK-NEXT:    br label [[RETURN]]
131; CHECK:       return:
132; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 2, [[BB2]] ], [ 1, [[BB3]] ], [ 0, [[BB4]] ], [ 42, [[BB5]] ], [ 3, [[ENTRY:%.*]] ]
133; CHECK-NEXT:    ret i32 [[P]]
134;
135entry:
136  switch i32 %x, label %default_case [
137  i32 0,  label %bb1
138  i32 1,  label %bb2
139  i32 16, label %bb3
140  i32 32, label %bb4
141  i32 64, label %bb5
142  ]
143
144
145default_case: unreachable
146bb1: br label %return
147bb2: br label %return
148bb3: br label %return
149bb4: br label %return
150bb5: br label %return
151
152return:
153  %p = phi i32 [ 3, %bb1 ], [ 2, %bb2 ], [ 1, %bb3 ], [ 0, %bb4 ], [ 42, %bb5 ]
154  ret i32 %p
155}
156
157define i32 @unable_to_create_dense_switch(i32 %x) {
158; CHECK-LABEL: @unable_to_create_dense_switch(
159; CHECK-NEXT:  entry:
160; CHECK-NEXT:    switch i32 [[X:%.*]], label [[DEFAULT_CASE:%.*]] [
161; CHECK-NEXT:      i32 1, label [[RETURN:%.*]]
162; CHECK-NEXT:      i32 2, label [[BB3:%.*]]
163; CHECK-NEXT:      i32 4, label [[BB4:%.*]]
164; CHECK-NEXT:      i32 4096, label [[BB5:%.*]]
165; CHECK-NEXT:    ]
166; CHECK:       default_case:
167; CHECK-NEXT:    unreachable
168; CHECK:       bb3:
169; CHECK-NEXT:    br label [[RETURN]]
170; CHECK:       bb4:
171; CHECK-NEXT:    br label [[RETURN]]
172; CHECK:       bb5:
173; CHECK-NEXT:    br label [[RETURN]]
174; CHECK:       return:
175; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 1, [[BB3]] ], [ 0, [[BB4]] ], [ 42, [[BB5]] ], [ 2, [[ENTRY:%.*]] ]
176; CHECK-NEXT:    ret i32 [[P]]
177;
178entry:
179  switch i32 %x, label %default_case [
180  i32 1,  label %bb2
181  i32 2, label %bb3
182  i32 4, label %bb4
183  i32 4096, label %bb5
184  ]
185
186
187default_case: unreachable
188bb1: br label %return
189bb2: br label %return
190bb3: br label %return
191bb4: br label %return
192bb5: br label %return
193
194return:
195  %p = phi i32 [ 3, %bb1 ], [ 2, %bb2 ], [ 1, %bb3 ], [ 0, %bb4 ], [ 42, %bb5 ]
196  ret i32 %p
197}
198
199declare i32 @bar(i32)
200define i32 @unable_to_generate_lookup_table(i32 %x, i32 %y) {
201; RV64I-LABEL: @unable_to_generate_lookup_table(
202; RV64I-NEXT:  entry:
203; RV64I-NEXT:    switch i32 [[Y:%.*]], label [[DEFAULT_CASE:%.*]] [
204; RV64I-NEXT:      i32 1, label [[BB2:%.*]]
205; RV64I-NEXT:      i32 2, label [[BB3:%.*]]
206; RV64I-NEXT:      i32 8, label [[BB4:%.*]]
207; RV64I-NEXT:      i32 64, label [[BB5:%.*]]
208; RV64I-NEXT:    ]
209; RV64I:       default_case:
210; RV64I-NEXT:    unreachable
211; RV64I:       bb2:
212; RV64I-NEXT:    [[XOR2:%.*]] = xor i32 [[X:%.*]], 48
213; RV64I-NEXT:    [[CALL2:%.*]] = call i32 @bar(i32 [[XOR2]])
214; RV64I-NEXT:    [[ADD2:%.*]] = sub i32 [[CALL2]], [[X]]
215; RV64I-NEXT:    br label [[RETURN:%.*]]
216; RV64I:       bb3:
217; RV64I-NEXT:    [[XOR3:%.*]] = xor i32 [[X]], 96
218; RV64I-NEXT:    [[CALL3:%.*]] = call i32 @bar(i32 [[XOR3]])
219; RV64I-NEXT:    [[ADD3:%.*]] = add i32 [[CALL3]], [[X]]
220; RV64I-NEXT:    br label [[RETURN]]
221; RV64I:       bb4:
222; RV64I-NEXT:    [[CALL4:%.*]] = call i32 @bar(i32 [[X]])
223; RV64I-NEXT:    [[ADD4:%.*]] = add i32 [[CALL4]], [[X]]
224; RV64I-NEXT:    br label [[RETURN]]
225; RV64I:       bb5:
226; RV64I-NEXT:    [[XOR5:%.*]] = xor i32 [[X]], 9
227; RV64I-NEXT:    [[CALL5:%.*]] = call i32 @bar(i32 [[XOR5]])
228; RV64I-NEXT:    [[ADD5:%.*]] = add i32 [[CALL5]], [[X]]
229; RV64I-NEXT:    br label [[RETURN]]
230; RV64I:       return:
231; RV64I-NEXT:    [[P:%.*]] = phi i32 [ [[ADD2]], [[BB2]] ], [ [[ADD3]], [[BB3]] ], [ [[ADD4]], [[BB4]] ], [ [[ADD5]], [[BB5]] ]
232; RV64I-NEXT:    ret i32 [[P]]
233;
234; RV64ZBB-LABEL: @unable_to_generate_lookup_table(
235; RV64ZBB-NEXT:  entry:
236; RV64ZBB-NEXT:    [[TMP0:%.*]] = call i32 @llvm.cttz.i32(i32 [[Y:%.*]], i1 true)
237; RV64ZBB-NEXT:    switch i32 [[TMP0]], label [[DEFAULT_CASE:%.*]] [
238; RV64ZBB-NEXT:      i32 0, label [[BB2:%.*]]
239; RV64ZBB-NEXT:      i32 1, label [[BB3:%.*]]
240; RV64ZBB-NEXT:      i32 3, label [[BB4:%.*]]
241; RV64ZBB-NEXT:      i32 6, label [[BB5:%.*]]
242; RV64ZBB-NEXT:    ]
243; RV64ZBB:       default_case:
244; RV64ZBB-NEXT:    unreachable
245; RV64ZBB:       bb2:
246; RV64ZBB-NEXT:    [[XOR2:%.*]] = xor i32 [[X:%.*]], 48
247; RV64ZBB-NEXT:    [[CALL2:%.*]] = call i32 @bar(i32 [[XOR2]])
248; RV64ZBB-NEXT:    [[ADD2:%.*]] = sub i32 [[CALL2]], [[X]]
249; RV64ZBB-NEXT:    br label [[RETURN:%.*]]
250; RV64ZBB:       bb3:
251; RV64ZBB-NEXT:    [[XOR3:%.*]] = xor i32 [[X]], 96
252; RV64ZBB-NEXT:    [[CALL3:%.*]] = call i32 @bar(i32 [[XOR3]])
253; RV64ZBB-NEXT:    [[ADD3:%.*]] = add i32 [[CALL3]], [[X]]
254; RV64ZBB-NEXT:    br label [[RETURN]]
255; RV64ZBB:       bb4:
256; RV64ZBB-NEXT:    [[CALL4:%.*]] = call i32 @bar(i32 [[X]])
257; RV64ZBB-NEXT:    [[ADD4:%.*]] = add i32 [[CALL4]], [[X]]
258; RV64ZBB-NEXT:    br label [[RETURN]]
259; RV64ZBB:       bb5:
260; RV64ZBB-NEXT:    [[XOR5:%.*]] = xor i32 [[X]], 9
261; RV64ZBB-NEXT:    [[CALL5:%.*]] = call i32 @bar(i32 [[XOR5]])
262; RV64ZBB-NEXT:    [[ADD5:%.*]] = add i32 [[CALL5]], [[X]]
263; RV64ZBB-NEXT:    br label [[RETURN]]
264; RV64ZBB:       return:
265; RV64ZBB-NEXT:    [[P:%.*]] = phi i32 [ [[ADD2]], [[BB2]] ], [ [[ADD3]], [[BB3]] ], [ [[ADD4]], [[BB4]] ], [ [[ADD5]], [[BB5]] ]
266; RV64ZBB-NEXT:    ret i32 [[P]]
267;
268entry:
269  switch i32 %y, label %default_case [
270  i32 1,  label %bb2
271  i32 2, label %bb3
272  i32 8, label %bb4
273  i32 64, label %bb5
274  ]
275
276
277default_case: unreachable
278bb1:
279  %xor1 = xor i32 %x, 42
280  %call1 = call i32 @bar(i32 %xor1)
281  %add1 = add i32 %call1, %x
282  br label %return
283bb2:
284  %xor2 = xor i32 %x, 48
285  %call2 = call i32 @bar(i32 %xor2)
286  %add2 = sub i32 %call2, %x
287  br label %return
288bb3:
289  %xor3 = xor i32 %x, 96
290  %call3 = call i32 @bar(i32 %xor3)
291  %add3 = add i32 %call3, %x
292  br label %return
293bb4:
294  %call4 = call i32 @bar(i32 %x)
295  %add4 = add i32 %call4, %x
296  br label %return
297bb5:
298  %xor5 = xor i32 %x, 9
299  %call5 = call i32 @bar(i32 %xor5)
300  %add5 = add i32 %call5, %x
301  br label %return
302
303return:
304  %p = phi i32 [ %add1, %bb1 ], [ %add2, %bb2 ], [ %add3, %bb3 ], [ %add4, %bb4 ], [ %add5, %bb5 ]
305
306  ret i32 %p
307}
308
309define i128 @switch_with_long_condition(i128 %x) {
310; CHECK-LABEL: @switch_with_long_condition(
311; CHECK-NEXT:  entry:
312; CHECK-NEXT:    switch i128 [[X:%.*]], label [[DEFAULT_CASE:%.*]] [
313; CHECK-NEXT:      i128 1, label [[RETURN:%.*]]
314; CHECK-NEXT:      i128 2, label [[BB3:%.*]]
315; CHECK-NEXT:      i128 4, label [[BB4:%.*]]
316; CHECK-NEXT:      i128 32, label [[BB5:%.*]]
317; CHECK-NEXT:    ]
318; CHECK:       default_case:
319; CHECK-NEXT:    unreachable
320; CHECK:       bb3:
321; CHECK-NEXT:    br label [[RETURN]]
322; CHECK:       bb4:
323; CHECK-NEXT:    br label [[RETURN]]
324; CHECK:       bb5:
325; CHECK-NEXT:    br label [[RETURN]]
326; CHECK:       return:
327; CHECK-NEXT:    [[P:%.*]] = phi i128 [ 1, [[BB3]] ], [ 0, [[BB4]] ], [ 42, [[BB5]] ], [ 2, [[ENTRY:%.*]] ]
328; CHECK-NEXT:    ret i128 [[P]]
329;
330entry:
331  switch i128 %x, label %default_case [
332  i128 1,  label %bb2
333  i128 2, label %bb3
334  i128 4, label %bb4
335  i128 32, label %bb5
336  ]
337
338
339default_case: unreachable
340bb1: br label %return
341bb2: br label %return
342bb3: br label %return
343bb4: br label %return
344bb5: br label %return
345
346return:
347  %p = phi i128 [ 3, %bb1 ], [ 2, %bb2 ], [ 1, %bb3 ], [ 0, %bb4 ], [ 42, %bb5 ]
348  ret i128 %p
349}
350