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

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

#include "llvm/Transforms/Utils/LoopUtils.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< ValuegetRecurrenceStartValue ()
 
InstructiongetLoopExitInstr ()
 
bool hasUnsafeAlgebra ()
 Returns true if the recurrence has unsafe algebra which requires a relaxed floating-point model. More...
 
InstructiongetUnsafeAlgebraInst ()
 Returns first unsafe algebra instruction in the PHI node's use-chain. More...
 
TypegetRecurrenceType ()
 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)
 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 ConstantgetRecurrenceIdentity (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 ValuecreateMinMaxOp (IRBuilder<> &Builder, MinMaxRecurrenceKind RK, Value *Left, Value *Right)
 Returns a Min/Max operation corresponding to MinMaxRecurrenceKind. More...
 
static bool AddReductionVar (PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop, bool HasFunNoNaNAttr, RecurrenceDescriptor &RedDes)
 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)
 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...
 
static InstructionlookThroughAnd (PHINode *Phi, Type *&RT, SmallPtrSetImpl< Instruction *> &Visited, SmallPtrSetImpl< Instruction *> &CI)
 Determines if Phi may have been type-promoted. More...
 
static bool getSourceExtensionKind (Instruction *Start, Instruction *Exit, Type *RT, bool &IsSigned, SmallPtrSetImpl< Instruction *> &Visited, SmallPtrSetImpl< Instruction *> &CI)
 Returns true if all the source operands of a recurrence are either SExtInsts or ZExtInsts. 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 73 of file LoopUtils.h.

Member Enumeration Documentation

◆ MinMaxRecurrenceKind

Enumerator
MRK_Invalid 
MRK_UIntMin 
MRK_UIntMax 
MRK_SIntMin 
MRK_SIntMax 
MRK_FloatMin 
MRK_FloatMax 

Definition at line 90 of file LoopUtils.h.

◆ 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 76 of file LoopUtils.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

Member Function Documentation

◆ AddReductionVar()

bool RecurrenceDescriptor::AddReductionVar ( PHINode Phi,
RecurrenceKind  Kind,
Loop TheLoop,
bool  HasFunNoNaNAttr,
RecurrenceDescriptor RedDes 
)
static

◆ 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 40 of file LoopUtils.cpp.

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

◆ createMinMaxOp()

Value * RecurrenceDescriptor::createMinMaxOp ( IRBuilder<> &  Builder,
MinMaxRecurrenceKind  RK,
Value Left,
Value Right 
)
static

◆ getCastInsts()

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

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

Definition at line 245 of file LoopUtils.h.

Referenced by llvm::createLoopVectorizePass().

◆ getLoopExitInstr()

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

Definition at line 203 of file LoopUtils.h.

Referenced by hasOutsideLoopUser().

◆ getMinMaxRecurrenceKind()

MinMaxRecurrenceKind llvm::RecurrenceDescriptor::getMinMaxRecurrenceKind ( )
inline

Definition at line 199 of file LoopUtils.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 611 of file LoopUtils.cpp.

References llvm::MCID::Add, and llvm_unreachable.

Referenced by llvm::InnerLoopVectorizer::fixReduction().

◆ 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 585 of file LoopUtils.cpp.

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

Referenced by llvm::InnerLoopVectorizer::fixReduction().

◆ getRecurrenceKind()

RecurrenceKind llvm::RecurrenceDescriptor::getRecurrenceKind ( )
inline

Definition at line 197 of file LoopUtils.h.

References Kind.

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

◆ getRecurrenceStartValue()

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

Definition at line 201 of file LoopUtils.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 241 of file LoopUtils.h.

Referenced by hasOutsideLoopUser().

◆ getSourceExtensionKind()

bool RecurrenceDescriptor::getSourceExtensionKind ( Instruction Start,
Instruction Exit,
Type RT,
bool IsSigned,
SmallPtrSetImpl< Instruction *> &  Visited,
SmallPtrSetImpl< Instruction *> &  CI 
)
static

Returns true if all the source operands of a recurrence are either SExtInsts or ZExtInsts.

This function is intended to be used with lookThroughAnd to determine if the recurrence has been type-promoted. The source operands are added to CI, and IsSigned is updated to indicate if all source operands are SExtInsts.

Definition at line 104 of file LoopUtils.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::Type::getPrimitiveSizeInBits(), llvm::CastInst::getSrcTy(), llvm::Value::hasOneUse(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::User::operands(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

◆ getUnsafeAlgebraInst()

Instruction* llvm::RecurrenceDescriptor::getUnsafeAlgebraInst ( )
inline

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

Definition at line 210 of file LoopUtils.h.

Referenced by hasOutsideLoopUser().

◆ hasMultipleUsesOf()

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

Returns true if instruction I has multiple uses in Insts.

Definition at line 469 of file LoopUtils.cpp.

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

◆ hasUnsafeAlgebra()

bool llvm::RecurrenceDescriptor::hasUnsafeAlgebra ( )
inline

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

Definition at line 207 of file LoopUtils.h.

Referenced by hasOutsideLoopUser().

◆ isArithmeticRecurrenceKind()

bool RecurrenceDescriptor::isArithmeticRecurrenceKind ( RecurrenceKind  Kind)
static

Returns true if the recurrence kind is an arithmetic kind.

Definition at line 67 of file LoopUtils.cpp.

◆ 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 531 of file LoopUtils.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 hasOutsideLoopUser().

◆ isFloatingPointRecurrenceKind()

bool RecurrenceDescriptor::isFloatingPointRecurrenceKind ( RecurrenceKind  Kind)
static

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

Definition at line 63 of file LoopUtils.cpp.

◆ isIntegerRecurrenceKind()

bool RecurrenceDescriptor::isIntegerRecurrenceKind ( RecurrenceKind  Kind)
static

Returns true if the recurrence kind is an integer kind.

Definition at line 48 of file LoopUtils.cpp.

◆ 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 382 of file LoopUtils.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().

◆ 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 431 of file LoopUtils.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(), and llvm::MCID::Select.

◆ isReductionPHI()

bool RecurrenceDescriptor::isReductionPHI ( PHINode Phi,
Loop TheLoop,
RecurrenceDescriptor RedDes 
)
static

◆ isSigned()

bool llvm::RecurrenceDescriptor::isSigned ( )
inline

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

Definition at line 248 of file LoopUtils.h.

◆ lookThroughAnd()

Instruction * RecurrenceDescriptor::lookThroughAnd ( PHINode Phi,
Type *&  RT,
SmallPtrSetImpl< Instruction *> &  Visited,
SmallPtrSetImpl< Instruction *> &  CI 
)
static

Determines if Phi may have been type-promoted.

If Phi has a single user that ANDs the Phi with a type mask, return the user. RT is updated to account for the narrower bit width represented by the mask, and the AND instruction is added to CI.

Definition at line 81 of file LoopUtils.cpp.

References llvm::tgtok::Bits, llvm::IntegerType::get(), llvm::Value::getContext(), llvm::Value::hasOneUse(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::match(), and llvm::Value::use_begin().


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