[VP][SelectionDAG][RISCV] Add get_vector_length intrinsics and generic SelectionDAG support.

[craig.topper]

Summary

The generic implementation is umin(TC, VF * vscale).

Lowering to vsetvli for RISC-V will come in a future patch.

This patch is a pre-requisite to be able to CodeGen vectorized code from
D99750.

[simoll]

I suppose this makes sense for ARM MVE/SVE as well?
Generally, we should simplify this in IR for other targets and/or tripcounts with known multiples: otherwise the VP expansion pass will create %evl-to-%mask expansion code not knowing that the %evl is ineffective (eg %evl == vector_length).

[craig.topper]

-Add SVE test.
-Updates to LangRef. Reflect that this intrinsic is not require to return VF*vscale for count > VF*vscale. We need this to make RISC-V's vsetvli a valid implementation of this intrinsic.

[frasercrmck]

llvm/docs/LangRef.rst

18072

Double comma here

18073

Should we explicitly denote this intrinsic with immarg parameters in the LangRef? I only see the one doing it but it sounds kind helpful

18087

Maybe also saying that the element width is in bits would clarify things a little better.

18087

If it's just a hint, do we need to restrict it to being at least 8? It might feel a little artificial.

[craig.topper]

Address comment. Fix dangling node in SelectionDAGBuilder

[frasercrmck]

It looks good to me, but I'd like to leave it open for a bit so that other more active reviewers can take a look.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

7315

Do we want to sanitize negative immediates here or elsewhere, or do we just let them become large positive ones?

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

7315

Good question. Do you have a suggestion how to sanitize it?

[frasercrmck]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

7315

Would adding something to the verifier be sufficient? Then we may be able to assert here?

[craig.topper]

Add verifier check

[craig.topper]

Pass VF to shouldExpandGetVectorLength

[rogfer01]

Thanks @craig.topper. This went under our radar. Apologies.

In general this makes sense, but if we want this to be useful for the VE target we need to address the fixed vector case. Being able to set the vector length is orthogonal to scalable vectors.

We assume that a call to llvm.experimental.get.vector.length for VE (or any other fixed-vector target with vector length) would set the cnt parameter, might optionally use the element_width parameter and then the vector factor would not be scaled by vscale. The user of the intrinsic, like the loop vectorizer, would have already chosen a meaningful value for vf for VE (VE for instance can use vf=256 when operating with 64-bit element width).

However this would render the intrinsic a bit ambiguous between fixed and scalable.

Maybe we can add an additional parameter stating if the VF is actually scaled by vscale or not (e.g., an immarg i1 or maybe a metadata string operand)?

llvm/docs/LangRef.rst

18094

I'd emphasise the fact that we always return an i32, this may be easy to miss from the two instances in the Syntax section.

18099

