llvm/test/Transforms/IndVarSimplify/implied-nonneg-from-unsigned-bound.ll

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

; If x <u y and y <=u INT_MIN, then x >=s 0.
; If x <=u y and y <=u INT_MAX, then x >=s 0.
; In these tests the guard compares y with x, and the exit compares
; smax(x, w) with a constant.

target datalayout = "e-m:e-i64:64-n8:16:32:64-S128"

; If y >u x and y <=u INT_MIN, then x >=s 0, which implies smax(x, w) >s -1.
define void @ugt_smin(i32 %x, i32 %w, ptr %p) {
; CHECK-LABEL: define void @ugt_smin(
; CHECK-SAME: i32 [[X:%.*]], i32 [[W:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[Y:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG0:![0-9]+]]
; CHECK-NEXT:    [[C:%.*]] = icmp ugt i32 [[Y]], [[X]]
; CHECK-NEXT:    br i1 [[C]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT:.*]]
; CHECK:       [[LOOP_PREHEADER]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], %[[LATCH:.*]] ], [ 0, %[[LOOP_PREHEADER]] ]
; CHECK-NEXT:    br i1 false, label %[[EXIT_LOOPEXIT:.*]], label %[[LATCH]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    call void @side()
; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[I_NEXT]], 100
; 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:
  %y = load i32, ptr %p, !range !2
  %c = icmp ugt i32 %y, %x
  br i1 %c, label %loop, label %exit
loop:
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %m = call i32 @llvm.smax.i32(i32 %x, i32 %w)
  %q = icmp slt i32 %m, 0
  br i1 %q, label %exit, label %latch
latch:
  call void @side()
  %i.next = add nuw nsw i32 %i, 1
  %ec = icmp ult i32 %i.next, 100
  br i1 %ec, label %loop, label %exit
exit:
  ret void
}

; If y >=u x and y <=u INT_MAX, then x >=s 0, which implies smax(x, w) >s -1.
define void @uge(i32 %x, i32 %w, ptr %p) {
; CHECK-LABEL: define void @uge(
; CHECK-SAME: i32 [[X:%.*]], i32 [[W:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[Y:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG1:![0-9]+]]
; CHECK-NEXT:    [[C:%.*]] = icmp uge i32 [[Y]], [[X]]
; CHECK-NEXT:    br i1 [[C]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT:.*]]
; CHECK:       [[LOOP_PREHEADER]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], %[[LATCH:.*]] ], [ 0, %[[LOOP_PREHEADER]] ]
; CHECK-NEXT:    br i1 false, label %[[EXIT_LOOPEXIT:.*]], label %[[LATCH]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    call void @side()
; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[I_NEXT]], 100
; 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:
  %y = load i32, ptr %p, !range !1
  %c = icmp uge i32 %y, %x
  br i1 %c, label %loop, label %exit
loop:
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %m = call i32 @llvm.smax.i32(i32 %x, i32 %w)
  %q = icmp slt i32 %m, 0
  br i1 %q, label %exit, label %latch
latch:
  call void @side()
  %i.next = add nuw nsw i32 %i, 1
  %ec = icmp ult i32 %i.next, 100
  br i1 %ec, label %loop, label %exit
exit:
  ret void
}

; If y >u x and y <u INT_MAX, then x >=s 0, which implies smax(x, w) >s -1.
define void @ugt_sle(i32 %x, i32 %w, ptr %p) {
; CHECK-LABEL: define void @ugt_sle(
; CHECK-SAME: i32 [[X:%.*]], i32 [[W:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[Y:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG2:![0-9]+]]
; CHECK-NEXT:    [[C:%.*]] = icmp ugt i32 [[Y]], [[X]]
; CHECK-NEXT:    br i1 [[C]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT:.*]]
; CHECK:       [[LOOP_PREHEADER]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], %[[LATCH:.*]] ], [ 0, %[[LOOP_PREHEADER]] ]
; CHECK-NEXT:    br i1 false, label %[[EXIT_LOOPEXIT:.*]], label %[[LATCH]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    call void @side()
; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[I_NEXT]], 100
; 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:
  %y = load i32, ptr %p, !range !0
  %c = icmp ugt i32 %y, %x
  br i1 %c, label %loop, label %exit
loop:
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %m = call i32 @llvm.smax.i32(i32 %x, i32 %w)
  %q = icmp sle i32 %m, -1
  br i1 %q, label %exit, label %latch
latch:
  call void @side()
  %i.next = add nuw nsw i32 %i, 1
  %ec = icmp ult i32 %i.next, 100
  br i1 %ec, label %loop, label %exit
exit:
  ret void
}

