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
25namespace llvm {
26class CallBase;
27class DILocation;
28class Function;
29class 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.
34class ContextTrieNode {
35public:
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
62private:
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.
89class SampleContextTracker {
90public:
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
190private:
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

source code of llvm/include/llvm/Transforms/IPO/SampleContextTracker.h