class CodeExtractor

Declaration

class CodeExtractor { /* full declaration omitted */ };

Description

Utility class for extracting code into a new function. This utility provides a simple interface for extracting some sequence of code into its own function, replacing it with a call to that function. It also provides various methods to query about the nature and result of such a transformation. The rough algorithm used is: 1) Find both the inputs and outputs for the extracted region. 2) Pass the inputs as arguments, remapping them within the extracted function to arguments. 3) Add allocas for any scalar outputs, adding all of the outputs' allocas as arguments, and inserting stores to the arguments for any scalars.

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:85

Member Variables

private llvm::DominatorTree* const DT

private const bool AggregateArgs

private llvm::BlockFrequencyInfo* BFI

private llvm::BranchProbabilityInfo* BPI

private llvm::AssumptionCache* AC

private llvm::BasicBlock* AllocationBlock

private bool AllowVarArgs

private SetVector<llvm::BasicBlock*> Blocks

private unsigned int NumExitBlocks = std::numeric_limits<unsigned int>::max()

private llvm::Type* RetTy

private SmallVector<llvm::BasicBlock*, 4> OldTargets

private std::string Suffix

private llvm::CodeExtractor::ValueSet ExcludeArgsFromAggregate

Method Overview

• public CodeExtractor(llvm::DominatorTree & DT, llvm::Loop & L, bool AggregateArgs = false, llvm::BlockFrequencyInfo * BFI = nullptr, llvm::BranchProbabilityInfo * BPI = nullptr, llvm::AssumptionCache * AC = nullptr, std::string Suffix = "")
• public CodeExtractor(ArrayRef<llvm::BasicBlock *> BBs, llvm::DominatorTree * DT = nullptr, bool AggregateArgs = false, llvm::BlockFrequencyInfo * BFI = nullptr, llvm::BranchProbabilityInfo * BPI = nullptr, llvm::AssumptionCache * AC = nullptr, bool AllowVarArgs = false, bool AllowAlloca = false, llvm::BasicBlock * AllocationBlock = nullptr, std::string Suffix = "")
• private void calculateNewCallTerminatorWeights(llvm::BasicBlock * CodeReplacer, DenseMap<llvm::BasicBlock *, llvm::BlockFrequency> & ExitWeights, llvm::BranchProbabilityInfo * BPI)
• private llvm::Function * constructFunction(const llvm::CodeExtractor::ValueSet & inputs, const llvm::CodeExtractor::ValueSet & outputs, llvm::BasicBlock * header, llvm::BasicBlock * newRootNode, llvm::BasicBlock * newHeader, llvm::Function * oldFunction, llvm::Module * M)
• private llvm::CallInst * emitCallAndSwitchStatement(llvm::Function * newFunction, llvm::BasicBlock * newHeader, llvm::CodeExtractor::ValueSet & inputs, llvm::CodeExtractor::ValueSet & outputs)
• public void excludeArgFromAggregate(llvm::Value * Arg)
• public llvm::Function * extractCodeRegion(const llvm::CodeExtractorAnalysisCache & CEAC, llvm::CodeExtractor::ValueSet & Inputs, llvm::CodeExtractor::ValueSet & Outputs)
• public llvm::Function * extractCodeRegion(const llvm::CodeExtractorAnalysisCache & CEAC)
• public void findAllocas(const llvm::CodeExtractorAnalysisCache & CEAC, llvm::CodeExtractor::ValueSet & SinkCands, llvm::CodeExtractor::ValueSet & HoistCands, llvm::BasicBlock *& ExitBlock) const
• public void findInputsOutputs(llvm::CodeExtractor::ValueSet & Inputs, llvm::CodeExtractor::ValueSet & Outputs, const llvm::CodeExtractor::ValueSet & Allocas) const
• public llvm::BasicBlock * findOrCreateBlockForHoisting(llvm::BasicBlock * CommonExitBlock)
• private llvm::CodeExtractor::LifetimeMarkerInfo getLifetimeMarkers(const llvm::CodeExtractorAnalysisCache & CEAC, llvm::Instruction * Addr, llvm::BasicBlock * ExitBlock) const
• public bool isEligible() const
• public bool isLegalToShrinkwrapLifetimeMarkers(const llvm::CodeExtractorAnalysisCache & CEAC, llvm::Instruction * AllocaAddr) const
• private void moveCodeToFunction(llvm::Function * newFunction)
• private void severSplitPHINodesOfEntry(llvm::BasicBlock *& Header)
• private void severSplitPHINodesOfExits(const SmallPtrSetImpl<llvm::BasicBlock *> & Exits)
• private void splitReturnBlocks()
• public static bool verifyAssumptionCache(const llvm::Function & OldFunc, const llvm::Function & NewFunc, llvm::AssumptionCache * AC)

Methods

