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/STLExtras.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/TinyPtrVector.h"
26#include "llvm/ADT/iterator_range.h"
27#include "llvm/IR/Constants.h"
28#include "llvm/Support/Casting.h"
29#include "llvm/Support/Compiler.h"
30
31namespace llvm {
32
33// Forward declarations.
34class raw_ostream;
35class Type;
36class Value;
37class VPDef;
38class VPSlotTracker;
39class VPUser;
40class VPRecipeBase;
41class VPPhiAccessors;
42
43/// This is the base class of the VPlan Def/Use graph, used for modeling the
44/// data flow into, within and out of the VPlan. VPValues can stand for live-ins
45/// coming from the input IR, symbolic values and values defined by recipes.
46class LLVM_ABI_FOR_TEST VPValue {
47 friend class VPlan;
48 friend struct VPIRValue;
49 friend struct VPSymbolicValue;
50 friend class VPRecipeValue;
51
52 const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
53
54 SmallVector<VPUser *, 1> Users;
55
56 /// Hold the underlying Value, if any, attached to this VPValue.
57 Value *UnderlyingVal;
58
59 VPValue(const unsigned char SC, Value *UV = nullptr)
60 : SubclassID(SC), UnderlyingVal(UV) {}
61
62 // DESIGN PRINCIPLE: Access to the underlying IR must be strictly limited to
63 // the front-end and back-end of VPlan so that the middle-end is as
64 // independent as possible of the underlying IR. We grant access to the
65 // underlying IR using friendship. In that way, we should be able to use VPlan
66 // for multiple underlying IRs (Polly?) by providing a new VPlan front-end,
67 // back-end and analysis information for the new IR.
68
69public:
70 /// Return the underlying Value attached to this VPValue.
71 Value *getUnderlyingValue() const { return UnderlyingVal; }
72
73 /// Return the underlying IR value for a VPIRValue.
74 Value *getLiveInIRValue() const;
75
76 /// An enumeration for keeping track of the concrete subclass of VPValue that
77 /// are actually instantiated.
78 enum {
79 VPVIRValueSC, /// A live-in VPValue wrapping an IR Value.
80 VPVSymbolicSC, /// A symbolic live-in VPValue without IR backing.
81 VPVRecipeValueSC, /// A VPValue defined by a recipe.
82 };
83
84 VPValue(const VPValue &) = delete;
85 VPValue &operator=(const VPValue &) = delete;
86
87 virtual ~VPValue() {
88 assert(Users.empty() && "trying to delete a VPValue with remaining users");
89 }
90
91 /// \return an ID for the concrete type of this object.
92 /// This is used to implement the classof checks. This should not be used
93 /// for any other purpose, as the values may change as LLVM evolves.
94 unsigned getVPValueID() const { return SubclassID; }
95
96#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
97 void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const;
98 void print(raw_ostream &OS, VPSlotTracker &Tracker) const;
99
100 /// Dump the value to stderr (for debugging).
101 void dump() const;
102#endif
103
104 /// Assert that this VPValue has not been materialized, if it is a
105 /// VPSymbolicValue.
106 void assertNotMaterialized() const;
107
108 unsigned getNumUsers() const {
109 if (Users.empty())
110 return 0;
111 assertNotMaterialized();
112 return Users.size();
113 }
114 void addUser(VPUser &User) {
115 assertNotMaterialized();
116 Users.push_back(Elt: &User);
117 }
118
119 /// Remove a single \p User from the list of users.
120 void removeUser(VPUser &User) {
121 assertNotMaterialized();
122 // The same user can be added multiple times, e.g. because the same VPValue
123 // is used twice by the same VPUser. Remove a single one.
124 auto *I = find(Range&: Users, Val: &User);
125 if (I != Users.end())
126 Users.erase(CI: I);
127 }
128
129 typedef SmallVectorImpl<VPUser *>::iterator user_iterator;
130 typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator;
131 typedef iterator_range<user_iterator> user_range;
132 typedef iterator_range<const_user_iterator> const_user_range;
133
134 user_iterator user_begin() {
135 assertNotMaterialized();
136 return Users.begin();
137 }
138 const_user_iterator user_begin() const {
139 assertNotMaterialized();
140 return Users.begin();
141 }
142 user_iterator user_end() {
143 assertNotMaterialized();
144 return Users.end();
145 }
146 const_user_iterator user_end() const {
147 assertNotMaterialized();
148 return Users.end();
149 }
150 user_range users() { return user_range(user_begin(), user_end()); }
151 const_user_range users() const {
152 return const_user_range(user_begin(), user_end());
153 }
154
155 /// Returns true if the value has more than one unique user.
156 bool hasMoreThanOneUniqueUser() const {
157 if (getNumUsers() == 0)
158 return false;
159
160 // Check if all users match the first user.
161 auto Current = std::next(x: user_begin());
162 while (Current != user_end() && *user_begin() == *Current)
163 Current++;
164 return Current != user_end();
165 }
166
167 bool hasOneUse() const { return getNumUsers() == 1; }
168
169 /// Return the single user of this value, or nullptr if there is not exactly
170 /// one user.
171 VPUser *getSingleUser() { return hasOneUse() ? *user_begin() : nullptr; }
172 const VPUser *getSingleUser() const {
173 return hasOneUse() ? *user_begin() : nullptr;
174 }
175
176 void replaceAllUsesWith(VPValue *New);
177
178 /// Go through the uses list for this VPValue and make each use point to \p
179 /// New if the callback ShouldReplace returns true for the given use specified
180 /// by a pair of (VPUser, the use index).
181 void replaceUsesWithIf(
182 VPValue *New,
183 llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace);
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 true if the VPValue is defined outside any loop.
194 bool isDefinedOutsideLoopRegions() const;
195
196 // Set \p Val as the underlying Value of this VPValue.
197 void setUnderlyingValue(Value *Val) {
198 assert(!UnderlyingVal && "Underlying Value is already set.");
199 UnderlyingVal = Val;
200 }
201};
202
203LLVM_ABI_FOR_TEST raw_ostream &operator<<(raw_ostream &OS,
204 const VPRecipeBase &R);
205
206/// A VPValue representing a live-in from the input IR or a constant. It wraps
207/// an underlying IR Value.
208struct VPIRValue : public VPValue {
209 VPIRValue(Value *UV) : VPValue(VPVIRValueSC, UV) {
210 assert(UV && "VPIRValue requires an underlying IR value");
211 }
212
213 /// Returns the underlying IR value.
214 Value *getValue() const { return getUnderlyingValue(); }
215
216 /// Returns the type of the underlying IR value.
217 Type *getType() const;
218
219 static bool classof(const VPValue *V) {
220 return V->getVPValueID() == VPVIRValueSC;
221 }
222};
223
224/// An overlay on VPIRValue for VPValues that wrap a ConstantInt. Provides
225/// convenient accessors for the underlying constant.
226struct VPConstantInt : public VPIRValue {
227 VPConstantInt(ConstantInt *CI) : VPIRValue(CI) {}
228
229 static bool classof(const VPValue *V) {
230 return isa<VPIRValue>(Val: V) && isa<ConstantInt>(Val: V->getUnderlyingValue());
231 }
232
233 bool isOne() const { return getAPInt().isOne(); }
234
235 bool isZero() const { return getAPInt().isZero(); }
236
237 const APInt &getAPInt() const {
238 return cast<ConstantInt>(Val: getValue())->getValue();
239 }
240
241 unsigned getBitWidth() const { return getAPInt().getBitWidth(); }
242
243 uint64_t getZExtValue() const { return getAPInt().getZExtValue(); }
244};
245
246/// A symbolic live-in VPValue, used for values like vector trip count, VF, and
247/// VFxUF.
248struct VPSymbolicValue : public VPValue {
249 VPSymbolicValue() : VPValue(VPVSymbolicSC, nullptr) {}
250
251 static bool classof(const VPValue *V) {
252 return V->getVPValueID() == VPVSymbolicSC;
253 }
254
255 /// Returns true if this symbolic value has been materialized.
256 bool isMaterialized() const { return Materialized; }
257
258 /// Mark this symbolic value as materialized.
259 void markMaterialized() {
260 assert(!Materialized && "VPSymbolicValue already materialized");
261 Materialized = true;
262 }
263
264private:
265 /// Track whether this symbolic value has been materialized (replaced).
266 /// After materialization, accessing users should trigger an assertion.
267 bool Materialized = false;
268};
269
270/// A VPValue defined by a recipe that produces one or more values.
271class VPRecipeValue : public VPValue {
272 friend class VPValue;
273 friend class VPDef;
274
275 /// Pointer to the VPRecipeBase that defines this VPValue.
276 VPRecipeBase *Def;
277
278#if !defined(NDEBUG)
279 /// Returns true if this VPRecipeValue is defined by \p D.
280 /// NOTE: Only used by VPDef to assert that VPRecipeValues added/removed from
281 /// /p D are associated with its VPRecipeBase,
282 bool isDefinedBy(const VPDef *D) const;
283#endif
284
285public:
286 LLVM_ABI_FOR_TEST VPRecipeValue(VPRecipeBase *Def, Value *UV = nullptr);
287
288 LLVM_ABI_FOR_TEST virtual ~VPRecipeValue();
289
290 static bool classof(const VPValue *V) {
291 return V->getVPValueID() == VPVRecipeValueSC;
292 }
293};
294
295/// This class augments VPValue with operands which provide the inverse def-use
296/// edges from VPValue's users to their defs.
297class VPUser {
298 /// Grant access to removeOperand for VPPhiAccessors, the only supported user.
299 friend class VPPhiAccessors;
300
301 SmallVector<VPValue *, 2> Operands;
302
303 /// Removes the operand at index \p Idx. This also removes the VPUser from the
304 /// use-list of the operand.
305 void removeOperand(unsigned Idx) {
306 getOperand(N: Idx)->removeUser(User&: *this);
307 Operands.erase(CI: Operands.begin() + Idx);
308 }
309
310protected:
311#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
312 /// Print the operands to \p O.
313 void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;
314#endif
315
316 VPUser(ArrayRef<VPValue *> Operands) {
317 for (VPValue *Operand : Operands)
318 addOperand(Operand);
319 }
320
321public:
322 VPUser() = delete;
323 VPUser(const VPUser &) = delete;
324 VPUser &operator=(const VPUser &) = delete;
325 virtual ~VPUser() {
326 for (VPValue *Op : operands())
327 Op->removeUser(User&: *this);
328 }
329
330 void addOperand(VPValue *Operand) {
331 Operands.push_back(Elt: Operand);
332 Operand->addUser(User&: *this);
333 }
334
335 unsigned getNumOperands() const { return Operands.size(); }
336 inline VPValue *getOperand(unsigned N) const {
337 assert(N < Operands.size() && "Operand index out of bounds");
338 return Operands[N];
339 }
340
341 void setOperand(unsigned I, VPValue *New) {
342 Operands[I]->removeUser(User&: *this);
343 Operands[I] = New;
344 New->addUser(User&: *this);
345 }
346
347 /// Swap operands of the VPUser. It must have exactly 2 operands.
348 void swapOperands() {
349 assert(Operands.size() == 2 && "must have 2 operands to swap");
350 std::swap(a&: Operands[0], b&: Operands[1]);
351 }
352
353 /// Replaces all uses of \p From in the VPUser with \p To.
354 void replaceUsesOfWith(VPValue *From, VPValue *To);
355
356 typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
357 typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
358 typedef iterator_range<operand_iterator> operand_range;
359 typedef iterator_range<const_operand_iterator> const_operand_range;
360
361 operand_iterator op_begin() { return Operands.begin(); }
362 const_operand_iterator op_begin() const { return Operands.begin(); }
363 operand_iterator op_end() { return Operands.end(); }
364 const_operand_iterator op_end() const { return Operands.end(); }
365 operand_range operands() { return operand_range(op_begin(), op_end()); }
366 const_operand_range operands() const {
367 return const_operand_range(op_begin(), op_end());
368 }
369
370 /// Returns true if the VPUser uses scalars of operand \p Op. Conservatively
371 /// returns if only first (scalar) lane is used, as default.
372 virtual bool usesScalars(const VPValue *Op) const {
373 assert(is_contained(operands(), Op) &&
374 "Op must be an operand of the recipe");
375 return usesFirstLaneOnly(Op);
376 }
377
378 /// Returns true if the VPUser only uses the first lane of operand \p Op.
379 /// Conservatively returns false.
380 virtual bool usesFirstLaneOnly(const VPValue *Op) const {
381 assert(is_contained(operands(), Op) &&
382 "Op must be an operand of the recipe");
383 return false;
384 }
385
386 /// Returns true if the VPUser only uses the first part of operand \p Op.
387 /// Conservatively returns false.
388 virtual bool usesFirstPartOnly(const VPValue *Op) const {
389 assert(is_contained(operands(), Op) &&
390 "Op must be an operand of the recipe");
391 return false;
392 }
393};
394
395/// This class augments a recipe with a set of VPValues defined by the recipe.
396/// It allows recipes to define zero, one or multiple VPValues. A VPDef owns
397/// the VPValues it defines and is responsible for deleting its defined values.
398/// Single-value VPDefs that also inherit from VPValue must make sure to inherit
399/// from VPDef before VPValue.
400class VPDef {
401 friend class VPRecipeValue;
402
403 /// The VPValues defined by this VPDef.
404 TinyPtrVector<VPRecipeValue *> DefinedValues;
405
406 /// Add \p V as a defined value by this VPDef.
407 void addDefinedValue(VPRecipeValue *V) {
408 assert(V->isDefinedBy(this) &&
409 "can only add VPValue already linked with this VPDef");
410 DefinedValues.push_back(NewVal: V);
411 }
412
413 /// Remove \p V from the values defined by this VPDef. \p V must be a defined
414 /// value of this VPDef.
415 void removeDefinedValue(VPRecipeValue *V) {
416 assert(V->isDefinedBy(this) &&
417 "can only remove VPValue linked with this VPDef");
418 assert(is_contained(DefinedValues, V) &&
419 "VPValue to remove must be in DefinedValues");
420 llvm::erase(C&: DefinedValues, V);
421 V->Def = nullptr;
422 }
423
424public:
425 VPDef() {}
426
427 virtual ~VPDef() {
428 for (VPRecipeValue *D : to_vector(Range&: DefinedValues)) {
429 assert(D->isDefinedBy(this) &&
430 "all defined VPValues should point to the containing VPDef");
431 assert(D->getNumUsers() == 0 &&
432 "all defined VPValues should have no more users");
433 delete D;
434 }
435 }
436
437 /// Returns the only VPValue defined by the VPDef. Can only be called for
438 /// VPDefs with a single defined value.
439 VPValue *getVPSingleValue() {
440 assert(DefinedValues.size() == 1 && "must have exactly one defined value");
441 assert(DefinedValues[0] && "defined value must be non-null");
442 return DefinedValues[0];
443 }
444 const VPValue *getVPSingleValue() const {
445 assert(DefinedValues.size() == 1 && "must have exactly one defined value");
446 assert(DefinedValues[0] && "defined value must be non-null");
447 return DefinedValues[0];
448 }
449
450 /// Returns the VPValue with index \p I defined by the VPDef.
451 VPValue *getVPValue(unsigned I) {
452 assert(DefinedValues[I] && "defined value must be non-null");
453 return DefinedValues[I];
454 }
455 const VPValue *getVPValue(unsigned I) const {
456 assert(DefinedValues[I] && "defined value must be non-null");
457 return DefinedValues[I];
458 }
459
460 /// Returns an ArrayRef of the values defined by the VPDef.
461 ArrayRef<VPRecipeValue *> definedValues() { return DefinedValues; }
462 /// Returns an ArrayRef of the values defined by the VPDef.
463 ArrayRef<VPRecipeValue *> definedValues() const { return DefinedValues; }
464
465 /// Returns the number of values defined by the VPDef.
466 unsigned getNumDefinedValues() const { return DefinedValues.size(); }
467};
468
469inline void VPValue::assertNotMaterialized() const {
470 assert((!isa<VPSymbolicValue>(this) ||
471 !cast<VPSymbolicValue>(this)->isMaterialized()) &&
472 "accessing materialized symbolic value");
473}
474
475} // namespace llvm
476
477#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
478