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