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