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