LLVM 19.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
15
16using namespace llvm;
17using namespace llvm::memprof;
18
19#define DEBUG_TYPE "memory-profile-info"
20
21// Upper bound on lifetime access density (accesses per byte per lifetime sec)
22// for marking an allocation cold.
24 "memprof-lifetime-access-density-cold-threshold", cl::init(0.05),
26 cl::desc("The threshold the lifetime access density (accesses per byte per "
27 "lifetime sec) must be under to consider an allocation cold"));
28
29// Lower bound on lifetime to mark an allocation cold (in addition to accesses
30// per byte per sec above). This is to avoid pessimizing short lived objects.
32 "memprof-ave-lifetime-cold-threshold", cl::init(200), cl::Hidden,
33 cl::desc("The average lifetime (s) for an allocation to be considered "
34 "cold"));
35
36// Lower bound on average lifetime accesses density (total life time access
37// density / alloc count) for marking an allocation hot.
39 "memprof-min-ave-lifetime-access-density-hot-threshold", cl::init(1000),
41 cl::desc("The minimum TotalLifetimeAccessDensity / AllocCount for an "
42 "allocation to be considered hot"));
43
45 uint64_t AllocCount,
46 uint64_t TotalLifetime) {
47 // The access densities are multiplied by 100 to hold 2 decimal places of
48 // precision, so need to divide by 100.
49 if (((float)TotalLifetimeAccessDensity) / AllocCount / 100 <
51 // Lifetime is expected to be in ms, so convert the threshold to ms.
52 && ((float)TotalLifetime) / AllocCount >=
54 return AllocationType::Cold;
55
56 // The access densities are multiplied by 100 to hold 2 decimal places of
57 // precision, so need to divide by 100.
58 if (((float)TotalLifetimeAccessDensity) / AllocCount / 100 >
60 return AllocationType::Hot;
61
62 return AllocationType::NotCold;
63}
64
66 LLVMContext &Ctx) {
67 std::vector<Metadata *> StackVals;
68 for (auto Id : CallStack) {
69 auto *StackValMD =
70 ValueAsMetadata::get(ConstantInt::get(Type::getInt64Ty(Ctx), Id));
71 StackVals.push_back(StackValMD);
72 }
73 return MDNode::get(Ctx, StackVals);
74}
75
77 assert(MIB->getNumOperands() == 2);
78 // The stack metadata is the first operand of each memprof MIB metadata.
79 return cast<MDNode>(MIB->getOperand(0));
80}
81
83 assert(MIB->getNumOperands() == 2);
84 // The allocation type is currently the second operand of each memprof
85 // MIB metadata. This will need to change as we add additional allocation
86 // types that can be applied based on the allocation profile data.
87 auto *MDS = dyn_cast<MDString>(MIB->getOperand(1));
88 assert(MDS);
89 if (MDS->getString().equals("cold")) {
90 return AllocationType::Cold;
91 } else if (MDS->getString().equals("hot")) {
92 return AllocationType::Hot;
93 }
94 return AllocationType::NotCold;
95}
96
98 switch (Type) {
99 case AllocationType::NotCold:
100 return "notcold";
101 break;
102 case AllocationType::Cold:
103 return "cold";
104 break;
105 case AllocationType::Hot:
106 return "hot";
107 break;
108 default:
109 assert(false && "Unexpected alloc type");
110 }
111 llvm_unreachable("invalid alloc type");
112}
113
116 auto AllocTypeString = getAllocTypeAttributeString(AllocType);
117 auto A = llvm::Attribute::get(Ctx, "memprof", AllocTypeString);
118 CI->addFnAttr(A);
119}
120
121bool llvm::memprof::hasSingleAllocType(uint8_t AllocTypes) {
122 const unsigned NumAllocTypes = llvm::popcount(AllocTypes);
123 assert(NumAllocTypes != 0);
124 return NumAllocTypes == 1;
125}
126
128 ArrayRef<uint64_t> StackIds) {
129 bool First = true;
130 CallStackTrieNode *Curr = nullptr;
131 for (auto StackId : StackIds) {
132 // If this is the first stack frame, add or update alloc node.
133 if (First) {
134 First = false;
135 if (Alloc) {
136 assert(AllocStackId == StackId);
137 Alloc->AllocTypes |= static_cast<uint8_t>(AllocType);
138 } else {
139 AllocStackId = StackId;
140 Alloc = new CallStackTrieNode(AllocType);
141 }
142 Curr = Alloc;
143 continue;
144 }
145 // Update existing caller node if it exists.
146 auto Next = Curr->Callers.find(StackId);
147 if (Next != Curr->Callers.end()) {
148 Curr = Next->second;
149 Curr->AllocTypes |= static_cast<uint8_t>(AllocType);
150 continue;
151 }
152 // Otherwise add a new caller node.
153 auto *New = new CallStackTrieNode(AllocType);
154 Curr->Callers[StackId] = New;
155 Curr = New;
156 }
157 assert(Curr);
158}
159
161 MDNode *StackMD = getMIBStackNode(MIB);
162 assert(StackMD);
163 std::vector<uint64_t> CallStack;
164 CallStack.reserve(StackMD->getNumOperands());
165 for (const auto &MIBStackIter : StackMD->operands()) {
166 auto *StackId = mdconst::dyn_extract<ConstantInt>(MIBStackIter);
167 assert(StackId);
168 CallStack.push_back(StackId->getZExtValue());
169 }
171}
172
174 std::vector<uint64_t> &MIBCallStack,
176 std::vector<Metadata *> MIBPayload(
177 {buildCallstackMetadata(MIBCallStack, Ctx)});
178 MIBPayload.push_back(
180 return MDNode::get(Ctx, MIBPayload);
181}
182
183// Recursive helper to trim contexts and create metadata nodes.
184// Caller should have pushed Node's loc to MIBCallStack. Doing this in the
185// caller makes it simpler to handle the many early returns in this method.
186bool CallStackTrie::buildMIBNodes(CallStackTrieNode *Node, LLVMContext &Ctx,
187 std::vector<uint64_t> &MIBCallStack,
188 std::vector<Metadata *> &MIBNodes,
189 bool CalleeHasAmbiguousCallerContext) {
190 // Trim context below the first node in a prefix with a single alloc type.
191 // Add an MIB record for the current call stack prefix.
192 if (hasSingleAllocType(Node->AllocTypes)) {
193 MIBNodes.push_back(
194 createMIBNode(Ctx, MIBCallStack, (AllocationType)Node->AllocTypes));
195 return true;
196 }
197
198 // We don't have a single allocation for all the contexts sharing this prefix,
199 // so recursively descend into callers in trie.
200 if (!Node->Callers.empty()) {
201 bool NodeHasAmbiguousCallerContext = Node->Callers.size() > 1;
202 bool AddedMIBNodesForAllCallerContexts = true;
203 for (auto &Caller : Node->Callers) {
204 MIBCallStack.push_back(Caller.first);
205 AddedMIBNodesForAllCallerContexts &=
206 buildMIBNodes(Caller.second, Ctx, MIBCallStack, MIBNodes,
207 NodeHasAmbiguousCallerContext);
208 // Remove Caller.
209 MIBCallStack.pop_back();
210 }
211 if (AddedMIBNodesForAllCallerContexts)
212 return true;
213 // We expect that the callers should be forced to add MIBs to disambiguate
214 // the context in this case (see below).
215 assert(!NodeHasAmbiguousCallerContext);
216 }
217
218 // If we reached here, then this node does not have a single allocation type,
219 // and we didn't add metadata for a longer call stack prefix including any of
220 // Node's callers. That means we never hit a single allocation type along all
221 // call stacks with this prefix. This can happen due to recursion collapsing
222 // or the stack being deeper than tracked by the profiler runtime, leading to
223 // contexts with different allocation types being merged. In that case, we
224 // trim the context just below the deepest context split, which is this
225 // node if the callee has an ambiguous caller context (multiple callers),
226 // since the recursive calls above returned false. Conservatively give it
227 // non-cold allocation type.
228 if (!CalleeHasAmbiguousCallerContext)
229 return false;
230 MIBNodes.push_back(createMIBNode(Ctx, MIBCallStack, AllocationType::NotCold));
231 return true;
232}
233
234// Build and attach the minimal necessary MIB metadata. If the alloc has a
235// single allocation type, add a function attribute instead. Returns true if
236// memprof metadata attached, false if not (attribute added).
238 auto &Ctx = CI->getContext();
239 if (hasSingleAllocType(Alloc->AllocTypes)) {
240 addAllocTypeAttribute(Ctx, CI, (AllocationType)Alloc->AllocTypes);
241 return false;
242 }
243 std::vector<uint64_t> MIBCallStack;
244 MIBCallStack.push_back(AllocStackId);
245 std::vector<Metadata *> MIBNodes;
246 assert(!Alloc->Callers.empty() && "addCallStack has not been called yet");
247 // The last parameter is meant to say whether the callee of the given node
248 // has more than one caller. Here the node being passed in is the alloc
249 // and it has no callees. So it's false.
250 if (buildMIBNodes(Alloc, Ctx, MIBCallStack, MIBNodes, false)) {
251 assert(MIBCallStack.size() == 1 &&
252 "Should only be left with Alloc's location in stack");
253 CI->setMetadata(LLVMContext::MD_memprof, MDNode::get(Ctx, MIBNodes));
254 return true;
255 }
256 // If there exists corner case that CallStackTrie has one chain to leaf
257 // and all node in the chain have multi alloc type, conservatively give
258 // it non-cold allocation type.
259 // FIXME: Avoid this case before memory profile created.
261 return false;
262}
263
264template <>
266 const MDNode *N, bool End)
267 : N(N) {
268 if (!N)
269 return;
270 Iter = End ? N->op_end() : N->op_begin();
271}
272
273template <>
276 assert(Iter != N->op_end());
277 ConstantInt *StackIdCInt = mdconst::dyn_extract<ConstantInt>(*Iter);
278 assert(StackIdCInt);
279 return StackIdCInt->getZExtValue();
280}
281
283 assert(N);
284 return mdconst::dyn_extract<ConstantInt>(N->operands().back())
285 ->getZExtValue();
286}
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
bool End
Definition: ELF_riscv.cpp:480
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"))
static MDNode * createMIBNode(LLVMContext &Ctx, std::vector< uint64_t > &MIBCallStack, AllocationType AllocType)
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
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:93
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1461
void addFnAttr(Attribute::AttrKind Kind)
Adds the attribute to the function.
Definition: InstrTypes.h:1818
This is the shared class of boolean and integer constants.
Definition: Constants.h:80
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:154
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1636
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
Metadata node.
Definition: Metadata.h:1067
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1428
ArrayRef< MDOperand > operands() const
Definition: Metadata.h:1426
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1541
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1434
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:600
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:495
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:1074
void addCallStack(AllocationType AllocType, ArrayRef< uint64_t > StackIds)
Add a call stack context with the given allocation type to the Trie.
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:450
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
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
#define N