LLVM  8.0.0svn
VPlan.cpp
Go to the documentation of this file.
1 //===- VPlan.cpp - Vectorizer Plan ----------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// This is the LLVM vectorization plan. It represents a candidate for
12 /// vectorization, allowing to plan and optimize how to vectorize a given loop
13 /// before generating LLVM-IR.
14 /// The vectorizer uses vectorization plans to estimate the costs of potential
15 /// candidates and if profitable to execute the desired plan, generating vector
16 /// LLVM-IR code.
17 ///
18 //===----------------------------------------------------------------------===//
19 
20 #include "VPlan.h"
21 #include "VPlanDominatorTree.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/ADT/Twine.h"
26 #include "llvm/Analysis/LoopInfo.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/CFG.h"
29 #include "llvm/IR/InstrTypes.h"
30 #include "llvm/IR/Instruction.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/Type.h"
33 #include "llvm/IR/Value.h"
34 #include "llvm/Support/Casting.h"
35 #include "llvm/Support/Debug.h"
41 #include <cassert>
42 #include <iterator>
43 #include <string>
44 #include <vector>
45 
46 using namespace llvm;
48 
49 #define DEBUG_TYPE "vplan"
50 
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.
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 
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.
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 
83  VPBlockBase *Block = this;
84  while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
85  Block = Region->getExit();
86  return cast<VPBasicBlock>(Block);
87 }
88 
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 
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 
107  for (VPBlockBase *Block : depth_first(Entry))
108  Blocks.push_back(Block);
109 
110  for (VPBlockBase *Block : Blocks)
111  delete Block;
112 }
113 
114 BasicBlock *
115 VPBasicBlock::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 
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.
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 
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 
279  Parent = InsertPos->getParent();
280  Parent->getRecipeList().insert(InsertPos->getIterator(), this);
281 }
282 
284  return getParent()->getRecipeList().erase(getIterator());
285 }
286 
287 void VPInstruction::generateInstruction(VPTransformState &State,
288  unsigned Part) {
289  IRBuilder<> &Builder = State.Builder;
290 
292  Value *A = State.get(getOperand(0), Part);
293  Value *B = State.get(getOperand(1), Part);
294  Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
295  State.set(this, V, Part);
296  return;
297  }
298 
299  switch (getOpcode()) {
300  case VPInstruction::Not: {
301  Value *A = State.get(getOperand(0), Part);
302  Value *V = Builder.CreateNot(A);
303  State.set(this, V, Part);
304  break;
305  }
306  case VPInstruction::ICmpULE: {
307  Value *IV = State.get(getOperand(0), Part);
308  Value *TC = State.get(getOperand(1), Part);
309  Value *V = Builder.CreateICmpULE(IV, TC);
310  State.set(this, V, Part);
311  break;
312  }
313  default:
314  llvm_unreachable("Unsupported opcode for instruction");
315  }
316 }
317 
319  assert(!State.Instance && "VPInstruction executing an Instance");
320  for (unsigned Part = 0; Part < State.UF; ++Part)
321  generateInstruction(State, Part);
322 }
323 
325  O << " +\n" << Indent << "\"EMIT ";
326  print(O);
327  O << "\\l\"";
328 }
329 
331  printAsOperand(O);
332  O << " = ";
333 
334  switch (getOpcode()) {
335  case VPInstruction::Not:
336  O << "not";
337  break;
339  O << "icmp ule";
340  break;
342  O << "combined load";
343  break;
345  O << "combined store";
346  break;
347  default:
349  }
350 
351  for (const VPValue *Operand : operands()) {
352  O << " ";
353  Operand->printAsOperand(O);
354  }
355 }
356 
357 /// Generate the code inside the body of the vectorized loop. Assumes a single
358 /// LoopVectorBody basic-block was created for this. Introduce additional
359 /// basic-blocks as needed, and fill them all.
361  // -1. Check if the backedge taken count is needed, and if so build it.
362  if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
363  Value *TC = State->TripCount;
364  IRBuilder<> Builder(State->CFG.PrevBB->getTerminator());
365  auto *TCMO = Builder.CreateSub(TC, ConstantInt::get(TC->getType(), 1),
366  "trip.count.minus.1");
367  Value2VPValue[TCMO] = BackedgeTakenCount;
368  }
369 
370  // 0. Set the reverse mapping from VPValues to Values for code generation.
371  for (auto &Entry : Value2VPValue)
372  State->VPValue2Value[Entry.second] = Entry.first;
373 
374  BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
375  BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
376  assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
377  BasicBlock *VectorLatchBB = VectorHeaderBB;
378 
379  // 1. Make room to generate basic-blocks inside loop body if needed.
380  VectorLatchBB = VectorHeaderBB->splitBasicBlock(
381  VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
382  Loop *L = State->LI->getLoopFor(VectorHeaderBB);
383  L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
384  // Remove the edge between Header and Latch to allow other connections.
385  // Temporarily terminate with unreachable until CFG is rewired.
386  // Note: this asserts the generated code's assumption that
387  // getFirstInsertionPt() can be dereferenced into an Instruction.
388  VectorHeaderBB->getTerminator()->eraseFromParent();
389  State->Builder.SetInsertPoint(VectorHeaderBB);
391  State->Builder.SetInsertPoint(Terminator);
392 
393  // 2. Generate code in loop body.
394  State->CFG.PrevVPBB = nullptr;
395  State->CFG.PrevBB = VectorHeaderBB;
396  State->CFG.LastBB = VectorLatchBB;
397 
398  for (VPBlockBase *Block : depth_first(Entry))
399  Block->execute(State);
400 
401  // Setup branch terminator successors for VPBBs in VPBBsToFix based on
402  // VPBB's successors.
403  for (auto VPBB : State->CFG.VPBBsToFix) {
404  assert(EnableVPlanNativePath &&
405  "Unexpected VPBBsToFix in non VPlan-native path");
406  BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB];
407  assert(BB && "Unexpected null basic block for VPBB");
408 
409  unsigned Idx = 0;
410  auto *BBTerminator = BB->getTerminator();
411 
412  for (VPBlockBase *SuccVPBlock : VPBB->getHierarchicalSuccessors()) {
413  VPBasicBlock *SuccVPBB = SuccVPBlock->getEntryBasicBlock();
414  BBTerminator->setSuccessor(Idx, State->CFG.VPBB2IRBB[SuccVPBB]);
415  ++Idx;
416  }
417  }
418 
419  // 3. Merge the temporary latch created with the last basic-block filled.
420  BasicBlock *LastBB = State->CFG.PrevBB;
421  // Connect LastBB to VectorLatchBB to facilitate their merge.
422  assert((EnableVPlanNativePath ||
423  isa<UnreachableInst>(LastBB->getTerminator())) &&
424  "Expected InnerLoop VPlan CFG to terminate with unreachable");
425  assert((!EnableVPlanNativePath || isa<BranchInst>(LastBB->getTerminator())) &&
426  "Expected VPlan CFG to terminate with branch in NativePath");
427  LastBB->getTerminator()->eraseFromParent();
428  BranchInst::Create(VectorLatchBB, LastBB);
429 
430  // Merge LastBB with Latch.
431  bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
432  (void)Merged;
433  assert(Merged && "Could not merge last basic block with latch.");
434  VectorLatchBB = LastBB;
435 
436  // We do not attempt to preserve DT for outer loop vectorization currently.
437  if (!EnableVPlanNativePath)
438  updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB);
439 }
440 
441 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
442  BasicBlock *LoopLatchBB) {
443  BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
444  assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
445  DT->addNewBlock(LoopHeaderBB, LoopPreHeaderBB);
446  // The vector body may be more than a single basic-block by this point.
447  // Update the dominator tree information inside the vector body by propagating
448  // it from header to latch, expecting only triangular control-flow, if any.
449  BasicBlock *PostDomSucc = nullptr;
450  for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
451  // Get the list of successors of this block.
452  std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
453  assert(Succs.size() <= 2 &&
454  "Basic block in vector loop has more than 2 successors.");
455  PostDomSucc = Succs[0];
456  if (Succs.size() == 1) {
457  assert(PostDomSucc->getSinglePredecessor() &&
458  "PostDom successor has more than one predecessor.");
459  DT->addNewBlock(PostDomSucc, BB);
460  continue;
461  }
462  BasicBlock *InterimSucc = Succs[1];
463  if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
464  PostDomSucc = Succs[1];
465  InterimSucc = Succs[0];
466  }
467  assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
468  "One successor of a basic block does not lead to the other.");
469  assert(InterimSucc->getSinglePredecessor() &&
470  "Interim successor has more than one predecessor.");
471  assert(PostDomSucc->hasNPredecessors(2) &&
472  "PostDom successor has more than two predecessors.");
473  DT->addNewBlock(InterimSucc, BB);
474  DT->addNewBlock(PostDomSucc, BB);
475  }
476 }
477 
478 const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
479  return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
480  Twine(getOrCreateBID(Block));
481 }
482 
483 const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
484  const std::string &Name = Block->getName();
485  if (!Name.empty())
486  return Name;
487  return "VPB" + Twine(getOrCreateBID(Block));
488 }
489 
490 void VPlanPrinter::dump() {
491  Depth = 1;
492  bumpIndent(0);
493  OS << "digraph VPlan {\n";
494  OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
495  if (!Plan.getName().empty())
496  OS << "\\n" << DOT::EscapeString(Plan.getName());
497  if (!Plan.Value2VPValue.empty() || Plan.BackedgeTakenCount) {
498  OS << ", where:";
499  if (Plan.BackedgeTakenCount)
500  OS << "\\n"
501  << *Plan.getOrCreateBackedgeTakenCount() << " := BackedgeTakenCount";
502  for (auto Entry : Plan.Value2VPValue) {
503  OS << "\\n" << *Entry.second;
504  OS << DOT::EscapeString(" := ");
505  Entry.first->printAsOperand(OS, false);
506  }
507  }
508  OS << "\"]\n";
509  OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
510  OS << "edge [fontname=Courier, fontsize=30]\n";
511  OS << "compound=true\n";
512 
513  for (VPBlockBase *Block : depth_first(Plan.getEntry()))
514  dumpBlock(Block);
515 
516  OS << "}\n";
517 }
518 
519 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
520  if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
521  dumpBasicBlock(BasicBlock);
522  else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
523  dumpRegion(Region);
524  else
525  llvm_unreachable("Unsupported kind of VPBlock.");
526 }
527 
528 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
529  bool Hidden, const Twine &Label) {
530  // Due to "dot" we print an edge between two regions as an edge between the
531  // exit basic block and the entry basic of the respective regions.
532  const VPBlockBase *Tail = From->getExitBasicBlock();
533  const VPBlockBase *Head = To->getEntryBasicBlock();
534  OS << Indent << getUID(Tail) << " -> " << getUID(Head);
535  OS << " [ label=\"" << Label << '\"';
536  if (Tail != From)
537  OS << " ltail=" << getUID(From);
538  if (Head != To)
539  OS << " lhead=" << getUID(To);
540  if (Hidden)
541  OS << "; splines=none";
542  OS << "]\n";
543 }
544 
545 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
546  auto &Successors = Block->getSuccessors();
547  if (Successors.size() == 1)
548  drawEdge(Block, Successors.front(), false, "");
549  else if (Successors.size() == 2) {
550  drawEdge(Block, Successors.front(), false, "T");
551  drawEdge(Block, Successors.back(), false, "F");
552  } else {
553  unsigned SuccessorNumber = 0;
554  for (auto *Successor : Successors)
555  drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
556  }
557 }
558 
559 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
560  OS << Indent << getUID(BasicBlock) << " [label =\n";
561  bumpIndent(1);
562  OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\"";
563  bumpIndent(1);
564  for (const VPRecipeBase &Recipe : *BasicBlock)
565  Recipe.print(OS, Indent);
566 
567  // Dump the condition bit.
568  const VPValue *CBV = BasicBlock->getCondBit();
569  if (CBV) {
570  OS << " +\n" << Indent << " \"CondBit: ";
571  if (const VPInstruction *CBI = dyn_cast<VPInstruction>(CBV)) {
572  CBI->printAsOperand(OS);
573  OS << " (" << DOT::EscapeString(CBI->getParent()->getName()) << ")\\l\"";
574  } else {
575  CBV->printAsOperand(OS);
576  OS << "\"";
577  }
578  }
579 
580  bumpIndent(-2);
581  OS << "\n" << Indent << "]\n";
582  dumpEdges(BasicBlock);
583 }
584 
585 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
586  OS << Indent << "subgraph " << getUID(Region) << " {\n";
587  bumpIndent(1);
588  OS << Indent << "fontname=Courier\n"
589  << Indent << "label=\""
590  << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
591  << DOT::EscapeString(Region->getName()) << "\"\n";
592  // Dump the blocks of the region.
593  assert(Region->getEntry() && "Region contains no inner blocks.");
594  for (const VPBlockBase *Block : depth_first(Region->getEntry()))
595  dumpBlock(Block);
596  bumpIndent(-1);
597  OS << Indent << "}\n";
598  dumpEdges(Region);
599 }
600 
601 void VPlanPrinter::printAsIngredient(raw_ostream &O, Value *V) {
602  std::string IngredientString;
603  raw_string_ostream RSO(IngredientString);
604  if (auto *Inst = dyn_cast<Instruction>(V)) {
605  if (!Inst->getType()->isVoidTy()) {
606  Inst->printAsOperand(RSO, false);
607  RSO << " = ";
608  }
609  RSO << Inst->getOpcodeName() << " ";
610  unsigned E = Inst->getNumOperands();
611  if (E > 0) {
612  Inst->getOperand(0)->printAsOperand(RSO, false);
613  for (unsigned I = 1; I < E; ++I)
614  Inst->getOperand(I)->printAsOperand(RSO << ", ", false);
615  }
616  } else // !Inst
617  V->printAsOperand(RSO, false);
618  RSO.flush();
619  O << DOT::EscapeString(IngredientString);
620 }
621 
623  O << " +\n" << Indent << "\"WIDEN\\l\"";
624  for (auto &Instr : make_range(Begin, End))
625  O << " +\n" << Indent << "\" " << VPlanIngredient(&Instr) << "\\l\"";
626 }
627 
629  const Twine &Indent) const {
630  O << " +\n" << Indent << "\"WIDEN-INDUCTION";
631  if (Trunc) {
632  O << "\\l\"";
633  O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
634  O << " +\n" << Indent << "\" " << VPlanIngredient(Trunc) << "\\l\"";
635  } else
636  O << " " << VPlanIngredient(IV) << "\\l\"";
637 }
638 
640  O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\"";
641 }
642 
644  O << " +\n" << Indent << "\"BLEND ";
645  Phi->printAsOperand(O, false);
646  O << " =";
647  if (!User) {
648  // Not a User of any mask: not really blending, this is a
649  // single-predecessor phi.
650  O << " ";
651  Phi->getIncomingValue(0)->printAsOperand(O, false);
652  } else {
653  for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
654  O << " ";
655  Phi->getIncomingValue(I)->printAsOperand(O, false);
656  O << "/";
658  }
659  }
660  O << "\\l\"";
661 }
662 
664  O << " +\n"
665  << Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
666  << VPlanIngredient(Ingredient);
667  if (AlsoPack)
668  O << " (S->V)";
669  O << "\\l\"";
670 }
671 
673  O << " +\n"
674  << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst)
675  << "\\l\"";
676 }
677 
679  const Twine &Indent) const {
680  O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
681  if (User) {
682  O << ", ";
684  }
685  O << "\\l\"";
686 }
687 
688 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
689 
691  for (VPUser *User : users())
692  for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
693  if (User->getOperand(I) == this)
694  User->setOperand(I, New);
695 }
696 
697 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
698  Old2NewTy &Old2New,
699  InterleavedAccessInfo &IAI) {
701  for (VPBlockBase *Base : RPOT) {
702  visitBlock(Base, Old2New, IAI);
703  }
704 }
705 
706 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
707  InterleavedAccessInfo &IAI) {
708  if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
709  for (VPRecipeBase &VPI : *VPBB) {
710  assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
711  auto *VPInst = cast<VPInstruction>(&VPI);
712  auto *Inst = cast<Instruction>(VPInst->getUnderlyingValue());
713  auto *IG = IAI.getInterleaveGroup(Inst);
714  if (!IG)
715  continue;
716 
717  auto NewIGIter = Old2New.find(IG);
718  if (NewIGIter == Old2New.end())
719  Old2New[IG] = new InterleaveGroup<VPInstruction>(
720  IG->getFactor(), IG->isReverse(), IG->getAlignment());
721 
722  if (Inst == IG->getInsertPos())
723  Old2New[IG]->setInsertPos(VPInst);
724 
725  InterleaveGroupMap[VPInst] = Old2New[IG];
726  InterleaveGroupMap[VPInst]->insertMember(
727  VPInst, IG->getIndex(Inst),
728  IG->isReverse() ? (-1) * int(IG->getFactor()) : IG->getFactor());
729  }
730  } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
731  visitRegion(Region, Old2New, IAI);
732  else
733  llvm_unreachable("Unsupported kind of VPBlock.");
734 }
735 
737  InterleavedAccessInfo &IAI) {
738  Old2NewTy Old2New;
739  visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI);
740 }
const std::string & getName() const
Definition: VPlan.h:397
LoopInfo * LI
Hold a pointer to LoopInfo to register new basic blocks in the loop.
Definition: VPlan.h:307
struct llvm::VPTransformState::CFGState CFG
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:628
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
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:360
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1258
This class represents lattice values for constants.
Definition: AllocatorList.h:24
Optional< VPIteration > Instance
Hold the indices to generate specific scalar instructions.
Definition: VPlan.h:248
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:406
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:1130
BasicBlock * PrevBB
The previous IR BasicBlock created or used.
Definition: VPlan.h:289
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1050
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:313
iplist< VPRecipeBase >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: VPlan.cpp:283
const VPBasicBlock * getExitBasicBlock() const
Definition: VPlan.cpp:75
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:138
Value * CreateICmpULE(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1768
BlockT * getExit() const
Get the exit BasicBlock of the Region.
Definition: RegionInfo.h:361
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:551
Value * get(VPValue *Def, unsigned Part)
Get the generated Value for a given VPValue and a given Part.
Definition: VPlan.h:264
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1294
unsigned VF
The chosen Vectorization and Unroll Factors of the loop being vectorized.
Definition: VPlan.h:242
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:461
void execute(VPTransformState &State) override
Generate the instruction.
Definition: VPlan.cpp:318
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:684
static Optional< unsigned > getOpcode(ArrayRef< VPValue *> Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:197
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:162
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:743
BasicBlock * LastBB
The last IR BasicBlock in the output IR.
Definition: VPlan.h:293
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:60
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
Definition: VPlan.cpp:278
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:310
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:103
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:372
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:251
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:1118
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:271
void set(VPValue *Def, Value *V, unsigned Part)
Set the generated Value for a given VPValue and a given Part.
Definition: VPlan.h:273
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:1104
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:234
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:991
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:643
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:467
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:483
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:127
Value * getOperand(unsigned i) const
Definition: User.h:170
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
Core dominator tree base class.
Definition: LoopInfo.h:61
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:477
Value * getUnderlyingValue()
Return the underlying Value attached to this VPValue.
Definition: VPlanValue.h:65
This class augments VPValue with operands which provide the inverse def-use edges from VPValue&#39;s user...
Definition: VPlanValue.h:132
VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI)
Definition: VPlan.cpp:736
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:219
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:236
virtual Value * getOrCreateVectorValues(Value *V, unsigned Part)=0
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
std::string EscapeString(const std::string &Label)
Definition: GraphWriter.cpp:36
This file contains the declarations of the Vectorization Plan base classes:
UnreachableInst * CreateUnreachable()
Definition: IRBuilder.h:938
InterleaveGroup< Instruction > * getInterleaveGroup(const Instruction *Instr) const
Get the interleave group that Instr belongs to.
Definition: VectorUtils.h:412
This function has undefined behavior.
const char * getOpcodeName() const
Definition: Instruction.h:128
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:678
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:297
void printAsOperand(raw_ostream &OS, bool PrintType) const
Definition: VPlan.h:531
cl::opt< bool > EnableVPlanNativePath
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:283
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:663
bool isBinaryOp() const
Definition: Instruction.h:131
VPCallback & Callback
Definition: VPlan.h:329
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
self_iterator getIterator()
Definition: ilist_node.h:82
VPValue2ValueTy VPValue2Value
Hold a reference to a mapping between VPValues in VPlan and original Values they correspond to...
Definition: VPlan.h:321
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:301
void printAsOperand(raw_ostream &OS) const
Definition: VPlanValue.h:89
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:1933
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:639
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:390
static void deleteCFG(VPBlockBase *Entry)
Delete all blocks reachable from a given VPBlockBase, inclusive.
Definition: VPlan.cpp:105
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:965
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:4226
#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:192
BlockVerifier::State From
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:324
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:334
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:847
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:672
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:231
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:307
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:622
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:423
VPBlockBase * getEnclosingBlockWithSuccessors()
An Enclosing Block of a block B is any block containing B, including B itself.
Definition: VPlan.cpp:89
void setOperand(unsigned i, Value *Val)
Definition: User.h:175
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
const VPBlockBase * getEntry() const
Definition: VPlan.h:1086
VPValue * getCondBit()
Definition: VPlan.h:488
void replaceAllUsesWith(VPValue *New)
Definition: VPlan.cpp:690
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:622
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:535
iv users
Definition: IVUsers.cpp:52
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:426
Flatten the CFG
VPBlockBase * getEntry()
Definition: VPlan.h:1184
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:459
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:215
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#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:410
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2039
iterator_range< df_iterator< T > > depth_first(const T &G)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Definition: JSON.cpp:592
VPBasicBlock * getParent()
Definition: VPlan.h:587
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:483
bool insertMember(InstTy *Instr, int Index, unsigned NewAlign)
Try to insert a new member Instr with index Index and alignment NewAlign.
Definition: VectorUtils.h:262
LLVM Value Representation.
Definition: Value.h:73
Value * TripCount
Hold the trip count of the scalar loop.
Definition: VPlan.h:324
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
VPBlockBase * getEnclosingBlockWithPredecessors()
Definition: VPlan.cpp:97
#define LLVM_DEBUG(X)
Definition: Debug.h:123
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:611
void print(raw_ostream &O, const Twine &Indent) const override
Print the Recipe.
Definition: VPlan.cpp:324
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:285