contrib/llvm/lib/Transforms/Utils/ImportedFunctionsInliningStatistics.cpp

   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 &
  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
  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
  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 }
  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
  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
 162 void ImportedFunctionsInliningStatistics::calculateRealInlines() {
 163   // Removing duplicated Callers.
 164   llvm::sort(NonImportedCallers);
 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
 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
 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(SortedNodes, [&](const SortedNodesTy::value_type &Lhs,
 194                               const SortedNodesTy::value_type &Rhs) {
 195     if (Lhs->second->NumberOfInlines != Rhs->second->NumberOfInlines)
 196       return Lhs->second->NumberOfInlines > Rhs->second->NumberOfInlines;
 197     if (Lhs->second->NumberOfRealInlines != Rhs->second->NumberOfRealInlines)
 198       return Lhs->second->NumberOfRealInlines >
 199              Rhs->second->NumberOfRealInlines;
 200     return Lhs->first() < Rhs->first();
 201   });
 202   return SortedNodes;
 203 }