LLVM  15.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"
21 #include <map>
22 #include <vector>
23 
24 namespace llvm {
25 class CallBase;
26 class DILocation;
27 class Function;
28 class Instruction;
29 
30 // Internal trie tree representation used for tracking context tree and sample
31 // profiles. The path from root node to a given node represents the context of
32 // that nodes' profile.
34 public:
35  ContextTrieNode(ContextTrieNode *Parent = nullptr,
36  StringRef FName = StringRef(),
37  FunctionSamples *FSamples = nullptr,
38  LineLocation CallLoc = {0, 0})
39  : ParentContext(Parent), FuncName(FName), FuncSamples(FSamples),
40  CallSiteLoc(CallLoc){};
41  ContextTrieNode *getChildContext(const LineLocation &CallSite,
42  StringRef ChildName);
43  ContextTrieNode *getHottestChildContext(const LineLocation &CallSite);
44  ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite,
45  StringRef ChildName,
46  bool AllowCreate = true);
47 
48  ContextTrieNode &moveToChildContext(const LineLocation &CallSite,
49  ContextTrieNode &&NodeToMove,
50  uint32_t ContextFramesToRemove,
51  bool DeleteNode = true);
52  void removeChildContext(const LineLocation &CallSite, StringRef ChildName);
53  std::map<uint64_t, ContextTrieNode> &getAllChildContext();
54  StringRef getFuncName() const;
55  FunctionSamples *getFunctionSamples() const;
56  void setFunctionSamples(FunctionSamples *FSamples);
57  Optional<uint32_t> getFunctionSize() const;
58  void addFunctionSize(uint32_t FSize);
59  LineLocation getCallSiteLoc() const;
61  void setParentContext(ContextTrieNode *Parent);
62  void dumpNode();
63  void dumpTree();
64 
65 private:
66  // Map line+discriminator location to child context
67  std::map<uint64_t, ContextTrieNode> AllChildContext;
68 
69  // Link to parent context node
70  ContextTrieNode *ParentContext;
71 
72  // Function name for current context
73  StringRef FuncName;
74 
75  // Function Samples for current context
76  FunctionSamples *FuncSamples;
77 
78  // Function size for current context
79  Optional<uint32_t> FuncSize;
80 
81  // Callsite location in parent context
82  LineLocation CallSiteLoc;
83 };
84 
85 // Profile tracker that manages profiles and its associated context. It
86 // provides interfaces used by sample profile loader to query context profile or
87 // base profile for given function or location; it also manages context tree
88 // manipulation that is needed to accommodate inline decisions so we have
89 // accurate post-inline profile for functions. Internally context profiles
90 // are organized in a trie, with each node representing profile for specific
91 // calling context and the context is identified by path from root to the node.
93 public:
94  struct ProfileComparer {
96  // Sort function profiles by the number of total samples and their
97  // contexts.
98  if (A->getTotalSamples() == B->getTotalSamples())
99  return A->getContext() < B->getContext();
100  return A->getTotalSamples() > B->getTotalSamples();
101  }
102  };
103 
104  // Keep profiles of a function sorted so that they will be processed/promoted
105  // deterministically.
106  using ContextSamplesTy = std::set<FunctionSamples *, ProfileComparer>;
107 
109  const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap);
110  // Query context profile for a specific callee with given name at a given
111  // call-site. The full context is identified by location of call instruction.
113  StringRef CalleeName);
114  // Get samples for indirect call targets for call site at given location.
115  std::vector<const FunctionSamples *>
117  // Query context profile for a given location. The full context
118  // is identified by input DILocation.
120  // Query context profile for a given sample contxt of a function.
122  // Get all context profile for given function.
125  // Query base profile for a given function. A base profile is a merged view
126  // of all context profiles for contexts that are not inlined.
128  bool MergeContext = true);
129  // Query base profile for a given function by name.
130  FunctionSamples *getBaseSamplesFor(StringRef Name, bool MergeContext = true);
131  // Retrieve the context trie node for given profile context
133  // Get real function name for a given trie node.
135  // Mark a context profile as inlined when function is inlined.
136  // This makes sure that inlined context profile will be excluded in
137  // function's base profile.
138  void markContextSamplesInlined(const FunctionSamples *InlinedSamples);
141  StringRef CalleeName);
142  // Dump the internal context profile trie.
143  void dump();
144 
145 private:
147  ContextTrieNode *getCalleeContextFor(const DILocation *DIL,
148  StringRef CalleeName);
149  ContextTrieNode *getOrCreateContextPath(const SampleContext &Context,
150  bool AllowCreate);
151  ContextTrieNode *getTopLevelContextNode(StringRef FName);
152  ContextTrieNode &addTopLevelContextNode(StringRef FName);
154  void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode,
155  uint32_t ContextFramesToRemove);
158  ContextTrieNode &ToNodeParent,
159  uint32_t ContextFramesToRemove);
160 
161  // Map from function name to context profiles (excluding base profile)
162  StringMap<ContextSamplesTy> FuncToCtxtProfiles;
163 
164  // Map from function guid to real function names. Only used in md5 mode.
165  const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap;
166 
167  // Root node for context trie tree
168  ContextTrieNode RootContext;
169 };
170 
171 } // end namespace llvm
172 #endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
llvm::SampleContextTracker::getCalleeContextSamplesFor
FunctionSamples * getCalleeContextSamplesFor(const CallBase &Inst, StringRef CalleeName)
Definition: SampleContextTracker.cpp:216
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SampleContextTracker::getFuncNameFor
StringRef getFuncNameFor(ContextTrieNode *Node) const
Definition: SampleContextTracker.cpp:422
llvm::ContextTrieNode::dumpNode
void dumpNode()
Definition: SampleContextTracker.cpp:151
llvm::Function
Definition: Function.h:60
StringRef.h
llvm::ContextTrieNode::getFuncName
StringRef getFuncName() const
Definition: SampleContextTracker.cpp:122
llvm::ContextTrieNode::setParentContext
void setParentContext(ContextTrieNode *Parent)
Definition: SampleContextTracker.cpp:147
llvm::sampleprof::SampleProfileMap
std::unordered_map< SampleContext, FunctionSamples, SampleContext::Hash > SampleProfileMap
Definition: SampleProf.h:1193
llvm::SampleContextTracker::markContextSamplesInlined
void markContextSamplesInlined(const FunctionSamples *InlinedSamples)
Definition: SampleContextTracker.cpp:354
llvm::SampleContextTracker::getContextFor
ContextTrieNode * getContextFor(const SampleContext &Context)
Definition: SampleContextTracker.cpp:430
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1551
llvm::ContextTrieNode::getHottestChildContext
ContextTrieNode * getHottestChildContext(const LineLocation &CallSite)
Definition: SampleContextTracker.cpp:44
llvm::ContextTrieNode::getCallSiteLoc
LineLocation getCallSiteLoc() const
Definition: SampleContextTracker.cpp:141
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
SampleProf.h
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:42
StringMap.h
llvm::ContextTrieNode::setFunctionSamples
void setFunctionSamples(FunctionSamples *FSamples)
Definition: SampleContextTracker.cpp:128
llvm::sampleprof::SampleContext
Definition: SampleProf.h:501
llvm::SampleContextTracker::ContextSamplesTy
std::set< FunctionSamples *, ProfileComparer > ContextSamplesTy
Definition: SampleContextTracker.h:106
llvm::SampleContextTracker::dump
void dump()
Definition: SampleContextTracker.cpp:420
llvm::StringMap< ContextSamplesTy >
llvm::ContextTrieNode::ContextTrieNode
ContextTrieNode(ContextTrieNode *Parent=nullptr, StringRef FName=StringRef(), FunctionSamples *FSamples=nullptr, LineLocation CallLoc={0, 0})
Definition: SampleContextTracker.h:35
llvm::ContextTrieNode::getParentContext
ContextTrieNode * getParentContext() const
Definition: SampleContextTracker.cpp:143
llvm::ContextTrieNode::moveToChildContext
ContextTrieNode & moveToChildContext(const LineLocation &CallSite, ContextTrieNode &&NodeToMove, uint32_t ContextFramesToRemove, bool DeleteNode=true)
Definition: SampleContextTracker.cpp:66
llvm::sampleprof::FunctionSamples
Representation of the samples collected for a function.
Definition: SampleProf.h:720
llvm::DenseMap
Definition: DenseMap.h:716
llvm::SampleContextTracker::SampleContextTracker
SampleContextTracker(SampleProfileMap &Profiles, const DenseMap< uint64_t, StringRef > *GUIDToFuncNameMap)
Definition: SampleContextTracker.cpp:197
llvm::SampleContextTracker
Definition: SampleContextTracker.h:92
llvm::SampleContextTracker::promoteMergeContextSamplesTree
void promoteMergeContextSamplesTree(const Instruction &Inst, StringRef CalleeName)
Definition: SampleContextTracker.cpp:364
llvm::sampleprof::LineLocation
Represents the relative location of an instruction.
Definition: SampleProf.h:282
llvm::SampleContextTracker::getAllContextSamplesFor
ContextSamplesTy & getAllContextSamplesFor(const Function &Func)
Definition: SampleContextTracker.cpp:295
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:118
llvm::ContextTrieNode::getOrCreateChildContext
ContextTrieNode * getOrCreateChildContext(const LineLocation &CallSite, StringRef ChildName, bool AllowCreate=true)
Definition: SampleContextTracker.cpp:179
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
uint32_t
llvm::ContextTrieNode::getFunctionSamples
FunctionSamples * getFunctionSamples() const
Definition: SampleContextTracker.cpp:124
llvm::ContextTrieNode
Definition: SampleContextTracker.h:33
llvm::ContextTrieNode::getFunctionSize
Optional< uint32_t > getFunctionSize() const
Definition: SampleContextTracker.cpp:132
Node
Definition: ItaniumDemangle.h:155
llvm::SampleContextTracker::getRootContext
ContextTrieNode & getRootContext()
Definition: SampleContextTracker.cpp:362
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::ContextTrieNode::dumpTree
void dumpTree()
Definition: SampleContextTracker.cpp:162
llvm::SampleContextTracker::getBaseSamplesFor
FunctionSamples * getBaseSamplesFor(const Function &Func, bool MergeContext=true)
Definition: SampleContextTracker.cpp:305
llvm::ContextTrieNode::addFunctionSize
void addFunctionSize(uint32_t FSize)
Definition: SampleContextTracker.cpp:134
llvm::SampleContextTracker::getContextSamplesFor
FunctionSamples * getContextSamplesFor(const DILocation *DIL)
Definition: SampleContextTracker.cpp:265
llvm::ContextTrieNode::removeChildContext
void removeChildContext(const LineLocation &CallSite, StringRef ChildName)
Definition: SampleContextTracker.cpp:111
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::SampleContextTracker::ProfileComparer::operator()
bool operator()(FunctionSamples *A, FunctionSamples *B) const
Definition: SampleContextTracker.h:95
llvm::SampleContextTracker::ProfileComparer
Definition: SampleContextTracker.h:94
llvm::SampleContextTracker::getIndirectCalleeContextSamplesFor
std::vector< const FunctionSamples * > getIndirectCalleeContextSamplesFor(const DILocation *DIL)
Definition: SampleContextTracker.cpp:245
llvm::codeview::PublicSymFlags::Function
@ Function