; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -S -passes=indvars < %s | FileCheck %s

; Check that we replace signed comparisons between non-negative values with
; unsigned comparisons if we can.

target datalayout = "n8:16:32:64"

define i32 @test_01(i32 %a, i32 %b, ptr %p) {
; CHECK-LABEL: @test_01(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP_ENTRY:%.*]]
; CHECK:       loop.entry:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_BE:%.*]] ]
; CHECK-NEXT:    [[CMP1:%.*]] = icmp samesign ult i32 [[IV]], 100
; CHECK-NEXT:    br i1 [[CMP1]], label [[B1:%.*]], label [[B2:%.*]]
; CHECK:       b1:
; CHECK-NEXT:    store i32 [[IV]], ptr [[P:%.*]], align 4
; CHECK-NEXT:    br label [[MERGE:%.*]]
; CHECK:       b2:
; CHECK-NEXT:    store i32 [[A:%.*]], ptr [[P]], align 4
; CHECK-NEXT:    br label [[MERGE]]
; CHECK:       merge:
; CHECK-NEXT:    [[CMP2:%.*]] = icmp samesign ult i32 [[IV]], 100
; CHECK-NEXT:    br i1 [[CMP2]], label [[B3:%.*]], label [[B4:%.*]]
; CHECK:       b3:
; CHECK-NEXT:    store i32 [[IV]], ptr [[P]], align 4
; CHECK-NEXT:    br label [[LOOP_BE]]
; CHECK:       b4:
; CHECK-NEXT:    store i32 [[B:%.*]], ptr [[P]], align 4
; CHECK-NEXT:    br label [[LOOP_BE]]
; CHECK:       loop.be:
; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], 1000
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP_ENTRY]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i32 999
;

entry:
  br label %loop.entry

loop.entry:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.be ]
  %cmp1 = icmp slt i32 %iv, 100
  br i1 %cmp1, label %b1, label %b2

b1:
  store i32 %iv, ptr %p
  br label %merge

b2:
  store i32 %a, ptr %p
  br label %merge

merge:
  %cmp2 = icmp ult i32 %iv, 100
  br i1 %cmp2, label %b3, label %b4

b3:
  store i32 %iv, ptr %p
  br label %loop.be

b4:
  store i32 %b, ptr %p
  br label %loop.be

loop.be:
  %iv.next = add i32 %iv, 1
  %cmp3 = icmp slt i32 %iv.next, 1000
  br i1 %cmp3, label %loop.entry, label %exit

exit:
  ret i32 %iv
}

define i32 @test_02(i32 %a, i32 %b, ptr %p) {
; CHECK-LABEL: @test_02(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP_ENTRY:%.*]]
; CHECK:       loop.entry:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_BE:%.*]] ]
; CHECK-NEXT:    [[CMP1:%.*]] = icmp samesign ugt i32 100, [[IV]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[B1:%.*]], label [[B2:%.*]]
; CHECK:       b1:
; CHECK-NEXT:    store i32 [[IV]], ptr [[P:%.*]], align 4
; CHECK-NEXT:    br label [[MERGE:%.*]]
; CHECK:       b2:
; CHECK-NEXT:    store i32 [[A:%.*]], ptr [[P]], align 4
; CHECK-NEXT:    br label [[MERGE]]
; CHECK:       merge:
; CHECK-NEXT:    [[CMP2:%.*]] = icmp samesign ugt i32 100, [[IV]]
; CHECK-NEXT:    br i1 [[CMP2]], label [[B3:%.*]], label [[B4:%.*]]
; CHECK:       b3:
; CHECK-NEXT:    store i32 [[IV]], ptr [[P]], align 4
; CHECK-NEXT:    br label [[LOOP_BE]]
; CHECK:       b4:
; CHECK-NEXT:    store i32 [[B:%.*]], ptr [[P]], align 4
; CHECK-NEXT:    br label [[LOOP_BE]]
; CHECK:       loop.be:
; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], 1000
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP_ENTRY]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i32 999
;

entry:
  br label %loop.entry

loop.entry:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.be ]
  %cmp1 = icmp sgt i32 100, %iv
  br i1 %cmp1, label %b1, label %b2

b1:
  store i32 %iv, ptr %p
  br label %merge

b2:
  store i32 %a, ptr %p
  br label %merge

merge:
  %cmp2 = icmp ugt i32 100, %iv
  br i1 %cmp2, label %b3, label %b4

b3:
  store i32 %iv, ptr %p
  br label %loop.be

b4:
  store i32 %b, ptr %p
  br label %loop.be

loop.be:
  %iv.next = add i32 %iv, 1
  %cmp3 = icmp sgt i32 1000, %iv.next
  br i1 %cmp3, label %loop.entry, label %exit

exit:
  ret i32 %iv
}

