MLIR  18.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  /// Return the current value being used by this operand.
150  IRValueT get() const { return value; }
151 
152  /// Set the current value being used by this operand.
153  void set(IRValueT newValue) {
154  // It isn't worth optimizing for the case of switching operands on a single
155  // value.
157  value = newValue;
158  insertIntoCurrent();
159  }
160 
161  /// Returns true if this operand contains the given value.
162  bool is(IRValueT other) const { return value == other; }
163 
164  /// \brief Remove this use of the operand.
165  void drop() {
167  value = nullptr;
168  }
169 
170 private:
171  /// The value used as this operand. This can be null when in a 'dropAllUses'
172  /// state.
173  IRValueT value = {};
174 
175  /// Insert this operand into the given use list.
176  void insertIntoCurrent() { insertInto(DerivedT::getUseList(value)); }
177 };
178 
179 //===----------------------------------------------------------------------===//
180 // IRObjectWithUseList
181 //===----------------------------------------------------------------------===//
182 
183 /// This class represents a single IR object that contains a use list.
184 template <typename OperandType>
186 public:
188  assert(use_empty() && "Cannot destroy a value that still has uses!");
189  }
190 
191  /// Drop all uses of this object from their respective owners.
192  void dropAllUses() {
193  while (!use_empty())
194  use_begin()->drop();
195  }
196 
197  /// Replace all uses of 'this' value with the new value, updating anything in
198  /// the IR that uses 'this' to use the other value instead. When this returns
199  /// there are zero uses of 'this'.
200  template <typename ValueT>
201  void replaceAllUsesWith(ValueT &&newValue) {
202  assert((!newValue || this != OperandType::getUseList(newValue)) &&
203  "cannot RAUW a value with itself");
204  while (!use_empty())
205  use_begin()->set(newValue);
206  }
207 
208  /// Shuffle the use-list chain according to the provided indices vector, which
209  /// need to represent a valid shuffle. That is, a vector of unique integers in
210  /// range [0, numUses - 1]. Users of this function need to guarantee the
211  /// validity of the indices vector.
213  assert((size_t)std::distance(getUses().begin(), getUses().end()) ==
214  indices.size() &&
215  "indices vector expected to have a number of elements equal to the "
216  "number of uses");
217  SmallVector<detail::IROperandBase *> shuffled(indices.size());
218  detail::IROperandBase *ptr = firstUse;
219  for (size_t idx = 0; idx < indices.size();
220  idx++, ptr = ptr->getNextOperandUsingThisValue())
221  shuffled[indices[idx]] = ptr;
222 
223  initFirstUse(shuffled.front());
224  auto *current = firstUse;
225  for (auto &next : llvm::drop_begin(shuffled)) {
226  current->linkTo(next);
227  current = next;
228  }
229  current->linkTo(nullptr);
230  }
231 
232  //===--------------------------------------------------------------------===//
233  // Uses
234  //===--------------------------------------------------------------------===//
235 
238 
239  use_iterator use_begin() const { return use_iterator(firstUse); }
240  use_iterator use_end() const { return use_iterator(nullptr); }
241 
242  /// Returns a range of all uses, which is useful for iterating over all uses.
243  use_range getUses() const { return {use_begin(), use_end()}; }
244 
245  /// Returns true if this value has exactly one use.
246  bool hasOneUse() const {
247  return firstUse && firstUse->getNextOperandUsingThisValue() == nullptr;
248  }
249 
250  /// Returns true if this value has no uses.
251  bool use_empty() const { return firstUse == nullptr; }
252 
253  //===--------------------------------------------------------------------===//
254  // Users
255  //===--------------------------------------------------------------------===//
256 
259 
262 
263  /// Returns a range of all users.
264  user_range getUsers() const { return {user_begin(), user_end()}; }
265 
266 protected:
267  IRObjectWithUseList() = default;
268 
269  /// Return the first operand that is using this value, for use by custom
270  /// use/def iterators.
271  OperandType *getFirstUse() const { return (OperandType *)firstUse; }
272 
273 private:
274  /// Set use as the first use of the chain.
275  void initFirstUse(detail::IROperandBase *use) {
276  firstUse = use;
277  firstUse->initChainWithUse(&firstUse);
278  }
279 
280  detail::IROperandBase *firstUse = nullptr;
281 
282  /// Allow access to `firstUse`.
283  friend detail::IROperandBase;
284 };
285 
286 //===----------------------------------------------------------------------===//
287 // ValueUseIterator
288 //===----------------------------------------------------------------------===//
289 
290 /// An iterator class that allows for iterating over the uses of an IR operand
291 /// type.
292 template <typename OperandType>
294  : public llvm::iterator_facade_base<ValueUseIterator<OperandType>,
295  std::forward_iterator_tag,
296  OperandType> {
297 public:
299 
300  /// Returns the operation that owns this use.
301  Operation *getUser() const { return current->getOwner(); }
302 
303  /// Returns the current operands.
304  OperandType *getOperand() const { return (OperandType *)current; }
305  OperandType &operator*() const { return *getOperand(); }
306 
307  using llvm::iterator_facade_base<ValueUseIterator<OperandType>,
308  std::forward_iterator_tag,
309  OperandType>::operator++;
311  assert(current && "incrementing past end()!");
312  current = (OperandType *)current->getNextOperandUsingThisValue();
313  return *this;
314  }
315 
316  bool operator==(const ValueUseIterator &rhs) const {
317  return current == rhs.current;
318  }
319 
320 protected:
322 };
323 
324 //===----------------------------------------------------------------------===//
325 // ValueUserIterator
326 //===----------------------------------------------------------------------===//
327 
328 /// An iterator over the users of an IRObject. This is a wrapper iterator around
329 /// a specific use iterator.
330 template <typename UseIteratorT, typename OperandType>
331 class ValueUserIterator final
332  : public llvm::mapped_iterator_base<
333  ValueUserIterator<UseIteratorT, OperandType>, UseIteratorT,
334  Operation *> {
335 public:
336  using llvm::mapped_iterator_base<ValueUserIterator<UseIteratorT, OperandType>,
337  UseIteratorT,
338  Operation *>::mapped_iterator_base;
339 
340  /// Map the element to the iterator result type.
341  Operation *mapElement(OperandType &value) const { return value.getOwner(); }
342 
343  /// Provide access to the underlying operation.
344  Operation *operator->() { return **this; }
345 };
346 
347 } // namespace mlir
348 
349 #endif
This class represents a single IR object that contains a use list.
Definition: UseDefLists.h:185
bool hasOneUse() const
Returns true if this value has exactly one use.
Definition: UseDefLists.h:246
use_range getUses() const
Returns a range of all uses, which is useful for iterating over all uses.
Definition: UseDefLists.h:243
user_range getUsers() const
Returns a range of all users.
Definition: UseDefLists.h:264
ValueUseIterator< OperandType > use_iterator
Definition: UseDefLists.h:236
OperandType * getFirstUse() const
Return the first operand that is using this value, for use by custom use/def iterators.
Definition: UseDefLists.h:271
void dropAllUses()
Drop all uses of this object from their respective owners.
Definition: UseDefLists.h:192
user_iterator user_end() const
Definition: UseDefLists.h:261
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:212
use_iterator use_begin() const
Definition: UseDefLists.h:239
ValueUserIterator< use_iterator, OperandType > user_iterator
Definition: UseDefLists.h:257
bool use_empty() const
Returns true if this value has no uses.
Definition: UseDefLists.h:251
user_iterator user_begin() const
Definition: UseDefLists.h:260
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:201
use_iterator use_end() const
Definition: UseDefLists.h:240
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:150
void set(IRValueT newValue)
Set the current value being used by this operand.
Definition: UseDefLists.h:153
IROperand & operator=(IROperand &&other)
Definition: UseDefLists.h:140
bool is(IRValueT other) const
Returns true if this operand contains the given value.
Definition: UseDefLists.h:162
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:165
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:296
ValueUseIterator(detail::IROperandBase *use=nullptr)
Definition: UseDefLists.h:298
bool operator==(const ValueUseIterator &rhs) const
Definition: UseDefLists.h:316
detail::IROperandBase * current
Definition: UseDefLists.h:321
Operation * getUser() const
Returns the operation that owns this use.
Definition: UseDefLists.h:301
ValueUseIterator & operator++()
Definition: UseDefLists.h:310
OperandType * getOperand() const
Returns the current operands.
Definition: UseDefLists.h:304
OperandType & operator*() const
Definition: UseDefLists.h:305
An iterator over the users of an IRObject.
Definition: UseDefLists.h:334
Operation * operator->()
Provide access to the underlying operation.
Definition: UseDefLists.h:344
Operation * mapElement(OperandType &value) const
Map the element to the iterator result type.
Definition: UseDefLists.h:341
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
This header declares functions that assist transformations in the MemRef dialect.