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