29 GetIntOrFpInductionDescriptor,
35 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
37 auto EndIter = Term ? Term->getIterator() : VPBB->end();
42 VPValue *VPV = Ingredient.getVPSingleValue();
44 if (DeadInstructions.
count(Inst)) {
47 Ingredient.eraseFromParent();
52 if (
auto *VPPhi = dyn_cast<VPWidenPHIRecipe>(&Ingredient)) {
53 auto *Phi = cast<PHINode>(VPPhi->getUnderlyingValue());
54 if (
const auto *II = GetIntOrFpInductionDescriptor(Phi)) {
55 VPValue *Start = Plan->getOrAddVPValue(II->getStartValue());
61 Plan->addVPValue(Phi, VPPhi);
65 assert(isa<VPInstruction>(&Ingredient) &&
66 "only VPInstructions expected here");
67 assert(!isa<PHINode>(Inst) &&
"phis should be handled above");
69 if (
LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
72 nullptr ,
false ,
false );
73 }
else if (
StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
76 Plan->getOrAddVPValue(Store->getValueOperand()),
nullptr ,
81 }
else if (
CallInst *CI = dyn_cast<CallInst>(Inst)) {
85 }
else if (
SelectInst *
SI = dyn_cast<SelectInst>(Inst)) {
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)) {
122 for (
auto &Recipe : *VPBB) {
123 for (
VPValue *Op : Recipe.operands())
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());
173 Clone->insertBefore(SinkCandidate);
175 auto *UI = cast<VPRecipeBase>(U);
176 if (UI->getParent() == SinkTo)
179 for (
unsigned Idx = 0;
Idx != UI->getNumOperands();
Idx++) {
182 UI->setOperand(
Idx, Clone);
188 if (
auto *Def = Op->getDefiningRecipe())
189 WorkList.
insert(std::make_pair(SinkTo, Def));
198 auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry());
199 if (!EntryBB || EntryBB->size() != 1 ||
200 !isa<VPBranchOnMaskRecipe>(EntryBB->begin()))
203 return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0);
208 auto *EntryBB = cast<VPBasicBlock>(R->getEntry());
209 if (EntryBB->getNumSuccessors() != 2)
212 auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]);
213 auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]);
214 if (!Succ0 || !Succ1)
217 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
219 if (Succ0->getSingleSuccessor() == Succ1)
221 if (Succ1->getSingleSuccessor() == Succ0)
236 for (
VPRegionBlock *Region1 : VPBlockUtils::blocksOnly<VPRegionBlock>(
238 if (!Region1->isReplicator())
240 auto *MiddleBasicBlock =
241 dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());
242 if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
246 dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
247 if (!Region2 || !Region2->isReplicator())
252 if (!Mask1 || Mask1 != Mask2)
255 assert(Mask1 && Mask2 &&
"both region must have conditions");
261 if (DeletedRegions.
contains(Region1))
263 auto *MiddleBasicBlock = cast<VPBasicBlock>(Region1->getSingleSuccessor());
264 auto *Region2 = cast<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
268 if (!Then1 || !Then2)
287 cast<VPPredInstPHIRecipe>(&Phi1ToMove)->getOperand(0);
288 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue();
290 auto *UI = dyn_cast<VPRecipeBase>(U);
291 if (!UI || UI->getParent() != Then2)
293 for (
unsigned I = 0,
E = U->getNumOperands();
I !=
E; ++
I) {
294 if (Phi1ToMoveV != U->getOperand(
I))
296 U->setOperand(
I, PredInst1);
300 Phi1ToMove.moveBefore(*Merge2, Merge2->begin());
309 DeletedRegions.
insert(Region1);
314 return !DeletedRegions.
empty();
322 assert(Instr->
getParent() &&
"Predicated instruction not in any basic block");
323 auto *BlockInMask = PredRecipe->
getMask();
355 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
358 if (
auto *RepR = dyn_cast<VPReplicateRecipe>(&R)) {
359 if (RepR->isPredicated())
385 bool ShouldSimplify =
true;
386 while (ShouldSimplify) {
394 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
397 dyn_cast_or_null<VPBasicBlock>(VPBB->getSinglePredecessor());
398 if (PredVPBB && PredVPBB->getNumSuccessors() == 1)
403 VPBasicBlock *PredVPBB = cast<VPBasicBlock>(VPBB->getSinglePredecessor());
405 R.moveBefore(*PredVPBB, PredVPBB->
end());
407 auto *ParentRegion = cast_or_null<VPRegionBlock>(VPBB->getParent());
408 if (ParentRegion && ParentRegion->getExiting() == VPBB)
409 ParentRegion->setExiting(PredVPBB);
410 for (
auto *Succ :
to_vector(VPBB->successors())) {
416 return !WorkList.
empty();
421 auto *
IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
422 if (!
IV ||
IV->getTruncInst())
433 auto &Casts =
IV->getInductionDescriptor().getCastInsts();
437 for (
auto *U : FindMyCast->
users()) {
438 auto *UserCast = cast<VPRecipeBase>(U);
439 if (UserCast->getNumDefinedValues() == 1 &&
440 UserCast->getVPSingleValue()->getUnderlyingValue() == IRCast) {
441 FoundUserCast = UserCast;
455 WidenNewIV = dyn_cast<VPWidenCanonicalIVRecipe>(U);
465 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
467 if (!WidenOriginalIV || !WidenOriginalIV->isCanonical() ||
468 WidenOriginalIV->getScalarType() != WidenNewIV->
getScalarType())
475 if (WidenOriginalIV->needsVectorIV() ||
492 if (R.mayHaveSideEffects() ||
any_of(R.definedValues(), [](
VPValue *V) {
493 return V->getNumUsers() > 0;
506 auto *WideIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
509 if (HasOnlyVectorVFs &&
none_of(WideIV->users(), [WideIV](
VPUser *U) {
510 return U->usesScalars(WideIV);
516 Type *ResultTy = WideIV->getPHINode()->getType();
518 ResultTy = TruncI->getType();
530 HeaderVPBB->
insert(Steps, IP);
536 if (HasOnlyVectorVFs && !U->usesScalars(WideIV))
538 for (
unsigned I = 0,
E = U->getNumOperands();
I !=
E;
I++) {
539 if (U->getOperand(
I) != WideIV)
541 U->setOperand(
I, Steps);
552 auto *ExpR = dyn_cast<VPExpandSCEVRecipe>(&R);
556 auto I = SCEV2VPV.
insert({ExpR->getSCEV(), ExpR});
559 ExpR->replaceAllUsesWith(
I.first->second);
560 ExpR->eraseFromParent();
565 VPInstruction *Not = dyn_cast<VPInstruction>(Term->getOperand(0));
576 assert(Plan.
hasVF(BestVF) &&
"BestVF is not available in Plan");
577 assert(Plan.
hasUF(BestUF) &&
"BestUF is not available in Plan");
580 auto *Term = dyn_cast<VPInstruction>(&ExitingVPBB->
back());
597 if (TripCount->
isZero() ||
605 Term->eraseFromParent();
615 auto *
Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
618 Region->getNumPredecessors() == 1 &&
"Expected SESE region!");
619 assert(R->getParent()->size() == 1 &&
620 "A recipe in an original replicator region must be the only "
621 "recipe in its block");
633 for (
auto &R : *
A->getParent()) {
643 if (ParentA == ParentB)
644 return LocalComesBefore(
A,
B);
667 auto TryToPushSinkCandidate = [&](
VPRecipeBase *SinkCandidate) {
669 SinkCandidate != Previous &&
670 "The previous value cannot depend on the users of the recurrence phi.");
671 if (isa<VPHeaderPHIRecipe>(SinkCandidate) ||
672 !Seen.
insert(SinkCandidate).second ||
681 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
684 "only recipes with a single defined value expected");
686 if (
auto *R = dyn_cast<VPRecipeBase>(
User))
687 TryToPushSinkCandidate(R);
698 if (SinkCandidate == FOR)
701 SinkCandidate->moveAfter(Previous);
702 Previous = SinkCandidate;
714 if (
auto *FOR = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R))
719 VPRecipeBase *Previous = FOR->getBackedgeValue()->getDefiningRecipe();
722 while (
auto *PrevPhi =
723 dyn_cast_or_null<VPFirstOrderRecurrencePHIRecipe>(Previous)) {
724 assert(PrevPhi->getParent() == FOR->getParent());
726 Previous = PrevPhi->getBackedgeValue()->getDefiningRecipe();
734 if (isa<VPHeaderPHIRecipe>(Previous))
739 auto *RecurSplice = cast<VPInstruction>(
741 {FOR, FOR->getBackedgeValue()}));
743 FOR->replaceAllUsesWith(RecurSplice);
746 RecurSplice->setOperand(0, FOR);
ReachingDefAnalysis InstSet & ToRemove
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
iv Induction Variable Users
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file implements dominator tree analysis for a single level of a VPlan's H-CFG.
static const uint32_t IV[8]
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
This class represents a function call, abstracting a target machine's calling convention.
@ ICMP_ULE
unsigned less or equal
static ConstantInt * getTrue(LLVMContext &Context)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Core dominator tree base class.
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
static constexpr ElementCount getFixed(ScalarTy MinVal)
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
A struct for saving information about induction variables.
const BasicBlock * getParent() const
const char * getOpcodeName() const
This is an important class for using LLVM in a threaded context.
An instruction for reading from memory.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
This class represents an analyzed expression in the program.
bool isZero() const
Return true if the expression is a constant zero.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
const SCEV * getConstant(ConstantInt *V)
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,...
LLVMContext & getContext() const
This class represents the LLVM 'select' instruction.
A vector that has set insertion semantics.
size_type size() const
Determine the number of elements in the SetVector.
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Provides information about what library functions are available for the current target.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
VPBasicBlock serves as the leaf 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.
iterator_range< iterator > phis()
Returns an iterator range over the PHI-like recipes in the block.
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
VPBasicBlock * splitAt(iterator SplitAt)
Split current block at SplitAt by inserting a new block between the current block and its successors ...
const VPRecipeBase & back() const
void insert(VPRecipeBase *Recipe, iterator InsertPt)
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
VPRegionBlock * getParent()
const VPBasicBlock * getExitingBasicBlock() const
const VPBasicBlock * getEntryBasicBlock() const
VPBlockBase * getSingleSuccessor() const
const VPBlocksTy & getSuccessors() const
static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBases IfTrue and IfFalse after BlockPtr.
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
A recipe for generating conditional branches on the bits of a mask.
VPlan-based builder utility analogous to IRBuilder.
Canonical scalar induction phi of the vector loop.
bool isCanonical(const InductionDescriptor &ID, Type *Ty) const
Check if the induction described by ID is canonical, i.e.
unsigned getNumDefinedValues() const
Returns the number of values defined by the VPDef.
ArrayRef< VPValue * > definedValues()
Returns an ArrayRef of the values defined by the VPDef.
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
A recipe for converting the canonical IV value to the corresponding value of an IV with different sta...
This is a concrete Recipe that models a single VPlan-level instruction.
@ FirstOrderRecurrenceSplice
unsigned getOpcode() const
VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when control converges back from ...
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
bool mayReadOrWriteMemory() const
Returns true if the recipe may read from or write to memory.
bool mayHaveSideEffects() const
Returns true if the recipe may have side-effects.
Instruction * getUnderlyingInstr()
Returns the underlying instruction, if the recipe is a VPValue or nullptr otherwise.
VPBasicBlock * getParent()
void moveBefore(VPBasicBlock &BB, iplist< VPRecipeBase >::iterator I)
Unlink this recipe and insert into BB before I.
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
iplist< VPRecipeBase >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
const VPBlockBase * getEntry() const
const VPBlockBase * getExiting() const
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
VPValue * getMask()
Return the mask of a predicated VPReplicateRecipe.
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
void setOperand(unsigned I, VPValue *New)
operand_iterator op_end()
operand_iterator op_begin()
VPValue * getOperand(unsigned N) const
Value * getUnderlyingValue()
Return the underlying Value attached to this VPValue.
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
void replaceAllUsesWith(VPValue *New)
unsigned getNumUsers() const
Value * getLiveInIRValue()
Returns the underlying IR value, if this VPValue is defined outside the scope of VPlan.
A recipe for widening Call instructions.
A Recipe for widening the canonical induction variable of the vector loop.
const Type * getScalarType() const
Returns the scalar type of the induction.
A recipe for handling GEP instructions.
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector valu...
A Recipe for widening load/store operations.
VPWidenRecipe is a recipe for producing a copy of vector type its ingredient.
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
VPValue * getOrAddExternalDef(Value *V)
Get the existing or add a new external definition for V.
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
bool hasVF(ElementCount VF)
bool hasUF(unsigned UF) const
void setVF(ElementCount VF)
bool hasScalarVFOnly() const
VPCanonicalIVPHIRecipe * getCanonicalIV()
Returns the canonical induction recipe of the vector loop.
Type * getType() const
All values are typed, get the type of this value.
void setName(const Twine &Name)
Change the name of the value.
StringRef getName() const
Return a constant reference to the value's name.
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
An efficient, type-erasing, non-owning reference to a callable.
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)
Get or create a VPValue that corresponds to the expansion of Expr.
bool onlyFirstLaneUsed(VPValue *Def)
Returns true if only the first lane of Def is used.
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)
Returns intrinsic ID for call.
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
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...
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...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
void sort(IteratorTy Start, IteratorTy End)
std::unique_ptr< VPlan > VPlanPtr
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
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...
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
const SCEV * createTripCountSCEV(Type *IdxTy, PredicatedScalarEvolution &PSE)
A recipe for handling first-order recurrence phis.
A recipe for widening select instructions.