56#define DEBUG_TYPE "vplan"
58#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
62 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() :
nullptr);
82 : SubclassID(SC), UnderlyingVal(UV), Def(Def) {
84 Def->addDefinedValue(
this);
88 assert(Users.empty() &&
"trying to delete a VPValue with remaining users");
90 Def->removeDefinedValue(
this);
93#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
104 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() :
nullptr);
110 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(
this);
112 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() :
nullptr);
119 return cast_or_null<VPRecipeBase>(
Def);
123 return cast_or_null<VPRecipeBase>(
Def);
131 while ((Next = Next->getParent()))
137 for (
unsigned i = 0; i < WorkList.
size(); i++) {
138 T *Current = WorkList[i];
139 if (Current->getNumPredecessors() == 0)
141 auto &Predecessors = Current->getPredecessors();
142 WorkList.
insert(Predecessors.begin(), Predecessors.end());
157 return cast<VPBasicBlock>(
Block);
164 return cast<VPBasicBlock>(
Block);
170 "Can only set plan on its entry or preheader block.");
179 return cast<VPBasicBlock>(
Block);
186 return cast<VPBasicBlock>(
Block);
190 if (!Successors.empty() || !Parent)
193 "Block w/o successors not the exiting block of its parent.");
198 if (!Predecessors.empty() || !Parent)
201 "Block w/o predecessors not the entry of its parent.");
212 while (It !=
end() && It->isPhi())
221 : VF(VF), UF(UF), LI(LI), DT(DT), Builder(Builder), ILV(ILV), Plan(Plan),
223 TypeAnalysis(Plan->getCanonicalIV()->getScalarType(), Ctx) {}
227 return Def->getLiveInIRValue();
236 if (!VecPart->getType()->isVectorTy()) {
237 assert(
Instance.Lane.isFirstLane() &&
"cannot get lane > 0 for scalar");
252 "Trying to access a single scalar per part but has multiple scalars "
261 auto GetBroadcastInstrs = [
this, Def](
Value *V) {
262 bool SafeToHoist = Def->isDefinedOutsideVectorRegions();
270 if (LoopVectorPreHeader)
282 assert(Def->isLiveIn() &&
"expected a live-in");
285 Value *IRV = Def->getLiveInIRValue();
286 Value *
B = GetBroadcastInstrs(IRV);
291 Value *ScalarValue =
get(Def, {Part, 0});
295 set(Def, ScalarValue, Part);
306 assert((isa<VPWidenIntOrFpInductionRecipe>(Def->getDefiningRecipe()) ||
307 isa<VPScalarIVStepsRecipe>(Def->getDefiningRecipe()) ||
308 isa<VPExpandSCEVRecipe>(Def->getDefiningRecipe())) &&
309 "unexpected recipe found to be invariant");
314 auto *LastInst = cast<Instruction>(
get(Def, {Part, LastLane}));
320 isa<PHINode>(LastInst)
331 Value *VectorValue =
nullptr;
333 VectorValue = GetBroadcastInstrs(ScalarValue);
334 set(Def, VectorValue, Part);
339 set(Def, Undef, Part);
342 VectorValue =
get(Def, Part);
349 VPRegionBlock *LoopRegion = R->getParent()->getEnclosingLoopRegion();
357 if (
LVer && (isa<LoadInst>(Orig) || isa<StoreInst>(Orig)))
375 for (
Value *V : To) {
397 << DIL->getFilename() <<
" Line: " << DIL->getLine());
421 for (
VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
426 assert(PredBB &&
"Predecessor basic-block not found building successor.");
430 auto *TermBr = dyn_cast<BranchInst>(PredBBTerminator);
431 if (isa<UnreachableInst>(PredBBTerminator)) {
432 assert(PredVPSuccessors.size() == 1 &&
433 "Predecessor ending w/o branch must have single successor.");
434 DebugLoc DL = PredBBTerminator->getDebugLoc();
438 }
else if (TermBr && !TermBr->isConditional()) {
439 TermBr->setSuccessor(0, NewBB);
443 unsigned idx = PredVPSuccessors.front() ==
this ? 0 : 1;
444 assert(!TermBr->getSuccessor(idx) &&
445 "Trying to reset an existing successor block.");
446 TermBr->setSuccessor(idx, NewBB);
459 auto *R = dyn_cast<VPRegionBlock>(BB);
460 return R && !R->isReplicator();
464 if (getPlan()->getVectorLoopRegion()->getSingleSuccessor() ==
this) {
471 VPBlockBase *PredVPB = getSingleHierarchicalPredecessor();
474 "predecessor must have the current block as only successor");
478 cast<BranchInst>(ExitingBB->
getTerminator())->setSuccessor(0, NewBB);
479 }
else if (PrevVPBB &&
480 !((SingleHPred = getSingleHierarchicalPredecessor()) &&
483 (SingleHPred->
getParent() == getEnclosingLoopRegion() &&
484 !IsLoopRegion(SingleHPred))) &&
485 !(Replica && getPredecessors().empty())) {
495 NewBB = createEmptyBasicBlock(State->
CFG);
509 <<
" in BB:" << NewBB->
getName() <<
'\n');
522 for (
auto *Def : R.definedValues())
523 Def->replaceAllUsesWith(NewValue);
525 for (
unsigned I = 0,
E = R.getNumOperands();
I !=
E;
I++)
526 R.setOperand(
I, NewValue);
531 assert((SplitAt == end() || SplitAt->getParent() ==
this) &&
532 "can only split at a position in the same block");
557 if (
P &&
P->isReplicator()) {
559 assert(!cast<VPRegionBlock>(
P)->isReplicator() &&
560 "unexpected nested replicate regions");
569 "block with multiple successors doesn't have a recipe as terminator");
582 "conditional branch recipe");
589 "block with 0 or 1 successors terminated by conditional branch recipe");
609#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
611 if (getSuccessors().empty()) {
612 O << Indent <<
"No successors\n";
614 O << Indent <<
"Successor(s): ";
616 for (
auto *Succ : getSuccessors())
617 O << LS << Succ->getName();
624 O << Indent <<
getName() <<
":\n";
626 auto RecipeIndent = Indent +
" ";
632 printSuccessors(O, Indent);
652 Old2NewVPBlocks[BB] = NewBB;
659 NewRPOT(Old2NewVPBlocks[Entry]);
660 for (
const auto &[OldBB, NewBB] :
zip(RPOT, NewRPOT)) {
661 for (
const auto &[OldPred, NewPred] :
662 zip(OldBB->getPredecessors(), NewBB->getPredecessors()))
663 assert(NewPred == Old2NewVPBlocks[OldPred] &&
"Different predecessors");
665 for (
const auto &[OldSucc, NewSucc] :
666 zip(OldBB->successors(), NewBB->successors()))
667 assert(NewSucc == Old2NewVPBlocks[OldSucc] &&
"Different successors");
671 return std::make_pair(Old2NewVPBlocks[Entry],
672 Old2NewVPBlocks[*
reverse(RPOT).begin()]);
676 const auto &[NewEntry, NewExiting] =
cloneSESE(getEntry());
680 Block->setParent(NewRegion);
688 Block->dropAllReferences(NewValue);
695 if (!isReplicator()) {
712 Block->execute(State);
719 assert(!State->
Instance &&
"Replicating a Region with non-null instance.");
724 for (
unsigned Part = 0,
UF = State->
UF; Part <
UF; ++Part) {
733 Block->execute(State);
742#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
745 O << Indent << (isReplicator() ?
"<xVFxUF> " :
"<x1> ") <<
getName() <<
": {";
746 auto NewIndent = Indent +
" ";
751 O << Indent <<
"}\n";
753 printSuccessors(O, Indent);
758 for (
auto &KV : LiveOuts)
765 Block->dropAllReferences(&DummyValue);
769 Preheader->dropAllReferences(&DummyValue);
772 for (
VPValue *VPV : VPLiveInsToFree)
774 if (BackedgeTakenCount)
775 delete BackedgeTakenCount;
781 auto Plan = std::make_unique<VPlan>(Preheader, VecPreheader);
793 Value *CanonicalIVStartValue,
796 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
799 ConstantInt::get(TripCountV->
getType(), 1),
800 "trip.count.minus.1");
801 BackedgeTakenCount->setUnderlyingValue(TCMO);
804 VectorTripCount.setUnderlyingValue(VectorTripCountV);
808 VFxUF.setUnderlyingValue(
814 if (CanonicalIVStartValue) {
815 VPValue *VPV = getVPValueOrAddLiveIn(CanonicalIVStartValue);
816 auto *
IV = getCanonicalIV();
819 return isa<VPScalarIVStepsRecipe>(U) ||
820 isa<VPScalarCastRecipe>(U) ||
821 isa<VPDerivedIVRecipe>(U) ||
822 cast<VPInstruction>(U)->getOpcode() ==
825 "the canonical IV should only be used by its increment or "
826 "ScalarIVSteps when resetting the start value");
827 IV->setOperand(0, VPV);
843 Block->execute(State);
850 VPBasicBlock *Header = getVectorLoopRegion()->getEntryBasicBlock();
853 if (isa<VPWidenPHIRecipe>(&R))
856 if (isa<VPWidenPointerInductionRecipe>(&R) ||
857 isa<VPWidenIntOrFpInductionRecipe>(&R)) {
859 if (isa<VPWidenIntOrFpInductionRecipe>(&R)) {
860 Phi = cast<PHINode>(State->
get(R.getVPSingleValue(), 0));
862 auto *WidenPhi = cast<VPWidenPointerInductionRecipe>(&R);
865 if (WidenPhi->onlyScalarsGenerated(State->
VF.
isScalable()))
868 auto *
GEP = cast<GetElementPtrInst>(State->
get(WidenPhi, 0));
869 Phi = cast<PHINode>(
GEP->getPointerOperand());
872 Phi->setIncomingBlock(1, VectorLatchBB);
876 Instruction *Inc = cast<Instruction>(Phi->getIncomingValue(1));
881 auto *PhiR = cast<VPHeaderPHIRecipe>(&R);
886 bool SinglePartNeeded = isa<VPCanonicalIVPHIRecipe>(PhiR) ||
887 isa<VPFirstOrderRecurrencePHIRecipe>(PhiR) ||
888 (isa<VPReductionPHIRecipe>(PhiR) &&
889 cast<VPReductionPHIRecipe>(PhiR)->isOrdered());
890 bool NeedsScalar = isa<VPCanonicalIVPHIRecipe>(PhiR) ||
891 (isa<VPReductionPHIRecipe>(PhiR) &&
892 cast<VPReductionPHIRecipe>(PhiR)->isInLoop());
893 unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->
UF;
895 for (
unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
896 Value *Phi = State->
get(PhiR, Part, NeedsScalar);
898 State->
get(PhiR->getBackedgeValue(),
899 SinglePartNeeded ? State->
UF - 1 : Part, NeedsScalar);
900 cast<PHINode>(Phi)->addIncoming(Val, VectorLatchBB);
908 updateDominatorTree(State->
DT, VectorHeaderBB, VectorLatchBB,
913#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
917 if (VFxUF.getNumUsers() > 0) {
923 if (VectorTripCount.getNumUsers() > 0) {
926 O <<
" = vector-trip-count";
929 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
931 BackedgeTakenCount->printAsOperand(O,
SlotTracker);
932 O <<
" = backedge-taken count";
936 if (TripCount->isLiveIn())
939 O <<
" = original trip-count";
947 O <<
"VPlan '" <<
getName() <<
"' {";
951 if (!getPreheader()->empty()) {
961 if (!LiveOuts.empty())
963 for (
const auto &KV : LiveOuts) {
973 RSO <<
Name <<
" for ";
975 RSO <<
"VF={" << VFs[0];
984 RSO <<
"UF={" << UFs[0];
1004 assert(LiveOuts.count(PN) == 0 &&
"an exit value for PN already exists");
1005 LiveOuts.insert({PN,
new VPLiveOut(PN, V)});
1015 for (
auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
1018 assert(Succs.size() <= 2 &&
1019 "Basic block in vector loop has more than 2 successors.");
1020 PostDomSucc = Succs[0];
1021 if (Succs.size() == 1) {
1023 "PostDom successor has more than one predecessor.");
1029 PostDomSucc = Succs[1];
1030 InterimSucc = Succs[0];
1033 "One successor of a basic block does not lead to the other.");
1035 "Interim successor has more than one predecessor.");
1037 "PostDom successor has more than two predecessors.");
1054 NewDeepRPOT(NewEntry);
1057 for (
const auto &[OldBB, NewBB] :
1058 zip(VPBlockUtils::blocksOnly<VPBasicBlock>(OldDeepRPOT),
1059 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT))) {
1060 assert(OldBB->getRecipeList().size() == NewBB->getRecipeList().
size() &&
1061 "blocks must have the same number of recipes");
1062 for (
const auto &[OldR, NewR] :
zip(*OldBB, *NewBB)) {
1063 assert(OldR.getNumOperands() == NewR.getNumOperands() &&
1064 "recipes must have the same number of operands");
1065 assert(OldR.getNumDefinedValues() == NewR.getNumDefinedValues() &&
1066 "recipes must define the same number of operands");
1067 for (
const auto &[OldV, NewV] :
1068 zip(OldR.definedValues(), NewR.definedValues()))
1069 Old2NewVPValues[OldV] = NewV;
1075 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT)) {
1077 for (
unsigned I = 0,
E = NewR.getNumOperands();
I !=
E; ++
I) {
1079 NewR.setOperand(
I, NewOp);
1087 const auto &[NewEntry, __] =
cloneSESE(Entry);
1090 auto *NewPlan =
new VPlan(NewPreheader, cast<VPBasicBlock>(NewEntry));
1092 for (
VPValue *OldLiveIn : VPLiveInsToFree) {
1093 Old2NewVPValues[OldLiveIn] =
1094 NewPlan->getVPValueOrAddLiveIn(OldLiveIn->getLiveInIRValue());
1096 Old2NewVPValues[&VectorTripCount] = &NewPlan->VectorTripCount;
1097 Old2NewVPValues[&VFxUF] = &NewPlan->VFxUF;
1098 if (BackedgeTakenCount) {
1099 NewPlan->BackedgeTakenCount =
new VPValue();
1100 Old2NewVPValues[BackedgeTakenCount] = NewPlan->BackedgeTakenCount;
1102 assert(TripCount &&
"trip count must be set");
1103 if (TripCount->isLiveIn())
1104 Old2NewVPValues[TripCount] =
1105 NewPlan->getVPValueOrAddLiveIn(TripCount->getLiveInIRValue());
1113 for (
const auto &[
_, LO] : LiveOuts)
1114 NewPlan->addLiveOut(LO->getPhi(), Old2NewVPValues[LO->getOperand(0)]);
1120 NewPlan->Name =
Name;
1122 "TripCount must have been added to Old2NewVPValues");
1123 NewPlan->TripCount = Old2NewVPValues[TripCount];
1127#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1130 return (isa<VPRegionBlock>(
Block) ?
"cluster_N" :
"N") +
1135 const std::string &
Name =
Block->getName();
1144 OS <<
"digraph VPlan {\n";
1145 OS <<
"graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
1156 for (
auto Line : Lines)
1161 OS <<
"node [shape=rect, fontname=Courier, fontsize=30]\n";
1162 OS <<
"edge [fontname=Courier, fontsize=30]\n";
1163 OS <<
"compound=true\n";
1183 bool Hidden,
const Twine &Label) {
1188 OS << Indent << getUID(
Tail) <<
" -> " << getUID(Head);
1189 OS <<
" [ label=\"" << Label <<
'\"';
1191 OS <<
" ltail=" << getUID(
From);
1193 OS <<
" lhead=" << getUID(To);
1195 OS <<
"; splines=none";
1200 auto &Successors =
Block->getSuccessors();
1201 if (Successors.size() == 1)
1202 drawEdge(
Block, Successors.front(),
false,
"");
1203 else if (Successors.size() == 2) {
1204 drawEdge(
Block, Successors.front(),
false,
"T");
1205 drawEdge(
Block, Successors.back(),
false,
"F");
1207 unsigned SuccessorNumber = 0;
1234 EmitLine(Line,
" +\n");
1235 EmitLine(
Lines.back(),
"\n");
1238 OS << Indent <<
"]\n";
1244 OS << Indent <<
"subgraph " << getUID(
Region) <<
" {\n";
1246 OS << Indent <<
"fontname=Courier\n"
1247 << Indent <<
"label=\""
1255 OS << Indent <<
"}\n";
1260 if (
auto *Inst = dyn_cast<Instruction>(V)) {
1261 if (!Inst->getType()->isVoidTy()) {
1262 Inst->printAsOperand(O,
false);
1265 O << Inst->getOpcodeName() <<
" ";
1266 unsigned E = Inst->getNumOperands();
1268 Inst->getOperand(0)->printAsOperand(O,
false);
1269 for (
unsigned I = 1;
I <
E; ++
I)
1270 Inst->getOperand(
I)->printAsOperand(O <<
", ",
false);
1273 V->printAsOperand(O,
false);
1281 replaceUsesWithIf(New, [](
VPUser &,
unsigned) {
return true; });
1293 for (
unsigned J = 0; J < getNumUsers();) {
1295 bool RemovedUser =
false;
1311#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1313 if (
const Value *UV = getUnderlyingValue()) {
1315 UV->printAsOperand(
OS,
false);
1320 unsigned Slot = Tracker.
getSlot(
this);
1321 if (Slot ==
unsigned(-1))
1324 OS <<
"vp<%" << Tracker.
getSlot(
this) <<
">";
1340 visitBlock(
Base, Old2New, IAI);
1344void VPInterleavedAccessInfo::visitBlock(
VPBlockBase *
Block, Old2NewTy &Old2New,
1348 if (isa<VPWidenPHIRecipe>(&VPI))
1350 assert(isa<VPInstruction>(&VPI) &&
"Can only handle VPInstructions");
1351 auto *VPInst = cast<VPInstruction>(&VPI);
1353 auto *Inst = dyn_cast_or_null<Instruction>(VPInst->getUnderlyingValue());
1360 auto NewIGIter = Old2New.find(IG);
1361 if (NewIGIter == Old2New.end())
1363 IG->getFactor(), IG->isReverse(), IG->getAlign());
1365 if (Inst == IG->getInsertPos())
1366 Old2New[IG]->setInsertPos(VPInst);
1368 InterleaveGroupMap[VPInst] = Old2New[IG];
1369 InterleaveGroupMap[VPInst]->insertMember(
1370 VPInst, IG->getIndex(Inst),
1371 Align(IG->isReverse() ? (-1) *
int(IG->getFactor())
1372 : IG->getFactor()));
1375 visitRegion(
Region, Old2New, IAI);
1386void VPSlotTracker::assignSlot(
const VPValue *V) {
1387 assert(!Slots.contains(V) &&
"VPValue already has a slot!");
1388 Slots[V] = NextSlot++;
1391void VPSlotTracker::assignSlots(
const VPlan &
Plan) {
1393 assignSlot(&
Plan.VFxUF);
1394 assignSlot(&
Plan.VectorTripCount);
1395 if (
Plan.BackedgeTakenCount)
1396 assignSlot(
Plan.BackedgeTakenCount);
1402 VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
1406void VPSlotTracker::assignSlots(
const VPBasicBlock *VPBB) {
1408 for (
VPValue *Def : Recipe.definedValues())
1413 return all_of(Def->users(),
1414 [Def](
const VPUser *U) { return U->onlyFirstLaneUsed(Def); });
1418 return all_of(Def->users(),
1419 [Def](
const VPUser *U) { return U->onlyFirstPartUsed(Def); });
1427 if (
auto *
E = dyn_cast<SCEVConstant>(Expr))
1429 else if (
auto *
E = dyn_cast<SCEVUnknown>(Expr))
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< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#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 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 std::pair< VPBlockBase *, VPBlockBase * > cloneSESE(VPBlockBase *Entry)
static bool hasConditionalTerminator(const VPBasicBlock *VPBB)
static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry, DenseMap< VPValue *, VPValue * > &Old2NewVPValues)
This file contains the declarations of the Vectorization Plan base classes:
static bool IsCondBranch(unsigned BrOpc)
static const uint32_t IV[8]
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
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.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
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, BasicBlock::iterator InsertBefore)
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.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
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.
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)
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 ...
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.
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.
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.
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.
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.
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...
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.
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 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.
VPRegionBlock * getParent()
const VPBasicBlock * getExitingBasicBlock() const
size_t getNumSuccessors() const
void printSuccessors(raw_ostream &O, const Twine &Indent) const
Print the successors of this block to O, prefixing all lines with Indent.
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
VPBlockBase * getSingleSuccessor() 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.
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.
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.
@ 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.
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...
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 consecutive numbers to all VPValues in a VPlan and allows querying t...
unsigned getSlot(const VPValue *V) const
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()
void addLiveOut(PHINode *PN, VPValue *V)
VPBasicBlock * getPreheader()
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.
static VPlanPtr createInitialVPlan(const SCEV *TripCount, ScalarEvolution &PSE)
Create initial VPlan skeleton, having an "entry" VPBasicBlock (wrapping original scalar pre-header) w...
void addSCEVExpansion(const SCEV *S, VPValue *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.
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...
std::string EscapeString(const std::string &Label)
bool match(Val *V, const Pattern &P)
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.
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)
Get or create a VPValue that corresponds to the expansion of Expr.
bool isUniformAfterVectorization(VPValue *VPV)
Returns true if VPV is uniform after vectorization.
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.
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.
Interval::succ_iterator succ_end(Interval *I)
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 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.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
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
auto reverse(ContainerTy &&C)
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)
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.
This struct is a compact representation of a valid (non-zero power of two) alignment.
VPIteration represents a single point in the iteration space of the output (vectorized and/or unrolle...
void print(raw_ostream &O) const