[ValueTracking] Add additional cases for `isKnownNonZero(mul X, Y)`

[goldstein.w.n]

Summary

If either X or Y is odd and the other is non-zero, the result is
non-zero.

Alive2 Link:

https://alive2.llvm.org/ce/z/9V7-es

[StephenFan]

LGTM

[goldstein.w.n]

Rebase

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2875–2892

Similar to the add case, we should compute mul known bits here based on the already computed XKnown/YKnown, rather than computing them again via the fallback.

I think just using KnownBits::mul should be enough, as the NSW case handled by computeKnownBitsMul is already handled better above.

[goldstein.w.n]

Make it so we don't need to fallback to generic case

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

2875–2892

Similar to the add case, we should compute mul known bits here based on the already computed XKnown/YKnown, rather than computing them again via the fallback.

I think just using KnownBits::mul should be enough, as the NSW case handled by computeKnownBitsMul is already handled better above.

Added the actual logic b.c there is a trick for knowing the sign of the result that doesn't appear to be handled by KnownBits::mul. Also seems more future-proof incase someone has a new bright idea and improves it further.

But we don't recompute knownbits now :)

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2875–2892

But isn't all the sign bit logic behind if (NSW), which we already handle separately?

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2875–2892

I mainly find the computeKnownBitsMulDoMul() function pretty ugly and would prefer to avoid it :) KnownBits::mul should handle anything that is not based on nowrap flags, and we handle nowrap flags ourselves.

[goldstein.w.n]

use KnownBits::mul instead of refactoring and using computeKnownBitsMul

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

2875–2892

You're right no difference. Thanks for all the reviews on this very long series :)

thinkwe are in the home stretch now

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2897

You can drop the SelfMultiply handling as well. It only determines that the low bit is zero, which is not useful if we want a non-zero result.

[goldstein.w.n]

Don't both with selfmultiply

[nikic]

LGTM

[holland11]

I'm probably missing something obvious here, but what does it matter that one of the operands is odd? If we are multiplying two numbers where one is odd or even (as long as its non-zero) and the other is non-zero, the result will be non-zero, no? I can't figure out what's special about odd in this context.

[goldstein.w.n]

In D149418#4335780, @holland11 wrote:

I'm probably missing something obvious here, but what does it matter that one of the operands is odd? If we are multiplying two numbers where one is odd or even (as long as its non-zero) and the other is non-zero, the result will be non-zero, no? I can't figure out what's special about odd in this context.

Its because multiple by odd preserves the low-bit from the input i.e
X * Y if Y is not, the low bit in X will be set in the result: https://alive2.llvm.org/ce/z/RD-MCy
So if X != 0 then the low-bit in X is non-zero then the result X * Y is non-zero.

[holland11]

Ah I see now, thank you! So in general, the only way a multiply with two non-zero source operands can result in a 0 is from overflow, but if at least one of those operands is odd, any overflow will never result in overflowing to 0.

