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/IR/DebugInfoMetadata.h" 22 #include "llvm/IR/Instructions.h" 23 #include "llvm/ProfileData/SampleProf.h" 24 #include <list> 25 #include <map> 26 27 using namespace llvm; 28 using namespace sampleprof; 29 30 namespace llvm { 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 StringRef FName = StringRef(), 39 FunctionSamples *FSamples = nullptr, 40 LineLocation CallLoc = {0, 0}) ParentContext(Parent)41 : ParentContext(Parent), FuncName(FName), FuncSamples(FSamples), 42 CallSiteLoc(CallLoc){}; 43 ContextTrieNode *getChildContext(const LineLocation &CallSite, 44 StringRef CalleeName); 45 ContextTrieNode *getChildContext(const LineLocation &CallSite); 46 ContextTrieNode *getOrCreateChildContext(const LineLocation &CallSite, 47 StringRef CalleeName, 48 bool AllowCreate = true); 49 50 ContextTrieNode &moveToChildContext(const LineLocation &CallSite, 51 ContextTrieNode &&NodeToMove, 52 StringRef ContextStrToRemove, 53 bool DeleteNode = true); 54 void removeChildContext(const LineLocation &CallSite, StringRef CalleeName); 55 std::map<uint32_t, ContextTrieNode> &getAllChildContext(); 56 const StringRef getFuncName() const; 57 FunctionSamples *getFunctionSamples() const; 58 void setFunctionSamples(FunctionSamples *FSamples); 59 LineLocation getCallSiteLoc() const; 60 ContextTrieNode *getParentContext() const; 61 void setParentContext(ContextTrieNode *Parent); 62 void dump(); 63 64 private: 65 static uint32_t nodeHash(StringRef ChildName, const LineLocation &Callsite); 66 67 // Map line+discriminator location to child context 68 std::map<uint32_t, ContextTrieNode> AllChildContext; 69 70 // Link to parent context node 71 ContextTrieNode *ParentContext; 72 73 // Function name for current context 74 StringRef FuncName; 75 76 // Function Samples for current context 77 FunctionSamples *FuncSamples; 78 79 // Callsite location in parent context 80 LineLocation CallSiteLoc; 81 }; 82 83 // Profile tracker that manages profiles and its associated context. It 84 // provides interfaces used by sample profile loader to query context profile or 85 // base profile for given function or location; it also manages context tree 86 // manipulation that is needed to accommodate inline decisions so we have 87 // accurate post-inline profile for functions. Internally context profiles 88 // are organized in a trie, with each node representing profile for specific 89 // calling context and the context is identified by path from root to the node. 90 class SampleContextTracker { 91 public: 92 SampleContextTracker(StringMap<FunctionSamples> &Profiles); 93 // Query context profile for a specific callee with given name at a given 94 // call-site. The full context is identified by location of call instruction. 95 FunctionSamples *getCalleeContextSamplesFor(const CallBase &Inst, 96 StringRef CalleeName); 97 // Query context profile for a given location. The full context 98 // is identified by input DILocation. 99 FunctionSamples *getContextSamplesFor(const DILocation *DIL); 100 // Query context profile for a given sample contxt of a function. 101 FunctionSamples *getContextSamplesFor(const SampleContext &Context); 102 // Query base profile for a given function. A base profile is a merged view 103 // of all context profiles for contexts that are not inlined. 104 FunctionSamples *getBaseSamplesFor(const Function &Func, 105 bool MergeContext = true); 106 // Query base profile for a given function by name. 107 FunctionSamples *getBaseSamplesFor(StringRef Name, bool MergeContext); 108 // Mark a context profile as inlined when function is inlined. 109 // This makes sure that inlined context profile will be excluded in 110 // function's base profile. 111 void markContextSamplesInlined(const FunctionSamples *InlinedSamples); 112 // Dump the internal context profile trie. 113 void dump(); 114 115 private: 116 ContextTrieNode *getContextFor(const DILocation *DIL); 117 ContextTrieNode *getContextFor(const SampleContext &Context); 118 ContextTrieNode *getCalleeContextFor(const DILocation *DIL, 119 StringRef CalleeName); 120 ContextTrieNode *getOrCreateContextPath(const SampleContext &Context, 121 bool AllowCreate); 122 ContextTrieNode *getTopLevelContextNode(StringRef FName); 123 ContextTrieNode &addTopLevelContextNode(StringRef FName); 124 ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &NodeToPromo); 125 void promoteMergeContextSamplesTree(const Instruction &Inst, 126 StringRef CalleeName); 127 void mergeContextNode(ContextTrieNode &FromNode, ContextTrieNode &ToNode, 128 StringRef ContextStrToRemove); 129 ContextTrieNode &promoteMergeContextSamplesTree(ContextTrieNode &FromNode, 130 ContextTrieNode &ToNodeParent, 131 StringRef ContextStrToRemove); 132 133 // Map from function name to context profiles (excluding base profile) 134 StringMap<SmallSet<FunctionSamples *, 16>> FuncToCtxtProfileSet; 135 136 // Root node for context trie tree 137 ContextTrieNode RootContext; 138 }; 139 140 } // end namespace llvm 141 #endif // LLVM_TRANSFORMS_IPO_SAMPLECONTEXTTRACKER_H 142