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/DenseMap.h"
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/ADT/SmallVector.h"
26#include "llvm/ADT/StringMap.h"
27#include "llvm/ADT/TinyPtrVector.h"
28#include "llvm/ADT/iterator_range.h"
29
30namespace llvm {
31
32// Forward declarations.
33class raw_ostream;
34class Value;
35class VPDef;
36struct VPDoubleValueDef;
37class VPSlotTracker;
38class VPUser;
39class VPRecipeBase;
40class VPInterleaveRecipe;
41class VPPhiAccessors;
42
43// This is the base class of the VPlan Def/Use graph, used for modeling the data
44// flow into, within and out of the VPlan. VPValues can stand for live-ins
45// coming from the input IR and instructions which VPlan will generate if
46// executed.
47class VPValue {
48 friend class VPDef;
49 friend struct VPDoubleValueDef;
50 friend class VPInterleaveRecipe;
51 friend class VPlan;
52 friend class VPExpressionRecipe;
53
54 const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
55
56 SmallVector<VPUser *, 1> Users;
57
58protected:
59 // Hold the underlying Value, if any, attached to this VPValue.
60 Value *UnderlyingVal;
61
62 /// Pointer to the VPDef that defines this VPValue. If it is nullptr, the
63 /// VPValue is not defined by any recipe modeled in VPlan.
64 VPDef *Def;
65
66 VPValue(const unsigned char SC, Value *UV = nullptr, VPDef *Def = nullptr);
67
68 /// Create a live-in VPValue.
69 VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV, nullptr) {}
70 /// Create a VPValue for a \p Def which is a subclass of VPValue.
71 VPValue(VPDef *Def, Value *UV = nullptr) : VPValue(VPVRecipeSC, UV, Def) {}
72 /// Create a VPValue for a \p Def which defines multiple values.
73 VPValue(Value *UV, VPDef *Def) : VPValue(VPValueSC, UV, Def) {}
74
75 // DESIGN PRINCIPLE: Access to the underlying IR must be strictly limited to
76 // the front-end and back-end of VPlan so that the middle-end is as
77 // independent as possible of the underlying IR. We grant access to the
78 // underlying IR using friendship. In that way, we should be able to use VPlan
79 // for multiple underlying IRs (Polly?) by providing a new VPlan front-end,
80 // back-end and analysis information for the new IR.
81
82public:
83 /// Return the underlying Value attached to this VPValue.
84 Value *getUnderlyingValue() const { return UnderlyingVal; }
85
86 /// An enumeration for keeping track of the concrete subclass of VPValue that
87 /// are actually instantiated.
88 enum {
89 VPValueSC, /// A generic VPValue, like live-in values or defined by a recipe
90 /// that defines multiple values.
91 VPVRecipeSC /// A VPValue sub-class that is a VPRecipeBase.
92 };
93
94 VPValue(const VPValue &) = delete;
95 VPValue &operator=(const VPValue &) = delete;
96
97 virtual ~VPValue();
98
99 /// \return an ID for the concrete type of this object.
100 /// This is used to implement the classof checks. This should not be used
101 /// for any other purpose, as the values may change as LLVM evolves.
102 unsigned getVPValueID() const { return SubclassID; }
103
104#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
105 void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const;
106 void print(raw_ostream &OS, VPSlotTracker &Tracker) const;
107
108 /// Dump the value to stderr (for debugging).
109 void dump() const;
110#endif
111
112 unsigned getNumUsers() const { return Users.size(); }
113 void addUser(VPUser &User) { Users.push_back(Elt: &User); }
114
115 /// Remove a single \p User from the list of users.
116 void removeUser(VPUser &User) {
117 // The same user can be added multiple times, e.g. because the same VPValue
118 // is used twice by the same VPUser. Remove a single one.
119 auto *I = find(Range&: Users, Val: &User);
120 if (I != Users.end())
121 Users.erase(CI: I);
122 }
123
124 typedef SmallVectorImpl<VPUser *>::iterator user_iterator;
125 typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator;
126 typedef iterator_range<user_iterator> user_range;
127 typedef iterator_range<const_user_iterator> const_user_range;
128
129 user_iterator user_begin() { return Users.begin(); }
130 const_user_iterator user_begin() const { return Users.begin(); }
131 user_iterator user_end() { return Users.end(); }
132 const_user_iterator user_end() const { return Users.end(); }
133 user_range users() { return user_range(user_begin(), user_end()); }
134 const_user_range users() const {
135 return const_user_range(user_begin(), user_end());
136 }
137
138 /// Returns true if the value has more than one unique user.
139 bool hasMoreThanOneUniqueUser() const {
140 if (getNumUsers() == 0)
141 return false;
142
143 // Check if all users match the first user.
144 auto Current = std::next(x: user_begin());
145 while (Current != user_end() && *user_begin() == *Current)
146 Current++;
147 return Current != user_end();
148 }
149
150 void replaceAllUsesWith(VPValue *New);
151
152 /// Go through the uses list for this VPValue and make each use point to \p
153 /// New if the callback ShouldReplace returns true for the given use specified
154 /// by a pair of (VPUser, the use index).
155 void replaceUsesWithIf(
156 VPValue *New,
157 llvm::function_ref<bool(VPUser &U, unsigned Idx)> ShouldReplace);
158
159 /// Returns the recipe defining this VPValue or nullptr if it is not defined
160 /// by a recipe, i.e. is a live-in.
161 VPRecipeBase *getDefiningRecipe();
162 const VPRecipeBase *getDefiningRecipe() const;
163
164 /// Returns true if this VPValue is defined by a recipe.
165 bool hasDefiningRecipe() const { return getDefiningRecipe(); }
166
167 /// Returns true if this VPValue is a live-in, i.e. defined outside the VPlan.
168 bool isLiveIn() const { return !hasDefiningRecipe(); }
169
170 /// Returns the underlying IR value, if this VPValue is defined outside the
171 /// scope of VPlan. Returns nullptr if the VPValue is defined by a VPDef
172 /// inside a VPlan.
173 Value *getLiveInIRValue() const {
174 assert(isLiveIn() &&
175 "VPValue is not a live-in; it is defined by a VPDef inside a VPlan");
176 return getUnderlyingValue();
177 }
178
179 /// Returns true if the VPValue is defined outside any loop.
180 bool isDefinedOutsideLoopRegions() const;
181
182 // Set \p Val as the underlying Value of this VPValue.
183 void setUnderlyingValue(Value *Val) {
184 assert(!UnderlyingVal && "Underlying Value is already set.");
185 UnderlyingVal = Val;
186 }
187};
188
189typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
190typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;
191
192raw_ostream &operator<<(raw_ostream &OS, const VPRecipeBase &R);
193
194/// This class augments VPValue with operands which provide the inverse def-use
195/// edges from VPValue's users to their defs.
196class VPUser {
197 /// Grant access to removeOperand for VPPhiAccessors, the only supported user.
198 friend class VPPhiAccessors;
199
200 SmallVector<VPValue *, 2> Operands;
201
202 /// Removes the operand at index \p Idx. This also removes the VPUser from the
203 /// use-list of the operand.
204 void removeOperand(unsigned Idx) {
205 getOperand(N: Idx)->removeUser(User&: *this);
206 Operands.erase(CI: Operands.begin() + Idx);
207 }
208
209protected:
210#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
211 /// Print the operands to \p O.
212 void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;
213#endif
214
215 VPUser(ArrayRef<VPValue *> Operands) {
216 for (VPValue *Operand : Operands)
217 addOperand(Operand);
218 }
219
220public:
221 VPUser() = delete;
222 VPUser(const VPUser &) = delete;
223 VPUser &operator=(const VPUser &) = delete;
224 virtual ~VPUser() {
225 for (VPValue *Op : operands())
226 Op->removeUser(User&: *this);
227 }
228
229 void addOperand(VPValue *Operand) {
230 Operands.push_back(Elt: Operand);
231 Operand->addUser(User&: *this);
232 }
233
234 unsigned getNumOperands() const { return Operands.size(); }
235 inline VPValue *getOperand(unsigned N) const {
236 assert(N < Operands.size() && "Operand index out of bounds");
237 return Operands[N];
238 }
239
240 void setOperand(unsigned I, VPValue *New) {
241 Operands[I]->removeUser(User&: *this);
242 Operands[I] = New;
243 New->addUser(User&: *this);
244 }
245
246 /// Swap operands of the VPUser. It must have exactly 2 operands.
247 void swapOperands() {
248 assert(Operands.size() == 2 && "must have 2 operands to swap");
249 std::swap(a&: Operands[0], b&: Operands[1]);
250 }
251
252 /// Replaces all uses of \p From in the VPUser with \p To.
253 void replaceUsesOfWith(VPValue *From, VPValue *To);
254
255 typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
256 typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
257 typedef iterator_range<operand_iterator> operand_range;
258 typedef iterator_range<const_operand_iterator> const_operand_range;
259
260 operand_iterator op_begin() { return Operands.begin(); }
261 const_operand_iterator op_begin() const { return Operands.begin(); }
262 operand_iterator op_end() { return Operands.end(); }
263 const_operand_iterator op_end() const { return Operands.end(); }
264 operand_range operands() { return operand_range(op_begin(), op_end()); }
265 const_operand_range operands() const {
266 return const_operand_range(op_begin(), op_end());
267 }
268
269 /// Returns true if the VPUser uses scalars of operand \p Op. Conservatively
270 /// returns if only first (scalar) lane is used, as default.
271 virtual bool usesScalars(const VPValue *Op) const {
272 assert(is_contained(operands(), Op) &&
273 "Op must be an operand of the recipe");
274 return onlyFirstLaneUsed(Op);
275 }
276
277 /// Returns true if the VPUser only uses the first lane of operand \p Op.
278 /// Conservatively returns false.
279 virtual bool onlyFirstLaneUsed(const VPValue *Op) const {
280 assert(is_contained(operands(), Op) &&
281 "Op must be an operand of the recipe");
282 return false;
283 }
284
285 /// Returns true if the VPUser only uses the first part of operand \p Op.
286 /// Conservatively returns false.
287 virtual bool onlyFirstPartUsed(const VPValue *Op) const {
288 assert(is_contained(operands(), Op) &&
289 "Op must be an operand of the recipe");
290 return false;
291 }
292};
293
294/// This class augments a recipe with a set of VPValues defined by the recipe.
295/// It allows recipes to define zero, one or multiple VPValues. A VPDef owns
296/// the VPValues it defines and is responsible for deleting its defined values.
297/// Single-value VPDefs that also inherit from VPValue must make sure to inherit
298/// from VPDef before VPValue.
299class VPDef {
300 friend class VPValue;
301
302 /// Subclass identifier (for isa/dyn_cast).
303 const unsigned char SubclassID;
304
305 /// The VPValues defined by this VPDef.
306 TinyPtrVector<VPValue *> DefinedValues;
307
308 /// Add \p V as a defined value by this VPDef.
309 void addDefinedValue(VPValue *V) {
310 assert(V->Def == this &&
311 "can only add VPValue already linked with this VPDef");
312 DefinedValues.push_back(NewVal: V);
313 }
314
315 /// Remove \p V from the values defined by this VPDef. \p V must be a defined
316 /// value of this VPDef.
317 void removeDefinedValue(VPValue *V) {
318 assert(V->Def == this && "can only remove VPValue linked with this VPDef");
319 assert(is_contained(DefinedValues, V) &&
320 "VPValue to remove must be in DefinedValues");
321 llvm::erase(C&: DefinedValues, V);
322 V->Def = nullptr;
323 }
324
325public:
326 /// An enumeration for keeping track of the concrete subclass of VPRecipeBase
327 /// that is actually instantiated. Values of this enumeration are kept in the
328 /// SubclassID field of the VPRecipeBase objects. They are used for concrete
329 /// type identification.
330 using VPRecipeTy = enum {
331 VPBranchOnMaskSC,
332 VPDerivedIVSC,
333 VPExpandSCEVSC,
334 VPExpressionSC,
335 VPIRInstructionSC,
336 VPInstructionSC,
337 VPInterleaveSC,
338 VPReductionEVLSC,
339 VPReductionSC,
340 VPPartialReductionSC,
341 VPReplicateSC,
342 VPScalarIVStepsSC,
343 VPVectorPointerSC,
344 VPVectorEndPointerSC,
345 VPWidenCallSC,
346 VPWidenCanonicalIVSC,
347 VPWidenCastSC,
348 VPWidenGEPSC,
349 VPWidenIntrinsicSC,
350 VPWidenLoadEVLSC,
351 VPWidenLoadSC,
352 VPWidenStoreEVLSC,
353 VPWidenStoreSC,
354 VPWidenSC,
355 VPWidenSelectSC,
356 VPBlendSC,
357 VPHistogramSC,
358 // START: Phi-like recipes. Need to be kept together.
359 VPWidenPHISC,
360 VPPredInstPHISC,
361 // START: SubclassID for recipes that inherit VPHeaderPHIRecipe.
362 // VPHeaderPHIRecipe need to be kept together.
363 VPCanonicalIVPHISC,
364 VPActiveLaneMaskPHISC,
365 VPEVLBasedIVPHISC,
366 VPFirstOrderRecurrencePHISC,
367 VPWidenIntOrFpInductionSC,
368 VPWidenPointerInductionSC,
369 VPReductionPHISC,
370 // END: SubclassID for recipes that inherit VPHeaderPHIRecipe
371 // END: Phi-like recipes
372 VPFirstPHISC = VPWidenPHISC,
373 VPFirstHeaderPHISC = VPCanonicalIVPHISC,
374 VPLastHeaderPHISC = VPReductionPHISC,
375 VPLastPHISC = VPReductionPHISC,
376 };
377
378 VPDef(const unsigned char SC) : SubclassID(SC) {}
379
380 virtual ~VPDef() {
381 for (VPValue *D : make_early_inc_range(Range&: DefinedValues)) {
382 assert(D->Def == this &&
383 "all defined VPValues should point to the containing VPDef");
384 assert(D->getNumUsers() == 0 &&
385 "all defined VPValues should have no more users");
386 D->Def = nullptr;
387 delete D;
388 }
389 }
390
391 /// Returns the only VPValue defined by the VPDef. Can only be called for
392 /// VPDefs with a single defined value.
393 VPValue *getVPSingleValue() {
394 assert(DefinedValues.size() == 1 && "must have exactly one defined value");
395 assert(DefinedValues[0] && "defined value must be non-null");
396 return DefinedValues[0];
397 }
398 const VPValue *getVPSingleValue() const {
399 assert(DefinedValues.size() == 1 && "must have exactly one defined value");
400 assert(DefinedValues[0] && "defined value must be non-null");
401 return DefinedValues[0];
402 }
403
404 /// Returns the VPValue with index \p I defined by the VPDef.
405 VPValue *getVPValue(unsigned I) {
406 assert(DefinedValues[I] && "defined value must be non-null");
407 return DefinedValues[I];
408 }
409 const VPValue *getVPValue(unsigned I) const {
410 assert(DefinedValues[I] && "defined value must be non-null");
411 return DefinedValues[I];
412 }
413
414 /// Returns an ArrayRef of the values defined by the VPDef.
415 ArrayRef<VPValue *> definedValues() { return DefinedValues; }
416 /// Returns an ArrayRef of the values defined by the VPDef.
417 ArrayRef<VPValue *> definedValues() const { return DefinedValues; }
418
419 /// Returns the number of values defined by the VPDef.
420 unsigned getNumDefinedValues() const { return DefinedValues.size(); }
421
422 /// \return an ID for the concrete type of this object.
423 /// This is used to implement the classof checks. This should not be used
424 /// for any other purpose, as the values may change as LLVM evolves.
425 unsigned getVPDefID() const { return SubclassID; }
426
427#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
428 /// Dump the VPDef to stderr (for debugging).
429 void dump() const;
430
431 /// Each concrete VPDef prints itself.
432 virtual void print(raw_ostream &O, const Twine &Indent,
433 VPSlotTracker &SlotTracker) const = 0;
434#endif
435};
436
437} // namespace llvm
438
439#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
440