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