LLVM  16.0.0git
MemoryProfileInfo.cpp
Go to the documentation of this file.
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 
15 
16 using namespace llvm;
17 using namespace llvm::memprof;
18 
19 #define DEBUG_TYPE "memory-profile-info"
20 
21 // Upper bound on accesses per byte for marking an allocation cold.
23  "memprof-accesses-per-byte-cold-threshold", cl::init(10.0), cl::Hidden,
24  cl::desc("The threshold the accesses per byte must be under to consider "
25  "an allocation cold"));
26 
27 // Lower bound on lifetime to mark an allocation cold (in addition to accesses
28 // per byte above). This is to avoid pessimizing short lived objects.
30  "memprof-min-lifetime-cold-threshold", cl::init(200), cl::Hidden,
31  cl::desc("The minimum lifetime (s) for an allocation to be considered "
32  "cold"));
33 
35  uint64_t MinSize,
36  uint64_t MinLifetime) {
37  if (((float)MaxAccessCount) / MinSize < MemProfAccessesPerByteColdThreshold &&
38  // MinLifetime is expected to be in ms, so convert the threshold to ms.
39  MinLifetime >= MemProfMinLifetimeColdThreshold * 1000)
40  return AllocationType::Cold;
42 }
43 
45  LLVMContext &Ctx) {
46  std::vector<Metadata *> StackVals;
47  for (auto Id : CallStack) {
48  auto *StackValMD =
50  StackVals.push_back(StackValMD);
51  }
52  return MDNode::get(Ctx, StackVals);
53 }
54 
56  assert(MIB->getNumOperands() == 2);
57  // The stack metadata is the first operand of each memprof MIB metadata.
58  return cast<MDNode>(MIB->getOperand(0));
59 }
60 
62  assert(MIB->getNumOperands() == 2);
63  // The allocation type is currently the second operand of each memprof
64  // MIB metadata. This will need to change as we add additional allocation
65  // types that can be applied based on the allocation profile data.
66  auto *MDS = dyn_cast<MDString>(MIB->getOperand(1));
67  assert(MDS);
68  if (MDS->getString().equals("cold"))
69  return AllocationType::Cold;
71 }
72 
74  switch (Type) {
76  return "notcold";
77  break;
79  return "cold";
80  break;
81  default:
82  assert(false && "Unexpected alloc type");
83  }
84  llvm_unreachable("invalid alloc type");
85 }
86 
89  auto AllocTypeString = getAllocTypeAttributeString(AllocType);
90  auto A = llvm::Attribute::get(Ctx, "memprof", AllocTypeString);
91  CI->addFnAttr(A);
92 }
93 
94 static bool hasSingleAllocType(uint8_t AllocTypes) {
95  const unsigned NumAllocTypes = countPopulation(AllocTypes);
96  assert(NumAllocTypes != 0);
97  return NumAllocTypes == 1;
98 }
99 
101  ArrayRef<uint64_t> StackIds) {
102  bool First = true;
103  CallStackTrieNode *Curr = nullptr;
104  for (auto StackId : StackIds) {
105  // If this is the first stack frame, add or update alloc node.
106  if (First) {
107  First = false;
108  if (Alloc) {
109  assert(AllocStackId == StackId);
110  Alloc->AllocTypes |= static_cast<uint8_t>(AllocType);
111  } else {
112  AllocStackId = StackId;
113  Alloc = new CallStackTrieNode(AllocType);
114  }
115  Curr = Alloc;
116  continue;
117  }
118  // Update existing caller node if it exists.
119  auto Next = Curr->Callers.find(StackId);
120  if (Next != Curr->Callers.end()) {
121  Curr = Next->second;
122  Curr->AllocTypes |= static_cast<uint8_t>(AllocType);
123  continue;
124  }
125  // Otherwise add a new caller node.
126  auto *New = new CallStackTrieNode(AllocType);
127  Curr->Callers[StackId] = New;
128  Curr = New;
129  }
130  assert(Curr);
131 }
132 
134  MDNode *StackMD = getMIBStackNode(MIB);
135  assert(StackMD);
136  std::vector<uint64_t> CallStack;
137  CallStack.reserve(StackMD->getNumOperands());
138  for (const auto &MIBStackIter : StackMD->operands()) {
139  auto *StackId = mdconst::dyn_extract<ConstantInt>(MIBStackIter);
140  assert(StackId);
141  CallStack.push_back(StackId->getZExtValue());
142  }
144 }
145 
147  std::vector<uint64_t> &MIBCallStack,
149  std::vector<Metadata *> MIBPayload(
150  {buildCallstackMetadata(MIBCallStack, Ctx)});
151  MIBPayload.push_back(
153  return MDNode::get(Ctx, MIBPayload);
154 }
155 
156 // Recursive helper to trim contexts and create metadata nodes.
157 // Caller should have pushed Node's loc to MIBCallStack. Doing this in the
158 // caller makes it simpler to handle the many early returns in this method.
159 bool CallStackTrie::buildMIBNodes(CallStackTrieNode *Node, LLVMContext &Ctx,
160  std::vector<uint64_t> &MIBCallStack,
161  std::vector<Metadata *> &MIBNodes,
162  bool CalleeHasAmbiguousCallerContext) {
163  // Trim context below the first node in a prefix with a single alloc type.
164  // Add an MIB record for the current call stack prefix.
165  if (hasSingleAllocType(Node->AllocTypes)) {
166  MIBNodes.push_back(
167  createMIBNode(Ctx, MIBCallStack, (AllocationType)Node->AllocTypes));
168  return true;
169  }
170 
171  // We don't have a single allocation for all the contexts sharing this prefix,
172  // so recursively descend into callers in trie.
173  if (!Node->Callers.empty()) {
174  bool NodeHasAmbiguousCallerContext = Node->Callers.size() > 1;
175  bool AddedMIBNodesForAllCallerContexts = true;
176  for (auto &Caller : Node->Callers) {
177  MIBCallStack.push_back(Caller.first);
178  AddedMIBNodesForAllCallerContexts &=
179  buildMIBNodes(Caller.second, Ctx, MIBCallStack, MIBNodes,
180  NodeHasAmbiguousCallerContext);
181  // Remove Caller.
182  MIBCallStack.pop_back();
183  }
184  if (AddedMIBNodesForAllCallerContexts)
185  return true;
186  // We expect that the callers should be forced to add MIBs to disambiguate
187  // the context in this case (see below).
188  assert(!NodeHasAmbiguousCallerContext);
189  }
190 
191  // If we reached here, then this node does not have a single allocation type,
192  // and we didn't add metadata for a longer call stack prefix including any of
193  // Node's callers. That means we never hit a single allocation type along all
194  // call stacks with this prefix. This can happen due to recursion collapsing
195  // or the stack being deeper than tracked by the profiler runtime, leading to
196  // contexts with different allocation types being merged. In that case, we
197  // trim the context just below the deepest context split, which is this
198  // node if the callee has an ambiguous caller context (multiple callers),
199  // since the recursive calls above returned false. Conservatively give it
200  // non-cold allocation type.
201  if (!CalleeHasAmbiguousCallerContext)
202  return false;
203  MIBNodes.push_back(createMIBNode(Ctx, MIBCallStack, AllocationType::NotCold));
204  return true;
205 }
206 
207 // Build and attach the minimal necessary MIB metadata. If the alloc has a
208 // single allocation type, add a function attribute instead. Returns true if
209 // memprof metadata attached, false if not (attribute added).
211  auto &Ctx = CI->getContext();
212  if (hasSingleAllocType(Alloc->AllocTypes)) {
213  addAllocTypeAttribute(Ctx, CI, (AllocationType)Alloc->AllocTypes);
214  return false;
215  }
216  std::vector<uint64_t> MIBCallStack;
217  MIBCallStack.push_back(AllocStackId);
218  std::vector<Metadata *> MIBNodes;
219  assert(!Alloc->Callers.empty() && "addCallStack has not been called yet");
220  buildMIBNodes(Alloc, Ctx, MIBCallStack, MIBNodes,
221  /*CalleeHasAmbiguousCallerContext=*/true);
222  assert(MIBCallStack.size() == 1 &&
223  "Should only be left with Alloc's location in stack");
224  CI->setMetadata(LLVMContext::MD_memprof, MDNode::get(Ctx, MIBNodes));
225  return true;
226 }
227 
228 template <>
230  const MDNode *N, bool End)
231  : N(N) {
232  if (!N)
233  return;
234  Iter = End ? N->op_end() : N->op_begin();
235 }
236 
237 template <>
238 uint64_t
240  assert(Iter != N->op_end());
241  ConstantInt *StackIdCInt = mdconst::dyn_extract<ConstantInt>(*Iter);
242  assert(StackIdCInt);
243  return StackIdCInt->getZExtValue();
244 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::memprof::getAllocType
AllocationType getAllocType(uint64_t MaxAccessCount, uint64_t MinSize, uint64_t MinLifetime)
Return the allocation type for a given set of memory profile values.
Definition: MemoryProfileInfo.cpp:34
llvm::Attribute::get
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:91
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::memprof::CallStack::CallStackIterator::CallStackIterator
CallStackIterator(const NodeT *N, bool End)
Definition: MemoryProfileInfo.h:137
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::memprof::getMIBAllocType
AllocationType getMIBAllocType(const MDNode *MIB)
Returns the allocation type from an MIB metadata node.
Definition: MemoryProfileInfo.cpp:61
llvm::memprof::CallStackTrie::buildAndAttachMIBMetadata
bool buildAndAttachMIBMetadata(CallBase *CI)
Build and attach the minimal necessary MIB metadata.
Definition: MemoryProfileInfo.cpp:210
llvm::ValueAsMetadata::get
static ValueAsMetadata * get(Value *V)
Definition: Metadata.cpp:393
llvm::MDNode::get
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1400
llvm::Instruction::setMetadata
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1456
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1298
CommandLine.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::memprof::CallStack
Helper class to iterate through stack ids in both metadata (memprof MIB and callsite) and the corresp...
Definition: MemoryProfileInfo.h:108
llvm::MDNode::operands
ArrayRef< MDOperand > operands() const
Definition: Metadata.h:1290
llvm::memprof::CallStack::CallStackIterator::operator*
uint64_t operator*()
Definition: MemoryProfileInfo.h:146
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
MemProfAccessesPerByteColdThreshold
cl::opt< float > MemProfAccessesPerByteColdThreshold("memprof-accesses-per-byte-cold-threshold", cl::init(10.0), cl::Hidden, cl::desc("The threshold the accesses per byte must be under to consider " "an allocation cold"))
llvm::pdb::PDB_SymType::Caller
@ Caller
llvm::CallBase::addFnAttr
void addFnAttr(Attribute::AttrKind Kind)
Adds the attribute to the function.
Definition: InstrTypes.h:1507
getAllocTypeAttributeString
static std::string getAllocTypeAttributeString(AllocationType Type)
Definition: MemoryProfileInfo.cpp:73
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:879
hasSingleAllocType
static bool hasSingleAllocType(uint8_t AllocTypes)
Definition: MemoryProfileInfo.cpp:94
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1292
llvm::cl::opt
Definition: CommandLine.h:1412
llvm::AllocationType::NotCold
@ NotCold
llvm::countPopulation
unsigned countPopulation(T Value)
Count the number of set bits in a value.
Definition: MathExtras.h:501
uint64_t
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::memprof::CallStack::CallStackIterator::Iter
IteratorT Iter
Definition: MemoryProfileInfo.h:118
llvm::MDString::get
static MDString * get(LLVMContext &Context, StringRef Str)
Definition: Metadata.cpp:498
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MDNode
Metadata node.
Definition: Metadata.h:944
llvm::memprof::CallStack::CallStackIterator::N
const NodeT * N
Definition: MemoryProfileInfo.h:117
createMIBNode
static MDNode * createMIBNode(LLVMContext &Ctx, std::vector< uint64_t > &MIBCallStack, AllocationType AllocType)
Definition: MemoryProfileInfo.cpp:146
llvm::ArrayRef< uint64_t >
llvm::memprof::getMIBStackNode
MDNode * getMIBStackNode(const MDNode *MIB)
Returns the stack node from an MIB metadata node.
Definition: MemoryProfileInfo.cpp:55
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
llvm::AllocationType
AllocationType
Definition: ModuleSummaryIndex.h:323
MemProfMinLifetimeColdThreshold
cl::opt< unsigned > MemProfMinLifetimeColdThreshold("memprof-min-lifetime-cold-threshold", cl::init(200), cl::Hidden, cl::desc("The minimum lifetime (s) for an allocation to be considered " "cold"))
llvm::memprof::buildCallstackMetadata
MDNode * buildCallstackMetadata(ArrayRef< uint64_t > CallStack, LLVMContext &Ctx)
Build callstack metadata from the provided list of call stack ids.
Definition: MemoryProfileInfo.cpp:44
llvm::ConstantInt::getZExtValue
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:142
llvm::memprof
Definition: MemoryProfileInfo.h:24
llvm::Type::getInt64Ty
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:240
MemoryProfileInfo.h
llvm::AllocationType::Cold
@ Cold
AllocType
AllocType
Definition: MemoryBuiltins.cpp:54
N
#define N
addAllocTypeAttribute
static void addAllocTypeAttribute(LLVMContext &Ctx, CallBase *CI, AllocationType AllocType)
Definition: MemoryProfileInfo.cpp:87
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1175
llvm::memprof::CallStackTrie::addCallStack
void addCallStack(AllocationType AllocType, ArrayRef< uint64_t > StackIds)
Add a call stack context with the given allocation type to the Trie.
Definition: MemoryProfileInfo.cpp:100
llvm::cl::desc
Definition: CommandLine.h:413
llvm::AMDGPU::VGPRIndexMode::Id
Id
Definition: SIDefines.h:241