[mlir] Rewrite the internal representation of OpResult to be optimized for memory.

[rriddle]

Summary

This changes the implementation of OpResult to have some of the results be represented inline in Value, via a pointer int pair of Operation*+result number, and the rest being trailing objects on the main operation. The full details of the new representation is detailed in the proposal here:
https://groups.google.com/a/tensorflow.org/g/mlir/c/XXzzKhqqF_0/m/v6bKb08WCgAJ

The only difference between here and the above proposal is that we only steal 2-bits for the Value kind instead of 3. This means that we can only fit 2-results inline instead of 6. This allows for other users to steal the final bit for PointerUnion/etc. If necessary, we can always steal this bit back in the future to save more space if 3-6 results are common enough.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

[jpienaar]

Looks good in general, thanks

mlir/include/mlir/IR/OperationSupport.h

623

Could you perhaps reformulate this? A void* is used where the owner is an Operation* as ... And state that it will always be an Operation* in this case?

Could we assert this somewhere?

623

Also, I'm guessing forward declaration does not work as we need to know number of low bits to be able to use PointerUnion?

mlir/include/mlir/IR/Value.h

41–43

How about just saying that we steal 2 bits and so can support 4 values? Folks may disagree on what could be reasonably stolen :)

mlir/lib/IR/Operation.cpp

215

Why only for 1 ? I thought up to 2 could be stored in place.

[rriddle]

Resolve comments.

[rriddle]

mlir/include/mlir/IR/OperationSupport.h

623

Yep, we need to see the full definition to know the low bits.

mlir/lib/IR/Operation.cpp

215

hasSingleResult is unrelated to the number of results we can pack inline in a Value. This is tied to how we store result types for the operation itself. We use a single Type, resultType for all of the result types. It has 3 states:

1. 0 result: null
2. 1 result: the single result type
3. N results: a TupleType containing each of the result types.

We use hasSingleResult to differentiate between case 2 and 3 when it is a single result operation that returns a TupleType.

[merge_guards_bot]

Unit tests: pass. 61175 tests passed, 0 failed and 729 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]

Thanks

[rriddle]

Add newline after namespace.

[merge_guards_bot]

Unit tests: pass. 61175 tests passed, 0 failed and 729 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/Operation.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 IRMultiObjectWithUseList<OpOperand>,
       public llvm::ilist_node_with_parent<Operation, Block>,
-      private llvm::TrailingObjects<Operation, OpResult, BlockOperand, Region,
+      private llvm::TrailingObjects<Operation, detail::TrailingOpResult,
+                                    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,
                            bool resizableOperandList);
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
   //===--------------------------------------------------------------------===//
 
-  unsigned getNumResults() { return numResults; }
+  /// Return the number of results held by this operation.
+  unsigned getNumResults();
 
-  Value getResult(unsigned idx) { return getOpResult(idx); }
+  /// Get the 'idx'th result of this operation.
+  OpResult getResult(unsigned idx) { return OpResult(this, idx); }
 
   /// Support result iteration.
   using result_range = ResultRange;
   using result_iterator = result_range::iterator;
 
   result_iterator result_begin() { return getResults().begin(); }
   result_iterator result_end() { return getResults().end(); }
   result_range getResults() { return result_range(this); }
 
-  MutableArrayRef<OpResult> getOpResults() {
-    return {getTrailingObjects<OpResult>(), numResults};
-  }
-
-  OpResult &getOpResult(unsigned idx) { return getOpResults()[idx]; }
+  result_range getOpResults() { return getResults(); }
+  OpResult getOpResult(unsigned idx) { return getResult(idx); }
 
   /// Support result type iteration.
   using result_type_iterator = result_range::type_iterator;
   using result_type_range = iterator_range<result_type_iterator>;
   result_type_iterator result_type_begin() { return result_begin(); }
   result_type_iterator result_type_end() { return result_end(); }
   result_type_range getResultTypes() { return getResults().getTypes(); }
 
private:
   /// Update the order index of this operation of this operation if necessary,
   /// potentially recomputing the order of the parent block.
   void updateOrderIfNecessary();
 
   /// Returns true if this operation has a valid order.
   bool hasValidOrder() { return orderIndex != kInvalidOrderIdx; }
 
 private:
