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;
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  assert(PredBB && "Predecessor basic-block not found building successor.");
128  auto *PredBBTerminator = PredBB->getTerminator();
129  LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
130  if (isa<UnreachableInst>(PredBBTerminator)) {
131  assert(PredVPSuccessors.size() == 1 &&
132  "Predecessor ending w/o branch must have single successor.");
133  PredBBTerminator->eraseFromParent();
134  BranchInst::Create(NewBB, PredBB);
135  } else {
136  assert(PredVPSuccessors.size() == 2 &&
137  "Predecessor ending with branch must have two successors.");
138  unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
139  assert(!PredBBTerminator->getSuccessor(idx) &&
140  "Trying to reset an existing successor block.");
141  PredBBTerminator->setSuccessor(idx, NewBB);
142  }
143  }
144  return NewBB;
145 }
146 
148  bool Replica = State->Instance &&
149  !(State->Instance->Part == 0 && State->Instance->Lane == 0);
150  VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
151  VPBlockBase *SingleHPred = nullptr;
152  BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
153 
154  // 1. Create an IR basic block, or reuse the last one if possible.
155  // The last IR basic block is reused, as an optimization, in three cases:
156  // A. the first VPBB reuses the loop header BB - when PrevVPBB is null;
157  // B. when the current VPBB has a single (hierarchical) predecessor which
158  // is PrevVPBB and the latter has a single (hierarchical) successor; and
159  // C. when the current VPBB is an entry of a region replica - where PrevVPBB
160  // is the exit of this region from a previous instance, or the predecessor
161  // of this region.
162  if (PrevVPBB && /* A */
163  !((SingleHPred = getSingleHierarchicalPredecessor()) &&
164  SingleHPred->getExitBasicBlock() == PrevVPBB &&
165  PrevVPBB->getSingleHierarchicalSuccessor()) && /* B */
166  !(Replica && getPredecessors().empty())) { /* C */
167  NewBB = createEmptyBasicBlock(State->CFG);
168  State->Builder.SetInsertPoint(NewBB);
169  // Temporarily terminate with unreachable until CFG is rewired.
171  State->Builder.SetInsertPoint(Terminator);
172  // Register NewBB in its loop. In innermost loops its the same for all BB's.
173  Loop *L = State->LI->getLoopFor(State->CFG.LastBB);
174  L->addBasicBlockToLoop(NewBB, *State->LI);
175  State->CFG.PrevBB = NewBB;
176  }
177 
178  // 2. Fill the IR basic block with IR instructions.
179  LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
180  << " in BB:" << NewBB->getName() << '\n');
181 
182  State->CFG.VPBB2IRBB[this] = NewBB;
183  State->CFG.PrevVPBB = this;
184 
185  for (VPRecipeBase &Recipe : Recipes)
186  Recipe.execute(*State);
187 
188  LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
189 }
190 
193 
194  if (!isReplicator()) {
195  // Visit the VPBlocks connected to "this", starting from it.
196  for (VPBlockBase *Block : RPOT) {
197  LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
198  Block->execute(State);
199  }
200  return;
201  }
202 
203  assert(!State->Instance && "Replicating a Region with non-null instance.");
204 
205  // Enter replicating mode.
206  State->Instance = {0, 0};
207 
208  for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
209  State->Instance->Part = Part;
210  for (unsigned Lane = 0, VF = State->VF; Lane < VF; ++Lane) {
211  State->Instance->Lane = Lane;
212  // Visit the VPBlocks connected to \p this, starting from it.
213  for (VPBlockBase *Block : RPOT) {
214  LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
215  Block->execute(State);
216  }
217  }
218  }
219 
220  // Exit replicating mode.
221  State->Instance.reset();
222 }
223 
225  Parent = InsertPos->getParent();
226  Parent->getRecipeList().insert(InsertPos->getIterator(), this);
227 }
228 
230  return getParent()->getRecipeList().erase(getIterator());
231 }
232 
233 void VPInstruction::generateInstruction(VPTransformState &State,
234  unsigned Part) {
235  IRBuilder<> &Builder = State.Builder;
236 
237  if (Instruction::isBinaryOp(getOpcode())) {
238  Value *A = State.get(getOperand(0), Part);
239  Value *B = State.get(getOperand(1), Part);
240  Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
241  State.set(this, V, Part);
242  return;
243  }
244 
245  switch (getOpcode()) {
246  case VPInstruction::Not: {
247  Value *A = State.get(getOperand(0), Part);
248  Value *V = Builder.CreateNot(A);
249  State.set(this, V, Part);
250  break;
251  }
252  default:
253  llvm_unreachable("Unsupported opcode for instruction");
254  }
255 }
256 
258  assert(!State.Instance && "VPInstruction executing an Instance");
259  for (unsigned Part = 0; Part < State.UF; ++Part)
260  generateInstruction(State, Part);
261 }
262 
264  O << " +\n" << Indent << "\"EMIT ";
265  print(O);
266  O << "\\l\"";
267 }
268 
270  printAsOperand(O);
271  O << " = ";
272 
273  switch (getOpcode()) {
274  case VPInstruction::Not:
275  O << "not";
276  break;
277  default:
278  O << Instruction::getOpcodeName(getOpcode());
279  }
280 
281  for (const VPValue *Operand : operands()) {
282  O << " ";
283  Operand->printAsOperand(O);
284  }
285 }
286 
287 /// Generate the code inside the body of the vectorized loop. Assumes a single
288 /// LoopVectorBody basic-block was created for this. Introduce additional
289 /// basic-blocks as needed, and fill them all.
291  // 0. Set the reverse mapping from VPValues to Values for code generation.
292  for (auto &Entry : Value2VPValue)
293  State->VPValue2Value[Entry.second] = Entry.first;
294 
295  BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
296  BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
297  assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
298  BasicBlock *VectorLatchBB = VectorHeaderBB;
299 
300  // 1. Make room to generate basic-blocks inside loop body if needed.
301  VectorLatchBB = VectorHeaderBB->splitBasicBlock(
302  VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
303  Loop *L = State->LI->getLoopFor(VectorHeaderBB);
304  L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
305  // Remove the edge between Header and Latch to allow other connections.
306  // Temporarily terminate with unreachable until CFG is rewired.
307  // Note: this asserts the generated code's assumption that
308  // getFirstInsertionPt() can be dereferenced into an Instruction.
309  VectorHeaderBB->getTerminator()->eraseFromParent();
310  State->Builder.SetInsertPoint(VectorHeaderBB);
312  State->Builder.SetInsertPoint(Terminator);
313 
314  // 2. Generate code in loop body.
315  State->CFG.PrevVPBB = nullptr;
316  State->CFG.PrevBB = VectorHeaderBB;
317  State->CFG.LastBB = VectorLatchBB;
318 
319  for (VPBlockBase *Block : depth_first(Entry))
320  Block->execute(State);
321 
322  // 3. Merge the temporary latch created with the last basic-block filled.
323  BasicBlock *LastBB = State->CFG.PrevBB;
324  // Connect LastBB to VectorLatchBB to facilitate their merge.
325  assert(isa<UnreachableInst>(LastBB->getTerminator()) &&
326  "Expected VPlan CFG to terminate with unreachable");
327  LastBB->getTerminator()->eraseFromParent();
328  BranchInst::Create(VectorLatchBB, LastBB);
329 
330  // Merge LastBB with Latch.
331  bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
332  (void)Merged;
333  assert(Merged && "Could not merge last basic block with latch.");
334  VectorLatchBB = LastBB;
335 
336  updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB);
337 }
338 
339 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
340  BasicBlock *LoopLatchBB) {
341  BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
342  assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
343  DT->addNewBlock(LoopHeaderBB, LoopPreHeaderBB);
344  // The vector body may be more than a single basic-block by this point.
345  // Update the dominator tree information inside the vector body by propagating
346  // it from header to latch, expecting only triangular control-flow, if any.
347  BasicBlock *PostDomSucc = nullptr;
348  for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
349  // Get the list of successors of this block.
350  std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
351  assert(Succs.size() <= 2 &&
352  "Basic block in vector loop has more than 2 successors.");
353  PostDomSucc = Succs[0];
354  if (Succs.size() == 1) {
355  assert(PostDomSucc->getSinglePredecessor() &&
356  "PostDom successor has more than one predecessor.");
357  DT->addNewBlock(PostDomSucc, BB);
358  continue;
359  }
360  BasicBlock *InterimSucc = Succs[1];
361  if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
362  PostDomSucc = Succs[1];
363  InterimSucc = Succs[0];
364  }
365  assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
366  "One successor of a basic block does not lead to the other.");
367  assert(InterimSucc->getSinglePredecessor() &&
368  "Interim successor has more than one predecessor.");
369  assert(pred_size(PostDomSucc) == 2 &&
370  "PostDom successor has more than two predecessors.");
371  DT->addNewBlock(InterimSucc, BB);
372  DT->addNewBlock(PostDomSucc, BB);
373  }
374 }
375 
376 const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
377  return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
378  Twine(getOrCreateBID(Block));
379 }
380 
381 const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
382  const std::string &Name = Block->getName();
383  if (!Name.empty())
384  return Name;
385  return "VPB" + Twine(getOrCreateBID(Block));
386 }
387 
388 void VPlanPrinter::dump() {
389  Depth = 1;
390  bumpIndent(0);
391  OS << "digraph VPlan {\n";
392  OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
393  if (!Plan.getName().empty())
394  OS << "\\n" << DOT::EscapeString(Plan.getName());
395  if (!Plan.Value2VPValue.empty()) {
396  OS << ", where:";
397  for (auto Entry : Plan.Value2VPValue) {
398  OS << "\\n" << *Entry.second;
399  OS << DOT::EscapeString(" := ");
400  Entry.first->printAsOperand(OS, false);
401  }
402  }
403  OS << "\"]\n";
404  OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
405  OS << "edge [fontname=Courier, fontsize=30]\n";
406  OS << "compound=true\n";
407 
408  for (VPBlockBase *Block : depth_first(Plan.getEntry()))
409  dumpBlock(Block);
410 
411  OS << "}\n";
412 }
413 
414 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
415  if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
416  dumpBasicBlock(BasicBlock);
417  else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
418  dumpRegion(Region);
419  else
420  llvm_unreachable("Unsupported kind of VPBlock.");
421 }
422 
423 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
424  bool Hidden, const Twine &Label) {
425  // Due to "dot" we print an edge between two regions as an edge between the
426  // exit basic block and the entry basic of the respective regions.
427  const VPBlockBase *Tail = From->getExitBasicBlock();
428  const VPBlockBase *Head = To->getEntryBasicBlock();
429  OS << Indent << getUID(Tail) << " -> " << getUID(Head);
430  OS << " [ label=\"" << Label << '\"';
431  if (Tail != From)
432  OS << " ltail=" << getUID(From);
433  if (Head != To)
434  OS << " lhead=" << getUID(To);
435  if (Hidden)
436  OS << "; splines=none";
437  OS << "]\n";
438 }
439 
440 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
441  auto &Successors = Block->getSuccessors();
442  if (Successors.size() == 1)
443  drawEdge(Block, Successors.front(), false, "");
444  else if (Successors.size() == 2) {
445  drawEdge(Block, Successors.front(), false, "T");
446  drawEdge(Block, Successors.back(), false, "F");
447  } else {
448  unsigned SuccessorNumber = 0;
449  for (auto *Successor : Successors)
450  drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
451  }
452 }
453 
454 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
455  OS << Indent << getUID(BasicBlock) << " [label =\n";
456  bumpIndent(1);
457  OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\"";
458  bumpIndent(1);
459  for (const VPRecipeBase &Recipe : *BasicBlock)
460  Recipe.print(OS, Indent);
461 
462  // Dump the condition bit.
463  const VPValue *CBV = BasicBlock->getCondBit();
464  if (CBV) {
465  OS << " +\n" << Indent << " \"CondBit: ";
466  if (const VPInstruction *CBI = dyn_cast<VPInstruction>(CBV)) {
467  CBI->printAsOperand(OS);
468  OS << " (" << DOT::EscapeString(CBI->getParent()->getName()) << ")\\l\"";
469  } else
470  CBV->printAsOperand(OS);
471  }
472 
473  bumpIndent(-2);
474  OS << "\n" << Indent << "]\n";
475  dumpEdges(BasicBlock);
476 }
477 
478 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
479  OS << Indent << "subgraph " << getUID(Region) << " {\n";
480  bumpIndent(1);
481  OS << Indent << "fontname=Courier\n"
482  << Indent << "label=\""
483  << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
484  << DOT::EscapeString(Region->getName()) << "\"\n";
485  // Dump the blocks of the region.
486  assert(Region->getEntry() && "Region contains no inner blocks.");
487  for (const VPBlockBase *Block : depth_first(Region->getEntry()))
488  dumpBlock(Block);
489  bumpIndent(-1);
490  OS << Indent << "}\n";
491  dumpEdges(Region);
492 }
493 
494 void VPlanPrinter::printAsIngredient(raw_ostream &O, Value *V) {
495  std::string IngredientString;
496  raw_string_ostream RSO(IngredientString);
497  if (auto *Inst = dyn_cast<Instruction>(V)) {
498  if (!Inst->getType()->isVoidTy()) {
499  Inst->printAsOperand(RSO, false);
500  RSO << " = ";
501  }
502  RSO << Inst->getOpcodeName() << " ";
503  unsigned E = Inst->getNumOperands();
504  if (E > 0) {
505  Inst->getOperand(0)->printAsOperand(RSO, false);
506  for (unsigned I = 1; I < E; ++I)
507  Inst->getOperand(I)->printAsOperand(RSO << ", ", false);
508  }
509  } else // !Inst
510  V->printAsOperand(RSO, false);
511  RSO.flush();
512  O << DOT::EscapeString(IngredientString);
513 }
514 
516  O << " +\n" << Indent << "\"WIDEN\\l\"";
517  for (auto &Instr : make_range(Begin, End))
518  O << " +\n" << Indent << "\" " << VPlanIngredient(&Instr) << "\\l\"";
519 }
520 
522  const Twine &Indent) const {
523  O << " +\n" << Indent << "\"WIDEN-INDUCTION";
524  if (Trunc) {
525  O << "\\l\"";
526  O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
527  O << " +\n" << Indent << "\" " << VPlanIngredient(Trunc) << "\\l\"";
528  } else
529  O << " " << VPlanIngredient(IV) << "\\l\"";
530 }
531 
533  O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\"";
534 }
535 
537  O << " +\n" << Indent << "\"BLEND ";
538  Phi->printAsOperand(O, false);
539  O << " =";
540  if (!User) {
541  // Not a User of any mask: not really blending, this is a
542  // single-predecessor phi.
543  O << " ";
544  Phi->getIncomingValue(0)->printAsOperand(O, false);
545  } else {
546  for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
547  O << " ";
548  Phi->getIncomingValue(I)->printAsOperand(O, false);
549  O << "/";
551  }
552  }
553  O << "\\l\"";
554 }
555 
557  O << " +\n"
558  << Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
559  << VPlanIngredient(Ingredient);
560  if (AlsoPack)
561  O << " (S->V)";
562  O << "\\l\"";
563 }
564 
566  O << " +\n"
567  << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst)
568  << "\\l\"";
569 }
570 
572  const Twine &Indent) const {
573  O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
574  if (User) {
575  O << ", ";
577  }
578  O << "\\l\"";
579 }
580 
581 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
const std::string & getName() const
Definition: VPlan.h:387
LoopInfo * LI
Hold a pointer to LoopInfo to register new basic blocks in the loop.
Definition: VPlan.h:300
struct llvm::VPTransformState::CFGState CFG
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemoryDependenceResults *MemDep=nullptr)
Attempts to merge a block into its predecessor, if possible.
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:521
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
void execute(struct VPTransformState *State)
Generate the IR code for this VPlan.
Definition: VPlan.cpp:290
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:245
VPRegionBlock * getParent()
Definition: VPlan.h:396
BasicBlock * PrevBB
The previous IR BasicBlock created or used.
Definition: VPlan.h:286
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1010
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:306
iplist< VPRecipeBase >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: VPlan.cpp:229
const VPBasicBlock * getExitBasicBlock() const
Definition: VPlan.cpp:74
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:541
Value * get(VPValue *Def, unsigned Part)
Get the generated Value for a given VPValue and a given Part.
Definition: VPlan.h:261
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:239
void execute(VPTransformState &State) override
Generate the instruction.
Definition: VPlan.cpp:257
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:147
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:290
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:224
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:303
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:251
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:1078
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:270
const VPBlockBase * getExit() const
Definition: VPlan.h:1064
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:231
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:536
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:457
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:473
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
Core dominator tree base class.
Definition: LoopInfo.h:61
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:467
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:571
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:294
void printAsOperand(raw_ostream &OS, bool PrintType) const
Definition: VPlan.h:521
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:280
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:556
bool isBinaryOp() const
Definition: Instruction.h:130
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:101
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:314
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:532
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:104
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:925
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:4145
#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:324
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:565
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:191
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:413
VPBlockBase * getEnclosingBlockWithSuccessors()
An Enclosing Block of a block B is any block containing B, including B itself.
Definition: VPlan.cpp:88
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:1046
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:515
void print(raw_ostream &OS) const
Definition: VPlan.h:525
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:416
Flatten the CFG
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: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:2033
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:577
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:96
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:601
void print(raw_ostream &O, const Twine &Indent) const override
Print the Recipe.
Definition: VPlan.cpp:263
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:282