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"
31 #include "llvm/ADT/DepthFirstIterator.h"
32 #include "llvm/ADT/GraphTraits.h"
33 #include "llvm/ADT/Optional.h"
34 #include "llvm/ADT/SmallBitVector.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/Analysis/VectorUtils.h"
42 #include "llvm/IR/IRBuilder.h"
43 #include <algorithm>
44 #include <cassert>
45 #include <cstddef>
46 #include <map>
47 #include <string>
48 
49 namespace llvm {
50 
51 class BasicBlock;
52 class DominatorTree;
53 class InnerLoopVectorizer;
54 template <class T> class InterleaveGroup;
55 class LoopInfo;
56 class raw_ostream;
57 class RecurrenceDescriptor;
58 class Value;
59 class VPBasicBlock;
60 class VPRegionBlock;
61 class VPSlotTracker;
62 class VPlan;
63 class VPlanSlp;
64 
65 /// A range of powers-of-2 vectorization factors with fixed start and
66 /// adjustable end. The range includes start and excludes end, e.g.,:
67 /// [1, 9) = {1, 2, 4, 8}
68 struct VFRange {
69   // A power of 2.
70   const unsigned Start;
71 
72   // Need not be a power of 2. If End <= Start range is empty.
73   unsigned End;
74 };
75 
76 using VPlanPtr = std::unique_ptr<VPlan>;
77 
78 /// In what follows, the term "input IR" refers to code that is fed into the
79 /// vectorizer whereas the term "output IR" refers to code that is generated by
80 /// the vectorizer.
81 
82 /// VPIteration represents a single point in the iteration space of the output
83 /// (vectorized and/or unrolled) IR loop.
84 struct VPIteration {
85   /// in [0..UF)
86   unsigned Part;
87 
88   /// in [0..VF)
89   unsigned Lane;
90 };
91 
92 /// This is a helper struct for maintaining vectorization state. It's used for
93 /// mapping values from the original loop to their corresponding values in
94 /// the new loop. Two mappings are maintained: one for vectorized values and
95 /// one for scalarized values. Vectorized values are represented with UF
96 /// vector values in the new loop, and scalarized values are represented with
97 /// UF x VF scalar values in the new loop. UF and VF are the unroll and
98 /// vectorization factors, respectively.
99 ///
100 /// Entries can be added to either map with setVectorValue and setScalarValue,
101 /// which assert that an entry was not already added before. If an entry is to
102 /// replace an existing one, call resetVectorValue and resetScalarValue. This is
103 /// currently needed to modify the mapped values during "fix-up" operations that
104 /// occur once the first phase of widening is complete. These operations include
105 /// type truncation and the second phase of recurrence widening.
106 ///
107 /// Entries from either map can be retrieved using the getVectorValue and
108 /// getScalarValue functions, which assert that the desired value exists.
109 struct VectorizerValueMap {
110   friend struct VPTransformState;
111 
112 private:
113   /// The unroll factor. Each entry in the vector map contains UF vector values.
114   unsigned UF;
115 
116   /// The vectorization factor. Each entry in the scalar map contains UF x VF
117   /// scalar values.
118   ElementCount VF;
119 
120   /// The vector and scalar map storage. We use std::map and not DenseMap
121   /// because insertions to DenseMap invalidate its iterators.
122   using VectorParts = SmallVector<Value *, 2>;
123   using ScalarParts = SmallVector<SmallVector<Value *, 4>, 2>;
124   std::map<Value *, VectorParts> VectorMapStorage;
125   std::map<Value *, ScalarParts> ScalarMapStorage;
126 
127 public:
128   /// Construct an empty map with the given unroll and vectorization factors.
129   VectorizerValueMap(unsigned UF, ElementCount VF) : UF(UF), VF(VF) {}
130 
131   /// \return True if the map has any vector entry for \p Key.
132   bool hasAnyVectorValue(Value *Key) const {
133     return VectorMapStorage.count(Key);
134   }
135 
136   /// \return True if the map has a vector entry for \p Key and \p Part.
137   bool hasVectorValue(Value *Key, unsigned Part) const {
138     assert(Part < UF && "Queried Vector Part is too large.");
139     if (!hasAnyVectorValue(Key))
140       return false;
141     const VectorParts &Entry = VectorMapStorage.find(Key)->second;
142     assert(Entry.size() == UF && "VectorParts has wrong dimensions.");
143     return Entry[Part] != nullptr;
144   }
145 
146   /// \return True if the map has any scalar entry for \p Key.
147   bool hasAnyScalarValue(Value *Key) const {
148     return ScalarMapStorage.count(Key);
149   }
150 
151   /// \return True if the map has a scalar entry for \p Key and \p Instance.
152   bool hasScalarValue(Value *Key, const VPIteration &Instance) const {
153     assert(Instance.Part < UF && "Queried Scalar Part is too large.");
154     assert(Instance.Lane < VF.Min && "Queried Scalar Lane is too large.");
155     assert(!VF.Scalable && "VF is assumed to be non scalable.");
156 
157     if (!hasAnyScalarValue(Key))
158       return false;
159     const ScalarParts &Entry = ScalarMapStorage.find(Key)->second;
160     assert(Entry.size() == UF && "ScalarParts has wrong dimensions.");
161     assert(Entry[Instance.Part].size() == VF.Min &&
162            "ScalarParts has wrong dimensions.");
163     return Entry[Instance.Part][Instance.Lane] != nullptr;
164   }
165 
166   /// Retrieve the existing vector value that corresponds to \p Key and
167   /// \p Part.
168   Value *getVectorValue(Value *Key, unsigned Part) {
169     assert(hasVectorValue(Key, Part) && "Getting non-existent value.");
170     return VectorMapStorage[Key][Part];
171   }
172 
173   /// Retrieve the existing scalar value that corresponds to \p Key and
174   /// \p Instance.
175   Value *getScalarValue(Value *Key, const VPIteration &Instance) {
176     assert(hasScalarValue(Key, Instance) && "Getting non-existent value.");
177     return ScalarMapStorage[Key][Instance.Part][Instance.Lane];
178   }
179 
180   /// Set a vector value associated with \p Key and \p Part. Assumes such a
181   /// value is not already set. If it is, use resetVectorValue() instead.
182   void setVectorValue(Value *Key, unsigned Part, Value *Vector) {
183     assert(!hasVectorValue(Key, Part) && "Vector value already set for part");
184     if (!VectorMapStorage.count(Key)) {
185       VectorParts Entry(UF);
186       VectorMapStorage[Key] = Entry;
187     }
188     VectorMapStorage[Key][Part] = Vector;
189   }
190 
191   /// Set a scalar value associated with \p Key and \p Instance. Assumes such a
192   /// value is not already set.
193   void setScalarValue(Value *Key, const VPIteration &Instance, Value *Scalar) {
194     assert(!hasScalarValue(Key, Instance) && "Scalar value already set");
195     if (!ScalarMapStorage.count(Key)) {
196       ScalarParts Entry(UF);
197       // TODO: Consider storing uniform values only per-part, as they occupy
198       //       lane 0 only, keeping the other VF-1 redundant entries null.
199       for (unsigned Part = 0; Part < UF; ++Part)
200         Entry[Part].resize(VF.Min, nullptr);
201       ScalarMapStorage[Key] = Entry;
202     }
203     ScalarMapStorage[Key][Instance.Part][Instance.Lane] = Scalar;
204   }
205 
206   /// Reset the vector value associated with \p Key for the given \p Part.
207   /// This function can be used to update values that have already been
208   /// vectorized. This is the case for "fix-up" operations including type
209   /// truncation and the second phase of recurrence vectorization.
210   void resetVectorValue(Value *Key, unsigned Part, Value *Vector) {
211     assert(hasVectorValue(Key, Part) && "Vector value not set for part");
212     VectorMapStorage[Key][Part] = Vector;
213   }
214 
215   /// Reset the scalar value associated with \p Key for \p Part and \p Lane.
216   /// This function can be used to update values that have already been
217   /// scalarized. This is the case for "fix-up" operations including scalar phi
218   /// nodes for scalarized and predicated instructions.
219   void resetScalarValue(Value *Key, const VPIteration &Instance,
220                         Value *Scalar) {
221     assert(hasScalarValue(Key, Instance) &&
222            "Scalar value not set for part and lane");
223     ScalarMapStorage[Key][Instance.Part][Instance.Lane] = Scalar;
224   }
225 };
226 
227 /// This class is used to enable the VPlan to invoke a method of ILV. This is
228 /// needed until the method is refactored out of ILV and becomes reusable.
229 struct VPCallback {
230   virtual ~VPCallback() {}
231   virtual Value *getOrCreateVectorValues(Value *V, unsigned Part) = 0;
232   virtual Value *getOrCreateScalarValue(Value *V,
233                                         const VPIteration &Instance) = 0;
234 };
235 
236 /// VPTransformState holds information passed down when "executing" a VPlan,
237 /// needed for generating the output IR.
238 struct VPTransformState {
239   VPTransformState(ElementCount VF, unsigned UF, LoopInfo *LI,
240                    DominatorTree *DT, IRBuilder<> &Builder,
241                    VectorizerValueMap &ValueMap, InnerLoopVectorizer *ILV,
242                    VPCallback &Callback)
243       : VF(VF), UF(UF), Instance(), LI(LI), DT(DT), Builder(Builder),
244         ValueMap(ValueMap), ILV(ILV), Callback(Callback) {}
245 
246   /// The chosen Vectorization and Unroll Factors of the loop being vectorized.
247   ElementCount VF;
248   unsigned UF;
249 
250   /// Hold the indices to generate specific scalar instructions. Null indicates
251   /// that all instances are to be generated, using either scalar or vector
252   /// instructions.
253   Optional<VPIteration> Instance;
254 
255   struct DataState {
256     /// A type for vectorized values in the new loop. Each value from the
257     /// original loop, when vectorized, is represented by UF vector values in
258     /// the new unrolled loop, where UF is the unroll factor.
259     typedef SmallVector<Value *, 2> PerPartValuesTy;
260 
261     DenseMap<VPValue *, PerPartValuesTy> PerPartOutput;
262   } Data;
263 
264   /// Get the generated Value for a given VPValue and a given Part. Note that
265   /// as some Defs are still created by ILV and managed in its ValueMap, this
266   /// method will delegate the call to ILV in such cases in order to provide
267   /// callers a consistent API.
268   /// \see set.
269   Value *get(VPValue *Def, unsigned Part) {
270     // If Values have been set for this Def return the one relevant for \p Part.
271     if (Data.PerPartOutput.count(Def))
272       return Data.PerPartOutput[Def][Part];
273     // Def is managed by ILV: bring the Values from ValueMap.
274     return Callback.getOrCreateVectorValues(VPValue2Value[Def], Part);
275   }
276 
277   /// Get the generated Value for a given VPValue and given Part and Lane.
278   Value *get(VPValue *Def, const VPIteration &Instance) {
279     // If the Def is managed directly by VPTransformState, extract the lane from
280     // the relevant part. Note that currently only VPInstructions and external
281     // defs are managed by VPTransformState. Other Defs are still created by ILV
282     // and managed in its ValueMap. For those this method currently just
283     // delegates the call to ILV below.
284     if (Data.PerPartOutput.count(Def)) {
285       auto *VecPart = Data.PerPartOutput[Def][Instance.Part];
286       // TODO: Cache created scalar values.
287       return Builder.CreateExtractElement(VecPart,
288                                           Builder.getInt32(Instance.Lane));
289     }
290 
291     return Callback.getOrCreateScalarValue(VPValue2Value[Def], Instance);
292   }
293 
294   /// Set the generated Value for a given VPValue and a given Part.
295   void set(VPValue *Def, Value *V, unsigned Part) {
296     if (!Data.PerPartOutput.count(Def)) {
297       DataState::PerPartValuesTy Entry(UF);
298       Data.PerPartOutput[Def] = Entry;
299     }
300     Data.PerPartOutput[Def][Part] = V;
301   }
302 
303   /// Hold state information used when constructing the CFG of the output IR,
304   /// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks.
305   struct CFGState {
306     /// The previous VPBasicBlock visited. Initially set to null.
307     VPBasicBlock *PrevVPBB = nullptr;
308 
309     /// The previous IR BasicBlock created or used. Initially set to the new
310     /// header BasicBlock.
311     BasicBlock *PrevBB = nullptr;
312 
313     /// The last IR BasicBlock in the output IR. Set to the new latch
314     /// BasicBlock, used for placing the newly created BasicBlocks.
315     BasicBlock *LastBB = nullptr;
316 
317     /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case
318     /// of replication, maps the BasicBlock of the last replica created.
319     SmallDenseMap<VPBasicBlock *, BasicBlock *> VPBB2IRBB;
320 
321     /// Vector of VPBasicBlocks whose terminator instruction needs to be fixed
322     /// up at the end of vector code generation.
323     SmallVector<VPBasicBlock *, 8> VPBBsToFix;
324 
325     CFGState() = default;
326   } CFG;
327 
328   /// Hold a pointer to LoopInfo to register new basic blocks in the loop.
329   LoopInfo *LI;
330 
331   /// Hold a pointer to Dominator Tree to register new basic blocks in the loop.
332   DominatorTree *DT;
333 
334   /// Hold a reference to the IRBuilder used to generate output IR code.
335   IRBuilder<> &Builder;
336 
337   /// Hold a reference to the Value state information used when generating the
338   /// Values of the output IR.
339   VectorizerValueMap &ValueMap;
340 
341   /// Hold a reference to a mapping between VPValues in VPlan and original
342   /// Values they correspond to.
343   VPValue2ValueTy VPValue2Value;
344 
345   /// Hold the canonical scalar IV of the vector loop (start=0, step=VF*UF).
346   Value *CanonicalIV = nullptr;
347 
348   /// Hold the trip count of the scalar loop.
349   Value *TripCount = nullptr;
350 
351   /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
352   InnerLoopVectorizer *ILV;
353 
354   VPCallback &Callback;
355 };
356 
357 /// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
358 /// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.
359 class VPBlockBase {
360   friend class VPBlockUtils;
361 
362   const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
363 
364   /// An optional name for the block.
365   std::string Name;
366 
367   /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if
368   /// it is a topmost VPBlockBase.
369   VPRegionBlock *Parent = nullptr;
370 
371   /// List of predecessor blocks.
372   SmallVector<VPBlockBase *, 1> Predecessors;
373 
374   /// List of successor blocks.
375   SmallVector<VPBlockBase *, 1> Successors;
376 
377   /// Successor selector, null for zero or single successor blocks.
378   VPValue *CondBit = nullptr;
379 
380   /// Current block predicate - null if the block does not need a predicate.
381   VPValue *Predicate = nullptr;
382 
383   /// VPlan containing the block. Can only be set on the entry block of the
384   /// plan.
385   VPlan *Plan = nullptr;
386 
387   /// Add \p Successor as the last successor to this block.
388   void appendSuccessor(VPBlockBase *Successor) {
389     assert(Successor && "Cannot add nullptr successor!");
390     Successors.push_back(Successor);
391   }
392 
393   /// Add \p Predecessor as the last predecessor to this block.
394   void appendPredecessor(VPBlockBase *Predecessor) {
395     assert(Predecessor && "Cannot add nullptr predecessor!");
396     Predecessors.push_back(Predecessor);
397   }
398 
399   /// Remove \p Predecessor from the predecessors of this block.
400   void removePredecessor(VPBlockBase *Predecessor) {
401     auto Pos = std::find(Predecessors.begin(), Predecessors.end(), Predecessor);
402     assert(Pos && "Predecessor does not exist");
403     Predecessors.erase(Pos);
404   }
405 
406   /// Remove \p Successor from the successors of this block.
407   void removeSuccessor(VPBlockBase *Successor) {
408     auto Pos = std::find(Successors.begin(), Successors.end(), Successor);
409     assert(Pos && "Successor does not exist");
410     Successors.erase(Pos);
411   }
412 
413 protected:
414   VPBlockBase(const unsigned char SC, const std::string &N)
415       : SubclassID(SC), Name(N) {}
416 
417 public:
418   /// An enumeration for keeping track of the concrete subclass of VPBlockBase
419   /// that are actually instantiated. Values of this enumeration are kept in the
420   /// SubclassID field of the VPBlockBase objects. They are used for concrete
421   /// type identification.
422   using VPBlockTy = enum { VPBasicBlockSC, VPRegionBlockSC };
423 
424   using VPBlocksTy = SmallVectorImpl<VPBlockBase *>;
425 
426   virtual ~VPBlockBase() = default;
427 
428   const std::string &getName() const { return Name; }
429 
430   void setName(const Twine &newName) { Name = newName.str(); }
431 
432   /// \return an ID for the concrete type of this object.
433   /// This is used to implement the classof checks. This should not be used
434   /// for any other purpose, as the values may change as LLVM evolves.
435   unsigned getVPBlockID() const { return SubclassID; }
436 
437   VPRegionBlock *getParent() { return Parent; }
438   const VPRegionBlock *getParent() const { return Parent; }
439 
440   /// \return A pointer to the plan containing the current block.
441   VPlan *getPlan();
442   const VPlan *getPlan() const;
443 
444   /// Sets the pointer of the plan containing the block. The block must be the
445   /// entry block into the VPlan.
446   void setPlan(VPlan *ParentPlan);
447 
448   void setParent(VPRegionBlock *P) { Parent = P; }
449 
450   /// \return the VPBasicBlock that is the entry of this VPBlockBase,
451   /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
452   /// VPBlockBase is a VPBasicBlock, it is returned.
453   const VPBasicBlock *getEntryBasicBlock() const;
454   VPBasicBlock *getEntryBasicBlock();
455 
456   /// \return the VPBasicBlock that is the exit of this VPBlockBase,
457   /// recursively, if the latter is a VPRegionBlock. Otherwise, if this
458   /// VPBlockBase is a VPBasicBlock, it is returned.
459   const VPBasicBlock *getExitBasicBlock() const;
460   VPBasicBlock *getExitBasicBlock();
461 
462   const VPBlocksTy &getSuccessors() const { return Successors; }
463   VPBlocksTy &getSuccessors() { return Successors; }
464 
465   const VPBlocksTy &getPredecessors() const { return Predecessors; }
466   VPBlocksTy &getPredecessors() { return Predecessors; }
467 
468   /// \return the successor of this VPBlockBase if it has a single successor.
469   /// Otherwise return a null pointer.
470   VPBlockBase *getSingleSuccessor() const {
471     return (Successors.size() == 1 ? *Successors.begin() : nullptr);
472   }
473 
474   /// \return the predecessor of this VPBlockBase if it has a single
475   /// predecessor. Otherwise return a null pointer.
476   VPBlockBase *getSinglePredecessor() const {
477     return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr);
478   }
479 
480   size_t getNumSuccessors() const { return Successors.size(); }
481   size_t getNumPredecessors() const { return Predecessors.size(); }
482 
483   /// An Enclosing Block of a block B is any block containing B, including B
484   /// itself. \return the closest enclosing block starting from "this", which
485   /// has successors. \return the root enclosing block if all enclosing blocks
486   /// have no successors.
487   VPBlockBase *getEnclosingBlockWithSuccessors();
488 
489   /// \return the closest enclosing block starting from "this", which has
490   /// predecessors. \return the root enclosing block if all enclosing blocks
491   /// have no predecessors.
492   VPBlockBase *getEnclosingBlockWithPredecessors();
493 
494   /// \return the successors either attached directly to this VPBlockBase or, if
495   /// this VPBlockBase is the exit block of a VPRegionBlock and has no
496   /// successors of its own, search recursively for the first enclosing
497   /// VPRegionBlock that has successors and return them. If no such
498   /// VPRegionBlock exists, return the (empty) successors of the topmost
499   /// VPBlockBase reached.
500   const VPBlocksTy &getHierarchicalSuccessors() {
501     return getEnclosingBlockWithSuccessors()->getSuccessors();
502   }
503 
504   /// \return the hierarchical successor of this VPBlockBase if it has a single
505   /// hierarchical successor. Otherwise return a null pointer.
506   VPBlockBase *getSingleHierarchicalSuccessor() {
507     return getEnclosingBlockWithSuccessors()->getSingleSuccessor();
508   }
509 
510   /// \return the predecessors either attached directly to this VPBlockBase or,
511   /// if this VPBlockBase is the entry block of a VPRegionBlock and has no
512   /// predecessors of its own, search recursively for the first enclosing
513   /// VPRegionBlock that has predecessors and return them. If no such
514   /// VPRegionBlock exists, return the (empty) predecessors of the topmost
515   /// VPBlockBase reached.
516   const VPBlocksTy &getHierarchicalPredecessors() {
517     return getEnclosingBlockWithPredecessors()->getPredecessors();
518   }
519 
520   /// \return the hierarchical predecessor of this VPBlockBase if it has a
521   /// single hierarchical predecessor. Otherwise return a null pointer.
522   VPBlockBase *getSingleHierarchicalPredecessor() {
523     return getEnclosingBlockWithPredecessors()->getSinglePredecessor();
524   }
525 
526   /// \return the condition bit selecting the successor.
527   VPValue *getCondBit() { return CondBit; }
528 
529   const VPValue *getCondBit() const { return CondBit; }
530 
531   void setCondBit(VPValue *CV) { CondBit = CV; }
532 
533   VPValue *getPredicate() { return Predicate; }
534 
535   const VPValue *getPredicate() const { return Predicate; }
536 
537   void setPredicate(VPValue *Pred) { Predicate = Pred; }
538 
539   /// Set a given VPBlockBase \p Successor as the single successor of this
540   /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor.
541   /// This VPBlockBase must have no successors.
542   void setOneSuccessor(VPBlockBase *Successor) {
543     assert(Successors.empty() && "Setting one successor when others exist.");
544     appendSuccessor(Successor);
545   }
546 
547   /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two
548   /// successors of this VPBlockBase. \p Condition is set as the successor
549   /// selector. This VPBlockBase is not added as predecessor of \p IfTrue or \p
550   /// IfFalse. This VPBlockBase must have no successors.
551   void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
552                         VPValue *Condition) {
553     assert(Successors.empty() && "Setting two successors when others exist.");
554     assert(Condition && "Setting two successors without condition!");
555     CondBit = Condition;
556     appendSuccessor(IfTrue);
557     appendSuccessor(IfFalse);
558   }
559 
560   /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase.
561   /// This VPBlockBase must have no predecessors. This VPBlockBase is not added
562   /// as successor of any VPBasicBlock in \p NewPreds.
563   void setPredecessors(ArrayRef<VPBlockBase *> NewPreds) {
564     assert(Predecessors.empty() && "Block predecessors already set.");
565     for (auto *Pred : NewPreds)
566       appendPredecessor(Pred);
567   }
568 
569   /// Remove all the predecessor of this block.
570   void clearPredecessors() { Predecessors.clear(); }
571 
572   /// Remove all the successors of this block and set to null its condition bit
573   void clearSuccessors() {
574     Successors.clear();
575     CondBit = nullptr;
576   }
577 
578   /// The method which generates the output IR that correspond to this
579   /// VPBlockBase, thereby "executing" the VPlan.
580   virtual void execute(struct VPTransformState *State) = 0;
581 
582   /// Delete all blocks reachable from a given VPBlockBase, inclusive.
583   static void deleteCFG(VPBlockBase *Entry);
584 
585   void printAsOperand(raw_ostream &OS, bool PrintType) const {
586     OS << getName();
587   }
588 
589   void print(raw_ostream &OS) const {
590     // TODO: Only printing VPBB name for now since we only have dot printing
591     // support for VPInstructions/Recipes.
592     printAsOperand(OS, false);
593   }
594 
595   /// Return true if it is legal to hoist instructions into this block.
596   bool isLegalToHoistInto() {
597     // There are currently no constraints that prevent an instruction to be
598     // hoisted into a VPBlockBase.
599     return true;
600   }
601 };
602 
603 /// VPRecipeBase is a base class modeling a sequence of one or more output IR
604 /// instructions.
605 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> {
606   friend VPBasicBlock;
607   friend class VPBlockUtils;
608 
609   const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
610 
611   /// Each VPRecipe belongs to a single VPBasicBlock.
612   VPBasicBlock *Parent = nullptr;
613 
614 public:
615   /// An enumeration for keeping track of the concrete subclass of VPRecipeBase
616   /// that is actually instantiated. Values of this enumeration are kept in the
617   /// SubclassID field of the VPRecipeBase objects. They are used for concrete
618   /// type identification.
619   using VPRecipeTy = enum {
620     VPBlendSC,
621     VPBranchOnMaskSC,
622     VPInstructionSC,
623     VPInterleaveSC,
624     VPPredInstPHISC,
625     VPReductionSC,
626     VPReplicateSC,
627     VPWidenCallSC,
628     VPWidenCanonicalIVSC,
629     VPWidenGEPSC,
630     VPWidenIntOrFpInductionSC,
631     VPWidenMemoryInstructionSC,
632     VPWidenPHISC,
633     VPWidenSC,
634     VPWidenSelectSC
635   };
636 
637   VPRecipeBase(const unsigned char SC) : SubclassID(SC) {}
638   virtual ~VPRecipeBase() = default;
639 
640   /// \return an ID for the concrete type of this object.
641   /// This is used to implement the classof checks. This should not be used
642   /// for any other purpose, as the values may change as LLVM evolves.
643   unsigned getVPRecipeID() const { return SubclassID; }
644 
645   /// \return the VPBasicBlock which this VPRecipe belongs to.
646   VPBasicBlock *getParent() { return Parent; }
647   const VPBasicBlock *getParent() const { return Parent; }
648 
649   /// The method which generates the output IR instructions that correspond to
650   /// this VPRecipe, thereby "executing" the VPlan.
651   virtual void execute(struct VPTransformState &State) = 0;
652 
653   /// Each recipe prints itself.
654   virtual void print(raw_ostream &O, const Twine &Indent,
655                      VPSlotTracker &SlotTracker) const = 0;
656 
657   /// Insert an unlinked recipe into a basic block immediately before
658   /// the specified recipe.
659   void insertBefore(VPRecipeBase *InsertPos);
660 
661   /// Insert an unlinked Recipe into a basic block immediately after
662   /// the specified Recipe.
663   void insertAfter(VPRecipeBase *InsertPos);
664 
665   /// Unlink this recipe from its current VPBasicBlock and insert it into
666   /// the VPBasicBlock that MovePos lives in, right after MovePos.
667   void moveAfter(VPRecipeBase *MovePos);
668 
669   /// This method unlinks 'this' from the containing basic block, but does not
670   /// delete it.
671   void removeFromParent();
672 
673   /// This method unlinks 'this' from the containing basic block and deletes it.
674   ///
675   /// \returns an iterator pointing to the element after the erased one
676   iplist<VPRecipeBase>::iterator eraseFromParent();
677 };
678 
679 /// This is a concrete Recipe that models a single VPlan-level instruction.
680 /// While as any Recipe it may generate a sequence of IR instructions when
681 /// executed, these instructions would always form a single-def expression as
682 /// the VPInstruction is also a single def-use vertex.
683 class VPInstruction : public VPUser, public VPRecipeBase {
684   friend class VPlanSlp;
685 
686 public:
687   /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
688   enum {
689     Not = Instruction::OtherOpsEnd + 1,
690     ICmpULE,
691     SLPLoad,
692     SLPStore,
693     ActiveLaneMask,
694   };
695 
696 private:
697   typedef unsigned char OpcodeTy;
698   OpcodeTy Opcode;
699 
700   /// Utility method serving execute(): generates a single instance of the
701   /// modeled instruction.
702   void generateInstruction(VPTransformState &State, unsigned Part);
703 
704 protected:
705   Instruction *getUnderlyingInstr() {
706     return cast_or_null<Instruction>(getUnderlyingValue());
707   }
708 
709   void setUnderlyingInstr(Instruction *I) { setUnderlyingValue(I); }
710 
711 public:
712   VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands)
713       : VPUser(VPValue::VPInstructionSC, Operands),
714         VPRecipeBase(VPRecipeBase::VPInstructionSC), Opcode(Opcode) {}
715 
716   VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands)
717       : VPInstruction(Opcode, ArrayRef<VPValue *>(Operands)) {}
718 
719   /// Method to support type inquiry through isa, cast, and dyn_cast.
720   static inline bool classof(const VPValue *V) {
721     return V->getVPValueID() == VPValue::VPInstructionSC;
722   }
723 
724   VPInstruction *clone() const {
725     SmallVector<VPValue *, 2> Operands(operands());
726     return new VPInstruction(Opcode, Operands);
727   }
728 
729   /// Method to support type inquiry through isa, cast, and dyn_cast.
730   static inline bool classof(const VPRecipeBase *R) {
731     return R->getVPRecipeID() == VPRecipeBase::VPInstructionSC;
732   }
733 
734   unsigned getOpcode() const { return Opcode; }
735 
736   /// Generate the instruction.
737   /// TODO: We currently execute only per-part unless a specific instance is
738   /// provided.
739   void execute(VPTransformState &State) override;
740 
741   /// Print the Recipe.
742   void print(raw_ostream &O, const Twine &Indent,
743              VPSlotTracker &SlotTracker) const override;
744 
745   /// Print the VPInstruction.
746   void print(raw_ostream &O) const;
747   void print(raw_ostream &O, VPSlotTracker &SlotTracker) const;
748 
749   /// Return true if this instruction may modify memory.
750   bool mayWriteToMemory() const {
751     // TODO: we can use attributes of the called function to rule out memory
752     //       modifications.
753     return Opcode == Instruction::Store || Opcode == Instruction::Call ||
754            Opcode == Instruction::Invoke || Opcode == SLPStore;
755   }
756 
757   bool hasResult() const {
758     // CallInst may or may not have a result, depending on the called function.
759     // Conservatively return calls have results for now.
760     switch (getOpcode()) {
761     case Instruction::Ret:
762     case Instruction::Br:
763     case Instruction::Store:
764     case Instruction::Switch:
765     case Instruction::IndirectBr:
766     case Instruction::Resume:
767     case Instruction::CatchRet:
768     case Instruction::Unreachable:
769     case Instruction::Fence:
770     case Instruction::AtomicRMW:
771       return false;
772     default:
773       return true;
774     }
775   }
776 };
777 
778 /// VPWidenRecipe is a recipe for producing a copy of vector type its
779 /// ingredient. This recipe covers most of the traditional vectorization cases
780 /// where each ingredient transforms into a vectorized version of itself.
781 class VPWidenRecipe : public VPRecipeBase {
782   /// Hold the instruction to be widened.
783   Instruction &Ingredient;
784 
785   /// Hold VPValues for the operands of the ingredient.
786   VPUser User;
787 
788 public:
789   template <typename IterT>
790   VPWidenRecipe(Instruction &I, iterator_range<IterT> Operands)
791       : VPRecipeBase(VPWidenSC), Ingredient(I), User(Operands) {}
792 
793   ~VPWidenRecipe() override = default;
794 
795   /// Method to support type inquiry through isa, cast, and dyn_cast.
796   static inline bool classof(const VPRecipeBase *V) {
797     return V->getVPRecipeID() == VPRecipeBase::VPWidenSC;
798   }
799 
800   /// Produce widened copies of all Ingredients.
801   void execute(VPTransformState &State) override;
802 
803   /// Print the recipe.
804   void print(raw_ostream &O, const Twine &Indent,
805              VPSlotTracker &SlotTracker) const override;
806 };
807 
808 /// A recipe for widening Call instructions.
809 class VPWidenCallRecipe : public VPRecipeBase {
810   /// Hold the call to be widened.
811   CallInst &Ingredient;
812 
813   /// Hold VPValues for the arguments of the call.
814   VPUser User;
815 
816 public:
817   template <typename IterT>
818   VPWidenCallRecipe(CallInst &I, iterator_range<IterT> CallArguments)
819       : VPRecipeBase(VPWidenCallSC), Ingredient(I), User(CallArguments) {}
820 
821   ~VPWidenCallRecipe() override = default;
822 
823   /// Method to support type inquiry through isa, cast, and dyn_cast.
824   static inline bool classof(const VPRecipeBase *V) {
825     return V->getVPRecipeID() == VPRecipeBase::VPWidenCallSC;
826   }
827 
828   /// Produce a widened version of the call instruction.
829   void execute(VPTransformState &State) override;
830 
831   /// Print the recipe.
832   void print(raw_ostream &O, const Twine &Indent,
833              VPSlotTracker &SlotTracker) const override;
834 };
835 
836 /// A recipe for widening select instructions.
837 class VPWidenSelectRecipe : public VPRecipeBase {
838 private:
839   /// Hold the select to be widened.
840   SelectInst &Ingredient;
841 
842   /// Hold VPValues for the operands of the select.
843   VPUser User;
844 
845   /// Is the condition of the select loop invariant?
846   bool InvariantCond;
847 
848 public:
849   template <typename IterT>
850   VPWidenSelectRecipe(SelectInst &I, iterator_range<IterT> Operands,
851                       bool InvariantCond)
852       : VPRecipeBase(VPWidenSelectSC), Ingredient(I), User(Operands),
853         InvariantCond(InvariantCond) {}
854 
855   ~VPWidenSelectRecipe() override = default;
856 
857   /// Method to support type inquiry through isa, cast, and dyn_cast.
858   static inline bool classof(const VPRecipeBase *V) {
859     return V->getVPRecipeID() == VPRecipeBase::VPWidenSelectSC;
860   }
861 
862   /// Produce a widened version of the select instruction.
863   void execute(VPTransformState &State) override;
864 
865   /// Print the recipe.
866   void print(raw_ostream &O, const Twine &Indent,
867              VPSlotTracker &SlotTracker) const override;
868 };
869 
870 /// A recipe for handling GEP instructions.
871 class VPWidenGEPRecipe : public VPRecipeBase {
872   GetElementPtrInst *GEP;
873 
874   /// Hold VPValues for the base and indices of the GEP.
875   VPUser User;
876 
877   bool IsPtrLoopInvariant;
878   SmallBitVector IsIndexLoopInvariant;
879 
880 public:
881   template <typename IterT>
882   VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range<IterT> Operands,
883                    Loop *OrigLoop)
884       : VPRecipeBase(VPWidenGEPSC), GEP(GEP), User(Operands),
885         IsIndexLoopInvariant(GEP->getNumIndices(), false) {
886     IsPtrLoopInvariant = OrigLoop->isLoopInvariant(GEP->getPointerOperand());
887     for (auto Index : enumerate(GEP->indices()))
888       IsIndexLoopInvariant[Index.index()] =
889           OrigLoop->isLoopInvariant(Index.value().get());
890   }
891   ~VPWidenGEPRecipe() override = default;
892 
893   /// Method to support type inquiry through isa, cast, and dyn_cast.
894   static inline bool classof(const VPRecipeBase *V) {
895     return V->getVPRecipeID() == VPRecipeBase::VPWidenGEPSC;
896   }
897 
898   /// Generate the gep nodes.
899   void execute(VPTransformState &State) override;
900 
901   /// Print the recipe.
902   void print(raw_ostream &O, const Twine &Indent,
903              VPSlotTracker &SlotTracker) const override;
904 };
905 
906 /// A recipe for handling phi nodes of integer and floating-point inductions,
907 /// producing their vector and scalar values.
908 class VPWidenIntOrFpInductionRecipe : public VPRecipeBase {
909   PHINode *IV;
910   TruncInst *Trunc;
911 
912 public:
913   VPWidenIntOrFpInductionRecipe(PHINode *IV, TruncInst *Trunc = nullptr)
914       : VPRecipeBase(VPWidenIntOrFpInductionSC), IV(IV), Trunc(Trunc) {}
915   ~VPWidenIntOrFpInductionRecipe() override = default;
916 
917   /// Method to support type inquiry through isa, cast, and dyn_cast.
918   static inline bool classof(const VPRecipeBase *V) {
919     return V->getVPRecipeID() == VPRecipeBase::VPWidenIntOrFpInductionSC;
920   }
921 
922   /// Generate the vectorized and scalarized versions of the phi node as
923   /// needed by their users.
924   void execute(VPTransformState &State) override;
925 
926   /// Print the recipe.
927   void print(raw_ostream &O, const Twine &Indent,
928              VPSlotTracker &SlotTracker) const override;
929 };
930 
931 /// A recipe for handling all phi nodes except for integer and FP inductions.
932 class VPWidenPHIRecipe : public VPRecipeBase {
933   PHINode *Phi;
934 
935 public:
936   VPWidenPHIRecipe(PHINode *Phi) : VPRecipeBase(VPWidenPHISC), Phi(Phi) {}
937   ~VPWidenPHIRecipe() override = default;
938 
939   /// Method to support type inquiry through isa, cast, and dyn_cast.
940   static inline bool classof(const VPRecipeBase *V) {
941     return V->getVPRecipeID() == VPRecipeBase::VPWidenPHISC;
942   }
943 
944   /// Generate the phi/select nodes.
945   void execute(VPTransformState &State) override;
946 
947   /// Print the recipe.
948   void print(raw_ostream &O, const Twine &Indent,
949              VPSlotTracker &SlotTracker) const override;
950 };
951 
952 /// A recipe for vectorizing a phi-node as a sequence of mask-based select
953 /// instructions.
954 class VPBlendRecipe : public VPRecipeBase {
955   PHINode *Phi;
956 
957   /// The blend operation is a User of the incoming values and of their
958   /// respective masks, ordered [I0, M0, I1, M1, ...]. Note that a single value
959   /// might be incoming with a full mask for which there is no VPValue.
960   VPUser User;
961 
962 public:
963   VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Operands)
964       : VPRecipeBase(VPBlendSC), Phi(Phi), User(Operands) {
965     assert(Operands.size() > 0 &&
966            ((Operands.size() == 1) || (Operands.size() % 2 == 0)) &&
967            "Expected either a single incoming value or a positive even number "
968            "of operands");
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::VPBlendSC;
974   }
975 
976   /// Return the number of incoming values, taking into account that a single
977   /// incoming value has no mask.
978   unsigned getNumIncomingValues() const {
979     return (User.getNumOperands() + 1) / 2;
980   }
981 
982   /// Return incoming value number \p Idx.
983   VPValue *getIncomingValue(unsigned Idx) const {
984     return User.getOperand(Idx * 2);
985   }
986 
987   /// Return mask number \p Idx.
988   VPValue *getMask(unsigned Idx) const { return User.getOperand(Idx * 2 + 1); }
989 
990   /// Generate the phi/select nodes.
991   void execute(VPTransformState &State) override;
992 
993   /// Print the recipe.
994   void print(raw_ostream &O, const Twine &Indent,
995              VPSlotTracker &SlotTracker) const override;
996 };
997 
998 /// VPInterleaveRecipe is a recipe for transforming an interleave group of load
999 /// or stores into one wide load/store and shuffles.
1000 class VPInterleaveRecipe : public VPRecipeBase {
1001   const InterleaveGroup<Instruction> *IG;
1002   VPUser User;
1003 
1004 public:
1005   VPInterleaveRecipe(const InterleaveGroup<Instruction> *IG, VPValue *Addr,
1006                      VPValue *Mask)
1007       : VPRecipeBase(VPInterleaveSC), IG(IG), User({Addr}) {
1008     if (Mask)
1009       User.addOperand(Mask);
1010   }
1011   ~VPInterleaveRecipe() override = default;
1012 
1013   /// Method to support type inquiry through isa, cast, and dyn_cast.
1014   static inline bool classof(const VPRecipeBase *V) {
1015     return V->getVPRecipeID() == VPRecipeBase::VPInterleaveSC;
1016   }
1017 
1018   /// Return the address accessed by this recipe.
1019   VPValue *getAddr() const {
1020     return User.getOperand(0); // Address is the 1st, mandatory operand.
1021   }
1022 
1023   /// Return the mask used by this recipe. Note that a full mask is represented
1024   /// by a nullptr.
1025   VPValue *getMask() const {
1026     // Mask is optional and therefore the last, currently 2nd operand.
1027     return User.getNumOperands() == 2 ? User.getOperand(1) : nullptr;
1028   }
1029 
1030   /// Generate the wide load or store, and shuffles.
1031   void execute(VPTransformState &State) override;
1032 
1033   /// Print the recipe.
1034   void print(raw_ostream &O, const Twine &Indent,
1035              VPSlotTracker &SlotTracker) const override;
1036 
1037   const InterleaveGroup<Instruction> *getInterleaveGroup() { return IG; }
1038 };
1039 
1040 /// A recipe to represent inloop reduction operations, performing a reduction on
1041 /// a vector operand into a scalar value, and adding the result to a chain.
1042 class VPReductionRecipe : public VPRecipeBase {
1043   /// The recurrence decriptor for the reduction in question.
1044   RecurrenceDescriptor *RdxDesc;
1045   /// The original instruction being converted to a reduction.
1046   Instruction *I;
1047   /// The VPValue of the vector value to be reduced.
1048   VPValue *VecOp;
1049   /// The VPValue of the scalar Chain being accumulated.
1050   VPValue *ChainOp;
1051   /// Fast math flags to use for the resulting reduction operation.
1052   bool NoNaN;
1053   /// Pointer to the TTI, needed to create the target reduction
1054   const TargetTransformInfo *TTI;
1055 
1056 public:
1057   VPReductionRecipe(RecurrenceDescriptor *R, Instruction *I, VPValue *ChainOp,
1058                     VPValue *VecOp, bool NoNaN, const TargetTransformInfo *TTI)
1059       : VPRecipeBase(VPReductionSC), RdxDesc(R), I(I), VecOp(VecOp),
1060         ChainOp(ChainOp), NoNaN(NoNaN), TTI(TTI) {}
1061 
1062   ~VPReductionRecipe() override = default;
1063 
1064   /// Method to support type inquiry through isa, cast, and dyn_cast.
1065   static inline bool classof(const VPRecipeBase *V) {
1066     return V->getVPRecipeID() == VPRecipeBase::VPReductionSC;
1067   }
1068 
1069   /// Generate the reduction in the loop
1070   void execute(VPTransformState &State) override;
1071 
1072   /// Print the recipe.
1073   void print(raw_ostream &O, const Twine &Indent,
1074              VPSlotTracker &SlotTracker) const override;
1075 };
1076 
1077 /// VPReplicateRecipe replicates a given instruction producing multiple scalar
1078 /// copies of the original scalar type, one per lane, instead of producing a
1079 /// single copy of widened type for all lanes. If the instruction is known to be
1080 /// uniform only one copy, per lane zero, will be generated.
1081 class VPReplicateRecipe : public VPRecipeBase {
1082   /// The instruction being replicated.
1083   Instruction *Ingredient;
1084 
1085   /// Hold VPValues for the operands of the ingredient.
1086   VPUser User;
1087 
1088   /// Indicator if only a single replica per lane is needed.
1089   bool IsUniform;
1090 
1091   /// Indicator if the replicas are also predicated.
1092   bool IsPredicated;
1093 
1094   /// Indicator if the scalar values should also be packed into a vector.
1095   bool AlsoPack;
1096 
1097 public:
1098   template <typename IterT>
1099   VPReplicateRecipe(Instruction *I, iterator_range<IterT> Operands,
1100                     bool IsUniform, bool IsPredicated = false)
1101       : VPRecipeBase(VPReplicateSC), Ingredient(I), User(Operands),
1102         IsUniform(IsUniform), IsPredicated(IsPredicated) {
1103     // Retain the previous behavior of predicateInstructions(), where an
1104     // insert-element of a predicated instruction got hoisted into the
1105     // predicated basic block iff it was its only user. This is achieved by
1106     // having predicated instructions also pack their values into a vector by
1107     // default unless they have a replicated user which uses their scalar value.
1108     AlsoPack = IsPredicated && !I->use_empty();
1109   }
1110 
1111   ~VPReplicateRecipe() override = default;
1112 
1113   /// Method to support type inquiry through isa, cast, and dyn_cast.
1114   static inline bool classof(const VPRecipeBase *V) {
1115     return V->getVPRecipeID() == VPRecipeBase::VPReplicateSC;
1116   }
1117 
1118   /// Generate replicas of the desired Ingredient. Replicas will be generated
1119   /// for all parts and lanes unless a specific part and lane are specified in
1120   /// the \p State.
1121   void execute(VPTransformState &State) override;
1122 
1123   void setAlsoPack(bool Pack) { AlsoPack = Pack; }
1124 
1125   /// Print the recipe.
1126   void print(raw_ostream &O, const Twine &Indent,
1127              VPSlotTracker &SlotTracker) const override;
1128 };
1129 
1130 /// A recipe for generating conditional branches on the bits of a mask.
1131 class VPBranchOnMaskRecipe : public VPRecipeBase {
1132   VPUser User;
1133 
1134 public:
1135   VPBranchOnMaskRecipe(VPValue *BlockInMask) : VPRecipeBase(VPBranchOnMaskSC) {
1136     if (BlockInMask) // nullptr means all-one mask.
1137       User.addOperand(BlockInMask);
1138   }
1139 
1140   /// Method to support type inquiry through isa, cast, and dyn_cast.
1141   static inline bool classof(const VPRecipeBase *V) {
1142     return V->getVPRecipeID() == VPRecipeBase::VPBranchOnMaskSC;
1143   }
1144 
1145   /// Generate the extraction of the appropriate bit from the block mask and the
1146   /// conditional branch.
1147   void execute(VPTransformState &State) override;
1148 
1149   /// Print the recipe.
1150   void print(raw_ostream &O, const Twine &Indent,
1151              VPSlotTracker &SlotTracker) const override {
1152     O << " +\n" << Indent << "\"BRANCH-ON-MASK ";
1153     if (VPValue *Mask = getMask())
1154       Mask->print(O, SlotTracker);
1155     else
1156       O << " All-One";
1157     O << "\\l\"";
1158   }
1159 
1160   /// Return the mask used by this recipe. Note that a full mask is represented
1161   /// by a nullptr.
1162   VPValue *getMask() const {
1163     assert(User.getNumOperands() <= 1 && "should have either 0 or 1 operands");
1164     // Mask is optional.
1165     return User.getNumOperands() == 1 ? User.getOperand(0) : nullptr;
1166   }
1167 };
1168 
1169 /// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
1170 /// control converges back from a Branch-on-Mask. The phi nodes are needed in
1171 /// order to merge values that are set under such a branch and feed their uses.
1172 /// The phi nodes can be scalar or vector depending on the users of the value.
1173 /// This recipe works in concert with VPBranchOnMaskRecipe.
1174 class VPPredInstPHIRecipe : public VPRecipeBase {
1175   Instruction *PredInst;
1176 
1177 public:
1178   /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
1179   /// nodes after merging back from a Branch-on-Mask.
1180   VPPredInstPHIRecipe(Instruction *PredInst)
1181       : VPRecipeBase(VPPredInstPHISC), PredInst(PredInst) {}
1182   ~VPPredInstPHIRecipe() override = default;
1183 
1184   /// Method to support type inquiry through isa, cast, and dyn_cast.
1185   static inline bool classof(const VPRecipeBase *V) {
1186     return V->getVPRecipeID() == VPRecipeBase::VPPredInstPHISC;
1187   }
1188 
1189   /// Generates phi nodes for live-outs as needed to retain SSA form.
1190   void execute(VPTransformState &State) override;
1191 
1192   /// Print the recipe.
1193   void print(raw_ostream &O, const Twine &Indent,
1194              VPSlotTracker &SlotTracker) const override;
1195 };
1196 
1197 /// A Recipe for widening load/store operations.
1198 /// The recipe uses the following VPValues:
1199 /// - For load: Address, optional mask
1200 /// - For store: Address, stored value, optional mask
1201 /// TODO: We currently execute only per-part unless a specific instance is
1202 /// provided.
1203 class VPWidenMemoryInstructionRecipe : public VPRecipeBase {
1204   Instruction &Instr;
1205   VPUser User;
1206 
1207   void setMask(VPValue *Mask) {
1208     if (!Mask)
1209       return;
1210     User.addOperand(Mask);
1211   }
1212 
1213   bool isMasked() const {
1214     return (isa<LoadInst>(Instr) && User.getNumOperands() == 2) ||
1215            (isa<StoreInst>(Instr) && User.getNumOperands() == 3);
1216   }
1217 
1218 public:
1219   VPWidenMemoryInstructionRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask)
1220       : VPRecipeBase(VPWidenMemoryInstructionSC), Instr(Load), User({Addr}) {
1221     setMask(Mask);
1222   }
1223 
1224   VPWidenMemoryInstructionRecipe(StoreInst &Store, VPValue *Addr,
1225                                  VPValue *StoredValue, VPValue *Mask)
1226       : VPRecipeBase(VPWidenMemoryInstructionSC), Instr(Store),
1227         User({Addr, StoredValue}) {
1228     setMask(Mask);
1229   }
1230 
1231   /// Method to support type inquiry through isa, cast, and dyn_cast.
1232   static inline bool classof(const VPRecipeBase *V) {
1233     return V->getVPRecipeID() == VPRecipeBase::VPWidenMemoryInstructionSC;
1234   }
1235 
1236   /// Return the address accessed by this recipe.
1237   VPValue *getAddr() const {
1238     return User.getOperand(0); // Address is the 1st, mandatory operand.
1239   }
1240 
1241   /// Return the mask used by this recipe. Note that a full mask is represented
1242   /// by a nullptr.
1243   VPValue *getMask() const {
1244     // Mask is optional and therefore the last operand.
1245     return isMasked() ? User.getOperand(User.getNumOperands() - 1) : nullptr;
1246   }
1247 
1248   /// Return the address accessed by this recipe.
1249   VPValue *getStoredValue() const {
1250     assert(isa<StoreInst>(Instr) &&
1251            "Stored value only available for store instructions");
1252     return User.getOperand(1); // Stored value is the 2nd, mandatory operand.
1253   }
1254 
1255   /// Generate the wide load/store.
1256   void execute(VPTransformState &State) override;
1257 
1258   /// Print the recipe.
1259   void print(raw_ostream &O, const Twine &Indent,
1260              VPSlotTracker &SlotTracker) const override;
1261 };
1262 
1263 /// A Recipe for widening the canonical induction variable of the vector loop.
1264 class VPWidenCanonicalIVRecipe : public VPRecipeBase {
1265   /// A VPValue representing the canonical vector IV.
1266   VPValue Val;
1267 
1268 public:
1269   VPWidenCanonicalIVRecipe() : VPRecipeBase(VPWidenCanonicalIVSC) {}
1270   ~VPWidenCanonicalIVRecipe() override = default;
1271 
1272   /// Return the VPValue representing the canonical vector induction variable of
1273   /// the vector loop.
1274   const VPValue *getVPValue() const { return &Val; }
1275   VPValue *getVPValue() { return &Val; }
1276 
1277   /// Method to support type inquiry through isa, cast, and dyn_cast.
1278   static inline bool classof(const VPRecipeBase *V) {
1279     return V->getVPRecipeID() == VPRecipeBase::VPWidenCanonicalIVSC;
1280   }
1281 
1282   /// Generate a canonical vector induction variable of the vector loop, with
1283   /// start = {<Part*VF, Part*VF+1, ..., Part*VF+VF-1> for 0 <= Part < UF}, and
1284   /// step = <VF*UF, VF*UF, ..., VF*UF>.
1285   void execute(VPTransformState &State) override;
1286 
1287   /// Print the recipe.
1288   void print(raw_ostream &O, const Twine &Indent,
1289              VPSlotTracker &SlotTracker) const override;
1290 };
1291 
1292 /// VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph. It
1293 /// holds a sequence of zero or more VPRecipe's each representing a sequence of
1294 /// output IR instructions.
1295 class VPBasicBlock : public VPBlockBase {
1296 public:
1297   using RecipeListTy = iplist<VPRecipeBase>;
1298 
1299 private:
1300   /// The VPRecipes held in the order of output instructions to generate.
1301   RecipeListTy Recipes;
1302 
1303 public:
1304   VPBasicBlock(const Twine &Name = "", VPRecipeBase *Recipe = nullptr)
1305       : VPBlockBase(VPBasicBlockSC, Name.str()) {
1306     if (Recipe)
1307       appendRecipe(Recipe);
1308   }
1309 
1310   ~VPBasicBlock() override { Recipes.clear(); }
1311 
1312   /// Instruction iterators...
1313   using iterator = RecipeListTy::iterator;
1314   using const_iterator = RecipeListTy::const_iterator;
1315   using reverse_iterator = RecipeListTy::reverse_iterator;
1316   using const_reverse_iterator = RecipeListTy::const_reverse_iterator;
1317 
1318   //===--------------------------------------------------------------------===//
1319   /// Recipe iterator methods
1320   ///
1321   inline iterator begin() { return Recipes.begin(); }
1322   inline const_iterator begin() const { return Recipes.begin(); }
1323   inline iterator end() { return Recipes.end(); }
1324   inline const_iterator end() const { return Recipes.end(); }
1325 
1326   inline reverse_iterator rbegin() { return Recipes.rbegin(); }
1327   inline const_reverse_iterator rbegin() const { return Recipes.rbegin(); }
1328   inline reverse_iterator rend() { return Recipes.rend(); }
1329   inline const_reverse_iterator rend() const { return Recipes.rend(); }
1330 
1331   inline size_t size() const { return Recipes.size(); }
1332   inline bool empty() const { return Recipes.empty(); }
1333   inline const VPRecipeBase &front() const { return Recipes.front(); }
1334   inline VPRecipeBase &front() { return Recipes.front(); }
1335   inline const VPRecipeBase &back() const { return Recipes.back(); }
1336   inline VPRecipeBase &back() { return Recipes.back(); }
1337 
1338   /// Returns a reference to the list of recipes.
1339   RecipeListTy &getRecipeList() { return Recipes; }
1340 
1341   /// Returns a pointer to a member of the recipe list.
1342   static RecipeListTy VPBasicBlock::*getSublistAccess(VPRecipeBase *) {
1343     return &VPBasicBlock::Recipes;
1344   }
1345 
1346   /// Method to support type inquiry through isa, cast, and dyn_cast.
1347   static inline bool classof(const VPBlockBase *V) {
1348     return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC;
1349   }
1350 
1351   void insert(VPRecipeBase *Recipe, iterator InsertPt) {
1352     assert(Recipe && "No recipe to append.");
1353     assert(!Recipe->Parent && "Recipe already in VPlan");
1354     Recipe->Parent = this;
1355     Recipes.insert(InsertPt, Recipe);
1356   }
1357 
1358   /// Augment the existing recipes of a VPBasicBlock with an additional
1359   /// \p Recipe as the last recipe.
1360   void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); }
1361 
1362   /// The method which generates the output IR instructions that correspond to
1363   /// this VPBasicBlock, thereby "executing" the VPlan.
1364   void execute(struct VPTransformState *State) override;
1365 
1366 private:
1367   /// Create an IR BasicBlock to hold the output instructions generated by this
1368   /// VPBasicBlock, and return it. Update the CFGState accordingly.
1369   BasicBlock *createEmptyBasicBlock(VPTransformState::CFGState &CFG);
1370 };
1371 
1372 /// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks
1373 /// which form a Single-Entry-Single-Exit subgraph of the output IR CFG.
1374 /// A VPRegionBlock may indicate that its contents are to be replicated several
1375 /// times. This is designed to support predicated scalarization, in which a
1376 /// scalar if-then code structure needs to be generated VF * UF times. Having
1377 /// this replication indicator helps to keep a single model for multiple
1378 /// candidate VF's. The actual replication takes place only once the desired VF
1379 /// and UF have been determined.
1380 class VPRegionBlock : public VPBlockBase {
1381   /// Hold the Single Entry of the SESE region modelled by the VPRegionBlock.
1382   VPBlockBase *Entry;
1383 
1384   /// Hold the Single Exit of the SESE region modelled by the VPRegionBlock.
1385   VPBlockBase *Exit;
1386 
1387   /// An indicator whether this region is to generate multiple replicated
1388   /// instances of output IR corresponding to its VPBlockBases.
1389   bool IsReplicator;
1390 
1391 public:
1392   VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exit,
1393                 const std::string &Name = "", bool IsReplicator = false)
1394       : VPBlockBase(VPRegionBlockSC, Name), Entry(Entry), Exit(Exit),
1395         IsReplicator(IsReplicator) {
1396     assert(Entry->getPredecessors().empty() && "Entry block has predecessors.");
1397     assert(Exit->getSuccessors().empty() && "Exit block has successors.");
1398     Entry->setParent(this);
1399     Exit->setParent(this);
1400   }
1401   VPRegionBlock(const std::string &Name = "", bool IsReplicator = false)
1402       : VPBlockBase(VPRegionBlockSC, Name), Entry(nullptr), Exit(nullptr),
1403         IsReplicator(IsReplicator) {}
1404 
1405   ~VPRegionBlock() override {
1406     if (Entry)
1407       deleteCFG(Entry);
1408   }
1409 
1410   /// Method to support type inquiry through isa, cast, and dyn_cast.
1411   static inline bool classof(const VPBlockBase *V) {
1412     return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC;
1413   }
1414 
1415   const VPBlockBase *getEntry() const { return Entry; }
1416   VPBlockBase *getEntry() { return Entry; }
1417 
1418   /// Set \p EntryBlock as the entry VPBlockBase of this VPRegionBlock. \p
1419   /// EntryBlock must have no predecessors.
1420   void setEntry(VPBlockBase *EntryBlock) {
1421     assert(EntryBlock->getPredecessors().empty() &&
1422            "Entry block cannot have predecessors.");
1423     Entry = EntryBlock;
1424     EntryBlock->setParent(this);
1425   }
1426 
1427   // FIXME: DominatorTreeBase is doing 'A->getParent()->front()'. 'front' is a
1428   // specific interface of llvm::Function, instead of using
1429   // GraphTraints::getEntryNode. We should add a new template parameter to
1430   // DominatorTreeBase representing the Graph type.
1431   VPBlockBase &front() const { return *Entry; }
1432 
1433   const VPBlockBase *getExit() const { return Exit; }
1434   VPBlockBase *getExit() { return Exit; }
1435 
1436   /// Set \p ExitBlock as the exit VPBlockBase of this VPRegionBlock. \p
1437   /// ExitBlock must have no successors.
1438   void setExit(VPBlockBase *ExitBlock) {
1439     assert(ExitBlock->getSuccessors().empty() &&
1440            "Exit block cannot have successors.");
1441     Exit = ExitBlock;
1442     ExitBlock->setParent(this);
1443   }
1444 
1445   /// An indicator whether this region is to generate multiple replicated
1446   /// instances of output IR corresponding to its VPBlockBases.
1447   bool isReplicator() const { return IsReplicator; }
1448 
1449   /// The method which generates the output IR instructions that correspond to
1450   /// this VPRegionBlock, thereby "executing" the VPlan.
1451   void execute(struct VPTransformState *State) override;
1452 };
1453 
1454 //===----------------------------------------------------------------------===//
1455 // GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs     //
1456 //===----------------------------------------------------------------------===//
1457 
1458 // The following set of template specializations implement GraphTraits to treat
1459 // any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
1460 // that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
1461 // VPBlockBase is a VPRegionBlock, this specialization provides access to its
1462 // successors/predecessors but not to the blocks inside the region.
1463 
1464 template <> struct GraphTraits<VPBlockBase *> {
1465   using NodeRef = VPBlockBase *;
1466   using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
1467 
1468   static NodeRef getEntryNode(NodeRef N) { return N; }
1469 
1470   static inline ChildIteratorType child_begin(NodeRef N) {
1471     return N->getSuccessors().begin();
1472   }
1473 
1474   static inline ChildIteratorType child_end(NodeRef N) {
1475     return N->getSuccessors().end();
1476   }
1477 };
1478 
1479 template <> struct GraphTraits<const VPBlockBase *> {
1480   using NodeRef = const VPBlockBase *;
1481   using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::const_iterator;
1482 
1483   static NodeRef getEntryNode(NodeRef N) { return N; }
1484 
1485   static inline ChildIteratorType child_begin(NodeRef N) {
1486     return N->getSuccessors().begin();
1487   }
1488 
1489   static inline ChildIteratorType child_end(NodeRef N) {
1490     return N->getSuccessors().end();
1491   }
1492 };
1493 
1494 // Inverse order specialization for VPBasicBlocks. Predecessors are used instead
1495 // of successors for the inverse traversal.
1496 template <> struct GraphTraits<Inverse<VPBlockBase *>> {
1497   using NodeRef = VPBlockBase *;
1498   using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
1499 
1500   static NodeRef getEntryNode(Inverse<NodeRef> B) { return B.Graph; }
1501 
1502   static inline ChildIteratorType child_begin(NodeRef N) {
1503     return N->getPredecessors().begin();
1504   }
1505 
1506   static inline ChildIteratorType child_end(NodeRef N) {
1507     return N->getPredecessors().end();
1508   }
1509 };
1510 
1511 // The following set of template specializations implement GraphTraits to
1512 // treat VPRegionBlock as a graph and recurse inside its nodes. It's important
1513 // to note that the blocks inside the VPRegionBlock are treated as VPBlockBases
1514 // (i.e., no dyn_cast is performed, VPBlockBases specialization is used), so
1515 // there won't be automatic recursion into other VPBlockBases that turn to be
1516 // VPRegionBlocks.
1517 
1518 template <>
1519 struct GraphTraits<VPRegionBlock *> : public GraphTraits<VPBlockBase *> {
1520   using GraphRef = VPRegionBlock *;
1521   using nodes_iterator = df_iterator<NodeRef>;
1522 
1523   static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
1524 
1525   static nodes_iterator nodes_begin(GraphRef N) {
1526     return nodes_iterator::begin(N->getEntry());
1527   }
1528 
1529   static nodes_iterator nodes_end(GraphRef N) {
1530     // df_iterator::end() returns an empty iterator so the node used doesn't
1531     // matter.
1532     return nodes_iterator::end(N);
1533   }
1534 };
1535 
1536 template <>
1537 struct GraphTraits<const VPRegionBlock *>
1538     : public GraphTraits<const VPBlockBase *> {
1539   using GraphRef = const VPRegionBlock *;
1540   using nodes_iterator = df_iterator<NodeRef>;
1541 
1542   static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
1543 
1544   static nodes_iterator nodes_begin(GraphRef N) {
1545     return nodes_iterator::begin(N->getEntry());
1546   }
1547 
1548   static nodes_iterator nodes_end(GraphRef N) {
1549     // df_iterator::end() returns an empty iterator so the node used doesn't
1550     // matter.
1551     return nodes_iterator::end(N);
1552   }
1553 };
1554 
1555 template <>
1556 struct GraphTraits<Inverse<VPRegionBlock *>>
1557     : public GraphTraits<Inverse<VPBlockBase *>> {
1558   using GraphRef = VPRegionBlock *;
1559   using nodes_iterator = df_iterator<NodeRef>;
1560 
1561   static NodeRef getEntryNode(Inverse<GraphRef> N) {
1562     return N.Graph->getExit();
1563   }
1564 
1565   static nodes_iterator nodes_begin(GraphRef N) {
1566     return nodes_iterator::begin(N->getExit());
1567   }
1568 
1569   static nodes_iterator nodes_end(GraphRef N) {
1570     // df_iterator::end() returns an empty iterator so the node used doesn't
1571     // matter.
1572     return nodes_iterator::end(N);
1573   }
1574 };
1575 
1576 /// VPlan models a candidate for vectorization, encoding various decisions take
1577 /// to produce efficient output IR, including which branches, basic-blocks and
1578 /// output IR instructions to generate, and their cost. VPlan holds a
1579 /// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry
1580 /// VPBlock.
1581 class VPlan {
1582   friend class VPlanPrinter;
1583   friend class VPSlotTracker;
1584 
1585   /// Hold the single entry to the Hierarchical CFG of the VPlan.
1586   VPBlockBase *Entry;
1587 
1588   /// Holds the VFs applicable to this VPlan.
1589   SmallSetVector<ElementCount, 2> VFs;
1590 
1591   /// Holds the name of the VPlan, for printing.
1592   std::string Name;
1593 
1594   /// Holds all the external definitions created for this VPlan.
1595   // TODO: Introduce a specific representation for external definitions in
1596   // VPlan. External definitions must be immutable and hold a pointer to its
1597   // underlying IR that will be used to implement its structural comparison
1598   // (operators '==' and '<').
1599   SmallPtrSet<VPValue *, 16> VPExternalDefs;
1600 
1601   /// Represents the backedge taken count of the original loop, for folding
1602   /// the tail.
1603   VPValue *BackedgeTakenCount = nullptr;
1604 
1605   /// Holds a mapping between Values and their corresponding VPValue inside
1606   /// VPlan.
1607   Value2VPValueTy Value2VPValue;
1608 
1609   /// Holds the VPLoopInfo analysis for this VPlan.
1610   VPLoopInfo VPLInfo;
1611 
1612   /// Holds the condition bit values built during VPInstruction to VPRecipe transformation.
1613   SmallVector<VPValue *, 4> VPCBVs;
1614 
1615 public:
1616   VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {
1617     if (Entry)
1618       Entry->setPlan(this);
1619   }
1620 
1621   ~VPlan() {
1622     if (Entry)
1623       VPBlockBase::deleteCFG(Entry);
1624     for (auto &MapEntry : Value2VPValue)
1625       delete MapEntry.second;
1626     if (BackedgeTakenCount)
1627       delete BackedgeTakenCount;
1628     for (VPValue *Def : VPExternalDefs)
1629       delete Def;
1630     for (VPValue *CBV : VPCBVs)
1631       delete CBV;
1632   }
1633 
1634   /// Generate the IR code for this VPlan.
1635   void execute(struct VPTransformState *State);
1636 
1637   VPBlockBase *getEntry() { return Entry; }
1638   const VPBlockBase *getEntry() const { return Entry; }
1639 
1640   VPBlockBase *setEntry(VPBlockBase *Block) {
1641     Entry = Block;
1642     Block->setPlan(this);
1643     return Entry;
1644   }
1645 
1646   /// The backedge taken count of the original loop.
1647   VPValue *getOrCreateBackedgeTakenCount() {
1648     if (!BackedgeTakenCount)
1649       BackedgeTakenCount = new VPValue();
1650     return BackedgeTakenCount;
1651   }
1652 
1653   void addVF(ElementCount VF) { VFs.insert(VF); }
1654 
1655   bool hasVF(ElementCount VF) { return VFs.count(VF); }
1656 
1657   const std::string &getName() const { return Name; }
1658 
1659   void setName(const Twine &newName) { Name = newName.str(); }
1660 
1661   /// Add \p VPVal to the pool of external definitions if it's not already
1662   /// in the pool.
1663   void addExternalDef(VPValue *VPVal) {
1664     VPExternalDefs.insert(VPVal);
1665   }
1666 
1667   /// Add \p CBV to the vector of condition bit values.
1668   void addCBV(VPValue *CBV) {
1669     VPCBVs.push_back(CBV);
1670   }
1671 
1672   void addVPValue(Value *V) {
1673     assert(V && "Trying to add a null Value to VPlan");
1674     assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
1675     Value2VPValue[V] = new VPValue(V);
1676   }
1677 
1678   VPValue *getVPValue(Value *V) {
1679     assert(V && "Trying to get the VPValue of a null Value");
1680     assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
1681     return Value2VPValue[V];
1682   }
1683 
1684   VPValue *getOrAddVPValue(Value *V) {
1685     assert(V && "Trying to get or add the VPValue of a null Value");
1686     if (!Value2VPValue.count(V))
1687       addVPValue(V);
1688     return getVPValue(V);
1689   }
1690 
1691   /// Return the VPLoopInfo analysis for this VPlan.
1692   VPLoopInfo &getVPLoopInfo() { return VPLInfo; }
1693   const VPLoopInfo &getVPLoopInfo() const { return VPLInfo; }
1694 
1695   /// Dump the plan to stderr (for debugging).
1696   void dump() const;
1697 
1698   /// Returns a range mapping the values the range \p Operands to their
1699   /// corresponding VPValues.
1700   iterator_range<mapped_iterator<Use *, std::function<VPValue *(Value *)>>>
1701   mapToVPValues(User::op_range Operands) {
1702     std::function<VPValue *(Value *)> Fn = [this](Value *Op) {
1703       return getOrAddVPValue(Op);
1704     };
1705     return map_range(Operands, Fn);
1706   }
1707 
1708 private:
1709   /// Add to the given dominator tree the header block and every new basic block
1710   /// that was created between it and the latch block, inclusive.
1711   static void updateDominatorTree(DominatorTree *DT, BasicBlock *LoopLatchBB,
1712                                   BasicBlock *LoopPreHeaderBB,
1713                                   BasicBlock *LoopExitBB);
1714 };
1715 
1716 /// VPlanPrinter prints a given VPlan to a given output stream. The printing is
1717 /// indented and follows the dot format.
1718 class VPlanPrinter {
1719   friend inline raw_ostream &operator<<(raw_ostream &OS, const VPlan &Plan);
1720   friend inline raw_ostream &operator<<(raw_ostream &OS,
1721                                         const struct VPlanIngredient &I);
1722 
1723 private:
1724   raw_ostream &OS;
1725   const VPlan &Plan;
1726   unsigned Depth = 0;
1727   unsigned TabWidth = 2;
1728   std::string Indent;
1729   unsigned BID = 0;
1730   SmallDenseMap<const VPBlockBase *, unsigned> BlockID;
1731 
1732   VPSlotTracker SlotTracker;
1733 
1734   VPlanPrinter(raw_ostream &O, const VPlan &P)
1735       : OS(O), Plan(P), SlotTracker(&P) {}
1736 
1737   /// Handle indentation.
1738   void bumpIndent(int b) { Indent = std::string((Depth += b) * TabWidth, ' '); }
1739 
1740   /// Print a given \p Block of the Plan.
1741   void dumpBlock(const VPBlockBase *Block);
1742 
1743   /// Print the information related to the CFG edges going out of a given
1744   /// \p Block, followed by printing the successor blocks themselves.
1745   void dumpEdges(const VPBlockBase *Block);
1746 
1747   /// Print a given \p BasicBlock, including its VPRecipes, followed by printing
1748   /// its successor blocks.
1749   void dumpBasicBlock(const VPBasicBlock *BasicBlock);
1750 
1751   /// Print a given \p Region of the Plan.
1752   void dumpRegion(const VPRegionBlock *Region);
1753 
1754   unsigned getOrCreateBID(const VPBlockBase *Block) {
1755     return BlockID.count(Block) ? BlockID[Block] : BlockID[Block] = BID++;
1756   }
1757 
1758   const Twine getOrCreateName(const VPBlockBase *Block);
1759 
1760   const Twine getUID(const VPBlockBase *Block);
1761 
1762   /// Print the information related to a CFG edge between two VPBlockBases.
1763   void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden,
1764                 const Twine &Label);
1765 
1766   void dump();
1767 
1768   static void printAsIngredient(raw_ostream &O, Value *V);
1769 };
1770 
1771 struct VPlanIngredient {
1772   Value *V;
1773 
1774   VPlanIngredient(Value *V) : V(V) {}
1775 };
1776 
1777 inline raw_ostream &operator<<(raw_ostream &OS, const VPlanIngredient &I) {
1778   VPlanPrinter::printAsIngredient(OS, I.V);
1779   return OS;
1780 }
1781 
1782 inline raw_ostream &operator<<(raw_ostream &OS, const VPlan &Plan) {
1783   VPlanPrinter Printer(OS, Plan);
1784   Printer.dump();
1785   return OS;
1786 }
1787 
1788 //===----------------------------------------------------------------------===//
1789 // VPlan Utilities
1790 //===----------------------------------------------------------------------===//
1791 
1792 /// Class that provides utilities for VPBlockBases in VPlan.
1793 class VPBlockUtils {
1794 public:
1795   VPBlockUtils() = delete;
1796 
1797   /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
1798   /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
1799   /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. If \p BlockPtr
1800   /// has more than one successor, its conditional bit is propagated to \p
1801   /// NewBlock. \p NewBlock must have neither successors nor predecessors.
1802   static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
1803     assert(NewBlock->getSuccessors().empty() &&
1804            "Can't insert new block with successors.");
1805     // TODO: move successors from BlockPtr to NewBlock when this functionality
1806     // is necessary. For now, setBlockSingleSuccessor will assert if BlockPtr
1807     // already has successors.
1808     BlockPtr->setOneSuccessor(NewBlock);
1809     NewBlock->setPredecessors({BlockPtr});
1810     NewBlock->setParent(BlockPtr->getParent());
1811   }
1812 
1813   /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
1814   /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
1815   /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
1816   /// parent to \p IfTrue and \p IfFalse. \p Condition is set as the successor
1817   /// selector. \p BlockPtr must have no successors and \p IfTrue and \p IfFalse
1818   /// must have neither successors nor predecessors.
1819   static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
1820                                    VPValue *Condition, VPBlockBase *BlockPtr) {
1821     assert(IfTrue->getSuccessors().empty() &&
1822            "Can't insert IfTrue with successors.");
1823     assert(IfFalse->getSuccessors().empty() &&
1824            "Can't insert IfFalse with successors.");
1825     BlockPtr->setTwoSuccessors(IfTrue, IfFalse, Condition);
1826     IfTrue->setPredecessors({BlockPtr});
1827     IfFalse->setPredecessors({BlockPtr});
1828     IfTrue->setParent(BlockPtr->getParent());
1829     IfFalse->setParent(BlockPtr->getParent());
1830   }
1831 
1832   /// Connect VPBlockBases \p From and \p To bi-directionally. Append \p To to
1833   /// the successors of \p From and \p From to the predecessors of \p To. Both
1834   /// VPBlockBases must have the same parent, which can be null. Both
1835   /// VPBlockBases can be already connected to other VPBlockBases.
1836   static void connectBlocks(VPBlockBase *From, VPBlockBase *To) {
1837     assert((From->getParent() == To->getParent()) &&
1838            "Can't connect two block with different parents");
1839     assert(From->getNumSuccessors() < 2 &&
1840            "Blocks can't have more than two successors.");
1841     From->appendSuccessor(To);
1842     To->appendPredecessor(From);
1843   }
1844 
1845   /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
1846   /// from the successors of \p From and \p From from the predecessors of \p To.
1847   static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
1848     assert(To && "Successor to disconnect is null.");
1849     From->removeSuccessor(To);
1850     To->removePredecessor(From);
1851   }
1852 
1853   /// Returns true if the edge \p FromBlock -> \p ToBlock is a back-edge.
1854   static bool isBackEdge(const VPBlockBase *FromBlock,
1855                          const VPBlockBase *ToBlock, const VPLoopInfo *VPLI) {
1856     assert(FromBlock->getParent() == ToBlock->getParent() &&
1857            FromBlock->getParent() && "Must be in same region");
1858     const VPLoop *FromLoop = VPLI->getLoopFor(FromBlock);
1859     const VPLoop *ToLoop = VPLI->getLoopFor(ToBlock);
1860     if (!FromLoop || !ToLoop || FromLoop != ToLoop)
1861       return false;
1862 
1863     // A back-edge is a branch from the loop latch to its header.
1864     return ToLoop->isLoopLatch(FromBlock) && ToBlock == ToLoop->getHeader();
1865   }
1866 
1867   /// Returns true if \p Block is a loop latch
1868   static bool blockIsLoopLatch(const VPBlockBase *Block,
1869                                const VPLoopInfo *VPLInfo) {
1870     if (const VPLoop *ParentVPL = VPLInfo->getLoopFor(Block))
1871       return ParentVPL->isLoopLatch(Block);
1872 
1873     return false;
1874   }
1875 
1876   /// Count and return the number of succesors of \p PredBlock excluding any
1877   /// backedges.
1878   static unsigned countSuccessorsNoBE(VPBlockBase *PredBlock,
1879                                       VPLoopInfo *VPLI) {
1880     unsigned Count = 0;
1881     for (VPBlockBase *SuccBlock : PredBlock->getSuccessors()) {
1882       if (!VPBlockUtils::isBackEdge(PredBlock, SuccBlock, VPLI))
1883         Count++;
1884     }
1885     return Count;
1886   }
1887 };
1888 
1889 class VPInterleavedAccessInfo {
1890   DenseMap<VPInstruction *, InterleaveGroup<VPInstruction> *>
1891       InterleaveGroupMap;
1892 
1893   /// Type for mapping of instruction based interleave groups to VPInstruction
1894   /// interleave groups
1895   using Old2NewTy = DenseMap<InterleaveGroup<Instruction> *,
1896                              InterleaveGroup<VPInstruction> *>;
1897 
1898   /// Recursively \p Region and populate VPlan based interleave groups based on
1899   /// \p IAI.
1900   void visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New,
1901                    InterleavedAccessInfo &IAI);
1902   /// Recursively traverse \p Block and populate VPlan based interleave groups
1903   /// based on \p IAI.
1904   void visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
1905                   InterleavedAccessInfo &IAI);
1906 
1907 public:
1908   VPInterleavedAccessInfo(VPlan &Plan, InterleavedAccessInfo &IAI);
1909 
1910   ~VPInterleavedAccessInfo() {
1911     SmallPtrSet<InterleaveGroup<VPInstruction> *, 4> DelSet;
1912     // Avoid releasing a pointer twice.
1913     for (auto &I : InterleaveGroupMap)
1914       DelSet.insert(I.second);
1915     for (auto *Ptr : DelSet)
1916       delete Ptr;
1917   }
1918 
1919   /// Get the interleave group that \p Instr belongs to.
1920   ///
1921   /// \returns nullptr if doesn't have such group.
1922   InterleaveGroup<VPInstruction> *
1923   getInterleaveGroup(VPInstruction *Instr) const {
1924     if (InterleaveGroupMap.count(Instr))
1925       return InterleaveGroupMap.find(Instr)->second;
1926     return nullptr;
1927   }
1928 };
1929 
1930 /// Class that maps (parts of) an existing VPlan to trees of combined
1931 /// VPInstructions.
1932 class VPlanSlp {
1933   enum class OpMode { Failed, Load, Opcode };
1934 
1935   /// A DenseMapInfo implementation for using SmallVector<VPValue *, 4> as
1936   /// DenseMap keys.
1937   struct BundleDenseMapInfo {
1938     static SmallVector<VPValue *, 4> getEmptyKey() {
1939       return {reinterpret_cast<VPValue *>(-1)};
1940     }
1941 
1942     static SmallVector<VPValue *, 4> getTombstoneKey() {
1943       return {reinterpret_cast<VPValue *>(-2)};
1944     }
1945 
1946     static unsigned getHashValue(const SmallVector<VPValue *, 4> &V) {
1947       return static_cast<unsigned>(hash_combine_range(V.begin(), V.end()));
1948     }
1949 
1950     static bool isEqual(const SmallVector<VPValue *, 4> &LHS,
1951                         const SmallVector<VPValue *, 4> &RHS) {
1952       return LHS == RHS;
1953     }
1954   };
1955 
1956   /// Mapping of values in the original VPlan to a combined VPInstruction.
1957   DenseMap<SmallVector<VPValue *, 4>, VPInstruction *, BundleDenseMapInfo>
1958       BundleToCombined;
1959 
1960   VPInterleavedAccessInfo &IAI;
1961 
1962   /// Basic block to operate on. For now, only instructions in a single BB are
1963   /// considered.
1964   const VPBasicBlock &BB;
1965 
1966   /// Indicates whether we managed to combine all visited instructions or not.
1967   bool CompletelySLP = true;
1968 
1969   /// Width of the widest combined bundle in bits.
1970   unsigned WidestBundleBits = 0;
1971 
1972   using MultiNodeOpTy =
1973       typename std::pair<VPInstruction *, SmallVector<VPValue *, 4>>;
1974 
1975   // Input operand bundles for the current multi node. Each multi node operand
1976   // bundle contains values not matching the multi node's opcode. They will
1977   // be reordered in reorderMultiNodeOps, once we completed building a
1978   // multi node.
1979   SmallVector<MultiNodeOpTy, 4> MultiNodeOps;
1980 
1981   /// Indicates whether we are building a multi node currently.
1982   bool MultiNodeActive = false;
1983 
1984   /// Check if we can vectorize Operands together.
1985   bool areVectorizable(ArrayRef<VPValue *> Operands) const;
1986 
1987   /// Add combined instruction \p New for the bundle \p Operands.
1988   void addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New);
1989 
1990   /// Indicate we hit a bundle we failed to combine. Returns nullptr for now.
1991   VPInstruction *markFailed();
1992 
1993   /// Reorder operands in the multi node to maximize sequential memory access
1994   /// and commutative operations.
1995   SmallVector<MultiNodeOpTy, 4> reorderMultiNodeOps();
1996 
1997   /// Choose the best candidate to use for the lane after \p Last. The set of
1998   /// candidates to choose from are values with an opcode matching \p Last's
1999   /// or loads consecutive to \p Last.
2000   std::pair<OpMode, VPValue *> getBest(OpMode Mode, VPValue *Last,
2001                                        SmallPtrSetImpl<VPValue *> &Candidates,
2002                                        VPInterleavedAccessInfo &IAI);
2003 
2004   /// Print bundle \p Values to dbgs().
2005   void dumpBundle(ArrayRef<VPValue *> Values);
2006 
2007 public:
2008   VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB) : IAI(IAI), BB(BB) {}
2009 
2010   ~VPlanSlp() {
2011     for (auto &KV : BundleToCombined)
2012       delete KV.second;
2013   }
2014 
2015   /// Tries to build an SLP tree rooted at \p Operands and returns a
2016   /// VPInstruction combining \p Operands, if they can be combined.
2017   VPInstruction *buildGraph(ArrayRef<VPValue *> Operands);
2018 
2019   /// Return the width of the widest combined bundle in bits.
2020   unsigned getWidestBundleBits() const { return WidestBundleBits; }
2021 
2022   /// Return true if all visited instruction can be combined.
2023   bool isCompletelySLP() const { return CompletelySLP; }
2024 };
2025 } // end namespace llvm
2026 
2027 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
2028