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.
71  assert(!FunctionSamples::ProfileIsCS && "CS profile is not handled here");
72  for (const auto &Samples : ProfileMap) {
73  addProfiledCalls(Samples.second);
74  }
75  }
76 
77  // Constructor for CS profile.
79  // BFS traverse the context profile trie to add call edges for calls shown
80  // in context.
81  std::queue<ContextTrieNode *> Queue;
82  for (auto &Child : ContextTracker.getRootContext().getAllChildContext()) {
83  ContextTrieNode *Callee = &Child.second;
84  addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
85  Queue.push(Callee);
86  }
87 
88  while (!Queue.empty()) {
89  ContextTrieNode *Caller = Queue.front();
90  Queue.pop();
91  FunctionSamples *CallerSamples = Caller->getFunctionSamples();
92 
93  // Add calls for context.
94  // Note that callsite target samples are completely ignored since they can
95  // conflict with the context edges, which are formed by context
96  // compression during profile generation, for cyclic SCCs. This may
97  // further result in an SCC order incompatible with the purely
98  // context-based one, which may in turn block context-based inlining.
99  for (auto &Child : Caller->getAllChildContext()) {
100  ContextTrieNode *Callee = &Child.second;
101  addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
102  Queue.push(Callee);
103 
104  // Fetch edge weight from the profile.
105  uint64_t Weight;
106  FunctionSamples *CalleeSamples = Callee->getFunctionSamples();
107  if (!CalleeSamples || !CallerSamples) {
108  Weight = 0;
109  } else {
110  uint64_t CalleeEntryCount = CalleeSamples->getEntrySamples();
111  uint64_t CallsiteCount = 0;
112  LineLocation Callsite = Callee->getCallSiteLoc();
113  if (auto CallTargets = CallerSamples->findCallTargetMapAt(Callsite)) {
114  SampleRecord::CallTargetMap &TargetCounts = CallTargets.get();
115  auto It = TargetCounts.find(CalleeSamples->getName());
116  if (It != TargetCounts.end())
117  CallsiteCount = It->second;
118  }
119  Weight = std::max(CallsiteCount, CalleeEntryCount);
120  }
121 
122  addProfiledCall(ContextTracker.getFuncNameFor(Caller),
123  ContextTracker.getFuncNameFor(Callee), Weight);
124  }
125  }
126  }
127 
128  iterator begin() { return Root.Edges.begin(); }
129  iterator end() { return Root.Edges.end(); }
130  ProfiledCallGraphNode *getEntryNode() { return &Root; }
132  if (!ProfiledFunctions.count(Name)) {
133  // Link to synthetic root to make sure every node is reachable
134  // from root. This does not affect SCC order.
135  ProfiledFunctions[Name] = ProfiledCallGraphNode(Name);
136  Root.Edges.emplace(&Root, &ProfiledFunctions[Name], 0);
137  }
138  }
139 
140 private:
141  void addProfiledCall(StringRef CallerName, StringRef CalleeName,
142  uint64_t Weight = 0) {
143  assert(ProfiledFunctions.count(CallerName));
144  auto CalleeIt = ProfiledFunctions.find(CalleeName);
145  if (CalleeIt == ProfiledFunctions.end())
146  return;
147  ProfiledCallGraphEdge Edge(&ProfiledFunctions[CallerName],
148  &CalleeIt->second, Weight);
149  auto &Edges = ProfiledFunctions[CallerName].Edges;
150  auto EdgeIt = Edges.find(Edge);
151  if (EdgeIt == Edges.end()) {
152  Edges.insert(Edge);
153  } else if (EdgeIt->Weight < Edge.Weight) {
154  // Replace existing call edges with same target but smaller weight.
155  Edges.erase(EdgeIt);
156  Edges.insert(Edge);
157  }
158  }
159 
160  void addProfiledCalls(const FunctionSamples &Samples) {
161  addProfiledFunction(Samples.getFuncName());
162 
163  for (const auto &Sample : Samples.getBodySamples()) {
164  for (const auto &Target : Sample.second.getCallTargets()) {
165  addProfiledFunction(Target.first());
166  addProfiledCall(Samples.getFuncName(), Target.first(), Target.second);
167  }
168  }
169 
170  for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) {
171  for (const auto &InlinedSamples : CallsiteSamples.second) {
172  addProfiledFunction(InlinedSamples.first);
173  addProfiledCall(Samples.getFuncName(), InlinedSamples.first,
174  InlinedSamples.second.getEntrySamples());
175  addProfiledCalls(InlinedSamples.second);
176  }
177  }
178  }
179 
181  StringMap<ProfiledCallGraphNode> ProfiledFunctions;
182 };
183 
184 } // end namespace sampleprof
185 
186 template <> struct GraphTraits<ProfiledCallGraphNode *> {
191 
192  static NodeRef getEntryNode(NodeRef PCGN) { return PCGN; }
193  static ChildIteratorType child_begin(NodeRef N) { return N->Edges.begin(); }
194  static ChildIteratorType child_end(NodeRef N) { return N->Edges.end(); }
195 };
196 
197 template <>
201  return PCG->getEntryNode();
202  }
203 
205  return PCG->begin();
206  }
207 
209  return PCG->end();
210  }
211 };
212 
213 } // end namespace llvm
214 
215 #endif
llvm::sampleprof::FunctionSamples::getBodySamples
const BodySampleMap & getBodySamples() const
Return all the samples collected in the body of the function.
Definition: SampleProf.h:842
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:432
llvm::sampleprof::FunctionSamples::ProfileIsCS
static bool ProfileIsCS
Definition: SampleProf.h:1030
llvm::GraphTraits< ProfiledCallGraphNode * >::getEntryNode
static NodeRef getEntryNode(NodeRef PCGN)
Definition: ProfiledCallGraph.h:192
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:1109
llvm::StringMap::end
iterator end()
Definition: StringMap.h:203
llvm::sampleprof::ProfiledCallGraph::begin
iterator begin()
Definition: ProfiledCallGraph.h:128
llvm::AMDGPU::Exp::Target
Target
Definition: SIDefines.h:742
llvm::sampleprof::FunctionSamples::getName
StringRef getName() const
Return the function name.
Definition: SampleProf.h:933
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:200
llvm::GraphTraits< ProfiledCallGraph * >::nodes_begin
static ChildIteratorType nodes_begin(ProfiledCallGraph *PCG)
Definition: ProfiledCallGraph.h:204
llvm::sampleprof::ProfiledCallGraphEdge
Definition: ProfiledCallGraph.h:29
GraphTraits.h
llvm::sampleprof::FunctionSamples::getFuncName
StringRef getFuncName() const
Return the original function name.
Definition: SampleProf.h:936
llvm::sampleprof::ProfiledCallGraphNode::iterator
std::set< ProfiledCallGraphEdge >::iterator iterator
Definition: ProfiledCallGraph.h:54
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:763
SampleProf.h
llvm::sampleprof::ProfiledCallGraph::end
iterator end()
Definition: ProfiledCallGraph.h:129
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:845
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:818
llvm::sampleprof::FunctionSamples
Representation of the samples collected for a function.
Definition: SampleProf.h:688
SampleProfReader.h
llvm::GraphTraits< ProfiledCallGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: ProfiledCallGraph.h:193
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SampleContextTracker
Definition: SampleContextTracker.h:97
llvm::sampleprof::ProfiledCallGraph::ProfiledCallGraph
ProfiledCallGraph(SampleContextTracker &ContextTracker)
Definition: ProfiledCallGraph.h:78
llvm::sampleprof::ProfiledCallGraphNode
Definition: ProfiledCallGraph.h:42
llvm::sampleprof::LineLocation
Represents the relative location of an instruction.
Definition: SampleProf.h:280
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:100
llvm::ContextTrieNode::getAllChildContext
std::map< uint64_t, ContextTrieNode > & getAllChildContext()
Definition: SampleContextTracker.cpp:116
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:208
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:206
llvm::sampleprof::ProfiledCallGraphNode::const_iterator
std::set< ProfiledCallGraphEdge >::const_iterator const_iterator
Definition: ProfiledCallGraph.h:55
llvm::SampleContextTracker::getRootContext
ContextTrieNode & getRootContext()
Definition: SampleContextTracker.cpp:372
llvm::GraphTraits< ProfiledCallGraphNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: ProfiledCallGraph.h:194
llvm::GraphTraits< ProfiledCallGraphNode * >
Definition: ProfiledCallGraph.h:186
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
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:190
llvm::sampleprof::ProfiledCallGraph::addProfiledFunction
void addProfiledFunction(StringRef Name)
Definition: ProfiledCallGraph.h:131
llvm::sampleprof::ProfiledCallGraph::getEntryNode
ProfiledCallGraphNode * getEntryNode()
Definition: ProfiledCallGraph.h:130
llvm::sampleprof::ProfiledCallGraphEdge::ProfiledCallGraphEdge
ProfiledCallGraphEdge(ProfiledCallGraphNode *Source, ProfiledCallGraphNode *Target, uint64_t Weight)
Definition: ProfiledCallGraph.h:30