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