xref: /llvm-project/llvm/lib/Transforms/Vectorize/VPlanValue.h (revision a002271972fb3fb2877bdb4abf9275b2c1291036)
1 //===- VPlanValue.h - Represent Values in Vectorizer Plan -----------------===//
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 entities induced by Vectorization
11 /// Plans, e.g. the instructions the VPlan intends to generate if executed.
12 /// VPlan models the following entities:
13 /// VPValue   VPUser   VPDef
14 ///    |        |
15 ///   VPInstruction
16 /// These are documented in docs/VectorizationPlan.rst.
17 ///
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
21 #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
22 
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/TinyPtrVector.h"
27 #include "llvm/ADT/iterator_range.h"
28 
29 namespace llvm {
30 
31 // Forward declarations.
32 class raw_ostream;
33 class Value;
34 class VPDef;
35 class VPSlotTracker;
36 class VPUser;
37 class VPRecipeBase;
38 class VPWidenMemoryInstructionRecipe;
39 
40 // This is the base class of the VPlan Def/Use graph, used for modeling the data
41 // flow into, within and out of the VPlan. VPValues can stand for live-ins
42 // coming from the input IR, instructions which VPlan will generate if executed
43 // and live-outs which the VPlan will need to fix accordingly.
44 class VPValue {
45   friend class VPBuilder;
46   friend class VPDef;
47   friend class VPInstruction;
48   friend struct VPlanTransforms;
49   friend class VPBasicBlock;
50   friend class VPInterleavedAccessInfo;
51   friend class VPSlotTracker;
52   friend class VPRecipeBase;
53   friend class VPWidenMemoryInstructionRecipe;
54 
55   const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
56 
57   SmallVector<VPUser *, 1> Users;
58 
59 protected:
60   // Hold the underlying Value, if any, attached to this VPValue.
61   Value *UnderlyingVal;
62 
63   /// Pointer to the VPDef that defines this VPValue. If it is nullptr, the
64   /// VPValue is not defined by any recipe modeled in VPlan.
65   VPDef *Def;
66 
67   VPValue(const unsigned char SC, Value *UV = nullptr, VPDef *Def = nullptr);
68 
69   // DESIGN PRINCIPLE: Access to the underlying IR must be strictly limited to
70   // the front-end and back-end of VPlan so that the middle-end is as
71   // independent as possible of the underlying IR. We grant access to the
72   // underlying IR using friendship. In that way, we should be able to use VPlan
73   // for multiple underlying IRs (Polly?) by providing a new VPlan front-end,
74   // back-end and analysis information for the new IR.
75 
76   // Set \p Val as the underlying Value of this VPValue.
77   void setUnderlyingValue(Value *Val) {
78     assert(!UnderlyingVal && "Underlying Value is already set.");
79     UnderlyingVal = Val;
80   }
81 
82 public:
83   /// Return the underlying Value attached to this VPValue.
84   Value *getUnderlyingValue() { return UnderlyingVal; }
85   const Value *getUnderlyingValue() const { return UnderlyingVal; }
86 
87   /// An enumeration for keeping track of the concrete subclass of VPValue that
88   /// are actually instantiated.
89   enum {
90     VPValueSC, /// A generic VPValue, like live-in values or defined by a recipe
91                /// that defines multiple values.
92     VPVRecipeSC /// A VPValue sub-class that is a VPRecipeBase.
93   };
94 
95   /// Create a live-in VPValue.
96   VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV, nullptr) {}
97   /// Create a VPValue for a \p Def which is a subclass of VPValue.
98   VPValue(VPDef *Def, Value *UV = nullptr) : VPValue(VPVRecipeSC, UV, Def) {}
99   /// Create a VPValue for a \p Def which defines multiple values.
100   VPValue(Value *UV, VPDef *Def) : VPValue(VPValueSC, UV, Def) {}
101   VPValue(const VPValue &) = delete;
102   VPValue &operator=(const VPValue &) = delete;
103 
104   virtual ~VPValue();
105 
106   /// \return an ID for the concrete type of this object.
107   /// This is used to implement the classof checks. This should not be used
108   /// for any other purpose, as the values may change as LLVM evolves.
109   unsigned getVPValueID() const { return SubclassID; }
110 
111 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
112   void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const;
113   void print(raw_ostream &OS, VPSlotTracker &Tracker) const;
114 
115   /// Dump the value to stderr (for debugging).
116   void dump() const;
117 #endif
118 
119   unsigned getNumUsers() const { return Users.size(); }
120   void addUser(VPUser &User) { Users.push_back(&User); }
121 
122   /// Remove a single \p User from the list of users.
123   void removeUser(VPUser &User) {
124     bool Found = false;
125     // The same user can be added multiple times, e.g. because the same VPValue
126     // is used twice by the same VPUser. Remove a single one.
127     erase_if(Users, [&User, &Found](VPUser *Other) {
128       if (Found)
129         return false;
130       if (Other == &User) {
131         Found = true;
132         return true;
133       }
134       return false;
135     });
136   }
137 
138   typedef SmallVectorImpl<VPUser *>::iterator user_iterator;
139   typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator;
140   typedef iterator_range<user_iterator> user_range;
141   typedef iterator_range<const_user_iterator> const_user_range;
142 
143   user_iterator user_begin() { return Users.begin(); }
144   const_user_iterator user_begin() const { return Users.begin(); }
145   user_iterator user_end() { return Users.end(); }
146   const_user_iterator user_end() const { return Users.end(); }
147   user_range users() { return user_range(user_begin(), user_end()); }
148   const_user_range users() const {
149     return const_user_range(user_begin(), user_end());
150   }
151 
152   /// Returns true if the value has more than one unique user.
153   bool hasMoreThanOneUniqueUser() {
154     if (getNumUsers() == 0)
155       return false;
156 
157     // Check if all users match the first user.
158     auto Current = std::next(user_begin());
159     while (Current != user_end() && *user_begin() == *Current)
160       Current++;
161     return Current != user_end();
162   }
163 
164   void replaceAllUsesWith(VPValue *New);
165 
166   /// Go through the uses list for this VPValue and make each use point to \p
167   /// New if the callback ShouldReplace returns true for the given use specified
168   /// by a pair of (VPUser, the use index).
169   void replaceUsesWithIf(
170       VPValue *New,
171       llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace);
172 
173   /// Returns the recipe defining this VPValue or nullptr if it is not defined
174   /// by a recipe, i.e. is a live-in.
175   VPRecipeBase *getDefiningRecipe();
176   const VPRecipeBase *getDefiningRecipe() const;
177 
178   /// Returns true if this VPValue is defined by a recipe.
179   bool hasDefiningRecipe() const { return getDefiningRecipe(); }
180 
181   /// Returns true if this VPValue is a live-in, i.e. defined outside the VPlan.
182   bool isLiveIn() const { return !hasDefiningRecipe(); }
183 
184   /// Returns the underlying IR value, if this VPValue is defined outside the
185   /// scope of VPlan. Returns nullptr if the VPValue is defined by a VPDef
186   /// inside a VPlan.
187   Value *getLiveInIRValue() {
188     assert(isLiveIn() &&
189            "VPValue is not a live-in; it is defined by a VPDef inside a VPlan");
190     return getUnderlyingValue();
191   }
192   const Value *getLiveInIRValue() const {
193     assert(isLiveIn() &&
194            "VPValue is not a live-in; it is defined by a VPDef inside a VPlan");
195     return getUnderlyingValue();
196   }
197 
198   /// Returns true if the VPValue is defined outside any vector regions, i.e. it
199   /// is a live-in value.
200   /// TODO: Also handle recipes defined in pre-header blocks.
201   bool isDefinedOutsideVectorRegions() const { return !hasDefiningRecipe(); }
202 };
203 
204 typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
205 typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;
206 
207 raw_ostream &operator<<(raw_ostream &OS, const VPValue &V);
208 
209 /// This class augments VPValue with operands which provide the inverse def-use
210 /// edges from VPValue's users to their defs.
211 class VPUser {
212 public:
213   /// Subclass identifier (for isa/dyn_cast).
214   enum class VPUserID {
215     Recipe,
216     LiveOut,
217   };
218 
219 private:
220   SmallVector<VPValue *, 2> Operands;
221 
222   VPUserID ID;
223 
224 protected:
225 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
226   /// Print the operands to \p O.
227   void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;
228 #endif
229 
230   VPUser(ArrayRef<VPValue *> Operands, VPUserID ID) : ID(ID) {
231     for (VPValue *Operand : Operands)
232       addOperand(Operand);
233   }
234 
235   VPUser(std::initializer_list<VPValue *> Operands, VPUserID ID)
236       : VPUser(ArrayRef<VPValue *>(Operands), ID) {}
237 
238   template <typename IterT>
239   VPUser(iterator_range<IterT> Operands, VPUserID ID) : ID(ID) {
240     for (VPValue *Operand : Operands)
241       addOperand(Operand);
242   }
243 
244 public:
245   VPUser() = delete;
246   VPUser(const VPUser &) = delete;
247   VPUser &operator=(const VPUser &) = delete;
248   virtual ~VPUser() {
249     for (VPValue *Op : operands())
250       Op->removeUser(*this);
251   }
252 
253   VPUserID getVPUserID() const { return ID; }
254 
255   void addOperand(VPValue *Operand) {
256     Operands.push_back(Operand);
257     Operand->addUser(*this);
258   }
259 
260   unsigned getNumOperands() const { return Operands.size(); }
261   inline VPValue *getOperand(unsigned N) const {
262     assert(N < Operands.size() && "Operand index out of bounds");
263     return Operands[N];
264   }
265 
266   void setOperand(unsigned I, VPValue *New) {
267     Operands[I]->removeUser(*this);
268     Operands[I] = New;
269     New->addUser(*this);
270   }
271 
272   void removeLastOperand() {
273     VPValue *Op = Operands.pop_back_val();
274     Op->removeUser(*this);
275   }
276 
277   typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
278   typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
279   typedef iterator_range<operand_iterator> operand_range;
280   typedef iterator_range<const_operand_iterator> const_operand_range;
281 
282   operand_iterator op_begin() { return Operands.begin(); }
283   const_operand_iterator op_begin() const { return Operands.begin(); }
284   operand_iterator op_end() { return Operands.end(); }
285   const_operand_iterator op_end() const { return Operands.end(); }
286   operand_range operands() { return operand_range(op_begin(), op_end()); }
287   const_operand_range operands() const {
288     return const_operand_range(op_begin(), op_end());
289   }
290 
291   /// Returns true if the VPUser uses scalars of operand \p Op. Conservatively
292   /// returns if only first (scalar) lane is used, as default.
293   virtual bool usesScalars(const VPValue *Op) const {
294     assert(is_contained(operands(), Op) &&
295            "Op must be an operand of the recipe");
296     return onlyFirstLaneUsed(Op);
297   }
298 
299   /// Returns true if the VPUser only uses the first lane of operand \p Op.
300   /// Conservatively returns false.
301   virtual bool onlyFirstLaneUsed(const VPValue *Op) const {
302     assert(is_contained(operands(), Op) &&
303            "Op must be an operand of the recipe");
304     return false;
305   }
306 };
307 
308 /// This class augments a recipe with a set of VPValues defined by the recipe.
309 /// It allows recipes to define zero, one or multiple VPValues. A VPDef owns
310 /// the VPValues it defines and is responsible for deleting its defined values.
311 /// Single-value VPDefs that also inherit from VPValue must make sure to inherit
312 /// from VPDef before VPValue.
313 class VPDef {
314   friend class VPValue;
315 
316   /// Subclass identifier (for isa/dyn_cast).
317   const unsigned char SubclassID;
318 
319   /// The VPValues defined by this VPDef.
320   TinyPtrVector<VPValue *> DefinedValues;
321 
322   /// Add \p V as a defined value by this VPDef.
323   void addDefinedValue(VPValue *V) {
324     assert(V->Def == this &&
325            "can only add VPValue already linked with this VPDef");
326     DefinedValues.push_back(V);
327   }
328 
329   /// Remove \p V from the values defined by this VPDef. \p V must be a defined
330   /// value of this VPDef.
331   void removeDefinedValue(VPValue *V) {
332     assert(V->Def == this && "can only remove VPValue linked with this VPDef");
333     assert(is_contained(DefinedValues, V) &&
334            "VPValue to remove must be in DefinedValues");
335     llvm::erase(DefinedValues, V);
336     V->Def = nullptr;
337   }
338 
339 public:
340   /// An enumeration for keeping track of the concrete subclass of VPRecipeBase
341   /// that is actually instantiated. Values of this enumeration are kept in the
342   /// SubclassID field of the VPRecipeBase objects. They are used for concrete
343   /// type identification.
344   using VPRecipeTy = enum {
345     VPBranchOnMaskSC,
346     VPDerivedIVSC,
347     VPExpandSCEVSC,
348     VPInstructionSC,
349     VPInterleaveSC,
350     VPReductionSC,
351     VPReplicateSC,
352     VPScalarIVStepsSC,
353     VPWidenCallSC,
354     VPWidenCanonicalIVSC,
355     VPWidenCastSC,
356     VPWidenGEPSC,
357     VPWidenMemoryInstructionSC,
358     VPWidenSC,
359     VPWidenSelectSC,
360     // START: Phi-like recipes. Need to be kept together.
361     VPBlendSC,
362     VPPredInstPHISC,
363     // START: SubclassID for recipes that inherit VPHeaderPHIRecipe.
364     // VPHeaderPHIRecipe need to be kept together.
365     VPCanonicalIVPHISC,
366     VPActiveLaneMaskPHISC,
367     VPFirstOrderRecurrencePHISC,
368     VPWidenPHISC,
369     VPWidenIntOrFpInductionSC,
370     VPWidenPointerInductionSC,
371     VPReductionPHISC,
372     // END: SubclassID for recipes that inherit VPHeaderPHIRecipe
373     // END: Phi-like recipes
374     VPFirstPHISC = VPBlendSC,
375     VPFirstHeaderPHISC = VPCanonicalIVPHISC,
376     VPLastHeaderPHISC = VPReductionPHISC,
377     VPLastPHISC = VPReductionPHISC,
378   };
379 
380   VPDef(const unsigned char SC) : SubclassID(SC) {}
381 
382   virtual ~VPDef() {
383     for (VPValue *D : make_early_inc_range(DefinedValues)) {
384       assert(D->Def == this &&
385              "all defined VPValues should point to the containing VPDef");
386       assert(D->getNumUsers() == 0 &&
387              "all defined VPValues should have no more users");
388       D->Def = nullptr;
389       delete D;
390     }
391   }
392 
393   /// Returns the only VPValue defined by the VPDef. Can only be called for
394   /// VPDefs with a single defined value.
395   VPValue *getVPSingleValue() {
396     assert(DefinedValues.size() == 1 && "must have exactly one defined value");
397     assert(DefinedValues[0] && "defined value must be non-null");
398     return DefinedValues[0];
399   }
400   const VPValue *getVPSingleValue() const {
401     assert(DefinedValues.size() == 1 && "must have exactly one defined value");
402     assert(DefinedValues[0] && "defined value must be non-null");
403     return DefinedValues[0];
404   }
405 
406   /// Returns the VPValue with index \p I defined by the VPDef.
407   VPValue *getVPValue(unsigned I) {
408     assert(DefinedValues[I] && "defined value must be non-null");
409     return DefinedValues[I];
410   }
411   const VPValue *getVPValue(unsigned I) const {
412     assert(DefinedValues[I] && "defined value must be non-null");
413     return DefinedValues[I];
414   }
415 
416   /// Returns an ArrayRef of the values defined by the VPDef.
417   ArrayRef<VPValue *> definedValues() { return DefinedValues; }
418   /// Returns an ArrayRef of the values defined by the VPDef.
419   ArrayRef<VPValue *> definedValues() const { return DefinedValues; }
420 
421   /// Returns the number of values defined by the VPDef.
422   unsigned getNumDefinedValues() const { return DefinedValues.size(); }
423 
424   /// \return an ID for the concrete type of this object.
425   /// This is used to implement the classof checks. This should not be used
426   /// for any other purpose, as the values may change as LLVM evolves.
427   unsigned getVPDefID() const { return SubclassID; }
428 
429 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
430   /// Dump the VPDef to stderr (for debugging).
431   void dump() const;
432 
433   /// Each concrete VPDef prints itself.
434   virtual void print(raw_ostream &O, const Twine &Indent,
435                      VPSlotTracker &SlotTracker) const = 0;
436 #endif
437 };
438 
439 class VPlan;
440 class VPBasicBlock;
441 
442 /// This class can be used to assign consecutive numbers to all VPValues in a
443 /// VPlan and allows querying the numbering for printing, similar to the
444 /// ModuleSlotTracker for IR values.
445 class VPSlotTracker {
446   DenseMap<const VPValue *, unsigned> Slots;
447   unsigned NextSlot = 0;
448 
449   void assignSlot(const VPValue *V);
450   void assignSlots(const VPlan &Plan);
451   void assignSlots(const VPBasicBlock *VPBB);
452 
453 public:
454   VPSlotTracker(const VPlan *Plan = nullptr) {
455     if (Plan)
456       assignSlots(*Plan);
457   }
458 
459   unsigned getSlot(const VPValue *V) const {
460     auto I = Slots.find(V);
461     if (I == Slots.end())
462       return -1;
463     return I->second;
464   }
465 };
466 
467 } // namespace llvm
468 
469 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
470