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