[ValueTracking] Do more thorough non-zero check in `isKnownToBePowerOfTwo` when `OrZero` is no set.

[goldstein.w.n]

Summary

We can cover more cases by directly checking if the result is
known-nonzero for common patterns when they are missing OrZero.

This patch add isKnownNonZero checks for shl, lshr, and, and mul.

[goldstein.w.n]

Rebase

[nikic]

Please land the remainder of the patch stack first.

llvm/lib/Analysis/ValueTracking.cpp

2046

Would it make sense to preserve the flag checks? I think isKnownNonZero will be able to prove the same result, but in a more roundabout way (it can't just check the flags, it will also have to prove non-zero operands etc).

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

2046

I think for shl you are right, IPSCCP will propagate nuw in all the cases I think isKnownNonZero helps here.
For lshr however the equivilent logic is missing. I take it you would prefer fixing this with a patch to IPSCCP?

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

2046

Think actually best in InstCombine, IPSCCP uses ranges which isn't so useful for checking if a remainder is zero. Think computeKnownBits makes more sense for this.

[goldstein.w.n]

Rebase to end of series + remove isKnownNonZero change from shifts

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

2046

Remove from shifts and improved flag adding logic in InstCombe: D157532

[goldstein.w.n]

moving to gh.

llvm/lib/Analysis/ValueTracking.cpp

if (Depth++ == MaxAnalysisRecursionDepth)
     return false;
 
   switch (I->getOpcode()) {
   case Instruction::ZExt:
     return isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q);
   case Instruction::Trunc:
     return OrZero && isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q);
   case Instruction::Shl:
     if (OrZero || Q.IIQ.hasNoUnsignedWrap(I) || Q.IIQ.hasNoSignedWrap(I))
       return isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q);
     return false;
   case Instruction::LShr:
     if (OrZero || Q.IIQ.isExact(cast<BinaryOperator>(I)))
       return isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q);
     return false;
   case Instruction::UDiv:
     if (Q.IIQ.isExact(cast<BinaryOperator>(I)))
       return isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q);
     return false;
   case Instruction::Mul:
-    return OrZero &&
-           isKnownToBeAPowerOfTwo(I->getOperand(1), OrZero, Depth, Q) &&
-           isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q);
+    return isKnownToBeAPowerOfTwo(I->getOperand(1), OrZero, Depth, Q) &&
+           isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q) &&
+           (OrZero || isKnownNonZero(I, Depth, Q));
   case Instruction::And:
-    if (OrZero) {
-      // A power of two and'd with anything is a power of two or zero.
-      if (isKnownToBeAPowerOfTwo(I->getOperand(1), /*OrZero*/ true, Depth, Q) ||
-          isKnownToBeAPowerOfTwo(I->getOperand(0), /*OrZero*/ true, Depth, Q))
-        return true;
-      // X & (-X) is always a power of two or zero.
-      if (match(I->getOperand(0), m_Neg(m_Specific(I->getOperand(1)))) ||
-          match(I->getOperand(1), m_Neg(m_Specific(I->getOperand(0)))))
-        return true;
-    }
+    if (OrZero &&
+        (isKnownToBeAPowerOfTwo(I->getOperand(1), /*OrZero*/ true, Depth, Q) ||
+         isKnownToBeAPowerOfTwo(I->getOperand(0), /*OrZero*/ true, Depth, Q)))
+      return OrZero || isKnownNonZero(I->getOperand(0), Depth, Q);
     return false;
   case Instruction::Add: {
     // Adding a power-of-two or zero to the same power-of-two or zero yields
     // either the original power-of-two, a larger power-of-two or zero.
     const OverflowingBinaryOperator *VOBO = cast<OverflowingBinaryOperator>(V);
     if (OrZero || Q.IIQ.hasNoUnsignedWrap(VOBO) ||
         Q.IIQ.hasNoSignedWrap(VOBO)) {
       if (match(I->getOperand(0),

llvm/test/Analysis/ValueTracking/known-power-of-two.ll

;
   ret i1 %r
 }
 
 define i1 @and_is_pow2(i16 %x, i16 %y) {
 ; CHECK-LABEL: define i1 @and_is_pow2
 ; CHECK-SAME: (i16 [[X:%.*]], i16 [[Y:%.*]]) {
 ; CHECK-NEXT:    [[XNZ:%.*]] = or i16 [[X]], 4
 ; CHECK-NEXT:    [[X_NEG:%.*]] = sub nsw i16 0, [[XNZ]]
-; CHECK-NEXT:    [[XX:%.*]] = and i16 [[XNZ]], [[X_NEG]]
-; CHECK-NEXT:    [[AND:%.*]] = and i16 [[XX]], [[Y]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i16 [[AND]], [[XX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[X_NEG]], [[Y]]
+; CHECK-NEXT:    [[AND:%.*]] = and i16 [[TMP1]], [[XNZ]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i16 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %xnz = or i16 %x, 4
   %x_neg = sub i16 0, %xnz
   %xx = and i16 %xnz, %x_neg
 
   %and = and i16 %y, %xx
   %r = icmp eq i16 %and, %xx

llvm/test/Transforms/InstSimplify/ctpop-pow2.ll

;
   %v0 = sub i16 0, %x
   %v1 = and i16 %x, %v0
   %cnt = call i16 @llvm.ctpop.i16(i16 %v1)
   ret i16 %cnt
 }
 
 define i8 @ctpop_x_nz_and_negx(i8 %x) {
 ; CHECK-LABEL: @ctpop_x_nz_and_negx(
-; CHECK-NEXT:    [[X1:%.*]] = or i8 [[X:%.*]], 1
-; CHECK-NEXT:    [[V0:%.*]] = sub i8 0, [[X1]]
-; CHECK-NEXT:    [[V1:%.*]] = and i8 [[X1]], [[V0]]
-; CHECK-NEXT:    ret i8 [[V1]]
+; CHECK-NEXT:    ret i8 1
 ;
   %x1 = or i8 %x, 1
   %v0 = sub i8 0, %x1
   %v1 = and i8 %x1, %v0
   %cnt = call i8 @llvm.ctpop.i8(i8 %v1)
   ret i8 %cnt
 }