1 //===- llvm/Analysis/MemoryProfileInfo.h - memory profile info ---*- C++ -*-==// 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 13 #ifndef LLVM_ANALYSIS_MEMORYPROFILEINFO_H 14 #define LLVM_ANALYSIS_MEMORYPROFILEINFO_H 15 16 #include "llvm/IR/Constants.h" 17 #include "llvm/IR/InstrTypes.h" 18 #include "llvm/IR/Metadata.h" 19 #include "llvm/IR/Module.h" 20 #include "llvm/IR/ModuleSummaryIndex.h" 21 #include <map> 22 23 namespace llvm { 24 namespace memprof { 25 26 /// Return the allocation type for a given set of memory profile values. 27 AllocationType getAllocType(uint64_t TotalLifetimeAccessDensity, 28 uint64_t AllocCount, uint64_t TotalLifetime); 29 30 /// Build callstack metadata from the provided list of call stack ids. Returns 31 /// the resulting metadata node. 32 MDNode *buildCallstackMetadata(ArrayRef<uint64_t> CallStack, LLVMContext &Ctx); 33 34 /// Returns the stack node from an MIB metadata node. 35 MDNode *getMIBStackNode(const MDNode *MIB); 36 37 /// Returns the allocation type from an MIB metadata node. 38 AllocationType getMIBAllocType(const MDNode *MIB); 39 40 /// Returns the total size from an MIB metadata node, or 0 if it was not 41 /// recorded. 42 uint64_t getMIBTotalSize(const MDNode *MIB); 43 44 /// Returns the string to use in attributes with the given type. 45 std::string getAllocTypeAttributeString(AllocationType Type); 46 47 /// True if the AllocTypes bitmask contains just a single type. 48 bool hasSingleAllocType(uint8_t AllocTypes); 49 50 /// Class to build a trie of call stack contexts for a particular profiled 51 /// allocation call, along with their associated allocation types. 52 /// The allocation will be at the root of the trie, which is then used to 53 /// compute the minimum lists of context ids needed to associate a call context 54 /// with a single allocation type. 55 class CallStackTrie { 56 private: 57 struct CallStackTrieNode { 58 // Allocation types for call context sharing the context prefix at this 59 // node. 60 uint8_t AllocTypes; 61 uint64_t TotalSize; 62 // Map of caller stack id to the corresponding child Trie node. 63 std::map<uint64_t, CallStackTrieNode *> Callers; 64 CallStackTrieNode(AllocationType Type, uint64_t TotalSize) 65 : AllocTypes(static_cast<uint8_t>(Type)), TotalSize(TotalSize) {} 66 }; 67 68 // The node for the allocation at the root. 69 CallStackTrieNode *Alloc = nullptr; 70 // The allocation's leaf stack id. 71 uint64_t AllocStackId = 0; 72 73 void deleteTrieNode(CallStackTrieNode *Node) { 74 if (!Node) 75 return; 76 for (auto C : Node->Callers) 77 deleteTrieNode(C.second); 78 delete Node; 79 } 80 81 // Recursive helper to trim contexts and create metadata nodes. 82 bool buildMIBNodes(CallStackTrieNode *Node, LLVMContext &Ctx, 83 std::vector<uint64_t> &MIBCallStack, 84 std::vector<Metadata *> &MIBNodes, 85 bool CalleeHasAmbiguousCallerContext); 86 87 public: 88 CallStackTrie() = default; 89 ~CallStackTrie() { deleteTrieNode(Alloc); } 90 91 bool empty() const { return Alloc == nullptr; } 92 93 /// Add a call stack context with the given allocation type to the Trie. 94 /// The context is represented by the list of stack ids (computed during 95 /// matching via a debug location hash), expected to be in order from the 96 /// allocation call down to the bottom of the call stack (i.e. callee to 97 /// caller order). 98 void addCallStack(AllocationType AllocType, ArrayRef<uint64_t> StackIds, 99 uint64_t TotalSize = 0); 100 101 /// Add the call stack context along with its allocation type from the MIB 102 /// metadata to the Trie. 103 void addCallStack(MDNode *MIB); 104 105 /// Build and attach the minimal necessary MIB metadata. If the alloc has a 106 /// single allocation type, add a function attribute instead. The reason for 107 /// adding an attribute in this case is that it matches how the behavior for 108 /// allocation calls will be communicated to lib call simplification after 109 /// cloning or another optimization to distinguish the allocation types, 110 /// which is lower overhead and more direct than maintaining this metadata. 111 /// Returns true if memprof metadata attached, false if not (attribute added). 112 bool buildAndAttachMIBMetadata(CallBase *CI); 113 }; 114 115 /// Helper class to iterate through stack ids in both metadata (memprof MIB and 116 /// callsite) and the corresponding ThinLTO summary data structures 117 /// (CallsiteInfo and MIBInfo). This simplifies implementation of client code 118 /// which doesn't need to worry about whether we are operating with IR (Regular 119 /// LTO), or summary (ThinLTO). 120 template <class NodeT, class IteratorT> class CallStack { 121 public: 122 CallStack(const NodeT *N = nullptr) : N(N) {} 123 124 // Implement minimum required methods for range-based for loop. 125 // The default implementation assumes we are operating on ThinLTO data 126 // structures, which have a vector of StackIdIndices. There are specialized 127 // versions provided to iterate through metadata. 128 struct CallStackIterator { 129 const NodeT *N = nullptr; 130 IteratorT Iter; 131 CallStackIterator(const NodeT *N, bool End); 132 uint64_t operator*(); 133 bool operator==(const CallStackIterator &rhs) { return Iter == rhs.Iter; } 134 bool operator!=(const CallStackIterator &rhs) { return !(*this == rhs); } 135 void operator++() { ++Iter; } 136 }; 137 138 bool empty() const { return N == nullptr; } 139 140 CallStackIterator begin() const; 141 CallStackIterator end() const { return CallStackIterator(N, /*End*/ true); } 142 CallStackIterator beginAfterSharedPrefix(CallStack &Other); 143 uint64_t back() const; 144 145 private: 146 const NodeT *N = nullptr; 147 }; 148 149 template <class NodeT, class IteratorT> 150 CallStack<NodeT, IteratorT>::CallStackIterator::CallStackIterator( 151 const NodeT *N, bool End) 152 : N(N) { 153 if (!N) { 154 Iter = nullptr; 155 return; 156 } 157 Iter = End ? N->StackIdIndices.end() : N->StackIdIndices.begin(); 158 } 159 160 template <class NodeT, class IteratorT> 161 uint64_t CallStack<NodeT, IteratorT>::CallStackIterator::operator*() { 162 assert(Iter != N->StackIdIndices.end()); 163 return *Iter; 164 } 165 166 template <class NodeT, class IteratorT> 167 uint64_t CallStack<NodeT, IteratorT>::back() const { 168 assert(N); 169 return N->StackIdIndices.back(); 170 } 171 172 template <class NodeT, class IteratorT> 173 typename CallStack<NodeT, IteratorT>::CallStackIterator 174 CallStack<NodeT, IteratorT>::begin() const { 175 return CallStackIterator(N, /*End*/ false); 176 } 177 178 template <class NodeT, class IteratorT> 179 typename CallStack<NodeT, IteratorT>::CallStackIterator 180 CallStack<NodeT, IteratorT>::beginAfterSharedPrefix(CallStack &Other) { 181 CallStackIterator Cur = begin(); 182 for (CallStackIterator OtherCur = Other.begin(); 183 Cur != end() && OtherCur != Other.end(); ++Cur, ++OtherCur) 184 assert(*Cur == *OtherCur); 185 return Cur; 186 } 187 188 /// Specializations for iterating through IR metadata stack contexts. 189 template <> 190 CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::CallStackIterator( 191 const MDNode *N, bool End); 192 template <> 193 uint64_t CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::operator*(); 194 template <> uint64_t CallStack<MDNode, MDNode::op_iterator>::back() const; 195 196 } // end namespace memprof 197 } // end namespace llvm 198 199 #endif 200