LLVM  6.0.0svn
Public Member Functions | Static Public Member Functions | List of all members
llvm::CodeExtractor Class Reference

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)
 Create a code extractor for a sequence of blocks. More...
 
 CodeExtractor (DominatorTree &DT, Loop &L, bool AggregateArgs=false, BlockFrequencyInfo *BFI=nullptr, BranchProbabilityInfo *BPI=nullptr)
 Create a code extractor for a loop body. More...
 
FunctionextractCodeRegion ()
 Perform the extraction, returning the new function. More...
 
bool isEligible () const
 Test whether this code extractor is eligible. More...
 
void findInputsOutputs (ValueSet &Inputs, ValueSet &Outputs, const ValueSet &Allocas) const
 Compute the set of input values and output values for the code. More...
 
bool isLegalToShrinkwrapLifetimeMarkers (Instruction *AllocaAddr) const
 Check if life time marker nodes can be hoisted/sunk into the outline region. More...
 
void findAllocas (ValueSet &SinkCands, ValueSet &HoistCands, BasicBlock *&ExitBlock) const
 Find the set of allocas whose life ranges are contained within the outlined region. More...
 
BasicBlockfindOrCreateBlockForHoisting (BasicBlock *CommonExitBlock)
 Find or create a block within the outline region for placing hoisted code. More...
 

Static Public Member Functions

static bool isBlockValidForExtraction (const BasicBlock &BB)
 Check to see if a block is valid for extraction. More...
 

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 50 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 
)

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.

Definition at line 161 of file CodeExtractor.cpp.

◆ CodeExtractor() [2/2]

CodeExtractor::CodeExtractor ( DominatorTree DT,
Loop L,
bool  AggregateArgs = false,
BlockFrequencyInfo BFI = nullptr,
BranchProbabilityInfo BPI = nullptr 
)

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 167 of file CodeExtractor.cpp.

Member Function Documentation

◆ extractCodeRegion()

Function * CodeExtractor::extractCodeRegion ( )

◆ findAllocas()

