blob: 7fbcffc6489dcfd43631be9a9aa3698f1ce15273 [file] [log] [blame]
//===-- MemoryProfileInfo.cpp - memory profile info ------------------------==//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// This file contains utilities to analyze memory profile information.
#include "llvm/Analysis/MemoryProfileInfo.h"
#include "llvm/Support/CommandLine.h"
using namespace llvm;
using namespace llvm::memprof;
#define DEBUG_TYPE "memory-profile-info"
// Upper bound on lifetime access density (accesses per byte per lifetime sec)
// for marking an allocation cold.
cl::opt<float> MemProfLifetimeAccessDensityColdThreshold(
"memprof-lifetime-access-density-cold-threshold", cl::init(0.05),
cl::desc("The threshold the lifetime access density (accesses per byte per "
"lifetime sec) must be under to consider an allocation cold"));
// Lower bound on lifetime to mark an allocation cold (in addition to accesses
// per byte per sec above). This is to avoid pessimizing short lived objects.
cl::opt<unsigned> MemProfAveLifetimeColdThreshold(
"memprof-ave-lifetime-cold-threshold", cl::init(200), cl::Hidden,
cl::desc("The average lifetime (s) for an allocation to be considered "
// Lower bound on average lifetime accesses density (total life time access
// density / alloc count) for marking an allocation hot.
cl::opt<unsigned> MemProfMinAveLifetimeAccessDensityHotThreshold(
"memprof-min-ave-lifetime-access-density-hot-threshold", cl::init(1000),
cl::desc("The minimum TotalLifetimeAccessDensity / AllocCount for an "
"allocation to be considered hot"));
AllocationType llvm::memprof::getAllocType(uint64_t TotalLifetimeAccessDensity,
uint64_t AllocCount,
uint64_t TotalLifetime) {
// The access densities are multiplied by 100 to hold 2 decimal places of
// precision, so need to divide by 100.
if (((float)TotalLifetimeAccessDensity) / AllocCount / 100 <
// Lifetime is expected to be in ms, so convert the threshold to ms.
&& ((float)TotalLifetime) / AllocCount >=
MemProfAveLifetimeColdThreshold * 1000)
return AllocationType::Cold;
// The access densities are multiplied by 100 to hold 2 decimal places of
// precision, so need to divide by 100.
if (((float)TotalLifetimeAccessDensity) / AllocCount / 100 >
return AllocationType::Hot;
return AllocationType::NotCold;
MDNode *llvm::memprof::buildCallstackMetadata(ArrayRef<uint64_t> CallStack,
LLVMContext &Ctx) {
std::vector<Metadata *> StackVals;
for (auto Id : CallStack) {
auto *StackValMD =
ValueAsMetadata::get(ConstantInt::get(Type::getInt64Ty(Ctx), Id));
return MDNode::get(Ctx, StackVals);
MDNode *llvm::memprof::getMIBStackNode(const MDNode *MIB) {
assert(MIB->getNumOperands() == 2);
// The stack metadata is the first operand of each memprof MIB metadata.
return cast<MDNode>(MIB->getOperand(0));
AllocationType llvm::memprof::getMIBAllocType(const MDNode *MIB) {
assert(MIB->getNumOperands() == 2);
// The allocation type is currently the second operand of each memprof
// MIB metadata. This will need to change as we add additional allocation
// types that can be applied based on the allocation profile data.
auto *MDS = dyn_cast<MDString>(MIB->getOperand(1));
if (MDS->getString().equals("cold")) {
return AllocationType::Cold;
} else if (MDS->getString().equals("hot")) {
return AllocationType::Hot;
return AllocationType::NotCold;
std::string llvm::memprof::getAllocTypeAttributeString(AllocationType Type) {
switch (Type) {
case AllocationType::NotCold:
return "notcold";
case AllocationType::Cold:
return "cold";
case AllocationType::Hot:
return "hot";
assert(false && "Unexpected alloc type");
llvm_unreachable("invalid alloc type");
static void addAllocTypeAttribute(LLVMContext &Ctx, CallBase *CI,
AllocationType AllocType) {
auto AllocTypeString = getAllocTypeAttributeString(AllocType);
auto A = llvm::Attribute::get(Ctx, "memprof", AllocTypeString);
bool llvm::memprof::hasSingleAllocType(uint8_t AllocTypes) {
const unsigned NumAllocTypes = llvm::popcount(AllocTypes);
assert(NumAllocTypes != 0);
return NumAllocTypes == 1;
void CallStackTrie::addCallStack(AllocationType AllocType,
ArrayRef<uint64_t> StackIds) {
bool First = true;
CallStackTrieNode *Curr = nullptr;
for (auto StackId : StackIds) {
// If this is the first stack frame, add or update alloc node.
if (First) {
First = false;
if (Alloc) {
assert(AllocStackId == StackId);
Alloc->AllocTypes |= static_cast<uint8_t>(AllocType);
} else {
AllocStackId = StackId;
Alloc = new CallStackTrieNode(AllocType);
Curr = Alloc;
// Update existing caller node if it exists.
auto Next = Curr->Callers.find(StackId);
if (Next != Curr->Callers.end()) {
Curr = Next->second;
Curr->AllocTypes |= static_cast<uint8_t>(AllocType);
// Otherwise add a new caller node.
auto *New = new CallStackTrieNode(AllocType);
Curr->Callers[StackId] = New;
Curr = New;
void CallStackTrie::addCallStack(MDNode *MIB) {
MDNode *StackMD = getMIBStackNode(MIB);
std::vector<uint64_t> CallStack;
for (const auto &MIBStackIter : StackMD->operands()) {
auto *StackId = mdconst::dyn_extract<ConstantInt>(MIBStackIter);
addCallStack(getMIBAllocType(MIB), CallStack);
static MDNode *createMIBNode(LLVMContext &Ctx,
std::vector<uint64_t> &MIBCallStack,
AllocationType AllocType) {
std::vector<Metadata *> MIBPayload(
{buildCallstackMetadata(MIBCallStack, Ctx)});
MDString::get(Ctx, getAllocTypeAttributeString(AllocType)));
return MDNode::get(Ctx, MIBPayload);
// Recursive helper to trim contexts and create metadata nodes.
// Caller should have pushed Node's loc to MIBCallStack. Doing this in the
// caller makes it simpler to handle the many early returns in this method.
bool CallStackTrie::buildMIBNodes(CallStackTrieNode *Node, LLVMContext &Ctx,
std::vector<uint64_t> &MIBCallStack,
std::vector<Metadata *> &MIBNodes,
bool CalleeHasAmbiguousCallerContext) {
// Trim context below the first node in a prefix with a single alloc type.
// Add an MIB record for the current call stack prefix.
if (hasSingleAllocType(Node->AllocTypes)) {
createMIBNode(Ctx, MIBCallStack, (AllocationType)Node->AllocTypes));
return true;
// We don't have a single allocation for all the contexts sharing this prefix,
// so recursively descend into callers in trie.
if (!Node->Callers.empty()) {
bool NodeHasAmbiguousCallerContext = Node->Callers.size() > 1;
bool AddedMIBNodesForAllCallerContexts = true;
for (auto &Caller : Node->Callers) {
AddedMIBNodesForAllCallerContexts &=
buildMIBNodes(Caller.second, Ctx, MIBCallStack, MIBNodes,
// Remove Caller.
if (AddedMIBNodesForAllCallerContexts)
return true;
// We expect that the callers should be forced to add MIBs to disambiguate
// the context in this case (see below).
// If we reached here, then this node does not have a single allocation type,
// and we didn't add metadata for a longer call stack prefix including any of
// Node's callers. That means we never hit a single allocation type along all
// call stacks with this prefix. This can happen due to recursion collapsing
// or the stack being deeper than tracked by the profiler runtime, leading to
// contexts with different allocation types being merged. In that case, we
// trim the context just below the deepest context split, which is this
// node if the callee has an ambiguous caller context (multiple callers),
// since the recursive calls above returned false. Conservatively give it
// non-cold allocation type.
if (!CalleeHasAmbiguousCallerContext)
return false;
MIBNodes.push_back(createMIBNode(Ctx, MIBCallStack, AllocationType::NotCold));
return true;
// Build and attach the minimal necessary MIB metadata. If the alloc has a
// single allocation type, add a function attribute instead. Returns true if
// memprof metadata attached, false if not (attribute added).
bool CallStackTrie::buildAndAttachMIBMetadata(CallBase *CI) {
auto &Ctx = CI->getContext();
if (hasSingleAllocType(Alloc->AllocTypes)) {
addAllocTypeAttribute(Ctx, CI, (AllocationType)Alloc->AllocTypes);
return false;
std::vector<uint64_t> MIBCallStack;
std::vector<Metadata *> MIBNodes;
assert(!Alloc->Callers.empty() && "addCallStack has not been called yet");
buildMIBNodes(Alloc, Ctx, MIBCallStack, MIBNodes,
assert(MIBCallStack.size() == 1 &&
"Should only be left with Alloc's location in stack");
CI->setMetadata(LLVMContext::MD_memprof, MDNode::get(Ctx, MIBNodes));
return true;
template <>
CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::CallStackIterator(
const MDNode *N, bool End)
: N(N) {
if (!N)
Iter = End ? N->op_end() : N->op_begin();
template <>
CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::operator*() {
assert(Iter != N->op_end());
ConstantInt *StackIdCInt = mdconst::dyn_extract<ConstantInt>(*Iter);
return StackIdCInt->getZExtValue();
template <> uint64_t CallStack<MDNode, MDNode::op_iterator>::back() const {
return mdconst::dyn_extract<ConstantInt>(N->operands().back())