LLVM 20.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"
21#include "VPlanCFG.h"
22#include "VPlanDominatorTree.h"
23#include "VPlanPatternMatch.h"
24#include "VPlanTransforms.h"
26#include "llvm/ADT/STLExtras.h"
29#include "llvm/ADT/Twine.h"
32#include "llvm/IR/BasicBlock.h"
33#include "llvm/IR/CFG.h"
34#include "llvm/IR/IRBuilder.h"
35#include "llvm/IR/Instruction.h"
37#include "llvm/IR/Type.h"
38#include "llvm/IR/Value.h"
41#include "llvm/Support/Debug.h"
48#include <cassert>
49#include <string>
50#include <vector>
51
52using namespace llvm;
53using namespace llvm::VPlanPatternMatch;
54
55namespace llvm {
57}
58
60 "vplan-print-in-dot-format", cl::Hidden,
61 cl::desc("Use dot format instead of plain text when dumping VPlans"));
62
63#define DEBUG_TYPE "vplan"
64
65#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
67 const VPInstruction *Instr = dyn_cast<VPInstruction>(&V);
69 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
70 V.print(OS, SlotTracker);
71 return OS;
72}
73#endif
74
76 const ElementCount &VF) const {
77 switch (LaneKind) {
79 // Lane = RuntimeVF - VF.getKnownMinValue() + Lane
80 return Builder.CreateSub(getRuntimeVF(Builder, Builder.getInt32Ty(), VF),
81 Builder.getInt32(VF.getKnownMinValue() - Lane));
83 return Builder.getInt32(Lane);
84 }
85 llvm_unreachable("Unknown lane kind");
86}
87
88VPValue::VPValue(const unsigned char SC, Value *UV, VPDef *Def)
89 : SubclassID(SC), UnderlyingVal(UV), Def(Def) {
90 if (Def)
91 Def->addDefinedValue(this);
92}
93
95 assert(Users.empty() && "trying to delete a VPValue with remaining users");
96 if (Def)
97 Def->removeDefinedValue(this);
98}
99
100#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
102 if (const VPRecipeBase *R = dyn_cast_or_null<VPRecipeBase>(Def))
103 R->print(OS, "", SlotTracker);
104 else
106}
107
108void VPValue::dump() const {
109 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this->Def);
111 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
113 dbgs() << "\n";
114}
115
116void VPDef::dump() const {
117 const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this);
119 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
120 print(dbgs(), "", SlotTracker);
121 dbgs() << "\n";
122}
123#endif
124
126 return cast_or_null<VPRecipeBase>(Def);
127}
128
130 return cast_or_null<VPRecipeBase>(Def);
131}
132
133// Get the top-most entry block of \p Start. This is the entry block of the
134// containing VPlan. This function is templated to support both const and non-const blocks
135template <typename T> static T *getPlanEntry(T *Start) {
136 T *Next = Start;
137 T *Current = Start;
138 while ((Next = Next->getParent()))
139 Current = Next;
140
141 SmallSetVector<T *, 8> WorkList;
142 WorkList.insert(Current);
143
144 for (unsigned i = 0; i < WorkList.size(); i++) {
145 T *Current = WorkList[i];
146 if (Current->getNumPredecessors() == 0)
147 return Current;
148 auto &Predecessors = Current->getPredecessors();
149 WorkList.insert(Predecessors.begin(), Predecessors.end());
150 }
151
152 llvm_unreachable("VPlan without any entry node without predecessors");
153}
154
155VPlan *VPBlockBase::getPlan() { return getPlanEntry(this)->Plan; }
156
157const VPlan *VPBlockBase::getPlan() const { return getPlanEntry(this)->Plan; }
158
159/// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
161 const VPBlockBase *Block = this;
162 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
163 Block = Region->getEntry();
164 return cast<VPBasicBlock>(Block);
165}
166
168 VPBlockBase *Block = this;
169 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
170 Block = Region->getEntry();
171 return cast<VPBasicBlock>(Block);
172}
173
174void VPBlockBase::setPlan(VPlan *ParentPlan) {
175 assert(
176 (ParentPlan->getEntry() == this || ParentPlan->getPreheader() == this) &&
177 "Can only set plan on its entry or preheader block.");
178 Plan = ParentPlan;
179}
180
181/// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
183 const VPBlockBase *Block = this;
184 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
185 Block = Region->getExiting();
186 return cast<VPBasicBlock>(Block);
187}
188
190 VPBlockBase *Block = this;
191 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
192 Block = Region->getExiting();
193 return cast<VPBasicBlock>(Block);
194}
195
197 if (!Successors.empty() || !Parent)
198 return this;
199 assert(Parent->getExiting() == this &&
200 "Block w/o successors not the exiting block of its parent.");
201 return Parent->getEnclosingBlockWithSuccessors();
202}
203
205 if (!Predecessors.empty() || !Parent)
206 return this;
207 assert(Parent->getEntry() == this &&
208 "Block w/o predecessors not the entry of its parent.");
209 return Parent->getEnclosingBlockWithPredecessors();
210}
211
214 delete Block;
215}
216
218 iterator It = begin();
219 while (It != end() && It->isPhi())
220 It++;
221 return It;
222}
223
225 DominatorTree *DT, IRBuilderBase &Builder,
226 InnerLoopVectorizer *ILV, VPlan *Plan,
227 LLVMContext &Ctx)
228 : VF(VF), UF(UF), CFG(DT), LI(LI), Builder(Builder), ILV(ILV), Plan(Plan),
229 LVer(nullptr),
230 TypeAnalysis(Plan->getCanonicalIV()->getScalarType(), Ctx) {}
231
233 if (Def->isLiveIn())
234 return Def->getLiveInIRValue();
235
236 if (hasScalarValue(Def, Instance)) {
237 return Data
238 .PerPartScalars[Def][Instance.Part][Instance.Lane.mapToCacheIndex(VF)];
239 }
240 if (!Instance.Lane.isFirstLane() &&
243 return Data.PerPartScalars[Def][Instance.Part][0];
244 }
245
246 assert(hasVectorValue(Def, Instance.Part));
247 auto *VecPart = Data.PerPartOutput[Def][Instance.Part];
248 if (!VecPart->getType()->isVectorTy()) {
249 assert(Instance.Lane.isFirstLane() && "cannot get lane > 0 for scalar");
250 return VecPart;
251 }
252 // TODO: Cache created scalar values.
253 Value *Lane = Instance.Lane.getAsRuntimeExpr(Builder, VF);
254 auto *Extract = Builder.CreateExtractElement(VecPart, Lane);
255 // set(Def, Extract, Instance);
256 return Extract;
257}
258
259Value *VPTransformState::get(VPValue *Def, unsigned Part, bool NeedsScalar) {
260 if (NeedsScalar) {
261 assert((VF.isScalar() || Def->isLiveIn() || hasVectorValue(Def, Part) ||
263 (hasScalarValue(Def, VPIteration(Part, 0)) &&
264 Data.PerPartScalars[Def][Part].size() == 1)) &&
265 "Trying to access a single scalar per part but has multiple scalars "
266 "per part.");
267 return get(Def, VPIteration(Part, 0));
268 }
269
270 // If Values have been set for this Def return the one relevant for \p Part.
271 if (hasVectorValue(Def, Part))
272 return Data.PerPartOutput[Def][Part];
273
274 auto GetBroadcastInstrs = [this, Def](Value *V) {
275 bool SafeToHoist = Def->isDefinedOutsideVectorRegions();
276 if (VF.isScalar())
277 return V;
278 // Place the code for broadcasting invariant variables in the new preheader.
280 if (SafeToHoist) {
281 BasicBlock *LoopVectorPreHeader = CFG.VPBB2IRBB[cast<VPBasicBlock>(
283 if (LoopVectorPreHeader)
284 Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
285 }
286
287 // Place the code for broadcasting invariant variables in the new preheader.
288 // Broadcast the scalar into all locations in the vector.
289 Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast");
290
291 return Shuf;
292 };
293
294 if (!hasScalarValue(Def, {Part, 0})) {
295 assert(Def->isLiveIn() && "expected a live-in");
296 if (Part != 0)
297 return get(Def, 0);
298 Value *IRV = Def->getLiveInIRValue();
299 Value *B = GetBroadcastInstrs(IRV);
300 set(Def, B, Part);
301 return B;
302 }
303
304 Value *ScalarValue = get(Def, {Part, 0});
305 // If we aren't vectorizing, we can just copy the scalar map values over
306 // to the vector map.
307 if (VF.isScalar()) {
308 set(Def, ScalarValue, Part);
309 return ScalarValue;
310 }
311
312 bool IsUniform = vputils::isUniformAfterVectorization(Def);
313
314 unsigned LastLane = IsUniform ? 0 : VF.getKnownMinValue() - 1;
315 // Check if there is a scalar value for the selected lane.
316 if (!hasScalarValue(Def, {Part, LastLane})) {
317 // At the moment, VPWidenIntOrFpInductionRecipes, VPScalarIVStepsRecipes and
318 // VPExpandSCEVRecipes can also be uniform.
319 assert((isa<VPWidenIntOrFpInductionRecipe>(Def->getDefiningRecipe()) ||
320 isa<VPScalarIVStepsRecipe>(Def->getDefiningRecipe()) ||
321 isa<VPExpandSCEVRecipe>(Def->getDefiningRecipe())) &&
322 "unexpected recipe found to be invariant");
323 IsUniform = true;
324 LastLane = 0;
325 }
326
327 auto *LastInst = cast<Instruction>(get(Def, {Part, LastLane}));
328 // Set the insert point after the last scalarized instruction or after the
329 // last PHI, if LastInst is a PHI. This ensures the insertelement sequence
330 // will directly follow the scalar definitions.
331 auto OldIP = Builder.saveIP();
332 auto NewIP =
333 isa<PHINode>(LastInst)
334 ? BasicBlock::iterator(LastInst->getParent()->getFirstNonPHI())
335 : std::next(BasicBlock::iterator(LastInst));
336 Builder.SetInsertPoint(&*NewIP);
337
338 // However, if we are vectorizing, we need to construct the vector values.
339 // If the value is known to be uniform after vectorization, we can just
340 // broadcast the scalar value corresponding to lane zero for each unroll
341 // iteration. Otherwise, we construct the vector values using
342 // insertelement instructions. Since the resulting vectors are stored in
343 // State, we will only generate the insertelements once.
344 Value *VectorValue = nullptr;
345 if (IsUniform) {
346 VectorValue = GetBroadcastInstrs(ScalarValue);
347 set(Def, VectorValue, Part);
348 } else {
349 // Initialize packing with insertelements to start from undef.
350 assert(!VF.isScalable() && "VF is assumed to be non scalable.");
351 Value *Undef = PoisonValue::get(VectorType::get(LastInst->getType(), VF));
352 set(Def, Undef, Part);
353 for (unsigned Lane = 0; Lane < VF.getKnownMinValue(); ++Lane)
354 packScalarIntoVectorValue(Def, {Part, Lane});
355 VectorValue = get(Def, Part);
356 }
357 Builder.restoreIP(OldIP);
358 return VectorValue;
359}
360
362 VPRegionBlock *LoopRegion = R->getParent()->getEnclosingLoopRegion();
363 return VPBB2IRBB[LoopRegion->getPreheaderVPBB()];
364}
365
367 const Instruction *Orig) {
368 // If the loop was versioned with memchecks, add the corresponding no-alias
369 // metadata.
370 if (LVer && (isa<LoadInst>(Orig) || isa<StoreInst>(Orig)))
371 LVer->annotateInstWithNoAlias(To, Orig);
372}
373
375 // No source instruction to transfer metadata from?
376 if (!From)
377 return;
378
379 if (Instruction *ToI = dyn_cast<Instruction>(To)) {
381 addNewMetadata(ToI, From);
382 }
383}
384
386 const DILocation *DIL = DL;
387 // When a FSDiscriminator is enabled, we don't need to add the multiply
388 // factors to the discriminators.
389 if (DIL &&
391 ->getParent()
394 // FIXME: For scalable vectors, assume vscale=1.
395 auto NewDIL =
397 if (NewDIL)
399 else
400 LLVM_DEBUG(dbgs() << "Failed to create new discriminator: "
401 << DIL->getFilename() << " Line: " << DIL->getLine());
402 } else
404}
405
407 const VPIteration &Instance) {
408 Value *ScalarInst = get(Def, Instance);
409 Value *VectorValue = get(Def, Instance.Part);
410 VectorValue = Builder.CreateInsertElement(
411 VectorValue, ScalarInst, Instance.Lane.getAsRuntimeExpr(Builder, VF));
412 set(Def, VectorValue, Instance.Part);
413}
414
416VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
417 // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
418 // Pred stands for Predessor. Prev stands for Previous - last visited/created.
419 BasicBlock *PrevBB = CFG.PrevBB;
420 BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
421 PrevBB->getParent(), CFG.ExitBB);
422 LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
423
424 // Hook up the new basic block to its predecessors.
425 for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
426 VPBasicBlock *PredVPBB = PredVPBlock->getExitingBasicBlock();
427 auto &PredVPSuccessors = PredVPBB->getHierarchicalSuccessors();
428 BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
429
430 assert(PredBB && "Predecessor basic-block not found building successor.");
431 auto *PredBBTerminator = PredBB->getTerminator();
432 LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
433
434 auto *TermBr = dyn_cast<BranchInst>(PredBBTerminator);
435 if (isa<UnreachableInst>(PredBBTerminator)) {
436 assert(PredVPSuccessors.size() == 1 &&
437 "Predecessor ending w/o branch must have single successor.");
438 DebugLoc DL = PredBBTerminator->getDebugLoc();
439 PredBBTerminator->eraseFromParent();
440 auto *Br = BranchInst::Create(NewBB, PredBB);
441 Br->setDebugLoc(DL);
442 } else if (TermBr && !TermBr->isConditional()) {
443 TermBr->setSuccessor(0, NewBB);
444 } else {
445 // Set each forward successor here when it is created, excluding
446 // backedges. A backward successor is set when the branch is created.
447 unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
448 assert(!TermBr->getSuccessor(idx) &&
449 "Trying to reset an existing successor block.");
450 TermBr->setSuccessor(idx, NewBB);
451 }
452 CFG.DTU.applyUpdates({{DominatorTree::Insert, PredBB, NewBB}});
453 }
454 return NewBB;
455}
456
458 assert(getHierarchicalSuccessors().size() <= 2 &&
459 "VPIRBasicBlock can have at most two successors at the moment!");
460 State->Builder.SetInsertPoint(getIRBasicBlock()->getTerminator());
461 executeRecipes(State, getIRBasicBlock());
462 if (getSingleSuccessor()) {
463 assert(isa<UnreachableInst>(getIRBasicBlock()->getTerminator()));
464 auto *Br = State->Builder.CreateBr(getIRBasicBlock());
465 Br->setOperand(0, nullptr);
466 getIRBasicBlock()->getTerminator()->eraseFromParent();
467 }
468
469 for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
470 VPBasicBlock *PredVPBB = PredVPBlock->getExitingBasicBlock();
471 BasicBlock *PredBB = State->CFG.VPBB2IRBB[PredVPBB];
472 assert(PredBB && "Predecessor basic-block not found building successor.");
473 LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
474
475 auto *PredBBTerminator = PredBB->getTerminator();
476 auto *TermBr = cast<BranchInst>(PredBBTerminator);
477 // Set each forward successor here when it is created, excluding
478 // backedges. A backward successor is set when the branch is created.
479 const auto &PredVPSuccessors = PredVPBB->getHierarchicalSuccessors();
480 unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
481 assert(!TermBr->getSuccessor(idx) &&
482 "Trying to reset an existing successor block.");
483 TermBr->setSuccessor(idx, IRBB);
484 State->CFG.DTU.applyUpdates({{DominatorTree::Insert, PredBB, IRBB}});
485 }
486}
487
489 bool Replica = State->Instance && !State->Instance->isFirstIteration();
490 VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
491 VPBlockBase *SingleHPred = nullptr;
492 BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
493
494 auto IsLoopRegion = [](VPBlockBase *BB) {
495 auto *R = dyn_cast<VPRegionBlock>(BB);
496 return R && !R->isReplicator();
497 };
498
499 // 1. Create an IR basic block.
500 if (PrevVPBB && /* A */
501 !((SingleHPred = getSingleHierarchicalPredecessor()) &&
502 SingleHPred->getExitingBasicBlock() == PrevVPBB &&
503 PrevVPBB->getSingleHierarchicalSuccessor() &&
504 (SingleHPred->getParent() == getEnclosingLoopRegion() &&
505 !IsLoopRegion(SingleHPred))) && /* B */
506 !(Replica && getPredecessors().empty())) { /* C */
507 // The last IR basic block is reused, as an optimization, in three cases:
508 // A. the first VPBB reuses the loop pre-header BB - when PrevVPBB is null;
509 // B. when the current VPBB has a single (hierarchical) predecessor which
510 // is PrevVPBB and the latter has a single (hierarchical) successor which
511 // both are in the same non-replicator region; and
512 // C. when the current VPBB is an entry of a region replica - where PrevVPBB
513 // is the exiting VPBB of this region from a previous instance, or the
514 // predecessor of this region.
515
516 NewBB = createEmptyBasicBlock(State->CFG);
517 State->Builder.SetInsertPoint(NewBB);
518 // Temporarily terminate with unreachable until CFG is rewired.
519 UnreachableInst *Terminator = State->Builder.CreateUnreachable();
520 // Register NewBB in its loop. In innermost loops its the same for all
521 // BB's.
522 if (State->CurrentVectorLoop)
523 State->CurrentVectorLoop->addBasicBlockToLoop(NewBB, *State->LI);
524 State->Builder.SetInsertPoint(Terminator);
525 State->CFG.PrevBB = NewBB;
526 }
527
528 // 2. Fill the IR basic block with IR instructions.
529 executeRecipes(State, NewBB);
530}
531
533 for (VPRecipeBase &R : Recipes) {
534 for (auto *Def : R.definedValues())
535 Def->replaceAllUsesWith(NewValue);
536
537 for (unsigned I = 0, E = R.getNumOperands(); I != E; I++)
538 R.setOperand(I, NewValue);
539 }
540}
541
543 LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
544 << " in BB:" << BB->getName() << '\n');
545
546 State->CFG.VPBB2IRBB[this] = BB;
547 State->CFG.PrevVPBB = this;
548
549 for (VPRecipeBase &Recipe : Recipes)
550 Recipe.execute(*State);
551
552 LLVM_DEBUG(dbgs() << "LV: filled BB:" << *BB);
553}
554
556 assert((SplitAt == end() || SplitAt->getParent() == this) &&
557 "can only split at a position in the same block");
558
560 // First, disconnect the current block from its successors.
561 for (VPBlockBase *Succ : Succs)
563
564 // Create new empty block after the block to split.
565 auto *SplitBlock = new VPBasicBlock(getName() + ".split");
567
568 // Add successors for block to split to new block.
569 for (VPBlockBase *Succ : Succs)
571
572 // Finally, move the recipes starting at SplitAt to new block.
573 for (VPRecipeBase &ToMove :
574 make_early_inc_range(make_range(SplitAt, this->end())))
575 ToMove.moveBefore(*SplitBlock, SplitBlock->end());
576
577 return SplitBlock;
578}
579
582 if (P && P->isReplicator()) {
583 P = P->getParent();
584 assert(!cast<VPRegionBlock>(P)->isReplicator() &&
585 "unexpected nested replicate regions");
586 }
587 return P;
588}
589
590static bool hasConditionalTerminator(const VPBasicBlock *VPBB) {
591 if (VPBB->empty()) {
592 assert(
593 VPBB->getNumSuccessors() < 2 &&
594 "block with multiple successors doesn't have a recipe as terminator");
595 return false;
596 }
597
598 const VPRecipeBase *R = &VPBB->back();
599 bool IsCondBranch = isa<VPBranchOnMaskRecipe>(R) ||
602 (void)IsCondBranch;
603
604 if (VPBB->getNumSuccessors() >= 2 ||
605 (VPBB->isExiting() && !VPBB->getParent()->isReplicator())) {
606 assert(IsCondBranch && "block with multiple successors not terminated by "
607 "conditional branch recipe");
608
609 return true;
610 }
611
612 assert(
613 !IsCondBranch &&
614 "block with 0 or 1 successors terminated by conditional branch recipe");
615 return false;
616}
617
619 if (hasConditionalTerminator(this))
620 return &back();
621 return nullptr;
622}
623
625 if (hasConditionalTerminator(this))
626 return &back();
627 return nullptr;
628}
629
631 return getParent() && getParent()->getExitingBasicBlock() == this;
632}
633
634#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
635void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const {
636 if (getSuccessors().empty()) {
637 O << Indent << "No successors\n";
638 } else {
639 O << Indent << "Successor(s): ";
640 ListSeparator LS;
641 for (auto *Succ : getSuccessors())
642 O << LS << Succ->getName();
643 O << '\n';
644 }
645}
646
647void VPBasicBlock::print(raw_ostream &O, const Twine &Indent,
648 VPSlotTracker &SlotTracker) const {
649 O << Indent << getName() << ":\n";
650
651 auto RecipeIndent = Indent + " ";
652 for (const VPRecipeBase &Recipe : *this) {
653 Recipe.print(O, RecipeIndent, SlotTracker);
654 O << '\n';
655 }
656
657 printSuccessors(O, Indent);
658}
659#endif
660
661static std::pair<VPBlockBase *, VPBlockBase *> cloneFrom(VPBlockBase *Entry);
662
663// Clone the CFG for all nodes reachable from \p Entry, this includes cloning
664// the blocks and their recipes. Operands of cloned recipes will NOT be updated.
665// Remapping of operands must be done separately. Returns a pair with the new
666// entry and exiting blocks of the cloned region. If \p Entry isn't part of a
667// region, return nullptr for the exiting block.
668static std::pair<VPBlockBase *, VPBlockBase *> cloneFrom(VPBlockBase *Entry) {
670 VPBlockBase *Exiting = nullptr;
671 bool InRegion = Entry->getParent();
672 // First, clone blocks reachable from Entry.
673 for (VPBlockBase *BB : vp_depth_first_shallow(Entry)) {
674 VPBlockBase *NewBB = BB->clone();
675 Old2NewVPBlocks[BB] = NewBB;
676 if (InRegion && BB->getNumSuccessors() == 0) {
677 assert(!Exiting && "Multiple exiting blocks?");
678 Exiting = BB;
679 }
680 }
681 assert((!InRegion || Exiting) && "regions must have a single exiting block");
682
683 // Second, update the predecessors & successors of the cloned blocks.
684 for (VPBlockBase *BB : vp_depth_first_shallow(Entry)) {
685 VPBlockBase *NewBB = Old2NewVPBlocks[BB];
687 for (VPBlockBase *Pred : BB->getPredecessors()) {
688 NewPreds.push_back(Old2NewVPBlocks[Pred]);
689 }
690 NewBB->setPredecessors(NewPreds);
692 for (VPBlockBase *Succ : BB->successors()) {
693 NewSuccs.push_back(Old2NewVPBlocks[Succ]);
694 }
695 NewBB->setSuccessors(NewSuccs);
696 }
697
698#if !defined(NDEBUG)
699 // Verify that the order of predecessors and successors matches in the cloned
700 // version.
701 for (const auto &[OldBB, NewBB] :
703 vp_depth_first_shallow(Old2NewVPBlocks[Entry]))) {
704 for (const auto &[OldPred, NewPred] :
705 zip(OldBB->getPredecessors(), NewBB->getPredecessors()))
706 assert(NewPred == Old2NewVPBlocks[OldPred] && "Different predecessors");
707
708 for (const auto &[OldSucc, NewSucc] :
709 zip(OldBB->successors(), NewBB->successors()))
710 assert(NewSucc == Old2NewVPBlocks[OldSucc] && "Different successors");
711 }
712#endif
713
714 return std::make_pair(Old2NewVPBlocks[Entry],
715 Exiting ? Old2NewVPBlocks[Exiting] : nullptr);
716}
717
719 const auto &[NewEntry, NewExiting] = cloneFrom(getEntry());
720 auto *NewRegion =
721 new VPRegionBlock(NewEntry, NewExiting, getName(), isReplicator());
722 for (VPBlockBase *Block : vp_depth_first_shallow(NewEntry))
723 Block->setParent(NewRegion);
724 return NewRegion;
725}
726
729 // Drop all references in VPBasicBlocks and replace all uses with
730 // DummyValue.
731 Block->dropAllReferences(NewValue);
732}
733
736 RPOT(Entry);
737
738 if (!isReplicator()) {
739 // Create and register the new vector loop.
740 Loop *PrevLoop = State->CurrentVectorLoop;
741 State->CurrentVectorLoop = State->LI->AllocateLoop();
742 BasicBlock *VectorPH = State->CFG.VPBB2IRBB[getPreheaderVPBB()];
743 Loop *ParentLoop = State->LI->getLoopFor(VectorPH);
744
745 // Insert the new loop into the loop nest and register the new basic blocks
746 // before calling any utilities such as SCEV that require valid LoopInfo.
747 if (ParentLoop)
748 ParentLoop->addChildLoop(State->CurrentVectorLoop);
749 else
750 State->LI->addTopLevelLoop(State->CurrentVectorLoop);
751
752 // Visit the VPBlocks connected to "this", starting from it.
753 for (VPBlockBase *Block : RPOT) {
754 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
755 Block->execute(State);
756 }
757
758 State->CurrentVectorLoop = PrevLoop;
759 return;
760 }
761
762 assert(!State->Instance && "Replicating a Region with non-null instance.");
763
764 // Enter replicating mode.
765 State->Instance = VPIteration(0, 0);
766
767 for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
768 State->Instance->Part = Part;
769 assert(!State->VF.isScalable() && "VF is assumed to be non scalable.");
770 for (unsigned Lane = 0, VF = State->VF.getKnownMinValue(); Lane < VF;
771 ++Lane) {
772 State->Instance->Lane = VPLane(Lane, VPLane::Kind::First);
773 // Visit the VPBlocks connected to \p this, starting from it.
774 for (VPBlockBase *Block : RPOT) {
775 LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
776 Block->execute(State);
777 }
778 }
779 }
780
781 // Exit replicating mode.
782 State->Instance.reset();
783}
784
787 for (VPRecipeBase &R : Recipes)
788 Cost += R.cost(VF, Ctx);
789 return Cost;
790}
791
793 if (!isReplicator()) {
795 for (VPBlockBase *Block : vp_depth_first_shallow(getEntry()))
796 Cost += Block->cost(VF, Ctx);
797 InstructionCost BackedgeCost =
798 Ctx.TTI.getCFInstrCost(Instruction::Br, TTI::TCK_RecipThroughput);
799 LLVM_DEBUG(dbgs() << "Cost of " << BackedgeCost << " for VF " << VF
800 << ": vector loop backedge\n");
801 Cost += BackedgeCost;
802 return Cost;
803 }
804
805 // Compute the cost of a replicate region. Replicating isn't supported for
806 // scalable vectors, return an invalid cost for them.
807 // TODO: Discard scalable VPlans with replicate recipes earlier after
808 // construction.
809 if (VF.isScalable())
811
812 // First compute the cost of the conditionally executed recipes, followed by
813 // account for the branching cost, except if the mask is a header mask or
814 // uniform condition.
815 using namespace llvm::VPlanPatternMatch;
816 VPBasicBlock *Then = cast<VPBasicBlock>(getEntry()->getSuccessors()[0]);
817 InstructionCost ThenCost = Then->cost(VF, Ctx);
818
819 // For the scalar case, we may not always execute the original predicated
820 // block, Thus, scale the block's cost by the probability of executing it.
821 if (VF.isScalar())
822 return ThenCost / getReciprocalPredBlockProb();
823
824 return ThenCost;
825}
826
827#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
829 VPSlotTracker &SlotTracker) const {
830 O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {";
831 auto NewIndent = Indent + " ";
832 for (auto *BlockBase : vp_depth_first_shallow(Entry)) {
833 O << '\n';
834 BlockBase->print(O, NewIndent, SlotTracker);
835 }
836 O << Indent << "}\n";
837
838 printSuccessors(O, Indent);
839}
840#endif
841
843 for (auto &KV : LiveOuts)
844 delete KV.second;
845 LiveOuts.clear();
846
847 if (Entry) {
848 VPValue DummyValue;
850 Block->dropAllReferences(&DummyValue);
851
853
854 Preheader->dropAllReferences(&DummyValue);
855 delete Preheader;
856 }
857 for (VPValue *VPV : VPLiveInsToFree)
858 delete VPV;
859 if (BackedgeTakenCount)
860 delete BackedgeTakenCount;
861}
862
864 bool RequiresScalarEpilogueCheck,
865 bool TailFolded, Loop *TheLoop) {
866 VPIRBasicBlock *Entry = new VPIRBasicBlock(TheLoop->getLoopPreheader());
867 VPBasicBlock *VecPreheader = new VPBasicBlock("vector.ph");
868 auto Plan = std::make_unique<VPlan>(Entry, VecPreheader);
869 Plan->TripCount =
871 // Create VPRegionBlock, with empty header and latch blocks, to be filled
872 // during processing later.
873 VPBasicBlock *HeaderVPBB = new VPBasicBlock("vector.body");
874 VPBasicBlock *LatchVPBB = new VPBasicBlock("vector.latch");
875 VPBlockUtils::insertBlockAfter(LatchVPBB, HeaderVPBB);
876 auto *TopRegion = new VPRegionBlock(HeaderVPBB, LatchVPBB, "vector loop",
877 false /*isReplicator*/);
878
879 VPBlockUtils::insertBlockAfter(TopRegion, VecPreheader);
880 VPBasicBlock *MiddleVPBB = new VPBasicBlock("middle.block");
881 VPBlockUtils::insertBlockAfter(MiddleVPBB, TopRegion);
882
883 VPBasicBlock *ScalarPH = new VPBasicBlock("scalar.ph");
884 if (!RequiresScalarEpilogueCheck) {
885 VPBlockUtils::connectBlocks(MiddleVPBB, ScalarPH);
886 return Plan;
887 }
888
889 // If needed, add a check in the middle block to see if we have completed
890 // all of the iterations in the first vector loop. Three cases:
891 // 1) If (N - N%VF) == N, then we *don't* need to run the remainder.
892 // Thus if tail is to be folded, we know we don't need to run the
893 // remainder and we can set the condition to true.
894 // 2) If we require a scalar epilogue, there is no conditional branch as
895 // we unconditionally branch to the scalar preheader. Do nothing.
896 // 3) Otherwise, construct a runtime check.
897 BasicBlock *IRExitBlock = TheLoop->getUniqueExitBlock();
898 auto *VPExitBlock = new VPIRBasicBlock(IRExitBlock);
899 // The connection order corresponds to the operands of the conditional branch.
900 VPBlockUtils::insertBlockAfter(VPExitBlock, MiddleVPBB);
901 VPBlockUtils::connectBlocks(MiddleVPBB, ScalarPH);
902
903 auto *ScalarLatchTerm = TheLoop->getLoopLatch()->getTerminator();
904 // Here we use the same DebugLoc as the scalar loop latch terminator instead
905 // of the corresponding compare because they may have ended up with
906 // different line numbers and we want to avoid awkward line stepping while
907 // debugging. Eg. if the compare has got a line number inside the loop.
908 VPBuilder Builder(MiddleVPBB);
909 VPValue *Cmp =
910 TailFolded
912 IntegerType::getInt1Ty(TripCount->getType()->getContext())))
913 : Builder.createICmp(CmpInst::ICMP_EQ, Plan->getTripCount(),
915 ScalarLatchTerm->getDebugLoc(), "cmp.n");
916 Builder.createNaryOp(VPInstruction::BranchOnCond, {Cmp},
917 ScalarLatchTerm->getDebugLoc());
918 return Plan;
919}
920
921void VPlan::prepareToExecute(Value *TripCountV, Value *VectorTripCountV,
922 Value *CanonicalIVStartValue,
923 VPTransformState &State) {
924 // Check if the backedge taken count is needed, and if so build it.
925 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
927 auto *TCMO = Builder.CreateSub(TripCountV,
928 ConstantInt::get(TripCountV->getType(), 1),
929 "trip.count.minus.1");
930 BackedgeTakenCount->setUnderlyingValue(TCMO);
931 }
932
933 VectorTripCount.setUnderlyingValue(VectorTripCountV);
934
936 // FIXME: Model VF * UF computation completely in VPlan.
937 VFxUF.setUnderlyingValue(
938 createStepForVF(Builder, TripCountV->getType(), State.VF, State.UF));
939
940 // When vectorizing the epilogue loop, the canonical induction start value
941 // needs to be changed from zero to the value after the main vector loop.
942 // FIXME: Improve modeling for canonical IV start values in the epilogue loop.
943 if (CanonicalIVStartValue) {
944 VPValue *VPV = getOrAddLiveIn(CanonicalIVStartValue);
945 auto *IV = getCanonicalIV();
946 assert(all_of(IV->users(),
947 [](const VPUser *U) {
948 return isa<VPScalarIVStepsRecipe>(U) ||
949 isa<VPScalarCastRecipe>(U) ||
950 isa<VPDerivedIVRecipe>(U) ||
951 cast<VPInstruction>(U)->getOpcode() ==
952 Instruction::Add;
953 }) &&
954 "the canonical IV should only be used by its increment or "
955 "ScalarIVSteps when resetting the start value");
956 IV->setOperand(0, VPV);
957 }
958}
959
960/// Replace \p VPBB with a VPIRBasicBlock wrapping \p IRBB. All recipes from \p
961/// VPBB are moved to the newly created VPIRBasicBlock. VPBB must have a single
962/// predecessor, which is rewired to the new VPIRBasicBlock. All successors of
963/// VPBB, if any, are rewired to the new VPIRBasicBlock.
965 VPIRBasicBlock *IRMiddleVPBB = new VPIRBasicBlock(IRBB);
966 for (auto &R : make_early_inc_range(*VPBB))
967 R.moveBefore(*IRMiddleVPBB, IRMiddleVPBB->end());
968 VPBlockBase *PredVPBB = VPBB->getSinglePredecessor();
969 VPBlockUtils::disconnectBlocks(PredVPBB, VPBB);
970 VPBlockUtils::connectBlocks(PredVPBB, IRMiddleVPBB);
971 for (auto *Succ : to_vector(VPBB->getSuccessors())) {
972 VPBlockUtils::connectBlocks(IRMiddleVPBB, Succ);
974 }
975 delete VPBB;
976}
977
978/// Generate the code inside the preheader and body of the vectorized loop.
979/// Assumes a single pre-header basic-block was created for this. Introduce
980/// additional basic-blocks as needed, and fill them all.
982 // Initialize CFG state.
983 State->CFG.PrevVPBB = nullptr;
984 State->CFG.ExitBB = State->CFG.PrevBB->getSingleSuccessor();
985 BasicBlock *VectorPreHeader = State->CFG.PrevBB;
986 State->Builder.SetInsertPoint(VectorPreHeader->getTerminator());
987
988 // Disconnect VectorPreHeader from ExitBB in both the CFG and DT.
989 cast<BranchInst>(VectorPreHeader->getTerminator())->setSuccessor(0, nullptr);
990 State->CFG.DTU.applyUpdates(
991 {{DominatorTree::Delete, VectorPreHeader, State->CFG.ExitBB}});
992
993 // Replace regular VPBB's for the middle and scalar preheader blocks with
994 // VPIRBasicBlocks wrapping their IR blocks. The IR blocks are created during
995 // skeleton creation, so we can only create the VPIRBasicBlocks now during
996 // VPlan execution rather than earlier during VPlan construction.
997 BasicBlock *MiddleBB = State->CFG.ExitBB;
998 VPBasicBlock *MiddleVPBB =
999 cast<VPBasicBlock>(getVectorLoopRegion()->getSingleSuccessor());
1000 // Find the VPBB for the scalar preheader, relying on the current structure
1001 // when creating the middle block and its successrs: if there's a single
1002 // predecessor, it must be the scalar preheader. Otherwise, the second
1003 // successor is the scalar preheader.
1004 BasicBlock *ScalarPh = MiddleBB->getSingleSuccessor();
1005 auto &MiddleSuccs = MiddleVPBB->getSuccessors();
1006 assert((MiddleSuccs.size() == 1 || MiddleSuccs.size() == 2) &&
1007 "middle block has unexpected successors");
1008 VPBasicBlock *ScalarPhVPBB = cast<VPBasicBlock>(
1009 MiddleSuccs.size() == 1 ? MiddleSuccs[0] : MiddleSuccs[1]);
1010 assert(!isa<VPIRBasicBlock>(ScalarPhVPBB) &&
1011 "scalar preheader cannot be wrapped already");
1012 replaceVPBBWithIRVPBB(ScalarPhVPBB, ScalarPh);
1013 replaceVPBBWithIRVPBB(MiddleVPBB, MiddleBB);
1014
1015 // Disconnect the middle block from its single successor (the scalar loop
1016 // header) in both the CFG and DT. The branch will be recreated during VPlan
1017 // execution.
1018 auto *BrInst = new UnreachableInst(MiddleBB->getContext());
1019 BrInst->insertBefore(MiddleBB->getTerminator());
1020 MiddleBB->getTerminator()->eraseFromParent();
1021 State->CFG.DTU.applyUpdates({{DominatorTree::Delete, MiddleBB, ScalarPh}});
1022
1023 // Generate code in the loop pre-header and body.
1025 Block->execute(State);
1026
1027 VPBasicBlock *LatchVPBB = getVectorLoopRegion()->getExitingBasicBlock();
1028 BasicBlock *VectorLatchBB = State->CFG.VPBB2IRBB[LatchVPBB];
1029
1030 // Fix the latch value of canonical, reduction and first-order recurrences
1031 // phis in the vector loop.
1032 VPBasicBlock *Header = getVectorLoopRegion()->getEntryBasicBlock();
1033 for (VPRecipeBase &R : Header->phis()) {
1034 // Skip phi-like recipes that generate their backedege values themselves.
1035 if (isa<VPWidenPHIRecipe>(&R))
1036 continue;
1037
1038 if (isa<VPWidenPointerInductionRecipe>(&R) ||
1039 isa<VPWidenIntOrFpInductionRecipe>(&R)) {
1040 PHINode *Phi = nullptr;
1041 if (isa<VPWidenIntOrFpInductionRecipe>(&R)) {
1042 Phi = cast<PHINode>(State->get(R.getVPSingleValue(), 0));
1043 } else {
1044 auto *WidenPhi = cast<VPWidenPointerInductionRecipe>(&R);
1045 assert(!WidenPhi->onlyScalarsGenerated(State->VF.isScalable()) &&
1046 "recipe generating only scalars should have been replaced");
1047 auto *GEP = cast<GetElementPtrInst>(State->get(WidenPhi, 0));
1048 Phi = cast<PHINode>(GEP->getPointerOperand());
1049 }
1050
1051 Phi->setIncomingBlock(1, VectorLatchBB);
1052
1053 // Move the last step to the end of the latch block. This ensures
1054 // consistent placement of all induction updates.
1055 Instruction *Inc = cast<Instruction>(Phi->getIncomingValue(1));
1056 Inc->moveBefore(VectorLatchBB->getTerminator()->getPrevNode());
1057 continue;
1058 }
1059
1060 auto *PhiR = cast<VPHeaderPHIRecipe>(&R);
1061 // For canonical IV, first-order recurrences and in-order reduction phis,
1062 // only a single part is generated, which provides the last part from the
1063 // previous iteration. For non-ordered reductions all UF parts are
1064 // generated.
1065 bool SinglePartNeeded =
1066 isa<VPCanonicalIVPHIRecipe>(PhiR) ||
1067 isa<VPFirstOrderRecurrencePHIRecipe, VPEVLBasedIVPHIRecipe>(PhiR) ||
1068 (isa<VPReductionPHIRecipe>(PhiR) &&
1069 cast<VPReductionPHIRecipe>(PhiR)->isOrdered());
1070 bool NeedsScalar =
1071 isa<VPCanonicalIVPHIRecipe, VPEVLBasedIVPHIRecipe>(PhiR) ||
1072 (isa<VPReductionPHIRecipe>(PhiR) &&
1073 cast<VPReductionPHIRecipe>(PhiR)->isInLoop());
1074 unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->UF;
1075
1076 for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
1077 Value *Phi = State->get(PhiR, Part, NeedsScalar);
1078 Value *Val =
1079 State->get(PhiR->getBackedgeValue(),
1080 SinglePartNeeded ? State->UF - 1 : Part, NeedsScalar);
1081 cast<PHINode>(Phi)->addIncoming(Val, VectorLatchBB);
1082 }
1083 }
1084
1085 State->CFG.DTU.flush();
1086 assert(State->CFG.DTU.getDomTree().verify(
1087 DominatorTree::VerificationLevel::Fast) &&
1088 "DT not preserved correctly");
1089}
1090
1092 // For now only return the cost of the vector loop region, ignoring any other
1093 // blocks, like the preheader or middle blocks.
1094 return getVectorLoopRegion()->cost(VF, Ctx);
1095}
1096
1097#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1100
1101 if (VFxUF.getNumUsers() > 0) {
1102 O << "\nLive-in ";
1103 VFxUF.printAsOperand(O, SlotTracker);
1104 O << " = VF * UF";
1105 }
1106
1107 if (VectorTripCount.getNumUsers() > 0) {
1108 O << "\nLive-in ";
1109 VectorTripCount.printAsOperand(O, SlotTracker);
1110 O << " = vector-trip-count";
1111 }
1112
1113 if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
1114 O << "\nLive-in ";
1115 BackedgeTakenCount->printAsOperand(O, SlotTracker);
1116 O << " = backedge-taken count";
1117 }
1118
1119 O << "\n";
1120 if (TripCount->isLiveIn())
1121 O << "Live-in ";
1122 TripCount->printAsOperand(O, SlotTracker);
1123 O << " = original trip-count";
1124 O << "\n";
1125}
1126
1130
1131 O << "VPlan '" << getName() << "' {";
1132
1133 printLiveIns(O);
1134
1135 if (!getPreheader()->empty()) {
1136 O << "\n";
1137 getPreheader()->print(O, "", SlotTracker);
1138 }
1139
1140 for (const VPBlockBase *Block : vp_depth_first_shallow(getEntry())) {
1141 O << '\n';
1142 Block->print(O, "", SlotTracker);
1143 }
1144
1145 if (!LiveOuts.empty())
1146 O << "\n";
1147 for (const auto &KV : LiveOuts) {
1148 KV.second->print(O, SlotTracker);
1149 }
1150
1151 O << "}\n";
1152}
1153
1154std::string VPlan::getName() const {
1155 std::string Out;
1156 raw_string_ostream RSO(Out);
1157 RSO << Name << " for ";
1158 if (!VFs.empty()) {
1159 RSO << "VF={" << VFs[0];
1160 for (ElementCount VF : drop_begin(VFs))
1161 RSO << "," << VF;
1162 RSO << "},";
1163 }
1164
1165 if (UFs.empty()) {
1166 RSO << "UF>=1";
1167 } else {
1168 RSO << "UF={" << UFs[0];
1169 for (unsigned UF : drop_begin(UFs))
1170 RSO << "," << UF;
1171 RSO << "}";
1172 }
1173
1174 return Out;
1175}
1176
1179 VPlanPrinter Printer(O, *this);
1180 Printer.dump();
1181}
1182
1184void VPlan::dump() const { print(dbgs()); }
1185#endif
1186
1188 assert(LiveOuts.count(PN) == 0 && "an exit value for PN already exists");
1189 LiveOuts.insert({PN, new VPLiveOut(PN, V)});
1190}
1191
1192static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry,
1193 DenseMap<VPValue *, VPValue *> &Old2NewVPValues) {
1194 // Update the operands of all cloned recipes starting at NewEntry. This
1195 // traverses all reachable blocks. This is done in two steps, to handle cycles
1196 // in PHI recipes.
1198 OldDeepRPOT(Entry);
1200 NewDeepRPOT(NewEntry);
1201 // First, collect all mappings from old to new VPValues defined by cloned
1202 // recipes.
1203 for (const auto &[OldBB, NewBB] :
1204 zip(VPBlockUtils::blocksOnly<VPBasicBlock>(OldDeepRPOT),
1205 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT))) {
1206 assert(OldBB->getRecipeList().size() == NewBB->getRecipeList().size() &&
1207 "blocks must have the same number of recipes");
1208 for (const auto &[OldR, NewR] : zip(*OldBB, *NewBB)) {
1209 assert(OldR.getNumOperands() == NewR.getNumOperands() &&
1210 "recipes must have the same number of operands");
1211 assert(OldR.getNumDefinedValues() == NewR.getNumDefinedValues() &&
1212 "recipes must define the same number of operands");
1213 for (const auto &[OldV, NewV] :
1214 zip(OldR.definedValues(), NewR.definedValues()))
1215 Old2NewVPValues[OldV] = NewV;
1216 }
1217 }
1218
1219 // Update all operands to use cloned VPValues.
1220 for (VPBasicBlock *NewBB :
1221 VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT)) {
1222 for (VPRecipeBase &NewR : *NewBB)
1223 for (unsigned I = 0, E = NewR.getNumOperands(); I != E; ++I) {
1224 VPValue *NewOp = Old2NewVPValues.lookup(NewR.getOperand(I));
1225 NewR.setOperand(I, NewOp);
1226 }
1227 }
1228}
1229
1231 // Clone blocks.
1232 VPBasicBlock *NewPreheader = Preheader->clone();
1233 const auto &[NewEntry, __] = cloneFrom(Entry);
1234
1235 // Create VPlan, clone live-ins and remap operands in the cloned blocks.
1236 auto *NewPlan = new VPlan(NewPreheader, cast<VPBasicBlock>(NewEntry));
1237 DenseMap<VPValue *, VPValue *> Old2NewVPValues;
1238 for (VPValue *OldLiveIn : VPLiveInsToFree) {
1239 Old2NewVPValues[OldLiveIn] =
1240 NewPlan->getOrAddLiveIn(OldLiveIn->getLiveInIRValue());
1241 }
1242 Old2NewVPValues[&VectorTripCount] = &NewPlan->VectorTripCount;
1243 Old2NewVPValues[&VFxUF] = &NewPlan->VFxUF;
1244 if (BackedgeTakenCount) {
1245 NewPlan->BackedgeTakenCount = new VPValue();
1246 Old2NewVPValues[BackedgeTakenCount] = NewPlan->BackedgeTakenCount;
1247 }
1248 assert(TripCount && "trip count must be set");
1249 if (TripCount->isLiveIn())
1250 Old2NewVPValues[TripCount] =
1251 NewPlan->getOrAddLiveIn(TripCount->getLiveInIRValue());
1252 // else NewTripCount will be created and inserted into Old2NewVPValues when
1253 // TripCount is cloned. In any case NewPlan->TripCount is updated below.
1254
1255 remapOperands(Preheader, NewPreheader, Old2NewVPValues);
1256 remapOperands(Entry, NewEntry, Old2NewVPValues);
1257
1258 // Clone live-outs.
1259 for (const auto &[_, LO] : LiveOuts)
1260 NewPlan->addLiveOut(LO->getPhi(), Old2NewVPValues[LO->getOperand(0)]);
1261
1262 // Initialize remaining fields of cloned VPlan.
1263 NewPlan->VFs = VFs;
1264 NewPlan->UFs = UFs;
1265 // TODO: Adjust names.
1266 NewPlan->Name = Name;
1267 assert(Old2NewVPValues.contains(TripCount) &&
1268 "TripCount must have been added to Old2NewVPValues");
1269 NewPlan->TripCount = Old2NewVPValues[TripCount];
1270 return NewPlan;
1271}
1272
1273#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1274
1275Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
1276 return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
1277 Twine(getOrCreateBID(Block));
1278}
1279
1280Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
1281 const std::string &Name = Block->getName();
1282 if (!Name.empty())
1283 return Name;
1284 return "VPB" + Twine(getOrCreateBID(Block));
1285}
1286
1288 Depth = 1;
1289 bumpIndent(0);
1290 OS << "digraph VPlan {\n";
1291 OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
1292 if (!Plan.getName().empty())
1293 OS << "\\n" << DOT::EscapeString(Plan.getName());
1294
1295 {
1296 // Print live-ins.
1297 std::string Str;
1298 raw_string_ostream SS(Str);
1299 Plan.printLiveIns(SS);
1301 StringRef(Str).rtrim('\n').split(Lines, "\n");
1302 for (auto Line : Lines)
1303 OS << DOT::EscapeString(Line.str()) << "\\n";
1304 }
1305
1306 OS << "\"]\n";
1307 OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
1308 OS << "edge [fontname=Courier, fontsize=30]\n";
1309 OS << "compound=true\n";
1310
1311 dumpBlock(Plan.getPreheader());
1312
1314 dumpBlock(Block);
1315
1316 OS << "}\n";
1317}
1318
1319void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
1320 if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
1321 dumpBasicBlock(BasicBlock);
1322 else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1323 dumpRegion(Region);
1324 else
1325 llvm_unreachable("Unsupported kind of VPBlock.");
1326}
1327
1328void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
1329 bool Hidden, const Twine &Label) {
1330 // Due to "dot" we print an edge between two regions as an edge between the
1331 // exiting basic block and the entry basic of the respective regions.
1332 const VPBlockBase *Tail = From->getExitingBasicBlock();
1333 const VPBlockBase *Head = To->getEntryBasicBlock();
1334 OS << Indent << getUID(Tail) << " -> " << getUID(Head);
1335 OS << " [ label=\"" << Label << '\"';
1336 if (Tail != From)
1337 OS << " ltail=" << getUID(From);
1338 if (Head != To)
1339 OS << " lhead=" << getUID(To);
1340 if (Hidden)
1341 OS << "; splines=none";
1342 OS << "]\n";
1343}
1344
1345void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
1346 auto &Successors = Block->getSuccessors();
1347 if (Successors.size() == 1)
1348 drawEdge(Block, Successors.front(), false, "");
1349 else if (Successors.size() == 2) {
1350 drawEdge(Block, Successors.front(), false, "T");
1351 drawEdge(Block, Successors.back(), false, "F");
1352 } else {
1353 unsigned SuccessorNumber = 0;
1354 for (auto *Successor : Successors)
1355 drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
1356 }
1357}
1358
1359void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
1360 // Implement dot-formatted dump by performing plain-text dump into the
1361 // temporary storage followed by some post-processing.
1362 OS << Indent << getUID(BasicBlock) << " [label =\n";
1363 bumpIndent(1);
1364 std::string Str;
1366 // Use no indentation as we need to wrap the lines into quotes ourselves.
1367 BasicBlock->print(SS, "", SlotTracker);
1368
1369 // We need to process each line of the output separately, so split
1370 // single-string plain-text dump.
1372 StringRef(Str).rtrim('\n').split(Lines, "\n");
1373
1374 auto EmitLine = [&](StringRef Line, StringRef Suffix) {
1375 OS << Indent << '"' << DOT::EscapeString(Line.str()) << "\\l\"" << Suffix;
1376 };
1377
1378 // Don't need the "+" after the last line.
1379 for (auto Line : make_range(Lines.begin(), Lines.end() - 1))
1380 EmitLine(Line, " +\n");
1381 EmitLine(Lines.back(), "\n");
1382
1383 bumpIndent(-1);
1384 OS << Indent << "]\n";
1385
1387}
1388
1389void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
1390 OS << Indent << "subgraph " << getUID(Region) << " {\n";
1391 bumpIndent(1);
1392 OS << Indent << "fontname=Courier\n"
1393 << Indent << "label=\""
1394 << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
1395 << DOT::EscapeString(Region->getName()) << "\"\n";
1396 // Dump the blocks of the region.
1397 assert(Region->getEntry() && "Region contains no inner blocks.");
1399 dumpBlock(Block);
1400 bumpIndent(-1);
1401 OS << Indent << "}\n";
1403}
1404
1406 if (auto *Inst = dyn_cast<Instruction>(V)) {
1407 if (!Inst->getType()->isVoidTy()) {
1408 Inst->printAsOperand(O, false);
1409 O << " = ";
1410 }
1411 O << Inst->getOpcodeName() << " ";
1412 unsigned E = Inst->getNumOperands();
1413 if (E > 0) {
1414 Inst->getOperand(0)->printAsOperand(O, false);
1415 for (unsigned I = 1; I < E; ++I)
1416 Inst->getOperand(I)->printAsOperand(O << ", ", false);
1417 }
1418 } else // !Inst
1419 V->printAsOperand(O, false);
1420}
1421
1422#endif
1423
1424template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
1425
1427 replaceUsesWithIf(New, [](VPUser &, unsigned) { return true; });
1428}
1429
1431 VPValue *New,
1432 llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace) {
1433 // Note that this early exit is required for correctness; the implementation
1434 // below relies on the number of users for this VPValue to decrease, which
1435 // isn't the case if this == New.
1436 if (this == New)
1437 return;
1438
1439 for (unsigned J = 0; J < getNumUsers();) {
1440 VPUser *User = Users[J];
1441 bool RemovedUser = false;
1442 for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
1443 if (User->getOperand(I) != this || !ShouldReplace(*User, I))
1444 continue;
1445
1446 RemovedUser = true;
1447 User->setOperand(I, New);
1448 }
1449 // If a user got removed after updating the current user, the next user to
1450 // update will be moved to the current position, so we only need to
1451 // increment the index if the number of users did not change.
1452 if (!RemovedUser)
1453 J++;
1454 }
1455}
1456
1457#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1459 OS << Tracker.getOrCreateName(this);
1460}
1461
1463 interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) {
1464 Op->printAsOperand(O, SlotTracker);
1465 });
1466}
1467#endif
1468
1469void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
1470 Old2NewTy &Old2New,
1471 InterleavedAccessInfo &IAI) {
1473 RPOT(Region->getEntry());
1474 for (VPBlockBase *Base : RPOT) {
1475 visitBlock(Base, Old2New, IAI);
1476 }
1477}
1478
1479void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
1480 InterleavedAccessInfo &IAI) {
1481 if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
1482 for (VPRecipeBase &VPI : *VPBB) {
1483 if (isa<VPWidenPHIRecipe>(&VPI))
1484 continue;
1485 assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
1486 auto *VPInst = cast<VPInstruction>(&VPI);
1487
1488 auto *Inst = dyn_cast_or_null<Instruction>(VPInst->getUnderlyingValue());
1489 if (!Inst)
1490 continue;
1491 auto *IG = IAI.getInterleaveGroup(Inst);
1492 if (!IG)
1493 continue;
1494
1495 auto NewIGIter = Old2New.find(IG);
1496 if (NewIGIter == Old2New.end())
1497 Old2New[IG] = new InterleaveGroup<VPInstruction>(
1498 IG->getFactor(), IG->isReverse(), IG->getAlign());
1499
1500 if (Inst == IG->getInsertPos())
1501 Old2New[IG]->setInsertPos(VPInst);
1502
1503 InterleaveGroupMap[VPInst] = Old2New[IG];
1504 InterleaveGroupMap[VPInst]->insertMember(
1505 VPInst, IG->getIndex(Inst),
1506 Align(IG->isReverse() ? (-1) * int(IG->getFactor())
1507 : IG->getFactor()));
1508 }
1509 } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1510 visitRegion(Region, Old2New, IAI);
1511 else
1512 llvm_unreachable("Unsupported kind of VPBlock.");
1513}
1514
1516 InterleavedAccessInfo &IAI) {
1517 Old2NewTy Old2New;
1518 visitRegion(Plan.getVectorLoopRegion(), Old2New, IAI);
1519}
1520
1521void VPSlotTracker::assignName(const VPValue *V) {
1522 assert(!VPValue2Name.contains(V) && "VPValue already has a name!");
1523 auto *UV = V->getUnderlyingValue();
1524 if (!UV) {
1525 VPValue2Name[V] = (Twine("vp<%") + Twine(NextSlot) + ">").str();
1526 NextSlot++;
1527 return;
1528 }
1529
1530 // Use the name of the underlying Value, wrapped in "ir<>", and versioned by
1531 // appending ".Number" to the name if there are multiple uses.
1532 std::string Name;
1534 UV->printAsOperand(S, false);
1535 assert(!Name.empty() && "Name cannot be empty.");
1536 std::string BaseName = (Twine("ir<") + Name + Twine(">")).str();
1537
1538 // First assign the base name for V.
1539 const auto &[A, _] = VPValue2Name.insert({V, BaseName});
1540 // Integer or FP constants with different types will result in he same string
1541 // due to stripping types.
1542 if (V->isLiveIn() && isa<ConstantInt, ConstantFP>(UV))
1543 return;
1544
1545 // If it is already used by C > 0 other VPValues, increase the version counter
1546 // C and use it for V.
1547 const auto &[C, UseInserted] = BaseName2Version.insert({BaseName, 0});
1548 if (!UseInserted) {
1549 C->second++;
1550 A->second = (BaseName + Twine(".") + Twine(C->second)).str();
1551 }
1552}
1553
1554void VPSlotTracker::assignNames(const VPlan &Plan) {
1555 if (Plan.VFxUF.getNumUsers() > 0)
1556 assignName(&Plan.VFxUF);
1557 assignName(&Plan.VectorTripCount);
1558 if (Plan.BackedgeTakenCount)
1559 assignName(Plan.BackedgeTakenCount);
1560 for (VPValue *LI : Plan.VPLiveInsToFree)
1561 assignName(LI);
1562 assignNames(Plan.getPreheader());
1563
1566 for (const VPBasicBlock *VPBB :
1567 VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
1568 assignNames(VPBB);
1569}
1570
1571void VPSlotTracker::assignNames(const VPBasicBlock *VPBB) {
1572 for (const VPRecipeBase &Recipe : *VPBB)
1573 for (VPValue *Def : Recipe.definedValues())
1574 assignName(Def);
1575}
1576
1577std::string VPSlotTracker::getOrCreateName(const VPValue *V) const {
1578 std::string Name = VPValue2Name.lookup(V);
1579 if (!Name.empty())
1580 return Name;
1581
1582 // If no name was assigned, no VPlan was provided when creating the slot
1583 // tracker or it is not reachable from the provided VPlan. This can happen,
1584 // e.g. when trying to print a recipe that has not been inserted into a VPlan
1585 // in a debugger.
1586 // TODO: Update VPSlotTracker constructor to assign names to recipes &
1587 // VPValues not associated with a VPlan, instead of constructing names ad-hoc
1588 // here.
1589 const VPRecipeBase *DefR = V->getDefiningRecipe();
1590 (void)DefR;
1591 assert((!DefR || !DefR->getParent() || !DefR->getParent()->getPlan()) &&
1592 "VPValue defined by a recipe in a VPlan?");
1593
1594 // Use the underlying value's name, if there is one.
1595 if (auto *UV = V->getUnderlyingValue()) {
1596 std::string Name;
1598 UV->printAsOperand(S, false);
1599 return (Twine("ir<") + Name + ">").str();
1600 }
1601
1602 return "<badref>";
1603}
1604
1606 return all_of(Def->users(),
1607 [Def](const VPUser *U) { return U->onlyFirstLaneUsed(Def); });
1608}
1609
1611 return all_of(Def->users(),
1612 [Def](const VPUser *U) { return U->onlyFirstPartUsed(Def); });
1613}
1614
1616 ScalarEvolution &SE) {
1617 if (auto *Expanded = Plan.getSCEVExpansion(Expr))
1618 return Expanded;
1619 VPValue *Expanded = nullptr;
1620 if (auto *E = dyn_cast<SCEVConstant>(Expr))
1621 Expanded = Plan.getOrAddLiveIn(E->getValue());
1622 else if (auto *E = dyn_cast<SCEVUnknown>(Expr))
1623 Expanded = Plan.getOrAddLiveIn(E->getValue());
1624 else {
1625 Expanded = new VPExpandSCEVRecipe(Expr, SE);
1627 }
1628 Plan.addSCEVExpansion(Expr, Expanded);
1629 return Expanded;
1630}
1631
1633 if (isa<VPActiveLaneMaskPHIRecipe>(V))
1634 return true;
1635
1636 auto IsWideCanonicalIV = [](VPValue *A) {
1637 return isa<VPWidenCanonicalIVRecipe>(A) ||
1638 (isa<VPWidenIntOrFpInductionRecipe>(A) &&
1639 cast<VPWidenIntOrFpInductionRecipe>(A)->isCanonical());
1640 };
1641
1642 VPValue *A, *B;
1644 return B == Plan.getTripCount() &&
1646 IsWideCanonicalIV(A));
1647
1648 return match(V, m_Binary<Instruction::ICmp>(m_VPValue(A), m_VPValue(B))) &&
1649 IsWideCanonicalIV(A) && B == Plan.getOrCreateBackedgeTakenCount();
1650}
1651
1653 const std::function<bool(ElementCount)> &Predicate, VFRange &Range) {
1654 assert(!Range.isEmpty() && "Trying to test an empty VF range.");
1655 bool PredicateAtRangeStart = Predicate(Range.Start);
1656
1657 for (ElementCount TmpVF : VFRange(Range.Start * 2, Range.End))
1658 if (Predicate(TmpVF) != PredicateAtRangeStart) {
1659 Range.End = TmpVF;
1660 break;
1661 }
1662
1663 return PredicateAtRangeStart;
1664}
1665
1666/// Build VPlans for the full range of feasible VF's = {\p MinVF, 2 * \p MinVF,
1667/// 4 * \p MinVF, ..., \p MaxVF} by repeatedly building a VPlan for a sub-range
1668/// of VF's starting at a given VF and extending it as much as possible. Each
1669/// vectorization decision can potentially shorten this sub-range during
1670/// buildVPlan().
1672 ElementCount MaxVF) {
1673 auto MaxVFTimes2 = MaxVF * 2;
1674 for (ElementCount VF = MinVF; ElementCount::isKnownLT(VF, MaxVFTimes2);) {
1675 VFRange SubRange = {VF, MaxVFTimes2};
1676 auto Plan = buildVPlan(SubRange);
1677 VPlanTransforms::optimize(*Plan, *PSE.getSE());
1678 VPlans.push_back(std::move(Plan));
1679 VF = SubRange.End;
1680 }
1681}
1682
1684 assert(count_if(VPlans,
1685 [VF](const VPlanPtr &Plan) { return Plan->hasVF(VF); }) ==
1686 1 &&
1687 "Multiple VPlans for VF.");
1688
1689 for (const VPlanPtr &Plan : VPlans) {
1690 if (Plan->hasVF(VF))
1691 return *Plan.get();
1692 }
1693 llvm_unreachable("No plan found!");
1694}
1695
1696#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1698 if (VPlans.empty()) {
1699 O << "LV: No VPlans built.\n";
1700 return;
1701 }
1702 for (const auto &Plan : VPlans)
1704 Plan->printDOT(O);
1705 else
1706 Plan->print(O);
1707}
1708#endif
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:533
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
Flatten the CFG
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
This file provides a LoopVectorizationPlanner class.
#define I(x, y, z)
Definition: MD5.cpp:58
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
#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.
This file provides utility VPlan to VPlan transformations.
static T * getPlanEntry(T *Start)
Definition: VPlan.cpp:135
static void replaceVPBBWithIRVPBB(VPBasicBlock *VPBB, BasicBlock *IRBB)
Replace VPBB with a VPIRBasicBlock wrapping IRBB.
Definition: VPlan.cpp:964
static bool hasConditionalTerminator(const VPBasicBlock *VPBB)
Definition: VPlan.cpp:590
static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry, DenseMap< VPValue *, VPValue * > &Old2NewVPValues)
Definition: VPlan.cpp:1192
static std::pair< VPBlockBase *, VPBlockBase * > cloneFrom(VPBlockBase *Entry)
Definition: VPlan.cpp:668
static cl::opt< bool > PrintVPlansInDotFormat("vplan-print-in-dot-format", cl::Hidden, cl::desc("Use dot format instead of plain text when dumping VPlans"))
This file contains the declarations of the Vectorization Plan base classes:
static bool IsCondBranch(unsigned BrOpc)
static const uint32_t IV[8]
Definition: blake3_impl.h:78
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
iterator end()
Definition: BasicBlock.h:461
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:4863
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:212
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:489
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:219
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:177
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:168
size_t size() const
Definition: BasicBlock.h:469
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:239
static BranchInst * Create(BasicBlock *IfTrue, InsertPosition InsertBefore=nullptr)
@ ICMP_EQ
equal
Definition: InstrTypes.h:778
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:850
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:194
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:146
Core dominator tree base class.
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
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:322
bool shouldEmitDebugInfoForProfiling() const
Returns true if we should emit debug info for profiling.
Definition: Metadata.cpp:1841
DomTreeT & getDomTree()
Flush DomTree updates and return DomTree.
void applyUpdates(ArrayRef< typename DomTreeT::UpdateType > Updates)
Submit updates to all available trees.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:91
Value * CreateInsertElement(Type *VecTy, Value *NewElt, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2492
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2480
UnreachableInst * CreateUnreachable()
Definition: IRBuilder.h:1280
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Definition: IRBuilder.cpp:1193
IntegerType * getInt32Ty()
Fetch the type representing a 32-bit integer.
Definition: IRBuilder.h:523
BasicBlock * GetInsertBlock() const
Definition: IRBuilder.h:171
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Definition: IRBuilder.h:217
InsertPoint saveIP() const
Returns the current insert point.
Definition: IRBuilder.h:274
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:483
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1361
BranchInst * CreateBr(BasicBlock *Dest)
Create an unconditional 'br label X' instruction.
Definition: IRBuilder.h:1131
void restoreIP(InsertPoint IP)
Sets the current insert point to a previously-saved location.
Definition: IRBuilder.h:286
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:177
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2686
InnerLoopVectorizer vectorizes loops which contain only one basic block to a specified vectorization ...
static InstructionCost getInvalid(CostType Val=0)
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:92
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:468
Drive the analysis of interleaved memory accesses in the loop.
Definition: VectorUtils.h:610
InterleaveGroup< Instruction > * getInterleaveGroup(const Instruction *Instr) const
Get the interleave group that Instr belongs to.
Definition: VectorUtils.h:655
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
void addChildLoop(LoopT *NewChild)
Add the specified loop to be a child of this loop.
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
BlockT * getUniqueExitBlock() const
If getUniqueExitBlocks would return exactly one block, return that block.
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
LoopT * AllocateLoop(ArgsTy &&...Args)
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
VPlan & getPlanFor(ElementCount VF) const
Return the VPlan for VF.
Definition: VPlan.cpp:1683
void buildVPlans(ElementCount MinVF, ElementCount MaxVF)
Build VPlans for power-of-2 VF's between MinVF and MaxVF inclusive, according to the information gath...
Definition: VPlan.cpp:1671
static bool getDecisionAndClampRange(const std::function< bool(ElementCount)> &Predicate, VFRange &Range)
Test a Predicate on a Range of VF's.
Definition: VPlan.cpp:1652
void printPlans(raw_ostream &O)
Definition: VPlan.cpp:1697
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:39
void eraseFromParent()
This method unlinks 'this' from the containing function and deletes it.
void dump() const
User-friendly dump.
Definition: AsmWriter.cpp:5299
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1852
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:320
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
The main scalar evolution driver.
size_type size() const
Determine the number of elements in the SetVector.
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:697
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
void push_back(const T &Elt)
Definition: SmallVector.h:426
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:685
StringRef rtrim(char Char) const
Return string with consecutive Char characters starting from the right removed.
Definition: StringRef.h:788
@ TCK_RecipThroughput
Reciprocal throughput.
InstructionCost getCFInstrCost(unsigned Opcode, TTI::TargetCostKind CostKind=TTI::TCK_SizeAndLatency, const Instruction *I=nullptr) const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
static IntegerType * getInt1Ty(LLVMContext &C)
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:128
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:2992
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
Definition: VPlan.h:3064
VPBasicBlock * clone() override
Clone the current block and it's recipes, without updating the operands of the cloned recipes.
Definition: VPlan.h:3111
RecipeListTy::iterator iterator
Instruction iterators...
Definition: VPlan.h:3016
void execute(VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPBasicBlock,...
Definition: VPlan.cpp:488
iterator end()
Definition: VPlan.h:3026
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:3024
InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override
Return the cost of this VPBasicBlock.
Definition: VPlan.cpp:785
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
Definition: VPlan.cpp:217
VPRegionBlock * getEnclosingLoopRegion()
Definition: VPlan.cpp:580
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:532
VPBasicBlock * splitAt(iterator SplitAt)
Split current block at SplitAt by inserting a new block between the current block and its successors ...
Definition: VPlan.cpp:555
void executeRecipes(VPTransformState *State, BasicBlock *BB)
Execute the recipes in the IR basic block BB.
Definition: VPlan.cpp:542
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:647
bool isExiting() const
Returns true if the block is exiting it's parent region.
Definition: VPlan.cpp:630
VPRecipeBase * getTerminator()
If the block has multiple successors, return the branch recipe terminating the block.
Definition: VPlan.cpp:618
const VPRecipeBase & back() const
Definition: VPlan.h:3038
bool empty() const
Definition: VPlan.h:3035
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:437
void setSuccessors(ArrayRef< VPBlockBase * > NewSuccs)
Set each VPBasicBlock in NewSuccss as successor of this VPBlockBase.
Definition: VPlan.h:632
VPRegionBlock * getParent()
Definition: VPlan.h:509
const VPBasicBlock * getExitingBasicBlock() const
Definition: VPlan.cpp:182
size_t getNumSuccessors() const
Definition: VPlan.h:554
iterator_range< VPBlockBase ** > successors()
Definition: VPlan.h:537
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:635
void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
Definition: VPlan.h:623
VPBlockBase * getEnclosingBlockWithPredecessors()
Definition: VPlan.cpp:204
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:539
static void deleteCFG(VPBlockBase *Entry)
Delete all blocks reachable from a given VPBlockBase, inclusive.
Definition: VPlan.cpp:212
VPlan * getPlan()
Definition: VPlan.cpp:155
void setPlan(VPlan *ParentPlan)
Sets the pointer of the plan containing the block.
Definition: VPlan.cpp:174
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:580
VPBlockBase * getSinglePredecessor() const
Definition: VPlan.h:550
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:574
VPBlockBase * getEnclosingBlockWithSuccessors()
An Enclosing Block of a block B is any block containing B, including B itself.
Definition: VPlan.cpp:196
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:160
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:534
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:3600
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:3647
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:3636
VPlan-based builder utility analogous to IRBuilder.
This class augments a recipe with a set of VPValues defined by the recipe.
Definition: VPlanValue.h:307
void dump() const
Dump the VPDef to stderr (for debugging).
Definition: VPlan.cpp:116
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:2699
A special type of VPBasicBlock that wraps an existing IR basic block.
Definition: VPlan.h:3133
void execute(VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPBasicBlock,...
Definition: VPlan.cpp:457
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:1233
VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI)
Definition: VPlan.cpp:1515
In what follows, the term "input IR" refers to code that is fed into the vectorizer whereas the term ...
Definition: VPlan.h:156
Value * getAsRuntimeExpr(IRBuilderBase &Builder, const ElementCount &VF) const
Returns an expression describing the lane index that can be used at runtime.
Definition: VPlan.cpp:75
static VPLane getFirstLane()
Definition: VPlan.h:180
@ 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:704
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:766
VPBasicBlock * getParent()
Definition: VPlan.h:791
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:3170
VPRegionBlock * clone() override
Clone all blocks in the single-entry single-exit region of the block and their recipes without updati...
Definition: VPlan.cpp:718
const VPBlockBase * getEntry() const
Definition: VPlan.h:3209
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:3241
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:727
InstructionCost cost(ElementCount VF, VPCostContext &Ctx) override
Return the cost of the block.
Definition: VPlan.cpp:792
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:828
void execute(VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPRegionBlock,...
Definition: VPlan.cpp:734
const VPBlockBase * getExiting() const
Definition: VPlan.h:3221
VPBasicBlock * getPreheaderVPBB()
Returns the pre-header VPBasicBlock of the loop region.
Definition: VPlan.h:3234
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:1577
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:202
void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const
Print the operands to O.
Definition: VPlan.cpp:1462
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
Definition: VPlan.cpp:125
void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const
Definition: VPlan.cpp:1458
void dump() const
Dump the value to stderr (for debugging).
Definition: VPlan.cpp:108
VPValue(const unsigned char SC, Value *UV=nullptr, VPDef *Def=nullptr)
Definition: VPlan.cpp:88
virtual ~VPValue()
Definition: VPlan.cpp:94
void print(raw_ostream &OS, VPSlotTracker &Tracker) const
Definition: VPlan.cpp:101
void replaceAllUsesWith(VPValue *New)
Definition: VPlan.cpp:1426
unsigned getNumUsers() const
Definition: VPlanValue.h:111
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:1430
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:3520
LLVM_DUMP_METHOD void dump()
Definition: VPlan.cpp:1287
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:3274
void printDOT(raw_ostream &O) const
Print this VPlan in DOT format to O.
Definition: VPlan.cpp:1178
std::string getName() const
Return a string with the name of the plan and the applicable VFs and UFs.
Definition: VPlan.cpp:1154
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:921
VPBasicBlock * getEntry()
Definition: VPlan.h:3376
VPValue & getVectorTripCount()
The vector trip count.
Definition: VPlan.h:3401
VPValue * getTripCount() const
The trip count of the original loop.
Definition: VPlan.h:3380
VPValue * getOrCreateBackedgeTakenCount()
The backedge taken count of the original loop.
Definition: VPlan.h:3394
void addLiveOut(PHINode *PN, VPValue *V)
Definition: VPlan.cpp:1187
VPBasicBlock * getPreheader()
Definition: VPlan.h:3509
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:3476
bool hasVF(ElementCount VF)
Definition: VPlan.h:3414
void addSCEVExpansion(const SCEV *S, VPValue *V)
Definition: VPlan.h:3503
InstructionCost cost(ElementCount VF, VPCostContext &Ctx)
Return the cost of this plan.
Definition: VPlan.cpp:1091
static VPlanPtr createInitialVPlan(const SCEV *TripCount, ScalarEvolution &PSE, bool RequiresScalarEpilogueCheck, bool TailFolded, Loop *TheLoop)
Create initial VPlan, having an "entry" VPBasicBlock (wrapping original scalar pre-header ) which con...
Definition: VPlan.cpp:863
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:3442
LLVM_DUMP_METHOD void dump() const
Dump the plan to stderr (for debugging).
Definition: VPlan.cpp:1184
void execute(VPTransformState *State)
Generate the IR code for this VPlan.
Definition: VPlan.cpp:981
void print(raw_ostream &O) const
Print this VPlan to O.
Definition: VPlan.cpp:1128
VPValue * getSCEVExpansion(const SCEV *S) const
Definition: VPlan.h:3499
void printLiveIns(raw_ostream &O) const
Print the live-ins of this VPlan to O.
Definition: VPlan.cpp:1098
VPlan * duplicate()
Clone the current VPlan, update all VPValues of the new VPlan and cloned recipes to refer to the clon...
Definition: VPlan.cpp:1230
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:664
static constexpr bool isKnownLT(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
Definition: TypeSize.h:218
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:661
#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:56
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:972
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
BinaryVPInstruction_match< Op0_t, Op1_t, VPInstruction::ActiveLaneMask > m_ActiveLaneMask(const Op0_t &Op0, const Op1_t &Op1)
VPCanonicalIVPHI_match m_CanonicalIV()
VPScalarIVSteps_match< Op0_t, Op1_t > m_ScalarIVSteps(const Op0_t &Op0, const Op1_t &Op1)
BinaryVPInstruction_match< Op0_t, Op1_t, VPInstruction::BranchOnCount > m_BranchOnCount(const Op0_t &Op0, const Op1_t &Op1)
UnaryVPInstruction_match< Op0_t, VPInstruction::BranchOnCond > m_BranchOnCond(const Op0_t &Op0)
class_match< VPValue > m_VPValue()
Match an arbitrary VPValue and ignore it.
@ SS
Definition: X86.h:211
bool isUniformAfterVectorization(const VPValue *VPV)
Returns true if VPV is uniform after vectorization.
Definition: VPlan.h:3824
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)
Get or create a VPValue that corresponds to the expansion of Expr.
Definition: VPlan.cpp:1615
bool onlyFirstPartUsed(const VPValue *Def)
Returns true if only the first part of Def is used.
Definition: VPlan.cpp:1610
bool onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used.
Definition: VPlan.cpp:1605
bool isHeaderMask(const VPValue *V, VPlan &Plan)
Return true if V is a header mask in Plan.
Definition: VPlan.cpp:1632
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 size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1680
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:2190
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
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:56
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:147
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:292
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:1928
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.
InstructionCost Cost
unsigned getReciprocalPredBlockProb()
A helper function that returns the reciprocal of the block probability of predicated blocks.
Definition: VPlan.h:95
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
A range of powers-of-2 vectorization factors with fixed start and adjustable end.
Definition: VPlan.h:100
ElementCount End
Definition: VPlan.h:105
Struct to hold various analysis needed for cost computations.
Definition: VPlan.h:737
const TargetTransformInfo & TTI
Definition: VPlan.h:738
VPIteration represents a single point in the iteration space of the output (vectorized and/or unrolle...
Definition: VPlan.h:238
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:378
BasicBlock * PrevBB
The previous IR BasicBlock created or used.
Definition: VPlan.h:384
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:392
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:380
BasicBlock * ExitBB
The last IR BasicBlock in the output IR.
Definition: VPlan.h:388
BasicBlock * getPreheaderBBFor(VPRecipeBase *R)
Returns the BasicBlock* mapped to the pre-header of the loop region containing R.
Definition: VPlan.cpp:361
DomTreeUpdater DTU
Updater for the DominatorTree.
Definition: VPlan.h:395
DenseMap< VPValue *, ScalarsPerPartValuesTy > PerPartScalars
Definition: VPlan.h:278
DenseMap< VPValue *, PerPartValuesTy > PerPartOutput
Definition: VPlan.h:275
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:255
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:259
LoopInfo * LI
Hold a pointer to LoopInfo to register new basic blocks in the loop.
Definition: VPlan.h:406
VPTransformState(ElementCount VF, unsigned UF, LoopInfo *LI, DominatorTree *DT, IRBuilderBase &Builder, InnerLoopVectorizer *ILV, VPlan *Plan, LLVMContext &Ctx)
Definition: VPlan.cpp:224
struct llvm::VPTransformState::DataState Data
void addMetadata(Value *To, Instruction *From)
Add metadata from one instruction to another.
Definition: VPlan.cpp:374
struct llvm::VPTransformState::CFGState CFG
LoopVersioning * LVer
LoopVersioning.
Definition: VPlan.h:425
void addNewMetadata(Instruction *To, const Instruction *Orig)
Add additional metadata to To that was not present on Orig.
Definition: VPlan.cpp:366
void packScalarIntoVectorValue(VPValue *Def, const VPIteration &Instance)
Construct the vector value of a scalarized value V one lane at a time.
Definition: VPlan.cpp:406
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:307
std::optional< VPIteration > Instance
Hold the indices to generate specific scalar instructions.
Definition: VPlan.h:267
IRBuilderBase & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Definition: VPlan.h:409
bool hasScalarValue(VPValue *Def, VPIteration Instance)
Definition: VPlan.h:295
VPlan * Plan
Pointer to the VPlan code is generated for.
Definition: VPlan.h:415
bool hasVectorValue(VPValue *Def, unsigned Part)
Definition: VPlan.h:289
ElementCount VF
The chosen Vectorization and Unroll Factors of the loop being vectorized.
Definition: VPlan.h:261
Loop * CurrentVectorLoop
The loop object for the current parent region, or nullptr.
Definition: VPlan.h:418
void setDebugLocFrom(DebugLoc DL)
Set the debug location in the builder using the debug location DL.
Definition: VPlan.cpp:385
void print(raw_ostream &O) const
Definition: VPlan.cpp:1405
static void optimize(VPlan &Plan, ScalarEvolution &SE)
Apply VPlan-to-VPlan optimizations to Plan, including induction recipe optimizations,...