LLVM 20.0.0git
MemoryProfileInfo.cpp
Go to the documentation of this file.
1//===-- MemoryProfileInfo.cpp - memory profile info ------------------------==//
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 file contains utilities to analyze memory profile information.
10//
11//===----------------------------------------------------------------------===//
12
14#include "llvm/IR/Constants.h"
16
17using namespace llvm;
18using namespace llvm::memprof;
19
20#define DEBUG_TYPE "memory-profile-info"
21
22// Upper bound on lifetime access density (accesses per byte per lifetime sec)
23// for marking an allocation cold.
25 "memprof-lifetime-access-density-cold-threshold", cl::init(0.05),
27 cl::desc("The threshold the lifetime access density (accesses per byte per "
28 "lifetime sec) must be under to consider an allocation cold"));
29
30// Lower bound on lifetime to mark an allocation cold (in addition to accesses
31// per byte per sec above). This is to avoid pessimizing short lived objects.
33 "memprof-ave-lifetime-cold-threshold", cl::init(200), cl::Hidden,
34 cl::desc("The average lifetime (s) for an allocation to be considered "
35 "cold"));
36
37// Lower bound on average lifetime accesses density (total life time access
38// density / alloc count) for marking an allocation hot.
40 "memprof-min-ave-lifetime-access-density-hot-threshold", cl::init(1000),
42 cl::desc("The minimum TotalLifetimeAccessDensity / AllocCount for an "
43 "allocation to be considered hot"));
44
46 "memprof-report-hinted-sizes", cl::init(false), cl::Hidden,
47 cl::desc("Report total allocation sizes of hinted allocations"));
48
50 uint64_t AllocCount,
51 uint64_t TotalLifetime) {
52 // The access densities are multiplied by 100 to hold 2 decimal places of
53 // precision, so need to divide by 100.
54 if (((float)TotalLifetimeAccessDensity) / AllocCount / 100 <
56 // Lifetime is expected to be in ms, so convert the threshold to ms.
57 && ((float)TotalLifetime) / AllocCount >=
59 return AllocationType::Cold;
60
61 // The access densities are multiplied by 100 to hold 2 decimal places of
62 // precision, so need to divide by 100.
63 if (((float)TotalLifetimeAccessDensity) / AllocCount / 100 >
65 return AllocationType::Hot;
66
67 return AllocationType::NotCold;
68}
69
71 LLVMContext &Ctx) {
73 StackVals.reserve(CallStack.size());
74 for (auto Id : CallStack) {
75 auto *StackValMD =
76 ValueAsMetadata::get(ConstantInt::get(Type::getInt64Ty(Ctx), Id));
77 StackVals.push_back(StackValMD);
78 }
79 return MDNode::get(Ctx, StackVals);
80}
81
83 assert(MIB->getNumOperands() >= 2);
84 // The stack metadata is the first operand of each memprof MIB metadata.
85 return cast<MDNode>(MIB->getOperand(0));
86}
87
89 assert(MIB->getNumOperands() >= 2);
90 // The allocation type is currently the second operand of each memprof
91 // MIB metadata. This will need to change as we add additional allocation
92 // types that can be applied based on the allocation profile data.
93 auto *MDS = dyn_cast<MDString>(MIB->getOperand(1));
94 assert(MDS);
95 if (MDS->getString() == "cold") {
96 return AllocationType::Cold;
97 } else if (MDS->getString() == "hot") {
98 return AllocationType::Hot;
99 }
100 return AllocationType::NotCold;
101}
102
104 switch (Type) {
105 case AllocationType::NotCold:
106 return "notcold";
107 break;
108 case AllocationType::Cold:
109 return "cold";
110 break;
111 case AllocationType::Hot:
112 return "hot";
113 break;
114 default:
115 assert(false && "Unexpected alloc type");
116 }
117 llvm_unreachable("invalid alloc type");
118}
119
122 auto AllocTypeString = getAllocTypeAttributeString(AllocType);
123 auto A = llvm::Attribute::get(Ctx, "memprof", AllocTypeString);
124 CI->addFnAttr(A);
125}
126
128 const unsigned NumAllocTypes = llvm::popcount(AllocTypes);
129 assert(NumAllocTypes != 0);
130 return NumAllocTypes == 1;
131}
132
135 std::vector<ContextTotalSize> ContextSizeInfo) {
136 bool First = true;
137 CallStackTrieNode *Curr = nullptr;
138 for (auto StackId : StackIds) {
139 // If this is the first stack frame, add or update alloc node.
140 if (First) {
141 First = false;
142 if (Alloc) {
143 assert(AllocStackId == StackId);
144 Alloc->AllocTypes |= static_cast<uint8_t>(AllocType);
145 } else {
146 AllocStackId = StackId;
147 Alloc = new CallStackTrieNode(AllocType);
148 }
149 Curr = Alloc;
150 continue;
151 }
152 // Update existing caller node if it exists.
153 auto Next = Curr->Callers.find(StackId);
154 if (Next != Curr->Callers.end()) {
155 Curr = Next->second;
156 Curr->AllocTypes |= static_cast<uint8_t>(AllocType);
157 continue;
158 }
159 // Otherwise add a new caller node.
160 auto *New = new CallStackTrieNode(AllocType);
161 Curr->Callers[StackId] = New;
162 Curr = New;
163 }
164 assert(Curr);
165 Curr->ContextSizeInfo.insert(Curr->ContextSizeInfo.end(),
166 ContextSizeInfo.begin(), ContextSizeInfo.end());
167}
168
170 MDNode *StackMD = getMIBStackNode(MIB);
171 assert(StackMD);
172 std::vector<uint64_t> CallStack;
173 CallStack.reserve(StackMD->getNumOperands());
174 for (const auto &MIBStackIter : StackMD->operands()) {
175 auto *StackId = mdconst::dyn_extract<ConstantInt>(MIBStackIter);
176 assert(StackId);
177 CallStack.push_back(StackId->getZExtValue());
178 }
179 std::vector<ContextTotalSize> ContextSizeInfo;
180 // Collect the context size information if it exists.
181 if (MIB->getNumOperands() > 2) {
182 for (unsigned I = 2; I < MIB->getNumOperands(); I++) {
183 MDNode *ContextSizePair = dyn_cast<MDNode>(MIB->getOperand(I));
184 assert(ContextSizePair->getNumOperands() == 2);
185 uint64_t FullStackId =
186 mdconst::dyn_extract<ConstantInt>(ContextSizePair->getOperand(0))
187 ->getZExtValue();
188 uint64_t TotalSize =
189 mdconst::dyn_extract<ConstantInt>(ContextSizePair->getOperand(1))
190 ->getZExtValue();
191 ContextSizeInfo.push_back({FullStackId, TotalSize});
192 }
193 }
194 addCallStack(getMIBAllocType(MIB), CallStack, std::move(ContextSizeInfo));
195}
196
199 ArrayRef<ContextTotalSize> ContextSizeInfo) {
200 SmallVector<Metadata *> MIBPayload(
201 {buildCallstackMetadata(MIBCallStack, Ctx)});
202 MIBPayload.push_back(
204 if (!ContextSizeInfo.empty()) {
205 for (const auto &[FullStackId, TotalSize] : ContextSizeInfo) {
206 auto *FullStackIdMD = ValueAsMetadata::get(
207 ConstantInt::get(Type::getInt64Ty(Ctx), FullStackId));
208 auto *TotalSizeMD = ValueAsMetadata::get(
209 ConstantInt::get(Type::getInt64Ty(Ctx), TotalSize));
210 auto *ContextSizeMD = MDNode::get(Ctx, {FullStackIdMD, TotalSizeMD});
211 MIBPayload.push_back(ContextSizeMD);
212 }
213 }
214 return MDNode::get(Ctx, MIBPayload);
215}
216
217void CallStackTrie::collectContextSizeInfo(
218 CallStackTrieNode *Node, std::vector<ContextTotalSize> &ContextSizeInfo) {
219 ContextSizeInfo.insert(ContextSizeInfo.end(), Node->ContextSizeInfo.begin(),
220 Node->ContextSizeInfo.end());
221 for (auto &Caller : Node->Callers)
222 collectContextSizeInfo(Caller.second, ContextSizeInfo);
223}
224
225// Recursive helper to trim contexts and create metadata nodes.
226// Caller should have pushed Node's loc to MIBCallStack. Doing this in the
227// caller makes it simpler to handle the many early returns in this method.
228bool CallStackTrie::buildMIBNodes(CallStackTrieNode *Node, LLVMContext &Ctx,
229 std::vector<uint64_t> &MIBCallStack,
230 std::vector<Metadata *> &MIBNodes,
231 bool CalleeHasAmbiguousCallerContext) {
232 // Trim context below the first node in a prefix with a single alloc type.
233 // Add an MIB record for the current call stack prefix.
234 if (hasSingleAllocType(Node->AllocTypes)) {
235 std::vector<ContextTotalSize> ContextSizeInfo;
236 collectContextSizeInfo(Node, ContextSizeInfo);
237 MIBNodes.push_back(createMIBNode(
238 Ctx, MIBCallStack, (AllocationType)Node->AllocTypes, ContextSizeInfo));
239 return true;
240 }
241
242 // We don't have a single allocation for all the contexts sharing this prefix,
243 // so recursively descend into callers in trie.
244 if (!Node->Callers.empty()) {
245 bool NodeHasAmbiguousCallerContext = Node->Callers.size() > 1;
246 bool AddedMIBNodesForAllCallerContexts = true;
247 for (auto &Caller : Node->Callers) {
248 MIBCallStack.push_back(Caller.first);
249 AddedMIBNodesForAllCallerContexts &=
250 buildMIBNodes(Caller.second, Ctx, MIBCallStack, MIBNodes,
251 NodeHasAmbiguousCallerContext);
252 // Remove Caller.
253 MIBCallStack.pop_back();
254 }
255 if (AddedMIBNodesForAllCallerContexts)
256 return true;
257 // We expect that the callers should be forced to add MIBs to disambiguate
258 // the context in this case (see below).
259 assert(!NodeHasAmbiguousCallerContext);
260 }
261
262 // If we reached here, then this node does not have a single allocation type,
263 // and we didn't add metadata for a longer call stack prefix including any of
264 // Node's callers. That means we never hit a single allocation type along all
265 // call stacks with this prefix. This can happen due to recursion collapsing
266 // or the stack being deeper than tracked by the profiler runtime, leading to
267 // contexts with different allocation types being merged. In that case, we
268 // trim the context just below the deepest context split, which is this
269 // node if the callee has an ambiguous caller context (multiple callers),
270 // since the recursive calls above returned false. Conservatively give it
271 // non-cold allocation type.
272 if (!CalleeHasAmbiguousCallerContext)
273 return false;
274 std::vector<ContextTotalSize> ContextSizeInfo;
275 collectContextSizeInfo(Node, ContextSizeInfo);
276 MIBNodes.push_back(createMIBNode(Ctx, MIBCallStack, AllocationType::NotCold,
277 ContextSizeInfo));
278 return true;
279}
280
282 StringRef Descriptor) {
283 addAllocTypeAttribute(CI->getContext(), CI, AT);
285 std::vector<ContextTotalSize> ContextSizeInfo;
286 collectContextSizeInfo(Alloc, ContextSizeInfo);
287 for (const auto &[FullStackId, TotalSize] : ContextSizeInfo) {
288 errs() << "MemProf hinting: Total size for full allocation context hash "
289 << FullStackId << " and " << Descriptor << " alloc type "
290 << getAllocTypeAttributeString(AT) << ": " << TotalSize << "\n";
291 }
292 }
293}
294
295// Build and attach the minimal necessary MIB metadata. If the alloc has a
296// single allocation type, add a function attribute instead. Returns true if
297// memprof metadata attached, false if not (attribute added).
299 if (hasSingleAllocType(Alloc->AllocTypes)) {
300 addSingleAllocTypeAttribute(CI, (AllocationType)Alloc->AllocTypes,
301 "single");
302 return false;
303 }
304 auto &Ctx = CI->getContext();
305 std::vector<uint64_t> MIBCallStack;
306 MIBCallStack.push_back(AllocStackId);
307 std::vector<Metadata *> MIBNodes;
308 assert(!Alloc->Callers.empty() && "addCallStack has not been called yet");
309 // The last parameter is meant to say whether the callee of the given node
310 // has more than one caller. Here the node being passed in is the alloc
311 // and it has no callees. So it's false.
312 if (buildMIBNodes(Alloc, Ctx, MIBCallStack, MIBNodes, false)) {
313 assert(MIBCallStack.size() == 1 &&
314 "Should only be left with Alloc's location in stack");
315 CI->setMetadata(LLVMContext::MD_memprof, MDNode::get(Ctx, MIBNodes));
316 return true;
317 }
318 // If there exists corner case that CallStackTrie has one chain to leaf
319 // and all node in the chain have multi alloc type, conservatively give
320 // it non-cold allocation type.
321 // FIXME: Avoid this case before memory profile created. Alternatively, select
322 // hint based on fraction cold.
324 return false;
325}
326
327template <>
329 const MDNode *N, bool End)
330 : N(N) {
331 if (!N)
332 return;
333 Iter = End ? N->op_end() : N->op_begin();
334}
335
336template <>
339 assert(Iter != N->op_end());
340 ConstantInt *StackIdCInt = mdconst::dyn_extract<ConstantInt>(*Iter);
341 assert(StackIdCInt);
342 return StackIdCInt->getZExtValue();
343}
344
346 assert(N);
347 return mdconst::dyn_extract<ConstantInt>(N->operands().back())
348 ->getZExtValue();
349}
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool End
Definition: ELF_riscv.cpp:480
#define I(x, y, z)
Definition: MD5.cpp:58
AllocType
cl::opt< float > MemProfLifetimeAccessDensityColdThreshold("memprof-lifetime-access-density-cold-threshold", cl::init(0.05), cl::Hidden, cl::desc("The threshold the lifetime access density (accesses per byte per " "lifetime sec) must be under to consider an allocation cold"))
cl::opt< unsigned > MemProfMinAveLifetimeAccessDensityHotThreshold("memprof-min-ave-lifetime-access-density-hot-threshold", cl::init(1000), cl::Hidden, cl::desc("The minimum TotalLifetimeAccessDensity / AllocCount for an " "allocation to be considered hot"))
cl::opt< bool > MemProfReportHintedSizes("memprof-report-hinted-sizes", cl::init(false), cl::Hidden, cl::desc("Report total allocation sizes of hinted allocations"))
static MDNode * createMIBNode(LLVMContext &Ctx, ArrayRef< uint64_t > MIBCallStack, AllocationType AllocType, ArrayRef< ContextTotalSize > ContextSizeInfo)
cl::opt< unsigned > MemProfAveLifetimeColdThreshold("memprof-ave-lifetime-cold-threshold", cl::init(200), cl::Hidden, cl::desc("The average lifetime (s) for an allocation to be considered " "cold"))
static void addAllocTypeAttribute(LLVMContext &Ctx, CallBase *CI, AllocationType AllocType)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:163
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:95
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1120
void addFnAttr(Attribute::AttrKind Kind)
Adds the attribute to the function.
Definition: InstrTypes.h:1482
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:157
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1679
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
Metadata node.
Definition: Metadata.h:1069
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1430
ArrayRef< MDOperand > operands() const
Definition: Metadata.h:1428
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1543
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1436
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:606
void push_back(Metadata *MD)
Append an element to the tuple. This will resize the node.
Definition: Metadata.h:1529
void reserve(size_type N)
Definition: SmallVector.h:663
void push_back(const T &Elt)
Definition: SmallVector.h:413
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:51
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
static IntegerType * getInt64Ty(LLVMContext &C)
static ValueAsMetadata * get(Value *V)
Definition: Metadata.cpp:501
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1075
void addCallStack(AllocationType AllocType, ArrayRef< uint64_t > StackIds, std::vector< ContextTotalSize > ContextSizeInfo={})
Add a call stack context with the given allocation type to the Trie.
void addSingleAllocTypeAttribute(CallBase *CI, AllocationType AT, StringRef Descriptor)
Add an attribute for the given allocation type to the call instruction.
bool buildAndAttachMIBMetadata(CallBase *CI)
Build and attach the minimal necessary MIB metadata.
Helper class to iterate through stack ids in both metadata (memprof MIB and callsite) and the corresp...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
MDNode * buildCallstackMetadata(ArrayRef< uint64_t > CallStack, LLVMContext &Ctx)
Build callstack metadata from the provided list of call stack ids.
AllocationType getAllocType(uint64_t TotalLifetimeAccessDensity, uint64_t AllocCount, uint64_t TotalLifetime)
Return the allocation type for a given set of memory profile values.
AllocationType getMIBAllocType(const MDNode *MIB)
Returns the allocation type from an MIB metadata node.
bool hasSingleAllocType(uint8_t AllocTypes)
True if the AllocTypes bitmask contains just a single type.
std::string getAllocTypeAttributeString(AllocationType Type)
Returns the string to use in attributes with the given type.
MDNode * getMIBStackNode(const MDNode *MIB)
Returns the stack node from an MIB metadata node.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
int popcount(T Value) noexcept
Count the number of set bits in a value.
Definition: bit.h:385
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
#define N