include/llvm/Transforms/Utils/CodeExtractor.h

   1 //===- Transform/Utils/CodeExtractor.h - Code extraction util ---*- 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 //
   9 // A utility to support extracting code from one function into its own
  10 // stand-alone function.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
  15 #define LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H
  16
  17 #include "llvm/ADT/ArrayRef.h"
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/SetVector.h"
  20 #include "llvm/ADT/SmallPtrSet.h"
  21 #include <limits>
  22
  23 namespace llvm {
  24
  25 class BasicBlock;
  26 class BlockFrequency;
  27 class BlockFrequencyInfo;
  28 class BranchProbabilityInfo;
  29 class AssumptionCache;
  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     AssumptionCache *AC;
  61
  62     // If true, varargs functions can be extracted.
  63     bool AllowVarArgs;
  64
  65     // Bits of intermediate state computed at various phases of extraction.
  66     SetVector<BasicBlock *> Blocks;
  67     unsigned NumExitBlocks = std::numeric_limits<unsigned>::max();
  68     Type *RetTy;
  69
  70     // Suffix to use when creating extracted function (appended to the original
  71     // function name + "."). If empty, the default is to use the entry block
  72     // label, if non-empty, otherwise "extracted".
  73     std::string Suffix;
  74
  75   public:
  76     /// Create a code extractor for a sequence of blocks.
  77     ///
  78     /// Given a sequence of basic blocks where the first block in the sequence
  79     /// dominates the rest, prepare a code extractor object for pulling this
  80     /// sequence out into its new function. When a DominatorTree is also given,
  81     /// extra checking and transformations are enabled. If AllowVarArgs is true,
  82     /// vararg functions can be extracted. This is safe, if all vararg handling
  83     /// code is extracted, including vastart. If AllowAlloca is true, then
  84     /// extraction of blocks containing alloca instructions would be possible,
  85     /// however code extractor won't validate whether extraction is legal.
  86     CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr,
  87                   bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr,
  88                   BranchProbabilityInfo *BPI = nullptr,
  89                   AssumptionCache *AC = nullptr,
  90                   bool AllowVarArgs = false, bool AllowAlloca = false,
  91                   std::string Suffix = "");
  92
  93     /// Create a code extractor for a loop body.
  94     ///
  95     /// Behaves just like the generic code sequence constructor, but uses the
  96     /// block sequence of the loop.
  97     CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false,
  98                   BlockFrequencyInfo *BFI = nullptr,
  99                   BranchProbabilityInfo *BPI = nullptr,
 100                   AssumptionCache *AC = nullptr,
 101                   std::string Suffix = "");
 102
 103     /// Perform the extraction, returning the new function.
 104     ///
 105     /// Returns zero when called on a CodeExtractor instance where isEligible
 106     /// returns false.
 107     Function *extractCodeRegion();
 108
 109     /// Test whether this code extractor is eligible.
 110     ///
 111     /// Based on the blocks used when constructing the code extractor,
 112     /// determine whether it is eligible for extraction.
 113     bool isEligible() const { return !Blocks.empty(); }
 114
 115     /// Compute the set of input values and output values for the code.
 116     ///
 117     /// These can be used either when performing the extraction or to evaluate
 118     /// the expected size of a call to the extracted function. Note that this
 119     /// work cannot be cached between the two as once we decide to extract
 120     /// a code sequence, that sequence is modified, including changing these
 121     /// sets, before extraction occurs. These modifications won't have any
 122     /// significant impact on the cost however.
 123     void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs,
 124                            const ValueSet &Allocas) const;
 125
 126     /// Check if life time marker nodes can be hoisted/sunk into the outline
 127     /// region.
 128     ///
 129     /// Returns true if it is safe to do the code motion.
 130     bool isLegalToShrinkwrapLifetimeMarkers(Instruction *AllocaAddr) const;
 131
 132     /// Find the set of allocas whose life ranges are contained within the
 133     /// outlined region.
 134     ///
 135     /// Allocas which have life_time markers contained in the outlined region
 136     /// should be pushed to the outlined function. The address bitcasts that
 137     /// are used by the lifetime markers are also candidates for shrink-
 138     /// wrapping. The instructions that need to be sunk are collected in
 139     /// 'Allocas'.
 140     void findAllocas(ValueSet &SinkCands, ValueSet &HoistCands,
 141                      BasicBlock *&ExitBlock) const;
 142
 143     /// Find or create a block within the outline region for placing hoisted
 144     /// code.
 145     ///
 146     /// CommonExitBlock is block outside the outline region. It is the common
 147     /// successor of blocks inside the region. If there exists a single block
 148     /// inside the region that is the predecessor of CommonExitBlock, that block
 149     /// will be returned. Otherwise CommonExitBlock will be split and the
 150     /// original block will be added to the outline region.
 151     BasicBlock *findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock);
 152
 153   private:
 154     struct LifetimeMarkerInfo {
 155       bool SinkLifeStart = false;
 156       bool HoistLifeEnd = false;
 157       Instruction *LifeStart = nullptr;
 158       Instruction *LifeEnd = nullptr;
 159     };
 160
 161     LifetimeMarkerInfo getLifetimeMarkers(Instruction *Addr,
 162                                           BasicBlock *ExitBlock) const;
 163
 164     void severSplitPHINodesOfEntry(BasicBlock *&Header);
 165     void severSplitPHINodesOfExits(const SmallPtrSetImpl<BasicBlock *> &Exits);
 166     void splitReturnBlocks();
 167
 168     Function *constructFunction(const ValueSet &inputs,
 169                                 const ValueSet &outputs,
 170                                 BasicBlock *header,
 171                                 BasicBlock *newRootNode, BasicBlock *newHeader,
 172                                 Function *oldFunction, Module *M);
 173
 174     void moveCodeToFunction(Function *newFunction);
 175
 176     void calculateNewCallTerminatorWeights(
 177         BasicBlock *CodeReplacer,
 178         DenseMap<BasicBlock *, BlockFrequency> &ExitWeights,
 179         BranchProbabilityInfo *BPI);
 180
 181     CallInst *emitCallAndSwitchStatement(Function *newFunction,
 182                                          BasicBlock *newHeader,
 183                                          ValueSet &inputs, ValueSet &outputs);
 184   };
 185
 186 } // end namespace llvm
 187
 188 #endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H