llvm/lib/Analysis/MemoryProfileInfo.cpp

   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 }