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