[mlir][PDL] Add support for PDL bytecode and expose PDL support to OwningRewritePatternList

[rriddle]

Summary

PDL patterns are now supported via a new PDLPatternModule class. This class contains a ModuleOp with the pdl::PatternOp operations representing the patterns, as well as a collection of registered C++ functions for native constraints/creations/rewrites/etc. that may be invoked via the pdl patterns. Instances of this class are added to an OwningRewritePatternList in the same fashion as C++ RewritePatterns, i.e. via the insert method.

The PDL bytecode is an in-memory representation of the PDL interpreter dialect that can be efficiently interpreted/executed. The representation of the bytecode boils down to a code array(for opcodes/memory locations/etc) and a memory buffer(for storing attributes/operations/values/any other data necessary). The bytecode operations are effectively a 1-1 mapping to the PDLInterp dialect operations, with a few exceptions in cases where the in-memory representation of the bytecode can be more efficient than the MLIR representation. For example, a generic AreEqual bytecode op can be used to represent AreEqualOp, CheckAttributeOp, and CheckTypeOp.

The execution of the bytecode is split into two phases: matching and rewriting. When matching, all of the matched patterns are collected to avoid the overhead of re-running parts of the matcher. These matched patterns are then considered alongside the native C++ patterns, which rewrite immediately in-place via RewritePattern::matchAndRewrite, for the given root operation. When a PDL pattern is matched and has the highest benefit, it is passed back to the bytecode to execute its rewriter.

Depends On D89104

[rriddle]

Still got some things to tidy up, but good for initial review.

[rriddle]

ping

[jpienaar]

First scan, mostly looks good thanks!

mlir/include/mlir/IR/PatternMatch.h

253

And we need these enable_if_t's due to the union used here?

308

And this array matches the first array? In using an ArrayAttr, it means these are uniqued, is there a reason to have them uniqued vs an array of them?

312

This has the same comment start as above, does this need to be expanded to differentiate it?

321

Could we have these in alphabetical order?

406

PDL?

mlir/lib/Rewrite/ByteCode.cpp

1

Not needed in cpp file.

102

GetOperandN ? So the above are "inlined" cases for common get operand queries? Does this actually pay off executionally/size wise?

mlir/lib/Rewrite/ByteCode.h

79

This is interesting. So this is just a raw memory block?

102

Nit: it need not be fused does it?

[rriddle]

Resolve comments

mlir/include/mlir/IR/PatternMatch.h

253

Yes, given that we have to treat Value differently because of the nested unions.

308

It's more of what is a better interface to the user. They are always going to be in ArrayAttr form within PDL, so it is merely a question of is it better to pass in an ArrayRef(that is unwrapped from an ArrayAttr) or an ArrayAttr. I don't have a huge preference, but ArrayAttr has some nicer utilities for unwrapping the attributes.

mlir/lib/Rewrite/ByteCode.cpp

102

It helps a little bit in execution time, and more in the encoding given that it removes the need for two extra fields.

mlir/lib/Rewrite/ByteCode.h

79

Yeah. Given that everything is pointer based, we can just have one large block of opaque memory.

102

I used fused because it is an established thing that if you create a Fused loc with one location it just returns the location unfused. Would you prefer that I dropped "fused" here?

[rriddle]

Ping

[jpienaar]

Nice, a bit big change, but not easy to break up. I think it looks good in general, thanks!

mlir/include/mlir/IR/PatternMatch.h

13

Out of date now ;-)

mlir/lib/Rewrite/ByteCode.cpp

1051

How about adding the enum value into the debug message or just doing GetOperandX ?

1118

Add comment describing fusedLoc behavior with get below

1120

Mmm, this creates a sequence of uniqued fusedloc, even though you only care about the final one. Could this be avoided?

mlir/lib/Rewrite/ByteCode.h

102

Well I was also thinking of location directives we have in DRR (so yes dropping fused)

mlir/test/Rewrite/pdl-bytecode.mlir

29

Nit: could we have this be something easier to see? E.g., test.replaced_by_pattern? When I read it first I though success below just indicated something about the rewriter, not that it was the op created here

[rriddle]

Resolve comments

[rriddle]

Thanks for the review Jacques! Very appreciated. Should be much easier to iterate on PDL now.

[NathanielMcVicar]

