1//===------- SVEShuffleOpts - SVE Shuffle Optimization --------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Tries to pattern match and combine scalable vector shuffles that could
10// be more efficiently performed by tbl instructions.
11//
12// An example would be a loop with 4 multiply-accumulate reductions, where the
13// new data in each vector iterations comes from a 4-way deinterleaving of
14// smaller datatypes loaded from memory which are then zero extended.
15//
16// Something like the following:
17// %bgra = call ... @llvm.masked.load
18// %deinterleave = call ... @llvm.vector.deinterleave4(%bgra)
19// If the load was of a <vscale x 8 x i16>, we now have 4 deinterleaved
20// <vscale x 2 x i16> values.
21// %b.i16 = extractvalue %deinterleave, 0
22// %b.i64 = zext <vscale x 2 x i16> %b.i16 to <vscale x 2 x i64>
23// %acc.b.next = add <vscale x 2 x i64> %acc.b, %b.i64
24// <repeat for the other 3 subvectors>
25//
26// If the initial load is a legal vector rather than 4x the size (generating a
27// structured ld4 instead), we would see multiple uunpkhi/lo instructions for
28// the extensions, followed by uzp1/2 instructions for the deinterleave.
29// Instead, we can replace all of those with 4 tbl instructions. The tradeoff,
30// of course, is that we now have 4 mask values to maintain which may increase
31// register pressure.
32//
33// This basic transform could be performed in CodeGenPrepare (as the equivalent
34// for NEON is), or in a DAG Combine. However, we hope to extend it to detect
35// other shuffles that we can fold into the tbl. Extending the above example,
36// if instead of directly adding to the accumulator we multiplied it by a
37// common term for all 4 components that had been reversed:
38// %common.load = call @llvm.masked.load
39// %common.reverse = call @llvm.vector.reverse
40// These would be loaded at the extended size, <vscale x 2 x i64> in our
41// example.
42// %b.mul = mul <vscale x 2 x i64> %b.i64, %common.reverse
43// %acc.b.next = add <vscale x 2 x i64> %acc.b, %b.mul
44// <repeat for the other 3 subvectors, using %common.reverse for each)
45//
46// In this case, the reverse isn't applied to the deinterleaved data in the
47// original IR, but to the common term multiplied by the individual bgra
48// elements. If the order of the elements in the accumulator is important, we
49// cannot change that. If, however, we know that the accumulator is reduced to
50// a single scalar after the loop and the data is either integers or floating
51// point with reassociation allowed, we could instead choose a different mask
52// for the tbls to reverse the individual bgra elements instead, removing an
53// additional instruction from the loop. This does require looking beyond the
54// blocks in the loop, so DAGCombine won't help.
55//
56// We should also be able to introduce new shuffles in order to balance out
57// SVE's bottom/top instruction pairs, which act on even/odd lanes instead of
58// the high or low half of a register.
59//
60// This pass may end up being a temporary solution that is removed if we can
61// create a generic vector shuffle intrinsic and move this feature to
62// LoopVectorize itself, as that would allow for better cost modelling.
63//
64//===----------------------------------------------------------------------===//
65
66#include "AArch64.h"
67#include "AArch64Subtarget.h"
68#include "AArch64TargetMachine.h"
69#include "llvm/Analysis/AssumptionCache.h"
70#include "llvm/Analysis/LoopInfo.h"
71#include "llvm/Analysis/LoopPass.h"
72#include "llvm/Analysis/MemorySSA.h"
73#include "llvm/Analysis/TargetTransformInfo.h"
74#include "llvm/Analysis/ValueTracking.h"
75#include "llvm/CodeGen/TargetLowering.h"
76#include "llvm/CodeGen/TargetPassConfig.h"
77#include "llvm/CodeGen/TargetSubtargetInfo.h"
78#include "llvm/IR/Constants.h"
79#include "llvm/IR/IRBuilder.h"
80#include "llvm/IR/Instructions.h"
81#include "llvm/IR/IntrinsicInst.h"
82#include "llvm/IR/IntrinsicsAArch64.h"
83#include "llvm/IR/LLVMContext.h"
84#include "llvm/IR/PatternMatch.h"
85#include "llvm/InitializePasses.h"
86#include <array>
87
88using namespace llvm;
89using namespace llvm::PatternMatch;
90
91#define DEBUG_TYPE "aarch64-sve-shuffle-opts"
92
93/// A mapping between a vector_deinterleaveN intrinsic and extending cast
94/// instructions used on the resulting subvectors.
95using DeinterleaveMap = SmallDenseMap<CallInst *, std::array<CastInst *, 4>>;
96
97/// Evaluate a deinterleave and see what the uses are. If we find other
98/// operations that we can combine into a tbl shuffle, add the deinterleave and
99/// the operations (currently only zext or uitofp) to the candidates map.
100static void evaluateDeinterleave(IntrinsicInst *I, DeinterleaveMap &Candidates,
101 Loop &L, const AArch64TargetLowering &TL,
102 const DataLayout DL) {
103 assert(I->getIntrinsicID() == Intrinsic::vector_deinterleave4 &&
104 "Only deinterleave4 supported currently");
105
106 ConstantRange VScaleRange = getVScaleRange(F: I->getFunction(), BitWidth: 64);
107 // TBL zeroes elements with an out-of-bounds index, but for the largest
108 // possible SVE vector (2048b) the maximum value for i8 elements (255) is not
109 // large enough to encode an 'out of bounds' value. So we can only perform
110 // this optimization for i8 elements if we know vscale is < 16.
111 EVT InputVT = TL.getValueType(DL, Ty: I->getOperand(i_nocapture: 0)->getType());
112 if (!InputVT.isScalableVector() ||
113 (InputVT.getScalarSizeInBits() < 16 &&
114 (!VScaleRange.getUpper().ult(RHS: 16) || VScaleRange.isUpperWrapped())) ||
115 TL.getTypeConversion(Context&: I->getContext(), VT: InputVT).first !=
116 TargetLoweringBase::TypeLegal)
117 return;
118
119 std::array<CastInst *, 4> Extends = {};
120 unsigned Opcode = 0;
121 Type *DestTy = nullptr;
122 for (User *U : I->users()) {
123 auto *Extract = dyn_cast<ExtractValueInst>(Val: U);
124 if (!Extract || !Extract->hasOneUse())
125 return;
126
127 // We expect only a single cast instruction as a user for the extract.
128 auto *Extend = dyn_cast_if_present<CastInst>(Val: *Extract->users().begin());
129 if (!Extend || (!isa<ZExtInst>(Val: Extend) && !isa<UIToFPInst>(Val: Extend)))
130 return;
131
132 // We're only interested if the uses are in the loop. This is almost
133 // certainly the case.
134 if (!L.contains(Inst: Extend))
135 return;
136
137 Opcode = Extend->getOpcode();
138 DestTy = Extend->getDestTy();
139
140 // Make sure DestTy matches the input size.
141 if (DestTy->getPrimitiveSizeInBits() != InputVT.getSizeInBits())
142 return;
143
144 Extends[Extract->getIndices().front()] = Extend;
145 }
146
147 // Check that all extracted values are being extended the same way, and that
148 // we have the expected number of extensions.
149 if (!all_of(Range&: Extends, P: [DestTy, Opcode](CastInst *CI) {
150 return !CI || (CI->getDestTy() == DestTy && CI->getOpcode() == Opcode);
151 }))
152 return;
153
154 Candidates.try_emplace(Key: I, Args&: Extends);
155}
156
157/// Given a map of deinterleaves to zext or uitofp casts, remove the operations
158/// and replace them with tbl shuffles.
159static void optimizeSVEDeinterleavedExtends(DeinterleaveMap Deinterleaves) {
160 for (auto &[Deinterleave, Extends] : Deinterleaves) {
161 VectorType *DestTy = cast<VectorType>(Val: Extends[0]->getDestTy());
162 VectorType *SrcTy = cast<VectorType>(Val: Extends[0]->getSrcTy());
163 unsigned DstBits = DestTy->getScalarSizeInBits();
164 unsigned SrcBits = SrcTy->getScalarSizeInBits();
165 bool IsUIToFP = isa<UIToFPInst>(Val: Extends[0]);
166 VectorType *StepVecTy = VectorType::getInteger(VTy: DestTy);
167 Value *Input = Deinterleave->getOperand(i_nocapture: 0);
168 Type *InputTy = Input->getType();
169
170 APInt Invalid = APInt::getAllOnes(numBits: DstBits);
171 for (auto [Idx, Extend] : enumerate(First&: Extends)) {
172 // If not all lanes were extracted, we can have gaps. Skip over them.
173 if (!Extend)
174 continue;
175 // Build the mask using stepvectors and casting.
176 // We want to select the Idx'th element, and every 4 elements after that.
177 // Each element needs to be zero extended; we can do that by providing
178 // tbl index values that are out of range. We can't do that nicely with
179 // a stepvector of the same element type as the input type, but we can
180 // do it with elements the size of the output type.
181 // E.g. for element 0 of a 16b -> 64b zext, we would start with a mask of
182 // 0xFFFF_FFFF_FFFF_0000 + Idx for the start of the stepvector, and use a
183 // step of 4. We then cast that back to an element size of 16b, yielding
184 // <0x0000 + Idx, 0xFFFF, 0xFFFF, 0xFFFF, 0x0004 + Idx, 0xFFFF...>.
185 APInt StartIdx = Invalid << SrcBits;
186 StartIdx += Idx;
187 IRBuilder<> Builder(Extend);
188 Value *StepVector = Builder.CreateStepVector(DstType: StepVecTy);
189 Value *ScaledSteps =
190 Builder.CreateNUWMul(LHS: StepVector, RHS: ConstantInt::get(Ty: StepVecTy, V: 4));
191 Value *ZextTbl = Builder.CreateNUWAdd(
192 LHS: ScaledSteps, RHS: ConstantInt::get(Ty: StepVecTy, V: StartIdx));
193 Value *FinalMask = Builder.CreateBitCast(V: ZextTbl, DestTy: InputTy);
194
195 // Replace the deinterleave, extractvalue, and extension chain with
196 // a tbl directly on the input value.
197 Value *Tbl = Builder.CreateIntrinsic(ID: Intrinsic::aarch64_sve_tbl,
198 OverloadTypes: {InputTy}, Args: {Input, FinalMask});
199 Value *Widen = Builder.CreateBitCast(V: Tbl, DestTy: StepVecTy);
200 if (IsUIToFP)
201 Widen = Builder.CreateUIToFP(V: Widen, DestTy);
202 LLVM_DEBUG(dbgs() << "SVETBLOPT: Replaced " << *Extend << " with "
203 << *Widen << "\n");
204 Extend->replaceAllUsesWith(V: Widen);
205 Extend->eraseFromParent();
206 }
207
208 // Delete the unused extracts and deinterleave.
209 for (User *U : make_early_inc_range(Range: Deinterleave->users()))
210 cast<Instruction>(Val: U)->eraseFromParent();
211 Deinterleave->eraseFromParent();
212 }
213}
214
215static bool processLoop(Loop &L, const AArch64Subtarget &ST, DataLayout DL) {
216 // At present, we only want to do this for innermost loops when SVE
217 // is available.
218 if (!L.isInnermost() || !ST.isSVEorStreamingSVEAvailable())
219 return false;
220
221 // TODO: Pull other shuffles into the tbl where possible.
222 // TODO: Add more advanced cases, such as introducing shuffles so that
223 // the SVE odd/even BT narrowing instructions can be used.
224 // TODO: Support other deinterleaves.
225 const AArch64TargetLowering &TL = *ST.getTargetLowering();
226 assert(DL.isLittleEndian() &&
227 "Shuffle optimizations unsupported for big endian targets.");
228 DeinterleaveMap Candidates;
229 for (auto *BB : L.blocks())
230 for (auto &I : *BB)
231 if (match(V: &I, P: m_Intrinsic<Intrinsic::vector_deinterleave4>(Ops: m_Value())))
232 evaluateDeinterleave(I: cast<IntrinsicInst>(Val: &I), Candidates, L, TL, DL);
233
234 if (Candidates.empty())
235 return false;
236
237 optimizeSVEDeinterleavedExtends(Deinterleaves: Candidates);
238 return true;
239}
240
241namespace {
242struct SVEShuffleOpts : public LoopPass {
243 static char ID; // Pass identification, replacement for typeid
244 SVEShuffleOpts() : LoopPass(ID) {}
245
246 bool runOnLoop(Loop *L, LPPassManager &PM) override {
247 if (skipLoop(L))
248 return false;
249
250 TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
251 const AArch64TargetMachine &TM = TPC.getTM<AArch64TargetMachine>();
252 const Function *F = L->getHeader()->getParent();
253 const AArch64Subtarget &ST = *TM.getSubtargetImpl(F: *F);
254
255 return processLoop(L&: *L, ST, DL: F->getDataLayout());
256 }
257
258 void getAnalysisUsage(AnalysisUsage &AU) const override {
259 AU.addRequired<TargetPassConfig>();
260 AU.setPreservesCFG();
261 }
262
263 StringRef getPassName() const override { return "SVE Shuffle Optimizations"; }
264};
265} // end anonymous namespace
266
267char SVEShuffleOpts::ID = 0;
268static const char *name = "SVE Shuffle Optimizations";
269INITIALIZE_PASS_BEGIN(SVEShuffleOpts, DEBUG_TYPE, name, false, false)
270INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
271INITIALIZE_PASS_END(SVEShuffleOpts, DEBUG_TYPE, name, false, false)
272
273Pass *llvm::createSVEShuffleOptsPass() { return new SVEShuffleOpts(); }
274
275PreservedAnalyses
276AArch64SVEShuffleOptsPass::run(Loop &L, LoopAnalysisManager &AM,
277 LoopStandardAnalysisResults &AR, LPMUpdater &U) {
278 const Function *F = L.getHeader()->getParent();
279 const AArch64Subtarget &ST = *TM.getSubtargetImpl(F: *F);
280
281 if (processLoop(L, ST, DL: F->getDataLayout())) {
282 PreservedAnalyses PA;
283 PA.preserveSet<CFGAnalyses>();
284 PA.preserve<TargetIRAnalysis>();
285 PA.preserve<AssumptionAnalysis>();
286 PA.preserve<MemorySSAAnalysis>();
287 return PA;
288 }
289
290 return PreservedAnalyses::all();
291}
292