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  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  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  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  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  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  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 
223 void VPInstruction::generateInstruction(VPTransformState &State,
224  unsigned Part) {
225  IRBuilder<> &Builder = State.Builder;
226 
227  if (Instruction::isBinaryOp(getOpcode())) {
228  Value *A = State.get(getOperand(0), Part);
229  Value *B = State.get(getOperand(1), Part);
230  Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
231  State.set(this, V, Part);
232  return;
233  }
234 
235  switch (getOpcode()) {
236  case VPInstruction::Not: {
237  Value *A = State.get(getOperand(0), Part);
238  Value *V = Builder.CreateNot(A);
239  State.set(this, V, Part);
240  break;
241  }
242  default:
243  llvm_unreachable("Unsupported opcode for instruction");
244  }
245 }
246 
248  assert(!State.Instance && "VPInstruction executing an Instance");
249  for (unsigned Part = 0; Part < State.UF; ++Part)
250  generateInstruction(State, Part);
251 }
252 
253 void VPInstruction::print(raw_ostream &O, const Twine &Indent) const {
254  O << " +\n" << Indent << "\"EMIT ";
255  print(O);
256  O << "\\l\"";
257 }
258 
260  printAsOperand(O);
261  O << " = ";
262 
263  switch (getOpcode()) {
264  case VPInstruction::Not:
265  O << "not";
266  break;
267  default:
268  O << Instruction::getOpcodeName(getOpcode());
269  }
270 
271  for (const VPValue *Operand : operands()) {
272  O << " ";
273  Operand->printAsOperand(O);
274  }
275 }
276 
277 /// Generate the code inside the body of the vectorized loop. Assumes a single
278 /// LoopVectorBody basic-block was created for this. Introduce additional
279 /// basic-blocks as needed, and fill them all.
281  // 0. Set the reverse mapping from VPValues to Values for code generation.
282  for (auto &Entry : Value2VPValue)
283  State->VPValue2Value[Entry.second] = Entry.first;
284 
285  BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
286  BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
287  assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
288  BasicBlock *VectorLatchBB = VectorHeaderBB;
289 
290  // 1. Make room to generate basic-blocks inside loop body if needed.
291  VectorLatchBB = VectorHeaderBB->splitBasicBlock(
292  VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
293  Loop *L = State->LI->getLoopFor(VectorHeaderBB);
294  L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
295  // Remove the edge between Header and Latch to allow other connections.
296  // Temporarily terminate with unreachable until CFG is rewired.
297  // Note: this asserts the generated code's assumption that
298  // getFirstInsertionPt() can be dereferenced into an Instruction.
299  VectorHeaderBB->getTerminator()->eraseFromParent();
300  State->Builder.SetInsertPoint(VectorHeaderBB);
302  State->Builder.SetInsertPoint(Terminator);
303 
304  // 2. Generate code in loop body.
305  State->CFG.PrevVPBB = nullptr;
306  State->CFG.PrevBB = VectorHeaderBB;
307  State->CFG.LastBB = VectorLatchBB;
308 
309  for (VPBlockBase *Block : depth_first(Entry))
310  Block->execute(State);
311 
312  // 3. Merge the temporary latch created with the last basic-block filled.
313  BasicBlock *LastBB = State->CFG.PrevBB;
314  // Connect LastBB to VectorLatchBB to facilitate their merge.
315  assert(isa<UnreachableInst>(LastBB->getTerminator()) &&
316  "Expected VPlan CFG to terminate with unreachable");
317  LastBB->getTerminator()->eraseFromParent();
318  BranchInst::Create(VectorLatchBB, LastBB);
319 
320  // Merge LastBB with Latch.
321  bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
322  (void)Merged;
323  assert(Merged && "Could not merge last basic block with latch.");
324  VectorLatchBB = LastBB;
325 
326  updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB);
327 }
328 
329 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
330  BasicBlock *LoopLatchBB) {
331  BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
332  assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
333  DT->addNewBlock(LoopHeaderBB, LoopPreHeaderBB);
334  // The vector body may be more than a single basic-block by this point.
335  // Update the dominator tree information inside the vector body by propagating
336  // it from header to latch, expecting only triangular control-flow, if any.
337  BasicBlock *PostDomSucc = nullptr;
338  for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
339  // Get the list of successors of this block.
340  std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
341  assert(Succs.size() <= 2 &&
342  "Basic block in vector loop has more than 2 successors.");
343  PostDomSucc = Succs[0];
344  if (Succs.size() == 1) {
345  assert(PostDomSucc->getSinglePredecessor() &&
346  "PostDom successor has more than one predecessor.");
347  DT->addNewBlock(PostDomSucc, BB);
348  continue;
349  }
350  BasicBlock *InterimSucc = Succs[1];
351  if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
352  PostDomSucc = Succs[1];
353  InterimSucc = Succs[0];
354  }
355  assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
356  "One successor of a basic block does not lead to the other.");
357  assert(InterimSucc->getSinglePredecessor() &&
358  "Interim successor has more than one predecessor.");
359  assert(std::distance(pred_begin(PostDomSucc), pred_end(PostDomSucc)) == 2 &&
360  "PostDom successor has more than two predecessors.");
361  DT->addNewBlock(InterimSucc, BB);
362  DT->addNewBlock(PostDomSucc, BB);
363  }
364 }
365 
366 const Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
367  return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
368  Twine(getOrCreateBID(Block));
369 }
370 
371 const Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
372  const std::string &Name = Block->getName();
373  if (!Name.empty())
374  return Name;
375  return "VPB" + Twine(getOrCreateBID(Block));
376 }
377 
378 void VPlanPrinter::dump() {
379  Depth = 1;
380  bumpIndent(0);
381  OS << "digraph VPlan {\n";
382  OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
383  if (!Plan.getName().empty())
384  OS << "\\n" << DOT::EscapeString(Plan.getName());
385  if (!Plan.Value2VPValue.empty()) {
386  OS << ", where:";
387  for (auto Entry : Plan.Value2VPValue) {
388  OS << "\\n" << *Entry.second;
389  OS << DOT::EscapeString(" := ");
390  Entry.first->printAsOperand(OS, false);
391  }
392  }
393  OS << "\"]\n";
394  OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
395  OS << "edge [fontname=Courier, fontsize=30]\n";
396  OS << "compound=true\n";
397 
398  for (VPBlockBase *Block : depth_first(Plan.getEntry()))
399  dumpBlock(Block);
400 
401  OS << "}\n";
402 }
403 
404 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
405  if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
406  dumpBasicBlock(BasicBlock);
407  else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
408  dumpRegion(Region);
409  else
410  llvm_unreachable("Unsupported kind of VPBlock.");
411 }
412 
413 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
414  bool Hidden, const Twine &Label) {
415  // Due to "dot" we print an edge between two regions as an edge between the
416  // exit basic block and the entry basic of the respective regions.
417  const VPBlockBase *Tail = From->getExitBasicBlock();
418  const VPBlockBase *Head = To->getEntryBasicBlock();
419  OS << Indent << getUID(Tail) << " -> " << getUID(Head);
420  OS << " [ label=\"" << Label << '\"';
421  if (Tail != From)
422  OS << " ltail=" << getUID(From);
423  if (Head != To)
424  OS << " lhead=" << getUID(To);
425  if (Hidden)
426  OS << "; splines=none";
427  OS << "]\n";
428 }
429 
430 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
431  auto &Successors = Block->getSuccessors();
432  if (Successors.size() == 1)
433  drawEdge(Block, Successors.front(), false, "");
434  else if (Successors.size() == 2) {
435  drawEdge(Block, Successors.front(), false, "T");
436  drawEdge(Block, Successors.back(), false, "F");
437  } else {
438  unsigned SuccessorNumber = 0;
439  for (auto *Successor : Successors)
440  drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
441  }
442 }
443 
444 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
445  OS << Indent << getUID(BasicBlock) << " [label =\n";
446  bumpIndent(1);
447  OS << Indent << "\"" << DOT::EscapeString(BasicBlock->getName()) << ":\\n\"";
448  bumpIndent(1);
449  for (const VPRecipeBase &Recipe : *BasicBlock)
450  Recipe.print(OS, Indent);
451  bumpIndent(-2);
452  OS << "\n" << Indent << "]\n";
453  dumpEdges(BasicBlock);
454 }
455 
456 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
457  OS << Indent << "subgraph " << getUID(Region) << " {\n";
458  bumpIndent(1);
459  OS << Indent << "fontname=Courier\n"
460  << Indent << "label=\""
461  << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
462  << DOT::EscapeString(Region->getName()) << "\"\n";
463  // Dump the blocks of the region.
464  assert(Region->getEntry() && "Region contains no inner blocks.");
465  for (const VPBlockBase *Block : depth_first(Region->getEntry()))
466  dumpBlock(Block);
467  bumpIndent(-1);
468  OS << Indent << "}\n";
469  dumpEdges(Region);
470 }
471 
472 void VPlanPrinter::printAsIngredient(raw_ostream &O, Value *V) {
473  std::string IngredientString;
474  raw_string_ostream RSO(IngredientString);
475  if (auto *Inst = dyn_cast<Instruction>(V)) {
476  if (!Inst->getType()->isVoidTy()) {
477  Inst->printAsOperand(RSO, false);
478  RSO << " = ";
479  }
480  RSO << Inst->getOpcodeName() << " ";
481  unsigned E = Inst->getNumOperands();
482  if (E > 0) {
483  Inst->getOperand(0)->printAsOperand(RSO, false);
484  for (unsigned I = 1; I < E; ++I)
485  Inst->getOperand(I)->printAsOperand(RSO << ", ", false);
486  }
487  } else // !Inst
488  V->printAsOperand(RSO, false);
489  RSO.flush();
490  O << DOT::EscapeString(IngredientString);
491 }
492 
493 void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent) const {
494  O << " +\n" << Indent << "\"WIDEN\\l\"";
495  for (auto &Instr : make_range(Begin, End))
496  O << " +\n" << Indent << "\" " << VPlanIngredient(&Instr) << "\\l\"";
497 }
498 
500  const Twine &Indent) const {
501  O << " +\n" << Indent << "\"WIDEN-INDUCTION";
502  if (Trunc) {
503  O << "\\l\"";
504  O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
505  O << " +\n" << Indent << "\" " << VPlanIngredient(Trunc) << "\\l\"";
506  } else
507  O << " " << VPlanIngredient(IV) << "\\l\"";
508 }
509 
510 void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
511  O << " +\n" << Indent << "\"WIDEN-PHI " << VPlanIngredient(Phi) << "\\l\"";
512 }
513 
514 void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent) const {
515  O << " +\n" << Indent << "\"BLEND ";
516  Phi->printAsOperand(O, false);
517  O << " =";
518  if (!User) {
519  // Not a User of any mask: not really blending, this is a
520  // single-predecessor phi.
521  O << " ";
522  Phi->getIncomingValue(0)->printAsOperand(O, false);
523  } else {
524  for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I) {
525  O << " ";
526  Phi->getIncomingValue(I)->printAsOperand(O, false);
527  O << "/";
529  }
530  }
531  O << "\\l\"";
532 }
533 
534 void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent) const {
535  O << " +\n"
536  << Indent << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
537  << VPlanIngredient(Ingredient);
538  if (AlsoPack)
539  O << " (S->V)";
540  O << "\\l\"";
541 }
542 
543 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent) const {
544  O << " +\n"
545  << Indent << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst)
546  << "\\l\"";
547 }
548 
550  const Twine &Indent) const {
551  O << " +\n" << Indent << "\"WIDEN " << VPlanIngredient(&Instr);
552  if (User) {
553  O << ", ";
555  }
556  O << "\\l\"";
557 }
const std::string & getName() const
Definition: VPlan.h:366
LoopInfo * LI
Hold a pointer to LoopInfo to register new basic blocks in the loop.
Definition: VPlan.h:284
struct llvm::VPTransformState::CFGState CFG
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:499
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
void execute(struct VPTransformState *State)
Generate the IR code for this VPlan.
Definition: VPlan.cpp:280
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1112
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:229
BasicBlock * PrevBB
The previous IR BasicBlock created or used.
Definition: VPlan.h:270
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:944
IRBuilder & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Definition: VPlan.h:290
const VPBasicBlock * getExitBasicBlock() const
Definition: VPlan.cpp:73
BlockT * getExit() const
Get the exit BasicBlock of the Region.
Definition: RegionInfo.h:360
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:492
Value * get(VPValue *Def, unsigned Part)
Get the generated Value for a given VPValue and a given Part.
Definition: VPlan.h:245
Value * CreateNot(Value *V, const Twine &Name="")
Definition: IRBuilder.h:1146
unsigned VF
The chosen Vectorization and Unroll Factors of the loop being vectorized.
Definition: VPlan.h:223
void execute(VPTransformState &State) override
Generate the instruction.
Definition: VPlan.cpp:247
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:678
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:668
BasicBlock * LastBB
The last IR BasicBlock in the output IR.
Definition: VPlan.h:274
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:58
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:287
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:985
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:244
void set(VPValue *Def, Value *V, unsigned Part)
Set the generated Value for a given VPValue and a given Part.
Definition: VPlan.h:254
const VPBlockBase * getExit() const
Definition: VPlan.h:980
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:215
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:514
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:432
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:448
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block...
Definition: IRBuilder.h:128
Value * getOperand(unsigned i) const
Definition: User.h:154
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:442
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:200
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:217
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:863
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:549
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:278
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:264
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:534
bool isBinaryOp() const
Definition: Instruction.h:130
static const unsigned End
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
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)
VPValue2ValueTy VPValue2Value
Hold a reference to a mapping between VPValues in VPlan and original Values they correspond to...
Definition: VPlan.h:298
void printAsOperand(raw_ostream &OS) const
Definition: VPlanValue.h:64
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:510
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:862
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:3575
#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:176
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:323
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:308
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:543
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:391
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:132
const VPBlockBase * getEntry() const
Definition: VPlan.h:977
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.cpp:493
bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemoryDependenceResults *MemDep=nullptr)
Attempts to merge a block into its predecessor, if possible.
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:394
Flatten the CFG
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:439
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
#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:383
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
iterator_range< df_iterator< T > > depth_first(const T &G)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:462
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:44
#define DEBUG(X)
Definition: Debug.h:118
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:120
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:543
void print(raw_ostream &O, const Twine &Indent) const override
Print the Recipe.
Definition: VPlan.cpp:253
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:266