29 GetIntOrFpInductionDescriptor,
34 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
36 auto EndIter = Term ? Term->getIterator() : VPBB->end();
41 VPValue *VPV = Ingredient.getVPSingleValue();
45 if (
auto *VPPhi = dyn_cast<VPWidenPHIRecipe>(&Ingredient)) {
46 auto *Phi = cast<PHINode>(VPPhi->getUnderlyingValue());
47 if (
const auto *II = GetIntOrFpInductionDescriptor(Phi)) {
48 VPValue *Start = Plan->getVPValueOrAddLiveIn(II->getStartValue());
53 Plan->addVPValue(Phi, VPPhi);
57 assert(isa<VPInstruction>(&Ingredient) &&
58 "only VPInstructions expected here");
59 assert(!isa<PHINode>(Inst) &&
"phis should be handled above");
61 if (
LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
63 *Load, Ingredient.getOperand(0),
nullptr ,
65 }
else if (
StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
67 *Store, Ingredient.getOperand(1), Ingredient.getOperand(0),
68 nullptr ,
false ,
false );
71 }
else if (
CallInst *CI = dyn_cast<CallInst>(Inst)) {
75 }
else if (
SelectInst *
SI = dyn_cast<SelectInst>(Inst)) {
77 }
else if (
auto *CI = dyn_cast<CastInst>(Inst)) {
79 CI->getOpcode(), Ingredient.getOperand(0), CI->getType(), CI);
90 "Only recpies with zero or one defined values expected");
91 Ingredient.eraseFromParent();
102 for (
VPRegionBlock *VPR : VPBlockUtils::blocksOnly<VPRegionBlock>(Iter)) {
109 for (
auto &Recipe : *VPBB) {
110 for (
VPValue *Op : Recipe.operands())
111 if (
auto *Def = Op->getDefiningRecipe())
112 WorkList.
insert(std::make_pair(VPBB, Def));
118 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
121 std::tie(SinkTo, SinkCandidate) = WorkList[
I];
122 if (SinkCandidate->
getParent() == SinkTo ||
126 if (
auto *RepR = dyn_cast<VPReplicateRecipe>(SinkCandidate)) {
127 if (!ScalarVFOnly && RepR->isUniform())
129 }
else if (!isa<VPScalarIVStepsRecipe>(SinkCandidate))
132 bool NeedsDuplicating =
false;
137 auto CanSinkWithUser = [SinkTo, &NeedsDuplicating,
138 SinkCandidate](
VPUser *U) {
139 auto *UI = dyn_cast<VPRecipeBase>(U);
142 if (UI->getParent() == SinkTo)
147 return NeedsDuplicating && isa<VPReplicateRecipe>(SinkCandidate);
152 if (NeedsDuplicating) {
156 cast<VPReplicateRecipe>(SinkCandidate)->getUnderlyingValue());
160 Clone->insertBefore(SinkCandidate);
162 auto *UI = cast<VPRecipeBase>(U);
163 if (UI->getParent() == SinkTo)
166 for (
unsigned Idx = 0;
Idx != UI->getNumOperands();
Idx++) {
169 UI->setOperand(
Idx, Clone);
175 if (
auto *Def = Op->getDefiningRecipe())
176 WorkList.
insert(std::make_pair(SinkTo, Def));
185 auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry());
186 if (!EntryBB || EntryBB->size() != 1 ||
187 !isa<VPBranchOnMaskRecipe>(EntryBB->begin()))
190 return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0);
195 auto *EntryBB = cast<VPBasicBlock>(R->getEntry());
196 if (EntryBB->getNumSuccessors() != 2)
199 auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]);
200 auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]);
201 if (!Succ0 || !Succ1)
204 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
206 if (Succ0->getSingleSuccessor() == Succ1)
208 if (Succ1->getSingleSuccessor() == Succ0)
223 for (
VPRegionBlock *Region1 : VPBlockUtils::blocksOnly<VPRegionBlock>(
225 if (!Region1->isReplicator())
227 auto *MiddleBasicBlock =
228 dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());
229 if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
233 dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
234 if (!Region2 || !Region2->isReplicator())
239 if (!Mask1 || Mask1 != Mask2)
242 assert(Mask1 && Mask2 &&
"both region must have conditions");
248 if (DeletedRegions.
contains(Region1))
250 auto *MiddleBasicBlock = cast<VPBasicBlock>(Region1->getSingleSuccessor());
251 auto *Region2 = cast<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
255 if (!Then1 || !Then2)
274 cast<VPPredInstPHIRecipe>(&Phi1ToMove)->getOperand(0);
275 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue();
277 auto *UI = dyn_cast<VPRecipeBase>(U);
278 if (!UI || UI->getParent() != Then2)
280 for (
unsigned I = 0,
E = U->getNumOperands();
I !=
E; ++
I) {
281 if (Phi1ToMoveV != U->getOperand(
I))
283 U->setOperand(
I, PredInst1);
287 Phi1ToMove.moveBefore(*Merge2, Merge2->begin());
296 DeletedRegions.
insert(Region1);
301 return !DeletedRegions.
empty();
309 assert(Instr->
getParent() &&
"Predicated instruction not in any basic block");
310 auto *BlockInMask = PredRecipe->
getMask();
342 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
345 if (
auto *RepR = dyn_cast<VPReplicateRecipe>(&R)) {
346 if (RepR->isPredicated())
372 bool ShouldSimplify =
true;
373 while (ShouldSimplify) {
381 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
384 dyn_cast_or_null<VPBasicBlock>(VPBB->getSinglePredecessor());
385 if (PredVPBB && PredVPBB->getNumSuccessors() == 1)
390 VPBasicBlock *PredVPBB = cast<VPBasicBlock>(VPBB->getSinglePredecessor());
392 R.moveBefore(*PredVPBB, PredVPBB->
end());
394 auto *ParentRegion = cast_or_null<VPRegionBlock>(VPBB->getParent());
395 if (ParentRegion && ParentRegion->getExiting() == VPBB)
396 ParentRegion->setExiting(PredVPBB);
397 for (
auto *Succ :
to_vector(VPBB->successors())) {
403 return !WorkList.
empty();
408 auto *
IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
409 if (!
IV ||
IV->getTruncInst())
420 auto &Casts =
IV->getInductionDescriptor().getCastInsts();
424 for (
auto *U : FindMyCast->
users()) {
425 auto *UserCast = cast<VPRecipeBase>(U);
426 if (UserCast->getNumDefinedValues() == 1 &&
427 UserCast->getVPSingleValue()->getUnderlyingValue() == IRCast) {
428 FoundUserCast = UserCast;
442 WidenNewIV = dyn_cast<VPWidenCanonicalIVRecipe>(U);
452 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
454 if (!WidenOriginalIV || !WidenOriginalIV->isCanonical() ||
455 WidenOriginalIV->getScalarType() != WidenNewIV->
getScalarType())
462 if (
any_of(WidenOriginalIV->users(),
463 [WidenOriginalIV](
VPUser *U) {
464 return !U->usesScalars(WidenOriginalIV);
482 if (R.mayHaveSideEffects() ||
any_of(R.definedValues(), [](
VPValue *V) {
483 return V->getNumUsers() > 0;
496 auto *WideIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
499 if (HasOnlyVectorVFs &&
none_of(WideIV->users(), [WideIV](
VPUser *U) {
500 return U->usesScalars(WideIV);
506 Type *ResultTy = WideIV->getPHINode()->getType();
508 ResultTy = TruncI->getType();
513 if (!CanonicalIV->
isCanonical(
ID.getKind(), WideIV->getStartValue(), Step,
521 HeaderVPBB->
insert(Steps, IP);
527 if (HasOnlyVectorVFs && !U->usesScalars(WideIV))
529 for (
unsigned I = 0,
E = U->getNumOperands();
I !=
E;
I++) {
530 if (U->getOperand(
I) != WideIV)
532 U->setOperand(
I, Steps);
543 auto *ExpR = dyn_cast<VPExpandSCEVRecipe>(&R);
547 auto I = SCEV2VPV.
insert({ExpR->getSCEV(), ExpR});
550 ExpR->replaceAllUsesWith(
I.first->second);
551 ExpR->eraseFromParent();
556 VPInstruction *Not = dyn_cast<VPInstruction>(Term->getOperand(0));
567 assert(Plan.
hasVF(BestVF) &&
"BestVF is not available in Plan");
568 assert(Plan.
hasUF(BestUF) &&
"BestUF is not available in Plan");
571 auto *Term = dyn_cast<VPInstruction>(&ExitingVPBB->
back());
588 if (TripCount->
isZero() ||
596 Term->eraseFromParent();
607 auto *
Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
610 Region->getNumPredecessors() == 1 &&
"Expected SESE region!");
611 assert(R->getParent()->size() == 1 &&
612 "A recipe in an original replicator region must be the only "
613 "recipe in its block");
626 for (
auto &R : *
A->getParent()) {
636 if (ParentA == ParentB)
637 return LocalComesBefore(
A,
B);
640 "No replicate regions expected at this point");
642 "No replicate regions expected at this point");
657 auto TryToPushSinkCandidate = [&](
VPRecipeBase *SinkCandidate) {
660 if (SinkCandidate == Previous)
663 if (isa<VPHeaderPHIRecipe>(SinkCandidate) ||
664 !Seen.
insert(SinkCandidate).second ||
674 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
677 "only recipes with a single defined value expected");
679 if (
auto *R = dyn_cast<VPRecipeBase>(
User))
680 if (!TryToPushSinkCandidate(R))
692 if (SinkCandidate == FOR)
695 SinkCandidate->moveAfter(Previous);
696 Previous = SinkCandidate;
709 if (
auto *FOR = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R))
714 VPRecipeBase *Previous = FOR->getBackedgeValue()->getDefiningRecipe();
717 while (
auto *PrevPhi =
718 dyn_cast_or_null<VPFirstOrderRecurrencePHIRecipe>(Previous)) {
719 assert(PrevPhi->getParent() == FOR->getParent());
721 Previous = PrevPhi->getBackedgeValue()->getDefiningRecipe();
730 if (isa<VPHeaderPHIRecipe>(Previous))
735 auto *RecurSplice = cast<VPInstruction>(
737 {FOR, FOR->getBackedgeValue()}));
739 FOR->replaceAllUsesWith(RecurSplice);
742 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.
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(InductionDescriptor::InductionKind Kind, VPValue *Start, VPValue *Step, Type *Ty) const
Check if the induction described by Kind, /p Start and Step is canonical, i.e.
unsigned getNumDefinedValues() const
Returns the number of 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.
unsigned getOpcode() const
@ FirstOrderRecurrenceSplice
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
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.
VPWidenCastRecipe is a recipe to create vector cast instructions.
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...
VPBasicBlock * getEntry()
VPValue * getVPValueOrAddLiveIn(Value *V)
Gets the VPValue for V or adds a new live-in (if none exists yet) 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 SCEV * createTripCountSCEV(Type *IdxTy, PredicatedScalarEvolution &PSE, Loop *OrigLoop)
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...
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
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.
A recipe for handling first-order recurrence phis.
A recipe for widening select instructions.