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