define i32 @test_03(ptr %p, ptr %capacity_p, ptr %num_elements_p) {
; CHECK-LABEL: @test_03(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CAPACITY:%.*]] = load i32, ptr [[CAPACITY_P:%.*]], align 4, !range [[RNG0:![0-9]+]]
; CHECK-NEXT:    [[NUM_ELEMENTS:%.*]] = load i32, ptr [[NUM_ELEMENTS_P:%.*]], align 4, !range [[RNG0]]
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT:    [[BYTES_TO_WRITE:%.*]] = sub nuw nsw i32 [[CAPACITY]], [[IV]]
; CHECK-NEXT:    [[CAPACITY_CHECK:%.*]] = icmp slt i32 [[BYTES_TO_WRITE]], 4
; CHECK-NEXT:    br i1 [[CAPACITY_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
; CHECK:       backedge:
; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P:%.*]], i32 [[IV]]
; CHECK-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[NUM_ELEMENTS]]
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
; CHECK:       out_of_bounds:
; CHECK-NEXT:    ret i32 -1
;
entry:
  %capacity = load i32, ptr %capacity_p, !range !0
  %num_elements = load i32, ptr %num_elements_p, !range !0
  br label %loop

loop:
  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
  %bytes_to_write = sub i32 %capacity, %iv
  %capacity_check = icmp slt i32 %bytes_to_write, 4
  br i1 %capacity_check, label %out_of_bounds, label %backedge

backedge:
  %el.ptr = getelementptr i32, ptr %p, i32 %iv
  store i32 1, ptr %el.ptr
  %iv.next = add nuw nsw i32 %iv, 4
  %loop_cond = icmp slt i32 %iv.next, %num_elements
  br i1 %loop_cond, label %loop, label %exit

exit:
  ret i32 %iv.next

out_of_bounds:
  ret i32 -1
}

define i32 @test_04(ptr %p, ptr %capacity_p, ptr %num_elements_p) {
; CHECK-LABEL: @test_04(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CAPACITY:%.*]] = load i32, ptr [[CAPACITY_P:%.*]], align 4, !range [[RNG0]]
; CHECK-NEXT:    [[NUM_ELEMENTS:%.*]] = load i32, ptr [[NUM_ELEMENTS_P:%.*]], align 4, !range [[RNG0]]
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT:    [[BYTES_TO_WRITE:%.*]] = sub nuw nsw i32 [[CAPACITY]], [[IV]]
; CHECK-NEXT:    [[CAPACITY_CHECK:%.*]] = icmp sle i32 [[BYTES_TO_WRITE]], 3
; CHECK-NEXT:    br i1 [[CAPACITY_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
; CHECK:       backedge:
; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P:%.*]], i32 [[IV]]
; CHECK-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[NUM_ELEMENTS]]
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
; CHECK:       out_of_bounds:
; CHECK-NEXT:    ret i32 -1
;
entry:
  %capacity = load i32, ptr %capacity_p, !range !0
  %num_elements = load i32, ptr %num_elements_p, !range !0
  br label %loop

loop:
  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
  %bytes_to_write = sub i32 %capacity, %iv
  %capacity_check = icmp sle i32 %bytes_to_write, 3
  br i1 %capacity_check, label %out_of_bounds, label %backedge

backedge:
  %el.ptr = getelementptr i32, ptr %p, i32 %iv
  store i32 1, ptr %el.ptr
  %iv.next = add nuw nsw i32 %iv, 4
  %loop_cond = icmp slt i32 %iv.next, %num_elements
  br i1 %loop_cond, label %loop, label %exit

exit:
  ret i32 %iv.next

out_of_bounds:
  ret i32 -1
}

define i32 @test_05(ptr %p, ptr %capacity_p, ptr %num_elements_p) {
; CHECK-LABEL: @test_05(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CAPACITY:%.*]] = load i32, ptr [[CAPACITY_P:%.*]], align 4, !range [[RNG0]]
; CHECK-NEXT:    [[NUM_ELEMENTS:%.*]] = load i32, ptr [[NUM_ELEMENTS_P:%.*]], align 4, !range [[RNG0]]
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT:    [[BYTES_TO_WRITE:%.*]] = sub nuw nsw i32 [[CAPACITY]], [[IV]]
; CHECK-NEXT:    [[CAPACITY_CHECK:%.*]] = icmp ult i32 [[BYTES_TO_WRITE]], 4
; CHECK-NEXT:    br i1 [[CAPACITY_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
; CHECK:       backedge:
; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P:%.*]], i32 [[IV]]
; CHECK-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[NUM_ELEMENTS]]
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
; CHECK:       out_of_bounds:
; CHECK-NEXT:    ret i32 -1
;
entry:
  %capacity = load i32, ptr %capacity_p, !range !0
  %num_elements = load i32, ptr %num_elements_p, !range !0
  br label %loop

loop:
  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
  %bytes_to_write = sub i32 %capacity, %iv
  %capacity_check = icmp ult i32 %bytes_to_write, 4
  br i1 %capacity_check, label %out_of_bounds, label %backedge

backedge:
  %el.ptr = getelementptr i32, ptr %p, i32 %iv
  store i32 1, ptr %el.ptr
  %iv.next = add nuw nsw i32 %iv, 4
  %loop_cond = icmp slt i32 %iv.next, %num_elements
  br i1 %loop_cond, label %loop, label %exit

exit:
  ret i32 %iv.next

out_of_bounds:
  ret i32 -1
}

