class LoopVectorizationLegality

Declaration

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

Description

LoopVectorizationLegality checks if it is legal to vectorize a loop, and to what vectorization factor. This class does not look at the profitability of vectorization, only the legality. This class has two main kinds of checks: * Memory checks - The code in canVectorizeMemory checks if vectorization will change the order of memory accesses in a way that will change the correctness of the program. * Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory checks for a number of different conditions, such as the availability of a single induction variable, that all types are supported and vectorize-able, etc. This code reflects the capabilities of InnerLoopVectorizer. This class is also used by InnerLoopVectorizer for identifying induction variable and the different reduction variables.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:241

Member Variables

private llvm::Loop* TheLoop
The loop that we evaluate.
private llvm::LoopInfo* LI
Loop Info analysis.
private llvm::PredicatedScalarEvolution& PSE
A wrapper around ScalarEvolution used to add runtime SCEV checks. Applies dynamic knowledge to simplify SCEV expressions in the context of existing SCEV assumptions. The analysis will also add a minimal set of new predicates if this is required to enable vectorization and unrolling.
private llvm::TargetTransformInfo* TTI
Target Transform Info.
private llvm::TargetLibraryInfo* TLI
Target Library Info.
private llvm::DominatorTree* DT
Dominator Tree.
private std::function<const LoopAccessInfo&(Loop&)>* GetLAA
private const llvm::LoopAccessInfo* LAI = nullptr
private llvm::OptimizationRemarkEmitter* ORE
Interface to emit optimization remarks.
private llvm::PHINode* PrimaryInduction = nullptr
Holds the primary induction variable. This is the counter of the loop.
private llvm::LoopVectorizationLegality::ReductionList Reductions
Holds the reduction variables.
private llvm::LoopVectorizationLegality::InductionList Inductions
Holds all of the induction variables that we found in the loop. Notice that inductions don't need to start at zero and that induction variables can be pointers.
private SmallPtrSet<llvm::Instruction*, 4> InductionCastsToIgnore
Holds all the casts that participate in the update chain of the induction variables, and that have been proven to be redundant (possibly under a runtime guard). These casts can be ignored when creating the vectorized loop body.
private llvm::LoopVectorizationLegality::RecurrenceSet FirstOrderRecurrences
Holds the phi nodes that are first-order recurrences.
private MapVector<llvm::Instruction*, llvm::Instruction*> SinkAfter
Holds instructions that need to sink past other instructions to handle first-order recurrences.
private llvm::Type* WidestIndTy = nullptr
Holds the widest induction type encountered.
private SmallPtrSet<llvm::Value*, 4> AllowedExit
Allowed outside users. This holds the variables that can be accessed from outside the loop.
private llvm::LoopVectorizationRequirements* Requirements
Vectorization requirements that will go through late-evaluation.
private llvm::LoopVectorizeHints* Hints
Used to emit an analysis of any legality issues.
private llvm::DemandedBits* DB
The demanded bits analysis is used to compute the minimum type size in which a reduction can be computed.
private llvm::AssumptionCache* AC
The assumption cache analysis is used to compute the minimum type size in which a reduction can be computed.
private SmallPtrSet<const llvm::Instruction*, 8> MaskedOp
While vectorizing these instructions we have to generate a call to the appropriate masked intrinsic
private SmallPtrSet<llvm::Instruction*, 8> ConditionalAssumes
Assume instructions in predicated blocks must be dropped if the CFG gets flattened.
private llvm::BlockFrequencyInfo* BFI
BFI and PSI are used to check for profile guided size optimizations.
private llvm::ProfileSummaryInfo* PSI

Method Overview

Methods

LoopVectorizationLegality(
    llvm::Loop* L,
    llvm::PredicatedScalarEvolution& PSE,
    llvm::DominatorTree* DT,
    llvm::TargetTransformInfo* TTI,
    llvm::TargetLibraryInfo* TLI,
    llvm::AAResults* AA,
    llvm::Function* F,
    std::function<const LoopAccessInfo&(Loop&)>*
        GetLAA,
    llvm::LoopInfo* LI,
    llvm::OptimizationRemarkEmitter* ORE,
    llvm::LoopVectorizationRequirements* R,
    llvm::LoopVectorizeHints* H,
    llvm::DemandedBits* DB,
    llvm::AssumptionCache* AC,
    llvm::BlockFrequencyInfo* BFI,
    llvm::ProfileSummaryInfo* PSI)

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:243

Parameters

llvm::Loop* L
llvm::PredicatedScalarEvolution& PSE
llvm::DominatorTree* DT
llvm::TargetTransformInfo* TTI
llvm::TargetLibraryInfo* TLI
llvm::AAResults* AA
llvm::Function* F
std::function<const LoopAccessInfo&(Loop&)>* GetLAA
llvm::LoopInfo* LI
llvm::OptimizationRemarkEmitter* ORE
llvm::LoopVectorizationRequirements* R
llvm::LoopVectorizeHints* H
llvm::DemandedBits* DB
llvm::AssumptionCache* AC
llvm::BlockFrequencyInfo* BFI
llvm::ProfileSummaryInfo* PSI

