llvm/test/Transforms/InstSimplify/urem-sub-nonzero.ll

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

declare i8 @llvm.umax.i8(i8, i8)

; Structural X u>= Y proofs.

; X != X urem Y is true if X is an add nuw of A and Y.

define i1 @nuw_add_ne(i8 %a, i8 %y) {
; CHECK-LABEL: define i1 @nuw_add_ne(
; CHECK-SAME: i8 [[A:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:    ret i1 true
;
  %x = add nuw i8 %a, %y
  %rem = urem i8 %x, %y
  %cmp = icmp ne i8 %x, %rem
  ret i1 %cmp
}

; X urem Y != X is true with commuted add and compare operands.

define i1 @nuw_add_ne_commuted(i8 %a, i8 %y) {
; CHECK-LABEL: define i1 @nuw_add_ne_commuted(
; CHECK-SAME: i8 [[A:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:    ret i1 true
;
  %x = add nuw i8 %y, %a
  %rem = urem i8 %x, %y
  %cmp = icmp ne i8 %rem, %x
  ret i1 %cmp
}

; umax(X - (X urem Y), 1) is X - (X urem Y) if X is an add nuw
; of A and Y.

define i8 @nuw_add_umax(i8 %a, i8 %y) {
; CHECK-LABEL: define i8 @nuw_add_umax(
; CHECK-SAME: i8 [[A:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:    [[X:%.*]] = add nuw i8 [[A]], [[Y]]
; CHECK-NEXT:    [[REM:%.*]] = urem i8 [[X]], [[Y]]
; CHECK-NEXT:    [[SUB:%.*]] = sub nuw i8 [[X]], [[REM]]
; CHECK-NEXT:    ret i8 [[SUB]]
;
  %x = add nuw i8 %a, %y
  %rem = urem i8 %x, %y
  %sub = sub nuw i8 %x, %rem
  %max = call i8 @llvm.umax.i8(i8 %sub, i8 1)
  ret i8 %max
}

; X != X urem Y is true element-wise if X is an add nuw of A and Y.

define <2 x i1> @nuw_add_ne_vector(<2 x i4> %a, <2 x i4> %y) {
; CHECK-LABEL: define <2 x i1> @nuw_add_ne_vector(
; CHECK-SAME: <2 x i4> [[A:%.*]], <2 x i4> [[Y:%.*]]) {
; CHECK-NEXT:    ret <2 x i1> splat (i1 true)
;
  %x = add nuw <2 x i4> %a, %y
  %rem = urem <2 x i4> %x, %y
  %cmp = icmp ne <2 x i4> %x, %rem
  ret <2 x i1> %cmp
}

; Dominating X u>= Y proofs.

; X != X urem Y is true if X u>= Y.

define i1 @dom_ne(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @dom_ne(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[COND:%.*]] = icmp uge i8 [[X]], [[Y]]
; CHECK-NEXT:    br i1 [[COND]], label %[[BODY:.*]], label %[[EXIT:.*]]
; CHECK:       [[BODY]]:
; CHECK-NEXT:    ret i1 true
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret i1 false
;
entry:
  %cond = icmp uge i8 %x, %y
  br i1 %cond, label %body, label %exit

body:
  %rem = urem i8 %x, %y
  %cmp = icmp ne i8 %x, %rem
  ret i1 %cmp

exit:
  ret i1 false
}

; X urem Y == X is false if X u>= Y.

define i1 @dom_eq_commuted(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @dom_eq_commuted(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[COND:%.*]] = icmp uge i8 [[X]], [[Y]]
; CHECK-NEXT:    br i1 [[COND]], label %[[BODY:.*]], label %[[EXIT:.*]]
; CHECK:       [[BODY]]:
; CHECK-NEXT:    ret i1 false
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret i1 true
;
entry:
  %cond = icmp uge i8 %x, %y
  br i1 %cond, label %body, label %exit

body:
  %rem = urem i8 %x, %y
  %cmp = icmp eq i8 %rem, %x
  ret i1 %cmp

exit:
  ret i1 true
}

; Equivalent comparisons against one.

; (X - (X urem Y)) u>= 1 is true if X u>= Y.

define i1 @dom_uge_one(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @dom_uge_one(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[COND:%.*]] = icmp uge i8 [[X]], [[Y]]
; CHECK-NEXT:    br i1 [[COND]], label %[[BODY:.*]], label %[[EXIT:.*]]
; CHECK:       [[BODY]]:
; CHECK-NEXT:    ret i1 true
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret i1 false
;
entry:
  %cond = icmp uge i8 %x, %y
  br i1 %cond, label %body, label %exit

body:
  %rem = urem i8 %x, %y
  %sub = sub i8 %x, %rem
  %cmp = icmp uge i8 %sub, 1
  ret i1 %cmp

exit:
  ret i1 false
}

; (X - (X urem Y)) u< 1 is false if X u>= Y.

define i1 @dom_ult_one(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @dom_ult_one(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[COND:%.*]] = icmp uge i8 [[X]], [[Y]]
; CHECK-NEXT:    br i1 [[COND]], label %[[BODY:.*]], label %[[EXIT:.*]]
; CHECK:       [[BODY]]:
; CHECK-NEXT:    ret i1 false
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret i1 true
;
entry:
  %cond = icmp uge i8 %x, %y
  br i1 %cond, label %body, label %exit

body:
  %rem = urem i8 %x, %y
  %sub = sub i8 %x, %rem
  %cmp = icmp ult i8 %sub, 1
  ret i1 %cmp

exit:
  ret i1 true
}

; Equivalent unsigned comparisons against zero.

; (X - (X urem Y)) u> 0 is true on the false edge of X u< Y.

define i1 @dom_ugt_zero_false_edge(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @dom_ugt_zero_false_edge(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[COND:%.*]] = icmp ult i8 [[X]], [[Y]]
; CHECK-NEXT:    br i1 [[COND]], label %[[EXIT:.*]], label %[[BODY:.*]]
; CHECK:       [[BODY]]:
; CHECK-NEXT:    ret i1 true
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret i1 false
;
entry:
  %cond = icmp ult i8 %x, %y
  br i1 %cond, label %exit, label %body

body:
  %rem = urem i8 %x, %y
  %sub = sub i8 %x, %rem
  %cmp = icmp ugt i8 %sub, 0
  ret i1 %cmp

exit:
  ret i1 false
}

; 0 u>= (X - (X urem Y)) is false if X u>= Y.

define i1 @dom_ule_zero_commuted(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @dom_ule_zero_commuted(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[COND:%.*]] = icmp uge i8 [[X]], [[Y]]
; CHECK-NEXT:    br i1 [[COND]], label %[[BODY:.*]], label %[[EXIT:.*]]
; CHECK:       [[BODY]]:
; CHECK-NEXT:    ret i1 false
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret i1 true
;
entry:
  %cond = icmp uge i8 %x, %y
  br i1 %cond, label %body, label %exit

body:
  %rem = urem i8 %x, %y
  %sub = sub i8 %x, %rem
  %cmp = icmp uge i8 0, %sub
  ret i1 %cmp

exit:
  ret i1 true
}

; Equality comparisons against zero.

; (X - (X urem Y)) != 0 is true if X u>= Y.

define i1 @dom_ne_zero(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @dom_ne_zero(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[COND:%.*]] = icmp uge i8 [[X]], [[Y]]
; CHECK-NEXT:    br i1 [[COND]], label %[[BODY:.*]], label %[[EXIT:.*]]
; CHECK:       [[BODY]]:
; CHECK-NEXT:    ret i1 true
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret i1 false
;
entry:
  %cond = icmp uge i8 %x, %y
  br i1 %cond, label %body, label %exit

body:
  %rem = urem i8 %x, %y
  %sub = sub i8 %x, %rem
  %cmp = icmp ne i8 %sub, 0
  ret i1 %cmp

exit:
  ret i1 false
}

; 0 == (X - (X urem Y)) is false if X u>= Y.

define i1 @dom_eq_zero_commuted(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @dom_eq_zero_commuted(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[COND:%.*]] = icmp uge i8 [[X]], [[Y]]
; CHECK-NEXT:    br i1 [[COND]], label %[[BODY:.*]], label %[[EXIT:.*]]
; CHECK:       [[BODY]]:
; CHECK-NEXT:    ret i1 false
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret i1 true
;
entry:
  %cond = icmp uge i8 %x, %y
  br i1 %cond, label %body, label %exit

body:
  %rem = urem i8 %x, %y
  %sub = sub i8 %x, %rem
  %cmp = icmp eq i8 0, %sub
  ret i1 %cmp

exit:
  ret i1 true
}

; Intrinsic user.

; umax(X - (X urem Y), 1) is X - (X urem Y) if X u>= Y.

define i8 @dom_umax_false_edge(i8 %x, i8 %y) {
; CHECK-LABEL: define i8 @dom_umax_false_edge(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[COND:%.*]] = icmp ult i8 [[X]], [[Y]]
; CHECK-NEXT:    br i1 [[COND]], label %[[EXIT:.*]], label %[[BODY:.*]]
; CHECK:       [[BODY]]:
; CHECK-NEXT:    [[REM:%.*]] = urem i8 [[X]], [[Y]]
; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[X]], [[REM]]
; CHECK-NEXT:    ret i8 [[SUB]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret i8 0
;
entry:
  %cond = icmp ult i8 %x, %y
  br i1 %cond, label %exit, label %body

body:
  %rem = urem i8 %x, %y
  %sub = sub i8 %x, %rem
  %max = call i8 @llvm.umax.i8(i8 %sub, i8 1)
  ret i8 %max

exit:
  ret i8 0
}

; Negative tests.

; Do not simplify if the add may wrap.

define i8 @add_may_wrap(i8 %a, i8 %y) {
; CHECK-LABEL: define i8 @add_may_wrap(
; CHECK-SAME: i8 [[A:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:    [[X:%.*]] = add i8 [[A]], [[Y]]
; CHECK-NEXT:    [[REM:%.*]] = urem i8 [[X]], [[Y]]
; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[X]], [[REM]]
; CHECK-NEXT:    [[MAX:%.*]] = call i8 @llvm.umax.i8(i8 [[SUB]], i8 1)
; CHECK-NEXT:    ret i8 [[MAX]]
;
  %x = add i8 %a, %y
  %rem = urem i8 %x, %y
  %sub = sub i8 %x, %rem
  %max = call i8 @llvm.umax.i8(i8 %sub, i8 1)
  ret i8 %max
}

; Do not simplify (X - (X urem Y)) != 0 without proof of X u>= Y.

define i1 @no_known_relation(i8 %x, i8 %y) {
; CHECK-LABEL: define i1 @no_known_relation(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]]) {
; CHECK-NEXT:    [[REM:%.*]] = urem i8 [[X]], [[Y]]
; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[X]], [[REM]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[SUB]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %rem = urem i8 %x, %y
  %sub = sub i8 %x, %rem
  %cmp = icmp ne i8 %sub, 0
  ret i1 %cmp
}

; Do not simplify using X u>= Z when the remainder divisor is Y.

define i1 @dom_wrong_divisor_ne_zero(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: define i1 @dom_wrong_divisor_ne_zero(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[Z:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[COND:%.*]] = icmp uge i8 [[X]], [[Z]]
; CHECK-NEXT:    br i1 [[COND]], label %[[BODY:.*]], label %[[EXIT:.*]]
; CHECK:       [[BODY]]:
; CHECK-NEXT:    [[REM:%.*]] = urem i8 [[X]], [[Y]]
; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[X]], [[REM]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[SUB]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret i1 false
;
entry:
  %cond = icmp uge i8 %x, %z
  br i1 %cond, label %body, label %exit

body:
  %rem = urem i8 %x, %y
  %sub = sub i8 %x, %rem
  %cmp = icmp ne i8 %sub, 0
  ret i1 %cmp

exit:
  ret i1 false
}

; Do not simplify umax using X u>= Y when the remainder divisor is Z.

define i8 @dom_wrong_divisor(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: define i8 @dom_wrong_divisor(
; CHECK-SAME: i8 [[X:%.*]], i8 [[Y:%.*]], i8 [[Z:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[COND:%.*]] = icmp uge i8 [[X]], [[Y]]
; CHECK-NEXT:    br i1 [[COND]], label %[[BODY:.*]], label %[[EXIT:.*]]
; CHECK:       [[BODY]]:
; CHECK-NEXT:    [[REM:%.*]] = urem i8 [[X]], [[Z]]
; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[X]], [[REM]]
; CHECK-NEXT:    [[MAX:%.*]] = call i8 @llvm.umax.i8(i8 [[SUB]], i8 1)
; CHECK-NEXT:    ret i8 [[MAX]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret i8 0
;
entry:
  %cond = icmp uge i8 %x, %y
  br i1 %cond, label %body, label %exit

body:
  %rem = urem i8 %x, %z
  %sub = sub i8 %x, %rem
  %max = call i8 @llvm.umax.i8(i8 %sub, i8 1)
  ret i8 %max

exit:
  ret i8 0
}