contrib/llvm/lib/Transforms/Vectorize/VPlan.h

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