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 | |
13 | #include "llvm/Analysis/MemoryProfileInfo.h" |
14 | #include "llvm/Support/CommandLine.h" |
15 | |
16 | using namespace llvm; |
17 | using 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. |
23 | cl::opt<float> MemProfLifetimeAccessDensityColdThreshold( |
24 | "memprof-lifetime-access-density-cold-threshold" , cl::init(Val: 0.05), |
25 | cl::Hidden, |
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. |
31 | cl::opt<unsigned> MemProfAveLifetimeColdThreshold( |
32 | "memprof-ave-lifetime-cold-threshold" , cl::init(Val: 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. |
38 | cl::opt<unsigned> MemProfMinAveLifetimeAccessDensityHotThreshold( |
39 | "memprof-min-ave-lifetime-access-density-hot-threshold" , cl::init(Val: 1000), |
40 | cl::Hidden, |
41 | cl::desc("The minimum TotalLifetimeAccessDensity / AllocCount for an " |
42 | "allocation to be considered hot" )); |
43 | |
44 | AllocationType llvm::memprof::getAllocType(uint64_t TotalLifetimeAccessDensity, |
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 < |
50 | MemProfLifetimeAccessDensityColdThreshold |
51 | // Lifetime is expected to be in ms, so convert the threshold to ms. |
52 | && ((float)TotalLifetime) / AllocCount >= |
53 | MemProfAveLifetimeColdThreshold * 1000) |
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 > |
59 | MemProfMinAveLifetimeAccessDensityHotThreshold) |
60 | return AllocationType::Hot; |
61 | |
62 | return AllocationType::NotCold; |
63 | } |
64 | |
65 | MDNode *llvm::memprof::buildCallstackMetadata(ArrayRef<uint64_t> CallStack, |
66 | LLVMContext &Ctx) { |
67 | std::vector<Metadata *> StackVals; |
68 | for (auto Id : CallStack) { |
69 | auto *StackValMD = |
70 | ValueAsMetadata::get(V: ConstantInt::get(Ty: Type::getInt64Ty(C&: Ctx), V: Id)); |
71 | StackVals.push_back(x: StackValMD); |
72 | } |
73 | return MDNode::get(Context&: Ctx, MDs: StackVals); |
74 | } |
75 | |
76 | MDNode *llvm::memprof::getMIBStackNode(const MDNode *MIB) { |
77 | assert(MIB->getNumOperands() == 2); |
78 | // The stack metadata is the first operand of each memprof MIB metadata. |
79 | return cast<MDNode>(Val: MIB->getOperand(I: 0)); |
80 | } |
81 | |
82 | AllocationType llvm::memprof::getMIBAllocType(const MDNode *MIB) { |
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>(Val: MIB->getOperand(I: 1)); |
88 | assert(MDS); |
89 | if (MDS->getString().equals(RHS: "cold" )) { |
90 | return AllocationType::Cold; |
91 | } else if (MDS->getString().equals(RHS: "hot" )) { |
92 | return AllocationType::Hot; |
93 | } |
94 | return AllocationType::NotCold; |
95 | } |
96 | |
97 | std::string llvm::memprof::getAllocTypeAttributeString(AllocationType Type) { |
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 | |
114 | static void addAllocTypeAttribute(LLVMContext &Ctx, CallBase *CI, |
115 | AllocationType AllocType) { |
116 | auto AllocTypeString = getAllocTypeAttributeString(Type: AllocType); |
117 | auto A = llvm::Attribute::get(Context&: Ctx, Kind: "memprof" , Val: AllocTypeString); |
118 | CI->addFnAttr(Attr: A); |
119 | } |
120 | |
121 | bool llvm::memprof::hasSingleAllocType(uint8_t AllocTypes) { |
122 | const unsigned NumAllocTypes = llvm::popcount(Value: AllocTypes); |
123 | assert(NumAllocTypes != 0); |
124 | return NumAllocTypes == 1; |
125 | } |
126 | |
127 | void CallStackTrie::addCallStack(AllocationType AllocType, |
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(x: 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 | |
160 | void CallStackTrie::addCallStack(MDNode *MIB) { |
161 | MDNode *StackMD = getMIBStackNode(MIB); |
162 | assert(StackMD); |
163 | std::vector<uint64_t> CallStack; |
164 | CallStack.reserve(n: StackMD->getNumOperands()); |
165 | for (const auto &MIBStackIter : StackMD->operands()) { |
166 | auto *StackId = mdconst::dyn_extract<ConstantInt>(MD: MIBStackIter); |
167 | assert(StackId); |
168 | CallStack.push_back(x: StackId->getZExtValue()); |
169 | } |
170 | addCallStack(AllocType: getMIBAllocType(MIB), StackIds: CallStack); |
171 | } |
172 | |
173 | static MDNode *createMIBNode(LLVMContext &Ctx, |
174 | std::vector<uint64_t> &MIBCallStack, |
175 | AllocationType AllocType) { |
176 | std::vector<Metadata *> MIBPayload( |
177 | {buildCallstackMetadata(CallStack: MIBCallStack, Ctx)}); |
178 | MIBPayload.push_back( |
179 | x: MDString::get(Context&: Ctx, Str: getAllocTypeAttributeString(Type: AllocType))); |
180 | return MDNode::get(Context&: Ctx, MDs: 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. |
186 | bool 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(AllocTypes: Node->AllocTypes)) { |
193 | MIBNodes.push_back( |
194 | x: createMIBNode(Ctx, MIBCallStack, AllocType: (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(x: Caller.first); |
205 | AddedMIBNodesForAllCallerContexts &= |
206 | buildMIBNodes(Node: Caller.second, Ctx, MIBCallStack, MIBNodes, |
207 | CalleeHasAmbiguousCallerContext: 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(x: createMIBNode(Ctx, MIBCallStack, AllocType: 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). |
237 | bool CallStackTrie::buildAndAttachMIBMetadata(CallBase *CI) { |
238 | auto &Ctx = CI->getContext(); |
239 | if (hasSingleAllocType(AllocTypes: Alloc->AllocTypes)) { |
240 | addAllocTypeAttribute(Ctx, CI, AllocType: (AllocationType)Alloc->AllocTypes); |
241 | return false; |
242 | } |
243 | std::vector<uint64_t> MIBCallStack; |
244 | MIBCallStack.push_back(x: 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(Node: Alloc, Ctx, MIBCallStack, MIBNodes, CalleeHasAmbiguousCallerContext: false)) { |
251 | assert(MIBCallStack.size() == 1 && |
252 | "Should only be left with Alloc's location in stack" ); |
253 | CI->setMetadata(KindID: LLVMContext::MD_memprof, Node: MDNode::get(Context&: Ctx, MDs: 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. |
260 | addAllocTypeAttribute(Ctx, CI, AllocType: AllocationType::NotCold); |
261 | return false; |
262 | } |
263 | |
264 | template <> |
265 | CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::CallStackIterator( |
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 | |
273 | template <> |
274 | uint64_t |
275 | CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::operator*() { |
276 | assert(Iter != N->op_end()); |
277 | ConstantInt *StackIdCInt = mdconst::dyn_extract<ConstantInt>(MD: *Iter); |
278 | assert(StackIdCInt); |
279 | return StackIdCInt->getZExtValue(); |
280 | } |
281 | |
282 | template <> uint64_t CallStack<MDNode, MDNode::op_iterator>::back() const { |
283 | assert(N); |
284 | return mdconst::dyn_extract<ConstantInt>(MD: N->operands().back()) |
285 | ->getZExtValue(); |
286 | } |
287 | |