xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Vectorize/VPlanValue.h (revision c66ec88fed842fbaad62c30d510644ceb7bd2d71)
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 
27 namespace llvm {
28 
29 // Forward declarations.
30 class raw_ostream;
31 class Value;
32 class VPSlotTracker;
33 class 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.
39 class 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 
50 protected:
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 
74 public:
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 
125 typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
126 typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;
127 
128 raw_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.
132 class VPUser : public VPValue {
133   SmallVector<VPValue *, 2> Operands;
134 
135 protected:
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 
142 public:
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 };
189 class VPlan;
190 class VPBasicBlock;
191 class 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.
196 class 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 
207 public:
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