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 class 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 VPUser.
188 void replaceUsesWithIf(VPValue *New,
189 llvm::function_ref<bool(VPUser *U)> ShouldReplace);
190
191 /// Returns the recipe defining this VPValue or nullptr if it is not defined
192 /// by a recipe, i.e. is a live-in.
193 VPRecipeBase *getDefiningRecipe();
194 const VPRecipeBase *getDefiningRecipe() const;
195
196 /// Returns the scalar type of this VPValue, dispatching based on the
197 /// concrete subclass.
198 Type *getScalarType() const;
199
200 /// Returns true if the VPValue is defined outside any loop.
201 bool isDefinedOutsideLoopRegions() const;
202
203 // Set \p Val as the underlying Value of this VPValue.
204 void setUnderlyingValue(Value *Val) {
205 assert(!UnderlyingVal && "Underlying Value is already set.");
206 UnderlyingVal = Val;
207 }
208};
209
210/// A symbolic live-in VPValue, used for values like vector trip count, VF, and
211/// VFxUF.
212class VPSymbolicValue : public VPValue {
213 /// The scalar type of this symbolic value.
214 Type *Ty;
215
216 /// Track whether this value has been materialized (replaced). After
217 /// materialization, accessing users should trigger an assertion.
218 bool Materialized = false;
219
220protected:
221 VPSymbolicValue(unsigned char SC, Type *Ty) : VPValue(SC, nullptr), Ty(Ty) {}
222
223public:
224 VPSymbolicValue(Type *Ty) : VPSymbolicValue(VPVSymbolicSC, Ty) {}
225
226 /// Returns the scalar type of this symbolic value.
227 Type *getType() const { return Ty; }
228
229 /// Returns true if this value has been materialized.
230 bool isMaterialized() const { return Materialized; }
231
232 /// Mark this value as materialized.
233 void markMaterialized() {
234 assert(!Materialized && "VPSymbolicValue already materialized");
235 Materialized = true;
236 }
237
238 static bool classof(const VPValue *V) {
239 return V->getVPValueID() == VPVSymbolicSC ||
240 V->getVPValueID() == VPRegionValueSC;
241 }
242};
243
244/// VPValues are defined by a VPRegionBlock, like the canonical IV. They must
245/// be materialized when the containing region is dissolved, before VPlan
246/// execution.
247class VPRegionValue : public VPSymbolicValue {
248 VPRegionBlock *DefiningRegion;
249 DebugLoc DL;
250
251public:
252 VPRegionValue(Type *Ty, DebugLoc DL, VPRegionBlock *Region)
253 : VPSymbolicValue(VPValue::VPRegionValueSC, Ty), DefiningRegion(Region),
254 DL(DL) {}
255
256 ~VPRegionValue() override = default;
257
258 /// Returns the region that defines this value.
259 VPRegionBlock *getDefiningRegion() const { return DefiningRegion; }
260
261 /// Returns the debug location of the VPRegionValue.
262 DebugLoc getDebugLoc() const { return DL; }
263
264 static inline bool classof(const VPValue *V) {
265 return V->getVPValueID() == VPValue::VPRegionValueSC;
266 }
267};
268
269LLVM_ABI_FOR_TEST raw_ostream &operator<<(raw_ostream &OS,
270 const VPRecipeBase &R);
271
272/// A VPValue representing a live-in from the input IR or a constant. It wraps
273/// an underlying IR Value.
274struct VPIRValue : public VPValue {
275 VPIRValue(Value *UV) : VPValue(VPVIRValueSC, UV) {
276 assert(UV && "VPIRValue requires an underlying IR value");
277 }
278
279 /// Returns the underlying IR value.
280 Value *getValue() const { return getUnderlyingValue(); }
281
282 /// Returns the type of the underlying IR value.
283 Type *getType() const;
284
285 static bool classof(const VPValue *V) {
286 return V->getVPValueID() == VPVIRValueSC;
287 }
288};
289
290/// An overlay on VPIRValue for VPValues that wrap a Constant. May be an
291/// integer, floating-point, or a vector constant.
292struct VPConstant : public VPIRValue {
293 VPConstant(Constant *C) : VPIRValue(C) {}
294
295 static bool classof(const VPValue *V) {
296 auto *IRV = dyn_cast<VPIRValue>(Val: V);
297 return IRV && isa<Constant>(Val: IRV->getValue());
298 }
299
300 const Constant *getConstant() const { return cast<Constant>(Val: getValue()); }
301};
302
303/// An overlay on VPConstant for VPValues that wrap a ConstantInt. Provides
304/// convenient accessors for the underlying APInt.
305struct VPConstantInt : public VPConstant {
306 VPConstantInt(ConstantInt *CI) : VPConstant(CI) {}
307
308 static bool classof(const VPValue *V) {
309 auto *VPC = dyn_cast<VPConstant>(Val: V);
310 return VPC && isa<ConstantInt>(Val: VPC->getConstant());
311 }
312
313 bool isOne() const { return getAPInt().isOne(); }
314
315 bool isZero() const { return getAPInt().isZero(); }
316
317 const APInt &getAPInt() const {
318 return cast<ConstantInt>(Val: getValue())->getValue();
319 }
320
321 unsigned getBitWidth() const { return getAPInt().getBitWidth(); }
322
323 uint64_t getZExtValue() const { return getAPInt().getZExtValue(); }
324};
325
326/// Abstract base class for VPValues defined by a VPRecipeBase.
327class VPRecipeValue : public VPValue {
328 friend class VPValue;
329 friend class VPDef;
330
331 /// The scalar type of the value produced by this recipe.
332 Type *Ty = nullptr;
333
334#if !defined(NDEBUG)
335 /// Returns true if this VPRecipeValue is defined by \p D.
336 /// NOTE: Only used by VPDef to assert that VPRecipeValues added/removed from
337 /// /p D are associated with its VPRecipeBase.
338 LLVM_ABI_FOR_TEST bool isDefinedBy(const VPDef *D) const;
339#endif
340
341protected:
342 VPRecipeValue(unsigned char SC, Value *UV, Type *Ty = nullptr)
343 : VPValue(SC, UV), Ty(Ty) {}
344
345public:
346 LLVM_ABI_FOR_TEST virtual ~VPRecipeValue() = 0;
347
348 /// Returns the scalar type of this VPRecipeValue.
349 Type *getScalarType() const { return Ty; }
350
351 static bool classof(const VPValue *V) {
352 return V->getVPValueID() == VPVMultiDefValueSC ||
353 V->getVPValueID() == VPVSingleDefValueSC;
354 }
355};
356
357/// A VPRecipeValue defined by a VPSingleDefRecipe.
358class LLVM_ABI_FOR_TEST VPSingleDefValue : public VPRecipeValue {
359 friend class VPDef;
360 friend class VPSingleDefRecipe;
361
362protected:
363 /// Construct a VPSingleDefValue. Must only be used by VPSingleDefRecipe.
364 VPSingleDefValue(VPSingleDefRecipe *Def, Value *UV = nullptr,
365 Type *Ty = nullptr);
366
367public:
368 ~VPSingleDefValue() override;
369
370 static bool classof(const VPValue *V) {
371 return V->getVPValueID() == VPVSingleDefValueSC;
372 }
373};
374
375/// A VPRecipeValue defined by a multi-def recipe, stores a pointer to it.
376class VPMultiDefValue : public VPRecipeValue {
377 friend class VPDef;
378
379 /// Pointer to the multi-def recipe that defines this VPValue, among others.
380 VPRecipeBase *Def;
381
382public:
383 LLVM_ABI_FOR_TEST VPMultiDefValue(VPRecipeBase *Def, Value *UV, Type *Ty);
384
385 ~VPMultiDefValue() override;
386
387 VPRecipeBase *getDef() const { return Def; }
388
389 static bool classof(const VPValue *V) {
390 return V->getVPValueID() == VPVMultiDefValueSC;
391 }
392};
393
394/// This class augments VPValue with operands which provide the inverse def-use
395/// edges from VPValue's users to their defs.
396class LLVM_ABI_FOR_TEST VPUser {
397 /// Grant access to removeOperand for VPPhiAccessors, the only supported user.
398 friend class VPPhiAccessors;
399 /// Grant access to addOperand for VPWidenMemoryRecipe.
400 friend class VPWidenMemoryRecipe;
401
402 SmallVector<VPValue *, 2> Operands;
403
404 /// Removes the operand at index \p Idx. This also removes the VPUser from the
405 /// use-list of the operand.
406 void removeOperand(unsigned Idx) {
407 getOperand(N: Idx)->removeUser(User&: *this);
408 Operands.erase(CI: Operands.begin() + Idx);
409 }
410
411protected:
412#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
413 /// Print the operands to \p O.
414 void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;
415#endif
416
417 VPUser(ArrayRef<VPValue *> Operands) {
418 for (VPValue *Operand : Operands)
419 addOperand(Operand);
420 }
421
422 void addOperand(VPValue *Operand) {
423 Operands.push_back(Elt: Operand);
424 Operand->addUser(User&: *this);
425 }
426
427public:
428 VPUser() = delete;
429 VPUser(const VPUser &) = delete;
430 VPUser &operator=(const VPUser &) = delete;
431 virtual ~VPUser() {
432 for (VPValue *Op : operands())
433 Op->removeUser(User&: *this);
434 }
435
436 unsigned getNumOperands() const { return Operands.size(); }
437 inline VPValue *getOperand(unsigned N) const {
438 assert(N < Operands.size() && "Operand index out of bounds");
439 return Operands[N];
440 }
441
442 /// Returns the last operand.
443 VPValue *getLastOperand() const { return Operands.back(); }
444
445 void setOperand(unsigned I, VPValue *New) {
446 assert((!Operands[I]->getScalarType() || !New->getScalarType() ||
447 Operands[I]->getScalarType() == New->getScalarType()) &&
448 "scalar type of new operand must match the old operand");
449 Operands[I]->removeUser(User&: *this);
450 Operands[I] = New;
451 New->addUser(User&: *this);
452 }
453
454 /// Swap operands of the VPUser. It must have exactly 2 operands.
455 void swapOperands() {
456 assert(Operands.size() == 2 && "must have 2 operands to swap");
457 std::swap(a&: Operands[0], b&: Operands[1]);
458 }
459
460 /// Replaces all uses of \p From in the VPUser with \p To.
461 void replaceUsesOfWith(VPValue *From, VPValue *To);
462
463 typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
464 typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
465 typedef iterator_range<operand_iterator> operand_range;
466 typedef iterator_range<const_operand_iterator> const_operand_range;
467
468 operand_iterator op_begin() { return Operands.begin(); }
469 const_operand_iterator op_begin() const { return Operands.begin(); }
470 operand_iterator op_end() { return Operands.end(); }
471 const_operand_iterator op_end() const { return Operands.end(); }
472 operand_range operands() { return operand_range(op_begin(), op_end()); }
473 const_operand_range operands() const {
474 return const_operand_range(op_begin(), op_end());
475 }
476 bool operands_empty() const { return Operands.empty(); } // NOLINT
477
478 /// Returns true if the VPUser uses scalars of operand \p Op. Conservatively
479 /// returns if only first (scalar) lane is used, as default.
480 virtual bool usesScalars(const VPValue *Op) const {
481 assert(is_contained(operands(), Op) &&
482 "Op must be an operand of the recipe");
483 return usesFirstLaneOnly(Op);
484 }
485
486 /// Returns true if the VPUser only uses the first lane of operand \p Op.
487 /// Conservatively returns false.
488 virtual bool usesFirstLaneOnly(const VPValue *Op) const {
489 assert(is_contained(operands(), Op) &&
490 "Op must be an operand of the recipe");
491 return false;
492 }
493
494 /// Returns true if the VPUser only uses the first part of operand \p Op.
495 /// Conservatively returns false.
496 virtual bool usesFirstPartOnly(const VPValue *Op) const {
497 assert(is_contained(operands(), Op) &&
498 "Op must be an operand of the recipe");
499 return false;
500 }
501};
502
503/// This class augments a recipe with a set of VPValues defined by the recipe.
504/// It allows recipes to define zero, one or multiple VPValues. A VPDef owns
505/// the VPValues it defines and is responsible for deleting its defined values.
506/// Single-value VPDefs that also inherit from VPValue must make sure to inherit
507/// from VPDef before VPValue.
508class VPDef {
509 friend class VPRecipeValue;
510 friend class VPSingleDefValue;
511 friend class VPMultiDefValue;
512
513 /// The VPValues defined by this VPDef.
514 TinyPtrVector<VPRecipeValue *> DefinedValues;
515
516 /// Add \p V as a defined value by this VPDef.
517 void addDefinedValue(VPRecipeValue *V) {
518 assert(V->isDefinedBy(this) &&
519 "can only add VPValue already linked with this VPDef");
520 DefinedValues.push_back(NewVal: V);
521 }
522
523 /// Remove \p V from the values defined by this VPDef. \p V must be a defined
524 /// value of this VPDef.
525 void removeDefinedValue(VPRecipeValue *V) {
526 assert(V->isDefinedBy(this) &&
527 "can only remove VPValue linked with this VPDef");
528 assert(is_contained(DefinedValues, V) &&
529 "VPValue to remove must be in DefinedValues");
530 llvm::erase(C&: DefinedValues, V);
531 if (auto *SV = dyn_cast<VPMultiDefValue>(Val: V))
532 SV->Def = nullptr;
533 }
534
535public:
536 VPDef() {}
537
538 virtual ~VPDef() {
539 for (VPRecipeValue *D : to_vector(Range&: DefinedValues)) {
540 assert(D->isDefinedBy(this) &&
541 "all defined VPValues should point to the containing VPDef");
542 assert(D->user_empty() &&
543 "all defined VPValues should have no more users");
544 delete D;
545 }
546 }
547
548 /// Returns the only VPValue defined by the VPDef. Can only be called for
549 /// VPDefs with a single defined value.
550 VPValue *getVPSingleValue() {
551 assert(DefinedValues.size() == 1 && "must have exactly one defined value");
552 assert(DefinedValues[0] && "defined value must be non-null");
553 return DefinedValues[0];
554 }
555 const VPValue *getVPSingleValue() const {
556 assert(DefinedValues.size() == 1 && "must have exactly one defined value");
557 assert(DefinedValues[0] && "defined value must be non-null");
558 return DefinedValues[0];
559 }
560
561 /// Returns the VPValue with index \p I defined by the VPDef.
562 VPValue *getVPValue(unsigned I) {
563 assert(DefinedValues[I] && "defined value must be non-null");
564 return DefinedValues[I];
565 }
566 const VPValue *getVPValue(unsigned I) const {
567 assert(DefinedValues[I] && "defined value must be non-null");
568 return DefinedValues[I];
569 }
570
571 /// Returns an ArrayRef of the values defined by the VPDef.
572 ArrayRef<VPRecipeValue *> definedValues() { return DefinedValues; }
573 /// Returns an ArrayRef of the values defined by the VPDef.
574 ArrayRef<VPRecipeValue *> definedValues() const { return DefinedValues; }
575
576 /// Returns the number of values defined by the VPDef.
577 unsigned getNumDefinedValues() const { return DefinedValues.size(); }
578};
579
580inline void VPValue::assertNotMaterialized() const {
581 assert((!isa<VPSymbolicValue>(this) ||
582 !cast<VPSymbolicValue>(this)->isMaterialized()) &&
583 "accessing materialized symbolic value");
584}
585
586} // namespace llvm
587
588#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
589