xref: /llvm-project/llvm/lib/Transforms/Vectorize/VPlanValue.h (revision 55f56cdc3329b9af059caf7fd5df01fe4e54eb14)
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. Values of this enumeration are kept in the
89   /// SubclassID field of the VPValue objects. They are used for concrete
90   /// type identification.
91   enum {
92     VPValueSC,
93     VPVInstructionSC,
94     VPVMemoryInstructionSC,
95     VPVReductionSC,
96     VPVReplicateSC,
97     VPVWidenSC,
98     VPVWidenCallSC,
99     VPVWidenCanonicalIVSC,
100     VPVWidenGEPSC,
101     VPVWidenSelectSC,
102 
103     // Phi-like VPValues. Need to be kept together.
104     VPVBlendSC,
105     VPVPredInstPHI,
106     // Header-phi recipes. Need to be kept together.
107     VPVCanonicalIVPHISC,
108     VPVActiveLaneMaskPHISC,
109     VPVFirstOrderRecurrencePHISC,
110     VPVWidenPHISC,
111     VPVWidenIntOrFpInductionSC,
112     VPVWidenPointerInductionSC,
113     VPVReductionPHISC,
114     VPVFirstHeaderPHISC = VPVCanonicalIVPHISC,
115     VPVLastPHISC = VPVReductionPHISC,
116   };
117 
118   VPValue(Value *UV = nullptr, VPDef *Def = nullptr)
119       : VPValue(VPValueSC, UV, Def) {}
120   VPValue(const VPValue &) = delete;
121   VPValue &operator=(const VPValue &) = delete;
122 
123   virtual ~VPValue();
124 
125   /// \return an ID for the concrete type of this object.
126   /// This is used to implement the classof checks. This should not be used
127   /// for any other purpose, as the values may change as LLVM evolves.
128   unsigned getVPValueID() const { return SubclassID; }
129 
130 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
131   void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const;
132   void print(raw_ostream &OS, VPSlotTracker &Tracker) const;
133 
134   /// Dump the value to stderr (for debugging).
135   void dump() const;
136 #endif
137 
138   unsigned getNumUsers() const { return Users.size(); }
139   void addUser(VPUser &User) { Users.push_back(&User); }
140 
141   /// Remove a single \p User from the list of users.
142   void removeUser(VPUser &User) {
143     bool Found = false;
144     // The same user can be added multiple times, e.g. because the same VPValue
145     // is used twice by the same VPUser. Remove a single one.
146     erase_if(Users, [&User, &Found](VPUser *Other) {
147       if (Found)
148         return false;
149       if (Other == &User) {
150         Found = true;
151         return true;
152       }
153       return false;
154     });
155   }
156 
157   typedef SmallVectorImpl<VPUser *>::iterator user_iterator;
158   typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator;
159   typedef iterator_range<user_iterator> user_range;
160   typedef iterator_range<const_user_iterator> const_user_range;
161 
162   user_iterator user_begin() { return Users.begin(); }
163   const_user_iterator user_begin() const { return Users.begin(); }
164   user_iterator user_end() { return Users.end(); }
165   const_user_iterator user_end() const { return Users.end(); }
166   user_range users() { return user_range(user_begin(), user_end()); }
167   const_user_range users() const {
168     return const_user_range(user_begin(), user_end());
169   }
170 
171   /// Returns true if the value has more than one unique user.
172   bool hasMoreThanOneUniqueUser() {
173     if (getNumUsers() == 0)
174       return false;
175 
176     // Check if all users match the first user.
177     auto Current = std::next(user_begin());
178     while (Current != user_end() && *user_begin() == *Current)
179       Current++;
180     return Current != user_end();
181   }
182 
183   void replaceAllUsesWith(VPValue *New);
184 
185   /// Returns the recipe defining this VPValue or nullptr if it is not defined
186   /// by a recipe, i.e. is a live-in.
187   VPRecipeBase *getDefiningRecipe();
188   const VPRecipeBase *getDefiningRecipe() const;
189 
190   /// Returns true if this VPValue is defined by a recipe.
191   bool hasDefiningRecipe() const { return getDefiningRecipe(); }
192 
193   /// Returns the underlying IR value, if this VPValue is defined outside the
194   /// scope of VPlan. Returns nullptr if the VPValue is defined by a VPDef
195   /// inside a VPlan.
196   Value *getLiveInIRValue() {
197     assert(!hasDefiningRecipe() &&
198            "VPValue is not a live-in; it is defined by a VPDef inside a VPlan");
199     return getUnderlyingValue();
200   }
201   const Value *getLiveInIRValue() const {
202     assert(!hasDefiningRecipe() &&
203            "VPValue is not a live-in; it is defined by a VPDef inside a VPlan");
204     return getUnderlyingValue();
205   }
206 
207   /// Returns true if the VPValue is defined outside any vector regions, i.e. it
208   /// is a live-in value.
209   /// TODO: Also handle recipes defined in pre-header blocks.
210   bool isDefinedOutsideVectorRegions() const { return !hasDefiningRecipe(); }
211 };
212 
213 typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
214 typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;
215 
216 raw_ostream &operator<<(raw_ostream &OS, const VPValue &V);
217 
218 /// This class augments VPValue with operands which provide the inverse def-use
219 /// edges from VPValue's users to their defs.
220 class VPUser {
221 public:
222   /// Subclass identifier (for isa/dyn_cast).
223   enum class VPUserID {
224     Recipe,
225     LiveOut,
226   };
227 
228 private:
229   SmallVector<VPValue *, 2> Operands;
230 
231   VPUserID ID;
232 
233 protected:
234 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
235   /// Print the operands to \p O.
236   void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;
237 #endif
238 
239   VPUser(ArrayRef<VPValue *> Operands, VPUserID ID) : ID(ID) {
240     for (VPValue *Operand : Operands)
241       addOperand(Operand);
242   }
243 
244   VPUser(std::initializer_list<VPValue *> Operands, VPUserID ID)
245       : VPUser(ArrayRef<VPValue *>(Operands), ID) {}
246 
247   template <typename IterT>
248   VPUser(iterator_range<IterT> Operands, VPUserID ID) : ID(ID) {
249     for (VPValue *Operand : Operands)
250       addOperand(Operand);
251   }
252 
253 public:
254   VPUser() = delete;
255   VPUser(const VPUser &) = delete;
256   VPUser &operator=(const VPUser &) = delete;
257   virtual ~VPUser() {
258     for (VPValue *Op : operands())
259       Op->removeUser(*this);
260   }
261 
262   VPUserID getVPUserID() const { return ID; }
263 
264   void addOperand(VPValue *Operand) {
265     Operands.push_back(Operand);
266     Operand->addUser(*this);
267   }
268 
269   unsigned getNumOperands() const { return Operands.size(); }
270   inline VPValue *getOperand(unsigned N) const {
271     assert(N < Operands.size() && "Operand index out of bounds");
272     return Operands[N];
273   }
274 
275   void setOperand(unsigned I, VPValue *New) {
276     Operands[I]->removeUser(*this);
277     Operands[I] = New;
278     New->addUser(*this);
279   }
280 
281   void removeLastOperand() {
282     VPValue *Op = Operands.pop_back_val();
283     Op->removeUser(*this);
284   }
285 
286   typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
287   typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
288   typedef iterator_range<operand_iterator> operand_range;
289   typedef iterator_range<const_operand_iterator> const_operand_range;
290 
291   operand_iterator op_begin() { return Operands.begin(); }
292   const_operand_iterator op_begin() const { return Operands.begin(); }
293   operand_iterator op_end() { return Operands.end(); }
294   const_operand_iterator op_end() const { return Operands.end(); }
295   operand_range operands() { return operand_range(op_begin(), op_end()); }
296   const_operand_range operands() const {
297     return const_operand_range(op_begin(), op_end());
298   }
299 
300   /// Method to support type inquiry through isa, cast, and dyn_cast.
301   static inline bool classof(const VPDef *Recipe);
302 
303   /// Returns true if the VPUser uses scalars of operand \p Op. Conservatively
304   /// returns if only first (scalar) lane is used, as default.
305   virtual bool usesScalars(const VPValue *Op) const {
306     assert(is_contained(operands(), Op) &&
307            "Op must be an operand of the recipe");
308     return onlyFirstLaneUsed(Op);
309   }
310 
311   /// Returns true if the VPUser only uses the first lane of operand \p Op.
312   /// Conservatively returns false.
313   virtual bool onlyFirstLaneUsed(const VPValue *Op) const {
314     assert(is_contained(operands(), Op) &&
315            "Op must be an operand of the recipe");
316     return false;
317   }
318 };
319 
320 /// This class augments a recipe with a set of VPValues defined by the recipe.
321 /// It allows recipes to define zero, one or multiple VPValues. A VPDef owns
322 /// the VPValues it defines and is responsible for deleting its defined values.
323 /// Single-value VPDefs that also inherit from VPValue must make sure to inherit
324 /// from VPDef before VPValue.
325 class VPDef {
326   friend class VPValue;
327 
328   /// Subclass identifier (for isa/dyn_cast).
329   const unsigned char SubclassID;
330 
331   /// The VPValues defined by this VPDef.
332   TinyPtrVector<VPValue *> DefinedValues;
333 
334   /// Add \p V as a defined value by this VPDef.
335   void addDefinedValue(VPValue *V) {
336     assert(V->Def == this &&
337            "can only add VPValue already linked with this VPDef");
338     DefinedValues.push_back(V);
339   }
340 
341   /// Remove \p V from the values defined by this VPDef. \p V must be a defined
342   /// value of this VPDef.
343   void removeDefinedValue(VPValue *V) {
344     assert(V->Def == this && "can only remove VPValue linked with this VPDef");
345     assert(is_contained(DefinedValues, V) &&
346            "VPValue to remove must be in DefinedValues");
347     erase_value(DefinedValues, V);
348     V->Def = nullptr;
349   }
350 
351 public:
352   /// An enumeration for keeping track of the concrete subclass of VPRecipeBase
353   /// that is actually instantiated. Values of this enumeration are kept in the
354   /// SubclassID field of the VPRecipeBase objects. They are used for concrete
355   /// type identification.
356   using VPRecipeTy = enum {
357     VPBranchOnMaskSC,
358     VPExpandSCEVSC,
359     VPInstructionSC,
360     VPInterleaveSC,
361     VPReductionSC,
362     VPReplicateSC,
363     VPScalarIVStepsSC,
364     VPWidenCallSC,
365     VPWidenCanonicalIVSC,
366     VPWidenGEPSC,
367     VPWidenMemoryInstructionSC,
368     VPWidenSC,
369     VPWidenSelectSC,
370 
371     // Phi-like recipes. Need to be kept together.
372     VPBlendSC,
373     VPPredInstPHISC,
374     // Header-phi recipes. Need to be kept together.
375     VPCanonicalIVPHISC,
376     VPActiveLaneMaskPHISC,
377     VPFirstOrderRecurrencePHISC,
378     VPWidenPHISC,
379     VPWidenIntOrFpInductionSC,
380     VPWidenPointerInductionSC,
381     VPReductionPHISC,
382     VPFirstPHISC = VPBlendSC,
383     VPFirstHeaderPHISC = VPCanonicalIVPHISC,
384     VPLastPHISC = VPReductionPHISC,
385   };
386 
387   VPDef(const unsigned char SC) : SubclassID(SC) {}
388 
389   virtual ~VPDef() {
390     for (VPValue *D : make_early_inc_range(DefinedValues)) {
391       assert(D->Def == this &&
392              "all defined VPValues should point to the containing VPDef");
393       assert(D->getNumUsers() == 0 &&
394              "all defined VPValues should have no more users");
395       D->Def = nullptr;
396       delete D;
397     }
398   }
399 
400   /// Returns the only VPValue defined by the VPDef. Can only be called for
401   /// VPDefs with a single defined value.
402   VPValue *getVPSingleValue() {
403     assert(DefinedValues.size() == 1 && "must have exactly one defined value");
404     assert(DefinedValues[0] && "defined value must be non-null");
405     return DefinedValues[0];
406   }
407   const VPValue *getVPSingleValue() const {
408     assert(DefinedValues.size() == 1 && "must have exactly one defined value");
409     assert(DefinedValues[0] && "defined value must be non-null");
410     return DefinedValues[0];
411   }
412 
413   /// Returns the VPValue with index \p I defined by the VPDef.
414   VPValue *getVPValue(unsigned I) {
415     assert(DefinedValues[I] && "defined value must be non-null");
416     return DefinedValues[I];
417   }
418   const VPValue *getVPValue(unsigned I) const {
419     assert(DefinedValues[I] && "defined value must be non-null");
420     return DefinedValues[I];
421   }
422 
423   /// Returns an ArrayRef of the values defined by the VPDef.
424   ArrayRef<VPValue *> definedValues() { return DefinedValues; }
425   /// Returns an ArrayRef of the values defined by the VPDef.
426   ArrayRef<VPValue *> definedValues() const { return DefinedValues; }
427 
428   /// Returns the number of values defined by the VPDef.
429   unsigned getNumDefinedValues() const { return DefinedValues.size(); }
430 
431   /// \return an ID for the concrete type of this object.
432   /// This is used to implement the classof checks. This should not be used
433   /// for any other purpose, as the values may change as LLVM evolves.
434   unsigned getVPDefID() const { return SubclassID; }
435 
436 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
437   /// Dump the VPDef to stderr (for debugging).
438   void dump() const;
439 
440   /// Each concrete VPDef prints itself.
441   virtual void print(raw_ostream &O, const Twine &Indent,
442                      VPSlotTracker &SlotTracker) const = 0;
443 #endif
444 };
445 
446 class VPlan;
447 class VPBasicBlock;
448 
449 /// This class can be used to assign consecutive numbers to all VPValues in a
450 /// VPlan and allows querying the numbering for printing, similar to the
451 /// ModuleSlotTracker for IR values.
452 class VPSlotTracker {
453   DenseMap<const VPValue *, unsigned> Slots;
454   unsigned NextSlot = 0;
455 
456   void assignSlot(const VPValue *V);
457   void assignSlots(const VPlan &Plan);
458 
459 public:
460   VPSlotTracker(const VPlan *Plan = nullptr) {
461     if (Plan)
462       assignSlots(*Plan);
463   }
464 
465   unsigned getSlot(const VPValue *V) const {
466     auto I = Slots.find(V);
467     if (I == Slots.end())
468       return -1;
469     return I->second;
470   }
471 };
472 
473 } // namespace llvm
474 
475 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
476