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(VPValue *New,
190 llvm::function_ref<bool(VPUser &U)> ShouldReplace);
191
192 /// Returns the recipe defining this VPValue or nullptr if it is not defined
193 /// by a recipe, i.e. is a live-in.
194 VPRecipeBase *getDefiningRecipe();
195 const VPRecipeBase *getDefiningRecipe() const;
196
197 /// Returns the scalar type of this VPValue, dispatching based on the
198 /// concrete subclass.
199 Type *getScalarType() const;
200
201 /// Returns true if the VPValue is defined outside any loop.
202 bool isDefinedOutsideLoopRegions() const;
203
204 // Set \p Val as the underlying Value of this VPValue.
205 void setUnderlyingValue(Value *Val) {
206 assert(!UnderlyingVal && "Underlying Value is already set.");
207 UnderlyingVal = Val;
208 }
209};
210
211/// A symbolic live-in VPValue, used for values like vector trip count, VF, and
212/// VFxUF.
213class VPSymbolicValue : public VPValue {
214 /// The scalar type of this symbolic value.
215 Type *Ty;
216
217 /// Track whether this value has been materialized (replaced). After
218 /// materialization, accessing users should trigger an assertion.
219 bool Materialized = false;
220
221protected:
222 VPSymbolicValue(unsigned char SC, Type *Ty) : VPValue(SC, nullptr), Ty(Ty) {}
223
224public:
225 VPSymbolicValue(Type *Ty) : VPSymbolicValue(VPVSymbolicSC, Ty) {}
226
227 /// Returns the scalar type of this symbolic value.
228 Type *getType() const { return Ty; }
229
230 /// Returns true if this value has been materialized.
231 bool isMaterialized() const { return Materialized; }
232
233 /// Mark this value as materialized.
234 void markMaterialized() {
235 assert(!Materialized && "VPSymbolicValue already materialized");
236 Materialized = true;
237 }
238
239 static bool classof(const VPValue *V) {
240 return V->getVPValueID() == VPVSymbolicSC ||
241 V->getVPValueID() == VPRegionValueSC;
242 }
243};
244
245/// VPValues are defined by a VPRegionBlock, like the canonical IV. They must
246/// be materialized when the containing region is dissolved, before VPlan
247/// execution.
248class VPRegionValue : public VPSymbolicValue {
249 VPRegionBlock *DefiningRegion;
250 DebugLoc DL;
251
252public:
253 VPRegionValue(Type *Ty, DebugLoc DL, VPRegionBlock *Region)
254 : VPSymbolicValue(VPValue::VPRegionValueSC, Ty), DefiningRegion(Region),
255 DL(DL) {}
256
257 ~VPRegionValue() override = default;
258
259 /// Returns the region that defines this value.
260 VPRegionBlock *getDefiningRegion() const { return DefiningRegion; }
261
262 /// Returns the debug location of the VPRegionValue.
263 DebugLoc getDebugLoc() const { return DL; }
264
265 static inline bool classof(const VPValue *V) {
266 return V->getVPValueID() == VPValue::VPRegionValueSC;
267 }
268};
269
270LLVM_ABI_FOR_TEST raw_ostream &operator<<(raw_ostream &OS,
271 const VPRecipeBase &R);
272
273/// A VPValue representing a live-in from the input IR or a constant. It wraps
274/// an underlying IR Value.
275struct VPIRValue : public VPValue {
276 VPIRValue(Value *UV) : VPValue(VPVIRValueSC, UV) {
277 assert(UV && "VPIRValue requires an underlying IR value");
278 }
279
280 /// Returns the underlying IR value.
281 Value *getValue() const { return getUnderlyingValue(); }
282
283 /// Returns the type of the underlying IR value.
284 Type *getType() const;
285
286 static bool classof(const VPValue *V) {
287 return V->getVPValueID() == VPVIRValueSC;
288 }
289};
290
291/// An overlay on VPIRValue for VPValues that wrap a Constant. May be an
292/// integer, floating-point, or a vector constant.
293struct VPConstant : public VPIRValue {
294 VPConstant(Constant *C) : VPIRValue(C) {}
295
296 static bool classof(const VPValue *V) {
297 auto *IRV = dyn_cast<VPIRValue>(Val: V);
298 return IRV && isa<Constant>(Val: IRV->getValue());
299 }
300
301 const Constant *getConstant() const { return cast<Constant>(Val: getValue()); }
302};
303
304/// An overlay on VPConstant for VPValues that wrap a ConstantInt. Provides
305/// convenient accessors for the underlying APInt.
306struct VPConstantInt : public VPConstant {
307 VPConstantInt(ConstantInt *CI) : VPConstant(CI) {}
308
309 static bool classof(const VPValue *V) {
310 auto *VPC = dyn_cast<VPConstant>(Val: V);
311 return VPC && isa<ConstantInt>(Val: VPC->getConstant());
312 }
313
314 bool isOne() const { return getAPInt().isOne(); }
315
316 bool isZero() const { return getAPInt().isZero(); }
317
318 const APInt &getAPInt() const {
319 return cast<ConstantInt>(Val: getValue())->getValue();
320 }
321
322 unsigned getBitWidth() const { return getAPInt().getBitWidth(); }
323
324 uint64_t getZExtValue() const { return getAPInt().getZExtValue(); }
325};
326
327/// Abstract base class for VPValues defined by a VPRecipeBase.
328class VPRecipeValue : public VPValue {
329 friend class VPValue;
330 friend class VPDef;
331
332 /// The scalar type of the value produced by this recipe.
333 Type *Ty = nullptr;
334
335#if !defined(NDEBUG)
336 /// Returns true if this VPRecipeValue is defined by \p D.
337 /// NOTE: Only used by VPDef to assert that VPRecipeValues added/removed from
338 /// /p D are associated with its VPRecipeBase.
339 bool isDefinedBy(const VPDef *D) const;
340#endif
341
342protected:
343 VPRecipeValue(unsigned char SC, Value *UV, Type *Ty = nullptr)
344 : VPValue(SC, UV), Ty(Ty) {}
345
346public:
347 LLVM_ABI_FOR_TEST virtual ~VPRecipeValue() = 0;
348
349 /// Returns the scalar type of this VPRecipeValue.
350 Type *getScalarType() const { return Ty; }
351
352 static bool classof(const VPValue *V) {
353 return V->getVPValueID() == VPVMultiDefValueSC ||
354 V->getVPValueID() == VPVSingleDefValueSC;
355 }
356};
357
358/// A VPRecipeValue defined by a VPSingleDefRecipe.
359class LLVM_ABI_FOR_TEST VPSingleDefValue : public VPRecipeValue {
360 friend class VPDef;
361 friend class VPSingleDefRecipe;
362
363protected:
364 /// Construct a VPSingleDefValue. Must only be used by VPSingleDefRecipe.
365 VPSingleDefValue(VPSingleDefRecipe *Def, Value *UV = nullptr,
366 Type *Ty = nullptr);
367
368public:
369 ~VPSingleDefValue() override;
370
371 static bool classof(const VPValue *V) {
372 return V->getVPValueID() == VPVSingleDefValueSC;
373 }
374};
375
376/// A VPRecipeValue defined by a multi-def recipe, stores a pointer to it.
377class VPMultiDefValue : public VPRecipeValue {
378 friend class VPDef;
379
380 /// Pointer to the multi-def recipe that defines this VPValue, among others.
381 VPRecipeBase *Def;
382
383public:
384 LLVM_ABI_FOR_TEST VPMultiDefValue(VPRecipeBase *Def, Value *UV, Type *Ty);
385
386 ~VPMultiDefValue() override;
387
388 VPRecipeBase *getDef() const { return Def; }
389
390 static bool classof(const VPValue *V) {
391 return V->getVPValueID() == VPVMultiDefValueSC;
392 }
393};
394
395/// This class augments VPValue with operands which provide the inverse def-use
396/// edges from VPValue's users to their defs.
397class LLVM_ABI_FOR_TEST VPUser {
398 /// Grant access to removeOperand for VPPhiAccessors, the only supported user.
399 friend class VPPhiAccessors;
400 /// Grant access to addOperand for VPWidenMemoryRecipe.
401 friend class VPWidenMemoryRecipe;
402
403 SmallVector<VPValue *, 2> Operands;
404
405 /// Removes the operand at index \p Idx. This also removes the VPUser from the
406 /// use-list of the operand.
407 void removeOperand(unsigned Idx) {
408 getOperand(N: Idx)->removeUser(User&: *this);
409 Operands.erase(CI: Operands.begin() + Idx);
410 }
411
412protected:
413#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
414 /// Print the operands to \p O.
415 void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;
416#endif
417
418 VPUser(ArrayRef<VPValue *> Operands) {
419 for (VPValue *Operand : Operands)
420 addOperand(Operand);
421 }
422
423 void addOperand(VPValue *Operand) {
424 Operands.push_back(Elt: Operand);
425 Operand->addUser(User&: *this);
426 }
427
428public:
429 VPUser() = delete;
430 VPUser(const VPUser &) = delete;
431 VPUser &operator=(const VPUser &) = delete;
432 virtual ~VPUser() {
433 for (VPValue *Op : operands())
434 Op->removeUser(User&: *this);
435 }
436
437 unsigned getNumOperands() const { return Operands.size(); }
438 inline VPValue *getOperand(unsigned N) const {
439 assert(N < Operands.size() && "Operand index out of bounds");
440 return Operands[N];
441 }
442
443 /// Returns the last operand.
444 VPValue *getLastOperand() const { return Operands.back(); }
445
446 void setOperand(unsigned I, VPValue *New) {
447 assert((!Operands[I]->getScalarType() || !New->getScalarType() ||
448 Operands[I]->getScalarType() == New->getScalarType()) &&
449 "scalar type of new operand must match the old operand");
450 Operands[I]->removeUser(User&: *this);
451 Operands[I] = New;
452 New->addUser(User&: *this);
453 }
454
455 /// Swap operands of the VPUser. It must have exactly 2 operands.
456 void swapOperands() {
457 assert(Operands.size() == 2 && "must have 2 operands to swap");
458 std::swap(a&: Operands[0], b&: Operands[1]);
459 }
460
461 /// Replaces all uses of \p From in the VPUser with \p To.
462 void replaceUsesOfWith(VPValue *From, VPValue *To);
463
464 typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
465 typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
466 typedef iterator_range<operand_iterator> operand_range;
467 typedef iterator_range<const_operand_iterator> const_operand_range;
468
469 operand_iterator op_begin() { return Operands.begin(); }
470 const_operand_iterator op_begin() const { return Operands.begin(); }
471 operand_iterator op_end() { return Operands.end(); }
472 const_operand_iterator op_end() const { return Operands.end(); }
473 operand_range operands() { return operand_range(op_begin(), op_end()); }
474 const_operand_range operands() const {
475 return const_operand_range(op_begin(), op_end());
476 }
477 bool operands_empty() const { return Operands.empty(); } // NOLINT
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