1 | //===- UseDefLists.h --------------------------------------------*- C++ -*-===// |
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 | // This file defines generic use/def list machinery and manipulation utilities. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef MLIR_IR_USEDEFLISTS_H |
14 | #define MLIR_IR_USEDEFLISTS_H |
15 | |
16 | #include "mlir/IR/Location.h" |
17 | #include "llvm/ADT/PointerIntPair.h" |
18 | #include "llvm/ADT/iterator_range.h" |
19 | |
20 | namespace mlir { |
21 | |
22 | class Operation; |
23 | template <typename OperandType> |
24 | class ValueUseIterator; |
25 | template <typename UseIteratorT, typename OperandType> |
26 | class ValueUserIterator; |
27 | |
28 | //===----------------------------------------------------------------------===// |
29 | // IROperand |
30 | //===----------------------------------------------------------------------===// |
31 | |
32 | namespace detail { |
33 | /// This class is the base for IROperand, and provides all of the non-templated |
34 | /// facilities for operand use management. |
35 | class IROperandBase { |
36 | public: |
37 | /// Return the owner of this operand. |
38 | Operation *getOwner() const { return owner; } |
39 | |
40 | /// Return the next operand on the use-list of the value we are referring to. |
41 | /// This should generally only be used by the internal implementation details |
42 | /// of the SSA machinery. |
43 | IROperandBase *getNextOperandUsingThisValue() { return nextUse; } |
44 | |
45 | /// Initialize the use-def chain by setting the back address to self and |
46 | /// nextUse to nullptr. |
47 | void initChainWithUse(IROperandBase **self) { |
48 | assert(this == *self); |
49 | back = self; |
50 | nextUse = nullptr; |
51 | } |
52 | |
53 | /// Link the current node to next. |
54 | void linkTo(IROperandBase *next) { |
55 | nextUse = next; |
56 | if (nextUse) |
57 | nextUse->back = &nextUse; |
58 | } |
59 | |
60 | protected: |
61 | IROperandBase(Operation *owner) : owner(owner) {} |
62 | IROperandBase(IROperandBase &&other) : owner(other.owner) { |
63 | *this = std::move(other); |
64 | } |
65 | IROperandBase &operator=(IROperandBase &&other) { |
66 | removeFromCurrent(); |
67 | other.removeFromCurrent(); |
68 | other.back = nullptr; |
69 | nextUse = nullptr; |
70 | back = nullptr; |
71 | return *this; |
72 | } |
73 | /// Operands are not copyable or assignable. |
74 | IROperandBase(const IROperandBase &use) = delete; |
75 | IROperandBase &operator=(const IROperandBase &use) = delete; |
76 | |
77 | ~IROperandBase() { removeFromCurrent(); } |
78 | |
79 | /// Remove this use of the operand. |
80 | void drop() { |
81 | removeFromCurrent(); |
82 | nextUse = nullptr; |
83 | back = nullptr; |
84 | } |
85 | |
86 | /// Remove this operand from the current use list. |
87 | void removeFromCurrent() { |
88 | if (!back) |
89 | return; |
90 | *back = nextUse; |
91 | if (nextUse) |
92 | nextUse->back = back; |
93 | } |
94 | |
95 | /// Insert this operand into the given use list. |
96 | template <typename UseListT> |
97 | void insertInto(UseListT *useList) { |
98 | back = &useList->firstUse; |
99 | nextUse = useList->firstUse; |
100 | if (nextUse) |
101 | nextUse->back = &nextUse; |
102 | useList->firstUse = this; |
103 | } |
104 | |
105 | /// The next operand in the use-chain. |
106 | IROperandBase *nextUse = nullptr; |
107 | |
108 | /// This points to the previous link in the use-chain. |
109 | IROperandBase **back = nullptr; |
110 | |
111 | private: |
112 | /// The operation owner of this operand. |
113 | Operation *const owner; |
114 | }; |
115 | } // namespace detail |
116 | |
117 | //===----------------------------------------------------------------------===// |
118 | // IROperand |
119 | //===----------------------------------------------------------------------===// |
120 | |
121 | /// A reference to a value, suitable for use as an operand of an operation. |
122 | /// IRValueT is the root type to use for values this tracks. Derived operand |
123 | /// types are expected to provide the following: |
124 | /// * static IRObjectWithUseList *getUseList(IRValueT value); |
125 | /// - Provide the use list that is attached to the given value. |
126 | template <typename DerivedT, typename IRValueT> |
127 | class IROperand : public detail::IROperandBase { |
128 | public: |
129 | IROperand(Operation *owner) : detail::IROperandBase(owner) {} |
130 | IROperand(Operation *owner, IRValueT value) |
131 | : detail::IROperandBase(owner), value(value) { |
132 | insertIntoCurrent(); |
133 | } |
134 | |
135 | /// We support a move constructor so IROperand's can be in vectors, but this |
136 | /// shouldn't be used by general clients. |
137 | IROperand(IROperand &&other) : detail::IROperandBase(std::move(other)) { |
138 | *this = std::move(other); |
139 | } |
140 | IROperand &operator=(IROperand &&other) { |
141 | detail::IROperandBase::operator=(std::move(other)); |
142 | value = other.value; |
143 | other.value = nullptr; |
144 | if (value) |
145 | insertIntoCurrent(); |
146 | return *this; |
147 | } |
148 | |
149 | /// Two operands are equal if they have the same owner and the same operand |
150 | /// number. They are stored inside of ops, so it is valid to compare their |
151 | /// pointers to determine equality. |
152 | bool operator==(const IROperand<DerivedT, IRValueT> &other) const { |
153 | return this == &other; |
154 | } |
155 | bool operator!=(const IROperand<DerivedT, IRValueT> &other) const { |
156 | return !(*this == other); |
157 | } |
158 | |
159 | /// Return the current value being used by this operand. |
160 | IRValueT get() const { return value; } |
161 | |
162 | /// Set the current value being used by this operand. |
163 | void set(IRValueT newValue) { |
164 | // It isn't worth optimizing for the case of switching operands on a single |
165 | // value. |
166 | removeFromCurrent(); |
167 | value = newValue; |
168 | insertIntoCurrent(); |
169 | } |
170 | |
171 | /// Returns true if this operand contains the given value. |
172 | bool is(IRValueT other) const { return value == other; } |
173 | |
174 | /// \brief Remove this use of the operand. |
175 | void drop() { |
176 | detail::IROperandBase::drop(); |
177 | value = nullptr; |
178 | } |
179 | |
180 | private: |
181 | /// The value used as this operand. This can be null when in a 'dropAllUses' |
182 | /// state. |
183 | IRValueT value = {}; |
184 | |
185 | /// Insert this operand into the given use list. |
186 | void insertIntoCurrent() { insertInto(DerivedT::getUseList(value)); } |
187 | }; |
188 | |
189 | //===----------------------------------------------------------------------===// |
190 | // IRObjectWithUseList |
191 | //===----------------------------------------------------------------------===// |
192 | |
193 | /// This class represents a single IR object that contains a use list. |
194 | template <typename OperandType> |
195 | class IRObjectWithUseList { |
196 | public: |
197 | ~IRObjectWithUseList() { |
198 | assert(use_empty() && "Cannot destroy a value that still has uses!" ); |
199 | } |
200 | |
201 | /// Drop all uses of this object from their respective owners. |
202 | void dropAllUses() { |
203 | while (!use_empty()) |
204 | use_begin()->drop(); |
205 | } |
206 | |
207 | /// Replace all uses of 'this' value with the new value, updating anything in |
208 | /// the IR that uses 'this' to use the other value instead. When this returns |
209 | /// there are zero uses of 'this'. |
210 | template <typename ValueT> |
211 | void replaceAllUsesWith(ValueT &&newValue) { |
212 | assert((!newValue || this != OperandType::getUseList(newValue)) && |
213 | "cannot RAUW a value with itself" ); |
214 | while (!use_empty()) |
215 | use_begin()->set(newValue); |
216 | } |
217 | |
218 | /// Shuffle the use-list chain according to the provided indices vector, which |
219 | /// need to represent a valid shuffle. That is, a vector of unique integers in |
220 | /// range [0, numUses - 1]. Users of this function need to guarantee the |
221 | /// validity of the indices vector. |
222 | void shuffleUseList(ArrayRef<unsigned> indices) { |
223 | assert((size_t)std::distance(getUses().begin(), getUses().end()) == |
224 | indices.size() && |
225 | "indices vector expected to have a number of elements equal to the " |
226 | "number of uses" ); |
227 | SmallVector<detail::IROperandBase *> shuffled(indices.size()); |
228 | detail::IROperandBase *ptr = firstUse; |
229 | for (size_t idx = 0; idx < indices.size(); |
230 | idx++, ptr = ptr->getNextOperandUsingThisValue()) |
231 | shuffled[indices[idx]] = ptr; |
232 | |
233 | initFirstUse(use: shuffled.front()); |
234 | auto *current = firstUse; |
235 | for (auto &next : llvm::drop_begin(RangeOrContainer&: shuffled)) { |
236 | current->linkTo(next); |
237 | current = next; |
238 | } |
239 | current->linkTo(next: nullptr); |
240 | } |
241 | |
242 | //===--------------------------------------------------------------------===// |
243 | // Uses |
244 | //===--------------------------------------------------------------------===// |
245 | |
246 | using use_iterator = ValueUseIterator<OperandType>; |
247 | using use_range = iterator_range<use_iterator>; |
248 | |
249 | use_iterator use_begin() const { return use_iterator(firstUse); } |
250 | use_iterator use_end() const { return use_iterator(nullptr); } |
251 | |
252 | /// Returns a range of all uses, which is useful for iterating over all uses. |
253 | use_range getUses() const { return {use_begin(), use_end()}; } |
254 | |
255 | /// Returns true if this value has exactly one use. |
256 | bool hasOneUse() const { |
257 | return firstUse && firstUse->getNextOperandUsingThisValue() == nullptr; |
258 | } |
259 | |
260 | /// Returns true if this value has no uses. |
261 | bool use_empty() const { return firstUse == nullptr; } |
262 | |
263 | //===--------------------------------------------------------------------===// |
264 | // Users |
265 | //===--------------------------------------------------------------------===// |
266 | |
267 | using user_iterator = ValueUserIterator<use_iterator, OperandType>; |
268 | using user_range = iterator_range<user_iterator>; |
269 | |
270 | user_iterator user_begin() const { return user_iterator(use_begin()); } |
271 | user_iterator user_end() const { return user_iterator(use_end()); } |
272 | |
273 | /// Returns a range of all users. |
274 | user_range getUsers() const { return {user_begin(), user_end()}; } |
275 | |
276 | protected: |
277 | IRObjectWithUseList() = default; |
278 | |
279 | /// Return the first operand that is using this value, for use by custom |
280 | /// use/def iterators. |
281 | OperandType *getFirstUse() const { return (OperandType *)firstUse; } |
282 | |
283 | private: |
284 | /// Set use as the first use of the chain. |
285 | void initFirstUse(detail::IROperandBase *use) { |
286 | firstUse = use; |
287 | firstUse->initChainWithUse(self: &firstUse); |
288 | } |
289 | |
290 | detail::IROperandBase *firstUse = nullptr; |
291 | |
292 | /// Allow access to `firstUse`. |
293 | friend detail::IROperandBase; |
294 | }; |
295 | |
296 | //===----------------------------------------------------------------------===// |
297 | // ValueUseIterator |
298 | //===----------------------------------------------------------------------===// |
299 | |
300 | /// An iterator class that allows for iterating over the uses of an IR operand |
301 | /// type. |
302 | template <typename OperandType> |
303 | class ValueUseIterator |
304 | : public llvm::iterator_facade_base<ValueUseIterator<OperandType>, |
305 | std::forward_iterator_tag, |
306 | OperandType> { |
307 | public: |
308 | ValueUseIterator(detail::IROperandBase *use = nullptr) : current(use) {} |
309 | |
310 | /// Returns the operation that owns this use. |
311 | Operation *getUser() const { return current->getOwner(); } |
312 | |
313 | /// Returns the current operands. |
314 | OperandType *getOperand() const { return (OperandType *)current; } |
315 | OperandType &operator*() const { return *getOperand(); } |
316 | |
317 | using llvm::iterator_facade_base<ValueUseIterator<OperandType>, |
318 | std::forward_iterator_tag, |
319 | OperandType>::operator++; |
320 | ValueUseIterator &operator++() { |
321 | assert(current && "incrementing past end()!" ); |
322 | current = (OperandType *)current->getNextOperandUsingThisValue(); |
323 | return *this; |
324 | } |
325 | |
326 | bool operator==(const ValueUseIterator &rhs) const { |
327 | return current == rhs.current; |
328 | } |
329 | |
330 | protected: |
331 | detail::IROperandBase *current; |
332 | }; |
333 | |
334 | //===----------------------------------------------------------------------===// |
335 | // ValueUserIterator |
336 | //===----------------------------------------------------------------------===// |
337 | |
338 | /// An iterator over the users of an IRObject. This is a wrapper iterator around |
339 | /// a specific use iterator. |
340 | template <typename UseIteratorT, typename OperandType> |
341 | class ValueUserIterator final |
342 | : public llvm::mapped_iterator_base< |
343 | ValueUserIterator<UseIteratorT, OperandType>, UseIteratorT, |
344 | Operation *> { |
345 | public: |
346 | using llvm::mapped_iterator_base<ValueUserIterator<UseIteratorT, OperandType>, |
347 | UseIteratorT, |
348 | Operation *>::mapped_iterator_base; |
349 | |
350 | /// Map the element to the iterator result type. |
351 | Operation *mapElement(OperandType &value) const { return value.getOwner(); } |
352 | |
353 | /// Provide access to the underlying operation. |
354 | Operation *operator->() { return **this; } |
355 | }; |
356 | |
357 | } // namespace mlir |
358 | |
359 | #endif |
360 | |