LLVM  13.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 CalleeName);
46  ContextTrieNode *getHottestChildContext(const LineLocation &CallSite);
47  ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite,
48  StringRef CalleeName,
49  bool AllowCreate = true);
50 
51  ContextTrieNode &moveToChildContext(const LineLocation &CallSite,
52  ContextTrieNode &&NodeToMove,
53  StringRef ContextStrToRemove,
54  bool DeleteNode = true);
55  void removeChildContext(const LineLocation &CallSite, StringRef CalleeName);
56  std::map<uint32_t, ContextTrieNode> &getAllChildContext();
57  StringRef getFuncName() const;
58  FunctionSamples *getFunctionSamples() const;
59  void setFunctionSamples(FunctionSamples *FSamples);
60  LineLocation getCallSiteLoc() const;
61  ContextTrieNode *getParentContext() const;
62  void setParentContext(ContextTrieNode *Parent);
63  void dump();
64 
65 private:
66  static uint32_t nodeHash(StringRef ChildName, const LineLocation &Callsite);
67 
68  // Map line+discriminator location to child context
69  std::map<uint32_t, ContextTrieNode> AllChildContext;
70 
71  // Link to parent context node
72  ContextTrieNode *ParentContext;
73 
74  // Function name for current context
75  StringRef FuncName;
76 
77  // Function Samples for current context
78  FunctionSamples *FuncSamples;
79 
80  // Callsite location in parent context
81  LineLocation CallSiteLoc;
82 };
83 
84 // Profile tracker that manages profiles and its associated context. It
85 // provides interfaces used by sample profile loader to query context profile or
86 // base profile for given function or location; it also manages context tree
87 // manipulation that is needed to accommodate inline decisions so we have
88 // accurate post-inline profile for functions. Internally context profiles
89 // are organized in a trie, with each node representing profile for specific
90 // calling context and the context is identified by path from root to the node.
92 public:
94 
96  // Query context profile for a specific callee with given name at a given
97  // call-site. The full context is identified by location of call instruction.
98  FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst,
99  StringRef CalleeName);
100  // Get samples for indirect call targets for call site at given location.
101  std::vector<const FunctionSamples *>
102  getIndirectCalleeContextSamplesFor(const DILocation *DIL);
103  // Query context profile for a given location. The full context
104  // is identified by input DILocation.
105  FunctionSamples *getContextSamplesFor(const DILocation *DIL);
106  // Query context profile for a given sample contxt of a function.
107  FunctionSamples *getContextSamplesFor(const SampleContext &Context);
108  // Get all context profile for given function.
109  ContextSamplesTy &getAllContextSamplesFor(const Function &Func);
110  ContextSamplesTy &getAllContextSamplesFor(StringRef Name);
111  // Query base profile for a given function. A base profile is a merged view
112  // of all context profiles for contexts that are not inlined.
113  FunctionSamples *getBaseSamplesFor(const Function &Func,
114  bool MergeContext = true);
115  // Query base profile for a given function by name.
116  FunctionSamples *getBaseSamplesFor(StringRef Name, bool MergeContext = true);
117  // Retrieve the context trie node for given profile context
118  ContextTrieNode *getContextFor(const SampleContext &Context);
119  // Mark a context profile as inlined when function is inlined.
120  // This makes sure that inlined context profile will be excluded in
121  // function's base profile.
122  void markContextSamplesInlined(const FunctionSamples *InlinedSamples);
123  ContextTrieNode &getRootContext();
124  void promoteMergeContextSamplesTree(const Instruction &Inst,
125  StringRef CalleeName);
126  // Dump the internal context profile trie.
127  void dump();
128 
129 private:
130  ContextTrieNode *getContextFor(const DILocation *DIL);
131  ContextTrieNode *getCalleeContextFor(const DILocation *DIL,
132  StringRef CalleeName);
133  ContextTrieNode *getOrCreateContextPath(const SampleContext &Context,
134  bool AllowCreate);
135  ContextTrieNode *getTopLevelContextNode(StringRef FName);
136  ContextTrieNode &addTopLevelContextNode(StringRef FName);
137  ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo);
138  void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode,
139  StringRef ContextStrToRemove);
140  ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &FromNode,
141  ContextTrieNode &ToNodeParent,
142  StringRef ContextStrToRemove);
143 
144  // Map from function name to context profiles (excluding base profile)
145  StringMap<ContextSamplesTy> FuncToCtxtProfiles;
146 
147  // Root node for context trie tree
148  ContextTrieNode RootContext;
149 };
150 
151 } // end namespace llvm
152 #endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H
llvm
Definition: AllocatorList.h:23
DebugInfoMetadata.h
llvm::Function
Definition: Function.h:61
StringRef.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::DILocation
Debug location.
Definition: DebugInfoMetadata.h:1562
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
SampleProf.h
llvm::Instruction
Definition: Instruction.h:45
StringMap.h
llvm::sampleprof::SampleContext
Definition: SampleProf.h:408
llvm::StringMap
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:108
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:533
llvm::SampleContextTracker
Definition: SampleContextTracker.h:91
llvm::sampleprof::LineLocation
Represents the relative location of an instruction.
Definition: SampleProf.h:264
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:1164