xref: /llvm-project/llvm/lib/Transforms/Vectorize/VPlan.cpp (revision 2435dcd83a32c63aef91c82cb19b08604ba96b64)
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 "VPlanCFG.h"
21 #include "VPlanDominatorTree.h"
22 #include "VPlanPatternMatch.h"
23 #include "llvm/ADT/PostOrderIterator.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/StringExtras.h"
27 #include "llvm/ADT/Twine.h"
28 #include "llvm/Analysis/LoopInfo.h"
29 #include "llvm/IR/BasicBlock.h"
30 #include "llvm/IR/CFG.h"
31 #include "llvm/IR/IRBuilder.h"
32 #include "llvm/IR/Instruction.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/Type.h"
35 #include "llvm/IR/Value.h"
36 #include "llvm/Support/Casting.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/GenericDomTreeConstruction.h"
40 #include "llvm/Support/GraphWriter.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
43 #include "llvm/Transforms/Utils/LoopVersioning.h"
44 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
45 #include <cassert>
46 #include <string>
47 #include <vector>
48 
49 using namespace llvm;
50 using namespace llvm::VPlanPatternMatch;
51 
52 namespace llvm {
53 extern cl::opt<bool> EnableVPlanNativePath;
54 }
55 
56 #define DEBUG_TYPE "vplan"
57 
58 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
59 raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) {
60   const VPInstruction *Instr = dyn_cast<VPInstruction>(&V);
61   VPSlotTracker SlotTracker(
62       (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
63   V.print(OS, SlotTracker);
64   return OS;
65 }
66 #endif
67 
68 Value *VPLane::getAsRuntimeExpr(IRBuilderBase &Builder,
69                                 const ElementCount &VF) const {
70   switch (LaneKind) {
71   case VPLane::Kind::ScalableLast:
72     // Lane = RuntimeVF - VF.getKnownMinValue() + Lane
73     return Builder.CreateSub(getRuntimeVF(Builder, Builder.getInt32Ty(), VF),
74                              Builder.getInt32(VF.getKnownMinValue() - Lane));
75   case VPLane::Kind::First:
76     return Builder.getInt32(Lane);
77   }
78   llvm_unreachable("Unknown lane kind");
79 }
80 
81 VPValue::VPValue(const unsigned char SC, Value *UV, VPDef *Def)
82     : SubclassID(SC), UnderlyingVal(UV), Def(Def) {
83   if (Def)
84     Def->addDefinedValue(this);
85 }
86 
87 VPValue::~VPValue() {
88   assert(Users.empty() && "trying to delete a VPValue with remaining users");
89   if (Def)
90     Def->removeDefinedValue(this);
91 }
92 
93 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
94 void VPValue::print(raw_ostream &OS, VPSlotTracker &SlotTracker) const {
95   if (const VPRecipeBase *R = dyn_cast_or_null<VPRecipeBase>(Def))
96     R->print(OS, "", SlotTracker);
97   else
98     printAsOperand(OS, SlotTracker);
99 }
100 
101 void VPValue::dump() const {
102   const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this->Def);
103   VPSlotTracker SlotTracker(
104       (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
105   print(dbgs(), SlotTracker);
106   dbgs() << "\n";
107 }
108 
109 void VPDef::dump() const {
110   const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this);
111   VPSlotTracker SlotTracker(
112       (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
113   print(dbgs(), "", SlotTracker);
114   dbgs() << "\n";
115 }
116 #endif
117 
118 VPRecipeBase *VPValue::getDefiningRecipe() {
119   return cast_or_null<VPRecipeBase>(Def);
120 }
121 
122 const VPRecipeBase *VPValue::getDefiningRecipe() const {
123   return cast_or_null<VPRecipeBase>(Def);
124 }
125 
126 // Get the top-most entry block of \p Start. This is the entry block of the
127 // containing VPlan. This function is templated to support both const and non-const blocks
128 template <typename T> static T *getPlanEntry(T *Start) {
129   T *Next = Start;
130   T *Current = Start;
131   while ((Next = Next->getParent()))
132     Current = Next;
133 
134   SmallSetVector<T *, 8> WorkList;
135   WorkList.insert(Current);
136 
137   for (unsigned i = 0; i < WorkList.size(); i++) {
138     T *Current = WorkList[i];
139     if (Current->getNumPredecessors() == 0)
140       return Current;
141     auto &Predecessors = Current->getPredecessors();
142     WorkList.insert(Predecessors.begin(), Predecessors.end());
143   }
144 
145   llvm_unreachable("VPlan without any entry node without predecessors");
146 }
147 
148 VPlan *VPBlockBase::getPlan() { return getPlanEntry(this)->Plan; }
149 
150 const VPlan *VPBlockBase::getPlan() const { return getPlanEntry(this)->Plan; }
151 
152 /// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
153 const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const {
154   const VPBlockBase *Block = this;
155   while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
156     Block = Region->getEntry();
157   return cast<VPBasicBlock>(Block);
158 }
159 
160 VPBasicBlock *VPBlockBase::getEntryBasicBlock() {
161   VPBlockBase *Block = this;
162   while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
163     Block = Region->getEntry();
164   return cast<VPBasicBlock>(Block);
165 }
166 
167 void VPBlockBase::setPlan(VPlan *ParentPlan) {
168   assert(
169       (ParentPlan->getEntry() == this || ParentPlan->getPreheader() == this) &&
170       "Can only set plan on its entry or preheader block.");
171   Plan = ParentPlan;
172 }
173 
174 /// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
175 const VPBasicBlock *VPBlockBase::getExitingBasicBlock() const {
176   const VPBlockBase *Block = this;
177   while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
178     Block = Region->getExiting();
179   return cast<VPBasicBlock>(Block);
180 }
181 
182 VPBasicBlock *VPBlockBase::getExitingBasicBlock() {
183   VPBlockBase *Block = this;
184   while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
185     Block = Region->getExiting();
186   return cast<VPBasicBlock>(Block);
187 }
188 
189 VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() {
190   if (!Successors.empty() || !Parent)
191     return this;
192   assert(Parent->getExiting() == this &&
193          "Block w/o successors not the exiting block of its parent.");
194   return Parent->getEnclosingBlockWithSuccessors();
195 }
196 
197 VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {
198   if (!Predecessors.empty() || !Parent)
199     return this;
200   assert(Parent->getEntry() == this &&
201          "Block w/o predecessors not the entry of its parent.");
202   return Parent->getEnclosingBlockWithPredecessors();
203 }
204 
205 void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
206   for (VPBlockBase *Block : to_vector(vp_depth_first_shallow(Entry)))
207     delete Block;
208 }
209 
210 VPBasicBlock::iterator VPBasicBlock::getFirstNonPhi() {
211   iterator It = begin();
212   while (It != end() && It->isPhi())
213     It++;
214   return It;
215 }
216 
217 VPTransformState::VPTransformState(ElementCount VF, unsigned UF, LoopInfo *LI,
218                                    DominatorTree *DT, IRBuilderBase &Builder,
219                                    InnerLoopVectorizer *ILV, VPlan *Plan,
220                                    LLVMContext &Ctx)
221     : VF(VF), UF(UF), LI(LI), DT(DT), Builder(Builder), ILV(ILV), Plan(Plan),
222       LVer(nullptr),
223       TypeAnalysis(Plan->getCanonicalIV()->getScalarType(), Ctx) {}
224 
225 Value *VPTransformState::get(VPValue *Def, const VPIteration &Instance) {
226   if (Def->isLiveIn())
227     return Def->getLiveInIRValue();
228 
229   if (hasScalarValue(Def, Instance)) {
230     return Data
231         .PerPartScalars[Def][Instance.Part][Instance.Lane.mapToCacheIndex(VF)];
232   }
233 
234   assert(hasVectorValue(Def, Instance.Part));
235   auto *VecPart = Data.PerPartOutput[Def][Instance.Part];
236   if (!VecPart->getType()->isVectorTy()) {
237     assert(Instance.Lane.isFirstLane() && "cannot get lane > 0 for scalar");
238     return VecPart;
239   }
240   // TODO: Cache created scalar values.
241   Value *Lane = Instance.Lane.getAsRuntimeExpr(Builder, VF);
242   auto *Extract = Builder.CreateExtractElement(VecPart, Lane);
243   // set(Def, Extract, Instance);
244   return Extract;
245 }
246 
247 Value *VPTransformState::get(VPValue *Def, unsigned Part, bool NeedsScalar) {
248   if (NeedsScalar) {
249     assert((VF.isScalar() || Def->isLiveIn() ||
250             (hasScalarValue(Def, VPIteration(Part, 0)) &&
251              Data.PerPartScalars[Def][Part].size() == 1)) &&
252            "Trying to access a single scalar per part but has multiple scalars "
253            "per part.");
254     return get(Def, VPIteration(Part, 0));
255   }
256 
257   // If Values have been set for this Def return the one relevant for \p Part.
258   if (hasVectorValue(Def, Part))
259     return Data.PerPartOutput[Def][Part];
260 
261   auto GetBroadcastInstrs = [this, Def](Value *V) {
262     bool SafeToHoist = Def->isDefinedOutsideVectorRegions();
263     if (VF.isScalar())
264       return V;
265     // Place the code for broadcasting invariant variables in the new preheader.
266     IRBuilder<>::InsertPointGuard Guard(Builder);
267     if (SafeToHoist) {
268       BasicBlock *LoopVectorPreHeader = CFG.VPBB2IRBB[cast<VPBasicBlock>(
269           Plan->getVectorLoopRegion()->getSinglePredecessor())];
270       if (LoopVectorPreHeader)
271         Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
272     }
273 
274     // Place the code for broadcasting invariant variables in the new preheader.
275     // Broadcast the scalar into all locations in the vector.
276     Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast");
277 
278     return Shuf;
279   };
280 
281   if (!hasScalarValue(Def, {Part, 0})) {
282     assert(Def->isLiveIn() && "expected a live-in");
283     if (Part != 0)
284       return get(Def, 0);
285     Value *IRV = Def->getLiveInIRValue();
286     Value *B = GetBroadcastInstrs(IRV);
287     set(Def, B, Part);
288     return B;
289   }
290 
291   Value *ScalarValue = get(Def, {Part, 0});
292   // If we aren't vectorizing, we can just copy the scalar map values over
293   // to the vector map.
294   if (VF.isScalar()) {
295     set(Def, ScalarValue, Part);
296     return ScalarValue;
297   }
298 
299   bool IsUniform = vputils::isUniformAfterVectorization(Def);
300 
301   unsigned LastLane = IsUniform ? 0 : VF.getKnownMinValue() - 1;
302   // Check if there is a scalar value for the selected lane.
303   if (!hasScalarValue(Def, {Part, LastLane})) {
304     // At the moment, VPWidenIntOrFpInductionRecipes, VPScalarIVStepsRecipes and
305     // VPExpandSCEVRecipes can also be uniform.
306     assert((isa<VPWidenIntOrFpInductionRecipe>(Def->getDefiningRecipe()) ||
307             isa<VPScalarIVStepsRecipe>(Def->getDefiningRecipe()) ||
308             isa<VPExpandSCEVRecipe>(Def->getDefiningRecipe())) &&
309            "unexpected recipe found to be invariant");
310     IsUniform = true;
311     LastLane = 0;
312   }
313 
314   auto *LastInst = cast<Instruction>(get(Def, {Part, LastLane}));
315   // Set the insert point after the last scalarized instruction or after the
316   // last PHI, if LastInst is a PHI. This ensures the insertelement sequence
317   // will directly follow the scalar definitions.
318   auto OldIP = Builder.saveIP();
319   auto NewIP =
320       isa<PHINode>(LastInst)
321           ? BasicBlock::iterator(LastInst->getParent()->getFirstNonPHI())
322           : std::next(BasicBlock::iterator(LastInst));
323   Builder.SetInsertPoint(&*NewIP);
324 
325   // However, if we are vectorizing, we need to construct the vector values.
326   // If the value is known to be uniform after vectorization, we can just
327   // broadcast the scalar value corresponding to lane zero for each unroll
328   // iteration. Otherwise, we construct the vector values using
329   // insertelement instructions. Since the resulting vectors are stored in
330   // State, we will only generate the insertelements once.
331   Value *VectorValue = nullptr;
332   if (IsUniform) {
333     VectorValue = GetBroadcastInstrs(ScalarValue);
334     set(Def, VectorValue, Part);
335   } else {
336     // Initialize packing with insertelements to start from undef.
337     assert(!VF.isScalable() && "VF is assumed to be non scalable.");
338     Value *Undef = PoisonValue::get(VectorType::get(LastInst->getType(), VF));
339     set(Def, Undef, Part);
340     for (unsigned Lane = 0; Lane < VF.getKnownMinValue(); ++Lane)
341       packScalarIntoVectorValue(Def, {Part, Lane});
342     VectorValue = get(Def, Part);
343   }
344   Builder.restoreIP(OldIP);
345   return VectorValue;
346 }
347 
348 BasicBlock *VPTransformState::CFGState::getPreheaderBBFor(VPRecipeBase *R) {
349   VPRegionBlock *LoopRegion = R->getParent()->getEnclosingLoopRegion();
350   return VPBB2IRBB[LoopRegion->getPreheaderVPBB()];
351 }
352 
353 void VPTransformState::addNewMetadata(Instruction *To,
354                                       const Instruction *Orig) {
355   // If the loop was versioned with memchecks, add the corresponding no-alias
356   // metadata.
357   if (LVer && (isa<LoadInst>(Orig) || isa<StoreInst>(Orig)))
358     LVer->annotateInstWithNoAlias(To, Orig);
359 }
360 
361 void VPTransformState::addMetadata(Instruction *To, Instruction *From) {
362   // No source instruction to transfer metadata from?
363   if (!From)
364     return;
365 
366   propagateMetadata(To, From);
367   addNewMetadata(To, From);
368 }
369 
370 void VPTransformState::addMetadata(ArrayRef<Value *> To, Instruction *From) {
371   // No source instruction to transfer metadata from?
372   if (!From)
373     return;
374 
375   for (Value *V : To) {
376     if (Instruction *I = dyn_cast<Instruction>(V))
377       addMetadata(I, From);
378   }
379 }
380 
381 void VPTransformState::setDebugLocFrom(DebugLoc DL) {
382   const DILocation *DIL = DL;
383   // When a FSDiscriminator is enabled, we don't need to add the multiply
384   // factors to the discriminators.
385   if (DIL &&
386       Builder.GetInsertBlock()
387           ->getParent()
388           ->shouldEmitDebugInfoForProfiling() &&
389       !EnableFSDiscriminator) {
390     // FIXME: For scalable vectors, assume vscale=1.
391     auto NewDIL =
392         DIL->cloneByMultiplyingDuplicationFactor(UF * VF.getKnownMinValue());
393     if (NewDIL)
394       Builder.SetCurrentDebugLocation(*NewDIL);
395     else
396       LLVM_DEBUG(dbgs() << "Failed to create new discriminator: "
397                         << DIL->getFilename() << " Line: " << DIL->getLine());
398   } else
399     Builder.SetCurrentDebugLocation(DIL);
400 }
401 
402 void VPTransformState::packScalarIntoVectorValue(VPValue *Def,
403                                                  const VPIteration &Instance) {
404   Value *ScalarInst = get(Def, Instance);
405   Value *VectorValue = get(Def, Instance.Part);
406   VectorValue = Builder.CreateInsertElement(
407       VectorValue, ScalarInst, Instance.Lane.getAsRuntimeExpr(Builder, VF));
408   set(Def, VectorValue, Instance.Part);
409 }
410 
411 BasicBlock *
412 VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
413   // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
414   // Pred stands for Predessor. Prev stands for Previous - last visited/created.
415   BasicBlock *PrevBB = CFG.PrevBB;
416   BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
417                                          PrevBB->getParent(), CFG.ExitBB);
418   LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
419 
420   // Hook up the new basic block to its predecessors.
421   for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
422     VPBasicBlock *PredVPBB = PredVPBlock->getExitingBasicBlock();
423     auto &PredVPSuccessors = PredVPBB->getHierarchicalSuccessors();
424     BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
425 
426     assert(PredBB && "Predecessor basic-block not found building successor.");
427     auto *PredBBTerminator = PredBB->getTerminator();
428     LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
429 
430     auto *TermBr = dyn_cast<BranchInst>(PredBBTerminator);
431     if (isa<UnreachableInst>(PredBBTerminator)) {
432       assert(PredVPSuccessors.size() == 1 &&
433              "Predecessor ending w/o branch must have single successor.");
434       DebugLoc DL = PredBBTerminator->getDebugLoc();
435       PredBBTerminator->eraseFromParent();
436       auto *Br = BranchInst::Create(NewBB, PredBB);
437       Br->setDebugLoc(DL);
438     } else if (TermBr && !TermBr->isConditional()) {
439       TermBr->setSuccessor(0, NewBB);
440     } else {
441       // Set each forward successor here when it is created, excluding
442       // backedges. A backward successor is set when the branch is created.
443       unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
444       assert(!TermBr->getSuccessor(idx) &&
445              "Trying to reset an existing successor block.");
446       TermBr->setSuccessor(idx, NewBB);
447     }
448   }
449   return NewBB;
450 }
451 
452 void VPBasicBlock::execute(VPTransformState *State) {
453   bool Replica = State->Instance && !State->Instance->isFirstIteration();
454   VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
455   VPBlockBase *SingleHPred = nullptr;
456   BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
457 
458   auto IsLoopRegion = [](VPBlockBase *BB) {
459     auto *R = dyn_cast<VPRegionBlock>(BB);
460     return R && !R->isReplicator();
461   };
462 
463   // 1. Create an IR basic block, or reuse the last one or ExitBB if possible.
464   if (getPlan()->getVectorLoopRegion()->getSingleSuccessor() == this) {
465     // ExitBB can be re-used for the exit block of the Plan.
466     NewBB = State->CFG.ExitBB;
467     State->CFG.PrevBB = NewBB;
468     State->Builder.SetInsertPoint(NewBB->getFirstNonPHI());
469 
470     // Update the branch instruction in the predecessor to branch to ExitBB.
471     VPBlockBase *PredVPB = getSingleHierarchicalPredecessor();
472     VPBasicBlock *ExitingVPBB = PredVPB->getExitingBasicBlock();
473     assert(PredVPB->getSingleSuccessor() == this &&
474            "predecessor must have the current block as only successor");
475     BasicBlock *ExitingBB = State->CFG.VPBB2IRBB[ExitingVPBB];
476     // The Exit block of a loop is always set to be successor 0 of the Exiting
477     // block.
478     cast<BranchInst>(ExitingBB->getTerminator())->setSuccessor(0, NewBB);
479   } else if (PrevVPBB && /* A */
480              !((SingleHPred = getSingleHierarchicalPredecessor()) &&
481                SingleHPred->getExitingBasicBlock() == PrevVPBB &&
482                PrevVPBB->getSingleHierarchicalSuccessor() &&
483                (SingleHPred->getParent() == getEnclosingLoopRegion() &&
484                 !IsLoopRegion(SingleHPred))) &&         /* B */
485              !(Replica && getPredecessors().empty())) { /* C */
486     // The last IR basic block is reused, as an optimization, in three cases:
487     // A. the first VPBB reuses the loop pre-header BB - when PrevVPBB is null;
488     // B. when the current VPBB has a single (hierarchical) predecessor which
489     //    is PrevVPBB and the latter has a single (hierarchical) successor which
490     //    both are in the same non-replicator region; and
491     // C. when the current VPBB is an entry of a region replica - where PrevVPBB
492     //    is the exiting VPBB of this region from a previous instance, or the
493     //    predecessor of this region.
494 
495     NewBB = createEmptyBasicBlock(State->CFG);
496     State->Builder.SetInsertPoint(NewBB);
497     // Temporarily terminate with unreachable until CFG is rewired.
498     UnreachableInst *Terminator = State->Builder.CreateUnreachable();
499     // Register NewBB in its loop. In innermost loops its the same for all
500     // BB's.
501     if (State->CurrentVectorLoop)
502       State->CurrentVectorLoop->addBasicBlockToLoop(NewBB, *State->LI);
503     State->Builder.SetInsertPoint(Terminator);
504     State->CFG.PrevBB = NewBB;
505   }
506 
507   // 2. Fill the IR basic block with IR instructions.
508   LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
509                     << " in BB:" << NewBB->getName() << '\n');
510 
511   State->CFG.VPBB2IRBB[this] = NewBB;
512   State->CFG.PrevVPBB = this;
513 
514   for (VPRecipeBase &Recipe : Recipes)
515     Recipe.execute(*State);
516 
517   LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
518 }
519 
520 void VPBasicBlock::dropAllReferences(VPValue *NewValue) {
521   for (VPRecipeBase &R : Recipes) {
522     for (auto *Def : R.definedValues())
523       Def->replaceAllUsesWith(NewValue);
524 
525     for (unsigned I = 0, E = R.getNumOperands(); I != E; I++)
526       R.setOperand(I, NewValue);
527   }
528 }
529 
530 VPBasicBlock *VPBasicBlock::splitAt(iterator SplitAt) {
531   assert((SplitAt == end() || SplitAt->getParent() == this) &&
532          "can only split at a position in the same block");
533 
534   SmallVector<VPBlockBase *, 2> Succs(successors());
535   // First, disconnect the current block from its successors.
536   for (VPBlockBase *Succ : Succs)
537     VPBlockUtils::disconnectBlocks(this, Succ);
538 
539   // Create new empty block after the block to split.
540   auto *SplitBlock = new VPBasicBlock(getName() + ".split");
541   VPBlockUtils::insertBlockAfter(SplitBlock, this);
542 
543   // Add successors for block to split to new block.
544   for (VPBlockBase *Succ : Succs)
545     VPBlockUtils::connectBlocks(SplitBlock, Succ);
546 
547   // Finally, move the recipes starting at SplitAt to new block.
548   for (VPRecipeBase &ToMove :
549        make_early_inc_range(make_range(SplitAt, this->end())))
550     ToMove.moveBefore(*SplitBlock, SplitBlock->end());
551 
552   return SplitBlock;
553 }
554 
555 VPRegionBlock *VPBasicBlock::getEnclosingLoopRegion() {
556   VPRegionBlock *P = getParent();
557   if (P && P->isReplicator()) {
558     P = P->getParent();
559     assert(!cast<VPRegionBlock>(P)->isReplicator() &&
560            "unexpected nested replicate regions");
561   }
562   return P;
563 }
564 
565 static bool hasConditionalTerminator(const VPBasicBlock *VPBB) {
566   if (VPBB->empty()) {
567     assert(
568         VPBB->getNumSuccessors() < 2 &&
569         "block with multiple successors doesn't have a recipe as terminator");
570     return false;
571   }
572 
573   const VPRecipeBase *R = &VPBB->back();
574   bool IsCondBranch = isa<VPBranchOnMaskRecipe>(R) ||
575                       match(R, m_BranchOnCond(m_VPValue())) ||
576                       match(R, m_BranchOnCount(m_VPValue(), m_VPValue()));
577   (void)IsCondBranch;
578 
579   if (VPBB->getNumSuccessors() >= 2 ||
580       (VPBB->isExiting() && !VPBB->getParent()->isReplicator())) {
581     assert(IsCondBranch && "block with multiple successors not terminated by "
582                            "conditional branch recipe");
583 
584     return true;
585   }
586 
587   assert(
588       !IsCondBranch &&
589       "block with 0 or 1 successors terminated by conditional branch recipe");
590   return false;
591 }
592 
593 VPRecipeBase *VPBasicBlock::getTerminator() {
594   if (hasConditionalTerminator(this))
595     return &back();
596   return nullptr;
597 }
598 
599 const VPRecipeBase *VPBasicBlock::getTerminator() const {
600   if (hasConditionalTerminator(this))
601     return &back();
602   return nullptr;
603 }
604 
605 bool VPBasicBlock::isExiting() const {
606   return getParent() && getParent()->getExitingBasicBlock() == this;
607 }
608 
609 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
610 void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const {
611   if (getSuccessors().empty()) {
612     O << Indent << "No successors\n";
613   } else {
614     O << Indent << "Successor(s): ";
615     ListSeparator LS;
616     for (auto *Succ : getSuccessors())
617       O << LS << Succ->getName();
618     O << '\n';
619   }
620 }
621 
622 void VPBasicBlock::print(raw_ostream &O, const Twine &Indent,
623                          VPSlotTracker &SlotTracker) const {
624   O << Indent << getName() << ":\n";
625 
626   auto RecipeIndent = Indent + "  ";
627   for (const VPRecipeBase &Recipe : *this) {
628     Recipe.print(O, RecipeIndent, SlotTracker);
629     O << '\n';
630   }
631 
632   printSuccessors(O, Indent);
633 }
634 #endif
635 
636 static std::pair<VPBlockBase *, VPBlockBase *> cloneSESE(VPBlockBase *Entry);
637 
638 // Clone the CFG for all nodes in the single-entry-single-exit region reachable
639 // from \p Entry, this includes cloning the blocks and their recipes. Operands
640 // of cloned recipes will NOT be updated. Remapping of operands must be done
641 // separately. Returns a pair with the the new entry and exiting blocks of the
642 // cloned region.
643 static std::pair<VPBlockBase *, VPBlockBase *> cloneSESE(VPBlockBase *Entry) {
644   DenseMap<VPBlockBase *, VPBlockBase *> Old2NewVPBlocks;
645   ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> RPOT(
646       Entry);
647   for (VPBlockBase *BB : RPOT) {
648     VPBlockBase *NewBB = BB->clone();
649     for (VPBlockBase *Pred : BB->getPredecessors())
650       VPBlockUtils::connectBlocks(Old2NewVPBlocks[Pred], NewBB);
651 
652     Old2NewVPBlocks[BB] = NewBB;
653   }
654 
655 #if !defined(NDEBUG)
656   // Verify that the order of predecessors and successors matches in the cloned
657   // version.
658   ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>>
659       NewRPOT(Old2NewVPBlocks[Entry]);
660   for (const auto &[OldBB, NewBB] : zip(RPOT, NewRPOT)) {
661     for (const auto &[OldPred, NewPred] :
662          zip(OldBB->getPredecessors(), NewBB->getPredecessors()))
663       assert(NewPred == Old2NewVPBlocks[OldPred] && "Different predecessors");
664 
665     for (const auto &[OldSucc, NewSucc] :
666          zip(OldBB->successors(), NewBB->successors()))
667       assert(NewSucc == Old2NewVPBlocks[OldSucc] && "Different successors");
668   }
669 #endif
670 
671   return std::make_pair(Old2NewVPBlocks[Entry],
672                         Old2NewVPBlocks[*reverse(RPOT).begin()]);
673 }
674 
675 VPRegionBlock *VPRegionBlock::clone() {
676   const auto &[NewEntry, NewExiting] = cloneSESE(getEntry());
677   auto *NewRegion =
678       new VPRegionBlock(NewEntry, NewExiting, getName(), isReplicator());
679   for (VPBlockBase *Block : vp_depth_first_shallow(NewEntry))
680     Block->setParent(NewRegion);
681   return NewRegion;
682 }
683 
684 void VPRegionBlock::dropAllReferences(VPValue *NewValue) {
685   for (VPBlockBase *Block : vp_depth_first_shallow(Entry))
686     // Drop all references in VPBasicBlocks and replace all uses with
687     // DummyValue.
688     Block->dropAllReferences(NewValue);
689 }
690 
691 void VPRegionBlock::execute(VPTransformState *State) {
692   ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>>
693       RPOT(Entry);
694 
695   if (!isReplicator()) {
696     // Create and register the new vector loop.
697     Loop *PrevLoop = State->CurrentVectorLoop;
698     State->CurrentVectorLoop = State->LI->AllocateLoop();
699     BasicBlock *VectorPH = State->CFG.VPBB2IRBB[getPreheaderVPBB()];
700     Loop *ParentLoop = State->LI->getLoopFor(VectorPH);
701 
702     // Insert the new loop into the loop nest and register the new basic blocks
703     // before calling any utilities such as SCEV that require valid LoopInfo.
704     if (ParentLoop)
705       ParentLoop->addChildLoop(State->CurrentVectorLoop);
706     else
707       State->LI->addTopLevelLoop(State->CurrentVectorLoop);
708 
709     // Visit the VPBlocks connected to "this", starting from it.
710     for (VPBlockBase *Block : RPOT) {
711       LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
712       Block->execute(State);
713     }
714 
715     State->CurrentVectorLoop = PrevLoop;
716     return;
717   }
718 
719   assert(!State->Instance && "Replicating a Region with non-null instance.");
720 
721   // Enter replicating mode.
722   State->Instance = VPIteration(0, 0);
723 
724   for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
725     State->Instance->Part = Part;
726     assert(!State->VF.isScalable() && "VF is assumed to be non scalable.");
727     for (unsigned Lane = 0, VF = State->VF.getKnownMinValue(); Lane < VF;
728          ++Lane) {
729       State->Instance->Lane = VPLane(Lane, VPLane::Kind::First);
730       // Visit the VPBlocks connected to \p this, starting from it.
731       for (VPBlockBase *Block : RPOT) {
732         LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
733         Block->execute(State);
734       }
735     }
736   }
737 
738   // Exit replicating mode.
739   State->Instance.reset();
740 }
741 
742 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
743 void VPRegionBlock::print(raw_ostream &O, const Twine &Indent,
744                           VPSlotTracker &SlotTracker) const {
745   O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {";
746   auto NewIndent = Indent + "  ";
747   for (auto *BlockBase : vp_depth_first_shallow(Entry)) {
748     O << '\n';
749     BlockBase->print(O, NewIndent, SlotTracker);
750   }
751   O << Indent << "}\n";
752 
753   printSuccessors(O, Indent);
754 }
755 #endif
756 
757 VPlan::~VPlan() {
758   for (auto &KV : LiveOuts)
759     delete KV.second;
760   LiveOuts.clear();
761 
762   if (Entry) {
763     VPValue DummyValue;
764     for (VPBlockBase *Block : vp_depth_first_shallow(Entry))
765       Block->dropAllReferences(&DummyValue);
766 
767     VPBlockBase::deleteCFG(Entry);
768 
769     Preheader->dropAllReferences(&DummyValue);
770     delete Preheader;
771   }
772   for (VPValue *VPV : VPLiveInsToFree)
773     delete VPV;
774   if (BackedgeTakenCount)
775     delete BackedgeTakenCount;
776 }
777 
778 VPlanPtr VPlan::createInitialVPlan(const SCEV *TripCount, ScalarEvolution &SE) {
779   VPBasicBlock *Preheader = new VPBasicBlock("ph");
780   VPBasicBlock *VecPreheader = new VPBasicBlock("vector.ph");
781   auto Plan = std::make_unique<VPlan>(Preheader, VecPreheader);
782   Plan->TripCount =
783       vputils::getOrCreateVPValueForSCEVExpr(*Plan, TripCount, SE);
784   // Create empty VPRegionBlock, to be filled during processing later.
785   auto *TopRegion = new VPRegionBlock("vector loop", false /*isReplicator*/);
786   VPBlockUtils::insertBlockAfter(TopRegion, VecPreheader);
787   VPBasicBlock *MiddleVPBB = new VPBasicBlock("middle.block");
788   VPBlockUtils::insertBlockAfter(MiddleVPBB, TopRegion);
789   return Plan;
790 }
791 
792 void VPlan::prepareToExecute(Value *TripCountV, Value *VectorTripCountV,
793                              Value *CanonicalIVStartValue,
794                              VPTransformState &State) {
795   // Check if the backedge taken count is needed, and if so build it.
796   if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
797     IRBuilder<> Builder(State.CFG.PrevBB->getTerminator());
798     auto *TCMO = Builder.CreateSub(TripCountV,
799                                    ConstantInt::get(TripCountV->getType(), 1),
800                                    "trip.count.minus.1");
801     BackedgeTakenCount->setUnderlyingValue(TCMO);
802   }
803 
804   VectorTripCount.setUnderlyingValue(VectorTripCountV);
805 
806   IRBuilder<> Builder(State.CFG.PrevBB->getTerminator());
807   // FIXME: Model VF * UF computation completely in VPlan.
808   VFxUF.setUnderlyingValue(
809       createStepForVF(Builder, TripCountV->getType(), State.VF, State.UF));
810 
811   // When vectorizing the epilogue loop, the canonical induction start value
812   // needs to be changed from zero to the value after the main vector loop.
813   // FIXME: Improve modeling for canonical IV start values in the epilogue loop.
814   if (CanonicalIVStartValue) {
815     VPValue *VPV = getVPValueOrAddLiveIn(CanonicalIVStartValue);
816     auto *IV = getCanonicalIV();
817     assert(all_of(IV->users(),
818                   [](const VPUser *U) {
819                     return isa<VPScalarIVStepsRecipe>(U) ||
820                            isa<VPScalarCastRecipe>(U) ||
821                            isa<VPDerivedIVRecipe>(U) ||
822                            cast<VPInstruction>(U)->getOpcode() ==
823                                Instruction::Add;
824                   }) &&
825            "the canonical IV should only be used by its increment or "
826            "ScalarIVSteps when resetting the start value");
827     IV->setOperand(0, VPV);
828   }
829 }
830 
831 /// Generate the code inside the preheader and body of the vectorized loop.
832 /// Assumes a single pre-header basic-block was created for this. Introduce
833 /// additional basic-blocks as needed, and fill them all.
834 void VPlan::execute(VPTransformState *State) {
835   // Initialize CFG state.
836   State->CFG.PrevVPBB = nullptr;
837   State->CFG.ExitBB = State->CFG.PrevBB->getSingleSuccessor();
838   BasicBlock *VectorPreHeader = State->CFG.PrevBB;
839   State->Builder.SetInsertPoint(VectorPreHeader->getTerminator());
840 
841   // Generate code in the loop pre-header and body.
842   for (VPBlockBase *Block : vp_depth_first_shallow(Entry))
843     Block->execute(State);
844 
845   VPBasicBlock *LatchVPBB = getVectorLoopRegion()->getExitingBasicBlock();
846   BasicBlock *VectorLatchBB = State->CFG.VPBB2IRBB[LatchVPBB];
847 
848   // Fix the latch value of canonical, reduction and first-order recurrences
849   // phis in the vector loop.
850   VPBasicBlock *Header = getVectorLoopRegion()->getEntryBasicBlock();
851   for (VPRecipeBase &R : Header->phis()) {
852     // Skip phi-like recipes that generate their backedege values themselves.
853     if (isa<VPWidenPHIRecipe>(&R))
854       continue;
855 
856     if (isa<VPWidenPointerInductionRecipe>(&R) ||
857         isa<VPWidenIntOrFpInductionRecipe>(&R)) {
858       PHINode *Phi = nullptr;
859       if (isa<VPWidenIntOrFpInductionRecipe>(&R)) {
860         Phi = cast<PHINode>(State->get(R.getVPSingleValue(), 0));
861       } else {
862         auto *WidenPhi = cast<VPWidenPointerInductionRecipe>(&R);
863         // TODO: Split off the case that all users of a pointer phi are scalar
864         // from the VPWidenPointerInductionRecipe.
865         if (WidenPhi->onlyScalarsGenerated(State->VF.isScalable()))
866           continue;
867 
868         auto *GEP = cast<GetElementPtrInst>(State->get(WidenPhi, 0));
869         Phi = cast<PHINode>(GEP->getPointerOperand());
870       }
871 
872       Phi->setIncomingBlock(1, VectorLatchBB);
873 
874       // Move the last step to the end of the latch block. This ensures
875       // consistent placement of all induction updates.
876       Instruction *Inc = cast<Instruction>(Phi->getIncomingValue(1));
877       Inc->moveBefore(VectorLatchBB->getTerminator()->getPrevNode());
878       continue;
879     }
880 
881     auto *PhiR = cast<VPHeaderPHIRecipe>(&R);
882     // For  canonical IV, first-order recurrences and in-order reduction phis,
883     // only a single part is generated, which provides the last part from the
884     // previous iteration. For non-ordered reductions all UF parts are
885     // generated.
886     bool SinglePartNeeded = isa<VPCanonicalIVPHIRecipe>(PhiR) ||
887                             isa<VPFirstOrderRecurrencePHIRecipe>(PhiR) ||
888                             (isa<VPReductionPHIRecipe>(PhiR) &&
889                              cast<VPReductionPHIRecipe>(PhiR)->isOrdered());
890     bool NeedsScalar = isa<VPCanonicalIVPHIRecipe>(PhiR) ||
891                        (isa<VPReductionPHIRecipe>(PhiR) &&
892                         cast<VPReductionPHIRecipe>(PhiR)->isInLoop());
893     unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->UF;
894 
895     for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
896       Value *Phi = State->get(PhiR, Part, NeedsScalar);
897       Value *Val =
898           State->get(PhiR->getBackedgeValue(),
899                      SinglePartNeeded ? State->UF - 1 : Part, NeedsScalar);
900       cast<PHINode>(Phi)->addIncoming(Val, VectorLatchBB);
901     }
902   }
903 
904   // We do not attempt to preserve DT for outer loop vectorization currently.
905   if (!EnableVPlanNativePath) {
906     BasicBlock *VectorHeaderBB = State->CFG.VPBB2IRBB[Header];
907     State->DT->addNewBlock(VectorHeaderBB, VectorPreHeader);
908     updateDominatorTree(State->DT, VectorHeaderBB, VectorLatchBB,
909                         State->CFG.ExitBB);
910   }
911 }
912 
913 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
914 void VPlan::printLiveIns(raw_ostream &O) const {
915   VPSlotTracker SlotTracker(this);
916 
917   if (VFxUF.getNumUsers() > 0) {
918     O << "\nLive-in ";
919     VFxUF.printAsOperand(O, SlotTracker);
920     O << " = VF * UF";
921   }
922 
923   if (VectorTripCount.getNumUsers() > 0) {
924     O << "\nLive-in ";
925     VectorTripCount.printAsOperand(O, SlotTracker);
926     O << " = vector-trip-count";
927   }
928 
929   if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
930     O << "\nLive-in ";
931     BackedgeTakenCount->printAsOperand(O, SlotTracker);
932     O << " = backedge-taken count";
933   }
934 
935   O << "\n";
936   if (TripCount->isLiveIn())
937     O << "Live-in ";
938   TripCount->printAsOperand(O, SlotTracker);
939   O << " = original trip-count";
940   O << "\n";
941 }
942 
943 LLVM_DUMP_METHOD
944 void VPlan::print(raw_ostream &O) const {
945   VPSlotTracker SlotTracker(this);
946 
947   O << "VPlan '" << getName() << "' {";
948 
949   printLiveIns(O);
950 
951   if (!getPreheader()->empty()) {
952     O << "\n";
953     getPreheader()->print(O, "", SlotTracker);
954   }
955 
956   for (const VPBlockBase *Block : vp_depth_first_shallow(getEntry())) {
957     O << '\n';
958     Block->print(O, "", SlotTracker);
959   }
960 
961   if (!LiveOuts.empty())
962     O << "\n";
963   for (const auto &KV : LiveOuts) {
964     KV.second->print(O, SlotTracker);
965   }
966 
967   O << "}\n";
968 }
969 
970 std::string VPlan::getName() const {
971   std::string Out;
972   raw_string_ostream RSO(Out);
973   RSO << Name << " for ";
974   if (!VFs.empty()) {
975     RSO << "VF={" << VFs[0];
976     for (ElementCount VF : drop_begin(VFs))
977       RSO << "," << VF;
978     RSO << "},";
979   }
980 
981   if (UFs.empty()) {
982     RSO << "UF>=1";
983   } else {
984     RSO << "UF={" << UFs[0];
985     for (unsigned UF : drop_begin(UFs))
986       RSO << "," << UF;
987     RSO << "}";
988   }
989 
990   return Out;
991 }
992 
993 LLVM_DUMP_METHOD
994 void VPlan::printDOT(raw_ostream &O) const {
995   VPlanPrinter Printer(O, *this);
996   Printer.dump();
997 }
998 
999 LLVM_DUMP_METHOD
1000 void VPlan::dump() const { print(dbgs()); }
1001 #endif
1002 
1003 void VPlan::addLiveOut(PHINode *PN, VPValue *V) {
1004   assert(LiveOuts.count(PN) == 0 && "an exit value for PN already exists");
1005   LiveOuts.insert({PN, new VPLiveOut(PN, V)});
1006 }
1007 
1008 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopHeaderBB,
1009                                 BasicBlock *LoopLatchBB,
1010                                 BasicBlock *LoopExitBB) {
1011   // The vector body may be more than a single basic-block by this point.
1012   // Update the dominator tree information inside the vector body by propagating
1013   // it from header to latch, expecting only triangular control-flow, if any.
1014   BasicBlock *PostDomSucc = nullptr;
1015   for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
1016     // Get the list of successors of this block.
1017     std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
1018     assert(Succs.size() <= 2 &&
1019            "Basic block in vector loop has more than 2 successors.");
1020     PostDomSucc = Succs[0];
1021     if (Succs.size() == 1) {
1022       assert(PostDomSucc->getSinglePredecessor() &&
1023              "PostDom successor has more than one predecessor.");
1024       DT->addNewBlock(PostDomSucc, BB);
1025       continue;
1026     }
1027     BasicBlock *InterimSucc = Succs[1];
1028     if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
1029       PostDomSucc = Succs[1];
1030       InterimSucc = Succs[0];
1031     }
1032     assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
1033            "One successor of a basic block does not lead to the other.");
1034     assert(InterimSucc->getSinglePredecessor() &&
1035            "Interim successor has more than one predecessor.");
1036     assert(PostDomSucc->hasNPredecessors(2) &&
1037            "PostDom successor has more than two predecessors.");
1038     DT->addNewBlock(InterimSucc, BB);
1039     DT->addNewBlock(PostDomSucc, BB);
1040   }
1041   // Latch block is a new dominator for the loop exit.
1042   DT->changeImmediateDominator(LoopExitBB, LoopLatchBB);
1043   assert(DT->verify(DominatorTree::VerificationLevel::Fast));
1044 }
1045 
1046 static void remapOperands(VPBlockBase *Entry, VPBlockBase *NewEntry,
1047                           DenseMap<VPValue *, VPValue *> &Old2NewVPValues) {
1048   // Update the operands of all cloned recipes starting at NewEntry. This
1049   // traverses all reachable blocks. This is done in two steps, to handle cycles
1050   // in PHI recipes.
1051   ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>>
1052       OldDeepRPOT(Entry);
1053   ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>>
1054       NewDeepRPOT(NewEntry);
1055   // First, collect all mappings from old to new VPValues defined by cloned
1056   // recipes.
1057   for (const auto &[OldBB, NewBB] :
1058        zip(VPBlockUtils::blocksOnly<VPBasicBlock>(OldDeepRPOT),
1059            VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT))) {
1060     assert(OldBB->getRecipeList().size() == NewBB->getRecipeList().size() &&
1061            "blocks must have the same number of recipes");
1062     for (const auto &[OldR, NewR] : zip(*OldBB, *NewBB)) {
1063       assert(OldR.getNumOperands() == NewR.getNumOperands() &&
1064              "recipes must have the same number of operands");
1065       assert(OldR.getNumDefinedValues() == NewR.getNumDefinedValues() &&
1066              "recipes must define the same number of operands");
1067       for (const auto &[OldV, NewV] :
1068            zip(OldR.definedValues(), NewR.definedValues()))
1069         Old2NewVPValues[OldV] = NewV;
1070     }
1071   }
1072 
1073   // Update all operands to use cloned VPValues.
1074   for (VPBasicBlock *NewBB :
1075        VPBlockUtils::blocksOnly<VPBasicBlock>(NewDeepRPOT)) {
1076     for (VPRecipeBase &NewR : *NewBB)
1077       for (unsigned I = 0, E = NewR.getNumOperands(); I != E; ++I) {
1078         VPValue *NewOp = Old2NewVPValues.lookup(NewR.getOperand(I));
1079         NewR.setOperand(I, NewOp);
1080       }
1081   }
1082 }
1083 
1084 VPlan *VPlan::duplicate() {
1085   // Clone blocks.
1086   VPBasicBlock *NewPreheader = Preheader->clone();
1087   const auto &[NewEntry, __] = cloneSESE(Entry);
1088 
1089   // Create VPlan, clone live-ins and remap operands in the cloned blocks.
1090   auto *NewPlan = new VPlan(NewPreheader, cast<VPBasicBlock>(NewEntry));
1091   DenseMap<VPValue *, VPValue *> Old2NewVPValues;
1092   for (VPValue *OldLiveIn : VPLiveInsToFree) {
1093     Old2NewVPValues[OldLiveIn] =
1094         NewPlan->getVPValueOrAddLiveIn(OldLiveIn->getLiveInIRValue());
1095   }
1096   Old2NewVPValues[&VectorTripCount] = &NewPlan->VectorTripCount;
1097   Old2NewVPValues[&VFxUF] = &NewPlan->VFxUF;
1098   if (BackedgeTakenCount) {
1099     NewPlan->BackedgeTakenCount = new VPValue();
1100     Old2NewVPValues[BackedgeTakenCount] = NewPlan->BackedgeTakenCount;
1101   }
1102   assert(TripCount && "trip count must be set");
1103   if (TripCount->isLiveIn())
1104     Old2NewVPValues[TripCount] =
1105         NewPlan->getVPValueOrAddLiveIn(TripCount->getLiveInIRValue());
1106   // else NewTripCount will be created and inserted into Old2NewVPValues when
1107   // TripCount is cloned. In any case NewPlan->TripCount is updated below.
1108 
1109   remapOperands(Preheader, NewPreheader, Old2NewVPValues);
1110   remapOperands(Entry, NewEntry, Old2NewVPValues);
1111 
1112   // Clone live-outs.
1113   for (const auto &[_, LO] : LiveOuts)
1114     NewPlan->addLiveOut(LO->getPhi(), Old2NewVPValues[LO->getOperand(0)]);
1115 
1116   // Initialize remaining fields of cloned VPlan.
1117   NewPlan->VFs = VFs;
1118   NewPlan->UFs = UFs;
1119   // TODO: Adjust names.
1120   NewPlan->Name = Name;
1121   assert(Old2NewVPValues.contains(TripCount) &&
1122          "TripCount must have been added to Old2NewVPValues");
1123   NewPlan->TripCount = Old2NewVPValues[TripCount];
1124   return NewPlan;
1125 }
1126 
1127 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1128 
1129 Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
1130   return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
1131          Twine(getOrCreateBID(Block));
1132 }
1133 
1134 Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
1135   const std::string &Name = Block->getName();
1136   if (!Name.empty())
1137     return Name;
1138   return "VPB" + Twine(getOrCreateBID(Block));
1139 }
1140 
1141 void VPlanPrinter::dump() {
1142   Depth = 1;
1143   bumpIndent(0);
1144   OS << "digraph VPlan {\n";
1145   OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
1146   if (!Plan.getName().empty())
1147     OS << "\\n" << DOT::EscapeString(Plan.getName());
1148 
1149   {
1150     // Print live-ins.
1151   std::string Str;
1152   raw_string_ostream SS(Str);
1153   Plan.printLiveIns(SS);
1154   SmallVector<StringRef, 0> Lines;
1155   StringRef(Str).rtrim('\n').split(Lines, "\n");
1156   for (auto Line : Lines)
1157     OS << DOT::EscapeString(Line.str()) << "\\n";
1158   }
1159 
1160   OS << "\"]\n";
1161   OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
1162   OS << "edge [fontname=Courier, fontsize=30]\n";
1163   OS << "compound=true\n";
1164 
1165   dumpBlock(Plan.getPreheader());
1166 
1167   for (const VPBlockBase *Block : vp_depth_first_shallow(Plan.getEntry()))
1168     dumpBlock(Block);
1169 
1170   OS << "}\n";
1171 }
1172 
1173 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
1174   if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
1175     dumpBasicBlock(BasicBlock);
1176   else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1177     dumpRegion(Region);
1178   else
1179     llvm_unreachable("Unsupported kind of VPBlock.");
1180 }
1181 
1182 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
1183                             bool Hidden, const Twine &Label) {
1184   // Due to "dot" we print an edge between two regions as an edge between the
1185   // exiting basic block and the entry basic of the respective regions.
1186   const VPBlockBase *Tail = From->getExitingBasicBlock();
1187   const VPBlockBase *Head = To->getEntryBasicBlock();
1188   OS << Indent << getUID(Tail) << " -> " << getUID(Head);
1189   OS << " [ label=\"" << Label << '\"';
1190   if (Tail != From)
1191     OS << " ltail=" << getUID(From);
1192   if (Head != To)
1193     OS << " lhead=" << getUID(To);
1194   if (Hidden)
1195     OS << "; splines=none";
1196   OS << "]\n";
1197 }
1198 
1199 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
1200   auto &Successors = Block->getSuccessors();
1201   if (Successors.size() == 1)
1202     drawEdge(Block, Successors.front(), false, "");
1203   else if (Successors.size() == 2) {
1204     drawEdge(Block, Successors.front(), false, "T");
1205     drawEdge(Block, Successors.back(), false, "F");
1206   } else {
1207     unsigned SuccessorNumber = 0;
1208     for (auto *Successor : Successors)
1209       drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
1210   }
1211 }
1212 
1213 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
1214   // Implement dot-formatted dump by performing plain-text dump into the
1215   // temporary storage followed by some post-processing.
1216   OS << Indent << getUID(BasicBlock) << " [label =\n";
1217   bumpIndent(1);
1218   std::string Str;
1219   raw_string_ostream SS(Str);
1220   // Use no indentation as we need to wrap the lines into quotes ourselves.
1221   BasicBlock->print(SS, "", SlotTracker);
1222 
1223   // We need to process each line of the output separately, so split
1224   // single-string plain-text dump.
1225   SmallVector<StringRef, 0> Lines;
1226   StringRef(Str).rtrim('\n').split(Lines, "\n");
1227 
1228   auto EmitLine = [&](StringRef Line, StringRef Suffix) {
1229     OS << Indent << '"' << DOT::EscapeString(Line.str()) << "\\l\"" << Suffix;
1230   };
1231 
1232   // Don't need the "+" after the last line.
1233   for (auto Line : make_range(Lines.begin(), Lines.end() - 1))
1234     EmitLine(Line, " +\n");
1235   EmitLine(Lines.back(), "\n");
1236 
1237   bumpIndent(-1);
1238   OS << Indent << "]\n";
1239 
1240   dumpEdges(BasicBlock);
1241 }
1242 
1243 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
1244   OS << Indent << "subgraph " << getUID(Region) << " {\n";
1245   bumpIndent(1);
1246   OS << Indent << "fontname=Courier\n"
1247      << Indent << "label=\""
1248      << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
1249      << DOT::EscapeString(Region->getName()) << "\"\n";
1250   // Dump the blocks of the region.
1251   assert(Region->getEntry() && "Region contains no inner blocks.");
1252   for (const VPBlockBase *Block : vp_depth_first_shallow(Region->getEntry()))
1253     dumpBlock(Block);
1254   bumpIndent(-1);
1255   OS << Indent << "}\n";
1256   dumpEdges(Region);
1257 }
1258 
1259 void VPlanIngredient::print(raw_ostream &O) const {
1260   if (auto *Inst = dyn_cast<Instruction>(V)) {
1261     if (!Inst->getType()->isVoidTy()) {
1262       Inst->printAsOperand(O, false);
1263       O << " = ";
1264     }
1265     O << Inst->getOpcodeName() << " ";
1266     unsigned E = Inst->getNumOperands();
1267     if (E > 0) {
1268       Inst->getOperand(0)->printAsOperand(O, false);
1269       for (unsigned I = 1; I < E; ++I)
1270         Inst->getOperand(I)->printAsOperand(O << ", ", false);
1271     }
1272   } else // !Inst
1273     V->printAsOperand(O, false);
1274 }
1275 
1276 #endif
1277 
1278 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
1279 
1280 void VPValue::replaceAllUsesWith(VPValue *New) {
1281   replaceUsesWithIf(New, [](VPUser &, unsigned) { return true; });
1282 }
1283 
1284 void VPValue::replaceUsesWithIf(
1285     VPValue *New,
1286     llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace) {
1287   // Note that this early exit is required for correctness; the implementation
1288   // below relies on the number of users for this VPValue to decrease, which
1289   // isn't the case if this == New.
1290   if (this == New)
1291     return;
1292 
1293   for (unsigned J = 0; J < getNumUsers();) {
1294     VPUser *User = Users[J];
1295     bool RemovedUser = false;
1296     for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
1297       if (User->getOperand(I) != this || !ShouldReplace(*User, I))
1298         continue;
1299 
1300       RemovedUser = true;
1301       User->setOperand(I, New);
1302     }
1303     // If a user got removed after updating the current user, the next user to
1304     // update will be moved to the current position, so we only need to
1305     // increment the index if the number of users did not change.
1306     if (!RemovedUser)
1307       J++;
1308   }
1309 }
1310 
1311 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1312 void VPValue::printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const {
1313   if (const Value *UV = getUnderlyingValue()) {
1314     OS << "ir<";
1315     UV->printAsOperand(OS, false);
1316     OS << ">";
1317     return;
1318   }
1319 
1320   unsigned Slot = Tracker.getSlot(this);
1321   if (Slot == unsigned(-1))
1322     OS << "<badref>";
1323   else
1324     OS << "vp<%" << Tracker.getSlot(this) << ">";
1325 }
1326 
1327 void VPUser::printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const {
1328   interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) {
1329     Op->printAsOperand(O, SlotTracker);
1330   });
1331 }
1332 #endif
1333 
1334 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
1335                                           Old2NewTy &Old2New,
1336                                           InterleavedAccessInfo &IAI) {
1337   ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>>
1338       RPOT(Region->getEntry());
1339   for (VPBlockBase *Base : RPOT) {
1340     visitBlock(Base, Old2New, IAI);
1341   }
1342 }
1343 
1344 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
1345                                          InterleavedAccessInfo &IAI) {
1346   if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
1347     for (VPRecipeBase &VPI : *VPBB) {
1348       if (isa<VPWidenPHIRecipe>(&VPI))
1349         continue;
1350       assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
1351       auto *VPInst = cast<VPInstruction>(&VPI);
1352 
1353       auto *Inst = dyn_cast_or_null<Instruction>(VPInst->getUnderlyingValue());
1354       if (!Inst)
1355         continue;
1356       auto *IG = IAI.getInterleaveGroup(Inst);
1357       if (!IG)
1358         continue;
1359 
1360       auto NewIGIter = Old2New.find(IG);
1361       if (NewIGIter == Old2New.end())
1362         Old2New[IG] = new InterleaveGroup<VPInstruction>(
1363             IG->getFactor(), IG->isReverse(), IG->getAlign());
1364 
1365       if (Inst == IG->getInsertPos())
1366         Old2New[IG]->setInsertPos(VPInst);
1367 
1368       InterleaveGroupMap[VPInst] = Old2New[IG];
1369       InterleaveGroupMap[VPInst]->insertMember(
1370           VPInst, IG->getIndex(Inst),
1371           Align(IG->isReverse() ? (-1) * int(IG->getFactor())
1372                                 : IG->getFactor()));
1373     }
1374   } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1375     visitRegion(Region, Old2New, IAI);
1376   else
1377     llvm_unreachable("Unsupported kind of VPBlock.");
1378 }
1379 
1380 VPInterleavedAccessInfo::VPInterleavedAccessInfo(VPlan &Plan,
1381                                                  InterleavedAccessInfo &IAI) {
1382   Old2NewTy Old2New;
1383   visitRegion(Plan.getVectorLoopRegion(), Old2New, IAI);
1384 }
1385 
1386 void VPSlotTracker::assignSlot(const VPValue *V) {
1387   assert(!Slots.contains(V) && "VPValue already has a slot!");
1388   Slots[V] = NextSlot++;
1389 }
1390 
1391 void VPSlotTracker::assignSlots(const VPlan &Plan) {
1392   if (Plan.VFxUF.getNumUsers() > 0)
1393     assignSlot(&Plan.VFxUF);
1394   assignSlot(&Plan.VectorTripCount);
1395   if (Plan.BackedgeTakenCount)
1396     assignSlot(Plan.BackedgeTakenCount);
1397   assignSlots(Plan.getPreheader());
1398 
1399   ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<const VPBlockBase *>>
1400       RPOT(VPBlockDeepTraversalWrapper<const VPBlockBase *>(Plan.getEntry()));
1401   for (const VPBasicBlock *VPBB :
1402        VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
1403     assignSlots(VPBB);
1404 }
1405 
1406 void VPSlotTracker::assignSlots(const VPBasicBlock *VPBB) {
1407   for (const VPRecipeBase &Recipe : *VPBB)
1408     for (VPValue *Def : Recipe.definedValues())
1409       assignSlot(Def);
1410 }
1411 
1412 bool vputils::onlyFirstLaneUsed(const VPValue *Def) {
1413   return all_of(Def->users(),
1414                 [Def](const VPUser *U) { return U->onlyFirstLaneUsed(Def); });
1415 }
1416 
1417 bool vputils::onlyFirstPartUsed(const VPValue *Def) {
1418   return all_of(Def->users(),
1419                 [Def](const VPUser *U) { return U->onlyFirstPartUsed(Def); });
1420 }
1421 
1422 VPValue *vputils::getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr,
1423                                                 ScalarEvolution &SE) {
1424   if (auto *Expanded = Plan.getSCEVExpansion(Expr))
1425     return Expanded;
1426   VPValue *Expanded = nullptr;
1427   if (auto *E = dyn_cast<SCEVConstant>(Expr))
1428     Expanded = Plan.getVPValueOrAddLiveIn(E->getValue());
1429   else if (auto *E = dyn_cast<SCEVUnknown>(Expr))
1430     Expanded = Plan.getVPValueOrAddLiveIn(E->getValue());
1431   else {
1432     Expanded = new VPExpandSCEVRecipe(Expr, SE);
1433     Plan.getPreheader()->appendRecipe(Expanded->getDefiningRecipe());
1434   }
1435   Plan.addSCEVExpansion(Expr, Expanded);
1436   return Expanded;
1437 }
1438