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