This is an archive of the discontinued LLVM Phabricator instance.

Differential D41045

[LV] NFC patch for moving VP*Recipe class definitions from LoopVectorize.cpp to VPlan.h
ClosedPublic

Authored by hsaito on Dec 8 2017, 6:25 PM.

Details

Reviewers
mkuper
hfinkel
Commits
rG7333aa9f1601: [LV] NFC patch for moving VP*Recipe class definitions from LoopVectorize.cpp to…
rL320900: [LV] NFC patch for moving VP*Recipe class definitions from LoopVectorize.cpp to…
Summary

This is a small step forward to move VPlan stuff to where it should belong (i.e., VPlan.*) --- easy and obvious things at a time, in small increment.

  1. VP*Recipe classes in LoopVectorize.cpp are moved to VPlan.h.
  2. Many of VP*Recipe::print() and execute() definitions are still left in LoopVectorize.cpp since they refer to things declared in LoopVectorize.cpp. To be moved to VPlan.cpp at a later time.
  3. InterleaveGroup class is moved from anonymous namespace to llvm namespace. Referencing it in anonymous namespace from VPlan.h ended up in warning.

Diff Detail

Event Timeline

hsaito created this revision.Dec 8 2017, 6:25 PM
Herald added subscribers: bollu, rengolin. · View Herald TranscriptDec 8 2017, 6:25 PM
fhahn added a subscriber: fhahn.Dec 9 2017, 4:30 AM
a.elovikov added a subscriber: a.elovikov.Dec 9 2017, 1:09 PM
dcaballe added a subscriber: dcaballe.Dec 11 2017, 9:14 AM
hsaito added a comment.Dec 11 2017, 11:24 AM

All print functions except for VPInterleaveRecipe::print() can be moved to VPlan.cpp. Updating the patch

sguggill added a subscriber: sguggill.Dec 11 2017, 2:03 PM
hsaito updated this revision to Diff 126465.EditedDec 11 2017, 3:53 PM

Most of print functions moved to VPlan.cpp. VPInterleaveRecipe::print() still has to stay in LoopVectorize.cpp since InterleaveGroup class is defined there, not in a header file VPlan.cpp can include.

These print functions depend on VPlanIngredients class defined near the bottom of VPlan.h. We can't easily move it and VPlanPrinter class above Recipe class definitions. That's why they belong to VPlan.cpp.

hfinkel accepted this revision.Dec 14 2017, 5:50 PM
hfinkel added a subscriber: hfinkel.

LGTM

This revision is now accepted and ready to land.Dec 14 2017, 5:50 PM
hsaito added a comment.Dec 15 2017, 9:39 AM
In D41045#956190, @hfinkel wrote:

LGTM

Thanks, Hal.

I don't have write access to the trunk (this is my first patch submission) and thus cannot commit this myself. Would be great if someone with write access would commit this for me.

Thanks,
Hideki

Closed by commit rL320900: [LV] NFC patch for moving VP*Recipe class definitions from LoopVectorize.cpp to… (authored by hfinkel). · Explain WhyDec 15 2017, 5:13 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
lib/
Transforms/
Vectorize/
532 lines
275 lines

Diff 126254