This appears to still be failing on VS2017 after the latest GCC5 fix (although builder is having some trouble, so I'll confirm). http://lab.llvm.org:8011/#/builders/13/builds/2128

E:\build_slave\mlir-x64-windows-ninja\llvm-project\mlir\lib\Rewrite\ByteCode.cpp(532): error C2440: '<function-style-cast>': cannot convert from 'mlir::pdl_interp::BranchOp' to 'mlir::SuccessorRange'
E:\build_slave\mlir-x64-windows-ninja\llvm-project\mlir\lib\Rewrite\ByteCode.cpp(532): note: No constructor could take the source type, or constructor overload resolution was ambiguous
E:\build_slave\mlir-x64-windows-ninja\llvm-project\mlir\lib\Rewrite\ByteCode.cpp(640): error C2440: '<function-style-cast>': cannot convert from 'mlir::pdl_interp::RecordMatchOp' to 'mlir::SuccessorRange'
E:\build_slave\mlir-x64-windows-ninja\llvm-project\mlir\lib\Rewrite\ByteCode.cpp(640): note: No constructor could take the source type, or constructor overload resolution was ambiguous

[mehdi_amini]

It is also still failing on gcc5: https://buildkite.com/mlir/mlir-core/builds/9764#87fef35f-6121-4af8-8442-a42b10775b61

[rriddle]

Attempt #2 at fixing GCC5: 8affe88108a1d5f37303cb2128e0650e70ab1eae

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

let description = [{
     success, this operation branches to the true destination, otherwise the
     false destination is taken.
 
     Example:
 
     ```mlir
     // Apply `myConstraint` to the entities defined by `input`, `attr`, and
     // `op`.
-    pdl_interp.apply_constraint "myConstraint"[42, "abc", i32](%input, %attr, %op : !pdl.value, !pdl.attribute, !pdl.operation)
+    pdl_interp.apply_constraint "myConstraint"[42, "abc", i32](%input, %attr, %op : !pdl.value, !pdl.attribute, !pdl.operation) -> ^matchDest, ^failureDest
     ```
   }];
 
   let arguments = (ins StrAttr:$name,
                        Variadic<PDL_PositionalValue>:$args,
                        OptionalAttr<ArrayAttr>:$constParams);
   let assemblyFormat = [{
     $name ($constParams^)? `(` $args `:` type($args) `)` attr-dict `->`
def PDLInterp_CheckTypeOp
   let description = [{
     `pdl_interp.check_type` operations compare a type with a statically known
     type. On success, this operation branches to the true destination, otherwise
     the false destination is taken.
 
     Example:
 
     ```mlir
-    pdl_interp.check_type %type is 0 -> ^matchDest, ^failureDest
+    pdl_interp.check_type %type is i32 -> ^matchDest, ^failureDest
     ```
   }];
 
   let arguments = (ins PDL_Type:$value, TypeAttr:$type);
   let assemblyFormat = "$value `is` $type attr-dict `->` successors";
 }
 
 //===----------------------------------------------------------------------===//
 // pdl_interp::CreateAttributeOp
 //===----------------------------------------------------------------------===//
 
 def PDLInterp_CreateAttributeOp
     : PDLInterp_Op<"create_attribute", [NoSideEffect]> {
   let summary = "Create an interpreter handle to a constant `Attribute`";
   let description = [{
     `pdl_interp.create_attribute` operations generate a handle within the
     interpreter for a specific constant attribute value.
 
     Example:
 
     ```mlir
-    pdl_interp.create_attribute 10 : i64
+    %attr = pdl_interp.create_attribute 10 : i64
     ```
   }];
 
   let arguments = (ins AnyAttr:$value);
   let results = (outs PDL_Attribute:$attribute);
   let assemblyFormat = "$value attr-dict";
 
   let builders = [
let description = [{
     been registered externally with the consumer of PDL, to create an
     `Attribute`, `Operation`, `Type`, or `Value`. The native function must
     produce a value of the specified return type, and may accept any number of
     positional arguments and constant attribute parameters.
 
     Example:
 
     ```mlir
-    %ret = pdl_interp.create_native "myNativeFunc"[42, "gt"](%arg0, %arg1) : !pdl.attribute
+    %ret = pdl_interp.create_native "myNativeFunc"[42, "gt"](%arg0, %arg1 : !pdl.value, !pdl.value) : !pdl.attribute
     ```
   }];
 
   let arguments = (ins StrAttr:$name,
                        Variadic<PDL_PositionalValue>:$args,
                        OptionalAttr<ArrayAttr>:$constParams);
   let results = (outs PDL_PositionalValue:$result);
   let assemblyFormat = [{
let description = [{
     `pdl_interp.switch_attribute` operations compare the value of a given
     attribute with a set of constant attributes. If the value matches one of the
     provided case values the destination for that case value is taken, otherwise
     the default destination is taken.
 
     Example:
 
     ```mlir
-    pdl_interp.switch_attribute %attr to [10, true] -> ^10Dest, ^trueDest, ^defaultDest
+    pdl_interp.switch_attribute %attr to [10, true](^10Dest, ^trueDest) -> ^defaultDest
     ```
   }];
   let arguments = (ins PDL_Attribute:$attribute, ArrayAttr:$caseValues);
   let assemblyFormat = [{
     $attribute `to` $caseValues `(` $cases `)` attr-dict `->` $defaultDest
   }];
 
   let builders = [
let description = [{
     `pdl_interp.switch_operation_name` operations compare the name of a given
     operation with a set of known names. If the value matches one of the
     provided case values the destination for that case value is taken, otherwise
     the default destination is taken.
 
     Example:
 
     ```mlir
-    pdl_interp.switch_operation_name of %op to ["foo.op", "bar.op"] -> ^fooDest, ^barDest, ^defaultDest
+    pdl_interp.switch_operation_name of %op to ["foo.op", "bar.op"](^fooDest, ^barDest) -> ^defaultDest
     ```
   }];
 
   let arguments = (ins PDL_Operation:$operation,
                        StrArrayAttr:$caseValues);
   let assemblyFormat = [{
     `of` $operation `to` $caseValues `(` $cases `)` attr-dict `->` $defaultDest
   }];
let description = [{
     `pdl_interp.switch_result_count` operations compare the result count of a
     given operation with a set of potential counts. If the value matches one of
     the provided case values the destination for that case value is taken,
     otherwise the default destination is taken.
 
     Example:
 
     ```mlir
-    pdl_interp.switch_result_count of %op to [0, 2] -> ^0Dest, ^2Dest, ^defaultDest
+    pdl_interp.switch_result_count of %op to [0, 2](^0Dest, ^2Dest) -> ^defaultDest
     ```
   }];
 
   let arguments = (ins PDL_Operation:$operation, I32ElementsAttr:$caseValues);
   let assemblyFormat = [{
     `of` $operation `to` $caseValues `(` $cases `)` attr-dict `->` $defaultDest
   }];
 

mlir/include/mlir/IR/BlockSupport.h

 //===----------------------------------------------------------------------===//
 
 /// This class implements the successor iterators for Block.
 class SuccessorRange final
     : public llvm::detail::indexed_accessor_range_base<
           SuccessorRange, BlockOperand *, Block *, Block *, Block *> {
 public:
   using RangeBaseT::RangeBaseT;
+  SuccessorRange();
   SuccessorRange(Block *block);
   SuccessorRange(Operation *term);
 
 private:
   /// See `llvm::detail::indexed_accessor_range_base` for details.
   static BlockOperand *offset_base(BlockOperand *object, ptrdiff_t index) {
     return object + index;
   }

mlir/include/mlir/IR/Operation.h

public:
   const AbstractOperation *getAbstractOperation() {
     return getName().getAbstractOperation();
   }
 
   /// Returns true if this operation has a registered operation description,
   /// otherwise false.
   bool isRegistered() { return getAbstractOperation(); }
 
+  /// Remove the operation from its parent block, but don't delete it.
+  void removeFromParent();
+
   /// Remove this operation from its parent block and delete it.
   void erase();
 
   /// Create a deep copy of this operation, remapping any operands that use
   /// values outside of the operation using the map that is provided (leaving
   /// them alone if no entry is present).  Replaces references to cloned
   /// sub-operations to the corresponding operation that is copied, and adds
   /// those mappings to the map.

mlir/include/mlir/IR/OperationSupport.h

public:
   const AbstractOperation *getAbstractOperation() const;
 
   void print(raw_ostream &os) const;
   void dump() const;
 
   void *getAsOpaquePointer() const {
     return static_cast<void *>(representation.getOpaqueValue());
   }
-  static OperationName getFromOpaquePointer(void *pointer);
+  static OperationName getFromOpaquePointer(const void *pointer);
 
 private:
   RepresentationUnion representation;
   OperationName(RepresentationUnion representation)
       : representation(representation) {}
 };
 
 inline raw_ostream &operator<<(raw_ostream &os, OperationName identifier) {

mlir/include/mlir/IR/PatternMatch.h

 //===- PatternMatch.h - PatternMatcher classes -------==---------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_PATTERNMATCHER_H
 #define MLIR_PATTERNMATCHER_H
 
 #include "mlir/IR/Builders.h"
+#include "mlir/IR/Module.h"
 
 namespace mlir {
 
 class PatternRewriter;
 
 //===----------------------------------------------------------------------===//
 // PatternBenefit class
 //===----------------------------------------------------------------------===//
if (succeeded(match(op))) {
       rewrite(op, rewriter);
       return success();
     }
     return failure();
   }
 };
 
 //===----------------------------------------------------------------------===//
+// PDLPatternModule
+//===----------------------------------------------------------------------===//
+
+//===----------------------------------------------------------------------===//
+// PDLValue
+
+/// Storage type of byte-code interpreter values. These are passed to constraint
+/// functions as arguments.
+class PDLValue {
+  /// The internal implementation type when the value is an Attribute,
+  /// Operation*, or Type. See `impl` below for more details.
+  using AttrOpTypeImplT = llvm::PointerUnion<Attribute, Operation *, Type>;
+
+public:
+  PDLValue(const PDLValue &other) : impl(other.impl) {}
+  PDLValue(std::nullptr_t = nullptr) : impl() {}
+  PDLValue(Attribute value) : impl(value) {}
+  PDLValue(Operation *value) : impl(value) {}
+  PDLValue(Type value) : impl(value) {}
+  PDLValue(Value value) : impl(value) {}
+
+  /// Returns true if the type of the held value is `T`.
+  template <typename T>
+  std::enable_if_t<std::is_same<T, Value>::value, bool> isa() const {
+    return impl.is<Value>();
+  }
+  template <typename T>
+  std::enable_if_t<!std::is_same<T, Value>::value, bool> isa() const {
+    auto attrOpTypeImpl = impl.dyn_cast<AttrOpTypeImplT>();
+    return attrOpTypeImpl && attrOpTypeImpl.is<T>();
+  }
+
+  /// Attempt to dynamically cast this value to type `T`, returns null if this
+  /// value is not an instance of `T`.
+  template <typename T>
+  std::enable_if_t<std::is_same<T, Value>::value, T> dyn_cast() const {
+    return impl.dyn_cast<T>();
+  }
+  template <typename T>
+  std::enable_if_t<!std::is_same<T, Value>::value, T> dyn_cast() const {
+    auto attrOpTypeImpl = impl.dyn_cast<AttrOpTypeImplT>();
+    return attrOpTypeImpl && attrOpTypeImpl.dyn_cast<T>();
+  }
+
+  /// Cast this value to type `T`, asserts if this value is not an instance of
+  /// `T`.
+  template <typename T>
+  std::enable_if_t<std::is_same<T, Value>::value, T> cast() const {
+    return impl.get<T>();
+  }
+  template <typename T>
+  std::enable_if_t<!std::is_same<T, Value>::value, T> cast() const {
+    return impl.get<AttrOpTypeImplT>().get<T>();
+  }
+
+  /// Get an opaque pointer to the value.
+  void *getAsOpaquePointer() { return impl.getOpaqueValue(); }
+
+  /// Print this value to the provided output stream.
+  void print(raw_ostream &os);
+
+private:
+  /// The internal opaque representation of a PDLValue. We use a nested
+  /// PointerUnion structure here because `Value` only has 1 low bit
+  /// available, where as the remaining types all have 3.
+  llvm::PointerUnion<AttrOpTypeImplT, Value> impl;
+};
+
+inline raw_ostream &operator<<(raw_ostream &os, PDLValue value) {
+  value.print(os);
+  return os;
+}
+
+//===----------------------------------------------------------------------===//
+// PDLPatternModule
+
+/// A generic PDL pattern constraint function. This function applies a
+/// constraint to a given set of opaque PDLValue entities. The second parameter
+/// is a set of constant value parameters specified in Attribute form. Returns
+/// success if the constraint successfully held, failure otherwise.
+using PDLConstraintFunction = std::function<LogicalResult(
+    ArrayRef<PDLValue>, ArrayAttr, PatternRewriter &)>;
+/// A generic PDL pattern constraint function. This function applies a
+/// constraint to a given opaque PDLValue entity. The second parameter is a set
+/// of constant value parameters specified in Attribute form. Returns success if
+/// the constraint successfully held, failure otherwise.
+using PDLSingleEntityConstraintFunction =
+    std::function<LogicalResult(PDLValue, ArrayAttr, PatternRewriter &)>;
+/// A native PDL creation function. This function creates a new PDLValue given
+/// a set of existing PDL values, a set of constant parameters specified in
+/// Attribute form, and a PatternRewriter. Returns the newly created PDLValue.
+using PDLCreateFunction =
+    std::function<PDLValue(ArrayRef<PDLValue>, ArrayAttr, PatternRewriter &)>;
+/// A native PDL rewrite function. This function rewrites the given root
+/// operation using the provided PatternRewriter. This method is only invoked
+/// when the corresponding match was successful.
+using PDLRewriteFunction = std::function<void(Operation *, ArrayRef<PDLValue>,
+                                              ArrayAttr, PatternRewriter &)>;
+
+/// This class contains all of the necessary data for a set of PDL patterns, or
+/// pattern rewrites specified in the form of the PDL dialect. This PDL module
+/// contained by this pattern may contain any number of `pdl.pattern`
+/// operations.
+class PDLPatternModule {
+public:
+  PDLPatternModule() = default;
+
+  /// Construct a PDL pattern with the given module.
+  PDLPatternModule(OwningModuleRef pdlModule)
+      : pdlModule(std::move(pdlModule)) {}
+
+  /// Merge the state in `other` into this pattern module.
+  void mergeIn(PDLPatternModule &&other);
+
+  /// Return the internal PDL module of this pattern.
+  ModuleOp getModule() { return pdlModule.get(); }
+
+  //===--------------------------------------------------------------------===//
+  // Function Registry
+
+  /// Register a constraint function.
+  void registerConstraintFunction(StringRef name,
+                                  PDLConstraintFunction constraintFn);
+  /// Register a single entity constraint function.
+  template <typename SingleEntityFn>
+  std::enable_if_t<!llvm::is_invocable<SingleEntityFn, ArrayRef<PDLValue>,
+                                       ArrayAttr, PatternRewriter &>::value>
+  registerConstraintFunction(StringRef name, SingleEntityFn &&constraintFn) {
+    registerConstraintFunction(name, [=](ArrayRef<PDLValue> values,
+                                         ArrayAttr constantParams,
+                                         PatternRewriter &rewriter) {
+      assert(values.size() == 1 && "expected values to have a single entity");
+      return constraintFn(values[0], constantParams, rewriter);
+    });
+  }
+
+  /// Register a creation function.
+  void registerCreateFunction(StringRef name, PDLCreateFunction createFn);
+
+  /// Register a rewrite function.
+  void registerRewriteFunction(StringRef name, PDLRewriteFunction rewriteFn);
+
+  /// Return the set of the registered constraint functions.
+  const llvm::StringMap<PDLConstraintFunction> &getConstraintFunctions() const {
+    return constraintFunctions;
+  }
+  llvm::StringMap<PDLConstraintFunction> takeConstraintFunctions() {
+    return constraintFunctions;
+  }
+  /// Return the set of the registered create functions.
+  const llvm::StringMap<PDLCreateFunction> &getCreateFunctions() const {
+    return createFunctions;
+  }
+  llvm::StringMap<PDLCreateFunction> takeCreateFunctions() {
+    return createFunctions;
+  }
+  /// Return the set of the registered rewrite functions.
+  const llvm::StringMap<PDLRewriteFunction> &getRewriteFunctions() const {
+    return rewriteFunctions;
+  }
+  llvm::StringMap<PDLRewriteFunction> takeRewriteFunctions() {
+    return rewriteFunctions;
+  }
+
+  /// Clear out the patterns and functions within this module.
+  void clear() {
+    pdlModule = nullptr;
+    constraintFunctions.clear();
+    createFunctions.clear();
+    rewriteFunctions.clear();
+  }
+
+private:
+  /// The module containing the `pdl.pattern` operations.
+  OwningModuleRef pdlModule;
+
+  /// The external functions referenced from within the pdl module.
+  llvm::StringMap<PDLConstraintFunction> constraintFunctions;
+  llvm::StringMap<PDLCreateFunction> createFunctions;
+  llvm::StringMap<PDLRewriteFunction> rewriteFunctions;
+};
+
+//===----------------------------------------------------------------------===//
 // PatternRewriter
 //===----------------------------------------------------------------------===//
 
 /// This class coordinates the application of a pattern to the current function,
 /// providing a way to create operations and keep track of what gets deleted.
 ///
 /// These class serves two purposes:
 ///  1) it is the interface that patterns interact with to make mutations to the
private:
   void replaceOpWithResultsOfAnotherOp(Operation *op, Operation *newOp);
 };
 
 //===----------------------------------------------------------------------===//
 // OwningRewritePatternList
 //===----------------------------------------------------------------------===//
 
 class OwningRewritePatternList {
-  using PatternListT = std::vector<std::unique_ptr<RewritePattern>>;
+  using NativePatternListT = std::vector<std::unique_ptr<RewritePattern>>;
 
 public:
   OwningRewritePatternList() = default;
 
-  /// Construct a OwningRewritePatternList populated with the pattern `t` of
-  /// type `T`.
-  template <typename T>
-  OwningRewritePatternList(T &&t) {
-    patterns.emplace_back(std::make_unique<T>(std::forward<T>(t)));
-  }
-
-  PatternListT::iterator begin() { return patterns.begin(); }
-  PatternListT::iterator end() { return patterns.end(); }
-  PatternListT::const_iterator begin() const { return patterns.begin(); }
-  PatternListT::const_iterator end() const { return patterns.end(); }
-  PatternListT::size_type size() const { return patterns.size(); }
-  void clear() { patterns.clear(); }
-
-  /// Take ownership of the patterns held by this list.
-  std::vector<std::unique_ptr<RewritePattern>> takePatterns() {
-    return std::move(patterns);
+  /// Construct a OwningRewritePatternList populated with the given pattern.
+  OwningRewritePatternList(std::unique_ptr<RewritePattern> pattern) {
+    nativePatterns.emplace_back(std::move(pattern));
+  }
+  OwningRewritePatternList(PDLPatternModule &&pattern)
+      : pdlPatterns(std::move(pattern)) {}
+
+  /// Return the native patterns held in this list.
+  NativePatternListT &getNativePatterns() { return nativePatterns; }
+
+  /// Return the PDL patterns held in this list.
+  PDLPatternModule &getPDLPatterns() { return pdlPatterns; }
+
+  /// Clear out all of the held patterns in this list.
+  void clear() {
+    nativePatterns.clear();
+    pdlPatterns.clear();
   }
 
   //===--------------------------------------------------------------------===//
   // Pattern Insertion
   //===--------------------------------------------------------------------===//
 
   /// Add an instance of each of the pattern types 'Ts' to the pattern list with
   /// the given arguments. Return a reference to `this` for chaining insertions.
   /// Note: ConstructorArg is necessary here to separate the two variadic lists.
   template <typename... Ts, typename ConstructorArg,
             typename... ConstructorArgs,
             typename = std::enable_if_t<sizeof...(Ts) != 0>>
   OwningRewritePatternList &insert(ConstructorArg &&arg,
-                                   ConstructorArgs &&... args) {
+                                   ConstructorArgs &&...args) {
     // The following expands a call to emplace_back for each of the pattern
     // types 'Ts'. This magic is necessary due to a limitation in the places
     // that a parameter pack can be expanded in c++11.
     // FIXME: In c++17 this can be simplified by using 'fold expressions'.
-    (void)std::initializer_list<int>{
-        0, (patterns.emplace_back(std::make_unique<Ts>(arg, args...)), 0)...};
+    (void)std::initializer_list<int>{0, (insertImpl<Ts>(arg, args...), 0)...};
     return *this;
   }
 
   /// Add an instance of each of the pattern types 'Ts'. Return a reference to
   /// `this` for chaining insertions.
   template <typename... Ts> OwningRewritePatternList &insert() {
-    (void)std::initializer_list<int>{
-        0, (patterns.emplace_back(std::make_unique<Ts>()), 0)...};
+    (void)std::initializer_list<int>{0, (insertImpl<Ts>(), 0)...};
     return *this;
   }
 
-  /// Add the given pattern to the pattern list.
-  void insert(std::unique_ptr<RewritePattern> pattern) {
-    patterns.emplace_back(std::move(pattern));
+  /// Add the given native pattern to the pattern list. Return a reference to
+  /// `this` for chaining insertions.
+  OwningRewritePatternList &insert(std::unique_ptr<RewritePattern> pattern) {
+    nativePatterns.emplace_back(std::move(pattern));
+    return *this;
+  }
+
+  /// Add the given pdl pattern to the pattern list. Return a reference to
+  /// `this` for chaining insertions.
+  OwningRewritePatternList &insert(PDLPatternModule &&pattern) {
+    pdlPatterns.mergeIn(std::move(pattern));
+    return *this;
   }
 
 private:
-  PatternListT patterns;
+  /// Add an instance of the pattern type 'T'. Return a reference to `this` for
+  /// chaining insertions.
+  template <typename T, typename... Args>
+  std::enable_if_t<std::is_base_of<RewritePattern, T>::value>
+  insertImpl(Args &&...args) {
+    nativePatterns.emplace_back(
+        std::make_unique<T>(std::forward<Args>(args)...));
+  }
+  template <typename T, typename... Args>
+  std::enable_if_t<std::is_base_of<PDLPatternModule, T>::value>
+  insertImpl(Args &&...args) {
+    pdlPatterns.mergeIn(T(std::forward<Args>(args)...));
+  }
+
+  NativePatternListT nativePatterns;
+  PDLPatternModule pdlPatterns;
 };
 
 } // end namespace mlir
 
 #endif // MLIR_PATTERN_MATCH_H

mlir/include/mlir/IR/StorageUniquerSupport.h

public:
   template <typename LocationT, typename... Args>
   static ConcreteT getChecked(LocationT loc, Args... args) {
     // If the construction invariants fail then we return a null attribute.
     if (failed(ConcreteT::verifyConstructionInvariants(loc, args...)))
       return ConcreteT();
     return UniquerT::template get<ConcreteT>(loc.getContext(), args...);
   }
 
+  /// Get an instance of the concrete type from a void pointer.
+  static ConcreteT getFromOpaquePointer(const void *ptr) {
+    return ptr ? BaseT::getFromOpaquePointer(ptr).template cast<ConcreteT>()
+               : nullptr;
+  }
+
 protected:
   /// Mutate the current storage instance. This will not change the unique key.
   /// The arguments are forwarded to 'ConcreteT::mutate'.
   template <typename... Args> LogicalResult mutate(Args &&...args) {
     return UniquerT::template mutate<ConcreteT>(this->getContext(), getImpl(),
                                                 std::forward<Args>(args)...);
   }
 

mlir/include/mlir/Rewrite/FrozenRewritePatternList.h

 //===- FrozenRewritePatternList.h - FrozenRewritePatternList ----*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_REWRITE_FROZENREWRITEPATTERNLIST_H
 #define MLIR_REWRITE_FROZENREWRITEPATTERNLIST_H
 
 #include "mlir/IR/PatternMatch.h"
 
 namespace mlir {
+namespace detail {
+class PDLByteCode;
+} // end namespace detail
+
 /// This class represents a frozen set of patterns that can be processed by a
 /// pattern applicator. This class is designed to enable caching pattern lists
 /// such that they need not be continuously recomputed.
 class FrozenRewritePatternList {
-  using PatternListT = std::vector<std::unique_ptr<RewritePattern>>;
+  using NativePatternListT = std::vector<std::unique_ptr<RewritePattern>>;
 
 public:
   /// Freeze the patterns held in `patterns`, and take ownership.
   FrozenRewritePatternList(OwningRewritePatternList &&patterns);
+  FrozenRewritePatternList(FrozenRewritePatternList &&patterns);
+  ~FrozenRewritePatternList();
+
+  /// Return the native patterns held by this list.
+  iterator_range<llvm::pointee_iterator<NativePatternListT::const_iterator>>
+  getNativePatterns() const {
+    return llvm::make_pointee_range(nativePatterns);
+  }
 
-  /// Return the patterns held by this list.
-  iterator_range<llvm::pointee_iterator<PatternListT::const_iterator>>
-  getPatterns() const {
-    return llvm::make_pointee_range(patterns);
+  /// Return the compiled PDL bytecode held by this list. Returns null if
+  /// there are no PDL patterns within the list.
+  const detail::PDLByteCode *getPDLByteCode() const {
+    return pdlByteCode.get();
   }
 
 private:
-  /// The patterns held by this list.
-  std::vector<std::unique_ptr<RewritePattern>> patterns;
+  /// The set of.
+  std::vector<std::unique_ptr<RewritePattern>> nativePatterns;
+
+  /// The bytecode containing the compiled PDL patterns.
+  std::unique_ptr<detail::PDLByteCode> pdlByteCode;
 };
 
 } // end namespace mlir
 
 #endif // MLIR_REWRITE_FROZENREWRITEPATTERNLIST_H

mlir/include/mlir/Rewrite/PatternApplicator.h

 #ifndef MLIR_REWRITE_PATTERNAPPLICATOR_H
 #define MLIR_REWRITE_PATTERNAPPLICATOR_H
 
 #include "mlir/Rewrite/FrozenRewritePatternList.h"
 
 namespace mlir {
 class PatternRewriter;
 
+namespace detail {
+class PDLByteCodeMutableState;
+} // end namespace detail
+
 /// This class manages the application of a group of rewrite patterns, with a
 /// user-provided cost model.
 class PatternApplicator {
 public:
   /// The cost model dynamically assigns a PatternBenefit to a particular
   /// pattern. Users can query contained patterns and pass analysis results to
   /// applyCostModel. Patterns to be discarded should have a benefit of
   /// `impossibleToMatch`.
   using CostModel = function_ref<PatternBenefit(const Pattern &)>;
 
-  explicit PatternApplicator(const FrozenRewritePatternList &frozenPatternList)
-      : frozenPatternList(frozenPatternList) {}
+  explicit PatternApplicator(const FrozenRewritePatternList &frozenPatternList);
+  ~PatternApplicator();
 
   /// Attempt to match and rewrite the given op with any pattern, allowing a
   /// predicate to decide if a pattern can be applied or not, and hooks for if
   /// the pattern match was a success or failure.
   ///
   /// canApply:  called before each match and rewrite attempt; return false to
   ///            skip pattern.
   /// onFailure: called when a pattern fails to match to perform cleanup.
public:
   void applyDefaultCostModel() {
     applyCostModel([](const Pattern &pattern) { return pattern.getBenefit(); });
   }
 
   /// Walk all of the patterns within the applicator.
   void walkAllPatterns(function_ref<void(const Pattern &)> walk);
 
 private:
-  /// Attempt to match and rewrite the given op with the given pattern, allowing
-  /// a predicate to decide if a pattern can be applied or not, and hooks for if
-  /// the pattern match was a success or failure.
-  LogicalResult
-  matchAndRewrite(Operation *op, const RewritePattern &pattern,
-                  PatternRewriter &rewriter,
-                  function_ref<bool(const Pattern &)> canApply,
-                  function_ref<void(const Pattern &)> onFailure,
-                  function_ref<LogicalResult(const Pattern &)> onSuccess);
-
   /// The list that owns the patterns used within this applicator.
   const FrozenRewritePatternList &frozenPatternList;
   /// The set of patterns to match for each operation, stable sorted by benefit.
   DenseMap<OperationName, SmallVector<const RewritePattern *, 2>> patterns;
   /// The set of patterns that may match against any operation type, stable
   /// sorted by benefit.
   SmallVector<const RewritePattern *, 1> anyOpPatterns;
+  /// The mutable state used during execution of the PDL bytecode.
+  std::unique_ptr<detail::PDLByteCodeMutableState> mutableByteCodeState;
 };
 
 } // end namespace mlir
 
 #endif // MLIR_REWRITE_PATTERNAPPLICATOR_H

mlir/lib/IR/Block.cpp

 unsigned PredecessorIterator::getSuccessorIndex() const {
   return I->getOperandNumber();
 }
 
 //===----------------------------------------------------------------------===//
 // SuccessorRange
 //===----------------------------------------------------------------------===//
 
-SuccessorRange::SuccessorRange(Block *block) : SuccessorRange(nullptr, 0) {
+SuccessorRange::SuccessorRange() : SuccessorRange(nullptr, 0) {}
+
+SuccessorRange::SuccessorRange(Block *block) : SuccessorRange() {
   if (Operation *term = block->getTerminator())
     if ((count = term->getNumSuccessors()))
       base = term->getBlockOperands().data();
 }
 
-SuccessorRange::SuccessorRange(Operation *term) : SuccessorRange(nullptr, 0) {
+SuccessorRange::SuccessorRange(Operation *term) : SuccessorRange() {
   if ((count = term->getNumSuccessors()))
     base = term->getBlockOperands().data();
 }
 
 //===----------------------------------------------------------------------===//
 // BlockRange
 //===----------------------------------------------------------------------===//
 

mlir/lib/IR/Operation.cpp

if (auto *op = representation.dyn_cast<const AbstractOperation *>())
     return op->name;
   return representation.get<Identifier>();
 }
 
 const AbstractOperation *OperationName::getAbstractOperation() const {
   return representation.dyn_cast<const AbstractOperation *>();
 }
 
-OperationName OperationName::getFromOpaquePointer(void *pointer) {
-  return OperationName(RepresentationUnion::getFromOpaqueValue(pointer));
+OperationName OperationName::getFromOpaquePointer(const void *pointer) {
+  return OperationName(
+      RepresentationUnion::getFromOpaqueValue(const_cast<void *>(pointer)));
 }
 
 //===----------------------------------------------------------------------===//
 // Operation
 //===----------------------------------------------------------------------===//
 
 /// Create a new Operation with the specific fields.
 Operation *Operation::create(Location location, OperationName name,
void llvm::ilist_traits<::mlir::Operation>::transferNodesFromList(
   if (curParent == otherList.getContainingBlock())
     return;
 
   // Update the 'block' member of each operation.
   for (; first != last; ++first)
     first->block = curParent;
 }
 
+/// Remove the operation from its parent block, but don't delete it.
+void Operation::removeFromParent() {
+  if (Block *parent = getBlock())
+    parent->getOperations().remove(this);
+}
+
 /// Remove this operation (and its descendants) from its Block and delete
 /// all of them.
 void Operation::erase() {
   if (auto *parent = getBlock())
     parent->getOperations().erase(this);
   else
     destroy();
 }

mlir/lib/IR/PatternMatch.cpp

 LogicalResult RewritePattern::match(Operation *op) const {
   llvm_unreachable("need to implement either match or matchAndRewrite!");
 }
 
 /// Out-of-line vtable anchor.
 void RewritePattern::anchor() {}
 
 //===----------------------------------------------------------------------===//
+// PDLValue
+//===----------------------------------------------------------------------===//
+
+void PDLValue::print(raw_ostream &os) {
+  if (!impl) {
+    os << "<Null-PDLValue>";
+    return;
+  }
+  if (Value val = impl.dyn_cast<Value>()) {
+    os << val;
+    return;
+  }
+  AttrOpTypeImplT aotImpl = impl.get<AttrOpTypeImplT>();
+  if (Attribute attr = aotImpl.dyn_cast<Attribute>())
+    os << attr;
+  else if (Operation *op = aotImpl.dyn_cast<Operation *>())
+    os << *op;
+  else
+    os << aotImpl.get<Type>();
+}
+
+//===----------------------------------------------------------------------===//
+// PDLPatternModule
+//===----------------------------------------------------------------------===//
+
+void PDLPatternModule::mergeIn(PDLPatternModule &&other) {
+  // Ignore the other module if it has no patterns.
+  if (!other.pdlModule)
+    return;
+  // Steal the other state if we have no patterns.
+  if (!pdlModule) {
+    constraintFunctions = std::move(other.constraintFunctions);
+    createFunctions = std::move(other.createFunctions);
+    rewriteFunctions = std::move(other.rewriteFunctions);
+    pdlModule = std::move(other.pdlModule);
+    return;
+  }
+  // Steal the functions of the other module.
+  for (auto &it : constraintFunctions)
+    registerConstraintFunction(it.first(), std::move(it.second));
+  for (auto &it : createFunctions)
+    registerCreateFunction(it.first(), std::move(it.second));
+  for (auto &it : rewriteFunctions)
+    registerRewriteFunction(it.first(), std::move(it.second));
+
+  // Merge the pattern operations from the other module into this one.
+  Block *block = pdlModule->getBody();
+  block->getTerminator()->erase();
+  block->getOperations().splice(block->end(),
+                                other.pdlModule->getBody()->getOperations());
+}
+
+//===----------------------------------------------------------------------===//
+// Function Registry
+
+void PDLPatternModule::registerConstraintFunction(
+    StringRef name, PDLConstraintFunction constraintFn) {
+  auto it = constraintFunctions.try_emplace(name, std::move(constraintFn));
+  (void)it;
+  assert(it.second &&
+         "constraint with the given name has already been registered");
+}
+void PDLPatternModule::registerCreateFunction(StringRef name,
+                                              PDLCreateFunction createFn) {
+  auto it = createFunctions.try_emplace(name, std::move(createFn));
+  (void)it;
+  assert(it.second && "native create function with the given name has "
+                      "already been registered");
+}
+void PDLPatternModule::registerRewriteFunction(StringRef name,
+                                               PDLRewriteFunction rewriteFn) {
+  auto it = rewriteFunctions.try_emplace(name, std::move(rewriteFn));
+  (void)it;
+  assert(it.second && "native rewrite function with the given name has "
+                      "already been registered");
+}
+
+//===----------------------------------------------------------------------===//
 // PatternRewriter
 //===----------------------------------------------------------------------===//
 
 PatternRewriter::~PatternRewriter() {
   // Out of line to provide a vtable anchor for the class.
 }
 
 /// This method performs the final replacement for a pattern, where the

mlir/lib/Rewrite/ByteCode.h

+//===- ByteCode.h - Pattern byte-code 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 declares a byte-code and interpreter for pattern rewrites in MLIR.
+// The byte-code is constructed from the PDL Interpreter dialect.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_REWRITE_BYTECODE_H_
+#define MLIR_REWRITE_BYTECODE_H_
+
+#include "mlir/IR/PatternMatch.h"
+
+namespace mlir {
+namespace pdl_interp {
+class RecordMatchOp;
+} // end namespace pdl_interp
+
+namespace detail {
+class PDLByteCode;
+
+/// Use generic bytecode types. ByteCodeField refers to the actual bytecode
+/// entries (set to uint8_t for "byte" bytecode). ByteCodeAddr refers to size of
+/// indices into the bytecode. Correctness is checked with static asserts.
+using ByteCodeField = uint16_t;
+using ByteCodeAddr = uint32_t;
+
+//===----------------------------------------------------------------------===//
+// PDLByteCodePattern
+//===----------------------------------------------------------------------===//
+
+/// All of the data pertaining to a specific pattern within the bytecode.
+class PDLByteCodePattern : public Pattern {
+public:
+  static PDLByteCodePattern create(pdl_interp::RecordMatchOp matchOp,
+                                   ByteCodeAddr rewriterAddr);
+
+  /// Return the bytecode address of the rewriter for this pattern.
+  ByteCodeAddr getRewriterAddr() const { return rewriterAddr; }
+
+private:
+  template <typename... Args>
+  PDLByteCodePattern(ByteCodeAddr rewriterAddr, Args &&...patternArgs)
+      : Pattern(std::forward<Args>(patternArgs)...),
+        rewriterAddr(rewriterAddr) {}
+
+  /// The address of the rewriter for this pattern.
+  ByteCodeAddr rewriterAddr;
+};
+
+//===----------------------------------------------------------------------===//
+// PDLByteCodeMutableState
+//===----------------------------------------------------------------------===//
+
+/// This class contains the mutable state of a bytecode instance. This allows
+/// for a bytecode instance to be cached and reused across various different
+/// threads/drivers.
+class PDLByteCodeMutableState {
+public:
+  /// Initialize the state from a bytecode instance.
+  void initialize(PDLByteCode &bytecode);
+
+  /// Set the new benefit for a bytecode pattern. The `patternIndex` corresponds
+  /// to the position of the pattern within the range returned by
+  /// `PDLByteCode::getPatterns`.
+  void updatePatternBenefit(unsigned patternIndex, PatternBenefit benefit);
+
+private:
+  /// Allow access to data fields.
+  friend class PDLByteCode;
+
+  /// The mutable block of memory used during the matching and rewriting phases
+  /// of the bytecode.
+  std::vector<const void *> memory;
+
+  /// The up-to-date benefits of the patterns held by the bytecode. The order
+  /// of this array corresponds 1-1 with the array of patterns in `PDLByteCode`.
+  std::vector<PatternBenefit> currentPatternBenefits;
+};
+
+//===----------------------------------------------------------------------===//
+// PDLByteCode
+//===----------------------------------------------------------------------===//
+
+/// The bytecode class is also the interpreter. Contains the bytecode itself,
+/// the static info, addresses of the rewriter functions, the interpreter
+/// memory buffer, and the execution context.
+class PDLByteCode {
+public:
+  /// Each successful match returns a MatchResult, which contains information
+  /// necessary to execute the rewriter and indicates the originating pattern.
+  struct MatchResult {
+    MatchResult(Location loc, const PDLByteCodePattern &pattern,
+                PatternBenefit benefit)
+        : location(loc), pattern(&pattern), benefit(benefit) {}
+
+    /// The fused location of operations to be replaced.
+    Location location;
+    /// Memory values defined in the matcher that are passed to the rewriter.
+    SmallVector<const void *, 4> values;
+    /// The originating pattern that was matched. This is always non-null, but
+    /// represented with a pointer to allow for assignment.
+    const PDLByteCodePattern *pattern;
+    /// The current benefit of the pattern that was matched.
+    PatternBenefit benefit;
+  };
+
+  /// Create a ByteCode instance from the given module containing operations in
+  /// the PDL interpreter dialect.
+  PDLByteCode(ModuleOp module,
+              llvm::StringMap<PDLConstraintFunction> constraintFns,
+              llvm::StringMap<PDLCreateFunction> createFns,
+              llvm::StringMap<PDLRewriteFunction> rewriteFns);
+
+  /// Return the patterns held by the bytecode.
+  ArrayRef<PDLByteCodePattern> getPatterns() const { return patterns; }
+
+  /// Initialize the given state such that it can be used to execute the current
+  /// bytecode.
+  void initializeMutableState(PDLByteCodeMutableState &state) const;
+
+  /// Run the pattern matcher on the given root operation, collecting the
+  /// matched patterns in `matches`.
+  void match(Operation *op, PatternRewriter &rewriter,
+             SmallVectorImpl<MatchResult> &matches,
+             PDLByteCodeMutableState &state) const;
+
+  /// Run the rewriter of the given pattern that was previously matched in
+  /// `match`.
+  void rewrite(PatternRewriter &rewriter, const MatchResult &match,
+               PDLByteCodeMutableState &state) const;
+
+private:
+  /// Execute the given byte code starting at the provided instruction `inst`.
+  /// `matches` is an optional field provided when this function is executed in
+  /// a matching context.
+  void executeByteCode(const ByteCodeField *inst, PatternRewriter &rewriter,
+                       PDLByteCodeMutableState &state,
+                       SmallVectorImpl<MatchResult> *matches) const;
+
+  /// A vector containing pointers to unqiued data. The storage is intentionally
+  /// opaque such that we can store a wide range of data types. The types of
+  /// data stored here include:
+  ///  * Attribute, Identifier, OperationName, Type
+  std::vector<const void *> uniquedData;
+
+  /// A vector containing the generated bytecode for the matcher.
+  SmallVector<ByteCodeField, 64> matcherByteCode;
+
+  /// A vector containing the generated bytecode for all of the rewriters.
+  SmallVector<ByteCodeField, 64> rewriterByteCode;
+
+  /// The set of patterns contained within the bytecode.
+  SmallVector<PDLByteCodePattern, 32> patterns;
+
+  /// A set of user defined functions invoked via PDL.
+  std::vector<PDLConstraintFunction> constraintFunctions;
+  std::vector<PDLCreateFunction> createFunctions;
+  std::vector<PDLRewriteFunction> rewriteFunctions;
+
+  /// The maximum memory index used by a value.
+  ByteCodeField maxValueMemoryIndex = 0;
+};
+
+} // end namespace detail
+} // end namespace mlir
+
+#endif // MLIR_REWRITE_BYTECODE_H_

mlir/lib/Rewrite/ByteCode.cpp

+//===- ByteCode.cpp - Pattern ByteCode 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 implements MLIR to byte-code generation and the interpreter.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ByteCode.h"
+#include "mlir/Analysis/Liveness.h"
+#include "mlir/Dialect/PDL/IR/PDLTypes.h"
+#include "mlir/Dialect/PDLInterp/IR/PDLInterp.h"
+#include "mlir/IR/Function.h"
+#include "mlir/IR/RegionGraphTraits.h"
+#include "llvm/ADT/IntervalMap.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/TypeSwitch.h"
+#include "llvm/Support/Debug.h"
+
+#define DEBUG_TYPE "pdl-bytecode"
+
+using namespace mlir;
+using namespace mlir::detail;
+
+//===----------------------------------------------------------------------===//
+// PDLByteCodePattern
+//===----------------------------------------------------------------------===//
+
+PDLByteCodePattern PDLByteCodePattern::create(pdl_interp::RecordMatchOp matchOp,
+                                              ByteCodeAddr rewriterAddr) {
+  SmallVector<StringRef, 8> generatedOps;
+  if (ArrayAttr generatedOpsAttr = matchOp.generatedOpsAttr())
+    generatedOps =
+        llvm::to_vector<8>(generatedOpsAttr.getAsValueRange<StringAttr>());
+
+  PatternBenefit benefit = matchOp.benefit();
+  MLIRContext *ctx = matchOp.getContext();
+
+  // Check to see if this is pattern matches a specific operation type.
+  if (Optional<StringRef> rootKind = matchOp.rootKind())
+    return PDLByteCodePattern(rewriterAddr, *rootKind, generatedOps, benefit,
+                              ctx);
+  return PDLByteCodePattern(rewriterAddr, generatedOps, benefit, ctx,
+                            MatchAnyOpTypeTag());
+}
+
+//===----------------------------------------------------------------------===//
+// PDLByteCodeMutableState
+//===----------------------------------------------------------------------===//
+
+/// Set the new benefit for a bytecode pattern. The `patternIndex` corresponds
+/// to the position of the pattern within the range returned by
+/// `PDLByteCode::getPatterns`.
+void PDLByteCodeMutableState::updatePatternBenefit(unsigned patternIndex,
+                                                   PatternBenefit benefit) {
+  currentPatternBenefits[patternIndex] = benefit;
+}
+
+//===----------------------------------------------------------------------===//
+// Bytecode OpCodes
+//===----------------------------------------------------------------------===//
+
+namespace {
+enum OpCode : ByteCodeField {
+  /// Apply an externally registered constraint.
+  ApplyConstraint,
+  /// Apply an externally registered rewrite.
+  ApplyRewrite,
+  /// Check if two generic values are equal.
+  AreEqual,
+  /// Unconditional branch.
+  Branch,
+  /// Compare the operand count of an operation with a constant.
+  CheckOperandCount,
+  /// Compare the name of an operation with a constant.
+  CheckOperationName,
+  /// Compare the result count of an operation with a constant.
+  CheckResultCount,
+  /// Invoke a native creation method.
+  CreateNative,
+  /// Create an operation.
+  CreateOperation,
+  /// Erase an operation.
+  EraseOp,
+  /// Terminate a matcher or rewrite sequence.
+  Finalize,
+  /// Get a specific attribute of an operation.
+  GetAttribute,
+  /// Get the type of an attribute.
+  GetAttributeType,
+  /// Get the defining operation of a value.
+  GetDefiningOp,
+  /// Get a specific operand of an operation.
+  GetOperand0,
+  GetOperand1,
+  GetOperand2,
+  GetOperand3,
+  GetOperand,
+  /// Get a specific result of an operation.
+  GetResult0,
+  GetResult1,
+  GetResult2,
+  GetResult3,
+  GetResult,
+  /// Get the type of a value.
+  GetValueType,
+  /// Check if a generic value is not null.
+  IsNotNull,
+  /// Record a successful pattern match.
+  RecordMatch,
+  /// Replace an operation.
+  ReplaceOp,
+  /// Compare an attribute with a set of constants.
+  SwitchAttribute,
+  /// Compare the operand count of an operation with a set of constants.
+  SwitchOperandCount,
+  /// Compare the name of an operation with a set of constants.
+  SwitchOperationName,
+  /// Compare the result count of an operation with a set of constants.
+  SwitchResultCount,
+  /// Compare a type with a set of constants.
+  SwitchType,
+};
+
+enum class PDLValueKind { Attribute, Operation, Type, Value };
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// ByteCode Generation
+//===----------------------------------------------------------------------===//
+
+//===----------------------------------------------------------------------===//
+// Generator
+
+namespace {
+class ByteCodeWriter;
+
+/// This class represents the main generator for the pattern bytecode.
+class Generator {
+public:
+  Generator(MLIRContext *ctx, std::vector<const void *> &uniquedData,
+            SmallVectorImpl<ByteCodeField> &matcherByteCode,
+            SmallVectorImpl<ByteCodeField> &rewriterByteCode,
+            SmallVectorImpl<PDLByteCodePattern> &patterns,
+            ByteCodeField &maxValueMemoryIndex,
+            llvm::StringMap<PDLConstraintFunction> &constraintFns,
+            llvm::StringMap<PDLCreateFunction> &createFns,
+            llvm::StringMap<PDLRewriteFunction> &rewriteFns)
+      : ctx(ctx), uniquedData(uniquedData), matcherByteCode(matcherByteCode),
+        rewriterByteCode(rewriterByteCode), patterns(patterns),
+        maxValueMemoryIndex(maxValueMemoryIndex) {
+    for (auto it : llvm::enumerate(constraintFns))
+      constraintToMemIndex.try_emplace(it.value().first(), it.index());
+    for (auto it : llvm::enumerate(createFns))
+      nativeCreateToMemIndex.try_emplace(it.value().first(), it.index());
+    for (auto it : llvm::enumerate(rewriteFns))
+      externalRewriterToMemIndex.try_emplace(it.value().first(), it.index());
+  }
+
+  /// Generate the bytecode for the given PDL interpreter module.
+  void generate(ModuleOp module);
+
+  /// Return the memory index to use for the given value.
+  ByteCodeField &getMemIndex(Value value) {
+    assert(valueToMemIndex.count(value) &&
+           "expected memory index to be assigned");
+    return valueToMemIndex[value];
+  }
+
+  /// Return an index to use when referring to the given data that is uniqued in
+  /// the MLIR context.
+  template <typename T>
+  std::enable_if_t<!std::is_convertible<T, Value>::value, ByteCodeField &>
+  getMemIndex(T val) {
+    const void *opaqueVal = val.getAsOpaquePointer();
+
+    // Get or insert a reference to this value.
+    auto it = uniquedDataToMemIndex.try_emplace(
+        opaqueVal, maxValueMemoryIndex + uniquedData.size());
+    if (it.second)
+      uniquedData.push_back(opaqueVal);
+    return it.first->second;
+  }
+
+private:
+  /// Allocate memory indices for the results of operations within the matcher
+  /// and rewriters.
+  void allocateMemoryIndices(FuncOp matcherFunc, ModuleOp rewriterModule);
+
+  /// Generate the bytecode for the given operation.
+  void generate(Operation *op, ByteCodeWriter &writer);
+  void generate(pdl_interp::ApplyConstraintOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::ApplyRewriteOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::AreEqualOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::BranchOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::CheckAttributeOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::CheckOperandCountOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::CheckOperationNameOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::CheckResultCountOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::CheckTypeOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::CreateAttributeOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::CreateNativeOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::CreateOperationOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::CreateTypeOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::EraseOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::FinalizeOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::GetAttributeOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::GetAttributeTypeOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::GetDefiningOpOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::GetOperandOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::GetResultOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::GetValueTypeOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::InferredTypeOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::IsNotNullOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::RecordMatchOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::ReplaceOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::SwitchAttributeOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::SwitchTypeOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::SwitchOperandCountOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::SwitchOperationNameOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::SwitchResultCountOp op, ByteCodeWriter &writer);
+
+  /// Mapping from value to its corresponding memory index.
+  DenseMap<Value, ByteCodeField> valueToMemIndex;
+
+  /// Mapping from the name of an externally registered rewrite to its index in
+  /// the bytecode registry.
+  llvm::StringMap<ByteCodeField> externalRewriterToMemIndex;
+
+  /// Mapping from the name of an externally registered constraint to its index
+  /// in the bytecode registry.
+  llvm::StringMap<ByteCodeField> constraintToMemIndex;
+
+  /// Mapping from the name of an externally registered creation method to its
+  /// index in the bytecode registry.
+  llvm::StringMap<ByteCodeField> nativeCreateToMemIndex;
+
+  /// Mapping from rewriter function name to the bytecode address of the
+  /// rewriter function in byte.
+  llvm::StringMap<ByteCodeAddr> rewriterToAddr;
+
+  /// Mapping from a uniqued storage object to its memory index within
+  /// `uniquedData`.
+  DenseMap<const void *, ByteCodeField> uniquedDataToMemIndex;
+
+  /// The current MLIR context.
+  MLIRContext *ctx;
+
+  /// Data of the ByteCode class to be populated.
+  std::vector<const void *> &uniquedData;
+  SmallVectorImpl<ByteCodeField> &matcherByteCode;
+  SmallVectorImpl<ByteCodeField> &rewriterByteCode;
+  SmallVectorImpl<PDLByteCodePattern> &patterns;
+  ByteCodeField &maxValueMemoryIndex;
+};
+
+/// This class provides utilities for writing a bytecode stream.
+struct ByteCodeWriter {
+  ByteCodeWriter(SmallVectorImpl<ByteCodeField> &bytecode, Generator &generator)
+      : bytecode(bytecode), generator(generator) {}
+
+  /// Append a field to the bytecode.
+  void append(ByteCodeField field) { bytecode.push_back(field); }
+
+  /// Append an address to the bytecode.
+  void append(ByteCodeAddr field) {
+    static_assert((sizeof(ByteCodeAddr) / sizeof(ByteCodeField)) == 2,
+                  "unexpected ByteCode address size");
+
+    ByteCodeField fieldParts[2];
+    std::memcpy(fieldParts, &field, sizeof(ByteCodeAddr));
+    bytecode.append({fieldParts[0], fieldParts[1]});
+  }
+
+  /// Append a successor range to the bytecode, the exact address will need to
+  /// be resolved later.
+  void append(SuccessorRange successors) {
+    // Add back references to the any successors so that the address can be
+    // resolved later.
+    for (Block *successor : successors) {
+      unresolvedSuccessorRefs[successor].push_back(bytecode.size());
+      append(ByteCodeAddr(0));
+    }
+  }
+
+  /// Append a range of values that will be read as generic PDLValues.
+  void appendPDLValueList(OperandRange values) {
+    bytecode.push_back(values.size());
+    for (Value value : values) {
+      // Append the type of the value in addition to the value itself.
+      PDLValueKind kind =
+          TypeSwitch<Type, PDLValueKind>(value.getType())
+              .Case<pdl::AttributeType>(
+                  [](Type) { return PDLValueKind::Attribute; })
+              .Case<pdl::OperationType>(
+                  [](Type) { return PDLValueKind::Operation; })
+              .Case<pdl::TypeType>([](Type) { return PDLValueKind::Type; })
+              .Case<pdl::ValueType>([](Type) { return PDLValueKind::Value; });
+      bytecode.push_back(static_cast<ByteCodeField>(kind));
+      append(value);
+    }
+  }
+
+  /// Check if the given class `T` has an iterator type.
+  template <typename T, typename... Args>
+  using has_pointer_traits = decltype(std::declval<T>().getAsOpaquePointer());
+
+  /// Append a value that will be stored in a memory slot and not inline within
+  /// the bytecode.
+  template <typename T>
+  std::enable_if_t<llvm::is_detected<has_pointer_traits, T>::value ||
+                   std::is_pointer<T>::value>
+  append(T value) {
+    bytecode.push_back(generator.getMemIndex(value));
+  }
+
+  /// Append a range of values.
+  template <typename T, typename IteratorT = llvm::detail::IterOfRange<T>>
+  std::enable_if_t<!llvm::is_detected<has_pointer_traits, T>::value>
+  append(T range) {
+    bytecode.push_back(llvm::size(range));
+    for (auto it : range)
+      append(it);
+  }
+
+  /// Append a variadic number of fields to the bytecode.
+  template <typename FieldTy, typename Field2Ty, typename... FieldTys>
+  void append(FieldTy field, Field2Ty field2, FieldTys... fields) {
+    append(field);
+    append(field2, fields...);
+  }
+
+  /// Successor references in the bytecode that have yet to be resolved.
+  DenseMap<Block *, SmallVector<unsigned, 4>> unresolvedSuccessorRefs;
+
+  /// The underlying bytecode buffer.
+  SmallVectorImpl<ByteCodeField> &bytecode;
+
+  /// The main generator producing PDL.
+  Generator &generator;
+};
+} // end anonymous namespace
+
+void Generator::generate(ModuleOp module) {
+  FuncOp matcherFunc = module.lookupSymbol<FuncOp>(
+      pdl_interp::PDLInterpDialect::getMatcherFunctionName());
+  ModuleOp rewriterModule = module.lookupSymbol<ModuleOp>(
+      pdl_interp::PDLInterpDialect::getRewriterModuleName());
+  assert(matcherFunc && rewriterModule && "invalid PDL Interpreter module");
+
+  // Allocate memory indices for the results of operations within the matcher
+  // and rewriters.
+  allocateMemoryIndices(matcherFunc, rewriterModule);
+
+  // Generate code for the rewriter functions.
+  ByteCodeWriter rewriterByteCodeWriter(rewriterByteCode, *this);
+  for (FuncOp rewriterFunc : rewriterModule.getOps<FuncOp>()) {
+    rewriterToAddr.try_emplace(rewriterFunc.getName(), rewriterByteCode.size());
+    for (Operation &op : rewriterFunc.getOps())
+      generate(&op, rewriterByteCodeWriter);
+  }
+  assert(rewriterByteCodeWriter.unresolvedSuccessorRefs.empty() &&
+         "unexpected branches in rewriter function");
+
+  // Generate code for the matcher function.
+  DenseMap<Block *, ByteCodeAddr> blockToAddr;
+  llvm::ReversePostOrderTraversal<Region *> rpot(&matcherFunc.getBody());
+  ByteCodeWriter matcherByteCodeWriter(matcherByteCode, *this);
+  for (Block *block : rpot) {
+    // Keep track of where this block begins within the matcher function.
+    blockToAddr.try_emplace(block, matcherByteCode.size());
+    for (Operation &op : *block)
+      generate(&op, matcherByteCodeWriter);
+  }
+
+  // Resolve successor references in the matcher.
+  for (auto &it : matcherByteCodeWriter.unresolvedSuccessorRefs) {
+    ByteCodeAddr addr = blockToAddr[it.first];
+    for (unsigned offsetToFix : it.second)
+      std::memcpy(&matcherByteCode[offsetToFix], &addr, sizeof(ByteCodeAddr));
+  }
+}
+
+void Generator::allocateMemoryIndices(FuncOp matcherFunc,
+                                      ModuleOp rewriterModule) {
+  // Rewriters use simplistic allocation scheme that simply assigns an index to
+  // each result.
+  for (FuncOp rewriterFunc : rewriterModule.getOps<FuncOp>()) {
+    ByteCodeField index = 0;
+    for (BlockArgument arg : rewriterFunc.getArguments())
+      valueToMemIndex.try_emplace(arg, index++);
+    rewriterFunc.getBody().walk([&](Operation *op) {
+      for (Value result : op->getResults())
+        valueToMemIndex.try_emplace(result, index++);
+    });
+    if (index > maxValueMemoryIndex)
+      maxValueMemoryIndex = index;
+  }
+
+  // The matcher function uses a more sophisticated numbering that tries to
+  // minimize the number of memory indices assigned. This is done by determining
+  // a live range of the values within the matcher, then the allocation is just
+  // finding the minimal number of overlapping live ranges. This is essentially
+  // a simplified form of register allocation where we don't necessarily have a
+  // limited number of registers, but we still want to minimize the number used.
+  DenseMap<Operation *, ByteCodeField> opToIndex;
+  matcherFunc.getBody().walk([&](Operation *op) {
+    opToIndex.insert(std::make_pair(op, opToIndex.size()));
+  });
+
+  // Liveness info for each of the defs within the matcher.
+  using LivenessSet = llvm::IntervalMap<ByteCodeField, char, 16>;
+  LivenessSet::Allocator allocator;
+  DenseMap<Value, LivenessSet> valueDefRanges;
+
+  // Assign the root operation being matched to slot 0.
+  BlockArgument rootOpArg = matcherFunc.getArgument(0);
+  valueToMemIndex[rootOpArg] = 0;
+
+  // Walk each of the blocks, computing the def interval that the value is used.
+  Liveness matcherLiveness(matcherFunc);
+  for (Block &block : matcherFunc.getBody()) {
+    const LivenessBlockInfo *info = matcherLiveness.getLiveness(&block);
+    assert(info && "expected liveness info for block");
+    auto processValue = [&](Value value, Operation *firstUseOrDef) {
+      // We don't need to process the root op argument, this value is always
+      // assigned to the first memory slot.
+      if (value == rootOpArg)
+        return;
+
+      // Set indices for the range of this block that the value is used.
+      auto defRangeIt = valueDefRanges.try_emplace(value, allocator).first;
+      defRangeIt->second.insert(
+          opToIndex[firstUseOrDef],
+          opToIndex[info->getEndOperation(value, firstUseOrDef)],
+          /*dummyValue*/ 0);
+    };
+
+    // Process the live-ins of this block.
+    for (Value liveIn : info->in())
+      processValue(liveIn, &block.front());
+
+    // Process any new defs within this block.
+    for (Operation &op : block)
+      for (Value result : op.getResults())
+        processValue(result, &op);
+  }
+
+  // Greedily allocate memory slots using the computed def live ranges.
+  std::vector<LivenessSet> allocatedIndices;
+  for (auto &defIt : valueDefRanges) {
+    ByteCodeField &memIndex = valueToMemIndex[defIt.first];
+    LivenessSet &defSet = defIt.second;
+
+    // Try to allocate to an existing index.
+    for (auto existingIndexIt : llvm::enumerate(allocatedIndices)) {
+      LivenessSet &existingIndex = existingIndexIt.value();
+      llvm::IntervalMapOverlaps<LivenessSet, LivenessSet> overlaps(
+          defIt.second, existingIndex);
+      if (overlaps.valid())
+        continue;
+      // Union the range of the def within the existing index.
+      for (auto it = defSet.begin(), e = defSet.end(); it != e; ++it)
+        existingIndex.insert(it.start(), it.stop(), /*dummyValue*/ 0);
+      memIndex = existingIndexIt.index() + 1;
+    }
+
+    // If no existing index could be used, add a new one.
+    if (memIndex == 0) {
+      allocatedIndices.emplace_back(allocator);
+      for (auto it = defSet.begin(), e = defSet.end(); it != e; ++it)
+        allocatedIndices.back().insert(it.start(), it.stop(), /*dummyValue*/ 0);
+      memIndex = allocatedIndices.size();
+    }
+  }
+
+  // Update the max number of indices.
+  ByteCodeField numMatcherIndices = allocatedIndices.size() + 1;
+  if (numMatcherIndices > maxValueMemoryIndex)
+    maxValueMemoryIndex = numMatcherIndices;
+}
+
+void Generator::generate(Operation *op, ByteCodeWriter &writer) {
+  TypeSwitch<Operation *>(op)
+      .Case<pdl_interp::ApplyConstraintOp, pdl_interp::ApplyRewriteOp,
+            pdl_interp::AreEqualOp, pdl_interp::BranchOp,
+            pdl_interp::CheckAttributeOp, pdl_interp::CheckOperandCountOp,
+            pdl_interp::CheckOperationNameOp, pdl_interp::CheckResultCountOp,
+            pdl_interp::CheckTypeOp, pdl_interp::CreateAttributeOp,
+            pdl_interp::CreateNativeOp, pdl_interp::CreateOperationOp,
+            pdl_interp::CreateTypeOp, pdl_interp::EraseOp,
+            pdl_interp::FinalizeOp, pdl_interp::GetAttributeOp,
+            pdl_interp::GetAttributeTypeOp, pdl_interp::GetDefiningOpOp,
+            pdl_interp::GetOperandOp, pdl_interp::GetResultOp,
+            pdl_interp::GetValueTypeOp, pdl_interp::InferredTypeOp,
+            pdl_interp::IsNotNullOp, pdl_interp::RecordMatchOp,
+            pdl_interp::ReplaceOp, pdl_interp::SwitchAttributeOp,
+            pdl_interp::SwitchTypeOp, pdl_interp::SwitchOperandCountOp,
+            pdl_interp::SwitchOperationNameOp, pdl_interp::SwitchResultCountOp>(
+          [&](auto interpOp) { this->generate(interpOp, writer); })
+      .Default([](Operation *) {
+        llvm_unreachable("unknown `pdl_interp` operation");
+      });
+}
+
+void Generator::generate(pdl_interp::ApplyConstraintOp op,
+                         ByteCodeWriter &writer) {
+  assert(constraintToMemIndex.count(op.name()) &&
+         "expected index for constraint function");
+  writer.append(OpCode::ApplyConstraint, constraintToMemIndex[op.name()],
+                op.constParamsAttr());
+  writer.appendPDLValueList(op.args());
+  writer.append(op.getSuccessors());
+}
+void Generator::generate(pdl_interp::ApplyRewriteOp op,
+                         ByteCodeWriter &writer) {
+  assert(externalRewriterToMemIndex.count(op.name()) &&
+         "expected index for rewrite function");
+  writer.append(OpCode::ApplyRewrite, externalRewriterToMemIndex[op.name()],
+                op.constParamsAttr(), op.root());
+  writer.appendPDLValueList(op.args());
+}
+void Generator::generate(pdl_interp::AreEqualOp op, ByteCodeWriter &writer) {
+  writer.append(OpCode::AreEqual, op.lhs(), op.rhs(), op.getSuccessors());
+}
+void Generator::generate(pdl_interp::BranchOp op, ByteCodeWriter &writer) {
+  writer.append(OpCode::Branch, SuccessorRange(op));
+}
+void Generator::generate(pdl_interp::CheckAttributeOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::AreEqual, op.attribute(), op.constantValue(),
+                op.getSuccessors());
+}
+void Generator::generate(pdl_interp::CheckOperandCountOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::CheckOperandCount, op.operation(), op.count(),
+                op.getSuccessors());
+}
+void Generator::generate(pdl_interp::CheckOperationNameOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::CheckOperationName, op.operation(),
+                OperationName(op.name(), ctx), op.getSuccessors());
+}
+void Generator::generate(pdl_interp::CheckResultCountOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::CheckResultCount, op.operation(), op.count(),
+                op.getSuccessors());
+}
+void Generator::generate(pdl_interp::CheckTypeOp op, ByteCodeWriter &writer) {
+  writer.append(OpCode::AreEqual, op.value(), op.type(), op.getSuccessors());
+}
+void Generator::generate(pdl_interp::CreateAttributeOp op,
+                         ByteCodeWriter &writer) {
+  // Simply repoint the memory index of the result to the constant.
+  getMemIndex(op.attribute()) = getMemIndex(op.value());
+}
+void Generator::generate(pdl_interp::CreateNativeOp op,
+                         ByteCodeWriter &writer) {
+  assert(nativeCreateToMemIndex.count(op.name()) &&
+         "expected index for creation function");
+  writer.append(OpCode::CreateNative, nativeCreateToMemIndex[op.name()],
+                op.result(), op.constParamsAttr());
+  writer.appendPDLValueList(op.args());
+}
+void Generator::generate(pdl_interp::CreateOperationOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::CreateOperation, op.operation(),
+                OperationName(op.name(), ctx), op.operands());
+
+  // Add the attributes.
+  OperandRange attributes = op.attributes();
+  writer.append(static_cast<ByteCodeField>(attributes.size()));
+  for (auto it : llvm::zip(op.attributeNames(), op.attributes())) {
+    writer.append(
+        Identifier::get(std::get<0>(it).cast<StringAttr>().getValue(), ctx),
+        std::get<1>(it));
+  }
+  writer.append(op.types());
+}
+void Generator::generate(pdl_interp::CreateTypeOp op, ByteCodeWriter &writer) {
+  // Simply repoint the memory index of the result to the constant.
+  getMemIndex(op.result()) = getMemIndex(op.value());
+}
+void Generator::generate(pdl_interp::EraseOp op, ByteCodeWriter &writer) {
+  writer.append(OpCode::EraseOp, op.operation());
+}
+void Generator::generate(pdl_interp::FinalizeOp op, ByteCodeWriter &writer) {
+  writer.append(OpCode::Finalize);
+}
+void Generator::generate(pdl_interp::GetAttributeOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::GetAttribute, op.attribute(), op.operation(),
+                Identifier::get(op.name(), ctx));
+}
+void Generator::generate(pdl_interp::GetAttributeTypeOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::GetAttributeType, op.result(), op.value());
+}
+void Generator::generate(pdl_interp::GetDefiningOpOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::GetDefiningOp, op.operation(), op.value());
+}
+void Generator::generate(pdl_interp::GetOperandOp op, ByteCodeWriter &writer) {
+  uint32_t index = op.index();
+  if (index < 4)
+    writer.append(static_cast<OpCode>(OpCode::GetOperand0 + index));
+  else
+    writer.append(OpCode::GetOperand, index);
+  writer.append(op.operation(), op.value());
+}
+void Generator::generate(pdl_interp::GetResultOp op, ByteCodeWriter &writer) {
+  uint32_t index = op.index();
+  if (index < 4)
+    writer.append(static_cast<OpCode>(OpCode::GetResult0 + index));
+  else
+    writer.append(OpCode::GetResult, index);
+  writer.append(op.operation(), op.value());
+}
+void Generator::generate(pdl_interp::GetValueTypeOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::GetValueType, op.result(), op.value());
+}
+void Generator::generate(pdl_interp::InferredTypeOp op,
+                         ByteCodeWriter &writer) {
+  // InferType maps to a null type as a marker for inferring a result type.
+  getMemIndex(op.type()) = getMemIndex(Type());
+}
+void Generator::generate(pdl_interp::IsNotNullOp op, ByteCodeWriter &writer) {
+  writer.append(OpCode::IsNotNull, op.value(), op.getSuccessors());
+}
+void Generator::generate(pdl_interp::RecordMatchOp op, ByteCodeWriter &writer) {
+  ByteCodeField patternIndex = patterns.size();
+  patterns.emplace_back(PDLByteCodePattern::create(
+      op, rewriterToAddr[op.rewriter().getLeafReference()]));
+  writer.append(OpCode::RecordMatch, patternIndex, SuccessorRange(op),
+                op.matchedOps(), op.inputs());
+}
+void Generator::generate(pdl_interp::ReplaceOp op, ByteCodeWriter &writer) {
+  writer.append(OpCode::ReplaceOp, op.operation(), op.replValues());
+}
+void Generator::generate(pdl_interp::SwitchAttributeOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::SwitchAttribute, op.attribute(), op.caseValuesAttr(),
+                op.getSuccessors());
+}
+void Generator::generate(pdl_interp::SwitchOperandCountOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::SwitchOperandCount, op.operation(), op.caseValuesAttr(),
+                op.getSuccessors());
+}
+void Generator::generate(pdl_interp::SwitchOperationNameOp op,
+                         ByteCodeWriter &writer) {
+  auto cases = llvm::map_range(op.caseValuesAttr(), [&](Attribute attr) {
+    return OperationName(attr.cast<StringAttr>().getValue(), ctx);
+  });
+  writer.append(OpCode::SwitchOperationName, op.operation(), cases,
+                op.getSuccessors());
+}
+void Generator::generate(pdl_interp::SwitchResultCountOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::SwitchResultCount, op.operation(), op.caseValuesAttr(),
+                op.getSuccessors());
+}
+void Generator::generate(pdl_interp::SwitchTypeOp op, ByteCodeWriter &writer) {
+  writer.append(OpCode::SwitchType, op.value(), op.caseValuesAttr(),
+                op.getSuccessors());
+}
+
+//===----------------------------------------------------------------------===//
+// PDLByteCode
+//===----------------------------------------------------------------------===//
+
+PDLByteCode::PDLByteCode(ModuleOp module,
+                         llvm::StringMap<PDLConstraintFunction> constraintFns,
+                         llvm::StringMap<PDLCreateFunction> createFns,
+                         llvm::StringMap<PDLRewriteFunction> rewriteFns) {
+  Generator generator(module.getContext(), uniquedData, matcherByteCode,
+                      rewriterByteCode, patterns, maxValueMemoryIndex,
+                      constraintFns, createFns, rewriteFns);
+  generator.generate(module);
+
+  // Initialize the external functions.
+  for (auto &it : constraintFns)
+    constraintFunctions.push_back(std::move(it.second));
+  for (auto &it : createFns)
+    createFunctions.push_back(std::move(it.second));
+  for (auto &it : rewriteFns)
+    rewriteFunctions.push_back(std::move(it.second));
+}
+
+/// Initialize the given state such that it can be used to execute the current
+/// bytecode.
+void PDLByteCode::initializeMutableState(PDLByteCodeMutableState &state) const {
+  state.memory.resize(maxValueMemoryIndex, nullptr);
+  state.currentPatternBenefits.reserve(patterns.size());
+  for (const PDLByteCodePattern &pattern : patterns)
+    state.currentPatternBenefits.push_back(pattern.getBenefit());
+}
+
+//===----------------------------------------------------------------------===//
+// ByteCode Execution
+
+namespace {
+/// This class provides support for executing a bytecode stream.
+class ByteCodeExecutor {
+public:
+  ByteCodeExecutor(const ByteCodeField *curCodeIt,
+                   MutableArrayRef<const void *> memory,
+                   ArrayRef<const void *> uniquedMemory,
+                   ArrayRef<ByteCodeField> code,
+                   ArrayRef<PatternBenefit> currentPatternBenefits,
+                   ArrayRef<PDLByteCodePattern> patterns,
+                   ArrayRef<PDLConstraintFunction> constraintFunctions,
+                   ArrayRef<PDLCreateFunction> createFunctions,
+                   ArrayRef<PDLRewriteFunction> rewriteFunctions)
+      : curCodeIt(curCodeIt), memory(memory), uniquedMemory(uniquedMemory),
+        code(code), currentPatternBenefits(currentPatternBenefits),
+        patterns(patterns), constraintFunctions(constraintFunctions),
+        createFunctions(createFunctions), rewriteFunctions(rewriteFunctions) {}
+
+  /// Start executing the code at the current bytecode index. `matches` is an
+  /// optional field provided when this function is executed in a matching
+  /// context.
+  void execute(PatternRewriter &rewriter,
+               SmallVectorImpl<PDLByteCode::MatchResult> *matches = nullptr,
+               Optional<Location> mainRewriteLoc = {});
+
+private:
+  /// Read a value from the bytecode buffer, optionally skipping a certain
+  /// number of prefix values. These methods always update the buffer to point
+  /// to the next field after the read data.
+  template <typename T = ByteCodeField> T read(size_t skipN = 0) {
+    curCodeIt += skipN;
+    return readImpl<T>();
+  }
+  ByteCodeField read(size_t skipN = 0) { return read<ByteCodeField>(skipN); }
+
+  /// Read a list of values from the bytecode buffer.
+  template <typename ValueT, typename T>
+  void readList(SmallVectorImpl<T> &list) {
+    list.clear();
+    for (unsigned i = 0, e = read(); i != e; ++i)
+      list.push_back(read<ValueT>());
+  }
+
+  /// Jump to a specific successor based on a predicate value.
+  void selectJump(bool isTrue) { selectJump(size_t(isTrue ? 0 : 1)); }
+  /// Jump to a specific successor based on a destination index.
+  void selectJump(size_t destIndex) {
+    curCodeIt = &code[read<ByteCodeAddr>(destIndex * 2)];
+  }
+
+  /// Handle a switch operation with the provided value and cases.
+  template <typename T, typename RangeT>
+  void handleSwitch(const T &value, RangeT &&cases) {
+    LLVM_DEBUG({
+      llvm::dbgs() << "  * Value: " << value << "\n"
+                   << "  * Cases: ";
+      llvm::interleaveComma(cases, llvm::dbgs());
+      llvm::dbgs() << "\n\n";
+    });
+
+    // Check to see if the attribute value is within the case list. Jump to
+    // the correct successor index based on the result.
+    auto it = llvm::find(cases, value);
+    selectJump(it == cases.end() ? size_t(0) : ((it - cases.begin()) + 1));
+  }
+
+  /// Internal implementation of reading various data types from the bytecode
+  /// stream.
+  template <typename T> const void *readFromMemory() {
+    size_t index = *curCodeIt++;
+
+    // If this type is an SSA value, it can only be stored in non-const memory.
+    if (llvm::is_one_of<T, Operation *, Value>::value || index < memory.size())
+      return memory[index];
+
+    // Otherwise, if this index is not inbounds it is uniqued.
+    return uniquedMemory[index - memory.size()];
+  }
+  template <typename T>
+  std::enable_if_t<std::is_pointer<T>::value, T> readImpl() {
+    return reinterpret_cast<T>(const_cast<void *>(readFromMemory<T>()));
+  }
+  template <typename T>
+  std::enable_if_t<std::is_class<T>::value && !std::is_same<PDLValue, T>::value,
+                   T>
+  readImpl() {
+    return T(T::getFromOpaquePointer(readFromMemory<T>()));
+  }
+  template <typename T>
+  std::enable_if_t<std::is_same<PDLValue, T>::value, T> readImpl() {
+    switch (static_cast<PDLValueKind>(read())) {
+    case PDLValueKind::Attribute:
+      return read<Attribute>();
+    case PDLValueKind::Operation:
+      return read<Operation *>();
+    case PDLValueKind::Type:
+      return read<Type>();
+    case PDLValueKind::Value:
+      return read<Value>();
+    }
+  }
+  template <typename T>
+  std::enable_if_t<std::is_same<T, ByteCodeAddr>::value, T> readImpl() {
+    static_assert((sizeof(ByteCodeAddr) / sizeof(ByteCodeField)) == 2,
+                  "unexpected ByteCode address size");
+    ByteCodeAddr result;
+    std::memcpy(&result, curCodeIt, sizeof(ByteCodeAddr));
+    curCodeIt += 2;
+    return result;
+  }
+  template <typename T>
+  std::enable_if_t<std::is_same<T, ByteCodeField>::value, T> readImpl() {
+    return *curCodeIt++;
+  }
+
+  /// The underlying bytecode buffer.
+  const ByteCodeField *curCodeIt;
+
+  /// The current execution memory.
+  MutableArrayRef<const void *> memory;
+
+  /// References to ByteCode data necessary for execution.
+  ArrayRef<const void *> uniquedMemory;
+  ArrayRef<ByteCodeField> code;
+  ArrayRef<PatternBenefit> currentPatternBenefits;
+  ArrayRef<PDLByteCodePattern> patterns;
+  ArrayRef<PDLConstraintFunction> constraintFunctions;
+  ArrayRef<PDLCreateFunction> createFunctions;
+  ArrayRef<PDLRewriteFunction> rewriteFunctions;
+};
+} // end anonymous namespace
+
+void ByteCodeExecutor::execute(
+    PatternRewriter &rewriter,
+    SmallVectorImpl<PDLByteCode::MatchResult> *matches,
+    Optional<Location> mainRewriteLoc) {
+  while (true) {
+    OpCode opCode = static_cast<OpCode>(read());
+    switch (opCode) {
+    case ApplyConstraint: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing ApplyConstraint:\n");
+      const PDLConstraintFunction &constraintFn = constraintFunctions[read()];
+      ArrayAttr constParams = read<ArrayAttr>();
+      SmallVector<PDLValue, 16> args;
+      readList<PDLValue>(args);
+      LLVM_DEBUG({
+        llvm::dbgs() << "  * Arguments: ";
+        llvm::interleaveComma(args, llvm::dbgs());
+        llvm::dbgs() << "\n  * Parameters: " << constParams << "\n\n";
+      });
+
+      // Invoke the constraint and jump to the proper destination.
+      selectJump(succeeded(constraintFn(args, constParams, rewriter)));
+      break;
+    }
+    case ApplyRewrite: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing ApplyRewrite:\n");
+      const PDLRewriteFunction &rewriteFn = rewriteFunctions[read()];
+      ArrayAttr constParams = read<ArrayAttr>();
+      Operation *root = read<Operation *>();
+      SmallVector<PDLValue, 16> args;
+      readList<PDLValue>(args);
+
+      LLVM_DEBUG({
+        llvm::dbgs() << "  * Root: " << *root << "\n"
+                     << "  * Arguments: ";
+        llvm::interleaveComma(args, llvm::dbgs());
+        llvm::dbgs() << "\n  * Parameters: " << constParams << "\n\n";
+      });
+      rewriteFn(root, args, constParams, rewriter);
+      break;
+    }
+    case AreEqual: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing AreEqual:\n");
+      const void *lhs = read<const void *>();
+      const void *rhs = read<const void *>();
+
+      LLVM_DEBUG(llvm::dbgs() << "  * " << lhs << " == " << rhs << "\n\n");
+      selectJump(lhs == rhs);
+      break;
+    }
+    case Branch: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing Branch\n\n");
+      curCodeIt = &code[read<ByteCodeAddr>()];
+      break;
+    }
+    case CheckOperandCount: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing CheckOperandCount:\n");
+      Operation *op = read<Operation *>();
+      uint32_t expectedCount = read<uint32_t>();
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Found: " << op->getNumOperands() << "\n"
+                              << "  * Expected: " << expectedCount << "\n\n");
+      selectJump(op->getNumOperands() == expectedCount);
+      break;
+    }
+    case CheckOperationName: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing CheckOperationName:\n");
+      Operation *op = read<Operation *>();
+      OperationName expectedName = read<OperationName>();
+
+      LLVM_DEBUG(llvm::dbgs()
+                 << "  * Found: \"" << op->getName() << "\"\n"
+                 << "  * Expected: \"" << expectedName << "\"\n\n");
+      selectJump(op->getName() == expectedName);
+      break;
+    }
+    case CheckResultCount: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing CheckResultCount:\n");
+      Operation *op = read<Operation *>();
+      uint32_t expectedCount = read<uint32_t>();
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Found: " << op->getNumResults() << "\n"
+                              << "  * Expected: " << expectedCount << "\n\n");
+      selectJump(op->getNumResults() == expectedCount);
+      break;
+    }
+    case CreateNative: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing CreateNative:\n");
+      const PDLCreateFunction &createFn = createFunctions[read()];
+      ByteCodeField resultIndex = read();
+      ArrayAttr constParams = read<ArrayAttr>();
+      SmallVector<PDLValue, 16> args;
+      readList<PDLValue>(args);
+
+      LLVM_DEBUG({
+        llvm::dbgs() << "  * Arguments: ";
+        llvm::interleaveComma(args, llvm::dbgs());
+        llvm::dbgs() << "\n  * Parameters: " << constParams << "\n";
+      });
+
+      PDLValue result = createFn(args, constParams, rewriter);
+      memory[resultIndex] = result.getAsOpaquePointer();
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Result: " << result << "\n\n");
+      break;
+    }
+    case CreateOperation: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing CreateOperation:\n");
+      assert(mainRewriteLoc && "expected rewrite loc to be provided when "
+                               "executing the rewriter bytecode");
+
+      unsigned memIndex = read();
+      OperationState state(*mainRewriteLoc, read<OperationName>());
+      readList<Value>(state.operands);
+      for (unsigned i = 0, e = read(); i != e; ++i) {
+        Identifier name = read<Identifier>();
+        if (Attribute attr = read<Attribute>())
+          state.addAttribute(name, attr);
+      }
+
+      bool hasInferredTypes = false;
+      for (unsigned i = 0, e = read(); i != e; ++i) {
+        Type resultType = read<Type>();
+        hasInferredTypes |= !resultType;
+        state.types.push_back(resultType);
+      }
+
+      // Handle the case where the operation has inferred types.
+      if (hasInferredTypes) {
+        InferTypeOpInterface::Concept *concept =
+            state.name.getAbstractOperation()
+                ->getInterface<InferTypeOpInterface>();
+
+        // TODO: Handle failure.
+        SmallVector<Type, 2> inferredTypes;
+        if (failed(concept->inferReturnTypes(
+                state.getContext(), state.location, state.operands,
+                state.attributes.getDictionary(state.getContext()),
+                state.regions, inferredTypes)))
+          return;
+
+        for (unsigned i = 0, e = state.types.size(); i != e; ++i)
+          if (!state.types[i])
+            state.types[i] = inferredTypes[i];
+      }
+      Operation *resultOp = rewriter.createOperation(state);
+      memory[memIndex] = resultOp;
+
+      LLVM_DEBUG({
+        llvm::dbgs() << "  * Attributes: "
+                     << state.attributes.getDictionary(state.getContext())
+                     << "\n  * Operands: ";
+        llvm::interleaveComma(state.operands, llvm::dbgs());
+        llvm::dbgs() << "\n  * Result Types: ";
+        llvm::interleaveComma(state.types, llvm::dbgs());
+        llvm::dbgs() << "\n  * Result: " << *resultOp << "\n\n";
+      });
+      break;
+    }
+    case EraseOp: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing EraseOp:\n");
+      Operation *op = read<Operation *>();
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Operation: " << *op << "\n\n");
+      rewriter.eraseOp(op);
+      break;
+    }
+    case Finalize: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing Finalize\n\n");
+      return;
+    }
+    case GetAttribute: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing GetAttribute:\n");
+      unsigned memIndex = read();
+      Operation *op = read<Operation *>();
+      Identifier attrName = read<Identifier>();
+      Attribute attr = op->getAttr(attrName);
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Operation: " << *op << "\n"
+                              << "  * Attribute: " << attrName << "\n"
+                              << "  * Result: " << attr << "\n\n");
+      memory[memIndex] = attr.getAsOpaquePointer();
+      break;
+    }
+    case GetAttributeType: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing GetAttributeType:\n");
+      unsigned memIndex = read();
+      Attribute attr = read<Attribute>();
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Attribute: " << attr << "\n"
+                              << "  * Result: " << attr.getType() << "\n\n");
+      memory[memIndex] = attr.getType().getAsOpaquePointer();
+      break;
+    }
+    case GetDefiningOp: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing GetDefiningOp:\n");
+      unsigned memIndex = read();
+      Value value = read<Value>();
+      Operation *op = value ? value.getDefiningOp() : nullptr;
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Value: " << value << "\n"
+                              << "  * Result: " << *op << "\n\n");
+      memory[memIndex] = op;
+      break;
+    }
+    case GetOperand0:
+    case GetOperand1:
+    case GetOperand2:
+    case GetOperand3:
+    case GetOperand: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing GetOperand:\n");
+      unsigned index =
+          opCode == GetOperand ? read<uint32_t>() : (opCode - GetOperand0);
+      Operation *op = read<Operation *>();
+      unsigned memIndex = read();
+      Value operand =
+          index < op->getNumOperands() ? op->getOperand(index) : Value();
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Operation: " << *op << "\n"
+                              << "  * Index: " << index << "\n"
+                              << "  * Result: " << operand << "\n\n");
+      memory[memIndex] = operand.getAsOpaquePointer();
+      break;
+    }
+    case GetResult0:
+    case GetResult1:
+    case GetResult2:
+    case GetResult3:
+    case GetResult: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing GetResult:\n");
+      unsigned index =
+          opCode == GetResult ? read<uint32_t>() : (opCode - GetResult0);
+      Operation *op = read<Operation *>();
+      unsigned memIndex = read();
+      OpResult result =
+          index < op->getNumResults() ? op->getResult(index) : OpResult();
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Operation: " << *op << "\n"
+                              << "  * Index: " << index << "\n"
+                              << "  * Result: " << result << "\n\n");
+      memory[memIndex] = result.getAsOpaquePointer();
+      break;
+    }
+    case GetValueType: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing GetValueType:\n");
+      unsigned memIndex = read();
+      Value value = read<Value>();
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Value: " << value << "\n"
+                              << "  * Result: " << value.getType() << "\n\n");
+      memory[memIndex] = value.getType().getAsOpaquePointer();
+      break;
+    }
+    case IsNotNull: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing IsNotNull:\n");
+      const void *value = read<const void *>();
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Value: " << value << "\n\n");
+      selectJump(value != nullptr);
+      break;
+    }
+    case RecordMatch: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing RecordMatch:\n");
+      assert(matches &&
+             "expected matches to be provided when executing the matcher");
+      unsigned patternIndex = read();
+      PatternBenefit benefit = currentPatternBenefits[patternIndex];
+      const ByteCodeField *dest = &code[read<ByteCodeAddr>()];
+
+      // If the benefit of the pattern is impossible, skip the processing of the
+      // rest of the pattern.
+      if (benefit.isImpossibleToMatch()) {
+        LLVM_DEBUG(llvm::dbgs() << "  * Benefit: Impossible To Match\n\n");
+        curCodeIt = dest;
+        break;
+      }
+
+      Location matchLoc = rewriter.getUnknownLoc();
+      for (unsigned i = 0, e = read(); i != e; ++i) {
+        matchLoc = FusedLoc::get({matchLoc, read<Operation *>()->getLoc()},
+                                 matchLoc.getContext());
+      }
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Benefit: " << benefit.getBenefit() << "\n"
+                              << "  * Location: " << matchLoc << "\n\n");
+      matches->emplace_back(matchLoc, patterns[patternIndex], benefit);
+      readList<const void *>(matches->back().values);
+      curCodeIt = dest;
+      break;
+    }
+    case ReplaceOp: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing ReplaceOp:\n");
+      Operation *op = read<Operation *>();
+      SmallVector<Value, 16> args;
+      readList<Value>(args);
+
+      LLVM_DEBUG({
+        llvm::dbgs() << "  * Operation: " << *op << "\n"
+                     << "  * Values: ";
+        llvm::interleaveComma(args, llvm::dbgs());
+        llvm::dbgs() << "\n\n";
+      });
+      rewriter.replaceOp(op, args);
+      break;
+    }
+    case SwitchAttribute: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing SwitchAttribute:\n");
+      Attribute value = read<Attribute>();
+      ArrayAttr cases = read<ArrayAttr>();
+      handleSwitch(value, cases);
+      break;
+    }
+    case SwitchOperandCount: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing SwitchOperandCount:\n");
+      Operation *op = read<Operation *>();
+      auto cases = read<DenseIntOrFPElementsAttr>().getValues<uint32_t>();
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Operation: " << *op << "\n");
+      handleSwitch(op->getNumOperands(), cases);
+      break;
+    }
+    case SwitchOperationName: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing SwitchOperationName:\n");
+      OperationName value = read<Operation *>()->getName();
+      size_t caseCount = read();
+
+      // The operation names are stored in-line, so to print them out for
+      // debugging purposes we need to read the array before executing the
+      // switch so that we can display all of the possible values.
+      LLVM_DEBUG({
+        const ByteCodeField *prevCodeIt = curCodeIt;
+        llvm::dbgs() << "  * Value: " << value << "\n"
+                     << "  * Cases: ";
+        llvm::interleaveComma(
+            llvm::map_range(llvm::seq<size_t>(0, caseCount),
+                            [&](size_t i) { return read<OperationName>(); }),
+            llvm::dbgs());
+        llvm::dbgs() << "\n\n";
+        curCodeIt = prevCodeIt;
+      });
+
+      // Try to find the switch value within any of the cases.
+      size_t jumpDest = 0;
+      for (size_t i = 0; i != caseCount; ++i) {
+        if (read<OperationName>() == value) {
+          curCodeIt += (caseCount - i - 1);
+          jumpDest = i + 1;
+          break;
+        }
+      }
+      selectJump(jumpDest);
+      break;
+    }
+    case SwitchResultCount: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing SwitchResultCount:\n");
+      Operation *op = read<Operation *>();
+      auto cases = read<DenseIntOrFPElementsAttr>().getValues<uint32_t>();
+
+      LLVM_DEBUG(llvm::dbgs() << "  * Operation: " << *op << "\n");
+      handleSwitch(op->getNumResults(), cases);
+      break;
+    }
+    case SwitchType: {
+      LLVM_DEBUG(llvm::dbgs() << "Executing SwitchType:\n");
+      Type value = read<Type>();
+      auto cases = read<ArrayAttr>().getAsValueRange<TypeAttr>();
+      handleSwitch(value, cases);
+      break;
+    }
+    }
+  }
+}
+
+/// Run the pattern matcher on the given root operation, collecting the matched
+/// patterns in `matches`.
+void PDLByteCode::match(Operation *op, PatternRewriter &rewriter,
+                        SmallVectorImpl<MatchResult> &matches,
+                        PDLByteCodeMutableState &state) const {
+  // The first memory slot is always the root operation.
+  state.memory[0] = op;
+
+  // The matcher function always starts at code address 0.
+  ByteCodeExecutor executor(matcherByteCode.data(), state.memory, uniquedData,
+                            matcherByteCode, state.currentPatternBenefits,
+                            patterns, constraintFunctions, createFunctions,
+                            rewriteFunctions);
+  executor.execute(rewriter, &matches);
+
+  // Order the found matches by benefit.
+  std::stable_sort(matches.begin(), matches.end(),
+                   [](const MatchResult &lhs, const MatchResult &rhs) {
+                     return lhs.benefit > rhs.benefit;
+                   });
+}
+
+/// Run the rewriter of the given pattern on the root operation `op`.
+void PDLByteCode::rewrite(PatternRewriter &rewriter, const MatchResult &match,
+                          PDLByteCodeMutableState &state) const {
+  // The arguments of the rewrite function are stored at the start of the
+  // memory buffer.
+  llvm::copy(match.values, state.memory.begin());
+
+  ByteCodeExecutor executor(
+      &rewriterByteCode[match.pattern->getRewriterAddr()], state.memory,
+      uniquedData, rewriterByteCode, state.currentPatternBenefits, patterns,
+      constraintFunctions, createFunctions, rewriteFunctions);
+  executor.execute(rewriter, /*matches=*/nullptr, match.location);
+}

