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