[ValueTracking] Add support in `isKnownNonZero` for dominating condition from `X > C1 && X < C2`

[goldstein.w.n]

Summary

X > C1 && X < C2 is canonicalized to X + C3 < C4, so look through
X + C to try and find compares.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2833

What is the motivating test case for this? And what information are we losing? This looks very dubious.

[goldstein.w.n]

Rebase

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2833

What is the motivating test case for this? And what information are we losing? This looks very dubious.

check_ucmp_range_from0_assumed and check_ucmp_range_from0_and_abs both rely on it. Diff w.o is roughly:

 define i1 @check_ucmp_range_from0_assumed(i8 %x, i8 %y) {
 ; CHECK-LABEL: @check_ucmp_range_from0_assumed(
-; CHECK-NEXT:    [[UB:%.*]] = add i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[NE:%.*]] = icmp ult i8 [[UB]], 14
+; CHECK-NEXT:    [[NE:%.*]] = icmp ult i8 [[X:%.*]], 15
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NE]])
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    ret i1 [[CMP0]]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
+; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
+; CHECK-NEXT:    ret i1 [[R]]

and

 define i1 @check_ucmp_range_from0_and_abs(i8 %x, i8 %y) {
 ; CHECK-LABEL: @check_ucmp_range_from0_and_abs(
 ; CHECK-NEXT:    [[X1:%.*]] = and i8 [[X:%.*]], 123
-; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i8 [[X1]], -1
-; CHECK-NEXT:    [[NE:%.*]] = icmp ult i8 [[TMP1]], 14
+; CHECK-NEXT:    [[NE:%.*]] = icmp ult i8 [[X1]], 15
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NE]])
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    ret i1 [[CMP0]]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
+; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
+; CHECK-NEXT:    ret i1 [[R]]
 ;

The expression X - 1 u< C cannot be true for X == 0, the expression X u< C can be true for X == 0 so when doing the dom analysis if we make the transform we end up unable to prove about X != 0. Its a but circular, i.e we use isKnownNonZero(X) which is true, make the change, then at a later use of X are unable to reprove isKnownNonZero(X)

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2833

Why isn't this covered by ephemeral value handling? That is supposed to prevent an assume from simplifying its own condition.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2833

Why isn't this covered by ephemeral value handling? That is supposed to prevent an assume from simplifying its own condition.

I don't know, what file should I look at?

My preference would be to keep as is and add TODO to see if this can be handled by ephemeral value handling. But can also do the inverse (remove this and add TODO to fix by handling in ephemeral value handling).

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2833

See isEphemeralValueOf() used by isValidAssumeForContext() in ValueTracking.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2833

See isEphemeralValueOf() used by isValidAssumeForContext() in ValueTracking.

So I'm not sure what you're getting at with re:"Why isn't this covered by ephemeral value handling?", the issue isn't that the assume doesn't check the expression, the issue is that after we visit the X0 + 1 u< C0 the new expression X1 u<= C1 no longer exclude zero.

Do isEphemeralValueOf` exclude the instruction from going the instcombine? If not I don't see how it could help avoid this case.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2833

See isEphemeralValueOf() used by isValidAssumeForContext() in ValueTracking.

So I'm not sure what you're getting at with re:"Why isn't this covered by ephemeral value handling?", the issue isn't that the assume doesn't check the expression, the issue is that after we visit the X0 + 1 u< C0 the new expression X1 u<= C1 no longer exclude zero.

Do isEphemeralValueOf` exclude the instruction from going the instcombine? If not I don't see how it could help avoid this case.

2833

See isEphemeralValueOf() used by isValidAssumeForContext() in ValueTracking.

So I'm not sure what you're getting at with re:"Why isn't this covered by ephemeral value handling?", the issue isn't that the assume doesn't check the expression, the issue is that after we visit the X0 + 1 u< C0 the new expression X1 u<= C1 no longer exclude zero.

