[Analysis] Add support for vscale in computeKnownBitsFromOperator

[david-arm]

Summary

In ValueTracking.cpp we use a function called
computeKnownBitsFromOperator to determine the known bits of a value.
For the vscale intrinsic if the function contains the vscale_range
attribute we can use the maximum and minimum values of vscale to
determine some known zero bits. This should help to improve code quality
by allowing certain optimisations to take place.

Tests added here:

Transforms/InstCombine/icmp-vscale.ll

[dmgreen]

Sounds good. I assume that unsetting low bits from the min value does not help much?

llvm/lib/Analysis/ValueTracking.cpp

1705

Will VScaleTypeSize be BitWidth?

[david-arm]

llvm/lib/Analysis/ValueTracking.cpp

1705

I can't see anything in the code that guarantees the result type of an instruction will have the same width as Known. However, I'm not sure this really matters? If VScaleTypeSize < BitWidth, then I'd expect any bits above BitWidth to also be zero. I looked at Instruction::ZExt as a guide just now and we first truncate Known to be the same as the input, compute the bits on that, then zero-extend back to the original BitWidth.

What specific problem were you worried about here?

[dmgreen]

llvm/lib/Analysis/ValueTracking.cpp

1705

It just seems to be re-calculating a value that we already have.

1831

This appears to be where Known is calculated.

1875

And it's asserted that the size is correct here.

[sdesmalen]

In D109883#3004334, @dmgreen wrote:

Sounds good. I assume that unsetting low bits from the min value does not help much?

I could see this being useful when min == max, which may help fold away code that checks if the vscale value is known even or a power of two.

[david-arm]

In D109883#3005766, @sdesmalen wrote:

In D109883#3004334, @dmgreen wrote:

Sounds good. I assume that unsetting low bits from the min value does not help much?

I could see this being useful when min == max, which may help fold away code that checks if the vscale value is known even or a power of two.

OK fair points @dmgreen and @sdesmalen! I'll look into taking min vscale into account as well. :)

llvm/lib/Analysis/ValueTracking.cpp

1831

Oh right I see. Thanks for explaining - I'll update the patch!

[david-arm]

• Added checks for min vscale values too!

[foad]

llvm/lib/Analysis/ValueTracking.cpp

1696

Maybe use auto?

1708

Can min ever be zero here?

1710

This assumes that vscale is a multiple of min, which is not documented in the langref.

[david-arm]

llvm/lib/Analysis/ValueTracking.cpp

1708

Yeah min can be zero. I think see the problem now because FirstSetBit will be set to UINT_MAX.

1710

Yes you're absolutely right. Of course if min=4, then a value of 5 would still set bit 0 too. I think that means I can only use min to check if it's equal to max.

[foad]

llvm/lib/Analysis/ValueTracking.cpp

1710

Well, you could still deduce *some* extra info from an arbitrary (min,max) pair, but it's probably overkill to try to implement that in this patch. Maybe we should have general helpers for that sort of thing. It could be useful in value tracking passes to be able to convert a known value range into known bits, and vice versa.

[david-arm]

• Fixed bug with using min vscale.

[foad]

The logic looks good to me now. I wonder if we should have an overload of KnownBits::makeConstant that takes a uint64_t?

[dmgreen]

This is a bit of a roundabout way of setting a constant, but that sounds OK to me considering what else this does. (So long as removing the llvm.vscale and replacing it with a constant won't cause problems elsewhere, I assume it shouldn't).

Can you add a quick comment explaining VScaleRange.first == VScaleRange.second vs other part of the code? And it might be worth having a test directly for converting vscale to a constant:

define i64 @const_vscale64_range4_4() vscale_range(4,4) {
entry:
  %vscale = call i64 @llvm.vscale.i64()
  ret i64 %vscale
}

[david-arm]

• Added new trivial function KnownBits::makeConstant(uint64_t) and changed ValueTracking code to use it.
• Added simple test for a vscale constant.
• Added comments to min == max case.

[foad]

llvm/include/llvm/Support/KnownBits.h

291 ↗

