; RUN: opt -verify-loop-info -irce -S < %s | FileCheck %s
; RUN: opt -verify-loop-info -passes='require<branch-prob>,irce' -S < %s | FileCheck %s

define void @decrementing_loop(i32 *%arr, i32 *%a_len_ptr, i32 %n) {
 entry:
  %len = load i32, i32* %a_len_ptr, !range !0
  %first.itr.check = icmp sgt i32 %n, 0
  %start = sub i32 %n, 1
  br i1 %first.itr.check, label %loop, label %exit

 loop:
  %idx = phi i32 [ %start, %entry ] , [ %idx.dec, %in.bounds ]
  %idx.dec = sub i32 %idx, 1
  %abc.high = icmp slt i32 %idx, %len
  %abc.low = icmp sge i32 %idx, 0
  %abc = and i1 %abc.low, %abc.high
  br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1

 in.bounds:
  %addr = getelementptr i32, i32* %arr, i32 %idx
  store i32 0, i32* %addr
  %next = icmp sgt i32 %idx.dec, -1
  br i1 %next, label %loop, label %exit

 out.of.bounds:
  ret void

 exit:
  ret void

; CHECK: loop.preheader:
; CHECK:   [[len_hiclamp:[^ ]+]] = call i32 @llvm.smin.i32(i32 %len, i32 %n)
; CHECK:   [[not_exit_preloop_at:[^ ]+]] = call i32 @llvm.smax.i32(i32 [[len_hiclamp]], i32 0)
; CHECK:   %exit.preloop.at = add nsw i32 [[not_exit_preloop_at]], -1
}

; Make sure that we can eliminate the range check when the loop looks like:
; for (i = len.a - 1; i >= 0; --i)
;   b[i] = a[i];
define void @test_01(i32* %a, i32* %b, i32* %a_len_ptr, i32* %b_len_ptr) {

; CHECK-LABEL: test_01
; CHECK:       mainloop:
; CHECK-NEXT:    br label %loop
; CHECK:       loop:
; CHECK:         %rc = and i1 true, true
; CHECK:       loop.preloop:

 entry:
  %len.a = load i32, i32* %a_len_ptr, !range !0
  %len.b = load i32, i32* %b_len_ptr, !range !0
  %first.itr.check = icmp ne i32 %len.a, 0
  br i1 %first.itr.check, label %loop, label %exit

 loop:
  %idx = phi i32 [ %len.a, %entry ] , [ %idx.next, %in.bounds ]
  %idx.next = sub i32 %idx, 1
  %rca = icmp ult i32 %idx.next, %len.a
  %rcb = icmp ult i32 %idx.next, %len.b
  %rc = and i1 %rca, %rcb
  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1

 in.bounds:
  %el.a = getelementptr i32, i32* %a, i32 %idx.next
  %el.b = getelementptr i32, i32* %b, i32 %idx.next
  %v = load i32, i32* %el.a
  store i32 %v, i32* %el.b
  %loop.cond = icmp slt i32 %idx, 2
  br i1 %loop.cond, label %exit, label %loop

 out.of.bounds:
  ret void

 exit:
  ret void
}

; Same as test_01, but the latch condition is unsigned
define void @test_02(i32* %a, i32* %b, i32* %a_len_ptr, i32* %b_len_ptr) {

; CHECK-LABEL: test_02
; CHECK:       mainloop:
; CHECK-NEXT:    br label %loop
; CHECK:       loop:
; CHECK:         %rc = and i1 true, true
; CHECK:       loop.preloop:

 entry:
  %len.a = load i32, i32* %a_len_ptr, !range !0
  %len.b = load i32, i32* %b_len_ptr, !range !0
  %first.itr.check = icmp ne i32 %len.a, 0
  br i1 %first.itr.check, label %loop, label %exit

 loop:
  %idx = phi i32 [ %len.a, %entry ] , [ %idx.next, %in.bounds ]
  %idx.next = sub i32 %idx, 1
  %rca = icmp ult i32 %idx.next, %len.a
  %rcb = icmp ult i32 %idx.next, %len.b
  %rc = and i1 %rca, %rcb
  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1

 in.bounds:
  %el.a = getelementptr i32, i32* %a, i32 %idx.next
  %el.b = getelementptr i32, i32* %b, i32 %idx.next
  %v = load i32, i32* %el.a
  store i32 %v, i32* %el.b
  %loop.cond = icmp ult i32 %idx, 2
  br i1 %loop.cond, label %exit, label %loop

 out.of.bounds:
  ret void

 exit:
  ret void
}

