Go to the documentation of this file.
27 GetIntOrFpInductionDescriptor,
33 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
35 auto EndIter =
Term ?
Term->getIterator() : VPBB->end();
40 VPValue *VPV = Ingredient.getVPSingleValue();
42 if (DeadInstructions.
count(Inst)) {
45 Ingredient.eraseFromParent();
50 if (
auto *VPPhi = dyn_cast<VPWidenPHIRecipe>(&Ingredient)) {
51 auto *Phi = cast<PHINode>(VPPhi->getUnderlyingValue());
52 if (
const auto *II = GetIntOrFpInductionDescriptor(Phi)) {
53 VPValue *Start = Plan->getOrAddVPValue(II->getStartValue());
59 Plan->addVPValue(Phi, VPPhi);
63 assert(isa<VPInstruction>(&Ingredient) &&
64 "only VPInstructions expected here");
65 assert(!isa<PHINode>(Inst) &&
"phis should be handled above");
70 nullptr ,
false ,
false );
74 Plan->getOrAddVPValue(
Store->getValueOperand()),
nullptr ,
78 GEP, Plan->mapToVPValues(
GEP->operands()), OrigLoop);
79 }
else if (
CallInst *CI = dyn_cast<CallInst>(Inst)) {
83 }
else if (
SelectInst *
SI = dyn_cast<SelectInst>(Inst)) {
87 *
SI, Plan->mapToVPValues(
SI->operands()), InvariantCond);
99 "Only recpies with zero or one defined values expected");
100 Ingredient.eraseFromParent();
101 Plan->removeVPValueFor(Inst);
103 Plan->addVPValue(Inst,
Def);
111 bool Changed =
false;
115 for (
VPRegionBlock *VPR : VPBlockUtils::blocksOnly<VPRegionBlock>(Iter)) {
117 if (!VPR->isReplicator() || EntryVPBB->
getSuccessors().size() != 2)
122 for (
auto &Recipe : *VPBB) {
124 if (
auto *
Def =
Op->getDefiningRecipe())
125 WorkList.
insert(std::make_pair(VPBB,
Def));
131 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
134 std::tie(SinkTo, SinkCandidate) = WorkList[
I];
135 if (SinkCandidate->
getParent() == SinkTo ||
139 if (
auto *RepR = dyn_cast<VPReplicateRecipe>(SinkCandidate)) {
140 if (!ScalarVFOnly && RepR->isUniform())
142 }
else if (!isa<VPScalarIVStepsRecipe>(SinkCandidate))
145 bool NeedsDuplicating =
false;
150 auto CanSinkWithUser = [SinkTo, &NeedsDuplicating,
151 SinkCandidate](
VPUser *U) {
152 auto *UI = dyn_cast<VPRecipeBase>(U);
155 if (UI->getParent() == SinkTo)
160 return NeedsDuplicating && isa<VPReplicateRecipe>(SinkCandidate);
165 if (NeedsDuplicating) {
169 cast<VPReplicateRecipe>(SinkCandidate)->getUnderlyingValue());
174 Clone->insertBefore(SinkCandidate);
176 auto *UI = cast<VPRecipeBase>(U);
177 if (UI->getParent() == SinkTo)
180 for (
unsigned Idx = 0; Idx != UI->getNumOperands(); Idx++) {
183 UI->setOperand(Idx, Clone);
189 if (
auto *
Def =
Op->getDefiningRecipe())
190 WorkList.
insert(std::make_pair(SinkTo,
Def));
199 auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry());
200 if (!EntryBB || EntryBB->size() != 1 ||
201 !isa<VPBranchOnMaskRecipe>(EntryBB->begin()))
204 return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0);
209 auto *EntryBB = cast<VPBasicBlock>(R->getEntry());
210 if (EntryBB->getNumSuccessors() != 2)
213 auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]);
214 auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]);
215 if (!Succ0 || !Succ1)
218 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
220 if (Succ0->getSingleSuccessor() == Succ1)
222 if (Succ1->getSingleSuccessor() == Succ0)
234 for (
VPRegionBlock *Region1 : VPBlockUtils::blocksOnly<VPRegionBlock>(
236 if (!Region1->isReplicator())
238 auto *MiddleBasicBlock =
239 dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());
240 if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
244 dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
245 if (!Region2 || !Region2->isReplicator())
250 if (!Mask1 || Mask1 != Mask2)
253 assert(Mask1 && Mask2 &&
"both region must have conditions");
254 WorkList.push_back(Region1);
259 if (DeletedRegions.
contains(Region1))
261 auto *MiddleBasicBlock = cast<VPBasicBlock>(Region1->getSingleSuccessor());
262 auto *Region2 = cast<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
266 if (!Then1 || !Then2)
285 cast<VPPredInstPHIRecipe>(&Phi1ToMove)->getOperand(0);
286 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue();
288 auto *UI = dyn_cast<VPRecipeBase>(U);
289 if (!UI || UI->getParent() != Then2)
291 for (
unsigned I = 0,
E = U->getNumOperands();
I !=
E; ++
I) {
292 if (Phi1ToMoveV != U->getOperand(
I))
294 U->setOperand(
I, PredInst1);
298 Phi1ToMove.moveBefore(*Merge2, Merge2->begin());
307 DeletedRegions.
insert(Region1);
312 return !DeletedRegions.empty();
317 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
320 dyn_cast_or_null<VPBasicBlock>(VPBB->getSinglePredecessor());
321 if (PredVPBB && PredVPBB->getNumSuccessors() == 1)
322 WorkList.push_back(VPBB);
326 VPBasicBlock *PredVPBB = cast<VPBasicBlock>(VPBB->getSinglePredecessor());
328 R.moveBefore(*PredVPBB, PredVPBB->
end());
330 auto *ParentRegion = cast_or_null<VPRegionBlock>(VPBB->getParent());
331 if (ParentRegion && ParentRegion->getExiting() == VPBB)
332 ParentRegion->setExiting(PredVPBB);
333 for (
auto *Succ :
to_vector(VPBB->successors())) {
339 return !WorkList.empty();
344 auto *
IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
345 if (!
IV ||
IV->getTruncInst())
356 auto &Casts =
IV->getInductionDescriptor().getCastInsts();
360 for (
auto *U : FindMyCast->
users()) {
361 auto *UserCast = cast<VPRecipeBase>(U);
362 if (UserCast->getNumDefinedValues() == 1 &&
363 UserCast->getVPSingleValue()->getUnderlyingValue() == IRCast) {
364 FoundUserCast = UserCast;
378 WidenNewIV = dyn_cast<VPWidenCanonicalIVRecipe>(U);
388 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
390 if (!WidenOriginalIV || !WidenOriginalIV->isCanonical() ||
391 WidenOriginalIV->getScalarType() != WidenNewIV->
getScalarType())
398 if (WidenOriginalIV->needsVectorIV() ||
415 if (R.mayHaveSideEffects() ||
any_of(R.definedValues(), [](
VPValue *V) {
416 return V->getNumUsers() > 0;
429 auto *WideIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
432 if (HasOnlyVectorVFs &&
none_of(WideIV->users(), [WideIV](
VPUser *U) {
433 return U->usesScalars(WideIV);
439 Type *ResultTy = WideIV->getPHINode()->getType();
441 ResultTy = TruncI->getType();
453 HeaderVPBB->
insert(Steps, IP);
475 auto *ExpR = dyn_cast<VPExpandSCEVRecipe>(&R);
479 auto I = SCEV2VPV.
insert({ExpR->getSCEV(), ExpR});
482 ExpR->replaceAllUsesWith(
I.first->second);
483 ExpR->eraseFromParent();
499 assert(Plan.
hasVF(BestVF) &&
"BestVF is not available in Plan");
500 assert(Plan.
hasUF(BestUF) &&
"BestUF is not available in Plan");
503 auto *
Term = dyn_cast<VPInstruction>(&ExitingVPBB->
back());
520 if (TripCount->
isZero() ||
528 Term->eraseFromParent();
unsigned getOpcode() const
LLVMContext & getContext() const
This is an optimization pass for GlobalISel generic memory operations.
Canonical scalar induction phi of the vector loop.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
iplist< VPRecipeBase >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setVF(ElementCount VF)
const VPRecipeBase & back() const
Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)
Returns intrinsic ID for call.
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Represents a single loop in the control flow graph.
size_type size() const
Determine the number of elements in the SetVector.
Value * getLiveInIRValue()
Returns the underlying IR value, if this VPValue is defined outside the scope of VPlan.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
VPValue * getOrAddExternalDef(Value *V)
Get the existing or add a new external definition for V.
ReachingDefAnalysis InstSet & ToRemove
The main scalar evolution driver.
VPCanonicalIVPHIRecipe * getCanonicalIV()
Returns the canonical induction recipe of the vector loop.
The instances of the Type class are immutable: once they are created, they are never changed.
std::unique_ptr< VPlan > VPlanPtr
static constexpr ElementCount getFixed(ScalarTy MinVal)
A recipe for widening Call instructions.
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
bool hasVF(ElementCount VF)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
A struct for saving information about induction variables.
This is a concrete Recipe that models a single VPlan-level instruction.
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)
Get or create a VPValue that corresponds to the expansion of Expr.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
(vector float) vec_cmpeq(*A, *B) C
@ ICMP_ULE
unsigned less or equal
void moveBefore(VPBasicBlock &BB, iplist< VPRecipeBase >::iterator I)
Unlink this recipe and insert into BB before I.
const SCEV * createTripCountSCEV(Type *IdxTy, PredicatedScalarEvolution &PSE)
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
iterator_range< df_iterator< VPBlockDeepTraversalWrapper< VPBlockBase * > > > vp_depth_first_deep(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order while traversing t...
void replaceAllUsesWith(VPValue *New)
A Recipe for widening the canonical induction variable of the vector loop.
unsigned getNumDefinedValues() const
Returns the number of values defined by the VPDef.
unsigned getNumOperands() const
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
An efficient, type-erasing, non-owning reference to a callable.
void setOperand(unsigned I, VPValue *New)
This class represents an analyzed expression in the program.
bool mayHaveSideEffects() const
Returns true if the recipe may have side-effects.
An instruction for storing to memory.
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
VPWidenRecipe is a recipe for producing a copy of vector type its ingredient.
This is an important class for using LLVM in a threaded context.
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector valu...
A recipe for handling GEP instructions.
This class represents the LLVM 'select' instruction.
A Recipe for widening load/store operations.
A recipe for widening select instructions.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
bool insert(const value_type &X)
Insert a new element into the SetVector.
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
VPBlockBase * getSingleSuccessor() const
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
const SCEV * getConstant(ConstantInt *V)
bool isCanonical(const InductionDescriptor &ID, Type *Ty) const
Check if the induction described by ID is canonical, i.e.
Type * getType() const
All values are typed, get the type of this value.
VPBasicBlock * getParent()
An instruction for reading from memory.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
const VPBasicBlock * getEntryBasicBlock() const
bool onlyFirstLaneUsed(VPValue *Def)
Returns true if only the first lane of Def is used.
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
static ConstantInt * getTrue(LLVMContext &Context)
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
bool hasScalarVFOnly() const
Provides information about what library functions are available for the current target.
bool mayReadOrWriteMemory() const
Returns true if the recipe may read from or write to memory.
const Type * getScalarType() const
Returns the scalar type of the induction.
void insert(VPRecipeBase *Recipe, iterator InsertPt)
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
VPValue * getOperand(unsigned N) const
iv Induction Variable Users
ArrayRef< VPValue * > definedValues()
Returns an ArrayRef of the values defined by the VPDef.
const VPBasicBlock * getExitingBasicBlock() const
static const uint32_t IV[8]
auto reverse(ContainerTy &&C)
Type * getType() const
Return the LLVM type of this SCEV expression.
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
virtual bool usesScalars(const VPValue *Op) const
Returns true if the VPUser uses scalars of operand Op.
This class represents a function call, abstracting a target machine's calling convention.
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
iterator_range< iterator > phis()
Returns an iterator range over the PHI-like recipes in the block.
bool hasUF(unsigned UF) const
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
A vector that has set insertion semantics.
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
const VPBlocksTy & getSuccessors() const
Value * getUnderlyingValue()
Return the underlying Value attached to this VPValue.
bool isZero() const
Return true if the expression is a constant zero.
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
A recipe for converting the canonical IV value to the corresponding value of an IV with different sta...