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 "VPlanDominatorTree.h"
  21 #include "llvm/ADT/DepthFirstIterator.h"
  22 #include "llvm/ADT/PostOrderIterator.h"
  23 #include "llvm/ADT/SmallVector.h"
  24 #include "llvm/ADT/Twine.h"
  25 #include "llvm/Analysis/LoopInfo.h"
  26 #include "llvm/IR/BasicBlock.h"
  27 #include "llvm/IR/CFG.h"
  28 #include "llvm/IR/InstrTypes.h"
  29 #include "llvm/IR/Instruction.h"
  30 #include "llvm/IR/Instructions.h"
  31 #include "llvm/IR/Type.h"
  32 #include "llvm/IR/Value.h"
  33 #include "llvm/Support/Casting.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/ErrorHandling.h"
  36 #include "llvm/Support/GenericDomTreeConstruction.h"
  37 #include "llvm/Support/GraphWriter.h"
  38 #include "llvm/Support/raw_ostream.h"
  39 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  40 #include <cassert>
  41 #include <iterator>
  42 #include <string>
  43 #include <vector>
  44
  45 using namespace llvm;
  46 extern cl::opt<bool> EnableVPlanNativePath;
  47
  48 #define DEBUG_TYPE "vplan"
  49
  50 raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) {
  51   if (const VPInstruction *Instr = dyn_cast<VPInstruction>(&V))
  52     Instr->print(OS);
  53   else
  54     V.printAsOperand(OS);
  55   return OS;
  56 }
  57
  58 /// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
  59 const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const {
  60   const VPBlockBase *Block = this;
  61   while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
  62     Block = Region->getEntry();
  63   return cast<VPBasicBlock>(Block);
  64 }
  65
  66 VPBasicBlock *VPBlockBase::getEntryBasicBlock() {
  67   VPBlockBase *Block = this;
  68   while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
  69     Block = Region->getEntry();
  70   return cast<VPBasicBlock>(Block);
  71 }
  72
  73 /// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
  74 const VPBasicBlock *VPBlockBase::getExitBasicBlock() const {
  75   const VPBlockBase *Block = this;
  76   while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
  77     Block = Region->getExit();
  78   return cast<VPBasicBlock>(Block);
  79 }
  80
  81 VPBasicBlock *VPBlockBase::getExitBasicBlock() {
  82   VPBlockBase *Block = this;
  83   while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
  84     Block = Region->getExit();
  85   return cast<VPBasicBlock>(Block);
  86 }
  87
  88 VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() {
  89   if (!Successors.empty() || !Parent)
  90     return this;
  91   assert(Parent->getExit() == this &&
  92          "Block w/o successors not the exit of its parent.");
  93   return Parent->getEnclosingBlockWithSuccessors();
  94 }
  95
  96 VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {
  97   if (!Predecessors.empty() || !Parent)
  98     return this;
  99   assert(Parent->getEntry() == this &&
 100          "Block w/o predecessors not the entry of its parent.");
 101   return Parent->getEnclosingBlockWithPredecessors();
 102 }
 103
 104 void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
 105   SmallVector<VPBlockBase *, 8> Blocks;
 106   for (VPBlockBase *Block : depth_first(Entry))
 107     Blocks.push_back(Block);
 108
 109   for (VPBlockBase *Block : Blocks)
 110     delete Block;
 111 }
 112
 113 BasicBlock *
 114 VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
 115   // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
 116   // Pred stands for Predessor. Prev stands for Previous - last visited/created.
 117   BasicBlock *PrevBB = CFG.PrevBB;
 118   BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
 119                                          PrevBB->getParent(), CFG.LastBB);
 120   LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
 121
 122   // Hook up the new basic block to its predecessors.
 123   for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
 124     VPBasicBlock *PredVPBB = PredVPBlock->getExitBasicBlock();
 125     auto &PredVPSuccessors = PredVPBB->getSuccessors();
 126     BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
 127
 128     // In outer loop vectorization scenario, the predecessor BBlock may not yet
 129     // be visited(backedge). Mark the VPBasicBlock for fixup at the end of
 130     // vectorization. We do not encounter this case in inner loop vectorization
 131     // as we start out by building a loop skeleton with the vector loop header
 132     // and latch blocks. As a result, we never enter this function for the
 133     // header block in the non VPlan-native path.
 134     if (!PredBB) {
 135       assert(EnableVPlanNativePath &&
 136              "Unexpected null predecessor in non VPlan-native path");
 137       CFG.VPBBsToFix.push_back(PredVPBB);
 138       continue;
 139     }
 140
 141     assert(PredBB && "Predecessor basic-block not found building successor.");
 142     auto *PredBBTerminator = PredBB->getTerminator();
 143     LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
 144     if (isa<UnreachableInst>(PredBBTerminator)) {
 145       assert(PredVPSuccessors.size() == 1 &&
 146              "Predecessor ending w/o branch must have single successor.");
 147       PredBBTerminator->eraseFromParent();
 148       BranchInst::Create(NewBB, PredBB);
 149     } else {
 150       assert(PredVPSuccessors.size() == 2 &&
 151              "Predecessor ending with branch must have two successors.");
 152       unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
 153       assert(!PredBBTerminator->getSuccessor(idx) &&
 154              "Trying to reset an existing successor block.");
 155       PredBBTerminator->setSuccessor(idx, NewBB);
 156     }
 157   }
 158   return NewBB;
 159 }
 160
 161 void VPBasicBlock::execute(VPTransformState *State) {
 162   bool Replica = State->Instance &&
 163                  !(State->Instance->Part == 0 && State->Instance->Lane == 0);
 164   VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
 165   VPBlockBase *SingleHPred = nullptr;
 166   BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
 167
 168   // 1. Create an IR basic block, or reuse the last one if possible.
 169   // The last IR basic block is reused, as an optimization, in three cases:
 170   // A. the first VPBB reuses the loop header BB - when PrevVPBB is null;
 171   // B. when the current VPBB has a single (hierarchical) predecessor which
 172   //    is PrevVPBB and the latter has a single (hierarchical) successor; and
 173   // C. when the current VPBB is an entry of a region replica - where PrevVPBB
 174   //    is the exit of this region from a previous instance, or the predecessor
 175   //    of this region.
 176   if (PrevVPBB && /* A */
 177       !((SingleHPred = getSingleHierarchicalPredecessor()) &&
 178         SingleHPred->getExitBasicBlock() == PrevVPBB &&
 179         PrevVPBB->getSingleHierarchicalSuccessor()) && /* B */
 180       !(Replica && getPredecessors().empty())) {       /* C */
 181     NewBB = createEmptyBasicBlock(State->CFG);
 182     State->Builder.SetInsertPoint(NewBB);
 183     // Temporarily terminate with unreachable until CFG is rewired.
 184     UnreachableInst *Terminator = State->Builder.CreateUnreachable();
 185     State->Builder.SetInsertPoint(Terminator);
 186     // Register NewBB in its loop. In innermost loops its the same for all BB's.
 187     Loop *L = State->LI->getLoopFor(State->CFG.LastBB);
 188     L->addBasicBlockToLoop(NewBB, *State->LI);
 189     State->CFG.PrevBB = NewBB;
 190   }
 191
 192   // 2. Fill the IR basic block with IR instructions.
 193   LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
 194                     << " in BB:" << NewBB->getName() << '\n');
 195
 196   State->CFG.VPBB2IRBB[this] = NewBB;
 197   State->CFG.PrevVPBB = this;
 198
 199   for (VPRecipeBase &Recipe : Recipes)
 200     Recipe.execute(*State);
 201
 202   VPValue *CBV;
 203   if (EnableVPlanNativePath && (CBV = getCondBit())) {
 204     Value *IRCBV = CBV->getUnderlyingValue();
 205     assert(IRCBV && "Unexpected null underlying value for condition bit");
 206
 207     // Condition bit value in a VPBasicBlock is used as the branch selector. In
 208     // the VPlan-native path case, since all branches are uniform we generate a
 209     // branch instruction using the condition value from vector lane 0 and dummy
 210     // successors. The successors are fixed later when the successor blocks are
 211     // visited.
 212     Value *NewCond = State->Callback.getOrCreateVectorValues(IRCBV, 0);
 213     NewCond = State->Builder.CreateExtractElement(NewCond,
 214                                                   State->Builder.getInt32(0));
 215
 216     // Replace the temporary unreachable terminator with the new conditional
 217     // branch.
 218     auto *CurrentTerminator = NewBB->getTerminator();
 219     assert(isa<UnreachableInst>(CurrentTerminator) &&
 220            "Expected to replace unreachable terminator with conditional "
 221            "branch.");
 222     auto *CondBr = BranchInst::Create(NewBB, nullptr, NewCond);
 223     CondBr->setSuccessor(0, nullptr);
 224     ReplaceInstWithInst(CurrentTerminator, CondBr);
 225   }
 226
 227   LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
 228 }
 229
 230 void VPRegionBlock::execute(VPTransformState *State) {
 231   ReversePostOrderTraversal<VPBlockBase *> RPOT(Entry);
 232
 233   if (!isReplicator()) {
 234     // Visit the VPBlocks connected to "this", starting from it.
 235     for (VPBlockBase *Block : RPOT) {
 236       if (EnableVPlanNativePath) {
 237         // The inner loop vectorization path does not represent loop preheader
 238         // and exit blocks as part of the VPlan. In the VPlan-native path, skip
 239         // vectorizing loop preheader block. In future, we may replace this
 240         // check with the check for loop preheader.
 241         if (Block->getNumPredecessors() == 0)
 242           continue;
 243
 244         // Skip vectorizing loop exit block. In future, we may replace this
 245         // check with the check for loop exit.
 246         if (Block->getNumSuccessors() == 0)
 247           continue;
 248       }
 249
 250       LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
 251       Block->execute(State);
 252     }
 253     return;
 254   }
 255
 256   assert(!State->Instance && "Replicating a Region with non-null instance.");
 257
 258   // Enter replicating mode.
 259   State->Instance = {0, 0};
 260
 261   for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
 262     State->Instance->Part = Part;
 263     for (unsigned Lane = 0, VF = State->VF; Lane < VF; ++Lane) {
 264       State->Instance->Lane = Lane;
 265       // Visit the VPBlocks connected to \p this, starting from it.
 266       for (VPBlockBase *Block : RPOT) {
 267         LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
 268         Block->execute(State);
 269       }
 270     }
 271   }
 272
 273   // Exit replicating mode.
 274   State->Instance.reset();
 275 }
 276
 277 void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
 278   Parent = InsertPos->getParent();
 279   Parent->getRecipeList().insert(InsertPos->getIterator(), this);
 280 }
 281
 282 iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
 283   return getParent()->getRecipeList().erase(getIterator());
 284 }
 285
 286 void VPInstruction::generateInstruction(VPTransformState &State,
 287                                         unsigned Part) {
 288   IRBuilder<> &Builder = State.Builder;
 289
 290   if (Instruction::isBinaryOp(getOpcode())) {
 291     Value *A = State.get(getOperand(0), Part);
 292     Value *B = State.get(getOperand(1), Part);
 293     Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
 294     State.set(this, V, Part);
 295     return;
 296   }
 297
 298   switch (getOpcode()) {
 299   case VPInstruction::Not: {
 300     Value *A = State.get(getOperand(0), Part);
 301     Value *V = Builder.CreateNot(A);
 302     State.set(this, V, Part);
 303     break;
 304   }
 305   case VPInstruction::ICmpULE: {
 306     Value *IV = State.get(getOperand(0), Part);
 307     Value *TC = State.get(getOperand(1), Part);
 308     Value *V = Builder.CreateICmpULE(IV, TC);
 309     State.set(this, V, Part);
 310     break;
 311   }
 312   default:
 313     llvm_unreachable("Unsupported opcode for instruction");
 314   }
 315 }
 316
 317 void VPInstruction::execute(VPTransformState &State) {
 318   assert(!State.Instance && "VPInstruction executing an Instance");
 319   for (unsigned Part = 0; Part < State.UF; ++Part)
 320     generateInstruction(State, Part);
 321 }
 322
 323 void VPInstruction::print(raw_ostream &O, const Twine &Indent) const {
 324   O << " +\n" << Indent << "\"EMIT ";
 325   print(O);
 326   O << "\\l\"";
 327 }
 328
 329 void VPInstruction::print(raw_ostream &O) const {
 330   printAsOperand(O);
 331   O << " = ";
 332
 333   switch (getOpcode()) {
 334   case VPInstruction::Not:
 335     O << "not";
 336     break;
 337   case VPInstruction::ICmpULE:
 338     O << "icmp ule";
 339     break;
 340   case VPInstruction::SLPLoad:
 341     O << "combined load";
 342     break;
 343   case VPInstruction::SLPStore:
 344     O << "combined store";
 345     break;
 346   default:
 347     O << Instruction::getOpcodeName(getOpcode());
 348   }
 349
 350   for (const VPValue *Operand : operands()) {
 351     O << " ";
 352     Operand->printAsOperand(O);
 353   }
 354 }
 355
 356 /// Generate the code inside the body of the vectorized loop. Assumes a single
 357 /// LoopVectorBody basic-block was created for this. Introduce additional
 358 /// basic-blocks as needed, and fill them all.
 359 void VPlan::execute(VPTransformState *State) {
 360   // -1. Check if the backedge taken count is needed, and if so build it.
 361   if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
 362     Value *TC = State->TripCount;
 363     IRBuilder<> Builder(State->CFG.PrevBB->getTerminator());
 364     auto *TCMO = Builder.CreateSub(TC, ConstantInt::get(TC->getType(), 1),
 365                                    "trip.count.minus.1");
 366     Value2VPValue[TCMO] = BackedgeTakenCount;
 367   }
 368
 369   // 0. Set the reverse mapping from VPValues to Values for code generation.
 370   for (auto &Entry : Value2VPValue)
 371     State->VPValue2Value[Entry.second] = Entry.first;
 372
 373   BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
 374   BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
 375   assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
 376
 377   // 1. Make room to generate basic-blocks inside loop body if needed.
 378   BasicBlock *VectorLatchBB = VectorHeaderBB->splitBasicBlock(
 379       VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
 380   Loop *L = State->LI->getLoopFor(VectorHeaderBB);
 381   L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
 382   // Remove the edge between Header and Latch to allow other connections.
 383   // Temporarily terminate with unreachable until CFG is rewired.
 384   // Note: this asserts the generated code's assumption that
 385   // getFirstInsertionPt() can be dereferenced into an Instruction.
 386   VectorHeaderBB->getTerminator()->eraseFromParent();
 387   State->Builder.SetInsertPoint(VectorHeaderBB);
 388   UnreachableInst *Terminator = State->Builder.CreateUnreachable();
 389   State->Builder.SetInsertPoint(Terminator);
 390
 391   // 2. Generate code in loop body.
 392   State->CFG.PrevVPBB = nullptr;
 393   State->CFG.PrevBB = VectorHeaderBB;
 394   State->CFG.LastBB = VectorLatchBB;
 395
 396   for (VPBlockBase *Block : depth_first(Entry))
 397     Block->execute(State);
 398
 399   // Setup branch terminator successors for VPBBs in VPBBsToFix based on
 400   // VPBB's successors.
 401   for (auto VPBB : State->CFG.VPBBsToFix) {
 402     assert(EnableVPlanNativePath &&
 403            "Unexpected VPBBsToFix in non VPlan-native path");
 404     BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB];
 405     assert(BB && "Unexpected null basic block for VPBB");
 406
 407     unsigned Idx = 0;
 408     auto *BBTerminator = BB->getTerminator();
 409
 410     for (VPBlockBase *SuccVPBlock : VPBB->getHierarchicalSuccessors()) {
 411       VPBasicBlock *SuccVPBB = SuccVPBlock->getEntryBasicBlock();
 412       BBTerminator->setSuccessor(Idx, State->CFG.VPBB2IRBB[SuccVPBB]);
 413       ++Idx;
 414     }
 415   }
 416
 417   // 3. Merge the temporary latch created with the last basic-block filled.
 418   BasicBlock *LastBB = State->CFG.PrevBB;
 419   // Connect LastBB to VectorLatchBB to facilitate their merge.
 420   assert((EnableVPlanNativePath ||
 421           isa<UnreachableInst>(LastBB->getTerminator())) &&
 422          "Expected InnerLoop VPlan CFG to terminate with unreachable");
 423   assert((!EnableVPlanNativePath || isa<BranchInst>(LastBB->getTerminator())) &&
 424          "Expected VPlan CFG to terminate with branch in NativePath");
 425   LastBB->getTerminator()->eraseFromParent();
 426   BranchInst::Create(VectorLatchBB, LastBB);
 427
 428   // Merge LastBB with Latch.
 429   bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
 430   (void)Merged;
 431   assert(Merged && "Could not merge last basic block with latch.");
 432   VectorLatchBB = LastBB;
 433
 434   // We do not attempt to preserve DT for outer loop vectorization currently.
 435   if (!EnableVPlanNativePath)
 436     updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB);
 437 }
 438
 439 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
 440                                 BasicBlock *LoopLatchBB) {
 441   BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
 442   assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
 443   DT->addNewBlock(LoopHeaderBB, LoopPreHeaderBB);
 444   // The vector body may be more than a single basic-block by this point.
 445   // Update the dominator tree information inside the vector body by propagating
 446   // it from header to latch, expecting only triangular control-flow, if any.
 447   BasicBlock *PostDomSucc = nullptr;
 448   for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
 449     // Get the list of successors of this block.
 450     std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
 451     assert(Succs.size() <= 2 &&
 452            "Basic block in vector loop has more than 2 successors.");
 453     PostDomSucc = Succs[0];
 454     if (Succs.size() == 1) {
 455       assert(PostDomSucc->getSinglePredecessor() &&
 456              "PostDom successor has more than one predecessor.");
 457       DT->addNewBlock(PostDomSucc, BB);
 458       continue;
 459     }
 460     BasicBlock *InterimSucc = Succs[1];
 461     if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
 462       PostDomSucc = Succs[1];
 463       InterimSucc = Succs[0];
 464     }
 465     assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
 466            "One successor of a basic block does not lead to the other.");
 467     assert(InterimSucc->getSinglePredecessor() &&
 468            "Interim successor has more than one predecessor.");
 469     assert(PostDomSucc->hasNPredecessors(2) &&
 470            "PostDom successor has more than two predecessors.");
 471     DT->addNewBlock(InterimSucc, BB);
 472     DT->addNewBlock(PostDomSucc, BB);
 473   }
 474 }
 475
 476 const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
 477   return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
 478          Twine(getOrCreateBID(Block));
 479 }
 480
 481 const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
 482   const std::string &Name = Block->getName();
 483   if (!Name.empty())
 484     return Name;
 485   return "VPB" + Twine(getOrCreateBID(Block));
 486 }
 487
 488 void VPlanPrinter::dump() {
 489   Depth = 1;
 490   bumpIndent(0);
 491   OS << "digraph VPlan {\n";
 492   OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
 493   if (!Plan.getName().empty())
 494     OS << "\\n" << DOT::EscapeString(Plan.getName());
 495   if (!Plan.Value2VPValue.empty() || Plan.BackedgeTakenCount) {
 496     OS << ", where:";
 497     if (Plan.BackedgeTakenCount)
 498       OS << "\\n"
 499          << *Plan.getOrCreateBackedgeTakenCount() << " := BackedgeTakenCount";
 500     for (auto Entry : Plan.Value2VPValue) {
 501       OS << "\\n" << *Entry.second;
 502       OS << DOT::EscapeString(" := ");
 503       Entry.first->printAsOperand(OS, false);
 504     }
 505   }
 506   OS << "\"]\n";
 507   OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
 508   OS << "edge [fontname=Courier, fontsize=30]\n";
 509   OS << "compound=true\n";
 510
 511   for (VPBlockBase *Block : depth_first(Plan.getEntry()))
 512     dumpBlock(Block);
 513
 514   OS << "}\n";
 515 }
 516
 517 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
 518   if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
 519     dumpBasicBlock(BasicBlock);
 520   else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
 521     dumpRegion(Region);
 522   else
 523     llvm_unreachable("Unsupported kind of VPBlock.");
 524 }
 525
 526 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
 527                             bool Hidden, const Twine &Label) {
 528   // Due to "dot" we print an edge between two regions as an edge between the
 529   // exit basic block and the entry basic of the respective regions.
 530   const VPBlockBase *Tail = From->getExitBasicBlock();
 531   const VPBlockBase *Head = To->getEntryBasicBlock();
 532   OS << Indent << getUID(Tail) << " -> " << getUID(Head);
 533   OS << " [ label=\"" << Label << '\"';
 534   if (Tail != From)
 535     OS << " ltail=" << getUID(From);
 536   if (Head != To)
 537     OS << " lhead=" << getUID(To);
 538   if (Hidden)
 539     OS << "; splines=none";
 540   OS << "]\n";
 541 }
 542
 543 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
 544   auto &Successors = Block->getSuccessors();
 545   if (Successors.size() == 1)
 546     drawEdge(Block, Successors.front(), false, "");
 547   else if (Successors.size() == 2) {
 548     drawEdge(Block, Successors.front(), false, "T");
 549     drawEdge(Block, Successors.back(), false, "F");
 550   } else {
 551     unsigned SuccessorNumber = 0;
 552     for (auto *Successor : Successors)
 553       drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
 554   }
 555 }
 556
 557 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
 558   OS << Indent << getUID(BasicBlock) << " [label =\n";
 559   bumpIndent(1);
 560   OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\"";
 561   bumpIndent(1);
 562
 563   // Dump the block predicate.
 564   const VPValue *Pred = BasicBlock->getPredicate();
 565   if (Pred) {
 566     OS << " +\n" << Indent << " \"BlockPredicate: ";
 567     if (const VPInstruction *PredI = dyn_cast<VPInstruction>(Pred)) {
 568       PredI->printAsOperand(OS);
 569       OS << " (" << DOT::EscapeString(PredI->getParent()->getName())
 570          << ")\\l\"";
 571     } else
 572       Pred->printAsOperand(OS);
 573   }
 574
 575   for (const VPRecipeBase &Recipe : *BasicBlock)
 576     Recipe.print(OS, Indent);
 577
 578   // Dump the condition bit.
 579   const VPValue *CBV = BasicBlock->getCondBit();
 580   if (CBV) {
 581     OS << " +\n" << Indent << " \"CondBit: ";
 582     if (const VPInstruction *CBI = dyn_cast<VPInstruction>(CBV)) {
 583       CBI->printAsOperand(OS);
 584       OS << " (" << DOT::EscapeString(CBI->getParent()->getName()) << ")\\l\"";
 585     } else {
 586       CBV->printAsOperand(OS);
 587       OS << "\"";
 588     }
 589   }
 590
 591   bumpIndent(-2);
 592   OS << "\n" << Indent << "]\n";
 593   dumpEdges(BasicBlock);
 594 }
 595
 596 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
 597   OS << Indent << "subgraph " << getUID(Region) << " {\n";
 598   bumpIndent(1);
 599   OS << Indent << "fontname=Courier\n"
 600      << Indent << "label=\""
 601      << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
 602      << DOT::EscapeString(Region->getName()) << "\"\n";
 603   // Dump the blocks of the region.
 604   assert(Region->getEntry() && "Region contains no inner blocks.");
 605   for (const VPBlockBase *Block : depth_first(Region->getEntry()))
 606     dumpBlock(Block);
 607   bumpIndent(-1);
 608   OS << Indent << "}\n";
 609   dumpEdges(Region);
 610 }
 611
 612 void VPlanPrinter::printAsIngredient(raw_ostream &O, Value *V) {
 613   std::string IngredientString;
 614   raw_string_ostream RSO(IngredientString);
 615   if (auto *Inst = dyn_cast<Instruction>(V)) {
 616     if (!Inst->getType()->isVoidTy()) {
 617       Inst->printAsOperand(RSO, false);
 618       RSO << " = ";
 619     }
 620     RSO << Inst->getOpcodeName() << " ";
 621     unsigned E = Inst->getNumOperands();
 622     if (E > 0) {
 623       Inst->getOperand(0)->printAsOperand(RSO, false);
 624       for (unsigned I = 1; I < E; ++I)
 625         Inst->getOperand(I)->printAsOperand(RSO << ", ", false);
 626     }
 627   } else // !Inst
 628     V->printAsOperand(RSO, false);
 629   RSO.flush();
 630   O << DOT::EscapeString(IngredientString);
 631 }
 632
 633 void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent) const {
 634   O << " +\n" << Indent << "\"WIDEN\\l\"";
 635   for (auto &Instr : make_range(Begin, End))
 636     O << " +\n" << Indent << "\"  " << VPlanIngredient(&Instr) << "\\l\"";
 637 }
 638
 639 void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O,
 640                                           const Twine &Indent) const {
 641   O << " +\n" << Indent << "\"WIDEN-INDUCTION";
 642   if (Trunc) {
 643     O << "\\l\"";
 644     O << " +\n" << Indent << "\"  " << VPlanIngredient(IV) << "\\l\"";
 645     O << " +\n" << Indent << "\"  " << VPlanIngredient(Trunc) << "\\l\"";
 646   } else
 647     O << " " << VPlanIngredient(IV) << "\\l\"";
 648 }
 649
 650 void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
 651   O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\"";
 652 }
 653
 654 void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent) const {
 655   O << " +\n" << Indent << "\"BLEND ";
 656   Phi->printAsOperand(O, false);
 657   O << " =";
 658   if (!User) {
 659     // Not a User of any mask: not really blending, this is a
 660     // single-predecessor phi.
 661     O << " ";
 662     Phi->getIncomingValue(0)->printAsOperand(O, false);
 663   } else {
 664     for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
 665       O << " ";
 666       Phi->getIncomingValue(I)->printAsOperand(O, false);
 667       O << "/";
 668       User->getOperand(I)->printAsOperand(O);
 669     }
 670   }
 671   O << "\\l\"";
 672 }
 673
 674 void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent) const {
 675   O << " +\n"
 676     << Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
 677     << VPlanIngredient(Ingredient);
 678   if (AlsoPack)
 679     O << " (S->V)";
 680   O << "\\l\"";
 681 }
 682
 683 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
 684   O << " +\n"
 685     << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst)
 686     << "\\l\"";
 687 }
 688
 689 void VPWidenMemoryInstructionRecipe::print(raw_ostream &O,
 690                                            const Twine &Indent) const {
 691   O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
 692   if (User) {
 693     O << ", ";
 694     User->getOperand(0)->printAsOperand(O);
 695   }
 696   O << "\\l\"";
 697 }
 698
 699 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
 700
 701 void VPValue::replaceAllUsesWith(VPValue *New) {
 702   for (VPUser *User : users())
 703     for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
 704       if (User->getOperand(I) == this)
 705         User->setOperand(I, New);
 706 }
 707
 708 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
 709                                           Old2NewTy &Old2New,
 710                                           InterleavedAccessInfo &IAI) {
 711   ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry());
 712   for (VPBlockBase *Base : RPOT) {
 713     visitBlock(Base, Old2New, IAI);
 714   }
 715 }
 716
 717 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
 718                                          InterleavedAccessInfo &IAI) {
 719   if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
 720     for (VPRecipeBase &VPI : *VPBB) {
 721       assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
 722       auto *VPInst = cast<VPInstruction>(&VPI);
 723       auto *Inst = cast<Instruction>(VPInst->getUnderlyingValue());
 724       auto *IG = IAI.getInterleaveGroup(Inst);
 725       if (!IG)
 726         continue;
 727
 728       auto NewIGIter = Old2New.find(IG);
 729       if (NewIGIter == Old2New.end())
 730         Old2New[IG] = new InterleaveGroup<VPInstruction>(
 731             IG->getFactor(), IG->isReverse(), IG->getAlignment());
 732
 733       if (Inst == IG->getInsertPos())
 734         Old2New[IG]->setInsertPos(VPInst);
 735
 736       InterleaveGroupMap[VPInst] = Old2New[IG];
 737       InterleaveGroupMap[VPInst]->insertMember(
 738           VPInst, IG->getIndex(Inst),
 739           IG->isReverse() ? (-1) * int(IG->getFactor()) : IG->getFactor());
 740     }
 741   } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
 742     visitRegion(Region, Old2New, IAI);
 743   else
 744     llvm_unreachable("Unsupported kind of VPBlock.");
 745 }
 746
 747 VPInterleavedAccessInfo::VPInterleavedAccessInfo(VPlan &Plan,
 748                                                  InterleavedAccessInfo &IAI) {
 749   Old2NewTy Old2New;
 750   visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI);
 751 }