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