[ValueTracking] Use maximum shift count in `shl` when determining if `shl` can be zero.

[goldstein.w.n]

Summary

Previously only return shl non-zero if the shift value was 1. We
can expand this if we have some bounds on the shift count.

For example:

%cnt = and %c, 16 ; Max cnt == 16
%val = or %v, 4 ; val[2] is known one
%shl = shl %val, %cnt ; (val.known.one << cnt.maxval) != 0

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2688

Isn't this going to assert if the max value is wider than the bit width?

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

2688

Should probably just use KnownBits::shl() here.

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

2688

Should probably just use KnownBits::shl() here.

Will do, does using KnownBits::shl fix the issue of failing the assert if max value is too wide, or do I need to add a check for that? Adding a few tests for that case and not seeing any assertions.

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

2688

Should probably just use KnownBits::shl() here.

Using KnownBits::shl(Known, KnownCnt).isNonZero() causes regressions. How about just adding a checking KnownCnt.getMaxValue().ult(Known.getBitWidth())?

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

2688

Should probably just use KnownBits::shl() here.

2688

Should probably just use KnownBits::shl() here.

Using KnownBits::shl(Known, KnownCnt).isNonZero() causes regressions. How about just adding a checking KnownCnt.getMaxValue().ult(Known.getBitWidth())?

Yeah KnownBits::shl isn't ideal here b.c its computing something more precision than we need. We only need to know if the maximum shift will clear the result. We don't need the precision of where the bits end up. For example with the 1 << (cnt & 16) case, KnowBits::shl cant set any bits for the output. But the current logic figures out that can't be zero.

[goldstein.w.n]

Check that shift count isn't invalid

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

2688

Isn't this going to assert if the max value is wider than the bit width?

Added a check.

[nikic]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

if (Q.IIQ.hasNoUnsignedWrap(BO))
       return isKnownNonZero(I->getOperand(0), Depth, Q);
 
     // shl X, Y != 0 if X is odd.  Note that the value of the shift is undefined
     // if the lowest bit is shifted off the end.
     KnownBits Known(BitWidth);
     computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth, Q);
     if (Known.One[0])
       return true;
+
+    if (!Known.isUnknown()) {
+      KnownBits KnownCnt =
+          computeKnownBits(I->getOperand(1), DemandedElts, Depth, Q);
+
+      if (KnownCnt.getMaxValue().ult(Known.getBitWidth()) &&
+          !Known.One.shl(KnownCnt.getMaxValue()).isZero())
+        return true;
+    }
+
     break;
   }
   case Instruction::LShr:
   case Instruction::AShr: {
     // shr exact can only shift out zero bits.
     const PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V);
     if (BO->isExact())
       return isKnownNonZero(I->getOperand(0), Depth, Q);

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

;
   %cmp0 = icmp ugt <2 x i8> %z, %w
   %cmp1 = icmp eq <2 x i8> %w, <i8 0, i8 0>
   %r = or <2 x i1> %cmp0, %cmp1
   ret <2 x i1> %r
 }
 
 define <2 x i1> @shl_nz_bounded_cnt_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @shl_nz_bounded_cnt_vec(
-; CHECK-NEXT:    [[CNT:%.*]] = and <2 x i32> [[X:%.*]], <i32 16, i32 24>
-; CHECK-NEXT:    [[VAL:%.*]] = or <2 x i32> [[Y:%.*]], <i32 131088, i32 16>
-; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> [[VAL]], [[CNT]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i32> [[SHL]], zeroinitializer
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %cnt = and <2 x i32> %x, <i32 16, i32 24>
   %val = or <2 x i32> %y, <i32 131088, i32 16>
   %shl = shl <2 x i32> %val, %cnt
   %r = icmp eq <2 x i32> %shl, zeroinitializer
   ret <2 x i1> %r
 }
 
 define i1 @shl_nz_bounded_cnt(i32 %cnt, i32 %y) {
 ; CHECK-LABEL: @shl_nz_bounded_cnt(
 ; CHECK-NEXT:    [[CNT_ULT4:%.*]] = icmp ult i32 [[CNT:%.*]], 4
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CNT_ULT4]])
-; CHECK-NEXT:    [[VAL:%.*]] = or i32 [[Y:%.*]], 131072
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[VAL]], [[CNT]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[SHL]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %cnt_ult4 = icmp ult i32 %cnt, 4
   call void @llvm.assume(i1 %cnt_ult4)
   %val = or i32 %y, 131072
   %shl = shl i32 %val, %cnt
   %r = icmp eq i32 %shl, 0
   ret i1 %r
 }