[mlir] Refactor operation results to use a single use list for all results of the operation.

[rriddle]

Summary

A new class is added, IRMultiObjectWithUseList, that allows for representing an IR use list that holds multiple sub values(used in this case for OpResults). This class provides all of the same functionality as the base IRObjectWithUseList, but for specific sub-values. This saves a word per operation result and is a necessary step in optimizing the layout of operation results. For now the use list is placed on the operation itself, so zero-result operations grow by a word. When the work for optimizing layout is finished, this can be moved back to being a trailing object based on memory/runtime benchmarking.

[rriddle]

Update diff

[merge_guards_bot]

Unit tests: pass. 61132 tests passed, 0 failed and 728 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[merge_guards_bot]

Unit tests: pass. 61132 tests passed, 0 failed and 728 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[jpienaar]

Looks good as part of optimizing the size, thanks

[rriddle]

Formatted diff.

[merge_guards_bot]

Unit tests: pass. 61154 tests passed, 0 failed and 728 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

mlir/include/mlir/IR/Block.h

 #ifndef MLIR_IR_BLOCK_H
 #define MLIR_IR_BLOCK_H
 
 #include "mlir/IR/BlockSupport.h"
 #include "mlir/IR/Visitors.h"
 
 namespace mlir {
 /// `Block` represents an ordered list of `Operation`s.
-class Block : public IRObjectWithUseList,
+class Block : public IRObjectWithUseList<BlockOperand>,
               public llvm::ilist_node_with_parent<Block, Region> {
 public:
   explicit Block() {}
   ~Block();
 
   void clear() {
     // Drop all references from within this block.
     dropAllReferences();

mlir/include/mlir/IR/Operation.h

 #include "llvm/ADT/Twine.h"
 
 namespace mlir {
 /// Operation is a basic unit of execution within a function. Operations can
 /// be nested within other operations effectively forming a tree. Child
 /// operations are organized into operation blocks represented by a 'Block'
 /// class.
 class Operation final
-    : public llvm::ilist_node_with_parent<Operation, Block>,
+    : public IRMultiObjectWithUseList<OpOperand>,
+      public llvm::ilist_node_with_parent<Operation, Block>,
       private llvm::TrailingObjects<Operation, OpResult, BlockOperand, Region,
                                     detail::OperandStorage> {
 public:
   /// Create a new Operation with the specific fields.
   static Operation *create(Location location, OperationName name,
                            ArrayRef<Type> resultTypes, ArrayRef<Value> operands,
                            ArrayRef<NamedAttribute> attributes,
                            ArrayRef<Block *> successors, unsigned numRegions,
public:
   operand_type_iterator operand_type_begin() { return operand_begin(); }
   operand_type_iterator operand_type_end() { return operand_end(); }
   operand_type_range getOperandTypes() { return getOperands().getTypes(); }
 
   //===--------------------------------------------------------------------===//
   // Results
   //===--------------------------------------------------------------------===//
 
-  /// Return true if there are no users of any results of this operation.
-  bool use_empty();
-
   unsigned getNumResults() { return numResults; }
 
   Value getResult(unsigned idx) { return getOpResult(idx); }
 
   /// Support result iteration.
   using result_range = ResultRange;
   using result_iterator = result_range::iterator;
 
private:
   size_t numTrailingObjects(OverloadToken<Region>) const { return numRegions; }
 };
 
 inline raw_ostream &operator<<(raw_ostream &os, Operation &op) {
   op.print(os);
   return os;
 }
 
-/// This class implements use iterator for the Operation. This iterates over all
-/// uses of all results of an Operation.
-class UseIterator final
-    : public llvm::iterator_facade_base<UseIterator, std::forward_iterator_tag,
-                                        Operation *> {
-public:
-  /// Initialize UseIterator for op, specify end to return iterator to last use.
-  explicit UseIterator(Operation *op, bool end = false);
-
-  UseIterator &operator++();
-  Operation *operator->() { return use->getOwner(); }
-  Operation *operator*() { return use->getOwner(); }
-
-  bool operator==(const UseIterator &other) const;
-  bool operator!=(const UseIterator &other) const;
-
-private:
-  void skipOverResultsWithNoUsers();
-
-  /// The operation whose uses are being iterated over.
-  Operation *op;
-  /// The result of op who's uses are being iterated over.
-  Operation::result_iterator res;
-  /// The use of the result.
-  Value::use_iterator use;
-};
 } // end namespace mlir
 
 namespace llvm {
 /// Provide isa functionality for operation casts.
 template <typename T> struct isa_impl<T, ::mlir::Operation> {
   static inline bool doit(const ::mlir::Operation &op) {
     return T::classof(const_cast<::mlir::Operation *>(&op));
   }

mlir/include/mlir/IR/UseDefLists.h

 
 #include "mlir/IR/Location.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/iterator_range.h"
 
 namespace mlir {
 
 class Block;
-class IROperand;
 class Operation;
 class Value;
 template <typename OperandType> class ValueUseIterator;
-template <typename OperandType> class ValueUserIterator;
+template <typename OperandType> class FilteredValueUseIterator;
+template <typename UseIteratorT, typename OperandType> class ValueUserIterator;
 
 //===----------------------------------------------------------------------===//
 // IRObjectWithUseList
 //===----------------------------------------------------------------------===//
 
-class IRObjectWithUseList {
+/// This class represents a single IR object that contains a use list.
+template <typename OperandType> class IRObjectWithUseList {
 public:
   ~IRObjectWithUseList() {
     assert(use_empty() && "Cannot destroy a value that still has uses!");
   }
 
-  /// Returns true if this value has no uses.
-  bool use_empty() const { return firstUse == nullptr; }
+  /// Drop all uses of this object from their respective owners.
+  void dropAllUses() {
+    while (!use_empty())
+      use_begin()->drop();
+  }
 
-  /// Returns true if this value has exactly one use.
-  inline bool hasOneUse() const;
+  /// Replace all uses of 'this' value with the new value, updating anything in
+  /// the IR that uses 'this' to use the other value instead.  When this returns
+  /// there are zero uses of 'this'.
+  void replaceAllUsesWith(typename OperandType::ValueType newValue) {
+    assert(this != OperandType::getUseList(newValue) &&
+           "cannot RAUW a value with itself");
+    while (!use_empty())
+      use_begin()->set(newValue);
+  }
 
-  using use_iterator = ValueUseIterator<IROperand>;
+  //===--------------------------------------------------------------------===//
+  // Uses
+  //===--------------------------------------------------------------------===//
+
+  using use_iterator = ValueUseIterator<OperandType>;
   using use_range = iterator_range<use_iterator>;
 
-  inline use_iterator use_begin() const;
-  inline use_iterator use_end() const;
+  use_iterator use_begin() const { return use_iterator(firstUse); }
+  use_iterator use_end() const { return use_iterator(nullptr); }
 
   /// Returns a range of all uses, which is useful for iterating over all uses.
-  inline use_range getUses() const;
+  use_range getUses() const { return {use_begin(), use_end()}; }
 
-  using user_iterator = ValueUserIterator<IROperand>;
-  using user_range = iterator_range<user_iterator>;
+  /// Returns true if this value has exactly one use.
+  bool hasOneUse() const {
+    return firstUse && firstUse->getNextOperandUsingThisValue() == nullptr;
+  }
 
-  inline user_iterator user_begin() const;
-  inline user_iterator user_end() const;
+  /// Returns true if this value has no uses.
+  bool use_empty() const { return firstUse == nullptr; }
 
-  /// Returns a range of all users.
-  inline user_range getUsers() const;
+  //===--------------------------------------------------------------------===//
+  // Users
+  //===--------------------------------------------------------------------===//
 
-  /// Replace all uses of 'this' value with the new value, updating anything in
-  /// the IR that uses 'this' to use the other value instead.  When this returns
-  /// there are zero uses of 'this'.
-  void replaceAllUsesWith(IRObjectWithUseList *newValue);
+  using user_iterator = ValueUserIterator<use_iterator, OperandType>;
+  using user_range = iterator_range<user_iterator>;
 
-  /// Drop all uses of this object from their respective owners.
-  void dropAllUses();
+  user_iterator user_begin() const { return user_iterator(use_begin()); }
+  user_iterator user_end() const { return user_iterator(use_end()); }
+
+  /// Returns a range of all users.
+  user_range getUsers() const { return {user_begin(), user_end()}; }
 
 protected:
   IRObjectWithUseList() {}
 
-  /// Return the first IROperand that is using this value, for use by custom
+  /// Return the first operand that is using this value, for use by custom
   /// use/def iterators.
-  IROperand *getFirstUse() { return firstUse; }
-  const IROperand *getFirstUse() const { return firstUse; }
+  OperandType *getFirstUse() const { return firstUse; }
 
 private:
-  friend class IROperand;
-  IROperand *firstUse = nullptr;
+  template <typename DerivedT, typename IRValueTy> friend class IROperand;
+  OperandType *firstUse = nullptr;
+};
+
+//===----------------------------------------------------------------------===//
+// IRMultiObjectWithUseList
+//===----------------------------------------------------------------------===//
+
+/// This class represents multiple IR objects with a single use list. This class
+/// provides wrapper functionality for manipulating the uses of a single object.
+template <typename OperandType>
+class IRMultiObjectWithUseList : public IRObjectWithUseList<OperandType> {
+public:
+  using BaseType = IRObjectWithUseList<OperandType>;
+  using ValueType = typename OperandType::ValueType;
+
+  /// Drop all uses of `value` from their respective owners.
+  void dropAllUses(ValueType value) {
+    assert(this == OperandType::getUseList(value) &&
+           "value not attached to this use list");
+    for (OperandType &use : llvm::make_early_inc_range(getUses(value)))
+      use.drop();
+  }
+  using BaseType::dropAllUses;
+
+  /// Replace all uses of `oldValue` with the new value, updating anything in
+  /// the IR that uses 'this' to use the other value instead.  When this returns
+  /// there are zero uses of 'this'.
+  void replaceAllUsesWith(ValueType oldValue, ValueType newValue) {
+    assert(this == OperandType::getUseList(oldValue) &&
+           "value not attached to this use list");
+    assert(this != OperandType::getUseList(newValue) &&
+           "cannot RAUW a value with itself");
+    for (OperandType &use : llvm::make_early_inc_range(getUses(oldValue)))
+      use.set(newValue);
+  }
+
+  //===--------------------------------------------------------------------===//
+  // Uses
+  //===--------------------------------------------------------------------===//
+
+  using filtered_use_iterator = FilteredValueUseIterator<OperandType>;
+  using filtered_use_range = iterator_range<filtered_use_iterator>;
+
+  filtered_use_iterator use_begin(ValueType value) const {
+    return filtered_use_iterator(this->getFirstUse(), value);
+  }
+  filtered_use_iterator use_end(ValueType) const { return use_end(); }
+  filtered_use_range getUses(ValueType value) const {
+    return {use_begin(value), use_end(value)};
+  }
+  bool hasOneUse(ValueType value) const {
+    return mlir::has_single_element(getUses(value));
+  }
+  bool use_empty(ValueType value) const {
+    return use_begin(value) == use_end(value);
+  }
+  using BaseType::getUses;
+  using BaseType::hasOneUse;
+  using BaseType::use_begin;
+  using BaseType::use_empty;
+  using BaseType::use_end;
+
+  //===--------------------------------------------------------------------===//
+  // Users
+  //===--------------------------------------------------------------------===//
+
+  using filtered_user_iterator =
+      ValueUserIterator<filtered_use_iterator, OperandType>;
+  using filtered_user_range = iterator_range<filtered_user_iterator>;
+
+  filtered_user_iterator user_begin(ValueType value) const {
+    return {use_begin(value)};
+  }
+  filtered_user_iterator user_end(ValueType value) const { return {use_end()}; }
+  filtered_user_range getUsers(ValueType value) const {
+    return {user_begin(value), user_end(value)};
+  }
+  using BaseType::getUsers;
+  using BaseType::user_begin;
+  using BaseType::user_end;
 };
 
 //===----------------------------------------------------------------------===//
 // IROperand
 //===----------------------------------------------------------------------===//
 
 /// A reference to a value, suitable for use as an operand of an operation.
-class IROperand {
+/// IRValueTy is the root type to use for values this tracks. Derived operand
+/// types are expected to provide the following:
+///  * static IRObjectWithUseList *getUseList(IRValueTy value);
+///    - Provide the use list that is attached to the given value.
+template <typename DerivedT, typename IRValueTy> class IROperand {
 public:
+  using ValueType = IRValueTy;
+
   IROperand(Operation *owner) : owner(owner) {}
-  IROperand(Operation *owner, IRObjectWithUseList *value)
-      : value(value), owner(owner) {
+  IROperand(Operation *owner, ValueType value) : value(value), owner(owner) {
     insertIntoCurrent();
   }
 
   /// Return the current value being used by this operand.
-  IRObjectWithUseList *get() const { return value; }
+  ValueType get() const { return value; }
 
   /// Set the current value being used by this operand.
-  void set(IRObjectWithUseList *newValue) {
+  void set(ValueType newValue) {
     // It isn't worth optimizing for the case of switching operands on a single
     // value.
     removeFromCurrent();
     value = newValue;
     insertIntoCurrent();
   }
 
   /// Return the owner of this operand.
   Operation *getOwner() { return owner; }
   Operation *getOwner() const { return owner; }
 
   /// \brief Remove this use of the operand.
   void drop() {
     removeFromCurrent();
     value = nullptr;
     nextUse = nullptr;
     back = nullptr;
   }
 
   ~IROperand() { removeFromCurrent(); }
 
   /// Return the next operand on the use-list of the value we are referring to.
   /// This should generally only be used by the internal implementation details
   /// of the SSA machinery.
-  IROperand *getNextOperandUsingThisValue() { return nextUse; }
+  DerivedT *getNextOperandUsingThisValue() { return nextUse; }
 
   /// We support a move constructor so IROperand's can be in vectors, but this
   /// shouldn't be used by general clients.
   IROperand(IROperand &&other) : owner(other.owner) {
     *this = std::move(other);
   }
   IROperand &operator=(IROperand &&other) {
     removeFromCurrent();
     other.removeFromCurrent();
     value = other.value;
     other.value = nullptr;
     other.back = nullptr;
     nextUse = nullptr;
     back = nullptr;
     insertIntoCurrent();
     return *this;
   }
 
 private:
-  /// The value used as this operand.  This can be null when in a
-  /// "dropAllUses" state.
-  IRObjectWithUseList *value = nullptr;
+  /// The value used as this operand. This can be null when in a 'dropAllUses'
+  /// state.
+  ValueType value = {};
 
   /// The next operand in the use-chain.
-  IROperand *nextUse = nullptr;
+  DerivedT *nextUse = nullptr;
 
   /// This points to the previous link in the use-chain.
-  IROperand **back = nullptr;
+  DerivedT **back = nullptr;
 
   /// The operation owner of this operand.
   Operation *const owner;
 
   /// Operands are not copyable or assignable.
   IROperand(const IROperand &use) = delete;
   IROperand &operator=(const IROperand &use) = delete;
 
   void removeFromCurrent() {
     if (!back)
       return;
     *back = nextUse;
     if (nextUse)
       nextUse->back = back;
   }
 
   void insertIntoCurrent() {
-    back = &value->firstUse;
-    nextUse = value->firstUse;
+    auto *useList = DerivedT::getUseList(value);
+    back = &useList->firstUse;
+    nextUse = useList->firstUse;
     if (nextUse)
       nextUse->back = &nextUse;
-    value->firstUse = this;
+    useList->firstUse = static_cast<DerivedT *>(this);
   }
 };
 
 //===----------------------------------------------------------------------===//
 // BlockOperand
 //===----------------------------------------------------------------------===//
 
 /// Terminator operations can have Block operands to represent successors.
-class BlockOperand : public IROperand {
+class BlockOperand : public IROperand<BlockOperand, Block *> {
 public:
-  using IROperand::IROperand;
-
-  /// Return the current block being used by this operand.
-  Block *get();
+  using IROperand<BlockOperand, Block *>::IROperand;
 
-  /// Set the current value being used by this operand.
-  void set(Block *block);
+  /// Provide the use list that is attached to the given block.
+  static IRObjectWithUseList<BlockOperand> *getUseList(Block *value);
 
   /// Return which operand this is in the operand list of the User.
   unsigned getOperandNumber();
 
 private:
   /// The number of OpOperands that correspond with this block operand.
   unsigned numSuccessorOperands = 0;
 
   /// Allow access to 'numSuccessorOperands'.
   friend Operation;
 };
 
 //===----------------------------------------------------------------------===//
 // OpOperand
 //===----------------------------------------------------------------------===//
 
+namespace detail {
+/// This class provides an opaque type erased wrapper around a `Value`.
+class OpaqueValue {
+public:
+  /// Implicit conversion from 'Value'.
+  OpaqueValue(Value value);
+  OpaqueValue(std::nullptr_t = nullptr) : impl(nullptr) {}
+  OpaqueValue(const OpaqueValue &) = default;
+  OpaqueValue &operator=(const OpaqueValue &) = default;
+  operator bool() const { return impl; }
+
+  /// Implicit conversion back to 'Value'.
+  operator Value() const;
+
+private:
+  void *impl;
+};
+} // namespace detail
+
 /// A reference to a value, suitable for use as an operand of an operation.
-class OpOperand : public IROperand {
+class OpOperand : public IROperand<OpOperand, detail::OpaqueValue> {
 public:
-  OpOperand(Operation *owner) : IROperand(owner) {}
-  OpOperand(Operation *owner, Value value);
+  using IROperand<OpOperand, detail::OpaqueValue>::IROperand;
 
-  /// Return the current value being used by this operand.
-  Value get();
+  /// Provide the use list that is attached to the given value.
+  static IRObjectWithUseList<OpOperand> *getUseList(Value value);
 
-  /// Set the current value being used by this operand.
-  void set(Value newValue);
+  /// Return the current value being used by this operand.
+  Value get() const;
 
   /// Return which operand this is in the operand list of the User.
   unsigned getOperandNumber();
 };
 
 //===----------------------------------------------------------------------===//
 // ValueUseIterator
 //===----------------------------------------------------------------------===//
 
-/// An iterator over all uses of a ValueBase.
-template <typename OperandType>
-class ValueUseIterator
-    : public std::iterator<std::forward_iterator_tag, OperandType> {
+namespace detail {
+/// A base iterator class that allows for iterating over the uses of a value.
+/// This is templated to allow for derived iterators to override specific
+/// iterator methods.
+template <typename DerivedT, typename OperandType>
+class ValueUseIteratorImpl
+    : public llvm::iterator_facade_base<DerivedT, std::forward_iterator_tag,
+                                        OperandType> {
 public:
-  ValueUseIterator() = default;
-  explicit ValueUseIterator(OperandType *current) : current(current) {}
-  OperandType *operator->() const { return current; }
-  OperandType &operator*() const { return *current; }
+  template <typename T>
+  ValueUseIteratorImpl(const ValueUseIteratorImpl<T, OperandType> &other)
+      : current(other.getOperand()) {}
+  ValueUseIteratorImpl(OperandType *current = nullptr) : current(current) {}
 
   Operation *getUser() const { return current->getOwner(); }
+  OperandType *getOperand() const { return current; }
 
-  ValueUseIterator &operator++() {
+  OperandType &operator*() const { return *current; }
+
+  using llvm::iterator_facade_base<DerivedT, std::forward_iterator_tag,
+                                   OperandType>::operator++;
+  ValueUseIteratorImpl &operator++() {
     assert(current && "incrementing past end()!");
     current = (OperandType *)current->getNextOperandUsingThisValue();
     return *this;
   }
 
-  ValueUseIterator operator++(int unused) {
-    ValueUseIterator copy = *this;
-    ++*this;
-    return copy;
-  }
-
-  friend bool operator==(ValueUseIterator lhs, ValueUseIterator rhs) {
-    return lhs.current == rhs.current;
-  }
-
-  friend bool operator!=(ValueUseIterator lhs, ValueUseIterator rhs) {
-    return !(lhs == rhs);
+  bool operator==(const ValueUseIteratorImpl &rhs) const {
+    return current == rhs.current;
   }
 
-private:
+protected:
   OperandType *current;
 };
 
-inline auto IRObjectWithUseList::use_begin() const -> use_iterator {
-  return use_iterator(firstUse);
-}
+} // end namespace detail
 
-inline auto IRObjectWithUseList::use_end() const -> use_iterator {
-  return use_iterator(nullptr);
-}
+/// An iterator over all of the uses of an IR object.
+template <typename OperandType>
+class ValueUseIterator
+    : public detail::ValueUseIteratorImpl<ValueUseIterator<OperandType>,
+                                          OperandType> {
+public:
+  using detail::ValueUseIteratorImpl<ValueUseIterator<OperandType>,
+                                     OperandType>::ValueUseIteratorImpl;
+};
 
-inline auto IRObjectWithUseList::getUses() const -> use_range {
-  return {use_begin(), use_end()};
+/// This class represents an iterator of the uses of a IR object that optionally
+/// filters on a specific sub-value. This allows for filtering the uses of an
+/// IRMultiObjectWithUseList.
+template <typename OperandType>
+class FilteredValueUseIterator
+    : public detail::ValueUseIteratorImpl<FilteredValueUseIterator<OperandType>,
+                                          OperandType> {
+public:
+  using BaseT =
+      detail::ValueUseIteratorImpl<FilteredValueUseIterator<OperandType>,
+                                   OperandType>;
+
+  FilteredValueUseIterator() = default;
+  FilteredValueUseIterator(const ValueUseIterator<OperandType> &it)
+      : BaseT(it), filterVal(nullptr) {}
+  FilteredValueUseIterator(OperandType *current,
+                           typename OperandType::ValueType filterVal)
+      : BaseT(current), filterVal(filterVal) {
+    findNextValid();
+  }
+
+  using BaseT::operator++;
+  FilteredValueUseIterator<OperandType> &operator++() {
+    BaseT::operator++();
+    findNextValid();
+    return *this;
   }
 
-/// Returns true if this value has exactly one use.
-inline bool IRObjectWithUseList::hasOneUse() const {
-  return firstUse && firstUse->getNextOperandUsingThisValue() == nullptr;
+private:
+  void findNextValid() {
+    if (!filterVal)
+      return;
+    while (this->current && ((OperandType *)this->current)->get() != filterVal)
+      BaseT::operator++();
   }
 
+  /// An optional value to use to filter specific uses.
+  typename OperandType::ValueType filterVal;
+};
+
 //===----------------------------------------------------------------------===//
 // ValueUserIterator
 //===----------------------------------------------------------------------===//
 
 /// An iterator over all users of a ValueBase.
-template <typename OperandType>
+template <typename UseIteratorT, typename OperandType>
 class ValueUserIterator final
-    : public llvm::mapped_iterator<ValueUseIterator<OperandType>,
+    : public llvm::mapped_iterator<UseIteratorT,
                                    Operation *(*)(OperandType &)> {
   static Operation *unwrap(OperandType &value) { return value.getOwner(); }
 
 public:
   using pointer = Operation *;
   using reference = Operation *;
 
   /// Initializes the result type iterator to the specified result iterator.
-  ValueUserIterator(ValueUseIterator<OperandType> it)
-      : llvm::mapped_iterator<ValueUseIterator<OperandType>,
-                              Operation *(*)(OperandType &)>(it, &unwrap) {}
+  ValueUserIterator(UseIteratorT it)
+      : llvm::mapped_iterator<UseIteratorT, Operation *(*)(OperandType &)>(
+            it, &unwrap) {}
   Operation *operator->() { return **this; }
 };
 
-inline auto IRObjectWithUseList::user_begin() const -> user_iterator {
-  return user_iterator(use_begin());
-}
-
-inline auto IRObjectWithUseList::user_end() const -> user_iterator {
-  return user_iterator(use_end());
-}
-
-inline auto IRObjectWithUseList::getUsers() const -> user_range {
-  return {user_begin(), user_end()};
-}
-
 } // namespace mlir
 
 #endif

mlir/include/mlir/IR/Value.h

 class BlockArgument;
 class Operation;
 class OpResult;
 class Region;
 class Value;
 
 namespace detail {
 /// The internal implementation of a Value.
-class ValueImpl : public IRObjectWithUseList {
+class ValueImpl {
 protected:
   /// This enumerates all of the SSA value kinds.
   enum class Kind {
     BlockArgument,
     OpResult,
   };
 
   ValueImpl(Kind kind, Type type) : typeAndKind(type, kind) {}
 
 private:
   /// The type of the value and its kind.
   llvm::PointerIntPair<Type, 1, Kind> typeAndKind;
 
   /// Allow access to 'typeAndKind'.
   friend Value;
 };
 
 /// The internal implementation of a BlockArgument.
-class BlockArgumentImpl : public ValueImpl {
+class BlockArgumentImpl : public ValueImpl,
+                          public IRObjectWithUseList<OpOperand> {
   BlockArgumentImpl(Type type, Block *owner)
       : ValueImpl(Kind::BlockArgument, type), owner(owner) {}
 
   /// The owner of this argument.
   Block *owner;
 
   /// Allow access to owner and constructor.
   friend BlockArgument;
public:
   /// Mutate the type of this Value to be of the specified type.
   ///
   /// Note that this is an extremely dangerous operation which can create
   /// completely invalid IR very easily.  It is strongly recommended that you
   /// recreate IR objects with the right types instead of mutating them in
   /// place.
   void setType(Type newType) { impl->typeAndKind.setPointer(newType); }
 
-  /// Replace all uses of 'this' value with the new value, updating anything in
-  /// the IR that uses 'this' to use the other value instead.  When this returns
-  /// there are zero uses of 'this'.
-  void replaceAllUsesWith(Value newValue) const {
-    impl->replaceAllUsesWith(newValue.impl);
-  }
-
   /// If this value is the result of an operation, return the operation that
   /// defines it.
   Operation *getDefiningOp() const;
 
   /// If this value is the result of an operation, use it as a location,
   /// otherwise return an unknown location.
   Location getLoc();
 
   /// Return the Region in which this Value is defined.
   Region *getParentRegion();
 
-  using use_iterator = ValueUseIterator<OpOperand>;
+  //===--------------------------------------------------------------------===//
+  // UseLists
+  //===--------------------------------------------------------------------===//
+
+  /// Provide the use list that is attached to this value.
+  IRObjectWithUseList<OpOperand> *getUseList() const;
+
+  /// Drop all uses of this object from their respective owners.
+  void dropAllUses() const;
+
+  /// Replace all uses of 'this' value with the new value, updating anything in
+  /// the IR that uses 'this' to use the other value instead.  When this returns
+  /// there are zero uses of 'this'.
+  void replaceAllUsesWith(Value newValue) const;
+
+  //===--------------------------------------------------------------------===//
+  // Uses
+
+  /// This class implements an iterator over the uses of a value.
+  using use_iterator = FilteredValueUseIterator<OpOperand>;
   using use_range = iterator_range<use_iterator>;
 
-  inline use_iterator use_begin();
-  inline use_iterator use_end();
+  use_iterator use_begin() const;
+  use_iterator use_end() const { return use_iterator(); }
 
   /// Returns a range of all uses, which is useful for iterating over all uses.
-  inline use_range getUses();
+  use_range getUses() const { return {use_begin(), use_end()}; }
 
-  using user_iterator = ValueUserIterator<IROperand>;
-  using user_range = iterator_range<user_iterator>;
+  /// Returns true if this value has exactly one use.
+  bool hasOneUse() const;
 
-  user_iterator user_begin() const { return impl->user_begin(); }
-  user_iterator user_end() const { return impl->user_end(); }
+  /// Returns true if this value has no uses.
+  bool use_empty() const;
 
-  /// Returns a range of all users.
-  user_range getUsers() const { return impl->getUsers(); }
+  //===--------------------------------------------------------------------===//
+  // Users
 
-  /// Returns true if this value has no uses.
-  bool use_empty() const { return impl->use_empty(); }
+  using user_iterator = ValueUserIterator<use_iterator, OpOperand>;
+  using user_range = iterator_range<user_iterator>;
 
-  /// Returns true if this value has exactly one use.
-  bool hasOneUse() const { return impl->hasOneUse(); }
+  user_iterator user_begin() const { return use_begin(); }
+  user_iterator user_end() const { return use_end(); }
+  user_range getUsers() const { return {user_begin(), user_end()}; }
 
-  /// Drop all uses of this object from their respective owners.
-  void dropAllUses() const { impl->dropAllUses(); }
+  //===--------------------------------------------------------------------===//
+  // Utilities
 
   void print(raw_ostream &os);
   void dump();
 
   /// Methods for supporting PointerLikeTypeTraits.
   void *getAsOpaquePointer() const { return static_cast<void *>(impl); }
   static Value getFromOpaquePointer(const void *pointer) {
     return reinterpret_cast<detail::ValueImpl *>(const_cast<void *>(pointer));
protected:
   friend OpOperand;
 };
 
 inline raw_ostream &operator<<(raw_ostream &os, Value value) {
   value.print(os);
   return os;
 }
 
-// Utility functions for iterating through Value uses.
-inline auto Value::use_begin() -> use_iterator {
-  return use_iterator((OpOperand *)impl->getFirstUse());
-}
-
-inline auto Value::use_end() -> use_iterator { return use_iterator(nullptr); }
-
-inline auto Value::getUses() -> iterator_range<use_iterator> {
-  return {use_begin(), use_end()};
-}
-
 /// Block arguments are values.
 class BlockArgument : public Value {
 public:
   using Value::Value;
 
   /// Temporary methods to enable transition of Value to being used as a
   /// value-type.
   /// TODO(riverriddle) Remove this when all usages have been removed.
private:
 
   /// Get a raw pointer to the internal implementation.
   detail::BlockArgumentImpl *getImpl() const {
     return reinterpret_cast<detail::BlockArgumentImpl *>(impl);
   }
 
   /// Allow access to `create` and `destroy`.
   friend Block;
+
+  /// Allow access to 'getImpl'.
+  friend Value;
 };
 
 /// This is a value defined by a result of an operation.
 class OpResult : public Value {
 public:
   using Value::Value;
 
   /// Temporary methods to enable transition of Value to being used as a

mlir/lib/IR/Operation.cpp

void Operation::dropAllReferences() {
 
   for (auto &dest : getBlockOperands())
     dest.drop();
 }
 
 /// This drops all uses of any values defined by this operation or its nested
 /// regions, wherever they are located.
 void Operation::dropAllDefinedValueUses() {
-  for (auto &val : getOpResults())
-    val.dropAllUses();
+  dropAllUses();
 
   for (auto &region : getRegions())
     for (auto &block : region)
       block.dropAllDefinedValueUses();
 }
 
-/// Return true if there are no users of any results of this operation.
-bool Operation::use_empty() {
-  for (auto result : getResults())
-    if (!result->use_empty())
-      return false;
-  return true;
-}
-
 void Operation::setSuccessor(Block *block, unsigned index) {
   assert(index < getNumSuccessors());
   getBlockOperands()[index].set(block);
 }
 
 auto Operation::getNonSuccessorOperands() -> operand_range {
   return getOperands().take_front(hasSuccessors() ? getSuccessorOperandIndex(0)
                                                   : getNumOperands());
if (region.empty())
     region.push_back(new Block);
 
   Block &block = region.back();
   if (!block.empty() && block.back().isKnownTerminator())
     return;
 
   block.push_back(buildTerminatorOp());
 }
-
-//===----------------------------------------------------------------------===//
-// UseIterator
-//===----------------------------------------------------------------------===//
-
-UseIterator::UseIterator(Operation *op, bool end)
-    : op(op), res(end ? op->result_end() : op->result_begin()) {
-  // Only initialize current use if there are results/can be uses.
-  if (op->getNumResults())
-    skipOverResultsWithNoUsers();
-}
-
-UseIterator &UseIterator::operator++() {
-  // We increment over uses, if we reach the last use then move to next
-  // result.
-  if (use != (*res)->use_end())
-    ++use;
-  if (use == (*res)->use_end()) {
-    ++res;
-    skipOverResultsWithNoUsers();
-  }
-  return *this;
-}
-
-bool UseIterator::operator==(const UseIterator &other) const {
-  if (op != other.op)
-    return false;
-  if (op->getNumResults() == 0)
-    return true;
-  return res == other.res && use == other.use;
-}
-
-bool UseIterator::operator!=(const UseIterator &other) const {
-  return !(*this == other);
-}
-
-void UseIterator::skipOverResultsWithNoUsers() {
-  while (res != op->result_end() && (*res)->use_empty())
-    ++res;
-
-  // If we are at the last result, then set use to first use of
-  // first result (sentinel value used for end).
-  if (res == op->result_end())
-    use = {};
-  else
-    use = (*res)->use_begin();
-}

mlir/lib/IR/Value.cpp

 /// Return the Region in which this Value is defined.
 Region *Value::getParentRegion() {
   if (auto *op = getDefiningOp())
     return op->getParentRegion();
   return cast<BlockArgument>()->getOwner()->getParent();
 }
 
 //===----------------------------------------------------------------------===//
-// BlockOperand
+// Value::UseLists
 //===----------------------------------------------------------------------===//
 
-/// Return the current block being used by this operand.
-Block *BlockOperand::get() { return static_cast<Block *>(IROperand::get()); }
+/// Provide the use list that is attached to this value.
+IRObjectWithUseList<OpOperand> *Value::getUseList() const {
+  if (BlockArgument arg = dyn_cast<BlockArgument>())
+    return arg.getImpl();
+  return cast<OpResult>().getOwner();
+}
 
-/// Set the current value being used by this operand.
-void BlockOperand::set(Block *block) { IROperand::set(block); }
+/// Drop all uses of this object from their respective owners.
+void Value::dropAllUses() const {
+  if (BlockArgument arg = dyn_cast<BlockArgument>())
+    return arg.getImpl()->dropAllUses();
+  return cast<OpResult>().getOwner()->dropAllUses(*this);
+}
+
+/// Replace all uses of 'this' value with the new value, updating anything in
+/// the IR that uses 'this' to use the other value instead.  When this returns
+/// there are zero uses of 'this'.
+void Value::replaceAllUsesWith(Value newValue) const {
+  if (BlockArgument arg = dyn_cast<BlockArgument>())
+    return arg.getImpl()->replaceAllUsesWith(newValue);
+  IRMultiObjectWithUseList<OpOperand> *useList = cast<OpResult>().getOwner();
+  useList->replaceAllUsesWith(*this, newValue);
+}
+
+//===--------------------------------------------------------------------===//
+// Uses
+
+auto Value::use_begin() const -> use_iterator {
+  if (BlockArgument arg = dyn_cast<BlockArgument>())
+    return arg.getImpl()->use_begin();
+  return cast<OpResult>().getOwner()->use_begin(*this);
+}
+
+/// Returns true if this value has exactly one use.
+bool Value::hasOneUse() const {
+  if (BlockArgument arg = dyn_cast<BlockArgument>())
+    return arg.getImpl()->hasOneUse();
+  return cast<OpResult>().getOwner()->hasOneUse(*this);
+}
+
+/// Returns true if this value has no uses.
+bool Value::use_empty() const {
+  if (BlockArgument arg = dyn_cast<BlockArgument>())
+    return arg.getImpl()->use_empty();
+  return cast<OpResult>().getOwner()->use_empty(*this);
+}
+
+//===----------------------------------------------------------------------===//
+// BlockOperand
+//===----------------------------------------------------------------------===//
+
+/// Provide the use list that is attached to the given block.
+IRObjectWithUseList<BlockOperand> *BlockOperand::getUseList(Block *value) {
+  return value;
+}
 
 /// Return which operand this is in the operand list.
 unsigned BlockOperand::getOperandNumber() {
   return this - &getOwner()->getBlockOperands()[0];
 }
 
 //===----------------------------------------------------------------------===//
 // OpOperand
 //===----------------------------------------------------------------------===//
 
-OpOperand::OpOperand(Operation *owner, Value value)
-    : IROperand(owner, value.impl) {}
+/// Provide the use list that is attached to the given value.
+IRObjectWithUseList<OpOperand> *OpOperand::getUseList(Value value) {
+  return value.getUseList();
+}
 
 /// Return the current value being used by this operand.
-Value OpOperand::get() { return (detail::ValueImpl *)IROperand::get(); }
-
-/// Set the current value being used by this operand.
-void OpOperand::set(Value newValue) { IROperand::set(newValue.impl); }
+Value OpOperand::get() const {
+  return IROperand<OpOperand, detail::OpaqueValue>::get();
+}
 
 /// Return which operand this is in the operand list.
 unsigned OpOperand::getOperandNumber() {
   return this - &getOwner()->getOpOperands()[0];
 }
 
 //===----------------------------------------------------------------------===//
-// IRObjectWithUseList implementation.
+// detail::OpaqueValue
 //===----------------------------------------------------------------------===//
 
-/// Replace all uses of 'this' value with the new value, updating anything in
-/// the IR that uses 'this' to use the other value instead.  When this returns
-/// there are zero uses of 'this'.
-void IRObjectWithUseList::replaceAllUsesWith(IRObjectWithUseList *newValue) {
-  assert(this != newValue && "cannot RAUW a value with itself");
-  while (!use_empty()) {
-    use_begin()->set(newValue);
-  }
-}
+/// Implicit conversion from 'Value'.
+detail::OpaqueValue::OpaqueValue(Value value)
+    : impl(value.getAsOpaquePointer()) {}
 
-/// Drop all uses of this object from their respective owners.
-void IRObjectWithUseList::dropAllUses() {
-  while (!use_empty()) {
-    use_begin()->drop();
-  }
+/// Implicit conversion back to 'Value'.
+detail::OpaqueValue::operator Value() const {
+  return Value::getFromOpaquePointer(impl);
 }

mlir/lib/Transforms/ViewOpGraph.cpp

 namespace llvm {
 
 // Specialize GraphTraits to treat Block as a graph of Operations as nodes and
 // uses as edges.
 template <> struct GraphTraits<Block *> {
   using GraphType = Block *;
   using NodeRef = Operation *;
 
-  using ChildIteratorType = UseIterator;
-  static ChildIteratorType child_begin(NodeRef n) {
-    return ChildIteratorType(n);
-  }
-  static ChildIteratorType child_end(NodeRef n) {
-    return ChildIteratorType(n, /*end=*/true);
-  }
+  using ChildIteratorType = Operation::user_iterator;
+  static ChildIteratorType child_begin(NodeRef n) { return n->user_begin(); }
+  static ChildIteratorType child_end(NodeRef n) { return n->user_end(); }
 
   // Operation's destructor is private so use Operation* instead and use
   // mapped iterator.
   static Operation *AddressOf(Operation &op) { return &op; }
   using nodes_iterator = mapped_iterator<Block::iterator, decltype(&AddressOf)>;
   static nodes_iterator nodes_begin(Block *b) {
     return nodes_iterator(b->begin(), &AddressOf);
   }