1; RUN: opt < %s -simplifycfg -S | FileCheck %s
2
3declare void @foo1()
4
5declare void @foo2()
6
7define void @test1(i32 %V) {
8        %C1 = icmp eq i32 %V, 4         ; <i1> [#uses=1]
9        %C2 = icmp eq i32 %V, 17                ; <i1> [#uses=1]
10        %CN = or i1 %C1, %C2            ; <i1> [#uses=1]
11        br i1 %CN, label %T, label %F
12T:              ; preds = %0
13        call void @foo1( )
14        ret void
15F:              ; preds = %0
16        call void @foo2( )
17        ret void
18; CHECK: @test1
19; CHECK:  switch i32 %V, label %F [
20; CHECK:    i32 17, label %T
21; CHECK:    i32 4, label %T
22; CHECK:  ]
23}
24
25define void @test2(i32 %V) {
26        %C1 = icmp ne i32 %V, 4         ; <i1> [#uses=1]
27        %C2 = icmp ne i32 %V, 17                ; <i1> [#uses=1]
28        %CN = and i1 %C1, %C2           ; <i1> [#uses=1]
29        br i1 %CN, label %T, label %F
30T:              ; preds = %0
31        call void @foo1( )
32        ret void
33F:              ; preds = %0
34        call void @foo2( )
35        ret void
36; CHECK: @test2
37; CHECK:  switch i32 %V, label %T [
38; CHECK:    i32 17, label %F
39; CHECK:    i32 4, label %F
40; CHECK:  ]
41}
42
43define void @test3(i32 %V) {
44        %C1 = icmp eq i32 %V, 4         ; <i1> [#uses=1]
45        br i1 %C1, label %T, label %N
46N:              ; preds = %0
47        %C2 = icmp eq i32 %V, 17                ; <i1> [#uses=1]
48        br i1 %C2, label %T, label %F
49T:              ; preds = %N, %0
50        call void @foo1( )
51        ret void
52F:              ; preds = %N
53        call void @foo2( )
54        ret void
55
56; CHECK: @test3
57; CHECK: switch i32 %V, label %F [
58; CHECK:     i32 4, label %T
59; CHECK:     i32 17, label %T
60; CHECK:   ]
61}
62
63
64
65define i32 @test4(i8 zeroext %c) nounwind ssp noredzone {
66entry:
67  %cmp = icmp eq i8 %c, 62
68  br i1 %cmp, label %lor.end, label %lor.lhs.false
69
70lor.lhs.false:                                    ; preds = %entry
71  %cmp4 = icmp eq i8 %c, 34
72  br i1 %cmp4, label %lor.end, label %lor.rhs
73
74lor.rhs:                                          ; preds = %lor.lhs.false
75  %cmp8 = icmp eq i8 %c, 92
76  br label %lor.end
77
78lor.end:                                          ; preds = %lor.rhs, %lor.lhs.false, %entry
79  %0 = phi i1 [ true, %lor.lhs.false ], [ true, %entry ], [ %cmp8, %lor.rhs ]
80  %lor.ext = zext i1 %0 to i32
81  ret i32 %lor.ext
82
83; CHECK: @test4
84; CHECK:  switch i8 %c, label %lor.rhs [
85; CHECK:    i8 62, label %lor.end
86; CHECK:    i8 34, label %lor.end
87; CHECK:    i8 92, label %lor.end
88; CHECK:  ]
89}
90
91define i32 @test5(i8 zeroext %c) nounwind ssp noredzone {
92entry:
93  switch i8 %c, label %lor.rhs [
94    i8 62, label %lor.end
95    i8 34, label %lor.end
96    i8 92, label %lor.end
97  ]
98
99lor.rhs:                                          ; preds = %entry
100  %V = icmp eq i8 %c, 92
101  br label %lor.end
102
103lor.end:                                          ; preds = %entry, %entry, %entry, %lor.rhs
104  %0 = phi i1 [ true, %entry ], [ %V, %lor.rhs ], [ true, %entry ], [ true, %entry ]
105  %lor.ext = zext i1 %0 to i32
106  ret i32 %lor.ext
107; CHECK: @test5
108; CHECK:  switch i8 %c, label %lor.rhs [
109; CHECK:    i8 62, label %lor.end
110; CHECK:    i8 34, label %lor.end
111; CHECK:    i8 92, label %lor.end
112; CHECK:  ]
113}
114
115
116define i1 @test6({ i32, i32 }* %I) {
117entry:
118        %tmp.1.i = getelementptr { i32, i32 }* %I, i64 0, i32 1         ; <i32*> [#uses=1]
119        %tmp.2.i = load i32* %tmp.1.i           ; <i32> [#uses=6]
120        %tmp.2 = icmp eq i32 %tmp.2.i, 14               ; <i1> [#uses=1]
121        br i1 %tmp.2, label %shortcirc_done.4, label %shortcirc_next.0
122shortcirc_next.0:               ; preds = %entry
123        %tmp.6 = icmp eq i32 %tmp.2.i, 15               ; <i1> [#uses=1]
124        br i1 %tmp.6, label %shortcirc_done.4, label %shortcirc_next.1
125shortcirc_next.1:               ; preds = %shortcirc_next.0
126        %tmp.11 = icmp eq i32 %tmp.2.i, 16              ; <i1> [#uses=1]
127        br i1 %tmp.11, label %shortcirc_done.4, label %shortcirc_next.2
128shortcirc_next.2:               ; preds = %shortcirc_next.1
129        %tmp.16 = icmp eq i32 %tmp.2.i, 17              ; <i1> [#uses=1]
130        br i1 %tmp.16, label %shortcirc_done.4, label %shortcirc_next.3
131shortcirc_next.3:               ; preds = %shortcirc_next.2
132        %tmp.21 = icmp eq i32 %tmp.2.i, 18              ; <i1> [#uses=1]
133        br i1 %tmp.21, label %shortcirc_done.4, label %shortcirc_next.4
134shortcirc_next.4:               ; preds = %shortcirc_next.3
135        %tmp.26 = icmp eq i32 %tmp.2.i, 19              ; <i1> [#uses=1]
136        br label %UnifiedReturnBlock
137shortcirc_done.4:               ; preds = %shortcirc_next.3, %shortcirc_next.2, %shortcirc_next.1, %shortcirc_next.0, %entry
138        br label %UnifiedReturnBlock
139UnifiedReturnBlock:             ; preds = %shortcirc_done.4, %shortcirc_next.4
140        %UnifiedRetVal = phi i1 [ %tmp.26, %shortcirc_next.4 ], [ true, %shortcirc_done.4 ]             ; <i1> [#uses=1]
141        ret i1 %UnifiedRetVal
142
143; CHECK: @test6
144; CHECK: %switch.tableidx = sub i32 %tmp.2.i, 14
145; CHECK: %0 = icmp ult i32 %switch.tableidx, 6
146; CHECK: select i1 %0, i1 true, i1 false
147}
148
149define void @test7(i8 zeroext %c, i32 %x) nounwind ssp noredzone {
150entry:
151  %cmp = icmp ult i32 %x, 32
152  %cmp4 = icmp eq i8 %c, 97
153  %or.cond = or i1 %cmp, %cmp4
154  %cmp9 = icmp eq i8 %c, 99
155  %or.cond11 = or i1 %or.cond, %cmp9
156  br i1 %or.cond11, label %if.then, label %if.end
157
158if.then:                                          ; preds = %entry
159  tail call void @foo1() nounwind noredzone
160  ret void
161
162if.end:                                           ; preds = %entry
163  ret void
164
165; CHECK: @test7
166; CHECK:   %cmp = icmp ult i32 %x, 32
167; CHECK:   br i1 %cmp, label %if.then, label %switch.early.test
168; CHECK: switch.early.test:
169; CHECK:   switch i8 %c, label %if.end [
170; CHECK:     i8 99, label %if.then
171; CHECK:     i8 97, label %if.then
172; CHECK:   ]
173}
174
175define i32 @test8(i8 zeroext %c, i32 %x, i1 %C) nounwind ssp noredzone {
176entry:
177  br i1 %C, label %N, label %if.then
178N:
179  %cmp = icmp ult i32 %x, 32
180  %cmp4 = icmp eq i8 %c, 97
181  %or.cond = or i1 %cmp, %cmp4
182  %cmp9 = icmp eq i8 %c, 99
183  %or.cond11 = or i1 %or.cond, %cmp9
184  br i1 %or.cond11, label %if.then, label %if.end
185
186if.then:                                          ; preds = %entry
187  %A = phi i32 [0, %entry], [42, %N]
188  tail call void @foo1() nounwind noredzone
189  ret i32 %A
190
191if.end:                                           ; preds = %entry
192  ret i32 0
193
194; CHECK: @test8
195; CHECK: switch.early.test:
196; CHECK:   switch i8 %c, label %if.end [
197; CHECK:     i8 99, label %if.then
198; CHECK:     i8 97, label %if.then
199; CHECK:   ]
200; CHECK:   %A = phi i32 [ 0, %entry ], [ 42, %switch.early.test ], [ 42, %N ], [ 42, %switch.early.test ]
201}
202
203;; This is "Example 7" from http://blog.regehr.org/archives/320
204define i32 @test9(i8 zeroext %c) nounwind ssp noredzone {
205entry:
206  %cmp = icmp ult i8 %c, 33
207  br i1 %cmp, label %lor.end, label %lor.lhs.false
208
209lor.lhs.false:                                    ; preds = %entry
210  %cmp4 = icmp eq i8 %c, 46
211  br i1 %cmp4, label %lor.end, label %lor.lhs.false6
212
213lor.lhs.false6:                                   ; preds = %lor.lhs.false
214  %cmp9 = icmp eq i8 %c, 44
215  br i1 %cmp9, label %lor.end, label %lor.lhs.false11
216
217lor.lhs.false11:                                  ; preds = %lor.lhs.false6
218  %cmp14 = icmp eq i8 %c, 58
219  br i1 %cmp14, label %lor.end, label %lor.lhs.false16
220
221lor.lhs.false16:                                  ; preds = %lor.lhs.false11
222  %cmp19 = icmp eq i8 %c, 59
223  br i1 %cmp19, label %lor.end, label %lor.lhs.false21
224
225lor.lhs.false21:                                  ; preds = %lor.lhs.false16
226  %cmp24 = icmp eq i8 %c, 60
227  br i1 %cmp24, label %lor.end, label %lor.lhs.false26
228
229lor.lhs.false26:                                  ; preds = %lor.lhs.false21
230  %cmp29 = icmp eq i8 %c, 62
231  br i1 %cmp29, label %lor.end, label %lor.lhs.false31
232
233lor.lhs.false31:                                  ; preds = %lor.lhs.false26
234  %cmp34 = icmp eq i8 %c, 34
235  br i1 %cmp34, label %lor.end, label %lor.lhs.false36
236
237lor.lhs.false36:                                  ; preds = %lor.lhs.false31
238  %cmp39 = icmp eq i8 %c, 92
239  br i1 %cmp39, label %lor.end, label %lor.rhs
240
241lor.rhs:                                          ; preds = %lor.lhs.false36
242  %cmp43 = icmp eq i8 %c, 39
243  br label %lor.end
244
245lor.end:                                          ; preds = %lor.rhs, %lor.lhs.false36, %lor.lhs.false31, %lor.lhs.false26, %lor.lhs.false21, %lor.lhs.false16, %lor.lhs.false11, %lor.lhs.false6, %lor.lhs.false, %entry
246  %0 = phi i1 [ true, %lor.lhs.false36 ], [ true, %lor.lhs.false31 ], [ true, %lor.lhs.false26 ], [ true, %lor.lhs.false21 ], [ true, %lor.lhs.false16 ], [ true, %lor.lhs.false11 ], [ true, %lor.lhs.false6 ], [ true, %lor.lhs.false ], [ true, %entry ], [ %cmp43, %lor.rhs ]
247  %conv46 = zext i1 %0 to i32
248  ret i32 %conv46
249
250; CHECK: @test9
251; CHECK:   %cmp = icmp ult i8 %c, 33
252; CHECK:   br i1 %cmp, label %lor.end, label %switch.early.test
253
254; CHECK: switch.early.test:
255; CHECK:   switch i8 %c, label %lor.rhs [
256; CHECK:     i8 92, label %lor.end
257; CHECK:     i8 62, label %lor.end
258; CHECK:     i8 60, label %lor.end
259; CHECK:     i8 59, label %lor.end
260; CHECK:     i8 58, label %lor.end
261; CHECK:     i8 46, label %lor.end
262; CHECK:     i8 44, label %lor.end
263; CHECK:     i8 34, label %lor.end
264; CHECK:     i8 39, label %lor.end
265; CHECK:   ]
266}
267
268define i32 @test10(i32 %mode, i1 %Cond) {
269  %A = icmp ne i32 %mode, 0
270  %B = icmp ne i32 %mode, 51
271  %C = and i1 %A, %B
272  %D = and i1 %C, %Cond
273  br i1 %D, label %T, label %F
274T:
275  ret i32 123
276F:
277  ret i32 324
278
279; CHECK: @test10
280; CHECK:  br i1 %Cond, label %switch.early.test, label %F
281; CHECK:switch.early.test:
282; CHECK:  switch i32 %mode, label %T [
283; CHECK:    i32 51, label %F
284; CHECK:    i32 0, label %F
285; CHECK:  ]
286}
287
288; PR8780
289define i32 @test11(i32 %bar) nounwind {
290entry:
291  %cmp = icmp eq i32 %bar, 4
292  %cmp2 = icmp eq i32 %bar, 35
293  %or.cond = or i1 %cmp, %cmp2
294  %cmp5 = icmp eq i32 %bar, 53
295  %or.cond1 = or i1 %or.cond, %cmp5
296  %cmp8 = icmp eq i32 %bar, 24
297  %or.cond2 = or i1 %or.cond1, %cmp8
298  %cmp11 = icmp eq i32 %bar, 23
299  %or.cond3 = or i1 %or.cond2, %cmp11
300  %cmp14 = icmp eq i32 %bar, 55
301  %or.cond4 = or i1 %or.cond3, %cmp14
302  %cmp17 = icmp eq i32 %bar, 12
303  %or.cond5 = or i1 %or.cond4, %cmp17
304  %cmp20 = icmp eq i32 %bar, 35
305  %or.cond6 = or i1 %or.cond5, %cmp20
306  br i1 %or.cond6, label %if.then, label %if.end
307
308if.then:                                          ; preds = %entry
309  br label %return
310
311if.end:                                           ; preds = %entry
312  br label %return
313
314return:                                           ; preds = %if.end, %if.then
315  %retval.0 = phi i32 [ 1, %if.then ], [ 0, %if.end ]
316  ret i32 %retval.0
317
318; CHECK: @test11
319; CHECK: switch i32 %bar, label %if.end [
320; CHECK:   i32 55, label %return
321; CHECK:   i32 53, label %return
322; CHECK:   i32 35, label %return
323; CHECK:   i32 24, label %return
324; CHECK:   i32 23, label %return
325; CHECK:   i32 12, label %return
326; CHECK:   i32 4, label %return
327; CHECK: ]
328}
329
330define void @test12() nounwind {
331entry:
332  br label %bb49.us.us
333
334bb49.us.us:
335  %A = icmp eq i32 undef, undef
336  br i1 %A, label %bb55.us.us, label %malformed
337
338bb48.us.us:
339  %B = icmp ugt i32 undef, undef
340  br i1 %B, label %bb55.us.us, label %bb49.us.us
341
342bb55.us.us:
343  br label %bb48.us.us
344
345malformed:
346  ret void
347; CHECK: @test12
348
349}
350
351; test13 - handle switch formation with ult.
352define void @test13(i32 %x) nounwind ssp noredzone {
353entry:
354  %cmp = icmp ult i32 %x, 2
355  br i1 %cmp, label %if.then, label %lor.lhs.false3
356
357lor.lhs.false3:                                   ; preds = %lor.lhs.false
358  %cmp5 = icmp eq i32 %x, 3
359  br i1 %cmp5, label %if.then, label %lor.lhs.false6
360
361lor.lhs.false6:                                   ; preds = %lor.lhs.false3
362  %cmp8 = icmp eq i32 %x, 4
363  br i1 %cmp8, label %if.then, label %lor.lhs.false9
364
365lor.lhs.false9:                                   ; preds = %lor.lhs.false6
366  %cmp11 = icmp eq i32 %x, 6
367  br i1 %cmp11, label %if.then, label %if.end
368
369if.then:                                          ; preds = %lor.lhs.false9, %lor.lhs.false6, %lor.lhs.false3, %lor.lhs.false, %entry
370  call void @foo1() noredzone
371  br label %if.end
372
373if.end:                                           ; preds = %if.then, %lor.lhs.false9
374  ret void
375; CHECK: @test13
376; CHECK:  switch i32 %x, label %if.end [
377; CHECK:     i32 6, label %if.then
378; CHECK:     i32 4, label %if.then
379; CHECK:     i32 3, label %if.then
380; CHECK:     i32 1, label %if.then
381; CHECK:     i32 0, label %if.then
382; CHECK:   ]
383}
384
385; test14 - handle switch formation with ult.
386define void @test14(i32 %x) nounwind ssp noredzone {
387entry:
388  %cmp = icmp ugt i32 %x, 2
389  br i1 %cmp, label %lor.lhs.false3, label %if.then
390
391lor.lhs.false3:                                   ; preds = %lor.lhs.false
392  %cmp5 = icmp ne i32 %x, 3
393  br i1 %cmp5, label %lor.lhs.false6, label %if.then
394
395lor.lhs.false6:                                   ; preds = %lor.lhs.false3
396  %cmp8 = icmp ne i32 %x, 4
397  br i1 %cmp8, label %lor.lhs.false9, label %if.then
398
399lor.lhs.false9:                                   ; preds = %lor.lhs.false6
400  %cmp11 = icmp ne i32 %x, 6
401  br i1 %cmp11, label %if.end, label %if.then
402
403if.then:                                          ; preds = %lor.lhs.false9, %lor.lhs.false6, %lor.lhs.false3, %lor.lhs.false, %entry
404  call void @foo1() noredzone
405  br label %if.end
406
407if.end:                                           ; preds = %if.then, %lor.lhs.false9
408  ret void
409; CHECK: @test14
410; CHECK:  switch i32 %x, label %if.end [
411; CHECK:     i32 6, label %if.then
412; CHECK:     i32 4, label %if.then
413; CHECK:     i32 3, label %if.then
414; CHECK:     i32 1, label %if.then
415; CHECK:     i32 0, label %if.then
416; CHECK:   ]
417}
418
419; Don't crash on ginormous ranges.
420define void @test15(i128 %x) nounwind {
421  %cmp = icmp ugt i128 %x, 2
422  br i1 %cmp, label %if.end, label %lor.false
423
424lor.false:
425  %cmp2 = icmp ne i128 %x, 100000000000000000000
426  br i1 %cmp2, label %if.end, label %if.then
427
428if.then:
429  call void @foo1() noredzone
430  br label %if.end
431
432if.end:
433  ret void
434
435; CHECK: @test15
436; CHECK-NOT: switch
437; CHECK: ret void
438}
439
440; PR8675
441; rdar://5134905
442define zeroext i1 @test16(i32 %x) nounwind {
443entry:
444; CHECK: @test16
445; CHECK: %x.off = add i32 %x, -1
446; CHECK: %switch = icmp ult i32 %x.off, 3
447  %cmp.i = icmp eq i32 %x, 1
448  br i1 %cmp.i, label %lor.end, label %lor.lhs.false
449
450lor.lhs.false:
451  %cmp.i2 = icmp eq i32 %x, 2
452  br i1 %cmp.i2, label %lor.end, label %lor.rhs
453
454lor.rhs:
455  %cmp.i1 = icmp eq i32 %x, 3
456  br label %lor.end
457
458lor.end:
459  %0 = phi i1 [ true, %lor.lhs.false ], [ true, %entry ], [ %cmp.i1, %lor.rhs ]
460  ret i1 %0
461}
462
463; Check that we don't turn an icmp into a switch where it's not useful.
464define void @test17(i32 %x, i32 %y) {
465  %cmp = icmp ult i32 %x, 3
466  %switch = icmp ult i32 %y, 2
467  %or.cond775 = or i1 %cmp, %switch
468  br i1 %or.cond775, label %lor.lhs.false8, label %return
469
470lor.lhs.false8:
471  tail call void @foo1()
472  ret void
473
474return:
475  ret void
476
477; CHECK: @test17
478; CHECK-NOT: switch.early.test
479; CHECK-NOT: switch i32
480; CHECK: ret void
481}
482
483