Utility class for extracting code into a new function. More...

#include "llvm/Transforms/Utils/CodeExtractor.h"

Public Member Functions
	CodeExtractor (ArrayRef< BasicBlock * > BBs, DominatorTree DT=nullptr, bool AggregateArgs=false, BlockFrequencyInfo BFI=nullptr, BranchProbabilityInfo BPI=nullptr, AssumptionCache AC=nullptr, bool AllowVarArgs=false, bool AllowAlloca=false, BasicBlock *AllocationBlock=nullptr, std::string Suffix="")
	Create a code extractor for a sequence of blocks.

	CodeExtractor (DominatorTree &DT, Loop &L, bool AggregateArgs=false, BlockFrequencyInfo BFI=nullptr, BranchProbabilityInfo BPI=nullptr, AssumptionCache *AC=nullptr, std::string Suffix="")
	Create a code extractor for a loop body.

Function *	extractCodeRegion (const CodeExtractorAnalysisCache &CEAC)
	Perform the extraction, returning the new function.

Function *	extractCodeRegion (const CodeExtractorAnalysisCache &CEAC, ValueSet &Inputs, ValueSet &Outputs)
	Perform the extraction, returning the new function and providing an interface to see what was categorized as inputs and outputs.

bool	isEligible () const
	Test whether this code extractor is eligible.

void	findInputsOutputs (ValueSet &Inputs, ValueSet &Outputs, const ValueSet &Allocas) const
	Compute the set of input values and output values for the code.

bool	isLegalToShrinkwrapLifetimeMarkers (const CodeExtractorAnalysisCache &CEAC, Instruction *AllocaAddr) const
	Check if life time marker nodes can be hoisted/sunk into the outline region.

void	findAllocas (const CodeExtractorAnalysisCache &CEAC, ValueSet &SinkCands, ValueSet &HoistCands, BasicBlock *&ExitBlock) const
	Find the set of allocas whose life ranges are contained within the outlined region.

BasicBlock *	findOrCreateBlockForHoisting (BasicBlock *CommonExitBlock)
	Find or create a block within the outline region for placing hoisted code.

void	excludeArgFromAggregate (Value *Arg)
	Exclude a value from aggregate argument passing when extracting a code region, passing it instead as a scalar.

Static Public Member Functions
static bool	verifyAssumptionCache (const Function &OldFunc, const Function &NewFunc, AssumptionCache *AC)
	Verify that assumption cache isn't stale after a region is extracted.

Detailed 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.

Definition at line 85 of file CodeExtractor.h.

Constructor & Destructor Documentation

◆ CodeExtractor() [1/2]

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

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.

Definition at line 244 of file CodeExtractor.cpp.

◆ CodeExtractor() [2/2]

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

Create a code extractor for a loop body.

Behaves just like the generic code sequence constructor, but uses the block sequence of the loop.

Definition at line 255 of file CodeExtractor.cpp.

Member Function Documentation

◆ excludeArgFromAggregate()

void CodeExtractor::excludeArgFromAggregate ( Value * Arg )

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

Definition at line 1880 of file CodeExtractor.cpp.

References llvm::SetVector< T, Vector, Set, N >::insert().

Referenced by llvm::OpenMPIRBuilder::finalize().

◆ extractCodeRegion() [1/2]

Function * CodeExtractor::extractCodeRegion ( const CodeExtractorAnalysisCache & CEAC )

Perform the extraction, returning the new function.

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

Definition at line 1625 of file CodeExtractor.cpp.

References extractCodeRegion().

Referenced by extractCodeRegion(), and llvm::OpenMPIRBuilder::finalize().

◆ extractCodeRegion() [2/2]

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

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

Parameters

CEAC	- Cache to speed up operations for the CodeExtractor when hoisting, and extracting lifetime values and assumes.
Inputs	[out] - filled with values marked as inputs to the newly outlined function.
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.

Definition at line 1631 of file CodeExtractor.cpp.

