| 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/Debug.h" |
| 17 | #include "llvm/Support/raw_ostream.h" |
| 18 | #include <iomanip> |
| 19 | #include <sstream> |
| 20 | #include <string> |
| 21 | |
| 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 = std::make_unique<InlineGraphNode>(); |
| 30 | ValueLookup->Imported = F.hasMetadata(Kind: "thinlto_src_module" ); |
| 31 | } |
| 32 | return *ValueLookup; |
| 33 | } |
| 34 | |
| 35 | void ImportedFunctionsInliningStatistics::recordInline(const Function &Caller, |
| 36 | const Function &Callee) { |
| 37 | |
| 38 | InlineGraphNode &CallerNode = createInlineGraphNode(F: Caller); |
| 39 | InlineGraphNode &CalleeNode = createInlineGraphNode(F: 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(Elt: &CalleeNode); |
| 52 | if (!CallerNode.Imported) { |
| 53 | // We could avoid second lookup, but it would make the code ultra ugly. |
| 54 | auto It = NodesMap.find(Key: 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(x: 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.hasMetadata(Kind: "thinlto_src_module" )); |
| 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(res_arg: 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(Msg: "inlined functions" , Fraction: InlinedFunctionsCount, |
| 141 | All: AllFunctions, PercentageOfMsg: "all functions" ) |
| 142 | << getStatString(Msg: "imported functions inlined anywhere" , |
| 143 | Fraction: InlinedImportedFunctionsCount, All: ImportedFunctions, |
| 144 | PercentageOfMsg: "imported functions" ) |
| 145 | << getStatString(Msg: "imported functions inlined into importing module" , |
| 146 | Fraction: InlinedImportedFunctionsToImportingModuleCount, |
| 147 | All: ImportedFunctions, PercentageOfMsg: "imported functions" , |
| 148 | /*LineEnd=*/false) |
| 149 | << getStatString(Msg: ", remaining" , Fraction: ImportedNotInlinedIntoModule, |
| 150 | All: ImportedFunctions, PercentageOfMsg: "imported functions" ) |
| 151 | << getStatString(Msg: "non-imported functions inlined anywhere" , |
| 152 | Fraction: InlinedNotImportedFunctionsCount, |
| 153 | All: NotImportedFuncCount, PercentageOfMsg: "non-imported functions" ) |
| 154 | << getStatString( |
| 155 | Msg: "non-imported functions inlined into importing module" , |
| 156 | Fraction: InlinedNotImportedFunctionsToImportingModuleCount, |
| 157 | All: NotImportedFuncCount, PercentageOfMsg: "non-imported functions" ); |
| 158 | dbgs() << Out; |
| 159 | } |
| 160 | |
| 161 | void ImportedFunctionsInliningStatistics::calculateRealInlines() { |
| 162 | // Removing duplicated Callers. |
| 163 | llvm::sort(C&: NonImportedCallers); |
| 164 | NonImportedCallers.erase(first: llvm::unique(R&: NonImportedCallers), |
| 165 | last: NonImportedCallers.end()); |
| 166 | |
| 167 | for (const auto &Name : NonImportedCallers) { |
| 168 | auto &Node = *NodesMap[Name]; |
| 169 | if (!Node.Visited) |
| 170 | dfs(GraphNode&: Node); |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | void ImportedFunctionsInliningStatistics::dfs(InlineGraphNode &GraphNode) { |
| 175 | assert(!GraphNode.Visited); |
| 176 | GraphNode.Visited = true; |
| 177 | for (auto *const InlinedFunctionNode : GraphNode.InlinedCallees) { |
| 178 | InlinedFunctionNode->NumberOfRealInlines++; |
| 179 | if (!InlinedFunctionNode->Visited) |
| 180 | dfs(GraphNode&: *InlinedFunctionNode); |
| 181 | } |
| 182 | } |
| 183 | |
| 184 | ImportedFunctionsInliningStatistics::SortedNodesTy |
| 185 | ImportedFunctionsInliningStatistics::getSortedNodes() { |
| 186 | SortedNodesTy SortedNodes; |
| 187 | SortedNodes.reserve(n: NodesMap.size()); |
| 188 | for (const NodesMapTy::value_type &Node : NodesMap) |
| 189 | SortedNodes.push_back(x: &Node); |
| 190 | |
| 191 | llvm::sort(C&: SortedNodes, Comp: [&](const SortedNodesTy::value_type &Lhs, |
| 192 | const SortedNodesTy::value_type &Rhs) { |
| 193 | if (Lhs->second->NumberOfInlines != Rhs->second->NumberOfInlines) |
| 194 | return Lhs->second->NumberOfInlines > Rhs->second->NumberOfInlines; |
| 195 | if (Lhs->second->NumberOfRealInlines != Rhs->second->NumberOfRealInlines) |
| 196 | return Lhs->second->NumberOfRealInlines > |
| 197 | Rhs->second->NumberOfRealInlines; |
| 198 | return Lhs->first() < Rhs->first(); |
| 199 | }); |
| 200 | return SortedNodes; |
| 201 | } |
| 202 | |