LLVM  14.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 
12 #include "llvm/ADT/GraphTraits.h"
13 #include "llvm/ADT/StringMap.h"
14 #include "llvm/ADT/StringRef.h"
18 #include <queue>
19 #include <set>
20 
21 using namespace llvm;
22 using namespace sampleprof;
23 
24 namespace llvm {
25 namespace sampleprof {
26 
28 
32  : Source(Source), Target(Target), Weight(Weight) {}
36 
37  // The call destination is the only important data here,
38  // allow to transparently unwrap into it.
39  operator ProfiledCallGraphNode *() const { return Target; }
40 };
41 
43 
44  // Sort edges by callee names only since all edges to be compared are from
45  // same caller. Edge weights are not considered either because for the same
46  // callee only the edge with the largest weight is added to the edge set.
49  const ProfiledCallGraphEdge &R) const {
50  return L.Target->Name < R.Target->Name;
51  }
52  };
53 
54  using iterator = std::set<ProfiledCallGraphEdge>::iterator;
55  using const_iterator = std::set<ProfiledCallGraphEdge>::const_iterator;
57  using edges = std::set<ProfiledCallGraphEdge, ProfiledCallGraphEdgeComparer>;
58 
60 
63 };
64 
66 public:
67  using iterator = std::set<ProfiledCallGraphEdge>::iterator;
68 
69  // Constructor for non-CS profile.
72  "CS flat profile is not handled here");
73  for (const auto &Samples : ProfileMap) {
74  addProfiledCalls(Samples.second);
75  }
76  }
77 
78  // Constructor for CS profile.
80  // BFS traverse the context profile trie to add call edges for calls shown
81  // in context.
82  std::queue<ContextTrieNode *> Queue;
83  for (auto &Child : ContextTracker.getRootContext().getAllChildContext()) {
84  ContextTrieNode *Callee = &Child.second;
85  addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
86  Queue.push(Callee);
87  }
88 
89  while (!Queue.empty()) {
90  ContextTrieNode *Caller = Queue.front();
91  Queue.pop();
92  FunctionSamples *CallerSamples = Caller->getFunctionSamples();
93 
94  // Add calls for context.
95  // Note that callsite target samples are completely ignored since they can
96  // conflict with the context edges, which are formed by context
97  // compression during profile generation, for cyclic SCCs. This may
98  // further result in an SCC order incompatible with the purely
99  // context-based one, which may in turn block context-based inlining.
100  for (auto &Child : Caller->getAllChildContext()) {
101  ContextTrieNode *Callee = &Child.second;
102  addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
103  Queue.push(Callee);
104 
105  // Fetch edge weight from the profile.
106  uint64_t Weight;
107  FunctionSamples *CalleeSamples = Callee->getFunctionSamples();
108  if (!CalleeSamples || !CallerSamples) {
109  Weight = 0;
110  } else {
111  uint64_t CalleeEntryCount = CalleeSamples->getEntrySamples();
112  uint64_t CallsiteCount = 0;
113  LineLocation Callsite = Callee->getCallSiteLoc();
114  if (auto CallTargets = CallerSamples->findCallTargetMapAt(Callsite)) {
115  SampleRecord::CallTargetMap &TargetCounts = CallTargets.get();
116  auto It = TargetCounts.find(CalleeSamples->getName());
117  if (It != TargetCounts.end())
118  CallsiteCount = It->second;
119  }
120  Weight = std::max(CallsiteCount, CalleeEntryCount);
121  }
122 
123  addProfiledCall(ContextTracker.getFuncNameFor(Caller),
124  ContextTracker.getFuncNameFor(Callee), Weight);
125  }
126  }
127  }
128 
129  iterator begin() { return Root.Edges.begin(); }
130  iterator end() { return Root.Edges.end(); }
131  ProfiledCallGraphNode *getEntryNode() { return &Root; }
133  if (!ProfiledFunctions.count(Name)) {
134  // Link to synthetic root to make sure every node is reachable
135  // from root. This does not affect SCC order.
136  ProfiledFunctions[Name] = ProfiledCallGraphNode(Name);
137  Root.Edges.emplace(&Root, &ProfiledFunctions[Name], 0);
138  }
139  }
140 
141 private:
142  void addProfiledCall(StringRef CallerName, StringRef CalleeName,
143  uint64_t Weight = 0) {
144  assert(ProfiledFunctions.count(CallerName));
145  auto CalleeIt = ProfiledFunctions.find(CalleeName);
146  if (CalleeIt == ProfiledFunctions.end())
147  return;
148  ProfiledCallGraphEdge Edge(&ProfiledFunctions[CallerName],
149  &CalleeIt->second, Weight);
150  auto &Edges = ProfiledFunctions[CallerName].Edges;
151  auto EdgeIt = Edges.find(Edge);
152  if (EdgeIt == Edges.end()) {
153  Edges.insert(Edge);
154  } else if (EdgeIt->Weight < Edge.Weight) {
155  // Replace existing call edges with same target but smaller weight.
156  Edges.erase(EdgeIt);
157  Edges.insert(Edge);
158  }
159  }
160 
161  void addProfiledCalls(const FunctionSamples &Samples) {
162  addProfiledFunction(Samples.getFuncName());
163 
164  for (const auto &Sample : Samples.getBodySamples()) {
165  for (const auto &Target : Sample.second.getCallTargets()) {
166  addProfiledFunction(Target.first());
167  addProfiledCall(Samples.getFuncName(), Target.first(), Target.second);
168  }
169  }
170 
171  for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) {
172  for (const auto &InlinedSamples : CallsiteSamples.second) {
173  addProfiledFunction(InlinedSamples.first);
174  addProfiledCall(Samples.getFuncName(), InlinedSamples.first,
175  InlinedSamples.second.getEntrySamples());
176  addProfiledCalls(InlinedSamples.second);
177  }
178  }
179  }
180 
182  StringMap<ProfiledCallGraphNode> ProfiledFunctions;
183 };
184 
185 } // end namespace sampleprof
186 
187 template <> struct GraphTraits<ProfiledCallGraphNode *> {
192 
193  static NodeRef getEntryNode(NodeRef PCGN) { return PCGN; }
194  static ChildIteratorType child_begin(NodeRef N) { return N->Edges.begin(); }
195  static ChildIteratorType child_end(NodeRef N) { return N->Edges.end(); }
196 };
197 
198 template <>
202  return PCG->getEntryNode();
203  }
204 
206  return PCG->begin();
207  }
208 
210  return PCG->end();
211  }
212 };
213 
214 } // end namespace llvm
215 
216 #endif
llvm::sampleprof::FunctionSamples::getBodySamples
const BodySampleMap & getBodySamples() const
Return all the samples collected in the body of the function.
Definition: SampleProf.h:855
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::SampleContextTracker::getFuncNameFor
StringRef getFuncNameFor(ContextTrieNode *Node) const
Definition: SampleContextTracker.cpp:421
llvm::GraphTraits< ProfiledCallGraphNode * >::getEntryNode
static NodeRef getEntryNode(NodeRef PCGN)
Definition: ProfiledCallGraph.h:193
llvm::sampleprof::ProfiledCallGraph::ProfiledCallGraph
ProfiledCallGraph(SampleProfileMap &ProfileMap)
Definition: ProfiledCallGraph.h:70
StringRef.h
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:137
llvm::sampleprof::SampleProfileMap
std::unordered_map< SampleContext, FunctionSamples, SampleContext::Hash > SampleProfileMap
Definition: SampleProf.h:1130
llvm::StringMap::end
iterator end()
Definition: StringMap.h:203
llvm::sampleprof::ProfiledCallGraph::begin
iterator begin()
Definition: ProfiledCallGraph.h:129
llvm::AMDGPU::Exp::Target
Target
Definition: SIDefines.h:745
llvm::sampleprof::FunctionSamples::getName
StringRef getName() const
Return the function name.
Definition: SampleProf.h:946
llvm::sampleprof::ProfiledCallGraphEdge::Target
ProfiledCallGraphNode * Target
Definition: ProfiledCallGraph.h:34
llvm::StringMap::find
iterator find(StringRef Key)
Definition: StringMap.h:216
llvm::GraphTraits< ProfiledCallGraph * >::getEntryNode
static NodeRef getEntryNode(ProfiledCallGraph *PCG)
Definition: ProfiledCallGraph.h:201
llvm::GraphTraits< ProfiledCallGraph * >::nodes_begin
static ChildIteratorType nodes_begin(ProfiledCallGraph *PCG)
Definition: ProfiledCallGraph.h:205
llvm::sampleprof::ProfiledCallGraphEdge
Definition: ProfiledCallGraph.h:29
GraphTraits.h
llvm::sampleprof::FunctionSamples::getFuncName
StringRef getFuncName() const
Return the original function name.
Definition: SampleProf.h:949
llvm::sampleprof::ProfiledCallGraphNode::iterator
std::set< ProfiledCallGraphEdge >::iterator iterator
Definition: ProfiledCallGraph.h:54
llvm::sampleprof::FunctionSamples::ProfileIsCSFlat
static bool ProfileIsCSFlat
Definition: SampleProf.h:1049
llvm::sampleprof::ProfiledCallGraph
Definition: ProfiledCallGraph.h:65
llvm::sampleprof::FunctionSamples::findCallTargetMapAt
ErrorOr< SampleRecord::CallTargetMap > findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const
Returns the call target map collected at a given location.
Definition: SampleProf.h:776
SampleProf.h
llvm::sampleprof::ProfiledCallGraph::end
iterator end()
Definition: ProfiledCallGraph.h:130
llvm::sampleprof::ProfiledCallGraphNode::Edges
edges Edges
Definition: ProfiledCallGraph.h:62
StringMap.h
llvm::sampleprof::ProfiledCallGraphEdge::Weight
uint64_t Weight
Definition: ProfiledCallGraph.h:35
llvm::StringMap< uint64_t >
llvm::sampleprof::FunctionSamples::getCallsiteSamples
const CallsiteSampleMap & getCallsiteSamples() const
Return all the callsite samples collected in the body of the function.
Definition: SampleProf.h:858
llvm::sampleprof::ProfiledCallGraphNode::ProfiledCallGraphNode
ProfiledCallGraphNode(StringRef FName=StringRef())
Definition: ProfiledCallGraph.h:59
uint64_t
llvm::sampleprof::FunctionSamples::getEntrySamples
uint64_t getEntrySamples() const
Return the sample count of the first instruction of the function.
Definition: SampleProf.h:831
llvm::sampleprof::FunctionSamples
Representation of the samples collected for a function.
Definition: SampleProf.h:691
SampleProfReader.h
llvm::GraphTraits< ProfiledCallGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: ProfiledCallGraph.h:194
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SampleContextTracker
Definition: SampleContextTracker.h:95
llvm::sampleprof::ProfiledCallGraph::ProfiledCallGraph
ProfiledCallGraph(SampleContextTracker &ContextTracker)
Definition: ProfiledCallGraph.h:79
llvm::sampleprof::ProfiledCallGraphNode
Definition: ProfiledCallGraph.h:42
llvm::sampleprof::LineLocation
Represents the relative location of an instruction.
Definition: SampleProf.h:283
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:99
llvm::ContextTrieNode::getAllChildContext
std::map< uint64_t, ContextTrieNode > & getAllChildContext()
Definition: SampleContextTracker.cpp:117
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::ContextTrieNode
Definition: SampleContextTracker.h:36
llvm::sampleprof::ProfiledCallGraph::iterator
std::set< ProfiledCallGraphEdge >::iterator iterator
Definition: ProfiledCallGraph.h:67
SampleContextTracker.h
llvm::GraphTraits< ProfiledCallGraph * >::nodes_end
static ChildIteratorType nodes_end(ProfiledCallGraph *PCG)
Definition: ProfiledCallGraph.h:209
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:185
llvm::sampleprof::ProfiledCallGraphNode::const_iterator
std::set< ProfiledCallGraphEdge >::const_iterator const_iterator
Definition: ProfiledCallGraph.h:55
llvm::SampleContextTracker::getRootContext
ContextTrieNode & getRootContext()
Definition: SampleContextTracker.cpp:361
llvm::GraphTraits< ProfiledCallGraphNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: ProfiledCallGraph.h:195
llvm::GraphTraits< ProfiledCallGraphNode * >
Definition: ProfiledCallGraph.h:187
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::sampleprof::ProfiledCallGraphEdge::Source
ProfiledCallGraphNode * Source
Definition: ProfiledCallGraph.h:33
llvm::sampleprof::ProfiledCallGraphNode::Name
StringRef Name
Definition: ProfiledCallGraph.h:61
llvm::sampleprof::ProfiledCallGraphNode::ProfiledCallGraphEdgeComparer::operator()
bool operator()(const ProfiledCallGraphEdge &L, const ProfiledCallGraphEdge &R) const
Definition: ProfiledCallGraph.h:48
llvm::sampleprof::ProfiledCallGraphNode::ProfiledCallGraphEdgeComparer
Definition: ProfiledCallGraph.h:47
N
#define N
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::sampleprof::ProfiledCallGraphNode::edges
std::set< ProfiledCallGraphEdge, ProfiledCallGraphEdgeComparer > edges
Definition: ProfiledCallGraph.h:57
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::GraphTraits< ProfiledCallGraphNode * >::ChildIteratorType
NodeType::const_iterator ChildIteratorType
Definition: ProfiledCallGraph.h:191
llvm::sampleprof::ProfiledCallGraph::addProfiledFunction
void addProfiledFunction(StringRef Name)
Definition: ProfiledCallGraph.h:132
llvm::sampleprof::ProfiledCallGraph::getEntryNode
ProfiledCallGraphNode * getEntryNode()
Definition: ProfiledCallGraph.h:131
llvm::sampleprof::ProfiledCallGraphEdge::ProfiledCallGraphEdge
ProfiledCallGraphEdge(ProfiledCallGraphNode *Source, ProfiledCallGraphNode *Target, uint64_t Weight)
Definition: ProfiledCallGraph.h:30