class RecurrenceDescriptor

Declaration

class RecurrenceDescriptor { /* full declaration omitted */ };

Description

This struct holds information about recurrence variables.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:69

Member Variables

public llvm::StoreInst* 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.
private TrackingVH<llvm::Value> StartValue
private llvm::Instruction* LoopExitInstr = nullptr
private llvm::RecurKind Kind = RecurKind::None
private llvm::FastMathFlags FMF
private llvm::Instruction* ExactFPMathInst = nullptr
private llvm::Type* RecurrenceType = nullptr
private bool IsSigned = false
private bool IsOrdered = false
private SmallPtrSet<llvm::Instruction*, 8> CastInsts
private unsigned int MinWidthCastToRecurrenceType

Method Overview

  • public static bool AddReductionVar(llvm::PHINode * Phi, llvm::RecurKind Kind, llvm::Loop * TheLoop, llvm::FastMathFlags FuncFMF, llvm::RecurrenceDescriptor & RedDes, llvm::DemandedBits * DB = nullptr, llvm::AssumptionCache * AC = nullptr, llvm::DominatorTree * DT = nullptr, llvm::ScalarEvolution * SE = nullptr)
  • public RecurrenceDescriptor(llvm::Value * Start, llvm::Instruction * Exit, llvm::StoreInst * Store, llvm::RecurKind K, llvm::FastMathFlags FMF, llvm::Instruction * ExactFP, llvm::Type * RT, bool Signed, bool Ordered, SmallPtrSetImpl<llvm::Instruction *> & CI, unsigned int MinWidthCastToRecurTy)
  • public RecurrenceDescriptor()
  • public static bool areAllUsesIn(llvm::Instruction * I, SmallPtrSetImpl<llvm::Instruction *> & Set)
  • public const SmallPtrSet<llvm::Instruction *, 8> & getCastInsts() const
  • public llvm::Instruction * getExactFPMathInst() const
  • public llvm::FastMathFlags getFastMathFlags() const
  • public llvm::Instruction * getLoopExitInstr() const
  • public unsigned int getMinWidthCastToRecurrenceTypeInBits() const
  • public static unsigned int getOpcode(llvm::RecurKind Kind)
  • public unsigned int getOpcode() const
  • public llvm::Value * getRecurrenceIdentity(llvm::RecurKind K, llvm::Type * Tp, llvm::FastMathFlags FMF) const
  • public llvm::RecurKind getRecurrenceKind() const
  • public TrackingVH<llvm::Value> getRecurrenceStartValue() const
  • public llvm::Type * getRecurrenceType() const
  • public SmallVector<llvm::Instruction *, 4> getReductionOpChain(llvm::PHINode * Phi, llvm::Loop * L) const
  • public bool hasExactFPMath() const
  • public static bool hasMultipleUsesOf(llvm::Instruction * I, SmallPtrSetImpl<llvm::Instruction *> & Insts, unsigned int MaxNumUses)
  • public static llvm::RecurrenceDescriptor::InstDesc isConditionalRdxPattern(llvm::RecurKind Kind, llvm::Instruction * I)
  • public static bool isFMulAddIntrinsic(llvm::Instruction * I)
  • public static bool isFPMinMaxRecurrenceKind(llvm::RecurKind Kind)
  • public static bool isFirstOrderRecurrence(llvm::PHINode * Phi, llvm::Loop * TheLoop, MapVector<llvm::Instruction *, llvm::Instruction *> & SinkAfter, llvm::DominatorTree * DT)
  • public static bool isFloatingPointRecurrenceKind(llvm::RecurKind Kind)
  • public static bool isIntMinMaxRecurrenceKind(llvm::RecurKind Kind)
  • public static bool isIntegerRecurrenceKind(llvm::RecurKind Kind)
  • public static llvm::RecurrenceDescriptor::InstDesc isMinMaxPattern(llvm::Instruction * I, llvm::RecurKind Kind, const llvm::RecurrenceDescriptor::InstDesc & Prev)
  • public static bool isMinMaxRecurrenceKind(llvm::RecurKind Kind)
  • public bool isOrdered() const
  • public static llvm::RecurrenceDescriptor::InstDesc isRecurrenceInstr(llvm::Loop * L, llvm::PHINode * Phi, llvm::Instruction * I, llvm::RecurKind Kind, llvm::RecurrenceDescriptor::InstDesc & Prev, llvm::FastMathFlags FuncFMF)
  • public static bool isReductionPHI(llvm::PHINode * Phi, llvm::Loop * TheLoop, llvm::RecurrenceDescriptor & RedDes, llvm::DemandedBits * DB = nullptr, llvm::AssumptionCache * AC = nullptr, llvm::DominatorTree * DT = nullptr, llvm::ScalarEvolution * SE = nullptr)
  • public static llvm::RecurrenceDescriptor::InstDesc isSelectCmpPattern(llvm::Loop * Loop, llvm::PHINode * OrigPhi, llvm::Instruction * I, llvm::RecurrenceDescriptor::InstDesc & Prev)
  • public static bool isSelectCmpRecurrenceKind(llvm::RecurKind Kind)
  • public bool isSigned() const

Methods

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

Description

Returns true if Phi is a reduction of type Kind and adds it to the RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are non-null, the minimal bit width needed to compute the reduction will be computed.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:168

Parameters

