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