1; RUN: opt -jump-threading -S < %s | FileCheck %s
2
3declare i32 @f1()
4declare i32 @f2()
5declare void @f3()
6
7; Make sure we can fold this branch ... We will not be able to thread it as
8; L0 is too big to duplicate. L2 is the unreachable block here.
9;
10; CHECK-LABEL: @test_br_folding_not_threading(
11; CHECK: L1:
12; CHECK: call i32 @f2()
13; CHECK: call void @f3()
14; CHECK-NEXT: ret void
15; CHECK-NOT: br
16; CHECK: L3:
17define void @test_br_folding_not_threading(i1 %cond) nounwind {
18entry:
19  br i1 %cond, label %L0, label %L3
20L0:
21  call i32 @f2()
22  call i32 @f2()
23  call i32 @f2()
24  call i32 @f2()
25  call i32 @f2()
26  call i32 @f2()
27  call i32 @f2()
28  call i32 @f2()
29  call i32 @f2()
30  call i32 @f2()
31  call i32 @f2()
32  call i32 @f2()
33  call i32 @f2()
34  br i1 %cond, label %L1, label %L2
35
36L1:
37  call void @f3()
38  ret void
39L2:
40  call void @f3()
41  ret void
42L3:
43  call void @f3()
44  ret void
45}
46
47
48; Make sure we can fold this branch ... We will not be able to thread it as
49; L0 is too big to duplicate. L2 is the unreachable block here.
50; With more than 1 predecessors.
51;
52; CHECK-LABEL: @test_br_folding_not_threading_multiple_preds(
53; CHECK: L1:
54; CHECK: call i32 @f2()
55; CHECK: call void @f3()
56; CHECK-NEXT: ret void
57; CHECK-NOT: br
58; CHECK: L3:
59define void @test_br_folding_not_threading_multiple_preds(i1 %condx, i1 %cond) nounwind {
60entry:
61  br i1 %condx, label %X0, label %X1
62
63X0:
64  br i1 %cond, label %L0, label %L3
65
66X1:
67  br i1 %cond, label %L0, label %L3
68
69L0:
70  call i32 @f2()
71  call i32 @f2()
72  call i32 @f2()
73  call i32 @f2()
74  call i32 @f2()
75  call i32 @f2()
76  call i32 @f2()
77  call i32 @f2()
78  call i32 @f2()
79  call i32 @f2()
80  call i32 @f2()
81  call i32 @f2()
82  call i32 @f2()
83  br i1 %cond, label %L1, label %L2
84
85L1:
86  call void @f3()
87  ret void
88L2:
89  call void @f3()
90  ret void
91L3:
92  call void @f3()
93  ret void
94}
95
96define i32 @test1(i1 %cond) {
97; CHECK-LABEL: @test1(
98
99	br i1 %cond, label %T1, label %F1
100
101T1:
102	%v1 = call i32 @f1()
103	br label %Merge
104
105F1:
106	%v2 = call i32 @f2()
107	br label %Merge
108
109Merge:
110	%A = phi i1 [true, %T1], [false, %F1]
111	%B = phi i32 [%v1, %T1], [%v2, %F1]
112	br i1 %A, label %T2, label %F2
113
114T2:
115; CHECK: T2:
116; CHECK: ret i32 %v1
117	call void @f3()
118	ret i32 %B
119
120F2:
121; CHECK: F2:
122; CHECK: ret i32 %v2
123	ret i32 %B
124}
125
126
127;; cond is known false on Entry -> F1 edge!
128define i32 @test2(i1 %cond) {
129; CHECK-LABEL: @test2(
130Entry:
131	br i1 %cond, label %T1, label %F1
132
133T1:
134; CHECK: %v1 = call i32 @f1()
135; CHECK: ret i32 47
136	%v1 = call i32 @f1()
137	br label %Merge
138
139F1:
140	br i1 %cond, label %Merge, label %F2
141
142Merge:
143	%B = phi i32 [47, %T1], [192, %F1]
144	ret i32 %B
145
146F2:
147	call void @f3()
148	ret i32 12
149}
150
151
152; Undef handling.
153define i32 @test3(i1 %cond) {
154; CHECK-LABEL: @test3(
155; CHECK-NEXT: T1:
156; CHECK-NEXT: ret i32 42
157	br i1 undef, label %T1, label %F1
158
159T1:
160	ret i32 42
161
162F1:
163	ret i32 17
164}
165
166define i32 @test4(i1 %cond, i1 %cond2) {
167; CHECK-LABEL: @test4(
168
169	br i1 %cond, label %T1, label %F1
170
171T1:
172; CHECK:   %v1 = call i32 @f1()
173; CHECK-NEXT:   br label %T
174
175	%v1 = call i32 @f1()
176	br label %Merge
177
178F1:
179	%v2 = call i32 @f2()
180; CHECK:   %v2 = call i32 @f2()
181; CHECK-NEXT:   br i1 %cond2,
182	br label %Merge
183
184Merge:
185	%A = phi i1 [undef, %T1], [%cond2, %F1]
186	%B = phi i32 [%v1, %T1], [%v2, %F1]
187	br i1 %A, label %T2, label %F2
188
189T2:
190	call void @f3()
191	ret i32 %B
192
193F2:
194	ret i32 %B
195}
196
197
198;; This tests that the branch in 'merge' can be cloned up into T1.
199define i32 @test5(i1 %cond, i1 %cond2) {
200; CHECK-LABEL: @test5(
201
202	br i1 %cond, label %T1, label %F1
203
204T1:
205; CHECK: T1:
206; CHECK-NEXT:   %v1 = call i32 @f1()
207; CHECK-NEXT:   %cond3 = icmp eq i32 %v1, 412
208; CHECK-NEXT:   br i1 %cond3, label %T2, label %F2
209
210	%v1 = call i32 @f1()
211        %cond3 = icmp eq i32 %v1, 412
212	br label %Merge
213
214F1:
215	%v2 = call i32 @f2()
216	br label %Merge
217
218Merge:
219	%A = phi i1 [%cond3, %T1], [%cond2, %F1]
220	%B = phi i32 [%v1, %T1], [%v2, %F1]
221	br i1 %A, label %T2, label %F2
222
223T2:
224	call void @f3()
225	ret i32 %B
226
227F2:
228	ret i32 %B
229}
230
231
232;; Lexically duplicated conditionals should be threaded.
233
234
235define i32 @test6(i32 %A) {
236; CHECK-LABEL: @test6(
237	%tmp455 = icmp eq i32 %A, 42
238	br i1 %tmp455, label %BB1, label %BB2
239
240; CHECK: call i32 @f2()
241; CHECK-NEXT: ret i32 3
242
243; CHECK: call i32 @f1()
244; CHECK-NOT: br
245; CHECK: call void @f3()
246; CHECK-NOT: br
247; CHECK: ret i32 4
248
249BB2:
250	call i32 @f1()
251	br label %BB1
252
253
254BB1:
255	%tmp459 = icmp eq i32 %A, 42
256	br i1 %tmp459, label %BB3, label %BB4
257
258BB3:
259	call i32 @f2()
260        ret i32 3
261
262BB4:
263	call void @f3()
264	ret i32 4
265}
266
267
268;; This tests that the branch in 'merge' can be cloned up into T1.
269;; rdar://7367025
270define i32 @test7(i1 %cond, i1 %cond2) {
271Entry:
272; CHECK-LABEL: @test7(
273	%v1 = call i32 @f1()
274	br i1 %cond, label %Merge, label %F1
275
276F1:
277	%v2 = call i32 @f2()
278	br label %Merge
279
280Merge:
281	%B = phi i32 [%v1, %Entry], [%v2, %F1]
282        %M = icmp ne i32 %B, %v1
283        %N = icmp eq i32 %B, 47
284        %O = and i1 %M, %N
285	br i1 %O, label %T2, label %F2
286
287; CHECK: Merge:
288; CHECK-NOT: phi
289; CHECK-NEXT:   %v2 = call i32 @f2()
290
291T2:
292	call void @f3()
293	ret i32 %B
294
295F2:
296	ret i32 %B
297; CHECK: F2:
298; CHECK-NEXT: phi i32
299}
300
301
302declare i1 @test8a()
303
304define i32 @test8b(i1 %cond, i1 %cond2) {
305; CHECK-LABEL: @test8b(
306T0:
307        %A = call i1 @test8a()
308	br i1 %A, label %T1, label %F1
309
310; CHECK: T0:
311; CHECK-NEXT: call
312; CHECK-NEXT: br i1 %A, label %T1, label %Y
313
314T1:
315        %B = call i1 @test8a()
316	br i1 %B, label %T2, label %F1
317
318; CHECK: T1:
319; CHECK-NEXT: call
320; CHECK-NEXT: br i1 %B, label %T2, label %Y
321T2:
322        %C = call i1 @test8a()
323	br i1 %cond, label %T3, label %F1
324
325; CHECK: T2:
326; CHECK-NEXT: call
327; CHECK-NEXT: br i1 %cond, label %T3, label %Y
328T3:
329        ret i32 0
330
331F1:
332        %D = phi i32 [0, %T0], [0, %T1], [1, %T2]
333        %E = icmp eq i32 %D, 1
334        %F = and i1 %E, %cond
335	br i1 %F, label %X, label %Y
336X:
337        call i1 @test8a()
338        ret i32 1
339Y:
340        ret i32 2
341}
342
343
344;;; Verify that we can handle constraint propagation through "xor x, 1".
345define i32 @test9(i1 %cond, i1 %cond2) {
346Entry:
347; CHECK-LABEL: @test9(
348	%v1 = call i32 @f1()
349	br i1 %cond, label %Merge, label %F1
350
351; CHECK: Entry:
352; CHECK-NEXT:  %v1 = call i32 @f1()
353; CHECK-NEXT:  br i1 %cond, label %F2, label %Merge
354
355F1:
356	%v2 = call i32 @f2()
357	br label %Merge
358
359Merge:
360	%B = phi i32 [%v1, %Entry], [%v2, %F1]
361        %M = icmp eq i32 %B, %v1
362        %M1 = xor i1 %M, 1
363        %N = icmp eq i32 %B, 47
364        %O = and i1 %M1, %N
365	br i1 %O, label %T2, label %F2
366
367; CHECK: Merge:
368; CHECK-NOT: phi
369; CHECK-NEXT:   %v2 = call i32 @f2()
370
371T2:
372	%Q = zext i1 %M to i32
373	ret i32 %Q
374
375F2:
376	ret i32 %B
377; CHECK: F2:
378; CHECK-NEXT: phi i32
379}
380
381
382
383; CHECK: @test10
384declare i32 @test10f1()
385declare i32 @test10f2()
386declare void @test10f3()
387
388;; Non-local condition threading.
389define i32 @test10g(i1 %cond) {
390; CHECK-LABEL: @test10g(
391; CHECK-NEXT:   br i1 %cond, label %T2, label %F2
392        br i1 %cond, label %T1, label %F1
393
394T1:
395        %v1 = call i32 @test10f1()
396        br label %Merge
397
398; CHECK: %v1 = call i32 @test10f1()
399; CHECK-NEXT: call void @f3()
400; CHECK-NEXT: ret i32 %v1
401
402F1:
403        %v2 = call i32 @test10f2()
404        br label %Merge
405
406Merge:
407        %B = phi i32 [%v1, %T1], [%v2, %F1]
408        br i1 %cond, label %T2, label %F2
409
410T2:
411        call void @f3()
412        ret i32 %B
413
414F2:
415        ret i32 %B
416}
417
418
419; Impossible conditional constraints should get threaded.  BB3 is dead here.
420define i32 @test11(i32 %A) {
421; CHECK-LABEL: @test11(
422; CHECK-NEXT: icmp
423; CHECK-NEXT: br i1 %tmp455, label %BB4, label %BB2
424	%tmp455 = icmp eq i32 %A, 42
425	br i1 %tmp455, label %BB1, label %BB2
426
427BB2:
428; CHECK: call i32 @f1()
429; CHECK-NEXT: ret i32 %C
430	%C = call i32 @f1()
431	ret i32 %C
432
433
434BB1:
435	%tmp459 = icmp eq i32 %A, 43
436	br i1 %tmp459, label %BB3, label %BB4
437
438BB3:
439	call i32 @f2()
440        ret i32 3
441
442BB4:
443	call void @f3()
444	ret i32 4
445}
446
447;; Correlated value through boolean expression.  GCC PR18046.
448define void @test12(i32 %A) {
449; CHECK-LABEL: @test12(
450entry:
451  %cond = icmp eq i32 %A, 0
452  br i1 %cond, label %bb, label %bb1
453; Should branch to the return block instead of through BB1.
454; CHECK: entry:
455; CHECK-NEXT: %cond = icmp eq i32 %A, 0
456; CHECK-NEXT: br i1 %cond, label %bb1, label %return
457
458bb:
459  %B = call i32 @test10f2()
460  br label %bb1
461
462bb1:
463  %C = phi i32 [ %A, %entry ], [ %B, %bb ]
464  %cond4 = icmp eq i32 %C, 0
465  br i1 %cond4, label %bb2, label %return
466
467; CHECK: bb1:
468; CHECK-NEXT: %B = call i32 @test10f2()
469; CHECK-NEXT: %cond4 = icmp eq i32 %B, 0
470; CHECK-NEXT: br i1 %cond4, label %bb2, label %return
471
472bb2:
473  %D = call i32 @test10f2()
474  ret void
475
476return:
477  ret void
478}
479
480
481;; Duplicate condition to avoid xor of cond.
482;; rdar://7391699
483define i32 @test13(i1 %cond, i1 %cond2) {
484Entry:
485; CHECK-LABEL: @test13(
486	%v1 = call i32 @f1()
487	br i1 %cond, label %Merge, label %F1
488
489F1:
490	br label %Merge
491
492Merge:
493	%B = phi i1 [true, %Entry], [%cond2, %F1]
494        %C = phi i32 [192, %Entry], [%v1, %F1]
495        %M = icmp eq i32 %C, 192
496        %N = xor i1 %B, %M
497	br i1 %N, label %T2, label %F2
498
499T2:
500	ret i32 123
501
502F2:
503	ret i32 %v1
504
505; CHECK:   br i1 %cond, label %F2, label %Merge
506
507; CHECK:      Merge:
508; CHECK-NEXT:   %M = icmp eq i32 %v1, 192
509; CHECK-NEXT:   %N = xor i1 %cond2, %M
510; CHECK-NEXT:   br i1 %N, label %T2, label %F2
511}
512
513; CHECK-LABEL: @test14(
514define i32 @test14(i32 %in) {
515entry:
516	%A = icmp eq i32 %in, 0
517; CHECK: br i1 %A, label %right_ret, label %merge
518  br i1 %A, label %left, label %right
519
520; CHECK-NOT: left:
521left:
522	br label %merge
523
524; CHECK-NOT: right:
525right:
526  %B = call i32 @f1()
527	br label %merge
528
529merge:
530; CHECK-NOT: %C = phi i32 [%in, %left], [%B, %right]
531	%C = phi i32 [%in, %left], [%B, %right]
532	%D = add i32 %C, 1
533	%E = icmp eq i32 %D, 2
534	br i1 %E, label %left_ret, label %right_ret
535
536; CHECK: left_ret:
537left_ret:
538	ret i32 0
539
540right_ret:
541	ret i32 1
542}
543
544; PR5652
545; CHECK-LABEL: @test15(
546define i32 @test15(i32 %len) {
547entry:
548; CHECK: icmp ult i32 %len, 13
549  %tmp = icmp ult i32 %len, 13
550  br i1 %tmp, label %check, label %exit0
551
552exit0:
553  ret i32 0
554
555check:
556  %tmp9 = icmp ult i32 %len, 21
557  br i1 %tmp9, label %exit1, label %exit2
558
559exit2:
560; CHECK-NOT: ret i32 2
561  ret i32 2
562
563exit1:
564  ret i32 1
565; CHECK: }
566}
567
568;;; Verify that we can handle constraint propagation through cast.
569define i32 @test16(i1 %cond) {
570Entry:
571; CHECK-LABEL: @test16(
572	br i1 %cond, label %Merge, label %F1
573
574; CHECK: Entry:
575; CHECK-NEXT:  br i1 %cond, label %F2, label %Merge
576
577F1:
578	%v1 = call i32 @f1()
579	br label %Merge
580
581Merge:
582	%B = phi i32 [0, %Entry], [%v1, %F1]
583	%M = icmp eq i32 %B, 0
584	%M1 = zext i1 %M to i32
585	%N = icmp eq i32 %M1, 0
586	br i1 %N, label %T2, label %F2
587
588; CHECK: Merge:
589; CHECK-NOT: phi
590; CHECK-NEXT:   %v1 = call i32 @f1()
591
592T2:
593	%Q = call i32 @f2()
594	ret i32 %Q
595
596F2:
597	ret i32 %B
598; CHECK: F2:
599; CHECK-NEXT: phi i32
600}
601
602; In this test we check that block duplication is inhibited by the presence
603; of a function with the 'noduplicate' attribute.
604
605declare void @g()
606declare void @j()
607declare void @k()
608
609; CHECK-LABEL: define void @h(i32 %p) {
610define void @h(i32 %p) {
611  %x = icmp ult i32 %p, 5
612  br i1 %x, label %l1, label %l2
613
614l1:
615  call void @j()
616  br label %l3
617
618l2:
619  call void @k()
620  br label %l3
621
622l3:
623; CHECK: call void @g() [[NOD:#[0-9]+]]
624; CHECK-NOT: call void @g() [[NOD]]
625  call void @g() noduplicate
626  %y = icmp ult i32 %p, 5
627  br i1 %y, label %l4, label %l5
628
629l4:
630  call void @j()
631  ret void
632
633l5:
634  call void @k()
635  ret void
636; CHECK: }
637}
638
639; CHECK-LABEL: define void @h_con(i32 %p) {
640define void @h_con(i32 %p) {
641  %x = icmp ult i32 %p, 5
642  br i1 %x, label %l1, label %l2
643
644l1:
645  call void @j()
646  br label %l3
647
648l2:
649  call void @k()
650  br label %l3
651
652l3:
653; CHECK: call void @g() [[CON:#[0-9]+]]
654; CHECK-NOT: call void @g() [[CON]]
655  call void @g() convergent
656  %y = icmp ult i32 %p, 5
657  br i1 %y, label %l4, label %l5
658
659l4:
660  call void @j()
661  ret void
662
663l5:
664  call void @k()
665  ret void
666; CHECK: }
667}
668
669
670; CHECK: attributes [[NOD]] = { noduplicate }
671; CHECK: attributes [[CON]] = { convergent }
672