1//===-- AMDGPUPromoteAlloca.cpp - Promote Allocas -------------------------===//
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// Eliminates allocas by either converting them into vectors or by migrating
10// them to local address space.
11//
12// Two passes are exposed by this file:
13// - "promote-alloca-to-vector", which runs early in the pipeline and only
14// promotes to vector. Promotion to vector is almost always profitable
15// except when the alloca is too big and the promotion would result in
16// very high register pressure.
17// - "promote-alloca", which does both promotion to vector and LDS and runs
18// much later in the pipeline. This runs after SROA because promoting to
19// LDS is of course less profitable than getting rid of the alloca or
20// vectorizing it, thus we only want to do it when the only alternative is
21// lowering the alloca to stack.
22//
23// Note that both of them exist for the old and new PMs. The new PM passes are
24// declared in AMDGPU.h and the legacy PM ones are declared here.s
25//
26//===----------------------------------------------------------------------===//
27
28#include "AMDGPU.h"
29#include "AMDGPUTargetMachine.h"
30#include "GCNSubtarget.h"
31#include "Utils/AMDGPUBaseInfo.h"
32#include "llvm/ADT/STLExtras.h"
33#include "llvm/Analysis/CaptureTracking.h"
34#include "llvm/Analysis/InstSimplifyFolder.h"
35#include "llvm/Analysis/InstructionSimplify.h"
36#include "llvm/Analysis/LoopInfo.h"
37#include "llvm/Analysis/ValueTracking.h"
38#include "llvm/CodeGen/TargetPassConfig.h"
39#include "llvm/IR/IRBuilder.h"
40#include "llvm/IR/IntrinsicInst.h"
41#include "llvm/IR/IntrinsicsAMDGPU.h"
42#include "llvm/IR/IntrinsicsR600.h"
43#include "llvm/IR/PatternMatch.h"
44#include "llvm/InitializePasses.h"
45#include "llvm/Pass.h"
46#include "llvm/Support/MathExtras.h"
47#include "llvm/Target/TargetMachine.h"
48#include "llvm/Transforms/Utils/SSAUpdater.h"
49
50#define DEBUG_TYPE "amdgpu-promote-alloca"
51
52using namespace llvm;
53
54namespace {
55
56// We support vector indices of the form ((A * stride) >> shift) + B
57// VarIndex is A, VarMul is stride, VarShift is shift and ConstIndex is B. All
58// parts are optional.
59struct GEPToVectorIndex {
60 WeakTrackingVH VarIndex = nullptr; // defaults to 0
61 ConstantInt *VarMul = nullptr; // defaults to 1
62 ConstantInt *VarShift = nullptr; // defaults to 0
63 ConstantInt *ConstIndex = nullptr; // defaults to 0
64 Value *Full = nullptr;
65};
66
67struct MemTransferInfo {
68 ConstantInt *SrcIndex = nullptr;
69 ConstantInt *DestIndex = nullptr;
70};
71
72// Analysis for planning the different strategies of alloca promotion.
73struct AllocaAnalysis {
74 AllocaInst *Alloca = nullptr;
75 DenseSet<Value *> Pointers;
76 SmallVector<Use *> Uses;
77 unsigned Score = 0;
78 bool HaveSelectOrPHI = false;
79 struct {
80 FixedVectorType *Ty = nullptr;
81 SmallVector<Instruction *> Worklist;
82 SmallVector<Instruction *> UsersToRemove;
83 MapVector<GetElementPtrInst *, GEPToVectorIndex> GEPVectorIdx;
84 MapVector<MemTransferInst *, MemTransferInfo> TransferInfo;
85 } Vector;
86 struct {
87 bool Enable = false;
88 SmallVector<User *> Worklist;
89 } LDS;
90
91 explicit AllocaAnalysis(AllocaInst *Alloca) : Alloca(Alloca) {}
92};
93
94// Shared implementation which can do both promotion to vector and to LDS.
95class AMDGPUPromoteAllocaImpl {
96private:
97 const AMDGPUOptions &CLOpts;
98 const TargetMachine &TM;
99 LoopInfo &LI;
100 Module &Mod;
101 const DataLayout &DL;
102
103 // FIXME: This should be per-kernel.
104 uint32_t LocalMemLimit = 0;
105 uint32_t CurrentLocalMemUsage = 0;
106 unsigned MaxVGPRs;
107 unsigned VGPRBudgetRatio;
108 unsigned MaxVectorRegs;
109
110 bool IsAMDGCN = false;
111 bool IsAMDHSA = false;
112
113 std::pair<Value *, Value *> getLocalSizeYZ(IRBuilder<> &Builder);
114 Value *getWorkitemID(IRBuilder<> &Builder, unsigned N);
115
116 bool collectAllocaUses(AllocaAnalysis &AA) const;
117
118 /// Val is a derived pointer from Alloca. OpIdx0/OpIdx1 are the operand
119 /// indices to an instruction with 2 pointer inputs (e.g. select, icmp).
120 /// Returns true if both operands are derived from the same alloca. Val should
121 /// be the same value as one of the input operands of UseInst.
122 bool binaryOpIsDerivedFromSameAlloca(Value *Alloca, Value *Val,
123 Instruction *UseInst, int OpIdx0,
124 int OpIdx1) const;
125
126 /// Check whether we have enough local memory for promotion.
127 bool hasSufficientLocalMem(const Function &F);
128
129 FixedVectorType *getVectorTypeForAlloca(Type *AllocaTy) const;
130 void analyzePromoteToVector(AllocaAnalysis &AA) const;
131 void promoteAllocaToVector(AllocaAnalysis &AA);
132 void analyzePromoteToLDS(AllocaAnalysis &AA) const;
133 bool tryPromoteAllocaToLDS(AllocaAnalysis &AA, bool SufficientLDS,
134 SetVector<IntrinsicInst *> &DeferredIntrs);
135 void
136 finishDeferredAllocaToLDSPromotion(SetVector<IntrinsicInst *> &DeferredIntrs);
137
138 void scoreAlloca(AllocaAnalysis &AA) const;
139
140 void setFunctionLimits(const Function &F);
141
142public:
143 AMDGPUPromoteAllocaImpl(TargetMachine &TM, Module &M, LoopInfo &LI)
144 : CLOpts(static_cast<const AMDGPUTargetMachine &>(TM).getCLOpts()),
145 TM(TM), LI(LI), Mod(M), DL(M.getDataLayout()) {
146 const Triple &TT = M.getTargetTriple();
147 IsAMDGCN = TT.isAMDGCN();
148 IsAMDHSA = TT.getOS() == Triple::AMDHSA;
149 }
150
151 bool run(Function &F, bool PromoteToLDS);
152};
153
154// FIXME: This can create globals so should be a module pass.
155class AMDGPUPromoteAlloca : public FunctionPass {
156public:
157 static char ID;
158
159 AMDGPUPromoteAlloca() : FunctionPass(ID) {}
160
161 bool runOnFunction(Function &F) override {
162 if (skipFunction(F))
163 return false;
164 if (auto *TPC = getAnalysisIfAvailable<TargetPassConfig>())
165 return AMDGPUPromoteAllocaImpl(
166 TPC->getTM<TargetMachine>(), *F.getParent(),
167 getAnalysis<LoopInfoWrapperPass>().getLoopInfo())
168 .run(F, /*PromoteToLDS*/ true);
169 return false;
170 }
171
172 StringRef getPassName() const override { return "AMDGPU Promote Alloca"; }
173
174 void getAnalysisUsage(AnalysisUsage &AU) const override {
175 AU.setPreservesCFG();
176 AU.addRequired<LoopInfoWrapperPass>();
177 FunctionPass::getAnalysisUsage(AU);
178 }
179};
180
181static unsigned getMaxVGPRs(unsigned LDSBytes, const TargetMachine &TM,
182 const Function &F) {
183 const GCNSubtarget &ST = TM.getSubtarget<GCNSubtarget>(F);
184
185 unsigned DynamicVGPRBlockSize = AMDGPU::getDynamicVGPRBlockSize(F);
186 unsigned MaxVGPRs = ST.getMaxNumVGPRs(
187 WavesPerEU: ST.getWavesPerEU(FlatWorkGroupSizes: ST.getFlatWorkGroupSizes(F), LDSBytes, F).first,
188 DynamicVGPRBlockSize);
189
190 // A DVGPR wave launches with a single VGPR block allocated.
191 if (DynamicVGPRBlockSize != 0 &&
192 AMDGPU::isEntryFunctionCC(CC: F.getCallingConv()))
193 MaxVGPRs = std::min(a: MaxVGPRs, b: DynamicVGPRBlockSize);
194
195 // A non-entry function has only 32 caller preserved registers.
196 // Do not promote alloca which will force spilling unless we know the function
197 // will be inlined.
198 if (!F.hasFnAttribute(Kind: Attribute::AlwaysInline) &&
199 !AMDGPU::isEntryFunctionCC(CC: F.getCallingConv()))
200 MaxVGPRs = std::min(a: MaxVGPRs, b: 32u);
201 return MaxVGPRs;
202}
203
204} // end anonymous namespace
205
206char AMDGPUPromoteAlloca::ID = 0;
207
208INITIALIZE_PASS_BEGIN(AMDGPUPromoteAlloca, DEBUG_TYPE,
209 "AMDGPU promote alloca to vector or LDS", false, false)
210// Move LDS uses from functions to kernels before promote alloca for accurate
211// estimation of LDS available
212INITIALIZE_PASS_DEPENDENCY(AMDGPULowerModuleLDSLegacy)
213INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
214INITIALIZE_PASS_END(AMDGPUPromoteAlloca, DEBUG_TYPE,
215 "AMDGPU promote alloca to vector or LDS", false, false)
216
217char &llvm::AMDGPUPromoteAllocaID = AMDGPUPromoteAlloca::ID;
218
219PreservedAnalyses AMDGPUPromoteAllocaPass::run(Function &F,
220 FunctionAnalysisManager &AM) {
221 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
222 bool Changed = AMDGPUPromoteAllocaImpl(TM, *F.getParent(), LI)
223 .run(F, /*PromoteToLDS=*/true);
224 if (Changed) {
225 PreservedAnalyses PA;
226 PA.preserveSet<CFGAnalyses>();
227 return PA;
228 }
229 return PreservedAnalyses::all();
230}
231
232PreservedAnalyses
233AMDGPUPromoteAllocaToVectorPass::run(Function &F, FunctionAnalysisManager &AM) {
234 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
235 bool Changed = AMDGPUPromoteAllocaImpl(TM, *F.getParent(), LI)
236 .run(F, /*PromoteToLDS=*/false);
237 if (Changed) {
238 PreservedAnalyses PA;
239 PA.preserveSet<CFGAnalyses>();
240 return PA;
241 }
242 return PreservedAnalyses::all();
243}
244
245FunctionPass *llvm::createAMDGPUPromoteAlloca() {
246 return new AMDGPUPromoteAlloca();
247}
248
249bool AMDGPUPromoteAllocaImpl::collectAllocaUses(AllocaAnalysis &AA) const {
250 const auto RejectUser = [&](Instruction *Inst, Twine Msg) {
251 LLVM_DEBUG(dbgs() << " Cannot promote alloca: " << Msg << "\n"
252 << " " << *Inst << "\n");
253 return false;
254 };
255
256 SmallVector<Instruction *, 4> WorkList({AA.Alloca});
257 while (!WorkList.empty()) {
258 auto *Cur = WorkList.pop_back_val();
259 if (find(Range&: AA.Pointers, Val: Cur) != AA.Pointers.end())
260 continue;
261 AA.Pointers.insert(V: Cur);
262 for (auto &U : Cur->uses()) {
263 auto *Inst = cast<Instruction>(Val: U.getUser());
264 if (isa<StoreInst>(Val: Inst)) {
265 if (U.getOperandNo() != StoreInst::getPointerOperandIndex()) {
266 return RejectUser(Inst, "pointer escapes via store");
267 }
268 }
269 AA.Uses.push_back(Elt: &U);
270
271 if (isa<GetElementPtrInst>(Val: U.getUser())) {
272 WorkList.push_back(Elt: Inst);
273 } else if (auto *SI = dyn_cast<SelectInst>(Val: Inst)) {
274 // Only promote a select if we know that the other select operand is
275 // from another pointer that will also be promoted.
276 if (!binaryOpIsDerivedFromSameAlloca(Alloca: AA.Alloca, Val: Cur, UseInst: SI, OpIdx0: 1, OpIdx1: 2))
277 return RejectUser(Inst, "select from mixed objects");
278 WorkList.push_back(Elt: Inst);
279 AA.HaveSelectOrPHI = true;
280 } else if (auto *Phi = dyn_cast<PHINode>(Val: Inst)) {
281 // Repeat for phis.
282
283 // TODO: Handle more complex cases. We should be able to replace loops
284 // over arrays.
285 switch (Phi->getNumIncomingValues()) {
286 case 1:
287 break;
288 case 2:
289 if (!binaryOpIsDerivedFromSameAlloca(Alloca: AA.Alloca, Val: Cur, UseInst: Phi, OpIdx0: 0, OpIdx1: 1))
290 return RejectUser(Inst, "phi from mixed objects");
291 break;
292 default:
293 return RejectUser(Inst, "phi with too many operands");
294 }
295
296 WorkList.push_back(Elt: Inst);
297 AA.HaveSelectOrPHI = true;
298 }
299 }
300 }
301 return true;
302}
303
304void AMDGPUPromoteAllocaImpl::scoreAlloca(AllocaAnalysis &AA) const {
305 LLVM_DEBUG(dbgs() << "Scoring: " << *AA.Alloca << "\n");
306 unsigned Score = 0;
307 // Increment score by one for each user + a bonus for users within loops.
308 for (auto *U : AA.Uses) {
309 Instruction *Inst = cast<Instruction>(Val: U->getUser());
310 if (isa<GetElementPtrInst>(Val: Inst) || isa<SelectInst>(Val: Inst) ||
311 isa<PHINode>(Val: Inst))
312 continue;
313 unsigned UserScore = 1 + (CLOpts.promote_alloca_vector_loop_user_weight *
314 LI.getLoopDepth(BB: Inst->getParent()));
315 LLVM_DEBUG(dbgs() << " [+" << UserScore << "]:\t" << *Inst << "\n");
316 Score += UserScore;
317 }
318 LLVM_DEBUG(dbgs() << " => Final Score:" << Score << "\n");
319 AA.Score = Score;
320}
321
322void AMDGPUPromoteAllocaImpl::setFunctionLimits(const Function &F) {
323 // Load per function limits, overriding with global options where appropriate.
324 // R600 register tuples/aliasing are fragile with large vector promotions so
325 // apply architecture specific limit here.
326 const int R600MaxVectorRegs = 16;
327 MaxVectorRegs = CLOpts.promote_alloca_to_vector_max_regs.value_or(
328 u: F.getFnAttributeAsParsedInteger(
329 Kind: "amdgpu-promote-alloca-to-vector-max-regs",
330 Default: IsAMDGCN ? 32 : R600MaxVectorRegs));
331 VGPRBudgetRatio = CLOpts.promote_alloca_to_vector_vgpr_ratio.value_or(
332 u: F.getFnAttributeAsParsedInteger(
333 Kind: "amdgpu-promote-alloca-to-vector-vgpr-ratio", Default: 4));
334}
335
336bool AMDGPUPromoteAllocaImpl::run(Function &F, bool PromoteToLDS) {
337 if (!CLOpts.promote_alloca_to_lds && !CLOpts.promote_alloca_to_vector)
338 return false;
339
340 bool SufficientLDS = PromoteToLDS && hasSufficientLocalMem(F);
341 MaxVGPRs = IsAMDGCN ? getMaxVGPRs(LDSBytes: CurrentLocalMemUsage, TM, F) : 128;
342 setFunctionLimits(F);
343
344 unsigned VectorizationBudget =
345 (CLOpts.promote_alloca_to_vector_limit
346 ? CLOpts.promote_alloca_to_vector_limit * 8
347 : (MaxVGPRs * 32)) /
348 VGPRBudgetRatio;
349
350 std::vector<AllocaAnalysis> Allocas;
351 for (Instruction &I : F.getEntryBlock()) {
352 if (AllocaInst *AI = dyn_cast<AllocaInst>(Val: &I)) {
353 // Array allocations are probably not worth handling, since an allocation
354 // of the array type is the canonical form.
355 if (!AI->isStaticAlloca() || AI->isArrayAllocation())
356 continue;
357
358 LLVM_DEBUG(dbgs() << "Analyzing: " << *AI << '\n');
359
360 AllocaAnalysis AA{AI};
361 if (collectAllocaUses(AA)) {
362 analyzePromoteToVector(AA);
363 if (PromoteToLDS)
364 analyzePromoteToLDS(AA);
365 if (AA.Vector.Ty || AA.LDS.Enable) {
366 scoreAlloca(AA);
367 Allocas.push_back(x: std::move(AA));
368 }
369 }
370 }
371 }
372
373 stable_sort(Range&: Allocas,
374 C: [](const auto &A, const auto &B) { return A.Score > B.Score; });
375
376 // clang-format off
377 LLVM_DEBUG(
378 dbgs() << "Sorted Worklist:\n";
379 for (const auto &AA : Allocas)
380 dbgs() << " " << *AA.Alloca << "\n";
381 );
382 // clang-format on
383
384 bool Changed = false;
385 SetVector<IntrinsicInst *> DeferredIntrs;
386 for (AllocaAnalysis &AA : Allocas) {
387 if (AA.Vector.Ty) {
388 std::optional<TypeSize> Size = AA.Alloca->getAllocationSize(DL);
389 assert(Size); // Expected to succeed on non-array alloca.
390 const unsigned AllocaCost = Size->getFixedValue() * 8;
391 // First, check if we have enough budget to vectorize this alloca.
392 if (AllocaCost <= VectorizationBudget) {
393 promoteAllocaToVector(AA);
394 Changed = true;
395 assert((VectorizationBudget - AllocaCost) < VectorizationBudget &&
396 "Underflow!");
397 VectorizationBudget -= AllocaCost;
398 LLVM_DEBUG(dbgs() << " Remaining vectorization budget:"
399 << VectorizationBudget << "\n");
400 continue;
401 } else {
402 LLVM_DEBUG(dbgs() << "Alloca too big for vectorization (size:"
403 << AllocaCost << ", budget:" << VectorizationBudget
404 << "): " << *AA.Alloca << "\n");
405 }
406 }
407
408 if (AA.LDS.Enable &&
409 tryPromoteAllocaToLDS(AA, SufficientLDS, DeferredIntrs))
410 Changed = true;
411 }
412 finishDeferredAllocaToLDSPromotion(DeferredIntrs);
413
414 // NOTE: tryPromoteAllocaToVector removes the alloca, so Allocas contains
415 // dangling pointers. If we want to reuse it past this point, the loop above
416 // would need to be updated to remove successfully promoted allocas.
417
418 return Changed;
419}
420
421// Checks if the instruction I is a memset user of the alloca AI that we can
422// deal with. Currently, only non-volatile memsets that affect the whole alloca
423// are handled.
424static bool isSupportedMemset(MemSetInst *I, AllocaInst *AI,
425 const DataLayout &DL) {
426 using namespace PatternMatch;
427 // For now we only care about non-volatile memsets that affect the whole type
428 // (start at index 0 and fill the whole alloca).
429 //
430 // TODO: Now that we moved to PromoteAlloca we could handle any memsets
431 // (except maybe volatile ones?) - we just need to use shufflevector if it
432 // only affects a subset of the vector.
433 const unsigned Size = DL.getTypeStoreSize(Ty: AI->getAllocatedType());
434 return I->getOperand(i_nocapture: 0) == AI &&
435 match(V: I->getOperand(i_nocapture: 2), P: m_SpecificInt(V: Size)) && !I->isVolatile();
436}
437
438static Value *calculateVectorIndex(Value *Ptr, AllocaAnalysis &AA) {
439 IRBuilder<> B(*AA.Alloca->getModule());
440
441 Ptr = Ptr->stripPointerCasts();
442 if (Ptr == AA.Alloca)
443 return B.getInt32(C: 0);
444
445 auto *GEP = cast<GetElementPtrInst>(Val: Ptr);
446 auto I = AA.Vector.GEPVectorIdx.find(Key: GEP);
447 assert(I != AA.Vector.GEPVectorIdx.end() && "Must have entry for GEP!");
448
449 if (!I->second.Full) {
450 Value *Result = nullptr;
451 B.SetInsertPoint(GEP);
452
453 if (I->second.VarIndex) {
454 Result = I->second.VarIndex;
455 Result = B.CreateSExtOrTrunc(V: Result, DestTy: B.getInt32Ty());
456
457 if (I->second.VarMul)
458 Result = B.CreateMul(LHS: Result, RHS: I->second.VarMul);
459
460 if (I->second.VarShift)
461 Result = B.CreateAShr(LHS: Result, RHS: I->second.VarShift, Name: "", /*isExact*/ true);
462 }
463
464 if (I->second.ConstIndex) {
465 if (Result)
466 Result = B.CreateAdd(LHS: Result, RHS: I->second.ConstIndex);
467 else
468 Result = I->second.ConstIndex;
469 }
470
471 if (!Result)
472 Result = B.getInt32(C: 0);
473
474 I->second.Full = Result;
475 }
476
477 return I->second.Full;
478}
479
480static std::optional<GEPToVectorIndex>
481computeGEPToVectorIndex(GetElementPtrInst *GEP, AllocaInst *Alloca,
482 Type *VecElemTy, const DataLayout &DL) {
483 // TODO: Extracting a "multiple of X" from a GEP might be a useful generic
484 // helper.
485 LLVMContext &Ctx = GEP->getContext();
486 unsigned BW = DL.getIndexTypeSizeInBits(Ty: GEP->getType());
487 SmallMapVector<Value *, APInt, 4> VarOffsets;
488 APInt ConstOffset(BW, 0);
489
490 // Walk backwards through nested GEPs to collect both constant and variable
491 // offsets, so that nested vector GEP chains can be lowered in one step.
492 //
493 // Given this IR fragment as input:
494 //
495 // %0 = alloca [10 x <2 x i32>], align 8, addrspace(5)
496 // %1 = getelementptr [10 x <2 x i32>], ptr addrspace(5) %0, i32 0, i32 %j
497 // %2 = getelementptr i8, ptr addrspace(5) %1, i32 4
498 // %3 = load i32, ptr addrspace(5) %2, align 4
499 //
500 // Combine both GEP operations in a single pass, producing:
501 // BasePtr = %0
502 // ConstOffset = 4
503 // VarOffsets = { %j -> element_size(<2 x i32>) }
504 //
505 // That lets us emit a single buffer_load directly into a VGPR, without ever
506 // allocating scratch memory for the intermediate pointer.
507 Value *CurPtr = GEP;
508 while (auto *CurGEP = dyn_cast<GetElementPtrInst>(Val: CurPtr)) {
509 if (!CurGEP->collectOffset(DL, BitWidth: BW, VariableOffsets&: VarOffsets, ConstantOffset&: ConstOffset))
510 return {};
511
512 // Move to the next outer pointer.
513 CurPtr = CurGEP->getPointerOperand();
514 }
515
516 assert(CurPtr == Alloca && "GEP not based on alloca");
517
518 int64_t VecElemSize = DL.getTypeAllocSize(Ty: VecElemTy);
519 if (VarOffsets.size() > 1)
520 return {};
521
522 // We support vector indices of the form ((VarIndex * stride) >> shift) + B.
523 // IndexQuot represents B. Check that the constant offset is a multiple
524 // of the vector element size.
525 if (ConstOffset.srem(RHS: VecElemSize) != 0)
526 return {};
527 APInt IndexQuot = ConstOffset.sdiv(RHS: VecElemSize);
528
529 GEPToVectorIndex Result;
530
531 if (!ConstOffset.isZero())
532 Result.ConstIndex = ConstantInt::get(Context&: Ctx, V: IndexQuot.sextOrTrunc(width: BW));
533
534 // If there are no variable offsets, only a constant offset, then we're done.
535 if (VarOffsets.empty())
536 return Result;
537
538 // Scale is the stride in the (A * stride) part. Check that there is only one
539 // variable offset and extract the scale factor.
540 const auto &VarOffset = VarOffsets.front();
541 auto ScaleOpt = VarOffset.second.tryZExtValue();
542 if (!ScaleOpt || *ScaleOpt == 0)
543 return {};
544
545 uint64_t Scale = *ScaleOpt;
546 Result.VarIndex = VarOffset.first;
547 auto *OffsetType = dyn_cast<IntegerType>(Val: Result.VarIndex->getType());
548 if (!OffsetType)
549 return {};
550
551 // The vector index for the variable part is: VarIndex * Scale / VecElemSize.
552 if (Scale >= (uint64_t)VecElemSize) {
553 if (Scale % VecElemSize != 0)
554 return {};
555
556 // Scale is a multiple of VecElemSize, so the index is just: VarIndex *
557 // (Scale / VecElemSize).
558 uint64_t VarMul = Scale / VecElemSize;
559 // Only the multiplier is needed.
560 if (VarMul != 1)
561 Result.VarMul = ConstantInt::get(Context&: Ctx, V: APInt(BW, VarMul));
562 } else {
563 if ((uint64_t)VecElemSize % Scale != 0)
564 return {};
565
566 // VecElemSize is a multiple of Scale, so the index is just: VarIndex /
567 // (VecElemSize / Scale).
568 uint64_t Divisor = VecElemSize / Scale;
569 // The divisor must be a power of 2 so we can use a right shift.
570 if (!isPowerOf2_64(Value: Divisor))
571 return {};
572
573 // VarIndex must be known to be divisible by that divisor.
574 KnownBits KB = computeKnownBits(V: VarOffset.first, DL);
575 if (KB.countMinTrailingZeros() < Log2_64(Value: Divisor))
576 return {};
577
578 Result.VarShift = ConstantInt::get(Context&: Ctx, V: APInt(BW, Log2_64(Value: Divisor)));
579 }
580
581 return Result;
582}
583
584/// Promotes a single user of the alloca to a vector form.
585///
586/// \param Inst Instruction to be promoted.
587/// \param DL Module Data Layout.
588/// \param AA Alloca Analysis.
589/// \param VecStoreSize Size of \p VectorTy in bytes.
590/// \param ElementSize Size of \p VectorTy element type in bytes.
591/// \param CurVal Current value of the vector (e.g. last stored value)
592/// \param[out] DeferredLoads \p Inst is added to this vector if it can't
593/// be promoted now. This happens when promoting requires \p
594/// CurVal, but \p CurVal is nullptr.
595/// \return the stored value if \p Inst would have written to the alloca, or
596/// nullptr otherwise.
597static Value *promoteAllocaUserToVector(Instruction *Inst, const DataLayout &DL,
598 AllocaAnalysis &AA,
599 unsigned VecStoreSize,
600 unsigned ElementSize,
601 function_ref<Value *()> GetCurVal) {
602 // Note: we use InstSimplifyFolder because it can leverage the DataLayout
603 // to do more folding, especially in the case of vector splats.
604 IRBuilder<InstSimplifyFolder> Builder(Inst->getIterator(),
605 InstSimplifyFolder(DL));
606
607 Type *VecEltTy = AA.Vector.Ty->getElementType();
608
609 switch (Inst->getOpcode()) {
610 case Instruction::Load: {
611 Value *CurVal = GetCurVal();
612 Value *Index =
613 calculateVectorIndex(Ptr: cast<LoadInst>(Val: Inst)->getPointerOperand(), AA);
614
615 // We're loading the full vector.
616 Type *AccessTy = Inst->getType();
617 TypeSize AccessSize = DL.getTypeStoreSize(Ty: AccessTy);
618 if (Constant *CI = dyn_cast<Constant>(Val: Index)) {
619 if (CI->isNullValue() && AccessSize == VecStoreSize) {
620 Inst->replaceAllUsesWith(
621 V: Builder.CreateBitPreservingCastChain(DL, V: CurVal, NewTy: AccessTy));
622 return nullptr;
623 }
624 }
625
626 // Loading a subvector, or a scalar that spans several elements.
627 TypeSize EltSize = DL.getTypeStoreSize(Ty: VecEltTy);
628 assert(AccessSize.isKnownMultipleOf(EltSize) &&
629 "promotable access must cover a whole number of elements");
630 const unsigned NumLoadedElts = AccessSize / EltSize;
631 if (NumLoadedElts > 1) {
632 auto *SubVecTy = FixedVectorType::get(ElementType: VecEltTy, NumElts: NumLoadedElts);
633 assert(DL.getTypeStoreSize(SubVecTy) == DL.getTypeStoreSize(AccessTy));
634
635 // If idx is dynamic, then sandwich load with bitcasts.
636 // ie. VectorTy SubVecTy AccessTy
637 // <64 x i8> -> <16 x i8> <8 x i16>
638 // <64 x i8> -> <4 x i128> -> i128 -> <8 x i16>
639 // Extracting subvector with dynamic index has very large expansion in
640 // the amdgpu backend. Limit to pow2.
641 FixedVectorType *VectorTy = AA.Vector.Ty;
642 TypeSize NumBits = DL.getTypeStoreSize(Ty: SubVecTy) * 8u;
643 uint64_t LoadAlign = cast<LoadInst>(Val: Inst)->getAlign().value();
644 bool IsAlignedLoad = NumBits <= (LoadAlign * 8u);
645 unsigned TotalNumElts = VectorTy->getNumElements();
646 bool IsProperlyDivisible = TotalNumElts % NumLoadedElts == 0;
647 if (!isa<ConstantInt>(Val: Index) &&
648 llvm::isPowerOf2_32(Value: SubVecTy->getNumElements()) &&
649 IsProperlyDivisible && IsAlignedLoad) {
650 IntegerType *NewElemTy = Builder.getIntNTy(N: NumBits);
651 const unsigned NewNumElts =
652 DL.getTypeStoreSize(Ty: VectorTy) * 8u / NumBits;
653 const unsigned LShrAmt = llvm::Log2_32(Value: SubVecTy->getNumElements());
654 FixedVectorType *BitCastTy =
655 FixedVectorType::get(ElementType: NewElemTy, NumElts: NewNumElts);
656 Value *BCVal =
657 Builder.CreateBitPreservingCastChain(DL, V: CurVal, NewTy: BitCastTy);
658 Value *NewIdx = Builder.CreateLShr(
659 LHS: Index, RHS: ConstantInt::get(Ty: Index->getType(), V: LShrAmt));
660 Value *ExtVal = Builder.CreateExtractElement(Vec: BCVal, Idx: NewIdx);
661 Value *BCOut =
662 Builder.CreateBitPreservingCastChain(DL, V: ExtVal, NewTy: AccessTy);
663 Inst->replaceAllUsesWith(V: BCOut);
664 return nullptr;
665 }
666
667 Value *SubVec = PoisonValue::get(T: SubVecTy);
668 for (unsigned K = 0; K < NumLoadedElts; ++K) {
669 Value *CurIdx =
670 Builder.CreateAdd(LHS: Index, RHS: ConstantInt::get(Ty: Index->getType(), V: K));
671 SubVec = Builder.CreateInsertElement(
672 Vec: SubVec, NewElt: Builder.CreateExtractElement(Vec: CurVal, Idx: CurIdx), Idx: K);
673 }
674
675 Inst->replaceAllUsesWith(
676 V: Builder.CreateBitPreservingCastChain(DL, V: SubVec, NewTy: AccessTy));
677 return nullptr;
678 }
679
680 // We're loading one element.
681 Value *ExtractElement = Builder.CreateExtractElement(Vec: CurVal, Idx: Index);
682 if (AccessTy != VecEltTy)
683 ExtractElement = Builder.CreateBitOrPointerCast(V: ExtractElement, DestTy: AccessTy);
684
685 Inst->replaceAllUsesWith(V: ExtractElement);
686 return nullptr;
687 }
688 case Instruction::Store: {
689 // For stores, it's a bit trickier and it depends on whether we're storing
690 // the full vector or not. If we're storing the full vector, we don't need
691 // to know the current value. If this is a store of a single element, we
692 // need to know the value.
693 StoreInst *SI = cast<StoreInst>(Val: Inst);
694 Value *Index = calculateVectorIndex(Ptr: SI->getPointerOperand(), AA);
695 Value *Val = SI->getValueOperand();
696
697 // We're storing the full vector, we can handle this without knowing CurVal.
698 Type *AccessTy = Val->getType();
699 TypeSize AccessSize = DL.getTypeStoreSize(Ty: AccessTy);
700 if (Constant *CI = dyn_cast<Constant>(Val: Index)) {
701 if (CI->isNullValue() && AccessSize == VecStoreSize) {
702 Value *Result =
703 Builder.CreateBitPreservingCastChain(DL, V: Val, NewTy: AA.Vector.Ty);
704 // If Result is a load from this alloca, it will later be RAUW'd and
705 // deleted. The SSAUpdater holds a raw Value* that RAUW doesn't update,
706 // leaving a dangling pointer. Wrap in a freeze to create a fresh value
707 // the SSAUpdater can safely hold; the freeze's operand is a proper IR
708 // use that RAUW does update.
709 if (isa<LoadInst>(Val: Result))
710 Result = Builder.CreateFreeze(V: Result);
711 return Result;
712 }
713 }
714
715 // Storing a subvector, or a scalar that spans several elements.
716 TypeSize EltSize = DL.getTypeStoreSize(Ty: VecEltTy);
717 assert(AccessSize.isKnownMultipleOf(EltSize) &&
718 "promotable access must cover a whole number of elements");
719 const unsigned NumWrittenElts = AccessSize / EltSize;
720 if (NumWrittenElts > 1) {
721 const unsigned NumVecElts = AA.Vector.Ty->getNumElements();
722 auto *SubVecTy = FixedVectorType::get(ElementType: VecEltTy, NumElts: NumWrittenElts);
723 assert(DL.getTypeStoreSize(SubVecTy) == DL.getTypeStoreSize(AccessTy));
724
725 Val = Builder.CreateBitPreservingCastChain(DL, V: Val, NewTy: SubVecTy);
726 Value *CurVec = GetCurVal();
727 for (unsigned K = 0, NumElts = std::min(a: NumWrittenElts, b: NumVecElts);
728 K < NumElts; ++K) {
729 Value *CurIdx =
730 Builder.CreateAdd(LHS: Index, RHS: ConstantInt::get(Ty: Index->getType(), V: K));
731 CurVec = Builder.CreateInsertElement(
732 Vec: CurVec, NewElt: Builder.CreateExtractElement(Vec: Val, Idx: K), Idx: CurIdx);
733 }
734 return CurVec;
735 }
736
737 if (Val->getType() != VecEltTy)
738 Val = Builder.CreateBitOrPointerCast(V: Val, DestTy: VecEltTy);
739 return Builder.CreateInsertElement(Vec: GetCurVal(), NewElt: Val, Idx: Index);
740 }
741 case Instruction::Call: {
742 if (auto *MTI = dyn_cast<MemTransferInst>(Val: Inst)) {
743 // For memcpy, we need to know curval.
744 ConstantInt *Length = cast<ConstantInt>(Val: MTI->getLength());
745 unsigned NumCopied = Length->getZExtValue() / ElementSize;
746 MemTransferInfo *TI = &AA.Vector.TransferInfo[MTI];
747 unsigned SrcBegin = TI->SrcIndex->getZExtValue();
748 unsigned DestBegin = TI->DestIndex->getZExtValue();
749
750 SmallVector<int> Mask;
751 for (unsigned Idx = 0; Idx < AA.Vector.Ty->getNumElements(); ++Idx) {
752 if (Idx >= DestBegin && Idx < DestBegin + NumCopied) {
753 Mask.push_back(Elt: SrcBegin < AA.Vector.Ty->getNumElements()
754 ? SrcBegin++
755 : PoisonMaskElem);
756 } else {
757 Mask.push_back(Elt: Idx);
758 }
759 }
760
761 return Builder.CreateShuffleVector(V: GetCurVal(), Mask);
762 }
763
764 if (auto *MSI = dyn_cast<MemSetInst>(Val: Inst)) {
765 // For memset, we don't need to know the previous value because we
766 // currently only allow memsets that cover the whole alloca.
767 Value *Elt = MSI->getOperand(i_nocapture: 1);
768 const unsigned BytesPerElt = DL.getTypeStoreSize(Ty: VecEltTy);
769 if (BytesPerElt > 1) {
770 Value *EltBytes = Builder.CreateVectorSplat(NumElts: BytesPerElt, V: Elt);
771
772 // If the element type of the vector is a pointer, we need to first cast
773 // to an integer, then use a PtrCast.
774 if (VecEltTy->isPointerTy()) {
775 Type *PtrInt = Builder.getIntNTy(N: BytesPerElt * 8);
776 Elt = Builder.CreateBitCast(V: EltBytes, DestTy: PtrInt);
777 Elt = Builder.CreateIntToPtr(V: Elt, DestTy: VecEltTy);
778 } else
779 Elt = Builder.CreateBitCast(V: EltBytes, DestTy: VecEltTy);
780 }
781
782 return Builder.CreateVectorSplat(EC: AA.Vector.Ty->getElementCount(), V: Elt);
783 }
784
785 if (auto *Intr = dyn_cast<IntrinsicInst>(Val: Inst)) {
786 if (Intr->getIntrinsicID() == Intrinsic::objectsize) {
787 Intr->replaceAllUsesWith(
788 V: Builder.getIntN(N: Intr->getType()->getIntegerBitWidth(),
789 C: DL.getTypeAllocSize(Ty: AA.Vector.Ty)));
790 return nullptr;
791 }
792 }
793
794 llvm_unreachable("Unsupported call when promoting alloca to vector");
795 }
796
797 default:
798 llvm_unreachable("Inconsistency in instructions promotable to vector");
799 }
800
801 llvm_unreachable("Did not return after promoting instruction!");
802}
803
804static bool isSupportedAccessType(FixedVectorType *VecTy, Type *AccessTy,
805 const DataLayout &DL) {
806 // An access that covers several elements can work if its size is a multiple
807 // of the size of the alloca's vector element type, since it can be split
808 // across consecutive elements. This covers accesses by a vector type, as well
809 // as scalar accesses that are wider than one element, which happens when an
810 // object is written one element at a time but read back in wider pieces.
811 //
812 // Examples:
813 // - VecTy = <8 x float>, AccessTy = <4 x float> -> OK
814 // - VecTy = <4 x double>, AccessTy = <2 x float> -> OK
815 // - VecTy = <4 x double>, AccessTy = <3 x float> -> NOT OK
816 // - 3*32 is not a multiple of 64
817 // - VecTy = <8 x i32>, AccessTy = i64 -> OK
818 //
819 // We could handle more complicated cases, but it'd make things a lot more
820 // complicated.
821 if (isa<FixedVectorType>(Val: AccessTy) || AccessTy->isIntegerTy() ||
822 AccessTy->isFloatingPointTy()) {
823 TypeSize AccTS = DL.getTypeStoreSize(Ty: AccessTy);
824 TypeSize VecTS = DL.getTypeStoreSize(Ty: VecTy->getElementType());
825 // If the type size and the store size don't match, we would need to do more
826 // than just bitcast to translate between an extracted/insertable subvectors
827 // and the accessed value.
828 if (AccTS * 8 == DL.getTypeSizeInBits(Ty: AccessTy) && AccTS > VecTS &&
829 AccTS.isKnownMultipleOf(RHS: VecTS))
830 return true;
831 }
832
833 // An access that covers exactly one element only needs a cast.
834 return CastInst::isBitOrNoopPointerCastable(SrcTy: VecTy->getElementType(), DestTy: AccessTy,
835 DL);
836}
837
838/// Iterates over an instruction worklist that may contain multiple instructions
839/// from the same basic block, but in a different order.
840template <typename InstContainer>
841static void forEachWorkListItem(const InstContainer &WorkList,
842 std::function<void(Instruction *)> Fn) {
843 // Bucket up uses of the alloca by the block they occur in.
844 // This is important because we have to handle multiple defs/uses in a block
845 // ourselves: SSAUpdater is purely for cross-block references.
846 DenseMap<BasicBlock *, SmallDenseSet<Instruction *>> UsesByBlock;
847 for (Instruction *User : WorkList)
848 UsesByBlock[User->getParent()].insert(V: User);
849
850 for (Instruction *User : WorkList) {
851 BasicBlock *BB = User->getParent();
852 auto &BlockUses = UsesByBlock[BB];
853
854 // Already processed, skip.
855 if (BlockUses.empty())
856 continue;
857
858 // Only user in the block, directly process it.
859 if (BlockUses.size() == 1) {
860 Fn(User);
861 continue;
862 }
863
864 // Multiple users in the block, do a linear scan to see users in order.
865 for (Instruction &Inst : *BB) {
866 if (!BlockUses.contains(V: &Inst))
867 continue;
868
869 Fn(&Inst);
870 }
871
872 // Clear the block so we know it's been processed.
873 BlockUses.clear();
874 }
875}
876
877/// Find an insert point after an alloca, after all other allocas clustered at
878/// the start of the block.
879static BasicBlock::iterator skipToNonAllocaInsertPt(BasicBlock &BB,
880 BasicBlock::iterator I) {
881 for (BasicBlock::iterator E = BB.end(); I != E && isa<AllocaInst>(Val: *I); ++I)
882 ;
883 return I;
884}
885
886/// Peel nested aggregates down to a single uniform element type, multiplying
887/// NumElems by the element count of each layer peeled.
888static Type *peelAggregateToElementType(Type *Ty, uint64_t &NumElems) {
889 while (true) {
890 if (auto *ArrayTy = dyn_cast<ArrayType>(Val: Ty)) {
891 NumElems *= ArrayTy->getNumElements();
892 Ty = ArrayTy->getElementType();
893 continue;
894 }
895
896 auto *StructTy = dyn_cast<StructType>(Val: Ty);
897 if (!StructTy || !StructTy->containsHomogeneousTypes())
898 break;
899
900 NumElems *= StructTy->getNumElements();
901 Ty = StructTy->getElementType(N: 0);
902 }
903
904 return Ty;
905}
906
907FixedVectorType *
908AMDGPUPromoteAllocaImpl::getVectorTypeForAlloca(Type *AllocaTy) const {
909 if (!CLOpts.promote_alloca_to_vector) {
910 LLVM_DEBUG(dbgs() << " Promote alloca to vectors is disabled\n");
911 return nullptr;
912 }
913
914 auto *VectorTy = dyn_cast<FixedVectorType>(Val: AllocaTy);
915 if (AllocaTy->isAggregateType()) {
916 uint64_t NumElems = 1;
917 Type *ElemTy = peelAggregateToElementType(Ty: AllocaTy, NumElems);
918
919 // Check for array of vectors
920 auto *InnerVectorTy = dyn_cast<FixedVectorType>(Val: ElemTy);
921 if (InnerVectorTy) {
922 NumElems *= InnerVectorTy->getNumElements();
923 ElemTy = InnerVectorTy->getElementType();
924 }
925
926 if (VectorType::isValidElementType(ElemTy) && NumElems > 0) {
927 unsigned ElementSize = DL.getTypeSizeInBits(Ty: ElemTy) / 8;
928 if (ElementSize > 0) {
929 unsigned AllocaSize = DL.getTypeStoreSize(Ty: AllocaTy);
930 // Expand vector if required to match padding of inner type,
931 // i.e. odd size subvectors.
932 // Storage size of new vector must match that of alloca for correct
933 // behaviour of byte offsets and GEP computation.
934 if (NumElems * ElementSize != AllocaSize)
935 NumElems = AllocaSize / ElementSize;
936 if (NumElems > 0 && (AllocaSize % ElementSize) == 0)
937 VectorTy = FixedVectorType::get(ElementType: ElemTy, NumElts: NumElems);
938 }
939 }
940 }
941 if (!VectorTy) {
942 LLVM_DEBUG(dbgs() << " Cannot convert type to vector\n");
943 return nullptr;
944 }
945
946 const unsigned MaxElements =
947 (MaxVectorRegs * 32) / DL.getTypeSizeInBits(Ty: VectorTy->getElementType());
948
949 if (VectorTy->getNumElements() > MaxElements ||
950 VectorTy->getNumElements() < 2) {
951 LLVM_DEBUG(dbgs() << " " << *VectorTy
952 << " has an unsupported number of elements\n");
953 return nullptr;
954 }
955
956 Type *VecEltTy = VectorTy->getElementType();
957 unsigned ElementSizeInBits = DL.getTypeSizeInBits(Ty: VecEltTy);
958 if (ElementSizeInBits != DL.getTypeAllocSizeInBits(Ty: VecEltTy)) {
959 LLVM_DEBUG(dbgs() << " Cannot convert to vector if the allocation size "
960 "does not match the type's size\n");
961 return nullptr;
962 }
963
964 return VectorTy;
965}
966
967void AMDGPUPromoteAllocaImpl::analyzePromoteToVector(AllocaAnalysis &AA) const {
968 if (AA.HaveSelectOrPHI) {
969 LLVM_DEBUG(dbgs() << " Cannot convert to vector due to select or phi\n");
970 return;
971 }
972
973 Type *AllocaTy = AA.Alloca->getAllocatedType();
974 AA.Vector.Ty = getVectorTypeForAlloca(AllocaTy);
975 if (!AA.Vector.Ty)
976 return;
977
978 const auto RejectUser = [&](Instruction *Inst, Twine Msg) {
979 LLVM_DEBUG(dbgs() << " Cannot promote alloca to vector: " << Msg << "\n"
980 << " " << *Inst << "\n");
981 AA.Vector.Ty = nullptr;
982 };
983
984 Type *VecEltTy = AA.Vector.Ty->getElementType();
985 unsigned ElementSize = DL.getTypeSizeInBits(Ty: VecEltTy) / 8;
986 assert(ElementSize > 0);
987 for (auto *U : AA.Uses) {
988 Instruction *Inst = cast<Instruction>(Val: U->getUser());
989
990 if (Value *Ptr = getLoadStorePointerOperand(V: Inst)) {
991 assert(!isa<StoreInst>(Inst) ||
992 U->getOperandNo() == StoreInst::getPointerOperandIndex());
993
994 Type *AccessTy = getLoadStoreType(I: Inst);
995 if (AccessTy->isAggregateType())
996 return RejectUser(Inst, "unsupported load/store as aggregate");
997 assert(!AccessTy->isAggregateType() || AccessTy->isArrayTy());
998
999 // Check that this is a simple access of a vector element.
1000 bool IsSimple = isa<LoadInst>(Val: Inst) ? cast<LoadInst>(Val: Inst)->isSimple()
1001 : cast<StoreInst>(Val: Inst)->isSimple();
1002 if (!IsSimple)
1003 return RejectUser(Inst, "not a simple load or store");
1004
1005 Ptr = Ptr->stripPointerCasts();
1006
1007 // Alloca already accessed as vector.
1008 if (Ptr == AA.Alloca &&
1009 DL.getTypeStoreSize(Ty: AA.Alloca->getAllocatedType()) ==
1010 DL.getTypeStoreSize(Ty: AccessTy)) {
1011 AA.Vector.Worklist.push_back(Elt: Inst);
1012 continue;
1013 }
1014
1015 if (!isSupportedAccessType(VecTy: AA.Vector.Ty, AccessTy, DL))
1016 return RejectUser(Inst, "not a supported access type");
1017
1018 AA.Vector.Worklist.push_back(Elt: Inst);
1019 continue;
1020 }
1021
1022 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: Inst)) {
1023 // If we can't compute a vector index from this GEP, then we can't
1024 // promote this alloca to vector.
1025 auto Index = computeGEPToVectorIndex(GEP, Alloca: AA.Alloca, VecElemTy: VecEltTy, DL);
1026 if (!Index)
1027 return RejectUser(Inst, "cannot compute vector index for GEP");
1028
1029 AA.Vector.GEPVectorIdx[GEP] = std::move(Index.value());
1030 AA.Vector.UsersToRemove.push_back(Elt: Inst);
1031 continue;
1032 }
1033
1034 if (MemSetInst *MSI = dyn_cast<MemSetInst>(Val: Inst);
1035 MSI && isSupportedMemset(I: MSI, AI: AA.Alloca, DL)) {
1036 AA.Vector.Worklist.push_back(Elt: Inst);
1037 continue;
1038 }
1039
1040 if (MemTransferInst *TransferInst = dyn_cast<MemTransferInst>(Val: Inst)) {
1041 if (TransferInst->isVolatile())
1042 return RejectUser(Inst, "mem transfer inst is volatile");
1043
1044 ConstantInt *Len = dyn_cast<ConstantInt>(Val: TransferInst->getLength());
1045 if (!Len || (Len->getZExtValue() % ElementSize))
1046 return RejectUser(Inst, "mem transfer inst length is non-constant or "
1047 "not a multiple of the vector element size");
1048
1049 auto getConstIndexIntoAlloca = [&](Value *Ptr) -> ConstantInt * {
1050 if (Ptr == AA.Alloca)
1051 return ConstantInt::get(Context&: Ptr->getContext(), V: APInt(32, 0));
1052
1053 GetElementPtrInst *GEP = cast<GetElementPtrInst>(Val: Ptr);
1054 const auto &GEPI = AA.Vector.GEPVectorIdx.find(Key: GEP)->second;
1055 if (GEPI.VarIndex)
1056 return nullptr;
1057 if (GEPI.ConstIndex)
1058 return GEPI.ConstIndex;
1059 return ConstantInt::get(Context&: Ptr->getContext(), V: APInt(32, 0));
1060 };
1061
1062 MemTransferInfo *TI =
1063 &AA.Vector.TransferInfo.try_emplace(Key: TransferInst).first->second;
1064 unsigned OpNum = U->getOperandNo();
1065 if (OpNum == 0) {
1066 Value *Dest = TransferInst->getDest();
1067 ConstantInt *Index = getConstIndexIntoAlloca(Dest);
1068 if (!Index)
1069 return RejectUser(Inst, "could not calculate constant dest index");
1070 TI->DestIndex = Index;
1071 } else {
1072 assert(OpNum == 1);
1073 Value *Src = TransferInst->getSource();
1074 ConstantInt *Index = getConstIndexIntoAlloca(Src);
1075 if (!Index)
1076 return RejectUser(Inst, "could not calculate constant src index");
1077 TI->SrcIndex = Index;
1078 }
1079 continue;
1080 }
1081
1082 if (auto *Intr = dyn_cast<IntrinsicInst>(Val: Inst)) {
1083 if (Intr->getIntrinsicID() == Intrinsic::objectsize) {
1084 AA.Vector.Worklist.push_back(Elt: Inst);
1085 continue;
1086 }
1087 }
1088
1089 // Ignore assume-like intrinsics and comparisons used in assumes.
1090 if (isAssumeLikeIntrinsic(I: Inst)) {
1091 if (!Inst->use_empty())
1092 return RejectUser(Inst, "assume-like intrinsic cannot have any users");
1093 AA.Vector.UsersToRemove.push_back(Elt: Inst);
1094 continue;
1095 }
1096
1097 if (isa<ICmpInst>(Val: Inst) && all_of(Range: Inst->users(), P: [](User *U) {
1098 return isAssumeLikeIntrinsic(I: cast<Instruction>(Val: U));
1099 })) {
1100 AA.Vector.UsersToRemove.push_back(Elt: Inst);
1101 continue;
1102 }
1103
1104 return RejectUser(Inst, "unhandled alloca user");
1105 }
1106
1107 // Follow-up check to ensure we've seen both sides of all transfer insts.
1108 for (const auto &Entry : AA.Vector.TransferInfo) {
1109 const MemTransferInfo &TI = Entry.second;
1110 if (!TI.SrcIndex || !TI.DestIndex)
1111 return RejectUser(Entry.first,
1112 "mem transfer inst between different objects");
1113 AA.Vector.Worklist.push_back(Elt: Entry.first);
1114 }
1115}
1116
1117void AMDGPUPromoteAllocaImpl::promoteAllocaToVector(AllocaAnalysis &AA) {
1118 LLVM_DEBUG(dbgs() << "Promoting to vectors: " << *AA.Alloca << '\n');
1119 LLVM_DEBUG(dbgs() << " type conversion: " << *AA.Alloca->getAllocatedType()
1120 << " -> " << *AA.Vector.Ty << '\n');
1121 const unsigned VecStoreSize = DL.getTypeStoreSize(Ty: AA.Vector.Ty);
1122
1123 Type *VecEltTy = AA.Vector.Ty->getElementType();
1124 const unsigned ElementSize = DL.getTypeSizeInBits(Ty: VecEltTy) / 8;
1125
1126 // Alloca is uninitialized memory. Imitate that by making the first value
1127 // undef.
1128 SSAUpdater Updater;
1129 Updater.Initialize(Ty: AA.Vector.Ty, Name: "promotealloca");
1130
1131 BasicBlock *EntryBB = AA.Alloca->getParent();
1132 BasicBlock::iterator InitInsertPos =
1133 skipToNonAllocaInsertPt(BB&: *EntryBB, I: AA.Alloca->getIterator());
1134 IRBuilder<> Builder(&*InitInsertPos);
1135 Value *AllocaInitValue = Builder.CreateFreeze(V: PoisonValue::get(T: AA.Vector.Ty));
1136 AllocaInitValue->takeName(V: AA.Alloca);
1137
1138 Updater.AddAvailableValue(BB: AA.Alloca->getParent(), V: AllocaInitValue);
1139
1140 // First handle the initial worklist, in basic block order.
1141 //
1142 // Insert a placeholder whenever we need the vector value at the top of a
1143 // basic block.
1144 SmallSetVector<Instruction *, 8> Placeholders;
1145 forEachWorkListItem(WorkList: AA.Vector.Worklist, Fn: [&](Instruction *I) {
1146 BasicBlock *BB = I->getParent();
1147 auto GetCurVal = [&]() -> Value * {
1148 if (Value *CurVal = Updater.FindValueForBlock(BB))
1149 return CurVal;
1150
1151 if (!Placeholders.empty() && Placeholders.back()->getParent() == BB)
1152 return Placeholders.back();
1153
1154 // If the current value in the basic block is not yet known, insert a
1155 // placeholder that we will replace later.
1156 IRBuilder<> Builder(I);
1157 auto *Placeholder = cast<Instruction>(Val: Builder.CreateFreeze(
1158 V: PoisonValue::get(T: AA.Vector.Ty), Name: "promotealloca.placeholder"));
1159 Placeholders.insert(X: Placeholder);
1160 return Placeholders.back();
1161 };
1162
1163 Value *Result = promoteAllocaUserToVector(Inst: I, DL, AA, VecStoreSize,
1164 ElementSize, GetCurVal);
1165 // If the returned result is a placeholder, it means the instruction does
1166 // not really modify the alloca. So no need to make it being available value
1167 // to SSAUpdater.
1168 // This will stop placeholder being cached in SSAUpdater. The cached
1169 // placeholder may cause stale pointer being referenced when doing
1170 // placeholder replacement.
1171 if (Result && (!isa<Instruction>(Val: Result) ||
1172 !Placeholders.contains(key: cast<Instruction>(Val: Result))))
1173 Updater.AddAvailableValue(BB, V: Result);
1174 });
1175
1176 // Now fixup the placeholders.
1177 for (Instruction *Placeholder : Placeholders) {
1178 Placeholder->replaceAllUsesWith(
1179 V: Updater.GetValueInMiddleOfBlock(BB: Placeholder->getParent()));
1180 Placeholder->eraseFromParent();
1181 }
1182
1183 // Delete all instructions.
1184 for (Instruction *I : AA.Vector.Worklist) {
1185 assert(I->use_empty());
1186 I->eraseFromParent();
1187 }
1188
1189 // Delete all the users that are known to be removeable.
1190 for (Instruction *I : reverse(C&: AA.Vector.UsersToRemove)) {
1191 I->dropDroppableUses();
1192 assert(I->use_empty());
1193 I->eraseFromParent();
1194 }
1195
1196 // Alloca should now be dead too.
1197 assert(AA.Alloca->use_empty());
1198 AA.Alloca->eraseFromParent();
1199}
1200
1201std::pair<Value *, Value *>
1202AMDGPUPromoteAllocaImpl::getLocalSizeYZ(IRBuilder<> &Builder) {
1203 Function &F = *Builder.GetInsertBlock()->getParent();
1204 const AMDGPUSubtarget &ST = AMDGPUSubtarget::get(TM, F);
1205
1206 if (!IsAMDHSA) {
1207 CallInst *LocalSizeY = Builder.CreateIntrinsicWithoutFolding(
1208 ID: Intrinsic::r600_read_local_size_y, Args: {});
1209 CallInst *LocalSizeZ = Builder.CreateIntrinsicWithoutFolding(
1210 ID: Intrinsic::r600_read_local_size_z, Args: {});
1211
1212 ST.makeLIDRangeMetadata(I: LocalSizeY);
1213 ST.makeLIDRangeMetadata(I: LocalSizeZ);
1214
1215 return std::pair(LocalSizeY, LocalSizeZ);
1216 }
1217
1218 // We must read the size out of the dispatch pointer.
1219 assert(IsAMDGCN);
1220
1221 // We are indexing into this struct, and want to extract the workgroup_size_*
1222 // fields.
1223 //
1224 // typedef struct hsa_kernel_dispatch_packet_s {
1225 // uint16_t header;
1226 // uint16_t setup;
1227 // uint16_t workgroup_size_x ;
1228 // uint16_t workgroup_size_y;
1229 // uint16_t workgroup_size_z;
1230 // uint16_t reserved0;
1231 // uint32_t grid_size_x ;
1232 // uint32_t grid_size_y ;
1233 // uint32_t grid_size_z;
1234 //
1235 // uint32_t private_segment_size;
1236 // uint32_t group_segment_size;
1237 // uint64_t kernel_object;
1238 //
1239 // #ifdef HSA_LARGE_MODEL
1240 // void *kernarg_address;
1241 // #elif defined HSA_LITTLE_ENDIAN
1242 // void *kernarg_address;
1243 // uint32_t reserved1;
1244 // #else
1245 // uint32_t reserved1;
1246 // void *kernarg_address;
1247 // #endif
1248 // uint64_t reserved2;
1249 // hsa_signal_t completion_signal; // uint64_t wrapper
1250 // } hsa_kernel_dispatch_packet_t
1251 //
1252 CallInst *DispatchPtr =
1253 Builder.CreateIntrinsicWithoutFolding(ID: Intrinsic::amdgcn_dispatch_ptr, Args: {});
1254 DispatchPtr->addRetAttr(Kind: Attribute::NoAlias);
1255 DispatchPtr->addRetAttr(Kind: Attribute::NonNull);
1256 F.removeFnAttr(Kind: "amdgpu-no-dispatch-ptr");
1257
1258 // Size of the dispatch packet struct.
1259 DispatchPtr->addDereferenceableRetAttr(Bytes: 64);
1260
1261 Type *I32Ty = Type::getInt32Ty(C&: Mod.getContext());
1262
1263 // We could do a single 64-bit load here, but it's likely that the basic
1264 // 32-bit and extract sequence is already present, and it is probably easier
1265 // to CSE this. The loads should be mergeable later anyway.
1266 Value *GEPXY = Builder.CreateConstInBoundsGEP1_64(Ty: I32Ty, Ptr: DispatchPtr, Idx0: 1);
1267 LoadInst *LoadXY = Builder.CreateAlignedLoad(Ty: I32Ty, Ptr: GEPXY, Align: Align(4));
1268
1269 Value *GEPZU = Builder.CreateConstInBoundsGEP1_64(Ty: I32Ty, Ptr: DispatchPtr, Idx0: 2);
1270 LoadInst *LoadZU = Builder.CreateAlignedLoad(Ty: I32Ty, Ptr: GEPZU, Align: Align(4));
1271
1272 MDNode *MD = MDNode::get(Context&: Mod.getContext(), MDs: {});
1273 LoadXY->setMetadata(KindID: LLVMContext::MD_invariant_load, Node: MD);
1274 LoadZU->setMetadata(KindID: LLVMContext::MD_invariant_load, Node: MD);
1275 ST.makeLIDRangeMetadata(I: LoadZU);
1276
1277 // Extract y component. Upper half of LoadZU should be zero already.
1278 Value *Y = Builder.CreateLShr(LHS: LoadXY, RHS: 16);
1279
1280 return std::pair(Y, LoadZU);
1281}
1282
1283Value *AMDGPUPromoteAllocaImpl::getWorkitemID(IRBuilder<> &Builder,
1284 unsigned N) {
1285 Function *F = Builder.GetInsertBlock()->getParent();
1286 const AMDGPUSubtarget &ST = AMDGPUSubtarget::get(TM, F: *F);
1287 Intrinsic::ID IntrID = Intrinsic::not_intrinsic;
1288 StringRef AttrName;
1289
1290 switch (N) {
1291 case 0:
1292 IntrID = IsAMDGCN ? (Intrinsic::ID)Intrinsic::amdgcn_workitem_id_x
1293 : (Intrinsic::ID)Intrinsic::r600_read_tidig_x;
1294 AttrName = "amdgpu-no-workitem-id-x";
1295 break;
1296 case 1:
1297 IntrID = IsAMDGCN ? (Intrinsic::ID)Intrinsic::amdgcn_workitem_id_y
1298 : (Intrinsic::ID)Intrinsic::r600_read_tidig_y;
1299 AttrName = "amdgpu-no-workitem-id-y";
1300 break;
1301
1302 case 2:
1303 IntrID = IsAMDGCN ? (Intrinsic::ID)Intrinsic::amdgcn_workitem_id_z
1304 : (Intrinsic::ID)Intrinsic::r600_read_tidig_z;
1305 AttrName = "amdgpu-no-workitem-id-z";
1306 break;
1307 default:
1308 llvm_unreachable("invalid dimension");
1309 }
1310
1311 Function *WorkitemIdFn = Intrinsic::getOrInsertDeclaration(M: &Mod, id: IntrID);
1312 CallInst *CI = Builder.CreateCall(Callee: WorkitemIdFn);
1313 ST.makeLIDRangeMetadata(I: CI);
1314 F->removeFnAttr(Kind: AttrName);
1315
1316 return CI;
1317}
1318
1319static bool isCallPromotable(CallInst *CI) {
1320 IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: CI);
1321 if (!II)
1322 return false;
1323
1324 switch (II->getIntrinsicID()) {
1325 case Intrinsic::memcpy:
1326 case Intrinsic::memmove:
1327 case Intrinsic::memset:
1328 case Intrinsic::lifetime_start:
1329 case Intrinsic::lifetime_end:
1330 case Intrinsic::invariant_start:
1331 case Intrinsic::invariant_end:
1332 case Intrinsic::launder_invariant_group:
1333 case Intrinsic::objectsize:
1334 return true;
1335 default:
1336 return false;
1337 }
1338}
1339
1340bool AMDGPUPromoteAllocaImpl::binaryOpIsDerivedFromSameAlloca(
1341 Value *BaseAlloca, Value *Val, Instruction *Inst, int OpIdx0,
1342 int OpIdx1) const {
1343 // Figure out which operand is the one we might not be promoting.
1344 Value *OtherOp = Inst->getOperand(i: OpIdx0);
1345 if (Val == OtherOp)
1346 OtherOp = Inst->getOperand(i: OpIdx1);
1347
1348 if (isa<ConstantPointerNull, ConstantAggregateZero>(Val: OtherOp))
1349 return true;
1350
1351 // TODO: getUnderlyingObject will not work on a vector getelementptr
1352 Value *OtherObj = getUnderlyingObject(V: OtherOp);
1353 if (!isa<AllocaInst>(Val: OtherObj))
1354 return false;
1355
1356 // TODO: We should be able to replace undefs with the right pointer type.
1357
1358 // TODO: If we know the other base object is another promotable
1359 // alloca, not necessarily this alloca, we can do this. The
1360 // important part is both must have the same address space at
1361 // the end.
1362 if (OtherObj != BaseAlloca) {
1363 LLVM_DEBUG(
1364 dbgs() << "Found a binary instruction with another alloca object\n");
1365 return false;
1366 }
1367
1368 return true;
1369}
1370
1371void AMDGPUPromoteAllocaImpl::analyzePromoteToLDS(AllocaAnalysis &AA) const {
1372 if (!CLOpts.promote_alloca_to_lds) {
1373 LLVM_DEBUG(dbgs() << " Promote alloca to LDS is disabled\n");
1374 return;
1375 }
1376
1377 // Don't promote the alloca to LDS for shader calling conventions as the work
1378 // item ID intrinsics are not supported for these calling conventions.
1379 // Furthermore not all LDS is available for some of the stages.
1380 const Function &ContainingFunction = *AA.Alloca->getFunction();
1381 CallingConv::ID CC = ContainingFunction.getCallingConv();
1382
1383 switch (CC) {
1384 case CallingConv::AMDGPU_KERNEL:
1385 case CallingConv::SPIR_KERNEL:
1386 break;
1387 default:
1388 LLVM_DEBUG(
1389 dbgs()
1390 << " promote alloca to LDS not supported with calling convention.\n");
1391 return;
1392 }
1393
1394 for (Use *Use : AA.Uses) {
1395 auto *User = Use->getUser();
1396
1397 if (CallInst *CI = dyn_cast<CallInst>(Val: User)) {
1398 if (!isCallPromotable(CI))
1399 return;
1400
1401 if (find(Range&: AA.LDS.Worklist, Val: User) == AA.LDS.Worklist.end())
1402 AA.LDS.Worklist.push_back(Elt: User);
1403 continue;
1404 }
1405
1406 Instruction *UseInst = cast<Instruction>(Val: User);
1407 if (UseInst->getOpcode() == Instruction::PtrToInt)
1408 return;
1409
1410 if (LoadInst *LI = dyn_cast<LoadInst>(Val: UseInst)) {
1411 if (LI->isVolatile())
1412 return;
1413 continue;
1414 }
1415
1416 if (StoreInst *SI = dyn_cast<StoreInst>(Val: UseInst)) {
1417 if (SI->isVolatile())
1418 return;
1419 continue;
1420 }
1421
1422 if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(Val: UseInst)) {
1423 if (RMW->isVolatile())
1424 return;
1425 continue;
1426 }
1427
1428 if (AtomicCmpXchgInst *CAS = dyn_cast<AtomicCmpXchgInst>(Val: UseInst)) {
1429 if (CAS->isVolatile())
1430 return;
1431 continue;
1432 }
1433
1434 // Only promote a select if we know that the other select operand
1435 // is from another pointer that will also be promoted.
1436 if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Val: UseInst)) {
1437 if (!binaryOpIsDerivedFromSameAlloca(BaseAlloca: AA.Alloca, Val: Use->get(), Inst: ICmp, OpIdx0: 0, OpIdx1: 1))
1438 return;
1439
1440 // May need to rewrite constant operands.
1441 if (find(Range&: AA.LDS.Worklist, Val: User) == AA.LDS.Worklist.end())
1442 AA.LDS.Worklist.push_back(Elt: ICmp);
1443 continue;
1444 }
1445
1446 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: UseInst)) {
1447 // Be conservative if an address could be computed outside the bounds of
1448 // the alloca.
1449 if (!GEP->isInBounds())
1450 return;
1451 } else if (!isa<ExtractElementInst, SelectInst, PHINode>(Val: User)) {
1452 // Do not promote vector/aggregate type instructions. It is hard to track
1453 // their users.
1454
1455 // Do not promote addrspacecast.
1456 //
1457 // TODO: If we know the address is only observed through flat pointers, we
1458 // could still promote.
1459 return;
1460 }
1461
1462 if (find(Range&: AA.LDS.Worklist, Val: User) == AA.LDS.Worklist.end())
1463 AA.LDS.Worklist.push_back(Elt: User);
1464 }
1465
1466 AA.LDS.Enable = true;
1467}
1468
1469bool AMDGPUPromoteAllocaImpl::hasSufficientLocalMem(const Function &F) {
1470
1471 FunctionType *FTy = F.getFunctionType();
1472 const AMDGPUSubtarget &ST = AMDGPUSubtarget::get(TM, F);
1473
1474 // If the function has any arguments in the local address space, then it's
1475 // possible these arguments require the entire local memory space, so
1476 // we cannot use local memory in the pass.
1477 for (Type *ParamTy : FTy->params()) {
1478 PointerType *PtrTy = dyn_cast<PointerType>(Val: ParamTy);
1479 if (PtrTy && PtrTy->getAddressSpace() == AMDGPUAS::LOCAL_ADDRESS) {
1480 LocalMemLimit = 0;
1481 LLVM_DEBUG(dbgs() << "Function has local memory argument. Promoting to "
1482 "local memory disabled.\n");
1483 return false;
1484 }
1485 }
1486
1487 LocalMemLimit = ST.getAddressableLocalMemorySize();
1488 if (LocalMemLimit == 0)
1489 return false;
1490
1491 SmallVector<const Constant *, 16> Stack;
1492 SmallPtrSet<const Constant *, 8> VisitedConstants;
1493 SmallPtrSet<const GlobalVariable *, 8> UsedLDS;
1494
1495 auto visitUsers = [&](const GlobalVariable *GV, const Constant *Val) -> bool {
1496 for (const User *U : Val->users()) {
1497 if (const Instruction *Use = dyn_cast<Instruction>(Val: U)) {
1498 if (Use->getFunction() == &F)
1499 return true;
1500 } else {
1501 const Constant *C = cast<Constant>(Val: U);
1502 if (VisitedConstants.insert(Ptr: C).second)
1503 Stack.push_back(Elt: C);
1504 }
1505 }
1506
1507 return false;
1508 };
1509
1510 for (GlobalVariable &GV : Mod.globals()) {
1511 if (GV.getAddressSpace() != AMDGPUAS::LOCAL_ADDRESS)
1512 continue;
1513
1514 if (visitUsers(&GV, &GV)) {
1515 UsedLDS.insert(Ptr: &GV);
1516 Stack.clear();
1517 continue;
1518 }
1519
1520 // For any ConstantExpr uses, we need to recursively search the users until
1521 // we see a function.
1522 while (!Stack.empty()) {
1523 const Constant *C = Stack.pop_back_val();
1524 if (visitUsers(&GV, C)) {
1525 UsedLDS.insert(Ptr: &GV);
1526 Stack.clear();
1527 break;
1528 }
1529 }
1530 }
1531
1532 SmallVector<std::pair<uint64_t, Align>, 16> AllocatedSizes;
1533 AllocatedSizes.reserve(N: UsedLDS.size());
1534
1535 for (const GlobalVariable *GV : UsedLDS) {
1536 Align Alignment =
1537 DL.getValueOrABITypeAlignment(Alignment: GV->getAlign(), Ty: GV->getValueType());
1538 uint64_t AllocSize = GV->getGlobalSize(DL);
1539
1540 // HIP uses an extern unsized array in local address space for dynamically
1541 // allocated shared memory. In that case, we have to disable the promotion.
1542 if (GV->hasExternalLinkage() && AllocSize == 0) {
1543 LocalMemLimit = 0;
1544 LLVM_DEBUG(dbgs() << "Function has a reference to externally allocated "
1545 "local memory. Promoting to local memory "
1546 "disabled.\n");
1547 return false;
1548 }
1549
1550 AllocatedSizes.emplace_back(Args&: AllocSize, Args&: Alignment);
1551 }
1552
1553 // Sort to try to estimate the worst case alignment padding
1554 //
1555 // FIXME: We should really do something to fix the addresses to a more optimal
1556 // value instead
1557 llvm::sort(C&: AllocatedSizes, Comp: llvm::less_second());
1558
1559 // Check how much local memory is being used by global objects
1560 CurrentLocalMemUsage = 0;
1561
1562 // FIXME: Try to account for padding here. The real padding and address is
1563 // currently determined from the inverse order of uses in the function when
1564 // legalizing, which could also potentially change. We try to estimate the
1565 // worst case here, but we probably should fix the addresses earlier.
1566 for (auto Alloc : AllocatedSizes) {
1567 CurrentLocalMemUsage = alignTo(Size: CurrentLocalMemUsage, A: Alloc.second);
1568 CurrentLocalMemUsage += Alloc.first;
1569 }
1570
1571 unsigned MaxOccupancy =
1572 ST.getWavesPerEU(FlatWorkGroupSizes: ST.getFlatWorkGroupSizes(F), LDSBytes: CurrentLocalMemUsage, F)
1573 .second;
1574
1575 // Round up to the next tier of usage.
1576 unsigned MaxSizeWithWaveCount =
1577 ST.getMaxLocalMemSizeWithWaveCount(WaveCount: MaxOccupancy, F);
1578
1579 // Program may already use more LDS than is usable at maximum occupancy.
1580 if (CurrentLocalMemUsage > MaxSizeWithWaveCount)
1581 return false;
1582
1583 LocalMemLimit = MaxSizeWithWaveCount;
1584
1585 LLVM_DEBUG(dbgs() << F.getName() << " uses " << CurrentLocalMemUsage
1586 << " bytes of LDS\n"
1587 << " Rounding size to " << MaxSizeWithWaveCount
1588 << " with a maximum occupancy of " << MaxOccupancy << '\n'
1589 << " and " << (LocalMemLimit - CurrentLocalMemUsage)
1590 << " available for promotion\n");
1591
1592 return true;
1593}
1594
1595// FIXME: Should try to pick the most likely to be profitable allocas first.
1596bool AMDGPUPromoteAllocaImpl::tryPromoteAllocaToLDS(
1597 AllocaAnalysis &AA, bool SufficientLDS,
1598 SetVector<IntrinsicInst *> &DeferredIntrs) {
1599 LLVM_DEBUG(dbgs() << "Trying to promote to LDS: " << *AA.Alloca << '\n');
1600
1601 // Not likely to have sufficient local memory for promotion.
1602 if (!SufficientLDS)
1603 return false;
1604
1605 IRBuilder<> Builder(AA.Alloca);
1606
1607 const Function &ContainingFunction = *AA.Alloca->getParent()->getParent();
1608 const AMDGPUSubtarget &ST = AMDGPUSubtarget::get(TM, F: ContainingFunction);
1609 unsigned WorkGroupSize = ST.getFlatWorkGroupSizes(F: ContainingFunction).second;
1610
1611 Align Alignment = AA.Alloca->getAlign();
1612
1613 // FIXME: This computed padding is likely wrong since it depends on inverse
1614 // usage order.
1615 //
1616 // FIXME: It is also possible that if we're allowed to use all of the memory
1617 // could end up using more than the maximum due to alignment padding.
1618
1619 uint32_t NewSize = alignTo(Size: CurrentLocalMemUsage, A: Alignment);
1620 std::optional<TypeSize> ElemSize = AA.Alloca->getAllocationSize(DL);
1621 if (!ElemSize || ElemSize->isScalable())
1622 return false;
1623 TypeSize AllocSize = WorkGroupSize * *ElemSize;
1624 NewSize += AllocSize.getFixedValue();
1625
1626 if (NewSize > LocalMemLimit) {
1627 LLVM_DEBUG(dbgs() << " " << AllocSize
1628 << " bytes of local memory not available to promote\n");
1629 return false;
1630 }
1631
1632 CurrentLocalMemUsage = NewSize;
1633
1634 LLVM_DEBUG(dbgs() << "Promoting alloca to local memory\n");
1635
1636 Function *F = AA.Alloca->getFunction();
1637
1638 Type *GVTy = ArrayType::get(ElementType: AA.Alloca->getAllocatedType(), NumElements: WorkGroupSize);
1639 GlobalVariable *GV = new GlobalVariable(
1640 Mod, GVTy, false, GlobalValue::InternalLinkage, PoisonValue::get(T: GVTy),
1641 Twine(F->getName()) + Twine('.') + AA.Alloca->getName(), nullptr,
1642 GlobalVariable::NotThreadLocal, AMDGPUAS::LOCAL_ADDRESS);
1643 GV->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
1644 GV->setAlignment(AA.Alloca->getAlign());
1645
1646 Value *TCntY, *TCntZ;
1647
1648 std::tie(args&: TCntY, args&: TCntZ) = getLocalSizeYZ(Builder);
1649 Value *TIdX = getWorkitemID(Builder, N: 0);
1650 Value *TIdY = getWorkitemID(Builder, N: 1);
1651 Value *TIdZ = getWorkitemID(Builder, N: 2);
1652
1653 Value *Tmp0 = Builder.CreateMul(LHS: TCntY, RHS: TCntZ, Name: "", HasNUW: true, HasNSW: true);
1654 Tmp0 = Builder.CreateMul(LHS: Tmp0, RHS: TIdX);
1655 Value *Tmp1 = Builder.CreateMul(LHS: TIdY, RHS: TCntZ, Name: "", HasNUW: true, HasNSW: true);
1656 Value *TID = Builder.CreateAdd(LHS: Tmp0, RHS: Tmp1);
1657 TID = Builder.CreateAdd(LHS: TID, RHS: TIdZ);
1658
1659 LLVMContext &Context = Mod.getContext();
1660 Value *Indices[] = {Constant::getNullValue(Ty: Type::getInt32Ty(C&: Context)), TID};
1661
1662 Value *Offset = Builder.CreateInBoundsGEP(Ty: GVTy, Ptr: GV, IdxList: Indices);
1663 AA.Alloca->mutateType(Ty: Offset->getType());
1664 AA.Alloca->replaceAllUsesWith(V: Offset);
1665 AA.Alloca->eraseFromParent();
1666
1667 PointerType *NewPtrTy = PointerType::get(C&: Context, AddressSpace: AMDGPUAS::LOCAL_ADDRESS);
1668
1669 for (Value *V : AA.LDS.Worklist) {
1670 CallInst *Call = dyn_cast<CallInst>(Val: V);
1671 if (!Call) {
1672 if (ICmpInst *CI = dyn_cast<ICmpInst>(Val: V)) {
1673 Value *LHS = CI->getOperand(i_nocapture: 0);
1674 Value *RHS = CI->getOperand(i_nocapture: 1);
1675
1676 Type *NewTy = LHS->getType()->getWithNewType(EltTy: NewPtrTy);
1677 if (isa<ConstantPointerNull, ConstantAggregateZero>(Val: LHS))
1678 CI->setOperand(i_nocapture: 0, Val_nocapture: Constant::getNullValue(Ty: NewTy));
1679
1680 if (isa<ConstantPointerNull, ConstantAggregateZero>(Val: RHS))
1681 CI->setOperand(i_nocapture: 1, Val_nocapture: Constant::getNullValue(Ty: NewTy));
1682
1683 continue;
1684 }
1685
1686 // The operand's value should be corrected on its own and we don't want to
1687 // touch the users.
1688 if (isa<AddrSpaceCastInst>(Val: V))
1689 continue;
1690
1691 assert(V->getType()->isPtrOrPtrVectorTy());
1692
1693 Type *NewTy = V->getType()->getWithNewType(EltTy: NewPtrTy);
1694 V->mutateType(Ty: NewTy);
1695
1696 // Adjust the types of any constant operands.
1697 if (SelectInst *SI = dyn_cast<SelectInst>(Val: V)) {
1698 if (isa<ConstantPointerNull, ConstantAggregateZero>(Val: SI->getOperand(i_nocapture: 1)))
1699 SI->setOperand(i_nocapture: 1, Val_nocapture: Constant::getNullValue(Ty: NewTy));
1700
1701 if (isa<ConstantPointerNull, ConstantAggregateZero>(Val: SI->getOperand(i_nocapture: 2)))
1702 SI->setOperand(i_nocapture: 2, Val_nocapture: Constant::getNullValue(Ty: NewTy));
1703 } else if (PHINode *Phi = dyn_cast<PHINode>(Val: V)) {
1704 for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) {
1705 if (isa<ConstantPointerNull, ConstantAggregateZero>(
1706 Val: Phi->getIncomingValue(i: I)))
1707 Phi->setIncomingValue(i: I, V: Constant::getNullValue(Ty: NewTy));
1708 }
1709 }
1710
1711 continue;
1712 }
1713
1714 IntrinsicInst *Intr = cast<IntrinsicInst>(Val: Call);
1715 Builder.SetInsertPoint(Intr);
1716 switch (Intr->getIntrinsicID()) {
1717 case Intrinsic::lifetime_start:
1718 case Intrinsic::lifetime_end:
1719 // These intrinsics are for address space 0 only
1720 Intr->eraseFromParent();
1721 continue;
1722 case Intrinsic::memcpy:
1723 case Intrinsic::memmove:
1724 // These have 2 pointer operands. In case if second pointer also needs
1725 // to be replaced we defer processing of these intrinsics until all
1726 // other values are processed.
1727 DeferredIntrs.insert(X: Intr);
1728 continue;
1729 case Intrinsic::memset: {
1730 MemSetInst *MemSet = cast<MemSetInst>(Val: Intr);
1731 Builder.CreateMemSet(Ptr: MemSet->getRawDest(), Val: MemSet->getValue(),
1732 Size: MemSet->getLength(), Align: MemSet->getDestAlign(),
1733 isVolatile: MemSet->isVolatile());
1734 Intr->eraseFromParent();
1735 continue;
1736 }
1737 case Intrinsic::invariant_start:
1738 case Intrinsic::invariant_end:
1739 case Intrinsic::launder_invariant_group: {
1740 assert(Intr->getArgOperand(Intr->arg_size() - 1)->getType() == NewPtrTy &&
1741 "pointer operand should already have been promoted");
1742 Function *NewF = Intrinsic::getOrInsertDeclaration(
1743 M: Intr->getModule(), id: Intr->getIntrinsicID(), OverloadTys: NewPtrTy);
1744 Intr->mutateType(Ty: NewF->getReturnType());
1745 Intr->setCalledFunction(NewF);
1746 continue;
1747 }
1748 case Intrinsic::objectsize: {
1749 Value *Src = Intr->getOperand(i_nocapture: 0);
1750
1751 Value *NewCall = Builder.CreateIntrinsic(
1752 ID: Intrinsic::objectsize,
1753 OverloadTypes: {Intr->getType(), PointerType::get(C&: Context, AddressSpace: AMDGPUAS::LOCAL_ADDRESS)},
1754 Args: {Src, Intr->getOperand(i_nocapture: 1), Intr->getOperand(i_nocapture: 2), Intr->getOperand(i_nocapture: 3)});
1755 Intr->replaceAllUsesWith(V: NewCall);
1756 Intr->eraseFromParent();
1757 continue;
1758 }
1759 default:
1760 Intr->print(O&: errs());
1761 llvm_unreachable("Don't know how to promote alloca intrinsic use.");
1762 }
1763 }
1764
1765 return true;
1766}
1767
1768void AMDGPUPromoteAllocaImpl::finishDeferredAllocaToLDSPromotion(
1769 SetVector<IntrinsicInst *> &DeferredIntrs) {
1770
1771 for (IntrinsicInst *Intr : DeferredIntrs) {
1772 IRBuilder<> Builder(Intr);
1773 Builder.SetInsertPoint(Intr);
1774 Intrinsic::ID ID = Intr->getIntrinsicID();
1775 assert(ID == Intrinsic::memcpy || ID == Intrinsic::memmove);
1776
1777 MemTransferInst *MI = cast<MemTransferInst>(Val: Intr);
1778 auto *B = Builder.CreateMemTransferInst(
1779 IntrID: ID, Dst: MI->getRawDest(), DstAlign: MI->getDestAlign(), Src: MI->getRawSource(),
1780 SrcAlign: MI->getSourceAlign(), Size: MI->getLength(), isVolatile: MI->isVolatile());
1781
1782 for (unsigned I = 0; I != 2; ++I) {
1783 if (uint64_t Bytes = Intr->getParamDereferenceableBytes(i: I)) {
1784 B->addDereferenceableParamAttr(i: I, Bytes);
1785 }
1786 }
1787
1788 Intr->eraseFromParent();
1789 }
1790}
1791