Edit: Nvm, the below is actually incorrect. I was only considering a single overflow (so 0b10000 in a 4 bit result), but it's possible to get multiple overflow (0b110000 in a 4 bit result) which could still be 0 without being a power of two.
I suppose another way to think about it is that the only way to overflow to 0 in binary is with a result that is a power of two (ex. 256 in 8bit). Power of two's are never divisible by an odd number (besides 1, but that would require 256 * 1 which wouldn't make sense for 8b arithmetic). So if our multiplication involves at least one odd number, the result will never be a power of two (unless the other operand is 1 which means we won't overflow anyways) which means it will never overflow to 0.

[holland11]

Made a mistake in my assumptions in the previous comment, but I do see how this patch makes sense now.

[goldstein.w.n]

In D149418#4336383, @holland11 wrote:

Ah I see now, thank you! So in general, the only way a multiply with two non-zero source operands can result in a 0 is from overflow, but if at least one of those operands is odd, any overflow will never result in overflowing to 0.

Edit: Nvm, the below is actually incorrect. I was only considering a single overflow (so 0b10000 in a 4 bit result), but it's possible to get multiple overflow (0b110000 in a 4 bit result) which could still be 0 without being a power of two.
I suppose another way to think about it is that the only way to overflow to 0 in binary is with a result that is a power of two (ex. 256 in 8bit). Power of two's are never divisible by an odd number (besides 1, but that would require 256 * 1 which wouldn't make sense for 8b arithmetic). So if our multiplication involves at least one odd number, the result will never be a power of two (unless the other operand is 1 which means we won't overflow anyways) which means it will never overflow to 0.

This made me think of something, we can actually strengthen this case. Odd is just a special case really the result is X * Y != 0 is the same is Lowbit(X) * Lowbit(Y) != 0. Patch incoming!

llvm/lib/Analysis/ValueTracking.cpp

case Instruction::Add: {
 
     return isNonZeroAdd(DemandedElts, Depth, Q, BitWidth, I->getOperand(0),
                         I->getOperand(1), Q.IIQ.hasNoSignedWrap(BO));
   }
   case Instruction::Mul: {
     // If X and Y are non-zero then so is X * Y as long as the multiplication
     // does not overflow.
     const OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V);
-    if ((Q.IIQ.hasNoSignedWrap(BO) || Q.IIQ.hasNoUnsignedWrap(BO)) &&
-        isKnownNonZero(I->getOperand(0), DemandedElts, Depth, Q) &&
-        isKnownNonZero(I->getOperand(1), DemandedElts, Depth, Q))
-      return true;
-    break;
+    if (Q.IIQ.hasNoSignedWrap(BO) || Q.IIQ.hasNoUnsignedWrap(BO))
+      return isKnownNonZero(I->getOperand(0), DemandedElts, Depth, Q) &&
+             isKnownNonZero(I->getOperand(1), DemandedElts, Depth, Q);
+
+    // If either X or Y is odd, then if the other is non-zero the result can't
+    // be zero.
+    KnownBits XKnown =
+        computeKnownBits(I->getOperand(0), DemandedElts, Depth, Q);
+    if (XKnown.One[0])
+      return isKnownNonZero(I->getOperand(1), DemandedElts, Depth, Q);
+
+    KnownBits YKnown =
+        computeKnownBits(I->getOperand(1), DemandedElts, Depth, Q);
+    if (YKnown.One[0])
+      return XKnown.isNonZero() ||
+             isKnownNonZero(I->getOperand(0), DemandedElts, Depth, Q);
+
+    return KnownBits::mul(XKnown, YKnown).isNonZero();
   }
   case Instruction::Select:
     // (C ? X : Y) != 0 if X != 0 and Y != 0.
     if (isKnownNonZero(I->getOperand(1), DemandedElts, Depth, Q) &&
         isKnownNonZero(I->getOperand(2), DemandedElts, Depth, Q))
       return true;
     break;
   case Instruction::PHI: {
     auto *PN = cast<PHINode>(I);
     if (Q.IIQ.UseInstrInfo && isNonZeroRecurrence(PN))
       return true;
 
     // Check if all incoming values are non-zero using recursion.

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

;
   %x = call i8 @llvm.cttz.i8(i8 %xs, i1 true)
   %z = or i8 %x, %ind
   %r = icmp eq i8 %z, 0
   ret i1 %r
 }
 
 define i1 @mul_nonzero_odd(i8 %xx, i8 %y, i8 %ind) {
 ; CHECK-LABEL: @mul_nonzero_odd(
-; CHECK-NEXT:    [[XO:%.*]] = or i8 [[XX:%.*]], 1
 ; CHECK-NEXT:    [[Y_NZ:%.*]] = icmp ne i8 [[Y:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[Y_NZ]])
-; CHECK-NEXT:    [[X:%.*]] = mul i8 [[XO]], [[Y]]
-; CHECK-NEXT:    [[Z:%.*]] = or i8 [[X]], [[IND:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[Z]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %xo = or i8 %xx, 1
   %y_nz = icmp ne i8 %y, 0
   call void @llvm.assume(i1 %y_nz)
   %x = mul i8 %xo, %y
   %z = or i8 %x, %ind
   %r = icmp eq i8 %z, 0
   ret i1 %r