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
23namespace llvm {
24namespace memprof {
25
26/// Return the allocation type for a given set of memory profile values.
27AllocationType 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.
32MDNode *buildCallstackMetadata(ArrayRef<uint64_t> CallStack, LLVMContext &Ctx);
33
34/// Returns the stack node from an MIB metadata node.
35MDNode *getMIBStackNode(const MDNode *MIB);
36
37/// Returns the allocation type from an MIB metadata node.
38AllocationType getMIBAllocType(const MDNode *MIB);
39
40/// Returns the string to use in attributes with the given type.
41std::string getAllocTypeAttributeString(AllocationType Type);
42
43/// True if the AllocTypes bitmask contains just a single type.
44bool 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.
51class CallStackTrie {
52private:
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
82public:
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).
114template <class NodeT, class IteratorT> class CallStack {
115public:
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
139private:
140 const NodeT *N = nullptr;
141};
142
143template <class NodeT, class IteratorT>
144CallStack<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
154template <class NodeT, class IteratorT>
155uint64_t CallStack<NodeT, IteratorT>::CallStackIterator::operator*() {
156 assert(Iter != N->StackIdIndices.end());
157 return *Iter;
158}
159
160template <class NodeT, class IteratorT>
161uint64_t CallStack<NodeT, IteratorT>::back() const {
162 assert(N);
163 return N->StackIdIndices.back();
164}
165
166template <class NodeT, class IteratorT>
167typename CallStack<NodeT, IteratorT>::CallStackIterator
168CallStack<NodeT, IteratorT>::begin() const {
169 return CallStackIterator(N, /*End*/ false);
170}
171
172template <class NodeT, class IteratorT>
173typename CallStack<NodeT, IteratorT>::CallStackIterator
174CallStack<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.
183template <>
184CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::CallStackIterator(
185 const MDNode *N, bool End);
186template <>
187uint64_t CallStack<MDNode, MDNode::op_iterator>::CallStackIterator::operator*();
188template <> uint64_t CallStack<MDNode, MDNode::op_iterator>::back() const;
189
190} // end namespace memprof
191} // end namespace llvm
192
193#endif
194

source code of llvm/include/llvm/Analysis/MemoryProfileInfo.h