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 unsigned getNumUsers() const { return Users.size(); }
105 void addUser(VPUser &User) { Users.push_back(Elt: &User); }
106
107 /// Remove a single \p User from the list of users.
108 void removeUser(VPUser &User) {
109 // The same user can be added multiple times, e.g. because the same VPValue
110 // is used twice by the same VPUser. Remove a single one.
111 auto *I = find(Range&: Users, Val: &User);
112 if (I != Users.end())
113 Users.erase(CI: I);
114 }
115
116 typedef SmallVectorImpl<VPUser *>::iterator user_iterator;
117 typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator;
118 typedef iterator_range<user_iterator> user_range;
119 typedef iterator_range<const_user_iterator> const_user_range;
120
121 user_iterator user_begin() { return Users.begin(); }
122 const_user_iterator user_begin() const { return Users.begin(); }
123 user_iterator user_end() { return Users.end(); }
124 const_user_iterator user_end() const { return Users.end(); }
125 user_range users() { return user_range(user_begin(), user_end()); }
126 const_user_range users() const {
127 return const_user_range(user_begin(), user_end());
128 }
129
130 /// Returns true if the value has more than one unique user.
131 bool hasMoreThanOneUniqueUser() const {
132 if (getNumUsers() == 0)
133 return false;
134
135 // Check if all users match the first user.
136 auto Current = std::next(x: user_begin());
137 while (Current != user_end() && *user_begin() == *Current)
138 Current++;
139 return Current != user_end();
140 }
141
142 bool hasOneUse() const { return getNumUsers() == 1; }
143
144 /// Return the single user of this value, or nullptr if there is not exactly
145 /// one user.
146 VPUser *getSingleUser() { return hasOneUse() ? *user_begin() : nullptr; }
147 const VPUser *getSingleUser() const {
148 return hasOneUse() ? *user_begin() : nullptr;
149 }
150
151 void replaceAllUsesWith(VPValue *New);
152
153 /// Go through the uses list for this VPValue and make each use point to \p
154 /// New if the callback ShouldReplace returns true for the given use specified
155 /// by a pair of (VPUser, the use index).
156 void replaceUsesWithIf(
157 VPValue *New,
158 llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace);
159
160 /// Returns the recipe defining this VPValue or nullptr if it is not defined
161 /// by a recipe, i.e. is a live-in.
162 VPRecipeBase *getDefiningRecipe();
163 const VPRecipeBase *getDefiningRecipe() const;
164
165 /// Returns true if this VPValue is defined by a recipe.
166 bool hasDefiningRecipe() const { return getDefiningRecipe(); }
167
168 /// Returns true if the VPValue is defined outside any loop.
169 bool isDefinedOutsideLoopRegions() const;
170
171 // Set \p Val as the underlying Value of this VPValue.
172 void setUnderlyingValue(Value *Val) {
173 assert(!UnderlyingVal && "Underlying Value is already set.");
174 UnderlyingVal = Val;
175 }
176};
177
178LLVM_ABI_FOR_TEST raw_ostream &operator<<(raw_ostream &OS,
179 const VPRecipeBase &R);
180
181/// A VPValue representing a live-in from the input IR or a constant. It wraps
182/// an underlying IR Value.
183struct VPIRValue : public VPValue {
184 VPIRValue(Value *UV) : VPValue(VPVIRValueSC, UV) {
185 assert(UV && "VPIRValue requires an underlying IR value");
186 }
187
188 /// Returns the underlying IR value.
189 Value *getValue() const { return getUnderlyingValue(); }
190
191 /// Returns the type of the underlying IR value.
192 Type *getType() const;
193
194 static bool classof(const VPValue *V) {
195 return V->getVPValueID() == VPVIRValueSC;
196 }
197};
198
199/// An overlay on VPIRValue for VPValues that wrap a ConstantInt. Provides
200/// convenient accessors for the underlying constant.
201struct VPConstantInt : public VPIRValue {
202 VPConstantInt(ConstantInt *CI) : VPIRValue(CI) {}
203
204 static bool classof(const VPValue *V) {
205 return isa<VPIRValue>(Val: V) && isa<ConstantInt>(Val: V->getUnderlyingValue());
206 }
207
208 bool isOne() const { return getAPInt().isOne(); }
209
210 bool isZero() const { return getAPInt().isZero(); }
211
212 const APInt &getAPInt() const {
213 return cast<ConstantInt>(Val: getValue())->getValue();
214 }
215
216 unsigned getBitWidth() const { return getAPInt().getBitWidth(); }
217
218 uint64_t getZExtValue() const { return getAPInt().getZExtValue(); }
219};
220
221/// A symbolic live-in VPValue, used for values like vector trip count, VF, and
222/// VFxUF.
223struct VPSymbolicValue : public VPValue {
224 VPSymbolicValue() : VPValue(VPVSymbolicSC, nullptr) {}
225
226 static bool classof(const VPValue *V) {
227 return V->getVPValueID() == VPVSymbolicSC;
228 }
229};
230
231/// A VPValue defined by a recipe that produces one or more values.
232class VPRecipeValue : public VPValue {
233 friend class VPValue;
234 friend class VPDef;
235
236 /// Pointer to the VPRecipeBase that defines this VPValue.
237 VPRecipeBase *Def;
238
239#if !defined(NDEBUG)
240 /// Returns true if this VPRecipeValue is defined by \p D.
241 /// NOTE: Only used by VPDef to assert that VPRecipeValues added/removed from
242 /// /p D are associated with its VPRecipeBase,
243 bool isDefinedBy(const VPDef *D) const;
244#endif
245
246public:
247 LLVM_ABI_FOR_TEST VPRecipeValue(VPRecipeBase *Def, Value *UV = nullptr);
248
249 LLVM_ABI_FOR_TEST virtual ~VPRecipeValue();
250
251 static bool classof(const VPValue *V) {
252 return V->getVPValueID() == VPVRecipeValueSC;
253 }
254};
255
256/// This class augments VPValue with operands which provide the inverse def-use
257/// edges from VPValue's users to their defs.
258class VPUser {
259 /// Grant access to removeOperand for VPPhiAccessors, the only supported user.
260 friend class VPPhiAccessors;
261
262 SmallVector<VPValue *, 2> Operands;
263
264 /// Removes the operand at index \p Idx. This also removes the VPUser from the
265 /// use-list of the operand.
266 void removeOperand(unsigned Idx) {
267 getOperand(N: Idx)->removeUser(User&: *this);
268 Operands.erase(CI: Operands.begin() + Idx);
269 }
270
271protected:
272#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
273 /// Print the operands to \p O.
274 void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;
275#endif
276
277 VPUser(ArrayRef<VPValue *> Operands) {
278 for (VPValue *Operand : Operands)
279 addOperand(Operand);
280 }
281
282public:
283 VPUser() = delete;
284 VPUser(const VPUser &) = delete;
285 VPUser &operator=(const VPUser &) = delete;
286 virtual ~VPUser() {
287 for (VPValue *Op : operands())
288 Op->removeUser(User&: *this);
289 }
290
291 void addOperand(VPValue *Operand) {
292 Operands.push_back(Elt: Operand);
293 Operand->addUser(User&: *this);
294 }
295
296 unsigned getNumOperands() const { return Operands.size(); }
297 inline VPValue *getOperand(unsigned N) const {
298 assert(N < Operands.size() && "Operand index out of bounds");
299 return Operands[N];
300 }
301
302 void setOperand(unsigned I, VPValue *New) {
303 Operands[I]->removeUser(User&: *this);
304 Operands[I] = New;
305 New->addUser(User&: *this);
306 }
307
308 /// Swap operands of the VPUser. It must have exactly 2 operands.
309 void swapOperands() {
310 assert(Operands.size() == 2 && "must have 2 operands to swap");
311 std::swap(a&: Operands[0], b&: Operands[1]);
312 }
313
314 /// Replaces all uses of \p From in the VPUser with \p To.
315 void replaceUsesOfWith(VPValue *From, VPValue *To);
316
317 typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
318 typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
319 typedef iterator_range<operand_iterator> operand_range;
320 typedef iterator_range<const_operand_iterator> const_operand_range;
321
322 operand_iterator op_begin() { return Operands.begin(); }
323 const_operand_iterator op_begin() const { return Operands.begin(); }
324 operand_iterator op_end() { return Operands.end(); }
325 const_operand_iterator op_end() const { return Operands.end(); }
326 operand_range operands() { return operand_range(op_begin(), op_end()); }
327 const_operand_range operands() const {
328 return const_operand_range(op_begin(), op_end());
329 }
330
331 /// Returns true if the VPUser uses scalars of operand \p Op. Conservatively
332 /// returns if only first (scalar) lane is used, as default.
333 virtual bool usesScalars(const VPValue *Op) const {
334 assert(is_contained(operands(), Op) &&
335 "Op must be an operand of the recipe");
336 return usesFirstLaneOnly(Op);
337 }
338
339 /// Returns true if the VPUser only uses the first lane of operand \p Op.
340 /// Conservatively returns false.
341 virtual bool usesFirstLaneOnly(const VPValue *Op) const {
342 assert(is_contained(operands(), Op) &&
343 "Op must be an operand of the recipe");
344 return false;
345 }
346
347 /// Returns true if the VPUser only uses the first part of operand \p Op.
348 /// Conservatively returns false.
349 virtual bool usesFirstPartOnly(const VPValue *Op) const {
350 assert(is_contained(operands(), Op) &&
351 "Op must be an operand of the recipe");
352 return false;
353 }
354};
355
356/// This class augments a recipe with a set of VPValues defined by the recipe.
357/// It allows recipes to define zero, one or multiple VPValues. A VPDef owns
358/// the VPValues it defines and is responsible for deleting its defined values.
359/// Single-value VPDefs that also inherit from VPValue must make sure to inherit
360/// from VPDef before VPValue.
361class VPDef {
362 friend class VPRecipeValue;
363
364 /// The VPValues defined by this VPDef.
365 TinyPtrVector<VPRecipeValue *> DefinedValues;
366
367 /// Add \p V as a defined value by this VPDef.
368 void addDefinedValue(VPRecipeValue *V) {
369 assert(V->isDefinedBy(this) &&
370 "can only add VPValue already linked with this VPDef");
371 DefinedValues.push_back(NewVal: V);
372 }
373
374 /// Remove \p V from the values defined by this VPDef. \p V must be a defined
375 /// value of this VPDef.
376 void removeDefinedValue(VPRecipeValue *V) {
377 assert(V->isDefinedBy(this) &&
378 "can only remove VPValue linked with this VPDef");
379 assert(is_contained(DefinedValues, V) &&
380 "VPValue to remove must be in DefinedValues");
381 llvm::erase(C&: DefinedValues, V);
382 V->Def = nullptr;
383 }
384
385public:
386 VPDef() {}
387
388 virtual ~VPDef() {
389 for (VPRecipeValue *D : to_vector(Range&: DefinedValues)) {
390 assert(D->isDefinedBy(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 delete D;
395 }
396 }
397
398 /// Returns the only VPValue defined by the VPDef. Can only be called for
399 /// VPDefs with a single defined value.
400 VPValue *getVPSingleValue() {
401 assert(DefinedValues.size() == 1 && "must have exactly one defined value");
402 assert(DefinedValues[0] && "defined value must be non-null");
403 return DefinedValues[0];
404 }
405 const VPValue *getVPSingleValue() const {
406 assert(DefinedValues.size() == 1 && "must have exactly one defined value");
407 assert(DefinedValues[0] && "defined value must be non-null");
408 return DefinedValues[0];
409 }
410
411 /// Returns the VPValue with index \p I defined by the VPDef.
412 VPValue *getVPValue(unsigned I) {
413 assert(DefinedValues[I] && "defined value must be non-null");
414 return DefinedValues[I];
415 }
416 const VPValue *getVPValue(unsigned I) const {
417 assert(DefinedValues[I] && "defined value must be non-null");
418 return DefinedValues[I];
419 }
420
421 /// Returns an ArrayRef of the values defined by the VPDef.
422 ArrayRef<VPRecipeValue *> definedValues() { return DefinedValues; }
423 /// Returns an ArrayRef of the values defined by the VPDef.
424 ArrayRef<VPRecipeValue *> definedValues() const { return DefinedValues; }
425
426 /// Returns the number of values defined by the VPDef.
427 unsigned getNumDefinedValues() const { return DefinedValues.size(); }
428};
429
430} // namespace llvm
431
432#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
433