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/ArrayRef.h"
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/SetVector.h"
  21 #include "llvm/ADT/SmallPtrSet.h"
  22 #include <limits>
  23
  24 namespace llvm {
  25
  26 class BasicBlock;
  27 class BlockFrequency;
  28 class BlockFrequencyInfo;
  29 class BranchProbabilityInfo;
  30 class CallInst;
  31 class DominatorTree;
  32 class Function;
  33 class Instruction;
  34 class Loop;
  35 class Module;
  36 class Type;
  37 class Value;
  38
  39   /// Utility class for extracting code into a new function.
  40   ///
  41   /// This utility provides a simple interface for extracting some sequence of
  42   /// code into its own function, replacing it with a call to that function. It
  43   /// also provides various methods to query about the nature and result of
  44   /// such a transformation.
  45   ///
  46   /// The rough algorithm used is:
  47   /// 1) Find both the inputs and outputs for the extracted region.
  48   /// 2) Pass the inputs as arguments, remapping them within the extracted
  49   ///    function to arguments.
  50   /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas
  51   ///    as arguments, and inserting stores to the arguments for any scalars.
  52   class CodeExtractor {
  53     using ValueSet = SetVector<Value *>;
  54
  55     // Various bits of state computed on construction.
  56     DominatorTree *const DT;
  57     const bool AggregateArgs;
  58     BlockFrequencyInfo *BFI;
  59     BranchProbabilityInfo *BPI;
  60
  61     // If true, varargs functions can be extracted.
  62     bool AllowVarArgs;
  63
  64     // Bits of intermediate state computed at various phases of extraction.
  65     SetVector<BasicBlock *> Blocks;
  66     unsigned NumExitBlocks = std::numeric_limits<unsigned>::max();
  67     Type *RetTy;
  68
  69     // Suffix to use when creating extracted function (appended to the original
  70     // function name + "."). If empty, the default is to use the entry block
  71     // label, if non-empty, otherwise "extracted".
  72     std::string Suffix;
  73
  74   public:
  75     /// Create a code extractor for a sequence of blocks.
  76     ///
  77     /// Given a sequence of basic blocks where the first block in the sequence
  78     /// dominates the rest, prepare a code extractor object for pulling this
  79     /// sequence out into its new function. When a DominatorTree is also given,
  80     /// extra checking and transformations are enabled. If AllowVarArgs is true,
  81     /// vararg functions can be extracted. This is safe, if all vararg handling
  82     /// code is extracted, including vastart. If AllowAlloca is true, then
  83     /// extraction of blocks containing alloca instructions would be possible,
  84     /// however code extractor won't validate whether extraction is legal.
  85     CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr,
  86                   bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr,
  87                   BranchProbabilityInfo *BPI = nullptr,
  88                   bool AllowVarArgs = false, bool AllowAlloca = false,
  89                   std::string Suffix = "");
  90
  91     /// Create a code extractor for a loop body.
  92     ///
  93     /// Behaves just like the generic code sequence constructor, but uses the
  94     /// block sequence of the loop.
  95     CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false,
  96                   BlockFrequencyInfo *BFI = nullptr,
  97                   BranchProbabilityInfo *BPI = nullptr,
  98                   std::string Suffix = "");
  99
 100     /// Perform the extraction, returning the new function.
 101     ///
 102     /// Returns zero when called on a CodeExtractor instance where isEligible
 103     /// returns false.
 104     Function *extractCodeRegion();
 105
 106     /// Test whether this code extractor is eligible.
 107     ///
 108     /// Based on the blocks used when constructing the code extractor,
 109     /// determine whether it is eligible for extraction.
 110     bool isEligible() const { return !Blocks.empty(); }
 111
 112     /// Compute the set of input values and output values for the code.
 113     ///
 114     /// These can be used either when performing the extraction or to evaluate
 115     /// the expected size of a call to the extracted function. Note that this
 116     /// work cannot be cached between the two as once we decide to extract
 117     /// a code sequence, that sequence is modified, including changing these
 118     /// sets, before extraction occurs. These modifications won't have any
 119     /// significant impact on the cost however.
 120     void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
 121                            const ValueSet &Allocas) const;
 122
 123     /// Check if life time marker nodes can be hoisted/sunk into the outline
 124     /// region.
 125     ///
 126     /// Returns true if it is safe to do the code motion.
 127     bool isLegalToShrinkwrapLifetimeMarkers(Instruction *AllocaAddr) const;
 128
 129     /// Find the set of allocas whose life ranges are contained within the
 130     /// outlined region.
 131     ///
 132     /// Allocas which have life_time markers contained in the outlined region
 133     /// should be pushed to the outlined function. The address bitcasts that
 134     /// are used by the lifetime markers are also candidates for shrink-
 135     /// wrapping. The instructions that need to be sunk are collected in
 136     /// 'Allocas'.
 137     void findAllocas(ValueSet &SinkCands, ValueSet &HoistCands,
 138                      BasicBlock *&ExitBlock) const;
 139
 140     /// Find or create a block within the outline region for placing hoisted
 141     /// code.
 142     ///
 143     /// CommonExitBlock is block outside the outline region. It is the common
 144     /// successor of blocks inside the region. If there exists a single block
 145     /// inside the region that is the predecessor of CommonExitBlock, that block
 146     /// will be returned. Otherwise CommonExitBlock will be split and the
 147     /// original block will be added to the outline region.
 148     BasicBlock *findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock);
 149
 150   private:
 151     void severSplitPHINodesOfEntry(BasicBlock *&Header);
 152     void severSplitPHINodesOfExits(const SmallPtrSetImpl<BasicBlock *> &Exits);
 153     void splitReturnBlocks();
 154
 155     Function *constructFunction(const ValueSet &inputs,
 156                                 const ValueSet &outputs,
 157                                 BasicBlock *header,
 158                                 BasicBlock *newRootNode, BasicBlock *newHeader,
 159                                 Function *oldFunction, Module *M);
 160
 161     void moveCodeToFunction(Function *newFunction);
 162
 163     void calculateNewCallTerminatorWeights(
 164         BasicBlock *CodeReplacer,
 165         DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,
 166         BranchProbabilityInfo *BPI);
 167
 168     CallInst *emitCallAndSwitchStatement(Function *newFunction,
 169                                          BasicBlock *newHeader,
 170                                          ValueSet &inputs, ValueSet &outputs);
 171   };
 172
 173 } // end namespace llvm
 174
 175 #endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H