1 | //===- Transforms/IPO/SampleContextTracker.h --------------------*- 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 | /// \file |
10 | /// This file provides the interface for context-sensitive profile tracker used |
11 | /// by CSSPGO. |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #ifndef LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H |
16 | #define LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H |
17 | |
18 | #include "llvm/ADT/StringRef.h" |
19 | #include "llvm/ADT/iterator.h" |
20 | #include "llvm/ProfileData/SampleProf.h" |
21 | #include <map> |
22 | #include <queue> |
23 | #include <vector> |
24 | |
25 | namespace llvm { |
26 | class CallBase; |
27 | class DILocation; |
28 | class Function; |
29 | class Instruction; |
30 | |
31 | // Internal trie tree representation used for tracking context tree and sample |
32 | // profiles. The path from root node to a given node represents the context of |
33 | // that nodes' profile. |
34 | class ContextTrieNode { |
35 | public: |
36 | ContextTrieNode(ContextTrieNode *Parent = nullptr, |
37 | FunctionId FName = FunctionId(), |
38 | FunctionSamples *FSamples = nullptr, |
39 | LineLocation CallLoc = {0, 0}) |
40 | : ParentContext(Parent), FuncName(FName), FuncSamples(FSamples), |
41 | CallSiteLoc(CallLoc){}; |
42 | ContextTrieNode *getChildContext(const LineLocation &CallSite, |
43 | FunctionId ChildName); |
44 | ContextTrieNode *getHottestChildContext(const LineLocation &CallSite); |
45 | ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite, |
46 | FunctionId ChildName, |
47 | bool AllowCreate = true); |
48 | void removeChildContext(const LineLocation &CallSite, FunctionId ChildName); |
49 | std::map<uint64_t, ContextTrieNode> &getAllChildContext(); |
50 | FunctionId getFuncName() const; |
51 | FunctionSamples *getFunctionSamples() const; |
52 | void setFunctionSamples(FunctionSamples *FSamples); |
53 | std::optional<uint32_t> getFunctionSize() const; |
54 | void addFunctionSize(uint32_t FSize); |
55 | LineLocation getCallSiteLoc() const; |
56 | ContextTrieNode *getParentContext() const; |
57 | void setParentContext(ContextTrieNode *Parent); |
58 | void setCallSiteLoc(const LineLocation &Loc); |
59 | void dumpNode(); |
60 | void dumpTree(); |
61 | |
62 | private: |
63 | // Map line+discriminator location to child context |
64 | std::map<uint64_t, ContextTrieNode> AllChildContext; |
65 | |
66 | // Link to parent context node |
67 | ContextTrieNode *ParentContext; |
68 | |
69 | // Function name for current context |
70 | FunctionId FuncName; |
71 | |
72 | // Function Samples for current context |
73 | FunctionSamples *FuncSamples; |
74 | |
75 | // Function size for current context |
76 | std::optional<uint32_t> FuncSize; |
77 | |
78 | // Callsite location in parent context |
79 | LineLocation CallSiteLoc; |
80 | }; |
81 | |
82 | // Profile tracker that manages profiles and its associated context. It |
83 | // provides interfaces used by sample profile loader to query context profile or |
84 | // base profile for given function or location; it also manages context tree |
85 | // manipulation that is needed to accommodate inline decisions so we have |
86 | // accurate post-inline profile for functions. Internally context profiles |
87 | // are organized in a trie, with each node representing profile for specific |
88 | // calling context and the context is identified by path from root to the node. |
89 | class SampleContextTracker { |
90 | public: |
91 | using ContextSamplesTy = std::vector<FunctionSamples *>; |
92 | |
93 | SampleContextTracker() = default; |
94 | SampleContextTracker(SampleProfileMap &Profiles, |
95 | const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap); |
96 | // Populate the FuncToCtxtProfiles map after the trie is built. |
97 | void populateFuncToCtxtMap(); |
98 | // Query context profile for a specific callee with given name at a given |
99 | // call-site. The full context is identified by location of call instruction. |
100 | FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst, |
101 | StringRef CalleeName); |
102 | // Get samples for indirect call targets for call site at given location. |
103 | std::vector<const FunctionSamples *> |
104 | getIndirectCalleeContextSamplesFor(const DILocation *DIL); |
105 | // Query context profile for a given location. The full context |
106 | // is identified by input DILocation. |
107 | FunctionSamples *getContextSamplesFor(const DILocation *DIL); |
108 | // Query context profile for a given sample contxt of a function. |
109 | FunctionSamples *getContextSamplesFor(const SampleContext &Context); |
110 | // Get all context profile for given function. |
111 | ContextSamplesTy &getAllContextSamplesFor(const Function &Func); |
112 | ContextSamplesTy &getAllContextSamplesFor(StringRef Name); |
113 | ContextTrieNode *getOrCreateContextPath(const SampleContext &Context, |
114 | bool AllowCreate); |
115 | // Query base profile for a given function. A base profile is a merged view |
116 | // of all context profiles for contexts that are not inlined. |
117 | FunctionSamples *getBaseSamplesFor(const Function &Func, |
118 | bool MergeContext = true); |
119 | // Query base profile for a given function by name. |
120 | FunctionSamples *getBaseSamplesFor(FunctionId Name, |
121 | bool MergeContext = true); |
122 | // Retrieve the context trie node for given profile context |
123 | ContextTrieNode *getContextFor(const SampleContext &Context); |
124 | // Get real function name for a given trie node. |
125 | StringRef getFuncNameFor(ContextTrieNode *Node) const; |
126 | // Mark a context profile as inlined when function is inlined. |
127 | // This makes sure that inlined context profile will be excluded in |
128 | // function's base profile. |
129 | void markContextSamplesInlined(const FunctionSamples *InlinedSamples); |
130 | ContextTrieNode &getRootContext(); |
131 | void promoteMergeContextSamplesTree(const Instruction &Inst, |
132 | FunctionId CalleeName); |
133 | |
134 | // Create a merged conext-less profile map. |
135 | void createContextLessProfileMap(SampleProfileMap &ContextLessProfiles); |
136 | ContextTrieNode * |
137 | getContextNodeForProfile(const FunctionSamples *FSamples) const { |
138 | auto I = ProfileToNodeMap.find(x: FSamples); |
139 | if (I == ProfileToNodeMap.end()) |
140 | return nullptr; |
141 | return I->second; |
142 | } |
143 | HashKeyMap<std::unordered_map, FunctionId, ContextSamplesTy> |
144 | &getFuncToCtxtProfiles() { |
145 | return FuncToCtxtProfiles; |
146 | } |
147 | |
148 | class Iterator : public llvm::iterator_facade_base< |
149 | Iterator, std::forward_iterator_tag, ContextTrieNode *, |
150 | std::ptrdiff_t, ContextTrieNode **, ContextTrieNode *> { |
151 | std::queue<ContextTrieNode *> NodeQueue; |
152 | |
153 | public: |
154 | explicit Iterator() = default; |
155 | explicit Iterator(ContextTrieNode *Node) { NodeQueue.push(x: Node); } |
156 | Iterator &operator++() { |
157 | assert(!NodeQueue.empty() && "Iterator already at the end" ); |
158 | ContextTrieNode *Node = NodeQueue.front(); |
159 | NodeQueue.pop(); |
160 | for (auto &It : Node->getAllChildContext()) |
161 | NodeQueue.push(x: &It.second); |
162 | return *this; |
163 | } |
164 | |
165 | bool operator==(const Iterator &Other) const { |
166 | if (NodeQueue.empty() && Other.NodeQueue.empty()) |
167 | return true; |
168 | if (NodeQueue.empty() || Other.NodeQueue.empty()) |
169 | return false; |
170 | return NodeQueue.front() == Other.NodeQueue.front(); |
171 | } |
172 | |
173 | ContextTrieNode *operator*() const { |
174 | assert(!NodeQueue.empty() && "Invalid access to end iterator" ); |
175 | return NodeQueue.front(); |
176 | } |
177 | }; |
178 | |
179 | Iterator begin() { return Iterator(&RootContext); } |
180 | Iterator end() { return Iterator(); } |
181 | |
182 | #ifndef NDEBUG |
183 | // Get a context string from root to current node. |
184 | std::string getContextString(const FunctionSamples &FSamples) const; |
185 | std::string getContextString(ContextTrieNode *Node) const; |
186 | #endif |
187 | // Dump the internal context profile trie. |
188 | void dump(); |
189 | |
190 | private: |
191 | ContextTrieNode *getContextFor(const DILocation *DIL); |
192 | ContextTrieNode *getCalleeContextFor(const DILocation *DIL, |
193 | FunctionId CalleeName); |
194 | ContextTrieNode *getTopLevelContextNode(FunctionId FName); |
195 | ContextTrieNode &addTopLevelContextNode(FunctionId FName); |
196 | ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo); |
197 | void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode); |
198 | ContextTrieNode & |
199 | promoteMergeContextSamplesTree(ContextTrieNode &FromNode, |
200 | ContextTrieNode &ToNodeParent); |
201 | ContextTrieNode &moveContextSamples(ContextTrieNode &ToNodeParent, |
202 | const LineLocation &CallSite, |
203 | ContextTrieNode &&NodeToMove); |
204 | void setContextNode(const FunctionSamples *FSample, ContextTrieNode *Node) { |
205 | ProfileToNodeMap[FSample] = Node; |
206 | } |
207 | // Map from function name to context profiles (excluding base profile) |
208 | HashKeyMap<std::unordered_map, FunctionId, ContextSamplesTy> |
209 | FuncToCtxtProfiles; |
210 | |
211 | // Map from current FunctionSample to the belonged context trie. |
212 | std::unordered_map<const FunctionSamples *, ContextTrieNode *> |
213 | ProfileToNodeMap; |
214 | |
215 | // Map from function guid to real function names. Only used in md5 mode. |
216 | const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap; |
217 | |
218 | // Root node for context trie tree |
219 | ContextTrieNode RootContext; |
220 | }; |
221 | |
222 | } // end namespace llvm |
223 | #endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H |
224 | |