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. isEligible()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 176