1; RUN: opt -simplifycfg -S -o - < %s | FileCheck %s
2
3declare void @helper(i32)
4
5define void @test1(i1 %a, i1 %b) {
6; CHECK-LABEL: @test1(
7entry:
8  br i1 %a, label %Y, label %X, !prof !0
9; CHECK: br i1 %or.cond, label %Z, label %Y, !prof !0
10
11X:
12  %c = or i1 %b, false
13  br i1 %c, label %Z, label %Y, !prof !1
14
15Y:
16  call void @helper(i32 0)
17  ret void
18
19Z:
20  call void @helper(i32 1)
21  ret void
22}
23
24define void @test2(i1 %a, i1 %b) {
25; CHECK-LABEL: @test2(
26entry:
27  br i1 %a, label %X, label %Y, !prof !1
28; CHECK: br i1 %or.cond, label %Z, label %Y, !prof !1
29; CHECK-NOT: !prof
30
31X:
32  %c = or i1 %b, false
33  br i1 %c, label %Z, label %Y, !prof !2
34
35Y:
36  call void @helper(i32 0)
37  ret void
38
39Z:
40  call void @helper(i32 1)
41  ret void
42}
43
44define void @test3(i1 %a, i1 %b) {
45; CHECK-LABEL: @test3(
46; CHECK-NOT: !prof
47entry:
48  br i1 %a, label %X, label %Y, !prof !1
49
50X:
51  %c = or i1 %b, false
52  br i1 %c, label %Z, label %Y
53
54Y:
55  call void @helper(i32 0)
56  ret void
57
58Z:
59  call void @helper(i32 1)
60  ret void
61}
62
63define void @test4(i1 %a, i1 %b) {
64; CHECK-LABEL: @test4(
65; CHECK-NOT: !prof
66entry:
67  br i1 %a, label %X, label %Y
68
69X:
70  %c = or i1 %b, false
71  br i1 %c, label %Z, label %Y, !prof !1
72
73Y:
74  call void @helper(i32 0)
75  ret void
76
77Z:
78  call void @helper(i32 1)
79  ret void
80}
81
82;; test5 - The case where it jumps to the default target will be removed.
83define void @test5(i32 %M, i32 %N) nounwind uwtable {
84entry:
85  switch i32 %N, label %sw2 [
86    i32 1, label %sw2
87    i32 2, label %sw.bb
88    i32 3, label %sw.bb1
89  ], !prof !3
90; CHECK-LABEL: @test5(
91; CHECK: switch i32 %N, label %sw2 [
92; CHECK: i32 3, label %sw.bb1
93; CHECK: i32 2, label %sw.bb
94; CHECK: ], !prof !2
95
96sw.bb:
97  call void @helper(i32 0)
98  br label %sw.epilog
99
100sw.bb1:
101  call void @helper(i32 1)
102  br label %sw.epilog
103
104sw2:
105  call void @helper(i32 2)
106  br label %sw.epilog
107
108sw.epilog:
109  ret void
110}
111
112;; test6 - Some cases of the second switch are pruned during optimization.
113;; Then the second switch will be converted to a branch, finally, the first
114;; switch and the branch will be merged into a single switch.
115define void @test6(i32 %M, i32 %N) nounwind uwtable {
116entry:
117  switch i32 %N, label %sw2 [
118    i32 1, label %sw2
119    i32 2, label %sw.bb
120    i32 3, label %sw.bb1
121  ], !prof !4
122; CHECK-LABEL: @test6(
123; CHECK: switch i32 %N, label %sw.epilog
124; CHECK: i32 3, label %sw.bb1
125; CHECK: i32 2, label %sw.bb
126; CHECK: i32 4, label %sw.bb5
127; CHECK: ], !prof !3
128
129sw.bb:
130  call void @helper(i32 0)
131  br label %sw.epilog
132
133sw.bb1:
134  call void @helper(i32 1)
135  br label %sw.epilog
136
137sw2:
138;; Here "case 2" is invalidated since the default case of the first switch
139;; does not include "case 2".
140  switch i32 %N, label %sw.epilog [
141    i32 2, label %sw.bb4
142    i32 4, label %sw.bb5
143  ], !prof !5
144
145sw.bb4:
146  call void @helper(i32 2)
147  br label %sw.epilog
148
149sw.bb5:
150  call void @helper(i32 3)
151  br label %sw.epilog
152
153sw.epilog:
154  ret void
155}
156
157;; This test is based on test1 but swapped the targets of the second branch.
158define void @test1_swap(i1 %a, i1 %b) {
159; CHECK-LABEL: @test1_swap(
160entry:
161  br i1 %a, label %Y, label %X, !prof !0
162; CHECK: br i1 %or.cond, label %Y, label %Z, !prof !4
163
164X:
165  %c = or i1 %b, false
166  br i1 %c, label %Y, label %Z, !prof !1
167
168Y:
169  call void @helper(i32 0)
170  ret void
171
172Z:
173  call void @helper(i32 1)
174  ret void
175}
176
177define void @test7(i1 %a, i1 %b) {
178; CHECK-LABEL: @test7(
179entry:
180  %c = or i1 %b, false
181  br i1 %a, label %Y, label %X, !prof !0
182; CHECK: br i1 %brmerge, label %Y, label %Z, !prof !5
183
184X:
185  br i1 %c, label %Y, label %Z, !prof !6
186
187Y:
188  call void @helper(i32 0)
189  ret void
190
191Z:
192  call void @helper(i32 1)
193  ret void
194}
195
196; Test basic folding to a conditional branch.
197define void @test8(i64 %x, i64 %y) nounwind {
198; CHECK-LABEL: @test8(
199entry:
200    %lt = icmp slt i64 %x, %y
201; CHECK: br i1 %lt, label %a, label %b, !prof !6
202    %qux = select i1 %lt, i32 0, i32 2
203    switch i32 %qux, label %bees [
204        i32 0, label %a
205        i32 1, label %b
206        i32 2, label %b
207    ], !prof !7
208a:
209    call void @helper(i32 0) nounwind
210    ret void
211b:
212    call void @helper(i32 1) nounwind
213    ret void
214bees:
215    call void @helper(i32 2) nounwind
216    ret void
217}
218
219; Test edge splitting when the default target has icmp and unconditinal
220; branch
221define i1 @test9(i32 %x, i32 %y) nounwind {
222; CHECK-LABEL: @test9(
223entry:
224    switch i32 %x, label %bees [
225        i32 0, label %a
226        i32 1, label %end
227        i32 2, label %end
228    ], !prof !7
229; CHECK: switch i32 %x, label %bees [
230; CHECK: i32 0, label %a
231; CHECK: i32 1, label %end
232; CHECK: i32 2, label %end
233; CHECK: i32 92, label %end
234; CHECK: ], !prof !7
235
236a:
237    call void @helper(i32 0) nounwind
238    %reta = icmp slt i32 %x, %y
239    ret i1 %reta
240
241bees:
242    %tmp = icmp eq i32 %x, 92
243    br label %end
244
245end:
246; CHECK: end:
247; CHECK: %ret = phi i1 [ true, %entry ], [ false, %bees ], [ true, %entry ], [ true, %entry ]
248    %ret = phi i1 [ true, %entry ], [%tmp, %bees], [true, %entry]
249    call void @helper(i32 2) nounwind
250    ret i1 %ret
251}
252
253define void @test10(i32 %x) nounwind readnone ssp noredzone {
254entry:
255 switch i32 %x, label %lor.rhs [
256   i32 2, label %lor.end
257   i32 1, label %lor.end
258   i32 3, label %lor.end
259 ], !prof !7
260
261lor.rhs:
262 call void @helper(i32 1) nounwind
263 ret void
264
265lor.end:
266 call void @helper(i32 0) nounwind
267 ret void
268
269; CHECK-LABEL: @test10(
270; CHECK: %x.off = add i32 %x, -1
271; CHECK: %switch = icmp ult i32 %x.off, 3
272; CHECK: br i1 %switch, label %lor.end, label %lor.rhs, !prof !8
273}
274
275; Remove dead cases from the switch.
276define void @test11(i32 %x) nounwind {
277  %i = shl i32 %x, 1
278  switch i32 %i, label %a [
279    i32 21, label %b
280    i32 24, label %c
281  ], !prof !8
282; CHECK-LABEL: @test11(
283; CHECK: %cond = icmp eq i32 %i, 24
284; CHECK: br i1 %cond, label %c, label %a, !prof !9
285
286a:
287 call void @helper(i32 0) nounwind
288 ret void
289b:
290 call void @helper(i32 1) nounwind
291 ret void
292c:
293 call void @helper(i32 2) nounwind
294 ret void
295}
296
297;; test12 - Don't crash if the whole switch is removed
298define void @test12(i32 %M, i32 %N) nounwind uwtable {
299entry:
300  switch i32 %N, label %sw.bb [
301    i32 1, label %sw.bb
302  ], !prof !9
303; CHECK-LABEL: @test12(
304; CHECK-NEXT: entry:
305; CHECK-NEXT: call void @helper
306; CHECK-NEXT: ret void
307
308sw.bb:
309  call void @helper(i32 0)
310  br label %sw.epilog
311
312sw.epilog:
313  ret void
314}
315
316;; If every case is dead, make sure they are all removed. This used to
317;; crash trying to merge the metadata.
318define void @test13(i32 %x) nounwind {
319entry:
320  %i = shl i32 %x, 1
321  switch i32 %i, label %a [
322    i32 21, label %b
323    i32 25, label %c
324  ], !prof !8
325; CHECK-LABEL: @test13(
326; CHECK-NEXT: entry:
327; CHECK-NEXT: call void @helper
328; CHECK-NEXT: ret void
329
330a:
331 call void @helper(i32 0) nounwind
332 ret void
333b:
334 call void @helper(i32 1) nounwind
335 ret void
336c:
337 call void @helper(i32 2) nounwind
338 ret void
339}
340
341;; When folding branches to common destination, the updated branch weights
342;; can exceed uint32 by more than factor of 2. We should keep halving the
343;; weights until they can fit into uint32.
344@max_regno = common global i32 0, align 4
345define void @test14(i32* %old, i32 %final) {
346; CHECK-LABEL: @test14
347; CHECK: br i1 %or.cond, label %for.exit, label %for.inc, !prof !10
348for.cond:
349  br label %for.cond2
350for.cond2:
351  %i.1 = phi i32 [ %inc19, %for.inc ], [ 0, %for.cond ]
352  %bit.0 = phi i32 [ %shl, %for.inc ], [ 1, %for.cond ]
353  %tobool = icmp eq i32 %bit.0, 0
354  br i1 %tobool, label %for.exit, label %for.body3, !prof !10
355for.body3:
356  %v3 = load i32* @max_regno, align 4
357  %cmp4 = icmp eq i32 %i.1, %v3
358  br i1 %cmp4, label %for.exit, label %for.inc, !prof !11
359for.inc:
360  %shl = shl i32 %bit.0, 1
361  %inc19 = add nsw i32 %i.1, 1
362  br label %for.cond2
363for.exit:
364  ret void
365}
366
367!0 = !{!"branch_weights", i32 3, i32 5}
368!1 = !{!"branch_weights", i32 1, i32 1}
369!2 = !{!"branch_weights", i32 1, i32 2}
370!3 = !{!"branch_weights", i32 4, i32 3, i32 2, i32 1}
371!4 = !{!"branch_weights", i32 4, i32 3, i32 2, i32 1}
372!5 = !{!"branch_weights", i32 7, i32 6, i32 5}
373!6 = !{!"branch_weights", i32 1, i32 3}
374!7 = !{!"branch_weights", i32 33, i32 9, i32 8, i32 7}
375!8 = !{!"branch_weights", i32 33, i32 9, i32 8}
376!9 = !{!"branch_weights", i32 7, i32 6}
377!10 = !{!"branch_weights", i32 672646, i32 21604207}
378!11 = !{!"branch_weights", i32 6960, i32 21597248}
379
380; CHECK: !0 = !{!"branch_weights", i32 5, i32 11}
381; CHECK: !1 = !{!"branch_weights", i32 1, i32 5}
382; CHECK: !2 = !{!"branch_weights", i32 7, i32 1, i32 2}
383; CHECK: !3 = !{!"branch_weights", i32 49, i32 12, i32 24, i32 35}
384; CHECK: !4 = !{!"branch_weights", i32 11, i32 5}
385; CHECK: !5 = !{!"branch_weights", i32 17, i32 15}
386; CHECK: !6 = !{!"branch_weights", i32 9, i32 7}
387; CHECK: !7 = !{!"branch_weights", i32 17, i32 9, i32 8, i32 7, i32 17}
388; CHECK: !8 = !{!"branch_weights", i32 24, i32 33}
389; CHECK: !9 = !{!"branch_weights", i32 8, i32 33}
390;; The false weight prints out as a negative integer here, but inside llvm, we
391;; treat the weight as an unsigned integer.
392; CHECK: !10 = !{!"branch_weights", i32 112017436, i32 -735157296}
393