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(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(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(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(ConstantInt::get(Type::getInt64Ty(Ctx), Id));
71     StackVals.push_back(StackValMD);
72   }
73   return MDNode::get(Ctx, 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>(MIB->getOperand(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>(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 
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(AllocType);
117   auto A = llvm::Attribute::get(Ctx, "memprof", AllocTypeString);
118   CI->addFnAttr(A);
119 }
120 
121 bool llvm::memprof::hasSingleAllocType(uint8_t AllocTypes) {
122   const unsigned NumAllocTypes = llvm::popcount(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(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(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   }
170   addCallStack(getMIBAllocType(MIB), 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(MIBCallStack, Ctx)});
178   MIBPayload.push_back(
179       MDString::get(Ctx, getAllocTypeAttributeString(AllocType)));
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.
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(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).
237 bool CallStackTrie::buildAndAttachMIBMetadata(CallBase *CI) {
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   buildMIBNodes(Alloc, Ctx, MIBCallStack, MIBNodes,
248                 /*CalleeHasAmbiguousCallerContext=*/true);
249   assert(MIBCallStack.size() == 1 &&
250          "Should only be left with Alloc's location in stack");
251   CI->setMetadata(LLVMContext::MD_memprof, MDNode::get(Ctx, MIBNodes));
252   return true;
253 }
254 
255 template <>
256 CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::CallStackIterator(
257     const MDNode *N, bool End)
258     : N(N) {
259   if (!N)
260     return;
261   Iter = End ? N->op_end() : N->op_begin();
262 }
263 
264 template <>
265 uint64_t
266 CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::operator*() {
267   assert(Iter != N->op_end());
268   ConstantInt *StackIdCInt = mdconst::dyn_extract<ConstantInt>(*Iter);
269   assert(StackIdCInt);
270   return StackIdCInt->getZExtValue();
271 }
272 
273 template <> uint64_t CallStack<MDNode, MDNode::op_iterator>::back() const {
274   assert(N);
275   return mdconst::dyn_extract<ConstantInt>(N->operands().back())
276       ->getZExtValue();
277 }
278