LLVM  14.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 "VPlanLoopInfo.h"
29 #include "VPlanValue.h"
30 #include "llvm/ADT/DenseMap.h"
32 #include "llvm/ADT/GraphTraits.h"
33 #include "llvm/ADT/Optional.h"
35 #include "llvm/ADT/SmallPtrSet.h"
36 #include "llvm/ADT/SmallSet.h"
37 #include "llvm/ADT/SmallVector.h"
38 #include "llvm/ADT/Twine.h"
39 #include "llvm/ADT/ilist.h"
40 #include "llvm/ADT/ilist_node.h"
42 #include "llvm/IR/DebugLoc.h"
43 #include "llvm/IR/IRBuilder.h"
45 #include <algorithm>
46 #include <cassert>
47 #include <cstddef>
48 #include <map>
49 #include <string>
50 
51 namespace llvm {
52 
53 class BasicBlock;
54 class DominatorTree;
55 class InductionDescriptor;
56 class InnerLoopVectorizer;
57 class LoopInfo;
58 class raw_ostream;
59 class RecurrenceDescriptor;
60 class Value;
61 class VPBasicBlock;
62 class VPRegionBlock;
63 class VPlan;
64 class VPReplicateRecipe;
65 class VPlanSlp;
66 
67 /// Returns a calculation for the total number of elements for a given \p VF.
68 /// For fixed width vectors this value is a constant, whereas for scalable
69 /// vectors it is an expression determined at runtime.
70 Value *getRuntimeVF(IRBuilder<> &B, Type *Ty, ElementCount VF);
71 
72 /// Return a value for Step multiplied by VF.
73 Value *createStepForVF(IRBuilder<> &B, Type *Ty, ElementCount VF, 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 new latch
312  /// BasicBlock, used for placing the newly created BasicBlocks.
313  BasicBlock *LastBB = nullptr;
314 
315  /// The IR BasicBlock that is the preheader of the vector loop in the output
316  /// IR.
317  /// FIXME: The vector preheader should also be modeled in VPlan, so any code
318  /// that needs to be added to the preheader gets directly generated by
319  /// VPlan. There should be no need to manage a pointer to the IR BasicBlock.
321 
322  /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case
323  /// of replication, maps the BasicBlock of the last replica created.
325 
326  /// Vector of VPBasicBlocks whose terminator instruction needs to be fixed
327  /// up at the end of vector code generation.
329 
330  CFGState() = default;
331  } CFG;
332 
333  /// Hold a pointer to LoopInfo to register new basic blocks in the loop.
335 
336  /// Hold a pointer to Dominator Tree to register new basic blocks in the loop.
338 
339  /// Hold a reference to the IRBuilder used to generate output IR code.
341 
343 
344  /// Hold the canonical scalar IV of the vector loop (start=0, step=VF*UF).
345  Value *CanonicalIV = nullptr;
346 
347  /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
349 
350  /// Pointer to the VPlan code is generated for.
352 
353  /// Holds recipes that may generate a poison value that is used after
354  /// vectorization, even when their operands are not poison.
356 };
357 
358 /// VPUsers instance used by VPBlockBase to manage CondBit and the block
359 /// predicate. Currently VPBlockUsers are used in VPBlockBase for historical
360 /// reasons, but in the future the only VPUsers should either be recipes or
361 /// live-outs.VPBlockBase uses.
362 struct VPBlockUser : public VPUser {
364 
366  if (getNumOperands() == 1)
367  return getOperand(0);
368 
369  return nullptr;
370  }
372  if (getNumOperands() == 1)
373  return getOperand(0);
374 
375  return nullptr;
376  }
377 
378  void resetSingleOpUser(VPValue *NewVal) {
379  assert(getNumOperands() <= 1 && "Didn't expect more than one operand!");
380  if (!NewVal) {
381  if (getNumOperands() == 1)
383  return;
384  }
385 
386  if (getNumOperands() == 1)
387  setOperand(0, NewVal);
388  else
389  addOperand(NewVal);
390  }
391 };
392 
393 /// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
394 /// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.
395 class VPBlockBase {
396  friend class VPBlockUtils;
397 
398  const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
399 
400  /// An optional name for the block.
401  std::string Name;
402 
403  /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if
404  /// it is a topmost VPBlockBase.
405  VPRegionBlock *Parent = nullptr;
406 
407  /// List of predecessor blocks.
408  SmallVector<VPBlockBase *, 1> Predecessors;
409 
410  /// List of successor blocks.
412 
413  /// Successor selector managed by a VPUser. For blocks with zero or one
414  /// successors, there is no operand. Otherwise there is exactly one operand
415  /// which is the branch condition.
416  VPBlockUser CondBitUser;
417 
418  /// If the block is predicated, its predicate is stored as an operand of this
419  /// VPUser to maintain the def-use relations. Otherwise there is no operand
420  /// here.
421  VPBlockUser PredicateUser;
422 
423  /// VPlan containing the block. Can only be set on the entry block of the
424  /// plan.
425  VPlan *Plan = nullptr;
426 
427  /// Add \p Successor as the last successor to this block.
428  void appendSuccessor(VPBlockBase *Successor) {
429  assert(Successor && "Cannot add nullptr successor!");
430  Successors.push_back(Successor);
431  }
432 
433  /// Add \p Predecessor as the last predecessor to this block.
434  void appendPredecessor(VPBlockBase *Predecessor) {
435  assert(Predecessor && "Cannot add nullptr predecessor!");
436  Predecessors.push_back(Predecessor);
437  }
438 
439  /// Remove \p Predecessor from the predecessors of this block.
440  void removePredecessor(VPBlockBase *Predecessor) {
441  auto Pos = find(Predecessors, Predecessor);
442  assert(Pos && "Predecessor does not exist");
443  Predecessors.erase(Pos);
444  }
445 
446  /// Remove \p Successor from the successors of this block.
447  void removeSuccessor(VPBlockBase *Successor) {
448  auto Pos = find(Successors, Successor);
449  assert(Pos && "Successor does not exist");
450  Successors.erase(Pos);
451  }
452 
453 protected:
454  VPBlockBase(const unsigned char SC, const std::string &N)
455  : SubclassID(SC), Name(N) {}
456 
457 public:
458  /// An enumeration for keeping track of the concrete subclass of VPBlockBase
459  /// that are actually instantiated. Values of this enumeration are kept in the
460  /// SubclassID field of the VPBlockBase objects. They are used for concrete
461  /// type identification.
462  using VPBlockTy = enum { VPBasicBlockSC, VPRegionBlockSC };
463 
465 
466  virtual ~VPBlockBase() = default;
467 
468  const std::string &getName() const { return Name; }
469 
470  void setName(const Twine &newName) { Name = newName.str(); }
471 
472  /// \return an ID for the concrete type of this object.
473  /// This is used to implement the classof checks. This should not be used
474  /// for any other purpose, as the values may change as LLVM evolves.
475  unsigned getVPBlockID() const { return SubclassID; }
476 
477  VPRegionBlock *getParent() { return Parent; }
478  const VPRegionBlock *getParent() const { return Parent; }
479 
480  /// \return A pointer to the plan containing the current block.
481  VPlan *getPlan();
482  const VPlan *getPlan() const;
483 
484  /// Sets the pointer of the plan containing the block. The block must be the
485  /// entry block into the VPlan.
486  void setPlan(VPlan *ParentPlan);
487 
488  void setParent(VPRegionBlock *P) { Parent = P; }
489 
490  /// \return the VPBasicBlock that is the entry of this VPBlockBase,
491  /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
492  /// VPBlockBase is a VPBasicBlock, it is returned.
493  const VPBasicBlock *getEntryBasicBlock() const;
495 
496  /// \return the VPBasicBlock that is the exit of this VPBlockBase,
497  /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
498  /// VPBlockBase is a VPBasicBlock, it is returned.
499  const VPBasicBlock *getExitBasicBlock() const;
501 
502  const VPBlocksTy &getSuccessors() const { return Successors; }
503  VPBlocksTy &getSuccessors() { return Successors; }
504 
506 
507  const VPBlocksTy &getPredecessors() const { return Predecessors; }
508  VPBlocksTy &getPredecessors() { return Predecessors; }
509 
510  /// \return the successor of this VPBlockBase if it has a single successor.
511  /// Otherwise return a null pointer.
513  return (Successors.size() == 1 ? *Successors.begin() : nullptr);
514  }
515 
516  /// \return the predecessor of this VPBlockBase if it has a single
517  /// predecessor. Otherwise return a null pointer.
519  return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr);
520  }
521 
522  size_t getNumSuccessors() const { return Successors.size(); }
523  size_t getNumPredecessors() const { return Predecessors.size(); }
524 
525  /// An Enclosing Block of a block B is any block containing B, including B
526  /// itself. \return the closest enclosing block starting from "this", which
527  /// has successors. \return the root enclosing block if all enclosing blocks
528  /// have no successors.
530 
531  /// \return the closest enclosing block starting from "this", which has
532  /// predecessors. \return the root enclosing block if all enclosing blocks
533  /// have no predecessors.
535 
536  /// \return the successors either attached directly to this VPBlockBase or, if
537  /// this VPBlockBase is the exit block of a VPRegionBlock and has no
538  /// successors of its own, search recursively for the first enclosing
539  /// VPRegionBlock that has successors and return them. If no such
540  /// VPRegionBlock exists, return the (empty) successors of the topmost
541  /// VPBlockBase reached.
544  }
545 
546  /// \return the hierarchical successor of this VPBlockBase if it has a single
547  /// hierarchical successor. Otherwise return a null pointer.
550  }
551 
552  /// \return the predecessors either attached directly to this VPBlockBase or,
553  /// if this VPBlockBase is the entry block of a VPRegionBlock and has no
554  /// predecessors of its own, search recursively for the first enclosing
555  /// VPRegionBlock that has predecessors and return them. If no such
556  /// VPRegionBlock exists, return the (empty) predecessors of the topmost
557  /// VPBlockBase reached.
560  }
561 
562  /// \return the hierarchical predecessor of this VPBlockBase if it has a
563  /// single hierarchical predecessor. Otherwise return a null pointer.
566  }
567 
568  /// \return the condition bit selecting the successor.
569  VPValue *getCondBit();
570  /// \return the condition bit selecting the successor.
571  const VPValue *getCondBit() const;
572  /// Set the condition bit selecting the successor.
573  void setCondBit(VPValue *CV);
574 
575  /// \return the block's predicate.
577  /// \return the block's predicate.
578  const VPValue *getPredicate() const;
579  /// Set the block's predicate.
580  void setPredicate(VPValue *Pred);
581 
582  /// Set a given VPBlockBase \p Successor as the single successor of this
583  /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor.
584  /// This VPBlockBase must have no successors.
586  assert(Successors.empty() && "Setting one successor when others exist.");
587  appendSuccessor(Successor);
588  }
589 
590  /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two
591  /// successors of this VPBlockBase. \p Condition is set as the successor
592  /// selector. This VPBlockBase is not added as predecessor of \p IfTrue or \p
593  /// IfFalse. This VPBlockBase must have no successors.
594  void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
595  VPValue *Condition) {
596  assert(Successors.empty() && "Setting two successors when others exist.");
597  assert(Condition && "Setting two successors without condition!");
598  setCondBit(Condition);
599  appendSuccessor(IfTrue);
600  appendSuccessor(IfFalse);
601  }
602 
603  /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase.
604  /// This VPBlockBase must have no predecessors. This VPBlockBase is not added
605  /// as successor of any VPBasicBlock in \p NewPreds.
607  assert(Predecessors.empty() && "Block predecessors already set.");
608  for (auto *Pred : NewPreds)
609  appendPredecessor(Pred);
610  }
611 
612  /// Remove all the predecessor of this block.
613  void clearPredecessors() { Predecessors.clear(); }
614 
615  /// Remove all the successors of this block and set to null its condition bit
617  Successors.clear();
618  setCondBit(nullptr);
619  }
620 
621  /// The method which generates the output IR that correspond to this
622  /// VPBlockBase, thereby "executing" the VPlan.
623  virtual void execute(struct VPTransformState *State) = 0;
624 
625  /// Delete all blocks reachable from a given VPBlockBase, inclusive.
626  static void deleteCFG(VPBlockBase *Entry);
627 
628  /// Return true if it is legal to hoist instructions into this block.
630  // There are currently no constraints that prevent an instruction to be
631  // hoisted into a VPBlockBase.
632  return true;
633  }
634 
635  /// Replace all operands of VPUsers in the block with \p NewValue and also
636  /// replaces all uses of VPValues defined in the block with NewValue.
637  virtual void dropAllReferences(VPValue *NewValue) = 0;
638 
639 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
640  void printAsOperand(raw_ostream &OS, bool PrintType) const {
641  OS << getName();
642  }
643 
644  /// Print plain-text dump of this VPBlockBase to \p O, prefixing all lines
645  /// with \p Indent. \p SlotTracker is used to print unnamed VPValue's using
646  /// consequtive numbers.
647  ///
648  /// Note that the numbering is applied to the whole VPlan, so printing
649  /// individual blocks is consistent with the whole VPlan printing.
650  virtual void print(raw_ostream &O, const Twine &Indent,
651  VPSlotTracker &SlotTracker) const = 0;
652 
653  /// Print plain-text dump of this VPlan to \p O.
654  void print(raw_ostream &O) const {
656  print(O, "", SlotTracker);
657  }
658 
659  /// Print the successors of this block to \p O, prefixing all lines with \p
660  /// Indent.
661  void printSuccessors(raw_ostream &O, const Twine &Indent) const;
662 
663  /// Dump this VPBlockBase to dbgs().
664  LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
665 #endif
666 };
667 
668 /// VPRecipeBase is a base class modeling a sequence of one or more output IR
669 /// instructions. VPRecipeBase owns the the VPValues it defines through VPDef
670 /// and is responsible for deleting its defined values. Single-value
671 /// VPRecipeBases that also inherit from VPValue must make sure to inherit from
672 /// VPRecipeBase before VPValue.
673 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock>,
674  public VPDef,
675  public VPUser {
676  friend VPBasicBlock;
677  friend class VPBlockUtils;
678 
679  /// Each VPRecipe belongs to a single VPBasicBlock.
680  VPBasicBlock *Parent = nullptr;
681 
682 public:
684  : VPDef(SC), VPUser(Operands, VPUser::VPUserID::Recipe) {}
685 
686  template <typename IterT>
688  : VPDef(SC), VPUser(Operands, VPUser::VPUserID::Recipe) {}
689  virtual ~VPRecipeBase() = default;
690 
691  /// \return the VPBasicBlock which this VPRecipe belongs to.
692  VPBasicBlock *getParent() { return Parent; }
693  const VPBasicBlock *getParent() const { return Parent; }
694 
695  /// The method which generates the output IR instructions that correspond to
696  /// this VPRecipe, thereby "executing" the VPlan.
697  virtual void execute(struct VPTransformState &State) = 0;
698 
699  /// Insert an unlinked recipe into a basic block immediately before
700  /// the specified recipe.
701  void insertBefore(VPRecipeBase *InsertPos);
702 
703  /// Insert an unlinked Recipe into a basic block immediately after
704  /// the specified Recipe.
705  void insertAfter(VPRecipeBase *InsertPos);
706 
707  /// Unlink this recipe from its current VPBasicBlock and insert it into
708  /// the VPBasicBlock that MovePos lives in, right after MovePos.
709  void moveAfter(VPRecipeBase *MovePos);
710 
711  /// Unlink this recipe and insert into BB before I.
712  ///
713  /// \pre I is a valid iterator into BB.
715 
716  /// This method unlinks 'this' from the containing basic block, but does not
717  /// delete it.
718  void removeFromParent();
719 
720  /// This method unlinks 'this' from the containing basic block and deletes it.
721  ///
722  /// \returns an iterator pointing to the element after the erased one
724 
725  /// Returns the underlying instruction, if the recipe is a VPValue or nullptr
726  /// otherwise.
728  return cast<Instruction>(getVPSingleValue()->getUnderlyingValue());
729  }
731  return cast<Instruction>(getVPSingleValue()->getUnderlyingValue());
732  }
733 
734  /// Method to support type inquiry through isa, cast, and dyn_cast.
735  static inline bool classof(const VPDef *D) {
736  // All VPDefs are also VPRecipeBases.
737  return true;
738  }
739 
740  static inline bool classof(const VPUser *U) {
741  return U->getVPUserID() == VPUser::VPUserID::Recipe;
742  }
743 
744  /// Returns true if the recipe may have side-effects.
745  bool mayHaveSideEffects() const;
746 
747  /// Returns true for PHI-like recipes.
748  bool isPhi() const {
749  return getVPDefID() >= VPFirstPHISC && getVPDefID() <= VPLastPHISC;
750  }
751 
752  /// Returns true if the recipe may read from memory.
753  bool mayReadFromMemory() const;
754 
755  /// Returns true if the recipe may write to memory.
756  bool mayWriteToMemory() const;
757 
758  /// Returns true if the recipe may read from or write to memory.
759  bool mayReadOrWriteMemory() const {
760  return mayReadFromMemory() || mayWriteToMemory();
761  }
762 };
763 
764 inline bool VPUser::classof(const VPDef *Def) {
765  return Def->getVPDefID() == VPRecipeBase::VPInstructionSC ||
766  Def->getVPDefID() == VPRecipeBase::VPWidenSC ||
767  Def->getVPDefID() == VPRecipeBase::VPWidenCallSC ||
768  Def->getVPDefID() == VPRecipeBase::VPWidenSelectSC ||
769  Def->getVPDefID() == VPRecipeBase::VPWidenGEPSC ||
770  Def->getVPDefID() == VPRecipeBase::VPBlendSC ||
771  Def->getVPDefID() == VPRecipeBase::VPInterleaveSC ||
772  Def->getVPDefID() == VPRecipeBase::VPReplicateSC ||
773  Def->getVPDefID() == VPRecipeBase::VPReductionSC ||
774  Def->getVPDefID() == VPRecipeBase::VPBranchOnMaskSC ||
775  Def->getVPDefID() == VPRecipeBase::VPWidenMemoryInstructionSC;
776 }
777 
778 /// This is a concrete Recipe that models a single VPlan-level instruction.
779 /// While as any Recipe it may generate a sequence of IR instructions when
780 /// executed, these instructions would always form a single-def expression as
781 /// the VPInstruction is also a single def-use vertex.
782 class VPInstruction : public VPRecipeBase, public VPValue {
783  friend class VPlanSlp;
784 
785 public:
786  /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
787  enum {
789  Instruction::OtherOpsEnd + 1, // Combines the incoming and previous
790  // values of a first-order recurrence.
799  };
800 
801 private:
802  typedef unsigned char OpcodeTy;
803  OpcodeTy Opcode;
804  FastMathFlags FMF;
805  DebugLoc DL;
806 
807  /// Utility method serving execute(): generates a single instance of the
808  /// modeled instruction.
809  void generateInstruction(VPTransformState &State, unsigned Part);
810 
811 protected:
813 
814 public:
816  : VPRecipeBase(VPRecipeBase::VPInstructionSC, Operands),
817  VPValue(VPValue::VPVInstructionSC, nullptr, this), Opcode(Opcode),
818  DL(DL) {}
819 
820  VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands,
821  DebugLoc DL = {})
823 
824  /// Method to support type inquiry through isa, cast, and dyn_cast.
825  static inline bool classof(const VPValue *V) {
827  }
828 
829  VPInstruction *clone() const {
831  return new VPInstruction(Opcode, Operands, DL);
832  }
833 
834  /// Method to support type inquiry through isa, cast, and dyn_cast.
835  static inline bool classof(const VPDef *R) {
836  return R->getVPDefID() == VPRecipeBase::VPInstructionSC;
837  }
838 
839  /// Extra classof implementations to allow directly casting from VPUser ->
840  /// VPInstruction.
841  static inline bool classof(const VPUser *U) {
842  auto *R = dyn_cast<VPRecipeBase>(U);
843  return R && R->getVPDefID() == VPRecipeBase::VPInstructionSC;
844  }
845  static inline bool classof(const VPRecipeBase *R) {
846  return R->getVPDefID() == VPRecipeBase::VPInstructionSC;
847  }
848 
849  unsigned getOpcode() const { return Opcode; }
850 
851  /// Generate the instruction.
852  /// TODO: We currently execute only per-part unless a specific instance is
853  /// provided.
854  void execute(VPTransformState &State) override;
855 
856 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
857  /// Print the VPInstruction to \p O.
858  void print(raw_ostream &O, const Twine &Indent,
859  VPSlotTracker &SlotTracker) const override;
860 
861  /// Print the VPInstruction to dbgs() (for debugging).
862  LLVM_DUMP_METHOD void dump() const;
863 #endif
864 
865  /// Return true if this instruction may modify memory.
866  bool mayWriteToMemory() const {
867  // TODO: we can use attributes of the called function to rule out memory
868  // modifications.
869  return Opcode == Instruction::Store || Opcode == Instruction::Call ||
870  Opcode == Instruction::Invoke || Opcode == SLPStore;
871  }
872 
873  bool hasResult() const {
874  // CallInst may or may not have a result, depending on the called function.
875  // Conservatively return calls have results for now.
876  switch (getOpcode()) {
877  case Instruction::Ret:
878  case Instruction::Br:
879  case Instruction::Store:
880  case Instruction::Switch:
881  case Instruction::IndirectBr:
882  case Instruction::Resume:
883  case Instruction::CatchRet:
884  case Instruction::Unreachable:
885  case Instruction::Fence:
886  case Instruction::AtomicRMW:
888  return false;
889  default:
890  return true;
891  }
892  }
893 
894  /// Set the fast-math flags.
895  void setFastMathFlags(FastMathFlags FMFNew);
896 };
897 
898 /// VPWidenRecipe is a recipe for producing a copy of vector type its
899 /// ingredient. This recipe covers most of the traditional vectorization cases
900 /// where each ingredient transforms into a vectorized version of itself.
901 class VPWidenRecipe : public VPRecipeBase, public VPValue {
902 public:
903  template <typename IterT>
905  : VPRecipeBase(VPRecipeBase::VPWidenSC, Operands),
907 
908  ~VPWidenRecipe() override = default;
909 
910  /// Method to support type inquiry through isa, cast, and dyn_cast.
911  static inline bool classof(const VPDef *D) {
912  return D->getVPDefID() == VPRecipeBase::VPWidenSC;
913  }
914  static inline bool classof(const VPValue *V) {
915  return V->getVPValueID() == VPValue::VPVWidenSC;
916  }
917 
918  /// Produce widened copies of all Ingredients.
919  void execute(VPTransformState &State) override;
920 
921 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
922  /// Print the recipe.
923  void print(raw_ostream &O, const Twine &Indent,
924  VPSlotTracker &SlotTracker) const override;
925 #endif
926 };
927 
928 /// A recipe for widening Call instructions.
929 class VPWidenCallRecipe : public VPRecipeBase, public VPValue {
930 
931 public:
932  template <typename IterT>
934  : VPRecipeBase(VPRecipeBase::VPWidenCallSC, CallArguments),
936 
937  ~VPWidenCallRecipe() override = default;
938 
939  /// Method to support type inquiry through isa, cast, and dyn_cast.
940  static inline bool classof(const VPDef *D) {
941  return D->getVPDefID() == VPRecipeBase::VPWidenCallSC;
942  }
943 
944  /// Produce a widened version of the call instruction.
945  void execute(VPTransformState &State) override;
946 
947 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
948  /// Print the recipe.
949  void print(raw_ostream &O, const Twine &Indent,
950  VPSlotTracker &SlotTracker) const override;
951 #endif
952 };
953 
954 /// A recipe for widening select instructions.
955 class VPWidenSelectRecipe : public VPRecipeBase, public VPValue {
956 
957  /// Is the condition of the select loop invariant?
958  bool InvariantCond;
959 
960 public:
961  template <typename IterT>
963  bool InvariantCond)
964  : VPRecipeBase(VPRecipeBase::VPWidenSelectSC, Operands),
966  InvariantCond(InvariantCond) {}
967 
968  ~VPWidenSelectRecipe() override = default;
969 
970  /// Method to support type inquiry through isa, cast, and dyn_cast.
971  static inline bool classof(const VPDef *D) {
972  return D->getVPDefID() == VPRecipeBase::VPWidenSelectSC;
973  }
974 
975  /// Produce a widened version of the select instruction.
976  void execute(VPTransformState &State) override;
977 
978 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
979  /// Print the recipe.
980  void print(raw_ostream &O, const Twine &Indent,
981  VPSlotTracker &SlotTracker) const override;
982 #endif
983 };
984 
985 /// A recipe for handling GEP instructions.
986 class VPWidenGEPRecipe : public VPRecipeBase, public VPValue {
987  bool IsPtrLoopInvariant;
988  SmallBitVector IsIndexLoopInvariant;
989 
990 public:
991  template <typename IterT>
993  : VPRecipeBase(VPRecipeBase::VPWidenGEPSC, Operands),
994  VPValue(VPWidenGEPSC, GEP, this),
995  IsIndexLoopInvariant(GEP->getNumIndices(), false) {}
996 
997  template <typename IterT>
999  Loop *OrigLoop)
1000  : VPRecipeBase(VPRecipeBase::VPWidenGEPSC, Operands),
1002  IsIndexLoopInvariant(GEP->getNumIndices(), false) {
1003  IsPtrLoopInvariant = OrigLoop->isLoopInvariant(GEP->getPointerOperand());
1004  for (auto Index : enumerate(GEP->indices()))
1005  IsIndexLoopInvariant[Index.index()] =
1006  OrigLoop->isLoopInvariant(Index.value().get());
1007  }
1008  ~VPWidenGEPRecipe() override = default;
1009 
1010  /// Method to support type inquiry through isa, cast, and dyn_cast.
1011  static inline bool classof(const VPDef *D) {
1012  return D->getVPDefID() == VPRecipeBase::VPWidenGEPSC;
1013  }
1014 
1015  /// Generate the gep nodes.
1016  void execute(VPTransformState &State) override;
1017 
1018 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1019  /// Print the recipe.
1020  void print(raw_ostream &O, const Twine &Indent,
1021  VPSlotTracker &SlotTracker) const override;
1022 #endif
1023 };
1024 
1025 /// A recipe for handling phi nodes of integer and floating-point inductions,
1026 /// producing their vector and scalar values.
1028  PHINode *IV;
1029  const InductionDescriptor &IndDesc;
1030 
1031 public:
1033  const InductionDescriptor &IndDesc)
1034  : VPRecipeBase(VPWidenIntOrFpInductionSC, {Start}), VPValue(IV, this),
1035  IV(IV), IndDesc(IndDesc) {}
1036 
1038  const InductionDescriptor &IndDesc,
1039  TruncInst *Trunc)
1040  : VPRecipeBase(VPWidenIntOrFpInductionSC, {Start}), VPValue(Trunc, this),
1041  IV(IV), IndDesc(IndDesc) {}
1042 
1043  ~VPWidenIntOrFpInductionRecipe() override = default;
1044 
1045  /// Method to support type inquiry through isa, cast, and dyn_cast.
1046  static inline bool classof(const VPDef *D) {
1047  return D->getVPDefID() == VPRecipeBase::VPWidenIntOrFpInductionSC;
1048  }
1049 
1050  /// Generate the vectorized and scalarized versions of the phi node as
1051  /// needed by their users.
1052  void execute(VPTransformState &State) override;
1053 
1054 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1055  /// Print the recipe.
1056  void print(raw_ostream &O, const Twine &Indent,
1057  VPSlotTracker &SlotTracker) const override;
1058 #endif
1059 
1060  /// Returns the start value of the induction.
1062 
1063  /// Returns the first defined value as TruncInst, if it is one or nullptr
1064  /// otherwise.
1066  return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
1067  }
1068  const TruncInst *getTruncInst() const {
1069  return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
1070  }
1071 
1072  /// Returns the induction descriptor for the recipe.
1073  const InductionDescriptor &getInductionDescriptor() const { return IndDesc; }
1074 };
1075 
1076 /// A pure virtual base class for all recipes modeling header phis, including
1077 /// phis for first order recurrences, pointer inductions and reductions. The
1078 /// start value is the first operand of the recipe and the incoming value from
1079 /// the backedge is the second operand.
1080 class VPHeaderPHIRecipe : public VPRecipeBase, public VPValue {
1081 protected:
1082  VPHeaderPHIRecipe(unsigned char VPVID, unsigned char VPDefID, PHINode *Phi,
1083  VPValue *Start = nullptr)
1084  : VPRecipeBase(VPDefID, {}), VPValue(VPVID, Phi, this) {
1085  if (Start)
1086  addOperand(Start);
1087  }
1088 
1089 public:
1090  ~VPHeaderPHIRecipe() override = default;
1091 
1092  /// Method to support type inquiry through isa, cast, and dyn_cast.
1093  static inline bool classof(const VPRecipeBase *B) {
1094  return B->getVPDefID() == VPRecipeBase::VPCanonicalIVPHISC ||
1095  B->getVPDefID() == VPRecipeBase::VPFirstOrderRecurrencePHISC ||
1096  B->getVPDefID() == VPRecipeBase::VPReductionPHISC ||
1097  B->getVPDefID() == VPRecipeBase::VPWidenIntOrFpInductionSC ||
1098  B->getVPDefID() == VPRecipeBase::VPWidenPHISC;
1099  }
1100  static inline bool classof(const VPValue *V) {
1101  return V->getVPValueID() == VPValue::VPVCanonicalIVPHISC ||
1106  }
1107 
1108  /// Generate the phi nodes.
1109  void execute(VPTransformState &State) override = 0;
1110 
1111 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1112  /// Print the recipe.
1113  void print(raw_ostream &O, const Twine &Indent,
1114  VPSlotTracker &SlotTracker) const override = 0;
1115 #endif
1116 
1117  /// Returns the start value of the phi, if one is set.
1119  return getNumOperands() == 0 ? nullptr : getOperand(0);
1120  }
1121 
1122  /// Returns the incoming value from the loop backedge.
1124  return getOperand(1);
1125  }
1126 
1127  /// Returns the backedge value as a recipe. The backedge value is guaranteed
1128  /// to be a recipe.
1130  return cast<VPRecipeBase>(getBackedgeValue()->getDef());
1131  }
1132 };
1133 
1134 /// A recipe for handling header phis that are widened in the vector loop.
1135 /// In the VPlan native path, all incoming VPValues & VPBasicBlock pairs are
1136 /// managed in the recipe directly.
1138  /// List of incoming blocks. Only used in the VPlan native path.
1139  SmallVector<VPBasicBlock *, 2> IncomingBlocks;
1140 
1141 public:
1142  /// Create a new VPWidenPHIRecipe for \p Phi with start value \p Start.
1143  VPWidenPHIRecipe(PHINode *Phi, VPValue *Start = nullptr)
1144  : VPHeaderPHIRecipe(VPVWidenPHISC, VPWidenPHISC, Phi) {
1145  if (Start)
1146  addOperand(Start);
1147  }
1148 
1149  ~VPWidenPHIRecipe() override = default;
1150 
1151  /// Method to support type inquiry through isa, cast, and dyn_cast.
1152  static inline bool classof(const VPRecipeBase *B) {
1153  return B->getVPDefID() == VPRecipeBase::VPWidenPHISC;
1154  }
1155  static inline bool classof(const VPHeaderPHIRecipe *R) {
1156  return R->getVPDefID() == VPRecipeBase::VPWidenPHISC;
1157  }
1158  static inline bool classof(const VPValue *V) {
1159  return V->getVPValueID() == VPValue::VPVWidenPHISC;
1160  }
1161 
1162  /// Generate the phi/select nodes.
1163  void execute(VPTransformState &State) override;
1164 
1165 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1166  /// Print the recipe.
1167  void print(raw_ostream &O, const Twine &Indent,
1168  VPSlotTracker &SlotTracker) const override;
1169 #endif
1170 
1171  /// Adds a pair (\p IncomingV, \p IncomingBlock) to the phi.
1172  void addIncoming(VPValue *IncomingV, VPBasicBlock *IncomingBlock) {
1173  addOperand(IncomingV);
1174  IncomingBlocks.push_back(IncomingBlock);
1175  }
1176 
1177  /// Returns the \p I th incoming VPBasicBlock.
1178  VPBasicBlock *getIncomingBlock(unsigned I) { return IncomingBlocks[I]; }
1179 
1180  /// Returns the \p I th incoming VPValue.
1181  VPValue *getIncomingValue(unsigned I) { return getOperand(I); }
1182 };
1183 
1184 /// A recipe for handling first-order recurrence phis. The start value is the
1185 /// first operand of the recipe and the incoming value from the backedge is the
1186 /// second operand.
1190  VPFirstOrderRecurrencePHISC, Phi, &Start) {}
1191 
1192  /// Method to support type inquiry through isa, cast, and dyn_cast.
1193  static inline bool classof(const VPRecipeBase *R) {
1194  return R->getVPDefID() == VPRecipeBase::VPFirstOrderRecurrencePHISC;
1195  }
1196  static inline bool classof(const VPHeaderPHIRecipe *R) {
1197  return R->getVPDefID() == VPRecipeBase::VPFirstOrderRecurrencePHISC;
1198  }
1199  static inline bool classof(const VPValue *V) {
1201  }
1202 
1203  void execute(VPTransformState &State) override;
1204 
1205 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1206  /// Print the recipe.
1207  void print(raw_ostream &O, const Twine &Indent,
1208  VPSlotTracker &SlotTracker) const override;
1209 #endif
1210 };
1211 
1212 /// A recipe for handling reduction phis. The start value is the first operand
1213 /// of the recipe and the incoming value from the backedge is the second
1214 /// operand.
1216  /// Descriptor for the reduction.
1217  const RecurrenceDescriptor &RdxDesc;
1218 
1219  /// The phi is part of an in-loop reduction.
1220  bool IsInLoop;
1221 
1222  /// The phi is part of an ordered reduction. Requires IsInLoop to be true.
1223  bool IsOrdered;
1224 
1225 public:
1226  /// Create a new VPReductionPHIRecipe for the reduction \p Phi described by \p
1227  /// RdxDesc.
1229  VPValue &Start, bool IsInLoop = false,
1230  bool IsOrdered = false)
1231  : VPHeaderPHIRecipe(VPVReductionPHISC, VPReductionPHISC, Phi, &Start),
1232  RdxDesc(RdxDesc), IsInLoop(IsInLoop), IsOrdered(IsOrdered) {
1233  assert((!IsOrdered || IsInLoop) && "IsOrdered requires IsInLoop");
1234  }
1235 
1236  ~VPReductionPHIRecipe() override = default;
1237 
1238  /// Method to support type inquiry through isa, cast, and dyn_cast.
1239  static inline bool classof(const VPRecipeBase *R) {
1240  return R->getVPDefID() == VPRecipeBase::VPReductionPHISC;
1241  }
1242  static inline bool classof(const VPHeaderPHIRecipe *R) {
1243  return R->getVPDefID() == VPRecipeBase::VPReductionPHISC;
1244  }
1245  static inline bool classof(const VPValue *V) {
1247  }
1248 
1249  /// Generate the phi/select nodes.
1250  void execute(VPTransformState &State) override;
1251 
1252 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1253  /// Print the recipe.
1254  void print(raw_ostream &O, const Twine &Indent,
1255  VPSlotTracker &SlotTracker) const override;
1256 #endif
1257 
1259  return RdxDesc;
1260  }
1261 
1262  /// Returns true, if the phi is part of an ordered reduction.
1263  bool isOrdered() const { return IsOrdered; }
1264 
1265  /// Returns true, if the phi is part of an in-loop reduction.
1266  bool isInLoop() const { return IsInLoop; }
1267 };
1268 
1269 /// A recipe for vectorizing a phi-node as a sequence of mask-based select
1270 /// instructions.
1271 class VPBlendRecipe : public VPRecipeBase, public VPValue {
1272  PHINode *Phi;
1273 
1274 public:
1275  /// The blend operation is a User of the incoming values and of their
1276  /// respective masks, ordered [I0, M0, I1, M1, ...]. Note that a single value
1277  /// might be incoming with a full mask for which there is no VPValue.
1279  : VPRecipeBase(VPBlendSC, Operands),
1280  VPValue(VPValue::VPVBlendSC, Phi, this), Phi(Phi) {
1281  assert(Operands.size() > 0 &&
1282  ((Operands.size() == 1) || (Operands.size() % 2 == 0)) &&
1283  "Expected either a single incoming value or a positive even number "
1284  "of operands");
1285  }
1286 
1287  /// Method to support type inquiry through isa, cast, and dyn_cast.
1288  static inline bool classof(const VPDef *D) {
1289  return D->getVPDefID() == VPRecipeBase::VPBlendSC;
1290  }
1291 
1292  /// Return the number of incoming values, taking into account that a single
1293  /// incoming value has no mask.
1294  unsigned getNumIncomingValues() const { return (getNumOperands() + 1) / 2; }
1295 
1296  /// Return incoming value number \p Idx.
1297  VPValue *getIncomingValue(unsigned Idx) const { return getOperand(Idx * 2); }
1298 
1299  /// Return mask number \p Idx.
1300  VPValue *getMask(unsigned Idx) const { return getOperand(Idx * 2 + 1); }
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 };
1311 
1312 /// VPInterleaveRecipe is a recipe for transforming an interleave group of load
1313 /// or stores into one wide load/store and shuffles. The first operand of a
1314 /// VPInterleave recipe is the address, followed by the stored values, followed
1315 /// by an optional mask.
1317  const InterleaveGroup<Instruction> *IG;
1318 
1319  bool HasMask = false;
1320 
1321 public:
1323  ArrayRef<VPValue *> StoredValues, VPValue *Mask)
1324  : VPRecipeBase(VPInterleaveSC, {Addr}), IG(IG) {
1325  for (unsigned i = 0; i < IG->getFactor(); ++i)
1326  if (Instruction *I = IG->getMember(i)) {
1327  if (I->getType()->isVoidTy())
1328  continue;
1329  new VPValue(I, this);
1330  }
1331 
1332  for (auto *SV : StoredValues)
1333  addOperand(SV);
1334  if (Mask) {
1335  HasMask = true;
1336  addOperand(Mask);
1337  }
1338  }
1339  ~VPInterleaveRecipe() override = default;
1340 
1341  /// Method to support type inquiry through isa, cast, and dyn_cast.
1342  static inline bool classof(const VPDef *D) {
1343  return D->getVPDefID() == VPRecipeBase::VPInterleaveSC;
1344  }
1345 
1346  /// Return the address accessed by this recipe.
1347  VPValue *getAddr() const {
1348  return getOperand(0); // Address is the 1st, mandatory operand.
1349  }
1350 
1351  /// Return the mask used by this recipe. Note that a full mask is represented
1352  /// by a nullptr.
1353  VPValue *getMask() const {
1354  // Mask is optional and therefore the last, currently 2nd operand.
1355  return HasMask ? getOperand(getNumOperands() - 1) : nullptr;
1356  }
1357 
1358  /// Return the VPValues stored by this interleave group. If it is a load
1359  /// interleave group, return an empty ArrayRef.
1361  // The first operand is the address, followed by the stored values, followed
1362  // by an optional mask.
1364  .slice(1, getNumStoreOperands());
1365  }
1366 
1367  /// Generate the wide load or store, and shuffles.
1368  void execute(VPTransformState &State) override;
1369 
1370 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1371  /// Print the recipe.
1372  void print(raw_ostream &O, const Twine &Indent,
1373  VPSlotTracker &SlotTracker) const override;
1374 #endif
1375 
1377 
1378  /// Returns the number of stored operands of this interleave group. Returns 0
1379  /// for load interleave groups.
1380  unsigned getNumStoreOperands() const {
1381  return getNumOperands() - (HasMask ? 2 : 1);
1382  }
1383 };
1384 
1385 /// A recipe to represent inloop reduction operations, performing a reduction on
1386 /// a vector operand into a scalar value, and adding the result to a chain.
1387 /// The Operands are {ChainOp, VecOp, [Condition]}.
1388 class VPReductionRecipe : public VPRecipeBase, public VPValue {
1389  /// The recurrence decriptor for the reduction in question.
1390  const RecurrenceDescriptor *RdxDesc;
1391  /// Pointer to the TTI, needed to create the target reduction
1392  const TargetTransformInfo *TTI;
1393 
1394 public:
1396  VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp,
1397  const TargetTransformInfo *TTI)
1398  : VPRecipeBase(VPRecipeBase::VPReductionSC, {ChainOp, VecOp}),
1399  VPValue(VPValue::VPVReductionSC, I, this), RdxDesc(R), TTI(TTI) {
1400  if (CondOp)
1401  addOperand(CondOp);
1402  }
1403 
1404  ~VPReductionRecipe() override = default;
1405 
1406  /// Method to support type inquiry through isa, cast, and dyn_cast.
1407  static inline bool classof(const VPValue *V) {
1408  return V->getVPValueID() == VPValue::VPVReductionSC;
1409  }
1410 
1411  /// Generate the reduction in the loop
1412  void execute(VPTransformState &State) override;
1413 
1414 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1415  /// Print the recipe.
1416  void print(raw_ostream &O, const Twine &Indent,
1417  VPSlotTracker &SlotTracker) const override;
1418 #endif
1419 
1420  /// The VPValue of the scalar Chain being accumulated.
1421  VPValue *getChainOp() const { return getOperand(0); }
1422  /// The VPValue of the vector value to be reduced.
1423  VPValue *getVecOp() const { return getOperand(1); }
1424  /// The VPValue of the condition for the block.
1425  VPValue *getCondOp() const {
1426  return getNumOperands() > 2 ? getOperand(2) : nullptr;
1427  }
1428 };
1429 
1430 /// VPReplicateRecipe replicates a given instruction producing multiple scalar
1431 /// copies of the original scalar type, one per lane, instead of producing a
1432 /// single copy of widened type for all lanes. If the instruction is known to be
1433 /// uniform only one copy, per lane zero, will be generated.
1434 class VPReplicateRecipe : public VPRecipeBase, public VPValue {
1435  /// Indicator if only a single replica per lane is needed.
1436  bool IsUniform;
1437 
1438  /// Indicator if the replicas are also predicated.
1439  bool IsPredicated;
1440 
1441  /// Indicator if the scalar values should also be packed into a vector.
1442  bool AlsoPack;
1443 
1444 public:
1445  template <typename IterT>
1447  bool IsUniform, bool IsPredicated = false)
1448  : VPRecipeBase(VPReplicateSC, Operands), VPValue(VPVReplicateSC, I, this),
1449  IsUniform(IsUniform), IsPredicated(IsPredicated) {
1450  // Retain the previous behavior of predicateInstructions(), where an
1451  // insert-element of a predicated instruction got hoisted into the
1452  // predicated basic block iff it was its only user. This is achieved by
1453  // having predicated instructions also pack their values into a vector by
1454  // default unless they have a replicated user which uses their scalar value.
1455  AlsoPack = IsPredicated && !I->use_empty();
1456  }
1457 
1458  ~VPReplicateRecipe() override = default;
1459 
1460  /// Method to support type inquiry through isa, cast, and dyn_cast.
1461  static inline bool classof(const VPDef *D) {
1462  return D->getVPDefID() == VPRecipeBase::VPReplicateSC;
1463  }
1464 
1465  static inline bool classof(const VPValue *V) {
1466  return V->getVPValueID() == VPValue::VPVReplicateSC;
1467  }
1468 
1469  /// Generate replicas of the desired Ingredient. Replicas will be generated
1470  /// for all parts and lanes unless a specific part and lane are specified in
1471  /// the \p State.
1472  void execute(VPTransformState &State) override;
1473 
1474  void setAlsoPack(bool Pack) { AlsoPack = Pack; }
1475 
1476 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1477  /// Print the recipe.
1478  void print(raw_ostream &O, const Twine &Indent,
1479  VPSlotTracker &SlotTracker) const override;
1480 #endif
1481 
1482  bool isUniform() const { return IsUniform; }
1483 
1484  bool isPacked() const { return AlsoPack; }
1485 
1486  bool isPredicated() const { return IsPredicated; }
1487 };
1488 
1489 /// A recipe for generating conditional branches on the bits of a mask.
1491 public:
1493  : VPRecipeBase(VPBranchOnMaskSC, {}) {
1494  if (BlockInMask) // nullptr means all-one mask.
1495  addOperand(BlockInMask);
1496  }
1497 
1498  /// Method to support type inquiry through isa, cast, and dyn_cast.
1499  static inline bool classof(const VPDef *D) {
1500  return D->getVPDefID() == VPRecipeBase::VPBranchOnMaskSC;
1501  }
1502 
1503  /// Generate the extraction of the appropriate bit from the block mask and the
1504  /// conditional branch.
1505  void execute(VPTransformState &State) override;
1506 
1507 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1508  /// Print the recipe.
1509  void print(raw_ostream &O, const Twine &Indent,
1510  VPSlotTracker &SlotTracker) const override {
1511  O << Indent << "BRANCH-ON-MASK ";
1512  if (VPValue *Mask = getMask())
1513  Mask->printAsOperand(O, SlotTracker);
1514  else
1515  O << " All-One";
1516  }
1517 #endif
1518 
1519  /// Return the mask used by this recipe. Note that a full mask is represented
1520  /// by a nullptr.
1521  VPValue *getMask() const {
1522  assert(getNumOperands() <= 1 && "should have either 0 or 1 operands");
1523  // Mask is optional.
1524  return getNumOperands() == 1 ? getOperand(0) : nullptr;
1525  }
1526 };
1527 
1528 /// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
1529 /// control converges back from a Branch-on-Mask. The phi nodes are needed in
1530 /// order to merge values that are set under such a branch and feed their uses.
1531 /// The phi nodes can be scalar or vector depending on the users of the value.
1532 /// This recipe works in concert with VPBranchOnMaskRecipe.
1533 class VPPredInstPHIRecipe : public VPRecipeBase, public VPValue {
1534 public:
1535  /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
1536  /// nodes after merging back from a Branch-on-Mask.
1538  : VPRecipeBase(VPPredInstPHISC, PredV),
1539  VPValue(VPValue::VPVPredInstPHI, nullptr, this) {}
1540  ~VPPredInstPHIRecipe() override = default;
1541 
1542  /// Method to support type inquiry through isa, cast, and dyn_cast.
1543  static inline bool classof(const VPDef *D) {
1544  return D->getVPDefID() == VPRecipeBase::VPPredInstPHISC;
1545  }
1546 
1547  /// Generates phi nodes for live-outs as needed to retain SSA form.
1548  void execute(VPTransformState &State) override;
1549 
1550 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1551  /// Print the recipe.
1552  void print(raw_ostream &O, const Twine &Indent,
1553  VPSlotTracker &SlotTracker) const override;
1554 #endif
1555 };
1556 
1557 /// A Recipe for widening load/store operations.
1558 /// The recipe uses the following VPValues:
1559 /// - For load: Address, optional mask
1560 /// - For store: Address, stored value, optional mask
1561 /// TODO: We currently execute only per-part unless a specific instance is
1562 /// provided.
1564  Instruction &Ingredient;
1565 
1566  // Whether the loaded-from / stored-to addresses are consecutive.
1567  bool Consecutive;
1568 
1569  // Whether the consecutive loaded/stored addresses are in reverse order.
1570  bool Reverse;
1571 
1572  void setMask(VPValue *Mask) {
1573  if (!Mask)
1574  return;
1575  addOperand(Mask);
1576  }
1577 
1578  bool isMasked() const {
1579  return isStore() ? getNumOperands() == 3 : getNumOperands() == 2;
1580  }
1581 
1582 public:
1584  bool Consecutive, bool Reverse)
1585  : VPRecipeBase(VPWidenMemoryInstructionSC, {Addr}),
1586  VPValue(VPValue::VPVMemoryInstructionSC, &Load, this), Ingredient(Load),
1587  Consecutive(Consecutive), Reverse(Reverse) {
1588  assert((Consecutive || !Reverse) && "Reverse implies consecutive");
1589  setMask(Mask);
1590  }
1591 
1593  VPValue *StoredValue, VPValue *Mask,
1594  bool Consecutive, bool Reverse)
1595  : VPRecipeBase(VPWidenMemoryInstructionSC, {Addr, StoredValue}),
1597  Ingredient(Store), Consecutive(Consecutive), Reverse(Reverse) {
1598  assert((Consecutive || !Reverse) && "Reverse implies consecutive");
1599  setMask(Mask);
1600  }
1601 
1602  /// Method to support type inquiry through isa, cast, and dyn_cast.
1603  static inline bool classof(const VPDef *D) {
1604  return D->getVPDefID() == VPRecipeBase::VPWidenMemoryInstructionSC;
1605  }
1606 
1607  /// Return the address accessed by this recipe.
1608  VPValue *getAddr() const {
1609  return getOperand(0); // Address is the 1st, mandatory operand.
1610  }
1611 
1612  /// Return the mask used by this recipe. Note that a full mask is represented
1613  /// by a nullptr.
1614  VPValue *getMask() const {
1615  // Mask is optional and therefore the last operand.
1616  return isMasked() ? getOperand(getNumOperands() - 1) : nullptr;
1617  }
1618 
1619  /// Returns true if this recipe is a store.
1620  bool isStore() const { return isa<StoreInst>(Ingredient); }
1621 
1622  /// Return the address accessed by this recipe.
1624  assert(isStore() && "Stored value only available for store instructions");
1625  return getOperand(1); // Stored value is the 2nd, mandatory operand.
1626  }
1627 
1628  // Return whether the loaded-from / stored-to addresses are consecutive.
1629  bool isConsecutive() const { return Consecutive; }
1630 
1631  // Return whether the consecutive loaded/stored addresses are in reverse
1632  // order.
1633  bool isReverse() const { return Reverse; }
1634 
1635  /// Generate the wide load/store.
1636  void execute(VPTransformState &State) override;
1637 
1638 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1639  /// Print the recipe.
1640  void print(raw_ostream &O, const Twine &Indent,
1641  VPSlotTracker &SlotTracker) const override;
1642 #endif
1643 };
1644 
1645 /// Canonical scalar induction phi of the vector loop. Starting at the specified
1646 /// start value (either 0 or the resume value when vectorizing the epilogue
1647 /// loop). VPWidenCanonicalIVRecipe represents the vector version of the
1648 /// canonical induction variable.
1650  DebugLoc DL;
1651 
1652 public:
1654  : VPHeaderPHIRecipe(VPValue::VPVCanonicalIVPHISC, VPCanonicalIVPHISC,
1655  nullptr, StartV),
1656  DL(DL) {}
1657 
1658  ~VPCanonicalIVPHIRecipe() override = default;
1659 
1660  /// Method to support type inquiry through isa, cast, and dyn_cast.
1661  static inline bool classof(const VPDef *D) {
1662  return D->getVPDefID() == VPCanonicalIVPHISC;
1663  }
1664 
1665  /// Generate the canonical scalar induction phi of the vector loop.
1666  void execute(VPTransformState &State) override;
1667 
1668 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1669  /// Print the recipe.
1670  void print(raw_ostream &O, const Twine &Indent,
1671  VPSlotTracker &SlotTracker) const override;
1672 #endif
1673 };
1674 
1675 /// A Recipe for widening the canonical induction variable of the vector loop.
1677 public:
1679  : VPRecipeBase(VPWidenCanonicalIVSC, {CanonicalIV}),
1680  VPValue(VPValue::VPVWidenCanonicalIVSC, nullptr, this) {}
1681 
1682  ~VPWidenCanonicalIVRecipe() override = default;
1683 
1684  /// Method to support type inquiry through isa, cast, and dyn_cast.
1685  static inline bool classof(const VPDef *D) {
1686  return D->getVPDefID() == VPRecipeBase::VPWidenCanonicalIVSC;
1687  }
1688 
1689  /// Generate a canonical vector induction variable of the vector loop, with
1690  /// start = {<Part*VF, Part*VF+1, ..., Part*VF+VF-1> for 0 <= Part < UF}, and
1691  /// step = <VF*UF, VF*UF, ..., VF*UF>.
1692  void execute(VPTransformState &State) override;
1693 
1694 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1695  /// Print the recipe.
1696  void print(raw_ostream &O, const Twine &Indent,
1697  VPSlotTracker &SlotTracker) const override;
1698 #endif
1699 };
1700 
1701 /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
1702 /// holds a sequence of zero or more VPRecipe's each representing a sequence of
1703 /// output IR instructions. All PHI-like recipes must come before any non-PHI recipes.
1704 class VPBasicBlock : public VPBlockBase {
1705 public:
1707 
1708 private:
1709  /// The VPRecipes held in the order of output instructions to generate.
1710  RecipeListTy Recipes;
1711 
1712 public:
1713  VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr)
1714  : VPBlockBase(VPBasicBlockSC, Name.str()) {
1715  if (Recipe)
1716  appendRecipe(Recipe);
1717  }
1718 
1719  ~VPBasicBlock() override {
1720  while (!Recipes.empty())
1721  Recipes.pop_back();
1722  }
1723 
1724  /// Instruction iterators...
1729 
1730  //===--------------------------------------------------------------------===//
1731  /// Recipe iterator methods
1732  ///
1733  inline iterator begin() { return Recipes.begin(); }
1734  inline const_iterator begin() const { return Recipes.begin(); }
1735  inline iterator end() { return Recipes.end(); }
1736  inline const_iterator end() const { return Recipes.end(); }
1737 
1738  inline reverse_iterator rbegin() { return Recipes.rbegin(); }
1739  inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); }
1740  inline reverse_iterator rend() { return Recipes.rend(); }
1741  inline const_reverse_iterator rend() const { return Recipes.rend(); }
1742 
1743  inline size_t size() const { return Recipes.size(); }
1744  inline bool empty() const { return Recipes.empty(); }
1745  inline const VPRecipeBase &front() const { return Recipes.front(); }
1746  inline VPRecipeBase &front() { return Recipes.front(); }
1747  inline const VPRecipeBase &back() const { return Recipes.back(); }
1748  inline VPRecipeBase &back() { return Recipes.back(); }
1749 
1750  /// Returns a reference to the list of recipes.
1751  RecipeListTy &getRecipeList() { return Recipes; }
1752 
1753  /// Returns a pointer to a member of the recipe list.
1755  return &VPBasicBlock::Recipes;
1756  }
1757 
1758  /// Method to support type inquiry through isa, cast, and dyn_cast.
1759  static inline bool classof(const VPBlockBase *V) {
1760  return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC;
1761  }
1762 
1763  void insert(VPRecipeBase *Recipe, iterator InsertPt) {
1764  assert(Recipe && "No recipe to append.");
1765  assert(!Recipe->Parent && "Recipe already in VPlan");
1766  Recipe->Parent = this;
1767  Recipes.insert(InsertPt, Recipe);
1768  }
1769 
1770  /// Augment the existing recipes of a VPBasicBlock with an additional
1771  /// \p Recipe as the last recipe.
1772  void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); }
1773 
1774  /// The method which generates the output IR instructions that correspond to
1775  /// this VPBasicBlock, thereby "executing" the VPlan.
1776  void execute(struct VPTransformState *State) override;
1777 
1778  /// Return the position of the first non-phi node recipe in the block.
1780 
1781  /// Returns an iterator range over the PHI-like recipes in the block.
1783  return make_range(begin(), getFirstNonPhi());
1784  }
1785 
1786  void dropAllReferences(VPValue *NewValue) override;
1787 
1788  /// Split current block at \p SplitAt by inserting a new block between the
1789  /// current block and its successors and moving all recipes starting at
1790  /// SplitAt to the new block. Returns the new block.
1791  VPBasicBlock *splitAt(iterator SplitAt);
1792 
1793 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1794  /// Print this VPBsicBlock to \p O, prefixing all lines with \p Indent. \p
1795  /// SlotTracker is used to print unnamed VPValue's using consequtive numbers.
1796  ///
1797  /// Note that the numbering is applied to the whole VPlan, so printing
1798  /// individual blocks is consistent with the whole VPlan printing.
1799  void print(raw_ostream &O, const Twine &Indent,
1800  VPSlotTracker &SlotTracker) const override;
1801  using VPBlockBase::print; // Get the print(raw_stream &O) version.
1802 #endif
1803 
1804 private:
1805  /// Create an IR BasicBlock to hold the output instructions generated by this
1806  /// VPBasicBlock, and return it. Update the CFGState accordingly.
1807  BasicBlock *createEmptyBasicBlock(VPTransformState::CFGState &CFG);
1808 };
1809 
1810 /// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks
1811 /// which form a Single-Entry-Single-Exit subgraph of the output IR CFG.
1812 /// A VPRegionBlock may indicate that its contents are to be replicated several
1813 /// times. This is designed to support predicated scalarization, in which a
1814 /// scalar if-then code structure needs to be generated VF * UF times. Having
1815 /// this replication indicator helps to keep a single model for multiple
1816 /// candidate VF's. The actual replication takes place only once the desired VF
1817 /// and UF have been determined.
1818 class VPRegionBlock : public VPBlockBase {
1819  /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock.
1820  VPBlockBase *Entry;
1821 
1822  /// Hold the Single Exit of the SESE region modelled by the VPRegionBlock.
1823  VPBlockBase *Exit;
1824 
1825  /// An indicator whether this region is to generate multiple replicated
1826  /// instances of output IR corresponding to its VPBlockBases.
1827  bool IsReplicator;
1828 
1829 public:
1831  const std::string &Name = "", bool IsReplicator = false)
1832  : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exit(Exit),
1833  IsReplicator(IsReplicator) {
1834  assert(Entry->getPredecessors().empty() && "Entry block has predecessors.");
1835  assert(Exit->getSuccessors().empty() && "Exit block has successors.");
1836  Entry->setParent(this);
1837  Exit->setParent(this);
1838  }
1839  VPRegionBlock(const std::string &Name = "", bool IsReplicator = false)
1840  : VPBlockBase(VPRegionBlockSC, Name), Entry(nullptr), Exit(nullptr),
1841  IsReplicator(IsReplicator) {}
1842 
1843  ~VPRegionBlock() override {
1844  if (Entry) {
1845  VPValue DummyValue;
1846  Entry->dropAllReferences(&DummyValue);
1847  deleteCFG(Entry);
1848  }
1849  }
1850 
1851  /// Method to support type inquiry through isa, cast, and dyn_cast.
1852  static inline bool classof(const VPBlockBase *V) {
1853  return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC;
1854  }
1855 
1856  const VPBlockBase *getEntry() const { return Entry; }
1857  VPBlockBase *getEntry() { return Entry; }
1858 
1859  /// Set \p EntryBlock as the entry VPBlockBase of this VPRegionBlock. \p
1860  /// EntryBlock must have no predecessors.
1861  void setEntry(VPBlockBase *EntryBlock) {
1862  assert(EntryBlock->getPredecessors().empty() &&
1863  "Entry block cannot have predecessors.");
1864  Entry = EntryBlock;
1865  EntryBlock->setParent(this);
1866  }
1867 
1868  // FIXME: DominatorTreeBase is doing 'A->getParent()->front()'. 'front' is a
1869  // specific interface of llvm::Function, instead of using
1870  // GraphTraints::getEntryNode. We should add a new template parameter to
1871  // DominatorTreeBase representing the Graph type.
1872  VPBlockBase &front() const { return *Entry; }
1873 
1874  const VPBlockBase *getExit() const { return Exit; }
1875  VPBlockBase *getExit() { return Exit; }
1876 
1877  /// Set \p ExitBlock as the exit VPBlockBase of this VPRegionBlock. \p
1878  /// ExitBlock must have no successors.
1879  void setExit(VPBlockBase *ExitBlock) {
1880  assert(ExitBlock->getSuccessors().empty() &&
1881  "Exit block cannot have successors.");
1882  Exit = ExitBlock;
1883  ExitBlock->setParent(this);
1884  }
1885 
1886  /// An indicator whether this region is to generate multiple replicated
1887  /// instances of output IR corresponding to its VPBlockBases.
1888  bool isReplicator() const { return IsReplicator; }
1889 
1890  /// The method which generates the output IR instructions that correspond to
1891  /// this VPRegionBlock, thereby "executing" the VPlan.
1892  void execute(struct VPTransformState *State) override;
1893 
1894  void dropAllReferences(VPValue *NewValue) override;
1895 
1896 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1897  /// Print this VPRegionBlock to \p O (recursively), prefixing all lines with
1898  /// \p Indent. \p SlotTracker is used to print unnamed VPValue's using
1899  /// consequtive numbers.
1900  ///
1901  /// Note that the numbering is applied to the whole VPlan, so printing
1902  /// individual regions is consistent with the whole VPlan printing.
1903  void print(raw_ostream &O, const Twine &Indent,
1904  VPSlotTracker &SlotTracker) const override;
1905  using VPBlockBase::print; // Get the print(raw_stream &O) version.
1906 #endif
1907 };
1908 
1909 //===----------------------------------------------------------------------===//
1910 // GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs //
1911 //===----------------------------------------------------------------------===//
1912 
1913 // The following set of template specializations implement GraphTraits to treat
1914 // any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
1915 // that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
1916 // VPBlockBase is a VPRegionBlock, this specialization provides access to its
1917 // successors/predecessors but not to the blocks inside the region.
1918 
1919 template <> struct GraphTraits<VPBlockBase *> {
1922 
1923  static NodeRef getEntryNode(NodeRef N) { return N; }
1924 
1926  return N->getSuccessors().begin();
1927  }
1928 
1930  return N->getSuccessors().end();
1931  }
1932 };
1933 
1934 template <> struct GraphTraits<const VPBlockBase *> {
1935  using NodeRef = const VPBlockBase *;
1937 
1938  static NodeRef getEntryNode(NodeRef N) { return N; }
1939 
1941  return N->getSuccessors().begin();
1942  }
1943 
1945  return N->getSuccessors().end();
1946  }
1947 };
1948 
1949 // Inverse order specialization for VPBasicBlocks. Predecessors are used instead
1950 // of successors for the inverse traversal.
1951 template <> struct GraphTraits<Inverse<VPBlockBase *>> {
1954 
1955  static NodeRef getEntryNode(Inverse<NodeRef> B) { return B.Graph; }
1956 
1958  return N->getPredecessors().begin();
1959  }
1960 
1962  return N->getPredecessors().end();
1963  }
1964 };
1965 
1966 // The following set of template specializations implement GraphTraits to
1967 // treat VPRegionBlock as a graph and recurse inside its nodes. It's important
1968 // to note that the blocks inside the VPRegionBlock are treated as VPBlockBases
1969 // (i.e., no dyn_cast is performed, VPBlockBases specialization is used), so
1970 // there won't be automatic recursion into other VPBlockBases that turn to be
1971 // VPRegionBlocks.
1972 
1973 template <>
1977 
1978  static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
1979 
1981  return nodes_iterator::begin(N->getEntry());
1982  }
1983 
1985  // df_iterator::end() returns an empty iterator so the node used doesn't
1986  // matter.
1987  return nodes_iterator::end(N);
1988  }
1989 };
1990 
1991 template <>
1994  using GraphRef = const VPRegionBlock *;
1996 
1997  static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
1998 
2000  return nodes_iterator::begin(N->getEntry());
2001  }
2002 
2004  // df_iterator::end() returns an empty iterator so the node used doesn't
2005  // matter.
2006  return nodes_iterator::end(N);
2007  }
2008 };
2009 
2010 template <>
2015 
2017  return N.Graph->getExit();
2018  }
2019 
2021  return nodes_iterator::begin(N->getExit());
2022  }
2023 
2025  // df_iterator::end() returns an empty iterator so the node used doesn't
2026  // matter.
2027  return nodes_iterator::end(N);
2028  }
2029 };
2030 
2031 /// Iterator to traverse all successors of a VPBlockBase node. This includes the
2032 /// entry node of VPRegionBlocks. Exit blocks of a region implicitly have their
2033 /// parent region's successors. This ensures all blocks in a region are visited
2034 /// before any blocks in a successor region when doing a reverse post-order
2035 // traversal of the graph.
2036 template <typename BlockPtrTy>
2038  : public iterator_facade_base<VPAllSuccessorsIterator<BlockPtrTy>,
2039  std::forward_iterator_tag, VPBlockBase> {
2040  BlockPtrTy Block;
2041  /// Index of the current successor. For VPBasicBlock nodes, this simply is the
2042  /// index for the successor array. For VPRegionBlock, SuccessorIdx == 0 is
2043  /// used for the region's entry block, and SuccessorIdx - 1 are the indices
2044  /// for the successor array.
2045  size_t SuccessorIdx;
2046 
2047  static BlockPtrTy getBlockWithSuccs(BlockPtrTy Current) {
2048  while (Current && Current->getNumSuccessors() == 0)
2049  Current = Current->getParent();
2050  return Current;
2051  }
2052 
2053  /// Templated helper to dereference successor \p SuccIdx of \p Block. Used by
2054  /// both the const and non-const operator* implementations.
2055  template <typename T1> static T1 deref(T1 Block, unsigned SuccIdx) {
2056  if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
2057  if (SuccIdx == 0)
2058  return R->getEntry();
2059  SuccIdx--;
2060  }
2061 
2062  // For exit blocks, use the next parent region with successors.
2063  return getBlockWithSuccs(Block)->getSuccessors()[SuccIdx];
2064  }
2065 
2066 public:
2067  VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0)
2068  : Block(Block), SuccessorIdx(Idx) {}
2070  : Block(Other.Block), SuccessorIdx(Other.SuccessorIdx) {}
2071 
2073  Block = R.Block;
2074  SuccessorIdx = R.SuccessorIdx;
2075  return *this;
2076  }
2077 
2078  static VPAllSuccessorsIterator end(BlockPtrTy Block) {
2079  BlockPtrTy ParentWithSuccs = getBlockWithSuccs(Block);
2080  unsigned NumSuccessors = ParentWithSuccs
2081  ? ParentWithSuccs->getNumSuccessors()
2082  : Block->getNumSuccessors();
2083 
2084  if (auto *R = dyn_cast<VPRegionBlock>(Block))
2085  return {R, NumSuccessors + 1};
2086  return {Block, NumSuccessors};
2087  }
2088 
2089  bool operator==(const VPAllSuccessorsIterator &R) const {
2090  return Block == R.Block && SuccessorIdx == R.SuccessorIdx;
2091  }
2092 
2093  const VPBlockBase *operator*() const { return deref(Block, SuccessorIdx); }
2094 
2095  BlockPtrTy operator*() { return deref(Block, SuccessorIdx); }
2096 
2098  SuccessorIdx++;
2099  return *this;
2100  }
2101 
2103  VPAllSuccessorsIterator Orig = *this;
2104  SuccessorIdx++;
2105  return Orig;
2106  }
2107 };
2108 
2109 /// Helper for GraphTraits specialization that traverses through VPRegionBlocks.
2110 template <typename BlockTy> class VPBlockRecursiveTraversalWrapper {
2111  BlockTy Entry;
2112 
2113 public:
2115  BlockTy getEntry() { return Entry; }
2116 };
2117 
2118 /// GraphTraits specialization to recursively traverse VPBlockBase nodes,
2119 /// including traversing through VPRegionBlocks. Exit blocks of a region
2120 /// implicitly have their parent region's successors. This ensures all blocks in
2121 /// a region are visited before any blocks in a successor region when doing a
2122 /// reverse post-order traversal of the graph.
2123 template <>
2127 
2128  static NodeRef
2130  return N.getEntry();
2131  }
2132 
2134  return ChildIteratorType(N);
2135  }
2136 
2138  return ChildIteratorType::end(N);
2139  }
2140 };
2141 
2142 template <>
2144  using NodeRef = const VPBlockBase *;
2146 
2147  static NodeRef
2149  return N.getEntry();
2150  }
2151 
2153  return ChildIteratorType(N);
2154  }
2155 
2157  return ChildIteratorType::end(N);
2158  }
2159 };
2160 
2161 /// VPlan models a candidate for vectorization, encoding various decisions take
2162 /// to produce efficient output IR, including which branches, basic-blocks and
2163 /// output IR instructions to generate, and their cost. VPlan holds a
2164 /// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry
2165 /// VPBlock.
2166 class VPlan {
2167  friend class VPlanPrinter;
2168  friend class VPSlotTracker;
2169 
2170  /// Hold the single entry to the Hierarchical CFG of the VPlan.
2171  VPBlockBase *Entry;
2172 
2173  /// Holds the VFs applicable to this VPlan.
2175 
2176  /// Holds the name of the VPlan, for printing.
2177  std::string Name;
2178 
2179  /// Holds all the external definitions created for this VPlan.
2180  // TODO: Introduce a specific representation for external definitions in
2181  // VPlan. External definitions must be immutable and hold a pointer to its
2182  // underlying IR that will be used to implement its structural comparison
2183  // (operators '==' and '<').
2184  SetVector<VPValue *> VPExternalDefs;
2185 
2186  /// Represents the trip count of the original loop, for folding
2187  /// the tail.
2188  VPValue *TripCount = nullptr;
2189 
2190  /// Represents the backedge taken count of the original loop, for folding
2191  /// the tail. It equals TripCount - 1.
2192  VPValue *BackedgeTakenCount = nullptr;
2193 
2194  /// Represents the vector trip count.
2195  VPValue VectorTripCount;
2196 
2197  /// Holds a mapping between Values and their corresponding VPValue inside
2198  /// VPlan.
2199  Value2VPValueTy Value2VPValue;
2200 
2201  /// Contains all VPValues that been allocated by addVPValue directly and need
2202  /// to be free when the plan's destructor is called.
2203  SmallVector<VPValue *, 16> VPValuesToFree;
2204 
2205  /// Holds the VPLoopInfo analysis for this VPlan.
2206  VPLoopInfo VPLInfo;
2207 
2208  /// Indicates whether it is safe use the Value2VPValue mapping or if the
2209  /// mapping cannot be used any longer, because it is stale.
2210  bool Value2VPValueEnabled = true;
2211 
2212 public:
2213  VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {
2214  if (Entry)
2215  Entry->setPlan(this);
2216  }
2217 
2219  if (Entry) {
2220  VPValue DummyValue;
2221  for (VPBlockBase *Block : depth_first(Entry))
2222  Block->dropAllReferences(&DummyValue);
2223 
2224  VPBlockBase::deleteCFG(Entry);
2225  }
2226  for (VPValue *VPV : VPValuesToFree)
2227  delete VPV;
2228  if (TripCount)
2229  delete TripCount;
2230  if (BackedgeTakenCount)
2231  delete BackedgeTakenCount;
2232  for (VPValue *Def : VPExternalDefs)
2233  delete Def;
2234  }
2235 
2236  /// Prepare the plan for execution, setting up the required live-in values.
2237  void prepareToExecute(Value *TripCount, Value *VectorTripCount,
2238  Value *CanonicalIVStartValue, VPTransformState &State);
2239 
2240  /// Generate the IR code for this VPlan.
2241  void execute(struct VPTransformState *State);
2242 
2243  VPBlockBase *getEntry() { return Entry; }
2244  const VPBlockBase *getEntry() const { return Entry; }
2245 
2247  Entry = Block;
2248  Block->setPlan(this);
2249  return Entry;
2250  }
2251 
2252  /// The trip count of the original loop.
2254  if (!TripCount)
2255  TripCount = new VPValue();
2256  return TripCount;
2257  }
2258 
2259  /// The backedge taken count of the original loop.
2261  if (!BackedgeTakenCount)
2262  BackedgeTakenCount = new VPValue();
2263  return BackedgeTakenCount;
2264  }
2265 
2266  /// The vector trip count.
2267  VPValue &getVectorTripCount() { return VectorTripCount; }
2268 
2269  /// Mark the plan to indicate that using Value2VPValue is not safe any
2270  /// longer, because it may be stale.
2271  void disableValue2VPValue() { Value2VPValueEnabled = false; }
2272 
2273  void addVF(ElementCount VF) { VFs.insert(VF); }
2274 
2275  bool hasVF(ElementCount VF) { return VFs.count(VF); }
2276 
2277  const std::string &getName() const { return Name; }
2278 
2279  void setName(const Twine &newName) { Name = newName.str(); }
2280 
2281  /// Add \p VPVal to the pool of external definitions if it's not already
2282  /// in the pool.
2283  void addExternalDef(VPValue *VPVal) { VPExternalDefs.insert(VPVal); }
2284 
2285  void addVPValue(Value *V) {
2286  assert(Value2VPValueEnabled &&
2287  "IR value to VPValue mapping may be out of date!");
2288  assert(V && "Trying to add a null Value to VPlan");
2289  assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
2290  VPValue *VPV = new VPValue(V);
2291  Value2VPValue[V] = VPV;
2292  VPValuesToFree.push_back(VPV);
2293  }
2294 
2295  void addVPValue(Value *V, VPValue *VPV) {
2296  assert(Value2VPValueEnabled && "Value2VPValue mapping may be out of date!");
2297  assert(V && "Trying to add a null Value to VPlan");
2298  assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
2299  Value2VPValue[V] = VPV;
2300  }
2301 
2302  /// Returns the VPValue for \p V. \p OverrideAllowed can be used to disable
2303  /// checking whether it is safe to query VPValues using IR Values.
2304  VPValue *getVPValue(Value *V, bool OverrideAllowed = false) {
2305  assert((OverrideAllowed || isa<Constant>(V) || Value2VPValueEnabled) &&
2306  "Value2VPValue mapping may be out of date!");
2307  assert(V && "Trying to get the VPValue of a null Value");
2308  assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
2309  return Value2VPValue[V];
2310  }
2311 
2312  /// Gets the VPValue or adds a new one (if none exists yet) for \p V. \p
2313  /// OverrideAllowed can be used to disable checking whether it is safe to
2314  /// query VPValues using IR Values.
2315  VPValue *getOrAddVPValue(Value *V, bool OverrideAllowed = false) {
2316  assert((OverrideAllowed || isa<Constant>(V) || Value2VPValueEnabled) &&
2317  "Value2VPValue mapping may be out of date!");
2318  assert(V && "Trying to get or add the VPValue of a null Value");
2319  if (!Value2VPValue.count(V))
2320  addVPValue(V);
2321  return getVPValue(V);
2322  }
2323 
2325  assert(Value2VPValueEnabled &&
2326  "IR value to VPValue mapping may be out of date!");
2327  Value2VPValue.erase(V);
2328  }
2329 
2330  /// Return the VPLoopInfo analysis for this VPlan.
2331  VPLoopInfo &getVPLoopInfo() { return VPLInfo; }
2332  const VPLoopInfo &getVPLoopInfo() const { return VPLInfo; }
2333 
2334 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2335  /// Print this VPlan to \p O.
2336  void print(raw_ostream &O) const;
2337 
2338  /// Print this VPlan in DOT format to \p O.
2339  void printDOT(raw_ostream &O) const;
2340 
2341  /// Dump the plan to stderr (for debugging).
2342  LLVM_DUMP_METHOD void dump() const;
2343 #endif
2344 
2345  /// Returns a range mapping the values the range \p Operands to their
2346  /// corresponding VPValues.
2349  std::function<VPValue *(Value *)> Fn = [this](Value *Op) {
2350  return getOrAddVPValue(Op);
2351  };
2352  return map_range(Operands, Fn);
2353  }
2354 
2355  /// Returns true if \p VPV is uniform after vectorization.
2357  auto RepR = dyn_cast_or_null<VPReplicateRecipe>(VPV->getDef());
2358  return !VPV->getDef() || (RepR && RepR->isUniform());
2359  }
2360 
2361  /// Returns the VPRegionBlock of the vector loop.
2363  return cast<VPRegionBlock>(getEntry());
2364  }
2365 
2366  /// Returns the canonical induction recipe of the vector loop.
2369  if (EntryVPBB->empty()) {
2370  // VPlan native path.
2371  EntryVPBB = cast<VPBasicBlock>(EntryVPBB->getSingleSuccessor());
2372  }
2373  return cast<VPCanonicalIVPHIRecipe>(&*EntryVPBB->begin());
2374  }
2375 
2376 private:
2377  /// Add to the given dominator tree the header block and every new basic block
2378  /// that was created between it and the latch block, inclusive.
2379  static void updateDominatorTree(DominatorTree *DT, BasicBlock *LoopLatchBB,
2380  BasicBlock *LoopPreHeaderBB,
2381  BasicBlock *LoopExitBB);
2382 };
2383 
2384 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2385 /// VPlanPrinter prints a given VPlan to a given output stream. The printing is
2386 /// indented and follows the dot format.
2388  raw_ostream &OS;
2389  const VPlan &Plan;
2390  unsigned Depth = 0;
2391  unsigned TabWidth = 2;
2392  std::string Indent;
2393  unsigned BID = 0;
2395 
2397 
2398  /// Handle indentation.
2399  void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); }
2400 
2401  /// Print a given \p Block of the Plan.
2402  void dumpBlock(const VPBlockBase *Block);
2403 
2404  /// Print the information related to the CFG edges going out of a given
2405  /// \p Block, followed by printing the successor blocks themselves.
2406  void dumpEdges(const VPBlockBase *Block);
2407 
2408  /// Print a given \p BasicBlock, including its VPRecipes, followed by printing
2409  /// its successor blocks.
2410  void dumpBasicBlock(const VPBasicBlock *BasicBlock);
2411 
2412  /// Print a given \p Region of the Plan.
2413  void dumpRegion(const VPRegionBlock *Region);
2414 
2415  unsigned getOrCreateBID(const VPBlockBase *Block) {
2416  return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++;
2417  }
2418 
2419  Twine getOrCreateName(const VPBlockBase *Block);
2420 
2421  Twine getUID(const VPBlockBase *Block);
2422 
2423  /// Print the information related to a CFG edge between two VPBlockBases.
2424  void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden,
2425  const Twine &Label);
2426 
2427 public:
2429  : OS(O), Plan(P), SlotTracker(&P) {}
2430 
2431  LLVM_DUMP_METHOD void dump();
2432 };
2433 
2435  const Value *V;
2436 
2437  VPlanIngredient(const Value *V) : V(V) {}
2438 
2439  void print(raw_ostream &O) const;
2440 };
2441 
2443  I.print(OS);
2444  return OS;
2445 }
2446 
2447 inline raw_ostream &operator<<(raw_ostream &OS, const VPlan &Plan) {
2448  Plan.print(OS);
2449  return OS;
2450 }
2451 #endif
2452 
2453 //===----------------------------------------------------------------------===//
2454 // VPlan Utilities
2455 //===----------------------------------------------------------------------===//
2456 
2457 /// Class that provides utilities for VPBlockBases in VPlan.
2459 public:
2460  VPBlockUtils() = delete;
2461 
2462  /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
2463  /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
2464  /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's
2465  /// successors are moved from \p BlockPtr to \p NewBlock and \p BlockPtr's
2466  /// conditional bit is propagated to \p NewBlock. \p NewBlock must have
2467  /// neither successors nor predecessors.
2468  static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
2469  assert(NewBlock->getSuccessors().empty() &&
2470  NewBlock->getPredecessors().empty() &&
2471  "Can't insert new block with predecessors or successors.");
2472  NewBlock->setParent(BlockPtr->getParent());
2473  SmallVector<VPBlockBase *> Succs(BlockPtr->successors());
2474  for (VPBlockBase *Succ : Succs) {
2475  disconnectBlocks(BlockPtr, Succ);
2476  connectBlocks(NewBlock, Succ);
2477  }
2478  NewBlock->setCondBit(BlockPtr->getCondBit());
2479  BlockPtr->setCondBit(nullptr);
2480  connectBlocks(BlockPtr, NewBlock);
2481  }
2482 
2483  /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
2484  /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
2485  /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
2486  /// parent to \p IfTrue and \p IfFalse. \p Condition is set as the successor
2487  /// selector. \p BlockPtr must have no successors and \p IfTrue and \p IfFalse
2488  /// must have neither successors nor predecessors.
2489  static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
2490  VPValue *Condition, VPBlockBase *BlockPtr) {
2491  assert(IfTrue->getSuccessors().empty() &&
2492  "Can't insert IfTrue with successors.");
2493  assert(IfFalse->getSuccessors().empty() &&
2494  "Can't insert IfFalse with successors.");
2495  BlockPtr->setTwoSuccessors(IfTrue, IfFalse, Condition);
2496  IfTrue->setPredecessors({BlockPtr});
2497  IfFalse->setPredecessors({BlockPtr});
2498  IfTrue->setParent(BlockPtr->getParent());
2499  IfFalse->setParent(BlockPtr->getParent());
2500  }
2501 
2502  /// Connect VPBlockBases \p From and \p To bi-directionally. Append \p To to
2503  /// the successors of \p From and \p From to the predecessors of \p To. Both
2504  /// VPBlockBases must have the same parent, which can be null. Both
2505  /// VPBlockBases can be already connected to other VPBlockBases.
2507  assert((From->getParent() == To->getParent()) &&
2508  "Can't connect two block with different parents");
2509  assert(From->getNumSuccessors() < 2 &&
2510  "Blocks can't have more than two successors.");
2511  From->appendSuccessor(To);
2512  To->appendPredecessor(From);
2513  }
2514 
2515  /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
2516  /// from the successors of \p From and \p From from the predecessors of \p To.
2518  assert(To && "Successor to disconnect is null.");
2519  From->removeSuccessor(To);
2520  To->removePredecessor(From);
2521  }
2522 
2523  /// Try to merge \p Block into its single predecessor, if \p Block is a
2524  /// VPBasicBlock and its predecessor has a single successor. Returns a pointer
2525  /// to the predecessor \p Block was merged into or nullptr otherwise.
2527  auto *VPBB = dyn_cast<VPBasicBlock>(Block);
2528  auto *PredVPBB =
2529  dyn_cast_or_null<VPBasicBlock>(Block->getSinglePredecessor());
2530  if (!VPBB || !PredVPBB || PredVPBB->getNumSuccessors() != 1)
2531  return nullptr;
2532 
2533  for (VPRecipeBase &R : make_early_inc_range(*VPBB))
2534  R.moveBefore(*PredVPBB, PredVPBB->end());
2535  VPBlockUtils::disconnectBlocks(PredVPBB, VPBB);
2536  auto *ParentRegion = cast<VPRegionBlock>(Block->getParent());
2537  if (ParentRegion->getExit() == Block)
2538  ParentRegion->setExit(PredVPBB);
2539  SmallVector<VPBlockBase *> Successors(Block->successors());
2540  for (auto *Succ : Successors) {
2541  VPBlockUtils::disconnectBlocks(Block, Succ);
2542  VPBlockUtils::connectBlocks(PredVPBB, Succ);
2543  }
2544  delete Block;
2545  return PredVPBB;
2546  }
2547 
2548  /// Returns true if the edge \p FromBlock -> \p ToBlock is a back-edge.
2549  static bool isBackEdge(const VPBlockBase *FromBlock,
2550  const VPBlockBase *ToBlock, const VPLoopInfo *VPLI) {
2551  assert(FromBlock->getParent() == ToBlock->getParent() &&
2552  FromBlock->getParent() && "Must be in same region");
2553  const VPLoop *FromLoop = VPLI->getLoopFor(FromBlock);
2554  const VPLoop *ToLoop = VPLI->getLoopFor(ToBlock);
2555  if (!FromLoop || !ToLoop || FromLoop != ToLoop)
2556  return false;
2557 
2558  // A back-edge is a branch from the loop latch to its header.
2559  return ToLoop->isLoopLatch(FromBlock) && ToBlock == ToLoop->getHeader();
2560  }
2561 
2562  /// Returns true if \p Block is a loop latch
2563  static bool blockIsLoopLatch(const VPBlockBase *Block,
2564  const VPLoopInfo *VPLInfo) {
2565  if (const VPLoop *ParentVPL = VPLInfo->getLoopFor(Block))
2566  return ParentVPL->isLoopLatch(Block);
2567 
2568  return false;
2569  }
2570 
2571  /// Count and return the number of succesors of \p PredBlock excluding any
2572  /// backedges.
2573  static unsigned countSuccessorsNoBE(VPBlockBase *PredBlock,
2574  VPLoopInfo *VPLI) {
2575  unsigned Count = 0;
2576  for (VPBlockBase *SuccBlock : PredBlock->getSuccessors()) {
2577  if (!VPBlockUtils::isBackEdge(PredBlock, SuccBlock, VPLI))
2578  Count++;
2579  }
2580  return Count;
2581  }
2582 
2583  /// Return an iterator range over \p Range which only includes \p BlockTy
2584  /// blocks. The accesses are casted to \p BlockTy.
2585  template <typename BlockTy, typename T>
2586  static auto blocksOnly(const T &Range) {
2587  // Create BaseTy with correct const-ness based on BlockTy.
2588  using BaseTy =
2589  typename std::conditional<std::is_const<BlockTy>::value,
2591 
2592  // We need to first create an iterator range over (const) BlocktTy & instead
2593  // of (const) BlockTy * for filter_range to work properly.
2594  auto Mapped =
2595  map_range(Range, [](BaseTy *Block) -> BaseTy & { return *Block; });
2596  auto Filter = make_filter_range(
2597  Mapped, [](BaseTy &Block) { return isa<BlockTy>(&Block); });
2598  return map_range(Filter, [](BaseTy &Block) -> BlockTy * {
2599  return cast<BlockTy>(&Block);
2600  });
2601  }
2602 };
2603 
2606  InterleaveGroupMap;
2607 
2608  /// Type for mapping of instruction based interleave groups to VPInstruction
2609  /// interleave groups
2612 
2613  /// Recursively \p Region and populate VPlan based interleave groups based on
2614  /// \p IAI.
2615  void visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New,
2616  InterleavedAccessInfo &IAI);
2617  /// Recursively traverse \p Block and populate VPlan based interleave groups
2618  /// based on \p IAI.
2619  void visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
2620  InterleavedAccessInfo &IAI);
2621 
2622 public:
2624 
2627  // Avoid releasing a pointer twice.
2628  for (auto &I : InterleaveGroupMap)
2629  DelSet.insert(I.second);
2630  for (auto *Ptr : DelSet)
2631  delete Ptr;
2632  }
2633 
2634  /// Get the interleave group that \p Instr belongs to.
2635  ///
2636  /// \returns nullptr if doesn't have such group.
2639  return InterleaveGroupMap.lookup(Instr);
2640  }
2641 };
2642 
2643 /// Class that maps (parts of) an existing VPlan to trees of combined
2644 /// VPInstructions.
2645 class VPlanSlp {
2646  enum class OpMode { Failed, Load, Opcode };
2647 
2648  /// A DenseMapInfo implementation for using SmallVector<VPValue *, 4> as
2649  /// DenseMap keys.
2650  struct BundleDenseMapInfo {
2651  static SmallVector<VPValue *, 4> getEmptyKey() {
2652  return {reinterpret_cast<VPValue *>(-1)};
2653  }
2654 
2655  static SmallVector<VPValue *, 4> getTombstoneKey() {
2656  return {reinterpret_cast<VPValue *>(-2)};
2657  }
2658 
2659  static unsigned getHashValue(const SmallVector<VPValue *, 4> &V) {
2660  return static_cast<unsigned>(hash_combine_range(V.begin(), V.end()));
2661  }
2662 
2663  static bool isEqual(const SmallVector<VPValue *, 4> &LHS,
2664  const SmallVector<VPValue *, 4> &RHS) {
2665  return LHS == RHS;
2666  }
2667  };
2668 
2669  /// Mapping of values in the original VPlan to a combined VPInstruction.
2670  DenseMap<SmallVector<VPValue *, 4>, VPInstruction *, BundleDenseMapInfo>
2671  BundleToCombined;
2672 
2674 
2675  /// Basic block to operate on. For now, only instructions in a single BB are
2676  /// considered.
2677  const VPBasicBlock &BB;
2678 
2679  /// Indicates whether we managed to combine all visited instructions or not.
2680  bool CompletelySLP = true;
2681 
2682  /// Width of the widest combined bundle in bits.
2683  unsigned WidestBundleBits = 0;
2684 
2685  using MultiNodeOpTy =
2686  typename std::pair<VPInstruction *, SmallVector<VPValue *, 4>>;
2687 
2688  // Input operand bundles for the current multi node. Each multi node operand
2689  // bundle contains values not matching the multi node's opcode. They will
2690  // be reordered in reorderMultiNodeOps, once we completed building a
2691  // multi node.
2692  SmallVector<MultiNodeOpTy, 4> MultiNodeOps;
2693 
2694  /// Indicates whether we are building a multi node currently.
2695  bool MultiNodeActive = false;
2696 
2697  /// Check if we can vectorize Operands together.
2698  bool areVectorizable(ArrayRef<VPValue *> Operands) const;
2699 
2700  /// Add combined instruction \p New for the bundle \p Operands.
2701  void addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New);
2702 
2703  /// Indicate we hit a bundle we failed to combine. Returns nullptr for now.
2704  VPInstruction *markFailed();
2705 
2706  /// Reorder operands in the multi node to maximize sequential memory access
2707  /// and commutative operations.
2708  SmallVector<MultiNodeOpTy, 4> reorderMultiNodeOps();
2709 
2710  /// Choose the best candidate to use for the lane after \p Last. The set of
2711  /// candidates to choose from are values with an opcode matching \p Last's
2712  /// or loads consecutive to \p Last.
2713  std::pair<OpMode, VPValue *> getBest(OpMode Mode, VPValue *Last,
2714  SmallPtrSetImpl<VPValue *> &Candidates,
2716 
2717 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2718  /// Print bundle \p Values to dbgs().
2719  void dumpBundle(ArrayRef<VPValue *> Values);
2720 #endif
2721 
2722 public:
2724 
2725  ~VPlanSlp() = default;
2726 
2727  /// Tries to build an SLP tree rooted at \p Operands and returns a
2728  /// VPInstruction combining \p Operands, if they can be combined.
2730 
2731  /// Return the width of the widest combined bundle in bits.
2732  unsigned getWidestBundleBits() const { return WidestBundleBits; }
2733 
2734  /// Return true if all visited instruction can be combined.
2735  bool isCompletelySLP() const { return CompletelySLP; }
2736 };
2737 } // end namespace llvm
2738 
2739 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
llvm::VPBasicBlock::getRecipeList
RecipeListTy & getRecipeList()
Returns a reference to the list of recipes.
Definition: VPlan.h:1751
llvm::VPRegionBlock::front
VPBlockBase & front() const
Definition: VPlan.h:1872
llvm::VPInstruction::getOpcode
unsigned getOpcode() const
Definition: VPlan.h:849
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:243
llvm::VPRecipeBase::moveAfter
void moveAfter(VPRecipeBase *MovePos)
Unlink this recipe from its current VPBasicBlock and insert it into the VPBasicBlock that MovePos liv...
Definition: VPlan.cpp:628
llvm::VPBlockBase::getSinglePredecessor
VPBlockBase * getSinglePredecessor() const
Definition: VPlan.h:518
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:2526
llvm::VPReductionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1319
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:1614
llvm::VPAllSuccessorsIterator::operator*
const VPBlockBase * operator*() const
Definition: VPlan.h:2093
llvm::VPWidenMemoryInstructionRecipe::VPWidenMemoryInstructionRecipe
VPWidenMemoryInstructionRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask, bool Consecutive, bool Reverse)
Definition: VPlan.h:1583
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:1294
llvm::VPlan::execute
void execute(struct VPTransformState *State)
Generate the IR code for this VPlan.
Definition: VPlan.cpp:891
llvm::VPlanIngredient::print
void print(raw_ostream &O) const
Definition: VPlan.cpp:1199
llvm::Loop::isLoopInvariant
bool isLoopInvariant(const Value *V) const
Return true if the specified value is loop invariant.
Definition: LoopInfo.cpp:64
llvm::VPlanSlp
Class that maps (parts of) an existing VPlan to trees of combined VPInstructions.
Definition: VPlan.h:2645
llvm::VPBlockRecursiveTraversalWrapper::getEntry
BlockTy getEntry()
Definition: VPlan.h:2115
llvm::GraphTraits< const VPBlockBase * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: VPlan.h:1938
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:971
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:510
llvm::VPRegionBlock::VPRegionBlock
VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exit, const std::string &Name="", bool IsReplicator=false)
Definition: VPlan.h:1830
llvm::VPBlendRecipe::getIncomingValue
VPValue * getIncomingValue(unsigned Idx) const
Return incoming value number Idx.
Definition: VPlan.h:1297
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:714
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::VPValue::VPVBlendSC
@ VPVBlendSC
Definition: VPlanValue.h:104
llvm::VPRecipeBase::getUnderlyingInstr
Instruction * getUnderlyingInstr()
Returns the underlying instruction, if the recipe is a VPValue or nullptr otherwise.
Definition: VPlan.h:727
llvm::VPWidenCallRecipe::~VPWidenCallRecipe
~VPWidenCallRecipe() override=default
llvm::VPLoop
Hold analysis information for every loop detected by VPLoopInfo.
Definition: VPlanLoopInfo.h:27
llvm::VPInstruction::SLPStore
@ SLPStore
Definition: VPlan.h:794
llvm::GraphTraits< VPBlockBase * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: VPlan.h:1923
llvm::VPlanIngredient::VPlanIngredient
VPlanIngredient(const Value *V)
Definition: VPlan.h:2437
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:1649
llvm::VPWidenPHIRecipe::VPWidenPHIRecipe
VPWidenPHIRecipe(PHINode *Phi, VPValue *Start=nullptr)
Create a new VPWidenPHIRecipe for Phi with start value Start.
Definition: VPlan.h:1143
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::VPTransformState::CFG
struct llvm::VPTransformState::CFGState CFG
llvm::VPRecipeBase::eraseFromParent
iplist< VPRecipeBase >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: VPlan.cpp:623
llvm::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:1393
llvm::VPPredInstPHIRecipe::execute
void execute(VPTransformState &State) override
Generates phi nodes for live-outs as needed to retain SSA form.
Definition: LoopVectorize.cpp:9867
llvm::VPDef::VPValue
friend class VPValue
Definition: VPlanValue.h:291
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:1299
llvm::VPBlockBase::getEnclosingBlockWithPredecessors
VPBlockBase * getEnclosingBlockWithPredecessors()
Definition: VPlan.cpp:183
llvm::VPAllSuccessorsIterator::operator*
BlockPtrTy operator*()
Definition: VPlan.h:2095
llvm::VPInstruction::classof
static bool classof(const VPUser *U)
Extra classof implementations to allow directly casting from VPUser -> VPInstruction.
Definition: VPlan.h:841
llvm::VPBasicBlock::back
const VPRecipeBase & back() const
Definition: VPlan.h:1747
llvm::VPBlockBase::isLegalToHoistInto
bool isLegalToHoistInto()
Return true if it is legal to hoist instructions into this block.
Definition: VPlan.h:629
llvm::VPBlockBase::getName
const std::string & getName() const
Definition: VPlan.h:468
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:2271
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:2315
llvm::ElementCount
Definition: TypeSize.h:385
llvm::VPUser::removeLastOperand
void removeLastOperand()
Definition: VPlanValue.h:262
llvm::VPWidenCanonicalIVRecipe::VPWidenCanonicalIVRecipe
VPWidenCanonicalIVRecipe(VPCanonicalIVPHIRecipe *CanonicalIV)
Definition: VPlan.h:1678
llvm::VPBasicBlock
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:1704
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
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:197
llvm::getRuntimeVF
Value * getRuntimeVF(IRBuilder<> &B, Type *Ty, ElementCount VF)
Return the runtime value for VF.
Definition: LoopVectorize.cpp:1069
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:1137
BlockTy
std::pair< BasicBlock *, unsigned > BlockTy
A pair of (basic block, score).
Definition: HotColdSplitting.cpp:410
llvm::VPBlockBase::getExitBasicBlock
const VPBasicBlock * getExitBasicBlock() const
Definition: VPlan.cpp:161
llvm::VPHeaderPHIRecipe
A pure virtual base class for all recipes modeling header phis, including phis for first order recurr...
Definition: VPlan.h:1080
llvm::VPlan::prepareToExecute
void prepareToExecute(Value *TripCount, Value *VectorTripCount, Value *CanonicalIVStartValue, VPTransformState &State)
Prepare the plan for execution, setting up the required live-in values.
Definition: VPlan.cpp:843
llvm::VPWidenIntOrFpInductionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1254
llvm::VPlanPrinter::dump
LLVM_DUMP_METHOD void dump()
Definition: VPlan.cpp:1090
llvm::VPPredInstPHIRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1543
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1177
llvm::VPCanonicalIVPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1385
llvm::VPWidenIntOrFpInductionRecipe::~VPWidenIntOrFpInductionRecipe
~VPWidenIntOrFpInductionRecipe() override=default
llvm::VPValue::VPVWidenIntOrFpInductionSC
@ VPVWidenIntOrFpInductionSC
Definition: VPlanValue.h:108
llvm::VPInterleaveRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: LoopVectorize.cpp:9452
ilist.h
llvm::VPValue::VPVCanonicalIVPHISC
@ VPVCanonicalIVPHISC
Definition: VPlanValue.h:105
llvm::VPDef::getVPSingleValue
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
Definition: VPlanValue.h:362
llvm::VPBasicBlock::end
const_iterator end() const
Definition: VPlan.h:1736
llvm::VPTransformState::get
Value * get(VPValue *Def, unsigned Part)
Get the generated Value for a given VPValue and a given Part.
Definition: LoopVectorize.cpp:10090
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:2080
llvm::VPRegionBlock::dropAllReferences
void dropAllReferences(VPValue *NewValue) override
Replace all operands of VPUsers in the block with NewValue and also replaces all uses of VPValues def...
Definition: VPlan.cpp:440
llvm::ilist_node_with_parent
An ilist node that can access its parent list.
Definition: ilist_node.h:256
llvm::VPInterleavedAccessInfo
Definition: VPlan.h:2604
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:9841
llvm::VPBlockBase::VPBlockBase
VPBlockBase(const unsigned char SC, const std::string &N)
Definition: VPlan.h:454
llvm::GraphTraits< VPRegionBlock * >::nodes_begin
static nodes_iterator nodes_begin(GraphRef N)
Definition: VPlan.h:1980
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:1322
llvm::VPLane::Kind::ScalableLast
@ ScalableLast
For ScalableLast, Lane is the offset from the start of the last N-element subvector in a scalable vec...
llvm::IRBuilder<>
llvm::GraphTraits< const VPBlockBase * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:1944
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::GraphTraits< VPBlockRecursiveTraversalWrapper< VPBlockBase * > >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:2133
llvm::VPInstruction::setFastMathFlags
void setFastMathFlags(FastMathFlags FMFNew)
Set the fast-math flags.
Definition: VPlan.cpp:833
llvm::VPReductionPHIRecipe
A recipe for handling reduction phis.
Definition: VPlan.h:1215
llvm::VPTransformState::set
void set(VPValue *Def, Value *V, unsigned Part)
Set the generated Value for a given VPValue and a given Part.
Definition: VPlan.h:259
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::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:181
llvm::VPInterleaveRecipe::~VPInterleaveRecipe
~VPInterleaveRecipe() override=default
llvm::VPRecipeBase::getUnderlyingInstr
const Instruction * getUnderlyingInstr() const
Definition: VPlan.h:730
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
llvm::VPBlendRecipe::execute
void execute(VPTransformState &State) override
Generate the phi/select nodes.
Definition: LoopVectorize.cpp:9715
llvm::VPReductionRecipe::VPReductionRecipe
VPReductionRecipe(const RecurrenceDescriptor *R, Instruction *I, VPValue *ChainOp, VPValue *VecOp, VPValue *CondOp, const TargetTransformInfo *TTI)
Definition: VPlan.h:1395
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:1533
llvm::VPBasicBlock::dropAllReferences
void dropAllReferences(VPValue *NewValue) override
Replace all operands of VPUsers in the block with NewValue and also replaces all uses of VPValues def...
Definition: VPlan.cpp:363
llvm::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:2367
DenseMap.h
llvm::VPWidenIntOrFpInductionRecipe::getTruncInst
TruncInst * getTruncInst()
Returns the first defined value as TruncInst, if it is one or nullptr otherwise.
Definition: VPlan.h:1065
llvm::VPLane::getAsRuntimeExpr
Value * getAsRuntimeExpr(IRBuilder<> &Builder, const ElementCount &VF) const
Returns an expression describing the lane index that can be used at runtime.
Definition: VPlan.cpp:63
llvm::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:236
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:227
llvm::GraphTraits< Inverse< VPRegionBlock * > >::getEntryNode
static NodeRef getEntryNode(Inverse< GraphRef > N)
Definition: VPlan.h:2016
llvm::VPBlockBase::getHierarchicalPredecessors
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:558
T1
#define T1
Definition: Mips16ISelLowering.cpp:340
llvm::VPInterleaveRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1342
llvm::VPInstruction::BranchOnCount
@ BranchOnCount
Definition: VPlan.h:798
llvm::VPWidenIntOrFpInductionRecipe::VPWidenIntOrFpInductionRecipe
VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, const InductionDescriptor &IndDesc, TruncInst *Trunc)
Definition: VPlan.h:1037
llvm::VPBlockUtils
Class that provides utilities for VPBlockBases in VPlan.
Definition: VPlan.h:2458
llvm::Optional
Definition: APInt.h:33
llvm::VPUser::op_begin
operand_iterator op_begin()
Definition: VPlanValue.h:272
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:145
llvm::VPlan::getEntry
const VPBlockBase * getEntry() const
Definition: VPlan.h:2244
llvm::VPWidenMemoryInstructionRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1360
llvm::VPWidenPHIRecipe::~VPWidenPHIRecipe
~VPWidenPHIRecipe() override=default
llvm::mapped_iterator
Definition: STLExtras.h:332
llvm::VPValue::VPVReductionSC
@ VPVReductionSC
Definition: VPlanValue.h:95
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::VPReplicateRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1461
llvm::VPWidenCallRecipe
A recipe for widening Call instructions.
Definition: VPlan.h:929
llvm::VPInstruction::CanonicalIVIncrementNUW
@ CanonicalIVIncrementNUW
Definition: VPlan.h:797
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::VPWidenMemoryInstructionRecipe::VPWidenMemoryInstructionRecipe
VPWidenMemoryInstructionRecipe(StoreInst &Store, VPValue *Addr, VPValue *StoredValue, VPValue *Mask, bool Consecutive, bool Reverse)
Definition: VPlan.h:1592
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
llvm::LoopBase::isLoopLatch
bool isLoopLatch(const BlockT *BB) const
Definition: LoopInfo.h:239
llvm::VPUser::operands
operand_range operands()
Definition: VPlanValue.h:276
llvm::VPUser::VPUserID
VPUserID
Subclass identifier (for isa/dyn_cast).
Definition: VPlanValue.h:202
RHS
Value * RHS
Definition: X86PartialReduction.cpp:74
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:1856
llvm::VPAllSuccessorsIterator
Iterator to traverse all successors of a VPBlockBase node.
Definition: VPlan.h:2037
llvm::FastMathFlags
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:165
llvm::VPValue::VPVWidenCanonicalIVSC
@ VPVWidenCanonicalIVSC
Definition: VPlanValue.h:99
llvm::VPValue::VPVPredInstPHI
@ VPVPredInstPHI
Definition: VPlanValue.h:109
llvm::VPWidenIntOrFpInductionRecipe::VPWidenIntOrFpInductionRecipe
VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start, const InductionDescriptor &IndDesc)
Definition: VPlan.h:1032
llvm::VPTransformState::hasScalarValue
bool hasScalarValue(VPValue *Def, VPIteration Instance)
Definition: VPlan.h:248
llvm::BitmaskEnumDetail::Mask
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::VPInstruction::mayWriteToMemory
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
Definition: VPlan.h:866
VPlanValue.h
llvm::VPReplicateRecipe::isPacked
bool isPacked() const
Definition: VPlan.h:1484
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:2148
llvm::iplist
An intrusive list with ownership and callbacks specified/controlled by ilist_traits,...
Definition: ilist.h:390
llvm::VPReductionRecipe
A recipe to represent inloop reduction operations, performing a reduction on a vector operand into a ...
Definition: VPlan.h:1388
llvm::VPReductionPHIRecipe::~VPReductionPHIRecipe
~VPReductionPHIRecipe() override=default
llvm::isEqual
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)
Definition: GCNRegPressure.cpp:55
DepthFirstIterator.h
llvm::VPWidenPHIRecipe::execute
void execute(VPTransformState &State) override
Generate the phi/select nodes.
Definition: LoopVectorize.cpp:9710
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::VPBlockBase::setPredicate
void setPredicate(VPValue *Pred)
Set the block's predicate.
Definition: VPlan.cpp:209
llvm::VPInterleaveRecipe::getInterleaveGroup
const InterleaveGroup< Instruction > * getInterleaveGroup()
Definition: VPlan.h:1376
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:207
llvm::VFRange
A range of powers-of-2 vectorization factors with fixed start and adjustable end.
Definition: VPlan.h:78
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::VPBranchOnMaskRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1499
llvm::VPWidenIntOrFpInductionRecipe::getInductionDescriptor
const InductionDescriptor & getInductionDescriptor() const
Returns the induction descriptor for the recipe.
Definition: VPlan.h:1073
llvm::VPDef
This class augments a recipe with a set of VPValues defined by the recipe.
Definition: VPlanValue.h:290
llvm::VPRecipeBase::mayWriteToMemory
bool mayWriteToMemory() const
Returns true if the recipe may write to memory.
Definition: VPlan.cpp:511
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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:9754
llvm::SmallBitVector
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
Definition: SmallBitVector.h:34
llvm::VPPredInstPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1352
llvm::VPReplicateRecipe
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition: VPlan.h:1434
llvm::VPTransformState
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:200
llvm::VPBasicBlock::iterator
RecipeListTy::iterator iterator
Instruction iterators...
Definition: VPlan.h:1725
llvm::VPReductionPHIRecipe::classof
static bool classof(const VPHeaderPHIRecipe *R)
Definition: VPlan.h:1242
LHS
Value * LHS
Definition: X86PartialReduction.cpp:73
llvm::VPBlockBase
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:395
llvm::VPReplicateRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1337
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:1772
llvm::VPlan::hasVF
bool hasVF(ElementCount VF)
Definition: VPlan.h:2275
llvm::VPReductionPHIRecipe::isInLoop
bool isInLoop() const
Returns true, if the phi is part of an in-loop reduction.
Definition: VPlan.h:1266
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:1158
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:825
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:1178
llvm::VPInstruction
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:782
llvm::VPBlockUser::VPBlockUser
VPBlockUser()
Definition: VPlan.h:363
llvm::VPTransformState::ILV
InnerLoopVectorizer * ILV
Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
Definition: VPlan.h:348
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:1003
llvm::VPBlockBase::setPredecessors
void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
Definition: VPlan.h:606
llvm::VPInterleavedAccessInfo::getInterleaveGroup
InterleaveGroup< VPInstruction > * getInterleaveGroup(VPInstruction *Instr) const
Get the interleave group that Instr belongs to.
Definition: VPlan.h:2638
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:334
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:367
llvm::VPReplicateRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:1465
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:503
llvm::VPBlockUtils::insertBlockAfter
static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBase NewBlock after BlockPtr.
Definition: VPlan.h:2468
llvm::VPBasicBlock::getSublistAccess
static RecipeListTy VPBasicBlock::* getSublistAccess(VPRecipeBase *)
Returns a pointer to a member of the recipe list.
Definition: VPlan.h:1754
llvm::VPWidenMemoryInstructionRecipe::isReverse
bool isReverse() const
Definition: VPlan.h:1633
llvm::GraphTraits< const VPBlockBase * >::ChildIteratorType
SmallVectorImpl< VPBlockBase * >::const_iterator ChildIteratorType
Definition: VPlan.h:1936
llvm::VPlanPrinter::VPlanPrinter
VPlanPrinter(raw_ostream &O, const VPlan &P)
Definition: VPlan.h:2428
llvm::VPlan::getVPValue
VPValue * getVPValue(Value *V, bool OverrideAllowed=false)
Returns the VPValue for V.
Definition: VPlan.h:2304
llvm::GraphTraits< Inverse< VPBlockBase * > >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:1961
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:633
llvm::VPBlockBase::getPredecessors
VPBlocksTy & getPredecessors()
Definition: VPlan.h:508
llvm::VPInterleaveRecipe
VPInterleaveRecipe is a recipe for transforming an interleave group of load or stores into one wide l...
Definition: VPlan.h:1316
llvm::createStepForVF
Value * createStepForVF(IRBuilder<> &B, Type *Ty, ElementCount VF, int64_t Step)
Return a value for Step multiplied by VF.
Definition: LoopVectorize.cpp:1061
llvm::VPBranchOnMaskRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.h:1509
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
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:462
false
Definition: StackSlotColoring.cpp:142
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::VPWidenPHIRecipe::getIncomingValue
VPValue * getIncomingValue(unsigned I)
Returns the I th incoming VPValue.
Definition: VPlan.h:1181
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:1413
llvm::VPReductionPHIRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:1245
llvm::VPUser::VPUserID::Recipe
@ Recipe
llvm::GraphTraits< const VPRegionBlock * >::nodes_begin
static nodes_iterator nodes_begin(GraphRef N)
Definition: VPlan.h:1999
llvm::VPHeaderPHIRecipe::getBackedgeRecipe
VPRecipeBase * getBackedgeRecipe()
Returns the backedge value as a recipe.
Definition: VPlan.h:1129
llvm::VPTransformState::DataState::PerPartScalars
DenseMap< VPValue *, ScalarsPerPartValuesTy > PerPartScalars
Definition: VPlan.h:225
llvm::VPInstruction::Not
@ Not
Definition: VPlan.h:791
llvm::Instruction
Definition: Instruction.h:45
llvm::VPReplicateRecipe::~VPReplicateRecipe
~VPReplicateRecipe() override=default
llvm::InterleavedAccessInfo
Drive the analysis of interleaved memory accesses in the loop.
Definition: VectorUtils.h:733
llvm::VPValue::VPVWidenCallSC
@ VPVWidenCallSC
Definition: VPlanValue.h:98
llvm::VPBlockBase::printSuccessors
void printSuccessors(raw_ostream &O, const Twine &Indent) const
Print the successors of this block to O, prefixing all lines with Indent.
Definition: VPlan.cpp:399
llvm::VPValue::VPVReplicateSC
@ VPVReplicateSC
Definition: VPlanValue.h:96
llvm::VPReductionRecipe::execute
void execute(VPTransformState &State) override
Generate the reduction in the loop.
Definition: LoopVectorize.cpp:9760
llvm::VPRegionBlock::execute
void execute(struct VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPRegionBlock,...
Definition: VPlan.cpp:447
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::VPBlockUtils::blocksOnly
static auto blocksOnly(const T &Range)
Return an iterator range over Range which only includes BlockTy blocks.
Definition: VPlan.h:2586
llvm::VPValue
Definition: VPlanValue.h:44
llvm::VPRegionBlock::~VPRegionBlock
~VPRegionBlock() override
Definition: VPlan.h:1843
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:9482
llvm::VPTransformState::CFGState::VPBBsToFix
SmallVector< VPBasicBlock *, 8 > VPBBsToFix
Vector of VPBasicBlocks whose terminator instruction needs to be fixed up at the end of vector code g...
Definition: VPlan.h:328
llvm::VPlanSlp::~VPlanSlp
~VPlanSlp()=default
llvm::VPlan::addExternalDef
void addExternalDef(VPValue *VPVal)
Add VPVal to the pool of external definitions if it's not already in the pool.
Definition: VPlan.h:2283
llvm::VPBlockBase::successors
iterator_range< VPBlockBase ** > successors()
Definition: VPlan.h:505
llvm::VPlanSlp::getWidestBundleBits
unsigned getWidestBundleBits() const
Return the width of the widest combined bundle in bits.
Definition: VPlan.h:2732
llvm::VPlan::getName
const std::string & getName() const
Definition: VPlan.h:2277
DebugLoc.h
SmallPtrSet.h
llvm::VPWidenCanonicalIVRecipe
A Recipe for widening the canonical induction variable of the vector loop.
Definition: VPlan.h:1676
llvm::VPAllSuccessorsIterator::operator++
VPAllSuccessorsIterator & operator++()
Definition: VPlan.h:2097
llvm::InnerLoopVectorizer
InnerLoopVectorizer vectorizes loops which contain only one basic block to a specified vectorization ...
Definition: LoopVectorize.cpp:447
llvm::VPBasicBlock::end
iterator end()
Definition: VPlan.h:1735
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::InterleaveGroup::getMember
InstTy * getMember(uint32_t Index) const
Get the member with the given index Index.
Definition: VectorUtils.h:661
llvm::VPReductionPHIRecipe::classof
static bool classof(const VPRecipeBase *R)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1239
llvm::GraphTraits< const VPBlockBase * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:1940
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:193
llvm::VPWidenCanonicalIVRecipe::~VPWidenCanonicalIVRecipe
~VPWidenCanonicalIVRecipe() override=default
llvm::VPUser::getNumOperands
unsigned getNumOperands() const
Definition: VPlanValue.h:250
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:179
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::VPBasicBlock::empty
bool empty() const
Definition: VPlan.h:1744
llvm::VPCanonicalIVPHIRecipe::~VPCanonicalIVPHIRecipe
~VPCanonicalIVPHIRecipe() override=default
llvm::VPWidenMemoryInstructionRecipe::getAddr
VPValue * getAddr() const
Return the address accessed by this recipe.
Definition: VPlan.h:1608
llvm::VPRegionBlock
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1818
llvm::VPWidenMemoryInstructionRecipe::isStore
bool isStore() const
Returns true if this recipe is a store.
Definition: VPlan.h:1620
llvm::VPBlockBase::getPredecessors
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:507
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:1228
llvm::GraphTraits< VPBlockRecursiveTraversalWrapper< const VPBlockBase * > >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:2156
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:78
llvm::VPBlockBase::getCondBit
VPValue * getCondBit()
Definition: VPlan.cpp:191
llvm::GraphTraits< Inverse< VPBlockBase * > >::getEntryNode
static NodeRef getEntryNode(Inverse< NodeRef > B)
Definition: VPlan.h:1955
llvm::GraphTraits< VPBlockBase * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:1925
llvm::VPInterleaveRecipe::getAddr
VPValue * getAddr() const
Return the address accessed by this recipe.
Definition: VPlan.h:1347
llvm::VPReplicateRecipe::execute
void execute(VPTransformState &State) override
Generate replicas of the desired Ingredient.
Definition: LoopVectorize.cpp:9809
llvm::VPInterleaveRecipe::getStoredValues
ArrayRef< VPValue * > getStoredValues() const
Return the VPValues stored by this interleave group.
Definition: VPlan.h:1360
llvm::VPRecipeBase::VPRecipeBase
VPRecipeBase(const unsigned char SC, ArrayRef< VPValue * > Operands)
Definition: VPlan.h:683
llvm::VPUser::setOperand
void setOperand(unsigned I, VPValue *New)
Definition: VPlanValue.h:256
llvm::VPWidenCanonicalIVRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1685
llvm::VPBlockBase::clearPredecessors
void clearPredecessors()
Remove all the predecessor of this block.
Definition: VPlan.h:613
llvm::VPBlockUser::getSingleOperandOrNull
const VPValue * getSingleOperandOrNull() const
Definition: VPlan.h:371
llvm::VPBlockBase::getNumSuccessors
size_t getNumSuccessors() const
Definition: VPlan.h:522
llvm::GraphTraits< VPBlockRecursiveTraversalWrapper< const VPBlockBase * > >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:2152
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::VPValue::VPVWidenSC
@ VPVWidenSC
Definition: VPlanValue.h:97
llvm::VPRecipeBase::execute
virtual void execute(struct VPTransformState &State)=0
The method which generates the output IR instructions that correspond to this VPRecipe,...
llvm::VPInstruction::classof
static bool classof(const VPRecipeBase *R)
Definition: VPlan.h:845
llvm::VPValue::VPVWidenGEPSC
@ VPVWidenGEPSC
Definition: VPlanValue.h:100
VectorUtils.h
llvm::ClrHandlerType::Filter
@ Filter
llvm::VPInterleaveRecipe::getMask
VPValue * getMask() const
Return the mask used by this recipe.
Definition: VPlan.h:1353
llvm::VPTransformState::CanonicalIV
Value * CanonicalIV
Hold the canonical scalar IV of the vector loop (start=0, step=VF*UF).
Definition: VPlan.h:345
llvm::VPRecipeBase::getParent
const VPBasicBlock * getParent() const
Definition: VPlan.h:693
llvm::VPBasicBlock::rbegin
const_reverse_iterator rbegin() const
Definition: VPlan.h:1739
llvm::VPlan::setName
void setName(const Twine &newName)
Definition: VPlan.h:2279
llvm::VPRecipeBase::removeFromParent
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
Definition: VPlan.cpp:617
llvm::VPBlockBase::getHierarchicalSuccessors
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:542
llvm::VPWidenMemoryInstructionRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1603
llvm::VPPredInstPHIRecipe::~VPPredInstPHIRecipe
~VPPredInstPHIRecipe() override=default
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:206
llvm::VPBranchOnMaskRecipe::VPBranchOnMaskRecipe
VPBranchOnMaskRecipe(VPValue *BlockInMask)
Definition: VPlan.h:1492
llvm::VPRecipeBase::mayHaveSideEffects
bool mayHaveSideEffects() const
Returns true if the recipe may have side-effects.
Definition: VPlan.cpp:573
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:309
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::VPValue::VPVMemoryInstructionSC
@ VPVMemoryInstructionSC
Definition: VPlanValue.h:94
llvm::VPInterleaveRecipe::getNumStoreOperands
unsigned getNumStoreOperands() const
Returns the number of stored operands of this interleave group.
Definition: VPlan.h:1380
llvm::VPReductionRecipe::getCondOp
VPValue * getCondOp() const
The VPValue of the condition for the block.
Definition: VPlan.h:1425
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
VPlanLoopInfo.h
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
llvm::VPlan::isUniformAfterVectorization
bool isUniformAfterVectorization(VPValue *VPV) const
Returns true if VPV is uniform after vectorization.
Definition: VPlan.h:2356
llvm::VPBlockBase::clearSuccessors
void clearSuccessors()
Remove all the successors of this block and set to null its condition bit.
Definition: VPlan.h:616
llvm::VPBlockBase::getSingleHierarchicalSuccessor
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:548
llvm::VPBlockBase::getSingleHierarchicalPredecessor
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:564
llvm::VPWidenGEPRecipe::execute
void execute(VPTransformState &State) override
Generate the gep nodes.
Definition: LoopVectorize.cpp:9626
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::VPRegionBlock::setExit
void setExit(VPBlockBase *ExitBlock)
Set ExitBlock as the exit VPBlockBase of this VPRegionBlock.
Definition: VPlan.h:1879
llvm::VPTransformState::DT
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:337
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:9702
llvm::VPWidenRecipe
VPWidenRecipe is a recipe for producing a copy of vector type its ingredient.
Definition: VPlan.h:901
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:1669
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::VPInstruction::execute
void execute(VPTransformState &State) override
Generate the instruction.
Definition: VPlan.cpp:764
llvm::VPReductionPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1522
llvm::InterleaveGroup::getFactor
uint32_t getFactor() const
Definition: VectorUtils.h:607
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:79
llvm::TruncInst
This class represents a truncation of integer types.
Definition: Instructions.h:4773
llvm::iplist_impl< simple_ilist< VPRecipeBase, Options... >, ilist_traits< VPRecipeBase > >::iterator
base_list_type::iterator iterator
Definition: ilist.h:177
llvm::VPBlockBase::getVPBlockID
unsigned getVPBlockID() const
Definition: VPlan.h:475
llvm::VPBlockBase::dump
LLVM_DUMP_METHOD void dump() const
Dump this VPBlockBase to dbgs().
Definition: VPlan.h:664
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:714
llvm::VPInstruction::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the VPInstruction to O.
Definition: VPlan.cpp:778
llvm::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:1743
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:970
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::VPIteration
VPIteration represents a single point in the iteration space of the output (vectorized and/or unrolle...
Definition: VPlan.h:183
llvm::VPBlockUtils::connectBlocks
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2506
llvm::GraphTraits< Inverse< VPBlockBase * > >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:1957
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:1118
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:933
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:642
llvm::VPHeaderPHIRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:1100
llvm::VPBlendRecipe::getMask
VPValue * getMask(unsigned Idx) const
Return mask number Idx.
Definition: VPlan.h:1300
llvm::VPTransformState::CFGState::PrevVPBB
VPBasicBlock * PrevVPBB
The previous VPBasicBlock visited. Initially set to null.
Definition: VPlan.h:305
llvm::VPValue::VPVWidenSelectSC
@ VPVWidenSelectSC
Definition: VPlanValue.h:101
llvm::VPBlockBase::getNumPredecessors
size_t getNumPredecessors() const
Definition: VPlan.h:523
llvm::VPlan::removeVPValueFor
void removeVPValueFor(Value *V)
Definition: VPlan.h:2324
llvm::VPlan::addVPValue
void addVPValue(Value *V)
Definition: VPlan.h:2285
llvm::VPWidenGEPRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1266
TemplateParamKind::Type
@ Type
llvm::VPWidenMemoryInstructionRecipe::getStoredValue
VPValue * getStoredValue() const
Return the address accessed by this recipe.
Definition: VPlan.h:1623
llvm::VPTransformState::hasAnyVectorValue
bool hasAnyVectorValue(VPValue *Def) const
Definition: VPlan.h:244
llvm::GraphTraits< VPBlockBase * >
Definition: VPlan.h:1919
llvm::VPBasicBlock::VPBasicBlock
VPBasicBlock(const Twine &Name="", VPRecipeBase *Recipe=nullptr)
Definition: VPlan.h:1713
llvm::VPBlockUtils::disconnectBlocks
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2517
IRBuilder.h
llvm::VPlan::getEntry
VPBlockBase * getEntry()
Definition: VPlan.h:2243
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::VPFirstOrderRecurrencePHIRecipe::classof
static bool classof(const VPHeaderPHIRecipe *R)
Definition: VPlan.h:1196
llvm::VPHeaderPHIRecipe::classof
static bool classof(const VPRecipeBase *B)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1093
llvm::VPBasicBlock::back
VPRecipeBase & back()
Definition: VPlan.h:1748
llvm::VPWidenIntOrFpInductionRecipe
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector and ...
Definition: VPlan.h:1027
llvm::GraphTraits< VPRegionBlock * >::getEntryNode
static NodeRef getEntryNode(GraphRef N)
Definition: VPlan.h:1978
llvm::GraphTraits< Inverse< VPRegionBlock * > >::nodes_end
static nodes_iterator nodes_end(GraphRef N)
Definition: VPlan.h:2024
llvm::VPReplicateRecipe::isUniform
bool isUniform() const
Definition: VPlan.h:1482
llvm::VPWidenPHIRecipe::classof
static bool classof(const VPRecipeBase *B)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1152
llvm::VPWidenGEPRecipe
A recipe for handling GEP instructions.
Definition: VPlan.h:986
llvm::VPBasicBlock::execute
void execute(struct VPTransformState *State) override
The method which generates the output IR instructions that correspond to this VPBasicBlock,...
Definition: VPlan.cpp:297
llvm::VPInstruction::hasResult
bool hasResult() const
Definition: VPlan.h:873
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1741
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:83
llvm::VPReplicateRecipe::VPReplicateRecipe
VPReplicateRecipe(Instruction *I, iterator_range< IterT > Operands, bool IsUniform, bool IsPredicated=false)
Definition: VPlan.h:1446
llvm::VPUser::VPUserID::Block
@ Block
llvm::VPlan::~VPlan
~VPlan()
Definition: VPlan.h:2218
llvm::VPWidenMemoryInstructionRecipe
A Recipe for widening load/store operations.
Definition: VPlan.h:1563
llvm::VPInstruction::clone
VPInstruction * clone() const
Definition: VPlan.h:829
llvm::VPBasicBlock::~VPBasicBlock
~VPBasicBlock() override
Definition: VPlan.h:1719
llvm::LinearPolySize::getKnownMinValue
ScalarTy getKnownMinValue() const
Returns the minimum value this size can represent.
Definition: TypeSize.h:296
llvm::VPInstruction::SLPLoad
@ SLPLoad
Definition: VPlan.h:793
llvm::df_iterator
Definition: DepthFirstIterator.h:85
llvm::VPWidenIntOrFpInductionRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1046
llvm::VPWidenRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1246
llvm::VPWidenSelectRecipe
A recipe for widening select instructions.
Definition: VPlan.h:955
llvm::GraphTraits< const VPRegionBlock * >::nodes_end
static nodes_iterator nodes_end(GraphRef N)
Definition: VPlan.h:2003
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
InstructionCost.h
llvm::VPInstruction::classof
static bool classof(const VPDef *R)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:835
llvm::VPCanonicalIVPHIRecipe::VPCanonicalIVPHIRecipe
VPCanonicalIVPHIRecipe(VPValue *StartV, DebugLoc DL)
Definition: VPlan.h:1653
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::VPInstruction::CanonicalIVIncrement
@ CanonicalIVIncrement
Definition: VPlan.h:796
llvm::VPWidenCallRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1216
llvm::VPBlockBase::printAsOperand
void printAsOperand(raw_ostream &OS, bool PrintType) const
Definition: VPlan.h:640
llvm::GraphTraits< const VPBlockBase * >
Definition: VPlan.h:1934
llvm::VPlan::getVectorLoopRegion
VPRegionBlock * getVectorLoopRegion()
Returns the VPRegionBlock of the vector loop.
Definition: VPlan.h:2362
llvm::VPBasicBlock::front
VPRecipeBase & front()
Definition: VPlan.h:1746
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::VPlanIngredient::V
const Value * V
Definition: VPlan.h:2435
llvm::VPFirstOrderRecurrencePHIRecipe::VPFirstOrderRecurrencePHIRecipe
VPFirstOrderRecurrencePHIRecipe(PHINode *Phi, VPValue &Start)
Definition: VPlan.h:1188
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:1086
llvm::VPReductionRecipe::getVecOp
VPValue * getVecOp() const
The VPValue of the vector value to be reduced.
Definition: VPlan.h:1423
llvm::VPBlockBase::getSingleSuccessor
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:512
this
Analysis the ScalarEvolution expression for r is this
Definition: README.txt:8
llvm::VPTransformState::CFGState::VectorPreHeader
BasicBlock * VectorPreHeader
The IR BasicBlock that is the preheader of the vector loop in the output IR.
Definition: VPlan.h:320
llvm::VPUser::addOperand
void addOperand(VPValue *Operand)
Definition: VPlanValue.h:245
llvm::VPInstruction::ActiveLaneMask
@ ActiveLaneMask
Definition: VPlan.h:795
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:933
llvm::VPWidenCallRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:940
llvm::VPLane::Kind
Kind
Kind describes how to interpret Lane.
Definition: VPlan.h:110
llvm::VPTransformState::VPTransformState
VPTransformState(ElementCount VF, unsigned UF, LoopInfo *LI, DominatorTree *DT, IRBuilder<> &Builder, InnerLoopVectorizer *ILV, VPlan *Plan)
Definition: VPlan.h:201
llvm::VPRecipeBase::getParent
VPBasicBlock * getParent()
Definition: VPlan.h:692
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:1374
llvm::VPBlockUtils::countSuccessorsNoBE
static unsigned countSuccessorsNoBE(VPBlockBase *PredBlock, VPLoopInfo *VPLI)
Count and return the number of succesors of PredBlock excluding any backedges.
Definition: VPlan.h:2573
llvm::VPFirstOrderRecurrencePHIRecipe
A recipe for handling first-order recurrence phis.
Definition: VPlan.h:1187
llvm::VPAllSuccessorsIterator::VPAllSuccessorsIterator
VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx=0)
Definition: VPlan.h:2067
llvm::VPBranchOnMaskRecipe
A recipe for generating conditional branches on the bits of a mask.
Definition: VPlan.h:1490
llvm::VPWidenSelectRecipe::execute
void execute(VPTransformState &State) override
Produce a widened version of the select instruction.
Definition: LoopVectorize.cpp:9487
llvm::VPBasicBlock::splitAt
VPBasicBlock * splitAt(iterator SplitAt)
Split current block at SplitAt by inserting a new block between the current block and its successors ...
Definition: VPlan.cpp:373
llvm::VPHeaderPHIRecipe::VPHeaderPHIRecipe
VPHeaderPHIRecipe(unsigned char VPVID, unsigned char VPDefID, PHINode *Phi, VPValue *Start=nullptr)
Definition: VPlan.h:1082
llvm::VPBlockUtils::insertTwoBlocksAfter
static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPValue *Condition, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBases IfTrue and IfFalse after BlockPtr.
Definition: VPlan.h:2489
llvm::VPBlockBase::setOneSuccessor
void setOneSuccessor(VPBlockBase *Successor)
Set a given VPBlockBase Successor as the single successor of this VPBlockBase.
Definition: VPlan.h:585
llvm::VPRegionBlock::getExit
VPBlockBase * getExit()
Definition: VPlan.h:1875
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:180
llvm::VPWidenPHIRecipe::classof
static bool classof(const VPHeaderPHIRecipe *R)
Definition: VPlan.h:1155
llvm::VPValue::VPInstruction
friend class VPInstruction
Definition: VPlanValue.h:47
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:558
llvm::VPBlockBase::getEntryBasicBlock
const VPBasicBlock * getEntryBasicBlock() const
Definition: VPlan.cpp:140
llvm::VPRegionBlock::getEntry
VPBlockBase * getEntry()
Definition: VPlan.h:1857
llvm::VPBasicBlock::classof
static bool classof(const VPBlockBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1759
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:374
llvm::VPRecipeBase::classof
static bool classof(const VPUser *U)
Definition: VPlan.h:740
llvm::VPFirstOrderRecurrencePHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1450
llvm::VPValue::setUnderlyingValue
void setUnderlyingValue(Value *Val)
Definition: VPlanValue.h:77
llvm::VPReplicateRecipe::setAlsoPack
void setAlsoPack(bool Pack)
Definition: VPlan.h:1474
llvm::VPReductionPHIRecipe::getRecurrenceDescriptor
const RecurrenceDescriptor & getRecurrenceDescriptor() const
Definition: VPlan.h:1258
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:229
CFG
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to CFG
Definition: README.txt:39
llvm::VPTransformState::Builder
IRBuilder & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Definition: VPlan.h:340
llvm::VPInstruction::VPInstruction
VPInstruction(unsigned Opcode, ArrayRef< VPValue * > Operands, DebugLoc DL)
Definition: VPlan.h:815
llvm::VPBlockBase::setCondBit
void setCondBit(VPValue *CV)
Set the condition bit selecting the successor.
Definition: VPlan.cpp:199
llvm::VPlan::addVPValue
void addVPValue(Value *V, VPValue *VPV)
Definition: VPlan.h:2295
llvm::GraphTraits< VPRegionBlock * >::nodes_end
static nodes_iterator nodes_end(GraphRef N)
Definition: VPlan.h:1984
llvm::VPBlockBase::setParent
void setParent(VPRegionBlock *P)
Definition: VPlan.h:488
llvm::VPWidenPHIRecipe::addIncoming
void addIncoming(VPValue *IncomingV, VPBasicBlock *IncomingBlock)
Adds a pair (IncomingV, IncomingBlock) to the phi.
Definition: VPlan.h:1172
llvm::VPRecipeBase::VPRecipeBase
VPRecipeBase(const unsigned char SC, iterator_range< IterT > Operands)
Definition: VPlan.h:687
llvm::VPBasicBlock::rend
const_reverse_iterator rend() const
Definition: VPlan.h:1741
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:2348
llvm::VPUser::classof
static bool classof(const VPDef *Recipe)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:764
llvm::VPReductionPHIRecipe::execute
void execute(VPTransformState &State) override
Generate the phi/select nodes.
Definition: VPlan.cpp:1459
llvm::VPBlockUtils::isBackEdge
static bool isBackEdge(const VPBlockBase *FromBlock, const VPBlockBase *ToBlock, const VPLoopInfo *VPLI)
Returns true if the edge FromBlock -> ToBlock is a back-edge.
Definition: VPlan.h:2549
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::VPInstruction::ICmpULE
@ ICmpULE
Definition: VPlan.h:792
llvm::VPBlockBase::print
void print(raw_ostream &O) const
Print plain-text dump of this VPlan to O.
Definition: VPlan.h:654
llvm::VPSlotTracker
This class can be used to assign consecutive numbers to all VPValues in a VPlan and allows querying t...
Definition: VPlanValue.h:412
llvm::map_range
auto map_range(ContainerTy &&C, FuncTy F)
Definition: STLExtras.h:361
llvm::VPBasicBlock::begin
const_iterator begin() const
Definition: VPlan.h:1734
llvm::VPRegionBlock::getExit
const VPBlockBase * getExit() const
Definition: VPlan.h:1874
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::VPRecipeBase::~VPRecipeBase
virtual ~VPRecipeBase()=default
llvm::VPWidenGEPRecipe::VPWidenGEPRecipe
VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range< IterT > Operands, Loop *OrigLoop)
Definition: VPlan.h:998
llvm::VPlanSlp::VPlanSlp
VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB)
Definition: VPlan.h:2723
llvm::VPBlockBase::getParent
VPRegionBlock * getParent()
Definition: VPlan.h:477
llvm::VPAllSuccessorsIterator::operator==
bool operator==(const VPAllSuccessorsIterator &R) const
Definition: VPlan.h:2089
llvm::VPBasicBlock::rbegin
reverse_iterator rbegin()
Definition: VPlan.h:1738
llvm::VPAllSuccessorsIterator::end
static VPAllSuccessorsIterator end(BlockPtrTy Block)
Definition: VPlan.h:2078
llvm::VPWidenGEPRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1011
llvm::Successor
@ Successor
Definition: SIMachineScheduler.h:35
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
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:355
llvm::VPValue::getDef
VPDef * getDef()
Definition: VPlanValue.h:180
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:1839
llvm::VPRecipeBase::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:735
llvm::VPCanonicalIVPHIRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1661
llvm::LoopInfoBase< VPBlockBase, VPLoop >
llvm::VPWidenGEPRecipe::VPWidenGEPRecipe
VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range< IterT > Operands)
Definition: VPlan.h:992
llvm::VPRecipeBase
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:673
llvm::iplist_impl::pop_back
void pop_back()
Definition: ilist.h:318
llvm::VPRegionBlock::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print this VPRegionBlock to O (recursively), prefixing all lines with Indent.
Definition: VPlan.cpp:497
llvm::VPlan::setEntry
VPBlockBase * setEntry(VPBlockBase *Block)
Definition: VPlan.h:2246
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
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::VPBlockBase::getPredicate
VPValue * getPredicate()
Definition: VPlan.cpp:201
llvm::VPAllSuccessorsIterator::VPAllSuccessorsIterator
VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other)
Definition: VPlan.h:2069
llvm::SlotTracker
This class provides computation of slot numbers for LLVM Assembly writing.
Definition: AsmWriter.cpp:653
llvm::VPRecipeBase::mayReadOrWriteMemory
bool mayReadOrWriteMemory() const
Returns true if the recipe may read from or write to memory.
Definition: VPlan.h:759
llvm::VPlan::getVectorTripCount
VPValue & getVectorTripCount()
The vector trip count.
Definition: VPlan.h:2267
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:581
llvm::VPInstruction::setUnderlyingInstr
void setUnderlyingInstr(Instruction *I)
Definition: VPlan.h:812
llvm::VPTransformState::CFGState
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:303
llvm::VPBlockBase::setName
void setName(const Twine &newName)
Definition: VPlan.h:470
llvm::Inverse
Definition: GraphTraits.h:95
llvm::VPBlockUtils::blockIsLoopLatch
static bool blockIsLoopLatch(const VPBlockBase *Block, const VPLoopInfo *VPLInfo)
Returns true if Block is a loop latch.
Definition: VPlan.h:2563
llvm::VPTransformState::CFGState::CFGState
CFGState()=default
llvm::VPBasicBlock::insert
void insert(VPRecipeBase *Recipe, iterator InsertPt)
Definition: VPlan.h:1763
llvm::VPValue::VPVReductionPHISC
@ VPVReductionPHISC
Definition: VPlanValue.h:110
llvm::VPlan::getVPLoopInfo
VPLoopInfo & getVPLoopInfo()
Return the VPLoopInfo analysis for this VPlan.
Definition: VPlan.h:2331
llvm::VPBlendRecipe
A recipe for vectorizing a phi-node as a sequence of mask-based select instructions.
Definition: VPlan.h:1271
llvm::iplist_impl::insert
iterator insert(iterator where, pointer New)
Definition: ilist.h:228
llvm::VPReplicateRecipe::isPredicated
bool isPredicated() const
Definition: VPlan.h:1486
llvm::VPUser
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:199
llvm::VPBlockUser::getSingleOperandOrNull
VPValue * getSingleOperandOrNull()
Definition: VPlan.h:365
llvm::VPFirstOrderRecurrencePHIRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:1199
llvm::RecurrenceDescriptor
The RecurrenceDescriptor is used to identify recurrences variables in a loop.
Definition: IVDescriptors.h:73
llvm::VPValue::VPVFirstOrderRecurrencePHISC
@ VPVFirstOrderRecurrencePHISC
Definition: VPlanValue.h:106
llvm::VPlan::VPlan
VPlan(VPBlockBase *Entry=nullptr)
Definition: VPlan.h:2213
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:1407
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:1278
SmallVector.h
llvm::VPBasicBlock::front
const VPRecipeBase & front() const
Definition: VPlan.h:1745
llvm::VPTransformState::VPValue2Value
VPValue2ValueTy VPValue2Value
Definition: VPlan.h:342
llvm::VPBasicBlock::begin
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:1733
llvm::VPlanSlp::isCompletelySLP
bool isCompletelySLP() const
Return true if all visited instruction can be combined.
Definition: VPlan.h:2735
llvm::VPAllSuccessorsIterator::operator++
VPAllSuccessorsIterator operator++(int X)
Definition: VPlan.h:2102
llvm::VPValue::VPVWidenPHISC
@ VPVWidenPHISC
Definition: VPlanValue.h:107
llvm::VPRegionBlock::setEntry
void setEntry(VPBlockBase *EntryBlock)
Set EntryBlock as the entry VPBlockBase of this VPRegionBlock.
Definition: VPlan.h:1861
llvm::VPAllSuccessorsIterator::operator=
VPAllSuccessorsIterator & operator=(const VPAllSuccessorsIterator &R)
Definition: VPlan.h:2072
llvm::VPInstruction::FirstOrderRecurrenceSplice
@ FirstOrderRecurrenceSplice
Definition: VPlan.h:788
llvm::VPWidenMemoryInstructionRecipe::execute
void execute(VPTransformState &State) override
Generate the wide load/store.
Definition: LoopVectorize.cpp:9913
llvm::VPBlendRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1288
SmallBitVector.h
llvm::VPUser::getOperand
VPValue * getOperand(unsigned N) const
Definition: VPlanValue.h:251
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:542
llvm::iplist_impl< simple_ilist< VPRecipeBase, Options... >, ilist_traits< VPRecipeBase > >::const_iterator
base_list_type::const_iterator const_iterator
Definition: ilist.h:178
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:1852
llvm::VPlan::printDOT
void printDOT(raw_ostream &O) const
Print this VPlan in DOT format to O.
Definition: VPlan.cpp:1028
llvm::VPlan::getOrCreateBackedgeTakenCount
VPValue * getOrCreateBackedgeTakenCount()
The backedge taken count of the original loop.
Definition: VPlan.h:2260
llvm::VPBasicBlock::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print this VPBsicBlock to O, prefixing all lines with Indent.
Definition: VPlan.cpp:411
llvm::VPBlockUtils::VPBlockUtils
VPBlockUtils()=delete
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::VPTransformState::CFGState::LastBB
BasicBlock * LastBB
The last IR BasicBlock in the output IR.
Definition: VPlan.h:313
llvm::PHINode
Definition: Instructions.h:2657
llvm::VPWidenRecipe::VPWidenRecipe
VPWidenRecipe(Instruction &I, iterator_range< IterT > Operands)
Definition: VPlan.h:904
llvm::VPWidenMemoryInstructionRecipe::isConsecutive
bool isConsecutive() const
Definition: VPlan.h:1629
ilist_node.h
llvm::GraphTraits< VPBlockRecursiveTraversalWrapper< VPBlockBase * > >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:2137
llvm::VPFirstOrderRecurrencePHIRecipe::execute
void execute(VPTransformState &State) override
Generate the phi nodes.
Definition: VPlan.cpp:1422
llvm::SmallVectorImpl< VPBlockBase * >
llvm::VPTransformState::CFGState::VPBB2IRBB
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:324
llvm::VPBlockBase::getParent
const VPRegionBlock * getParent() const
Definition: VPlan.h:478
llvm::VPTransformState::Plan
VPlan * Plan
Pointer to the VPlan code is generated for.
Definition: VPlan.h:351
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:343
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:1123
llvm::VPFirstOrderRecurrencePHIRecipe::classof
static bool classof(const VPRecipeBase *R)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1193
llvm::VPlan::getVPLoopInfo
const VPLoopInfo & getVPLoopInfo() const
Definition: VPlan.h:2332
llvm::VPPredInstPHIRecipe::VPPredInstPHIRecipe
VPPredInstPHIRecipe(VPValue *PredV)
Construct a VPPredInstPHIRecipe given PredInst whose value needs a phi nodes after merging back from ...
Definition: VPlan.h:1537
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1478
llvm::VPValue::getVPValueID
unsigned getVPValueID() const
Definition: VPlanValue.h:123
llvm::VPWidenSelectRecipe::VPWidenSelectRecipe
VPWidenSelectRecipe(SelectInst &I, iterator_range< IterT > Operands, bool InvariantCond)
Definition: VPlan.h:962
llvm::VPBranchOnMaskRecipe::getMask
VPValue * getMask() const
Return the mask used by this recipe.
Definition: VPlan.h:1521
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
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::VPBlockBase::deleteCFG
static void deleteCFG(VPBlockBase *Entry)
Delete all blocks reachable from a given VPBlockBase, inclusive.
Definition: VPlan.cpp:213
llvm::VPRegionBlock::isReplicator
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:1888
llvm::GraphTraits
Definition: GraphTraits.h:35
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:1280
llvm::VPInstruction::VPInstruction
VPInstruction(unsigned Opcode, std::initializer_list< VPValue * > Operands, DebugLoc DL={})
Definition: VPlan.h:820
llvm::VPWidenIntOrFpInductionRecipe::getTruncInst
const TruncInst * getTruncInst() const
Definition: VPlan.h:1068
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:1782
llvm::VPBasicBlock::getFirstNonPhi
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
Definition: VPlan.cpp:220
llvm::VPReductionRecipe::getChainOp
VPValue * getChainOp() const
The VPValue of the scalar Chain being accumulated.
Definition: VPlan.h:1421
llvm::VPInterleavedAccessInfo::VPInterleavedAccessInfo
VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI)
Definition: VPlan.cpp:1614
llvm::VPValue::VPVInstructionSC
@ VPVInstructionSC
Definition: VPlanValue.h:93
llvm::VPBlockRecursiveTraversalWrapper
Helper for GraphTraits specialization that traverses through VPRegionBlocks.
Definition: VPlan.h:2110
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::VPWidenRecipe::classof
static bool classof(const VPValue *V)
Definition: VPlan.h:914
llvm::VPWidenRecipe::classof
static bool classof(const VPDef *D)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:911
llvm::VPBlockBase::getSuccessors
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:502
llvm::VPHeaderPHIRecipe::~VPHeaderPHIRecipe
~VPHeaderPHIRecipe() override=default
llvm::GraphTraits< Inverse< VPBlockBase * > >::ChildIteratorType
SmallVectorImpl< VPBlockBase * >::iterator ChildIteratorType
Definition: VPlan.h:1953
llvm::VPBlockRecursiveTraversalWrapper::VPBlockRecursiveTraversalWrapper
VPBlockRecursiveTraversalWrapper(BlockTy Entry)
Definition: VPlan.h:2114
llvm::VPWidenRecipe::~VPWidenRecipe
~VPWidenRecipe() override=default
llvm::VPWidenRecipe::execute
void execute(VPTransformState &State) override
Produce widened copies of all Ingredients.
Definition: LoopVectorize.cpp:9508
llvm::VPDef::getVPDefID
unsigned getVPDefID() const
Definition: VPlanValue.h:394
llvm::VPInstruction::dump
LLVM_DUMP_METHOD void dump() const
Print the VPInstruction to dbgs() (for debugging).
Definition: VPlan.cpp:773
llvm::GraphTraits< VPBlockRecursiveTraversalWrapper< VPBlockBase * > >::getEntryNode
static NodeRef getEntryNode(VPBlockRecursiveTraversalWrapper< VPBlockBase * > N)
Definition: VPlan.h:2129
llvm::VPBasicBlock::rend
reverse_iterator rend()
Definition: VPlan.h:1740
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:1929
llvm::VPlan
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2166
llvm::GraphTraits< Inverse< VPRegionBlock * > >::nodes_begin
static nodes_iterator nodes_begin(GraphRef N)
Definition: VPlan.h:2020
llvm::VPBlockBase::setTwoSuccessors
void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPValue *Condition)
Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.
Definition: VPlan.h:594
llvm::VPInterleavedAccessInfo::~VPInterleavedAccessInfo
~VPInterleavedAccessInfo()
Definition: VPlan.h:2625
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:601
llvm::deref
Binary functor that adapts to any other binary functor after dereferencing operands.
Definition: STLExtras.h:1959
llvm::VPHeaderPHIRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override=0
Print the recipe.
llvm::VPReductionPHIRecipe::isOrdered
bool isOrdered() const
Returns true, if the phi is part of an ordered reduction.
Definition: VPlan.h:1263
llvm::GraphTraits< const VPRegionBlock * >::getEntryNode
static NodeRef getEntryNode(GraphRef N)
Definition: VPlan.h:1997
llvm::VPlan::dump
LLVM_DUMP_METHOD void dump() const
Dump the plan to stderr (for debugging).
Definition: VPlan.cpp:1034
llvm::VPlanIngredient
Definition: VPlan.h:2434
llvm::VPWidenSelectRecipe::print
void print(raw_ostream &O, const Twine &Indent, VPSlotTracker &SlotTracker) const override
Print the recipe.
Definition: VPlan.cpp:1233
llvm::VPRecipeBase::isPhi
bool isPhi() const
Returns true for PHI-like recipes.
Definition: VPlan.h:748
llvm::VPWidenIntOrFpInductionRecipe::getStartValue
VPValue * getStartValue()
Returns the start value of the induction.
Definition: VPlan.h:1061
llvm::VPlanPrinter
VPlanPrinter prints a given VPlan to a given output stream.
Definition: VPlan.h:2387
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:1921
llvm::VPBlockUser
VPUsers instance used by VPBlockBase to manage CondBit and the block predicate.
Definition: VPlan.h:362
llvm::VPRecipeBase::insertAfter
void insertAfter(VPRecipeBase *InsertPos)
Insert an unlinked Recipe into a basic block immediately after the specified Recipe.
Definition: VPlan.cpp:609
llvm::VFRange::Start
const ElementCount Start
Definition: VPlan.h:80
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1198
llvm::VPBlockUser::resetSingleOpUser
void resetSingleOpUser(VPValue *NewVal)
Definition: VPlan.h:378
llvm::VPTransformState::hasVectorValue
bool hasVectorValue(VPValue *Def, unsigned Part)
Definition: VPlan.h:238
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::VPlan::getOrCreateTripCount
VPValue * getOrCreateTripCount()
The trip count of the original loop.
Definition: VPlan.h:2253
llvm::VPHeaderPHIRecipe::execute
void execute(VPTransformState &State) override=0
Generate the phi nodes.
SmallSet.h
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:364
llvm::VPlan::addVF
void addVF(ElementCount VF)
Definition: VPlan.h:2273