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