61 cl::desc(
"Use dot format instead of plain text when dumping VPlans"));
63#define DEBUG_TYPE "vplan"
65#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
69 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() :
nullptr);
89 : SubclassID(SC), UnderlyingVal(UV), Def(Def) {
91 Def->addDefinedValue(
this);
95 assert(Users.empty() &&
"trying to delete a VPValue with remaining users");
97 Def->removeDefinedValue(
this);
100#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
111 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() :
nullptr);
117 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(
this);
119 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() :
nullptr);
126 return cast_or_null<VPRecipeBase>(
Def);
130 return cast_or_null<VPRecipeBase>(
Def);
138 while ((Next = Next->getParent()))
144 for (
unsigned i = 0; i < WorkList.
size(); i++) {
145 T *Current = WorkList[i];
146 if (Current->getNumPredecessors() == 0)
148 auto &Predecessors = Current->getPredecessors();
149 WorkList.
insert(Predecessors.begin(), Predecessors.end());
164 return cast<VPBasicBlock>(
Block);
171 return cast<VPBasicBlock>(
Block);
177 "Can only set plan on its entry or preheader block.");
186 return cast<VPBasicBlock>(
Block);
193 return cast<VPBasicBlock>(
Block);
197 if (!Successors.empty() || !Parent)
200 "Block w/o successors not the exiting block of its parent.");
205 if (!Predecessors.empty() || !Parent)
208 "Block w/o predecessors not the entry of its parent.");
219 while (It !=
end() && It->isPhi())
228 : VF(VF), UF(UF),
CFG(DT), LI(LI), Builder(Builder), ILV(ILV), Plan(Plan),
230 TypeAnalysis(Plan->getCanonicalIV()->getScalarType(), Ctx) {}
234 return Def->getLiveInIRValue();
248 if (!VecPart->getType()->isVectorTy()) {
249 assert(
Instance.Lane.isFirstLane() &&
"cannot get lane > 0 for scalar");
265 "Trying to access a single scalar per part but has multiple scalars "
274 auto GetBroadcastInstrs = [
this, Def](
Value *V) {
275 bool SafeToHoist = Def->isDefinedOutsideVectorRegions();
283 if (LoopVectorPreHeader)
295 assert(Def->isLiveIn() &&
"expected a live-in");
298 Value *IRV = Def->getLiveInIRValue();
299 Value *
B = GetBroadcastInstrs(IRV);
304 Value *ScalarValue =
get(Def, {Part, 0});
308 set(Def, ScalarValue, Part);
319 assert((isa<VPWidenIntOrFpInductionRecipe>(Def->getDefiningRecipe()) ||
320 isa<VPScalarIVStepsRecipe>(Def->getDefiningRecipe()) ||
321 isa<VPExpandSCEVRecipe>(Def->getDefiningRecipe())) &&
322 "unexpected recipe found to be invariant");
327 auto *LastInst = cast<Instruction>(
get(Def, {Part, LastLane}));
333 isa<PHINode>(LastInst)
344 Value *VectorValue =
nullptr;
346 VectorValue = GetBroadcastInstrs(ScalarValue);
347 set(Def, VectorValue, Part);
352 set(Def, Undef, Part);
355 VectorValue =
get(Def, Part);
362 VPRegionBlock *LoopRegion = R->getParent()->getEnclosingLoopRegion();
370 if (
LVer && (isa<LoadInst>(Orig) || isa<StoreInst>(Orig)))
379 if (
Instruction *ToI = dyn_cast<Instruction>(To)) {
401 << DIL->getFilename() <<
" Line: " << DIL->getLine());
425 for (
VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
430 assert(PredBB &&
"Predecessor basic-block not found building successor.");
434 auto *TermBr = dyn_cast<BranchInst>(PredBBTerminator);
435 if (isa<UnreachableInst>(PredBBTerminator)) {
436 assert(PredVPSuccessors.size() == 1 &&
437 "Predecessor ending w/o branch must have single successor.");
438 DebugLoc DL = PredBBTerminator->getDebugLoc();
442 }
else if (TermBr && !TermBr->isConditional()) {
443 TermBr->setSuccessor(0, NewBB);
447 unsigned idx = PredVPSuccessors.front() ==
this ? 0 : 1;
448 assert(!TermBr->getSuccessor(idx) &&
449 "Trying to reset an existing successor block.");
450 TermBr->setSuccessor(idx, NewBB);
458 assert(getHierarchicalSuccessors().
size() <= 2 &&
459 "VPIRBasicBlock can have at most two successors at the moment!");
461 executeRecipes(State, getIRBasicBlock());
462 if (getSingleSuccessor()) {
463 assert(isa<UnreachableInst>(getIRBasicBlock()->getTerminator()));
466 getIRBasicBlock()->getTerminator()->eraseFromParent();
469 for (
VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
472 assert(PredBB &&
"Predecessor basic-block not found building successor.");
476 auto *TermBr = cast<BranchInst>(PredBBTerminator);
480 unsigned idx = PredVPSuccessors.front() ==
this ? 0 : 1;
481 assert(!TermBr->getSuccessor(idx) &&
482 "Trying to reset an existing successor block.");
483 TermBr->setSuccessor(idx, IRBB);
495 auto *R = dyn_cast<VPRegionBlock>(BB);
496 return R && !R->isReplicator();
501 !((SingleHPred = getSingleHierarchicalPredecessor()) &&
504 (SingleHPred->
getParent() == getEnclosingLoopRegion() &&
505 !IsLoopRegion(SingleHPred))) &&
506 !(Replica && getPredecessors().empty())) {
516 NewBB = createEmptyBasicBlock(State->
CFG);
529 executeRecipes(State, NewBB);
534 for (
auto *Def : R.definedValues())
535 Def->replaceAllUsesWith(NewValue);
537 for (
unsigned I = 0, E = R.getNumOperands();
I != E;
I++)
538 R.setOperand(
I, NewValue);
544 <<
" in BB:" << BB->
getName() <<
'\n');
556 assert((SplitAt == end() || SplitAt->getParent() ==
this) &&
557 "can only split at a position in the same block");
582 if (
P &&
P->isReplicator()) {
584 assert(!cast<VPRegionBlock>(
P)->isReplicator() &&
585 "unexpected nested replicate regions");
594 "block with multiple successors doesn't have a recipe as terminator");
607 "conditional branch recipe");
614 "block with 0 or 1 successors terminated by conditional branch recipe");
634#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
636 if (getSuccessors().empty()) {
637 O << Indent <<
"No successors\n";
639 O << Indent <<
"Successor(s): ";
641 for (
auto *Succ : getSuccessors())
642 O << LS << Succ->getName();
649 O << Indent <<
getName() <<
":\n";
651 auto RecipeIndent = Indent +
" ";
657 printSuccessors(O, Indent);
671 bool InRegion = Entry->getParent();
675 Old2NewVPBlocks[BB] = NewBB;
676 if (InRegion && BB->getNumSuccessors() == 0) {
677 assert(!Exiting &&
"Multiple exiting blocks?");
681 assert((!InRegion || Exiting) &&
"regions must have a single exiting block");
688 NewPreds.
push_back(Old2NewVPBlocks[Pred]);
693 NewSuccs.
push_back(Old2NewVPBlocks[Succ]);
701 for (
const auto &[OldBB, NewBB] :
704 for (
const auto &[OldPred, NewPred] :
705 zip(OldBB->getPredecessors(), NewBB->getPredecessors()))
706 assert(NewPred == Old2NewVPBlocks[OldPred] &&
"Different predecessors");
708 for (
const auto &[OldSucc, NewSucc] :
709 zip(OldBB->successors(), NewBB->successors()))
710 assert(NewSucc == Old2NewVPBlocks[OldSucc] &&
"Different successors");
714 return std::make_pair(Old2NewVPBlocks[Entry],
715 Exiting ? Old2NewVPBlocks[Exiting] :
nullptr);
719 const auto &[NewEntry, NewExiting] =
cloneFrom(getEntry());
723 Block->setParent(NewRegion);
731 Block->dropAllReferences(NewValue);
738 if (!isReplicator()) {
755 Block->execute(State);
762 assert(!State->
Instance &&
"Replicating a Region with non-null instance.");
767 for (
unsigned Part = 0,
UF = State->
UF; Part <
UF; ++Part) {
776 Block->execute(State);
793 if (!isReplicator()) {
800 <<
": vector loop backedge\n");
801 Cost += BackedgeCost;
816 VPBasicBlock *Then = cast<VPBasicBlock>(getEntry()->getSuccessors()[0]);
827#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
830 O << Indent << (isReplicator() ?
"<xVFxUF> " :
"<x1> ") <<
getName() <<
": {";
831 auto NewIndent = Indent +
" ";
836 O << Indent <<
"}\n";
838 printSuccessors(O, Indent);
843 for (
auto &KV : LiveOuts)
850 Block->dropAllReferences(&DummyValue);
854 Preheader->dropAllReferences(&DummyValue);
857 for (
VPValue *VPV : VPLiveInsToFree)
859 if (BackedgeTakenCount)
860 delete BackedgeTakenCount;
864 bool RequiresScalarEpilogueCheck,
865 bool TailFolded,
Loop *TheLoop) {
868 auto Plan = std::make_unique<VPlan>(Entry, VecPreheader);
876 auto *TopRegion =
new VPRegionBlock(HeaderVPBB, LatchVPBB,
"vector loop",
884 if (!RequiresScalarEpilogueCheck) {
915 ScalarLatchTerm->getDebugLoc(),
"cmp.n");
917 ScalarLatchTerm->getDebugLoc());
922 Value *CanonicalIVStartValue,
925 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
928 ConstantInt::get(TripCountV->
getType(), 1),
929 "trip.count.minus.1");
930 BackedgeTakenCount->setUnderlyingValue(TCMO);
933 VectorTripCount.setUnderlyingValue(VectorTripCountV);
937 VFxUF.setUnderlyingValue(
943 if (CanonicalIVStartValue) {
944 VPValue *VPV = getOrAddLiveIn(CanonicalIVStartValue);
945 auto *
IV = getCanonicalIV();
948 return isa<VPScalarIVStepsRecipe>(U) ||
949 isa<VPScalarCastRecipe>(U) ||
950 isa<VPDerivedIVRecipe>(U) ||
951 cast<VPInstruction>(U)->getOpcode() ==
954 "the canonical IV should only be used by its increment or "
955 "ScalarIVSteps when resetting the start value");
956 IV->setOperand(0, VPV);
967 R.moveBefore(*IRMiddleVPBB, IRMiddleVPBB->
end());
989 cast<BranchInst>(VectorPreHeader->
getTerminator())->setSuccessor(0,
nullptr);
999 cast<VPBasicBlock>(getVectorLoopRegion()->getSingleSuccessor());
1006 assert((MiddleSuccs.size() == 1 || MiddleSuccs.size() == 2) &&
1007 "middle block has unexpected successors");
1009 MiddleSuccs.size() == 1 ? MiddleSuccs[0] : MiddleSuccs[1]);
1010 assert(!isa<VPIRBasicBlock>(ScalarPhVPBB) &&
1011 "scalar preheader cannot be wrapped already");
1025 Block->execute(State);
1032 VPBasicBlock *Header = getVectorLoopRegion()->getEntryBasicBlock();
1035 if (isa<VPWidenPHIRecipe>(&R))
1038 if (isa<VPWidenPointerInductionRecipe>(&R) ||
1039 isa<VPWidenIntOrFpInductionRecipe>(&R)) {
1041 if (isa<VPWidenIntOrFpInductionRecipe>(&R)) {
1042 Phi = cast<PHINode>(State->
get(R.getVPSingleValue(), 0));
1044 auto *WidenPhi = cast<VPWidenPointerInductionRecipe>(&R);
1046 "recipe generating only scalars should have been replaced");
1047 auto *
GEP = cast<GetElementPtrInst>(State->
get(WidenPhi, 0));
1048 Phi = cast<PHINode>(
GEP->getPointerOperand());
1051 Phi->setIncomingBlock(1, VectorLatchBB);
1055 Instruction *Inc = cast<Instruction>(Phi->getIncomingValue(1));
1060 auto *PhiR = cast<VPHeaderPHIRecipe>(&R);
1065 bool SinglePartNeeded =
1066 isa<VPCanonicalIVPHIRecipe>(PhiR) ||
1067 isa<VPFirstOrderRecurrencePHIRecipe, VPEVLBasedIVPHIRecipe>(PhiR) ||
1068 (isa<VPReductionPHIRecipe>(PhiR) &&
1069 cast<VPReductionPHIRecipe>(PhiR)->isOrdered());
1071 isa<VPCanonicalIVPHIRecipe, VPEVLBasedIVPHIRecipe>(PhiR) ||
1072 (isa<VPReductionPHIRecipe>(PhiR) &&
1073 cast<VPReductionPHIRecipe>(PhiR)->isInLoop());
1074 unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->
UF;
1076 for (
unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
1077 Value *Phi = State->
get(PhiR, Part, NeedsScalar);
1079 State->
get(PhiR->getBackedgeValue(),
1080 SinglePartNeeded ? State->
UF - 1 : Part, NeedsScalar);
1081 cast<PHINode>(Phi)->addIncoming(Val, VectorLatchBB);
1087 DominatorTree::VerificationLevel::Fast) &&
1088 "DT not preserved correctly");
1094 return getVectorLoopRegion()->cost(
VF, Ctx);
1097#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1101 if (VFxUF.getNumUsers() > 0) {
1107 if (VectorTripCount.getNumUsers() > 0) {
1110 O <<
" = vector-trip-count";
1113 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
1115 BackedgeTakenCount->printAsOperand(O,
SlotTracker);
1116 O <<
" = backedge-taken count";
1120 if (TripCount->isLiveIn())
1123 O <<
" = original trip-count";
1131 O <<
"VPlan '" <<
getName() <<
"' {";
1135 if (!getPreheader()->empty()) {
1145 if (!LiveOuts.empty())
1147 for (
const auto &KV : LiveOuts) {
1157 RSO <<
Name <<
" for ";
1159 RSO <<
"VF={" << VFs[0];
1168 RSO <<
"UF={" << UFs[0];
1188 assert(LiveOuts.count(PN) == 0 &&
"an exit value for PN already exists");
1189 LiveOuts.insert({PN,
new VPLiveOut(PN, V)});
1200 NewDeepRPOT(NewEntry);
1203 for (
const auto &[OldBB, NewBB] :
1204 zip(VPBlockUtils::blocksOnly<VPBasicBlock>(OldDeepRPOT),
1205 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT))) {
1206 assert(OldBB->getRecipeList().size() == NewBB->getRecipeList().
size() &&
1207 "blocks must have the same number of recipes");
1208 for (
const auto &[OldR, NewR] :
zip(*OldBB, *NewBB)) {
1209 assert(OldR.getNumOperands() == NewR.getNumOperands() &&
1210 "recipes must have the same number of operands");
1211 assert(OldR.getNumDefinedValues() == NewR.getNumDefinedValues() &&
1212 "recipes must define the same number of operands");
1213 for (
const auto &[OldV, NewV] :
1214 zip(OldR.definedValues(), NewR.definedValues()))
1215 Old2NewVPValues[OldV] = NewV;
1221 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT)) {
1223 for (
unsigned I = 0, E = NewR.getNumOperands();
I != E; ++
I) {
1225 NewR.setOperand(
I, NewOp);
1233 const auto &[NewEntry, __] =
cloneFrom(Entry);
1236 auto *NewPlan =
new VPlan(NewPreheader, cast<VPBasicBlock>(NewEntry));
1238 for (
VPValue *OldLiveIn : VPLiveInsToFree) {
1239 Old2NewVPValues[OldLiveIn] =
1240 NewPlan->getOrAddLiveIn(OldLiveIn->getLiveInIRValue());
1242 Old2NewVPValues[&VectorTripCount] = &NewPlan->VectorTripCount;
1243 Old2NewVPValues[&VFxUF] = &NewPlan->VFxUF;
1244 if (BackedgeTakenCount) {
1245 NewPlan->BackedgeTakenCount =
new VPValue();
1246 Old2NewVPValues[BackedgeTakenCount] = NewPlan->BackedgeTakenCount;
1248 assert(TripCount &&
"trip count must be set");
1249 if (TripCount->isLiveIn())
1250 Old2NewVPValues[TripCount] =
1251 NewPlan->getOrAddLiveIn(TripCount->getLiveInIRValue());
1259 for (
const auto &[
_, LO] : LiveOuts)
1260 NewPlan->addLiveOut(LO->getPhi(), Old2NewVPValues[LO->getOperand(0)]);
1266 NewPlan->Name =
Name;
1268 "TripCount must have been added to Old2NewVPValues");
1269 NewPlan->TripCount = Old2NewVPValues[TripCount];
1273#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1276 return (isa<VPRegionBlock>(
Block) ?
"cluster_N" :
"N") +
1281 const std::string &
Name =
Block->getName();
1290 OS <<
"digraph VPlan {\n";
1291 OS <<
"graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
1302 for (
auto Line : Lines)
1307 OS <<
"node [shape=rect, fontname=Courier, fontsize=30]\n";
1308 OS <<
"edge [fontname=Courier, fontsize=30]\n";
1309 OS <<
"compound=true\n";
1329 bool Hidden,
const Twine &Label) {
1334 OS << Indent << getUID(
Tail) <<
" -> " << getUID(Head);
1335 OS <<
" [ label=\"" << Label <<
'\"';
1337 OS <<
" ltail=" << getUID(
From);
1339 OS <<
" lhead=" << getUID(To);
1341 OS <<
"; splines=none";
1346 auto &Successors =
Block->getSuccessors();
1347 if (Successors.size() == 1)
1348 drawEdge(
Block, Successors.front(),
false,
"");
1349 else if (Successors.size() == 2) {
1350 drawEdge(
Block, Successors.front(),
false,
"T");
1351 drawEdge(
Block, Successors.back(),
false,
"F");
1353 unsigned SuccessorNumber = 0;
1380 EmitLine(Line,
" +\n");
1381 EmitLine(
Lines.back(),
"\n");
1384 OS << Indent <<
"]\n";
1390 OS << Indent <<
"subgraph " << getUID(
Region) <<
" {\n";
1392 OS << Indent <<
"fontname=Courier\n"
1393 << Indent <<
"label=\""
1401 OS << Indent <<
"}\n";
1406 if (
auto *Inst = dyn_cast<Instruction>(V)) {
1407 if (!Inst->getType()->isVoidTy()) {
1408 Inst->printAsOperand(O,
false);
1411 O << Inst->getOpcodeName() <<
" ";
1412 unsigned E = Inst->getNumOperands();
1414 Inst->getOperand(0)->printAsOperand(O,
false);
1415 for (
unsigned I = 1;
I < E; ++
I)
1416 Inst->getOperand(
I)->printAsOperand(O <<
", ",
false);
1419 V->printAsOperand(O,
false);
1424template void DomTreeBuilder::Calculate<VPDominatorTree>(
VPDominatorTree &DT);
1427 replaceUsesWithIf(New, [](
VPUser &,
unsigned) {
return true; });
1439 for (
unsigned J = 0; J < getNumUsers();) {
1441 bool RemovedUser =
false;
1457#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1475 visitBlock(
Base, Old2New, IAI);
1479void VPInterleavedAccessInfo::visitBlock(
VPBlockBase *
Block, Old2NewTy &Old2New,
1483 if (isa<VPWidenPHIRecipe>(&VPI))
1485 assert(isa<VPInstruction>(&VPI) &&
"Can only handle VPInstructions");
1486 auto *VPInst = cast<VPInstruction>(&VPI);
1488 auto *Inst = dyn_cast_or_null<Instruction>(VPInst->getUnderlyingValue());
1495 auto NewIGIter = Old2New.find(IG);
1496 if (NewIGIter == Old2New.end())
1498 IG->getFactor(), IG->isReverse(), IG->getAlign());
1500 if (Inst == IG->getInsertPos())
1501 Old2New[IG]->setInsertPos(VPInst);
1503 InterleaveGroupMap[VPInst] = Old2New[IG];
1504 InterleaveGroupMap[VPInst]->insertMember(
1505 VPInst, IG->getIndex(Inst),
1506 Align(IG->isReverse() ? (-1) *
int(IG->getFactor())
1507 : IG->getFactor()));
1510 visitRegion(
Region, Old2New, IAI);
1521void VPSlotTracker::assignName(
const VPValue *V) {
1522 assert(!VPValue2Name.contains(V) &&
"VPValue already has a name!");
1523 auto *UV = V->getUnderlyingValue();
1525 VPValue2Name[V] = (
Twine(
"vp<%") +
Twine(NextSlot) +
">").str();
1534 UV->printAsOperand(S,
false);
1535 assert(!
Name.empty() &&
"Name cannot be empty.");
1539 const auto &[
A,
_] = VPValue2Name.insert({V, BaseName});
1542 if (
V->isLiveIn() && isa<ConstantInt, ConstantFP>(UV))
1547 const auto &[
C, UseInserted] = BaseName2Version.insert({BaseName, 0});
1550 A->second = (BaseName +
Twine(
".") +
Twine(
C->second)).str();
1554void VPSlotTracker::assignNames(
const VPlan &
Plan) {
1556 assignName(&
Plan.VFxUF);
1557 assignName(&
Plan.VectorTripCount);
1558 if (
Plan.BackedgeTakenCount)
1559 assignName(
Plan.BackedgeTakenCount);
1567 VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
1571void VPSlotTracker::assignNames(
const VPBasicBlock *VPBB) {
1573 for (
VPValue *Def : Recipe.definedValues())
1578 std::string
Name = VPValue2Name.lookup(V);
1592 "VPValue defined by a recipe in a VPlan?");
1595 if (
auto *UV = V->getUnderlyingValue()) {
1598 UV->printAsOperand(S,
false);
1599 return (
Twine(
"ir<") +
Name +
">").str();
1606 return all_of(Def->users(),
1607 [Def](
const VPUser *U) { return U->onlyFirstLaneUsed(Def); });
1611 return all_of(Def->users(),
1612 [Def](
const VPUser *U) { return U->onlyFirstPartUsed(Def); });
1620 if (
auto *E = dyn_cast<SCEVConstant>(Expr))
1622 else if (
auto *E = dyn_cast<SCEVUnknown>(Expr))
1633 if (isa<VPActiveLaneMaskPHIRecipe>(V))
1636 auto IsWideCanonicalIV = [](
VPValue *
A) {
1637 return isa<VPWidenCanonicalIVRecipe>(
A) ||
1638 (isa<VPWidenIntOrFpInductionRecipe>(
A) &&
1639 cast<VPWidenIntOrFpInductionRecipe>(
A)->isCanonical());
1646 IsWideCanonicalIV(
A));
1654 assert(!
Range.isEmpty() &&
"Trying to test an empty VF range.");
1655 bool PredicateAtRangeStart = Predicate(
Range.Start);
1658 if (Predicate(TmpVF) != PredicateAtRangeStart) {
1663 return PredicateAtRangeStart;
1673 auto MaxVFTimes2 = MaxVF * 2;
1676 auto Plan = buildVPlan(SubRange);
1678 VPlans.push_back(std::move(
Plan));
1687 "Multiple VPlans for VF.");
1696#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1698 if (VPlans.empty()) {
1699 O <<
"LV: No VPlans built.\n";
1702 for (
const auto &
Plan : VPlans)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
dxil pretty DXIL Metadata Pretty Printer
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 void dumpEdges(CFGMST< Edge, BBInfo > &MST, GCOVFunction &GF)
Generic dominator tree construction - this file provides routines to construct immediate dominator in...
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iv Induction Variable Users
This file provides a LoopVectorizationPlanner class.
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
static StringRef getName(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file implements dominator tree analysis for a single level of a VPlan's H-CFG.
static T * getPlanEntry(T *Start)
static void replaceVPBBWithIRVPBB(VPBasicBlock *VPBB, BasicBlock *IRBB)
Replace VPBB with a VPIRBasicBlock wrapping IRBB.
static bool hasConditionalTerminator(const VPBasicBlock *VPBB)
static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry, DenseMap< VPValue *, VPValue * > &Old2NewVPValues)
static std::pair< VPBlockBase *, VPBlockBase * > cloneFrom(VPBlockBase *Entry)
static cl::opt< bool > PrintVPlansInDotFormat("vplan-print-in-dot-format", cl::Hidden, cl::desc("Use dot format instead of plain text when dumping VPlans"))
This file contains the declarations of the Vectorization Plan base classes:
static bool IsCondBranch(unsigned BrOpc)
static const uint32_t IV[8]
LLVM Basic Block Representation.
void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW=nullptr, bool ShouldPreserveUseListOrder=false, bool IsForDebug=false) const
Print the basic block to an output stream with an optional AssemblyAnnotationWriter.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
static ConstantInt * getTrue(LLVMContext &Context)
std::optional< const DILocation * > cloneByMultiplyingDuplicationFactor(unsigned DF) const
Returns a new DILocation with duplication factor DF * current duplication factor encoded in the discr...
This class represents an Operation in the Expression.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Core dominator tree base class.
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
constexpr bool isScalar() const
Exactly one element.
bool shouldEmitDebugInfoForProfiling() const
Returns true if we should emit debug info for profiling.
DomTreeT & getDomTree()
Flush DomTree updates and return DomTree.
void applyUpdates(ArrayRef< typename DomTreeT::UpdateType > Updates)
Submit updates to all available trees.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
Common base class shared among various IRBuilders.
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
UnreachableInst * CreateUnreachable()
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
IntegerType * getInt32Ty()
Fetch the type representing a 32-bit integer.
BasicBlock * GetInsertBlock() const
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
InsertPoint saveIP() const
Returns the current insert point.
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
void restoreIP(InsertPoint IP)
Sets the current insert point to a previously-saved location.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
InnerLoopVectorizer vectorizes loops which contain only one basic block to a specified vectorization ...
static InstructionCost getInvalid(CostType Val=0)
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
The group of interleaved loads/stores sharing the same stride and close to each other.
Drive the analysis of interleaved memory accesses in the loop.
InterleaveGroup< Instruction > * getInterleaveGroup(const Instruction *Instr) const
Get the interleave group that Instr belongs to.
This is an important class for using LLVM in a threaded context.
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
LoopT * AllocateLoop(ArgsTy &&...Args)
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
VPlan & getPlanFor(ElementCount VF) const
Return the VPlan for VF.
void buildVPlans(ElementCount MinVF, ElementCount MaxVF)
Build VPlans for power-of-2 VF's between MinVF and MaxVF inclusive, according to the information gath...
static bool getDecisionAndClampRange(const std::function< bool(ElementCount)> &Predicate, VFRange &Range)
Test a Predicate on a Range of VF's.
void printPlans(raw_ostream &O)
void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)
Add the noalias annotations to VersionedInst.
Represents a single loop in the control flow graph.
void eraseFromParent()
This method unlinks 'this' from the containing function and deletes it.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
size_type size() const
Determine the number of elements in the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
This class provides computation of slot numbers for LLVM Assembly writing.
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.
StringRef - Represent a constant reference to a string, i.e.
std::pair< StringRef, StringRef > split(char Separator) const
Split into two substrings around the first occurrence of a separator character.
StringRef rtrim(char Char) const
Return string with consecutive Char characters starting from the right removed.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
static IntegerType * getInt1Ty(LLVMContext &C)
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
This function has undefined behavior.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
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.
VPBasicBlock * clone() override
Clone the current block and it's recipes, without updating the operands of the cloned recipes.
RecipeListTy::iterator iterator
Instruction iterators...
void execute(VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPBasicBlock,...
iterator begin()
Recipe iterator methods.
InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override
Return the cost of this VPBasicBlock.
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
VPRegionBlock * getEnclosingLoopRegion()
void dropAllReferences(VPValue *NewValue) override
Replace all operands of VPUsers in the block with NewValue and also replaces all uses of VPValues def...
VPBasicBlock * splitAt(iterator SplitAt)
Split current block at SplitAt by inserting a new block between the current block and its successors ...
void executeRecipes(VPTransformState *State, BasicBlock *BB)
Execute the recipes in the IR basic block BB.
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print this VPBsicBlock to O, prefixing all lines with Indent.
bool isExiting() const
Returns true if the block is exiting it's parent region.
VPRecipeBase * getTerminator()
If the block has multiple successors, return the branch recipe terminating the block.
const VPRecipeBase & back() const
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
void setSuccessors(ArrayRef< VPBlockBase * > NewSuccs)
Set each VPBasicBlock in NewSuccss as successor of this VPBlockBase.
VPRegionBlock * getParent()
const VPBasicBlock * getExitingBasicBlock() const
size_t getNumSuccessors() const
iterator_range< VPBlockBase ** > successors()
void printSuccessors(raw_ostream &O, const Twine &Indent) const
Print the successors of this block to O, prefixing all lines with Indent.
void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
VPBlockBase * getEnclosingBlockWithPredecessors()
const VPBlocksTy & getPredecessors() const
static void deleteCFG(VPBlockBase *Entry)
Delete all blocks reachable from a given VPBlockBase, inclusive.
void setPlan(VPlan *ParentPlan)
Sets the pointer of the plan containing the block.
VPBlockBase * getSingleHierarchicalSuccessor()
VPBlockBase * getSinglePredecessor() const
const VPBlocksTy & getHierarchicalSuccessors()
VPBlockBase * getEnclosingBlockWithSuccessors()
An Enclosing Block of a block B is any block containing B, including B itself.
const VPBasicBlock * getEntryBasicBlock() const
const VPBlocksTy & getSuccessors() const
Helper for GraphTraits specialization that traverses through VPRegionBlocks.
static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBase NewBlock 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.
VPlan-based builder utility analogous to IRBuilder.
This class augments a recipe with a set of VPValues defined by the recipe.
void dump() const
Dump the VPDef to stderr (for debugging).
virtual void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const =0
Each concrete VPDef prints itself.
Recipe to expand a SCEV expression.
A special type of VPBasicBlock that wraps an existing IR basic block.
void execute(VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPBasicBlock,...
This is a concrete Recipe that models a single VPlan-level instruction.
VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI)
In what follows, the term "input IR" refers to code that is fed into the vectorizer whereas the term ...
Value * getAsRuntimeExpr(IRBuilderBase &Builder, const ElementCount &VF) const
Returns an expression describing the lane index that can be used at runtime.
static VPLane getFirstLane()
@ ScalableLast
For ScalableLast, Lane is the offset from the start of the last N-element subvector in a scalable vec...
@ First
For First, Lane is the index into the first N elements of a fixed-vector <N x <ElTy>> or a scalable v...
A value that is used outside the VPlan.
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
VPBasicBlock * getParent()
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
VPRegionBlock * clone() override
Clone all blocks in the single-entry single-exit region of the block and their recipes without updati...
const VPBlockBase * getEntry() const
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
void dropAllReferences(VPValue *NewValue) override
Replace all operands of VPUsers in the block with NewValue and also replaces all uses of VPValues def...
InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override
Return the cost of the block.
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print this VPRegionBlock to O (recursively), prefixing all lines with Indent.
void execute(VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPRegionBlock,...
const VPBlockBase * getExiting() const
VPBasicBlock * getPreheaderVPBB()
Returns the pre-header VPBasicBlock of the loop region.
This class can be used to assign names to VPValues.
std::string getOrCreateName(const VPValue *V) const
Returns the name assigned to V, if there is one, otherwise try to construct one from the underlying v...
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const
Print the operands to O.
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const
void dump() const
Dump the value to stderr (for debugging).
VPValue(const unsigned char SC, Value *UV=nullptr, VPDef *Def=nullptr)
void print(raw_ostream &OS, VPSlotTracker &Tracker) const
void replaceAllUsesWith(VPValue *New)
unsigned getNumUsers() const
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...
VPDef * Def
Pointer to the VPDef that defines this VPValue.
VPlanPrinter prints a given VPlan to a given output stream.
LLVM_DUMP_METHOD void dump()
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
void printDOT(raw_ostream &O) const
Print this VPlan in DOT format to O.
std::string getName() const
Return a string with the name of the plan and the applicable VFs and UFs.
void prepareToExecute(Value *TripCount, Value *VectorTripCount, Value *CanonicalIVStartValue, VPTransformState &State)
Prepare the plan for execution, setting up the required live-in values.
VPBasicBlock * getEntry()
VPValue & getVectorTripCount()
The vector trip count.
VPValue * getTripCount() const
The trip count of the original loop.
VPValue * getOrCreateBackedgeTakenCount()
The backedge taken count of the original loop.
void addLiveOut(PHINode *PN, VPValue *V)
VPBasicBlock * getPreheader()
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
bool hasVF(ElementCount VF)
void addSCEVExpansion(const SCEV *S, VPValue *V)
InstructionCost cost(ElementCount VF, VPCostContext &Ctx)
Return the cost of this plan.
static VPlanPtr createInitialVPlan(const SCEV *TripCount, ScalarEvolution &PSE, bool RequiresScalarEpilogueCheck, bool TailFolded, Loop *TheLoop)
Create initial VPlan, having an "entry" VPBasicBlock (wrapping original scalar pre-header ) which con...
VPValue * getOrAddLiveIn(Value *V)
Gets the live-in VPValue for V or adds a new live-in (if none exists yet) for V.
LLVM_DUMP_METHOD void dump() const
Dump the plan to stderr (for debugging).
void execute(VPTransformState *State)
Generate the IR code for this VPlan.
void print(raw_ostream &O) const
Print this VPlan to O.
VPValue * getSCEVExpansion(const SCEV *S) const
void printLiveIns(raw_ostream &O) const
Print the live-ins of this VPlan to O.
VPlan * duplicate()
Clone the current VPlan, update all VPValues of the new VPlan and cloned recipes to refer to the clon...
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
StringRef getName() const
Return a constant reference to the value's name.
static VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
static constexpr bool isKnownLT(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
A raw_ostream that writes to an std::string.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
@ C
The default llvm calling convention, compatible with C.
std::string EscapeString(const std::string &Label)
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)
BinaryVPInstruction_match< Op0_t, Op1_t, VPInstruction::ActiveLaneMask > m_ActiveLaneMask(const Op0_t &Op0, const Op1_t &Op1)
VPCanonicalIVPHI_match m_CanonicalIV()
VPScalarIVSteps_match< Op0_t, Op1_t > m_ScalarIVSteps(const Op0_t &Op0, const Op1_t &Op1)
BinaryVPInstruction_match< Op0_t, Op1_t, VPInstruction::BranchOnCount > m_BranchOnCount(const Op0_t &Op0, const Op1_t &Op1)
UnaryVPInstruction_match< Op0_t, VPInstruction::BranchOnCond > m_BranchOnCond(const Op0_t &Op0)
class_match< VPValue > m_VPValue()
Match an arbitrary VPValue and ignore it.
bool isUniformAfterVectorization(const VPValue *VPV)
Returns true if VPV is uniform after vectorization.
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)
Get or create a VPValue that corresponds to the expansion of Expr.
bool onlyFirstPartUsed(const VPValue *Def)
Returns true if only the first part of Def is used.
bool onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used.
bool isHeaderMask(const VPValue *V, VPlan &Plan)
Return true if V is a header mask in Plan.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
auto successors(const MachineBasicBlock *BB)
Value * getRuntimeVF(IRBuilderBase &B, Type *Ty, ElementCount VF)
Return the runtime value for VF.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
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< VPBlockShallowTraversalWrapper< VPBlockBase * > > > vp_depth_first_shallow(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order.
Instruction * propagateMetadata(Instruction *I, ArrayRef< Value * > VL)
Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath, MD_nontemporal,...
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
cl::opt< bool > EnableFSDiscriminator
cl::opt< bool > EnableVPlanNativePath("enable-vplan-native-path", cl::Hidden, cl::desc("Enable VPlan-native vectorization path with " "support for outer loop vectorization."))
std::unique_ptr< VPlan > VPlanPtr
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
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...
Value * createStepForVF(IRBuilderBase &B, Type *Ty, ElementCount VF, int64_t Step)
Return a value for Step multiplied by VF.
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.
unsigned getReciprocalPredBlockProb()
A helper function that returns the reciprocal of the block probability of predicated blocks.
This struct is a compact representation of a valid (non-zero power of two) alignment.
A range of powers-of-2 vectorization factors with fixed start and adjustable end.
Struct to hold various analysis needed for cost computations.
const TargetTransformInfo & TTI
VPIteration represents a single point in the iteration space of the output (vectorized and/or unrolle...
void print(raw_ostream &O) const