LLVM 17.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/StringMap.h"
14#include "llvm/ADT/StringRef.h"
18#include <queue>
19#include <set>
20
21namespace llvm {
22namespace sampleprof {
23
24struct ProfiledCallGraphNode;
25
33
34 // The call destination is the only important data here,
35 // allow to transparently unwrap into it.
36 operator ProfiledCallGraphNode *() const { return Target; }
37};
38
40
41 // Sort edges by callee names only since all edges to be compared are from
42 // same caller. Edge weights are not considered either because for the same
43 // callee only the edge with the largest weight is added to the edge set.
46 const ProfiledCallGraphEdge &R) const {
47 return L.Target->Name < R.Target->Name;
48 }
49 };
50
52 using edges = std::set<edge, ProfiledCallGraphEdgeComparer>;
53 using iterator = edges::iterator;
54 using const_iterator = edges::const_iterator;
55
57
60};
61
63public:
65
66 // Constructor for non-CS profile.
69 "CS flat profile is not handled here");
70 for (const auto &Samples : ProfileMap) {
71 addProfiledCalls(Samples.second);
72 }
73 }
74
75 // Constructor for CS profile.
77 // BFS traverse the context profile trie to add call edges for calls shown
78 // in context.
79 std::queue<ContextTrieNode *> Queue;
80 for (auto &Child : ContextTracker.getRootContext().getAllChildContext()) {
81 ContextTrieNode *Callee = &Child.second;
83 Queue.push(Callee);
84 }
85
86 while (!Queue.empty()) {
87 ContextTrieNode *Caller = Queue.front();
88 Queue.pop();
89 FunctionSamples *CallerSamples = Caller->getFunctionSamples();
90
91 // Add calls for context.
92 // Note that callsite target samples are completely ignored since they can
93 // conflict with the context edges, which are formed by context
94 // compression during profile generation, for cyclic SCCs. This may
95 // further result in an SCC order incompatible with the purely
96 // context-based one, which may in turn block context-based inlining.
97 for (auto &Child : Caller->getAllChildContext()) {
98 ContextTrieNode *Callee = &Child.second;
100 Queue.push(Callee);
101
102 // Fetch edge weight from the profile.
103 uint64_t Weight;
104 FunctionSamples *CalleeSamples = Callee->getFunctionSamples();
105 if (!CalleeSamples || !CallerSamples) {
106 Weight = 0;
107 } else {
108 uint64_t CalleeEntryCount = CalleeSamples->getHeadSamplesEstimate();
109 uint64_t CallsiteCount = 0;
110 LineLocation Callsite = Callee->getCallSiteLoc();
111 if (auto CallTargets = CallerSamples->findCallTargetMapAt(Callsite)) {
112 SampleRecord::CallTargetMap &TargetCounts = CallTargets.get();
113 auto It = TargetCounts.find(CalleeSamples->getName());
114 if (It != TargetCounts.end())
115 CallsiteCount = It->second;
116 }
117 Weight = std::max(CallsiteCount, CalleeEntryCount);
118 }
119
120 addProfiledCall(ContextTracker.getFuncNameFor(Caller),
121 ContextTracker.getFuncNameFor(Callee), Weight);
122 }
123 }
124 }
125
126 iterator begin() { return Root.Edges.begin(); }
127 iterator end() { return Root.Edges.end(); }
130 if (!ProfiledFunctions.count(Name)) {
131 // Link to synthetic root to make sure every node is reachable
132 // from root. This does not affect SCC order.
133 ProfiledFunctions[Name] = ProfiledCallGraphNode(Name);
134 Root.Edges.emplace(&Root, &ProfiledFunctions[Name], 0);
135 }
136 }
137
138private:
139 void addProfiledCall(StringRef CallerName, StringRef CalleeName,
140 uint64_t Weight = 0) {
141 assert(ProfiledFunctions.count(CallerName));
142 auto CalleeIt = ProfiledFunctions.find(CalleeName);
143 if (CalleeIt == ProfiledFunctions.end())
144 return;
145 ProfiledCallGraphEdge Edge(&ProfiledFunctions[CallerName],
146 &CalleeIt->second, Weight);
147 auto &Edges = ProfiledFunctions[CallerName].Edges;
148 auto EdgeIt = Edges.find(Edge);
149 if (EdgeIt == Edges.end()) {
150 Edges.insert(Edge);
151 } else if (EdgeIt->Weight < Edge.Weight) {
152 // Replace existing call edges with same target but smaller weight.
153 Edges.erase(EdgeIt);
154 Edges.insert(Edge);
155 }
156 }
157
158 void addProfiledCalls(const FunctionSamples &Samples) {
159 addProfiledFunction(Samples.getFuncName());
160
161 for (const auto &Sample : Samples.getBodySamples()) {
162 for (const auto &[Target, Frequency] : Sample.second.getCallTargets()) {
163 addProfiledFunction(Target);
164 addProfiledCall(Samples.getFuncName(), Target, Frequency);
165 }
166 }
167
168 for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) {
169 for (const auto &InlinedSamples : CallsiteSamples.second) {
170 addProfiledFunction(InlinedSamples.first);
171 addProfiledCall(Samples.getFuncName(), InlinedSamples.first,
172 InlinedSamples.second.getHeadSamplesEstimate());
173 addProfiledCalls(InlinedSamples.second);
174 }
175 }
176 }
177
178 ProfiledCallGraphNode Root;
179 StringMap<ProfiledCallGraphNode> ProfiledFunctions;
180};
181
182} // end namespace sampleprof
183
184template <> struct GraphTraits<ProfiledCallGraphNode *> {
189
190 static NodeRef getEntryNode(NodeRef PCGN) { return PCGN; }
191 static ChildIteratorType child_begin(NodeRef N) { return N->Edges.begin(); }
192 static ChildIteratorType child_end(NodeRef N) { return N->Edges.end(); }
193};
194
195template <>
199 return PCG->getEntryNode();
200 }
201
203 return PCG->begin();
204 }
205
207 return PCG->end();
208 }
209};
210
211} // end namespace llvm
212
213#endif
This file defines the StringMap class.
amdgpu Simplify well known AMD library false FunctionCallee Callee
std::string Name
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
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()
StringRef getFuncNameFor(ContextTrieNode *Node) const
iterator end()
Definition: StringMap.h:204
iterator find(StringRef Key)
Definition: StringMap.h:217
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Target - Wrapper for Target specific information.
Representation of the samples collected for a function.
Definition: SampleProf.h:726
ErrorOr< SampleRecord::CallTargetMap > findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const
Returns the call target map collected at a given location.
Definition: SampleProf.h:847
uint64_t getHeadSamplesEstimate() const
Return an estimate of the sample count of the function entry basic block.
Definition: SampleProf.h:906
StringRef getName() const
Return the function name.
Definition: SampleProf.h:1025
ProfiledCallGraphNode * getEntryNode()
ProfiledCallGraphNode::iterator iterator
ProfiledCallGraph(SampleContextTracker &ContextTracker)
ProfiledCallGraph(SampleProfileMap &ProfileMap)
std::unordered_map< SampleContext, FunctionSamples, SampleContext::Hash > SampleProfileMap
Definition: SampleProf.h:1222
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:283
ProfiledCallGraphEdge(ProfiledCallGraphNode *Source, ProfiledCallGraphNode *Target, uint64_t Weight)
bool operator()(const ProfiledCallGraphEdge &L, const ProfiledCallGraphEdge &R) const
ProfiledCallGraphNode(StringRef FName=StringRef())
std::set< edge, ProfiledCallGraphEdgeComparer > edges