33 GetIntOrFpInductionDescriptor,
38 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
40 auto EndIter = Term ? Term->getIterator() : VPBB->end();
45 VPValue *VPV = Ingredient.getVPSingleValue();
49 if (
auto *VPPhi = dyn_cast<VPWidenPHIRecipe>(&Ingredient)) {
50 auto *Phi = cast<PHINode>(VPPhi->getUnderlyingValue());
51 const auto *II = GetIntOrFpInductionDescriptor(Phi);
55 VPValue *Start = Plan->getVPValueOrAddLiveIn(II->getStartValue());
60 assert(isa<VPInstruction>(&Ingredient) &&
61 "only VPInstructions expected here");
62 assert(!isa<PHINode>(Inst) &&
"phis should be handled above");
64 if (
LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
66 *Load, Ingredient.getOperand(0),
nullptr ,
68 }
else if (
StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
70 *Store, Ingredient.getOperand(1), Ingredient.getOperand(0),
71 nullptr ,
false ,
false );
74 }
else if (
CallInst *CI = dyn_cast<CallInst>(Inst)) {
76 *CI,
drop_end(Ingredient.operands()),
78 }
else if (
SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
80 }
else if (
auto *CI = dyn_cast<CastInst>(Inst)) {
82 CI->getOpcode(), Ingredient.getOperand(0), CI->getType(), *CI);
93 "Only recpies with zero or one defined values expected");
94 Ingredient.eraseFromParent();
101 bool Changed =
false;
105 for (
VPRegionBlock *VPR : VPBlockUtils::blocksOnly<VPRegionBlock>(Iter)) {
112 for (
auto &Recipe : *VPBB) {
115 dyn_cast_or_null<VPSingleDefRecipe>(
Op->getDefiningRecipe()))
116 WorkList.
insert(std::make_pair(VPBB, Def));
122 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
125 std::tie(SinkTo, SinkCandidate) = WorkList[
I];
126 if (SinkCandidate->
getParent() == SinkTo ||
130 if (
auto *RepR = dyn_cast<VPReplicateRecipe>(SinkCandidate)) {
131 if (!ScalarVFOnly && RepR->isUniform())
133 }
else if (!isa<VPScalarIVStepsRecipe>(SinkCandidate))
136 bool NeedsDuplicating =
false;
141 auto CanSinkWithUser = [SinkTo, &NeedsDuplicating,
142 SinkCandidate](
VPUser *U) {
143 auto *UI = dyn_cast<VPRecipeBase>(U);
146 if (UI->getParent() == SinkTo)
148 NeedsDuplicating = UI->onlyFirstLaneUsed(SinkCandidate);
150 return NeedsDuplicating && isa<VPReplicateRecipe>(SinkCandidate);
152 if (!
all_of(SinkCandidate->
users(), CanSinkWithUser))
155 if (NeedsDuplicating) {
162 Clone->insertBefore(SinkCandidate);
164 return cast<VPRecipeBase>(&U)->getParent() != SinkTo;
170 dyn_cast_or_null<VPSingleDefRecipe>(
Op->getDefiningRecipe()))
171 WorkList.
insert(std::make_pair(SinkTo, Def));
180 auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry());
181 if (!EntryBB || EntryBB->size() != 1 ||
182 !isa<VPBranchOnMaskRecipe>(EntryBB->begin()))
185 return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0);
190 auto *EntryBB = cast<VPBasicBlock>(R->getEntry());
191 if (EntryBB->getNumSuccessors() != 2)
194 auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]);
195 auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]);
196 if (!Succ0 || !Succ1)
199 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
201 if (Succ0->getSingleSuccessor() == Succ1)
203 if (Succ1->getSingleSuccessor() == Succ0)
218 for (
VPRegionBlock *Region1 : VPBlockUtils::blocksOnly<VPRegionBlock>(
220 if (!Region1->isReplicator())
222 auto *MiddleBasicBlock =
223 dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());
224 if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
228 dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
229 if (!Region2 || !Region2->isReplicator())
234 if (!Mask1 || Mask1 != Mask2)
237 assert(Mask1 && Mask2 &&
"both region must have conditions");
243 if (DeletedRegions.
contains(Region1))
245 auto *MiddleBasicBlock = cast<VPBasicBlock>(Region1->getSingleSuccessor());
246 auto *Region2 = cast<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
250 if (!Then1 || !Then2)
269 cast<VPPredInstPHIRecipe>(&Phi1ToMove)->getOperand(0);
270 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue();
272 auto *UI = dyn_cast<VPRecipeBase>(&U);
273 return UI && UI->getParent() == Then2;
276 Phi1ToMove.moveBefore(*Merge2, Merge2->begin());
285 DeletedRegions.
insert(Region1);
290 return !DeletedRegions.
empty();
297 std::string RegionName = (
Twine(
"pred.") + Instr->getOpcodeName()).str();
298 assert(Instr->getParent() &&
"Predicated instruction not in any basic block");
299 auto *BlockInMask = PredRecipe->
getMask();
331 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
334 if (
auto *RepR = dyn_cast<VPReplicateRecipe>(&R)) {
335 if (RepR->isPredicated())
361 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
364 dyn_cast_or_null<VPBasicBlock>(VPBB->getSinglePredecessor());
365 if (PredVPBB && PredVPBB->getNumSuccessors() == 1)
370 VPBasicBlock *PredVPBB = cast<VPBasicBlock>(VPBB->getSinglePredecessor());
372 R.moveBefore(*PredVPBB, PredVPBB->
end());
374 auto *ParentRegion = cast_or_null<VPRegionBlock>(VPBB->getParent());
375 if (ParentRegion && ParentRegion->getExiting() == VPBB)
376 ParentRegion->setExiting(PredVPBB);
377 for (
auto *Succ :
to_vector(VPBB->successors())) {
383 return !WorkList.
empty();
390 bool ShouldSimplify =
true;
391 while (ShouldSimplify) {
406 auto *
IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
407 if (!
IV ||
IV->getTruncInst())
418 auto &Casts =
IV->getInductionDescriptor().getCastInsts();
422 for (
auto *U : FindMyCast->
users()) {
423 auto *UserCast = dyn_cast<VPSingleDefRecipe>(U);
424 if (UserCast && UserCast->getUnderlyingValue() == IRCast) {
425 FoundUserCast = UserCast;
429 FindMyCast = FoundUserCast;
441 WidenNewIV = dyn_cast<VPWidenCanonicalIVRecipe>(U);
451 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
453 if (!WidenOriginalIV || !WidenOriginalIV->isCanonical() ||
454 WidenOriginalIV->getScalarType() != WidenNewIV->
getScalarType())
461 if (
any_of(WidenOriginalIV->users(),
462 [WidenOriginalIV](
VPUser *U) {
463 return !U->usesScalars(WidenOriginalIV);
482 if (
any_of(R.definedValues(),
483 [](
VPValue *V) { return V->getNumUsers(); }))
489 auto *RepR = dyn_cast<VPReplicateRecipe>(&R);
490 bool IsConditionalAssume =
491 RepR && RepR->isPredicated() &&
492 match(RepR->getUnderlyingInstr(), m_Intrinsic<Intrinsic::assume>());
493 if (R.mayHaveSideEffects() && !IsConditionalAssume)
511 if (!CanonicalIV->
isCanonical(Kind, StartV, Step)) {
513 HeaderVPBB->
insert(BaseIV, IP);
526 HeaderVPBB->
insert(BaseIV, IP);
532 if (ResultTy != StepTy) {
543 BaseIV, Step, InductionOpcode,
545 HeaderVPBB->
insert(Steps, IP);
566 if (
auto *PtrIV = dyn_cast<VPWidenPointerInductionRecipe>(&Phi)) {
572 ConstantInt::get(
ID.getStep()->getType(), 0));
573 VPValue *StepV = PtrIV->getOperand(1);
576 Instruction::Add,
nullptr, SE,
nullptr, StartV,
583 PtrIV->getDebugLoc(),
"next.gep");
585 Recipe->insertAfter(Steps);
586 PtrIV->replaceAllUsesWith(Recipe);
592 auto *WideIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
595 if (HasOnlyVectorVFs &&
none_of(WideIV->users(), [WideIV](
VPUser *U) {
596 return U->usesScalars(WideIV);
602 Plan,
ID.getKind(),
ID.getInductionOpcode(),
603 dyn_cast_or_null<FPMathOperator>(
ID.getInductionBinOp()), SE,
604 WideIV->getTruncInst(), WideIV->getStartValue(), WideIV->getStepValue(),
608 if (!HasOnlyVectorVFs)
609 WideIV->replaceAllUsesWith(Steps);
611 WideIV->replaceUsesWithIf(Steps, [WideIV](
VPUser &U,
unsigned) {
612 return U.usesScalars(WideIV);
624 auto *ExpR = dyn_cast<VPExpandSCEVRecipe>(&R);
628 auto I = SCEV2VPV.
insert({ExpR->getSCEV(), ExpR});
631 ExpR->replaceAllUsesWith(
I.first->second);
632 ExpR->eraseFromParent();
639 assert(Plan.
hasVF(BestVF) &&
"BestVF is not available in Plan");
640 assert(Plan.
hasUF(BestUF) &&
"BestUF is not available in Plan");
643 auto *Term = &ExitingVPBB->
back();
650 if (!
match(Term, m_BranchOnCount(m_VPValue(), m_VPValue())) &&
652 m_BranchOnCond(
m_Not(m_ActiveLaneMask(m_VPValue(), m_VPValue())))))
661 if (TripCount->
isZero() ||
669 Term->eraseFromParent();
680 auto *
Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
683 Region->getNumPredecessors() == 1 &&
"Expected SESE region!");
684 assert(R->getParent()->size() == 1 &&
685 "A recipe in an original replicator region must be the only "
686 "recipe in its block");
699 for (
auto &R : *
A->getParent()) {
709 if (ParentA == ParentB)
710 return LocalComesBefore(
A,
B);
713 "No replicate regions expected at this point");
715 "No replicate regions expected at this point");
730 auto TryToPushSinkCandidate = [&](
VPRecipeBase *SinkCandidate) {
733 if (SinkCandidate == Previous)
736 if (isa<VPHeaderPHIRecipe>(SinkCandidate) ||
737 !Seen.
insert(SinkCandidate).second ||
741 if (SinkCandidate->mayHaveSideEffects())
750 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
753 "only recipes with a single defined value expected");
756 if (
auto *R = dyn_cast<VPRecipeBase>(
User))
757 if (!TryToPushSinkCandidate(R))
769 if (SinkCandidate == FOR)
772 SinkCandidate->moveAfter(Previous);
773 Previous = SinkCandidate;
786 if (
auto *FOR = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R))
791 VPRecipeBase *Previous = FOR->getBackedgeValue()->getDefiningRecipe();
794 while (
auto *PrevPhi =
795 dyn_cast_or_null<VPFirstOrderRecurrencePHIRecipe>(Previous)) {
796 assert(PrevPhi->getParent() == FOR->getParent());
798 Previous = PrevPhi->getBackedgeValue()->getDefiningRecipe();
807 if (isa<VPHeaderPHIRecipe>(Previous))
812 auto *RecurSplice = cast<VPInstruction>(
814 {FOR, FOR->getBackedgeValue()}));
816 FOR->replaceAllUsesWith(RecurSplice);
819 RecurSplice->setOperand(0, FOR);
827 auto *PhiR = dyn_cast<VPReductionPHIRecipe>(&R);
838 for (
unsigned I = 0;
I != Worklist.
size(); ++
I) {
840 if (
auto *RecWithFlags =
842 RecWithFlags->dropPoisonGeneratingFlags();
846 auto *UserRecipe = dyn_cast<VPRecipeBase>(U);
849 for (
VPValue *V : UserRecipe->definedValues())
859 if (
auto *Blend = dyn_cast<VPBlendRecipe>(&R)) {
860 VPValue *Inc0 = Blend->getIncomingValue(0);
861 for (
unsigned I = 1;
I != Blend->getNumIncomingValues(); ++
I)
862 if (Inc0 != Blend->getIncomingValue(
I))
865 Blend->eraseFromParent();
872 VPValue *Trunc = R.getVPSingleValue();
875 if (TruncTy == ATy) {
879 if (isa<VPReplicateRecipe>(&R))
883 unsigned ExtOpcode =
match(R.getOperand(0),
m_SExt(m_VPValue()))
888 VPC->insertBefore(&R);
892 VPC->insertBefore(&R);
900 R.getParent()->getPlan()->getCanonicalIV()->getScalarType(),
904 auto *R = dyn_cast<VPRecipeBase>(U);
907 for (
VPValue *VPV : R->definedValues())
915 return R.getVPSingleValue()->replaceAllUsesWith(
A);
923 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
936 unsigned NumProcessedRecipes = 0;
945 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
951 if (isa<VPWidenMemoryInstructionRecipe>(&R) &&
952 cast<VPWidenMemoryInstructionRecipe>(&R)->
isStore())
955 VPValue *ResultVPV = R.getVPSingleValue();
957 unsigned NewResSizeInBits = MinBWs.
lookup(UI);
958 if (!NewResSizeInBits)
962 NumProcessedRecipes++;
968 if (isa<VPReplicateRecipe, VPWidenCastRecipe>(&R)) {
980 auto *UV = dyn_cast_or_null<Instruction>(
Op->getUnderlyingValue());
983 return !isa<VPWidenRecipe, VPWidenSelectRecipe>(U);
987 ProcessedTruncs[
Op] =
nullptr;
988 NumProcessedRecipes += 1;
998 (void)OldResSizeInBits;
1005 if (
auto *VPW = dyn_cast<VPRecipeWithIRFlags>(&R))
1006 VPW->dropPoisonGeneratingFlags();
1008 if (OldResSizeInBits != NewResSizeInBits) {
1012 Ext->insertAfter(&R);
1014 Ext->setOperand(0, ResultVPV);
1015 assert(OldResSizeInBits > NewResSizeInBits &&
"Nothing to shrink?");
1018 "Only ICmps should not need extending the result.");
1020 if (isa<VPWidenMemoryInstructionRecipe>(&R)) {
1021 assert(!cast<VPWidenMemoryInstructionRecipe>(&R)->
isStore() &&
"stores cannot be narrowed");
1026 unsigned StartIdx = isa<VPWidenSelectRecipe>(&R) ? 1 : 0;
1027 for (
unsigned Idx = StartIdx;
Idx != R.getNumOperands(); ++
Idx) {
1028 auto *
Op = R.getOperand(
Idx);
1029 unsigned OpSizeInBits =
1031 if (OpSizeInBits == NewResSizeInBits)
1033 assert(OpSizeInBits > NewResSizeInBits &&
"nothing to truncate");
1034 auto [ProcessedIter, IterIsEmpty] =
1035 ProcessedTruncs.
insert({
Op,
nullptr});
1039 : ProcessedIter->second;
1040 R.setOperand(
Idx, NewOp);
1043 ProcessedIter->second = NewOp;
1044 if (!
Op->isLiveIn()) {
1049 auto *OpInst = dyn_cast<Instruction>(
Op->getLiveInIRValue());
1050 bool IsContained = MinBWs.
contains(OpInst);
1051 NumProcessedRecipes += IsContained;
1059 assert(MinBWs.
size() == NumProcessedRecipes &&
1060 "some entries in MinBWs haven't been processed");
1115 VPValue *StartV = CanonicalIVPHI->getStartValue();
1117 auto *CanonicalIVIncrement =
1118 cast<VPInstruction>(CanonicalIVPHI->getBackedgeValue());
1121 CanonicalIVIncrement->dropPoisonGeneratingFlags();
1122 DebugLoc DL = CanonicalIVIncrement->getDebugLoc();
1132 VPValue *TripCount, *IncrementValue;
1137 IncrementValue = CanonicalIVIncrement;
1143 IncrementValue = CanonicalIVPHI;
1154 DL,
"active.lane.mask.entry");
1159 LaneMaskPhi->insertAfter(CanonicalIVPHI);
1165 auto *InLoopIncrement =
1167 {IncrementValue}, {
false,
false},
DL);
1169 {InLoopIncrement, TripCount},
DL,
1170 "active.lane.mask.next");
1182 VPlan &Plan,
bool UseActiveLaneMaskForControlFlow,
1185 UseActiveLaneMaskForControlFlow) &&
1186 "DataAndControlFlowWithoutRuntimeCheck implies "
1187 "UseActiveLaneMaskForControlFlow");
1189 auto FoundWidenCanonicalIVUser =
1191 [](
VPUser *U) { return isa<VPWidenCanonicalIVRecipe>(U); });
1192 assert(FoundWidenCanonicalIVUser &&
1193 "Must have widened canonical IV when tail folding!");
1194 auto *WideCanonicalIV =
1195 cast<VPWidenCanonicalIVRecipe>(*FoundWidenCanonicalIVUser);
1197 if (UseActiveLaneMaskForControlFlow) {
1204 "active.lane.mask");
1212 auto *CompareToReplace = dyn_cast<VPInstruction>(U);
1213 if (!CompareToReplace ||
1214 CompareToReplace->getOpcode() != Instruction::ICmp ||
1216 CompareToReplace->getOperand(1) != BTC)
1219 assert(CompareToReplace->getOperand(0) == WideCanonicalIV &&
1220 "WidenCanonicalIV must be the first operand of the compare");
1221 CompareToReplace->replaceAllUsesWith(LaneMask);
1222 CompareToReplace->eraseFromParent();
1231 auto collectPoisonGeneratingInstrsInBackwardSlice([&](
VPRecipeBase *Root) {
1236 while (!Worklist.
empty()) {
1237 VPRecipeBase *CurRec = Worklist.back();
1238 Worklist.pop_back();
1240 if (!Visited.insert(CurRec).second)
1247 if (isa<VPWidenMemoryInstructionRecipe>(CurRec) ||
1248 isa<VPInterleaveRecipe>(CurRec) ||
1249 isa<VPScalarIVStepsRecipe>(CurRec) ||
1250 isa<VPCanonicalIVPHIRecipe>(CurRec) ||
1251 isa<VPActiveLaneMaskPHIRecipe>(CurRec))
1257 if (auto *RecWithFlags = dyn_cast<VPRecipeWithIRFlags>(CurRec)) {
1258 RecWithFlags->dropPoisonGeneratingFlags();
1260 Instruction *Instr = dyn_cast_or_null<Instruction>(
1261 CurRec->getVPSingleValue()->getUnderlyingValue());
1263 assert((!Instr || !Instr->hasPoisonGeneratingFlags()) &&
1264 "found instruction with poison generating flags not covered by "
1265 "VPRecipeWithIRFlags");
1279 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {
1281 if (
auto *WidenRec = dyn_cast<VPWidenMemoryInstructionRecipe>(&Recipe)) {
1282 Instruction &UnderlyingInstr = WidenRec->getIngredient();
1283 VPRecipeBase *AddrDef = WidenRec->getAddr()->getDefiningRecipe();
1284 if (AddrDef && WidenRec->isConsecutive() &&
1285 BlockNeedsPredication(UnderlyingInstr.
getParent()))
1286 collectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
1287 }
else if (
auto *InterleaveRec = dyn_cast<VPInterleaveRecipe>(&Recipe)) {
1288 VPRecipeBase *AddrDef = InterleaveRec->getAddr()->getDefiningRecipe();
1292 InterleaveRec->getInterleaveGroup();
1293 bool NeedPredication =
false;
1295 I < NumMembers; ++
I) {
1298 NeedPredication |= BlockNeedsPredication(Member->getParent());
1301 if (NeedPredication)
1302 collectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static bool isStore(int Opcode)
ReachingDefAnalysis InstSet & ToRemove
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
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
static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution &SE)
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 std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
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)
This class represents an Operation in the Expression.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
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)
Utility class for floating point operations which can have information about relaxed accuracy require...
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags.
Convenience struct for specifying and reasoning about fast-math flags.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
A struct for saving information about induction variables.
InductionKind
This enum represents the kinds of inductions that we support.
@ IK_IntInduction
Integer induction variable. Step = C.
const BasicBlock * getParent() const
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
The group of interleaved loads/stores sharing the same stride and close to each other.
InstTy * getMember(uint32_t Index) const
Get the member with the given index Index.
uint32_t getNumMembers() const
This is an important class for using LLVM in a threaded context.
An instruction for reading from memory.
This class implements a map that also provides access to all stored values in a deterministic order.
bool contains(const KeyT &Key) const
ValueT lookup(const KeyT &Key) const
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.
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
RecurKind getRecurrenceKind() const
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.
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,...
const SCEV * getElementCount(Type *Ty, ElementCount EC)
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 empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
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.
A SetVector that performs no allocations if smaller than a certain size.
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.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
A recipe for generating the active lane mask for the vector loop that is used to predicate the vector...
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.
RecipeListTy::iterator iterator
Instruction iterators...
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 ...
VPRecipeBase * getTerminator()
If the block has multiple successors, return the branch recipe terminating the block.
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
VPBlockBase * getSinglePredecessor() const
const VPBasicBlock * getEntryBasicBlock() const
VPBlockBase * getSingleHierarchicalPredecessor()
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.
static VPBuilder getToInsertAfter(VPRecipeBase *R)
Create a VPBuilder to insert after R.
VPInstruction * createOverflowingOp(unsigned Opcode, std::initializer_list< VPValue * > Operands, VPRecipeWithIRFlags::WrapFlagsTy WrapFlags, DebugLoc DL={}, const Twine &Name="")
VPInstruction * createNaryOp(unsigned Opcode, ArrayRef< VPValue * > Operands, Instruction *Inst=nullptr, const Twine &Name="")
Create an N-ary operation with Opcode, Operands and set Inst as its underlying Instruction.
VPValue * createNot(VPValue *Operand, DebugLoc DL={}, const Twine &Name="")
void setInsertPoint(VPBasicBlock *TheBB)
This specifies that created VPInstructions should be appended to the end of the specified block.
Canonical scalar induction phi of the vector loop.
Type * getScalarType() const
Returns the scalar type of the induction.
bool isCanonical(InductionDescriptor::InductionKind Kind, VPValue *Start, VPValue *Step) 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.
@ FirstOrderRecurrenceSplice
@ CanonicalIVIncrementForPart
@ CalculateTripCountMinusVF
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.
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.
VPScalarCastRecipe is a recipe to create scalar cast instructions.
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
VPSingleDef is a base class for recipes for modeling a sequence of one or more output IR that define ...
Instruction * getUnderlyingInstr()
Returns the underlying instruction.
An analysis for type-inference for VPValues.
LLVMContext & getContext()
Return the LLVMContext used by the analysis.
Type * inferScalarType(const VPValue *V)
Infer the type of V. Returns the scalar type of V.
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()
void addOperand(VPValue *Operand)
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.
void replaceUsesWithIf(VPValue *New, llvm::function_ref< bool(VPUser &U, unsigned Idx)> ShouldReplace)
Go through the uses list for this VPValue and make each use point to New if the callback ShouldReplac...
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 * getTripCount() const
The trip count of the original loop.
VPValue * getOrCreateBackedgeTakenCount()
The backedge taken count of the original loop.
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 LeafTy multiplyCoefficientBy(ScalarTy RHS) const
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.
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
bool match(Val *V, const Pattern &P)
CastOperator_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, SExtInst > > m_ZExtOrSExt(const OpTy &Op)
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)
Matches SExt.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)
Get or create a VPValue that corresponds to the expansion of Expr.
bool onlyFirstLaneUsed(const 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...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
RecurKind
These are the kinds of recurrences that we support.
@ Mul
Product of integers.
DWARFExpression::Operation Op
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
@ DataAndControlFlowWithoutRuntimeCheck
Use predicate to control both data and control flow, but modify the trip count so that a runtime over...
A recipe for handling first-order recurrence phis.
A recipe for widening select instructions.