[TargetLowering] Improve legalization of scalable vector types

[frasercrmck]

Summary

This patch extends the vector type-conversion and legalization capabilities of
scalable vector types.

Firstly, vscale x 1 types now behave more like the corresponding `vscale x
2+` types. This enables the integer promotion legalization of extended scalable
types, such as the promotion of <vscale x 1 x i5> to <vscale x 1 x i8>.

These vscale x 1 types are also now better handled by
getVectorTypeBreakdown, where what looks like older handling for 1-element
fixed-length vector types was spuriously updated to include scalable types.

Widening of scalable types is now better supported, by using INSERT_SUBVECTOR
to insert the smaller scalable vector "value" type into the wider scalable
vector "part" type. This allows AArch64 to pass and return vscale x 1 types
by value by widening.

There are still cases where we are unable to legalize vscale x 1 types, such
as where expansion would require splitting the vector in two.

[craig.topper]

llvm/test/CodeGen/RISCV/rvv/legalize-scalable-vectortype.ll

3

These tests don't cover widening do they?

[frasercrmck]

llvm/test/CodeGen/RISCV/rvv/legalize-scalable-vectortype.ll

3

True, they don't. To be honest I was specifically targeting the promotion but the code looks like it should handle widening okay. I'm not sure we have an RVV case where we have to widen an illegal <vscale x 1 x ty> type to a legal one.

[craig.topper]

llvm/test/CodeGen/RISCV/rvv/legalize-scalable-vectortype.ll

3

I can't remember if the caller can handle widening scalable vectors properly. I fought with this code before when we tried to use types like <vscale x 6 x ty> for x6 segment load/stores.

Can the vectorize create these <vscale x 4 x i5> types that need promotion?

[frasercrmck]

llvm/test/CodeGen/RISCV/rvv/legalize-scalable-vectortype.ll

3

Yeah I wouldn't be surprised. Since this patch only affects vscale x 1 types, any existing issues in widening scalable vectors are already out in the open. I think without proper tests, ot might be best to remove the claim of "allowing" widening from this patch. At least we can say it now treats vscale x 1 more similarly to the others.

I haven't looked too deeply but I believe these i5s can appear during switch generation or switch case optimizations. I don't know about the loop vectorizer, but our WFV vectorizer will happily vectorize these.

[frasercrmck]

• rebase

[frasercrmck]

I've tried to find a test case for vector widening but wasn't able to. I've updated the description of the patch to reflect this.

[sdesmalen]

Hi @frasercrmck, thanks for working on this. We're currently investigating legalization of <vscale x 1 x eltty> vectors for SVE, so we'll be able to add some tests for the widening case.

llvm/lib/CodeGen/TargetLoweringBase.cpp

997

I found that when widening <vscale x 1 x eltty>, it shouldn't go down this code-path and hit the fatal error, but rather continue down the code path below (so that it will actually try to widening to <vscale x 2 x eltty>, <vscale x 4 x eltty>, etc. until it has found a legal one.

That said, without a way to test this having the fatal_error is fine for now, especially since we'll soon share some patches that implements the widening of these types with corresponding tests. vscale x 1 types are never legal for SVE and always need widening.

1515

Is this equivalent to EltCnt.isVector() ? (I assume we can assert that a minimum value of 0 is not allowed)

[frasercrmck]

• rebase
• add initial widening
• support scalable vectors in widenVectorToPartType

[frasercrmck]

In D102073#2753558, @sdesmalen wrote:

Hi @frasercrmck, thanks for working on this. We're currently investigating legalization of <vscale x 1 x eltty> vectors for SVE, so we'll be able to add some tests for the widening case.

Hi @sdesmalen, thanks for getting in touch. I've just updated the patch to add some initial widening support for AArch64. Let me know what you think. It's very basic right now as I've found that we can't yet widen the subvector operations.

llvm/lib/CodeGen/TargetLoweringBase.cpp

997

Thanks for the input. I was wondering that whether widening would be better, yeah. I think holding off until your patch sounds reasonable.

1515

I think it's more strictly equivalent to !EltCnt.isScalar() which I was about to update to use. I think that's marginally more readable as people may wonder why we're checking isVector in what's obviously a vector method. What do you think?

