llvm/lib/Transforms/Vectorize/VPlan.cpp

   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
  48 using namespace llvm;
  49
  50 namespace llvm {
  51 extern cl::opt<bool> EnableVPlanNativePath;
  52 }
  53
  54 #define DEBUG_TYPE "vplan"
  55
  56 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  57 raw_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
  66 Value *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
  79 VPValue::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
  85 VPValue::~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)
  92 void 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
  99 void 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
 107 void 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
 116 VPRecipeBase *VPValue::getDefiningRecipe() {
 117   return cast_or_null<VPRecipeBase>(Def);
 118 }
 119
 120 const 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
 126 template <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
 146 VPlan *VPBlockBase::getPlan() { return getPlanEntry(this)->Plan; }
 147
 148 const VPlan *VPBlockBase::getPlan() const { return getPlanEntry(this)->Plan; }
 149
 150 /// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
 151 const 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
 158 VPBasicBlock *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
 165 void 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.
 173 const 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
 180 VPBasicBlock *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
 187 VPBlockBase *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
 195 VPBlockBase *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
 203 void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
 204   for (VPBlockBase *Block : to_vector(vp_depth_first_shallow(Entry)))
 205     delete Block;
 206 }
 207
 208 VPBasicBlock::iterator VPBasicBlock::getFirstNonPhi() {
 209   iterator It = begin();
 210   while (It != end() && It->isPhi())
 211     It++;
 212   return It;
 213 }
 214
 215 Value *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
 237 Value *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
 329 BasicBlock *VPTransformState::CFGState::getPreheaderBBFor(VPRecipeBase *R) {
 330   VPRegionBlock *LoopRegion = R->getParent()->getEnclosingLoopRegion();
 331   return VPBB2IRBB[LoopRegion->getPreheaderVPBB()];
 332 }
 333
 334 void 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
 342 void 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
 351 void 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
 362 void 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
 383 void 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
 392 BasicBlock *
 393 VPBasicBlock::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
 433 void 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
 501 void 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
 511 VPBasicBlock *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
 536 VPRegionBlock *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
 546 static 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
 575 VPRecipeBase *VPBasicBlock::getTerminator() {
 576   if (hasConditionalTerminator(this))
 577     return &back();
 578   return nullptr;
 579 }
 580
 581 const VPRecipeBase *VPBasicBlock::getTerminator() const {
 582   if (hasConditionalTerminator(this))
 583     return &back();
 584   return nullptr;
 585 }
 586
 587 bool VPBasicBlock::isExiting() const {
 588   return getParent()->getExitingBasicBlock() == this;
 589 }
 590
 591 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 592 void 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
 604 void 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
 618 void 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
 625 void 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)
 677 void 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
 691 VPlan::~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
 712 VPlanPtr 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
 726 void 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.
 773 void 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)
 853 void 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
 882 LLVM_DUMP_METHOD
 883 void 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
 909 std::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
 932 LLVM_DUMP_METHOD
 933 void VPlan::printDOT(raw_ostream &O) const {
 934   VPlanPrinter Printer(O, *this);
 935   Printer.dump();
 936 }
 937
 938 LLVM_DUMP_METHOD
 939 void VPlan::dump() const { print(dbgs()); }
 940 #endif
 941
 942 void 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
 947 void 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
 987 Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
 988   return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
 989          Twine(getOrCreateBID(Block));
 990 }
 991
 992 Twine 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
 999 void 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
1031 void 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
1040 void 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
1057 void 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
1071 void 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
1101 void 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
1117 void 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
1136 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
1137
1138 void VPValue::replaceAllUsesWith(VPValue *New) {
1139   replaceUsesWithIf(New, [](VPUser &, unsigned) { return true; });
1140 }
1141
1142 void 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)
1170 void 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
1185 void 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
1192 void 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
1202 void 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
1238 VPInterleavedAccessInfo::VPInterleavedAccessInfo(VPlan &Plan,
1239                                                  InterleavedAccessInfo &IAI) {
1240   Old2NewTy Old2New;
1241   visitRegion(Plan.getVectorLoopRegion(), Old2New, IAI);
1242 }
1243
1244 void VPSlotTracker::assignSlot(const VPValue *V) {
1245   assert(!Slots.contains(V) && "VPValue already has a slot!");
1246   Slots[V] = NextSlot++;
1247 }
1248
1249 void 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
1264 void VPSlotTracker::assignSlots(const VPBasicBlock *VPBB) {
1265   for (const VPRecipeBase &Recipe : *VPBB)
1266     for (VPValue *Def : Recipe.definedValues())
1267       assignSlot(Def);
1268 }
1269
1270 bool vputils::onlyFirstLaneUsed(VPValue *Def) {
1271   return all_of(Def->users(),
1272                 [Def](VPUser *U) { return U->onlyFirstLaneUsed(Def); });
1273 }
1274
1275 bool vputils::onlyFirstPartUsed(VPValue *Def) {
1276   return all_of(Def->users(),
1277                 [Def](VPUser *U) { return U->onlyFirstPartUsed(Def); });
1278 }
1279
1280 VPValue *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 }