LLVM  9.0.0svn
VPlan.cpp
Go to the documentation of this file.
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"
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"
40 #include <cassert>
41 #include <iterator>
42 #include <string>
43 #include <vector>
44 
45 using namespace llvm;
47 
48 #define DEBUG_TYPE "vplan"
49 
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.
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 
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.
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 
82  VPBlockBase *Block = this;
83  while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
84  Block = Region->getExit();
85  return cast<VPBasicBlock>(Block);
86 }
87 
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 
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 
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 
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.
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 
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 
278  Parent = InsertPos->getParent();
279  Parent->getRecipeList().insert(InsertPos->getIterator(), this);
280 }
281 
283  return getParent()->getRecipeList().erase(getIterator());
284 }
285 
286 void VPInstruction::generateInstruction(VPTransformState &State,
287  unsigned Part) {
288  IRBuilder<> &Builder = State.Builder;
289 
291  Value *A = State.get(getOperand(0), Part);
292  Value *B = State.get(getOperand(1), Part);
293  Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
294  State.set(this, V, Part);
295  return;
296  }
297 
298  switch (getOpcode()) {
299  case VPInstruction::Not: {
300  Value *A = State.get(getOperand(0), Part);
301  Value *V = Builder.CreateNot(A);
302  State.set(this, V, Part);
303  break;
304  }
305  case VPInstruction::ICmpULE: {
306  Value *IV = State.get(getOperand(0), Part);
307  Value *TC = State.get(getOperand(1), Part);
308  Value *V = Builder.CreateICmpULE(IV, TC);
309  State.set(this, V, Part);
310  break;
311  }
312  default:
313  llvm_unreachable("Unsupported opcode for instruction");
314  }
315 }
316 
318  assert(!State.Instance && "VPInstruction executing an Instance");
319  for (unsigned Part = 0; Part < State.UF; ++Part)
320  generateInstruction(State, Part);
321 }
322 
323 void VPInstruction::print(raw_ostream &O, const Twine &Indent) const {
324  O << " +\n" << Indent << "\"EMIT ";
325  print(O);
326  O << "\\l\"";
327 }
328 
330  printAsOperand(O);
331  O << " = ";
332 
333  switch (getOpcode()) {
334  case VPInstruction::Not:
335  O << "not";
336  break;
338  O << "icmp ule";
339  break;
341  O << "combined load";
342  break;
344  O << "combined store";
345  break;
346  default:
348  }
349 
350  for (const VPValue *Operand : operands()) {
351  O << " ";
352  Operand->printAsOperand(O);
353  }
354 }
355 
356 /// Generate the code inside the body of the vectorized loop. Assumes a single
357 /// LoopVectorBody basic-block was created for this. Introduce additional
358 /// basic-blocks as needed, and fill them all.
360  // -1. Check if the backedge taken count is needed, and if so build it.
361  if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
362  Value *TC = State->TripCount;
363  IRBuilder<> Builder(State->CFG.PrevBB->getTerminator());
364  auto *TCMO = Builder.CreateSub(TC, ConstantInt::get(TC->getType(), 1),
365  "trip.count.minus.1");
366  Value2VPValue[TCMO] = BackedgeTakenCount;
367  }
368 
369  // 0. Set the reverse mapping from VPValues to Values for code generation.
370  for (auto &Entry : Value2VPValue)
371  State->VPValue2Value[Entry.second] = Entry.first;
372 
373  BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
374  BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
375  assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
376 
377  // 1. Make room to generate basic-blocks inside loop body if needed.
378  BasicBlock *VectorLatchBB = VectorHeaderBB->splitBasicBlock(
379  VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
380  Loop *L = State->LI->getLoopFor(VectorHeaderBB);
381  L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
382  // Remove the edge between Header and Latch to allow other connections.
383  // Temporarily terminate with unreachable until CFG is rewired.
384  // Note: this asserts the generated code's assumption that
385  // getFirstInsertionPt() can be dereferenced into an Instruction.
386  VectorHeaderBB->getTerminator()->eraseFromParent();
387  State->Builder.SetInsertPoint(VectorHeaderBB);
389  State->Builder.SetInsertPoint(Terminator);
390 
391  // 2. Generate code in loop body.
392  State->CFG.PrevVPBB = nullptr;
393  State->CFG.PrevBB = VectorHeaderBB;
394  State->CFG.LastBB = VectorLatchBB;
395 
396  for (VPBlockBase *Block : depth_first(Entry))
397  Block->execute(State);
398 
399  // Setup branch terminator successors for VPBBs in VPBBsToFix based on
400  // VPBB's successors.
401  for (auto VPBB : State->CFG.VPBBsToFix) {
402  assert(EnableVPlanNativePath &&
403  "Unexpected VPBBsToFix in non VPlan-native path");
404  BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB];
405  assert(BB && "Unexpected null basic block for VPBB");
406 
407  unsigned Idx = 0;
408  auto *BBTerminator = BB->getTerminator();
409 
410  for (VPBlockBase *SuccVPBlock : VPBB->getHierarchicalSuccessors()) {
411  VPBasicBlock *SuccVPBB = SuccVPBlock->getEntryBasicBlock();
412  BBTerminator->setSuccessor(Idx, State->CFG.VPBB2IRBB[SuccVPBB]);
413  ++Idx;
414  }
415  }
416 
417  // 3. Merge the temporary latch created with the last basic-block filled.
418  BasicBlock *LastBB = State->CFG.PrevBB;
419  // Connect LastBB to VectorLatchBB to facilitate their merge.
420  assert((EnableVPlanNativePath ||
421  isa<UnreachableInst>(LastBB->getTerminator())) &&
422  "Expected InnerLoop VPlan CFG to terminate with unreachable");
423  assert((!EnableVPlanNativePath || isa<BranchInst>(LastBB->getTerminator())) &&
424  "Expected VPlan CFG to terminate with branch in NativePath");
425  LastBB->getTerminator()->eraseFromParent();
426  BranchInst::Create(VectorLatchBB, LastBB);
427 
428  // Merge LastBB with Latch.
429  bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
430  (void)Merged;
431  assert(Merged && "Could not merge last basic block with latch.");
432  VectorLatchBB = LastBB;
433 
434  // We do not attempt to preserve DT for outer loop vectorization currently.
435  if (!EnableVPlanNativePath)
436  updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB);
437 }
438 
439 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
440  BasicBlock *LoopLatchBB) {
441  BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
442  assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
443  DT->addNewBlock(LoopHeaderBB, LoopPreHeaderBB);
444  // The vector body may be more than a single basic-block by this point.
445  // Update the dominator tree information inside the vector body by propagating
446  // it from header to latch, expecting only triangular control-flow, if any.
447  BasicBlock *PostDomSucc = nullptr;
448  for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
449  // Get the list of successors of this block.
450  std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
451  assert(Succs.size() <= 2 &&
452  "Basic block in vector loop has more than 2 successors.");
453  PostDomSucc = Succs[0];
454  if (Succs.size() == 1) {
455  assert(PostDomSucc->getSinglePredecessor() &&
456  "PostDom successor has more than one predecessor.");
457  DT->addNewBlock(PostDomSucc, BB);
458  continue;
459  }
460  BasicBlock *InterimSucc = Succs[1];
461  if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
462  PostDomSucc = Succs[1];
463  InterimSucc = Succs[0];
464  }
465  assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
466  "One successor of a basic block does not lead to the other.");
467  assert(InterimSucc->getSinglePredecessor() &&
468  "Interim successor has more than one predecessor.");
469  assert(PostDomSucc->hasNPredecessors(2) &&
470  "PostDom successor has more than two predecessors.");
471  DT->addNewBlock(InterimSucc, BB);
472  DT->addNewBlock(PostDomSucc, BB);
473  }
474 }
475 
476 const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
477  return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
478  Twine(getOrCreateBID(Block));
479 }
480 
481 const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
482  const std::string &Name = Block->getName();
483  if (!Name.empty())
484  return Name;
485  return "VPB" + Twine(getOrCreateBID(Block));
486 }
487 
488 void VPlanPrinter::dump() {
489  Depth = 1;
490  bumpIndent(0);
491  OS << "digraph VPlan {\n";
492  OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
493  if (!Plan.getName().empty())
494  OS << "\\n" << DOT::EscapeString(Plan.getName());
495  if (!Plan.Value2VPValue.empty() || Plan.BackedgeTakenCount) {
496  OS << ", where:";
497  if (Plan.BackedgeTakenCount)
498  OS << "\\n"
499  << *Plan.getOrCreateBackedgeTakenCount() << " := BackedgeTakenCount";
500  for (auto Entry : Plan.Value2VPValue) {
501  OS << "\\n" << *Entry.second;
502  OS << DOT::EscapeString(" := ");
503  Entry.first->printAsOperand(OS, false);
504  }
505  }
506  OS << "\"]\n";
507  OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
508  OS << "edge [fontname=Courier, fontsize=30]\n";
509  OS << "compound=true\n";
510 
511  for (VPBlockBase *Block : depth_first(Plan.getEntry()))
512  dumpBlock(Block);
513 
514  OS << "}\n";
515 }
516 
517 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
518  if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
519  dumpBasicBlock(BasicBlock);
520  else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
521  dumpRegion(Region);
522  else
523  llvm_unreachable("Unsupported kind of VPBlock.");
524 }
525 
526 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
527  bool Hidden, const Twine &Label) {
528  // Due to "dot" we print an edge between two regions as an edge between the
529  // exit basic block and the entry basic of the respective regions.
530  const VPBlockBase *Tail = From->getExitBasicBlock();
531  const VPBlockBase *Head = To->getEntryBasicBlock();
532  OS << Indent << getUID(Tail) << " -> " << getUID(Head);
533  OS << " [ label=\"" << Label << '\"';
534  if (Tail != From)
535  OS << " ltail=" << getUID(From);
536  if (Head != To)
537  OS << " lhead=" << getUID(To);
538  if (Hidden)
539  OS << "; splines=none";
540  OS << "]\n";
541 }
542 
543 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
544  auto &Successors = Block->getSuccessors();
545  if (Successors.size() == 1)
546  drawEdge(Block, Successors.front(), false, "");
547  else if (Successors.size() == 2) {
548  drawEdge(Block, Successors.front(), false, "T");
549  drawEdge(Block, Successors.back(), false, "F");
550  } else {
551  unsigned SuccessorNumber = 0;
552  for (auto *Successor : Successors)
553  drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
554  }
555 }
556 
557 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
558  OS << Indent << getUID(BasicBlock) << " [label =\n";
559  bumpIndent(1);
560  OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\"";
561  bumpIndent(1);
562 
563  // Dump the block predicate.
564  const VPValue *Pred = BasicBlock->getPredicate();
565  if (Pred) {
566  OS << " +\n" << Indent << " \"BlockPredicate: ";
567  if (const VPInstruction *PredI = dyn_cast<VPInstruction>(Pred)) {
568  PredI->printAsOperand(OS);
569  OS << " (" << DOT::EscapeString(PredI->getParent()->getName())
570  << ")\\l\"";
571  } else
572  Pred->printAsOperand(OS);
573  }
574 
575  for (const VPRecipeBase &Recipe : *BasicBlock)
576  Recipe.print(OS, Indent);
577 
578  // Dump the condition bit.
579  const VPValue *CBV = BasicBlock->getCondBit();
580  if (CBV) {
581  OS << " +\n" << Indent << " \"CondBit: ";
582  if (const VPInstruction *CBI = dyn_cast<VPInstruction>(CBV)) {
583  CBI->printAsOperand(OS);
584  OS << " (" << DOT::EscapeString(CBI->getParent()->getName()) << ")\\l\"";
585  } else {
586  CBV->printAsOperand(OS);
587  OS << "\"";
588  }
589  }
590 
591  bumpIndent(-2);
592  OS << "\n" << Indent << "]\n";
593  dumpEdges(BasicBlock);
594 }
595 
596 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
597  OS << Indent << "subgraph " << getUID(Region) << " {\n";
598  bumpIndent(1);
599  OS << Indent << "fontname=Courier\n"
600  << Indent << "label=\""
601  << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
602  << DOT::EscapeString(Region->getName()) << "\"\n";
603  // Dump the blocks of the region.
604  assert(Region->getEntry() && "Region contains no inner blocks.");
605  for (const VPBlockBase *Block : depth_first(Region->getEntry()))
606  dumpBlock(Block);
607  bumpIndent(-1);
608  OS << Indent << "}\n";
609  dumpEdges(Region);
610 }
611 
612 void VPlanPrinter::printAsIngredient(raw_ostream &O, Value *V) {
613  std::string IngredientString;
614  raw_string_ostream RSO(IngredientString);
615  if (auto *Inst = dyn_cast<Instruction>(V)) {
616  if (!Inst->getType()->isVoidTy()) {
617  Inst->printAsOperand(RSO, false);
618  RSO << " = ";
619  }
620  RSO << Inst->getOpcodeName() << " ";
621  unsigned E = Inst->getNumOperands();
622  if (E > 0) {
623  Inst->getOperand(0)->printAsOperand(RSO, false);
624  for (unsigned I = 1; I < E; ++I)
625  Inst->getOperand(I)->printAsOperand(RSO << ", ", false);
626  }
627  } else // !Inst
628  V->printAsOperand(RSO, false);
629  RSO.flush();
630  O << DOT::EscapeString(IngredientString);
631 }
632 
633 void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent) const {
634  O << " +\n" << Indent << "\"WIDEN\\l\"";
635  for (auto &Instr : make_range(Begin, End))
636  O << " +\n" << Indent << "\" " << VPlanIngredient(&Instr) << "\\l\"";
637 }
638 
640  const Twine &Indent) const {
641  O << " +\n" << Indent << "\"WIDEN-INDUCTION";
642  if (Trunc) {
643  O << "\\l\"";
644  O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
645  O << " +\n" << Indent << "\" " << VPlanIngredient(Trunc) << "\\l\"";
646  } else
647  O << " " << VPlanIngredient(IV) << "\\l\"";
648 }
649 
650 void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
651  O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\"";
652 }
653 
654 void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent) const {
655  O << " +\n" << Indent << "\"BLEND ";
656  Phi->printAsOperand(O, false);
657  O << " =";
658  if (!User) {
659  // Not a User of any mask: not really blending, this is a
660  // single-predecessor phi.
661  O << " ";
662  Phi->getIncomingValue(0)->printAsOperand(O, false);
663  } else {
664  for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
665  O << " ";
666  Phi->getIncomingValue(I)->printAsOperand(O, false);
667  O << "/";
669  }
670  }
671  O << "\\l\"";
672 }
673 
674 void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent) const {
675  O << " +\n"
676  << Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
677  << VPlanIngredient(Ingredient);
678  if (AlsoPack)
679  O << " (S->V)";
680  O << "\\l\"";
681 }
682 
683 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
684  O << " +\n"
685  << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst)
686  << "\\l\"";
687 }
688 
690  const Twine &Indent) const {
691  O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
692  if (User) {
693  O << ", ";
695  }
696  O << "\\l\"";
697 }
698 
699 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
700 
702  for (VPUser *User : users())
703  for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
704  if (User->getOperand(I) == this)
705  User->setOperand(I, New);
706 }
707 
708 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
709  Old2NewTy &Old2New,
710  InterleavedAccessInfo &IAI) {
712  for (VPBlockBase *Base : RPOT) {
713  visitBlock(Base, Old2New, IAI);
714  }
715 }
716 
717 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
718  InterleavedAccessInfo &IAI) {
719  if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
720  for (VPRecipeBase &VPI : *VPBB) {
721  assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
722  auto *VPInst = cast<VPInstruction>(&VPI);
723  auto *Inst = cast<Instruction>(VPInst->getUnderlyingValue());
724  auto *IG = IAI.getInterleaveGroup(Inst);
725  if (!IG)
726  continue;
727 
728  auto NewIGIter = Old2New.find(IG);
729  if (NewIGIter == Old2New.end())
730  Old2New[IG] = new InterleaveGroup<VPInstruction>(
731  IG->getFactor(), IG->isReverse(), IG->getAlignment());
732 
733  if (Inst == IG->getInsertPos())
734  Old2New[IG]->setInsertPos(VPInst);
735 
736  InterleaveGroupMap[VPInst] = Old2New[IG];
737  InterleaveGroupMap[VPInst]->insertMember(
738  VPInst, IG->getIndex(Inst),
739  IG->isReverse() ? (-1) * int(IG->getFactor()) : IG->getFactor());
740  }
741  } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
742  visitRegion(Region, Old2New, IAI);
743  else
744  llvm_unreachable("Unsupported kind of VPBlock.");
745 }
746 
748  InterleavedAccessInfo &IAI) {
749  Old2NewTy Old2New;
750  visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI);
751 }
const std::string & getName() const
Definition: VPlan.h:399
LoopInfo * LI
Hold a pointer to LoopInfo to register new basic blocks in the loop.
Definition: VPlan.h:306
struct llvm::VPTransformState::CFGState CFG
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:639
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
void execute(struct VPTransformState *State)
Generate the IR code for this VPlan.
Definition: VPlan.cpp:359
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1458
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Optional< VPIteration > Instance
Hold the indices to generate specific scalar instructions.
Definition: VPlan.h:247
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr)
Attempts to merge a block into its predecessor, if possible.
VPRegionBlock * getParent()
Definition: VPlan.h:408
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:1147
BasicBlock * PrevBB
The previous IR BasicBlock created or used.
Definition: VPlan.h:288
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1067
This file implements dominator tree analysis for a single level of a VPlan&#39;s H-CFG.
IRBuilder & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Definition: VPlan.h:312
iplist< VPRecipeBase >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: VPlan.cpp:282
const VPBasicBlock * getExitBasicBlock() const
Definition: VPlan.cpp:74
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
Value * CreateICmpULE(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:2078
BlockT * getExit() const
Get the exit BasicBlock of the Region.
Definition: RegionInfo.h:360
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:568
Value * get(VPValue *Def, unsigned Part)
Get the generated Value for a given VPValue and a given Part.
Definition: VPlan.h:263
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1524
unsigned VF
The chosen Vectorization and Unroll Factors of the loop being vectorized.
Definition: VPlan.h:241
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:463
void execute(VPTransformState &State) override
Generate the instruction.
Definition: VPlan.cpp:317
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:897
static Optional< unsigned > getOpcode(ArrayRef< VPValue *> Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:196
void execute(struct VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPBasicBlock, thereby "executing" the VPlan.
Definition: VPlan.cpp:161
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:779
BasicBlock * LastBB
The last IR BasicBlock in the output IR.
Definition: VPlan.h:292
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:59
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
Definition: VPlan.cpp:277
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:309
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:102
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
Drive the analysis of interleaved memory accesses in the loop.
Definition: VectorUtils.h:417
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:237
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:1135
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:268
void set(VPValue *Def, Value *V, unsigned Part)
Set the generated Value for a given VPValue and a given Part.
Definition: VPlan.h:272
The group of interleaved loads/stores sharing the same stride and close to each other.
Definition: VectorUtils.h:27
const VPBlockBase * getExit() const
Definition: VPlan.h:1121
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:233
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1135
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:654
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:469
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:485
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:132
Value * getOperand(unsigned i) const
Definition: User.h:169
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
Core dominator tree base class.
Definition: LoopInfo.h:63
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:479
Value * getUnderlyingValue()
Return the underlying Value attached to this VPValue.
Definition: VPlanValue.h:64
This class augments VPValue with operands which provide the inverse def-use edges from VPValue&#39;s user...
Definition: VPlanValue.h:131
VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI)
Definition: VPlan.cpp:747
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:216
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
virtual Value * getOrCreateVectorValues(Value *V, unsigned Part)=0
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
std::string EscapeString(const std::string &Label)
Definition: GraphWriter.cpp:35
This file contains the declarations of the Vectorization Plan base classes:
UnreachableInst * CreateUnreachable()
Definition: IRBuilder.h:1050
InterleaveGroup< Instruction > * getInterleaveGroup(const Instruction *Instr) const
Get the interleave group that Instr belongs to.
Definition: VectorUtils.h:457
This function has undefined behavior.
const char * getOpcodeName() const
Definition: Instruction.h:127
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:689
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:296
VPValue * getPredicate()
Definition: VPlan.h:496
void printAsOperand(raw_ostream &OS, bool PrintType) const
Definition: VPlan.h:548
cl::opt< bool > EnableVPlanNativePath
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:282
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:674
bool isBinaryOp() const
Definition: Instruction.h:130
VPCallback & Callback
Definition: VPlan.h:328
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:99
self_iterator getIterator()
Definition: ilist_node.h:81
VPValue2ValueTy VPValue2Value
Hold a reference to a mapping between VPValues in VPlan and original Values they correspond to...
Definition: VPlan.h:320
SmallVector< VPBasicBlock *, 8 > VPBBsToFix
Vector of VPBasicBlocks whose terminator instruction needs to be fixed up at the end of vector code g...
Definition: VPlan.h:300
void printAsOperand(raw_ostream &OS) const
Definition: VPlanValue.h:88
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2263
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:650
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:388
static void deleteCFG(VPBlockBase *Entry)
Delete all blocks reachable from a given VPBlockBase, inclusive.
Definition: VPlan.cpp:104
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:982
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:4351
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool insertMember(InstTy *Instr, int32_t Index, uint32_t NewAlign)
Try to insert a new member Instr with index Index and alignment NewAlign.
Definition: VectorUtils.h:297
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
unsigned getNumOperands() const
Definition: User.h:191
BlockVerifier::State From
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:323
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:333
Generic dominator tree construction - This file provides routines to construct immediate dominator in...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:683
void execute(struct VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPRegionBlock, thereby "executing" the VPlan.
Definition: VPlan.cpp:230
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:343
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:631
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:425
VPBlockBase * getEnclosingBlockWithSuccessors()
An Enclosing Block of a block B is any block containing B, including B itself.
Definition: VPlan.cpp:88
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
const VPBlockBase * getEntry() const
Definition: VPlan.h:1103
VPValue * getCondBit()
Definition: VPlan.h:490
void replaceAllUsesWith(VPValue *New)
Definition: VPlan.cpp:701
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:633
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
void print(raw_ostream &OS) const
Definition: VPlan.h:552
iv users
Definition: IVUsers.cpp:51
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:428
Flatten the CFG
VPBlockBase * getEntry()
Definition: VPlan.h:1201
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:506
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:407
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2038
iterator_range< df_iterator< T > > depth_first(const T &G)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
VPBasicBlock * getParent()
Definition: VPlan.h:604
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:482
LLVM Value Representation.
Definition: Value.h:72
Value * TripCount
Hold the trip count of the scalar loop.
Definition: VPlan.h:323
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
VPBlockBase * getEnclosingBlockWithPredecessors()
Definition: VPlan.cpp:96
#define LLVM_DEBUG(X)
Definition: Debug.h:122
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:628
void print(raw_ostream &O, const Twine &Indent) const override
Print the Recipe.
Definition: VPlan.cpp:323
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:284