mlir/lib/Rewrite/FrozenRewritePatternList.cpp

 //===- FrozenRewritePatternList.cpp - Frozen Pattern List -------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/Rewrite/FrozenRewritePatternList.h"
+#include "ByteCode.h"
+#include "mlir/Conversion/PDLToPDLInterp/PDLToPDLInterp.h"
+#include "mlir/Dialect/PDL/IR/PDL.h"
+#include "mlir/Interfaces/SideEffectInterfaces.h"
+#include "mlir/Pass/Pass.h"
+#include "mlir/Pass/PassManager.h"
 
 using namespace mlir;
 
+static LogicalResult convertPDLToPDLInterp(ModuleOp pdlModule) {
+  // Skip the conversion if the module doesn't contain pdl.
+  if (llvm::empty(pdlModule.getOps<pdl::PatternOp>()))
+    return success();
+
+  // Simplify the provided PDL module. Note that we can't use the canonicalizer
+  // here because it would create a cyclic dependency.
+  auto simplifyFn = [](Operation *op) {
+    // TODO: Add folding here if ever necessary.
+    if (isOpTriviallyDead(op))
+      op->erase();
+  };
+  pdlModule.getBody()->walk(simplifyFn);
+
+  /// Lower the PDL pattern module to the interpreter dialect.
+  PassManager pdlPipeline(pdlModule.getContext(), /*verifyPasses=*/false);
+  pdlPipeline.addPass(createPDLToPDLInterpPass());
+  if (failed(pdlPipeline.run(pdlModule)))
+    return failure();
+
+  // Simplify again after running the lowering pipeline.
+  pdlModule.getBody()->walk(simplifyFn);
+  return success();
+}
+
 //===----------------------------------------------------------------------===//
 // FrozenRewritePatternList
 //===----------------------------------------------------------------------===//
 
 FrozenRewritePatternList::FrozenRewritePatternList(
     OwningRewritePatternList &&patterns)
