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