Run DCE after a LoopFlatten test to reduce spurious output [nfc]
[llvm-project.git] / llvm / test / Analysis / ScalarEvolution / different-loops-recs.ll
blob349c6bde6991262f472c76cb1592392fe4ae80ff
1 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s
3 ; This test set ensures that we can correctly operate with recurrencies from
4 ; different loops.
6 ; Check that we can evaluate a sum of phis from two different loops in any
7 ; order.
9 define void @test_00() {
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}<nuw><nsw><%loop1>,+,1}<nw><%loop2>
22 ; CHECK:       %s2 = add i32 %phi5, %phi2
23 ; CHECK-NEXT:  -->  {{{{}}57,+,2}<nuw><nsw><%loop1>,+,2}<nw><%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}<nuw><nsw><%loop1>,+,3}<%loop2>
30 ; CHECK:       %s6 = add i32 %sum2, %phi6
31 ; CHECK-NEXT:  -->  {{{{}}63,+,6}<%loop1>,+,3}<nw><%loop2>
33 entry:
34   br label %loop1
36 loop1:
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
48 loop2:
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
60 exit:
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
70 ; Check that we can evaluate a sum of phis+invariants from two different loops
71 ; in any order.
73 define void @test_01(i32 %a, i32 %b) {
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}<nw><%loop2>
96 ; CHECK:       %s4 = add i32 %phi2, %is2
97 ; CHECK-NEXT:  -->  {{{{}}(159 + (2 * %b)),+,2}<nw><%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>
103 entry:
104   br label %loop1
106 loop1:
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
119 loop2:
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
133 exit:
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
143 ; Check that we can correctly evaluate a sum of phis+variants from two different
144 ; loops in any order.
146 define void @test_02(i32 %a, i32 %b, ptr %p) {
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)
178 entry:
179   br label %loop1
181 loop1:
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, ptr %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
195 loop2:
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, ptr %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
211 exit:
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
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.
226 define void @test_03(i32 %a, i32 %b, i32 %c, ptr %p) {
228 ; CHECK-LABEL: Classifying expressions for: @test_03
229 ; CHECK:       %v1 = load i32, ptr %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)
238 entry:
239   br label %loop1
241 loop1:
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
247 loop2:
248   %phi2 = phi i32 [ %a, %loop1 ], [ %phi2.inc, %loop2 ]
249   %phi2.inc = add i32 %phi2, 2
250   %v1 = load i32, ptr %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
257 exit:
259   ret void
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.
264 define void @test_04() {
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> U: [2,9223372036854775807) S: [2,9223372036854775807)
275 ; CHECK:       %tmp9 = sext i8 %tmp8 to i64
276 ; CHECK-NEXT:  -->  (sext i8 %tmp8 to i64) U: [-128,128) S: [-128,128)
277 ; CHECK:       %tmp10 = sub i64 %tmp9, %tmp7
278 ; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i64) + {-2,+,-1}<nsw><%loop2>) U: [9223372036854775682,126) S: [9223372036854775682,126)
279 ; CHECK:       %tmp11 = add i64 %tmp10, undef
280 ; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i64) + {(-2 + undef),+,-1}<nw><%loop2>)
281 ; CHECK:       %tmp13 = trunc i64 %tmp11 to i32
282 ; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i32) + {(-2 + (trunc i64 undef to i32)),+,-1}<%loop2>)
283 ; CHECK:       %tmp14 = sub i32 %tmp13, %tmp2
284 ; `{{[{][{]}}` is the ugliness needed to match `{{`
285 ; CHECK-NEXT:  -->  ((sext i8 %tmp8 to i32) + {{[{][{]}}(-4 + (trunc i64 undef to i32)),+,-1}<%loop1>,+,-1}<%loop2>)
286 ; CHECK:       %tmp15 = add nuw nsw i64 %tmp7, 1
287 ; CHECK-NEXT:  -->  {3,+,1}<nuw><nsw><%loop2>
290   br label %loop1
292 loop1:
293   %tmp = phi i64 [ 2, %bb ], [ %tmp4, %bb3 ]
294   %tmp2 = trunc i64 %tmp to i32
295   br i1 undef, label %loop2, label %bb3
297 bb3:
298   %tmp4 = add nuw nsw i64 %tmp, 1
299   br label %loop1
301 bb5:
302   ret void
304 loop2:
305   %tmp7 = phi i64 [ %tmp15, %loop2 ], [ 2, %loop1 ]
306   %tmp8 = load i8, ptr addrspace(1) undef, align 1
307   %tmp9 = sext i8 %tmp8 to i64
308   %tmp10 = sub i64 %tmp9, %tmp7
309   %tmp11 = add i64 %tmp10, undef
310   %tmp13 = trunc i64 %tmp11 to i32
311   %tmp14 = sub i32 %tmp13, %tmp2
312   %tmp15 = add nuw nsw i64 %tmp7, 1
313   %tmp16 = icmp slt i64 %tmp15, %tmp
314   br i1 %tmp16, label %loop2, label %bb5
317 @A = weak global [1000 x i32] zeroinitializer, align 32
319 ; Demonstrate a situation when we can add two recs with different degrees from
320 ; the same loop.
321 define void @test_05(i32 %N) {
323 ; CHECK-LABEL: Classifying expressions for: @test_05
324 ; CHECK:       %SQ = mul i32 %i.0, %i.0
325 ; CHECK-NEXT:  -->  {4,+,5,+,2}<%bb3>
326 ; CHECK:       %tmp4 = mul i32 %i.0, 2
327 ; CHECK-NEXT:  -->  {4,+,2}<nuw><nsw><%bb3>
328 ; CHECK:       %tmp5 = sub i32 %SQ, %tmp4
329 ; CHECK-NEXT:  -->  {0,+,3,+,2}<%bb3>
331 entry:
332         %"alloca point" = bitcast i32 0 to i32           ; <i32> [#uses=0]
333         br label %bb3
335 bb:             ; preds = %bb3
336         %tmp = getelementptr [1000 x i32], ptr @A, i32 0, i32 %i.0          ; <ptr> [#uses=1]
337         store i32 123, ptr %tmp
338         %tmp2 = add i32 %i.0, 1         ; <i32> [#uses=1]
339         br label %bb3
341 bb3:            ; preds = %bb, %entry
342         %i.0 = phi i32 [ 2, %entry ], [ %tmp2, %bb ]            ; <i32> [#uses=3]
343         %SQ = mul i32 %i.0, %i.0
344         %tmp4 = mul i32 %i.0, 2
345         %tmp5 = sub i32 %SQ, %tmp4
346         %tmp3 = icmp sle i32 %tmp5, 9999          ; <i1> [#uses=1]
347         br i1 %tmp3, label %bb, label %bb5
349 bb5:            ; preds = %bb3
350         br label %return
352 return:         ; preds = %bb5
353         ret void
356 ; Check that we can add Phis from different loops with different nesting, nested
357 ; loop comes first.
358 define void @test_06() {
360 ; CHECK-LABEL: Classifying expressions for: @test_06
361 ; CHECK:       %s1 = add i32 %phi1, %phi2
362 ; CHECK-NEXT:  -->  {{{{}}30,+,1}<nuw><nsw><%loop1>,+,2}<nw><%loop2>
363 ; CHECK:       %s2 = add i32 %phi2, %phi1
364 ; CHECK-NEXT:  -->  {{{{}}30,+,1}<nuw><nsw><%loop1>,+,2}<nw><%loop2>
365 ; CHECK:       %s3 = add i32 %phi1, %phi3
366 ; CHECK-NEXT:  -->  {{{{}}40,+,1}<nuw><nsw><%loop1>,+,3}<nw><%loop3>
367 ; CHECK:       %s4 = add i32 %phi3, %phi1
368 ; CHECK-NEXT:  -->  {{{{}}40,+,1}<nuw><nsw><%loop1>,+,3}<nw><%loop3>
369 ; CHECK:       %s5 = add i32 %phi2, %phi3
370 ; CHECK-NEXT:  -->  {{{{}}50,+,2}<nuw><nsw><%loop2>,+,3}<nw><%loop3>
371 ; CHECK:       %s6 = add i32 %phi3, %phi2
372 ; CHECK-NEXT:  -->  {{{{}}50,+,2}<nuw><nsw><%loop2>,+,3}<nw><%loop3>
374 entry:
375   br label %loop1
377 loop1:
378   %phi1 = phi i32 [ 10, %entry ], [ %phi1.inc, %loop1.exit ]
379   br label %loop2
381 loop2:
382   %phi2 = phi i32 [ 20, %loop1 ], [ %phi2.inc, %loop2 ]
383   %phi2.inc = add i32 %phi2, 2
384   %cond2 = icmp ult i32 %phi2.inc, 1000
385   br i1 %cond2, label %loop2, label %loop1.exit
387 loop1.exit:
388   %phi1.inc = add i32 %phi1, 1
389   %cond1 = icmp ult i32 %phi1.inc, 1000
390   br i1 %cond1, label %loop1, label %loop3
392 loop3:
393   %phi3 = phi i32 [ 30, %loop1.exit ], [ %phi3.inc, %loop3 ]
394   %phi3.inc = add i32 %phi3, 3
395   %cond3 = icmp ult i32 %phi3.inc, 1000
396   br i1 %cond3, label %loop3, label %exit
398 exit:
399   %s1 = add i32 %phi1, %phi2
400   %s2 = add i32 %phi2, %phi1
401   %s3 = add i32 %phi1, %phi3
402   %s4 = add i32 %phi3, %phi1
403   %s5 = add i32 %phi2, %phi3
404   %s6 = add i32 %phi3, %phi2
405   ret void
408 ; Check that we can add Phis from different loops with different nesting, nested
409 ; loop comes second.
410 define void @test_07() {
412 ; CHECK-LABEL: Classifying expressions for: @test_07
413 ; CHECK:       %s1 = add i32 %phi1, %phi2
414 ; CHECK-NEXT:  -->  {{{{}}30,+,1}<nuw><nsw><%loop1>,+,2}<nw><%loop2>
415 ; CHECK:       %s2 = add i32 %phi2, %phi1
416 ; CHECK-NEXT:  -->  {{{{}}30,+,1}<nuw><nsw><%loop1>,+,2}<nw><%loop2>
417 ; CHECK:       %s3 = add i32 %phi1, %phi3
418 ; CHECK-NEXT:  -->  {{{{}}40,+,3}<nuw><nsw><%loop3>,+,1}<nw><%loop1>
419 ; CHECK:       %s4 = add i32 %phi3, %phi1
420 ; CHECK-NEXT:  -->  {{{{}}40,+,3}<nuw><nsw><%loop3>,+,1}<nw><%loop1>
421 ; CHECK:       %s5 = add i32 %phi2, %phi3
422 ; CHECK-NEXT:  -->  {{{{}}50,+,3}<nuw><nsw><%loop3>,+,2}<nw><%loop2>
423 ; CHECK:       %s6 = add i32 %phi3, %phi2
424 ; CHECK-NEXT:  -->  {{{{}}50,+,3}<nuw><nsw><%loop3>,+,2}<nw><%loop2>
426 entry:
427   br label %loop3
429 loop3:
430   %phi3 = phi i32 [ 30, %entry ], [ %phi3.inc, %loop3 ]
431   %phi3.inc = add i32 %phi3, 3
432   %cond3 = icmp ult i32 %phi3.inc, 1000
433   br i1 %cond3, label %loop3, label %loop1
435 loop1:
436   %phi1 = phi i32 [ 10, %loop3 ], [ %phi1.inc, %loop1.exit ]
437   br label %loop2
439 loop2:
440   %phi2 = phi i32 [ 20, %loop1 ], [ %phi2.inc, %loop2 ]
441   %phi2.inc = add i32 %phi2, 2
442   %cond2 = icmp ult i32 %phi2.inc, 1000
443   br i1 %cond2, label %loop2, label %loop1.exit
445 loop1.exit:
446   %phi1.inc = add i32 %phi1, 1
447   %cond1 = icmp ult i32 %phi1.inc, 1000
448   br i1 %cond1, label %exit, label %loop1
450 exit:
451   %s1 = add i32 %phi1, %phi2
452   %s2 = add i32 %phi2, %phi1
453   %s3 = add i32 %phi1, %phi3
454   %s4 = add i32 %phi3, %phi1
455   %s5 = add i32 %phi2, %phi3
456   %s6 = add i32 %phi3, %phi2
457   ret void
460 ; Make sure that a complicated Phi does not get folded with rec's start value
461 ; of a loop which is above.
462 define void @test_08() {
464 ; CHECK-LABEL: Classifying expressions for: @test_08
465 ; CHECK:       %tmp11 = add i64 %iv.2.2, %iv.2.1
466 ; CHECK-NEXT:  -->  ({0,+,-1}<nuw><nsw><%loop_2> + %iv.2.1)
467 ; CHECK:       %tmp12 = trunc i64 %tmp11 to i32
468 ; CHECK-NEXT:  -->  ((trunc i64 %iv.2.1 to i32) + {0,+,-1}<%loop_2>)
469 ; CHECK:       %tmp14 = mul i32 %tmp12, %tmp7
470 ; CHECK-NEXT:  -->  (((trunc i64 %iv.2.1 to i32) + {0,+,-1}<%loop_2>) * {-1,+,-1}<%loop_1>)
471 ; CHECK:       %tmp16 = mul i64 %iv.2.1, %iv.1.1
472 ; CHECK-NEXT:  -->  ({2,+,1}<nuw><nsw><%loop_1> * %iv.2.1)
474 entry:
475   br label %loop_1
477 loop_1:
478   %iv.1.1 = phi i64 [ 2, %entry ], [ %iv.1.1.next, %loop_1_back_branch ]
479   %iv.1.2 = phi i32 [ -1, %entry ], [ %iv.1.2.next, %loop_1_back_branch ]
480   br label %loop_1_exit
482 dead:
483   br label %loop_1_exit
485 loop_1_exit:
486   %tmp5 = icmp sgt i64 %iv.1.1, 2
487   br i1 %tmp5, label %loop_2_preheader, label %loop_1_back_branch
489 loop_1_back_branch:
490   %iv.1.1.next = add nuw nsw i64 %iv.1.1, 1
491   %iv.1.2.next = add nsw i32 %iv.1.2, 1
492   br label %loop_1
494 loop_2_preheader:
495   %tmp6 = sub i64 1, %iv.1.1
496   %tmp7 = trunc i64 %tmp6 to i32
497   br label %loop_2
499 loop_2:
500   %iv.2.1 = phi i64 [ 0, %loop_2_preheader ], [ %tmp16, %loop_2 ]
501   %iv.2.2 = phi i64 [ 0, %loop_2_preheader ], [ %iv.2.2.next, %loop_2 ]
502   %iv.2.3 = phi i64 [ 2, %loop_2_preheader ], [ %iv.2.3.next, %loop_2 ]
503   %tmp11 = add i64 %iv.2.2, %iv.2.1
504   %tmp12 = trunc i64 %tmp11 to i32
505   %tmp14 = mul i32 %tmp12, %tmp7
506   %tmp16 = mul i64 %iv.2.1, %iv.1.1
507   %iv.2.3.next = add nuw nsw i64 %iv.2.3, 1
508   %iv.2.2.next = add nsw i64 %iv.2.2, -1
509   %tmp17 = icmp slt i64 %iv.2.3.next, %iv.1.1
510   br i1 %tmp17, label %loop_2, label %exit
512 exit:
513   %tmp10 = add i32 %iv.1.2, 3
514   ret void
517 define i64 @test_09(i32 %param) {
519 ; CHECK-LABEL: Classifying expressions for: @test_09
520 ; CHECK:       %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %outer.loop ]
521 ; CHECK-NEXT:    -->  {0,+,1}<nuw><nsw><%loop1>
522 ; CHECK:       %iv1.trunc = trunc i64 %iv1 to i32
523 ; CHECK-NEXT:    -->  {0,+,1}<%loop1>
524 ; CHECK:       %iv1.next = add nuw nsw i64 %iv1, 1
525 ; CHECK-NEXT:    -->  {1,+,1}<nuw><nsw><%loop1>
526 ; CHECK:       %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ]
527 ; CHECK-NEXT:    -->  {%param,+,1}<%loop2>
528 ; CHECK:       %iv2.next = add i32 %iv2, 1
529 ; CHECK-NEXT:    -->  {(1 + %param),+,1}<%loop2>
530 ; CHECK:       %iv2.ext = sext i32 %iv2.next to i64
531 ; CHECK-NEXT:    -->  (sext i32 {(1 + %param),+,1}<%loop2> to i64)
532 ; CHECK:       %ret = mul i64 %iv1, %iv2.ext
533 ; CHECK-NEXT:    -->  ((sext i32 {(1 + %param),+,1}<%loop2> to i64) * {0,+,1}<nuw><nsw><%loop1>)
535 entry:
536   br label %outer.loop
538 outer.loop:                                 ; preds = %loop2.exit, %entry
539   br label %loop1
541 loop1:                                           ; preds = %guarded, %outer.loop
542   %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %outer.loop ]
543   %iv1.trunc = trunc i64 %iv1 to i32
544   %cond1 = icmp ult i64 %iv1, 100
545   br i1 %cond1, label %guarded, label %deopt
547 guarded:                                          ; preds = %loop1
548   %iv1.next = add nuw nsw i64 %iv1, 1
549   %tmp16 = icmp slt i32 %iv1.trunc, 2
550   br i1 %tmp16, label %loop1, label %loop2.preheader
552 deopt:                                            ; preds = %loop1
553   unreachable
555 loop2.preheader:                                 ; preds = %guarded
556   br label %loop2
558 loop2:                                           ; preds = %loop2, %loop2.preheader
559   %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ]
560   %iv2.next = add i32 %iv2, 1
561   %cond2 = icmp slt i32 %iv2, %iv1.trunc
562   br i1 %cond2, label %loop2, label %exit
564 exit:                                          ; preds = %loop2.exit
565   %iv2.ext = sext i32 %iv2.next to i64
566   %ret = mul i64 %iv1, %iv2.ext
567   ret i64 %ret
570 define i64 @test_10(i32 %param) {
572 ; CHECK-LABEL: Classifying expressions for: @test_10
573 ; CHECK:       %uncle = phi i64 [ %uncle.outer.next, %uncle.loop.backedge ], [ 0, %outer.loop ]
574 ; CHECK-NEXT:  -->  {0,+,1}<nuw><nsw><%uncle.loop>
575 ; CHECK:       %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %uncle.loop ]
576 ; CHECK-NEXT:  -->  {0,+,1}<nuw><nsw><%loop1>
577 ; CHECK:       %iv1.trunc = trunc i64 %iv1 to i32
578 ; CHECK-NEXT:  -->  {0,+,1}<%loop1>
579 ; CHECK:       %iv1.next = add nuw nsw i64 %iv1, 1
580 ; CHECK-NEXT:  -->  {1,+,1}<nuw><nsw><%loop1>
581 ; CHECK:       %uncle.outer.next = add i64 %uncle, 1
582 ; CHECK-NEXT:  -->  {1,+,1}<nuw><nsw><%uncle.loop>
583 ; CHECK:       %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ]
584 ; CHECK-NEXT:  -->  {%param,+,1}<%loop2>
585 ; CHECK:       %iv2.next = add i32 %iv2, 1
586 ; CHECK-NEXT:  -->  {(1 + %param),+,1}<%loop2>
587 ; CHECK:       %iv2.ext = sext i32 %iv2.next to i64
588 ; CHECK-NEXT:  -->  (sext i32 {(1 + %param),+,1}<%loop2> to i64)
589 ; CHECK:       %ret = mul i64 %iv1, %iv2.ext
590 ; CHECK-NEXT:  -->  ((sext i32 {(1 + %param),+,1}<%loop2> to i64) * {0,+,1}<nuw><nsw><%loop1>)
592 entry:
593   br label %outer.loop
595 outer.loop:                                       ; preds = %entry
596   br label %uncle.loop
598 uncle.loop:                                       ; preds = %uncle.loop.backedge, %outer.loop
599   %uncle = phi i64 [ %uncle.outer.next, %uncle.loop.backedge ], [ 0, %outer.loop ]
600   br label %loop1
602 loop1:                                            ; preds = %guarded, %uncle.loop
603   %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %uncle.loop ]
604   %iv1.trunc = trunc i64 %iv1 to i32
605   %cond1 = icmp ult i64 %iv1, 100
606   br i1 %cond1, label %guarded, label %deopt
608 guarded:                                          ; preds = %loop1
609   %iv1.next = add nuw nsw i64 %iv1, 1
610   %tmp16 = icmp slt i32 %iv1.trunc, 2
611   br i1 %tmp16, label %loop1, label %uncle.loop.backedge
613 uncle.loop.backedge:                              ; preds = %guarded
614   %uncle.outer.next = add i64 %uncle, 1
615   %cond.uncle = icmp ult i64 %uncle, 120
616   br i1 %cond.uncle, label %loop2.preheader, label %uncle.loop
618 deopt:                                            ; preds = %loop1
619   unreachable
621 loop2.preheader:                                  ; preds = %uncle.loop.backedge
622   br label %loop2
624 loop2:                                            ; preds = %loop2, %loop2.preheader
625   %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ]
626   %iv2.next = add i32 %iv2, 1
627   %cond2 = icmp slt i32 %iv2, %iv1.trunc
628   br i1 %cond2, label %loop2, label %exit
630 exit:                                             ; preds = %loop2
631   %iv2.ext = sext i32 %iv2.next to i64
632   %ret = mul i64 %iv1, %iv2.ext
633   ret i64 %ret