Do isEphemeralValueOf` exclude the instruction from going the instcombine? If not I don't see how it could help avoid this case.

Sorry ignore, accidentally resubmitted.

[goldstein.w.n]

ping @nikic

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

llvm/include/llvm/IR/InstrTypes.h

static_assert(FIRST_FCMP_PREDICATE == 0,
                   "FIRST_FCMP_PREDICATE is required to be 0");
     return P <= LAST_FCMP_PREDICATE;
   }
 
   static bool isIntPredicate(Predicate P) {
     return P >= FIRST_ICMP_PREDICATE && P <= LAST_ICMP_PREDICATE;
   }
 
+  /// Returns if this cmp is only used by a singular assume
+  bool isAssumedTrue(bool OneUse) const;
+
   static StringRef getPredicateName(Predicate P);
 
   bool isFPPredicate() const { return isFPPredicate(getPredicate()); }
   bool isIntPredicate() const { return isIntPredicate(getPredicate()); }
 
   /// For example, EQ -> NE, UGT -> ULE, SLT -> SGE,
   ///              OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
   /// @returns the inverse predicate for the instruction's current predicate.

llvm/lib/Analysis/ValueTracking.cpp

static bool checkDominatingConditionForNonNull(const Value *V, const User *U,
   const Instruction *CtxI = Q.CxtI;
   const DominatorTree *DT = Q.DT;
 
   // Consider only compare instructions uniquely controlling a branch
   Value *RHS;
   CmpInst::Predicate Pred;
   bool NonNullIfTrue;
   const User *CmpUse = nullptr;
-  if (match(U, m_c_ICmp(Pred, m_Specific(V), m_Value(RHS)))) {
+  const APInt *AddC;
+  if (match(U, m_Add(m_Specific(V), m_APInt(AddC))) && !AddC->isZero()) {
+    unsigned NumUsesExplored = 0;
+    for (const auto *U2 : U->users()) {
+
+      // This is inner loop of a loop through V->Users() so be more
+      // conservative here.
+      if (NumUsesExplored++ >= (DomConditionsMaxUses + 3) / 4)
+        break;
+
+      // Only handles (A + C1) u< C2, which is the canonical form of A > C3
+      // && A < C4.
+      if (match(U2, m_ICmp(Pred, m_Specific(U), m_Value(RHS)))) {
+        auto *RHSC = dyn_cast<ConstantInt>(RHS);
+        // TODO: Since we already here, we could check all (or at least more)
+        // conditions, at the moment we only handle `ICMP_ULT` to get the `A u<
+        // C1 && A u> C2` canonicalization case.
+        if (RHSC == nullptr || Pred != ICmpInst::ICMP_ULT)
+          continue;
+
+        NonNullIfTrue = RHSC->getValue().ult(*AddC);
+        if (NonNullIfTrue &&
+            dyn_cast<ICmpInst>(U2)->isAssumedTrue(/*OneUse*/ false))
+          return true;
+
+        CmpUse = U2;
+        break;
+      }
+    }
+  } else if (match(U, m_c_ICmp(Pred, m_Specific(V), m_Value(RHS)))) {
     CmpUse = U;
     if (cmpExcludesZero(Pred, RHS))
       NonNullIfTrue = true;
     else if (cmpExcludesZero(CmpInst::getInversePredicate(Pred), RHS))
       NonNullIfTrue = false;
     else
       return false;
-  } else
+  }
+
+  if (CmpUse == nullptr)
     return false;
 
   SmallVector<const User *, 4> WorkList;
   SmallPtrSet<const User *, 4> Visited;
   for (const auto *CmpU : CmpUse->users()) {
 
     assert(WorkList.empty() && "Should be!");
     if (Visited.insert(CmpU).second)
if (V == getLoadStorePointerOperand(U)) {
                                 V->getType()->getPointerAddressSpace()) &&
           DT->dominates(I, CtxI))
         return true;
     }
 
     bool ImpliesNonZero = false;
     if (auto *OpU = dyn_cast<Operator>(U)) {
       switch (OpU->getOpcode()) {
+      case Instruction::Add:
       case Instruction::ICmp:
         if (checkDominatingConditionForNonNull(V, U, Q))
           return true;
         break;
       case Instruction::And:
         ImpliesNonZero = true;
         break;
       case Instruction::Sub:

llvm/lib/IR/Instructions.cpp

 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/ProfDataUtils.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"

 bool CmpInst::isEquality(Predicate P) {
   if (ICmpInst::isIntPredicate(P))
     return ICmpInst::isEquality(P);
   if (FCmpInst::isFPPredicate(P))
     return FCmpInst::isEquality(P);
   llvm_unreachable("Unsupported predicate kind");
 }
 
+bool CmpInst::isAssumedTrue(bool OneUse) const {
+  if (OneUse && !hasOneUse())
+    return false;
+  for (const auto *U : users())
+    if (dyn_cast<AssumeInst>(U))
+      return true;
+  return false;
+}
+
 CmpInst::Predicate CmpInst::getInversePredicate(Predicate pred) {
   switch (pred) {
     default: llvm_unreachable("Unknown cmp predicate!");
     case ICMP_EQ: return ICMP_NE;
     case ICMP_NE: return ICMP_EQ;
     case ICMP_UGT: return ICMP_ULE;
     case ICMP_ULT: return ICMP_UGE;
     case ICMP_UGE: return ICMP_ULT;

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (Pred == CmpInst::ICMP_SGT && C == *C2 - 1)
     return new ICmpInst(ICmpInst::ICMP_ULT, X, ConstantInt::get(Ty, SMax - C));
 
   // (X + C2) <s C --> X >u (C ^ SMAX) (if C == C2)
   if (Pred == CmpInst::ICMP_SLT && C == *C2)
     return new ICmpInst(ICmpInst::ICMP_UGT, X, ConstantInt::get(Ty, C ^ SMax));
 
   // (X + -1) <u C --> X <=u C (if X is never null)
   if (Pred == CmpInst::ICMP_ULT && C2->isAllOnes()) {
+    // Don't make this transform if the only use of this Cmp is assume as we
+    // both lose information and de-canonicalize the (A < C1 && A > C2) case
+    if (!Cmp.isAssumedTrue(/*OneUse*/ true)) {
       const SimplifyQuery Q = SQ.getWithInstruction(&Cmp);
       if (llvm::isKnownNonZero(X, DL, 0, Q.AC, Q.CxtI, Q.DT))
         return new ICmpInst(ICmpInst::ICMP_ULE, X, ConstantInt::get(Ty, C));
     }
+  }
 
   if (!Add->hasOneUse())
     return nullptr;
 
   // X+C <u C2 -> (X & -C2) == C
   //   iff C & (C2-1) == 0
   //       C2 is a power of 2
   if (Pred == ICmpInst::ICMP_ULT && C.isPowerOf2() && (*C2 & (C - 1)) == 0)

llvm/test/Analysis/ValueTracking/known-non-zero-range.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=instcombine < %s -S | FileCheck %s
 
 declare void @llvm.assume(i1)
 declare i8 @llvm.abs.i8(i8, i1)
 declare void @use1(i1)
 
 define i1 @check_ucmp_range(i8 %x, i8 %y) {
 ; CHECK-LABEL: @check_ucmp_range(
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], -11
 ; CHECK-NEXT:    [[NE:%.*]] = icmp ult i8 [[TMP1]], 19
 ; CHECK-NEXT:    br i1 [[NE]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ; CHECK:       false:
 ; CHECK-NEXT:    [[RT:%.*]] = icmp eq i8 [[X]], 0
 ; CHECK-NEXT:    call void @use1(i1 [[RT]])
 ; CHECK-NEXT:    ret i1 [[RT]]
 ;
   %ub = icmp ult i8 %x, 30
   %lb = icmp ugt i8 %x, 10
   %ne = and i1 %ub, %lb

 
 define i1 @check_ucmp_range_from0(i8 %x, i8 %y) {
 ; CHECK-LABEL: @check_ucmp_range_from0(
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], -1
 ; CHECK-NEXT:    [[NE:%.*]] = icmp ult i8 [[TMP1]], 14
 ; CHECK-NEXT:    br i1 [[NE]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ; CHECK:       false:
 ; CHECK-NEXT:    [[RT:%.*]] = icmp eq i8 [[X]], 0
 ; CHECK-NEXT:    call void @use1(i1 [[RT]])
 ; CHECK-NEXT:    ret i1 [[RT]]
 ;
   %ub = icmp ult i8 %x, 15
   %lb = icmp ugt i8 %x, 0
   %ne = and i1 %ub, %lb

 }
 
 define i1 @check_ucmp_range_from0_assumed(i8 %x, i8 %y) {
 ; CHECK-LABEL: @check_ucmp_range_from0_assumed(
 ; CHECK-NEXT:    [[UB:%.*]] = add i8 [[X:%.*]], -1
 ; CHECK-NEXT:    [[NE:%.*]] = icmp ult i8 [[UB]], 14
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NE]])
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ;
   %ub = add i8 %x, -1
   %ne = icmp ult i8 %ub, 14
   call void @llvm.assume(i1 %ne)
   %cmp0 = icmp ugt i8 %x, %y
   %cmp1 = icmp eq i8 %y, 0
   %r = or i1 %cmp0, %cmp1
   ret i1 %r
 }
 
 
 define i1 @check_ucmp_range_and(i8 %x, i8 %y) {
 ; CHECK-LABEL: @check_ucmp_range_and(
 ; CHECK-NEXT:    [[X1:%.*]] = and i8 [[X:%.*]], 120
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i8 [[X1]], -20
 ; CHECK-NEXT:    [[NE:%.*]] = icmp ult i8 [[TMP1]], 16
 ; CHECK-NEXT:    br i1 [[NE]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ; CHECK:       false:
 ; CHECK-NEXT:    [[RT:%.*]] = icmp eq i8 [[X]], 0
 ; CHECK-NEXT:    call void @use1(i1 [[RT]])
 ; CHECK-NEXT:    ret i1 [[RT]]
 ;
   %x1 = and i8 %x, 123
   %ub = icmp ult i8 %x1, 36
   %lb = icmp ugt i8 %x1, 19

 
 define i1 @check_ucmp_range_from0_and_abs(i8 %x, i8 %y) {
 ; CHECK-LABEL: @check_ucmp_range_from0_and_abs(
 ; CHECK-NEXT:    [[X1:%.*]] = and i8 [[X:%.*]], 123
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i8 [[X1]], -1
 ; CHECK-NEXT:    [[NE:%.*]] = icmp ult i8 [[TMP1]], 14
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NE]])
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ;
   %x1 = and i8 %x, 123
   %x2 = call i8 @llvm.abs.i8(i8 %x1, i1 true)
   %ub = icmp ult i8 %x2, 15
   %lb = icmp ugt i8 %x2, 0
   %ne = and i1 %ub, %lb
   call void @llvm.assume(i1 %ne)
   %cmp0 = icmp ugt i8 %x, %y

 
 define i1 @check_ucmp_range_inv(i8 %x, i8 %y) {
 ; CHECK-LABEL: @check_ucmp_range_inv(
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], 14
 ; CHECK-NEXT:    [[NE:%.*]] = icmp ult i8 [[TMP1]], 29
 ; CHECK-NEXT:    br i1 [[NE]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       false:
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ; CHECK:       true:
 ; CHECK-NEXT:    [[RT:%.*]] = icmp eq i8 [[X]], 0
 ; CHECK-NEXT:    call void @use1(i1 [[RT]])
 ; CHECK-NEXT:    ret i1 [[RT]]
 ;
   %ub = icmp slt i8 %x, 15
   %lb = icmp sgt i8 %x, -15
   %ne = and i1 %ub, %lb

llvm/test/Analysis/ValueTracking/known-non-zero-through-dom-use.ll

 ;; test explicitly that `isKnownNonZero` works.
 
 define i1 @check_neg(i8 %x, i8 %y) {
 ; CHECK-LABEL: @check_neg(
 ; CHECK-NEXT:    [[NOTSUB:%.*]] = add i8 [[X:%.*]], -1
 ; CHECK-NEXT:    [[NE:%.*]] = icmp ult i8 [[NOTSUB]], -5
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NE]])
 ; CHECK-NEXT:    [[CMP0:%.*]] = icmp ugt i8 [[X]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 [[Y]], 0
-; CHECK-NEXT:    [[R:%.*]] = or i1 [[CMP0]], [[CMP1]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 [[CMP0]]
 ;
   %z = sub i8 0, %x
   %ne = icmp ugt i8 %z, 4
   call void @llvm.assume(i1 %ne)
   %cmp0 = icmp ugt i8 %x, %y
   %cmp1 = icmp eq i8 %y, 0
   %r = or i1 %cmp0, %cmp1
   ret i1 %r