llvm/lib/Analysis/ImportedFunctionsInliningStatistics.cpp

   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 &
  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
  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
  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 }
  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
  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
 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
 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
 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 }