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;
CallStackTrieNodeCallStackTrieNode64 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
deleteTrieNode(CallStackTrieNode * Node)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;
~CallStackTrie()89 ~CallStackTrie() { deleteTrieNode(Alloc); }
90
empty()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:
N(N)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
empty()138 bool empty() const { return N == nullptr; }
139
140 CallStackIterator begin() const;
end()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>
CallStackIterator(const NodeT * N,bool End)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>
back()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
begin()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
beginAfterSharedPrefix(CallStack & Other)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