llvm/test/Transforms/IndVarSimplify/loop-invariant-predicate-samesign.ll

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

; IndVars replaces a compare of an IV with a loop-invariant value by its value
; on loop entry, if:
;  - Monotonicity: once the compare is true, it stays true.
;  - Backedge guard: the backedge is taken only if the compare is true.
; If the compare may be poison, both must hold for the same picks of its
; poison values.

declare void @use(i1)

; %cmp must not be replaced with %start samesign >u %inv.
; E.g. for %start = 127, %inv = -1, %cmp is poison at %iv = 127, and false at
; %iv = -128.
; Monotonicity: needs the poison at %iv = 127 to be picked false, because
; %cmp is false on the next iteration.
; Backedge guard: needs it to be picked true, because the backedge is taken at
; %iv = 127.
define void @samesign_ugt_signed_latch(i8 %start, i8 %inv) {
; CHECK-LABEL: define void @samesign_ugt_signed_latch(
; CHECK-SAME: i8 [[START:%.*]], i8 [[INV:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START]], %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LOOP]] ]
; CHECK-NEXT:    [[CMP:%.*]] = icmp samesign ugt i8 [[IV]], [[INV]]
; CHECK-NEXT:    call void @use(i1 [[CMP]])
; CHECK-NEXT:    [[IV_NEXT]] = add nuw i8 [[IV]], 1
; CHECK-NEXT:    [[LATCH_COND:%.*]] = icmp sgt i8 [[IV]], [[INV]]
; CHECK-NEXT:    br i1 [[LATCH_COND]], label %[[LOOP]], label %[[EXIT:.*]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  br label %loop
loop:
  %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
  %cmp = icmp samesign ugt i8 %iv, %inv
  call void @use(i1 %cmp)
  %iv.next = add nuw i8 %iv, 1
  %latch.cond = icmp sgt i8 %iv, %inv
  br i1 %latch.cond, label %loop, label %exit
exit:
  ret void
}

