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

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.

Reviewed By: jpienaar

Differential Revision: https://reviews.llvm.org/D72020

8 files changed, 369 insertions, 167 deletions

diff --git a/mlir/include/mlir/IR/Operation.h b/mlir/include/mlir/IR/Operation.h
index 4bc798834fc..71d77a2df3e 100644
--- a/mlir/include/mlir/IR/Operation.h
+++ b/mlir/include/mlir/IR/Operation.h
@@ -27,7 +27,8 @@ namespace mlir {
 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.
@@ -238,9 +239,11 @@ public:
   // 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;
@@ -250,11 +253,8 @@ public:
   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;
@@ -572,7 +572,7 @@ private:
   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);
 
@@ -585,6 +585,15 @@ private:
     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
@@ -603,7 +612,18 @@ private:
   /// 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;
@@ -617,14 +637,18 @@ private:
   // 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;
diff --git a/mlir/include/mlir/IR/OperationSupport.h b/mlir/include/mlir/IR/OperationSupport.h
index 30376b8b599..cfd7447f168 100644
--- a/mlir/include/mlir/IR/OperationSupport.h
+++ b/mlir/include/mlir/IR/OperationSupport.h
@@ -453,6 +453,19 @@ private:
 } // 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
 //===----------------------------------------------------------------------===//
 
@@ -573,10 +586,11 @@ private:
 
 /// 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.
@@ -585,21 +599,39 @@ public:
 
 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
@@ -607,8 +639,7 @@ private:
 /// 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;
 
@@ -633,9 +664,7 @@ public:
   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);
diff --git a/mlir/include/mlir/IR/Value.h b/mlir/include/mlir/IR/Value.h
index acbab60554a..d4869f242c0 100644
--- a/mlir/include/mlir/IR/Value.h
+++ b/mlir/include/mlir/IR/Value.h
@@ -18,7 +18,6 @@
 #include "mlir/Support/LLVM.h"
 
 namespace mlir {
-class Block;
 class BlockArgument;
 class Operation;
 class OpResult;
@@ -26,48 +25,8 @@ 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,
@@ -76,34 +35,59 @@ class OpResultImpl : public ValueImpl {
 /// 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
@@ -112,15 +96,14 @@ public:
   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(); }
@@ -131,7 +114,7 @@ public:
   /// 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.
@@ -191,23 +174,36 @@ public:
   //===--------------------------------------------------------------------===//
   // 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);
+  }
+
+  /// Construct a value.
+  Value(detail::BlockArgumentImpl *impl);
+  Value(Operation *op, unsigned resultNo);
 
-  /// Allow access to 'impl'.
-  friend OpOperand;
+  /// 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) {
@@ -215,6 +211,26 @@ inline raw_ostream &operator<<(raw_ostream &os, Value value) {
   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:
@@ -232,6 +248,12 @@ public:
   /// 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;
 
@@ -246,7 +268,8 @@ private:
 
   /// 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`.
@@ -256,6 +279,10 @@ private:
   friend Value;
 };
 
+//===----------------------------------------------------------------------===//
+// OpResult
+//===----------------------------------------------------------------------===//
+
 /// This is a value defined by a result of an operation.
 class OpResult : public Value {
 public:
@@ -264,30 +291,23 @@ public:
   /// 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;
@@ -295,7 +315,7 @@ private:
 
 /// 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
@@ -305,16 +325,16 @@ 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.
@@ -328,18 +348,20 @@ public:
   }
   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);
@@ -360,7 +382,7 @@ public:
   }
   enum {
     NumLowBitsAvailable =
-        PointerLikeTypeTraits<mlir::detail::ValueImpl *>::NumLowBitsAvailable
+        PointerLikeTypeTraits<mlir::Value>::NumLowBitsAvailable
   };
 };
 } // end namespace llvm
diff --git a/mlir/include/mlir/Support/STLExtras.h b/mlir/include/mlir/Support/STLExtras.h
index 9a128611c6e..9e6dc421c6d 100644
--- a/mlir/include/mlir/Support/STLExtras.h
+++ b/mlir/include/mlir/Support/STLExtras.h
@@ -294,10 +294,23 @@ 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:
diff --git a/mlir/lib/IR/Operation.cpp b/mlir/lib/IR/Operation.cpp
index fd9c40f597e..6cf7eea6b4f 100644
--- a/mlir/lib/IR/Operation.cpp
+++ b/mlir/lib/IR/Operation.cpp
@@ -64,17 +64,6 @@ OperationName OperationName::getFromOpaquePointer(void *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
 //===----------------------------------------------------------------------===//
 
@@ -124,27 +113,41 @@ Operation *Operation::create(Location location, OperationName name,
                              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,
+      /*detail::OperandStorage*/ 1);
   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);
@@ -152,11 +155,6 @@ Operation *Operation::create(Location location, OperationName name,
   // 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.
@@ -208,11 +206,20 @@ Operation *Operation::create(Location location, OperationName name,
   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.
@@ -222,9 +229,6 @@ Operation::~Operation() {
   // 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();
@@ -540,6 +544,13 @@ void Operation::dropAllDefinedValueUses() {
       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);
diff --git a/mlir/lib/IR/OperationSupport.cpp b/mlir/lib/IR/OperationSupport.cpp
index 5dfd3b02cc6..436c8325cb6 100644
--- a/mlir/lib/IR/OperationSupport.cpp
+++ b/mlir/lib/IR/OperationSupport.cpp
@@ -150,7 +150,12 @@ OperandRange::OperandRange(Operation *op)
 // 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
@@ -160,25 +165,26 @@ ValueRange::ValueRange(ArrayRef<Value> values)
 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);
 }
diff --git a/mlir/lib/IR/Value.cpp b/mlir/lib/IR/Value.cpp
index fd9fda53e68..13bd0bcd8f3 100644
--- a/mlir/lib/IR/Value.cpp
+++ b/mlir/lib/IR/Value.cpp
@@ -9,8 +9,63 @@
 #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 {
@@ -84,6 +139,48 @@ bool Value::use_empty() const {
 }
 
 //===----------------------------------------------------------------------===//
+// 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
 //===----------------------------------------------------------------------===//
 
diff --git a/mlir/test/lib/Transforms/TestInlining.cpp b/mlir/test/lib/Transforms/TestInlining.cpp
index 36378283f8e..584849d0f51 100644
--- a/mlir/test/lib/Transforms/TestInlining.cpp
+++ b/mlir/test/lib/Transforms/TestInlining.cpp
@@ -46,7 +46,7 @@ struct Inliner : public FunctionPass<Inliner> {
       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;