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