void addInductionPhi(
    llvm::PHINode* Phi,
    const llvm::InductionDescriptor& ID,
    SmallPtrSetImpl<llvm::Value*>& AllowedExit)

Description

Updates the vectorization state by adding \p Phi to the inductions list. This can set \p Phi as the main induction of the loop if \p Phi is a better choice for the main induction than the existing one.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:462

Parameters

llvm::PHINode* Phi
const llvm::InductionDescriptor& ID
SmallPtrSetImpl<llvm::Value*>& AllowedExit

bool blockCanBePredicated(
    llvm::BasicBlock* BB,
    SmallPtrSetImpl<llvm::Value*>& SafePtrs,
    SmallPtrSetImpl<const llvm::Instruction*>&
        MaskedOp,
    SmallPtrSetImpl<llvm::Instruction*>&
        ConditionalAssumes) const

Description

Return true if all of the instructions in the block can be speculatively executed, and record the loads/stores that require masking.\p SafePtrs is a list of addresses that are known to be legal and we know that we can read from them without segfault.\p MaskedOp is a list of instructions that have to be transformed into calls to the appropriate masked intrinsic when the loop is vectorized.\p ConditionalAssumes is a list of assume instructions in predicated blocks that must be dropped if the CFG gets flattened.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:454

Parameters

llvm::BasicBlock* BB
SmallPtrSetImpl<llvm::Value*>& SafePtrs
SmallPtrSetImpl<const llvm::Instruction*>& MaskedOp
SmallPtrSetImpl<llvm::Instruction*>& ConditionalAssumes

bool blockNeedsPredication(
    llvm::BasicBlock* BB) const

Description

Return true if the block BB needs to be predicated in order for the loop to be vectorized.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:340

Parameters

llvm::BasicBlock* BB

bool canVectorize(bool UseVPlanNativePath)

Description

Returns true if it is legal to vectorize this loop. This does not mean that it is profitable to vectorize this loop, only that it is legal to do so. Temporarily taking UseVPlanNativePath parameter. If true, take the new code path being implemented for outer loop vectorization (should be functional for inner loop vectorization) based on VPlan. If false, good old LV code.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:273

Parameters

bool UseVPlanNativePath

bool canVectorizeFPMath(
    bool EnableStrictReductions)

Description

Returns true if it is legal to vectorize the FP math operations in this loop. Vectorizing is legal if we allow reordering of FP operations, or if we can use in-order reductions.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:278

Parameters

bool EnableStrictReductions

bool canVectorizeInstrs()

Description

Check if a single basic block loop is vectorizable. At this point we know that this is a loop with a constant trip count and we only need to check individual instructions.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:430

bool canVectorizeLoopCFG(llvm::Loop* Lp,
                         bool UseVPlanNativePath)

Description

Return true if the pre-header, exiting and latch blocks of \p Lp (non-recursive) are considered legal for vectorization. Temporarily taking UseVPlanNativePath parameter. If true, take the new code path being implemented for outer loop vectorization (should be functional for inner loop vectorization) based on VPlan. If false, good old LV code.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:425

Parameters

llvm::Loop* Lp
bool UseVPlanNativePath

bool canVectorizeLoopNestCFG(
    llvm::Loop* Lp,
    bool UseVPlanNativePath)

Description

Return true if the pre-header, exiting and latch blocks of \p Lp and all its nested loops are considered legal for vectorization. These legal checks are common for inner and outer loop vectorization. Temporarily taking UseVPlanNativePath parameter. If true, take the new code path being implemented for outer loop vectorization (should be functional for inner loop vectorization) based on VPlan. If false, good old LV code.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:412

Parameters

llvm::Loop* Lp
bool UseVPlanNativePath

bool canVectorizeMemory()

Description

When we vectorize loops we may change the order in which we read and write from memory. This method checks if it is legal to vectorize the code, considering only memory constrains. Returns true if the loop is vectorizable

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:436

bool canVectorizeOuterLoop()

Description

Return true if we can vectorize this outer loop. The method performs specific checks for outer loop vectorization.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:444

bool canVectorizeWithIfConvert()

Description

Return true if we can vectorize this loop using the IF-conversion transformation.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:440

const SmallPtrSetImpl<llvm::Instruction*>&
getConditionalAssumes() const

Description

Returns all assume calls in predicated blocks. They need to be dropped when flattening the CFG.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:400

llvm::LoopVectorizationLegality::RecurrenceSet&
getFirstOrderRecurrences()

Description

Return the first-order recurrences found in the loop.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:295

const llvm::LoopVectorizationLegality::
    InductionList&
    getInductionVars() const

