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 auto [It, Inserted] = ProfiledFunctions.try_emplace(Key: Name);
139 if (Inserted) {
140 // Link to synthetic root to make sure every node is reachable
141 // from root. This does not affect SCC order.
142 // Store the pointer of the node because the map can be rehashed.
143 auto &Node =
144 ProfiledCallGraphNodeList.emplace_back(args: ProfiledCallGraphNode(Name));
145 It->second = &Node;
146 Root.Edges.emplace(args: &Root, args&: It->second, args: 0);
147 }
148 }
149
150private:
151 void addProfiledCall(FunctionId CallerName, FunctionId CalleeName,
152 uint64_t Weight = 0) {
153 auto CalleeIt = ProfiledFunctions.find(Key: CalleeName);
154 if (CalleeIt == ProfiledFunctions.end())
155 return;
156 auto CallerIt = ProfiledFunctions.find(Key: CallerName);
157 assert(CallerIt != ProfiledFunctions.end());
158 ProfiledCallGraphEdge Edge(CallerIt->second, CalleeIt->second, Weight);
159 auto &Edges = CallerIt->second->Edges;
160 auto [EdgeIt, Inserted] = Edges.insert(x: Edge);
161 if (!Inserted) {
162 // Accumulate weight to the existing edge.
163 Edge.Weight += EdgeIt->Weight;
164 Edges.erase(position: EdgeIt);
165 Edges.insert(x: Edge);
166 }
167 }
168
169 void addProfiledCalls(const FunctionSamples &Samples) {
170 addProfiledFunction(Name: Samples.getFunction());
171
172 for (const auto &Sample : Samples.getBodySamples()) {
173 for (const auto &[Target, Frequency] : Sample.second.getCallTargets()) {
174 addProfiledFunction(Name: Target);
175 addProfiledCall(CallerName: Samples.getFunction(), CalleeName: Target, Weight: Frequency);
176 }
177 }
178
179 for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) {
180 for (const auto &InlinedSamples : CallsiteSamples.second) {
181 addProfiledFunction(Name: InlinedSamples.first);
182 addProfiledCall(CallerName: Samples.getFunction(), CalleeName: InlinedSamples.first,
183 Weight: InlinedSamples.second.getHeadSamplesEstimate());
184 addProfiledCalls(Samples: InlinedSamples.second);
185 }
186 }
187 }
188
189 // Trim edges with weight up to `Threshold`. Do not trim anything if
190 // `Threshold` is zero.
191 void trimColdEges(uint64_t Threshold = 0) {
192 if (!Threshold)
193 return;
194
195 for (auto &Node : ProfiledFunctions) {
196 auto &Edges = Node.second->Edges;
197 auto I = Edges.begin();
198 while (I != Edges.end()) {
199 if (I->Weight <= Threshold)
200 I = Edges.erase(position: I);
201 else
202 I++;
203 }
204 }
205 }
206
207 ProfiledCallGraphNode Root;
208 // backing buffer for ProfiledCallGraphNodes.
209 std::list<ProfiledCallGraphNode> ProfiledCallGraphNodeList;
210 HashKeyMap<llvm::DenseMap, FunctionId, ProfiledCallGraphNode*>
211 ProfiledFunctions;
212};
213
214} // end namespace sampleprof
215
216template <> struct GraphTraits<ProfiledCallGraphNode *> {
217 using NodeType = ProfiledCallGraphNode;
218 using NodeRef = ProfiledCallGraphNode *;
219 using EdgeType = NodeType::edge;
220 using ChildIteratorType = NodeType::const_iterator;
221
222 static NodeRef getEntryNode(NodeRef PCGN) { return PCGN; }
223 static ChildIteratorType child_begin(NodeRef N) { return N->Edges.begin(); }
224 static ChildIteratorType child_end(NodeRef N) { return N->Edges.end(); }
225};
226
227template <>
228struct GraphTraits<ProfiledCallGraph *>
229 : public GraphTraits<ProfiledCallGraphNode *> {
230 static NodeRef getEntryNode(ProfiledCallGraph *PCG) {
231 return PCG->getEntryNode();
232 }
233
234 static ChildIteratorType nodes_begin(ProfiledCallGraph *PCG) {
235 return PCG->begin();
236 }
237
238 static ChildIteratorType nodes_end(ProfiledCallGraph *PCG) {
239 return PCG->end();
240 }
241};
242
243} // end namespace llvm
244
245#endif
246