1 //===-- ProfiledCallGraph.h - Profiled Call Graph ----------------- 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 #ifndef LLVM_TOOLS_LLVM_PROFGEN_PROFILEDCALLGRAPH_H 10 #define LLVM_TOOLS_LLVM_PROFGEN_PROFILEDCALLGRAPH_H 11 12 #include "llvm/ADT/GraphTraits.h" 13 #include "llvm/ADT/StringMap.h" 14 #include "llvm/ADT/StringRef.h" 15 #include "llvm/ProfileData/SampleProf.h" 16 #include "llvm/ProfileData/SampleProfReader.h" 17 #include "llvm/Transforms/IPO/SampleContextTracker.h" 18 #include <queue> 19 #include <set> 20 #include <string> 21 22 using namespace llvm; 23 using namespace sampleprof; 24 25 namespace llvm { 26 namespace sampleprof { 27 28 struct ProfiledCallGraphNode { NameProfiledCallGraphNode29 ProfiledCallGraphNode(StringRef FName = StringRef()) : Name(FName) {} 30 StringRef Name; 31 32 struct ProfiledCallGraphNodeComparer { operatorProfiledCallGraphNode::ProfiledCallGraphNodeComparer33 bool operator()(const ProfiledCallGraphNode *L, 34 const ProfiledCallGraphNode *R) const { 35 return L->Name < R->Name; 36 } 37 }; 38 std::set<ProfiledCallGraphNode *, ProfiledCallGraphNodeComparer> Callees; 39 }; 40 41 class ProfiledCallGraph { 42 public: 43 using iterator = std::set<ProfiledCallGraphNode *>::iterator; 44 45 // Constructor for non-CS profile. ProfiledCallGraph(StringMap<FunctionSamples> & ProfileMap)46 ProfiledCallGraph(StringMap<FunctionSamples> &ProfileMap) { 47 assert(!FunctionSamples::ProfileIsCS && "CS profile is not handled here"); 48 for (const auto &Samples : ProfileMap) { 49 addProfiledCalls(Samples.second); 50 } 51 } 52 53 // Constructor for CS profile. ProfiledCallGraph(SampleContextTracker & ContextTracker)54 ProfiledCallGraph(SampleContextTracker &ContextTracker) { 55 // BFS traverse the context profile trie to add call edges for calls shown 56 // in context. 57 std::queue<ContextTrieNode *> Queue; 58 for (auto &Child : ContextTracker.getRootContext().getAllChildContext()) { 59 ContextTrieNode *Callee = &Child.second; 60 addProfiledFunction(Callee->getFuncName()); 61 Queue.push(Callee); 62 } 63 64 while (!Queue.empty()) { 65 ContextTrieNode *Caller = Queue.front(); 66 Queue.pop(); 67 // Add calls for context. When AddNodeWithSamplesOnly is true, both caller 68 // and callee need to have context profile. 69 // Note that callsite target samples are completely ignored since they can 70 // conflict with the context edges, which are formed by context 71 // compression during profile generation, for cyclic SCCs. This may 72 // further result in an SCC order incompatible with the purely 73 // context-based one, which may in turn block context-based inlining. 74 for (auto &Child : Caller->getAllChildContext()) { 75 ContextTrieNode *Callee = &Child.second; 76 addProfiledFunction(Callee->getFuncName()); 77 Queue.push(Callee); 78 addProfiledCall(Caller->getFuncName(), Callee->getFuncName()); 79 } 80 } 81 } 82 begin()83 iterator begin() { return Root.Callees.begin(); } end()84 iterator end() { return Root.Callees.end(); } getEntryNode()85 ProfiledCallGraphNode *getEntryNode() { return &Root; } addProfiledFunction(StringRef Name)86 void addProfiledFunction(StringRef Name) { 87 if (!ProfiledFunctions.count(Name)) { 88 // Link to synthetic root to make sure every node is reachable 89 // from root. This does not affect SCC order. 90 ProfiledFunctions[Name] = ProfiledCallGraphNode(Name); 91 Root.Callees.insert(&ProfiledFunctions[Name]); 92 } 93 } 94 addProfiledCall(StringRef CallerName,StringRef CalleeName)95 void addProfiledCall(StringRef CallerName, StringRef CalleeName) { 96 assert(ProfiledFunctions.count(CallerName)); 97 auto CalleeIt = ProfiledFunctions.find(CalleeName); 98 if (CalleeIt == ProfiledFunctions.end()) { 99 return; 100 } 101 ProfiledFunctions[CallerName].Callees.insert(&CalleeIt->second); 102 } 103 addProfiledCalls(const FunctionSamples & Samples)104 void addProfiledCalls(const FunctionSamples &Samples) { 105 addProfiledFunction(Samples.getFuncName()); 106 107 for (const auto &Sample : Samples.getBodySamples()) { 108 for (const auto &Target : Sample.second.getCallTargets()) { 109 addProfiledFunction(Target.first()); 110 addProfiledCall(Samples.getFuncName(), Target.first()); 111 } 112 } 113 114 for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) { 115 for (const auto &InlinedSamples : CallsiteSamples.second) { 116 addProfiledFunction(InlinedSamples.first); 117 addProfiledCall(Samples.getFuncName(), InlinedSamples.first); 118 addProfiledCalls(InlinedSamples.second); 119 } 120 } 121 } 122 123 private: 124 ProfiledCallGraphNode Root; 125 StringMap<ProfiledCallGraphNode> ProfiledFunctions; 126 }; 127 128 } // end namespace sampleprof 129 130 template <> struct GraphTraits<ProfiledCallGraphNode *> { 131 using NodeRef = ProfiledCallGraphNode *; 132 using ChildIteratorType = std::set<ProfiledCallGraphNode *>::iterator; 133 134 static NodeRef getEntryNode(NodeRef PCGN) { return PCGN; } 135 static ChildIteratorType child_begin(NodeRef N) { return N->Callees.begin(); } 136 static ChildIteratorType child_end(NodeRef N) { return N->Callees.end(); } 137 }; 138 139 template <> 140 struct GraphTraits<ProfiledCallGraph *> 141 : public GraphTraits<ProfiledCallGraphNode *> { 142 static NodeRef getEntryNode(ProfiledCallGraph *PCG) { 143 return PCG->getEntryNode(); 144 } 145 146 static ChildIteratorType nodes_begin(ProfiledCallGraph *PCG) { 147 return PCG->begin(); 148 } 149 150 static ChildIteratorType nodes_end(ProfiledCallGraph *PCG) { 151 return PCG->end(); 152 } 153 }; 154 155 } // end namespace llvm 156 157 #endif 158