[RISCV] Model interleave and deinterleave shuffles in cost model

[luke]

Summary

Interleave and deinterleave shuffles are lowered by a more efficient
sequence if the element size is smaller than ELEN.

[luke]

Don't count cost of li

[luke]

Don't count cost of li

[luke]

llvm/test/Analysis/CostModel/RISCV/shuffle-interleave.ll

44

The motivation behind this patch is to use this shuffle cost for the cost of an interleaved memory access, so the shuffles in this test case are the same as the ones generated by the loop vectorizer.

Unfortunately, because these shuffles change the length of the vector, TargetTransformImpl.h returns -1 in getInstructionCost:

case Instruction::ShuffleVector: {
  auto *Shuffle = dyn_cast<ShuffleVectorInst>(U);
  // ...

  if (Shuffle->changesLength()) {
   // ...
    return CostKind == TTI::TCK_RecipThroughput ? -1 : 1;
  }

Which makes it difficult to test. Any ideas here?

[luke]

llvm/lib/Target/RISCV/RISCVTargetTransformInfo.cpp

340

I excluded the li here since in loops it's an invariant that's hoisted out. Do we still need to be pessimistic and include it here?

[luke]

Split test out to precommit test case

[reames]

Very close to LGTM, please apply changes and I think we're good to go.

llvm/lib/Target/RISCV/RISCVTargetTransformInfo.cpp

331

I think that LT.second must be fixed if the original type was. Turn this into an assert?

337

You need to check that Mask[0] is either 0 or 1 here. (Or generalize the lowering.)

343

Creating the masks just to check them this way is a bit inefficient. I'm fine with this landing as is, but we probably need to generalize out isInterleaveMask utilities. We already have that code in the lowering, so this is at least our second copy.

Follow up change is fine.

llvm/test/Analysis/CostModel/RISCV/shuffle-interleave.ll

17

This cost is also suspiciously high. This really should be a single slideup. Yet another follow on change. :)

44

Seems like we need to make a change to generic code and TTI interface. There's no reason we shouldn't be costing length changing shuffles.

A generic means would be to model a non-length changing shuffle followed by a vector insert or extract.

This is definite a separate change.

[luke]

llvm/lib/Target/RISCV/RISCVTargetTransformInfo.cpp

331

I thought so too, but <2 x i64> can get scalarized to i64 on zve32x! The zve32x test case in https://reviews.llvm.org/D145697 exercises this

343

I agree, I was hoping there would be something equivalent to isReverse()/isTransposeMask() in ShuffleVectorInst.
I was also wondering if there should also be a dedicated ShuffleKind for this like SK_[DE]INTERLEAVE.

[luke]

llvm/test/Analysis/CostModel/RISCV/shuffle-interleave.ll

17

If you stick this into llc then the shuffle actually disappears entirely.
We could try and model concatenating shuffles, but I think this is also blocked on the comment below

[reames]

llvm/lib/Target/RISCV/RISCVTargetTransformInfo.cpp

337

This remains open. This is the only blocking item.

[luke]

Check mask[0] != 0 | 1

[luke]

Check mask[0] != 0 | 1

[luke]

llvm/lib/Target/RISCV/RISCVTargetTransformInfo.cpp

337

Sorry for the delay, was wrestling with arc

[reames]

LGTM

llvm/lib/Target/RISCV/RISCVTargetTransformInfo.cpp

 //===-- RISCVTargetTransformInfo.cpp - RISC-V specific TTI ----------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "RISCVTargetTransformInfo.h"
 #include "MCTargetDesc/RISCVMatInt.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/VectorUtils.h"
 #include "llvm/CodeGen/BasicTTIImpl.h"
 #include "llvm/CodeGen/CostTable.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include <cmath>
 #include <optional>
 using namespace llvm;
 
 #define DEBUG_TYPE "riscvtti"
if (isa<FixedVectorType>(Tp) && Kind == TargetTransformInfo::SK_Broadcast) {
 
     // Example sequence:
     //   vrgather.vi     v9, v8, 0
     // TODO: vrgather could be slower than vmv.v.x. It is
     // implementation-dependent.
     return LT.first * getLMULCost(LT.second);
   }
 
