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
14///  |-- VPUser
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/SmallVector.h"
25#include "llvm/ADT/iterator_range.h"
26
27namespace llvm {
28
29// Forward declarations.
30class raw_ostream;
31class Value;
32class VPSlotTracker;
33class VPUser;
34
35// This is the base class of the VPlan Def/Use graph, used for modeling the data
36// flow into, within and out of the VPlan. VPValues can stand for live-ins
37// coming from the input IR, instructions which VPlan will generate if executed
38// and live-outs which the VPlan will need to fix accordingly.
39class VPValue {
40  friend class VPBuilder;
41  friend struct VPlanTransforms;
42  friend class VPBasicBlock;
43  friend class VPInterleavedAccessInfo;
44  friend class VPSlotTracker;
45
46  const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
47
48  SmallVector<VPUser *, 1> Users;
49
50protected:
51  // Hold the underlying Value, if any, attached to this VPValue.
52  Value *UnderlyingVal;
53
54  VPValue(const unsigned char SC, Value *UV = nullptr)
55      : SubclassID(SC), UnderlyingVal(UV) {}
56
57  // DESIGN PRINCIPLE: Access to the underlying IR must be strictly limited to
58  // the front-end and back-end of VPlan so that the middle-end is as
59  // independent as possible of the underlying IR. We grant access to the
60  // underlying IR using friendship. In that way, we should be able to use VPlan
61  // for multiple underlying IRs (Polly?) by providing a new VPlan front-end,
62  // back-end and analysis information for the new IR.
63
64  /// Return the underlying Value attached to this VPValue.
65  Value *getUnderlyingValue() { return UnderlyingVal; }
66  const Value *getUnderlyingValue() const { return UnderlyingVal; }
67
68  // Set \p Val as the underlying Value of this VPValue.
69  void setUnderlyingValue(Value *Val) {
70    assert(!UnderlyingVal && "Underlying Value is already set.");
71    UnderlyingVal = Val;
72  }
73
74public:
75  /// An enumeration for keeping track of the concrete subclass of VPValue that
76  /// are actually instantiated. Values of this enumeration are kept in the
77  /// SubclassID field of the VPValue objects. They are used for concrete
78  /// type identification.
79  enum { VPValueSC, VPUserSC, VPInstructionSC };
80
81  VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV) {}
82  VPValue(const VPValue &) = delete;
83  VPValue &operator=(const VPValue &) = delete;
84
85  /// \return an ID for the concrete type of this object.
86  /// This is used to implement the classof checks. This should not be used
87  /// for any other purpose, as the values may change as LLVM evolves.
88  unsigned getVPValueID() const { return SubclassID; }
89
90  void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const;
91  void print(raw_ostream &OS, VPSlotTracker &Tracker) const;
92
93  unsigned getNumUsers() const { return Users.size(); }
94  void addUser(VPUser &User) { Users.push_back(&User); }
95
96  typedef SmallVectorImpl<VPUser *>::iterator user_iterator;
97  typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator;
98  typedef iterator_range<user_iterator> user_range;
99  typedef iterator_range<const_user_iterator> const_user_range;
100
101  user_iterator user_begin() { return Users.begin(); }
102  const_user_iterator user_begin() const { return Users.begin(); }
103  user_iterator user_end() { return Users.end(); }
104  const_user_iterator user_end() const { return Users.end(); }
105  user_range users() { return user_range(user_begin(), user_end()); }
106  const_user_range users() const {
107    return const_user_range(user_begin(), user_end());
108  }
109
110  /// Returns true if the value has more than one unique user.
111  bool hasMoreThanOneUniqueUser() {
112    if (getNumUsers() == 0)
113      return false;
114
115    // Check if all users match the first user.
116    auto Current = std::next(user_begin());
117    while (Current != user_end() && *user_begin() == *Current)
118      Current++;
119    return Current != user_end();
120  }
121
122  void replaceAllUsesWith(VPValue *New);
123};
124
125typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
126typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;
127
128raw_ostream &operator<<(raw_ostream &OS, const VPValue &V);
129
130/// This class augments VPValue with operands which provide the inverse def-use
131/// edges from VPValue's users to their defs.
132class VPUser : public VPValue {
133  SmallVector<VPValue *, 2> Operands;
134
135protected:
136  VPUser(const unsigned char SC) : VPValue(SC) {}
137  VPUser(const unsigned char SC, ArrayRef<VPValue *> Operands) : VPValue(SC) {
138    for (VPValue *Operand : Operands)
139      addOperand(Operand);
140  }
141
142public:
143  VPUser() : VPValue(VPValue::VPUserSC) {}
144  VPUser(ArrayRef<VPValue *> Operands) : VPUser(VPValue::VPUserSC, Operands) {}
145  VPUser(std::initializer_list<VPValue *> Operands)
146      : VPUser(ArrayRef<VPValue *>(Operands)) {}
147  template <typename IterT>
148  VPUser(iterator_range<IterT> Operands) : VPValue(VPValue::VPUserSC) {
149    for (VPValue *Operand : Operands)
150      addOperand(Operand);
151  }
152
153  VPUser(const VPUser &) = delete;
154  VPUser &operator=(const VPUser &) = delete;
155
156  /// Method to support type inquiry through isa, cast, and dyn_cast.
157  static inline bool classof(const VPValue *V) {
158    return V->getVPValueID() >= VPUserSC &&
159           V->getVPValueID() <= VPInstructionSC;
160  }
161
162  void addOperand(VPValue *Operand) {
163    Operands.push_back(Operand);
164    Operand->addUser(*this);
165  }
166
167  unsigned getNumOperands() const { return Operands.size(); }
168  inline VPValue *getOperand(unsigned N) const {
169    assert(N < Operands.size() && "Operand index out of bounds");
170    return Operands[N];
171  }
172
173  void setOperand(unsigned I, VPValue *New) { Operands[I] = New; }
174
175  typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
176  typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
177  typedef iterator_range<operand_iterator> operand_range;
178  typedef iterator_range<const_operand_iterator> const_operand_range;
179
180  operand_iterator op_begin() { return Operands.begin(); }
181  const_operand_iterator op_begin() const { return Operands.begin(); }
182  operand_iterator op_end() { return Operands.end(); }
183  const_operand_iterator op_end() const { return Operands.end(); }
184  operand_range operands() { return operand_range(op_begin(), op_end()); }
185  const_operand_range operands() const {
186    return const_operand_range(op_begin(), op_end());
187  }
188};
189class VPlan;
190class VPBasicBlock;
191class VPRegionBlock;
192
193/// This class can be used to assign consecutive numbers to all VPValues in a
194/// VPlan and allows querying the numbering for printing, similar to the
195/// ModuleSlotTracker for IR values.
196class VPSlotTracker {
197  DenseMap<const VPValue *, unsigned> Slots;
198  unsigned NextSlot = 0;
199
200  void assignSlots(const VPBlockBase *VPBB);
201  void assignSlots(const VPRegionBlock *Region);
202  void assignSlots(const VPBasicBlock *VPBB);
203  void assignSlot(const VPValue *V);
204
205  void assignSlots(const VPlan &Plan);
206
207public:
208  VPSlotTracker(const VPlan *Plan) {
209    if (Plan)
210      assignSlots(*Plan);
211  }
212
213  unsigned getSlot(const VPValue *V) const {
214    auto I = Slots.find(V);
215    if (I == Slots.end())
216      return -1;
217    return I->second;
218  }
219};
220
221} // namespace llvm
222
223#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
224