Add MLIR interpreter framework

[logan]

Summary

This commit introduces an MLIR interpreter framework. This interpreter framework allows multiple dialects register their op implementations. The interpreter traverses the SSACFG regions, manages the mapping between SSA names and evaluated values, and calls the op implementations with the evaluated values of the operands.

[logan]

Reformat with clang-format.

[ezhulenev]

mlir/include/mlir/Interpreter/InterpreterOpInterface.h

38

Should it also provide an option to specify required alignment?

53

https://en.cppreference.com/w/cpp/types/byte instead of char?

[ezhulenev]

mlir/include/mlir/Interpreter/InterpreterOpInterface.h

38

Or should it even do manual memory management? Can it be a wrapper around std::any? You’ll get type checks, and automatic object destruction, and correct handling of alignment, plus a small value optimization for avoiding heap allocations.

[ezhulenev]

mlir/include/mlir/Interpreter/InterpreterOpInterface.h

58

I think it should become something like ::tfrt::Value (https://github.com/tensorflow/runtime/blob/master/include/tfrt/host_context/value.h), because right now the assumption is that whoever creates EvalValueImpl owns the storage behind the pointer, and it's hard to find such place inside the interpret interface implementation. It can't go to heap either, because there is no way to tell when it should be destructed.

mlir/docs/Interpreter.md

+# MLIR Interpreter
+
+This directory contains a simple MLIR interpreter for multiple registered
+dialects. This interpreter traverses SSACFG regions, maintains the control flow,
+maps SSA names to evaluated results, and calls the operation implementation
+through the `InterpreterOpInterface`.
+
+## Define a dialect interpreter
+
+To build an interpreter for a new dialect, a `DialectInterpreter` class must be
+defined:
+
+```
+class YourDialectInterpreter {
+public:
+  using Dialect = YourDialect;
+  using Context = ...;
+
+  // Attach the InterpreterOpInterface to the operations.
+  static void attachInterface(MLIRContext &context);
+
+  // Create an interpreter context.
+  static Context *createContext(...) { ... }
+
+  // Destroy the interpreter context.
+  static void destroyContext(Context *) {}
+};
+```
+
+This class must define the following members:
+
+1.  `Dialect` - A type alias for the dialect being interpreted.
+2.  `attachInterface` - A static method that attaches `InterpreterOpInterface`
+    to the operations in the dialect.
+3.  `Context` - A context type for the dialect interpreter.
+4.  `createContext` - A static method to create the context for dialect
+    interpreter. This function will be called when the dialect interpreter is
+    registered to the `Interpreter` class.
+5.  `destroyContext` - A static method to destroy the dialect interpreter
+    context.
+
+Next, the operations in the dialect must implement `InterpreterOpInterface`.
+There are two approaches.
+
+The recommended approach is to define a derived class of
+`InterpreterOpInterface::ExternalModel<OpInterpreterClassName, Op>` and register
+it in the `attachInterface` static member function:
+
+```
+struct YourOpInterpreter
+    : public InterpreterOpInterface::ExternalModel<YourOpInterpreter,
+                                                   YourOp> {
+  static EvalResult interpret(Operation *op, Interpreter &interpreter,
+                              ArrayRef<EvalValue> operands) {
+    // ...
+  }
+};
+
+void YourDialectInterpreter::attachInterface(MLIRContext &context) {
+  YourOp::attachInterface<YourOpInterpreter>(context);
+}
+```
+
+The second approach is to add `DeclareOpInterfaceMethods` to the operation
+definition in the TableGen file:
+
+```
+include "mlir/Interpreter/InterpreterOpInterface.td"
+
+def YourOp : Op<YourDialect, "your_op_mnemonic", [
+    DeclareOpInterfaceMethods<InterpreterOpInterface,
+        ["interpret"]>]> {
+  // ...
+}
+```
+
+and define the `interpret` method in the C++ file:
+
+```
+#include "mlir/Interpreter/Interpreter.h"
+#include "mlir/Interpreter/InterpreterOpInterface.h"
+
+EvalResult YourOp::interpret(Interpreter &interpreter,
+                             ArrayRef<EvalValue> operands) {
+  // ...
+}
+```
+
+Note: The shortcoming of the second approach is that the interpreter
+implementation must be linked with the operation definition, thus the first
+approach is recommended.
+
+## Register a dialect interpreter
+
+Register a dialect interpreter with the `registerDialectInterpreter` method. The
+arguments of `registerDialectInterpreter` will be forwarded to
+`YourDialectInterpreter::createContext` function.
+
+```
+MLIRContext context;
+Interpreter interpreter(context);
+interpreter.registerDialectInterpreter<YourDialectInterpreter>(...);
+```
+
+## Interpret a function
+
+To interpret a function:
+
+```
+OwningOpRef<mlir::ModuleOp> yourModuleOp =
+    loadYourModule(interpreter.getContext());
+interpreter.setModule(*yourModuleOp);
+
+SmallVector<EvalValue, 4> arguments;
+arguments.push_back(interpreter.createEvalValue(type, ...));
+
+EvalResult result = interpreter.execute("yourFunctionName", arguments);
+
+if (result.getKind() == EvalResultKind::Error) {
+  // handle errors
+} else if (result.getKind() == EvalResultKind::ReturnValue) {
+  ArrayRef<EvalValue> returnValues = result.getValues();
+  // ...
+}
+```
+
+## Interpret an operation
+
+The interpreter can interpret an operation as well. However, if the operation
+has references to escaped SSA names (i.e. non-operand SSA names defined by outer
+regions), the caller must set up the function frame, the region frame, and the
+SSA name mapping properly:
+
+```
+ScopedFunctionFrame functionFrameGuard(interpreter);
+ScopedRegionFrame regionFrameGuard(interpreter);
+
+Value escapedName = ...;
+interpreter.setEvalValue(escapedName, interpreter.createEvalValue(type, ...));
+
+SmallVector<EvalValue, 4> arguments;
+arguments.push_back(interpreter.createEvalValue(type, ...));
+
+Operation *op = ...;
+EvalResult result = interpreter.execute(op, arguments);
+
+if (result.getKind() == EvalResultKind::Error) {
+  // handle errors
+} else if (result.getKind() == EvalResultKind::ReturnValue) {
+  ArrayRef<EvalValue> returnValues = result.getValues();
+  // ...
+}
+```

mlir/include/mlir/CMakeLists.txt

 add_subdirectory(Conversion)
 add_subdirectory(Dialect)
 add_subdirectory(IR)
 add_subdirectory(Interfaces)
+add_subdirectory(Interpreter)
 add_subdirectory(Reducer)
 add_subdirectory(Transforms)

mlir/include/mlir/Interpreter/CMakeLists.txt

+add_mlir_interface(InterpreterOpInterface)

mlir/include/mlir/Interpreter/Dialects/FuncInterpreter.h

+//===- FuncInterpreter.h - Func dialect interpreter -------------*- C++ -*-===//
+//
+// Part of the LLVM 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the dialect interpreter declaration for the Func dialect.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_INTERPRETER_DIALECTS_FUNCINTERPRETER_H_
+#define MLIR_INTERPRETER_DIALECTS_FUNCINTERPRETER_H_
+
+#include "mlir/Dialect/Func/IR/FuncOps.h"
+#include "mlir/IR/MLIRContext.h"
+
+namespace mlir {
+
+/// Dialect interpreter for the Func dialect.
+class FuncInterpreter {
+public:
+  using Dialect = func::FuncDialect;
+  using Context = void;
+
+  /// Attach the InterpreterOpInterface to the ops in the Func dialect.
+  static void attachInterface(MLIRContext &context);
+
+  /// Create an interpreter context.
+  static Context *createContext() { return nullptr; }
+
+  /// Destroy the interpreter context.
+  static void destroyContext(Context *) {}
+};
+
+} // namespace mlir
+
+#endif // MLIR_INTERPRETER_DIALECTS_FUNCINTERPRETER_H_

mlir/include/mlir/Interpreter/Interpreter.h

+//===- Interpreter.h - MLIR Interpreter API ---------------------*- C++ -*-===//
+//
+// Part of the LLVM 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the Interpreter class and the APIs of the interpreter.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_INTERPRETER_INTERPRETER_H_
+#define MLIR_INTERPRETER_INTERPRETER_H_
+
+#include "mlir/Dialect/Func/IR/FuncOps.h"
+#include "mlir/IR/BuiltinOps.h"
+#include "mlir/IR/MLIRContext.h"
+#include "mlir/Interpreter/InterpreterOpInterface.h"
+#include "mlir/Support/LogicalResult.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+
+#include <cassert>
+#include <forward_list>
+#include <utility>
+
+namespace mlir {
+
+namespace detail {
+
+// Owning pointer for type-erased dialect op interpreter context.
+class OwningDialectInterpreterContext {
+public:
+  OwningDialectInterpreterContext() : context(nullptr), deleter(nullptr) {}
+  OwningDialectInterpreterContext(void *context, void (*deleter)(void *))
+      : context(context), deleter(deleter) {}
+  OwningDialectInterpreterContext(OwningDialectInterpreterContext &&rhs)
+      : context(rhs.context), deleter(rhs.deleter) {
+    rhs.context = nullptr;
+    rhs.deleter = nullptr;
+  }
+  OwningDialectInterpreterContext &
+  operator=(OwningDialectInterpreterContext &&rhs) {
+    if (&rhs != this) {
+      context = rhs.context;
+      deleter = rhs.deleter;
+      rhs.context = nullptr;
+      rhs.deleter = nullptr;
+    }
+    return *this;
+  }
+  ~OwningDialectInterpreterContext() {
+    if (context) {
+      deleter(context);
+    }
+  }
+
+  void *get() const { return context; }
+
+private:
+  void *context;
+  void (*deleter)(void *);
+
+private:
+  OwningDialectInterpreterContext(const OwningDialectInterpreterContext &) =
+      delete;
+  OwningDialectInterpreterContext &
+  operator=(const OwningDialectInterpreterContext &rhs) = delete;
+};
+
+} // namespace detail
+
+class Interpreter {
+public:
+  explicit Interpreter(MLIRContext &context,
+                       bool enableStackTraceOnError = false);
+
+  //===--------------------------------------------------------------------===//
+  // Dialect interpreter registration
+  //===--------------------------------------------------------------------===//
+
+  /// Register a dialect op interpreter.
+  template <typename DialectInterpreter, typename... Args>
+  void registerDialectInterpreter(Args &&...args) {
+    using Dialect = typename DialectInterpreter::Dialect;
+
+    // Register and load the dialect.
+    DialectRegistry dialects;
+    dialects.insert<Dialect>();
+    context->appendDialectRegistry(dialects);
+    context->loadDialect<Dialect>();
+
+    // Attach op interfaces.
+    DialectInterpreter::attachInterface(*context);
+
+    // Create dialect contexts.
+    detail::OwningDialectInterpreterContext context(
+        DialectInterpreter::createContext(std::forward<Args>(args)...),
+        [](void *context) {
+          using Context = typename DialectInterpreter::Context;
+          DialectInterpreter::destroyContext(
+              reinterpret_cast<Context *>(context));
+        });
+    dialectContexts[Dialect::getDialectNamespace()] = std::move(context);
+  }
+
+  template <typename DialectInterpreter, typename OtherDialectInterpreter,
+            typename... MoreDialectInterpreters, typename... Args>
+  void registerDialectInterpreter(Args &&...args) {
+    registerDialectInterpreter<DialectInterpreter>();
+    registerDialectInterpreter<OtherDialectInterpreter,
+                               MoreDialectInterpreters...>(
+        std::forward<Args>(args)...);
+  }
+
+  /// Get the dialect interpreter context.
+  template <typename DialectInterpreter>
+  typename DialectInterpreter::Context *getDialectInterpreterContext() const {
+    using Dialect = typename DialectInterpreter::Dialect;
+    auto iter = dialectContexts.find(Dialect::getDialectNamespace());
+    if (iter == dialectContexts.end()) {
+      return nullptr;
+    }
+    return reinterpret_cast<typename DialectInterpreter::Context *>(
+        iter->second.get());
+  }
+
+  //===--------------------------------------------------------------------===//
+  // MLIRContext and Module accessors
+  //===--------------------------------------------------------------------===//
+
+  /// Get the MLIR context.
+  MLIRContext &getContext() { return *context; }
+
+  /// Get the ModuleOp.
+  ModuleOp getModule() { return module; }
+
+  /// Set the ModuleOp.
+  void setModule(ModuleOp newModule) { module = newModule; }
+
+  //===--------------------------------------------------------------------===//
+  // Execution functions
+  //===--------------------------------------------------------------------===//
+
+  /// Find the function by name and execute the function with the function
+  /// arguments.
+  EvalResult execute(StringRef entry_func_name, ArrayRef<EvalValue> arguments);
+
+  /// Execute a function with the function arguments.
+  EvalResult execute(func::FuncOp func, ArrayRef<EvalValue> arguments);
+
+  /// Function argument provider callback function.
+  ///
+  /// All `execute` methods for `func::FuncOp` (or function name) has a variant
+  /// that takes `ArgumentProviderRef`. These `execute` methods pass the
+  /// function argument types to `argument_provider` and use the returned values
+  /// as actual arguments. With this interface, the callers of `execute` don't
+  /// have to find the `func::FuncOp` and extract its argument types by
+  /// themselves.
+  using ArgumentProviderRef =
+      llvm::function_ref<EvalResult(Interpreter &, TypeRange)>;
+
+  /// Find the function by name and execute the function with the function
+  /// arguments from the argument provider.
+  EvalResult execute(StringRef entry_func_name,
+                     ArgumentProviderRef argument_provider);
+
+  /// Execute a function with the function arguments from the argument provider.
+  EvalResult execute(func::FuncOp func, ArgumentProviderRef argument_provider);
+
+  /// Execute a region with the block arguments of the entry block.
+  EvalResult execute(Region &region, ArrayRef<EvalValue> arguments);
+
+  /// Execute a block with the block arguments.
+  EvalResult execute(Block &block, ArrayRef<EvalValue> arguments);
+
+  /// Execute an operation (get the input operands from the
+  /// SSA-name-to-evaluated-value map).
+  EvalResult execute(Operation &operation);
+
+  /// Execute an operation with the input operands.
+  EvalResult execute(Operation &operation, ArrayRef<EvalValue> operands);
+
+  //===--------------------------------------------------------------------===//
+  // Interpreter frame management functions
+  //===--------------------------------------------------------------------===//
+
+  /// Push a function frame (SSA lookup only can search up to the function
+  /// frame. The callee must not refer the SSA defined by the caller.)
+  void pushFunctionFrame() {
+    evalValueMapStack.push_front(std::forward_list<EvalValueMap>());
+  }
+
+  /// Pop a function frame.
+  void popFunctionFrame() {
+    assert(!evalValueMapStack.empty() && "function frame must be available");
+    assert(evalValueMapStack.front().empty() &&
+           "all region frames must be popped");
+    evalValueMapStack.pop_front();
+  }
+
+  /// Push a region frame (SSA lookup can search the outer region frame up
+  /// until the function frame).
+  void pushRegionFrame() {
+    assert(!evalValueMapStack.empty() && "function frame must be available");
+    evalValueMapStack.front().push_front(EvalValueMap());
+  }
+
+  /// Pop a region frame.
+  void popRegionFrame() {
+    assert(!evalValueMapStack.empty() && "function frame must be available");
+    assert(!evalValueMapStack.front().empty() &&
+           "region frame must be available");
+    evalValueMapStack.front().pop_front();
+  }
+
+  /// Get the evaluated value of an SSA name.
+  EvalValue getEvalValue(Value ssaName) const {
+    assert(!evalValueMapStack.empty() && "function frame must be available");
+    for (auto stackIter = evalValueMapStack.front().begin();
+         stackIter != evalValueMapStack.front().end(); ++stackIter) {
+      auto iter = stackIter->find(ssaName);
+      if (iter != stackIter->end()) {
+        return iter->second;
+      }
+    }
+    return EvalValue();
+  }
+
+  /// Bind an SSA name to an evaluated value.
+  void setEvalValue(Value ssaName, EvalValue value) {
+    assert(!evalValueMapStack.empty() && "function frame must be available");
+    assert(!evalValueMapStack.front().empty() &&
+           "region frame must be available");
+    evalValueMapStack.front().front()[ssaName] = value;
+  }
+
+  /// Bind SSA names to evaluated values. Returns failure if the number of the
+  /// SSA names and the number of the evaluated values mismatches.
+  LogicalResult setEvalValues(ValueRange ssaNames,
+                              ArrayRef<EvalValue> evalValues);
+
+  //===--------------------------------------------------------------------===//
+  // EvalResult functions
+  //===--------------------------------------------------------------------===//
+
+  /// Create an EvalResult for an error message.
+  EvalResult createErrorResult(StringRef errorMessage);
+
+  /// Create an EvalResult to bind op results to values.
+  EvalResult createBindValueResult(ArrayRef<EvalValue> values) {
+    return EvalResult(EvalResultKind::BindValue, values, nullptr, nullptr);
+  }
+
+  /// Create an EvalResult for returning values.
+  EvalResult createReturnValueResult(ArrayRef<EvalValue> values) {
+    return EvalResult(EvalResultKind::ReturnValue, values, nullptr, nullptr);
+  }
+
+  /// Create an EvalResult for yielding values.
+  EvalResult createYieldValueResult(ArrayRef<EvalValue> values) {
+    return EvalResult(EvalResultKind::YieldValue, values, nullptr, nullptr);
+  }
+
+  /// Create an EvalResult for branching to another block.
+  EvalResult createBranchResult(Block &destBlock, ArrayRef<EvalValue> values) {
+    return EvalResult(EvalResultKind::Branch, values, &destBlock, nullptr);
+  }
+
+  //===--------------------------------------------------------------------===//
+  // EvalValue functions
+  //===--------------------------------------------------------------------===//
+
+  /// Create an EvalValue with uninitialized data buffer.
+  EvalValue createEvalValue(Type type, size_t dataSizeInBytes);
+
+  /// Create an EvalValue and initialize with `data`.
+  EvalValue createEvalValue(Type type, const void *data,
+                            size_t dataSizeInBytes);
+
+  /// Create an EvalValue and initialize with `data`.
+  template <typename T>
+  EvalValue createEvalValue(Type type, llvm::ArrayRef<T> data) {
+    return createEvalValue(type, reinterpret_cast<const char *>(data.data()),
+                           sizeof(T) * data.size());
+  }
+
+private:
+  /// Mapping from SSA names to evaluated value. This represents a value lookup
+  /// scope within a region.
+  using EvalValueMap = llvm::DenseMap<Value, EvalValue>;
+
+  /// Mapping from dialect names to their interpreter context.
+  using DialectInterpreterContextMap =
+      llvm::DenseMap<llvm::StringRef, detail::OwningDialectInterpreterContext>;
+
+  /// Mapping from dialect names to dialect interpreter contexts.
+  DialectInterpreterContextMap dialectContexts;
+
+  /// MLIRContext for this interpreter.
+  MLIRContext *context;
+
+  /// ModuleOp being interpreted. Typically, the interpreter will search the
+  /// callee function within this module.
+  ModuleOp module;
+
+  /// Stack for the mappings from SSA name to evaluated value.
+  std::forward_list<std::forward_list<EvalValueMap>> evalValueMapStack;
+
+  /// Whether the interpreter should include a stack trace in `EvalError`.
+  bool enableStackTraceOnError;
+
+private:
+  Interpreter(const Interpreter &) = delete;
+  Interpreter &operator=(const Interpreter &) = delete;
+};
+
+/// Helper class to push and pop a function frame in a C++ scope.
+class ScopedFunctionFrame {
+private:
+  Interpreter &interpreter;
+
+public:
+  explicit ScopedFunctionFrame(Interpreter &interpreter)
+      : interpreter(interpreter) {
+    interpreter.pushFunctionFrame();
+  }
+
+  ~ScopedFunctionFrame() { interpreter.popFunctionFrame(); }
+};
+
+/// Helper class to push and pop a region frame in a C++ scope.
+class ScopedRegionFrame {
+private:
+  Interpreter &interpreter;
+
+public:
+  explicit ScopedRegionFrame(Interpreter &interpreter)
+      : interpreter(interpreter) {
+    interpreter.pushRegionFrame();
+  }
+
+  ~ScopedRegionFrame() { interpreter.popRegionFrame(); }
+};
+
+} // namespace mlir
+
+#endif // MLIR_INTERPRETER_INTERPRETER_H_

mlir/include/mlir/Interpreter/InterpreterOpInterface.h

+//===- CopyOpInterface.h - copy operations interface ----------------------===//
+//
+// Part of the LLVM 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the operation interface for the interpretable
+// operations.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_INTERFACES_INTERPRETEROPINTERFACE_H_
+#define MLIR_INTERFACES_INTERPRETEROPINTERFACE_H_
+
+#include "mlir/Dialect/Traits.h"
+#include "mlir/IR/OpDefinition.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/IntrusiveRefCntPtr.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+
+#include <memory>
+#include <string>
+#include <utility>
+
+namespace mlir {
+
+class Interpreter;
+
+namespace detail {
+class EvalValueImpl : public llvm::RefCountedBase<EvalValueImpl> {
+public:
+  constexpr static size_t kAlign = 8;
+
+public:
+  EvalValueImpl(Type type, size_t dataSize) : type(type), data(dataSize, 0) {}
+
+  EvalValueImpl(Type type, llvm::ArrayRef<char> data)
+      : type(type), data(data.begin(), data.end()) {}
+
+  Type getType() const { return type; }
+
+  size_t getRawDataSizeInBytes() const { return data.size(); }
+
+  char *getRawData() { return data.data(); }
+
+  const char *getRawData() const { return data.data(); }
+
+private:
+  Type type;
+  std::vector<char> data;
+};
+} // namespace detail
+
+/// A handle to the evaluated value.
+class EvalValue {
+private:
+  friend class Interpreter;
+
+public:
+  EvalValue();
+  ~EvalValue();
+  EvalValue(const EvalValue &src);
+  EvalValue &operator=(const EvalValue &src);
+  EvalValue(EvalValue &&src);
+  EvalValue &operator=(EvalValue &&src);
+
+private:
+  explicit EvalValue(detail::EvalValueImpl *impl);
+
+public:
+  /// Returns the type of the evaluated value.
+  Type getType() const;
+
+  /// Returns the data buffer size for the evaluated value.
+  size_t getRawDataSizeInBytes() const;
+
+  /// Returns the data buffer for the evaluated value.
+  char *getRawData();
+
+  /// Returns the data buffer for the evaluated value.
+  const char *getRawData() const;
+
+  /// Returns the data for the evaluated value.
+  template <typename DataType>
+  llvm::MutableArrayRef<DataType> getData() {
+    size_t dataSizeInBytes = getRawDataSizeInBytes();
+    assert(dataSizeInBytes % sizeof(DataType) == 0);
+    return llvm::makeMutableArrayRef<DataType>(
+        reinterpret_cast<DataType *>(getRawData()),
+        dataSizeInBytes / sizeof(DataType));
+  }
+
+  /// Returns the data for the evaluated value.
+  template <typename DataType>
+  llvm::ArrayRef<DataType> getData() const {
+    size_t dataSizeInBytes = getRawDataSizeInBytes();
+    assert(dataSizeInBytes % sizeof(DataType) == 0);
+    return llvm::makeArrayRef<DataType>(
+        reinterpret_cast<const DataType *>(getRawData()),
+        dataSizeInBytes / sizeof(DataType));
+  }
+
+  /// Returns whether this handle holds a null value.
+  explicit operator bool() const { return static_cast<bool>(impl); }
+
+  /// Checks whether `this` and `rhs` refer to the same value.
+  bool operator==(const EvalValue &rhs) const { return impl == rhs.impl; }
+
+  /// Checks whether `this` and `rhs` refer to different values.
+  bool operator!=(const EvalValue &rhs) const { return impl != rhs.impl; }
+
+private:
+  llvm::IntrusiveRefCntPtr<detail::EvalValueImpl> impl;
+};
+
+/// A class to represent interpreter evaluation errors.
+class EvalError {
+public:
+  explicit EvalError(llvm::StringRef message,
+                     bool shouldPrintStackTrace = false);
+
+  /// Get the error message.
+  const std::string &getMessage() const { return message; }
+
+  /// Get the stack trace.
+  const std::string &getStackTrace() const { return stacktrace; }
+
+private:
+  std::string message;
+  std::string stacktrace;
+};
+
+/// Evaluation result states.
+enum class EvalResultKind {
+  /// An error occurs in the interpreter. In this state, `getError()` returns
+  /// an `EvalError` object.
+  Error,
+
+  /// Bind evaluated values to the op result SSA names. In this state,
+  /// `getValues()` returns the evaluated values which should be bound to SSA
+  /// names.
+  BindValue,
+
+  /// Return evaluated values to the caller. In this state, `getValues()`
+  /// returns the evaluated values which should be treated as the function
+  /// return values.
+  ///
+  /// Note: Typically, `ReturnValue` may pop multiple regions until it is
+  /// handled by a call op.
+  ReturnValue,
+
+  /// Return evaluated values to the parent op. In this state, `getValues()`
+  /// returns the evaluated values which should be treated as the region yield
+  /// values.
+  ///
+  /// Note: Typically, `YieldValue` only pops one region and will be handled by
+  /// the parent op.
+  YieldValue,
+
+  /// Branch to a new block. In this state, `getBlock()` returns the
+  /// destination block and `getValues()` returns the block arguments.
+  Branch,
+};
+
+/// A class to represent the interpreter evaluation results.
+class EvalResult {
+  friend class Interpreter;
+
+public:
+  EvalResult() : kind(EvalResultKind::Error) {}
+
+private:
+  EvalResult(EvalResultKind kind, llvm::ArrayRef<EvalValue> values,
+             Block *block, std::unique_ptr<EvalError> error)
+      : kind(kind), values(values.begin(), values.end()), block(block),
+        error(std::move(error)) {}
+
+public:
+  /// Get the evaluation result kind.
+  EvalResultKind getKind() const { return kind; }
+
+  /// Get the evaluated values for BindValue, ReturnValue, and YieldValue and
+  /// the block arguments for Branch.
+  llvm::ArrayRef<EvalValue> getValues() { return llvm::makeArrayRef(values); }
+  llvm::ArrayRef<EvalValue> getValues() const {
+    return llvm::makeArrayRef(values);
+  }
+
+  /// Get the branch destination block.
+  Block *getBlock() const { return block; }
+
+  /// Get the evaluation error.
+  const EvalError &getError() const { return *error; }
+
+private:
+  EvalResultKind kind;
+  llvm::SmallVector<EvalValue, 1> values;
+  Block *block;
+  std::unique_ptr<EvalError> error;
+};
+
+} // namespace mlir
+
+/// Include the generated interface declarations.
+#include "mlir/Interpreter/InterpreterOpInterface.h.inc"
+
+#endif // MLIR_INTERFACES_INTERPRETEROPINTERFACE_H_

mlir/include/mlir/Interpreter/InterpreterOpInterface.td

+//===- InterpreterOpInterface.td - Interpreter interface ---*- tablegen -*-===//
+//
+// Part of the LLVM 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains an op interface for interpretable operations.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_INTERPRETEROPINTERFACE
+
+include "mlir/IR/OpBase.td"
+
+def InterpreterOpInterface : OpInterface<"InterpreterOpInterface"> {
+  let description = [{
+    This is the OpInterface for the interpreter implementation.
+  }];
+
+  let methods = [
+    InterfaceMethod<[{
+        Returns the results of the op given the input arguments.
+      }],
+      "::mlir::EvalResult", "interpret",
+      (ins "::mlir::Interpreter &":$interpreter,
+           "::llvm::ArrayRef<::mlir::EvalValue>":$operands)
+    >,
+  ];
+
+  let cppNamespace = "::mlir";
+}
+
+#endif // MLIR_INTERPRETEROPINTERFACE

mlir/lib/CMakeLists.txt

 # Enable errors for any global constructors.
 add_flag_if_supported("-Werror=global-constructors" WERROR_GLOBAL_CONSTRUCTOR)
 
 add_subdirectory(Analysis)
 add_subdirectory(Conversion)
 add_subdirectory(Dialect)
 add_subdirectory(IR)
 add_subdirectory(Interfaces)
+add_subdirectory(Interpreter)
 add_subdirectory(Parser)
 add_subdirectory(Pass)
 add_subdirectory(Reducer)
 add_subdirectory(Rewrite)
 add_subdirectory(Support)
 add_subdirectory(TableGen)
 add_subdirectory(Target)
 add_subdirectory(Tools)
 add_subdirectory(Transforms)
 add_subdirectory(ExecutionEngine)

mlir/lib/Interpreter/CMakeLists.txt

+add_subdirectory(Dialects)
+
+add_mlir_library(MLIRInterpreter
+  Interpreter.cpp
+  InterpreterOpInterface.cpp
+
+  ADDITIONAL_HEADER_DIRS
+  ${MLIR_MAIN_INCLUDE_DIR}/mlir/Interpreter
+
+  DEPENDS
+  MLIRInterpreterOpInterfaceIncGen
+
+  LINK_LIBS PUBLIC
+  MLIRSupport
+  )

mlir/lib/Interpreter/Dialects/CMakeLists.txt

+add_mlir_library(MLIRFuncInterpreter
+  FuncInterpreter.cpp
+
+  ADDITIONAL_HEADER_DIRS
+  ${MLIR_MAIN_INCLUDE_DIR}/mlir/Interpreter
+
+  DEPENDS
+  MLIRInterpreterOpInterfaceIncGen
+
+  LINK_LIBS PUBLIC
+  MLIRFuncDialect
+  MLIRInterpreter
+  MLIRSupport
+  )

mlir/lib/Interpreter/Dialects/FuncInterpreter.cpp

+#include "mlir/Interpreter/Dialects/FuncInterpreter.h"
+
+#include "mlir/Dialect/Func/IR/FuncOps.h"
+#include "mlir/IR/MLIRContext.h"
+#include "mlir/Interpreter/Interpreter.h"
+#include "mlir/Interpreter/InterpreterOpInterface.h"
+
+using namespace mlir;
+
+namespace {
+
+class ReturnOpInterpreter
+    : public InterpreterOpInterface::ExternalModel<ReturnOpInterpreter,
+                                                   func::ReturnOp> {
+public:
+  static EvalResult interpret(Operation *op, Interpreter &interpreter,
+                              ArrayRef<EvalValue> operands) {
+    return interpreter.createReturnValueResult(operands);
+  }
+};
+
+} // namespace
+
+void FuncInterpreter::attachInterface(MLIRContext &context) {
+  func::ReturnOp::attachInterface<ReturnOpInterpreter>(context);
+}

mlir/lib/Interpreter/Interpreter.cpp

+#include "mlir/Interpreter/Interpreter.h"
+
+#include "mlir/IR/MLIRContext.h"
+#include "mlir/IR/RegionKindInterface.h"
+#include "mlir/Interpreter/InterpreterOpInterface.h"
+#include "mlir/Support/DebugStringHelper.h"
+#include "llvm/ADT/SmallVector.h"
+
+using namespace mlir;
+
+EvalValue::EvalValue() : impl(nullptr) {}
+EvalValue::~EvalValue() = default;
+EvalValue::EvalValue(const EvalValue &src) = default;
+EvalValue &EvalValue::operator=(const EvalValue &src) = default;
+EvalValue::EvalValue(EvalValue &&src) = default;
+EvalValue &EvalValue::operator=(EvalValue &&src) = default;
+EvalValue::EvalValue(detail::EvalValueImpl *impl) : impl(impl) {}
+
+Type EvalValue::getType() const { return impl->getType(); }
+
+size_t EvalValue::getRawDataSizeInBytes() const {
+  return impl->getRawDataSizeInBytes();
+}
+
+char *EvalValue::getRawData() { return impl->getRawData(); }
+
+const char *EvalValue::getRawData() const { return impl->getRawData(); }
+
+Interpreter::Interpreter(MLIRContext &context, bool enableStackTraceOnError)
+    : context(&context), enableStackTraceOnError(enableStackTraceOnError) {}
+
+EvalResult Interpreter::execute(StringRef entryFuncName,
+                                ArrayRef<EvalValue> arguments) {
+  func::FuncOp func = module.lookupSymbol<func::FuncOp>(entryFuncName);
+  if (!func) {
+    return createErrorResult("failed to find function by name");
+  }
+  return execute(func, arguments);
+}
+
+EvalResult Interpreter::execute(StringRef entryFuncName,
+                                ArgumentProviderRef argumentProvider) {
+  func::FuncOp func = module.lookupSymbol<func::FuncOp>(entryFuncName);
+  if (!func) {
+    return createErrorResult("failed to find function by name");
+  }
+  return execute(func, argumentProvider);
+}
+
+EvalResult Interpreter::execute(func::FuncOp func,
+                                ArrayRef<EvalValue> arguments) {
+  ScopedFunctionFrame functionFrameGuard(*this);
+  return execute(func.getBody(), arguments);
+}
+
+EvalResult Interpreter::execute(func::FuncOp func,
+                                ArgumentProviderRef argumentProvider) {
+  EvalResult arguments =
+      argumentProvider(*this, func.getFunctionType().getInputs());
+  if (arguments.getKind() != EvalResultKind::BindValue) {
+    return arguments;
+  }
+  return execute(func, arguments.getValues());
+}
+
+EvalResult Interpreter::execute(Region &region, ArrayRef<EvalValue> arguments) {
+  // Check the region kind.
+  if (Operation *parent_op = region.getParentOp()) {
+    if (parent_op->isRegistered()) {
+      if (auto interface = dyn_cast<RegionKindInterface>(parent_op)) {
+        if (interface.getRegionKind(region.getRegionNumber()) !=
+            RegionKind::SSACFG) {
+          return createErrorResult("only SSACFG region can be interpreted");
+        }
+      }
+    }
+  }
+
+  ScopedRegionFrame regionFrameGuard(*this);
+
+  // Executes the operations in the blocks.
+  EvalResult result = createBranchResult(region.front(), arguments);
+  while (true) {
+    result = execute(*result.getBlock(), arguments);
+    switch (result.getKind()) {
+    case EvalResultKind::Error:
+      return result;
+    case EvalResultKind::BindValue:
+      return createErrorResult(
+          "region evaluation result must be return or yield");
+    case EvalResultKind::ReturnValue:
+    case EvalResultKind::YieldValue:
+      return result;
+    case EvalResultKind::Branch:
+      break;
+    }
+  }
+}
+
+EvalResult Interpreter::execute(Block &block, ArrayRef<EvalValue> arguments) {
+  if (failed(setEvalValues(ValueRange(block.getArguments()), arguments))) {
+    return createErrorResult(
+        "number of formal arguments and actual arguments mismatch");
+  }
+
+  for (auto &op : block) {
+    EvalResult result = execute(op);
+    switch (result.getKind()) {
+    case EvalResultKind::Error:
+      return result;
+    case EvalResultKind::BindValue: {
+      if (failed(
+              setEvalValues(ValueRange(op.getResults()), result.getValues()))) {
+        return createErrorResult("number of op results mismatch");
+      }
+      continue;
+    }
+    case EvalResultKind::ReturnValue:
+    case EvalResultKind::YieldValue:
+    case EvalResultKind::Branch:
+      return result;
+    }
+  }
+
+  return createErrorResult("block does not end with a terminator op");
+}
+
+EvalResult Interpreter::execute(Operation &op) {
+  llvm::SmallVector<EvalValue, 8> operands;
+  for (Value operand : op.getOperands()) {
+    operands.push_back(getEvalValue(operand));
+  }
+  return execute(op, operands);
+}
+
+EvalResult Interpreter::execute(Operation &op, ArrayRef<EvalValue> operands) {
+  if (auto interface = dyn_cast<InterpreterOpInterface>(&op)) {
+    return interface.interpret(*this, operands);
+  }
+
+  return createErrorResult("op does not implement InterpreterOpInterface: " +
+                           debugString(op));
+}
+
+LogicalResult Interpreter::setEvalValues(ValueRange ssaNames,
+                                         ArrayRef<EvalValue> evalValues) {
+  if (ssaNames.size() != evalValues.size()) {
+    return LogicalResult::failure();
+  }
+  for (auto pair : llvm::zip(ssaNames, evalValues)) {
+    setEvalValue(std::get<0>(pair), std::get<1>(pair));
+  }
+  return LogicalResult::success();
+}
+
+EvalResult Interpreter::createErrorResult(StringRef errorMessage) {
+  return EvalResult(
+      EvalResultKind::Error, {}, nullptr,
+      std::make_unique<EvalError>(errorMessage, enableStackTraceOnError));
+}
+
+EvalValue Interpreter::createEvalValue(Type type, size_t dataSizeInBytes) {
+  auto implPtr =
+      llvm::makeIntrusiveRefCnt<detail::EvalValueImpl>(type, dataSizeInBytes);
+  return EvalValue(implPtr.get());
+}
+
+EvalValue Interpreter::createEvalValue(Type type, const void *data,
+                                       size_t dataSizeInBytes) {
+  auto implPtr = llvm::makeIntrusiveRefCnt<detail::EvalValueImpl>(
+      type, llvm::makeArrayRef<char>(static_cast<const char *>(data),
+                                     dataSizeInBytes));
+  return EvalValue(implPtr.get());
+}

mlir/lib/Interpreter/InterpreterOpInterface.cpp

+#include "mlir/Interpreter/InterpreterOpInterface.h"
+
+#include "llvm/Support/Signals.h"
+#include "llvm/Support/raw_ostream.h"
+
+/// Include the definitions of the interpreter op interface.
+#include "mlir/Interpreter/InterpreterOpInterface.cpp.inc"
+
+using namespace mlir;
+
+EvalError::EvalError(llvm::StringRef message, bool shouldPrintStackTrace)
+    : message(message.str()) {
+  if (shouldPrintStackTrace) {
+    llvm::raw_string_ostream stream(stacktrace);
+    llvm::sys::PrintStackTrace(stream);
+  }
+}

mlir/unittests/CMakeLists.txt

 set_target_properties(MLIRUnitTests PROPERTIES FOLDER "MLIR Tests")
 
 function(add_mlir_unittest test_dirname)
   add_unittest(MLIRUnitTests ${test_dirname} ${ARGN})
 endfunction()
 
 add_subdirectory(Analysis)
 add_subdirectory(Conversion)
 add_subdirectory(Dialect)
 add_subdirectory(Interfaces)
+add_subdirectory(Interpreter)
 add_subdirectory(IR)
 add_subdirectory(Parser)
 add_subdirectory(Pass)
 add_subdirectory(Support)
 add_subdirectory(Rewrite)
 add_subdirectory(TableGen)
 add_subdirectory(Transforms)
 
 # The native target may not be enabled when cross compiling.
 if(TARGET ${LLVM_NATIVE_ARCH})
   add_subdirectory(ExecutionEngine)
 endif()

mlir/unittests/IR/CMakeLists.txt

 add_mlir_unittest(MLIRIRTests
   AttributeTest.cpp
   DialectTest.cpp
   InterfaceAttachmentTest.cpp
   OperationSupportTest.cpp
   PatternMatchTest.cpp
   ShapedTypeTest.cpp
   SubElementInterfaceTest.cpp
 
   DEPENDS
   MLIRTestInterfaceIncGen
 )
 target_include_directories(MLIRIRTests PRIVATE "${MLIR_BINARY_DIR}/test/lib/Dialect/Test")
 target_link_libraries(MLIRIRTests
   PRIVATE
   MLIRIR
-  MLIRTestDialect)
+  MLIRTestDialect
+  MLIRInterpreter)

