InnerLoopVectorizer vectorizes loops which contain only one basic block to a specified vectorization factor (VF). More...

Inheritance diagram for llvm::InnerLoopVectorizer:

[legend]

Collaboration diagram for llvm::InnerLoopVectorizer:

[legend]

Public Types
using	VectorParts = SmallVector< Value *, 2 >
	A type for vectorized values in the new loop. More...

Public Member Functions
	InnerLoopVectorizer (Loop OrigLoop, PredicatedScalarEvolution &PSE, LoopInfo LI, DominatorTree DT, const TargetLibraryInfo TLI, const TargetTransformInfo TTI, AssumptionCache AC, OptimizationRemarkEmitter ORE, unsigned VecWidth, unsigned UnrollFactor, LoopVectorizationLegality LVL, LoopVectorizationCostModel *CM)

virtual	~InnerLoopVectorizer ()=default

BasicBlock *	createVectorizedLoopSkeleton ()
	Create a new empty loop. More...

void	widenInstruction (Instruction &I)
	Widen a single instruction within the innermost loop. More...

void	fixVectorizedLoop ()
	Fix the vectorized code, taking care of header phi's, live-outs, and more. More...

bool	areSafetyChecksAdded ()

void	widenPHIInstruction (Instruction *PN, unsigned UF, unsigned VF)
	Vectorize a single PHINode in a block. More...

void	scalarizeInstruction (Instruction *Instr, const VPIteration &Instance, bool IfPredicateInstr)
	A helper function to scalarize a single Instruction in the innermost loop. More...

void	widenIntOrFpInduction (PHINode IV, TruncInst Trunc=nullptr)
	Widen an integer or floating-point induction variable `IV`. More...

Value *	getOrCreateVectorValue (Value *V, unsigned Part)
	getOrCreateVectorValue and getOrCreateScalarValue coordinate to generate a vector or scalar value on-demand if one is not yet available. More...

Value *	getOrCreateScalarValue (Value *V, const VPIteration &Instance)
	Return a value in the new loop corresponding to `V` from the original loop at unroll and vector indices `Instance`. More...

void	packScalarIntoVectorValue (Value *V, const VPIteration &Instance)
	Construct the vector value of a scalarized value `V` one lane at a time. More...

void	vectorizeInterleaveGroup (Instruction Instr, VectorParts BlockInMask=nullptr)
	Try to vectorize the interleaved access group that `Instr` belongs to, optionally masking the vector operations if `BlockInMask` is non-null. More...

void	vectorizeMemoryInstruction (Instruction Instr, VectorParts BlockInMask=nullptr)
	Vectorize Load and Store instructions, optionally masking the vector operations if `BlockInMask` is non-null. More...

void	setDebugLocFromInst (IRBuilder<> &B, const Value *Ptr)
	Set the debug location in the builder using the debug location in the instruction. More...

void	fixNonInductionPHIs (void)
	Fix the non-induction PHIs in the OrigPHIsToFix vector. More...

Protected Types
using	PhiVector = SmallVector< PHINode *, 4 >
	A small list of PHINodes. More...

using	ScalarParts = SmallVector< SmallVector< Value *, 4 >, 2 >
	A type for scalarized values in the new loop. More...

Protected Member Functions
void	fixupIVUsers (PHINode OrigPhi, const InductionDescriptor &II, Value CountRoundDown, Value EndValue, BasicBlock MiddleBlock)
	Set up the values of the IVs correctly when exiting the vector loop. More...

PHINode *	createInductionVariable (Loop L, Value Start, Value End, Value Step, Instruction *DL)
	Create a new induction variable inside L. More...

void	fixCrossIterationPHIs ()
	Handle all cross-iteration phis in the header. More...

void	fixFirstOrderRecurrence (PHINode *Phi)
	Fix a first-order recurrence. More...

void	fixReduction (PHINode *Phi)
	Fix a reduction cross-iteration phi. More...

void	fixLCSSAPHIs ()
	The Loop exit block may have single value PHI nodes with some incoming value. More...

void	sinkScalarOperands (Instruction *PredInst)
	Iteratively sink the scalarized operands of a predicated instruction into the block that was created for it. More...

void	truncateToMinimalBitwidths ()
	Shrinks vector element sizes to the smallest bitwidth they can be legally represented as. More...

void	updateAnalysis ()
	Insert the new loop to the loop hierarchy and pass manager and update the analysis passes. More...

virtual Value *	getBroadcastInstrs (Value *V)
	Create a broadcast instruction. More...

virtual Value *	getStepVector (Value Val, int StartIdx, Value Step, Instruction::BinaryOps Opcode=Instruction::BinaryOpsEnd)
	This function adds (StartIdx, StartIdx + Step, StartIdx + 2*Step, ...) to each vector element of Val. More...

void	buildScalarSteps (Value ScalarIV, Value Step, Instruction *EntryVal, const InductionDescriptor &ID)
	Compute scalar induction steps. More...

void	createVectorIntOrFpInductionPHI (const InductionDescriptor &II, Value Step, Instruction EntryVal)
	Create a vector induction phi node based on an existing scalar one. More...

bool	shouldScalarizeInstruction (Instruction *I) const
	Returns true if an instruction `I` should be scalarized instead of vectorized for the chosen vectorization factor. More...

bool	needsScalarInduction (Instruction *IV) const
	Returns true if we should generate a scalar version of `IV`. More...

void	recordVectorLoopValueForInductionCast (const InductionDescriptor &ID, const Instruction EntryVal, Value VectorLoopValue, unsigned Part, unsigned Lane=UINT_MAX)
	If there is a cast involved in the induction variable `ID`, which should be ignored in the vectorized loop body, this function records the VectorLoopValue of the respective Phi also as the VectorLoopValue of the cast. More...

virtual Value *	reverseVector (Value *Vec)
	Generate a shuffle sequence that will reverse the vector Vec. More...

Value *	getOrCreateTripCount (Loop *NewLoop)
	Returns (and creates if needed) the original loop trip count. More...

Value *	getOrCreateVectorTripCount (Loop *NewLoop)
	Returns (and creates if needed) the trip count of the widened loop. More...

Value *	createBitOrPointerCast (Value V, VectorType DstVTy, const DataLayout &DL)
	Returns a bitcasted value to the requested vector type. More...

void	emitMinimumIterationCountCheck (Loop L, BasicBlock Bypass)
	Emit a bypass check to see if the vector trip count is zero, including if it overflows. More...

void	emitSCEVChecks (Loop L, BasicBlock Bypass)
	Emit a bypass check to see if all of the SCEV assumptions we've had to make are correct. More...

void	emitMemRuntimeChecks (Loop L, BasicBlock Bypass)
	Emit bypass checks to check any memory assumptions we may have made. More...

Value *	emitTransformedIndex (IRBuilder<> &B, Value Index, ScalarEvolution SE, const DataLayout &DL, const InductionDescriptor &ID) const
	Compute the transformed value of Index at offset StartValue using step StepValue. More...

void	addNewMetadata (Instruction To, const Instruction Orig)
	Add additional metadata to `To` that was not present on `Orig`. More...

void	addMetadata (Instruction To, Instruction From)
	Add metadata from one instruction to another. More...

void	addMetadata (ArrayRef< Value > To, Instruction From)
	Similar to the previous function but it adds the metadata to a vector of instructions. More...

Protected Attributes
Loop *	OrigLoop
	The original loop. More...

PredicatedScalarEvolution &	PSE
	A wrapper around ScalarEvolution used to add runtime SCEV checks. More...

LoopInfo *	LI
	Loop Info. More...

DominatorTree *	DT
	Dominator Tree. More...

AliasAnalysis *	AA
	Alias Analysis. More...

const TargetLibraryInfo *	TLI
	Target Library Info. More...

const TargetTransformInfo *	TTI
	Target Transform Info. More...

AssumptionCache *	AC
	Assumption Cache. More...

OptimizationRemarkEmitter *	ORE
	Interface to emit optimization remarks. More...

std::unique_ptr< LoopVersioning >	LVer
	LoopVersioning. More...

unsigned	VF
	The vectorization SIMD factor to use. More...

unsigned	UF
	The vectorization unroll factor to use. More...

IRBuilder	Builder
	The builder that we use. More...

BasicBlock *	LoopVectorPreHeader
	The vector-loop preheader. More...

BasicBlock *	LoopScalarPreHeader
	The scalar-loop preheader. More...

BasicBlock *	LoopMiddleBlock
	Middle Block between the vector and the scalar. More...

BasicBlock *	LoopExitBlock
	The ExitBlock of the scalar loop. More...

BasicBlock *	LoopVectorBody
	The vector loop body. More...

BasicBlock *	LoopScalarBody
	The scalar loop body. More...

SmallVector< BasicBlock *, 4 >	LoopBypassBlocks
	A list of all bypass blocks. The first block is the entry of the loop. More...

PHINode *	Induction = nullptr
	The new Induction variable which was added to the new block. More...

