LLVM  14.0.0git
VPlan.cpp
Go to the documentation of this file.
1 //===- VPlan.cpp - Vectorizer Plan ----------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// This is the LLVM vectorization plan. It represents a candidate for
11 /// vectorization, allowing to plan and optimize how to vectorize a given loop
12 /// before generating LLVM-IR.
13 /// The vectorizer uses vectorization plans to estimate the costs of potential
14 /// candidates and if profitable to execute the desired plan, generating vector
15 /// LLVM-IR code.
16 ///
17 //===----------------------------------------------------------------------===//
18 
19 #include "VPlan.h"
20 #include "VPlanDominatorTree.h"
23 #include "llvm/ADT/STLExtras.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/ADT/Twine.h"
27 #include "llvm/Analysis/LoopInfo.h"
28 #include "llvm/IR/BasicBlock.h"
29 #include "llvm/IR/CFG.h"
30 #include "llvm/IR/InstrTypes.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/Type.h"
34 #include "llvm/IR/Value.h"
35 #include "llvm/Support/Casting.h"
37 #include "llvm/Support/Debug.h"
43 #include <cassert>
44 #include <iterator>
45 #include <string>
46 #include <vector>
47 
48 using namespace llvm;
50 
51 #define DEBUG_TYPE "vplan"
52 
53 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
55  const VPInstruction *Instr = dyn_cast<VPInstruction>(&V);
57  (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
58  V.print(OS, SlotTracker);
59  return OS;
60 }
61 #endif
62 
64  const ElementCount &VF) const {
65  switch (LaneKind) {
67  // Lane = RuntimeVF - VF.getKnownMinValue() + Lane
68  return Builder.CreateSub(getRuntimeVF(Builder, Builder.getInt32Ty(), VF),
69  Builder.getInt32(VF.getKnownMinValue() - Lane));
71  return Builder.getInt32(Lane);
72  }
73  llvm_unreachable("Unknown lane kind");
74 }
75 
76 VPValue::VPValue(const unsigned char SC, Value *UV, VPDef *Def)
77  : SubclassID(SC), UnderlyingVal(UV), Def(Def) {
78  if (Def)
79  Def->addDefinedValue(this);
80 }
81 
83  assert(Users.empty() && "trying to delete a VPValue with remaining users");
84  if (Def)
85  Def->removeDefinedValue(this);
86 }
87 
88 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
90  if (const VPRecipeBase *R = dyn_cast_or_null<VPRecipeBase>(Def))
91  R->print(OS, "", SlotTracker);
92  else
94 }
95 
96 void VPValue::dump() const {
97  const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this->Def);
99  (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
100  print(dbgs(), SlotTracker);
101  dbgs() << "\n";
102 }
103 
104 void VPDef::dump() const {
105  const VPRecipeBase *Instr = dyn_cast_or_null<VPRecipeBase>(this);
107  (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
108  print(dbgs(), "", SlotTracker);
109  dbgs() << "\n";
110 }
111 #endif
112 
113 // Get the top-most entry block of \p Start. This is the entry block of the
114 // containing VPlan. This function is templated to support both const and non-const blocks
115 template <typename T> static T *getPlanEntry(T *Start) {
116  T *Next = Start;
117  T *Current = Start;
118  while ((Next = Next->getParent()))
119  Current = Next;
120 
121  SmallSetVector<T *, 8> WorkList;
122  WorkList.insert(Current);
123 
124  for (unsigned i = 0; i < WorkList.size(); i++) {
125  T *Current = WorkList[i];
126  if (Current->getNumPredecessors() == 0)
127  return Current;
128  auto &Predecessors = Current->getPredecessors();
129  WorkList.insert(Predecessors.begin(), Predecessors.end());
130  }
131 
132  llvm_unreachable("VPlan without any entry node without predecessors");
133 }
134 
135 VPlan *VPBlockBase::getPlan() { return getPlanEntry(this)->Plan; }
136 
137 const VPlan *VPBlockBase::getPlan() const { return getPlanEntry(this)->Plan; }
138 
139 /// \return the VPBasicBlock that is the entry of Block, possibly indirectly.
141  const VPBlockBase *Block = this;
142  while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
143  Block = Region->getEntry();
144  return cast<VPBasicBlock>(Block);
145 }
146 
148  VPBlockBase *Block = this;
149  while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
150  Block = Region->getEntry();
151  return cast<VPBasicBlock>(Block);
152 }
153 
154 void VPBlockBase::setPlan(VPlan *ParentPlan) {
155  assert(ParentPlan->getEntry() == this &&
156  "Can only set plan on its entry block.");
157  Plan = ParentPlan;
158 }
159 
160 /// \return the VPBasicBlock that is the exit of Block, possibly indirectly.
162  const VPBlockBase *Block = this;
163  while (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
164  Block = Region->getExit();
165  return cast<VPBasicBlock>(Block);
166 }
167 
169  VPBlockBase *Block = this;
170  while (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
171  Block = Region->getExit();
172  return cast<VPBasicBlock>(Block);
173 }
174 
176  if (!Successors.empty() || !Parent)
177  return this;
178  assert(Parent->getExit() == this &&
179  "Block w/o successors not the exit of its parent.");
180  return Parent->getEnclosingBlockWithSuccessors();
181 }
182 
184  if (!Predecessors.empty() || !Parent)
185  return this;
186  assert(Parent->getEntry() == this &&
187  "Block w/o predecessors not the entry of its parent.");
188  return Parent->getEnclosingBlockWithPredecessors();
189 }
190 
192  return CondBitUser.getSingleOperandOrNull();
193 }
194 
195 const VPValue *VPBlockBase::getCondBit() const {
196  return CondBitUser.getSingleOperandOrNull();
197 }
198 
199 void VPBlockBase::setCondBit(VPValue *CV) { CondBitUser.resetSingleOpUser(CV); }
200 
202  return PredicateUser.getSingleOperandOrNull();
203 }
204 
205 const VPValue *VPBlockBase::getPredicate() const {
206  return PredicateUser.getSingleOperandOrNull();
207 }
208 
210  PredicateUser.resetSingleOpUser(CV);
211 }
212 
215 
216  for (VPBlockBase *Block : Blocks)
217  delete Block;
218 }
219 
221  iterator It = begin();
222  while (It != end() && It->isPhi())
223  It++;
224  return It;
225 }
226 
228  if (!Def->getDef())
229  return Def->getLiveInIRValue();
230 
231  if (hasScalarValue(Def, Instance)) {
232  return Data
233  .PerPartScalars[Def][Instance.Part][Instance.Lane.mapToCacheIndex(VF)];
234  }
235 
237  auto *VecPart = Data.PerPartOutput[Def][Instance.Part];
238  if (!VecPart->getType()->isVectorTy()) {
239  assert(Instance.Lane.isFirstLane() && "cannot get lane > 0 for scalar");
240  return VecPart;
241  }
242  // TODO: Cache created scalar values.
243  Value *Lane = Instance.Lane.getAsRuntimeExpr(Builder, VF);
244  auto *Extract = Builder.CreateExtractElement(VecPart, Lane);
245  // set(Def, Extract, Instance);
246  return Extract;
247 }
248 
249 BasicBlock *
250 VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
251  // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
252  // Pred stands for Predessor. Prev stands for Previous - last visited/created.
253  BasicBlock *PrevBB = CFG.PrevBB;
254  BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
255  PrevBB->getParent(), CFG.LastBB);
256  LLVM_DEBUG(dbgs() << "LV: created " << NewBB->getName() << '\n');
257 
258  // Hook up the new basic block to its predecessors.
259  for (VPBlockBase *PredVPBlock : getHierarchicalPredecessors()) {
260  VPBasicBlock *PredVPBB = PredVPBlock->getExitBasicBlock();
261  auto &PredVPSuccessors = PredVPBB->getSuccessors();
262  BasicBlock *PredBB = CFG.VPBB2IRBB[PredVPBB];
263 
264  // In outer loop vectorization scenario, the predecessor BBlock may not yet
265  // be visited(backedge). Mark the VPBasicBlock for fixup at the end of
266  // vectorization. We do not encounter this case in inner loop vectorization
267  // as we start out by building a loop skeleton with the vector loop header
268  // and latch blocks. As a result, we never enter this function for the
269  // header block in the non VPlan-native path.
270  if (!PredBB) {
272  "Unexpected null predecessor in non VPlan-native path");
273  CFG.VPBBsToFix.push_back(PredVPBB);
274  continue;
275  }
276 
277  assert(PredBB && "Predecessor basic-block not found building successor.");
278  auto *PredBBTerminator = PredBB->getTerminator();
279  LLVM_DEBUG(dbgs() << "LV: draw edge from" << PredBB->getName() << '\n');
280  if (isa<UnreachableInst>(PredBBTerminator)) {
281  assert(PredVPSuccessors.size() == 1 &&
282  "Predecessor ending w/o branch must have single successor.");
283  PredBBTerminator->eraseFromParent();
284  BranchInst::Create(NewBB, PredBB);
285  } else {
286  assert(PredVPSuccessors.size() == 2 &&
287  "Predecessor ending with branch must have two successors.");
288  unsigned idx = PredVPSuccessors.front() == this ? 0 : 1;
289  assert(!PredBBTerminator->getSuccessor(idx) &&
290  "Trying to reset an existing successor block.");
291  PredBBTerminator->setSuccessor(idx, NewBB);
292  }
293  }
294  return NewBB;
295 }
296 
298  bool Replica = State->Instance && !State->Instance->isFirstIteration();
299  VPBasicBlock *PrevVPBB = State->CFG.PrevVPBB;
300  VPBlockBase *SingleHPred = nullptr;
301  BasicBlock *NewBB = State->CFG.PrevBB; // Reuse it if possible.
302 
303  // 1. Create an IR basic block, or reuse the last one if possible.
304  // The last IR basic block is reused, as an optimization, in three cases:
305  // A. the first VPBB reuses the loop header BB - when PrevVPBB is null;
306  // B. when the current VPBB has a single (hierarchical) predecessor which
307  // is PrevVPBB and the latter has a single (hierarchical) successor; and
308  // C. when the current VPBB is an entry of a region replica - where PrevVPBB
309  // is the exit of this region from a previous instance, or the predecessor
310  // of this region.
311  if (PrevVPBB && /* A */
312  !((SingleHPred = getSingleHierarchicalPredecessor()) &&
313  SingleHPred->getExitBasicBlock() == PrevVPBB &&
314  PrevVPBB->getSingleHierarchicalSuccessor()) && /* B */
315  !(Replica && getPredecessors().empty())) { /* C */
316  NewBB = createEmptyBasicBlock(State->CFG);
317  State->Builder.SetInsertPoint(NewBB);
318  // Temporarily terminate with unreachable until CFG is rewired.
321  // Register NewBB in its loop. In innermost loops its the same for all BB's.
322  Loop *L = State->LI->getLoopFor(State->CFG.LastBB);
323  L->addBasicBlockToLoop(NewBB, *State->LI);
324  State->CFG.PrevBB = NewBB;
325  }
326 
327  // 2. Fill the IR basic block with IR instructions.
328  LLVM_DEBUG(dbgs() << "LV: vectorizing VPBB:" << getName()
329  << " in BB:" << NewBB->getName() << '\n');
330 
331  State->CFG.VPBB2IRBB[this] = NewBB;
332  State->CFG.PrevVPBB = this;
333 
334  for (VPRecipeBase &Recipe : Recipes)
335  Recipe.execute(*State);
336 
337  VPValue *CBV;
338  if (EnableVPlanNativePath && (CBV = getCondBit())) {
339  assert(CBV->getUnderlyingValue() &&
340  "Unexpected null underlying value for condition bit");
341 
342  // Condition bit value in a VPBasicBlock is used as the branch selector. In
343  // the VPlan-native path case, since all branches are uniform we generate a
344  // branch instruction using the condition value from vector lane 0 and dummy
345  // successors. The successors are fixed later when the successor blocks are
346  // visited.
347  Value *NewCond = State->get(CBV, {0, 0});
348 
349  // Replace the temporary unreachable terminator with the new conditional
350  // branch.
351  auto *CurrentTerminator = NewBB->getTerminator();
352  assert(isa<UnreachableInst>(CurrentTerminator) &&
353  "Expected to replace unreachable terminator with conditional "
354  "branch.");
355  auto *CondBr = BranchInst::Create(NewBB, nullptr, NewCond);
356  CondBr->setSuccessor(0, nullptr);
357  ReplaceInstWithInst(CurrentTerminator, CondBr);
358  }
359 
360  LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
361 }
362 
364  for (VPRecipeBase &R : Recipes) {
365  for (auto *Def : R.definedValues())
366  Def->replaceAllUsesWith(NewValue);
367 
368  for (unsigned I = 0, E = R.getNumOperands(); I != E; I++)
369  R.setOperand(I, NewValue);
370  }
371 }
372 
374  assert((SplitAt == end() || SplitAt->getParent() == this) &&
375  "can only split at a position in the same block");
376 
378  // First, disconnect the current block from its successors.
379  for (VPBlockBase *Succ : Succs)
380  VPBlockUtils::disconnectBlocks(this, Succ);
381 
382  // Create new empty block after the block to split.
383  auto *SplitBlock = new VPBasicBlock(getName() + ".split");
385 
386  // Add successors for block to split to new block.
387  for (VPBlockBase *Succ : Succs)
389 
390  // Finally, move the recipes starting at SplitAt to new block.
391  for (VPRecipeBase &ToMove :
392  make_early_inc_range(make_range(SplitAt, this->end())))
393  ToMove.moveBefore(*SplitBlock, SplitBlock->end());
394 
395  return SplitBlock;
396 }
397 
398 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
399 void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const {
400  if (getSuccessors().empty()) {
401  O << Indent << "No successors\n";
402  } else {
403  O << Indent << "Successor(s): ";
404  ListSeparator LS;
405  for (auto *Succ : getSuccessors())
406  O << LS << Succ->getName();
407  O << '\n';
408  }
409 }
410 
411 void VPBasicBlock::print(raw_ostream &O, const Twine &Indent,
412  VPSlotTracker &SlotTracker) const {
413  O << Indent << getName() << ":\n";
414  if (const VPValue *Pred = getPredicate()) {
415  O << Indent << "BlockPredicate:";
416  Pred->printAsOperand(O, SlotTracker);
417  if (const auto *PredInst = dyn_cast<VPInstruction>(Pred))
418  O << " (" << PredInst->getParent()->getName() << ")";
419  O << '\n';
420  }
421 
422  auto RecipeIndent = Indent + " ";
423  for (const VPRecipeBase &Recipe : *this) {
424  Recipe.print(O, RecipeIndent, SlotTracker);
425  O << '\n';
426  }
427 
428  printSuccessors(O, Indent);
429 
430  if (const VPValue *CBV = getCondBit()) {
431  O << Indent << "CondBit: ";
432  CBV->printAsOperand(O, SlotTracker);
433  if (const auto *CBI = dyn_cast<VPInstruction>(CBV))
434  O << " (" << CBI->getParent()->getName() << ")";
435  O << '\n';
436  }
437 }
438 #endif
439 
441  for (VPBlockBase *Block : depth_first(Entry))
442  // Drop all references in VPBasicBlocks and replace all uses with
443  // DummyValue.
444  Block->dropAllReferences(NewValue);
445 }
446 
449 
450  if (!isReplicator()) {
451  // Visit the VPBlocks connected to "this", starting from it.
452  for (VPBlockBase *Block : RPOT) {
453  if (EnableVPlanNativePath) {
454  // The inner loop vectorization path does not represent loop preheader
455  // and exit blocks as part of the VPlan. In the VPlan-native path, skip
456  // vectorizing loop preheader block. In future, we may replace this
457  // check with the check for loop preheader.
458  if (Block->getNumPredecessors() == 0)
459  continue;
460 
461  // Skip vectorizing loop exit block. In future, we may replace this
462  // check with the check for loop exit.
463  if (Block->getNumSuccessors() == 0)
464  continue;
465  }
466 
467  LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
468  Block->execute(State);
469  }
470  return;
471  }
472 
473  assert(!State->Instance && "Replicating a Region with non-null instance.");
474 
475  // Enter replicating mode.
476  State->Instance = VPIteration(0, 0);
477 
478  for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
479  State->Instance->Part = Part;
480  assert(!State->VF.isScalable() && "VF is assumed to be non scalable.");
481  for (unsigned Lane = 0, VF = State->VF.getKnownMinValue(); Lane < VF;
482  ++Lane) {
483  State->Instance->Lane = VPLane(Lane, VPLane::Kind::First);
484  // Visit the VPBlocks connected to \p this, starting from it.
485  for (VPBlockBase *Block : RPOT) {
486  LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
487  Block->execute(State);
488  }
489  }
490  }
491 
492  // Exit replicating mode.
493  State->Instance.reset();
494 }
495 
496 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
498  VPSlotTracker &SlotTracker) const {
499  O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {";
500  auto NewIndent = Indent + " ";
501  for (auto *BlockBase : depth_first(Entry)) {
502  O << '\n';
503  BlockBase->print(O, NewIndent, SlotTracker);
504  }
505  O << Indent << "}\n";
506 
507  printSuccessors(O, Indent);
508 }
509 #endif
510 
512  switch (getVPDefID()) {
513  case VPWidenMemoryInstructionSC: {
514  return cast<VPWidenMemoryInstructionRecipe>(this)->isStore();
515  }
516  case VPReplicateSC:
517  case VPWidenCallSC:
518  return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
519  ->mayWriteToMemory();
520  case VPBranchOnMaskSC:
521  return false;
522  case VPWidenIntOrFpInductionSC:
523  case VPWidenCanonicalIVSC:
524  case VPWidenPHISC:
525  case VPBlendSC:
526  case VPWidenSC:
527  case VPWidenGEPSC:
528  case VPReductionSC:
529  case VPWidenSelectSC: {
530  const Instruction *I =
531  dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
532  (void)I;
533  assert((!I || !I->mayWriteToMemory()) &&
534  "underlying instruction may write to memory");
535  return false;
536  }
537  default:
538  return true;
539  }
540 }
541 
543  switch (getVPDefID()) {
544  case VPWidenMemoryInstructionSC: {
545  return !cast<VPWidenMemoryInstructionRecipe>(this)->isStore();
546  }
547  case VPReplicateSC:
548  case VPWidenCallSC:
549  return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
550  ->mayReadFromMemory();
551  case VPBranchOnMaskSC:
552  return false;
553  case VPWidenIntOrFpInductionSC:
554  case VPWidenCanonicalIVSC:
555  case VPWidenPHISC:
556  case VPBlendSC:
557  case VPWidenSC:
558  case VPWidenGEPSC:
559  case VPReductionSC:
560  case VPWidenSelectSC: {
561  const Instruction *I =
562  dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
563  (void)I;
564  assert((!I || !I->mayReadFromMemory()) &&
565  "underlying instruction may read from memory");
566  return false;
567  }
568  default:
569  return true;
570  }
571 }
572 
574  switch (getVPDefID()) {
575  case VPBranchOnMaskSC:
576  return false;
577  case VPWidenIntOrFpInductionSC:
578  case VPWidenCanonicalIVSC:
579  case VPWidenPHISC:
580  case VPBlendSC:
581  case VPWidenSC:
582  case VPWidenGEPSC:
583  case VPReductionSC:
584  case VPWidenSelectSC: {
585  const Instruction *I =
586  dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
587  (void)I;
588  assert((!I || !I->mayHaveSideEffects()) &&
589  "underlying instruction has side-effects");
590  return false;
591  }
592  case VPReplicateSC: {
593  auto *R = cast<VPReplicateRecipe>(this);
594  return R->getUnderlyingInstr()->mayHaveSideEffects();
595  }
596  default:
597  return true;
598  }
599 }
600 
602  assert(!Parent && "Recipe already in some VPBasicBlock");
603  assert(InsertPos->getParent() &&
604  "Insertion position not in any VPBasicBlock");
605  Parent = InsertPos->getParent();
606  Parent->getRecipeList().insert(InsertPos->getIterator(), this);
607 }
608 
610  assert(!Parent && "Recipe already in some VPBasicBlock");
611  assert(InsertPos->getParent() &&
612  "Insertion position not in any VPBasicBlock");
613  Parent = InsertPos->getParent();
614  Parent->getRecipeList().insertAfter(InsertPos->getIterator(), this);
615 }
616 
618  assert(getParent() && "Recipe not in any VPBasicBlock");
620  Parent = nullptr;
621 }
622 
624  assert(getParent() && "Recipe not in any VPBasicBlock");
625  return getParent()->getRecipeList().erase(getIterator());
626 }
627 
630  insertAfter(InsertPos);
631 }
632 
635  assert(I == BB.end() || I->getParent() == &BB);
637  Parent = &BB;
638  BB.getRecipeList().insert(I, this);
639 }
640 
641 void VPInstruction::generateInstruction(VPTransformState &State,
642  unsigned Part) {
643  IRBuilder<> &Builder = State.Builder;
644  Builder.SetCurrentDebugLocation(DL);
645 
647  Value *A = State.get(getOperand(0), Part);
648  Value *B = State.get(getOperand(1), Part);
649  Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
650  State.set(this, V, Part);
651  return;
652  }
653 
654  switch (getOpcode()) {
655  case VPInstruction::Not: {
656  Value *A = State.get(getOperand(0), Part);
657  Value *V = Builder.CreateNot(A);
658  State.set(this, V, Part);
659  break;
660  }
661  case VPInstruction::ICmpULE: {
662  Value *IV = State.get(getOperand(0), Part);
663  Value *TC = State.get(getOperand(1), Part);
664  Value *V = Builder.CreateICmpULE(IV, TC);
665  State.set(this, V, Part);
666  break;
667  }
668  case Instruction::Select: {
669  Value *Cond = State.get(getOperand(0), Part);
670  Value *Op1 = State.get(getOperand(1), Part);
671  Value *Op2 = State.get(getOperand(2), Part);
672  Value *V = Builder.CreateSelect(Cond, Op1, Op2);
673  State.set(this, V, Part);
674  break;
675  }
677  // Get first lane of vector induction variable.
678  Value *VIVElem0 = State.get(getOperand(0), VPIteration(Part, 0));
679  // Get the original loop tripcount.
680  Value *ScalarTC = State.get(getOperand(1), Part);
681 
682  auto *Int1Ty = Type::getInt1Ty(Builder.getContext());
683  auto *PredTy = VectorType::get(Int1Ty, State.VF);
684  Instruction *Call = Builder.CreateIntrinsic(
685  Intrinsic::get_active_lane_mask, {PredTy, ScalarTC->getType()},
686  {VIVElem0, ScalarTC}, nullptr, "active.lane.mask");
687  State.set(this, Call, Part);
688  break;
689  }
691  // Generate code to combine the previous and current values in vector v3.
692  //
693  // vector.ph:
694  // v_init = vector(..., ..., ..., a[-1])
695  // br vector.body
696  //
697  // vector.body
698  // i = phi [0, vector.ph], [i+4, vector.body]
699  // v1 = phi [v_init, vector.ph], [v2, vector.body]
700  // v2 = a[i, i+1, i+2, i+3];
701  // v3 = vector(v1(3), v2(0, 1, 2))
702 
703  // For the first part, use the recurrence phi (v1), otherwise v2.
704  auto *V1 = State.get(getOperand(0), 0);
705  Value *PartMinus1 = Part == 0 ? V1 : State.get(getOperand(1), Part - 1);
706  if (!PartMinus1->getType()->isVectorTy()) {
707  State.set(this, PartMinus1, Part);
708  } else {
709  Value *V2 = State.get(getOperand(1), Part);
710  State.set(this, Builder.CreateVectorSplice(PartMinus1, V2, -1), Part);
711  }
712  break;
713  }
714 
717  Value *Next = nullptr;
718  if (Part == 0) {
720  auto *Phi = State.get(getOperand(0), 0);
721  // The loop step is equal to the vectorization factor (num of SIMD
722  // elements) times the unroll factor (num of SIMD instructions).
723  Value *Step =
724  createStepForVF(Builder, Phi->getType(), State.VF, State.UF);
725  Next = Builder.CreateAdd(Phi, Step, "index.next", IsNUW, false);
726  } else {
727  Next = State.get(this, 0);
728  }
729 
730  State.set(this, Next, Part);
731  break;
732  }
734  if (Part != 0)
735  break;
736  // First create the compare.
737  Value *IV = State.get(getOperand(0), Part);
738  Value *TC = State.get(getOperand(1), Part);
739  Value *Cond = Builder.CreateICmpEQ(IV, TC);
740 
741  // Now create the branch.
742  auto *Plan = getParent()->getPlan();
743  VPRegionBlock *TopRegion = Plan->getVectorLoopRegion();
744  VPBasicBlock *Header = TopRegion->getEntry()->getEntryBasicBlock();
745  if (Header->empty()) {
747  "empty entry block only expected in VPlanNativePath");
748  Header = cast<VPBasicBlock>(Header->getSingleSuccessor());
749  }
750  // TODO: Once the exit block is modeled in VPlan, use it instead of going
751  // through State.CFG.LastBB.
752  BasicBlock *Exit =
753  cast<BranchInst>(State.CFG.LastBB->getTerminator())->getSuccessor(0);
754 
755  Builder.CreateCondBr(Cond, Exit, State.CFG.VPBB2IRBB[Header]);
756  Builder.GetInsertBlock()->getTerminator()->eraseFromParent();
757  break;
758  }
759  default:
760  llvm_unreachable("Unsupported opcode for instruction");
761  }
762 }
763 
765  assert(!State.Instance && "VPInstruction executing an Instance");
767  State.Builder.setFastMathFlags(FMF);
768  for (unsigned Part = 0; Part < State.UF; ++Part)
769  generateInstruction(State, Part);
770 }
771 
772 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
773 void VPInstruction::dump() const {
774  VPSlotTracker SlotTracker(getParent()->getPlan());
775  print(dbgs(), "", SlotTracker);
776 }
777 
779  VPSlotTracker &SlotTracker) const {
780  O << Indent << "EMIT ";
781 
782  if (hasResult()) {
784  O << " = ";
785  }
786 
787  switch (getOpcode()) {
788  case VPInstruction::Not:
789  O << "not";
790  break;
792  O << "icmp ule";
793  break;
795  O << "combined load";
796  break;
798  O << "combined store";
799  break;
801  O << "active lane mask";
802  break;
804  O << "first-order splice";
805  break;
807  O << "VF * UF + ";
808  break;
810  O << "VF * UF +(nuw) ";
811  break;
813  O << "branch-on-count ";
814  break;
815  default:
817  }
818 
819  O << FMF;
820 
821  for (const VPValue *Operand : operands()) {
822  O << " ";
823  Operand->printAsOperand(O, SlotTracker);
824  }
825 
826  if (DL) {
827  O << ", !dbg ";
828  DL.print(O);
829  }
830 }
831 #endif
832 
834  // Make sure the VPInstruction is a floating-point operation.
835  assert((Opcode == Instruction::FAdd || Opcode == Instruction::FMul ||
836  Opcode == Instruction::FNeg || Opcode == Instruction::FSub ||
837  Opcode == Instruction::FDiv || Opcode == Instruction::FRem ||
838  Opcode == Instruction::FCmp) &&
839  "this op can't take fast-math flags");
840  FMF = FMFNew;
841 }
842 
843 void VPlan::prepareToExecute(Value *TripCountV, Value *VectorTripCountV,
844  Value *CanonicalIVStartValue,
845  VPTransformState &State) {
846  // Check if the trip count is needed, and if so build it.
847  if (TripCount && TripCount->getNumUsers()) {
848  for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part)
849  State.set(TripCount, TripCountV, Part);
850  }
851 
852  // Check if the backedge taken count is needed, and if so build it.
853  if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
855  auto *TCMO = Builder.CreateSub(TripCountV,
856  ConstantInt::get(TripCountV->getType(), 1),
857  "trip.count.minus.1");
858  auto VF = State.VF;
859  Value *VTCMO =
860  VF.isScalar() ? TCMO : Builder.CreateVectorSplat(VF, TCMO, "broadcast");
861  for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part)
862  State.set(BackedgeTakenCount, VTCMO, Part);
863  }
864 
865  for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part)
866  State.set(&VectorTripCount, VectorTripCountV, Part);
867 
868  // When vectorizing the epilogue loop, the canonical induction start value
869  // needs to be changed from zero to the value after the main vector loop.
870  if (CanonicalIVStartValue) {
871  VPValue *VPV = new VPValue(CanonicalIVStartValue);
872  addExternalDef(VPV);
873  auto *IV = getCanonicalIV();
874  assert(all_of(IV->users(),
875  [](const VPUser *U) {
876  auto *VPI = cast<VPInstruction>(U);
877  return VPI->getOpcode() ==
878  VPInstruction::CanonicalIVIncrement ||
879  VPI->getOpcode() ==
880  VPInstruction::CanonicalIVIncrementNUW;
881  }) &&
882  "the canonical IV should only be used by its increments when "
883  "resetting the start value");
884  IV->setOperand(0, VPV);
885  }
886 }
887 
888 /// Generate the code inside the body of the vectorized loop. Assumes a single
889 /// LoopVectorBody basic-block was created for this. Introduce additional
890 /// basic-blocks as needed, and fill them all.
892  // 0. Set the reverse mapping from VPValues to Values for code generation.
893  for (auto &Entry : Value2VPValue)
894  State->VPValue2Value[Entry.second] = Entry.first;
895 
896  BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
897  State->CFG.VectorPreHeader = VectorPreHeaderBB;
898  BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
899  assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
900 
901  // 1. Make room to generate basic-blocks inside loop body if needed.
902  BasicBlock *VectorLatchBB = VectorHeaderBB->splitBasicBlock(
903  VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
904  Loop *L = State->LI->getLoopFor(VectorHeaderBB);
905  L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
906  // Remove the edge between Header and Latch to allow other connections.
907  // Temporarily terminate with unreachable until CFG is rewired.
908  // Note: this asserts the generated code's assumption that
909  // getFirstInsertionPt() can be dereferenced into an Instruction.
910  VectorHeaderBB->getTerminator()->eraseFromParent();
911  State->Builder.SetInsertPoint(VectorHeaderBB);
914 
915  // 2. Generate code in loop body.
916  State->CFG.PrevVPBB = nullptr;
917  State->CFG.PrevBB = VectorHeaderBB;
918  State->CFG.LastBB = VectorLatchBB;
919 
920  for (VPBlockBase *Block : depth_first(Entry))
921  Block->execute(State);
922 
923  // Setup branch terminator successors for VPBBs in VPBBsToFix based on
924  // VPBB's successors.
925  for (auto VPBB : State->CFG.VPBBsToFix) {
927  "Unexpected VPBBsToFix in non VPlan-native path");
928  BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB];
929  assert(BB && "Unexpected null basic block for VPBB");
930 
931  unsigned Idx = 0;
932  auto *BBTerminator = BB->getTerminator();
933 
934  for (VPBlockBase *SuccVPBlock : VPBB->getHierarchicalSuccessors()) {
935  VPBasicBlock *SuccVPBB = SuccVPBlock->getEntryBasicBlock();
936  BBTerminator->setSuccessor(Idx, State->CFG.VPBB2IRBB[SuccVPBB]);
937  ++Idx;
938  }
939  }
940 
941  // 3. Merge the temporary latch created with the last basic-block filled.
942  BasicBlock *LastBB = State->CFG.PrevBB;
943  assert(isa<BranchInst>(LastBB->getTerminator()) &&
944  "Expected VPlan CFG to terminate with branch");
945 
946  // Move both the branch and check from LastBB to VectorLatchBB.
947  auto *LastBranch = cast<BranchInst>(LastBB->getTerminator());
948  LastBranch->moveBefore(VectorLatchBB->getTerminator());
949  VectorLatchBB->getTerminator()->eraseFromParent();
950  // Move condition so it is guaranteed to be next to branch. This is only done
951  // to avoid excessive test updates.
952  // TODO: Remove special handling once the increments for all inductions are
953  // modeled explicitly in VPlan.
954  cast<Instruction>(LastBranch->getCondition())->moveBefore(LastBranch);
955  // Connect LastBB to VectorLatchBB to facilitate their merge.
956  BranchInst::Create(VectorLatchBB, LastBB);
957 
958  // Merge LastBB with Latch.
959  bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
960  (void)Merged;
961  assert(Merged && "Could not merge last basic block with latch.");
962  VectorLatchBB = LastBB;
963 
964  // Fix the latch value of canonical, reduction and first-order recurrences
965  // phis in the vector loop.
966  VPBasicBlock *Header = Entry->getEntryBasicBlock();
967  if (Header->empty()) {
969  Header = cast<VPBasicBlock>(Header->getSingleSuccessor());
970  }
971  for (VPRecipeBase &R : Header->phis()) {
972  // Skip phi-like recipes that generate their backedege values themselves.
973  // TODO: Model their backedge values explicitly.
974  if (isa<VPWidenIntOrFpInductionRecipe>(&R) || isa<VPWidenPHIRecipe>(&R))
975  continue;
976 
977  auto *PhiR = cast<VPHeaderPHIRecipe>(&R);
978  // For canonical IV, first-order recurrences and in-order reduction phis,
979  // only a single part is generated, which provides the last part from the
980  // previous iteration. For non-ordered reductions all UF parts are
981  // generated.
982  bool SinglePartNeeded = isa<VPCanonicalIVPHIRecipe>(PhiR) ||
983  isa<VPFirstOrderRecurrencePHIRecipe>(PhiR) ||
984  cast<VPReductionPHIRecipe>(PhiR)->isOrdered();
985  unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->UF;
986 
987  for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
988  Value *Phi = State->get(PhiR, Part);
989  Value *Val = State->get(PhiR->getBackedgeValue(),
990  SinglePartNeeded ? State->UF - 1 : Part);
991  cast<PHINode>(Phi)->addIncoming(Val, VectorLatchBB);
992  }
993  }
994 
995  // We do not attempt to preserve DT for outer loop vectorization currently.
997  updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB,
998  L->getExitBlock());
999 }
1000 
1001 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1004  VPSlotTracker SlotTracker(this);
1005 
1006  O << "VPlan '" << Name << "' {";
1007 
1008  if (VectorTripCount.getNumUsers() > 0) {
1009  O << "\nLive-in ";
1010  VectorTripCount.printAsOperand(O, SlotTracker);
1011  O << " = vector-trip-count\n";
1012  }
1013 
1014  if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
1015  O << "\nLive-in ";
1016  BackedgeTakenCount->printAsOperand(O, SlotTracker);
1017  O << " = backedge-taken count\n";
1018  }
1019 
1020  for (const VPBlockBase *Block : depth_first(getEntry())) {
1021  O << '\n';
1022  Block->print(O, "", SlotTracker);
1023  }
1024  O << "}\n";
1025 }
1026 
1029  VPlanPrinter Printer(O, *this);
1030  Printer.dump();
1031 }
1032 
1034 void VPlan::dump() const { print(dbgs()); }
1035 #endif
1036 
1037 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
1038  BasicBlock *LoopLatchBB,
1039  BasicBlock *LoopExitBB) {
1040  BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
1041  assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
1042  // The vector body may be more than a single basic-block by this point.
1043  // Update the dominator tree information inside the vector body by propagating
1044  // it from header to latch, expecting only triangular control-flow, if any.
1045  BasicBlock *PostDomSucc = nullptr;
1046  for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
1047  // Get the list of successors of this block.
1048  std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
1049  assert(Succs.size() <= 2 &&
1050  "Basic block in vector loop has more than 2 successors.");
1051  PostDomSucc = Succs[0];
1052  if (Succs.size() == 1) {
1053  assert(PostDomSucc->getSinglePredecessor() &&
1054  "PostDom successor has more than one predecessor.");
1055  DT->addNewBlock(PostDomSucc, BB);
1056  continue;
1057  }
1058  BasicBlock *InterimSucc = Succs[1];
1059  if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
1060  PostDomSucc = Succs[1];
1061  InterimSucc = Succs[0];
1062  }
1063  assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
1064  "One successor of a basic block does not lead to the other.");
1065  assert(InterimSucc->getSinglePredecessor() &&
1066  "Interim successor has more than one predecessor.");
1067  assert(PostDomSucc->hasNPredecessors(2) &&
1068  "PostDom successor has more than two predecessors.");
1069  DT->addNewBlock(InterimSucc, BB);
1070  DT->addNewBlock(PostDomSucc, BB);
1071  }
1072  // Latch block is a new dominator for the loop exit.
1073  DT->changeImmediateDominator(LoopExitBB, LoopLatchBB);
1075 }
1076 
1077 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1078 Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
1079  return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
1080  Twine(getOrCreateBID(Block));
1081 }
1082 
1083 Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
1084  const std::string &Name = Block->getName();
1085  if (!Name.empty())
1086  return Name;
1087  return "VPB" + Twine(getOrCreateBID(Block));
1088 }
1089 
1091  Depth = 1;
1092  bumpIndent(0);
1093  OS << "digraph VPlan {\n";
1094  OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
1095  if (!Plan.getName().empty())
1096  OS << "\\n" << DOT::EscapeString(Plan.getName());
1097  if (Plan.BackedgeTakenCount) {
1098  OS << ", where:\\n";
1099  Plan.BackedgeTakenCount->print(OS, SlotTracker);
1100  OS << " := BackedgeTakenCount";
1101  }
1102  OS << "\"]\n";
1103  OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
1104  OS << "edge [fontname=Courier, fontsize=30]\n";
1105  OS << "compound=true\n";
1106 
1107  for (const VPBlockBase *Block : depth_first(Plan.getEntry()))
1108  dumpBlock(Block);
1109 
1110  OS << "}\n";
1111 }
1112 
1113 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
1114  if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
1115  dumpBasicBlock(BasicBlock);
1116  else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1117  dumpRegion(Region);
1118  else
1119  llvm_unreachable("Unsupported kind of VPBlock.");
1120 }
1121 
1122 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
1123  bool Hidden, const Twine &Label) {
1124  // Due to "dot" we print an edge between two regions as an edge between the
1125  // exit basic block and the entry basic of the respective regions.
1126  const VPBlockBase *Tail = From->getExitBasicBlock();
1127  const VPBlockBase *Head = To->getEntryBasicBlock();
1128  OS << Indent << getUID(Tail) << " -> " << getUID(Head);
1129  OS << " [ label=\"" << Label << '\"';
1130  if (Tail != From)
1131  OS << " ltail=" << getUID(From);
1132  if (Head != To)
1133  OS << " lhead=" << getUID(To);
1134  if (Hidden)
1135  OS << "; splines=none";
1136  OS << "]\n";
1137 }
1138 
1139 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
1140  auto &Successors = Block->getSuccessors();
1141  if (Successors.size() == 1)
1142  drawEdge(Block, Successors.front(), false, "");
1143  else if (Successors.size() == 2) {
1144  drawEdge(Block, Successors.front(), false, "T");
1145  drawEdge(Block, Successors.back(), false, "F");
1146  } else {
1147  unsigned SuccessorNumber = 0;
1148  for (auto *Successor : Successors)
1149  drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
1150  }
1151 }
1152 
1153 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
1154  // Implement dot-formatted dump by performing plain-text dump into the
1155  // temporary storage followed by some post-processing.
1156  OS << Indent << getUID(BasicBlock) << " [label =\n";
1157  bumpIndent(1);
1158  std::string Str;
1159  raw_string_ostream SS(Str);
1160  // Use no indentation as we need to wrap the lines into quotes ourselves.
1161  BasicBlock->print(SS, "", SlotTracker);
1162 
1163  // We need to process each line of the output separately, so split
1164  // single-string plain-text dump.
1166  StringRef(Str).rtrim('\n').split(Lines, "\n");
1167 
1168  auto EmitLine = [&](StringRef Line, StringRef Suffix) {
1169  OS << Indent << '"' << DOT::EscapeString(Line.str()) << "\\l\"" << Suffix;
1170  };
1171 
1172  // Don't need the "+" after the last line.
1173  for (auto Line : make_range(Lines.begin(), Lines.end() - 1))
1174  EmitLine(Line, " +\n");
1175  EmitLine(Lines.back(), "\n");
1176 
1177  bumpIndent(-1);
1178  OS << Indent << "]\n";
1179 
1180  dumpEdges(BasicBlock);
1181 }
1182 
1183 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
1184  OS << Indent << "subgraph " << getUID(Region) << " {\n";
1185  bumpIndent(1);
1186  OS << Indent << "fontname=Courier\n"
1187  << Indent << "label=\""
1188  << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
1189  << DOT::EscapeString(Region->getName()) << "\"\n";
1190  // Dump the blocks of the region.
1191  assert(Region->getEntry() && "Region contains no inner blocks.");
1192  for (const VPBlockBase *Block : depth_first(Region->getEntry()))
1193  dumpBlock(Block);
1194  bumpIndent(-1);
1195  OS << Indent << "}\n";
1196  dumpEdges(Region);
1197 }
1198 
1200  if (auto *Inst = dyn_cast<Instruction>(V)) {
1201  if (!Inst->getType()->isVoidTy()) {
1202  Inst->printAsOperand(O, false);
1203  O << " = ";
1204  }
1205  O << Inst->getOpcodeName() << " ";
1206  unsigned E = Inst->getNumOperands();
1207  if (E > 0) {
1208  Inst->getOperand(0)->printAsOperand(O, false);
1209  for (unsigned I = 1; I < E; ++I)
1210  Inst->getOperand(I)->printAsOperand(O << ", ", false);
1211  }
1212  } else // !Inst
1213  V->printAsOperand(O, false);
1214 }
1215 
1217  VPSlotTracker &SlotTracker) const {
1218  O << Indent << "WIDEN-CALL ";
1219 
1220  auto *CI = cast<CallInst>(getUnderlyingInstr());
1221  if (CI->getType()->isVoidTy())
1222  O << "void ";
1223  else {
1225  O << " = ";
1226  }
1227 
1228  O << "call @" << CI->getCalledFunction()->getName() << "(";
1230  O << ")";
1231 }
1232 
1234  VPSlotTracker &SlotTracker) const {
1235  O << Indent << "WIDEN-SELECT ";
1237  O << " = select ";
1239  O << ", ";
1241  O << ", ";
1243  O << (InvariantCond ? " (condition is loop invariant)" : "");
1244 }
1245 
1247  VPSlotTracker &SlotTracker) const {
1248  O << Indent << "WIDEN ";
1250  O << " = " << getUnderlyingInstr()->getOpcodeName() << " ";
1252 }
1253 
1255  VPSlotTracker &SlotTracker) const {
1256  O << Indent << "WIDEN-INDUCTION";
1257  if (getTruncInst()) {
1258  O << "\\l\"";
1259  O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
1260  O << " +\n" << Indent << "\" ";
1262  } else
1263  O << " " << VPlanIngredient(IV);
1264 }
1265 #endif
1266 
1268  auto *StartC = dyn_cast<ConstantInt>(getStartValue()->getLiveInIRValue());
1269  auto *StepC = dyn_cast<SCEVConstant>(getInductionDescriptor().getStep());
1270  return StartC && StartC->isZero() && StepC && StepC->isOne();
1271 }
1272 
1273 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1275  VPSlotTracker &SlotTracker) const {
1276  O << Indent << "WIDEN-GEP ";
1277  O << (IsPtrLoopInvariant ? "Inv" : "Var");
1278  size_t IndicesNumber = IsIndexLoopInvariant.size();
1279  for (size_t I = 0; I < IndicesNumber; ++I)
1280  O << "[" << (IsIndexLoopInvariant[I] ? "Inv" : "Var") << "]";
1281 
1282  O << " ";
1284  O << " = getelementptr ";
1286 }
1287 
1289  VPSlotTracker &SlotTracker) const {
1290  O << Indent << "WIDEN-PHI ";
1291 
1292  auto *OriginalPhi = cast<PHINode>(getUnderlyingValue());
1293  // Unless all incoming values are modeled in VPlan print the original PHI
1294  // directly.
1295  // TODO: Remove once all VPWidenPHIRecipe instances keep all relevant incoming
1296  // values as VPValues.
1297  if (getNumOperands() != OriginalPhi->getNumOperands()) {
1298  O << VPlanIngredient(OriginalPhi);
1299  return;
1300  }
1301 
1303  O << " = phi ";
1305 }
1306 
1308  VPSlotTracker &SlotTracker) const {
1309  O << Indent << "BLEND ";
1310  Phi->printAsOperand(O, false);
1311  O << " =";
1312  if (getNumIncomingValues() == 1) {
1313  // Not a User of any mask: not really blending, this is a
1314  // single-predecessor phi.
1315  O << " ";
1317  } else {
1318  for (unsigned I = 0, E = getNumIncomingValues(); I < E; ++I) {
1319  O << " ";
1321  O << "/";
1323  }
1324  }
1325 }
1326 
1328  VPSlotTracker &SlotTracker) const {
1329  O << Indent << "REDUCE ";
1331  O << " = ";
1333  O << " +";
1334  if (isa<FPMathOperator>(getUnderlyingInstr()))
1336  O << " reduce." << Instruction::getOpcodeName(RdxDesc->getOpcode()) << " (";
1338  if (getCondOp()) {
1339  O << ", ";
1341  }
1342  O << ")";
1343 }
1344 
1346  VPSlotTracker &SlotTracker) const {
1347  O << Indent << (IsUniform ? "CLONE " : "REPLICATE ");
1348 
1349  if (!getUnderlyingInstr()->getType()->isVoidTy()) {
1351  O << " = ";
1352  }
1355 
1356  if (AlsoPack)
1357  O << " (S->V)";
1358 }
1359 
1361  VPSlotTracker &SlotTracker) const {
1362  O << Indent << "PHI-PREDICATED-INSTRUCTION ";
1364  O << " = ";
1366 }
1367 
1369  VPSlotTracker &SlotTracker) const {
1370  O << Indent << "WIDEN ";
1371 
1372  if (!isStore()) {
1374  O << " = ";
1375  }
1376  O << Instruction::getOpcodeName(Ingredient.getOpcode()) << " ";
1377 
1379 }
1380 #endif
1381 
1383  Value *Start = getStartValue()->getLiveInIRValue();
1384  PHINode *EntryPart = PHINode::Create(
1385  Start->getType(), 2, "index", &*State.CFG.PrevBB->getFirstInsertionPt());
1386  EntryPart->addIncoming(Start, State.CFG.VectorPreHeader);
1387  EntryPart->setDebugLoc(DL);
1388  for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part)
1389  State.set(this, EntryPart, Part);
1390 }
1391 
1392 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1394  VPSlotTracker &SlotTracker) const {
1395  O << Indent << "EMIT ";
1397  O << " = CANONICAL-INDUCTION";
1398 }
1399 #endif
1400 
1402  Value *CanonicalIV = State.get(getOperand(0), 0);
1403  Type *STy = CanonicalIV->getType();
1405  ElementCount VF = State.VF;
1406  Value *VStart = VF.isScalar()
1407  ? CanonicalIV
1408  : Builder.CreateVectorSplat(VF, CanonicalIV, "broadcast");
1409  for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part) {
1410  Value *VStep = createStepForVF(Builder, STy, VF, Part);
1411  if (VF.isVector()) {
1412  VStep = Builder.CreateVectorSplat(VF, VStep);
1413  VStep = Builder.CreateAdd(VStep, Builder.CreateStepVector(VStep->getType()));
1414  }
1415  Value *CanonicalVectorIV = Builder.CreateAdd(VStart, VStep, "vec.iv");
1416  State.set(this, CanonicalVectorIV, Part);
1417  }
1418 }
1419 
1420 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1422  VPSlotTracker &SlotTracker) const {
1423  O << Indent << "EMIT ";
1425  O << " = WIDEN-CANONICAL-INDUCTION ";
1427 }
1428 #endif
1429 
1431  auto &Builder = State.Builder;
1432  // Create a vector from the initial value.
1433  auto *VectorInit = getStartValue()->getLiveInIRValue();
1434 
1435  Type *VecTy = State.VF.isScalar()
1436  ? VectorInit->getType()
1437  : VectorType::get(VectorInit->getType(), State.VF);
1438 
1439  if (State.VF.isVector()) {
1440  auto *IdxTy = Builder.getInt32Ty();
1441  auto *One = ConstantInt::get(IdxTy, 1);
1443  Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
1444  auto *RuntimeVF = getRuntimeVF(Builder, IdxTy, State.VF);
1445  auto *LastIdx = Builder.CreateSub(RuntimeVF, One);
1446  VectorInit = Builder.CreateInsertElement(
1447  PoisonValue::get(VecTy), VectorInit, LastIdx, "vector.recur.init");
1448  }
1449 
1450  // Create a phi node for the new recurrence.
1451  PHINode *EntryPart = PHINode::Create(
1452  VecTy, 2, "vector.recur", &*State.CFG.PrevBB->getFirstInsertionPt());
1453  EntryPart->addIncoming(VectorInit, State.CFG.VectorPreHeader);
1454  State.set(this, EntryPart, 0);
1455 }
1456 
1457 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1459  VPSlotTracker &SlotTracker) const {
1460  O << Indent << "FIRST-ORDER-RECURRENCE-PHI ";
1462  O << " = phi ";
1464 }
1465 #endif
1466 
1468  PHINode *PN = cast<PHINode>(getUnderlyingValue());
1469  auto &Builder = State.Builder;
1470 
1471  // In order to support recurrences we need to be able to vectorize Phi nodes.
1472  // Phi nodes have cycles, so we need to vectorize them in two stages. This is
1473  // stage #1: We create a new vector PHI node with no incoming edges. We'll use
1474  // this value when we vectorize all of the instructions that use the PHI.
1475  bool ScalarPHI = State.VF.isScalar() || IsInLoop;
1476  Type *VecTy =
1477  ScalarPHI ? PN->getType() : VectorType::get(PN->getType(), State.VF);
1478 
1479  BasicBlock *HeaderBB = State.CFG.PrevBB;
1480  assert(State.LI->getLoopFor(HeaderBB)->getHeader() == HeaderBB &&
1481  "recipe must be in the vector loop header");
1482  unsigned LastPartForNewPhi = isOrdered() ? 1 : State.UF;
1483  for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
1484  Value *EntryPart =
1485  PHINode::Create(VecTy, 2, "vec.phi", &*HeaderBB->getFirstInsertionPt());
1486  State.set(this, EntryPart, Part);
1487  }
1488 
1489  // Reductions do not have to start at zero. They can start with
1490  // any loop invariant values.
1491  VPValue *StartVPV = getStartValue();
1492  Value *StartV = StartVPV->getLiveInIRValue();
1493 
1494  Value *Iden = nullptr;
1495  RecurKind RK = RdxDesc.getRecurrenceKind();
1498  // MinMax reduction have the start value as their identify.
1499  if (ScalarPHI) {
1500  Iden = StartV;
1501  } else {
1503  Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
1504  StartV = Iden =
1505  Builder.CreateVectorSplat(State.VF, StartV, "minmax.ident");
1506  }
1507  } else {
1508  Iden = RdxDesc.getRecurrenceIdentity(RK, VecTy->getScalarType(),
1509  RdxDesc.getFastMathFlags());
1510 
1511  if (!ScalarPHI) {
1512  Iden = Builder.CreateVectorSplat(State.VF, Iden);
1514  Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
1515  Constant *Zero = Builder.getInt32(0);
1516  StartV = Builder.CreateInsertElement(Iden, StartV, Zero);
1517  }
1518  }
1519 
1520  for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
1521  Value *EntryPart = State.get(this, Part);
1522  // Make sure to add the reduction start value only to the
1523  // first unroll part.
1524  Value *StartVal = (Part == 0) ? StartV : Iden;
1525  cast<PHINode>(EntryPart)->addIncoming(StartVal, State.CFG.VectorPreHeader);
1526  }
1527 }
1528 
1529 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1531  VPSlotTracker &SlotTracker) const {
1532  O << Indent << "WIDEN-REDUCTION-PHI ";
1533 
1535  O << " = phi ";
1537 }
1538 #endif
1539 
1540 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
1541 
1543  for (unsigned J = 0; J < getNumUsers();) {
1544  VPUser *User = Users[J];
1545  unsigned NumUsers = getNumUsers();
1546  for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
1547  if (User->getOperand(I) == this)
1548  User->setOperand(I, New);
1549  // If a user got removed after updating the current user, the next user to
1550  // update will be moved to the current position, so we only need to
1551  // increment the index if the number of users did not change.
1552  if (NumUsers == getNumUsers())
1553  J++;
1554  }
1555 }
1556 
1557 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1559  if (const Value *UV = getUnderlyingValue()) {
1560  OS << "ir<";
1561  UV->printAsOperand(OS, false);
1562  OS << ">";
1563  return;
1564  }
1565 
1566  unsigned Slot = Tracker.getSlot(this);
1567  if (Slot == unsigned(-1))
1568  OS << "<badref>";
1569  else
1570  OS << "vp<%" << Tracker.getSlot(this) << ">";
1571 }
1572 
1575  Op->printAsOperand(O, SlotTracker);
1576  });
1577 }
1578 #endif
1579 
1580 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
1581  Old2NewTy &Old2New,
1582  InterleavedAccessInfo &IAI) {
1584  for (VPBlockBase *Base : RPOT) {
1585  visitBlock(Base, Old2New, IAI);
1586  }
1587 }
1588 
1589 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
1590  InterleavedAccessInfo &IAI) {
1591  if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
1592  for (VPRecipeBase &VPI : *VPBB) {
1593  if (isa<VPHeaderPHIRecipe>(&VPI))
1594  continue;
1595  assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
1596  auto *VPInst = cast<VPInstruction>(&VPI);
1597  auto *Inst = cast<Instruction>(VPInst->getUnderlyingValue());
1598  auto *IG = IAI.getInterleaveGroup(Inst);
1599  if (!IG)
1600  continue;
1601 
1602  auto NewIGIter = Old2New.find(IG);
1603  if (NewIGIter == Old2New.end())
1604  Old2New[IG] = new InterleaveGroup<VPInstruction>(
1605  IG->getFactor(), IG->isReverse(), IG->getAlign());
1606 
1607  if (Inst == IG->getInsertPos())
1608  Old2New[IG]->setInsertPos(VPInst);
1609 
1610  InterleaveGroupMap[VPInst] = Old2New[IG];
1611  InterleaveGroupMap[VPInst]->insertMember(
1612  VPInst, IG->getIndex(Inst),
1613  Align(IG->isReverse() ? (-1) * int(IG->getFactor())
1614  : IG->getFactor()));
1615  }
1616  } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1617  visitRegion(Region, Old2New, IAI);
1618  else
1619  llvm_unreachable("Unsupported kind of VPBlock.");
1620 }
1621 
1623  InterleavedAccessInfo &IAI) {
1624  Old2NewTy Old2New;
1625  visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI);
1626 }
1627 
1628 void VPSlotTracker::assignSlot(const VPValue *V) {
1629  assert(Slots.find(V) == Slots.end() && "VPValue already has a slot!");
1630  Slots[V] = NextSlot++;
1631 }
1632 
1633 void VPSlotTracker::assignSlots(const VPlan &Plan) {
1634 
1635  for (const VPValue *V : Plan.VPExternalDefs)
1636  assignSlot(V);
1637 
1638  assignSlot(&Plan.VectorTripCount);
1639  if (Plan.BackedgeTakenCount)
1640  assignSlot(Plan.BackedgeTakenCount);
1641 
1645  Plan.getEntry()));
1646  for (const VPBasicBlock *VPBB :
1647  VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
1648  for (const VPRecipeBase &Recipe : *VPBB)
1649  for (VPValue *Def : Recipe.definedValues())
1650  assignSlot(Def);
1651 }
llvm::VPBasicBlock::getRecipeList
RecipeListTy & getRecipeList()
Returns a reference to the list of recipes.
Definition: VPlan.h:1783
llvm::VPInstruction::getOpcode
unsigned getOpcode() const
Definition: VPlan.h:849
i
i
Definition: README.txt:29
llvm::VPRecipeBase::moveAfter
void moveAfter(VPRecipeBase *MovePos)
Unlink this recipe from its current VPBasicBlock and insert it into the VPBasicBlock that MovePos liv...
Definition: VPlan.cpp:628
llvm::VPReductionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1327
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:298
llvm::VPBlockBase::getPlan
VPlan * getPlan()
Definition: VPlan.cpp:135
llvm::BasicBlock::print
void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW=nullptr, bool ShouldPreserveUseListOrder=false, bool IsForDebug=false) const
Print the basic block to an output stream with an optional AssemblyAnnotationWriter.
Definition: AsmWriter.cpp:4477
llvm::VPBlendRecipe::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming values, taking into account that a single incoming value has no mask.
Definition: VPlan.h:1305
llvm::VPlan::execute
void execute(struct VPTransformState *State)
Generate the IR code for this VPlan.
Definition: VPlan.cpp:891
llvm::VPlanIngredient::print
void print(raw_ostream &O) const
Definition: VPlan.cpp:1199
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:507
llvm::VPBlendRecipe::getIncomingValue
VPValue * getIncomingValue(unsigned Idx) const
Return incoming value number Idx.
Definition: VPlan.h:1308
llvm::IRBuilderBase::SetInsertPoint
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Definition: IRBuilder.h:184
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::VPRecipeBase::getUnderlyingInstr
Instruction * getUnderlyingInstr()
Returns the underlying instruction, if the recipe is a VPValue or nullptr otherwise.
Definition: VPlan.h:727
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:238
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::VPTransformState::CFG
struct llvm::VPTransformState::CFGState CFG
llvm::VPRecipeBase::eraseFromParent
iplist< VPRecipeBase >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: VPlan.cpp:623
llvm::LoopBase::getExitBlock
BlockT * getExitBlock() const
If getExitBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:82
llvm::VPWidenCanonicalIVRecipe::execute
void execute(VPTransformState &State) override
Generate a canonical vector induction variable of the vector loop, with start = {<Part*VF,...
Definition: VPlan.cpp:1401
llvm::VPBlendRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1307
llvm::VPBlockBase::getEnclosingBlockWithPredecessors
VPBlockBase * getEnclosingBlockWithPredecessors()
Definition: VPlan.cpp:183
llvm::StringRef::rtrim
LLVM_NODISCARD StringRef rtrim(char Char) const
Return string with consecutive Char characters starting from the right removed.
Definition: StringRef.h:856
llvm::VPBlockBase::getName
const std::string & getName() const
Definition: VPlan.h:468
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::ElementCount
Definition: TypeSize.h:385
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::codeview::DebugSubsectionKind::Lines
@ Lines
llvm::VPBasicBlock
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:1736
T
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::getRuntimeVF
Value * getRuntimeVF(IRBuilder<> &B, Type *Ty, ElementCount VF)
Return the runtime value for VF.
Definition: LoopVectorize.cpp:1077
llvm::VPBlockBase::getExitBasicBlock
const VPBasicBlock * getExitBasicBlock() const
Definition: VPlan.cpp:161
llvm::VPlan::prepareToExecute
void prepareToExecute(Value *TripCount, Value *VectorTripCount, Value *CanonicalIVStartValue, VPTransformState &State)
Prepare the plan for execution, setting up the required live-in values.
Definition: VPlan.cpp:843
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:632
llvm::VPWidenIntOrFpInductionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1254
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:76
llvm::VPValue::getLiveInIRValue
Value * getLiveInIRValue()
Returns the underlying IR value, if this VPValue is defined outside the scope of VPlan.
Definition: VPlanValue.h:186
llvm::Type::getScalarType
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:308
llvm::VPlanPrinter::dump
LLVM_DUMP_METHOD void dump()
Definition: VPlan.cpp:1090
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1175
llvm::VPCanonicalIVPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1393
llvm::VPDef::getVPSingleValue
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
Definition: VPlanValue.h:368
llvm::VPTransformState::get
Value * get(VPValue *Def, unsigned Part)
Get the generated Value for a given VPValue and a given Part.
Definition: LoopVectorize.cpp:10126
llvm::VPRegionBlock::dropAllReferences
void dropAllReferences(VPValue *NewValue) override
Replace all operands of VPUsers in the block with NewValue and also replaces all uses of VPValues def...
Definition: VPlan.cpp:440
llvm::VPDef::print
virtual void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const =0
Each concrete VPDef prints itself.
llvm::DOT::EscapeString
std::string EscapeString(const std::string &Label)
Definition: GraphWriter.cpp:55
llvm::IRBuilderBase::setFastMathFlags
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
Definition: IRBuilder.h:305
ErrorHandling.h
llvm::VPLane::Kind::First
@ First
For First, Lane is the index into the first N elements of a fixed-vector <N x <ElTy>> or a scalable v...
llvm::VPLane::Kind::ScalableLast
@ ScalableLast
For ScalableLast, Lane is the offset from the start of the last N-element subvector in a scalable vec...
llvm::IRBuilder<>
llvm::VPInstruction::setFastMathFlags
void setFastMathFlags(FastMathFlags FMFNew)
Set the fast-math flags.
Definition: VPlan.cpp:833
llvm::VPTransformState::set
void set(VPValue *Def, Value *V, unsigned Part)
Set the generated Value for a given VPValue and a given Part.
Definition: VPlan.h:259
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::RecurrenceDescriptor::getOpcode
static unsigned getOpcode(RecurKind Kind)
Returns the opcode corresponding to the RecurrenceKind.
Definition: IVDescriptors.cpp:1003
llvm::interleaveComma
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
Definition: STLExtras.h:1873
llvm::VPBasicBlock::dropAllReferences
void dropAllReferences(VPValue *NewValue) override
Replace all operands of VPUsers in the block with NewValue and also replaces all uses of VPValues def...
Definition: VPlan.cpp:363
llvm::VPlan::getCanonicalIV
VPCanonicalIVPHIRecipe * getCanonicalIV()
Returns the canonical induction recipe of the vector loop.
Definition: VPlan.h:2399
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::VPWidenIntOrFpInductionRecipe::getTruncInst
TruncInst * getTruncInst()
Returns the first defined value as TruncInst, if it is one or nullptr otherwise.
Definition: VPlan.h:1066
llvm::VPLane::getAsRuntimeExpr
Value * getAsRuntimeExpr(IRBuilder<> &Builder, const ElementCount &VF) const
Returns an expression describing the lane index that can be used at runtime.
Definition: VPlan.cpp:63
llvm::VPValue::dump
void dump() const
Dump the value to stderr (for debugging).
Definition: VPlan.cpp:96
llvm::BasicBlock::getSingleSuccessor
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:298
llvm::VPBlockBase::getHierarchicalPredecessors
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:558
llvm::BasicBlock::splitBasicBlock
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:385
llvm::VPInstruction::CanonicalIVIncrementNUW
@ CanonicalIVIncrementNUW
Definition: VPlan.h:797
llvm::VPWidenMemoryInstructionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1368
llvm::VPValue::print
void print(raw_ostream &OS, VPSlotTracker &Tracker) const
Definition: VPlan.cpp:89
llvm::iplist_impl::remove
pointer remove(iterator &IT)
Definition: ilist.h:251
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:268
STLExtras.h
llvm::VPUser::operands
operand_range operands()
Definition: VPlanValue.h:282
llvm::BasicBlock::hasNPredecessors
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
Definition: BasicBlock.cpp:290
llvm::VPRegionBlock::getEntry
const VPBlockBase * getEntry() const
Definition: VPlan.h:1888
llvm::FastMathFlags
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:165
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:104
llvm::VPTransformState::hasScalarValue
bool hasScalarValue(VPValue *Def, VPIteration Instance)
Definition: VPlan.h:248
llvm::VPValue::VPValue
VPValue(const unsigned char SC, Value *UV=nullptr, VPDef *Def=nullptr)
Definition: VPlan.cpp:76
llvm::InterleaveGroup
The group of interleaved loads/stores sharing the same stride and close to each other.
Definition: VectorUtils.h:284
llvm::VPInstruction::FirstOrderRecurrenceSplice
@ FirstOrderRecurrenceSplice
Definition: VPlan.h:788
llvm::LinearPolySize::isScalable
bool isScalable() const
Returns whether the size is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:298
llvm::iplist
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:390
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DepthFirstIterator.h
llvm::VPBlockBase::setPredicate
void setPredicate(VPValue *Pred)
Set the block's predicate.
Definition: VPlan.cpp:209
llvm::iplist_impl::erase
iterator erase(iterator where)
Definition: ilist.h:267
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::VPWidenIntOrFpInductionRecipe::getInductionDescriptor
const InductionDescriptor & getInductionDescriptor() const
Returns the induction descriptor for the recipe.
Definition: VPlan.h:1074
llvm::VPDef
This class augments a recipe with a set of VPValues defined by the recipe.
Definition: VPlanValue.h:296
llvm::RecurKind
RecurKind
These are the kinds of recurrences that we support.
Definition: IVDescriptors.h:39
llvm::VPRecipeBase::mayWriteToMemory
bool mayWriteToMemory() const
Returns true if the recipe may write to memory.
Definition: VPlan.cpp:511
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
VPlanDominatorTree.h
llvm::VPTransformState::DataState::PerPartOutput
DenseMap< VPValue *, PerPartValuesTy > PerPartOutput
Definition: VPlan.h:222
llvm::ElementCount::isScalar
bool isScalar() const
Counting predicates.
Definition: TypeSize.h:395
llvm::VPPredInstPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1360
Instruction.h
llvm::VPTransformState
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:200
CommandLine.h
Printer
print alias Alias Set Printer
Definition: AliasSetTracker.cpp:762
llvm::VPBasicBlock::iterator
RecipeListTy::iterator iterator
Instruction iterators...
Definition: VPlan.h:1757
llvm::VPBlockBase
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:395
llvm::VPReplicateRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1345
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1592
llvm::VPInstruction
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:782
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:418
llvm::VPlan::print
void print(raw_ostream &O) const
Print this VPlan to O.
Definition: VPlan.cpp:1003
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::StringRef::split
LLVM_NODISCARD std::pair< StringRef, StringRef > split(char Separator) const
Split into two substrings around the first occurrence of a separator character.
Definition: StringRef.h:749
llvm::VPTransformState::LI
LoopInfo * LI
Hold a pointer to LoopInfo to register new basic blocks in the loop.
Definition: VPlan.h:334
llvm::User
Definition: User.h:44
llvm::RecurrenceDescriptor::isSelectCmpRecurrenceKind
static bool isSelectCmpRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is of the form select(cmp(),x,y) where one of (x,...
Definition: IVDescriptors.h:244
Twine.h
InstrTypes.h
llvm::VPBlockUtils::insertBlockAfter
static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBase NewBlock after BlockPtr.
Definition: VPlan.h:2500
getOpcode
static Optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:199
llvm::VPRecipeBase::moveBefore
void moveBefore(VPBasicBlock &BB, iplist< VPRecipeBase >::iterator I)
Unlink this recipe and insert into BB before I.
Definition: VPlan.cpp:633
llvm::ReplaceInstWithInst
void ReplaceInstWithInst(BasicBlock::InstListType &BIL, BasicBlock::iterator &BI, Instruction *I)
Replace the instruction specified by BI with the instruction specified by I.
Definition: BasicBlockUtils.cpp:479
llvm::createStepForVF
Value * createStepForVF(IRBuilder<> &B, Type *Ty, ElementCount VF, int64_t Step)
Return a value for Step multiplied by VF.
Definition: LoopVectorize.cpp:1069
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:226
llvm::BasicBlock::getFirstInsertionPt
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:253
llvm::VPBlockBase::getEnclosingBlockWithSuccessors
VPBlockBase * getEnclosingBlockWithSuccessors()
An Enclosing Block of a block B is any block containing B, including B itself.
Definition: VPlan.cpp:175
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::VPWidenCanonicalIVRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1421
llvm::Instruction::getOpcodeName
const char * getOpcodeName() const
Definition: Instruction.h:162
llvm::RecurrenceDescriptor::getRecurrenceIdentity
Value * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF) const
Returns identity corresponding to the RecurrenceKind.
Definition: IVDescriptors.cpp:952
llvm::VPTransformState::DataState::PerPartScalars
DenseMap< VPValue *, ScalarsPerPartValuesTy > PerPartScalars
Definition: VPlan.h:225
llvm::Instruction
Definition: Instruction.h:45
llvm::InterleavedAccessInfo
Drive the analysis of interleaved memory accesses in the loop.
Definition: VectorUtils.h:733
llvm::VPValue::replaceAllUsesWith
void replaceAllUsesWith(VPValue *New)
Definition: VPlan.cpp:1542
llvm::VPBlockBase::printSuccessors
void printSuccessors(raw_ostream &O, const Twine &Indent) const
Print the successors of this block to O, prefixing all lines with Indent.
Definition: VPlan.cpp:399
llvm::RecurrenceDescriptor::getRecurrenceKind
RecurKind getRecurrenceKind() const
Definition: IVDescriptors.h:200
llvm::VPRegionBlock::execute
void execute(struct VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPRegionBlock,...
Definition: VPlan.cpp:447
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::VPValue
Definition: VPlanValue.h:44
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:925
llvm::VPTransformState::CFGState::VPBBsToFix
SmallVector< VPBasicBlock *, 8 > VPBBsToFix
Vector of VPBasicBlocks whose terminator instruction needs to be fixed up at the end of vector code g...
Definition: VPlan.h:328
llvm::VPlan::addExternalDef
void addExternalDef(VPValue *VPVal)
Add VPVal to the pool of external definitions if it's not already in the pool.
Definition: VPlan.h:2315
llvm::VPBlockBase::successors
iterator_range< VPBlockBase ** > successors()
Definition: VPlan.h:505
llvm::VPlan::getName
const std::string & getName() const
Definition: VPlan.h:2309
llvm::DominatorTreeBase::changeImmediateDominator
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Definition: GenericDomTree.h:655
VPlan.h
llvm::VPBasicBlock::end
iterator end()
Definition: VPlan.h:1767
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::StringRef::str
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:245
IVDescriptors.h
llvm::VPUser::getNumOperands
unsigned getNumOperands() const
Definition: VPlanValue.h:256
Type.h
llvm::VPBasicBlock::empty
bool empty() const
Definition: VPlan.h:1776
llvm::VPRegionBlock
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1850
llvm::VPWidenMemoryInstructionRecipe::isStore
bool isStore() const
Returns true if this recipe is a store.
Definition: VPlan.h:1631
llvm::VPBlockBase::getPredecessors
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:507
CFG.h
LoopInfo.h
llvm::VPBlockBase::getCondBit
VPValue * getCondBit()
Definition: VPlan.cpp:191
EnableVPlanNativePath
cl::opt< bool > EnableVPlanNativePath
llvm::IRBuilderBase::FastMathFlagGuard
Definition: IRBuilder.h:389
BasicBlock.h
llvm::cl::opt< bool >
llvm::VPRecipeBase::removeFromParent
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
Definition: VPlan.cpp:617
llvm::VPBlockBase::getHierarchicalSuccessors
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:542
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:207
llvm::VPRecipeBase::mayHaveSideEffects
bool mayHaveSideEffects() const
Returns true if the recipe may have side-effects.
Definition: VPlan.cpp:573
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::VPValue::Def
VPDef * Def
Pointer to the VPDef that defines this VPValue.
Definition: VPlanValue.h:65
llvm::VPReductionRecipe::getCondOp
VPValue * getCondOp() const
The VPValue of the condition for the block.
Definition: VPlan.h:1436
llvm::VPSlotTracker::getSlot
unsigned getSlot(const VPValue *V) const
Definition: VPlanValue.h:431
llvm::VPBlockBase::getSingleHierarchicalSuccessor
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:548
llvm::VPBlockBase::getSingleHierarchicalPredecessor
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:564
llvm::VPTransformState::DT
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:337
llvm::RegionBase::getEntry
BlockT * getEntry() const
Get the entry BasicBlock of the Region.
Definition: RegionInfo.h:322
llvm::VPInstruction::execute
void execute(VPTransformState &State) override
Generate the instruction.
Definition: VPlan.cpp:764
llvm::VPReductionPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1530
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2807
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3148
llvm::VPTransformState::UF
unsigned UF
Definition: VPlan.h:209
llvm::DenseMap
Definition: DenseMap.h:714
llvm::VPInstruction::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the VPInstruction to O.
Definition: VPlan.cpp:778
llvm::VPValue::getNumUsers
unsigned getNumUsers() const
Definition: VPlanValue.h:133
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:970
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::VPIteration
VPIteration represents a single point in the iteration space of the output (vectorized and/or unrolle...
Definition: VPlan.h:183
llvm::succ_begin
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:99
llvm::VPBlockUtils::connectBlocks
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2538
llvm::VPHeaderPHIRecipe::getStartValue
VPValue * getStartValue()
Returns the start value of the phi, if one is set.
Definition: VPlan.h:1129
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:585
llvm::VPBlendRecipe::getMask
VPValue * getMask(unsigned Idx) const
Return mask number Idx.
Definition: VPlan.h:1311
llvm::VPTransformState::CFGState::PrevVPBB
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:305
llvm::VPWidenGEPRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1274
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:367
llvm::IRBuilderBase::CreateUnreachable
UnreachableInst * CreateUnreachable()
Definition: IRBuilder.h:1138
llvm::X86AS::SS
@ SS
Definition: X86.h:189
llvm::VPBasicBlock::VPBasicBlock
VPBasicBlock(const Twine &Name="", VPRecipeBase *Recipe=nullptr)
Definition: VPlan.h:1745
llvm::VPBlockUtils::disconnectBlocks
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2549
llvm::VPlan::getEntry
VPBlockBase * getEntry()
Definition: VPlan.h:2275
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::VPInstruction::ActiveLaneMask
@ ActiveLaneMask
Definition: VPlan.h:795
getPlanEntry
static T * getPlanEntry(T *Start)
Definition: VPlan.cpp:115
llvm::VPBasicBlock::execute
void execute(struct VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPBasicBlock,...
Definition: VPlan.cpp:297
llvm::IRBuilderBase::CreateExtractElement
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2299
llvm::VPInstruction::hasResult
bool hasResult() const
Definition: VPlan.h:873
llvm::Instruction::isBinaryOp
bool isBinaryOp() const
Definition: Instruction.h:165
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:138
llvm::VPUser::printOperands
void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const
Print the operands to O.
Definition: VPlan.cpp:1573
llvm::LinearPolySize::getKnownMinValue
ScalarTy getKnownMinValue() const
Returns the minimum value this size can represent.
Definition: TypeSize.h:296
llvm::VPWidenRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1246
llvm::ElementCount::isVector
bool isVector() const
One or more elements.
Definition: TypeSize.h:397
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::Value::printAsOperand
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:4654
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:140
llvm::VPWidenIntOrFpInductionRecipe::isCanonical
bool isCanonical() const
Returns true if the induction is canonical, i.e.
Definition: VPlan.cpp:1267
llvm::VPWidenCallRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1216
llvm::VPlanIngredient::V
const Value * V
Definition: VPlan.h:2467
llvm::VPReductionRecipe::getVecOp
VPValue * getVecOp() const
The VPValue of the vector value to be reduced.
Definition: VPlan.h:1434
llvm::Instruction::getFastMathFlags
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
Definition: Instruction.cpp:290
llvm::MergeBlockIntoPredecessor
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false)
Attempts to merge a block into its predecessor, if possible.
Definition: BasicBlockUtils.cpp:180
llvm::VPBlockBase::getSingleSuccessor
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:512
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::VPTransformState::CFGState::VectorPreHeader
BasicBlock * VectorPreHeader
The IR BasicBlock that is the preheader of the vector loop in the output IR.
Definition: VPlan.h:320
llvm::RecurrenceDescriptor::getFastMathFlags
FastMathFlags getFastMathFlags() const
Definition: IVDescriptors.h:204
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
llvm::VPRecipeBase::getParent
VPBasicBlock * getParent()
Definition: VPlan.h:692
llvm::IRBuilderBase::InsertPointGuard
Definition: IRBuilder.h:367
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
llvm::VPCanonicalIVPHIRecipe::execute
void execute(VPTransformState &State) override
Generate the canonical scalar induction phi of the vector loop.
Definition: VPlan.cpp:1382
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
llvm::VPBasicBlock::splitAt
VPBasicBlock * splitAt(iterator SplitAt)
Split current block at SplitAt by inserting a new block between the current block and its successors ...
Definition: VPlan.cpp:373
llvm::VPTransformState::VF
ElementCount VF
The chosen Vectorization and Unroll Factors of the loop being vectorized.
Definition: VPlan.h:208
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:152
llvm::VPBlockBase::getEntryBasicBlock
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:140
llvm::DominatorTreeBase::addNewBlock
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
Definition: GenericDomTree.h:619
llvm::VPTransformState::Data
struct llvm::VPTransformState::DataState Data
llvm::VPDef::getVPValue
VPValue * getVPValue(unsigned I)
Returns the VPValue with index I defined by the VPDef.
Definition: VPlanValue.h:380
llvm::VPFirstOrderRecurrencePHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1458
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:36
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:228
CFG
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to CFG
Definition: README.txt:39
llvm::VPTransformState::Builder
IRBuilder & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Definition: VPlan.h:340
llvm::VPBlockBase::setCondBit
void setCondBit(VPValue *CV)
Set the condition bit selecting the successor.
Definition: VPlan.cpp:199
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:162
llvm::VPReductionPHIRecipe::execute
void execute(VPTransformState &State) override
Generate the phi/select nodes.
Definition: VPlan.cpp:1467
llvm::VPDef::dump
void dump() const
Dump the VPDef to stderr (for debugging).
Definition: VPlan.cpp:104
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::VPInstruction::CanonicalIVIncrement
@ CanonicalIVIncrement
Definition: VPlan.h:796
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::VPSlotTracker
This class can be used to assign consecutive numbers to all VPValues in a VPlan and allows querying t...
Definition: VPlanValue.h:418
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:252
llvm::VPRegionBlock::getExit
const VPBlockBase * getExit() const
Definition: VPlan.h:1906
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
GraphWriter.h
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:35
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
llvm::PHINode::Create
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Definition: Instructions.h:2699
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::VPRecipeBase
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:673
llvm::AArch64CC::LS
@ LS
Definition: AArch64BaseInfo.h:264
Casting.h
llvm::VPRegionBlock::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print this VPRegionBlock to O (recursively), prefixing all lines with Indent.
Definition: VPlan.cpp:497
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::VPInstruction::ICmpULE
@ ICmpULE
Definition: VPlan.h:792
llvm::VPBlockBase::getPredicate
VPValue * getPredicate()
Definition: VPlan.cpp:201
llvm::DebugLoc::print
void print(raw_ostream &OS) const
prints source location /path/to/file.exe:line:col @[inlined at]
Definition: DebugLoc.cpp:104
llvm::SlotTracker
This class provides computation of slot numbers for LLVM Assembly writing.
Definition: AsmWriter.cpp:653
llvm::VPInstruction::SLPStore
@ SLPStore
Definition: VPlan.h:794
GenericDomTreeConstruction.h
llvm::VPTransformState::CFGState
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:303
llvm::VPInstruction::SLPLoad
@ SLPLoad
Definition: VPlan.h:793
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:290
llvm::iplist_impl::insertAfter
iterator insertAfter(iterator where, pointer New)
Definition: ilist.h:237
llvm::iplist_impl::insert
iterator insert(iterator where, pointer New)
Definition: ilist.h:228
llvm::VPUser
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:205
llvm::SmallBitVector::size
size_type size() const
Returns the number of bits in this bitvector.
Definition: SmallBitVector.h:194
llvm::VPBlockUser::getSingleOperandOrNull
VPValue * getSingleOperandOrNull()
Definition: VPlan.h:365
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:789
llvm::VPInstruction::BranchOnCount
@ BranchOnCount
Definition: VPlan.h:798
Instructions.h
PostOrderIterator.h
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
llvm::CallingConv::Tail
@ Tail
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
SmallVector.h
llvm::VPTransformState::VPValue2Value
VPValue2ValueTy VPValue2Value
Definition: VPlan.h:342
llvm::VPBasicBlock::begin
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:1765
llvm::LoopBase::addBasicBlockToLoop
void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)
This method is used by other analyses to update loop information.
Definition: LoopInfoImpl.h:242
llvm::VPUser::getOperand
VPValue * getOperand(unsigned N) const
Definition: VPlanValue.h:257
llvm::VPTransformState::Instance
Optional< VPIteration > Instance
Hold the indices to generate specific scalar instructions.
Definition: VPlan.h:214
llvm::VPRecipeBase::mayReadFromMemory
bool mayReadFromMemory() const
Returns true if the recipe may read from memory.
Definition: VPlan.cpp:542
llvm::VPlan::printDOT
void printDOT(raw_ostream &O) const
Print this VPlan in DOT format to O.
Definition: VPlan.cpp:1028
llvm::VPBasicBlock::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print this VPBsicBlock to O, prefixing all lines with Indent.
Definition: VPlan.cpp:411
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
llvm::VPTransformState::CFGState::LastBB
BasicBlock * LastBB
The last IR BasicBlock in the output IR.
Definition: VPlan.h:313
llvm::PHINode
Definition: Instructions.h:2657
llvm::VPInstruction::Not
@ Not
Definition: VPlan.h:791
llvm::VPFirstOrderRecurrencePHIRecipe::execute
void execute(VPTransformState &State) override
Generate the phi nodes.
Definition: VPlan.cpp:1430
llvm::VPTransformState::CFGState::VPBB2IRBB
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:324
llvm::VPLane
In what follows, the term "input IR" refers to code that is fed into the vectorizer whereas the term ...
Definition: VPlan.h:107
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:306
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4733
llvm::VPBlockBase::deleteCFG
static void deleteCFG(VPBlockBase *Entry)
Delete all blocks reachable from a given VPBlockBase, inclusive.
Definition: VPlan.cpp:213
llvm::VPRegionBlock::isReplicator
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:1920
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::VPWidenPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1288
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::Region
Definition: RegionInfo.h:889
llvm::VPBasicBlock::phis
iterator_range< iterator > phis()
Returns an iterator range over the PHI-like recipes in the block.
Definition: VPlan.h:1814
llvm::RecurrenceDescriptor::isMinMaxRecurrenceKind
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
Definition: IVDescriptors.h:238
llvm::VPValue::~VPValue
virtual ~VPValue()
Definition: VPlan.cpp:82
raw_ostream.h
llvm::VPBasicBlock::getFirstNonPhi
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
Definition: VPlan.cpp:220
llvm::VPReductionRecipe::getChainOp
VPValue * getChainOp() const
The VPValue of the scalar Chain being accumulated.
Definition: VPlan.h:1432
llvm::VPInterleavedAccessInfo::VPInterleavedAccessInfo
VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI)
Definition: VPlan.cpp:1622
llvm::VPBlockRecursiveTraversalWrapper
Helper for GraphTraits specialization that traverses through VPRegionBlocks.
Definition: VPlan.h:2142
llvm::VPBlockBase::getSuccessors
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:502
BasicBlockUtils.h
llvm::VPDef::getVPDefID
unsigned getVPDefID() const
Definition: VPlanValue.h:400
llvm::VPInstruction::dump
LLVM_DUMP_METHOD void dump() const
Print the VPInstruction to dbgs() (for debugging).
Definition: VPlan.cpp:773
llvm::SplitBlock
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
Definition: BasicBlockUtils.cpp:839
Value.h
llvm::pdb::PDB_SymType::Block
@ Block
llvm::RegionBase::getExit
BlockT * getExit() const
Get the exit BasicBlock of the Region.
Definition: RegionInfo.h:359
llvm::VPValue::getUnderlyingValue
Value * getUnderlyingValue()
Return the underlying Value attached to this VPValue.
Definition: VPlanValue.h:84
llvm::VPlan
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2198
llvm::VPBlockBase::setPlan
void setPlan(VPlan *ParentPlan)
Sets the pointer of the plan containing the block.
Definition: VPlan.cpp:154
llvm::MCID::Terminator
@ Terminator
Definition: MCInstrDesc.h:155
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::VPRecipeBase::insertBefore
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
Definition: VPlan.cpp:601
Debug.h
llvm::VectorType::get
static VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
Definition: Type.cpp:670
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::VPReductionPHIRecipe::isOrdered
bool isOrdered() const
Returns true, if the phi is part of an ordered reduction.
Definition: VPlan.h:1274
llvm::VPlan::dump
LLVM_DUMP_METHOD void dump() const
Dump the plan to stderr (for debugging).
Definition: VPlan.cpp:1034
llvm::VPlanIngredient
Definition: VPlan.h:2466
llvm::VPWidenSelectRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1233
llvm::VPValue::printAsOperand
void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const
Definition: VPlan.cpp:1558
llvm::VPWidenIntOrFpInductionRecipe::getStartValue
VPValue * getStartValue()
Returns the start value of the induction.
Definition: VPlan.h:1061
llvm::VPlanPrinter
VPlanPrinter prints a given VPlan to a given output stream.
Definition: VPlan.h:2419
llvm::VPTransformState::CFGState::PrevBB
BasicBlock * PrevBB
The previous IR BasicBlock created or used.
Definition: VPlan.h:309
llvm::VPRecipeBase::insertAfter
void insertAfter(VPRecipeBase *InsertPos)
Insert an unlinked Recipe into a basic block immediately after the specified Recipe.
Definition: VPlan.cpp:609
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::VPBlockUser::resetSingleOpUser
void resetSingleOpUser(VPValue *NewVal)
Definition: VPlan.h:378
llvm::VPTransformState::hasVectorValue
bool hasVectorValue(VPValue *Def, unsigned Part)
Definition: VPlan.h:238
llvm::InterleavedAccessInfo::getInterleaveGroup
InterleaveGroup< Instruction > * getInterleaveGroup(const Instruction *Instr) const
Get the interleave group that Instr belongs to.
Definition: VectorUtils.h:778
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1794