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)))
366 if (
Instruction *ToI = dyn_cast<Instruction>(To)) {
388 << DIL->getFilename() <<
" Line: " << DIL->getLine());
412 for (
VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
417 assert(PredBB &&
"Predecessor basic-block not found building successor.");
421 auto *TermBr = dyn_cast<BranchInst>(PredBBTerminator);
422 if (isa<UnreachableInst>(PredBBTerminator)) {
423 assert(PredVPSuccessors.size() == 1 &&
424 "Predecessor ending w/o branch must have single successor.");
425 DebugLoc DL = PredBBTerminator->getDebugLoc();
429 }
else if (TermBr && !TermBr->isConditional()) {
430 TermBr->setSuccessor(0, NewBB);
434 unsigned idx = PredVPSuccessors.front() ==
this ? 0 : 1;
435 assert(!TermBr->getSuccessor(idx) &&
436 "Trying to reset an existing successor block.");
437 TermBr->setSuccessor(idx, NewBB);
450 auto *R = dyn_cast<VPRegionBlock>(BB);
451 return R && !R->isReplicator();
455 if (getPlan()->getVectorLoopRegion()->getSingleSuccessor() ==
this) {
462 VPBlockBase *PredVPB = getSingleHierarchicalPredecessor();
465 "predecessor must have the current block as only successor");
469 cast<BranchInst>(ExitingBB->
getTerminator())->setSuccessor(0, NewBB);
470 }
else if (PrevVPBB &&
471 !((SingleHPred = getSingleHierarchicalPredecessor()) &&
474 (SingleHPred->
getParent() == getEnclosingLoopRegion() &&
475 !IsLoopRegion(SingleHPred))) &&
476 !(Replica && getPredecessors().empty())) {
486 NewBB = createEmptyBasicBlock(State->
CFG);
500 <<
" in BB:" << NewBB->
getName() <<
'\n');
513 for (
auto *Def : R.definedValues())
514 Def->replaceAllUsesWith(NewValue);
516 for (
unsigned I = 0, E = R.getNumOperands();
I != E;
I++)
517 R.setOperand(
I, NewValue);
522 assert((SplitAt == end() || SplitAt->getParent() ==
this) &&
523 "can only split at a position in the same block");
548 if (
P &&
P->isReplicator()) {
550 assert(!cast<VPRegionBlock>(
P)->isReplicator() &&
551 "unexpected nested replicate regions");
560 "block with multiple successors doesn't have a recipe as terminator");
573 "conditional branch recipe");
580 "block with 0 or 1 successors terminated by conditional branch recipe");
600#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
602 if (getSuccessors().empty()) {
603 O << Indent <<
"No successors\n";
605 O << Indent <<
"Successor(s): ";
607 for (
auto *Succ : getSuccessors())
608 O << LS << Succ->getName();
615 O << Indent <<
getName() <<
":\n";
617 auto RecipeIndent = Indent +
" ";
623 printSuccessors(O, Indent);
643 Old2NewVPBlocks[BB] = NewBB;
650 NewRPOT(Old2NewVPBlocks[Entry]);
651 for (
const auto &[OldBB, NewBB] :
zip(RPOT, NewRPOT)) {
652 for (
const auto &[OldPred, NewPred] :
653 zip(OldBB->getPredecessors(), NewBB->getPredecessors()))
654 assert(NewPred == Old2NewVPBlocks[OldPred] &&
"Different predecessors");
656 for (
const auto &[OldSucc, NewSucc] :
657 zip(OldBB->successors(), NewBB->successors()))
658 assert(NewSucc == Old2NewVPBlocks[OldSucc] &&
"Different successors");
662 return std::make_pair(Old2NewVPBlocks[Entry],
663 Old2NewVPBlocks[*
reverse(RPOT).begin()]);
667 const auto &[NewEntry, NewExiting] =
cloneSESE(getEntry());
671 Block->setParent(NewRegion);
679 Block->dropAllReferences(NewValue);
686 if (!isReplicator()) {
703 Block->execute(State);
710 assert(!State->
Instance &&
"Replicating a Region with non-null instance.");
715 for (
unsigned Part = 0,
UF = State->
UF; Part <
UF; ++Part) {
724 Block->execute(State);
733#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
736 O << Indent << (isReplicator() ?
"<xVFxUF> " :
"<x1> ") <<
getName() <<
": {";
737 auto NewIndent = Indent +
" ";
742 O << Indent <<
"}\n";
744 printSuccessors(O, Indent);
749 for (
auto &KV : LiveOuts)
756 Block->dropAllReferences(&DummyValue);
760 Preheader->dropAllReferences(&DummyValue);
763 for (
VPValue *VPV : VPLiveInsToFree)
765 if (BackedgeTakenCount)
766 delete BackedgeTakenCount;
772 auto Plan = std::make_unique<VPlan>(Preheader, VecPreheader);
784 Value *CanonicalIVStartValue,
787 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
790 ConstantInt::get(TripCountV->
getType(), 1),
791 "trip.count.minus.1");
792 BackedgeTakenCount->setUnderlyingValue(TCMO);
795 VectorTripCount.setUnderlyingValue(VectorTripCountV);
799 VFxUF.setUnderlyingValue(
805 if (CanonicalIVStartValue) {
806 VPValue *VPV = getOrAddLiveIn(CanonicalIVStartValue);
807 auto *
IV = getCanonicalIV();
810 return isa<VPScalarIVStepsRecipe>(U) ||
811 isa<VPScalarCastRecipe>(U) ||
812 isa<VPDerivedIVRecipe>(U) ||
813 cast<VPInstruction>(U)->getOpcode() ==
816 "the canonical IV should only be used by its increment or "
817 "ScalarIVSteps when resetting the start value");
818 IV->setOperand(0, VPV);
834 Block->execute(State);
841 VPBasicBlock *Header = getVectorLoopRegion()->getEntryBasicBlock();
844 if (isa<VPWidenPHIRecipe>(&R))
847 if (isa<VPWidenPointerInductionRecipe>(&R) ||
848 isa<VPWidenIntOrFpInductionRecipe>(&R)) {
850 if (isa<VPWidenIntOrFpInductionRecipe>(&R)) {
851 Phi = cast<PHINode>(State->
get(R.getVPSingleValue(), 0));
853 auto *WidenPhi = cast<VPWidenPointerInductionRecipe>(&R);
855 "recipe generating only scalars should have been replaced");
856 auto *
GEP = cast<GetElementPtrInst>(State->
get(WidenPhi, 0));
857 Phi = cast<PHINode>(
GEP->getPointerOperand());
860 Phi->setIncomingBlock(1, VectorLatchBB);
864 Instruction *Inc = cast<Instruction>(Phi->getIncomingValue(1));
869 auto *PhiR = cast<VPHeaderPHIRecipe>(&R);
874 bool SinglePartNeeded =
875 isa<VPCanonicalIVPHIRecipe>(PhiR) ||
876 isa<VPFirstOrderRecurrencePHIRecipe, VPEVLBasedIVPHIRecipe>(PhiR) ||
877 (isa<VPReductionPHIRecipe>(PhiR) &&
878 cast<VPReductionPHIRecipe>(PhiR)->isOrdered());
880 isa<VPCanonicalIVPHIRecipe, VPEVLBasedIVPHIRecipe>(PhiR) ||
881 (isa<VPReductionPHIRecipe>(PhiR) &&
882 cast<VPReductionPHIRecipe>(PhiR)->isInLoop());
883 unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->
UF;
885 for (
unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
886 Value *Phi = State->
get(PhiR, Part, NeedsScalar);
888 State->
get(PhiR->getBackedgeValue(),
889 SinglePartNeeded ? State->
UF - 1 : Part, NeedsScalar);
890 cast<PHINode>(Phi)->addIncoming(Val, VectorLatchBB);
898 updateDominatorTree(State->
DT, VectorHeaderBB, VectorLatchBB,
903#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
907 if (VFxUF.getNumUsers() > 0) {
913 if (VectorTripCount.getNumUsers() > 0) {
916 O <<
" = vector-trip-count";
919 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
921 BackedgeTakenCount->printAsOperand(O,
SlotTracker);
922 O <<
" = backedge-taken count";
926 if (TripCount->isLiveIn())
929 O <<
" = original trip-count";
937 O <<
"VPlan '" <<
getName() <<
"' {";
941 if (!getPreheader()->empty()) {
951 if (!LiveOuts.empty())
953 for (
const auto &KV : LiveOuts) {
963 RSO <<
Name <<
" for ";
965 RSO <<
"VF={" << VFs[0];
974 RSO <<
"UF={" << UFs[0];
994 assert(LiveOuts.count(PN) == 0 &&
"an exit value for PN already exists");
995 LiveOuts.insert({PN,
new VPLiveOut(PN, V)});
1005 for (
auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
1008 assert(Succs.size() <= 2 &&
1009 "Basic block in vector loop has more than 2 successors.");
1010 PostDomSucc = Succs[0];
1011 if (Succs.size() == 1) {
1013 "PostDom successor has more than one predecessor.");
1019 PostDomSucc = Succs[1];
1020 InterimSucc = Succs[0];
1023 "One successor of a basic block does not lead to the other.");
1025 "Interim successor has more than one predecessor.");
1027 "PostDom successor has more than two predecessors.");
1044 NewDeepRPOT(NewEntry);
1047 for (
const auto &[OldBB, NewBB] :
1048 zip(VPBlockUtils::blocksOnly<VPBasicBlock>(OldDeepRPOT),
1049 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT))) {
1050 assert(OldBB->getRecipeList().size() == NewBB->getRecipeList().
size() &&
1051 "blocks must have the same number of recipes");
1052 for (
const auto &[OldR, NewR] :
zip(*OldBB, *NewBB)) {
1053 assert(OldR.getNumOperands() == NewR.getNumOperands() &&
1054 "recipes must have the same number of operands");
1055 assert(OldR.getNumDefinedValues() == NewR.getNumDefinedValues() &&
1056 "recipes must define the same number of operands");
1057 for (
const auto &[OldV, NewV] :
1058 zip(OldR.definedValues(), NewR.definedValues()))
1059 Old2NewVPValues[OldV] = NewV;
1065 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT)) {
1067 for (
unsigned I = 0, E = NewR.getNumOperands();
I != E; ++
I) {
1069 NewR.setOperand(
I, NewOp);
1077 const auto &[NewEntry, __] =
cloneSESE(Entry);
1080 auto *NewPlan =
new VPlan(NewPreheader, cast<VPBasicBlock>(NewEntry));
1082 for (
VPValue *OldLiveIn : VPLiveInsToFree) {
1083 Old2NewVPValues[OldLiveIn] =
1084 NewPlan->getOrAddLiveIn(OldLiveIn->getLiveInIRValue());
1086 Old2NewVPValues[&VectorTripCount] = &NewPlan->VectorTripCount;
1087 Old2NewVPValues[&VFxUF] = &NewPlan->VFxUF;
1088 if (BackedgeTakenCount) {
1089 NewPlan->BackedgeTakenCount =
new VPValue();
1090 Old2NewVPValues[BackedgeTakenCount] = NewPlan->BackedgeTakenCount;
1092 assert(TripCount &&
"trip count must be set");
1093 if (TripCount->isLiveIn())
1094 Old2NewVPValues[TripCount] =
1095 NewPlan->getOrAddLiveIn(TripCount->getLiveInIRValue());
1103 for (
const auto &[
_, LO] : LiveOuts)
1104 NewPlan->addLiveOut(LO->getPhi(), Old2NewVPValues[LO->getOperand(0)]);
1110 NewPlan->Name =
Name;
1112 "TripCount must have been added to Old2NewVPValues");
1113 NewPlan->TripCount = Old2NewVPValues[TripCount];
1117#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1120 return (isa<VPRegionBlock>(
Block) ?
"cluster_N" :
"N") +
1125 const std::string &
Name =
Block->getName();
1134 OS <<
"digraph VPlan {\n";
1135 OS <<
"graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
1146 for (
auto Line : Lines)
1151 OS <<
"node [shape=rect, fontname=Courier, fontsize=30]\n";
1152 OS <<
"edge [fontname=Courier, fontsize=30]\n";
1153 OS <<
"compound=true\n";
1173 bool Hidden,
const Twine &Label) {
1178 OS << Indent << getUID(
Tail) <<
" -> " << getUID(Head);
1179 OS <<
" [ label=\"" << Label <<
'\"';
1181 OS <<
" ltail=" << getUID(
From);
1183 OS <<
" lhead=" << getUID(To);
1185 OS <<
"; splines=none";
1190 auto &Successors =
Block->getSuccessors();
1191 if (Successors.size() == 1)
1192 drawEdge(
Block, Successors.front(),
false,
"");
1193 else if (Successors.size() == 2) {
1194 drawEdge(
Block, Successors.front(),
false,
"T");
1195 drawEdge(
Block, Successors.back(),
false,
"F");
1197 unsigned SuccessorNumber = 0;
1224 EmitLine(Line,
" +\n");
1225 EmitLine(
Lines.back(),
"\n");
1228 OS << Indent <<
"]\n";
1234 OS << Indent <<
"subgraph " << getUID(
Region) <<
" {\n";
1236 OS << Indent <<
"fontname=Courier\n"
1237 << Indent <<
"label=\""
1245 OS << Indent <<
"}\n";
1250 if (
auto *Inst = dyn_cast<Instruction>(V)) {
1251 if (!Inst->getType()->isVoidTy()) {
1252 Inst->printAsOperand(O,
false);
1255 O << Inst->getOpcodeName() <<
" ";
1256 unsigned E = Inst->getNumOperands();
1258 Inst->getOperand(0)->printAsOperand(O,
false);
1259 for (
unsigned I = 1;
I < E; ++
I)
1260 Inst->getOperand(
I)->printAsOperand(O <<
", ",
false);
1263 V->printAsOperand(O,
false);
1271 replaceUsesWithIf(New, [](
VPUser &,
unsigned) {
return true; });
1283 for (
unsigned J = 0; J < getNumUsers();) {
1285 bool RemovedUser =
false;
1301#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1319 visitBlock(
Base, Old2New, IAI);
1323void VPInterleavedAccessInfo::visitBlock(
VPBlockBase *
Block, Old2NewTy &Old2New,
1327 if (isa<VPWidenPHIRecipe>(&VPI))
1329 assert(isa<VPInstruction>(&VPI) &&
"Can only handle VPInstructions");
1330 auto *VPInst = cast<VPInstruction>(&VPI);
1332 auto *Inst = dyn_cast_or_null<Instruction>(VPInst->getUnderlyingValue());
1339 auto NewIGIter = Old2New.find(IG);
1340 if (NewIGIter == Old2New.end())
1342 IG->getFactor(), IG->isReverse(), IG->getAlign());
1344 if (Inst == IG->getInsertPos())
1345 Old2New[IG]->setInsertPos(VPInst);
1347 InterleaveGroupMap[VPInst] = Old2New[IG];
1348 InterleaveGroupMap[VPInst]->insertMember(
1349 VPInst, IG->getIndex(Inst),
1350 Align(IG->isReverse() ? (-1) *
int(IG->getFactor())
1351 : IG->getFactor()));
1354 visitRegion(
Region, Old2New, IAI);
1365void VPSlotTracker::assignName(
const VPValue *V) {
1366 assert(!VPValue2Name.contains(V) &&
"VPValue already has a name!");
1367 auto *UV = V->getUnderlyingValue();
1369 VPValue2Name[V] = (
Twine(
"vp<%") +
Twine(NextSlot) +
">").str();
1378 UV->printAsOperand(S,
false);
1379 assert(!
Name.empty() &&
"Name cannot be empty.");
1383 const auto &[
A,
_] = VPValue2Name.insert({V, BaseName});
1386 if (
V->isLiveIn() && isa<ConstantInt, ConstantFP>(UV))
1391 const auto &[
C, UseInserted] = BaseName2Version.insert({BaseName, 0});
1394 A->second = (BaseName +
Twine(
".") +
Twine(
C->second)).str();
1398void VPSlotTracker::assignNames(
const VPlan &
Plan) {
1400 assignName(&
Plan.VFxUF);
1401 assignName(&
Plan.VectorTripCount);
1402 if (
Plan.BackedgeTakenCount)
1403 assignName(
Plan.BackedgeTakenCount);
1411 VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
1415void VPSlotTracker::assignNames(
const VPBasicBlock *VPBB) {
1417 for (
VPValue *Def : Recipe.definedValues())
1422 std::string
Name = VPValue2Name.lookup(V);
1436 "VPValue defined by a recipe in a VPlan?");
1439 if (
auto *UV = V->getUnderlyingValue()) {
1442 UV->printAsOperand(S,
false);
1443 return (
Twine(
"ir<") +
Name +
">").str();
1450 return all_of(Def->users(),
1451 [Def](
const VPUser *U) { return U->onlyFirstLaneUsed(Def); });
1455 return all_of(Def->users(),
1456 [Def](
const VPUser *U) { return U->onlyFirstPartUsed(Def); });
1464 if (
auto *E = dyn_cast<SCEVConstant>(Expr))
1466 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< 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 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]
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.
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...
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()
void addLiveOut(PHINode *PN, VPValue *V)
VPBasicBlock * getPreheader()
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)
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.
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)
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.
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.
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...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
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