third_party/llvm-16.0/llvm/lib/Analysis/MemoryProfileInfo.cpp - SwiftShader - Git at Google

 //===-- MemoryProfileInfo.cpp - memory profile info ------------------------==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt 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 accesses per byte for marking an allocation cold.
 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"));

 // Lower bound on lifetime to mark an allocation cold (in addition to accesses
 // per byte above). This is to avoid pessimizing short lived objects.
 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"));

 AllocationType llvm::memprof::getAllocType(uint64_t MaxAccessCount,
                                            uint64_t MinSize,
                                            uint64_t MinLifetime) {
   if (((float)MaxAccessCount) / MinSize < MemProfAccessesPerByteColdThreshold &&
       // MinLifetime is expected to be in ms, so convert the threshold to ms.
       MinLifetime >= MemProfMinLifetimeColdThreshold * 1000)
     return AllocationType::Cold;
   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));
     StackVals.push_back(StackValMD);
   }
   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));
   assert(MDS);
   if (MDS->getString().equals("cold"))
     return AllocationType::Cold;
   return AllocationType::NotCold;
 }

 static std::string getAllocTypeAttributeString(AllocationType Type) {
   switch (Type) {
   case AllocationType::NotCold:
     return "notcold";
     break;
   case AllocationType::Cold:
     return "cold";
     break;
   default:
     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);
   CI->addFnAttr(A);
 }

 static bool 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;
       continue;
     }
     // 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);
       continue;
     }
     // Otherwise add a new caller node.
     auto *New = new CallStackTrieNode(AllocType);
     Curr->Callers[StackId] = New;
     Curr = New;
   }
   assert(Curr);
 }

 void CallStackTrie::addCallStack(MDNode *MIB) {
   MDNode *StackMD = getMIBStackNode(MIB);
   assert(StackMD);
   std::vector<uint64_t> CallStack;
   CallStack.reserve(StackMD->getNumOperands());
   for (const auto &MIBStackIter : StackMD->operands()) {
     auto *StackId = mdconst::dyn_extract<ConstantInt>(MIBStackIter);
     assert(StackId);
     CallStack.push_back(StackId->getZExtValue());
   }
   addCallStack(getMIBAllocType(MIB), CallStack);
 }

 static MDNode *createMIBNode(LLVMContext &Ctx,
                              std::vector<uint64_t> &MIBCallStack,
                              AllocationType AllocType) {
   std::vector<Metadata *> MIBPayload(
       {buildCallstackMetadata(MIBCallStack, Ctx)});
   MIBPayload.push_back(
       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)) {
     MIBNodes.push_back(
         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) {
       MIBCallStack.push_back(Caller.first);
       AddedMIBNodesForAllCallerContexts &=
           buildMIBNodes(Caller.second, Ctx, MIBCallStack, MIBNodes,
                         NodeHasAmbiguousCallerContext);
       // Remove Caller.
       MIBCallStack.pop_back();
     }
     if (AddedMIBNodesForAllCallerContexts)
       return true;
     // We expect that the callers should be forced to add MIBs to disambiguate
     // the context in this case (see below).
     assert(!NodeHasAmbiguousCallerContext);
   }

   // 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;
   MIBCallStack.push_back(AllocStackId);
   std::vector<Metadata *> MIBNodes;
   assert(!Alloc->Callers.empty() && "addCallStack has not been called yet");
   buildMIBNodes(Alloc, Ctx, MIBCallStack, MIBNodes,
                 /*CalleeHasAmbiguousCallerContext=*/true);
   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)
     return;
   Iter = End ? N->op_end() : N->op_begin();
 }

 template <>
 uint64_t
 CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::operator*() {
   assert(Iter != N->op_end());
   ConstantInt *StackIdCInt = mdconst::dyn_extract<ConstantInt>(*Iter);
   assert(StackIdCInt);
   return StackIdCInt->getZExtValue();
 }
	//===-- MemoryProfileInfo.cpp - memory profile info ------------------------==//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt 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 accesses per byte for marking an allocation cold.
	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"));

	// Lower bound on lifetime to mark an allocation cold (in addition to accesses
	// per byte above). This is to avoid pessimizing short lived objects.
	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"));

	AllocationType llvm::memprof::getAllocType(uint64_t MaxAccessCount,
	uint64_t MinSize,
	uint64_t MinLifetime) {
	if (((float)MaxAccessCount) / MinSize < MemProfAccessesPerByteColdThreshold &&
	// MinLifetime is expected to be in ms, so convert the threshold to ms.
	MinLifetime >= MemProfMinLifetimeColdThreshold * 1000)
	return AllocationType::Cold;
	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));
	StackVals.push_back(StackValMD);
	}
	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));
	assert(MDS);
	if (MDS->getString().equals("cold"))
	return AllocationType::Cold;
	return AllocationType::NotCold;
	}

	static std::string getAllocTypeAttributeString(AllocationType Type) {
	switch (Type) {
	case AllocationType::NotCold:
	return "notcold";
	break;
	case AllocationType::Cold:
	return "cold";
	break;
	default:
	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);
	CI->addFnAttr(A);
	}

	static bool 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;
	continue;
	}
	// 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);
	continue;
	}
	// Otherwise add a new caller node.
	auto *New = new CallStackTrieNode(AllocType);
	Curr->Callers[StackId] = New;
	Curr = New;
	}
	assert(Curr);
	}

	void CallStackTrie::addCallStack(MDNode *MIB) {
	MDNode *StackMD = getMIBStackNode(MIB);
	assert(StackMD);
	std::vector<uint64_t> CallStack;
	CallStack.reserve(StackMD->getNumOperands());
	for (const auto &MIBStackIter : StackMD->operands()) {
	auto *StackId = mdconst::dyn_extract<ConstantInt>(MIBStackIter);
	assert(StackId);
	CallStack.push_back(StackId->getZExtValue());
	}
	addCallStack(getMIBAllocType(MIB), CallStack);
	}

	static MDNode *createMIBNode(LLVMContext &Ctx,
	std::vector<uint64_t> &MIBCallStack,
	AllocationType AllocType) {
	std::vector<Metadata *> MIBPayload(
	{buildCallstackMetadata(MIBCallStack, Ctx)});
	MIBPayload.push_back(
	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)) {
	MIBNodes.push_back(
	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) {
	MIBCallStack.push_back(Caller.first);
	AddedMIBNodesForAllCallerContexts &=
	buildMIBNodes(Caller.second, Ctx, MIBCallStack, MIBNodes,
	NodeHasAmbiguousCallerContext);
	// Remove Caller.
	MIBCallStack.pop_back();
	}
	if (AddedMIBNodesForAllCallerContexts)
	return true;
	// We expect that the callers should be forced to add MIBs to disambiguate
	// the context in this case (see below).
	assert(!NodeHasAmbiguousCallerContext);
	}

	// 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;
	MIBCallStack.push_back(AllocStackId);
	std::vector<Metadata *> MIBNodes;
	assert(!Alloc->Callers.empty() && "addCallStack has not been called yet");
	buildMIBNodes(Alloc, Ctx, MIBCallStack, MIBNodes,
	/CalleeHasAmbiguousCallerContext=/true);
	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)
	return;
	Iter = End ? N->op_end() : N->op_begin();
	}

	template <>
	uint64_t
	CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::operator*() {
	assert(Iter != N->op_end());
	ConstantInt StackIdCInt = mdconst::dyn_extract<ConstantInt>(Iter);
	assert(StackIdCInt);
	return StackIdCInt->getZExtValue();
	}