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