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  getSuccessors().end());
379  // First, disconnect the current block from its successors.
380  for (VPBlockBase *Succ : Succs)
381  VPBlockUtils::disconnectBlocks(this, Succ);
382 
383  // Create new empty block after the block to split.
384  auto *SplitBlock = new VPBasicBlock(getName() + ".split");
386 
387  // Add successors for block to split to new block.
388  for (VPBlockBase *Succ : Succs)
390 
391  // Finally, move the recipes starting at SplitAt to new block.
392  for (VPRecipeBase &ToMove :
393  make_early_inc_range(make_range(SplitAt, this->end())))
394  ToMove.moveBefore(*SplitBlock, SplitBlock->end());
395 
396  return SplitBlock;
397 }
398 
399 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
400 void VPBlockBase::printSuccessors(raw_ostream &O, const Twine &Indent) const {
401  if (getSuccessors().empty()) {
402  O << Indent << "No successors\n";
403  } else {
404  O << Indent << "Successor(s): ";
405  ListSeparator LS;
406  for (auto *Succ : getSuccessors())
407  O << LS << Succ->getName();
408  O << '\n';
409  }
410 }
411 
412 void VPBasicBlock::print(raw_ostream &O, const Twine &Indent,
413  VPSlotTracker &SlotTracker) const {
414  O << Indent << getName() << ":\n";
415  if (const VPValue *Pred = getPredicate()) {
416  O << Indent << "BlockPredicate:";
417  Pred->printAsOperand(O, SlotTracker);
418  if (const auto *PredInst = dyn_cast<VPInstruction>(Pred))
419  O << " (" << PredInst->getParent()->getName() << ")";
420  O << '\n';
421  }
422 
423  auto RecipeIndent = Indent + " ";
424  for (const VPRecipeBase &Recipe : *this) {
425  Recipe.print(O, RecipeIndent, SlotTracker);
426  O << '\n';
427  }
428 
429  printSuccessors(O, Indent);
430 
431  if (const VPValue *CBV = getCondBit()) {
432  O << Indent << "CondBit: ";
433  CBV->printAsOperand(O, SlotTracker);
434  if (const auto *CBI = dyn_cast<VPInstruction>(CBV))
435  O << " (" << CBI->getParent()->getName() << ")";
436  O << '\n';
437  }
438 }
439 #endif
440 
442  for (VPBlockBase *Block : depth_first(Entry))
443  // Drop all references in VPBasicBlocks and replace all uses with
444  // DummyValue.
445  Block->dropAllReferences(NewValue);
446 }
447 
450 
451  if (!isReplicator()) {
452  // Visit the VPBlocks connected to "this", starting from it.
453  for (VPBlockBase *Block : RPOT) {
454  if (EnableVPlanNativePath) {
455  // The inner loop vectorization path does not represent loop preheader
456  // and exit blocks as part of the VPlan. In the VPlan-native path, skip
457  // vectorizing loop preheader block. In future, we may replace this
458  // check with the check for loop preheader.
459  if (Block->getNumPredecessors() == 0)
460  continue;
461 
462  // Skip vectorizing loop exit block. In future, we may replace this
463  // check with the check for loop exit.
464  if (Block->getNumSuccessors() == 0)
465  continue;
466  }
467 
468  LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
469  Block->execute(State);
470  }
471  return;
472  }
473 
474  assert(!State->Instance && "Replicating a Region with non-null instance.");
475 
476  // Enter replicating mode.
477  State->Instance = VPIteration(0, 0);
478 
479  for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part) {
480  State->Instance->Part = Part;
481  assert(!State->VF.isScalable() && "VF is assumed to be non scalable.");
482  for (unsigned Lane = 0, VF = State->VF.getKnownMinValue(); Lane < VF;
483  ++Lane) {
484  State->Instance->Lane = VPLane(Lane, VPLane::Kind::First);
485  // Visit the VPBlocks connected to \p this, starting from it.
486  for (VPBlockBase *Block : RPOT) {
487  LLVM_DEBUG(dbgs() << "LV: VPBlock in RPO " << Block->getName() << '\n');
488  Block->execute(State);
489  }
490  }
491  }
492 
493  // Exit replicating mode.
494  State->Instance.reset();
495 }
496 
497 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
499  VPSlotTracker &SlotTracker) const {
500  O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {";
501  auto NewIndent = Indent + " ";
502  for (auto *BlockBase : depth_first(Entry)) {
503  O << '\n';
504  BlockBase->print(O, NewIndent, SlotTracker);
505  }
506  O << Indent << "}\n";
507 
508  printSuccessors(O, Indent);
509 }
510 #endif
511 
513  switch (getVPDefID()) {
514  case VPWidenMemoryInstructionSC: {
515  return cast<VPWidenMemoryInstructionRecipe>(this)->isStore();
516  }
517  case VPReplicateSC:
518  case VPWidenCallSC:
519  return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
520  ->mayWriteToMemory();
521  case VPBranchOnMaskSC:
522  return false;
523  case VPWidenIntOrFpInductionSC:
524  case VPWidenCanonicalIVSC:
525  case VPWidenPHISC:
526  case VPBlendSC:
527  case VPWidenSC:
528  case VPWidenGEPSC:
529  case VPReductionSC:
530  case VPWidenSelectSC: {
531  const Instruction *I =
532  dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
533  (void)I;
534  assert((!I || !I->mayWriteToMemory()) &&
535  "underlying instruction may write to memory");
536  return false;
537  }
538  default:
539  return true;
540  }
541 }
542 
544  switch (getVPDefID()) {
545  case VPWidenMemoryInstructionSC: {
546  return !cast<VPWidenMemoryInstructionRecipe>(this)->isStore();
547  }
548  case VPReplicateSC:
549  case VPWidenCallSC:
550  return cast<Instruction>(getVPSingleValue()->getUnderlyingValue())
551  ->mayReadFromMemory();
552  case VPBranchOnMaskSC:
553  return false;
554  case VPWidenIntOrFpInductionSC:
555  case VPWidenCanonicalIVSC:
556  case VPWidenPHISC:
557  case VPBlendSC:
558  case VPWidenSC:
559  case VPWidenGEPSC:
560  case VPReductionSC:
561  case VPWidenSelectSC: {
562  const Instruction *I =
563  dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
564  (void)I;
565  assert((!I || !I->mayReadFromMemory()) &&
566  "underlying instruction may read from memory");
567  return false;
568  }
569  default:
570  return true;
571  }
572 }
573 
575  switch (getVPDefID()) {
576  case VPBranchOnMaskSC:
577  return false;
578  case VPWidenIntOrFpInductionSC:
579  case VPWidenCanonicalIVSC:
580  case VPWidenPHISC:
581  case VPBlendSC:
582  case VPWidenSC:
583  case VPWidenGEPSC:
584  case VPReductionSC:
585  case VPWidenSelectSC: {
586  const Instruction *I =
587  dyn_cast_or_null<Instruction>(getVPSingleValue()->getUnderlyingValue());
588  (void)I;
589  assert((!I || !I->mayHaveSideEffects()) &&
590  "underlying instruction has side-effects");
591  return false;
592  }
593  case VPReplicateSC: {
594  auto *R = cast<VPReplicateRecipe>(this);
595  return R->getUnderlyingInstr()->mayHaveSideEffects();
596  }
597  default:
598  return true;
599  }
600 }
601 
603  assert(!Parent && "Recipe already in some VPBasicBlock");
604  assert(InsertPos->getParent() &&
605  "Insertion position not in any VPBasicBlock");
606  Parent = InsertPos->getParent();
607  Parent->getRecipeList().insert(InsertPos->getIterator(), this);
608 }
609 
611  assert(!Parent && "Recipe already in some VPBasicBlock");
612  assert(InsertPos->getParent() &&
613  "Insertion position not in any VPBasicBlock");
614  Parent = InsertPos->getParent();
615  Parent->getRecipeList().insertAfter(InsertPos->getIterator(), this);
616 }
617 
619  assert(getParent() && "Recipe not in any VPBasicBlock");
621  Parent = nullptr;
622 }
623 
625  assert(getParent() && "Recipe not in any VPBasicBlock");
626  return getParent()->getRecipeList().erase(getIterator());
627 }
628 
631  insertAfter(InsertPos);
632 }
633 
636  assert(I == BB.end() || I->getParent() == &BB);
638  Parent = &BB;
639  BB.getRecipeList().insert(I, this);
640 }
641 
642 void VPInstruction::generateInstruction(VPTransformState &State,
643  unsigned Part) {
644  IRBuilder<> &Builder = State.Builder;
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.TripCount;
681 
682  auto *Int1Ty = Type::getInt1Ty(Builder.getContext());
683  auto *PredTy = FixedVectorType::get(Int1Ty, State.VF.getKnownMinValue());
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  default:
715  llvm_unreachable("Unsupported opcode for instruction");
716  }
717 }
718 
720  assert(!State.Instance && "VPInstruction executing an Instance");
721  for (unsigned Part = 0; Part < State.UF; ++Part)
722  generateInstruction(State, Part);
723 }
724 
725 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
726 void VPInstruction::dump() const {
727  VPSlotTracker SlotTracker(getParent()->getPlan());
728  print(dbgs(), "", SlotTracker);
729 }
730 
732  VPSlotTracker &SlotTracker) const {
733  O << Indent << "EMIT ";
734 
735  if (hasResult()) {
737  O << " = ";
738  }
739 
740  switch (getOpcode()) {
741  case VPInstruction::Not:
742  O << "not";
743  break;
745  O << "icmp ule";
746  break;
748  O << "combined load";
749  break;
751  O << "combined store";
752  break;
754  O << "active lane mask";
755  break;
757  O << "first-order splice";
758  break;
759  default:
761  }
762 
763  for (const VPValue *Operand : operands()) {
764  O << " ";
765  Operand->printAsOperand(O, SlotTracker);
766  }
767 }
768 #endif
769 
770 /// Generate the code inside the body of the vectorized loop. Assumes a single
771 /// LoopVectorBody basic-block was created for this. Introduce additional
772 /// basic-blocks as needed, and fill them all.
774  // -1. Check if the backedge taken count is needed, and if so build it.
775  if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
776  Value *TC = State->TripCount;
778  auto *TCMO = Builder.CreateSub(TC, ConstantInt::get(TC->getType(), 1),
779  "trip.count.minus.1");
780  auto VF = State->VF;
781  Value *VTCMO =
782  VF.isScalar() ? TCMO : Builder.CreateVectorSplat(VF, TCMO, "broadcast");
783  for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part)
784  State->set(BackedgeTakenCount, VTCMO, Part);
785  }
786 
787  // 0. Set the reverse mapping from VPValues to Values for code generation.
788  for (auto &Entry : Value2VPValue)
789  State->VPValue2Value[Entry.second] = Entry.first;
790 
791  BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
792  State->CFG.VectorPreHeader = VectorPreHeaderBB;
793  BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
794  assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
795 
796  // 1. Make room to generate basic-blocks inside loop body if needed.
797  BasicBlock *VectorLatchBB = VectorHeaderBB->splitBasicBlock(
798  VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
799  Loop *L = State->LI->getLoopFor(VectorHeaderBB);
800  L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
801  // Remove the edge between Header and Latch to allow other connections.
802  // Temporarily terminate with unreachable until CFG is rewired.
803  // Note: this asserts the generated code's assumption that
804  // getFirstInsertionPt() can be dereferenced into an Instruction.
805  VectorHeaderBB->getTerminator()->eraseFromParent();
806  State->Builder.SetInsertPoint(VectorHeaderBB);
809 
810  // 2. Generate code in loop body.
811  State->CFG.PrevVPBB = nullptr;
812  State->CFG.PrevBB = VectorHeaderBB;
813  State->CFG.LastBB = VectorLatchBB;
814 
815  for (VPBlockBase *Block : depth_first(Entry))
816  Block->execute(State);
817 
818  // Fix the latch value of reduction and first-order recurrences phis in the
819  // vector loop.
820  VPBasicBlock *Header = Entry->getEntryBasicBlock();
821  for (VPRecipeBase &R : Header->phis()) {
822  auto *PhiR = dyn_cast<VPWidenPHIRecipe>(&R);
823  if (!PhiR || !(isa<VPFirstOrderRecurrencePHIRecipe>(&R) ||
824  isa<VPReductionPHIRecipe>(&R)))
825  continue;
826  // For first-order recurrences and in-order reduction phis, only a single
827  // part is generated, which provides the last part from the previous
828  // iteration. Otherwise all UF parts are generated.
829  bool SinglePartNeeded = isa<VPFirstOrderRecurrencePHIRecipe>(&R) ||
830  cast<VPReductionPHIRecipe>(&R)->isOrdered();
831  unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->UF;
832  for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
833  Value *VecPhi = State->get(PhiR, Part);
834  Value *Val = State->get(PhiR->getBackedgeValue(),
835  SinglePartNeeded ? State->UF - 1 : Part);
836  cast<PHINode>(VecPhi)->addIncoming(Val, VectorLatchBB);
837  }
838  }
839 
840  // Setup branch terminator successors for VPBBs in VPBBsToFix based on
841  // VPBB's successors.
842  for (auto VPBB : State->CFG.VPBBsToFix) {
844  "Unexpected VPBBsToFix in non VPlan-native path");
845  BasicBlock *BB = State->CFG.VPBB2IRBB[VPBB];
846  assert(BB && "Unexpected null basic block for VPBB");
847 
848  unsigned Idx = 0;
849  auto *BBTerminator = BB->getTerminator();
850 
851  for (VPBlockBase *SuccVPBlock : VPBB->getHierarchicalSuccessors()) {
852  VPBasicBlock *SuccVPBB = SuccVPBlock->getEntryBasicBlock();
853  BBTerminator->setSuccessor(Idx, State->CFG.VPBB2IRBB[SuccVPBB]);
854  ++Idx;
855  }
856  }
857 
858  // 3. Merge the temporary latch created with the last basic-block filled.
859  BasicBlock *LastBB = State->CFG.PrevBB;
860  // Connect LastBB to VectorLatchBB to facilitate their merge.
862  isa<UnreachableInst>(LastBB->getTerminator())) &&
863  "Expected InnerLoop VPlan CFG to terminate with unreachable");
864  assert((!EnableVPlanNativePath || isa<BranchInst>(LastBB->getTerminator())) &&
865  "Expected VPlan CFG to terminate with branch in NativePath");
866  LastBB->getTerminator()->eraseFromParent();
867  BranchInst::Create(VectorLatchBB, LastBB);
868 
869  // Merge LastBB with Latch.
870  bool Merged = MergeBlockIntoPredecessor(VectorLatchBB, nullptr, State->LI);
871  (void)Merged;
872  assert(Merged && "Could not merge last basic block with latch.");
873  VectorLatchBB = LastBB;
874 
875  // We do not attempt to preserve DT for outer loop vectorization currently.
877  updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB,
878  L->getExitBlock());
879 }
880 
881 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
883 void VPlan::print(raw_ostream &O) const {
885 
886  O << "VPlan '" << Name << "' {";
887  for (const VPBlockBase *Block : depth_first(getEntry())) {
888  O << '\n';
889  Block->print(O, "", SlotTracker);
890  }
891  O << "}\n";
892 }
893 
896  VPlanPrinter Printer(O, *this);
897  Printer.dump();
898 }
899 
901 void VPlan::dump() const { print(dbgs()); }
902 #endif
903 
904 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
905  BasicBlock *LoopLatchBB,
906  BasicBlock *LoopExitBB) {
907  BasicBlock *LoopHeaderBB = LoopPreHeaderBB->getSingleSuccessor();
908  assert(LoopHeaderBB && "Loop preheader does not have a single successor.");
909  // The vector body may be more than a single basic-block by this point.
910  // Update the dominator tree information inside the vector body by propagating
911  // it from header to latch, expecting only triangular control-flow, if any.
912  BasicBlock *PostDomSucc = nullptr;
913  for (auto *BB = LoopHeaderBB; BB != LoopLatchBB; BB = PostDomSucc) {
914  // Get the list of successors of this block.
915  std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
916  assert(Succs.size() <= 2 &&
917  "Basic block in vector loop has more than 2 successors.");
918  PostDomSucc = Succs[0];
919  if (Succs.size() == 1) {
920  assert(PostDomSucc->getSinglePredecessor() &&
921  "PostDom successor has more than one predecessor.");
922  DT->addNewBlock(PostDomSucc, BB);
923  continue;
924  }
925  BasicBlock *InterimSucc = Succs[1];
926  if (PostDomSucc->getSingleSuccessor() == InterimSucc) {
927  PostDomSucc = Succs[1];
928  InterimSucc = Succs[0];
929  }
930  assert(InterimSucc->getSingleSuccessor() == PostDomSucc &&
931  "One successor of a basic block does not lead to the other.");
932  assert(InterimSucc->getSinglePredecessor() &&
933  "Interim successor has more than one predecessor.");
934  assert(PostDomSucc->hasNPredecessors(2) &&
935  "PostDom successor has more than two predecessors.");
936  DT->addNewBlock(InterimSucc, BB);
937  DT->addNewBlock(PostDomSucc, BB);
938  }
939  // Latch block is a new dominator for the loop exit.
940  DT->changeImmediateDominator(LoopExitBB, LoopLatchBB);
942 }
943 
944 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
945 Twine VPlanPrinter::getUID(const VPBlockBase *Block) {
946  return (isa<VPRegionBlock>(Block) ? "cluster_N" : "N") +
947  Twine(getOrCreateBID(Block));
948 }
949 
950 Twine VPlanPrinter::getOrCreateName(const VPBlockBase *Block) {
951  const std::string &Name = Block->getName();
952  if (!Name.empty())
953  return Name;
954  return "VPB" + Twine(getOrCreateBID(Block));
955 }
956 
958  Depth = 1;
959  bumpIndent(0);
960  OS << "digraph VPlan {\n";
961  OS << "graph [labelloc=t, fontsize=30; label=\"Vectorization Plan";
962  if (!Plan.getName().empty())
963  OS << "\\n" << DOT::EscapeString(Plan.getName());
964  if (Plan.BackedgeTakenCount) {
965  OS << ", where:\\n";
966  Plan.BackedgeTakenCount->print(OS, SlotTracker);
967  OS << " := BackedgeTakenCount";
968  }
969  OS << "\"]\n";
970  OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
971  OS << "edge [fontname=Courier, fontsize=30]\n";
972  OS << "compound=true\n";
973 
974  for (const VPBlockBase *Block : depth_first(Plan.getEntry()))
975  dumpBlock(Block);
976 
977  OS << "}\n";
978 }
979 
980 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
981  if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
982  dumpBasicBlock(BasicBlock);
983  else if (const VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
984  dumpRegion(Region);
985  else
986  llvm_unreachable("Unsupported kind of VPBlock.");
987 }
988 
989 void VPlanPrinter::drawEdge(const VPBlockBase *From, const VPBlockBase *To,
990  bool Hidden, const Twine &Label) {
991  // Due to "dot" we print an edge between two regions as an edge between the
992  // exit basic block and the entry basic of the respective regions.
993  const VPBlockBase *Tail = From->getExitBasicBlock();
994  const VPBlockBase *Head = To->getEntryBasicBlock();
995  OS << Indent << getUID(Tail) << " -> " << getUID(Head);
996  OS << " [ label=\"" << Label << '\"';
997  if (Tail != From)
998  OS << " ltail=" << getUID(From);
999  if (Head != To)
1000  OS << " lhead=" << getUID(To);
1001  if (Hidden)
1002  OS << "; splines=none";
1003  OS << "]\n";
1004 }
1005 
1006 void VPlanPrinter::dumpEdges(const VPBlockBase *Block) {
1007  auto &Successors = Block->getSuccessors();
1008  if (Successors.size() == 1)
1009  drawEdge(Block, Successors.front(), false, "");
1010  else if (Successors.size() == 2) {
1011  drawEdge(Block, Successors.front(), false, "T");
1012  drawEdge(Block, Successors.back(), false, "F");
1013  } else {
1014  unsigned SuccessorNumber = 0;
1015  for (auto *Successor : Successors)
1016  drawEdge(Block, Successor, false, Twine(SuccessorNumber++));
1017  }
1018 }
1019 
1020 void VPlanPrinter::dumpBasicBlock(const VPBasicBlock *BasicBlock) {
1021  // Implement dot-formatted dump by performing plain-text dump into the
1022  // temporary storage followed by some post-processing.
1023  OS << Indent << getUID(BasicBlock) << " [label =\n";
1024  bumpIndent(1);
1025  std::string Str;
1026  raw_string_ostream SS(Str);
1027  // Use no indentation as we need to wrap the lines into quotes ourselves.
1028  BasicBlock->print(SS, "", SlotTracker);
1029 
1030  // We need to process each line of the output separately, so split
1031  // single-string plain-text dump.
1033  StringRef(Str).rtrim('\n').split(Lines, "\n");
1034 
1035  auto EmitLine = [&](StringRef Line, StringRef Suffix) {
1036  OS << Indent << '"' << DOT::EscapeString(Line.str()) << "\\l\"" << Suffix;
1037  };
1038 
1039  // Don't need the "+" after the last line.
1040  for (auto Line : make_range(Lines.begin(), Lines.end() - 1))
1041  EmitLine(Line, " +\n");
1042  EmitLine(Lines.back(), "\n");
1043 
1044  bumpIndent(-1);
1045  OS << Indent << "]\n";
1046 
1047  dumpEdges(BasicBlock);
1048 }
1049 
1050 void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
1051  OS << Indent << "subgraph " << getUID(Region) << " {\n";
1052  bumpIndent(1);
1053  OS << Indent << "fontname=Courier\n"
1054  << Indent << "label=\""
1055  << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
1056  << DOT::EscapeString(Region->getName()) << "\"\n";
1057  // Dump the blocks of the region.
1058  assert(Region->getEntry() && "Region contains no inner blocks.");
1059  for (const VPBlockBase *Block : depth_first(Region->getEntry()))
1060  dumpBlock(Block);
1061  bumpIndent(-1);
1062  OS << Indent << "}\n";
1063  dumpEdges(Region);
1064 }
1065 
1067  if (auto *Inst = dyn_cast<Instruction>(V)) {
1068  if (!Inst->getType()->isVoidTy()) {
1069  Inst->printAsOperand(O, false);
1070  O << " = ";
1071  }
1072  O << Inst->getOpcodeName() << " ";
1073  unsigned E = Inst->getNumOperands();
1074  if (E > 0) {
1075  Inst->getOperand(0)->printAsOperand(O, false);
1076  for (unsigned I = 1; I < E; ++I)
1077  Inst->getOperand(I)->printAsOperand(O << ", ", false);
1078  }
1079  } else // !Inst
1080  V->printAsOperand(O, false);
1081 }
1082 
1084  VPSlotTracker &SlotTracker) const {
1085  O << Indent << "WIDEN-CALL ";
1086 
1087  auto *CI = cast<CallInst>(getUnderlyingInstr());
1088  if (CI->getType()->isVoidTy())
1089  O << "void ";
1090  else {
1092  O << " = ";
1093  }
1094 
1095  O << "call @" << CI->getCalledFunction()->getName() << "(";
1097  O << ")";
1098 }
1099 
1101  VPSlotTracker &SlotTracker) const {
1102  O << Indent << "WIDEN-SELECT ";
1104  O << " = select ";
1106  O << ", ";
1108  O << ", ";
1110  O << (InvariantCond ? " (condition is loop invariant)" : "");
1111 }
1112 
1114  VPSlotTracker &SlotTracker) const {
1115  O << Indent << "WIDEN ";
1117  O << " = " << getUnderlyingInstr()->getOpcodeName() << " ";
1119 }
1120 
1122  VPSlotTracker &SlotTracker) const {
1123  O << Indent << "WIDEN-INDUCTION";
1124  if (getTruncInst()) {
1125  O << "\\l\"";
1126  O << " +\n" << Indent << "\" " << VPlanIngredient(IV) << "\\l\"";
1127  O << " +\n" << Indent << "\" ";
1129  } else
1130  O << " " << VPlanIngredient(IV);
1131 }
1132 
1134  VPSlotTracker &SlotTracker) const {
1135  O << Indent << "WIDEN-GEP ";
1136  O << (IsPtrLoopInvariant ? "Inv" : "Var");
1137  size_t IndicesNumber = IsIndexLoopInvariant.size();
1138  for (size_t I = 0; I < IndicesNumber; ++I)
1139  O << "[" << (IsIndexLoopInvariant[I] ? "Inv" : "Var") << "]";
1140 
1141  O << " ";
1143  O << " = getelementptr ";
1145 }
1146 
1148  VPSlotTracker &SlotTracker) const {
1149  O << Indent << "WIDEN-PHI ";
1150 
1151  auto *OriginalPhi = cast<PHINode>(getUnderlyingValue());
1152  // Unless all incoming values are modeled in VPlan print the original PHI
1153  // directly.
1154  // TODO: Remove once all VPWidenPHIRecipe instances keep all relevant incoming
1155  // values as VPValues.
1156  if (getNumOperands() != OriginalPhi->getNumOperands()) {
1157  O << VPlanIngredient(OriginalPhi);
1158  return;
1159  }
1160 
1162  O << " = phi ";
1164 }
1165 
1167  VPSlotTracker &SlotTracker) const {
1168  O << Indent << "BLEND ";
1169  Phi->printAsOperand(O, false);
1170  O << " =";
1171  if (getNumIncomingValues() == 1) {
1172  // Not a User of any mask: not really blending, this is a
1173  // single-predecessor phi.
1174  O << " ";
1176  } else {
1177  for (unsigned I = 0, E = getNumIncomingValues(); I < E; ++I) {
1178  O << " ";
1180  O << "/";
1182  }
1183  }
1184 }
1185 
1187  VPSlotTracker &SlotTracker) const {
1188  O << Indent << "REDUCE ";
1190  O << " = ";
1192  O << " + reduce." << Instruction::getOpcodeName(RdxDesc->getOpcode())
1193  << " (";
1195  if (getCondOp()) {
1196  O << ", ";
1198  }
1199  O << ")";
1200 }
1201 
1203  VPSlotTracker &SlotTracker) const {
1204  O << Indent << (IsUniform ? "CLONE " : "REPLICATE ");
1205 
1206  if (!getUnderlyingInstr()->getType()->isVoidTy()) {
1208  O << " = ";
1209  }
1212 
1213  if (AlsoPack)
1214  O << " (S->V)";
1215 }
1216 
1218  VPSlotTracker &SlotTracker) const {
1219  O << Indent << "PHI-PREDICATED-INSTRUCTION ";
1221  O << " = ";
1223 }
1224 
1226  VPSlotTracker &SlotTracker) const {
1227  O << Indent << "WIDEN ";
1228 
1229  if (!isStore()) {
1231  O << " = ";
1232  }
1233  O << Instruction::getOpcodeName(Ingredient.getOpcode()) << " ";
1234 
1236 }
1237 #endif
1238 
1240  Value *CanonicalIV = State.CanonicalIV;
1241  Type *STy = CanonicalIV->getType();
1243  ElementCount VF = State.VF;
1244  assert(!VF.isScalable() && "the code following assumes non scalables ECs");
1245  Value *VStart = VF.isScalar()
1246  ? CanonicalIV
1247  : Builder.CreateVectorSplat(VF.getKnownMinValue(),
1248  CanonicalIV, "broadcast");
1249  for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part) {
1251  for (unsigned Lane = 0; Lane < VF.getKnownMinValue(); ++Lane)
1252  Indices.push_back(
1253  ConstantInt::get(STy, Part * VF.getKnownMinValue() + Lane));
1254  // If VF == 1, there is only one iteration in the loop above, thus the
1255  // element pushed back into Indices is ConstantInt::get(STy, Part)
1256  Constant *VStep =
1257  VF.isScalar() ? Indices.back() : ConstantVector::get(Indices);
1258  // Add the consecutive indices to the vector value.
1259  Value *CanonicalVectorIV = Builder.CreateAdd(VStart, VStep, "vec.iv");
1260  State.set(getVPSingleValue(), CanonicalVectorIV, Part);
1261  }
1262 }
1263 
1264 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1266  VPSlotTracker &SlotTracker) const {
1267  O << Indent << "EMIT ";
1269  O << " = WIDEN-CANONICAL-INDUCTION";
1270 }
1271 #endif
1272 
1274  auto &Builder = State.Builder;
1275  // Create a vector from the initial value.
1276  auto *VectorInit = getStartValue()->getLiveInIRValue();
1277 
1278  Type *VecTy = State.VF.isScalar()
1279  ? VectorInit->getType()
1280  : VectorType::get(VectorInit->getType(), State.VF);
1281 
1282  if (State.VF.isVector()) {
1283  auto *IdxTy = Builder.getInt32Ty();
1284  auto *One = ConstantInt::get(IdxTy, 1);
1286  Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
1287  auto *RuntimeVF = getRuntimeVF(Builder, IdxTy, State.VF);
1288  auto *LastIdx = Builder.CreateSub(RuntimeVF, One);
1289  VectorInit = Builder.CreateInsertElement(
1290  PoisonValue::get(VecTy), VectorInit, LastIdx, "vector.recur.init");
1291  }
1292 
1293  // Create a phi node for the new recurrence.
1294  PHINode *EntryPart = PHINode::Create(
1295  VecTy, 2, "vector.recur", &*State.CFG.PrevBB->getFirstInsertionPt());
1296  EntryPart->addIncoming(VectorInit, State.CFG.VectorPreHeader);
1297  State.set(this, EntryPart, 0);
1298 }
1299 
1300 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1302  VPSlotTracker &SlotTracker) const {
1303  O << Indent << "FIRST-ORDER-RECURRENCE-PHI ";
1305  O << " = phi ";
1307 }
1308 #endif
1309 
1311  PHINode *PN = cast<PHINode>(getUnderlyingValue());
1312  auto &Builder = State.Builder;
1313 
1314  // In order to support recurrences we need to be able to vectorize Phi nodes.
1315  // Phi nodes have cycles, so we need to vectorize them in two stages. This is
1316  // stage #1: We create a new vector PHI node with no incoming edges. We'll use
1317  // this value when we vectorize all of the instructions that use the PHI.
1318  bool ScalarPHI = State.VF.isScalar() || IsInLoop;
1319  Type *VecTy =
1320  ScalarPHI ? PN->getType() : VectorType::get(PN->getType(), State.VF);
1321 
1322  BasicBlock *HeaderBB = State.CFG.PrevBB;
1323  assert(State.LI->getLoopFor(HeaderBB)->getHeader() == HeaderBB &&
1324  "recipe must be in the vector loop header");
1325  unsigned LastPartForNewPhi = isOrdered() ? 1 : State.UF;
1326  for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
1327  Value *EntryPart =
1328  PHINode::Create(VecTy, 2, "vec.phi", &*HeaderBB->getFirstInsertionPt());
1329  State.set(this, EntryPart, Part);
1330  }
1331 
1332  // Reductions do not have to start at zero. They can start with
1333  // any loop invariant values.
1334  VPValue *StartVPV = getStartValue();
1335  Value *StartV = StartVPV->getLiveInIRValue();
1336 
1337  Value *Iden = nullptr;
1338  RecurKind RK = RdxDesc.getRecurrenceKind();
1340  // MinMax reduction have the start value as their identify.
1341  if (ScalarPHI) {
1342  Iden = StartV;
1343  } else {
1345  Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
1346  StartV = Iden =
1347  Builder.CreateVectorSplat(State.VF, StartV, "minmax.ident");
1348  }
1349  } else {
1351  RK, VecTy->getScalarType(), RdxDesc.getFastMathFlags());
1352  Iden = IdenC;
1353 
1354  if (!ScalarPHI) {
1355  Iden = ConstantVector::getSplat(State.VF, IdenC);
1357  Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
1358  Constant *Zero = Builder.getInt32(0);
1359  StartV = Builder.CreateInsertElement(Iden, StartV, Zero);
1360  }
1361  }
1362 
1363  for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
1364  Value *EntryPart = State.get(this, Part);
1365  // Make sure to add the reduction start value only to the
1366  // first unroll part.
1367  Value *StartVal = (Part == 0) ? StartV : Iden;
1368  cast<PHINode>(EntryPart)->addIncoming(StartVal, State.CFG.VectorPreHeader);
1369  }
1370 }
1371 
1372 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1374  VPSlotTracker &SlotTracker) const {
1375  O << Indent << "WIDEN-REDUCTION-PHI ";
1376 
1378  O << " = phi ";
1380 }
1381 #endif
1382 
1383 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
1384 
1386  for (unsigned J = 0; J < getNumUsers();) {
1387  VPUser *User = Users[J];
1388  unsigned NumUsers = getNumUsers();
1389  for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
1390  if (User->getOperand(I) == this)
1391  User->setOperand(I, New);
1392  // If a user got removed after updating the current user, the next user to
1393  // update will be moved to the current position, so we only need to
1394  // increment the index if the number of users did not change.
1395  if (NumUsers == getNumUsers())
1396  J++;
1397  }
1398 }
1399 
1400 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1402  if (const Value *UV = getUnderlyingValue()) {
1403  OS << "ir<";
1404  UV->printAsOperand(OS, false);
1405  OS << ">";
1406  return;
1407  }
1408 
1409  unsigned Slot = Tracker.getSlot(this);
1410  if (Slot == unsigned(-1))
1411  OS << "<badref>";
1412  else
1413  OS << "vp<%" << Tracker.getSlot(this) << ">";
1414 }
1415 
1418  Op->printAsOperand(O, SlotTracker);
1419  });
1420 }
1421 #endif
1422 
1423 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
1424  Old2NewTy &Old2New,
1425  InterleavedAccessInfo &IAI) {
1427  for (VPBlockBase *Base : RPOT) {
1428  visitBlock(Base, Old2New, IAI);
1429  }
1430 }
1431 
1432 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
1433  InterleavedAccessInfo &IAI) {
1434  if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {
1435  for (VPRecipeBase &VPI : *VPBB) {
1436  if (isa<VPWidenPHIRecipe>(&VPI))
1437  continue;
1438  assert(isa<VPInstruction>(&VPI) && "Can only handle VPInstructions");
1439  auto *VPInst = cast<VPInstruction>(&VPI);
1440  auto *Inst = cast<Instruction>(VPInst->getUnderlyingValue());
1441  auto *IG = IAI.getInterleaveGroup(Inst);
1442  if (!IG)
1443  continue;
1444 
1445  auto NewIGIter = Old2New.find(IG);
1446  if (NewIGIter == Old2New.end())
1447  Old2New[IG] = new InterleaveGroup<VPInstruction>(
1448  IG->getFactor(), IG->isReverse(), IG->getAlign());
1449 
1450  if (Inst == IG->getInsertPos())
1451  Old2New[IG]->setInsertPos(VPInst);
1452 
1453  InterleaveGroupMap[VPInst] = Old2New[IG];
1454  InterleaveGroupMap[VPInst]->insertMember(
1455  VPInst, IG->getIndex(Inst),
1456  Align(IG->isReverse() ? (-1) * int(IG->getFactor())
1457  : IG->getFactor()));
1458  }
1459  } else if (VPRegionBlock *Region = dyn_cast<VPRegionBlock>(Block))
1460  visitRegion(Region, Old2New, IAI);
1461  else
1462  llvm_unreachable("Unsupported kind of VPBlock.");
1463 }
1464 
1466  InterleavedAccessInfo &IAI) {
1467  Old2NewTy Old2New;
1468  visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI);
1469 }
1470 
1471 void VPSlotTracker::assignSlot(const VPValue *V) {
1472  assert(Slots.find(V) == Slots.end() && "VPValue already has a slot!");
1473  Slots[V] = NextSlot++;
1474 }
1475 
1476 void VPSlotTracker::assignSlots(const VPlan &Plan) {
1477 
1478  for (const VPValue *V : Plan.VPExternalDefs)
1479  assignSlot(V);
1480 
1481  if (Plan.BackedgeTakenCount)
1482  assignSlot(Plan.BackedgeTakenCount);
1483 
1487  Plan.getEntry()));
1488  for (const VPBasicBlock *VPBB :
1489  VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
1490  for (const VPRecipeBase &Recipe : *VPBB)
1491  for (VPValue *Def : Recipe.definedValues())
1492  assignSlot(Def);
1493 }
llvm::VPBasicBlock::getRecipeList
RecipeListTy & getRecipeList()
Returns a reference to the list of recipes.
Definition: VPlan.h:1653
llvm::VPInstruction::getOpcode
unsigned getOpcode() const
Definition: VPlan.h:830
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:629
llvm::VPReductionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1186
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:4504
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:1245
llvm::VPlan::execute
void execute(struct VPTransformState *State)
Generate the IR code for this VPlan.
Definition: VPlan.cpp:773
llvm::VPlanIngredient::print
void print(raw_ostream &O) const
Definition: VPlan.cpp:1066
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:491
llvm::VPBlendRecipe::getIncomingValue
VPValue * getIncomingValue(unsigned Idx) const
Return incoming value number Idx.
Definition: VPlan.h:1248
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
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:718
llvm::VPInstruction::ActiveLaneMask
@ ActiveLaneMask
Definition: VPlan.h:786
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:200
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:624
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:1239
llvm::VPBlendRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1166
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:461
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::ElementCount
Definition: TypeSize.h:386
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:1606
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:1116
llvm::VPBlockBase::getExitBasicBlock
const VPBasicBlock * getExitBasicBlock() const
Definition: VPlan.cpp:161
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:625
llvm::VPWidenIntOrFpInductionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1121
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:77
llvm::VPValue::getLiveInIRValue
Value * getLiveInIRValue()
Returns the underlying IR value, if this VPValue is defined outside the scope of VPlan.
Definition: VPlanValue.h:184
llvm::Type::getScalarType
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:319
llvm::VPlanPrinter::dump
LLVM_DUMP_METHOD void dump()
Definition: VPlan.cpp:957
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::VPDef::getVPSingleValue
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
Definition: VPlanValue.h:360
llvm::VPTransformState::get
Value * get(VPValue *Def, unsigned Part)
Get the generated Value for a given VPValue and a given Part.
Definition: LoopVectorize.cpp:9939
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:441
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:51
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::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:253
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:880
llvm::interleaveComma
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
Definition: STLExtras.h:1832
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::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:1048
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:294
llvm::VPBlockBase::getHierarchicalPredecessors
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:549
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:381
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::VPWidenMemoryInstructionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1225
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:264
STLExtras.h
llvm::VPUser::operands
operand_range operands()
Definition: VPlanValue.h:275
llvm::BasicBlock::hasNPredecessors
bool hasNPredecessors(unsigned N) const
Return true if this block has exactly N predecessors.
Definition: BasicBlock.cpp:286
llvm::VPRegionBlock::getEntry
const VPBlockBase * getEntry() const
Definition: VPlan.h:1758
llvm::Sched::Fast
@ Fast
Definition: TargetLowering.h:105
llvm::VPTransformState::hasScalarValue
bool hasScalarValue(VPValue *Def, VPIteration Instance)
Definition: VPlan.h:242
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::LinearPolySize::isScalable
bool isScalable() const
Returns whether the size is scaled by a runtime quantity (vscale).
Definition: TypeSize.h:299
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::VPDef
This class augments a recipe with a set of VPValues defined by the recipe.
Definition: VPlanValue.h:289
llvm::RecurKind
RecurKind
These are the kinds of recurrences that we support.
Definition: IVDescriptors.h:38
llvm::VPRecipeBase::mayWriteToMemory
bool mayWriteToMemory() const
Returns true if the recipe may write to memory.
Definition: VPlan.cpp:512
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:216
llvm::ElementCount::isScalar
bool isScalar() const
Counting predicates.
Definition: TypeSize.h:396
llvm::VPPredInstPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1217
Instruction.h
llvm::VPTransformState
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:194
CommandLine.h
Printer
print alias Alias Set Printer
Definition: AliasSetTracker.cpp:762
llvm::VPBasicBlock::iterator
RecipeListTy::iterator iterator
Instruction iterators...
Definition: VPlan.h:1627
llvm::VPBlockBase
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:388
llvm::VPReplicateRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1202
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::VPInstruction
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:773
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:410
llvm::VPlan::print
void print(raw_ostream &O) const
Print this VPlan to O.
Definition: VPlan.cpp:883
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:328
llvm::User
Definition: User.h:44
Twine.h
InstrTypes.h
llvm::VPBlockUtils::insertBlockAfter
static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBase NewBlock after BlockPtr.
Definition: VPlan.h:2325
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:634
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:468
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:237
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:249
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:1265
llvm::Instruction::getOpcodeName
const char * getOpcodeName() const
Definition: Instruction.h:162
llvm::VPInstruction::FirstOrderRecurrenceSplice
@ FirstOrderRecurrenceSplice
Definition: VPlan.h:779
llvm::VPTransformState::DataState::PerPartScalars
DenseMap< VPValue *, ScalarsPerPartValuesTy > PerPartScalars
Definition: VPlan.h:219
llvm::Instruction
Definition: Instruction.h:45
llvm::InterleavedAccessInfo
Drive the analysis of interleaved memory accesses in the loop.
Definition: VectorUtils.h:727
llvm::VPValue::replaceAllUsesWith
void replaceAllUsesWith(VPValue *New)
Definition: VPlan.cpp:1385
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:400
llvm::RecurrenceDescriptor::getRecurrenceKind
RecurKind getRecurrenceKind() const
Definition: IVDescriptors.h:182
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:448
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::ConstantVector::getSplat
static Constant * getSplat(ElementCount EC, Constant *Elt)
Return a ConstantVector with the specified constant in each element.
Definition: Constants.cpp:1412
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:900
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:322
llvm::VPInstruction::SLPLoad
@ SLPLoad
Definition: VPlan.h:784
llvm::VPlan::getName
const std::string & getName() const
Definition: VPlan.h:2156
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:1637
llvm::FixedVectorType::get
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
Definition: Type.cpp:648
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::VPTransformState::TripCount
Value * TripCount
Hold the trip count of the scalar loop.
Definition: VPlan.h:342
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:249
Type.h
llvm::VPBasicBlock::empty
bool empty() const
Definition: VPlan.h:1646
llvm::VPRegionBlock
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1720
llvm::VPWidenMemoryInstructionRecipe::isStore
bool isStore() const
Returns true if this recipe is a store.
Definition: VPlan.h:1559
llvm::VPBlockBase::getPredecessors
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:498
CFG.h
LoopInfo.h
llvm::VPBlockBase::getCondBit
VPValue * getCondBit()
Definition: VPlan.cpp:191
EnableVPlanNativePath
cl::opt< bool > EnableVPlanNativePath
BasicBlock.h
llvm::cl::opt< bool >
llvm::VPTransformState::CanonicalIV
Value * CanonicalIV
Hold the canonical scalar IV of the vector loop (start=0, step=VF*UF).
Definition: VPlan.h:339
llvm::VPRecipeBase::removeFromParent
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
Definition: VPlan.cpp:618
llvm::VPBlockBase::getHierarchicalSuccessors
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:533
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:192
llvm::VPRecipeBase::mayHaveSideEffects
bool mayHaveSideEffects() const
Returns true if the recipe may have side-effects.
Definition: VPlan.cpp:574
llvm::VPInstruction::ICmpULE
@ ICmpULE
Definition: VPlan.h:783
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:1376
llvm::VPSlotTracker::getSlot
unsigned getSlot(const VPValue *V) const
Definition: VPlanValue.h:424
llvm::VPBlockBase::getSingleHierarchicalSuccessor
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:539
llvm::VPBlockBase::getSingleHierarchicalPredecessor
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:555
llvm::VPTransformState::DT
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:331
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:719
llvm::VPReductionPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1373
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2783
llvm::BranchInst::Create
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3124
llvm::VPTransformState::UF
unsigned UF
Definition: VPlan.h:203
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:731
llvm::VPValue::getNumUsers
unsigned getNumUsers() const
Definition: VPlanValue.h:132
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::VPIteration
VPIteration represents a single point in the iteration space of the output (vectorized and/or unrolle...
Definition: VPlan.h:177
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:2359
llvm::VPInstruction::SLPStore
@ SLPStore
Definition: VPlan.h:785
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:576
llvm::VPBlendRecipe::getMask
VPValue * getMask(unsigned Idx) const
Return mask number Idx.
Definition: VPlan.h:1251
llvm::VPTransformState::CFGState::PrevVPBB
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:299
llvm::VPWidenGEPRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1133
llvm::IRBuilderBase::CreateUnreachable
UnreachableInst * CreateUnreachable()
Definition: IRBuilder.h:1138
llvm::VPBasicBlock::VPBasicBlock
VPBasicBlock(const Twine &Name="", VPRecipeBase *Recipe=nullptr)
Definition: VPlan.h:1615
llvm::VPBlockUtils::disconnectBlocks
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2370
llvm::VPlan::getEntry
VPBlockBase * getEntry()
Definition: VPlan.h:2132
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:2442
llvm::VPInstruction::hasResult
bool hasResult() const
Definition: VPlan.h:854
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:1416
llvm::LinearPolySize::getKnownMinValue
ScalarTy getKnownMinValue() const
Returns the minimum value this size can represent.
Definition: TypeSize.h:297
llvm::VPWidenRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1113
llvm::ElementCount::isVector
bool isVector() const
One or more elements.
Definition: TypeSize.h:398
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:4675
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:141
llvm::VPWidenCallRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1083
llvm::RecurrenceDescriptor::getRecurrenceIdentity
static Constant * getRecurrenceIdentity(RecurKind K, Type *Tp, FastMathFlags FMF)
Returns identity corresponding to the RecurrenceKind.
Definition: IVDescriptors.cpp:834
llvm::VPlanIngredient::V
const Value * V
Definition: VPlan.h:2293
llvm::VPReductionRecipe::getVecOp
VPValue * getVecOp() const
The VPValue of the vector value to be reduced.
Definition: VPlan.h:1374
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:173
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:314
llvm::RecurrenceDescriptor::getFastMathFlags
FastMathFlags getFastMathFlags() const
Definition: IVDescriptors.h:186
llvm::CallingConv::Tail
@ Tail
Tail - This calling convention attemps to make calls as fast as possible while guaranteeing that tail...
Definition: CallingConv.h:81
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::X86AS::SS
@ SS
Definition: X86.h:189
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:683
llvm::IRBuilderBase::InsertPointGuard
Definition: IRBuilder.h:367
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
llvm::ConstantVector::get
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1369
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:202
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:148
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:372
llvm::VPFirstOrderRecurrencePHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1301
llvm::BasicBlock::getContext
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:229
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:334
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:1310
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::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:411
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:254
llvm::VPRegionBlock::getExit
const VPBlockBase * getExit() const
Definition: VPlan.h:1776
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
GraphWriter.h
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:35
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
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:2675
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:664
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:498
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::VPBlockBase::getPredicate
VPValue * getPredicate()
Definition: VPlan.cpp:201
llvm::SlotTracker
This class provides computation of slot numbers for LLVM Assembly writing.
Definition: AsmWriter.cpp:659
GenericDomTreeConstruction.h
llvm::VPTransformState::CFGState
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:297
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:198
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:358
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:785
Instructions.h
PostOrderIterator.h
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
SmallVector.h
llvm::VPTransformState::VPValue2Value
VPValue2ValueTy VPValue2Value
Definition: VPlan.h:336
llvm::VPBasicBlock::begin
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:1635
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::VPInstruction::Not
@ Not
Definition: VPlan.h:782
llvm::VPUser::getOperand
VPValue * getOperand(unsigned N) const
Definition: VPlanValue.h:250
llvm::VPTransformState::Instance
Optional< VPIteration > Instance
Hold the indices to generate specific scalar instructions.
Definition: VPlan.h:208
llvm::VPRecipeBase::mayReadFromMemory
bool mayReadFromMemory() const
Returns true if the recipe may read from memory.
Definition: VPlan.cpp:543
llvm::VPlan::printDOT
void printDOT(raw_ostream &O) const
Print this VPlan in DOT format to O.
Definition: VPlan.cpp:895
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:412
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:307
llvm::PHINode
Definition: Instructions.h:2633
llvm::VPFirstOrderRecurrencePHIRecipe::execute
void execute(VPTransformState &State) override
Generate the phi/select nodes.
Definition: VPlan.cpp:1273
llvm::VPTransformState::CFGState::VPBB2IRBB
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:318
llvm::VPLane
In what follows, the term "input IR" refers to code that is fed into the vectorizer whereas the term ...
Definition: VPlan.h:101
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
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:4715
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:1790
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:1147
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:1684
llvm::RecurrenceDescriptor::isMinMaxRecurrenceKind
static bool isMinMaxRecurrenceKind(RecurKind Kind)
Returns true if the recurrence kind is any min/max kind.
Definition: IVDescriptors.h:220
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:1372
llvm::VPInterleavedAccessInfo::VPInterleavedAccessInfo
VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI)
Definition: VPlan.cpp:1465
llvm::VPBlockRecursiveTraversalWrapper
Helper for GraphTraits specialization that traverses through VPRegionBlocks.
Definition: VPlan.h:2012
llvm::VPBlockBase::getSuccessors
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:495
BasicBlockUtils.h
llvm::VPDef::getVPDefID
unsigned getVPDefID() const
Definition: VPlanValue.h:392
llvm::VPInstruction::dump
LLVM_DUMP_METHOD void dump() const
Print the VPInstruction to dbgs() (for debugging).
Definition: VPlan.cpp:726
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:814
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::VPWidenPHIRecipe::getStartValue
VPValue * getStartValue()
Returns the start value of the phi, if it is a reduction or first-order recurrence.
Definition: VPlan.h:1108
llvm::VPlan
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2068
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:75
llvm::VPRecipeBase::insertBefore
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
Definition: VPlan.cpp:602
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:632
llvm::VPReductionPHIRecipe::isOrdered
bool isOrdered() const
Returns true, if the phi is part of an ordered reduction.
Definition: VPlan.h:1214
llvm::VPlan::dump
LLVM_DUMP_METHOD void dump() const
Dump the plan to stderr (for debugging).
Definition: VPlan.cpp:901
llvm::VPlanIngredient
Definition: VPlan.h:2292
llvm::VPWidenSelectRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1100
llvm::VPValue::printAsOperand
void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const
Definition: VPlan.cpp:1401
llvm::VPlanPrinter
VPlanPrinter prints a given VPlan to a given output stream.
Definition: VPlan.h:2245
llvm::VPTransformState::CFGState::PrevBB
BasicBlock * PrevBB
The previous IR BasicBlock created or used.
Definition: VPlan.h:303
llvm::VPRecipeBase::insertAfter
void insertAfter(VPRecipeBase *InsertPos)
Insert an unlinked Recipe into a basic block immediately after the specified Recipe.
Definition: VPlan.cpp:610
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::VPBlockUser::resetSingleOpUser
void resetSingleOpUser(VPValue *NewVal)
Definition: VPlan.h:371
llvm::VPTransformState::hasVectorValue
bool hasVectorValue(VPValue *Def, unsigned Part)
Definition: VPlan.h:232
llvm::InterleavedAccessInfo::getInterleaveGroup
InterleaveGroup< Instruction > * getInterleaveGroup(const Instruction *Instr) const
Get the interleave group that Instr belongs to.
Definition: VectorUtils.h:772
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1790