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