-  Operation(Location location, OperationName name, unsigned numResults,
+  Operation(Location location, OperationName name, ArrayRef<Type> resultTypes,
             unsigned numSuccessors, unsigned numRegions,
             const NamedAttributeList &attributes);
 
   // Operations are deleted through the destroy() member because they are
   // allocated with malloc.
   ~Operation();
 
   /// Returns the operand storage object.
   detail::OperandStorage &getOperandStorage() {
     return *getTrailingObjects<detail::OperandStorage>();
   }
 
+  /// Returns a raw pointer to the storage for the given trailing result. The
+  /// given result number should be 0-based relative to the trailing results,
+  /// and not all of the results of the operation. This method should generally
+  /// only be used by the 'Value' classes.
+  detail::TrailingOpResult *getTrailingResult(unsigned trailingResultNumber) {
+    return getTrailingObjects<detail::TrailingOpResult>() +
+           trailingResultNumber;
+  }
+
   /// Provide a 'getParent' method for ilist_node_with_parent methods.
   /// We mark it as a const function because ilist_node_with_parent specifically
   /// requires a 'getParent() const' method. Once ilist_node removes this
   /// constraint, we should drop the const to fit the rest of the MLIR const
   /// model.
   Block *getParent() const { return block; }
 
   /// The operation block that contains this operation.
   Block *block = nullptr;
 
   /// This holds information about the source location the operation was defined
   /// or derived from.
   Location location;
 
   /// Relative order of this operation in its parent block. Used for
   /// O(1) local dominance checks between operations.
   mutable unsigned orderIndex = 0;
 
-  const unsigned numResults, numSuccs, numRegions;
+  const unsigned numSuccs;
+  const unsigned numRegions : 31;
+
+  /// This holds the result types of the operation. There are three different
+  /// states recorded here:
+  /// - 0 results : The type below is null.
+  /// - 1 result  : The single result type is held here.
+  /// - N results : The type here is a tuple holding the result types.
+  /// Note: We steal a bit for 'hasSingleResult' from somewhere else so that we
+  /// can use 'resultType` in an ArrayRef<Type>.
+  bool hasSingleResult : 1;
+  Type resultType;
 
   /// This holds the name of the operation.
   OperationName name;
 
   /// This holds general named attributes for the operation.
   NamedAttributeList attrs;
 
   // allow ilist_traits access to 'block' field.
   friend struct llvm::ilist_traits<Operation>;
 
   // allow block to access the 'orderIndex' field.
   friend class Block;
 
+  // allow value to access the 'getTrailingResult' method.
+  friend class Value;
+
   // allow ilist_node_with_parent to access the 'getParent' method.
   friend class llvm::ilist_node_with_parent<Operation, Block>;
 
   // This stuff is used by the TrailingObjects template.
-  friend llvm::TrailingObjects<Operation, OpResult, BlockOperand, Region,
-                               detail::OperandStorage>;
-  size_t numTrailingObjects(OverloadToken<OpResult>) const {
-    return numResults;
+  friend llvm::TrailingObjects<Operation, detail::TrailingOpResult,
+                               BlockOperand, Region, detail::OperandStorage>;
+  size_t numTrailingObjects(OverloadToken<detail::TrailingOpResult>) const {
+    return OpResult::getNumTrailing(
+        const_cast<Operation *>(this)->getNumResults());
   }
   size_t numTrailingObjects(OverloadToken<BlockOperand>) const {
     return numSuccs;
   }
   size_t numTrailingObjects(OverloadToken<Region>) const { return numRegions; }
 };
 
 inline raw_ostream &operator<<(raw_ostream &os, Operation &op) {

mlir/include/mlir/IR/OperationSupport.h

private:
   friend llvm::TrailingObjects<OperandStorage, ResizableStorage, OpOperand>;
   size_t numTrailingObjects(OverloadToken<ResizableStorage>) const {
     return resizable ? 1 : 0;
   }
 };
 } // end namespace detail
 
 //===----------------------------------------------------------------------===//
+// TrailingOpResult
+//===----------------------------------------------------------------------===//
+
+namespace detail {
+/// This class provides the implementation for a trailing operation result.
+struct TrailingOpResult {
+  /// The only element is the trailing result number, or the offset from the
+  /// beginning of the trailing array.
+  uint64_t trailingResultNumber;
+};
+} // end namespace detail
+
+//===----------------------------------------------------------------------===//
 // OpPrintingFlags
 //===----------------------------------------------------------------------===//
 
 /// Set of flags used to control the behavior of the various IR print methods
 /// (e.g. Operation::Print).
 class OpPrintingFlags {
 public:
   OpPrintingFlags();
private:
   friend RangeBaseT;
 };
 
 //===----------------------------------------------------------------------===//
 // ResultRange
 
 /// This class implements the result iterators for the Operation class.
 class ResultRange final
