1327952Sdim//===- Transform/Utils/CodeExtractor.h - Code extraction util ---*- C++ -*-===// 2239310Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6239310Sdim// 7239310Sdim//===----------------------------------------------------------------------===// 8239310Sdim// 9239310Sdim// A utility to support extracting code from one function into its own 10239310Sdim// stand-alone function. 11239310Sdim// 12239310Sdim//===----------------------------------------------------------------------===// 13239310Sdim 14280031Sdim#ifndef LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H 15280031Sdim#define LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H 16239310Sdim 17327952Sdim#include "llvm/ADT/ArrayRef.h" 18327952Sdim#include "llvm/ADT/DenseMap.h" 19239310Sdim#include "llvm/ADT/SetVector.h" 20344779Sdim#include "llvm/ADT/SmallPtrSet.h" 21327952Sdim#include <limits> 22239310Sdim 23239310Sdimnamespace llvm { 24239310Sdim 25360784Sdimclass AllocaInst; 26327952Sdimclass BasicBlock; 27327952Sdimclass BlockFrequency; 28327952Sdimclass BlockFrequencyInfo; 29327952Sdimclass BranchProbabilityInfo; 30353358Sdimclass AssumptionCache; 31344779Sdimclass CallInst; 32327952Sdimclass DominatorTree; 33327952Sdimclass Function; 34327952Sdimclass Instruction; 35327952Sdimclass Loop; 36327952Sdimclass Module; 37327952Sdimclass Type; 38327952Sdimclass Value; 39327952Sdim 40360784Sdim/// A cache for the CodeExtractor analysis. The operation \ref 41360784Sdim/// CodeExtractor::extractCodeRegion is guaranteed not to invalidate this 42360784Sdim/// object. This object should conservatively be considered invalid if any 43360784Sdim/// other mutating operations on the IR occur. 44360784Sdim/// 45360784Sdim/// Constructing this object is O(n) in the size of the function. 46360784Sdimclass CodeExtractorAnalysisCache { 47360784Sdim /// The allocas in the function. 48360784Sdim SmallVector<AllocaInst *, 16> Allocas; 49360784Sdim 50360784Sdim /// Base memory addresses of load/store instructions, grouped by block. 51360784Sdim DenseMap<BasicBlock *, DenseSet<Value *>> BaseMemAddrs; 52360784Sdim 53360784Sdim /// Blocks which contain instructions which may have unknown side-effects 54360784Sdim /// on memory. 55360784Sdim DenseSet<BasicBlock *> SideEffectingBlocks; 56360784Sdim 57360784Sdim void findSideEffectInfoForBlock(BasicBlock &BB); 58360784Sdim 59360784Sdimpublic: 60360784Sdim CodeExtractorAnalysisCache(Function &F); 61360784Sdim 62360784Sdim /// Get the allocas in the function at the time the analysis was created. 63360784Sdim /// Note that some of these allocas may no longer be present in the function, 64360784Sdim /// due to \ref CodeExtractor::extractCodeRegion. 65360784Sdim ArrayRef<AllocaInst *> getAllocas() const { return Allocas; } 66360784Sdim 67360784Sdim /// Check whether \p BB contains an instruction thought to load from, store 68360784Sdim /// to, or otherwise clobber the alloca \p Addr. 69360784Sdim bool doesBlockContainClobberOfAddr(BasicBlock &BB, AllocaInst *Addr) const; 70360784Sdim}; 71360784Sdim 72341825Sdim /// Utility class for extracting code into a new function. 73239310Sdim /// 74239310Sdim /// This utility provides a simple interface for extracting some sequence of 75239310Sdim /// code into its own function, replacing it with a call to that function. It 76239310Sdim /// also provides various methods to query about the nature and result of 77239310Sdim /// such a transformation. 78239310Sdim /// 79239310Sdim /// The rough algorithm used is: 80239310Sdim /// 1) Find both the inputs and outputs for the extracted region. 81239310Sdim /// 2) Pass the inputs as arguments, remapping them within the extracted 82239310Sdim /// function to arguments. 83239310Sdim /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas 84239310Sdim /// as arguments, and inserting stores to the arguments for any scalars. 85239310Sdim class CodeExtractor { 86327952Sdim using ValueSet = SetVector<Value *>; 87239310Sdim 88239310Sdim // Various bits of state computed on construction. 89239310Sdim DominatorTree *const DT; 90239310Sdim const bool AggregateArgs; 91314564Sdim BlockFrequencyInfo *BFI; 92314564Sdim BranchProbabilityInfo *BPI; 93353358Sdim AssumptionCache *AC; 94239310Sdim 95327952Sdim // If true, varargs functions can be extracted. 96327952Sdim bool AllowVarArgs; 97327952Sdim 98239310Sdim // Bits of intermediate state computed at various phases of extraction. 99239310Sdim SetVector<BasicBlock *> Blocks; 100327952Sdim unsigned NumExitBlocks = std::numeric_limits<unsigned>::max(); 101239310Sdim Type *RetTy; 102239310Sdim 103344779Sdim // Suffix to use when creating extracted function (appended to the original 104344779Sdim // function name + "."). If empty, the default is to use the entry block 105344779Sdim // label, if non-empty, otherwise "extracted". 106344779Sdim std::string Suffix; 107344779Sdim 108239310Sdim public: 109341825Sdim /// Create a code extractor for a sequence of blocks. 110239310Sdim /// 111239310Sdim /// Given a sequence of basic blocks where the first block in the sequence 112239310Sdim /// dominates the rest, prepare a code extractor object for pulling this 113239310Sdim /// sequence out into its new function. When a DominatorTree is also given, 114327952Sdim /// extra checking and transformations are enabled. If AllowVarArgs is true, 115327952Sdim /// vararg functions can be extracted. This is safe, if all vararg handling 116341825Sdim /// code is extracted, including vastart. If AllowAlloca is true, then 117341825Sdim /// extraction of blocks containing alloca instructions would be possible, 118341825Sdim /// however code extractor won't validate whether extraction is legal. 119276479Sdim CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr, 120314564Sdim bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr, 121327952Sdim BranchProbabilityInfo *BPI = nullptr, 122353358Sdim AssumptionCache *AC = nullptr, 123344779Sdim bool AllowVarArgs = false, bool AllowAlloca = false, 124344779Sdim std::string Suffix = ""); 125239310Sdim 126341825Sdim /// Create a code extractor for a loop body. 127239310Sdim /// 128239310Sdim /// Behaves just like the generic code sequence constructor, but uses the 129239310Sdim /// block sequence of the loop. 130314564Sdim CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false, 131314564Sdim BlockFrequencyInfo *BFI = nullptr, 132344779Sdim BranchProbabilityInfo *BPI = nullptr, 133353358Sdim AssumptionCache *AC = nullptr, 134344779Sdim std::string Suffix = ""); 135239310Sdim 136341825Sdim /// Perform the extraction, returning the new function. 137327952Sdim /// 138239310Sdim /// Returns zero when called on a CodeExtractor instance where isEligible 139239310Sdim /// returns false. 140360784Sdim Function *extractCodeRegion(const CodeExtractorAnalysisCache &CEAC); 141239310Sdim 142360784Sdim /// Verify that assumption cache isn't stale after a region is extracted. 143360784Sdim /// Returns false when verifier finds errors. AssumptionCache is passed as 144360784Sdim /// parameter to make this function stateless. 145360784Sdim static bool verifyAssumptionCache(const Function& F, AssumptionCache *AC); 146360784Sdim 147341825Sdim /// Test whether this code extractor is eligible. 148239310Sdim /// 149239310Sdim /// Based on the blocks used when constructing the code extractor, 150239310Sdim /// determine whether it is eligible for extraction. 151360784Sdim /// 152360784Sdim /// Checks that varargs handling (with vastart and vaend) is only done in 153360784Sdim /// the outlined blocks. 154360784Sdim bool isEligible() const; 155239310Sdim 156341825Sdim /// Compute the set of input values and output values for the code. 157239310Sdim /// 158239310Sdim /// These can be used either when performing the extraction or to evaluate 159239310Sdim /// the expected size of a call to the extracted function. Note that this 160239310Sdim /// work cannot be cached between the two as once we decide to extract 161239310Sdim /// a code sequence, that sequence is modified, including changing these 162239310Sdim /// sets, before extraction occurs. These modifications won't have any 163239310Sdim /// significant impact on the cost however. 164321369Sdim void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, 165321369Sdim const ValueSet &Allocas) const; 166239310Sdim 167321369Sdim /// Check if life time marker nodes can be hoisted/sunk into the outline 168321369Sdim /// region. 169321369Sdim /// 170321369Sdim /// Returns true if it is safe to do the code motion. 171360784Sdim bool 172360784Sdim isLegalToShrinkwrapLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC, 173360784Sdim Instruction *AllocaAddr) const; 174327952Sdim 175321369Sdim /// Find the set of allocas whose life ranges are contained within the 176321369Sdim /// outlined region. 177321369Sdim /// 178321369Sdim /// Allocas which have life_time markers contained in the outlined region 179321369Sdim /// should be pushed to the outlined function. The address bitcasts that 180321369Sdim /// are used by the lifetime markers are also candidates for shrink- 181321369Sdim /// wrapping. The instructions that need to be sunk are collected in 182321369Sdim /// 'Allocas'. 183360784Sdim void findAllocas(const CodeExtractorAnalysisCache &CEAC, 184360784Sdim ValueSet &SinkCands, ValueSet &HoistCands, 185321369Sdim BasicBlock *&ExitBlock) const; 186321369Sdim 187321369Sdim /// Find or create a block within the outline region for placing hoisted 188321369Sdim /// code. 189321369Sdim /// 190321369Sdim /// CommonExitBlock is block outside the outline region. It is the common 191321369Sdim /// successor of blocks inside the region. If there exists a single block 192321369Sdim /// inside the region that is the predecessor of CommonExitBlock, that block 193321369Sdim /// will be returned. Otherwise CommonExitBlock will be split and the 194321369Sdim /// original block will be added to the outline region. 195321369Sdim BasicBlock *findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock); 196321369Sdim 197239310Sdim private: 198353358Sdim struct LifetimeMarkerInfo { 199353358Sdim bool SinkLifeStart = false; 200353358Sdim bool HoistLifeEnd = false; 201353358Sdim Instruction *LifeStart = nullptr; 202353358Sdim Instruction *LifeEnd = nullptr; 203353358Sdim }; 204353358Sdim 205360784Sdim LifetimeMarkerInfo 206360784Sdim getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC, 207360784Sdim Instruction *Addr, BasicBlock *ExitBlock) const; 208353358Sdim 209344779Sdim void severSplitPHINodesOfEntry(BasicBlock *&Header); 210344779Sdim void severSplitPHINodesOfExits(const SmallPtrSetImpl<BasicBlock *> &Exits); 211239310Sdim void splitReturnBlocks(); 212239310Sdim 213239310Sdim Function *constructFunction(const ValueSet &inputs, 214239310Sdim const ValueSet &outputs, 215239310Sdim BasicBlock *header, 216239310Sdim BasicBlock *newRootNode, BasicBlock *newHeader, 217239310Sdim Function *oldFunction, Module *M); 218239310Sdim 219239310Sdim void moveCodeToFunction(Function *newFunction); 220239310Sdim 221314564Sdim void calculateNewCallTerminatorWeights( 222314564Sdim BasicBlock *CodeReplacer, 223314564Sdim DenseMap<BasicBlock *, BlockFrequency> &ExitWeights, 224314564Sdim BranchProbabilityInfo *BPI); 225314564Sdim 226344779Sdim CallInst *emitCallAndSwitchStatement(Function *newFunction, 227344779Sdim BasicBlock *newHeader, 228344779Sdim ValueSet &inputs, ValueSet &outputs); 229239310Sdim }; 230239310Sdim 231327952Sdim} // end namespace llvm 232327952Sdim 233327952Sdim#endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H 234