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 { |
25 | 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 { |
43 | 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 | |
54 | 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: 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(Threshold: 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(Name: Callee->getFuncName()); |
88 | Queue.push(x: 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(Name: Callee->getFuncName()); |
105 | Queue.push(x: 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: Callsite)) { |
117 | auto It = CallTargets->find(x: CalleeSamples->getFunction()); |
118 | if (It != CallTargets->end()) |
119 | CallsiteCount = It->second; |
120 | } |
121 | Weight = std::max(a: CallsiteCount, b: CalleeEntryCount); |
122 | } |
123 | |
124 | addProfiledCall(CallerName: Caller->getFuncName(), CalleeName: 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(Threshold: IgnoreColdCallThreshold); |
131 | } |
132 | |
133 | iterator begin() { return Root.Edges.begin(); } |
134 | iterator end() { return Root.Edges.end(); } |
135 | ProfiledCallGraphNode *getEntryNode() { return &Root; } |
136 | |
137 | void addProfiledFunction(FunctionId Name) { |
138 | if (!ProfiledFunctions.count(Key: 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(args: ProfiledCallGraphNode(Name)); |
144 | ProfiledFunctions[Name] = &Node; |
145 | Root.Edges.emplace(args: &Root, args&: ProfiledFunctions[Name], args: 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(Key: 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(x: Edge); |
160 | if (EdgeIt == Edges.end()) { |
161 | Edges.insert(x: Edge); |
162 | } else { |
163 | // Accumulate weight to the existing edge. |
164 | Edge.Weight += EdgeIt->Weight; |
165 | Edges.erase(position: EdgeIt); |
166 | Edges.insert(x: Edge); |
167 | } |
168 | } |
169 | |
170 | void addProfiledCalls(const FunctionSamples &Samples) { |
171 | addProfiledFunction(Name: Samples.getFunction()); |
172 | |
173 | for (const auto &Sample : Samples.getBodySamples()) { |
174 | for (const auto &[Target, Frequency] : Sample.second.getCallTargets()) { |
175 | addProfiledFunction(Name: Target); |
176 | addProfiledCall(CallerName: Samples.getFunction(), CalleeName: Target, Weight: Frequency); |
177 | } |
178 | } |
179 | |
180 | for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) { |
181 | for (const auto &InlinedSamples : CallsiteSamples.second) { |
182 | addProfiledFunction(Name: InlinedSamples.first); |
183 | addProfiledCall(CallerName: Samples.getFunction(), CalleeName: InlinedSamples.first, |
184 | Weight: InlinedSamples.second.getHeadSamplesEstimate()); |
185 | addProfiledCalls(Samples: 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(position: 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 | |