-    : patterns(patterns.takePatterns()) {}
+    : nativePatterns(std::move(patterns.getNativePatterns())) {
+  PDLPatternModule &pdlPatterns = patterns.getPDLPatterns();
+
+  // Generate the bytecode for the PDL patterns if any were provided.
+  ModuleOp pdlModule = pdlPatterns.getModule();
+  if (!pdlModule)
+    return;
+  if (failed(convertPDLToPDLInterp(pdlModule)))
+    llvm::report_fatal_error(
+        "failed to lower PDL pattern module to the PDL Interpreter");
+
+  // Generate the pdl bytecode.
+  pdlByteCode = std::make_unique<detail::PDLByteCode>(
+      pdlModule, pdlPatterns.takeConstraintFunctions(),
+      pdlPatterns.takeCreateFunctions(), pdlPatterns.takeRewriteFunctions());
+}
+
+FrozenRewritePatternList::FrozenRewritePatternList(
+    FrozenRewritePatternList &&patterns)
+    : nativePatterns(std::move(patterns.nativePatterns)),
+      pdlByteCode(std::move(patterns.pdlByteCode)) {}
+
+FrozenRewritePatternList::~FrozenRewritePatternList() {}

mlir/lib/Rewrite/PatternApplicator.cpp

 //===- PatternApplicator.cpp - Pattern Application Engine -------*- 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 implements an applicator that applies pattern rewrites based upon a
 // user defined cost model.
 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/Rewrite/PatternApplicator.h"
