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