; Check that we can figure out that IV is non-negative via implication through
; Phi node.
define void @test_03(i32* %a, i32* %a_len_ptr, i1 %cond) {

; CHECK-LABEL: test_03
; CHECK:       mainloop:
; CHECK-NEXT:    br label %loop
; CHECK:       loop:
; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
; CHECK:       loop.preloop:

 entry:
  %len.a = load i32, i32* %a_len_ptr, !range !0
  %len.minus.one = sub nsw i32 %len.a, 1
  %len.minus.two = sub nsw i32 %len.a, 2
  br i1 %cond, label %if.true, label %if.false

if.true:
  br label %merge

if.false:
  br label %merge

merge:
  %starting.value = phi i32 [ %len.minus.two, %if.true ], [ %len.minus.one, %if.false ]
  %first.itr.check = icmp sgt i32 %len.a, 3
  br i1 %first.itr.check, label %loop, label %exit

loop:
  %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ]
  %idx.next = sub i32 %idx, 1
  %rc = icmp ult i32 %idx.next, %len.a
  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1

in.bounds:
  %el.a = getelementptr i32, i32* %a, i32 %idx.next
  %v = load i32, i32* %el.a
  %loop.cond = icmp slt i32 %idx, 2
  br i1 %loop.cond, label %exit, label %loop

out.of.bounds:
  ret void

exit:
  ret void
}

; Check that we can figure out that IV is non-negative via implication through
; two Phi nodes.
define void @test_04(i32* %a, i32* %a_len_ptr, i1 %cond) {

; CHECK-LABEL: test_04
; CHECK:       mainloop:
; CHECK-NEXT:    br label %loop
; CHECK:       loop:
; CHECK:         br i1 true, label %in.bounds, label %out.of.bounds
; CHECK:       loop.preloop:

 entry:
  %len.a = load i32, i32* %a_len_ptr, !range !0
  %len.minus.one = sub nsw i32 %len.a, 1
  %len.plus.one = add nsw i32 %len.a, 1
  %len.minus.two = sub nsw i32 %len.a, 2
  br i1 %cond, label %if.true, label %if.false

if.true:
  br label %merge

if.false:
  br label %merge

merge:
  %starting.value = phi i32 [ %len.minus.two, %if.true ], [ %len.minus.one, %if.false ]
  %len.phi = phi i32 [ %len.a, %if.true ], [ %len.plus.one, %if.false ]
  %first.itr.check = icmp sgt i32 %len.a, 3
  br i1 %first.itr.check, label %loop, label %exit

loop:
  %idx = phi i32 [ %starting.value, %merge ] , [ %idx.next, %in.bounds ]
  %idx.next = sub i32 %idx, 1
  %rc = icmp ult i32 %idx.next, %len.phi
  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1

in.bounds:
  %el.a = getelementptr i32, i32* %a, i32 %idx.next
  %v = load i32, i32* %el.a
  %loop.cond = icmp slt i32 %idx, 2
  br i1 %loop.cond, label %exit, label %loop

out.of.bounds:
  ret void

exit:
  ret void
}

; TODO: we need to be more careful when trying to look through phi nodes in
; cycles, because the condition to prove may reference the previous value of
; the phi. So we currently fail to optimize this case.
; Check that we can figure out that IV is non-negative via implication through
; two Phi nodes, one being AddRec.
define void @test_05(i32* %a, i32* %a_len_ptr, i1 %cond) {

; CHECK-LABEL: test_05
; CHECK: entry:
; CHECK:   br label %merge
; CHECK-NOT: mainloop

 entry:
  %len.a = load i32, i32* %a_len_ptr, !range !0
  %len.minus.one = sub nsw i32 %len.a, 1
  %len.plus.one = add nsw i32 %len.a, 1
  %len.minus.two = sub nsw i32 %len.a, 2
  br label %merge

merge:
  %starting.value = phi i32 [ %len.minus.two, %entry ], [ %len.minus.one, %merge ]
  %len.phi = phi i32 [ %len.a, %entry ], [ %len.phi.next, %merge ]
  %len.phi.next = add nsw i32 %len.phi, 1
  br i1 true, label %first.iter.check, label %merge

first.iter.check:
  %first.itr.check = icmp sgt i32 %len.a, 3
  br i1 %first.itr.check, label %loop, label %exit

loop:
  %idx = phi i32 [ %starting.value, %first.iter.check ] , [ %idx.next, %in.bounds ]
  %idx.next = sub i32 %idx, 1
  %rc = icmp ult i32 %idx.next, %len.phi
  br i1 %rc, label %in.bounds, label %out.of.bounds, !prof !1

in.bounds:
  %el.a = getelementptr i32, i32* %a, i32 %idx.next
  %v = load i32, i32* %el.a
  %loop.cond = icmp slt i32 %idx, 2
  br i1 %loop.cond, label %exit, label %loop

out.of.bounds:
  ret void

exit:
  ret void
}

!0 = !{i32 0, i32 2147483647}
!1 = !{!"branch_weights", i32 64, i32 4}