blob: a7d6609f8c569ac345a2b2f462d24c6de6eb5d15 [file] [log] [blame]
//===- LoopVectorizationPlanner.h - Planner for LoopVectorization ---------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file provides a LoopVectorizationPlanner class.
/// InnerLoopVectorizer vectorizes loops which contain only one basic
/// LoopVectorizationPlanner - drives the vectorization process after having
/// passed Legality checks.
/// The planner builds and optimizes the Vectorization Plans which record the
/// decisions how to vectorize the given loop. In particular, represent the
/// control-flow of the vectorized version, the replication of instructions that
/// are to be scalarized, and interleave access groups.
///
/// Also provides a VPlan-based builder utility analogous to IRBuilder.
/// It provides an instruction-level API for generating VPInstructions while
/// abstracting away the Recipe manipulation details.
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
#define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H
#include "VPlan.h"
namespace llvm {
class LoopInfo;
class LoopVectorizationLegality;
class LoopVectorizationCostModel;
class PredicatedScalarEvolution;
class LoopVectorizationRequirements;
class LoopVectorizeHints;
class OptimizationRemarkEmitter;
class TargetTransformInfo;
class TargetLibraryInfo;
class VPRecipeBuilder;
/// VPlan-based builder utility analogous to IRBuilder.
class VPBuilder {
VPBasicBlock *BB = nullptr;
VPBasicBlock::iterator InsertPt = VPBasicBlock::iterator();
VPInstruction *createInstruction(unsigned Opcode,
ArrayRef<VPValue *> Operands) {
VPInstruction *Instr = new VPInstruction(Opcode, Operands);
if (BB)
BB->insert(Instr, InsertPt);
return Instr;
}
VPInstruction *createInstruction(unsigned Opcode,
std::initializer_list<VPValue *> Operands) {
return createInstruction(Opcode, ArrayRef<VPValue *>(Operands));
}
public:
VPBuilder() {}
/// Clear the insertion point: created instructions will not be inserted into
/// a block.
void clearInsertionPoint() {
BB = nullptr;
InsertPt = VPBasicBlock::iterator();
}
VPBasicBlock *getInsertBlock() const { return BB; }
VPBasicBlock::iterator getInsertPoint() const { return InsertPt; }
/// InsertPoint - A saved insertion point.
class VPInsertPoint {
VPBasicBlock *Block = nullptr;
VPBasicBlock::iterator Point;
public:
/// Creates a new insertion point which doesn't point to anything.
VPInsertPoint() = default;
/// Creates a new insertion point at the given location.
VPInsertPoint(VPBasicBlock *InsertBlock, VPBasicBlock::iterator InsertPoint)
: Block(InsertBlock), Point(InsertPoint) {}
/// Returns true if this insert point is set.
bool isSet() const { return Block != nullptr; }
VPBasicBlock *getBlock() const { return Block; }
VPBasicBlock::iterator getPoint() const { return Point; }
};
/// Sets the current insert point to a previously-saved location.
void restoreIP(VPInsertPoint IP) {
if (IP.isSet())
setInsertPoint(IP.getBlock(), IP.getPoint());
else
clearInsertionPoint();
}
/// This specifies that created VPInstructions should be appended to the end
/// of the specified block.
void setInsertPoint(VPBasicBlock *TheBB) {
assert(TheBB && "Attempting to set a null insert point");
BB = TheBB;
InsertPt = BB->end();
}
/// This specifies that created instructions should be inserted at the
/// specified point.
void setInsertPoint(VPBasicBlock *TheBB, VPBasicBlock::iterator IP) {
BB = TheBB;
InsertPt = IP;
}
/// Insert and return the specified instruction.
VPInstruction *insert(VPInstruction *I) const {
BB->insert(I, InsertPt);
return I;
}
/// Create an N-ary operation with \p Opcode, \p Operands and set \p Inst as
/// its underlying Instruction.
VPValue *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
Instruction *Inst = nullptr) {
VPInstruction *NewVPInst = createInstruction(Opcode, Operands);
NewVPInst->setUnderlyingValue(Inst);
return NewVPInst;
}
VPValue *createNaryOp(unsigned Opcode,
std::initializer_list<VPValue *> Operands,
Instruction *Inst = nullptr) {
return createNaryOp(Opcode, ArrayRef<VPValue *>(Operands), Inst);
}
VPValue *createNot(VPValue *Operand) {
return createInstruction(VPInstruction::Not, {Operand});
}
VPValue *createAnd(VPValue *LHS, VPValue *RHS) {
return createInstruction(Instruction::BinaryOps::And, {LHS, RHS});
}
VPValue *createOr(VPValue *LHS, VPValue *RHS) {
return createInstruction(Instruction::BinaryOps::Or, {LHS, RHS});
}
VPValue *createSelect(VPValue *Cond, VPValue *TrueVal, VPValue *FalseVal) {
return createNaryOp(Instruction::Select, {Cond, TrueVal, FalseVal});
}
//===--------------------------------------------------------------------===//
// RAII helpers.
//===--------------------------------------------------------------------===//
/// RAII object that stores the current insertion point and restores it when
/// the object is destroyed.
class InsertPointGuard {
VPBuilder &Builder;
VPBasicBlock *Block;
VPBasicBlock::iterator Point;
public:
InsertPointGuard(VPBuilder &B)
: Builder(B), Block(B.getInsertBlock()), Point(B.getInsertPoint()) {}
InsertPointGuard(const InsertPointGuard &) = delete;
InsertPointGuard &operator=(const InsertPointGuard &) = delete;
~InsertPointGuard() { Builder.restoreIP(VPInsertPoint(Block, Point)); }
};
};
/// TODO: The following VectorizationFactor was pulled out of
/// LoopVectorizationCostModel class. LV also deals with
/// VectorizerParams::VectorizationFactor and VectorizationCostTy.
/// We need to streamline them.
/// Information about vectorization costs.
struct VectorizationFactor {
/// Vector width with best cost.
ElementCount Width;
/// Cost of the loop with that width.
InstructionCost Cost;
VectorizationFactor(ElementCount Width, InstructionCost Cost)
: Width(Width), Cost(Cost) {}
/// Width 1 means no vectorization, cost 0 means uncomputed cost.
static VectorizationFactor Disabled() {
return {ElementCount::getFixed(1), 0};
}
bool operator==(const VectorizationFactor &rhs) const {
return Width == rhs.Width && Cost == rhs.Cost;
}
bool operator!=(const VectorizationFactor &rhs) const {
return !(*this == rhs);
}
};
/// A class that represents two vectorization factors (initialized with 0 by
/// default). One for fixed-width vectorization and one for scalable
/// vectorization. This can be used by the vectorizer to choose from a range of
/// fixed and/or scalable VFs in order to find the most cost-effective VF to
/// vectorize with.
struct FixedScalableVFPair {
ElementCount FixedVF;
ElementCount ScalableVF;
FixedScalableVFPair()
: FixedVF(ElementCount::getFixed(0)),
ScalableVF(ElementCount::getScalable(0)) {}
FixedScalableVFPair(const ElementCount &Max) : FixedScalableVFPair() {
*(Max.isScalable() ? &ScalableVF : &FixedVF) = Max;
}
FixedScalableVFPair(const ElementCount &FixedVF,
const ElementCount &ScalableVF)
: FixedVF(FixedVF), ScalableVF(ScalableVF) {
assert(!FixedVF.isScalable() && ScalableVF.isScalable() &&
"Invalid scalable properties");
}
static FixedScalableVFPair getNone() { return FixedScalableVFPair(); }
/// \return true if either fixed- or scalable VF is non-zero.
explicit operator bool() const { return FixedVF || ScalableVF; }
/// \return true if either fixed- or scalable VF is a valid vector VF.
bool hasVector() const { return FixedVF.isVector() || ScalableVF.isVector(); }
};
/// Planner drives the vectorization process after having passed
/// Legality checks.
class LoopVectorizationPlanner {
/// The loop that we evaluate.
Loop *OrigLoop;
/// Loop Info analysis.
LoopInfo *LI;
/// Target Library Info.
const TargetLibraryInfo *TLI;
/// Target Transform Info.
const TargetTransformInfo *TTI;
/// The legality analysis.
LoopVectorizationLegality *Legal;
/// The profitability analysis.
LoopVectorizationCostModel &CM;
/// The interleaved access analysis.
InterleavedAccessInfo &IAI;
PredicatedScalarEvolution &PSE;
const LoopVectorizeHints &Hints;
LoopVectorizationRequirements &Requirements;
OptimizationRemarkEmitter *ORE;
SmallVector<VPlanPtr, 4> VPlans;
/// A builder used to construct the current plan.
VPBuilder Builder;
public:
LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI,
const TargetTransformInfo *TTI,
LoopVectorizationLegality *Legal,
LoopVectorizationCostModel &CM,
InterleavedAccessInfo &IAI,
PredicatedScalarEvolution &PSE,
const LoopVectorizeHints &Hints,
LoopVectorizationRequirements &Requirements,
OptimizationRemarkEmitter *ORE)
: OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM), IAI(IAI),
PSE(PSE), Hints(Hints), Requirements(Requirements), ORE(ORE) {}
/// Plan how to best vectorize, return the best VF and its cost, or None if
/// vectorization and interleaving should be avoided up front.
Optional<VectorizationFactor> plan(ElementCount UserVF, unsigned UserIC);
/// Use the VPlan-native path to plan how to best vectorize, return the best
/// VF and its cost.
VectorizationFactor planInVPlanNativePath(ElementCount UserVF);
/// Return the best VPlan for \p VF.
VPlan &getBestPlanFor(ElementCount VF) const;
/// Generate the IR code for the body of the vectorized loop according to the
/// best selected \p VF, \p UF and VPlan \p BestPlan.
void executePlan(ElementCount VF, unsigned UF, VPlan &BestPlan,
InnerLoopVectorizer &LB, DominatorTree *DT);
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void printPlans(raw_ostream &O);
#endif
/// Look through the existing plans and return true if we have one with all
/// the vectorization factors in question.
bool hasPlanWithVF(ElementCount VF) const {
return any_of(VPlans,
[&](const VPlanPtr &Plan) { return Plan->hasVF(VF); });
}
/// Test a \p Predicate on a \p Range of VF's. Return the value of applying
/// \p Predicate on Range.Start, possibly decreasing Range.End such that the
/// returned value holds for the entire \p Range.
static bool
getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate,
VFRange &Range);
protected:
/// Collect the instructions from the original loop that would be trivially
/// dead in the vectorized loop if generated.
void collectTriviallyDeadInstructions(
SmallPtrSetImpl<Instruction *> &DeadInstructions);
/// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
/// according to the information gathered by Legal when it checked if it is
/// legal to vectorize the loop.
void buildVPlans(ElementCount MinVF, ElementCount MaxVF);
private:
/// Build a VPlan according to the information gathered by Legal. \return a
/// VPlan for vectorization factors \p Range.Start and up to \p Range.End
/// exclusive, possibly decreasing \p Range.End.
VPlanPtr buildVPlan(VFRange &Range);
/// Build a VPlan using VPRecipes according to the information gather by
/// Legal. This method is only used for the legacy inner loop vectorizer.
VPlanPtr buildVPlanWithVPRecipes(
VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions,
const MapVector<Instruction *, Instruction *> &SinkAfter);
/// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
/// according to the information gathered by Legal when it checked if it is
/// legal to vectorize the loop. This method creates VPlans using VPRecipes.
void buildVPlansWithVPRecipes(ElementCount MinVF, ElementCount MaxVF);
// Adjust the recipes for reductions. For in-loop reductions the chain of
// instructions leading from the loop exit instr to the phi need to be
// converted to reductions, with one operand being vector and the other being
// the scalar reduction chain. For other reductions, a select is introduced
// between the phi and live-out recipes when folding the tail.
void adjustRecipesForReductions(VPBasicBlock *LatchVPBB, VPlanPtr &Plan,
VPRecipeBuilder &RecipeBuilder,
ElementCount MinVF);
};
} // namespace llvm
#endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H