1//===-- AMDGPUMemoryUtils.cpp - -------------------------------------------===//
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#include "AMDGPUMemoryUtils.h"
10#include "Utils/AMDGPUBaseInfo.h"
11#include "llvm/ADT/SetOperations.h"
12#include "llvm/Analysis/AliasAnalysis.h"
13#include "llvm/Analysis/CallGraph.h"
14#include "llvm/Analysis/MemorySSA.h"
15#include "llvm/IR/DataLayout.h"
16#include "llvm/IR/Instructions.h"
17#include "llvm/IR/IntrinsicInst.h"
18#include "llvm/IR/IntrinsicsAMDGPU.h"
19#include "llvm/IR/LLVMContext.h"
20#include "llvm/IR/ReplaceConstant.h"
21#include "llvm/Support/AMDGPUAddrSpace.h"
22
23#define DEBUG_TYPE "amdgpu-memory-utils"
24
25using namespace llvm;
26
27namespace llvm::AMDGPU {
28
29Align getAlign(const DataLayout &DL, const GlobalVariable *GV) {
30 return DL.getValueOrABITypeAlignment(Alignment: GV->getPointerAlignment(DL),
31 Ty: GV->getValueType());
32}
33
34unsigned getSyntheticApertureNumber(unsigned AS) {
35 switch (AS) {
36 case AMDGPUAS::BARRIER:
37 return SyntheticAperture::BARRIER;
38 default:
39 return SyntheticAperture::None;
40 }
41}
42
43void copyMetadataForWidenedLoad(LoadInst &Dest, const LoadInst &Source) {
44 SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
45 Source.getAllMetadata(MDs&: MD);
46 for (const auto &[ID, N] : MD) {
47 switch (ID) {
48 case LLVMContext::MD_dbg:
49 case LLVMContext::MD_invariant_load:
50 case LLVMContext::MD_nontemporal:
51 Dest.setMetadata(KindID: ID, Node: N);
52 break;
53 default:
54 break;
55 }
56 }
57}
58
59// Returns the target extension type of a global variable,
60// which can only be a TargetExtType, an array or single-element struct of it,
61// or their nesting combination.
62// TODO: allow struct of multiple TargetExtType elements of the same type.
63// TODO: Disallow other uses of target("amdgcn.named.barrier") including:
64// - Structs containing barriers in different scope/rank
65// - Structs containing a mixture of barriers and other data.
66// - Globals in other address spaces.
67// - Allocas.
68static TargetExtType *getTargetExtType(const GlobalVariable &GV) {
69 Type *Ty = GV.getValueType();
70 while (true) {
71 if (auto *TTy = dyn_cast<TargetExtType>(Val: Ty))
72 return TTy;
73 if (auto *STy = dyn_cast<StructType>(Val: Ty)) {
74 if (STy->getNumElements() != 1)
75 return nullptr;
76 Ty = STy->getElementType(N: 0);
77 continue;
78 }
79 if (auto *ATy = dyn_cast<ArrayType>(Val: Ty)) {
80 Ty = ATy->getElementType();
81 continue;
82 }
83 return nullptr;
84 }
85}
86
87TargetExtType *isNamedBarrier(const GlobalVariable &GV) {
88 if (GV.getAddressSpace() != AMDGPUAS::BARRIER)
89 return nullptr;
90 if (TargetExtType *Ty = getTargetExtType(GV))
91 return Ty->getName() == "amdgcn.named.barrier" ? Ty : nullptr;
92 return nullptr;
93}
94
95unsigned getNumNamedBarriersDeclared(const DataLayout &DL,
96 const GlobalVariable &GV) {
97 assert(isNamedBarrier(GV));
98 unsigned GVSize = GV.getGlobalSize(DL);
99 assert(GVSize && (GVSize % NamedBarrierTypeSizeInBytes == 0));
100 return GVSize / NamedBarrierTypeSizeInBytes;
101}
102
103bool isDynamicLDS(const GlobalVariable &GV) {
104 // external zero size addrspace(3) without initializer is dynlds.
105 const Module *M = GV.getParent();
106 const DataLayout &DL = M->getDataLayout();
107 if (GV.getType()->getPointerAddressSpace() != AMDGPUAS::LOCAL_ADDRESS)
108 return false;
109 return GV.getGlobalSize(DL) == 0;
110}
111
112bool isLDSVariableToLower(const GlobalVariable &GV) {
113 if (GV.getType()->getPointerAddressSpace() != AMDGPUAS::LOCAL_ADDRESS) {
114 return false;
115 }
116 if (isDynamicLDS(GV)) {
117 return true;
118 }
119 if (GV.isConstant()) {
120 // A constant undef variable can't be written to, and any load is
121 // undef, so it should be eliminated by the optimizer. It could be
122 // dropped by the back end if not. This pass skips over it.
123 return false;
124 }
125 if (GV.hasInitializer() && !isa<UndefValue>(Val: GV.getInitializer())) {
126 // Initializers are unimplemented for LDS address space.
127 // Leave such variables in place for consistent error reporting.
128 return false;
129 }
130 return true;
131}
132
133bool eliminateGVConstantExprUsesFromAllInstructions(
134 Module &M, function_ref<bool(const GlobalVariable &)> Filter) {
135 SmallVector<Constant *> Worklist;
136 for (auto &GV : M.globals())
137 if (Filter(GV))
138 Worklist.push_back(Elt: &GV);
139 return convertUsersOfConstantsToInstructions(Consts: Worklist);
140}
141
142void getUsesOfGVByFunction(const CallGraph &CG, Module &M,
143 function_ref<bool(const GlobalVariable &)> Filter,
144 FunctionVariableMap &Kernels,
145 FunctionVariableMap &Functions) {
146 // Get uses from the current function, excluding uses by called Functions
147 // Two output variables to avoid walking the globals list twice
148 for (auto &GV : M.globals()) {
149 if (!Filter(GV))
150 continue;
151 for (User *V : GV.users()) {
152 if (auto *I = dyn_cast<Instruction>(Val: V)) {
153 Function *F = I->getFunction();
154 if (isKernel(F: *F))
155 Kernels[F].insert(V: &GV);
156 else
157 Functions[F].insert(V: &GV);
158 }
159 }
160 }
161}
162
163GVUsesInfoTy
164getTransitiveUsesOfGV(const CallGraph &CG, Module &M,
165 function_ref<bool(const GlobalVariable &)> Filter) {
166
167 FunctionVariableMap DirectMapKernel;
168 FunctionVariableMap DirectMapFunction;
169 getUsesOfGVByFunction(CG, M, Filter, Kernels&: DirectMapKernel, Functions&: DirectMapFunction);
170
171 // Collect functions whose address has escaped
172 DenseSet<Function *> AddressTakenFuncs;
173 for (Function &F : M.functions()) {
174 if (!isKernel(F))
175 if (F.hasAddressTaken(nullptr,
176 /* IgnoreCallbackUses */ false,
177 /* IgnoreAssumeLikeCalls */ false,
178 /* IgnoreLLVMUsed */ IngoreLLVMUsed: true,
179 /* IgnoreArcAttachedCall */ IgnoreARCAttachedCall: false)) {
180 AddressTakenFuncs.insert(V: &F);
181 }
182 }
183
184 // Collect variables that are used by functions whose address has escaped
185 DenseSet<GlobalVariable *> VariablesReachableThroughFunctionPointer;
186 for (Function *F : AddressTakenFuncs) {
187 set_union(S1&: VariablesReachableThroughFunctionPointer, S2: DirectMapFunction[F]);
188 }
189
190 auto FunctionMakesUnknownCall = [&](const Function *F) -> bool {
191 assert(!F->isDeclaration());
192 for (const CallGraphNode::CallRecord &R : *CG[F]) {
193 if (!R.second->getFunction())
194 return true;
195 }
196 return false;
197 };
198
199 // Work out which variables are reachable through function calls
200 FunctionVariableMap TransitiveMapFunction = DirectMapFunction;
201
202 // If the function makes any unknown call, assume the worst case that it can
203 // access all variables accessed by functions whose address escaped
204 for (Function &F : M.functions()) {
205 if (!F.isDeclaration() && FunctionMakesUnknownCall(&F)) {
206 if (!isKernel(F)) {
207 set_union(S1&: TransitiveMapFunction[&F],
208 S2: VariablesReachableThroughFunctionPointer);
209 }
210 }
211 }
212
213 // Direct implementation of collecting all variables reachable from each
214 // function
215 for (Function &Func : M.functions()) {
216 if (Func.isDeclaration() || isKernel(F: Func))
217 continue;
218
219 DenseSet<Function *> seen; // catches cycles
220 SmallVector<Function *, 4> wip = {&Func};
221
222 while (!wip.empty()) {
223 Function *F = wip.pop_back_val();
224
225 // Can accelerate this by referring to transitive map for functions that
226 // have already been computed, with more care than this
227 set_union(S1&: TransitiveMapFunction[&Func], S2: DirectMapFunction[F]);
228
229 for (const CallGraphNode::CallRecord &R : *CG[F]) {
230 Function *Ith = R.second->getFunction();
231 if (Ith) {
232 if (!seen.contains(V: Ith)) {
233 seen.insert(V: Ith);
234 wip.push_back(Elt: Ith);
235 }
236 }
237 }
238 }
239 }
240
241 // Collect variables that are transitively used by functions whose address has
242 // escaped
243 for (Function *F : AddressTakenFuncs) {
244 set_union(S1&: VariablesReachableThroughFunctionPointer,
245 S2: TransitiveMapFunction[F]);
246 }
247
248 // DirectMapKernel lists which variables are used by the kernel
249 // find the variables which are used through a function call
250 FunctionVariableMap IndirectMapKernel;
251
252 for (Function &Func : M.functions()) {
253 if (Func.isDeclaration() || !isKernel(F: Func))
254 continue;
255
256 for (const CallGraphNode::CallRecord &R : *CG[&Func]) {
257 Function *Ith = R.second->getFunction();
258 if (Ith) {
259 set_union(S1&: IndirectMapKernel[&Func], S2: TransitiveMapFunction[Ith]);
260 }
261 }
262
263 // Check if the kernel encounters unknows calls, wheher directly or
264 // indirectly.
265 bool SeesUnknownCalls = [&]() {
266 SmallVector<Function *> WorkList = {CG[&Func]->getFunction()};
267 SmallPtrSet<Function *, 8> Visited;
268
269 while (!WorkList.empty()) {
270 Function *F = WorkList.pop_back_val();
271
272 for (const CallGraphNode::CallRecord &CallRecord : *CG[F]) {
273 if (!CallRecord.second)
274 continue;
275
276 Function *Callee = CallRecord.second->getFunction();
277 if (!Callee)
278 return true;
279
280 if (Visited.insert(Ptr: Callee).second)
281 WorkList.push_back(Elt: Callee);
282 }
283 }
284 return false;
285 }();
286
287 if (SeesUnknownCalls) {
288 set_union(S1&: IndirectMapKernel[&Func],
289 S2: VariablesReachableThroughFunctionPointer);
290 }
291 }
292
293 return {.DirectAccess: std::move(DirectMapKernel), .IndirectAccess: std::move(IndirectMapKernel)};
294}
295
296GVUsesInfoTy getTransitiveUsesOfLDSForLowering(const CallGraph &CG, Module &M) {
297 GVUsesInfoTy UsesInfo = getTransitiveUsesOfGV(CG, M, Filter: isLDSVariableToLower);
298 // Verify that we fall into one of 2 cases:
299 // - All variables are either absolute
300 // or direct mapped dynamic LDS that is not lowered.
301 // - No variables are absolute.
302 // Named-barriers which are absolute symbols are removed
303 // from the maps.
304 std::optional<bool> HasAbsoluteGVs;
305 for (auto &Map : {UsesInfo.DirectAccess, UsesInfo.IndirectAccess}) {
306 for (auto &[Fn, GVs] : Map) {
307 for (auto *GV : GVs) {
308 bool IsAbsolute = GV->isAbsoluteSymbolRef();
309 bool IsDirectMapDynLDSGV =
310 AMDGPU::isDynamicLDS(GV: *GV) && UsesInfo.DirectAccess.contains(Val: Fn);
311 if (IsDirectMapDynLDSGV)
312 continue;
313
314 if (HasAbsoluteGVs.has_value()) {
315 if (*HasAbsoluteGVs != IsAbsolute) {
316 reportFatalUsageError(
317 reason: "module cannot mix absolute and non-absolute LDS GVs");
318 }
319 } else
320 HasAbsoluteGVs = IsAbsolute;
321 }
322 }
323 }
324
325 // If we only had absolute GVs, we have nothing to do, return an empty
326 // result.
327 if (HasAbsoluteGVs && *HasAbsoluteGVs)
328 return GVUsesInfoTy();
329
330 return UsesInfo;
331}
332
333void removeFnAttrFromReachable(CallGraph &CG, Function *KernelRoot,
334 ArrayRef<StringRef> FnAttrs) {
335 for (StringRef Attr : FnAttrs)
336 KernelRoot->removeFnAttr(Kind: Attr);
337
338 SmallVector<Function *> WorkList = {CG[KernelRoot]->getFunction()};
339 SmallPtrSet<Function *, 8> Visited;
340 bool SeenUnknownCall = false;
341
342 while (!WorkList.empty()) {
343 Function *F = WorkList.pop_back_val();
344
345 for (auto &CallRecord : *CG[F]) {
346 if (!CallRecord.second)
347 continue;
348
349 Function *Callee = CallRecord.second->getFunction();
350 if (!Callee) {
351 if (!SeenUnknownCall) {
352 SeenUnknownCall = true;
353
354 // If we see any indirect calls, assume nothing about potential
355 // targets.
356 // TODO: This could be refined to possible LDS global users.
357 for (auto &ExternalCallRecord : *CG.getExternalCallingNode()) {
358 Function *PotentialCallee =
359 ExternalCallRecord.second->getFunction();
360 assert(PotentialCallee);
361 if (!isKernel(F: *PotentialCallee)) {
362 for (StringRef Attr : FnAttrs)
363 PotentialCallee->removeFnAttr(Kind: Attr);
364 }
365 }
366 }
367 } else {
368 for (StringRef Attr : FnAttrs)
369 Callee->removeFnAttr(Kind: Attr);
370 if (Visited.insert(Ptr: Callee).second)
371 WorkList.push_back(Elt: Callee);
372 }
373 }
374 }
375}
376
377bool isReallyAClobber(const Value *Ptr, MemoryDef *Def, AAResults *AA) {
378 Instruction *DefInst = Def->getMemoryInst();
379
380 if (isa<FenceInst>(Val: DefInst))
381 return false;
382
383 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: DefInst)) {
384 switch (II->getIntrinsicID()) {
385 case Intrinsic::amdgcn_s_barrier:
386 case Intrinsic::amdgcn_s_cluster_barrier:
387 case Intrinsic::amdgcn_s_barrier_signal:
388 case Intrinsic::amdgcn_s_barrier_signal_var:
389 case Intrinsic::amdgcn_s_barrier_signal_isfirst:
390 case Intrinsic::amdgcn_s_barrier_init:
391 case Intrinsic::amdgcn_s_barrier_join:
392 case Intrinsic::amdgcn_s_barrier_wait:
393 case Intrinsic::amdgcn_s_barrier_leave:
394 case Intrinsic::amdgcn_s_get_barrier_state:
395 case Intrinsic::amdgcn_s_wakeup_barrier:
396 case Intrinsic::amdgcn_wave_barrier:
397 case Intrinsic::amdgcn_sched_barrier:
398 case Intrinsic::amdgcn_sched_group_barrier:
399 case Intrinsic::amdgcn_iglp_opt:
400 return false;
401 default:
402 break;
403 }
404 }
405
406 // Ignore atomics not aliasing with the original load, any atomic is a
407 // universal MemoryDef from MSSA's point of view too, just like a fence.
408 const auto checkNoAlias = [AA, Ptr](auto I) -> bool {
409 return I && AA->isNoAlias(I->getPointerOperand(), Ptr);
410 };
411
412 if (checkNoAlias(dyn_cast<AtomicCmpXchgInst>(Val: DefInst)) ||
413 checkNoAlias(dyn_cast<AtomicRMWInst>(Val: DefInst)))
414 return false;
415
416 return true;
417}
418
419bool isClobberedInFunction(const LoadInst *Load, MemorySSA *MSSA,
420 AAResults *AA) {
421 MemorySSAWalker *Walker = MSSA->getWalker();
422 MemoryLocation Loc(MemoryLocation::get(LI: Load));
423 MemoryUseOrDef *Use = MSSA->getMemoryAccess(I: Load);
424 SmallVector<MemoryAccess *> WorkList{
425 Walker->getClobberingMemoryAccess(MA: Use->getDefiningAccess(), Loc)};
426 SmallPtrSet<MemoryAccess *, 8> Visited;
427
428 LLVM_DEBUG(dbgs() << "Checking clobbering of: " << *Load << '\n');
429
430 // Start with a nearest dominating clobbering access, it will be either
431 // live on entry (nothing to do, load is not clobbered), MemoryDef, or
432 // MemoryPhi if several MemoryDefs can define this memory state. In that
433 // case add all Defs to WorkList and continue going up and checking all
434 // the definitions of this memory location until the root. When all the
435 // defs are exhausted and came to the entry state we have no clobber.
436 // Along the scan ignore barriers and fences which are considered clobbers
437 // by the MemorySSA, but not really writing anything into the memory.
438 while (!WorkList.empty()) {
439 MemoryAccess *MA = WorkList.pop_back_val();
440 if (!Visited.insert(Ptr: MA).second)
441 continue;
442
443 if (MSSA->isLiveOnEntryDef(MA))
444 continue;
445
446 if (MemoryDef *Def = dyn_cast<MemoryDef>(Val: MA)) {
447 LLVM_DEBUG(dbgs() << " Def: " << *Def->getMemoryInst() << '\n');
448
449 if (isReallyAClobber(Ptr: Load->getPointerOperand(), Def, AA)) {
450 LLVM_DEBUG(dbgs() << " -> load is clobbered\n");
451 return true;
452 }
453
454 WorkList.push_back(
455 Elt: Walker->getClobberingMemoryAccess(MA: Def->getDefiningAccess(), Loc));
456 continue;
457 }
458
459 const MemoryPhi *Phi = cast<MemoryPhi>(Val: MA);
460 for (const auto &Use : Phi->incoming_values())
461 WorkList.push_back(
462 Elt: Walker->getClobberingMemoryAccess(MA: cast<MemoryAccess>(Val: &Use), Loc));
463 }
464
465 LLVM_DEBUG(dbgs() << " -> no clobber\n");
466 return false;
467}
468
469} // end namespace llvm::AMDGPU
470