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  friend class VPBlockUtils;
310 
311 private:
312  const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
313 
314  /// An optional name for the block.
315  std::string Name;
316 
317  /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if
318  /// it is a topmost VPBlockBase.
319  VPRegionBlock *Parent = nullptr;
320 
321  /// List of predecessor blocks.
322  SmallVector<VPBlockBase *, 1> Predecessors;
323 
324  /// List of successor blocks.
326 
327  /// Add \p Successor as the last successor to this block.
328  void appendSuccessor(VPBlockBase *Successor) {
329  assert(Successor && "Cannot add nullptr successor!");
330  Successors.push_back(Successor);
331  }
332 
333  /// Add \p Predecessor as the last predecessor to this block.
334  void appendPredecessor(VPBlockBase *Predecessor) {
335  assert(Predecessor && "Cannot add nullptr predecessor!");
336  Predecessors.push_back(Predecessor);
337  }
338 
339  /// Remove \p Predecessor from the predecessors of this block.
340  void removePredecessor(VPBlockBase *Predecessor) {
341  auto Pos = std::find(Predecessors.begin(), Predecessors.end(), Predecessor);
342  assert(Pos && "Predecessor does not exist");
343  Predecessors.erase(Pos);
344  }
345 
346  /// Remove \p Successor from the successors of this block.
347  void removeSuccessor(VPBlockBase *Successor) {
348  auto Pos = std::find(Successors.begin(), Successors.end(), Successor);
349  assert(Pos && "Successor does not exist");
350  Successors.erase(Pos);
351  }
352 
353 protected:
354  VPBlockBase(const unsigned char SC, const std::string &N)
355  : SubclassID(SC), Name(N) {}
356 
357 public:
358  /// An enumeration for keeping track of the concrete subclass of VPBlockBase
359  /// that are actually instantiated. Values of this enumeration are kept in the
360  /// SubclassID field of the VPBlockBase objects. They are used for concrete
361  /// type identification.
362  using VPBlockTy = enum { VPBasicBlockSC, VPRegionBlockSC };
363 
365 
366  virtual ~VPBlockBase() = default;
367 
368  const std::string &getName() const { return Name; }
369 
370  void setName(const Twine &newName) { Name = newName.str(); }
371 
372  /// \return an ID for the concrete type of this object.
373  /// This is used to implement the classof checks. This should not be used
374  /// for any other purpose, as the values may change as LLVM evolves.
375  unsigned getVPBlockID() const { return SubclassID; }
376 
377  VPRegionBlock *getParent() { return Parent; }
378  const VPRegionBlock *getParent() const { return Parent; }
379 
380  void setParent(VPRegionBlock *P) { Parent = P; }
381 
382  /// \return the VPBasicBlock that is the entry of this VPBlockBase,
383  /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
384  /// VPBlockBase is a VPBasicBlock, it is returned.
385  const VPBasicBlock *getEntryBasicBlock() const;
386  VPBasicBlock *getEntryBasicBlock();
387 
388  /// \return the VPBasicBlock that is the exit of this VPBlockBase,
389  /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
390  /// VPBlockBase is a VPBasicBlock, it is returned.
391  const VPBasicBlock *getExitBasicBlock() const;
392  VPBasicBlock *getExitBasicBlock();
393 
394  const VPBlocksTy &getSuccessors() const { return Successors; }
395  VPBlocksTy &getSuccessors() { return Successors; }
396 
397  const VPBlocksTy &getPredecessors() const { return Predecessors; }
398  VPBlocksTy &getPredecessors() { return Predecessors; }
399 
400  /// \return the successor of this VPBlockBase if it has a single successor.
401  /// Otherwise return a null pointer.
403  return (Successors.size() == 1 ? *Successors.begin() : nullptr);
404  }
405 
406  /// \return the predecessor of this VPBlockBase if it has a single
407  /// predecessor. Otherwise return a null pointer.
409  return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr);
410  }
411 
412  size_t getNumSuccessors() const { return Successors.size(); }
413  size_t getNumPredecessors() const { return Predecessors.size(); }
414 
415  /// An Enclosing Block of a block B is any block containing B, including B
416  /// itself. \return the closest enclosing block starting from "this", which
417  /// has successors. \return the root enclosing block if all enclosing blocks
418  /// have no successors.
419  VPBlockBase *getEnclosingBlockWithSuccessors();
420 
421  /// \return the closest enclosing block starting from "this", which has
422  /// predecessors. \return the root enclosing block if all enclosing blocks
423  /// have no predecessors.
424  VPBlockBase *getEnclosingBlockWithPredecessors();
425 
426  /// \return the successors either attached directly to this VPBlockBase or, if
427  /// this VPBlockBase is the exit block of a VPRegionBlock and has no
428  /// successors of its own, search recursively for the first enclosing
429  /// VPRegionBlock that has successors and return them. If no such
430  /// VPRegionBlock exists, return the (empty) successors of the topmost
431  /// VPBlockBase reached.
433  return getEnclosingBlockWithSuccessors()->getSuccessors();
434  }
435 
436  /// \return the hierarchical successor of this VPBlockBase if it has a single
437  /// hierarchical successor. Otherwise return a null pointer.
439  return getEnclosingBlockWithSuccessors()->getSingleSuccessor();
440  }
441 
442  /// \return the predecessors either attached directly to this VPBlockBase or,
443  /// if this VPBlockBase is the entry block of a VPRegionBlock and has no
444  /// predecessors of its own, search recursively for the first enclosing
445  /// VPRegionBlock that has predecessors and return them. If no such
446  /// VPRegionBlock exists, return the (empty) predecessors of the topmost
447  /// VPBlockBase reached.
449  return getEnclosingBlockWithPredecessors()->getPredecessors();
450  }
451 
452  /// \return the hierarchical predecessor of this VPBlockBase if it has a
453  /// single hierarchical predecessor. Otherwise return a null pointer.
455  return getEnclosingBlockWithPredecessors()->getSinglePredecessor();
456  }
457 
458  /// Set a given VPBlockBase \p Successor as the single successor of this
459  /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor.
460  /// This VPBlockBase must have no successors.
461  void setOneSuccessor(VPBlockBase *Successor) {
462  assert(Successors.empty() && "Setting one successor when others exist.");
463  appendSuccessor(Successor);
464  }
465 
466  /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two
467  /// successors of this VPBlockBase. This VPBlockBase is not added as
468  /// predecessor of \p IfTrue or \p IfFalse. This VPBlockBase must have no
469  /// successors.
470  void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse) {
471  assert(Successors.empty() && "Setting two successors when others exist.");
472  appendSuccessor(IfTrue);
473  appendSuccessor(IfFalse);
474  }
475 
476  /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase.
477  /// This VPBlockBase must have no predecessors. This VPBlockBase is not added
478  /// as successor of any VPBasicBlock in \p NewPreds.
480  assert(Predecessors.empty() && "Block predecessors already set.");
481  for (auto *Pred : NewPreds)
482  appendPredecessor(Pred);
483  }
484 
485  /// The method which generates the output IR that correspond to this
486  /// VPBlockBase, thereby "executing" the VPlan.
487  virtual void execute(struct VPTransformState *State) = 0;
488 
489  /// Delete all blocks reachable from a given VPBlockBase, inclusive.
490  static void deleteCFG(VPBlockBase *Entry);
491 };
492 
493 /// VPRecipeBase is a base class modeling a sequence of one or more output IR
494 /// instructions.
495 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> {
496  friend VPBasicBlock;
497 
498 private:
499  const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
500 
501  /// Each VPRecipe belongs to a single VPBasicBlock.
502  VPBasicBlock *Parent = nullptr;
503 
504 public:
505  /// An enumeration for keeping track of the concrete subclass of VPRecipeBase
506  /// that is actually instantiated. Values of this enumeration are kept in the
507  /// SubclassID field of the VPRecipeBase objects. They are used for concrete
508  /// type identification.
509  using VPRecipeTy = enum {
510  VPBlendSC,
511  VPBranchOnMaskSC,
512  VPInstructionSC,
513  VPInterleaveSC,
514  VPPredInstPHISC,
515  VPReplicateSC,
516  VPWidenIntOrFpInductionSC,
517  VPWidenMemoryInstructionSC,
518  VPWidenPHISC,
519  VPWidenSC,
520  };
521 
522  VPRecipeBase(const unsigned char SC) : SubclassID(SC) {}
523  virtual ~VPRecipeBase() = default;
524 
525  /// \return an ID for the concrete type of this object.
526  /// This is used to implement the classof checks. This should not be used
527  /// for any other purpose, as the values may change as LLVM evolves.
528  unsigned getVPRecipeID() const { return SubclassID; }
529 
530  /// \return the VPBasicBlock which this VPRecipe belongs to.
531  VPBasicBlock *getParent() { return Parent; }
532  const VPBasicBlock *getParent() const { return Parent; }
533 
534  /// The method which generates the output IR instructions that correspond to
535  /// this VPRecipe, thereby "executing" the VPlan.
536  virtual void execute(struct VPTransformState &State) = 0;
537 
538  /// Each recipe prints itself.
539  virtual void print(raw_ostream &O, const Twine &Indent) const = 0;
540 };
541 
542 /// This is a concrete Recipe that models a single VPlan-level instruction.
543 /// While as any Recipe it may generate a sequence of IR instructions when
544 /// executed, these instructions would always form a single-def expression as
545 /// the VPInstruction is also a single def-use vertex.
546 class VPInstruction : public VPUser, public VPRecipeBase {
547 public:
548  /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
549  enum { Not = Instruction::OtherOpsEnd + 1 };
550 
551 private:
552  typedef unsigned char OpcodeTy;
553  OpcodeTy Opcode;
554 
555  /// Utility method serving execute(): generates a single instance of the
556  /// modeled instruction.
557  void generateInstruction(VPTransformState &State, unsigned Part);
558 
559 public:
560  VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands)
561  : VPUser(VPValue::VPInstructionSC, Operands),
562  VPRecipeBase(VPRecipeBase::VPInstructionSC), Opcode(Opcode) {}
563 
564  VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands)
565  : VPInstruction(Opcode, ArrayRef<VPValue *>(Operands)) {}
566 
567  /// Method to support type inquiry through isa, cast, and dyn_cast.
568  static inline bool classof(const VPValue *V) {
569  return V->getVPValueID() == VPValue::VPInstructionSC;
570  }
571 
572  /// Method to support type inquiry through isa, cast, and dyn_cast.
573  static inline bool classof(const VPRecipeBase *R) {
574  return R->getVPRecipeID() == VPRecipeBase::VPInstructionSC;
575  }
576 
577  unsigned getOpcode() const { return Opcode; }
578 
579  /// Generate the instruction.
580  /// TODO: We currently execute only per-part unless a specific instance is
581  /// provided.
582  void execute(VPTransformState &State) override;
583 
584  /// Print the Recipe.
585  void print(raw_ostream &O, const Twine &Indent) const override;
586 
587  /// Print the VPInstruction.
588  void print(raw_ostream &O) const;
589 };
590 
591 /// VPWidenRecipe is a recipe for producing a copy of vector type for each
592 /// Instruction in its ingredients independently, in order. This recipe covers
593 /// most of the traditional vectorization cases where each ingredient transforms
594 /// into a vectorized version of itself.
595 class VPWidenRecipe : public VPRecipeBase {
596 private:
597  /// Hold the ingredients by pointing to their original BasicBlock location.
598  BasicBlock::iterator Begin;
600 
601 public:
603  End = I->getIterator();
604  Begin = End++;
605  }
606 
607  ~VPWidenRecipe() override = default;
608 
609  /// Method to support type inquiry through isa, cast, and dyn_cast.
610  static inline bool classof(const VPRecipeBase *V) {
611  return V->getVPRecipeID() == VPRecipeBase::VPWidenSC;
612  }
613 
614  /// Produce widened copies of all Ingredients.
615  void execute(VPTransformState &State) override;
616 
617  /// Augment the recipe to include Instr, if it lies at its End.
619  if (End != Instr->getIterator())
620  return false;
621  End++;
622  return true;
623  }
624 
625  /// Print the recipe.
626  void print(raw_ostream &O, const Twine &Indent) const override;
627 };
628 
629 /// A recipe for handling phi nodes of integer and floating-point inductions,
630 /// producing their vector and scalar values.
632 private:
633  PHINode *IV;
634  TruncInst *Trunc;
635 
636 public:
638  : VPRecipeBase(VPWidenIntOrFpInductionSC), IV(IV), Trunc(Trunc) {}
639  ~VPWidenIntOrFpInductionRecipe() override = default;
640 
641  /// Method to support type inquiry through isa, cast, and dyn_cast.
642  static inline bool classof(const VPRecipeBase *V) {
643  return V->getVPRecipeID() == VPRecipeBase::VPWidenIntOrFpInductionSC;
644  }
645 
646  /// Generate the vectorized and scalarized versions of the phi node as
647  /// needed by their users.
648  void execute(VPTransformState &State) override;
649 
650  /// Print the recipe.
651  void print(raw_ostream &O, const Twine &Indent) const override;
652 };
653 
654 /// A recipe for handling all phi nodes except for integer and FP inductions.
656 private:
657  PHINode *Phi;
658 
659 public:
660  VPWidenPHIRecipe(PHINode *Phi) : VPRecipeBase(VPWidenPHISC), Phi(Phi) {}
661  ~VPWidenPHIRecipe() override = default;
662 
663  /// Method to support type inquiry through isa, cast, and dyn_cast.
664  static inline bool classof(const VPRecipeBase *V) {
665  return V->getVPRecipeID() == VPRecipeBase::VPWidenPHISC;
666  }
667 
668  /// Generate the phi/select nodes.
669  void execute(VPTransformState &State) override;
670 
671  /// Print the recipe.
672  void print(raw_ostream &O, const Twine &Indent) const override;
673 };
674 
675 /// A recipe for vectorizing a phi-node as a sequence of mask-based select
676 /// instructions.
677 class VPBlendRecipe : public VPRecipeBase {
678 private:
679  PHINode *Phi;
680 
681  /// The blend operation is a User of a mask, if not null.
682  std::unique_ptr<VPUser> User;
683 
684 public:
686  : VPRecipeBase(VPBlendSC), Phi(Phi) {
687  assert((Phi->getNumIncomingValues() == 1 ||
688  Phi->getNumIncomingValues() == Masks.size()) &&
689  "Expected the same number of incoming values and masks");
690  if (!Masks.empty())
691  User.reset(new VPUser(Masks));
692  }
693 
694  /// Method to support type inquiry through isa, cast, and dyn_cast.
695  static inline bool classof(const VPRecipeBase *V) {
696  return V->getVPRecipeID() == VPRecipeBase::VPBlendSC;
697  }
698 
699  /// Generate the phi/select nodes.
700  void execute(VPTransformState &State) override;
701 
702  /// Print the recipe.
703  void print(raw_ostream &O, const Twine &Indent) const override;
704 };
705 
706 /// VPInterleaveRecipe is a recipe for transforming an interleave group of load
707 /// or stores into one wide load/store and shuffles.
709 private:
710  const InterleaveGroup *IG;
711 
712 public:
714  : VPRecipeBase(VPInterleaveSC), IG(IG) {}
715  ~VPInterleaveRecipe() override = default;
716 
717  /// Method to support type inquiry through isa, cast, and dyn_cast.
718  static inline bool classof(const VPRecipeBase *V) {
719  return V->getVPRecipeID() == VPRecipeBase::VPInterleaveSC;
720  }
721 
722  /// Generate the wide load or store, and shuffles.
723  void execute(VPTransformState &State) override;
724 
725  /// Print the recipe.
726  void print(raw_ostream &O, const Twine &Indent) const override;
727 
728  const InterleaveGroup *getInterleaveGroup() { return IG; }
729 };
730 
731 /// VPReplicateRecipe replicates a given instruction producing multiple scalar
732 /// copies of the original scalar type, one per lane, instead of producing a
733 /// single copy of widened type for all lanes. If the instruction is known to be
734 /// uniform only one copy, per lane zero, will be generated.
736 private:
737  /// The instruction being replicated.
738  Instruction *Ingredient;
739 
740  /// Indicator if only a single replica per lane is needed.
741  bool IsUniform;
742 
743  /// Indicator if the replicas are also predicated.
744  bool IsPredicated;
745 
746  /// Indicator if the scalar values should also be packed into a vector.
747  bool AlsoPack;
748 
749 public:
750  VPReplicateRecipe(Instruction *I, bool IsUniform, bool IsPredicated = false)
751  : VPRecipeBase(VPReplicateSC), Ingredient(I), IsUniform(IsUniform),
752  IsPredicated(IsPredicated) {
753  // Retain the previous behavior of predicateInstructions(), where an
754  // insert-element of a predicated instruction got hoisted into the
755  // predicated basic block iff it was its only user. This is achieved by
756  // having predicated instructions also pack their values into a vector by
757  // default unless they have a replicated user which uses their scalar value.
758  AlsoPack = IsPredicated && !I->use_empty();
759  }
760 
761  ~VPReplicateRecipe() override = default;
762 
763  /// Method to support type inquiry through isa, cast, and dyn_cast.
764  static inline bool classof(const VPRecipeBase *V) {
765  return V->getVPRecipeID() == VPRecipeBase::VPReplicateSC;
766  }
767 
768  /// Generate replicas of the desired Ingredient. Replicas will be generated
769  /// for all parts and lanes unless a specific part and lane are specified in
770  /// the \p State.
771  void execute(VPTransformState &State) override;
772 
773  void setAlsoPack(bool Pack) { AlsoPack = Pack; }
774 
775  /// Print the recipe.
776  void print(raw_ostream &O, const Twine &Indent) const override;
777 };
778 
779 /// A recipe for generating conditional branches on the bits of a mask.
781 private:
782  std::unique_ptr<VPUser> User;
783 
784 public:
785  VPBranchOnMaskRecipe(VPValue *BlockInMask) : VPRecipeBase(VPBranchOnMaskSC) {
786  if (BlockInMask) // nullptr means all-one mask.
787  User.reset(new VPUser({BlockInMask}));
788  }
789 
790  /// Method to support type inquiry through isa, cast, and dyn_cast.
791  static inline bool classof(const VPRecipeBase *V) {
792  return V->getVPRecipeID() == VPRecipeBase::VPBranchOnMaskSC;
793  }
794 
795  /// Generate the extraction of the appropriate bit from the block mask and the
796  /// conditional branch.
797  void execute(VPTransformState &State) override;
798 
799  /// Print the recipe.
800  void print(raw_ostream &O, const Twine &Indent) const override {
801  O << " +\n" << Indent << "\"BRANCH-ON-MASK ";
802  if (User)
803  O << *User->getOperand(0);
804  else
805  O << " All-One";
806  O << "\\l\"";
807  }
808 };
809 
810 /// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
811 /// control converges back from a Branch-on-Mask. The phi nodes are needed in
812 /// order to merge values that are set under such a branch and feed their uses.
813 /// The phi nodes can be scalar or vector depending on the users of the value.
814 /// This recipe works in concert with VPBranchOnMaskRecipe.
816 private:
817  Instruction *PredInst;
818 
819 public:
820  /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
821  /// nodes after merging back from a Branch-on-Mask.
823  : VPRecipeBase(VPPredInstPHISC), PredInst(PredInst) {}
824  ~VPPredInstPHIRecipe() override = default;
825 
826  /// Method to support type inquiry through isa, cast, and dyn_cast.
827  static inline bool classof(const VPRecipeBase *V) {
828  return V->getVPRecipeID() == VPRecipeBase::VPPredInstPHISC;
829  }
830 
831  /// Generates phi nodes for live-outs as needed to retain SSA form.
832  void execute(VPTransformState &State) override;
833 
834  /// Print the recipe.
835  void print(raw_ostream &O, const Twine &Indent) const override;
836 };
837 
838 /// A Recipe for widening load/store operations.
839 /// TODO: We currently execute only per-part unless a specific instance is
840 /// provided.
842 private:
843  Instruction &Instr;
844  std::unique_ptr<VPUser> User;
845 
846 public:
848  : VPRecipeBase(VPWidenMemoryInstructionSC), Instr(Instr) {
849  if (Mask) // Create a VPInstruction to register as a user of the mask.
850  User.reset(new VPUser({Mask}));
851  }
852 
853  /// Method to support type inquiry through isa, cast, and dyn_cast.
854  static inline bool classof(const VPRecipeBase *V) {
855  return V->getVPRecipeID() == VPRecipeBase::VPWidenMemoryInstructionSC;
856  }
857 
858  /// Generate the wide load/store.
859  void execute(VPTransformState &State) override;
860 
861  /// Print the recipe.
862  void print(raw_ostream &O, const Twine &Indent) const override;
863 };
864 
865 /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
866 /// holds a sequence of zero or more VPRecipe's each representing a sequence of
867 /// output IR instructions.
868 class VPBasicBlock : public VPBlockBase {
869 public:
871 
872 private:
873  /// The VPRecipes held in the order of output instructions to generate.
874  RecipeListTy Recipes;
875 
876 public:
877  VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr)
878  : VPBlockBase(VPBasicBlockSC, Name.str()) {
879  if (Recipe)
880  appendRecipe(Recipe);
881  }
882 
883  ~VPBasicBlock() override { Recipes.clear(); }
884 
885  /// Instruction iterators...
890 
891  //===--------------------------------------------------------------------===//
892  /// Recipe iterator methods
893  ///
894  inline iterator begin() { return Recipes.begin(); }
895  inline const_iterator begin() const { return Recipes.begin(); }
896  inline iterator end() { return Recipes.end(); }
897  inline const_iterator end() const { return Recipes.end(); }
898 
899  inline reverse_iterator rbegin() { return Recipes.rbegin(); }
900  inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); }
901  inline reverse_iterator rend() { return Recipes.rend(); }
902  inline const_reverse_iterator rend() const { return Recipes.rend(); }
903 
904  inline size_t size() const { return Recipes.size(); }
905  inline bool empty() const { return Recipes.empty(); }
906  inline const VPRecipeBase &front() const { return Recipes.front(); }
907  inline VPRecipeBase &front() { return Recipes.front(); }
908  inline const VPRecipeBase &back() const { return Recipes.back(); }
909  inline VPRecipeBase &back() { return Recipes.back(); }
910 
911  /// Returns a pointer to a member of the recipe list.
913  return &VPBasicBlock::Recipes;
914  }
915 
916  /// Method to support type inquiry through isa, cast, and dyn_cast.
917  static inline bool classof(const VPBlockBase *V) {
918  return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC;
919  }
920 
921  void insert(VPRecipeBase *Recipe, iterator InsertPt) {
922  assert(Recipe && "No recipe to append.");
923  assert(!Recipe->Parent && "Recipe already in VPlan");
924  Recipe->Parent = this;
925  Recipes.insert(InsertPt, Recipe);
926  }
927 
928  /// Augment the existing recipes of a VPBasicBlock with an additional
929  /// \p Recipe as the last recipe.
930  void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); }
931 
932  /// The method which generates the output IR instructions that correspond to
933  /// this VPBasicBlock, thereby "executing" the VPlan.
934  void execute(struct VPTransformState *State) override;
935 
936 private:
937  /// Create an IR BasicBlock to hold the output instructions generated by this
938  /// VPBasicBlock, and return it. Update the CFGState accordingly.
939  BasicBlock *createEmptyBasicBlock(VPTransformState::CFGState &CFG);
940 };
941 
942 /// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks
943 /// which form a Single-Entry-Single-Exit subgraph of the output IR CFG.
944 /// A VPRegionBlock may indicate that its contents are to be replicated several
945 /// times. This is designed to support predicated scalarization, in which a
946 /// scalar if-then code structure needs to be generated VF * UF times. Having
947 /// this replication indicator helps to keep a single model for multiple
948 /// candidate VF's. The actual replication takes place only once the desired VF
949 /// and UF have been determined.
950 class VPRegionBlock : public VPBlockBase {
951 private:
952  /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock.
953  VPBlockBase *Entry;
954 
955  /// Hold the Single Exit of the SESE region modelled by the VPRegionBlock.
956  VPBlockBase *Exit;
957 
958  /// An indicator whether this region is to generate multiple replicated
959  /// instances of output IR corresponding to its VPBlockBases.
960  bool IsReplicator;
961 
962 public:
964  const std::string &Name = "", bool IsReplicator = false)
965  : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exit(Exit),
966  IsReplicator(IsReplicator) {
967  assert(Entry->getPredecessors().empty() && "Entry block has predecessors.");
968  assert(Exit->getSuccessors().empty() && "Exit block has successors.");
969  Entry->setParent(this);
970  Exit->setParent(this);
971  }
972  VPRegionBlock(const std::string &Name = "", bool IsReplicator = false)
973  : VPBlockBase(VPRegionBlockSC, Name), Entry(nullptr), Exit(nullptr),
974  IsReplicator(IsReplicator) {}
975 
976  ~VPRegionBlock() override {
977  if (Entry)
978  deleteCFG(Entry);
979  }
980 
981  /// Method to support type inquiry through isa, cast, and dyn_cast.
982  static inline bool classof(const VPBlockBase *V) {
983  return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC;
984  }
985 
986  const VPBlockBase *getEntry() const { return Entry; }
987  VPBlockBase *getEntry() { return Entry; }
988 
989  /// Set \p EntryBlock as the entry VPBlockBase of this VPRegionBlock. \p
990  /// EntryBlock must have no predecessors.
991  void setEntry(VPBlockBase *EntryBlock) {
992  assert(EntryBlock->getPredecessors().empty() &&
993  "Entry block cannot have predecessors.");
994  Entry = EntryBlock;
995  EntryBlock->setParent(this);
996  }
997 
998  const VPBlockBase *getExit() const { return Exit; }
999  VPBlockBase *getExit() { return Exit; }
1000 
1001  /// Set \p ExitBlock as the exit VPBlockBase of this VPRegionBlock. \p
1002  /// ExitBlock must have no successors.
1003  void setExit(VPBlockBase *ExitBlock) {
1004  assert(ExitBlock->getSuccessors().empty() &&
1005  "Exit block cannot have successors.");
1006  Exit = ExitBlock;
1007  ExitBlock->setParent(this);
1008  }
1009 
1010  /// An indicator whether this region is to generate multiple replicated
1011  /// instances of output IR corresponding to its VPBlockBases.
1012  bool isReplicator() const { return IsReplicator; }
1013 
1014  /// The method which generates the output IR instructions that correspond to
1015  /// this VPRegionBlock, thereby "executing" the VPlan.
1016  void execute(struct VPTransformState *State) override;
1017 };
1018 
1019 /// VPlan models a candidate for vectorization, encoding various decisions take
1020 /// to produce efficient output IR, including which branches, basic-blocks and
1021 /// output IR instructions to generate, and their cost. VPlan holds a
1022 /// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry
1023 /// VPBlock.
1024 class VPlan {
1025  friend class VPlanPrinter;
1026 
1027 private:
1028  /// Hold the single entry to the Hierarchical CFG of the VPlan.
1029  VPBlockBase *Entry;
1030 
1031  /// Holds the VFs applicable to this VPlan.
1033 
1034  /// Holds the name of the VPlan, for printing.
1035  std::string Name;
1036 
1037  /// Holds all the external definitions created for this VPlan.
1038  // TODO: Introduce a specific representation for external definitions in
1039  // VPlan. External definitions must be immutable and hold a pointer to its
1040  // underlying IR that will be used to implement its structural comparison
1041  // (operators '==' and '<').
1042  SmallSet<VPValue *, 16> VPExternalDefs;
1043 
1044  /// Holds a mapping between Values and their corresponding VPValue inside
1045  /// VPlan.
1046  Value2VPValueTy Value2VPValue;
1047 
1048 public:
1049  VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {}
1050 
1052  if (Entry)
1053  VPBlockBase::deleteCFG(Entry);
1054  for (auto &MapEntry : Value2VPValue)
1055  delete MapEntry.second;
1056  for (VPValue *Def : VPExternalDefs)
1057  delete Def;
1058  }
1059 
1060  /// Generate the IR code for this VPlan.
1061  void execute(struct VPTransformState *State);
1062 
1063  VPBlockBase *getEntry() { return Entry; }
1064  const VPBlockBase *getEntry() const { return Entry; }
1065 
1066  VPBlockBase *setEntry(VPBlockBase *Block) { return Entry = Block; }
1067 
1068  void addVF(unsigned VF) { VFs.insert(VF); }
1069 
1070  bool hasVF(unsigned VF) { return VFs.count(VF); }
1071 
1072  const std::string &getName() const { return Name; }
1073 
1074  void setName(const Twine &newName) { Name = newName.str(); }
1075 
1076  /// Add \p VPVal to the pool of external definitions if it's not already
1077  /// in the pool.
1078  void addExternalDef(VPValue *VPVal) {
1079  VPExternalDefs.insert(VPVal);
1080  }
1081 
1082  void addVPValue(Value *V) {
1083  assert(V && "Trying to add a null Value to VPlan");
1084  assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
1085  Value2VPValue[V] = new VPValue();
1086  }
1087 
1089  assert(V && "Trying to get the VPValue of a null Value");
1090  assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
1091  return Value2VPValue[V];
1092  }
1093 
1094 private:
1095  /// Add to the given dominator tree the header block and every new basic block
1096  /// that was created between it and the latch block, inclusive.
1097  static void updateDominatorTree(DominatorTree *DT,
1098  BasicBlock *LoopPreHeaderBB,
1099  BasicBlock *LoopLatchBB);
1100 };
1101 
1102 /// VPlanPrinter prints a given VPlan to a given output stream. The printing is
1103 /// indented and follows the dot format.
1105  friend inline raw_ostream &operator<<(raw_ostream &OS, VPlan &Plan);
1106  friend inline raw_ostream &operator<<(raw_ostream &OS,
1107  const struct VPlanIngredient &I);
1108 
1109 private:
1110  raw_ostream &OS;
1111  VPlan &Plan;
1112  unsigned Depth;
1113  unsigned TabWidth = 2;
1114  std::string Indent;
1115  unsigned BID = 0;
1117 
1118  VPlanPrinter(raw_ostream &O, VPlan &P) : OS(O), Plan(P) {}
1119 
1120  /// Handle indentation.
1121  void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); }
1122 
1123  /// Print a given \p Block of the Plan.
1124  void dumpBlock(const VPBlockBase *Block);
1125 
1126  /// Print the information related to the CFG edges going out of a given
1127  /// \p Block, followed by printing the successor blocks themselves.
1128  void dumpEdges(const VPBlockBase *Block);
1129 
1130  /// Print a given \p BasicBlock, including its VPRecipes, followed by printing
1131  /// its successor blocks.
1132  void dumpBasicBlock(const VPBasicBlock *BasicBlock);
1133 
1134  /// Print a given \p Region of the Plan.
1135  void dumpRegion(const VPRegionBlock *Region);
1136 
1137  unsigned getOrCreateBID(const VPBlockBase *Block) {
1138  return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++;
1139  }
1140 
1141  const Twine getOrCreateName(const VPBlockBase *Block);
1142 
1143  const Twine getUID(const VPBlockBase *Block);
1144 
1145  /// Print the information related to a CFG edge between two VPBlockBases.
1146  void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden,
1147  const Twine &Label);
1148 
1149  void dump();
1150 
1151  static void printAsIngredient(raw_ostream &O, Value *V);
1152 };
1153 
1156 
1157  VPlanIngredient(Value *V) : V(V) {}
1158 };
1159 
1161  VPlanPrinter::printAsIngredient(OS, I.V);
1162  return OS;
1163 }
1164 
1166  VPlanPrinter Printer(OS, Plan);
1167  Printer.dump();
1168  return OS;
1169 }
1170 
1171 //===--------------------------------------------------------------------===//
1172 // GraphTraits specializations for VPlan/VPRegionBlock Control-Flow Graphs //
1173 //===--------------------------------------------------------------------===//
1174 
1175 // Provide specializations of GraphTraits to be able to treat a VPBlockBase as a
1176 // graph of VPBlockBase nodes...
1177 
1178 template <> struct GraphTraits<VPBlockBase *> {
1181 
1182  static NodeRef getEntryNode(NodeRef N) { return N; }
1183 
1185  return N->getSuccessors().begin();
1186  }
1187 
1189  return N->getSuccessors().end();
1190  }
1191 };
1192 
1193 template <> struct GraphTraits<const VPBlockBase *> {
1194  using NodeRef = const VPBlockBase *;
1196 
1197  static NodeRef getEntryNode(NodeRef N) { return N; }
1198 
1200  return N->getSuccessors().begin();
1201  }
1202 
1204  return N->getSuccessors().end();
1205  }
1206 };
1207 
1208 // Provide specializations of GraphTraits to be able to treat a VPBlockBase as a
1209 // graph of VPBlockBase nodes... and to walk it in inverse order. Inverse order
1210 // for a VPBlockBase is considered to be when traversing the predecessors of a
1211 // VPBlockBase instead of its successors.
1212 template <> struct GraphTraits<Inverse<VPBlockBase *>> {
1215 
1217  return B;
1218  }
1219 
1221  return N->getPredecessors().begin();
1222  }
1223 
1225  return N->getPredecessors().end();
1226  }
1227 };
1228 
1229 //===----------------------------------------------------------------------===//
1230 // VPlan Utilities
1231 //===----------------------------------------------------------------------===//
1232 
1233 /// Class that provides utilities for VPBlockBases in VPlan.
1235 public:
1236  VPBlockUtils() = delete;
1237 
1238  /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
1239  /// NewBlock as successor of \p BlockPtr and \p Block as predecessor of \p
1240  /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p NewBlock
1241  /// must have neither successors nor predecessors.
1242  static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
1243  assert(NewBlock->getSuccessors().empty() &&
1244  "Can't insert new block with successors.");
1245  // TODO: move successors from BlockPtr to NewBlock when this functionality
1246  // is necessary. For now, setBlockSingleSuccessor will assert if BlockPtr
1247  // already has successors.
1248  BlockPtr->setOneSuccessor(NewBlock);
1249  NewBlock->setPredecessors({BlockPtr});
1250  NewBlock->setParent(BlockPtr->getParent());
1251  }
1252 
1253  /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
1254  /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
1255  /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
1256  /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
1257  /// and \p IfTrue and \p IfFalse must have neither successors nor
1258  /// predecessors.
1259  static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
1260  VPBlockBase *BlockPtr) {
1261  assert(IfTrue->getSuccessors().empty() &&
1262  "Can't insert IfTrue with successors.");
1263  assert(IfFalse->getSuccessors().empty() &&
1264  "Can't insert IfFalse with successors.");
1265  BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
1266  IfTrue->setPredecessors({BlockPtr});
1267  IfFalse->setPredecessors({BlockPtr});
1268  IfTrue->setParent(BlockPtr->getParent());
1269  IfFalse->setParent(BlockPtr->getParent());
1270  }
1271 
1272  /// Connect VPBlockBases \p From and \p To bi-directionally. Append \p To to
1273  /// the successors of \p From and \p From to the predecessors of \p To. Both
1274  /// VPBlockBases must have the same parent, which can be null. Both
1275  /// VPBlockBases can be already connected to other VPBlockBases.
1276  static void connectBlocks(VPBlockBase *From, VPBlockBase *To) {
1277  assert((From->getParent() == To->getParent()) &&
1278  "Can't connect two block with different parents");
1279  assert(From->getNumSuccessors() < 2 &&
1280  "Blocks can't have more than two successors.");
1281  From->appendSuccessor(To);
1282  To->appendPredecessor(From);
1283  }
1284 
1285  /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
1286  /// from the successors of \p From and \p From from the predecessors of \p To.
1287  static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
1288  assert(To && "Successor to disconnect is null.");
1289  From->removeSuccessor(To);
1290  To->removePredecessor(From);
1291  }
1292 };
1293 } // end namespace llvm
1294 
1295 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
const std::string & getName() const
Definition: VPlan.h:368
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:602
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:250
const VPRegionBlock * getParent() const
Definition: VPlan.h:378
bool appendInstruction(Instruction *Instr)
Augment the recipe to include Instr, if it lies at its End.
Definition: VPlan.h:618
void setAlsoPack(bool Pack)
Definition: VPlan.h:773
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:610
enum { VPBasicBlockSC, VPRegionBlockSC } VPBlockTy
An enumeration for keeping track of the concrete subclass of VPBlockBase that are actually instantiat...
Definition: VPlan.h:362
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:883
SmallVectorImpl< VPBlockBase * >::const_iterator ChildIteratorType
Definition: VPlan.h:1195
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:963
const_reverse_iterator rbegin() const
Definition: VPlan.h:900
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
VPRegionBlock * getParent()
Definition: VPlan.h:377
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:1024
VPInstruction(unsigned Opcode, ArrayRef< VPValue *> Operands)
Definition: VPlan.h:560
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
void setEntry(VPBlockBase *EntryBlock)
Set EntryBlock as the entry VPBlockBase of this VPRegionBlock.
Definition: VPlan.h:991
VPlanIngredient(Value *V)
Definition: VPlan.h:1157
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:950
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:520
IRBuilder & Builder
Hold a reference to the IRBuilder used to generate output IR code.
Definition: VPlan.h:290
VPRecipeBase & back()
Definition: VPlan.h:909
This is a helper struct for maintaining vectorization state.
Definition: VPlan.h:90
A Recipe for widening load/store operations.
Definition: VPlan.h:841
void print(raw_ostream &O, const Twine &Indent) const override
Print the recipe.
Definition: VPlan.h:800
bool hasAnyScalarValue(Value *Key) const
Definition: VPlan.h:128
void addExternalDef(VPValue *VPVal)
Add VPVal to the pool of external definitions if it&#39;s not already in the pool.
Definition: VPlan.h:1078
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:402
void addVPValue(Value *V)
Definition: VPlan.h:1082
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:642
static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBases IfTrue and IfFalse after BlockPtr.
Definition: VPlan.h:1259
VPRecipeBase & front()
Definition: VPlan.h:907
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:495
unsigned getVPRecipeID() const
Definition: VPlan.h:528
VPValue * getVPValue(Value *V)
Definition: VPlan.h:1088
bool hasAnyVectorValue(Value *Key) const
Definition: VPlan.h:113
reverse_iterator rend()
Definition: VPlan.h:901
static bool classof(const VPRecipeBase *R)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:573
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:815
const VPBlocksTy & getHierarchicalSuccessors()
Definition: VPlan.h:432
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:987
size_t size() const
Definition: VPlan.h:904
static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBase NewBlock after BlockPtr.
Definition: VPlan.h:1242
bool hasVectorValue(Value *Key, unsigned Part) const
Definition: VPlan.h:118
VPBlocksTy & getSuccessors()
Definition: VPlan.h:395
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:677
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:655
~VPRegionBlock() override
Definition: VPlan.h:976
void setName(const Twine &newName)
Definition: VPlan.h:370
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:921
const std::string & getName() const
Definition: VPlan.h:1072
VPBlocksTy & getPredecessors()
Definition: VPlan.h:398
static RecipeListTy VPBasicBlock::* getSublistAccess(VPRecipeBase *)
Returns a pointer to a member of the recipe list.
Definition: VPlan.h:912
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:1224
void setName(const Twine &newName)
Definition: VPlan.h:1074
VPWidenPHIRecipe(PHINode *Phi)
Definition: VPlan.h:660
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:1199
Key
PAL metadata keys.
VPBlockBase * getSinglePredecessor() const
Definition: VPlan.h:408
VPlanPrinter prints a given VPlan to a given output stream.
Definition: VPlan.h:1104
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:1203
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition: VPlan.h:1012
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:664
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:998
VPTransformState holds information passed down when "executing" a VPlan, needed for generating the ou...
Definition: VPlan.h:215
VPBlockBase * getSingleHierarchicalSuccessor()
Definition: VPlan.h:438
VPBlockBase * getSingleHierarchicalPredecessor()
Definition: VPlan.h:454
unsigned getVPBlockID() const
Definition: VPlan.h:375
static bool classof(const VPValue *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:568
unsigned getVPValueID() const
Definition: VPlanValue.h:83
VPInstruction(unsigned Opcode, std::initializer_list< VPValue *> Operands)
Definition: VPlan.h:564
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:894
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:1180
void appendRecipe(VPRecipeBase *Recipe)
Augment the existing recipes of a VPBasicBlock with an additional Recipe as the last recipe...
Definition: VPlan.h:930
const VPBlocksTy & getHierarchicalPredecessors()
Definition: VPlan.h:448
#define P(N)
This class augments VPValue with operands which provide the inverse def-use edges from VPValue&#39;s user...
Definition: VPlanValue.h:114
An ilist node that can access its parent list.
Definition: ilist_node.h:257
void setOneSuccessor(VPBlockBase *Successor)
Set a given VPBlockBase Successor as the single successor of this VPBlockBase.
Definition: VPlan.h:461
const InterleaveGroup * getInterleaveGroup()
Definition: VPlan.h:728
VPWidenMemoryInstructionRecipe(Instruction &Instr, VPValue *Mask)
Definition: VPlan.h:847
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:854
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlan.h:1220
VPBlendRecipe(PHINode *Phi, ArrayRef< VPValue *> Masks)
Definition: VPlan.h:685
void setExit(VPBlockBase *ExitBlock)
Set ExitBlock as the exit VPBlockBase of this VPRegionBlock.
Definition: VPlan.h:1003
reverse_iterator rbegin()
Definition: VPlan.h:899
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:637
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
size_t getNumPredecessors() const
Definition: VPlan.h:413
static NodeRef getEntryNode(NodeRef N)
Definition: VPlan.h:1182
static ChildIteratorType child_end(NodeRef N)
Definition: VPlan.h:1188
Hold state information used when constructing the CFG of the output IR, traversing the VPBasicBlocks ...
Definition: VPlan.h:264
size_t getNumSuccessors() const
Definition: VPlan.h:412
static const unsigned End
VPCallback & Callback
Definition: VPlan.h:303
VPBlockBase * setEntry(VPBlockBase *Block)
Definition: VPlan.h:1066
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
bool hasVF(unsigned VF)
Definition: VPlan.h:1070
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:917
SmallVectorImpl< VPBlockBase * >::iterator ChildIteratorType
Definition: VPlan.h:1214
iterator erase(const_iterator CI)
Definition: SmallVector.h:447
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:1276
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:929
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
void setPredecessors(ArrayRef< VPBlockBase *> NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
Definition: VPlan.h:479
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:868
VPBlockBase(const unsigned char SC, const std::string &N)
Definition: VPlan.h:354
const_iterator begin() const
Definition: VPlan.h:895
unsigned Lane
in [0..VF)
Definition: VPlan.h:70
void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse)
Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.
Definition: VPlan.h:470
const VPRecipeBase & back() const
Definition: VPlan.h:908
Iterator for intrusive lists based on ilist_node.
See the file comment.
Definition: ValueMap.h:86
const VPRecipeBase & front() const
Definition: VPlan.h:906
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:750
Class that provides utilities for VPBlockBases in VPlan.
Definition: VPlan.h:1234
static NodeRef getEntryNode(NodeRef N)
Definition: VPlan.h:1197
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:982
const VPBlocksTy & getSuccessors() const
Definition: VPlan.h:394
unsigned getNumIncomingValues() const
Return the number of incoming edges.
const VPBlockBase * getEntry() const
Definition: VPlan.h:986
void addVF(unsigned VF)
Definition: VPlan.h:1068
VPInterleaveRecipe is a recipe for transforming an interleave group of load or stores into one wide l...
Definition: VPlan.h:708
static Inverse< VPBlockBase * > getEntryNode(Inverse< VPBlockBase *> B)
Definition: VPlan.h:1216
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:999
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
VPRegionBlock(const std::string &Name="", bool IsReplicator=false)
Definition: VPlan.h:972
const VPBasicBlock * getParent() const
Definition: VPlan.h:532
bool empty() const
Definition: VPlan.h:905
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
VPInterleaveRecipe(const InterleaveGroup *IG)
Definition: VPlan.h:713
iterator insert(iterator where, pointer New)
Definition: ilist.h:228
const VPBlocksTy & getPredecessors() const
Definition: VPlan.h:397
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:309
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition: VPlan.h:735
VPBlockBase * getEntry()
Definition: VPlan.h:1063
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:791
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:827
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
VPRecipeBase(const unsigned char SC)
Definition: VPlan.h:522
VPPredInstPHIRecipe(Instruction *PredInst)
Construct a VPPredInstPHIRecipe given PredInst whose value needs a phi nodes after merging back from ...
Definition: VPlan.h:822
const VPBlockBase * getEntry() const
Definition: VPlan.h:1064
static bool classof(const VPRecipeBase *V)
Method to support type inquiry through isa, cast, and dyn_cast.
Definition: VPlan.h:764
VPlan(VPBlockBase *Entry=nullptr)
Definition: VPlan.h:1049
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector and ...
Definition: VPlan.h:631
unsigned getOpcode() const
Definition: VPlan.h:577
const_iterator end() const
Definition: VPlan.h:897
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2023
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:18
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:695
iterator end()
Definition: VPlan.h:896
VPBasicBlock * getParent()
Definition: VPlan.h:531
VPWidenRecipe is a recipe for producing a copy of vector type for each Instruction in its ingredients...
Definition: VPlan.h:595
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:780
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:1184
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:677
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:718
unsigned Part
in [0..UF)
Definition: VPlan.h:67
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:546
VPBranchOnMaskRecipe(VPValue *BlockInMask)
Definition: VPlan.h:785
bool use_empty() const
Definition: Value.h:328
const_reverse_iterator rend() const
Definition: VPlan.h:902
VPBasicBlock(const Twine &Name="", VPRecipeBase *Recipe=nullptr)
Definition: VPlan.h:877
void setParent(VPRegionBlock *P)
Definition: VPlan.h:380
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:1287
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