| ; RUN: opt -analyze -enable-new-pm=0 -scalar-evolution < %s | FileCheck %s |
| ; RUN: opt -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s |
| |
| ; This test set ensures that we can correctly operate with recurrencies from |
| ; different loops. |
| |
| ; Check that we can evaluate a sum of phis from two different loops in any |
| ; order. |
| |
| define void @test_00() { |
| |
| ; CHECK-LABEL: Classifying expressions for: @test_00 |
| ; CHECK: %sum1 = add i32 %phi1, %phi2 |
| ; CHECK-NEXT: --> {14,+,3}<%loop1> |
| ; CHECK: %sum2 = add i32 %sum1, %phi3 |
| ; CHECK-NEXT: --> {20,+,6}<%loop1> |
| ; CHECK: %sum3 = add i32 %phi4, %phi5 |
| ; CHECK-NEXT: --> {116,+,3}<%loop2> |
| ; CHECK: %sum4 = add i32 %sum3, %phi6 |
| ; CHECK-NEXT: --> {159,+,6}<%loop2> |
| ; CHECK: %s1 = add i32 %phi1, %phi4 |
| ; CHECK-NEXT: --> {{{{}}73,+,1}<%loop1>,+,1}<%loop2> |
| ; CHECK: %s2 = add i32 %phi5, %phi2 |
| ; CHECK-NEXT: --> {{{{}}57,+,2}<%loop1>,+,2}<%loop2> |
| ; CHECK: %s3 = add i32 %sum1, %sum3 |
| ; CHECK-NEXT: --> {{{{}}130,+,3}<%loop1>,+,3}<%loop2> |
| ; CHECK: %s4 = add i32 %sum4, %sum2 |
| ; CHECK-NEXT: --> {{{{}}179,+,6}<%loop1>,+,6}<%loop2> |
| ; CHECK: %s5 = add i32 %phi3, %sum3 |
| ; CHECK-NEXT: --> {{{{}}122,+,3}<%loop1>,+,3}<%loop2> |
| ; CHECK: %s6 = add i32 %sum2, %phi6 |
| ; CHECK-NEXT: --> {{{{}}63,+,6}<%loop1>,+,3}<%loop2> |
| |
| entry: |
| br label %loop1 |
| |
| loop1: |
| %phi1 = phi i32 [ 10, %entry ], [ %phi1.inc, %loop1 ] |
| %phi2 = phi i32 [ 4, %entry ], [ %phi2.inc, %loop1 ] |
| %phi3 = phi i32 [ 6, %entry ], [ %phi3.inc, %loop1 ] |
| %phi1.inc = add i32 %phi1, 1 |
| %phi2.inc = add i32 %phi2, 2 |
| %phi3.inc = add i32 %phi3, 3 |
| %sum1 = add i32 %phi1, %phi2 |
| %sum2 = add i32 %sum1, %phi3 |
| %cond1 = icmp ult i32 %sum2, 1000 |
| br i1 %cond1, label %loop1, label %loop2 |
| |
| loop2: |
| %phi4 = phi i32 [ 63, %loop1 ], [ %phi4.inc, %loop2 ] |
| %phi5 = phi i32 [ 53, %loop1 ], [ %phi5.inc, %loop2 ] |
| %phi6 = phi i32 [ 43, %loop1 ], [ %phi6.inc, %loop2 ] |
| %phi4.inc = add i32 %phi4, 1 |
| %phi5.inc = add i32 %phi5, 2 |
| %phi6.inc = add i32 %phi6, 3 |
| %sum3 = add i32 %phi4, %phi5 |
| %sum4 = add i32 %sum3, %phi6 |
| %cond2 = icmp ult i32 %sum4, 1000 |
| br i1 %cond2, label %loop2, label %exit |
| |
| exit: |
| %s1 = add i32 %phi1, %phi4 |
| %s2 = add i32 %phi5, %phi2 |
| %s3 = add i32 %sum1, %sum3 |
| %s4 = add i32 %sum4, %sum2 |
| %s5 = add i32 %phi3, %sum3 |
| %s6 = add i32 %sum2, %phi6 |
| ret void |
| } |
| |
| ; Check that we can evaluate a sum of phis+invariants from two different loops |
| ; in any order. |
| |
| define void @test_01(i32 %a, i32 %b) { |
| |
| ; CHECK-LABEL: Classifying expressions for: @test_01 |
| ; CHECK: %sum1 = add i32 %phi1, %phi2 |
| ; CHECK-NEXT: --> {(%a + %b),+,3}<%loop1> |
| ; CHECK: %sum2 = add i32 %sum1, %phi3 |
| ; CHECK-NEXT: --> {(6 + %a + %b),+,6}<%loop1> |
| ; CHECK: %is1 = add i32 %sum2, %a |
| ; CHECK-NEXT: --> {(6 + (2 * %a) + %b),+,6}<%loop1> |
| ; CHECK: %sum3 = add i32 %phi4, %phi5 |
| ; CHECK-NEXT: --> {116,+,3}<%loop2> |
| ; CHECK: %sum4 = add i32 %sum3, %phi6 |
| ; CHECK-NEXT: --> {159,+,6}<%loop2> |
| ; CHECK: %is2 = add i32 %sum4, %b |
| ; CHECK-NEXT: --> {(159 + %b),+,6}<%loop2> |
| ; CHECK: %ec2 = add i32 %is1, %is2 |
| ; CHECK-NEXT: --> {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2> |
| ; CHECK: %s1 = add i32 %phi1, %is1 |
| ; CHECK-NEXT: --> {(6 + (3 * %a) + %b),+,7}<%loop1> |
| ; CHECK: %s2 = add i32 %is2, %phi4 |
| ; CHECK-NEXT: --> {(222 + %b),+,7}<%loop2> |
| ; CHECK: %s3 = add i32 %is1, %phi5 |
| ; CHECK-NEXT: --> {{{{}}(59 + (2 * %a) + %b),+,6}<%loop1>,+,2}<%loop2> |
| ; CHECK: %s4 = add i32 %phi2, %is2 |
| ; CHECK-NEXT: --> {{{{}}(159 + (2 * %b)),+,2}<%loop1>,+,6}<%loop2> |
| ; CHECK: %s5 = add i32 %is1, %is2 |
| ; CHECK-NEXT: --> {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2> |
| ; CHECK: %s6 = add i32 %is2, %is1 |
| ; CHECK-NEXT: --> {{{{}}(165 + (2 * %a) + (2 * %b)),+,6}<%loop1>,+,6}<%loop2> |
| |
| entry: |
| br label %loop1 |
| |
| loop1: |
| %phi1 = phi i32 [ %a, %entry ], [ %phi1.inc, %loop1 ] |
| %phi2 = phi i32 [ %b, %entry ], [ %phi2.inc, %loop1 ] |
| %phi3 = phi i32 [ 6, %entry ], [ %phi3.inc, %loop1 ] |
| %phi1.inc = add i32 %phi1, 1 |
| %phi2.inc = add i32 %phi2, 2 |
| %phi3.inc = add i32 %phi3, 3 |
| %sum1 = add i32 %phi1, %phi2 |
| %sum2 = add i32 %sum1, %phi3 |
| %is1 = add i32 %sum2, %a |
| %cond1 = icmp ult i32 %is1, 1000 |
| br i1 %cond1, label %loop1, label %loop2 |
| |
| loop2: |
| %phi4 = phi i32 [ 63, %loop1 ], [ %phi4.inc, %loop2 ] |
| %phi5 = phi i32 [ 53, %loop1 ], [ %phi5.inc, %loop2 ] |
| %phi6 = phi i32 [ 43, %loop1 ], [ %phi6.inc, %loop2 ] |
| %phi4.inc = add i32 %phi4, 1 |
| %phi5.inc = add i32 %phi5, 2 |
| %phi6.inc = add i32 %phi6, 3 |
| %sum3 = add i32 %phi4, %phi5 |
| %sum4 = add i32 %sum3, %phi6 |
| %is2 = add i32 %sum4, %b |
| %ec2 = add i32 %is1, %is2 |
| %cond2 = icmp ult i32 %ec2, 1000 |
| br i1 %cond2, label %loop2, label %exit |
| |
| exit: |
| %s1 = add i32 %phi1, %is1 |
| %s2 = add i32 %is2, %phi4 |
| %s3 = add i32 %is1, %phi5 |
| %s4 = add i32 %phi2, %is2 |
| %s5 = add i32 %is1, %is2 |
| %s6 = add i32 %is2, %is1 |
| ret void |
| } |
| |
| ; Check that we can correctly evaluate a sum of phis+variants from two different |
| ; loops in any order. |
| |
| define void @test_02(i32 %a, i32 %b, i32* %p) { |
| |
| ; CHECK-LABEL: Classifying expressions for: @test_02 |
| ; CHECK: %sum1 = add i32 %phi1, %phi2 |
| ; CHECK-NEXT: --> {(%a + %b),+,3}<%loop1> |
| ; CHECK: %sum2 = add i32 %sum1, %phi3 |
| ; CHECK-NEXT: --> {(6 + %a + %b),+,6}<%loop1> |
| ; CHECK: %is1 = add i32 %sum2, %v1 |
| ; CHECK-NEXT: --> ({(6 + %a + %b),+,6}<%loop1> + %v1) |
| ; CHECK: %sum3 = add i32 %phi4, %phi5 |
| ; CHECK-NEXT: --> {(%a + %b),+,3}<%loop2> |
| ; CHECK: %sum4 = add i32 %sum3, %phi6 |
| ; CHECK-NEXT: --> {(43 + %a + %b),+,6}<%loop2> |
| ; CHECK: %is2 = add i32 %sum4, %v2 |
| ; CHECK-NEXT: --> ({(43 + %a + %b),+,6}<%loop2> + %v2) |
| ; CHECK: %is3 = add i32 %v1, %sum2 |
| ; CHECK-NEXT: --> ({(6 + %a + %b),+,6}<%loop1> + %v1) |
| ; CHECK: %ec2 = add i32 %is1, %is3 |
| ; CHECK-NEXT: --> (2 * ({(6 + %a + %b),+,6}<%loop1> + %v1)) |
| ; CHECK: %s1 = add i32 %phi1, %is1 |
| ; CHECK-NEXT: --> ({(6 + (2 * %a) + %b),+,7}<%loop1> + %v1) |
| ; CHECK: %s2 = add i32 %is2, %phi4 |
| ; CHECK-NEXT: --> ({(43 + (2 * %a) + %b),+,7}<%loop2> + %v2) |
| ; CHECK: %s3 = add i32 %is1, %phi5 |
| ; CHECK-NEXT: --> {({(6 + (2 * %b) + %a),+,6}<%loop1> + %v1),+,2}<%loop2> |
| ; CHECK: %s4 = add i32 %phi2, %is2 |
| ; CHECK-NEXT: --> ({{{{}}(43 + (2 * %b) + %a),+,2}<%loop1>,+,6}<%loop2> + %v2) |
| ; CHECK: %s5 = add i32 %is1, %is2 |
| ; CHECK-NEXT: --> ({({(49 + (2 * %a) + (2 * %b)),+,6}<%loop1> + %v1),+,6}<%loop2> + %v2) |
| ; CHECK: %s6 = add i32 %is2, %is1 |
| ; CHECK-NEXT: --> ({({(49 + (2 * %a) + (2 * %b)),+,6}<%loop1> + %v1),+,6}<%loop2> + %v2) |
| |
| entry: |
| br label %loop1 |
| |
| loop1: |
| %phi1 = phi i32 [ %a, %entry ], [ %phi1.inc, %loop1 ] |
| %phi2 = phi i32 [ %b, %entry ], [ %phi2.inc, %loop1 ] |
| %phi3 = phi i32 [ 6, %entry ], [ %phi3.inc, %loop1 ] |
| %phi1.inc = add i32 %phi1, 1 |
| %phi2.inc = add i32 %phi2, 2 |
| %phi3.inc = add i32 %phi3, 3 |
| %v1 = load i32, i32* %p |
| %sum1 = add i32 %phi1, %phi2 |
| %sum2 = add i32 %sum1, %phi3 |
| %is1 = add i32 %sum2, %v1 |
| %cond1 = icmp ult i32 %is1, 1000 |
| br i1 %cond1, label %loop1, label %loop2 |
| |
| loop2: |
| %phi4 = phi i32 [ %a, %loop1 ], [ %phi4.inc, %loop2 ] |
| %phi5 = phi i32 [ %b, %loop1 ], [ %phi5.inc, %loop2 ] |
| %phi6 = phi i32 [ 43, %loop1 ], [ %phi6.inc, %loop2 ] |
| %phi4.inc = add i32 %phi4, 1 |
| %phi5.inc = add i32 %phi5, 2 |
| %phi6.inc = add i32 %phi6, 3 |
| %v2 = load i32, i32* %p |
| %sum3 = add i32 %phi4, %phi5 |
| %sum4 = add i32 %sum3, %phi6 |
| %is2 = add i32 %sum4, %v2 |
| %is3 = add i32 %v1, %sum2 |
| %ec2 = add i32 %is1, %is3 |
| %cond2 = icmp ult i32 %ec2, 1000 |
| br i1 %cond2, label %loop2, label %exit |
| |
| exit: |
| %s1 = add i32 %phi1, %is1 |
| %s2 = add i32 %is2, %phi4 |
| %s3 = add i32 %is1, %phi5 |
| %s4 = add i32 %phi2, %is2 |
| %s5 = add i32 %is1, %is2 |
| %s6 = add i32 %is2, %is1 |
| ret void |
| } |
| |
| ; Mix of previous use cases that demonstrates %s3 can be incorrectly treated as |
| ; a recurrence of loop1 because of operands order if we pick recurrencies in an |
| ; incorrect order. It also shows that we cannot safely fold v1 (SCEVUnknown) |
| ; because we cannot prove for sure that it doesn't use Phis of loop 2. |
| |
| define void @test_03(i32 %a, i32 %b, i32 %c, i32* %p) { |
| |
| ; CHECK-LABEL: Classifying expressions for: @test_03 |
| ; CHECK: %v1 = load i32, i32* %p |
| ; CHECK-NEXT: --> %v1 |
| ; CHECK: %s1 = add i32 %phi1, %v1 |
| ; CHECK-NEXT: --> ({%a,+,1}<%loop1> + %v1) |
| ; CHECK: %s2 = add i32 %s1, %b |
| ; CHECK-NEXT: --> ({(%a + %b),+,1}<%loop1> + %v1) |
| ; CHECK: %s3 = add i32 %s2, %phi2 |
| ; CHECK-NEXT: --> ({{{{}}((2 * %a) + %b),+,1}<%loop1>,+,2}<%loop2> + %v1) |
| |
| entry: |
| br label %loop1 |
| |
| loop1: |
| %phi1 = phi i32 [ %a, %entry ], [ %phi1.inc, %loop1 ] |
| %phi1.inc = add i32 %phi1, 1 |
| %cond1 = icmp ult i32 %phi1, %c |
| br i1 %cond1, label %loop1, label %loop2 |
| |
| loop2: |
| %phi2 = phi i32 [ %a, %loop1 ], [ %phi2.inc, %loop2 ] |
| %phi2.inc = add i32 %phi2, 2 |
| %v1 = load i32, i32* %p |
| %s1 = add i32 %phi1, %v1 |
| %s2 = add i32 %s1, %b |
| %s3 = add i32 %s2, %phi2 |
| %cond2 = icmp ult i32 %s3, %c |
| br i1 %cond2, label %loop2, label %exit |
| |
| exit: |
| |
| ret void |
| } |
| |
| ; Another mix of previous use cases that demonstrates that incorrect picking of |
| ; a loop for a recurrence may cause a crash of SCEV analysis. |
| define void @test_04() { |
| |
| ; CHECK-LABEL: Classifying expressions for: @test_04 |
| ; CHECK: %tmp = phi i64 [ 2, %bb ], [ %tmp4, %bb3 ] |
| ; CHECK-NEXT: --> {2,+,1}<nuw><nsw><%loop1> |
| ; CHECK: %tmp2 = trunc i64 %tmp to i32 |
| ; CHECK-NEXT: --> {2,+,1}<%loop1> |
| ; CHECK: %tmp4 = add nuw nsw i64 %tmp, 1 |
| ; CHECK-NEXT: --> {3,+,1}<nuw><%loop1> |
| ; CHECK: %tmp7 = phi i64 [ %tmp15, %loop2 ], [ 2, %loop1 ] |
| ; CHECK-NEXT: --> {2,+,1}<nuw><nsw><%loop2> |
| ; CHECK: %tmp10 = sub i64 %tmp9, %tmp7 |
| ; CHECK-NEXT: --> ((sext i8 %tmp8 to i64) + {-2,+,-1}<nw><%loop2>) |
| ; CHECK: %tmp11 = add i64 %tmp10, undef |
| ; CHECK-NEXT: --> ((sext i8 %tmp8 to i64) + {(-2 + undef),+,-1}<nw><%loop2>) |
| ; CHECK: %tmp13 = trunc i64 %tmp11 to i32 |
| ; CHECK-NEXT: --> ((sext i8 %tmp8 to i32) + {(-2 + (trunc i64 undef to i32)),+,-1}<%loop2>) |
| ; CHECK: %tmp14 = sub i32 %tmp13, %tmp2 |
| ; `{{[{][{]}}` is the ugliness needed to match `{{` |
| ; CHECK-NEXT: --> ((sext i8 %tmp8 to i32) + {{[{][{]}}(-4 + (trunc i64 undef to i32)),+,-1}<%loop1>,+,-1}<%loop2>) |
| ; CHECK: %tmp15 = add nuw nsw i64 %tmp7, 1 |
| ; CHECK-NEXT: --> {3,+,1}<nuw><nsw><%loop2> |
| |
| bb: |
| br label %loop1 |
| |
| loop1: |
| %tmp = phi i64 [ 2, %bb ], [ %tmp4, %bb3 ] |
| %tmp2 = trunc i64 %tmp to i32 |
| br i1 undef, label %loop2, label %bb3 |
| |
| bb3: |
| %tmp4 = add nuw nsw i64 %tmp, 1 |
| br label %loop1 |
| |
| bb5: |
| ret void |
| |
| loop2: |
| %tmp7 = phi i64 [ %tmp15, %loop2 ], [ 2, %loop1 ] |
| %tmp8 = load i8, i8 addrspace(1)* undef, align 1 |
| %tmp9 = sext i8 %tmp8 to i64 |
| %tmp10 = sub i64 %tmp9, %tmp7 |
| %tmp11 = add i64 %tmp10, undef |
| %tmp13 = trunc i64 %tmp11 to i32 |
| %tmp14 = sub i32 %tmp13, %tmp2 |
| %tmp15 = add nuw nsw i64 %tmp7, 1 |
| %tmp16 = icmp slt i64 %tmp15, %tmp |
| br i1 %tmp16, label %loop2, label %bb5 |
| } |
| |
| @A = weak global [1000 x i32] zeroinitializer, align 32 |
| |
| ; Demonstrate a situation when we can add two recs with different degrees from |
| ; the same loop. |
| define void @test_05(i32 %N) { |
| |
| ; CHECK-LABEL: Classifying expressions for: @test_05 |
| ; CHECK: %SQ = mul i32 %i.0, %i.0 |
| ; CHECK-NEXT: --> {4,+,5,+,2}<%bb3> |
| ; CHECK: %tmp4 = mul i32 %i.0, 2 |
| ; CHECK-NEXT: --> {4,+,2}<nuw><nsw><%bb3> |
| ; CHECK: %tmp5 = sub i32 %SQ, %tmp4 |
| ; CHECK-NEXT: --> {0,+,3,+,2}<%bb3> |
| |
| entry: |
| %"alloca point" = bitcast i32 0 to i32 ; <i32> [#uses=0] |
| br label %bb3 |
| |
| bb: ; preds = %bb3 |
| %tmp = getelementptr [1000 x i32], [1000 x i32]* @A, i32 0, i32 %i.0 ; <i32*> [#uses=1] |
| store i32 123, i32* %tmp |
| %tmp2 = add i32 %i.0, 1 ; <i32> [#uses=1] |
| br label %bb3 |
| |
| bb3: ; preds = %bb, %entry |
| %i.0 = phi i32 [ 2, %entry ], [ %tmp2, %bb ] ; <i32> [#uses=3] |
| %SQ = mul i32 %i.0, %i.0 |
| %tmp4 = mul i32 %i.0, 2 |
| %tmp5 = sub i32 %SQ, %tmp4 |
| %tmp3 = icmp sle i32 %tmp5, 9999 ; <i1> [#uses=1] |
| br i1 %tmp3, label %bb, label %bb5 |
| |
| bb5: ; preds = %bb3 |
| br label %return |
| |
| return: ; preds = %bb5 |
| ret void |
| } |
| |
| ; Check that we can add Phis from different loops with different nesting, nested |
| ; loop comes first. |
| define void @test_06() { |
| |
| ; CHECK-LABEL: Classifying expressions for: @test_06 |
| ; CHECK: %s1 = add i32 %phi1, %phi2 |
| ; CHECK-NEXT: --> {{{{}}30,+,1}<%loop1>,+,2}<%loop2> |
| ; CHECK: %s2 = add i32 %phi2, %phi1 |
| ; CHECK-NEXT: --> {{{{}}30,+,1}<%loop1>,+,2}<%loop2> |
| ; CHECK: %s3 = add i32 %phi1, %phi3 |
| ; CHECK-NEXT: --> {{{{}}40,+,1}<%loop1>,+,3}<%loop3> |
| ; CHECK: %s4 = add i32 %phi3, %phi1 |
| ; CHECK-NEXT: --> {{{{}}40,+,1}<%loop1>,+,3}<%loop3> |
| ; CHECK: %s5 = add i32 %phi2, %phi3 |
| ; CHECK-NEXT: --> {{{{}}50,+,2}<%loop2>,+,3}<%loop3> |
| ; CHECK: %s6 = add i32 %phi3, %phi2 |
| ; CHECK-NEXT: --> {{{{}}50,+,2}<%loop2>,+,3}<%loop3> |
| |
| entry: |
| br label %loop1 |
| |
| loop1: |
| %phi1 = phi i32 [ 10, %entry ], [ %phi1.inc, %loop1.exit ] |
| br label %loop2 |
| |
| loop2: |
| %phi2 = phi i32 [ 20, %loop1 ], [ %phi2.inc, %loop2 ] |
| %phi2.inc = add i32 %phi2, 2 |
| %cond2 = icmp ult i32 %phi2.inc, 1000 |
| br i1 %cond2, label %loop2, label %loop1.exit |
| |
| loop1.exit: |
| %phi1.inc = add i32 %phi1, 1 |
| %cond1 = icmp ult i32 %phi1.inc, 1000 |
| br i1 %cond1, label %loop1, label %loop3 |
| |
| loop3: |
| %phi3 = phi i32 [ 30, %loop1.exit ], [ %phi3.inc, %loop3 ] |
| %phi3.inc = add i32 %phi3, 3 |
| %cond3 = icmp ult i32 %phi3.inc, 1000 |
| br i1 %cond3, label %loop3, label %exit |
| |
| exit: |
| %s1 = add i32 %phi1, %phi2 |
| %s2 = add i32 %phi2, %phi1 |
| %s3 = add i32 %phi1, %phi3 |
| %s4 = add i32 %phi3, %phi1 |
| %s5 = add i32 %phi2, %phi3 |
| %s6 = add i32 %phi3, %phi2 |
| ret void |
| } |
| |
| ; Check that we can add Phis from different loops with different nesting, nested |
| ; loop comes second. |
| define void @test_07() { |
| |
| ; CHECK-LABEL: Classifying expressions for: @test_07 |
| ; CHECK: %s1 = add i32 %phi1, %phi2 |
| ; CHECK-NEXT: --> {{{{}}30,+,1}<%loop1>,+,2}<%loop2> |
| ; CHECK: %s2 = add i32 %phi2, %phi1 |
| ; CHECK-NEXT: --> {{{{}}30,+,1}<%loop1>,+,2}<%loop2> |
| ; CHECK: %s3 = add i32 %phi1, %phi3 |
| ; CHECK-NEXT: --> {{{{}}40,+,3}<%loop3>,+,1}<%loop1> |
| ; CHECK: %s4 = add i32 %phi3, %phi1 |
| ; CHECK-NEXT: --> {{{{}}40,+,3}<%loop3>,+,1}<%loop1> |
| ; CHECK: %s5 = add i32 %phi2, %phi3 |
| ; CHECK-NEXT: --> {{{{}}50,+,3}<%loop3>,+,2}<%loop2> |
| ; CHECK: %s6 = add i32 %phi3, %phi2 |
| ; CHECK-NEXT: --> {{{{}}50,+,3}<%loop3>,+,2}<%loop2> |
| |
| entry: |
| br label %loop3 |
| |
| loop3: |
| %phi3 = phi i32 [ 30, %entry ], [ %phi3.inc, %loop3 ] |
| %phi3.inc = add i32 %phi3, 3 |
| %cond3 = icmp ult i32 %phi3.inc, 1000 |
| br i1 %cond3, label %loop3, label %loop1 |
| |
| loop1: |
| %phi1 = phi i32 [ 10, %loop3 ], [ %phi1.inc, %loop1.exit ] |
| br label %loop2 |
| |
| loop2: |
| %phi2 = phi i32 [ 20, %loop1 ], [ %phi2.inc, %loop2 ] |
| %phi2.inc = add i32 %phi2, 2 |
| %cond2 = icmp ult i32 %phi2.inc, 1000 |
| br i1 %cond2, label %loop2, label %loop1.exit |
| |
| loop1.exit: |
| %phi1.inc = add i32 %phi1, 1 |
| %cond1 = icmp ult i32 %phi1.inc, 1000 |
| br i1 %cond1, label %exit, label %loop1 |
| |
| exit: |
| %s1 = add i32 %phi1, %phi2 |
| %s2 = add i32 %phi2, %phi1 |
| %s3 = add i32 %phi1, %phi3 |
| %s4 = add i32 %phi3, %phi1 |
| %s5 = add i32 %phi2, %phi3 |
| %s6 = add i32 %phi3, %phi2 |
| ret void |
| } |
| |
| ; Make sure that a complicated Phi does not get folded with rec's start value |
| ; of a loop which is above. |
| define void @test_08() { |
| |
| ; CHECK-LABEL: Classifying expressions for: @test_08 |
| ; CHECK: %tmp11 = add i64 %iv.2.2, %iv.2.1 |
| ; CHECK-NEXT: --> ({0,+,-1}<nsw><%loop_2> + %iv.2.1) |
| ; CHECK: %tmp12 = trunc i64 %tmp11 to i32 |
| ; CHECK-NEXT: --> ((trunc i64 %iv.2.1 to i32) + {0,+,-1}<%loop_2>) |
| ; CHECK: %tmp14 = mul i32 %tmp12, %tmp7 |
| ; CHECK-NEXT: --> (((trunc i64 %iv.2.1 to i32) + {0,+,-1}<%loop_2>) * {-1,+,-1}<%loop_1>) |
| ; CHECK: %tmp16 = mul i64 %iv.2.1, %iv.1.1 |
| ; CHECK-NEXT: --> ({2,+,1}<nuw><nsw><%loop_1> * %iv.2.1) |
| |
| entry: |
| br label %loop_1 |
| |
| loop_1: |
| %iv.1.1 = phi i64 [ 2, %entry ], [ %iv.1.1.next, %loop_1_back_branch ] |
| %iv.1.2 = phi i32 [ -1, %entry ], [ %iv.1.2.next, %loop_1_back_branch ] |
| br label %loop_1_exit |
| |
| dead: |
| br label %loop_1_exit |
| |
| loop_1_exit: |
| %tmp5 = icmp sgt i64 %iv.1.1, 2 |
| br i1 %tmp5, label %loop_2_preheader, label %loop_1_back_branch |
| |
| loop_1_back_branch: |
| %iv.1.1.next = add nuw nsw i64 %iv.1.1, 1 |
| %iv.1.2.next = add nsw i32 %iv.1.2, 1 |
| br label %loop_1 |
| |
| loop_2_preheader: |
| %tmp6 = sub i64 1, %iv.1.1 |
| %tmp7 = trunc i64 %tmp6 to i32 |
| br label %loop_2 |
| |
| loop_2: |
| %iv.2.1 = phi i64 [ 0, %loop_2_preheader ], [ %tmp16, %loop_2 ] |
| %iv.2.2 = phi i64 [ 0, %loop_2_preheader ], [ %iv.2.2.next, %loop_2 ] |
| %iv.2.3 = phi i64 [ 2, %loop_2_preheader ], [ %iv.2.3.next, %loop_2 ] |
| %tmp11 = add i64 %iv.2.2, %iv.2.1 |
| %tmp12 = trunc i64 %tmp11 to i32 |
| %tmp14 = mul i32 %tmp12, %tmp7 |
| %tmp16 = mul i64 %iv.2.1, %iv.1.1 |
| %iv.2.3.next = add nuw nsw i64 %iv.2.3, 1 |
| %iv.2.2.next = add nsw i64 %iv.2.2, -1 |
| %tmp17 = icmp slt i64 %iv.2.3.next, %iv.1.1 |
| br i1 %tmp17, label %loop_2, label %exit |
| |
| exit: |
| %tmp10 = add i32 %iv.1.2, 3 |
| ret void |
| } |
| |
| define i64 @test_09(i32 %param) { |
| |
| ; CHECK-LABEL: Classifying expressions for: @test_09 |
| ; CHECK: %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %outer.loop ] |
| ; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%loop1> |
| ; CHECK: %iv1.trunc = trunc i64 %iv1 to i32 |
| ; CHECK-NEXT: --> {0,+,1}<%loop1> |
| ; CHECK: %iv1.next = add nuw nsw i64 %iv1, 1 |
| ; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%loop1> |
| ; CHECK: %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ] |
| ; CHECK-NEXT: --> {%param,+,1}<%loop2> |
| ; CHECK: %iv2.next = add i32 %iv2, 1 |
| ; CHECK-NEXT: --> {(1 + %param),+,1}<%loop2> |
| ; CHECK: %iv2.ext = sext i32 %iv2.next to i64 |
| ; CHECK-NEXT: --> (sext i32 {(1 + %param),+,1}<%loop2> to i64) |
| ; CHECK: %ret = mul i64 %iv1, %iv2.ext |
| ; CHECK-NEXT: --> ((sext i32 {(1 + %param),+,1}<%loop2> to i64) * {0,+,1}<nuw><nsw><%loop1>) |
| |
| entry: |
| br label %outer.loop |
| |
| outer.loop: ; preds = %loop2.exit, %entry |
| br label %loop1 |
| |
| loop1: ; preds = %guarded, %outer.loop |
| %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %outer.loop ] |
| %iv1.trunc = trunc i64 %iv1 to i32 |
| %cond1 = icmp ult i64 %iv1, 100 |
| br i1 %cond1, label %guarded, label %deopt |
| |
| guarded: ; preds = %loop1 |
| %iv1.next = add nuw nsw i64 %iv1, 1 |
| %tmp16 = icmp slt i32 %iv1.trunc, 2 |
| br i1 %tmp16, label %loop1, label %loop2.preheader |
| |
| deopt: ; preds = %loop1 |
| unreachable |
| |
| loop2.preheader: ; preds = %guarded |
| br label %loop2 |
| |
| loop2: ; preds = %loop2, %loop2.preheader |
| %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ] |
| %iv2.next = add i32 %iv2, 1 |
| %cond2 = icmp slt i32 %iv2, %iv1.trunc |
| br i1 %cond2, label %loop2, label %exit |
| |
| exit: ; preds = %loop2.exit |
| %iv2.ext = sext i32 %iv2.next to i64 |
| %ret = mul i64 %iv1, %iv2.ext |
| ret i64 %ret |
| } |
| |
| define i64 @test_10(i32 %param) { |
| |
| ; CHECK-LABEL: Classifying expressions for: @test_10 |
| ; CHECK: %uncle = phi i64 [ %uncle.outer.next, %uncle.loop.backedge ], [ 0, %outer.loop ] |
| ; CHECK-NEXT: --> {0,+,1}<%uncle.loop> |
| ; CHECK: %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %uncle.loop ] |
| ; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%loop1> |
| ; CHECK: %iv1.trunc = trunc i64 %iv1 to i32 |
| ; CHECK-NEXT: --> {0,+,1}<%loop1> |
| ; CHECK: %iv1.next = add nuw nsw i64 %iv1, 1 |
| ; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%loop1> |
| ; CHECK: %uncle.outer.next = add i64 %uncle, 1 |
| ; CHECK-NEXT: --> {1,+,1}<%uncle.loop> |
| ; CHECK: %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ] |
| ; CHECK-NEXT: --> {%param,+,1}<%loop2> |
| ; CHECK: %iv2.next = add i32 %iv2, 1 |
| ; CHECK-NEXT: --> {(1 + %param),+,1}<%loop2> |
| ; CHECK: %iv2.ext = sext i32 %iv2.next to i64 |
| ; CHECK-NEXT: --> (sext i32 {(1 + %param),+,1}<%loop2> to i64) |
| ; CHECK: %ret = mul i64 %iv1, %iv2.ext |
| ; CHECK-NEXT: --> ((sext i32 {(1 + %param),+,1}<%loop2> to i64) * {0,+,1}<nuw><nsw><%loop1>) |
| |
| entry: |
| br label %outer.loop |
| |
| outer.loop: ; preds = %entry |
| br label %uncle.loop |
| |
| uncle.loop: ; preds = %uncle.loop.backedge, %outer.loop |
| %uncle = phi i64 [ %uncle.outer.next, %uncle.loop.backedge ], [ 0, %outer.loop ] |
| br label %loop1 |
| |
| loop1: ; preds = %guarded, %uncle.loop |
| %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %uncle.loop ] |
| %iv1.trunc = trunc i64 %iv1 to i32 |
| %cond1 = icmp ult i64 %iv1, 100 |
| br i1 %cond1, label %guarded, label %deopt |
| |
| guarded: ; preds = %loop1 |
| %iv1.next = add nuw nsw i64 %iv1, 1 |
| %tmp16 = icmp slt i32 %iv1.trunc, 2 |
| br i1 %tmp16, label %loop1, label %uncle.loop.backedge |
| |
| uncle.loop.backedge: ; preds = %guarded |
| %uncle.outer.next = add i64 %uncle, 1 |
| %cond.uncle = icmp ult i64 %uncle, 120 |
| br i1 %cond.uncle, label %loop2.preheader, label %uncle.loop |
| |
| deopt: ; preds = %loop1 |
| unreachable |
| |
| loop2.preheader: ; preds = %uncle.loop.backedge |
| br label %loop2 |
| |
| loop2: ; preds = %loop2, %loop2.preheader |
| %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ] |
| %iv2.next = add i32 %iv2, 1 |
| %cond2 = icmp slt i32 %iv2, %iv1.trunc |
| br i1 %cond2, label %loop2, label %exit |
| |
| exit: ; preds = %loop2 |
| %iv2.ext = sext i32 %iv2.next to i64 |
| %ret = mul i64 %iv1, %iv2.ext |
| ret i64 %ret |
| } |