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