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