¶CodeExtractor(
    llvm::DominatorTree& DT,
    llvm::Loop& L,
    bool AggregateArgs = false,
    llvm::BlockFrequencyInfo* BFI = nullptr,
    llvm::BranchProbabilityInfo* BPI = nullptr,
    llvm::AssumptionCache* AC = nullptr,
    std::string Suffix = "")

Description

Create a code extractor for a loop body. Behaves just like the generic code sequence constructor, but uses the block sequence of the loop.

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:143

Parameters

llvm::DominatorTree& DT

llvm::Loop& L

bool AggregateArgs = false

llvm::BlockFrequencyInfo* BFI = nullptr

llvm::BranchProbabilityInfo* BPI = nullptr

llvm::AssumptionCache* AC = nullptr

std::string Suffix = ""

¶CodeExtractor(
    ArrayRef<llvm::BasicBlock*> BBs,
    llvm::DominatorTree* DT = nullptr,
    bool AggregateArgs = false,
    llvm::BlockFrequencyInfo* BFI = nullptr,
    llvm::BranchProbabilityInfo* BPI = nullptr,
    llvm::AssumptionCache* AC = nullptr,
    bool AllowVarArgs = false,
    bool AllowAlloca = false,
    llvm::BasicBlock* AllocationBlock = nullptr,
    std::string Suffix = "")

Description

Create a code extractor for a sequence of blocks. Given a sequence of basic blocks where the first block in the sequence dominates the rest, prepare a code extractor object for pulling this sequence out into its new function. When a DominatorTree is also given, extra checking and transformations are enabled. If AllowVarArgs is true, vararg functions can be extracted. This is safe, if all vararg handling code is extracted, including vastart. If AllowAlloca is true, then extraction of blocks containing alloca instructions would be possible, however code extractor won't validate whether extraction is legal. Any new allocations will be placed in the AllocationBlock, unless it is null, in which case it will be placed in the entry block of the function from which the code is being extracted.

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:131

Parameters

ArrayRef<llvm::BasicBlock*> BBs

llvm::DominatorTree* DT = nullptr

bool AggregateArgs = false

llvm::BlockFrequencyInfo* BFI = nullptr

llvm::BranchProbabilityInfo* BPI = nullptr

llvm::AssumptionCache* AC = nullptr

bool AllowVarArgs = false

bool AllowAlloca = false

llvm::BasicBlock* AllocationBlock = nullptr

std::string Suffix = ""

¶void calculateNewCallTerminatorWeights(
    llvm::BasicBlock* CodeReplacer,
    DenseMap<llvm::BasicBlock*,
             llvm::BlockFrequency>& ExitWeights,
    llvm::BranchProbabilityInfo* BPI)

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:256

Parameters

llvm::BasicBlock* CodeReplacer

DenseMap<llvm::BasicBlock*, llvm::BlockFrequency>& ExitWeights

llvm::BranchProbabilityInfo* BPI

¶llvm::Function* constructFunction(
    const llvm::CodeExtractor::ValueSet& inputs,
    const llvm::CodeExtractor::ValueSet& outputs,
    llvm::BasicBlock* header,
    llvm::BasicBlock* newRootNode,
    llvm::BasicBlock* newHeader,
    llvm::Function* oldFunction,
    llvm::Module* M)

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:248

Parameters

const llvm::CodeExtractor::ValueSet& inputs

const llvm::CodeExtractor::ValueSet& outputs

llvm::BasicBlock* header

llvm::BasicBlock* newRootNode

llvm::BasicBlock* newHeader

llvm::Function* oldFunction

llvm::Module* M

¶llvm::CallInst* emitCallAndSwitchStatement(
    llvm::Function* newFunction,
    llvm::BasicBlock* newHeader,
    llvm::CodeExtractor::ValueSet& inputs,
    llvm::CodeExtractor::ValueSet& outputs)

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:261

Parameters

llvm::Function* newFunction

llvm::BasicBlock* newHeader

llvm::CodeExtractor::ValueSet& inputs

llvm::CodeExtractor::ValueSet& outputs

¶void excludeArgFromAggregate(llvm::Value* Arg)

Description

Exclude a value from aggregate argument passing when extracting a code region, passing it instead as a scalar.

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:228

Parameters

llvm::Value* Arg

¶llvm::Function* extractCodeRegion(
    const llvm::CodeExtractorAnalysisCache& CEAC,
    llvm::CodeExtractor::ValueSet& Inputs,
    llvm::CodeExtractor::ValueSet& Outputs)

Description

Perform the extraction, returning the new function and providing an interface to see what was categorized as inputs and outputs.

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:166

Parameters

const llvm::CodeExtractorAnalysisCache& CEAC

- Cache to speed up operations for the CodeExtractor when hoisting, and extracting lifetime values and assumes.

llvm::CodeExtractor::ValueSet& Inputs

