[SelectionDAG] Implement SplitVecOp_INSERT_SUBVECTOR

[joechrisellis]

Summary

This function is needed for when it is necessary to split the subvector
operand of an llvm.experimental.vector.insert call. Splitting the
subvector operand means performing two insertions: one inserting the
lower part of the split subvector into the destination vector, and
another for inserting the upper part.

Through experimenting, it seems quite rare to need split the subvector
operand, but this is necessary to avoid assertion errors.

[lebedev.ri]

Tests missing

[joechrisellis]

@lebedev.ri hi, I am aware of this. Changes planned. 🙂

[joechrisellis]

Add test.

[david-arm]

Hi @joechrisellis, hope you don't mind but I've added @paulwalker-arm and @kmclaughlin as reviewers, due to the legalisation work they've been involved in for the last few months!

[david-arm]

Is it possible to add a brief description of what the intent of this patch is? It's not immediately obvious why we're adding the split function from the code or summary. I'm assuming it's related to the new intrinsic in your test, since LLVM has not needed this function until now?

[joechrisellis]

In D92760#2439765, @david-arm wrote:

Is it possible to add a brief description of what the intent of this patch is? It's not immediately obvious why we're adding the split function from the code or summary. I'm assuming it's related to the new intrinsic in your test, since LLVM has not needed this function until now?

Yes, good idea. I am not sure, but I think it might have actually been possible to hit a codepath that expects the split function to exist even without the new llvm.experimental.vector.insert intrinsics (unless the INSERT_SUBVECTOR ISD nodes are never created?). From our experiments, it's pretty rare that we end up needing this function even with the intrinsics anyway. But it does prevent an assertion error in certain circumstances. 🙂

Also, it might be worth noting that operand splitting is already implemented for EXTRACT_SUBVECTOR.

[david-arm]

If you can find a test that exposes the need for this split function with generic IR that would be really helpful I think - LLVM has managed for a long time without needing this split function so something has changed. I suspect it's probably just the new intrinsic that now exposes this code path.

llvm/test/CodeGen/AArch64/split-vector-insert.ll

6

Could you add a few more tests here, for example test floating point (nxv2f64.v8f64) and predicate vectors (nxv2i1.v8i1)?

[paulwalker-arm]

In D92760#2442179, @david-arm wrote:

If you can find a test that exposes the need for this split function with generic IR that would be really helpful I think - LLVM has managed for a long time without needing this split function so something has changed. I suspect it's probably just the new intrinsic that now exposes this code path.

Personally I think using the intrinsic as the test is better than trying to rely on an exact sequence of unluckiness to generate the failure.

For information I believe scalable vectors is what has changed. Specifically the changes we've made to INSERT_SUBVECTOR to allow a fixed-length vector to be extracted from/inserted into a scalable vector. Before this you'd only ever insert "fixed into fixed" or "scalable into scalable". Given the nature of INSERT_SUBVECTOR the operand is always smaller than the result and thus if the operand type is illegal then the result type must also be illegal, in which case SplitVecRes_INSERT_SUBVECTOR will handle type legalisation. However by allowing mixed vector types we've opened up the possibility for extracting an illegal vector type, that requires splitting to be made legal, from a legal one.

[david-arm]

HI @paulwalker-arm, right that makes sense and thanks for the explanation!

[paulwalker-arm]

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

2287–2291

Is this protection necessary? From what I can see the code below should work for all valid forms of INSERT_SUBVECTOR. That's to say you don't need to worry about the case of inserting a scalable vector into a fixed length vector because that is not a valid use of INSERT_SUBVECTOR and thus should be caught before getting here.

llvm/test/CodeGen/AArch64/split-vector-insert.ll

54

Is this required? I'm wondering if simply passing the subvector as a function parameter (or loading it from memory) and returning the scalable result directly, leads to a simpler test.

[paulwalker-arm]

llvm/test/CodeGen/AArch64/split-vector-insert.ll

2

This RUN line requires an asserts build so the test will need ; REQUIRES: asserts . However, for what it's worth it seems overkill to test both the code generation output and the result of the legaliser with generally the assembler output from llc usually being enough.

[joechrisellis]

Add more tests, address @paulwalker-arm and @david-arm's review comments.

[joechrisellis]

Remove unneeded files.

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

2287–2291

It might not be necessary, but since SplitVecOp_EXTRACT_SUBVECTOR has a similar check I would like to keep this for the time being!

llvm/test/CodeGen/AArch64/split-vector-insert.ll

2

