llvm/lib/Transforms/Vectorize/VPlan.cpp

   1 //===- VPlan.cpp - Vectorizer Plan ----------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///
   9 /// \file
  10 /// This is the LLVM vectorization plan. It represents a candidate for
  11 /// vectorization, allowing to plan and optimize how to vectorize a given loop
  12 /// before generating LLVM-IR.
  13 /// The vectorizer uses vectorization plans to estimate the costs of potential
  14 /// candidates and if profitable to execute the desired plan, generating vector
  15 /// LLVM-IR code.
  16 ///
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "VPlan.h"
  20 #include "VPlanDominatorTree.h"
  21 #include "llvm/ADT/DepthFirstIterator.h"
  22 #include "llvm/ADT/PostOrderIterator.h"
  23 #include "llvm/ADT/STLExtras.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/ADT/Twine.h"
  26 #include "llvm/Analysis/IVDescriptors.h"
  27 #include "llvm/Analysis/LoopInfo.h"
  28 #include "llvm/IR/BasicBlock.h"
  29 #include "llvm/IR/CFG.h"
  30 #include "llvm/IR/InstrTypes.h"
  31 #include "llvm/IR/Instruction.h"
  32 #include "llvm/IR/Instructions.h"
  33 #include "llvm/IR/Type.h"
  34 #include "llvm/IR/Value.h"
  35 #include "llvm/Support/Casting.h"
  36 #include "llvm/Support/CommandLine.h"
  37 #include "llvm/Support/Debug.h"
  38 #include "llvm/Support/ErrorHandling.h"
  39 #include "llvm/Support/GenericDomTreeConstruction.h"
  40 #include "llvm/Support/GraphWriter.h"
  41 #include "llvm/Support/raw_ostream.h"
  42 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  43 #include <cassert>
  44 #include <iterator>
  45 #include <string>
  46 #include <vector>
  47
  48 using namespace llvm;
  49 extern cl::opt<bool> EnableVPlanNativePath;
  50
  51 #define DEBUG_TYPE "vplan"
  52
  53 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  54 raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) {
  55   const VPInstruction *Instr = dyn_cast<VPInstruction>(&V);
  56   VPSlotTracker SlotTracker(
  57       (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
  58   V.print(OS, SlotTracker);
  59   return OS;
  60 }
  61 #endif
  62
  63 Value *VPLane::getAsRuntimeExpr(IRBuilder<> &Builder,
  64                                 const ElementCount &VF) const {
  65   switch (LaneKind) {
  66   case VPLane::Kind::ScalableLast:
  67     // Lane = RuntimeVF - VF.getKnownMinValue() + Lane
  68     return Builder.CreateSub(getRuntimeVF(Builder, Builder.getInt32Ty(), VF),
  69                              Builder.getInt32(VF.getKnownMinValue() - Lane));
  70   case VPLane::Kind::First:
  71     return Builder.getInt32(Lane);
  72   }
  73   llvm_unreachable("Unknown lane kind");
  74 }
  75
  76 VPValue::VPValue(const unsigned char SC, Value *UV, VPDef *Def)
  77     : SubclassID(SC), UnderlyingVal(UV), Def(Def) {
  78   if (Def)
  79     Def->addDefinedValue(this);
  80 }
  81
  82 VPValue::~VPValue() {
  83   assert(Users.empty() && "trying to delete a VPValue with remaining users");
  84   if (Def)
  85     Def->removeDefinedValue(this);
  86 }
  87
  88 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  89 void VPValue::print(raw_ostream &OS, VPSlotTracker &SlotTracker) const {
  90   if (const VPRecipeBase *R = dyn_cast_or_null<VPRecipeBase>(Def))
  91     R->print(OS, "", SlotTracker);
  92   else
  93     printAsOperand(OS, SlotTracker);
  94 }
  95
  96 void VPValue::dump() const {
  97   const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this->Def);
  98   VPSlotTracker SlotTracker(
  99       (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
 100   print(dbgs(), SlotTracker);
 101   dbgs() << "\n";
 102 }
 103
 104 void VPDef::dump() const {
 105   const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this);
 106   VPSlotTracker SlotTracker(
 107       (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
 108   print(dbgs(), "", SlotTracker);
 109   dbgs() << "\n";
 110 }
 111 #endif
 112
 113 // Get the top-most entry block of \p Start. This is the entry block of the
 114 // containing VPlan. This function is templated to support both const and non-const blocks
 115 template <typename T> static T *getPlanEntry(T *Start) {
 116   T *Next = Start;
 117   T *Current = Start;
 118   while ((Next = Next->getParent()))
 119     Current = Next;
 120
 121   SmallSetVector<T *, 8> WorkList;
 122   WorkList.insert(Current);
 123
 124   for (unsigned i = 0; i < WorkList.size(); i++) {
 125     T *Current = WorkList[i];
 126     if (Current->getNumPredecessors() == 0)
 127       return Current;
 128     auto &Predecessors = Current->getPredecessors();
 129     WorkList.insert(Predecessors.begin(), Predecessors.end());
 130   }
 131
 132   llvm_unreachable("VPlan without any entry node without predecessors");
 133 }
 134
 135 VPlan *VPBlockBase::getPlan() { return getPlanEntry(this)->Plan; }
 136
 137 const VPlan *VPBlockBase::getPlan() const { return getPlanEntry(this)->Plan; }
 138
 139 /// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
 140 const VPBasicBlock *VPBlockBase::getEntryBasicBlock() const {
 141   const VPBlockBase *Block = this;
 142   while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
 143     Block = Region->getEntry();
 144   return cast<VPBasicBlock>(Block);
 145 }
 146
 147 VPBasicBlock *VPBlockBase::getEntryBasicBlock() {
 148   VPBlockBase *Block = this;
 149   while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
 150     Block = Region->getEntry();
 151   return cast<VPBasicBlock>(Block);
 152 }
 153
 154 void VPBlockBase::setPlan(VPlan *ParentPlan) {
 155   assert(ParentPlan->getEntry() == this &&
 156          "Can only set plan on its entry block.");
 157   Plan = ParentPlan;
 158 }
 159
 160 /// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
 161 const VPBasicBlock *VPBlockBase::getExitBasicBlock() const {
 162   const VPBlockBase *Block = this;
 163   while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
 164     Block = Region->getExit();
 165   return cast<VPBasicBlock>(Block);
 166 }
 167
 168 VPBasicBlock *VPBlockBase::getExitBasicBlock() {
 169   VPBlockBase *Block = this;
 170   while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
 171     Block = Region->getExit();
 172   return cast<VPBasicBlock>(Block);
 173 }
 174
 175 VPBlockBase *VPBlockBase::getEnclosingBlockWithSuccessors() {
 176   if (!Successors.empty() || !Parent)
 177     return this;
 178   assert(Parent->getExit() == this &&
 179          "Block w/o successors not the exit of its parent.");
 180   return Parent->getEnclosingBlockWithSuccessors();
 181 }
 182
 183 VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {
 184   if (!Predecessors.empty() || !Parent)
 185     return this;
 186   assert(Parent->getEntry() == this &&
 187          "Block w/o predecessors not the entry of its parent.");
 188   return Parent->getEnclosingBlockWithPredecessors();
 189 }
 190
 191 VPValue *VPBlockBase::getCondBit() {
 192   return CondBitUser.getSingleOperandOrNull();
 193 }
 194
 195 const VPValue *VPBlockBase::getCondBit() const {
 196   return CondBitUser.getSingleOperandOrNull();
 197 }
 198
 199 void VPBlockBase::setCondBit(VPValue *CV) { CondBitUser.resetSingleOpUser(CV); }
 200
 201 VPValue *VPBlockBase::getPredicate() {
 202   return PredicateUser.getSingleOperandOrNull();
 203 }
 204
 205 const VPValue *VPBlockBase::getPredicate() const {
 206   return PredicateUser.getSingleOperandOrNull();
 207 }
 208
 209 void VPBlockBase::setPredicate(VPValue *CV) {
 210   PredicateUser.resetSingleOpUser(CV);
 211 }
 212
 213 void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
 214   SmallVector<VPBlockBase *, 8> Blocks(depth_first(Entry));
 215
 216   for (VPBlockBase *Block : Blocks)
 217     delete Block;
 218 }
 219
 220 VPBasicBlock::iterator VPBasicBlock::getFirstNonPhi() {
 221   iterator It = begin();
 222   while (It != end() && It->isPhi())
 223     It++;
 224   return It;
 225 }
 226
 227 Value *VPTransformState::get(VPValue *Def, const VPIteration &Instance) {
 228   if (!Def->getDef())
 229     return Def->getLiveInIRValue();
 230
 231   if (hasScalarValue(Def, Instance)) {
 232     return Data
 233         .PerPartScalars[Def][Instance.Part][Instance.Lane.mapToCacheIndex(VF)];
 234   }
 235
 236   assert(hasVectorValue(Def, Instance.Part));
 237   auto *VecPart = Data.PerPartOutput[Def][Instance.Part];
 238   if (!VecPart->getType()->isVectorTy()) {
 239     assert(Instance.Lane.isFirstLane() && "cannot get lane > 0 for scalar");
 240     return VecPart;
 241   }
 242   // TODO: Cache created scalar values.
 243   Value *Lane = Instance.Lane.getAsRuntimeExpr(Builder, VF);
 244   auto *Extract = Builder.CreateExtractElement(VecPart, Lane);
 245   // set(Def, Extract, Instance);
 246   return Extract;
 247 }
 248
 249 BasicBlock *
 250 VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
 251   // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
 252   // Pred stands for Predessor. Prev stands for Previous - last visited/created.
 253   BasicBlock *PrevBB = CFG.PrevBB;
 254   BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
 255                                          PrevBB->getParent(), CFG.LastBB);
 256   LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
 257
 258   // Hook up the new basic block to its predecessors.
 259   for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
 260     VPBasicBlock *PredVPBB = PredVPBlock->getExitBasicBlock();
 261     auto &PredVPSuccessors = PredVPBB->getSuccessors();
 262     BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
 263
 264     // In outer loop vectorization scenario, the predecessor BBlock may not yet
 265     // be visited(backedge). Mark the VPBasicBlock for fixup at the end of
 266     // vectorization. We do not encounter this case in inner loop vectorization
 267     // as we start out by building a loop skeleton with the vector loop header
 268     // and latch blocks. As a result, we never enter this function for the
 269     // header block in the non VPlan-native path.
 270     if (!PredBB) {
 271       assert(EnableVPlanNativePath &&
 272              "Unexpected null predecessor in non VPlan-native path");
 273       CFG.VPBBsToFix.push_back(PredVPBB);
 274       continue;
 275     }
 276
 277     assert(PredBB && "Predecessor basic-block not found building successor.");
 278     auto *PredBBTerminator = PredBB->getTerminator();
 279     LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
 280     if (isa<UnreachableInst>(PredBBTerminator)) {
 281       assert(PredVPSuccessors.size() == 1 &&
 282              "Predecessor ending w/o branch must have single successor.");
 283       PredBBTerminator->eraseFromParent();
 284       BranchInst::Create(NewBB, PredBB);
 285     } else {
 286       assert(PredVPSuccessors.size() == 2 &&
 287              "Predecessor ending with branch must have two successors.");
 288       unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
 289       assert(!PredBBTerminator->getSuccessor(idx) &&
 290              "Trying to reset an existing successor block.");
 291       PredBBTerminator->setSuccessor(idx, NewBB);
 292     }
 293   }
 294   return NewBB;
 295 }
 296
 297 void VPBasicBlock::execute(VPTransformState *State) {
 298   bool Replica = State->Instance && !State->Instance->isFirstIteration();
 299   VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
 300   VPBlockBase *SingleHPred = nullptr;
 301   BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
 302
 303   // 1. Create an IR basic block, or reuse the last one if possible.
 304   // The last IR basic block is reused, as an optimization, in three cases:
 305   // A. the first VPBB reuses the loop header BB - when PrevVPBB is null;
 306   // B. when the current VPBB has a single (hierarchical) predecessor which
 307   //    is PrevVPBB and the latter has a single (hierarchical) successor; and
 308   // C. when the current VPBB is an entry of a region replica - where PrevVPBB
 309   //    is the exit of this region from a previous instance, or the predecessor
 310   //    of this region.
 311   if (PrevVPBB && /* A */
 312       !((SingleHPred = getSingleHierarchicalPredecessor()) &&
 313         SingleHPred->getExitBasicBlock() == PrevVPBB &&
 314         PrevVPBB->getSingleHierarchicalSuccessor()) && /* B */
 315       !(Replica && getPredecessors().empty())) {       /* C */
 316     NewBB = createEmptyBasicBlock(State->CFG);
 317     State->Builder.SetInsertPoint(NewBB);
 318     // Temporarily terminate with unreachable until CFG is rewired.
 319     UnreachableInst *Terminator = State->Builder.CreateUnreachable();
 320     State->Builder.SetInsertPoint(Terminator);
 321     // Register NewBB in its loop. In innermost loops its the same for all BB's.
 322     Loop *L = State->LI->getLoopFor(State->CFG.LastBB);
 323     L->addBasicBlockToLoop(NewBB, *State->LI);
 324     State->CFG.PrevBB = NewBB;
 325   }
 326
 327   // 2. Fill the IR basic block with IR instructions.
 328   LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
 329                     << " in BB:" << NewBB->getName() << '\n');
 330
 331   State->CFG.VPBB2IRBB[this] = NewBB;
 332   State->CFG.PrevVPBB = this;
 333
 334   for (VPRecipeBase &Recipe : Recipes)
 335     Recipe.execute(*State);
 336
 337   VPValue *CBV;
 338   if (EnableVPlanNativePath && (CBV = getCondBit())) {
 339     assert(CBV->getUnderlyingValue() &&
 340            "Unexpected null underlying value for condition bit");
 341
 342     // Condition bit value in a VPBasicBlock is used as the branch selector. In
 343     // the VPlan-native path case, since all branches are uniform we generate a
 344     // branch instruction using the condition value from vector lane 0 and dummy
 345     // successors. The successors are fixed later when the successor blocks are
 346     // visited.
 347     Value *NewCond = State->get(CBV, {0, 0});
 348
 349     // Replace the temporary unreachable terminator with the new conditional
 350     // branch.
 351     auto *CurrentTerminator = NewBB->getTerminator();
 352     assert(isa<UnreachableInst>(CurrentTerminator) &&
 353            "Expected to replace unreachable terminator with conditional "
 354            "branch.");
 355     auto *CondBr = BranchInst::Create(NewBB, nullptr, NewCond);
 356     CondBr->setSuccessor(0, nullptr);
 357     ReplaceInstWithInst(CurrentTerminator, CondBr);
 358   }
 359
 360   LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
 361 }
 362
 363 void VPBasicBlock::dropAllReferences(VPValue *NewValue) {
 364   for (VPRecipeBase &R : Recipes) {
 365     for (auto *Def : R.definedValues())
 366       Def->replaceAllUsesWith(NewValue);
 367
 368     for (unsigned I = 0, E = R.getNumOperands(); I != E; I++)
 369       R.setOperand(I, NewValue);
 370   }
 371 }
 372
 373 VPBasicBlock *VPBasicBlock::splitAt(iterator SplitAt) {
 374   assert((SplitAt == end() || SplitAt->getParent() == this) &&
 375          "can only split at a position in the same block");
 376
 377   SmallVector<VPBlockBase *, 2> Succs(getSuccessors().begin(),
 378                                       getSuccessors().end());
 379   // First, disconnect the current block from its successors.
 380   for (VPBlockBase *Succ : Succs)
 381     VPBlockUtils::disconnectBlocks(this, Succ);
 382
 383   // Create new empty block after the block to split.
 384   auto *SplitBlock = new VPBasicBlock(getName() + ".split");
 385   VPBlockUtils::insertBlockAfter(SplitBlock, this);
 386
 387   // Add successors for block to split to new block.
 388   for (VPBlockBase *Succ : Succs)
 389     VPBlockUtils::connectBlocks(SplitBlock, Succ);
 390
 391   // Finally, move the recipes starting at SplitAt to new block.
 392   for (VPRecipeBase &ToMove :
 393        make_early_inc_range(make_range(SplitAt, this->end())))
 394     ToMove.moveBefore(*SplitBlock, SplitBlock->end());
 395
 396   return SplitBlock;
 397 }
 398
 399 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 400 void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const {
 401   if (getSuccessors().empty()) {
 402     O << Indent << "No successors\n";
 403   } else {
 404     O << Indent << "Successor(s): ";
 405     ListSeparator LS;
 406     for (auto *Succ : getSuccessors())
 407       O << LS << Succ->getName();
 408     O << '\n';
 409   }
 410 }
 411
 412 void VPBasicBlock::print(raw_ostream &O, const Twine &Indent,
 413                          VPSlotTracker &SlotTracker) const {
 414   O << Indent << getName() << ":\n";
 415   if (const VPValue *Pred = getPredicate()) {
 416     O << Indent << "BlockPredicate:";
 417     Pred->printAsOperand(O, SlotTracker);
 418     if (const auto *PredInst = dyn_cast<VPInstruction>(Pred))
 419       O << " (" << PredInst->getParent()->getName() << ")";
 420     O << '\n';
 421   }
 422
 423   auto RecipeIndent = Indent + "  ";
 424   for (const VPRecipeBase &Recipe : *this) {
 425     Recipe.print(O, RecipeIndent, SlotTracker);
 426     O << '\n';
 427   }
 428
 429   printSuccessors(O, Indent);
 430
 431   if (const VPValue *CBV = getCondBit()) {
 432     O << Indent << "CondBit: ";
 433     CBV->printAsOperand(O, SlotTracker);
 434     if (const auto *CBI = dyn_cast<VPInstruction>(CBV))
 435       O << " (" << CBI->getParent()->getName() << ")";
 436     O << '\n';
 437   }
 438 }
 439 #endif
 440
 441 void VPRegionBlock::dropAllReferences(VPValue *NewValue) {
 442   for (VPBlockBase *Block : depth_first(Entry))
 443     // Drop all references in VPBasicBlocks and replace all uses with
 444     // DummyValue.
 445     Block->dropAllReferences(NewValue);
 446 }
 447
 448 void VPRegionBlock::execute(VPTransformState *State) {
 449   ReversePostOrderTraversal<VPBlockBase *> RPOT(Entry);
 450
 451   if (!isReplicator()) {
 452     // Visit the VPBlocks connected to "this", starting from it.
 453     for (VPBlockBase *Block : RPOT) {
 454       if (EnableVPlanNativePath) {
 455         // The inner loop vectorization path does not represent loop preheader
 456         // and exit blocks as part of the VPlan. In the VPlan-native path, skip
 457         // vectorizing loop preheader block. In future, we may replace this
 458         // check with the check for loop preheader.
 459         if (Block->getNumPredecessors() == 0)
 460           continue;
 461
 462         // Skip vectorizing loop exit block. In future, we may replace this
 463         // check with the check for loop exit.
 464         if (Block->getNumSuccessors() == 0)
 465           continue;
 466       }
 467
 468       LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
 469       Block->execute(State);
 470     }
 471     return;
 472   }
 473
 474   assert(!State->Instance && "Replicating a Region with non-null instance.");
 475
 476   // Enter replicating mode.
 477   State->Instance = VPIteration(0, 0);
 478
 479   for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
 480     State->Instance->Part = Part;
 481     assert(!State->VF.isScalable() && "VF is assumed to be non scalable.");
 482     for (unsigned Lane = 0, VF = State->VF.getKnownMinValue(); Lane < VF;
 483          ++Lane) {
 484       State->Instance->Lane = VPLane(Lane, VPLane::Kind::First);
 485       // Visit the VPBlocks connected to \p this, starting from it.
 486       for (VPBlockBase *Block : RPOT) {
 487         LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
 488         Block->execute(State);
 489       }
 490     }
 491   }
 492
 493   // Exit replicating mode.
 494   State->Instance.reset();
 495 }
 496
 497 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 498 void VPRegionBlock::print(raw_ostream &O, const Twine &Indent,
 499                           VPSlotTracker &SlotTracker) const {
 500   O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {";
 501   auto NewIndent = Indent + "  ";
 502   for (auto *BlockBase : depth_first(Entry)) {
 503     O << '\n';
 504     BlockBase->print(O, NewIndent, SlotTracker);
 505   }
 506   O << Indent << "}\n";
 507
 508   printSuccessors(O, Indent);
 509 }
 510 #endif
 511
 512 bool VPRecipeBase::mayWriteToMemory() const {
 513   switch (getVPDefID()) {
 514   case VPWidenMemoryInstructionSC: {
 515     return cast<VPWidenMemoryInstructionRecipe>(this)->isStore();
 516   }
 517   case VPReplicateSC:
 518   case VPWidenCallSC:
 519     return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
 520         ->mayWriteToMemory();
 521   case VPBranchOnMaskSC:
 522     return false;
 523   case VPWidenIntOrFpInductionSC:
 524   case VPWidenCanonicalIVSC:
 525   case VPWidenPHISC:
 526   case VPBlendSC:
 527   case VPWidenSC:
 528   case VPWidenGEPSC:
 529   case VPReductionSC:
 530   case VPWidenSelectSC: {
 531     const Instruction *I =
 532         dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
 533     (void)I;
 534     assert((!I || !I->mayWriteToMemory()) &&
 535            "underlying instruction may write to memory");
 536     return false;
 537   }
 538   default:
 539     return true;
 540   }
 541 }
 542
 543 bool VPRecipeBase::mayReadFromMemory() const {
 544   switch (getVPDefID()) {
 545   case VPWidenMemoryInstructionSC: {
 546     return !cast<VPWidenMemoryInstructionRecipe>(this)->isStore();
 547   }
 548   case VPReplicateSC:
 549   case VPWidenCallSC:
 550     return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
 551         ->mayReadFromMemory();
 552   case VPBranchOnMaskSC:
 553     return false;
 554   case VPWidenIntOrFpInductionSC:
 555   case VPWidenCanonicalIVSC:
 556   case VPWidenPHISC:
 557   case VPBlendSC:
 558   case VPWidenSC:
 559   case VPWidenGEPSC:
 560   case VPReductionSC:
 561   case VPWidenSelectSC: {
 562     const Instruction *I =
 563         dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
 564     (void)I;
 565     assert((!I || !I->mayReadFromMemory()) &&
 566            "underlying instruction may read from memory");
 567     return false;
 568   }
 569   default:
 570     return true;
 571   }
 572 }
 573
 574 bool VPRecipeBase::mayHaveSideEffects() const {
 575   switch (getVPDefID()) {
 576   case VPBranchOnMaskSC:
 577     return false;
 578   case VPWidenIntOrFpInductionSC:
 579   case VPWidenCanonicalIVSC:
 580   case VPWidenPHISC:
 581   case VPBlendSC:
 582   case VPWidenSC:
 583   case VPWidenGEPSC:
 584   case VPReductionSC:
 585   case VPWidenSelectSC: {
 586     const Instruction *I =
 587         dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
 588     (void)I;
 589     assert((!I || !I->mayHaveSideEffects()) &&
 590            "underlying instruction has side-effects");
 591     return false;
 592   }
 593   case VPReplicateSC: {
 594     auto *R = cast<VPReplicateRecipe>(this);
 595     return R->getUnderlyingInstr()->mayHaveSideEffects();
 596   }
 597   default:
 598     return true;
 599   }
 600 }
 601
 602 void VPRecipeBase::insertBefore(VPRecipeBase *InsertPos) {
 603   assert(!Parent && "Recipe already in some VPBasicBlock");
 604   assert(InsertPos->getParent() &&
 605          "Insertion position not in any VPBasicBlock");
 606   Parent = InsertPos->getParent();
 607   Parent->getRecipeList().insert(InsertPos->getIterator(), this);
 608 }
 609
 610 void VPRecipeBase::insertAfter(VPRecipeBase *InsertPos) {
 611   assert(!Parent && "Recipe already in some VPBasicBlock");
 612   assert(InsertPos->getParent() &&
 613          "Insertion position not in any VPBasicBlock");
 614   Parent = InsertPos->getParent();
 615   Parent->getRecipeList().insertAfter(InsertPos->getIterator(), this);
 616 }
 617
 618 void VPRecipeBase::removeFromParent() {
 619   assert(getParent() && "Recipe not in any VPBasicBlock");
 620   getParent()->getRecipeList().remove(getIterator());
 621   Parent = nullptr;
 622 }
 623
 624 iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
 625   assert(getParent() && "Recipe not in any VPBasicBlock");
 626   return getParent()->getRecipeList().erase(getIterator());
 627 }
 628
 629 void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
 630   removeFromParent();
 631   insertAfter(InsertPos);
 632 }
 633
 634 void VPRecipeBase::moveBefore(VPBasicBlock &BB,
 635                               iplist<VPRecipeBase>::iterator I) {
 636   assert(I == BB.end() || I->getParent() == &BB);
 637   removeFromParent();
 638   Parent = &BB;
 639   BB.getRecipeList().insert(I, this);
 640 }
 641
 642 void VPInstruction::generateInstruction(VPTransformState &State,
 643                                         unsigned Part) {
 644   IRBuilder<> &Builder = State.Builder;
 645
 646   if (Instruction::isBinaryOp(getOpcode())) {
 647     Value *A = State.get(getOperand(0), Part);
 648     Value *B = State.get(getOperand(1), Part);
 649     Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
 650     State.set(this, V, Part);
 651     return;
 652   }
 653
 654   switch (getOpcode()) {
 655   case VPInstruction::Not: {
 656     Value *A = State.get(getOperand(0), Part);
 657     Value *V = Builder.CreateNot(A);
 658     State.set(this, V, Part);
 659     break;
 660   }
 661   case VPInstruction::ICmpULE: {
 662     Value *IV = State.get(getOperand(0), Part);
 663     Value *TC = State.get(getOperand(1), Part);
 664     Value *V = Builder.CreateICmpULE(IV, TC);
 665     State.set(this, V, Part);
 666     break;
 667   }
 668   case Instruction::Select: {
 669     Value *Cond = State.get(getOperand(0), Part);
 670     Value *Op1 = State.get(getOperand(1), Part);
 671     Value *Op2 = State.get(getOperand(2), Part);
 672     Value *V = Builder.CreateSelect(Cond, Op1, Op2);
 673     State.set(this, V, Part);
 674     break;
 675   }
 676   case VPInstruction::ActiveLaneMask: {
 677     // Get first lane of vector induction variable.
 678     Value *VIVElem0 = State.get(getOperand(0), VPIteration(Part, 0));
 679     // Get the original loop tripcount.
 680     Value *ScalarTC = State.TripCount;
 681
 682     auto *Int1Ty = Type::getInt1Ty(Builder.getContext());
 683     auto *PredTy = FixedVectorType::get(Int1Ty, State.VF.getKnownMinValue());
 684     Instruction *Call = Builder.CreateIntrinsic(
 685         Intrinsic::get_active_lane_mask, {PredTy, ScalarTC->getType()},
 686         {VIVElem0, ScalarTC}, nullptr, "active.lane.mask");
 687     State.set(this, Call, Part);
 688     break;
 689   }
 690   case VPInstruction::FirstOrderRecurrenceSplice: {
 691     // Generate code to combine the previous and current values in vector v3.
 692     //
 693     //   vector.ph:
 694     //     v_init = vector(..., ..., ..., a[-1])
 695     //     br vector.body
 696     //
 697     //   vector.body
 698     //     i = phi [0, vector.ph], [i+4, vector.body]
 699     //     v1 = phi [v_init, vector.ph], [v2, vector.body]
 700     //     v2 = a[i, i+1, i+2, i+3];
 701     //     v3 = vector(v1(3), v2(0, 1, 2))
 702
 703     // For the first part, use the recurrence phi (v1), otherwise v2.
 704     auto *V1 = State.get(getOperand(0), 0);
 705     Value *PartMinus1 = Part == 0 ? V1 : State.get(getOperand(1), Part - 1);
 706     if (!PartMinus1->getType()->isVectorTy()) {
 707       State.set(this, PartMinus1, Part);
 708     } else {
 709       Value *V2 = State.get(getOperand(1), Part);
 710       State.set(this, Builder.CreateVectorSplice(PartMinus1, V2, -1), Part);
 711     }
 712     break;
 713   }
 714   default:
 715     llvm_unreachable("Unsupported opcode for instruction");
 716   }
 717 }
 718
 719 void VPInstruction::execute(VPTransformState &State) {
 720   assert(!State.Instance && "VPInstruction executing an Instance");
 721   for (unsigned Part = 0; Part < State.UF; ++Part)
 722     generateInstruction(State, Part);
 723 }
 724
 725 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 726 void VPInstruction::dump() const {
 727   VPSlotTracker SlotTracker(getParent()->getPlan());
 728   print(dbgs(), "", SlotTracker);
 729 }
 730
 731 void VPInstruction::print(raw_ostream &O, const Twine &Indent,
 732                           VPSlotTracker &SlotTracker) const {
 733   O << Indent << "EMIT ";
 734
 735   if (hasResult()) {
 736     printAsOperand(O, SlotTracker);
 737     O << " = ";
 738   }
 739
 740   switch (getOpcode()) {
 741   case VPInstruction::Not:
 742     O << "not";
 743     break;
 744   case VPInstruction::ICmpULE:
 745     O << "icmp ule";
 746     break;
 747   case VPInstruction::SLPLoad:
 748     O << "combined load";
 749     break;
 750   case VPInstruction::SLPStore:
 751     O << "combined store";
 752     break;
 753   case VPInstruction::ActiveLaneMask:
 754     O << "active lane mask";
 755     break;
 756   case VPInstruction::FirstOrderRecurrenceSplice:
 757     O << "first-order splice";
 758     break;
 759   default:
 760     O << Instruction::getOpcodeName(getOpcode());
 761   }
 762
 763   for (const VPValue *Operand : operands()) {
 764     O << " ";
 765     Operand->printAsOperand(O, SlotTracker);
 766   }
 767 }
 768 #endif
 769
 770 /// Generate the code inside the body of the vectorized loop. Assumes a single
 771 /// LoopVectorBody basic-block was created for this. Introduce additional
 772 /// basic-blocks as needed, and fill them all.
 773 void VPlan::execute(VPTransformState *State) {
 774   // -1. Check if the backedge taken count is needed, and if so build it.
 775   if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
 776     Value *TC = State->TripCount;
 777     IRBuilder<> Builder(State->CFG.PrevBB->getTerminator());
 778     auto *TCMO = Builder.CreateSub(TC, ConstantInt::get(TC->getType(), 1),
 779                                    "trip.count.minus.1");
 780     auto VF = State->VF;
 781     Value *VTCMO =
 782         VF.isScalar() ? TCMO : Builder.CreateVectorSplat(VF, TCMO, "broadcast");
 783     for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part)
 784       State->set(BackedgeTakenCount, VTCMO, Part);
 785   }
 786
 787   // 0. Set the reverse mapping from VPValues to Values for code generation.
 788   for (auto &Entry : Value2VPValue)
 789     State->VPValue2Value[Entry.second] = Entry.first;
 790
 791   BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
 792   State->CFG.VectorPreHeader = VectorPreHeaderBB;
 793   BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
 794   assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
 795
 796   // 1. Make room to generate basic-blocks inside loop body if needed.
 797   BasicBlock *VectorLatchBB = VectorHeaderBB->splitBasicBlock(
 798       VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
 799   Loop *L = State->LI->getLoopFor(VectorHeaderBB);
 800   L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
 801   // Remove the edge between Header and Latch to allow other connections.
 802   // Temporarily terminate with unreachable until CFG is rewired.
 803   // Note: this asserts the generated code's assumption that
 804   // getFirstInsertionPt() can be dereferenced into an Instruction.
 805   VectorHeaderBB->getTerminator()->eraseFromParent();
 806   State->Builder.SetInsertPoint(VectorHeaderBB);
 807   UnreachableInst *Terminator = State->Builder.CreateUnreachable();
 808   State->Builder.SetInsertPoint(Terminator);
 809
 810   // 2. Generate code in loop body.
 811   State->CFG.PrevVPBB = nullptr;
 812   State->CFG.PrevBB = VectorHeaderBB;
 813   State->CFG.LastBB = VectorLatchBB;
 814
 815   for (VPBlockBase *Block : depth_first(Entry))
 816     Block->execute(State);
 817
 818   // Fix the latch value of reduction and first-order recurrences phis in the
 819   // vector loop.
 820   VPBasicBlock *Header = Entry->getEntryBasicBlock();
 821   for (VPRecipeBase &R : Header->phis()) {
 822     auto *PhiR = dyn_cast<VPWidenPHIRecipe>(&R);
 823     if (!PhiR || !(isa<VPFirstOrderRecurrencePHIRecipe>(&R) ||
 824                    isa<VPReductionPHIRecipe>(&R)))
 825       continue;
 826     // For first-order recurrences and in-order reduction phis, only a single
 827     // part is generated, which provides the last part from the previous
 828     // iteration. Otherwise all UF parts are generated.
 829     bool SinglePartNeeded = isa<VPFirstOrderRecurrencePHIRecipe>(&R) ||
 830                             cast<VPReductionPHIRecipe>(&R)->isOrdered();
 831     unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->UF;
 832     for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
 833       Value *VecPhi = State->get(PhiR, Part);
 834       Value *Val = State->get(PhiR->getBackedgeValue(),
 835                               SinglePartNeeded ? State->UF - 1 : Part);
 836       cast<PHINode>(VecPhi)->addIncoming(Val, VectorLatchBB);
 837     }
 838   }
 839
 840   // Setup branch terminator successors for VPBBs in VPBBsToFix based on
 841   // VPBB's successors.
 842   for (auto VPBB : State->CFG.VPBBsToFix) {
 843     assert(EnableVPlanNativePath &&
 844            "Unexpected VPBBsToFix in non VPlan-native path");
 845     BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB];
 846     assert(BB && "Unexpected null basic block for VPBB");
 847
 848     unsigned Idx = 0;
 849     auto *BBTerminator = BB->getTerminator();
 850
 851     for (VPBlockBase *SuccVPBlock : VPBB->getHierarchicalSuccessors()) {
 852       VPBasicBlock *SuccVPBB = SuccVPBlock->getEntryBasicBlock();
 853       BBTerminator->setSuccessor(Idx, State->CFG.VPBB2IRBB[SuccVPBB]);
 854       ++Idx;
 855     }
 856   }
 857
 858   // 3. Merge the temporary latch created with the last basic-block filled.
 859   BasicBlock *LastBB = State->CFG.PrevBB;
 860   // Connect LastBB to VectorLatchBB to facilitate their merge.
 861   assert((EnableVPlanNativePath ||
 862           isa<UnreachableInst>(LastBB->getTerminator())) &&
 863          "Expected InnerLoop VPlan CFG to terminate with unreachable");
 864   assert((!EnableVPlanNativePath || isa<BranchInst>(LastBB->getTerminator())) &&
 865          "Expected VPlan CFG to terminate with branch in NativePath");
 866   LastBB->getTerminator()->eraseFromParent();
 867   BranchInst::Create(VectorLatchBB, LastBB);
 868
 869   // Merge LastBB with Latch.
 870   bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
 871   (void)Merged;
 872   assert(Merged && "Could not merge last basic block with latch.");
 873   VectorLatchBB = LastBB;
 874
 875   // We do not attempt to preserve DT for outer loop vectorization currently.
 876   if (!EnableVPlanNativePath)
 877     updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB,
 878                         L->getExitBlock());
 879 }
 880
 881 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 882 LLVM_DUMP_METHOD
 883 void VPlan::print(raw_ostream &O) const {
 884   VPSlotTracker SlotTracker(this);
 885
 886   O << "VPlan '" << Name << "' {";
 887   for (const VPBlockBase *Block : depth_first(getEntry())) {
 888     O << '\n';
 889     Block->print(O, "", SlotTracker);
 890   }
 891   O << "}\n";
 892 }
 893
 894 LLVM_DUMP_METHOD
 895 void VPlan::printDOT(raw_ostream &O) const {
 896   VPlanPrinter Printer(O, *this);
 897   Printer.dump();
 898 }
 899
 900 LLVM_DUMP_METHOD
 901 void VPlan::dump() const { print(dbgs()); }
 902 #endif
 903
 904 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
 905                                 BasicBlock *LoopLatchBB,
 906                                 BasicBlock *LoopExitBB) {
 907   BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
 908   assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
 909   // The vector body may be more than a single basic-block by this point.
 910   // Update the dominator tree information inside the vector body by propagating
 911   // it from header to latch, expecting only triangular control-flow, if any.
 912   BasicBlock *PostDomSucc = nullptr;
 913   for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
 914     // Get the list of successors of this block.
 915     std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
 916     assert(Succs.size() <= 2 &&
 917            "Basic block in vector loop has more than 2 successors.");
 918     PostDomSucc = Succs[0];
 919     if (Succs.size() == 1) {
 920       assert(PostDomSucc->getSinglePredecessor() &&
 921              "PostDom successor has more than one predecessor.");
 922       DT->addNewBlock(PostDomSucc, BB);
 923       continue;
 924     }
 925     BasicBlock *InterimSucc = Succs[1];
 926     if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
 927       PostDomSucc = Succs[1];
 928       InterimSucc = Succs[0];
 929     }
 930     assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
 931            "One successor of a basic block does not lead to the other.");
 932     assert(InterimSucc->getSinglePredecessor() &&
 933            "Interim successor has more than one predecessor.");
 934     assert(PostDomSucc->hasNPredecessors(2) &&
 935            "PostDom successor has more than two predecessors.");
 936     DT->addNewBlock(InterimSucc, BB);
 937     DT->addNewBlock(PostDomSucc, BB);
 938   }
 939   // Latch block is a new dominator for the loop exit.
 940   DT->changeImmediateDominator(LoopExitBB, LoopLatchBB);
 941   assert(DT->verify(DominatorTree::VerificationLevel::Fast));
 942 }
 943
 944 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 945 Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
 946   return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
 947          Twine(getOrCreateBID(Block));
 948 }
 949
 950 Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
 951   const std::string &Name = Block->getName();
 952   if (!Name.empty())
 953     return Name;
 954   return "VPB" + Twine(getOrCreateBID(Block));
 955 }
 956
 957 void VPlanPrinter::dump() {
 958   Depth = 1;
 959   bumpIndent(0);
 960   OS << "digraph VPlan {\n";
 961   OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
 962   if (!Plan.getName().empty())
 963     OS << "\\n" << DOT::EscapeString(Plan.getName());
 964   if (Plan.BackedgeTakenCount) {
 965     OS << ", where:\\n";
 966     Plan.BackedgeTakenCount->print(OS, SlotTracker);
 967     OS << " := BackedgeTakenCount";
 968   }
 969   OS << "\"]\n";
 970   OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
 971   OS << "edge [fontname=Courier, fontsize=30]\n";
 972   OS << "compound=true\n";
 973
 974   for (const VPBlockBase *Block : depth_first(Plan.getEntry()))
 975     dumpBlock(Block);
 976
 977   OS << "}\n";
 978 }
 979
 980 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
 981   if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
 982     dumpBasicBlock(BasicBlock);
 983   else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
 984     dumpRegion(Region);
 985   else
 986     llvm_unreachable("Unsupported kind of VPBlock.");
 987 }
 988
 989 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
 990                             bool Hidden, const Twine &Label) {
 991   // Due to "dot" we print an edge between two regions as an edge between the
 992   // exit basic block and the entry basic of the respective regions.
 993   const VPBlockBase *Tail = From->getExitBasicBlock();
 994   const VPBlockBase *Head = To->getEntryBasicBlock();
 995   OS << Indent << getUID(Tail) << " -> " << getUID(Head);
 996   OS << " [ label=\"" << Label << '\"';
 997   if (Tail != From)
 998     OS << " ltail=" << getUID(From);
 999   if (Head != To)
1000     OS << " lhead=" << getUID(To);
1001   if (Hidden)
1002     OS << "; splines=none";
1003   OS << "]\n";
1004 }
1005
1006 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
1007   auto &Successors = Block->getSuccessors();
1008   if (Successors.size() == 1)
1009     drawEdge(Block, Successors.front(), false, "");
1010   else if (Successors.size() == 2) {
1011     drawEdge(Block, Successors.front(), false, "T");
1012     drawEdge(Block, Successors.back(), false, "F");
1013   } else {
1014     unsigned SuccessorNumber = 0;
1015     for (auto *Successor : Successors)
1016       drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
1017   }
1018 }
1019
1020 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
1021   // Implement dot-formatted dump by performing plain-text dump into the
1022   // temporary storage followed by some post-processing.
1023   OS << Indent << getUID(BasicBlock) << " [label =\n";
1024   bumpIndent(1);
1025   std::string Str;
1026   raw_string_ostream SS(Str);
1027   // Use no indentation as we need to wrap the lines into quotes ourselves.
1028   BasicBlock->print(SS, "", SlotTracker);
1029
1030   // We need to process each line of the output separately, so split
1031   // single-string plain-text dump.
1032   SmallVector<StringRef, 0> Lines;
1033   StringRef(Str).rtrim('\n').split(Lines, "\n");
1034
1035   auto EmitLine = [&](StringRef Line, StringRef Suffix) {
1036     OS << Indent << '"' << DOT::EscapeString(Line.str()) << "\\l\"" << Suffix;
1037   };
1038
1039   // Don't need the "+" after the last line.
1040   for (auto Line : make_range(Lines.begin(), Lines.end() - 1))
1041     EmitLine(Line, " +\n");
1042   EmitLine(Lines.back(), "\n");
1043
1044   bumpIndent(-1);
1045   OS << Indent << "]\n";
1046
1047   dumpEdges(BasicBlock);
1048 }
1049
1050 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
1051   OS << Indent << "subgraph " << getUID(Region) << " {\n";
1052   bumpIndent(1);
1053   OS << Indent << "fontname=Courier\n"
1054      << Indent << "label=\""
1055      << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
1056      << DOT::EscapeString(Region->getName()) << "\"\n";
1057   // Dump the blocks of the region.
1058   assert(Region->getEntry() && "Region contains no inner blocks.");
1059   for (const VPBlockBase *Block : depth_first(Region->getEntry()))
1060     dumpBlock(Block);
1061   bumpIndent(-1);
1062   OS << Indent << "}\n";
1063   dumpEdges(Region);
1064 }
1065
1066 void VPlanIngredient::print(raw_ostream &O) const {
1067   if (auto *Inst = dyn_cast<Instruction>(V)) {
1068     if (!Inst->getType()->isVoidTy()) {
1069       Inst->printAsOperand(O, false);
1070       O << " = ";
1071     }
1072     O << Inst->getOpcodeName() << " ";
1073     unsigned E = Inst->getNumOperands();
1074     if (E > 0) {
1075       Inst->getOperand(0)->printAsOperand(O, false);
1076       for (unsigned I = 1; I < E; ++I)
1077         Inst->getOperand(I)->printAsOperand(O << ", ", false);
1078     }
1079   } else // !Inst
1080     V->printAsOperand(O, false);
1081 }
1082
1083 void VPWidenCallRecipe::print(raw_ostream &O, const Twine &Indent,
1084                               VPSlotTracker &SlotTracker) const {
1085   O << Indent << "WIDEN-CALL ";
1086
1087   auto *CI = cast<CallInst>(getUnderlyingInstr());
1088   if (CI->getType()->isVoidTy())
1089     O << "void ";
1090   else {
1091     printAsOperand(O, SlotTracker);
1092     O << " = ";
1093   }
1094
1095   O << "call @" << CI->getCalledFunction()->getName() << "(";
1096   printOperands(O, SlotTracker);
1097   O << ")";
1098 }
1099
1100 void VPWidenSelectRecipe::print(raw_ostream &O, const Twine &Indent,
1101                                 VPSlotTracker &SlotTracker) const {
1102   O << Indent << "WIDEN-SELECT ";
1103   printAsOperand(O, SlotTracker);
1104   O << " = select ";
1105   getOperand(0)->printAsOperand(O, SlotTracker);
1106   O << ", ";
1107   getOperand(1)->printAsOperand(O, SlotTracker);
1108   O << ", ";
1109   getOperand(2)->printAsOperand(O, SlotTracker);
1110   O << (InvariantCond ? " (condition is loop invariant)" : "");
1111 }
1112
1113 void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent,
1114                           VPSlotTracker &SlotTracker) const {
1115   O << Indent << "WIDEN ";
1116   printAsOperand(O, SlotTracker);
1117   O << " = " << getUnderlyingInstr()->getOpcodeName() << " ";
1118   printOperands(O, SlotTracker);
1119 }
1120
1121 void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O, const Twine &Indent,
1122                                           VPSlotTracker &SlotTracker) const {
1123   O << Indent << "WIDEN-INDUCTION";
1124   if (getTruncInst()) {
1125     O << "\\l\"";
1126     O << " +\n" << Indent << "\"  " << VPlanIngredient(IV) << "\\l\"";
1127     O << " +\n" << Indent << "\"  ";
1128     getVPValue(0)->printAsOperand(O, SlotTracker);
1129   } else
1130     O << " " << VPlanIngredient(IV);
1131 }
1132
1133 void VPWidenGEPRecipe::print(raw_ostream &O, const Twine &Indent,
1134                              VPSlotTracker &SlotTracker) const {
1135   O << Indent << "WIDEN-GEP ";
1136   O << (IsPtrLoopInvariant ? "Inv" : "Var");
1137   size_t IndicesNumber = IsIndexLoopInvariant.size();
1138   for (size_t I = 0; I < IndicesNumber; ++I)
1139     O << "[" << (IsIndexLoopInvariant[I] ? "Inv" : "Var") << "]";
1140
1141   O << " ";
1142   printAsOperand(O, SlotTracker);
1143   O << " = getelementptr ";
1144   printOperands(O, SlotTracker);
1145 }
1146
1147 void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent,
1148                              VPSlotTracker &SlotTracker) const {
1149   O << Indent << "WIDEN-PHI ";
1150
1151   auto *OriginalPhi = cast<PHINode>(getUnderlyingValue());
1152   // Unless all incoming values are modeled in VPlan  print the original PHI
1153   // directly.
1154   // TODO: Remove once all VPWidenPHIRecipe instances keep all relevant incoming
1155   // values as VPValues.
1156   if (getNumOperands() != OriginalPhi->getNumOperands()) {
1157     O << VPlanIngredient(OriginalPhi);
1158     return;
1159   }
1160
1161   printAsOperand(O, SlotTracker);
1162   O << " = phi ";
1163   printOperands(O, SlotTracker);
1164 }
1165
1166 void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent,
1167                           VPSlotTracker &SlotTracker) const {
1168   O << Indent << "BLEND ";
1169   Phi->printAsOperand(O, false);
1170   O << " =";
1171   if (getNumIncomingValues() == 1) {
1172     // Not a User of any mask: not really blending, this is a
1173     // single-predecessor phi.
1174     O << " ";
1175     getIncomingValue(0)->printAsOperand(O, SlotTracker);
1176   } else {
1177     for (unsigned I = 0, E = getNumIncomingValues(); I < E; ++I) {
1178       O << " ";
1179       getIncomingValue(I)->printAsOperand(O, SlotTracker);
1180       O << "/";
1181       getMask(I)->printAsOperand(O, SlotTracker);
1182     }
1183   }
1184 }
1185
1186 void VPReductionRecipe::print(raw_ostream &O, const Twine &Indent,
1187                               VPSlotTracker &SlotTracker) const {
1188   O << Indent << "REDUCE ";
1189   printAsOperand(O, SlotTracker);
1190   O << " = ";
1191   getChainOp()->printAsOperand(O, SlotTracker);
1192   O << " + reduce." << Instruction::getOpcodeName(RdxDesc->getOpcode())
1193     << " (";
1194   getVecOp()->printAsOperand(O, SlotTracker);
1195   if (getCondOp()) {
1196     O << ", ";
1197     getCondOp()->printAsOperand(O, SlotTracker);
1198   }
1199   O << ")";
1200 }
1201
1202 void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent,
1203                               VPSlotTracker &SlotTracker) const {
1204   O << Indent << (IsUniform ? "CLONE " : "REPLICATE ");
1205
1206   if (!getUnderlyingInstr()->getType()->isVoidTy()) {
1207     printAsOperand(O, SlotTracker);
1208     O << " = ";
1209   }
1210   O << Instruction::getOpcodeName(getUnderlyingInstr()->getOpcode()) << " ";
1211   printOperands(O, SlotTracker);
1212
1213   if (AlsoPack)
1214     O << " (S->V)";
1215 }
1216
1217 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent,
1218                                 VPSlotTracker &SlotTracker) const {
1219   O << Indent << "PHI-PREDICATED-INSTRUCTION ";
1220   printAsOperand(O, SlotTracker);
1221   O << " = ";
1222   printOperands(O, SlotTracker);
1223 }
1224
1225 void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, const Twine &Indent,
1226                                            VPSlotTracker &SlotTracker) const {
1227   O << Indent << "WIDEN ";
1228
1229   if (!isStore()) {
1230     getVPSingleValue()->printAsOperand(O, SlotTracker);
1231     O << " = ";
1232   }
1233   O << Instruction::getOpcodeName(Ingredient.getOpcode()) << " ";
1234
1235   printOperands(O, SlotTracker);
1236 }
1237 #endif
1238
1239 void VPWidenCanonicalIVRecipe::execute(VPTransformState &State) {
1240   Value *CanonicalIV = State.CanonicalIV;
1241   Type *STy = CanonicalIV->getType();
1242   IRBuilder<> Builder(State.CFG.PrevBB->getTerminator());
1243   ElementCount VF = State.VF;
1244   assert(!VF.isScalable() && "the code following assumes non scalables ECs");
1245   Value *VStart = VF.isScalar()
1246                       ? CanonicalIV
1247                       : Builder.CreateVectorSplat(VF.getKnownMinValue(),
1248                                                   CanonicalIV, "broadcast");
1249   for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part) {
1250     SmallVector<Constant *, 8> Indices;
1251     for (unsigned Lane = 0; Lane < VF.getKnownMinValue(); ++Lane)
1252       Indices.push_back(
1253           ConstantInt::get(STy, Part * VF.getKnownMinValue() + Lane));
1254     // If VF == 1, there is only one iteration in the loop above, thus the
1255     // element pushed back into Indices is ConstantInt::get(STy, Part)
1256     Constant *VStep =
1257         VF.isScalar() ? Indices.back() : ConstantVector::get(Indices);
1258     // Add the consecutive indices to the vector value.
1259     Value *CanonicalVectorIV = Builder.CreateAdd(VStart, VStep, "vec.iv");
1260     State.set(getVPSingleValue(), CanonicalVectorIV, Part);
1261   }
1262 }
1263
1264 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1265 void VPWidenCanonicalIVRecipe::print(raw_ostream &O, const Twine &Indent,
1266                                      VPSlotTracker &SlotTracker) const {
1267   O << Indent << "EMIT ";
1268   getVPSingleValue()->printAsOperand(O, SlotTracker);
1269   O << " = WIDEN-CANONICAL-INDUCTION";
1270 }
1271 #endif
1272
1273 void VPFirstOrderRecurrencePHIRecipe::execute(VPTransformState &State) {
1274   auto &Builder = State.Builder;
1275   // Create a vector from the initial value.
1276   auto *VectorInit = getStartValue()->getLiveInIRValue();
1277
1278   Type *VecTy = State.VF.isScalar()
1279                     ? VectorInit->getType()
1280                     : VectorType::get(VectorInit->getType(), State.VF);
1281
1282   if (State.VF.isVector()) {
1283     auto *IdxTy = Builder.getInt32Ty();
1284     auto *One = ConstantInt::get(IdxTy, 1);
1285     IRBuilder<>::InsertPointGuard Guard(Builder);
1286     Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
1287     auto *RuntimeVF = getRuntimeVF(Builder, IdxTy, State.VF);
1288     auto *LastIdx = Builder.CreateSub(RuntimeVF, One);
1289     VectorInit = Builder.CreateInsertElement(
1290         PoisonValue::get(VecTy), VectorInit, LastIdx, "vector.recur.init");
1291   }
1292
1293   // Create a phi node for the new recurrence.
1294   PHINode *EntryPart = PHINode::Create(
1295       VecTy, 2, "vector.recur", &*State.CFG.PrevBB->getFirstInsertionPt());
1296   EntryPart->addIncoming(VectorInit, State.CFG.VectorPreHeader);
1297   State.set(this, EntryPart, 0);
1298 }
1299
1300 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1301 void VPFirstOrderRecurrencePHIRecipe::print(raw_ostream &O, const Twine &Indent,
1302                                             VPSlotTracker &SlotTracker) const {
1303   O << Indent << "FIRST-ORDER-RECURRENCE-PHI ";
1304   printAsOperand(O, SlotTracker);
1305   O << " = phi ";
1306   printOperands(O, SlotTracker);
1307 }
1308 #endif
1309
1310 void VPReductionPHIRecipe::execute(VPTransformState &State) {
1311   PHINode *PN = cast<PHINode>(getUnderlyingValue());
1312   auto &Builder = State.Builder;
1313
1314   // In order to support recurrences we need to be able to vectorize Phi nodes.
1315   // Phi nodes have cycles, so we need to vectorize them in two stages. This is
1316   // stage #1: We create a new vector PHI node with no incoming edges. We'll use
1317   // this value when we vectorize all of the instructions that use the PHI.
1318   bool ScalarPHI = State.VF.isScalar() || IsInLoop;
1319   Type *VecTy =
1320       ScalarPHI ? PN->getType() : VectorType::get(PN->getType(), State.VF);
1321
1322   BasicBlock *HeaderBB = State.CFG.PrevBB;
1323   assert(State.LI->getLoopFor(HeaderBB)->getHeader() == HeaderBB &&
1324          "recipe must be in the vector loop header");
1325   unsigned LastPartForNewPhi = isOrdered() ? 1 : State.UF;
1326   for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
1327     Value *EntryPart =
1328         PHINode::Create(VecTy, 2, "vec.phi", &*HeaderBB->getFirstInsertionPt());
1329     State.set(this, EntryPart, Part);
1330   }
1331
1332   // Reductions do not have to start at zero. They can start with
1333   // any loop invariant values.
1334   VPValue *StartVPV = getStartValue();
1335   Value *StartV = StartVPV->getLiveInIRValue();
1336
1337   Value *Iden = nullptr;
1338   RecurKind RK = RdxDesc.getRecurrenceKind();
1339   if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RK)) {
1340     // MinMax reduction have the start value as their identify.
1341     if (ScalarPHI) {
1342       Iden = StartV;
1343     } else {
1344       IRBuilderBase::InsertPointGuard IPBuilder(Builder);
1345       Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
1346       StartV = Iden =
1347           Builder.CreateVectorSplat(State.VF, StartV, "minmax.ident");
1348     }
1349   } else {
1350     Constant *IdenC = RecurrenceDescriptor::getRecurrenceIdentity(
1351         RK, VecTy->getScalarType(), RdxDesc.getFastMathFlags());
1352     Iden = IdenC;
1353
1354     if (!ScalarPHI) {
1355       Iden = ConstantVector::getSplat(State.VF, IdenC);
1356       IRBuilderBase::InsertPointGuard IPBuilder(Builder);
1357       Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
1358       Constant *Zero = Builder.getInt32(0);
1359       StartV = Builder.CreateInsertElement(Iden, StartV, Zero);
1360     }
1361   }
1362
1363   for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
1364     Value *EntryPart = State.get(this, Part);
1365     // Make sure to add the reduction start value only to the
1366     // first unroll part.
1367     Value *StartVal = (Part == 0) ? StartV : Iden;
1368     cast<PHINode>(EntryPart)->addIncoming(StartVal, State.CFG.VectorPreHeader);
1369   }
1370 }
1371
1372 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1373 void VPReductionPHIRecipe::print(raw_ostream &O, const Twine &Indent,
1374                                  VPSlotTracker &SlotTracker) const {
1375   O << Indent << "WIDEN-REDUCTION-PHI ";
1376
1377   printAsOperand(O, SlotTracker);
1378   O << " = phi ";
1379   printOperands(O, SlotTracker);
1380 }
1381 #endif
1382
1383 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
1384
1385 void VPValue::replaceAllUsesWith(VPValue *New) {
1386   for (unsigned J = 0; J < getNumUsers();) {
1387     VPUser *User = Users[J];
1388     unsigned NumUsers = getNumUsers();
1389     for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
1390       if (User->getOperand(I) == this)
1391         User->setOperand(I, New);
1392     // If a user got removed after updating the current user, the next user to
1393     // update will be moved to the current position, so we only need to
1394     // increment the index if the number of users did not change.
1395     if (NumUsers == getNumUsers())
1396       J++;
1397   }
1398 }
1399
1400 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1401 void VPValue::printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const {
1402   if (const Value *UV = getUnderlyingValue()) {
1403     OS << "ir<";
1404     UV->printAsOperand(OS, false);
1405     OS << ">";
1406     return;
1407   }
1408
1409   unsigned Slot = Tracker.getSlot(this);
1410   if (Slot == unsigned(-1))
1411     OS << "<badref>";
1412   else
1413     OS << "vp<%" << Tracker.getSlot(this) << ">";
1414 }
1415
1416 void VPUser::printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const {
1417   interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) {
1418     Op->printAsOperand(O, SlotTracker);
1419   });
1420 }
1421 #endif
1422
1423 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
1424                                           Old2NewTy &Old2New,
1425                                           InterleavedAccessInfo &IAI) {
1426   ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry());
1427   for (VPBlockBase *Base : RPOT) {
1428     visitBlock(Base, Old2New, IAI);
1429   }
1430 }
1431
1432 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
1433                                          InterleavedAccessInfo &IAI) {
1434   if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
1435     for (VPRecipeBase &VPI : *VPBB) {
1436       if (isa<VPWidenPHIRecipe>(&VPI))
1437         continue;
1438       assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
1439       auto *VPInst = cast<VPInstruction>(&VPI);
1440       auto *Inst = cast<Instruction>(VPInst->getUnderlyingValue());
1441       auto *IG = IAI.getInterleaveGroup(Inst);
1442       if (!IG)
1443         continue;
1444
1445       auto NewIGIter = Old2New.find(IG);
1446       if (NewIGIter == Old2New.end())
1447         Old2New[IG] = new InterleaveGroup<VPInstruction>(
1448             IG->getFactor(), IG->isReverse(), IG->getAlign());
1449
1450       if (Inst == IG->getInsertPos())
1451         Old2New[IG]->setInsertPos(VPInst);
1452
1453       InterleaveGroupMap[VPInst] = Old2New[IG];
1454       InterleaveGroupMap[VPInst]->insertMember(
1455           VPInst, IG->getIndex(Inst),
1456           Align(IG->isReverse() ? (-1) * int(IG->getFactor())
1457                                 : IG->getFactor()));
1458     }
1459   } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1460     visitRegion(Region, Old2New, IAI);
1461   else
1462     llvm_unreachable("Unsupported kind of VPBlock.");
1463 }
1464
1465 VPInterleavedAccessInfo::VPInterleavedAccessInfo(VPlan &Plan,
1466                                                  InterleavedAccessInfo &IAI) {
1467   Old2NewTy Old2New;
1468   visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI);
1469 }
1470
1471 void VPSlotTracker::assignSlot(const VPValue *V) {
1472   assert(Slots.find(V) == Slots.end() && "VPValue already has a slot!");
1473   Slots[V] = NextSlot++;
1474 }
1475
1476 void VPSlotTracker::assignSlots(const VPlan &Plan) {
1477
1478   for (const VPValue *V : Plan.VPExternalDefs)
1479     assignSlot(V);
1480
1481   if (Plan.BackedgeTakenCount)
1482     assignSlot(Plan.BackedgeTakenCount);
1483
1484   ReversePostOrderTraversal<
1485       VPBlockRecursiveTraversalWrapper<const VPBlockBase *>>
1486       RPOT(VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(
1487           Plan.getEntry()));
1488   for (const VPBasicBlock *VPBB :
1489        VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
1490     for (const VPRecipeBase &Recipe : *VPBB)
1491       for (VPValue *Def : Recipe.definedValues())
1492         assignSlot(Def);
1493 }