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