MLIR  19.0.0git
UseDefLists.h
Go to the documentation of this file.
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.
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.
44 
45  /// Initialize the use-def chain by setting the back address to self and
46  /// nextUse to nullptr.
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  }
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 
78 
79  /// Remove this use of the operand.
80  void drop() {
82  nextUse = nullptr;
83  back = nullptr;
84  }
85 
86  /// Remove this operand from the current use list.
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>
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  }
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.
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() {
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>
196 public:
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.
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(shuffled.front());
234  auto *current = firstUse;
235  for (auto &next : llvm::drop_begin(shuffled)) {
236  current->linkTo(next);
237  current = next;
238  }
239  current->linkTo(nullptr);
240  }
241 
242  //===--------------------------------------------------------------------===//
243  // Uses
244  //===--------------------------------------------------------------------===//
245 
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 
269 
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(&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>
304  : public llvm::iterator_facade_base<ValueUseIterator<OperandType>,
305  std::forward_iterator_tag,
306  OperandType> {
307 public:
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++;
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:
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
This class represents a single IR object that contains a use list.
Definition: UseDefLists.h:195
bool hasOneUse() const
Returns true if this value has exactly one use.
Definition: UseDefLists.h:256
use_range getUses() const
Returns a range of all uses, which is useful for iterating over all uses.
Definition: UseDefLists.h:253
user_range getUsers() const
Returns a range of all users.
Definition: UseDefLists.h:274
ValueUseIterator< OperandType > use_iterator
Definition: UseDefLists.h:246
OperandType * getFirstUse() const
Return the first operand that is using this value, for use by custom use/def iterators.
Definition: UseDefLists.h:281
void dropAllUses()
Drop all uses of this object from their respective owners.
Definition: UseDefLists.h:202
user_iterator user_end() const
Definition: UseDefLists.h:271
void shuffleUseList(ArrayRef< unsigned > indices)
Shuffle the use-list chain according to the provided indices vector, which need to represent a valid ...
Definition: UseDefLists.h:222
use_iterator use_begin() const
Definition: UseDefLists.h:249
ValueUserIterator< use_iterator, OperandType > user_iterator
Definition: UseDefLists.h:267
bool use_empty() const
Returns true if this value has no uses.
Definition: UseDefLists.h:261
user_iterator user_begin() const
Definition: UseDefLists.h:270
void replaceAllUsesWith(ValueT &&newValue)
Replace all uses of 'this' value with the new value, updating anything in the IR that uses 'this' to ...
Definition: UseDefLists.h:211
use_iterator use_end() const
Definition: UseDefLists.h:250
A reference to a value, suitable for use as an operand of an operation.
Definition: UseDefLists.h:127
IRValueT get() const
Return the current value being used by this operand.
Definition: UseDefLists.h:160
void set(IRValueT newValue)
Set the current value being used by this operand.
Definition: UseDefLists.h:163
IROperand & operator=(IROperand &&other)
Definition: UseDefLists.h:140
bool operator==(const IROperand< DerivedT, IRValueT > &other) const
Two operands are equal if they have the same owner and the same operand number.
Definition: UseDefLists.h:152
bool is(IRValueT other) const
Returns true if this operand contains the given value.
Definition: UseDefLists.h:172
IROperand(IROperand &&other)
We support a move constructor so IROperand's can be in vectors, but this shouldn't be used by general...
Definition: UseDefLists.h:137
IROperand(Operation *owner)
Definition: UseDefLists.h:129
IROperand(Operation *owner, IRValueT value)
Definition: UseDefLists.h:130
void drop()
Remove this use of the operand.
Definition: UseDefLists.h:175
bool operator!=(const IROperand< DerivedT, IRValueT > &other) const
Definition: UseDefLists.h:155
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
An iterator class that allows for iterating over the uses of an IR operand type.
Definition: UseDefLists.h:306
ValueUseIterator(detail::IROperandBase *use=nullptr)
Definition: UseDefLists.h:308
bool operator==(const ValueUseIterator &rhs) const
Definition: UseDefLists.h:326
detail::IROperandBase * current
Definition: UseDefLists.h:331
Operation * getUser() const
Returns the operation that owns this use.
Definition: UseDefLists.h:311
ValueUseIterator & operator++()
Definition: UseDefLists.h:320
OperandType * getOperand() const
Returns the current operands.
Definition: UseDefLists.h:314
OperandType & operator*() const
Definition: UseDefLists.h:315
An iterator over the users of an IRObject.
Definition: UseDefLists.h:344
Operation * operator->()
Provide access to the underlying operation.
Definition: UseDefLists.h:354
Operation * mapElement(OperandType &value) const
Map the element to the iterator result type.
Definition: UseDefLists.h:351
This class is the base for IROperand, and provides all of the non-templated facilities for operand us...
Definition: UseDefLists.h:35
IROperandBase & operator=(const IROperandBase &use)=delete
IROperandBase * nextUse
The next operand in the use-chain.
Definition: UseDefLists.h:106
IROperandBase ** back
This points to the previous link in the use-chain.
Definition: UseDefLists.h:109
IROperandBase(const IROperandBase &use)=delete
Operands are not copyable or assignable.
void removeFromCurrent()
Remove this operand from the current use list.
Definition: UseDefLists.h:87
IROperandBase(Operation *owner)
Definition: UseDefLists.h:61
Operation * getOwner() const
Return the owner of this operand.
Definition: UseDefLists.h:38
void linkTo(IROperandBase *next)
Link the current node to next.
Definition: UseDefLists.h:54
void drop()
Remove this use of the operand.
Definition: UseDefLists.h:80
IROperandBase(IROperandBase &&other)
Definition: UseDefLists.h:62
void insertInto(UseListT *useList)
Insert this operand into the given use list.
Definition: UseDefLists.h:97
IROperandBase & operator=(IROperandBase &&other)
Definition: UseDefLists.h:65
void initChainWithUse(IROperandBase **self)
Initialize the use-def chain by setting the back address to self and nextUse to nullptr.
Definition: UseDefLists.h:47
IROperandBase * getNextOperandUsingThisValue()
Return the next operand on the use-list of the value we are referring to.
Definition: UseDefLists.h:43
Include the generated interface declarations.