llvm/Analysis/MemoryProfileInfo.h

0001 //===- llvm/Analysis/MemoryProfileInfo.h - memory profile info ---*- C++ -*-==//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file contains utilities to analyze memory profile information.
0010 //
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_ANALYSIS_MEMORYPROFILEINFO_H
0014 #define LLVM_ANALYSIS_MEMORYPROFILEINFO_H
0015
0016 #include "llvm/IR/Metadata.h"
0017 #include "llvm/IR/ModuleSummaryIndex.h"
0018 #include <map>
0019
0020 namespace llvm {
0021 namespace memprof {
0022
0023 /// Return the allocation type for a given set of memory profile values.
0024 AllocationType getAllocType(uint64_t TotalLifetimeAccessDensity,
0025                             uint64_t AllocCount, uint64_t TotalLifetime);
0026
0027 /// Build callstack metadata from the provided list of call stack ids. Returns
0028 /// the resulting metadata node.
0029 MDNode *buildCallstackMetadata(ArrayRef<uint64_t> CallStack, LLVMContext &Ctx);
0030
0031 /// Build metadata from the provided list of full stack id and profiled size, to
0032 /// use when reporting of hinted sizes is enabled.
0033 MDNode *buildContextSizeMetadata(ArrayRef<ContextTotalSize> ContextSizeInfo,
0034                                  LLVMContext &Ctx);
0035
0036 /// Returns the stack node from an MIB metadata node.
0037 MDNode *getMIBStackNode(const MDNode *MIB);
0038
0039 /// Returns the allocation type from an MIB metadata node.
0040 AllocationType getMIBAllocType(const MDNode *MIB);
0041
0042 /// Returns the string to use in attributes with the given type.
0043 std::string getAllocTypeAttributeString(AllocationType Type);
0044
0045 /// True if the AllocTypes bitmask contains just a single type.
0046 bool hasSingleAllocType(uint8_t AllocTypes);
0047
0048 /// Class to build a trie of call stack contexts for a particular profiled
0049 /// allocation call, along with their associated allocation types.
0050 /// The allocation will be at the root of the trie, which is then used to
0051 /// compute the minimum lists of context ids needed to associate a call context
0052 /// with a single allocation type.
0053 class CallStackTrie {
0054 private:
0055   struct CallStackTrieNode {
0056     // Allocation types for call context sharing the context prefix at this
0057     // node.
0058     uint8_t AllocTypes;
0059     // If the user has requested reporting of hinted sizes, keep track of the
0060     // associated full stack id and profiled sizes. Can have more than one
0061     // after trimming (e.g. when building from metadata). This is only placed on
0062     // the last (root-most) trie node for each allocation context.
0063     std::vector<ContextTotalSize> ContextSizeInfo;
0064     // Map of caller stack id to the corresponding child Trie node.
0065     std::map<uint64_t, CallStackTrieNode *> Callers;
0066     CallStackTrieNode(AllocationType Type)
0067         : AllocTypes(static_cast<uint8_t>(Type)) {}
0068     void addAllocType(AllocationType AllocType) {
0069       AllocTypes |= static_cast<uint8_t>(AllocType);
0070     }
0071     void removeAllocType(AllocationType AllocType) {
0072       AllocTypes &= ~static_cast<uint8_t>(AllocType);
0073     }
0074     bool hasAllocType(AllocationType AllocType) const {
0075       return AllocTypes & static_cast<uint8_t>(AllocType);
0076     }
0077   };
0078
0079   // The node for the allocation at the root.
0080   CallStackTrieNode *Alloc = nullptr;
0081   // The allocation's leaf stack id.
0082   uint64_t AllocStackId = 0;
0083
0084   void deleteTrieNode(CallStackTrieNode *Node) {
0085     if (!Node)
0086       return;
0087     for (auto C : Node->Callers)
0088       deleteTrieNode(C.second);
0089     delete Node;
0090   }
0091
0092   // Recursively build up a complete list of context size information from the
0093   // trie nodes reached form the given Node, for hint size reporting.
0094   void collectContextSizeInfo(CallStackTrieNode *Node,
0095                               std::vector<ContextTotalSize> &ContextSizeInfo);
0096
0097   // Recursively convert hot allocation types to notcold, since we don't
0098   // actually do any cloning for hot contexts, to facilitate more aggressive
0099   // pruning of contexts.
0100   void convertHotToNotCold(CallStackTrieNode *Node);
0101
0102   // Recursive helper to trim contexts and create metadata nodes.
0103   bool buildMIBNodes(CallStackTrieNode *Node, LLVMContext &Ctx,
0104                      std::vector<uint64_t> &MIBCallStack,
0105                      std::vector<Metadata *> &MIBNodes,
0106                      bool CalleeHasAmbiguousCallerContext);
0107
0108 public:
0109   CallStackTrie() = default;
0110   ~CallStackTrie() { deleteTrieNode(Alloc); }
0111
0112   bool empty() const { return Alloc == nullptr; }
0113
0114   /// Add a call stack context with the given allocation type to the Trie.
0115   /// The context is represented by the list of stack ids (computed during
0116   /// matching via a debug location hash), expected to be in order from the
0117   /// allocation call down to the bottom of the call stack (i.e. callee to
0118   /// caller order).
0119   void addCallStack(AllocationType AllocType, ArrayRef<uint64_t> StackIds,
0120                     std::vector<ContextTotalSize> ContextSizeInfo = {});
0121
0122   /// Add the call stack context along with its allocation type from the MIB
0123   /// metadata to the Trie.
0124   void addCallStack(MDNode *MIB);
0125
0126   /// Build and attach the minimal necessary MIB metadata. If the alloc has a
0127   /// single allocation type, add a function attribute instead. The reason for
0128   /// adding an attribute in this case is that it matches how the behavior for
0129   /// allocation calls will be communicated to lib call simplification after
0130   /// cloning or another optimization to distinguish the allocation types,
0131   /// which is lower overhead and more direct than maintaining this metadata.
0132   /// Returns true if memprof metadata attached, false if not (attribute added).
0133   bool buildAndAttachMIBMetadata(CallBase *CI);
0134
0135   /// Add an attribute for the given allocation type to the call instruction.
0136   /// If hinted by reporting is enabled, a message is emitted with the given
0137   /// descriptor used to identify the category of single allocation type.
0138   void addSingleAllocTypeAttribute(CallBase *CI, AllocationType AT,
0139                                    StringRef Descriptor);
0140 };
0141
0142 /// Helper class to iterate through stack ids in both metadata (memprof MIB and
0143 /// callsite) and the corresponding ThinLTO summary data structures
0144 /// (CallsiteInfo and MIBInfo). This simplifies implementation of client code
0145 /// which doesn't need to worry about whether we are operating with IR (Regular
0146 /// LTO), or summary (ThinLTO).
0147 template <class NodeT, class IteratorT> class CallStack {
0148 public:
0149   CallStack(const NodeT *N = nullptr) : N(N) {}
0150
0151   // Implement minimum required methods for range-based for loop.
0152   // The default implementation assumes we are operating on ThinLTO data
0153   // structures, which have a vector of StackIdIndices. There are specialized
0154   // versions provided to iterate through metadata.
0155   struct CallStackIterator {
0156     const NodeT *N = nullptr;
0157     IteratorT Iter;
0158     CallStackIterator(const NodeT *N, bool End);
0159     uint64_t operator*();
0160     bool operator==(const CallStackIterator &rhs) { return Iter == rhs.Iter; }
0161     bool operator!=(const CallStackIterator &rhs) { return !(*this == rhs); }
0162     void operator++() { ++Iter; }
0163   };
0164
0165   bool empty() const { return N == nullptr; }
0166
0167   CallStackIterator begin() const;
0168   CallStackIterator end() const { return CallStackIterator(N, /*End*/ true); }
0169   CallStackIterator beginAfterSharedPrefix(CallStack &Other);
0170   uint64_t back() const;
0171
0172 private:
0173   const NodeT *N = nullptr;
0174 };
0175
0176 template <class NodeT, class IteratorT>
0177 CallStack<NodeT, IteratorT>::CallStackIterator::CallStackIterator(
0178     const NodeT *N, bool End)
0179     : N(N) {
0180   if (!N) {
0181     Iter = nullptr;
0182     return;
0183   }
0184   Iter = End ? N->StackIdIndices.end() : N->StackIdIndices.begin();
0185 }
0186
0187 template <class NodeT, class IteratorT>
0188 uint64_t CallStack<NodeT, IteratorT>::CallStackIterator::operator*() {
0189   assert(Iter != N->StackIdIndices.end());
0190   return *Iter;
0191 }
0192
0193 template <class NodeT, class IteratorT>
0194 uint64_t CallStack<NodeT, IteratorT>::back() const {
0195   assert(N);
0196   return N->StackIdIndices.back();
0197 }
0198
0199 template <class NodeT, class IteratorT>
0200 typename CallStack<NodeT, IteratorT>::CallStackIterator
0201 CallStack<NodeT, IteratorT>::begin() const {
0202   return CallStackIterator(N, /*End*/ false);
0203 }
0204
0205 template <class NodeT, class IteratorT>
0206 typename CallStack<NodeT, IteratorT>::CallStackIterator
0207 CallStack<NodeT, IteratorT>::beginAfterSharedPrefix(CallStack &Other) {
0208   CallStackIterator Cur = begin();
0209   for (CallStackIterator OtherCur = Other.begin();
0210        Cur != end() && OtherCur != Other.end(); ++Cur, ++OtherCur)
0211     assert(*Cur == *OtherCur);
0212   return Cur;
0213 }
0214
0215 /// Specializations for iterating through IR metadata stack contexts.
0216 template <>
0217 CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::CallStackIterator(
0218     const MDNode *N, bool End);
0219 template <>
0220 uint64_t CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::operator*();
0221 template <> uint64_t CallStack<MDNode, MDNode::op_iterator>::back() const;
0222
0223 } // end namespace memprof
0224 } // end namespace llvm
0225
0226 #endif