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/StringRef.h" 19 #include "llvm/ADT/iterator.h" 20 #include "llvm/ProfileData/SampleProf.h" 21 #include "llvm/Support/Compiler.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. 35 class ContextTrieNode { 36 public: 37 ContextTrieNode(ContextTrieNode *Parent = nullptr, 38 FunctionId FName = FunctionId(), 39 FunctionSamples *FSamples = nullptr, 40 LineLocation CallLoc = {0, 0}) ParentContext(Parent)41 : ParentContext(Parent), FuncName(FName), FuncSamples(FSamples), 42 CallSiteLoc(CallLoc){}; 43 LLVM_ABI ContextTrieNode *getChildContext(const LineLocation &CallSite, 44 FunctionId ChildName); 45 LLVM_ABI ContextTrieNode * 46 getHottestChildContext(const LineLocation &CallSite); 47 LLVM_ABI ContextTrieNode * 48 getOrCreateChildContext(const LineLocation &CallSite, FunctionId ChildName, 49 bool AllowCreate = true); 50 LLVM_ABI void removeChildContext(const LineLocation &CallSite, 51 FunctionId ChildName); 52 LLVM_ABI std::map<uint64_t, ContextTrieNode> &getAllChildContext(); 53 LLVM_ABI FunctionId getFuncName() const; 54 LLVM_ABI FunctionSamples *getFunctionSamples() const; 55 LLVM_ABI void setFunctionSamples(FunctionSamples *FSamples); 56 LLVM_ABI std::optional<uint32_t> getFunctionSize() const; 57 LLVM_ABI void addFunctionSize(uint32_t FSize); 58 LLVM_ABI LineLocation getCallSiteLoc() const; 59 LLVM_ABI ContextTrieNode *getParentContext() const; 60 LLVM_ABI void setParentContext(ContextTrieNode *Parent); 61 LLVM_ABI void setCallSiteLoc(const LineLocation &Loc); 62 LLVM_ABI void dumpNode(); 63 LLVM_ABI 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 FunctionId FuncName; 74 75 // Function Samples for current context 76 FunctionSamples *FuncSamples; 77 78 // Function size for current context 79 std::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. 92 class SampleContextTracker { 93 public: 94 using ContextSamplesTy = std::vector<FunctionSamples *>; 95 96 SampleContextTracker() = default; 97 LLVM_ABI 98 SampleContextTracker(SampleProfileMap &Profiles, 99 const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap); 100 // Populate the FuncToCtxtProfiles map after the trie is built. 101 LLVM_ABI void populateFuncToCtxtMap(); 102 // Query context profile for a specific callee with given name at a given 103 // call-site. The full context is identified by location of call instruction. 104 LLVM_ABI FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst, 105 StringRef CalleeName); 106 // Get samples for indirect call targets for call site at given location. 107 LLVM_ABI std::vector<const FunctionSamples *> 108 getIndirectCalleeContextSamplesFor(const DILocation *DIL); 109 // Query context profile for a given location. The full context 110 // is identified by input DILocation. 111 LLVM_ABI FunctionSamples *getContextSamplesFor(const DILocation *DIL); 112 // Query context profile for a given sample contxt of a function. 113 LLVM_ABI FunctionSamples *getContextSamplesFor(const SampleContext &Context); 114 // Get all context profile for given function. 115 LLVM_ABI ContextSamplesTy &getAllContextSamplesFor(const Function &Func); 116 LLVM_ABI ContextSamplesTy &getAllContextSamplesFor(StringRef Name); 117 LLVM_ABI ContextTrieNode *getOrCreateContextPath(const SampleContext &Context, 118 bool AllowCreate); 119 // Query base profile for a given function. A base profile is a merged view 120 // of all context profiles for contexts that are not inlined. 121 LLVM_ABI FunctionSamples *getBaseSamplesFor(const Function &Func, 122 bool MergeContext = true); 123 // Query base profile for a given function by name. 124 LLVM_ABI FunctionSamples *getBaseSamplesFor(FunctionId Name, 125 bool MergeContext = true); 126 // Retrieve the context trie node for given profile context 127 LLVM_ABI ContextTrieNode *getContextFor(const SampleContext &Context); 128 // Get real function name for a given trie node. 129 LLVM_ABI StringRef getFuncNameFor(ContextTrieNode *Node) const; 130 // Mark a context profile as inlined when function is inlined. 131 // This makes sure that inlined context profile will be excluded in 132 // function's base profile. 133 LLVM_ABI void 134 markContextSamplesInlined(const FunctionSamples *InlinedSamples); 135 LLVM_ABI ContextTrieNode &getRootContext(); 136 LLVM_ABI void promoteMergeContextSamplesTree(const Instruction &Inst, 137 FunctionId CalleeName); 138 139 // Create a merged conext-less profile map. 140 LLVM_ABI void 141 createContextLessProfileMap(SampleProfileMap &ContextLessProfiles); 142 ContextTrieNode * getContextNodeForProfile(const FunctionSamples * FSamples)143 getContextNodeForProfile(const FunctionSamples *FSamples) const { 144 auto I = ProfileToNodeMap.find(FSamples); 145 if (I == ProfileToNodeMap.end()) 146 return nullptr; 147 return I->second; 148 } 149 HashKeyMap<std::unordered_map, FunctionId, ContextSamplesTy> getFuncToCtxtProfiles()150 &getFuncToCtxtProfiles() { 151 return FuncToCtxtProfiles; 152 } 153 154 class Iterator : public llvm::iterator_facade_base< 155 Iterator, std::forward_iterator_tag, ContextTrieNode *, 156 std::ptrdiff_t, ContextTrieNode **, ContextTrieNode *> { 157 std::queue<ContextTrieNode *> NodeQueue; 158 159 public: 160 explicit Iterator() = default; Iterator(ContextTrieNode * Node)161 explicit Iterator(ContextTrieNode *Node) { NodeQueue.push(Node); } 162 Iterator &operator++() { 163 assert(!NodeQueue.empty() && "Iterator already at the end"); 164 ContextTrieNode *Node = NodeQueue.front(); 165 NodeQueue.pop(); 166 for (auto &It : Node->getAllChildContext()) 167 NodeQueue.push(&It.second); 168 return *this; 169 } 170 171 bool operator==(const Iterator &Other) const { 172 if (NodeQueue.empty() && Other.NodeQueue.empty()) 173 return true; 174 if (NodeQueue.empty() || Other.NodeQueue.empty()) 175 return false; 176 return NodeQueue.front() == Other.NodeQueue.front(); 177 } 178 179 ContextTrieNode *operator*() const { 180 assert(!NodeQueue.empty() && "Invalid access to end iterator"); 181 return NodeQueue.front(); 182 } 183 }; 184 begin()185 Iterator begin() { return Iterator(&RootContext); } end()186 Iterator end() { return Iterator(); } 187 188 #ifndef NDEBUG 189 // Get a context string from root to current node. 190 std::string getContextString(const FunctionSamples &FSamples) const; 191 std::string getContextString(ContextTrieNode *Node) const; 192 #endif 193 // Dump the internal context profile trie. 194 LLVM_ABI void dump(); 195 196 private: 197 ContextTrieNode *getContextFor(const DILocation *DIL); 198 ContextTrieNode *getCalleeContextFor(const DILocation *DIL, 199 FunctionId CalleeName); 200 ContextTrieNode *getTopLevelContextNode(FunctionId FName); 201 ContextTrieNode &addTopLevelContextNode(FunctionId FName); 202 ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo); 203 void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode); 204 ContextTrieNode & 205 promoteMergeContextSamplesTree(ContextTrieNode &FromNode, 206 ContextTrieNode &ToNodeParent); 207 ContextTrieNode &moveContextSamples(ContextTrieNode &ToNodeParent, 208 const LineLocation &CallSite, 209 ContextTrieNode &&NodeToMove); setContextNode(const FunctionSamples * FSample,ContextTrieNode * Node)210 void setContextNode(const FunctionSamples *FSample, ContextTrieNode *Node) { 211 ProfileToNodeMap[FSample] = Node; 212 } 213 // Map from function name to context profiles (excluding base profile) 214 HashKeyMap<std::unordered_map, FunctionId, ContextSamplesTy> 215 FuncToCtxtProfiles; 216 217 // Map from current FunctionSample to the belonged context trie. 218 std::unordered_map<const FunctionSamples *, ContextTrieNode *> 219 ProfileToNodeMap; 220 221 // Map from function guid to real function names. Only used in md5 mode. 222 const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap; 223 224 // Root node for context trie tree 225 ContextTrieNode RootContext; 226 }; 227 228 } // end namespace llvm 229 #endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H 230