; 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
}