1; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
2
3; This test set ensures that we can correctly operate with recurrencies from
4; different loops.
5
6; Check that we can evaluate a sum of phis from two different loops in any
7; order.
8
9define void @test_00() {
10
11; CHECK-LABEL: Classifying expressions for: @test_00
12; CHECK:       %sum1 = add i32 %phi1, %phi2
13; CHECK-NEXT:  -->  {14,+,3}<%loop1>
14; CHECK:       %sum2 = add i32 %sum1, %phi3
15; CHECK-NEXT:  -->  {20,+,6}<%loop1>
16; CHECK:       %sum3 = add i32 %phi4, %phi5
17; CHECK-NEXT:  -->  {116,+,3}<%loop2>
18; CHECK:       %sum4 = add i32 %sum3, %phi6
19; CHECK-NEXT:  -->  {159,+,6}<%loop2>
20; CHECK:       %s1 = add i32 %phi1, %phi4
21; CHECK-NEXT:  -->  {{{{}}73,+,1}<%loop1>,+,1}<%loop2>
22; CHECK:       %s2 = add i32 %phi5, %phi2
23; CHECK-NEXT:  -->  {{{{}}57,+,2}<%loop1>,+,2}<%loop2>
24; CHECK:       %s3 = add i32 %sum1, %sum3
25; CHECK-NEXT:  -->  {{{{}}130,+,3}<%loop1>,+,3}<%loop2>
26; CHECK:       %s4 = add i32 %sum4, %sum2
27; CHECK-NEXT:  -->  {{{{}}179,+,6}<%loop1>,+,6}<%loop2>
28; CHECK:       %s5 = add i32 %phi3, %sum3
29; CHECK-NEXT:  -->  {{{{}}122,+,3}<%loop1>,+,3}<%loop2>
30; CHECK:       %s6 = add i32 %sum2, %phi6
31; CHECK-NEXT:  -->  {{{{}}63,+,6}<%loop1>,+,3}<%loop2>
32
33entry:
34  br label %loop1
35
36loop1:
37  %phi1 = phi i32 [ 10, %entry ], [ %phi1.inc, %loop1 ]
38  %phi2 = phi i32 [ 4, %entry ], [ %phi2.inc, %loop1 ]
39  %phi3 = phi i32 [ 6, %entry ], [ %phi3.inc, %loop1 ]
40  %phi1.inc = add i32 %phi1, 1
41  %phi2.inc = add i32 %phi2, 2
42  %phi3.inc = add i32 %phi3, 3
43  %sum1 = add i32 %phi1, %phi2
44  %sum2 = add i32 %sum1, %phi3
45  %cond1 = icmp ult i32 %sum2, 1000
46  br i1 %cond1, label %loop1, label %loop2
47
48loop2:
49  %phi4 = phi i32 [ 63, %loop1 ], [ %phi4.inc, %loop2 ]
50  %phi5 = phi i32 [ 53, %loop1 ], [ %phi5.inc, %loop2 ]
51  %phi6 = phi i32 [ 43, %loop1 ], [ %phi6.inc, %loop2 ]
52  %phi4.inc = add i32 %phi4, 1
53  %phi5.inc = add i32 %phi5, 2
54  %phi6.inc = add i32 %phi6, 3
55  %sum3 = add i32 %phi4, %phi5
56  %sum4 = add i32 %sum3, %phi6
57  %cond2 = icmp ult i32 %sum4, 1000
58  br i1 %cond2, label %loop2, label %exit
59
60exit:
61  %s1 = add i32 %phi1, %phi4
62  %s2 = add i32 %phi5, %phi2
63  %s3 = add i32 %sum1, %sum3
64  %s4 = add i32 %sum4, %sum2
65  %s5 = add i32 %phi3, %sum3
66  %s6 = add i32 %sum2, %phi6
67  ret void
68}
69
70; Check that we can evaluate a sum of phis+invariants from two different loops
71; in any order.
72
73define void @test_01(i32 %a, i32 %b) {
74
75; CHECK-LABEL: Classifying expressions for: @test_01
76; CHECK:       %sum1 = add i32 %phi1, %phi2
77; CHECK-NEXT:  -->  {(%a + %b),+,3}<%loop1>
78; CHECK:       %sum2 = add i32 %sum1, %phi3
79; CHECK-NEXT:  -->  {(6 + %a + %b),+,6}<%loop1>
80; CHECK:       %is1 = add i32 %sum2, %a
81; CHECK-NEXT:  -->  {(6 + (2 * %a) + %b),+,6}<%loop1>
82; CHECK:       %sum3 = add i32 %phi4, %phi5
83; CHECK-NEXT:  -->  {116,+,3}<%loop2>
84; CHECK:       %sum4 = add i32 %sum3, %phi6
85; CHECK-NEXT:  -->  {159,+,6}<%loop2>
86; CHECK:       %is2 = add i32 %sum4, %b
87; CHECK-NEXT:  -->  {(159 + %b),+,6}<%loop2>
88; CHECK:       %ec2 = add i32 %is1, %is2
89; CHECK-NEXT:  -->  {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2>
90; CHECK:       %s1 = add i32 %phi1, %is1
91; CHECK-NEXT:  -->  {(6 + (3 * %a) + %b),+,7}<%loop1>
92; CHECK:       %s2 = add i32 %is2, %phi4
93; CHECK-NEXT:  -->  {(222 + %b),+,7}<%loop2>
94; CHECK:       %s3 = add i32 %is1, %phi5
95; CHECK-NEXT:  -->  {{{{}}(59 + (2 * %a) + %b),+,6}<%loop1>,+,2}<%loop2>
96; CHECK:       %s4 = add i32 %phi2, %is2
97; CHECK-NEXT:  -->  {{{{}}(159 + (2 * %b)),+,2}<%loop1>,+,6}<%loop2>
98; CHECK:       %s5 = add i32 %is1, %is2
99; CHECK-NEXT:  -->  {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2>
100; CHECK:       %s6 = add i32 %is2, %is1
101; CHECK-NEXT:  -->  {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2>
102
103entry:
104  br label %loop1
105
106loop1:
107  %phi1 = phi i32 [ %a, %entry ], [ %phi1.inc, %loop1 ]
108  %phi2 = phi i32 [ %b, %entry ], [ %phi2.inc, %loop1 ]
109  %phi3 = phi i32 [ 6, %entry ], [ %phi3.inc, %loop1 ]
110  %phi1.inc = add i32 %phi1, 1
111  %phi2.inc = add i32 %phi2, 2
112  %phi3.inc = add i32 %phi3, 3
113  %sum1 = add i32 %phi1, %phi2
114  %sum2 = add i32 %sum1, %phi3
115  %is1 = add i32 %sum2, %a
116  %cond1 = icmp ult i32 %is1, 1000
117  br i1 %cond1, label %loop1, label %loop2
118
119loop2:
120  %phi4 = phi i32 [ 63, %loop1 ], [ %phi4.inc, %loop2 ]
121  %phi5 = phi i32 [ 53, %loop1 ], [ %phi5.inc, %loop2 ]
122  %phi6 = phi i32 [ 43, %loop1 ], [ %phi6.inc, %loop2 ]
123  %phi4.inc = add i32 %phi4, 1
124  %phi5.inc = add i32 %phi5, 2
125  %phi6.inc = add i32 %phi6, 3
126  %sum3 = add i32 %phi4, %phi5
127  %sum4 = add i32 %sum3, %phi6
128  %is2 = add i32 %sum4, %b
129  %ec2 = add i32 %is1, %is2
130  %cond2 = icmp ult i32 %ec2, 1000
131  br i1 %cond2, label %loop2, label %exit
132
133exit:
134  %s1 = add i32 %phi1, %is1
135  %s2 = add i32 %is2, %phi4
136  %s3 = add i32 %is1, %phi5
137  %s4 = add i32 %phi2, %is2
138  %s5 = add i32 %is1, %is2
139  %s6 = add i32 %is2, %is1
140  ret void
141}
142
143; Check that we can correctly evaluate a sum of phis+variants from two different
144; loops in any order.
145
146define void @test_02(i32 %a, i32 %b, i32* %p) {
147
148; CHECK-LABEL: Classifying expressions for: @test_02
149; CHECK:       %sum1 = add i32 %phi1, %phi2
150; CHECK-NEXT:  -->  {(%a + %b),+,3}<%loop1>
151; CHECK:       %sum2 = add i32 %sum1, %phi3
152; CHECK-NEXT:  -->  {(6 + %a + %b),+,6}<%loop1>
153; CHECK:       %is1 = add i32 %sum2, %v1
154; CHECK-NEXT:  -->  ({(6 + %a + %b),+,6}<%loop1> + %v1)
155; CHECK:       %sum3 = add i32 %phi4, %phi5
156; CHECK-NEXT:  -->  {(%a + %b),+,3}<%loop2>
157; CHECK:       %sum4 = add i32 %sum3, %phi6
158; CHECK-NEXT:  -->  {(43 + %a + %b),+,6}<%loop2>
159; CHECK:       %is2 = add i32 %sum4, %v2
160; CHECK-NEXT:  -->  ({(43 + %a + %b),+,6}<%loop2> + %v2)
161; CHECK:       %is3 = add i32 %v1, %sum2
162; CHECK-NEXT:  -->  ({(6 + %a + %b),+,6}<%loop1> + %v1)
163; CHECK:       %ec2 = add i32 %is1, %is3
164; CHECK-NEXT:  -->  (2 * ({(6 + %a + %b),+,6}<%loop1> + %v1))
165; CHECK:       %s1 = add i32 %phi1, %is1
166; CHECK-NEXT:  -->  ({(6 + (2 * %a) + %b),+,7}<%loop1> + %v1)
167; CHECK:       %s2 = add i32 %is2, %phi4
168; CHECK-NEXT:  -->  ({(43 + (2 * %a) + %b),+,7}<%loop2> + %v2)
169; CHECK:       %s3 = add i32 %is1, %phi5
170; CHECK-NEXT:  -->  {({(6 + (2 * %b) + %a),+,6}<%loop1> + %v1),+,2}<%loop2>
171; CHECK:       %s4 = add i32 %phi2, %is2
172; CHECK-NEXT:  -->  ({{{{}}(43 + (2 * %b) + %a),+,2}<%loop1>,+,6}<%loop2> + %v2)
173; CHECK:       %s5 = add i32 %is1, %is2
174; CHECK-NEXT:  -->  ({({(49 + (2 * %a) + (2 * %b)),+,6}<%loop1> + %v1),+,6}<%loop2> + %v2)
175; CHECK:       %s6 = add i32 %is2, %is1
176; CHECK-NEXT:  -->  ({({(49 + (2 * %a) + (2 * %b)),+,6}<%loop1> + %v1),+,6}<%loop2> + %v2)
177
178entry:
179  br label %loop1
180
181loop1:
182  %phi1 = phi i32 [ %a, %entry ], [ %phi1.inc, %loop1 ]
183  %phi2 = phi i32 [ %b, %entry ], [ %phi2.inc, %loop1 ]
184  %phi3 = phi i32 [ 6, %entry ], [ %phi3.inc, %loop1 ]
185  %phi1.inc = add i32 %phi1, 1
186  %phi2.inc = add i32 %phi2, 2
187  %phi3.inc = add i32 %phi3, 3
188  %v1 = load i32, i32* %p
189  %sum1 = add i32 %phi1, %phi2
190  %sum2 = add i32 %sum1, %phi3
191  %is1 = add i32 %sum2, %v1
192  %cond1 = icmp ult i32 %is1, 1000
193  br i1 %cond1, label %loop1, label %loop2
194
195loop2:
196  %phi4 = phi i32 [ %a, %loop1 ], [ %phi4.inc, %loop2 ]
197  %phi5 = phi i32 [ %b, %loop1 ], [ %phi5.inc, %loop2 ]
198  %phi6 = phi i32 [ 43, %loop1 ], [ %phi6.inc, %loop2 ]
199  %phi4.inc = add i32 %phi4, 1
200  %phi5.inc = add i32 %phi5, 2
201  %phi6.inc = add i32 %phi6, 3
202  %v2 = load i32, i32* %p
203  %sum3 = add i32 %phi4, %phi5
204  %sum4 = add i32 %sum3, %phi6
205  %is2 = add i32 %sum4, %v2
206  %is3 = add i32 %v1, %sum2
207  %ec2 = add i32 %is1, %is3
208  %cond2 = icmp ult i32 %ec2, 1000
209  br i1 %cond2, label %loop2, label %exit
210
211exit:
212  %s1 = add i32 %phi1, %is1
213  %s2 = add i32 %is2, %phi4
214  %s3 = add i32 %is1, %phi5
215  %s4 = add i32 %phi2, %is2
216  %s5 = add i32 %is1, %is2
217  %s6 = add i32 %is2, %is1
218  ret void
219}
220
221; Mix of previous use cases that demonstrates %s3 can be incorrectly treated as
222; a recurrence of loop1 because of operands order if we pick recurrencies in an
223; incorrect order. It also shows that we cannot safely fold v1 (SCEVUnknown)
224; because we cannot prove for sure that it doesn't use Phis of loop 2.
225
226define void @test_03(i32 %a, i32 %b, i32 %c, i32* %p) {
227
228; CHECK-LABEL: Classifying expressions for: @test_03
229; CHECK:       %v1 = load i32, i32* %p
230; CHECK-NEXT:  -->  %v1
231; CHECK:       %s1 = add i32 %phi1, %v1
232; CHECK-NEXT:  -->  ({%a,+,1}<%loop1> + %v1)
233; CHECK:       %s2 = add i32 %s1, %b
234; CHECK-NEXT:  -->  ({(%a + %b),+,1}<%loop1> + %v1)
235; CHECK:       %s3 = add i32 %s2, %phi2
236; CHECK-NEXT:  -->  ({{{{}}((2 * %a) + %b),+,1}<%loop1>,+,2}<%loop2> + %v1)
237
238entry:
239  br label %loop1
240
241loop1:
242  %phi1 = phi i32 [ %a, %entry ], [ %phi1.inc, %loop1 ]
243  %phi1.inc = add i32 %phi1, 1
244  %cond1 = icmp ult i32 %phi1, %c
245  br i1 %cond1, label %loop1, label %loop2
246
247loop2:
248  %phi2 = phi i32 [ %a, %loop1 ], [ %phi2.inc, %loop2 ]
249  %phi2.inc = add i32 %phi2, 2
250  %v1 = load i32, i32* %p
251  %s1 = add i32 %phi1, %v1
252  %s2 = add i32 %s1, %b
253  %s3 = add i32 %s2, %phi2
254  %cond2 = icmp ult i32 %s3, %c
255  br i1 %cond2, label %loop2, label %exit
256
257exit:
258
259  ret void
260}
261
262; Another mix of previous use cases that demonstrates that incorrect picking of
263; a loop for a recurrence may cause a crash of SCEV analysis.
264define void @test_04() {
265
266; CHECK-LABEL: Classifying expressions for: @test_04
267; CHECK:       %tmp = phi i64 [ 2, %bb ], [ %tmp4, %bb3 ]
268; CHECK-NEXT:  -->  {2,+,1}<nuw><nsw><%loop1>
269; CHECK:       %tmp2 = trunc i64 %tmp to i32
270; CHECK-NEXT:  -->  {2,+,1}<%loop1>
271; CHECK:       %tmp4 = add nuw nsw i64 %tmp, 1
272; CHECK-NEXT:  -->  {3,+,1}<nuw><%loop1>
273; CHECK:       %tmp7 = phi i64 [ %tmp15, %loop2 ], [ 2, %loop1 ]
274; CHECK-NEXT:  -->  {2,+,1}<nuw><nsw><%loop2>
275; CHECK:       %tmp10 = sub i64 %tmp9, %tmp7
276; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i64) + {-2,+,-1}<nw><%loop2>)
277; CHECK:       %tmp11 = add i64 %tmp10, undef
278; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i64) + {(-2 + undef),+,-1}<nw><%loop2>)
279; CHECK:       %tmp13 = trunc i64 %tmp11 to i32
280; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i32) + {(-2 + (trunc i64 undef to i32)),+,-1}<%loop2>)
281; CHECK:       %tmp14 = sub i32 %tmp13, %tmp2
282; `{{[{][{]}}` is the ugliness needed to match `{{`
283; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i32) + {{[{][{]}}(-4 + (trunc i64 undef to i32)),+,-1}<%loop1>,+,-1}<%loop2>)
284; CHECK:       %tmp15 = add nuw nsw i64 %tmp7, 1
285; CHECK-NEXT:  -->  {3,+,1}<nuw><nsw><%loop2>
286
287bb:
288  br label %loop1
289
290loop1:
291  %tmp = phi i64 [ 2, %bb ], [ %tmp4, %bb3 ]
292  %tmp2 = trunc i64 %tmp to i32
293  br i1 undef, label %loop2, label %bb3
294
295bb3:
296  %tmp4 = add nuw nsw i64 %tmp, 1
297  br label %loop1
298
299bb5:
300  ret void
301
302loop2:
303  %tmp7 = phi i64 [ %tmp15, %loop2 ], [ 2, %loop1 ]
304  %tmp8 = load i8, i8 addrspace(1)* undef, align 1
305  %tmp9 = sext i8 %tmp8 to i64
306  %tmp10 = sub i64 %tmp9, %tmp7
307  %tmp11 = add i64 %tmp10, undef
308  %tmp13 = trunc i64 %tmp11 to i32
309  %tmp14 = sub i32 %tmp13, %tmp2
310  %tmp15 = add nuw nsw i64 %tmp7, 1
311  %tmp16 = icmp slt i64 %tmp15, %tmp
312  br i1 %tmp16, label %loop2, label %bb5
313}
314
315@A = weak global [1000 x i32] zeroinitializer, align 32
316
317; Demonstrate a situation when we can add two recs with different degrees from
318; the same loop.
319define void @test_05(i32 %N) {
320
321; CHECK-LABEL: Classifying expressions for: @test_05
322; CHECK:       %SQ = mul i32 %i.0, %i.0
323; CHECK-NEXT:  -->  {4,+,5,+,2}<%bb3>
324; CHECK:       %tmp4 = mul i32 %i.0, 2
325; CHECK-NEXT:  -->  {4,+,2}<nuw><nsw><%bb3>
326; CHECK:       %tmp5 = sub i32 %SQ, %tmp4
327; CHECK-NEXT:  -->  {0,+,3,+,2}<%bb3>
328
329entry:
330        %"alloca point" = bitcast i32 0 to i32           ; <i32> [#uses=0]
331        br label %bb3
332
333bb:             ; preds = %bb3
334        %tmp = getelementptr [1000 x i32], [1000 x i32]* @A, i32 0, i32 %i.0          ; <i32*> [#uses=1]
335        store i32 123, i32* %tmp
336        %tmp2 = add i32 %i.0, 1         ; <i32> [#uses=1]
337        br label %bb3
338
339bb3:            ; preds = %bb, %entry
340        %i.0 = phi i32 [ 2, %entry ], [ %tmp2, %bb ]            ; <i32> [#uses=3]
341        %SQ = mul i32 %i.0, %i.0
342        %tmp4 = mul i32 %i.0, 2
343        %tmp5 = sub i32 %SQ, %tmp4
344        %tmp3 = icmp sle i32 %tmp5, 9999          ; <i1> [#uses=1]
345        br i1 %tmp3, label %bb, label %bb5
346
347bb5:            ; preds = %bb3
348        br label %return
349
350return:         ; preds = %bb5
351        ret void
352}
353
354; Check that we can add Phis from different loops with different nesting, nested
355; loop comes first.
356define void @test_06() {
357
358; CHECK-LABEL: Classifying expressions for: @test_06
359; CHECK:       %s1 = add i32 %phi1, %phi2
360; CHECK-NEXT:  -->  {{{{}}30,+,1}<%loop1>,+,2}<%loop2>
361; CHECK:       %s2 = add i32 %phi2, %phi1
362; CHECK-NEXT:  -->  {{{{}}30,+,1}<%loop1>,+,2}<%loop2>
363; CHECK:       %s3 = add i32 %phi1, %phi3
364; CHECK-NEXT:  -->  {{{{}}40,+,1}<%loop1>,+,3}<%loop3>
365; CHECK:       %s4 = add i32 %phi3, %phi1
366; CHECK-NEXT:  -->  {{{{}}40,+,1}<%loop1>,+,3}<%loop3>
367; CHECK:       %s5 = add i32 %phi2, %phi3
368; CHECK-NEXT:  -->  {{{{}}50,+,2}<%loop2>,+,3}<%loop3>
369; CHECK:       %s6 = add i32 %phi3, %phi2
370; CHECK-NEXT:  -->  {{{{}}50,+,2}<%loop2>,+,3}<%loop3>
371
372entry:
373  br label %loop1
374
375loop1:
376  %phi1 = phi i32 [ 10, %entry ], [ %phi1.inc, %loop1.exit ]
377  br label %loop2
378
379loop2:
380  %phi2 = phi i32 [ 20, %loop1 ], [ %phi2.inc, %loop2 ]
381  %phi2.inc = add i32 %phi2, 2
382  %cond2 = icmp ult i32 %phi2.inc, 1000
383  br i1 %cond2, label %loop2, label %loop1.exit
384
385loop1.exit:
386  %phi1.inc = add i32 %phi1, 1
387  %cond1 = icmp ult i32 %phi1.inc, 1000
388  br i1 %cond1, label %loop1, label %loop3
389
390loop3:
391  %phi3 = phi i32 [ 30, %loop1.exit ], [ %phi3.inc, %loop3 ]
392  %phi3.inc = add i32 %phi3, 3
393  %cond3 = icmp ult i32 %phi3.inc, 1000
394  br i1 %cond3, label %loop3, label %exit
395
396exit:
397  %s1 = add i32 %phi1, %phi2
398  %s2 = add i32 %phi2, %phi1
399  %s3 = add i32 %phi1, %phi3
400  %s4 = add i32 %phi3, %phi1
401  %s5 = add i32 %phi2, %phi3
402  %s6 = add i32 %phi3, %phi2
403  ret void
404}
405
406; Check that we can add Phis from different loops with different nesting, nested
407; loop comes second.
408define void @test_07() {
409
410; CHECK-LABEL: Classifying expressions for: @test_07
411; CHECK:       %s1 = add i32 %phi1, %phi2
412; CHECK-NEXT:  -->  {{{{}}30,+,1}<%loop1>,+,2}<%loop2>
413; CHECK:       %s2 = add i32 %phi2, %phi1
414; CHECK-NEXT:  -->  {{{{}}30,+,1}<%loop1>,+,2}<%loop2>
415; CHECK:       %s3 = add i32 %phi1, %phi3
416; CHECK-NEXT:  -->  {{{{}}40,+,3}<%loop3>,+,1}<%loop1>
417; CHECK:       %s4 = add i32 %phi3, %phi1
418; CHECK-NEXT:  -->  {{{{}}40,+,3}<%loop3>,+,1}<%loop1>
419; CHECK:       %s5 = add i32 %phi2, %phi3
420; CHECK-NEXT:  -->  {{{{}}50,+,3}<%loop3>,+,2}<%loop2>
421; CHECK:       %s6 = add i32 %phi3, %phi2
422; CHECK-NEXT:  -->  {{{{}}50,+,3}<%loop3>,+,2}<%loop2>
423
424entry:
425  br label %loop3
426
427loop3:
428  %phi3 = phi i32 [ 30, %entry ], [ %phi3.inc, %loop3 ]
429  %phi3.inc = add i32 %phi3, 3
430  %cond3 = icmp ult i32 %phi3.inc, 1000
431  br i1 %cond3, label %loop3, label %loop1
432
433loop1:
434  %phi1 = phi i32 [ 10, %loop3 ], [ %phi1.inc, %loop1.exit ]
435  br label %loop2
436
437loop2:
438  %phi2 = phi i32 [ 20, %loop1 ], [ %phi2.inc, %loop2 ]
439  %phi2.inc = add i32 %phi2, 2
440  %cond2 = icmp ult i32 %phi2.inc, 1000
441  br i1 %cond2, label %loop2, label %loop1.exit
442
443loop1.exit:
444  %phi1.inc = add i32 %phi1, 1
445  %cond1 = icmp ult i32 %phi1.inc, 1000
446  br i1 %cond1, label %exit, label %loop1
447
448exit:
449  %s1 = add i32 %phi1, %phi2
450  %s2 = add i32 %phi2, %phi1
451  %s3 = add i32 %phi1, %phi3
452  %s4 = add i32 %phi3, %phi1
453  %s5 = add i32 %phi2, %phi3
454  %s6 = add i32 %phi3, %phi2
455  ret void
456}
457
458; Make sure that a complicated Phi does not get folded with rec's start value
459; of a loop which is above.
460define void @test_08() {
461
462; CHECK-LABEL: Classifying expressions for: @test_08
463; CHECK:       %tmp11 = add i64 %iv.2.2, %iv.2.1
464; CHECK-NEXT:  -->  ({0,+,-1}<nsw><%loop_2> + %iv.2.1)
465; CHECK:       %tmp12 = trunc i64 %tmp11 to i32
466; CHECK-NEXT:  -->  ((trunc i64 %iv.2.1 to i32) + {0,+,-1}<%loop_2>)
467; CHECK:       %tmp14 = mul i32 %tmp12, %tmp7
468; CHECK-NEXT:  -->  (((trunc i64 %iv.2.1 to i32) + {0,+,-1}<%loop_2>) * {-1,+,-1}<%loop_1>)
469; CHECK:       %tmp16 = mul i64 %iv.2.1, %iv.1.1
470; CHECK-NEXT:  -->  ({2,+,1}<nuw><nsw><%loop_1> * %iv.2.1)
471
472entry:
473  br label %loop_1
474
475loop_1:
476  %iv.1.1 = phi i64 [ 2, %entry ], [ %iv.1.1.next, %loop_1_back_branch ]
477  %iv.1.2 = phi i32 [ -1, %entry ], [ %iv.1.2.next, %loop_1_back_branch ]
478  br label %loop_1_exit
479
480dead:
481  br label %loop_1_exit
482
483loop_1_exit:
484  %tmp5 = icmp sgt i64 %iv.1.1, 2
485  br i1 %tmp5, label %loop_2_preheader, label %loop_1_back_branch
486
487loop_1_back_branch:
488  %iv.1.1.next = add nuw nsw i64 %iv.1.1, 1
489  %iv.1.2.next = add nsw i32 %iv.1.2, 1
490  br label %loop_1
491
492loop_2_preheader:
493  %tmp6 = sub i64 1, %iv.1.1
494  %tmp7 = trunc i64 %tmp6 to i32
495  br label %loop_2
496
497loop_2:
498  %iv.2.1 = phi i64 [ 0, %loop_2_preheader ], [ %tmp16, %loop_2 ]
499  %iv.2.2 = phi i64 [ 0, %loop_2_preheader ], [ %iv.2.2.next, %loop_2 ]
500  %iv.2.3 = phi i64 [ 2, %loop_2_preheader ], [ %iv.2.3.next, %loop_2 ]
501  %tmp11 = add i64 %iv.2.2, %iv.2.1
502  %tmp12 = trunc i64 %tmp11 to i32
503  %tmp14 = mul i32 %tmp12, %tmp7
504  %tmp16 = mul i64 %iv.2.1, %iv.1.1
505  %iv.2.3.next = add nuw nsw i64 %iv.2.3, 1
506  %iv.2.2.next = add nsw i64 %iv.2.2, -1
507  %tmp17 = icmp slt i64 %iv.2.3.next, %iv.1.1
508  br i1 %tmp17, label %loop_2, label %exit
509
510exit:
511  %tmp10 = add i32 %iv.1.2, 3
512  ret void
513}
514
515define i64 @test_09(i32 %param) {
516
517; CHECK-LABEL: Classifying expressions for: @test_09
518; CHECK:       %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %outer.loop ]
519; CHECK-NEXT:    -->  {0,+,1}<nuw><nsw><%loop1>
520; CHECK:       %iv1.trunc = trunc i64 %iv1 to i32
521; CHECK-NEXT:    -->  {0,+,1}<%loop1>
522; CHECK:       %iv1.next = add nuw nsw i64 %iv1, 1
523; CHECK-NEXT:    -->  {1,+,1}<nuw><nsw><%loop1>
524; CHECK:       %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ]
525; CHECK-NEXT:    -->  {%param,+,1}<%loop2>
526; CHECK:       %iv2.next = add i32 %iv2, 1
527; CHECK-NEXT:    -->  {(1 + %param),+,1}<%loop2>
528; CHECK:       %iv2.ext = sext i32 %iv2.next to i64
529; CHECK-NEXT:    -->  (sext i32 {(1 + %param),+,1}<%loop2> to i64)
530; CHECK:       %ret = mul i64 %iv1, %iv2.ext
531; CHECK-NEXT:    -->  ((sext i32 {(1 + %param),+,1}<%loop2> to i64) * {0,+,1}<nuw><nsw><%loop1>)
532
533entry:
534  br label %outer.loop
535
536outer.loop:                                 ; preds = %loop2.exit, %entry
537  br label %loop1
538
539loop1:                                           ; preds = %guarded, %outer.loop
540  %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %outer.loop ]
541  %iv1.trunc = trunc i64 %iv1 to i32
542  %cond1 = icmp ult i64 %iv1, 100
543  br i1 %cond1, label %guarded, label %deopt
544
545guarded:                                          ; preds = %loop1
546  %iv1.next = add nuw nsw i64 %iv1, 1
547  %tmp16 = icmp slt i32 %iv1.trunc, 2
548  br i1 %tmp16, label %loop1, label %loop2.preheader
549
550deopt:                                            ; preds = %loop1
551  unreachable
552
553loop2.preheader:                                 ; preds = %guarded
554  br label %loop2
555
556loop2:                                           ; preds = %loop2, %loop2.preheader
557  %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ]
558  %iv2.next = add i32 %iv2, 1
559  %cond2 = icmp slt i32 %iv2, %iv1.trunc
560  br i1 %cond2, label %loop2, label %exit
561
562exit:                                          ; preds = %loop2.exit
563  %iv2.ext = sext i32 %iv2.next to i64
564  %ret = mul i64 %iv1, %iv2.ext
565  ret i64 %ret
566}
567
568define i64 @test_10(i32 %param) {
569
570; CHECK-LABEL: Classifying expressions for: @test_10
571; CHECK:       %uncle = phi i64 [ %uncle.outer.next, %uncle.loop.backedge ], [ 0, %outer.loop ]
572; CHECK-NEXT:  -->  {0,+,1}<%uncle.loop>
573; CHECK:       %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %uncle.loop ]
574; CHECK-NEXT:  -->  {0,+,1}<nuw><nsw><%loop1>
575; CHECK:       %iv1.trunc = trunc i64 %iv1 to i32
576; CHECK-NEXT:  -->  {0,+,1}<%loop1>
577; CHECK:       %iv1.next = add nuw nsw i64 %iv1, 1
578; CHECK-NEXT:  -->  {1,+,1}<nuw><nsw><%loop1>
579; CHECK:       %uncle.outer.next = add i64 %uncle, 1
580; CHECK-NEXT:  -->  {1,+,1}<%uncle.loop>
581; CHECK:       %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ]
582; CHECK-NEXT:  -->  {%param,+,1}<%loop2>
583; CHECK:       %iv2.next = add i32 %iv2, 1
584; CHECK-NEXT:  -->  {(1 + %param),+,1}<%loop2>
585; CHECK:       %iv2.ext = sext i32 %iv2.next to i64
586; CHECK-NEXT:  -->  (sext i32 {(1 + %param),+,1}<%loop2> to i64)
587; CHECK:       %ret = mul i64 %iv1, %iv2.ext
588; CHECK-NEXT:  -->  ((sext i32 {(1 + %param),+,1}<%loop2> to i64) * {0,+,1}<nuw><nsw><%loop1>)
589
590entry:
591  br label %outer.loop
592
593outer.loop:                                       ; preds = %entry
594  br label %uncle.loop
595
596uncle.loop:                                       ; preds = %uncle.loop.backedge, %outer.loop
597  %uncle = phi i64 [ %uncle.outer.next, %uncle.loop.backedge ], [ 0, %outer.loop ]
598  br label %loop1
599
600loop1:                                            ; preds = %guarded, %uncle.loop
601  %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %uncle.loop ]
602  %iv1.trunc = trunc i64 %iv1 to i32
603  %cond1 = icmp ult i64 %iv1, 100
604  br i1 %cond1, label %guarded, label %deopt
605
606guarded:                                          ; preds = %loop1
607  %iv1.next = add nuw nsw i64 %iv1, 1
608  %tmp16 = icmp slt i32 %iv1.trunc, 2
609  br i1 %tmp16, label %loop1, label %uncle.loop.backedge
610
611uncle.loop.backedge:                              ; preds = %guarded
612  %uncle.outer.next = add i64 %uncle, 1
613  %cond.uncle = icmp ult i64 %uncle, 120
614  br i1 %cond.uncle, label %loop2.preheader, label %uncle.loop
615
616deopt:                                            ; preds = %loop1
617  unreachable
618
619loop2.preheader:                                  ; preds = %uncle.loop.backedge
620  br label %loop2
621
622loop2:                                            ; preds = %loop2, %loop2.preheader
623  %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ]
624  %iv2.next = add i32 %iv2, 1
625  %cond2 = icmp slt i32 %iv2, %iv1.trunc
626  br i1 %cond2, label %loop2, label %exit
627
628exit:                                             ; preds = %loop2
629  %iv2.ext = sext i32 %iv2.next to i64
630  %ret = mul i64 %iv1, %iv2.ext
631  ret i64 %ret
632}
633