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/StringMap.h" |
27 | #include "llvm/ADT/TinyPtrVector.h" |
28 | #include "llvm/ADT/iterator_range.h" |
29 | |
30 | namespace llvm { |
31 | |
32 | // Forward declarations. |
33 | class raw_ostream; |
34 | class Value; |
35 | class VPDef; |
36 | class VPSlotTracker; |
37 | class VPUser; |
38 | class VPRecipeBase; |
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 | |
54 | const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast). |
55 | |
56 | SmallVector<VPUser *, 1> Users; |
57 | |
58 | protected: |
59 | // Hold the underlying Value, if any, attached to this VPValue. |
60 | Value *UnderlyingVal; |
61 | |
62 | /// Pointer to the VPDef that defines this VPValue. If it is nullptr, the |
63 | /// VPValue is not defined by any recipe modeled in VPlan. |
64 | VPDef *Def; |
65 | |
66 | VPValue(const unsigned char SC, Value *UV = nullptr, VPDef *Def = nullptr); |
67 | |
68 | // DESIGN PRINCIPLE: Access to the underlying IR must be strictly limited to |
69 | // the front-end and back-end of VPlan so that the middle-end is as |
70 | // independent as possible of the underlying IR. We grant access to the |
71 | // underlying IR using friendship. In that way, we should be able to use VPlan |
72 | // for multiple underlying IRs (Polly?) by providing a new VPlan front-end, |
73 | // back-end and analysis information for the new IR. |
74 | |
75 | public: |
76 | /// Return the underlying Value attached to this VPValue. |
77 | Value *getUnderlyingValue() { return UnderlyingVal; } |
78 | const Value *getUnderlyingValue() const { return UnderlyingVal; } |
79 | |
80 | /// An enumeration for keeping track of the concrete subclass of VPValue that |
81 | /// are actually instantiated. |
82 | enum { |
83 | VPValueSC, /// A generic VPValue, like live-in values or defined by a recipe |
84 | /// that defines multiple values. |
85 | VPVRecipeSC /// A VPValue sub-class that is a VPRecipeBase. |
86 | }; |
87 | |
88 | /// Create a live-in VPValue. |
89 | VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV, nullptr) {} |
90 | /// Create a VPValue for a \p Def which is a subclass of VPValue. |
91 | VPValue(VPDef *Def, Value *UV = nullptr) : VPValue(VPVRecipeSC, UV, Def) {} |
92 | /// Create a VPValue for a \p Def which defines multiple values. |
93 | VPValue(Value *UV, VPDef *Def) : VPValue(VPValueSC, UV, Def) {} |
94 | VPValue(const VPValue &) = delete; |
95 | VPValue &operator=(const VPValue &) = delete; |
96 | |
97 | virtual ~VPValue(); |
98 | |
99 | /// \return an ID for the concrete type of this object. |
100 | /// This is used to implement the classof checks. This should not be used |
101 | /// for any other purpose, as the values may change as LLVM evolves. |
102 | unsigned getVPValueID() const { return SubclassID; } |
103 | |
104 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
105 | void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const; |
106 | void print(raw_ostream &OS, VPSlotTracker &Tracker) const; |
107 | |
108 | /// Dump the value to stderr (for debugging). |
109 | void dump() const; |
110 | #endif |
111 | |
112 | unsigned getNumUsers() const { return Users.size(); } |
113 | void addUser(VPUser &User) { Users.push_back(Elt: &User); } |
114 | |
115 | /// Remove a single \p User from the list of users. |
116 | void removeUser(VPUser &User) { |
117 | // The same user can be added multiple times, e.g. because the same VPValue |
118 | // is used twice by the same VPUser. Remove a single one. |
119 | auto *I = find(Range&: Users, Val: &User); |
120 | if (I != Users.end()) |
121 | Users.erase(CI: I); |
122 | } |
123 | |
124 | typedef SmallVectorImpl<VPUser *>::iterator user_iterator; |
125 | typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator; |
126 | typedef iterator_range<user_iterator> user_range; |
127 | typedef iterator_range<const_user_iterator> const_user_range; |
128 | |
129 | user_iterator user_begin() { return Users.begin(); } |
130 | const_user_iterator user_begin() const { return Users.begin(); } |
131 | user_iterator user_end() { return Users.end(); } |
132 | const_user_iterator user_end() const { return Users.end(); } |
133 | user_range users() { return user_range(user_begin(), user_end()); } |
134 | const_user_range users() const { |
135 | return const_user_range(user_begin(), user_end()); |
136 | } |
137 | |
138 | /// Returns true if the value has more than one unique user. |
139 | bool hasMoreThanOneUniqueUser() { |
140 | if (getNumUsers() == 0) |
141 | return false; |
142 | |
143 | // Check if all users match the first user. |
144 | auto Current = std::next(x: user_begin()); |
145 | while (Current != user_end() && *user_begin() == *Current) |
146 | Current++; |
147 | return Current != user_end(); |
148 | } |
149 | |
150 | void replaceAllUsesWith(VPValue *New); |
151 | |
152 | /// Go through the uses list for this VPValue and make each use point to \p |
153 | /// New if the callback ShouldReplace returns true for the given use specified |
154 | /// by a pair of (VPUser, the use index). |
155 | void replaceUsesWithIf( |
156 | VPValue *New, |
157 | llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace); |
158 | |
159 | /// Returns the recipe defining this VPValue or nullptr if it is not defined |
160 | /// by a recipe, i.e. is a live-in. |
161 | VPRecipeBase *getDefiningRecipe(); |
162 | const VPRecipeBase *getDefiningRecipe() const; |
163 | |
164 | /// Returns true if this VPValue is defined by a recipe. |
165 | bool hasDefiningRecipe() const { return getDefiningRecipe(); } |
166 | |
167 | /// Returns true if this VPValue is a live-in, i.e. defined outside the VPlan. |
168 | bool isLiveIn() const { return !hasDefiningRecipe(); } |
169 | |
170 | /// Returns the underlying IR value, if this VPValue is defined outside the |
171 | /// scope of VPlan. Returns nullptr if the VPValue is defined by a VPDef |
172 | /// inside a VPlan. |
173 | Value *getLiveInIRValue() { |
174 | assert(isLiveIn() && |
175 | "VPValue is not a live-in; it is defined by a VPDef inside a VPlan" ); |
176 | return getUnderlyingValue(); |
177 | } |
178 | const Value *getLiveInIRValue() const { |
179 | assert(isLiveIn() && |
180 | "VPValue is not a live-in; it is defined by a VPDef inside a VPlan" ); |
181 | return getUnderlyingValue(); |
182 | } |
183 | |
184 | /// Returns true if the VPValue is defined outside any vector regions, i.e. it |
185 | /// is a live-in value. |
186 | /// TODO: Also handle recipes defined in pre-header blocks. |
187 | bool isDefinedOutsideVectorRegions() const { return !hasDefiningRecipe(); } |
188 | |
189 | // Set \p Val as the underlying Value of this VPValue. |
190 | void setUnderlyingValue(Value *Val) { |
191 | assert(!UnderlyingVal && "Underlying Value is already set." ); |
192 | UnderlyingVal = Val; |
193 | } |
194 | }; |
195 | |
196 | typedef DenseMap<Value *, VPValue *> Value2VPValueTy; |
197 | typedef DenseMap<VPValue *, Value *> VPValue2ValueTy; |
198 | |
199 | raw_ostream &operator<<(raw_ostream &OS, const VPValue &V); |
200 | |
201 | /// This class augments VPValue with operands which provide the inverse def-use |
202 | /// edges from VPValue's users to their defs. |
203 | class VPUser { |
204 | public: |
205 | /// Subclass identifier (for isa/dyn_cast). |
206 | enum class VPUserID { |
207 | Recipe, |
208 | LiveOut, |
209 | }; |
210 | |
211 | private: |
212 | SmallVector<VPValue *, 2> Operands; |
213 | |
214 | VPUserID ID; |
215 | |
216 | protected: |
217 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
218 | /// Print the operands to \p O. |
219 | void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const; |
220 | #endif |
221 | |
222 | VPUser(ArrayRef<VPValue *> Operands, VPUserID ID) : ID(ID) { |
223 | for (VPValue *Operand : Operands) |
224 | addOperand(Operand); |
225 | } |
226 | |
227 | VPUser(std::initializer_list<VPValue *> Operands, VPUserID ID) |
228 | : VPUser(ArrayRef<VPValue *>(Operands), ID) {} |
229 | |
230 | template <typename IterT> |
231 | VPUser(iterator_range<IterT> Operands, VPUserID ID) : ID(ID) { |
232 | for (VPValue *Operand : Operands) |
233 | addOperand(Operand); |
234 | } |
235 | |
236 | public: |
237 | VPUser() = delete; |
238 | VPUser(const VPUser &) = delete; |
239 | VPUser &operator=(const VPUser &) = delete; |
240 | virtual ~VPUser() { |
241 | for (VPValue *Op : operands()) |
242 | Op->removeUser(User&: *this); |
243 | } |
244 | |
245 | VPUserID getVPUserID() const { return ID; } |
246 | |
247 | void addOperand(VPValue *Operand) { |
248 | Operands.push_back(Elt: Operand); |
249 | Operand->addUser(User&: *this); |
250 | } |
251 | |
252 | unsigned getNumOperands() const { return Operands.size(); } |
253 | inline VPValue *getOperand(unsigned N) const { |
254 | assert(N < Operands.size() && "Operand index out of bounds" ); |
255 | return Operands[N]; |
256 | } |
257 | |
258 | void setOperand(unsigned I, VPValue *New) { |
259 | Operands[I]->removeUser(User&: *this); |
260 | Operands[I] = New; |
261 | New->addUser(User&: *this); |
262 | } |
263 | |
264 | void removeLastOperand() { |
265 | VPValue *Op = Operands.pop_back_val(); |
266 | Op->removeUser(User&: *this); |
267 | } |
268 | |
269 | typedef SmallVectorImpl<VPValue *>::iterator operand_iterator; |
270 | typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator; |
271 | typedef iterator_range<operand_iterator> operand_range; |
272 | typedef iterator_range<const_operand_iterator> const_operand_range; |
273 | |
274 | operand_iterator op_begin() { return Operands.begin(); } |
275 | const_operand_iterator op_begin() const { return Operands.begin(); } |
276 | operand_iterator op_end() { return Operands.end(); } |
277 | const_operand_iterator op_end() const { return Operands.end(); } |
278 | operand_range operands() { return operand_range(op_begin(), op_end()); } |
279 | const_operand_range operands() const { |
280 | return const_operand_range(op_begin(), op_end()); |
281 | } |
282 | |
283 | /// Returns true if the VPUser uses scalars of operand \p Op. Conservatively |
284 | /// returns if only first (scalar) lane is used, as default. |
285 | virtual bool usesScalars(const VPValue *Op) const { |
286 | assert(is_contained(operands(), Op) && |
287 | "Op must be an operand of the recipe" ); |
288 | return onlyFirstLaneUsed(Op); |
289 | } |
290 | |
291 | /// Returns true if the VPUser only uses the first lane of operand \p Op. |
292 | /// Conservatively returns false. |
293 | virtual bool onlyFirstLaneUsed(const VPValue *Op) const { |
294 | assert(is_contained(operands(), Op) && |
295 | "Op must be an operand of the recipe" ); |
296 | return false; |
297 | } |
298 | |
299 | /// Returns true if the VPUser only uses the first part of operand \p Op. |
300 | /// Conservatively returns false. |
301 | virtual bool onlyFirstPartUsed(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(NewVal: 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(C&: 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 | VPScalarCastSC, |
353 | VPScalarIVStepsSC, |
354 | VPVectorPointerSC, |
355 | VPWidenCallSC, |
356 | VPWidenCanonicalIVSC, |
357 | VPWidenCastSC, |
358 | VPWidenGEPSC, |
359 | VPWidenLoadEVLSC, |
360 | VPWidenLoadSC, |
361 | VPWidenStoreEVLSC, |
362 | VPWidenStoreSC, |
363 | VPWidenSC, |
364 | VPWidenSelectSC, |
365 | VPBlendSC, |
366 | // START: Phi-like recipes. Need to be kept together. |
367 | VPWidenPHISC, |
368 | VPPredInstPHISC, |
369 | // START: SubclassID for recipes that inherit VPHeaderPHIRecipe. |
370 | // VPHeaderPHIRecipe need to be kept together. |
371 | VPCanonicalIVPHISC, |
372 | VPActiveLaneMaskPHISC, |
373 | VPEVLBasedIVPHISC, |
374 | VPFirstOrderRecurrencePHISC, |
375 | VPWidenIntOrFpInductionSC, |
376 | VPWidenPointerInductionSC, |
377 | VPReductionPHISC, |
378 | // END: SubclassID for recipes that inherit VPHeaderPHIRecipe |
379 | // END: Phi-like recipes |
380 | VPFirstPHISC = VPWidenPHISC, |
381 | = VPCanonicalIVPHISC, |
382 | = VPReductionPHISC, |
383 | VPLastPHISC = VPReductionPHISC, |
384 | }; |
385 | |
386 | VPDef(const unsigned char SC) : SubclassID(SC) {} |
387 | |
388 | virtual ~VPDef() { |
389 | for (VPValue *D : make_early_inc_range(Range&: DefinedValues)) { |
390 | assert(D->Def == this && |
391 | "all defined VPValues should point to the containing VPDef" ); |
392 | assert(D->getNumUsers() == 0 && |
393 | "all defined VPValues should have no more users" ); |
394 | D->Def = nullptr; |
395 | delete D; |
396 | } |
397 | } |
398 | |
399 | /// Returns the only VPValue defined by the VPDef. Can only be called for |
400 | /// VPDefs with a single defined value. |
401 | VPValue *getVPSingleValue() { |
402 | assert(DefinedValues.size() == 1 && "must have exactly one defined value" ); |
403 | assert(DefinedValues[0] && "defined value must be non-null" ); |
404 | return DefinedValues[0]; |
405 | } |
406 | const VPValue *getVPSingleValue() const { |
407 | assert(DefinedValues.size() == 1 && "must have exactly one defined value" ); |
408 | assert(DefinedValues[0] && "defined value must be non-null" ); |
409 | return DefinedValues[0]; |
410 | } |
411 | |
412 | /// Returns the VPValue with index \p I defined by the VPDef. |
413 | VPValue *getVPValue(unsigned I) { |
414 | assert(DefinedValues[I] && "defined value must be non-null" ); |
415 | return DefinedValues[I]; |
416 | } |
417 | const VPValue *getVPValue(unsigned I) const { |
418 | assert(DefinedValues[I] && "defined value must be non-null" ); |
419 | return DefinedValues[I]; |
420 | } |
421 | |
422 | /// Returns an ArrayRef of the values defined by the VPDef. |
423 | ArrayRef<VPValue *> definedValues() { return DefinedValues; } |
424 | /// Returns an ArrayRef of the values defined by the VPDef. |
425 | ArrayRef<VPValue *> definedValues() const { return DefinedValues; } |
426 | |
427 | /// Returns the number of values defined by the VPDef. |
428 | unsigned getNumDefinedValues() const { return DefinedValues.size(); } |
429 | |
430 | /// \return an ID for the concrete type of this object. |
431 | /// This is used to implement the classof checks. This should not be used |
432 | /// for any other purpose, as the values may change as LLVM evolves. |
433 | unsigned getVPDefID() const { return SubclassID; } |
434 | |
435 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
436 | /// Dump the VPDef to stderr (for debugging). |
437 | void dump() const; |
438 | |
439 | /// Each concrete VPDef prints itself. |
440 | virtual void print(raw_ostream &O, const Twine &Indent, |
441 | VPSlotTracker &SlotTracker) const = 0; |
442 | #endif |
443 | }; |
444 | |
445 | class VPlan; |
446 | class VPBasicBlock; |
447 | |
448 | /// This class can be used to assign names to VPValues. For VPValues without |
449 | /// underlying value, assign consecutive numbers and use those as names (wrapped |
450 | /// in vp<>). Otherwise, use the name from the underlying value (wrapped in |
451 | /// ir<>), appending a .V version number if there are multiple uses of the same |
452 | /// name. Allows querying names for VPValues for printing, similar to the |
453 | /// ModuleSlotTracker for IR values. |
454 | class VPSlotTracker { |
455 | /// Keep track of versioned names assigned to VPValues with underlying IR |
456 | /// values. |
457 | DenseMap<const VPValue *, std::string> VPValue2Name; |
458 | /// Keep track of the next number to use to version the base name. |
459 | StringMap<unsigned> BaseName2Version; |
460 | |
461 | /// Number to assign to the next VPValue without underlying value. |
462 | unsigned NextSlot = 0; |
463 | |
464 | void assignName(const VPValue *V); |
465 | void assignNames(const VPlan &Plan); |
466 | void assignNames(const VPBasicBlock *VPBB); |
467 | |
468 | public: |
469 | VPSlotTracker(const VPlan *Plan = nullptr) { |
470 | if (Plan) |
471 | assignNames(Plan: *Plan); |
472 | } |
473 | |
474 | /// Returns the name assigned to \p V, if there is one, otherwise try to |
475 | /// construct one from the underlying value, if there's one; else return |
476 | /// <badref>. |
477 | std::string getOrCreateName(const VPValue *V) const; |
478 | }; |
479 | |
480 | } // namespace llvm |
481 | |
482 | #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H |
483 | |