-    : public detail::indexed_accessor_range_base<ResultRange, OpResult *, Value,
-                                                 Value, Value> {
+    : public indexed_accessor_range<ResultRange, Operation *, OpResult,
+                                    OpResult, OpResult> {
 public:
-  using RangeBaseT::RangeBaseT;
+  using indexed_accessor_range<ResultRange, Operation *, OpResult, OpResult,
+                               OpResult>::indexed_accessor_range;
   ResultRange(Operation *op);
 
   /// Returns the types of the values within this range.
   using type_iterator = ValueTypeIterator<iterator>;
   iterator_range<type_iterator> getTypes() const { return {begin(), end()}; }
 
 private:
   /// See `detail::indexed_accessor_range_base` for details.
-  static OpResult *offset_base(OpResult *object, ptrdiff_t index) {
-    return object + index;
-  }
-  /// See `detail::indexed_accessor_range_base` for details.
-  static Value dereference_iterator(OpResult *object, ptrdiff_t index) {
-    return object[index];
-  }
+  static OpResult dereference_iterator(Operation *op, ptrdiff_t index);
 
-  /// Allow access to `offset_base` and `dereference_iterator`.
-  friend RangeBaseT;
+  /// Allow access to `dereference_iterator`.
+  friend indexed_accessor_range<ResultRange, Operation *, OpResult, OpResult,
+                                OpResult>;
 };
 
 //===----------------------------------------------------------------------===//
 // ValueRange
 
+namespace detail {
+/// The type representing the owner of a ValueRange. This is either a list of
+/// values, operands, or an Operation+start index for results.
+struct ValueRangeOwner {
+  ValueRangeOwner(const Value *owner) : ptr(owner), startIndex(0) {}
+  ValueRangeOwner(OpOperand *owner) : ptr(owner), startIndex(0) {}
+  ValueRangeOwner(Operation *owner, unsigned startIndex)
+      : ptr(owner), startIndex(startIndex) {}
+  bool operator==(const ValueRangeOwner &rhs) const { return ptr == rhs.ptr; }
+
+  /// The owner pointer of the range. The owner has represents three distinct
+  /// states:
+  /// const Value *: The owner is the base to a contiguous array of Value.
+  /// OpOperand *  : The owner is the base to a contiguous array of operands.
+  /// void*        : This owner is an Operation*. It is marked as void* here
+  ///                because the definition of Operation is not visible here.
+  PointerUnion<const Value *, OpOperand *, void *> ptr;
+
+  /// Ths start index into the range. This is only used for Operation* owners.
+  unsigned startIndex;
+};
+} // end namespace detail
+
 /// This class provides an abstraction over the different types of ranges over
 /// Values. In many cases, this prevents the need to explicitly materialize a
 /// SmallVector/std::vector. This class should be used in places that are not
 /// suitable for a more derived type (e.g. ArrayRef) or a template range
 /// parameter.
 class ValueRange final
     : public detail::indexed_accessor_range_base<
-          ValueRange, PointerUnion<const Value *, OpOperand *, OpResult *>,
-          Value, Value, Value> {
+          ValueRange, detail::ValueRangeOwner, Value, Value, Value> {
 public:
   using RangeBaseT::RangeBaseT;
 
   template <typename Arg,
             typename = typename std::enable_if_t<
                 std::is_constructible<ArrayRef<Value>, Arg>::value &&
                 !std::is_convertible<Arg, Value>::value>>
   ValueRange(Arg &&arg) : ValueRange(ArrayRef<Value>(std::forward<Arg>(arg))) {}
   ValueRange(const Value &value) : ValueRange(&value, /*count=*/1) {}
   ValueRange(const std::initializer_list<Value> &values)
       : ValueRange(ArrayRef<Value>(values)) {}
   ValueRange(iterator_range<OperandRange::iterator> values)
       : ValueRange(OperandRange(values)) {}
   ValueRange(iterator_range<ResultRange::iterator> values)
       : ValueRange(ResultRange(values)) {}
   ValueRange(ArrayRef<Value> values = llvm::None);
   ValueRange(OperandRange values);
   ValueRange(ResultRange values);
 
   /// Returns the types of the values within this range.
   using type_iterator = ValueTypeIterator<iterator>;
   iterator_range<type_iterator> getTypes() const { return {begin(), end()}; }
 
 private:
-  /// The type representing the owner of this range. This is either a list of
-  /// values, operands, or results.
-  using OwnerT = PointerUnion<const Value *, OpOperand *, OpResult *>;
+  using OwnerT = detail::ValueRangeOwner;
 
   /// See `detail::indexed_accessor_range_base` for details.
   static OwnerT offset_base(const OwnerT &owner, ptrdiff_t index);
   /// See `detail::indexed_accessor_range_base` for details.
   static Value dereference_iterator(const OwnerT &owner, ptrdiff_t index);
 
   /// Allow access to `offset_base` and `dereference_iterator`.
   friend RangeBaseT;

mlir/include/mlir/IR/Value.h

 #ifndef MLIR_IR_VALUE_H
 #define MLIR_IR_VALUE_H
 
 #include "mlir/IR/Types.h"
 #include "mlir/IR/UseDefLists.h"
 #include "mlir/Support/LLVM.h"
 
 namespace mlir {
-class Block;
 class BlockArgument;
 class Operation;
 class OpResult;
 class Region;
 class Value;
 
 namespace detail {
-/// The internal implementation of a Value.
-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,
-                          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;
-};
-
-class OpResultImpl : public ValueImpl {
-  OpResultImpl(Type type, Operation *owner)
-      : ValueImpl(Kind::OpResult, type), owner(owner) {}
-
-  /// The owner of this result.
-  Operation *owner;
-
-  /// Allow access to owner and the constructor.
-  friend OpResult;
-};
+class BlockArgumentImpl;
 } // end namespace detail
 
 /// This class represents an instance of an SSA value in the MLIR system,
 /// representing a computable value that has a type and a set of users. An SSA
 /// value is either a BlockArgument or the result of an operation. Note: This
 /// class has value-type semantics and is just a simple wrapper around a
 /// ValueImpl that is either owner by a block(in the case of a BlockArgument) or
 /// an Operation(in the case of an OpResult).
-///
 class Value {
 public:
-  /// This enumerates all of the SSA value kinds in the MLIR system.
+  /// The enumeration represents the various different kinds of values the
+  /// internal representation may take. We steal 2 bits to support a total of 4
+  /// possible values.
   enum class Kind {
-    BlockArgument,
-    OpResult,
+    /// The first N kinds are all inline operation results. An inline operation
+    /// result means that the kind represents the result number, and the owner
+    /// pointer is the owning `Operation*`. Note: These are packed first to make
+    /// result number lookups more efficient.
+    OpResult0 = 0,
+    OpResult1 = 1,
+
+    /// The next kind represents a 'trailing' operation result. This is for
+    /// results with numbers larger than we can represent inline. The owner here
+    /// is an `TrailingOpResult*` that points to a trailing storage on the
+    /// parent operation.
+    TrailingOpResult = 2,
+
+    /// The last kind represents a block argument. The owner here is a
+    /// `BlockArgumentImpl*`.
+    BlockArgument = 3
+  };
+
+  /// This value represents the 'owner' of the value and its kind. See the
+  /// 'Kind' enumeration above for a more detailed description of each kind of
+  /// owner.
+  struct ImplTypeTraits : public llvm::PointerLikeTypeTraits<void *> {
+    // We know that all pointers within the ImplType are aligned by 8-bytes,
+    // meaning that we can steal up to 3 bits for the different values.
+    enum { NumLowBitsAvailable = 3 };
   };
+  using ImplType = llvm::PointerIntPair<void *, 2, Kind, ImplTypeTraits>;
 
-  Value(std::nullptr_t) : impl(nullptr) {}
-  Value(detail::ValueImpl *impl = nullptr) : impl(impl) {}
+public:
+  Value(std::nullptr_t) : ownerAndKind() {}
+  Value(ImplType ownerAndKind = {}) : ownerAndKind(ownerAndKind) {}
   Value(const Value &) = default;
   Value &operator=(const Value &) = default;
-  ~Value() {}
 
   template <typename U> bool isa() const {
-    assert(impl && "isa<> used on a null type.");
+    assert(*this && "isa<> used on a null type.");
     return U::classof(*this);
   }
   template <typename U> U dyn_cast() const {
-    return isa<U>() ? U(impl) : U(nullptr);
+    return isa<U>() ? U(ownerAndKind) : U(nullptr);
   }
   template <typename U> U dyn_cast_or_null() const {
-    return (impl && isa<U>()) ? U(impl) : U(nullptr);
+    return (*this && isa<U>()) ? U(ownerAndKind) : U(nullptr);
   }
   template <typename U> U cast() const {
     assert(isa<U>());
-    return U(impl);
+    return U(ownerAndKind);
   }
 
   /// Temporary methods to enable transition of Value to being used as a
   /// value-type.
   /// TODO(riverriddle) Remove these when all usages have been removed.
   Value operator*() const { return *this; }
   Value *operator->() const { return const_cast<Value *>(this); }
 
-  operator bool() const { return impl; }
-  bool operator==(const Value &other) const { return impl == other.impl; }
+  operator bool() const { return ownerAndKind.getPointer(); }
+  bool operator==(const Value &other) const {
+    return ownerAndKind == other.ownerAndKind;
+  }
   bool operator!=(const Value &other) const { return !(*this == other); }
 
-  /// Return the kind of this value.
-  Kind getKind() const { return (Kind)impl->typeAndKind.getInt(); }
-
   /// Return the type of this value.
-  Type getType() const { return impl->typeAndKind.getPointer(); }
+  Type getType() const;
 
   /// Utility to get the associated MLIRContext that this value is defined in.
   MLIRContext *getContext() const { return getType().getContext(); }
 
   /// 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); }
+  void setType(Type newType);
 
   /// 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();
public:
 
   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()}; }
 
   //===--------------------------------------------------------------------===//
   // Utilities
 
+  /// Returns the kind of this value.
+  Kind getKind() const { return ownerAndKind.getInt(); }
+
   void print(raw_ostream &os);
   void dump();
 
   /// Methods for supporting PointerLikeTypeTraits.
-  void *getAsOpaquePointer() const { return static_cast<void *>(impl); }
+  void *getAsOpaquePointer() const { return ownerAndKind.getOpaqueValue(); }
   static Value getFromOpaquePointer(const void *pointer) {
-    return reinterpret_cast<detail::ValueImpl *>(const_cast<void *>(pointer));
+    Value value;
+    value.ownerAndKind.setFromOpaqueValue(const_cast<void *>(pointer));
+    return value;
   }
 
   friend ::llvm::hash_code hash_value(Value arg);
 
 protected:
-  /// The internal implementation of this value.
-  mutable detail::ValueImpl *impl;
+  /// Returns true if the given operation result can be packed inline.
+  static bool canPackResultInline(unsigned resultNo) {
+    return resultNo < static_cast<unsigned>(Kind::TrailingOpResult);
+  }
 
-  /// Allow access to 'impl'.
-  friend OpOperand;
+  /// Construct a value.
+  Value(detail::BlockArgumentImpl *impl);
+  Value(Operation *op, unsigned resultNo);
+
+  /// This value represents the 'owner' of the value and its kind. See the
+  /// 'Kind' enumeration above for a more detailed description of each kind of
+  /// owner.
+  ImplType ownerAndKind;
 };
 
 inline raw_ostream &operator<<(raw_ostream &os, Value value) {
   value.print(os);
   return os;
 }
 
+//===----------------------------------------------------------------------===//
+// BlockArgument
+//===----------------------------------------------------------------------===//
+
+namespace detail {
+/// The internal implementation of a BlockArgument.
+class BlockArgumentImpl : public IRObjectWithUseList<OpOperand> {
+  BlockArgumentImpl(Type type, Block *owner) : type(type), owner(owner) {}
+
+  /// The type of this argument.
+  Type type;
+
+  /// The owner of this argument.
+  Block *owner;
+
+  /// Allow access to owner and constructor.
+  friend BlockArgument;
+};
+} // end namespace detail
+
 /// 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.
   BlockArgument *operator->() { return this; }
 
   static bool classof(Value value) {
     return value.getKind() == Kind::BlockArgument;
   }
 
   /// Returns the block that owns this argument.
   Block *getOwner() const { return getImpl()->owner; }
 
+  /// Return the type of this value.
+  Type getType() const { return getImpl()->type; }
+
+  /// Set the type of this value.
+  void setType(Type newType) { getImpl()->type = newType; }
+
   /// Returns the number of this argument.
   unsigned getArgNumber() const;
 
 private:
   /// Allocate a new argument with the given type and owner.
   static BlockArgument create(Type type, Block *owner) {
     return new detail::BlockArgumentImpl(type, owner);
   }
 
   /// Destroy and deallocate this argument.
   void destroy() { delete getImpl(); }
 
   /// Get a raw pointer to the internal implementation.
   detail::BlockArgumentImpl *getImpl() const {
-    return reinterpret_cast<detail::BlockArgumentImpl *>(impl);
+    return reinterpret_cast<detail::BlockArgumentImpl *>(
+        ownerAndKind.getPointer());
   }
 
   /// Allow access to `create` and `destroy`.
   friend Block;
 
   /// Allow access to 'getImpl'.
   friend Value;
 };
 