llvm/test/CodeGen/RISCV/rvv/legalize-scalable-vectortype.ll

3

I've added some initial widening tests for AArch64.

[sdesmalen]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

616–625

Should this also return SDValue() if PartNumElts.isScalable() != ValueNumElts.isScalable() ?

llvm/lib/CodeGen/TargetLoweringBase.cpp

1515

I'm kind of neutral on it, but I see how this may cause some confusion. Perhaps we should consider removing the isVector() method entirely in favour of using !isScalar() at some point.

[frasercrmck]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

616–625

Possibly. I was thinking that technically we can widen a fixed-length Value to a scalable Part -- the same way we widen a scalable Value to scalable Part -- using INSERT_SUBVECTOR. Though only if the Part element count is known to be greater than the Value element count, so this would disallow widening v4i32 to nxv1i32, for instance. We definitely can't support widening a scalable to a fixed so we must certainly return SDValue() there.

I tried to permit these scenarios in the code, though it's hypothetical since we don't have a target that uses the "mixed" widening.

If you think that all of this is unnecessary then I'm happy to take your suggestion.

[sdesmalen]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

616–625

Without a specific use-case in mind, I have a slight preference to avoid widening (or possibly allowing to widen) fixed-width to scalable vectors until there is a real need for it, and until we can write a test-case. By returning SDValue, the code in getCopyTo/FromPartsVector will probably fail earlier on, rather than doing something that may be wrong. Maybe it doesn't really matter, but I guess it's easy to change this code if we do need it at some point.

[frasercrmck]

• only widen vectors with equivalent scalable properties

[frasercrmck]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

616–625

Fair enough, I have a bit of a habit of doing that. I've added that check now.

[sdesmalen]

LGTM, thanks!

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

for (unsigned i = 0; i < NumParts; i += StepSize) {
       }
     }
   }
 
   if (DAG.getDataLayout().isBigEndian())
     std::reverse(Parts, Parts + OrigNumParts);
 }
 
-static SDValue widenVectorToPartType(SelectionDAG &DAG,
-                                     SDValue Val, const SDLoc &DL, EVT PartVT) {
-  if (!PartVT.isFixedLengthVector())
+static SDValue widenVectorToPartType(SelectionDAG &DAG, SDValue Val,
+                                     const SDLoc &DL, EVT PartVT) {
+  if (!PartVT.isVector())
     return SDValue();
 
   EVT ValueVT = Val.getValueType();
-  unsigned PartNumElts = PartVT.getVectorNumElements();
-  unsigned ValueNumElts = ValueVT.getVectorNumElements();
-  if (PartNumElts > ValueNumElts &&
-      PartVT.getVectorElementType() == ValueVT.getVectorElementType()) {
-    EVT ElementVT = PartVT.getVectorElementType();
-    // Vector widening case, e.g. <2 x float> -> <4 x float>.  Shuffle in
-    // undef elements.
-    SmallVector<SDValue, 16> Ops;
-    DAG.ExtractVectorElements(Val, Ops);
-    SDValue EltUndef = DAG.getUNDEF(ElementVT);
-    for (unsigned i = ValueNumElts, e = PartNumElts; i != e; ++i)
-      Ops.push_back(EltUndef);
+  ElementCount PartNumElts = PartVT.getVectorElementCount();
+  ElementCount ValueNumElts = ValueVT.getVectorElementCount();
+
+  // We only support widening vectors with equivalent element types and
+  // fixed/scalable properties. If a target needs to widen a fixed-length type
+  // to a scalable one, it should be possible to use INSERT_SUBVECTOR below.
+  if (ElementCount::isKnownLE(PartNumElts, ValueNumElts) ||
+      PartNumElts.isScalable() != ValueNumElts.isScalable() ||
+      PartVT.getVectorElementType() != ValueVT.getVectorElementType())
+    return SDValue();
+
+  // Widening a scalable vector to another scalable vector is done by inserting
+  // the vector into a larger undef one.
+  if (PartNumElts.isScalable())
+    return DAG.getNode(ISD::INSERT_SUBVECTOR, DL, PartVT, DAG.getUNDEF(PartVT),
+                       Val, DAG.getVectorIdxConstant(0, DL));
+
+  Ops.append((PartNumElts - ValueNumElts).getFixedValue(), EltUndef);
 
-    // FIXME: Use CONCAT for 2x -> 4x.
-    return DAG.getBuildVector(PartVT, DL, Ops);
-  }
 
-  return SDValue();
-}
-
 /// getCopyToPartsVector - Create a series of nodes that contain the specified
 /// value split into legal parts.
 static void getCopyToPartsVector(SelectionDAG &DAG, const SDLoc &DL,
                                  SDValue Val, SDValue *Parts, unsigned NumParts,
                                  MVT PartVT, const Value *V,
                                  Optional<CallingConv::ID> CallConv) {
   EVT ValueVT = Val.getValueType();
   assert(ValueVT.isVector() && "Not a vector");

llvm/lib/CodeGen/TargetLoweringBase.cpp

TargetLoweringBase::getTypeConversion(LLVMContext &Context, EVT VT) const {
   // Handle vector types.
   ElementCount NumElts = VT.getVectorElementCount();
   EVT EltVT = VT.getVectorElementType();
 
   // Vectors with only one element are always scalarized.
   if (NumElts.isScalar())
     return LegalizeKind(TypeScalarizeVector, EltVT);
 
-  if (VT.getVectorElementCount() == ElementCount::getScalable(1))
-    report_fatal_error("Cannot legalize this vector");
-
   // Try to widen vector elements until the element type is a power of two and
   // promote it to a legal type later on, for example:
   // <3 x i8> -> <4 x i8> -> <4 x i32>
   if (EltVT.isInteger()) {
     // Vectors with a number of elements that is not a power of two are always
     // widened, for example <3 x i8> -> <4 x i8>.
     if (!VT.isPow2VectorType()) {
       NumElts = NumElts.coefficientNextPowerOf2();
       EVT NVT = EVT::getVectorVT(Context, EltVT, NumElts);
       return LegalizeKind(TypeWidenVector, NVT);
     }
 
     // Examine the element type.
     LegalizeKind LK = getTypeConversion(Context, EltVT);
 
     // If type is to be expanded, split the vector.
     //  <4 x i140> -> <2 x i140>
-    if (LK.first == TypeExpandInteger)
+    if (LK.first == TypeExpandInteger) {
+      if (VT.getVectorElementCount() == ElementCount::getScalable(1))
+        report_fatal_error("Cannot legalize this scalable vector");
       return LegalizeKind(TypeSplitVector,
                           VT.getHalfNumVectorElementsVT(Context));
+    }
 
     // Promote the integer element types until a legal vector type is found
     // or until the element integer type is too big. If a legal type was not
     // found, fallback to the usual mechanism of widening/splitting the
     // vector.
     EVT OldEltVT = EltVT;
     while (true) {
       // Increase the bitwidth of the element to the next pow-of-two
TargetLoweringBase::getTypeConversion(LLVMContext &Context, EVT VT) const {
   }
 
   // Widen odd vectors to next power of two.
   if (!VT.isPow2VectorType()) {
     EVT NVT = VT.getPow2VectorType(Context);
     return LegalizeKind(TypeWidenVector, NVT);
   }
 
+  if (VT.getVectorElementCount() == ElementCount::getScalable(1))
+    report_fatal_error("Cannot legalize this vector");
+
   // Vectors with illegal element types are expanded.
   EVT NVT = EVT::getVectorVT(Context, EltVT,
                              VT.getVectorElementCount().divideCoefficientBy(2));
   return LegalizeKind(TypeSplitVector, NVT);
 }
 
 static unsigned getVectorTypeBreakdownMVT(MVT VT, MVT &IntermediateVT,
                                           unsigned &NumIntermediates,

 /// getVectorTypeBreakdown - Vector types are broken down into some number of
 /// legal first class types.  For example, MVT::v8f32 maps to 2 MVT::v4f32
 /// with Altivec or SSE1, or 8 promoted MVT::f64 values with the X86 FP stack.
 /// Similarly, MVT::v2i64 turns into 4 MVT::i32 values with both PPC and X86.
 ///
 /// This method returns the number of registers needed, and the VT for each
 /// register.  It also returns the VT and quantity of the intermediate values
 /// before they are promoted/expanded.
-unsigned TargetLoweringBase::getVectorTypeBreakdown(LLVMContext &Context, EVT VT,
-                                                EVT &IntermediateVT,
+unsigned TargetLoweringBase::getVectorTypeBreakdown(LLVMContext &Context,
+                                                    EVT VT, EVT &IntermediateVT,
                                                     unsigned &NumIntermediates,
                                                     MVT &RegisterVT) const {
   ElementCount EltCnt = VT.getVectorElementCount();
 
   // If there is a wider vector type with the same element type as this one,
   // or a promoted vector type that has the same number of elements which
   // are wider, then we should convert to that legal vector type.
   // This handles things like <2 x float> -> <4 x float> and
   // <4 x i1> -> <4 x i32>.
   LegalizeTypeAction TA = getTypeAction(Context, VT);
-  if (EltCnt.getKnownMinValue() != 1 &&
+  if (!EltCnt.isScalar() &&
       (TA == TypeWidenVector || TA == TypePromoteInteger)) {
     EVT RegisterEVT = getTypeToTransformTo(Context, VT);
     if (isTypeLegal(RegisterEVT)) {
       IntermediateVT = RegisterEVT;
       RegisterVT = RegisterEVT.getSimpleVT();
       NumIntermediates = 1;
       return 1;
     }

llvm/test/CodeGen/AArch64/sve-widen-scalable-vectortype.ll

+; RUN: llc -mtriple=aarch64--linux-gnu -mattr=+sve -asm-verbose=0 < %s
+
+; Test that scalable vectors that are smaller than the legal vector size can be
+; properly widened to part vectors.
+
+;
+; Vectors that need widening
+;
+
+; For now, just check that these don't crash during legalization. Widening of
+; scalable-vector INSERT_SUBVECTOR and EXTRACT_SUBVECTOR is not yet available.
+define <vscale x 1 x i32> @widen_1i32(<vscale x 1 x i32> %illegal) nounwind {
+  ret <vscale x 1 x i32> %illegal
+}
+
+define <vscale x 1 x double> @widen_1f64(<vscale x 1 x double> %illegal) nounwind {
+  ret <vscale x 1 x double> %illegal
+}

llvm/test/CodeGen/RISCV/rvv/legalize-scalable-vectortype.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=riscv32 -mattr=+experimental-v -verify-machineinstrs < %s | FileCheck %s
+; RUN: llc -mtriple=riscv64 -mattr=+experimental-v -verify-machineinstrs < %s | FileCheck %s
+
+define <vscale x 4 x i5> @trunc_nxv4i32_to_nxv4i5(<vscale x 4 x i32> %a) {
+; CHECK-LABEL: trunc_nxv4i32_to_nxv4i5:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    vsetvli a0, zero, e16,m1,ta,mu
+; CHECK-NEXT:    vnsrl.wi v25, v8, 0
+; CHECK-NEXT:    vsetvli a0, zero, e8,mf2,ta,mu
+; CHECK-NEXT:    vnsrl.wi v8, v25, 0
+; CHECK-NEXT:    ret
+  %v = trunc <vscale x 4 x i32> %a to <vscale x 4 x i5>
+  ret <vscale x 4 x i5> %v
+}
+
+define <vscale x 1 x i5> @trunc_nxv1i32_to_nxv1i5(<vscale x 1 x i32> %a) {
+; CHECK-LABEL: trunc_nxv1i32_to_nxv1i5:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    vsetvli a0, zero, e16,mf4,ta,mu
+; CHECK-NEXT:    vnsrl.wi v25, v8, 0
+; CHECK-NEXT:    vsetvli a0, zero, e8,mf8,ta,mu
+; CHECK-NEXT:    vnsrl.wi v8, v25, 0
+; CHECK-NEXT:    ret
+  %v = trunc <vscale x 1 x i32> %a to <vscale x 1 x i5>
+  ret <vscale x 1 x i5> %v
+}