Add recursive decomposition reasoning to isKnownNonEqual

[reames]

Summary

The basic idea is that by looking through operand instructions which don't change the equality result that we can push the existing known bits comparison down past instructions which would obscure them.

We have analogous handling in InstSimplify for most - though weirdly not all - of these cases starting from an icmp root. It's a bit unfortunate to duplicate logic, but since my actual goal is to extend BasicAA, the icmp logic doesn't help. (And just makes it hard to test here.)

Note that this can't land until after D92694 as the increase in scope makes that bug much more common.

[reames]

Rebase over landed tests

[nikic]

We have analogous handling in InstSimplify for most - though weirdly not all - of these cases starting from an icmp root. It's a bit unfortunate to duplicate logic, but since my actual goal is to extend BasicAA, the icmp logic doesn't help. (And just makes it hard to test here.)

Could you add some tests for the BasicAA use case? If that's the intended target, I'm not sure this is the right approach. Currently the BasicAA logic for the non-equal index case is structural, while it should really be based on the index difference of decomposed GEP expressions. I suspect that handling it that way may also handle your motivating case, as e.g. common add operands would get stripped by that.

llvm/lib/Analysis/ValueTracking.cpp

2536

IntToPtr/PtrToInt can truncate, you need to check bit widths here.

[nikic]

In D92698#2435582, @nikic wrote:

We have analogous handling in InstSimplify for most - though weirdly not all - of these cases starting from an icmp root. It's a bit unfortunate to duplicate logic, but since my actual goal is to extend BasicAA, the icmp logic doesn't help. (And just makes it hard to test here.)

Could you add some tests for the BasicAA use case? If that's the intended target, I'm not sure this is the right approach. Currently the BasicAA logic for the non-equal index case is structural, while it should really be based on the index difference of decomposed GEP expressions. I suspect that handling it that way may also handle your motivating case, as e.g. common add operands would get stripped by that.

After double checking that, it looks like our GEP expression decomposition wouldn't be aggressive enough for that. We only decompose adds if they have one constant operand.

[reames]

In D92698#2435582, @nikic wrote:

Could you add some tests for the BasicAA use case?

Tests for the basic aa extension will be in the patch for basicaa. I could probably contrive a test case through the existing basic aa use of isKnownNonEqual, but it would take some thought. Are you okay with me landing this as is, and then including supplemental tests in the next patch?

[reames]

Remove ptrtoint and inttoptr due to truncation issue pointed out in review. These can be handled in a follow up patch if needed, my motivating case doesn't require them.

[nikic]

In D92698#2435769, @reames wrote:

Tests for the basic aa extension will be in the patch for basicaa. I could probably contrive a test case through the existing basic aa use of isKnownNonEqual, but it would take some thought. Are you okay with me landing this as is, and then including supplemental tests in the next patch?

Sure, that's fine. I thought this patch is all there is to it, wasn't aware it requires further changes in BasicAA.

The logic here is pretty straightforward and I don't expect it to be expensive, so LGTM.

llvm/lib/Analysis/ValueTracking.cpp

2502

Should be just Depth here to stay consistent with the computeKnownBits case, and the previous behavior?

[reames]

llvm/lib/Analysis/ValueTracking.cpp

2502

I don't think so. We are recursing into an operand.

llvm/lib/Analysis/ValueTracking.cpp

 bool llvm::isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth,
                            AssumptionCache *AC, const Instruction *CxtI,
                            const DominatorTree *DT, bool UseInstrInfo) {
   KnownBits Known =
       computeKnownBits(V, DL, Depth, AC, CxtI, DT, nullptr, UseInstrInfo);
   return Known.isNegative();
 }
 
