LLVM  15.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 namespace llvm {
22 namespace sampleprof {
23 
24 struct 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 
63 public:
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;
82  addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
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;
99  addProfiledFunction(ContextTracker.getFuncNameFor(Callee));
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->getEntrySamples();
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(); }
128  ProfiledCallGraphNode *getEntryNode() { return &Root; }
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 
138 private:
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 : Sample.second.getCallTargets()) {
163  addProfiledFunction(Target.first());
164  addProfiledCall(Samples.getFuncName(), Target.first(), Target.second);
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.getEntrySamples());
173  addProfiledCalls(InlinedSamples.second);
174  }
175  }
176  }
177 
178  ProfiledCallGraphNode Root;
179  StringMap<ProfiledCallGraphNode> ProfiledFunctions;
180 };
181 
182 } // end namespace sampleprof
183 
184 template <> 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 
195 template <>
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
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SampleContextTracker::getFuncNameFor
StringRef getFuncNameFor(ContextTrieNode *Node) const
Definition: SampleContextTracker.cpp:457
llvm::sampleprof::FunctionSamples::ProfileIsCS
static bool ProfileIsCS
Definition: SampleProf.h:1104
llvm::GraphTraits< ProfiledCallGraphNode * >::getEntryNode
static NodeRef getEntryNode(NodeRef PCGN)
Definition: ProfiledCallGraph.h:190
llvm::sampleprof::ProfiledCallGraph::ProfiledCallGraph
ProfiledCallGraph(SampleProfileMap &ProfileMap)
Definition: ProfiledCallGraph.h:67
StringRef.h
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:145
llvm::sampleprof::SampleProfileMap
std::unordered_map< SampleContext, FunctionSamples, SampleContext::Hash > SampleProfileMap
Definition: SampleProf.h:1183
llvm::StringMap::end
iterator end()
Definition: StringMap.h:204
llvm::sampleprof::ProfiledCallGraph::begin
iterator begin()
Definition: ProfiledCallGraph.h:126
llvm::AMDGPU::Exp::Target
Target
Definition: SIDefines.h:858
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::sampleprof::FunctionSamples::getName
StringRef getName() const
Return the function name.
Definition: SampleProf.h:1001
llvm::sampleprof::ProfiledCallGraphEdge::Target
ProfiledCallGraphNode * Target
Definition: ProfiledCallGraph.h:31
llvm::StringMap::find
iterator find(StringRef Key)
Definition: StringMap.h:217
llvm::sampleprof::ProfiledCallGraphNode::const_iterator
edges::const_iterator const_iterator
Definition: ProfiledCallGraph.h:54
llvm::GraphTraits< ProfiledCallGraph * >::getEntryNode
static NodeRef getEntryNode(ProfiledCallGraph *PCG)
Definition: ProfiledCallGraph.h:198
llvm::GraphTraits< ProfiledCallGraph * >::nodes_begin
static ChildIteratorType nodes_begin(ProfiledCallGraph *PCG)
Definition: ProfiledCallGraph.h:202
llvm::sampleprof::ProfiledCallGraphEdge
Definition: ProfiledCallGraph.h:26
GraphTraits.h
llvm::sampleprof::ProfiledCallGraph
Definition: ProfiledCallGraph.h:62
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:831
SampleProf.h
llvm::sampleprof::ProfiledCallGraph::end
iterator end()
Definition: ProfiledCallGraph.h:127
llvm::sampleprof::ProfiledCallGraphNode::Edges
edges Edges
Definition: ProfiledCallGraph.h:59
StringMap.h
llvm::sampleprof::ProfiledCallGraphEdge::Weight
uint64_t Weight
Definition: ProfiledCallGraph.h:32
llvm::StringMap< uint64_t >
llvm::sampleprof::ProfiledCallGraphNode::iterator
edges::iterator iterator
Definition: ProfiledCallGraph.h:53
llvm::sampleprof::ProfiledCallGraphNode::ProfiledCallGraphNode
ProfiledCallGraphNode(StringRef FName=StringRef())
Definition: ProfiledCallGraph.h:56
uint64_t
llvm::sampleprof::FunctionSamples::getEntrySamples
uint64_t getEntrySamples() const
Return the sample count of the first instruction of the function.
Definition: SampleProf.h:886
llvm::sampleprof::FunctionSamples
Representation of the samples collected for a function.
Definition: SampleProf.h:710
SampleProfReader.h
llvm::GraphTraits< ProfiledCallGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: ProfiledCallGraph.h:191
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SampleContextTracker
Definition: SampleContextTracker.h:89
llvm::sampleprof::ProfiledCallGraph::ProfiledCallGraph
ProfiledCallGraph(SampleContextTracker &ContextTracker)
Definition: ProfiledCallGraph.h:76
llvm::sampleprof::ProfiledCallGraphNode
Definition: ProfiledCallGraph.h:39
llvm::sampleprof::ProfiledCallGraphNode::edges
std::set< edge, ProfiledCallGraphEdgeComparer > edges
Definition: ProfiledCallGraph.h:52
llvm::sampleprof::LineLocation
Represents the relative location of an instruction.
Definition: SampleProf.h:282
llvm::SPIRV::ImageOperand::Sample
@ Sample
llvm::ContextTrieNode::getAllChildContext
std::map< uint64_t, ContextTrieNode > & getAllChildContext()
Definition: SampleContextTracker.cpp:113
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::ContextTrieNode
Definition: SampleContextTracker.h:34
SampleContextTracker.h
llvm::GraphTraits< ProfiledCallGraph * >::nodes_end
static ChildIteratorType nodes_end(ProfiledCallGraph *PCG)
Definition: ProfiledCallGraph.h:206
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:186
llvm::SampleContextTracker::getRootContext
ContextTrieNode & getRootContext()
Definition: SampleContextTracker.cpp:371
llvm::GraphTraits< ProfiledCallGraphNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: ProfiledCallGraph.h:192
llvm::GraphTraits< ProfiledCallGraphNode * >
Definition: ProfiledCallGraph.h:184
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::sampleprof::ProfiledCallGraphEdge::Source
ProfiledCallGraphNode * Source
Definition: ProfiledCallGraph.h:30
llvm::sampleprof::ProfiledCallGraphNode::Name
StringRef Name
Definition: ProfiledCallGraph.h:58
llvm::sampleprof::ProfiledCallGraphNode::ProfiledCallGraphEdgeComparer::operator()
bool operator()(const ProfiledCallGraphEdge &L, const ProfiledCallGraphEdge &R) const
Definition: ProfiledCallGraph.h:45
llvm::sampleprof::ProfiledCallGraphNode::ProfiledCallGraphEdgeComparer
Definition: ProfiledCallGraph.h:44
N
#define N
llvm::GraphTraits
Definition: GraphTraits.h:37
llvm::GraphTraits< ProfiledCallGraphNode * >::ChildIteratorType
NodeType::const_iterator ChildIteratorType
Definition: ProfiledCallGraph.h:188
llvm::sampleprof::ProfiledCallGraph::addProfiledFunction
void addProfiledFunction(StringRef Name)
Definition: ProfiledCallGraph.h:129
llvm::sampleprof::ProfiledCallGraph::iterator
ProfiledCallGraphNode::iterator iterator
Definition: ProfiledCallGraph.h:64
llvm::sampleprof::ProfiledCallGraph::getEntryNode
ProfiledCallGraphNode * getEntryNode()
Definition: ProfiledCallGraph.h:128
llvm::sampleprof::ProfiledCallGraphEdge::ProfiledCallGraphEdge
ProfiledCallGraphEdge(ProfiledCallGraphNode *Source, ProfiledCallGraphNode *Target, uint64_t Weight)
Definition: ProfiledCallGraph.h:27