References llvm::any_of(), assert(), llvm::BasicBlock::begin(), llvm::Block, Blocks, llvm::BranchInst::Create(), llvm::BasicBlock::Create(), llvm::Value::dump(), llvm::SetVector< T, Vector, Set, N >::empty(), llvm::BasicBlock::end(), eraseLifetimeMarkersOnInputs(), llvm::errs(), findAllocas(), findInputsOutputs(), findOrCreateBlockForHoisting(), fixupDebugInfoPostExtraction(), llvm::SetVector< T, Vector, Set, N >::getArrayRef(), llvm::BlockFrequencyInfo::getBlockFreq(), llvm::BasicBlock::getContext(), llvm::BranchProbabilityInfo::getEdgeProbability(), llvm::BasicBlock::getFirstInsertionPt(), llvm::BlockFrequency::getFrequency(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getNumSuccessors(), llvm::GlobalValue::getParent(), llvm::BasicBlock::getParent(), llvm::Function::getPersonalityFn(), llvm::BlockFrequencyInfo::getProfileCountFromFreq(), llvm::Function::getSubprogram(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Function::hasPersonalityFn(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), insertLifetimeMarkersSurroundingCall(), isEligible(), LLVM_DEBUG, llvm::make_early_inc_range(), llvm::Instruction::moveBefore(), llvm::none_of(), llvm::Function::PCT_Real, llvm::predecessors(), llvm::report_fatal_error(), llvm::BlockFrequencyInfo::setBlockFreq(), llvm::Function::setDoesNotReturn(), llvm::Function::setEntryCount(), llvm::PHINode::setIncomingBlock(), llvm::Function::setPersonalityFn(), llvm::SmallPtrSetImplBase::size(), llvm::successors(), llvm::AssumptionCache::unregisterAssumption(), verifyAssumptionCache(), and llvm::verifyFunction().

◆ findAllocas()

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

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'.

Definition at line 493 of file CodeExtractor.cpp.

References assert(), llvm::SmallVectorImpl< T >::clear(), llvm::CastInst::CreatePointerCast(), llvm::dbgs(), definedInRegion(), E, llvm::SmallVectorBase< Size_T >::empty(), llvm::CodeExtractorAnalysisCache::getAllocas(), getCommonExitBlock(), llvm::Type::getInt8PtrTy(), llvm::GlobalValue::getParent(), llvm::BasicBlock::getParent(), getParent(), I, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::Instruction::isLifetimeStartOrEnd(), LLVM_DEBUG, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorBase< Size_T >::size().

Referenced by llvm::OpenMPIRBuilder::createParallel(), and extractCodeRegion().

◆ findInputsOutputs()

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

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.

Definition at line 645 of file CodeExtractor.cpp.

References Blocks, llvm::SetVector< T, Vector, Set, N >::count(), definedInCaller(), definedInRegion(), and llvm::SetVector< T, Vector, Set, N >::insert().

Referenced by llvm::OpenMPIRBuilder::createParallel(), and extractCodeRegion().

◆ findOrCreateBlockForHoisting()

BasicBlock * CodeExtractor::findOrCreateBlockForHoisting ( BasicBlock * CommonExitBlock )

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.

Definition at line 386 of file CodeExtractor.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::BasicBlock::end(), llvm::BasicBlock::getFirstNonPHI(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::BasicBlock::getTerminator(), I, llvm::make_early_inc_range(), llvm::predecessors(), llvm::User::replaceUsesOfWith(), and llvm::BasicBlock::splitBasicBlock().

Referenced by extractCodeRegion().

◆ isEligible()

bool CodeExtractor::isEligible ( ) const

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.

Definition at line 618 of file CodeExtractor.cpp.

References llvm::any_of(), F, and I.

Referenced by extractCodeRegion(), and llvm::OpenMPIRBuilder::finalize().

◆ isLegalToShrinkwrapLifetimeMarkers()

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

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.

Definition at line 372 of file CodeExtractor.cpp.

References Addr, llvm::CodeExtractorAnalysisCache::doesBlockContainClobberOfAddr(), and getParent().

◆ verifyAssumptionCache()

bool CodeExtractor::verifyAssumptionCache	(	const Function &	OldFunc,
		const Function &	NewFunc,
		AssumptionCache *	AC
	)

static

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.

Definition at line 1851 of file CodeExtractor.cpp.

References llvm::AssumptionCache::assumptions(), llvm::AssumptionCache::assumptionsFor(), and I.