LLVM  8.0.0svn
VPlan.h
Go to the documentation of this file.
1 //===- VPlan.h - Represent A Vectorizer Plan --------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 /// \file
11 /// This file contains the declarations of the Vectorization Plan base classes:
12 /// 1. VPBasicBlock and VPRegionBlock that inherit from a common pure virtual
13 /// VPBlockBase, together implementing a Hierarchical CFG;
14 /// 2. Specializations of GraphTraits that allow VPBlockBase graphs to be
15 /// treated as proper graphs for generic algorithms;
16 /// 3. Pure virtual VPRecipeBase serving as the base class for recipes contained
17 /// within VPBasicBlocks;
18 /// 4. VPInstruction, a concrete Recipe and VPUser modeling a single planned
19 /// instruction;
20 /// 5. The VPlan class holding a candidate for vectorization;
21 /// 6. The VPlanPrinter class providing a way to print a plan in dot format;
22 /// These are documented in docs/VectorizationPlan.rst.
23 //
24 //===----------------------------------------------------------------------===//
25 
26 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
27 #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
28 
29 #include "VPlanLoopInfo.h"
30 #include "VPlanValue.h"
31 #include "llvm/ADT/DenseMap.h"
33 #include "llvm/ADT/GraphTraits.h"
34 #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"
41 #include "llvm/IR/IRBuilder.h"
42 #include <algorithm>
43 #include <cassert>
44 #include <cstddef>
45 #include <map>
46 #include <string>
47 
48 namespace llvm {
49 
50 class LoopVectorizationLegality;
51 class LoopVectorizationCostModel;
52 class BasicBlock;
53 class DominatorTree;
54 class InnerLoopVectorizer;
55 class InterleaveGroup;
56 class raw_ostream;
57 class Value;
58 class VPBasicBlock;
59 class VPRegionBlock;
60 class VPlan;
61 
62 /// A range of powers-of-2 vectorization factors with fixed start and
63 /// adjustable end. The range includes start and excludes end, e.g.,:
64 /// [1, 9) = {1, 2, 4, 8}
65 struct VFRange {
66  // A power of 2.
67  const unsigned Start;
68 
69  // Need not be a power of 2. If End <= Start range is empty.
70  unsigned End;
71 };
72 
73 using VPlanPtr = std::unique_ptr<VPlan>;
74 
75 /// In what follows, the term "input IR" refers to code that is fed into the
76 /// vectorizer whereas the term "output IR" refers to code that is generated by
77 /// the vectorizer.
78 
79 /// VPIteration represents a single point in the iteration space of the output
80 /// (vectorized and/or unrolled) IR loop.
81 struct VPIteration {
82  /// in [0..UF)
83  unsigned Part;
84 
85  /// in [0..VF)
86  unsigned Lane;
87 };
88 
89 /// This is a helper struct for maintaining vectorization state. It's used for
90 /// mapping values from the original loop to their corresponding values in
91 /// the new loop. Two mappings are maintained: one for vectorized values and
92 /// one for scalarized values. Vectorized values are represented with UF
93 /// vector values in the new loop, and scalarized values are represented with
94 /// UF x VF scalar values in the new loop. UF and VF are the unroll and
95 /// vectorization factors, respectively.
96 ///
97 /// Entries can be added to either map with setVectorValue and setScalarValue,
98 /// which assert that an entry was not already added before. If an entry is to
99 /// replace an existing one, call resetVectorValue and resetScalarValue. This is
100 /// currently needed to modify the mapped values during "fix-up" operations that
101 /// occur once the first phase of widening is complete. These operations include
102 /// type truncation and the second phase of recurrence widening.
103 ///
104 /// Entries from either map can be retrieved using the getVectorValue and
105 /// getScalarValue functions, which assert that the desired value exists.
107  friend struct VPTransformState;
108 
109 private:
110  /// The unroll factor. Each entry in the vector map contains UF vector values.
111  unsigned UF;
112 
113  /// The vectorization factor. Each entry in the scalar map contains UF x VF
114  /// scalar values.
115  unsigned VF;
116 
117  /// The vector and scalar map storage. We use std::map and not DenseMap
118  /// because insertions to DenseMap invalidate its iterators.
121  std::map<Value *, VectorParts> VectorMapStorage;
122  std::map<Value *, ScalarParts> ScalarMapStorage;
123 
124 public:
125  /// Construct an empty map with the given unroll and vectorization factors.
126  VectorizerValueMap(unsigned UF, unsigned VF) : UF(UF), VF(VF) {}
127 
128  /// \return True if the map has any vector entry for \p Key.
129  bool hasAnyVectorValue(Value *Key) const {
130  return VectorMapStorage.count(Key);
131  }
132 
133  /// \return True if the map has a vector entry for \p Key and \p Part.
134  bool hasVectorValue(Value *Key, unsigned Part) const {
135  assert(Part < UF && "Queried Vector Part is too large.");
136  if (!hasAnyVectorValue(Key))
137  return false;
138  const VectorParts &Entry = VectorMapStorage.find(Key)->second;
139  assert(Entry.size() == UF && "VectorParts has wrong dimensions.");
140  return Entry[Part] != nullptr;
141  }
142 
143  /// \return True if the map has any scalar entry for \p Key.
144  bool hasAnyScalarValue(Value *Key) const {
145  return ScalarMapStorage.count(Key);
146  }
147 
148  /// \return True if the map has a scalar entry for \p Key and \p Instance.
149  bool hasScalarValue(Value *Key, const VPIteration &Instance) const {
150  assert(Instance.Part < UF && "Queried Scalar Part is too large.");
151  assert(Instance.Lane < VF && "Queried Scalar Lane is too large.");
152  if (!hasAnyScalarValue(Key))
153  return false;
154  const ScalarParts &Entry = ScalarMapStorage.find(Key)->second;
155  assert(Entry.size() == UF && "ScalarParts has wrong dimensions.");
156  assert(Entry[Instance.Part].size() == VF &&
157  "ScalarParts has wrong dimensions.");
158  return Entry[Instance.Part][Instance.Lane] != nullptr;
159  }
160 
161  /// Retrieve the existing vector value that corresponds to \p Key and
162  /// \p Part.
163  Value *getVectorValue(Value *Key, unsigned Part) {
164  assert(hasVectorValue(Key, Part) && "Getting non-existent value.");
165  return VectorMapStorage[Key][Part];
166  }
167 
168  /// Retrieve the existing scalar value that corresponds to \p Key and
169  /// \p Instance.
170  Value *getScalarValue(Value *Key, const VPIteration &Instance) {
171  assert(hasScalarValue(Key, Instance) && "Getting non-existent value.");
172  return ScalarMapStorage[Key][Instance.Part][Instance.Lane];
173  }
174 
175  /// Set a vector value associated with \p Key and \p Part. Assumes such a
176  /// value is not already set. If it is, use resetVectorValue() instead.
177  void setVectorValue(Value *Key, unsigned Part, Value *Vector) {
178  assert(!hasVectorValue(Key, Part) && "Vector value already set for part");
179  if (!VectorMapStorage.count(Key)) {
180  VectorParts Entry(UF);
181  VectorMapStorage[Key] = Entry;
182  }
183  VectorMapStorage[Key][Part] = Vector;
184  }
185 
186  /// Set a scalar value associated with \p Key and \p Instance. Assumes such a
187  /// value is not already set.
188  void setScalarValue(Value *Key, const VPIteration &Instance, Value *Scalar) {
189  assert(!hasScalarValue(Key, Instance) && "Scalar value already set");
190  if (!ScalarMapStorage.count(Key)) {
191  ScalarParts Entry(UF);
192  // TODO: Consider storing uniform values only per-part, as they occupy
193  // lane 0 only, keeping the other VF-1 redundant entries null.
194  for (unsigned Part = 0; Part < UF; ++Part)
195  Entry[Part].resize(VF, nullptr);
196  ScalarMapStorage[Key] = Entry;
197  }
198  ScalarMapStorage[Key][Instance.Part][Instance.Lane] = Scalar;
199  }
200 
201  /// Reset the vector value associated with \p Key for the given \p Part.
202  /// This function can be used to update values that have already been
203  /// vectorized. This is the case for "fix-up" operations including type
204  /// truncation and the second phase of recurrence vectorization.
205  void resetVectorValue(Value *Key, unsigned Part, Value *Vector) {
206  assert(hasVectorValue(Key, Part) && "Vector value not set for part");
207  VectorMapStorage[Key][Part] = Vector;
208  }
209 
210  /// Reset the scalar value associated with \p Key for \p Part and \p Lane.
211  /// This function can be used to update values that have already been
212  /// scalarized. This is the case for "fix-up" operations including scalar phi
213  /// nodes for scalarized and predicated instructions.
214  void resetScalarValue(Value *Key, const VPIteration &Instance,
215  Value *Scalar) {
216  assert(hasScalarValue(Key, Instance) &&
217  "Scalar value not set for part and lane");
218  ScalarMapStorage[Key][Instance.Part][Instance.Lane] = Scalar;
219  }
220 };
221 
222 /// This class is used to enable the VPlan to invoke a method of ILV. This is
223 /// needed until the method is refactored out of ILV and becomes reusable.
224 struct VPCallback {
225  virtual ~VPCallback() {}
226  virtual Value *getOrCreateVectorValues(Value *V, unsigned Part) = 0;
227 };
228 
229 /// VPTransformState holds information passed down when "executing" a VPlan,
230 /// needed for generating the output IR.
232  VPTransformState(unsigned VF, unsigned UF, LoopInfo *LI, DominatorTree *DT,
234  InnerLoopVectorizer *ILV, VPCallback &Callback)
235  : VF(VF), UF(UF), Instance(), LI(LI), DT(DT), Builder(Builder),
236  ValueMap(ValueMap), ILV(ILV), Callback(Callback) {}
237 
238  /// The chosen Vectorization and Unroll Factors of the loop being vectorized.
239  unsigned VF;
240  unsigned UF;
241 
242  /// Hold the indices to generate specific scalar instructions. Null indicates
243  /// that all instances are to be generated, using either scalar or vector
244  /// instructions.
246 
247  struct DataState {
248  /// A type for vectorized values in the new loop. Each value from the
249  /// original loop, when vectorized, is represented by UF vector values in
250  /// the new unrolled loop, where UF is the unroll factor.
252 
254  } Data;
255 
256  /// Get the generated Value for a given VPValue and a given Part. Note that
257  /// as some Defs are still created by ILV and managed in its ValueMap, this
258  /// method will delegate the call to ILV in such cases in order to provide
259  /// callers a consistent API.
260  /// \see set.
261  Value *get(VPValue *Def, unsigned Part) {
262  // If Values have been set for this Def return the one relevant for \p Part.
263  if (Data.PerPartOutput.count(Def))
264  return Data.PerPartOutput[Def][Part];
265  // Def is managed by ILV: bring the Values from ValueMap.
266  return Callback.getOrCreateVectorValues(VPValue2Value[Def], Part);
267  }
268 
269  /// Set the generated Value for a given VPValue and a given Part.
270  void set(VPValue *Def, Value *V, unsigned Part) {
271  if (!Data.PerPartOutput.count(Def)) {
272  DataState::PerPartValuesTy Entry(UF);
273  Data.PerPartOutput[Def] = Entry;
274  }
275  Data.PerPartOutput[Def][Part] = V;
276  }
277 
278  /// Hold state information used when constructing the CFG of the output IR,
279  /// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks.
280  struct CFGState {
281  /// The previous VPBasicBlock visited. Initially set to null.
282  VPBasicBlock *PrevVPBB = nullptr;
283 
284  /// The previous IR BasicBlock created or used. Initially set to the new
285  /// header BasicBlock.
286  BasicBlock *PrevBB = nullptr;
287 
288  /// The last IR BasicBlock in the output IR. Set to the new latch
289  /// BasicBlock, used for placing the newly created BasicBlocks.
290  BasicBlock *LastBB = nullptr;
291 
292  /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case
293  /// of replication, maps the BasicBlock of the last replica created.
295 
296  /// Vector of VPBasicBlocks whose terminator instruction needs to be fixed
297  /// up at the end of vector code generation.
299 
300  CFGState() = default;
301  } CFG;
302 
303  /// Hold a pointer to LoopInfo to register new basic blocks in the loop.
305 
306  /// Hold a pointer to Dominator Tree to register new basic blocks in the loop.
308 
309  /// Hold a reference to the IRBuilder used to generate output IR code.
311 
312  /// Hold a reference to the Value state information used when generating the
313  /// Values of the output IR.
315 
316  /// Hold a reference to a mapping between VPValues in VPlan and original
317  /// Values they correspond to.
319 
320  /// Hold the trip count of the scalar loop.
321  Value *TripCount = nullptr;
322 
323  /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
325 
327 };
328 
329 /// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
330 /// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.
331 class VPBlockBase {
332  friend class VPBlockUtils;
333 
334 private:
335  const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
336 
337  /// An optional name for the block.
338  std::string Name;
339 
340  /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if
341  /// it is a topmost VPBlockBase.
342  VPRegionBlock *Parent = nullptr;
343 
344  /// List of predecessor blocks.
345  SmallVector<VPBlockBase *, 1> Predecessors;
346 
347  /// List of successor blocks.
349 
350  /// Successor selector, null for zero or single successor blocks.
351  VPValue *CondBit = nullptr;
352 
353  /// Add \p Successor as the last successor to this block.
354  void appendSuccessor(VPBlockBase *Successor) {
355  assert(Successor && "Cannot add nullptr successor!");
356  Successors.push_back(Successor);
357  }
358 
359  /// Add \p Predecessor as the last predecessor to this block.
360  void appendPredecessor(VPBlockBase *Predecessor) {
361  assert(Predecessor && "Cannot add nullptr predecessor!");
362  Predecessors.push_back(Predecessor);
363  }
364 
365  /// Remove \p Predecessor from the predecessors of this block.
366  void removePredecessor(VPBlockBase *Predecessor) {
367  auto Pos = std::find(Predecessors.begin(), Predecessors.end(), Predecessor);
368  assert(Pos && "Predecessor does not exist");
369  Predecessors.erase(Pos);
370  }
371 
372  /// Remove \p Successor from the successors of this block.
373  void removeSuccessor(VPBlockBase *Successor) {
374  auto Pos = std::find(Successors.begin(), Successors.end(), Successor);
375  assert(Pos && "Successor does not exist");
376  Successors.erase(Pos);
377  }
378 
379 protected:
380  VPBlockBase(const unsigned char SC, const std::string &N)
381  : SubclassID(SC), Name(N) {}
382 
383 public:
384  /// An enumeration for keeping track of the concrete subclass of VPBlockBase
385  /// that are actually instantiated. Values of this enumeration are kept in the
386  /// SubclassID field of the VPBlockBase objects. They are used for concrete
387  /// type identification.
388  using VPBlockTy = enum { VPBasicBlockSC, VPRegionBlockSC };
389 
391 
392  virtual ~VPBlockBase() = default;
393 
394  const std::string &getName() const { return Name; }
395 
396  void setName(const Twine &newName) { Name = newName.str(); }
397 
398  /// \return an ID for the concrete type of this object.
399  /// This is used to implement the classof checks. This should not be used
400  /// for any other purpose, as the values may change as LLVM evolves.
401  unsigned getVPBlockID() const { return SubclassID; }
402 
403  VPRegionBlock *getParent() { return Parent; }
404  const VPRegionBlock *getParent() const { return Parent; }
405 
406  void setParent(VPRegionBlock *P) { Parent = P; }
407 
408  /// \return the VPBasicBlock that is the entry of this VPBlockBase,
409  /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
410  /// VPBlockBase is a VPBasicBlock, it is returned.
411  const VPBasicBlock *getEntryBasicBlock() const;
412  VPBasicBlock *getEntryBasicBlock();
413 
414  /// \return the VPBasicBlock that is the exit of this VPBlockBase,
415  /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
416  /// VPBlockBase is a VPBasicBlock, it is returned.
417  const VPBasicBlock *getExitBasicBlock() const;
418  VPBasicBlock *getExitBasicBlock();
419 
420  const VPBlocksTy &getSuccessors() const { return Successors; }
421  VPBlocksTy &getSuccessors() { return Successors; }
422 
423  const VPBlocksTy &getPredecessors() const { return Predecessors; }
424  VPBlocksTy &getPredecessors() { return Predecessors; }
425 
426  /// \return the successor of this VPBlockBase if it has a single successor.
427  /// Otherwise return a null pointer.
429  return (Successors.size() == 1 ? *Successors.begin() : nullptr);
430  }
431 
432  /// \return the predecessor of this VPBlockBase if it has a single
433  /// predecessor. Otherwise return a null pointer.
435  return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr);
436  }
437 
438  size_t getNumSuccessors() const { return Successors.size(); }
439  size_t getNumPredecessors() const { return Predecessors.size(); }
440 
441  /// An Enclosing Block of a block B is any block containing B, including B
442  /// itself. \return the closest enclosing block starting from "this", which
443  /// has successors. \return the root enclosing block if all enclosing blocks
444  /// have no successors.
445  VPBlockBase *getEnclosingBlockWithSuccessors();
446 
447  /// \return the closest enclosing block starting from "this", which has
448  /// predecessors. \return the root enclosing block if all enclosing blocks
449  /// have no predecessors.
450  VPBlockBase *getEnclosingBlockWithPredecessors();
451 
452  /// \return the successors either attached directly to this VPBlockBase or, if
453  /// this VPBlockBase is the exit block of a VPRegionBlock and has no
454  /// successors of its own, search recursively for the first enclosing
455  /// VPRegionBlock that has successors and return them. If no such
456  /// VPRegionBlock exists, return the (empty) successors of the topmost
457  /// VPBlockBase reached.
459  return getEnclosingBlockWithSuccessors()->getSuccessors();
460  }
461 
462  /// \return the hierarchical successor of this VPBlockBase if it has a single
463  /// hierarchical successor. Otherwise return a null pointer.
465  return getEnclosingBlockWithSuccessors()->getSingleSuccessor();
466  }
467 
468  /// \return the predecessors either attached directly to this VPBlockBase or,
469  /// if this VPBlockBase is the entry block of a VPRegionBlock and has no
470  /// predecessors of its own, search recursively for the first enclosing
471  /// VPRegionBlock that has predecessors and return them. If no such
472  /// VPRegionBlock exists, return the (empty) predecessors of the topmost
473  /// VPBlockBase reached.
475  return getEnclosingBlockWithPredecessors()->getPredecessors();
476  }
477 
478  /// \return the hierarchical predecessor of this VPBlockBase if it has a
479  /// single hierarchical predecessor. Otherwise return a null pointer.
481  return getEnclosingBlockWithPredecessors()->getSinglePredecessor();
482  }
483 
484  /// \return the condition bit selecting the successor.
485  VPValue *getCondBit() { return CondBit; }
486 
487  const VPValue *getCondBit() const { return CondBit; }
488 
489  void setCondBit(VPValue *CV) { CondBit = CV; }
490 
491  /// Set a given VPBlockBase \p Successor as the single successor of this
492  /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor.
493  /// This VPBlockBase must have no successors.
494  void setOneSuccessor(VPBlockBase *Successor) {
495  assert(Successors.empty() && "Setting one successor when others exist.");
496  appendSuccessor(Successor);
497  }
498 
499  /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two
500  /// successors of this VPBlockBase. \p Condition is set as the successor
501  /// selector. This VPBlockBase is not added as predecessor of \p IfTrue or \p
502  /// IfFalse. This VPBlockBase must have no successors.
503  void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
504  VPValue *Condition) {
505  assert(Successors.empty() && "Setting two successors when others exist.");
506  assert(Condition && "Setting two successors without condition!");
507  CondBit = Condition;
508  appendSuccessor(IfTrue);
509  appendSuccessor(IfFalse);
510  }
511 
512  /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase.
513  /// This VPBlockBase must have no predecessors. This VPBlockBase is not added
514  /// as successor of any VPBasicBlock in \p NewPreds.
516  assert(Predecessors.empty() && "Block predecessors already set.");
517  for (auto *Pred : NewPreds)
518  appendPredecessor(Pred);
519  }
520 
521  /// The method which generates the output IR that correspond to this
522  /// VPBlockBase, thereby "executing" the VPlan.
523  virtual void execute(struct VPTransformState *State) = 0;
524 
525  /// Delete all blocks reachable from a given VPBlockBase, inclusive.
526  static void deleteCFG(VPBlockBase *Entry);
527 
528  void printAsOperand(raw_ostream &OS, bool PrintType) const {
529  OS << getName();
530  }
531 
532  void print(raw_ostream &OS) const {
533  // TODO: Only printing VPBB name for now since we only have dot printing
534  // support for VPInstructions/Recipes.
535  printAsOperand(OS, false);
536  }
537 
538  /// Return true if it is legal to hoist instructions into this block.
540  // There are currently no constraints that prevent an instruction to be
541  // hoisted into a VPBlockBase.
542  return true;
543  }
544 };
545 
546 /// VPRecipeBase is a base class modeling a sequence of one or more output IR
547 /// instructions.
548 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> {
549  friend VPBasicBlock;
550 
551 private:
552  const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
553 
554  /// Each VPRecipe belongs to a single VPBasicBlock.
555  VPBasicBlock *Parent = nullptr;
556 
557 public:
558  /// An enumeration for keeping track of the concrete subclass of VPRecipeBase
559  /// that is actually instantiated. Values of this enumeration are kept in the
560  /// SubclassID field of the VPRecipeBase objects. They are used for concrete
561  /// type identification.
562  using VPRecipeTy = enum {
563  VPBlendSC,
564  VPBranchOnMaskSC,
565  VPInstructionSC,
566  VPInterleaveSC,
567  VPPredInstPHISC,
568  VPReplicateSC,
569  VPWidenIntOrFpInductionSC,
570  VPWidenMemoryInstructionSC,
571  VPWidenPHISC,
572  VPWidenSC,
573  };
574 
575  VPRecipeBase(const unsigned char SC) : SubclassID(SC) {}
576  virtual ~VPRecipeBase() = default;
577 
578  /// \return an ID for the concrete type of this object.
579  /// This is used to implement the classof checks. This should not be used
580  /// for any other purpose, as the values may change as LLVM evolves.
581  unsigned getVPRecipeID() const { return SubclassID; }
582 
583  /// \return the VPBasicBlock which this VPRecipe belongs to.
584  VPBasicBlock *getParent() { return Parent; }
585  const VPBasicBlock *getParent() const { return Parent; }
586 
587  /// The method which generates the output IR instructions that correspond to
588  /// this VPRecipe, thereby "executing" the VPlan.
589  virtual void execute(struct VPTransformState &State) = 0;
590 
591  /// Each recipe prints itself.
592  virtual void print(raw_ostream &O, const Twine &Indent) const = 0;
593 
594  /// Insert an unlinked recipe into a basic block immediately before
595  /// the specified recipe.
596  void insertBefore(VPRecipeBase *InsertPos);
597 
598  /// This method unlinks 'this' from the containing basic block and deletes it.
599  ///
600  /// \returns an iterator pointing to the element after the erased one
601  iplist<VPRecipeBase>::iterator eraseFromParent();
602 };
603 
604 /// This is a concrete Recipe that models a single VPlan-level instruction.
605 /// While as any Recipe it may generate a sequence of IR instructions when
606 /// executed, these instructions would always form a single-def expression as
607 /// the VPInstruction is also a single def-use vertex.
608 class VPInstruction : public VPUser, public VPRecipeBase {
609  friend class VPlanHCFGTransforms;
610 
611 public:
612  /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
613  enum { Not = Instruction::OtherOpsEnd + 1, ICmpULE };
614 
615 private:
616  typedef unsigned char OpcodeTy;
617  OpcodeTy Opcode;
618 
619  /// Utility method serving execute(): generates a single instance of the
620  /// modeled instruction.
621  void generateInstruction(VPTransformState &State, unsigned Part);
622 
623 public:
624  VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands)
625  : VPUser(VPValue::VPInstructionSC, Operands),
626  VPRecipeBase(VPRecipeBase::VPInstructionSC), Opcode(Opcode) {}
627 
628  VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands)
629  : VPInstruction(Opcode, ArrayRef<VPValue *>(Operands)) {}
630 
631  /// Method to support type inquiry through isa, cast, and dyn_cast.
632  static inline bool classof(const VPValue *V) {
633  return V->getVPValueID() == VPValue::VPInstructionSC;
634  }
635 
636  /// Method to support type inquiry through isa, cast, and dyn_cast.
637  static inline bool classof(const VPRecipeBase *R) {
638  return R->getVPRecipeID() == VPRecipeBase::VPInstructionSC;
639  }
640 
641  unsigned getOpcode() const { return Opcode; }
642 
643  /// Generate the instruction.
644  /// TODO: We currently execute only per-part unless a specific instance is
645  /// provided.
646  void execute(VPTransformState &State) override;
647 
648  /// Print the Recipe.
649  void print(raw_ostream &O, const Twine &Indent) const override;
650 
651  /// Print the VPInstruction.
652  void print(raw_ostream &O) const;
653 };
654 
655 /// VPWidenRecipe is a recipe for producing a copy of vector type for each
656 /// Instruction in its ingredients independently, in order. This recipe covers
657 /// most of the traditional vectorization cases where each ingredient transforms
658 /// into a vectorized version of itself.
659 class VPWidenRecipe : public VPRecipeBase {
660 private:
661  /// Hold the ingredients by pointing to their original BasicBlock location.
662  BasicBlock::iterator Begin;
664 
665 public:
667  End = I->getIterator();
668  Begin = End++;
669  }
670 
671  ~VPWidenRecipe() override = default;
672 
673  /// Method to support type inquiry through isa, cast, and dyn_cast.
674  static inline bool classof(const VPRecipeBase *V) {
675  return V->getVPRecipeID() == VPRecipeBase::VPWidenSC;
676  }
677 
678  /// Produce widened copies of all Ingredients.
679  void execute(VPTransformState &State) override;
680 
681  /// Augment the recipe to include Instr, if it lies at its End.
683  if (End != Instr->getIterator())
684  return false;
685  End++;
686  return true;
687  }
688 
689  /// Print the recipe.
690  void print(raw_ostream &O, const Twine &Indent) const override;
691 };
692 
693 /// A recipe for handling phi nodes of integer and floating-point inductions,
694 /// producing their vector and scalar values.
696 private:
697  PHINode *IV;
698  TruncInst *Trunc;
699 
700 public:
702  : VPRecipeBase(VPWidenIntOrFpInductionSC), IV(IV), Trunc(Trunc) {}
703  ~VPWidenIntOrFpInductionRecipe() override = default;
704 
705  /// Method to support type inquiry through isa, cast, and dyn_cast.
706  static inline bool classof(const VPRecipeBase *V) {
707  return V->getVPRecipeID() == VPRecipeBase::VPWidenIntOrFpInductionSC;
708  }
709 
710  /// Generate the vectorized and scalarized versions of the phi node as
711  /// needed by their users.
712  void execute(VPTransformState &State) override;
713 
714  /// Print the recipe.
715  void print(raw_ostream &O, const Twine &Indent) const override;
716 };
717 
718 /// A recipe for handling all phi nodes except for integer and FP inductions.
720 private:
721  PHINode *Phi;
722 
723 public:
724  VPWidenPHIRecipe(PHINode *Phi) : VPRecipeBase(VPWidenPHISC), Phi(Phi) {}
725  ~VPWidenPHIRecipe() override = default;
726 
727  /// Method to support type inquiry through isa, cast, and dyn_cast.
728  static inline bool classof(const VPRecipeBase *V) {
729  return V->getVPRecipeID() == VPRecipeBase::VPWidenPHISC;
730  }
731 
732  /// Generate the phi/select nodes.
733  void execute(VPTransformState &State) override;
734 
735  /// Print the recipe.
736  void print(raw_ostream &O, const Twine &Indent) const override;
737 };
738 
739 /// A recipe for vectorizing a phi-node as a sequence of mask-based select
740 /// instructions.
741 class VPBlendRecipe : public VPRecipeBase {
742 private:
743  PHINode *Phi;
744 
745  /// The blend operation is a User of a mask, if not null.
746  std::unique_ptr<VPUser> User;
747 
748 public:
750  : VPRecipeBase(VPBlendSC), Phi(Phi) {
751  assert((Phi->getNumIncomingValues() == 1 ||
752  Phi->getNumIncomingValues() == Masks.size()) &&
753  "Expected the same number of incoming values and masks");
754  if (!Masks.empty())
755  User.reset(new VPUser(Masks));
756  }
757 
758  /// Method to support type inquiry through isa, cast, and dyn_cast.
759  static inline bool classof(const VPRecipeBase *V) {
760  return V->getVPRecipeID() == VPRecipeBase::VPBlendSC;
761  }
762 
763  /// Generate the phi/select nodes.
764  void execute(VPTransformState &State) override;
765 
766  /// Print the recipe.
767  void print(raw_ostream &O, const Twine &Indent) const override;
768 };
769 
770 /// VPInterleaveRecipe is a recipe for transforming an interleave group of load
771 /// or stores into one wide load/store and shuffles.
773 private:
774  const InterleaveGroup *IG;
775  std::unique_ptr<VPUser> User;
776 
777 public:
779  : VPRecipeBase(VPInterleaveSC), IG(IG) {
780  if (Mask) // Create a VPInstruction to register as a user of the mask.
781  User.reset(new VPUser({Mask}));
782  }
783  ~VPInterleaveRecipe() override = default;
784 
785  /// Method to support type inquiry through isa, cast, and dyn_cast.
786  static inline bool classof(const VPRecipeBase *V) {
787  return V->getVPRecipeID() == VPRecipeBase::VPInterleaveSC;
788  }
789 
790  /// Generate the wide load or store, and shuffles.
791  void execute(VPTransformState &State) override;
792 
793  /// Print the recipe.
794  void print(raw_ostream &O, const Twine &Indent) const override;
795 
796  const InterleaveGroup *getInterleaveGroup() { return IG; }
797 };
798 
799 /// VPReplicateRecipe replicates a given instruction producing multiple scalar
800 /// copies of the original scalar type, one per lane, instead of producing a
801 /// single copy of widened type for all lanes. If the instruction is known to be
802 /// uniform only one copy, per lane zero, will be generated.
804 private:
805  /// The instruction being replicated.
806  Instruction *Ingredient;
807 
808  /// Indicator if only a single replica per lane is needed.
809  bool IsUniform;
810 
811  /// Indicator if the replicas are also predicated.
812  bool IsPredicated;
813 
814  /// Indicator if the scalar values should also be packed into a vector.
815  bool AlsoPack;
816 
817 public:
818  VPReplicateRecipe(Instruction *I, bool IsUniform, bool IsPredicated = false)
819  : VPRecipeBase(VPReplicateSC), Ingredient(I), IsUniform(IsUniform),
820  IsPredicated(IsPredicated) {
821  // Retain the previous behavior of predicateInstructions(), where an
822  // insert-element of a predicated instruction got hoisted into the
823  // predicated basic block iff it was its only user. This is achieved by
824  // having predicated instructions also pack their values into a vector by
825  // default unless they have a replicated user which uses their scalar value.
826  AlsoPack = IsPredicated && !I->use_empty();
827  }
828 
829  ~VPReplicateRecipe() override = default;
830 
831  /// Method to support type inquiry through isa, cast, and dyn_cast.
832  static inline bool classof(const VPRecipeBase *V) {
833  return V->getVPRecipeID() == VPRecipeBase::VPReplicateSC;
834  }
835 
836  /// Generate replicas of the desired Ingredient. Replicas will be generated
837  /// for all parts and lanes unless a specific part and lane are specified in
838  /// the \p State.
839  void execute(VPTransformState &State) override;
840 
841  void setAlsoPack(bool Pack) { AlsoPack = Pack; }
842 
843  /// Print the recipe.
844  void print(raw_ostream &O, const Twine &Indent) const override;
845 };
846 
847 /// A recipe for generating conditional branches on the bits of a mask.
849 private:
850  std::unique_ptr<VPUser> User;
851 
852 public:
853  VPBranchOnMaskRecipe(VPValue *BlockInMask) : VPRecipeBase(VPBranchOnMaskSC) {
854  if (BlockInMask) // nullptr means all-one mask.
855  User.reset(new VPUser({BlockInMask}));
856  }
857 
858  /// Method to support type inquiry through isa, cast, and dyn_cast.
859  static inline bool classof(const VPRecipeBase *V) {
860  return V->getVPRecipeID() == VPRecipeBase::VPBranchOnMaskSC;
861  }
862 
863  /// Generate the extraction of the appropriate bit from the block mask and the
864  /// conditional branch.
865  void execute(VPTransformState &State) override;
866 
867  /// Print the recipe.
868  void print(raw_ostream &O, const Twine &Indent) const override {
869  O << " +\n" << Indent << "\"BRANCH-ON-MASK ";
870  if (User)
871  O << *User->getOperand(0);
872  else
873  O << " All-One";
874  O << "\\l\"";
875  }
876 };
877 
878 /// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
879 /// control converges back from a Branch-on-Mask. The phi nodes are needed in
880 /// order to merge values that are set under such a branch and feed their uses.
881 /// The phi nodes can be scalar or vector depending on the users of the value.
882 /// This recipe works in concert with VPBranchOnMaskRecipe.
884 private:
885  Instruction *PredInst;
886 
887 public:
888  /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
889  /// nodes after merging back from a Branch-on-Mask.
891  : VPRecipeBase(VPPredInstPHISC), PredInst(PredInst) {}
892  ~VPPredInstPHIRecipe() override = default;
893 
894  /// Method to support type inquiry through isa, cast, and dyn_cast.
895  static inline bool classof(const VPRecipeBase *V) {
896  return V->getVPRecipeID() == VPRecipeBase::VPPredInstPHISC;
897  }
898 
899  /// Generates phi nodes for live-outs as needed to retain SSA form.
900  void execute(VPTransformState &State) override;
901 
902  /// Print the recipe.
903  void print(raw_ostream &O, const Twine &Indent) const override;
904 };
905 
906 /// A Recipe for widening load/store operations.
907 /// TODO: We currently execute only per-part unless a specific instance is
908 /// provided.
910 private:
911  Instruction &Instr;
912  std::unique_ptr<VPUser> User;
913 
914 public:
916  : VPRecipeBase(VPWidenMemoryInstructionSC), Instr(Instr) {
917  if (Mask) // Create a VPInstruction to register as a user of the mask.
918  User.reset(new VPUser({Mask}));
919  }
920 
921  /// Method to support type inquiry through isa, cast, and dyn_cast.
922  static inline bool classof(const VPRecipeBase *V) {
923  return V->getVPRecipeID() == VPRecipeBase::VPWidenMemoryInstructionSC;
924  }
925 
926  /// Generate the wide load/store.
927  void execute(VPTransformState &State) override;
928 
929  /// Print the recipe.
930  void print(raw_ostream &O, const Twine &Indent) const override;
931 };
932 
933 /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
934 /// holds a sequence of zero or more VPRecipe's each representing a sequence of
935 /// output IR instructions.
936 class VPBasicBlock : public VPBlockBase {
937 public:
939 
940 private:
941  /// The VPRecipes held in the order of output instructions to generate.
942  RecipeListTy Recipes;
943 
944 public:
945  VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr)
946  : VPBlockBase(VPBasicBlockSC, Name.str()) {
947  if (Recipe)
948  appendRecipe(Recipe);
949  }
950 
951  ~VPBasicBlock() override { Recipes.clear(); }
952 
953  /// Instruction iterators...
958 
959  //===--------------------------------------------------------------------===//
960  /// Recipe iterator methods
961  ///
962  inline iterator begin() { return Recipes.begin(); }
963  inline const_iterator begin() const { return Recipes.begin(); }
964  inline iterator end() { return Recipes.end(); }
965  inline const_iterator end() const { return Recipes.end(); }
966 
967  inline reverse_iterator rbegin() { return Recipes.rbegin(); }
968  inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); }
969  inline reverse_iterator rend() { return Recipes.rend(); }
970  inline const_reverse_iterator rend() const { return Recipes.rend(); }
971 
972  inline size_t size() const { return Recipes.size(); }
973  inline bool empty() const { return Recipes.empty(); }
974  inline const VPRecipeBase &front() const { return Recipes.front(); }
975  inline VPRecipeBase &front() { return Recipes.front(); }
976  inline const VPRecipeBase &back() const { return Recipes.back(); }
977  inline VPRecipeBase &back() { return Recipes.back(); }
978 
979  /// Returns a reference to the list of recipes.
980  RecipeListTy &getRecipeList() { return Recipes; }
981 
982  /// Returns a pointer to a member of the recipe list.
984  return &VPBasicBlock::Recipes;
985  }
986 
987  /// Method to support type inquiry through isa, cast, and dyn_cast.
988  static inline bool classof(const VPBlockBase *V) {
989  return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC;
990  }
991 
992  void insert(VPRecipeBase *Recipe, iterator InsertPt) {
993  assert(Recipe && "No recipe to append.");
994  assert(!Recipe->Parent && "Recipe already in VPlan");
995  Recipe->Parent = this;
996  Recipes.insert(InsertPt, Recipe);
997  }
998 
999  /// Augment the existing recipes of a VPBasicBlock with an additional
1000  /// \p Recipe as the last recipe.
1001  void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); }
1002 
1003  /// The method which generates the output IR instructions that correspond to
1004  /// this VPBasicBlock, thereby "executing" the VPlan.
1005  void execute(struct VPTransformState *State) override;
1006 
1007 private:
1008  /// Create an IR BasicBlock to hold the output instructions generated by this
1009  /// VPBasicBlock, and return it. Update the CFGState accordingly.
1010  BasicBlock *createEmptyBasicBlock(VPTransformState::CFGState &CFG);
1011 };
1012 
1013 /// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks
1014 /// which form a Single-Entry-Single-Exit subgraph of the output IR CFG.
1015 /// A VPRegionBlock may indicate that its contents are to be replicated several
1016 /// times. This is designed to support predicated scalarization, in which a
1017 /// scalar if-then code structure needs to be generated VF * UF times. Having
1018 /// this replication indicator helps to keep a single model for multiple
1019 /// candidate VF's. The actual replication takes place only once the desired VF
1020 /// and UF have been determined.
1021 class VPRegionBlock : public VPBlockBase {
1022 private:
1023  /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock.
1024  VPBlockBase *Entry;
1025 
1026  /// Hold the Single Exit of the SESE region modelled by the VPRegionBlock.
1027  VPBlockBase *Exit;
1028 
1029  /// An indicator whether this region is to generate multiple replicated
1030  /// instances of output IR corresponding to its VPBlockBases.
1031  bool IsReplicator;
1032 
1033 public:
1035  const std::string &Name = "", bool IsReplicator = false)
1036  : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exit(Exit),
1037  IsReplicator(IsReplicator) {
1038  assert(Entry->getPredecessors().empty() && "Entry block has predecessors.");
1039  assert(Exit->getSuccessors().empty() && "Exit block has successors.");
1040  Entry->setParent(this);
1041  Exit->setParent(this);
1042  }
1043  VPRegionBlock(const std::string &Name = "", bool IsReplicator = false)
1044  : VPBlockBase(VPRegionBlockSC, Name), Entry(nullptr), Exit(nullptr),
1045  IsReplicator(IsReplicator) {}
1046 
1047  ~VPRegionBlock() override {
1048  if (Entry)
1049  deleteCFG(Entry);
1050  }
1051 
1052  /// Method to support type inquiry through isa, cast, and dyn_cast.
1053  static inline bool classof(const VPBlockBase *V) {
1054  return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC;
1055  }
1056 
1057  const VPBlockBase *getEntry() const { return Entry; }
1058  VPBlockBase *getEntry() { return Entry; }
1059 
1060  /// Set \p EntryBlock as the entry VPBlockBase of this VPRegionBlock. \p
1061  /// EntryBlock must have no predecessors.
1062  void setEntry(VPBlockBase *EntryBlock) {
1063  assert(EntryBlock->getPredecessors().empty() &&
1064  "Entry block cannot have predecessors.");
1065  Entry = EntryBlock;
1066  EntryBlock->setParent(this);
1067  }
1068 
1069  // FIXME: DominatorTreeBase is doing 'A->getParent()->front()'. 'front' is a
1070  // specific interface of llvm::Function, instead of using
1071  // GraphTraints::getEntryNode. We should add a new template parameter to
1072  // DominatorTreeBase representing the Graph type.
1073  VPBlockBase &front() const { return *Entry; }
1074 
1075  const VPBlockBase *getExit() const { return Exit; }
1076  VPBlockBase *getExit() { return Exit; }
1077 
1078  /// Set \p ExitBlock as the exit VPBlockBase of this VPRegionBlock. \p
1079  /// ExitBlock must have no successors.
1080  void setExit(VPBlockBase *ExitBlock) {
1081  assert(ExitBlock->getSuccessors().empty() &&
1082  "Exit block cannot have successors.");
1083  Exit = ExitBlock;
1084  ExitBlock->setParent(this);
1085  }
1086 
1087  /// An indicator whether this region is to generate multiple replicated
1088  /// instances of output IR corresponding to its VPBlockBases.
1089  bool isReplicator() const { return IsReplicator; }
1090 
1091  /// The method which generates the output IR instructions that correspond to
1092  /// this VPRegionBlock, thereby "executing" the VPlan.
1093  void execute(struct VPTransformState *State) override;
1094 };
1095 
1096 /// VPlan models a candidate for vectorization, encoding various decisions take
1097 /// to produce efficient output IR, including which branches, basic-blocks and
1098 /// output IR instructions to generate, and their cost. VPlan holds a
1099 /// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry
1100 /// VPBlock.
1101 class VPlan {
1102  friend class VPlanPrinter;
1103 
1104 private:
1105  /// Hold the single entry to the Hierarchical CFG of the VPlan.
1106  VPBlockBase *Entry;
1107 
1108  /// Holds the VFs applicable to this VPlan.
1110 
1111  /// Holds the name of the VPlan, for printing.
1112  std::string Name;
1113 
1114  /// Holds all the external definitions created for this VPlan.
1115  // TODO: Introduce a specific representation for external definitions in
1116  // VPlan. External definitions must be immutable and hold a pointer to its
1117  // underlying IR that will be used to implement its structural comparison
1118  // (operators '==' and '<').
1119  SmallPtrSet<VPValue *, 16> VPExternalDefs;
1120 
1121  /// Represents the backedge taken count of the original loop, for folding
1122  /// the tail.
1123  VPValue *BackedgeTakenCount = nullptr;
1124 
1125  /// Holds a mapping between Values and their corresponding VPValue inside
1126  /// VPlan.
1127  Value2VPValueTy Value2VPValue;
1128 
1129  /// Holds the VPLoopInfo analysis for this VPlan.
1130  VPLoopInfo VPLInfo;
1131 
1132  /// Holds the condition bit values built during VPInstruction to VPRecipe transformation.
1134 
1135 public:
1136  VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {}
1137 
1139  if (Entry)
1140  VPBlockBase::deleteCFG(Entry);
1141  for (auto &MapEntry : Value2VPValue)
1142  if (MapEntry.second != BackedgeTakenCount)
1143  delete MapEntry.second;
1144  if (BackedgeTakenCount)
1145  delete BackedgeTakenCount; // Delete once, if in Value2VPValue or not.
1146  for (VPValue *Def : VPExternalDefs)
1147  delete Def;
1148  for (VPValue *CBV : VPCBVs)
1149  delete CBV;
1150  }
1151 
1152  /// Generate the IR code for this VPlan.
1153  void execute(struct VPTransformState *State);
1154 
1155  VPBlockBase *getEntry() { return Entry; }
1156  const VPBlockBase *getEntry() const { return Entry; }
1157 
1158  VPBlockBase *setEntry(VPBlockBase *Block) { return Entry = Block; }
1159 
1160  /// The backedge taken count of the original loop.
1162  if (!BackedgeTakenCount)
1163  BackedgeTakenCount = new VPValue();
1164  return BackedgeTakenCount;
1165  }
1166 
1167  void addVF(unsigned VF) { VFs.insert(VF); }
1168 
1169  bool hasVF(unsigned VF) { return VFs.count(VF); }
1170 
1171  const std::string &getName() const { return Name; }
1172 
1173  void setName(const Twine &newName) { Name = newName.str(); }
1174 
1175  /// Add \p VPVal to the pool of external definitions if it's not already
1176  /// in the pool.
1177  void addExternalDef(VPValue *VPVal) {
1178  VPExternalDefs.insert(VPVal);
1179  }
1180 
1181  /// Add \p CBV to the vector of condition bit values.
1182  void addCBV(VPValue *CBV) {
1183  VPCBVs.push_back(CBV);
1184  }
1185 
1186  void addVPValue(Value *V) {
1187  assert(V && "Trying to add a null Value to VPlan");
1188  assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
1189  Value2VPValue[V] = new VPValue();
1190  }
1191 
1193  assert(V && "Trying to get the VPValue of a null Value");
1194  assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
1195  return Value2VPValue[V];
1196  }
1197 
1198  /// Return the VPLoopInfo analysis for this VPlan.
1199  VPLoopInfo &getVPLoopInfo() { return VPLInfo; }
1200  const VPLoopInfo &getVPLoopInfo() const { return VPLInfo; }
1201 
1202 private:
1203  /// Add to the given dominator tree the header block and every new basic block
1204  /// that was created between it and the latch block, inclusive.
1205  static void updateDominatorTree(DominatorTree *DT,
1206  BasicBlock *LoopPreHeaderBB,
1207  BasicBlock *LoopLatchBB);
1208 };
1209 
1210 /// VPlanPrinter prints a given VPlan to a given output stream. The printing is
1211 /// indented and follows the dot format.
1213  friend inline raw_ostream &operator<<(raw_ostream &OS, VPlan &Plan);
1214  friend inline raw_ostream &operator<<(raw_ostream &OS,
1215  const struct VPlanIngredient &I);
1216 
1217 private:
1218  raw_ostream &OS;
1219  VPlan &Plan;
1220  unsigned Depth;
1221  unsigned TabWidth = 2;
1222  std::string Indent;
1223  unsigned BID = 0;
1225 
1226  VPlanPrinter(raw_ostream &O, VPlan &P) : OS(O), Plan(P) {}
1227 
1228  /// Handle indentation.
1229  void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); }
1230 
1231  /// Print a given \p Block of the Plan.
1232  void dumpBlock(const VPBlockBase *Block);
1233 
1234  /// Print the information related to the CFG edges going out of a given
1235  /// \p Block, followed by printing the successor blocks themselves.
1236  void dumpEdges(const VPBlockBase *Block);
1237 
1238  /// Print a given \p BasicBlock, including its VPRecipes, followed by printing
1239  /// its successor blocks.
1240  void dumpBasicBlock(const VPBasicBlock *BasicBlock);
1241 
1242  /// Print a given \p Region of the Plan.
1243  void dumpRegion(const VPRegionBlock *Region);
1244 
1245  unsigned getOrCreateBID(const VPBlockBase *Block) {
1246  return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++;
1247  }
1248 
1249  const Twine getOrCreateName(const VPBlockBase *Block);
1250 
1251  const Twine getUID(const VPBlockBase *Block);
1252 
1253  /// Print the information related to a CFG edge between two VPBlockBases.
1254  void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden,
1255  const Twine &Label);
1256 
1257  void dump();
1258 
1259  static void printAsIngredient(raw_ostream &O, Value *V);
1260 };
1261 
1264 
1265  VPlanIngredient(Value *V) : V(V) {}
1266 };
1267 
1269  VPlanPrinter::printAsIngredient(OS, I.V);
1270  return OS;
1271 }
1272 
1274  VPlanPrinter Printer(OS, Plan);
1275  Printer.dump();
1276  return OS;
1277 }
1278 
1279 //===----------------------------------------------------------------------===//
1280 // GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs //
1281 //===----------------------------------------------------------------------===//
1282 
1283 // The following set of template specializations implement GraphTraits to treat
1284 // any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
1285 // that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
1286 // VPBlockBase is a VPRegionBlock, this specialization provides access to its
1287 // successors/predecessors but not to the blocks inside the region.
1288 
1289 template <> struct GraphTraits<VPBlockBase *> {
1292 
1293  static NodeRef getEntryNode(NodeRef N) { return N; }
1294 
1296  return N->getSuccessors().begin();
1297  }
1298 
1300  return N->getSuccessors().end();
1301  }
1302 };
1303 
1304 template <> struct GraphTraits<const VPBlockBase *> {
1305  using NodeRef = const VPBlockBase *;
1307 
1308  static NodeRef getEntryNode(NodeRef N) { return N; }
1309 
1311  return N->getSuccessors().begin();
1312  }
1313 
1315  return N->getSuccessors().end();
1316  }
1317 };
1318 
1319 // Inverse order specialization for VPBasicBlocks. Predecessors are used instead
1320 // of successors for the inverse traversal.
1321 template <> struct GraphTraits<Inverse<VPBlockBase *>> {
1324 
1326 
1328  return N->getPredecessors().begin();
1329  }
1330 
1332  return N->getPredecessors().end();
1333  }
1334 };
1335 
1336 // The following set of template specializations implement GraphTraits to
1337 // treat VPRegionBlock as a graph and recurse inside its nodes. It's important
1338 // to note that the blocks inside the VPRegionBlock are treated as VPBlockBases
1339 // (i.e., no dyn_cast is performed, VPBlockBases specialization is used), so
1340 // there won't be automatic recursion into other VPBlockBases that turn to be
1341 // VPRegionBlocks.
1342 
1343 template <>
1347 
1348  static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
1349 
1351  return nodes_iterator::begin(N->getEntry());
1352  }
1353 
1355  // df_iterator::end() returns an empty iterator so the node used doesn't
1356  // matter.
1357  return nodes_iterator::end(N);
1358  }
1359 };
1360 
1361 template <>
1364  using GraphRef = const VPRegionBlock *;
1366 
1367  static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
1368 
1370  return nodes_iterator::begin(N->getEntry());
1371  }
1372 
1374  // df_iterator::end() returns an empty iterator so the node used doesn't
1375  // matter.
1376  return nodes_iterator::end(N);
1377  }
1378 };
1379 
1380 template <>
1385 
1387  return N.Graph->getExit();
1388  }
1389 
1391  return nodes_iterator::begin(N->getExit());
1392  }
1393 
1395  // df_iterator::end() returns an empty iterator so the node used doesn't
1396  // matter.
1397  return nodes_iterator::end(N);
1398  }
1399 };
1400 
1401 //===----------------------------------------------------------------------===//
1402 // VPlan Utilities
1403 //===----------------------------------------------------------------------===//
1404 
1405 /// Class that provides utilities for VPBlockBases in VPlan.
1407 public:
1408  VPBlockUtils() = delete;
1409 
1410  /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
1411  /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
1412  /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. If \p BlockPtr
1413  /// has more than one successor, its conditional bit is propagated to \p
1414  /// NewBlock. \p NewBlock must have neither successors nor predecessors.
1415  static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
1416  assert(NewBlock->getSuccessors().empty() &&
1417  "Can't insert new block with successors.");
1418  // TODO: move successors from BlockPtr to NewBlock when this functionality
1419  // is necessary. For now, setBlockSingleSuccessor will assert if BlockPtr
1420  // already has successors.
1421  BlockPtr->setOneSuccessor(NewBlock);
1422  NewBlock->setPredecessors({BlockPtr});
1423  NewBlock->setParent(BlockPtr->getParent());
1424  }
1425 
1426  /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
1427  /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
1428  /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
1429  /// parent to \p IfTrue and \p IfFalse. \p Condition is set as the successor
1430  /// selector. \p BlockPtr must have no successors and \p IfTrue and \p IfFalse
1431  /// must have neither successors nor predecessors.
1432  static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
1433  VPValue *Condition, VPBlockBase *BlockPtr) {
1434  assert(IfTrue->getSuccessors().empty() &&
1435  "Can't insert IfTrue with successors.");
1436  assert(IfFalse->getSuccessors().empty() &&
1437  "Can't insert IfFalse with successors.");
1438  BlockPtr->setTwoSuccessors(IfTrue, IfFalse, Condition);
1439  IfTrue->setPredecessors({BlockPtr});
1440  IfFalse->setPredecessors({BlockPtr});
1441  IfTrue->setParent(BlockPtr->getParent());
1442  IfFalse->setParent(BlockPtr->getParent());
1443  }
1444 
1445  /// Connect VPBlockBases \p From and \p To bi-directionally. Append \p To to
1446  /// the successors of \p From and \p From to the predecessors of \p To. Both
1447  /// VPBlockBases must have the same parent, which can be null. Both
1448  /// VPBlockBases can be already connected to other VPBlockBases.
1450  assert((From->getParent() == To->getParent()) &&
1451  "Can't connect two block with different parents");
1452  assert(From->getNumSuccessors() < 2 &&
1453  "Blocks can't have more than two successors.");
1454  From->appendSuccessor(To);
1455  To->appendPredecessor(From);
1456  }
1457 
1458  /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
1459  /// from the successors of \p From and \p From from the predecessors of \p To.
1461  assert(To && "Successor to disconnect is null.");
1462  From->removeSuccessor(To);
1463  To->removePredecessor(From);
1464  }
1465 };
1466 
1467 } // end namespace llvm
1468 
1469 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
const std::string & getName() const
Definition: VPlan.h:394
LoopInfo * LI
Hold a pointer to LoopInfo to register new basic blocks in the loop.
Definition: VPlan.h:304
VPWidenRecipe(Instruction *I)
Definition: VPlan.h:666
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:259
const VPRegionBlock * getParent() const
Definition: VPlan.h:404
bool appendInstruction(Instruction *Instr)
Augment the recipe to include Instr, if it lies at its End.
Definition: VPlan.h:682
static NodeRef getEntryNode(Inverse< GraphRef > N)
Definition: VPlan.h:1386
void setAlsoPack(bool Pack)
Definition: VPlan.h:841
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:674
enum { VPBasicBlockSC, VPRegionBlockSC } VPBlockTy
An enumeration for keeping track of the concrete subclass of VPBlockBase that are actually instantiat...
Definition: VPlan.h:388
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:250
VectorizerValueMap(unsigned UF, unsigned VF)
Construct an empty map with the given unroll and vectorization factors.
Definition: VPlan.h:126
~VPBasicBlock() override
Definition: VPlan.h:951
SmallVectorImpl< VPBlockBase * >::const_iterator ChildIteratorType
Definition: VPlan.h:1306
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
InnerLoopVectorizer vectorizes loops which contain only one basic block to a specified vectorization ...
VPInterleaveRecipe(const InterleaveGroup *IG, VPValue *Mask)
Definition: VPlan.h:778
Various leaf nodes.
Definition: ISDOpcodes.h:60
VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exit, const std::string &Name="", bool IsReplicator=false)
Definition: VPlan.h:1034
const_reverse_iterator rbegin() const
Definition: VPlan.h:968
static NodeRef getEntryNode(GraphRef N)
Definition: VPlan.h:1348
Optional< VPIteration > Instance
Hold the indices to generate specific scalar instructions.
Definition: VPlan.h:245
VPRegionBlock * getParent()
Definition: VPlan.h:403
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:1101
VPInstruction(unsigned Opcode, ArrayRef< VPValue *> Operands)
Definition: VPlan.h:624
DenseMap< VPValue *, PerPartValuesTy > PerPartOutput
Definition: VPlan.h:253
Value * getScalarValue(Value *Key, const VPIteration &Instance)
Retrieve the existing scalar value that corresponds to Key and Instance.
Definition: VPlan.h:170
void setEntry(VPBlockBase *EntryBlock)
Set EntryBlock as the entry VPBlockBase of this VPRegionBlock.
Definition: VPlan.h:1062
VPlanIngredient(Value *V)
Definition: VPlan.h:1265
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1021
enum { VPBlendSC, VPBranchOnMaskSC, VPInstructionSC, VPInterleaveSC, VPPredInstPHISC, VPReplicateSC, VPWidenIntOrFpInductionSC, VPWidenMemoryInstructionSC, VPWidenPHISC, VPWidenSC, } VPRecipeTy
An enumeration for keeping track of the concrete subclass of VPRecipeBase that is actually instantiat...
Definition: VPlan.h:573
IRBuilder & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Definition: VPlan.h:310
VPRecipeBase & back()
Definition: VPlan.h:977
This is a helper struct for maintaining vectorization state.
Definition: VPlan.h:106
A Recipe for widening load/store operations.
Definition: VPlan.h:909
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.h:868
bool hasAnyScalarValue(Value *Key) const
Definition: VPlan.h:144
void addExternalDef(VPValue *VPVal)
Add VPVal to the pool of external definitions if it&#39;s not already in the pool.
Definition: VPlan.h:1177
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:428
void addVPValue(Value *V)
Definition: VPlan.h:1186
print alias Alias Set Printer
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:706
VPRecipeBase & front()
Definition: VPlan.h:975
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:548
unsigned getVPRecipeID() const
Definition: VPlan.h:581
VPValue * getVPValue(Value *V)
Definition: VPlan.h:1192
bool hasAnyVectorValue(Value *Key) const
Definition: VPlan.h:129
reverse_iterator rend()
Definition: VPlan.h:969
static bool classof(const VPRecipeBase *R)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:637
unsigned VF
The chosen Vectorization and Unroll Factors of the loop being vectorized.
Definition: VPlan.h:239
VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when control converges back from ...
Definition: VPlan.h:883
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:458
amdgpu Simplify well known AMD library false Value Value const Twine & Name
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
virtual ~VPCallback()
Definition: VPlan.h:225
VPBlockBase * getEntry()
Definition: VPlan.h:1058
size_t size() const
Definition: VPlan.h:972
static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBase NewBlock after BlockPtr.
Definition: VPlan.h:1415
bool hasVectorValue(Value *Key, unsigned Part) const
Definition: VPlan.h:134
VPBlocksTy & getSuccessors()
Definition: VPlan.h:421
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:743
VectorizerValueMap & ValueMap
Hold a reference to the Value state information used when generating the Values of the output IR...
Definition: VPlan.h:314
static StringRef getName(Value *V)
A recipe for handling all phi nodes except for integer and FP inductions.
Definition: VPlan.h:719
~VPRegionBlock() override
Definition: VPlan.h:1047
void setName(const Twine &newName)
Definition: VPlan.h:396
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:307
void insert(VPRecipeBase *Recipe, iterator InsertPt)
Definition: VPlan.h:992
const std::string & getName() const
Definition: VPlan.h:1171
VPBlocksTy & getPredecessors()
Definition: VPlan.h:424
static RecipeListTy VPBasicBlock::* getSublistAccess(VPRecipeBase *)
Returns a pointer to a member of the recipe list.
Definition: VPlan.h:983
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:1331
void setName(const Twine &newName)
Definition: VPlan.h:1173
VPWidenPHIRecipe(PHINode *Phi)
Definition: VPlan.h:724
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:1310
Key
PAL metadata keys.
VPBlockBase * getSinglePredecessor() const
Definition: VPlan.h:434
unsigned End
Definition: VPlan.h:70
VPlanPrinter prints a given VPlan to a given output stream.
Definition: VPlan.h:1212
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:1314
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:1089
static nodes_iterator nodes_begin(GraphRef N)
Definition: VPlan.h:1369
static NodeRef getEntryNode(GraphRef N)
Definition: VPlan.h:1367
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:728
This class is used to enable the VPlan to invoke a method of ILV.
Definition: VPlan.h:224
The group of interleaved loads/stores sharing the same stride and close to each other.
Definition: VectorUtils.h:221
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
const VPBlockBase * getExit() const
Definition: VPlan.h:1075
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:231
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:464
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:480
unsigned getVPBlockID() const
Definition: VPlan.h:401
static bool classof(const VPValue *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:632
unsigned getVPValueID() const
Definition: VPlanValue.h:86
VPInstruction(unsigned Opcode, std::initializer_list< VPValue *> Operands)
Definition: VPlan.h:628
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
This class represents a truncation of integer types.
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:962
void resetScalarValue(Value *Key, const VPIteration &Instance, Value *Scalar)
Reset the scalar value associated with Key for Part and Lane.
Definition: VPlan.h:214
bool isLegalToHoistInto()
Return true if it is legal to hoist instructions into this block.
Definition: VPlan.h:539
SmallVectorImpl< VPBlockBase * >::iterator ChildIteratorType
Definition: VPlan.h:1291
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe...
Definition: VPlan.h:1001
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:474
#define P(N)
static nodes_iterator nodes_end(GraphRef N)
Definition: VPlan.h:1394
This class augments VPValue with operands which provide the inverse def-use edges from VPValue&#39;s user...
Definition: VPlanValue.h:117
An ilist node that can access its parent list.
Definition: ilist_node.h:257
typename VPBlockBase *::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:79
void setOneSuccessor(VPBlockBase *Successor)
Set a given VPBlockBase Successor as the single successor of this VPBlockBase.
Definition: VPlan.h:494
const InterleaveGroup * getInterleaveGroup()
Definition: VPlan.h:796
VPWidenMemoryInstructionRecipe(Instruction &Instr, VPValue *Mask)
Definition: VPlan.h:915
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:922
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:1327
VPBlendRecipe(PHINode *Phi, ArrayRef< VPValue *> Masks)
Definition: VPlan.h:749
void setExit(VPBlockBase *ExitBlock)
Set ExitBlock as the exit VPBlockBase of this VPRegionBlock.
Definition: VPlan.h:1080
This file defines VPLoopInfo analysis and VPLoop class.
reverse_iterator rbegin()
Definition: VPlan.h:967
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
const VPValue * getCondBit() const
Definition: VPlan.h:487
SmallVector< Value *, 2 > PerPartValuesTy
A type for vectorized values in the new loop.
Definition: VPlan.h:251
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
bool hasScalarValue(Value *Key, const VPIteration &Instance) const
Definition: VPlan.h:149
VPWidenIntOrFpInductionRecipe(PHINode *IV, TruncInst *Trunc=nullptr)
Definition: VPlan.h:701
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:294
const unsigned Start
Definition: VPlan.h:67
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:371
size_t getNumPredecessors() const
Definition: VPlan.h:439
static NodeRef getEntryNode(NodeRef N)
Definition: VPlan.h:1293
void addCBV(VPValue *CBV)
Add CBV to the vector of condition bit values.
Definition: VPlan.h:1182
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:73
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:1299
void printAsOperand(raw_ostream &OS, bool PrintType) const
Definition: VPlan.h:528
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:280
size_t getNumSuccessors() const
Definition: VPlan.h:438
VPCallback & Callback
Definition: VPlan.h:326
VPBlockBase * setEntry(VPBlockBase *Block)
Definition: VPlan.h:1158
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
bool hasVF(unsigned VF)
Definition: VPlan.h:1169
self_iterator getIterator()
Definition: ilist_node.h:82
VPValue2ValueTy VPValue2Value
Hold a reference to a mapping between VPValues in VPlan and original Values they correspond to...
Definition: VPlan.h:318
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:181
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:298
static bool classof(const VPBlockBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:988
VPBlockBase & front() const
Definition: VPlan.h:1073
SmallVectorImpl< VPBlockBase * >::iterator ChildIteratorType
Definition: VPlan.h:1323
iterator erase(const_iterator CI)
Definition: SmallVector.h:445
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:1449
size_t size() const
Definition: SmallVector.h:53
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1063
void setScalarValue(Value *Key, const VPIteration &Instance, Value *Scalar)
Set a scalar value associated with Key and Instance.
Definition: VPlan.h:188
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:390
static nodes_iterator nodes_end(GraphRef N)
Definition: VPlan.h:1373
static void deleteCFG(VPBlockBase *Entry)
Delete all blocks reachable from a given VPBlockBase, inclusive.
Definition: VPlan.cpp:105
void setPredecessors(ArrayRef< VPBlockBase *> NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
Definition: VPlan.h:515
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:936
VPBlockBase(const unsigned char SC, const std::string &N)
Definition: VPlan.h:380
const_iterator begin() const
Definition: VPlan.h:963
unsigned Lane
in [0..VF)
Definition: VPlan.h:86
const VPRecipeBase & back() const
Definition: VPlan.h:976
Iterator for intrusive lists based on ilist_node.
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:503
See the file comment.
Definition: ValueMap.h:86
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
const GraphType & Graph
Definition: GraphTraits.h:97
static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPValue *Condition, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBases IfTrue and IfFalse after BlockPtr.
Definition: VPlan.h:1432
BlockVerifier::State From
A range of powers-of-2 vectorization factors with fixed start and adjustable end. ...
Definition: VPlan.h:65
const VPRecipeBase & front() const
Definition: VPlan.h:974
VPLoopInfo & getVPLoopInfo()
Return the VPLoopInfo analysis for this VPlan.
Definition: VPlan.h:1199
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:331
static NodeRef getEntryNode(Inverse< NodeRef > B)
Definition: VPlan.h:1325
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
VPReplicateRecipe(Instruction *I, bool IsUniform, bool IsPredicated=false)
Definition: VPlan.h:818
Class that provides utilities for VPBlockBases in VPlan.
Definition: VPlan.h:1406
static NodeRef getEntryNode(NodeRef N)
Definition: VPlan.h:1308
CHAIN = SC CHAIN, Imm128 - System call.
static bool classof(const VPBlockBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:1053
void setCondBit(VPValue *CV)
Definition: VPlan.h:489
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:420
unsigned getNumIncomingValues() const
Return the number of incoming edges.
const VPBlockBase * getEntry() const
Definition: VPlan.h:1057
void addVF(unsigned VF)
Definition: VPlan.h:1167
VPInterleaveRecipe is a recipe for transforming an interleave group of load or stores into one wide l...
Definition: VPlan.h:772
VPValue * getCondBit()
Definition: VPlan.h:485
VPValue * getOrCreateBackedgeTakenCount()
The backedge taken count of the original loop.
Definition: VPlan.h:1161
void resetVectorValue(Value *Key, unsigned Part, Value *Vector)
Reset the vector value associated with Key for the given Part.
Definition: VPlan.h:205
VPBlockBase * getExit()
Definition: VPlan.h:1076
InnerLoopVectorizer * ILV
Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
Definition: VPlan.h:324
VPRegionBlock(const std::string &Name="", bool IsReplicator=false)
Definition: VPlan.h:1043
const VPBasicBlock * getParent() const
Definition: VPlan.h:585
bool empty() const
Definition: VPlan.h:973
void print(raw_ostream &OS) const
Definition: VPlan.h:532
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
iterator insert(iterator where, pointer New)
Definition: ilist.h:228
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:423
Flatten the CFG
static nodes_iterator nodes_begin(GraphRef N)
Definition: VPlan.h:1390
Value * getVectorValue(Value *Key, unsigned Part)
Retrieve the existing vector value that corresponds to Key and Part.
Definition: VPlan.h:163
void clear()
Definition: ilist.h:309
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition: VPlan.h:803
VPBlockBase * getEntry()
Definition: VPlan.h:1155
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:859
VPTransformState(unsigned VF, unsigned UF, LoopInfo *LI, DominatorTree *DT, IRBuilder<> &Builder, VectorizerValueMap &ValueMap, InnerLoopVectorizer *ILV, VPCallback &Callback)
Definition: VPlan.h:232
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:895
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
VPRecipeBase(const unsigned char SC)
Definition: VPlan.h:575
VPPredInstPHIRecipe(Instruction *PredInst)
Construct a VPPredInstPHIRecipe given PredInst whose value needs a phi nodes after merging back from ...
Definition: VPlan.h:890
const VPBlockBase * getEntry() const
Definition: VPlan.h:1156
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:832
VPlan(VPBlockBase *Entry=nullptr)
Definition: VPlan.h:1136
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector and ...
Definition: VPlan.h:695
unsigned getOpcode() const
Definition: VPlan.h:641
const_iterator end() const
Definition: VPlan.h:965
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2033
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:146
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:18
void setVectorValue(Value *Key, unsigned Part, Value *Vector)
Set a vector value associated with Key and Part.
Definition: VPlan.h:177
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:759
Definition: JSON.cpp:592
iterator end()
Definition: VPlan.h:964
VPBasicBlock * getParent()
Definition: VPlan.h:584
VPWidenRecipe is a recipe for producing a copy of vector type for each Instruction in its ingredients...
Definition: VPlan.h:659
aarch64 promote const
This file contains the declarations of the entities induced by Vectorization Plans, e.g.
LLVM Value Representation.
Definition: Value.h:73
A recipe for generating conditional branches on the bits of a mask.
Definition: VPlan.h:848
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:1295
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
A recipe for vectorizing a phi-node as a sequence of mask-based select instructions.
Definition: VPlan.h:741
In what follows, the term "input IR" refers to code that is fed into the vectorizer whereas the term ...
Definition: VPlan.h:81
static nodes_iterator nodes_end(GraphRef N)
Definition: VPlan.h:1354
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:786
unsigned Part
in [0..UF)
Definition: VPlan.h:83
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:608
RecipeListTy & getRecipeList()
Returns a reference to the list of recipes.
Definition: VPlan.h:980
VPBranchOnMaskRecipe(VPValue *BlockInMask)
Definition: VPlan.h:853
bool use_empty() const
Definition: Value.h:323
const_reverse_iterator rend() const
Definition: VPlan.h:970
static nodes_iterator nodes_begin(GraphRef N)
Definition: VPlan.h:1350
VPBasicBlock(const Twine &Name="", VPRecipeBase *Recipe=nullptr)
Definition: VPlan.h:945
void setParent(VPRegionBlock *P)
Definition: VPlan.h:406
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:1460
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:144
const VPLoopInfo & getVPLoopInfo() const
Definition: VPlan.h:1200
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:165