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
30namespace llvm {
31
32// Forward declarations.
33class raw_ostream;
34class Value;
35class VPDef;
36class VPSlotTracker;
37class VPUser;
38class 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.
44class 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
58protected:
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
75public:
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
196typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
197typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;
198
199raw_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.
203class VPUser {
204public:
205 /// Subclass identifier (for isa/dyn_cast).
206 enum class VPUserID {
207 Recipe,
208 LiveOut,
209 };
210
211private:
212 SmallVector<VPValue *, 2> Operands;
213
214 VPUserID ID;
215
216protected:
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
236public:
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.
313class 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
339public:
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 VPFirstHeaderPHISC = VPCanonicalIVPHISC,
382 VPLastHeaderPHISC = 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
445class VPlan;
446class 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.
454class 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
468public:
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

source code of llvm/lib/Transforms/Vectorize/VPlanValue.h