; %cmp can be replaced with %start samesign >u %inv.
; Backedge guard: the latch is %iv >u %inv, so when the backedge is taken, %cmp
; is true or poison.
; Monotonicity: once %iv >u %inv is true, it stays true, because %iv only grows
; (nuw). So once the backedge is taken, %cmp stays true or poison.
; %start samesign >u %inv is poison only if %start <s 0 <=s %inv. Then %iv
; stays negative (nuw), so %cmp is poison on every iteration too.
define void @samesign_ugt_unsigned_latch(i8 %start, i8 %inv) {
; CHECK-LABEL: define void @samesign_ugt_unsigned_latch(
; CHECK-SAME: i8 [[START:%.*]], i8 [[INV:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[CMP:%.*]] = icmp samesign ugt i8 [[START]], [[INV]]
; CHECK-NEXT:    call void @use(i1 [[CMP]])
; CHECK-NEXT:    [[LATCH_COND:%.*]] = icmp ugt i8 [[START]], [[INV]]
; CHECK-NEXT:    br i1 [[LATCH_COND]], label %[[LOOP]], label %[[EXIT:.*]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  br label %loop
loop:
  %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
  %cmp = icmp samesign ugt i8 %iv, %inv
  call void @use(i1 %cmp)
  %iv.next = add nuw i8 %iv, 1
  %latch.cond = icmp ugt i8 %iv, %inv
  br i1 %latch.cond, label %loop, label %exit
exit:
  ret void
}

; TODO: %cmp can be replaced with %start samesign >u %inv.
; Backedge guard: %inv >=s 0, so when the latch %iv >s %inv is true, both
; operands are non-negative, and %cmp is %iv >u %inv, which is true.
; Monotonicity: once %iv >u %inv is true, it stays true, because %iv only grows
; (nuw). So once the backedge is taken, %cmp stays true or poison.
; %start samesign >u %inv is poison only if %start <s 0. Then the loop exits
; after the first iteration.
define void @samesign_ugt_signed_latch_nonneg_inv(i8 %start, i8 %inv) {
; CHECK-LABEL: define void @samesign_ugt_signed_latch_nonneg_inv(
; CHECK-SAME: i8 [[START:%.*]], i8 [[INV:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[INV_NONNEG:%.*]] = icmp sge i8 [[INV]], 0
; CHECK-NEXT:    br i1 [[INV_NONNEG]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT:.*]]
; CHECK:       [[LOOP_PREHEADER]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[IV_NEXT:%.*]], %[[LOOP]] ], [ [[START]], %[[LOOP_PREHEADER]] ]
; CHECK-NEXT:    [[CMP:%.*]] = icmp samesign ugt i8 [[IV]], [[INV]]
; CHECK-NEXT:    call void @use(i1 [[CMP]])
; CHECK-NEXT:    [[IV_NEXT]] = add nuw i8 [[IV]], 1
; CHECK-NEXT:    [[LATCH_COND:%.*]] = icmp sgt i8 [[IV]], [[INV]]
; CHECK-NEXT:    br i1 [[LATCH_COND]], label %[[LOOP]], label %[[EXIT_LOOPEXIT:.*]]
; CHECK:       [[EXIT_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  %inv.nonneg = icmp sge i8 %inv, 0
  br i1 %inv.nonneg, label %loop, label %exit
loop:
  %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
  %cmp = icmp samesign ugt i8 %iv, %inv
  call void @use(i1 %cmp)
  %iv.next = add nuw i8 %iv, 1
  %latch.cond = icmp sgt i8 %iv, %inv
  br i1 %latch.cond, label %loop, label %exit
exit:
  ret void
}

; TODO: %cmp can be replaced with %start samesign >u %inv.
; %start >=s 0 and %iv steps with nuw nsw, so %iv stays non-negative.
; %inv <s 0, so the operand signs always differ, and %cmp is poison on
; every iteration, so it is safe to use the value on the first iteration.
define void @samesign_ugt_signed_latch_iv_keeps_sign(i8 %start, i8 %inv) {
; CHECK-LABEL: define void @samesign_ugt_signed_latch_iv_keeps_sign(
; CHECK-SAME: i8 [[START:%.*]], i8 [[INV:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[INV_NEG:%.*]] = icmp slt i8 [[INV]], 0
; CHECK-NEXT:    [[START_NONNEG:%.*]] = icmp sge i8 [[START]], 0
; CHECK-NEXT:    [[GUARD:%.*]] = and i1 [[INV_NEG]], [[START_NONNEG]]
; CHECK-NEXT:    br i1 [[GUARD]], label %[[LOOP_PREHEADER:.*]], label %[[EXIT:.*]]
; CHECK:       [[LOOP_PREHEADER]]:
; CHECK-NEXT:    br label %[[LOOP:.*]]
; CHECK:       [[LOOP]]:
; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[IV_NEXT:%.*]], %[[LOOP]] ], [ [[START]], %[[LOOP_PREHEADER]] ]
; CHECK-NEXT:    [[CMP:%.*]] = icmp samesign ugt i8 [[IV]], [[INV]]
; CHECK-NEXT:    call void @use(i1 [[CMP]])
; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i8 [[IV]], 1
; CHECK-NEXT:    [[LATCH_COND:%.*]] = icmp sgt i8 [[START]], [[INV]]
; CHECK-NEXT:    br i1 [[LATCH_COND]], label %[[LOOP]], label %[[EXIT_LOOPEXIT:.*]]
; CHECK:       [[EXIT_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    ret void
;
entry:
  %inv.neg = icmp slt i8 %inv, 0
  %start.nonneg = icmp sge i8 %start, 0
  %guard = and i1 %inv.neg, %start.nonneg
  br i1 %guard, label %loop, label %exit
loop:
  %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
  %cmp = icmp samesign ugt i8 %iv, %inv
  call void @use(i1 %cmp)
  %iv.next = add nuw nsw i8 %iv, 1
  %latch.cond = icmp sgt i8 %iv, %inv
  br i1 %latch.cond, label %loop, label %exit
exit:
  ret void
}