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 /// \brief 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 // Bits of intermediate state computed at various phases of extraction. 60 SetVector<BasicBlock *> Blocks; 61 unsigned NumExitBlocks = std::numeric_limits<unsigned>::max(); 62 Type *RetTy; 63 64 public: 65 /// \brief Create a code extractor for a sequence of blocks. 66 /// 67 /// Given a sequence of basic blocks where the first block in the sequence 68 /// dominates the rest, prepare a code extractor object for pulling this 69 /// sequence out into its new function. When a DominatorTree is also given, 70 /// extra checking and transformations are enabled. 71 CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr, 72 bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr, 73 BranchProbabilityInfo *BPI = nullptr); 74 75 /// \brief Create a code extractor for a loop body. 76 /// 77 /// Behaves just like the generic code sequence constructor, but uses the 78 /// block sequence of the loop. 79 CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false, 80 BlockFrequencyInfo *BFI = nullptr, 81 BranchProbabilityInfo *BPI = nullptr); 82 83 /// \brief Check to see if a block is valid for extraction. 84 /// 85 /// Blocks containing EHPads, allocas, invokes, or vastarts are not valid. 86 static bool isBlockValidForExtraction(const BasicBlock &BB); 87 88 /// \brief Perform the extraction, returning the new function. 89 /// 90 /// Returns zero when called on a CodeExtractor instance where isEligible 91 /// returns false. 92 Function *extractCodeRegion(); 93 94 /// \brief Test whether this code extractor is eligible. 95 /// 96 /// Based on the blocks used when constructing the code extractor, 97 /// determine whether it is eligible for extraction. 98 bool isEligible() const { return !Blocks.empty(); } 99 100 /// \brief Compute the set of input values and output values for the code. 101 /// 102 /// These can be used either when performing the extraction or to evaluate 103 /// the expected size of a call to the extracted function. Note that this 104 /// work cannot be cached between the two as once we decide to extract 105 /// a code sequence, that sequence is modified, including changing these 106 /// sets, before extraction occurs. These modifications won't have any 107 /// significant impact on the cost however. 108 void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, 109 const ValueSet &Allocas) const; 110 111 /// Check if life time marker nodes can be hoisted/sunk into the outline 112 /// region. 113 /// 114 /// Returns true if it is safe to do the code motion. 115 bool isLegalToShrinkwrapLifetimeMarkers(Instruction *AllocaAddr) const; 116 117 /// Find the set of allocas whose life ranges are contained within the 118 /// outlined region. 119 /// 120 /// Allocas which have life_time markers contained in the outlined region 121 /// should be pushed to the outlined function. The address bitcasts that 122 /// are used by the lifetime markers are also candidates for shrink- 123 /// wrapping. The instructions that need to be sunk are collected in 124 /// 'Allocas'. 125 void findAllocas(ValueSet &SinkCands, ValueSet &HoistCands, 126 BasicBlock *&ExitBlock) const; 127 128 /// Find or create a block within the outline region for placing hoisted 129 /// code. 130 /// 131 /// CommonExitBlock is block outside the outline region. It is the common 132 /// successor of blocks inside the region. If there exists a single block 133 /// inside the region that is the predecessor of CommonExitBlock, that block 134 /// will be returned. Otherwise CommonExitBlock will be split and the 135 /// original block will be added to the outline region. 136 BasicBlock *findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock); 137 138 private: 139 void severSplitPHINodes(BasicBlock *&Header); 140 void splitReturnBlocks(); 141 142 Function *constructFunction(const ValueSet &inputs, 143 const ValueSet &outputs, 144 BasicBlock *header, 145 BasicBlock *newRootNode, BasicBlock *newHeader, 146 Function *oldFunction, Module *M); 147 148 void moveCodeToFunction(Function *newFunction); 149 150 void calculateNewCallTerminatorWeights( 151 BasicBlock *CodeReplacer, 152 DenseMap<BasicBlock *, BlockFrequency> &ExitWeights, 153 BranchProbabilityInfo *BPI); 154 155 void emitCallAndSwitchStatement(Function *newFunction, 156 BasicBlock *newHeader, 157 ValueSet &inputs, 158 ValueSet &outputs); 159 }; 160 161 } // end namespace llvm 162 163 #endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H 164
