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/SmallSet.h" 19 #include "llvm/ADT/StringMap.h" 20 #include "llvm/ADT/StringRef.h" 21 #include "llvm/Analysis/CallGraph.h" 22 #include "llvm/IR/DebugInfoMetadata.h" 23 #include "llvm/IR/Instructions.h" 24 #include "llvm/ProfileData/SampleProf.h" 25 #include <list> 26 #include <map> 27 #include <vector> 28 29 using namespace llvm; 30 using namespace sampleprof; 31 32 namespace llvm { 33 34 // Internal trie tree representation used for tracking context tree and sample 35 // profiles. The path from root node to a given node represents the context of 36 // that nodes' profile. 37 class ContextTrieNode { 38 public: 39 ContextTrieNode(ContextTrieNode *Parent = nullptr, 40 StringRef FName = StringRef(), 41 FunctionSamples *FSamples = nullptr, 42 LineLocation CallLoc = {0, 0}) ParentContext(Parent)43 : ParentContext(Parent), FuncName(FName), FuncSamples(FSamples), 44 CallSiteLoc(CallLoc){}; 45 ContextTrieNode *getChildContext(const LineLocation &CallSite, 46 StringRef CalleeName); 47 ContextTrieNode *getHottestChildContext(const LineLocation &CallSite); 48 ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite, 49 StringRef CalleeName, 50 bool AllowCreate = true); 51 52 ContextTrieNode &moveToChildContext(const LineLocation &CallSite, 53 ContextTrieNode &&NodeToMove, 54 StringRef ContextStrToRemove, 55 bool DeleteNode = true); 56 void removeChildContext(const LineLocation &CallSite, StringRef CalleeName); 57 std::map<uint32_t, ContextTrieNode> &getAllChildContext(); 58 const StringRef getFuncName() const; 59 FunctionSamples *getFunctionSamples() const; 60 void setFunctionSamples(FunctionSamples *FSamples); 61 LineLocation getCallSiteLoc() const; 62 ContextTrieNode *getParentContext() const; 63 void setParentContext(ContextTrieNode *Parent); 64 void dump(); 65 66 private: 67 static uint32_t nodeHash(StringRef ChildName, const LineLocation &Callsite); 68 69 // Map line+discriminator location to child context 70 std::map<uint32_t, ContextTrieNode> AllChildContext; 71 72 // Link to parent context node 73 ContextTrieNode *ParentContext; 74 75 // Function name for current context 76 StringRef FuncName; 77 78 // Function Samples for current context 79 FunctionSamples *FuncSamples; 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 = SmallSet<FunctionSamples *, 16>; 95 96 SampleContextTracker(StringMap<FunctionSamples> &Profiles); 97 // Query context profile for a specific callee with given name at a given 98 // call-site. The full context is identified by location of call instruction. 99 FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst, 100 StringRef CalleeName); 101 // Get samples for indirect call targets for call site at given location. 102 std::vector<const FunctionSamples *> 103 getIndirectCalleeContextSamplesFor(const DILocation *DIL); 104 // Query context profile for a given location. The full context 105 // is identified by input DILocation. 106 FunctionSamples *getContextSamplesFor(const DILocation *DIL); 107 // Query context profile for a given sample contxt of a function. 108 FunctionSamples *getContextSamplesFor(const SampleContext &Context); 109 // Get all context profile for given function. 110 ContextSamplesTy &getAllContextSamplesFor(const Function &Func); 111 ContextSamplesTy &getAllContextSamplesFor(StringRef Name); 112 // Query base profile for a given function. A base profile is a merged view 113 // of all context profiles for contexts that are not inlined. 114 FunctionSamples *getBaseSamplesFor(const Function &Func, 115 bool MergeContext = true); 116 // Query base profile for a given function by name. 117 FunctionSamples *getBaseSamplesFor(StringRef Name, bool MergeContext); 118 // Mark a context profile as inlined when function is inlined. 119 // This makes sure that inlined context profile will be excluded in 120 // function's base profile. 121 void markContextSamplesInlined(const FunctionSamples *InlinedSamples); 122 void promoteMergeContextSamplesTree(const Instruction &Inst, 123 StringRef CalleeName); 124 void addCallGraphEdges(CallGraph &CG, StringMap<Function *> &SymbolMap); 125 // Dump the internal context profile trie. 126 void dump(); 127 128 private: 129 ContextTrieNode *getContextFor(const DILocation *DIL); 130 ContextTrieNode *getContextFor(const SampleContext &Context); 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> FuncToCtxtProfileSet; 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