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 "LoopVectorizationPlanner.h"
21#include "VPlanCFG.h"
22#include "VPlanDominatorTree.h"
23#include "VPlanHelpers.h"
24#include "VPlanPatternMatch.h"
25#include "VPlanTransforms.h"
26#include "VPlanUtils.h"
27#include "llvm/ADT/PostOrderIterator.h"
28#include "llvm/ADT/STLExtras.h"
29#include "llvm/ADT/SmallVector.h"
30#include "llvm/ADT/StringExtras.h"
31#include "llvm/ADT/Twine.h"
32#include "llvm/Analysis/DomTreeUpdater.h"
33#include "llvm/Analysis/LoopInfo.h"
34#include "llvm/Analysis/OptimizationRemarkEmitter.h"
35#include "llvm/IR/BasicBlock.h"
36#include "llvm/IR/CFG.h"
37#include "llvm/IR/IRBuilder.h"
38#include "llvm/IR/Instruction.h"
39#include "llvm/IR/Instructions.h"
40#include "llvm/IR/Type.h"
41#include "llvm/IR/Value.h"
42#include "llvm/Support/Casting.h"
43#include "llvm/Support/CommandLine.h"
44#include "llvm/Support/Debug.h"
45#include "llvm/Support/GraphWriter.h"
46#include "llvm/Support/raw_ostream.h"
47#include "llvm/Transforms/Utils/BasicBlockUtils.h"
48#include "llvm/Transforms/Utils/LoopVersioning.h"
49#include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h"
50#include <cassert>
51#include <string>
52
53using namespace llvm;
54using namespace llvm::VPlanPatternMatch;
55
56namespace llvm {
57extern cl::opt<bool> ProfcheckDisableMetadataFixes;
58} // namespace llvm
59
60/// @{
61/// Metadata attribute names
62const char LLVMLoopVectorizeFollowupAll[] = "llvm.loop.vectorize.followup_all";
63const char LLVMLoopVectorizeFollowupVectorized[] =
64 "llvm.loop.vectorize.followup_vectorized";
65const char LLVMLoopVectorizeFollowupEpilogue[] =
66 "llvm.loop.vectorize.followup_epilogue";
67/// @}
68
69extern cl::opt<unsigned> ForceTargetInstructionCost;
70
71extern cl::opt<unsigned> NumberOfStoresToPredicate;
72
73static cl::opt<bool> PrintVPlansInDotFormat(
74 "vplan-print-in-dot-format", cl::Hidden,
75 cl::desc("Use dot format instead of plain text when dumping VPlans"));
76
77#define DEBUG_TYPE "loop-vectorize"
78
79#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
80raw_ostream &llvm::operator<<(raw_ostream &OS, const VPRecipeBase &R) {
81 const VPBasicBlock *Parent = R.getParent();
82 VPSlotTracker SlotTracker(Parent ? Parent->getPlan() : nullptr);
83 R.print(OS, "", SlotTracker);
84 return OS;
85}
86#endif
87
88Value *VPLane::getAsRuntimeExpr(IRBuilderBase &Builder,
89 const ElementCount &VF) const {
90 switch (LaneKind) {
91 case VPLane::Kind::ScalableLast:
92 // Lane = RuntimeVF - VF.getKnownMinValue() + Lane
93 return Builder.CreateSub(LHS: getRuntimeVF(B&: Builder, Ty: Builder.getInt32Ty(), VF),
94 RHS: Builder.getInt32(C: VF.getKnownMinValue() - Lane));
95 case VPLane::Kind::First:
96 return Builder.getInt64(C: Lane);
97 }
98 llvm_unreachable("Unknown lane kind");
99}
100
101#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
102void VPValue::print(raw_ostream &OS, VPSlotTracker &SlotTracker) const {
103 if (const VPRecipeBase *R = getDefiningRecipe())
104 R->print(OS, "", SlotTracker);
105 else
106 printAsOperand(OS, SlotTracker);
107}
108
109void VPValue::dump() const {
110 const VPRecipeBase *Instr = getDefiningRecipe();
111 VPSlotTracker SlotTracker(
112 (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
113 print(dbgs(), SlotTracker);
114 dbgs() << "\n";
115}
116
117void VPRecipeBase::dump() const {
118 VPSlotTracker SlotTracker(getParent() ? getParent()->getPlan() : nullptr);
119 print(dbgs(), "", SlotTracker);
120 dbgs() << "\n";
121}
122#endif
123
124#if !defined(NDEBUG)
125bool VPRecipeValue::isDefinedBy(const VPDef *D) const {
126 return getDefiningRecipe() == D;
127}
128#endif
129
130VPRecipeBase *VPValue::getDefiningRecipe() {
131 auto *RecipeValue = dyn_cast<VPRecipeValue>(Val: this);
132 if (!RecipeValue)
133 return nullptr;
134 if (auto *MultiDef = dyn_cast<VPMultiDefValue>(Val: RecipeValue))
135 return MultiDef->getDef();
136 return static_cast<VPSingleDefRecipe *>(RecipeValue);
137}
138
139const VPRecipeBase *VPValue::getDefiningRecipe() const {
140 return const_cast<VPValue *>(this)->getDefiningRecipe();
141}
142
143Value *VPValue::getLiveInIRValue() const {
144 return cast<VPIRValue>(Val: this)->getValue();
145}
146
147Type *VPIRValue::getType() const { return getUnderlyingValue()->getType(); }
148
149Type *VPValue::getScalarType() const {
150 switch (getVPValueID()) {
151 case VPVIRValueSC:
152 return cast<VPIRValue>(Val: this)->getType();
153 case VPRegionValueSC:
154 return cast<VPRegionValue>(Val: this)->getType();
155 case VPVSymbolicSC:
156 return cast<VPSymbolicValue>(Val: this)->getType();
157 case VPVMultiDefValueSC:
158 case VPVSingleDefValueSC:
159 return cast<VPRecipeValue>(Val: this)->getScalarType();
160 }
161 llvm_unreachable("Unhandled VPValue subclass");
162}
163
164VPRecipeValue::~VPRecipeValue() {
165 assert(Users.empty() &&
166 "trying to delete a VPRecipeValue with remaining users");
167}
168
169VPSingleDefValue::VPSingleDefValue(VPSingleDefRecipe *Def, Value *UV, Type *Ty)
170 : VPRecipeValue(VPVSingleDefValueSC, UV, Ty) {
171 assert(Def && "VPSingleDefValue requires a defining recipe");
172 Def->addDefinedValue(V: this);
173}
174
175VPSingleDefValue::~VPSingleDefValue() {
176 getDefiningRecipe()->removeDefinedValue(V: this);
177}
178
179VPMultiDefValue::VPMultiDefValue(VPRecipeBase *Def, Value *UV, Type *Ty)
180 : VPRecipeValue(VPVMultiDefValueSC, UV, Ty), Def(Def) {
181 assert(Def && "VPMultiDefValue requires a defining recipe");
182 Def->addDefinedValue(V: this);
183}
184
185VPMultiDefValue::~VPMultiDefValue() {
186 getDefiningRecipe()->removeDefinedValue(V: this);
187}
188
189// Get the top-most entry block of \p Start. This is the entry block of the
190// containing VPlan. This function is templated to support both const and non-const blocks
191template <typename T> static T *getPlanEntry(T *Start) {
192 T *Next = Start;
193 T *Current = Start;
194 while ((Next = Next->getParent()))
195 Current = Next;
196
197 SmallSetVector<T *, 8> WorkList;
198 WorkList.insert(Current);
199
200 for (unsigned i = 0; i < WorkList.size(); i++) {
201 T *Current = WorkList[i];
202 if (!Current->hasPredecessors())
203 return Current;
204 auto &Predecessors = Current->getPredecessors();
205 WorkList.insert_range(Predecessors);
206 }
207
208 llvm_unreachable("VPlan without any entry node without predecessors");
209}
210
211VPlan *VPBlockBase::getPlan() { return getPlanEntry(Start: this)->Plan; }
212
213const VPlan *VPBlockBase::getPlan() const { return getPlanEntry(Start: this)->Plan; }
214
215/// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
216const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const {
217 const VPBlockBase *Block = this;
218 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Val: Block))
219 Block = Region->getEntry();
220 return cast<VPBasicBlock>(Val: Block);
221}
222
223VPBasicBlock *VPBlockBase::getEntryBasicBlock() {
224 VPBlockBase *Block = this;
225 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Val: Block))
226 Block = Region->getEntry();
227 return cast<VPBasicBlock>(Val: Block);
228}
229
230void VPBlockBase::setPlan(VPlan *ParentPlan) {
231 assert(ParentPlan->getEntry() == this && "Can only set plan on its entry.");
232 Plan = ParentPlan;
233}
234
235/// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
236const VPBasicBlock *VPBlockBase::getExitingBasicBlock() const {
237 const VPBlockBase *Block = this;
238 while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Val: Block))
239 Block = Region->getExiting();
240 return cast<VPBasicBlock>(Val: Block);
241}
242
243VPBasicBlock *VPBlockBase::getExitingBasicBlock() {
244 VPBlockBase *Block = this;
245 while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Val: Block))
246 Block = Region->getExiting();
247 return cast<VPBasicBlock>(Val: Block);
248}
249
250VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() {
251 if (!Successors.empty() || !Parent)
252 return this;
253 assert(Parent->getExiting() == this &&
254 "Block w/o successors not the exiting block of its parent.");
255 return Parent->getEnclosingBlockWithSuccessors();
256}
257
258VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {
259 if (!Predecessors.empty() || !Parent)
260 return this;
261 assert(Parent->getEntry() == this &&
262 "Block w/o predecessors not the entry of its parent.");
263 return Parent->getEnclosingBlockWithPredecessors();
264}
265
266VPBasicBlock::iterator VPBasicBlock::getFirstNonPhi() {
267 iterator It = begin();
268 while (It != end() && It->isPhi())
269 It++;
270 return It;
271}
272
273VPTransformState::VPTransformState(const TargetTransformInfo *TTI,
274 ElementCount VF, LoopInfo *LI,
275 DominatorTree *DT, AssumptionCache *AC,
276 IRBuilderBase &Builder, VPlan *Plan,
277 Loop *CurrentParentLoop)
278 : TTI(TTI), VF(VF), CFG(DT), LI(LI), AC(AC), Builder(Builder), Plan(Plan),
279 CurrentParentLoop(CurrentParentLoop), VPDT(*Plan) {}
280
281Value *VPTransformState::get(const VPValue *Def, const VPLane &Lane) {
282 assert(!isa<VPRegionValue>(Def) &&
283 "VPRegionValue must be materialized before VPTransformState::get");
284 if (isa<VPIRValue, VPSymbolicValue>(Val: Def))
285 return Def->getUnderlyingValue();
286
287 if (hasScalarValue(Def, Lane))
288 return Data.VPV2Scalars[Def][Lane.mapToCacheIndex(VF)];
289
290 if (!Lane.isFirstLane() && vputils::isSingleScalar(VPV: Def) &&
291 hasScalarValue(Def, Lane: VPLane::getFirstLane())) {
292 return Data.VPV2Scalars[Def][0];
293 }
294
295 // Look through BuildVector to avoid redundant extracts.
296 // TODO: Remove once replicate regions are unrolled explicitly.
297 if (Lane.getKind() == VPLane::Kind::First && match(V: Def, P: m_BuildVector())) {
298 auto *BuildVector = cast<VPInstruction>(Val: Def);
299 return get(Def: BuildVector->getOperand(N: Lane.getKnownLane()), IsScalar: true);
300 }
301
302 assert(hasVectorValue(Def));
303 auto *VecPart = Data.VPV2Vector[Def];
304 if (!VecPart->getType()->isVectorTy()) {
305 assert(Lane.isFirstLane() && "cannot get lane > 0 for scalar");
306 return VecPart;
307 }
308 // TODO: Cache created scalar values.
309 Value *LaneV = Lane.getAsRuntimeExpr(Builder, VF);
310 auto *Extract = Builder.CreateExtractElement(Vec: VecPart, Idx: LaneV);
311 // set(Def, Extract, Instance);
312 return Extract;
313}
314
315Value *VPTransformState::get(const VPValue *Def, bool NeedsScalar) {
316 assert(!isa<VPRegionValue>(Def) &&
317 "VPRegionValue must be materialized before VPTransformState::get");
318 if (NeedsScalar) {
319 assert((VF.isScalar() || isa<VPIRValue, VPSymbolicValue>(Def) ||
320 hasVectorValue(Def) || !vputils::onlyFirstLaneUsed(Def) ||
321 (hasScalarValue(Def, VPLane(0)) &&
322 Data.VPV2Scalars[Def].size() == 1)) &&
323 "Trying to access a single scalar per part but has multiple scalars "
324 "per part.");
325 return get(Def, Lane: VPLane(0));
326 }
327
328 // If Values have been set for this Def return the one relevant for \p Part.
329 if (hasVectorValue(Def))
330 return Data.VPV2Vector[Def];
331
332 auto GetBroadcastInstrs = [this](Value *V) {
333 if (VF.isScalar())
334 return V;
335 // Broadcast the scalar into all locations in the vector.
336 Value *Shuf = Builder.CreateVectorSplat(EC: VF, V, Name: "broadcast");
337 return Shuf;
338 };
339
340 Value *ScalarValue = get(Def, Lane: VPLane(0));
341 VPLane LastLane = VPLane::getLastLaneForVF(VF);
342 IRBuilderBase::InsertPointGuard Guard(Builder);
343 if (auto *LastInst = dyn_cast<Instruction>(Val: get(Def, Lane: LastLane)))
344 // Set the insert point after the last scalarized instruction or after the
345 // last PHI, if LastInst is a PHI. This ensures the insertelement sequence
346 // will directly follow the scalar definitions.
347 Builder.SetInsertPoint(isa<PHINode>(Val: LastInst)
348 ? LastInst->getParent()->getFirstNonPHIIt()
349 : std::next(x: BasicBlock::iterator(LastInst)));
350 Value *VectorValue = GetBroadcastInstrs(ScalarValue);
351 set(Def, V: VectorValue);
352 return VectorValue;
353}
354
355void VPTransformState::setDebugLocFrom(DebugLoc DL) {
356 const DILocation *DIL = DL;
357 // When a FSDiscriminator is enabled, we don't need to add the multiply
358 // factors to the discriminators.
359 if (DIL &&
360 Builder.GetInsertBlock()
361 ->getParent()
362 ->shouldEmitDebugInfoForProfiling() &&
363 !EnableFSDiscriminator) {
364 // FIXME: For scalable vectors, assume vscale=1.
365 unsigned UF = Plan->getConcreteUF();
366 auto NewDIL =
367 DIL->cloneByMultiplyingDuplicationFactor(DF: UF * VF.getKnownMinValue());
368 if (NewDIL)
369 Builder.SetCurrentDebugLocation(*NewDIL);
370 else
371 LLVM_DEBUG(dbgs() << "Failed to create new discriminator: "
372 << DIL->getFilename() << " Line: " << DIL->getLine());
373 } else
374 Builder.SetCurrentDebugLocation(DL);
375}
376
377Value *VPTransformState::packScalarIntoVectorizedValue(const VPValue *Def,
378 Value *WideValue,
379 const VPLane &Lane) {
380 Value *ScalarInst = get(Def, Lane);
381 Value *LaneExpr = Lane.getAsRuntimeExpr(Builder, VF);
382 if (auto *StructTy = dyn_cast<StructType>(Val: WideValue->getType())) {
383 // We must handle each element of a vectorized struct type.
384 for (unsigned I = 0, E = StructTy->getNumElements(); I != E; I++) {
385 Value *ScalarValue = Builder.CreateExtractValue(Agg: ScalarInst, Idxs: I);
386 Value *VectorValue = Builder.CreateExtractValue(Agg: WideValue, Idxs: I);
387 VectorValue =
388 Builder.CreateInsertElement(Vec: VectorValue, NewElt: ScalarValue, Idx: LaneExpr);
389 WideValue = Builder.CreateInsertValue(Agg: WideValue, Val: VectorValue, Idxs: I);
390 }
391 } else {
392 WideValue = Builder.CreateInsertElement(Vec: WideValue, NewElt: ScalarInst, Idx: LaneExpr);
393 }
394 return WideValue;
395}
396
397BasicBlock *VPBasicBlock::createEmptyBasicBlock(VPTransformState &State) {
398 auto &CFG = State.CFG;
399 // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
400 // Pred stands for Predessor. Prev stands for Previous - last visited/created.
401 BasicBlock *PrevBB = CFG.PrevBB;
402 BasicBlock *NewBB = BasicBlock::Create(Context&: PrevBB->getContext(), Name: getName(),
403 Parent: PrevBB->getParent(), InsertBefore: CFG.ExitBB);
404 LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
405
406 return NewBB;
407}
408
409void VPBasicBlock::connectToPredecessors(VPTransformState &State) {
410 auto &CFG = State.CFG;
411 BasicBlock *NewBB = CFG.VPBB2IRBB[this];
412
413 // Register NewBB in its loop. In innermost loops its the same for all
414 // BB's.
415 Loop *ParentLoop = State.CurrentParentLoop;
416 // If this block has a sole successor that is an exit block or is an exit
417 // block itself then it needs adding to the same parent loop as the exit
418 // block.
419 VPBlockBase *SuccOrExitVPB = getSingleSuccessor();
420 SuccOrExitVPB = SuccOrExitVPB ? SuccOrExitVPB : this;
421 if (State.Plan->isExitBlock(VPBB: SuccOrExitVPB)) {
422 ParentLoop = State.LI->getLoopFor(
423 BB: cast<VPIRBasicBlock>(Val: SuccOrExitVPB)->getIRBasicBlock());
424 }
425
426 if (ParentLoop && !State.LI->getLoopFor(BB: NewBB))
427 ParentLoop->addBasicBlockToLoop(NewBB, LI&: *State.LI);
428
429 SmallVector<VPBlockBase *> Preds;
430 if (VPBlockUtils::isHeader(VPB: this, VPDT: State.VPDT)) {
431 // There's no block for the latch yet, connect to the preheader only.
432 Preds = {getPredecessors()[0]};
433 } else {
434 Preds = to_vector(Range&: getPredecessors());
435 }
436
437 // Hook up the new basic block to its predecessors.
438 for (VPBlockBase *PredVPBlock : Preds) {
439 VPBasicBlock *PredVPBB = PredVPBlock->getExitingBasicBlock();
440 auto &PredVPSuccessors = PredVPBB->getHierarchicalSuccessors();
441 assert(CFG.VPBB2IRBB.contains(PredVPBB) &&
442 "Predecessor basic-block not found building successor.");
443 BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
444 auto *PredBBTerminator = PredBB->getTerminator();
445 LLVM_DEBUG(dbgs() << "LV: draw edge from " << PredBB->getName() << '\n');
446
447 if (isa<UnreachableInst>(Val: PredBBTerminator)) {
448 assert(PredVPSuccessors.size() == 1 &&
449 "Predecessor ending w/o branch must have single successor.");
450 DebugLoc DL = PredBBTerminator->getDebugLoc();
451 PredBBTerminator->eraseFromParent();
452 auto *Br = UncondBrInst::Create(Target: NewBB, InsertBefore: PredBB);
453 Br->setDebugLoc(DL);
454 } else if (auto *UBI = dyn_cast<UncondBrInst>(Val: PredBBTerminator)) {
455 UBI->setSuccessor(NewBB);
456 } else {
457 // Set each forward successor here when it is created, excluding
458 // backedges. A backward successor is set when the branch is created.
459 // Branches to VPIRBasicBlocks must have the same successors in VPlan as
460 // in the original IR, except when the predecessor is the entry block.
461 // This enables including SCEV and memory runtime check blocks in VPlan.
462 // TODO: Remove exception by modeling the terminator of entry block using
463 // BranchOnCond.
464 unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
465 auto *TermBr = cast<CondBrInst>(Val: PredBBTerminator);
466 assert((!TermBr->getSuccessor(idx) ||
467 (isa<VPIRBasicBlock>(this) &&
468 (TermBr->getSuccessor(idx) == NewBB ||
469 PredVPBlock == getPlan()->getEntry()))) &&
470 "Trying to reset an existing successor block.");
471 TermBr->setSuccessor(idx, NewSucc: NewBB);
472 }
473 CFG.DTU.applyUpdates(Updates: {{DominatorTree::Insert, PredBB, NewBB}});
474 }
475}
476
477void VPIRBasicBlock::execute(VPTransformState *State) {
478 assert(getHierarchicalSuccessors().size() <= 2 &&
479 "VPIRBasicBlock can have at most two successors at the moment!");
480 // Move completely disconnected blocks to their final position.
481 if (IRBB->hasNPredecessors(N: 0) && succ_begin(BB: IRBB) == succ_end(BB: IRBB))
482 IRBB->moveAfter(MovePos: State->CFG.PrevBB);
483 State->Builder.SetInsertPoint(IRBB->getTerminator());
484 State->CFG.PrevBB = IRBB;
485 State->CFG.VPBB2IRBB[this] = IRBB;
486 executeRecipes(State, BB: IRBB);
487 // Create a branch instruction to terminate IRBB if one was not created yet
488 // and is needed.
489 if (getSingleSuccessor() && isa<UnreachableInst>(Val: IRBB->getTerminator())) {
490 auto *Br = State->Builder.CreateBr(Dest: IRBB);
491 Br->setOperand(i_nocapture: 0, Val_nocapture: nullptr);
492 IRBB->getTerminator()->eraseFromParent();
493 } else {
494 assert((getNumSuccessors() == 0 ||
495 isa<UncondBrInst, CondBrInst>(IRBB->getTerminator())) &&
496 "other blocks must be terminated by a branch");
497 }
498
499 connectToPredecessors(State&: *State);
500}
501
502VPIRBasicBlock *VPIRBasicBlock::clone() {
503 auto *NewBlock = getPlan()->createEmptyVPIRBasicBlock(IRBB);
504 for (VPRecipeBase &R : Recipes)
505 NewBlock->appendRecipe(Recipe: R.clone());
506 return NewBlock;
507}
508
509void VPBasicBlock::execute(VPTransformState *State) {
510 if (VPBlockUtils::isHeader(VPB: this, VPDT: State->VPDT)) {
511 // Create and register the new vector loop.
512 Loop *PrevParentLoop = State->CurrentParentLoop;
513 State->CurrentParentLoop = State->LI->AllocateLoop();
514
515 // Insert the new loop into the loop nest and register the new basic blocks
516 // before calling any utilities such as SCEV that require valid LoopInfo.
517 if (PrevParentLoop)
518 PrevParentLoop->addChildLoop(NewChild: State->CurrentParentLoop);
519 else
520 State->LI->addTopLevelLoop(New: State->CurrentParentLoop);
521 }
522
523 // 1. Create an IR basic block.
524 BasicBlock *NewBB = createEmptyBasicBlock(State&: *State);
525
526 State->Builder.SetInsertPoint(NewBB);
527 // Temporarily terminate with unreachable until CFG is rewired.
528 UnreachableInst *Terminator = State->Builder.CreateUnreachable();
529 State->Builder.SetInsertPoint(Terminator);
530
531 State->CFG.PrevBB = NewBB;
532 State->CFG.VPBB2IRBB[this] = NewBB;
533 connectToPredecessors(State&: *State);
534
535 // 2. Fill the IR basic block with IR instructions.
536 executeRecipes(State, BB: NewBB);
537
538 // If this block is a latch, update CurrentParentLoop.
539 if (VPBlockUtils::isLatch(VPB: this, VPDT: State->VPDT))
540 State->CurrentParentLoop = State->CurrentParentLoop->getParentLoop();
541}
542
543VPBasicBlock *VPBasicBlock::clone() {
544 auto *NewBlock = getPlan()->createVPBasicBlock(Name: getName());
545 for (VPRecipeBase &R : *this)
546 NewBlock->appendRecipe(Recipe: R.clone());
547 return NewBlock;
548}
549
550void VPBasicBlock::executeRecipes(VPTransformState *State, BasicBlock *BB) {
551 LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB: " << getName()
552 << " in BB: " << BB->getName() << '\n');
553
554 State->CFG.PrevVPBB = this;
555
556 for (VPRecipeBase &Recipe : Recipes) {
557 State->setDebugLocFrom(Recipe.getDebugLoc());
558 Recipe.execute(State&: *State);
559 }
560
561 LLVM_DEBUG(dbgs() << "LV: filled BB: " << *BB);
562}
563
564VPBasicBlock *VPBasicBlock::splitAt(iterator SplitAt) {
565 assert((SplitAt == end() || SplitAt->getParent() == this) &&
566 "can only split at a position in the same block");
567
568 // Create new empty block after the block to split.
569 auto *SplitBlock = getPlan()->createVPBasicBlock(Name: getName() + ".split");
570 VPBlockUtils::insertBlockAfter(NewBlock: SplitBlock, BlockPtr: this);
571
572 // If this is the exiting block, make the split the new exiting block.
573 auto *ParentRegion = getParent();
574 if (ParentRegion && ParentRegion->getExiting() == this)
575 ParentRegion->setExiting(SplitBlock);
576
577 // Finally, move the recipes starting at SplitAt to new block.
578 for (VPRecipeBase &ToMove :
579 make_early_inc_range(Range: make_range(x: SplitAt, y: this->end())))
580 ToMove.moveBefore(BB&: *SplitBlock, I: SplitBlock->end());
581
582 return SplitBlock;
583}
584
585/// Return the enclosing loop region for region \p P. The templated version is
586/// used to support both const and non-const block arguments.
587template <typename T> static T *getEnclosingLoopRegionForRegion(T *P) {
588 if (P && P->isReplicator()) {
589 P = P->getParent();
590 // Multiple loop regions can be nested, but replicate regions can only be
591 // nested inside a loop region or must be outside any other region.
592 assert((!P || !P->isReplicator()) && "unexpected nested replicate regions");
593 }
594 return P;
595}
596
597VPRegionBlock *VPBasicBlock::getEnclosingLoopRegion() {
598 return getEnclosingLoopRegionForRegion(P: getParent());
599}
600
601const VPRegionBlock *VPBasicBlock::getEnclosingLoopRegion() const {
602 return getEnclosingLoopRegionForRegion(P: getParent());
603}
604
605static bool hasConditionalTerminator(const VPBasicBlock *VPBB) {
606 if (VPBB->empty()) {
607 assert(
608 VPBB->getNumSuccessors() < 2 &&
609 "block with multiple successors doesn't have a recipe as terminator");
610 return false;
611 }
612
613 const VPRecipeBase *R = &VPBB->back();
614 [[maybe_unused]] bool IsSwitch =
615 isa<VPInstruction>(Val: R) &&
616 cast<VPInstruction>(Val: R)->getOpcode() == Instruction::Switch;
617 [[maybe_unused]] bool IsBranchOnTwoConds = match(V: R, P: m_BranchOnTwoConds());
618 [[maybe_unused]] bool IsCondBranch =
619 isa<VPBranchOnMaskRecipe>(Val: R) ||
620 match(V: R, P: m_CombineOr(Ps: m_BranchOnCond(), Ps: m_BranchOnCount()));
621 if (VPBB->getNumSuccessors() == 2 ||
622 (VPBB->isExiting() && !VPBB->getParent()->isReplicator())) {
623 assert((IsCondBranch || IsSwitch || IsBranchOnTwoConds) &&
624 "block with multiple successors not terminated by "
625 "conditional branch nor switch recipe");
626
627 return true;
628 }
629
630 if (VPBB->getNumSuccessors() > 2) {
631 assert((IsSwitch || IsBranchOnTwoConds) &&
632 "block with more than 2 successors not terminated by a switch or "
633 "branch-on-two-conds recipe");
634 return true;
635 }
636
637 assert(
638 !IsCondBranch && !IsBranchOnTwoConds &&
639 "block with 0 or 1 successors terminated by conditional branch recipe");
640 return false;
641}
642
643VPRecipeBase *VPBasicBlock::getTerminator() {
644 if (hasConditionalTerminator(VPBB: this))
645 return &back();
646 return nullptr;
647}
648
649const VPRecipeBase *VPBasicBlock::getTerminator() const {
650 if (hasConditionalTerminator(VPBB: this))
651 return &back();
652 return nullptr;
653}
654
655bool VPBasicBlock::isExiting() const {
656 return getParent() && getParent()->getExitingBasicBlock() == this;
657}
658
659#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
660void VPBlockBase::print(raw_ostream &O) const {
661 VPSlotTracker SlotTracker(getPlan());
662 print(O, "", SlotTracker);
663}
664
665void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const {
666 if (!hasSuccessors()) {
667 O << Indent << "No successors\n";
668 } else {
669 O << Indent << "Successor(s): ";
670 ListSeparator LS;
671 for (auto *Succ : getSuccessors())
672 O << LS << Succ->getName();
673 O << '\n';
674 }
675}
676
677void VPBasicBlock::print(raw_ostream &O, const Twine &Indent,
678 VPSlotTracker &SlotTracker) const {
679 O << Indent << getName() << ":\n";
680
681 auto RecipeIndent = Indent + " ";
682 for (const VPRecipeBase &Recipe : *this) {
683 Recipe.print(O, RecipeIndent, SlotTracker);
684 O << '\n';
685 }
686
687 printSuccessors(O, Indent);
688}
689#endif
690
691std::pair<VPBlockBase *, VPBlockBase *>
692VPBlockUtils::cloneFrom(VPBlockBase *Entry) {
693 DenseMap<VPBlockBase *, VPBlockBase *> Old2NewVPBlocks;
694 VPBlockBase *Exiting = nullptr;
695 bool InRegion = Entry->getParent();
696 // First, clone blocks reachable from Entry.
697 for (VPBlockBase *BB : vp_depth_first_shallow(G: Entry)) {
698 VPBlockBase *NewBB = BB->clone();
699 Old2NewVPBlocks[BB] = NewBB;
700 if (InRegion && BB->getNumSuccessors() == 0) {
701 assert(!Exiting && "Multiple exiting blocks?");
702 Exiting = BB;
703 }
704 }
705 assert((!InRegion || Exiting) && "regions must have a single exiting block");
706
707 // Second, update the predecessors & successors of the cloned blocks.
708 for (VPBlockBase *BB : vp_depth_first_shallow(G: Entry)) {
709 VPBlockBase *NewBB = Old2NewVPBlocks[BB];
710 SmallVector<VPBlockBase *> NewPreds;
711 for (VPBlockBase *Pred : BB->getPredecessors()) {
712 NewPreds.push_back(Elt: Old2NewVPBlocks[Pred]);
713 }
714 NewBB->setPredecessors(NewPreds);
715 SmallVector<VPBlockBase *> NewSuccs;
716 for (VPBlockBase *Succ : BB->successors()) {
717 NewSuccs.push_back(Elt: Old2NewVPBlocks[Succ]);
718 }
719 NewBB->setSuccessors(NewSuccs);
720 }
721
722#if !defined(NDEBUG)
723 // Verify that the order of predecessors and successors matches in the cloned
724 // version.
725 for (const auto &[OldBB, NewBB] :
726 zip(vp_depth_first_shallow(Entry),
727 vp_depth_first_shallow(Old2NewVPBlocks[Entry]))) {
728 for (const auto &[OldPred, NewPred] :
729 zip(OldBB->getPredecessors(), NewBB->getPredecessors()))
730 assert(NewPred == Old2NewVPBlocks[OldPred] && "Different predecessors");
731
732 for (const auto &[OldSucc, NewSucc] :
733 zip(OldBB->successors(), NewBB->successors()))
734 assert(NewSucc == Old2NewVPBlocks[OldSucc] && "Different successors");
735 }
736#endif
737
738 return std::make_pair(x&: Old2NewVPBlocks[Entry],
739 y: Exiting ? Old2NewVPBlocks[Exiting] : nullptr);
740}
741
742VPRegionBlock *VPRegionBlock::clone() {
743 const auto &[NewEntry, NewExiting] = VPBlockUtils::cloneFrom(Entry: getEntry());
744 VPlan &Plan = *getPlan();
745 VPRegionValue *CanIV = getCanonicalIV();
746 VPRegionBlock *NewRegion =
747 CanIV ? Plan.createLoopRegion(CanIVTy: CanIV->getType(), DL: CanIV->getDebugLoc(),
748 Name: getName(), Entry: NewEntry, Exiting: NewExiting)
749 : Plan.createReplicateRegion(Entry: NewEntry, Exiting: NewExiting, Name: getName());
750
751 if (getHeaderMask())
752 NewRegion->createHeaderMask();
753
754 for (VPBlockBase *Block : vp_depth_first_shallow(G: NewEntry))
755 Block->setParent(NewRegion);
756 return NewRegion;
757}
758
759void VPRegionBlock::execute(VPTransformState *State) {
760 llvm_unreachable("regions must get dissolved before ::execute");
761}
762
763InstructionCost VPBasicBlock::cost(ElementCount VF, VPCostContext &Ctx) {
764 InstructionCost Cost = 0;
765 for (VPRecipeBase &R : Recipes)
766 Cost += R.cost(VF, Ctx);
767 return Cost;
768}
769
770const VPBasicBlock *VPBasicBlock::getCFGPredecessor(unsigned Idx) const {
771 const VPBlockBase *Pred = nullptr;
772 if (hasPredecessors()) {
773 Pred = getPredecessors()[Idx];
774 } else {
775 auto *Region = getParent();
776 assert(Region && !Region->isReplicator() && Region->getEntry() == this &&
777 "must be in the entry block of a non-replicate region");
778 assert(Idx < 2 && Region->getNumPredecessors() == 1 &&
779 "loop region has a single predecessor (preheader), its entry block "
780 "has 2 incoming blocks");
781
782 // Idx == 0 selects the predecessor of the region, Idx == 1 selects the
783 // region itself whose exiting block feeds the phi across the backedge.
784 Pred = Idx == 0 ? Region->getSinglePredecessor() : Region;
785 }
786 return Pred->getExitingBasicBlock();
787}
788
789InstructionCost VPRegionBlock::cost(ElementCount VF, VPCostContext &Ctx) {
790 if (!isReplicator()) {
791 // Neglect the cost of canonical IV, matching the legacy cost model.
792 InstructionCost Cost = 0;
793 for (VPBlockBase *Block : vp_depth_first_shallow(G: getEntry()))
794 Cost += Block->cost(VF, Ctx);
795 InstructionCost BackedgeCost =
796 ForceTargetInstructionCost.getNumOccurrences()
797 ? InstructionCost(ForceTargetInstructionCost)
798 : Ctx.TTI.getCFInstrCost(Opcode: Instruction::UncondBr, CostKind: Ctx.CostKind);
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())
810 return InstructionCost::getInvalid();
811
812 // Compute and return the cost of the conditionally executed recipes.
813 assert(VF.isVector() && "Can only compute vector cost at the moment.");
814 VPBasicBlock *Then = cast<VPBasicBlock>(Val: getEntry()->getSuccessors()[0]);
815 return Then->cost(VF, Ctx);
816}
817
818#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
819void VPRegionBlock::print(raw_ostream &O, const Twine &Indent,
820 VPSlotTracker &SlotTracker) const {
821 O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {";
822 auto NewIndent = Indent + " ";
823 if (auto *CanIV = getCanonicalIV()) {
824 O << '\n';
825 CanIV->print(O, SlotTracker);
826 O << " = CANONICAL-IV\n";
827 }
828 if (auto *HdrMask = getUsedHeaderMask()) {
829 HdrMask->print(O, SlotTracker);
830 O << " = HEADER-MASK\n";
831 }
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
842void VPRegionBlock::dissolveToCFGLoop() {
843 auto *Header = cast<VPBasicBlock>(Val: getEntry());
844 auto *ExitingLatch = cast<VPBasicBlock>(Val: getExiting());
845 auto *CanIV = getCanonicalIV();
846 if (!CanIV->user_empty()) {
847 VPlan &Plan = *getPlan();
848 auto *Zero = Plan.getZero(Ty: CanIV->getType());
849 DebugLoc DL = CanIV->getDebugLoc();
850 VPInstruction *CanIVInc = getOrCreateCanonicalIVIncrement();
851 VPBuilder HeaderBuilder(Header, Header->begin());
852 auto *ScalarR =
853 HeaderBuilder.createScalarPhi(IncomingValues: {Zero, CanIVInc}, DL, Name: "index");
854 CanIV->replaceAllUsesWith(New: ScalarR);
855 }
856
857 VPBlockBase *Preheader = getSinglePredecessor();
858 VPBlockUtils::disconnectBlocks(From: Preheader, To: this);
859
860 for (VPBlockBase *VPB : vp_depth_first_shallow(G: Entry))
861 VPB->setParent(getParent());
862
863 VPBlockUtils::connectBlocks(From: Preheader, To: Header);
864 VPBlockUtils::transferSuccessors(Old: this, New: ExitingLatch);
865 VPBlockUtils::connectBlocks(From: ExitingLatch, To: Header);
866}
867
868VPInstruction *VPRegionBlock::getOrCreateCanonicalIVIncrement() {
869 // TODO: Represent the increment as VPRegionValue as well.
870 VPRegionValue *CanIV = getCanonicalIV();
871 assert(CanIV && "Expected a canonical IV");
872
873 if (auto *Inc = vputils::findCanonicalIVIncrement(Plan&: *getPlan()))
874 return Inc;
875
876 assert(!getPlan()->getVFxUF().isMaterialized() &&
877 "VFxUF can be used only before it is materialized.");
878 auto *ExitingLatch = cast<VPBasicBlock>(Val: getExiting());
879 return VPBuilder(ExitingLatch->getTerminator())
880 .createOverflowingOp(Opcode: Instruction::Add, Operands: {CanIV, &getPlan()->getVFxUF()},
881 WrapFlags: {hasCanonicalIVNUW(), /* HasNSW */ false},
882 DL: CanIV->getDebugLoc(), Name: "index.next");
883}
884
885VPlan::VPlan(Loop *L, Type *IdxTy)
886 : VectorTripCount(IdxTy), VF(IdxTy), UF(IdxTy), VFxUF(IdxTy) {
887 setEntry(createVPIRBasicBlock(IRBB: L->getLoopPreheader()));
888 ScalarHeader = createVPIRBasicBlock(IRBB: L->getHeader());
889
890 SmallVector<BasicBlock *> IRExitBlocks;
891 L->getUniqueExitBlocks(ExitBlocks&: IRExitBlocks);
892 for (BasicBlock *EB : IRExitBlocks)
893 ExitBlocks.push_back(Elt: createVPIRBasicBlock(IRBB: EB));
894}
895
896VPlan::~VPlan() {
897 VPSymbolicValue DummyValue(nullptr);
898
899 // Redirect all recipe operands to DummyValue before deleting blocks.
900 for (VPBasicBlock *VPBB :
901 VPBlockUtils::blocksOnly<VPBasicBlock>(Range&: CreatedBlocks))
902 for (VPRecipeBase &R : *VPBB)
903 for (unsigned I = 0, E = R.getNumOperands(); I != E; I++)
904 R.setOperand(I, New: &DummyValue);
905
906 for (auto *VPB : CreatedBlocks)
907 delete VPB;
908 for (VPValue *VPV : getLiveIns())
909 delete VPV;
910 delete BackedgeTakenCount;
911}
912
913bool VPlan::isExitBlock(VPBlockBase *VPBB) {
914 return is_contained(Range&: ExitBlocks, Element: VPBB);
915}
916
917/// To make RUN_VPLAN_PASS print final VPlan.
918static void printFinalVPlan(VPlan &) {}
919
920/// Generate the code inside the preheader and body of the vectorized loop.
921/// Assumes a single pre-header basic-block was created for this. Introduce
922/// additional basic-blocks as needed, and fill them all.
923void VPlan::execute(VPTransformState *State) {
924 assert(none_of(vp_depth_first_shallow(getEntry()), IsaPred<VPRegionBlock>) &&
925 "all region blocks must be dissolved before ::execute");
926
927 // Initialize CFG state.
928 State->CFG.PrevVPBB = nullptr;
929 State->CFG.ExitBB = State->CFG.PrevBB->getSingleSuccessor();
930
931 // Update VPDominatorTree since VPBasicBlock may be removed after State was
932 // constructed.
933 State->VPDT.recalculate(Func&: *this);
934
935 // Disconnect VectorPreHeader from ExitBB in both the CFG and DT.
936 BasicBlock *VectorPreHeader = State->CFG.PrevBB;
937 cast<UncondBrInst>(Val: VectorPreHeader->getTerminator())->setSuccessor(nullptr);
938 State->CFG.DTU.applyUpdates(
939 Updates: {{DominatorTree::Delete, VectorPreHeader, State->CFG.ExitBB}});
940
941 LLVM_DEBUG(dbgs() << "Executing best plan with VF=" << State->VF
942 << ", UF=" << getConcreteUF() << '\n');
943 setName("Final VPlan");
944 // TODO: RUN_VPLAN_PASS/VPlanTransforms::runPass should automatically dump
945 // VPlans after some specific stages when "-debug" is specified, but that
946 // hasn't been implemented yet. For now, just do both:
947 LLVM_DEBUG(dump());
948 RUN_VPLAN_PASS(printFinalVPlan, *this);
949
950 BasicBlock *ScalarPh = State->CFG.ExitBB;
951 VPBasicBlock *ScalarPhVPBB = getScalarPreheader();
952 if (ScalarPhVPBB) {
953 // Disconnect scalar preheader and scalar header, as the dominator tree edge
954 // will be updated as part of VPlan execution. This allows keeping the DTU
955 // logic generic during VPlan execution.
956 State->CFG.DTU.applyUpdates(
957 Updates: {{DominatorTree::Delete, ScalarPh, ScalarPh->getSingleSuccessor()}});
958 }
959 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> RPOT(
960 Entry);
961 // Generate code for the VPlan, in parts of the vector skeleton, loop body and
962 // successor blocks including the middle, exit and scalar preheader blocks.
963 for (VPBlockBase *Block : RPOT)
964 Block->execute(State);
965
966 if (hasEarlyExit()) {
967 // Fix up LoopInfo for extra dispatch blocks when vectorizing loops with
968 // early exits. For dispatch blocks, we need to find the smallest common
969 // loop of all successors that are in a loop. Note: we only need to update
970 // loop info for blocks after the middle block, but there is no easy way to
971 // get those at this point.
972 for (VPBlockBase *VPB : reverse(C&: RPOT)) {
973 auto *VPBB = dyn_cast<VPBasicBlock>(Val: VPB);
974 if (!VPBB || isa<VPIRBasicBlock>(Val: VPBB))
975 continue;
976 BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB];
977 Loop *L = State->LI->getLoopFor(BB);
978 if (!L || any_of(Range: successors(BB),
979 P: [L](BasicBlock *Succ) { return L->contains(BB: Succ); }))
980 continue;
981 // Find the innermost loop containing all successors that are in a loop.
982 // Successors not in any loop don't constrain the target loop.
983 Loop *Target = nullptr;
984 for (BasicBlock *Succ : successors(BB)) {
985 Loop *SuccLoop = State->LI->getLoopFor(BB: Succ);
986 if (!SuccLoop)
987 continue;
988 if (!Target)
989 Target = SuccLoop;
990 else
991 Target = State->LI->getSmallestCommonLoop(A: Target, B: SuccLoop);
992 }
993 State->LI->removeBlock(BB);
994 if (Target)
995 Target->addBasicBlockToLoop(NewBB: BB, LI&: *State->LI);
996 }
997 }
998
999 // If the original loop is unreachable, delete it and all its blocks.
1000 if (!ScalarPhVPBB) {
1001 // DeleteDeadBlocks will remove single-entry phis. Remove them from the exit
1002 // VPIRBBs in VPlan as well, otherwise we would retain references to deleted
1003 // IR instructions.
1004 for (VPIRBasicBlock *EB : getExitBlocks()) {
1005 for (VPRecipeBase &R : make_early_inc_range(Range: EB->phis())) {
1006 if (R.getNumOperands() == 1)
1007 R.eraseFromParent();
1008 }
1009 }
1010
1011 Loop *OrigLoop =
1012 State->LI->getLoopFor(BB: getScalarHeader()->getIRBasicBlock());
1013 auto Blocks = OrigLoop->getBlocksVector();
1014 Blocks.push_back(x: ScalarPh);
1015 while (!OrigLoop->isInnermost())
1016 State->LI->erase(L: *OrigLoop->begin());
1017 State->LI->erase(L: OrigLoop);
1018 for (auto *BB : Blocks)
1019 State->LI->removeBlock(BB);
1020 DeleteDeadBlocks(BBs: Blocks, DTU: &State->CFG.DTU);
1021 }
1022
1023 State->CFG.DTU.flush();
1024
1025 // Fix the latch (backedge) value of all header phis in all loop headers.
1026 for (VPBlockBase *VPB : vp_depth_first_shallow(G: getEntry())) {
1027 if (!VPBlockUtils::isHeader(VPB, VPDT: State->VPDT))
1028 continue;
1029 auto *Header = cast<VPBasicBlock>(Val: VPB);
1030 auto *LatchVPBB = cast<VPBasicBlock>(Val: Header->getPredecessors()[1]);
1031 BasicBlock *VectorLatchBB = State->CFG.VPBB2IRBB[LatchVPBB];
1032
1033 for (VPRecipeBase &R : Header->phis()) {
1034 auto *PhiR = cast<VPSingleDefRecipe>(Val: &R);
1035 bool NeedsScalar =
1036 isa<VPPhi>(Val: PhiR) || (isa<VPReductionPHIRecipe>(Val: PhiR) &&
1037 cast<VPReductionPHIRecipe>(Val: PhiR)->isInLoop());
1038
1039 Value *Phi = State->get(Def: PhiR, NeedsScalar);
1040 Value *Val = State->get(Def: PhiR->getOperand(N: 1), NeedsScalar);
1041 cast<PHINode>(Val: Phi)->addIncoming(V: Val, BB: VectorLatchBB);
1042 }
1043 }
1044}
1045
1046InstructionCost VPlan::cost(ElementCount VF, VPCostContext &Ctx) {
1047 // For now only return the cost of the vector loop region, ignoring any other
1048 // blocks, like the preheader or middle blocks, expect for checking them for
1049 // recipes with invalid costs.
1050 InstructionCost Cost = getVectorLoopRegion()->cost(VF, Ctx);
1051
1052 // If the cost of the loop region is invalid or any recipe in the skeleton
1053 // outside loop regions are invalid return an invalid cost.
1054 if (!Cost.isValid() || any_of(Range: VPBlockUtils::blocksOnly<VPBasicBlock>(
1055 Range: vp_depth_first_shallow(G: getEntry())),
1056 P: [&VF, &Ctx](VPBasicBlock *VPBB) {
1057 return !VPBB->cost(VF, Ctx).isValid();
1058 }))
1059 return InstructionCost::getInvalid();
1060
1061 return Cost;
1062}
1063
1064VPRegionBlock *VPlan::getVectorLoopRegion() {
1065 // TODO: Cache if possible.
1066 for (VPBlockBase *B : vp_depth_first_shallow(G: getEntry()))
1067 if (auto *R = dyn_cast<VPRegionBlock>(Val: B))
1068 return R->isReplicator() ? nullptr : R;
1069 return nullptr;
1070}
1071
1072const VPRegionBlock *VPlan::getVectorLoopRegion() const {
1073 for (const VPBlockBase *B : vp_depth_first_shallow(G: getEntry()))
1074 if (auto *R = dyn_cast<VPRegionBlock>(Val: B))
1075 return R->isReplicator() ? nullptr : R;
1076 return nullptr;
1077}
1078
1079bool VPlan::isOuterLoop() const {
1080 const VPRegionBlock *LoopRegion = getVectorLoopRegion();
1081 assert(LoopRegion && "expected a vector loop region");
1082 return any_of(Range: VPBlockUtils::blocksOnly<const VPRegionBlock>(
1083 Range: vp_depth_first_shallow(G: LoopRegion->getEntry())),
1084 P: [](const VPRegionBlock *R) { return !R->isReplicator(); });
1085}
1086
1087#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1088void VPlan::printLiveIns(raw_ostream &O) const {
1089 VPSlotTracker SlotTracker(this);
1090
1091 if (!VF.user_empty()) {
1092 O << "\nLive-in ";
1093 VF.printAsOperand(O, SlotTracker);
1094 O << " = VF";
1095 }
1096
1097 if (!UF.user_empty()) {
1098 O << "\nLive-in ";
1099 UF.printAsOperand(O, SlotTracker);
1100 O << " = UF";
1101 }
1102
1103 if (!VFxUF.user_empty()) {
1104 O << "\nLive-in ";
1105 VFxUF.printAsOperand(O, SlotTracker);
1106 O << " = VF * UF";
1107 }
1108
1109 if (!VectorTripCount.user_empty()) {
1110 O << "\nLive-in ";
1111 VectorTripCount.printAsOperand(O, SlotTracker);
1112 O << " = vector-trip-count";
1113 }
1114
1115 if (BackedgeTakenCount && !BackedgeTakenCount->user_empty()) {
1116 O << "\nLive-in ";
1117 BackedgeTakenCount->printAsOperand(O, SlotTracker);
1118 O << " = backedge-taken count";
1119 }
1120
1121 O << "\n";
1122 if (TripCount && !TripCount->user_empty()) {
1123 if (isa<VPIRValue>(TripCount))
1124 O << "Live-in ";
1125 TripCount->printAsOperand(O, SlotTracker);
1126 O << " = original trip-count";
1127 O << "\n";
1128 }
1129}
1130
1131LLVM_DUMP_METHOD
1132void VPlan::print(raw_ostream &O) const {
1133 VPSlotTracker SlotTracker(this);
1134
1135 O << "VPlan '" << getName() << "' {";
1136
1137 printLiveIns(O);
1138
1139 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<const VPBlockBase *>>
1140 RPOT(getEntry());
1141 for (const VPBlockBase *Block : RPOT) {
1142 O << '\n';
1143 Block->print(O, "", SlotTracker);
1144 }
1145
1146 O << "}\n";
1147}
1148
1149std::string VPlan::getName() const {
1150 std::string Out;
1151 raw_string_ostream RSO(Out);
1152 RSO << Name << " for ";
1153 if (!VFs.empty()) {
1154 RSO << "VF={" << VFs[0];
1155 for (ElementCount VF : drop_begin(VFs))
1156 RSO << "," << VF;
1157 RSO << "},";
1158 }
1159
1160 if (UFs.empty()) {
1161 RSO << "UF>=1";
1162 } else {
1163 RSO << "UF={" << UFs[0];
1164 for (unsigned UF : drop_begin(UFs))
1165 RSO << "," << UF;
1166 RSO << "}";
1167 }
1168
1169 return Out;
1170}
1171
1172LLVM_DUMP_METHOD
1173void VPlan::printDOT(raw_ostream &O) const {
1174 VPlanPrinter Printer(O, *this);
1175 Printer.dump();
1176}
1177
1178LLVM_DUMP_METHOD
1179void VPlan::dump() const { print(dbgs()); }
1180#endif
1181
1182static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry,
1183 DenseMap<VPValue *, VPValue *> &Old2NewVPValues) {
1184 // Update the operands of all cloned recipes starting at NewEntry. This
1185 // traverses all reachable blocks. This is done in two steps, to handle cycles
1186 // in PHI recipes.
1187 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>>
1188 OldDeepRPOT(Entry);
1189 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>>
1190 NewDeepRPOT(NewEntry);
1191 // First, collect all mappings from old to new VPValues defined by cloned
1192 // recipes.
1193 for (const auto &[OldBB, NewBB] :
1194 zip(t: VPBlockUtils::blocksOnly<VPBasicBlock>(Range&: OldDeepRPOT),
1195 u: VPBlockUtils::blocksOnly<VPBasicBlock>(Range&: NewDeepRPOT))) {
1196 assert(OldBB->getRecipeList().size() == NewBB->getRecipeList().size() &&
1197 "blocks must have the same number of recipes");
1198 for (const auto &[OldR, NewR] : zip(t&: *OldBB, u&: *NewBB)) {
1199 assert(OldR.getNumOperands() == NewR.getNumOperands() &&
1200 "recipes must have the same number of operands");
1201 assert(OldR.getNumDefinedValues() == NewR.getNumDefinedValues() &&
1202 "recipes must define the same number of operands");
1203 for (const auto &[OldV, NewV] :
1204 zip(t: OldR.definedValues(), u: NewR.definedValues()))
1205 Old2NewVPValues[OldV] = NewV;
1206 }
1207 }
1208
1209 // Update all operands to use cloned VPValues.
1210 for (VPBasicBlock *NewBB :
1211 VPBlockUtils::blocksOnly<VPBasicBlock>(Range&: NewDeepRPOT)) {
1212 for (VPRecipeBase &NewR : *NewBB)
1213 for (unsigned I = 0, E = NewR.getNumOperands(); I != E; ++I) {
1214 VPValue *NewOp = Old2NewVPValues.lookup(Val: NewR.getOperand(N: I));
1215 NewR.setOperand(I, New: NewOp);
1216 }
1217 }
1218}
1219
1220VPlan *VPlan::duplicate() {
1221 unsigned NumBlocksBeforeCloning = CreatedBlocks.size();
1222 // Clone blocks.
1223 const auto &[NewEntry, __] = VPBlockUtils::cloneFrom(Entry);
1224
1225 BasicBlock *ScalarHeaderIRBB = getScalarHeader()->getIRBasicBlock();
1226 VPIRBasicBlock *NewScalarHeader = nullptr;
1227 if (getScalarHeader()->hasPredecessors()) {
1228 NewScalarHeader = cast<VPIRBasicBlock>(Val: *find_if(
1229 Range: vp_depth_first_shallow(G: NewEntry), P: [ScalarHeaderIRBB](VPBlockBase *VPB) {
1230 auto *VPIRBB = dyn_cast<VPIRBasicBlock>(Val: VPB);
1231 return VPIRBB && VPIRBB->getIRBasicBlock() == ScalarHeaderIRBB;
1232 }));
1233 } else {
1234 NewScalarHeader = createVPIRBasicBlock(IRBB: ScalarHeaderIRBB);
1235 }
1236 // Create VPlan, clone live-ins and remap operands in the cloned blocks.
1237 auto *NewPlan =
1238 new VPlan(cast<VPBasicBlock>(Val: NewEntry), NewScalarHeader, getIndexType());
1239 DenseMap<VPValue *, VPValue *> Old2NewVPValues;
1240 for (VPIRValue *OldLiveIn : getLiveIns())
1241 Old2NewVPValues[OldLiveIn] = NewPlan->getOrAddLiveIn(V: OldLiveIn);
1242
1243 if (auto *TripCountIRV = dyn_cast_or_null<VPIRValue>(Val: TripCount))
1244 Old2NewVPValues[TripCountIRV] = NewPlan->getOrAddLiveIn(V: TripCountIRV);
1245 // else NewTripCount will be created and inserted into Old2NewVPValues when
1246 // TripCount is cloned. In any case NewPlan->TripCount is updated below.
1247
1248 assert(none_of(Old2NewVPValues.keys(), IsaPred<VPSymbolicValue>) &&
1249 "All VPSymbolicValues must be handled below");
1250
1251 if (auto *LoopRegion = getVectorLoopRegion()) {
1252 auto *NewLoopRegion = NewPlan->getVectorLoopRegion();
1253 for (auto [Old, New] : zip_equal(t: LoopRegion->getRegionValues(),
1254 u: NewLoopRegion->getRegionValues())) {
1255 Old2NewVPValues[Old] = New;
1256 if (Old->isMaterialized())
1257 New->markMaterialized();
1258 }
1259 }
1260
1261 if (BackedgeTakenCount)
1262 NewPlan->BackedgeTakenCount =
1263 new VPSymbolicValue(BackedgeTakenCount->getType());
1264
1265 // Map and propagate materialized state for symbolic values.
1266 for (auto [OldSV, NewSV] :
1267 {std::pair{&VectorTripCount, &NewPlan->VectorTripCount},
1268 {&VF, &NewPlan->VF},
1269 {&UF, &NewPlan->UF},
1270 {&VFxUF, &NewPlan->VFxUF},
1271 {BackedgeTakenCount, NewPlan->BackedgeTakenCount}}) {
1272 if (!OldSV)
1273 continue;
1274 Old2NewVPValues[OldSV] = NewSV;
1275 if (OldSV->isMaterialized())
1276 NewSV->markMaterialized();
1277 }
1278
1279 remapOperands(Entry, NewEntry, Old2NewVPValues);
1280
1281 // Initialize remaining fields of cloned VPlan.
1282 NewPlan->VFs = VFs;
1283 NewPlan->UFs = UFs;
1284 // TODO: Adjust names.
1285 NewPlan->Name = Name;
1286 if (TripCount) {
1287 assert(Old2NewVPValues.contains(TripCount) &&
1288 "TripCount must have been added to Old2NewVPValues");
1289 NewPlan->TripCount = Old2NewVPValues[TripCount];
1290 }
1291
1292 // Transfer all cloned blocks (the second half of all current blocks) from
1293 // current to new VPlan.
1294 unsigned NumBlocksAfterCloning = CreatedBlocks.size();
1295 for (unsigned I :
1296 seq<unsigned>(Begin: NumBlocksBeforeCloning, End: NumBlocksAfterCloning))
1297 NewPlan->CreatedBlocks.push_back(Elt: this->CreatedBlocks[I]);
1298 CreatedBlocks.truncate(N: NumBlocksBeforeCloning);
1299
1300 // Update ExitBlocks of the new plan.
1301 for (VPBlockBase *VPB : NewPlan->CreatedBlocks) {
1302 if (VPB->getNumSuccessors() == 0 && isa<VPIRBasicBlock>(Val: VPB) &&
1303 VPB != NewScalarHeader)
1304 NewPlan->ExitBlocks.push_back(Elt: cast<VPIRBasicBlock>(Val: VPB));
1305 }
1306
1307 return NewPlan;
1308}
1309
1310VPIRBasicBlock *VPlan::createEmptyVPIRBasicBlock(BasicBlock *IRBB) {
1311 auto *VPIRBB = new VPIRBasicBlock(IRBB);
1312 CreatedBlocks.push_back(Elt: VPIRBB);
1313 return VPIRBB;
1314}
1315
1316VPIRBasicBlock *VPlan::createVPIRBasicBlock(BasicBlock *IRBB) {
1317 auto *VPIRBB = createEmptyVPIRBasicBlock(IRBB);
1318 for (Instruction &I :
1319 make_range(x: IRBB->begin(), y: IRBB->getTerminator()->getIterator()))
1320 VPIRBB->appendRecipe(Recipe: VPIRInstruction::create(I));
1321 return VPIRBB;
1322}
1323
1324#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1325
1326Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
1327 return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
1328 Twine(getOrCreateBID(Block));
1329}
1330
1331void VPlanPrinter::dump() {
1332 Depth = 1;
1333 bumpIndent(0);
1334 OS << "digraph VPlan {\n";
1335 OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
1336 if (!Plan.getName().empty())
1337 OS << "\\n" << DOT::EscapeString(Plan.getName());
1338
1339 {
1340 // Print live-ins.
1341 std::string Str;
1342 raw_string_ostream SS(Str);
1343 Plan.printLiveIns(SS);
1344 SmallVector<StringRef, 0> Lines;
1345 StringRef(Str).rtrim('\n').split(Lines, "\n");
1346 for (auto Line : Lines)
1347 OS << DOT::EscapeString(Line.str()) << "\\n";
1348 }
1349
1350 OS << "\"]\n";
1351 OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
1352 OS << "edge [fontname=Courier, fontsize=30]\n";
1353 OS << "compound=true\n";
1354
1355 for (const VPBlockBase *Block : vp_depth_first_shallow(Plan.getEntry()))
1356 dumpBlock(Block);
1357
1358 OS << "}\n";
1359}
1360
1361void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
1362 if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
1363 dumpBasicBlock(BasicBlock);
1364 else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1365 dumpRegion(Region);
1366 else
1367 llvm_unreachable("Unsupported kind of VPBlock.");
1368}
1369
1370void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
1371 bool Hidden, const Twine &Label) {
1372 // Due to "dot" we print an edge between two regions as an edge between the
1373 // exiting basic block and the entry basic of the respective regions.
1374 const VPBlockBase *Tail = From->getExitingBasicBlock();
1375 const VPBlockBase *Head = To->getEntryBasicBlock();
1376 OS << Indent << getUID(Tail) << " -> " << getUID(Head);
1377 OS << " [ label=\"" << Label << '\"';
1378 if (Tail != From)
1379 OS << " ltail=" << getUID(From);
1380 if (Head != To)
1381 OS << " lhead=" << getUID(To);
1382 if (Hidden)
1383 OS << "; splines=none";
1384 OS << "]\n";
1385}
1386
1387void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
1388 auto &Successors = Block->getSuccessors();
1389 if (Successors.size() == 1)
1390 drawEdge(Block, Successors.front(), false, "");
1391 else if (Successors.size() == 2) {
1392 drawEdge(Block, Successors.front(), false, "T");
1393 drawEdge(Block, Successors.back(), false, "F");
1394 } else {
1395 unsigned SuccessorNumber = 0;
1396 for (auto *Successor : Successors)
1397 drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
1398 }
1399}
1400
1401void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
1402 // Implement dot-formatted dump by performing plain-text dump into the
1403 // temporary storage followed by some post-processing.
1404 OS << Indent << getUID(BasicBlock) << " [label =\n";
1405 bumpIndent(1);
1406 std::string Str;
1407 raw_string_ostream SS(Str);
1408 // Use no indentation as we need to wrap the lines into quotes ourselves.
1409 BasicBlock->print(SS, "", SlotTracker);
1410
1411 // We need to process each line of the output separately, so split
1412 // single-string plain-text dump.
1413 SmallVector<StringRef, 0> Lines;
1414 StringRef(Str).rtrim('\n').split(Lines, "\n");
1415
1416 auto EmitLine = [&](StringRef Line, StringRef Suffix) {
1417 OS << Indent << '"' << DOT::EscapeString(Line.str()) << "\\l\"" << Suffix;
1418 };
1419
1420 // Don't need the "+" after the last line.
1421 for (auto Line : make_range(Lines.begin(), Lines.end() - 1))
1422 EmitLine(Line, " +\n");
1423 EmitLine(Lines.back(), "\n");
1424
1425 bumpIndent(-1);
1426 OS << Indent << "]\n";
1427
1428 dumpEdges(BasicBlock);
1429}
1430
1431void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
1432 OS << Indent << "subgraph " << getUID(Region) << " {\n";
1433 bumpIndent(1);
1434 OS << Indent << "fontname=Courier\n"
1435 << Indent << "label=\""
1436 << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
1437 << DOT::EscapeString(Region->getName()) << "\"\n";
1438
1439 if (auto *CanIV = Region->getCanonicalIV()) {
1440 OS << Indent << "\"";
1441 std::string Op;
1442 raw_string_ostream S(Op);
1443 CanIV->printAsOperand(S, SlotTracker);
1444 OS << DOT::EscapeString(Op);
1445 OS << " = CANONICAL-IV\"\n";
1446 }
1447
1448 // Dump the blocks of the region.
1449 assert(Region->getEntry() && "Region contains no inner blocks.");
1450 for (const VPBlockBase *Block : vp_depth_first_shallow(Region->getEntry()))
1451 dumpBlock(Block);
1452 bumpIndent(-1);
1453 OS << Indent << "}\n";
1454 dumpEdges(Region);
1455}
1456
1457#endif
1458
1459/// Returns true if there is a vector loop region and \p VPV is defined in a
1460/// loop region.
1461static bool isDefinedInsideLoopRegions(const VPValue *VPV) {
1462 if (isa<VPRegionValue>(Val: VPV))
1463 return true;
1464 const VPRecipeBase *DefR = VPV->getDefiningRecipe();
1465 return DefR && (!DefR->getParent()->getPlan()->getVectorLoopRegion() ||
1466 DefR->getParent()->getEnclosingLoopRegion());
1467}
1468
1469bool VPValue::isDefinedOutsideLoopRegions() const {
1470 return !isDefinedInsideLoopRegions(VPV: this);
1471}
1472void VPValue::replaceAllUsesWith(VPValue *New) {
1473 replaceUsesWithIf(New, ShouldReplace: [](VPUser &, unsigned) { return true; });
1474 if (auto *SV = dyn_cast<VPSymbolicValue>(Val: this))
1475 SV->markMaterialized();
1476}
1477
1478void VPValue::replaceUsesWithIf(
1479 VPValue *New,
1480 llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace) {
1481 assertNotMaterialized();
1482 // Note that this early exit is required for correctness; the implementation
1483 // below relies on the number of users for this VPValue to decrease, which
1484 // isn't the case if this == New.
1485 if (this == New)
1486 return;
1487
1488 for (unsigned J = 0; J < getNumUsers();) {
1489 VPUser *User = Users[J];
1490 bool RemovedUser = false;
1491 for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
1492 if (User->getOperand(N: I) != this || !ShouldReplace(*User, I))
1493 continue;
1494
1495 RemovedUser = true;
1496 User->setOperand(I, New);
1497 }
1498 // If a user got removed after updating the current user, the next user to
1499 // update will be moved to the current position, so we only need to
1500 // increment the index if the number of users did not change.
1501 if (!RemovedUser)
1502 J++;
1503 }
1504}
1505
1506void VPUser::replaceUsesOfWith(VPValue *From, VPValue *To) {
1507 for (unsigned Idx = 0; Idx != getNumOperands(); ++Idx) {
1508 if (getOperand(N: Idx) == From)
1509 setOperand(I: Idx, New: To);
1510 }
1511}
1512
1513#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1514void VPValue::printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const {
1515 OS << Tracker.getOrCreateName(this);
1516}
1517
1518void VPUser::printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const {
1519 interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) {
1520 Op->printAsOperand(O, SlotTracker);
1521 });
1522}
1523#endif
1524
1525void VPSlotTracker::assignName(const VPValue *V) {
1526 assert(!VPValue2Name.contains(V) && "VPValue already has a name!");
1527 auto *UV = V->getUnderlyingValue();
1528 auto *VPI = dyn_cast_or_null<VPInstruction>(Val: V);
1529 if (!UV && !(VPI && !VPI->getName().empty())) {
1530 VPValue2Name[V] = (Twine("vp<%") + Twine(NextSlot) + ">").str();
1531 NextSlot++;
1532 return;
1533 }
1534
1535 // Use the name of the underlying Value, wrapped in "ir<>", and versioned by
1536 // appending ".Number" to the name if there are multiple uses.
1537 std::string Name;
1538 if (UV)
1539 Name = getName(V: UV);
1540 else
1541 Name = VPI->getName();
1542
1543 assert(!Name.empty() && "Name cannot be empty.");
1544 StringRef Prefix = UV ? "ir<" : "vp<%";
1545 std::string BaseName = (Twine(Prefix) + Name + Twine(">")).str();
1546
1547 // First assign the base name for V.
1548 const auto &[A, _] = VPValue2Name.try_emplace(Key: V, Args&: BaseName);
1549 // Integer or FP constants with different types will result in the same string
1550 // due to stripping types.
1551 if (isa<VPIRValue>(Val: V) && isa<ConstantInt, ConstantFP>(Val: UV))
1552 return;
1553
1554 // If it is already used by C > 0 other VPValues, increase the version counter
1555 // C and use it for V.
1556 const auto &[C, UseInserted] = BaseName2Version.try_emplace(Key: BaseName, Args: 0);
1557 if (!UseInserted) {
1558 C->second++;
1559 A->second = (BaseName + Twine(".") + Twine(C->second)).str();
1560 }
1561}
1562
1563void VPSlotTracker::assignNames(const VPlan &Plan) {
1564 if (!Plan.VF.user_empty())
1565 assignName(V: &Plan.VF);
1566 if (!Plan.UF.user_empty())
1567 assignName(V: &Plan.UF);
1568 if (!Plan.VFxUF.user_empty())
1569 assignName(V: &Plan.VFxUF);
1570 assignName(V: &Plan.VectorTripCount);
1571 if (Plan.BackedgeTakenCount)
1572 assignName(V: Plan.BackedgeTakenCount);
1573 for (VPValue *LI : Plan.getLiveIns())
1574 assignName(V: LI);
1575
1576 ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<const VPBlockBase *>>
1577 RPOT(VPBlockDeepTraversalWrapper<const VPBlockBase *>(Plan.getEntry()));
1578 for (const VPBlockBase *VPB : RPOT) {
1579 if (auto *VPBB = dyn_cast<VPBasicBlock>(Val: VPB))
1580 assignNames(VPBB);
1581 else
1582 for (auto *RV : cast<VPRegionBlock>(Val: VPB)->getRegionValues())
1583 assignName(V: RV);
1584 }
1585}
1586
1587void VPSlotTracker::assignNames(const VPBasicBlock *VPBB) {
1588 for (const VPRecipeBase &Recipe : *VPBB)
1589 for (VPValue *Def : Recipe.definedValues())
1590 assignName(V: Def);
1591}
1592
1593std::string VPSlotTracker::getName(const Value *V) {
1594 std::string Name;
1595 raw_string_ostream S(Name);
1596 if (V->hasName() || !isa<Instruction>(Val: V)) {
1597 V->printAsOperand(O&: S, PrintType: false);
1598 return Name;
1599 }
1600
1601 if (!MST) {
1602 // Lazily create the ModuleSlotTracker when we first hit an unnamed
1603 // instruction.
1604 auto *I = cast<Instruction>(Val: V);
1605 // This check is required to support unit tests with incomplete IR.
1606 if (I->getParent()) {
1607 MST = std::make_unique<ModuleSlotTracker>(args: I->getModule());
1608 MST->incorporateFunction(F: *I->getFunction());
1609 } else {
1610 MST = std::make_unique<ModuleSlotTracker>(args: nullptr);
1611 }
1612 }
1613 V->printAsOperand(O&: S, PrintType: false, MST&: *MST);
1614 return Name;
1615}
1616
1617std::string VPSlotTracker::getOrCreateName(const VPValue *V) const {
1618 std::string Name = VPValue2Name.lookup(Val: V);
1619 if (!Name.empty())
1620 return Name;
1621
1622 // If no name was assigned, no VPlan was provided when creating the slot
1623 // tracker or it is not reachable from the provided VPlan. This can happen,
1624 // e.g. when trying to print a recipe that has not been inserted into a VPlan
1625 // in a debugger.
1626 // TODO: Update VPSlotTracker constructor to assign names to recipes &
1627 // VPValues not associated with a VPlan, instead of constructing names ad-hoc
1628 // here.
1629 const VPRecipeBase *DefR = V->getDefiningRecipe();
1630 (void)DefR;
1631 assert((!DefR || !DefR->getParent() || !DefR->getParent()->getPlan()) &&
1632 "VPValue defined by a recipe in a VPlan?");
1633
1634 // Use the underlying value's name, if there is one.
1635 if (auto *UV = V->getUnderlyingValue()) {
1636 std::string Name;
1637 raw_string_ostream S(Name);
1638 UV->printAsOperand(O&: S, PrintType: false);
1639 return (Twine("ir<") + Name + ">").str();
1640 }
1641
1642 return "<badref>";
1643}
1644
1645VPInstruction *VPBuilder::createAnyOfReduction(VPValue *ChainOp,
1646 VPValue *TrueVal,
1647 VPValue *FalseVal, DebugLoc DL) {
1648 assert(ChainOp->getScalarType()->isIntegerTy(1) &&
1649 "ChainOp must be i1 for AnyOf reduction");
1650 VPIRFlags Flags(RecurKind::Or, /*IsOrdered=*/false, /*IsInLoop=*/false,
1651 FastMathFlags());
1652 auto *OrReduce =
1653 createNaryOp(Opcode: VPInstruction::ComputeReductionResult, Operands: {ChainOp}, Flags, DL);
1654 auto *Freeze = createNaryOp(Opcode: Instruction::Freeze, Operands: {OrReduce}, DL);
1655 return createSelect(Cond: Freeze, TrueVal, FalseVal, DL, Name: "rdx.select");
1656}
1657
1658bool LoopVectorizationPlanner::getDecisionAndClampRange(
1659 const std::function<bool(ElementCount)> &Predicate, VFRange &Range) {
1660 assert(!Range.isEmpty() && "Trying to test an empty VF range.");
1661 bool PredicateAtRangeStart = Predicate(Range.Start);
1662
1663 for (ElementCount TmpVF : VFRange(Range.Start * 2, Range.End))
1664 if (Predicate(TmpVF) != PredicateAtRangeStart) {
1665 Range.End = TmpVF;
1666 break;
1667 }
1668
1669 return PredicateAtRangeStart;
1670}
1671
1672VPSingleDefRecipe *
1673VPBuilder::createConsecutiveVectorPointer(VPValue *Ptr, Type *SourceElementTy,
1674 bool Reverse, DebugLoc DL) {
1675 VPlan &Plan = getPlan();
1676 GEPNoWrapFlags Flags = vputils::getGEPFlagsForPtr(Ptr);
1677 if (Reverse) {
1678 // When folding the tail, we may compute an address that we don't in the
1679 // original scalar loop: drop the GEP no-wrap flags in this case. Otherwise
1680 // preserve existing flags without no-unsigned-wrap, as we will emit
1681 // negative indices.
1682 GEPNoWrapFlags ReverseFlags = Plan.hasTailFolded()
1683 ? GEPNoWrapFlags::none()
1684 : Flags.withoutNoUnsignedWrap();
1685 return tryInsertInstruction(R: new VPVectorEndPointerRecipe(
1686 Ptr, &Plan.getVF(), SourceElementTy, /*Stride=*/-1, ReverseFlags, DL));
1687 }
1688 Type *StrideTy = Plan.getDataLayout().getIndexType(PtrTy: Ptr->getScalarType());
1689 VPValue *StrideOne = Plan.getConstantInt(Ty: StrideTy, Val: 1);
1690 return createVectorPointer(Ptr, SourceElementTy, Stride: StrideOne, GEPFlags: Flags, DL);
1691}
1692
1693VPlan &LoopVectorizationPlanner::getPlanFor(ElementCount VF) const {
1694 assert(count_if(VPlans,
1695 [VF](const VPlanPtr &Plan) { return Plan->hasVF(VF); }) ==
1696 1 &&
1697 "Multiple VPlans for VF.");
1698
1699 for (const VPlanPtr &Plan : VPlans) {
1700 if (Plan->hasVF(VF))
1701 return *Plan.get();
1702 }
1703 llvm_unreachable("No plan found!");
1704}
1705
1706static void addRuntimeUnrollDisableMetaData(Loop *L) {
1707 SmallVector<Metadata *, 4> MDs;
1708 // Reserve first location for self reference to the LoopID metadata node.
1709 MDs.push_back(Elt: nullptr);
1710 bool IsUnrollMetadata = false;
1711 MDNode *LoopID = L->getLoopID();
1712 if (LoopID) {
1713 // First find existing loop unrolling disable metadata.
1714 for (unsigned I = 1, IE = LoopID->getNumOperands(); I < IE; ++I) {
1715 auto *MD = dyn_cast<MDNode>(Val: LoopID->getOperand(I));
1716 if (MD) {
1717 const auto *S = dyn_cast<MDString>(Val: MD->getOperand(I: 0));
1718 if (!S)
1719 continue;
1720 if (S->getString().starts_with(Prefix: "llvm.loop.unroll.runtime.disable"))
1721 continue;
1722 IsUnrollMetadata =
1723 S->getString().starts_with(Prefix: "llvm.loop.unroll.disable");
1724 }
1725 MDs.push_back(Elt: LoopID->getOperand(I));
1726 }
1727 }
1728
1729 if (!IsUnrollMetadata) {
1730 // Add runtime unroll disable metadata.
1731 LLVMContext &Context = L->getHeader()->getContext();
1732 SmallVector<Metadata *, 1> DisableOperands;
1733 DisableOperands.push_back(
1734 Elt: MDString::get(Context, Str: "llvm.loop.unroll.runtime.disable"));
1735 MDNode *DisableNode = MDNode::get(Context, MDs: DisableOperands);
1736 MDs.push_back(Elt: DisableNode);
1737 MDNode *NewLoopID = MDNode::get(Context, MDs);
1738 // Set operand 0 to refer to the loop id itself.
1739 NewLoopID->replaceOperandWith(I: 0, New: NewLoopID);
1740 L->setLoopID(NewLoopID);
1741 }
1742}
1743
1744void LoopVectorizationPlanner::updateLoopMetadataAndProfileInfo(
1745 Loop *VectorLoop, VPBasicBlock *HeaderVPBB, const VPlan &Plan,
1746 bool VectorizingEpilogue, MDNode *OrigLoopID,
1747 std::optional<unsigned> OrigAverageTripCount,
1748 unsigned OrigLoopInvocationWeight, unsigned EstimatedVFxUF,
1749 bool DisableRuntimeUnroll) {
1750 // Update the metadata of the scalar loop. Skip the update when vectorizing
1751 // the epilogue loop to ensure it is updated only once. Also skip the update
1752 // when the scalar loop became unreachable.
1753 auto *ScalarPH = Plan.getScalarPreheader();
1754 if (ScalarPH && !VectorizingEpilogue) {
1755 std::optional<MDNode *> RemainderLoopID =
1756 makeFollowupLoopID(OrigLoopID, FollowupAttrs: {LLVMLoopVectorizeFollowupAll,
1757 LLVMLoopVectorizeFollowupEpilogue});
1758 if (RemainderLoopID) {
1759 OrigLoop->setLoopID(*RemainderLoopID);
1760 } else {
1761 if (DisableRuntimeUnroll)
1762 addRuntimeUnrollDisableMetaData(L: OrigLoop);
1763
1764 LoopVectorizeHints Hints(OrigLoop, /*InterleaveOnlyWhenForced*/ false,
1765 *ORE);
1766 Hints.setAlreadyVectorized();
1767 }
1768 }
1769 // Tag the scalar remainder so downstream passes (e.g. the unroller and
1770 // WarnMissedTransforms) can produce more informative remarks. Only emit
1771 // when remarks are enabled.
1772 if (ORE->enabled() && ScalarPH && ScalarPH->hasPredecessors())
1773 OrigLoop->addIntLoopAttribute(Name: "llvm.loop.vectorize.epilogue", Value: 1);
1774
1775 if (!VectorLoop)
1776 return;
1777
1778 if (std::optional<MDNode *> VectorizedLoopID = makeFollowupLoopID(
1779 OrigLoopID, FollowupAttrs: {LLVMLoopVectorizeFollowupAll,
1780 LLVMLoopVectorizeFollowupVectorized})) {
1781 VectorLoop->setLoopID(*VectorizedLoopID);
1782 } else {
1783 // Keep all loop hints from the original loop on the vector loop (we'll
1784 // replace the vectorizer-specific hints below).
1785 if (OrigLoopID)
1786 VectorLoop->setLoopID(OrigLoopID);
1787
1788 if (!VectorizingEpilogue) {
1789 LoopVectorizeHints Hints(VectorLoop, /*InterleaveOnlyWhenForced*/ false,
1790 *ORE);
1791 Hints.setAlreadyVectorized();
1792 }
1793 }
1794 // Tag the vector loop body so downstream passes can identify it. Only
1795 // emit when remarks are enabled.
1796 if (ORE->enabled())
1797 VectorLoop->addIntLoopAttribute(Name: "llvm.loop.vectorize.body", Value: 1);
1798 TargetTransformInfo::UnrollingPreferences UP;
1799 TTI.getUnrollingPreferences(L: VectorLoop, *PSE.getSE(), UP, ORE);
1800 if (!UP.UnrollVectorizedLoop || VectorizingEpilogue)
1801 addRuntimeUnrollDisableMetaData(L: VectorLoop);
1802
1803 // Set/update profile weights for the vector and remainder loops as original
1804 // loop iterations are now distributed among them. Note that original loop
1805 // becomes the scalar remainder loop after vectorization.
1806 //
1807 // For cases like foldTailByMasking() and requiresScalarEpiloque() we may
1808 // end up getting slightly roughened result but that should be OK since
1809 // profile is not inherently precise anyway. Note also possible bypass of
1810 // vector code caused by legality checks is ignored, assigning all the weight
1811 // to the vector loop, optimistically.
1812 //
1813 // For scalable vectorization we can't know at compile time how many
1814 // iterations of the loop are handled in one vector iteration, so instead
1815 // use the value of vscale used for tuning.
1816 unsigned AverageVectorTripCount = 0;
1817 unsigned RemainderAverageTripCount = 0;
1818 auto EC = VectorLoop->getLoopPreheader()->getParent()->getEntryCount();
1819 auto IsProfiled = EC && *EC != 0;
1820 if (!OrigAverageTripCount) {
1821 if (!IsProfiled)
1822 return;
1823 auto &SE = *PSE.getSE();
1824 AverageVectorTripCount = SE.getSmallConstantTripCount(L: VectorLoop);
1825 if (ProfcheckDisableMetadataFixes || !AverageVectorTripCount)
1826 return;
1827 if (ScalarPH)
1828 RemainderAverageTripCount =
1829 SE.getSmallConstantTripCount(L: OrigLoop) % EstimatedVFxUF;
1830 // Setting to 1 should be sufficient to generate the correct branch weights.
1831 OrigLoopInvocationWeight = 1;
1832 } else {
1833 // Calculate number of iterations in unrolled loop.
1834 AverageVectorTripCount = *OrigAverageTripCount / EstimatedVFxUF;
1835 // Calculate number of iterations for remainder loop.
1836 RemainderAverageTripCount = *OrigAverageTripCount % EstimatedVFxUF;
1837 }
1838 if (HeaderVPBB) {
1839 setLoopEstimatedTripCount(L: VectorLoop, EstimatedTripCount: AverageVectorTripCount,
1840 EstimatedLoopInvocationWeight: OrigLoopInvocationWeight);
1841 }
1842
1843 if (ScalarPH) {
1844 setLoopEstimatedTripCount(L: OrigLoop, EstimatedTripCount: RemainderAverageTripCount,
1845 EstimatedLoopInvocationWeight: OrigLoopInvocationWeight);
1846 }
1847}
1848
1849#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1850void LoopVectorizationPlanner::printPlans(raw_ostream &O) {
1851 if (VPlans.empty()) {
1852 O << "LV: No VPlans built.\n";
1853 return;
1854 }
1855 for (const auto &Plan : VPlans)
1856 if (PrintVPlansInDotFormat)
1857 Plan->printDOT(O);
1858 else
1859 Plan->print(O);
1860}
1861#endif
1862
1863bool llvm::canConstantBeExtended(const APInt *C, Type *NarrowType,
1864 TTI::PartialReductionExtendKind ExtKind) {
1865 APInt TruncatedVal = C->trunc(width: NarrowType->getScalarSizeInBits());
1866 unsigned WideSize = C->getBitWidth();
1867 APInt ExtendedVal = ExtKind == TTI::PR_SignExtend
1868 ? TruncatedVal.sext(width: WideSize)
1869 : TruncatedVal.zext(width: WideSize);
1870 return ExtendedVal == *C;
1871}
1872
1873TargetTransformInfo::OperandValueInfo
1874VPCostContext::getOperandInfo(VPValue *V) const {
1875 if (auto *IRV = dyn_cast<VPIRValue>(Val: V))
1876 return TTI::getOperandInfo(V: IRV->getValue());
1877
1878 return {};
1879}
1880
1881InstructionCost VPCostContext::getScalarizationOverhead(
1882 Type *ResultTy, ArrayRef<const VPValue *> Operands, ElementCount VF,
1883 TTI::VectorInstrContext VIC, bool AlwaysIncludeReplicatingR) {
1884 if (VF.isScalar())
1885 return 0;
1886
1887 assert(!VF.isScalable() &&
1888 "Scalarization overhead not supported for scalable vectors");
1889
1890 InstructionCost ScalarizationCost = 0;
1891 // Compute the cost of scalarizing the result if needed.
1892 if (!ResultTy->isVoidTy()) {
1893 for (Type *VectorTy :
1894 to_vector(Range: getContainedTypes(Ty: toVectorizedTy(Ty: ResultTy, EC: VF)))) {
1895 ScalarizationCost += TTI.getScalarizationOverhead(
1896 Ty: cast<VectorType>(Val: VectorTy), DemandedElts: APInt::getAllOnes(numBits: VF.getFixedValue()),
1897 /*Insert=*/true, /*Extract=*/false, CostKind,
1898 /*ForPoisonSrc=*/true, VL: {}, VIC);
1899 }
1900 }
1901 // Compute the cost of scalarizing the operands, skipping ones that do not
1902 // require extraction/scalarization and do not incur any overhead.
1903 SmallPtrSet<const VPValue *, 4> UniqueOperands;
1904 SmallVector<Type *> Tys;
1905 for (auto *Op : Operands) {
1906 if (isa<VPIRValue>(Val: Op) ||
1907 (!AlwaysIncludeReplicatingR &&
1908 isa<VPReplicateRecipe, VPPredInstPHIRecipe>(Val: Op)) ||
1909 (isa<VPReplicateRecipe>(Val: Op) &&
1910 cast<VPReplicateRecipe>(Val: Op)->getOpcode() == Instruction::Load) ||
1911 !UniqueOperands.insert(Ptr: Op).second)
1912 continue;
1913 Tys.push_back(Elt: toVectorizedTy(Ty: Op->getScalarType(), EC: VF));
1914 }
1915 return ScalarizationCost +
1916 TTI.getOperandsScalarizationOverhead(Tys, CostKind, VIC);
1917}
1918
1919bool VPCostContext::useEmulatedMaskMemRefHack(const VPReplicateRecipe *R,
1920 ElementCount VF) {
1921 const Instruction *UI = R->getUnderlyingInstr();
1922 if (isa<LoadInst>(Val: UI))
1923 return true;
1924 assert(isa<StoreInst>(UI) && "R must either be a load or store");
1925
1926 if (!NumPredStores) {
1927 // Count the number of predicated stores in the VPlan, caching the result.
1928 // Only stores where scatter is not legal are counted, matching the legacy
1929 // cost model behavior.
1930 const VPlan &Plan = *R->getParent()->getPlan();
1931 NumPredStores = 0;
1932 for (const VPRegionBlock *VPRB :
1933 VPBlockUtils::blocksOnly<const VPRegionBlock>(
1934 Range: vp_depth_first_shallow(G: Plan.getVectorLoopRegion()->getEntry()))) {
1935 assert(VPRB->isReplicator() && "must only contain replicate regions");
1936 for (const VPBasicBlock *VPBB :
1937 VPBlockUtils::blocksOnly<const VPBasicBlock>(
1938 Range: vp_depth_first_shallow(G: VPRB->getEntry()))) {
1939 for (const VPRecipeBase &Recipe : *VPBB) {
1940 auto *RepR = dyn_cast<VPReplicateRecipe>(Val: &Recipe);
1941 if (!RepR)
1942 continue;
1943 if (!isa<StoreInst>(Val: RepR->getUnderlyingInstr()))
1944 continue;
1945 // Check if scatter is legal for this store. If so, don't count it.
1946 Type *Ty = RepR->getOperand(N: 0)->getScalarType();
1947 auto *VTy = VectorType::get(ElementType: Ty, EC: VF);
1948 const Align Alignment =
1949 getLoadStoreAlignment(I: RepR->getUnderlyingInstr());
1950 if (!TTI.isLegalMaskedScatter(DataType: VTy, Alignment))
1951 ++(*NumPredStores);
1952 }
1953 }
1954 }
1955 }
1956 return *NumPredStores > NumberOfStoresToPredicate;
1957}
1958
1959bool VPCostContext::isFreeScalarIntrinsic(Intrinsic::ID ID) {
1960 return is_contained(Set: {Intrinsic::assume, Intrinsic::lifetime_end,
1961 Intrinsic::lifetime_start, Intrinsic::sideeffect,
1962 Intrinsic::pseudoprobe,
1963 Intrinsic::experimental_noalias_scope_decl},
1964 Element: ID);
1965}
1966