PHINode *	OldInduction = nullptr
	The induction variable of the old basic block. More...

VectorizerValueMap	VectorLoopValueMap
	Maps values from the original loop to their corresponding values in the vectorized loop. More...

SmallVector< Instruction *, 4 >	PredicatedInstructions
	Store instructions that were predicated. More...

Value *	TripCount = nullptr
	Trip count of the original loop. More...

Value *	VectorTripCount = nullptr
	Trip count of the widened loop (TripCount - TripCount % (VF*UF)) More...

LoopVectorizationLegality *	Legal
	The legality analysis. More...

LoopVectorizationCostModel *	Cost
	The profitablity analysis. More...

bool	AddedSafetyChecks = false

DenseMap< PHINode , Value >	IVEndValues

SmallVector< PHINode *, 8 >	OrigPHIsToFix

Friends
class	LoopVectorizationPlanner

Detailed Description

InnerLoopVectorizer vectorizes loops which contain only one basic block to a specified vectorization factor (VF).

This class performs the widening of scalars into vectors, or multiple scalars. This class also implements the following features:

It inserts an epilogue loop for handling loops that don't have iteration counts that are known to be a multiple of the vectorization factor.
It handles the code generation for reduction variables.
Scalarization (implementation using scalars) of un-vectorizable instructions. InnerLoopVectorizer does not perform any vectorization-legality checks, and relies on the caller to check for the different legality aspects. The InnerLoopVectorizer relies on the LoopVectorizationLegality class to provide information about the induction and reduction variables that were found to a given vectorization factor.

Definition at line 345 of file LoopVectorize.cpp.

Member Typedef Documentation

◆ PhiVector

using llvm::InnerLoopVectorizer::PhiVector = SmallVector<PHINode *, 4>

protected

A small list of PHINodes.

Definition at line 448 of file LoopVectorize.cpp.

◆ ScalarParts

using llvm::InnerLoopVectorizer::ScalarParts = SmallVector<SmallVector<Value *, 4>, 2>

protected

A type for scalarized values in the new loop.

Each value from the original loop, when scalarized, is represented by UF x VF scalar values in the new unrolled loop, where UF is the unroll factor and VF is the vectorization factor.

Definition at line 454 of file LoopVectorize.cpp.

◆ VectorParts

using llvm::InnerLoopVectorizer::VectorParts = SmallVector<Value *, 2>

A type for vectorized values in the new loop.

Each value from the original loop, when vectorized, is represented by UF vector values in the new unrolled loop, where UF is the unroll factor.

Definition at line 376 of file LoopVectorize.cpp.

Constructor & Destructor Documentation

◆ InnerLoopVectorizer()

llvm::InnerLoopVectorizer::InnerLoopVectorizer	(	Loop *	OrigLoop,
		PredicatedScalarEvolution &	PSE,
		LoopInfo *	LI,
		DominatorTree *	DT,
		const TargetLibraryInfo *	TLI,
		const TargetTransformInfo *	TTI,
		AssumptionCache *	AC,
		OptimizationRemarkEmitter *	ORE,
		unsigned	VecWidth,
		unsigned	UnrollFactor,
		LoopVectorizationLegality *	LVL,
		LoopVectorizationCostModel *	CM
	)

inline

Definition at line 347 of file LoopVectorize.cpp.

References createVectorizedLoopSkeleton(), fixVectorizedLoop(), I, widenInstruction(), and ~InnerLoopVectorizer().

◆ ~InnerLoopVectorizer()

virtual llvm::InnerLoopVectorizer::~InnerLoopVectorizer ( )

virtualdefault

Referenced by InnerLoopVectorizer().

Member Function Documentation

◆ addMetadata() [1/2]

void InnerLoopVectorizer::addMetadata	(	Instruction *	To,
		Instruction *	From
	)

protected

Add metadata from one instruction to another.

This includes both the original MDs from From and additional ones (

See also: addNewMetadata). Use this for newly created instructions in the vector loop.

Definition at line 802 of file LoopVectorize.cpp.

References addNewMetadata(), and llvm::propagateMetadata().

Referenced by addMetadata(), vectorizeMemoryInstruction(), widenInstruction(), and widenIntOrFpInduction().

◆ addMetadata() [2/2]

void InnerLoopVectorizer::addMetadata	(	ArrayRef< Value *>	To,
		Instruction *	From
	)

protected

Similar to the previous function but it adds the metadata to a vector of instructions.

Definition at line 808 of file LoopVectorize.cpp.

References addMetadata(), and I.

◆ addNewMetadata()

void InnerLoopVectorizer::addNewMetadata	(	Instruction *	To,
		const Instruction *	Orig
	)

protected

Add additional metadata to To that was not present on Orig.

Currently this is used to add the noalias annotations based on the inserted memchecks. Use this for instructions that are cloned into the vector loop.

Definition at line 794 of file LoopVectorize.cpp.

References LVer.

Referenced by addMetadata(), and scalarizeInstruction().

◆ areSafetyChecksAdded()

bool llvm::InnerLoopVectorizer::areSafetyChecksAdded ( )

inline

Definition at line 371 of file LoopVectorize.cpp.

References AddedSafetyChecks.

Referenced by llvm::LoopVectorizePass::processLoop().

◆ buildScalarSteps()

void InnerLoopVectorizer::buildScalarSteps	(	Value *	ScalarIV,
		Value *	Step,
		Instruction *	EntryVal,
		const InductionDescriptor &	ID
	)

protected

Compute scalar induction steps.

ScalarIV is the scalar induction variable on which to base the steps, Step is the size of the step, and EntryVal is the value from the original loop that maps to the steps. Note that EntryVal doesn't have to be an induction variable - it can also be a truncate instruction.

Definition at line 1783 of file LoopVectorize.cpp.

References llvm::MCID::Add, addFastMathFlag(), assert(), Builder, Cost, llvm::IRBuilder< T, Inserter >::CreateBinOp(), llvm::InductionDescriptor::getInductionOpcode(), llvm::Type::getScalarType(), getSignedIntOrFpConstant(), llvm::Value::getType(), llvm::Type::isIntegerTy(), llvm::LoopVectorizationCostModel::isUniformAfterVectorization(), recordVectorLoopValueForInductionCast(), llvm::VectorizerValueMap::setScalarValue(), UF, VectorLoopValueMap, and VF.

Referenced by widenIntOrFpInduction().

◆ createBitOrPointerCast()

Value * InnerLoopVectorizer::createBitOrPointerCast	(	Value *	V,
		VectorType *	DstVTy,
		const DataLayout &	DL
	)

protected

Returns a bitcasted value to the requested vector type.

Also handles bitcasts of vector<float> <-> vector<pointer> types.

Definition at line 2482 of file LoopVectorize.cpp.

References assert(), Builder, llvm::IRBuilder< T, Inserter >::CreateBitOrPointerCast(), llvm::VectorType::get(), llvm::Value::getContext(), llvm::SequentialType::getElementType(), llvm::Type::getIntNTy(), llvm::SequentialType::getNumElements(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), llvm::CastInst::isBitOrNoopPointerCastable(), llvm::Type::isFloatingPointTy(), llvm::Type::isPointerTy(), and VF.

Referenced by vectorizeInterleaveGroup().

◆ createInductionVariable()

PHINode * InnerLoopVectorizer::createInductionVariable	(	Loop *	L,
		Value *	Start,
		Value *	End,
		Value *	Step,
		Instruction *	DL
	)

protected

Create a new induction variable inside L.

Definition at line 2357 of file LoopVectorize.cpp.

Referenced by createVectorizedLoopSkeleton().

◆ createVectorIntOrFpInductionPHI()

void InnerLoopVectorizer::createVectorIntOrFpInductionPHI	(	const InductionDescriptor &	II,
		Value *	Step,
		Instruction *	EntryVal
	)

protected

Create a vector induction phi node based on an existing scalar one.

EntryVal is the value from the original loop that maps to the vector phi node, and Step is the loop-invariant step. If EntryVal is a truncate instruction, instead of widening the original IV, we widen a version of the IV truncated to EntryVal's type.

Definition at line 1510 of file LoopVectorize.cpp.

References assert().

Referenced by widenIntOrFpInduction().

◆ createVectorizedLoopSkeleton()

BasicBlock * InnerLoopVectorizer::createVectorizedLoopSkeleton ( )

Create a new empty loop.

Unlink the old loop and connect the new one. Return the pre-header block of the new loop.

