| //===- llvm/Analysis/MemoryProfileInfo.h - memory profile info ---*- C++ -*-==// |
| // |
| // 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. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_ANALYSIS_MEMORYPROFILEINFO_H |
| #define LLVM_ANALYSIS_MEMORYPROFILEINFO_H |
| |
| #include "llvm/IR/Constants.h" |
| #include "llvm/IR/InstrTypes.h" |
| #include "llvm/IR/Metadata.h" |
| #include "llvm/IR/Module.h" |
| #include "llvm/IR/ModuleSummaryIndex.h" |
| #include <map> |
| |
| namespace llvm { |
| namespace memprof { |
| |
| /// Return the allocation type for a given set of memory profile values. |
| AllocationType getAllocType(uint64_t MaxAccessCount, uint64_t MinSize, |
| uint64_t MinLifetime); |
| |
| /// Build callstack metadata from the provided list of call stack ids. Returns |
| /// the resulting metadata node. |
| MDNode *buildCallstackMetadata(ArrayRef<uint64_t> CallStack, LLVMContext &Ctx); |
| |
| /// Returns the stack node from an MIB metadata node. |
| MDNode *getMIBStackNode(const MDNode *MIB); |
| |
| /// Returns the allocation type from an MIB metadata node. |
| AllocationType getMIBAllocType(const MDNode *MIB); |
| |
| /// Class to build a trie of call stack contexts for a particular profiled |
| /// allocation call, along with their associated allocation types. |
| /// The allocation will be at the root of the trie, which is then used to |
| /// compute the minimum lists of context ids needed to associate a call context |
| /// with a single allocation type. |
| class CallStackTrie { |
| private: |
| struct CallStackTrieNode { |
| // Allocation types for call context sharing the context prefix at this |
| // node. |
| uint8_t AllocTypes; |
| // Map of caller stack id to the corresponding child Trie node. |
| std::map<uint64_t, CallStackTrieNode *> Callers; |
| CallStackTrieNode(AllocationType Type) |
| : AllocTypes(static_cast<uint8_t>(Type)) {} |
| }; |
| |
| // The node for the allocation at the root. |
| CallStackTrieNode *Alloc; |
| // The allocation's leaf stack id. |
| uint64_t AllocStackId; |
| |
| void deleteTrieNode(CallStackTrieNode *Node) { |
| if (!Node) |
| return; |
| for (auto C : Node->Callers) |
| deleteTrieNode(C.second); |
| delete Node; |
| } |
| |
| // Recursive helper to trim contexts and create metadata nodes. |
| bool buildMIBNodes(CallStackTrieNode *Node, LLVMContext &Ctx, |
| std::vector<uint64_t> &MIBCallStack, |
| std::vector<Metadata *> &MIBNodes, |
| bool CalleeHasAmbiguousCallerContext); |
| |
| public: |
| CallStackTrie() : Alloc(nullptr), AllocStackId(0) {} |
| ~CallStackTrie() { deleteTrieNode(Alloc); } |
| |
| bool empty() const { return Alloc == nullptr; } |
| |
| /// Add a call stack context with the given allocation type to the Trie. |
| /// The context is represented by the list of stack ids (computed during |
| /// matching via a debug location hash), expected to be in order from the |
| /// allocation call down to the bottom of the call stack (i.e. callee to |
| /// caller order). |
| void addCallStack(AllocationType AllocType, ArrayRef<uint64_t> StackIds); |
| |
| /// Add the call stack context along with its allocation type from the MIB |
| /// metadata to the Trie. |
| void addCallStack(MDNode *MIB); |
| |
| /// Build and attach the minimal necessary MIB metadata. If the alloc has a |
| /// single allocation type, add a function attribute instead. The reason for |
| /// adding an attribute in this case is that it matches how the behavior for |
| /// allocation calls will be communicated to lib call simplification after |
| /// cloning or another optimization to distinguish the allocation types, |
| /// which is lower overhead and more direct than maintaining this metadata. |
| /// Returns true if memprof metadata attached, false if not (attribute added). |
| bool buildAndAttachMIBMetadata(CallBase *CI); |
| }; |
| |
| /// Helper class to iterate through stack ids in both metadata (memprof MIB and |
| /// callsite) and the corresponding ThinLTO summary data structures |
| /// (CallsiteInfo and MIBInfo). This simplifies implementation of client code |
| /// which doesn't need to worry about whether we are operating with IR (Regular |
| /// LTO), or summary (ThinLTO). |
| template <class NodeT, class IteratorT> class CallStack { |
| public: |
| CallStack(const NodeT *N = nullptr) : N(N) {} |
| |
| // Implement minimum required methods for range-based for loop. |
| // The default implementation assumes we are operating on ThinLTO data |
| // structures, which have a vector of StackIdIndices. There are specialized |
| // versions provided to iterate through metadata. |
| struct CallStackIterator { |
| const NodeT *N = nullptr; |
| IteratorT Iter; |
| CallStackIterator(const NodeT *N, bool End); |
| uint64_t operator*(); |
| bool operator==(const CallStackIterator &rhs) { return Iter == rhs.Iter; } |
| bool operator!=(const CallStackIterator &rhs) { return !(*this == rhs); } |
| void operator++() { ++Iter; } |
| }; |
| |
| bool empty() const { return N == nullptr; } |
| |
| CallStackIterator begin() const; |
| CallStackIterator end() const { return CallStackIterator(N, /*End*/ true); } |
| CallStackIterator beginAfterSharedPrefix(CallStack &Other); |
| |
| private: |
| const NodeT *N = nullptr; |
| }; |
| |
| template <class NodeT, class IteratorT> |
| CallStack<NodeT, IteratorT>::CallStackIterator::CallStackIterator( |
| const NodeT *N, bool End) |
| : N(N) { |
| if (!N) |
| return; |
| Iter = End ? N->StackIdIndices.end() : N->StackIdIndices.begin(); |
| } |
| |
| template <class NodeT, class IteratorT> |
| uint64_t CallStack<NodeT, IteratorT>::CallStackIterator::operator*() { |
| assert(Iter != N->StackIdIndices.end()); |
| return *Iter; |
| } |
| |
| template <class NodeT, class IteratorT> |
| typename CallStack<NodeT, IteratorT>::CallStackIterator |
| CallStack<NodeT, IteratorT>::begin() const { |
| return CallStackIterator(N, /*End*/ false); |
| } |
| |
| template <class NodeT, class IteratorT> |
| typename CallStack<NodeT, IteratorT>::CallStackIterator |
| CallStack<NodeT, IteratorT>::beginAfterSharedPrefix(CallStack &Other) { |
| CallStackIterator Cur = begin(); |
| for (CallStackIterator OtherCur = Other.begin(); |
| Cur != end() && OtherCur != Other.end(); ++Cur, ++OtherCur) |
| assert(*Cur == *OtherCur); |
| return Cur; |
| } |
| |
| /// Specializations for iterating through IR metadata stack contexts. |
| template <> |
| CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::CallStackIterator( |
| const MDNode *N, bool End); |
| template <> |
| uint64_t CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::operator*(); |
| |
| } // end namespace memprof |
| } // end namespace llvm |
| |
| #endif |