LLVM 17.0.0git
SampleContextTracker.h
Go to the documentation of this file.
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/StringMap.h"
19#include "llvm/ADT/StringRef.h"
20#include "llvm/ADT/iterator.h"
22#include <map>
23#include <queue>
24#include <vector>
25
26namespace llvm {
27class CallBase;
28class DILocation;
29class Function;
30class Instruction;
31
32// Internal trie tree representation used for tracking context tree and sample
33// profiles. The path from root node to a given node represents the context of
34// that nodes' profile.
36public:
38 StringRef FName = StringRef(),
39 FunctionSamples *FSamples = nullptr,
40 LineLocation CallLoc = {0, 0})
41 : ParentContext(Parent), FuncName(FName), FuncSamples(FSamples),
42 CallSiteLoc(CallLoc){};
43 ContextTrieNode *getChildContext(const LineLocation &CallSite,
44 StringRef ChildName);
45 ContextTrieNode *getHottestChildContext(const LineLocation &CallSite);
46 ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite,
47 StringRef ChildName,
48 bool AllowCreate = true);
49 void removeChildContext(const LineLocation &CallSite, StringRef ChildName);
50 std::map<uint64_t, ContextTrieNode> &getAllChildContext();
51 StringRef getFuncName() const;
52 FunctionSamples *getFunctionSamples() const;
53 void setFunctionSamples(FunctionSamples *FSamples);
54 std::optional<uint32_t> getFunctionSize() const;
55 void addFunctionSize(uint32_t FSize);
56 LineLocation getCallSiteLoc() const;
57 ContextTrieNode *getParentContext() const;
58 void setParentContext(ContextTrieNode *Parent);
59 void setCallSiteLoc(const LineLocation &Loc);
60 void dumpNode();
61 void dumpTree();
62
63private:
64 // Map line+discriminator location to child context
65 std::map<uint64_t, ContextTrieNode> AllChildContext;
66
67 // Link to parent context node
68 ContextTrieNode *ParentContext;
69
70 // Function name for current context
71 StringRef FuncName;
72
73 // Function Samples for current context
74 FunctionSamples *FuncSamples;
75
76 // Function size for current context
77 std::optional<uint32_t> FuncSize;
78
79 // Callsite location in parent context
80 LineLocation CallSiteLoc;
81};
82
83// Profile tracker that manages profiles and its associated context. It
84// provides interfaces used by sample profile loader to query context profile or
85// base profile for given function or location; it also manages context tree
86// manipulation that is needed to accommodate inline decisions so we have
87// accurate post-inline profile for functions. Internally context profiles
88// are organized in a trie, with each node representing profile for specific
89// calling context and the context is identified by path from root to the node.
91public:
92 using ContextSamplesTy = std::vector<FunctionSamples *>;
93
96 const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap);
97 // Populate the FuncToCtxtProfiles map after the trie is built.
99 // Query context profile for a specific callee with given name at a given
100 // call-site. The full context is identified by location of call instruction.
102 StringRef CalleeName);
103 // Get samples for indirect call targets for call site at given location.
104 std::vector<const FunctionSamples *>
106 // Query context profile for a given location. The full context
107 // is identified by input DILocation.
109 // Query context profile for a given sample contxt of a function.
111 // Get all context profile for given function.
115 bool AllowCreate);
116 // Query base profile for a given function. A base profile is a merged view
117 // of all context profiles for contexts that are not inlined.
119 bool MergeContext = true);
120 // Query base profile for a given function by name.
121 FunctionSamples *getBaseSamplesFor(StringRef Name, bool MergeContext = true);
122 // Retrieve the context trie node for given profile context
124 // Get real function name for a given trie node.
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);
132 StringRef CalleeName);
133
134 // Create a merged conext-less profile map.
135 void createContextLessProfileMap(SampleProfileMap &ContextLessProfiles);
138 auto I = ProfileToNodeMap.find(FSamples);
139 if (I == ProfileToNodeMap.end())
140 return nullptr;
141 return I->second;
142 }
144 return FuncToCtxtProfiles;
145 }
146
148 Iterator, std::forward_iterator_tag, ContextTrieNode *,
149 std::ptrdiff_t, ContextTrieNode **, ContextTrieNode *> {
150 std::queue<ContextTrieNode *> NodeQueue;
151
152 public:
153 explicit Iterator() = default;
154 explicit Iterator(ContextTrieNode *Node) { NodeQueue.push(Node); }
156 assert(!NodeQueue.empty() && "Iterator already at the end");
157 ContextTrieNode *Node = NodeQueue.front();
158 NodeQueue.pop();
159 for (auto &It : Node->getAllChildContext())
160 NodeQueue.push(&It.second);
161 return *this;
162 }
163
164 bool operator==(const Iterator &Other) const {
165 if (NodeQueue.empty() && Other.NodeQueue.empty())
166 return true;
167 if (NodeQueue.empty() || Other.NodeQueue.empty())
168 return false;
169 return NodeQueue.front() == Other.NodeQueue.front();
170 }
171
173 assert(!NodeQueue.empty() && "Invalid access to end iterator");
174 return NodeQueue.front();
175 }
176 };
177
178 Iterator begin() { return Iterator(&RootContext); }
179 Iterator end() { return Iterator(); }
180
181#ifndef NDEBUG
182 // Get a context string from root to current node.
183 std::string getContextString(const FunctionSamples &FSamples) const;
184 std::string getContextString(ContextTrieNode *Node) const;
185#endif
186 // Dump the internal context profile trie.
187 void dump();
188
189private:
191 ContextTrieNode *getCalleeContextFor(const DILocation *DIL,
192 StringRef CalleeName);
193 ContextTrieNode *getTopLevelContextNode(StringRef FName);
194 ContextTrieNode &addTopLevelContextNode(StringRef FName);
196 void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode);
199 ContextTrieNode &ToNodeParent);
200 ContextTrieNode &moveContextSamples(ContextTrieNode &ToNodeParent,
201 const LineLocation &CallSite,
202 ContextTrieNode &&NodeToMove);
203 void setContextNode(const FunctionSamples *FSample, ContextTrieNode *Node) {
204 ProfileToNodeMap[FSample] = Node;
205 }
206 // Map from function name to context profiles (excluding base profile)
207 StringMap<ContextSamplesTy> FuncToCtxtProfiles;
208
209 // Map from current FunctionSample to the belonged context trie.
210 std::unordered_map<const FunctionSamples *, ContextTrieNode *>
211 ProfileToNodeMap;
212
213 // Map from function guid to real function names. Only used in md5 mode.
214 const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap;
215
216 // Root node for context trie tree
217 ContextTrieNode RootContext;
218};
219
220} // end namespace llvm
221#endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
This file defines the StringMap class.
std::string Name
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1184
std::map< uint64_t, ContextTrieNode > & getAllChildContext()
ContextTrieNode * getOrCreateChildContext(const LineLocation &CallSite, StringRef ChildName, bool AllowCreate=true)
void setCallSiteLoc(const LineLocation &Loc)
LineLocation getCallSiteLoc() const
FunctionSamples * getFunctionSamples() const
std::optional< uint32_t > getFunctionSize() const
void removeChildContext(const LineLocation &CallSite, StringRef ChildName)
ContextTrieNode * getHottestChildContext(const LineLocation &CallSite)
void setParentContext(ContextTrieNode *Parent)
ContextTrieNode(ContextTrieNode *Parent=nullptr, StringRef FName=StringRef(), FunctionSamples *FSamples=nullptr, LineLocation CallLoc={0, 0})
void addFunctionSize(uint32_t FSize)
ContextTrieNode * getParentContext() const
void setFunctionSamples(FunctionSamples *FSamples)
ContextTrieNode * getChildContext(const LineLocation &CallSite, StringRef ChildName)
Debug location.
bool operator==(const Iterator &Other) const
FunctionSamples * getBaseSamplesFor(const Function &Func, bool MergeContext=true)
ContextTrieNode * getOrCreateContextPath(const SampleContext &Context, bool AllowCreate)
StringMap< ContextSamplesTy > & getFuncToCtxtProfiles()
StringRef getFuncNameFor(ContextTrieNode *Node) const
std::string getContextString(const FunctionSamples &FSamples) const
void promoteMergeContextSamplesTree(const Instruction &Inst, StringRef CalleeName)
ContextTrieNode * getContextNodeForProfile(const FunctionSamples *FSamples) const
FunctionSamples * getContextSamplesFor(const DILocation *DIL)
std::vector< FunctionSamples * > ContextSamplesTy
ContextSamplesTy & getAllContextSamplesFor(const Function &Func)
void markContextSamplesInlined(const FunctionSamples *InlinedSamples)
void createContextLessProfileMap(SampleProfileMap &ContextLessProfiles)
std::vector< const FunctionSamples * > getIndirectCalleeContextSamplesFor(const DILocation *DIL)
FunctionSamples * getCalleeContextSamplesFor(const CallBase &Inst, StringRef CalleeName)
ContextTrieNode * getContextFor(const SampleContext &Context)
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:111
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
Representation of the samples collected for a function.
Definition: SampleProf.h:718
std::unordered_map< SampleContext, FunctionSamples, SampleContext::Hash > SampleProfileMap
Definition: SampleProf.h:1199
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Represents the relative location of an instruction.
Definition: SampleProf.h:283