+#include "ByteCode.h"
 #include "llvm/Support/Debug.h"
 
 using namespace mlir;
+using namespace mlir::detail;
+
+PatternApplicator::PatternApplicator(
+    const FrozenRewritePatternList &frozenPatternList)
+    : frozenPatternList(frozenPatternList) {
+  if (const PDLByteCode *bytecode = frozenPatternList.getPDLByteCode()) {
+    mutableByteCodeState = std::make_unique<PDLByteCodeMutableState>();
+    bytecode->initializeMutableState(*mutableByteCodeState);
+  }
+}
+PatternApplicator::~PatternApplicator() {}
 
 #define DEBUG_TYPE "pattern-match"
 
 void PatternApplicator::applyCostModel(CostModel model) {
+  // Apply the cost model to the bytecode patterns first, and then the native
+  // patterns.
+  if (const PDLByteCode *bytecode = frozenPatternList.getPDLByteCode()) {
+    for (auto it : llvm::enumerate(bytecode->getPatterns()))
+      mutableByteCodeState->updatePatternBenefit(it.index(), model(it.value()));
+  }
+
   // Separate patterns by root kind to simplify lookup later on.
   patterns.clear();
   anyOpPatterns.clear();
-  for (const auto &pat : frozenPatternList.getPatterns()) {
+  for (const auto &pat : frozenPatternList.getNativePatterns()) {
     // If the pattern is always impossible to match, just ignore it.
     if (pat.getBenefit().isImpossibleToMatch()) {
       LLVM_DEBUG({
         llvm::dbgs()
             << "Ignoring pattern '" << pat.getRootKind()
             << "' because it is impossible to match (by pattern benefit)\n";
       });
       continue;
void PatternApplicator::applyCostModel(CostModel model) {
   };
   for (auto &it : patterns)
     processPatternList(it.second);
   processPatternList(anyOpPatterns);
 }
 
 void PatternApplicator::walkAllPatterns(
     function_ref<void(const Pattern &)> walk) {
-  for (auto &it : frozenPatternList.getPatterns())
+  for (const Pattern &it : frozenPatternList.getNativePatterns())
+    walk(it);
+  if (const PDLByteCode *bytecode = frozenPatternList.getPDLByteCode()) {
+    for (const Pattern &it : bytecode->getPatterns())
       walk(it);
   }
+}
 
 LogicalResult PatternApplicator::matchAndRewrite(
     Operation *op, PatternRewriter &rewriter,
     function_ref<bool(const Pattern &)> canApply,
     function_ref<void(const Pattern &)> onFailure,
     function_ref<LogicalResult(const Pattern &)> onSuccess) {
+  // Before checking native patterns, first match against the bytecode. This
+  // won't automatically perform any rewrites so there is no need to worry about
+  // conflicts.
+  SmallVector<PDLByteCode::MatchResult, 4> pdlMatches;
+  const PDLByteCode *bytecode = frozenPatternList.getPDLByteCode();
+  if (bytecode)
+    bytecode->match(op, rewriter, pdlMatches, *mutableByteCodeState);
+
   // Check to see if there are patterns matching this specific operation type.
   MutableArrayRef<const RewritePattern *> opPatterns;
   auto patternIt = patterns.find(op->getName());
   if (patternIt != patterns.end())
     opPatterns = patternIt->second;
 
   // Process the patterns for that match the specific operation type, and any
   // operation type in an interleaved fashion.
-  // FIXME: It'd be nice to just write an llvm::make_merge_range utility
-  // and pass in a comparison function. That would make this code trivial.
   auto opIt = opPatterns.begin(), opE = opPatterns.end();
   auto anyIt = anyOpPatterns.begin(), anyE = anyOpPatterns.end();
-  while (opIt != opE && anyIt != anyE) {
-    // Try to match the pattern providing the most benefit.
-    const RewritePattern *pattern;
-    if ((*opIt)->getBenefit() >= (*anyIt)->getBenefit())
-      pattern = *(opIt++);
-    else
-      pattern = *(anyIt++);
-
-    // Otherwise, try to match the generic pattern.
-    if (succeeded(matchAndRewrite(op, *pattern, rewriter, canApply, onFailure,
-                                  onSuccess)))
-      return success();
-  }
-  // If we break from the loop, then only one of the ranges can still have
-  // elements. Loop over both without checking given that we don't need to
-  // interleave anymore.
-  for (const RewritePattern *pattern : llvm::concat<const RewritePattern *>(
-           llvm::make_range(opIt, opE), llvm::make_range(anyIt, anyE))) {
-    if (succeeded(matchAndRewrite(op, *pattern, rewriter, canApply, onFailure,
-                                  onSuccess)))
-      return success();
-  }
-  return failure();
+  auto pdlIt = pdlMatches.begin(), pdlE = pdlMatches.end();
+  while (true) {
+    // Find the next pattern with the highest benefit.
+    const Pattern *bestPattern = nullptr;
+    const PDLByteCode::MatchResult *pdlMatch = nullptr;
+    /// Operation specific patterns.
+    if (opIt != opE)
+      bestPattern = *(opIt++);
+    /// Operation agnostic patterns.
+    if (anyIt != anyE &&
+        (!bestPattern || bestPattern->getBenefit() < (*anyIt)->getBenefit()))
+      bestPattern = *(anyIt++);
+    /// PDL patterns.
+    if (pdlIt != pdlE &&
+        (!bestPattern || bestPattern->getBenefit() < pdlIt->benefit)) {
+      pdlMatch = pdlIt;
+      bestPattern = (pdlIt++)->pattern;
     }
+    if (!bestPattern)
+      break;
 
-LogicalResult PatternApplicator::matchAndRewrite(
-    Operation *op, const RewritePattern &pattern, PatternRewriter &rewriter,
-    function_ref<bool(const Pattern &)> canApply,
-    function_ref<void(const Pattern &)> onFailure,
-    function_ref<LogicalResult(const Pattern &)> onSuccess) {
     // Check that the pattern can be applied.
-  if (canApply && !canApply(pattern))
-    return failure();
+    if (canApply && !canApply(*bestPattern))
+      continue;
 
     // Try to match and rewrite this pattern. The patterns are sorted by
-  // benefit, so if we match we can immediately rewrite.
+    // benefit, so if we match we can immediately rewrite. For PDL patterns, the
+    // match has already been performed, we just need to rewrite.
     rewriter.setInsertionPoint(op);
-  if (succeeded(pattern.matchAndRewrite(op, rewriter)))
-    return success(!onSuccess || succeeded(onSuccess(pattern)));
+    LogicalResult result = success();
+    if (pdlMatch) {
+      bytecode->rewrite(rewriter, *pdlMatch, *mutableByteCodeState);
+    } else {
+      result = static_cast<const RewritePattern *>(bestPattern)
+                   ->matchAndRewrite(op, rewriter);
+    }
+    if (succeeded(result) && (!onSuccess || succeeded(onSuccess(*bestPattern))))
+      return success();
 
+    // Perform any necessary cleanups.
     if (onFailure)
-    onFailure(pattern);
+      onFailure(*bestPattern);
+  }
   return failure();
 }

mlir/test/Rewrite/pdl-bytecode.mlir

+// RUN: mlir-opt %s -test-pdl-bytecode-pass -split-input-file | FileCheck %s
+
+// Note: Tests here are written using the PDL Interpreter dialect to avoid
+// unnecessarily testing unnecessary aspects of the pattern compilation
+// pipeline. These tests are written such that we can focus solely on the
+// lowering/execution of the bytecode itself.
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::ApplyConstraintOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.apply_constraint "multi_entity_constraint"(%root, %root : !pdl.operation, !pdl.operation) -> ^pat, ^end
+
+  ^pat:
+    pdl_interp.apply_constraint "single_entity_constraint"(%root : !pdl.operation) -> ^pat2, ^end
+
+  ^pat2:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.apply_constraint_1
+// CHECK: "test.success"
+module @ir attributes { test.apply_constraint_1 } {
+  "test.op"() { test_attr } : () -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::ApplyRewriteOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.check_operation_name of %root is "test.op" -> ^pat, ^end
+
+  ^pat:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %operand = pdl_interp.get_operand 0 of %root
+      pdl_interp.apply_rewrite "rewriter"[42](%operand : !pdl.value) on %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.apply_rewrite_1
+// CHECK: %[[INPUT:.*]] = "test.op_input"
+// CHECK-NOT: "test.op"
+// CHECK: "test.success"(%[[INPUT]]) {constantParams = [42]}
+module @ir attributes { test.apply_rewrite_1 } {
+  %input = "test.op_input"() : () -> i32
+  "test.op"(%input) : (i32) -> ()
+}
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::AreEqualOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    %test_attr = pdl_interp.create_attribute unit
+    %attr = pdl_interp.get_attribute "test_attr" of %root
+    pdl_interp.are_equal %test_attr, %attr : !pdl.attribute -> ^pat, ^end
+
+  ^pat:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.are_equal_1
+// CHECK: "test.success"
+module @ir attributes { test.are_equal_1 } {
+  "test.op"() { test_attr } : () -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::BranchOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.check_operation_name of %root is "test.op" -> ^pat1, ^end
+
+  ^pat1:
+    pdl_interp.branch ^pat2
+
+  ^pat2:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(2), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.branch_1
+// CHECK: "test.success"
+module @ir attributes { test.branch_1 } {
+  "test.op"() : () -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::CheckAttributeOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    %attr = pdl_interp.get_attribute "test_attr" of %root
+    pdl_interp.check_attribute %attr is unit -> ^pat, ^end
+
+  ^pat:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.check_attribute_1
+// CHECK: "test.success"
+module @ir attributes { test.check_attribute_1 } {
+  "test.op"() { test_attr } : () -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::CheckOperandCountOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.check_operand_count of %root is 1 -> ^pat, ^end
+
+  ^pat:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.check_operand_count_1
+// CHECK: "test.op"() : () -> i32
+// CHECK: "test.success"
+module @ir attributes { test.check_operand_count_1 } {
+  %operand = "test.op"() : () -> i32
+  "test.op"(%operand) : (i32) -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::CheckOperationNameOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.check_operation_name of %root is "test.op" -> ^pat, ^end
+
+  ^pat:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.check_operation_name_1
+// CHECK: "test.success"
+module @ir attributes { test.check_operation_name_1 } {
+  "test.op"() : () -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::CheckResultCountOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.check_result_count of %root is 1 -> ^pat, ^end
+
+  ^pat:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.check_result_count_1
+// CHECK: "test.success"() : () -> ()
+module @ir attributes { test.check_result_count_1 } {
+  "test.op"() : () -> i32
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::CheckTypeOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    %attr = pdl_interp.get_attribute "test_attr" of %root
+    pdl_interp.is_not_null %attr : !pdl.attribute -> ^pat1, ^end
+
+  ^pat1:
+    %type = pdl_interp.get_attribute_type of %attr
+    pdl_interp.check_type %type is i32 -> ^pat2, ^end
+
+  ^pat2:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.check_type_1
+// CHECK: "test.success"
+module @ir attributes { test.check_type_1 } {
+  "test.op"() { test_attr = 10 : i32 } : () -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::CreateAttributeOp
+//===----------------------------------------------------------------------===//
+
+// Fully tested within the tests for other operations.
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::CreateNativeOp
+//===----------------------------------------------------------------------===//
+
+// -----
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.check_operation_name of %root is "test.op" -> ^pat, ^end
+
+  ^pat:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_native "creator"(%root : !pdl.operation) : !pdl.operation
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.create_native_1
+// CHECK: "test.success"
+module @ir attributes { test.create_native_1 } {
+  "test.op"() : () -> ()
+}
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::CreateOperationOp
+//===----------------------------------------------------------------------===//
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::CreateTypeOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    %attr = pdl_interp.get_attribute "test_attr" of %root
+    pdl_interp.is_not_null %attr : !pdl.attribute -> ^pat1, ^end
+
+  ^pat1:
+    %test_type = pdl_interp.create_type i32
+    %type = pdl_interp.get_attribute_type of %attr
+    pdl_interp.are_equal %type, %test_type : !pdl.type -> ^pat2, ^end
+
+  ^pat2:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.create_type_1
+// CHECK: "test.success"
+module @ir attributes { test.create_type_1 } {
+  "test.op"() { test_attr = 0 : i32 } : () -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::EraseOp
+//===----------------------------------------------------------------------===//
+
+// Fully tested within the tests for other operations.
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::FinalizeOp
+//===----------------------------------------------------------------------===//
+
+// Fully tested within the tests for other operations.
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::GetAttributeOp
+//===----------------------------------------------------------------------===//
+
+// Fully tested within the tests for other operations.
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::GetAttributeTypeOp
+//===----------------------------------------------------------------------===//
+
+// Fully tested within the tests for other operations.
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::GetDefiningOpOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.check_operand_count of %root is 5 -> ^pat1, ^end
+
+  ^pat1:
+    %operand0 = pdl_interp.get_operand 0 of %root
+    %operand4 = pdl_interp.get_operand 4 of %root
+    %defOp0 = pdl_interp.get_defining_op of %operand0
+    %defOp4 = pdl_interp.get_defining_op of %operand4
+    pdl_interp.are_equal %defOp0, %defOp4 : !pdl.operation -> ^pat2, ^end
+
+  ^pat2:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.get_defining_op_1
+// CHECK: %[[OPERAND0:.*]] = "test.op"
+// CHECK: %[[OPERAND1:.*]] = "test.op"
+// CHECK: "test.success"
+// CHECK: "test.op"(%[[OPERAND0]], %[[OPERAND0]], %[[OPERAND0]], %[[OPERAND0]], %[[OPERAND1]])
+module @ir attributes { test.get_defining_op_1 } {
+  %operand = "test.op"() : () -> i32
+  %other_operand = "test.op"() : () -> i32
+  "test.op"(%operand, %operand, %operand, %operand, %operand) : (i32, i32, i32, i32, i32) -> ()
+  "test.op"(%operand, %operand, %operand, %operand, %other_operand) : (i32, i32, i32, i32, i32) -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::GetOperandOp
+//===----------------------------------------------------------------------===//
+
+// Fully tested within the tests for other operations.
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::GetResultOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.check_result_count of %root is 5 -> ^pat1, ^end
+
+  ^pat1:
+    %result0 = pdl_interp.get_result 0 of %root
+    %result4 = pdl_interp.get_result 4 of %root
+    %result0_type = pdl_interp.get_value_type of %result0
+    %result4_type = pdl_interp.get_value_type of %result4
+    pdl_interp.are_equal %result0_type, %result4_type : !pdl.type -> ^pat2, ^end
+
+  ^pat2:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.get_result_1
+// CHECK: "test.success"
+// CHECK: "test.op"() : () -> (i32, i32, i32, i32, i64)
+module @ir attributes { test.get_result_1 } {
+  %a:5 = "test.op"() : () -> (i32, i32, i32, i32, i32)
+  %b:5 = "test.op"() : () -> (i32, i32, i32, i32, i64)
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::GetValueTypeOp
+//===----------------------------------------------------------------------===//
+
+// Fully tested within the tests for other operations.
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::InferredTypeOp
+//===----------------------------------------------------------------------===//
+
+// Fully tested within the tests for other operations.
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::IsNotNullOp
+//===----------------------------------------------------------------------===//
+
+// Fully tested within the tests for other operations.
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::RecordMatchOp
+//===----------------------------------------------------------------------===//
+
+// Check that the highest benefit pattern is selected.
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.check_operation_name of %root is "test.op" -> ^pat1, ^end
+
+  ^pat1:
+    pdl_interp.record_match @rewriters::@failure(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^pat2
+
+  ^pat2:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(2), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @failure(%root : !pdl.operation) {
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.record_match_1
+// CHECK: "test.success"
+module @ir attributes { test.record_match_1 } {
+  "test.op"() : () -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::ReplaceOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.check_operation_name of %root is "test.op" -> ^pat, ^end
+
+  ^pat:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %operand = pdl_interp.get_operand 0 of %root
+      pdl_interp.replace %root with (%operand)
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.replace_op_1
+// CHECK: %[[INPUT:.*]] = "test.op_input"
+// CHECK-NOT: "test.op"
+// CHECK: "test.op_consumer"(%[[INPUT]])
+module @ir attributes { test.replace_op_1 } {
+  %input = "test.op_input"() : () -> i32
+  %result = "test.op"(%input) : (i32) -> i32
+  "test.op_consumer"(%result) : (i32) -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::SwitchAttributeOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    %attr = pdl_interp.get_attribute "test_attr" of %root
+    pdl_interp.switch_attribute %attr to [0, unit](^end, ^pat) -> ^end
+
+  ^pat:
+    %attr_2 = pdl_interp.get_attribute "test_attr_2" of %root
+    pdl_interp.switch_attribute %attr_2 to [0, unit](^end, ^end) -> ^pat2
+
+  ^pat2:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.switch_attribute_1
+// CHECK: "test.success"
+module @ir attributes { test.switch_attribute_1 } {
+  "test.op"() { test_attr } : () -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::SwitchOperandCountOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.switch_operand_count of %root to dense<[0, 1]> : vector<2xi32>(^end, ^pat) -> ^end
+
+  ^pat:
+    pdl_interp.switch_operand_count of %root to dense<[0, 2]> : vector<2xi32>(^end, ^end) -> ^pat2
+
+  ^pat2:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.switch_operand_1
+// CHECK: "test.success"
+module @ir attributes { test.switch_operand_1 } {
+  %input = "test.op_input"() : () -> i32
+  "test.op"(%input) : (i32) -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::SwitchOperationNameOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.switch_operation_name of %root to ["foo.op", "test.op"](^end, ^pat1) -> ^end
+
+  ^pat1:
+    pdl_interp.switch_operation_name of %root to ["foo.op", "bar.op"](^end, ^end) -> ^pat2
+
+  ^pat2:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.switch_operation_name_1
+// CHECK: "test.success"
+module @ir attributes { test.switch_operation_name_1 } {
+  "test.op"() : () -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::SwitchResultCountOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    pdl_interp.switch_result_count of %root to dense<[0, 1]> : vector<2xi32>(^end, ^pat) -> ^end
+
+  ^pat:
+    pdl_interp.switch_result_count of %root to dense<[0, 2]> : vector<2xi32>(^end, ^end) -> ^pat2
+
+  ^pat2:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.switch_result_1
+// CHECK: "test.success"
+module @ir attributes { test.switch_result_1 } {
+  "test.op"() : () -> i32
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::SwitchTypeOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  func @matcher(%root : !pdl.operation) {
+    %attr = pdl_interp.get_attribute "test_attr" of %root
+    pdl_interp.is_not_null %attr : !pdl.attribute -> ^pat1, ^end
+
+  ^pat1:
+    %type = pdl_interp.get_attribute_type of %attr
+    pdl_interp.switch_type %type to [i32, i64](^pat2, ^end) -> ^end
+
+  ^pat2:
+    pdl_interp.switch_type %type to [i16, i64](^end, ^end) -> ^pat3
+
+  ^pat3:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"() -> ()
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.switch_type_1
+// CHECK: "test.success"
+module @ir attributes { test.switch_type_1 } {
+  "test.op"() { test_attr = 10 : i32 } : () -> ()
+}

mlir/test/lib/Rewrite/TestPDLByteCode.cpp

+//===- TestPDLByteCode.cpp - Test rewriter bytecode functionality ---------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "mlir/Pass/Pass.h"
+#include "mlir/Pass/PassManager.h"
+#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
+
+using namespace mlir;
+
+/// Custom constraint invoked from PDL.
+static LogicalResult customSingleEntityConstraint(PDLValue value,
+                                                  ArrayAttr constantParams,
+                                                  PatternRewriter &rewriter) {
+  Operation *rootOp = value.cast<Operation *>();
+  return success(rootOp->getName().getStringRef() == "test.op");
+}
+static LogicalResult customMultiEntityConstraint(ArrayRef<PDLValue> values,
+                                                 ArrayAttr constantParams,
+                                                 PatternRewriter &rewriter) {
+  return customSingleEntityConstraint(values[1], constantParams, rewriter);
+}
+
+// Custom creator invoked from PDL.
+static PDLValue customCreate(ArrayRef<PDLValue> args, ArrayAttr constantParams,
+                             PatternRewriter &rewriter) {
+  return rewriter.createOperation(
+      OperationState(args[0].cast<Operation *>()->getLoc(), "test.success"));
+}
+
+/// Custom rewriter invoked from PDL.
+static void customRewriter(Operation *root, ArrayRef<PDLValue> args,
+                           ArrayAttr constantParams,
+                           PatternRewriter &rewriter) {
+  OperationState successOpState(root->getLoc(), "test.success");
+  successOpState.addOperands(args[0].cast<Value>());
+  successOpState.addAttribute("constantParams", constantParams);
+  rewriter.createOperation(successOpState);
+  rewriter.eraseOp(root);
+}
+
+namespace {
+struct TestPDLByteCodePass
+    : public PassWrapper<TestPDLByteCodePass, OperationPass<ModuleOp>> {
+  void runOnOperation() final {
+    ModuleOp module = getOperation();
+
+    // The test cases are encompassed via two modules, one containing the
+    // patterns and one containing the operations to rewrite.
+    ModuleOp patternModule = module.lookupSymbol<ModuleOp>("patterns");
+    ModuleOp irModule = module.lookupSymbol<ModuleOp>("ir");
+    if (!patternModule || !irModule)
+      return;
+
+    // Process the pattern module.
+    patternModule.getOperation()->removeFromParent();
+    PDLPatternModule pdlPattern(patternModule);
+    pdlPattern.registerConstraintFunction("multi_entity_constraint",
+                                          customMultiEntityConstraint);
+    pdlPattern.registerConstraintFunction("single_entity_constraint",
+                                          customSingleEntityConstraint);
+    pdlPattern.registerCreateFunction("creator", customCreate);
+    pdlPattern.registerRewriteFunction("rewriter", customRewriter);
+
+    OwningRewritePatternList patternList(std::move(pdlPattern));
+
+    // Invoke the pattern driver with the provided patterns.
+    (void)applyPatternsAndFoldGreedily(irModule.getBodyRegion(),
+                                       std::move(patternList));
+  }
+};
+} // end anonymous namespace
+
+namespace mlir {
+void registerTestPDLByteCodePass() {
+  PassRegistration<TestPDLByteCodePass>("test-pdl-bytecode-pass",
+                                        "Test PDL ByteCode functionality");
+}
+} // namespace mlir

mlir/test/lib/Transforms/TestLinalgTransforms.cpp

funcOp.walk([](LinalgOp op) {
     op.removeAttr(LinalgTransforms::kLinalgTransformMarker);
   });
 }
 
 static void fillL1TilingAndMatmulToVectorPatterns(
     FuncOp funcOp, StringRef startMarker,
     SmallVectorImpl<OwningRewritePatternList> &patternsVector) {
   MLIRContext *ctx = funcOp.getContext();
-  patternsVector.emplace_back(LinalgTilingPattern<MatmulOp>(
+  patternsVector.emplace_back(std::make_unique<LinalgTilingPattern<MatmulOp>>(
       ctx,
       LinalgTilingOptions().setTileSizes({8, 12, 16}).setInterchange({1, 0, 2}),
       LinalgMarker(Identifier::get(startMarker, ctx),
                    Identifier::get("L1", ctx))));
 
-  patternsVector.emplace_back(LinalgPromotionPattern<MatmulOp>(
+  patternsVector.emplace_back(
+      std::make_unique<LinalgPromotionPattern<MatmulOp>>(
           ctx, LinalgPromotionOptions().setUseFullTileBuffersByDefault(true),
-      LinalgMarker(Identifier::get("L1", ctx), Identifier::get("VEC", ctx))));
+          LinalgMarker(Identifier::get("L1", ctx),
+                       Identifier::get("VEC", ctx))));
 
-  patternsVector.emplace_back(LinalgVectorizationPattern<MatmulOp>(
+  patternsVector.emplace_back(
+      std::make_unique<LinalgVectorizationPattern<MatmulOp>>(
           ctx, LinalgMarker(Identifier::get("VEC", ctx))));
   patternsVector.back()
       .insert<LinalgVectorizationPattern<FillOp>,
               LinalgVectorizationPattern<CopyOp>>(ctx);
 }
 
 //===----------------------------------------------------------------------===//
 // Test promotion callbacks
 //===----------------------------------------------------------------------===//
applyMatmulToVectorPatterns(FuncOp funcOp,
                             bool testMatmulToVectorPatterns1dTiling,
                             bool testMatmulToVectorPatterns2dTiling) {
   MLIRContext *ctx = funcOp.getContext();
   SmallVector<OwningRewritePatternList, 4> stage1Patterns;
   if (testMatmulToVectorPatterns1dTiling) {
     fillL1TilingAndMatmulToVectorPatterns(funcOp, Identifier::get("START", ctx),
                                           stage1Patterns);
   } else if (testMatmulToVectorPatterns2dTiling) {
-    stage1Patterns.emplace_back(LinalgTilingPattern<MatmulOp>(
+    stage1Patterns.emplace_back(std::make_unique<LinalgTilingPattern<MatmulOp>>(
         ctx,
         LinalgTilingOptions()
             .setTileSizes({768, 264, 768})
             .setInterchange({1, 2, 0}),
         LinalgMarker(Identifier::get("START", ctx),
                      Identifier::get("L2", ctx))));
     fillL1TilingAndMatmulToVectorPatterns(funcOp, Identifier::get("L2", ctx),
                                           stage1Patterns);

mlir/tools/mlir-opt/mlir-opt.cpp

 void registerTestLoopFusion();
 void registerTestLoopMappingPass();
 void registerTestLoopPermutationPass();
 void registerTestLoopUnrollingPass();
 void registerTestMatchers();
 void registerTestMemRefDependenceCheck();
 void registerTestMemRefStrideCalculation();
 void registerTestOpaqueLoc();
+void registerTestPDLByteCodePass();
 void registerTestPreparationPassWithAllowedMemrefResults();
 void registerTestPrintDefUsePass();
 void registerTestPrintNestingPass();
 void registerTestRecursiveTypesPass();
 void registerTestReducer();
 void registerTestSpirvEntryPointABIPass();
 void registerTestSCFUtilsPass();
 void registerTestVectorConversions();
#endif
   registerTestLivenessPass();
   registerTestLoopFusion();
   registerTestLoopMappingPass();
   registerTestLoopUnrollingPass();
   registerTestMatchers();
   registerTestMemRefDependenceCheck();
   registerTestMemRefStrideCalculation();
   registerTestOpaqueLoc();
+  registerTestPDLByteCodePass();
   registerTestPreparationPassWithAllowedMemrefResults();
   registerTestPrintDefUsePass();
   registerTestPrintNestingPass();
   registerTestRecursiveTypesPass();
   registerTestReducer();
   registerTestGpuParallelLoopMappingPass();
   registerTestSpirvEntryPointABIPass();
   registerTestSCFUtilsPass();