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_TRANSFORMS_IPO_PROFILEDCALLGRAPH_H
10 #define LLVM_TRANSFORMS_IPO_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 
21 using namespace llvm;
22 using namespace sampleprof;
23 
24 namespace llvm {
25 namespace sampleprof {
26 
27 struct ProfiledCallGraphNode;
28 
29 struct ProfiledCallGraphEdge {
30   ProfiledCallGraphEdge(ProfiledCallGraphNode *Source,
31                         ProfiledCallGraphNode *Target, uint64_t Weight)
32       : Source(Source), Target(Target), Weight(Weight) {}
33   ProfiledCallGraphNode *Source;
34   ProfiledCallGraphNode *Target;
35   uint64_t Weight;
36 
37   // The call destination is the only important data here,
38   // allow to transparently unwrap into it.
39   operator ProfiledCallGraphNode *() const { return Target; }
40 };
41 
42 struct ProfiledCallGraphNode {
43 
44   // Sort edges by callee names only since all edges to be compared are from
45   // same caller. Edge weights are not considered either because for the same
46   // callee only the edge with the largest weight is added to the edge set.
47   struct ProfiledCallGraphEdgeComparer {
48     bool operator()(const ProfiledCallGraphEdge &L,
49                     const ProfiledCallGraphEdge &R) const {
50       return L.Target->Name < R.Target->Name;
51     }
52   };
53 
54   using iterator = std::set<ProfiledCallGraphEdge>::iterator;
55   using const_iterator = std::set<ProfiledCallGraphEdge>::const_iterator;
56   using edge = ProfiledCallGraphEdge;
57   using edges = std::set<ProfiledCallGraphEdge, ProfiledCallGraphEdgeComparer>;
58 
59   ProfiledCallGraphNode(StringRef FName = StringRef()) : Name(FName) {}
60 
61   StringRef Name;
62   edges Edges;
63 };
64 
65 class ProfiledCallGraph {
66 public:
67   using iterator = std::set<ProfiledCallGraphEdge>::iterator;
68 
69   // Constructor for non-CS profile.
70   ProfiledCallGraph(SampleProfileMap &ProfileMap) {
71     assert(!FunctionSamples::ProfileIsCSFlat &&
72            "CS flat profile is not handled here");
73     for (const auto &Samples : ProfileMap) {
74       addProfiledCalls(Samples.second);
75     }
76   }
77 
78   // Constructor for CS profile.
79   ProfiledCallGraph(SampleContextTracker &ContextTracker) {
80     // BFS traverse the context profile trie to add call edges for calls shown
81     // in context.
82     std::queue<ContextTrieNode *> Queue;
83     for (auto &Child : ContextTracker.getRootContext().getAllChildContext()) {
84       ContextTrieNode *Callee = &Child.second;
85       addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
86       Queue.push(Callee);
87     }
88 
89     while (!Queue.empty()) {
90       ContextTrieNode *Caller = Queue.front();
91       Queue.pop();
92       FunctionSamples *CallerSamples = Caller->getFunctionSamples();
93 
94       // Add calls for context.
95       // Note that callsite target samples are completely ignored since they can
96       // conflict with the context edges, which are formed by context
97       // compression during profile generation, for cyclic SCCs. This may
98       // further result in an SCC order incompatible with the purely
99       // context-based one, which may in turn block context-based inlining.
100       for (auto &Child : Caller->getAllChildContext()) {
101         ContextTrieNode *Callee = &Child.second;
102         addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
103         Queue.push(Callee);
104 
105         // Fetch edge weight from the profile.
106         uint64_t Weight;
107         FunctionSamples *CalleeSamples = Callee->getFunctionSamples();
108         if (!CalleeSamples || !CallerSamples) {
109           Weight = 0;
110         } else {
111           uint64_t CalleeEntryCount = CalleeSamples->getEntrySamples();
112           uint64_t CallsiteCount = 0;
113           LineLocation Callsite = Callee->getCallSiteLoc();
114           if (auto CallTargets = CallerSamples->findCallTargetMapAt(Callsite)) {
115             SampleRecord::CallTargetMap &TargetCounts = CallTargets.get();
116             auto It = TargetCounts.find(CalleeSamples->getName());
117             if (It != TargetCounts.end())
118               CallsiteCount = It->second;
119           }
120           Weight = std::max(CallsiteCount, CalleeEntryCount);
121         }
122 
123         addProfiledCall(ContextTracker.getFuncNameFor(Caller),
124                         ContextTracker.getFuncNameFor(Callee), Weight);
125       }
126     }
127   }
128 
129   iterator begin() { return Root.Edges.begin(); }
130   iterator end() { return Root.Edges.end(); }
131   ProfiledCallGraphNode *getEntryNode() { return &Root; }
132   void addProfiledFunction(StringRef Name) {
133     if (!ProfiledFunctions.count(Name)) {
134       // Link to synthetic root to make sure every node is reachable
135       // from root. This does not affect SCC order.
136       ProfiledFunctions[Name] = ProfiledCallGraphNode(Name);
137       Root.Edges.emplace(&Root, &ProfiledFunctions[Name], 0);
138     }
139   }
140 
141 private:
142   void addProfiledCall(StringRef CallerName, StringRef CalleeName,
143                        uint64_t Weight = 0) {
144     assert(ProfiledFunctions.count(CallerName));
145     auto CalleeIt = ProfiledFunctions.find(CalleeName);
146     if (CalleeIt == ProfiledFunctions.end())
147       return;
148     ProfiledCallGraphEdge Edge(&ProfiledFunctions[CallerName],
149                                &CalleeIt->second, Weight);
150     auto &Edges = ProfiledFunctions[CallerName].Edges;
151     auto EdgeIt = Edges.find(Edge);
152     if (EdgeIt == Edges.end()) {
153       Edges.insert(Edge);
154     } else if (EdgeIt->Weight < Edge.Weight) {
155       // Replace existing call edges with same target but smaller weight.
156       Edges.erase(EdgeIt);
157       Edges.insert(Edge);
158     }
159   }
160 
161   void addProfiledCalls(const FunctionSamples &Samples) {
162     addProfiledFunction(Samples.getFuncName());
163 
164     for (const auto &Sample : Samples.getBodySamples()) {
165       for (const auto &Target : Sample.second.getCallTargets()) {
166         addProfiledFunction(Target.first());
167         addProfiledCall(Samples.getFuncName(), Target.first(), Target.second);
168       }
169     }
170 
171     for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) {
172       for (const auto &InlinedSamples : CallsiteSamples.second) {
173         addProfiledFunction(InlinedSamples.first);
174         addProfiledCall(Samples.getFuncName(), InlinedSamples.first,
175                         InlinedSamples.second.getEntrySamples());
176         addProfiledCalls(InlinedSamples.second);
177       }
178     }
179   }
180 
181   ProfiledCallGraphNode Root;
182   StringMap<ProfiledCallGraphNode> ProfiledFunctions;
183 };
184 
185 } // end namespace sampleprof
186 
187 template <> struct GraphTraits<ProfiledCallGraphNode *> {
188   using NodeType = ProfiledCallGraphNode;
189   using NodeRef = ProfiledCallGraphNode *;
190   using EdgeType = NodeType::edge;
191   using ChildIteratorType = NodeType::const_iterator;
192 
193   static NodeRef getEntryNode(NodeRef PCGN) { return PCGN; }
194   static ChildIteratorType child_begin(NodeRef N) { return N->Edges.begin(); }
195   static ChildIteratorType child_end(NodeRef N) { return N->Edges.end(); }
196 };
197 
198 template <>
199 struct GraphTraits<ProfiledCallGraph *>
200     : public GraphTraits<ProfiledCallGraphNode *> {
201   static NodeRef getEntryNode(ProfiledCallGraph *PCG) {
202     return PCG->getEntryNode();
203   }
204 
205   static ChildIteratorType nodes_begin(ProfiledCallGraph *PCG) {
206     return PCG->begin();
207   }
208 
209   static ChildIteratorType nodes_end(ProfiledCallGraph *PCG) {
210     return PCG->end();
211   }
212 };
213 
214 } // end namespace llvm
215 
216 #endif
217