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 Types
enum	RecurrenceKind { RK_NoRecurrence, RK_IntegerAdd, RK_IntegerMult, RK_IntegerOr, RK_IntegerAnd, RK_IntegerXor, RK_IntegerMinMax, RK_FloatAdd, RK_FloatMult, RK_FloatMinMax }
	This enum represents the kinds of recurrences that we support. More...

enum	MinMaxRecurrenceKind { MRK_Invalid, MRK_UIntMin, MRK_UIntMax, MRK_SIntMin, MRK_SIntMax, MRK_FloatMin, MRK_FloatMax }

Public Member Functions
	RecurrenceDescriptor ()=default

	RecurrenceDescriptor (Value Start, Instruction Exit, RecurrenceKind K, MinMaxRecurrenceKind MK, Instruction UAI, Type RT, bool Signed, SmallPtrSetImpl< Instruction *> &CI)

RecurrenceKind	getRecurrenceKind ()

MinMaxRecurrenceKind	getMinMaxRecurrenceKind ()

TrackingVH< Value >	getRecurrenceStartValue ()

Instruction *	getLoopExitInstr ()

bool	hasUnsafeAlgebra ()
	Returns true if the recurrence has unsafe algebra which requires a relaxed floating-point model. More...

Instruction *	getUnsafeAlgebraInst ()
	Returns first unsafe algebra instruction in the PHI node's use-chain. More...

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

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

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

Static Public Member Functions
static InstDesc	isRecurrenceInstr (Instruction *I, RecurrenceKind Kind, InstDesc &Prev, bool HasFunNoNaNAttr)
	Returns a struct describing if the instruction 'I' can be a recurrence variable of type 'Kind'. More...

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

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

static InstDesc	isMinMaxSelectCmpPattern (Instruction *I, InstDesc &Prev)
	Returns a struct describing if the instruction if the instruction is a Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y) or max(X, Y). More...

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

static Constant *	getRecurrenceIdentity (RecurrenceKind K, Type *Tp)
	Returns identity corresponding to the RecurrenceKind. More...

static unsigned	getRecurrenceBinOp (RecurrenceKind Kind)
	Returns the opcode of binary operation corresponding to the RecurrenceKind. More...

static bool	AddReductionVar (PHINode Phi, RecurrenceKind Kind, Loop TheLoop, bool HasFunNoNaNAttr, RecurrenceDescriptor &RedDes, DemandedBits DB=nullptr, AssumptionCache AC=nullptr, DominatorTree *DT=nullptr)
	Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor. More...

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

static bool	isFirstOrderRecurrence (PHINode Phi, Loop TheLoop, DenseMap< Instruction , Instruction > &SinkAfter, DominatorTree *DT)
	Returns true if Phi is a first-order recurrence. More...

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

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

static bool	isArithmeticRecurrenceKind (RecurrenceKind Kind)
	Returns true if the recurrence kind is an arithmetic kind. More...

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 63 of file IVDescriptors.h.

Member Enumeration Documentation

◆ MinMaxRecurrenceKind

enum llvm::RecurrenceDescriptor::MinMaxRecurrenceKind

Enumerator
MRK_Invalid
MRK_UIntMin
MRK_UIntMax
MRK_SIntMin
MRK_SIntMax
MRK_FloatMin
MRK_FloatMax

Definition at line 80 of file IVDescriptors.h.

◆ RecurrenceKind

enum llvm::RecurrenceDescriptor::RecurrenceKind

This enum represents the kinds of recurrences that we support.

Enumerator
RK_NoRecurrence	Not a recurrence.
RK_IntegerAdd	Sum of integers.
RK_IntegerMult	Product of integers.
RK_IntegerOr	Bitwise or logical OR of numbers.
RK_IntegerAnd	Bitwise or logical AND of numbers.
RK_IntegerXor	Bitwise or logical XOR of numbers.
RK_IntegerMinMax	Min/max implemented in terms of select(cmp()).
RK_FloatAdd	Sum of floats.
RK_FloatMult	Product of floats.
RK_FloatMinMax	Min/max implemented in terms of select(cmp()).

