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
24using namespace llvm;
25
26namespace llvm {
27cl::opt<InlinerFunctionImportStatsOpts> InlinerFunctionImportStats(
28 "inliner-function-import-stats",
29 cl::init(Val: 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} // namespace llvm
36
37ImportedFunctionsInliningStatistics::InlineGraphNode &
38ImportedFunctionsInliningStatistics::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(Kind: "thinlto_src_module");
44 }
45 return *ValueLookup;
46}
47
48void ImportedFunctionsInliningStatistics::recordInline(const Function &Caller,
49 const Function &Callee) {
50
51 InlineGraphNode &CallerNode = createInlineGraphNode(F: Caller);
52 InlineGraphNode &CalleeNode = createInlineGraphNode(F: 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(Elt: &CalleeNode);
65 if (!CallerNode.Imported) {
66 // We could avoid second lookup, but it would make the code ultra ugly.
67 auto It = NodesMap.find(Key: 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(x: It->first());
72 }
73}
74
75void 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(Kind: "thinlto_src_module"));
82 }
83}
84static 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
99void 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(res_arg: 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(Msg: "inlined functions", Fraction: InlinedFunctionsCount,
154 All: AllFunctions, PercentageOfMsg: "all functions")
155 << getStatString(Msg: "imported functions inlined anywhere",
156 Fraction: InlinedImportedFunctionsCount, All: ImportedFunctions,
157 PercentageOfMsg: "imported functions")
158 << getStatString(Msg: "imported functions inlined into importing module",
159 Fraction: InlinedImportedFunctionsToImportingModuleCount,
160 All: ImportedFunctions, PercentageOfMsg: "imported functions",
161 /*LineEnd=*/false)
162 << getStatString(Msg: ", remaining", Fraction: ImportedNotInlinedIntoModule,
163 All: ImportedFunctions, PercentageOfMsg: "imported functions")
164 << getStatString(Msg: "non-imported functions inlined anywhere",
165 Fraction: InlinedNotImportedFunctionsCount,
166 All: NotImportedFuncCount, PercentageOfMsg: "non-imported functions")
167 << getStatString(
168 Msg: "non-imported functions inlined into importing module",
169 Fraction: InlinedNotImportedFunctionsToImportingModuleCount,
170 All: NotImportedFuncCount, PercentageOfMsg: "non-imported functions");
171 Ostream.flush();
172 dbgs() << Out;
173}
174
175void ImportedFunctionsInliningStatistics::calculateRealInlines() {
176 // Removing duplicated Callers.
177 llvm::sort(C&: NonImportedCallers);
178 NonImportedCallers.erase(first: llvm::unique(R&: NonImportedCallers),
179 last: NonImportedCallers.end());
180
181 for (const auto &Name : NonImportedCallers) {
182 auto &Node = *NodesMap[Name];
183 if (!Node.Visited)
184 dfs(GraphNode&: Node);
185 }
186}
187
188void ImportedFunctionsInliningStatistics::dfs(InlineGraphNode &GraphNode) {
189 assert(!GraphNode.Visited);
190 GraphNode.Visited = true;
191 for (auto *const InlinedFunctionNode : GraphNode.InlinedCallees) {
192 InlinedFunctionNode->NumberOfRealInlines++;
193 if (!InlinedFunctionNode->Visited)
194 dfs(GraphNode&: *InlinedFunctionNode);
195 }
196}
197
198ImportedFunctionsInliningStatistics::SortedNodesTy
199ImportedFunctionsInliningStatistics::getSortedNodes() {
200 SortedNodesTy SortedNodes;
201 SortedNodes.reserve(n: NodesMap.size());
202 for (const NodesMapTy::value_type &Node : NodesMap)
203 SortedNodes.push_back(x: &Node);
204
205 llvm::sort(C&: SortedNodes, Comp: [&](const SortedNodesTy::value_type &Lhs,
206 const SortedNodesTy::value_type &Rhs) {
207 if (Lhs->second->NumberOfInlines != Rhs->second->NumberOfInlines)
208 return Lhs->second->NumberOfInlines > Rhs->second->NumberOfInlines;
209 if (Lhs->second->NumberOfRealInlines != Rhs->second->NumberOfRealInlines)
210 return Lhs->second->NumberOfRealInlines >
211 Rhs->second->NumberOfRealInlines;
212 return Lhs->first() < Rhs->first();
213 });
214 return SortedNodes;
215}
216