Home | History | Annotate | Line # | Download | only in Utils 
      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