I think we want to explain that when cnt ≤ (vscale * VF) (for now, assume vscale = 1 if we're dealing with fixed vectors). We understand in this case the result of this intrinsic is cnt.

Also the case for cnt > (vscale * VF) is worded in a bit of an obscure way and might not be true as we understand it. For the specific case of RISC-V, if VLMAX=64, cnt=64 will return 64 but cnt=65 may return a value x ∊ (32, 64], like 33. That would not be a result "at least as large as the result for any value less than count" (we understand "any value less than count" as a value ∊ [0, 64]). Maybe we got it wrong.

[craig.topper]

Attempt to address Roger's comments.

[rogfer01]

@kaz7 do you have any thoughts on the way we intend to define this generic intrinsic? I think it may be useful for VE as well.

llvm/docs/LangRef.rst

18072

Typo scalable? (maybe this is an abbreviation but only one letter was left out)

[reames]

This looks reasonable to me, minor comments only.

llvm/docs/LangRef.rst

18085

First argument is interpreted an unsigned integer correct? Should state that.

18105

reword: larger than the maximum legal vectorization factor.

Also, should probably add a requirement here that zero is only returned when the requested trip count is zero.

llvm/lib/IR/Verifier.cpp

5463 ↗

(On Diff #523874)

I don't think the element width can be zero or negative either can it?

[reames]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

7322

I believe this is just computing the number of elements in the ElementCount constructed from VF and the scaleable bit.

On the IR level, we have CreateElementCount on IRBuilder. We probably need something analogous on DAG. It looks like we've got a couple examples already, so it'd be good to pull that out and rebase.

One generic optimization we should probably add (in a separate patch), is to fold get_active_vector_length to TC when TC can be proven less than EC.

[craig.topper]

llvm/docs/LangRef.rst

18105

I'm not sure what you mean by "maximum legalization factor"? My statement here was intended to only refer to the vectorization factor passed in. If the vectorization factor is for a type that isn't supported legally by hardware, the intrinsic will still return a vector length that utilizes the whole type.

[reames]

llvm/docs/LangRef.rst

18105

How about something like this? (For clarity, this is going in a different direction than my original comment.)

If the count is larger than the number of lanes in the type described by the last two arguments, then this intrinsic may return a value less than the number of lanes implied by the type.

Basically, what if we were explicit about the VF and scalable bit mapping to a type, and then described the behavior in terms of the number of runtime lanes in that type?

[craig.topper]

Address review comments

[reames]

LGTM

p.s. It would be helpful to land this even well in advance of the vectorizer changes. That would lets us write code gen test cases for both variants of VP predication being discussed, and see what we can get code generation to look like.

[craig.topper]

Remove the element width hint. I don't think it's worth while right now.

[frasercrmck]

LGTM too, one typo

llvm/docs/LangRef.rst

18085

typo: specifieso?

[craig.topper]

Fix typo

[craig.topper]

Returning to review since I dropped the element width after @reames review

[reames]

In D149916#4375221, @craig.topper wrote:

Returning to review since I dropped the element width after @reames review

I think we are going to need that, but I'm happy to take advantage of this being an experimental intrinsic and iterating in tree, so LGTM either way.

llvm/docs/LangRef.rst

 
 
 Arguments:
 """"""""""
 
 None.
 
 
+'``llvm.experimental.get.vector.length``' Intrinsic
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+Syntax:
+"""""""
+This is an overloaded intrinsic.
+
+::
+
+      declare i32 @llvm.experimental.get.vector.length.i32(i32 %cnt, i32 immarg %element_width, i32 immarg %vf)
+      declare i32 @llvm.experimental.get.vector.length.i64(i64 %cnt, i32 immarg %element_width, i32 immarg %vf)
+
+Overview:
+"""""""""
+
+The '``llvm.experimental.get.vector.length.*``' intrinsics take a number of
+elements to process and returns how many of the elements can be processed
+with the requested vectorization factor.
+
+Arguments:
+""""""""""
+
+The first operand is of any integer type and specifies total number of elements
+to be processed. The second argument is an i32 immediate for the element width
+in bits of the vector type. This serves as a hint to the target about the
+element types involved in the loop. The third parameter is an i32 immediate for
+the vectorization factor. This factor is treated as a multiple of vscale.
+
+Semantics:
+""""""""""
+
+Returns a positive value (explicit vector length) that is unknown at compile
+time and depends on the hardware specification.
+If the result value does not fit in the result type, then the result is
+a :ref:`poison value <poisonvalues>`.
+
+If the total count is larger than VF*vscale, this intrinsic may not return
+VF*vscale. The result will be at least as large as the result for any value
+less than count. This ensures that calling it for the total count will return
+the largest value any later loop iteration will see.
+
 Matrix Intrinsics
 -----------------
 
 Operations on matrixes requiring shape information (like number of rows/columns
 or the memory layout) can be expressed using the matrix intrinsics. These
 intrinsics require matrix dimensions to be passed as immediate arguments, and
 matrixes are passed and returned as vectors. This means that for a ``R`` x
 ``C`` matrix, element ``i`` of column ``j`` is at index ``j * R + i`` in the
 corresponding vector, with indices starting at 0. Currently column-major layout
 is assumed.  The intrinsics support both integer and floating point matrixes.

llvm/include/llvm/CodeGen/TargetLowering.h

 //===- llvm/CodeGen/TargetLowering.h - Target Lowering Info -----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 ///
public:
   }
 
   /// Return true if the @llvm.get.active.lane.mask intrinsic should be expanded
   /// using generic code in SelectionDAGBuilder.
   virtual bool shouldExpandGetActiveLaneMask(EVT VT, EVT OpVT) const {
     return true;
   }
 
+  virtual bool shouldExpandGetVectorLength() const {
+    return true;
+  }
+
   // Return true if op(vecreduce(x), vecreduce(y)) should be reassociated to
   // vecreduce(op(x, y)) for the reduction opcode RedOpc.
   virtual bool shouldReassociateReduction(unsigned RedOpc, EVT VT) const {
     return true;
   }
 
   /// Return true if it is profitable to convert a select of FP constants into
   /// a constant pool load whose address depends on the select condition. The

llvm/include/llvm/IR/Intrinsics.td

def int_vp_cttz : DefaultAttrsIntrinsic<[ llvm_anyvector_ty ],
                                llvm_i32_ty]>;
 }
 
 def int_get_active_lane_mask:
   DefaultAttrsIntrinsic<[llvm_anyvector_ty],
             [llvm_anyint_ty, LLVMMatchType<1>],
             [IntrNoMem, IntrNoSync, IntrWillReturn]>;
 