; If y >u x and y <u INT_MAX, then x >=s 0, which implies smax(x, w) >=s 0.
define void @ugt_sge(i32 %x, i32 %w, ptr %p) {
; CHECK-LABEL: define void @ugt_sge(
; CHECK-SAME: i32 [[X:%.*]], i32 [[W:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[Y:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG2]]
; CHECK-NEXT:    [[C:%.*]] = icmp ugt i32 [[Y]], [[X]]
; CHECK-NEXT:    br i1 [[C]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT:.*]]
; CHECK:       [[LOOP_PREHEADER]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], %[[LATCH:.*]] ], [ 0, %[[LOOP_PREHEADER]] ]
; CHECK-NEXT:    br i1 true, label %[[EXIT_LOOPEXIT:.*]], label %[[LATCH]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    call void @side()
; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[I_NEXT]], 100
; 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:
  %y = load i32, ptr %p, !range !0
  %c = icmp ugt i32 %y, %x
  br i1 %c, label %loop, label %exit
loop:
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %m = call i32 @llvm.smax.i32(i32 %x, i32 %w)
  %q = icmp sge i32 %m, 0
  br i1 %q, label %exit, label %latch
latch:
  call void @side()
  %i.next = add nuw nsw i32 %i, 1
  %ec = icmp ult i32 %i.next, 100
  br i1 %ec, label %loop, label %exit
exit:
  ret void
}

; If y >u x and y <u INT_MAX, then x >=s 0, which implies smax(x, w) >=s -5.
define void @ugt_weaker(i32 %x, i32 %w, ptr %p) {
; CHECK-LABEL: define void @ugt_weaker(
; CHECK-SAME: i32 [[X:%.*]], i32 [[W:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[Y:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG2]]
; CHECK-NEXT:    [[C:%.*]] = icmp ugt i32 [[Y]], [[X]]
; CHECK-NEXT:    br i1 [[C]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT:.*]]
; CHECK:       [[LOOP_PREHEADER]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], %[[LATCH:.*]] ], [ 0, %[[LOOP_PREHEADER]] ]
; CHECK-NEXT:    br i1 false, label %[[EXIT_LOOPEXIT:.*]], label %[[LATCH]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    call void @side()
; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[I_NEXT]], 100
; 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:
  %y = load i32, ptr %p, !range !0
  %c = icmp ugt i32 %y, %x
  br i1 %c, label %loop, label %exit
loop:
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %m = call i32 @llvm.smax.i32(i32 %x, i32 %w)
  %q = icmp slt i32 %m, -5
  br i1 %q, label %exit, label %latch
latch:
  call void @side()
  %i.next = add nuw nsw i32 %i, 1
  %ec = icmp ult i32 %i.next, 100
  br i1 %ec, label %loop, label %exit
exit:
  ret void
}

; If y >u x and y <=u INT_MIN + 1, x may be INT_MIN. So smax(x, w) <s 0 cannot
; be folded.
define void @neg_ugt_smin_plus_1(i32 %x, i32 %w, ptr %p) {
; CHECK-LABEL: define void @neg_ugt_smin_plus_1(
; CHECK-SAME: i32 [[X:%.*]], i32 [[W:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[Y:%.*]] = load i32, ptr [[P]], align 4, !range [[RNG3:![0-9]+]]
; CHECK-NEXT:    [[C:%.*]] = icmp ugt i32 [[Y]], [[X]]
; CHECK-NEXT:    br i1 [[C]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT:.*]]
; CHECK:       [[LOOP_PREHEADER]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], %[[LATCH:.*]] ], [ 0, %[[LOOP_PREHEADER]] ]
; CHECK-NEXT:    [[M:%.*]] = call i32 @llvm.smax.i32(i32 [[X]], i32 [[W]])
; CHECK-NEXT:    [[Q:%.*]] = icmp slt i32 [[M]], 0
; CHECK-NEXT:    br i1 [[Q]], label %[[EXIT_LOOPEXIT:.*]], label %[[LATCH]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    call void @side()
; CHECK-NEXT:    [[I_NEXT]] = add nuw nsw i32 [[I]], 1
; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i32 [[I_NEXT]], 100
; 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:
  %y = load i32, ptr %p, !range !3
  %c = icmp ugt i32 %y, %x
  br i1 %c, label %loop, label %exit
loop:
  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  %m = call i32 @llvm.smax.i32(i32 %x, i32 %w)
  %q = icmp slt i32 %m, 0
  br i1 %q, label %exit, label %latch
latch:
  call void @side()
  %i.next = add nuw nsw i32 %i, 1
  %ec = icmp ult i32 %i.next, 100
  br i1 %ec, label %loop, label %exit
exit:
  ret void
}

declare void @side()

; [0, INT_MAX)
!0 = !{i32 0, i32 2147483647}
; [0, INT_MAX]
!1 = !{i32 0, i32 -2147483648}
; [0, INT_MIN] as unsigned
!2 = !{i32 0, i32 -2147483647}
; [0, INT_MIN + 1] as unsigned
!3 = !{i32 0, i32 -2147483646}
;.
; CHECK: [[RNG0]] = !{i32 0, i32 -2147483647}
; CHECK: [[RNG1]] = !{i32 0, i32 -2147483648}
; CHECK: [[RNG2]] = !{i32 0, i32 2147483647}
; CHECK: [[RNG3]] = !{i32 0, i32 -2147483646}
;.