class InnerLoopVectorizer

Declaration

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

Description

InnerLoopVectorizer vectorizes loops which contain only one basic block to a specified vectorization factor (VF). This class performs the widening of scalars into vectors, or multiple scalars. This class also implements the following features: * It inserts an epilogue loop for handling loops that don't have iteration counts that are known to be a multiple of the vectorization factor. * It handles the code generation for reduction variables. * Scalarization (implementation using scalars) of un-vectorizable instructions. InnerLoopVectorizer does not perform any vectorization-legality checks, and relies on the caller to check for the different legality aspects. The InnerLoopVectorizer relies on the LoopVectorizationLegality class to provide information about the induction and reduction variables that were found to a given vectorization factor.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:398

Member Variables

protected llvm::Loop* OrigLoop
The original loop.
protected llvm::PredicatedScalarEvolution& PSE
A wrapper around ScalarEvolution used to add runtime SCEV checks. Applies dynamic knowledge to simplify SCEV expressions and converts them to a more usable form.
protected llvm::LoopInfo* LI
Loop Info.
protected llvm::DominatorTree* DT
Dominator Tree.
protected llvm::AliasAnalysis* AA
Alias Analysis.
protected const llvm::TargetLibraryInfo* TLI
Target Library Info.
protected const llvm::TargetTransformInfo* TTI
Target Transform Info.
protected llvm::AssumptionCache* AC
Assumption Cache.
protected llvm::OptimizationRemarkEmitter* ORE
Interface to emit optimization remarks.
protected std::unique_ptr<LoopVersioning> LVer
This is currently only used to add no-alias metadata based on the memchecks. The actually versioning is performed manually.
protected unsigned int VF
The vectorization SIMD factor to use. Each vector will have this many vector elements.
protected unsigned int UF
The vectorization unroll factor to use. Each scalar is vectorized to this many different vector instructions.
protected IRBuilder<> Builder
The builder that we use
protected llvm::BasicBlock* LoopVectorPreHeader
The vector-loop preheader.
protected llvm::BasicBlock* LoopScalarPreHeader
The scalar-loop preheader.
protected llvm::BasicBlock* LoopMiddleBlock
Middle Block between the vector and the scalar.
protected llvm::BasicBlock* LoopExitBlock
The ExitBlock of the scalar loop.
protected llvm::BasicBlock* LoopVectorBody
The vector loop body.
protected llvm::BasicBlock* LoopScalarBody
The scalar loop body.
protected SmallVector<llvm::BasicBlock*, 4> LoopBypassBlocks
A list of all bypass blocks. The first block is the entry of the loop.
protected llvm::PHINode* Induction = nullptr
The new Induction variable which was added to the new block.
protected llvm::PHINode* OldInduction = nullptr
The induction variable of the old basic block.
protected llvm::VectorizerValueMap VectorLoopValueMap
Maps values from the original loop to their corresponding values in the vectorized loop. A key value can map to either vector values, scalar values or both kinds of values, depending on whether the key was vectorized and scalarized.
protected SmallVector<llvm::Instruction*, 4> PredicatedInstructions
Store instructions that were predicated.
protected llvm::Value* TripCount = nullptr
Trip count of the original loop.
protected llvm::Value* VectorTripCount = nullptr
Trip count of the widened loop (TripCount - TripCount % (VF*UF))
The legality analysis.
protected llvm::LoopVectorizationCostModel* Cost
The profitablity analysis.
protected bool AddedSafetyChecks = false
protected DenseMap<llvm::PHINode*, llvm::Value*> IVEndValues
protected SmallVector<llvm::PHINode*, 8> OrigPHIsToFix

Method Overview

Methods

InnerLoopVectorizer(
    llvm::Loop* OrigLoop,
    llvm::PredicatedScalarEvolution& PSE,
    llvm::LoopInfo* LI,
    llvm::DominatorTree* DT,
    const llvm::TargetLibraryInfo* TLI,
    const llvm::TargetTransformInfo* TTI,
    llvm::AssumptionCache* AC,
    llvm::OptimizationRemarkEmitter* ORE,
    unsigned int VecWidth,
    unsigned int UnrollFactor,
    llvm::LoopVectorizationLegality* LVL,
    llvm::LoopVectorizationCostModel* CM)

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:400

