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