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
20namespace mlir {
21
22class Operation;
23template <typename OperandType>
24class ValueUseIterator;
25template <typename UseIteratorT, typename OperandType>
26class ValueUserIterator;
27
28//===----------------------------------------------------------------------===//
29// IROperand
30//===----------------------------------------------------------------------===//
31
32namespace detail {
33/// This class is the base for IROperand, and provides all of the non-templated
34/// facilities for operand use management.
35class IROperandBase {
36public:
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
60protected:
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
111private:
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.
126template <typename DerivedT, typename IRValueT>
127class IROperand : public detail::IROperandBase {
128public:
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
180private:
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.
194template <typename OperandType>
195class IRObjectWithUseList {
196public:
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
276protected:
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
283private:
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.
302template <typename OperandType>
303class ValueUseIterator
304 : public llvm::iterator_facade_base<ValueUseIterator<OperandType>,
305 std::forward_iterator_tag,
306 OperandType> {
307public:
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
330protected:
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.
340template <typename UseIteratorT, typename OperandType>
341class ValueUserIterator final
342 : public llvm::mapped_iterator_base<
343 ValueUserIterator<UseIteratorT, OperandType>, UseIteratorT,
344 Operation *> {
345public:
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

source code of mlir/include/mlir/IR/UseDefLists.h