[ValueTracking] Add a new predicate: isKnownNonEqual()

[jmolloy]

Summary

isKnownNonEqual(A, B) returns true if it can be determined that A != B.

At the moment it only knows one fact, that a non-wrapping add of nonzero to a value cannot be that value:

A + B != A [where B != 0, addition is nsw or nuw]

[sanjoy]

I don't think you need to check for no-wrap -- a non-zero B should be sufficient to prove A + B != A.

[hfinkel]

I like the idea of this function, but I'm somewhat nervous of adding such a generic facility with such a limited implementation. It would make me feel much better if it also had the following check: call computeKnownBits on V1 and V2, and return true if any of the bits known to be 1 in one value are known to be zero in the other. That would naturally leverage much more of the existing infrastructure.

Also, I assume you're planning on soon using this somewhere?

[hfinkel]

In D12801#251005, @hfinkel wrote:

...

Also, I assume you're planning on soon using this somewhere?

You can ignore this; I see you're using it in D12801.

[hfinkel]

In D12801#251007, @hfinkel wrote:

In D12801#251005, @hfinkel wrote:

...

Also, I assume you're planning on soon using this somewhere?

You can ignore this; I see you're using it in D12801.

Err... D12802.

[jmolloy]

Hi Hal, Sanjoy,

Thanks for the review. I've addressed both your comments, and:

• Hooked this up to InstSimplify - it turned out Hal's idea about computeKnownBits wasn't known to it, so it learned something.
• Switched to using a lit test, now instsimplify uses this function.

[jmolloy]

Ping!

[jmolloy]

Ping!

[sanjoy]

Some minor comments inline.

lib/Analysis/ValueTracking.cpp

1938

Isn't this checking V1 == V2 + X? They're both equivalent though, so the answer is still okay, just mildly confusing. :)

1941

Why not use something from PatternMatch.h here, like m_Add?

1965

I'd use auto * here.

Also can this be relaxed to allow everything computeKnownBits can handle (i.e. allow pointers and vectors too)?

[jmolloy]

Hi Sanjoy,

Thanks for the comments. Switching to PatternMatch was a good idea - the code is substantially more readable!

All comments acted upon.

Cheers,

James

[jmolloy]

Hi Sanjoy,

Do you have any comments on this?

Cheers,

James

[sanjoy]

Sorry for the delay, lgtm.

include/llvm/Analysis/ValueTracking.h

bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth = 0,
                       const DominatorTree *DT = nullptr);
 
   /// Returns true if the give value is known to be non-negative.
   bool isKnownNonNegative(Value *V, const DataLayout &DL, unsigned Depth = 0,
                           AssumptionCache *AC = nullptr,
                           const Instruction *CxtI = nullptr,
                           const DominatorTree *DT = nullptr);
 
+  /// isKnownNonEqual - Return true if the given value is known to be non-equal
+  /// when defined. Does not support vectors.
+  bool isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL,
+                      AssumptionCache *AC = nullptr,
+                      const Instruction *CxtI = nullptr,
+                      const DominatorTree *DT = nullptr);
+
   /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
   /// this predicate to simplify operations downstream.  Mask is known to be
   /// zero for bits that V cannot have.
   ///
   /// This function is defined on values with integer type, values with pointer
   /// type, and vectors of integers.  In the case
   /// where V is a vector, the mask, known zero, and known one values are the
   /// same width as the vector element, and the bit is set only if it is true

lib/Analysis/ValueTracking.cpp

 bool llvm::isKnownNonNegative(Value *V, const DataLayout &DL, unsigned Depth,
                               AssumptionCache *AC, const Instruction *CxtI,
                               const DominatorTree *DT) {
   bool NonNegative, Negative;
   ComputeSignBit(V, NonNegative, Negative, DL, Depth, AC, CxtI, DT);
   return NonNegative;
 }
 
