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->getOrAddLiveIn(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 Ingredient.getDebugLoc());
69 }
else if (
StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
71 *Store, Ingredient.getOperand(1), Ingredient.getOperand(0),
72 nullptr ,
false ,
false ,
73 Ingredient.getDebugLoc());
76 }
else if (
CallInst *CI = dyn_cast<CallInst>(Inst)) {
78 *CI,
drop_end(Ingredient.operands()),
80 }
else if (
SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
82 }
else if (
auto *CI = dyn_cast<CastInst>(Inst)) {
84 CI->getOpcode(), Ingredient.getOperand(0), CI->getType(), *CI);
95 "Only recpies with zero or one defined values expected");
96 Ingredient.eraseFromParent();
103 bool Changed =
false;
107 for (
VPRegionBlock *VPR : VPBlockUtils::blocksOnly<VPRegionBlock>(Iter)) {
114 for (
auto &Recipe : *VPBB) {
117 dyn_cast_or_null<VPSingleDefRecipe>(
Op->getDefiningRecipe()))
118 WorkList.
insert(std::make_pair(VPBB, Def));
124 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
127 std::tie(SinkTo, SinkCandidate) = WorkList[
I];
128 if (SinkCandidate->
getParent() == SinkTo ||
132 if (
auto *RepR = dyn_cast<VPReplicateRecipe>(SinkCandidate)) {
133 if (!ScalarVFOnly && RepR->isUniform())
135 }
else if (!isa<VPScalarIVStepsRecipe>(SinkCandidate))
138 bool NeedsDuplicating =
false;
143 auto CanSinkWithUser = [SinkTo, &NeedsDuplicating,
144 SinkCandidate](
VPUser *U) {
145 auto *UI = dyn_cast<VPRecipeBase>(U);
148 if (UI->getParent() == SinkTo)
150 NeedsDuplicating = UI->onlyFirstLaneUsed(SinkCandidate);
152 return NeedsDuplicating && isa<VPReplicateRecipe>(SinkCandidate);
154 if (!
all_of(SinkCandidate->
users(), CanSinkWithUser))
157 if (NeedsDuplicating) {
164 Clone->insertBefore(SinkCandidate);
166 return cast<VPRecipeBase>(&U)->getParent() != SinkTo;
172 dyn_cast_or_null<VPSingleDefRecipe>(
Op->getDefiningRecipe()))
173 WorkList.
insert(std::make_pair(SinkTo, Def));
182 auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry());
183 if (!EntryBB || EntryBB->size() != 1 ||
184 !isa<VPBranchOnMaskRecipe>(EntryBB->begin()))
187 return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0);
192 auto *EntryBB = cast<VPBasicBlock>(R->getEntry());
193 if (EntryBB->getNumSuccessors() != 2)
196 auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]);
197 auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]);
198 if (!Succ0 || !Succ1)
201 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
203 if (Succ0->getSingleSuccessor() == Succ1)
205 if (Succ1->getSingleSuccessor() == Succ0)
220 for (
VPRegionBlock *Region1 : VPBlockUtils::blocksOnly<VPRegionBlock>(
222 if (!Region1->isReplicator())
224 auto *MiddleBasicBlock =
225 dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());
226 if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
230 dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
231 if (!Region2 || !Region2->isReplicator())
236 if (!Mask1 || Mask1 != Mask2)
239 assert(Mask1 && Mask2 &&
"both region must have conditions");
245 if (DeletedRegions.
contains(Region1))
247 auto *MiddleBasicBlock = cast<VPBasicBlock>(Region1->getSingleSuccessor());
248 auto *Region2 = cast<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
252 if (!Then1 || !Then2)
271 cast<VPPredInstPHIRecipe>(&Phi1ToMove)->getOperand(0);
272 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue();
274 auto *UI = dyn_cast<VPRecipeBase>(&U);
275 return UI && UI->getParent() == Then2;
278 Phi1ToMove.moveBefore(*Merge2, Merge2->begin());
287 DeletedRegions.
insert(Region1);
292 return !DeletedRegions.
empty();
299 std::string RegionName = (
Twine(
"pred.") + Instr->getOpcodeName()).str();
300 assert(Instr->getParent() &&
"Predicated instruction not in any basic block");
301 auto *BlockInMask = PredRecipe->
getMask();
333 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
336 if (
auto *RepR = dyn_cast<VPReplicateRecipe>(&R)) {
337 if (RepR->isPredicated())
363 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
366 dyn_cast_or_null<VPBasicBlock>(VPBB->getSinglePredecessor());
367 if (PredVPBB && PredVPBB->getNumSuccessors() == 1)
372 VPBasicBlock *PredVPBB = cast<VPBasicBlock>(VPBB->getSinglePredecessor());
374 R.moveBefore(*PredVPBB, PredVPBB->
end());
376 auto *ParentRegion = cast_or_null<VPRegionBlock>(VPBB->getParent());
377 if (ParentRegion && ParentRegion->getExiting() == VPBB)
378 ParentRegion->setExiting(PredVPBB);
379 for (
auto *Succ :
to_vector(VPBB->successors())) {
385 return !WorkList.
empty();
392 bool ShouldSimplify =
true;
393 while (ShouldSimplify) {
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 = dyn_cast<VPSingleDefRecipe>(U);
426 if (UserCast && UserCast->getUnderlyingValue() == IRCast) {
427 FoundUserCast = UserCast;
431 FindMyCast = FoundUserCast;
443 WidenNewIV = dyn_cast<VPWidenCanonicalIVRecipe>(U);
453 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
455 if (!WidenOriginalIV || !WidenOriginalIV->isCanonical() ||
456 WidenOriginalIV->getScalarType() != WidenNewIV->
getScalarType())
463 if (
any_of(WidenOriginalIV->users(),
464 [WidenOriginalIV](
VPUser *U) {
465 return !U->usesScalars(WidenOriginalIV);
480 auto *RepR = dyn_cast<VPReplicateRecipe>(&R);
481 bool IsConditionalAssume =
482 RepR && RepR->isPredicated() &&
483 match(RepR->getUnderlyingInstr(), m_Intrinsic<Intrinsic::assume>());
484 if (IsConditionalAssume)
487 if (R.mayHaveSideEffects())
491 return all_of(R.definedValues(),
492 [](
VPValue *V) { return V->getNumUsers() == 0; });
519 if (!CanonicalIV->
isCanonical(Kind, StartV, Step)) {
521 HeaderVPBB->
insert(BaseIV, IP);
534 HeaderVPBB->
insert(BaseIV, IP);
540 if (ResultTy != StepTy) {
551 BaseIV, Step, InductionOpcode,
553 HeaderVPBB->
insert(Steps, IP);
574 if (
auto *PtrIV = dyn_cast<VPWidenPointerInductionRecipe>(&Phi)) {
581 VPValue *StepV = PtrIV->getOperand(1);
584 Instruction::Add,
nullptr, SE,
nullptr, StartV,
591 PtrIV->getDebugLoc(),
"next.gep");
593 Recipe->insertAfter(Steps);
594 PtrIV->replaceAllUsesWith(Recipe);
600 auto *WideIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
603 if (HasOnlyVectorVFs &&
none_of(WideIV->users(), [WideIV](
VPUser *U) {
604 return U->usesScalars(WideIV);
610 Plan,
ID.getKind(),
ID.getInductionOpcode(),
611 dyn_cast_or_null<FPMathOperator>(
ID.getInductionBinOp()), SE,
612 WideIV->getTruncInst(), WideIV->getStartValue(), WideIV->getStepValue(),
616 if (!HasOnlyVectorVFs)
617 WideIV->replaceAllUsesWith(Steps);
619 WideIV->replaceUsesWithIf(Steps, [WideIV](
VPUser &U,
unsigned) {
620 return U.usesScalars(WideIV);
632 auto *ExpR = dyn_cast<VPExpandSCEVRecipe>(&R);
636 auto I = SCEV2VPV.
insert({ExpR->getSCEV(), ExpR});
639 ExpR->replaceAllUsesWith(
I.first->second);
640 ExpR->eraseFromParent();
649 while (!WorkList.
empty()) {
651 if (!Seen.
insert(Cur).second)
658 WorkList.
append(R->op_begin(), R->op_end());
659 R->eraseFromParent();
666 assert(Plan.
hasVF(BestVF) &&
"BestVF is not available in Plan");
667 assert(Plan.
hasUF(BestUF) &&
"BestUF is not available in Plan");
670 auto *Term = &ExitingVPBB->
back();
677 if (!
match(Term, m_BranchOnCount(m_VPValue(), m_VPValue())) &&
679 m_BranchOnCond(
m_Not(m_ActiveLaneMask(m_VPValue(), m_VPValue())))))
688 if (TripCount->
isZero() ||
698 Term->eraseFromParent();
711 auto *
Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
714 Region->getNumPredecessors() == 1 &&
"Expected SESE region!");
715 assert(R->getParent()->size() == 1 &&
716 "A recipe in an original replicator region must be the only "
717 "recipe in its block");
730 for (
auto &R : *
A->getParent()) {
740 if (ParentA == ParentB)
741 return LocalComesBefore(
A,
B);
744 "No replicate regions expected at this point");
746 "No replicate regions expected at this point");
761 auto TryToPushSinkCandidate = [&](
VPRecipeBase *SinkCandidate) {
764 if (SinkCandidate == Previous)
767 if (isa<VPHeaderPHIRecipe>(SinkCandidate) ||
768 !Seen.
insert(SinkCandidate).second ||
772 if (SinkCandidate->mayHaveSideEffects())
781 for (
unsigned I = 0;
I != WorkList.
size(); ++
I) {
784 "only recipes with a single defined value expected");
787 if (
auto *R = dyn_cast<VPRecipeBase>(
User))
788 if (!TryToPushSinkCandidate(R))
800 if (SinkCandidate == FOR)
803 SinkCandidate->moveAfter(Previous);
804 Previous = SinkCandidate;
817 if (
auto *FOR = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R))
822 VPRecipeBase *Previous = FOR->getBackedgeValue()->getDefiningRecipe();
825 while (
auto *PrevPhi =
826 dyn_cast_or_null<VPFirstOrderRecurrencePHIRecipe>(Previous)) {
827 assert(PrevPhi->getParent() == FOR->getParent());
829 Previous = PrevPhi->getBackedgeValue()->getDefiningRecipe();
838 if (isa<VPHeaderPHIRecipe>(Previous))
843 auto *RecurSplice = cast<VPInstruction>(
845 {FOR, FOR->getBackedgeValue()}));
847 FOR->replaceAllUsesWith(RecurSplice);
850 RecurSplice->setOperand(0, FOR);
857 for (
unsigned I = 0;
I !=
Users.size(); ++
I) {
859 if (!Cur || isa<VPHeaderPHIRecipe>(Cur))
862 Users.insert(V->user_begin(), V->user_end());
864 return Users.takeVector();
870 auto *PhiR = dyn_cast<VPReductionPHIRecipe>(&R);
879 if (
auto *RecWithFlags = dyn_cast<VPRecipeWithIRFlags>(U)) {
880 RecWithFlags->dropPoisonGeneratingFlags();
888 if (
auto *Blend = dyn_cast<VPBlendRecipe>(&R)) {
889 VPValue *Inc0 = Blend->getIncomingValue(0);
890 for (
unsigned I = 1;
I != Blend->getNumIncomingValues(); ++
I)
891 if (Inc0 != Blend->getIncomingValue(
I))
894 Blend->eraseFromParent();
901 VPValue *Trunc = R.getVPSingleValue();
904 if (TruncTy == ATy) {
908 if (isa<VPReplicateRecipe>(&R))
912 unsigned ExtOpcode =
match(R.getOperand(0),
m_SExt(m_VPValue()))
917 VPC->insertBefore(&R);
921 VPC->insertBefore(&R);
929 R.getParent()->getPlan()->getCanonicalIV()->getScalarType(),
933 auto *R = dyn_cast<VPRecipeBase>(U);
936 for (
VPValue *VPV : R->definedValues())
944 return R.getVPSingleValue()->replaceAllUsesWith(
A);
952 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
965 unsigned NumProcessedRecipes = 0;
974 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
981 VPValue *ResultVPV = R.getVPSingleValue();
983 unsigned NewResSizeInBits = MinBWs.
lookup(UI);
984 if (!NewResSizeInBits)
988 NumProcessedRecipes++;
994 if (isa<VPReplicateRecipe, VPWidenCastRecipe>(&R)) {
1004 if (!
Op->isLiveIn())
1006 auto *UV = dyn_cast_or_null<Instruction>(
Op->getUnderlyingValue());
1009 return !isa<VPWidenRecipe, VPWidenSelectRecipe>(U);
1013 ProcessedTruncs[
Op] =
nullptr;
1014 NumProcessedRecipes += 1;
1024 (void)OldResSizeInBits;
1031 if (
auto *VPW = dyn_cast<VPRecipeWithIRFlags>(&R))
1032 VPW->dropPoisonGeneratingFlags();
1034 if (OldResSizeInBits != NewResSizeInBits) {
1038 Ext->insertAfter(&R);
1040 Ext->setOperand(0, ResultVPV);
1041 assert(OldResSizeInBits > NewResSizeInBits &&
"Nothing to shrink?");
1044 "Only ICmps should not need extending the result.");
1046 assert(!isa<VPWidenStoreRecipe>(&R) &&
"stores cannot be narrowed");
1047 if (isa<VPWidenLoadRecipe>(&R))
1051 unsigned StartIdx = isa<VPWidenSelectRecipe>(&R) ? 1 : 0;
1052 for (
unsigned Idx = StartIdx;
Idx != R.getNumOperands(); ++
Idx) {
1053 auto *
Op = R.getOperand(
Idx);
1054 unsigned OpSizeInBits =
1056 if (OpSizeInBits == NewResSizeInBits)
1058 assert(OpSizeInBits > NewResSizeInBits &&
"nothing to truncate");
1059 auto [ProcessedIter, IterIsEmpty] =
1060 ProcessedTruncs.
insert({
Op,
nullptr});
1064 : ProcessedIter->second;
1065 R.setOperand(
Idx, NewOp);
1068 ProcessedIter->second = NewOp;
1069 if (!
Op->isLiveIn()) {
1074 auto *OpInst = dyn_cast<Instruction>(
Op->getLiveInIRValue());
1075 bool IsContained = MinBWs.
contains(OpInst);
1076 NumProcessedRecipes += IsContained;
1084 assert(MinBWs.
size() == NumProcessedRecipes &&
1085 "some entries in MinBWs haven't been processed");
1140 VPValue *StartV = CanonicalIVPHI->getStartValue();
1142 auto *CanonicalIVIncrement =
1143 cast<VPInstruction>(CanonicalIVPHI->getBackedgeValue());
1146 CanonicalIVIncrement->dropPoisonGeneratingFlags();
1147 DebugLoc DL = CanonicalIVIncrement->getDebugLoc();
1157 VPValue *TripCount, *IncrementValue;
1162 IncrementValue = CanonicalIVIncrement;
1168 IncrementValue = CanonicalIVPHI;
1179 DL,
"active.lane.mask.entry");
1184 LaneMaskPhi->insertAfter(CanonicalIVPHI);
1190 auto *InLoopIncrement =
1192 {IncrementValue}, {
false,
false},
DL);
1194 {InLoopIncrement, TripCount},
DL,
1195 "active.lane.mask.next");
1212 auto *FoundWidenCanonicalIVUser =
1214 [](
VPUser *U) { return isa<VPWidenCanonicalIVRecipe>(U); });
1216 [](
VPUser *U) { return isa<VPWidenCanonicalIVRecipe>(U); }) <=
1218 "Must have at most one VPWideCanonicalIVRecipe");
1220 auto *WideCanonicalIV =
1221 cast<VPWidenCanonicalIVRecipe>(*FoundWidenCanonicalIVUser);
1222 WideCanonicalIVs.
push_back(WideCanonicalIV);
1229 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
1230 if (WidenOriginalIV && WidenOriginalIV->isCanonical())
1231 WideCanonicalIVs.
push_back(WidenOriginalIV);
1238 for (
auto *Wide : WideCanonicalIVs) {
1240 auto *HeaderMask = dyn_cast<VPInstruction>(U);
1241 if (!HeaderMask || HeaderMask->getOpcode() != Instruction::ICmp ||
1243 HeaderMask->getOperand(1) != BTC)
1246 assert(HeaderMask->getOperand(0) == Wide &&
1247 "WidenCanonicalIV must be the first operand of the compare");
1255 VPlan &Plan,
bool UseActiveLaneMaskForControlFlow,
1258 UseActiveLaneMaskForControlFlow) &&
1259 "DataAndControlFlowWithoutRuntimeCheck implies "
1260 "UseActiveLaneMaskForControlFlow");
1262 auto FoundWidenCanonicalIVUser =
1264 [](
VPUser *U) { return isa<VPWidenCanonicalIVRecipe>(U); });
1265 assert(FoundWidenCanonicalIVUser &&
1266 "Must have widened canonical IV when tail folding!");
1267 auto *WideCanonicalIV =
1268 cast<VPWidenCanonicalIVRecipe>(*FoundWidenCanonicalIVUser);
1270 if (UseActiveLaneMaskForControlFlow) {
1277 "active.lane.mask");
1284 HeaderMask->replaceAllUsesWith(LaneMask);
1312 VPValue *StartV = CanonicalIVPHI->getStartValue();
1316 EVLPhi->insertAfter(CanonicalIVPHI);
1319 VPEVL->
insertBefore(*Header, Header->getFirstNonPhi());
1321 auto *CanonicalIVIncrement =
1322 cast<VPInstruction>(CanonicalIVPHI->getBackedgeValue());
1324 if (
unsigned IVSize = CanonicalIVPHI->getScalarType()->getScalarSizeInBits();
1327 : Instruction::ZExt,
1328 OpVPEVL, CanonicalIVPHI->getScalarType());
1333 {CanonicalIVIncrement->hasNoUnsignedWrap(),
1334 CanonicalIVIncrement->hasNoSignedWrap()},
1335 CanonicalIVIncrement->
getDebugLoc(),
"index.evl.next");
1336 NextEVLIV->insertBefore(CanonicalIVIncrement);
1337 EVLPhi->addOperand(NextEVLIV);
1341 auto *MemR = dyn_cast<VPWidenMemoryRecipe>(U);
1344 assert(!MemR->isReverse() &&
1345 "Reversed memory operations not supported yet.");
1346 VPValue *OrigMask = MemR->getMask();
1347 assert(OrigMask &&
"Unmasked widen memory recipe when folding tail");
1348 VPValue *NewMask = HeaderMask == OrigMask ? nullptr : OrigMask;
1349 if (
auto *L = dyn_cast<VPWidenLoadRecipe>(MemR)) {
1352 L->replaceAllUsesWith(
N);
1353 L->eraseFromParent();
1354 }
else if (
auto *S = dyn_cast<VPWidenStoreRecipe>(MemR)) {
1357 S->eraseFromParent();
1366 CanonicalIVPHI->replaceAllUsesWith(EVLPhi);
1367 CanonicalIVIncrement->setOperand(0, CanonicalIVPHI);
1377 auto collectPoisonGeneratingInstrsInBackwardSlice([&](
VPRecipeBase *Root) {
1382 while (!Worklist.
empty()) {
1383 VPRecipeBase *CurRec = Worklist.back();
1384 Worklist.pop_back();
1386 if (!Visited.insert(CurRec).second)
1393 if (isa<VPWidenMemoryRecipe>(CurRec) || isa<VPInterleaveRecipe>(CurRec) ||
1394 isa<VPScalarIVStepsRecipe>(CurRec) || isa<VPHeaderPHIRecipe>(CurRec))
1400 if (auto *RecWithFlags = dyn_cast<VPRecipeWithIRFlags>(CurRec)) {
1402 using namespace llvm::VPlanPatternMatch;
1408 if (match(RecWithFlags, m_Or(m_VPValue(A), m_VPValue(B))) &&
1409 RecWithFlags->isDisjoint()) {
1410 VPBuilder Builder(RecWithFlags);
1411 VPInstruction *New = Builder.createOverflowingOp(
1412 Instruction::Add, {A, B}, {false, false},
1413 RecWithFlags->getDebugLoc());
1414 RecWithFlags->replaceAllUsesWith(New);
1415 RecWithFlags->eraseFromParent();
1418 RecWithFlags->dropPoisonGeneratingFlags();
1420 Instruction *Instr = dyn_cast_or_null<Instruction>(
1421 CurRec->getVPSingleValue()->getUnderlyingValue());
1423 assert((!Instr || !Instr->hasPoisonGeneratingFlags()) &&
1424 "found instruction with poison generating flags not covered by "
1425 "VPRecipeWithIRFlags");
1439 for (
VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {
1441 if (
auto *WidenRec = dyn_cast<VPWidenMemoryRecipe>(&Recipe)) {
1442 Instruction &UnderlyingInstr = WidenRec->getIngredient();
1443 VPRecipeBase *AddrDef = WidenRec->getAddr()->getDefiningRecipe();
1444 if (AddrDef && WidenRec->isConsecutive() &&
1445 BlockNeedsPredication(UnderlyingInstr.
getParent()))
1446 collectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
1447 }
else if (
auto *InterleaveRec = dyn_cast<VPInterleaveRecipe>(&Recipe)) {
1448 VPRecipeBase *AddrDef = InterleaveRec->getAddr()->getDefiningRecipe();
1452 InterleaveRec->getInterleaveGroup();
1453 bool NeedPredication =
false;
1455 I < NumMembers; ++
I) {
1458 NeedPredication |= BlockNeedsPredication(Member->getParent());
1461 if (NeedPredication)
1462 collectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
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
iv Induction Variable Users
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.
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
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.
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 input value IV value to the corresponding value of an IV with different s...
A recipe for generating the phi node for the current index of elements, adjusted in accordance with E...
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()
DebugLoc getDebugLoc() const
Returns the debug location of the recipe.
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...
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.
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
bool hasVF(ElementCount VF)
bool hasUF(unsigned UF) const
void setVF(ElementCount VF)
VPValue * getOrAddLiveIn(Value *V)
Gets the live-in VPValue for V or adds a new live-in (if none exists yet) for V.
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
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
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 load operations with vector-predication intrinsics, using the address to load f...
A recipe for widening load operations, using the address to load from and an optional mask.
A recipe for widening select instructions.
A recipe for widening store operations with vector-predication intrinsics, using the value to store,...
A recipe for widening store operations, using the stored value, the address to store to and an option...