LLVM  16.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 
26 namespace llvm {
27 class CallBase;
28 class DILocation;
29 class Function;
30 class 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.
36 public:
37  ContextTrieNode(ContextTrieNode *Parent = nullptr,
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  Optional<uint32_t> getFunctionSize() const;
55  void addFunctionSize(uint32_t FSize);
56  LineLocation getCallSiteLoc() const;
58  void setParentContext(ContextTrieNode *Parent);
59  void setCallSiteLoc(const LineLocation &Loc);
60  void dumpNode();
61  void dumpTree();
62 
63 private:
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  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.
91 public:
92  using ContextSamplesTy = std::vector<FunctionSamples *>;
93 
94  SampleContextTracker() = default;
96  const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap);
97  // Populate the FuncToCtxtProfiles map after the trie is built.
98  void populateFuncToCtxtMap();
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);
137  getContextNodeForProfile(const FunctionSamples *FSamples) const {
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 
189 private:
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
llvm::SampleContextTracker::getCalleeContextSamplesFor
FunctionSamples * getCalleeContextSamplesFor(const CallBase &Inst, StringRef CalleeName)
Definition: SampleContextTracker.cpp:225
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::SampleContextTracker::getContextString
std::string getContextString(const FunctionSamples &FSamples) const
Definition: SampleContextTracker.cpp:430
llvm::SampleContextTracker::getFuncNameFor
StringRef getFuncNameFor(ContextTrieNode *Node) const
Definition: SampleContextTracker.cpp:457
llvm::ContextTrieNode::dumpNode
void dumpNode()
Definition: SampleContextTracker.cpp:150
llvm::Function
Definition: Function.h:60
StringRef.h
llvm::ContextTrieNode::getFuncName
StringRef getFuncName() const
Definition: SampleContextTracker.cpp:117
llvm::SampleContextTracker::Iterator::operator*
ContextTrieNode * operator*() const
Definition: SampleContextTracker.h:172
llvm::SampleContextTracker::populateFuncToCtxtMap
void populateFuncToCtxtMap()
Definition: SampleContextTracker.cpp:213
llvm::ContextTrieNode::setParentContext
void setParentContext(ContextTrieNode *Parent)
Definition: SampleContextTracker.cpp:142
llvm::sampleprof::SampleProfileMap
std::unordered_map< SampleContext, FunctionSamples, SampleContext::Hash > SampleProfileMap
Definition: SampleProf.h:1188
llvm::SampleContextTracker::markContextSamplesInlined
void markContextSamplesInlined(const FunctionSamples *InlinedSamples)
Definition: SampleContextTracker.cpp:363
llvm::SampleContextTracker::getContextFor
ContextTrieNode * getContextFor(const SampleContext &Context)
Definition: SampleContextTracker.cpp:465
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1557
llvm::SampleContextTracker::begin
Iterator begin()
Definition: SampleContextTracker.h:178
llvm::SampleContextTracker::ContextSamplesTy
std::vector< FunctionSamples * > ContextSamplesTy
Definition: SampleContextTracker.h:92
llvm::ContextTrieNode::getHottestChildContext
ContextTrieNode * getHottestChildContext(const LineLocation &CallSite)
Definition: SampleContextTracker.cpp:44
llvm::ContextTrieNode::getCallSiteLoc
LineLocation getCallSiteLoc() const
Definition: SampleContextTracker.cpp:136
llvm::SampleContextTracker::Iterator::Iterator
Iterator(ContextTrieNode *Node)
Definition: SampleContextTracker.h:154
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::ContextTrieNode::setCallSiteLoc
void setCallSiteLoc(const LineLocation &Loc)
Definition: SampleContextTracker.cpp:146
SampleProf.h
llvm::Instruction
Definition: Instruction.h:42
llvm::ContextTrieNode::setFunctionSamples
void setFunctionSamples(FunctionSamples *FSamples)
Definition: SampleContextTracker.cpp:123
llvm::sampleprof::SampleContext
Definition: SampleProf.h:502
llvm::SampleContextTracker::dump
void dump()
Definition: SampleContextTracker.cpp:455
llvm::StringMap< ContextSamplesTy >
llvm::ContextTrieNode::ContextTrieNode
ContextTrieNode(ContextTrieNode *Parent=nullptr, StringRef FName=StringRef(), FunctionSamples *FSamples=nullptr, LineLocation CallLoc={0, 0})
Definition: SampleContextTracker.h:37
llvm::SampleContextTracker::Iterator::operator++
Iterator & operator++()
Definition: SampleContextTracker.h:155
llvm::ContextTrieNode::getParentContext
ContextTrieNode * getParentContext() const
Definition: SampleContextTracker.cpp:138
llvm::sampleprof::FunctionSamples
Representation of the samples collected for a function.
Definition: SampleProf.h:711
llvm::SampleContextTracker::getFuncToCtxtProfiles
StringMap< ContextSamplesTy > & getFuncToCtxtProfiles()
Definition: SampleContextTracker.h:143
llvm::DenseMap
Definition: DenseMap.h:714
iterator.h
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::iterator_facade_base
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
llvm::SampleContextTracker::Iterator
Definition: SampleContextTracker.h:147
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SampleContextTracker
Definition: SampleContextTracker.h:90
llvm::SampleContextTracker::getContextNodeForProfile
ContextTrieNode * getContextNodeForProfile(const FunctionSamples *FSamples) const
Definition: SampleContextTracker.h:137
llvm::SampleContextTracker::promoteMergeContextSamplesTree
void promoteMergeContextSamplesTree(const Instruction &Inst, StringRef CalleeName)
Definition: SampleContextTracker.cpp:373
llvm::sampleprof::LineLocation
Represents the relative location of an instruction.
Definition: SampleProf.h:283
llvm::SampleContextTracker::getAllContextSamplesFor
ContextSamplesTy & getAllContextSamplesFor(const Function &Func)
Definition: SampleContextTracker.cpp:304
llvm::ContextTrieNode::getChildContext
ContextTrieNode * getChildContext(const LineLocation &CallSite, StringRef ChildName)
Definition: SampleContextTracker.cpp:31
llvm::ContextTrieNode::getAllChildContext
std::map< uint64_t, ContextTrieNode > & getAllChildContext()
Definition: SampleContextTracker.cpp:113
llvm::SampleContextTracker::Iterator::Iterator
Iterator()=default
llvm::ContextTrieNode::getOrCreateChildContext
ContextTrieNode * getOrCreateChildContext(const LineLocation &CallSite, StringRef ChildName, bool AllowCreate=true)
Definition: SampleContextTracker.cpp:178
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
uint32_t
llvm::ContextTrieNode::getFunctionSamples
FunctionSamples * getFunctionSamples() const
Definition: SampleContextTracker.cpp:119
llvm::ContextTrieNode
Definition: SampleContextTracker.h:35
llvm::ContextTrieNode::getFunctionSize
Optional< uint32_t > getFunctionSize() const
Definition: SampleContextTracker.cpp:127
Node
Definition: ItaniumDemangle.h:155
llvm::SampleContextTracker::SampleContextTracker
SampleContextTracker()=default
llvm::SampleContextTracker::getOrCreateContextPath
ContextTrieNode * getOrCreateContextPath(const SampleContext &Context, bool AllowCreate)
Definition: SampleContextTracker.cpp:532
llvm::SampleContextTracker::getRootContext
ContextTrieNode & getRootContext()
Definition: SampleContextTracker.cpp:371
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::ContextTrieNode::dumpTree
void dumpTree()
Definition: SampleContextTracker.cpp:161
llvm::SampleContextTracker::getBaseSamplesFor
FunctionSamples * getBaseSamplesFor(const Function &Func, bool MergeContext=true)
Definition: SampleContextTracker.cpp:314
llvm::ContextTrieNode::addFunctionSize
void addFunctionSize(uint32_t FSize)
Definition: SampleContextTracker.cpp:129
llvm::SampleContextTracker::createContextLessProfileMap
void createContextLessProfileMap(SampleProfileMap &ContextLessProfiles)
Definition: SampleContextTracker.cpp:633
llvm::SampleContextTracker::getContextSamplesFor
FunctionSamples * getContextSamplesFor(const DILocation *DIL)
Definition: SampleContextTracker.cpp:274
llvm::ContextTrieNode::removeChildContext
void removeChildContext(const LineLocation &CallSite, StringRef ChildName)
Definition: SampleContextTracker.cpp:106
llvm::SampleContextTracker::Iterator::operator==
bool operator==(const Iterator &Other) const
Definition: SampleContextTracker.h:164
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
StringMap.h
llvm::SampleContextTracker::end
Iterator end()
Definition: SampleContextTracker.h:179
llvm::SampleContextTracker::getIndirectCalleeContextSamplesFor
std::vector< const FunctionSamples * > getIndirectCalleeContextSamplesFor(const DILocation *DIL)
Definition: SampleContextTracker.cpp:254
llvm::codeview::PublicSymFlags::Function
@ Function
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1247