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
19namespace llvm {
20namespace sampleprof {
21
22struct ProfiledCallGraphNode;
23
24struct 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
37struct 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
61class ProfiledCallGraph {
62public:
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
149private:
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
217template <> 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
228template <>
229struct 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

source code of llvm/include/llvm/Transforms/IPO/ProfiledCallGraph.h