LLVM  7.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"
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/Dominators.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"
40 #include <cassert>
41 #include <iterator>
42 #include <string>
43 #include <vector>
44 
45 using namespace llvm;
46 
47 #define DEBUG_TYPE "vplan"
48 
50  if (const VPInstruction *Instr = dyn_cast<VPInstruction>(&V))
51  Instr->print(OS);
52  else
53  V.printAsOperand(OS);
54  return OS;
55 }
56 
57 /// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
59  const VPBlockBase *Block = this;
60  while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
61  Block = Region->getEntry();
62  return cast<VPBasicBlock>(Block);
63 }
64 
66  VPBlockBase *Block = this;
67  while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
68  Block = Region->getEntry();
69  return cast<VPBasicBlock>(Block);
70 }
71 
72 /// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
74  const VPBlockBase *Block = this;
75  while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
76  Block = Region->getExit();
77  return cast<VPBasicBlock>(Block);
78 }
79 
81  VPBlockBase *Block = this;
82  while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
83  Block = Region->getExit();
84  return cast<VPBasicBlock>(Block);
85 }
86 
88  if (!Successors.empty() || !Parent)
89  return this;
90  assert(Parent->getExit() == this &&
91  "Block w/o successors not the exit of its parent.");
92  return Parent->getEnclosingBlockWithSuccessors();
93 }
94 
96  if (!Predecessors.empty() || !Parent)
97  return this;
98  assert(Parent->getEntry() == this &&
99  "Block w/o predecessors not the entry of its parent.");
100  return Parent->getEnclosingBlockWithPredecessors();
101 }
102 
105  for (VPBlockBase *Block : depth_first(Entry))
106  Blocks.push_back(Block);
107 
108  for (VPBlockBase *Block : Blocks)
109  delete Block;
110 }
111 
112 BasicBlock *
113 VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
114  // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
115  // Pred stands for Predessor. Prev stands for Previous - last visited/created.
116  BasicBlock *PrevBB = CFG.PrevBB;
117  BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
118  PrevBB->getParent(), CFG.LastBB);
119  LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
120 
121  // Hook up the new basic block to its predecessors.
122  for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
123  VPBasicBlock *PredVPBB = PredVPBlock->getExitBasicBlock();
124  auto &PredVPSuccessors = PredVPBB->getSuccessors();
125  BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
126  assert(PredBB && "Predecessor basic-block not found building successor.");
127  auto *PredBBTerminator = PredBB->getTerminator();
128  LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
129  if (isa<UnreachableInst>(PredBBTerminator)) {
130  assert(PredVPSuccessors.size() == 1 &&
131  "Predecessor ending w/o branch must have single successor.");
132  PredBBTerminator->eraseFromParent();
133  BranchInst::Create(NewBB, PredBB);
134  } else {
135  assert(PredVPSuccessors.size() == 2 &&
136  "Predecessor ending with branch must have two successors.");
137  unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
138  assert(!PredBBTerminator->getSuccessor(idx) &&
139  "Trying to reset an existing successor block.");
140  PredBBTerminator->setSuccessor(idx, NewBB);
141  }
142  }
143  return NewBB;
144 }
145 
147  bool Replica = State->Instance &&
148  !(State->Instance->Part == 0 && State->Instance->Lane == 0);
149  VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
150  VPBlockBase *SingleHPred = nullptr;
151  BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
152 
153  // 1. Create an IR basic block, or reuse the last one if possible.
154  // The last IR basic block is reused, as an optimization, in three cases:
155  // A. the first VPBB reuses the loop header BB - when PrevVPBB is null;
156  // B. when the current VPBB has a single (hierarchical) predecessor which
157  // is PrevVPBB and the latter has a single (hierarchical) successor; and
158  // C. when the current VPBB is an entry of a region replica - where PrevVPBB
159  // is the exit of this region from a previous instance, or the predecessor
160  // of this region.
161  if (PrevVPBB && /* A */
162  !((SingleHPred = getSingleHierarchicalPredecessor()) &&
163  SingleHPred->getExitBasicBlock() == PrevVPBB &&
164  PrevVPBB->getSingleHierarchicalSuccessor()) && /* B */
165  !(Replica && getPredecessors().empty())) { /* C */
166  NewBB = createEmptyBasicBlock(State->CFG);
167  State->Builder.SetInsertPoint(NewBB);
168  // Temporarily terminate with unreachable until CFG is rewired.
170  State->Builder.SetInsertPoint(Terminator);
171  // Register NewBB in its loop. In innermost loops its the same for all BB's.
172  Loop *L = State->LI->getLoopFor(State->CFG.LastBB);
173  L->addBasicBlockToLoop(NewBB, *State->LI);
174  State->CFG.PrevBB = NewBB;
175  }
176 
177  // 2. Fill the IR basic block with IR instructions.
178  LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
179  << " in BB:" << NewBB->getName() << '\n');
180 
181  State->CFG.VPBB2IRBB[this] = NewBB;
182  State->CFG.PrevVPBB = this;
183 
184  for (VPRecipeBase &Recipe : Recipes)
185  Recipe.execute(*State);
186 
187  LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
188 }
189 
192 
193  if (!isReplicator()) {
194  // Visit the VPBlocks connected to "this", starting from it.
195  for (VPBlockBase *Block : RPOT) {
196  LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
197  Block->execute(State);
198  }
199  return;
200  }
201 
202  assert(!State->Instance && "Replicating a Region with non-null instance.");
203 
204  // Enter replicating mode.
205  State->Instance = {0, 0};
206 
207  for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
208  State->Instance->Part = Part;
209  for (unsigned Lane = 0, VF = State->VF; Lane < VF; ++Lane) {
210  State->Instance->Lane = Lane;
211  // Visit the VPBlocks connected to \p this, starting from it.
212  for (VPBlockBase *Block : RPOT) {
213  LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
214  Block->execute(State);
215  }
216  }
217  }
218 
219  // Exit replicating mode.
220  State->Instance.reset();
221 }
222 
224  Parent = InsertPos->getParent();
225  Parent->getRecipeList().insert(InsertPos->getIterator(), this);
226 }
227 
229  return getParent()->getRecipeList().erase(getIterator());
230 }
231 
232 void VPInstruction::generateInstruction(VPTransformState &State,
233  unsigned Part) {
234  IRBuilder<> &Builder = State.Builder;
235 
236  if (Instruction::isBinaryOp(getOpcode())) {
237  Value *A = State.get(getOperand(0), Part);
238  Value *B = State.get(getOperand(1), Part);
239  Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
240  State.set(this, V, Part);
241  return;
242  }
243 
244  switch (getOpcode()) {
245  case VPInstruction::Not: {
246  Value *A = State.get(getOperand(0), Part);
247  Value *V = Builder.CreateNot(A);
248  State.set(this, V, Part);
249  break;
250  }
251  default:
252  llvm_unreachable("Unsupported opcode for instruction");
253  }
254 }
255 
257  assert(!State.Instance && "VPInstruction executing an Instance");
258  for (unsigned Part = 0; Part < State.UF; ++Part)
259  generateInstruction(State, Part);
260 }
261 
262 void VPInstruction::print(raw_ostream &O, const Twine &Indent) const {
263  O << " +\n" << Indent << "\"EMIT ";
264  print(O);
265  O << "\\l\"";
266 }
267 
269  printAsOperand(O);
270  O << " = ";
271 
272  switch (getOpcode()) {
273  case VPInstruction::Not:
274  O << "not";
275  break;
276  default:
277  O << Instruction::getOpcodeName(getOpcode());
278  }
279 
280  for (const VPValue *Operand : operands()) {
281  O << " ";
282  Operand->printAsOperand(O);
283  }
284 }
285 
286 /// Generate the code inside the body of the vectorized loop. Assumes a single
287 /// LoopVectorBody basic-block was created for this. Introduce additional
288 /// basic-blocks as needed, and fill them all.
290  // 0. Set the reverse mapping from VPValues to Values for code generation.
291  for (auto &Entry : Value2VPValue)
292  State->VPValue2Value[Entry.second] = Entry.first;
293 
294  BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
295  BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
296  assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
297  BasicBlock *VectorLatchBB = VectorHeaderBB;
298 
299  // 1. Make room to generate basic-blocks inside loop body if needed.
300  VectorLatchBB = VectorHeaderBB->splitBasicBlock(
301  VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
302  Loop *L = State->LI->getLoopFor(VectorHeaderBB);
303  L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
304  // Remove the edge between Header and Latch to allow other connections.
305  // Temporarily terminate with unreachable until CFG is rewired.
306  // Note: this asserts the generated code's assumption that
307  // getFirstInsertionPt() can be dereferenced into an Instruction.
308  VectorHeaderBB->getTerminator()->eraseFromParent();
309  State->Builder.SetInsertPoint(VectorHeaderBB);
311  State->Builder.SetInsertPoint(Terminator);
312 
313  // 2. Generate code in loop body.
314  State->CFG.PrevVPBB = nullptr;
315  State->CFG.PrevBB = VectorHeaderBB;
316  State->CFG.LastBB = VectorLatchBB;
317 
318  for (VPBlockBase *Block : depth_first(Entry))
319  Block->execute(State);
320 
321  // 3. Merge the temporary latch created with the last basic-block filled.
322  BasicBlock *LastBB = State->CFG.PrevBB;
323  // Connect LastBB to VectorLatchBB to facilitate their merge.
324  assert(isa<UnreachableInst>(LastBB->getTerminator()) &&
325  "Expected VPlan CFG to terminate with unreachable");
326  LastBB->getTerminator()->eraseFromParent();
327  BranchInst::Create(VectorLatchBB, LastBB);
328 
329  // Merge LastBB with Latch.
330  bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
331  (void)Merged;
332  assert(Merged && "Could not merge last basic block with latch.");
333  VectorLatchBB = LastBB;
334 
335  updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB);
336 }
337 
338 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
339  BasicBlock *LoopLatchBB) {
340  BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
341  assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
342  DT->addNewBlock(LoopHeaderBB, LoopPreHeaderBB);
343  // The vector body may be more than a single basic-block by this point.
344  // Update the dominator tree information inside the vector body by propagating
345  // it from header to latch, expecting only triangular control-flow, if any.
346  BasicBlock *PostDomSucc = nullptr;
347  for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
348  // Get the list of successors of this block.
349  std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
350  assert(Succs.size() <= 2 &&
351  "Basic block in vector loop has more than 2 successors.");
352  PostDomSucc = Succs[0];
353  if (Succs.size() == 1) {
354  assert(PostDomSucc->getSinglePredecessor() &&
355  "PostDom successor has more than one predecessor.");
356  DT->addNewBlock(PostDomSucc, BB);
357  continue;
358  }
359  BasicBlock *InterimSucc = Succs[1];
360  if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
361  PostDomSucc = Succs[1];
362  InterimSucc = Succs[0];
363  }
364  assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
365  "One successor of a basic block does not lead to the other.");
366  assert(InterimSucc->getSinglePredecessor() &&
367  "Interim successor has more than one predecessor.");
368  assert(pred_size(PostDomSucc) == 2 &&
369  "PostDom successor has more than two predecessors.");
370  DT->addNewBlock(InterimSucc, BB);
371  DT->addNewBlock(PostDomSucc, BB);
372  }
373 }
374 
375 const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
376  return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
377  Twine(getOrCreateBID(Block));
378 }
379 
380 const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
381  const std::string &Name = Block->getName();
382  if (!Name.empty())
383  return Name;
384  return "VPB" + Twine(getOrCreateBID(Block));
385 }
386 
387 void VPlanPrinter::dump() {
388  Depth = 1;
389  bumpIndent(0);
390  OS << "digraph VPlan {\n";
391  OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
392  if (!Plan.getName().empty())
393  OS << "\\n" << DOT::EscapeString(Plan.getName());
394  if (!Plan.Value2VPValue.empty()) {
395  OS << ", where:";
396  for (auto Entry : Plan.Value2VPValue) {
397  OS << "\\n" << *Entry.second;
398  OS << DOT::EscapeString(" := ");
399  Entry.first->printAsOperand(OS, false);
400  }
401  }
402  OS << "\"]\n";
403  OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
404  OS << "edge [fontname=Courier, fontsize=30]\n";
405  OS << "compound=true\n";
406 
407  for (VPBlockBase *Block : depth_first(Plan.getEntry()))
408  dumpBlock(Block);
409 
410  OS << "}\n";
411 }
412 
413 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
414  if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
415  dumpBasicBlock(BasicBlock);
416  else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
417  dumpRegion(Region);
418  else
419  llvm_unreachable("Unsupported kind of VPBlock.");
420 }
421 
422 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
423  bool Hidden, const Twine &Label) {
424  // Due to "dot" we print an edge between two regions as an edge between the
425  // exit basic block and the entry basic of the respective regions.
426  const VPBlockBase *Tail = From->getExitBasicBlock();
427  const VPBlockBase *Head = To->getEntryBasicBlock();
428  OS << Indent << getUID(Tail) << " -> " << getUID(Head);
429  OS << " [ label=\"" << Label << '\"';
430  if (Tail != From)
431  OS << " ltail=" << getUID(From);
432  if (Head != To)
433  OS << " lhead=" << getUID(To);
434  if (Hidden)
435  OS << "; splines=none";
436  OS << "]\n";
437 }
438 
439 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
440  auto &Successors = Block->getSuccessors();
441  if (Successors.size() == 1)
442  drawEdge(Block, Successors.front(), false, "");
443  else if (Successors.size() == 2) {
444  drawEdge(Block, Successors.front(), false, "T");
445  drawEdge(Block, Successors.back(), false, "F");
446  } else {
447  unsigned SuccessorNumber = 0;
448  for (auto *Successor : Successors)
449  drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
450  }
451 }
452 
453 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
454  OS << Indent << getUID(BasicBlock) << " [label =\n";
455  bumpIndent(1);
456  OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\"";
457  bumpIndent(1);
458  for (const VPRecipeBase &Recipe : *BasicBlock)
459  Recipe.print(OS, Indent);
460  bumpIndent(-2);
461  OS << "\n" << Indent << "]\n";
462  dumpEdges(BasicBlock);
463 }
464 
465 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
466  OS << Indent << "subgraph " << getUID(Region) << " {\n";
467  bumpIndent(1);
468  OS << Indent << "fontname=Courier\n"
469  << Indent << "label=\""
470  << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
471  << DOT::EscapeString(Region->getName()) << "\"\n";
472  // Dump the blocks of the region.
473  assert(Region->getEntry() && "Region contains no inner blocks.");
474  for (const VPBlockBase *Block : depth_first(Region->getEntry()))
475  dumpBlock(Block);
476  bumpIndent(-1);
477  OS << Indent << "}\n";
478  dumpEdges(Region);
479 }
480 
481 void VPlanPrinter::printAsIngredient(raw_ostream &O, Value *V) {
482  std::string IngredientString;
483  raw_string_ostream RSO(IngredientString);
484  if (auto *Inst = dyn_cast<Instruction>(V)) {
485  if (!Inst->getType()->isVoidTy()) {
486  Inst->printAsOperand(RSO, false);
487  RSO << " = ";
488  }
489  RSO << Inst->getOpcodeName() << " ";
490  unsigned E = Inst->getNumOperands();
491  if (E > 0) {
492  Inst->getOperand(0)->printAsOperand(RSO, false);
493  for (unsigned I = 1; I < E; ++I)
494  Inst->getOperand(I)->printAsOperand(RSO << ", ", false);
495  }
496  } else // !Inst
497  V->printAsOperand(RSO, false);
498  RSO.flush();
499  O << DOT::EscapeString(IngredientString);
500 }
501 
502 void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent) const {
503  O << " +\n" << Indent << "\"WIDEN\\l\"";
504  for (auto &Instr : make_range(Begin, End))
505  O << " +\n" << Indent << "\" " << VPlanIngredient(&Instr) << "\\l\"";
506 }
507 
509  const Twine &Indent) const {
510  O << " +\n" << Indent << "\"WIDEN-INDUCTION";
511  if (Trunc) {
512  O << "\\l\"";
513  O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
514  O << " +\n" << Indent << "\" " << VPlanIngredient(Trunc) << "\\l\"";
515  } else
516  O << " " << VPlanIngredient(IV) << "\\l\"";
517 }
518 
519 void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
520  O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\"";
521 }
522 
523 void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent) const {
524  O << " +\n" << Indent << "\"BLEND ";
525  Phi->printAsOperand(O, false);
526  O << " =";
527  if (!User) {
528  // Not a User of any mask: not really blending, this is a
529  // single-predecessor phi.
530  O << " ";
531  Phi->getIncomingValue(0)->printAsOperand(O, false);
532  } else {
533  for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
534  O << " ";
535  Phi->getIncomingValue(I)->printAsOperand(O, false);
536  O << "/";
538  }
539  }
540  O << "\\l\"";
541 }
542 
543 void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent) const {
544  O << " +\n"
545  << Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
546  << VPlanIngredient(Ingredient);
547  if (AlsoPack)
548  O << " (S->V)";
549  O << "\\l\"";
550 }
551 
552 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
553  O << " +\n"
554  << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst)
555  << "\\l\"";
556 }
557 
559  const Twine &Indent) const {
560  O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
561  if (User) {
562  O << ", ";
564  }
565  O << "\\l\"";
566 }
const std::string & getName() const
Definition: VPlan.h:383
LoopInfo * LI
Hold a pointer to LoopInfo to register new basic blocks in the loop.
Definition: VPlan.h:299
struct llvm::VPTransformState::CFGState CFG
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:508
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemoryDependenceResults *MemDep=nullptr, DeferredDominance *DDT=nullptr)
Attempts to merge a block into its predecessor, if possible.
void execute(struct VPTransformState *State)
Generate the IR code for this VPlan.
Definition: VPlan.cpp:289
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1246
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Optional< VPIteration > Instance
Hold the indices to generate specific scalar instructions.
Definition: VPlan.h:244
VPRegionBlock * getParent()
Definition: VPlan.h:392
BasicBlock * PrevBB
The previous IR BasicBlock created or used.
Definition: VPlan.h:285
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:979
IRBuilder & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Definition: VPlan.h:305
iplist< VPRecipeBase >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: VPlan.cpp:228
const VPBasicBlock * getExitBasicBlock() const
Definition: VPlan.cpp:73
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:510
Value * get(VPValue *Def, unsigned Part)
Get the generated Value for a given VPValue and a given Part.
Definition: VPlan.h:260
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1282
unsigned VF
The chosen Vectorization and Unroll Factors of the loop being vectorized.
Definition: VPlan.h:238
void execute(VPTransformState &State) override
Generate the instruction.
Definition: VPlan.cpp:256
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
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:146
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:731
BasicBlock * LastBB
The last IR BasicBlock in the output IR.
Definition: VPlan.h:289
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:58
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
Definition: VPlan.cpp:223
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:302
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
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:183
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:1041
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:262
void set(VPValue *Def, Value *V, unsigned Part)
Set the generated Value for a given VPValue and a given Part.
Definition: VPlan.h:269
const VPBlockBase * getExit() const
Definition: VPlan.h:1027
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:230
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:523
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:453
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:469
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
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
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:463
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:218
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:235
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
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:926
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:558
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:293
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:279
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:543
bool isBinaryOp() const
Definition: Instruction.h:130
static const unsigned End
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:101
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
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:313
void printAsOperand(raw_ostream &OS) const
Definition: VPlanValue.h:85
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:519
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:103
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:894
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:4112
#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
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:323
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:552
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:190
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:409
VPBlockBase * getEnclosingBlockWithSuccessors()
An Enclosing Block of a block B is any block containing B, including B itself.
Definition: VPlan.cpp:87
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:1015
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:502
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:412
Flatten the CFG
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:62
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:445
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
unsigned pred_size(const BasicBlock *BB)
Definition: CFG.h:110
#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:401
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2023
iterator_range< df_iterator< T > > depth_first(const T &G)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
VPBasicBlock * getParent()
Definition: VPlan.h:546
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:477
LLVM Value Representation.
Definition: Value.h:73
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:95
const TerminatorInst * 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
#define LLVM_DEBUG(X)
Definition: Debug.h:119
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:570
void print(raw_ostream &O, const Twine &Indent) const override
Print the Recipe.
Definition: VPlan.cpp:262
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:281