define i32 @test_06(ptr %p, ptr %capacity_p, ptr %num_elements_p) {
; CHECK-LABEL: @test_06(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CAPACITY:%.*]] = load i32, ptr [[CAPACITY_P:%.*]], align 4, !range [[RNG0]]
; CHECK-NEXT:    [[NUM_ELEMENTS:%.*]] = load i32, ptr [[NUM_ELEMENTS_P:%.*]], align 4, !range [[RNG0]]
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT:    [[BYTES_TO_WRITE:%.*]] = sub nuw nsw i32 [[CAPACITY]], [[IV]]
; CHECK-NEXT:    [[CAPACITY_CHECK:%.*]] = icmp ule i32 [[BYTES_TO_WRITE]], 3
; CHECK-NEXT:    br i1 [[CAPACITY_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]]
; CHECK:       backedge:
; CHECK-NEXT:    [[EL_PTR:%.*]] = getelementptr i32, ptr [[P:%.*]], i32 [[IV]]
; CHECK-NEXT:    store i32 1, ptr [[EL_PTR]], align 4
; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[NUM_ELEMENTS]]
; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ]
; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
; CHECK:       out_of_bounds:
; CHECK-NEXT:    ret i32 -1
;
entry:
  %capacity = load i32, ptr %capacity_p, !range !0
  %num_elements = load i32, ptr %num_elements_p, !range !0
  br label %loop

loop:
  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
  %bytes_to_write = sub i32 %capacity, %iv
  %capacity_check = icmp ule i32 %bytes_to_write, 3
  br i1 %capacity_check, label %out_of_bounds, label %backedge

backedge:
  %el.ptr = getelementptr i32, ptr %p, i32 %iv
  store i32 1, ptr %el.ptr
  %iv.next = add nuw nsw i32 %iv, 4
  %loop_cond = icmp slt i32 %iv.next, %num_elements
  br i1 %loop_cond, label %loop, label %exit

exit:
  ret i32 %iv.next

out_of_bounds:
  ret i32 -1
}

define void @slt_no_smax_needed(i64 %n, ptr %dst) {
; CHECK-LABEL: @slt_no_smax_needed(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[N_TRUNC:%.*]] = trunc i64 [[N:%.*]] to i32
; CHECK-NEXT:    [[ADD_1:%.*]] = add i32 [[N_TRUNC]], 1
; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 [[ADD_1]], 1
; CHECK-NEXT:    [[PRE:%.*]] = icmp ult i32 [[ADD_1]], 8
; CHECK-NEXT:    br i1 [[PRE]], label [[EXIT:%.*]], label [[LOOP_PREHEADER:%.*]]
; CHECK:       loop.preheader:
; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[SHR]], i32 1)
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[LOOP_PREHEADER]] ]
; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, ptr [[DST:%.*]], i32 [[IV]]
; CHECK-NEXT:    store i8 0, ptr [[GEP]], align 1
; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], [[SMAX]]
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
; CHECK:       exit.loopexit:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;
entry:
  %n.trunc = trunc i64 %n to i32
  %add.1 = add i32 %n.trunc, 1
  %shr = lshr i32 %add.1, 1
  %pre = icmp ult i32 %add.1, 8
  br i1 %pre, label %exit, label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  %gep = getelementptr inbounds i8, ptr %dst, i32 %iv
  store i8 0, ptr %gep, align 1
  %iv.next = add i32 %iv, 1
  %ec = icmp slt i32 %iv.next, %shr
  br i1 %ec, label %loop, label %exit

exit:
  ret void
}

define void @ult_no_umax_needed(i64 %n, ptr %dst) {
; CHECK-LABEL: @ult_no_umax_needed(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[N_TRUNC:%.*]] = trunc i64 [[N:%.*]] to i32
; CHECK-NEXT:    [[ADD_1:%.*]] = add i32 [[N_TRUNC]], 1
; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 [[ADD_1]], 1
; CHECK-NEXT:    [[PRE:%.*]] = icmp ult i32 [[ADD_1]], 8
; CHECK-NEXT:    br i1 [[PRE]], label [[EXIT:%.*]], label [[LOOP_PREHEADER:%.*]]
; CHECK:       loop.preheader:
; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[SHR]], i32 1)
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[LOOP_PREHEADER]] ]
; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, ptr [[DST:%.*]], i32 [[IV]]
; CHECK-NEXT:    store i8 0, ptr [[GEP]], align 1
; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], [[UMAX]]
; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
; CHECK:       exit.loopexit:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;
entry:
  %n.trunc = trunc i64 %n to i32
  %add.1 = add i32 %n.trunc, 1
  %shr = lshr i32 %add.1, 1
  %pre = icmp ult i32 %add.1, 8
  br i1 %pre, label %exit, label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  %gep = getelementptr inbounds i8, ptr %dst, i32 %iv
  store i8 0, ptr %gep, align 1
  %iv.next = add i32 %iv, 1
  %ec = icmp ult i32 %iv.next, %shr
  br i1 %ec, label %loop, label %exit

exit:
  ret void
}

!0 = !{i32 1, i32 2147483648}