LLVM 18.0.0git
ProfiledCallGraph.h
Go to the documentation of this file.
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
13#include "llvm/ADT/StringRef.h"
17#include <queue>
18#include <set>
19
20namespace llvm {
21namespace sampleprof {
22
23struct ProfiledCallGraphNode;
24
32
33 // The call destination is the only important data here,
34 // allow to transparently unwrap into it.
35 operator ProfiledCallGraphNode *() const { return Target; }
36};
37
39
40 // Sort edges by callee names only since all edges to be compared are from
41 // same caller. Edge weights are not considered either because for the same
42 // callee only the edge with the largest weight is added to the edge set.
45 const ProfiledCallGraphEdge &R) const {
46 return L.Target->Name < R.Target->Name;
47 }
48 };
49
51 using edges = std::set<edge, ProfiledCallGraphEdgeComparer>;
52 using iterator = edges::iterator;
53 using const_iterator = edges::const_iterator;
54
56 {}
57
60};
61
63public:
65
66 // Constructor for non-CS profile.
68 uint64_t IgnoreColdCallThreshold = 0) {
70 "CS flat profile is not handled here");
71 for (const auto &Samples : ProfileMap) {
72 addProfiledCalls(Samples.second);
73 }
74
75 // Trim edges with weight up to `IgnoreColdCallThreshold`. This aims
76 // for a more stable call graph with "determinstic" edges from run to run.
77 trimColdEges(IgnoreColdCallThreshold);
78 }
79
80 // Constructor for CS profile.
82 uint64_t IgnoreColdCallThreshold = 0) {
83 // BFS traverse the context profile trie to add call edges for calls shown
84 // in context.
85 std::queue<ContextTrieNode *> Queue;
86 for (auto &Child : ContextTracker.getRootContext().getAllChildContext()) {
87 ContextTrieNode *Callee = &Child.second;
88 addProfiledFunction(Callee->getFuncName());
89 Queue.push(Callee);
90 }
91
92 while (!Queue.empty()) {
93 ContextTrieNode *Caller = Queue.front();
94 Queue.pop();
95 FunctionSamples *CallerSamples = Caller->getFunctionSamples();
96
97 // Add calls for context.
98 // Note that callsite target samples are completely ignored since they can
99 // conflict with the context edges, which are formed by context
100 // compression during profile generation, for cyclic SCCs. This may
101 // further result in an SCC order incompatible with the purely
102 // context-based one, which may in turn block context-based inlining.
103 for (auto &Child : Caller->getAllChildContext()) {
104 ContextTrieNode *Callee = &Child.second;
105 addProfiledFunction(Callee->getFuncName());
106 Queue.push(Callee);
107
108 // Fetch edge weight from the profile.
109 uint64_t Weight;
110 FunctionSamples *CalleeSamples = Callee->getFunctionSamples();
111 if (!CalleeSamples || !CallerSamples) {
112 Weight = 0;
113 } else {
114 uint64_t CalleeEntryCount = CalleeSamples->getHeadSamplesEstimate();
115 uint64_t CallsiteCount = 0;
116 LineLocation Callsite = Callee->getCallSiteLoc();
117 if (auto CallTargets = CallerSamples->findCallTargetMapAt(Callsite)) {
118 SampleRecord::CallTargetMap &TargetCounts = CallTargets.get();
119 auto It = TargetCounts.find(CalleeSamples->getFunction());
120 if (It != TargetCounts.end())
121 CallsiteCount = It->second;
122 }
123 Weight = std::max(CallsiteCount, CalleeEntryCount);
124 }
125
126 addProfiledCall(Caller->getFuncName(), Callee->getFuncName(), Weight);
127 }
128 }
129
130 // Trim edges with weight up to `IgnoreColdCallThreshold`. This aims
131 // for a more stable call graph with "determinstic" edges from run to run.
132 trimColdEges(IgnoreColdCallThreshold);
133 }
134
135 iterator begin() { return Root.Edges.begin(); }
136 iterator end() { return Root.Edges.end(); }
138
140 if (!ProfiledFunctions.count(Name)) {
141 // Link to synthetic root to make sure every node is reachable
142 // from root. This does not affect SCC order.
143 ProfiledFunctions[Name] = ProfiledCallGraphNode(Name);
144 Root.Edges.emplace(&Root, &ProfiledFunctions[Name], 0);
145 }
146 }
147
148private:
149 void addProfiledCall(FunctionId CallerName, FunctionId CalleeName,
150 uint64_t Weight = 0) {
151 assert(ProfiledFunctions.count(CallerName));
152 auto CalleeIt = ProfiledFunctions.find(CalleeName);
153 if (CalleeIt == ProfiledFunctions.end())
154 return;
155 ProfiledCallGraphEdge Edge(&ProfiledFunctions[CallerName],
156 &CalleeIt->second, Weight);
157 auto &Edges = ProfiledFunctions[CallerName].Edges;
158 auto EdgeIt = Edges.find(Edge);
159 if (EdgeIt == Edges.end()) {
160 Edges.insert(Edge);
161 } else {
162 // Accumulate weight to the existing edge.
163 Edge.Weight += EdgeIt->Weight;
164 Edges.erase(EdgeIt);
165 Edges.insert(Edge);
166 }
167 }
168
169 void addProfiledCalls(const FunctionSamples &Samples) {
170 addProfiledFunction(Samples.getFunction());
171
172 for (const auto &Sample : Samples.getBodySamples()) {
173 for (const auto &[Target, Frequency] : Sample.second.getCallTargets()) {
174 addProfiledFunction(Target);
175 addProfiledCall(Samples.getFunction(), Target, Frequency);
176 }
177 }
178
179 for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) {
180 for (const auto &InlinedSamples : CallsiteSamples.second) {
181 addProfiledFunction(InlinedSamples.first);
182 addProfiledCall(Samples.getFunction(), InlinedSamples.first,
183 InlinedSamples.second.getHeadSamplesEstimate());
184 addProfiledCalls(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(I);
201 else
202 I++;
203 }
204 }
205 }
206
207 ProfiledCallGraphNode Root;
208 HashKeyMap<std::unordered_map, FunctionId, ProfiledCallGraphNode>
209 ProfiledFunctions;
210};
211
212} // end namespace sampleprof
213
214template <> struct GraphTraits<ProfiledCallGraphNode *> {
219
220 static NodeRef getEntryNode(NodeRef PCGN) { return PCGN; }
221 static ChildIteratorType child_begin(NodeRef N) { return N->Edges.begin(); }
222 static ChildIteratorType child_end(NodeRef N) { return N->Edges.end(); }
223};
224
225template <>
229 return PCG->getEntryNode();
230 }
231
233 return PCG->begin();
234 }
235
237 return PCG->end();
238 }
239};
240
241} // end namespace llvm
242
243#endif
std::string Name
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file provides the interface for context-sensitive profile tracker used by CSSPGO.
std::map< uint64_t, ContextTrieNode > & getAllChildContext()
Target - Wrapper for Target specific information.
This class represents a function that is read from a sample profile.
Definition: FunctionId.h:36
Representation of the samples collected for a function.
Definition: SampleProf.h:744
ErrorOr< SampleRecord::CallTargetMap > findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const
Returns the call target map collected at a given location.
Definition: SampleProf.h:887
FunctionId getFunction() const
Return the function name.
Definition: SampleProf.h:1069
uint64_t getHeadSamplesEstimate() const
Return an estimate of the sample count of the function entry basic block.
Definition: SampleProf.h:947
ProfiledCallGraphNode * getEntryNode()
ProfiledCallGraphNode::iterator iterator
void addProfiledFunction(FunctionId Name)
ProfiledCallGraph(SampleContextTracker &ContextTracker, uint64_t IgnoreColdCallThreshold=0)
ProfiledCallGraph(SampleProfileMap &ProfileMap, uint64_t IgnoreColdCallThreshold=0)
This class provides operator overloads to the map container using MD5 as the key type,...
Definition: SampleProf.h:1306
std::unordered_map< FunctionId, uint64_t > CallTargetMap
Definition: SampleProf.h:338
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
#define N
static ChildIteratorType child_end(NodeRef N)
static ChildIteratorType child_begin(NodeRef N)
static NodeRef getEntryNode(ProfiledCallGraph *PCG)
static ChildIteratorType nodes_end(ProfiledCallGraph *PCG)
static ChildIteratorType nodes_begin(ProfiledCallGraph *PCG)
Represents the relative location of an instruction.
Definition: SampleProf.h:280
ProfiledCallGraphEdge(ProfiledCallGraphNode *Source, ProfiledCallGraphNode *Target, uint64_t Weight)
bool operator()(const ProfiledCallGraphEdge &L, const ProfiledCallGraphEdge &R) const
ProfiledCallGraphNode(FunctionId FName=FunctionId())
std::set< edge, ProfiledCallGraphEdgeComparer > edges