The RecurrenceDescriptor is used to identify recurrences variables in a loop. More...

#include "llvm/Analysis/IVDescriptors.h"

Classes
class	InstDesc
	This POD struct holds information about a potential recurrence operation. More...

Public Member Functions
	RecurrenceDescriptor ()=default

	RecurrenceDescriptor (Value Start, Instruction Exit, StoreInst Store, RecurKind K, FastMathFlags FMF, Instruction ExactFP, Type RT, bool Signed, bool Ordered, SmallPtrSetImpl< Instruction > &CI, unsigned MinWidthCastToRecurTy)

RecurKind	getRecurrenceKind () const

unsigned	getOpcode () const

FastMathFlags	getFastMathFlags () const

TrackingVH< Value >	getRecurrenceStartValue () const

Instruction *	getLoopExitInstr () const

bool	hasExactFPMath () const
	Returns true if the recurrence has floating-point math that requires precise (ordered) operations.

Instruction *	getExactFPMathInst () const
	Returns 1st non-reassociative FP instruction in the PHI node's use-chain.

Type *	getRecurrenceType () const
	Returns the type of the recurrence.

Value *	getSentinelValue () const
	Returns the sentinel value for FindFirstIV & FindLastIV recurrences to replace the start value.

const SmallPtrSet< Instruction *, 8 > &	getCastInsts () const
	Returns a reference to the instructions used for type-promoting the recurrence.

unsigned	getMinWidthCastToRecurrenceTypeInBits () const
	Returns the minimum width used by the recurrence in bits.

bool	isSigned () const
	Returns true if all source operands of the recurrence are SExtInsts.

bool	isOrdered () const
	Expose an ordered FP reduction to the instance users.

LLVM_ABI SmallVector< Instruction *, 4 >	getReductionOpChain (PHINode Phi, Loop L) const
	Attempts to find a chain of operations from Phi to LoopExitInst that can be treated as a set of reductions instructions for in-loop reductions.

Static Public Member Functions
static LLVM_ABI InstDesc	isRecurrenceInstr (Loop L, PHINode Phi, Instruction I, RecurKind Kind, InstDesc &Prev, FastMathFlags FuncFMF, ScalarEvolution SE)
	Returns a struct describing if the instruction 'I' can be a recurrence variable of type 'Kind' for a Loop `L` and reduction PHI `Phi`.

static LLVM_ABI bool	hasMultipleUsesOf (Instruction I, SmallPtrSetImpl< Instruction > &Insts, unsigned MaxNumUses)
	Returns true if instruction I has multiple uses in Insts.

static LLVM_ABI bool	areAllUsesIn (Instruction I, SmallPtrSetImpl< Instruction > &Set)
	Returns true if all uses of the instruction I is within the Set.

static LLVM_ABI InstDesc	isMinMaxPattern (Instruction *I, RecurKind Kind, const InstDesc &Prev)
	Returns a struct describing if the instruction is a llvm.

static LLVM_ABI InstDesc	isAnyOfPattern (Loop Loop, PHINode OrigPhi, Instruction *I, InstDesc &Prev)
	Returns a struct describing whether the instruction is either a Select(ICmp(A, B), X, Y), or Select(FCmp(A, B), X, Y) where one of (X, Y) is a loop invariant integer and the other is a PHI value.

static LLVM_ABI InstDesc	isFindIVPattern (RecurKind Kind, Loop TheLoop, PHINode OrigPhi, Instruction *I, ScalarEvolution &SE)
	Returns a struct describing whether the instruction is either a Select(ICmp(A, B), X, Y), or Select(FCmp(A, B), X, Y) where one of (X, Y) is an increasing (FindLast) or decreasing (FindFirst) loop induction variable, and the other is a PHI value.

static LLVM_ABI InstDesc	isConditionalRdxPattern (Instruction *I)
	Returns a struct describing if the instruction is a Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.

static LLVM_ABI unsigned	getOpcode (RecurKind Kind)
	Returns the opcode corresponding to the RecurrenceKind.

static LLVM_ABI bool	AddReductionVar (PHINode Phi, RecurKind Kind, Loop TheLoop, FastMathFlags FuncFMF, RecurrenceDescriptor &RedDes, DemandedBits DB=nullptr, AssumptionCache AC=nullptr, DominatorTree DT=nullptr, ScalarEvolution SE=nullptr)
	Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor.

