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