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
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.
23cl::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.
31cl::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.
38cl::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
44AllocationType 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
65MDNode *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
76MDNode *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
82AllocationType 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
97std::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
114static 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
121bool llvm::memprof::hasSingleAllocType(uint8_t AllocTypes) {
122 const unsigned NumAllocTypes = llvm::popcount(Value: AllocTypes);
123 assert(NumAllocTypes != 0);
124 return NumAllocTypes == 1;
125}
126
127void 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
160void 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
173static 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.
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(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).
237bool 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
264template <>
265CallStack<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
273template <>
274uint64_t
275CallStack<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
282template <> 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

source code of llvm/lib/Analysis/MemoryProfileInfo.cpp