static LLVM_ABI bool	isReductionPHI (PHINode Phi, Loop TheLoop, RecurrenceDescriptor &RedDes, DemandedBits DB=nullptr, AssumptionCache AC=nullptr, DominatorTree DT=nullptr, ScalarEvolution SE=nullptr)
	Returns true if Phi is a reduction in TheLoop.

static LLVM_ABI bool	isFixedOrderRecurrence (PHINode Phi, Loop TheLoop, DominatorTree *DT)
	Returns true if Phi is a fixed-order recurrence.

static LLVM_ABI bool	isIntegerRecurrenceKind (RecurKind Kind)
	Returns true if the recurrence kind is an integer kind.

static LLVM_ABI bool	isFloatingPointRecurrenceKind (RecurKind Kind)
	Returns true if the recurrence kind is a floating point kind.

static bool	isIntMinMaxRecurrenceKind (RecurKind Kind)
	Returns true if the recurrence kind is an integer min/max kind.

static bool	isFPMinMaxRecurrenceKind (RecurKind Kind)
	Returns true if the recurrence kind is a floating-point min/max kind.

static bool	isMinMaxRecurrenceKind (RecurKind Kind)
	Returns true if the recurrence kind is any min/max kind.

static bool	isAnyOfRecurrenceKind (RecurKind Kind)
	Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,y) is loop invariant.

static bool	isFindFirstIVRecurrenceKind (RecurKind Kind)
	Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,y) is decreasing loop induction.

static bool	isFindLastIVRecurrenceKind (RecurKind Kind)
	Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,y) is increasing loop induction.

static bool	isSignedRecurrenceKind (RecurKind Kind)
	Returns true if recurrece kind is a signed redux kind.

static bool	isFindIVRecurrenceKind (RecurKind Kind)
	Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,y) is an increasing or decreasing loop induction.

static bool	isFMulAddIntrinsic (Instruction *I)
	Returns true if the instruction is a call to the llvm.fmuladd intrinsic.

Public Attributes
StoreInst *	IntermediateStore = nullptr
	Reductions may store temporary or final result to an invariant address.

Detailed Description

The RecurrenceDescriptor is used to identify recurrences variables in a loop.

Reduction is a special case of recurrence that has uses of the recurrence variable outside the loop. The method isReductionPHI identifies reductions that are basic recurrences.

Basic recurrences are defined as the summation, product, OR, AND, XOR, min, or max of a set of terms. For example: for(i=0; i<n; i++) { total += array[i]; } is a summation of array elements. Basic recurrences are a special case of chains of recurrences (CR). See ScalarEvolution for CR references. This struct holds information about recurrence variables.

Definition at line 90 of file IVDescriptors.h.

Constructor & Destructor Documentation

◆ RecurrenceDescriptor() [1/2]

llvm::RecurrenceDescriptor::RecurrenceDescriptor ( )

default

◆ RecurrenceDescriptor() [2/2]

llvm::RecurrenceDescriptor::RecurrenceDescriptor	(	Value *	Start,
		Instruction *	Exit,
		StoreInst *	Store,
		RecurKind	K,
		FastMathFlags	FMF,
		Instruction *	ExactFP,
		Type *	RT,
		bool	Signed,
		bool	Ordered,
		SmallPtrSetImpl< Instruction * > &	CI,
		unsigned	MinWidthCastToRecurTy
	)

inline

Definition at line 94 of file IVDescriptors.h.

Member Function Documentation

◆ AddReductionVar()

bool RecurrenceDescriptor::AddReductionVar	(	PHINode *	Phi,
		RecurKind	Kind,
		Loop *	TheLoop,
		FastMathFlags	FuncFMF,
		RecurrenceDescriptor &	RedDes,
		DemandedBits *	DB = `nullptr`,
		AssumptionCache *	AC = `nullptr`,
		DominatorTree *	DT = `nullptr`,
		ScalarEvolution *	SE = `nullptr`
	)

static

Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor.

If either DB is non-null or AC and DT are non-null, the minimal bit width needed to compute the reduction will be computed.

Definition at line 217 of file IVDescriptors.cpp.

