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