lib/Transforms/Vectorize/LoopVectorize.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 277 Lines • ▼ Show 20 LinescreateMissedAnalysis(const char *PassName, StringRef RemarkName, Loop *TheLoop,
return R; return R;
} }
namespace { namespace {
class LoopVectorizationLegality; class LoopVectorizationLegality;
class LoopVectorizationCostModel; class LoopVectorizationCostModel;
class LoopVectorizationRequirements; class LoopVectorizationRequirements;
class VPBlendRecipe;
class VPInterleaveRecipe;
class VPReplicateRecipe;
class VPWidenIntOrFpInductionRecipe;
class VPWidenRecipe;
class VPWidenMemoryInstructionRecipe;
} // end anonymous namespace } // end anonymous namespace
/// Returns true if the given loop body has a cycle, excluding the loop /// Returns true if the given loop body has a cycle, excluding the loop
/// itself. /// itself.
static bool hasCyclesInLoopBody(const Loop &L) { static bool hasCyclesInLoopBody(const Loop &L) {
if (!L.empty()) if (!L.empty())
return true; return true;
▲ Show 20 Lines • Show All 534 Lines • ▼ Show 20 Lines
void InnerLoopVectorizer::addMetadata(ArrayRef<Value *> To, void InnerLoopVectorizer::addMetadata(ArrayRef<Value *> To,
Instruction *From) { Instruction *From) {
for (Value *V : To) { for (Value *V : To) {
if (Instruction *I = dyn_cast<Instruction>(V)) if (Instruction *I = dyn_cast<Instruction>(V))
addMetadata(I, From); addMetadata(I, From);
} }
} }
namespace { namespace llvm {
/// \brief The group of interleaved loads/stores sharing the same stride and /// \brief The group of interleaved loads/stores sharing the same stride and
/// close to each other. /// close to each other.
/// ///
/// Each member in this group has an index starting from 0, and the largest /// Each member in this group has an index starting from 0, and the largest
/// index should be less than interleaved factor, which is equal to the absolute /// index should be less than interleaved factor, which is equal to the absolute
/// value of the access's stride. /// value of the access's stride.
/// ///
▲ Show 20 Lines • Show All 121 Lines • ▼ Show 20 Linesprivate:
// %add = add i32 %even // Use of %even // %add = add i32 %even // Use of %even
// %odd = load i32 // %odd = load i32
// //
// store i32 %even // store i32 %even
// %odd = add i32 // Def of %odd // %odd = add i32 // Def of %odd
// store i32 %odd // Insert Position // store i32 %odd // Insert Position
Instruction *InsertPos; Instruction *InsertPos;
}; };
} // end namespace llvm
namespace {
/// \brief Drive the analysis of interleaved memory accesses in the loop. /// \brief Drive the analysis of interleaved memory accesses in the loop.
/// ///
/// Use this class to analyze interleaved accesses only when we can vectorize /// Use this class to analyze interleaved accesses only when we can vectorize
/// a loop. Otherwise it's meaningless to do analysis as the vectorization /// a loop. Otherwise it's meaningless to do analysis as the vectorization
/// on interleaved accesses is unsafe. /// on interleaved accesses is unsafe.
/// ///
/// The analysis collects interleave groups and records the relationships /// The analysis collects interleave groups and records the relationships
▲ Show 20 Lines • Show All 6,677 Lines • ▼ Show 20 Lines if (!IsUnrollMetadata) {
MDs.push_back(DisableNode); MDs.push_back(DisableNode);
MDNode *NewLoopID = MDNode::get(Context, MDs); MDNode *NewLoopID = MDNode::get(Context, MDs);
// Set operand 0 to refer to the loop id itself. // Set operand 0 to refer to the loop id itself.
NewLoopID->replaceOperandWith(0, NewLoopID); NewLoopID->replaceOperandWith(0, NewLoopID);
L->setLoopID(NewLoopID); L->setLoopID(NewLoopID);
} }
} }
namespace {
/// VPWidenRecipe is a recipe for producing a copy of vector type for each
/// Instruction in its ingredients independently, in order. This recipe covers
/// most of the traditional vectorization cases where each ingredient transforms
/// into a vectorized version of itself.
class VPWidenRecipe : public VPRecipeBase {
private:
/// Hold the ingredients by pointing to their original BasicBlock location.
BasicBlock::iterator Begin;
BasicBlock::iterator End;
public:
VPWidenRecipe(Instruction *I) : VPRecipeBase(VPWidenSC) {
End = I->getIterator();
Begin = End++;
}
~VPWidenRecipe() override = default;
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPWidenSC;
}
/// Produce widened copies of all Ingredients.
void execute(VPTransformState &State) override {
for (auto &Instr : make_range(Begin, End))
State.ILV->widenInstruction(Instr);
}
/// Augment the recipe to include Instr, if it lies at its End.
bool appendInstruction(Instruction *Instr) {
if (End != Instr->getIterator())
return false;
End++;
return true;
}
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override {
O << " +\n" << Indent << "\"WIDEN\\l\"";
for (auto &Instr : make_range(Begin, End))
O << " +\n" << Indent << "\" " << VPlanIngredient(&Instr) << "\\l\"";
}
};
/// A recipe for handling phi nodes of integer and floating-point inductions,
/// producing their vector and scalar values.
class VPWidenIntOrFpInductionRecipe : public VPRecipeBase {
private:
PHINode *IV;
TruncInst *Trunc;
public:
VPWidenIntOrFpInductionRecipe(PHINode *IV, TruncInst *Trunc = nullptr)
: VPRecipeBase(VPWidenIntOrFpInductionSC), IV(IV), Trunc(Trunc) {}
~VPWidenIntOrFpInductionRecipe() override = default;
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPWidenIntOrFpInductionSC;
}
/// Generate the vectorized and scalarized versions of the phi node as
/// needed by their users.
void execute(VPTransformState &State) override {
assert(!State.Instance && "Int or FP induction being replicated.");
State.ILV->widenIntOrFpInduction(IV, Trunc);
}
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override {
O << " +\n" << Indent << "\"WIDEN-INDUCTION";
if (Trunc) {
O << "\\l\"";
O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
O << " +\n" << Indent << "\" " << VPlanIngredient(Trunc) << "\\l\"";
} else
O << " " << VPlanIngredient(IV) << "\\l\"";
}
};
/// A recipe for handling all phi nodes except for integer and FP inductions.
class VPWidenPHIRecipe : public VPRecipeBase {
private:
PHINode *Phi;
public:
VPWidenPHIRecipe(PHINode *Phi) : VPRecipeBase(VPWidenPHISC), Phi(Phi) {}
~VPWidenPHIRecipe() override = default;
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPWidenPHISC;
}
/// Generate the phi/select nodes.
void execute(VPTransformState &State) override {
State.ILV->widenPHIInstruction(Phi, State.UF, State.VF);
}
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override {
O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\"";
}
};
/// A recipe for vectorizing a phi-node as a sequence of mask-based select
/// instructions.
class VPBlendRecipe : public VPRecipeBase {
private:
PHINode *Phi;
/// The blend operation is a User of a mask, if not null.
std::unique_ptr<VPUser> User;
public:
VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Masks)
: VPRecipeBase(VPBlendSC), Phi(Phi) {
assert((Phi->getNumIncomingValues() == 1 ||
Phi->getNumIncomingValues() == Masks.size()) &&
"Expected the same number of incoming values and masks");
if (!Masks.empty())
User.reset(new VPUser(Masks));
}
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPBlendSC;
}
/// Generate the phi/select nodes.
void execute(VPTransformState &State) override {
State.ILV->setDebugLocFromInst(State.Builder, Phi);
// We know that all PHIs in non-header blocks are converted into
// selects, so we don't have to worry about the insertion order and we
// can just use the builder.
// At this point we generate the predication tree. There may be
// duplications since this is a simple recursive scan, but future
// optimizations will clean it up.
unsigned NumIncoming = Phi->getNumIncomingValues();
assert((User || NumIncoming == 1) &&
"Multiple predecessors with predecessors having a full mask");
// Generate a sequence of selects of the form:
// SELECT(Mask3, In3,
// SELECT(Mask2, In2,
// ( ...)))
InnerLoopVectorizer::VectorParts Entry(State.UF);
for (unsigned In = 0; In < NumIncoming; ++In) {
for (unsigned Part = 0; Part < State.UF; ++Part) {
// We might have single edge PHIs (blocks) - use an identity
// 'select' for the first PHI operand.
Value *In0 =
State.ILV->getOrCreateVectorValue(Phi->getIncomingValue(In), Part);
if (In == 0)
Entry[Part] = In0; // Initialize with the first incoming value.
else {
// Select between the current value and the previous incoming edge
// based on the incoming mask.
Value *Cond = State.get(User->getOperand(In), Part);
Entry[Part] =
State.Builder.CreateSelect(Cond, In0, Entry[Part], "predphi");
}
}
}
for (unsigned Part = 0; Part < State.UF; ++Part)
State.ValueMap.setVectorValue(Phi, Part, Entry[Part]);
}
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override {
O << " +\n" << Indent << "\"BLEND ";
Phi->printAsOperand(O, false);
O << " =";
if (!User) {
// Not a User of any mask: not really blending, this is a
// single-predecessor phi.
O << " ";
Phi->getIncomingValue(0)->printAsOperand(O, false);
} else {
for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
O << " ";
Phi->getIncomingValue(I)->printAsOperand(O, false);
O << "/";
User->getOperand(I)->printAsOperand(O);
}
}
O << "\\l\"";
}
};
/// VPInterleaveRecipe is a recipe for transforming an interleave group of load
/// or stores into one wide load/store and shuffles.
class VPInterleaveRecipe : public VPRecipeBase {
private:
const InterleaveGroup *IG;
public:
VPInterleaveRecipe(const InterleaveGroup *IG)
: VPRecipeBase(VPInterleaveSC), IG(IG) {}
~VPInterleaveRecipe() override = default;
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPInterleaveSC;
}
/// Generate the wide load or store, and shuffles.
void execute(VPTransformState &State) override {
assert(!State.Instance && "Interleave group being replicated.");
State.ILV->vectorizeInterleaveGroup(IG->getInsertPos());
}
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override;
const InterleaveGroup *getInterleaveGroup() { return IG; }
};
/// VPReplicateRecipe replicates a given instruction producing multiple scalar
/// copies of the original scalar type, one per lane, instead of producing a
/// single copy of widened type for all lanes. If the instruction is known to be
/// uniform only one copy, per lane zero, will be generated.
class VPReplicateRecipe : public VPRecipeBase {
private:
/// The instruction being replicated.
Instruction *Ingredient;
/// Indicator if only a single replica per lane is needed.
bool IsUniform;
/// Indicator if the replicas are also predicated.
bool IsPredicated;
/// Indicator if the scalar values should also be packed into a vector.
bool AlsoPack;
public:
VPReplicateRecipe(Instruction *I, bool IsUniform, bool IsPredicated = false)
: VPRecipeBase(VPReplicateSC), Ingredient(I), IsUniform(IsUniform),
IsPredicated(IsPredicated) {
// Retain the previous behavior of predicateInstructions(), where an
// insert-element of a predicated instruction got hoisted into the
// predicated basic block iff it was its only user. This is achieved by
// having predicated instructions also pack their values into a vector by
// default unless they have a replicated user which uses their scalar value.
AlsoPack = IsPredicated && !I->use_empty();
}
~VPReplicateRecipe() override = default;
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPReplicateSC;
}
/// Generate replicas of the desired Ingredient. Replicas will be generated
/// for all parts and lanes unless a specific part and lane are specified in
/// the \p State.
void execute(VPTransformState &State) override;
void setAlsoPack(bool Pack) { AlsoPack = Pack; }
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override {
O << " +\n"
<< Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
<< VPlanIngredient(Ingredient);
if (AlsoPack)
O << " (S->V)";
O << "\\l\"";
}
};
/// A recipe for generating conditional branches on the bits of a mask.
class VPBranchOnMaskRecipe : public VPRecipeBase {
private:
std::unique_ptr<VPUser> User;
public:
VPBranchOnMaskRecipe(VPValue *BlockInMask) : VPRecipeBase(VPBranchOnMaskSC) {
if (BlockInMask) // nullptr means all-one mask.
User.reset(new VPUser({BlockInMask}));
}
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPBranchOnMaskSC;
}
/// Generate the extraction of the appropriate bit from the block mask and the
/// conditional branch.
void execute(VPTransformState &State) override;
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override {
O << " +\n" << Indent << "\"BRANCH-ON-MASK ";
if (User)
O << *User->getOperand(0);
else
O << " All-One";
O << "\\l\"";
}
};
/// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
/// control converges back from a Branch-on-Mask. The phi nodes are needed in
/// order to merge values that are set under such a branch and feed their uses.
/// The phi nodes can be scalar or vector depending on the users of the value.
/// This recipe works in concert with VPBranchOnMaskRecipe.
class VPPredInstPHIRecipe : public VPRecipeBase {
private:
Instruction *PredInst;
public:
/// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
/// nodes after merging back from a Branch-on-Mask.
VPPredInstPHIRecipe(Instruction *PredInst)
: VPRecipeBase(VPPredInstPHISC), PredInst(PredInst) {}
~VPPredInstPHIRecipe() override = default;
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPPredInstPHISC;
}
/// Generates phi nodes for live-outs as needed to retain SSA form.
void execute(VPTransformState &State) override;
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override {
O << " +\n"
<< Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst)
<< "\\l\"";
}
};
/// A Recipe for widening load/store operations.
/// TODO: We currently execute only per-part unless a specific instance is
/// provided.
class VPWidenMemoryInstructionRecipe : public VPRecipeBase {
private:
Instruction &Instr;
std::unique_ptr<VPUser> User;
public:
VPWidenMemoryInstructionRecipe(Instruction &Instr, VPValue *Mask)
: VPRecipeBase(VPWidenMemoryInstructionSC), Instr(Instr) {
if (Mask) // Create a VPInstruction to register as a user of the mask.
User.reset(new VPUser({Mask}));
}
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPWidenMemoryInstructionSC;
}
/// Generate the wide load/store.
void execute(VPTransformState &State) override {
if (!User)
return State.ILV->vectorizeMemoryInstruction(&Instr);
// Last (and currently only) operand is a mask.
InnerLoopVectorizer::VectorParts MaskValues(State.UF);
VPValue *Mask = User->getOperand(User->getNumOperands() - 1);
for (unsigned Part = 0; Part < State.UF; ++Part)
MaskValues[Part] = State.get(Mask, Part);
State.ILV->vectorizeMemoryInstruction(&Instr, &MaskValues);
}
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override {
O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
if (User) {
O << ", ";
User->getOperand(0)->printAsOperand(O);
}
O << "\\l\"";
}
};
} // end anonymous namespace
bool LoopVectorizationPlanner::getDecisionAndClampRange( bool LoopVectorizationPlanner::getDecisionAndClampRange(
const std::function<bool(unsigned)> &Predicate, VFRange &Range) { const std::function<bool(unsigned)> &Predicate, VFRange &Range) {
assert(Range.End > Range.Start && "Trying to test an empty VF range."); assert(Range.End > Range.Start && "Trying to test an empty VF range.");
bool PredicateAtRangeStart = Predicate(Range.Start); bool PredicateAtRangeStart = Predicate(Range.Start);
for (unsigned TmpVF = Range.Start * 2; TmpVF < Range.End; TmpVF *= 2) for (unsigned TmpVF = Range.Start * 2; TmpVF < Range.End; TmpVF *= 2)
if (Predicate(TmpVF) != PredicateAtRangeStart) { if (Predicate(TmpVF) != PredicateAtRangeStart) {
Range.End = TmpVF; Range.End = TmpVF;
▲ Show 20 Lines • Show All 536 Lines • ▼ Show 20 LinesLoopVectorizationPlanner::buildVPlan(VFRange &Range,
} }
RSO << "},UF>=1"; RSO << "},UF>=1";
RSO.flush(); RSO.flush();
Plan->setName(PlanName); Plan->setName(PlanName);
return Plan; return Plan;
} }
void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent) const {
O << " +\n" << Indent << "\"WIDEN\\l\"";
for (auto &Instr : make_range(Begin, End))
O << " +\n" << Indent << "\" " << VPlanIngredient(&Instr) << "\\l\"";
}
void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O,
const Twine &Indent) const {
O << " +\n" << Indent << "\"WIDEN-INDUCTION";
if (Trunc) {
O << "\\l\"";
O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
O << " +\n" << Indent << "\" " << VPlanIngredient(Trunc) << "\\l\"";
} else
O << " " << VPlanIngredient(IV) << "\\l\"";
}
void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\"";
}
void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent) const {
O << " +\n" << Indent << "\"BLEND ";
Phi->printAsOperand(O, false);
O << " =";
if (!User) {
// Not a User of any mask: not really blending, this is a
// single-predecessor phi.
O << " ";
Phi->getIncomingValue(0)->printAsOperand(O, false);
} else {
for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
O << " ";
Phi->getIncomingValue(I)->printAsOperand(O, false);
O << "/";
User->getOperand(I)->printAsOperand(O);
}
}
O << "\\l\"";
}
void VPInterleaveRecipe::print(raw_ostream &O, const Twine &Indent) const { void VPInterleaveRecipe::print(raw_ostream &O, const Twine &Indent) const {
O << " +\n" O << " +\n"
<< Indent << "\"INTERLEAVE-GROUP with factor " << IG->getFactor() << " at "; << Indent << "\"INTERLEAVE-GROUP with factor " << IG->getFactor() << " at ";
IG->getInsertPos()->printAsOperand(O, false); IG->getInsertPos()->printAsOperand(O, false);
O << "\\l\""; O << "\\l\"";
for (unsigned i = 0; i < IG->getFactor(); ++i) for (unsigned i = 0; i < IG->getFactor(); ++i)
if (Instruction *I = IG->getMember(i)) if (Instruction *I = IG->getMember(i))
O << " +\n" O << " +\n"
<< Indent << "\" " << VPlanIngredient(I) << " " << i << "\\l\""; << Indent << "\" " << VPlanIngredient(I) << " " << i << "\\l\"";
} }
void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent) const {
O << " +\n"
<< Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
<< VPlanIngredient(Ingredient);
if (AlsoPack)
O << " (S->V)";
O << "\\l\"";
}
void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
O << " +\n"
<< Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst)
<< "\\l\"";
}
void VPWidenMemoryInstructionRecipe::print(raw_ostream &O,
const Twine &Indent) const {
O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
if (User) {
O << ", ";
User->getOperand(0)->printAsOperand(O);
}
O << "\\l\"";
}
void VPWidenRecipe::execute(VPTransformState &State) {
for (auto &Instr : make_range(Begin, End))
State.ILV->widenInstruction(Instr);
}
void VPWidenIntOrFpInductionRecipe::execute(VPTransformState &State) {
assert(!State.Instance && "Int or FP induction being replicated.");
State.ILV->widenIntOrFpInduction(IV, Trunc);
}
void VPWidenPHIRecipe::execute(VPTransformState &State) {
State.ILV->widenPHIInstruction(Phi, State.UF, State.VF);
}
void VPBlendRecipe::execute(VPTransformState &State) {
State.ILV->setDebugLocFromInst(State.Builder, Phi);
// We know that all PHIs in non-header blocks are converted into
// selects, so we don't have to worry about the insertion order and we
// can just use the builder.
// At this point we generate the predication tree. There may be
// duplications since this is a simple recursive scan, but future
// optimizations will clean it up.
unsigned NumIncoming = Phi->getNumIncomingValues();
assert((User || NumIncoming == 1) &&
"Multiple predecessors with predecessors having a full mask");
// Generate a sequence of selects of the form:
// SELECT(Mask3, In3,
// SELECT(Mask2, In2,
// ( ...)))
InnerLoopVectorizer::VectorParts Entry(State.UF);
for (unsigned In = 0; In < NumIncoming; ++In) {
for (unsigned Part = 0; Part < State.UF; ++Part) {
// We might have single edge PHIs (blocks) - use an identity
// 'select' for the first PHI operand.
Value *In0 =
State.ILV->getOrCreateVectorValue(Phi->getIncomingValue(In), Part);
if (In == 0)
Entry[Part] = In0; // Initialize with the first incoming value.
else {
// Select between the current value and the previous incoming edge
// based on the incoming mask.
Value *Cond = State.get(User->getOperand(In), Part);
Entry[Part] =
State.Builder.CreateSelect(Cond, In0, Entry[Part], "predphi");
}
}
}
for (unsigned Part = 0; Part < State.UF; ++Part)
State.ValueMap.setVectorValue(Phi, Part, Entry[Part]);
}
void VPInterleaveRecipe::execute(VPTransformState &State) {
assert(!State.Instance && "Interleave group being replicated.");
State.ILV->vectorizeInterleaveGroup(IG->getInsertPos());
}
void VPReplicateRecipe::execute(VPTransformState &State) { void VPReplicateRecipe::execute(VPTransformState &State) {
if (State.Instance) { // Generate a single instance. if (State.Instance) { // Generate a single instance.
State.ILV->scalarizeInstruction(Ingredient, *State.Instance, IsPredicated); State.ILV->scalarizeInstruction(Ingredient, *State.Instance, IsPredicated);
// Insert scalar instance packing it into a vector. // Insert scalar instance packing it into a vector.
if (AlsoPack && State.VF > 1) { if (AlsoPack && State.VF > 1) {
// If we're constructing lane 0, initialize to start from undef. // If we're constructing lane 0, initialize to start from undef.
if (State.Instance->Lane == 0) { if (State.Instance->Lane == 0) {
Value *Undef = Value *Undef =
▲ Show 20 Lines • Show All 67 Lines • ▼ Show 20 Lines if (State.ValueMap.hasVectorValue(PredInst, Part)) {
Type *PredInstType = PredInst->getType(); Type *PredInstType = PredInst->getType();
PHINode *Phi = State.Builder.CreatePHI(PredInstType, 2); PHINode *Phi = State.Builder.CreatePHI(PredInstType, 2);
Phi->addIncoming(UndefValue::get(ScalarPredInst->getType()), PredicatingBB); Phi->addIncoming(UndefValue::get(ScalarPredInst->getType()), PredicatingBB);
Phi->addIncoming(ScalarPredInst, PredicatedBB); Phi->addIncoming(ScalarPredInst, PredicatedBB);
State.ValueMap.resetScalarValue(PredInst, *State.Instance, Phi); State.ValueMap.resetScalarValue(PredInst, *State.Instance, Phi);
} }
} }
void VPWidenMemoryInstructionRecipe::execute(VPTransformState &State) {
if (!User)
return State.ILV->vectorizeMemoryInstruction(&Instr);
// Last (and currently only) operand is a mask.
InnerLoopVectorizer::VectorParts MaskValues(State.UF);
VPValue *Mask = User->getOperand(User->getNumOperands() - 1);
for (unsigned Part = 0; Part < State.UF; ++Part)
MaskValues[Part] = State.get(Mask, Part);
State.ILV->vectorizeMemoryInstruction(&Instr, &MaskValues);
}
bool LoopVectorizePass::processLoop(Loop *L) { bool LoopVectorizePass::processLoop(Loop *L) {
assert(L->empty() && "Only process inner loops."); assert(L->empty() && "Only process inner loops.");
#ifndef NDEBUG #ifndef NDEBUG
const std::string DebugLocStr = getDebugLocString(L); const std::string DebugLocStr = getDebugLocString(L);
#endif /* NDEBUG */ #endif /* NDEBUG */
DEBUG(dbgs() << "\nLV: Checking a loop in \"" DEBUG(dbgs() << "\nLV: Checking a loop in \""
▲ Show 20 Lines • Show All 346 Lines • Show Last 20 Lines

lib/Transforms/Vectorize/VPlan.h

Show First 20 Lines • Show All 48 Lines • ▼ Show 20 Lines
class LoopVectorizationCostModel; class LoopVectorizationCostModel;
} // namespace } // namespace
namespace llvm { namespace llvm {
class BasicBlock; class BasicBlock;
class DominatorTree; class DominatorTree;
class InnerLoopVectorizer; class InnerLoopVectorizer;
class InterleaveGroup;
class LoopInfo; class LoopInfo;
class raw_ostream; class raw_ostream;
class Value; class Value;
class VPBasicBlock; class VPBasicBlock;
class VPRegionBlock; class VPRegionBlock;
/// In what follows, the term "input IR" refers to code that is fed into the /// In what follows, the term "input IR" refers to code that is fed into the
/// vectorizer whereas the term "output IR" refers to code that is generated by /// vectorizer whereas the term "output IR" refers to code that is generated by
▲ Show 20 Lines • Show All 516 Lines • ▼ Show 20 Linespublic:
/// Print the Recipe. /// Print the Recipe.
void print(raw_ostream &O, const Twine &Indent) const override; void print(raw_ostream &O, const Twine &Indent) const override;
/// Print the VPInstruction. /// Print the VPInstruction.
void print(raw_ostream &O) const; void print(raw_ostream &O) const;
}; };
/// VPWidenRecipe is a recipe for producing a copy of vector type for each
/// Instruction in its ingredients independently, in order. This recipe covers
/// most of the traditional vectorization cases where each ingredient transforms
/// into a vectorized version of itself.
class VPWidenRecipe : public VPRecipeBase {
private:
/// Hold the ingredients by pointing to their original BasicBlock location.
BasicBlock::iterator Begin;
BasicBlock::iterator End;
public:
VPWidenRecipe(Instruction *I) : VPRecipeBase(VPWidenSC) {
End = I->getIterator();
Begin = End++;
}
~VPWidenRecipe() override = default;
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPWidenSC;
}
/// Produce widened copies of all Ingredients.
void execute(VPTransformState &State) override;
/// Augment the recipe to include Instr, if it lies at its End.
bool appendInstruction(Instruction *Instr) {
if (End != Instr->getIterator())
return false;
End++;
return true;
}
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override;
};
/// A recipe for handling phi nodes of integer and floating-point inductions,
/// producing their vector and scalar values.
class VPWidenIntOrFpInductionRecipe : public VPRecipeBase {
private:
PHINode *IV;
TruncInst *Trunc;
public:
VPWidenIntOrFpInductionRecipe(PHINode *IV, TruncInst *Trunc = nullptr)
: VPRecipeBase(VPWidenIntOrFpInductionSC), IV(IV), Trunc(Trunc) {}
~VPWidenIntOrFpInductionRecipe() override = default;
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPWidenIntOrFpInductionSC;
}
/// Generate the vectorized and scalarized versions of the phi node as
/// needed by their users.
void execute(VPTransformState &State) override;
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override;
};
/// A recipe for handling all phi nodes except for integer and FP inductions.
class VPWidenPHIRecipe : public VPRecipeBase {
private:
PHINode *Phi;
public:
VPWidenPHIRecipe(PHINode *Phi) : VPRecipeBase(VPWidenPHISC), Phi(Phi) {}
~VPWidenPHIRecipe() override = default;
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPWidenPHISC;
}
/// Generate the phi/select nodes.
void execute(VPTransformState &State) override;
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override;
};
/// A recipe for vectorizing a phi-node as a sequence of mask-based select
/// instructions.
class VPBlendRecipe : public VPRecipeBase {
private:
PHINode *Phi;
/// The blend operation is a User of a mask, if not null.
std::unique_ptr<VPUser> User;
public:
VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Masks)
: VPRecipeBase(VPBlendSC), Phi(Phi) {
assert((Phi->getNumIncomingValues() == 1 ||
Phi->getNumIncomingValues() == Masks.size()) &&
"Expected the same number of incoming values and masks");
if (!Masks.empty())
User.reset(new VPUser(Masks));
}
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPBlendSC;
}
/// Generate the phi/select nodes.
void execute(VPTransformState &State) override;
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override;
};
/// VPInterleaveRecipe is a recipe for transforming an interleave group of load
/// or stores into one wide load/store and shuffles.
class VPInterleaveRecipe : public VPRecipeBase {
private:
const InterleaveGroup *IG;
public:
VPInterleaveRecipe(const InterleaveGroup *IG)
: VPRecipeBase(VPInterleaveSC), IG(IG) {}
~VPInterleaveRecipe() override = default;
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPInterleaveSC;
}
/// Generate the wide load or store, and shuffles.
void execute(VPTransformState &State) override;
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override;
const InterleaveGroup *getInterleaveGroup() { return IG; }
};
/// VPReplicateRecipe replicates a given instruction producing multiple scalar
/// copies of the original scalar type, one per lane, instead of producing a
/// single copy of widened type for all lanes. If the instruction is known to be
/// uniform only one copy, per lane zero, will be generated.
class VPReplicateRecipe : public VPRecipeBase {
private:
/// The instruction being replicated.
Instruction *Ingredient;
/// Indicator if only a single replica per lane is needed.
bool IsUniform;
/// Indicator if the replicas are also predicated.
bool IsPredicated;
/// Indicator if the scalar values should also be packed into a vector.
bool AlsoPack;
public:
VPReplicateRecipe(Instruction *I, bool IsUniform, bool IsPredicated = false)
: VPRecipeBase(VPReplicateSC), Ingredient(I), IsUniform(IsUniform),
IsPredicated(IsPredicated) {
// Retain the previous behavior of predicateInstructions(), where an
// insert-element of a predicated instruction got hoisted into the
// predicated basic block iff it was its only user. This is achieved by
// having predicated instructions also pack their values into a vector by
// default unless they have a replicated user which uses their scalar value.
AlsoPack = IsPredicated && !I->use_empty();
}
~VPReplicateRecipe() override = default;
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPReplicateSC;
}
/// Generate replicas of the desired Ingredient. Replicas will be generated
/// for all parts and lanes unless a specific part and lane are specified in
/// the \p State.
void execute(VPTransformState &State) override;
void setAlsoPack(bool Pack) { AlsoPack = Pack; }
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override;
};
/// A recipe for generating conditional branches on the bits of a mask.
class VPBranchOnMaskRecipe : public VPRecipeBase {
private:
std::unique_ptr<VPUser> User;
public:
VPBranchOnMaskRecipe(VPValue *BlockInMask) : VPRecipeBase(VPBranchOnMaskSC) {
if (BlockInMask) // nullptr means all-one mask.
User.reset(new VPUser({BlockInMask}));
}
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPBranchOnMaskSC;
}
/// Generate the extraction of the appropriate bit from the block mask and the
/// conditional branch.
void execute(VPTransformState &State) override;
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override {
O << " +\n" << Indent << "\"BRANCH-ON-MASK ";
if (User)
O << *User->getOperand(0);
else
O << " All-One";
O << "\\l\"";
}
};
/// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
/// control converges back from a Branch-on-Mask. The phi nodes are needed in
/// order to merge values that are set under such a branch and feed their uses.
/// The phi nodes can be scalar or vector depending on the users of the value.
/// This recipe works in concert with VPBranchOnMaskRecipe.
class VPPredInstPHIRecipe : public VPRecipeBase {
private:
Instruction *PredInst;
public:
/// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
/// nodes after merging back from a Branch-on-Mask.
VPPredInstPHIRecipe(Instruction *PredInst)
: VPRecipeBase(VPPredInstPHISC), PredInst(PredInst) {}
~VPPredInstPHIRecipe() override = default;
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPPredInstPHISC;
}
/// Generates phi nodes for live-outs as needed to retain SSA form.
void execute(VPTransformState &State) override;
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override;
};
/// A Recipe for widening load/store operations.
/// TODO: We currently execute only per-part unless a specific instance is
/// provided.
class VPWidenMemoryInstructionRecipe : public VPRecipeBase {
private:
Instruction &Instr;
std::unique_ptr<VPUser> User;
public:
VPWidenMemoryInstructionRecipe(Instruction &Instr, VPValue *Mask)
: VPRecipeBase(VPWidenMemoryInstructionSC), Instr(Instr) {
if (Mask) // Create a VPInstruction to register as a user of the mask.
User.reset(new VPUser({Mask}));
}
/// Method to support type inquiry through isa, cast, and dyn_cast.
static inline bool classof(const VPRecipeBase *V) {
return V->getVPRecipeID() == VPRecipeBase::VPWidenMemoryInstructionSC;
}
/// Generate the wide load/store.
void execute(VPTransformState &State) override;
/// Print the recipe.
void print(raw_ostream &O, const Twine &Indent) const override;
};
/// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
/// holds a sequence of zero or more VPRecipe's each representing a sequence of /// holds a sequence of zero or more VPRecipe's each representing a sequence of
/// output IR instructions. /// output IR instructions.
class VPBasicBlock : public VPBlockBase { class VPBasicBlock : public VPBlockBase {
public: public:
using RecipeListTy = iplist<VPRecipeBase>; using RecipeListTy = iplist<VPRecipeBase>;
private: private:
▲ Show 20 Lines • Show All 323 Lines • Show Last 20 Lines