(On Diff #373516)

I'm confused. How does this work (since there is no implicit conversion from uint64_t to APInt) and what does it do (i.e. what BitWidth does it use)?

[david-arm]

llvm/include/llvm/Support/KnownBits.h

291 ↗

(On Diff #373516)

Hi @foad, oh I see. I should probably write

return makeConstant(APInt(C));

instead. I imagine the compiler has just assumed I'm calling the version that takes an APInt!

[david-arm]

llvm/include/llvm/Support/KnownBits.h

291 ↗

(On Diff #373516)

Hi @foad, I just wonder if it's really worth adding this overloaded version as you were suggesting in a comment last week? Having looked into this again I realise I probably do need to pass in the BitWidth as well and I'm not sure how commonly this function would be called? I'd also have to deal with a possible mis-match in bitwidths, i.e. if we request a bit width of 32 but the constant has more than 32 bits?

[foad]

llvm/include/llvm/Support/KnownBits.h

291 ↗

(On Diff #373516)

Sure, it was just a half-baked idea, I hadn't really thought through the details. It definitely wouldn't need to be part of this patch anway.

[foad]

LGTM (though I don't really know anything about vscale!).

[dmgreen]

Thanks for adding the comments. LGTM

llvm/lib/Analysis/ValueTracking.cpp

if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
         break;
       case Intrinsic::riscv_vsetvli:
       case Intrinsic::riscv_vsetvlimax:
         // Assume that VL output is positive and would fit in an int32_t.
         // TODO: VLEN might be capped at 16 bits in a future V spec update.
         if (BitWidth >= 32)
           Known.Zero.setBitsFrom(31);
         break;
+      case Intrinsic::vscale: {
+        if (!II->getFunction()->hasFnAttribute(Attribute::VScaleRange))
+          break;
+
+        uint64_t MaxVScale = II->getFunction()
+                             ->getFnAttribute(Attribute::VScaleRange)
+                             .getVScaleRangeArgs()
+                             .second;
+
+        if (MaxVScale == 0)
+          break;
+
+        unsigned FirstZeroBit = 64 - countLeadingZeros(MaxVScale);
+        unsigned VScaleTypeSize = Q.DL.getTypeSizeInBits(II->getType()->getScalarType());
+        if (FirstZeroBit < VScaleTypeSize)
+          Known.Zero.setBitsFrom(FirstZeroBit);
+
+        break;
+      }
       }
     }
     break;
   case Instruction::ShuffleVector: {
     auto *Shuf = dyn_cast<ShuffleVectorInst>(I);
     // FIXME: Do we need to handle ConstantExpr involving shufflevectors?
     if (!Shuf) {
       Known.resetAll();
case Instruction::Freeze:
     break;
   }
 }
 
 /// Determine which bits of V are known to be either zero or one and return
 /// them.
 KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts,
                            unsigned Depth, const Query &Q) {
   KnownBits Known(getBitWidth(V->getType(), Q.DL));
   computeKnownBits(V, DemandedElts, Known, Depth, Q);
   return Known;
 }
 
 /// Determine which bits of V are known to be either zero or one and return
 /// them.
 KnownBits computeKnownBits(const Value *V, unsigned Depth, const Query &Q) {
   KnownBits Known(getBitWidth(V->getType(), Q.DL));
void computeKnownBits(const Value *V, const APInt &DemandedElts,
 
   assert(V && "No Value?");
   assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
 
 #ifndef NDEBUG
   Type *Ty = V->getType();
   unsigned BitWidth = Known.getBitWidth();
 
   assert((Ty->isIntOrIntVectorTy(BitWidth) || Ty->isPtrOrPtrVectorTy()) &&
          "Not integer or pointer type!");
 
   if (auto *FVTy = dyn_cast<FixedVectorType>(Ty)) {
     assert(
         FVTy->getNumElements() == DemandedElts.getBitWidth() &&
         "DemandedElt width should equal the fixed vector number of elements");
   } else {
     assert(DemandedElts == APInt(1, 1) &&

llvm/test/Transforms/InstCombine/icmp-vscale.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+define i1 @ugt_vscale64_x_32() vscale_range(0,16) {
+; CHECK-LABEL: @ugt_vscale64_x_32(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %vscale = call i64 @llvm.vscale.i64()
+  %num_els = shl i64 %vscale, 5
+  %res = icmp ugt i64 %num_els, 1024
+  ret i1 %res
+}
+
+define i1 @ugt_vscale64_x_31() vscale_range(0,16) {
+; CHECK-LABEL: @ugt_vscale64_x_31(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %vscale = call i64 @llvm.vscale.i64()
+  %num_els = mul i64 %vscale, 31
+  %res = icmp ugt i64 %num_els, 1024
+  ret i1 %res
+}
+
+define i1 @ugt_vscale16_x_32() vscale_range(0,16) {
+; CHECK-LABEL: @ugt_vscale16_x_32(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %vscale = call i16 @llvm.vscale.i16()
+  %num_els = shl i16 %vscale, 5
+  %res = icmp ugt i16 %num_els, 1024
+  ret i1 %res
+}
+
+define i1 @ult_vscale16() vscale_range(0,16) {
+; CHECK-LABEL: @ult_vscale16(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %vscale = call i16 @llvm.vscale.i16()
+  %res = icmp ult i16 1024, %vscale
+  ret i1 %res
+}
+
+define i1 @ule_vscale64() vscale_range(0,16) {
+; CHECK-LABEL: @ule_vscale64(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %vscale = call i64 @llvm.vscale.i64()
+  %res = icmp ule i64 1024, %vscale
+  ret i1 %res
+}
+
+define i1 @ne_vscale64_x_32() vscale_range(0,16) {
+; CHECK-LABEL: @ne_vscale64_x_32(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  %vscale = call i64 @llvm.vscale.i64()
+  %num_els = mul i64 %vscale, 32
+  %res = icmp ne i64 %num_els, 39488
+  ret i1 %res
+}
+
+declare i8 @llvm.vscale.i8()
+declare i16 @llvm.vscale.i16()
+declare i32 @llvm.vscale.i32()
+declare i64 @llvm.vscale.i64()

llvm/test/Transforms/LoopVectorize/AArch64/sve-widen-phi.ll

 ; that we can use gather instructions with the correct offsets, taking
 ; vscale into account.
 
 define void @widen_ptr_phi_unrolled(i32* noalias nocapture %a, i32* noalias nocapture %b, i32* nocapture readonly %c, i64 %n) #0 {
 ; CHECK-LABEL: @widen_ptr_phi_unrolled(
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[POINTER_PHI:%.*]] = phi i32* [ %c, %vector.ph ], [ %[[PTR_IND:.*]], %vector.body ]
 ; CHECK:         [[TMP5:%.*]] = call i64 @llvm.vscale.i64()
-; CHECK-NEXT:    [[TMP6:%.*]] = shl i64 [[TMP5]], 2
-; CHECK-NEXT:    [[TMP7:%.*]] = shl i64 [[TMP5]], 4
+; CHECK-NEXT:    [[TMP6:%.*]] = shl nuw nsw i64 [[TMP5]], 2
+; CHECK-NEXT:    [[TMP7:%.*]] = shl nuw nsw i64 [[TMP5]], 4
 ; CHECK-NEXT:    [[TMP8:%.*]] = call <vscale x 4 x i64> @llvm.experimental.stepvector.nxv4i64()
 ; CHECK-NEXT:    [[VECTOR_GEP:%.*]] = shl <vscale x 4 x i64> [[TMP8]], shufflevector (<vscale x 4 x i64> insertelement (<vscale x 4 x i64> poison, i64 1, i32 0), <vscale x 4 x i64> poison, <vscale x 4 x i32> zeroinitializer)
 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr i32, i32* [[POINTER_PHI]], <vscale x 4 x i64> [[VECTOR_GEP]]
 ; CHECK-NEXT:    [[DOTSPLATINSERT2:%.*]] = insertelement <vscale x 4 x i64> poison, i64 [[TMP6]], i32 0
 ; CHECK-NEXT:    [[DOTSPLAT3:%.*]] = shufflevector <vscale x 4 x i64> [[DOTSPLATINSERT2]], <vscale x 4 x i64> poison, <vscale x 4 x i32> zeroinitializer
 ; CHECK-NEXT:    [[TMP10:%.*]] = call <vscale x 4 x i64> @llvm.experimental.stepvector.nxv4i64()
 ; CHECK-NEXT:    [[TMP11:%.*]] = add <vscale x 4 x i64> [[DOTSPLAT3]], [[TMP10]]
 ; CHECK-NEXT:    [[VECTOR_GEP4:%.*]] = shl <vscale x 4 x i64> [[TMP11]], shufflevector (<vscale x 4 x i64> insertelement (<vscale x 4 x i64> poison, i64 1, i32 0), <vscale x 4 x i64> poison, <vscale x 4 x i32> zeroinitializer)

 ; CHECK-LABEL: @widen_2ptrs_phi_unrolled(
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    %[[IDX:.*]] = phi i64 [ 0, %vector.ph ], [ %{{.*}}, %vector.body ]
 ; CHECK-NEXT:    %[[LGEP1:.*]] = getelementptr i32, i32* %src, i64 %[[IDX]]
 ; CHECK-NEXT:    %[[SGEP1:.*]] = getelementptr i32, i32* %dst, i64 %[[IDX]]
 ; CHECK-NEXT:    %[[LPTR1:.*]] = bitcast i32* %[[LGEP1]] to <vscale x 4 x i32>*
 ; CHECK-NEXT:    %{{.*}} = load <vscale x 4 x i32>, <vscale x 4 x i32>* %[[LPTR1]], align 4
 ; CHECK-NEXT:    %[[VSCALE1:.*]] = call i32 @llvm.vscale.i32()
-; CHECK-NEXT:    %[[TMP1:.*]] = shl i32 %[[VSCALE1]], 2
-; CHECK-NEXT:    %[[TMP2:.*]] = sext i32 %[[TMP1]] to i64
+; CHECK-NEXT:    %[[TMP1:.*]] = shl nuw nsw i32 %[[VSCALE1]], 2
+; CHECK-NEXT:    %[[TMP2:.*]] = zext i32 %[[TMP1]] to i64
 ; CHECK-NEXT:    %[[LGEP2:.*]] = getelementptr i32, i32* %[[LGEP1]], i64 %[[TMP2]]
 ; CHECK-NEXT:    %[[LPTR2:.*]] = bitcast i32* %[[LGEP2]] to <vscale x 4 x i32>*
 ; CHECK-NEXT:    %{{.*}} = load <vscale x 4 x i32>, <vscale x 4 x i32>* %[[LPTR2]], align 4
 ; CHECK:         %[[SPTR1:.*]] = bitcast i32* %[[SGEP1]] to <vscale x 4 x i32>*
 ; CHECK-NEXT:    store <vscale x 4 x i32> %{{.*}}, <vscale x 4 x i32>* %[[SPTR1]], align 4
 ; CHECK-NEXT:    %[[VSCALE2:.*]] = call i32 @llvm.vscale.i32()
-; CHECK-NEXT:    %[[TMP3:.*]] = shl i32 %[[VSCALE2]], 2
-; CHECK-NEXT:    %[[TMP4:.*]] = sext i32 %[[TMP3]] to i64
+; CHECK-NEXT:    %[[TMP3:.*]] = shl nuw nsw i32 %[[VSCALE2]], 2
+; CHECK-NEXT:    %[[TMP4:.*]] = zext i32 %[[TMP3]] to i64
 ; CHECK-NEXT:    %[[SGEP2:.*]] = getelementptr i32, i32* %[[SGEP1]], i64 %[[TMP4]]
 ; CHECK-NEXT:    %[[SPTR2:.*]] = bitcast i32* %[[SGEP2]] to <vscale x 4 x i32>*
 ; CHECK-NEXT:    store <vscale x 4 x i32> %{{.*}}, <vscale x 4 x i32>* %[[SPTR2]], align 4
 
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body

 ; CHECK:       %[[IDX:.*]] = phi i64 [ 0, %vector.ph ], [ %{{.*}}, %vector.body ]
 ; CHECK:       %[[STEPVEC:.*]] = call <vscale x 2 x i64> @llvm.experimental.stepvector.nxv2i64()
 ; CHECK-NEXT:  %[[TMP1:.*]] = insertelement <vscale x 2 x i64> poison, i64 %[[IDX]], i32 0
 ; CHECK-NEXT:  %[[TMP2:.*]] = shufflevector <vscale x 2 x i64> %[[TMP1]], <vscale x 2 x i64> poison, <vscale x 2 x i32> zeroinitializer
 ; CHECK-NEXT:  %[[VECIND1:.*]] = add <vscale x 2 x i64> %[[TMP2]], %[[STEPVEC]]
 ; CHECK-NEXT:  %[[APTRS1:.*]] = getelementptr i32, i32* %a, <vscale x 2 x i64> %[[VECIND1]]
 ; CHECK-NEXT:  %[[GEPA1:.*]] = getelementptr i32, i32* %a, i64 %[[IDX]]
 ; CHECK-NEXT:  %[[VSCALE64:.*]] = call i64 @llvm.vscale.i64()
-; CHECK-NEXT:  %[[VSCALE64X2:.*]] = shl i64 %[[VSCALE64]], 1
+; CHECK-NEXT:  %[[VSCALE64X2:.*]] = shl nuw nsw i64 %[[VSCALE64]], 1
 ; CHECK-NEXT:  %[[TMP3:.*]] = insertelement <vscale x 2 x i64> poison, i64 %[[VSCALE64X2]], i32 0
 ; CHECK-NEXT:  %[[TMP4:.*]] = shufflevector <vscale x 2 x i64> %[[TMP3]], <vscale x 2 x i64> poison, <vscale x 2 x i32> zeroinitializer
 ; CHECK-NEXT:  %[[TMP5:.*]] = add <vscale x 2 x i64> %[[TMP4]], %[[STEPVEC]]
 ; CHECK-NEXT:  %[[VECIND2:.*]] = add <vscale x 2 x i64> %[[TMP2]], %[[TMP5]]
 ; CHECK-NEXT:  %[[APTRS2:.*]] = getelementptr i32, i32* %a, <vscale x 2 x i64> %[[VECIND2]]
 ; CHECK-NEXT:  %[[GEPB1:.*]] = getelementptr i32*, i32** %b, i64 %[[IDX]]
 ; The following checks that there is no extractelement after
 ; vectorization when the stepvector has multiple uses, which demonstrates
 ; the removal of a redundant fmov instruction in the generated asm code.
 ; CHECK-NOT:   %[[EXTRACT:.*]] = extractelement <vscale x 2 x i32*> [[APTRS1]], i32 0
 ; CHECK:       %[[BPTR1:.*]] = bitcast i32** %[[GEPB1]] to <vscale x 2 x i32*>*
 ; CHECK-NEXT:  store <vscale x 2 x i32*> %[[APTRS1]], <vscale x 2 x i32*>* %[[BPTR1]], align 8
 ; CHECK:       %[[VSCALE32:.*]] = call i32 @llvm.vscale.i32()
-; CHECK-NEXT:  %[[VSCALE32X2:.*]] = shl i32 %[[VSCALE32]], 1
-; CHECK-NEXT:  %[[TMP6:.*]] = sext i32 %[[VSCALE32X2]] to i64
+; CHECK-NEXT:  %[[VSCALE32X2:.*]] = shl nuw nsw i32 %[[VSCALE32]], 1
+; CHECK-NEXT:  %[[TMP6:.*]] = zext i32 %[[VSCALE32X2]] to i64
 ; CHECK-NEXT:  %[[GEPB2:.*]] = getelementptr i32*, i32** %[[GEPB1]], i64 %[[TMP6]]
 ; CHECK-NEXT:  %[[BPTR2:.*]] = bitcast i32** %[[GEPB2]] to <vscale x 2 x i32*>*
 ; CHECK-NEXT   store <vscale x 2 x i32*> %[[APTRS2]], <vscale x 2 x i32*>* %[[BPTR2]], align 8
 
 entry:
   br label %for.body
 
 for.body: