lib/Transforms/Utils/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/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>
  21 using namespace llvm;
  22
  23 ImportedFunctionsInliningStatistics::InlineGraphNode &
  24 ImportedFunctionsInliningStatistics::createInlineGraphNode(const Function &F) {
  25
  26   auto &ValueLookup = NodesMap[F.getName()];
  27   if (!ValueLookup) {
  28     ValueLookup = std::make_unique<InlineGraphNode>();
  29     ValueLookup->Imported = F.getMetadata("thinlto_src_module") != nullptr;
  30   }
  31   return *ValueLookup;
  32 }
  33
  34 void 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
  61 void 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.getMetadata("thinlto_src_module") != nullptr);
  68   }
  69 }
  70 static 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
  85 void 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
 161 void 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
 175 void 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
 185 ImportedFunctionsInliningStatistics::SortedNodesTy
 186 ImportedFunctionsInliningStatistics::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 }