Description

Returns the induction variables found in the loop.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:292

const llvm::InductionDescriptor*
getIntOrFpInductionDescriptor(
    llvm::PHINode* Phi) const

Description

Returns a pointer to the induction descriptor, if \p Phi is an integer or floating point induction.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:316

Parameters

llvm::PHINode* Phi

const llvm::LoopAccessInfo* getLAI() const

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:375

unsigned int getMaxSafeDepDistBytes()

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:381

uint64_t getMaxSafeVectorWidthInBits() const

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:383

unsigned int getNumLoads() const

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:396

unsigned int getNumStores() const

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:395

const llvm::InductionDescriptor*
getPointerInductionDescriptor(
    llvm::PHINode* Phi) const

Description

Returns a pointer to the induction descriptor, if \p Phi is pointer induction.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:320

Parameters

llvm::PHINode* Phi

llvm::PHINode* getPrimaryInduction()

Description

Returns the primary induction variable.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:286

const llvm::LoopVectorizationLegality::
    ReductionList&
    getReductionVars() const

Description

Returns the reduction variables found in the loop.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:289

const llvm::RuntimePointerChecking*
getRuntimePointerChecking() const

Description

Returns the information that we collected about runtime memory check.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:371

MapVector<llvm::Instruction*, llvm::Instruction*>&
getSinkAfter()

Description

Return the set of instructions to sink to handle first-order recurrences.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:298

const llvm::ValueToValueMap* getSymbolicStrides()
    const

Description

If an access has a symbolic strides, this maps the pointer value to the stride symbol.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:467

llvm::Type* getWidestInductionType()

Description

Returns the widest induction type.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:301

bool hasStride(llvm::Value* V)

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:387

Parameters

llvm::Value* V

bool isCastedInductionVariable(
    const llvm::Value* V) const

Description

Returns True if V is a cast that is part of an induction def-use chain, and had been proven to be redundant under a runtime guard (in other words, the cast has the same SCEV expression as the induction phi).

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:325

Parameters

const llvm::Value* V

int isConsecutivePtr(llvm::Type* AccessTy,
                     llvm::Value* Ptr) const

Description

Check if this pointer is consecutive when vectorizing. This happens when the last index of the GEP is the induction variable, or that the pointer itself is an induction variable. This check allows us to vectorize A[idx] into a wide load/store. Returns: 0 - Stride is unknown or non-consecutive. 1 - Address is consecutive. -1 - Address is consecutive, and decreasing. NOTE: This method must only be used before modifying the original scalar loop. Do not use after invoking 'createVectorizedLoopSkeleton' (PR34965).

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:352

Parameters

llvm::Type* AccessTy
llvm::Value* Ptr

bool isFirstOrderRecurrence(
    const llvm::PHINode* Phi) const

Description

Returns True if Phi is a first-order recurrence in this loop.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:336

Parameters

const llvm::PHINode* Phi

bool isInductionPhi(const llvm::Value* V) const

Description

Returns True if V is a Phi node of an induction variable in this loop.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:312

Parameters

const llvm::Value* V

bool isInductionVariable(
    const llvm::Value* V) const

Description

Returns True if V can be considered as an induction variable in this loop. V can be the induction phi, or some redundant cast in the def-use chain of the inducion phi.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:330

Parameters

const llvm::Value* V

bool isInvariantAddressOfReduction(llvm::Value* V)

Description

Returns True if given address is invariant and is used to store recurrent expression

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:309

Parameters

llvm::Value* V

bool isInvariantStoreOfReduction(
    llvm::StoreInst* SI)

Description

Returns True if given store is a final invariant store of one of the reductions found in the loop.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:305

Parameters

llvm::StoreInst* SI

bool isMaskRequired(
    const llvm::Instruction* I) const

Description

Returns true if vector representation of the instruction \p I requires mask.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:391

Parameters

const llvm::Instruction* I

bool isReductionVariable(llvm::PHINode* PN) const

Description

Returns True if PN is a reduction variable in this loop.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:333

Parameters

llvm::PHINode* PN

bool isSafeForAnyVectorWidth() const

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:377

bool isUniform(llvm::Value* V)

Description

Returns true if the value V is uniform within the loop.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:355

Parameters

llvm::Value* V

bool isUniformMemOp(llvm::Instruction& I)

Description

A uniform memory op is a load or store which accesses the same memory location on all lanes.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:359

Parameters

llvm::Instruction& I

bool prepareToFoldTailByMasking()

Description

Return true if we can vectorize this loop while folding its tail by masking, and mark all respective loads/stores for masking. This object's state is only modified iff this function returns true.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:283

bool setupOuterLoopInductions()

Description

Set up outer loop inductions by checking Phis in outer loop header for supported inductions (int inductions). Return false if any of these Phis is not a supported induction or if we fail to find an induction.

Declared at: llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h:417