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 <map> 22 #include <queue> 23 #include <vector> 24 25 namespace llvm { 26 class CallBase; 27 class DILocation; 28 class Function; 29 class Instruction; 30 31 // Internal trie tree representation used for tracking context tree and sample 32 // profiles. The path from root node to a given node represents the context of 33 // that nodes' profile. 34 class ContextTrieNode { 35 public: 36 ContextTrieNode(ContextTrieNode *Parent = nullptr, 37 FunctionId FName = FunctionId(), 38 FunctionSamples *FSamples = nullptr, 39 LineLocation CallLoc = {0, 0}) 40 : ParentContext(Parent), FuncName(FName), FuncSamples(FSamples), 41 CallSiteLoc(CallLoc){}; 42 ContextTrieNode *getChildContext(const LineLocation &CallSite, 43 FunctionId ChildName); 44 ContextTrieNode *getHottestChildContext(const LineLocation &CallSite); 45 ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite, 46 FunctionId ChildName, 47 bool AllowCreate = true); 48 void removeChildContext(const LineLocation &CallSite, FunctionId ChildName); 49 std::map<uint64_t, ContextTrieNode> &getAllChildContext(); 50 FunctionId getFuncName() const; 51 FunctionSamples *getFunctionSamples() const; 52 void setFunctionSamples(FunctionSamples *FSamples); 53 std::optional<uint32_t> getFunctionSize() const; 54 void addFunctionSize(uint32_t FSize); 55 LineLocation getCallSiteLoc() const; 56 ContextTrieNode *getParentContext() const; 57 void setParentContext(ContextTrieNode *Parent); 58 void setCallSiteLoc(const LineLocation &Loc); 59 void dumpNode(); 60 void dumpTree(); 61 62 private: 63 // Map line+discriminator location to child context 64 std::map<uint64_t, ContextTrieNode> AllChildContext; 65 66 // Link to parent context node 67 ContextTrieNode *ParentContext; 68 69 // Function name for current context 70 FunctionId FuncName; 71 72 // Function Samples for current context 73 FunctionSamples *FuncSamples; 74 75 // Function size for current context 76 std::optional<uint32_t> FuncSize; 77 78 // Callsite location in parent context 79 LineLocation CallSiteLoc; 80 }; 81 82 // Profile tracker that manages profiles and its associated context. It 83 // provides interfaces used by sample profile loader to query context profile or 84 // base profile for given function or location; it also manages context tree 85 // manipulation that is needed to accommodate inline decisions so we have 86 // accurate post-inline profile for functions. Internally context profiles 87 // are organized in a trie, with each node representing profile for specific 88 // calling context and the context is identified by path from root to the node. 89 class SampleContextTracker { 90 public: 91 using ContextSamplesTy = std::vector<FunctionSamples *>; 92 93 SampleContextTracker() = default; 94 SampleContextTracker(SampleProfileMap &Profiles, 95 const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap); 96 // Populate the FuncToCtxtProfiles map after the trie is built. 97 void populateFuncToCtxtMap(); 98 // Query context profile for a specific callee with given name at a given 99 // call-site. The full context is identified by location of call instruction. 100 FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst, 101 StringRef CalleeName); 102 // Get samples for indirect call targets for call site at given location. 103 std::vector<const FunctionSamples *> 104 getIndirectCalleeContextSamplesFor(const DILocation *DIL); 105 // Query context profile for a given location. The full context 106 // is identified by input DILocation. 107 FunctionSamples *getContextSamplesFor(const DILocation *DIL); 108 // Query context profile for a given sample contxt of a function. 109 FunctionSamples *getContextSamplesFor(const SampleContext &Context); 110 // Get all context profile for given function. 111 ContextSamplesTy &getAllContextSamplesFor(const Function &Func); 112 ContextSamplesTy &getAllContextSamplesFor(StringRef Name); 113 ContextTrieNode *getOrCreateContextPath(const SampleContext &Context, 114 bool AllowCreate); 115 // Query base profile for a given function. A base profile is a merged view 116 // of all context profiles for contexts that are not inlined. 117 FunctionSamples *getBaseSamplesFor(const Function &Func, 118 bool MergeContext = true); 119 // Query base profile for a given function by name. 120 FunctionSamples *getBaseSamplesFor(FunctionId Name, 121 bool MergeContext = true); 122 // Retrieve the context trie node for given profile context 123 ContextTrieNode *getContextFor(const SampleContext &Context); 124 // Get real function name for a given trie node. 125 StringRef getFuncNameFor(ContextTrieNode *Node) const; 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); 130 ContextTrieNode &getRootContext(); 131 void promoteMergeContextSamplesTree(const Instruction &Inst, 132 FunctionId CalleeName); 133 134 // Create a merged conext-less profile map. 135 void createContextLessProfileMap(SampleProfileMap &ContextLessProfiles); 136 ContextTrieNode * 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 } 143 HashKeyMap<std::unordered_map, FunctionId, ContextSamplesTy> 144 &getFuncToCtxtProfiles() { 145 return FuncToCtxtProfiles; 146 } 147 148 class Iterator : public llvm::iterator_facade_base< 149 Iterator, std::forward_iterator_tag, ContextTrieNode *, 150 std::ptrdiff_t, ContextTrieNode **, ContextTrieNode *> { 151 std::queue<ContextTrieNode *> NodeQueue; 152 153 public: 154 explicit Iterator() = default; 155 explicit Iterator(ContextTrieNode *Node) { NodeQueue.push(Node); } 156 Iterator &operator++() { 157 assert(!NodeQueue.empty() && "Iterator already at the end"); 158 ContextTrieNode *Node = NodeQueue.front(); 159 NodeQueue.pop(); 160 for (auto &It : Node->getAllChildContext()) 161 NodeQueue.push(&It.second); 162 return *this; 163 } 164 165 bool operator==(const Iterator &Other) const { 166 if (NodeQueue.empty() && Other.NodeQueue.empty()) 167 return true; 168 if (NodeQueue.empty() || Other.NodeQueue.empty()) 169 return false; 170 return NodeQueue.front() == Other.NodeQueue.front(); 171 } 172 173 ContextTrieNode *operator*() const { 174 assert(!NodeQueue.empty() && "Invalid access to end iterator"); 175 return NodeQueue.front(); 176 } 177 }; 178 179 Iterator begin() { return Iterator(&RootContext); } 180 Iterator end() { return Iterator(); } 181 182 #ifndef NDEBUG 183 // Get a context string from root to current node. 184 std::string getContextString(const FunctionSamples &FSamples) const; 185 std::string getContextString(ContextTrieNode *Node) const; 186 #endif 187 // Dump the internal context profile trie. 188 void dump(); 189 190 private: 191 ContextTrieNode *getContextFor(const DILocation *DIL); 192 ContextTrieNode *getCalleeContextFor(const DILocation *DIL, 193 FunctionId CalleeName); 194 ContextTrieNode *getTopLevelContextNode(FunctionId FName); 195 ContextTrieNode &addTopLevelContextNode(FunctionId FName); 196 ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo); 197 void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode); 198 ContextTrieNode & 199 promoteMergeContextSamplesTree(ContextTrieNode &FromNode, 200 ContextTrieNode &ToNodeParent); 201 ContextTrieNode &moveContextSamples(ContextTrieNode &ToNodeParent, 202 const LineLocation &CallSite, 203 ContextTrieNode &&NodeToMove); 204 void setContextNode(const FunctionSamples *FSample, ContextTrieNode *Node) { 205 ProfileToNodeMap[FSample] = Node; 206 } 207 // Map from function name to context profiles (excluding base profile) 208 HashKeyMap<std::unordered_map, FunctionId, ContextSamplesTy> 209 FuncToCtxtProfiles; 210 211 // Map from current FunctionSample to the belonged context trie. 212 std::unordered_map<const FunctionSamples *, ContextTrieNode *> 213 ProfileToNodeMap; 214 215 // Map from function guid to real function names. Only used in md5 mode. 216 const DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap; 217 218 // Root node for context trie tree 219 ContextTrieNode RootContext; 220 }; 221 222 } // end namespace llvm 223 #endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H 224