1//===- MVEGatherScatterLowering.cpp - Gather/Scatter lowering -------------===//
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/// This pass custom lowers llvm.gather and llvm.scatter instructions to
10/// arm.mve.gather and arm.mve.scatter intrinsics, optimising the code to
11/// produce a better final result as we go.
12//
13//===----------------------------------------------------------------------===//
14
15#include "ARM.h"
16#include "ARMBaseInstrInfo.h"
17#include "ARMSubtarget.h"
18#include "llvm/Analysis/LoopInfo.h"
19#include "llvm/Analysis/TargetTransformInfo.h"
20#include "llvm/Analysis/ValueTracking.h"
21#include "llvm/CodeGen/TargetLowering.h"
22#include "llvm/CodeGen/TargetPassConfig.h"
23#include "llvm/CodeGen/TargetSubtargetInfo.h"
24#include "llvm/IR/BasicBlock.h"
25#include "llvm/IR/Constant.h"
26#include "llvm/IR/Constants.h"
27#include "llvm/IR/DerivedTypes.h"
28#include "llvm/IR/Function.h"
29#include "llvm/IR/IRBuilder.h"
30#include "llvm/IR/InstrTypes.h"
31#include "llvm/IR/Instruction.h"
32#include "llvm/IR/Instructions.h"
33#include "llvm/IR/IntrinsicInst.h"
34#include "llvm/IR/Intrinsics.h"
35#include "llvm/IR/IntrinsicsARM.h"
36#include "llvm/IR/PatternMatch.h"
37#include "llvm/IR/Type.h"
38#include "llvm/IR/Value.h"
39#include "llvm/InitializePasses.h"
40#include "llvm/Pass.h"
41#include "llvm/Support/Casting.h"
42#include "llvm/Transforms/Utils/Local.h"
43#include <cassert>
44
45using namespace llvm;
46
47#define DEBUG_TYPE "arm-mve-gather-scatter-lowering"
48
49cl::opt<bool> EnableMaskedGatherScatters(
50 "enable-arm-maskedgatscat", cl::Hidden, cl::init(Val: true),
51 cl::desc("Enable the generation of masked gathers and scatters"));
52
53namespace {
54
55class MVEGatherScatterLowering : public FunctionPass {
56public:
57 static char ID; // Pass identification, replacement for typeid
58
59 explicit MVEGatherScatterLowering() : FunctionPass(ID) {
60 initializeMVEGatherScatterLoweringPass(*PassRegistry::getPassRegistry());
61 }
62
63 bool runOnFunction(Function &F) override;
64
65 StringRef getPassName() const override {
66 return "MVE gather/scatter lowering";
67 }
68
69 void getAnalysisUsage(AnalysisUsage &AU) const override {
70 AU.setPreservesCFG();
71 AU.addRequired<TargetPassConfig>();
72 AU.addRequired<LoopInfoWrapperPass>();
73 FunctionPass::getAnalysisUsage(AU);
74 }
75
76private:
77 LoopInfo *LI = nullptr;
78 const DataLayout *DL;
79
80 // Check this is a valid gather with correct alignment
81 bool isLegalTypeAndAlignment(unsigned NumElements, unsigned ElemSize,
82 Align Alignment);
83 // Check whether Ptr is hidden behind a bitcast and look through it
84 void lookThroughBitcast(Value *&Ptr);
85 // Decompose a ptr into Base and Offsets, potentially using a GEP to return a
86 // scalar base and vector offsets, or else fallback to using a base of 0 and
87 // offset of Ptr where possible.
88 Value *decomposePtr(Value *Ptr, Value *&Offsets, int &Scale,
89 FixedVectorType *Ty, Type *MemoryTy,
90 IRBuilder<> &Builder);
91 // Check for a getelementptr and deduce base and offsets from it, on success
92 // returning the base directly and the offsets indirectly using the Offsets
93 // argument
94 Value *decomposeGEP(Value *&Offsets, FixedVectorType *Ty,
95 GetElementPtrInst *GEP, IRBuilder<> &Builder);
96 // Compute the scale of this gather/scatter instruction
97 int computeScale(unsigned GEPElemSize, unsigned MemoryElemSize);
98 // If the value is a constant, or derived from constants via additions
99 // and multilications, return its numeric value
100 std::optional<int64_t> getIfConst(const Value *V);
101 // If Inst is an add instruction, check whether one summand is a
102 // constant. If so, scale this constant and return it together with
103 // the other summand.
104 std::pair<Value *, int64_t> getVarAndConst(Value *Inst, int TypeScale);
105
106 Instruction *lowerGather(IntrinsicInst *I);
107 // Create a gather from a base + vector of offsets
108 Instruction *tryCreateMaskedGatherOffset(IntrinsicInst *I, Value *Ptr,
109 Instruction *&Root,
110 IRBuilder<> &Builder);
111 // Create a gather from a vector of pointers
112 Instruction *tryCreateMaskedGatherBase(IntrinsicInst *I, Value *Ptr,
113 IRBuilder<> &Builder,
114 int64_t Increment = 0);
115 // Create an incrementing gather from a vector of pointers
116 Instruction *tryCreateMaskedGatherBaseWB(IntrinsicInst *I, Value *Ptr,
117 IRBuilder<> &Builder,
118 int64_t Increment = 0);
119
120 Instruction *lowerScatter(IntrinsicInst *I);
121 // Create a scatter to a base + vector of offsets
122 Instruction *tryCreateMaskedScatterOffset(IntrinsicInst *I, Value *Offsets,
123 IRBuilder<> &Builder);
124 // Create a scatter to a vector of pointers
125 Instruction *tryCreateMaskedScatterBase(IntrinsicInst *I, Value *Ptr,
126 IRBuilder<> &Builder,
127 int64_t Increment = 0);
128 // Create an incrementing scatter from a vector of pointers
129 Instruction *tryCreateMaskedScatterBaseWB(IntrinsicInst *I, Value *Ptr,
130 IRBuilder<> &Builder,
131 int64_t Increment = 0);
132
133 // QI gathers and scatters can increment their offsets on their own if
134 // the increment is a constant value (digit)
135 Instruction *tryCreateIncrementingGatScat(IntrinsicInst *I, Value *Ptr,
136 IRBuilder<> &Builder);
137 // QI gathers/scatters can increment their offsets on their own if the
138 // increment is a constant value (digit) - this creates a writeback QI
139 // gather/scatter
140 Instruction *tryCreateIncrementingWBGatScat(IntrinsicInst *I, Value *BasePtr,
141 Value *Ptr, unsigned TypeScale,
142 IRBuilder<> &Builder);
143
144 // Optimise the base and offsets of the given address
145 bool optimiseAddress(Value *Address, BasicBlock *BB, LoopInfo *LI);
146 // Try to fold consecutive geps together into one
147 Value *foldGEP(GetElementPtrInst *GEP, Value *&Offsets, unsigned &Scale,
148 IRBuilder<> &Builder);
149 // Check whether these offsets could be moved out of the loop they're in
150 bool optimiseOffsets(Value *Offsets, BasicBlock *BB, LoopInfo *LI);
151 // Pushes the given add out of the loop
152 void pushOutAdd(PHINode *&Phi, Value *OffsSecondOperand, unsigned StartIndex);
153 // Pushes the given mul or shl out of the loop
154 void pushOutMulShl(unsigned Opc, PHINode *&Phi, Value *IncrementPerRound,
155 Value *OffsSecondOperand, unsigned LoopIncrement,
156 IRBuilder<> &Builder);
157};
158
159} // end anonymous namespace
160
161char MVEGatherScatterLowering::ID = 0;
162
163INITIALIZE_PASS(MVEGatherScatterLowering, DEBUG_TYPE,
164 "MVE gather/scattering lowering pass", false, false)
165
166Pass *llvm::createMVEGatherScatterLoweringPass() {
167 return new MVEGatherScatterLowering();
168}
169
170bool MVEGatherScatterLowering::isLegalTypeAndAlignment(unsigned NumElements,
171 unsigned ElemSize,
172 Align Alignment) {
173 if (((NumElements == 4 &&
174 (ElemSize == 32 || ElemSize == 16 || ElemSize == 8)) ||
175 (NumElements == 8 && (ElemSize == 16 || ElemSize == 8)) ||
176 (NumElements == 16 && ElemSize == 8)) &&
177 Alignment >= ElemSize / 8)
178 return true;
179 LLVM_DEBUG(dbgs() << "masked gathers/scatters: instruction does not have "
180 << "valid alignment or vector type \n");
181 return false;
182}
183
184static bool checkOffsetSize(Value *Offsets, unsigned TargetElemCount) {
185 // Offsets that are not of type <N x i32> are sign extended by the
186 // getelementptr instruction, and MVE gathers/scatters treat the offset as
187 // unsigned. Thus, if the element size is smaller than 32, we can only allow
188 // positive offsets - i.e., the offsets are not allowed to be variables we
189 // can't look into.
190 // Additionally, <N x i32> offsets have to either originate from a zext of a
191 // vector with element types smaller or equal the type of the gather we're
192 // looking at, or consist of constants that we can check are small enough
193 // to fit into the gather type.
194 // Thus we check that 0 < value < 2^TargetElemSize.
195 unsigned TargetElemSize = 128 / TargetElemCount;
196 unsigned OffsetElemSize = cast<FixedVectorType>(Val: Offsets->getType())
197 ->getElementType()
198 ->getScalarSizeInBits();
199 if (OffsetElemSize != TargetElemSize || OffsetElemSize != 32) {
200 Constant *ConstOff = dyn_cast<Constant>(Val: Offsets);
201 if (!ConstOff)
202 return false;
203 int64_t TargetElemMaxSize = (1ULL << TargetElemSize);
204 auto CheckValueSize = [TargetElemMaxSize](Value *OffsetElem) {
205 ConstantInt *OConst = dyn_cast<ConstantInt>(Val: OffsetElem);
206 if (!OConst)
207 return false;
208 int SExtValue = OConst->getSExtValue();
209 if (SExtValue >= TargetElemMaxSize || SExtValue < 0)
210 return false;
211 return true;
212 };
213 if (isa<FixedVectorType>(Val: ConstOff->getType())) {
214 for (unsigned i = 0; i < TargetElemCount; i++) {
215 if (!CheckValueSize(ConstOff->getAggregateElement(Elt: i)))
216 return false;
217 }
218 } else {
219 if (!CheckValueSize(ConstOff))
220 return false;
221 }
222 }
223 return true;
224}
225
226Value *MVEGatherScatterLowering::decomposePtr(Value *Ptr, Value *&Offsets,
227 int &Scale, FixedVectorType *Ty,
228 Type *MemoryTy,
229 IRBuilder<> &Builder) {
230 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: Ptr)) {
231 if (Value *V = decomposeGEP(Offsets, Ty, GEP, Builder)) {
232 Scale =
233 computeScale(GEPElemSize: DL->getTypeAllocSizeInBits(Ty: GEP->getSourceElementType()),
234 MemoryElemSize: MemoryTy->getScalarSizeInBits());
235 return Scale == -1 ? nullptr : V;
236 }
237 }
238
239 // If we couldn't use the GEP (or it doesn't exist), attempt to use a
240 // BasePtr of 0 with Ptr as the Offsets, so long as there are only 4
241 // elements.
242 FixedVectorType *PtrTy = cast<FixedVectorType>(Val: Ptr->getType());
243 if (PtrTy->getNumElements() != 4 || MemoryTy->getScalarSizeInBits() == 32)
244 return nullptr;
245 Value *Zero = ConstantInt::get(Ty: Builder.getInt32Ty(), V: 0);
246 Value *BasePtr = Builder.CreateIntToPtr(V: Zero, DestTy: Builder.getPtrTy());
247 Offsets = Builder.CreatePtrToInt(
248 V: Ptr, DestTy: FixedVectorType::get(ElementType: Builder.getInt32Ty(), NumElts: 4));
249 Scale = 0;
250 return BasePtr;
251}
252
253Value *MVEGatherScatterLowering::decomposeGEP(Value *&Offsets,
254 FixedVectorType *Ty,
255 GetElementPtrInst *GEP,
256 IRBuilder<> &Builder) {
257 if (!GEP) {
258 LLVM_DEBUG(dbgs() << "masked gathers/scatters: no getelementpointer "
259 << "found\n");
260 return nullptr;
261 }
262 LLVM_DEBUG(dbgs() << "masked gathers/scatters: getelementpointer found."
263 << " Looking at intrinsic for base + vector of offsets\n");
264 Value *GEPPtr = GEP->getPointerOperand();
265 Offsets = GEP->getOperand(i_nocapture: 1);
266 if (GEPPtr->getType()->isVectorTy() ||
267 !isa<FixedVectorType>(Val: Offsets->getType()))
268 return nullptr;
269
270 if (GEP->getNumOperands() != 2) {
271 LLVM_DEBUG(dbgs() << "masked gathers/scatters: getelementptr with too many"
272 << " operands. Expanding.\n");
273 return nullptr;
274 }
275 Offsets = GEP->getOperand(i_nocapture: 1);
276 unsigned OffsetsElemCount =
277 cast<FixedVectorType>(Val: Offsets->getType())->getNumElements();
278 // Paranoid check whether the number of parallel lanes is the same
279 assert(Ty->getNumElements() == OffsetsElemCount);
280
281 ZExtInst *ZextOffs = dyn_cast<ZExtInst>(Val: Offsets);
282 if (ZextOffs)
283 Offsets = ZextOffs->getOperand(i_nocapture: 0);
284 FixedVectorType *OffsetType = cast<FixedVectorType>(Val: Offsets->getType());
285
286 // If the offsets are already being zext-ed to <N x i32>, that relieves us of
287 // having to make sure that they won't overflow.
288 if (!ZextOffs || cast<FixedVectorType>(Val: ZextOffs->getDestTy())
289 ->getElementType()
290 ->getScalarSizeInBits() != 32)
291 if (!checkOffsetSize(Offsets, TargetElemCount: OffsetsElemCount))
292 return nullptr;
293
294 // The offset sizes have been checked; if any truncating or zext-ing is
295 // required to fix them, do that now
296 if (Ty != Offsets->getType()) {
297 if ((Ty->getElementType()->getScalarSizeInBits() <
298 OffsetType->getElementType()->getScalarSizeInBits())) {
299 Offsets = Builder.CreateTrunc(V: Offsets, DestTy: Ty);
300 } else {
301 Offsets = Builder.CreateZExt(V: Offsets, DestTy: VectorType::getInteger(VTy: Ty));
302 }
303 }
304 // If none of the checks failed, return the gep's base pointer
305 LLVM_DEBUG(dbgs() << "masked gathers/scatters: found correct offsets\n");
306 return GEPPtr;
307}
308
309void MVEGatherScatterLowering::lookThroughBitcast(Value *&Ptr) {
310 // Look through bitcast instruction if #elements is the same
311 if (auto *BitCast = dyn_cast<BitCastInst>(Val: Ptr)) {
312 auto *BCTy = cast<FixedVectorType>(Val: BitCast->getType());
313 auto *BCSrcTy = cast<FixedVectorType>(Val: BitCast->getOperand(i_nocapture: 0)->getType());
314 if (BCTy->getNumElements() == BCSrcTy->getNumElements()) {
315 LLVM_DEBUG(dbgs() << "masked gathers/scatters: looking through "
316 << "bitcast\n");
317 Ptr = BitCast->getOperand(i_nocapture: 0);
318 }
319 }
320}
321
322int MVEGatherScatterLowering::computeScale(unsigned GEPElemSize,
323 unsigned MemoryElemSize) {
324 // This can be a 32bit load/store scaled by 4, a 16bit load/store scaled by 2,
325 // or a 8bit, 16bit or 32bit load/store scaled by 1
326 if (GEPElemSize == 32 && MemoryElemSize == 32)
327 return 2;
328 else if (GEPElemSize == 16 && MemoryElemSize == 16)
329 return 1;
330 else if (GEPElemSize == 8)
331 return 0;
332 LLVM_DEBUG(dbgs() << "masked gathers/scatters: incorrect scale. Can't "
333 << "create intrinsic\n");
334 return -1;
335}
336
337std::optional<int64_t> MVEGatherScatterLowering::getIfConst(const Value *V) {
338 const Constant *C = dyn_cast<Constant>(Val: V);
339 if (C && C->getSplatValue())
340 return std::optional<int64_t>{C->getUniqueInteger().getSExtValue()};
341 if (!isa<Instruction>(Val: V))
342 return std::optional<int64_t>{};
343
344 const Instruction *I = cast<Instruction>(Val: V);
345 if (I->getOpcode() == Instruction::Add || I->getOpcode() == Instruction::Or ||
346 I->getOpcode() == Instruction::Mul ||
347 I->getOpcode() == Instruction::Shl) {
348 std::optional<int64_t> Op0 = getIfConst(V: I->getOperand(i: 0));
349 std::optional<int64_t> Op1 = getIfConst(V: I->getOperand(i: 1));
350 if (!Op0 || !Op1)
351 return std::optional<int64_t>{};
352 if (I->getOpcode() == Instruction::Add)
353 return std::optional<int64_t>{*Op0 + *Op1};
354 if (I->getOpcode() == Instruction::Mul)
355 return std::optional<int64_t>{*Op0 * *Op1};
356 if (I->getOpcode() == Instruction::Shl)
357 return std::optional<int64_t>{*Op0 << *Op1};
358 if (I->getOpcode() == Instruction::Or)
359 return std::optional<int64_t>{*Op0 | *Op1};
360 }
361 return std::optional<int64_t>{};
362}
363
364// Return true if I is an Or instruction that is equivalent to an add, due to
365// the operands having no common bits set.
366static bool isAddLikeOr(Instruction *I, const DataLayout &DL) {
367 return I->getOpcode() == Instruction::Or &&
368 haveNoCommonBitsSet(LHSCache: I->getOperand(i: 0), RHSCache: I->getOperand(i: 1), SQ: DL);
369}
370
371std::pair<Value *, int64_t>
372MVEGatherScatterLowering::getVarAndConst(Value *Inst, int TypeScale) {
373 std::pair<Value *, int64_t> ReturnFalse =
374 std::pair<Value *, int64_t>(nullptr, 0);
375 // At this point, the instruction we're looking at must be an add or an
376 // add-like-or.
377 Instruction *Add = dyn_cast<Instruction>(Val: Inst);
378 if (Add == nullptr ||
379 (Add->getOpcode() != Instruction::Add && !isAddLikeOr(I: Add, DL: *DL)))
380 return ReturnFalse;
381
382 Value *Summand;
383 std::optional<int64_t> Const;
384 // Find out which operand the value that is increased is
385 if ((Const = getIfConst(V: Add->getOperand(i: 0))))
386 Summand = Add->getOperand(i: 1);
387 else if ((Const = getIfConst(V: Add->getOperand(i: 1))))
388 Summand = Add->getOperand(i: 0);
389 else
390 return ReturnFalse;
391
392 // Check that the constant is small enough for an incrementing gather
393 int64_t Immediate = *Const << TypeScale;
394 if (Immediate > 512 || Immediate < -512 || Immediate % 4 != 0)
395 return ReturnFalse;
396
397 return std::pair<Value *, int64_t>(Summand, Immediate);
398}
399
400Instruction *MVEGatherScatterLowering::lowerGather(IntrinsicInst *I) {
401 using namespace PatternMatch;
402 LLVM_DEBUG(dbgs() << "masked gathers: checking transform preconditions\n"
403 << *I << "\n");
404
405 // @llvm.masked.gather.*(Ptrs, alignment, Mask, Src0)
406 // Attempt to turn the masked gather in I into a MVE intrinsic
407 // Potentially optimising the addressing modes as we do so.
408 auto *Ty = cast<FixedVectorType>(Val: I->getType());
409 Value *Ptr = I->getArgOperand(i: 0);
410 Align Alignment = I->getParamAlign(ArgNo: 0).valueOrOne();
411 Value *Mask = I->getArgOperand(i: 1);
412 Value *PassThru = I->getArgOperand(i: 2);
413
414 if (!isLegalTypeAndAlignment(NumElements: Ty->getNumElements(), ElemSize: Ty->getScalarSizeInBits(),
415 Alignment))
416 return nullptr;
417 lookThroughBitcast(Ptr);
418 assert(Ptr->getType()->isVectorTy() && "Unexpected pointer type");
419
420 IRBuilder<> Builder(I);
421 Instruction *Root = I;
422
423 Instruction *Load = tryCreateIncrementingGatScat(I, Ptr, Builder);
424 if (!Load)
425 Load = tryCreateMaskedGatherOffset(I, Ptr, Root, Builder);
426 if (!Load)
427 Load = tryCreateMaskedGatherBase(I, Ptr, Builder);
428 if (!Load)
429 return nullptr;
430
431 if (!isa<UndefValue>(Val: PassThru) && !match(V: PassThru, P: m_Zero())) {
432 LLVM_DEBUG(dbgs() << "masked gathers: found non-trivial passthru - "
433 << "creating select\n");
434 Load = SelectInst::Create(C: Mask, S1: Load, S2: PassThru);
435 Builder.Insert(I: Load);
436 }
437
438 Root->replaceAllUsesWith(V: Load);
439 Root->eraseFromParent();
440 if (Root != I)
441 // If this was an extending gather, we need to get rid of the sext/zext
442 // sext/zext as well as of the gather itself
443 I->eraseFromParent();
444
445 LLVM_DEBUG(dbgs() << "masked gathers: successfully built masked gather\n"
446 << *Load << "\n");
447 return Load;
448}
449
450Instruction *MVEGatherScatterLowering::tryCreateMaskedGatherBase(
451 IntrinsicInst *I, Value *Ptr, IRBuilder<> &Builder, int64_t Increment) {
452 using namespace PatternMatch;
453 auto *Ty = cast<FixedVectorType>(Val: I->getType());
454 LLVM_DEBUG(dbgs() << "masked gathers: loading from vector of pointers\n");
455 if (Ty->getNumElements() != 4 || Ty->getScalarSizeInBits() != 32)
456 // Can't build an intrinsic for this
457 return nullptr;
458 Value *Mask = I->getArgOperand(i: 1);
459 if (match(V: Mask, P: m_One()))
460 return Builder.CreateIntrinsicWithoutFolding(
461 ID: Intrinsic::arm_mve_vldr_gather_base, OverloadTypes: {Ty, Ptr->getType()},
462 Args: {Ptr, Builder.getInt32(C: Increment)});
463 return Builder.CreateIntrinsicWithoutFolding(
464 ID: Intrinsic::arm_mve_vldr_gather_base_predicated,
465 OverloadTypes: {Ty, Ptr->getType(), Mask->getType()},
466 Args: {Ptr, Builder.getInt32(C: Increment), Mask});
467}
468
469Instruction *MVEGatherScatterLowering::tryCreateMaskedGatherBaseWB(
470 IntrinsicInst *I, Value *Ptr, IRBuilder<> &Builder, int64_t Increment) {
471 using namespace PatternMatch;
472 auto *Ty = cast<FixedVectorType>(Val: I->getType());
473 LLVM_DEBUG(dbgs() << "masked gathers: loading from vector of pointers with "
474 << "writeback\n");
475 if (Ty->getNumElements() != 4 || Ty->getScalarSizeInBits() != 32)
476 // Can't build an intrinsic for this
477 return nullptr;
478 Value *Mask = I->getArgOperand(i: 1);
479 if (match(V: Mask, P: m_One()))
480 return Builder.CreateIntrinsicWithoutFolding(
481 ID: Intrinsic::arm_mve_vldr_gather_base_wb, OverloadTypes: {Ty, Ptr->getType()},
482 Args: {Ptr, Builder.getInt32(C: Increment)});
483 return Builder.CreateIntrinsicWithoutFolding(
484 ID: Intrinsic::arm_mve_vldr_gather_base_wb_predicated,
485 OverloadTypes: {Ty, Ptr->getType(), Mask->getType()},
486 Args: {Ptr, Builder.getInt32(C: Increment), Mask});
487}
488
489Instruction *MVEGatherScatterLowering::tryCreateMaskedGatherOffset(
490 IntrinsicInst *I, Value *Ptr, Instruction *&Root, IRBuilder<> &Builder) {
491 using namespace PatternMatch;
492
493 Type *MemoryTy = I->getType();
494 Type *ResultTy = MemoryTy;
495
496 unsigned Unsigned = 1;
497 // The size of the gather was already checked in isLegalTypeAndAlignment;
498 // if it was not a full vector width an appropriate extend should follow.
499 auto *Extend = Root;
500 bool TruncResult = false;
501 if (MemoryTy->getPrimitiveSizeInBits() < 128) {
502 if (I->hasOneUse()) {
503 // If the gather has a single extend of the correct type, use an extending
504 // gather and replace the ext. In which case the correct root to replace
505 // is not the CallInst itself, but the instruction which extends it.
506 Instruction* User = cast<Instruction>(Val: *I->users().begin());
507 if (isa<SExtInst>(Val: User) &&
508 User->getType()->getPrimitiveSizeInBits() == 128) {
509 LLVM_DEBUG(dbgs() << "masked gathers: Incorporating extend: "
510 << *User << "\n");
511 Extend = User;
512 ResultTy = User->getType();
513 Unsigned = 0;
514 } else if (isa<ZExtInst>(Val: User) &&
515 User->getType()->getPrimitiveSizeInBits() == 128) {
516 LLVM_DEBUG(dbgs() << "masked gathers: Incorporating extend: "
517 << *ResultTy << "\n");
518 Extend = User;
519 ResultTy = User->getType();
520 }
521 }
522
523 // If an extend hasn't been found and the type is an integer, create an
524 // extending gather and truncate back to the original type.
525 if (ResultTy->getPrimitiveSizeInBits() < 128 &&
526 ResultTy->isIntOrIntVectorTy()) {
527 ResultTy = ResultTy->getWithNewBitWidth(
528 NewBitWidth: 128 / cast<FixedVectorType>(Val: ResultTy)->getNumElements());
529 TruncResult = true;
530 LLVM_DEBUG(dbgs() << "masked gathers: Small input type, truncing to: "
531 << *ResultTy << "\n");
532 }
533
534 // The final size of the gather must be a full vector width
535 if (ResultTy->getPrimitiveSizeInBits() != 128) {
536 LLVM_DEBUG(dbgs() << "masked gathers: Extend needed but not provided "
537 "from the correct type. Expanding\n");
538 return nullptr;
539 }
540 }
541
542 Value *Offsets;
543 int Scale;
544 Value *BasePtr = decomposePtr(
545 Ptr, Offsets, Scale, Ty: cast<FixedVectorType>(Val: ResultTy), MemoryTy, Builder);
546 if (!BasePtr)
547 return nullptr;
548
549 Root = Extend;
550 Value *Mask = I->getArgOperand(i: 1);
551 Instruction *Load = nullptr;
552 if (!match(V: Mask, P: m_One()))
553 Load = Builder.CreateIntrinsicWithoutFolding(
554 ID: Intrinsic::arm_mve_vldr_gather_offset_predicated,
555 OverloadTypes: {ResultTy, BasePtr->getType(), Offsets->getType(), Mask->getType()},
556 Args: {BasePtr, Offsets, Builder.getInt32(C: MemoryTy->getScalarSizeInBits()),
557 Builder.getInt32(C: Scale), Builder.getInt32(C: Unsigned), Mask});
558 else
559 Load = Builder.CreateIntrinsicWithoutFolding(
560 ID: Intrinsic::arm_mve_vldr_gather_offset,
561 OverloadTypes: {ResultTy, BasePtr->getType(), Offsets->getType()},
562 Args: {BasePtr, Offsets, Builder.getInt32(C: MemoryTy->getScalarSizeInBits()),
563 Builder.getInt32(C: Scale), Builder.getInt32(C: Unsigned)});
564
565 if (TruncResult) {
566 Load = TruncInst::Create(Instruction::Trunc, S: Load, Ty: MemoryTy);
567 Builder.Insert(I: Load);
568 }
569 return Load;
570}
571
572Instruction *MVEGatherScatterLowering::lowerScatter(IntrinsicInst *I) {
573 using namespace PatternMatch;
574 LLVM_DEBUG(dbgs() << "masked scatters: checking transform preconditions\n"
575 << *I << "\n");
576
577 // @llvm.masked.scatter.*(data, ptrs, alignment, mask)
578 // Attempt to turn the masked scatter in I into a MVE intrinsic
579 // Potentially optimising the addressing modes as we do so.
580 Value *Input = I->getArgOperand(i: 0);
581 Value *Ptr = I->getArgOperand(i: 1);
582 Align Alignment = I->getParamAlign(ArgNo: 1).valueOrOne();
583 auto *Ty = cast<FixedVectorType>(Val: Input->getType());
584
585 if (!isLegalTypeAndAlignment(NumElements: Ty->getNumElements(), ElemSize: Ty->getScalarSizeInBits(),
586 Alignment))
587 return nullptr;
588
589 lookThroughBitcast(Ptr);
590 assert(Ptr->getType()->isVectorTy() && "Unexpected pointer type");
591
592 IRBuilder<> Builder(I);
593 Instruction *Store = tryCreateIncrementingGatScat(I, Ptr, Builder);
594 if (!Store)
595 Store = tryCreateMaskedScatterOffset(I, Offsets: Ptr, Builder);
596 if (!Store)
597 Store = tryCreateMaskedScatterBase(I, Ptr, Builder);
598 if (!Store)
599 return nullptr;
600
601 LLVM_DEBUG(dbgs() << "masked scatters: successfully built masked scatter\n"
602 << *Store << "\n");
603 I->eraseFromParent();
604 return Store;
605}
606
607Instruction *MVEGatherScatterLowering::tryCreateMaskedScatterBase(
608 IntrinsicInst *I, Value *Ptr, IRBuilder<> &Builder, int64_t Increment) {
609 using namespace PatternMatch;
610 Value *Input = I->getArgOperand(i: 0);
611 auto *Ty = cast<FixedVectorType>(Val: Input->getType());
612 // Only QR variants allow truncating
613 if (!(Ty->getNumElements() == 4 && Ty->getScalarSizeInBits() == 32)) {
614 // Can't build an intrinsic for this
615 return nullptr;
616 }
617 Value *Mask = I->getArgOperand(i: 2);
618 // int_arm_mve_vstr_scatter_base(_predicated) addr, offset, data(, mask)
619 LLVM_DEBUG(dbgs() << "masked scatters: storing to a vector of pointers\n");
620 if (match(V: Mask, P: m_One()))
621 return Builder.CreateIntrinsicWithoutFolding(
622 ID: Intrinsic::arm_mve_vstr_scatter_base,
623 OverloadTypes: {Ptr->getType(), Input->getType()},
624 Args: {Ptr, Builder.getInt32(C: Increment), Input});
625 return Builder.CreateIntrinsicWithoutFolding(
626 ID: Intrinsic::arm_mve_vstr_scatter_base_predicated,
627 OverloadTypes: {Ptr->getType(), Input->getType(), Mask->getType()},
628 Args: {Ptr, Builder.getInt32(C: Increment), Input, Mask});
629}
630
631Instruction *MVEGatherScatterLowering::tryCreateMaskedScatterBaseWB(
632 IntrinsicInst *I, Value *Ptr, IRBuilder<> &Builder, int64_t Increment) {
633 using namespace PatternMatch;
634 Value *Input = I->getArgOperand(i: 0);
635 auto *Ty = cast<FixedVectorType>(Val: Input->getType());
636 LLVM_DEBUG(dbgs() << "masked scatters: storing to a vector of pointers "
637 << "with writeback\n");
638 if (Ty->getNumElements() != 4 || Ty->getScalarSizeInBits() != 32)
639 // Can't build an intrinsic for this
640 return nullptr;
641 Value *Mask = I->getArgOperand(i: 2);
642 if (match(V: Mask, P: m_One()))
643 return Builder.CreateIntrinsicWithoutFolding(
644 ID: Intrinsic::arm_mve_vstr_scatter_base_wb,
645 OverloadTypes: {Ptr->getType(), Input->getType()},
646 Args: {Ptr, Builder.getInt32(C: Increment), Input});
647 return Builder.CreateIntrinsicWithoutFolding(
648 ID: Intrinsic::arm_mve_vstr_scatter_base_wb_predicated,
649 OverloadTypes: {Ptr->getType(), Input->getType(), Mask->getType()},
650 Args: {Ptr, Builder.getInt32(C: Increment), Input, Mask});
651}
652
653Instruction *MVEGatherScatterLowering::tryCreateMaskedScatterOffset(
654 IntrinsicInst *I, Value *Ptr, IRBuilder<> &Builder) {
655 using namespace PatternMatch;
656 Value *Input = I->getArgOperand(i: 0);
657 Value *Mask = I->getArgOperand(i: 2);
658 Type *InputTy = Input->getType();
659 Type *MemoryTy = InputTy;
660
661 LLVM_DEBUG(dbgs() << "masked scatters: getelementpointer found. Storing"
662 << " to base + vector of offsets\n");
663 // If the input has been truncated, try to integrate that trunc into the
664 // scatter instruction (we don't care about alignment here)
665 if (TruncInst *Trunc = dyn_cast<TruncInst>(Val: Input)) {
666 Value *PreTrunc = Trunc->getOperand(i_nocapture: 0);
667 Type *PreTruncTy = PreTrunc->getType();
668 if (PreTruncTy->getPrimitiveSizeInBits() == 128) {
669 Input = PreTrunc;
670 InputTy = PreTruncTy;
671 }
672 }
673 bool ExtendInput = false;
674 if (InputTy->getPrimitiveSizeInBits() < 128 &&
675 InputTy->isIntOrIntVectorTy()) {
676 // If we can't find a trunc to incorporate into the instruction, create an
677 // implicit one with a zext, so that we can still create a scatter. We know
678 // that the input type is 4x/8x/16x and of type i8/i16/i32, so any type
679 // smaller than 128 bits will divide evenly into a 128bit vector.
680 InputTy = InputTy->getWithNewBitWidth(
681 NewBitWidth: 128 / cast<FixedVectorType>(Val: InputTy)->getNumElements());
682 ExtendInput = true;
683 LLVM_DEBUG(dbgs() << "masked scatters: Small input type, will extend:\n"
684 << *Input << "\n");
685 }
686 if (InputTy->getPrimitiveSizeInBits() != 128) {
687 LLVM_DEBUG(dbgs() << "masked scatters: cannot create scatters for "
688 "non-standard input types. Expanding.\n");
689 return nullptr;
690 }
691
692 Value *Offsets;
693 int Scale;
694 Value *BasePtr = decomposePtr(
695 Ptr, Offsets, Scale, Ty: cast<FixedVectorType>(Val: InputTy), MemoryTy, Builder);
696 if (!BasePtr)
697 return nullptr;
698
699 if (ExtendInput)
700 Input = Builder.CreateZExt(V: Input, DestTy: InputTy);
701 if (!match(V: Mask, P: m_One()))
702 return Builder.CreateIntrinsicWithoutFolding(
703 ID: Intrinsic::arm_mve_vstr_scatter_offset_predicated,
704 OverloadTypes: {BasePtr->getType(), Offsets->getType(), Input->getType(),
705 Mask->getType()},
706 Args: {BasePtr, Offsets, Input,
707 Builder.getInt32(C: MemoryTy->getScalarSizeInBits()),
708 Builder.getInt32(C: Scale), Mask});
709 return Builder.CreateIntrinsicWithoutFolding(
710 ID: Intrinsic::arm_mve_vstr_scatter_offset,
711 OverloadTypes: {BasePtr->getType(), Offsets->getType(), Input->getType()},
712 Args: {BasePtr, Offsets, Input,
713 Builder.getInt32(C: MemoryTy->getScalarSizeInBits()),
714 Builder.getInt32(C: Scale)});
715}
716
717Instruction *MVEGatherScatterLowering::tryCreateIncrementingGatScat(
718 IntrinsicInst *I, Value *Ptr, IRBuilder<> &Builder) {
719 FixedVectorType *Ty;
720 if (I->getIntrinsicID() == Intrinsic::masked_gather)
721 Ty = cast<FixedVectorType>(Val: I->getType());
722 else
723 Ty = cast<FixedVectorType>(Val: I->getArgOperand(i: 0)->getType());
724
725 // Incrementing gathers only exist for v4i32
726 if (Ty->getNumElements() != 4 || Ty->getScalarSizeInBits() != 32)
727 return nullptr;
728 // Incrementing gathers are not beneficial outside of a loop
729 Loop *L = LI->getLoopFor(BB: I->getParent());
730 if (L == nullptr)
731 return nullptr;
732
733 // Decompose the GEP into Base and Offsets
734 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: Ptr);
735 Value *Offsets;
736 Value *BasePtr = decomposeGEP(Offsets, Ty, GEP, Builder);
737 if (!BasePtr)
738 return nullptr;
739
740 LLVM_DEBUG(dbgs() << "masked gathers/scatters: trying to build incrementing "
741 "wb gather/scatter\n");
742
743 // The gep was in charge of making sure the offsets are scaled correctly
744 // - calculate that factor so it can be applied by hand
745 int TypeScale =
746 computeScale(GEPElemSize: DL->getTypeAllocSizeInBits(Ty: GEP->getSourceElementType()),
747 MemoryElemSize: DL->getTypeSizeInBits(Ty: GEP->getType()) /
748 cast<FixedVectorType>(Val: GEP->getType())->getNumElements());
749 if (TypeScale == -1)
750 return nullptr;
751
752 if (GEP->hasOneUse()) {
753 // Only in this case do we want to build a wb gather, because the wb will
754 // change the phi which does affect other users of the gep (which will still
755 // be using the phi in the old way)
756 if (auto *Load = tryCreateIncrementingWBGatScat(I, BasePtr, Ptr: Offsets,
757 TypeScale, Builder))
758 return Load;
759 }
760
761 LLVM_DEBUG(dbgs() << "masked gathers/scatters: trying to build incrementing "
762 "non-wb gather/scatter\n");
763
764 std::pair<Value *, int64_t> Add = getVarAndConst(Inst: Offsets, TypeScale);
765 if (Add.first == nullptr)
766 return nullptr;
767 Value *OffsetsIncoming = Add.first;
768 int64_t Immediate = Add.second;
769
770 // Make sure the offsets are scaled correctly
771 Instruction *ScaledOffsets = BinaryOperator::Create(
772 Op: Instruction::Shl, S1: OffsetsIncoming,
773 S2: Builder.CreateVectorSplat(NumElts: Ty->getNumElements(),
774 V: Builder.getInt32(C: TypeScale)),
775 Name: "ScaledIndex", InsertBefore: I->getIterator());
776 // Add the base to the offsets
777 OffsetsIncoming = BinaryOperator::Create(
778 Op: Instruction::Add, S1: ScaledOffsets,
779 S2: Builder.CreateVectorSplat(
780 NumElts: Ty->getNumElements(),
781 V: Builder.CreatePtrToInt(
782 V: BasePtr,
783 DestTy: cast<VectorType>(Val: ScaledOffsets->getType())->getElementType())),
784 Name: "StartIndex", InsertBefore: I->getIterator());
785
786 if (I->getIntrinsicID() == Intrinsic::masked_gather)
787 return tryCreateMaskedGatherBase(I, Ptr: OffsetsIncoming, Builder, Increment: Immediate);
788 else
789 return tryCreateMaskedScatterBase(I, Ptr: OffsetsIncoming, Builder, Increment: Immediate);
790}
791
792Instruction *MVEGatherScatterLowering::tryCreateIncrementingWBGatScat(
793 IntrinsicInst *I, Value *BasePtr, Value *Offsets, unsigned TypeScale,
794 IRBuilder<> &Builder) {
795 // Check whether this gather's offset is incremented by a constant - if so,
796 // and the load is of the right type, we can merge this into a QI gather
797 Loop *L = LI->getLoopFor(BB: I->getParent());
798 // Offsets that are worth merging into this instruction will be incremented
799 // by a constant, thus we're looking for an add of a phi and a constant
800 PHINode *Phi = dyn_cast<PHINode>(Val: Offsets);
801 if (Phi == nullptr || Phi->getNumIncomingValues() != 2 ||
802 Phi->getParent() != L->getHeader() || !Phi->hasNUses(N: 2))
803 // No phi means no IV to write back to; if there is a phi, we expect it
804 // to have exactly two incoming values; the only phis we are interested in
805 // will be loop IV's and have exactly two uses, one in their increment and
806 // one in the gather's gep
807 return nullptr;
808
809 unsigned IncrementIndex =
810 Phi->getIncomingBlock(i: 0) == L->getLoopLatch() ? 0 : 1;
811 // Look through the phi to the phi increment
812 Offsets = Phi->getIncomingValue(i: IncrementIndex);
813
814 std::pair<Value *, int64_t> Add = getVarAndConst(Inst: Offsets, TypeScale);
815 if (Add.first == nullptr)
816 return nullptr;
817 Value *OffsetsIncoming = Add.first;
818 int64_t Immediate = Add.second;
819 if (OffsetsIncoming != Phi)
820 // Then the increment we are looking at is not an increment of the
821 // induction variable, and we don't want to do a writeback
822 return nullptr;
823
824 Builder.SetInsertPoint(&Phi->getIncomingBlock(i: 1 - IncrementIndex)->back());
825 unsigned NumElems =
826 cast<FixedVectorType>(Val: OffsetsIncoming->getType())->getNumElements();
827
828 // Make sure the offsets are scaled correctly
829 Instruction *ScaledOffsets = BinaryOperator::Create(
830 Op: Instruction::Shl, S1: Phi->getIncomingValue(i: 1 - IncrementIndex),
831 S2: Builder.CreateVectorSplat(NumElts: NumElems, V: Builder.getInt32(C: TypeScale)),
832 Name: "ScaledIndex",
833 InsertBefore: Phi->getIncomingBlock(i: 1 - IncrementIndex)->back().getIterator());
834 // Add the base to the offsets
835 OffsetsIncoming = BinaryOperator::Create(
836 Op: Instruction::Add, S1: ScaledOffsets,
837 S2: Builder.CreateVectorSplat(
838 NumElts: NumElems,
839 V: Builder.CreatePtrToInt(
840 V: BasePtr,
841 DestTy: cast<VectorType>(Val: ScaledOffsets->getType())->getElementType())),
842 Name: "StartIndex",
843 InsertBefore: Phi->getIncomingBlock(i: 1 - IncrementIndex)->back().getIterator());
844 // The gather is pre-incrementing
845 OffsetsIncoming = BinaryOperator::Create(
846 Op: Instruction::Sub, S1: OffsetsIncoming,
847 S2: Builder.CreateVectorSplat(NumElts: NumElems, V: Builder.getInt32(C: Immediate)),
848 Name: "PreIncrementStartIndex",
849 InsertBefore: Phi->getIncomingBlock(i: 1 - IncrementIndex)->back().getIterator());
850 Phi->setIncomingValue(i: 1 - IncrementIndex, V: OffsetsIncoming);
851
852 Builder.SetInsertPoint(I);
853
854 Instruction *EndResult;
855 Instruction *NewInduction;
856 if (I->getIntrinsicID() == Intrinsic::masked_gather) {
857 // Build the incrementing gather
858 Value *Load = tryCreateMaskedGatherBaseWB(I, Ptr: Phi, Builder, Increment: Immediate);
859 // One value to be handed to whoever uses the gather, one is the loop
860 // increment
861 EndResult = ExtractValueInst::Create(Agg: Load, Idxs: 0, NameStr: "Gather");
862 NewInduction = ExtractValueInst::Create(Agg: Load, Idxs: 1, NameStr: "GatherIncrement");
863 Builder.Insert(I: EndResult);
864 Builder.Insert(I: NewInduction);
865 } else {
866 // Build the incrementing scatter
867 EndResult = NewInduction =
868 tryCreateMaskedScatterBaseWB(I, Ptr: Phi, Builder, Increment: Immediate);
869 }
870 Instruction *AddInst = cast<Instruction>(Val: Offsets);
871 AddInst->replaceAllUsesWith(V: NewInduction);
872 AddInst->eraseFromParent();
873 Phi->setIncomingValue(i: IncrementIndex, V: NewInduction);
874
875 return EndResult;
876}
877
878void MVEGatherScatterLowering::pushOutAdd(PHINode *&Phi,
879 Value *OffsSecondOperand,
880 unsigned StartIndex) {
881 LLVM_DEBUG(dbgs() << "masked gathers/scatters: optimising add instruction\n");
882 assert(Phi->getNumIncomingValues() == 2);
883 BasicBlock *NewIndexBlock = Phi->getIncomingBlock(i: StartIndex);
884 BasicBlock::iterator InsertionPoint = NewIndexBlock->back().getIterator();
885 // Initialize the phi with a vector that contains a sum of the constants
886 Instruction *NewIndex = BinaryOperator::Create(
887 Op: Instruction::Add, S1: Phi->getIncomingValue(i: StartIndex), S2: OffsSecondOperand,
888 Name: "PushedOutAdd", InsertBefore: InsertionPoint);
889 unsigned IncrementIndex = StartIndex == 0 ? 1 : 0;
890
891 // Order such that start index comes first (this reduces mov's)
892 Value *IncrementIndexValue = Phi->getIncomingValue(i: IncrementIndex);
893 BasicBlock *IncrementIndexBlock = Phi->getIncomingBlock(i: IncrementIndex);
894 Phi->setIncomingValue(i: 0, V: NewIndex);
895 Phi->setIncomingBlock(i: 0, BB: NewIndexBlock);
896 Phi->setIncomingValue(i: 1, V: IncrementIndexValue);
897 Phi->setIncomingBlock(i: 1, BB: IncrementIndexBlock);
898}
899
900void MVEGatherScatterLowering::pushOutMulShl(unsigned Opcode, PHINode *&Phi,
901 Value *IncrementPerRound,
902 Value *OffsSecondOperand,
903 unsigned LoopIncrement,
904 IRBuilder<> &Builder) {
905 LLVM_DEBUG(dbgs() << "masked gathers/scatters: optimising mul instruction\n");
906 assert(Phi->getNumIncomingValues() == 2);
907
908 // Create a new scalar add outside of the loop and transform it to a splat
909 // by which loop variable can be incremented
910 BasicBlock *StartIndexBlock =
911 Phi->getIncomingBlock(i: LoopIncrement == 1 ? 0 : 1);
912 BasicBlock::iterator InsertionPoint = StartIndexBlock->back().getIterator();
913
914 // Create a new index
915 Value *StartIndex =
916 BinaryOperator::Create(Op: (Instruction::BinaryOps)Opcode,
917 S1: Phi->getIncomingValue(i: LoopIncrement == 1 ? 0 : 1),
918 S2: OffsSecondOperand, Name: "PushedOutMul", InsertBefore: InsertionPoint);
919
920 Instruction *Product =
921 BinaryOperator::Create(Op: (Instruction::BinaryOps)Opcode, S1: IncrementPerRound,
922 S2: OffsSecondOperand, Name: "Product", InsertBefore: InsertionPoint);
923 BasicBlock *NewIncrementBlock = Phi->getIncomingBlock(i: LoopIncrement);
924 BasicBlock::iterator NewIncrInsertPt =
925 NewIncrementBlock->back().getIterator();
926 NewIncrInsertPt = std::prev(x: NewIncrInsertPt);
927
928 // Increment NewIndex by Product instead of the multiplication
929 Instruction *NewIncrement = BinaryOperator::Create(
930 Op: Instruction::Add, S1: Phi, S2: Product, Name: "IncrementPushedOutMul", InsertBefore: NewIncrInsertPt);
931
932 Phi->setIncomingValue(i: 0, V: StartIndex);
933 Phi->setIncomingBlock(i: 0, BB: StartIndexBlock);
934 Phi->setIncomingValue(i: 1, V: NewIncrement);
935 Phi->setIncomingBlock(i: 1, BB: NewIncrementBlock);
936}
937
938// Check whether all usages of this instruction are as offsets of
939// gathers/scatters or simple arithmetics only used by gathers/scatters
940static bool hasAllGatScatUsers(Instruction *I, const DataLayout &DL) {
941 if (I->use_empty()) {
942 return false;
943 }
944 bool Gatscat = true;
945 for (User *U : I->users()) {
946 if (!isa<Instruction>(Val: U))
947 return false;
948 if (isa<GetElementPtrInst>(Val: U) ||
949 isGatherScatter(IntInst: dyn_cast<IntrinsicInst>(Val: U))) {
950 return Gatscat;
951 } else {
952 unsigned OpCode = cast<Instruction>(Val: U)->getOpcode();
953 if ((OpCode == Instruction::Add || OpCode == Instruction::Mul ||
954 OpCode == Instruction::Shl ||
955 isAddLikeOr(I: cast<Instruction>(Val: U), DL)) &&
956 hasAllGatScatUsers(I: cast<Instruction>(Val: U), DL)) {
957 continue;
958 }
959 return false;
960 }
961 }
962 return Gatscat;
963}
964
965bool MVEGatherScatterLowering::optimiseOffsets(Value *Offsets, BasicBlock *BB,
966 LoopInfo *LI) {
967 LLVM_DEBUG(dbgs() << "masked gathers/scatters: trying to optimize: "
968 << *Offsets << "\n");
969 // Optimise the addresses of gathers/scatters by moving invariant
970 // calculations out of the loop
971 if (!isa<Instruction>(Val: Offsets))
972 return false;
973 Instruction *Offs = cast<Instruction>(Val: Offsets);
974 if (Offs->getOpcode() != Instruction::Add && !isAddLikeOr(I: Offs, DL: *DL) &&
975 Offs->getOpcode() != Instruction::Mul &&
976 Offs->getOpcode() != Instruction::Shl)
977 return false;
978 Loop *L = LI->getLoopFor(BB);
979 if (L == nullptr)
980 return false;
981 if (!Offs->hasOneUse()) {
982 if (!hasAllGatScatUsers(I: Offs, DL: *DL))
983 return false;
984 }
985
986 // Find out which, if any, operand of the instruction
987 // is a phi node
988 PHINode *Phi;
989 int OffsSecondOp;
990 if (isa<PHINode>(Val: Offs->getOperand(i: 0))) {
991 Phi = cast<PHINode>(Val: Offs->getOperand(i: 0));
992 OffsSecondOp = 1;
993 } else if (isa<PHINode>(Val: Offs->getOperand(i: 1))) {
994 Phi = cast<PHINode>(Val: Offs->getOperand(i: 1));
995 OffsSecondOp = 0;
996 } else {
997 bool Changed = false;
998 if (isa<Instruction>(Val: Offs->getOperand(i: 0)) &&
999 L->contains(Inst: cast<Instruction>(Val: Offs->getOperand(i: 0))))
1000 Changed |= optimiseOffsets(Offsets: Offs->getOperand(i: 0), BB, LI);
1001 if (isa<Instruction>(Val: Offs->getOperand(i: 1)) &&
1002 L->contains(Inst: cast<Instruction>(Val: Offs->getOperand(i: 1))))
1003 Changed |= optimiseOffsets(Offsets: Offs->getOperand(i: 1), BB, LI);
1004 if (!Changed)
1005 return false;
1006 if (isa<PHINode>(Val: Offs->getOperand(i: 0))) {
1007 Phi = cast<PHINode>(Val: Offs->getOperand(i: 0));
1008 OffsSecondOp = 1;
1009 } else if (isa<PHINode>(Val: Offs->getOperand(i: 1))) {
1010 Phi = cast<PHINode>(Val: Offs->getOperand(i: 1));
1011 OffsSecondOp = 0;
1012 } else {
1013 return false;
1014 }
1015 }
1016 // A phi node we want to perform this function on should be from the
1017 // loop header.
1018 if (Phi->getParent() != L->getHeader())
1019 return false;
1020
1021 // We're looking for a simple add recurrence.
1022 BinaryOperator *IncInstruction;
1023 Value *Start, *IncrementPerRound;
1024 if (!matchSimpleRecurrence(P: Phi, BO&: IncInstruction, Start, Step&: IncrementPerRound) ||
1025 IncInstruction->getOpcode() != Instruction::Add)
1026 return false;
1027
1028 int IncrementingBlock = Phi->getIncomingValue(i: 0) == IncInstruction ? 0 : 1;
1029
1030 // Get the value that is added to/multiplied with the phi
1031 Value *OffsSecondOperand = Offs->getOperand(i: OffsSecondOp);
1032
1033 if (IncrementPerRound->getType() != OffsSecondOperand->getType() ||
1034 !L->isLoopInvariant(V: OffsSecondOperand))
1035 // Something has gone wrong, abort
1036 return false;
1037
1038 // Only proceed if the increment per round is a constant or an instruction
1039 // which does not originate from within the loop
1040 if (!isa<Constant>(Val: IncrementPerRound) &&
1041 !(isa<Instruction>(Val: IncrementPerRound) &&
1042 !L->contains(Inst: cast<Instruction>(Val: IncrementPerRound))))
1043 return false;
1044
1045 // If the phi is not used by anything else, we can just adapt it when
1046 // replacing the instruction; if it is, we'll have to duplicate it
1047 PHINode *NewPhi;
1048 if (Phi->hasNUses(N: 2) && IncInstruction->hasOneUse()) {
1049 // No other users -> reuse existing phi (One user is the instruction
1050 // we're looking at, the other is the phi increment)
1051 NewPhi = Phi;
1052 } else {
1053 // There are other users -> create a new phi
1054 NewPhi = PHINode::Create(Ty: Phi->getType(), NumReservedValues: 2, NameStr: "NewPhi", InsertBefore: Phi->getIterator());
1055 // Copy the incoming values of the old phi
1056 NewPhi->addIncoming(V: Phi->getIncomingValue(i: IncrementingBlock == 1 ? 0 : 1),
1057 BB: Phi->getIncomingBlock(i: IncrementingBlock == 1 ? 0 : 1));
1058 IncInstruction = BinaryOperator::Create(
1059 Op: Instruction::BinaryOps(IncInstruction->getOpcode()), S1: NewPhi,
1060 S2: IncrementPerRound, Name: "LoopIncrement", InsertBefore: IncInstruction->getIterator());
1061 NewPhi->addIncoming(V: IncInstruction,
1062 BB: Phi->getIncomingBlock(i: IncrementingBlock));
1063 IncrementingBlock = 1;
1064 }
1065
1066 IRBuilder<> Builder(Phi);
1067 Builder.SetCurrentDebugLocation(Offs->getDebugLoc());
1068
1069 switch (Offs->getOpcode()) {
1070 case Instruction::Add:
1071 case Instruction::Or:
1072 pushOutAdd(Phi&: NewPhi, OffsSecondOperand, StartIndex: IncrementingBlock == 1 ? 0 : 1);
1073 break;
1074 case Instruction::Mul:
1075 case Instruction::Shl:
1076 pushOutMulShl(Opcode: Offs->getOpcode(), Phi&: NewPhi, IncrementPerRound,
1077 OffsSecondOperand, LoopIncrement: IncrementingBlock, Builder);
1078 break;
1079 default:
1080 return false;
1081 }
1082 LLVM_DEBUG(dbgs() << "masked gathers/scatters: simplified loop variable "
1083 << "add/mul\n");
1084
1085 // The instruction has now been "absorbed" into the phi value
1086 Offs->replaceAllUsesWith(V: NewPhi);
1087 Offs->eraseFromParent();
1088 // Clean up the old increment in case it's unused because we built a new
1089 // one
1090 if (IncInstruction->use_empty())
1091 IncInstruction->eraseFromParent();
1092
1093 return true;
1094}
1095
1096static Value *CheckAndCreateOffsetAdd(Value *X, unsigned ScaleX, Value *Y,
1097 unsigned ScaleY, IRBuilder<> &Builder) {
1098 // Splat the non-vector value to a vector of the given type - if the value is
1099 // a constant (and its value isn't too big), we can even use this opportunity
1100 // to scale it to the size of the vector elements
1101 auto FixSummands = [&Builder](FixedVectorType *&VT, Value *&NonVectorVal) {
1102 ConstantInt *Const;
1103 if ((Const = dyn_cast<ConstantInt>(Val: NonVectorVal)) &&
1104 VT->getElementType() != NonVectorVal->getType()) {
1105 unsigned TargetElemSize = VT->getElementType()->getPrimitiveSizeInBits();
1106 uint64_t N = Const->getZExtValue();
1107 if (N < (unsigned)(1 << (TargetElemSize - 1))) {
1108 NonVectorVal = Builder.CreateVectorSplat(
1109 NumElts: VT->getNumElements(), V: Builder.getIntN(N: TargetElemSize, C: N));
1110 return;
1111 }
1112 }
1113 NonVectorVal =
1114 Builder.CreateVectorSplat(NumElts: VT->getNumElements(), V: NonVectorVal);
1115 };
1116
1117 FixedVectorType *XElType = dyn_cast<FixedVectorType>(Val: X->getType());
1118 FixedVectorType *YElType = dyn_cast<FixedVectorType>(Val: Y->getType());
1119 // If one of X, Y is not a vector, we have to splat it in order
1120 // to add the two of them.
1121 if (XElType && !YElType) {
1122 FixSummands(XElType, Y);
1123 YElType = cast<FixedVectorType>(Val: Y->getType());
1124 } else if (YElType && !XElType) {
1125 FixSummands(YElType, X);
1126 XElType = cast<FixedVectorType>(Val: X->getType());
1127 }
1128 assert(XElType && YElType && "Unknown vector types");
1129 // Check that the summands are of compatible types
1130 if (XElType != YElType) {
1131 LLVM_DEBUG(dbgs() << "masked gathers/scatters: incompatible gep offsets\n");
1132 return nullptr;
1133 }
1134
1135 if (XElType->getElementType()->getScalarSizeInBits() != 32) {
1136 // Check that by adding the vectors we do not accidentally
1137 // create an overflow
1138 Constant *ConstX = dyn_cast<Constant>(Val: X);
1139 Constant *ConstY = dyn_cast<Constant>(Val: Y);
1140 if (!ConstX || !ConstY)
1141 return nullptr;
1142 unsigned TargetElemSize = 128 / XElType->getNumElements();
1143 for (unsigned i = 0; i < XElType->getNumElements(); i++) {
1144 ConstantInt *ConstXEl =
1145 dyn_cast<ConstantInt>(Val: ConstX->getAggregateElement(Elt: i));
1146 ConstantInt *ConstYEl =
1147 dyn_cast<ConstantInt>(Val: ConstY->getAggregateElement(Elt: i));
1148 if (!ConstXEl || !ConstYEl ||
1149 ConstXEl->getZExtValue() * ScaleX +
1150 ConstYEl->getZExtValue() * ScaleY >=
1151 (unsigned)(1 << (TargetElemSize - 1)))
1152 return nullptr;
1153 }
1154 }
1155
1156 Value *XScale = Builder.CreateVectorSplat(
1157 NumElts: XElType->getNumElements(),
1158 V: Builder.getIntN(N: XElType->getScalarSizeInBits(), C: ScaleX));
1159 Value *YScale = Builder.CreateVectorSplat(
1160 NumElts: YElType->getNumElements(),
1161 V: Builder.getIntN(N: YElType->getScalarSizeInBits(), C: ScaleY));
1162 Value *Add = Builder.CreateAdd(LHS: Builder.CreateMul(LHS: X, RHS: XScale),
1163 RHS: Builder.CreateMul(LHS: Y, RHS: YScale));
1164
1165 if (checkOffsetSize(Offsets: Add, TargetElemCount: XElType->getNumElements()))
1166 return Add;
1167 else
1168 return nullptr;
1169}
1170
1171Value *MVEGatherScatterLowering::foldGEP(GetElementPtrInst *GEP,
1172 Value *&Offsets, unsigned &Scale,
1173 IRBuilder<> &Builder) {
1174 Value *GEPPtr = GEP->getPointerOperand();
1175 Offsets = GEP->getOperand(i_nocapture: 1);
1176 Scale = DL->getTypeAllocSize(Ty: GEP->getSourceElementType());
1177 // We only merge geps with constant offsets, because only for those
1178 // we can make sure that we do not cause an overflow
1179 if (GEP->getNumIndices() != 1 || !isa<Constant>(Val: Offsets))
1180 return nullptr;
1181 if (GetElementPtrInst *BaseGEP = dyn_cast<GetElementPtrInst>(Val: GEPPtr)) {
1182 // Merge the two geps into one
1183 Value *BaseBasePtr = foldGEP(GEP: BaseGEP, Offsets, Scale, Builder);
1184 if (!BaseBasePtr)
1185 return nullptr;
1186 Offsets = CheckAndCreateOffsetAdd(
1187 X: Offsets, ScaleX: Scale, Y: GEP->getOperand(i_nocapture: 1),
1188 ScaleY: DL->getTypeAllocSize(Ty: GEP->getSourceElementType()), Builder);
1189 if (Offsets == nullptr)
1190 return nullptr;
1191 Scale = 1; // Scale is always an i8 at this point.
1192 return BaseBasePtr;
1193 }
1194 return GEPPtr;
1195}
1196
1197bool MVEGatherScatterLowering::optimiseAddress(Value *Address, BasicBlock *BB,
1198 LoopInfo *LI) {
1199 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: Address);
1200 if (!GEP)
1201 return false;
1202 bool Changed = false;
1203 if (GEP->hasOneUse() && isa<GetElementPtrInst>(Val: GEP->getPointerOperand())) {
1204 IRBuilder<> Builder(GEP);
1205 Value *Offsets;
1206 unsigned Scale;
1207 Value *Base = foldGEP(GEP, Offsets, Scale, Builder);
1208 // We only want to merge the geps if there is a real chance that they can be
1209 // used by an MVE gather; thus the offset has to have the correct size
1210 // (always i32 if it is not of vector type) and the base has to be a
1211 // pointer.
1212 if (Offsets && Base && Base != GEP) {
1213 assert(Scale == 1 && "Expected to fold GEP to a scale of 1");
1214 Type *BaseTy = Builder.getPtrTy();
1215 if (auto *VecTy = dyn_cast<FixedVectorType>(Val: Base->getType()))
1216 BaseTy = FixedVectorType::get(ElementType: BaseTy, FVTy: VecTy);
1217 GetElementPtrInst *NewAddress = GetElementPtrInst::Create(
1218 PointeeType: Builder.getInt8Ty(), Ptr: Builder.CreateBitCast(V: Base, DestTy: BaseTy), IdxList: Offsets,
1219 NameStr: "gep.merged", InsertBefore: GEP->getIterator());
1220 LLVM_DEBUG(dbgs() << "Folded GEP: " << *GEP
1221 << "\n new : " << *NewAddress << "\n");
1222 GEP->replaceAllUsesWith(
1223 V: Builder.CreateBitCast(V: NewAddress, DestTy: GEP->getType()));
1224 GEP = NewAddress;
1225 Changed = true;
1226 }
1227 }
1228 Changed |= optimiseOffsets(Offsets: GEP->getOperand(i_nocapture: 1), BB: GEP->getParent(), LI);
1229 return Changed;
1230}
1231
1232bool MVEGatherScatterLowering::runOnFunction(Function &F) {
1233 if (!EnableMaskedGatherScatters)
1234 return false;
1235 auto &TPC = getAnalysis<TargetPassConfig>();
1236 auto &TM = TPC.getTM<TargetMachine>();
1237 auto *ST = &TM.getSubtarget<ARMSubtarget>(F);
1238 if (!ST->hasMVEIntegerOps())
1239 return false;
1240 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1241 DL = &F.getDataLayout();
1242 SmallVector<IntrinsicInst *, 4> Gathers;
1243 SmallVector<IntrinsicInst *, 4> Scatters;
1244
1245 bool Changed = false;
1246
1247 for (BasicBlock &BB : F) {
1248 Changed |= SimplifyInstructionsInBlock(BB: &BB);
1249
1250 for (Instruction &I : BB) {
1251 IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: &I);
1252 if (II && II->getIntrinsicID() == Intrinsic::masked_gather &&
1253 isa<FixedVectorType>(Val: II->getType())) {
1254 Gathers.push_back(Elt: II);
1255 Changed |= optimiseAddress(Address: II->getArgOperand(i: 0), BB: II->getParent(), LI);
1256 } else if (II && II->getIntrinsicID() == Intrinsic::masked_scatter &&
1257 isa<FixedVectorType>(Val: II->getArgOperand(i: 0)->getType())) {
1258 Scatters.push_back(Elt: II);
1259 Changed |= optimiseAddress(Address: II->getArgOperand(i: 1), BB: II->getParent(), LI);
1260 }
1261 }
1262 }
1263 for (IntrinsicInst *I : Gathers) {
1264 Instruction *L = lowerGather(I);
1265 if (L == nullptr)
1266 continue;
1267
1268 // Get rid of any now dead instructions
1269 SimplifyInstructionsInBlock(BB: L->getParent());
1270 Changed = true;
1271 }
1272
1273 for (IntrinsicInst *I : Scatters) {
1274 Instruction *S = lowerScatter(I);
1275 if (S == nullptr)
1276 continue;
1277
1278 // Get rid of any now dead instructions
1279 SimplifyInstructionsInBlock(BB: S->getParent());
1280 Changed = true;
1281 }
1282 return Changed;
1283}
1284