+//===----------------------------------------------------------------------===//
+// OpResult
+//===----------------------------------------------------------------------===//
+
 /// 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
   /// value-type.
   /// TODO(riverriddle) Remove these when all usages have been removed.
-  OpResult *operator*() { return this; }
+  OpResult operator*() { return *this; }
   OpResult *operator->() { return this; }
 
-  static bool classof(Value value) { return value.getKind() == Kind::OpResult; }
+  static bool classof(Value value) {
+    return value.getKind() != Kind::BlockArgument;
+  }
 
   /// Returns the operation that owns this result.
-  Operation *getOwner() const { return getImpl()->owner; }
+  Operation *getOwner() const;
 
   /// Returns the number of this result.
   unsigned getResultNumber() const;
 
 private:
-  /// Allocate a new result with the given type and owner.
-  static OpResult create(Type type, Operation *owner) {
-    return new detail::OpResultImpl(type, owner);
-  }
-
-  /// Destroy and deallocate this result.
-  void destroy() { delete getImpl(); }
-
-  /// Get a raw pointer to the internal implementation.
-  detail::OpResultImpl *getImpl() const {
-    return reinterpret_cast<detail::OpResultImpl *>(impl);
-  }
+  /// Given a number of operation results, returns the number that need to be
+  /// stored as trailing.
+  static unsigned getNumTrailing(unsigned numResults);
 
   /// Allow access to `create` and `destroy`.
   friend Operation;
 };
 
 /// Make Value hashable.
 inline ::llvm::hash_code hash_value(Value arg) {
-  return ::llvm::hash_value(arg.impl);
+  return ::llvm::hash_value(arg.ownerAndKind.getOpaqueValue());
 }
 
 } // namespace mlir
 
 namespace llvm {
 
 template <> struct DenseMapInfo<mlir::Value> {
   static mlir::Value getEmptyKey() {
     auto pointer = llvm::DenseMapInfo<void *>::getEmptyKey();
-    return mlir::Value(static_cast<mlir::detail::ValueImpl *>(pointer));
+    return mlir::Value::getFromOpaquePointer(pointer);
   }
   static mlir::Value getTombstoneKey() {
     auto pointer = llvm::DenseMapInfo<void *>::getTombstoneKey();
-    return mlir::Value(static_cast<mlir::detail::ValueImpl *>(pointer));
+    return mlir::Value::getFromOpaquePointer(pointer);
   }
   static unsigned getHashValue(mlir::Value val) {
     return mlir::hash_value(val);
   }
-  static bool isEqual(mlir::Value LHS, mlir::Value RHS) { return LHS == RHS; }
+  static bool isEqual(mlir::Value lhs, mlir::Value rhs) { return lhs == rhs; }
 };
 
 /// Allow stealing the low bits of a value.
 template <> struct PointerLikeTypeTraits<mlir::Value> {
 public:
   static inline void *getAsVoidPointer(mlir::Value I) {
     return const_cast<void *>(I.getAsOpaquePointer());
   }
   static inline mlir::Value getFromVoidPointer(void *P) {
     return mlir::Value::getFromOpaquePointer(P);
   }
   enum {
     NumLowBitsAvailable =
-        PointerLikeTypeTraits<mlir::detail::ValueImpl *>::NumLowBitsAvailable
+        PointerLikeTypeTraits<mlir::Value::ImplType>::NumLowBitsAvailable
   };
 };
 
 template <> struct DenseMapInfo<mlir::BlockArgument> {
   static mlir::BlockArgument getEmptyKey() {
     auto pointer = llvm::DenseMapInfo<void *>::getEmptyKey();
-    return mlir::BlockArgument(static_cast<mlir::detail::ValueImpl *>(pointer));
+    return mlir::BlockArgument(
+        mlir::Value::ImplType::getFromOpaqueValue(pointer));
   }
   static mlir::BlockArgument getTombstoneKey() {
     auto pointer = llvm::DenseMapInfo<void *>::getTombstoneKey();
-    return mlir::BlockArgument(static_cast<mlir::detail::ValueImpl *>(pointer));
+    return mlir::BlockArgument(
+        mlir::Value::ImplType::getFromOpaqueValue(pointer));
   }
   static unsigned getHashValue(mlir::BlockArgument val) {
     return mlir::hash_value(val);
   }
   static bool isEqual(mlir::BlockArgument LHS, mlir::BlockArgument RHS) {
     return LHS == RHS;
   }
 };
 
 /// Allow stealing the low bits of a value.
 template <> struct PointerLikeTypeTraits<mlir::BlockArgument> {
 public:
   static inline void *getAsVoidPointer(mlir::Value I) {
     return const_cast<void *>(I.getAsOpaquePointer());
   }
   static inline mlir::BlockArgument getFromVoidPointer(void *P) {
     return mlir::Value::getFromOpaquePointer(P).cast<mlir::BlockArgument>();
   }
   enum {
     NumLowBitsAvailable =
-        PointerLikeTypeTraits<mlir::detail::ValueImpl *>::NumLowBitsAvailable
+        PointerLikeTypeTraits<mlir::Value>::NumLowBitsAvailable
   };
 };
 } // end namespace llvm
 
 #endif

