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