LLVM  6.0.0svn
ImportedFunctionsInliningStatistics.cpp
Go to the documentation of this file.
1 //===-- ImportedFunctionsInliningStats.cpp ----------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 // Generating inliner statistics for imported functions, mostly useful for
10 // ThinLTO.
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/IR/Function.h"
16 #include "llvm/IR/Module.h"
17 #include "llvm/Support/Debug.h"
19 #include <algorithm>
20 #include <iomanip>
21 #include <sstream>
22 using namespace llvm;
23 
24 ImportedFunctionsInliningStatistics::InlineGraphNode &
25 ImportedFunctionsInliningStatistics::createInlineGraphNode(const Function &F) {
26 
27  auto &ValueLookup = NodesMap[F.getName()];
28  if (!ValueLookup) {
29  ValueLookup = llvm::make_unique<InlineGraphNode>();
30  ValueLookup->Imported = F.getMetadata("thinlto_src_module") != nullptr;
31  }
32  return *ValueLookup;
33 }
34 
36  const Function &Callee) {
37 
38  InlineGraphNode &CallerNode = createInlineGraphNode(Caller);
39  InlineGraphNode &CalleeNode = createInlineGraphNode(Callee);
40  CalleeNode.NumberOfInlines++;
41 
42  if (!CallerNode.Imported && !CalleeNode.Imported) {
43  // Direct inline from not imported callee to not imported caller, so we
44  // don't have to add this to graph. It might be very helpful if you wanna
45  // get the inliner statistics in compile step where there are no imported
46  // functions. In this case the graph would be empty.
47  CalleeNode.NumberOfRealInlines++;
48  return;
49  }
50 
51  CallerNode.InlinedCallees.push_back(&CalleeNode);
52  if (!CallerNode.Imported) {
53  // We could avoid second lookup, but it would make the code ultra ugly.
54  auto It = NodesMap.find(Caller.getName());
55  assert(It != NodesMap.end() && "The node should be already there.");
56  // Save Caller as a starting node for traversal. The string has to be one
57  // from map because Caller can disappear (and function name with it).
58  NonImportedCallers.push_back(It->first());
59  }
60 }
61 
63  ModuleName = M.getName();
64  for (const auto &F : M.functions()) {
65  if (F.isDeclaration())
66  continue;
67  AllFunctions++;
68  ImportedFunctions += int(F.getMetadata("thinlto_src_module") != nullptr);
69  }
70 }
71 static std::string getStatString(const char *Msg, int32_t Fraction, int32_t All,
72  const char *PercentageOfMsg,
73  bool LineEnd = true) {
74  double Result = 0;
75  if (All != 0)
76  Result = 100 * static_cast<double>(Fraction) / All;
77 
78  std::stringstream Str;
79  Str << std::setprecision(4) << Msg << ": " << Fraction << " [" << Result
80  << "% of " << PercentageOfMsg << "]";
81  if (LineEnd)
82  Str << "\n";
83  return Str.str();
84 }
85 
87  calculateRealInlines();
88  NonImportedCallers.clear();
89 
90  int32_t InlinedImportedFunctionsCount = 0;
91  int32_t InlinedNotImportedFunctionsCount = 0;
92 
93  int32_t InlinedImportedFunctionsToImportingModuleCount = 0;
94  int32_t InlinedNotImportedFunctionsToImportingModuleCount = 0;
95 
96  const auto SortedNodes = getSortedNodes();
97  std::string Out;
98  Out.reserve(5000);
99  raw_string_ostream Ostream(Out);
100 
101  Ostream << "------- Dumping inliner stats for [" << ModuleName
102  << "] -------\n";
103 
104  if (Verbose)
105  Ostream << "-- List of inlined functions:\n";
106 
107  for (const auto &Node : SortedNodes) {
108  assert(Node->second->NumberOfInlines >= Node->second->NumberOfRealInlines);
109  if (Node->second->NumberOfInlines == 0)
110  continue;
111 
112  if (Node->second->Imported) {
113  InlinedImportedFunctionsCount++;
114  InlinedImportedFunctionsToImportingModuleCount +=
115  int(Node->second->NumberOfRealInlines > 0);
116  } else {
117  InlinedNotImportedFunctionsCount++;
118  InlinedNotImportedFunctionsToImportingModuleCount +=
119  int(Node->second->NumberOfRealInlines > 0);
120  }
121 
122  if (Verbose)
123  Ostream << "Inlined "
124  << (Node->second->Imported ? "imported " : "not imported ")
125  << "function [" << Node->first() << "]"
126  << ": #inlines = " << Node->second->NumberOfInlines
127  << ", #inlines_to_importing_module = "
128  << Node->second->NumberOfRealInlines << "\n";
129  }
130 
131  auto InlinedFunctionsCount =
132  InlinedImportedFunctionsCount + InlinedNotImportedFunctionsCount;
133  auto NotImportedFuncCount = AllFunctions - ImportedFunctions;
134  auto ImportedNotInlinedIntoModule =
135  ImportedFunctions - InlinedImportedFunctionsToImportingModuleCount;
136 
137  Ostream << "-- Summary:\n"
138  << "All functions: " << AllFunctions
139  << ", imported functions: " << ImportedFunctions << "\n"
140  << getStatString("inlined functions", InlinedFunctionsCount,
141  AllFunctions, "all functions")
142  << getStatString("imported functions inlined anywhere",
143  InlinedImportedFunctionsCount, ImportedFunctions,
144  "imported functions")
145  << getStatString("imported functions inlined into importing module",
146  InlinedImportedFunctionsToImportingModuleCount,
147  ImportedFunctions, "imported functions",
148  /*LineEnd=*/false)
149  << getStatString(", remaining", ImportedNotInlinedIntoModule,
150  ImportedFunctions, "imported functions")
151  << getStatString("non-imported functions inlined anywhere",
152  InlinedNotImportedFunctionsCount,
153  NotImportedFuncCount, "non-imported functions")
154  << getStatString(
155  "non-imported functions inlined into importing module",
156  InlinedNotImportedFunctionsToImportingModuleCount,
157  NotImportedFuncCount, "non-imported functions");
158  Ostream.flush();
159  dbgs() << Out;
160 }
161 
162 void ImportedFunctionsInliningStatistics::calculateRealInlines() {
163  // Removing duplicated Callers.
164  std::sort(NonImportedCallers.begin(), NonImportedCallers.end());
165  NonImportedCallers.erase(
166  std::unique(NonImportedCallers.begin(), NonImportedCallers.end()),
167  NonImportedCallers.end());
168 
169  for (const auto &Name : NonImportedCallers) {
170  auto &Node = *NodesMap[Name];
171  if (!Node.Visited)
172  dfs(Node);
173  }
174 }
175 
176 void ImportedFunctionsInliningStatistics::dfs(InlineGraphNode &GraphNode) {
177  assert(!GraphNode.Visited);
178  GraphNode.Visited = true;
179  for (auto *const InlinedFunctionNode : GraphNode.InlinedCallees) {
180  InlinedFunctionNode->NumberOfRealInlines++;
181  if (!InlinedFunctionNode->Visited)
182  dfs(*InlinedFunctionNode);
183  }
184 }
185 
186 ImportedFunctionsInliningStatistics::SortedNodesTy
187 ImportedFunctionsInliningStatistics::getSortedNodes() {
188  SortedNodesTy SortedNodes;
189  SortedNodes.reserve(NodesMap.size());
190  for (const NodesMapTy::value_type& Node : NodesMap)
191  SortedNodes.push_back(&Node);
192 
193  std::sort(
194  SortedNodes.begin(), SortedNodes.end(),
195  [&](const SortedNodesTy::value_type &Lhs,
196  const SortedNodesTy::value_type &Rhs) {
197  if (Lhs->second->NumberOfInlines != Rhs->second->NumberOfInlines)
198  return Lhs->second->NumberOfInlines > Rhs->second->NumberOfInlines;
199  if (Lhs->second->NumberOfRealInlines != Rhs->second->NumberOfRealInlines)
200  return Lhs->second->NumberOfRealInlines >
201  Rhs->second->NumberOfRealInlines;
202  return Lhs->first() < Rhs->first();
203  });
204  return SortedNodes;
205 }
void setModuleInfo(const Module &M)
Set information like AllFunctions, ImportedFunctions, ModuleName.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
Definition: StringMap.h:126
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
void recordInline(const Function &Caller, const Function &Callee)
Record inline of.
iterator find(StringRef Key)
Definition: StringMap.h:337
StringRef getName() const
Get a short "name" for the module.
Definition: Module.h:220
F(f)
unsigned size() const
Definition: StringMap.h:112
MDNode * getMetadata(unsigned KindID) const
Get the current metadata attachments for the given kind, if any.
Definition: Metadata.cpp:1431
amdgpu Simplify well known AMD library false Value * Callee
iterator_range< iterator > functions()
Definition: Module.h:583
Module.h This file contains the declarations for the Module class.
static std::string getStatString(const char *Msg, int32_t Fraction, int32_t All, const char *PercentageOfMsg, bool LineEnd=true)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void dump(bool Verbose)
Dump stats computed with InlinerStatistics class.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:201
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:462
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199
iterator end()
Definition: StringMap.h:322