MLIR  14.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> class ValueUseIterator;
24 template <typename OperandType> class FilteredValueUseIterator;
25 template <typename UseIteratorT, typename OperandType> class ValueUserIterator;
26 
27 //===----------------------------------------------------------------------===//
28 // IROperand
29 //===----------------------------------------------------------------------===//
30 
31 namespace detail {
32 /// This class is the base for IROperand, and provides all of the non-templated
33 /// facilities for operand use management.
35 public:
36  /// Return the owner of this operand.
37  Operation *getOwner() const { return owner; }
38 
39  /// Return the next operand on the use-list of the value we are referring to.
40  /// This should generally only be used by the internal implementation details
41  /// of the SSA machinery.
43 
44 protected:
45  IROperandBase(Operation *owner) : owner(owner) {}
46  IROperandBase(IROperandBase &&other) : owner(other.owner) {
47  *this = std::move(other);
48  }
51  other.removeFromCurrent();
52  other.back = nullptr;
53  nextUse = nullptr;
54  back = nullptr;
55  return *this;
56  }
57  /// Operands are not copyable or assignable.
58  IROperandBase(const IROperandBase &use) = delete;
59  IROperandBase &operator=(const IROperandBase &use) = delete;
60 
62 
63  /// Remove this use of the operand.
64  void drop() {
66  nextUse = nullptr;
67  back = nullptr;
68  }
69 
70  /// Remove this operand from the current use list.
72  if (!back)
73  return;
74  *back = nextUse;
75  if (nextUse)
76  nextUse->back = back;
77  }
78 
79  /// Insert this operand into the given use list.
80  template <typename UseListT> void insertInto(UseListT *useList) {
81  back = &useList->firstUse;
82  nextUse = useList->firstUse;
83  if (nextUse)
84  nextUse->back = &nextUse;
85  useList->firstUse = this;
86  }
87 
88  /// The next operand in the use-chain.
89  IROperandBase *nextUse = nullptr;
90 
91  /// This points to the previous link in the use-chain.
92  IROperandBase **back = nullptr;
93 
94 private:
95  /// The operation owner of this operand.
96  Operation *const owner;
97 };
98 } // namespace detail
99 
100 //===----------------------------------------------------------------------===//
101 // IROperand
102 //===----------------------------------------------------------------------===//
103 
104 /// A reference to a value, suitable for use as an operand of an operation.
105 /// IRValueT is the root type to use for values this tracks. Derived operand
106 /// types are expected to provide the following:
107 /// * static IRObjectWithUseList *getUseList(IRValueT value);
108 /// - Provide the use list that is attached to the given value.
109 template <typename DerivedT, typename IRValueT>
111 public:
112  IROperand(Operation *owner) : detail::IROperandBase(owner) {}
113  IROperand(Operation *owner, IRValueT value)
114  : detail::IROperandBase(owner), value(value) {
115  insertIntoCurrent();
116  }
117 
118  /// We support a move constructor so IROperand's can be in vectors, but this
119  /// shouldn't be used by general clients.
120  IROperand(IROperand &&other) : detail::IROperandBase(std::move(other)) {
121  *this = std::move(other);
122  }
124  detail::IROperandBase::operator=(std::move(other));
125  value = other.value;
126  other.value = nullptr;
127  if (value)
128  insertIntoCurrent();
129  return *this;
130  }
131 
132  /// Return the current value being used by this operand.
133  IRValueT get() const { return value; }
134 
135  /// Set the current value being used by this operand.
136  void set(IRValueT newValue) {
137  // It isn't worth optimizing for the case of switching operands on a single
138  // value.
140  value = newValue;
141  insertIntoCurrent();
142  }
143 
144  /// Returns true if this operand contains the given value.
145  bool is(IRValueT other) const { return value == other; }
146 
147  /// \brief Remove this use of the operand.
148  void drop() {
150  value = nullptr;
151  }
152 
153 private:
154  /// The value used as this operand. This can be null when in a 'dropAllUses'
155  /// state.
156  IRValueT value = {};
157 
158  /// Insert this operand into the given use list.
159  void insertIntoCurrent() { insertInto(DerivedT::getUseList(value)); }
160 };
161 
162 //===----------------------------------------------------------------------===//
163 // IRObjectWithUseList
164 //===----------------------------------------------------------------------===//
165 
166 /// This class represents a single IR object that contains a use list.
167 template <typename OperandType> class IRObjectWithUseList {
168 public:
170  assert(use_empty() && "Cannot destroy a value that still has uses!");
171  }
172 
173  /// Drop all uses of this object from their respective owners.
174  void dropAllUses() {
175  while (!use_empty())
176  use_begin()->drop();
177  }
178 
179  /// Replace all uses of 'this' value with the new value, updating anything in
180  /// the IR that uses 'this' to use the other value instead. When this returns
181  /// there are zero uses of 'this'.
182  template <typename ValueT>
183  void replaceAllUsesWith(ValueT &&newValue) {
184  assert((!newValue || this != OperandType::getUseList(newValue)) &&
185  "cannot RAUW a value with itself");
186  while (!use_empty())
187  use_begin()->set(newValue);
188  }
189 
190  //===--------------------------------------------------------------------===//
191  // Uses
192  //===--------------------------------------------------------------------===//
193 
196 
197  use_iterator use_begin() const { return use_iterator(firstUse); }
198  use_iterator use_end() const { return use_iterator(nullptr); }
199 
200  /// Returns a range of all uses, which is useful for iterating over all uses.
201  use_range getUses() const { return {use_begin(), use_end()}; }
202 
203  /// Returns true if this value has exactly one use.
204  bool hasOneUse() const {
205  return firstUse && firstUse->getNextOperandUsingThisValue() == nullptr;
206  }
207 
208  /// Returns true if this value has no uses.
209  bool use_empty() const { return firstUse == nullptr; }
210 
211  //===--------------------------------------------------------------------===//
212  // Users
213  //===--------------------------------------------------------------------===//
214 
217 
218  user_iterator user_begin() const { return user_iterator(use_begin()); }
219  user_iterator user_end() const { return user_iterator(use_end()); }
220 
221  /// Returns a range of all users.
222  user_range getUsers() const { return {user_begin(), user_end()}; }
223 
224 protected:
225  IRObjectWithUseList() = default;
226 
227  /// Return the first operand that is using this value, for use by custom
228  /// use/def iterators.
229  OperandType *getFirstUse() const { return (OperandType *)firstUse; }
230 
231 private:
232  detail::IROperandBase *firstUse = nullptr;
233 
234  /// Allow access to `firstUse`.
235  friend detail::IROperandBase;
236 };
237 
238 //===----------------------------------------------------------------------===//
239 // ValueUseIterator
240 //===----------------------------------------------------------------------===//
241 
242 /// An iterator class that allows for iterating over the uses of an IR operand
243 /// type.
244 template <typename OperandType>
245 class ValueUseIterator
246  : public llvm::iterator_facade_base<ValueUseIterator<OperandType>,
247  std::forward_iterator_tag,
248  OperandType> {
249 public:
250  ValueUseIterator(detail::IROperandBase *use = nullptr) : current(use) {}
251 
252  /// Returns the operation that owns this use.
253  Operation *getUser() const { return current->getOwner(); }
254 
255  /// Returns the current operands.
256  OperandType *getOperand() const { return (OperandType *)current; }
257  OperandType &operator*() const { return *getOperand(); }
258 
259  using llvm::iterator_facade_base<ValueUseIterator<OperandType>,
260  std::forward_iterator_tag,
261  OperandType>::operator++;
263  assert(current && "incrementing past end()!");
264  current = (OperandType *)current->getNextOperandUsingThisValue();
265  return *this;
266  }
267 
268  bool operator==(const ValueUseIterator &rhs) const {
269  return current == rhs.current;
270  }
271 
272 protected:
274 };
275 
276 //===----------------------------------------------------------------------===//
277 // ValueUserIterator
278 //===----------------------------------------------------------------------===//
279 
280 /// An iterator over the users of an IRObject. This is a wrapper iterator around
281 /// a specific use iterator.
282 template <typename UseIteratorT, typename OperandType>
283 class ValueUserIterator final
284  : public llvm::mapped_iterator_base<
285  ValueUserIterator<UseIteratorT, OperandType>, UseIteratorT,
286  Operation *> {
287 public:
288  using llvm::mapped_iterator_base<ValueUserIterator<UseIteratorT, OperandType>,
289  UseIteratorT,
290  Operation *>::mapped_iterator_base;
291 
292  /// Map the element to the iterator result type.
293  Operation *mapElement(OperandType &value) const { return value.getOwner(); }
294 
295  /// Provide access to the underlying operation.
296  Operation *operator->() { return **this; }
297 };
298 
299 } // namespace mlir
300 
301 #endif
Include the generated interface declarations.
This class is the base for IROperand, and provides all of the non-templated facilities for operand us...
Definition: UseDefLists.h:34
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:28
void drop()
Remove this use of the operand.
Definition: UseDefLists.h:148
use_iterator use_end() const
Definition: UseDefLists.h:198
void drop()
Remove this use of the operand.
Definition: UseDefLists.h:64
IROperandBase * nextUse
The next operand in the use-chain.
Definition: UseDefLists.h:89
An iterator class that allows for iterating over the uses of an IR operand type.
Definition: UseDefLists.h:23
user_range getUsers() const
Returns a range of all users.
Definition: UseDefLists.h:222
IROperand & operator=(IROperand &&other)
Definition: UseDefLists.h:123
user_iterator user_begin() const
Definition: UseDefLists.h:218
An iterator over the users of an IRObject.
Definition: UseDefLists.h:25
void insertInto(UseListT *useList)
Insert this operand into the given use list.
Definition: UseDefLists.h:80
OperandType * getFirstUse() const
Return the first operand that is using this value, for use by custom use/def iterators.
Definition: UseDefLists.h:229
static constexpr const bool value
ValueUseIterator(detail::IROperandBase *use=nullptr)
Definition: UseDefLists.h:250
IROperand(IROperand &&other)
We support a move constructor so IROperand&#39;s can be in vectors, but this shouldn&#39;t be used by general...
Definition: UseDefLists.h:120
void dropAllUses()
Drop all uses of this object from their respective owners.
Definition: UseDefLists.h:174
user_iterator user_end() const
Definition: UseDefLists.h:219
This class represents a single IR object that contains a use list.
Definition: UseDefLists.h:167
use_range getUses() const
Returns a range of all uses, which is useful for iterating over all uses.
Definition: UseDefLists.h:201
void replaceAllUsesWith(ValueT &&newValue)
Replace all uses of &#39;this&#39; value with the new value, updating anything in the IR that uses &#39;this&#39; to ...
Definition: UseDefLists.h:183
IROperandBase & operator=(IROperandBase &&other)
Definition: UseDefLists.h:49
detail::IROperandBase * current
Definition: UseDefLists.h:273
Operation * getUser() const
Returns the operation that owns this use.
Definition: UseDefLists.h:253
bool is(IRValueT other) const
Returns true if this operand contains the given value.
Definition: UseDefLists.h:145
IROperandBase * getNextOperandUsingThisValue()
Return the next operand on the use-list of the value we are referring to.
Definition: UseDefLists.h:42
bool operator==(const ValueUseIterator &rhs) const
Definition: UseDefLists.h:268
Operation * operator->()
Provide access to the underlying operation.
Definition: UseDefLists.h:296
Operation * mapElement(OperandType &value) const
Map the element to the iterator result type.
Definition: UseDefLists.h:293
use_iterator use_begin() const
Definition: UseDefLists.h:197
IROperand(Operation *owner, IRValueT value)
Definition: UseDefLists.h:113
IROperand(Operation *owner)
Definition: UseDefLists.h:112
Operation * getOwner() const
Return the owner of this operand.
Definition: UseDefLists.h:37
OperandType & operator*() const
Definition: UseDefLists.h:257
IROperandBase(IROperandBase &&other)
Definition: UseDefLists.h:46
A reference to a value, suitable for use as an operand of an operation.
Definition: UseDefLists.h:110
IROperandBase ** back
This points to the previous link in the use-chain.
Definition: UseDefLists.h:92
ValueUseIterator & operator++()
Definition: UseDefLists.h:262
IROperandBase(Operation *owner)
Definition: UseDefLists.h:45
void removeFromCurrent()
Remove this operand from the current use list.
Definition: UseDefLists.h:71
bool hasOneUse() const
Returns true if this value has exactly one use.
Definition: UseDefLists.h:204
bool use_empty() const
Returns true if this value has no uses.
Definition: UseDefLists.h:209
OperandType * getOperand() const
Returns the current operands.
Definition: UseDefLists.h:256