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