1; RUN: opt %s -jump-threading -S -enable-jump-threading-lvi | FileCheck %s
2
3declare i32 @f1()
4declare i32 @f2()
5declare void @f3()
6
7define i32 @test1(i1 %cond) {
8; CHECK: @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: @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: @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: @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: @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: @test6
148	%tmp455 = icmp eq i32 %A, 42
149	br i1 %tmp455, label %BB1, label %BB2
150
151BB2:
152; CHECK: call i32 @f1()
153; CHECK-NEXT: call void @f3()
154; CHECK-NEXT: ret i32 4
155	call i32 @f1()
156	br label %BB1
157
158
159BB1:
160	%tmp459 = icmp eq i32 %A, 42
161	br i1 %tmp459, label %BB3, label %BB4
162
163BB3:
164	call i32 @f2()
165        ret i32 3
166
167BB4:
168	call void @f3()
169	ret i32 4
170}
171
172
173;; This tests that the branch in 'merge' can be cloned up into T1.
174;; rdar://7367025
175define i32 @test7(i1 %cond, i1 %cond2) {
176Entry:
177; CHECK: @test7
178	%v1 = call i32 @f1()
179	br i1 %cond, label %Merge, label %F1
180
181F1:
182	%v2 = call i32 @f2()
183	br label %Merge
184
185Merge:
186	%B = phi i32 [%v1, %Entry], [%v2, %F1]
187        %M = icmp ne i32 %B, %v1
188        %N = icmp eq i32 %B, 47
189        %O = and i1 %M, %N
190	br i1 %O, label %T2, label %F2
191
192; CHECK: Merge:
193; CHECK-NOT: phi
194; CHECK-NEXT:   %v2 = call i32 @f2()
195
196T2:
197	call void @f3()
198	ret i32 %B
199
200F2:
201	ret i32 %B
202; CHECK: F2:
203; CHECK-NEXT: phi i32
204}
205
206
207declare i1 @test8a()
208
209define i32 @test8b(i1 %cond, i1 %cond2) {
210; CHECK: @test8b
211T0:
212        %A = call i1 @test8a()
213	br i1 %A, label %T1, label %F1
214
215; CHECK: T0:
216; CHECK-NEXT: call
217; CHECK-NEXT: br i1 %A, label %T1, label %Y
218
219T1:
220        %B = call i1 @test8a()
221	br i1 %B, label %T2, label %F1
222
223; CHECK: T1:
224; CHECK-NEXT: call
225; CHECK-NEXT: br i1 %B, label %T2, label %Y
226T2:
227        %C = call i1 @test8a()
228	br i1 %cond, label %T3, label %F1
229
230; CHECK: T2:
231; CHECK-NEXT: call
232; CHECK-NEXT: br i1 %cond, label %T3, label %Y
233T3:
234        ret i32 0
235
236F1:
237        %D = phi i32 [0, %T0], [0, %T1], [1, %T2]
238        %E = icmp eq i32 %D, 1
239        %F = and i1 %E, %cond
240	br i1 %F, label %X, label %Y
241X:
242        call i1 @test8a()
243        ret i32 1
244Y:
245        ret i32 2
246}
247
248
249;;; Verify that we can handle constraint propagation through "xor x, 1".
250define i32 @test9(i1 %cond, i1 %cond2) {
251Entry:
252; CHECK: @test9
253	%v1 = call i32 @f1()
254	br i1 %cond, label %Merge, label %F1
255
256; CHECK: Entry:
257; CHECK-NEXT:  %v1 = call i32 @f1()
258; CHECK-NEXT:  br i1 %cond, label %F2, label %Merge
259
260F1:
261	%v2 = call i32 @f2()
262	br label %Merge
263
264Merge:
265	%B = phi i32 [%v1, %Entry], [%v2, %F1]
266        %M = icmp eq i32 %B, %v1
267        %M1 = xor i1 %M, 1
268        %N = icmp eq i32 %B, 47
269        %O = and i1 %M1, %N
270	br i1 %O, label %T2, label %F2
271
272; CHECK: Merge:
273; CHECK-NOT: phi
274; CHECK-NEXT:   %v2 = call i32 @f2()
275
276T2:
277	%Q = zext i1 %M to i32
278	ret i32 %Q
279
280F2:
281	ret i32 %B
282; CHECK: F2:
283; CHECK-NEXT: phi i32
284}
285
286
287
288; CHECK: @test10
289declare i32 @test10f1()
290declare i32 @test10f2()
291declare void @test10f3()
292
293;; Non-local condition threading.
294define i32 @test10g(i1 %cond) {
295; CHECK: @test10g
296; CHECK-NEXT:   br i1 %cond, label %T2, label %F2
297        br i1 %cond, label %T1, label %F1
298
299T1:
300        %v1 = call i32 @test10f1()
301        br label %Merge
302
303; CHECK: %v1 = call i32 @test10f1()
304; CHECK-NEXT: call void @f3()
305; CHECK-NEXT: ret i32 %v1
306
307F1:
308        %v2 = call i32 @test10f2()
309        br label %Merge
310
311Merge:
312        %B = phi i32 [%v1, %T1], [%v2, %F1]
313        br i1 %cond, label %T2, label %F2
314
315T2:
316        call void @f3()
317        ret i32 %B
318
319F2:
320        ret i32 %B
321}
322
323
324; Impossible conditional constraints should get threaded.  BB3 is dead here.
325define i32 @test11(i32 %A) {
326; CHECK: @test11
327; CHECK-NEXT: icmp
328; CHECK-NEXT: br i1 %tmp455, label %BB4, label %BB2
329	%tmp455 = icmp eq i32 %A, 42
330	br i1 %tmp455, label %BB1, label %BB2
331
332BB2:
333; CHECK: call i32 @f1()
334; CHECK-NEXT: ret i32 %C
335	%C = call i32 @f1()
336	ret i32 %C
337
338
339BB1:
340	%tmp459 = icmp eq i32 %A, 43
341	br i1 %tmp459, label %BB3, label %BB4
342
343BB3:
344	call i32 @f2()
345        ret i32 3
346
347BB4:
348	call void @f3()
349	ret i32 4
350}
351
352;; Correlated value through boolean expression.  GCC PR18046.
353define void @test12(i32 %A) {
354; CHECK: @test12
355entry:
356  %cond = icmp eq i32 %A, 0
357  br i1 %cond, label %bb, label %bb1
358; Should branch to the return block instead of through BB1.
359; CHECK: entry:
360; CHECK-NEXT: %cond = icmp eq i32 %A, 0
361; CHECK-NEXT: br i1 %cond, label %bb1, label %return
362
363bb:
364  %B = call i32 @test10f2()
365  br label %bb1
366
367bb1:
368  %C = phi i32 [ %A, %entry ], [ %B, %bb ]
369  %cond4 = icmp eq i32 %C, 0
370  br i1 %cond4, label %bb2, label %return
371
372; CHECK: bb1:
373; CHECK-NEXT: %B = call i32 @test10f2()
374; CHECK-NEXT: %cond4 = icmp eq i32 %B, 0
375; CHECK-NEXT: br i1 %cond4, label %bb2, label %return
376
377bb2:
378  %D = call i32 @test10f2()
379  ret void
380
381return:
382  ret void
383}
384
385
386;; Duplicate condition to avoid xor of cond.
387;; rdar://7391699
388define i32 @test13(i1 %cond, i1 %cond2) {
389Entry:
390; CHECK: @test13
391	%v1 = call i32 @f1()
392	br i1 %cond, label %Merge, label %F1
393
394F1:
395	br label %Merge
396
397Merge:
398	%B = phi i1 [true, %Entry], [%cond2, %F1]
399        %C = phi i32 [192, %Entry], [%v1, %F1]
400        %M = icmp eq i32 %C, 192
401        %N = xor i1 %B, %M
402	br i1 %N, label %T2, label %F2
403
404T2:
405	ret i32 123
406
407F2:
408	ret i32 %v1
409
410;; FIXME: CONSTANT FOLD on clone and when phi gets eliminated.
411
412; CHECK:      Entry.Merge_crit_edge:
413; CHECK-NEXT:   %M1 = icmp eq i32 192, 192
414; CHECK-NEXT:   %N2 = xor i1 true, %M1
415; CHECK-NEXT:   br i1 %N2, label %T2, label %F2
416
417; CHECK:      Merge:
418; CHECK-NEXT:   %M = icmp eq i32 %v1, 192
419; CHECK-NEXT:   %N = xor i1 %cond2, %M
420; CHECK-NEXT:   br i1 %N, label %T2, label %F2
421}
422
423
424