void CodeExtractor::findAllocas ( 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 320 of file CodeExtractor.cpp.

References llvm::MCID::Bitcast, definedInRegion(), llvm::dyn_cast(), getCommonExitBlock(), llvm::IntrinsicInst::getIntrinsicID(), getParent(), llvm::SetVector< T, Vector, Set >::insert(), isLegalToShrinkwrapLifetimeMarkers(), and llvm::Value::users().

Referenced by extractCodeRegion(), and isEligible().

◆ 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 427 of file CodeExtractor.cpp.

References llvm::SwitchInst::addCase(), llvm::Function::addFnAttr(), llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), llvm::Function::arg_begin(), llvm::Function::arg_end(), assert(), llvm::DomTreeNodeBase< NodeT >::begin(), llvm::BasicBlock::begin(), llvm::Function::begin(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), Context, llvm::SetVector< T, Vector, Set >::count(), llvm::BasicBlock::Create(), llvm::Function::Create(), llvm::GetElementPtrInst::Create(), llvm::CallInst::Create(), llvm::PHINode::Create(), llvm::ReturnInst::Create(), llvm::BranchInst::Create(), llvm::SwitchInst::Create(), llvm::dbgs(), DEBUG, definedInCaller(), definedInRegion(), llvm::Function::doesNotThrow(), llvm::dyn_cast(), E, llvm::DomTreeNodeBase< NodeT >::end(), llvm::Instruction::eraseFromParent(), llvm::BasicBlock::front(), llvm::Function::front(), GEP, llvm::ConstantInt::get(), llvm::FunctionType::get(), llvm::StructType::get(), llvm::DataLayout::getAllocaAddrSpace(), llvm::Function::getAttributes(), llvm::Function::getBasicBlockList(), llvm::SwitchInst::getCondition(), llvm::BasicBlock::getContext(), llvm::Function::getContext(), llvm::Module::getContext(), llvm::Value::getContext(), llvm::Module::getDataLayout(), llvm::Function::getEntryBlock(), llvm::BasicBlock::getFirstNonPHI(), llvm::AttributeList::getFnAttributes(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::BasicBlock::getInstList(), llvm::Type::getInt16Ty(), llvm::Type::getInt1Ty(), llvm::Type::getInt32Ty(), getName(), llvm::Value::getName(), llvm::ilist_node_with_parent< NodeTy, ParentTy, Options >::getNextNode(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Constant::getNullValue(), llvm::PHINode::getNumIncomingValues(), llvm::TerminatorInst::getNumSuccessors(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), getParent(), llvm::Function::getReturnType(), llvm::TerminatorInst::getSuccessor(), llvm::SwitchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::PointerType::getUnqual(), llvm::Type::getVoidTy(), llvm::BranchProbability::getZero(), llvm::Function::hasUWTable(), I, llvm::SetVector< T, Vector, Set >::insert(), llvm::GlobalValue::InternalLinkage, llvm::Type::isVoidTy(), llvm::LLVMContext::MD_prof, llvm::iplist_impl< IntrusiveListT, TraitsT >::push_back(), llvm::iplist_impl< IntrusiveListT, TraitsT >::remove(), llvm::SwitchInst::removeCase(), llvm::PHINode::removeIncomingValue(), llvm::Value::replaceAllUsesWith(), llvm::User::replaceUsesOfWith(), llvm::SwitchInst::setCondition(), llvm::SwitchInst::setDefaultDest(), llvm::Function::setDoesNotThrow(), llvm::BranchProbabilityInfo::setEdgeProbability(), llvm::Function::setHasUWTable(), llvm::Instruction::setMetadata(), llvm::Value::setName(), llvm::TerminatorInst::setSuccessor(), SI, llvm::SetVector< T, Vector, Set >::size(), llvm::SmallVectorTemplateCommon< T >::size(), llvm::SplitBlock(), use, llvm::Value::user_begin(), llvm::Value::user_end(), Users, and llvm::Value::users().

Referenced by extractCodeRegion(), and isEligible().

◆ 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 269 of file CodeExtractor.cpp.

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

Referenced by extractCodeRegion(), and isEligible().

◆ isBlockValidForExtraction()

bool CodeExtractor::isBlockValidForExtraction ( const BasicBlock BB)
static

Check to see if a block is valid for extraction.

Test whether a block is valid for extraction.

Blocks containing EHPads, allocas, invokes, or vastarts are not valid.

Definition at line 81 of file CodeExtractor.cpp.

References E, llvm::SmallVectorBase::empty(), F(), getParent(), llvm::BasicBlock::hasAddressTaken(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::BasicBlock::isEHPad(), llvm::User::operands(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

Referenced by buildExtractionBlockSet().

◆ isEligible()

bool llvm::CodeExtractor::isEligible ( ) const
inline

Test whether this code extractor is eligible.

Based on the blocks used when constructing the code extractor, determine whether it is eligible for extraction.

Definition at line 98 of file CodeExtractor.h.

References llvm::SetVector< T, Vector, Set >::empty(), findAllocas(), findInputsOutputs(), findOrCreateBlockForHoisting(), and isLegalToShrinkwrapLifetimeMarkers().

Referenced by extractCodeRegion().

◆ isLegalToShrinkwrapLifetimeMarkers()

bool CodeExtractor::isLegalToShrinkwrapLifetimeMarkers ( 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 218 of file CodeExtractor.cpp.

References llvm::dyn_cast(), llvm::IntrinsicInst::getIntrinsicID(), getParent(), llvm::LoadInst::getPointerOperand(), llvm::StoreInst::getPointerOperand(), llvm::SPII::Load, SI, llvm::SPII::Store, and llvm::Value::stripInBoundsConstantOffsets().

Referenced by findAllocas(), and isEligible().


The documentation for this class was generated from the following files: