[mlir] Add transform.foreach_match

[ftynse]

Summary

Add a new transform op combinator that implements an "if-then-else"
style of mechanism for applying transformations. Its main purpose is to
serve as a higher-level driver when applying multiple transform scripts
to potentially overlapping pieces of the payload IR. This is similar to
how the various rewrite drivers operate in C++, but at a higher level
and with more declarative expressions. This is not intended to replace
existing pattern-based rewrites, but to to drive more complex
transformations that are exposed in the transform dialect and are too
complex to be expressed as simple declarative rewrites.

[springerm]

mlir/include/mlir/Dialect/Transform/IR/MatchInterfaces.td

10–14

This should be fixed with D147689.

mlir/include/mlir/Dialect/Transform/IR/TransformOps.td

127

closing parenthesis

130

remove

133

succeeds

136

Is this preorder or postorder?

158

remove

165

an

mlir/lib/Dialect/Transform/IR/TransformOps.cpp

505–508

Could this be done in the op verifier?

571–575

Isn't this already caught by the op verifier/parser?

mlir/test/lib/Dialect/Transform/TestTransformDialectExtension.cpp

218

with

[ftynse]

Address review.

mlir/include/mlir/Dialect/Transform/IR/MatchInterfaces.td

10–14

Nice, thanks for fixing!

mlir/lib/Dialect/Transform/IR/TransformOps.cpp

505–508

We actually allow for external symbols in the verifier. During application, we can "resolve" them by inlining definitions from other files, see https://reviews.llvm.org/D146961. If that didn't happen, this will complain.

571–575

This gets called from the trait verifier, which runs before op verifier, so we unfortunately need to duplicate some conditions to avoid hard failures.

mlir/include/mlir/Dialect/Transform/IR/CMakeLists.txt

 
 add_mlir_dialect(TransformOps transform)
 add_mlir_doc(TransformOps TransformOps Dialects/ -gen-op-doc -dialect=transform)
 
 # Contrary to what the name claims, this only produces the _op_ interface.
 add_mlir_interface(TransformInterfaces)
 add_mlir_doc(TransformInterfaces TransformOpInterfaces Dialects/ -gen-op-interface-docs)
 
+add_mlir_interface(MatchInterfaces)
+add_dependencies(MLIRMatchInterfacesIncGen MLIRTransformInterfacesIncGen)
+add_mlir_doc(TransformInterfaces MatchOpInterfaces Dialects/ -gen-op-interface-docs)
+
 set(LLVM_TARGET_DEFINITIONS TransformInterfaces.td)
 mlir_tablegen(TransformTypeInterfaces.h.inc -gen-type-interface-decls)
 mlir_tablegen(TransformTypeInterfaces.cpp.inc -gen-type-interface-defs)
 add_public_tablegen_target(MLIRTransformDialectTypeInterfacesIncGen)
 add_dependencies(mlir-headers MLIRTransformDialectTypeInterfacesIncGen)
 add_mlir_doc(TransformInterfaces TransformTypeInterfaces Dialects/ -gen-type-interface-docs)

mlir/include/mlir/Dialect/Transform/IR/MatchInterfaces.h

+//===- MatchInterfaces.h - Transform Dialect Interfaces ---------*- 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_DIALECT_TRANSFORM_IR_MATCHINTERFACES_H
+#define MLIR_DIALECT_TRANSFORM_IR_MATCHINTERFACES_H
+
+#include "mlir/Dialect/Transform/IR/TransformInterfaces.h"
+#include "mlir/IR/OpDefinition.h"
+
+namespace mlir {
+namespace transform {
+class MatchOpInterface;
+
+template <typename OpTy>
+class SingleOpMatcherOpTrait
+    : public OpTrait::TraitBase<OpTy, SingleOpMatcherOpTrait> {
+  template <typename T>
+  using has_get_operand_handle =
+      decltype(std::declval<T &>().getOperandHandle());
+  template <typename T>
+  using has_match_operation = decltype(std::declval<T &>().matchOperation(
+      std::declval<Operation *>(), std::declval<TransformResults &>(),
+      std::declval<TransformState &>()));
+
+public:
+  static LogicalResult verifyTrait(Operation *op) {
+    static_assert(llvm::is_detected<has_get_operand_handle, OpTy>::value,
+                  "SingleOpMatcherOpTrait expects operation type to have the "
+                  "getOperandHandle() method");
+    static_assert(llvm::is_detected<has_match_operation, OpTy>::value,
+                  "SingleOpMatcherOpTrait expected operation type to have the "
+                  "matchOperation(Operation *, TransformResults &, "
+                  "TransformState &) method");
+
+    // This must be a dynamic assert because interface registration is dynamic.
+    assert(isa<MatchOpInterface>(op) &&
+           "SingleOpMatchOpTrait is only available on operations with "
+           "MatchOpInterface");
+    Value operandHandle = cast<OpTy>(op).getOperandHandle();
+    if (!operandHandle.getType().isa<TransformHandleTypeInterface>()) {
+      return op->emitError() << "SingleOpMatchOpTrait requires the op handle "
+                                "to be of TransformHandleTypeInterface";
+    }
+
+    return success();
+  }
+
+  DiagnosedSilenceableFailure apply(TransformResults &results,
+                                    TransformState &state) {
+    Value operandHandle = cast<OpTy>(this->getOperation()).getOperandHandle();
+    ArrayRef<Operation *> payload = state.getPayloadOps(operandHandle);
+    if (payload.size() != 1) {
+      return emitDefiniteFailure(this->getOperation()->getLoc())
+             << "SingleOpMatchOpTrait requires the operand handle to point to "
+                "a single payload op";
+    }
+
+    return cast<OpTy>(this->getOperation())
+        .matchOperation(payload[0], results, state);
+  }
+};
+
+} // namespace transform
+} // namespace mlir
+
+#include "mlir/Dialect/Transform/IR/MatchInterfaces.h.inc"
+
+#endif // MLIR_DIALECT_TRANSFORM_IR_MATCHINTERFACES_H

mlir/include/mlir/Dialect/Transform/IR/MatchInterfaces.td

+//===- MatchInterfaces.td - Transform dialect interfaces ---*- tablegen -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+include "mlir/IR/OpBase.td"
+include "mlir/Dialect/Transform/IR/TransformInterfaces.td"
+
+def MatchOpInterface
+    : OpInterface<"MatchOpInterface", [TransformOpInterface]> {
+  let cppNamespace = "::mlir::transform";
+}
+
+def SingleOpMatcher : NativeOpTrait<"SingleOpMatcherOpTrait"> {
+  let cppNamespace = "::mlir::transform";
+
+  string extraDeclaration = [{
+    ::mlir::DiagnosedSilenceableFailure matchOperation(
+          ::mlir::Operation *current,
+          ::mlir::transform::TransformResults &results,
+          ::mlir::transform::TransformState &state);
+  }];
+}

mlir/include/mlir/Dialect/Transform/IR/TransformInterfaces.h

 #include "mlir/Dialect/Transform/IR/TransformTypes.h"
 #include "mlir/Dialect/Transform/Utils/DiagnosedSilenceableFailure.h"
 #include "mlir/Dialect/Transform/Utils/RaggedArray.h"
 #include "mlir/IR/OpDefinition.h"
 #include "mlir/Interfaces/SideEffectInterfaces.h"
 #include "mlir/Support/LogicalResult.h"
 
 namespace mlir {
+
 namespace transform {
 
 class TransformOpInterface;
+class TransformResults;
 
 /// Options controlling the application of transform operations by the
 /// TransformState.
 class TransformOptions {
 public:
   TransformOptions() = default;
   TransformOptions(const TransformOptions &) = default;
   TransformOptions &operator=(const TransformOptions &) = default;
private:
   }
   Mappings &getMapping(Operation *operation) {
     auto it = mappings.find(operation->getParentRegion());
     assert(it != mappings.end() &&
            "trying to find a mapping for an operation from an unmapped region");
     return it->second;
   }
 
+  /// Updates the state to include the associations between op results and the
+  /// provided result of applying a transform op.
+  LogicalResult updateStateFromResults(const TransformResults &results,
+                                       ResultRange opResults);
+
   /// Sets the payload IR ops associated with the given transform IR value
   /// (handle). A payload op may be associated multiple handles as long as
   /// at most one of them gets consumed by further transformations.
   /// For example, a hypothetical "find function by name" may be called twice in
   /// a row to produce two handles pointing to the same function:
   ///
   ///   %0 = transform.find_func_by_name { name = "myfunc" }
   ///   %1 = transform.find_func_by_name { name = "myfunc" }

 /// Verification hook for TransformOpInterface.
 LogicalResult verifyTransformOpInterface(Operation *op);
 
 /// Populates `mappings` with mapped values associated with the given transform
 /// IR values in the given `state`.
 void prepareValueMappings(
     SmallVectorImpl<SmallVector<transform::MappedValue>> &mappings,
     ValueRange values, const transform::TransformState &state);
+
+/// Populates `results` with payload associations that match exactly those of
+/// the operands to `block`'s terminator.
+void forwardTerminatorOperands(Block *block, transform::TransformState &state,
+                               transform::TransformResults &results);
 } // namespace detail
 
 /// This trait is supposed to be attached to Transform dialect operations that
 /// can be standalone top-level transforms. Such operations typically contain
 /// other Transform dialect operations that can be executed following some
 /// control flow logic specific to the current operation. The operations with
 /// this trait are expected to have at least one single-block region with one
 /// argument of PDL Operation type. The operations are also expected to be valid

mlir/include/mlir/Dialect/Transform/IR/TransformOps.h

 //===- TransformDialect.h - Transform dialect operations --------*- 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_DIALECT_TRANSFORM_IR_TRANSFORMOPS_H
 #define MLIR_DIALECT_TRANSFORM_IR_TRANSFORMOPS_H
 
 #include "mlir/Dialect/PDL/IR/PDLTypes.h"
+#include "mlir/Dialect/Transform/IR/MatchInterfaces.h"
 #include "mlir/Dialect/Transform/IR/TransformInterfaces.h"
 #include "mlir/Dialect/Transform/IR/TransformTypes.h"
 #include "mlir/IR/FunctionInterfaces.h"
 #include "mlir/IR/OpDefinition.h"
 #include "mlir/IR/OpImplementation.h"
 #include "mlir/IR/PatternMatch.h"
 #include "mlir/IR/SymbolTable.h"
 #include "mlir/Interfaces/CallInterfaces.h"

mlir/include/mlir/Dialect/Transform/IR/TransformOps.td

 include "mlir/Interfaces/CallInterfaces.td"
 include "mlir/Interfaces/CastInterfaces.td"
 include "mlir/Interfaces/ControlFlowInterfaces.td"
 include "mlir/Interfaces/InferTypeOpInterface.td"
 include "mlir/Interfaces/SideEffectInterfaces.td"
 include "mlir/IR/FunctionInterfaces.td"
 include "mlir/IR/OpAsmInterface.td"
 include "mlir/IR/SymbolInterfaces.td"
+include "mlir/Dialect/Transform/IR/MatchInterfaces.td"
 include "mlir/Dialect/Transform/IR/TransformAttrs.td"
 include "mlir/Dialect/Transform/IR/TransformDialect.td"
 include "mlir/Dialect/Transform/IR/TransformInterfaces.td"
 
 def AlternativesOp : TransformDialectOp<"alternatives",
     [DeclareOpInterfaceMethods<RegionBranchOpInterface,
         ["getSuccessorEntryOperands", "getSuccessorRegions",
          "getRegionInvocationBounds"]>,
def CastOp : TransformDialectOp<"cast",
   let extraClassDeclaration = [{
     ::mlir::DiagnosedSilenceableFailure applyToOne(
       ::mlir::Operation *target,
       ::mlir::transform::ApplyToEachResultList &results,
       ::mlir::transform::TransformState &state);
   }];
 }
 
+def ForeachMatchOp : TransformDialectOp<"foreach_match", [
+    DeclareOpInterfaceMethods<MemoryEffectsOpInterface>,
+    DeclareOpInterfaceMethods<SymbolUserOpInterface>,
+    DeclareOpInterfaceMethods<TransformOpInterface>]> {
+  let summary = "Applies named sequences when a named matcher succeeds";
+  let description = [{
+    Given a pair of co-indexed lists of transform dialect symbols (such as
+    `transform.named_sequence`), walks the payload IR associated with the root
+    handle and interprets the symbols as matcher/action pairs by applying the
+    body of the corresponding symbol definition. The symbol from the first list
+    is the matcher part: if it results in a silenceable error, the error is
+    silenced and the next matcher is attempted. Definite failures from any
+    matcher stop the application immediately and are propagated unconditionally.
+    If none of the matchers succeeds, the next payload operation in walk order
+    (post-order at the moment of writing, double check `Operation::walk`) is
+    matched. If a matcher succeeds, the co-indexed action symbol is applied and
+    the following matchers are not applied to the same payload operation. If the
+    action succeeds, the next payload operation in walk order is matched. If it
+    fails, both silenceable and definite errors are propagated as the result of
+    this op.
+
+    The matcher symbol must take one operand of a type that implements the same
+    transform dialect interface as the `root` operand (a check is performed at
+    application time to see if the associated payload satisfies the constraints
+    of the actual type). It must not consume the operand as multiple matchers
+    may be applied. The matcher may produce any number of results. The action
+    symbol paired with the matcher must take the same number of arguments as the
+    matcher has results, and these arguments must implement the same transform
+    dialect interfaces, but not necessarily have the exact same type (again, a
+    check is performed at application time to see if the associated payload
+    satisfies the constraints of actual types on both sides). The action symbol
+    may not have results. The actions are expected to only modify payload
+    operations nested in the `root` payload operations associated with the
+    operand of this transform operation.
+
+    This operation consumes the operand and produces a new handle associated
+    with the same payload. This is necessary to trigger invalidation of handles
+    to any of the payload operations nested in the payload operations associated
+    with the operand, as those are likely to be modified by actions. Note that
+    the root payload operation associated with the operand are not matched.
+
+    The operation succeeds if none of the matchers produced a definite failure
+    during application and if all of the applied actions produced success. Note
+    that it also succeeds if all the matchers failed on all payload operations,
+    i.e. failure to apply is not an error. The operation produces a silenceable
+    failure if any applied action produced a silenceable failure. In this case,
+    the resulting handle is associated with an empty payload. The operation
+    produces a definite failure if any of the applied matchers or actions
+    produced a definite failure.
+  }];
+
+  let arguments = (ins TransformHandleTypeInterface:$root,
+                       SymbolRefArrayAttr:$matchers,
+                       SymbolRefArrayAttr:$actions);
+  let results = (outs TransformHandleTypeInterface:$updated);
+
+  let assemblyFormat =
+      "`in` $root custom<ForeachMatchSymbols>($matchers, $actions) "
+      "attr-dict `:` functional-type($root, $updated)";
+
+  let hasVerifier = 1;
+}
+
 def ForeachOp : TransformDialectOp<"foreach",
     [DeclareOpInterfaceMethods<TransformOpInterface>,
      DeclareOpInterfaceMethods<MemoryEffectsOpInterface>,
      DeclareOpInterfaceMethods<RegionBranchOpInterface, [
          "getSuccessorRegions", "getSuccessorEntryOperands"]>,
      SingleBlockImplicitTerminator<"::mlir::transform::YieldOp">
     ]> {
   let summary = "Executes the body for each payload op";
let arguments = (ins TransformHandleTypeInterface:$target,
                        I64Attr:$result_number);
   let results = (outs TransformValueHandleTypeInterface:$result);
   let assemblyFormat = "$target `[` $result_number `]` attr-dict `:` "
                        "functional-type(operands, results)";
 }
 
 def IncludeOp : TransformDialectOp<"include",
     [CallOpInterface,
+     MatchOpInterface,
      DeclareOpInterfaceMethods<MemoryEffectsOpInterface>,
      DeclareOpInterfaceMethods<SymbolUserOpInterface>,
      DeclareOpInterfaceMethods<TransformOpInterface>]> {
   let summary = "Includes a named transform sequence";
   let description = [{
     The application of this transform operation is equivalent to applying the
     operations contained in the named transform sequence with operands being
     remapped to block arguments. The behavior of the operation when a

mlir/lib/Dialect/Transform/IR/CMakeLists.txt

 add_mlir_dialect_library(MLIRTransformDialect
+  MatchInterfaces.cpp
   TransformDialect.cpp
   TransformInterfaces.cpp
   TransformOps.cpp
   TransformTypes.cpp
 
   DEPENDS
+  MLIRMatchInterfacesIncGen
   MLIRTransformDialectIncGen
   MLIRTransformInterfacesIncGen
 
   LINK_LIBS PUBLIC
   MLIRIR
   MLIRParser
   MLIRPDLDialect
   MLIRPDLInterpDialect
   MLIRRewrite
   MLIRSideEffectInterfaces
   MLIRTransforms
   MLIRTransformDialectUtils
   )

mlir/lib/Dialect/Transform/IR/MatchInterfaces.cpp

+//===- MatchInterfaces.cpp - Transform Dialect Interfaces -----------------===//
+//
+// 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/Dialect/Transform/IR/MatchInterfaces.h"
+
+using namespace mlir;
+
+//===----------------------------------------------------------------------===//
+// Generated interface implementation.
+//===----------------------------------------------------------------------===//
+
+#include "mlir/Dialect/Transform/IR/MatchInterfaces.cpp.inc"

mlir/lib/Dialect/Transform/IR/TransformInterfaces.cpp

for (Mappings &mapping : llvm::make_second_range(mappings)) {
           diag.attachNote(op->getLoc()) << "payload op: " << op->getName();
           return diag;
         }
       }
     }
   }
 #endif // LLVM_ENABLE_ABI_BREAKING_CHECKS
 
-  for (OpResult result : transform->getResults()) {
-    assert(result.getDefiningOp() == transform.getOperation() &&
-           "payload IR association for a value other than the result of the "
-           "current transform op");
+  if (failed(updateStateFromResults(results, transform->getResults())))
+    return DiagnosedSilenceableFailure::definiteFailure();
+
+  printOnFailureRAII.release();
+  DEBUG_WITH_TYPE(DEBUG_PRINT_AFTER_ALL, {
+    DBGS() << "Top-level payload:\n";
+    getTopLevel()->print(llvm::dbgs());
+  });
+  return result;
+}
+
+LogicalResult transform::TransformState::updateStateFromResults(
+    const TransformResults &results, ResultRange opResults) {
+  for (OpResult result : opResults) {
     if (result.getType().isa<TransformParamTypeInterface>()) {
       assert(results.isParam(result.getResultNumber()) &&
              "expected parameters for the parameter-typed result");
       if (failed(
               setParams(result, results.getParams(result.getResultNumber())))) {
-        return DiagnosedSilenceableFailure::definiteFailure();
+        return failure();
       }
     } else if (result.getType().isa<TransformValueHandleTypeInterface>()) {
       assert(results.isValue(result.getResultNumber()) &&
              "expected values for value-type-result");
       if (failed(setPayloadValues(
               result, results.getValues(result.getResultNumber())))) {
-        return DiagnosedSilenceableFailure::definiteFailure();
+        return failure();
       }
     } else {
       assert(!results.isParam(result.getResultNumber()) &&
              "expected payload ops for the non-parameter typed result");
       if (failed(
               setPayloadOps(result, results.get(result.getResultNumber())))) {
-        return DiagnosedSilenceableFailure::definiteFailure();
+        return failure();
       }
     }
   }
-
-  printOnFailureRAII.release();
-  DEBUG_WITH_TYPE(DEBUG_PRINT_AFTER_ALL, {
-    DBGS() << "Top-level payload:\n";
-    getTopLevel()->print(llvm::dbgs());
-  });
-  return result;
+  return success();
 }
 
 //===----------------------------------------------------------------------===//
 // TransformState::Extension
 //===----------------------------------------------------------------------===//
 
 transform::TransformState::Extension::~Extension() = default;
 
if (r.getType().isa<TransformParamTypeInterface>()) {
       transformResults.setValues(r, castVector<Value>(transposed[position]));
     } else {
       transformResults.set(r, castVector<Operation *>(transposed[position]));
     }
   }
 }
 
 //===----------------------------------------------------------------------===//
-// Utilities for PossibleTopLevelTransformOpTrait.
+// Utilities for implementing transform ops with regions.
 //===----------------------------------------------------------------------===//
 
 void transform::detail::prepareValueMappings(
     SmallVectorImpl<SmallVector<transform::MappedValue>> &mappings,
     ValueRange values, const transform::TransformState &state) {
   for (Value operand : values) {
     SmallVector<MappedValue> &mapped = mappings.emplace_back();
     if (operand.getType().isa<TransformHandleTypeInterface>()) {
       llvm::append_range(mapped, state.getPayloadOps(operand));
     } else if (operand.getType().isa<TransformValueHandleTypeInterface>()) {
       llvm::append_range(mapped, state.getPayloadValues(operand));
     } else {
       assert(operand.getType().isa<TransformParamTypeInterface>() &&
              "unsupported kind of transform dialect value");
       llvm::append_range(mapped, state.getParams(operand));
     }
   }
 }
 
+void transform::detail::forwardTerminatorOperands(
+    Block *block, transform::TransformState &state,
+    transform::TransformResults &results) {
+  for (auto &&[terminatorOperand, result] :
+       llvm::zip(block->getTerminator()->getOperands(),
+                 block->getParentOp()->getOpResults())) {
+    if (result.getType().isa<transform::TransformHandleTypeInterface>()) {
+      results.set(result, state.getPayloadOps(terminatorOperand));
+    } else if (result.getType()
+                   .isa<transform::TransformValueHandleTypeInterface>()) {
+      results.setValues(result, state.getPayloadValues(terminatorOperand));
+    } else {
+      assert(result.getType().isa<transform::TransformParamTypeInterface>() &&
+             "unhandled transform type interface");
+      results.setParams(result, state.getParams(terminatorOperand));
+    }
+  }
+}
+
+//===----------------------------------------------------------------------===//
+// Utilities for PossibleTopLevelTransformOpTrait.
+//===----------------------------------------------------------------------===//
+
 LogicalResult transform::detail::mapPossibleTopLevelTransformOpBlockArguments(
     TransformState &state, Operation *op, Region &region) {
   SmallVector<Operation *> targets;
   SmallVector<SmallVector<MappedValue>> extraMappings;
   if (op->getNumOperands() != 0) {
     llvm::append_range(targets, state.getPayloadOps(op->getOperand(0)));
     prepareValueMappings(extraMappings, op->getOperands().drop_front(), state);
   } else {

mlir/lib/Dialect/Transform/IR/TransformOps.cpp

 //===- TransformDialect.cpp - Transform dialect operations ----------------===//
 //
 // 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/Dialect/Transform/IR/TransformOps.h"
 #include "mlir/Dialect/PDL/IR/PDLOps.h"
+#include "mlir/Dialect/Transform/IR/MatchInterfaces.h"
 #include "mlir/Dialect/Transform/IR/TransformDialect.h"
 #include "mlir/Dialect/Transform/IR/TransformInterfaces.h"
 #include "mlir/Dialect/Transform/IR/TransformTypes.h"
+#include "mlir/IR/Diagnostics.h"
 #include "mlir/IR/FunctionImplementation.h"
 #include "mlir/IR/PatternMatch.h"
 #include "mlir/Interfaces/ControlFlowInterfaces.h"
 #include "mlir/Rewrite/FrozenRewritePatternSet.h"
 #include "mlir/Rewrite/PatternApplicator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/Debug.h"
 #include <optional>
 
 #define DEBUG_TYPE "transform-dialect"
 #define DBGS() (llvm::dbgs() << "[" DEBUG_TYPE "] ")
 
+#define DEBUG_TYPE_MATCHER "transform-matcher"
+#define DBGS_MATCHER() (llvm::dbgs() << "[" DEBUG_TYPE_MATCHER "] ")
+#define DEBUG_MATCHER(x) DEBUG_WITH_TYPE(DEBUG_TYPE_MATCHER, x)
+
 using namespace mlir;
 
 static ParseResult parseSequenceOpOperands(
     OpAsmParser &parser, std::optional<OpAsmParser::UnresolvedOperand> &root,
     Type &rootType,
     SmallVectorImpl<OpAsmParser::UnresolvedOperand> &extraBindings,
     SmallVectorImpl<Type> &extraBindingTypes);
 static void printSequenceOpOperands(OpAsmPrinter &printer, Operation *op,
                                     Value root, Type rootType,
                                     ValueRange extraBindings,
                                     TypeRange extraBindingTypes);
+static void printForeachMatchSymbols(OpAsmPrinter &printer, Operation *op,
+                                     ArrayAttr matchers, ArrayAttr actions);
+static ParseResult parseForeachMatchSymbols(OpAsmParser &parser,
+                                            ArrayAttr &matchers,
+                                            ArrayAttr &actions);
 
 #define GET_OP_CLASSES
 #include "mlir/Dialect/Transform/IR/TransformOps.cpp.inc"
 
 //===----------------------------------------------------------------------===//
 // PatternApplicatorExtension
 //===----------------------------------------------------------------------===//
 

 }
 
 static void forwardEmptyOperands(Block *block, transform::TransformState &state,
                                  transform::TransformResults &results) {
   for (const auto &res : block->getParentOp()->getOpResults())
     results.set(res, {});
 }
 
-static void forwardTerminatorOperands(Block *block,
-                                      transform::TransformState &state,
-                                      transform::TransformResults &results) {
-  for (auto &&[terminatorOperand, result] :
-       llvm::zip(block->getTerminator()->getOperands(),
-                 block->getParentOp()->getOpResults())) {
-    if (result.getType().isa<transform::TransformHandleTypeInterface>()) {
-      results.set(result, state.getPayloadOps(terminatorOperand));
-    } else if (result.getType()
-                   .isa<transform::TransformValueHandleTypeInterface>()) {
-      results.setValues(result, state.getPayloadValues(terminatorOperand));
-    } else {
-      assert(result.getType().isa<transform::TransformParamTypeInterface>() &&
-             "unhandled transform type interface");
-      results.setParams(result, state.getParams(terminatorOperand));
-    }
-  }
-}
-
 DiagnosedSilenceableFailure
 transform::AlternativesOp::apply(transform::TransformResults &results,
                                  transform::TransformState &state) {
   SmallVector<Operation *> originals;
   if (Value scopeHandle = getScope())
     llvm::append_range(originals, state.getPayloadOps(scopeHandle));
   else
     originals.push_back(state.getTopLevel());
if (!failed) {
       IRRewriter rewriter(getContext(), &listener);
       for (const auto &kvp : llvm::zip(originals, clones)) {
         Operation *original = std::get<0>(kvp);
         Operation *clone = std::get<1>(kvp);
         original->getBlock()->getOperations().insert(original->getIterator(),
                                                      clone);
         rewriter.replaceOp(original, clone->getResults());
       }
-      forwardTerminatorOperands(&reg.front(), state, results);
+      detail::forwardTerminatorOperands(&reg.front(), state, results);
       return DiagnosedSilenceableFailure::success();
     }
   }
   return emitSilenceableError() << "all alternatives failed";
 }
 
 void transform::AlternativesOp::getEffects(
     SmallVectorImpl<MemoryEffects::EffectInstance> &effects) {
return llvm::all_of(
       std::initializer_list<Type>{inputs.front(), outputs.front()},
       [](Type ty) {
         return ty
             .isa<pdl::OperationType, transform::TransformHandleTypeInterface>();
       });
 }
 
 //===----------------------------------------------------------------------===//
+// ForeachMatchOp
+//===----------------------------------------------------------------------===//
+
+/// Applies matcher operations from the given `block` assigning `op` as the
+/// payload of the block's first argument. Updates `state` accordingly. If any
+/// of the matcher produces a silenceable failure, discards it (printing the
+/// content to the debug output stream) and returns failure. If any of the
+/// matchers produces a definite failure, reports it and returns failure. If all
+/// matchers in the block succeed, populates `mappings` with the payload
+/// entities associated with the block terminator operands.
+static DiagnosedSilenceableFailure
+matchBlock(Block &block, Operation *op, transform::TransformState &state,
+           SmallVectorImpl<SmallVector<transform::MappedValue>> &mappings) {
+  assert(block.getParent() && "cannot match using a detached block");
+  auto matchScope = state.make_isolated_region_scope(*block.getParent());
+  if (failed(state.mapBlockArgument(block.getArgument(0), {op})))
+    return DiagnosedSilenceableFailure::definiteFailure();
+
+  for (Operation &match : block.without_terminator()) {
+    if (!isa<transform::MatchOpInterface>(match)) {
+      return emitDefiniteFailure(match.getLoc())
+             << "expected operations in the match part to "
+                "implement MatchOpInterface";
+    }
+    DiagnosedSilenceableFailure diag =
+        state.applyTransform(cast<transform::TransformOpInterface>(match));
+    if (diag.succeeded())
+      continue;
+
+    return diag;
+  }
+
+  // Remember the values mapped to the terminator operands so we can
+  // forward them to the action.
+  ValueRange yieldedValues = block.getTerminator()->getOperands();
+  transform::detail::prepareValueMappings(mappings, yieldedValues, state);
+  return DiagnosedSilenceableFailure::success();
+}
+
+DiagnosedSilenceableFailure
+transform::ForeachMatchOp::apply(transform::TransformResults &results,
+                                 transform::TransformState &state) {
+  SmallVector<std::pair<FunctionOpInterface, FunctionOpInterface>>
+      matchActionPairs;
+  matchActionPairs.reserve(getMatchers().size());
+  SymbolTableCollection symbolTable;
+  for (auto &&[matcher, action] :
+       llvm::zip_equal(getMatchers(), getActions())) {
+    auto matcherSymbol =
+        symbolTable.lookupNearestSymbolFrom<FunctionOpInterface>(
+            getOperation(), cast<SymbolRefAttr>(matcher));
+    auto actionSymbol =
+        symbolTable.lookupNearestSymbolFrom<FunctionOpInterface>(
+            getOperation(), cast<SymbolRefAttr>(action));
+    assert(matcherSymbol && actionSymbol &&
+           "unresolved symbols not caught by the verifier");
+
+    if (matcherSymbol.isExternal())
+      return emitDefiniteFailure() << "unresolved external symbol " << matcher;
+    if (actionSymbol.isExternal())
+      return emitDefiniteFailure() << "unresolved external symbol " << action;
+
+    matchActionPairs.emplace_back(matcherSymbol, actionSymbol);
+  }
+
+  for (Operation *root : state.getPayloadOps(getRoot())) {
+    WalkResult walkResult = root->walk([&](Operation *op) {
+      // Skip over the root op itself so we don't invalidate it.
+      if (op == root)
+        return WalkResult::advance();
+
+      DEBUG_MATCHER({
+        DBGS_MATCHER() << "matching ";
+        op->print(llvm::dbgs(),
+                  OpPrintingFlags().assumeVerified().skipRegions());
+        llvm::dbgs() << " @" << op << "\n";
+      });
+
+      // Try all the match/action pairs until the first successful match.
+      for (auto [matcher, action] : matchActionPairs) {
+        SmallVector<SmallVector<MappedValue>> mappings;
+        DiagnosedSilenceableFailure diag =
+            matchBlock(matcher.getFunctionBody().front(), op, state, mappings);
+        if (diag.isDefiniteFailure())
+          return WalkResult::interrupt();
+        if (diag.isSilenceableFailure()) {
+          DEBUG_MATCHER(DBGS_MATCHER()
+                        << "matcher " << matcher.getName() << " failed\n");
+          continue;
+        }
+
+        auto scope = state.make_isolated_region_scope(action.getFunctionBody());
+        for (auto &&[arg, map] : llvm::zip_equal(
+                 action.getFunctionBody().front().getArguments(), mappings)) {
+          if (failed(state.mapBlockArgument(arg, map)))
+            return WalkResult::interrupt();
+        }
+
+        for (Operation &transform :
+             action.getFunctionBody().front().without_terminator()) {
+          DiagnosedSilenceableFailure result =
+              state.applyTransform(cast<TransformOpInterface>(transform));
+          if (failed(result.checkAndReport()))
+            return WalkResult::interrupt();
+        }
+        break;
+      }
+      return WalkResult::advance();
+    });
+    if (walkResult.wasInterrupted())
+      return DiagnosedSilenceableFailure::definiteFailure();
+  }
+
+  // The root operation should not have been affected, so we can just reassign
+  // the payload to the result. Note that we need to consume the root handle to
+  // make sure any handles to operations inside, that could have been affected
+  // by actions, are invalidated.
+  results.set(getUpdated().cast<OpResult>(), state.getPayloadOps(getRoot()));
+  return DiagnosedSilenceableFailure::success();
+}
+
+void transform::ForeachMatchOp::getEffects(
+    SmallVectorImpl<MemoryEffects::EffectInstance> &effects) {
+  // Bail if invalid.
+  if (getOperation()->getNumOperands() < 1 ||
+      getOperation()->getNumResults() < 1) {
+    return modifiesPayload(effects);
+  }
+
+  consumesHandle(getRoot(), effects);
+  producesHandle(getUpdated(), effects);
+  modifiesPayload(effects);
+}
+
+/// Parses the comma-separated list of symbol reference pairs of the format
+/// `@matcher -> @action`.
+static ParseResult parseForeachMatchSymbols(OpAsmParser &parser,
+                                            ArrayAttr &matchers,
+                                            ArrayAttr &actions) {
+  StringAttr matcher;
+  StringAttr action;
+  SmallVector<Attribute> matcherList;
+  SmallVector<Attribute> actionList;
+  do {
+    if (parser.parseSymbolName(matcher) || parser.parseArrow() ||
+        parser.parseSymbolName(action)) {
+      return failure();
+    }
+    matcherList.push_back(SymbolRefAttr::get(matcher));
+    actionList.push_back(SymbolRefAttr::get(action));
+  } while (parser.parseOptionalComma().succeeded());
+
+  matchers = parser.getBuilder().getArrayAttr(matcherList);
+  actions = parser.getBuilder().getArrayAttr(actionList);
+  return success();
+}
+
+/// Prints the comma-separated list of symbol reference pairs of the format
+/// `@matcher -> @action`.
+static void printForeachMatchSymbols(OpAsmPrinter &printer, Operation *op,
+                                     ArrayAttr matchers, ArrayAttr actions) {
+  printer.increaseIndent();
+  printer.increaseIndent();
+  for (auto &&[matcher, action, idx] : llvm::zip_equal(
+           matchers, actions, llvm::seq<unsigned>(0, matchers.size()))) {
+    printer.printNewline();
+    printer << cast<SymbolRefAttr>(matcher) << " -> "
+            << cast<SymbolRefAttr>(action);
+    if (idx != matchers.size() - 1)
+      printer << ", ";
+  }
+  printer.decreaseIndent();
+  printer.decreaseIndent();
+}
+
+LogicalResult transform::ForeachMatchOp::verify() {
+  if (getMatchers().size() != getActions().size())
+    return emitOpError() << "expected the same number of matchers and actions";
+  if (getMatchers().empty())
+    return emitOpError() << "expected at least one match/action pair";
+
+  llvm::SmallPtrSet<Attribute, 8> matcherNames;
+  for (Attribute name : getMatchers()) {
+    if (matcherNames.insert(name).second)
+      continue;
+    emitWarning() << "matcher " << name
+                  << " is used more than once, only the first match will apply";
+  }
+
+  return success();
+}
+
+/// Returns `true` if both types implement one of the interfaces provided as
+/// template parameters.
+template <typename... Tys>
+static bool implementSameInterface(Type t1, Type t2) {
+  return ((isa<Tys>(t1) && isa<Tys>(t2)) || ... || false);
+}
+
+/// Returns `true` if both types implement one of the transform dialect
+/// interfaces.
+static bool implementSameTransformInterface(Type t1, Type t2) {
+  return implementSameInterface<transform::TransformHandleTypeInterface,
+                                transform::TransformParamTypeInterface,
+                                transform::TransformValueHandleTypeInterface>(
+      t1, t2);
+}
+
+/// Checks that the attributes of the function-like operation have correct
+/// consumption effect annotations. If `alsoVerifyInternal`, checks for
+/// annotations being present even if they can be inferred from the body.
+static DiagnosedSilenceableFailure
+verifyFunctionLikeConsumeAnnotations(FunctionOpInterface op,
+                                     bool alsoVerifyInternal = false) {
+  auto transformOp = cast<transform::TransformOpInterface>(op.getOperation());
+  llvm::SmallDenseSet<unsigned> consumedArguments;
+  if (!op.isExternal()) {
+    transform::getConsumedBlockArguments(op.getFunctionBody().front(),
+                                         consumedArguments);
+  }
+  for (unsigned i = 0, e = op.getNumArguments(); i < e; ++i) {
+    bool isConsumed =
+        op.getArgAttr(i, transform::TransformDialect::kArgConsumedAttrName) !=
+        nullptr;
+    bool isReadOnly =
+        op.getArgAttr(i, transform::TransformDialect::kArgReadOnlyAttrName) !=
+        nullptr;
+    if (isConsumed && isReadOnly) {
+      return transformOp.emitSilenceableError()
+             << "argument #" << i << " cannot be both readonly and consumed";
+    }
+    if ((op.isExternal() || alsoVerifyInternal) && !isConsumed && !isReadOnly) {
+      return transformOp.emitSilenceableError()
+             << "must provide consumed/readonly status for arguments of "
+                "external or called ops";
+    }
+    if (op.isExternal())
+      continue;
+
+    if (consumedArguments.contains(i) && !isConsumed && isReadOnly) {
+      return transformOp.emitSilenceableError()
+             << "argument #" << i
+             << " is consumed in the body but is not marked as such";
+    }
+    if (!consumedArguments.contains(i) && isConsumed) {
+      Diagnostic warning(op->getLoc(), DiagnosticSeverity::Warning);
+      warning << "argument #" << i
+              << " is not consumed in the body but is marked as consumed";
+      return DiagnosedSilenceableFailure::silenceableFailure(
+          std::move(warning));
+    }
+  }
+  return DiagnosedSilenceableFailure::success();
+}
+
+LogicalResult transform::ForeachMatchOp::verifySymbolUses(
+    SymbolTableCollection &symbolTable) {
+  assert(getMatchers().size() == getActions().size());
+  auto consumedAttr =
+      StringAttr::get(getContext(), TransformDialect::kArgConsumedAttrName);
+  for (auto &&[matcher, action] :
+       llvm::zip_equal(getMatchers(), getActions())) {
+    auto matcherSymbol = dyn_cast_or_null<FunctionOpInterface>(
+        symbolTable.lookupNearestSymbolFrom(getOperation(),
+                                            cast<SymbolRefAttr>(matcher)));
+    auto actionSymbol = dyn_cast_or_null<FunctionOpInterface>(
+        symbolTable.lookupNearestSymbolFrom(getOperation(),
+                                            cast<SymbolRefAttr>(action)));
+    if (!matcherSymbol ||
+        !isa<TransformOpInterface>(matcherSymbol.getOperation()))
+      return emitError() << "unresolved matcher symbol " << matcher;
+    if (!actionSymbol ||
+        !isa<TransformOpInterface>(actionSymbol.getOperation()))
+      return emitError() << "unresolved action symbol " << action;
+
+    if (failed(verifyFunctionLikeConsumeAnnotations(matcherSymbol,
+                                                    /*alsoVerifyInternal=*/true)
+                   .checkAndReport())) {
+      return failure();
+    }
+    if (failed(verifyFunctionLikeConsumeAnnotations(actionSymbol,
+                                                    /*alsoVerifyInternal=*/true)
+                   .checkAndReport())) {
+      return failure();
+    }
+
+    ArrayRef<Type> matcherResults = matcherSymbol.getResultTypes();
+    ArrayRef<Type> actionArguments = actionSymbol.getArgumentTypes();
+    if (matcherResults.size() != actionArguments.size()) {
+      return emitError() << "mismatching number of matcher results and "
+                            "action arguments between "
+                         << matcher << " (" << matcherResults.size() << ") and "
+                         << action << " (" << actionArguments.size() << ")";
+    }
+    for (auto &&[i, matcherType, actionType] :
+         llvm::enumerate(matcherResults, actionArguments)) {
+      if (implementSameTransformInterface(matcherType, actionType))
+        continue;
+
+      return emitError() << "mismatching type interfaces for matcher result "
+                            "and action argument #"
+                         << i;
+    }
+
+    if (!actionSymbol.getResultTypes().empty()) {
+      InFlightDiagnostic diag =
+          emitError() << "action symbol is not expected to have results";
+      diag.attachNote(actionSymbol->getLoc()) << "symbol declaration";
+      return diag;
+    }
+
+    if (matcherSymbol.getArgumentTypes().size() != 1 ||
+        !implementSameTransformInterface(matcherSymbol.getArgumentTypes()[0],
+                                         getRoot().getType())) {
+      InFlightDiagnostic diag =
+          emitOpError() << "expects matcher symbol to have one argument with "
+                           "the same transform interface as the first operand";
+      diag.attachNote(matcherSymbol->getLoc()) << "symbol declaration";
+      return diag;
+    }
+
+    if (matcherSymbol.getArgAttr(0, consumedAttr)) {
+      InFlightDiagnostic diag =
+          emitOpError()
+          << "does not expect matcher symbol to consume its operand";
+      diag.attachNote(matcherSymbol->getLoc()) << "symbol declaration";
+      return diag;
+    }
+  }
+  return success();
+}
+
+//===----------------------------------------------------------------------===//
 // ForeachOp
 //===----------------------------------------------------------------------===//
 
 DiagnosedSilenceableFailure
 transform::ForeachOp::apply(transform::TransformResults &results,
                             transform::TransformState &state) {
   ArrayRef<Operation *> payloadOps = state.getPayloadOps(getTarget());
   SmallVector<SmallVector<Operation *>> resultOps(getNumResults(), {});
if (result.isSilenceableFailure()) {
         return result;
       }
       (void)result.silence();
     }
   }
 
   // Forward the operation mapping for values yielded from the sequence to the
   // values produced by the sequence op.
-  forwardTerminatorOperands(&block, state, results);
+  transform::detail::forwardTerminatorOperands(&block, state, results);
   return DiagnosedSilenceableFailure::success();
 }
 
 DiagnosedSilenceableFailure
 transform::IncludeOp::apply(transform::TransformResults &results,
                             transform::TransformState &state) {
   auto callee = SymbolTable::lookupNearestSymbolFrom<NamedSequenceOp>(
       getOperation(), getTarget());
void transform::IncludeOp::getEffects(
   for (unsigned i = 0, e = getNumOperands(); i < e; ++i) {
     if (callee.getArgAttr(i, TransformDialect::kArgConsumedAttrName))
       consumesHandle(getOperand(i), effects);
     else
       onlyReadsHandle(getOperand(i), effects);
   }
 }
 
-template <typename... Tys>
-static bool implementSameInterface(Type t1, Type t2) {
-  return ((isa<Tys>(t1) && isa<Tys>(t2)) || ... || false);
-}
-
-/// Checks that the attributes of the named sequence operation have correct
-/// consumption effect annotations. If `alsoVerifyInternal`, checks for
-/// annotations being present even if they can be inferred from the body.
-static DiagnosedSilenceableFailure
-verifyNamedSequenceConsumeAnnotations(transform::NamedSequenceOp op,
-                                      bool alsoVerifyInternal = false) {
-  llvm::SmallDenseSet<unsigned> consumedArguments;
-  if (!op.isExternal()) {
-    transform::getConsumedBlockArguments(op.getBody().front(),
-                                         consumedArguments);
-  }
-  for (unsigned i = 0, e = op.getFunctionType().getNumInputs(); i < e; ++i) {
-    bool isConsumed =
-        op.getArgAttr(i, transform::TransformDialect::kArgConsumedAttrName) !=
-        nullptr;
-    bool isReadOnly =
-        op.getArgAttr(i, transform::TransformDialect::kArgReadOnlyAttrName) !=
-        nullptr;
-    if (isConsumed && isReadOnly) {
-      return op.emitSilenceableError()
-             << "argument #" << i << " cannot be both readonly and consumed";
-    }
-    if ((op.isExternal() || alsoVerifyInternal) && !isConsumed && !isReadOnly) {
-      return op.emitSilenceableError()
-             << "must provide consumed/readonly status for arguments of "
-                "external or called ops";
-    }
-    if (op.isExternal())
-      continue;
-
-    if (consumedArguments.contains(i) && !isConsumed && isReadOnly) {
-      return op.emitSilenceableError()
-             << "argument #" << i
-             << " is consumed in the body but is not marked as such";
-    }
-    if (!consumedArguments.contains(i) && isConsumed) {
-      Diagnostic warning(op->getLoc(), DiagnosticSeverity::Warning);
-      warning << "argument #" << i
-              << " is not consumed in the body but is marked as consumed";
-      return DiagnosedSilenceableFailure::silenceableFailure(
-          std::move(warning));
-    }
-  }
-  return DiagnosedSilenceableFailure::success();
-}
-
 LogicalResult
 transform::IncludeOp::verifySymbolUses(SymbolTableCollection &symbolTable) {
   // Access through indirection and do additional checking because this may be
   // running before the main op verifier.
   auto targetAttr = getOperation()->getAttrOfType<SymbolRefAttr>("target");
   if (!targetAttr)
     return emitOpError() << "expects a 'target' symbol reference attribute";
 
transform::IncludeOp::verifySymbolUses(SymbolTableCollection &symbolTable) {
   }
 
   if (fnType.getNumResults() != getNumResults())
     return emitError("incorrect number of results for callee");
 
   for (unsigned i = 0, e = fnType.getNumResults(); i != e; ++i) {
     Type resultType = getResult(i).getType();
     Type funcType = fnType.getResult(i);
-    if (!implementSameInterface<TransformHandleTypeInterface,
-                                TransformValueHandleTypeInterface,
-                                TransformParamTypeInterface>(resultType,
-                                                             funcType)) {
+    if (!implementSameTransformInterface(resultType, funcType)) {
       return emitOpError() << "type of result #" << i
                            << " must implement the same transform dialect "
                               "interface as the corresponding callee result";
     }
   }
 
-  return verifyNamedSequenceConsumeAnnotations(target,
-                                               /*alsoVerifyInternal=*/true)
+  return verifyFunctionLikeConsumeAnnotations(
+             cast<FunctionOpInterface>(*target),
       .checkAndReport();
 }
 
 //===----------------------------------------------------------------------===//
 // MergeHandlesOp
 //===----------------------------------------------------------------------===//
 
 DiagnosedSilenceableFailure

 
 void transform::NamedSequenceOp::print(OpAsmPrinter &printer) {
   function_interface_impl::printFunctionOp(
       printer, cast<FunctionOpInterface>(getOperation()), /*isVariadic=*/false,
       getFunctionTypeAttrName().getValue(), getArgAttrsAttrName(),
       getResAttrsAttrName());
 }
 
+/// Verifies that a symbol function-like transform dialect operation has the
+/// signature and the terminator that have conforming types, i.e., types
+/// implementing the same transform dialect type interface. If `allowExternal`
+/// is set, allow external symbols (declarations) and don't check the terminator
+/// as it may not exist.
+static DiagnosedSilenceableFailure
+verifyYieldingSingleBlockOp(FunctionOpInterface op, bool allowExternal) {
+  if (auto parent = op->getParentOfType<transform::TransformOpInterface>()) {
+    DiagnosedSilenceableFailure diag =
+        emitSilenceableFailure(op)
+        << "cannot be defined inside another transform op";
+    diag.attachNote(parent.getLoc()) << "ancestor transform op";
+    return diag;
+  }
+
+  if (op.isExternal() || op.getFunctionBody().empty()) {
+    if (allowExternal)
+      return DiagnosedSilenceableFailure::success();
+
+    return emitSilenceableFailure(op) << "cannot be external";
+  }
+
+  if (op.getFunctionBody().front().empty())
+    return emitSilenceableFailure(op) << "expected a non-empty body block";
+
+  Operation *terminator = &op.getFunctionBody().front().back();
+  if (!isa<transform::YieldOp>(terminator)) {
+    DiagnosedSilenceableFailure diag = emitSilenceableFailure(op)
+                                       << "expected '"
+                                       << transform::YieldOp::getOperationName()
+                                       << "' as terminator";
+    diag.attachNote(terminator->getLoc()) << "terminator";
+    return diag;
+  }
+
+  if (terminator->getNumOperands() != op.getResultTypes().size()) {
+    return emitSilenceableFailure(terminator)
+           << "expected terminator to have as many operands as the parent op "
+              "has results";
+  }
+  for (auto [i, operandType, resultType] : llvm::zip_equal(
+           llvm::seq<unsigned>(0, terminator->getNumOperands()),
+           terminator->getOperands().getType(), op.getResultTypes())) {
+    if (operandType == resultType)
+      continue;
+    return emitSilenceableFailure(terminator)
+           << "the type of the terminator operand #" << i
+           << " must match the type of the corresponding parent op result ("
+           << operandType << " vs " << resultType << ")";
+  }
+
+  return DiagnosedSilenceableFailure::success();
+}
+
 /// Verification of a NamedSequenceOp. This does not report the error
 /// immediately, so it can be used to check for op's well-formedness before the
 /// verifier runs, e.g., during trait verification.
 static DiagnosedSilenceableFailure
 verifyNamedSequenceOp(transform::NamedSequenceOp op) {
   if (Operation *parent = op->getParentWithTrait<OpTrait::SymbolTable>()) {
     if (!parent->getAttr(
             transform::TransformDialect::kWithNamedSequenceAttrName)) {
if (auto parent = op->getParentOfType<transform::TransformOpInterface>()) {
     DiagnosedSilenceableFailure diag =
         emitSilenceableFailure(op)
         << "cannot be defined inside another transform op";
     diag.attachNote(parent.getLoc()) << "ancestor transform op";
     return diag;
   }
 
   if (op.isExternal() || op.getBody().empty())
-    return verifyNamedSequenceConsumeAnnotations(op);
+    return verifyFunctionLikeConsumeAnnotations(cast<FunctionOpInterface>(*op));
 
   if (op.getBody().front().empty())
     return emitSilenceableFailure(op) << "expected a non-empty body block";
 
   Operation *terminator = &op.getBody().front().back();
   if (!isa<transform::YieldOp>(terminator)) {
     DiagnosedSilenceableFailure diag = emitSilenceableFailure(op)
                                        << "expected '"
for (auto [i, operandType, resultType] :
     if (operandType == resultType)
       continue;
     return emitSilenceableFailure(terminator)
            << "the type of the terminator operand #" << i
            << " must match the type of the corresponding parent op result ("
            << operandType << " vs " << resultType << ")";
   }
 
-  return verifyNamedSequenceConsumeAnnotations(op);
+  auto funcOp = cast<FunctionOpInterface>(*op);
+  DiagnosedSilenceableFailure diag =
+      verifyFunctionLikeConsumeAnnotations(funcOp);
+  if (!diag.succeeded())
+    return diag;
+
+  return verifyYieldingSingleBlockOp(funcOp,
+                                     /*allowExternal=*/true);
 }
 
 LogicalResult transform::NamedSequenceOp::verify() {
   // Actual verification happens in a separate function for reusability.
   return verifyNamedSequenceOp(*this).checkAndReport();
 }
 
 //===----------------------------------------------------------------------===//

mlir/test/Dialect/Transform/ops-invalid.mlir

module attributes { transform.with_named_sequence } {
   ^bb0(%arg0: !transform.any_op):
     // expected-note @below {{used here as operand #0}}
     transform.include @foo failures(propagate) (%arg0) : (!transform.any_op) -> ()
     // expected-note @below {{used here as operand #0}}
     transform.include @foo failures(propagate) (%arg0) : (!transform.any_op) -> ()
     transform.yield
   }
 }
+
+// -----
+
+module attributes { transform.with_named_sequence } {
+  transform.sequence failures(propagate) {
+  ^bb0(%root: !transform.any_op):
+    // expected-error @below {{unresolved matcher symbol @foo}}
+    transform.foreach_match in %root
+      @foo -> @bar : (!transform.any_op) -> !transform.any_op
+  }
+}
+
+// -----
+
+module attributes { transform.with_named_sequence } {
+  func.func private @foo()
+
+  transform.sequence failures(propagate) {
+  ^bb0(%root: !transform.any_op):
+    // expected-error @below {{unresolved matcher symbol @foo}}
+    transform.foreach_match in %root
+      @foo -> @bar : (!transform.any_op) -> !transform.any_op
+  }
+}
+
+// -----
+
+module attributes { transform.with_named_sequence } {
+  transform.named_sequence @match()
+
+  transform.sequence failures(propagate) {
+  ^bb0(%root: !transform.any_op):
+    // expected-error @below {{unresolved action symbol @bar}}
+    transform.foreach_match in %root
+      @match -> @bar : (!transform.any_op) -> !transform.any_op
+  }
+}
+
+// -----
+
+module attributes { transform.with_named_sequence } {
+  func.func private @bar()
+  transform.named_sequence @match()
+
+  transform.sequence failures(propagate) {
+  ^bb0(%root: !transform.any_op):
+    // expected-error @below {{unresolved action symbol @bar}}
+    transform.foreach_match in %root
+      @match -> @bar : (!transform.any_op) -> !transform.any_op
+  }
+}
+
+// -----
+
+module attributes { transform.with_named_sequence } {
+  transform.named_sequence @match() -> !transform.any_op
+  transform.named_sequence @action()
+
+  transform.sequence failures(propagate) {
+  ^bb0(%root: !transform.any_op):
+    // expected-error @below {{mismatching number of matcher results and action arguments between @match (1) and @action (0)}}
+    transform.foreach_match in %root
+      @match -> @action : (!transform.any_op) -> !transform.any_op
+  }
+}
+
+// -----
+
+module attributes { transform.with_named_sequence } {
+  transform.named_sequence @match(!transform.any_op {transform.readonly})
+  // expected-note @below {{symbol declaration}}
+  transform.named_sequence @action() -> !transform.any_op
+
+  transform.sequence failures(propagate) {
+  ^bb0(%root: !transform.any_op):
+    // expected-error @below {{action symbol is not expected to have results}}
+    transform.foreach_match in %root
+      @match -> @action : (!transform.any_op) -> !transform.any_op
+  }
+}
+
+// -----
+
+module attributes { transform.with_named_sequence } {
+  // expected-note @below {{symbol declaration}}
+  transform.named_sequence @match()
+  transform.named_sequence @action()
+
+  transform.sequence failures(propagate) {
+  ^bb0(%root: !transform.any_op):
+    // expected-error @below {{expects matcher symbol to have one argument with the same transform interface as the first operand}}
+    transform.foreach_match in %root
+      @match -> @action : (!transform.any_op) -> !transform.any_op
+  }
+}
+
+// -----
+
+module attributes { transform.with_named_sequence } {
+  // expected-note @below {{symbol declaration}}
+  transform.named_sequence @match(!transform.any_op {transform.consumed})
+  transform.named_sequence @action()
+
+  transform.sequence failures(propagate) {
+  ^bb0(%root: !transform.any_op):
+    // expected-error @below {{'transform.foreach_match' op does not expect matcher symbol to consume its operand}}
+    transform.foreach_match in %root
+      @match -> @action : (!transform.any_op) -> !transform.any_op
+  }
+}

mlir/test/Dialect/Transform/test-interpreter.mlir

module @named_return attributes { transform.with_named_sequence } {
 
   transform.sequence failures(propagate) {
   ^bb0(%arg0: !transform.any_op):
     %0:2 = include @foo failures(propagate) (%arg0) : (!transform.any_op) -> (!transform.any_op, !transform.any_value)
     transform.test_print_remark_at_operand %0#0, "operation" : !transform.any_op
     transform.test_print_remark_at_operand_value %0#1, "value" : !transform.any_value
   }
 }
+
+// -----
+
+module attributes { transform.with_named_sequence } {
+  transform.named_sequence @match1(%current: !transform.any_op {transform.readonly}) -> (!transform.any_op) {
+    transform.test_succeed_if_operand_of_op_kind %current, "test.some_op" : !transform.any_op
+    transform.yield %current : !transform.any_op
+  }
+
+  transform.named_sequence @match2(%current: !transform.any_op {transform.readonly}) -> (!transform.any_op) {
+    transform.test_succeed_if_operand_of_op_kind %current, "func.func" : !transform.any_op
+    transform.yield %current : !transform.any_op
+  }
+
+  transform.named_sequence @action1(%current: !transform.any_op {transform.readonly}) {
+    transform.test_print_remark_at_operand %current, "matched1" : !transform.any_op
+    transform.yield
+  }
+  transform.named_sequence @action2(%current: !transform.any_op {transform.readonly}) {
+    transform.test_print_remark_at_operand %current, "matched2" : !transform.any_op
+    transform.yield
+  }
+
+  transform.sequence failures(propagate) {
+  ^bb0(%root: !transform.any_op):
+    transform.foreach_match in %root
+        @match1 -> @action1,
+        @match2 -> @action2
+      : (!transform.any_op) -> (!transform.any_op)
+    transform.yield
+  }
+
+  // expected-remark @below {{matched2}}
+  func.func private @foo()
+  // expected-remark @below {{matched2}}
+  func.func private @bar()
+  "test.testtest"() : () -> ()
+  // expected-remark @below {{matched1}}
+  "test.some_op"() : () -> ()
+}
+
+// -----
+
+module attributes { transform.with_named_sequence } {
+  transform.named_sequence @match(!transform.any_op {transform.readonly})
+  transform.named_sequence @action()
+
+  transform.sequence failures(propagate) {
+  ^bb0(%root: !transform.any_op):
+    // expected-error @below {{unresolved external symbol @match}}
+    transform.foreach_match in %root
+      @match -> @action : (!transform.any_op) -> !transform.any_op
+  }
+}
+
+// -----
+
+module attributes { transform.with_named_sequence } {
+  transform.named_sequence @match(%arg: !transform.any_op {transform.readonly}) {
+    transform.yield
+  }
+  transform.named_sequence @action()
+
+  transform.sequence failures(propagate) {
+  ^bb0(%root: !transform.any_op):
+    // expected-error @below {{unresolved external symbol @action}}
+    transform.foreach_match in %root
+      @match -> @action : (!transform.any_op) -> !transform.any_op
+  }
+}
+
+// -----
+
+module attributes { transform.with_named_sequence } {
+  transform.named_sequence @match(%arg: !transform.any_op {transform.readonly}) {
+    // expected-error @below {{expected operations in the match part to implement MatchOpInterface}}
+    transform.test_print_remark_at_operand %arg, "remark" : !transform.any_op
+    transform.yield
+  }
+  transform.named_sequence @action() {
+    transform.yield
+  }
+
+  transform.sequence failures(propagate) {
+  ^bb0(%root: !transform.any_op):
+    transform.foreach_match in %root
+      @match -> @action : (!transform.any_op) -> !transform.any_op
+  }
+}

mlir/test/lib/Dialect/Transform/TestTransformDialectExtension.h

 // purposes.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_TESTTRANSFORMDIALECTEXTENSION_H
 #define MLIR_TESTTRANSFORMDIALECTEXTENSION_H
 
 #include "mlir/Dialect/PDL/IR/PDLTypes.h"
+#include "mlir/Dialect/Transform/IR/MatchInterfaces.h"
 #include "mlir/Dialect/Transform/IR/TransformInterfaces.h"
 #include "mlir/Dialect/Transform/IR/TransformTypes.h"
 #include "mlir/IR/OpImplementation.h"
 
 namespace mlir {
 class DialectRegistry;
 } // namespace mlir
 

mlir/test/lib/Dialect/Transform/TestTransformDialectExtension.cpp

 }
 
 void mlir::test::TestConsumeOperandOfOpKindOrFail::getEffects(
     SmallVectorImpl<MemoryEffects::EffectInstance> &effects) {
   transform::consumesHandle(getOperand(), effects);
   transform::modifiesPayload(effects);
 }
 
+DiagnosedSilenceableFailure
+mlir::test::TestSucceedIfOperandOfOpKind::matchOperation(
+    Operation *op, transform::TransformResults &results,
+    transform::TransformState &state) {
+  if (op->getName().getStringRef() != getOpKind()) {
+    return emitSilenceableError()
+           << "op expected the operand to be associated with a payload op of "
+              "kind "
+           << getOpKind() << " got " << op->getName().getStringRef();
+  }
+  return DiagnosedSilenceableFailure::success();
+}
+
+void mlir::test::TestSucceedIfOperandOfOpKind::getEffects(
+    SmallVectorImpl<MemoryEffects::EffectInstance> &effects) {
+  transform::onlyReadsHandle(getOperand(), effects);
+  transform::onlyReadsPayload(effects);
+}
+
 DiagnosedSilenceableFailure mlir::test::TestPrintRemarkAtOperandOp::apply(
     transform::TransformResults &results, transform::TransformState &state) {
   ArrayRef<Operation *> payload = state.getPayloadOps(getOperand());
   for (Operation *op : payload)
     op->emitRemark() << getMessage();
 
   return DiagnosedSilenceableFailure::success();
 }

mlir/test/lib/Dialect/Transform/TestTransformDialectExtension.td

 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_TESTTRANSFORMDIALECTEXTENSION_TD
 #define MLIR_TESTTRANSFORMDIALECTEXTENSION_TD
 
 include "mlir/Interfaces/SideEffectInterfaces.td"
 include "mlir/IR/AttrTypeBase.td"
 include "mlir/IR/OpBase.td"
+include "mlir/Dialect/Transform/IR/MatchInterfaces.td"
 include "mlir/Dialect/Transform/IR/TransformDialect.td"
 include "mlir/Dialect/Transform/IR/TransformInterfaces.td"
 include "mlir/Dialect/PDL/IR/PDLTypes.td"
 
 def TestTransformTestDialectHandleType
   : TypeDef<Transform_Dialect, "TestDialectOp",
       [DeclareTypeInterfaceMethods<TransformHandleTypeInterface>]> {
   let description = [{Handle pointing to an op from the Test dialect.}];
: Op<Transform_Dialect, "test_consume_operand_of_op_kind_or_fail",
         DeclareOpInterfaceMethods<MemoryEffectsOpInterface>]> {
   let arguments = (ins
     PDL_Operation:$operand,
     StrAttr:$op_kind);
   let assemblyFormat = "$operand `,` $op_kind attr-dict";
   let cppNamespace = "::mlir::test";
 }
 
+def TestSucceedIfOperandOfOpKind
+  : Op<Transform_Dialect, "test_succeed_if_operand_of_op_kind",
+       [MatchOpInterface,
+        SingleOpMatcher,
+        DeclareOpInterfaceMethods<MemoryEffectsOpInterface>]> {
+  let arguments = (ins
+    TransformHandleTypeInterface:$operand_handle,
+    StrAttr:$op_kind);
+  let assemblyFormat =
+      "$operand_handle `,` $op_kind attr-dict `:` type($operand_handle)";
+  let extraClassDeclaration = SingleOpMatcher.extraDeclaration;
+  let cppNamespace = "::mlir::test";
+}
+
 def TestPrintRemarkAtOperandOp
   : Op<Transform_Dialect, "test_print_remark_at_operand",
        [DeclareOpInterfaceMethods<TransformOpInterface>,
         DeclareOpInterfaceMethods<MemoryEffectsOpInterface>]> {
   let arguments = (ins
     TransformHandleTypeInterface:$operand,
     StrAttr:$message);
   let assemblyFormat =

utils/bazel/llvm-project-overlay/mlir/BUILD.bazel

tbl_outs = [
         ),
     ],
     tblgen = ":mlir-tblgen",
     td_file = "include/mlir/Dialect/Transform/IR/TransformInterfaces.td",
     deps = [":TransformDialectTdFiles"],
 )
 
 gentbl_cc_library(
+    name = "TransformDialectMatchInterfacesIncGen",
+    strip_include_prefix = "include",
+    tbl_outs = [
+        (
+            [
+                "-gen-op-interface-decls",
+            ],
+            "include/mlir/Dialect/Transform/IR/MatchInterfaces.h.inc",
+        ),
+        (
+            [
+                "-gen-op-interface-defs",
+            ],
+            "include/mlir/Dialect/Transform/IR/MatchInterfaces.cpp.inc",
+        ),
+    ],
+    tblgen = ":mlir-tblgen",
+    td_file = "include/mlir/Dialect/Transform/IR/MatchInterfaces.td",
+    deps = [
+        ":TransformDialectTdFiles",
+        ":TransformDialectInterfacesIncGen",
+    ],
+)
+
+gentbl_cc_library(
     name = "TransformDialectIncGen",
     strip_include_prefix = "include",
     tbl_outs = [
         (
             [
                 "-gen-dialect-decls",
             ],
             "include/mlir/Dialect/Transform/IR/TransformDialect.h.inc",
deps = [
         ":PDLDialect",
         ":PDLInterpDialect",
         ":Rewrite",
         ":SideEffectInterfaces",
         ":Support",
         ":TransformDialectEnumsIncGen",
         ":TransformDialectIncGen",
         ":TransformDialectInterfacesIncGen",
+        ":TransformDialectMatchInterfacesIncGen",
         ":TransformDialectUtils",
         ":TransformOpsIncGen",
         ":TransformTypesIncGen",
         ":Transforms",
         "//llvm:Support",
     ],
 )