xref: /llvm-project/llvm/lib/Analysis/MemoryProfileInfo.cpp (revision b2f3ac836aac166b8fb21690a0a480c816de0521)
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/IR/Constants.h"
15 #include "llvm/Support/CommandLine.h"
16 
17 using namespace llvm;
18 using 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.
24 cl::opt<float> MemProfLifetimeAccessDensityColdThreshold(
25     "memprof-lifetime-access-density-cold-threshold", cl::init(0.05),
26     cl::Hidden,
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.
32 cl::opt<unsigned> MemProfAveLifetimeColdThreshold(
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.
39 cl::opt<unsigned> MemProfMinAveLifetimeAccessDensityHotThreshold(
40     "memprof-min-ave-lifetime-access-density-hot-threshold", cl::init(1000),
41     cl::Hidden,
42     cl::desc("The minimum TotalLifetimeAccessDensity / AllocCount for an "
43              "allocation to be considered hot"));
44 
45 cl::opt<bool> MemProfReportHintedSizes(
46     "memprof-report-hinted-sizes", cl::init(false), cl::Hidden,
47     cl::desc("Report total allocation sizes of hinted allocations"));
48 
49 AllocationType llvm::memprof::getAllocType(uint64_t TotalLifetimeAccessDensity,
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 <
55           MemProfLifetimeAccessDensityColdThreshold
56       // Lifetime is expected to be in ms, so convert the threshold to ms.
57       && ((float)TotalLifetime) / AllocCount >=
58              MemProfAveLifetimeColdThreshold * 1000)
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 >
64       MemProfMinAveLifetimeAccessDensityHotThreshold)
65     return AllocationType::Hot;
66 
67   return AllocationType::NotCold;
68 }
69 
70 MDNode *llvm::memprof::buildCallstackMetadata(ArrayRef<uint64_t> CallStack,
71                                               LLVMContext &Ctx) {
72   std::vector<Metadata *> StackVals;
73   for (auto Id : CallStack) {
74     auto *StackValMD =
75         ValueAsMetadata::get(ConstantInt::get(Type::getInt64Ty(Ctx), Id));
76     StackVals.push_back(StackValMD);
77   }
78   return MDNode::get(Ctx, StackVals);
79 }
80 
81 MDNode *llvm::memprof::getMIBStackNode(const MDNode *MIB) {
82   assert(MIB->getNumOperands() >= 2);
83   // The stack metadata is the first operand of each memprof MIB metadata.
84   return cast<MDNode>(MIB->getOperand(0));
85 }
86 
87 AllocationType llvm::memprof::getMIBAllocType(const MDNode *MIB) {
88   assert(MIB->getNumOperands() >= 2);
89   // The allocation type is currently the second operand of each memprof
90   // MIB metadata. This will need to change as we add additional allocation
91   // types that can be applied based on the allocation profile data.
92   auto *MDS = dyn_cast<MDString>(MIB->getOperand(1));
93   assert(MDS);
94   if (MDS->getString() == "cold") {
95     return AllocationType::Cold;
96   } else if (MDS->getString() == "hot") {
97     return AllocationType::Hot;
98   }
99   return AllocationType::NotCold;
100 }
101 
102 uint64_t llvm::memprof::getMIBTotalSize(const MDNode *MIB) {
103   if (MIB->getNumOperands() < 3)
104     return 0;
105   return mdconst::dyn_extract<ConstantInt>(MIB->getOperand(2))->getZExtValue();
106 }
107 
108 std::string llvm::memprof::getAllocTypeAttributeString(AllocationType Type) {
109   switch (Type) {
110   case AllocationType::NotCold:
111     return "notcold";
112     break;
113   case AllocationType::Cold:
114     return "cold";
115     break;
116   case AllocationType::Hot:
117     return "hot";
118     break;
119   default:
120     assert(false && "Unexpected alloc type");
121   }
122   llvm_unreachable("invalid alloc type");
123 }
124 
125 static void addAllocTypeAttribute(LLVMContext &Ctx, CallBase *CI,
126                                   AllocationType AllocType) {
127   auto AllocTypeString = getAllocTypeAttributeString(AllocType);
128   auto A = llvm::Attribute::get(Ctx, "memprof", AllocTypeString);
129   CI->addFnAttr(A);
130 }
131 
132 bool llvm::memprof::hasSingleAllocType(uint8_t AllocTypes) {
133   const unsigned NumAllocTypes = llvm::popcount(AllocTypes);
134   assert(NumAllocTypes != 0);
135   return NumAllocTypes == 1;
136 }
137 
138 void CallStackTrie::addCallStack(AllocationType AllocType,
139                                  ArrayRef<uint64_t> StackIds,
140                                  uint64_t TotalSize) {
141   bool First = true;
142   CallStackTrieNode *Curr = nullptr;
143   for (auto StackId : StackIds) {
144     // If this is the first stack frame, add or update alloc node.
145     if (First) {
146       First = false;
147       if (Alloc) {
148         assert(AllocStackId == StackId);
149         Alloc->AllocTypes |= static_cast<uint8_t>(AllocType);
150         Alloc->TotalSize += TotalSize;
151       } else {
152         AllocStackId = StackId;
153         Alloc = new CallStackTrieNode(AllocType, TotalSize);
154       }
155       Curr = Alloc;
156       continue;
157     }
158     // Update existing caller node if it exists.
159     auto Next = Curr->Callers.find(StackId);
160     if (Next != Curr->Callers.end()) {
161       Curr = Next->second;
162       Curr->AllocTypes |= static_cast<uint8_t>(AllocType);
163       Curr->TotalSize += TotalSize;
164       continue;
165     }
166     // Otherwise add a new caller node.
167     auto *New = new CallStackTrieNode(AllocType, TotalSize);
168     Curr->Callers[StackId] = New;
169     Curr = New;
170   }
171   assert(Curr);
172 }
173 
174 void CallStackTrie::addCallStack(MDNode *MIB) {
175   MDNode *StackMD = getMIBStackNode(MIB);
176   assert(StackMD);
177   std::vector<uint64_t> CallStack;
178   CallStack.reserve(StackMD->getNumOperands());
179   for (const auto &MIBStackIter : StackMD->operands()) {
180     auto *StackId = mdconst::dyn_extract<ConstantInt>(MIBStackIter);
181     assert(StackId);
182     CallStack.push_back(StackId->getZExtValue());
183   }
184   addCallStack(getMIBAllocType(MIB), CallStack, getMIBTotalSize(MIB));
185 }
186 
187 static MDNode *createMIBNode(LLVMContext &Ctx, ArrayRef<uint64_t> MIBCallStack,
188                              AllocationType AllocType, uint64_t TotalSize) {
189   SmallVector<Metadata *> MIBPayload(
190       {buildCallstackMetadata(MIBCallStack, Ctx)});
191   MIBPayload.push_back(
192       MDString::get(Ctx, getAllocTypeAttributeString(AllocType)));
193   if (TotalSize)
194     MIBPayload.push_back(ValueAsMetadata::get(
195         ConstantInt::get(Type::getInt64Ty(Ctx), TotalSize)));
196   return MDNode::get(Ctx, MIBPayload);
197 }
198 
199 // Recursive helper to trim contexts and create metadata nodes.
200 // Caller should have pushed Node's loc to MIBCallStack. Doing this in the
201 // caller makes it simpler to handle the many early returns in this method.
202 bool CallStackTrie::buildMIBNodes(CallStackTrieNode *Node, LLVMContext &Ctx,
203                                   std::vector<uint64_t> &MIBCallStack,
204                                   std::vector<Metadata *> &MIBNodes,
205                                   bool CalleeHasAmbiguousCallerContext) {
206   // Trim context below the first node in a prefix with a single alloc type.
207   // Add an MIB record for the current call stack prefix.
208   if (hasSingleAllocType(Node->AllocTypes)) {
209     MIBNodes.push_back(createMIBNode(
210         Ctx, MIBCallStack, (AllocationType)Node->AllocTypes, Node->TotalSize));
211     return true;
212   }
213 
214   // We don't have a single allocation for all the contexts sharing this prefix,
215   // so recursively descend into callers in trie.
216   if (!Node->Callers.empty()) {
217     bool NodeHasAmbiguousCallerContext = Node->Callers.size() > 1;
218     bool AddedMIBNodesForAllCallerContexts = true;
219     for (auto &Caller : Node->Callers) {
220       MIBCallStack.push_back(Caller.first);
221       AddedMIBNodesForAllCallerContexts &=
222           buildMIBNodes(Caller.second, Ctx, MIBCallStack, MIBNodes,
223                         NodeHasAmbiguousCallerContext);
224       // Remove Caller.
225       MIBCallStack.pop_back();
226     }
227     if (AddedMIBNodesForAllCallerContexts)
228       return true;
229     // We expect that the callers should be forced to add MIBs to disambiguate
230     // the context in this case (see below).
231     assert(!NodeHasAmbiguousCallerContext);
232   }
233 
234   // If we reached here, then this node does not have a single allocation type,
235   // and we didn't add metadata for a longer call stack prefix including any of
236   // Node's callers. That means we never hit a single allocation type along all
237   // call stacks with this prefix. This can happen due to recursion collapsing
238   // or the stack being deeper than tracked by the profiler runtime, leading to
239   // contexts with different allocation types being merged. In that case, we
240   // trim the context just below the deepest context split, which is this
241   // node if the callee has an ambiguous caller context (multiple callers),
242   // since the recursive calls above returned false. Conservatively give it
243   // non-cold allocation type.
244   if (!CalleeHasAmbiguousCallerContext)
245     return false;
246   MIBNodes.push_back(createMIBNode(Ctx, MIBCallStack, AllocationType::NotCold,
247                                    Node->TotalSize));
248   return true;
249 }
250 
251 // Build and attach the minimal necessary MIB metadata. If the alloc has a
252 // single allocation type, add a function attribute instead. Returns true if
253 // memprof metadata attached, false if not (attribute added).
254 bool CallStackTrie::buildAndAttachMIBMetadata(CallBase *CI) {
255   auto &Ctx = CI->getContext();
256   if (hasSingleAllocType(Alloc->AllocTypes)) {
257     addAllocTypeAttribute(Ctx, CI, (AllocationType)Alloc->AllocTypes);
258     if (MemProfReportHintedSizes) {
259       assert(Alloc->TotalSize);
260       errs() << "Total size for allocation with location hash " << AllocStackId
261              << " and single alloc type "
262              << getAllocTypeAttributeString((AllocationType)Alloc->AllocTypes)
263              << ": " << Alloc->TotalSize << "\n";
264     }
265     return false;
266   }
267   std::vector<uint64_t> MIBCallStack;
268   MIBCallStack.push_back(AllocStackId);
269   std::vector<Metadata *> MIBNodes;
270   assert(!Alloc->Callers.empty() && "addCallStack has not been called yet");
271   // The last parameter is meant to say whether the callee of the given node
272   // has more than one caller. Here the node being passed in is the alloc
273   // and it has no callees. So it's false.
274   if (buildMIBNodes(Alloc, Ctx, MIBCallStack, MIBNodes, false)) {
275     assert(MIBCallStack.size() == 1 &&
276            "Should only be left with Alloc's location in stack");
277     CI->setMetadata(LLVMContext::MD_memprof, MDNode::get(Ctx, MIBNodes));
278     return true;
279   }
280   // If there exists corner case that CallStackTrie has one chain to leaf
281   // and all node in the chain have multi alloc type, conservatively give
282   // it non-cold allocation type.
283   // FIXME: Avoid this case before memory profile created.
284   addAllocTypeAttribute(Ctx, CI, AllocationType::NotCold);
285   return false;
286 }
287 
288 template <>
289 CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::CallStackIterator(
290     const MDNode *N, bool End)
291     : N(N) {
292   if (!N)
293     return;
294   Iter = End ? N->op_end() : N->op_begin();
295 }
296 
297 template <>
298 uint64_t
299 CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::operator*() {
300   assert(Iter != N->op_end());
301   ConstantInt *StackIdCInt = mdconst::dyn_extract<ConstantInt>(*Iter);
302   assert(StackIdCInt);
303   return StackIdCInt->getZExtValue();
304 }
305 
306 template <> uint64_t CallStack<MDNode, MDNode::op_iterator>::back() const {
307   assert(N);
308   return mdconst::dyn_extract<ConstantInt>(N->operands().back())
309       ->getZExtValue();
310 }
311