[ValueTracking] Add logic for `isKnownNonZero(ctlz/cttz X)`

[goldstein.w.n]

Summary

for cttz if X[0] is non-zero, then the expression is non-zero.
for ctlz if X[SignBit] is non-zero, then the expression in
non-zero.

Alive2 Links:

cttz (false): https://alive2.llvm.org/ce/z/ySQzbg
cttz (true): https://alive2.llvm.org/ce/z/auiTCJ
ctlz (false): https://alive2.llvm.org/ce/z/yk3sTJ
ctlz (true): https://alive2.llvm.org/ce/z/-JuDty

[nikic]

LGTM

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

llvm/lib/Analysis/ValueTracking.cpp

if (auto *II = dyn_cast<IntrinsicInst>(I)) {
         if (isKnownNonZero(II->getArgOperand(0), DemandedElts, Depth, Q))
           return true;
         break;
       case Intrinsic::uadd_sat:
         if (isKnownNonZero(II->getArgOperand(0), DemandedElts, Depth, Q) ||
             isKnownNonZero(II->getArgOperand(1), DemandedElts, Depth, Q))
           return true;
         break;
+      case Intrinsic::cttz:
+        return computeKnownBits(II->getArgOperand(0), DemandedElts, Depth, Q)
+            .Zero[0];
+      case Intrinsic::ctlz:
+        return computeKnownBits(II->getArgOperand(0), DemandedElts, Depth, Q)
+            .isNonNegative();
       case Intrinsic::fshr:
       case Intrinsic::fshl:
         // If Op0 == Op1, this is a rotate. rotate(x, y) != 0 iff x != 0.
         if (II->getArgOperand(0) == II->getArgOperand(1))
           return isKnownNonZero(II->getArgOperand(0), DemandedElts, Depth, Q);
         break;
       case Intrinsic::vscale:
         return true;

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

;
   %x = bitcast float %xa to i32
   %z = or i32 %x, %ind
   %r = icmp eq i32 %z, 0
   ret i1 %r
 }
 
 define i1 @ctlz_true_nonzero(i8 %xx, i8 %ind) {
 ; CHECK-LABEL: @ctlz_true_nonzero(
-; CHECK-NEXT:    [[XS:%.*]] = lshr i8 [[XX:%.*]], 1
-; CHECK-NEXT:    [[X:%.*]] = call i8 @llvm.ctlz.i8(i8 [[XS]], i1 true)
-; 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
 ;
   %xs = lshr i8 %xx, 1
   %x = call i8 @llvm.ctlz.i8(i8 %xs, i1 true)
   %z = or i8 %x, %ind
   %r = icmp eq i8 %z, 0
   ret i1 %r
 }
 
 define i1 @ctlz_false_nonzero(i8 %xx, i8 %ind) {
 ; CHECK-LABEL: @ctlz_false_nonzero(
-; CHECK-NEXT:    [[XA:%.*]] = and i8 [[XX:%.*]], 127
-; CHECK-NEXT:    [[X:%.*]] = call i8 @llvm.ctlz.i8(i8 [[XA]], i1 true)
-; 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
 ;
   %xa = and i8 %xx, 127
   %x = call i8 @llvm.ctlz.i8(i8 %xa, i1 true)
   %z = or i8 %x, %ind
   %r = icmp eq i8 %z, 0
   ret i1 %r
 }
 
;
   %x = call i8 @llvm.ctlz.i8(i8 %xs, i1 true)
   %z = or i8 %x, %ind
   %r = icmp eq i8 %z, 0
   ret i1 %r
 }
 
 define i1 @cttz_true_nonzero(i8 %xx, i8 %ind) {
 ; CHECK-LABEL: @cttz_true_nonzero(
-; CHECK-NEXT:    [[XS:%.*]] = shl i8 [[XX:%.*]], 1
-; CHECK-NEXT:    [[X:%.*]] = call i8 @llvm.cttz.i8(i8 [[XS]], i1 true)
-; 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
 ;
   %xs = shl i8 %xx, 1
   %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 @cttz_false_nonzero(i8 %xx, i8 %ind) {
 ; CHECK-LABEL: @cttz_false_nonzero(
-; CHECK-NEXT:    [[XA:%.*]] = and i8 [[XX:%.*]], -2
-; CHECK-NEXT:    [[X:%.*]] = call i8 @llvm.cttz.i8(i8 [[XA]], i1 true)
-; 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
 ;
   %xa = and i8 %xx, -2
   %x = call i8 @llvm.cttz.i8(i8 %xa, i1 true)
   %z = or i8 %x, %ind
   %r = icmp eq i8 %z, 0
   ret i1 %r
 }