[out] - filled with values marked as inputs to the newly outlined function.

llvm::CodeExtractor::ValueSet& Outputs

[out] - filled with values marked as outputs to the newly outlined function.

Returns

zero when called on a CodeExtractor instance where isEligible returns false.

¶llvm::Function* extractCodeRegion(
    const llvm::CodeExtractorAnalysisCache& CEAC)

Description

Perform the extraction, returning the new function. Returns zero when called on a CodeExtractor instance where isEligible returns false.

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:153

Parameters

const llvm::CodeExtractorAnalysisCache& CEAC

¶void findAllocas(
    const llvm::CodeExtractorAnalysisCache& CEAC,
    llvm::CodeExtractor::ValueSet& SinkCands,
    llvm::CodeExtractor::ValueSet& HoistCands,
    llvm::BasicBlock*& ExitBlock) const

Description

Find the set of allocas whose life ranges are contained within the outlined region. Allocas which have life_time markers contained in the outlined region should be pushed to the outlined function. The address bitcasts that are used by the lifetime markers are also candidates for shrink- wrapping. The instructions that need to be sunk are collected in 'Allocas'.

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:212

Parameters

const llvm::CodeExtractorAnalysisCache& CEAC

llvm::CodeExtractor::ValueSet& SinkCands

llvm::CodeExtractor::ValueSet& HoistCands

llvm::BasicBlock*& ExitBlock

¶void findInputsOutputs(
    llvm::CodeExtractor::ValueSet& Inputs,
    llvm::CodeExtractor::ValueSet& Outputs,
    const llvm::CodeExtractor::ValueSet& Allocas)
    const

Description

Compute the set of input values and output values for the code. These can be used either when performing the extraction or to evaluate the expected size of a call to the extracted function. Note that this work cannot be cached between the two as once we decide to extract a code sequence, that sequence is modified, including changing these sets, before extraction occurs. These modifications won't have any significant impact on the cost however.

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:193

Parameters

llvm::CodeExtractor::ValueSet& Inputs

llvm::CodeExtractor::ValueSet& Outputs

const llvm::CodeExtractor::ValueSet& Allocas

¶llvm::BasicBlock* findOrCreateBlockForHoisting(
    llvm::BasicBlock* CommonExitBlock)

Description

Find or create a block within the outline region for placing hoisted code. CommonExitBlock is block outside the outline region. It is the common successor of blocks inside the region. If there exists a single block inside the region that is the predecessor of CommonExitBlock, that block will be returned. Otherwise CommonExitBlock will be split and the original block will be added to the outline region.

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:224

Parameters

llvm::BasicBlock* CommonExitBlock

¶llvm::CodeExtractor::LifetimeMarkerInfo
getLifetimeMarkers(
    const llvm::CodeExtractorAnalysisCache& CEAC,
    llvm::Instruction* Addr,
    llvm::BasicBlock* ExitBlock) const

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:241

Parameters

const llvm::CodeExtractorAnalysisCache& CEAC

llvm::Instruction* Addr

llvm::BasicBlock* ExitBlock

¶bool isEligible() const

Description

Test whether this code extractor is eligible. Based on the blocks used when constructing the code extractor, determine whether it is eligible for extraction. Checks that varargs handling (with vastart and vaend) is only done in the outlined blocks.

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:183

¶bool isLegalToShrinkwrapLifetimeMarkers(
    const llvm::CodeExtractorAnalysisCache& CEAC,
    llvm::Instruction* AllocaAddr) const

Description

Check if life time marker nodes can be hoisted/sunk into the outline region. Returns true if it is safe to do the code motion.

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:201

Parameters

const llvm::CodeExtractorAnalysisCache& CEAC

llvm::Instruction* AllocaAddr

¶void moveCodeToFunction(
    llvm::Function* newFunction)

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:254

Parameters

llvm::Function* newFunction

¶void severSplitPHINodesOfEntry(
    llvm::BasicBlock*& Header)

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:244

Parameters

llvm::BasicBlock*& Header

¶void severSplitPHINodesOfExits(
    const SmallPtrSetImpl<llvm::BasicBlock*>&
        Exits)

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:245

Parameters

const SmallPtrSetImpl<llvm::BasicBlock*>& Exits

¶void splitReturnBlocks()

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:246

¶static bool verifyAssumptionCache(
    const llvm::Function& OldFunc,
    const llvm::Function& NewFunc,
    llvm::AssumptionCache* AC)

Description

Verify that assumption cache isn't stale after a region is extracted. Returns true when verifier finds errors. AssumptionCache is passed as parameter to make this function stateless.

Declared at: llvm/include/llvm/Transforms/Utils/CodeExtractor.h:172

Parameters

const llvm::Function& OldFunc

const llvm::Function& NewFunc

llvm::AssumptionCache* AC