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