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" 21 #include "llvm/IR/DebugInfoMetadata.h" 22 #include "llvm/IR/Instructions.h" 23 #include "llvm/ProfileData/SampleProf.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. 36 class ContextTrieNode { 37 public: 38 ContextTrieNode(ContextTrieNode *Parent = nullptr, 39 StringRef FName = StringRef(), 40 FunctionSamples *FSamples = nullptr, 41 LineLocation CallLoc = {0, 0}) ParentContext(Parent)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. 91 class SampleContextTracker { 92 public: 93 using ContextSamplesTy = SmallVector<FunctionSamples *, 16>; 94 95 SampleContextTracker(StringMap<FunctionSamples> &Profiles); 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 153