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/ProfileData/SampleProf.h"
14 #include "llvm/ProfileData/SampleProfReader.h"
15 #include "llvm/Transforms/IPO/SampleContextTracker.h"
16 #include <queue>
17 #include <set>
18 
19 namespace llvm {
20 namespace sampleprof {
21 
22 struct ProfiledCallGraphNode;
23 
24 struct ProfiledCallGraphEdge {
ProfiledCallGraphEdgeProfiledCallGraphEdge25   ProfiledCallGraphEdge(ProfiledCallGraphNode *Source,
26                         ProfiledCallGraphNode *Target, uint64_t Weight)
27       : Source(Source), Target(Target), Weight(Weight) {}
28   ProfiledCallGraphNode *Source;
29   ProfiledCallGraphNode *Target;
30   uint64_t Weight;
31 
32   // The call destination is the only important data here,
33   // allow to transparently unwrap into it.
34   operator ProfiledCallGraphNode *() const { return Target; }
35 };
36 
37 struct ProfiledCallGraphNode {
38 
39   // Sort edges by callee names only since all edges to be compared are from
40   // same caller. Edge weights are not considered either because for the same
41   // callee only the edge with the largest weight is added to the edge set.
42   struct ProfiledCallGraphEdgeComparer {
operatorProfiledCallGraphNode::ProfiledCallGraphEdgeComparer43     bool operator()(const ProfiledCallGraphEdge &L,
44                     const ProfiledCallGraphEdge &R) const {
45       return L.Target->Name < R.Target->Name;
46     }
47   };
48 
49   using edge = ProfiledCallGraphEdge;
50   using edges = std::set<edge, ProfiledCallGraphEdgeComparer>;
51   using iterator = edges::iterator;
52   using const_iterator = edges::const_iterator;
53 
NameProfiledCallGraphNode54   ProfiledCallGraphNode(FunctionId FName = FunctionId()) : Name(FName)
55   {}
56 
57   FunctionId Name;
58   edges Edges;
59 };
60 
61 class ProfiledCallGraph {
62 public:
63   using iterator = ProfiledCallGraphNode::iterator;
64 
65   // Constructor for non-CS profile.
66   ProfiledCallGraph(SampleProfileMap &ProfileMap,
67                     uint64_t IgnoreColdCallThreshold = 0) {
68     assert(!FunctionSamples::ProfileIsCS &&
69            "CS flat profile is not handled here");
70     for (const auto &Samples : ProfileMap) {
71       addProfiledCalls(Samples.second);
72     }
73 
74     // Trim edges with weight up to `IgnoreColdCallThreshold`. This aims
75     // for a more stable call graph with "determinstic" edges from run to run.
76     trimColdEges(IgnoreColdCallThreshold);
77   }
78 
79   // Constructor for CS profile.
80   ProfiledCallGraph(SampleContextTracker &ContextTracker,
81                     uint64_t IgnoreColdCallThreshold = 0) {
82     // BFS traverse the context profile trie to add call edges for calls shown
83     // in context.
84     std::queue<ContextTrieNode *> Queue;
85     for (auto &Child : ContextTracker.getRootContext().getAllChildContext()) {
86       ContextTrieNode *Callee = &Child.second;
87       addProfiledFunction(Callee->getFuncName());
88       Queue.push(Callee);
89     }
90 
91     while (!Queue.empty()) {
92       ContextTrieNode *Caller = Queue.front();
93       Queue.pop();
94       FunctionSamples *CallerSamples = Caller->getFunctionSamples();
95 
96       // Add calls for context.
97       // Note that callsite target samples are completely ignored since they can
98       // conflict with the context edges, which are formed by context
99       // compression during profile generation, for cyclic SCCs. This may
100       // further result in an SCC order incompatible with the purely
101       // context-based one, which may in turn block context-based inlining.
102       for (auto &Child : Caller->getAllChildContext()) {
103         ContextTrieNode *Callee = &Child.second;
104         addProfiledFunction(Callee->getFuncName());
105         Queue.push(Callee);
106 
107         // Fetch edge weight from the profile.
108         uint64_t Weight;
109         FunctionSamples *CalleeSamples = Callee->getFunctionSamples();
110         if (!CalleeSamples || !CallerSamples) {
111           Weight = 0;
112         } else {
113           uint64_t CalleeEntryCount = CalleeSamples->getHeadSamplesEstimate();
114           uint64_t CallsiteCount = 0;
115           LineLocation Callsite = Callee->getCallSiteLoc();
116           if (auto CallTargets = CallerSamples->findCallTargetMapAt(Callsite)) {
117             auto It = CallTargets->find(CalleeSamples->getFunction());
118             if (It != CallTargets->end())
119               CallsiteCount = It->second;
120           }
121           Weight = std::max(CallsiteCount, CalleeEntryCount);
122         }
123 
124         addProfiledCall(Caller->getFuncName(), Callee->getFuncName(), Weight);
125       }
126     }
127 
128     // Trim edges with weight up to `IgnoreColdCallThreshold`. This aims
129     // for a more stable call graph with "determinstic" edges from run to run.
130     trimColdEges(IgnoreColdCallThreshold);
131   }
132 
begin()133   iterator begin() { return Root.Edges.begin(); }
end()134   iterator end() { return Root.Edges.end(); }
getEntryNode()135   ProfiledCallGraphNode *getEntryNode() { return &Root; }
136 
addProfiledFunction(FunctionId Name)137   void addProfiledFunction(FunctionId Name) {
138     if (!ProfiledFunctions.count(Name)) {
139       // Link to synthetic root to make sure every node is reachable
140       // from root. This does not affect SCC order.
141       // Store the pointer of the node because the map can be rehashed.
142       auto &Node =
143           ProfiledCallGraphNodeList.emplace_back(ProfiledCallGraphNode(Name));
144       ProfiledFunctions[Name] = &Node;
145       Root.Edges.emplace(&Root, ProfiledFunctions[Name], 0);
146     }
147   }
148 
149 private:
150   void addProfiledCall(FunctionId CallerName, FunctionId CalleeName,
151                        uint64_t Weight = 0) {
152     assert(ProfiledFunctions.count(CallerName));
153     auto CalleeIt = ProfiledFunctions.find(CalleeName);
154     if (CalleeIt == ProfiledFunctions.end())
155       return;
156     ProfiledCallGraphEdge Edge(ProfiledFunctions[CallerName],
157                                CalleeIt->second, Weight);
158     auto &Edges = ProfiledFunctions[CallerName]->Edges;
159     auto EdgeIt = Edges.find(Edge);
160     if (EdgeIt == Edges.end()) {
161       Edges.insert(Edge);
162     } else {
163       // Accumulate weight to the existing edge.
164       Edge.Weight += EdgeIt->Weight;
165       Edges.erase(EdgeIt);
166       Edges.insert(Edge);
167     }
168   }
169 
addProfiledCalls(const FunctionSamples & Samples)170   void addProfiledCalls(const FunctionSamples &Samples) {
171     addProfiledFunction(Samples.getFunction());
172 
173     for (const auto &Sample : Samples.getBodySamples()) {
174       for (const auto &[Target, Frequency] : Sample.second.getCallTargets()) {
175         addProfiledFunction(Target);
176         addProfiledCall(Samples.getFunction(), Target, Frequency);
177       }
178     }
179 
180     for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) {
181       for (const auto &InlinedSamples : CallsiteSamples.second) {
182         addProfiledFunction(InlinedSamples.first);
183         addProfiledCall(Samples.getFunction(), InlinedSamples.first,
184                         InlinedSamples.second.getHeadSamplesEstimate());
185         addProfiledCalls(InlinedSamples.second);
186       }
187     }
188   }
189 
190   // Trim edges with weight up to `Threshold`. Do not trim anything if
191   // `Threshold` is zero.
192   void trimColdEges(uint64_t Threshold = 0) {
193     if (!Threshold)
194       return;
195 
196     for (auto &Node : ProfiledFunctions) {
197       auto &Edges = Node.second->Edges;
198       auto I = Edges.begin();
199       while (I != Edges.end()) {
200         if (I->Weight <= Threshold)
201           I = Edges.erase(I);
202         else
203           I++;
204       }
205     }
206   }
207 
208   ProfiledCallGraphNode Root;
209   // backing buffer for ProfiledCallGraphNodes.
210   std::list<ProfiledCallGraphNode> ProfiledCallGraphNodeList;
211   HashKeyMap<llvm::DenseMap, FunctionId, ProfiledCallGraphNode*>
212       ProfiledFunctions;
213 };
214 
215 } // end namespace sampleprof
216 
217 template <> struct GraphTraits<ProfiledCallGraphNode *> {
218   using NodeType = ProfiledCallGraphNode;
219   using NodeRef = ProfiledCallGraphNode *;
220   using EdgeType = NodeType::edge;
221   using ChildIteratorType = NodeType::const_iterator;
222 
223   static NodeRef getEntryNode(NodeRef PCGN) { return PCGN; }
224   static ChildIteratorType child_begin(NodeRef N) { return N->Edges.begin(); }
225   static ChildIteratorType child_end(NodeRef N) { return N->Edges.end(); }
226 };
227 
228 template <>
229 struct GraphTraits<ProfiledCallGraph *>
230     : public GraphTraits<ProfiledCallGraphNode *> {
231   static NodeRef getEntryNode(ProfiledCallGraph *PCG) {
232     return PCG->getEntryNode();
233   }
234 
235   static ChildIteratorType nodes_begin(ProfiledCallGraph *PCG) {
236     return PCG->begin();
237   }
238 
239   static ChildIteratorType nodes_end(ProfiledCallGraph *PCG) {
240     return PCG->end();
241   }
242 };
243 
244 } // end namespace llvm
245 
246 #endif
247