1 //===-- ImportedFunctionsInliningStatistics.h -------------------*- 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 #ifndef LLVM_ANALYSIS_UTILS_IMPORTEDFUNCTIONSINLININGSTATISTICS_H 13 #define LLVM_ANALYSIS_UTILS_IMPORTEDFUNCTIONSINLININGSTATISTICS_H 14 15 #include "llvm/ADT/SmallVector.h" 16 #include "llvm/ADT/StringMap.h" 17 #include "llvm/ADT/StringRef.h" 18 #include <memory> 19 #include <vector> 20 21 namespace llvm { 22 class Module; 23 class Function; 24 /// Calculate and dump ThinLTO specific inliner stats. 25 /// The main statistics are: 26 /// (1) Number of inlined imported functions, 27 /// (2) Number of imported functions inlined into importing module (indirect), 28 /// (3) Number of non imported functions inlined into importing module 29 /// (indirect). 30 /// The difference between first and the second is that first stat counts 31 /// all performed inlines on imported functions, but the second one only the 32 /// functions that have been eventually inlined to a function in the importing 33 /// module (by a chain of inlines). Because llvm uses bottom-up inliner, it is 34 /// possible to e.g. import function `A`, `B` and then inline `B` to `A`, 35 /// and after this `A` might be too big to be inlined into some other function 36 /// that calls it. It calculates this statistic by building graph, where 37 /// the nodes are functions, and edges are performed inlines and then by marking 38 /// the edges starting from not imported function. 39 /// 40 /// If `Verbose` is set to true, then it also dumps statistics 41 /// per each inlined function, sorted by the greatest inlines count like 42 /// - number of performed inlines 43 /// - number of performed inlines to importing module 44 class ImportedFunctionsInliningStatistics { 45 private: 46 /// InlineGraphNode represents node in graph of inlined functions. 47 struct InlineGraphNode { 48 // Default-constructible and movable. 49 InlineGraphNode() = default; 50 InlineGraphNode(InlineGraphNode &&) = default; 51 InlineGraphNode &operator=(InlineGraphNode &&) = default; 52 53 llvm::SmallVector<InlineGraphNode *, 8> InlinedCallees; 54 /// Incremented every direct inline. 55 int32_t NumberOfInlines = 0; 56 /// Number of inlines into non imported function (possibly indirect via 57 /// intermediate inlines). Computed based on graph search. 58 int32_t NumberOfRealInlines = 0; 59 bool Imported = false; 60 bool Visited = false; 61 }; 62 63 public: 64 ImportedFunctionsInliningStatistics() = default; 65 ImportedFunctionsInliningStatistics( 66 const ImportedFunctionsInliningStatistics &) = delete; 67 68 /// Set information like AllFunctions, ImportedFunctions, ModuleName. 69 void setModuleInfo(const Module &M); 70 /// Record inline of @param Callee to @param Caller for statistis. 71 void recordInline(const Function &Caller, const Function &Callee); 72 /// Dump stats computed with InlinerStatistics class. 73 /// If @param Verbose is true then separate statistics for every inlined 74 /// function will be printed. 75 void dump(bool Verbose); 76 77 private: 78 /// Creates new Node in NodeMap and sets attributes, or returns existed one. 79 InlineGraphNode &createInlineGraphNode(const Function &); 80 void calculateRealInlines(); 81 void dfs(InlineGraphNode &GraphNode); 82 83 using NodesMapTy = 84 llvm::StringMap<std::unique_ptr<InlineGraphNode>>; 85 using SortedNodesTy = 86 std::vector<const NodesMapTy::MapEntryTy*>; 87 /// Returns vector of elements sorted by 88 /// (-NumberOfInlines, -NumberOfRealInlines, FunctionName). 89 SortedNodesTy getSortedNodes(); 90 91 private: 92 /// This map manage life of all InlineGraphNodes. Unique pointer to 93 /// InlineGraphNode used since the node pointers are also saved in the 94 /// InlinedCallees vector. If it would store InlineGraphNode instead then the 95 /// address of the node would not be invariant. 96 NodesMapTy NodesMap; 97 /// Non external functions that have some other function inlined inside. 98 std::vector<StringRef> NonImportedCallers; 99 int AllFunctions = 0; 100 int ImportedFunctions = 0; 101 StringRef ModuleName; 102 }; 103 104 enum class InlinerFunctionImportStatsOpts { 105 No = 0, 106 Basic = 1, 107 Verbose = 2, 108 }; 109 110 } // llvm 111 112 #endif // LLVM_ANALYSIS_UTILS_IMPORTEDFUNCTIONSINLININGSTATISTICS_H 113