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