+  if (isa<FixedVectorType>(Tp) && Kind == TTI::SK_PermuteSingleSrc &&
+      Mask.size() >= 2) {
+    std::pair<InstructionCost, MVT> LT = getTypeLegalizationCost(Tp);
+    MVT EltTp = LT.second.getVectorElementType();
+    // If the size of the element is < ELEN then shuffles of interleaves and
+    // deinterleaves of 2 vectors can be lowered into the following sequences
+    if (EltTp.getScalarSizeInBits() < ST->getELEN()) {
+      auto InterleaveMask = createInterleaveMask(Mask.size() / 2, 2);
+      auto DeinterleaveMask = createStrideMask(Mask[0], 2, Mask.size());
+      // Example sequence:
+      //   vsetivli zero, 4, e8, mf4, ta, ma (ignored)
+      //   vwaddu.vv  v10, v8, v9
+      //   li   a0, -1
+      //   vwmaccu.vx v10, a0, v9
+      //   vmv1r.v  v8, v10
+      if (equal(InterleaveMask, Mask))
+        return 4 * LT.first * getLMULCost(LT.second);
+
+      // Example sequence:
+      //   vnsrl.wi v10, v8, 0
+      if (equal(DeinterleaveMask, Mask))
+        return LT.first * getLMULCost(LT.second);
+    }
+  }
+
   return BaseT::getShuffleCost(Kind, Tp, Mask, CostKind, Index, SubTp);
 }
 
 InstructionCost
 RISCVTTIImpl::getMaskedMemoryOpCost(unsigned Opcode, Type *Src, Align Alignment,
                                     unsigned AddressSpace,
                                     TTI::TargetCostKind CostKind) {
   if (!isLegalMaskedLoadStore(Src, Alignment) ||

llvm/test/Analysis/CostModel/RISCV/shuffle-interleave.ll

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
+; RUN: opt < %s -passes="print<cost-model>" 2>&1 -disable-output -mtriple=riscv32 -mattr=+v | FileCheck %s -check-prefixes=CHECK,RV32
+; RUN: opt < %s -passes="print<cost-model>" 2>&1 -disable-output -mtriple=riscv64 -mattr=+v | FileCheck %s -check-prefixes=CHECK,RV64
+define <8 x i8> @interleave2_v8i8(<4 x i8> %v0, <4 x i8> %v1) {
+; CHECK-LABEL: 'interleave2_v8i8'
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 15 for instruction: %concat = shufflevector <4 x i8> %v0, <4 x i8> %v1, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 4 for instruction: %res = shufflevector <8 x i8> %concat, <8 x i8> poison, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: ret <8 x i8> %res
+;
+  %concat = shufflevector <4 x i8> %v0, <4 x i8> %v1, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+  %res = shufflevector <8 x i8> %concat, <8 x i8> poison, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+  ret <8 x i8> %res
+}
+
+define <8 x i32> @interleave2_v8i32(<4 x i32> %v0, <4 x i32> %v1) {
+; CHECK-LABEL: 'interleave2_v8i32'
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 15 for instruction: %concat = shufflevector <4 x i32> %v0, <4 x i32> %v1, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 8 for instruction: %res = shufflevector <8 x i32> %concat, <8 x i32> poison, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: ret <8 x i32> %res
+;
+  %concat = shufflevector <4 x i32> %v0, <4 x i32> %v1, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+  %res = shufflevector <8 x i32> %concat, <8 x i32> poison, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+  ret <8 x i32> %res
+}
+
+; Should be expensive on RV32 because it can't widen
+define <8 x i64> @interleave2_v8i64(<4 x i64> %v0, <4 x i64> %v1) {
+; RV32-LABEL: 'interleave2_v8i64'
+; RV32-NEXT:  Cost Model: Found an estimated cost of 35 for instruction: %concat = shufflevector <4 x i64> %v0, <4 x i64> %v1, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+; RV32-NEXT:  Cost Model: Found an estimated cost of 70 for instruction: %res = shufflevector <8 x i64> %concat, <8 x i64> poison, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+; RV32-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: ret <8 x i64> %res
+;
+; RV64-LABEL: 'interleave2_v8i64'
+; RV64-NEXT:  Cost Model: Found an estimated cost of 15 for instruction: %concat = shufflevector <4 x i64> %v0, <4 x i64> %v1, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+; RV64-NEXT:  Cost Model: Found an estimated cost of 30 for instruction: %res = shufflevector <8 x i64> %concat, <8 x i64> poison, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+; RV64-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: ret <8 x i64> %res
+;
+  %concat = shufflevector <4 x i64> %v0, <4 x i64> %v1, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+  %res = shufflevector <8 x i64> %concat, <8 x i64> poison, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+  ret <8 x i64> %res
+}
+
+; TODO: getInstructionCost doesn't call getShuffleCost here because the shuffle changes length
+define {<4 x i8>, <4 x i8>} @deinterleave_2(<8 x i8> %v) {
+; CHECK-LABEL: 'deinterleave_2'
+; CHECK-NEXT:  Cost Model: Found an estimated cost of -1 for instruction: %v0 = shufflevector <8 x i8> %v, <8 x i8> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of -1 for instruction: %v1 = shufflevector <8 x i8> %v, <8 x i8> poison, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+; CHECK-NEXT:  Cost Model: Found an estimated cost of -1 for instruction: %res0 = insertvalue { <4 x i8>, <4 x i8> } poison, <4 x i8> %v0, 0
+; CHECK-NEXT:  Cost Model: Found an estimated cost of -1 for instruction: %res1 = insertvalue { <4 x i8>, <4 x i8> } %res0, <4 x i8> %v1, 1
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: ret { <4 x i8>, <4 x i8> } %res1
+;
+  %v0 = shufflevector <8 x i8> %v, <8 x i8> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %v1 = shufflevector <8 x i8> %v, <8 x i8> poison, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %res0 = insertvalue {<4 x i8>, <4 x i8>} poison, <4 x i8> %v0, 0
+  %res1 = insertvalue {<4 x i8>, <4 x i8>} %res0, <4 x i8> %v1, 1
+  ret {<4 x i8>, <4 x i8>} %res1
+}