References llvm::SmallVectorImpl< T >::append(), areAllUsesIn(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), checkOrderedReduction(), collectCastInstrs(), computeRecurrenceType(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::FAdd, llvm::FMul, llvm::RecurrenceDescriptor::InstDesc::getExactFPMathInst(), llvm::FastMathFlags::getFast(), llvm::Instruction::getFastMathFlags(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::User::getOperand(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::RecurrenceDescriptor::InstDesc::getPatternInst(), llvm::StoreInst::getPointerOperand(), llvm::RecurrenceDescriptor::InstDesc::getRecKind(), llvm::ScalarEvolution::getSCEV(), llvm::StoreInst::getValueOperand(), hasMultipleUsesOf(), llvm::SmallPtrSetImpl< PtrType >::insert(), IntermediateStore, llvm::is_contained(), isAnyOfPattern(), isAnyOfRecurrenceKind(), llvm::Instruction::isCommutative(), isConditionalRdxPattern(), isFloatingPointRecurrenceKind(), llvm::Type::isFloatingPointTy(), isFMulAddIntrinsic(), isFPMinMaxRecurrenceKind(), isIntegerRecurrenceKind(), llvm::Type::isIntegerTy(), isIntMinMaxRecurrenceKind(), llvm::ScalarEvolution::isLoopInvariant(), isMinMaxPattern(), isMinMaxRecurrenceKind(), llvm::RecurrenceDescriptor::InstDesc::isRecurrence(), isRecurrenceInstr(), LLVM_DEBUG, lookThroughAnd(), llvm::None, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Value::use_empty(), and llvm::Value::users().

Referenced by isReductionPHI().

◆ areAllUsesIn()

bool RecurrenceDescriptor::areAllUsesIn	(	Instruction *	I,
		SmallPtrSetImpl< Instruction * > &	Set
	)

static

Returns true if all uses of the instruction I is within the Set.

Definition at line 31 of file IVDescriptors.cpp.

References I.

Referenced by AddReductionVar().

◆ getCastInsts()

const SmallPtrSet< Instruction *, 8 > & llvm::RecurrenceDescriptor::getCastInsts ( ) const

inline

Returns a reference to the instructions used for type-promoting the recurrence.

Definition at line 323 of file IVDescriptors.h.

Referenced by llvm::LoopVectorizationCostModel::collectValuesToIgnore().

◆ getExactFPMathInst()

Instruction * llvm::RecurrenceDescriptor::getExactFPMathInst ( ) const

inline

Returns 1st non-reassociative FP instruction in the PHI node's use-chain.

Definition at line 240 of file IVDescriptors.h.

Referenced by findInnerReductionPhi().

◆ getFastMathFlags()

FastMathFlags llvm::RecurrenceDescriptor::getFastMathFlags ( ) const

inline

Definition at line 229 of file IVDescriptors.h.

Referenced by llvm::LoopVectorizationCostModel::getReductionPatternCost().

◆ getLoopExitInstr()

Instruction * llvm::RecurrenceDescriptor::getLoopExitInstr ( ) const

inline

Definition at line 233 of file IVDescriptors.h.

Referenced by llvm::VPRecipeBuilder::tryToCreateWidenRecipe().

◆ getMinWidthCastToRecurrenceTypeInBits()

unsigned llvm::RecurrenceDescriptor::getMinWidthCastToRecurrenceTypeInBits ( ) const

inline

Returns the minimum width used by the recurrence in bits.

Definition at line 326 of file IVDescriptors.h.

Referenced by llvm::LoopVectorizationCostModel::getSmallestAndWidestTypes().

◆ getOpcode() [1/2]

unsigned llvm::RecurrenceDescriptor::getOpcode ( ) const

inline

Definition at line 227 of file IVDescriptors.h.

References getOpcode(), and getRecurrenceKind().

Referenced by llvm::VPReductionRecipe::computeCost(), llvm::VPExpressionRecipe::computeCost(), llvm::VPReductionRecipe::execute(), llvm::VPReductionEVLRecipe::execute(), findInnerReductionPhi(), getOpcode(), getReductionOpChain(), llvm::VPReductionRecipe::print(), llvm::VPReductionEVLRecipe::print(), llvm::VPExpressionRecipe::print(), tryToMatchAndCreateExtendedReduction(), and tryToMatchAndCreateMulAccumulateReduction().

◆ getOpcode() [2/2]

unsigned RecurrenceDescriptor::getOpcode ( RecurKind Kind )

static

Returns the opcode corresponding to the RecurrenceKind.

Definition at line 1219 of file IVDescriptors.cpp.

References llvm::Add, llvm::AddChainWithSubs, llvm::And, llvm::AnyOf, llvm::FAdd, llvm::FindFirstIVSMin, llvm::FindFirstIVUMin, llvm::FindLastIVSMax, llvm::FindLastIVUMax, llvm::FMax, llvm::FMaximum, llvm::FMaximumNum, llvm::FMin, llvm::FMinimum, llvm::FMinimumNum, llvm::FMul, llvm::FMulAdd, llvm_unreachable, llvm::Mul, llvm::Or, llvm::SMax, llvm::SMin, llvm::Sub, llvm::UMax, llvm::UMin, and llvm::Xor.

Referenced by llvm::LoopVectorizationCostModel::getReductionPatternCost().

◆ getRecurrenceKind()

RecurKind llvm::RecurrenceDescriptor::getRecurrenceKind ( ) const

inline

Definition at line 225 of file IVDescriptors.h.

Referenced by llvm::LoopVectorizationCostModel::collectElementTypesForWidening(), llvm::LoopVectorizationCostModel::collectInLoopReductions(), findInnerReductionPhi(), getOpcode(), llvm::LoopVectorizationCostModel::getReductionPatternCost(), llvm::AArch64TTIImpl::isLegalToVectorizeReduction(), llvm::RISCVTTIImpl::isLegalToVectorizeReduction(), and llvm::VPRecipeBuilder::tryToCreateWidenRecipe().

◆ getRecurrenceStartValue()

TrackingVH< Value > llvm::RecurrenceDescriptor::getRecurrenceStartValue ( ) const

inline

Definition at line 231 of file IVDescriptors.h.

Referenced by llvm::VPRecipeBuilder::tryToCreateWidenRecipe().

◆ getRecurrenceType()

Type * llvm::RecurrenceDescriptor::getRecurrenceType ( ) const

inline

Returns the type of the recurrence.

This type can be narrower than the actual type of the Phi if the recurrence has been type-promoted.

Definition at line 304 of file IVDescriptors.h.

Referenced by llvm::LoopVectorizationCostModel::collectElementTypesForWidening(), llvm::LoopVectorizationCostModel::collectInLoopReductions(), llvm::LoopVectorizationCostModel::getReductionPatternCost(), llvm::LoopVectorizationCostModel::getSmallestAndWidestTypes(), llvm::AArch64TTIImpl::isLegalToVectorizeReduction(), and llvm::RISCVTTIImpl::isLegalToVectorizeReduction().

◆ getReductionOpChain()

SmallVector< Instruction *, 4 > RecurrenceDescriptor::getReductionOpChain	(	PHINode *	Phi,
		Loop *	L
	)		const

Attempts to find a chain of operations from Phi to LoopExitInst that can be treated as a set of reductions instructions for in-loop reductions.

Definition at line 1262 of file IVDescriptors.cpp.

References llvm::AddChainWithSubs, getOpcode(), llvm::Value::hasNUses(), isFMulAddIntrinsic(), isMinMaxRecurrenceKind(), llvm::SelectPatternResult::isMinOrMax(), LHS, llvm::matchSelectPattern(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), RHS, and llvm::Value::users().

Referenced by llvm::LoopVectorizationCostModel::collectInLoopReductions(), and findInnerReductionPhi().

◆ getSentinelValue()

Value * llvm::RecurrenceDescriptor::getSentinelValue ( ) const

inline

Returns the sentinel value for FindFirstIV & FindLastIV recurrences to replace the start value.

Definition at line 308 of file IVDescriptors.h.

References llvm::Type::getIntegerBitWidth(), llvm::APInt::getMaxValue(), llvm::APInt::getMinValue(), llvm::APInt::getSignedMaxValue(), llvm::APInt::getSignedMinValue(), llvm::Value::getType(), isFindLastIVRecurrenceKind(), and isSignedRecurrenceKind().

◆ hasExactFPMath()

bool llvm::RecurrenceDescriptor::hasExactFPMath ( ) const

inline

Returns true if the recurrence has floating-point math that requires precise (ordered) operations.

Definition at line 237 of file IVDescriptors.h.

Referenced by llvm::LoopVectorizationLegality::canVectorizeFPMath().

◆ hasMultipleUsesOf()

bool RecurrenceDescriptor::hasMultipleUsesOf	(	Instruction *	I,
		SmallPtrSetImpl< Instruction * > &	Insts,
		unsigned	MaxNumUses
	)

static

Returns true if instruction I has multiple uses in Insts.

Definition at line 980 of file IVDescriptors.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), and I.

Referenced by AddReductionVar().

◆ isAnyOfPattern()

RecurrenceDescriptor::InstDesc RecurrenceDescriptor::isAnyOfPattern	(	Loop *	Loop,
		PHINode *	OrigPhi,
		Instruction *	I,
		InstDesc &	Prev
	)

static

Returns a struct describing whether the instruction is either a Select(ICmp(A, B), X, Y), or Select(FCmp(A, B), X, Y) where one of (X, Y) is a loop invariant integer and the other is a PHI value.

Prev specifies the description of an already processed select instruction, so its corresponding cmp can be matched to it.

Definition at line 632 of file IVDescriptors.cpp.

References llvm::AnyOf, llvm::RecurrenceDescriptor::InstDesc::getRecKind(), I, llvm::Loop::isLoopInvariant(), llvm::PatternMatch::m_Cmp(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and Select.

Referenced by AddReductionVar(), and isRecurrenceInstr().

◆ isAnyOfRecurrenceKind()

static bool llvm::RecurrenceDescriptor::isAnyOfRecurrenceKind ( RecurKind Kind )

inlinestatic

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,y) is loop invariant.

Definition at line 269 of file IVDescriptors.h.

References llvm::AnyOf.

Referenced by AddReductionVar(), llvm::VPReductionRecipe::computeCost(), llvm::createSimpleReduction(), llvm::VPReductionRecipe::execute(), fixReductionScalarResumeWhenVectorizingEpilog(), llvm::LoopVectorizationCostModel::getInstructionCost(), isRecurrenceInstr(), and preparePlanForEpilogueVectorLoop().

◆ isConditionalRdxPattern()

RecurrenceDescriptor::InstDesc RecurrenceDescriptor::isConditionalRdxPattern ( Instruction * I )

static

Returns a struct describing if the instruction is a Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern.

Returns true if the select instruction has users in the compare-and-add reduction pattern below.

The select instruction argument is the last one in the sequence.

sum.1 = phi ... ... cmp = fcmp pred %0, CFP add = fadd %0, sum.1 sum.2 = select cmp, add, sum.1

Definition at line 851 of file IVDescriptors.cpp.

References llvm::Value::hasOneUse(), I, llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_FAdd(), llvm::PatternMatch::m_FMul(), llvm::PatternMatch::m_FSub(), llvm::PatternMatch::m_Mul(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

Referenced by AddReductionVar(), and isRecurrenceInstr().

◆ isFindFirstIVRecurrenceKind()

static bool llvm::RecurrenceDescriptor::isFindFirstIVRecurrenceKind ( RecurKind Kind )

inlinestatic

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,y) is decreasing loop induction.

Definition at line 275 of file IVDescriptors.h.

References llvm::FindFirstIVSMin, and llvm::FindFirstIVUMin.

Referenced by isFindIVPattern(), and isFindIVRecurrenceKind().

◆ isFindIVPattern()

RecurrenceDescriptor::InstDesc RecurrenceDescriptor::isFindIVPattern	(	RecurKind	Kind,
		Loop *	TheLoop,
		PHINode *	OrigPhi,
		Instruction *	I,
		ScalarEvolution &	SE
	)

static

Returns a struct describing whether the instruction is either a Select(ICmp(A, B), X, Y), or Select(FCmp(A, B), X, Y) where one of (X, Y) is an increasing (FindLast) or decreasing (FindFirst) loop induction variable, and the other is a PHI value.

Definition at line 694 of file IVDescriptors.cpp.

References assert(), llvm::ConstantRange::contains(), llvm::dbgs(), llvm::FindFirstIVSMin, llvm::FindFirstIVUMin, llvm::FindLastIVSMax, llvm::FindLastIVUMax, llvm::Type::getIntegerBitWidth(), llvm::APInt::getMaxValue(), llvm::APInt::getMinValue(), llvm::ConstantRange::getNonEmpty(), llvm::ScalarEvolution::getSCEV(), llvm::APInt::getSignedMaxValue(), llvm::APInt::getSignedMinValue(), llvm::ScalarEvolution::getSignedRange(), llvm::ScalarEvolution::getUnsignedRange(), llvm::Value::hasOneUse(), I, isFindFirstIVRecurrenceKind(), isFindLastIVRecurrenceKind(), llvm::ScalarEvolution::isKnownNegative(), llvm::ScalarEvolution::isKnownPositive(), llvm::ScalarEvolution::isSCEVable(), LLVM_DEBUG, llvm::PatternMatch::m_Cmp(), llvm::PatternMatch::m_CombineOr(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and llvm::Sentinel.

Referenced by isRecurrenceInstr().

◆ isFindIVRecurrenceKind()

static bool llvm::RecurrenceDescriptor::isFindIVRecurrenceKind ( RecurKind Kind )

inlinestatic

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,y) is an increasing or decreasing loop induction.

Definition at line 297 of file IVDescriptors.h.

References isFindFirstIVRecurrenceKind(), and isFindLastIVRecurrenceKind().

Referenced by llvm::createSimpleReduction(), fixReductionScalarResumeWhenVectorizingEpilog(), isRecurrenceInstr(), and preparePlanForEpilogueVectorLoop().

◆ isFindLastIVRecurrenceKind()

static bool llvm::RecurrenceDescriptor::isFindLastIVRecurrenceKind ( RecurKind Kind )

inlinestatic

Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,y) is increasing loop induction.

Definition at line 282 of file IVDescriptors.h.

References llvm::FindLastIVSMax, and llvm::FindLastIVUMax.

Referenced by llvm::createFindLastIVReduction(), getSentinelValue(), isFindIVPattern(), and isFindIVRecurrenceKind().

◆ isFixedOrderRecurrence()

bool RecurrenceDescriptor::isFixedOrderRecurrence	(	PHINode *	Phi,
		Loop *	TheLoop,
		DominatorTree *	DT
	)

static

Returns true if Phi is a fixed-order recurrence.

A fixed-order recurrence is a non-reduction recurrence relation in which the value of the recurrence in the current loop iteration equals a value defined in a previous iteration (e.g. if the value is defined in the previous iteration, we refer to it as first-order recurrence, if it is defined in the iteration before the previous, we refer to it as second-order recurrence and so on). Note that this function optimistically assumes that uses of the recurrence can be re-ordered if necessary and users need to check and perform the re-ordering.

Definition at line 1131 of file IVDescriptors.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DominatorTree::dominates(), llvm::SmallVectorBase< Size_T >::empty(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::Value::users().

◆ isFloatingPointRecurrenceKind()

bool RecurrenceDescriptor::isFloatingPointRecurrenceKind ( RecurKind Kind )

static

Returns true if the recurrence kind is a floating point kind.

Definition at line 64 of file IVDescriptors.cpp.

References isIntegerRecurrenceKind(), and llvm::None.

Referenced by AddReductionVar().

◆ isFMulAddIntrinsic()

static bool llvm::RecurrenceDescriptor::isFMulAddIntrinsic ( Instruction * I )

inlinestatic

Returns true if the instruction is a call to the llvm.fmuladd intrinsic.

Definition at line 342 of file IVDescriptors.h.

References I.

Referenced by AddReductionVar(), checkOrderedReduction(), getReductionOpChain(), llvm::LoopVectorizationCostModel::getVectorCallCost(), isRecurrenceInstr(), and llvm::LoopVectorizationCostModel::setVectorizedCallDecision().

◆ isFPMinMaxRecurrenceKind()

static bool llvm::RecurrenceDescriptor::isFPMinMaxRecurrenceKind ( RecurKind Kind )

inlinestatic

Returns true if the recurrence kind is a floating-point min/max kind.

Definition at line 255 of file IVDescriptors.h.

References llvm::FMax, llvm::FMaximum, llvm::FMaximumNum, llvm::FMaxNum, llvm::FMin, llvm::FMinimum, llvm::FMinimumNum, and llvm::FMinNum.

Referenced by AddReductionVar(), isMinMaxRecurrenceKind(), and isRecurrenceInstr().

◆ isIntegerRecurrenceKind()

bool RecurrenceDescriptor::isIntegerRecurrenceKind ( RecurKind Kind )

static

Returns true if the recurrence kind is an integer kind.

Definition at line 39 of file IVDescriptors.cpp.

References llvm::Add, llvm::AddChainWithSubs, llvm::And, llvm::AnyOf, llvm::FindFirstIVSMin, llvm::FindFirstIVUMin, llvm::FindLastIVSMax, llvm::FindLastIVUMax, llvm::Mul, llvm::Or, llvm::SMax, llvm::SMin, llvm::Sub, llvm::UMax, llvm::UMin, and llvm::Xor.

Referenced by AddReductionVar(), and isFloatingPointRecurrenceKind().

◆ isIntMinMaxRecurrenceKind()

static bool llvm::RecurrenceDescriptor::isIntMinMaxRecurrenceKind ( RecurKind Kind )

inlinestatic

Returns true if the recurrence kind is an integer min/max kind.

Definition at line 249 of file IVDescriptors.h.

References llvm::SMax, llvm::SMin, llvm::UMax, and llvm::UMin.

Referenced by AddReductionVar(), isMinMaxRecurrenceKind(), and isRecurrenceInstr().

◆ isMinMaxPattern()

RecurrenceDescriptor::InstDesc RecurrenceDescriptor::isMinMaxPattern	(	Instruction *	I,
		RecurKind	Kind,
		const InstDesc &	Prev
	)

static

Returns a struct describing if the instruction is a llvm.

(s/u)(min/max), llvm.minnum/maxnum or a Select(ICmp(X, Y), X, Y) pair of instructions corresponding to a min(X, Y) or max(X, Y), matching the recurrence kind Kind. Prev specifies the description of an already processed select instruction, so its corresponding cmp can be matched to it.

Definition at line 793 of file IVDescriptors.cpp.

Referenced by AddReductionVar(), and isRecurrenceInstr().

◆ isMinMaxRecurrenceKind()

static bool llvm::RecurrenceDescriptor::isMinMaxRecurrenceKind ( RecurKind Kind )

inlinestatic

Returns true if the recurrence kind is any min/max kind.

Definition at line 263 of file IVDescriptors.h.

References isFPMinMaxRecurrenceKind(), and isIntMinMaxRecurrenceKind().

Referenced by AddReductionVar(), llvm::VPReductionRecipe::computeCost(), llvm::VPReductionRecipe::execute(), llvm::VPReductionEVLRecipe::execute(), llvm::getOrderedReduction(), getReductionOpChain(), llvm::LoopVectorizationCostModel::getReductionPatternCost(), llvm::getShuffleReduction(), and isMinMaxPattern().

◆ isOrdered()

bool llvm::RecurrenceDescriptor::isOrdered ( ) const

inline

Expose an ordered FP reduction to the instance users.

Definition at line 334 of file IVDescriptors.h.

Referenced by llvm::LoopVectorizationLegality::canVectorizeFPMath(), and llvm::LoopVectorizationCostModel::useOrderedReductions().

◆ isRecurrenceInstr()

RecurrenceDescriptor::InstDesc RecurrenceDescriptor::isRecurrenceInstr	(	Loop *	L,
		PHINode *	Phi,
		Instruction *	I,
		RecurKind	Kind,
		InstDesc &	Prev,
		FastMathFlags	FuncFMF,
		ScalarEvolution *	SE
	)

static

Returns a struct describing if the instruction 'I' can be a recurrence variable of type 'Kind' for a Loop L and reduction PHI Phi.

If the recurrence is a min/max pattern of select(icmp()) this function advances the instruction pointer 'I' from the compare instruction to the select instruction and stores this pointer in 'PatternLastInst' member of the returned struct.

Definition at line 892 of file IVDescriptors.cpp.

References llvm::Add, llvm::AddChainWithSubs, llvm::And, assert(), llvm::FAdd, llvm::FMax, llvm::FMaxNum, llvm::FMin, llvm::FMinNum, llvm::FMul, llvm::FMulAdd, llvm::RecurrenceDescriptor::InstDesc::getExactFPMathInst(), llvm::RecurrenceDescriptor::InstDesc::getRecKind(), I, isAnyOfPattern(), isAnyOfRecurrenceKind(), isConditionalRdxPattern(), isFindIVPattern(), isFindIVRecurrenceKind(), isFMulAddIntrinsic(), isFPMinMaxRecurrenceKind(), isIntMinMaxRecurrenceKind(), isMinMaxPattern(), llvm::RecurrenceDescriptor::InstDesc::isRecurrence(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::Mul, llvm::FastMathFlags::noNaNs(), llvm::None, llvm::FastMathFlags::noSignedZeros(), llvm::Or, llvm::Sub, and llvm::Xor.

Referenced by AddReductionVar().

◆ isReductionPHI()

bool RecurrenceDescriptor::isReductionPHI	(	PHINode *	Phi,
		Loop *	TheLoop,
		RecurrenceDescriptor &	RedDes,
		DemandedBits *	DB = `nullptr`,
		AssumptionCache *	AC = `nullptr`,
		DominatorTree *	DT = `nullptr`,
		ScalarEvolution *	SE = `nullptr`
	)

static

Returns true if Phi is a reduction in TheLoop.

The RecurrenceDescriptor is returned in RedDes. If either DB is non-null or AC and DT are non-null, the minimal bit width needed to compute the reduction will be computed. If SE is non-null, store instructions to loop invariant addresses are processed.

Definition at line 994 of file IVDescriptors.cpp.

References llvm::Add, llvm::AddChainWithSubs, AddReductionVar(), llvm::And, llvm::AnyOf, llvm::dbgs(), F, llvm::FAdd, llvm::FindFirstIVSMin, llvm::FindLastIVSMax, llvm::FMax, llvm::FMaximum, llvm::FMaximumNum, llvm::FMin, llvm::FMinimum, llvm::FMinimumNum, llvm::FMul, llvm::FMulAdd, llvm::LoopBase< BlockT, LoopT >::getHeader(), LLVM_DEBUG, llvm::Mul, llvm::Or, llvm::FastMathFlags::setNoNaNs(), llvm::FastMathFlags::setNoSignedZeros(), llvm::SMax, llvm::SMin, llvm::Sub, llvm::UMax, llvm::UMin, and llvm::Xor.

Referenced by findInnerReductionPhi().

◆ isSigned()

bool llvm::RecurrenceDescriptor::isSigned ( ) const

inline

Returns true if all source operands of the recurrence are SExtInsts.

Definition at line 331 of file IVDescriptors.h.

◆ isSignedRecurrenceKind()

static bool llvm::RecurrenceDescriptor::isSignedRecurrenceKind ( RecurKind Kind )

inlinestatic

Returns true if recurrece kind is a signed redux kind.

Definition at line 288 of file IVDescriptors.h.

References llvm::FindFirstIVSMin, llvm::FindLastIVSMax, llvm::SMax, and llvm::SMin.

Referenced by llvm::createFindLastIVReduction(), and getSentinelValue().

Member Data Documentation

◆ IntermediateStore

StoreInst* llvm::RecurrenceDescriptor::IntermediateStore = nullptr

Reductions may store temporary or final result to an invariant address.

If there is such a store in the loop then, after successfull run of AddReductionVar method, this field will be assigned the last met store.

Definition at line 350 of file IVDescriptors.h.

Referenced by AddReductionVar(), llvm::LoopVectorizationLegality::isInvariantAddressOfReduction(), and llvm::LoopVectorizationLegality::isInvariantStoreOfReduction().

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

include/llvm/Analysis/IVDescriptors.h
lib/Analysis/IVDescriptors.cpp

Classes

Public Member Functions

Static Public Member Functions

Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ RecurrenceDescriptor() [1/2]

◆ RecurrenceDescriptor() [2/2]

Member Function Documentation

◆ AddReductionVar()

◆ areAllUsesIn()

◆ getCastInsts()

◆ getExactFPMathInst()

◆ getFastMathFlags()

◆ getLoopExitInstr()

◆ getMinWidthCastToRecurrenceTypeInBits()

◆ getOpcode() [1/2]

◆ getOpcode() [2/2]

◆ getRecurrenceKind()

◆ getRecurrenceStartValue()

◆ getRecurrenceType()

◆ getReductionOpChain()

◆ getSentinelValue()

◆ hasExactFPMath()

◆ hasMultipleUsesOf()

◆ isAnyOfPattern()

◆ isAnyOfRecurrenceKind()

◆ isConditionalRdxPattern()

◆ isFindFirstIVRecurrenceKind()

◆ isFindIVPattern()

◆ isFindIVRecurrenceKind()

◆ isFindLastIVRecurrenceKind()

◆ isFixedOrderRecurrence()

◆ isFloatingPointRecurrenceKind()

◆ isFMulAddIntrinsic()

◆ isFPMinMaxRecurrenceKind()

◆ isIntegerRecurrenceKind()

◆ isIntMinMaxRecurrenceKind()

◆ isMinMaxPattern()

◆ isMinMaxRecurrenceKind()

◆ isOrdered()

◆ isRecurrenceInstr()

◆ isReductionPHI()

◆ isSigned()

◆ isSignedRecurrenceKind()

Member Data Documentation

◆ IntermediateStore