+static bool isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL,
+                           const Query &Q);
+
+bool llvm::isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL,
+                          AssumptionCache *AC, const Instruction *CxtI,
+                          const DominatorTree *DT) {
+  return ::isKnownNonEqual(V1, V2, DL, Query(AC,
+                                             safeCxtI(V1, safeCxtI(V2, CxtI)),
+                                             DT));
+}
+
 static bool MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout &DL,
                               unsigned Depth, const Query &Q);
 
 bool llvm::MaskedValueIsZero(Value *V, const APInt &Mask, const DataLayout &DL,
                              unsigned Depth, AssumptionCache *AC,
                              const Instruction *CxtI, const DominatorTree *DT) {
   return ::MaskedValueIsZero(V, Mask, DL, Depth,
                              Query(AC, safeCxtI(V, CxtI), DT));
bool isKnownNonZero(Value *V, const DataLayout &DL, unsigned Depth,
 
   if (!BitWidth) return false;
   APInt KnownZero(BitWidth, 0);
   APInt KnownOne(BitWidth, 0);
   computeKnownBits(V, KnownZero, KnownOne, DL, Depth, Q);
   return KnownOne != 0;
 }
 
+/// Return true if V2 == V1 + X, where X is known non-zero.
+static bool isAddOfNonZero(Value *V1, Value *V2, const DataLayout &DL,
+                           const Query &Q) {
+  BinaryOperator *BO = dyn_cast<BinaryOperator>(V1);
+  if (!BO || BO->getOpcode() != Instruction::Add)
+    return false;
+  Value *Op = nullptr;
+  if (V2 == BO->getOperand(0))
+    Op = BO->getOperand(1);
+  else if (V2 == BO->getOperand(1))
+    Op = BO->getOperand(0);
+  else
+    return false;
+  return isKnownNonZero(Op, DL, 0, Q) &&
+    (BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap());
+}
+
+/// Return true if it is known that V1 != V2.
+static bool isKnownNonEqual(Value *V1, Value *V2, const DataLayout &DL,
+                            const Query &Q) {
+  if (V1->getType()->isVectorTy() || V1 == V2)
+    return false;
+  if (V1->getType() != V2->getType())
+    // We can't look through casts yet.
+    return false;
+  if (isAddOfNonZero(V1, V2, DL, Q) || isAddOfNonZero(V2, V1, DL, Q))
+    return true;
+  return false;
+}
+
 /// Return true if 'V & Mask' is known to be zero.  We use this predicate to
 /// simplify operations downstream. Mask is known to be zero for bits that V
 /// cannot have.
 ///
 /// This function is defined on values with integer type, values with pointer
 /// type, and vectors of integers.  In the case
 /// where V is a vector, the mask, known zero, and known one values are the
 /// same width as the vector element, and the bit is set only if it is true

unittests/Analysis/ValueTrackingTest.cpp

void parseAssembly(const char *Assembly) {
 
     A = nullptr;
     for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
       if (I->hasName()) {
         if (I->getName() == "A")
           A = &*I;
       }
     }
+    B = nullptr;
+    for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
+      if (I->hasName()) {
+        if (I->getName() == "B")
+          B = &*I;
+      }
+    }
     if (A == nullptr)
       report_fatal_error("@test must have an instruction %A");
   }
 
   std::unique_ptr<Module> M;
-  Instruction *A;
+  Instruction *A, *B;
 };
   
 class MatchSelectPatternTest : public testing::Test,
                                public AssemblyParsingTestHelper {
 protected:
   void expectPattern(const SelectPatternResult &P) {
     Value *LHS, *RHS;
     Instruction::CastOps CastOp;
     SelectPatternResult R = matchSelectPattern(A, LHS, RHS, &CastOp);
     EXPECT_EQ(P.Flavor, R.Flavor);
     EXPECT_EQ(P.NaNBehavior, R.NaNBehavior);
     EXPECT_EQ(P.Ordered, R.Ordered);
   }
 };
 
 class KnownValueTest : public testing::Test,
                        public AssemblyParsingTestHelper {
 protected:
   bool knownNonZero() {
     return isKnownNonZero(A, M->getDataLayout());
   }
+
+  bool knownNonEqual() {
+    assert(B && "B must be defined!");
+    return isKnownNonEqual(A, B, M->getDataLayout());
+  }
 };
   
 }
 
 TEST_F(MatchSelectPatternTest, SimpleFMin) {
   parseAssembly(
       "define float @test(float %a) {\n"
       "  %1 = fcmp ult float %a, 5.0\n"
parseAssembly(
     "exit:\n"
     "  unreachable\n"
     "}\n");
   EXPECT_TRUE(knownNonZero());
 }
 
 TEST_F(KnownValueTest, MonotonicWrappingPHI) {
   parseAssembly(
-    "define i8 @test(i8* %pq) {\n"
+    "define i8 @test() {\n"
     "entry:\n"
     "  br label %loop\n"
     "loop:\n"
     "  %A = phi i8 [ 1, %entry ], [ %next, %loop ]\n"
     "  %next = add i8 %A, 1"
     "  br label %loop\n"
     "exit:\n"
     "  unreachable\n"
     "}\n");
   EXPECT_FALSE(knownNonZero());
 }
+
+TEST_F(KnownValueTest, KnownNonEqual1) {
+  parseAssembly(
+    "define i8 @test(i8* %pq, i8 %rB) {\n"
+    "  %B = add i8 %rB, 0\n"
+    "  %q = load i8, i8* %pq, !range !0\n" // %q is known nonzero; no known bits
+    "  %A = add nsw i8 %B, %q\n"
+    "  ret i8 %A\n"
+    "}\n"
+    "!0 = !{ i8 1, i8 5 }\n");
+  EXPECT_TRUE(knownNonEqual());
+};
+
+TEST_F(KnownValueTest, KnownNonEqualWrapping) {
+  parseAssembly(
+    "define i8 @test(i8* %pq, i8 %rB) {\n"
+    "  %B = add i8 %rB, 0\n"
+    "  %q = load i8, i8* %pq, !range !0\n" // %q is known nonzero; no known bits
+    "  %A = add i8 %B, %q\n"
+    "  ret i8 %A\n"
+    "}\n"
+    "!0 = !{ i8 1, i8 5 }\n");
+  EXPECT_FALSE(knownNonEqual());
+};