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 
13 #include "llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/IR/Function.h"
16 #include "llvm/IR/Module.h"
17 #include "llvm/Support/Debug.h"
18 #include "llvm/Support/raw_ostream.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 
35 void ImportedFunctionsInliningStatistics::recordInline(const Function &Caller,
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 
62 void ImportedFunctionsInliningStatistics::setModuleInfo(const Module &M) {
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 
86 void ImportedFunctionsInliningStatistics::dump(const bool Verbose) {
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 }
206