+def int_experimental_get_vector_length:
+  DefaultAttrsIntrinsic<[llvm_i32_ty],
+                        [llvm_anyint_ty, llvm_i32_ty, llvm_i32_ty],
+                        [IntrNoMem, IntrNoSync, IntrWillReturn,
+                         ImmArg<ArgIndex<1>>, ImmArg<ArgIndex<2>>]>;
+
 def int_experimental_vp_splice:
   DefaultAttrsIntrinsic<[llvm_anyvector_ty],
             [LLVMMatchType<0>,
              LLVMMatchType<0>,
              llvm_i32_ty,
              LLVMScalarOrSameVectorWidth<0, llvm_i1_ty>,
              llvm_i32_ty, llvm_i32_ty],
             [IntrNoMem, ImmArg<ArgIndex<2>>]>;

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

 //===- SelectionDAGBuilder.cpp - Selection-DAG building -------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
case Intrinsic::get_active_lane_mask: {
     SDValue VectorStep = DAG.getStepVector(sdl, VecTy);
     SDValue VectorInduction = DAG.getNode(
         ISD::UADDSAT, sdl, VecTy, VectorIndex, VectorStep);
     SDValue SetCC = DAG.getSetCC(sdl, CCVT, VectorInduction,
                                  VectorTripCount, ISD::CondCode::SETULT);
     setValue(&I, SetCC);
     return;
   }