mlir/include/mlir/Support/STLExtras.h

 ///   * ReferenceT dereference_iterator(const BaseT &base, ptrdiff_t index)
 ///     - Derefence an iterator pointing to a parent base at the given index.
 template <typename DerivedT, typename BaseT, typename T,
           typename PointerT = T *, typename ReferenceT = T &>
 class indexed_accessor_range
     : public detail::indexed_accessor_range_base<
           indexed_accessor_range<DerivedT, BaseT, T, PointerT, ReferenceT>,
           std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT> {
+public:
+  using detail::indexed_accessor_range_base<
+      indexed_accessor_range<DerivedT, BaseT, T, PointerT, ReferenceT>,
+      std::pair<BaseT, ptrdiff_t>, T, PointerT,
+      ReferenceT>::indexed_accessor_range_base;
+
+  /// Returns the current base of the range.
+  const BaseT &getBase() const { return this->base.first; }
+
+  /// Returns the current start index of the range.
+  ptrdiff_t getStartIndex() const { return this->base.second; }
+
 protected:
   indexed_accessor_range(BaseT base, ptrdiff_t startIndex, ptrdiff_t count)
       : detail::indexed_accessor_range_base<
-            DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT>(
+            indexed_accessor_range<DerivedT, BaseT, T, PointerT, ReferenceT>,
+            std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT>(
             std::make_pair(base, startIndex), count) {}
 
 private:
   /// See `detail::indexed_accessor_range_base` for details.
   static std::pair<BaseT, ptrdiff_t>
   offset_base(const std::pair<BaseT, ptrdiff_t> &base, ptrdiff_t index) {
     // We encode the internal base as a pair of the derived base and a start
     // index into the derived base.

mlir/lib/IR/Operation.cpp

const AbstractOperation *OperationName::getAbstractOperation() const {
   return representation.dyn_cast<const AbstractOperation *>();
 }
 
 OperationName OperationName::getFromOpaquePointer(void *pointer) {
   return OperationName(RepresentationUnion::getFromOpaqueValue(pointer));
 }
 
 //===----------------------------------------------------------------------===//
-// OpResult
-//===----------------------------------------------------------------------===//
-
-/// Return the result number of this result.
-unsigned OpResult::getResultNumber() const {
-  // Results are not stored in place, so we have to find it within the list.
-  auto resList = getOwner()->getOpResults();
-  return std::distance(resList.begin(), llvm::find(resList, *this));
-}
-
-//===----------------------------------------------------------------------===//
 // Operation
 //===----------------------------------------------------------------------===//
 
 /// Create a new Operation with the specific fields.
 Operation *Operation::create(Location location, OperationName name,
                              ArrayRef<Type> resultTypes,
                              ArrayRef<Value> operands,
                              ArrayRef<NamedAttribute> attributes,

 Operation *Operation::create(Location location, OperationName name,
                              ArrayRef<Type> resultTypes,
                              ArrayRef<Value> operands,
                              NamedAttributeList attributes,
                              ArrayRef<Block *> successors, unsigned numRegions,
                              bool resizableOperandList) {
   unsigned numSuccessors = successors.size();
 
+  // We only need to allocate additional memory for a subset of results.
+  unsigned numTrailingResults = OpResult::getNumTrailing(resultTypes.size());
+
   // Input operands are nullptr-separated for each successor, the null operands
   // aren't actually stored.
   unsigned numOperands = operands.size() - numSuccessors;
 
   // Compute the byte size for the operation and the operand storage.
-  auto byteSize =
-      totalSizeToAlloc<OpResult, BlockOperand, Region, detail::OperandStorage>(
-          resultTypes.size(), numSuccessors, numRegions,
-          /*detail::OperandStorage*/ 1);
+  auto byteSize = totalSizeToAlloc<detail::TrailingOpResult, BlockOperand,
+                                   Region, detail::OperandStorage>(
+      numTrailingResults, numSuccessors, numRegions,
   byteSize += llvm::alignTo(detail::OperandStorage::additionalAllocSize(
                                 numOperands, resizableOperandList),
                             alignof(Operation));
   void *rawMem = malloc(byteSize);
 
   // Create the new Operation.
-  auto op = ::new (rawMem) Operation(location, name, resultTypes.size(),
-                                     numSuccessors, numRegions, attributes);
+  auto op = ::new (rawMem) Operation(location, name, resultTypes, numSuccessors,
+                                     numRegions, attributes);
 
   assert((numSuccessors == 0 || !op->isKnownNonTerminator()) &&
          "unexpected successors in a non-terminator operation");
 
+  // Initialize the trailing results.
+  if (LLVM_UNLIKELY(numTrailingResults > 0)) {
+    // We initialize the trailing results with their result number. This makes
+    // 'getResultNumber' checks much more efficient. The main purpose for these
+    // results is to give an anchor to the main operation anyways, so this is
+    // purely an optimization.
+    auto *trailingResultIt = op->getTrailingObjects<detail::TrailingOpResult>();
+    for (unsigned i = 0; i != numTrailingResults; ++i, ++trailingResultIt)
+      trailingResultIt->trailingResultNumber = i;
+  }
+
   // Initialize the regions.
   for (unsigned i = 0; i != numRegions; ++i)
     new (&op->getRegion(i)) Region(op);
 
   // Initialize the results and operands.
   new (&op->getOperandStorage())
       detail::OperandStorage(numOperands, resizableOperandList);
-
-  auto instResults = op->getOpResults();
-  for (unsigned i = 0, e = resultTypes.size(); i != e; ++i)
-    new (&instResults[i]) OpResult(OpResult::create(resultTypes[i], op));
-
   auto opOperands = op->getOpOperands();
 
   // Initialize normal operands.
   unsigned operandIt = 0, operandE = operands.size();
   unsigned nextOperand = 0;
   for (; operandIt != operandE; ++operandIt) {
     // Null operands are used as sentinels between successor operand lists. If
     // we encounter one here, break and handle the successor operands lists
Operation *Operation::create(Location location, OperationName name,
 
   // Verify that the amount of sentinel operands is equivalent to the number of
   // successors.
   assert(currentSuccNum == numSuccessors);
 
   return op;
 }
 
-Operation::Operation(Location location, OperationName name, unsigned numResults,
-                     unsigned numSuccessors, unsigned numRegions,
-                     const NamedAttributeList &attributes)
-    : location(location), numResults(numResults), numSuccs(numSuccessors),
-      numRegions(numRegions), name(name), attrs(attributes) {}
+Operation::Operation(Location location, OperationName name,
+                     ArrayRef<Type> resultTypes, unsigned numSuccessors,
+                     unsigned numRegions, const NamedAttributeList &attributes)
+    : location(location), numSuccs(numSuccessors), numRegions(numRegions),
+      hasSingleResult(false), name(name), attrs(attributes) {
+  if (!resultTypes.empty()) {
+    // If there is a single result it is stored in-place, otherwise use a tuple.
+    hasSingleResult = resultTypes.size() == 1;
+    if (hasSingleResult)
+      resultType = resultTypes.front();
+    else
+      resultType = TupleType::get(resultTypes, location->getContext());
+  }
+}
 
 // Operations are deleted through the destroy() member because they are
 // allocated via malloc.
 Operation::~Operation() {
   assert(block == nullptr && "operation destroyed but still in a block");
 
   // Explicitly run the destructors for the operands and results.
   getOperandStorage().~OperandStorage();
 
-  for (auto &result : getOpResults())
-    result.destroy();
-
   // Explicitly run the destructors for the successors.
   for (auto &successor : getBlockOperands())
     successor.~BlockOperand();
 
   // Explicitly destroy the regions.
   for (auto &region : getRegions())
     region.~Region();
 }

 void Operation::dropAllDefinedValueUses() {
   dropAllUses();
 
   for (auto &region : getRegions())
     for (auto &block : region)
       block.dropAllDefinedValueUses();
 }
 
+/// Return the number of results held by this operation.
+unsigned Operation::getNumResults() {
+  if (!resultType)
+    return 0;
+  return hasSingleResult ? 1 : resultType.cast<TupleType>().size();
+}
+
 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());

mlir/lib/IR/OperationSupport.cpp

 
 OperandRange::OperandRange(Operation *op)
     : OperandRange(op->getOpOperands().data(), op->getNumOperands()) {}
 
 //===----------------------------------------------------------------------===//
 // ResultRange
 
 ResultRange::ResultRange(Operation *op)
-    : ResultRange(op->getOpResults().data(), op->getNumResults()) {}
+    : ResultRange(op, /*startIndex=*/0, op->getNumResults()) {}
+
+/// See `detail::indexed_accessor_range_base` for details.
+OpResult ResultRange::dereference_iterator(Operation *op, ptrdiff_t index) {
+  return op->getResult(index);
+}
 
 //===----------------------------------------------------------------------===//
 // ValueRange
 
 ValueRange::ValueRange(ArrayRef<Value> values)
     : ValueRange(values.data(), values.size()) {}
 ValueRange::ValueRange(OperandRange values)
     : ValueRange(values.begin().getBase(), values.size()) {}
 ValueRange::ValueRange(ResultRange values)
-    : ValueRange(values.begin().getBase(), values.size()) {}
+    : ValueRange(
+          {values.getBase(), static_cast<unsigned>(values.getStartIndex())},
+          values.size()) {}
 
 /// See `detail::indexed_accessor_range_base` for details.
 ValueRange::OwnerT ValueRange::offset_base(const OwnerT &owner,
                                            ptrdiff_t index) {
-  if (OpOperand *operand = owner.dyn_cast<OpOperand *>())
-    return operand + index;
-  if (OpResult *result = owner.dyn_cast<OpResult *>())
-    return result + index;
-  return owner.get<const Value *>() + index;
+  if (auto *value = owner.ptr.dyn_cast<const Value *>())
+    return {value + index};
+  if (auto *operand = owner.ptr.dyn_cast<OpOperand *>())
+    return {operand + index};
+  Operation *operation = reinterpret_cast<Operation *>(owner.ptr.get<void *>());
+  return {operation, owner.startIndex + static_cast<unsigned>(index)};
 }
 /// See `detail::indexed_accessor_range_base` for details.
 Value ValueRange::dereference_iterator(const OwnerT &owner, ptrdiff_t index) {
-  // Operands access the held value via 'get'.
-  if (OpOperand *operand = owner.dyn_cast<OpOperand *>())
+  if (auto *value = owner.ptr.dyn_cast<const Value *>())
+    return value[index];
+  if (auto *operand = owner.ptr.dyn_cast<OpOperand *>())
     return operand[index].get();
-  // An OpResult is a value, so we can return it directly.
-  if (OpResult *result = owner.dyn_cast<OpResult *>())
-    return result[index];
-  // Otherwise, this is a raw value array so just index directly.
-  return owner.get<const Value *>()[index];
+  Operation *operation = reinterpret_cast<Operation *>(owner.ptr.get<void *>());
+  return operation->getResult(owner.startIndex + index);
 }

mlir/lib/IR/Value.cpp

 //===- Value.cpp - MLIR Value Classes -------------------------------------===//
 //
 // Part of the MLIR Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/IR/Value.h"
 #include "mlir/IR/Block.h"
 #include "mlir/IR/Operation.h"
+#include "mlir/IR/StandardTypes.h"
 using namespace mlir;
 
+/// Construct a value.
+Value::Value(detail::BlockArgumentImpl *impl)
+    : ownerAndKind(impl, Kind::BlockArgument) {}
+Value::Value(Operation *op, unsigned resultNo) {
+  assert(op->getNumResults() > resultNo && "invalid result number");
+  if (LLVM_LIKELY(canPackResultInline(resultNo))) {
+    ownerAndKind = {op, static_cast<Kind>(resultNo)};
+    return;
+  }
+
+  // If we can't pack the result directly, we need to represent this as a
+  // trailing result.
+  unsigned trailingResultNo =
+      resultNo - static_cast<unsigned>(Kind::TrailingOpResult);
+  ownerAndKind = {op->getTrailingResult(trailingResultNo),
+                  Kind::TrailingOpResult};
+}
+
+/// Return the type of this value.
+Type Value::getType() const {
+  if (BlockArgument arg = dyn_cast<BlockArgument>())
+    return arg.getType();
+
+  // If this is an operation result, query the parent operation.
+  OpResult result = cast<OpResult>();
+  Operation *owner = result.getOwner();
+  if (owner->hasSingleResult)
+    return owner->resultType;
+  return owner->resultType.cast<TupleType>().getType(result.getResultNumber());
+}
+
+/// Mutate the type of this Value to be of the specified type.
+void Value::setType(Type newType) {
+  if (BlockArgument arg = dyn_cast<BlockArgument>())
+    return arg.setType(newType);
+  OpResult result = cast<OpResult>();
+
+  // If the owner has a single result, simply update it directly.
+  Operation *owner = result.getOwner();
+  if (owner->hasSingleResult) {
+    owner->resultType = newType;
+    return;
+  }
+  unsigned resultNo = result.getResultNumber();
+
+  // Otherwise, rebuild the tuple if the new type is different from the current.
+  auto curTypes = owner->resultType.cast<TupleType>().getTypes();
+  if (curTypes[resultNo] == newType)
+    return;
+  auto newTypes = llvm::to_vector<4>(curTypes);
+  newTypes[resultNo] = newType;
+  owner->resultType = TupleType::get(newTypes, newType.getContext());
+}
+
 /// If this value is the result of an Operation, return the operation that
 /// defines it.
 Operation *Value::getDefiningOp() const {
   if (auto result = dyn_cast<OpResult>())
     return result->getOwner();
   return nullptr;
 }
 

 /// 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);
 }
 
 //===----------------------------------------------------------------------===//
+// OpResult
+//===----------------------------------------------------------------------===//
+
+/// Returns the operation that owns this result.
+Operation *OpResult::getOwner() const {
+  // If the result is in-place, the `owner` is the operation.
+  if (LLVM_LIKELY(getKind() != Kind::TrailingOpResult))
+    return reinterpret_cast<Operation *>(ownerAndKind.getPointer());
+
+  // Otherwise, we need to do some arithmetic to get the operation pointer.
+  // Move the trailing owner to the start of the array.
+  auto *trailingIt =
+      static_cast<detail::TrailingOpResult *>(ownerAndKind.getPointer());
+  trailingIt -= trailingIt->trailingResultNumber;
+
+  // This point is the first trailing object after the operation. So all we need
+  // to do here is adjust for the operation size.
+  return reinterpret_cast<Operation *>(trailingIt) - 1;
+}
+
+/// Return the result number of this result.
+unsigned OpResult::getResultNumber() const {
+  // If the result is in-place, we can use the kind directly.
+  if (LLVM_LIKELY(getKind() != Kind::TrailingOpResult))
+    return static_cast<unsigned>(ownerAndKind.getInt());
+  // Otherwise, we add the number of inline results to the trailing owner.
+  auto *trailingIt =
+      static_cast<detail::TrailingOpResult *>(ownerAndKind.getPointer());
+  unsigned trailingNumber = trailingIt->trailingResultNumber;
+  return trailingNumber + static_cast<unsigned>(Kind::TrailingOpResult);
+}
+
+/// Given a number of operation results, returns the number that need to be
+/// stored as trailing.
+unsigned OpResult::getNumTrailing(unsigned numResults) {
+  // If we can pack all of the results, there is no need for additional storage.
+  if (numResults <= static_cast<unsigned>(Kind::TrailingOpResult))
+    return 0;
+  return numResults - static_cast<unsigned>(Kind::TrailingOpResult);
+}
+
+//===----------------------------------------------------------------------===//
 // BlockOperand
 //===----------------------------------------------------------------------===//
 
 /// Provide the use list that is attached to the given block.
 IRObjectWithUseList<BlockOperand> *BlockOperand::getUseList(Block *value) {
   return value;
 }
 

mlir/test/lib/Transforms/TestInlining.cpp

for (auto caller : callers) {
       if (!callee)
         continue;
 
       // Inline the functional region operation, but only clone the internal
       // region if there is more than one use.
       if (failed(inlineRegion(
               interface, &callee.body(), caller,
               llvm::to_vector<8>(caller.getArgOperands()),
-              llvm::to_vector<8>(caller.getResults()), caller.getLoc(),
+              SmallVector<Value, 8>(caller.getResults()), caller.getLoc(),
               /*shouldCloneInlinedRegion=*/!callee.getResult()->hasOneUse())))
         continue;
 
       // If the inlining was successful then erase the call and callee if
       // possible.
       caller.erase();
       if (callee.use_empty())
         callee.erase();
     }
   }
 };
 } // end anonymous namespace
 
 static PassRegistration<Inliner> pass("test-inline",
                                       "Test inlining region calls");