LLVM  7.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 "VPlanValue.h"
30 #include "llvm/ADT/DenseMap.h"
31 #include "llvm/ADT/GraphTraits.h"
32 #include "llvm/ADT/Optional.h"
33 #include "llvm/ADT/SmallSet.h"
34 #include "llvm/ADT/SmallVector.h"
35 #include "llvm/ADT/Twine.h"
36 #include "llvm/ADT/ilist.h"
37 #include "llvm/ADT/ilist_node.h"
38 #include "llvm/IR/IRBuilder.h"
39 #include <algorithm>
40 #include <cassert>
41 #include <cstddef>
42 #include <map>
43 #include <string>
44 
45 namespace llvm {
46 
47 class LoopVectorizationLegality;
48 class LoopVectorizationCostModel;
49 class BasicBlock;
50 class DominatorTree;
51 class InnerLoopVectorizer;
52 class InterleaveGroup;
53 class LoopInfo;
54 class raw_ostream;
55 class Value;
56 class VPBasicBlock;
57 class VPRegionBlock;
58 
59 /// In what follows, the term "input IR" refers to code that is fed into the
60 /// vectorizer whereas the term "output IR" refers to code that is generated by
61 /// the vectorizer.
62 
63 /// VPIteration represents a single point in the iteration space of the output
64 /// (vectorized and/or unrolled) IR loop.
65 struct VPIteration {
66  /// in [0..UF)
67  unsigned Part;
68 
69  /// in [0..VF)
70  unsigned Lane;
71 };
72 
73 /// This is a helper struct for maintaining vectorization state. It's used for
74 /// mapping values from the original loop to their corresponding values in
75 /// the new loop. Two mappings are maintained: one for vectorized values and
76 /// one for scalarized values. Vectorized values are represented with UF
77 /// vector values in the new loop, and scalarized values are represented with
78 /// UF x VF scalar values in the new loop. UF and VF are the unroll and
79 /// vectorization factors, respectively.
80 ///
81 /// Entries can be added to either map with setVectorValue and setScalarValue,
82 /// which assert that an entry was not already added before. If an entry is to
83 /// replace an existing one, call resetVectorValue and resetScalarValue. This is
84 /// currently needed to modify the mapped values during "fix-up" operations that
85 /// occur once the first phase of widening is complete. These operations include
86 /// type truncation and the second phase of recurrence widening.
87 ///
88 /// Entries from either map can be retrieved using the getVectorValue and
89 /// getScalarValue functions, which assert that the desired value exists.
91  friend struct VPTransformState;
92 
93 private:
94  /// The unroll factor. Each entry in the vector map contains UF vector values.
95  unsigned UF;
96 
97  /// The vectorization factor. Each entry in the scalar map contains UF x VF
98  /// scalar values.
99  unsigned VF;
100 
101  /// The vector and scalar map storage. We use std::map and not DenseMap
102  /// because insertions to DenseMap invalidate its iterators.
105  std::map<Value *, VectorParts> VectorMapStorage;
106  std::map<Value *, ScalarParts> ScalarMapStorage;
107 
108 public:
109  /// Construct an empty map with the given unroll and vectorization factors.
110  VectorizerValueMap(unsigned UF, unsigned VF) : UF(UF), VF(VF) {}
111 
112  /// \return True if the map has any vector entry for \p Key.
113  bool hasAnyVectorValue(Value *Key) const {
114  return VectorMapStorage.count(Key);
115  }
116 
117  /// \return True if the map has a vector entry for \p Key and \p Part.
118  bool hasVectorValue(Value *Key, unsigned Part) const {
119  assert(Part < UF && "Queried Vector Part is too large.");
120  if (!hasAnyVectorValue(Key))
121  return false;
122  const VectorParts &Entry = VectorMapStorage.find(Key)->second;
123  assert(Entry.size() == UF && "VectorParts has wrong dimensions.");
124  return Entry[Part] != nullptr;
125  }
126 
127  /// \return True if the map has any scalar entry for \p Key.
128  bool hasAnyScalarValue(Value *Key) const {
129  return ScalarMapStorage.count(Key);
130  }
131 
132  /// \return True if the map has a scalar entry for \p Key and \p Instance.
133  bool hasScalarValue(Value *Key, const VPIteration &Instance) const {
134  assert(Instance.Part < UF && "Queried Scalar Part is too large.");
135  assert(Instance.Lane < VF && "Queried Scalar Lane is too large.");
136  if (!hasAnyScalarValue(Key))
137  return false;
138  const ScalarParts &Entry = ScalarMapStorage.find(Key)->second;
139  assert(Entry.size() == UF && "ScalarParts has wrong dimensions.");
140  assert(Entry[Instance.Part].size() == VF &&
141  "ScalarParts has wrong dimensions.");
142  return Entry[Instance.Part][Instance.Lane] != nullptr;
143  }
144 
145  /// Retrieve the existing vector value that corresponds to \p Key and
146  /// \p Part.
148  assert(hasVectorValue(Key, Part) && "Getting non-existent value.");
149  return VectorMapStorage[Key][Part];
150  }
151 
152  /// Retrieve the existing scalar value that corresponds to \p Key and
153  /// \p Instance.
154  Value *getScalarValue(Value *Key, const VPIteration &Instance) {
155  assert(hasScalarValue(Key, Instance) && "Getting non-existent value.");
156  return ScalarMapStorage[Key][Instance.Part][Instance.Lane];
157  }
158 
159  /// Set a vector value associated with \p Key and \p Part. Assumes such a
160  /// value is not already set. If it is, use resetVectorValue() instead.
161  void setVectorValue(Value *Key, unsigned Part, Value *Vector) {
162  assert(!hasVectorValue(Key, Part) && "Vector value already set for part");
163  if (!VectorMapStorage.count(Key)) {
164  VectorParts Entry(UF);
165  VectorMapStorage[Key] = Entry;
166  }
167  VectorMapStorage[Key][Part] = Vector;
168  }
169 
170  /// Set a scalar value associated with \p Key and \p Instance. Assumes such a
171  /// value is not already set.
172  void setScalarValue(Value *Key, const VPIteration &Instance, Value *Scalar) {
173  assert(!hasScalarValue(Key, Instance) && "Scalar value already set");
174  if (!ScalarMapStorage.count(Key)) {
175  ScalarParts Entry(UF);
176  // TODO: Consider storing uniform values only per-part, as they occupy
177  // lane 0 only, keeping the other VF-1 redundant entries null.
178  for (unsigned Part = 0; Part < UF; ++Part)
179  Entry[Part].resize(VF, nullptr);
180  ScalarMapStorage[Key] = Entry;
181  }
182  ScalarMapStorage[Key][Instance.Part][Instance.Lane] = Scalar;
183  }
184 
185  /// Reset the vector value associated with \p Key for the given \p Part.
186  /// This function can be used to update values that have already been
187  /// vectorized. This is the case for "fix-up" operations including type
188  /// truncation and the second phase of recurrence vectorization.
189  void resetVectorValue(Value *Key, unsigned Part, Value *Vector) {
190  assert(hasVectorValue(Key, Part) && "Vector value not set for part");
191  VectorMapStorage[Key][Part] = Vector;
192  }
193 
194  /// Reset the scalar value associated with \p Key for \p Part and \p Lane.
195  /// This function can be used to update values that have already been
196  /// scalarized. This is the case for "fix-up" operations including scalar phi
197  /// nodes for scalarized and predicated instructions.
198  void resetScalarValue(Value *Key, const VPIteration &Instance,
199  Value *Scalar) {
200  assert(hasScalarValue(Key, Instance) &&
201  "Scalar value not set for part and lane");
202  ScalarMapStorage[Key][Instance.Part][Instance.Lane] = Scalar;
203  }
204 };
205 
206 /// This class is used to enable the VPlan to invoke a method of ILV. This is
207 /// needed until the method is refactored out of ILV and becomes reusable.
208 struct VPCallback {
209  virtual ~VPCallback() {}
210  virtual Value *getOrCreateVectorValues(Value *V, unsigned Part) = 0;
211 };
212 
213 /// VPTransformState holds information passed down when "executing" a VPlan,
214 /// needed for generating the output IR.
216  VPTransformState(unsigned VF, unsigned UF, LoopInfo *LI, DominatorTree *DT,
218  InnerLoopVectorizer *ILV, VPCallback &Callback)
219  : VF(VF), UF(UF), Instance(), LI(LI), DT(DT), Builder(Builder),
220  ValueMap(ValueMap), ILV(ILV), Callback(Callback) {}
221 
222  /// The chosen Vectorization and Unroll Factors of the loop being vectorized.
223  unsigned VF;
224  unsigned UF;
225 
226  /// Hold the indices to generate specific scalar instructions. Null indicates
227  /// that all instances are to be generated, using either scalar or vector
228  /// instructions.
230 
231  struct DataState {
232  /// A type for vectorized values in the new loop. Each value from the
233  /// original loop, when vectorized, is represented by UF vector values in
234  /// the new unrolled loop, where UF is the unroll factor.
236 
238  } Data;
239 
240  /// Get the generated Value for a given VPValue and a given Part. Note that
241  /// as some Defs are still created by ILV and managed in its ValueMap, this
242  /// method will delegate the call to ILV in such cases in order to provide
243  /// callers a consistent API.
244  /// \see set.
245  Value *get(VPValue *Def, unsigned Part) {
246  // If Values have been set for this Def return the one relevant for \p Part.
247  if (Data.PerPartOutput.count(Def))
248  return Data.PerPartOutput[Def][Part];
249  // Def is managed by ILV: bring the Values from ValueMap.
250  return Callback.getOrCreateVectorValues(VPValue2Value[Def], Part);
251  }
252 
253  /// Set the generated Value for a given VPValue and a given Part.
254  void set(VPValue *Def, Value *V, unsigned Part) {
255  if (!Data.PerPartOutput.count(Def)) {
256  DataState::PerPartValuesTy Entry(UF);
257  Data.PerPartOutput[Def] = Entry;
258  }
259  Data.PerPartOutput[Def][Part] = V;
260  }
261 
262  /// Hold state information used when constructing the CFG of the output IR,
263  /// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks.
264  struct CFGState {
265  /// The previous VPBasicBlock visited. Initially set to null.
266  VPBasicBlock *PrevVPBB = nullptr;
267 
268  /// The previous IR BasicBlock created or used. Initially set to the new
269  /// header BasicBlock.
270  BasicBlock *PrevBB = nullptr;
271 
272  /// The last IR BasicBlock in the output IR. Set to the new latch
273  /// BasicBlock, used for placing the newly created BasicBlocks.
274  BasicBlock *LastBB = nullptr;
275 
276  /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case
277  /// of replication, maps the BasicBlock of the last replica created.
279 
280  CFGState() = default;
281  } CFG;
282 
283  /// Hold a pointer to LoopInfo to register new basic blocks in the loop.
285 
286  /// Hold a pointer to Dominator Tree to register new basic blocks in the loop.
288 
289  /// Hold a reference to the IRBuilder used to generate output IR code.
291 
292  /// Hold a reference to the Value state information used when generating the
293  /// Values of the output IR.
295 
296  /// Hold a reference to a mapping between VPValues in VPlan and original
297  /// Values they correspond to.
299 
300  /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
302 
304 };
305 
306 /// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
307 /// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.
308 class VPBlockBase {
309 private:
310  const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
311 
312  /// An optional name for the block.
313  std::string Name;
314 
315  /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if
316  /// it is a topmost VPBlockBase.
317  VPRegionBlock *Parent = nullptr;
318 
319  /// List of predecessor blocks.
320  SmallVector<VPBlockBase *, 1> Predecessors;
321 
322  /// List of successor blocks.
324 
325  /// Add \p Successor as the last successor to this block.
326  void appendSuccessor(VPBlockBase *Successor) {
327  assert(Successor && "Cannot add nullptr successor!");
328  Successors.push_back(Successor);
329  }
330 
331  /// Add \p Predecessor as the last predecessor to this block.
332  void appendPredecessor(VPBlockBase *Predecessor) {
333  assert(Predecessor && "Cannot add nullptr predecessor!");
334  Predecessors.push_back(Predecessor);
335  }
336 
337  /// Remove \p Predecessor from the predecessors of this block.
338  void removePredecessor(VPBlockBase *Predecessor) {
339  auto Pos = std::find(Predecessors.begin(), Predecessors.end(), Predecessor);
340  assert(Pos && "Predecessor does not exist");
341  Predecessors.erase(Pos);
342  }
343 
344  /// Remove \p Successor from the successors of this block.
345  void removeSuccessor(VPBlockBase *Successor) {
346  auto Pos = std::find(Successors.begin(), Successors.end(), Successor);
347  assert(Pos && "Successor does not exist");
348  Successors.erase(Pos);
349  }
350 
351 protected:
352  VPBlockBase(const unsigned char SC, const std::string &N)
353  : SubclassID(SC), Name(N) {}
354 
355 public:
356  /// An enumeration for keeping track of the concrete subclass of VPBlockBase
357  /// that are actually instantiated. Values of this enumeration are kept in the
358  /// SubclassID field of the VPBlockBase objects. They are used for concrete
359  /// type identification.
360  using VPBlockTy = enum { VPBasicBlockSC, VPRegionBlockSC };
361 
363 
364  virtual ~VPBlockBase() = default;
365 
366  const std::string &getName() const { return Name; }
367 
368  void setName(const Twine &newName) { Name = newName.str(); }
369 
370  /// \return an ID for the concrete type of this object.
371  /// This is used to implement the classof checks. This should not be used
372  /// for any other purpose, as the values may change as LLVM evolves.
373  unsigned getVPBlockID() const { return SubclassID; }
374 
375  const VPRegionBlock *getParent() const { return Parent; }
376 
377  void setParent(VPRegionBlock *P) { Parent = P; }
378 
379  /// \return the VPBasicBlock that is the entry of this VPBlockBase,
380  /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
381  /// VPBlockBase is a VPBasicBlock, it is returned.
382  const VPBasicBlock *getEntryBasicBlock() const;
383  VPBasicBlock *getEntryBasicBlock();
384 
385  /// \return the VPBasicBlock that is the exit of this VPBlockBase,
386  /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
387  /// VPBlockBase is a VPBasicBlock, it is returned.
388  const VPBasicBlock *getExitBasicBlock() const;
389  VPBasicBlock *getExitBasicBlock();
390 
391  const VPBlocksTy &getSuccessors() const { return Successors; }
392  VPBlocksTy &getSuccessors() { return Successors; }
393 
394  const VPBlocksTy &getPredecessors() const { return Predecessors; }
395  VPBlocksTy &getPredecessors() { return Predecessors; }
396 
397  /// \return the successor of this VPBlockBase if it has a single successor.
398  /// Otherwise return a null pointer.
400  return (Successors.size() == 1 ? *Successors.begin() : nullptr);
401  }
402 
403  /// \return the predecessor of this VPBlockBase if it has a single
404  /// predecessor. Otherwise return a null pointer.
406  return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr);
407  }
408 
409  /// An Enclosing Block of a block B is any block containing B, including B
410  /// itself. \return the closest enclosing block starting from "this", which
411  /// has successors. \return the root enclosing block if all enclosing blocks
412  /// have no successors.
413  VPBlockBase *getEnclosingBlockWithSuccessors();
414 
415  /// \return the closest enclosing block starting from "this", which has
416  /// predecessors. \return the root enclosing block if all enclosing blocks
417  /// have no predecessors.
418  VPBlockBase *getEnclosingBlockWithPredecessors();
419 
420  /// \return the successors either attached directly to this VPBlockBase or, if
421  /// this VPBlockBase is the exit block of a VPRegionBlock and has no
422  /// successors of its own, search recursively for the first enclosing
423  /// VPRegionBlock that has successors and return them. If no such
424  /// VPRegionBlock exists, return the (empty) successors of the topmost
425  /// VPBlockBase reached.
427  return getEnclosingBlockWithSuccessors()->getSuccessors();
428  }
429 
430  /// \return the hierarchical successor of this VPBlockBase if it has a single
431  /// hierarchical successor. Otherwise return a null pointer.
433  return getEnclosingBlockWithSuccessors()->getSingleSuccessor();
434  }
435 
436  /// \return the predecessors either attached directly to this VPBlockBase or,
437  /// if this VPBlockBase is the entry block of a VPRegionBlock and has no
438  /// predecessors of its own, search recursively for the first enclosing
439  /// VPRegionBlock that has predecessors and return them. If no such
440  /// VPRegionBlock exists, return the (empty) predecessors of the topmost
441  /// VPBlockBase reached.
443  return getEnclosingBlockWithPredecessors()->getPredecessors();
444  }
445 
446  /// \return the hierarchical predecessor of this VPBlockBase if it has a
447  /// single hierarchical predecessor. Otherwise return a null pointer.
449  return getEnclosingBlockWithPredecessors()->getSinglePredecessor();
450  }
451 
452  /// Sets a given VPBlockBase \p Successor as the single successor and \return
453  /// \p Successor. The parent of this Block is copied to be the parent of
454  /// \p Successor.
456  assert(Successors.empty() && "Setting one successor when others exist.");
457  appendSuccessor(Successor);
458  Successor->appendPredecessor(this);
459  Successor->Parent = Parent;
460  return Successor;
461  }
462 
463  /// Sets two given VPBlockBases \p IfTrue and \p IfFalse to be the two
464  /// successors. The parent of this Block is copied to be the parent of both
465  /// \p IfTrue and \p IfFalse.
466  void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse) {
467  assert(Successors.empty() && "Setting two successors when others exist.");
468  appendSuccessor(IfTrue);
469  appendSuccessor(IfFalse);
470  IfTrue->appendPredecessor(this);
471  IfFalse->appendPredecessor(this);
472  IfTrue->Parent = Parent;
473  IfFalse->Parent = Parent;
474  }
475 
476  void disconnectSuccessor(VPBlockBase *Successor) {
477  assert(Successor && "Successor to disconnect is null.");
478  removeSuccessor(Successor);
479  Successor->removePredecessor(this);
480  }
481 
482  /// The method which generates the output IR that correspond to this
483  /// VPBlockBase, thereby "executing" the VPlan.
484  virtual void execute(struct VPTransformState *State) = 0;
485 
486  /// Delete all blocks reachable from a given VPBlockBase, inclusive.
487  static void deleteCFG(VPBlockBase *Entry);
488 };
489 
490 /// VPRecipeBase is a base class modeling a sequence of one or more output IR
491 /// instructions.
492 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> {
493  friend VPBasicBlock;
494 
495 private:
496  const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
497 
498  /// Each VPRecipe belongs to a single VPBasicBlock.
499  VPBasicBlock *Parent = nullptr;
500 
501 public:
502  /// An enumeration for keeping track of the concrete subclass of VPRecipeBase
503  /// that is actually instantiated. Values of this enumeration are kept in the
504  /// SubclassID field of the VPRecipeBase objects. They are used for concrete
505  /// type identification.
506  using VPRecipeTy = enum {
507  VPBlendSC,
508  VPBranchOnMaskSC,
509  VPInstructionSC,
510  VPInterleaveSC,
511  VPPredInstPHISC,
512  VPReplicateSC,
513  VPWidenIntOrFpInductionSC,
514  VPWidenMemoryInstructionSC,
515  VPWidenPHISC,
516  VPWidenSC,
517  };
518 
519  VPRecipeBase(const unsigned char SC) : SubclassID(SC) {}
520  virtual ~VPRecipeBase() = default;
521 
522  /// \return an ID for the concrete type of this object.
523  /// This is used to implement the classof checks. This should not be used
524  /// for any other purpose, as the values may change as LLVM evolves.
525  unsigned getVPRecipeID() const { return SubclassID; }
526 
527  /// \return the VPBasicBlock which this VPRecipe belongs to.
528  VPBasicBlock *getParent() { return Parent; }
529  const VPBasicBlock *getParent() const { return Parent; }
530 
531  /// The method which generates the output IR instructions that correspond to
532  /// this VPRecipe, thereby "executing" the VPlan.
533  virtual void execute(struct VPTransformState &State) = 0;
534 
535  /// Each recipe prints itself.
536  virtual void print(raw_ostream &O, const Twine &Indent) const = 0;
537 };
538 
539 /// This is a concrete Recipe that models a single VPlan-level instruction.
540 /// While as any Recipe it may generate a sequence of IR instructions when
541 /// executed, these instructions would always form a single-def expression as
542 /// the VPInstruction is also a single def-use vertex.
543 class VPInstruction : public VPUser, public VPRecipeBase {
544 public:
545  /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
546  enum { Not = Instruction::OtherOpsEnd + 1 };
547 
548 private:
549  typedef unsigned char OpcodeTy;
550  OpcodeTy Opcode;
551 
552  /// Utility method serving execute(): generates a single instance of the
553  /// modeled instruction.
554  void generateInstruction(VPTransformState &State, unsigned Part);
555 
556 public:
557  VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands)
558  : VPUser(VPValue::VPInstructionSC, Operands),
559  VPRecipeBase(VPRecipeBase::VPInstructionSC), Opcode(Opcode) {}
560 
561  /// Method to support type inquiry through isa, cast, and dyn_cast.
562  static inline bool classof(const VPValue *V) {
563  return V->getVPValueID() == VPValue::VPInstructionSC;
564  }
565 
566  /// Method to support type inquiry through isa, cast, and dyn_cast.
567  static inline bool classof(const VPRecipeBase *R) {
568  return R->getVPRecipeID() == VPRecipeBase::VPInstructionSC;
569  }
570 
571  unsigned getOpcode() const { return Opcode; }
572 
573  /// Generate the instruction.
574  /// TODO: We currently execute only per-part unless a specific instance is
575  /// provided.
576  void execute(VPTransformState &State) override;
577 
578  /// Print the Recipe.
579  void print(raw_ostream &O, const Twine &Indent) const override;
580 
581  /// Print the VPInstruction.
582  void print(raw_ostream &O) const;
583 };
584 
585 /// VPWidenRecipe is a recipe for producing a copy of vector type for each
586 /// Instruction in its ingredients independently, in order. This recipe covers
587 /// most of the traditional vectorization cases where each ingredient transforms
588 /// into a vectorized version of itself.
589 class VPWidenRecipe : public VPRecipeBase {
590 private:
591  /// Hold the ingredients by pointing to their original BasicBlock location.
592  BasicBlock::iterator Begin;
594 
595 public:
597  End = I->getIterator();
598  Begin = End++;
599  }
600 
601  ~VPWidenRecipe() override = default;
602 
603  /// Method to support type inquiry through isa, cast, and dyn_cast.
604  static inline bool classof(const VPRecipeBase *V) {
605  return V->getVPRecipeID() == VPRecipeBase::VPWidenSC;
606  }
607 
608  /// Produce widened copies of all Ingredients.
609  void execute(VPTransformState &State) override;
610 
611  /// Augment the recipe to include Instr, if it lies at its End.
613  if (End != Instr->getIterator())
614  return false;
615  End++;
616  return true;
617  }
618 
619  /// Print the recipe.
620  void print(raw_ostream &O, const Twine &Indent) const override;
621 };
622 
623 /// A recipe for handling phi nodes of integer and floating-point inductions,
624 /// producing their vector and scalar values.
626 private:
627  PHINode *IV;
628  TruncInst *Trunc;
629 
630 public:
632  : VPRecipeBase(VPWidenIntOrFpInductionSC), IV(IV), Trunc(Trunc) {}
633  ~VPWidenIntOrFpInductionRecipe() override = default;
634 
635  /// Method to support type inquiry through isa, cast, and dyn_cast.
636  static inline bool classof(const VPRecipeBase *V) {
637  return V->getVPRecipeID() == VPRecipeBase::VPWidenIntOrFpInductionSC;
638  }
639 
640  /// Generate the vectorized and scalarized versions of the phi node as
641  /// needed by their users.
642  void execute(VPTransformState &State) override;
643 
644  /// Print the recipe.
645  void print(raw_ostream &O, const Twine &Indent) const override;
646 };
647 
648 /// A recipe for handling all phi nodes except for integer and FP inductions.
650 private:
651  PHINode *Phi;
652 
653 public:
654  VPWidenPHIRecipe(PHINode *Phi) : VPRecipeBase(VPWidenPHISC), Phi(Phi) {}
655  ~VPWidenPHIRecipe() override = default;
656 
657  /// Method to support type inquiry through isa, cast, and dyn_cast.
658  static inline bool classof(const VPRecipeBase *V) {
659  return V->getVPRecipeID() == VPRecipeBase::VPWidenPHISC;
660  }
661 
662  /// Generate the phi/select nodes.
663  void execute(VPTransformState &State) override;
664 
665  /// Print the recipe.
666  void print(raw_ostream &O, const Twine &Indent) const override;
667 };
668 
669 /// A recipe for vectorizing a phi-node as a sequence of mask-based select
670 /// instructions.
671 class VPBlendRecipe : public VPRecipeBase {
672 private:
673  PHINode *Phi;
674 
675  /// The blend operation is a User of a mask, if not null.
676  std::unique_ptr<VPUser> User;
677 
678 public:
680  : VPRecipeBase(VPBlendSC), Phi(Phi) {
681  assert((Phi->getNumIncomingValues() == 1 ||
682  Phi->getNumIncomingValues() == Masks.size()) &&
683  "Expected the same number of incoming values and masks");
684  if (!Masks.empty())
685  User.reset(new VPUser(Masks));
686  }
687 
688  /// Method to support type inquiry through isa, cast, and dyn_cast.
689  static inline bool classof(const VPRecipeBase *V) {
690  return V->getVPRecipeID() == VPRecipeBase::VPBlendSC;
691  }
692 
693  /// Generate the phi/select nodes.
694  void execute(VPTransformState &State) override;
695 
696  /// Print the recipe.
697  void print(raw_ostream &O, const Twine &Indent) const override;
698 };
699 
700 /// VPInterleaveRecipe is a recipe for transforming an interleave group of load
701 /// or stores into one wide load/store and shuffles.
703 private:
704  const InterleaveGroup *IG;
705 
706 public:
708  : VPRecipeBase(VPInterleaveSC), IG(IG) {}
709  ~VPInterleaveRecipe() override = default;
710 
711  /// Method to support type inquiry through isa, cast, and dyn_cast.
712  static inline bool classof(const VPRecipeBase *V) {
713  return V->getVPRecipeID() == VPRecipeBase::VPInterleaveSC;
714  }
715 
716  /// Generate the wide load or store, and shuffles.
717  void execute(VPTransformState &State) override;
718 
719  /// Print the recipe.
720  void print(raw_ostream &O, const Twine &Indent) const override;
721 
722  const InterleaveGroup *getInterleaveGroup() { return IG; }
723 };
724 
725 /// VPReplicateRecipe replicates a given instruction producing multiple scalar
726 /// copies of the original scalar type, one per lane, instead of producing a
727 /// single copy of widened type for all lanes. If the instruction is known to be
728 /// uniform only one copy, per lane zero, will be generated.
730 private:
731  /// The instruction being replicated.
732  Instruction *Ingredient;
733 
734  /// Indicator if only a single replica per lane is needed.
735  bool IsUniform;
736 
737  /// Indicator if the replicas are also predicated.
738  bool IsPredicated;
739 
740  /// Indicator if the scalar values should also be packed into a vector.
741  bool AlsoPack;
742 
743 public:
744  VPReplicateRecipe(Instruction *I, bool IsUniform, bool IsPredicated = false)
745  : VPRecipeBase(VPReplicateSC), Ingredient(I), IsUniform(IsUniform),
746  IsPredicated(IsPredicated) {
747  // Retain the previous behavior of predicateInstructions(), where an
748  // insert-element of a predicated instruction got hoisted into the
749  // predicated basic block iff it was its only user. This is achieved by
750  // having predicated instructions also pack their values into a vector by
751  // default unless they have a replicated user which uses their scalar value.
752  AlsoPack = IsPredicated && !I->use_empty();
753  }
754 
755  ~VPReplicateRecipe() override = default;
756 
757  /// Method to support type inquiry through isa, cast, and dyn_cast.
758  static inline bool classof(const VPRecipeBase *V) {
759  return V->getVPRecipeID() == VPRecipeBase::VPReplicateSC;
760  }
761 
762  /// Generate replicas of the desired Ingredient. Replicas will be generated
763  /// for all parts and lanes unless a specific part and lane are specified in
764  /// the \p State.
765  void execute(VPTransformState &State) override;
766 
767  void setAlsoPack(bool Pack) { AlsoPack = Pack; }
768 
769  /// Print the recipe.
770  void print(raw_ostream &O, const Twine &Indent) const override;
771 };
772 
773 /// A recipe for generating conditional branches on the bits of a mask.
775 private:
776  std::unique_ptr<VPUser> User;
777 
778 public:
779  VPBranchOnMaskRecipe(VPValue *BlockInMask) : VPRecipeBase(VPBranchOnMaskSC) {
780  if (BlockInMask) // nullptr means all-one mask.
781  User.reset(new VPUser({BlockInMask}));
782  }
783 
784  /// Method to support type inquiry through isa, cast, and dyn_cast.
785  static inline bool classof(const VPRecipeBase *V) {
786  return V->getVPRecipeID() == VPRecipeBase::VPBranchOnMaskSC;
787  }
788 
789  /// Generate the extraction of the appropriate bit from the block mask and the
790  /// conditional branch.
791  void execute(VPTransformState &State) override;
792 
793  /// Print the recipe.
794  void print(raw_ostream &O, const Twine &Indent) const override {
795  O << " +\n" << Indent << "\"BRANCH-ON-MASK ";
796  if (User)
797  O << *User->getOperand(0);
798  else
799  O << " All-One";
800  O << "\\l\"";
801  }
802 };
803 
804 /// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
805 /// control converges back from a Branch-on-Mask. The phi nodes are needed in
806 /// order to merge values that are set under such a branch and feed their uses.
807 /// The phi nodes can be scalar or vector depending on the users of the value.
808 /// This recipe works in concert with VPBranchOnMaskRecipe.
810 private:
811  Instruction *PredInst;
812 
813 public:
814  /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
815  /// nodes after merging back from a Branch-on-Mask.
817  : VPRecipeBase(VPPredInstPHISC), PredInst(PredInst) {}
818  ~VPPredInstPHIRecipe() override = default;
819 
820  /// Method to support type inquiry through isa, cast, and dyn_cast.
821  static inline bool classof(const VPRecipeBase *V) {
822  return V->getVPRecipeID() == VPRecipeBase::VPPredInstPHISC;
823  }
824 
825  /// Generates phi nodes for live-outs as needed to retain SSA form.
826  void execute(VPTransformState &State) override;
827 
828  /// Print the recipe.
829  void print(raw_ostream &O, const Twine &Indent) const override;
830 };
831 
832 /// A Recipe for widening load/store operations.
833 /// TODO: We currently execute only per-part unless a specific instance is
834 /// provided.
836 private:
837  Instruction &Instr;
838  std::unique_ptr<VPUser> User;
839 
840 public:
842  : VPRecipeBase(VPWidenMemoryInstructionSC), Instr(Instr) {
843  if (Mask) // Create a VPInstruction to register as a user of the mask.
844  User.reset(new VPUser({Mask}));
845  }
846 
847  /// Method to support type inquiry through isa, cast, and dyn_cast.
848  static inline bool classof(const VPRecipeBase *V) {
849  return V->getVPRecipeID() == VPRecipeBase::VPWidenMemoryInstructionSC;
850  }
851 
852  /// Generate the wide load/store.
853  void execute(VPTransformState &State) override;
854 
855  /// Print the recipe.
856  void print(raw_ostream &O, const Twine &Indent) const override;
857 };
858 
859 /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
860 /// holds a sequence of zero or more VPRecipe's each representing a sequence of
861 /// output IR instructions.
862 class VPBasicBlock : public VPBlockBase {
863 public:
865 
866 private:
867  /// The VPRecipes held in the order of output instructions to generate.
868  RecipeListTy Recipes;
869 
870 public:
871  VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr)
872  : VPBlockBase(VPBasicBlockSC, Name.str()) {
873  if (Recipe)
874  appendRecipe(Recipe);
875  }
876 
877  ~VPBasicBlock() override { Recipes.clear(); }
878 
879  /// Instruction iterators...
884 
885  //===--------------------------------------------------------------------===//
886  /// Recipe iterator methods
887  ///
888  inline iterator begin() { return Recipes.begin(); }
889  inline const_iterator begin() const { return Recipes.begin(); }
890  inline iterator end() { return Recipes.end(); }
891  inline const_iterator end() const { return Recipes.end(); }
892 
893  inline reverse_iterator rbegin() { return Recipes.rbegin(); }
894  inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); }
895  inline reverse_iterator rend() { return Recipes.rend(); }
896  inline const_reverse_iterator rend() const { return Recipes.rend(); }
897 
898  inline size_t size() const { return Recipes.size(); }
899  inline bool empty() const { return Recipes.empty(); }
900  inline const VPRecipeBase &front() const { return Recipes.front(); }
901  inline VPRecipeBase &front() { return Recipes.front(); }
902  inline const VPRecipeBase &back() const { return Recipes.back(); }
903  inline VPRecipeBase &back() { return Recipes.back(); }
904 
905  /// \brief Returns a pointer to a member of the recipe list.
907  return &VPBasicBlock::Recipes;
908  }
909 
910  /// Method to support type inquiry through isa, cast, and dyn_cast.
911  static inline bool classof(const VPBlockBase *V) {
912  return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC;
913  }
914 
915  void insert(VPRecipeBase *Recipe, iterator InsertPt) {
916  assert(Recipe && "No recipe to append.");
917  assert(!Recipe->Parent && "Recipe already in VPlan");
918  Recipe->Parent = this;
919  Recipes.insert(InsertPt, Recipe);
920  }
921 
922  /// Augment the existing recipes of a VPBasicBlock with an additional
923  /// \p Recipe as the last recipe.
924  void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); }
925 
926  /// The method which generates the output IR instructions that correspond to
927  /// this VPBasicBlock, thereby "executing" the VPlan.
928  void execute(struct VPTransformState *State) override;
929 
930 private:
931  /// Create an IR BasicBlock to hold the output instructions generated by this
932  /// VPBasicBlock, and return it. Update the CFGState accordingly.
933  BasicBlock *createEmptyBasicBlock(VPTransformState::CFGState &CFG);
934 };
935 
936 /// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks
937 /// which form a Single-Entry-Single-Exit subgraph of the output IR CFG.
938 /// A VPRegionBlock may indicate that its contents are to be replicated several
939 /// times. This is designed to support predicated scalarization, in which a
940 /// scalar if-then code structure needs to be generated VF * UF times. Having
941 /// this replication indicator helps to keep a single model for multiple
942 /// candidate VF's. The actual replication takes place only once the desired VF
943 /// and UF have been determined.
944 class VPRegionBlock : public VPBlockBase {
945 private:
946  /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock.
947  VPBlockBase *Entry;
948 
949  /// Hold the Single Exit of the SESE region modelled by the VPRegionBlock.
950  VPBlockBase *Exit;
951 
952  /// An indicator whether this region is to generate multiple replicated
953  /// instances of output IR corresponding to its VPBlockBases.
954  bool IsReplicator;
955 
956 public:
958  const std::string &Name = "", bool IsReplicator = false)
959  : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exit(Exit),
960  IsReplicator(IsReplicator) {
961  assert(Entry->getPredecessors().empty() && "Entry block has predecessors.");
962  assert(Exit->getSuccessors().empty() && "Exit block has successors.");
963  Entry->setParent(this);
964  Exit->setParent(this);
965  }
966 
967  ~VPRegionBlock() override {
968  if (Entry)
969  deleteCFG(Entry);
970  }
971 
972  /// Method to support type inquiry through isa, cast, and dyn_cast.
973  static inline bool classof(const VPBlockBase *V) {
974  return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC;
975  }
976 
977  const VPBlockBase *getEntry() const { return Entry; }
978  VPBlockBase *getEntry() { return Entry; }
979 
980  const VPBlockBase *getExit() const { return Exit; }
981  VPBlockBase *getExit() { return Exit; }
982 
983  /// An indicator whether this region is to generate multiple replicated
984  /// instances of output IR corresponding to its VPBlockBases.
985  bool isReplicator() const { return IsReplicator; }
986 
987  /// The method which generates the output IR instructions that correspond to
988  /// this VPRegionBlock, thereby "executing" the VPlan.
989  void execute(struct VPTransformState *State) override;
990 };
991 
992 /// VPlan models a candidate for vectorization, encoding various decisions take
993 /// to produce efficient output IR, including which branches, basic-blocks and
994 /// output IR instructions to generate, and their cost. VPlan holds a
995 /// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry
996 /// VPBlock.
997 class VPlan {
998  friend class VPlanPrinter;
999 
1000 private:
1001  /// Hold the single entry to the Hierarchical CFG of the VPlan.
1002  VPBlockBase *Entry;
1003 
1004  /// Holds the VFs applicable to this VPlan.
1006 
1007  /// Holds the name of the VPlan, for printing.
1008  std::string Name;
1009 
1010  /// Holds a mapping between Values and their corresponding VPValue inside
1011  /// VPlan.
1012  Value2VPValueTy Value2VPValue;
1013 
1014 public:
1015  VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {}
1016 
1018  if (Entry)
1019  VPBlockBase::deleteCFG(Entry);
1020  for (auto &MapEntry : Value2VPValue)
1021  delete MapEntry.second;
1022  }
1023 
1024  /// Generate the IR code for this VPlan.
1025  void execute(struct VPTransformState *State);
1026 
1027  VPBlockBase *getEntry() { return Entry; }
1028  const VPBlockBase *getEntry() const { return Entry; }
1029 
1030  VPBlockBase *setEntry(VPBlockBase *Block) { return Entry = Block; }
1031 
1032  void addVF(unsigned VF) { VFs.insert(VF); }
1033 
1034  bool hasVF(unsigned VF) { return VFs.count(VF); }
1035 
1036  const std::string &getName() const { return Name; }
1037 
1038  void setName(const Twine &newName) { Name = newName.str(); }
1039 
1040  void addVPValue(Value *V) {
1041  assert(V && "Trying to add a null Value to VPlan");
1042  assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
1043  Value2VPValue[V] = new VPValue();
1044  }
1045 
1047  assert(V && "Trying to get the VPValue of a null Value");
1048  assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
1049  return Value2VPValue[V];
1050  }
1051 
1052 private:
1053  /// Add to the given dominator tree the header block and every new basic block
1054  /// that was created between it and the latch block, inclusive.
1055  static void updateDominatorTree(DominatorTree *DT,
1056  BasicBlock *LoopPreHeaderBB,
1057  BasicBlock *LoopLatchBB);
1058 };
1059 
1060 /// VPlanPrinter prints a given VPlan to a given output stream. The printing is
1061 /// indented and follows the dot format.
1063  friend inline raw_ostream &operator<<(raw_ostream &OS, VPlan &Plan);
1064  friend inline raw_ostream &operator<<(raw_ostream &OS,
1065  const struct VPlanIngredient &I);
1066 
1067 private:
1068  raw_ostream &OS;
1069  VPlan &Plan;
1070  unsigned Depth;
1071  unsigned TabWidth = 2;
1072  std::string Indent;
1073  unsigned BID = 0;
1075 
1076  VPlanPrinter(raw_ostream &O, VPlan &P) : OS(O), Plan(P) {}
1077 
1078  /// Handle indentation.
1079  void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); }
1080 
1081  /// Print a given \p Block of the Plan.
1082  void dumpBlock(const VPBlockBase *Block);
1083 
1084  /// Print the information related to the CFG edges going out of a given
1085  /// \p Block, followed by printing the successor blocks themselves.
1086  void dumpEdges(const VPBlockBase *Block);
1087 
1088  /// Print a given \p BasicBlock, including its VPRecipes, followed by printing
1089  /// its successor blocks.
1090  void dumpBasicBlock(const VPBasicBlock *BasicBlock);
1091 
1092  /// Print a given \p Region of the Plan.
1093  void dumpRegion(const VPRegionBlock *Region);
1094 
1095  unsigned getOrCreateBID(const VPBlockBase *Block) {
1096  return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++;
1097  }
1098 
1099  const Twine getOrCreateName(const VPBlockBase *Block);
1100 
1101  const Twine getUID(const VPBlockBase *Block);
1102 
1103  /// Print the information related to a CFG edge between two VPBlockBases.
1104  void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden,
1105  const Twine &Label);
1106 
1107  void dump();
1108 
1109  static void printAsIngredient(raw_ostream &O, Value *V);
1110 };
1111 
1114 
1115  VPlanIngredient(Value *V) : V(V) {}
1116 };
1117 
1119  VPlanPrinter::printAsIngredient(OS, I.V);
1120  return OS;
1121 }
1122 
1124  VPlanPrinter Printer(OS, Plan);
1125  Printer.dump();
1126  return OS;
1127 }
1128 
1129 //===--------------------------------------------------------------------===//
1130 // GraphTraits specializations for VPlan/VPRegionBlock Control-Flow Graphs //
1131 //===--------------------------------------------------------------------===//
1132 
1133 // Provide specializations of GraphTraits to be able to treat a VPBlockBase as a
1134 // graph of VPBlockBase nodes...
1135 
1136 template <> struct GraphTraits<VPBlockBase *> {
1139 
1140  static NodeRef getEntryNode(NodeRef N) { return N; }
1141 
1143  return N->getSuccessors().begin();
1144  }
1145 
1147  return N->getSuccessors().end();
1148  }
1149 };
1150 
1151 template <> struct GraphTraits<const VPBlockBase *> {
1152  using NodeRef = const VPBlockBase *;
1154 
1155  static NodeRef getEntryNode(NodeRef N) { return N; }
1156 
1158  return N->getSuccessors().begin();
1159  }
1160 
1162  return N->getSuccessors().end();
1163  }
1164 };
1165 
1166 // Provide specializations of GraphTraits to be able to treat a VPBlockBase as a
1167 // graph of VPBlockBase nodes... and to walk it in inverse order. Inverse order
1168 // for a VPBlockBase is considered to be when traversing the predecessors of a
1169 // VPBlockBase instead of its successors.
1170 template <> struct GraphTraits<Inverse<VPBlockBase *>> {
1173 
1175  return B;
1176  }
1177 
1179  return N->getPredecessors().begin();
1180  }
1181 
1183  return N->getPredecessors().end();
1184  }
1185 };
1186 
1187 } // end namespace llvm
1188 
1189 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
const std::string & getName() const
Definition: VPlan.h:366
LoopInfo * LI
Hold a pointer to LoopInfo to register new basic blocks in the loop.
Definition: VPlan.h:284
VPWidenRecipe(Instruction *I)
Definition: VPlan.h:596
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:245
const VPRegionBlock * getParent() const
Definition: VPlan.h:375
bool appendInstruction(Instruction *Instr)
Augment the recipe to include Instr, if it lies at its End.
Definition: VPlan.h:612
void setAlsoPack(bool Pack)
Definition: VPlan.h:767
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:604
enum { VPBasicBlockSC, VPRegionBlockSC } VPBlockTy
An enumeration for keeping track of the concrete subclass of VPBlockBase that are actually instantiat...
Definition: VPlan.h:360
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:329
VectorizerValueMap(unsigned UF, unsigned VF)
Construct an empty map with the given unroll and vectorization factors.
Definition: VPlan.h:110
~VPBasicBlock() override
Definition: VPlan.h:877
SmallVectorImpl< VPBlockBase * >::const_iterator ChildIteratorType
Definition: VPlan.h:1153
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 ...
Various leaf nodes.
Definition: ISDOpcodes.h:60
VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exit, const std::string &Name="", bool IsReplicator=false)
Definition: VPlan.h:957
const_reverse_iterator rbegin() const
Definition: VPlan.h:894
Optional< VPIteration > Instance
Hold the indices to generate specific scalar instructions.
Definition: VPlan.h:229
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:997
DenseMap< VPValue *, PerPartValuesTy > PerPartOutput
Definition: VPlan.h:237
Value * getScalarValue(Value *Key, const VPIteration &Instance)
Retrieve the existing scalar value that corresponds to Key and Instance.
Definition: VPlan.h:154
VPlanIngredient(Value *V)
Definition: VPlan.h:1115
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:944
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:517
IRBuilder & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Definition: VPlan.h:290
VPRecipeBase & back()
Definition: VPlan.h:903
This is a helper struct for maintaining vectorization state.
Definition: VPlan.h:90
A Recipe for widening load/store operations.
Definition: VPlan.h:835
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.h:794
bool hasAnyScalarValue(Value *Key) const
Definition: VPlan.h:128
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:399
void addVPValue(Value *V)
Definition: VPlan.h:1040
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:636
VPRecipeBase & front()
Definition: VPlan.h:901
VPBlockBase * setOneSuccessor(VPBlockBase *Successor)
Sets a given VPBlockBase Successor as the single successor and.
Definition: VPlan.h:455
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:492
unsigned getVPRecipeID() const
Definition: VPlan.h:525
VPValue * getVPValue(Value *V)
Definition: VPlan.h:1046
bool hasAnyVectorValue(Value *Key) const
Definition: VPlan.h:113
reverse_iterator rend()
Definition: VPlan.h:895
static bool classof(const VPRecipeBase *R)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:567
unsigned VF
The chosen Vectorization and Unroll Factors of the loop being vectorized.
Definition: VPlan.h:223
VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when control converges back from ...
Definition: VPlan.h:809
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:426
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
virtual ~VPCallback()
Definition: VPlan.h:209
VPBlockBase * getEntry()
Definition: VPlan.h:978
size_t size() const
Definition: VPlan.h:898
bool hasVectorValue(Value *Key, unsigned Part) const
Definition: VPlan.h:118
VPBlocksTy & getSuccessors()
Definition: VPlan.h:392
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:707
VectorizerValueMap & ValueMap
Hold a reference to the Value state information used when generating the Values of the output IR...
Definition: VPlan.h:294
A recipe for handling all phi nodes except for integer and FP inductions.
Definition: VPlan.h:649
~VPRegionBlock() override
Definition: VPlan.h:967
void setName(const Twine &newName)
Definition: VPlan.h:368
DominatorTree * DT
Hold a pointer to Dominator Tree to register new basic blocks in the loop.
Definition: VPlan.h:287
void insert(VPRecipeBase *Recipe, iterator InsertPt)
Definition: VPlan.h:915
const std::string & getName() const
Definition: VPlan.h:1036
VPBlocksTy & getPredecessors()
Definition: VPlan.h:395
static RecipeListTy VPBasicBlock::* getSublistAccess(VPRecipeBase *)
Returns a pointer to a member of the recipe list.
Definition: VPlan.h:906
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:1182
void setName(const Twine &newName)
Definition: VPlan.h:1038
VPWidenPHIRecipe(PHINode *Phi)
Definition: VPlan.h:654
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:1157
Key
PAL metadata keys.
VPBlockBase * getSinglePredecessor() const
Definition: VPlan.h:405
VPlanPrinter prints a given VPlan to a given output stream.
Definition: VPlan.h:1062
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:1161
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:985
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:658
This class is used to enable the VPlan to invoke a method of ILV.
Definition: VPlan.h:208
The group of interleaved loads/stores sharing the same stride and close to each other.
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:980
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:215
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:432
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:448
unsigned getVPBlockID() const
Definition: VPlan.h:373
static bool classof(const VPValue *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:562
unsigned getVPValueID() const
Definition: VPlanValue.h:62
VPInstruction(unsigned Opcode, std::initializer_list< VPValue *> Operands)
Definition: VPlan.h:557
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
This class represents a truncation of integer types.
iterator begin()
Recipe iterator methods.
Definition: VPlan.h:888
void resetScalarValue(Value *Key, const VPIteration &Instance, Value *Scalar)
Reset the scalar value associated with Key for Part and Lane.
Definition: VPlan.h:198
SmallVectorImpl< VPBlockBase * >::iterator ChildIteratorType
Definition: VPlan.h:1138
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe...
Definition: VPlan.h:924
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:442
#define P(N)
This class augments VPValue with operands which provide the inverse def-use edges from VPValue&#39;s user...
Definition: VPlanValue.h:93
An ilist node that can access its parent list.
Definition: ilist_node.h:257
const InterleaveGroup * getInterleaveGroup()
Definition: VPlan.h:722
VPWidenMemoryInstructionRecipe(Instruction &Instr, VPValue *Mask)
Definition: VPlan.h:841
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:848
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:1178
VPBlendRecipe(PHINode *Phi, ArrayRef< VPValue *> Masks)
Definition: VPlan.h:679
reverse_iterator rbegin()
Definition: VPlan.h:893
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
SmallVector< Value *, 2 > PerPartValuesTy
A type for vectorized values in the new loop.
Definition: VPlan.h:235
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
bool hasScalarValue(Value *Key, const VPIteration &Instance) const
Definition: VPlan.h:133
VPWidenIntOrFpInductionRecipe(PHINode *IV, TruncInst *Trunc=nullptr)
Definition: VPlan.h:631
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
SmallDenseMap< VPBasicBlock *, BasicBlock * > VPBB2IRBB
A mapping of each VPBasicBlock to the corresponding BasicBlock.
Definition: VPlan.h:278
static NodeRef getEntryNode(NodeRef N)
Definition: VPlan.h:1140
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:1146
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:264
static const unsigned End
VPCallback & Callback
Definition: VPlan.h:303
VPBlockBase * setEntry(VPBlockBase *Block)
Definition: VPlan.h:1030
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
bool hasVF(unsigned VF)
Definition: VPlan.h:1034
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:298
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:81
static bool classof(const VPBlockBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:911
SmallVectorImpl< VPBlockBase * >::iterator ChildIteratorType
Definition: VPlan.h:1172
iterator erase(const_iterator CI)
Definition: SmallVector.h:447
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:835
void setScalarValue(Value *Key, const VPIteration &Instance, Value *Scalar)
Set a scalar value associated with Key and Instance.
Definition: VPlan.h:172
static void deleteCFG(VPBlockBase *Entry)
Delete all blocks reachable from a given VPBlockBase, inclusive.
Definition: VPlan.cpp:103
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:862
VPBlockBase(const unsigned char SC, const std::string &N)
Definition: VPlan.h:352
const_iterator begin() const
Definition: VPlan.h:889
unsigned Lane
in [0..VF)
Definition: VPlan.h:70
void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse)
Sets two given VPBlockBases IfTrue and IfFalse to be the two successors.
Definition: VPlan.h:466
const VPRecipeBase & back() const
Definition: VPlan.h:902
Iterator for intrusive lists based on ilist_node.
See the file comment.
Definition: ValueMap.h:86
const VPRecipeBase & front() const
Definition: VPlan.h:900
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:308
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
VPReplicateRecipe(Instruction *I, bool IsUniform, bool IsPredicated=false)
Definition: VPlan.h:744
static NodeRef getEntryNode(NodeRef N)
Definition: VPlan.h:1155
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:973
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:391
unsigned getNumIncomingValues() const
Return the number of incoming edges.
const VPBlockBase * getEntry() const
Definition: VPlan.h:977
void addVF(unsigned VF)
Definition: VPlan.h:1032
VPInterleaveRecipe is a recipe for transforming an interleave group of load or stores into one wide l...
Definition: VPlan.h:702
static Inverse< VPBlockBase * > getEntryNode(Inverse< VPBlockBase *> B)
Definition: VPlan.h:1174
void resetVectorValue(Value *Key, unsigned Part, Value *Vector)
Reset the vector value associated with Key for the given Part.
Definition: VPlan.h:189
VPBlockBase * getExit()
Definition: VPlan.h:981
typename SuperClass::iterator iterator
Definition: SmallVector.h:328
InnerLoopVectorizer * ILV
Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
Definition: VPlan.h:301
const VPBasicBlock * getParent() const
Definition: VPlan.h:529
bool empty() const
Definition: VPlan.h:899
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
VPInterleaveRecipe(const InterleaveGroup *IG)
Definition: VPlan.h:707
iterator insert(iterator where, pointer New)
Definition: ilist.h:241
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:394
Flatten the CFG
Value * getVectorValue(Value *Key, unsigned Part)
Retrieve the existing vector value that corresponds to Key and Part.
Definition: VPlan.h:147
void clear()
Definition: ilist.h:322
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition: VPlan.h:729
VPBlockBase * getEntry()
Definition: VPlan.h:1027
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:785
VPTransformState(unsigned VF, unsigned UF, LoopInfo *LI, DominatorTree *DT, IRBuilder<> &Builder, VectorizerValueMap &ValueMap, InnerLoopVectorizer *ILV, VPCallback &Callback)
Definition: VPlan.h:216
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:821
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
VPRecipeBase(const unsigned char SC)
Definition: VPlan.h:519
VPPredInstPHIRecipe(Instruction *PredInst)
Construct a VPPredInstPHIRecipe given PredInst whose value needs a phi nodes after merging back from ...
Definition: VPlan.h:816
const VPBlockBase * getEntry() const
Definition: VPlan.h:1028
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:758
VPlan(VPBlockBase *Entry=nullptr)
Definition: VPlan.h:1015
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector and ...
Definition: VPlan.h:625
unsigned getOpcode() const
Definition: VPlan.h:571
const_iterator end() const
Definition: VPlan.h:891
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
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:141
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
void setVectorValue(Value *Key, unsigned Part, Value *Vector)
Set a vector value associated with Key and Part.
Definition: VPlan.h:161
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:689
void disconnectSuccessor(VPBlockBase *Successor)
Definition: VPlan.h:476
iterator end()
Definition: VPlan.h:890
VPBasicBlock * getParent()
Definition: VPlan.h:528
VPWidenRecipe is a recipe for producing a copy of vector type for each Instruction in its ingredients...
Definition: VPlan.h:589
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:774
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:1142
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
A recipe for vectorizing a phi-node as a sequence of mask-based select instructions.
Definition: VPlan.h:671
In what follows, the term "input IR" refers to code that is fed into the vectorizer whereas the term ...
Definition: VPlan.h:65
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:712
unsigned Part
in [0..UF)
Definition: VPlan.h:67
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:543
VPBranchOnMaskRecipe(VPValue *BlockInMask)
Definition: VPlan.h:779
bool use_empty() const
Definition: Value.h:328
const_reverse_iterator rend() const
Definition: VPlan.h:896
VPBasicBlock(const Twine &Name="", VPRecipeBase *Recipe=nullptr)
Definition: VPlan.h:871
void setParent(VPRegionBlock *P)
Definition: VPlan.h:377
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:144
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:65