[ValueTracking] Add logic for `(sub x, y) != 0` if we know `KnownX != KnownY`

[goldstein.w.n]

Summary

Alive2 Link:

https://alive2.llvm.org/ce/z/TAFcjF

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2725

[goldstein.w.n]

Return false if knownx is unknown

[goldstein.w.n]

fixed

[nikic]

LGTM

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

llvm/lib/Analysis/ValueTracking.cpp

#endif
   case Instruction::PtrToInt:
     // Similar to int2ptr above, we can look through ptr2int here if the cast
     // is a no-op or an extend and not a truncate.
     if (!isa<ScalableVectorType>(I->getType()) &&
         Q.DL.getTypeSizeInBits(I->getOperand(0)->getType()).getFixedValue() <=
             Q.DL.getTypeSizeInBits(I->getType()).getFixedValue())
       return isKnownNonZero(I->getOperand(0), Depth, Q);
     break;
-  case Instruction::Sub:
+  case Instruction::Sub: {
     if (auto *C = dyn_cast<Constant>(I->getOperand(0)))
       if (C->isNullValue() &&
           isKnownNonZero(I->getOperand(1), DemandedElts, Depth, Q))
         return true;
+
+    KnownBits XKnown =
+        computeKnownBits(I->getOperand(0), DemandedElts, Depth, Q);
+    if (!XKnown.isUnknown()) {
+      KnownBits YKnown =
+          computeKnownBits(I->getOperand(1), DemandedElts, Depth, Q);
+      // If X != Y then X - Y is non zero.
+      std::optional<bool> ne = KnownBits::ne(XKnown, YKnown);
+      // If we are unable to compute if X != Y, we won't be able to do anything
+      // computing the knownbits of the sub expression so just return here.
+      return ne && *ne;
+    }
     break;
+  }
   case Instruction::Or:
     // X | Y != 0 if X != 0 or Y != 0.
     return isKnownNonZero(I->getOperand(0), DemandedElts, Depth, Q) ||
            isKnownNonZero(I->getOperand(1), DemandedElts, Depth, Q);
   case Instruction::SExt:
   case Instruction::ZExt:
     // ext X != 0 if X != 0.
     return isKnownNonZero(I->getOperand(0), Depth, Q);

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

;
   call void @llvm.assume(i1 %val_nz)
   %shl = shl i32 %val, %cnt
   %r = icmp eq i32 %shl, 0
   ret i1 %r
 }
 
 define i1 @sub_nonzero_ops_ne(i8 %xx, i8 %yy, i8 %z) {
 ; CHECK-LABEL: @sub_nonzero_ops_ne(
-; CHECK-NEXT:    [[X:%.*]] = and i8 [[XX:%.*]], -65
-; CHECK-NEXT:    [[Y:%.*]] = or i8 [[YY:%.*]], 64
-; CHECK-NEXT:    [[S:%.*]] = sub i8 [[X]], [[Y]]
-; CHECK-NEXT:    [[EXP:%.*]] = or i8 [[Z:%.*]], [[S]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[EXP]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %x = and i8 %xx, 191
   %y = or i8 %yy, 64
   %s = sub i8 %x, %y
   %exp = or i8 %z, %s
   %r = icmp eq i8 %exp, 0
   ret i1 %r
 }