LLVM  15.0.0git
VPlan.h
Go to the documentation of this file.
1 //===- VPlan.h - Represent A Vectorizer Plan --------------------*- C++ -*-===//
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 file contains the declarations of the Vectorization Plan base classes:
11 /// 1. VPBasicBlock and VPRegionBlock that inherit from a common pure virtual
12 /// VPBlockBase, together implementing a Hierarchical CFG;
13 /// 2. Specializations of GraphTraits that allow VPBlockBase graphs to be
14 /// treated as proper graphs for generic algorithms;
15 /// 3. Pure virtual VPRecipeBase serving as the base class for recipes contained
16 /// within VPBasicBlocks;
17 /// 4. VPInstruction, a concrete Recipe and VPUser modeling a single planned
18 /// instruction;
19 /// 5. The VPlan class holding a candidate for vectorization;
20 /// 6. The VPlanPrinter class providing a way to print a plan in dot format;
21 /// These are documented in docs/VectorizationPlan.rst.
22 //
23 //===----------------------------------------------------------------------===//
24 
25 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
26 #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
27 
28 #include "VPlanValue.h"
29 #include "llvm/ADT/DenseMap.h"
31 #include "llvm/ADT/GraphTraits.h"
32 #include "llvm/ADT/MapVector.h"
33 #include "llvm/ADT/Optional.h"
35 #include "llvm/ADT/SmallPtrSet.h"
36 #include "llvm/ADT/SmallVector.h"
37 #include "llvm/ADT/Twine.h"
38 #include "llvm/ADT/ilist.h"
39 #include "llvm/ADT/ilist_node.h"
40 #include "llvm/Analysis/LoopInfo.h"
42 #include "llvm/IR/DebugLoc.h"
43 #include "llvm/IR/FMF.h"
44 #include <algorithm>
45 #include <cassert>
46 #include <cstddef>
47 #include <string>
48 
49 namespace llvm {
50 
51 class BasicBlock;
52 class DominatorTree;
53 class InductionDescriptor;
54 class InnerLoopVectorizer;
55 class IRBuilderBase;
56 class LoopInfo;
57 class raw_ostream;
58 class RecurrenceDescriptor;
59 class Value;
60 class VPBasicBlock;
61 class VPRegionBlock;
62 class VPlan;
63 class VPReplicateRecipe;
64 class VPlanSlp;
65 
66 /// Returns a calculation for the total number of elements for a given \p VF.
67 /// For fixed width vectors this value is a constant, whereas for scalable
68 /// vectors it is an expression determined at runtime.
69 Value *getRuntimeVF(IRBuilderBase &B, Type *Ty, ElementCount VF);
70 
71 /// Return a value for Step multiplied by VF.
72 Value *createStepForVF(IRBuilderBase &B, Type *Ty, ElementCount VF,
73  int64_t Step);
74 
75 /// A range of powers-of-2 vectorization factors with fixed start and
76 /// adjustable end. The range includes start and excludes end, e.g.,:
77 /// [1, 9) = {1, 2, 4, 8}
78 struct VFRange {
79  // A power of 2.
81 
82  // Need not be a power of 2. If End <= Start range is empty.
84 
85  bool isEmpty() const {
87  }
88 
90  : Start(Start), End(End) {
92  "Both Start and End should have the same scalable flag");
94  "Expected Start to be a power of 2");
95  }
96 };
97 
98 using VPlanPtr = std::unique_ptr<VPlan>;
99 
100 /// In what follows, the term "input IR" refers to code that is fed into the
101 /// vectorizer whereas the term "output IR" refers to code that is generated by
102 /// the vectorizer.
103 
104 /// VPLane provides a way to access lanes in both fixed width and scalable
105 /// vectors, where for the latter the lane index sometimes needs calculating
106 /// as a runtime expression.
107 class VPLane {
108 public:
109  /// Kind describes how to interpret Lane.
110  enum class Kind : uint8_t {
111  /// For First, Lane is the index into the first N elements of a
112  /// fixed-vector <N x <ElTy>> or a scalable vector <vscale x N x <ElTy>>.
113  First,
114  /// For ScalableLast, Lane is the offset from the start of the last
115  /// N-element subvector in a scalable vector <vscale x N x <ElTy>>. For
116  /// example, a Lane of 0 corresponds to lane `(vscale - 1) * N`, a Lane of
117  /// 1 corresponds to `((vscale - 1) * N) + 1`, etc.
119  };
120 
121 private:
122  /// in [0..VF)
123  unsigned Lane;
124 
125  /// Indicates how the Lane should be interpreted, as described above.
126  Kind LaneKind;
127 
128 public:
129  VPLane(unsigned Lane, Kind LaneKind) : Lane(Lane), LaneKind(LaneKind) {}
130 
132 
134  unsigned LaneOffset = VF.getKnownMinValue() - 1;
135  Kind LaneKind;
136  if (VF.isScalable())
137  // In this case 'LaneOffset' refers to the offset from the start of the
138  // last subvector with VF.getKnownMinValue() elements.
139  LaneKind = VPLane::Kind::ScalableLast;
140  else
141  LaneKind = VPLane::Kind::First;
142  return VPLane(LaneOffset, LaneKind);
143  }
144 
145  /// Returns a compile-time known value for the lane index and asserts if the
146  /// lane can only be calculated at runtime.
147  unsigned getKnownLane() const {
148  assert(LaneKind == Kind::First);
149  return Lane;
150  }
151 
152  /// Returns an expression describing the lane index that can be used at
153  /// runtime.
155 
156  /// Returns the Kind of lane offset.
157  Kind getKind() const { return LaneKind; }
158 
159  /// Returns true if this is the first lane of the whole vector.
160  bool isFirstLane() const { return Lane == 0 && LaneKind == Kind::First; }
161 
162  /// Maps the lane to a cache index based on \p VF.
163  unsigned mapToCacheIndex(const ElementCount &VF) const {
164  switch (LaneKind) {
166  assert(VF.isScalable() && Lane < VF.getKnownMinValue());
167  return VF.getKnownMinValue() + Lane;
168  default:
169  assert(Lane < VF.getKnownMinValue());
170  return Lane;
171  }
172  }
173 
174  /// Returns the maxmimum number of lanes that we are able to consider
175  /// caching for \p VF.
176  static unsigned getNumCachedLanes(const ElementCount &VF) {
177  return VF.getKnownMinValue() * (VF.isScalable() ? 2 : 1);
178  }
179 };
180 
181 /// VPIteration represents a single point in the iteration space of the output
182 /// (vectorized and/or unrolled) IR loop.
183 struct VPIteration {
184  /// in [0..UF)
185  unsigned Part;
186 
188 
189  VPIteration(unsigned Part, unsigned Lane,
191  : Part(Part), Lane(Lane, Kind) {}
192 
193  VPIteration(unsigned Part, const VPLane &Lane) : Part(Part), Lane(Lane) {}
194 
195  bool isFirstIteration() const { return Part == 0 && Lane.isFirstLane(); }
196 };
197 
198 /// VPTransformState holds information passed down when "executing" a VPlan,
199 /// needed for generating the output IR.
204  : VF(VF), UF(UF), LI(LI), DT(DT), Builder(Builder), ILV(ILV), Plan(Plan) {
205  }
206 
207  /// The chosen Vectorization and Unroll Factors of the loop being vectorized.
209  unsigned UF;
210 
211  /// Hold the indices to generate specific scalar instructions. Null indicates
212  /// that all instances are to be generated, using either scalar or vector
213  /// instructions.
215 
216  struct DataState {
217  /// A type for vectorized values in the new loop. Each value from the
218  /// original loop, when vectorized, is represented by UF vector values in
219  /// the new unrolled loop, where UF is the unroll factor.
221 
223 
226  } Data;
227 
228  /// Get the generated Value for a given VPValue and a given Part. Note that
229  /// as some Defs are still created by ILV and managed in its ValueMap, this
230  /// method will delegate the call to ILV in such cases in order to provide
231  /// callers a consistent API.
232  /// \see set.
233  Value *get(VPValue *Def, unsigned Part);
234 
235  /// Get the generated Value for a given VPValue and given Part and Lane.
237 
238  bool hasVectorValue(VPValue *Def, unsigned Part) {
239  auto I = Data.PerPartOutput.find(Def);
240  return I != Data.PerPartOutput.end() && Part < I->second.size() &&
241  I->second[Part];
242  }
243 
245  return Data.PerPartOutput.find(Def) != Data.PerPartOutput.end();
246  }
247 
249  auto I = Data.PerPartScalars.find(Def);
250  if (I == Data.PerPartScalars.end())
251  return false;
252  unsigned CacheIdx = Instance.Lane.mapToCacheIndex(VF);
253  return Instance.Part < I->second.size() &&
254  CacheIdx < I->second[Instance.Part].size() &&
255  I->second[Instance.Part][CacheIdx];
256  }
257 
258  /// Set the generated Value for a given VPValue and a given Part.
259  void set(VPValue *Def, Value *V, unsigned Part) {
260  if (!Data.PerPartOutput.count(Def)) {
262  Data.PerPartOutput[Def] = Entry;
263  }
264  Data.PerPartOutput[Def][Part] = V;
265  }
266  /// Reset an existing vector value for \p Def and a given \p Part.
267  void reset(VPValue *Def, Value *V, unsigned Part) {
268  auto Iter = Data.PerPartOutput.find(Def);
269  assert(Iter != Data.PerPartOutput.end() &&
270  "need to overwrite existing value");
271  Iter->second[Part] = V;
272  }
273 
274  /// Set the generated scalar \p V for \p Def and the given \p Instance.
275  void set(VPValue *Def, Value *V, const VPIteration &Instance) {
276  auto Iter = Data.PerPartScalars.insert({Def, {}});
277  auto &PerPartVec = Iter.first->second;
278  while (PerPartVec.size() <= Instance.Part)
279  PerPartVec.emplace_back();
280  auto &Scalars = PerPartVec[Instance.Part];
281  unsigned CacheIdx = Instance.Lane.mapToCacheIndex(VF);
282  while (Scalars.size() <= CacheIdx)
283  Scalars.push_back(nullptr);
284  assert(!Scalars[CacheIdx] && "should overwrite existing value");
285  Scalars[CacheIdx] = V;
286  }
287 
288  /// Reset an existing scalar value for \p Def and a given \p Instance.
289  void reset(VPValue *Def, Value *V, const VPIteration &Instance) {
290  auto Iter = Data.PerPartScalars.find(Def);
291  assert(Iter != Data.PerPartScalars.end() &&
292  "need to overwrite existing value");
293  assert(Instance.Part < Iter->second.size() &&
294  "need to overwrite existing value");
295  unsigned CacheIdx = Instance.Lane.mapToCacheIndex(VF);
296  assert(CacheIdx < Iter->second[Instance.Part].size() &&
297  "need to overwrite existing value");
298  Iter->second[Instance.Part][CacheIdx] = V;
299  }
300 
301  /// Hold state information used when constructing the CFG of the output IR,
302  /// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks.
303  struct CFGState {
304  /// The previous VPBasicBlock visited. Initially set to null.
305  VPBasicBlock *PrevVPBB = nullptr;
306 
307  /// The previous IR BasicBlock created or used. Initially set to the new
308  /// header BasicBlock.
309  BasicBlock *PrevBB = nullptr;
310 
311  /// The last IR BasicBlock in the output IR. Set to the exit block of the
312  /// vector loop.
313  BasicBlock *ExitBB = nullptr;
314 
315  /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case
316  /// of replication, maps the BasicBlock of the last replica created.
318 
319  CFGState() = default;
320 
321  /// Returns the BasicBlock* mapped to the pre-header of the loop region
322  /// containing \p R.
324  } CFG;
325 
326  /// Hold a pointer to LoopInfo to register new basic blocks in the loop.
328 
329  /// Hold a pointer to Dominator Tree to register new basic blocks in the loop.
331 
332  /// Hold a reference to the IRBuilder used to generate output IR code.
334 
336 
337  /// Hold the canonical scalar IV of the vector loop (start=0, step=VF*UF).
338  Value *CanonicalIV = nullptr;
339 
340  /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
342 
343  /// Pointer to the VPlan code is generated for.
345 
346  /// Holds recipes that may generate a poison value that is used after
347  /// vectorization, even when their operands are not poison.
349 
350  /// The loop object for the current parent region, or nullptr.
352 };
353 
354 /// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
355 /// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.
356 class VPBlockBase {
357  friend class VPBlockUtils;
358 
359  const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
360 
361  /// An optional name for the block.
362  std::string Name;
363 
364  /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if
365  /// it is a topmost VPBlockBase.
366  VPRegionBlock *Parent = nullptr;
367 
368  /// List of predecessor blocks.
369  SmallVector<VPBlockBase *, 1> Predecessors;
370 
371  /// List of successor blocks.
373 
374  /// VPlan containing the block. Can only be set on the entry block of the
375  /// plan.
376  VPlan *Plan = nullptr;
377 
378  /// Add \p Successor as the last successor to this block.
379  void appendSuccessor(VPBlockBase *Successor) {
380  assert(Successor && "Cannot add nullptr successor!");
381  Successors.push_back(Successor);
382  }
383 
384  /// Add \p Predecessor as the last predecessor to this block.
385  void appendPredecessor(VPBlockBase *Predecessor) {
386  assert(Predecessor && "Cannot add nullptr predecessor!");
387  Predecessors.push_back(Predecessor);
388  }
389 
390  /// Remove \p Predecessor from the predecessors of this block.
391  void removePredecessor(VPBlockBase *Predecessor) {
392  auto Pos = find(Predecessors, Predecessor);
393  assert(Pos && "Predecessor does not exist");
394  Predecessors.erase(Pos);
395  }
396 
397  /// Remove \p Successor from the successors of this block.
398  void removeSuccessor(VPBlockBase *Successor) {
399  auto Pos = find(Successors, Successor);
400  assert(Pos && "Successor does not exist");
401  Successors.erase(Pos);
402  }
403 
404 protected:
405  VPBlockBase(const unsigned char SC, const std::string &N)
406  : SubclassID(SC), Name(N) {}
407 
408 public:
409  /// An enumeration for keeping track of the concrete subclass of VPBlockBase
410  /// that are actually instantiated. Values of this enumeration are kept in the
411  /// SubclassID field of the VPBlockBase objects. They are used for concrete
412  /// type identification.
413  using VPBlockTy = enum { VPBasicBlockSC, VPRegionBlockSC };
414 
416 
417  virtual ~VPBlockBase() = default;
418 
419  const std::string &getName() const { return Name; }
420 
421  void setName(const Twine &newName) { Name = newName.str(); }
422 
423  /// \return an ID for the concrete type of this object.
424  /// This is used to implement the classof checks. This should not be used
425  /// for any other purpose, as the values may change as LLVM evolves.
426  unsigned getVPBlockID() const { return SubclassID; }
427 
428  VPRegionBlock *getParent() { return Parent; }
429  const VPRegionBlock *getParent() const { return Parent; }
430 
431  /// \return A pointer to the plan containing the current block.
432  VPlan *getPlan();
433  const VPlan *getPlan() const;
434 
435  /// Sets the pointer of the plan containing the block. The block must be the
436  /// entry block into the VPlan.
437  void setPlan(VPlan *ParentPlan);
438 
439  void setParent(VPRegionBlock *P) { Parent = P; }
440 
441  /// \return the VPBasicBlock that is the entry of this VPBlockBase,
442  /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
443  /// VPBlockBase is a VPBasicBlock, it is returned.
444  const VPBasicBlock *getEntryBasicBlock() const;
446 
447  /// \return the VPBasicBlock that is the exiting this VPBlockBase,
448  /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
449  /// VPBlockBase is a VPBasicBlock, it is returned.
450  const VPBasicBlock *getExitingBasicBlock() const;
452 
453  const VPBlocksTy &getSuccessors() const { return Successors; }
454  VPBlocksTy &getSuccessors() { return Successors; }
455 
457 
458  const VPBlocksTy &getPredecessors() const { return Predecessors; }
459  VPBlocksTy &getPredecessors() { return Predecessors; }
460 
461  /// \return the successor of this VPBlockBase if it has a single successor.
462  /// Otherwise return a null pointer.
464  return (Successors.size() == 1 ? *Successors.begin() : nullptr);
465  }
466 
467  /// \return the predecessor of this VPBlockBase if it has a single
468  /// predecessor. Otherwise return a null pointer.
470  return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr);
471  }
472 
473  size_t getNumSuccessors() const { return Successors.size(); }
474  size_t getNumPredecessors() const { return Predecessors.size(); }
475 
476  /// An Enclosing Block of a block B is any block containing B, including B
477  /// itself. \return the closest enclosing block starting from "this", which
478  /// has successors. \return the root enclosing block if all enclosing blocks
479  /// have no successors.
481 
482  /// \return the closest enclosing block starting from "this", which has
483  /// predecessors. \return the root enclosing block if all enclosing blocks
484  /// have no predecessors.
486 
487  /// \return the successors either attached directly to this VPBlockBase or, if
488  /// this VPBlockBase is the exit block of a VPRegionBlock and has no
489  /// successors of its own, search recursively for the first enclosing
490  /// VPRegionBlock that has successors and return them. If no such
491  /// VPRegionBlock exists, return the (empty) successors of the topmost
492  /// VPBlockBase reached.
495  }
496 
497  /// \return the hierarchical successor of this VPBlockBase if it has a single
498  /// hierarchical successor. Otherwise return a null pointer.
501  }
502 
503  /// \return the predecessors either attached directly to this VPBlockBase or,
504  /// if this VPBlockBase is the entry block of a VPRegionBlock and has no
505  /// predecessors of its own, search recursively for the first enclosing
506  /// VPRegionBlock that has predecessors and return them. If no such
507  /// VPRegionBlock exists, return the (empty) predecessors of the topmost
508  /// VPBlockBase reached.
511  }
512 
513  /// \return the hierarchical predecessor of this VPBlockBase if it has a
514  /// single hierarchical predecessor. Otherwise return a null pointer.
517  }
518 
519  /// Set a given VPBlockBase \p Successor as the single successor of this
520  /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor.
521  /// This VPBlockBase must have no successors.
523  assert(Successors.empty() && "Setting one successor when others exist.");
524  appendSuccessor(Successor);
525  }
526 
527  /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two
528  /// successors of this VPBlockBase. This VPBlockBase is not added as
529  /// predecessor of \p IfTrue or \p IfFalse. This VPBlockBase must have no
530  /// successors.
531  void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse) {
532  assert(Successors.empty() && "Setting two successors when others exist.");
533  appendSuccessor(IfTrue);
534  appendSuccessor(IfFalse);
535  }
536 
537  /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase.
538  /// This VPBlockBase must have no predecessors. This VPBlockBase is not added
539  /// as successor of any VPBasicBlock in \p NewPreds.
541  assert(Predecessors.empty() && "Block predecessors already set.");
542  for (auto *Pred : NewPreds)
543  appendPredecessor(Pred);
544  }
545 
546  /// Remove all the predecessor of this block.
547  void clearPredecessors() { Predecessors.clear(); }
548 
549  /// Remove all the successors of this block.
550  void clearSuccessors() { Successors.clear(); }
551 
552  /// The method which generates the output IR that correspond to this
553  /// VPBlockBase, thereby "executing" the VPlan.
554  virtual void execute(struct VPTransformState *State) = 0;
555 
556  /// Delete all blocks reachable from a given VPBlockBase, inclusive.
557  static void deleteCFG(VPBlockBase *Entry);
558 
559  /// Return true if it is legal to hoist instructions into this block.
561  // There are currently no constraints that prevent an instruction to be
562  // hoisted into a VPBlockBase.
563  return true;
564  }
565 
566  /// Replace all operands of VPUsers in the block with \p NewValue and also
567  /// replaces all uses of VPValues defined in the block with NewValue.
568  virtual void dropAllReferences(VPValue *NewValue) = 0;
569 
570 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
571  void printAsOperand(raw_ostream &OS, bool PrintType) const {
572  OS << getName();
573  }
574 
575  /// Print plain-text dump of this VPBlockBase to \p O, prefixing all lines
576  /// with \p Indent. \p SlotTracker is used to print unnamed VPValue's using
577  /// consequtive numbers.
578  ///
579  /// Note that the numbering is applied to the whole VPlan, so printing
580  /// individual blocks is consistent with the whole VPlan printing.
581  virtual void print(raw_ostream &O, const Twine &Indent,
582  VPSlotTracker &SlotTracker) const = 0;
583 
584  /// Print plain-text dump of this VPlan to \p O.
585  void print(raw_ostream &O) const {
587  print(O, "", SlotTracker);
588  }
589 
590  /// Print the successors of this block to \p O, prefixing all lines with \p
591  /// Indent.
592  void printSuccessors(raw_ostream &O, const Twine &Indent) const;
593 
594  /// Dump this VPBlockBase to dbgs().
595  LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
596 #endif
597 };
598 
599 /// A value that is used outside the VPlan. The operand of the user needs to be
600 /// added to the associated LCSSA phi node.
601 class VPLiveOut : public VPUser {
602  PHINode *Phi;
603 
604 public:
606  : VPUser({Op}, VPUser::VPUserID::LiveOut), Phi(Phi) {}
607 
608  /// Fixup the wrapped LCSSA phi node in the unique exit block. This simply
609  /// means we need to add the appropriate incoming value from the middle
610  /// block as exiting edges from the scalar epilogue loop (if present) are
611  /// already in place, and we exit the vector loop exclusively to the middle
612  /// block.
613  void fixPhi(VPlan &Plan, VPTransformState &State);
614 
615  /// Returns true if the VPLiveOut uses scalars of operand \p Op.
616  bool usesScalars(const VPValue *Op) const override {
618  "Op must be an operand of the recipe");
619  return true;
620  }
621 
622  PHINode *getPhi() const { return Phi; }
623 };
624 
625 /// VPRecipeBase is a base class modeling a sequence of one or more output IR
626 /// instructions. VPRecipeBase owns the the VPValues it defines through VPDef
627 /// and is responsible for deleting its defined values. Single-value
628 /// VPRecipeBases that also inherit from VPValue must make sure to inherit from
629 /// VPRecipeBase before VPValue.
630 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock>,
631  public VPDef,
632  public VPUser {
633  friend VPBasicBlock;
634  friend class VPBlockUtils;
635 
636  /// Each VPRecipe belongs to a single VPBasicBlock.
637  VPBasicBlock *Parent = nullptr;
638 
639 public:
641  : VPDef(SC), VPUser(Operands, VPUser::VPUserID::Recipe) {}
642 
643  template <typename IterT>
645  : VPDef(SC), VPUser(Operands, VPUser::VPUserID::Recipe) {}
646  virtual ~VPRecipeBase() = default;
647 
648  /// \return the VPBasicBlock which this VPRecipe belongs to.
649  VPBasicBlock *getParent() { return Parent; }
650  const VPBasicBlock *getParent() const { return Parent; }
651 
652  /// The method which generates the output IR instructions that correspond to
653  /// this VPRecipe, thereby "executing" the VPlan.
654  virtual void execute(struct VPTransformState &State) = 0;
655 
656  /// Insert an unlinked recipe into a basic block immediately before
657  /// the specified recipe.
658  void insertBefore(VPRecipeBase *InsertPos);
659  /// Insert an unlinked recipe into \p BB immediately before the insertion
660  /// point \p IP;
662 
663  /// Insert an unlinked Recipe into a basic block immediately after
664  /// the specified Recipe.
665  void insertAfter(VPRecipeBase *InsertPos);
666 
667  /// Unlink this recipe from its current VPBasicBlock and insert it into
668  /// the VPBasicBlock that MovePos lives in, right after MovePos.
669  void moveAfter(VPRecipeBase *MovePos);
670 
671  /// Unlink this recipe and insert into BB before I.
672  ///
673  /// \pre I is a valid iterator into BB.
675 
676  /// This method unlinks 'this' from the containing basic block, but does not
677  /// delete it.
678  void removeFromParent();
679 
680  /// This method unlinks 'this' from the containing basic block and deletes it.
681  ///
682  /// \returns an iterator pointing to the element after the erased one
684 
685  /// Returns the underlying instruction, if the recipe is a VPValue or nullptr
686  /// otherwise.
688  return cast<Instruction>(getVPSingleValue()->getUnderlyingValue());
689  }
691  return cast<Instruction>(getVPSingleValue()->getUnderlyingValue());
692  }
693 
694  /// Method to support type inquiry through isa, cast, and dyn_cast.
695  static inline bool classof(const VPDef *D) {
696  // All VPDefs are also VPRecipeBases.
697  return true;
698  }
699 
700  static inline bool classof(const VPUser *U) {
701  return U->getVPUserID() == VPUser::VPUserID::Recipe;
702  }
703 
704  /// Returns true if the recipe may have side-effects.
705  bool mayHaveSideEffects() const;
706 
707  /// Returns true for PHI-like recipes.
708  bool isPhi() const {
709  return getVPDefID() >= VPFirstPHISC && getVPDefID() <= VPLastPHISC;
710  }
711 
712  /// Returns true if the recipe may read from memory.
713  bool mayReadFromMemory() const;
714 
715  /// Returns true if the recipe may write to memory.
716  bool mayWriteToMemory() const;
717 
718  /// Returns true if the recipe may read from or write to memory.
719  bool mayReadOrWriteMemory() const {
720  return mayReadFromMemory() || mayWriteToMemory();
721  }
722 };
723 
724 inline bool VPUser::classof(const VPDef *Def) {
725  return Def->getVPDefID() == VPRecipeBase::VPInstructionSC ||
726  Def->getVPDefID() == VPRecipeBase::VPWidenSC ||
727  Def->getVPDefID() == VPRecipeBase::VPWidenCallSC ||
728  Def->getVPDefID() == VPRecipeBase::VPWidenSelectSC ||
729  Def->getVPDefID() == VPRecipeBase::VPWidenGEPSC ||
730  Def->getVPDefID() == VPRecipeBase::VPBlendSC ||
731  Def->getVPDefID() == VPRecipeBase::VPInterleaveSC ||
732  Def->getVPDefID() == VPRecipeBase::VPReplicateSC ||
733  Def->getVPDefID() == VPRecipeBase::VPReductionSC ||
734  Def->getVPDefID() == VPRecipeBase::VPBranchOnMaskSC ||
735  Def->getVPDefID() == VPRecipeBase::VPWidenMemoryInstructionSC;
736 }
737 
738 /// This is a concrete Recipe that models a single VPlan-level instruction.
739 /// While as any Recipe it may generate a sequence of IR instructions when
740 /// executed, these instructions would always form a single-def expression as
741 /// the VPInstruction is also a single def-use vertex.
742 class VPInstruction : public VPRecipeBase, public VPValue {
743  friend class VPlanSlp;
744 
745 public:
746  /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
747  enum {
749  Instruction::OtherOpsEnd + 1, // Combines the incoming and previous
750  // values of a first-order recurrence.
760  };
761 
762 private:
763  typedef unsigned char OpcodeTy;
764  OpcodeTy Opcode;
765  FastMathFlags FMF;
766  DebugLoc DL;
767 
768  /// Utility method serving execute(): generates a single instance of the
769  /// modeled instruction.
770  void generateInstruction(VPTransformState &State, unsigned Part);
771 
772 protected:
774 
775 public:
777  : VPRecipeBase(VPRecipeBase::VPInstructionSC, Operands),
778  VPValue(VPValue::VPVInstructionSC, nullptr, this), Opcode(Opcode),
779  DL(DL) {}
780 
781  VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands,
782  DebugLoc DL = {})
784 
785  /// Method to support type inquiry through isa, cast, and dyn_cast.
786  static inline bool classof(const VPValue *V) {
788  }
789 
790  VPInstruction *clone() const {
792  return new VPInstruction(Opcode, Operands, DL);
793  }
794 
795  /// Method to support type inquiry through isa, cast, and dyn_cast.
796  static inline bool classof(const VPDef *R) {
797  return R->getVPDefID() == VPRecipeBase::VPInstructionSC;
798  }
799 
800  /// Extra classof implementations to allow directly casting from VPUser ->
801  /// VPInstruction.
802  static inline bool classof(const VPUser *U) {
803  auto *R = dyn_cast<VPRecipeBase>(U);
804  return R && R->getVPDefID() == VPRecipeBase::VPInstructionSC;
805  }
806  static inline bool classof(const VPRecipeBase *R) {
807  return R->getVPDefID() == VPRecipeBase::VPInstructionSC;
808  }
809 
810  unsigned getOpcode() const { return Opcode; }
811 
812  /// Generate the instruction.
813  /// TODO: We currently execute only per-part unless a specific instance is
814  /// provided.
815  void execute(VPTransformState &State) override;
816 
817 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
818  /// Print the VPInstruction to \p O.
819  void print(raw_ostream &O, const Twine &Indent,
820  VPSlotTracker &SlotTracker) const override;
821 
822  /// Print the VPInstruction to dbgs() (for debugging).
823  LLVM_DUMP_METHOD void dump() const;
824 #endif
825 
826  /// Return true if this instruction may modify memory.
827  bool mayWriteToMemory() const {
828  // TODO: we can use attributes of the called function to rule out memory
829  // modifications.
830  return Opcode == Instruction::Store || Opcode == Instruction::Call ||
831  Opcode == Instruction::Invoke || Opcode == SLPStore;
832  }
833 
834  bool hasResult() const {
835  // CallInst may or may not have a result, depending on the called function.
836  // Conservatively return calls have results for now.
837  switch (getOpcode()) {
838  case Instruction::Ret:
839  case Instruction::Br:
840  case Instruction::Store:
841  case Instruction::Switch:
842  case Instruction::IndirectBr:
843  case Instruction::Resume:
844  case Instruction::CatchRet:
845  case Instruction::Unreachable:
846  case Instruction::Fence:
847  case Instruction::AtomicRMW:
850  return false;
851  default:
852  return true;
853  }
854  }
855 
856  /// Set the fast-math flags.
857  void setFastMathFlags(FastMathFlags FMFNew);
858 
859  /// Returns true if the recipe only uses the first lane of operand \p Op.
860  bool onlyFirstLaneUsed(const VPValue *Op) const override {
862  "Op must be an operand of the recipe");
863  if (getOperand(0) != Op)
864  return false;
865  switch (getOpcode()) {
866  default:
867  return false;
872  return true;
873  };
874  llvm_unreachable("switch should return");
875  }
876 };
877 
878 /// VPWidenRecipe is a recipe for producing a copy of vector type its
879 /// ingredient. This recipe covers most of the traditional vectorization cases
880 /// where each ingredient transforms into a vectorized version of itself.
881 class VPWidenRecipe : public VPRecipeBase, public VPValue {
882 public:
883  template <typename IterT>
885  : VPRecipeBase(VPRecipeBase::VPWidenSC, Operands),
887 
888  ~VPWidenRecipe() override = default;
889 
890  /// Method to support type inquiry through isa, cast, and dyn_cast.
891  static inline bool classof(const VPDef *D) {
892  return D->getVPDefID() == VPRecipeBase::VPWidenSC;
893  }
894  static inline bool classof(const VPValue *V) {
895  return V->getVPValueID() == VPValue::VPVWidenSC;
896  }
897 
898  /// Produce widened copies of all Ingredients.
899  void execute(VPTransformState &State) override;
900 
901 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
902  /// Print the recipe.
903  void print(raw_ostream &O, const Twine &Indent,
904  VPSlotTracker &SlotTracker) const override;
905 #endif
906 };
907 
908 /// A recipe for widening Call instructions.
909 class VPWidenCallRecipe : public VPRecipeBase, public VPValue {
910 
911 public:
912  template <typename IterT>
914  : VPRecipeBase(VPRecipeBase::VPWidenCallSC, CallArguments),
916 
917  ~VPWidenCallRecipe() override = default;
918 
919  /// Method to support type inquiry through isa, cast, and dyn_cast.
920  static inline bool classof(const VPDef *D) {
921  return D->getVPDefID() == VPRecipeBase::VPWidenCallSC;
922  }
923 
924  /// Produce a widened version of the call instruction.
925  void execute(VPTransformState &State) override;
926 
927 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
928  /// Print the recipe.
929  void print(raw_ostream &O, const Twine &Indent,
930  VPSlotTracker &SlotTracker) const override;
931 #endif
932 };
933 
934 /// A recipe for widening select instructions.
935 class VPWidenSelectRecipe : public VPRecipeBase, public VPValue {
936 
937  /// Is the condition of the select loop invariant?
938  bool InvariantCond;
939 
940 public:
941  template <typename IterT>
943  bool InvariantCond)
944  : VPRecipeBase(VPRecipeBase::VPWidenSelectSC, Operands),
946  InvariantCond(InvariantCond) {}
947 
948  ~VPWidenSelectRecipe() override = default;
949 
950  /// Method to support type inquiry through isa, cast, and dyn_cast.
951  static inline bool classof(const VPDef *D) {
952  return D->getVPDefID() == VPRecipeBase::VPWidenSelectSC;
953  }
954 
955  /// Produce a widened version of the select instruction.
956  void execute(VPTransformState &State) override;
957 
958 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
959  /// Print the recipe.
960  void print(raw_ostream &O, const Twine &Indent,
961  VPSlotTracker &SlotTracker) const override;
962 #endif
963 };
964 
965 /// A recipe for handling GEP instructions.
966 class VPWidenGEPRecipe : public VPRecipeBase, public VPValue {
967  bool IsPtrLoopInvariant;
968  SmallBitVector IsIndexLoopInvariant;
969 
970 public:
971  template <typename IterT>
973  : VPRecipeBase(VPRecipeBase::VPWidenGEPSC, Operands),
974  VPValue(VPWidenGEPSC, GEP, this),
975  IsIndexLoopInvariant(GEP->getNumIndices(), false) {}
976 
977  template <typename IterT>
979  Loop *OrigLoop)
980  : VPRecipeBase(VPRecipeBase::VPWidenGEPSC, Operands),
982  IsIndexLoopInvariant(GEP->getNumIndices(), false) {
983  IsPtrLoopInvariant = OrigLoop->isLoopInvariant(GEP->getPointerOperand());
984  for (auto Index : enumerate(GEP->indices()))
985  IsIndexLoopInvariant[Index.index()] =
986  OrigLoop->isLoopInvariant(Index.value().get());
987  }
988  ~VPWidenGEPRecipe() override = default;
989 
990  /// Method to support type inquiry through isa, cast, and dyn_cast.
991  static inline bool classof(const VPDef *D) {
992  return D->getVPDefID() == VPRecipeBase::VPWidenGEPSC;
993  }
994 
995  /// Generate the gep nodes.
996  void execute(VPTransformState &State) override;
997 
998 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
999  /// Print the recipe.
1000  void print(raw_ostream &O, const Twine &Indent,
1001  VPSlotTracker &SlotTracker) const override;
1002 #endif
1003 };
1004 
1005 /// A recipe for handling phi nodes of integer and floating-point inductions,
1006 /// producing their vector values.
1008  PHINode *IV;
1009  const InductionDescriptor &IndDesc;
1010  bool NeedsVectorIV;
1011 
1012 public:
1014  const InductionDescriptor &IndDesc,
1015  bool NeedsVectorIV)
1016  : VPRecipeBase(VPWidenIntOrFpInductionSC, {Start, Step}),
1017  VPValue(IV, this), IV(IV), IndDesc(IndDesc),
1018  NeedsVectorIV(NeedsVectorIV) {}
1019 
1021  const InductionDescriptor &IndDesc,
1022  TruncInst *Trunc, bool NeedsVectorIV)
1023  : VPRecipeBase(VPWidenIntOrFpInductionSC, {Start, Step}),
1024  VPValue(Trunc, this), IV(IV), IndDesc(IndDesc),
1025  NeedsVectorIV(NeedsVectorIV) {}
1026 
1027  ~VPWidenIntOrFpInductionRecipe() override = default;
1028 
1029  /// Method to support type inquiry through isa, cast, and dyn_cast.
1030  static inline bool classof(const VPDef *D) {
1031  return D->getVPDefID() == VPRecipeBase::VPWidenIntOrFpInductionSC;
1032  }
1033 
1034  /// Generate the vectorized and scalarized versions of the phi node as
1035  /// needed by their users.
1036  void execute(VPTransformState &State) override;
1037 
1038 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1039  /// Print the recipe.
1040  void print(raw_ostream &O, const Twine &Indent,
1041  VPSlotTracker &SlotTracker) const override;
1042 #endif
1043 
1044  /// Returns the start value of the induction.
1046  const VPValue *getStartValue() const { return getOperand(0); }
1047 
1048  /// Returns the step value of the induction.
1049  VPValue *getStepValue() { return getOperand(1); }
1050  const VPValue *getStepValue() const { return getOperand(1); }
1051 
1052  /// Returns the first defined value as TruncInst, if it is one or nullptr
1053  /// otherwise.
1055  return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
1056  }
1057  const TruncInst *getTruncInst() const {
1058  return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
1059  }
1060 
1061  PHINode *getPHINode() { return IV; }
1062 
1063  /// Returns the induction descriptor for the recipe.
1064  const InductionDescriptor &getInductionDescriptor() const { return IndDesc; }
1065 
1066  /// Returns true if the induction is canonical, i.e. starting at 0 and
1067  /// incremented by UF * VF (= the original IV is incremented by 1).
1068  bool isCanonical() const;
1069 
1070  /// Returns the scalar type of the induction.
1071  const Type *getScalarType() const {
1072  const TruncInst *TruncI = getTruncInst();
1073  return TruncI ? TruncI->getType() : IV->getType();
1074  }
1075 
1076  /// Returns true if a vector phi needs to be created for the induction.
1077  bool needsVectorIV() const { return NeedsVectorIV; }
1078 };
1079 
1080 /// A pure virtual base class for all recipes modeling header phis, including
1081 /// phis for first order recurrences, pointer inductions and reductions. The
1082 /// start value is the first operand of the recipe and the incoming value from
1083 /// the backedge is the second operand.
1084 class VPHeaderPHIRecipe : public VPRecipeBase, public VPValue {
1085 protected:
1086  VPHeaderPHIRecipe(unsigned char VPVID, unsigned char VPDefID, PHINode *Phi,
1087  VPValue *Start = nullptr)
1088  : VPRecipeBase(VPDefID, {}), VPValue(VPVID, Phi, this) {
1089  if (Start)
1090  addOperand(Start);
1091  }
1092 
1093 public:
1094  ~VPHeaderPHIRecipe() override = default;
1095 
1096  /// Method to support type inquiry through isa, cast, and dyn_cast.
1097  static inline bool classof(const VPRecipeBase *B) {
1098  return B->getVPDefID() == VPRecipeBase::VPCanonicalIVPHISC ||
1099  B->getVPDefID() == VPRecipeBase::VPFirstOrderRecurrencePHISC ||
1100  B->getVPDefID() == VPRecipeBase::VPReductionPHISC ||
1101  B->getVPDefID() == VPRecipeBase::VPWidenIntOrFpInductionSC ||
1102  B->getVPDefID() == VPRecipeBase::VPWidenPHISC;
1103  }
1104  static inline bool classof(const VPValue *V) {
1105  return V->getVPValueID() == VPValue::VPVCanonicalIVPHISC ||
1110  }
1111 
1112  /// Generate the phi nodes.
1113  void execute(VPTransformState &State) override = 0;
1114 
1115 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1116  /// Print the recipe.
1117  void print(raw_ostream &O, const Twine &Indent,
1118  VPSlotTracker &SlotTracker) const override = 0;
1119 #endif
1120 
1121  /// Returns the start value of the phi, if one is set.
1123  return getNumOperands() == 0 ? nullptr : getOperand(0);
1124  }
1126  return getNumOperands() == 0 ? nullptr : getOperand(0);
1127  }
1128 
1129  /// Returns the incoming value from the loop backedge.
1131  return getOperand(1);
1132  }
1133 
1134  /// Returns the backedge value as a recipe. The backedge value is guaranteed
1135  /// to be a recipe.
1137  return cast<VPRecipeBase>(getBackedgeValue()->getDef());
1138  }
1139 };
1140 
1142  const InductionDescriptor &IndDesc;
1143 
1144  /// SCEV used to expand step.
1145  /// FIXME: move expansion of step to the pre-header, once it is modeled
1146  /// explicitly.
1147  ScalarEvolution &SE;
1148 
1149 public:
1150  /// Create a new VPWidenPointerInductionRecipe for \p Phi with start value \p
1151  /// Start.
1153  const InductionDescriptor &IndDesc,
1154  ScalarEvolution &SE)
1155  : VPHeaderPHIRecipe(VPVWidenPointerInductionSC, VPWidenPointerInductionSC,
1156  Phi),
1157  IndDesc(IndDesc), SE(SE) {
1158  addOperand(Start);
1159  }
1160 
1161  ~VPWidenPointerInductionRecipe() override = default;
1162 
1163  /// Method to support type inquiry through isa, cast, and dyn_cast.
1164  static inline bool classof(const VPRecipeBase *B) {
1165  return B->getVPDefID() == VPRecipeBase::VPWidenPointerInductionSC;
1166  }
1167  static inline bool classof(const VPHeaderPHIRecipe *R) {
1168  return R->getVPDefID() == VPRecipeBase::VPWidenPointerInductionSC;
1169  }
1170  static inline bool classof(const VPValue *V) {
1172  }
1173 
1174  /// Generate vector values for the pointer induction.
1175  void execute(VPTransformState &State) override;
1176 
1177  /// Returns true if only scalar values will be generated.
1179 
1180 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1181  /// Print the recipe.
1182  void print(raw_ostream &O, const Twine &Indent,
1183  VPSlotTracker &SlotTracker) const override;
1184 #endif
1185 };
1186 
1187 /// A recipe for handling header phis that are widened in the vector loop.
1188 /// In the VPlan native path, all incoming VPValues & VPBasicBlock pairs are
1189 /// managed in the recipe directly.
1191  /// List of incoming blocks. Only used in the VPlan native path.
1192  SmallVector<VPBasicBlock *, 2> IncomingBlocks;
1193 
1194 public:
1195  /// Create a new VPWidenPHIRecipe for \p Phi with start value \p Start.
1196  VPWidenPHIRecipe(PHINode *Phi, VPValue *Start = nullptr)
1197  : VPHeaderPHIRecipe(VPVWidenPHISC, VPWidenPHISC, Phi) {
1198  if (Start)
1199  addOperand(Start);
1200  }
1201 
1202  ~VPWidenPHIRecipe() override = default;
1203 
1204  /// Method to support type inquiry through isa, cast, and dyn_cast.
1205  static inline bool classof(const VPRecipeBase *B) {
1206  return B->getVPDefID() == VPRecipeBase::VPWidenPHISC;
1207  }
1208  static inline bool classof(const VPHeaderPHIRecipe *R) {
1209  return R->getVPDefID() == VPRecipeBase::VPWidenPHISC;
1210  }
1211  static inline bool classof(const VPValue *V) {
1212  return V->getVPValueID() == VPValue::VPVWidenPHISC;
1213  }
1214 
1215  /// Generate the phi/select nodes.
1216  void execute(VPTransformState &State) override;
1217 
1218 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1219  /// Print the recipe.
1220  void print(raw_ostream &O, const Twine &Indent,
1221  VPSlotTracker &SlotTracker) const override;
1222 #endif
1223 
1224  /// Adds a pair (\p IncomingV, \p IncomingBlock) to the phi.
1225  void addIncoming(VPValue *IncomingV, VPBasicBlock *IncomingBlock) {
1226  addOperand(IncomingV);
1227  IncomingBlocks.push_back(IncomingBlock);
1228  }
1229 
1230  /// Returns the \p I th incoming VPBasicBlock.
1231  VPBasicBlock *getIncomingBlock(unsigned I) { return IncomingBlocks[I]; }
1232 
1233  /// Returns the \p I th incoming VPValue.
1234  VPValue *getIncomingValue(unsigned I) { return getOperand(I); }
1235 };
1236 
1237 /// A recipe for handling first-order recurrence phis. The start value is the
1238 /// first operand of the recipe and the incoming value from the backedge is the
1239 /// second operand.
1243  VPFirstOrderRecurrencePHISC, Phi, &Start) {}
1244 
1245  /// Method to support type inquiry through isa, cast, and dyn_cast.
1246  static inline bool classof(const VPRecipeBase *R) {
1247  return R->getVPDefID() == VPRecipeBase::VPFirstOrderRecurrencePHISC;
1248  }
1249  static inline bool classof(const VPHeaderPHIRecipe *R) {
1250  return R->getVPDefID() == VPRecipeBase::VPFirstOrderRecurrencePHISC;
1251  }
1252  static inline bool classof(const VPValue *V) {
1254  }
1255 
1256  void execute(VPTransformState &State) override;
1257 
1258 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1259  /// Print the recipe.
1260  void print(raw_ostream &O, const Twine &Indent,
1261  VPSlotTracker &SlotTracker) const override;
1262 #endif
1263 };
1264 
1265 /// A recipe for handling reduction phis. The start value is the first operand
1266 /// of the recipe and the incoming value from the backedge is the second
1267 /// operand.
1269  /// Descriptor for the reduction.
1270  const RecurrenceDescriptor &RdxDesc;
1271 
1272  /// The phi is part of an in-loop reduction.
1273  bool IsInLoop;
1274 
1275  /// The phi is part of an ordered reduction. Requires IsInLoop to be true.
1276  bool IsOrdered;
1277 
1278 public:
1279  /// Create a new VPReductionPHIRecipe for the reduction \p Phi described by \p
1280  /// RdxDesc.
1282  VPValue &Start, bool IsInLoop = false,
1283  bool IsOrdered = false)
1284  : VPHeaderPHIRecipe(VPVReductionPHISC, VPReductionPHISC, Phi, &Start),
1285  RdxDesc(RdxDesc), IsInLoop(IsInLoop), IsOrdered(IsOrdered) {
1286  assert((!IsOrdered || IsInLoop) && "IsOrdered requires IsInLoop");
1287  }
1288 
1289  ~VPReductionPHIRecipe() override = default;
1290 
1291  /// Method to support type inquiry through isa, cast, and dyn_cast.
1292  static inline bool classof(const VPRecipeBase *R) {
1293  return R->getVPDefID() == VPRecipeBase::VPReductionPHISC;
1294  }
1295  static inline bool classof(const VPHeaderPHIRecipe *R) {
1296  return R->getVPDefID() == VPRecipeBase::VPReductionPHISC;
1297  }
1298  static inline bool classof(const VPValue *V) {
1300  }
1301 
1302  /// Generate the phi/select nodes.
1303  void execute(VPTransformState &State) override;
1304 
1305 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1306  /// Print the recipe.
1307  void print(raw_ostream &O, const Twine &Indent,
1308  VPSlotTracker &SlotTracker) const override;
1309 #endif
1310 
1312  return RdxDesc;
1313  }
1314 
1315  /// Returns true, if the phi is part of an ordered reduction.
1316  bool isOrdered() const { return IsOrdered; }
1317 
1318  /// Returns true, if the phi is part of an in-loop reduction.
1319  bool isInLoop() const { return IsInLoop; }
1320 };
1321 
1322 /// A recipe for vectorizing a phi-node as a sequence of mask-based select
1323 /// instructions.
1324 class VPBlendRecipe : public VPRecipeBase, public VPValue {
1325  PHINode *Phi;
1326 
1327 public:
1328  /// The blend operation is a User of the incoming values and of their
1329  /// respective masks, ordered [I0, M0, I1, M1, ...]. Note that a single value
1330  /// might be incoming with a full mask for which there is no VPValue.
1332  : VPRecipeBase(VPBlendSC, Operands),
1333  VPValue(VPValue::VPVBlendSC, Phi, this), Phi(Phi) {
1334  assert(Operands.size() > 0 &&
1335  ((Operands.size() == 1) || (Operands.size() % 2 == 0)) &&
1336  "Expected either a single incoming value or a positive even number "
1337  "of operands");
1338  }
1339 
1340  /// Method to support type inquiry through isa, cast, and dyn_cast.
1341  static inline bool classof(const VPDef *D) {
1342  return D->getVPDefID() == VPRecipeBase::VPBlendSC;
1343  }
1344 
1345  /// Return the number of incoming values, taking into account that a single
1346  /// incoming value has no mask.
1347  unsigned getNumIncomingValues() const { return (getNumOperands() + 1) / 2; }
1348 
1349  /// Return incoming value number \p Idx.
1350  VPValue *getIncomingValue(unsigned Idx) const { return getOperand(Idx * 2); }
1351 
1352  /// Return mask number \p Idx.
1353  VPValue *getMask(unsigned Idx) const { return getOperand(Idx * 2 + 1); }
1354 
1355  /// Generate the phi/select nodes.
1356  void execute(VPTransformState &State) override;
1357 
1358 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1359  /// Print the recipe.
1360  void print(raw_ostream &O, const Twine &Indent,
1361  VPSlotTracker &SlotTracker) const override;
1362 #endif
1363 
1364  /// Returns true if the recipe only uses the first lane of operand \p Op.
1365  bool onlyFirstLaneUsed(const VPValue *Op) const override {
1367  "Op must be an operand of the recipe");
1368  // Recursing through Blend recipes only, must terminate at header phi's the
1369  // latest.
1370  return all_of(users(),
1371  [this](VPUser *U) { return U->onlyFirstLaneUsed(this); });
1372  }
1373 };
1374 
1375 /// VPInterleaveRecipe is a recipe for transforming an interleave group of load
1376 /// or stores into one wide load/store and shuffles. The first operand of a
1377 /// VPInterleave recipe is the address, followed by the stored values, followed
1378 /// by an optional mask.
1380  const InterleaveGroup<Instruction> *IG;
1381 
1382  bool HasMask = false;
1383 
1384 public:
1386  ArrayRef<VPValue *> StoredValues, VPValue *Mask)
1387  : VPRecipeBase(VPInterleaveSC, {Addr}), IG(IG) {
1388  for (unsigned i = 0; i < IG->getFactor(); ++i)
1389  if (Instruction *I = IG->getMember(i)) {
1390  if (I->getType()->isVoidTy())
1391  continue;
1392  new VPValue(I, this);
1393  }
1394 
1395  for (auto *SV : StoredValues)
1396  addOperand(SV);
1397  if (Mask) {
1398  HasMask = true;
1399  addOperand(Mask);
1400  }
1401  }
1402  ~VPInterleaveRecipe() override = default;
1403 
1404  /// Method to support type inquiry through isa, cast, and dyn_cast.
1405  static inline bool classof(const VPDef *D) {
1406  return D->getVPDefID() == VPRecipeBase::VPInterleaveSC;
1407  }
1408 
1409  /// Return the address accessed by this recipe.
1410  VPValue *getAddr() const {
1411  return getOperand(0); // Address is the 1st, mandatory operand.
1412  }
1413 
1414  /// Return the mask used by this recipe. Note that a full mask is represented
1415  /// by a nullptr.
1416  VPValue *getMask() const {
1417  // Mask is optional and therefore the last, currently 2nd operand.
1418  return HasMask ? getOperand(getNumOperands() - 1) : nullptr;
1419  }
1420 
1421  /// Return the VPValues stored by this interleave group. If it is a load
1422  /// interleave group, return an empty ArrayRef.
1424  // The first operand is the address, followed by the stored values, followed
1425  // by an optional mask.
1427  .slice(1, getNumStoreOperands());
1428  }
1429 
1430  /// Generate the wide load or store, and shuffles.
1431  void execute(VPTransformState &State) override;
1432 
1433 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1434  /// Print the recipe.
1435  void print(raw_ostream &O, const Twine &Indent,
1436  VPSlotTracker &SlotTracker) const override;
1437 #endif
1438 
1440 
1441  /// Returns the number of stored operands of this interleave group. Returns 0
1442  /// for load interleave groups.
1443  unsigned getNumStoreOperands() const {
1444  return getNumOperands() - (HasMask ? 2 : 1);
1445  }
1446 
1447  /// The recipe only uses the first lane of the address.
1448  bool onlyFirstLaneUsed(const VPValue *Op) const override {
1450  "Op must be an operand of the recipe");
1451  return Op == getAddr() && all_of(getStoredValues(), [Op](VPValue *StoredV) {
1452  return Op != StoredV;
1453  });
1454  }
1455 };
1456 
1457 /// A recipe to represent inloop reduction operations, performing a reduction on
1458 /// a vector operand into a scalar value, and adding the result to a chain.
1459 /// The Operands are {ChainOp, VecOp, [Condition]}.
1460 class VPReductionRecipe : public VPRecipeBase, public VPValue {
1461  /// The recurrence decriptor for the reduction in question.
1462  const RecurrenceDescriptor *RdxDesc;
1463  /// Pointer to the TTI, needed to create the target reduction
1464  const TargetTransformInfo *TTI;
1465 
1466 public:
1468  VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp,
1469  const TargetTransformInfo *TTI)
1470  : VPRecipeBase(VPRecipeBase::VPReductionSC, {ChainOp, VecOp}),
1471  VPValue(VPValue::VPVReductionSC, I, this), RdxDesc(R), TTI(TTI) {
1472  if (CondOp)
1473  addOperand(CondOp);
1474  }
1475 
1476  ~VPReductionRecipe() override = default;
1477 
1478  /// Method to support type inquiry through isa, cast, and dyn_cast.
1479  static inline bool classof(const VPValue *V) {
1480  return V->getVPValueID() == VPValue::VPVReductionSC;
1481  }
1482 
1483  /// Generate the reduction in the loop
1484  void execute(VPTransformState &State) override;
1485 
1486 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1487  /// Print the recipe.
1488  void print(raw_ostream &O, const Twine &Indent,
1489  VPSlotTracker &SlotTracker) const override;
1490 #endif
1491 
1492  /// The VPValue of the scalar Chain being accumulated.
1493  VPValue *getChainOp() const { return getOperand(0); }
1494  /// The VPValue of the vector value to be reduced.
1495  VPValue *getVecOp() const { return getOperand(1); }
1496  /// The VPValue of the condition for the block.
1497  VPValue *getCondOp() const {
1498  return getNumOperands() > 2 ? getOperand(2) : nullptr;
1499  }
1500 };
1501 
1502 /// VPReplicateRecipe replicates a given instruction producing multiple scalar
1503 /// copies of the original scalar type, one per lane, instead of producing a
1504 /// single copy of widened type for all lanes. If the instruction is known to be
1505 /// uniform only one copy, per lane zero, will be generated.
1506 class VPReplicateRecipe : public VPRecipeBase, public VPValue {
1507  /// Indicator if only a single replica per lane is needed.
1508  bool IsUniform;
1509 
1510  /// Indicator if the replicas are also predicated.
1511  bool IsPredicated;
1512 
1513  /// Indicator if the scalar values should also be packed into a vector.
1514  bool AlsoPack;
1515 
1516 public:
1517  template <typename IterT>
1519  bool IsUniform, bool IsPredicated = false)
1520  : VPRecipeBase(VPReplicateSC, Operands), VPValue(VPVReplicateSC, I, this),
1521  IsUniform(IsUniform), IsPredicated(IsPredicated) {
1522  // Retain the previous behavior of predicateInstructions(), where an
1523  // insert-element of a predicated instruction got hoisted into the
1524  // predicated basic block iff it was its only user. This is achieved by
1525  // having predicated instructions also pack their values into a vector by
1526  // default unless they have a replicated user which uses their scalar value.
1527  AlsoPack = IsPredicated && !I->use_empty();
1528  }
1529 
1530  ~VPReplicateRecipe() override = default;
1531 
1532  /// Method to support type inquiry through isa, cast, and dyn_cast.
1533  static inline bool classof(const VPDef *D) {
1534  return D->getVPDefID() == VPRecipeBase::VPReplicateSC;
1535  }
1536 
1537  static inline bool classof(const VPValue *V) {
1538  return V->getVPValueID() == VPValue::VPVReplicateSC;
1539  }
1540 
1541  /// Generate replicas of the desired Ingredient. Replicas will be generated
1542  /// for all parts and lanes unless a specific part and lane are specified in
1543  /// the \p State.
1544  void execute(VPTransformState &State) override;
1545 
1546  void setAlsoPack(bool Pack) { AlsoPack = Pack; }
1547 
1548 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1549  /// Print the recipe.
1550  void print(raw_ostream &O, const Twine &Indent,
1551  VPSlotTracker &SlotTracker) const override;
1552 #endif
1553 
1554  bool isUniform() const { return IsUniform; }
1555 
1556  bool isPacked() const { return AlsoPack; }
1557 
1558  bool isPredicated() const { return IsPredicated; }
1559 
1560  /// Returns true if the recipe only uses the first lane of operand \p Op.
1561  bool onlyFirstLaneUsed(const VPValue *Op) const override {
1563  "Op must be an operand of the recipe");
1564  return isUniform();
1565  }
1566 
1567  /// Returns true if the recipe uses scalars of operand \p Op.
1568  bool usesScalars(const VPValue *Op) const override {
1570  "Op must be an operand of the recipe");
1571  return true;
1572  }
1573 };
1574 
1575 /// A recipe for generating conditional branches on the bits of a mask.
1577 public:
1579  : VPRecipeBase(VPBranchOnMaskSC, {}) {
1580  if (BlockInMask) // nullptr means all-one mask.
1581  addOperand(BlockInMask);
1582  }
1583 
1584  /// Method to support type inquiry through isa, cast, and dyn_cast.
1585  static inline bool classof(const VPDef *D) {
1586  return D->getVPDefID() == VPRecipeBase::VPBranchOnMaskSC;
1587  }
1588 
1589  /// Generate the extraction of the appropriate bit from the block mask and the
1590  /// conditional branch.
1591  void execute(VPTransformState &State) override;
1592 
1593 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1594  /// Print the recipe.
1595  void print(raw_ostream &O, const Twine &Indent,
1596  VPSlotTracker &SlotTracker) const override {
1597  O << Indent << "BRANCH-ON-MASK ";
1598  if (VPValue *Mask = getMask())
1599  Mask->printAsOperand(O, SlotTracker);
1600  else
1601  O << " All-One";
1602  }
1603 #endif
1604 
1605  /// Return the mask used by this recipe. Note that a full mask is represented
1606  /// by a nullptr.
1607  VPValue *getMask() const {
1608  assert(getNumOperands() <= 1 && "should have either 0 or 1 operands");
1609  // Mask is optional.
1610  return getNumOperands() == 1 ? getOperand(0) : nullptr;
1611  }
1612 
1613  /// Returns true if the recipe uses scalars of operand \p Op.
1614  bool usesScalars(const VPValue *Op) const override {
1616  "Op must be an operand of the recipe");
1617  return true;
1618  }
1619 };
1620 
1621 /// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
1622 /// control converges back from a Branch-on-Mask. The phi nodes are needed in
1623 /// order to merge values that are set under such a branch and feed their uses.
1624 /// The phi nodes can be scalar or vector depending on the users of the value.
1625 /// This recipe works in concert with VPBranchOnMaskRecipe.
1626 class VPPredInstPHIRecipe : public VPRecipeBase, public VPValue {
1627 public:
1628  /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
1629  /// nodes after merging back from a Branch-on-Mask.
1631  : VPRecipeBase(VPPredInstPHISC, PredV),
1632  VPValue(VPValue::VPVPredInstPHI, nullptr, this) {}
1633  ~VPPredInstPHIRecipe() override = default;
1634 
1635  /// Method to support type inquiry through isa, cast, and dyn_cast.
1636  static inline bool classof(const VPDef *D) {
1637  return D->getVPDefID() == VPRecipeBase::VPPredInstPHISC;
1638  }
1639 
1640  /// Generates phi nodes for live-outs as needed to retain SSA form.
1641  void execute(VPTransformState &State) override;
1642 
1643 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1644  /// Print the recipe.
1645  void print(raw_ostream &O, const Twine &Indent,
1646  VPSlotTracker &SlotTracker) const override;
1647 #endif
1648 
1649  /// Returns true if the recipe uses scalars of operand \p Op.
1650  bool usesScalars(const VPValue *Op) const override {
1652  "Op must be an operand of the recipe");
1653  return true;
1654  }
1655 };
1656 
1657 /// A Recipe for widening load/store operations.
1658 /// The recipe uses the following VPValues:
1659 /// - For load: Address, optional mask
1660 /// - For store: Address, stored value, optional mask
1661 /// TODO: We currently execute only per-part unless a specific instance is
1662 /// provided.
1664  Instruction &Ingredient;
1665 
1666  // Whether the loaded-from / stored-to addresses are consecutive.
1667  bool Consecutive;
1668 
1669  // Whether the consecutive loaded/stored addresses are in reverse order.
1670  bool Reverse;
1671 
1672  void setMask(VPValue *Mask) {
1673  if (!Mask)
1674  return;
1675  addOperand(Mask);
1676  }
1677 
1678  bool isMasked() const {
1679  return isStore() ? getNumOperands() == 3 : getNumOperands() == 2;
1680  }
1681 
1682 public:
1684  bool Consecutive, bool Reverse)
1685  : VPRecipeBase(VPWidenMemoryInstructionSC, {Addr}), Ingredient(Load),
1686  Consecutive(Consecutive), Reverse(Reverse) {
1687  assert((Consecutive || !Reverse) && "Reverse implies consecutive");
1689  setMask(Mask);
1690  }
1691 
1693  VPValue *StoredValue, VPValue *Mask,
1694  bool Consecutive, bool Reverse)
1695  : VPRecipeBase(VPWidenMemoryInstructionSC, {Addr, StoredValue}),
1696  Ingredient(Store), Consecutive(Consecutive), Reverse(Reverse) {
1697  assert((Consecutive || !Reverse) && "Reverse implies consecutive");
1698  setMask(Mask);
1699  }
1700 
1701  /// Method to support type inquiry through isa, cast, and dyn_cast.
1702  static inline bool classof(const VPDef *D) {
1703  return D->getVPDefID() == VPRecipeBase::VPWidenMemoryInstructionSC;
1704  }
1705 
1706  /// Return the address accessed by this recipe.
1707  VPValue *getAddr() const {
1708  return getOperand(0); // Address is the 1st, mandatory operand.
1709  }
1710 
1711  /// Return the mask used by this recipe. Note that a full mask is represented
1712  /// by a nullptr.
1713  VPValue *getMask() const {
1714  // Mask is optional and therefore the last operand.
1715  return isMasked() ? getOperand(getNumOperands() - 1) : nullptr;
1716  }
1717 
1718  /// Returns true if this recipe is a store.
1719  bool isStore() const { return isa<StoreInst>(Ingredient); }
1720 
1721  /// Return the address accessed by this recipe.
1723  assert(isStore() && "Stored value only available for store instructions");
1724  return getOperand(1); // Stored value is the 2nd, mandatory operand.
1725  }
1726 
1727  // Return whether the loaded-from / stored-to addresses are consecutive.
1728  bool isConsecutive() const { return Consecutive; }
1729 
1730  // Return whether the consecutive loaded/stored addresses are in reverse
1731  // order.
1732  bool isReverse() const { return Reverse; }
1733 
1734  /// Generate the wide load/store.
1735  void execute(VPTransformState &State) override;
1736 
1737 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1738  /// Print the recipe.
1739  void print(raw_ostream &O, const Twine &Indent,
1740  VPSlotTracker &SlotTracker) const override;
1741 #endif
1742 
1743  /// Returns true if the recipe only uses the first lane of operand \p Op.
1744  bool onlyFirstLaneUsed(const VPValue *Op) const override {
1746  "Op must be an operand of the recipe");
1747 
1748  // Widened, consecutive memory operations only demand the first lane of
1749  // their address, unless the same operand is also stored. That latter can
1750  // happen with opaque pointers.
1751  return Op == getAddr() && isConsecutive() &&
1752  (!isStore() || Op != getStoredValue());
1753  }
1754 
1755  Instruction &getIngredient() const { return Ingredient; }
1756 };
1757 
1758 /// Recipe to expand a SCEV expression.
1759 class VPExpandSCEVRecipe : public VPRecipeBase, public VPValue {
1760  const SCEV *Expr;
1761  ScalarEvolution &SE;
1762 
1763 public:
1765  : VPRecipeBase(VPExpandSCEVSC, {}), VPValue(nullptr, this), Expr(Expr),
1766  SE(SE) {}
1767 
1768  ~VPExpandSCEVRecipe() override = default;
1769 
1770  /// Method to support type inquiry through isa, cast, and dyn_cast.
1771  static inline bool classof(const VPDef *D) {
1772  return D->getVPDefID() == VPExpandSCEVSC;
1773  }
1774 
1775  /// Generate a canonical vector induction variable of the vector loop, with
1776  void execute(VPTransformState &State) override;
1777 
1778 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1779  /// Print the recipe.
1780  void print(raw_ostream &O, const Twine &Indent,
1781  VPSlotTracker &SlotTracker) const override;
1782 #endif
1783 
1784  const SCEV *getSCEV() const { return Expr; }
1785 };
1786 
1787 /// Canonical scalar induction phi of the vector loop. Starting at the specified
1788 /// start value (either 0 or the resume value when vectorizing the epilogue
1789 /// loop). VPWidenCanonicalIVRecipe represents the vector version of the
1790 /// canonical induction variable.
1792  DebugLoc DL;
1793 
1794 public:
1796  : VPHeaderPHIRecipe(VPValue::VPVCanonicalIVPHISC, VPCanonicalIVPHISC,
1797  nullptr, StartV),
1798  DL(DL) {}
1799 
1800  ~VPCanonicalIVPHIRecipe() override = default;
1801 
1802  /// Method to support type inquiry through isa, cast, and dyn_cast.
1803  static inline bool classof(const VPDef *D) {
1804  return D->getVPDefID() == VPCanonicalIVPHISC;
1805  }
1806  static inline bool classof(const VPHeaderPHIRecipe *D) {
1807  return D->getVPDefID() == VPCanonicalIVPHISC;
1808  }
1809  static inline bool classof(const VPValue *V) {
1811  }
1812 
1813  /// Generate the canonical scalar induction phi of the vector loop.
1814  void execute(VPTransformState &State) override;
1815 
1816 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1817  /// Print the recipe.
1818  void print(raw_ostream &O, const Twine &Indent,
1819  VPSlotTracker &SlotTracker) const override;
1820 #endif
1821 
1822  /// Returns the scalar type of the induction.
1823  const Type *getScalarType() const {
1824  return getOperand(0)->getLiveInIRValue()->getType();
1825  }
1826 
1827  /// Returns true if the recipe only uses the first lane of operand \p Op.
1828  bool onlyFirstLaneUsed(const VPValue *Op) const override {
1830  "Op must be an operand of the recipe");
1831  return true;
1832  }
1833 };
1834 
1835 /// A Recipe for widening the canonical induction variable of the vector loop.
1837 public:
1839  : VPRecipeBase(VPWidenCanonicalIVSC, {CanonicalIV}),
1840  VPValue(VPValue::VPVWidenCanonicalIVSC, nullptr, this) {}
1841 
1842  ~VPWidenCanonicalIVRecipe() override = default;
1843 
1844  /// Method to support type inquiry through isa, cast, and dyn_cast.
1845  static inline bool classof(const VPDef *D) {
1846  return D->getVPDefID() == VPRecipeBase::VPWidenCanonicalIVSC;
1847  }
1848 
1849  /// Extra classof implementations to allow directly casting from VPUser ->
1850  /// VPWidenCanonicalIVRecipe.
1851  static inline bool classof(const VPUser *U) {
1852  auto *R = dyn_cast<VPRecipeBase>(U);
1853  return R && R->getVPDefID() == VPRecipeBase::VPWidenCanonicalIVSC;
1854  }
1855  static inline bool classof(const VPRecipeBase *R) {
1856  return R->getVPDefID() == VPRecipeBase::VPWidenCanonicalIVSC;
1857  }
1858 
1859  /// Generate a canonical vector induction variable of the vector loop, with
1860  /// start = {<Part*VF, Part*VF+1, ..., Part*VF+VF-1> for 0 <= Part < UF}, and
1861  /// step = <VF*UF, VF*UF, ..., VF*UF>.
1862  void execute(VPTransformState &State) override;
1863 
1864 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1865  /// Print the recipe.
1866  void print(raw_ostream &O, const Twine &Indent,
1867  VPSlotTracker &SlotTracker) const override;
1868 #endif
1869 
1870  /// Returns the scalar type of the induction.
1871  const Type *getScalarType() const {
1872  return cast<VPCanonicalIVPHIRecipe>(getOperand(0)->getDef())
1873  ->getScalarType();
1874  }
1875 };
1876 
1877 /// A recipe for handling phi nodes of integer and floating-point inductions,
1878 /// producing their scalar values.
1880  /// Scalar type to use for the generated values.
1881  Type *Ty;
1882  /// If not nullptr, truncate the generated values to TruncToTy.
1883  Type *TruncToTy;
1884  const InductionDescriptor &IndDesc;
1885 
1886 public:
1888  VPValue *CanonicalIV, VPValue *Start, VPValue *Step,
1889  Type *TruncToTy)
1890  : VPRecipeBase(VPScalarIVStepsSC, {CanonicalIV, Start, Step}),
1891  VPValue(nullptr, this), Ty(Ty), TruncToTy(TruncToTy), IndDesc(IndDesc) {
1892  }
1893 
1894  ~VPScalarIVStepsRecipe() override = default;
1895 
1896  /// Method to support type inquiry through isa, cast, and dyn_cast.
1897  static inline bool classof(const VPDef *D) {
1898  return D->getVPDefID() == VPRecipeBase::VPScalarIVStepsSC;
1899  }
1900  /// Extra classof implementations to allow directly casting from VPUser ->
1901  /// VPScalarIVStepsRecipe.
1902  static inline bool classof(const VPUser *U) {
1903  auto *R = dyn_cast<VPRecipeBase>(U);
1904  return R && R->getVPDefID() == VPRecipeBase::VPScalarIVStepsSC;
1905  }
1906  static inline bool classof(const VPRecipeBase *R) {
1907  return R->getVPDefID() == VPRecipeBase::VPScalarIVStepsSC;
1908  }
1909 
1910  /// Generate the scalarized versions of the phi node as needed by their users.
1911  void execute(VPTransformState &State) override;
1912 
1913 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1914  /// Print the recipe.
1915  void print(raw_ostream &O, const Twine &Indent,
1916  VPSlotTracker &SlotTracker) const override;
1917 #endif
1918 
1919  /// Returns true if the induction is canonical, i.e. starting at 0 and
1920  /// incremented by UF * VF (= the original IV is incremented by 1).
1921  bool isCanonical() const;
1922 
1924  VPValue *getStartValue() const { return getOperand(1); }
1925  VPValue *getStepValue() const { return getOperand(2); }
1926 
1927  /// Returns true if the recipe only uses the first lane of operand \p Op.
1928  bool onlyFirstLaneUsed(const VPValue *Op) const override {
1930  "Op must be an operand of the recipe");
1931  return true;
1932  }
1933 };
1934 
1935 /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
1936 /// holds a sequence of zero or more VPRecipe's each representing a sequence of
1937 /// output IR instructions. All PHI-like recipes must come before any non-PHI recipes.
1938 class VPBasicBlock : public VPBlockBase {
1939 public:
1941 
1942 private:
1943  /// The VPRecipes held in the order of output instructions to generate.
1944  RecipeListTy Recipes;
1945 
1946 public:
1947  VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr)
1948  : VPBlockBase(VPBasicBlockSC, Name.str()) {
1949  if (Recipe)
1950  appendRecipe(Recipe);
1951  }
1952 
1953  ~VPBasicBlock() override {
1954  while (!Recipes.empty())
1955  Recipes.pop_back();
1956  }
1957 
1958  /// Instruction iterators...
1963 
1964  //===--------------------------------------------------------------------===//
1965  /// Recipe iterator methods
1966  ///
1967  inline iterator begin() { return Recipes.begin(); }
1968  inline const_iterator begin() const { return Recipes.begin(); }
1969  inline iterator end() { return Recipes.end(); }
1970  inline const_iterator end() const { return Recipes.end(); }
1971 
1972  inline reverse_iterator rbegin() { return Recipes.rbegin(); }
1973  inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); }
1974  inline reverse_iterator rend() { return Recipes.rend(); }
1975  inline const_reverse_iterator rend() const { return Recipes.rend(); }
1976 
1977  inline size_t size() const { return Recipes.size(); }
1978  inline bool empty() const { return Recipes.empty(); }
1979  inline const VPRecipeBase &front() const { return Recipes.front(); }
1980  inline VPRecipeBase &front() { return Recipes.front(); }
1981  inline const VPRecipeBase &back() const { return Recipes.back(); }
1982  inline VPRecipeBase &back() { return Recipes.back(); }
1983 
1984  /// Returns a reference to the list of recipes.
1985  RecipeListTy &getRecipeList() { return Recipes; }
1986 
1987  /// Returns a pointer to a member of the recipe list.
1989  return &VPBasicBlock::Recipes;
1990  }
1991 
1992  /// Method to support type inquiry through isa, cast, and dyn_cast.
1993  static inline bool classof(const VPBlockBase *V) {
1994  return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC;
1995  }
1996 
1997  void insert(VPRecipeBase *Recipe, iterator InsertPt) {
1998  assert(Recipe && "No recipe to append.");
1999  assert(!Recipe->Parent && "Recipe already in VPlan");
2000  Recipe->Parent = this;
2001  Recipes.insert(InsertPt, Recipe);
2002  }
2003 
2004  /// Augment the existing recipes of a VPBasicBlock with an additional
2005  /// \p Recipe as the last recipe.
2006  void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); }
2007 
2008  /// The method which generates the output IR instructions that correspond to
2009  /// this VPBasicBlock, thereby "executing" the VPlan.
2010  void execute(struct VPTransformState *State) override;
2011 
2012  /// Return the position of the first non-phi node recipe in the block.
2014 
2015  /// Returns an iterator range over the PHI-like recipes in the block.
2017  return make_range(begin(), getFirstNonPhi());
2018  }
2019 
2020  void dropAllReferences(VPValue *NewValue) override;
2021 
2022  /// Split current block at \p SplitAt by inserting a new block between the
2023  /// current block and its successors and moving all recipes starting at
2024  /// SplitAt to the new block. Returns the new block.
2025  VPBasicBlock *splitAt(iterator SplitAt);
2026 
2028 
2029 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2030  /// Print this VPBsicBlock to \p O, prefixing all lines with \p Indent. \p
2031  /// SlotTracker is used to print unnamed VPValue's using consequtive numbers.
2032  ///
2033  /// Note that the numbering is applied to the whole VPlan, so printing
2034  /// individual blocks is consistent with the whole VPlan printing.
2035  void print(raw_ostream &O, const Twine &Indent,
2036  VPSlotTracker &SlotTracker) const override;
2037  using VPBlockBase::print; // Get the print(raw_stream &O) version.
2038 #endif
2039 
2040  /// If the block has multiple successors, return the branch recipe terminating
2041  /// the block. If there are no or only a single successor, return nullptr;
2043  const VPRecipeBase *getTerminator() const;
2044 
2045  /// Returns true if the block is exiting it's parent region.
2046  bool isExiting() const;
2047 
2048 private:
2049  /// Create an IR BasicBlock to hold the output instructions generated by this
2050  /// VPBasicBlock, and return it. Update the CFGState accordingly.
2051  BasicBlock *createEmptyBasicBlock(VPTransformState::CFGState &CFG);
2052 };
2053 
2054 /// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks
2055 /// which form a Single-Entry-Single-Exiting subgraph of the output IR CFG.
2056 /// A VPRegionBlock may indicate that its contents are to be replicated several
2057 /// times. This is designed to support predicated scalarization, in which a
2058 /// scalar if-then code structure needs to be generated VF * UF times. Having
2059 /// this replication indicator helps to keep a single model for multiple
2060 /// candidate VF's. The actual replication takes place only once the desired VF
2061 /// and UF have been determined.
2062 class VPRegionBlock : public VPBlockBase {
2063  /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock.
2064  VPBlockBase *Entry;
2065 
2066  /// Hold the Single Exiting block of the SESE region modelled by the
2067  /// VPRegionBlock.
2068  VPBlockBase *Exiting;
2069 
2070  /// An indicator whether this region is to generate multiple replicated
2071  /// instances of output IR corresponding to its VPBlockBases.
2072  bool IsReplicator;
2073 
2074 public:
2076  const std::string &Name = "", bool IsReplicator = false)
2077  : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exiting(Exiting),
2078  IsReplicator(IsReplicator) {
2079  assert(Entry->getPredecessors().empty() && "Entry block has predecessors.");
2080  assert(Exiting->getSuccessors().empty() && "Exit block has successors.");
2081  Entry->setParent(this);
2082  Exiting->setParent(this);
2083  }
2084  VPRegionBlock(const std::string &Name = "", bool IsReplicator = false)
2085  : VPBlockBase(VPRegionBlockSC, Name), Entry(nullptr), Exiting(nullptr),
2086  IsReplicator(IsReplicator) {}
2087 
2088  ~VPRegionBlock() override {
2089  if (Entry) {
2090  VPValue DummyValue;
2091  Entry->dropAllReferences(&DummyValue);
2092  deleteCFG(Entry);
2093  }
2094  }
2095 
2096  /// Method to support type inquiry through isa, cast, and dyn_cast.
2097  static inline bool classof(const VPBlockBase *V) {
2098  return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC;
2099  }
2100 
2101  const VPBlockBase *getEntry() const { return Entry; }
2102  VPBlockBase *getEntry() { return Entry; }
2103 
2104  /// Set \p EntryBlock as the entry VPBlockBase of this VPRegionBlock. \p
2105  /// EntryBlock must have no predecessors.
2106  void setEntry(VPBlockBase *EntryBlock) {
2107  assert(EntryBlock->getPredecessors().empty() &&
2108  "Entry block cannot have predecessors.");
2109  Entry = EntryBlock;
2110  EntryBlock->setParent(this);
2111  }
2112 
2113  // FIXME: DominatorTreeBase is doing 'A->getParent()->front()'. 'front' is a
2114  // specific interface of llvm::Function, instead of using
2115  // GraphTraints::getEntryNode. We should add a new template parameter to
2116  // DominatorTreeBase representing the Graph type.
2117  VPBlockBase &front() const { return *Entry; }
2118 
2119  const VPBlockBase *getExiting() const { return Exiting; }
2120  VPBlockBase *getExiting() { return Exiting; }
2121 
2122  /// Set \p ExitingBlock as the exiting VPBlockBase of this VPRegionBlock. \p
2123  /// ExitingBlock must have no successors.
2124  void setExiting(VPBlockBase *ExitingBlock) {
2125  assert(ExitingBlock->getSuccessors().empty() &&
2126  "Exit block cannot have successors.");
2127  Exiting = ExitingBlock;
2128  ExitingBlock->setParent(this);
2129  }
2130 
2131  /// Returns the pre-header VPBasicBlock of the loop region.
2133  assert(!isReplicator() && "should only get pre-header of loop regions");
2135  }
2136 
2137  /// An indicator whether this region is to generate multiple replicated
2138  /// instances of output IR corresponding to its VPBlockBases.
2139  bool isReplicator() const { return IsReplicator; }
2140 
2141  /// The method which generates the output IR instructions that correspond to
2142  /// this VPRegionBlock, thereby "executing" the VPlan.
2143  void execute(struct VPTransformState *State) override;
2144 
2145  void dropAllReferences(VPValue *NewValue) override;
2146 
2147 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2148  /// Print this VPRegionBlock to \p O (recursively), prefixing all lines with
2149  /// \p Indent. \p SlotTracker is used to print unnamed VPValue's using
2150  /// consequtive numbers.
2151  ///
2152  /// Note that the numbering is applied to the whole VPlan, so printing
2153  /// individual regions is consistent with the whole VPlan printing.
2154  void print(raw_ostream &O, const Twine &Indent,
2155  VPSlotTracker &SlotTracker) const override;
2156  using VPBlockBase::print; // Get the print(raw_stream &O) version.
2157 #endif
2158 };
2159 
2160 //===----------------------------------------------------------------------===//
2161 // GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs //
2162 //===----------------------------------------------------------------------===//
2163 
2164 // The following set of template specializations implement GraphTraits to treat
2165 // any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
2166 // that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
2167 // VPBlockBase is a VPRegionBlock, this specialization provides access to its
2168 // successors/predecessors but not to the blocks inside the region.
2169 
2170 template <> struct GraphTraits<VPBlockBase *> {
2173 
2174  static NodeRef getEntryNode(NodeRef N) { return N; }
2175 
2177  return N->getSuccessors().begin();
2178  }
2179 
2181  return N->getSuccessors().end();
2182  }
2183 };
2184 
2185 template <> struct GraphTraits<const VPBlockBase *> {
2186  using NodeRef = const VPBlockBase *;
2188 
2189  static NodeRef getEntryNode(NodeRef N) { return N; }
2190 
2192  return N->getSuccessors().begin();
2193  }
2194 
2196  return N->getSuccessors().end();
2197  }
2198 };
2199 
2200 // Inverse order specialization for VPBasicBlocks. Predecessors are used instead
2201 // of successors for the inverse traversal.
2202 template <> struct GraphTraits<Inverse<VPBlockBase *>> {
2205 
2206  static NodeRef getEntryNode(Inverse<NodeRef> B) { return B.Graph; }
2207 
2209  return N->getPredecessors().begin();
2210  }
2211 
2213  return N->getPredecessors().end();
2214  }
2215 };
2216 
2217 // The following set of template specializations implement GraphTraits to
2218 // treat VPRegionBlock as a graph and recurse inside its nodes. It's important
2219 // to note that the blocks inside the VPRegionBlock are treated as VPBlockBases
2220 // (i.e., no dyn_cast is performed, VPBlockBases specialization is used), so
2221 // there won't be automatic recursion into other VPBlockBases that turn to be
2222 // VPRegionBlocks.
2223 
2224 template <>
2228 
2229  static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
2230 
2232  return nodes_iterator::begin(N->getEntry());
2233  }
2234 
2236  // df_iterator::end() returns an empty iterator so the node used doesn't
2237  // matter.
2238  return nodes_iterator::end(N);
2239  }
2240 };
2241 
2242 template <>
2245  using GraphRef = const VPRegionBlock *;
2247 
2248  static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
2249 
2251  return nodes_iterator::begin(N->getEntry());
2252  }
2253 
2255  // df_iterator::end() returns an empty iterator so the node used doesn't
2256  // matter.
2257  return nodes_iterator::end(N);
2258  }
2259 };
2260 
2261 template <>
2266 
2268  return N.Graph->getExiting();
2269  }
2270 
2272  return nodes_iterator::begin(N->getExiting());
2273  }
2274 
2276  // df_iterator::end() returns an empty iterator so the node used doesn't
2277  // matter.
2278  return nodes_iterator::end(N);
2279  }
2280 };
2281 
2282 /// Iterator to traverse all successors of a VPBlockBase node. This includes the
2283 /// entry node of VPRegionBlocks. Exit blocks of a region implicitly have their
2284 /// parent region's successors. This ensures all blocks in a region are visited
2285 /// before any blocks in a successor region when doing a reverse post-order
2286 // traversal of the graph.
2287 template <typename BlockPtrTy>
2289  : public iterator_facade_base<VPAllSuccessorsIterator<BlockPtrTy>,
2290  std::forward_iterator_tag, VPBlockBase> {
2291  BlockPtrTy Block;
2292  /// Index of the current successor. For VPBasicBlock nodes, this simply is the
2293  /// index for the successor array. For VPRegionBlock, SuccessorIdx == 0 is
2294  /// used for the region's entry block, and SuccessorIdx - 1 are the indices
2295  /// for the successor array.
2296  size_t SuccessorIdx;
2297 
2298  static BlockPtrTy getBlockWithSuccs(BlockPtrTy Current) {
2299  while (Current && Current->getNumSuccessors() == 0)
2300  Current = Current->getParent();
2301  return Current;
2302  }
2303 
2304  /// Templated helper to dereference successor \p SuccIdx of \p Block. Used by
2305  /// both the const and non-const operator* implementations.
2306  template <typename T1> static T1 deref(T1 Block, unsigned SuccIdx) {
2307  if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
2308  if (SuccIdx == 0)
2309  return R->getEntry();
2310  SuccIdx--;
2311  }
2312 
2313  // For exit blocks, use the next parent region with successors.
2314  return getBlockWithSuccs(Block)->getSuccessors()[SuccIdx];
2315  }
2316 
2317 public:
2318  VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0)
2319  : Block(Block), SuccessorIdx(Idx) {}
2321  : Block(Other.Block), SuccessorIdx(Other.SuccessorIdx) {}
2322 
2324  Block = R.Block;
2325  SuccessorIdx = R.SuccessorIdx;
2326  return *this;
2327  }
2328 
2329  static VPAllSuccessorsIterator end(BlockPtrTy Block) {
2330  BlockPtrTy ParentWithSuccs = getBlockWithSuccs(Block);
2331  unsigned NumSuccessors = ParentWithSuccs
2332  ? ParentWithSuccs->getNumSuccessors()
2333  : Block->getNumSuccessors();
2334 
2335  if (auto *R = dyn_cast<VPRegionBlock>(Block))
2336  return {R, NumSuccessors + 1};
2337  return {Block, NumSuccessors};
2338  }
2339 
2340  bool operator==(const VPAllSuccessorsIterator &R) const {
2341  return Block == R.Block && SuccessorIdx == R.SuccessorIdx;
2342  }
2343 
2344  const VPBlockBase *operator*() const { return deref(Block, SuccessorIdx); }
2345 
2346  BlockPtrTy operator*() { return deref(Block, SuccessorIdx); }
2347 
2349  SuccessorIdx++;
2350  return *this;
2351  }
2352 
2354  VPAllSuccessorsIterator Orig = *this;
2355  SuccessorIdx++;
2356  return Orig;
2357  }
2358 };
2359 
2360 /// Helper for GraphTraits specialization that traverses through VPRegionBlocks.
2361 template <typename BlockTy> class VPBlockRecursiveTraversalWrapper {
2362  BlockTy Entry;
2363 
2364 public:
2366  BlockTy getEntry() { return Entry; }
2367 };
2368 
2369 /// GraphTraits specialization to recursively traverse VPBlockBase nodes,
2370 /// including traversing through VPRegionBlocks. Exit blocks of a region
2371 /// implicitly have their parent region's successors. This ensures all blocks in
2372 /// a region are visited before any blocks in a successor region when doing a
2373 /// reverse post-order traversal of the graph.
2374 template <>
2378 
2379  static NodeRef
2381  return N.getEntry();
2382  }
2383 
2385  return ChildIteratorType(N);
2386  }
2387 
2389  return ChildIteratorType::end(N);
2390  }
2391 };
2392 
2393 template <>
2395  using NodeRef = const VPBlockBase *;
2397 
2398  static NodeRef
2400  return N.getEntry();
2401  }
2402 
2404  return ChildIteratorType(N);
2405  }
2406 
2408  return ChildIteratorType::end(N);
2409  }
2410 };
2411 
2412 /// VPlan models a candidate for vectorization, encoding various decisions take
2413 /// to produce efficient output IR, including which branches, basic-blocks and
2414 /// output IR instructions to generate, and their cost. VPlan holds a
2415 /// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry
2416 /// VPBlock.
2417 class VPlan {
2418  friend class VPlanPrinter;
2419  friend class VPSlotTracker;
2420 
2421  /// Hold the single entry to the Hierarchical CFG of the VPlan.
2422  VPBlockBase *Entry;
2423 
2424  /// Holds the VFs applicable to this VPlan.
2426 
2427  /// Holds the name of the VPlan, for printing.
2428  std::string Name;
2429 
2430  /// Holds all the external definitions created for this VPlan. External
2431  /// definitions must be immutable and hold a pointer to their underlying IR.
2432  DenseMap<Value *, VPValue *> VPExternalDefs;
2433 
2434  /// Represents the trip count of the original loop, for folding
2435  /// the tail.
2436  VPValue *TripCount = nullptr;
2437 
2438  /// Represents the backedge taken count of the original loop, for folding
2439  /// the tail. It equals TripCount - 1.
2440  VPValue *BackedgeTakenCount = nullptr;
2441 
2442  /// Represents the vector trip count.
2443  VPValue VectorTripCount;
2444 
2445  /// Holds a mapping between Values and their corresponding VPValue inside
2446  /// VPlan.
2447  Value2VPValueTy Value2VPValue;
2448 
2449  /// Contains all VPValues that been allocated by addVPValue directly and need
2450  /// to be free when the plan's destructor is called.
2451  SmallVector<VPValue *, 16> VPValuesToFree;
2452 
2453  /// Indicates whether it is safe use the Value2VPValue mapping or if the
2454  /// mapping cannot be used any longer, because it is stale.
2455  bool Value2VPValueEnabled = true;
2456 
2457  /// Values used outside the plan.
2459 
2460 public:
2461  VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {
2462  if (Entry)
2463  Entry->setPlan(this);
2464  }
2465 
2467  clearLiveOuts();
2468 
2469  if (Entry) {
2470  VPValue DummyValue;
2471  for (VPBlockBase *Block : depth_first(Entry))
2472  Block->dropAllReferences(&DummyValue);
2473 
2474  VPBlockBase::deleteCFG(Entry);
2475  }
2476  for (VPValue *VPV : VPValuesToFree)
2477  delete VPV;
2478  if (TripCount)
2479  delete TripCount;
2480  if (BackedgeTakenCount)
2481  delete BackedgeTakenCount;
2482  for (auto &P : VPExternalDefs)
2483  delete P.second;
2484  }
2485 
2486  /// Prepare the plan for execution, setting up the required live-in values.
2487  void prepareToExecute(Value *TripCount, Value *VectorTripCount,
2488  Value *CanonicalIVStartValue, VPTransformState &State);
2489 
2490  /// Generate the IR code for this VPlan.
2491  void execute(struct VPTransformState *State);
2492 
2493  VPBlockBase *getEntry() { return Entry; }
2494  const VPBlockBase *getEntry() const { return Entry; }
2495 
2497  Entry = Block;
2498  Block->setPlan(this);
2499  return Entry;
2500  }
2501 
2502  /// The trip count of the original loop.
2504  if (!TripCount)
2505  TripCount = new VPValue();
2506  return TripCount;
2507  }
2508 
2509  /// The backedge taken count of the original loop.
2511  if (!BackedgeTakenCount)
2512  BackedgeTakenCount = new VPValue();
2513  return BackedgeTakenCount;
2514  }
2515 
2516  /// The vector trip count.
2517  VPValue &getVectorTripCount() { return VectorTripCount; }
2518 
2519  /// Mark the plan to indicate that using Value2VPValue is not safe any
2520  /// longer, because it may be stale.
2521  void disableValue2VPValue() { Value2VPValueEnabled = false; }
2522 
2523  void addVF(ElementCount VF) { VFs.insert(VF); }
2524 
2525  bool hasVF(ElementCount VF) { return VFs.count(VF); }
2526 
2527  const std::string &getName() const { return Name; }
2528 
2529  void setName(const Twine &newName) { Name = newName.str(); }
2530 
2531  /// Get the existing or add a new external definition for \p V.
2533  auto I = VPExternalDefs.insert({V, nullptr});
2534  if (I.second)
2535  I.first->second = new VPValue(V);
2536  return I.first->second;
2537  }
2538 
2539  void addVPValue(Value *V) {
2540  assert(Value2VPValueEnabled &&
2541  "IR value to VPValue mapping may be out of date!");
2542  assert(V && "Trying to add a null Value to VPlan");
2543  assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
2544  VPValue *VPV = new VPValue(V);
2545  Value2VPValue[V] = VPV;
2546  VPValuesToFree.push_back(VPV);
2547  }
2548 
2549  void addVPValue(Value *V, VPValue *VPV) {
2550  assert(Value2VPValueEnabled && "Value2VPValue mapping may be out of date!");
2551  assert(V && "Trying to add a null Value to VPlan");
2552  assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
2553  Value2VPValue[V] = VPV;
2554  }
2555 
2556  /// Returns the VPValue for \p V. \p OverrideAllowed can be used to disable
2557  /// checking whether it is safe to query VPValues using IR Values.
2558  VPValue *getVPValue(Value *V, bool OverrideAllowed = false) {
2559  assert((OverrideAllowed || isa<Constant>(V) || Value2VPValueEnabled) &&
2560  "Value2VPValue mapping may be out of date!");
2561  assert(V && "Trying to get the VPValue of a null Value");
2562  assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
2563  return Value2VPValue[V];
2564  }
2565 
2566  /// Gets the VPValue or adds a new one (if none exists yet) for \p V. \p
2567  /// OverrideAllowed can be used to disable checking whether it is safe to
2568  /// query VPValues using IR Values.
2569  VPValue *getOrAddVPValue(Value *V, bool OverrideAllowed = false) {
2570  assert((OverrideAllowed || isa<Constant>(V) || Value2VPValueEnabled) &&
2571  "Value2VPValue mapping may be out of date!");
2572  assert(V && "Trying to get or add the VPValue of a null Value");
2573  if (!Value2VPValue.count(V))
2574  addVPValue(V);
2575  return getVPValue(V);
2576  }
2577 
2579  assert(Value2VPValueEnabled &&
2580  "IR value to VPValue mapping may be out of date!");
2581  Value2VPValue.erase(V);
2582  }
2583 
2584 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2585  /// Print this VPlan to \p O.
2586  void print(raw_ostream &O) const;
2587 
2588  /// Print this VPlan in DOT format to \p O.
2589  void printDOT(raw_ostream &O) const;
2590 
2591  /// Dump the plan to stderr (for debugging).
2592  LLVM_DUMP_METHOD void dump() const;
2593 #endif
2594 
2595  /// Returns a range mapping the values the range \p Operands to their
2596  /// corresponding VPValues.
2599  std::function<VPValue *(Value *)> Fn = [this](Value *Op) {
2600  return getOrAddVPValue(Op);
2601  };
2602  return map_range(Operands, Fn);
2603  }
2604 
2605  /// Returns true if \p VPV is uniform after vectorization.
2607  auto RepR = dyn_cast_or_null<VPReplicateRecipe>(VPV->getDef());
2608  return !VPV->getDef() || (RepR && RepR->isUniform());
2609  }
2610 
2611  /// Returns the VPRegionBlock of the vector loop.
2613  return cast<VPRegionBlock>(getEntry()->getSingleSuccessor());
2614  }
2616  return cast<VPRegionBlock>(getEntry()->getSingleSuccessor());
2617  }
2618 
2619  /// Returns the canonical induction recipe of the vector loop.
2622  if (EntryVPBB->empty()) {
2623  // VPlan native path.
2624  EntryVPBB = cast<VPBasicBlock>(EntryVPBB->getSingleSuccessor());
2625  }
2626  return cast<VPCanonicalIVPHIRecipe>(&*EntryVPBB->begin());
2627  }
2628 
2629  void addLiveOut(PHINode *PN, VPValue *V);
2630 
2631  void clearLiveOuts() {
2632  for (auto &KV : LiveOuts)
2633  delete KV.second;
2634  LiveOuts.clear();
2635  }
2636 
2638  delete LiveOuts[PN];
2639  LiveOuts.erase(PN);
2640  }
2641 
2643  return LiveOuts;
2644  }
2645 
2646 private:
2647  /// Add to the given dominator tree the header block and every new basic block
2648  /// that was created between it and the latch block, inclusive.
2649  static void updateDominatorTree(DominatorTree *DT, BasicBlock *LoopLatchBB,
2650  BasicBlock *LoopPreHeaderBB,
2651  BasicBlock *LoopExitBB);
2652 };
2653 
2654 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2655 /// VPlanPrinter prints a given VPlan to a given output stream. The printing is
2656 /// indented and follows the dot format.
2658  raw_ostream &OS;
2659  const VPlan &Plan;
2660  unsigned Depth = 0;
2661  unsigned TabWidth = 2;
2662  std::string Indent;
2663  unsigned BID = 0;
2665 
2667 
2668  /// Handle indentation.
2669  void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); }
2670 
2671  /// Print a given \p Block of the Plan.
2672  void dumpBlock(const VPBlockBase *Block);
2673 
2674  /// Print the information related to the CFG edges going out of a given
2675  /// \p Block, followed by printing the successor blocks themselves.
2676  void dumpEdges(const VPBlockBase *Block);
2677 
2678  /// Print a given \p BasicBlock, including its VPRecipes, followed by printing
2679  /// its successor blocks.
2680  void dumpBasicBlock(const VPBasicBlock *BasicBlock);
2681 
2682  /// Print a given \p Region of the Plan.
2683  void dumpRegion(const VPRegionBlock *Region);
2684 
2685  unsigned getOrCreateBID(const VPBlockBase *Block) {
2686  return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++;
2687  }
2688 
2689  Twine getOrCreateName(const VPBlockBase *Block);
2690 
2691  Twine getUID(const VPBlockBase *Block);
2692 
2693  /// Print the information related to a CFG edge between two VPBlockBases.
2694  void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden,
2695  const Twine &Label);
2696 
2697 public:
2699  : OS(O), Plan(P), SlotTracker(&P) {}
2700 
2701  LLVM_DUMP_METHOD void dump();
2702 };
2703 
2705  const Value *V;
2706 
2707  VPlanIngredient(const Value *V) : V(V) {}
2708 
2709  void print(raw_ostream &O) const;
2710 };
2711 
2713  I.print(OS);
2714  return OS;
2715 }
2716 
2717 inline raw_ostream &operator<<(raw_ostream &OS, const VPlan &Plan) {
2718  Plan.print(OS);
2719  return OS;
2720 }
2721 #endif
2722 
2723 //===----------------------------------------------------------------------===//
2724 // VPlan Utilities
2725 //===----------------------------------------------------------------------===//
2726 
2727 /// Class that provides utilities for VPBlockBases in VPlan.
2729 public:
2730  VPBlockUtils() = delete;
2731 
2732  /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
2733  /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
2734  /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's
2735  /// successors are moved from \p BlockPtr to \p NewBlock. \p NewBlock must
2736  /// have neither successors nor predecessors.
2737  static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
2738  assert(NewBlock->getSuccessors().empty() &&
2739  NewBlock->getPredecessors().empty() &&
2740  "Can't insert new block with predecessors or successors.");
2741  NewBlock->setParent(BlockPtr->getParent());
2742  SmallVector<VPBlockBase *> Succs(BlockPtr->successors());
2743  for (VPBlockBase *Succ : Succs) {
2744  disconnectBlocks(BlockPtr, Succ);
2745  connectBlocks(NewBlock, Succ);
2746  }
2747  connectBlocks(BlockPtr, NewBlock);
2748  }
2749 
2750  /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
2751  /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
2752  /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
2753  /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
2754  /// and \p IfTrue and \p IfFalse must have neither successors nor
2755  /// predecessors.
2756  static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
2757  VPBlockBase *BlockPtr) {
2758  assert(IfTrue->getSuccessors().empty() &&
2759  "Can't insert IfTrue with successors.");
2760  assert(IfFalse->getSuccessors().empty() &&
2761  "Can't insert IfFalse with successors.");
2762  BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
2763  IfTrue->setPredecessors({BlockPtr});
2764  IfFalse->setPredecessors({BlockPtr});
2765  IfTrue->setParent(BlockPtr->getParent());
2766  IfFalse->setParent(BlockPtr->getParent());
2767  }
2768 
2769  /// Connect VPBlockBases \p From and \p To bi-directionally. Append \p To to
2770  /// the successors of \p From and \p From to the predecessors of \p To. Both
2771  /// VPBlockBases must have the same parent, which can be null. Both
2772  /// VPBlockBases can be already connected to other VPBlockBases.
2774  assert((From->getParent() == To->getParent()) &&
2775  "Can't connect two block with different parents");
2776  assert(From->getNumSuccessors() < 2 &&
2777  "Blocks can't have more than two successors.");
2778  From->appendSuccessor(To);
2779  To->appendPredecessor(From);
2780  }
2781 
2782  /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
2783  /// from the successors of \p From and \p From from the predecessors of \p To.
2785  assert(To && "Successor to disconnect is null.");
2786  From->removeSuccessor(To);
2787  To->removePredecessor(From);
2788  }
2789 
2790  /// Try to merge \p Block into its single predecessor, if \p Block is a
2791  /// VPBasicBlock and its predecessor has a single successor. Returns a pointer
2792  /// to the predecessor \p Block was merged into or nullptr otherwise.
2794  auto *VPBB = dyn_cast<VPBasicBlock>(Block);
2795  auto *PredVPBB =
2796  dyn_cast_or_null<VPBasicBlock>(Block->getSinglePredecessor());
2797  if (!VPBB || !PredVPBB || PredVPBB->getNumSuccessors() != 1)
2798  return nullptr;
2799 
2800  for (VPRecipeBase &R : make_early_inc_range(*VPBB))
2801  R.moveBefore(*PredVPBB, PredVPBB->end());
2802  VPBlockUtils::disconnectBlocks(PredVPBB, VPBB);
2803  auto *ParentRegion = cast<VPRegionBlock>(Block->getParent());
2804  if (ParentRegion->getExiting() == Block)
2805  ParentRegion->setExiting(PredVPBB);
2806  SmallVector<VPBlockBase *> Successors(Block->successors());
2807  for (auto *Succ : Successors) {
2808  VPBlockUtils::disconnectBlocks(Block, Succ);
2809  VPBlockUtils::connectBlocks(PredVPBB, Succ);
2810  }
2811  delete Block;
2812  return PredVPBB;
2813  }
2814 
2815  /// Return an iterator range over \p Range which only includes \p BlockTy
2816  /// blocks. The accesses are casted to \p BlockTy.
2817  template <typename BlockTy, typename T>
2818  static auto blocksOnly(const T &Range) {
2819  // Create BaseTy with correct const-ness based on BlockTy.
2820  using BaseTy =
2821  typename std::conditional<std::is_const<BlockTy>::value,
2823 
2824  // We need to first create an iterator range over (const) BlocktTy & instead
2825  // of (const) BlockTy * for filter_range to work properly.
2826  auto Mapped =
2827  map_range(Range, [](BaseTy *Block) -> BaseTy & { return *Block; });
2828  auto Filter = make_filter_range(
2829  Mapped, [](BaseTy &Block) { return isa<BlockTy>(&Block); });
2830  return map_range(Filter, [](BaseTy &Block) -> BlockTy * {
2831  return cast<BlockTy>(&Block);
2832  });
2833  }
2834 };
2835 
2838  InterleaveGroupMap;
2839 
2840  /// Type for mapping of instruction based interleave groups to VPInstruction
2841  /// interleave groups
2844 
2845  /// Recursively \p Region and populate VPlan based interleave groups based on
2846  /// \p IAI.
2847  void visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New,
2848  InterleavedAccessInfo &IAI);
2849  /// Recursively traverse \p Block and populate VPlan based interleave groups
2850  /// based on \p IAI.
2851  void visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
2852  InterleavedAccessInfo &IAI);
2853 
2854 public:
2856 
2859  // Avoid releasing a pointer twice.
2860  for (auto &I : InterleaveGroupMap)
2861  DelSet.insert(I.second);
2862  for (auto *Ptr : DelSet)
2863  delete Ptr;
2864  }
2865 
2866  /// Get the interleave group that \p Instr belongs to.
2867  ///
2868  /// \returns nullptr if doesn't have such group.
2871  return InterleaveGroupMap.lookup(Instr);
2872  }
2873 };
2874 
2875 /// Class that maps (parts of) an existing VPlan to trees of combined
2876 /// VPInstructions.
2877 class VPlanSlp {
2878  enum class OpMode { Failed, Load, Opcode };
2879 
2880  /// A DenseMapInfo implementation for using SmallVector<VPValue *, 4> as
2881  /// DenseMap keys.
2882  struct BundleDenseMapInfo {
2883  static SmallVector<VPValue *, 4> getEmptyKey() {
2884  return {reinterpret_cast<VPValue *>(-1)};
2885  }
2886 
2887  static SmallVector<VPValue *, 4> getTombstoneKey() {
2888  return {reinterpret_cast<VPValue *>(-2)};
2889  }
2890 
2891  static unsigned getHashValue(const SmallVector<VPValue *, 4> &V) {
2892  return static_cast<unsigned>(hash_combine_range(V.begin(), V.end()));
2893  }
2894 
2895  static bool isEqual(const SmallVector<VPValue *, 4> &LHS,
2896  const SmallVector<VPValue *, 4> &RHS) {
2897  return LHS == RHS;
2898  }
2899  };
2900 
2901  /// Mapping of values in the original VPlan to a combined VPInstruction.
2902  DenseMap<SmallVector<VPValue *, 4>, VPInstruction *, BundleDenseMapInfo>
2903  BundleToCombined;
2904 
2906 
2907  /// Basic block to operate on. For now, only instructions in a single BB are
2908  /// considered.
2909  const VPBasicBlock &BB;
2910 
2911  /// Indicates whether we managed to combine all visited instructions or not.
2912  bool CompletelySLP = true;
2913 
2914  /// Width of the widest combined bundle in bits.
2915  unsigned WidestBundleBits = 0;
2916 
2917  using MultiNodeOpTy =
2918  typename std::pair<VPInstruction *, SmallVector<VPValue *, 4>>;
2919 
2920  // Input operand bundles for the current multi node. Each multi node operand
2921  // bundle contains values not matching the multi node's opcode. They will
2922  // be reordered in reorderMultiNodeOps, once we completed building a
2923  // multi node.
2924  SmallVector<MultiNodeOpTy, 4> MultiNodeOps;
2925 
2926  /// Indicates whether we are building a multi node currently.
2927  bool MultiNodeActive = false;
2928 
2929  /// Check if we can vectorize Operands together.
2930  bool areVectorizable(ArrayRef<VPValue *> Operands) const;
2931 
2932  /// Add combined instruction \p New for the bundle \p Operands.
2933  void addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New);
2934 
2935  /// Indicate we hit a bundle we failed to combine. Returns nullptr for now.
2936  VPInstruction *markFailed();
2937 
2938  /// Reorder operands in the multi node to maximize sequential memory access
2939  /// and commutative operations.
2940  SmallVector<MultiNodeOpTy, 4> reorderMultiNodeOps();
2941 
2942  /// Choose the best candidate to use for the lane after \p Last. The set of
2943  /// candidates to choose from are values with an opcode matching \p Last's
2944  /// or loads consecutive to \p Last.
2945  std::pair<OpMode, VPValue *> getBest(OpMode Mode, VPValue *Last,
2946  SmallPtrSetImpl<VPValue *> &Candidates,
2948 
2949 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2950  /// Print bundle \p Values to dbgs().
2951  void dumpBundle(ArrayRef<VPValue *> Values);
2952 #endif
2953 
2954 public:
2956 
2957  ~VPlanSlp() = default;
2958 
2959  /// Tries to build an SLP tree rooted at \p Operands and returns a
2960  /// VPInstruction combining \p Operands, if they can be combined.
2962 
2963  /// Return the width of the widest combined bundle in bits.
2964  unsigned getWidestBundleBits() const { return WidestBundleBits; }
2965 
2966  /// Return true if all visited instruction can be combined.
2967  bool isCompletelySLP() const { return CompletelySLP; }
2968 };
2969 
2970 namespace vputils {
2971 
2972 /// Returns true if only the first lane of \p Def is used.
2974 
2975 /// Get or create a VPValue that corresponds to the expansion of \p Expr. If \p
2976 /// Expr is a SCEVConstant or SCEVUnknown, return a VPValue wrapping the live-in
2977 /// value. Otherwise return a VPExpandSCEVRecipe to expand \p Expr. If \p Plan's
2978 /// pre-header already contains a recipe expanding \p Expr, return it. If not,
2979 /// create a new one.
2980 VPValue *getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr,
2981  ScalarEvolution &SE);
2982 } // end namespace vputils
2983 
2984 } // end namespace llvm
2985 
2986 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
llvm::VPBasicBlock::getRecipeList
RecipeListTy & getRecipeList()
Returns a reference to the list of recipes.
Definition: VPlan.h:1985
llvm::VPRegionBlock::front
VPBlockBase & front() const
Definition: VPlan.h:2117
llvm::VPInstruction::getOpcode
unsigned getOpcode() const
Definition: VPlan.h:810
i
i
Definition: README.txt:29
llvm::VPWidenGEPRecipe::~VPWidenGEPRecipe
~VPWidenGEPRecipe() override=default
llvm::VFRange::VFRange
VFRange(const ElementCount &Start, const ElementCount &End)
Definition: VPlan.h:89
llvm::VPUser::getVPUserID
VPUserID getVPUserID() const
Definition: VPlanValue.h:248
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:662
llvm::VPBlockBase::getSinglePredecessor
VPBlockBase * getSinglePredecessor() const
Definition: VPlan.h:469
llvm::VPBlockUtils::tryToMergeBlockIntoPredecessor
static VPBasicBlock * tryToMergeBlockIntoPredecessor(VPBlockBase *Block)
Try to merge Block into its single predecessor, if Block is a VPBasicBlock and its predecessor has a ...
Definition: VPlan.h:2793
llvm::VPExpandSCEVRecipe::getSCEV
const SCEV * getSCEV() const
Definition: VPlan.h:1784
llvm::VPReductionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1425
llvm::VPBlockBase::getPlan
VPlan * getPlan()
Definition: VPlan.cpp:135
llvm::VPWidenMemoryInstructionRecipe::getMask
VPValue * getMask() const
Return the mask used by this recipe.
Definition: VPlan.h:1713
llvm::VPAllSuccessorsIterator::operator*
const VPBlockBase * operator*() const
Definition: VPlan.h:2344
llvm::VPWidenIntOrFpInductionRecipe::getStepValue
VPValue * getStepValue()
Returns the step value of the induction.
Definition: VPlan.h:1049
llvm::VPWidenMemoryInstructionRecipe::VPWidenMemoryInstructionRecipe
VPWidenMemoryInstructionRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask, bool Consecutive, bool Reverse)
Definition: VPlan.h:1683
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:1347
llvm::VPlan::execute
void execute(struct VPTransformState *State)
Generate the IR code for this VPlan.
Definition: VPlan.cpp:969
llvm::VPlanIngredient::print
void print(raw_ostream &O) const
Definition: VPlan.cpp:1259
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:60
llvm::VPlanSlp
Class that maps (parts of) an existing VPlan to trees of combined VPInstructions.
Definition: VPlan.h:2877
llvm::VPBlockRecursiveTraversalWrapper::getEntry
BlockTy getEntry()
Definition: VPlan.h:2366
llvm::VPWidenMemoryInstructionRecipe::onlyFirstLaneUsed
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:1744
llvm::GraphTraits< const VPBlockBase * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: VPlan.h:2189
llvm::VPWidenSelectRecipe::~VPWidenSelectRecipe
~VPWidenSelectRecipe() override=default
llvm::VPWidenSelectRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:951
llvm::VPLane::VPLane
VPLane(unsigned Lane, Kind LaneKind)
Definition: VPlan.h:129
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:494
llvm::VPBlendRecipe::getIncomingValue
VPValue * getIncomingValue(unsigned Idx) const
Return incoming value number Idx.
Definition: VPlan.h:1350
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:724
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
FMF.h
llvm::VPRecipeBase::getUnderlyingInstr
Instruction * getUnderlyingInstr()
Returns the underlying instruction, if the recipe is a VPValue or nullptr otherwise.
Definition: VPlan.h:687
llvm::VPLiveOut::usesScalars
bool usesScalars(const VPValue *Op) const override
Returns true if the VPLiveOut uses scalars of operand Op.
Definition: VPlan.h:616
llvm::VPWidenCallRecipe::~VPWidenCallRecipe
~VPWidenCallRecipe() override=default
llvm::GraphTraits< VPBlockBase * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: VPlan.h:2174
llvm::VPlanIngredient::VPlanIngredient
VPlanIngredient(const Value *V)
Definition: VPlan.h:2707
llvm::VPBlockBase::dropAllReferences
virtual void dropAllReferences(VPValue *NewValue)=0
Replace all operands of VPUsers in the block with NewValue and also replaces all uses of VPValues def...
llvm::VPCanonicalIVPHIRecipe
Canonical scalar induction phi of the vector loop.
Definition: VPlan.h:1791
llvm::VPWidenPHIRecipe::VPWidenPHIRecipe
VPWidenPHIRecipe(PHINode *Phi, VPValue *Start=nullptr)
Create a new VPWidenPHIRecipe for Phi with start value Start.
Definition: VPlan.h:1196
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:657
llvm::VPLane::getFirstLane
static VPLane getFirstLane()
Definition: VPlan.h:131
Optional.h
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:1541
llvm::VPPredInstPHIRecipe::execute
void execute(VPTransformState &State) override
Generates phi nodes for live-outs as needed to retain SSA form.
Definition: LoopVectorize.cpp:9846
llvm::VPDef::VPValue
friend class VPValue
Definition: VPlanValue.h:312
llvm::VPIteration::VPIteration
VPIteration(unsigned Part, const VPLane &Lane)
Definition: VPlan.h:193
llvm::VPBlendRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1405
llvm::VPBlockBase::getEnclosingBlockWithPredecessors
VPBlockBase * getEnclosingBlockWithPredecessors()
Definition: VPlan.cpp:183
llvm::VPAllSuccessorsIterator::operator*
BlockPtrTy operator*()
Definition: VPlan.h:2346
llvm::VPInstruction::classof
static bool classof(const VPUser *U)
Extra classof implementations to allow directly casting from VPUser -> VPInstruction.
Definition: VPlan.h:802
llvm::VPBasicBlock::back
const VPRecipeBase & back() const
Definition: VPlan.h:1981
llvm::VPLiveOut::getPhi
PHINode * getPhi() const
Definition: VPlan.h:622
llvm::VPBlockBase::isLegalToHoistInto
bool isLegalToHoistInto()
Return true if it is legal to hoist instructions into this block.
Definition: VPlan.h:560
llvm::VPBlockBase::getName
const std::string & getName() const
Definition: VPlan.h:419
llvm::VPlan::disableValue2VPValue
void disableValue2VPValue()
Mark the plan to indicate that using Value2VPValue is not safe any longer, because it may be stale.
Definition: VPlan.h:2521
llvm::VPTransformState::Builder
IRBuilderBase & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Definition: VPlan.h:333
llvm::VPlan::getOrAddVPValue
VPValue * getOrAddVPValue(Value *V, bool OverrideAllowed=false)
Gets the VPValue or adds a new one (if none exists yet) for V.
Definition: VPlan.h:2569
llvm::ElementCount
Definition: TypeSize.h:404
llvm::VPWidenCanonicalIVRecipe::VPWidenCanonicalIVRecipe
VPWidenCanonicalIVRecipe(VPCanonicalIVPHIRecipe *CanonicalIV)
Definition: VPlan.h:1838
llvm::VPBasicBlock
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:1938
llvm::VPScalarIVStepsRecipe::classof
static bool classof(const VPUser *U)
Extra classof implementations to allow directly casting from VPUser -> VPScalarIVStepsRecipe.
Definition: VPlan.h:1902
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:199
llvm::VPBranchOnMaskRecipe::usesScalars
bool usesScalars(const VPValue *Op) const override
Returns true if the recipe uses scalars of operand Op.
Definition: VPlan.h:1614
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::VPWidenPHIRecipe
A recipe for handling header phis that are widened in the vector loop.
Definition: VPlan.h:1190
BlockTy
std::pair< BasicBlock *, unsigned > BlockTy
A pair of (basic block, score).
Definition: HotColdSplitting.cpp:398
llvm::VPValue::VPVInstructionSC
@ VPVInstructionSC
Definition: VPlanValue.h:93
llvm::VPHeaderPHIRecipe
A pure virtual base class for all recipes modeling header phis, including phis for first order recurr...
Definition: VPlan.h:1084
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:897
llvm::VPWidenIntOrFpInductionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1314
llvm::VPValue::getLiveInIRValue
Value * getLiveInIRValue()
Returns the underlying IR value, if this VPValue is defined outside the scope of VPlan.
Definition: VPlanValue.h:187
llvm::Type::getScalarType
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:309
llvm::VPlanPrinter::dump
LLVM_DUMP_METHOD void dump()
Definition: VPlan.cpp:1150
llvm::VPPredInstPHIRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1636
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::VPCanonicalIVPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1505
llvm::VPWidenIntOrFpInductionRecipe::~VPWidenIntOrFpInductionRecipe
~VPWidenIntOrFpInductionRecipe() override=default
llvm::VPInterleaveRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: LoopVectorize.cpp:9178
ilist.h
llvm::VPInstruction::SLPStore
@ SLPStore
Definition: VPlan.h:754
llvm::VPDef::getVPSingleValue
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
Definition: VPlanValue.h:386
llvm::VPBasicBlock::end
const_iterator end() const
Definition: VPlan.h:1970
llvm::VPTransformState::get
Value * get(VPValue *Def, unsigned Part)
Get the generated Value for a given VPValue and a given Part.
Definition: LoopVectorize.cpp:10069
llvm::VPlan::getOrAddExternalDef
VPValue * getOrAddExternalDef(Value *V)
Get the existing or add a new external definition for V.
Definition: VPlan.h:2532
llvm::enumerate
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:2057
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:456
llvm::ilist_node_with_parent
An ilist node that can access its parent list.
Definition: ilist_node.h:257
llvm::VPInterleavedAccessInfo
Definition: VPlan.h:2836
llvm::VPBranchOnMaskRecipe::execute
void execute(VPTransformState &State) override
Generate the extraction of the appropriate bit from the block mask and the conditional branch.
Definition: LoopVectorize.cpp:9820
llvm::VPBlockBase::VPBlockBase
VPBlockBase(const unsigned char SC, const std::string &N)
Definition: VPlan.h:405
llvm::GraphTraits< VPRegionBlock * >::nodes_begin
static nodes_iterator nodes_begin(GraphRef N)
Definition: VPlan.h:2231
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::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::VPInterleaveRecipe::VPInterleaveRecipe
VPInterleaveRecipe(const InterleaveGroup< Instruction > *IG, VPValue *Addr, ArrayRef< VPValue * > StoredValues, VPValue *Mask)
Definition: VPlan.h:1385
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::VPWidenPointerInductionRecipe::onlyScalarsGenerated
bool onlyScalarsGenerated(ElementCount VF)
Returns true if only scalar values will be generated.
Definition: VPlan.cpp:1513
llvm::GraphTraits< const VPBlockBase * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:2195
MapVector.h
llvm::SmallDenseMap
Definition: DenseMap.h:882
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::GraphTraits< VPBlockRecursiveTraversalWrapper< VPBlockBase * > >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:2384
llvm::VPInstruction::setFastMathFlags
void setFastMathFlags(FastMathFlags FMFNew)
Set the fast-math flags.
Definition: VPlan.cpp:887
llvm::VPReductionPHIRecipe
A recipe for handling reduction phis.
Definition: VPlan.h:1268
llvm::VPInstruction::CanonicalIVIncrement
@ CanonicalIVIncrement
Definition: VPlan.h:756
llvm::VPWidenIntOrFpInductionRecipe::needsVectorIV
bool needsVectorIV() const
Returns true if a vector phi needs to be created for the induction.
Definition: VPlan.h:1077
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:166
llvm::VPTransformState::set
void set(VPValue *Def, Value *V, const VPIteration &Instance)
Set the generated scalar V for Def and the given Instance.
Definition: VPlan.h:275
llvm::iplist_impl< simple_ilist< VPRecipeBase, Options... >, ilist_traits< VPRecipeBase > >::const_reverse_iterator
base_list_type::const_reverse_iterator const_reverse_iterator
Definition: ilist.h:182
llvm::VPInterleaveRecipe::~VPInterleaveRecipe
~VPInterleaveRecipe() override=default
llvm::VPRegionBlock::getPreheaderVPBB
VPBasicBlock * getPreheaderVPBB()
Returns the pre-header VPBasicBlock of the loop region.
Definition: VPlan.h:2132
llvm::VPRecipeBase::getUnderlyingInstr
const Instruction * getUnderlyingInstr() const
Definition: VPlan.h:690
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:304
llvm::VPTransformState::CFGState::getPreheaderBBFor
BasicBlock * getPreheaderBBFor(VPRecipeBase *R)
Returns the BasicBlock* mapped to the pre-header of the loop region containing R.
Definition: VPlan.cpp:226
llvm::VPBlendRecipe::execute
void execute(VPTransformState &State) override
Generate the phi/select nodes.
Definition: LoopVectorize.cpp:9694
llvm::VPReductionRecipe::VPReductionRecipe
VPReductionRecipe(const RecurrenceDescriptor *R, Instruction *I, VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp, const TargetTransformInfo *TTI)
Definition: VPlan.h:1467
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::VPBlockBase::~VPBlockBase
virtual ~VPBlockBase()=default
llvm::VPPredInstPHIRecipe
VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when control converges back from ...
Definition: VPlan.h:1626
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:339
llvm::VPLane::getKind
Kind getKind() const
Returns the Kind of lane offset.
Definition: VPlan.h:157
llvm::VPlan::getCanonicalIV
VPCanonicalIVPHIRecipe * getCanonicalIV()
Returns the canonical induction recipe of the vector loop.
Definition: VPlan.h:2620
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
DenseMap.h
llvm::VPWidenIntOrFpInductionRecipe::getTruncInst
TruncInst * getTruncInst()
Returns the first defined value as TruncInst, if it is one or nullptr otherwise.
Definition: VPlan.h:1054
llvm::VPIteration::isFirstIteration
bool isFirstIteration() const
Definition: VPlan.h:195
llvm::VPlanPtr
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:98
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::GraphTraits< Inverse< VPRegionBlock * > >::getEntryNode
static NodeRef getEntryNode(Inverse< GraphRef > N)
Definition: VPlan.h:2267
llvm::VPBlockBase::getHierarchicalPredecessors
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:509
llvm::VPBasicBlock::getTerminator
VPRecipeBase * getTerminator()
If the block has multiple successors, return the branch recipe terminating the block.
Definition: VPlan.cpp:413
T1
#define T1
Definition: Mips16ISelLowering.cpp:340
llvm::VPInstruction::BranchOnCond
@ BranchOnCond
Definition: VPlan.h:759
llvm::VPInterleaveRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1405
llvm::VPBlockUtils::insertTwoBlocksAfter
static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBases IfTrue and IfFalse after BlockPtr.
Definition: VPlan.h:2756
llvm::VPWidenIntOrFpInductionRecipe::getScalarType
const Type * getScalarType() const
Returns the scalar type of the induction.
Definition: VPlan.h:1071
llvm::VPBlockUtils
Class that provides utilities for VPBlockBases in VPlan.
Definition: VPlan.h:2728
llvm::Optional
Definition: APInt.h:33
llvm::VPUser::op_begin
operand_iterator op_begin()
Definition: VPlanValue.h:277
llvm::VPScalarIVStepsRecipe::execute
void execute(VPTransformState &State) override
Generate the scalarized versions of the phi node as needed by their users.
Definition: LoopVectorize.cpp:9635
llvm::DenseMapBase::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:147
llvm::VPlan::getEntry
const VPBlockBase * getEntry() const
Definition: VPlan.h:2494
llvm::VPWidenIntOrFpInductionRecipe::VPWidenIntOrFpInductionRecipe
VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, VPValue *Step, const InductionDescriptor &IndDesc, TruncInst *Trunc, bool NeedsVectorIV)
Definition: VPlan.h:1020
llvm::VPWidenMemoryInstructionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1478
llvm::VPWidenPHIRecipe::~VPWidenPHIRecipe
~VPWidenPHIRecipe() override=default
llvm::mapped_iterator
Definition: STLExtras.h:298
llvm::MapVector
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::VPReplicateRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1533
llvm::VPWidenCallRecipe
A recipe for widening Call instructions.
Definition: VPlan.h:909
llvm::VPPredInstPHIRecipe::usesScalars
bool usesScalars(const VPValue *Op) const override
Returns true if the recipe uses scalars of operand Op.
Definition: VPlan.h:1650
llvm::VPBasicBlock::isExiting
bool isExiting() const
Returns true if the block is exiting it's parent region.
Definition: VPlan.cpp:425
llvm::VPWidenMemoryInstructionRecipe::VPWidenMemoryInstructionRecipe
VPWidenMemoryInstructionRecipe(StoreInst &Store, VPValue *Addr, VPValue *StoredValue, VPValue *Mask, bool Consecutive, bool Reverse)
Definition: VPlan.h:1692
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:119
llvm::VPReplicateRecipe::onlyFirstLaneUsed
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:1561
llvm::VPUser::operands
operand_range operands()
Definition: VPlanValue.h:281
llvm::VPUser::VPUserID
VPUserID
Subclass identifier (for isa/dyn_cast).
Definition: VPlanValue.h:209
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::VPScalarIVStepsRecipe::classof
static bool classof(const VPRecipeBase *R)
Definition: VPlan.h:1906
llvm::isPowerOf2_32
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:491
llvm::VPRegionBlock::getEntry
const VPBlockBase * getEntry() const
Definition: VPlan.h:2101
llvm::VPAllSuccessorsIterator
Iterator to traverse all successors of a VPBlockBase node.
Definition: VPlan.h:2288
llvm::FastMathFlags
Convenience struct for specifying and reasoning about fast-math flags.
Definition: FMF.h:21
llvm::VPTransformState::hasScalarValue
bool hasScalarValue(VPValue *Def, VPIteration Instance)
Definition: VPlan.h:248
llvm::VPValue::VPVWidenSC
@ VPVWidenSC
Definition: VPlanValue.h:97
llvm::VPInstruction::SLPLoad
@ SLPLoad
Definition: VPlan.h:753
llvm::VPInstruction::mayWriteToMemory
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: VPlan.h:827
VPlanValue.h
llvm::VPReplicateRecipe::isPacked
bool isPacked() const
Definition: VPlan.h:1556
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:298
llvm::GraphTraits< VPBlockRecursiveTraversalWrapper< const VPBlockBase * > >::getEntryNode
static NodeRef getEntryNode(VPBlockRecursiveTraversalWrapper< const VPBlockBase * > N)
Definition: VPlan.h:2399
llvm::VPBasicBlock::getEnclosingLoopRegion
VPRegionBlock * getEnclosingLoopRegion()
Definition: VPlan.cpp:374
llvm::iplist
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:391
llvm::VPReductionRecipe
A recipe to represent inloop reduction operations, performing a reduction on a vector operand into a ...
Definition: VPlan.h:1460
llvm::VPReductionPHIRecipe::~VPReductionPHIRecipe
~VPReductionPHIRecipe() override=default
llvm::isEqual
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)
Definition: GCNRegPressure.cpp:55
llvm::VPScalarIVStepsRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1897
llvm::VPScalarIVStepsRecipe::isCanonical
bool isCanonical() const
Returns true if the induction is canonical, i.e.
Definition: VPlan.cpp:1350
llvm::VPValue::users
user_range users()
Definition: VPlanValue.h:162
DepthFirstIterator.h
llvm::VPWidenPHIRecipe::execute
void execute(VPTransformState &State) override
Generate the phi/select nodes.
Definition: VPlan.cpp:1683
llvm::VPBlockBase::execute
virtual void execute(struct VPTransformState *State)=0
The method which generates the output IR that correspond to this VPBlockBase, thereby "executing" the...
llvm::VPScalarIVStepsRecipe::getCanonicalIV
VPCanonicalIVPHIRecipe * getCanonicalIV() const
Definition: VPlan.cpp:1346
llvm::VPInterleaveRecipe::getInterleaveGroup
const InterleaveGroup< Instruction > * getInterleaveGroup()
Definition: VPlan.h:1439
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:240
llvm::VPValue::VPVReductionSC
@ VPVReductionSC
Definition: VPlanValue.h:95
llvm::VFRange
A range of powers-of-2 vectorization factors with fixed start and adjustable end.
Definition: VPlan.h:78
llvm::VPTransformState::VPTransformState
VPTransformState(ElementCount VF, unsigned UF, LoopInfo *LI, DominatorTree *DT, IRBuilderBase &Builder, InnerLoopVectorizer *ILV, VPlan *Plan)
Definition: VPlan.h:201
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::VPLiveOut::fixPhi
void fixPhi(VPlan &Plan, VPTransformState &State)
Fixup the wrapped LCSSA phi node in the unique exit block.
Definition: VPlan.cpp:618
llvm::VPBranchOnMaskRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1585
llvm::VPWidenIntOrFpInductionRecipe::getInductionDescriptor
const InductionDescriptor & getInductionDescriptor() const
Returns the induction descriptor for the recipe.
Definition: VPlan.h:1064
llvm::VPDef
This class augments a recipe with a set of VPValues defined by the recipe.
Definition: VPlanValue.h:311
llvm::VPCanonicalIVPHIRecipe::getScalarType
const Type * getScalarType() const
Returns the scalar type of the induction.
Definition: VPlan.h:1823
llvm::VPRecipeBase::mayWriteToMemory
bool mayWriteToMemory() const
Returns true if the recipe may write to memory.
Definition: VPlan.cpp:528
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
GraphTraits.h
llvm::VPTransformState::DataState::PerPartOutput
DenseMap< VPValue *, PerPartValuesTy > PerPartOutput
Definition: VPlan.h:222
llvm::VPInterleaveRecipe::execute
void execute(VPTransformState &State) override
Generate the wide load or store, and shuffles.
Definition: LoopVectorize.cpp:9733
llvm::SmallBitVector
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
Definition: SmallBitVector.h:35
llvm::VPPredInstPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1470
llvm::VPReplicateRecipe
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition: VPlan.h:1506
llvm::VPWidenIntOrFpInductionRecipe::getStartValue
const VPValue * getStartValue() const
Definition: VPlan.h:1046
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::VPTransformState
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:200
llvm::VPInstruction::CanonicalIVIncrementNUW
@ CanonicalIVIncrementNUW
Definition: VPlan.h:757
llvm::VPBasicBlock::iterator
RecipeListTy::iterator iterator
Instruction iterators...
Definition: VPlan.h:1959
llvm::VPReductionPHIRecipe::classof
static bool classof(const VPHeaderPHIRecipe *R)
Definition: VPlan.h:1295
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::VPBlockBase
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:356
llvm::VPReplicateRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1446
llvm::VPBasicBlock::appendRecipe
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe.
Definition: VPlan.h:2006
llvm::VPlan::hasVF
bool hasVF(ElementCount VF)
Definition: VPlan.h:2525
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:1617
llvm::VPReductionPHIRecipe::isInLoop
bool isInLoop() const
Returns true, if the phi is part of an in-loop reduction.
Definition: VPlan.h:1319
llvm::VPWidenCanonicalIVRecipe::classof
static bool classof(const VPRecipeBase *R)
Definition: VPlan.h:1855
llvm::InductionDescriptor
A struct for saving information about induction variables.
Definition: IVDescriptors.h:306
llvm::VPWidenPHIRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:1211
llvm::VPTransformState::DataState::PerPartValuesTy
SmallVector< Value *, 2 > PerPartValuesTy
A type for vectorized values in the new loop.
Definition: VPlan.h:220
llvm::VPInstruction::classof
static bool classof(const VPValue *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:786
llvm::VPLane::mapToCacheIndex
unsigned mapToCacheIndex(const ElementCount &VF) const
Maps the lane to a cache index based on VF.
Definition: VPlan.h:163
llvm::VPWidenPHIRecipe::getIncomingBlock
VPBasicBlock * getIncomingBlock(unsigned I)
Returns the I th incoming VPBasicBlock.
Definition: VPlan.h:1231
llvm::VPInstruction
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:742
llvm::VPTransformState::ILV
InnerLoopVectorizer * ILV
Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
Definition: VPlan.h:341
llvm::VFRange::isEmpty
bool isEmpty() const
Definition: VPlan.h:85
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:418
llvm::Failed
testing::Matcher< const detail::ErrorHolder & > Failed()
Definition: Error.h:198
llvm::VPlan::print
void print(raw_ostream &O) const
Print this VPlan to O.
Definition: VPlan.cpp:1049
llvm::vputils::getOrCreateVPValueForSCEVExpr
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, ScalarEvolution &SE)
Get or create a VPValue that corresponds to the expansion of Expr.
Definition: VPlan.cpp:1830
llvm::VPBlockBase::setPredecessors
void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
Definition: VPlan.h:540
llvm::createStepForVF
Value * createStepForVF(IRBuilderBase &B, Type *Ty, ElementCount VF, int64_t Step)
Return a value for Step multiplied by VF.
Definition: LoopVectorize.cpp:988
llvm::VPScalarIVStepsRecipe::onlyFirstLaneUsed
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:1928
llvm::VPInterleavedAccessInfo::getInterleaveGroup
InterleaveGroup< VPInstruction > * getInterleaveGroup(VPInstruction *Instr) const
Get the interleave group that Instr belongs to.
Definition: VPlan.h:2870
llvm::VPIteration::Lane
VPLane Lane
Definition: VPlan.h:187
llvm::VPTransformState::LI
LoopInfo * LI
Hold a pointer to LoopInfo to register new basic blocks in the loop.
Definition: VPlan.h:327
llvm::VPlanSlp::buildGraph
VPInstruction * buildGraph(ArrayRef< VPValue * > Operands)
Tries to build an SLP tree rooted at Operands and returns a VPInstruction combining Operands,...
Definition: VPlanSLP.cpp:358
llvm::VPReplicateRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:1537
llvm::VPLane::isFirstLane
bool isFirstLane() const
Returns true if this is the first lane of the whole vector.
Definition: VPlan.h:160
Twine.h
llvm::VPBlockBase::getSuccessors
VPBlocksTy & getSuccessors()
Definition: VPlan.h:454
llvm::VPBlockUtils::insertBlockAfter
static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBase NewBlock after BlockPtr.
Definition: VPlan.h:2737
llvm::VPWidenPointerInductionRecipe::execute
void execute(VPTransformState &State) override
Generate vector values for the pointer induction.
Definition: LoopVectorize.cpp:9537
llvm::VPBasicBlock::getSublistAccess
static RecipeListTy VPBasicBlock::* getSublistAccess(VPRecipeBase *)
Returns a pointer to a member of the recipe list.
Definition: VPlan.h:1988
llvm::VPWidenMemoryInstructionRecipe::isReverse
bool isReverse() const
Definition: VPlan.h:1732
llvm::VPScalarIVStepsRecipe::VPScalarIVStepsRecipe
VPScalarIVStepsRecipe(Type *Ty, const InductionDescriptor &IndDesc, VPValue *CanonicalIV, VPValue *Start, VPValue *Step, Type *TruncToTy)
Definition: VPlan.h:1887
llvm::GraphTraits< const VPBlockBase * >::ChildIteratorType
SmallVectorImpl< VPBlockBase * >::const_iterator ChildIteratorType
Definition: VPlan.h:2187
llvm::VPlanPrinter::VPlanPrinter
VPlanPrinter(raw_ostream &O, const VPlan &P)
Definition: VPlan.h:2698
llvm::VPlan::getVPValue
VPValue * getVPValue(Value *V, bool OverrideAllowed=false)
Returns the VPValue for V.
Definition: VPlan.h:2558
llvm::GraphTraits< Inverse< VPBlockBase * > >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:2212
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
llvm::VPRecipeBase::moveBefore
void moveBefore(VPBasicBlock &BB, iplist< VPRecipeBase >::iterator I)
Unlink this recipe and insert into BB before I.
Definition: VPlan.cpp:667
llvm::VPBlockBase::getPredecessors
VPBlocksTy & getPredecessors()
Definition: VPlan.h:459
llvm::VPInterleaveRecipe
VPInterleaveRecipe is a recipe for transforming an interleave group of load or stores into one wide l...
Definition: VPlan.h:1379
IP
Definition: NVPTXLowerArgs.cpp:167
llvm::VPBranchOnMaskRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.h:1595
llvm::VPBlockBase::VPBlockTy
enum { VPBasicBlockSC, VPRegionBlockSC } VPBlockTy
An enumeration for keeping track of the concrete subclass of VPBlockBase that are actually instantiat...
Definition: VPlan.h:413
false
Definition: StackSlotColoring.cpp:141
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
llvm::VPBlockBase::getEnclosingBlockWithSuccessors
VPBlockBase * getEnclosingBlockWithSuccessors()
An Enclosing Block of a block B is any block containing B, including B itself.
Definition: VPlan.cpp:175
llvm::VPCanonicalIVPHIRecipe::classof
static bool classof(const VPHeaderPHIRecipe *D)
Definition: VPlan.h:1806
llvm::VPWidenPHIRecipe::getIncomingValue
VPValue * getIncomingValue(unsigned I)
Returns the I th incoming VPValue.
Definition: VPlan.h:1234
llvm::VPWidenPointerInductionRecipe::classof
static bool classof(const VPRecipeBase *B)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1164
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:1561
llvm::VPReductionPHIRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:1298
llvm::VPUser::VPUserID::Recipe
@ Recipe
llvm::GraphTraits< const VPRegionBlock * >::nodes_begin
static nodes_iterator nodes_begin(GraphRef N)
Definition: VPlan.h:2250
llvm::VPHeaderPHIRecipe::getBackedgeRecipe
VPRecipeBase * getBackedgeRecipe()
Returns the backedge value as a recipe.
Definition: VPlan.h:1136
llvm::VPValue::VPVWidenPointerInductionSC
@ VPVWidenPointerInductionSC
Definition: VPlanValue.h:109
llvm::VPTransformState::DataState::PerPartScalars
DenseMap< VPValue *, ScalarsPerPartValuesTy > PerPartScalars
Definition: VPlan.h:225
llvm::Instruction
Definition: Instruction.h:42
llvm::VPReplicateRecipe::~VPReplicateRecipe
~VPReplicateRecipe() override=default
llvm::InterleavedAccessInfo
Drive the analysis of interleaved memory accesses in the loop.
Definition: VectorUtils.h:751
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:430
llvm::VPReductionRecipe::execute
void execute(VPTransformState &State) override
Generate the reduction in the loop.
Definition: LoopVectorize.cpp:9739
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:463
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::VPVFirstOrderRecurrencePHISC
@ VPVFirstOrderRecurrencePHISC
Definition: VPlanValue.h:106
llvm::VPScalarIVStepsRecipe::getStartValue
VPValue * getStartValue() const
Definition: VPlan.h:1924
llvm::VPBlockUtils::blocksOnly
static auto blocksOnly(const T &Range)
Return an iterator range over Range which only includes BlockTy blocks.
Definition: VPlan.h:2818
llvm::VPValue::VPVWidenPHISC
@ VPVWidenPHISC
Definition: VPlanValue.h:107
llvm::VPValue
Definition: VPlanValue.h:44
llvm::VPRegionBlock::~VPRegionBlock
~VPRegionBlock() override
Definition: VPlan.h:2088
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::VPWidenCallRecipe::execute
void execute(VPTransformState &State) override
Produce a widened version of the call instruction.
Definition: LoopVectorize.cpp:9208
llvm::VPlanSlp::~VPlanSlp
~VPlanSlp()=default
llvm::VPlan::clearLiveOuts
void clearLiveOuts()
Definition: VPlan.h:2631
llvm::VPBlockBase::successors
iterator_range< VPBlockBase ** > successors()
Definition: VPlan.h:456
llvm::VPlanSlp::getWidestBundleBits
unsigned getWidestBundleBits() const
Return the width of the widest combined bundle in bits.
Definition: VPlan.h:2964
llvm::VPlan::getName
const std::string & getName() const
Definition: VPlan.h:2527
DebugLoc.h
SmallPtrSet.h
llvm::VPTransformState::CFGState::ExitBB
BasicBlock * ExitBB
The last IR BasicBlock in the output IR.
Definition: VPlan.h:313
llvm::VPWidenCanonicalIVRecipe
A Recipe for widening the canonical induction variable of the vector loop.
Definition: VPlan.h:1836
llvm::VPWidenMemoryInstructionRecipe::getIngredient
Instruction & getIngredient() const
Definition: VPlan.h:1755
llvm::VPAllSuccessorsIterator::operator++
VPAllSuccessorsIterator & operator++()
Definition: VPlan.h:2348
llvm::VPlan::removeLiveOut
void removeLiveOut(PHINode *PN)
Definition: VPlan.h:2637
llvm::InnerLoopVectorizer
InnerLoopVectorizer vectorizes loops which contain only one basic block to a specified vectorization ...
Definition: LoopVectorize.cpp:438
llvm::VPBasicBlock::end
iterator end()
Definition: VPlan.h:1969
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::InterleaveGroup::getMember
InstTy * getMember(uint32_t Index) const
Get the member with the given index Index.
Definition: VectorUtils.h:679
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::VPReductionPHIRecipe::classof
static bool classof(const VPRecipeBase *R)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1292
llvm::GraphTraits< const VPBlockBase * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:2191
llvm::ArrayRef::slice
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array.
Definition: ArrayRef.h:194
llvm::VPWidenCanonicalIVRecipe::~VPWidenCanonicalIVRecipe
~VPWidenCanonicalIVRecipe() override=default
llvm::VPUser::getNumOperands
unsigned getNumOperands() const
Definition: VPlanValue.h:255
llvm::VPRegionBlock::VPRegionBlock
VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exiting, const std::string &Name="", bool IsReplicator=false)
Definition: VPlan.h:2075
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::iplist_impl< simple_ilist< VPRecipeBase, Options... >, ilist_traits< VPRecipeBase > >::reverse_iterator
base_list_type::reverse_iterator reverse_iterator
Definition: ilist.h:180
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::VPBasicBlock::empty
bool empty() const
Definition: VPlan.h:1978
llvm::VPValue::VPVBlendSC
@ VPVBlendSC
Definition: VPlanValue.h:104
llvm::VPWidenIntOrFpInductionRecipe::VPWidenIntOrFpInductionRecipe
VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, VPValue *Step, const InductionDescriptor &IndDesc, bool NeedsVectorIV)
Definition: VPlan.h:1013
llvm::VPValue::VPVWidenSelectSC
@ VPVWidenSelectSC
Definition: VPlanValue.h:101
llvm::VPCanonicalIVPHIRecipe::~VPCanonicalIVPHIRecipe
~VPCanonicalIVPHIRecipe() override=default
llvm::VPWidenMemoryInstructionRecipe::getAddr
VPValue * getAddr() const
Return the address accessed by this recipe.
Definition: VPlan.h:1707
llvm::VPValue::VPVReductionPHISC
@ VPVReductionPHISC
Definition: VPlanValue.h:111
llvm::VPRegionBlock
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:2062
llvm::VPWidenMemoryInstructionRecipe::isStore
bool isStore() const
Returns true if this recipe is a store.
Definition: VPlan.h:1719
llvm::VPBlockBase::getPredecessors
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:458
LoopInfo.h
llvm::VPReductionPHIRecipe::VPReductionPHIRecipe
VPReductionPHIRecipe(PHINode *Phi, const RecurrenceDescriptor &RdxDesc, VPValue &Start, bool IsInLoop=false, bool IsOrdered=false)
Create a new VPReductionPHIRecipe for the reduction Phi described by RdxDesc.
Definition: VPlan.h:1281
llvm::VPInstruction::FirstOrderRecurrenceSplice
@ FirstOrderRecurrenceSplice
Definition: VPlan.h:748
llvm::GraphTraits< VPBlockRecursiveTraversalWrapper< const VPBlockBase * > >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:2407
llvm::Twine::str
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:74
llvm::GraphTraits< Inverse< VPBlockBase * > >::getEntryNode
static NodeRef getEntryNode(Inverse< NodeRef > B)
Definition: VPlan.h:2206
llvm::GraphTraits< VPBlockBase * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:2176
llvm::VPInterleaveRecipe::getAddr
VPValue * getAddr() const
Return the address accessed by this recipe.
Definition: VPlan.h:1410
llvm::VPWidenPointerInductionRecipe::VPWidenPointerInductionRecipe
VPWidenPointerInductionRecipe(PHINode *Phi, VPValue *Start, const InductionDescriptor &IndDesc, ScalarEvolution &SE)
Create a new VPWidenPointerInductionRecipe for Phi with start value Start.
Definition: VPlan.h:1152
llvm::VPReplicateRecipe::execute
void execute(VPTransformState &State) override
Generate replicas of the desired Ingredient.
Definition: LoopVectorize.cpp:9788
llvm::VPInterleaveRecipe::getStoredValues
ArrayRef< VPValue * > getStoredValues() const
Return the VPValues stored by this interleave group.
Definition: VPlan.h:1423
llvm::VPRecipeBase::VPRecipeBase
VPRecipeBase(const unsigned char SC, ArrayRef< VPValue * > Operands)
Definition: VPlan.h:640
llvm::VPWidenCanonicalIVRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1845
llvm::VPBlockBase::clearPredecessors
void clearPredecessors()
Remove all the predecessor of this block.
Definition: VPlan.h:547
llvm::VPBlockBase::getNumSuccessors
size_t getNumSuccessors() const
Definition: VPlan.h:473
llvm::GraphTraits< VPBlockRecursiveTraversalWrapper< const VPBlockBase * > >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:2403
llvm::VPLane::getNumCachedLanes
static unsigned getNumCachedLanes(const ElementCount &VF)
Returns the maxmimum number of lanes that we are able to consider caching for VF.
Definition: VPlan.h:176
llvm::VPRecipeBase::execute
virtual void execute(struct VPTransformState &State)=0
The method which generates the output IR instructions that correspond to this VPRecipe,...
llvm::VPlan::getVectorLoopRegion
const VPRegionBlock * getVectorLoopRegion() const
Definition: VPlan.h:2615
llvm::VPInstruction::classof
static bool classof(const VPRecipeBase *R)
Definition: VPlan.h:806
VectorUtils.h
llvm::ClrHandlerType::Filter
@ Filter
llvm::VPInterleaveRecipe::getMask
VPValue * getMask() const
Return the mask used by this recipe.
Definition: VPlan.h:1416
llvm::VPTransformState::CanonicalIV
Value * CanonicalIV
Hold the canonical scalar IV of the vector loop (start=0, step=VF*UF).
Definition: VPlan.h:338
llvm::VPRecipeBase::getParent
const VPBasicBlock * getParent() const
Definition: VPlan.h:650
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::VPBlendRecipe::onlyFirstLaneUsed
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:1365
llvm::VPBasicBlock::rbegin
const_reverse_iterator rbegin() const
Definition: VPlan.h:1973
llvm::VPlan::setName
void setName(const Twine &newName)
Definition: VPlan.h:2529
llvm::VPRecipeBase::removeFromParent
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
Definition: VPlan.cpp:651
llvm::VPBlockBase::getHierarchicalSuccessors
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:493
llvm::VPWidenMemoryInstructionRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1702
llvm::VPPredInstPHIRecipe::~VPPredInstPHIRecipe
~VPPredInstPHIRecipe() override=default
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:239
llvm::VPBranchOnMaskRecipe::VPBranchOnMaskRecipe
VPBranchOnMaskRecipe(VPValue *BlockInMask)
Definition: VPlan.h:1578
llvm::VPRecipeBase::mayHaveSideEffects
bool mayHaveSideEffects() const
Returns true if the recipe may have side-effects.
Definition: VPlan.cpp:590
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
llvm::VPExpandSCEVRecipe::execute
void execute(VPTransformState &State) override
Generate a canonical vector induction variable of the vector loop, with.
Definition: VPlan.cpp:1520
type
AMD64 Optimization Manual has some nice information about optimizing integer multiplication by a constant How much of it applies to Intel s X86 implementation There are definite trade offs to xmm0 cvttss2siq rdx jb L3 subss xmm0 rax cvttss2siq rdx xorq rdx rax ret instead of xmm1 cvttss2siq rcx movaps xmm2 subss xmm2 cvttss2siq rax rdx xorq rax ucomiss xmm0 cmovb rax ret Seems like the jb branch has high likelihood of being taken It would have saved a few instructions It s not possible to reference and DH registers in an instruction requiring REX prefix divb and mulb both produce results in AH If isel emits a CopyFromReg which gets turned into a movb and that can be allocated a r8b r15b To get around isel emits a CopyFromReg from AX and then right shift it down by and truncate it It s not pretty but it works We need some register allocation magic to make the hack go which would often require a callee saved register Callees usually need to keep this value live for most of their body so it doesn t add a significant burden on them We currently implement this in however this is suboptimal because it means that it would be quite awkward to implement the optimization for callers A better implementation would be to relax the LLVM IR rules for sret arguments to allow a function with an sret argument to have a non void return type
Definition: README-X86-64.txt:70
llvm::VPLane::getAsRuntimeExpr
Value * getAsRuntimeExpr(IRBuilderBase &Builder, const ElementCount &VF) const
Returns an expression describing the lane index that can be used at runtime.
Definition: VPlan.cpp:63
llvm::VPInterleaveRecipe::getNumStoreOperands
unsigned getNumStoreOperands() const
Returns the number of stored operands of this interleave group.
Definition: VPlan.h:1443
llvm::VPReductionRecipe::getCondOp
VPValue * getCondOp() const
The VPValue of the condition for the block.
Definition: VPlan.h:1497
llvm::VPTransformState::reset
void reset(VPValue *Def, Value *V, const VPIteration &Instance)
Reset an existing scalar value for Def and a given Instance.
Definition: VPlan.h:289
llvm::VPInterleaveRecipe::onlyFirstLaneUsed
bool onlyFirstLaneUsed(const VPValue *Op) const override
The recipe only uses the first lane of the address.
Definition: VPlan.h:1448
llvm::VPlan::isUniformAfterVectorization
bool isUniformAfterVectorization(VPValue *VPV) const
Returns true if VPV is uniform after vectorization.
Definition: VPlan.h:2606
llvm::VPBlockBase::clearSuccessors
void clearSuccessors()
Remove all the successors of this block.
Definition: VPlan.h:550
llvm::VPBlockBase::getSingleHierarchicalSuccessor
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:499
llvm::VPBlockBase::getSingleHierarchicalPredecessor
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:515
llvm::VPWidenGEPRecipe::execute
void execute(VPTransformState &State) override
Generate the gep nodes.
Definition: LoopVectorize.cpp:9363
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::VPTransformState::DT
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:330
llvm::VPWidenIntOrFpInductionRecipe::execute
void execute(VPTransformState &State) override
Generate the vectorized and scalarized versions of the phi node as needed by their users.
Definition: LoopVectorize.cpp:9436
llvm::VPWidenRecipe
VPWidenRecipe is a recipe for producing a copy of vector type its ingredient.
Definition: VPlan.h:881
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1637
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::VPInstruction::execute
void execute(VPTransformState &State) override
Generate the instruction.
Definition: VPlan.cpp:815
llvm::VPReductionPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1673
llvm::InterleaveGroup::getFactor
uint32_t getFactor() const
Definition: VectorUtils.h:625
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:78
llvm::TruncInst
This class represents a truncation of integer types.
Definition: Instructions.h:4767
llvm::VPInstruction::Not
@ Not
Definition: VPlan.h:751
llvm::iplist_impl< simple_ilist< VPRecipeBase, Options... >, ilist_traits< VPRecipeBase > >::iterator
base_list_type::iterator iterator
Definition: ilist.h:178
llvm::VPBlockBase::getVPBlockID
unsigned getVPBlockID() const
Definition: VPlan.h:426
llvm::VPBlockBase::dump
LLVM_DUMP_METHOD void dump() const
Dump this VPBlockBase to dbgs().
Definition: VPlan.h:595
llvm::VPLane::getLastLaneForVF
static VPLane getLastLaneForVF(const ElementCount &VF)
Definition: VPlan.h:133
llvm::VPTransformState::UF
unsigned UF
Definition: VPlan.h:209
llvm::DenseMap
Definition: DenseMap.h:716
llvm::VPInstruction::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the VPInstruction to O.
Definition: VPlan.cpp:829
llvm::VPIteration::VPIteration
VPIteration(unsigned Part, unsigned Lane, VPLane::Kind Kind=VPLane::Kind::First)
Definition: VPlan.h:189
llvm::VPTransformState::DataState
Definition: VPlan.h:216
llvm::VPBasicBlock::size
size_t size() const
Definition: VPlan.h:1977
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::VPBlockUtils::connectBlocks
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2773
llvm::GraphTraits< Inverse< VPBlockBase * > >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:2208
llvm::iterator_facade_base
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
llvm::VPHeaderPHIRecipe::getStartValue
VPValue * getStartValue()
Returns the start value of the phi, if one is set.
Definition: VPlan.h:1122
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:916
llvm::VPRegionBlock::getExiting
const VPBlockBase * getExiting() const
Definition: VPlan.h:2119
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:618
llvm::VPHeaderPHIRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:1104
llvm::VPBlendRecipe::getMask
VPValue * getMask(unsigned Idx) const
Return mask number Idx.
Definition: VPlan.h:1353
llvm::VPTransformState::CFGState::PrevVPBB
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:305
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1682
llvm::VPBlockBase::getNumPredecessors
size_t getNumPredecessors() const
Definition: VPlan.h:474
llvm::VPlan::removeVPValueFor
void removeVPValueFor(Value *V)
Definition: VPlan.h:2578
llvm::VPlan::addVPValue
void addVPValue(Value *V)
Definition: VPlan.h:2539
llvm::VPWidenGEPRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1372
TemplateParamKind::Type
@ Type
llvm::VPWidenMemoryInstructionRecipe::getStoredValue
VPValue * getStoredValue() const
Return the address accessed by this recipe.
Definition: VPlan.h:1722
llvm::VPExpandSCEVRecipe::VPExpandSCEVRecipe
VPExpandSCEVRecipe(const SCEV *Expr, ScalarEvolution &SE)
Definition: VPlan.h:1764
llvm::VPTransformState::hasAnyVectorValue
bool hasAnyVectorValue(VPValue *Def) const
Definition: VPlan.h:244
llvm::VPBlockBase::setTwoSuccessors
void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse)
Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.
Definition: VPlan.h:531
llvm::GraphTraits< VPBlockBase * >
Definition: VPlan.h:2170
llvm::VPBasicBlock::VPBasicBlock
VPBasicBlock(const Twine &Name="", VPRecipeBase *Recipe=nullptr)
Definition: VPlan.h:1947
llvm::VPBlockUtils::disconnectBlocks
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2784
llvm::VPWidenPointerInductionRecipe::~VPWidenPointerInductionRecipe
~VPWidenPointerInductionRecipe() override=default
llvm::VPlan::getEntry
VPBlockBase * getEntry()
Definition: VPlan.h:2493
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::VPWidenIntOrFpInductionRecipe::getPHINode
PHINode * getPHINode()
Definition: VPlan.h:1061
llvm::VPFirstOrderRecurrencePHIRecipe::classof
static bool classof(const VPHeaderPHIRecipe *R)
Definition: VPlan.h:1249
llvm::VPHeaderPHIRecipe::classof
static bool classof(const VPRecipeBase *B)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1097
llvm::VPBasicBlock::back
VPRecipeBase & back()
Definition: VPlan.h:1982
llvm::VPWidenIntOrFpInductionRecipe
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector valu...
Definition: VPlan.h:1007
llvm::GraphTraits< VPRegionBlock * >::getEntryNode
static NodeRef getEntryNode(GraphRef N)
Definition: VPlan.h:2229
llvm::GraphTraits< Inverse< VPRegionBlock * > >::nodes_end
static nodes_iterator nodes_end(GraphRef N)
Definition: VPlan.h:2275
llvm::VPReplicateRecipe::isUniform
bool isUniform() const
Definition: VPlan.h:1554
llvm::VPWidenPHIRecipe::classof
static bool classof(const VPRecipeBase *B)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1205
llvm::VPWidenGEPRecipe
A recipe for handling GEP instructions.
Definition: VPlan.h:966
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:272
llvm::VPInstruction::hasResult
bool hasResult() const
Definition: VPlan.h:834
llvm::VPLiveOut
A value that is used outside the VPlan.
Definition: VPlan.h:601
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1724
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
Mode
SI Whole Quad Mode
Definition: SIWholeQuadMode.cpp:262
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::VPReplicateRecipe::VPReplicateRecipe
VPReplicateRecipe(Instruction *I, iterator_range< IterT > Operands, bool IsUniform, bool IsPredicated=false)
Definition: VPlan.h:1518
llvm::VPlan::~VPlan
~VPlan()
Definition: VPlan.h:2466
llvm::VPWidenPointerInductionRecipe::classof
static bool classof(const VPHeaderPHIRecipe *R)
Definition: VPlan.h:1167
llvm::VPWidenPointerInductionRecipe
Definition: VPlan.h:1141
llvm::VPWidenMemoryInstructionRecipe
A Recipe for widening load/store operations.
Definition: VPlan.h:1663
llvm::VPInstruction::clone
VPInstruction * clone() const
Definition: VPlan.h:790
llvm::VPBasicBlock::~VPBasicBlock
~VPBasicBlock() override
Definition: VPlan.h:1953
llvm::LinearPolySize::getKnownMinValue
ScalarTy getKnownMinValue() const
Returns the minimum value this size can represent.
Definition: TypeSize.h:296
llvm::df_iterator
Definition: DepthFirstIterator.h:86
llvm::VPWidenIntOrFpInductionRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1030
llvm::VPWidenRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1306
llvm::VPRegionBlock::setExiting
void setExiting(VPBlockBase *ExitingBlock)
Set ExitingBlock as the exiting VPBlockBase of this VPRegionBlock.
Definition: VPlan.h:2124
llvm::VPWidenSelectRecipe
A recipe for widening select instructions.
Definition: VPlan.h:935
llvm::GraphTraits< const VPRegionBlock * >::nodes_end
static nodes_iterator nodes_end(GraphRef N)
Definition: VPlan.h:2254
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::VPInstruction::classof
static bool classof(const VPDef *R)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:796
llvm::VPWidenCanonicalIVRecipe::classof
static bool classof(const VPUser *U)
Extra classof implementations to allow directly casting from VPUser -> VPWidenCanonicalIVRecipe.
Definition: VPlan.h:1851
llvm::VPCanonicalIVPHIRecipe::VPCanonicalIVPHIRecipe
VPCanonicalIVPHIRecipe(VPValue *StartV, DebugLoc DL)
Definition: VPlan.h:1795
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::VPWidenIntOrFpInductionRecipe::isCanonical
bool isCanonical() const
Returns true if the induction is canonical, i.e.
Definition: VPlan.cpp:1340
llvm::VPValue::VPVWidenCallSC
@ VPVWidenCallSC
Definition: VPlanValue.h:98
llvm::VPWidenCallRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1276
llvm::VPBlockBase::printAsOperand
void printAsOperand(raw_ostream &OS, bool PrintType) const
Definition: VPlan.h:571
llvm::GraphTraits< const VPBlockBase * >
Definition: VPlan.h:2185
llvm::VPlan::getVectorLoopRegion
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:2612
llvm::VPBasicBlock::front
VPRecipeBase & front()
Definition: VPlan.h:1980
llvm::VPCanonicalIVPHIRecipe::onlyFirstLaneUsed
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:1828
llvm::VPTransformState::reset
void reset(VPValue *Def, Value *V, unsigned Part)
Reset an existing vector value for Def and a given Part.
Definition: VPlan.h:267
llvm::VPScalarIVStepsRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1364
llvm::VPlanIngredient::V
const Value * V
Definition: VPlan.h:2705
llvm::getRuntimeVF
Value * getRuntimeVF(IRBuilderBase &B, Type *Ty, ElementCount VF)
Return the runtime value for VF.
Definition: LoopVectorize.cpp:996
llvm::VPFirstOrderRecurrencePHIRecipe::VPFirstOrderRecurrencePHIRecipe
VPFirstOrderRecurrencePHIRecipe(PHINode *Phi, VPValue &Start)
Definition: VPlan.h:1241
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LoopInfo
Definition: LoopInfo.h:1102
llvm::VPReductionRecipe::getVecOp
VPValue * getVecOp() const
The VPValue of the vector value to be reduced.
Definition: VPlan.h:1495
llvm::VPBlockBase::getSingleSuccessor
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:463
this
Analysis the ScalarEvolution expression for r is this
Definition: README.txt:8
llvm::VPUser::addOperand
void addOperand(VPValue *Operand)
Definition: VPlanValue.h:250
llvm::VPUser::onlyFirstLaneUsed
virtual bool onlyFirstLaneUsed(const VPValue *Op) const
Returns true if the VPUser only uses the first lane of operand Op.
Definition: VPlanValue.h:299
llvm::VPLane::getKnownLane
unsigned getKnownLane() const
Returns a compile-time known value for the lane index and asserts if the lane can only be calculated ...
Definition: VPlan.h:147
llvm::VPWidenCallRecipe::VPWidenCallRecipe
VPWidenCallRecipe(CallInst &I, iterator_range< IterT > CallArguments)
Definition: VPlan.h:913
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::VPWidenCallRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:920
llvm::VPLane::Kind
Kind
Kind describes how to interpret Lane.
Definition: VPlan.h:110
llvm::VPExpandSCEVRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1771
llvm::VPRecipeBase::getParent
VPBasicBlock * getParent()
Definition: VPlan.h:649
llvm::IRBuilderBase
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:93
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::VPIteration::Part
unsigned Part
in [0..UF)
Definition: VPlan.h:185
llvm::VPCanonicalIVPHIRecipe::execute
void execute(VPTransformState &State) override
Generate the canonical scalar induction phi of the vector loop.
Definition: VPlan.cpp:1492
llvm::VPFirstOrderRecurrencePHIRecipe
A recipe for handling first-order recurrence phis.
Definition: VPlan.h:1240
llvm::VPExpandSCEVRecipe::~VPExpandSCEVRecipe
~VPExpandSCEVRecipe() override=default
llvm::VPWidenPointerInductionRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:1170
llvm::VPScalarIVStepsRecipe::getStepValue
VPValue * getStepValue() const
Definition: VPlan.h:1925
llvm::VPAllSuccessorsIterator::VPAllSuccessorsIterator
VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx=0)
Definition: VPlan.h:2318
llvm::VPBranchOnMaskRecipe
A recipe for generating conditional branches on the bits of a mask.
Definition: VPlan.h:1576
llvm::VPWidenSelectRecipe::execute
void execute(VPTransformState &State) override
Produce a widened version of the select instruction.
Definition: LoopVectorize.cpp:9213
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:349
llvm::VPHeaderPHIRecipe::VPHeaderPHIRecipe
VPHeaderPHIRecipe(unsigned char VPVID, unsigned char VPDefID, PHINode *Phi, VPValue *Start=nullptr)
Definition: VPlan.h:1086
llvm::VPBlockBase::setOneSuccessor
void setOneSuccessor(VPBlockBase *Successor)
Set a given VPBlockBase Successor as the single successor of this VPBlockBase.
Definition: VPlan.h:522
llvm::VPTransformState::VF
ElementCount VF
The chosen Vectorization and Unroll Factors of the loop being vectorized.
Definition: VPlan.h:208
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::VPWidenPHIRecipe::classof
static bool classof(const VPHeaderPHIRecipe *R)
Definition: VPlan.h:1208
llvm::VPValue::VPInstruction
friend class VPInstruction
Definition: VPlanValue.h:47
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:209
llvm::VPlan::addLiveOut
void addLiveOut(PHINode *PN, VPValue *V)
Definition: VPlan.cpp:1094
llvm::make_filter_range
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:534
llvm::VPBlockBase::getEntryBasicBlock
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:140
llvm::vputils::onlyFirstLaneUsed
bool onlyFirstLaneUsed(VPValue *Def)
Returns true if only the first lane of Def is used.
Definition: VPlan.cpp:1825
llvm::VPRegionBlock::getEntry
VPBlockBase * getEntry()
Definition: VPlan.h:2102
llvm::VPBasicBlock::classof
static bool classof(const VPBlockBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1993
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:398
llvm::VPInstruction::onlyFirstLaneUsed
bool onlyFirstLaneUsed(const VPValue *Op) const override
Returns true if the recipe only uses the first lane of operand Op.
Definition: VPlan.h:860
llvm::VPRecipeBase::classof
static bool classof(const VPUser *U)
Definition: VPlan.h:700
llvm::VPLiveOut::VPLiveOut
VPLiveOut(PHINode *Phi, VPValue *Op)
Definition: VPlan.h:605
llvm::VPFirstOrderRecurrencePHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1599
llvm::VPValue::setUnderlyingValue
void setUnderlyingValue(Value *Val)
Definition: VPlanValue.h:77
llvm::VPReplicateRecipe::setAlsoPack
void setAlsoPack(bool Pack)
Definition: VPlan.h:1546
llvm::VPReductionPHIRecipe::getRecurrenceDescriptor
const RecurrenceDescriptor & getRecurrenceDescriptor() const
Definition: VPlan.h:1311
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:230
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::VPInstruction::VPInstruction
VPInstruction(unsigned Opcode, ArrayRef< VPValue * > Operands, DebugLoc DL)
Definition: VPlan.h:776
llvm::VPlan::addVPValue
void addVPValue(Value *V, VPValue *VPV)
Definition: VPlan.h:2549
llvm::GraphTraits< VPRegionBlock * >::nodes_end
static nodes_iterator nodes_end(GraphRef N)
Definition: VPlan.h:2235
llvm::VPBlockBase::setParent
void setParent(VPRegionBlock *P)
Definition: VPlan.h:439
llvm::VPWidenPHIRecipe::addIncoming
void addIncoming(VPValue *IncomingV, VPBasicBlock *IncomingBlock)
Adds a pair (IncomingV, IncomingBlock) to the phi.
Definition: VPlan.h:1225
llvm::VPRecipeBase::VPRecipeBase
VPRecipeBase(const unsigned char SC, iterator_range< IterT > Operands)
Definition: VPlan.h:644
llvm::VPBasicBlock::rend
const_reverse_iterator rend() const
Definition: VPlan.h:1975
llvm::VPlan::mapToVPValues
iterator_range< mapped_iterator< Use *, std::function< VPValue *(Value *)> > > mapToVPValues(User::op_range Operands)
Returns a range mapping the values the range Operands to their corresponding VPValues.
Definition: VPlan.h:2598
llvm::VPUser::classof
static bool classof(const VPDef *Recipe)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:724
llvm::VPReductionPHIRecipe::execute
void execute(VPTransformState &State) override
Generate the phi/select nodes.
Definition: VPlan.cpp:1608
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::VPBlockBase::print
void print(raw_ostream &O) const
Print plain-text dump of this VPlan to O.
Definition: VPlan.h:585
llvm::VPSlotTracker
This class can be used to assign consecutive numbers to all VPValues in a VPlan and allows querying t...
Definition: VPlanValue.h:436
llvm::map_range
auto map_range(ContainerTy &&C, FuncTy F)
Definition: STLExtras.h:327
llvm::VPBasicBlock::begin
const_iterator begin() const
Definition: VPlan.h:1968
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::VPRecipeBase::~VPRecipeBase
virtual ~VPRecipeBase()=default
llvm::VPWidenGEPRecipe::VPWidenGEPRecipe
VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range< IterT > Operands, Loop *OrigLoop)
Definition: VPlan.h:978
llvm::VPlanSlp::VPlanSlp
VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB)
Definition: VPlan.h:2955
llvm::VPBlockBase::getParent
VPRegionBlock * getParent()
Definition: VPlan.h:428
llvm::VPAllSuccessorsIterator::operator==
bool operator==(const VPAllSuccessorsIterator &R) const
Definition: VPlan.h:2340
llvm::VPTransformState::CurrentVectorLoop
Loop * CurrentVectorLoop
The loop object for the current parent region, or nullptr.
Definition: VPlan.h:351
llvm::VPBasicBlock::rbegin
reverse_iterator rbegin()
Definition: VPlan.h:1972
llvm::VPAllSuccessorsIterator::end
static VPAllSuccessorsIterator end(BlockPtrTy Block)
Definition: VPlan.h:2329
llvm::VPWidenGEPRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:991
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:35
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
llvm::VPTransformState::MayGeneratePoisonRecipes
SmallPtrSet< VPRecipeBase *, 16 > MayGeneratePoisonRecipes
Holds recipes that may generate a poison value that is used after vectorization, even when their oper...
Definition: VPlan.h:348
llvm::VPValue::getDef
VPDef * getDef()
Definition: VPlanValue.h:181
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::VPRegionBlock::VPRegionBlock
VPRegionBlock(const std::string &Name="", bool IsReplicator=false)
Definition: VPlan.h:2084
llvm::VPRecipeBase::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:695
llvm::VPCanonicalIVPHIRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1803
llvm::VPWidenGEPRecipe::VPWidenGEPRecipe
VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range< IterT > Operands)
Definition: VPlan.h:972
llvm::VPScalarIVStepsRecipe
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
Definition: VPlan.h:1879
llvm::VPRecipeBase
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:630
llvm::iplist_impl::pop_back
void pop_back()
Definition: ilist.h:319
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:514
llvm::VPlan::setEntry
VPBlockBase * setEntry(VPBlockBase *Block)
Definition: VPlan.h:2496
llvm::VPReductionRecipe::~VPReductionRecipe
~VPReductionRecipe() override=default
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::VPAllSuccessorsIterator::VPAllSuccessorsIterator
VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other)
Definition: VPlan.h:2320
llvm::SlotTracker
This class provides computation of slot numbers for LLVM Assembly writing.
Definition: AsmWriter.cpp:656
llvm::VPReplicateRecipe::usesScalars
bool usesScalars(const VPValue *Op) const override
Returns true if the recipe uses scalars of operand Op.
Definition: VPlan.h:1568
llvm::VPRecipeBase::mayReadOrWriteMemory
bool mayReadOrWriteMemory() const
Returns true if the recipe may read from or write to memory.
Definition: VPlan.h:719
llvm::VPlan::getVectorTripCount
VPValue & getVectorTripCount()
The vector trip count.
Definition: VPlan.h:2517
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::VPInstruction::setUnderlyingInstr
void setUnderlyingInstr(Instruction *I)
Definition: VPlan.h:773
llvm::VPTransformState::CFGState
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:303
llvm::VPWidenCanonicalIVRecipe::getScalarType
const Type * getScalarType() const
Returns the scalar type of the induction.
Definition: VPlan.h:1871
llvm::VPBlockBase::setName
void setName(const Twine &newName)
Definition: VPlan.h:421
llvm::Inverse
Definition: GraphTraits.h:97
llvm::VPUser::VPUserID::LiveOut
@ LiveOut
llvm::VPWidenPointerInductionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1329
llvm::VPTransformState::CFGState::CFGState
CFGState()=default
llvm::VPBasicBlock::insert
void insert(VPRecipeBase *Recipe, iterator InsertPt)
Definition: VPlan.h:1997
llvm::VPInstruction::ActiveLaneMask
@ ActiveLaneMask
Definition: VPlan.h:755
llvm::VPBlendRecipe
A recipe for vectorizing a phi-node as a sequence of mask-based select instructions.
Definition: VPlan.h:1324
llvm::iplist_impl::insert
iterator insert(iterator where, pointer New)
Definition: ilist.h:229
llvm::VPReplicateRecipe::isPredicated
bool isPredicated() const
Definition: VPlan.h:1558
llvm::VPUser
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:206
llvm::VPFirstOrderRecurrencePHIRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:1252
llvm::RecurrenceDescriptor
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:69
llvm::VPInstruction::BranchOnCount
@ BranchOnCount
Definition: VPlan.h:758
llvm::VPlan::VPlan
VPlan(VPBlockBase *Entry=nullptr)
Definition: VPlan.h:2461
llvm::VPBlockBase::print
virtual void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const =0
Print plain-text dump of this VPBlockBase to O, prefixing all lines with Indent.
llvm::VPReductionRecipe::classof
static bool classof(const VPValue *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1479
llvm::VPBlendRecipe::VPBlendRecipe
VPBlendRecipe(PHINode *Phi, ArrayRef< VPValue * > Operands)
The blend operation is a User of the incoming values and of their respective masks,...
Definition: VPlan.h:1331
SmallVector.h
llvm::VPValue::VPVPredInstPHI
@ VPVPredInstPHI
Definition: VPlanValue.h:110
llvm::VPBasicBlock::front
const VPRecipeBase & front() const
Definition: VPlan.h:1979
llvm::VPTransformState::VPValue2Value
VPValue2ValueTy VPValue2Value
Definition: VPlan.h:335
llvm::VPBasicBlock::begin
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:1967
llvm::VPlanSlp::isCompletelySLP
bool isCompletelySLP() const
Return true if all visited instruction can be combined.
Definition: VPlan.h:2967
llvm::VPAllSuccessorsIterator::operator++
VPAllSuccessorsIterator operator++(int X)
Definition: VPlan.h:2353
llvm::VPHeaderPHIRecipe::getStartValue
VPValue * getStartValue() const
Definition: VPlan.h:1125
llvm::VPRegionBlock::setEntry
void setEntry(VPBlockBase *EntryBlock)
Set EntryBlock as the entry VPBlockBase of this VPRegionBlock.
Definition: VPlan.h:2106
llvm::VPAllSuccessorsIterator::operator=
VPAllSuccessorsIterator & operator=(const VPAllSuccessorsIterator &R)
Definition: VPlan.h:2323
llvm::VPlan::getLiveOuts
const MapVector< PHINode *, VPLiveOut * > & getLiveOuts() const
Definition: VPlan.h:2642
llvm::VPWidenMemoryInstructionRecipe::execute
void execute(VPTransformState &State) override
Generate the wide load/store.
Definition: LoopVectorize.cpp:9892
llvm::VPBlendRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1341
SmallBitVector.h
llvm::VPUser::getOperand
VPValue * getOperand(unsigned N) const
Definition: VPlanValue.h:256
llvm::VPTransformState::Instance
Optional< VPIteration > Instance
Hold the indices to generate specific scalar instructions.
Definition: VPlan.h:214
N
#define N
llvm::VPRecipeBase::mayReadFromMemory
bool mayReadFromMemory() const
Returns true if the recipe may read from memory.
Definition: VPlan.cpp:559
llvm::iplist_impl< simple_ilist< VPRecipeBase, Options... >, ilist_traits< VPRecipeBase > >::const_iterator
base_list_type::const_iterator const_iterator
Definition: ilist.h:179
llvm::hash_combine_range
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:483
llvm::VPRegionBlock::classof
static bool classof(const VPBlockBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:2097
llvm::VPlan::printDOT
void printDOT(raw_ostream &O) const
Print this VPlan in DOT format to O.
Definition: VPlan.cpp:1085
llvm::VPlan::getOrCreateBackedgeTakenCount
VPValue * getOrCreateBackedgeTakenCount()
The backedge taken count of the original loop.
Definition: VPlan.h:2510
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:442
llvm::VPBlockUtils::VPBlockUtils
VPBlockUtils()=delete
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::VPExpandSCEVRecipe
Recipe to expand a SCEV expression.
Definition: VPlan.h:1759
llvm::VPValue::VPVReplicateSC
@ VPVReplicateSC
Definition: VPlanValue.h:96
llvm::PHINode
Definition: Instructions.h:2651
llvm::VPWidenRecipe::VPWidenRecipe
VPWidenRecipe(Instruction &I, iterator_range< IterT > Operands)
Definition: VPlan.h:884
llvm::VPWidenMemoryInstructionRecipe::isConsecutive
bool isConsecutive() const
Definition: VPlan.h:1728
ilist_node.h
llvm::GraphTraits< VPBlockRecursiveTraversalWrapper< VPBlockBase * > >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:2388
llvm::VPBlockBase::getExitingBasicBlock
const VPBasicBlock * getExitingBasicBlock() const
Definition: VPlan.cpp:161
llvm::VPFirstOrderRecurrencePHIRecipe::execute
void execute(VPTransformState &State) override
Generate the phi nodes.
Definition: VPlan.cpp:1570
llvm::SmallVectorImpl< VPBlockBase * >
llvm::VPTransformState::CFGState::VPBB2IRBB
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:317
llvm::VPBlockBase::getParent
const VPRegionBlock * getParent() const
Definition: VPlan.h:429
llvm::VPTransformState::Plan
VPlan * Plan
Pointer to the VPlan code is generated for.
Definition: VPlan.h:344
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::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::VPHeaderPHIRecipe::getBackedgeValue
VPValue * getBackedgeValue()
Returns the incoming value from the loop backedge.
Definition: VPlan.h:1130
llvm::VPFirstOrderRecurrencePHIRecipe::classof
static bool classof(const VPRecipeBase *R)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1246
llvm::VPPredInstPHIRecipe::VPPredInstPHIRecipe
VPPredInstPHIRecipe(VPValue *PredV)
Construct a VPPredInstPHIRecipe given PredInst whose value needs a phi nodes after merging back from ...
Definition: VPlan.h:1630
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1461
llvm::VPValue::getVPValueID
unsigned getVPValueID() const
Definition: VPlanValue.h:124
llvm::VPWidenSelectRecipe::VPWidenSelectRecipe
VPWidenSelectRecipe(SelectInst &I, iterator_range< IterT > Operands, bool InvariantCond)
Definition: VPlan.h:942
llvm::VPBranchOnMaskRecipe::getMask
VPValue * getMask() const
Return the mask used by this recipe.
Definition: VPlan.h:1607
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::VPValue::VPVWidenIntOrFpInductionSC
@ VPVWidenIntOrFpInductionSC
Definition: VPlanValue.h:108
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::VPBlockBase::deleteCFG
static void deleteCFG(VPBlockBase *Entry)
Delete all blocks reachable from a given VPBlockBase, inclusive.
Definition: VPlan.cpp:191
llvm::VPRegionBlock::isReplicator
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:2139
llvm::GraphTraits
Definition: GraphTraits.h:37
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::VPWidenPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1386
llvm::VPInstruction::VPInstruction
VPInstruction(unsigned Opcode, std::initializer_list< VPValue * > Operands, DebugLoc DL={})
Definition: VPlan.h:781
llvm::VPWidenIntOrFpInductionRecipe::getTruncInst
const TruncInst * getTruncInst() const
Definition: VPlan.h:1057
llvm::Region
Definition: RegionInfo.h:889
llvm::VFRange::End
ElementCount End
Definition: VPlan.h:83
llvm::VPBasicBlock::phis
iterator_range< iterator > phis()
Returns an iterator range over the PHI-like recipes in the block.
Definition: VPlan.h:2016
llvm::VPValue::VPVWidenGEPSC
@ VPVWidenGEPSC
Definition: VPlanValue.h:100
llvm::VPBasicBlock::getFirstNonPhi
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
Definition: VPlan.cpp:198
llvm::VPValue::VPVCanonicalIVPHISC
@ VPVCanonicalIVPHISC
Definition: VPlanValue.h:105
llvm::VPReductionRecipe::getChainOp
VPValue * getChainOp() const
The VPValue of the scalar Chain being accumulated.
Definition: VPlan.h:1493
llvm::VPInterleavedAccessInfo::VPInterleavedAccessInfo
VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI)
Definition: VPlan.cpp:1794
llvm::VPValue::VPVMemoryInstructionSC
@ VPVMemoryInstructionSC
Definition: VPlanValue.h:94
llvm::VPBlockRecursiveTraversalWrapper
Helper for GraphTraits specialization that traverses through VPRegionBlocks.
Definition: VPlan.h:2361
llvm::VPWidenRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:894
llvm::VPWidenRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:891
llvm::VPBlockBase::getSuccessors
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:453
llvm::VPHeaderPHIRecipe::~VPHeaderPHIRecipe
~VPHeaderPHIRecipe() override=default
llvm::VPExpandSCEVRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1533
llvm::GraphTraits< Inverse< VPBlockBase * > >::ChildIteratorType
SmallVectorImpl< VPBlockBase * >::iterator ChildIteratorType
Definition: VPlan.h:2204
llvm::VPBlockRecursiveTraversalWrapper::VPBlockRecursiveTraversalWrapper
VPBlockRecursiveTraversalWrapper(BlockTy Entry)
Definition: VPlan.h:2365
llvm::VPWidenRecipe::~VPWidenRecipe
~VPWidenRecipe() override=default
llvm::VPWidenRecipe::execute
void execute(VPTransformState &State) override
Produce widened copies of all Ingredients.
Definition: LoopVectorize.cpp:9234
llvm::VPDef::getVPDefID
unsigned getVPDefID() const
Definition: VPlanValue.h:418
llvm::VPInstruction::dump
LLVM_DUMP_METHOD void dump() const
Print the VPInstruction to dbgs() (for debugging).
Definition: VPlan.cpp:824
llvm::GraphTraits< VPBlockRecursiveTraversalWrapper< VPBlockBase * > >::getEntryNode
static NodeRef getEntryNode(VPBlockRecursiveTraversalWrapper< VPBlockBase * > N)
Definition: VPlan.h:2380
llvm::VPBasicBlock::rend
reverse_iterator rend()
Definition: VPlan.h:1974
llvm::VPValue::getUnderlyingValue
Value * getUnderlyingValue()
Return the underlying Value attached to this VPValue.
Definition: VPlanValue.h:84
llvm::GraphTraits< VPBlockBase * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:2180
llvm::VPlan
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2417
llvm::GraphTraits< Inverse< VPRegionBlock * > >::nodes_begin
static nodes_iterator nodes_begin(GraphRef N)
Definition: VPlan.h:2271
llvm::VPWidenIntOrFpInductionRecipe::getStepValue
const VPValue * getStepValue() const
Definition: VPlan.h:1050
llvm::VPInterleavedAccessInfo::~VPInterleavedAccessInfo
~VPInterleavedAccessInfo()
Definition: VPlan.h:2857
llvm::VPBlockBase::setPlan
void setPlan(VPlan *ParentPlan)
Sets the pointer of the plan containing the block.
Definition: VPlan.cpp:154
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:627
llvm::VPScalarIVStepsRecipe::~VPScalarIVStepsRecipe
~VPScalarIVStepsRecipe() override=default
llvm::deref
Binary functor that adapts to any other binary functor after dereferencing operands.
Definition: STLExtras.h:1936
llvm::MapVector::erase
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
Definition: MapVector.h:174
llvm::VPCanonicalIVPHIRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:1809
llvm::VPHeaderPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override=0
Print the recipe.
llvm::VPValue::VPVWidenCanonicalIVSC
@ VPVWidenCanonicalIVSC
Definition: VPlanValue.h:99
llvm::VPReductionPHIRecipe::isOrdered
bool isOrdered() const
Returns true, if the phi is part of an ordered reduction.
Definition: VPlan.h:1316
llvm::GraphTraits< const VPRegionBlock * >::getEntryNode
static NodeRef getEntryNode(GraphRef N)
Definition: VPlan.h:2248
llvm::VPlan::dump
LLVM_DUMP_METHOD void dump() const
Dump the plan to stderr (for debugging).
Definition: VPlan.cpp:1091
llvm::VPlanIngredient
Definition: VPlan.h:2704
llvm::VPWidenSelectRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1293
llvm::VPRecipeBase::isPhi
bool isPhi() const
Returns true for PHI-like recipes.
Definition: VPlan.h:708
llvm::VPInstruction::ICmpULE
@ ICmpULE
Definition: VPlan.h:752
llvm::VPWidenIntOrFpInductionRecipe::getStartValue
VPValue * getStartValue()
Returns the start value of the induction.
Definition: VPlan.h:1045
llvm::VPlanPrinter
VPlanPrinter prints a given VPlan to a given output stream.
Definition: VPlan.h:2657
llvm::VPTransformState::CFGState::PrevBB
BasicBlock * PrevBB
The previous IR BasicBlock created or used.
Definition: VPlan.h:309
llvm::GraphTraits< VPBlockBase * >::ChildIteratorType
SmallVectorImpl< VPBlockBase * >::iterator ChildIteratorType
Definition: VPlan.h:2172
llvm::VPRegionBlock::getExiting
VPBlockBase * getExiting()
Definition: VPlan.h:2120
llvm::VPRecipeBase::insertAfter
void insertAfter(VPRecipeBase *InsertPos)
Insert an unlinked Recipe into a basic block immediately after the specified Recipe.
Definition: VPlan.cpp:643
llvm::VFRange::Start
const ElementCount Start
Definition: VPlan.h:80
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1236
llvm::VPTransformState::hasVectorValue
bool hasVectorValue(VPValue *Def, unsigned Part)
Definition: VPlan.h:238
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::VPlan::getOrCreateTripCount
VPValue * getOrCreateTripCount()
The trip count of the original loop.
Definition: VPlan.h:2503
llvm::VPHeaderPHIRecipe::execute
void execute(VPTransformState &State) override=0
Generate the phi nodes.
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::VPlan::addVF
void addVF(ElementCount VF)
Definition: VPlan.h:2523