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/Metadata.h"
17 #include "llvm/IR/ModuleSummaryIndex.h"
18 #include "llvm/Support/Compiler.h"
19 #include <map>
20
21 namespace llvm {
22
23 class OptimizationRemarkEmitter;
24
25 namespace memprof {
26
27 /// Whether the alloc memeprof metadata will include context size info for all
28 /// MIBs.
29 LLVM_ABI bool metadataIncludesAllContextSizeInfo();
30
31 /// Whether the alloc memprof metadata may include context size info for some
32 /// MIBs (but possibly not all).
33 LLVM_ABI bool metadataMayIncludeContextSizeInfo();
34
35 /// Whether we need to record the context size info in the alloc trie used to
36 /// build metadata.
37 LLVM_ABI bool recordContextSizeInfoForAnalysis();
38
39 /// Build callstack metadata from the provided list of call stack ids. Returns
40 /// the resulting metadata node.
41 LLVM_ABI MDNode *buildCallstackMetadata(ArrayRef<uint64_t> CallStack,
42 LLVMContext &Ctx);
43
44 /// Build metadata from the provided list of full stack id and profiled size, to
45 /// use when reporting of hinted sizes is enabled.
46 LLVM_ABI MDNode *
47 buildContextSizeMetadata(ArrayRef<ContextTotalSize> ContextSizeInfo,
48 LLVMContext &Ctx);
49
50 /// Returns the stack node from an MIB metadata node.
51 LLVM_ABI MDNode *getMIBStackNode(const MDNode *MIB);
52
53 /// Returns the allocation type from an MIB metadata node.
54 LLVM_ABI AllocationType getMIBAllocType(const MDNode *MIB);
55
56 /// Returns the string to use in attributes with the given type.
57 LLVM_ABI std::string getAllocTypeAttributeString(AllocationType Type);
58
59 /// True if the AllocTypes bitmask contains just a single type.
60 LLVM_ABI bool hasSingleAllocType(uint8_t AllocTypes);
61
62 /// Class to build a trie of call stack contexts for a particular profiled
63 /// allocation call, along with their associated allocation types.
64 /// The allocation will be at the root of the trie, which is then used to
65 /// compute the minimum lists of context ids needed to associate a call context
66 /// with a single allocation type.
67 class CallStackTrie {
68 private:
69 struct CallStackTrieNode {
70 // Allocation types for call context sharing the context prefix at this
71 // node.
72 uint8_t AllocTypes;
73 // If the user has requested reporting of hinted sizes, keep track of the
74 // associated full stack id and profiled sizes. Can have more than one
75 // after trimming (e.g. when building from metadata). This is only placed on
76 // the last (root-most) trie node for each allocation context.
77 std::vector<ContextTotalSize> ContextSizeInfo;
78 // Map of caller stack id to the corresponding child Trie node.
79 std::map<uint64_t, CallStackTrieNode *> Callers;
CallStackTrieNodeCallStackTrieNode80 CallStackTrieNode(AllocationType Type)
81 : AllocTypes(static_cast<uint8_t>(Type)) {}
addAllocTypeCallStackTrieNode82 void addAllocType(AllocationType AllocType) {
83 AllocTypes |= static_cast<uint8_t>(AllocType);
84 }
removeAllocTypeCallStackTrieNode85 void removeAllocType(AllocationType AllocType) {
86 AllocTypes &= ~static_cast<uint8_t>(AllocType);
87 }
hasAllocTypeCallStackTrieNode88 bool hasAllocType(AllocationType AllocType) const {
89 return AllocTypes & static_cast<uint8_t>(AllocType);
90 }
91 };
92
93 // The node for the allocation at the root.
94 CallStackTrieNode *Alloc = nullptr;
95 // The allocation's leaf stack id.
96 uint64_t AllocStackId = 0;
97
98 // If the client provides a remarks emitter object, we will emit remarks on
99 // allocations for which we apply non-context sensitive allocation hints.
100 OptimizationRemarkEmitter *ORE;
101
102 // The maximum size of a cold allocation context, from the profile summary.
103 uint64_t MaxColdSize;
104
deleteTrieNode(CallStackTrieNode * Node)105 void deleteTrieNode(CallStackTrieNode *Node) {
106 if (!Node)
107 return;
108 for (auto C : Node->Callers)
109 deleteTrieNode(C.second);
110 delete Node;
111 }
112
113 // Recursively build up a complete list of context size information from the
114 // trie nodes reached form the given Node, for hint size reporting.
115 void collectContextSizeInfo(CallStackTrieNode *Node,
116 std::vector<ContextTotalSize> &ContextSizeInfo);
117
118 // Recursively convert hot allocation types to notcold, since we don't
119 // actually do any cloning for hot contexts, to facilitate more aggressive
120 // pruning of contexts.
121 void convertHotToNotCold(CallStackTrieNode *Node);
122
123 // Recursive helper to trim contexts and create metadata nodes.
124 bool buildMIBNodes(CallStackTrieNode *Node, LLVMContext &Ctx,
125 std::vector<uint64_t> &MIBCallStack,
126 std::vector<Metadata *> &MIBNodes,
127 bool CalleeHasAmbiguousCallerContext, uint64_t &TotalBytes,
128 uint64_t &ColdBytes);
129
130 public:
131 CallStackTrie(OptimizationRemarkEmitter *ORE = nullptr,
132 uint64_t MaxColdSize = 0)
ORE(ORE)133 : ORE(ORE), MaxColdSize(MaxColdSize) {}
~CallStackTrie()134 ~CallStackTrie() { deleteTrieNode(Alloc); }
135
empty()136 bool empty() const { return Alloc == nullptr; }
137
138 /// Add a call stack context with the given allocation type to the Trie.
139 /// The context is represented by the list of stack ids (computed during
140 /// matching via a debug location hash), expected to be in order from the
141 /// allocation call down to the bottom of the call stack (i.e. callee to
142 /// caller order).
143 LLVM_ABI void
144 addCallStack(AllocationType AllocType, ArrayRef<uint64_t> StackIds,
145 std::vector<ContextTotalSize> ContextSizeInfo = {});
146
147 /// Add the call stack context along with its allocation type from the MIB
148 /// metadata to the Trie.
149 LLVM_ABI void addCallStack(MDNode *MIB);
150
151 /// Build and attach the minimal necessary MIB metadata. If the alloc has a
152 /// single allocation type, add a function attribute instead. The reason for
153 /// adding an attribute in this case is that it matches how the behavior for
154 /// allocation calls will be communicated to lib call simplification after
155 /// cloning or another optimization to distinguish the allocation types,
156 /// which is lower overhead and more direct than maintaining this metadata.
157 /// Returns true if memprof metadata attached, false if not (attribute added).
158 LLVM_ABI bool buildAndAttachMIBMetadata(CallBase *CI);
159
160 /// Add an attribute for the given allocation type to the call instruction.
161 /// If hinted by reporting is enabled, a message is emitted with the given
162 /// descriptor used to identify the category of single allocation type.
163 LLVM_ABI void addSingleAllocTypeAttribute(CallBase *CI, AllocationType AT,
164 StringRef Descriptor);
165 };
166
167 /// Helper class to iterate through stack ids in both metadata (memprof MIB and
168 /// callsite) and the corresponding ThinLTO summary data structures
169 /// (CallsiteInfo and MIBInfo). This simplifies implementation of client code
170 /// which doesn't need to worry about whether we are operating with IR (Regular
171 /// LTO), or summary (ThinLTO).
172 template <class NodeT, class IteratorT> class CallStack {
173 public:
N(N)174 CallStack(const NodeT *N = nullptr) : N(N) {}
175
176 // Implement minimum required methods for range-based for loop.
177 // The default implementation assumes we are operating on ThinLTO data
178 // structures, which have a vector of StackIdIndices. There are specialized
179 // versions provided to iterate through metadata.
180 struct CallStackIterator {
181 const NodeT *N = nullptr;
182 IteratorT Iter;
183 CallStackIterator(const NodeT *N, bool End);
184 uint64_t operator*();
185 bool operator==(const CallStackIterator &rhs) { return Iter == rhs.Iter; }
186 bool operator!=(const CallStackIterator &rhs) { return !(*this == rhs); }
187 void operator++() { ++Iter; }
188 };
189
empty()190 bool empty() const { return N == nullptr; }
191
192 CallStackIterator begin() const;
end()193 CallStackIterator end() const { return CallStackIterator(N, /*End*/ true); }
194 CallStackIterator beginAfterSharedPrefix(const CallStack &Other);
195 uint64_t back() const;
196
197 private:
198 const NodeT *N = nullptr;
199 };
200
201 template <class NodeT, class IteratorT>
CallStackIterator(const NodeT * N,bool End)202 CallStack<NodeT, IteratorT>::CallStackIterator::CallStackIterator(
203 const NodeT *N, bool End)
204 : N(N) {
205 if (!N) {
206 Iter = nullptr;
207 return;
208 }
209 Iter = End ? N->StackIdIndices.end() : N->StackIdIndices.begin();
210 }
211
212 template <class NodeT, class IteratorT>
213 uint64_t CallStack<NodeT, IteratorT>::CallStackIterator::operator*() {
214 assert(Iter != N->StackIdIndices.end());
215 return *Iter;
216 }
217
218 template <class NodeT, class IteratorT>
back()219 uint64_t CallStack<NodeT, IteratorT>::back() const {
220 assert(N);
221 return N->StackIdIndices.back();
222 }
223
224 template <class NodeT, class IteratorT>
225 typename CallStack<NodeT, IteratorT>::CallStackIterator
begin()226 CallStack<NodeT, IteratorT>::begin() const {
227 return CallStackIterator(N, /*End*/ false);
228 }
229
230 template <class NodeT, class IteratorT>
231 typename CallStack<NodeT, IteratorT>::CallStackIterator
beginAfterSharedPrefix(const CallStack & Other)232 CallStack<NodeT, IteratorT>::beginAfterSharedPrefix(const CallStack &Other) {
233 CallStackIterator Cur = begin();
234 for (CallStackIterator OtherCur = Other.begin();
235 Cur != end() && OtherCur != Other.end(); ++Cur, ++OtherCur)
236 assert(*Cur == *OtherCur);
237 return Cur;
238 }
239
240 /// Specializations for iterating through IR metadata stack contexts.
241 template <>
242 LLVM_ABI
243 CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::CallStackIterator(
244 const MDNode *N, bool End);
245 template <>
246 LLVM_ABI uint64_t
247 CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::operator*();
248 template <>
249 LLVM_ABI uint64_t CallStack<MDNode, MDNode::op_iterator>::back() const;
250
251 } // end namespace memprof
252 } // end namespace llvm
253
254 #endif
255