LLVM 20.0.0git
Macros | Functions
IVDescriptors.cpp File Reference
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/DemandedBits.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/KnownBits.h"

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "iv-descriptors"
 

Functions

static InstructionlookThroughAnd (PHINode *Phi, Type *&RT, SmallPtrSetImpl< Instruction * > &Visited, SmallPtrSetImpl< Instruction * > &CI)
 Determines if Phi may have been type-promoted.
 
static std::pair< Type *, boolcomputeRecurrenceType (Instruction *Exit, DemandedBits *DB, AssumptionCache *AC, DominatorTree *DT)
 Compute the minimal bit width needed to represent a reduction whose exit instruction is given by Exit.
 
static void collectCastInstrs (Loop *TheLoop, Instruction *Exit, Type *RecurrenceType, SmallPtrSetImpl< Instruction * > &Casts, unsigned &MinWidthCastToRecurTy)
 Collect cast instructions that can be ignored in the vectorizer's cost model, given a reduction exit value and the minimal type in which the.
 
static bool checkOrderedReduction (RecurKind Kind, Instruction *ExactFPMathInst, Instruction *Exit, PHINode *Phi)
 
static bool getCastsForInductionPHI (PredicatedScalarEvolution &PSE, const SCEVUnknown *PhiScev, const SCEVAddRecExpr *AR, SmallVectorImpl< Instruction * > &CastInsts)
 This function is called when we suspect that the update-chain of a phi node (whose symbolic SCEV expression sin PhiScev) contains redundant casts, that can be ignored.
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "iv-descriptors"

Definition at line 30 of file IVDescriptors.cpp.

Function Documentation

◆ checkOrderedReduction()

static bool checkOrderedReduction ( RecurKind  Kind,
Instruction ExactFPMathInst,
Instruction Exit,
PHINode Phi 
)
static

◆ collectCastInstrs()

static void collectCastInstrs ( Loop TheLoop,
Instruction Exit,
Type RecurrenceType,
SmallPtrSetImpl< Instruction * > &  Casts,
unsigned MinWidthCastToRecurTy 
)
static

Collect cast instructions that can be ignored in the vectorizer's cost model, given a reduction exit value and the minimal type in which the.

Definition at line 139 of file IVDescriptors.cpp.

References llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SmallVectorBase< Size_T >::empty(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::RecurrenceDescriptor::AddReductionVar().

◆ computeRecurrenceType()

static std::pair< Type *, bool > computeRecurrenceType ( Instruction Exit,
DemandedBits DB,
AssumptionCache AC,
DominatorTree DT 
)
static

Compute the minimal bit width needed to represent a reduction whose exit instruction is given by Exit.

Definition at line 93 of file IVDescriptors.cpp.

References llvm::bit_ceil(), llvm::computeKnownBits(), llvm::ComputeNumSignBits(), DL, and llvm::Type::getIntNTy().

Referenced by llvm::RecurrenceDescriptor::AddReductionVar().

◆ getCastsForInductionPHI()

static bool getCastsForInductionPHI ( PredicatedScalarEvolution PSE,
const SCEVUnknown PhiScev,
const SCEVAddRecExpr AR,
SmallVectorImpl< Instruction * > &  CastInsts 
)
static

This function is called when we suspect that the update-chain of a phi node (whose symbolic SCEV expression sin PhiScev) contains redundant casts, that can be ignored.

(This can happen when the PSCEV rewriter adds a runtime predicate P under which the SCEV expression for the phi can be the AddRecurrence AR; See createAddRecFromPHIWithCast). We want to find the cast instructions that are involved in the update-chain of this induction. A caller that adds the required runtime predicate can be free to drop these cast instructions, and compute the phi using AR (instead of some scev expression with casts).

For example, without a predicate the scev expression can take the following form: (Ext ix (Trunc iy ( Start + i*Step ) to ix) to iy)

It corresponds to the following IR sequence: for.body: x = phi i64 [ 0, ph ], [ add, for.body ] casted_phi = "ExtTrunc i64 %x" add = add i64 casted_phi, step

where x is given in PN, PSE.getSCEV(x) is equal to PSE.getSCEV(casted_phi) under a predicate, and the IR sequence that "ExtTrunc i64 %x" represents can take one of several forms, for example, such as: ExtTrunc1: casted_phi = and x, 2^n-1 or: ExtTrunc2: t = shl x, m casted_phi = ashr t, m

If we are able to find such sequence, we return the instructions we found, namely casted_phi and the instructions on its use-def chain up to the phi (not including the phi).

Definition at line 1360 of file IVDescriptors.cpp.

References llvm::PredicatedScalarEvolution::areAddRecsEqualWithPreds(), assert(), llvm::SmallVectorBase< Size_T >::empty(), llvm::SCEVAddRecExpr::getLoop(), llvm::User::getOperand(), llvm::PredicatedScalarEvolution::getSCEV(), llvm::SCEVUnknown::getValue(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::InductionDescriptor::isInductionPHI().

◆ lookThroughAnd()

static Instruction * 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 68 of file IVDescriptors.cpp.

References llvm::IntegerType::get(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_Instruction(), and llvm::PatternMatch::match().

Referenced by llvm::RecurrenceDescriptor::AddReductionVar().