Index: llvm/lib/Analysis/ValueTracking.cpp
===================================================================
--- llvm/lib/Analysis/ValueTracking.cpp
+++ llvm/lib/Analysis/ValueTracking.cpp
@@ -2502,6 +2502,7 @@
   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) {
@@ -2514,7 +2515,9 @@
   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 invertable.
   auto *O1 = dyn_cast<Operator>(V1);
   auto *O2 = dyn_cast<Operator>(V2);
   if (O1 && O2 && O1->getOpcode() == O2->getOpcode()) {
@@ -2522,6 +2525,21 @@
     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:
+      // invertable if A * B == (A * B) mod 2^N where A, and B are integers
+      // and N is the bitwdith.
+      if (!cast<BinaryOperator>(O1)->hasNoUnsignedWrap() ||
+          !cast<BinaryOperator>(O2)->hasNoUnsignedWrap())
+        break;
+
       // Assume operand order has been canonicalized
       if (O1->getOperand(0) == O2->getOperand(0))
         return isKnownNonEqual(O1->getOperand(1), O2->getOperand(1),
Index: llvm/test/Analysis/ValueTracking/known-non-equal.ll
===================================================================
--- llvm/test/Analysis/ValueTracking/known-non-equal.ll
+++ llvm/test/Analysis/ValueTracking/known-non-equal.ll
@@ -130,4 +130,35 @@
   ret i1 %cmp
 }
 
+; %C is unknown and op could wrap mapping two values to the same
+; output value.
+define i1 @mul1(i8 %B, i8 %C) {
+; CHECK-LABEL: @mul1(
+; CHECK-NEXT:    [[A:%.*]] = add i8 [[B:%.*]], 1
+; CHECK-NEXT:    [[A_OP:%.*]] = mul i8 [[C:%.*]], [[A]]
+; CHECK-NEXT:    [[B_OP:%.*]] = mul i8 [[C]], [[B]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[A_OP]], [[B_OP]]
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %A = add i8 %B, 1
+  %A.op = mul i8 %C, %A
+  %B.op = mul i8 %C, %B
+
+  %cmp = icmp eq i8 %A.op, %B.op
+  ret i1 %cmp
+}
+
+define i1 @mul2(i8 %B, i8 %C) {
+; CHECK-LABEL: @mul2(
+; CHECK-NEXT:    ret i1 false
+;
+  %A = add i8 %B, 1
+  %A.op = mul nuw i8 %C, %A
+  %B.op = mul nuw i8 %C, %B
+
+  %cmp = icmp eq i8 %A.op, %B.op
+  ret i1 %cmp
+}
+
+
 !0 = !{ i8 1, i8 5 }