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 &
createInlineGraphNode(const Function & F)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
recordInline(const Function & Caller,const Function & Callee)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
setModuleInfo(const Module & M)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 }
getStatString(const char * Msg,int32_t Fraction,int32_t All,const char * PercentageOfMsg,bool LineEnd=true)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
dump(const bool Verbose)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
calculateRealInlines()162 void ImportedFunctionsInliningStatistics::calculateRealInlines() {
163 // Removing duplicated Callers.
164 llvm::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
dfs(InlineGraphNode & GraphNode)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
getSortedNodes()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 llvm::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 !=
200 Rhs->second->NumberOfRealInlines)
201 return Lhs->second->NumberOfRealInlines >
202 Rhs->second->NumberOfRealInlines;
203 return Lhs->first() < Rhs->first();
204 });
205 return SortedNodes;
206 }
207