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() ||
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
367 addNewMetadata(To, From);
368}
369
371 // No source instruction to transfer metadata from?
372 if (!From)
373 return;
374
375 for (Value *V : To) {
376 if (Instruction *I = dyn_cast<Instruction>(V))
378 }
379}
380
382 const DILocation *DIL = DL;
383 // When a FSDiscriminator is enabled, we don't need to add the multiply
384 // factors to the discriminators.
385 if (DIL &&
387 ->getParent()
390 // FIXME: For scalable vectors, assume vscale=1.
391 auto NewDIL =
393 if (NewDIL)
395 else
396 LLVM_DEBUG(dbgs() << "Failed to create new discriminator: "
397 << DIL->getFilename() << " Line: " << DIL->getLine());
398 } else
400}
401
403 const VPIteration &Instance) {
404 Value *ScalarInst = get(Def, Instance);
405 Value *VectorValue = get(Def, Instance.Part);
406 VectorValue = Builder.CreateInsertElement(
407 VectorValue, ScalarInst, Instance.Lane.getAsRuntimeExpr(Builder, VF));
408 set(Def, VectorValue, Instance.Part);
409}
410
412VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
413 // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
414 // Pred stands for Predessor. Prev stands for Previous - last visited/created.
415 BasicBlock *PrevBB = CFG.PrevBB;
416 BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
417 PrevBB->getParent(), CFG.ExitBB);
418 LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
419
420 // Hook up the new basic block to its predecessors.
421 for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
422 VPBasicBlock *PredVPBB = PredVPBlock->getExitingBasicBlock();
423 auto &PredVPSuccessors = PredVPBB->getHierarchicalSuccessors();
424 BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
425
426 assert(PredBB && "Predecessor basic-block not found building successor.");
427 auto *PredBBTerminator = PredBB->getTerminator();
428 LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
429
430 auto *TermBr = dyn_cast<BranchInst>(PredBBTerminator);
431 if (isa<UnreachableInst>(PredBBTerminator)) {
432 assert(PredVPSuccessors.size() == 1 &&
433 "Predecessor ending w/o branch must have single successor.");
434 DebugLoc DL = PredBBTerminator->getDebugLoc();
435 PredBBTerminator->eraseFromParent();
436 auto *Br = BranchInst::Create(NewBB, PredBB);
437 Br->setDebugLoc(DL);
438 } else if (TermBr && !TermBr->isConditional()) {
439 TermBr->setSuccessor(0, NewBB);
440 } else {
441 // Set each forward successor here when it is created, excluding
442 // backedges. A backward successor is set when the branch is created.
443 unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
444 assert(!TermBr->getSuccessor(idx) &&
445 "Trying to reset an existing successor block.");
446 TermBr->setSuccessor(idx, NewBB);
447 }
448 }
449 return NewBB;
450}
451
453 bool Replica = State->Instance && !State->Instance->isFirstIteration();
454 VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
455 VPBlockBase *SingleHPred = nullptr;
456 BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
457
458 auto IsLoopRegion = [](VPBlockBase *BB) {
459 auto *R = dyn_cast<VPRegionBlock>(BB);
460 return R && !R->isReplicator();
461 };
462
463 // 1. Create an IR basic block, or reuse the last one or ExitBB if possible.
464 if (getPlan()->getVectorLoopRegion()->getSingleSuccessor() == this) {
465 // ExitBB can be re-used for the exit block of the Plan.
466 NewBB = State->CFG.ExitBB;
467 State->CFG.PrevBB = NewBB;
468 State->Builder.SetInsertPoint(NewBB->getFirstNonPHI());
469
470 // Update the branch instruction in the predecessor to branch to ExitBB.
471 VPBlockBase *PredVPB = getSingleHierarchicalPredecessor();
472 VPBasicBlock *ExitingVPBB = PredVPB->getExitingBasicBlock();
473 assert(PredVPB->getSingleSuccessor() == this &&
474 "predecessor must have the current block as only successor");
475 BasicBlock *ExitingBB = State->CFG.VPBB2IRBB[ExitingVPBB];
476 // The Exit block of a loop is always set to be successor 0 of the Exiting
477 // block.
478 cast<BranchInst>(ExitingBB->getTerminator())->setSuccessor(0, NewBB);
479 } else if (PrevVPBB && /* A */
480 !((SingleHPred = getSingleHierarchicalPredecessor()) &&
481 SingleHPred->getExitingBasicBlock() == PrevVPBB &&
482 PrevVPBB->getSingleHierarchicalSuccessor() &&
483 (SingleHPred->getParent() == getEnclosingLoopRegion() &&
484 !IsLoopRegion(SingleHPred))) && /* B */
485 !(Replica && getPredecessors().empty())) { /* C */
486 // The last IR basic block is reused, as an optimization, in three cases:
487 // A. the first VPBB reuses the loop pre-header BB - when PrevVPBB is null;
488 // B. when the current VPBB has a single (hierarchical) predecessor which
489 // is PrevVPBB and the latter has a single (hierarchical) successor which
490 // both are in the same non-replicator region; and
491 // C. when the current VPBB is an entry of a region replica - where PrevVPBB
492 // is the exiting VPBB of this region from a previous instance, or the
493 // predecessor of this region.
494
495 NewBB = createEmptyBasicBlock(State->CFG);
496 State->Builder.SetInsertPoint(NewBB);
497 // Temporarily terminate with unreachable until CFG is rewired.
498 UnreachableInst *Terminator = State->Builder.CreateUnreachable();
499 // Register NewBB in its loop. In innermost loops its the same for all
500 // BB's.
501 if (State->CurrentVectorLoop)
502 State->CurrentVectorLoop->addBasicBlockToLoop(NewBB, *State->LI);
503 State->Builder.SetInsertPoint(Terminator);
504 State->CFG.PrevBB = NewBB;
505 }
506
507 // 2. Fill the IR basic block with IR instructions.
508 LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
509 << " in BB:" << NewBB->getName() << '\n');
510
511 State->CFG.VPBB2IRBB[this] = NewBB;
512 State->CFG.PrevVPBB = this;
513
514 for (VPRecipeBase &Recipe : Recipes)
515 Recipe.execute(*State);
516
517 LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
518}
519
521 for (VPRecipeBase &R : Recipes) {
522 for (auto *Def : R.definedValues())
523 Def->replaceAllUsesWith(NewValue);
524
525 for (unsigned I = 0, E = R.getNumOperands(); I != E; I++)
526 R.setOperand(I, NewValue);
527 }
528}
529
531 assert((SplitAt == end() || SplitAt->getParent() == this) &&
532 "can only split at a position in the same block");
533
535 // First, disconnect the current block from its successors.
536 for (VPBlockBase *Succ : Succs)
538
539 // Create new empty block after the block to split.
540 auto *SplitBlock = new VPBasicBlock(getName() + ".split");
542
543 // Add successors for block to split to new block.
544 for (VPBlockBase *Succ : Succs)
546
547 // Finally, move the recipes starting at SplitAt to new block.
548 for (VPRecipeBase &ToMove :
549 make_early_inc_range(make_range(SplitAt, this->end())))
550 ToMove.moveBefore(*SplitBlock, SplitBlock->end());
551
552 return SplitBlock;
553}
554
557 if (P && P->isReplicator()) {
558 P = P->getParent();
559 assert(!cast<VPRegionBlock>(P)->isReplicator() &&
560 "unexpected nested replicate regions");
561 }
562 return P;
563}
564
565static bool hasConditionalTerminator(const VPBasicBlock *VPBB) {
566 if (VPBB->empty()) {
567 assert(
568 VPBB->getNumSuccessors() < 2 &&
569 "block with multiple successors doesn't have a recipe as terminator");
570 return false;
571 }
572
573 const VPRecipeBase *R = &VPBB->back();
574 bool IsCondBranch = isa<VPBranchOnMaskRecipe>(R) ||
577 (void)IsCondBranch;
578
579 if (VPBB->getNumSuccessors() >= 2 ||
580 (VPBB->isExiting() && !VPBB->getParent()->isReplicator())) {
581 assert(IsCondBranch && "block with multiple successors not terminated by "
582 "conditional branch recipe");
583
584 return true;
585 }
586
587 assert(
588 !IsCondBranch &&
589 "block with 0 or 1 successors terminated by conditional branch recipe");
590 return false;
591}
592
594 if (hasConditionalTerminator(this))
595 return &back();
596 return nullptr;
597}
598
600 if (hasConditionalTerminator(this))
601 return &back();
602 return nullptr;
603}
604
606 return getParent() && getParent()->getExitingBasicBlock() == this;
607}
608
609#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
610void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const {
611 if (getSuccessors().empty()) {
612 O << Indent << "No successors\n";
613 } else {
614 O << Indent << "Successor(s): ";
615 ListSeparator LS;
616 for (auto *Succ : getSuccessors())
617 O << LS << Succ->getName();
618 O << '\n';
619 }
620}
621
622void VPBasicBlock::print(raw_ostream &O, const Twine &Indent,
623 VPSlotTracker &SlotTracker) const {
624 O << Indent << getName() << ":\n";
625
626 auto RecipeIndent = Indent + " ";
627 for (const VPRecipeBase &Recipe : *this) {
628 Recipe.print(O, RecipeIndent, SlotTracker);
629 O << '\n';
630 }
631
632 printSuccessors(O, Indent);
633}
634#endif
635
636static std::pair<VPBlockBase *, VPBlockBase *> cloneSESE(VPBlockBase *Entry);
637
638// Clone the CFG for all nodes in the single-entry-single-exit region reachable
639// from \p Entry, this includes cloning the blocks and their recipes. Operands
640// of cloned recipes will NOT be updated. Remapping of operands must be done
641// separately. Returns a pair with the the new entry and exiting blocks of the
642// cloned region.
643static std::pair<VPBlockBase *, VPBlockBase *> cloneSESE(VPBlockBase *Entry) {
646 Entry);
647 for (VPBlockBase *BB : RPOT) {
648 VPBlockBase *NewBB = BB->clone();
649 for (VPBlockBase *Pred : BB->getPredecessors())
650 VPBlockUtils::connectBlocks(Old2NewVPBlocks[Pred], NewBB);
651
652 Old2NewVPBlocks[BB] = NewBB;
653 }
654
655#if !defined(NDEBUG)
656 // Verify that the order of predecessors and successors matches in the cloned
657 // version.
659 NewRPOT(Old2NewVPBlocks[Entry]);
660 for (const auto &[OldBB, NewBB] : zip(RPOT, NewRPOT)) {
661 for (const auto &[OldPred, NewPred] :
662 zip(OldBB->getPredecessors(), NewBB->getPredecessors()))
663 assert(NewPred == Old2NewVPBlocks[OldPred] && "Different predecessors");
664
665 for (const auto &[OldSucc, NewSucc] :
666 zip(OldBB->successors(), NewBB->successors()))
667 assert(NewSucc == Old2NewVPBlocks[OldSucc] && "Different successors");
668 }
669#endif
670
671 return std::make_pair(Old2NewVPBlocks[Entry],
672 Old2NewVPBlocks[*reverse(RPOT).begin()]);
673}
674
676 const auto &[NewEntry, NewExiting] = cloneSESE(getEntry());
677 auto *NewRegion =
678 new VPRegionBlock(NewEntry, NewExiting, getName(), isReplicator());
679 for (VPBlockBase *Block : vp_depth_first_shallow(NewEntry))
680 Block->setParent(NewRegion);
681 return NewRegion;
682}
683
686 // Drop all references in VPBasicBlocks and replace all uses with
687 // DummyValue.
688 Block->dropAllReferences(NewValue);
689}
690
693 RPOT(Entry);
694
695 if (!isReplicator()) {
696 // Create and register the new vector loop.
697 Loop *PrevLoop = State->CurrentVectorLoop;
698 State->CurrentVectorLoop = State->LI->AllocateLoop();
699 BasicBlock *VectorPH = State->CFG.VPBB2IRBB[getPreheaderVPBB()];
700 Loop *ParentLoop = State->LI->getLoopFor(VectorPH);
701
702 // Insert the new loop into the loop nest and register the new basic blocks
703 // before calling any utilities such as SCEV that require valid LoopInfo.
704 if (ParentLoop)
705 ParentLoop->addChildLoop(State->CurrentVectorLoop);
706 else
707 State->LI->addTopLevelLoop(State->CurrentVectorLoop);
708
709 // Visit the VPBlocks connected to "this", starting from it.
710 for (VPBlockBase *Block : RPOT) {
711 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
712 Block->execute(State);
713 }
714
715 State->CurrentVectorLoop = PrevLoop;
716 return;
717 }
718
719 assert(!State->Instance && "Replicating a Region with non-null instance.");
720
721 // Enter replicating mode.
722 State->Instance = VPIteration(0, 0);
723
724 for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
725 State->Instance->Part = Part;
726 assert(!State->VF.isScalable() && "VF is assumed to be non scalable.");
727 for (unsigned Lane = 0, VF = State->VF.getKnownMinValue(); Lane < VF;
728 ++Lane) {
729 State->Instance->Lane = VPLane(Lane, VPLane::Kind::First);
730 // Visit the VPBlocks connected to \p this, starting from it.
731 for (VPBlockBase *Block : RPOT) {
732 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
733 Block->execute(State);
734 }
735 }
736 }
737
738 // Exit replicating mode.
739 State->Instance.reset();
740}
741
742#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
744 VPSlotTracker &SlotTracker) const {
745 O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {";
746 auto NewIndent = Indent + " ";
747 for (auto *BlockBase : vp_depth_first_shallow(Entry)) {
748 O << '\n';
749 BlockBase->print(O, NewIndent, SlotTracker);
750 }
751 O << Indent << "}\n";
752
753 printSuccessors(O, Indent);
754}
755#endif
756
758 for (auto &KV : LiveOuts)
759 delete KV.second;
760 LiveOuts.clear();
761
762 if (Entry) {
763 VPValue DummyValue;
765 Block->dropAllReferences(&DummyValue);
766
768
769 Preheader->dropAllReferences(&DummyValue);
770 delete Preheader;
771 }
772 for (VPValue *VPV : VPLiveInsToFree)
773 delete VPV;
774 if (BackedgeTakenCount)
775 delete BackedgeTakenCount;
776}
777
779 VPBasicBlock *Preheader = new VPBasicBlock("ph");
780 VPBasicBlock *VecPreheader = new VPBasicBlock("vector.ph");
781 auto Plan = std::make_unique<VPlan>(Preheader, VecPreheader);
782 Plan->TripCount =
784 // Create empty VPRegionBlock, to be filled during processing later.
785 auto *TopRegion = new VPRegionBlock("vector loop", false /*isReplicator*/);
786 VPBlockUtils::insertBlockAfter(TopRegion, VecPreheader);
787 VPBasicBlock *MiddleVPBB = new VPBasicBlock("middle.block");
788 VPBlockUtils::insertBlockAfter(MiddleVPBB, TopRegion);
789 return Plan;
790}
791
792void VPlan::prepareToExecute(Value *TripCountV, Value *VectorTripCountV,
793 Value *CanonicalIVStartValue,
794 VPTransformState &State) {
795 // Check if the backedge taken count is needed, and if so build it.
796 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
798 auto *TCMO = Builder.CreateSub(TripCountV,
799 ConstantInt::get(TripCountV->getType(), 1),
800 "trip.count.minus.1");
801 BackedgeTakenCount->setUnderlyingValue(TCMO);
802 }
803
804 VectorTripCount.setUnderlyingValue(VectorTripCountV);
805
807 // FIXME: Model VF * UF computation completely in VPlan.
808 VFxUF.setUnderlyingValue(
809 createStepForVF(Builder, TripCountV->getType(), State.VF, State.UF));
810
811 // When vectorizing the epilogue loop, the canonical induction start value
812 // needs to be changed from zero to the value after the main vector loop.
813 // FIXME: Improve modeling for canonical IV start values in the epilogue loop.
814 if (CanonicalIVStartValue) {
815 VPValue *VPV = getVPValueOrAddLiveIn(CanonicalIVStartValue);
816 auto *IV = getCanonicalIV();
817 assert(all_of(IV->users(),
818 [](const VPUser *U) {
819 return isa<VPScalarIVStepsRecipe>(U) ||
820 isa<VPScalarCastRecipe>(U) ||
821 isa<VPDerivedIVRecipe>(U) ||
822 cast<VPInstruction>(U)->getOpcode() ==
823 Instruction::Add;
824 }) &&
825 "the canonical IV should only be used by its increment or "
826 "ScalarIVSteps when resetting the start value");
827 IV->setOperand(0, VPV);
828 }
829}
830
831/// Generate the code inside the preheader and body of the vectorized loop.
832/// Assumes a single pre-header basic-block was created for this. Introduce
833/// additional basic-blocks as needed, and fill them all.
835 // Initialize CFG state.
836 State->CFG.PrevVPBB = nullptr;
837 State->CFG.ExitBB = State->CFG.PrevBB->getSingleSuccessor();
838 BasicBlock *VectorPreHeader = State->CFG.PrevBB;
839 State->Builder.SetInsertPoint(VectorPreHeader->getTerminator());
840
841 // Generate code in the loop pre-header and body.
843 Block->execute(State);
844
845 VPBasicBlock *LatchVPBB = getVectorLoopRegion()->getExitingBasicBlock();
846 BasicBlock *VectorLatchBB = State->CFG.VPBB2IRBB[LatchVPBB];
847
848 // Fix the latch value of canonical, reduction and first-order recurrences
849 // phis in the vector loop.
850 VPBasicBlock *Header = getVectorLoopRegion()->getEntryBasicBlock();
851 for (VPRecipeBase &R : Header->phis()) {
852 // Skip phi-like recipes that generate their backedege values themselves.
853 if (isa<VPWidenPHIRecipe>(&R))
854 continue;
855
856 if (isa<VPWidenPointerInductionRecipe>(&R) ||
857 isa<VPWidenIntOrFpInductionRecipe>(&R)) {
858 PHINode *Phi = nullptr;
859 if (isa<VPWidenIntOrFpInductionRecipe>(&R)) {
860 Phi = cast<PHINode>(State->get(R.getVPSingleValue(), 0));
861 } else {
862 auto *WidenPhi = cast<VPWidenPointerInductionRecipe>(&R);
863 // TODO: Split off the case that all users of a pointer phi are scalar
864 // from the VPWidenPointerInductionRecipe.
865 if (WidenPhi->onlyScalarsGenerated(State->VF.isScalable()))
866 continue;
867
868 auto *GEP = cast<GetElementPtrInst>(State->get(WidenPhi, 0));
869 Phi = cast<PHINode>(GEP->getPointerOperand());
870 }
871
872 Phi->setIncomingBlock(1, VectorLatchBB);
873
874 // Move the last step to the end of the latch block. This ensures
875 // consistent placement of all induction updates.
876 Instruction *Inc = cast<Instruction>(Phi->getIncomingValue(1));
877 Inc->moveBefore(VectorLatchBB->getTerminator()->getPrevNode());
878 continue;
879 }
880
881 auto *PhiR = cast<VPHeaderPHIRecipe>(&R);
882 // For canonical IV, first-order recurrences and in-order reduction phis,
883 // only a single part is generated, which provides the last part from the
884 // previous iteration. For non-ordered reductions all UF parts are
885 // generated.
886 bool SinglePartNeeded = isa<VPCanonicalIVPHIRecipe>(PhiR) ||
887 isa<VPFirstOrderRecurrencePHIRecipe>(PhiR) ||
888 (isa<VPReductionPHIRecipe>(PhiR) &&
889 cast<VPReductionPHIRecipe>(PhiR)->isOrdered());
890 bool NeedsScalar = isa<VPCanonicalIVPHIRecipe>(PhiR) ||
891 (isa<VPReductionPHIRecipe>(PhiR) &&
892 cast<VPReductionPHIRecipe>(PhiR)->isInLoop());
893 unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->UF;
894
895 for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
896 Value *Phi = State->get(PhiR, Part, NeedsScalar);
897 Value *Val =
898 State->get(PhiR->getBackedgeValue(),
899 SinglePartNeeded ? State->UF - 1 : Part, NeedsScalar);
900 cast<PHINode>(Phi)->addIncoming(Val, VectorLatchBB);
901 }
902 }
903
904 // We do not attempt to preserve DT for outer loop vectorization currently.
906 BasicBlock *VectorHeaderBB = State->CFG.VPBB2IRBB[Header];
907 State->DT->addNewBlock(VectorHeaderBB, VectorPreHeader);
908 updateDominatorTree(State->DT, VectorHeaderBB, VectorLatchBB,
909 State->CFG.ExitBB);
910 }
911}
912
913#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
916
917 if (VFxUF.getNumUsers() > 0) {
918 O << "\nLive-in ";
919 VFxUF.printAsOperand(O, SlotTracker);
920 O << " = VF * UF";
921 }
922
923 if (VectorTripCount.getNumUsers() > 0) {
924 O << "\nLive-in ";
925 VectorTripCount.printAsOperand(O, SlotTracker);
926 O << " = vector-trip-count";
927 }
928
929 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
930 O << "\nLive-in ";
931 BackedgeTakenCount->printAsOperand(O, SlotTracker);
932 O << " = backedge-taken count";
933 }
934
935 O << "\n";
936 if (TripCount->isLiveIn())
937 O << "Live-in ";
938 TripCount->printAsOperand(O, SlotTracker);
939 O << " = original trip-count";
940 O << "\n";
941}
942
944void VPlan::print(raw_ostream &O) const {
946
947 O << "VPlan '" << getName() << "' {";
948
949 printLiveIns(O);
950
951 if (!getPreheader()->empty()) {
952 O << "\n";
953 getPreheader()->print(O, "", SlotTracker);
954 }
955
956 for (const VPBlockBase *Block : vp_depth_first_shallow(getEntry())) {
957 O << '\n';
958 Block->print(O, "", SlotTracker);
959 }
960
961 if (!LiveOuts.empty())
962 O << "\n";
963 for (const auto &KV : LiveOuts) {
964 KV.second->print(O, SlotTracker);
965 }
966
967 O << "}\n";
968}
969
970std::string VPlan::getName() const {
971 std::string Out;
972 raw_string_ostream RSO(Out);
973 RSO << Name << " for ";
974 if (!VFs.empty()) {
975 RSO << "VF={" << VFs[0];
976 for (ElementCount VF : drop_begin(VFs))
977 RSO << "," << VF;
978 RSO << "},";
979 }
980
981 if (UFs.empty()) {
982 RSO << "UF>=1";
983 } else {
984 RSO << "UF={" << UFs[0];
985 for (unsigned UF : drop_begin(UFs))
986 RSO << "," << UF;
987 RSO << "}";
988 }
989
990 return Out;
991}
992
995 VPlanPrinter Printer(O, *this);
996 Printer.dump();
997}
998
1000void VPlan::dump() const { print(dbgs()); }
1001#endif
1002
1004 assert(LiveOuts.count(PN) == 0 && "an exit value for PN already exists");
1005 LiveOuts.insert({PN, new VPLiveOut(PN, V)});
1006}
1007
1008void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopHeaderBB,
1009 BasicBlock *LoopLatchBB,
1010 BasicBlock *LoopExitBB) {
1011 // The vector body may be more than a single basic-block by this point.
1012 // Update the dominator tree information inside the vector body by propagating
1013 // it from header to latch, expecting only triangular control-flow, if any.
1014 BasicBlock *PostDomSucc = nullptr;
1015 for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
1016 // Get the list of successors of this block.
1017 std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
1018 assert(Succs.size() <= 2 &&
1019 "Basic block in vector loop has more than 2 successors.");
1020 PostDomSucc = Succs[0];
1021 if (Succs.size() == 1) {
1022 assert(PostDomSucc->getSinglePredecessor() &&
1023 "PostDom successor has more than one predecessor.");
1024 DT->addNewBlock(PostDomSucc, BB);
1025 continue;
1026 }
1027 BasicBlock *InterimSucc = Succs[1];
1028 if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
1029 PostDomSucc = Succs[1];
1030 InterimSucc = Succs[0];
1031 }
1032 assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
1033 "One successor of a basic block does not lead to the other.");
1034 assert(InterimSucc->getSinglePredecessor() &&
1035 "Interim successor has more than one predecessor.");
1036 assert(PostDomSucc->hasNPredecessors(2) &&
1037 "PostDom successor has more than two predecessors.");
1038 DT->addNewBlock(InterimSucc, BB);
1039 DT->addNewBlock(PostDomSucc, BB);
1040 }
1041 // Latch block is a new dominator for the loop exit.
1042 DT->changeImmediateDominator(LoopExitBB, LoopLatchBB);
1043 assert(DT->verify(DominatorTree::VerificationLevel::Fast));
1044}
1045
1046static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry,
1047 DenseMap<VPValue *, VPValue *> &Old2NewVPValues) {
1048 // Update the operands of all cloned recipes starting at NewEntry. This
1049 // traverses all reachable blocks. This is done in two steps, to handle cycles
1050 // in PHI recipes.
1052 OldDeepRPOT(Entry);
1054 NewDeepRPOT(NewEntry);
1055 // First, collect all mappings from old to new VPValues defined by cloned
1056 // recipes.
1057 for (const auto &[OldBB, NewBB] :
1058 zip(VPBlockUtils::blocksOnly<VPBasicBlock>(OldDeepRPOT),
1059 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT))) {
1060 assert(OldBB->getRecipeList().size() == NewBB->getRecipeList().size() &&
1061 "blocks must have the same number of recipes");
1062 for (const auto &[OldR, NewR] : zip(*OldBB, *NewBB)) {
1063 assert(OldR.getNumOperands() == NewR.getNumOperands() &&
1064 "recipes must have the same number of operands");
1065 assert(OldR.getNumDefinedValues() == NewR.getNumDefinedValues() &&
1066 "recipes must define the same number of operands");
1067 for (const auto &[OldV, NewV] :
1068 zip(OldR.definedValues(), NewR.definedValues()))
1069 Old2NewVPValues[OldV] = NewV;
1070 }
1071 }
1072
1073 // Update all operands to use cloned VPValues.
1074 for (VPBasicBlock *NewBB :
1075 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT)) {
1076 for (VPRecipeBase &NewR : *NewBB)
1077 for (unsigned I = 0, E = NewR.getNumOperands(); I != E; ++I) {
1078 VPValue *NewOp = Old2NewVPValues.lookup(NewR.getOperand(I));
1079 NewR.setOperand(I, NewOp);
1080 }
1081 }
1082}
1083
1085 // Clone blocks.
1086 VPBasicBlock *NewPreheader = Preheader->clone();
1087 const auto &[NewEntry, __] = cloneSESE(Entry);
1088
1089 // Create VPlan, clone live-ins and remap operands in the cloned blocks.
1090 auto *NewPlan = new VPlan(NewPreheader, cast<VPBasicBlock>(NewEntry));
1091 DenseMap<VPValue *, VPValue *> Old2NewVPValues;
1092 for (VPValue *OldLiveIn : VPLiveInsToFree) {
1093 Old2NewVPValues[OldLiveIn] =
1094 NewPlan->getVPValueOrAddLiveIn(OldLiveIn->getLiveInIRValue());
1095 }
1096 Old2NewVPValues[&VectorTripCount] = &NewPlan->VectorTripCount;
1097 Old2NewVPValues[&VFxUF] = &NewPlan->VFxUF;
1098 if (BackedgeTakenCount) {
1099 NewPlan->BackedgeTakenCount = new VPValue();
1100 Old2NewVPValues[BackedgeTakenCount] = NewPlan->BackedgeTakenCount;
1101 }
1102 assert(TripCount && "trip count must be set");
1103 if (TripCount->isLiveIn())
1104 Old2NewVPValues[TripCount] =
1105 NewPlan->getVPValueOrAddLiveIn(TripCount->getLiveInIRValue());
1106 // else NewTripCount will be created and inserted into Old2NewVPValues when
1107 // TripCount is cloned. In any case NewPlan->TripCount is updated below.
1108
1109 remapOperands(Preheader, NewPreheader, Old2NewVPValues);
1110 remapOperands(Entry, NewEntry, Old2NewVPValues);
1111
1112 // Clone live-outs.
1113 for (const auto &[_, LO] : LiveOuts)
1114 NewPlan->addLiveOut(LO->getPhi(), Old2NewVPValues[LO->getOperand(0)]);
1115
1116 // Initialize remaining fields of cloned VPlan.
1117 NewPlan->VFs = VFs;
1118 NewPlan->UFs = UFs;
1119 // TODO: Adjust names.
1120 NewPlan->Name = Name;
1121 assert(Old2NewVPValues.contains(TripCount) &&
1122 "TripCount must have been added to Old2NewVPValues");
1123 NewPlan->TripCount = Old2NewVPValues[TripCount];
1124 return NewPlan;
1125}
1126
1127#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1128
1129Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
1130 return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
1131 Twine(getOrCreateBID(Block));
1132}
1133
1134Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
1135 const std::string &Name = Block->getName();
1136 if (!Name.empty())
1137 return Name;
1138 return "VPB" + Twine(getOrCreateBID(Block));
1139}
1140
1142 Depth = 1;
1143 bumpIndent(0);
1144 OS << "digraph VPlan {\n";
1145 OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
1146 if (!Plan.getName().empty())
1147 OS << "\\n" << DOT::EscapeString(Plan.getName());
1148
1149 {
1150 // Print live-ins.
1151 std::string Str;
1152 raw_string_ostream SS(Str);
1153 Plan.printLiveIns(SS);
1155 StringRef(Str).rtrim('\n').split(Lines, "\n");
1156 for (auto Line : Lines)
1157 OS << DOT::EscapeString(Line.str()) << "\\n";
1158 }
1159
1160 OS << "\"]\n";
1161 OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
1162 OS << "edge [fontname=Courier, fontsize=30]\n";
1163 OS << "compound=true\n";
1164
1165 dumpBlock(Plan.getPreheader());
1166
1168 dumpBlock(Block);
1169
1170 OS << "}\n";
1171}
1172
1173void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
1174 if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
1175 dumpBasicBlock(BasicBlock);
1176 else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1177 dumpRegion(Region);
1178 else
1179 llvm_unreachable("Unsupported kind of VPBlock.");
1180}
1181
1182void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
1183 bool Hidden, const Twine &Label) {
1184 // Due to "dot" we print an edge between two regions as an edge between the
1185 // exiting basic block and the entry basic of the respective regions.
1186 const VPBlockBase *Tail = From->getExitingBasicBlock();
1187 const VPBlockBase *Head = To->getEntryBasicBlock();
1188 OS << Indent << getUID(Tail) << " -> " << getUID(Head);
1189 OS << " [ label=\"" << Label << '\"';
1190 if (Tail != From)
1191 OS << " ltail=" << getUID(From);
1192 if (Head != To)
1193 OS << " lhead=" << getUID(To);
1194 if (Hidden)
1195 OS << "; splines=none";
1196 OS << "]\n";
1197}
1198
1199void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
1200 auto &Successors = Block->getSuccessors();
1201 if (Successors.size() == 1)
1202 drawEdge(Block, Successors.front(), false, "");
1203 else if (Successors.size() == 2) {
1204 drawEdge(Block, Successors.front(), false, "T");
1205 drawEdge(Block, Successors.back(), false, "F");
1206 } else {
1207 unsigned SuccessorNumber = 0;
1208 for (auto *Successor : Successors)
1209 drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
1210 }
1211}
1212
1213void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
1214 // Implement dot-formatted dump by performing plain-text dump into the
1215 // temporary storage followed by some post-processing.
1216 OS << Indent << getUID(BasicBlock) << " [label =\n";
1217 bumpIndent(1);
1218 std::string Str;
1220 // Use no indentation as we need to wrap the lines into quotes ourselves.
1221 BasicBlock->print(SS, "", SlotTracker);
1222
1223 // We need to process each line of the output separately, so split
1224 // single-string plain-text dump.
1226 StringRef(Str).rtrim('\n').split(Lines, "\n");
1227
1228 auto EmitLine = [&](StringRef Line, StringRef Suffix) {
1229 OS << Indent << '"' << DOT::EscapeString(Line.str()) << "\\l\"" << Suffix;
1230 };
1231
1232 // Don't need the "+" after the last line.
1233 for (auto Line : make_range(Lines.begin(), Lines.end() - 1))
1234 EmitLine(Line, " +\n");
1235 EmitLine(Lines.back(), "\n");
1236
1237 bumpIndent(-1);
1238 OS << Indent << "]\n";
1239
1241}
1242
1243void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
1244 OS << Indent << "subgraph " << getUID(Region) << " {\n";
1245 bumpIndent(1);
1246 OS << Indent << "fontname=Courier\n"
1247 << Indent << "label=\""
1248 << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
1249 << DOT::EscapeString(Region->getName()) << "\"\n";
1250 // Dump the blocks of the region.
1251 assert(Region->getEntry() && "Region contains no inner blocks.");
1253 dumpBlock(Block);
1254 bumpIndent(-1);
1255 OS << Indent << "}\n";
1257}
1258
1260 if (auto *Inst = dyn_cast<Instruction>(V)) {
1261 if (!Inst->getType()->isVoidTy()) {
1262 Inst->printAsOperand(O, false);
1263 O << " = ";
1264 }
1265 O << Inst->getOpcodeName() << " ";
1266 unsigned E = Inst->getNumOperands();
1267 if (E > 0) {
1268 Inst->getOperand(0)->printAsOperand(O, false);
1269 for (unsigned I = 1; I < E; ++I)
1270 Inst->getOperand(I)->printAsOperand(O << ", ", false);
1271 }
1272 } else // !Inst
1273 V->printAsOperand(O, false);
1274}
1275
1276#endif
1277
1278template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
1279
1281 replaceUsesWithIf(New, [](VPUser &, unsigned) { return true; });
1282}
1283
1285 VPValue *New,
1286 llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace) {
1287 // Note that this early exit is required for correctness; the implementation
1288 // below relies on the number of users for this VPValue to decrease, which
1289 // isn't the case if this == New.
1290 if (this == New)
1291 return;
1292
1293 for (unsigned J = 0; J < getNumUsers();) {
1294 VPUser *User = Users[J];
1295 bool RemovedUser = false;
1296 for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
1297 if (User->getOperand(I) != this || !ShouldReplace(*User, I))
1298 continue;
1299
1300 RemovedUser = true;
1301 User->setOperand(I, New);
1302 }
1303 // If a user got removed after updating the current user, the next user to
1304 // update will be moved to the current position, so we only need to
1305 // increment the index if the number of users did not change.
1306 if (!RemovedUser)
1307 J++;
1308 }
1309}
1310
1311#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1313 if (const Value *UV = getUnderlyingValue()) {
1314 OS << "ir<";
1315 UV->printAsOperand(OS, false);
1316 OS << ">";
1317 return;
1318 }
1319
1320 unsigned Slot = Tracker.getSlot(this);
1321 if (Slot == unsigned(-1))
1322 OS << "<badref>";
1323 else
1324 OS << "vp<%" << Tracker.getSlot(this) << ">";
1325}
1326
1328 interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) {
1329 Op->printAsOperand(O, SlotTracker);
1330 });
1331}
1332#endif
1333
1334void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
1335 Old2NewTy &Old2New,
1336 InterleavedAccessInfo &IAI) {
1338 RPOT(Region->getEntry());
1339 for (VPBlockBase *Base : RPOT) {
1340 visitBlock(Base, Old2New, IAI);
1341 }
1342}
1343
1344void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
1345 InterleavedAccessInfo &IAI) {
1346 if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
1347 for (VPRecipeBase &VPI : *VPBB) {
1348 if (isa<VPWidenPHIRecipe>(&VPI))
1349 continue;
1350 assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
1351 auto *VPInst = cast<VPInstruction>(&VPI);
1352
1353 auto *Inst = dyn_cast_or_null<Instruction>(VPInst->getUnderlyingValue());
1354 if (!Inst)
1355 continue;
1356 auto *IG = IAI.getInterleaveGroup(Inst);
1357 if (!IG)
1358 continue;
1359
1360 auto NewIGIter = Old2New.find(IG);
1361 if (NewIGIter == Old2New.end())
1362 Old2New[IG] = new InterleaveGroup<VPInstruction>(
1363 IG->getFactor(), IG->isReverse(), IG->getAlign());
1364
1365 if (Inst == IG->getInsertPos())
1366 Old2New[IG]->setInsertPos(VPInst);
1367
1368 InterleaveGroupMap[VPInst] = Old2New[IG];
1369 InterleaveGroupMap[VPInst]->insertMember(
1370 VPInst, IG->getIndex(Inst),
1371 Align(IG->isReverse() ? (-1) * int(IG->getFactor())
1372 : IG->getFactor()));
1373 }
1374 } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1375 visitRegion(Region, Old2New, IAI);
1376 else
1377 llvm_unreachable("Unsupported kind of VPBlock.");
1378}
1379
1381 InterleavedAccessInfo &IAI) {
1382 Old2NewTy Old2New;
1383 visitRegion(Plan.getVectorLoopRegion(), Old2New, IAI);
1384}
1385
1386void VPSlotTracker::assignSlot(const VPValue *V) {
1387 assert(!Slots.contains(V) && "VPValue already has a slot!");
1388 Slots[V] = NextSlot++;
1389}
1390
1391void VPSlotTracker::assignSlots(const VPlan &Plan) {
1392 if (Plan.VFxUF.getNumUsers() > 0)
1393 assignSlot(&Plan.VFxUF);
1394 assignSlot(&Plan.VectorTripCount);
1395 if (Plan.BackedgeTakenCount)
1396 assignSlot(Plan.BackedgeTakenCount);
1397 assignSlots(Plan.getPreheader());
1398
1401 for (const VPBasicBlock *VPBB :
1402 VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
1403 assignSlots(VPBB);
1404}
1405
1406void VPSlotTracker::assignSlots(const VPBasicBlock *VPBB) {
1407 for (const VPRecipeBase &Recipe : *VPBB)
1408 for (VPValue *Def : Recipe.definedValues())
1409 assignSlot(Def);
1410}
1411
1413 return all_of(Def->users(),
1414 [Def](const VPUser *U) { return U->onlyFirstLaneUsed(Def); });
1415}
1416
1418 return all_of(Def->users(),
1419 [Def](const VPUser *U) { return U->onlyFirstPartUsed(Def); });
1420}
1421
1423 ScalarEvolution &SE) {
1424 if (auto *Expanded = Plan.getSCEVExpansion(Expr))
1425 return Expanded;
1426 VPValue *Expanded = nullptr;
1427 if (auto *E = dyn_cast<SCEVConstant>(Expr))
1428 Expanded = Plan.getVPValueOrAddLiveIn(E->getValue());
1429 else if (auto *E = dyn_cast<SCEVUnknown>(Expr))
1430 Expanded = Plan.getVPValueOrAddLiveIn(E->getValue());
1431 else {
1432 Expanded = new VPExpandSCEVRecipe(Expr, SE);
1434 }
1435 Plan.addSCEVExpansion(Expr, Expanded);
1436 return Expanded;
1437}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
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:643
static bool hasConditionalTerminator(const VPBasicBlock *VPBB)
Definition: VPlan.cpp:565
static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry, DenseMap< VPValue *, VPValue * > &Old2NewVPValues)
Definition: VPlan.cpp:1046
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
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator end()
Definition: BasicBlock.h:442
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:4800
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:347
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:198
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
Definition: BasicBlock.cpp:461
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:439
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:469
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:205
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:164
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:155
size_t size() const
Definition: BasicBlock.h:450
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:220
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:307
bool shouldEmitDebugInfoForProfiling() const
Returns true if we should emit debug info for profiling.
Definition: Metadata.cpp:1832
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:2455
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2443
UnreachableInst * CreateUnreachable()
Definition: IRBuilder.h:1257
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Definition: IRBuilder.cpp:1214
IntegerType * getInt32Ty()
Fetch the type representing a 32-bit integer.
Definition: IRBuilder.h:520
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:271
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:480
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1338
void restoreIP(InsertPoint IP)
Sets the current insert point to a previously-saved location.
Definition: IRBuilder.h:283
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:2649
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:444
Drive the analysis of interleaved memory accesses in the loop.
Definition: VectorUtils.h:586
InterleaveGroup< Instruction > * getInterleaveGroup(const Instruction *Instr) const
Get the interleave group that Instr belongs to.
Definition: VectorUtils.h:631
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:5233
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:690
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:696
StringRef rtrim(char Char) const
Return string with consecutive Char characters starting from the right removed.
Definition: StringRef.h:799
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:2594
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
Definition: VPlan.h:2662
VPBasicBlock * clone() override
Clone the current block and it's recipes, without updating the operands of the cloned recipes.
Definition: VPlan.h:2706
RecipeListTy::iterator iterator
Instruction iterators...
Definition: VPlan.h:2615
void execute(VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPBasicBlock,...
Definition: VPlan.cpp:452
iterator end()
Definition: VPlan.h:2625
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:2623
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
Definition: VPlan.cpp:210
VPRegionBlock * getEnclosingLoopRegion()
Definition: VPlan.cpp:555
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:520
VPBasicBlock * splitAt(iterator SplitAt)
Split current block at SplitAt by inserting a new block between the current block and its successors ...
Definition: VPlan.cpp:530
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:622
bool isExiting() const
Returns true if the block is exiting it's parent region.
Definition: VPlan.cpp:605
VPRecipeBase * getTerminator()
If the block has multiple successors, return the branch recipe terminating the block.
Definition: VPlan.cpp:593
const VPRecipeBase & back() const
Definition: VPlan.h:2637
bool empty() const
Definition: VPlan.h:2634
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:421
VPRegionBlock * getParent()
Definition: VPlan.h:493
const VPBasicBlock * getExitingBasicBlock() const
Definition: VPlan.cpp:175
size_t getNumSuccessors() const
Definition: VPlan.h:538
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:610
VPBlockBase * getEnclosingBlockWithPredecessors()
Definition: VPlan.cpp:197
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:523
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:564
VPBlockBase * getSinglePredecessor() const
Definition: VPlan.h:534
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:558
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:528
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:3178
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:3225
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:3214
This class augments a recipe with a set of VPValues defined by the recipe.
Definition: VPlanValue.h:314
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:2333
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:1139
VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI)
Definition: VPlan.cpp:1380
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:673
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:713
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:2727
VPRegionBlock * clone() override
Clone all blocks in the single-entry single-exit region of the block and their recipes without updati...
Definition: VPlan.cpp:675
const VPBlockBase * getEntry() const
Definition: VPlan.h:2766
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:2798
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:684
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:743
void execute(VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPRegionBlock,...
Definition: VPlan.cpp:691
const VPBlockBase * getExiting() const
Definition: VPlan.h:2778
VPBasicBlock * getPreheaderVPBB()
Returns the pre-header VPBasicBlock of the loop region.
Definition: VPlan.h:2791
This class can be used to assign consecutive numbers to all VPValues in a VPlan and allows querying t...
Definition: VPlanValue.h:448
unsigned getSlot(const VPValue *V) const
Definition: VPlanValue.h:462
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:204
void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const
Print the operands to O.
Definition: VPlan.cpp:1327
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:1312
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:1280
unsigned getNumUsers() const
Definition: VPlanValue.h:113
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:1284
VPDef * Def
Pointer to the VPDef that defines this VPValue.
Definition: VPlanValue.h:65
VPlanPrinter prints a given VPlan to a given output stream.
Definition: VPlan.h:3098
LLVM_DUMP_METHOD void dump()
Definition: VPlan.cpp:1141
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2828
void printDOT(raw_ostream &O) const
Print this VPlan in DOT format to O.
Definition: VPlan.cpp:994
std::string getName() const
Return a string with the name of the plan and the applicable VFs and UFs.
Definition: VPlan.cpp:970
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:792
VPBasicBlock * getEntry()
Definition: VPlan.h:2925
void addLiveOut(PHINode *PN, VPValue *V)
Definition: VPlan.cpp:1003
VPBasicBlock * getPreheader()
Definition: VPlan.h:3080
VPValue * getVPValueOrAddLiveIn(Value *V)
Gets the VPValue for V or adds a new live-in (if none exists yet) for V.
Definition: VPlan.h:3006
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:3042
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:778
void addSCEVExpansion(const SCEV *S, VPValue *V)
Definition: VPlan.h:3074
LLVM_DUMP_METHOD void dump() const
Dump the plan to stderr (for debugging).
Definition: VPlan.cpp:1000
void execute(VPTransformState *State)
Generate the IR code for this VPlan.
Definition: VPlan.cpp:834
void print(raw_ostream &O) const
Print this VPlan to O.
Definition: VPlan.cpp:944
VPValue * getSCEVExpansion(const SCEV *S) const
Definition: VPlan.h:3070
void printLiveIns(raw_ostream &O) const
Print the live-ins of this VPlan to O.
Definition: VPlan.cpp:914
VPlan * duplicate()
Clone the current VPlan, update all VPValues of the new VPlan and cloned recipes to refer to the clon...
Definition: VPlan.cpp:1084
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
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:1422
bool isUniformAfterVectorization(VPValue *VPV)
Returns true if VPV is uniform after vectorization.
Definition: VPlan.h:3402
bool onlyFirstPartUsed(const VPValue *Def)
Returns true if only the first part of Def is used.
Definition: VPlan.cpp:1417
bool onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used.
Definition: VPlan.cpp:1412
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:862
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
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:1731
auto successors(const MachineBasicBlock *BB)
Value * getRuntimeVF(IRBuilderBase &B, Type *Ty, ElementCount VF)
Return the runtime value for VF.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
Definition: STLExtras.h:2174
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:665
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:428
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
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:363
BasicBlock * PrevBB
The previous IR BasicBlock created or used.
Definition: VPlan.h:369
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:377
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:365
BasicBlock * ExitBB
The last IR BasicBlock in the output IR.
Definition: VPlan.h:373
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:387
VPTransformState(ElementCount VF, unsigned UF, LoopInfo *LI, DominatorTree *DT, IRBuilderBase &Builder, InnerLoopVectorizer *ILV, VPlan *Plan, LLVMContext &Ctx)
Definition: VPlan.cpp:217
void addMetadata(Instruction *To, Instruction *From)
Add metadata from one instruction to another.
Definition: VPlan.cpp:361
struct llvm::VPTransformState::DataState Data
struct llvm::VPTransformState::CFGState CFG
LoopVersioning * LVer
LoopVersioning.
Definition: VPlan.h:409
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:402
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:393
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:390
bool hasScalarValue(VPValue *Def, VPIteration Instance)
Definition: VPlan.h:276
VPlan * Plan
Pointer to the VPlan code is generated for.
Definition: VPlan.h:399
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:402
void setDebugLocFrom(DebugLoc DL)
Set the debug location in the builder using the debug location DL.
Definition: VPlan.cpp:381
void print(raw_ostream &O) const
Definition: VPlan.cpp:1259