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