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