mlir/unittests/Interpreter/CMakeLists.txt

+add_subdirectory(Dialects)

mlir/unittests/Interpreter/Dialects/CMakeLists.txt

+add_mlir_unittest(MLIRInterpreterDialectTests
+  FuncInterpreterTest.cpp
+)
+
+target_link_libraries(MLIRInterpreterDialectTests
+  PRIVATE
+  MLIRFuncInterpreter
+  MLIRFuncDialect
+  MLIRInterpreter
+)

mlir/unittests/Interpreter/Dialects/FuncInterpreterTest.cpp

+#include "mlir/Interpreter/Dialects/FuncInterpreter.h"
+
+#include "mlir/Dialect/Func/IR/FuncOps.h"
+#include "mlir/Interpreter/Interpreter.h"
+
+#include <gtest/gtest.h>
+
+using namespace mlir;
+
+TEST(InterpreterTest, ReturnOp) {
+  MLIRContext context;
+  Interpreter interpreter(context);
+  interpreter.registerDialectInterpreter<FuncInterpreter>();
+
+  // Builds the test module.
+  OpBuilder builder(&context);
+
+  auto i32Type = builder.getI32Type();
+  auto funcType = builder.getFunctionType({i32Type, i32Type}, {i32Type});
+  auto funcOp =
+      func::FuncOp::create(builder.getUnknownLoc(), "main", funcType, {});
+
+  Block *block = funcOp.addEntryBlock();
+
+  builder.setInsertionPointToEnd(block);
+  builder.create<func::ReturnOp>(builder.getUnknownLoc(),
+                                 ValueRange({funcOp.getArgument(1)}));
+
+  OwningOpRef<mlir::ModuleOp> test_module =
+      ModuleOp::create(builder.getUnknownLoc());
+  test_module->push_back(funcOp);
+
+  // Test execution.
+  interpreter.setModule(*test_module);
+
+  SmallVector<EvalValue, 2> args = {
+      interpreter.createEvalValue(i32Type, llvm::makeArrayRef<int32_t>({-1})),
+      interpreter.createEvalValue(i32Type, llvm::makeArrayRef<int32_t>({42})),
+  };
+  EvalResult result = interpreter.execute("main", args);
+
+  ASSERT_EQ(EvalResultKind::ReturnValue, result.getKind());
+
+  ArrayRef<EvalValue> results = result.getValues();
+  ASSERT_EQ(1u, results.size());
+
+  EXPECT_NE(results[0], args[0]);
+  EXPECT_EQ(results[0], args[1]);
+  EXPECT_EQ(42, results[0].getData<int32_t>()[0]);
+}