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