-static bool isKnownNonEqual(const Value *V1, const Value *V2, const Query &Q);
+static bool isKnownNonEqual(const Value *V1, const Value *V2, unsigned Depth,
+                            const Query &Q);
 
 bool llvm::isKnownNonEqual(const Value *V1, const Value *V2,
                            const DataLayout &DL, AssumptionCache *AC,
                            const Instruction *CxtI, const DominatorTree *DT,
                            bool UseInstrInfo) {
-  return ::isKnownNonEqual(V1, V2,
+  return ::isKnownNonEqual(V1, V2, 0,
                            Query(DL, AC, safeCxtI(V1, safeCxtI(V2, CxtI)), DT,
                                  UseInstrInfo, /*ORE=*/nullptr));
 }
 
 static bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth,
                               const Query &Q);
 
 bool llvm::MaskedValueIsZero(const Value *V, const APInt &Mask,
bool isKnownNonZero(const Value* V, unsigned Depth, const Query& Q) {
 
   auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
   APInt DemandedElts =
       FVTy ? APInt::getAllOnesValue(FVTy->getNumElements()) : APInt(1, 1);
   return isKnownNonZero(V, DemandedElts, Depth, Q);
 }
 
 /// Return true if V2 == V1 + X, where X is known non-zero.
-static bool isAddOfNonZero(const Value *V1, const Value *V2, const Query &Q) {
+static bool isAddOfNonZero(const Value *V1, const Value *V2, unsigned Depth,
+                           const Query &Q) {
   const 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, 0, Q);
+  return isKnownNonZero(Op, Depth + 1, Q);
 }
 
 /// Return true if it is known that V1 != V2.
-static bool isKnownNonEqual(const Value *V1, const Value *V2, const Query &Q) {
+static bool isKnownNonEqual(const Value *V1, const Value *V2, unsigned Depth,
+                            const Query &Q) {
   if (V1 == V2)
     return false;
   if (V1->getType() != V2->getType())
     // We can't look through casts yet.
     return false;
-  if (isAddOfNonZero(V1, V2, Q) || isAddOfNonZero(V2, V1, Q))
+
+  if (Depth >= MaxAnalysisRecursionDepth)
+    return false;
+
+  // See if we can recurse through (exactly one of) our operands.
+  auto *O1 = dyn_cast<Operator>(V1);
+  auto *O2 = dyn_cast<Operator>(V2);
+  if (O1 && O2 && O1->getOpcode() == O2->getOpcode()) {
+    switch (O1->getOpcode()) {
+    default: break;
+    case Instruction::Add:
+    case Instruction::Sub:
+      // Assume operand order has been canonicalized
+      if (O1->getOperand(0) == O2->getOperand(0))
+        return isKnownNonEqual(O1->getOperand(1), O2->getOperand(1),
+                               Depth + 1, Q);
+      if (O1->getOperand(1) == O2->getOperand(1))
+        return isKnownNonEqual(O1->getOperand(0), O2->getOperand(0),
+                               Depth + 1, Q);
+      break;
+    case Instruction::SExt:
+    case Instruction::ZExt:
+      if (O1->getOperand(0)->getType() == O2->getOperand(0)->getType())
+        return isKnownNonEqual(O1->getOperand(0), O2->getOperand(0),
+                               Depth + 1, Q);
+      break;
+    };
+  }
+  
+  if (isAddOfNonZero(V1, V2, Depth, Q) || isAddOfNonZero(V2, V1, Depth, Q))
     return true;
 
   if (V1->getType()->isIntOrIntVectorTy()) {
     // Are any known bits in V1 contradictory to known bits in V2? If V1
     // has a known zero where V2 has a known one, they must not be equal.
-    KnownBits Known1 = computeKnownBits(V1, 0, Q);
-    KnownBits Known2 = computeKnownBits(V2, 0, Q);
+    KnownBits Known1 = computeKnownBits(V1, Depth, Q);
+    KnownBits Known2 = computeKnownBits(V2, Depth, Q);
 
     if (Known1.Zero.intersects(Known2.One) ||
         Known2.Zero.intersects(Known1.One))
       return true;
   }
   return false;
 }
 

llvm/test/Analysis/ValueTracking/known-non-equal.ll

;
   %B.op = add i8 %C, %B
 
   %cmp = icmp eq i8 %A.op, %B.op
   ret i1 %cmp
 }
 
 define i1 @sub1(i8 %B, i8 %C) {
 ; CHECK-LABEL: @sub1(
-; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
-; CHECK-NEXT:    [[A_OP:%.*]] = sub i8 [[A]], [[C:%.*]]
-; CHECK-NEXT:    [[B_OP:%.*]] = sub i8 [[B]], [[C]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP]], [[B_OP]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %A = add i8 %B, 1
   %A.op = sub i8 %A, %C
   %B.op = sub i8 %B, %C
 
   %cmp = icmp eq i8 %A.op, %B.op
   ret i1 %cmp
 }
 
 define i1 @sub2(i8 %B, i8 %C) {
 ; CHECK-LABEL: @sub2(
-; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
-; CHECK-NEXT:    [[A_OP:%.*]] = sub i8 [[C:%.*]], [[A]]
-; CHECK-NEXT:    [[B_OP:%.*]] = sub i8 [[C]], [[B]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP]], [[B_OP]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 false
 ;
   %A = add i8 %B, 1
   %A.op = sub i8 %C, %A
   %B.op = sub i8 %C, %B
 
   %cmp = icmp eq i8 %A.op, %B.op
   ret i1 %cmp
 }
 
 !0 = !{ i8 1, i8 5 }