Definition at line 2704 of file LoopVectorize.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::LoopBase< BlockT, LoopT >::addChildLoop(), llvm::PHINode::addIncoming(), llvm::LoopInfoBase< BlockT, LoopT >::addTopLevelLoop(), llvm::LoopInfoBase< BlockT, LoopT >::AllocateLoop(), assert(), B, Builder, Cost, llvm::CmpInst::Create(), llvm::PHINode::Create(), llvm::BranchInst::Create(), createInductionVariable(), emitMemRuntimeChecks(), emitMinimumIterationCountCheck(), emitSCEVChecks(), emitTransformedIndex(), llvm::LoopVectorizationCostModel::foldTailByMasking(), llvm::ConstantInt::get(), llvm::PHINode::getBasicBlockIndex(), llvm::CastInst::getCastOpcode(), llvm::Module::getDataLayout(), llvm::Instruction::getDebugLoc(), getDebugLocFromInstOrOperands(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::BasicBlock::getFirstInsertionPt(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopVectorizationLegality::getInductionVars(), llvm::Loop::getLoopID(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::BasicBlock::getModule(), getOrCreateTripCount(), getOrCreateVectorTripCount(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::LoopVectorizationLegality::getPrimaryInduction(), llvm::PredicatedScalarEvolution::getSE(), llvm::InductionDescriptor::getStartValue(), llvm::InductionDescriptor::getStep(), llvm::BasicBlock::getTerminator(), llvm::IRBuilderBase::getTrue(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::Optional< T >::getValue(), llvm::LoopVectorizationLegality::getWidestInductionType(), llvm::Optional< T >::hasValue(), llvm::CmpInst::ICMP_EQ, Induction, IVEndValues, Legal, LI, List, LLVMLoopVectorizeFollowupAll, LoopBypassBlocks, LoopExitBlock, LoopMiddleBlock, LoopScalarBody, LoopScalarPreHeader, LoopVectorBody, LoopVectorPreHeader, llvm::makeFollowupLoopID(), OldInduction, ORE, OrigLoop, PSE, llvm::ReplaceInstWithInst(), llvm::LoopVectorizeHints::setAlreadyVectorized(), llvm::Instruction::setDebugLoc(), llvm::PHINode::setIncomingValue(), llvm::IRBuilderBase::SetInsertPoint(), llvm::Loop::setLoopID(), llvm::Value::setName(), llvm::BasicBlock::splitBasicBlock(), UF, and VF.

Referenced by llvm::LoopVectorizationPlanner::executePlan(), and InnerLoopVectorizer().

◆ emitMemRuntimeChecks()

void InnerLoopVectorizer::emitMemRuntimeChecks	(	Loop *	L,
		BasicBlock *	Bypass
	)

protected

Emit bypass checks to check any memory assumptions we may have made.

Definition at line 2577 of file LoopVectorize.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), AddedSafetyChecks, llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), llvm::LoopAccessInfo::addRuntimeChecks(), assert(), Cost, llvm::BranchInst::Create(), DT, EnableVPlanNativePath, llvm::LoopVectorizationCostModel::foldTailByMasking(), llvm::LoopVectorizationLegality::getLAI(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::PredicatedScalarEvolution::getSE(), llvm::BasicBlock::getTerminator(), Legal, LI, LoopBypassBlocks, LVer, OrigLoop, PSE, llvm::ReplaceInstWithInst(), llvm::Value::setName(), and llvm::BasicBlock::splitBasicBlock().

Referenced by createVectorizedLoopSkeleton().

◆ emitMinimumIterationCountCheck()

void InnerLoopVectorizer::emitMinimumIterationCountCheck	(	Loop *	L,
		BasicBlock *	Bypass
	)

protected

Emit a bypass check to see if the vector trip count is zero, including if it overflows.

Definition at line 2512 of file LoopVectorize.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), Builder, Cost, llvm::BranchInst::Create(), llvm::IRBuilder< T, Inserter >::CreateICmp(), DT, llvm::LoopVectorizationCostModel::foldTailByMasking(), llvm::ConstantInt::get(), llvm::IRBuilderBase::getFalse(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), getOrCreateTripCount(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, LI, LoopBypassBlocks, P, llvm::ReplaceInstWithInst(), llvm::LoopVectorizationCostModel::requiresScalarEpilogue(), llvm::BasicBlock::splitBasicBlock(), UF, and VF.

Referenced by createVectorizedLoopSkeleton().

◆ emitSCEVChecks()

void InnerLoopVectorizer::emitSCEVChecks	(	Loop *	L,
		BasicBlock *	Bypass
	)

protected

Emit a bypass check to see if all of the SCEV assumptions we've had to make are correct.

Definition at line 2545 of file LoopVectorize.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), AddedSafetyChecks, llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), assert(), C, Cost, llvm::BranchInst::Create(), DT, llvm::LoopVectorizationCostModel::foldTailByMasking(), llvm::Module::getDataLayout(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::BasicBlock::getModule(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::PredicatedScalarEvolution::getSE(), llvm::BasicBlock::getTerminator(), llvm::PredicatedScalarEvolution::getUnionPredicate(), LI, LoopBypassBlocks, PSE, llvm::ReplaceInstWithInst(), llvm::Value::setName(), and llvm::BasicBlock::splitBasicBlock().

Referenced by createVectorizedLoopSkeleton().

◆ emitTransformedIndex()

Value * InnerLoopVectorizer::emitTransformedIndex	(	IRBuilder<> &	B,
		Value *	Index,
		ScalarEvolution *	SE,
		const DataLayout &	DL,
		const InductionDescriptor &	ID
	)		const

protected

Compute the transformed value of Index at offset StartValue using step StepValue.

For integer induction, returns StartValue + Index * StepValue. For pointer induction, returns StartValue[Index * StepValue]. FIXME: The newly created binary instructions should contain nsw/nuw flags, which can be found from the original scalar operations.

Definition at line 2616 of file LoopVectorize.cpp.

Referenced by createVectorizedLoopSkeleton(), fixupIVUsers(), widenIntOrFpInduction(), and widenPHIInstruction().

◆ fixCrossIterationPHIs()

void InnerLoopVectorizer::fixCrossIterationPHIs ( )

protected

Handle all cross-iteration phis in the header.

Definition at line 3302 of file LoopVectorize.cpp.

References fixFirstOrderRecurrence(), fixReduction(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopVectorizationLegality::isFirstOrderRecurrence(), llvm::LoopVectorizationLegality::isReductionVariable(), Legal, OrigLoop, and llvm::BasicBlock::phis().

Referenced by fixVectorizedLoop().

◆ fixFirstOrderRecurrence()

void InnerLoopVectorizer::fixFirstOrderRecurrence ( PHINode * Phi )

protected

Fix a first-order recurrence.

This is the second phase of vectorizing this phi node.

Definition at line 3318 of file LoopVectorize.cpp.

References llvm::PHINode::addIncoming(), llvm::BasicBlock::begin(), Builder, llvm::IRBuilder< T, Inserter >::CreateExtractElement(), llvm::IRBuilder< T, Inserter >::CreateInsertElement(), llvm::IRBuilder< T, Inserter >::CreatePHI(), llvm::IRBuilder< T, Inserter >::CreateShuffleVector(), llvm::VectorType::get(), llvm::ConstantVector::get(), llvm::UndefValue::get(), llvm::BasicBlock::getFirstInsertionPt(), llvm::PHINode::getIncomingValueForBlock(), llvm::IRBuilderBase::getInt32(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), getOrCreateVectorValue(), llvm::BasicBlock::getTerminator(), llvm::VectorizerValueMap::getVectorValue(), I, llvm::Loop::isLoopInvariant(), LI, LoopMiddleBlock, LoopScalarPreHeader, LoopVectorBody, LoopVectorPreHeader, OrigLoop, llvm::Value::replaceAllUsesWith(), llvm::VectorizerValueMap::resetVectorValue(), llvm::IRBuilderBase::SetInsertPoint(), UF, VectorLoopValueMap, and VF.

Referenced by fixCrossIterationPHIs().

◆ fixLCSSAPHIs()

void InnerLoopVectorizer::fixLCSSAPHIs ( )

protected

The Loop exit block may have single value PHI nodes with some incoming value.

While vectorizing we only handled real values that were defined inside the loop and we should have one value for each predecessor of its parent basic block. See PR14725.

Definition at line 3659 of file LoopVectorize.cpp.

References Builder, Cost, getOrCreateScalarValue(), llvm::BasicBlock::getTerminator(), llvm::LoopVectorizationCostModel::isUniformAfterVectorization(), LoopExitBlock, LoopMiddleBlock, llvm::BasicBlock::phis(), llvm::IRBuilderBase::SetInsertPoint(), UF, and VF.

Referenced by fixVectorizedLoop().

◆ fixNonInductionPHIs()

void InnerLoopVectorizer::fixNonInductionPHIs ( void )

Fix the non-induction PHIs in the OrigPHIsToFix vector.

Definition at line 3744 of file LoopVectorize.cpp.

References llvm::PHINode::addIncoming(), assert(), Builder, llvm::PHINode::getNumIncomingValues(), getOrCreateVectorValue(), llvm::Instruction::getParent(), llvm::VectorizerValueMap::getVectorValue(), OrigPHIsToFix, llvm::predecessors(), llvm::IRBuilderBase::SetInsertPoint(), llvm::SmallVectorBase::size(), and VectorLoopValueMap.

Referenced by fixVectorizedLoop().

◆ fixReduction()

void InnerLoopVectorizer::fixReduction ( PHINode * Phi )

protected

Fix a reduction cross-iteration phi.

This is the second phase of vectorizing this phi node.

Definition at line 3486 of file LoopVectorize.cpp.

References addFastMathFlag(), llvm::PHINode::addIncoming(), assert(), Builder, llvm::PHINode::Create(), llvm::IRBuilder< T, Inserter >::CreateBinOp(), llvm::IRBuilder< T, Inserter >::CreateInsertElement(), llvm::createMinMaxOp(), llvm::IRBuilder< T, Inserter >::CreateSExt(), llvm::createTargetReduction(), llvm::IRBuilder< T, Inserter >::CreateTrunc(), llvm::IRBuilder< T, Inserter >::CreateVectorSplat(), llvm::IRBuilder< T, Inserter >::CreateZExt(), E, llvm::VectorType::get(), llvm::PHINode::getBasicBlockIndex(), llvm::BasicBlock::getFirstInsertionPt(), llvm::PHINode::getIncomingValueForBlock(), llvm::IRBuilderBase::getInt32(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), getOrCreateVectorValue(), llvm::RecurrenceDescriptor::getRecurrenceBinOp(), llvm::RecurrenceDescriptor::getRecurrenceIdentity(), llvm::RecurrenceDescriptor::getRecurrenceKind(), llvm::LoopVectorizationLegality::getReductionVars(), llvm::Type::getScalarType(), llvm::ConstantVector::getSplat(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::VectorizerValueMap::getVectorValue(), llvm::LoopVectorizationLegality::hasFunNoNaNAttr(), I, llvm::LoopVectorizationLegality::isReductionVariable(), Legal, LI, LoopBypassBlocks, LoopExitBlock, LoopMiddleBlock, LoopScalarPreHeader, LoopVectorBody, LoopVectorPreHeader, OrigLoop, llvm::BasicBlock::phis(), llvm::VectorizerValueMap::resetVectorValue(), llvm::RecurrenceDescriptor::RK_FloatMinMax, llvm::RecurrenceDescriptor::RK_IntegerMinMax, setDebugLocFromInst(), llvm::PHINode::setIncomingValue(), llvm::IRBuilderBase::SetInsertPoint(), TTI, UF, VectorLoopValueMap, and VF.

Referenced by fixCrossIterationPHIs().

◆ fixupIVUsers()

void InnerLoopVectorizer::fixupIVUsers	(	PHINode *	OrigPhi,
		const InductionDescriptor &	II,
		Value *	CountRoundDown,
		Value *	EndValue,
		BasicBlock *	MiddleBlock
	)

protected

Set up the values of the IVs correctly when exiting the vector loop.

Definition at line 2910 of file LoopVectorize.cpp.

References llvm::PHINode::addIncoming(), assert(), B, llvm::LoopBase< BlockT, LoopT >::contains(), emitTransformedIndex(), llvm::ConstantInt::get(), llvm::PHINode::getBasicBlockIndex(), llvm::Module::getDataLayout(), llvm::LoopBase< BlockT, LoopT >::getExitBlock(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::BasicBlock::getModule(), llvm::Instruction::getOpcode(), llvm::PredicatedScalarEvolution::getSE(), llvm::InductionDescriptor::getStep(), llvm::BasicBlock::getTerminator(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::hash_combine(), llvm::hash_combine_range(), I, isEqual(), llvm::Instruction::isIdenticalTo(), llvm::Type::isIntegerTy(), OrigLoop, llvm::HexagonII::PostInc, PSE, llvm::Value::setName(), llvm::Value::users(), llvm::User::value_op_begin(), and llvm::User::value_op_end().

Referenced by fixVectorizedLoop().

◆ fixVectorizedLoop()

void InnerLoopVectorizer::fixVectorizedLoop ( )

Fix the vectorized code, taking care of header phi's, live-outs, and more.

Definition at line 3259 of file LoopVectorize.cpp.

References assert(), cse(), EnableVPlanNativePath, fixCrossIterationPHIs(), fixLCSSAPHIs(), fixNonInductionPHIs(), fixupIVUsers(), llvm::LoopVectorizationLegality::getInductionVars(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), getOrCreateVectorTripCount(), IVEndValues, Legal, LI, LoopMiddleBlock, LoopVectorBody, OrigPHIsToFix, PredicatedInstructions, sinkScalarOperands(), truncateToMinimalBitwidths(), updateAnalysis(), and VF.

Referenced by llvm::LoopVectorizationPlanner::executePlan(), and InnerLoopVectorizer().

◆ getBroadcastInstrs()

Value * InnerLoopVectorizer::getBroadcastInstrs ( Value * V )

protectedvirtual

Create a broadcast instruction.

This method generates a broadcast instruction (shuffle) for loop invariant values and for the induction value. If this is the induction variable then we extend it to N, N+1, ... this is needed because each iteration in the loop corresponds to a SIMD element.

Definition at line 1491 of file LoopVectorize.cpp.

References Builder, llvm::IRBuilder< T, Inserter >::CreateVectorSplat(), llvm::DominatorTree::dominates(), DT, llvm::dyn_cast(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::Loop::isLoopInvariant(), LoopVectorPreHeader, OrigLoop, llvm::IRBuilderBase::SetInsertPoint(), and VF.

Referenced by getOrCreateVectorValue(), llvm::InnerLoopUnroller::InnerLoopUnroller(), and widenIntOrFpInduction().

◆ getOrCreateScalarValue()

Value * InnerLoopVectorizer::getOrCreateScalarValue	(	Value *	V,
		const VPIteration &	Instance
	)

Return a value in the new loop corresponding to V from the original loop at unroll and vector indices Instance.

If the value has been vectorized but not scalarized, the necessary extractelement instruction will be generated.

Definition at line 1898 of file LoopVectorize.cpp.

References assert(), Builder, Cost, llvm::IRBuilder< T, Inserter >::CreateExtractElement(), llvm::IRBuilderBase::getInt32(), getOrCreateVectorValue(), llvm::VectorizerValueMap::getScalarValue(), llvm::VectorizerValueMap::hasScalarValue(), llvm::Loop::isLoopInvariant(), llvm::LoopVectorizationCostModel::isUniformAfterVectorization(), llvm::VPIteration::Lane, OrigLoop, llvm::VPIteration::Part, VectorLoopValueMap, and VF.

Referenced by fixLCSSAPHIs(), scalarizeInstruction(), vectorizeInterleaveGroup(), vectorizeMemoryInstruction(), and widenInstruction().

◆ getOrCreateTripCount()

Value * InnerLoopVectorizer::getOrCreateTripCount ( Loop * NewLoop )

protected

Returns (and creates if needed) the original loop trip count.

Definition at line 2389 of file LoopVectorize.cpp.

References assert(), Builder, llvm::CastInst::CreatePointerCast(), llvm::SCEVExpander::expandCodeFor(), llvm::PredicatedScalarEvolution::getBackedgeTakenCount(), llvm::Module::getDataLayout(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::BasicBlock::getModule(), llvm::Type::getPrimitiveSizeInBits(), llvm::PredicatedScalarEvolution::getSE(), llvm::BasicBlock::getTerminator(), llvm::SCEV::getType(), llvm::Value::getType(), llvm::LoopVectorizationLegality::getWidestInductionType(), llvm::Type::isPointerTy(), Legal, PSE, and TripCount.

Referenced by createVectorizedLoopSkeleton(), emitMinimumIterationCountCheck(), llvm::LoopVectorizationPlanner::executePlan(), and getOrCreateVectorTripCount().

◆ getOrCreateVectorTripCount()

Value * InnerLoopVectorizer::getOrCreateVectorTripCount ( Loop * NewLoop )

protected

Returns (and creates if needed) the trip count of the widened loop.

Definition at line 2436 of file LoopVectorize.cpp.

References assert(), Builder, Cost, llvm::IRBuilder< T, Inserter >::CreateAdd(), llvm::IRBuilder< T, Inserter >::CreateICmpEQ(), llvm::IRBuilder< T, Inserter >::CreateSelect(), llvm::IRBuilder< T, Inserter >::CreateSub(), llvm::IRBuilder< T, Inserter >::CreateURem(), llvm::LoopVectorizationCostModel::foldTailByMasking(), llvm::ConstantInt::get(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), getOrCreateTripCount(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::isPowerOf2_32(), llvm::LoopVectorizationCostModel::requiresScalarEpilogue(), UF, VectorTripCount, and VF.

Referenced by createVectorizedLoopSkeleton(), and fixVectorizedLoop().

◆ getOrCreateVectorValue()

Value * InnerLoopVectorizer::getOrCreateVectorValue	(	Value *	V,
		unsigned	Part
	)

getOrCreateVectorValue and getOrCreateScalarValue coordinate to generate a vector or scalar value on-demand if one is not yet available.

When vectorizing a loop, we visit the definition of an instruction before its uses. When visiting the definition, we either vectorize or scalarize the instruction, creating an entry for it in the corresponding map. (In some cases, such as induction variables, we will create both vector and scalar entries.) Then, as we encounter uses of the definition, we derive values for each scalar or vector use unless such a value is already available. For example, if we scalarize a definition and one of its uses is vector, we build the required vector on-demand with an insertelement sequence when visiting the use. Otherwise, if the use is scalar, we can use the existing scalar definition.

Return a value in the new loop corresponding to V from the original loop at unroll index Part. If the value has already been vectorized, the corresponding vector entry in VectorLoopValueMap is returned. If, however, the value has a scalar entry in VectorLoopValueMap, we construct a new vector value on-demand by inserting the scalar values into a vector with an insertelement sequence. If the value has been neither vectorized nor scalarized, it must be loop invariant, so we simply broadcast the value into a vector.

Definition at line 1824 of file LoopVectorize.cpp.

References assert(), B, Builder, Cost, EnableVPlanNativePath, llvm::ConstantInt::get(), llvm::VectorType::get(), llvm::UndefValue::get(), getBroadcastInstrs(), llvm::VectorizerValueMap::getScalarValue(), llvm::Value::getType(), llvm::VectorizerValueMap::getVectorValue(), llvm::VectorizerValueMap::hasAnyScalarValue(), llvm::LoopVectorizationLegality::hasStride(), llvm::VectorizerValueMap::hasVectorValue(), I, Induction, llvm::LoopVectorizationCostModel::isUniformAfterVectorization(), llvm::Type::isVectorTy(), llvm::Type::isVoidTy(), Legal, packScalarIntoVectorValue(), llvm::IRBuilderBase::restoreIP(), llvm::IRBuilderBase::saveIP(), llvm::IRBuilderBase::SetInsertPoint(), llvm::VectorizerValueMap::setVectorValue(), llvm::RegState::Undef, VectorLoopValueMap, and VF.

Referenced by llvm::VPBlendRecipe::execute(), fixFirstOrderRecurrence(), fixNonInductionPHIs(), fixReduction(), getOrCreateScalarValue(), truncateToMinimalBitwidths(), vectorizeInterleaveGroup(), vectorizeMemoryInstruction(), and widenInstruction().

◆ getStepVector()

Value * InnerLoopVectorizer::getStepVector	(	Value *	Val,
		int	StartIdx,
		Value *	Step,
		Instruction::BinaryOps	Opcode = `Instruction::BinaryOpsEnd`
	)

protectedvirtual

This function adds (StartIdx, StartIdx + Step, StartIdx + 2*Step, ...) to each vector element of Val.

The sequence starts at StartIndex. Opcode is relevant for FP induction variable.

Definition at line 1727 of file LoopVectorize.cpp.

References assert(), Builder, llvm::IRBuilder< T, Inserter >::CreateAdd(), llvm::IRBuilder< T, Inserter >::CreateBinOp(), llvm::IRBuilder< T, Inserter >::CreateFMul(), llvm::IRBuilder< T, Inserter >::CreateMul(), llvm::IRBuilder< T, Inserter >::CreateVectorSplat(), llvm::ConstantInt::get(), llvm::ConstantFP::get(), llvm::ConstantVector::get(), llvm::Type::getScalarType(), llvm::Value::getType(), llvm::Type::getVectorNumElements(), llvm::Type::isFloatingPointTy(), llvm::Type::isIntegerTy(), llvm::Type::isVectorTy(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::FastMathFlags::setFast().

Referenced by llvm::InnerLoopUnroller::InnerLoopUnroller(), and widenIntOrFpInduction().

◆ needsScalarInduction()

bool InnerLoopVectorizer::needsScalarInduction ( Instruction * IV ) const

protected

Returns true if we should generate a scalar version of IV.

Definition at line 1592 of file LoopVectorize.cpp.

References llvm::any_of(), llvm::LoopBase< BlockT, LoopT >::contains(), I, OrigLoop, shouldScalarizeInstruction(), and llvm::Value::users().

Referenced by widenIntOrFpInduction().

◆ packScalarIntoVectorValue()

void InnerLoopVectorizer::packScalarIntoVectorValue	(	Value *	V,
		const VPIteration &	Instance
	)

Construct the vector value of a scalarized value V one lane at a time.

Definition at line 1931 of file LoopVectorize.cpp.

References assert(), Builder, llvm::IRBuilder< T, Inserter >::CreateInsertElement(), llvm::IRBuilderBase::getInt32(), llvm::VectorizerValueMap::getScalarValue(), llvm::Value::getType(), llvm::VectorizerValueMap::getVectorValue(), Induction, llvm::Type::isVectorTy(), llvm::Type::isVoidTy(), llvm::VPIteration::Lane, llvm::VPIteration::Part, llvm::VectorizerValueMap::resetVectorValue(), and VectorLoopValueMap.

Referenced by llvm::VPReplicateRecipe::execute(), and getOrCreateVectorValue().

◆ recordVectorLoopValueForInductionCast()

void InnerLoopVectorizer::recordVectorLoopValueForInductionCast	(	const InductionDescriptor &	ID,
		const Instruction *	EntryVal,
		Value *	VectorLoopValue,
		unsigned	Part,
		unsigned	Lane = `UINT_MAX`
	)

protected

If there is a cast involved in the induction variable ID, which should be ignored in the vectorized loop body, this function records the VectorLoopValue of the respective Phi also as the VectorLoopValue of the cast.

We had already proved that the casted Phi is equal to the uncasted Phi in the vectorized loop (under a runtime guard), and therefore there is no need to vectorize the cast - the same value can be used in the vector loop for both the Phi and the cast. If VectorLoopValue is a scalarized value, Lane is also specified, Otherwise, VectorLoopValue is a widened/vectorized value.

EntryVal is the value from the original loop that maps to the vector phi node and is used to distinguish what is the IV currently being processed - original one (if EntryVal is a phi corresponding to the original IV) or the "newly-created" one based on the proof mentioned above (see also buildScalarSteps() and createVectorIntOrFPInductionPHI()). In the latter case EntryVal is a TruncInst and we must not record anything for that IV, but it's error-prone to expect callers of this routine to care about that, hence this explicit parameter.

Definition at line 1602 of file LoopVectorize.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorBase::empty(), llvm::InductionDescriptor::getCastInsts(), llvm::VectorizerValueMap::setScalarValue(), llvm::VectorizerValueMap::setVectorValue(), and VectorLoopValueMap.

Referenced by buildScalarSteps(), and widenIntOrFpInduction().

◆ reverseVector()

Value * InnerLoopVectorizer::reverseVector ( Value * Vec )

protectedvirtual

Generate a shuffle sequence that will reverse the vector Vec.

Definition at line 1944 of file LoopVectorize.cpp.

References assert(), Builder, llvm::IRBuilder< T, Inserter >::CreateShuffleVector(), llvm::ConstantVector::get(), llvm::UndefValue::get(), llvm::IRBuilderBase::getInt32(), llvm::Value::getType(), llvm::Type::isVectorTy(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and VF.

Referenced by llvm::InnerLoopUnroller::InnerLoopUnroller(), vectorizeInterleaveGroup(), and vectorizeMemoryInstruction().

◆ scalarizeInstruction()

void InnerLoopVectorizer::scalarizeInstruction	(	Instruction *	Instr,
		const VPIteration &	Instance,
		bool	IfPredicateInstr
	)

A helper function to scalarize a single Instruction in the innermost loop.

Generates a sequence of scalar instances for each lane between MinLane and MaxLane, times each part between MinPart and MaxPart, inclusive..

Definition at line 2319 of file LoopVectorize.cpp.

References AC, addNewMetadata(), assert(), llvm::Intrinsic::assume, Builder, llvm::Instruction::clone(), llvm::Value::getName(), llvm::User::getNumOperands(), llvm::User::getOperand(), getOrCreateScalarValue(), llvm::Value::getType(), llvm::IRBuilder< T, Inserter >::Insert(), llvm::Type::isAggregateType(), llvm::Type::isVoidTy(), op, PredicatedInstructions, llvm::AssumptionCache::registerAssumption(), setDebugLocFromInst(), llvm::Value::setName(), llvm::User::setOperand(), llvm::VectorizerValueMap::setScalarValue(), and VectorLoopValueMap.

Referenced by llvm::VPReplicateRecipe::execute().

◆ setDebugLocFromInst()

void InnerLoopVectorizer::setDebugLocFromInst	(	IRBuilder<> &	B,
		const Value *	Ptr
	)

Set the debug location in the builder using the debug location in the instruction.

Definition at line 758 of file LoopVectorize.cpp.

References llvm::DILocation::cloneWithDuplicationFactor(), llvm::dbgs(), LLVM_DEBUG, llvm::IRBuilderBase::SetCurrentDebugLocation(), UF, and VF.

Referenced by llvm::VPBlendRecipe::execute(), fixReduction(), scalarizeInstruction(), vectorizeInterleaveGroup(), vectorizeMemoryInstruction(), widenInstruction(), and widenPHIInstruction().

◆ shouldScalarizeInstruction()

bool InnerLoopVectorizer::shouldScalarizeInstruction ( Instruction * I ) const

protected

Returns true if an instruction I should be scalarized instead of vectorized for the chosen vectorization factor.

Definition at line 1587 of file LoopVectorize.cpp.

References Cost, llvm::LoopVectorizationCostModel::isProfitableToScalarize(), llvm::LoopVectorizationCostModel::isScalarAfterVectorization(), and VF.

Referenced by needsScalarInduction(), and widenIntOrFpInduction().

◆ sinkScalarOperands()

void InnerLoopVectorizer::sinkScalarOperands ( Instruction * PredInst )

protected

Iteratively sink the scalarized operands of a predicated instruction into the block that was created for it.

Definition at line 3680 of file LoopVectorize.cpp.

References llvm::all_of(), llvm::SetVector< T, Vector, Set >::begin(), llvm::SetVector< T, Vector, Set >::clear(), llvm::dyn_cast(), llvm::SetVector< T, Vector, Set >::end(), llvm::PHINode::getIncomingValueNumForOperand(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::Instruction::getParent(), I, LI, llvm::User::op_begin(), and llvm::User::op_end().

Referenced by fixVectorizedLoop().

◆ truncateToMinimalBitwidths()

void InnerLoopVectorizer::truncateToMinimalBitwidths ( )

protected

Shrinks vector element sizes to the smallest bitwidth they can be legally represented as.

Definition at line 3133 of file LoopVectorize.cpp.

Referenced by fixVectorizedLoop().

◆ updateAnalysis()

void InnerLoopVectorizer::updateAnalysis ( )

protected

Insert the new loop to the loop hierarchy and pass manager and update the analysis passes.

Definition at line 4151 of file LoopVectorize.cpp.

References llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), llvm::all_of(), assert(), llvm::sys::path::begin(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::dbgs(), DT, EnableVPlanNativePath, llvm::sys::path::end(), llvm::SmallPtrSetImpl< PtrType >::end(), llvm::CallingConv::Fast, llvm::SmallPtrSetImpl< PtrType >::find(), llvm::ScalarEvolution::forgetLoop(), llvm::LoopVectorizationLegality::getInductionVars(), llvm::getLoadStorePointerOperand(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::User::getOperand(), llvm::PredicatedScalarEvolution::getSE(), I, llvm::InductionDescriptor::IK_PtrInduction, Induction, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), Legal, LI, LLVM_DEBUG, llvm::SPII::Load, LoopBypassBlocks, LoopExitBlock, LoopMiddleBlock, LoopScalarBody, LoopScalarPreHeader, LoopVectorBody, OrigLoop, llvm::DominatorTreeBase< NodeT, IsPostDom >::properlyDominates(), PSE, llvm::SPII::Store, llvm::DominatorTreeBase< NodeT, IsPostDom >::verify(), and VF.

Referenced by fixVectorizedLoop().

◆ vectorizeInterleaveGroup()

void InnerLoopVectorizer::vectorizeInterleaveGroup	(	Instruction *	Instr,
		VectorParts *	BlockInMask = `nullptr`
	)

Try to vectorize the interleaved access group that Instr belongs to, optionally masking the vector operations if BlockInMask is non-null.

Definition at line 1994 of file LoopVectorize.cpp.

Referenced by llvm::VPInterleaveRecipe::execute(), and vectorizeMemoryInstruction().

◆ vectorizeMemoryInstruction()

void InnerLoopVectorizer::vectorizeMemoryInstruction	(	Instruction *	Instr,
		VectorParts *	BlockInMask = `nullptr`
	)

Vectorize Load and Store instructions, optionally masking the vector operations if BlockInMask is non-null.

Definition at line 2181 of file LoopVectorize.cpp.

References addMetadata(), assert(), Builder, llvm::LoopVectorizationCostModel::CM_GatherScatter, llvm::LoopVectorizationCostModel::CM_Interleave, llvm::LoopVectorizationCostModel::CM_Unknown, llvm::LoopVectorizationCostModel::CM_Widen, llvm::LoopVectorizationCostModel::CM_Widen_Reverse, Cost, llvm::IRBuilder< T, Inserter >::CreateAlignedLoad(), llvm::IRBuilder< T, Inserter >::CreateAlignedStore(), llvm::IRBuilder< T, Inserter >::CreateBitCast(), llvm::IRBuilder< T, Inserter >::CreateGEP(), llvm::IRBuilderBase::CreateMaskedGather(), llvm::IRBuilderBase::CreateMaskedLoad(), llvm::IRBuilderBase::CreateMaskedScatter(), llvm::IRBuilderBase::CreateMaskedStore(), llvm::dyn_cast(), gep, llvm::VectorType::get(), llvm::UndefValue::get(), llvm::DataLayout::getABITypeAlignment(), llvm::Module::getDataLayout(), llvm::IRBuilderBase::getInt32(), llvm::getLoadStoreAddressSpace(), llvm::getLoadStoreAlignment(), llvm::getLoadStorePointerOperand(), getMemInstValueType(), llvm::Instruction::getModule(), getOrCreateScalarValue(), getOrCreateVectorValue(), llvm::Type::getPointerTo(), llvm::LoopVectorizationCostModel::getWideningDecision(), LI, llvm::BitmaskEnumDetail::Mask(), reverseVector(), setDebugLocFromInst(), llvm::GetElementPtrInst::setIsInBounds(), llvm::VectorizerValueMap::setVectorValue(), SI, UF, vectorizeInterleaveGroup(), VectorLoopValueMap, and VF.

Referenced by llvm::VPWidenMemoryInstructionRecipe::execute().

◆ widenInstruction()

void InnerLoopVectorizer::widenInstruction ( Instruction & I )

Widen a single instruction within the innermost loop.

Vectorize casts.

Definition at line 3878 of file LoopVectorize.cpp.

Referenced by InnerLoopVectorizer().

◆ widenIntOrFpInduction()

void InnerLoopVectorizer::widenIntOrFpInduction	(	PHINode *	IV,
		TruncInst *	Trunc = `nullptr`
	)

Widen an integer or floating-point induction variable IV.

If Trunc is provided, the integer induction variable will first be truncated to the corresponding type.

Definition at line 1630 of file LoopVectorize.cpp.

References addMetadata(), assert(), Builder, buildScalarSteps(), llvm::IRBuilder< T, Inserter >::CreateCast(), llvm::IRBuilder< T, Inserter >::CreateSExtOrTrunc(), llvm::IRBuilder< T, Inserter >::CreateTrunc(), createVectorIntOrFpInductionPHI(), emitTransformedIndex(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::end(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::find(), getBroadcastInstrs(), llvm::Module::getDataLayout(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopVectorizationLegality::getInductionVars(), llvm::BasicBlock::getModule(), llvm::PredicatedScalarEvolution::getSE(), getStepVector(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), Induction, llvm::Type::isIntegerTy(), llvm::ScalarEvolution::isLoopInvariant(), llvm::ScalarEvolution::isSCEVable(), Legal, LoopVectorPreHeader, needsScalarInduction(), OldInduction, OrigLoop, PSE, recordVectorLoopValueForInductionCast(), llvm::Value::setName(), llvm::VectorizerValueMap::setVectorValue(), shouldScalarizeInstruction(), UF, VectorLoopValueMap, and VF.

Referenced by llvm::VPWidenIntOrFpInductionRecipe::execute().

◆ widenPHIInstruction()

void InnerLoopVectorizer::widenPHIInstruction	(	Instruction *	PN,
		unsigned	UF,
		unsigned	VF
	)

Vectorize a single PHINode in a block.

This method handles the induction variable canonicalization. It supports both VF = 1 for unrolled loops and arbitrary length vectors.

Definition at line 3780 of file LoopVectorize.cpp.

References assert(), Builder, Cost, llvm::MapVector< KeyT, ValueT, MapType, VectorType >::count(), llvm::PHINode::Create(), llvm::IRBuilder< T, Inserter >::CreateAdd(), llvm::IRBuilder< T, Inserter >::CreatePHI(), llvm::IRBuilder< T, Inserter >::CreateSExtOrTrunc(), emitTransformedIndex(), EnableVPlanNativePath, llvm::ConstantInt::get(), llvm::VectorType::get(), llvm::Module::getDataLayout(), llvm::BasicBlock::getFirstInsertionPt(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopVectorizationLegality::getInductionVars(), llvm::BasicBlock::getModule(), llvm::User::getNumOperands(), llvm::Instruction::getParent(), llvm::PredicatedScalarEvolution::getSE(), llvm::Value::getType(), llvm::InductionDescriptor::IK_FpInduction, llvm::InductionDescriptor::IK_IntInduction, llvm::InductionDescriptor::IK_NoInduction, llvm::InductionDescriptor::IK_PtrInduction, Induction, llvm::LoopVectorizationLegality::isFirstOrderRecurrence(), llvm::Type::isPointerTy(), llvm::LoopVectorizationLegality::isReductionVariable(), llvm::LoopVectorizationCostModel::isUniformAfterVectorization(), Legal, llvm_unreachable, llvm::MapVector< KeyT, ValueT, MapType, VectorType >::lookup(), LoopVectorBody, OrigLoop, OrigPHIsToFix, P, PSE, setDebugLocFromInst(), llvm::Value::setName(), llvm::VectorizerValueMap::setScalarValue(), llvm::VectorizerValueMap::setVectorValue(), UF, VectorLoopValueMap, and VF.

Referenced by llvm::VPWidenPHIRecipe::execute().

Friends And Related Function Documentation

◆ LoopVectorizationPlanner

friend class LoopVectorizationPlanner

friend

Definition at line 445 of file LoopVectorize.cpp.

Member Data Documentation

◆ AA

AliasAnalysis* llvm::InnerLoopVectorizer::AA

protected

Alias Analysis.

Definition at line 623 of file LoopVectorize.cpp.

Referenced by collectSupportedLoops(), llvm::LoopVectorizePass::processLoop(), llvm::LoopVectorizePass::run(), and llvm::LoopVectorizePass::runImpl().

◆ AC

AssumptionCache* llvm::InnerLoopVectorizer::AC

protected

Assumption Cache.

Definition at line 632 of file LoopVectorize.cpp.

Referenced by collectSupportedLoops(), llvm::LoopVectorizationCostModel::collectValuesToIgnore(), llvm::LoopVectorizePass::processLoop(), llvm::LoopVectorizePass::run(), llvm::LoopVectorizePass::runImpl(), and scalarizeInstruction().

◆ AddedSafetyChecks

bool llvm::InnerLoopVectorizer::AddedSafetyChecks = false

protected

Definition at line 706 of file LoopVectorize.cpp.

Referenced by areSafetyChecksAdded(), emitMemRuntimeChecks(), and emitSCEVChecks().

◆ Builder

IRBuilder llvm::InnerLoopVectorizer::Builder

protected

The builder that we use.

Definition at line 653 of file LoopVectorize.cpp.

Referenced by buildScalarSteps(), llvm::LoopVectorizationPlanner::collectTriviallyDeadInstructions(), createBitOrPointerCast(), llvm::VPRecipeBuilder::createBlockInMask(), llvm::VPRecipeBuilder::createEdgeMask(), createVectorizedLoopSkeleton(), emitMinimumIterationCountCheck(), llvm::LoopVectorizationPlanner::executePlan(), fixFirstOrderRecurrence(), fixLCSSAPHIs(), fixNonInductionPHIs(), fixReduction(), getBroadcastInstrs(), getOrCreateScalarValue(), getOrCreateTripCount(), getOrCreateVectorTripCount(), getOrCreateVectorValue(), getStepVector(), packScalarIntoVectorValue(), reverseVector(), scalarizeInstruction(), llvm::VPRecipeBuilder::tryToCreateRecipe(), vectorizeInterleaveGroup(), vectorizeMemoryInstruction(), widenInstruction(), widenIntOrFpInduction(), and widenPHIInstruction().

◆ Cost

LoopVectorizationCostModel* llvm::InnerLoopVectorizer::Cost

protected

◆ DT

DominatorTree* llvm::InnerLoopVectorizer::DT

protected

Dominator Tree.

Definition at line 620 of file LoopVectorize.cpp.

Referenced by collectSupportedLoops(), emitMemRuntimeChecks(), emitMinimumIterationCountCheck(), emitSCEVChecks(), llvm::LoopVectorizationPlanner::executePlan(), getBroadcastInstrs(), llvm::LoopVectorizePass::processLoop(), llvm::LoopVectorizePass::run(), llvm::LoopVectorizePass::runImpl(), and updateAnalysis().

◆ Induction

PHINode* llvm::InnerLoopVectorizer::Induction = nullptr

protected

The new Induction variable which was added to the new block.

Definition at line 679 of file LoopVectorize.cpp.

Referenced by llvm::LoopVectorizationPlanner::collectTriviallyDeadInstructions(), llvm::LoopVectorizationCostModel::collectValuesToIgnore(), createVectorizedLoopSkeleton(), getOrCreateVectorValue(), llvm::LoopVectorizationCostModel::memoryInstructionCanBeWidened(), packScalarIntoVectorValue(), updateAnalysis(), widenIntOrFpInduction(), and widenPHIInstruction().

◆ IVEndValues

DenseMap<PHINode *, Value *> llvm::InnerLoopVectorizer::IVEndValues

protected

Definition at line 710 of file LoopVectorize.cpp.

Referenced by createVectorizedLoopSkeleton(), and fixVectorizedLoop().

◆ Legal

LoopVectorizationLegality* llvm::InnerLoopVectorizer::Legal

protected

The legality analysis.

Definition at line 700 of file LoopVectorize.cpp.

◆ LI

LoopInfo* llvm::InnerLoopVectorizer::LI

protected

◆ LoopBypassBlocks

SmallVector<BasicBlock *, 4> llvm::InnerLoopVectorizer::LoopBypassBlocks

protected

A list of all bypass blocks. The first block is the entry of the loop.

Definition at line 676 of file LoopVectorize.cpp.

Referenced by createVectorizedLoopSkeleton(), emitMemRuntimeChecks(), emitMinimumIterationCountCheck(), emitSCEVChecks(), fixReduction(), and updateAnalysis().

◆ LoopExitBlock

BasicBlock* llvm::InnerLoopVectorizer::LoopExitBlock

protected

The ExitBlock of the scalar loop.

Definition at line 667 of file LoopVectorize.cpp.

Referenced by createVectorizedLoopSkeleton(), fixLCSSAPHIs(), fixReduction(), and updateAnalysis().

◆ LoopMiddleBlock

BasicBlock* llvm::InnerLoopVectorizer::LoopMiddleBlock

protected

Middle Block between the vector and the scalar.

Definition at line 664 of file LoopVectorize.cpp.

Referenced by createVectorizedLoopSkeleton(), fixFirstOrderRecurrence(), fixLCSSAPHIs(), fixReduction(), fixVectorizedLoop(), and updateAnalysis().

◆ LoopScalarBody

BasicBlock* llvm::InnerLoopVectorizer::LoopScalarBody

protected

The scalar loop body.

Definition at line 673 of file LoopVectorize.cpp.

Referenced by createVectorizedLoopSkeleton(), and updateAnalysis().

◆ LoopScalarPreHeader

BasicBlock* llvm::InnerLoopVectorizer::LoopScalarPreHeader

protected

The scalar-loop preheader.

Definition at line 661 of file LoopVectorize.cpp.

Referenced by createVectorizedLoopSkeleton(), fixFirstOrderRecurrence(), fixReduction(), and updateAnalysis().

◆ LoopVectorBody

BasicBlock* llvm::InnerLoopVectorizer::LoopVectorBody

protected

The vector loop body.

Definition at line 670 of file LoopVectorize.cpp.

Referenced by createVectorizedLoopSkeleton(), fixFirstOrderRecurrence(), fixReduction(), fixVectorizedLoop(), updateAnalysis(), and widenPHIInstruction().

◆ LoopVectorPreHeader

BasicBlock* llvm::InnerLoopVectorizer::LoopVectorPreHeader

protected

The vector-loop preheader.

Definition at line 658 of file LoopVectorize.cpp.

Referenced by createVectorizedLoopSkeleton(), fixFirstOrderRecurrence(), fixReduction(), getBroadcastInstrs(), and widenIntOrFpInduction().

◆ LVer

std::unique_ptr<LoopVersioning> llvm::InnerLoopVectorizer::LVer

protected

LoopVersioning.

It's only set up (non-null) if memchecks were used.

This is currently only used to add no-alias metadata based on the memchecks. The actually versioning is performed manually.

Definition at line 642 of file LoopVectorize.cpp.

Referenced by addNewMetadata(), and emitMemRuntimeChecks().

◆ OldInduction

PHINode* llvm::InnerLoopVectorizer::OldInduction = nullptr

protected

The induction variable of the old basic block.

Definition at line 682 of file LoopVectorize.cpp.

Referenced by createVectorizedLoopSkeleton(), and widenIntOrFpInduction().

◆ ORE

OptimizationRemarkEmitter* llvm::InnerLoopVectorizer::ORE

protected

Interface to emit optimization remarks.

Definition at line 635 of file LoopVectorize.cpp.

Referenced by collectSupportedLoops(), llvm::LoopVectorizationCostModel::computeMaxVF(), createVectorizedLoopSkeleton(), llvm::LoopVectorizePass::processLoop(), llvm::LoopVectorizePass::run(), llvm::LoopVectorizePass::runImpl(), and llvm::LoopVectorizationCostModel::selectVectorizationFactor().

◆ OrigLoop

Loop* llvm::InnerLoopVectorizer::OrigLoop

protected

◆ OrigPHIsToFix

SmallVector<PHINode *, 8> llvm::InnerLoopVectorizer::OrigPHIsToFix

protected

Definition at line 714 of file LoopVectorize.cpp.

Referenced by fixNonInductionPHIs(), fixVectorizedLoop(), and widenPHIInstruction().

◆ PredicatedInstructions

SmallVector<Instruction *, 4> llvm::InnerLoopVectorizer::PredicatedInstructions

protected

Store instructions that were predicated.

Definition at line 691 of file LoopVectorize.cpp.

Referenced by fixVectorizedLoop(), and scalarizeInstruction().

◆ PSE

PredicatedScalarEvolution& llvm::InnerLoopVectorizer::PSE

protected

A wrapper around ScalarEvolution used to add runtime SCEV checks.

Applies dynamic knowledge to simplify SCEV expressions and converts them to a more usable form.

Definition at line 614 of file LoopVectorize.cpp.

Referenced by llvm::LoopVectorizationCostModel::computeMaxVF(), createVectorizedLoopSkeleton(), emitMemRuntimeChecks(), emitSCEVChecks(), fixupIVUsers(), getOrCreateTripCount(), isStrideMul(), llvm::LoopVectorizePass::processLoop(), llvm::LoopVectorizationCostModel::selectInterleaveCount(), llvm::LoopVectorizationCostModel::setCostBasedWideningDecision(), updateAnalysis(), widenInstruction(), widenIntOrFpInduction(), and widenPHIInstruction().

◆ TLI

const TargetLibraryInfo* llvm::InnerLoopVectorizer::TLI

protected

Target Library Info.

Definition at line 626 of file LoopVectorize.cpp.

Referenced by collectSupportedLoops(), llvm::LoopVectorizePass::processLoop(), llvm::LoopVectorizePass::run(), llvm::LoopVectorizePass::runImpl(), llvm::LoopVectorizationCostModel::setCostBasedWideningDecision(), llvm::VPRecipeBuilder::tryToCreateRecipe(), llvm::VPRecipeBuilder::tryToWiden(), and widenInstruction().

◆ TripCount

Value* llvm::InnerLoopVectorizer::TripCount = nullptr

protected

Trip count of the original loop.

Definition at line 694 of file LoopVectorize.cpp.

Referenced by getOrCreateTripCount().

◆ TTI

const TargetTransformInfo* llvm::InnerLoopVectorizer::TTI

protected

Target Transform Info.

Definition at line 629 of file LoopVectorize.cpp.

◆ UF

unsigned llvm::InnerLoopVectorizer::UF

protected

The vectorization unroll factor to use.

Each scalar is vectorized to this many different vector instructions.

Definition at line 650 of file LoopVectorize.cpp.

Referenced by buildScalarSteps(), createVectorizedLoopSkeleton(), emitMinimumIterationCountCheck(), fixFirstOrderRecurrence(), fixLCSSAPHIs(), fixReduction(), getOrCreateVectorTripCount(), llvm::LoopVectorizationPlanner::setBestPlan(), setDebugLocFromInst(), truncateToMinimalBitwidths(), vectorizeInterleaveGroup(), vectorizeMemoryInstruction(), widenInstruction(), widenIntOrFpInduction(), and widenPHIInstruction().

◆ VectorLoopValueMap

VectorizerValueMap llvm::InnerLoopVectorizer::VectorLoopValueMap

protected

Maps values from the original loop to their corresponding values in the vectorized loop.

A key value can map to either vector values, scalar values or both kinds of values, depending on whether the key was vectorized and scalarized.

Definition at line 688 of file LoopVectorize.cpp.

Referenced by buildScalarSteps(), llvm::LoopVectorizationPlanner::executePlan(), fixFirstOrderRecurrence(), fixNonInductionPHIs(), fixReduction(), getOrCreateScalarValue(), getOrCreateVectorValue(), packScalarIntoVectorValue(), recordVectorLoopValueForInductionCast(), scalarizeInstruction(), truncateToMinimalBitwidths(), vectorizeInterleaveGroup(), vectorizeMemoryInstruction(), widenInstruction(), widenIntOrFpInduction(), and widenPHIInstruction().

◆ VectorTripCount

Value* llvm::InnerLoopVectorizer::VectorTripCount = nullptr

protected

Trip count of the widened loop (TripCount - TripCount % (VF*UF))

Definition at line 697 of file LoopVectorize.cpp.

Referenced by getOrCreateVectorTripCount().

◆ VF

unsigned llvm::InnerLoopVectorizer::VF

protected

The vectorization SIMD factor to use.

Each vector will have this many vector elements.

Definition at line 646 of file LoopVectorize.cpp.

Referenced by buildScalarSteps(), llvm::LoopVectorizationPlanner::buildVPlans(), llvm::LoopVectorizationCostModel::calculateRegisterUsage(), llvm::LoopVectorizationCostModel::collectInstsToScalarize(), createBitOrPointerCast(), createVectorizedLoopSkeleton(), emitMinimumIterationCountCheck(), fixFirstOrderRecurrence(), fixLCSSAPHIs(), fixReduction(), fixVectorizedLoop(), getBroadcastInstrs(), getOrCreateScalarValue(), getOrCreateVectorTripCount(), getOrCreateVectorValue(), getScalarizationOverhead(), getVectorIntrinsicCost(), isStrideMul(), llvm::LoopVectorizationCostModel::memoryInstructionCanBeWidened(), reverseVector(), llvm::LoopVectorizationCostModel::selectUserVectorizationFactor(), llvm::LoopVectorizationPlanner::setBestPlan(), llvm::LoopVectorizationCostModel::setCostBasedWideningDecision(), setDebugLocFromInst(), shouldScalarizeInstruction(), llvm::VPRecipeBuilder::tryToCreateRecipe(), llvm::VPRecipeBuilder::tryToInterleaveMemory(), llvm::VPRecipeBuilder::tryToOptimizeInduction(), llvm::VPRecipeBuilder::tryToWiden(), llvm::VPRecipeBuilder::tryToWidenMemory(), updateAnalysis(), vectorizeInterleaveGroup(), vectorizeMemoryInstruction(), widenInstruction(), widenIntOrFpInduction(), and widenPHIInstruction().

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

lib/Transforms/Vectorize/LoopVectorize.cpp

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ PhiVector

◆ ScalarParts

◆ VectorParts

Constructor & Destructor Documentation

◆ InnerLoopVectorizer()

◆ ~InnerLoopVectorizer()

Member Function Documentation

◆ addMetadata() [1/2]

◆ addMetadata() [2/2]

◆ addNewMetadata()

◆ areSafetyChecksAdded()

◆ buildScalarSteps()

◆ createBitOrPointerCast()

◆ createInductionVariable()

◆ createVectorIntOrFpInductionPHI()

◆ createVectorizedLoopSkeleton()

◆ emitMemRuntimeChecks()

◆ emitMinimumIterationCountCheck()

◆ emitSCEVChecks()

◆ emitTransformedIndex()

◆ fixCrossIterationPHIs()

◆ fixFirstOrderRecurrence()

◆ fixLCSSAPHIs()

◆ fixNonInductionPHIs()

◆ fixReduction()

◆ fixupIVUsers()

◆ fixVectorizedLoop()

◆ getBroadcastInstrs()

◆ getOrCreateScalarValue()

◆ getOrCreateTripCount()

◆ getOrCreateVectorTripCount()

◆ getOrCreateVectorValue()

◆ getStepVector()

◆ needsScalarInduction()

◆ packScalarIntoVectorValue()

◆ recordVectorLoopValueForInductionCast()

◆ reverseVector()

◆ scalarizeInstruction()

◆ setDebugLocFromInst()

◆ shouldScalarizeInstruction()

◆ sinkScalarOperands()

◆ truncateToMinimalBitwidths()

◆ updateAnalysis()

◆ vectorizeInterleaveGroup()

◆ vectorizeMemoryInstruction()

◆ widenInstruction()

◆ widenIntOrFpInduction()

◆ widenPHIInstruction()

Friends And Related Function Documentation

◆ LoopVectorizationPlanner

Member Data Documentation

◆ AA

◆ AC

◆ AddedSafetyChecks

◆ Builder

◆ Cost

◆ DT

◆ Induction

◆ IVEndValues

◆ Legal

◆ LI

◆ LoopBypassBlocks

◆ LoopExitBlock

◆ LoopMiddleBlock

◆ LoopScalarBody

◆ LoopScalarPreHeader

◆ LoopVectorBody

◆ LoopVectorPreHeader

◆ LVer

◆ OldInduction

◆ ORE

◆ OrigLoop