I've added the ; REQUIRES: asserts line. I am a little reluctant to remove the legaliser checks because without them it is not clear we are testing SplitVecOp_INSERT_SUBVECTOR?

6

Done for floating point vectors -- I also tried to hit this codepath with predicate vectors but couldn't find a test case that works. Please ping if you think this is something we definitely need! 😄

54

I think it is necessary. I did try to simplify this test further, but didn't get anywhere. FWIW, calls to SplitVecOp_INSERT_SUBVECTOR seem to be very rare. I was unable to write a test by hand that exercised this codepath -- I actually got this test by using creduce + bugpoint to reduce a failure we had in a project that uses the ACLE.

It seems that simpler examples, like what you suggest, allow the compiler to factor out the INSERT_SUBVECTOR ISD node earlier on.

[paulwalker-arm]

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

2287–2291

I believe in SplitVecOp_EXTRACT_SUBVECTOR's case there is a check for a legitimate scenario that if hit may require an update to the function. However, in your instance the check is simply validating the DAG, which is not necessary because that's the job of SelectionDAG::getNode, of which I can see:

assert((VT.isScalableVector() || N2VT.isFixedLengthVector()) &&                 
           "Cannot insert a scalable vector into a fixed length vector!");

So unless the check serves a different purpose the code looks redundant and redundant code should be removed. I guess if you are super paranoid you could replicate SelectionDAG::getNode's assert but I really don't see the need.

[joechrisellis]

Remove redudant check for valid INSERTION_SUBVECTOR ISD node.

[joechrisellis]

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

2287–2291

Ahh okay, that makes sense -- my bad! Will remove this check. 🙂

[joechrisellis]

Simplify test.

[paulwalker-arm]

A few stylistic things to consider (I'm only really bothered about loosing the v32 tests) but otherwise looks good.

llvm/test/CodeGen/AArch64/split-vector-insert.ll

2

It's up to you but I prefer to keep RUN lines minimal so:

-o - is not needed as that is the default when redirecting files into llc,
-mtriple=aarch64-- can be replaced with target triple = "aarch64-unknown-linux-gnu"
-mcpu=a64fx can be replaced with a function attribute attributes #0 = { "target-features"="+sve" } remembering to reference #0 in the function definitions.

3

Again your choice, but you could drop this then just use CHECK for the code generation validation, which is more in keeping with the majority of the code generation tests.

117

I don't believe this and the other v32 test offers any value. The v8 tests are already testing nested (two levels) type legalisation, so there's no reason to test it again at four levels. Add this to the fact the generated code it pretty unreadable I recommend removing them.

[joechrisellis]

Address @paulwalker-arm's style comments.

[joechrisellis]

Thanks for the comments! 😄

[paulwalker-arm]

llvm/test/CodeGen/AArch64/split-vector-insert.ll

3

--check-prefix=CHECK is not needed as it's the default when no --check-prefix is specified.

[joechrisellis]

Remove redundant --check-prefix=CHECK.

llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.h

private:
   bool SplitVectorOperand(SDNode *N, unsigned OpNo);
   SDValue SplitVecOp_VSELECT(SDNode *N, unsigned OpNo);
   SDValue SplitVecOp_VECREDUCE(SDNode *N, unsigned OpNo);
   SDValue SplitVecOp_VECREDUCE_SEQ(SDNode *N);
   SDValue SplitVecOp_UnaryOp(SDNode *N);
   SDValue SplitVecOp_TruncateHelper(SDNode *N);
 
   SDValue SplitVecOp_BITCAST(SDNode *N);
+  SDValue SplitVecOp_INSERT_SUBVECTOR(SDNode *N, unsigned OpNo);
   SDValue SplitVecOp_EXTRACT_SUBVECTOR(SDNode *N);
   SDValue SplitVecOp_EXTRACT_VECTOR_ELT(SDNode *N);
   SDValue SplitVecOp_ExtVecInRegOp(SDNode *N);
   SDValue SplitVecOp_STORE(StoreSDNode *N, unsigned OpNo);
   SDValue SplitVecOp_MSTORE(MaskedStoreSDNode *N, unsigned OpNo);
   SDValue SplitVecOp_MSCATTER(MaskedScatterSDNode *N, unsigned OpNo);
   SDValue SplitVecOp_MGATHER(MaskedGatherSDNode *MGT, unsigned OpNo);
   SDValue SplitVecOp_CONCAT_VECTORS(SDNode *N);

llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

#ifndef NDEBUG
     dbgs() << "\n";
 #endif
     report_fatal_error("Do not know how to split this operator's "
                        "operand!\n");
 
   case ISD::SETCC:             Res = SplitVecOp_VSETCC(N); break;
   case ISD::BITCAST:           Res = SplitVecOp_BITCAST(N); break;
   case ISD::EXTRACT_SUBVECTOR: Res = SplitVecOp_EXTRACT_SUBVECTOR(N); break;
+  case ISD::INSERT_SUBVECTOR:  Res = SplitVecOp_INSERT_SUBVECTOR(N, OpNo); break;
   case ISD::EXTRACT_VECTOR_ELT:Res = SplitVecOp_EXTRACT_VECTOR_ELT(N); break;
   case ISD::CONCAT_VECTORS:    Res = SplitVecOp_CONCAT_VECTORS(N); break;
   case ISD::TRUNCATE:
     Res = SplitVecOp_TruncateHelper(N);
     break;
   case ISD::STRICT_FP_ROUND:
   case ISD::FP_ROUND:          Res = SplitVecOp_FP_ROUND(N); break;
   case ISD::FCOPYSIGN:         Res = SplitVecOp_FCOPYSIGN(N); break;
SDValue DAGTypeLegalizer::SplitVecOp_BITCAST(SDNode *N) {
 
   if (DAG.getDataLayout().isBigEndian())
     std::swap(Lo, Hi);
 
   return DAG.getNode(ISD::BITCAST, SDLoc(N), N->getValueType(0),
                      JoinIntegers(Lo, Hi));
 }
 
+SDValue DAGTypeLegalizer::SplitVecOp_INSERT_SUBVECTOR(SDNode *N,
+                                                      unsigned OpNo) {
+  assert(OpNo == 1 && "Invalid OpNo; can only split SubVec.");
+  // We know that the result type is legal.
+  EVT ResVT = N->getValueType(0);
+
+  if (ResVT.isFixedLengthVector() &&
+      N->getOperand(0).getValueType().isFixedLengthVector() &&
+      N->getOperand(1).getValueType().isScalableVector())
+    report_fatal_error("Inserting a scalable vector into a fixed-length vector "
+                       "is not yet supported. ");
+
+  SDValue Vec = N->getOperand(0);
+  SDValue SubVec = N->getOperand(1);
+  SDValue Idx = N->getOperand(2);
+  SDLoc dl(N);
+
+  SDValue Lo, Hi;
+  GetSplitVector(SubVec, Lo, Hi);
+
+  uint64_t IdxVal = cast<ConstantSDNode>(Idx)->getZExtValue();
+  uint64_t LoElts = Lo.getValueType().getVectorMinNumElements();
+
+  SDValue FirstInsertion =
+      DAG.getNode(ISD::INSERT_SUBVECTOR, dl, ResVT, Vec, Lo, Idx);
+  SDValue SecondInsertion =
+      DAG.getNode(ISD::INSERT_SUBVECTOR, dl, ResVT, FirstInsertion, Hi,
+                  DAG.getVectorIdxConstant(IdxVal + LoElts, dl));
+
+  return SecondInsertion;
+}
+
 SDValue DAGTypeLegalizer::SplitVecOp_EXTRACT_SUBVECTOR(SDNode *N) {
   // We know that the extracted result type is legal.
   EVT SubVT = N->getValueType(0);
 
   if (SubVT.isScalableVector() !=
       N->getOperand(0).getValueType().isScalableVector())
     report_fatal_error("Extracting fixed from scalable not implemented");
 

llvm/test/CodeGen/AArch64/split-vector-insert.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -o - -mtriple=aarch64-- -mcpu=a64fx -debug-only=legalize-types 2>&1 | FileCheck %s --check-prefix=CHECK-LEGALIZATION
+; RUN: llc < %s -o - -mtriple=aarch64-- -mcpu=a64fx | FileCheck %s --check-prefix=CHECK-CODEGEN
+
+declare void @_Z5svtblu12__SVUint64_tu12__SVUint64_t(<vscale x 2 x i64>, <vscale x 2 x i64>)
+declare <vscale x 2 x i64> @llvm.experimental.vector.insert.nxv2i64.v8i64(<vscale x 2 x i64>, <8 x i64>, i64)
+
+define void @foo() {
+; CHECK-LEGALIZATION: Legally typed node: [[T1:t[0-9]+]]: nxv2i64 = insert_subvector undef:nxv2i64, [[T2:t[0-9]+]], Constant:i64<0>
+; CHECK-LEGALIZATION: Legally typed node: [[T3:t[0-9]+]]: nxv2i64 = insert_subvector [[T1]], [[T2]], Constant:i64<2>
+; CHECK-LEGALIZATION: Legally typed node: [[T4:t[0-9]+]]: nxv2i64 = insert_subvector [[T3]], [[T2]], Constant:i64<4>
+; CHECK-LEGALIZATION: Legally typed node: [[T5:t[0-9]+]]: nxv2i64 = insert_subvector [[T4]], [[T2]], Constant:i64<6>
+
+; CHECK-CODEGEN-LABEL: foo:
+; CHECK-CODEGEN:       // %bb.0:
+; CHECK-CODEGEN-NEXT:    stp x29, x30, [sp, #-16]! // 16-byte Folded Spill
+; CHECK-CODEGEN-NEXT:    addvl sp, sp, #-3
+; CHECK-CODEGEN-NEXT:    .cfi_escape 0x0f, 0x0c, 0x8f, 0x00, 0x11, 0x10, 0x22, 0x11, 0x18, 0x92, 0x2e, 0x00, 0x1e, 0x22 // sp + 16 + 24 * VG
+; CHECK-CODEGEN-NEXT:    .cfi_offset w30, -8
+; CHECK-CODEGEN-NEXT:    .cfi_offset w29, -16
+; CHECK-CODEGEN-NEXT:    cntd x9
+; CHECK-CODEGEN-NEXT:    sub x9, x9, #1 // =1
+; CHECK-CODEGEN-NEXT:    mov w8, #2
+; CHECK-CODEGEN-NEXT:    cmp x9, #2 // =2
+; CHECK-CODEGEN-NEXT:    csel x8, x9, x8, lo
+; CHECK-CODEGEN-NEXT:    movi v0.2d, #0000000000000000
+; CHECK-CODEGEN-NEXT:    ptrue p0.d
+; CHECK-CODEGEN-NEXT:    mov x10, sp
+; CHECK-CODEGEN-NEXT:    lsl x8, x8, #3
+; CHECK-CODEGEN-NEXT:    st1d { z0.d }, p0, [sp]
+; CHECK-CODEGEN-NEXT:    str q0, [x10, x8]
+; CHECK-CODEGEN-NEXT:    addvl x10, sp, #1
+; CHECK-CODEGEN-NEXT:    ld1d { z1.d }, p0/z, [sp]
+; CHECK-CODEGEN-NEXT:    mov w8, #4
+; CHECK-CODEGEN-NEXT:    cmp x9, #4 // =4
+; CHECK-CODEGEN-NEXT:    csel x8, x9, x8, lo
+; CHECK-CODEGEN-NEXT:    lsl x8, x8, #3
+; CHECK-CODEGEN-NEXT:    st1d { z1.d }, p0, [sp, #1, mul vl]
+; CHECK-CODEGEN-NEXT:    str q0, [x10, x8]
+; CHECK-CODEGEN-NEXT:    addvl x10, sp, #2
+; CHECK-CODEGEN-NEXT:    ld1d { z1.d }, p0/z, [sp, #1, mul vl]
+; CHECK-CODEGEN-NEXT:    mov w8, #6
+; CHECK-CODEGEN-NEXT:    cmp x9, #6 // =6
+; CHECK-CODEGEN-NEXT:    csel x8, x9, x8, lo
+; CHECK-CODEGEN-NEXT:    lsl x8, x8, #3
+; CHECK-CODEGEN-NEXT:    st1d { z1.d }, p0, [sp, #2, mul vl]
+; CHECK-CODEGEN-NEXT:    str q0, [x10, x8]
+; CHECK-CODEGEN-NEXT:    ld1d { z1.d }, p0/z, [sp, #2, mul vl]
+; CHECK-CODEGEN-NEXT:    bl _Z5svtblu12__SVUint64_tu12__SVUint64_t
+; CHECK-CODEGEN-NEXT:    addvl sp, sp, #3
+; CHECK-CODEGEN-NEXT:    ldp x29, x30, [sp], #16 // 16-byte Folded Reload
+; CHECK-CODEGEN-NEXT:    ret
+  %castScalableSve = call <vscale x 2 x i64> @llvm.experimental.vector.insert.nxv2i64.v8i64(<vscale x 2 x i64> undef, <8 x i64> zeroinitializer, i64 0)
+  call void @_Z5svtblu12__SVUint64_tu12__SVUint64_t(<vscale x 2 x i64> undef, <vscale x 2 x i64> %castScalableSve)
+  ret void
+}