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(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(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