10b57cec5SDimitry Andric //===- Transform/Utils/CodeExtractor.h - Code extraction util ---*- C++ -*-===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // A utility to support extracting code from one function into its own 100b57cec5SDimitry Andric // stand-alone function. 110b57cec5SDimitry Andric // 120b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 130b57cec5SDimitry Andric 140b57cec5SDimitry Andric #ifndef LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H 150b57cec5SDimitry Andric #define LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H 160b57cec5SDimitry Andric 170b57cec5SDimitry Andric #include "llvm/ADT/ArrayRef.h" 180b57cec5SDimitry Andric #include "llvm/ADT/DenseMap.h" 190b57cec5SDimitry Andric #include "llvm/ADT/SetVector.h" 200b57cec5SDimitry Andric #include "llvm/ADT/SmallPtrSet.h" 210b57cec5SDimitry Andric #include <limits> 220b57cec5SDimitry Andric 230b57cec5SDimitry Andric namespace llvm { 240b57cec5SDimitry Andric 258bcb0991SDimitry Andric class AllocaInst; 260b57cec5SDimitry Andric class BasicBlock; 270b57cec5SDimitry Andric class BlockFrequency; 280b57cec5SDimitry Andric class BlockFrequencyInfo; 290b57cec5SDimitry Andric class BranchProbabilityInfo; 300b57cec5SDimitry Andric class AssumptionCache; 310b57cec5SDimitry Andric class CallInst; 320b57cec5SDimitry Andric class DominatorTree; 330b57cec5SDimitry Andric class Function; 340b57cec5SDimitry Andric class Instruction; 350b57cec5SDimitry Andric class Loop; 360b57cec5SDimitry Andric class Module; 370b57cec5SDimitry Andric class Type; 380b57cec5SDimitry Andric class Value; 390b57cec5SDimitry Andric 408bcb0991SDimitry Andric /// A cache for the CodeExtractor analysis. The operation \ref 418bcb0991SDimitry Andric /// CodeExtractor::extractCodeRegion is guaranteed not to invalidate this 428bcb0991SDimitry Andric /// object. This object should conservatively be considered invalid if any 438bcb0991SDimitry Andric /// other mutating operations on the IR occur. 448bcb0991SDimitry Andric /// 458bcb0991SDimitry Andric /// Constructing this object is O(n) in the size of the function. 468bcb0991SDimitry Andric class CodeExtractorAnalysisCache { 478bcb0991SDimitry Andric /// The allocas in the function. 488bcb0991SDimitry Andric SmallVector<AllocaInst *, 16> Allocas; 498bcb0991SDimitry Andric 508bcb0991SDimitry Andric /// Base memory addresses of load/store instructions, grouped by block. 518bcb0991SDimitry Andric DenseMap<BasicBlock *, DenseSet<Value *>> BaseMemAddrs; 528bcb0991SDimitry Andric 538bcb0991SDimitry Andric /// Blocks which contain instructions which may have unknown side-effects 548bcb0991SDimitry Andric /// on memory. 558bcb0991SDimitry Andric DenseSet<BasicBlock *> SideEffectingBlocks; 568bcb0991SDimitry Andric 578bcb0991SDimitry Andric void findSideEffectInfoForBlock(BasicBlock &BB); 588bcb0991SDimitry Andric 598bcb0991SDimitry Andric public: 608bcb0991SDimitry Andric CodeExtractorAnalysisCache(Function &F); 618bcb0991SDimitry Andric 628bcb0991SDimitry Andric /// Get the allocas in the function at the time the analysis was created. 638bcb0991SDimitry Andric /// Note that some of these allocas may no longer be present in the function, 648bcb0991SDimitry Andric /// due to \ref CodeExtractor::extractCodeRegion. 658bcb0991SDimitry Andric ArrayRef<AllocaInst *> getAllocas() const { return Allocas; } 668bcb0991SDimitry Andric 678bcb0991SDimitry Andric /// Check whether \p BB contains an instruction thought to load from, store 688bcb0991SDimitry Andric /// to, or otherwise clobber the alloca \p Addr. 698bcb0991SDimitry Andric bool doesBlockContainClobberOfAddr(BasicBlock &BB, AllocaInst *Addr) const; 708bcb0991SDimitry Andric }; 718bcb0991SDimitry Andric 720b57cec5SDimitry Andric /// Utility class for extracting code into a new function. 730b57cec5SDimitry Andric /// 740b57cec5SDimitry Andric /// This utility provides a simple interface for extracting some sequence of 750b57cec5SDimitry Andric /// code into its own function, replacing it with a call to that function. It 760b57cec5SDimitry Andric /// also provides various methods to query about the nature and result of 770b57cec5SDimitry Andric /// such a transformation. 780b57cec5SDimitry Andric /// 790b57cec5SDimitry Andric /// The rough algorithm used is: 800b57cec5SDimitry Andric /// 1) Find both the inputs and outputs for the extracted region. 810b57cec5SDimitry Andric /// 2) Pass the inputs as arguments, remapping them within the extracted 820b57cec5SDimitry Andric /// function to arguments. 830b57cec5SDimitry Andric /// 3) Add allocas for any scalar outputs, adding all of the outputs' allocas 840b57cec5SDimitry Andric /// as arguments, and inserting stores to the arguments for any scalars. 850b57cec5SDimitry Andric class CodeExtractor { 860b57cec5SDimitry Andric using ValueSet = SetVector<Value *>; 870b57cec5SDimitry Andric 880b57cec5SDimitry Andric // Various bits of state computed on construction. 890b57cec5SDimitry Andric DominatorTree *const DT; 900b57cec5SDimitry Andric const bool AggregateArgs; 910b57cec5SDimitry Andric BlockFrequencyInfo *BFI; 920b57cec5SDimitry Andric BranchProbabilityInfo *BPI; 930b57cec5SDimitry Andric AssumptionCache *AC; 940b57cec5SDimitry Andric 950b57cec5SDimitry Andric // If true, varargs functions can be extracted. 960b57cec5SDimitry Andric bool AllowVarArgs; 970b57cec5SDimitry Andric 980b57cec5SDimitry Andric // Bits of intermediate state computed at various phases of extraction. 990b57cec5SDimitry Andric SetVector<BasicBlock *> Blocks; 1000b57cec5SDimitry Andric unsigned NumExitBlocks = std::numeric_limits<unsigned>::max(); 1010b57cec5SDimitry Andric Type *RetTy; 1020b57cec5SDimitry Andric 1030b57cec5SDimitry Andric // Suffix to use when creating extracted function (appended to the original 1040b57cec5SDimitry Andric // function name + "."). If empty, the default is to use the entry block 1050b57cec5SDimitry Andric // label, if non-empty, otherwise "extracted". 1060b57cec5SDimitry Andric std::string Suffix; 1070b57cec5SDimitry Andric 1080b57cec5SDimitry Andric public: 1090b57cec5SDimitry Andric /// Create a code extractor for a sequence of blocks. 1100b57cec5SDimitry Andric /// 1110b57cec5SDimitry Andric /// Given a sequence of basic blocks where the first block in the sequence 1120b57cec5SDimitry Andric /// dominates the rest, prepare a code extractor object for pulling this 1130b57cec5SDimitry Andric /// sequence out into its new function. When a DominatorTree is also given, 1140b57cec5SDimitry Andric /// extra checking and transformations are enabled. If AllowVarArgs is true, 1150b57cec5SDimitry Andric /// vararg functions can be extracted. This is safe, if all vararg handling 1160b57cec5SDimitry Andric /// code is extracted, including vastart. If AllowAlloca is true, then 1170b57cec5SDimitry Andric /// extraction of blocks containing alloca instructions would be possible, 1180b57cec5SDimitry Andric /// however code extractor won't validate whether extraction is legal. 1190b57cec5SDimitry Andric CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT = nullptr, 1200b57cec5SDimitry Andric bool AggregateArgs = false, BlockFrequencyInfo *BFI = nullptr, 1210b57cec5SDimitry Andric BranchProbabilityInfo *BPI = nullptr, 1220b57cec5SDimitry Andric AssumptionCache *AC = nullptr, 1230b57cec5SDimitry Andric bool AllowVarArgs = false, bool AllowAlloca = false, 1240b57cec5SDimitry Andric std::string Suffix = ""); 1250b57cec5SDimitry Andric 1260b57cec5SDimitry Andric /// Create a code extractor for a loop body. 1270b57cec5SDimitry Andric /// 1280b57cec5SDimitry Andric /// Behaves just like the generic code sequence constructor, but uses the 1290b57cec5SDimitry Andric /// block sequence of the loop. 1300b57cec5SDimitry Andric CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false, 1310b57cec5SDimitry Andric BlockFrequencyInfo *BFI = nullptr, 1320b57cec5SDimitry Andric BranchProbabilityInfo *BPI = nullptr, 1330b57cec5SDimitry Andric AssumptionCache *AC = nullptr, 1340b57cec5SDimitry Andric std::string Suffix = ""); 1350b57cec5SDimitry Andric 1360b57cec5SDimitry Andric /// Perform the extraction, returning the new function. 1370b57cec5SDimitry Andric /// 1380b57cec5SDimitry Andric /// Returns zero when called on a CodeExtractor instance where isEligible 1390b57cec5SDimitry Andric /// returns false. 1408bcb0991SDimitry Andric Function *extractCodeRegion(const CodeExtractorAnalysisCache &CEAC); 1418bcb0991SDimitry Andric 1428bcb0991SDimitry Andric /// Verify that assumption cache isn't stale after a region is extracted. 1435ffd83dbSDimitry Andric /// Returns true when verifier finds errors. AssumptionCache is passed as 1448bcb0991SDimitry Andric /// parameter to make this function stateless. 1455ffd83dbSDimitry Andric static bool verifyAssumptionCache(const Function &OldFunc, 1465ffd83dbSDimitry Andric const Function &NewFunc, 1475ffd83dbSDimitry Andric AssumptionCache *AC); 1480b57cec5SDimitry Andric 1490b57cec5SDimitry Andric /// Test whether this code extractor is eligible. 1500b57cec5SDimitry Andric /// 1510b57cec5SDimitry Andric /// Based on the blocks used when constructing the code extractor, 1520b57cec5SDimitry Andric /// determine whether it is eligible for extraction. 1538bcb0991SDimitry Andric /// 1548bcb0991SDimitry Andric /// Checks that varargs handling (with vastart and vaend) is only done in 1558bcb0991SDimitry Andric /// the outlined blocks. 1568bcb0991SDimitry Andric bool isEligible() const; 1570b57cec5SDimitry Andric 1580b57cec5SDimitry Andric /// Compute the set of input values and output values for the code. 1590b57cec5SDimitry Andric /// 1600b57cec5SDimitry Andric /// These can be used either when performing the extraction or to evaluate 1610b57cec5SDimitry Andric /// the expected size of a call to the extracted function. Note that this 1620b57cec5SDimitry Andric /// work cannot be cached between the two as once we decide to extract 1630b57cec5SDimitry Andric /// a code sequence, that sequence is modified, including changing these 1640b57cec5SDimitry Andric /// sets, before extraction occurs. These modifications won't have any 1650b57cec5SDimitry Andric /// significant impact on the cost however. 1660b57cec5SDimitry Andric void findInputsOutputs(ValueSet &Inputs, ValueSet &Outputs, 1670b57cec5SDimitry Andric const ValueSet &Allocas) const; 1680b57cec5SDimitry Andric 1690b57cec5SDimitry Andric /// Check if life time marker nodes can be hoisted/sunk into the outline 1700b57cec5SDimitry Andric /// region. 1710b57cec5SDimitry Andric /// 1720b57cec5SDimitry Andric /// Returns true if it is safe to do the code motion. 1738bcb0991SDimitry Andric bool 1748bcb0991SDimitry Andric isLegalToShrinkwrapLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC, 1758bcb0991SDimitry Andric Instruction *AllocaAddr) const; 1760b57cec5SDimitry Andric 1770b57cec5SDimitry Andric /// Find the set of allocas whose life ranges are contained within the 1780b57cec5SDimitry Andric /// outlined region. 1790b57cec5SDimitry Andric /// 1800b57cec5SDimitry Andric /// Allocas which have life_time markers contained in the outlined region 1810b57cec5SDimitry Andric /// should be pushed to the outlined function. The address bitcasts that 1820b57cec5SDimitry Andric /// are used by the lifetime markers are also candidates for shrink- 1830b57cec5SDimitry Andric /// wrapping. The instructions that need to be sunk are collected in 1840b57cec5SDimitry Andric /// 'Allocas'. 1858bcb0991SDimitry Andric void findAllocas(const CodeExtractorAnalysisCache &CEAC, 1868bcb0991SDimitry Andric ValueSet &SinkCands, ValueSet &HoistCands, 1870b57cec5SDimitry Andric BasicBlock *&ExitBlock) const; 1880b57cec5SDimitry Andric 1890b57cec5SDimitry Andric /// Find or create a block within the outline region for placing hoisted 1900b57cec5SDimitry Andric /// code. 1910b57cec5SDimitry Andric /// 1920b57cec5SDimitry Andric /// CommonExitBlock is block outside the outline region. It is the common 1930b57cec5SDimitry Andric /// successor of blocks inside the region. If there exists a single block 1940b57cec5SDimitry Andric /// inside the region that is the predecessor of CommonExitBlock, that block 1950b57cec5SDimitry Andric /// will be returned. Otherwise CommonExitBlock will be split and the 1960b57cec5SDimitry Andric /// original block will be added to the outline region. 1970b57cec5SDimitry Andric BasicBlock *findOrCreateBlockForHoisting(BasicBlock *CommonExitBlock); 1980b57cec5SDimitry Andric 1990b57cec5SDimitry Andric private: 2000b57cec5SDimitry Andric struct LifetimeMarkerInfo { 2010b57cec5SDimitry Andric bool SinkLifeStart = false; 2020b57cec5SDimitry Andric bool HoistLifeEnd = false; 2030b57cec5SDimitry Andric Instruction *LifeStart = nullptr; 2040b57cec5SDimitry Andric Instruction *LifeEnd = nullptr; 2050b57cec5SDimitry Andric }; 2060b57cec5SDimitry Andric 2078bcb0991SDimitry Andric LifetimeMarkerInfo 2088bcb0991SDimitry Andric getLifetimeMarkers(const CodeExtractorAnalysisCache &CEAC, 2098bcb0991SDimitry Andric Instruction *Addr, BasicBlock *ExitBlock) const; 2100b57cec5SDimitry Andric 2110b57cec5SDimitry Andric void severSplitPHINodesOfEntry(BasicBlock *&Header); 2120b57cec5SDimitry Andric void severSplitPHINodesOfExits(const SmallPtrSetImpl<BasicBlock *> &Exits); 2130b57cec5SDimitry Andric void splitReturnBlocks(); 2140b57cec5SDimitry Andric 2150b57cec5SDimitry Andric Function *constructFunction(const ValueSet &inputs, 2160b57cec5SDimitry Andric const ValueSet &outputs, 2170b57cec5SDimitry Andric BasicBlock *header, 2180b57cec5SDimitry Andric BasicBlock *newRootNode, BasicBlock *newHeader, 2190b57cec5SDimitry Andric Function *oldFunction, Module *M); 2200b57cec5SDimitry Andric 2210b57cec5SDimitry Andric void moveCodeToFunction(Function *newFunction); 2220b57cec5SDimitry Andric 2230b57cec5SDimitry Andric void calculateNewCallTerminatorWeights( 2240b57cec5SDimitry Andric BasicBlock *CodeReplacer, 2250b57cec5SDimitry Andric DenseMap<BasicBlock *, BlockFrequency> &ExitWeights, 2260b57cec5SDimitry Andric BranchProbabilityInfo *BPI); 2270b57cec5SDimitry Andric 2280b57cec5SDimitry Andric CallInst *emitCallAndSwitchStatement(Function *newFunction, 2290b57cec5SDimitry Andric BasicBlock *newHeader, 2300b57cec5SDimitry Andric ValueSet &inputs, ValueSet &outputs); 2310b57cec5SDimitry Andric }; 2320b57cec5SDimitry Andric 2330b57cec5SDimitry Andric } // end namespace llvm 2340b57cec5SDimitry Andric 2350b57cec5SDimitry Andric #endif // LLVM_TRANSFORMS_UTILS_CODEEXTRACTOR_H 236