Teach isKnownNonEqual how to recurse through invertable multiplies

[reames]

Summary

Build on the work started in 8f07629, and add the multiply case. In the process, more clearly describe the requirement for the operation we're looking through.

Reviewers, please confirm my reasoning is correct. I always get confused by modulo arithmetic.

[nikic]

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

161

I don't think this is right if %C can be zero. In that case %A.op == %B.op regardless of what the relation between %A and %B is.

[nikic]

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

161

It is fine with the added non-zero requirement though: https://alive2.llvm.org/ce/z/_SBhuP

Looks like it also holds if both muls as nsw rather than nuw: https://alive2.llvm.org/ce/z/Z6D5qK

[reames]

Add non-zero restriction. For now, restrict to constant case. I could have used isKnownNonZero, but that would require recursing through both operands which I'd rather not do from a compile time perspective.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2540

For completely sake, I think this should handle the nsw case as well.

2543

With canonicalized operands, the constant can only be on the RHS.

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

169

Add nuw to these to make it eligible in the first place?

173

We should also have a negative test with nuw but non-constant (and thus not known non zero) common operand.

[reames]

Address review comments.

p.s. Thanks for the detailed comments, definitely improving the code.

[nikic]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

2520

nit: invertable -> invertible

[uabelho]

Hi,

The following starts failing with this commit:

opt -S -o /dev/null bbi-51071.ll -early-cse

With bbi-51071.ll being

@f.a = external global i16, align 1

define void @f() {
entry:
  store i16 ptrtoint (i16* @f.a to i16), i16* undef, align 1
  %0 = load i16, i16* undef, align 1
  %mul = mul nsw i16 %0, -1
  %1 = load i16, i16* @f.a, align 1
  %mul1 = mul nsw i16 %1, 11
  %cmp = icmp eq i16 %mul, %mul1
  %conv = zext i1 %cmp to i16
  ret void

I get

opt: ../include/llvm/Support/Casting.h:269: typename cast_retty<X, Y *>::ret_type llvm::cast(Y *) [X = llvm::BinaryOperator, Y = const llvm::Operator]: Assertion `isa<X>(Val) && "cast<Ty>() argument of incompatible type!"' failed.

[nikic]

@uabelho Thanks for the reproducer! This issue should be fixed by https://github.com/llvm/llvm-project/commit/dcd21572f971ae5b5f1bf1f1abefafa0085404e1.

[uabelho]

In D92726#2472881, @nikic wrote:

@uabelho Thanks for the reproducer! This issue should be fixed by https://github.com/llvm/llvm-project/commit/dcd21572f971ae5b5f1bf1f1abefafa0085404e1.

Thanks!

llvm/lib/Analysis/ValueTracking.cpp

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, Depth + 1, Q);
 }
 
+
 /// Return true if it is known that V1 != V2.
 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 (Depth >= MaxAnalysisRecursionDepth)
     return false;
 
-  // See if we can recurse through (exactly one of) our operands.
+  // See if we can recurse through (exactly one of) our operands.  This
+  // requires our operation be 1-to-1 and map every input value to exactly
+  // one output value.  Such an operation is invertible.
   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::Mul:
+      // invertible if A * B == (A * B) mod 2^N where A, and B are integers
+      // and N is the bitwdith.  The nsw case is non-obvious, but proven by
+      // alive2: https://alive2.llvm.org/ce/z/Z6D5qK
+      if ((!cast<BinaryOperator>(O1)->hasNoUnsignedWrap() ||
+           !cast<BinaryOperator>(O2)->hasNoUnsignedWrap()) &&
+          (!cast<BinaryOperator>(O1)->hasNoSignedWrap() ||
+           !cast<BinaryOperator>(O2)->hasNoSignedWrap()))
+        break;
+
+      // Assume operand order has been canonicalized
+      if (O1->getOperand(1) == O2->getOperand(1) &&
+          isa<ConstantInt>(O1->getOperand(1)) &&
+          !cast<ConstantInt>(O1->getOperand(1))->isZero())
+        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;
     };
   }

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

;
   %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
 }
 
+; op could wrap mapping two values to the same output value.
+define i1 @mul1(i8 %B) {
+; CHECK-LABEL: @mul1(
+; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
+; CHECK-NEXT:    [[A_OP:%.*]] = mul i8 [[A]], 27
+; CHECK-NEXT:    [[B_OP:%.*]] = mul i8 [[B]], 27
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP]], [[B_OP]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %A = add i8 %B, 1
+  %A.op = mul i8 %A, 27
+  %B.op = mul i8 %B, 27
+
+  %cmp = icmp eq i8 %A.op, %B.op
+  ret i1 %cmp
+}
+
+define i1 @mul2(i8 %B) {
+; CHECK-LABEL: @mul2(
+; CHECK-NEXT:    ret i1 false
+;
+  %A = add i8 %B, 1
+  %A.op = mul nuw i8 %A, 27
+  %B.op = mul nuw i8 %B, 27
+
+  %cmp = icmp eq i8 %A.op, %B.op
+  ret i1 %cmp
+}
+
+define i1 @mul3(i8 %B) {
+; CHECK-LABEL: @mul3(
+; CHECK-NEXT:    ret i1 false
+;
+  %A = add i8 %B, 1
+  %A.op = mul nsw i8 %A, 27
+  %B.op = mul nsw i8 %B, 27
+
+  %cmp = icmp eq i8 %A.op, %B.op
+  ret i1 %cmp
+}
+
+; Multiply by zero collapses all values to one
+define i1 @mul4(i8 %B) {
+; CHECK-LABEL: @mul4(
+; CHECK-NEXT:    ret i1 true
+;
+  %A = add i8 %B, 1
+  %A.op = mul nuw i8 %A, 0
+  %B.op = mul nuw i8 %B, 0
+
+  %cmp = icmp eq i8 %A.op, %B.op
+  ret i1 %cmp
+}
+
+; C might be zero, we can't tell
+define i1 @mul5(i8 %B, i8 %C) {
+; CHECK-LABEL: @mul5(
+; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
+; CHECK-NEXT:    [[A_OP:%.*]] = mul nuw nsw i8 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[B_OP:%.*]] = mul nuw nsw i8 [[B]], [[C]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP]], [[B_OP]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %A = add i8 %B, 1
+  %A.op = mul nsw nuw i8 %A, %C
+  %B.op = mul nsw nuw i8 %B, %C
+
+  %cmp = icmp eq i8 %A.op, %B.op
+  ret i1 %cmp
+}
+
+
 !0 = !{ i8 1, i8 5 }