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/ArrayRef.h"
  19 #include "llvm/ADT/SetVector.h"
  20
  21 namespace llvm {
  22   class BasicBlock;
  23   class DominatorTree;
  24   class Function;
  25   class Loop;
  26   class Module;
  27   class RegionNode;
  28   class Type;
  29   class Value;
  30
  31   /// \brief Utility class for extracting code into a new function.
  32   ///
  33   /// This utility provides a simple interface for extracting some sequence of
  34   /// code into its own function, replacing it with a call to that function. It
  35   /// also provides various methods to query about the nature and result of
  36   /// such a transformation.
  37   ///
  38   /// The rough algorithm used is:
  39   /// 1) Find both the inputs and outputs for the extracted region.
  40   /// 2) Pass the inputs as arguments, remapping them within the extracted
  41   ///    function to arguments.
  42   /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas
  43   ///    as arguments, and inserting stores to the arguments for any scalars.
  44   class CodeExtractor {
  45     typedef SetVector<Value *> ValueSet;
  46
  47     // Various bits of state computed on construction.
  48     DominatorTree *const DT;
  49     const bool AggregateArgs;
  50
  51     // Bits of intermediate state computed at various phases of extraction.
  52     SetVector<BasicBlock *> Blocks;
  53     unsigned NumExitBlocks;
  54     Type *RetTy;
  55
  56   public:
  57     /// \brief Create a code extractor for a single basic block.
  58     ///
  59     /// In this formation, we don't require a dominator tree. The given basic
  60     /// block is set up for extraction.
  61     CodeExtractor(BasicBlock *BB, bool AggregateArgs = false);
  62
  63     /// \brief Create a code extractor for a sequence of blocks.
  64     ///
  65     /// Given a sequence of basic blocks where the first block in the sequence
  66     /// dominates the rest, prepare a code extractor object for pulling this
  67     /// sequence out into its new function. When a DominatorTree is also given,
  68     /// extra checking and transformations are enabled.
  69     CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr,
  70                   bool AggregateArgs = false);
  71
  72     /// \brief Create a code extractor for a loop body.
  73     ///
  74     /// Behaves just like the generic code sequence constructor, but uses the
  75     /// block sequence of the loop.
  76     CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false);
  77
  78     /// \brief Create a code extractor for a region node.
  79     ///
  80     /// Behaves just like the generic code sequence constructor, but uses the
  81     /// block sequence of the region node passed in.
  82     CodeExtractor(DominatorTree &DT, const RegionNode &RN,
  83                   bool AggregateArgs = false);
  84
  85     /// \brief Perform the extraction, returning the new function.
  86     ///
  87     /// Returns zero when called on a CodeExtractor instance where isEligible
  88     /// returns false.
  89     Function *extractCodeRegion();
  90
  91     /// \brief Test whether this code extractor is eligible.
  92     ///
  93     /// Based on the blocks used when constructing the code extractor,
  94     /// determine whether it is eligible for extraction.
  95     bool isEligible() const { return !Blocks.empty(); }
  96
  97     /// \brief Compute the set of input values and output values for the code.
  98     ///
  99     /// These can be used either when performing the extraction or to evaluate
 100     /// the expected size of a call to the extracted function. Note that this
 101     /// work cannot be cached between the two as once we decide to extract
 102     /// a code sequence, that sequence is modified, including changing these
 103     /// sets, before extraction occurs. These modifications won't have any
 104     /// significant impact on the cost however.
 105     void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs) const;
 106
 107   private:
 108     void severSplitPHINodes(BasicBlock *&Header);
 109     void splitReturnBlocks();
 110
 111     Function *constructFunction(const ValueSet &inputs,
 112                                 const ValueSet &outputs,
 113                                 BasicBlock *header,
 114                                 BasicBlock *newRootNode, BasicBlock *newHeader,
 115                                 Function *oldFunction, Module *M);
 116
 117     void moveCodeToFunction(Function *newFunction);
 118
 119     void emitCallAndSwitchStatement(Function *newFunction,
 120                                     BasicBlock *newHeader,
 121                                     ValueSet &inputs,
 122                                     ValueSet &outputs);
 123   };
 124 }
 125
 126 #endif