LLVM  13.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_TOOLS_LLVM_PROFGEN_PROFILEDCALLGRAPH_H
10 #define LLVM_TOOLS_LLVM_PROFGEN_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 #include <string>
21 
22 using namespace llvm;
23 using namespace sampleprof;
24 
25 namespace llvm {
26 namespace sampleprof {
27 
31 
34  const ProfiledCallGraphNode *R) const {
35  return L->Name < R->Name;
36  }
37  };
38  std::set<ProfiledCallGraphNode *, ProfiledCallGraphNodeComparer> Callees;
39 };
40 
42 public:
43  using iterator = std::set<ProfiledCallGraphNode *>::iterator;
44 
45  // Constructor for non-CS profile.
47  assert(!FunctionSamples::ProfileIsCS && "CS profile is not handled here");
48  for (const auto &Samples : ProfileMap) {
49  addProfiledCalls(Samples.second);
50  }
51  }
52 
53  // Constructor for CS profile.
55  // BFS traverse the context profile trie to add call edges for calls shown
56  // in context.
57  std::queue<ContextTrieNode *> Queue;
58  for (auto &Child : ContextTracker.getRootContext().getAllChildContext()) {
59  ContextTrieNode *Callee = &Child.second;
60  addProfiledFunction(Callee->getFuncName());
61  Queue.push(Callee);
62  }
63 
64  while (!Queue.empty()) {
65  ContextTrieNode *Caller = Queue.front();
66  Queue.pop();
67  // Add calls for context. When AddNodeWithSamplesOnly is true, both caller
68  // and callee need to have context profile.
69  // Note that callsite target samples are completely ignored since they can
70  // conflict with the context edges, which are formed by context
71  // compression during profile generation, for cyclic SCCs. This may
72  // further result in an SCC order incompatible with the purely
73  // context-based one, which may in turn block context-based inlining.
74  for (auto &Child : Caller->getAllChildContext()) {
75  ContextTrieNode *Callee = &Child.second;
76  addProfiledFunction(Callee->getFuncName());
77  Queue.push(Callee);
78  addProfiledCall(Caller->getFuncName(), Callee->getFuncName());
79  }
80  }
81  }
82 
83  iterator begin() { return Root.Callees.begin(); }
84  iterator end() { return Root.Callees.end(); }
85  ProfiledCallGraphNode *getEntryNode() { return &Root; }
87  if (!ProfiledFunctions.count(Name)) {
88  // Link to synthetic root to make sure every node is reachable
89  // from root. This does not affect SCC order.
90  ProfiledFunctions[Name] = ProfiledCallGraphNode(Name);
91  Root.Callees.insert(&ProfiledFunctions[Name]);
92  }
93  }
94 
95  void addProfiledCall(StringRef CallerName, StringRef CalleeName) {
96  assert(ProfiledFunctions.count(CallerName));
97  auto CalleeIt = ProfiledFunctions.find(CalleeName);
98  if (CalleeIt == ProfiledFunctions.end()) {
99  return;
100  }
101  ProfiledFunctions[CallerName].Callees.insert(&CalleeIt->second);
102  }
103 
104  void addProfiledCalls(const FunctionSamples &Samples) {
105  addProfiledFunction(Samples.getFuncName());
106 
107  for (const auto &Sample : Samples.getBodySamples()) {
108  for (const auto &Target : Sample.second.getCallTargets()) {
109  addProfiledFunction(Target.first());
110  addProfiledCall(Samples.getFuncName(), Target.first());
111  }
112  }
113 
114  for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) {
115  for (const auto &InlinedSamples : CallsiteSamples.second) {
116  addProfiledFunction(InlinedSamples.first);
117  addProfiledCall(Samples.getFuncName(), InlinedSamples.first);
118  addProfiledCalls(InlinedSamples.second);
119  }
120  }
121  }
122 
123 private:
125  StringMap<ProfiledCallGraphNode> ProfiledFunctions;
126 };
127 
128 } // end namespace sampleprof
129 
130 template <> struct GraphTraits<ProfiledCallGraphNode *> {
132  using ChildIteratorType = std::set<ProfiledCallGraphNode *>::iterator;
133 
134  static NodeRef getEntryNode(NodeRef PCGN) { return PCGN; }
135  static ChildIteratorType child_begin(NodeRef N) { return N->Callees.begin(); }
136  static ChildIteratorType child_end(NodeRef N) { return N->Callees.end(); }
137 };
138 
139 template <>
143  return PCG->getEntryNode();
144  }
145 
147  return PCG->begin();
148  }
149 
151  return PCG->end();
152  }
153 };
154 
155 } // end namespace llvm
156 
157 #endif
llvm::sampleprof::FunctionSamples::getBodySamples
const BodySampleMap & getBodySamples() const
Return all the samples collected in the body of the function.
Definition: SampleProf.h:685
llvm
Definition: AllocatorList.h:23
llvm::sampleprof::FunctionSamples::ProfileIsCS
static bool ProfileIsCS
Definition: SampleProf.h:883
llvm::GraphTraits< ProfiledCallGraphNode * >::getEntryNode
static NodeRef getEntryNode(NodeRef PCGN)
Definition: ProfiledCallGraph.h:134
StringRef.h
llvm::Target
Target - Wrapper for Target specific information.
Definition: TargetRegistry.h:125
llvm::ContextTrieNode::getAllChildContext
std::map< uint32_t, ContextTrieNode > & getAllChildContext()
Definition: SampleContextTracker.cpp:116
llvm::sampleprof::ProfiledCallGraphNode::ProfiledCallGraphNodeComparer
Definition: ProfiledCallGraph.h:32
llvm::sampleprof::ProfiledCallGraph::begin
iterator begin()
Definition: ProfiledCallGraph.h:83
llvm::GraphTraits< ProfiledCallGraph * >::getEntryNode
static NodeRef getEntryNode(ProfiledCallGraph *PCG)
Definition: ProfiledCallGraph.h:142
llvm::GraphTraits< ProfiledCallGraph * >::nodes_begin
static ChildIteratorType nodes_begin(ProfiledCallGraph *PCG)
Definition: ProfiledCallGraph.h:146
GraphTraits.h
llvm::sampleprof::FunctionSamples::getFuncName
StringRef getFuncName() const
Return the original function name.
Definition: SampleProf.h:785
llvm::sampleprof::ProfiledCallGraph
Definition: ProfiledCallGraph.h:41
SampleProf.h
llvm::sampleprof::ProfiledCallGraph::end
iterator end()
Definition: ProfiledCallGraph.h:84
StringMap.h
llvm::StringMap
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:108
llvm::sampleprof::ProfiledCallGraph::iterator
std::set< ProfiledCallGraphNode * >::iterator iterator
Definition: ProfiledCallGraph.h:43
llvm::sampleprof::FunctionSamples::getCallsiteSamples
const CallsiteSampleMap & getCallsiteSamples() const
Return all the callsite samples collected in the body of the function.
Definition: SampleProf.h:688
llvm::GraphTraits< ProfiledCallGraphNode * >::ChildIteratorType
std::set< ProfiledCallGraphNode * >::iterator ChildIteratorType
Definition: ProfiledCallGraph.h:132
llvm::sampleprof::ProfiledCallGraphNode::ProfiledCallGraphNode
ProfiledCallGraphNode(StringRef FName=StringRef())
Definition: ProfiledCallGraph.h:29
llvm::sampleprof::FunctionSamples
Representation of the samples collected for a function.
Definition: SampleProf.h:533
SampleProfReader.h
llvm::GraphTraits< ProfiledCallGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: ProfiledCallGraph.h:135
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SampleContextTracker
Definition: SampleContextTracker.h:91
llvm::sampleprof::ProfiledCallGraph::ProfiledCallGraph
ProfiledCallGraph(SampleContextTracker &ContextTracker)
Definition: ProfiledCallGraph.h:54
llvm::sampleprof::ProfiledCallGraphNode
Definition: ProfiledCallGraph.h:28
llvm::sampleprof::ProfiledCallGraph::addProfiledCall
void addProfiledCall(StringRef CallerName, StringRef CalleeName)
Definition: ProfiledCallGraph.h:95
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::ContextTrieNode
Definition: SampleContextTracker.h:36
SampleContextTracker.h
llvm::GraphTraits< ProfiledCallGraph * >::nodes_end
static ChildIteratorType nodes_end(ProfiledCallGraph *PCG)
Definition: ProfiledCallGraph.h:150
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:206
llvm::SampleContextTracker::getRootContext
ContextTrieNode & getRootContext()
Definition: SampleContextTracker.cpp:331
llvm::GraphTraits< ProfiledCallGraphNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: ProfiledCallGraph.h:136
llvm::GraphTraits< ProfiledCallGraphNode * >
Definition: ProfiledCallGraph.h:130
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::sampleprof::ProfiledCallGraphNode::Name
StringRef Name
Definition: ProfiledCallGraph.h:30
llvm::sampleprof::ProfiledCallGraph::addProfiledCalls
void addProfiledCalls(const FunctionSamples &Samples)
Definition: ProfiledCallGraph.h:104
llvm::sampleprof::ProfiledCallGraphNode::Callees
std::set< ProfiledCallGraphNode *, ProfiledCallGraphNodeComparer > Callees
Definition: ProfiledCallGraph.h:38
llvm::sampleprof::ProfiledCallGraph::ProfiledCallGraph
ProfiledCallGraph(StringMap< FunctionSamples > &ProfileMap)
Definition: ProfiledCallGraph.h:46
N
#define N
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::sampleprof::ProfiledCallGraph::addProfiledFunction
void addProfiledFunction(StringRef Name)
Definition: ProfiledCallGraph.h:86
llvm::sampleprof::ProfiledCallGraphNode::ProfiledCallGraphNodeComparer::operator()
bool operator()(const ProfiledCallGraphNode *L, const ProfiledCallGraphNode *R) const
Definition: ProfiledCallGraph.h:33
llvm::sampleprof::ProfiledCallGraph::getEntryNode
ProfiledCallGraphNode * getEntryNode()
Definition: ProfiledCallGraph.h:85