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