llvm::PHINode* Phi
llvm::RecurKind Kind
llvm::Loop* TheLoop
llvm::FastMathFlags FuncFMF
llvm::RecurrenceDescriptor& RedDes
llvm::DemandedBits* DB = nullptr
llvm::AssumptionCache* AC = nullptr
llvm::DominatorTree* DT = nullptr
llvm::ScalarEvolution* SE = nullptr

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:73

Parameters

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

RecurrenceDescriptor()

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:71

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

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:134

Parameters

llvm::Instruction* I
SmallPtrSetImpl<llvm::Instruction*>& Set

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

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:246

llvm::Instruction* getExactFPMathInst() const

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:210

llvm::FastMathFlags getFastMathFlags() const

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:199

llvm::Instruction* getLoopExitInstr() const

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:203

unsigned int
getMinWidthCastToRecurrenceTypeInBits() const

Description

Returns the minimum width used by the recurrence in bits.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:249

static unsigned int getOpcode(
    llvm::RecurKind Kind)

Description

Returns the opcode corresponding to the RecurrenceKind.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:161

Parameters

llvm::RecurKind Kind

unsigned int getOpcode() const

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:197

llvm::Value* getRecurrenceIdentity(
    llvm::RecurKind K,
    llvm::Type* Tp,
    llvm::FastMathFlags FMF) const

Description

Returns identity corresponding to the RecurrenceKind.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:158

Parameters

llvm::RecurKind K
llvm::Type* Tp
llvm::FastMathFlags FMF

llvm::RecurKind getRecurrenceKind() const

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:195

TrackingVH<llvm::Value> getRecurrenceStartValue()
    const

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:201

llvm::Type* getRecurrenceType() const

Description

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.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:242

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

Description

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.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:261

Parameters

llvm::PHINode* Phi
llvm::Loop* L

bool hasExactFPMath() const

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:207

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

Description

Returns true if instruction I has multiple uses in Insts

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:129

Parameters

llvm::Instruction* I
SmallPtrSetImpl<llvm::Instruction*>& Insts
unsigned int MaxNumUses

static llvm::RecurrenceDescriptor::InstDesc
isConditionalRdxPattern(llvm::RecurKind Kind,
                        llvm::Instruction* I)

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:155

Parameters

llvm::RecurKind Kind
llvm::Instruction* I

static bool isFMulAddIntrinsic(
    llvm::Instruction* I)

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:265

Parameters

llvm::Instruction* I

static bool isFPMinMaxRecurrenceKind(
    llvm::RecurKind Kind)

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:225

Parameters

llvm::RecurKind Kind

static bool isFirstOrderRecurrence(
    llvm::PHINode* Phi,
    llvm::Loop* TheLoop,
    MapVector<llvm::Instruction*,
              llvm::Instruction*>& SinkAfter,
    llvm::DominatorTree* DT)

Description

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. \p 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.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:191

Parameters

llvm::PHINode* Phi
llvm::Loop* TheLoop
MapVector<llvm::Instruction*, llvm::Instruction*>& SinkAfter
llvm::DominatorTree* DT

static bool isFloatingPointRecurrenceKind(
    llvm::RecurKind Kind)

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:216

Parameters

llvm::RecurKind Kind

static bool isIntMinMaxRecurrenceKind(
    llvm::RecurKind Kind)

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:219

Parameters

llvm::RecurKind Kind

static bool isIntegerRecurrenceKind(
    llvm::RecurKind Kind)

Description

Returns true if the recurrence kind is an integer kind.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:213

Parameters

llvm::RecurKind Kind

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

Description

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 \p Kind. \p Prev specifies the description of an already processed select instruction, so its corresponding cmp can be matched to it.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:141

Parameters

llvm::Instruction* I
llvm::RecurKind Kind
const llvm::RecurrenceDescriptor::InstDesc& Prev

static bool isMinMaxRecurrenceKind(
    llvm::RecurKind Kind)

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:230

Parameters

llvm::RecurKind Kind

bool isOrdered() const

Description

Expose an ordered FP reduction to the instance users.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:257

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

Description

Returns a struct describing if the instruction 'I' can be a recurrence variable of type 'Kind' for a Loop \p L and reduction PHI \p 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.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:124

Parameters

llvm::Loop* L
llvm::PHINode* Phi
llvm::Instruction* I
llvm::RecurKind Kind
llvm::RecurrenceDescriptor::InstDesc& Prev
llvm::FastMathFlags FuncFMF

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

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:179

Parameters

llvm::PHINode* Phi
llvm::Loop* TheLoop
llvm::RecurrenceDescriptor& RedDes
llvm::DemandedBits* DB = nullptr
llvm::AssumptionCache* AC = nullptr
llvm::DominatorTree* DT = nullptr
llvm::ScalarEvolution* SE = nullptr

static llvm::RecurrenceDescriptor::InstDesc
isSelectCmpPattern(
    llvm::Loop* Loop,
    llvm::PHINode* OrigPhi,
    llvm::Instruction* I,
    llvm::RecurrenceDescriptor::InstDesc& Prev)

Description

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. \p Prev specifies the description of an already processed select instruction, so its corresponding cmp can be matched to it.

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:150

Parameters

llvm::Loop* Loop
llvm::PHINode* OrigPhi
llvm::Instruction* I
llvm::RecurrenceDescriptor::InstDesc& Prev

static bool isSelectCmpRecurrenceKind(
    llvm::RecurKind Kind)

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:236

Parameters

llvm::RecurKind Kind

bool isSigned() const

Description

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

Declared at: llvm/include/llvm/Analysis/IVDescriptors.h:254