+  case Intrinsic::experimental_get_vector_length: {
+    if (!TLI.shouldExpandGetVectorLength()) {
+      visitTargetIntrinsic(I, Intrinsic);
+      return;
+    }
+
+    // Expand to a umin between the trip count and the maximum elements the type
+    // can hold.
+    EVT VT = TLI.getValueType(DAG.getDataLayout(), I.getType());
+    SDValue TripCount = getValue(I.getOperand(0));
+
+    // Extend the trip count to at least the result VT.
+    if (TripCount.getValueType().bitsLT(VT))
+      TripCount = DAG.getNode(ISD::ZERO_EXTEND, sdl, VT, TripCount);
+
+    EVT TripCountVT = TripCount.getValueType();
+
+    uint64_t VF = cast<ConstantInt>(I.getOperand(2))->getZExtValue();
+    SDValue MaxEVL = DAG.getVScale(sdl, TripCountVT,
+                                   APInt(TripCountVT.getSizeInBits(), VF));
+    SDValue UMin = DAG.getNode(ISD::UMIN, sdl, TripCountVT, TripCount, MaxEVL);
+    // Clip to the result type if needed.
+    SDValue Trunc = DAG.getNode(ISD::TRUNCATE, sdl, VT, UMin);
+
+    setValue(&I, Trunc);
+    return;
+  }
   case Intrinsic::vector_insert: {
     SDValue Vec = getValue(I.getOperand(0));
     SDValue SubVec = getValue(I.getOperand(1));
     SDValue Index = getValue(I.getOperand(2));
 
     // The intrinsic's index type is i64, but the SDNode requires an index type
     // suitable for the target. Convert the index as required.
     MVT VectorIdxTy = TLI.getVectorIdxTy(DAG.getDataLayout());

llvm/test/CodeGen/AArch64/get_vector_length.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py UTC_ARGS: --version 2
+; RUN: llc < %s -mtriple=aarch64-linux-gnu -mattr=+sve | FileCheck %s
+
+declare i32 @llvm.experimental.get.vector.length.i16(i16, i32, i32)
+declare i32 @llvm.experimental.get.vector.length.i32(i32, i32, i32)
+declare i32 @llvm.experimental.get.vector.length.i64(i64, i32, i32)
+
+define i32 @vector_length_i16(i16 zeroext %tc) {
+; CHECK-LABEL: vector_length_i16:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    cntd x8
+; CHECK-NEXT:    cmp w0, w8
+; CHECK-NEXT:    csel w0, w0, w8, lo
+; CHECK-NEXT:    ret
+  %a = call i32 @llvm.experimental.get.vector.length.i16(i16 %tc, i32 8, i32 2)
+  ret i32 %a
+}
+
+define i32 @vector_length_i32(i32 zeroext %tc) {
+; CHECK-LABEL: vector_length_i32:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    cntd x8
+; CHECK-NEXT:    cmp w0, w8
+; CHECK-NEXT:    csel w0, w0, w8, lo
+; CHECK-NEXT:    ret
+  %a = call i32 @llvm.experimental.get.vector.length.i32(i32 %tc, i32 8, i32 2)
+  ret i32 %a
+}
+
+define i32 @vector_length_i64(i64 %tc) {
+; CHECK-LABEL: vector_length_i64:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    cntd x8
+; CHECK-NEXT:    cmp x0, x8
+; CHECK-NEXT:    csel x0, x0, x8, lo
+; CHECK-NEXT:    // kill: def $w0 killed $w0 killed $x0
+; CHECK-NEXT:    ret
+  %a = call i32 @llvm.experimental.get.vector.length.i64(i64 %tc, i32 8, i32 2)
+  ret i32 %a
+}

llvm/test/CodeGen/RISCV/rvv/get_vector_length.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py UTC_ARGS: --version 2
+; RUN: sed 's/iXLen/i32/g' %s | llc -mtriple=riscv32 -mattr=+v -verify-machineinstrs | FileCheck %s --check-prefixes=CHECK,RV32
+; RUN: sed 's/iXLen/i32/g' %s | llc -mtriple=riscv64 -mattr=+v -verify-machineinstrs | FileCheck %s --check-prefixes=CHECK,RV64
+
+declare i32 @llvm.experimental.get.vector.length.i16(i16, i32, i32)
+declare i32 @llvm.experimental.get.vector.length.i32(i32, i32, i32)
+declare i32 @llvm.experimental.get.vector.length.i64(i64, i32, i32)
+
+define i32 @vector_length_i16(i16 zeroext %tc) {
+; CHECK-LABEL: vector_length_i16:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    csrr a1, vlenb
+; CHECK-NEXT:    srli a1, a1, 2
+; CHECK-NEXT:    bltu a0, a1, .LBB0_2
+; CHECK-NEXT:  # %bb.1:
+; CHECK-NEXT:    mv a0, a1
+; CHECK-NEXT:  .LBB0_2:
+; CHECK-NEXT:    ret
+  %a = call i32 @llvm.experimental.get.vector.length.i16(i16 %tc, i32 8, i32 2)
+  ret i32 %a
+}
+
+define i32 @vector_length_i32(i32 zeroext %tc) {
+; RV32-LABEL: vector_length_i32:
+; RV32:       # %bb.0:
+; RV32-NEXT:    csrr a1, vlenb
+; RV32-NEXT:    srli a1, a1, 2
+; RV32-NEXT:    bltu a0, a1, .LBB1_2
+; RV32-NEXT:  # %bb.1:
+; RV32-NEXT:    mv a0, a1
+; RV32-NEXT:  .LBB1_2:
+; RV32-NEXT:    ret
+;
+; RV64-LABEL: vector_length_i32:
+; RV64:       # %bb.0:
+; RV64-NEXT:    sext.w a0, a0
+; RV64-NEXT:    csrr a1, vlenb
+; RV64-NEXT:    srli a1, a1, 2
+; RV64-NEXT:    bltu a0, a1, .LBB1_2
+; RV64-NEXT:  # %bb.1:
+; RV64-NEXT:    mv a0, a1
+; RV64-NEXT:  .LBB1_2:
+; RV64-NEXT:    ret
+  %a = call i32 @llvm.experimental.get.vector.length.i32(i32 %tc, i32 8, i32 2)
+  ret i32 %a
+}
+
+define i32 @vector_length_XLen(iXLen zeroext %tc) {
+; RV32-LABEL: vector_length_XLen:
+; RV32:       # %bb.0:
+; RV32-NEXT:    csrr a1, vlenb
+; RV32-NEXT:    srli a1, a1, 2
+; RV32-NEXT:    bltu a0, a1, .LBB2_2
+; RV32-NEXT:  # %bb.1:
+; RV32-NEXT:    mv a0, a1
+; RV32-NEXT:  .LBB2_2:
+; RV32-NEXT:    ret
+;
+; RV64-LABEL: vector_length_XLen:
+; RV64:       # %bb.0:
+; RV64-NEXT:    sext.w a0, a0
+; RV64-NEXT:    csrr a1, vlenb
+; RV64-NEXT:    srli a1, a1, 2
+; RV64-NEXT:    bltu a0, a1, .LBB2_2
+; RV64-NEXT:  # %bb.1:
+; RV64-NEXT:    mv a0, a1
+; RV64-NEXT:  .LBB2_2:
+; RV64-NEXT:    ret
+  %a = call i32 @llvm.experimental.get.vector.length.iXLen(iXLen %tc, i32 8, i32 2)
+  ret i32 %a
+}