contrib/llvm/include/llvm/Transforms/Utils/CodeExtractor.h

   1 //===-- Transform/Utils/CodeExtractor.h - Code extraction util --*- 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 //
  10 // A utility to support extracting code from one function into its own
  11 // stand-alone function.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
  16 #define LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
  17
  18 #include "llvm/ADT/SetVector.h"
  19
  20 namespace llvm {
  21 template <typename T> class ArrayRef;
  22   class BasicBlock;
  23   class BlockFrequency;
  24   class BlockFrequencyInfo;
  25   class BranchProbabilityInfo;
  26   class DominatorTree;
  27   class Function;
  28   class Instruction;
  29   class Loop;
  30   class Module;
  31   class RegionNode;
  32   class Type;
  33   class Value;
  34
  35   /// \brief Utility class for extracting code into a new function.
  36   ///
  37   /// This utility provides a simple interface for extracting some sequence of
  38   /// code into its own function, replacing it with a call to that function. It
  39   /// also provides various methods to query about the nature and result of
  40   /// such a transformation.
  41   ///
  42   /// The rough algorithm used is:
  43   /// 1) Find both the inputs and outputs for the extracted region.
  44   /// 2) Pass the inputs as arguments, remapping them within the extracted
  45   ///    function to arguments.
  46   /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas
  47   ///    as arguments, and inserting stores to the arguments for any scalars.
  48   class CodeExtractor {
  49     typedef SetVector<Value *> ValueSet;
  50
  51     // Various bits of state computed on construction.
  52     DominatorTree *const DT;
  53     const bool AggregateArgs;
  54     BlockFrequencyInfo *BFI;
  55     BranchProbabilityInfo *BPI;
  56
  57     // Bits of intermediate state computed at various phases of extraction.
  58     SetVector<BasicBlock *> Blocks;
  59     unsigned NumExitBlocks;
  60     Type *RetTy;
  61
  62   public:
  63
  64     /// \brief Check to see if a block is valid for extraction.
  65     ///
  66     /// Blocks containing EHPads, allocas, invokes, or vastarts are not valid.
  67     static bool isBlockValidForExtraction(const BasicBlock &BB);
  68
  69     /// \brief Create a code extractor for a sequence of blocks.
  70     ///
  71     /// Given a sequence of basic blocks where the first block in the sequence
  72     /// dominates the rest, prepare a code extractor object for pulling this
  73     /// sequence out into its new function. When a DominatorTree is also given,
  74     /// extra checking and transformations are enabled.
  75     CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr,
  76                   bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr,
  77                   BranchProbabilityInfo *BPI = nullptr);
  78
  79     /// \brief Create a code extractor for a loop body.
  80     ///
  81     /// Behaves just like the generic code sequence constructor, but uses the
  82     /// block sequence of the loop.
  83     CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false,
  84                   BlockFrequencyInfo *BFI = nullptr,
  85                   BranchProbabilityInfo *BPI = nullptr);
  86
  87     /// \brief Perform the extraction, returning the new function.
  88     ///
  89     /// Returns zero when called on a CodeExtractor instance where isEligible
  90     /// returns false.
  91     Function *extractCodeRegion();
  92
  93     /// \brief Test whether this code extractor is eligible.
  94     ///
  95     /// Based on the blocks used when constructing the code extractor,
  96     /// determine whether it is eligible for extraction.
  97     bool isEligible() const { return !Blocks.empty(); }
  98
  99     /// \brief Compute the set of input values and output values for the code.
 100     ///
 101     /// These can be used either when performing the extraction or to evaluate
 102     /// the expected size of a call to the extracted function. Note that this
 103     /// work cannot be cached between the two as once we decide to extract
 104     /// a code sequence, that sequence is modified, including changing these
 105     /// sets, before extraction occurs. These modifications won't have any
 106     /// significant impact on the cost however.
 107     void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
 108                            const ValueSet &Allocas) const;
 109     /// Find the set of allocas whose life ranges are contained within the
 110     /// outlined region.
 111     ///
 112     /// Allocas which have life_time markers contained in the outlined region
 113     /// should be pushed to the outlined function. The address bitcasts that
 114     /// are used by the lifetime markers are also candidates for shrink-
 115     /// wrapping. The instructions that need to be sinked are collected in
 116     /// 'Allocas'.
 117     void findAllocas(ValueSet &Allocas) const;
 118
 119   private:
 120     void severSplitPHINodes(BasicBlock *&Header);
 121     void splitReturnBlocks();
 122
 123     Function *constructFunction(const ValueSet &inputs,
 124                                 const ValueSet &outputs,
 125                                 BasicBlock *header,
 126                                 BasicBlock *newRootNode, BasicBlock *newHeader,
 127                                 Function *oldFunction, Module *M);
 128
 129     void moveCodeToFunction(Function *newFunction);
 130
 131     void calculateNewCallTerminatorWeights(
 132         BasicBlock *CodeReplacer,
 133         DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,
 134         BranchProbabilityInfo *BPI);
 135
 136     void emitCallAndSwitchStatement(Function *newFunction,
 137                                     BasicBlock *newHeader,
 138                                     ValueSet &inputs,
 139                                     ValueSet &outputs);
 140   };
 141 }
 142
 143 #endif