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/Support/Compiler.h" 21 #include <limits> 22 23 namespace llvm { 24 25 template <typename PtrType> class SmallPtrSetImpl; 26 class AllocaInst; 27 class BasicBlock; 28 class BlockFrequency; 29 class BlockFrequencyInfo; 30 class BranchProbabilityInfo; 31 class AssumptionCache; 32 class CallInst; 33 class DominatorTree; 34 class Function; 35 class Instruction; 36 class Module; 37 class Type; 38 class Value; 39 class StructType; 40 41 /// A cache for the CodeExtractor analysis. The operation \ref 42 /// CodeExtractor::extractCodeRegion is guaranteed not to invalidate this 43 /// object. This object should conservatively be considered invalid if any 44 /// other mutating operations on the IR occur. 45 /// 46 /// Constructing this object is O(n) in the size of the function. 47 class CodeExtractorAnalysisCache { 48 /// The allocas in the function. 49 SmallVector<AllocaInst *, 16> Allocas; 50 51 /// Base memory addresses of load/store instructions, grouped by block. 52 DenseMap<BasicBlock *, DenseSet<Value *>> BaseMemAddrs; 53 54 /// Blocks which contain instructions which may have unknown side-effects 55 /// on memory. 56 DenseSet<BasicBlock *> SideEffectingBlocks; 57 58 void findSideEffectInfoForBlock(BasicBlock &BB); 59 60 public: 61 LLVM_ABI CodeExtractorAnalysisCache(Function &F); 62 63 /// Get the allocas in the function at the time the analysis was created. 64 /// Note that some of these allocas may no longer be present in the function, 65 /// due to \ref CodeExtractor::extractCodeRegion. getAllocas()66 ArrayRef<AllocaInst *> getAllocas() const { return Allocas; } 67 68 /// Check whether \p BB contains an instruction thought to load from, store 69 /// to, or otherwise clobber the alloca \p Addr. 70 LLVM_ABI bool doesBlockContainClobberOfAddr(BasicBlock &BB, 71 AllocaInst *Addr) const; 72 }; 73 74 /// Utility class for extracting code into a new function. 75 /// 76 /// This utility provides a simple interface for extracting some sequence of 77 /// code into its own function, replacing it with a call to that function. It 78 /// also provides various methods to query about the nature and result of 79 /// such a transformation. 80 /// 81 /// The rough algorithm used is: 82 /// 1) Find both the inputs and outputs for the extracted region. 83 /// 2) Pass the inputs as arguments, remapping them within the extracted 84 /// function to arguments. 85 /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas 86 /// as arguments, and inserting stores to the arguments for any scalars. 87 class CodeExtractor { 88 using ValueSet = SetVector<Value *>; 89 90 // Various bits of state computed on construction. 91 DominatorTree *const DT; 92 const bool AggregateArgs; 93 BlockFrequencyInfo *BFI; 94 BranchProbabilityInfo *BPI; 95 AssumptionCache *AC; 96 97 // A block outside of the extraction set where any intermediate 98 // allocations will be placed inside. If this is null, allocations 99 // will be placed in the entry block of the function. 100 BasicBlock *AllocationBlock; 101 102 // If true, varargs functions can be extracted. 103 bool AllowVarArgs; 104 105 // Bits of intermediate state computed at various phases of extraction. 106 SetVector<BasicBlock *> Blocks; 107 108 /// Lists of blocks that are branched from the code region to be extracted, 109 /// also called the exit blocks. Each block is contained at most once. Its 110 /// order defines the return value of the extracted function. 111 /// 112 /// When there is just one (or no) exit block, the return value is 113 /// irrelevant. 114 /// 115 /// When there are exactly two exit blocks, the extracted function returns a 116 /// boolean. For ExtractedFuncRetVals[0], it returns 'true'. For 117 /// ExtractedFuncRetVals[1] it returns 'false'. 118 /// NOTE: Since a boolean is represented by i1, ExtractedFuncRetVals[0] 119 /// returns 1 and ExtractedFuncRetVals[1] returns 0, which opposite 120 /// of the regular pattern below. 121 /// 122 /// When there are 3 or more exit blocks, leaving the extracted function via 123 /// the first block it returns 0. When leaving via the second entry it 124 /// returns 1, etc. 125 SmallVector<BasicBlock *> ExtractedFuncRetVals; 126 127 // Suffix to use when creating extracted function (appended to the original 128 // function name + "."). If empty, the default is to use the entry block 129 // label, if non-empty, otherwise "extracted". 130 std::string Suffix; 131 132 // If true, the outlined function has aggregate argument in zero address 133 // space. 134 bool ArgsInZeroAddressSpace; 135 136 public: 137 /// Create a code extractor for a sequence of blocks. 138 /// 139 /// Given a sequence of basic blocks where the first block in the sequence 140 /// dominates the rest, prepare a code extractor object for pulling this 141 /// sequence out into its new function. When a DominatorTree is also given, 142 /// extra checking and transformations are enabled. If AllowVarArgs is true, 143 /// vararg functions can be extracted. This is safe, if all vararg handling 144 /// code is extracted, including vastart. If AllowAlloca is true, then 145 /// extraction of blocks containing alloca instructions would be possible, 146 /// however code extractor won't validate whether extraction is legal. 147 /// Any new allocations will be placed in the AllocationBlock, unless 148 /// it is null, in which case it will be placed in the entry block of 149 /// the function from which the code is being extracted. 150 /// If ArgsInZeroAddressSpace param is set to true, then the aggregate 151 /// param pointer of the outlined function is declared in zero address 152 /// space. 153 LLVM_ABI 154 CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr, 155 bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr, 156 BranchProbabilityInfo *BPI = nullptr, 157 AssumptionCache *AC = nullptr, bool AllowVarArgs = false, 158 bool AllowAlloca = false, 159 BasicBlock *AllocationBlock = nullptr, 160 std::string Suffix = "", bool ArgsInZeroAddressSpace = false); 161 162 /// Perform the extraction, returning the new function. 163 /// 164 /// Returns zero when called on a CodeExtractor instance where isEligible 165 /// returns false. 166 LLVM_ABI Function * 167 extractCodeRegion(const CodeExtractorAnalysisCache &CEAC); 168 169 /// Perform the extraction, returning the new function and providing an 170 /// interface to see what was categorized as inputs and outputs. 171 /// 172 /// \param CEAC - Cache to speed up operations for the CodeExtractor when 173 /// hoisting, and extracting lifetime values and assumes. 174 /// \param Inputs [out] - filled with values marked as inputs to the 175 /// newly outlined function. 176 /// \param Outputs [out] - filled with values marked as outputs to the 177 /// newly outlined function. 178 /// \returns zero when called on a CodeExtractor instance where isEligible 179 /// returns false. 180 LLVM_ABI Function *extractCodeRegion(const CodeExtractorAnalysisCache &CEAC, 181 ValueSet &Inputs, ValueSet &Outputs); 182 183 /// Verify that assumption cache isn't stale after a region is extracted. 184 /// Returns true when verifier finds errors. AssumptionCache is passed as 185 /// parameter to make this function stateless. 186 LLVM_ABI static bool verifyAssumptionCache(const Function &OldFunc, 187 const Function &NewFunc, 188 AssumptionCache *AC); 189 190 /// Test whether this code extractor is eligible. 191 /// 192 /// Based on the blocks used when constructing the code extractor, 193 /// determine whether it is eligible for extraction. 194 /// 195 /// Checks that varargs handling (with vastart and vaend) is only done in 196 /// the outlined blocks. 197 LLVM_ABI bool isEligible() const; 198 199 /// Compute the set of input values and output values for the code. 200 /// 201 /// These can be used either when performing the extraction or to evaluate 202 /// the expected size of a call to the extracted function. Note that this 203 /// work cannot be cached between the two as once we decide to extract 204 /// a code sequence, that sequence is modified, including changing these 205 /// sets, before extraction occurs. These modifications won't have any 206 /// significant impact on the cost however. 207 LLVM_ABI void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, 208 const ValueSet &Allocas, 209 bool CollectGlobalInputs = false) const; 210 211 /// Check if life time marker nodes can be hoisted/sunk into the outline 212 /// region. 213 /// 214 /// Returns true if it is safe to do the code motion. 215 LLVM_ABI bool 216 isLegalToShrinkwrapLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC, 217 Instruction *AllocaAddr) const; 218 219 /// Find the set of allocas whose life ranges are contained within the 220 /// outlined region. 221 /// 222 /// Allocas which have life_time markers contained in the outlined region 223 /// should be pushed to the outlined function. The address bitcasts that 224 /// are used by the lifetime markers are also candidates for shrink- 225 /// wrapping. The instructions that need to be sunk are collected in 226 /// 'Allocas'. 227 LLVM_ABI void findAllocas(const CodeExtractorAnalysisCache &CEAC, 228 ValueSet &SinkCands, ValueSet &HoistCands, 229 BasicBlock *&ExitBlock) const; 230 231 /// Find or create a block within the outline region for placing hoisted 232 /// code. 233 /// 234 /// CommonExitBlock is block outside the outline region. It is the common 235 /// successor of blocks inside the region. If there exists a single block 236 /// inside the region that is the predecessor of CommonExitBlock, that block 237 /// will be returned. Otherwise CommonExitBlock will be split and the 238 /// original block will be added to the outline region. 239 LLVM_ABI BasicBlock * 240 findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock); 241 242 /// Exclude a value from aggregate argument passing when extracting a code 243 /// region, passing it instead as a scalar. 244 LLVM_ABI void excludeArgFromAggregate(Value *Arg); 245 246 private: 247 struct LifetimeMarkerInfo { 248 bool SinkLifeStart = false; 249 bool HoistLifeEnd = false; 250 Instruction *LifeStart = nullptr; 251 Instruction *LifeEnd = nullptr; 252 }; 253 254 ValueSet ExcludeArgsFromAggregate; 255 256 LifetimeMarkerInfo 257 getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC, 258 Instruction *Addr, BasicBlock *ExitBlock) const; 259 260 /// Updates the list of SwitchCases (corresponding to exit blocks) after 261 /// changes of the control flow or the Blocks list. 262 void computeExtractedFuncRetVals(); 263 264 /// Return the type used for the return code of the extracted function to 265 /// indicate which exit block to jump to. 266 Type *getSwitchType(); 267 268 void severSplitPHINodesOfEntry(BasicBlock *&Header); 269 void severSplitPHINodesOfExits(); 270 void splitReturnBlocks(); 271 272 void moveCodeToFunction(Function *newFunction); 273 274 void calculateNewCallTerminatorWeights( 275 BasicBlock *CodeReplacer, 276 const DenseMap<BasicBlock *, BlockFrequency> &ExitWeights, 277 BranchProbabilityInfo *BPI); 278 279 /// Normalizes the control flow of the extracted regions, such as ensuring 280 /// that the extracted region does not contain a return instruction. 281 void normalizeCFGForExtraction(BasicBlock *&header); 282 283 /// Generates the function declaration for the function containing the 284 /// extracted code. 285 Function *constructFunctionDeclaration(const ValueSet &inputs, 286 const ValueSet &outputs, 287 BlockFrequency EntryFreq, 288 const Twine &Name, 289 ValueSet &StructValues, 290 StructType *&StructTy); 291 292 /// Generates the code for the extracted function. That is: a prolog, the 293 /// moved or copied code from the original function, and epilogs for each 294 /// exit. 295 void emitFunctionBody(const ValueSet &inputs, const ValueSet &outputs, 296 const ValueSet &StructValues, Function *newFunction, 297 StructType *StructArgTy, BasicBlock *header, 298 const ValueSet &SinkingCands, 299 SmallVectorImpl<Value *> &NewValues); 300 301 /// Generates a Basic Block that calls the extracted function. 302 CallInst *emitReplacerCall(const ValueSet &inputs, const ValueSet &outputs, 303 const ValueSet &StructValues, 304 Function *newFunction, StructType *StructArgTy, 305 Function *oldFunction, BasicBlock *ReplIP, 306 BlockFrequency EntryFreq, 307 ArrayRef<Value *> LifetimesStart, 308 std::vector<Value *> &Reloads); 309 310 /// Connects the basic block containing the call to the extracted function 311 /// into the original function's control flow. 312 void insertReplacerCall( 313 Function *oldFunction, BasicBlock *header, BasicBlock *codeReplacer, 314 const ValueSet &outputs, ArrayRef<Value *> Reloads, 315 const DenseMap<BasicBlock *, BlockFrequency> &ExitWeights); 316 }; 317 318 } // end namespace llvm 319 320 #endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H 321