Definition at line 66 of file IVDescriptors.h.

Constructor & Destructor Documentation

◆ RecurrenceDescriptor() [1/2]

llvm::RecurrenceDescriptor::RecurrenceDescriptor ( )

default

◆ RecurrenceDescriptor() [2/2]

llvm::RecurrenceDescriptor::RecurrenceDescriptor	(	Value *	Start,
		Instruction *	Exit,
		RecurrenceKind	K,
		MinMaxRecurrenceKind	MK,
		Instruction *	UAI,
		Type *	RT,
		bool	Signed,
		SmallPtrSetImpl< Instruction *> &	CI
	)

inline

Definition at line 92 of file IVDescriptors.h.

Member Function Documentation

◆ AddReductionVar()

bool RecurrenceDescriptor::AddReductionVar	(	PHINode *	Phi,
		RecurrenceKind	Kind,
		Loop *	TheLoop,
		bool	HasFunNoNaNAttr,
		RecurrenceDescriptor &	RedDes,
		DemandedBits *	DB = `nullptr`,
		AssumptionCache *	AC = `nullptr`,
		DominatorTree *	DT = `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 191 of file IVDescriptors.cpp.

References llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), and llvm::Value::getType().

Referenced by llvm::RecurrenceDescriptor::InstDesc::getPatternInst(), and MatchReductions().

◆ 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 44 of file IVDescriptors.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), E, llvm::User::op_begin(), and llvm::User::op_end().

Referenced by llvm::RecurrenceDescriptor::InstDesc::getPatternInst().

◆ getCastInsts()

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

inline

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

Definition at line 228 of file IVDescriptors.h.

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

◆ getLoopExitInstr()

Instruction* llvm::RecurrenceDescriptor::getLoopExitInstr ( )

inline

Definition at line 204 of file IVDescriptors.h.

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

◆ getMinMaxRecurrenceKind()

MinMaxRecurrenceKind llvm::RecurrenceDescriptor::getMinMaxRecurrenceKind ( )

inline

Definition at line 200 of file IVDescriptors.h.

Referenced by llvm::createTargetReduction().

◆ getRecurrenceBinOp()

unsigned RecurrenceDescriptor::getRecurrenceBinOp ( RecurrenceKind Kind )

static

Returns the opcode of binary operation corresponding to the RecurrenceKind.

This function translates the recurrence kind to an LLVM binary operator.

Definition at line 746 of file IVDescriptors.cpp.

References llvm::MCID::Add, llvm::InductionDescriptor::InductionDescriptor(), and llvm_unreachable.

Referenced by llvm::InnerLoopVectorizer::fixReduction(), and llvm::RecurrenceDescriptor::InstDesc::getPatternInst().

◆ getRecurrenceIdentity()

Constant * RecurrenceDescriptor::getRecurrenceIdentity	(	RecurrenceKind	K,
		Type *	Tp
	)

static

Returns identity corresponding to the RecurrenceKind.

This function returns the identity element (or neutral element) for the operation K.

Definition at line 720 of file IVDescriptors.cpp.

References llvm::ConstantInt::get(), llvm::ConstantFP::get(), and llvm_unreachable.

Referenced by llvm::InnerLoopVectorizer::fixReduction(), and llvm::RecurrenceDescriptor::InstDesc::getPatternInst().

◆ getRecurrenceKind()

RecurrenceKind llvm::RecurrenceDescriptor::getRecurrenceKind ( )

inline

Definition at line 198 of file IVDescriptors.h.

Referenced by llvm::createTargetReduction(), and llvm::InnerLoopVectorizer::fixReduction().

◆ getRecurrenceStartValue()

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

inline

Definition at line 202 of file IVDescriptors.h.

◆ getRecurrenceType()

Type* llvm::RecurrenceDescriptor::getRecurrenceType ( )

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 224 of file IVDescriptors.h.

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

◆ getUnsafeAlgebraInst()

Instruction* llvm::RecurrenceDescriptor::getUnsafeAlgebraInst ( )

inline

Returns first unsafe algebra instruction in the PHI node's use-chain.

Definition at line 211 of file IVDescriptors.h.

References isArithmeticRecurrenceKind(), isFloatingPointRecurrenceKind(), and isIntegerRecurrenceKind().

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

◆ 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 592 of file IVDescriptors.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), E, llvm::User::op_begin(), and llvm::User::op_end().

Referenced by llvm::RecurrenceDescriptor::InstDesc::getPatternInst().

◆ hasUnsafeAlgebra()

bool llvm::RecurrenceDescriptor::hasUnsafeAlgebra ( )

inline

Returns true if the recurrence has unsafe algebra which requires a relaxed floating-point model.

Definition at line 208 of file IVDescriptors.h.

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

◆ isArithmeticRecurrenceKind()

bool RecurrenceDescriptor::isArithmeticRecurrenceKind ( RecurrenceKind Kind )

static

Returns true if the recurrence kind is an arithmetic kind.

Definition at line 71 of file IVDescriptors.cpp.

Referenced by getUnsafeAlgebraInst().

◆ isConditionalRdxPattern()

RecurrenceDescriptor::InstDesc RecurrenceDescriptor::isConditionalRdxPattern	(	RecurrenceKind	Kind,
		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 513 of file IVDescriptors.cpp.

References llvm::dyn_cast(), llvm::SelectInst::getCondition(), llvm::SelectInst::getFalseValue(), llvm::SelectInst::getTrueValue(), llvm::Value::hasOneUse(), I, llvm::Instruction::isBinaryOp(), llvm::Instruction::isFast(), llvm::PatternMatch::m_FAdd(), llvm::PatternMatch::m_FMul(), llvm::PatternMatch::m_FSub(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and SI.

Referenced by llvm::RecurrenceDescriptor::InstDesc::getPatternInst().

◆ isFirstOrderRecurrence()

bool RecurrenceDescriptor::isFirstOrderRecurrence	(	PHINode *	Phi,
		Loop *	TheLoop,
		DenseMap< Instruction , Instruction > &	SinkAfter,
		DominatorTree *	DT
	)

static

Returns true if Phi is a first-order recurrence.

A first-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 the previous iteration. SinkAfter includes pairs of instructions where the first will be rescheduled to appear after the second if/when the loop is vectorized. It may be augmented with additional pairs if needed in order to handle Phi as a first-order recurrence.

Definition at line 666 of file IVDescriptors.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::PHINode::getBasicBlockIndex(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::Value::hasOneUse(), I, llvm::Instruction::user_back(), and llvm::Value::users().

Referenced by llvm::RecurrenceDescriptor::InstDesc::getPatternInst(), and llvm::LoopVectorizationLegality::isUniform().

◆ isFloatingPointRecurrenceKind()

bool RecurrenceDescriptor::isFloatingPointRecurrenceKind ( RecurrenceKind Kind )

static

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

Definition at line 67 of file IVDescriptors.cpp.

Referenced by getUnsafeAlgebraInst().

◆ isIntegerRecurrenceKind()

bool RecurrenceDescriptor::isIntegerRecurrenceKind ( RecurrenceKind Kind )

static

Returns true if the recurrence kind is an integer kind.

Definition at line 52 of file IVDescriptors.cpp.

Referenced by getUnsafeAlgebraInst().

◆ isMinMaxSelectCmpPattern()

RecurrenceDescriptor::InstDesc RecurrenceDescriptor::isMinMaxSelectCmpPattern	(	Instruction *	I,
		InstDesc &	Prev
	)

static

Returns a struct describing if the instruction if the instruction is a Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y) or max(X, Y).

Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y) or max(X, Y).

Definition at line 455 of file IVDescriptors.cpp.

References assert(), llvm::dyn_cast(), llvm::RecurrenceDescriptor::InstDesc::getMinMaxKind(), llvm::User::getOperand(), llvm::Value::hasOneUse(), llvm::PatternMatch::m_OrdFMax(), llvm::PatternMatch::m_OrdFMin(), llvm::PatternMatch::m_SMax(), llvm::PatternMatch::m_SMin(), llvm::PatternMatch::m_UMax(), llvm::PatternMatch::m_UMin(), llvm::PatternMatch::m_UnordFMax(), llvm::PatternMatch::m_UnordFMin(), llvm::PatternMatch::m_Value(), llvm::MCID::Select, and llvm::Value::user_begin().

Referenced by llvm::RecurrenceDescriptor::InstDesc::getPatternInst().

◆ isRecurrenceInstr()

RecurrenceDescriptor::InstDesc RecurrenceDescriptor::isRecurrenceInstr	(	Instruction *	I,
		RecurrenceKind	Kind,
		InstDesc &	Prev,
		bool	HasFunNoNaNAttr
	)

static

Returns a struct describing if the instruction 'I' can be a recurrence variable of type 'Kind'.

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 551 of file IVDescriptors.cpp.

References llvm::MCID::Add, llvm::RecurrenceDescriptor::InstDesc::getMinMaxKind(), llvm::Instruction::getOpcode(), llvm::Value::getType(), llvm::RecurrenceDescriptor::InstDesc::getUnsafeAlgebraInst(), llvm::Instruction::isFast(), llvm::Type::isFloatingPointTy(), LLVM_FALLTHROUGH, and llvm::MCID::Select.

Referenced by llvm::RecurrenceDescriptor::InstDesc::getPatternInst().

◆ isReductionPHI()

bool RecurrenceDescriptor::isReductionPHI	(	PHINode *	Phi,
		Loop *	TheLoop,
		RecurrenceDescriptor &	RedDes,
		DemandedBits *	DB = `nullptr`,
		AssumptionCache *	AC = `nullptr`,
		DominatorTree *	DT = `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.

Definition at line 606 of file IVDescriptors.cpp.

References llvm::dbgs(), F(), llvm::Function::getFnAttribute(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::BasicBlock::getParent(), llvm::Attribute::getValueAsString(), and LLVM_DEBUG.

Referenced by findInnerReductionPhi(), llvm::RecurrenceDescriptor::InstDesc::getPatternInst(), and llvm::LoopVectorizationLegality::isUniform().

◆ isSigned()

bool llvm::RecurrenceDescriptor::isSigned ( )

inline

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

Definition at line 231 of file IVDescriptors.h.

References MRK_Invalid, and RK_NoRecurrence.

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

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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Enumeration Documentation

◆ MinMaxRecurrenceKind

◆ RecurrenceKind

Constructor & Destructor Documentation

◆ RecurrenceDescriptor() [1/2]

◆ RecurrenceDescriptor() [2/2]

Member Function Documentation

◆ AddReductionVar()

◆ areAllUsesIn()

◆ getCastInsts()

◆ getLoopExitInstr()

◆ getMinMaxRecurrenceKind()

◆ getRecurrenceBinOp()

◆ getRecurrenceIdentity()

◆ getRecurrenceKind()

◆ getRecurrenceStartValue()

◆ getRecurrenceType()

◆ getUnsafeAlgebraInst()

◆ hasMultipleUsesOf()

◆ hasUnsafeAlgebra()

◆ isArithmeticRecurrenceKind()

◆ isConditionalRdxPattern()

◆ isFirstOrderRecurrence()

◆ isFloatingPointRecurrenceKind()

◆ isIntegerRecurrenceKind()

◆ isMinMaxSelectCmpPattern()

◆ isRecurrenceInstr()

◆ isReductionPHI()

◆ isSigned()