Parameters

llvm::Loop* OrigLoop
llvm::PredicatedScalarEvolution& PSE
llvm::LoopInfo* LI
llvm::DominatorTree* DT
const llvm::TargetLibraryInfo* TLI
const llvm::TargetTransformInfo* TTI
llvm::AssumptionCache* AC
llvm::OptimizationRemarkEmitter* ORE
unsigned int VecWidth
unsigned int UnrollFactor
llvm::LoopVectorizationLegality* LVL
llvm::LoopVectorizationCostModel* CM

void addMetadata(ArrayRef<llvm::Value*> To,
                 llvm::Instruction* From)

Description

Similar to the previous function but it adds the metadata to a vector of instructions.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:668

Parameters

ArrayRef<llvm::Value*> To
llvm::Instruction* From

void addMetadata(llvm::Instruction* To,
                 llvm::Instruction* From)

Description

Add metadata from one instruction to another. This includes both the original MDs from \p From and additional ones (

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:664

Parameters

llvm::Instruction* To
llvm::Instruction* From

void addNewMetadata(llvm::Instruction* To,
                    const llvm::Instruction* Orig)

Description

Add additional metadata to \p To that was not present on \p Orig. Currently this is used to add the noalias annotations based on the inserted memchecks. Use this for instructions that are *cloned* into the vector loop.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:657

Parameters

llvm::Instruction* To
const llvm::Instruction* Orig

bool areSafetyChecksAdded()

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:424

void buildScalarSteps(
    llvm::Value* ScalarIV,
    llvm::Value* Step,
    llvm::Instruction* EntryVal,
    const llvm::InductionDescriptor& ID)

Description

Compute scalar induction steps. \p ScalarIV is the scalar induction variable on which to base the steps, \p Step is the size of the step, and\p EntryVal is the value from the original loop that maps to the steps. Note that \p EntryVal doesn't have to be an induction variable - it can also be a truncate instruction.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:575

Parameters

llvm::Value* ScalarIV
llvm::Value* Step
llvm::Instruction* EntryVal
const llvm::InductionDescriptor& ID

void clearReductionWrapFlags(
    llvm::RecurrenceDescriptor& RdxDesc)

Description

Clear NSW/NUW flags from reduction instructions if necessary.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:540

Parameters

llvm::RecurrenceDescriptor& RdxDesc

llvm::Value* createBitOrPointerCast(
    llvm::Value* V,
    llvm::VectorType* DstVTy,
    const llvm::DataLayout& DL)

Description

Returns a bitcasted value to the requested vector type. Also handles bitcasts of vector <float > < -> vector <pointer > types.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:628

Parameters

llvm::Value* V
llvm::VectorType* DstVTy
const llvm::DataLayout& DL

llvm::PHINode* createInductionVariable(
    llvm::Loop* L,
    llvm::Value* Start,
    llvm::Value* End,
    llvm::Value* Step,
    llvm::Instruction* DL)

Description

Create a new induction variable inside L.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:525

Parameters

llvm::Loop* L
llvm::Value* Start
llvm::Value* End
llvm::Value* Step
llvm::Instruction* DL

void createVectorIntOrFpInductionPHI(
    const llvm::InductionDescriptor& II,
    llvm::Value* Step,
    llvm::Instruction* EntryVal)

Description

Create a vector induction phi node based on an existing scalar one. \p EntryVal is the value from the original loop that maps to the vector phi node, and \p Step is the loop-invariant step. If \p EntryVal is a truncate instruction, instead of widening the original IV, we widen a version of the IV truncated to \p EntryVal's type.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:583

Parameters

const llvm::InductionDescriptor& II
llvm::Value* Step
llvm::Instruction* EntryVal

llvm::BasicBlock* createVectorizedLoopSkeleton()

Description

Create a new empty loop. Unlink the old loop and connect the new one. Return the pre-header block of the new loop.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:415

void emitMemRuntimeChecks(
    llvm::Loop* L,
    llvm::BasicBlock* Bypass)

Description

Emit bypass checks to check any memory assumptions we may have made.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:640

Parameters

llvm::Loop* L
llvm::BasicBlock* Bypass

void emitMinimumIterationCountCheck(
    llvm::Loop* L,
    llvm::BasicBlock* Bypass)

Description

Emit a bypass check to see if the vector trip count is zero, including if it overflows.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:633

Parameters

llvm::Loop* L
llvm::BasicBlock* Bypass

void emitSCEVChecks(llvm::Loop* L,
                    llvm::BasicBlock* Bypass)

Description

Emit a bypass check to see if all of the SCEV assumptions we've had to make are correct.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:637

Parameters

llvm::Loop* L
llvm::BasicBlock* Bypass

llvm::Value* emitTransformedIndex(
    IRBuilder<>& B,
    llvm::Value* Index,
    llvm::ScalarEvolution* SE,
    const llvm::DataLayout& DL,
    const llvm::InductionDescriptor& ID) const

Description

Compute the transformed value of Index at offset StartValue using step StepValue. For integer induction, returns StartValue + Index * StepValue. For pointer induction, returns StartValue[Index * StepValue]. FIXME: The newly created binary instructions should contain nsw/nuw flags, which can be found from the original scalar operations.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:648

Parameters

IRBuilder<>& B
llvm::Value* Index
llvm::ScalarEvolution* SE
const llvm::DataLayout& DL
const llvm::InductionDescriptor& ID

void fixCrossIterationPHIs()

Description

Handle all cross-iteration phis in the header.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:529

void fixFirstOrderRecurrence(llvm::PHINode* Phi)

Description

Fix a first-order recurrence. This is the second phase of vectorizing this phi node.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:533

Parameters

llvm::PHINode* Phi

void fixLCSSAPHIs()

Description

The Loop exit block may have single value PHI nodes with some incoming value. While vectorizing we only handled real values that were defined inside the loop and we should have one value for each predecessor of its parent basic block. See PR14725.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:546

void fixNonInductionPHIs()

Description

Fix the non-induction PHIs in the OrigPHIsToFix vector.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:505

void fixReduction(llvm::PHINode* Phi)

Description

Fix a reduction cross-iteration phi. This is the second phase of vectorizing this phi node.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:537

Parameters

llvm::PHINode* Phi

void fixVectorizedLoop()

Description

Fix the vectorized code, taking care of header phi's, live-outs, and more.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:421

void fixupIVUsers(
    llvm::PHINode* OrigPhi,
    const llvm::InductionDescriptor& II,
    llvm::Value* CountRoundDown,
    llvm::Value* EndValue,
    llvm::BasicBlock* MiddleBlock)

Description

Set up the values of the IVs correctly when exiting the vector loop.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:520

Parameters

llvm::PHINode* OrigPhi
const llvm::InductionDescriptor& II
llvm::Value* CountRoundDown
llvm::Value* EndValue
llvm::BasicBlock* MiddleBlock

virtual llvm::Value* getBroadcastInstrs(
    llvm::Value* V)

Description

Create a broadcast instruction. This method generates a broadcast instruction (shuffle) for loop invariant values and for the induction value. If this is the induction variable then we extend it to N, N+1, ... this is needed because each iteration in the loop corresponds to a SIMD element.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:561

Parameters

llvm::Value* V

llvm::Value* getOrCreateScalarValue(
    llvm::Value* V,
    const llvm::VPIteration& Instance)

Description

Return a value in the new loop corresponding to \p V from the original loop at unroll and vector indices \p Instance. If the value has been vectorized but not scalarized, the necessary extractelement instruction will be generated.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:480

Parameters

llvm::Value* V
const llvm::VPIteration& Instance

llvm::Value* getOrCreateTripCount(
    llvm::Loop* NewLoop)

Description

Returns (and creates if needed) the original loop trip count.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:621

Parameters

llvm::Loop* NewLoop

llvm::Value* getOrCreateVectorTripCount(
    llvm::Loop* NewLoop)

Description

Returns (and creates if needed) the trip count of the widened loop.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:624

Parameters

llvm::Loop* NewLoop

llvm::Value* getOrCreateVectorValue(
    llvm::Value* V,
    unsigned int Part)

Description

getOrCreateVectorValue and getOrCreateScalarValue coordinate to generate a vector or scalar value on-demand if one is not yet available. When vectorizing a loop, we visit the definition of an instruction before its uses. When visiting the definition, we either vectorize or scalarize the instruction, creating an entry for it in the corresponding map. (In some cases, such as induction variables, we will create both vector and scalar entries.) Then, as we encounter uses of the definition, we derive values for each scalar or vector use unless such a value is already available. For example, if we scalarize a definition and one of its uses is vector, we build the required vector on-demand with an insertelement sequence when visiting the use. Otherwise, if the use is scalar, we can use the existing scalar definition. Return a value in the new loop corresponding to \p V from the original loop at unroll index \p Part. If the value has already been vectorized, the corresponding vector entry in VectorLoopValueMap is returned. If, however, the value has a scalar entry in VectorLoopValueMap, we construct a new vector value on-demand by inserting the scalar values into a vector with an insertelement sequence. If the value has been neither vectorized nor scalarized, it must be loop invariant, so we simply broadcast the value into a vector.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:474

Parameters

llvm::Value* V
unsigned int Part

virtual llvm::Value* getStepVector(
    llvm::Value* Val,
    int StartIdx,
    llvm::Value* Step,
    Instruction::BinaryOps Opcode =
        Instruction::BinaryOpsEnd)

Description

This function adds (StartIdx, StartIdx + Step, StartIdx + 2*Step, ...) to each vector element of Val. The sequence starts at StartIndex.\p Opcode is relevant for FP induction variable.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:566

Parameters

llvm::Value* Val
int StartIdx
llvm::Value* Step
Instruction::BinaryOps Opcode = Instruction::BinaryOpsEnd

bool needsScalarInduction(
    llvm::Instruction* IV) const

Description

Returns true if we should generate a scalar version of \p IV.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:591

Parameters

llvm::Instruction* IV

void packScalarIntoVectorValue(
    llvm::Value* V,
    const llvm::VPIteration& Instance)

Description

Construct the vector value of a scalarized value \p V one lane at a time.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:483

Parameters

llvm::Value* V
const llvm::VPIteration& Instance

void recordVectorLoopValueForInductionCast(
    const llvm::InductionDescriptor& ID,
    const llvm::Instruction* EntryVal,
    llvm::Value* VectorLoopValue,
    unsigned int Part,
    unsigned int Lane = (2147483647 * 2U + 1U))

Description

If there is a cast involved in the induction variable \p ID, which should be ignored in the vectorized loop body, this function records the VectorLoopValue of the respective Phi also as the VectorLoopValue of the cast. We had already proved that the casted Phi is equal to the uncasted Phi in the vectorized loop (under a runtime guard), and therefore there is no need to vectorize the cast - the same value can be used in the vector loop for both the Phi and the cast. If \p VectorLoopValue is a scalarized value, \p Lane is also specified, Otherwise, \p VectorLoopValue is a widened/vectorized value. \p EntryVal is the value from the original loop that maps to the vector phi node and is used to distinguish what is the IV currently being processed - original one (if \p EntryVal is a phi corresponding to the original IV) or the "newly-created" one based on the proof mentioned above (see also buildScalarSteps() and createVectorIntOrFPInductionPHI()). In the latter case \p EntryVal is a TruncInst and we must not record anything for that IV, but it's error-prone to expect callers of this routine to care about that, hence this explicit parameter.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:611

Parameters

const llvm::InductionDescriptor& ID
const llvm::Instruction* EntryVal
llvm::Value* VectorLoopValue
unsigned int Part
unsigned int Lane = (2147483647 * 2U + 1U)

virtual llvm::Value* reverseVector(
    llvm::Value* Vec)

Description

Generate a shuffle sequence that will reverse the vector Vec.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:618

Parameters

llvm::Value* Vec

void scalarizeInstruction(
    llvm::Instruction* Instr,
    const llvm::VPIteration& Instance,
    bool IfPredicateInstr)

Description

A helper function to scalarize a single Instruction in the innermost loop. Generates a sequence of scalar instances for each lane between \p MinLane and \p MaxLane, times each part between \p MinPart and \p MaxPart, inclusive..

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:445

Parameters

llvm::Instruction* Instr
const llvm::VPIteration& Instance
bool IfPredicateInstr

void setDebugLocFromInst(IRBuilder<>& B,
                         const llvm::Value* Ptr)

Description

Set the debug location in the builder using the debug location in the instruction.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:502

Parameters

IRBuilder<>& B
const llvm::Value* Ptr

bool shouldScalarizeInstruction(
    llvm::Instruction* I) const

Description

Returns true if an instruction \p I should be scalarized instead of vectorized for the chosen vectorization factor.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:588

Parameters

llvm::Instruction* I

void sinkScalarOperands(
    llvm::Instruction* PredInst)

Description

Iteratively sink the scalarized operands of a predicated instruction into the block that was created for it.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:550

Parameters

llvm::Instruction* PredInst

void truncateToMinimalBitwidths()

Description

Shrinks vector element sizes to the smallest bitwidth they can be legally represented as.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:554

void vectorizeInterleaveGroup(
    llvm::Instruction* Instr,
    llvm::VPTransformState& State,
    llvm::VPValue* Addr,
    llvm::VPValue* BlockInMask = nullptr)

Description

Try to vectorize the interleaved access group that \p Instr belongs to with the base address given in \p Addr, optionally masking the vector operations if \p BlockInMask is non-null. Use \p State to translate given VPValues to IR values in the vectorized loop.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:489

Parameters

llvm::Instruction* Instr
llvm::VPTransformState& State
llvm::VPValue* Addr
llvm::VPValue* BlockInMask = nullptr

void vectorizeMemoryInstruction(
    llvm::Instruction* Instr,
    llvm::VPTransformState& State,
    llvm::VPValue* Addr,
    llvm::VPValue* BlockInMask = nullptr)

Description

Vectorize Load and Store instructions with the base address given in \p Addr, optionally masking the vector operations if \p BlockInMask is non-null. Use \p State to translate given VPValues to IR values in the vectorized loop.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:496

Parameters

llvm::Instruction* Instr
llvm::VPTransformState& State
llvm::VPValue* Addr
llvm::VPValue* BlockInMask = nullptr

void widenGEP(
    llvm::GetElementPtrInst* GEP,
    unsigned int UF,
    unsigned int VF,
    bool IsPtrLoopInvariant,
    llvm::SmallBitVector& IsIndexLoopInvariant)

Description

Vectorize a single GetElementPtrInst based on information gathered and decisions taken during planning.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:433

Parameters

llvm::GetElementPtrInst* GEP
unsigned int UF
unsigned int VF
bool IsPtrLoopInvariant
llvm::SmallBitVector& IsIndexLoopInvariant

void widenInstruction(llvm::Instruction& I)

Description

Widen a single instruction within the innermost loop.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:418

Parameters

llvm::Instruction& I

void widenIntOrFpInduction(
    llvm::PHINode* IV,
    llvm::TruncInst* Trunc = nullptr)

Description

Widen an integer or floating-point induction variable \p IV. If \p Trunc is provided, the integer induction variable will first be truncated to the corresponding type.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:451

Parameters

llvm::PHINode* IV
llvm::TruncInst* Trunc = nullptr

void widenPHIInstruction(llvm::Instruction* PN,
                         unsigned int UF,
                         unsigned int VF)

Description

Vectorize a single PHINode in a block. This method handles the induction variable canonicalization. It supports both VF = 1 for unrolled loops and arbitrary length vectors.

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:439

Parameters

llvm::Instruction* PN
unsigned int UF
unsigned int VF

virtual ~InnerLoopVectorizer()

Declared at: llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:411