LLVM 19.0.0git
VPlan.cpp
Go to the documentation of this file.
1//===- VPlan.cpp - Vectorizer Plan ----------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This is the LLVM vectorization plan. It represents a candidate for
11/// vectorization, allowing to plan and optimize how to vectorize a given loop
12/// before generating LLVM-IR.
13/// The vectorizer uses vectorization plans to estimate the costs of potential
14/// candidates and if profitable to execute the desired plan, generating vector
15/// LLVM-IR code.
16///
17//===----------------------------------------------------------------------===//
18
19#include "VPlan.h"
20#include "VPlanCFG.h"
21#include "VPlanDominatorTree.h"
22#include "VPlanPatternMatch.h"
24#include "llvm/ADT/STLExtras.h"
27#include "llvm/ADT/Twine.h"
29#include "llvm/IR/BasicBlock.h"
30#include "llvm/IR/CFG.h"
31#include "llvm/IR/IRBuilder.h"
32#include "llvm/IR/Instruction.h"
34#include "llvm/IR/Type.h"
35#include "llvm/IR/Value.h"
38#include "llvm/Support/Debug.h"
45#include <cassert>
46#include <string>
47#include <vector>
48
49using namespace llvm;
50using namespace llvm::VPlanPatternMatch;
51
52namespace llvm {
54}
55
56#define DEBUG_TYPE "vplan"
57
58#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
60 const VPInstruction *Instr = dyn_cast<VPInstruction>(&V);
62 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
63 V.print(OS, SlotTracker);
64 return OS;
65}
66#endif
67
69 const ElementCount &VF) const {
70 switch (LaneKind) {
72 // Lane = RuntimeVF - VF.getKnownMinValue() + Lane
73 return Builder.CreateSub(getRuntimeVF(Builder, Builder.getInt32Ty(), VF),
74 Builder.getInt32(VF.getKnownMinValue() - Lane));
76 return Builder.getInt32(Lane);
77 }
78 llvm_unreachable("Unknown lane kind");
79}
80
81VPValue::VPValue(const unsigned char SC, Value *UV, VPDef *Def)
82 : SubclassID(SC), UnderlyingVal(UV), Def(Def) {
83 if (Def)
84 Def->addDefinedValue(this);
85}
86
88 assert(Users.empty() && "trying to delete a VPValue with remaining users");
89 if (Def)
90 Def->removeDefinedValue(this);
91}
92
93#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
95 if (const VPRecipeBase *R = dyn_cast_or_null<VPRecipeBase>(Def))
96 R->print(OS, "", SlotTracker);
97 else
99}
100
101void VPValue::dump() const {
102 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this->Def);
104 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
106 dbgs() << "\n";
107}
108
109void VPDef::dump() const {
110 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this);
112 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
113 print(dbgs(), "", SlotTracker);
114 dbgs() << "\n";
115}
116#endif
117
119 return cast_or_null<VPRecipeBase>(Def);
120}
121
123 return cast_or_null<VPRecipeBase>(Def);
124}
125
126// Get the top-most entry block of \p Start. This is the entry block of the
127// containing VPlan. This function is templated to support both const and non-const blocks
128template <typename T> static T *getPlanEntry(T *Start) {
129 T *Next = Start;
130 T *Current = Start;
131 while ((Next = Next->getParent()))
132 Current = Next;
133
134 SmallSetVector<T *, 8> WorkList;
135 WorkList.insert(Current);
136
137 for (unsigned i = 0; i < WorkList.size(); i++) {
138 T *Current = WorkList[i];
139 if (Current->getNumPredecessors() == 0)
140 return Current;
141 auto &Predecessors = Current->getPredecessors();
142 WorkList.insert(Predecessors.begin(), Predecessors.end());
143 }
144
145 llvm_unreachable("VPlan without any entry node without predecessors");
146}
147
148VPlan *VPBlockBase::getPlan() { return getPlanEntry(this)->Plan; }
149
150const VPlan *VPBlockBase::getPlan() const { return getPlanEntry(this)->Plan; }
151
152/// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
154 const VPBlockBase *Block = this;
155 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
156 Block = Region->getEntry();
157 return cast<VPBasicBlock>(Block);
158}
159
161 VPBlockBase *Block = this;
162 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
163 Block = Region->getEntry();
164 return cast<VPBasicBlock>(Block);
165}
166
167void VPBlockBase::setPlan(VPlan *ParentPlan) {
168 assert(
169 (ParentPlan->getEntry() == this || ParentPlan->getPreheader() == this) &&
170 "Can only set plan on its entry or preheader block.");
171 Plan = ParentPlan;
172}
173
174/// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
176 const VPBlockBase *Block = this;
177 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
178 Block = Region->getExiting();
179 return cast<VPBasicBlock>(Block);
180}
181
183 VPBlockBase *Block = this;
184 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
185 Block = Region->getExiting();
186 return cast<VPBasicBlock>(Block);
187}
188
190 if (!Successors.empty() || !Parent)
191 return this;
192 assert(Parent->getExiting() == this &&
193 "Block w/o successors not the exiting block of its parent.");
194 return Parent->getEnclosingBlockWithSuccessors();
195}
196
198 if (!Predecessors.empty() || !Parent)
199 return this;
200 assert(Parent->getEntry() == this &&
201 "Block w/o predecessors not the entry of its parent.");
202 return Parent->getEnclosingBlockWithPredecessors();
203}
204
207 delete Block;
208}
209
211 iterator It = begin();
212 while (It != end() && It->isPhi())
213 It++;
214 return It;
215}
216
218 DominatorTree *DT, IRBuilderBase &Builder,
219 InnerLoopVectorizer *ILV, VPlan *Plan,
220 LLVMContext &Ctx)
221 : VF(VF), UF(UF), LI(LI), DT(DT), Builder(Builder), ILV(ILV), Plan(Plan),
222 LVer(nullptr),
223 TypeAnalysis(Plan->getCanonicalIV()->getScalarType(), Ctx) {}
224
226 if (Def->isLiveIn())
227 return Def->getLiveInIRValue();
228
229 if (hasScalarValue(Def, Instance)) {
230 return Data
231 .PerPartScalars[Def][Instance.Part][Instance.Lane.mapToCacheIndex(VF)];
232 }
233
234 assert(hasVectorValue(Def, Instance.Part));
235 auto *VecPart = Data.PerPartOutput[Def][Instance.Part];
236 if (!VecPart->getType()->isVectorTy()) {
237 assert(Instance.Lane.isFirstLane() && "cannot get lane > 0 for scalar");
238 return VecPart;
239 }
240 // TODO: Cache created scalar values.
241 Value *Lane = Instance.Lane.getAsRuntimeExpr(Builder, VF);
242 auto *Extract = Builder.CreateExtractElement(VecPart, Lane);
243 // set(Def, Extract, Instance);
244 return Extract;
245}
246
247Value *VPTransformState::get(VPValue *Def, unsigned Part, bool NeedsScalar) {
248 if (NeedsScalar) {
249 assert((VF.isScalar() || Def->isLiveIn() || hasVectorValue(Def, Part) ||
250 (hasScalarValue(Def, VPIteration(Part, 0)) &&
251 Data.PerPartScalars[Def][Part].size() == 1)) &&
252 "Trying to access a single scalar per part but has multiple scalars "
253 "per part.");
254 return get(Def, VPIteration(Part, 0));
255 }
256
257 // If Values have been set for this Def return the one relevant for \p Part.
258 if (hasVectorValue(Def, Part))
259 return Data.PerPartOutput[Def][Part];
260
261 auto GetBroadcastInstrs = [this, Def](Value *V) {
262 bool SafeToHoist = Def->isDefinedOutsideVectorRegions();
263 if (VF.isScalar())
264 return V;
265 // Place the code for broadcasting invariant variables in the new preheader.
267 if (SafeToHoist) {
268 BasicBlock *LoopVectorPreHeader = CFG.VPBB2IRBB[cast<VPBasicBlock>(
270 if (LoopVectorPreHeader)
271 Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
272 }
273
274 // Place the code for broadcasting invariant variables in the new preheader.
275 // Broadcast the scalar into all locations in the vector.
276 Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast");
277
278 return Shuf;
279 };
280
281 if (!hasScalarValue(Def, {Part, 0})) {
282 assert(Def->isLiveIn() && "expected a live-in");
283 if (Part != 0)
284 return get(Def, 0);
285 Value *IRV = Def->getLiveInIRValue();
286 Value *B = GetBroadcastInstrs(IRV);
287 set(Def, B, Part);
288 return B;
289 }
290
291 Value *ScalarValue = get(Def, {Part, 0});
292 // If we aren't vectorizing, we can just copy the scalar map values over
293 // to the vector map.
294 if (VF.isScalar()) {
295 set(Def, ScalarValue, Part);
296 return ScalarValue;
297 }
298
299 bool IsUniform = vputils::isUniformAfterVectorization(Def);
300
301 unsigned LastLane = IsUniform ? 0 : VF.getKnownMinValue() - 1;
302 // Check if there is a scalar value for the selected lane.
303 if (!hasScalarValue(Def, {Part, LastLane})) {
304 // At the moment, VPWidenIntOrFpInductionRecipes, VPScalarIVStepsRecipes and
305 // VPExpandSCEVRecipes can also be uniform.
306 assert((isa<VPWidenIntOrFpInductionRecipe>(Def->getDefiningRecipe()) ||
307 isa<VPScalarIVStepsRecipe>(Def->getDefiningRecipe()) ||
308 isa<VPExpandSCEVRecipe>(Def->getDefiningRecipe())) &&
309 "unexpected recipe found to be invariant");
310 IsUniform = true;
311 LastLane = 0;
312 }
313
314 auto *LastInst = cast<Instruction>(get(Def, {Part, LastLane}));
315 // Set the insert point after the last scalarized instruction or after the
316 // last PHI, if LastInst is a PHI. This ensures the insertelement sequence
317 // will directly follow the scalar definitions.
318 auto OldIP = Builder.saveIP();
319 auto NewIP =
320 isa<PHINode>(LastInst)
321 ? BasicBlock::iterator(LastInst->getParent()->getFirstNonPHI())
322 : std::next(BasicBlock::iterator(LastInst));
323 Builder.SetInsertPoint(&*NewIP);
324
325 // However, if we are vectorizing, we need to construct the vector values.
326 // If the value is known to be uniform after vectorization, we can just
327 // broadcast the scalar value corresponding to lane zero for each unroll
328 // iteration. Otherwise, we construct the vector values using
329 // insertelement instructions. Since the resulting vectors are stored in
330 // State, we will only generate the insertelements once.
331 Value *VectorValue = nullptr;
332 if (IsUniform) {
333 VectorValue = GetBroadcastInstrs(ScalarValue);
334 set(Def, VectorValue, Part);
335 } else {
336 // Initialize packing with insertelements to start from undef.
337 assert(!VF.isScalable() && "VF is assumed to be non scalable.");
338 Value *Undef = PoisonValue::get(VectorType::get(LastInst->getType(), VF));
339 set(Def, Undef, Part);
340 for (unsigned Lane = 0; Lane < VF.getKnownMinValue(); ++Lane)
341 packScalarIntoVectorValue(Def, {Part, Lane});
342 VectorValue = get(Def, Part);
343 }
344 Builder.restoreIP(OldIP);
345 return VectorValue;
346}
347
349 VPRegionBlock *LoopRegion = R->getParent()->getEnclosingLoopRegion();
350 return VPBB2IRBB[LoopRegion->getPreheaderVPBB()];
351}
352
354 const Instruction *Orig) {
355 // If the loop was versioned with memchecks, add the corresponding no-alias
356 // metadata.
357 if (LVer && (isa<LoadInst>(Orig) || isa<StoreInst>(Orig)))
358 LVer->annotateInstWithNoAlias(To, Orig);
359}
360
362 // No source instruction to transfer metadata from?
363 if (!From)
364 return;
365
366 if (Instruction *ToI = dyn_cast<Instruction>(To)) {
368 addNewMetadata(ToI, From);
369 }
370}
371
373 const DILocation *DIL = DL;
374 // When a FSDiscriminator is enabled, we don't need to add the multiply
375 // factors to the discriminators.
376 if (DIL &&
378 ->getParent()
381 // FIXME: For scalable vectors, assume vscale=1.
382 auto NewDIL =
384 if (NewDIL)
386 else
387 LLVM_DEBUG(dbgs() << "Failed to create new discriminator: "
388 << DIL->getFilename() << " Line: " << DIL->getLine());
389 } else
391}
392
394 const VPIteration &Instance) {
395 Value *ScalarInst = get(Def, Instance);
396 Value *VectorValue = get(Def, Instance.Part);
397 VectorValue = Builder.CreateInsertElement(
398 VectorValue, ScalarInst, Instance.Lane.getAsRuntimeExpr(Builder, VF));
399 set(Def, VectorValue, Instance.Part);
400}
401
403VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
404 // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
405 // Pred stands for Predessor. Prev stands for Previous - last visited/created.
406 BasicBlock *PrevBB = CFG.PrevBB;
407 BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
408 PrevBB->getParent(), CFG.ExitBB);
409 LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
410
411 // Hook up the new basic block to its predecessors.
412 for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
413 VPBasicBlock *PredVPBB = PredVPBlock->getExitingBasicBlock();
414 auto &PredVPSuccessors = PredVPBB->getHierarchicalSuccessors();
415 BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
416
417 assert(PredBB && "Predecessor basic-block not found building successor.");
418 auto *PredBBTerminator = PredBB->getTerminator();
419 LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
420
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();
426 PredBBTerminator->eraseFromParent();
427 auto *Br = BranchInst::Create(NewBB, PredBB);
428 Br->setDebugLoc(DL);
429 } else if (TermBr && !TermBr->isConditional()) {
430 TermBr->setSuccessor(0, NewBB);
431 } else {
432 // Set each forward successor here when it is created, excluding
433 // backedges. A backward successor is set when the branch is created.
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);
438 }
439 }
440 return NewBB;
441}
442
444 bool Replica = State->Instance && !State->Instance->isFirstIteration();
445 VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
446 VPBlockBase *SingleHPred = nullptr;
447 BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
448
449 auto IsLoopRegion = [](VPBlockBase *BB) {
450 auto *R = dyn_cast<VPRegionBlock>(BB);
451 return R && !R->isReplicator();
452 };
453
454 // 1. Create an IR basic block, or reuse the last one or ExitBB if possible.
455 if (getPlan()->getVectorLoopRegion()->getSingleSuccessor() == this) {
456 // ExitBB can be re-used for the exit block of the Plan.
457 NewBB = State->CFG.ExitBB;
458 State->CFG.PrevBB = NewBB;
459 State->Builder.SetInsertPoint(NewBB->getFirstNonPHI());
460
461 // Update the branch instruction in the predecessor to branch to ExitBB.
462 VPBlockBase *PredVPB = getSingleHierarchicalPredecessor();
463 VPBasicBlock *ExitingVPBB = PredVPB->getExitingBasicBlock();
464 assert(PredVPB->getSingleSuccessor() == this &&
465 "predecessor must have the current block as only successor");
466 BasicBlock *ExitingBB = State->CFG.VPBB2IRBB[ExitingVPBB];
467 // The Exit block of a loop is always set to be successor 0 of the Exiting
468 // block.
469 cast<BranchInst>(ExitingBB->getTerminator())->setSuccessor(0, NewBB);
470 } else if (PrevVPBB && /* A */
471 !((SingleHPred = getSingleHierarchicalPredecessor()) &&
472 SingleHPred->getExitingBasicBlock() == PrevVPBB &&
473 PrevVPBB->getSingleHierarchicalSuccessor() &&
474 (SingleHPred->getParent() == getEnclosingLoopRegion() &&
475 !IsLoopRegion(SingleHPred))) && /* B */
476 !(Replica && getPredecessors().empty())) { /* C */
477 // The last IR basic block is reused, as an optimization, in three cases:
478 // A. the first VPBB reuses the loop pre-header BB - when PrevVPBB is null;
479 // B. when the current VPBB has a single (hierarchical) predecessor which
480 // is PrevVPBB and the latter has a single (hierarchical) successor which
481 // both are in the same non-replicator region; and
482 // C. when the current VPBB is an entry of a region replica - where PrevVPBB
483 // is the exiting VPBB of this region from a previous instance, or the
484 // predecessor of this region.
485
486 NewBB = createEmptyBasicBlock(State->CFG);
487 State->Builder.SetInsertPoint(NewBB);
488 // Temporarily terminate with unreachable until CFG is rewired.
489 UnreachableInst *Terminator = State->Builder.CreateUnreachable();
490 // Register NewBB in its loop. In innermost loops its the same for all
491 // BB's.
492 if (State->CurrentVectorLoop)
493 State->CurrentVectorLoop->addBasicBlockToLoop(NewBB, *State->LI);
494 State->Builder.SetInsertPoint(Terminator);
495 State->CFG.PrevBB = NewBB;
496 }
497
498 // 2. Fill the IR basic block with IR instructions.
499 LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
500 << " in BB:" << NewBB->getName() << '\n');
501
502 State->CFG.VPBB2IRBB[this] = NewBB;
503 State->CFG.PrevVPBB = this;
504
505 for (VPRecipeBase &Recipe : Recipes)
506 Recipe.execute(*State);
507
508 LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
509}
510
512 for (VPRecipeBase &R : Recipes) {
513 for (auto *Def : R.definedValues())
514 Def->replaceAllUsesWith(NewValue);
515
516 for (unsigned I = 0, E = R.getNumOperands(); I != E; I++)
517 R.setOperand(I, NewValue);
518 }
519}
520
522 assert((SplitAt == end() || SplitAt->getParent() == this) &&
523 "can only split at a position in the same block");
524
526 // First, disconnect the current block from its successors.
527 for (VPBlockBase *Succ : Succs)
529
530 // Create new empty block after the block to split.
531 auto *SplitBlock = new VPBasicBlock(getName() + ".split");
533
534 // Add successors for block to split to new block.
535 for (VPBlockBase *Succ : Succs)
537
538 // Finally, move the recipes starting at SplitAt to new block.
539 for (VPRecipeBase &ToMove :
540 make_early_inc_range(make_range(SplitAt, this->end())))
541 ToMove.moveBefore(*SplitBlock, SplitBlock->end());
542
543 return SplitBlock;
544}
545
548 if (P && P->isReplicator()) {
549 P = P->getParent();
550 assert(!cast<VPRegionBlock>(P)->isReplicator() &&
551 "unexpected nested replicate regions");
552 }
553 return P;
554}
555
556static bool hasConditionalTerminator(const VPBasicBlock *VPBB) {
557 if (VPBB->empty()) {
558 assert(
559 VPBB->getNumSuccessors() < 2 &&
560 "block with multiple successors doesn't have a recipe as terminator");
561 return false;
562 }
563
564 const VPRecipeBase *R = &VPBB->back();
565 bool IsCondBranch = isa<VPBranchOnMaskRecipe>(R) ||
568 (void)IsCondBranch;
569
570 if (VPBB->getNumSuccessors() >= 2 ||
571 (VPBB->isExiting() && !VPBB->getParent()->isReplicator())) {
572 assert(IsCondBranch && "block with multiple successors not terminated by "
573 "conditional branch recipe");
574
575 return true;
576 }
577
578 assert(
579 !IsCondBranch &&
580 "block with 0 or 1 successors terminated by conditional branch recipe");
581 return false;
582}
583
585 if (hasConditionalTerminator(this))
586 return &back();
587 return nullptr;
588}
589
591 if (hasConditionalTerminator(this))
592 return &back();
593 return nullptr;
594}
595
597 return getParent() && getParent()->getExitingBasicBlock() == this;
598}
599
600#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
601void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const {
602 if (getSuccessors().empty()) {
603 O << Indent << "No successors\n";
604 } else {
605 O << Indent << "Successor(s): ";
606 ListSeparator LS;
607 for (auto *Succ : getSuccessors())
608 O << LS << Succ->getName();
609 O << '\n';
610 }
611}
612
613void VPBasicBlock::print(raw_ostream &O, const Twine &Indent,
614 VPSlotTracker &SlotTracker) const {
615 O << Indent << getName() << ":\n";
616
617 auto RecipeIndent = Indent + " ";
618 for (const VPRecipeBase &Recipe : *this) {
619 Recipe.print(O, RecipeIndent, SlotTracker);
620 O << '\n';
621 }
622
623 printSuccessors(O, Indent);
624}
625#endif
626
627static std::pair<VPBlockBase *, VPBlockBase *> cloneSESE(VPBlockBase *Entry);
628
629// Clone the CFG for all nodes in the single-entry-single-exit region reachable
630// from \p Entry, this includes cloning the blocks and their recipes. Operands
631// of cloned recipes will NOT be updated. Remapping of operands must be done
632// separately. Returns a pair with the the new entry and exiting blocks of the
633// cloned region.
634static std::pair<VPBlockBase *, VPBlockBase *> cloneSESE(VPBlockBase *Entry) {
637 Entry);
638 for (VPBlockBase *BB : RPOT) {
639 VPBlockBase *NewBB = BB->clone();
640 for (VPBlockBase *Pred : BB->getPredecessors())
641 VPBlockUtils::connectBlocks(Old2NewVPBlocks[Pred], NewBB);
642
643 Old2NewVPBlocks[BB] = NewBB;
644 }
645
646#if !defined(NDEBUG)
647 // Verify that the order of predecessors and successors matches in the cloned
648 // version.
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");
655
656 for (const auto &[OldSucc, NewSucc] :
657 zip(OldBB->successors(), NewBB->successors()))
658 assert(NewSucc == Old2NewVPBlocks[OldSucc] && "Different successors");
659 }
660#endif
661
662 return std::make_pair(Old2NewVPBlocks[Entry],
663 Old2NewVPBlocks[*reverse(RPOT).begin()]);
664}
665
667 const auto &[NewEntry, NewExiting] = cloneSESE(getEntry());
668 auto *NewRegion =
669 new VPRegionBlock(NewEntry, NewExiting, getName(), isReplicator());
670 for (VPBlockBase *Block : vp_depth_first_shallow(NewEntry))
671 Block->setParent(NewRegion);
672 return NewRegion;
673}
674
677 // Drop all references in VPBasicBlocks and replace all uses with
678 // DummyValue.
679 Block->dropAllReferences(NewValue);
680}
681
684 RPOT(Entry);
685
686 if (!isReplicator()) {
687 // Create and register the new vector loop.
688 Loop *PrevLoop = State->CurrentVectorLoop;
689 State->CurrentVectorLoop = State->LI->AllocateLoop();
690 BasicBlock *VectorPH = State->CFG.VPBB2IRBB[getPreheaderVPBB()];
691 Loop *ParentLoop = State->LI->getLoopFor(VectorPH);
692
693 // Insert the new loop into the loop nest and register the new basic blocks
694 // before calling any utilities such as SCEV that require valid LoopInfo.
695 if (ParentLoop)
696 ParentLoop->addChildLoop(State->CurrentVectorLoop);
697 else
698 State->LI->addTopLevelLoop(State->CurrentVectorLoop);
699
700 // Visit the VPBlocks connected to "this", starting from it.
701 for (VPBlockBase *Block : RPOT) {
702 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
703 Block->execute(State);
704 }
705
706 State->CurrentVectorLoop = PrevLoop;
707 return;
708 }
709
710 assert(!State->Instance && "Replicating a Region with non-null instance.");
711
712 // Enter replicating mode.
713 State->Instance = VPIteration(0, 0);
714
715 for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
716 State->Instance->Part = Part;
717 assert(!State->VF.isScalable() && "VF is assumed to be non scalable.");
718 for (unsigned Lane = 0, VF = State->VF.getKnownMinValue(); Lane < VF;
719 ++Lane) {
720 State->Instance->Lane = VPLane(Lane, VPLane::Kind::First);
721 // Visit the VPBlocks connected to \p this, starting from it.
722 for (VPBlockBase *Block : RPOT) {
723 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
724 Block->execute(State);
725 }
726 }
727 }
728
729 // Exit replicating mode.
730 State->Instance.reset();
731}
732
733#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
735 VPSlotTracker &SlotTracker) const {
736 O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {";
737 auto NewIndent = Indent + " ";
738 for (auto *BlockBase : vp_depth_first_shallow(Entry)) {
739 O << '\n';
740 BlockBase->print(O, NewIndent, SlotTracker);
741 }
742 O << Indent << "}\n";
743
744 printSuccessors(O, Indent);
745}
746#endif
747
749 for (auto &KV : LiveOuts)
750 delete KV.second;
751 LiveOuts.clear();
752
753 if (Entry) {
754 VPValue DummyValue;
756 Block->dropAllReferences(&DummyValue);
757
759
760 Preheader->dropAllReferences(&DummyValue);
761 delete Preheader;
762 }
763 for (VPValue *VPV : VPLiveInsToFree)
764 delete VPV;
765 if (BackedgeTakenCount)
766 delete BackedgeTakenCount;
767}
768
770 VPBasicBlock *Preheader = new VPBasicBlock("ph");
771 VPBasicBlock *VecPreheader = new VPBasicBlock("vector.ph");
772 auto Plan = std::make_unique<VPlan>(Preheader, VecPreheader);
773 Plan->TripCount =
775 // Create empty VPRegionBlock, to be filled during processing later.
776 auto *TopRegion = new VPRegionBlock("vector loop", false /*isReplicator*/);
777 VPBlockUtils::insertBlockAfter(TopRegion, VecPreheader);
778 VPBasicBlock *MiddleVPBB = new VPBasicBlock("middle.block");
779 VPBlockUtils::insertBlockAfter(MiddleVPBB, TopRegion);
780 return Plan;
781}
782
783void VPlan::prepareToExecute(Value *TripCountV, Value *VectorTripCountV,
784 Value *CanonicalIVStartValue,
785 VPTransformState &State) {
786 // Check if the backedge taken count is needed, and if so build it.
787 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
789 auto *TCMO = Builder.CreateSub(TripCountV,
790 ConstantInt::get(TripCountV->getType(), 1),
791 "trip.count.minus.1");
792 BackedgeTakenCount->setUnderlyingValue(TCMO);
793 }
794
795 VectorTripCount.setUnderlyingValue(VectorTripCountV);
796
798 // FIXME: Model VF * UF computation completely in VPlan.
799 VFxUF.setUnderlyingValue(
800 createStepForVF(Builder, TripCountV->getType(), State.VF, State.UF));
801
802 // When vectorizing the epilogue loop, the canonical induction start value
803 // needs to be changed from zero to the value after the main vector loop.
804 // FIXME: Improve modeling for canonical IV start values in the epilogue loop.
805 if (CanonicalIVStartValue) {
806 VPValue *VPV = getOrAddLiveIn(CanonicalIVStartValue);
807 auto *IV = getCanonicalIV();
808 assert(all_of(IV->users(),
809 [](const VPUser *U) {
810 return isa<VPScalarIVStepsRecipe>(U) ||
811 isa<VPScalarCastRecipe>(U) ||
812 isa<VPDerivedIVRecipe>(U) ||
813 cast<VPInstruction>(U)->getOpcode() ==
814 Instruction::Add;
815 }) &&
816 "the canonical IV should only be used by its increment or "
817 "ScalarIVSteps when resetting the start value");
818 IV->setOperand(0, VPV);
819 }
820}
821
822/// Generate the code inside the preheader and body of the vectorized loop.
823/// Assumes a single pre-header basic-block was created for this. Introduce
824/// additional basic-blocks as needed, and fill them all.
826 // Initialize CFG state.
827 State->CFG.PrevVPBB = nullptr;
828 State->CFG.ExitBB = State->CFG.PrevBB->getSingleSuccessor();
829 BasicBlock *VectorPreHeader = State->CFG.PrevBB;
830 State->Builder.SetInsertPoint(VectorPreHeader->getTerminator());
831
832 // Generate code in the loop pre-header and body.
834 Block->execute(State);
835
836 VPBasicBlock *LatchVPBB = getVectorLoopRegion()->getExitingBasicBlock();
837 BasicBlock *VectorLatchBB = State->CFG.VPBB2IRBB[LatchVPBB];
838
839 // Fix the latch value of canonical, reduction and first-order recurrences
840 // phis in the vector loop.
841 VPBasicBlock *Header = getVectorLoopRegion()->getEntryBasicBlock();
842 for (VPRecipeBase &R : Header->phis()) {
843 // Skip phi-like recipes that generate their backedege values themselves.
844 if (isa<VPWidenPHIRecipe>(&R))
845 continue;
846
847 if (isa<VPWidenPointerInductionRecipe>(&R) ||
848 isa<VPWidenIntOrFpInductionRecipe>(&R)) {
849 PHINode *Phi = nullptr;
850 if (isa<VPWidenIntOrFpInductionRecipe>(&R)) {
851 Phi = cast<PHINode>(State->get(R.getVPSingleValue(), 0));
852 } else {
853 auto *WidenPhi = cast<VPWidenPointerInductionRecipe>(&R);
854 assert(!WidenPhi->onlyScalarsGenerated(State->VF.isScalable()) &&
855 "recipe generating only scalars should have been replaced");
856 auto *GEP = cast<GetElementPtrInst>(State->get(WidenPhi, 0));
857 Phi = cast<PHINode>(GEP->getPointerOperand());
858 }
859
860 Phi->setIncomingBlock(1, VectorLatchBB);
861
862 // Move the last step to the end of the latch block. This ensures
863 // consistent placement of all induction updates.
864 Instruction *Inc = cast<Instruction>(Phi->getIncomingValue(1));
865 Inc->moveBefore(VectorLatchBB->getTerminator()->getPrevNode());
866 continue;
867 }
868
869 auto *PhiR = cast<VPHeaderPHIRecipe>(&R);
870 // For canonical IV, first-order recurrences and in-order reduction phis,
871 // only a single part is generated, which provides the last part from the
872 // previous iteration. For non-ordered reductions all UF parts are
873 // generated.
874 bool SinglePartNeeded =
875 isa<VPCanonicalIVPHIRecipe>(PhiR) ||
876 isa<VPFirstOrderRecurrencePHIRecipe, VPEVLBasedIVPHIRecipe>(PhiR) ||
877 (isa<VPReductionPHIRecipe>(PhiR) &&
878 cast<VPReductionPHIRecipe>(PhiR)->isOrdered());
879 bool NeedsScalar =
880 isa<VPCanonicalIVPHIRecipe, VPEVLBasedIVPHIRecipe>(PhiR) ||
881 (isa<VPReductionPHIRecipe>(PhiR) &&
882 cast<VPReductionPHIRecipe>(PhiR)->isInLoop());
883 unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->UF;
884
885 for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
886 Value *Phi = State->get(PhiR, Part, NeedsScalar);
887 Value *Val =
888 State->get(PhiR->getBackedgeValue(),
889 SinglePartNeeded ? State->UF - 1 : Part, NeedsScalar);
890 cast<PHINode>(Phi)->addIncoming(Val, VectorLatchBB);
891 }
892 }
893
894 // We do not attempt to preserve DT for outer loop vectorization currently.
896 BasicBlock *VectorHeaderBB = State->CFG.VPBB2IRBB[Header];
897 State->DT->addNewBlock(VectorHeaderBB, VectorPreHeader);
898 updateDominatorTree(State->DT, VectorHeaderBB, VectorLatchBB,
899 State->CFG.ExitBB);
900 }
901}
902
903#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
906
907 if (VFxUF.getNumUsers() > 0) {
908 O << "\nLive-in ";
909 VFxUF.printAsOperand(O, SlotTracker);
910 O << " = VF * UF";
911 }
912
913 if (VectorTripCount.getNumUsers() > 0) {
914 O << "\nLive-in ";
915 VectorTripCount.printAsOperand(O, SlotTracker);
916 O << " = vector-trip-count";
917 }
918
919 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
920 O << "\nLive-in ";
921 BackedgeTakenCount->printAsOperand(O, SlotTracker);
922 O << " = backedge-taken count";
923 }
924
925 O << "\n";
926 if (TripCount->isLiveIn())
927 O << "Live-in ";
928 TripCount->printAsOperand(O, SlotTracker);
929 O << " = original trip-count";
930 O << "\n";
931}
932
934void VPlan::print(raw_ostream &O) const {
936
937 O << "VPlan '" << getName() << "' {";
938
939 printLiveIns(O);
940
941 if (!getPreheader()->empty()) {
942 O << "\n";
943 getPreheader()->print(O, "", SlotTracker);
944 }
945
946 for (const VPBlockBase *Block : vp_depth_first_shallow(getEntry())) {
947 O << '\n';
948 Block->print(O, "", SlotTracker);
949 }
950
951 if (!LiveOuts.empty())
952 O << "\n";
953 for (const auto &KV : LiveOuts) {
954 KV.second->print(O, SlotTracker);
955 }
956
957 O << "}\n";
958}
959
960std::string VPlan::getName() const {
961 std::string Out;
962 raw_string_ostream RSO(Out);
963 RSO << Name << " for ";
964 if (!VFs.empty()) {
965 RSO << "VF={" << VFs[0];
966 for (ElementCount VF : drop_begin(VFs))
967 RSO << "," << VF;
968 RSO << "},";
969 }
970
971 if (UFs.empty()) {
972 RSO << "UF>=1";
973 } else {
974 RSO << "UF={" << UFs[0];
975 for (unsigned UF : drop_begin(UFs))
976 RSO << "," << UF;
977 RSO << "}";
978 }
979
980 return Out;
981}
982
985 VPlanPrinter Printer(O, *this);
986 Printer.dump();
987}
988
990void VPlan::dump() const { print(dbgs()); }
991#endif
992
994 assert(LiveOuts.count(PN) == 0 && "an exit value for PN already exists");
995 LiveOuts.insert({PN, new VPLiveOut(PN, V)});
996}
997
998void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopHeaderBB,
999 BasicBlock *LoopLatchBB,
1000 BasicBlock *LoopExitBB) {
1001 // The vector body may be more than a single basic-block by this point.
1002 // Update the dominator tree information inside the vector body by propagating
1003 // it from header to latch, expecting only triangular control-flow, if any.
1004 BasicBlock *PostDomSucc = nullptr;
1005 for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
1006 // Get the list of successors of this block.
1007 std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
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) {
1012 assert(PostDomSucc->getSinglePredecessor() &&
1013 "PostDom successor has more than one predecessor.");
1014 DT->addNewBlock(PostDomSucc, BB);
1015 continue;
1016 }
1017 BasicBlock *InterimSucc = Succs[1];
1018 if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
1019 PostDomSucc = Succs[1];
1020 InterimSucc = Succs[0];
1021 }
1022 assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
1023 "One successor of a basic block does not lead to the other.");
1024 assert(InterimSucc->getSinglePredecessor() &&
1025 "Interim successor has more than one predecessor.");
1026 assert(PostDomSucc->hasNPredecessors(2) &&
1027 "PostDom successor has more than two predecessors.");
1028 DT->addNewBlock(InterimSucc, BB);
1029 DT->addNewBlock(PostDomSucc, BB);
1030 }
1031 // Latch block is a new dominator for the loop exit.
1032 DT->changeImmediateDominator(LoopExitBB, LoopLatchBB);
1033 assert(DT->verify(DominatorTree::VerificationLevel::Fast));
1034}
1035
1036static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry,
1037 DenseMap<VPValue *, VPValue *> &Old2NewVPValues) {
1038 // Update the operands of all cloned recipes starting at NewEntry. This
1039 // traverses all reachable blocks. This is done in two steps, to handle cycles
1040 // in PHI recipes.
1042 OldDeepRPOT(Entry);
1044 NewDeepRPOT(NewEntry);
1045 // First, collect all mappings from old to new VPValues defined by cloned
1046 // recipes.
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;
1060 }
1061 }
1062
1063 // Update all operands to use cloned VPValues.
1064 for (VPBasicBlock *NewBB :
1065 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT)) {
1066 for (VPRecipeBase &NewR : *NewBB)
1067 for (unsigned I = 0, E = NewR.getNumOperands(); I != E; ++I) {
1068 VPValue *NewOp = Old2NewVPValues.lookup(NewR.getOperand(I));
1069 NewR.setOperand(I, NewOp);
1070 }
1071 }
1072}
1073
1075 // Clone blocks.
1076 VPBasicBlock *NewPreheader = Preheader->clone();
1077 const auto &[NewEntry, __] = cloneSESE(Entry);
1078
1079 // Create VPlan, clone live-ins and remap operands in the cloned blocks.
1080 auto *NewPlan = new VPlan(NewPreheader, cast<VPBasicBlock>(NewEntry));
1081 DenseMap<VPValue *, VPValue *> Old2NewVPValues;
1082 for (VPValue *OldLiveIn : VPLiveInsToFree) {
1083 Old2NewVPValues[OldLiveIn] =
1084 NewPlan->getOrAddLiveIn(OldLiveIn->getLiveInIRValue());
1085 }
1086 Old2NewVPValues[&VectorTripCount] = &NewPlan->VectorTripCount;
1087 Old2NewVPValues[&VFxUF] = &NewPlan->VFxUF;
1088 if (BackedgeTakenCount) {
1089 NewPlan->BackedgeTakenCount = new VPValue();
1090 Old2NewVPValues[BackedgeTakenCount] = NewPlan->BackedgeTakenCount;
1091 }
1092 assert(TripCount && "trip count must be set");
1093 if (TripCount->isLiveIn())
1094 Old2NewVPValues[TripCount] =
1095 NewPlan->getOrAddLiveIn(TripCount->getLiveInIRValue());
1096 // else NewTripCount will be created and inserted into Old2NewVPValues when
1097 // TripCount is cloned. In any case NewPlan->TripCount is updated below.
1098
1099 remapOperands(Preheader, NewPreheader, Old2NewVPValues);
1100 remapOperands(Entry, NewEntry, Old2NewVPValues);
1101
1102 // Clone live-outs.
1103 for (const auto &[_, LO] : LiveOuts)
1104 NewPlan->addLiveOut(LO->getPhi(), Old2NewVPValues[LO->getOperand(0)]);
1105
1106 // Initialize remaining fields of cloned VPlan.
1107 NewPlan->VFs = VFs;
1108 NewPlan->UFs = UFs;
1109 // TODO: Adjust names.
1110 NewPlan->Name = Name;
1111 assert(Old2NewVPValues.contains(TripCount) &&
1112 "TripCount must have been added to Old2NewVPValues");
1113 NewPlan->TripCount = Old2NewVPValues[TripCount];
1114 return NewPlan;
1115}
1116
1117#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1118
1119Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
1120 return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
1121 Twine(getOrCreateBID(Block));
1122}
1123
1124Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
1125 const std::string &Name = Block->getName();
1126 if (!Name.empty())
1127 return Name;
1128 return "VPB" + Twine(getOrCreateBID(Block));
1129}
1130
1132 Depth = 1;
1133 bumpIndent(0);
1134 OS << "digraph VPlan {\n";
1135 OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
1136 if (!Plan.getName().empty())
1137 OS << "\\n" << DOT::EscapeString(Plan.getName());
1138
1139 {
1140 // Print live-ins.
1141 std::string Str;
1142 raw_string_ostream SS(Str);
1143 Plan.printLiveIns(SS);
1145 StringRef(Str).rtrim('\n').split(Lines, "\n");
1146 for (auto Line : Lines)
1147 OS << DOT::EscapeString(Line.str()) << "\\n";
1148 }
1149
1150 OS << "\"]\n";
1151 OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
1152 OS << "edge [fontname=Courier, fontsize=30]\n";
1153 OS << "compound=true\n";
1154
1155 dumpBlock(Plan.getPreheader());
1156
1158 dumpBlock(Block);
1159
1160 OS << "}\n";
1161}
1162
1163void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
1164 if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
1165 dumpBasicBlock(BasicBlock);
1166 else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1167 dumpRegion(Region);
1168 else
1169 llvm_unreachable("Unsupported kind of VPBlock.");
1170}
1171
1172void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
1173 bool Hidden, const Twine &Label) {
1174 // Due to "dot" we print an edge between two regions as an edge between the
1175 // exiting basic block and the entry basic of the respective regions.
1176 const VPBlockBase *Tail = From->getExitingBasicBlock();
1177 const VPBlockBase *Head = To->getEntryBasicBlock();
1178 OS << Indent << getUID(Tail) << " -> " << getUID(Head);
1179 OS << " [ label=\"" << Label << '\"';
1180 if (Tail != From)
1181 OS << " ltail=" << getUID(From);
1182 if (Head != To)
1183 OS << " lhead=" << getUID(To);
1184 if (Hidden)
1185 OS << "; splines=none";
1186 OS << "]\n";
1187}
1188
1189void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
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");
1196 } else {
1197 unsigned SuccessorNumber = 0;
1198 for (auto *Successor : Successors)
1199 drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
1200 }
1201}
1202
1203void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
1204 // Implement dot-formatted dump by performing plain-text dump into the
1205 // temporary storage followed by some post-processing.
1206 OS << Indent << getUID(BasicBlock) << " [label =\n";
1207 bumpIndent(1);
1208 std::string Str;
1210 // Use no indentation as we need to wrap the lines into quotes ourselves.
1211 BasicBlock->print(SS, "", SlotTracker);
1212
1213 // We need to process each line of the output separately, so split
1214 // single-string plain-text dump.
1216 StringRef(Str).rtrim('\n').split(Lines, "\n");
1217
1218 auto EmitLine = [&](StringRef Line, StringRef Suffix) {
1219 OS << Indent << '"' << DOT::EscapeString(Line.str()) << "\\l\"" << Suffix;
1220 };
1221
1222 // Don't need the "+" after the last line.
1223 for (auto Line : make_range(Lines.begin(), Lines.end() - 1))
1224 EmitLine(Line, " +\n");
1225 EmitLine(Lines.back(), "\n");
1226
1227 bumpIndent(-1);
1228 OS << Indent << "]\n";
1229
1231}
1232
1233void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
1234 OS << Indent << "subgraph " << getUID(Region) << " {\n";
1235 bumpIndent(1);
1236 OS << Indent << "fontname=Courier\n"
1237 << Indent << "label=\""
1238 << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
1239 << DOT::EscapeString(Region->getName()) << "\"\n";
1240 // Dump the blocks of the region.
1241 assert(Region->getEntry() && "Region contains no inner blocks.");
1243 dumpBlock(Block);
1244 bumpIndent(-1);
1245 OS << Indent << "}\n";
1247}
1248
1250 if (auto *Inst = dyn_cast<Instruction>(V)) {
1251 if (!Inst->getType()->isVoidTy()) {
1252 Inst->printAsOperand(O, false);
1253 O << " = ";
1254 }
1255 O << Inst->getOpcodeName() << " ";
1256 unsigned E = Inst->getNumOperands();
1257 if (E > 0) {
1258 Inst->getOperand(0)->printAsOperand(O, false);
1259 for (unsigned I = 1; I < E; ++I)
1260 Inst->getOperand(I)->printAsOperand(O << ", ", false);
1261 }
1262 } else // !Inst
1263 V->printAsOperand(O, false);
1264}
1265
1266#endif
1267
1268template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
1269
1271 replaceUsesWithIf(New, [](VPUser &, unsigned) { return true; });
1272}
1273
1275 VPValue *New,
1276 llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace) {
1277 // Note that this early exit is required for correctness; the implementation
1278 // below relies on the number of users for this VPValue to decrease, which
1279 // isn't the case if this == New.
1280 if (this == New)
1281 return;
1282
1283 for (unsigned J = 0; J < getNumUsers();) {
1284 VPUser *User = Users[J];
1285 bool RemovedUser = false;
1286 for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
1287 if (User->getOperand(I) != this || !ShouldReplace(*User, I))
1288 continue;
1289
1290 RemovedUser = true;
1291 User->setOperand(I, New);
1292 }
1293 // If a user got removed after updating the current user, the next user to
1294 // update will be moved to the current position, so we only need to
1295 // increment the index if the number of users did not change.
1296 if (!RemovedUser)
1297 J++;
1298 }
1299}
1300
1301#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1303 OS << Tracker.getOrCreateName(this);
1304}
1305
1307 interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) {
1308 Op->printAsOperand(O, SlotTracker);
1309 });
1310}
1311#endif
1312
1313void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
1314 Old2NewTy &Old2New,
1315 InterleavedAccessInfo &IAI) {
1317 RPOT(Region->getEntry());
1318 for (VPBlockBase *Base : RPOT) {
1319 visitBlock(Base, Old2New, IAI);
1320 }
1321}
1322
1323void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
1324 InterleavedAccessInfo &IAI) {
1325 if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
1326 for (VPRecipeBase &VPI : *VPBB) {
1327 if (isa<VPWidenPHIRecipe>(&VPI))
1328 continue;
1329 assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
1330 auto *VPInst = cast<VPInstruction>(&VPI);
1331
1332 auto *Inst = dyn_cast_or_null<Instruction>(VPInst->getUnderlyingValue());
1333 if (!Inst)
1334 continue;
1335 auto *IG = IAI.getInterleaveGroup(Inst);
1336 if (!IG)
1337 continue;
1338
1339 auto NewIGIter = Old2New.find(IG);
1340 if (NewIGIter == Old2New.end())
1341 Old2New[IG] = new InterleaveGroup<VPInstruction>(
1342 IG->getFactor(), IG->isReverse(), IG->getAlign());
1343
1344 if (Inst == IG->getInsertPos())
1345 Old2New[IG]->setInsertPos(VPInst);
1346
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()));
1352 }
1353 } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1354 visitRegion(Region, Old2New, IAI);
1355 else
1356 llvm_unreachable("Unsupported kind of VPBlock.");
1357}
1358
1360 InterleavedAccessInfo &IAI) {
1361 Old2NewTy Old2New;
1362 visitRegion(Plan.getVectorLoopRegion(), Old2New, IAI);
1363}
1364
1365void VPSlotTracker::assignName(const VPValue *V) {
1366 assert(!VPValue2Name.contains(V) && "VPValue already has a name!");
1367 auto *UV = V->getUnderlyingValue();
1368 if (!UV) {
1369 VPValue2Name[V] = (Twine("vp<%") + Twine(NextSlot) + ">").str();
1370 NextSlot++;
1371 return;
1372 }
1373
1374 // Use the name of the underlying Value, wrapped in "ir<>", and versioned by
1375 // appending ".Number" to the name if there are multiple uses.
1376 std::string Name;
1378 UV->printAsOperand(S, false);
1379 assert(!Name.empty() && "Name cannot be empty.");
1380 std::string BaseName = (Twine("ir<") + Name + Twine(">")).str();
1381
1382 // First assign the base name for V.
1383 const auto &[A, _] = VPValue2Name.insert({V, BaseName});
1384 // Integer or FP constants with different types will result in he same string
1385 // due to stripping types.
1386 if (V->isLiveIn() && isa<ConstantInt, ConstantFP>(UV))
1387 return;
1388
1389 // If it is already used by C > 0 other VPValues, increase the version counter
1390 // C and use it for V.
1391 const auto &[C, UseInserted] = BaseName2Version.insert({BaseName, 0});
1392 if (!UseInserted) {
1393 C->second++;
1394 A->second = (BaseName + Twine(".") + Twine(C->second)).str();
1395 }
1396}
1397
1398void VPSlotTracker::assignNames(const VPlan &Plan) {
1399 if (Plan.VFxUF.getNumUsers() > 0)
1400 assignName(&Plan.VFxUF);
1401 assignName(&Plan.VectorTripCount);
1402 if (Plan.BackedgeTakenCount)
1403 assignName(Plan.BackedgeTakenCount);
1404 for (VPValue *LI : Plan.VPLiveInsToFree)
1405 assignName(LI);
1406 assignNames(Plan.getPreheader());
1407
1410 for (const VPBasicBlock *VPBB :
1411 VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
1412 assignNames(VPBB);
1413}
1414
1415void VPSlotTracker::assignNames(const VPBasicBlock *VPBB) {
1416 for (const VPRecipeBase &Recipe : *VPBB)
1417 for (VPValue *Def : Recipe.definedValues())
1418 assignName(Def);
1419}
1420
1421std::string VPSlotTracker::getOrCreateName(const VPValue *V) const {
1422 std::string Name = VPValue2Name.lookup(V);
1423 if (!Name.empty())
1424 return Name;
1425
1426 // If no name was assigned, no VPlan was provided when creating the slot
1427 // tracker or it is not reachable from the provided VPlan. This can happen,
1428 // e.g. when trying to print a recipe that has not been inserted into a VPlan
1429 // in a debugger.
1430 // TODO: Update VPSlotTracker constructor to assign names to recipes &
1431 // VPValues not associated with a VPlan, instead of constructing names ad-hoc
1432 // here.
1433 const VPRecipeBase *DefR = V->getDefiningRecipe();
1434 (void)DefR;
1435 assert((!DefR || !DefR->getParent() || !DefR->getParent()->getPlan()) &&
1436 "VPValue defined by a recipe in a VPlan?");
1437
1438 // Use the underlying value's name, if there is one.
1439 if (auto *UV = V->getUnderlyingValue()) {
1440 std::string Name;
1442 UV->printAsOperand(S, false);
1443 return (Twine("ir<") + Name + ">").str();
1444 }
1445
1446 return "<badref>";
1447}
1448
1450 return all_of(Def->users(),
1451 [Def](const VPUser *U) { return U->onlyFirstLaneUsed(Def); });
1452}
1453
1455 return all_of(Def->users(),
1456 [Def](const VPUser *U) { return U->onlyFirstPartUsed(Def); });
1457}
1458
1460 ScalarEvolution &SE) {
1461 if (auto *Expanded = Plan.getSCEVExpansion(Expr))
1462 return Expanded;
1463 VPValue *Expanded = nullptr;
1464 if (auto *E = dyn_cast<SCEVConstant>(Expr))
1465 Expanded = Plan.getOrAddLiveIn(E->getValue());
1466 else if (auto *E = dyn_cast<SCEVUnknown>(Expr))
1467 Expanded = Plan.getOrAddLiveIn(E->getValue());
1468 else {
1469 Expanded = new VPExpandSCEVRecipe(Expr, SE);
1471 }
1472 Plan.addSCEVExpansion(Expr, Expanded);
1473 return Expanded;
1474}
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.
Definition: Compiler.h:537
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
#define LLVM_DEBUG(X)
Definition: Debug.h:101
std::string Name
static void dumpEdges(CFGMST< Edge, BBInfo > &MST, GCOVFunction &GF)
Generic dominator tree construction - this file provides routines to construct immediate dominator in...
Hexagon Common GEP
#define _
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iv Induction Variable Users
Definition: IVUsers.cpp:48
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
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 contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the SmallVector class.
This file contains some functions that are useful when dealing with strings.
This file implements dominator tree analysis for a single level of a VPlan's H-CFG.
static T * getPlanEntry(T *Start)
Definition: VPlan.cpp:128
static std::pair< VPBlockBase *, VPBlockBase * > cloneSESE(VPBlockBase *Entry)
Definition: VPlan.cpp:634
static bool hasConditionalTerminator(const VPBasicBlock *VPBB)
Definition: VPlan.cpp:556
static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry, DenseMap< VPValue *, VPValue * > &Old2NewVPValues)
Definition: VPlan.cpp:1036
This file contains the declarations of the Vectorization Plan base classes:
static bool IsCondBranch(unsigned BrOpc)
static const uint32_t IV[8]
Definition: blake3_impl.h:78
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator end()
Definition: BasicBlock.h:443
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.
Definition: AsmWriter.cpp:4836
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:360
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:199
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
Definition: BasicBlock.cpp:474
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:452
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:482
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:206
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:165
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:168
size_t size() const
Definition: BasicBlock.h:451
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...
Definition: BasicBlock.h:221
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
Debug location.
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.
A debug info location.
Definition: DebugLoc.h:33
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...
Definition: DenseMap.h:202
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:145
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.
Definition: Dominators.h:162
constexpr bool isScalar() const
Exactly one element.
Definition: TypeSize.h:319
bool shouldEmitDebugInfoForProfiling() const
Returns true if we should emit debug info for profiling.
Definition: Metadata.cpp:1834
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:94
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2472
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2460
UnreachableInst * CreateUnreachable()
Definition: IRBuilder.h:1263
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Definition: IRBuilder.cpp:1192
IntegerType * getInt32Ty()
Fetch the type representing a 32-bit integer.
Definition: IRBuilder.h:526
BasicBlock * GetInsertBlock() const
Definition: IRBuilder.h:174
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: IRBuilder.h:220
InsertPoint saveIP() const
Returns the current insert point.
Definition: IRBuilder.h:277
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:486
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1344
void restoreIP(InsertPoint IP)
Sets the current insert point to a previously-saved location.
Definition: IRBuilder.h:289
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:180
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2666
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.
Definition: VectorUtils.h:445
Drive the analysis of interleaved memory accesses in the loop.
Definition: VectorUtils.h:587
InterleaveGroup< Instruction > * getInterleaveGroup(const Instruction *Instr) const
Get the interleave group that Instr belongs to.
Definition: VectorUtils.h:632
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
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.
Definition: LoopInfo.h:44
void eraseFromParent()
This method unlinks 'this' from the containing function and deletes it.
void dump() const
User-friendly dump.
Definition: AsmWriter.cpp:5272
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1827
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:322
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.
Definition: SetVector.h:98
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
This class provides computation of slot numbers for LLVM Assembly writing.
Definition: AsmWriter.cpp:693
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
std::pair< StringRef, StringRef > split(char Separator) const
Split into two substrings around the first occurrence of a separator character.
Definition: StringRef.h:693
StringRef rtrim(char Char) const
Return string with consecutive Char characters starting from the right removed.
Definition: StringRef.h:796
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
This function has undefined behavior.
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
Value * getOperand(unsigned i) const
Definition: User.h:169
unsigned getNumOperands() const
Definition: User.h:191
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:2827
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
Definition: VPlan.h:2895
VPBasicBlock * clone() override
Clone the current block and it's recipes, without updating the operands of the cloned recipes.
Definition: VPlan.h:2939
RecipeListTy::iterator iterator
Instruction iterators...
Definition: VPlan.h:2848
void execute(VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPBasicBlock,...
Definition: VPlan.cpp:443
iterator end()
Definition: VPlan.h:2858
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:2856
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
Definition: VPlan.cpp:210
VPRegionBlock * getEnclosingLoopRegion()
Definition: VPlan.cpp:546
void dropAllReferences(VPValue *NewValue) override
Replace all operands of VPUsers in the block with NewValue and also replaces all uses of VPValues def...
Definition: VPlan.cpp:511
VPBasicBlock * splitAt(iterator SplitAt)
Split current block at SplitAt by inserting a new block between the current block and its successors ...
Definition: VPlan.cpp:521
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print this VPBsicBlock to O, prefixing all lines with Indent.
Definition: VPlan.cpp:613
bool isExiting() const
Returns true if the block is exiting it's parent region.
Definition: VPlan.cpp:596
VPRecipeBase * getTerminator()
If the block has multiple successors, return the branch recipe terminating the block.
Definition: VPlan.cpp:584
const VPRecipeBase & back() const
Definition: VPlan.h:2870
bool empty() const
Definition: VPlan.h:2867
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:417
VPRegionBlock * getParent()
Definition: VPlan.h:489
const VPBasicBlock * getExitingBasicBlock() const
Definition: VPlan.cpp:175
size_t getNumSuccessors() const
Definition: VPlan.h:534
void printSuccessors(raw_ostream &O, const Twine &Indent) const
Print the successors of this block to O, prefixing all lines with Indent.
Definition: VPlan.cpp:601
VPBlockBase * getEnclosingBlockWithPredecessors()
Definition: VPlan.cpp:197
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:519
static void deleteCFG(VPBlockBase *Entry)
Delete all blocks reachable from a given VPBlockBase, inclusive.
Definition: VPlan.cpp:205
VPlan * getPlan()
Definition: VPlan.cpp:148
void setPlan(VPlan *ParentPlan)
Sets the pointer of the plan containing the block.
Definition: VPlan.cpp:167
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:560
VPBlockBase * getSinglePredecessor() const
Definition: VPlan.h:530
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:554
VPBlockBase * getEnclosingBlockWithSuccessors()
An Enclosing Block of a block B is any block containing B, including B itself.
Definition: VPlan.cpp:189
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:153
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:524
Helper for GraphTraits specialization that traverses through VPRegionBlocks.
Definition: VPlanCFG.h:115
static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBase NewBlock after BlockPtr.
Definition: VPlan.h:3384
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:3431
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:3420
This class augments a recipe with a set of VPValues defined by the recipe.
Definition: VPlanValue.h:308
void dump() const
Dump the VPDef to stderr (for debugging).
Definition: VPlan.cpp:109
virtual void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const =0
Each concrete VPDef prints itself.
Recipe to expand a SCEV expression.
Definition: VPlan.h:2534
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:1160
VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI)
Definition: VPlan.cpp:1359
In what follows, the term "input IR" refers to code that is fed into the vectorizer whereas the term ...
Definition: VPlan.h:143
Value * getAsRuntimeExpr(IRBuilderBase &Builder, const ElementCount &VF) const
Returns an expression describing the lane index that can be used at runtime.
Definition: VPlan.cpp:68
@ 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.
Definition: VPlan.h:669
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:709
VPBasicBlock * getParent()
Definition: VPlan.h:734
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:2960
VPRegionBlock * clone() override
Clone all blocks in the single-entry single-exit region of the block and their recipes without updati...
Definition: VPlan.cpp:666
const VPBlockBase * getEntry() const
Definition: VPlan.h:2999
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:3031
void dropAllReferences(VPValue *NewValue) override
Replace all operands of VPUsers in the block with NewValue and also replaces all uses of VPValues def...
Definition: VPlan.cpp:675
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print this VPRegionBlock to O (recursively), prefixing all lines with Indent.
Definition: VPlan.cpp:734
void execute(VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPRegionBlock,...
Definition: VPlan.cpp:682
const VPBlockBase * getExiting() const
Definition: VPlan.h:3011
VPBasicBlock * getPreheaderVPBB()
Returns the pre-header VPBasicBlock of the loop region.
Definition: VPlan.h:3024
This class can be used to assign names to VPValues.
Definition: VPlanValue.h:449
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...
Definition: VPlan.cpp:1421
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:203
void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const
Print the operands to O.
Definition: VPlan.cpp:1306
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
Definition: VPlan.cpp:118
void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const
Definition: VPlan.cpp:1302
void dump() const
Dump the value to stderr (for debugging).
Definition: VPlan.cpp:101
VPValue(const unsigned char SC, Value *UV=nullptr, VPDef *Def=nullptr)
Definition: VPlan.cpp:81
virtual ~VPValue()
Definition: VPlan.cpp:87
void print(raw_ostream &OS, VPSlotTracker &Tracker) const
Definition: VPlan.cpp:94
void replaceAllUsesWith(VPValue *New)
Definition: VPlan.cpp:1270
unsigned getNumUsers() const
Definition: VPlanValue.h:112
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...
Definition: VPlan.cpp:1274
VPDef * Def
Pointer to the VPDef that defines this VPValue.
Definition: VPlanValue.h:64
VPlanPrinter prints a given VPlan to a given output stream.
Definition: VPlan.h:3304
LLVM_DUMP_METHOD void dump()
Definition: VPlan.cpp:1131
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:3061
void printDOT(raw_ostream &O) const
Print this VPlan in DOT format to O.
Definition: VPlan.cpp:984
std::string getName() const
Return a string with the name of the plan and the applicable VFs and UFs.
Definition: VPlan.cpp:960
void prepareToExecute(Value *TripCount, Value *VectorTripCount, Value *CanonicalIVStartValue, VPTransformState &State)
Prepare the plan for execution, setting up the required live-in values.
Definition: VPlan.cpp:783
VPBasicBlock * getEntry()
Definition: VPlan.h:3154
void addLiveOut(PHINode *PN, VPValue *V)
Definition: VPlan.cpp:993
VPBasicBlock * getPreheader()
Definition: VPlan.h:3286
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:3248
static VPlanPtr createInitialVPlan(const SCEV *TripCount, ScalarEvolution &PSE)
Create initial VPlan skeleton, having an "entry" VPBasicBlock (wrapping original scalar pre-header) w...
Definition: VPlan.cpp:769
void addSCEVExpansion(const SCEV *S, VPValue *V)
Definition: VPlan.h:3280
VPValue * getOrAddLiveIn(Value *V)
Gets the live-in VPValue for V or adds a new live-in (if none exists yet) for V.
Definition: VPlan.h:3214
LLVM_DUMP_METHOD void dump() const
Dump the plan to stderr (for debugging).
Definition: VPlan.cpp:990
void execute(VPTransformState *State)
Generate the IR code for this VPlan.
Definition: VPlan.cpp:825
void print(raw_ostream &O) const
Print this VPlan to O.
Definition: VPlan.cpp:934
VPValue * getSCEVExpansion(const SCEV *S) const
Definition: VPlan.h:3276
void printLiveIns(raw_ostream &O) const
Print the live-ins of this VPlan to O.
Definition: VPlan.cpp:904
VPlan * duplicate()
Clone the current VPlan, update all VPValues of the new VPlan and cloned recipes to refer to the clon...
Definition: VPlan.cpp:1074
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
static VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
Definition: Type.cpp:676
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:171
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
Definition: TypeSize.h:168
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.
Definition: raw_ostream.h:52
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:660
#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...
Definition: CallingConv.h:76
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
std::string EscapeString(const std::string &Label)
Definition: GraphWriter.cpp:55
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
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.
@ SS
Definition: X86.h:207
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)
Get or create a VPValue that corresponds to the expansion of Expr.
Definition: VPlan.cpp:1459
bool isUniformAfterVectorization(VPValue *VPV)
Returns true if VPV is uniform after vectorization.
Definition: VPlan.h:3608
bool onlyFirstPartUsed(const VPValue *Def)
Returns true if only the first part of Def is used.
Definition: VPlan.cpp:1454
bool onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used.
Definition: VPlan.cpp:1449
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:853
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1722
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)
Definition: STLExtras.h:2165
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...
Definition: STLExtras.h:656
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.
Definition: VPlanCFG.h:214
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)
Definition: STLExtras.h:419
cl::opt< bool > EnableVPlanNativePath("enable-vplan-native-path", cl::Hidden, cl::desc("Enable VPlan-native vectorization path with " "support for outer loop vectorization."))
Definition: VPlan.cpp:53
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:134
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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...
Definition: SmallVector.h:1312
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)
Definition: APFixedPoint.h:293
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.
Definition: Alignment.h:39
VPIteration represents a single point in the iteration space of the output (vectorized and/or unrolle...
Definition: VPlan.h:219
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:359
BasicBlock * PrevBB
The previous IR BasicBlock created or used.
Definition: VPlan.h:365
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:373
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:361
BasicBlock * ExitBB
The last IR BasicBlock in the output IR.
Definition: VPlan.h:369
BasicBlock * getPreheaderBBFor(VPRecipeBase *R)
Returns the BasicBlock* mapped to the pre-header of the loop region containing R.
Definition: VPlan.cpp:348
DenseMap< VPValue *, ScalarsPerPartValuesTy > PerPartScalars
Definition: VPlan.h:259
DenseMap< VPValue *, PerPartValuesTy > PerPartOutput
Definition: VPlan.h:256
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:236
Value * get(VPValue *Def, unsigned Part, bool IsScalar=false)
Get the generated vector Value for a given VPValue Def and a given Part if IsScalar is false,...
Definition: VPlan.cpp:247
LoopInfo * LI
Hold a pointer to LoopInfo to register new basic blocks in the loop.
Definition: VPlan.h:383
VPTransformState(ElementCount VF, unsigned UF, LoopInfo *LI, DominatorTree *DT, IRBuilderBase &Builder, InnerLoopVectorizer *ILV, VPlan *Plan, LLVMContext &Ctx)
Definition: VPlan.cpp:217
struct llvm::VPTransformState::DataState Data
void addMetadata(Value *To, Instruction *From)
Add metadata from one instruction to another.
Definition: VPlan.cpp:361
struct llvm::VPTransformState::CFGState CFG
LoopVersioning * LVer
LoopVersioning.
Definition: VPlan.h:405
void addNewMetadata(Instruction *To, const Instruction *Orig)
Add additional metadata to To that was not present on Orig.
Definition: VPlan.cpp:353
void packScalarIntoVectorValue(VPValue *Def, const VPIteration &Instance)
Construct the vector value of a scalarized value V one lane at a time.
Definition: VPlan.cpp:393
void set(VPValue *Def, Value *V, unsigned Part, bool IsScalar=false)
Set the generated vector Value for a given VPValue and a given Part, if IsScalar is false.
Definition: VPlan.h:288
std::optional< VPIteration > Instance
Hold the indices to generate specific scalar instructions.
Definition: VPlan.h:248
IRBuilderBase & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Definition: VPlan.h:389
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:386
bool hasScalarValue(VPValue *Def, VPIteration Instance)
Definition: VPlan.h:276
VPlan * Plan
Pointer to the VPlan code is generated for.
Definition: VPlan.h:395
bool hasVectorValue(VPValue *Def, unsigned Part)
Definition: VPlan.h:270
ElementCount VF
The chosen Vectorization and Unroll Factors of the loop being vectorized.
Definition: VPlan.h:242
Loop * CurrentVectorLoop
The loop object for the current parent region, or nullptr.
Definition: VPlan.h:398
void setDebugLocFrom(DebugLoc DL)
Set the debug location in the builder using the debug location DL.
Definition: VPlan.cpp:372
void print(raw_ostream &O) const
Definition: VPlan.cpp:1249