1 //===-- ImportedFunctionsInliningStats.cpp ----------------------*- 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 // Generating inliner statistics for imported functions, mostly useful for
9 // ThinLTO.
10 //===----------------------------------------------------------------------===//
11 
12 #include "llvm/Analysis/Utils/ImportedFunctionsInliningStatistics.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/IR/Function.h"
15 #include "llvm/IR/Module.h"
16 #include "llvm/Support/CommandLine.h"
17 #include "llvm/Support/Debug.h"
18 #include "llvm/Support/raw_ostream.h"
19 #include <algorithm>
20 #include <iomanip>
21 #include <sstream>
22 #include <string>
23 
24 using namespace llvm;
25 
26 namespace llvm {
27 cl::opt<InlinerFunctionImportStatsOpts> InlinerFunctionImportStats(
28     "inliner-function-import-stats",
29     cl::init(InlinerFunctionImportStatsOpts::No),
30     cl::values(clEnumValN(InlinerFunctionImportStatsOpts::Basic, "basic",
31                           "basic statistics"),
32                clEnumValN(InlinerFunctionImportStatsOpts::Verbose, "verbose",
33                           "printing of statistics for each inlined function")),
34     cl::Hidden, cl::desc("Enable inliner stats for imported functions"));
35 }
36 
37 ImportedFunctionsInliningStatistics::InlineGraphNode &
createInlineGraphNode(const Function & F)38 ImportedFunctionsInliningStatistics::createInlineGraphNode(const Function &F) {
39 
40   auto &ValueLookup = NodesMap[F.getName()];
41   if (!ValueLookup) {
42     ValueLookup = std::make_unique<InlineGraphNode>();
43     ValueLookup->Imported = F.hasMetadata("thinlto_src_module");
44   }
45   return *ValueLookup;
46 }
47 
recordInline(const Function & Caller,const Function & Callee)48 void ImportedFunctionsInliningStatistics::recordInline(const Function &Caller,
49                                                        const Function &Callee) {
50 
51   InlineGraphNode &CallerNode = createInlineGraphNode(Caller);
52   InlineGraphNode &CalleeNode = createInlineGraphNode(Callee);
53   CalleeNode.NumberOfInlines++;
54 
55   if (!CallerNode.Imported && !CalleeNode.Imported) {
56     // Direct inline from not imported callee to not imported caller, so we
57     // don't have to add this to graph. It might be very helpful if you wanna
58     // get the inliner statistics in compile step where there are no imported
59     // functions. In this case the graph would be empty.
60     CalleeNode.NumberOfRealInlines++;
61     return;
62   }
63 
64   CallerNode.InlinedCallees.push_back(&CalleeNode);
65   if (!CallerNode.Imported) {
66     // We could avoid second lookup, but it would make the code ultra ugly.
67     auto It = NodesMap.find(Caller.getName());
68     assert(It != NodesMap.end() && "The node should be already there.");
69     // Save Caller as a starting node for traversal. The string has to be one
70     // from map because Caller can disappear (and function name with it).
71     NonImportedCallers.push_back(It->first());
72   }
73 }
74 
setModuleInfo(const Module & M)75 void ImportedFunctionsInliningStatistics::setModuleInfo(const Module &M) {
76   ModuleName = M.getName();
77   for (const auto &F : M.functions()) {
78     if (F.isDeclaration())
79       continue;
80     AllFunctions++;
81     ImportedFunctions += int(F.hasMetadata("thinlto_src_module"));
82   }
83 }
getStatString(const char * Msg,int32_t Fraction,int32_t All,const char * PercentageOfMsg,bool LineEnd=true)84 static std::string getStatString(const char *Msg, int32_t Fraction, int32_t All,
85                                  const char *PercentageOfMsg,
86                                  bool LineEnd = true) {
87   double Result = 0;
88   if (All != 0)
89     Result = 100 * static_cast<double>(Fraction) / All;
90 
91   std::stringstream Str;
92   Str << std::setprecision(4) << Msg << ": " << Fraction << " [" << Result
93       << "% of " << PercentageOfMsg << "]";
94   if (LineEnd)
95     Str << "\n";
96   return Str.str();
97 }
98 
dump(const bool Verbose)99 void ImportedFunctionsInliningStatistics::dump(const bool Verbose) {
100   calculateRealInlines();
101   NonImportedCallers.clear();
102 
103   int32_t InlinedImportedFunctionsCount = 0;
104   int32_t InlinedNotImportedFunctionsCount = 0;
105 
106   int32_t InlinedImportedFunctionsToImportingModuleCount = 0;
107   int32_t InlinedNotImportedFunctionsToImportingModuleCount = 0;
108 
109   const auto SortedNodes = getSortedNodes();
110   std::string Out;
111   Out.reserve(5000);
112   raw_string_ostream Ostream(Out);
113 
114   Ostream << "------- Dumping inliner stats for [" << ModuleName
115           << "] -------\n";
116 
117   if (Verbose)
118     Ostream << "-- List of inlined functions:\n";
119 
120   for (const auto &Node : SortedNodes) {
121     assert(Node->second->NumberOfInlines >= Node->second->NumberOfRealInlines);
122     if (Node->second->NumberOfInlines == 0)
123       continue;
124 
125     if (Node->second->Imported) {
126       InlinedImportedFunctionsCount++;
127       InlinedImportedFunctionsToImportingModuleCount +=
128           int(Node->second->NumberOfRealInlines > 0);
129     } else {
130       InlinedNotImportedFunctionsCount++;
131       InlinedNotImportedFunctionsToImportingModuleCount +=
132           int(Node->second->NumberOfRealInlines > 0);
133     }
134 
135     if (Verbose)
136       Ostream << "Inlined "
137               << (Node->second->Imported ? "imported " : "not imported ")
138               << "function [" << Node->first() << "]"
139               << ": #inlines = " << Node->second->NumberOfInlines
140               << ", #inlines_to_importing_module = "
141               << Node->second->NumberOfRealInlines << "\n";
142   }
143 
144   auto InlinedFunctionsCount =
145       InlinedImportedFunctionsCount + InlinedNotImportedFunctionsCount;
146   auto NotImportedFuncCount = AllFunctions - ImportedFunctions;
147   auto ImportedNotInlinedIntoModule =
148       ImportedFunctions - InlinedImportedFunctionsToImportingModuleCount;
149 
150   Ostream << "-- Summary:\n"
151           << "All functions: " << AllFunctions
152           << ", imported functions: " << ImportedFunctions << "\n"
153           << getStatString("inlined functions", InlinedFunctionsCount,
154                            AllFunctions, "all functions")
155           << getStatString("imported functions inlined anywhere",
156                            InlinedImportedFunctionsCount, ImportedFunctions,
157                            "imported functions")
158           << getStatString("imported functions inlined into importing module",
159                            InlinedImportedFunctionsToImportingModuleCount,
160                            ImportedFunctions, "imported functions",
161                            /*LineEnd=*/false)
162           << getStatString(", remaining", ImportedNotInlinedIntoModule,
163                            ImportedFunctions, "imported functions")
164           << getStatString("non-imported functions inlined anywhere",
165                            InlinedNotImportedFunctionsCount,
166                            NotImportedFuncCount, "non-imported functions")
167           << getStatString(
168                  "non-imported functions inlined into importing module",
169                  InlinedNotImportedFunctionsToImportingModuleCount,
170                  NotImportedFuncCount, "non-imported functions");
171   Ostream.flush();
172   dbgs() << Out;
173 }
174 
calculateRealInlines()175 void ImportedFunctionsInliningStatistics::calculateRealInlines() {
176   // Removing duplicated Callers.
177   llvm::sort(NonImportedCallers);
178   NonImportedCallers.erase(
179       std::unique(NonImportedCallers.begin(), NonImportedCallers.end()),
180       NonImportedCallers.end());
181 
182   for (const auto &Name : NonImportedCallers) {
183     auto &Node = *NodesMap[Name];
184     if (!Node.Visited)
185       dfs(Node);
186   }
187 }
188 
dfs(InlineGraphNode & GraphNode)189 void ImportedFunctionsInliningStatistics::dfs(InlineGraphNode &GraphNode) {
190   assert(!GraphNode.Visited);
191   GraphNode.Visited = true;
192   for (auto *const InlinedFunctionNode : GraphNode.InlinedCallees) {
193     InlinedFunctionNode->NumberOfRealInlines++;
194     if (!InlinedFunctionNode->Visited)
195       dfs(*InlinedFunctionNode);
196   }
197 }
198 
199 ImportedFunctionsInliningStatistics::SortedNodesTy
getSortedNodes()200 ImportedFunctionsInliningStatistics::getSortedNodes() {
201   SortedNodesTy SortedNodes;
202   SortedNodes.reserve(NodesMap.size());
203   for (const NodesMapTy::value_type &Node : NodesMap)
204     SortedNodes.push_back(&Node);
205 
206   llvm::sort(SortedNodes, [&](const SortedNodesTy::value_type &Lhs,
207                               const SortedNodesTy::value_type &Rhs) {
208     if (Lhs->second->NumberOfInlines != Rhs->second->NumberOfInlines)
209       return Lhs->second->NumberOfInlines > Rhs->second->NumberOfInlines;
210     if (Lhs->second->NumberOfRealInlines != Rhs->second->NumberOfRealInlines)
211       return Lhs->second->NumberOfRealInlines >
212              Rhs->second->NumberOfRealInlines;
213     return Lhs->first() < Rhs->first();
214   });
215   return SortedNodes;
216 }
217