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   case Instruction::Select: {
 313     Value *Cond = State.get(getOperand(0), Part);
 314     Value *Op1 = State.get(getOperand(1), Part);
 315     Value *Op2 = State.get(getOperand(2), Part);
 316     Value *V = Builder.CreateSelect(Cond, Op1, Op2);
 317     State.set(this, V, Part);
 318     break;
 319   }
 320   default:
 321     llvm_unreachable("Unsupported opcode for instruction");
 322   }
 323 }
 324
 325 void VPInstruction::execute(VPTransformState &State) {
 326   assert(!State.Instance && "VPInstruction executing an Instance");
 327   for (unsigned Part = 0; Part < State.UF; ++Part)
 328     generateInstruction(State, Part);
 329 }
 330
 331 void VPInstruction::print(raw_ostream &O, const Twine &Indent) const {
 332   O << " +\n" << Indent << "\"EMIT ";
 333   print(O);
 334   O << "\\l\"";
 335 }
 336
 337 void VPInstruction::print(raw_ostream &O) const {
 338   printAsOperand(O);
 339   O << " = ";
 340
 341   switch (getOpcode()) {
 342   case VPInstruction::Not:
 343     O << "not";
 344     break;
 345   case VPInstruction::ICmpULE:
 346     O << "icmp ule";
 347     break;
 348   case VPInstruction::SLPLoad:
 349     O << "combined load";
 350     break;
 351   case VPInstruction::SLPStore:
 352     O << "combined store";
 353     break;
 354   default:
 355     O << Instruction::getOpcodeName(getOpcode());
 356   }
 357
 358   for (const VPValue *Operand : operands()) {
 359     O << " ";
 360     Operand->printAsOperand(O);
 361   }
 362 }
 363
 364 /// Generate the code inside the body of the vectorized loop. Assumes a single
 365 /// LoopVectorBody basic-block was created for this. Introduce additional
 366 /// basic-blocks as needed, and fill them all.
 367 void VPlan::execute(VPTransformState *State) {
 368   // -1. Check if the backedge taken count is needed, and if so build it.
 369   if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
 370     Value *TC = State->TripCount;
 371     IRBuilder<> Builder(State->CFG.PrevBB->getTerminator());
 372     auto *TCMO = Builder.CreateSub(TC, ConstantInt::get(TC->getType(), 1),
 373                                    "trip.count.minus.1");
 374     Value2VPValue[TCMO] = BackedgeTakenCount;
 375   }
 376
 377   // 0. Set the reverse mapping from VPValues to Values for code generation.
 378   for (auto &Entry : Value2VPValue)
 379     State->VPValue2Value[Entry.second] = Entry.first;
 380
 381   BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
 382   BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
 383   assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
 384
 385   // 1. Make room to generate basic-blocks inside loop body if needed.
 386   BasicBlock *VectorLatchBB = VectorHeaderBB->splitBasicBlock(
 387       VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
 388   Loop *L = State->LI->getLoopFor(VectorHeaderBB);
 389   L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
 390   // Remove the edge between Header and Latch to allow other connections.
 391   // Temporarily terminate with unreachable until CFG is rewired.
 392   // Note: this asserts the generated code's assumption that
 393   // getFirstInsertionPt() can be dereferenced into an Instruction.
 394   VectorHeaderBB->getTerminator()->eraseFromParent();
 395   State->Builder.SetInsertPoint(VectorHeaderBB);
 396   UnreachableInst *Terminator = State->Builder.CreateUnreachable();
 397   State->Builder.SetInsertPoint(Terminator);
 398
 399   // 2. Generate code in loop body.
 400   State->CFG.PrevVPBB = nullptr;
 401   State->CFG.PrevBB = VectorHeaderBB;
 402   State->CFG.LastBB = VectorLatchBB;
 403
 404   for (VPBlockBase *Block : depth_first(Entry))
 405     Block->execute(State);
 406
 407   // Setup branch terminator successors for VPBBs in VPBBsToFix based on
 408   // VPBB's successors.
 409   for (auto VPBB : State->CFG.VPBBsToFix) {
 410     assert(EnableVPlanNativePath &&
 411            "Unexpected VPBBsToFix in non VPlan-native path");
 412     BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB];
 413     assert(BB && "Unexpected null basic block for VPBB");
 414
 415     unsigned Idx = 0;
 416     auto *BBTerminator = BB->getTerminator();
 417
 418     for (VPBlockBase *SuccVPBlock : VPBB->getHierarchicalSuccessors()) {
 419       VPBasicBlock *SuccVPBB = SuccVPBlock->getEntryBasicBlock();
 420       BBTerminator->setSuccessor(Idx, State->CFG.VPBB2IRBB[SuccVPBB]);
 421       ++Idx;
 422     }
 423   }
 424
 425   // 3. Merge the temporary latch created with the last basic-block filled.
 426   BasicBlock *LastBB = State->CFG.PrevBB;
 427   // Connect LastBB to VectorLatchBB to facilitate their merge.
 428   assert((EnableVPlanNativePath ||
 429           isa<UnreachableInst>(LastBB->getTerminator())) &&
 430          "Expected InnerLoop VPlan CFG to terminate with unreachable");
 431   assert((!EnableVPlanNativePath || isa<BranchInst>(LastBB->getTerminator())) &&
 432          "Expected VPlan CFG to terminate with branch in NativePath");
 433   LastBB->getTerminator()->eraseFromParent();
 434   BranchInst::Create(VectorLatchBB, LastBB);
 435
 436   // Merge LastBB with Latch.
 437   bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
 438   (void)Merged;
 439   assert(Merged && "Could not merge last basic block with latch.");
 440   VectorLatchBB = LastBB;
 441
 442   // We do not attempt to preserve DT for outer loop vectorization currently.
 443   if (!EnableVPlanNativePath)
 444     updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB);
 445 }
 446
 447 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
 448                                 BasicBlock *LoopLatchBB) {
 449   BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
 450   assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
 451   DT->addNewBlock(LoopHeaderBB, LoopPreHeaderBB);
 452   // The vector body may be more than a single basic-block by this point.
 453   // Update the dominator tree information inside the vector body by propagating
 454   // it from header to latch, expecting only triangular control-flow, if any.
 455   BasicBlock *PostDomSucc = nullptr;
 456   for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
 457     // Get the list of successors of this block.
 458     std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
 459     assert(Succs.size() <= 2 &&
 460            "Basic block in vector loop has more than 2 successors.");
 461     PostDomSucc = Succs[0];
 462     if (Succs.size() == 1) {
 463       assert(PostDomSucc->getSinglePredecessor() &&
 464              "PostDom successor has more than one predecessor.");
 465       DT->addNewBlock(PostDomSucc, BB);
 466       continue;
 467     }
 468     BasicBlock *InterimSucc = Succs[1];
 469     if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
 470       PostDomSucc = Succs[1];
 471       InterimSucc = Succs[0];
 472     }
 473     assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
 474            "One successor of a basic block does not lead to the other.");
 475     assert(InterimSucc->getSinglePredecessor() &&
 476            "Interim successor has more than one predecessor.");
 477     assert(PostDomSucc->hasNPredecessors(2) &&
 478            "PostDom successor has more than two predecessors.");
 479     DT->addNewBlock(InterimSucc, BB);
 480     DT->addNewBlock(PostDomSucc, BB);
 481   }
 482 }
 483
 484 const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
 485   return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
 486          Twine(getOrCreateBID(Block));
 487 }
 488
 489 const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
 490   const std::string &Name = Block->getName();
 491   if (!Name.empty())
 492     return Name;
 493   return "VPB" + Twine(getOrCreateBID(Block));
 494 }
 495
 496 void VPlanPrinter::dump() {
 497   Depth = 1;
 498   bumpIndent(0);
 499   OS << "digraph VPlan {\n";
 500   OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
 501   if (!Plan.getName().empty())
 502     OS << "\\n" << DOT::EscapeString(Plan.getName());
 503   if (!Plan.Value2VPValue.empty() || Plan.BackedgeTakenCount) {
 504     OS << ", where:";
 505     if (Plan.BackedgeTakenCount)
 506       OS << "\\n"
 507          << *Plan.getOrCreateBackedgeTakenCount() << " := BackedgeTakenCount";
 508     for (auto Entry : Plan.Value2VPValue) {
 509       OS << "\\n" << *Entry.second;
 510       OS << DOT::EscapeString(" := ");
 511       Entry.first->printAsOperand(OS, false);
 512     }
 513   }
 514   OS << "\"]\n";
 515   OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
 516   OS << "edge [fontname=Courier, fontsize=30]\n";
 517   OS << "compound=true\n";
 518
 519   for (VPBlockBase *Block : depth_first(Plan.getEntry()))
 520     dumpBlock(Block);
 521
 522   OS << "}\n";
 523 }
 524
 525 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
 526   if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
 527     dumpBasicBlock(BasicBlock);
 528   else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
 529     dumpRegion(Region);
 530   else
 531     llvm_unreachable("Unsupported kind of VPBlock.");
 532 }
 533
 534 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
 535                             bool Hidden, const Twine &Label) {
 536   // Due to "dot" we print an edge between two regions as an edge between the
 537   // exit basic block and the entry basic of the respective regions.
 538   const VPBlockBase *Tail = From->getExitBasicBlock();
 539   const VPBlockBase *Head = To->getEntryBasicBlock();
 540   OS << Indent << getUID(Tail) << " -> " << getUID(Head);
 541   OS << " [ label=\"" << Label << '\"';
 542   if (Tail != From)
 543     OS << " ltail=" << getUID(From);
 544   if (Head != To)
 545     OS << " lhead=" << getUID(To);
 546   if (Hidden)
 547     OS << "; splines=none";
 548   OS << "]\n";
 549 }
 550
 551 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
 552   auto &Successors = Block->getSuccessors();
 553   if (Successors.size() == 1)
 554     drawEdge(Block, Successors.front(), false, "");
 555   else if (Successors.size() == 2) {
 556     drawEdge(Block, Successors.front(), false, "T");
 557     drawEdge(Block, Successors.back(), false, "F");
 558   } else {
 559     unsigned SuccessorNumber = 0;
 560     for (auto *Successor : Successors)
 561       drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
 562   }
 563 }
 564
 565 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
 566   OS << Indent << getUID(BasicBlock) << " [label =\n";
 567   bumpIndent(1);
 568   OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\"";
 569   bumpIndent(1);
 570
 571   // Dump the block predicate.
 572   const VPValue *Pred = BasicBlock->getPredicate();
 573   if (Pred) {
 574     OS << " +\n" << Indent << " \"BlockPredicate: ";
 575     if (const VPInstruction *PredI = dyn_cast<VPInstruction>(Pred)) {
 576       PredI->printAsOperand(OS);
 577       OS << " (" << DOT::EscapeString(PredI->getParent()->getName())
 578          << ")\\l\"";
 579     } else
 580       Pred->printAsOperand(OS);
 581   }
 582
 583   for (const VPRecipeBase &Recipe : *BasicBlock)
 584     Recipe.print(OS, Indent);
 585
 586   // Dump the condition bit.
 587   const VPValue *CBV = BasicBlock->getCondBit();
 588   if (CBV) {
 589     OS << " +\n" << Indent << " \"CondBit: ";
 590     if (const VPInstruction *CBI = dyn_cast<VPInstruction>(CBV)) {
 591       CBI->printAsOperand(OS);
 592       OS << " (" << DOT::EscapeString(CBI->getParent()->getName()) << ")\\l\"";
 593     } else {
 594       CBV->printAsOperand(OS);
 595       OS << "\"";
 596     }
 597   }
 598
 599   bumpIndent(-2);
 600   OS << "\n" << Indent << "]\n";
 601   dumpEdges(BasicBlock);
 602 }
 603
 604 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
 605   OS << Indent << "subgraph " << getUID(Region) << " {\n";
 606   bumpIndent(1);
 607   OS << Indent << "fontname=Courier\n"
 608      << Indent << "label=\""
 609      << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
 610      << DOT::EscapeString(Region->getName()) << "\"\n";
 611   // Dump the blocks of the region.
 612   assert(Region->getEntry() && "Region contains no inner blocks.");
 613   for (const VPBlockBase *Block : depth_first(Region->getEntry()))
 614     dumpBlock(Block);
 615   bumpIndent(-1);
 616   OS << Indent << "}\n";
 617   dumpEdges(Region);
 618 }
 619
 620 void VPlanPrinter::printAsIngredient(raw_ostream &O, Value *V) {
 621   std::string IngredientString;
 622   raw_string_ostream RSO(IngredientString);
 623   if (auto *Inst = dyn_cast<Instruction>(V)) {
 624     if (!Inst->getType()->isVoidTy()) {
 625       Inst->printAsOperand(RSO, false);
 626       RSO << " = ";
 627     }
 628     RSO << Inst->getOpcodeName() << " ";
 629     unsigned E = Inst->getNumOperands();
 630     if (E > 0) {
 631       Inst->getOperand(0)->printAsOperand(RSO, false);
 632       for (unsigned I = 1; I < E; ++I)
 633         Inst->getOperand(I)->printAsOperand(RSO << ", ", false);
 634     }
 635   } else // !Inst
 636     V->printAsOperand(RSO, false);
 637   RSO.flush();
 638   O << DOT::EscapeString(IngredientString);
 639 }
 640
 641 void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent) const {
 642   O << " +\n" << Indent << "\"WIDEN\\l\"";
 643   for (auto &Instr : make_range(Begin, End))
 644     O << " +\n" << Indent << "\"  " << VPlanIngredient(&Instr) << "\\l\"";
 645 }
 646
 647 void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O,
 648                                           const Twine &Indent) const {
 649   O << " +\n" << Indent << "\"WIDEN-INDUCTION";
 650   if (Trunc) {
 651     O << "\\l\"";
 652     O << " +\n" << Indent << "\"  " << VPlanIngredient(IV) << "\\l\"";
 653     O << " +\n" << Indent << "\"  " << VPlanIngredient(Trunc) << "\\l\"";
 654   } else
 655     O << " " << VPlanIngredient(IV) << "\\l\"";
 656 }
 657
 658 void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
 659   O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\"";
 660 }
 661
 662 void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent) const {
 663   O << " +\n" << Indent << "\"BLEND ";
 664   Phi->printAsOperand(O, false);
 665   O << " =";
 666   if (!User) {
 667     // Not a User of any mask: not really blending, this is a
 668     // single-predecessor phi.
 669     O << " ";
 670     Phi->getIncomingValue(0)->printAsOperand(O, false);
 671   } else {
 672     for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
 673       O << " ";
 674       Phi->getIncomingValue(I)->printAsOperand(O, false);
 675       O << "/";
 676       User->getOperand(I)->printAsOperand(O);
 677     }
 678   }
 679   O << "\\l\"";
 680 }
 681
 682 void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent) const {
 683   O << " +\n"
 684     << Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
 685     << VPlanIngredient(Ingredient);
 686   if (AlsoPack)
 687     O << " (S->V)";
 688   O << "\\l\"";
 689 }
 690
 691 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
 692   O << " +\n"
 693     << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst)
 694     << "\\l\"";
 695 }
 696
 697 void VPWidenMemoryInstructionRecipe::print(raw_ostream &O,
 698                                            const Twine &Indent) const {
 699   O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
 700   if (User) {
 701     O << ", ";
 702     User->getOperand(0)->printAsOperand(O);
 703   }
 704   O << "\\l\"";
 705 }
 706
 707 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
 708
 709 void VPValue::replaceAllUsesWith(VPValue *New) {
 710   for (VPUser *User : users())
 711     for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
 712       if (User->getOperand(I) == this)
 713         User->setOperand(I, New);
 714 }
 715
 716 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
 717                                           Old2NewTy &Old2New,
 718                                           InterleavedAccessInfo &IAI) {
 719   ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry());
 720   for (VPBlockBase *Base : RPOT) {
 721     visitBlock(Base, Old2New, IAI);
 722   }
 723 }
 724
 725 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
 726                                          InterleavedAccessInfo &IAI) {
 727   if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
 728     for (VPRecipeBase &VPI : *VPBB) {
 729       assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
 730       auto *VPInst = cast<VPInstruction>(&VPI);
 731       auto *Inst = cast<Instruction>(VPInst->getUnderlyingValue());
 732       auto *IG = IAI.getInterleaveGroup(Inst);
 733       if (!IG)
 734         continue;
 735
 736       auto NewIGIter = Old2New.find(IG);
 737       if (NewIGIter == Old2New.end())
 738         Old2New[IG] = new InterleaveGroup<VPInstruction>(
 739             IG->getFactor(), IG->isReverse(), IG->getAlignment());
 740
 741       if (Inst == IG->getInsertPos())
 742         Old2New[IG]->setInsertPos(VPInst);
 743
 744       InterleaveGroupMap[VPInst] = Old2New[IG];
 745       InterleaveGroupMap[VPInst]->insertMember(
 746           VPInst, IG->getIndex(Inst),
 747           IG->isReverse() ? (-1) * int(IG->getFactor()) : IG->getFactor());
 748     }
 749   } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
 750     visitRegion(Region, Old2New, IAI);
 751   else
 752     llvm_unreachable("Unsupported kind of VPBlock.");
 753 }
 754
 755 VPInterleavedAccessInfo::VPInterleavedAccessInfo(VPlan &Plan,
 756                                                  InterleavedAccessInfo &IAI) {
 757   Old2NewTy Old2New;
 758   visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI);
 759 }