[mlir-tblgen] Support `either` in Tablegen DRR.

[Chia-hungDuan]

Summary

Add a new directive either to specify the operands can be matched in either order

[Mogball]

Bunch of minor things, but otherwise LGTM. The nested syntax makes a lot of sense since it's restricted to binary operations.

mlir/docs/DeclarativeRewrites.md

751–752

"are marked" and "ordering"

764

typo

mlir/include/mlir/IR/OpBase.td

2688

same typo xd

mlir/lib/TableGen/Pattern.cpp

145–147

Should probably add a comment for this one.

mlir/tools/mlir-tblgen/RewriterGen.cpp

726

formatv with no arguments

739

llvm::raw_string_ostream instead?

[rriddle]

mlir/docs/DeclarativeRewrites.md

764–765

Can you reword this? I'm having trouble parsing this sentence.

mlir/lib/TableGen/Pattern.cpp

808–816

nit: If one branch has braces, all should have braces.

Also, please use braces when the body is larger than a single line/statement.

mlir/tools/mlir-tblgen/RewriterGen.cpp

481

615–623

nit: Drop else after continue/return/etc

[Chia-hungDuan]

mlir/docs/DeclarativeRewrites.md

748

BTW, I'm wondering if there's a better name for this. It may be a little bit confusing with Commutative trait. (The difference is capitalizing or not)

764–765

Sorry, my bad. Rephrase to

Only type operand is supported with `commutative` and note that an operation        
with `Commutative` trait doesn't mean its operand will be matched commtatively.  
You need to explicitly specify it.

Not sure if it's better.

mlir/include/mlir/IR/OpBase.td

2688

Sorry, my bad...

mlir/lib/TableGen/Pattern.cpp

145–147

I think this is a bug before. It's used to collect the location from each operations in the source pattern. So it should include only operation DagNode. In fact, we don't use directive like returnType in source pattern, thus we didn't see issues before.

mlir/tools/mlir-tblgen/RewriterGen.cpp

739

Here we want to delay the collection of matched operation thus I use a string for caching it. I think raw_string_ostream is similar. Or do you mean if we use raw_string_ostream, that will be more consistent with os << ... style?

[Chia-hungDuan]

Address review comment

[Mogball]

mlir/lib/TableGen/Pattern.cpp

145–147

Yeah you're right, which is why it's be nice to have a disclaimer like "don't count directives".

mlir/tools/mlir-tblgen/RewriterGen.cpp

739

For consistency

[jpienaar]

mlir/docs/DeclarativeRewrites.md

748

How about either? You don't actually care about commutativity, you are effectively expressing 2 patterns in one by allowing two adjacent trees to be matched independent of their order

751

s/have the commutative property/may be matched in either order/ ?

751

two adjacent ?

765

I'm not sure I'm following "type" here.

767

With renaming of the trait you can drop this part as the confusion will be gone :)

mlir/lib/TableGen/Pattern.cpp

145–147

Can one use returnType or location in source pattern? Or are there other cases which would result in count mismatch beyond replace with value [change looks fine, but good to document expectation here]

783–784

I think this is something not clear above: commutative (or what it will be called) results in "unpacking" from 1 node to 2 (do we verify anywhere that it is only 2? else this count need to consider that)

mlir/tools/mlir-tblgen/RewriterGen.cpp

716

This makes sense to me [well I'd be concerned about shadowing given the variable names, sometihng like ods_match_ or some such prefix to avoid accidentally shadowing].

726

Why not?

733

I'm not sure if a user would be able to understand this, could we make it easier to understand?

[Chia-hungDuan]

Address review comment and changed the directive name to either

mlir/docs/DeclarativeRewrites.md

748

Sounds Good!

765

Sorry, I want to say an operand which is not an Attribute. I'm thinking that if we should allow commutative attributes. It's doable but not sure if it's necessary(or it's reasonable).

767

True :) Thanks

mlir/lib/TableGen/Pattern.cpp

145–147

No, user can't use returnType/location in source pattern. Here we add either directive which will lead to count mismatch.

Comment added

783–784

You're right. Comment updated.

PS. I restrict the number of operand of either to be 2(checked somewhere). The reason for that is to make the codegen/verification easier.

mlir/tools/mlir-tblgen/RewriterGen.cpp

716

changed to "either_oprandX".

726

This is to make the codegen/verification easier. It's doable but so far I'm not sure if we need to support that at beginning. I would like to add that when we heard some cases that need it.

733

Changed to "There's no operation that defines operand {0} of {1}", how about this?

[jpienaar]

Looks good thanks

mlir/docs/DeclarativeRewrites.md

752

either ? (both could be that the constraints have to apply to both sides).

This sentence is confusing to me in general and I wonder if we should just skip to the example directly as I find that clear. WDYT?

759

accept

763

s/like/than/ ?

765

Arguments consists of operands and attributes, just saying operand here would do (could you change the above too?)

mlir/include/mlir/IR/OpBase.td

2688

Same as above

mlir/include/mlir/TableGen/Pattern.h

189

s/a return/an/ ?

mlir/tools/mlir-tblgen/RewriterGen.cpp

708

Do we care if the other args are attributes?

756

Lets use LLVM naming style here :) odsEiherOperand[01] ?

[Chia-hungDuan]

addressed review comment and will add more checks in the next revision.

[Chia-hungDuan]

Rebased and did minor code clean up.

[Chia-hungDuan]

Rebase only.

mlir/docs/DeclarativeRewrites.md

 
 ```tablegen
 def : Pat<(Foo $input), (replaceWithValue $input)>;
 ```
 
 The above pattern removes the `Foo` and replaces all uses of `Foo` with
 `$input`.
 
+### `either`
+
+The `either` directive is used to specify the operands may be matched in either
+order. When two adjacents are marked with `either`, it'll try to match the
+operands with both ordering of constraints. For example,
+
+```tablegen
+def : Pat<(TwoArgOp (either $firstArg, (AnOp $secondArg))),
+          (...)>;
+```
+
+The above pattern will accpet both `"test.TwoArgOp"(%I32Arg, %AnOpArg)` and
+`"test.TwoArgOp"(%AnOpArg, %I32Arg)`.
+
+Only type operand is supported with `either` and note that an operation
+with `Commutative` trait doesn't imply that it'll have the same behavior like
+`either` while pattern matching.
+
 ## Debugging Tips
 
 ### Run `mlir-tblgen` to see the generated content
 
 TableGen syntax sometimes can be obscure; reading the generated content can be a
 very helpful way to understand and debug issues. To build `mlir-tblgen`, run
 `cmake --build . --target mlir-tblgen` in your build directory and find the
 `mlir-tblgen` binary in the `bin/` subdirectory. All the supported generators
 can be found via `mlir-tblgen --help`.
 

mlir/include/mlir/IR/OpBase.td

 // (AnOp $val,
 //       (returnType (NativeCodeCall<"$_builder.getTupleType({$0})"> $val)));
 // ```
 //
 // Specify multiple return types with multiple of any of the above.
 
 def returnType;
 
+// Directive used to specify the operands may be matched in either order. When
+// two adjacents are marked with `either`, it'll try to match the operands in
+// both ordering of constraints. Example:
+//
+// ```
+// (TwoArgOp (either $firstArg, (AnOp $secondArg)))
+// ```
+// The above pattern will accept both `"test.TwoArgOp"(%I32Arg, %AnOpArg)` and
+// `"test.TwoArgOp"(%AnOpArg, %I32Arg)`.
+//
+// Only type operand is supported with `either` and note that an operation
+// with `Commutative` trait doesn't imply that it'll have the same behavior like
+// `either` while pattern matching.
+def either;
+
 //===----------------------------------------------------------------------===//
 // Attribute and Type generation
 //===----------------------------------------------------------------------===//
 
 // Class for defining a custom getter.
 //
 // TableGen generates several generic getter methods for each attribute and type
 // by default, corresponding to the specified dag parameters. If the default

mlir/include/mlir/TableGen/Pattern.h

public:
   bool isLocationDirective() const;
 
   // Returns whether this DAG is a return type specifier.
   bool isReturnTypeDirective() const;
 
   // Returns true if this DAG node is wrapping native code call.
   bool isNativeCodeCall() const;
 
+  // Returns whether this DAG is a return `either` specifier.
+  bool isEither() const;
+
   // Returns true if this DAG node is an operation.
   bool isOperation() const;
 
   // Returns the native code call template inside this DAG node.
   // Precondition: isNativeCodeCall()
   StringRef getNativeCodeTemplate() const;
 
   // Returns the number of values will be returned by the native helper

mlir/lib/TableGen/Pattern.cpp

 bool DagNode::isNativeCodeCall() const {
   if (auto *defInit = dyn_cast_or_null<llvm::DefInit>(node->getOperator()))
     return defInit->getDef()->isSubClassOf("NativeCodeCall");
   return false;
 }
 
 bool DagNode::isOperation() const {
   return !isNativeCodeCall() && !isReplaceWithValue() &&
-         !isLocationDirective() && !isReturnTypeDirective();
+         !isLocationDirective() && !isReturnTypeDirective() && !isEither();
 }
 
 llvm::StringRef DagNode::getNativeCodeTemplate() const {
   assert(isNativeCodeCall() && "the DAG leaf must be NativeCodeCall");
   return cast<llvm::DefInit>(node->getOperator())
       ->getDef()
       ->getValueAsString("expression");
 }
Operator &DagNode::getDialectOp(RecordOperatorMap *mapper) const {
   auto it = mapper->find(opDef);
   if (it != mapper->end())
     return *it->second;
   return *mapper->try_emplace(opDef, std::make_unique<Operator>(opDef))
               .first->second;
 }
 
 int DagNode::getNumOps() const {
-  int count = isReplaceWithValue() ? 0 : 1;
+  // We want to get number of operations recursively involved in the DAG tree.
+  // All other directives should be excluded.
+  int count = isOperation() ? 1 : 0;
   for (int i = 0, e = getNumArgs(); i != e; ++i) {
     if (auto child = getArgAsNestedDag(i))
       count += child.getNumOps();
   }
   return count;
 }
 
 int DagNode::getNumArgs() const { return node->getNumArgs(); }
bool DagNode::isLocationDirective() const {
   return dagOpDef->getName() == "location";
 }
 
 bool DagNode::isReturnTypeDirective() const {
   auto *dagOpDef = cast<llvm::DefInit>(node->getOperator())->getDef();
   return dagOpDef->getName() == "returnType";
 }
 
+bool DagNode::isEither() const {
+  auto *dagOpDef = cast<llvm::DefInit>(node->getOperator())->getDef();
+  return dagOpDef->getName() == "either";
+}
+
 void DagNode::print(raw_ostream &os) const {
   if (node)
     node->print(os);
 }
 
 //===----------------------------------------------------------------------===//
 // SymbolInfoMap
 //===----------------------------------------------------------------------===//
if (tree.isNativeCodeCall()) {
     }
 
     return;
   }
 
   if (tree.isOperation()) {
     auto &op = getDialectOp(tree);
     auto numOpArgs = op.getNumArgs();
+    int numEither = 0;
 
-    // The pattern might have trailing directives.
+    // We need to exclude the trailing directives and `either` directive groups
+    // two operands of the operation.
     int numDirectives = 0;
     for (int i = numTreeArgs - 1; i >= 0; --i) {
       if (auto dagArg = tree.getArgAsNestedDag(i)) {
         if (dagArg.isLocationDirective() || dagArg.isReturnTypeDirective())
           ++numDirectives;
-        else
-          break;
+        else if (dagArg.isEither())
+          ++numEither;
       }
     }
 
-    if (numOpArgs != numTreeArgs - numDirectives) {
-      auto err = formatv("op '{0}' argument number mismatch: "
-                         "{1} in pattern vs. {2} in definition",
-                         op.getOperationName(), numTreeArgs, numOpArgs);
+    if (numOpArgs != numTreeArgs - numDirectives + numEither) {
+      auto err =
+          formatv("op '{0}' argument number mismatch: "
+                  op.getOperationName(), numTreeArgs + numEither, numOpArgs);
       PrintFatalError(&def, err);
     }
 
     // The name attached to the DAG node's operator is for representing the
     // results generated from this op. It should be remembered as bound results.
     if (!treeName.empty()) {
       LLVM_DEBUG(llvm::dbgs()
                  << "found symbol bound to op result: " << treeName << '\n');
       verifyBind(infoMap.bindOpResult(treeName, op), treeName);
     }
 
-    for (int i = 0; i != numTreeArgs; ++i) {
+    // The operand in `either` DAG should be bound to the operation in the
+    // parent DagNode.
+    auto collectSymbolInEither = [&](DagNode parent, DagNode tree, int &opArg) {
+      for (int i = 0; i < 2; ++i, ++opArg) {
+        if (DagNode subTree = tree.getArgAsNestedDag(i)) {
+          collectBoundSymbols(subTree, infoMap, isSrcPattern);
+        } else {
+          auto argName = tree.getArgName(i);
+          if (!argName.empty() && argName != "_")
+            verifyBind(infoMap.bindOpArgument(parent, argName, op, opArg),
+                       argName);
+        }
+      }
+    };
+
+    for (int i = 0, opArg = 0; i != numTreeArgs; ++i, ++opArg) {
       if (auto treeArg = tree.getArgAsNestedDag(i)) {
+        if (treeArg.isEither())
+          collectSymbolInEither(tree, treeArg, opArg);
+        else
           // This DAG node argument is a DAG node itself. Go inside recursively.
           collectBoundSymbols(treeArg, infoMap, isSrcPattern);
         continue;
       }
 
       if (isSrcPattern) {
         // We can only bind symbols to op arguments in source pattern. Those
         // symbols are referenced in result patterns.
         auto treeArgName = tree.getArgName(i);
         // `$_` is a special symbol meaning ignore the current argument.
         if (!treeArgName.empty() && treeArgName != "_") {
           LLVM_DEBUG(llvm::dbgs() << "found symbol bound to op argument: "
                                   << treeArgName << '\n');
-          verifyBind(infoMap.bindOpArgument(tree, treeArgName, op, i),
+          verifyBind(infoMap.bindOpArgument(tree, treeArgName, op, opArg),
                      treeArgName);
         }
       }
     }
     return;
   }
 
   if (!treeName.empty()) {
     PrintFatalError(
         &def, formatv("binding symbol '{0}' to non-operation/native code call "
                       "unsupported right now",
                       treeName));
   }
   return;
 }

mlir/test/lib/Dialect/Test/TestOps.td

 def : Pat<(OneI32ResultOp),
           (MixedVOperandOp3
               (MixedVResultOp3:$results__0 ConstantAttr<I32Attr, "2">),
               (replaceWithValue $results__1),
               (replaceWithValue $results__2),
               ConstantAttr<I32Attr, "2">)>;
 
 //===----------------------------------------------------------------------===//
+// Test Patterns (either)
+
+def TestEitherOpA : TEST_Op<"either_op_a"> {
+  let arguments = (ins AnyInteger:$arg0, AnyInteger:$arg1, AnyInteger:$arg2);
+  let results = (outs I32:$output);
+}
+
+def TestEitherOpB : TEST_Op<"either_op_b"> {
+  let arguments = (ins AnyInteger:$arg0);
+  let results = (outs I32:$output);
+}
+
+def : Pat<(TestEitherOpA (either I32:$arg1, I16:$arg2), $_),
+          (TestEitherOpB $arg2)>;
+
+def : Pat<(TestEitherOpA (either (TestEitherOpB I32:$arg1), I16:$arg2), $_),
+          (TestEitherOpB $arg2)>;
+
+def : Pat<(TestEitherOpA (either (TestEitherOpB I32:$arg1),
+                                 (TestEitherOpB I16:$arg2)),
+                          $_),
+          (TestEitherOpB $arg2)>;
+
+//===----------------------------------------------------------------------===//
 // Test Patterns (Location)
 
 // Test that we can specify locations for generated ops.
 def : Pat<(TestLocationSrcOp:$res1
            (TestLocationSrcOp:$res2
             (TestLocationSrcOp:$res3 $input))),
           (TestLocationDstOp
             (TestLocationDstOp

mlir/test/mlir-tblgen/pattern.mlir

 // CHECK-LABEL: redundantTest
 func @redundantTest(%arg0: i32) -> i32 {
   %0 = "test.op_m"(%arg0) : (i32) -> i32
   // CHECK: "test.op_m"(%arg0) {optional_attr = 314159265 : i32} : (i32) -> i32
   return %0 : i32
 }
 
 //===----------------------------------------------------------------------===//
+// Test either directive
+//===----------------------------------------------------------------------===//
+
+// CHECK: @either_dag_leaf_only
+func @either_dag_leaf_only_1(%arg0 : i32, %arg1 : i16, %arg2 : i8) -> () {
+  // CHECK: "test.either_op_b"(%arg1) : (i16) -> i32
+  %0 = "test.either_op_a"(%arg0, %arg1, %arg2) : (i32, i16, i8) -> i32
+  // CHECK: "test.either_op_b"(%arg1) : (i16) -> i32
+  %1 = "test.either_op_a"(%arg1, %arg0, %arg2) : (i16, i32, i8) -> i32
+  return
+}
+
+// CHECK: @either_dag_leaf_dag_node
+func @either_dag_leaf_dag_node(%arg0 : i32, %arg1 : i16, %arg2 : i8) -> () {
+  %0 = "test.either_op_b"(%arg0) : (i32) -> i32
+  // CHECK: "test.either_op_b"(%arg1) : (i16) -> i32
+  %1 = "test.either_op_a"(%0, %arg1, %arg2) : (i32, i16, i8) -> i32
+  // CHECK: "test.either_op_b"(%arg1) : (i16) -> i32
+  %2 = "test.either_op_a"(%arg1, %0, %arg2) : (i16, i32, i8) -> i32
+  return
+}
+
+// CHECK: @either_dag_node_dag_node
+func @either_dag_node_dag_node(%arg0 : i32, %arg1 : i16, %arg2 : i8) -> () {
+  %0 = "test.either_op_b"(%arg0) : (i32) -> i32
+  %1 = "test.either_op_b"(%arg1) : (i16) -> i32
+  // CHECK: "test.either_op_b"(%arg1) : (i16) -> i32
+  %2 = "test.either_op_a"(%0, %1, %arg2) : (i32, i32, i8) -> i32
+  // CHECK: "test.either_op_b"(%arg1) : (i16) -> i32
+  %3 = "test.either_op_a"(%1, %0, %arg2) : (i32, i32, i8) -> i32
+  return
+}
+
+//===----------------------------------------------------------------------===//
 // Test that ops without type deduction can be created with type builders.
 //===----------------------------------------------------------------------===//
 
 func @explicitReturnTypeTest(%arg0 : i64) -> i8 {
   %0 = "test.source_op"(%arg0) {tag = 11 : i32} : (i64) -> i8
   // CHECK: "test.op_x"(%arg0) : (i64) -> i32
   // CHECK: "test.op_x"(%0) : (i32) -> i8
   return %0 : i8

mlir/tools/mlir-tblgen/RewriterGen.cpp

private:
   // Emits C++ statements for matching using a native code call.
   void emitNativeCodeMatch(DagNode tree, StringRef name, int depth);
 
   // Emits C++ statements for matching the op constrained by the given DAG
   // `tree` returning the op's variable name.
   void emitOpMatch(DagNode tree, StringRef opName, int depth);
 
   // Emits C++ statements for matching the `argIndex`-th argument of the given
-  // DAG `tree` as an operand. operandIndex is the index in the DAG excluding
-  // the preceding attributes.
-  void emitOperandMatch(DagNode tree, StringRef opName, int argIndex,
-                        int operandIndex, int depth);
+  // DAG `tree` as an operand. `operandName` and `operandMatcher` indicate the
+  // bound name and the constraint of the operand respectively.
+  void emitOperandMatch(DagNode tree, StringRef opName, StringRef operandName,
+                        DagLeaf operandMatcher, StringRef argName,
+                        int argIndex);
+
+  // Emits C++ statements for matching the operands which can be matched in
+  // either order.
+  void emitEitherOperandMatch(DagNode tree, DagNode eitherArgTree,
+                              StringRef opName, int argIndex, int &operandIndex,
+                              int depth);
 
   // Emits C++ statements for matching the `argIndex`-th argument of the given
   // DAG `tree` as an attribute.
   void emitAttributeMatch(DagNode tree, StringRef opName, int argIndex,
                           int depth);
 
   // Emits C++ for checking a match with a corresponding match failure
   // diagnostic.
void PatternEmitter::emitNativeCodeMatch(DagNode tree, StringRef opName,
   // names.
   SmallVector<std::string, 8> capture;
 
   raw_indented_ostream::DelimitedScope scope(os);
 
   for (int i = 0, e = tree.getNumArgs(); i != e; ++i) {
     std::string argName = formatv("arg{0}_{1}", depth, i);
     if (DagNode argTree = tree.getArgAsNestedDag(i)) {
+      if (argTree.isEither())
+        PrintFatalError(loc, "NativeCodeCall cannot have `either` operands");
+
       os << "Value " << argName << ";\n";
     } else {
       auto leaf = tree.getArgAsLeaf(i);
       if (leaf.isAttrMatcher() || leaf.isConstantAttr()) {
         os << "Attribute " << argName << ";\n";
       } else {
         os << "Value " << argName << ";\n";
       }
os << formatv("auto {0} = ::llvm::dyn_cast<{2}>({1}); "
                 castedName, opName, op.getQualCppClassName());
 
   // Skip the operand matching at depth 0 as the pattern rewriter already does.
   if (depth != 0)
     emitMatchCheck(opName, /*matchStr=*/castedName,
                    formatv("\"{0} is not {1} type\"", castedName,
                            op.getQualCppClassName()));
 
-  if (tree.getNumArgs() != op.getNumArgs())
-    PrintFatalError(loc, formatv("op '{0}' argument number mismatch: {1} in "
-                                 "pattern vs. {2} in definition",
-                                 op.getOperationName(), tree.getNumArgs(),
-                                 op.getNumArgs()));
-
   // If the operand's name is set, set to that variable.
   auto name = tree.getSymbol();
   if (!name.empty())
     os << formatv("{0} = {1};\n", name, castedName);
 
   for (int i = 0, e = tree.getNumArgs(), nextOperand = 0; i != e; ++i) {
     auto opArg = op.getArg(i);
     std::string argName = formatv("op{0}", depth + 1);
 
     // Handle nested DAG construct first
     if (DagNode argTree = tree.getArgAsNestedDag(i)) {
+      if (argTree.isEither()) {
+        emitEitherOperandMatch(tree, argTree, castedName, i, nextOperand,
+                               depth);
+        continue;
+      }
       if (auto *operand = opArg.dyn_cast<NamedTypeConstraint *>()) {
         if (operand->isVariableLength()) {
           auto error = formatv("use nested DAG construct to match op {0}'s "
                                "variadic operand #{1} unsupported now",
                                op.getOperationName(), i);
           PrintFatalError(loc, error);
         }
       }
+
       os << "{\n";
 
       // Attributes don't count for getODSOperands.
       // TODO: Operand is a Value, check if we should remove `getDefiningOp()`.
       os.indent() << formatv(
           "auto *{0} = "
           "(*{1}.getODSOperands({2}).begin()).getDefiningOp();\n",
           argName, castedName, nextOperand);
       // Null check of operand's definingOp
-      emitMatchCheck(castedName, /*matchStr=*/argName,
-                     formatv("\"Operand {0} of {1} has null definingOp\"",
-                             nextOperand++, castedName));
+      emitMatchCheck(
+          castedName, /*matchStr=*/argName,
+          formatv("\"There's no operation that defines operand {0} of {1}\"",
       emitMatch(argTree, argName, depth + 1);
       os << formatv("tblgen_ops.push_back({0});\n", argName);
       os.unindent() << "}\n";
       continue;
     }
 
     // Next handle DAG leaf: operand or attribute
     if (opArg.is<NamedTypeConstraint *>()) {
-      // emitOperandMatch's argument indexing counts attributes.
-      emitOperandMatch(tree, castedName, i, nextOperand, depth);
+      auto operandName =
+          formatv("{0}.getODSOperands({1})", castedName, nextOperand);
+      emitOperandMatch(tree, castedName, operandName.str(),
+                       /*operandMatcher=*/tree.getArgAsLeaf(i),
+                       /*argName=*/tree.getArgName(i),
+                       /*argIndex=*/i);
       ++nextOperand;
     } else if (opArg.is<NamedAttribute *>()) {
       emitAttributeMatch(tree, opName, i, depth);
     } else {
       PrintFatalError(loc, "unhandled case when matching op");
     }
   }
   LLVM_DEBUG(llvm::dbgs() << "done emitting match for op '"
                           << op.getOperationName() << "' at depth " << depth
                           << '\n');
 }
 
 void PatternEmitter::emitOperandMatch(DagNode tree, StringRef opName,
-                                      int argIndex, int operandIndex,
-                                      int depth) {
+                                      StringRef operandName,
+                                      DagLeaf operandMatcher, StringRef argName,
+                                      int argIndex) {
   Operator &op = tree.getDialectOp(opMap);
   auto *operand = op.getArg(argIndex).get<NamedTypeConstraint *>();
-  auto matcher = tree.getArgAsLeaf(argIndex);
 
   // If a constraint is specified, we need to generate C++ statements to
   // check the constraint.
-  if (!matcher.isUnspecified()) {
-    if (!matcher.isOperandMatcher()) {
+  if (!operandMatcher.isUnspecified()) {
+    if (!operandMatcher.isOperandMatcher())
       PrintFatalError(
           loc, formatv("the {1}-th argument of op '{0}' should be an operand",
                        op.getOperationName(), argIndex + 1));
-    }
 
     // Only need to verify if the matcher's type is different from the one
     // of op definition.
-    Constraint constraint = matcher.getAsConstraint();
+    Constraint constraint = operandMatcher.getAsConstraint();
     if (operand->constraint != constraint) {
       if (operand->isVariableLength()) {
         auto error = formatv(
             "further constrain op {0}'s variadic operand #{1} unsupported now",
             op.getOperationName(), argIndex);
         PrintFatalError(loc, error);
       }
-      auto self = formatv("(*{0}.getODSOperands({1}).begin()).getType()",
-                          opName, operandIndex);
+      auto self = formatv("(*{0}.begin()).getType()", operandName);
       StringRef verifier = staticMatcherHelper.getVerifierName(constraint);
       emitStaticVerifierCall(
           verifier, opName, self.str(),
           formatv(
               "\"operand {0} of op '{1}' failed to satisfy constraint: '{2}'\"",
               operand - op.operand_begin(), op.getOperationName(),
               constraint.getSummary())
               .str());
     }
   }
 
   // Capture the value
-  auto name = tree.getArgName(argIndex);
   // `$_` is a special symbol to ignore op argument matching.
-  if (!name.empty() && name != "_") {
-    // We need to subtract the number of attributes before this operand to get
-    // the index in the operand list.
-    auto numPrevAttrs = std::count_if(
-        op.arg_begin(), op.arg_begin() + argIndex,
-        [](const Argument &arg) { return arg.is<NamedAttribute *>(); });
-
-    auto res = symbolInfoMap.findBoundSymbol(name, tree, op, argIndex);
-    os << formatv("{0} = {1}.getODSOperands({2});\n",
-                  res->second.getVarName(name), opName,
-                  argIndex - numPrevAttrs);
-  }
+  if (!argName.empty() && argName != "_") {
+    auto res = symbolInfoMap.findBoundSymbol(argName, tree, op, argIndex);
+    os << formatv("{0} = {1};\n", res->second.getVarName(argName), operandName);
+  }
+
+void PatternEmitter::emitEitherOperandMatch(DagNode tree, DagNode eitherArgTree,
+                                            StringRef opName, int argIndex,
+                                            int &operandIndex, int depth) {
+  if (eitherArgTree.getNumArgs() != 2)
+    PrintFatalError(loc, "`either` only supports grouping two operands");
+
+  Operator &op = tree.getDialectOp(opMap);
+
+  std::string codeBuffer;
+  llvm::raw_string_ostream tblgenOps(codeBuffer);
+
+  std::string lambda = formatv("eitherLambda{0}", depth);
+  os << formatv("auto {0} = [&](OperandRange v0, OperandRange v1) {{\n",
+                lambda);
+
+  os.indent();
+
+  for (int i = 0; i < 2; ++i, ++argIndex) {
+    if (DagNode argTree = eitherArgTree.getArgAsNestedDag(i)) {
+      if (argTree.isEither())
+        PrintFatalError(loc, "either cannot be nested");
+
+      std::string argName = formatv("local_op_{0}", i).str();
+
+      os << formatv("auto {0} = (*v{1}.begin()).getDefiningOp();\n", argName,
+                    i);
+      emitMatchCheck(
+          opName, /*matchStr=*/argName,
+          formatv("\"There's no operation that defines operand {0} of {1}\"",
+                  operandIndex++, opName));
+      emitMatch(argTree, argName, depth + 1);
+      // `tblgen_ops` is used to collect the matched operations. In either, we
+      // need to queue the operation only if the matching success. Thus we emit
+      // the code at the end.
+      tblgenOps << formatv("tblgen_ops.push_back({0});\n", argName);
+    } else if (op.getArg(argIndex).is<NamedTypeConstraint *>()) {
+      emitOperandMatch(tree, opName, /*operandName=*/formatv("v{0}", i).str(),
+                       /*operandMatcher=*/eitherArgTree.getArgAsLeaf(i),
+                       /*argName=*/eitherArgTree.getArgName(i), argIndex);
+      ++operandIndex;
+    } else
+      PrintFatalError(loc, "either can only be applied on type operand");
+  }
+
+  os << tblgenOps.str();
+  os << "return success();\n";
+  os.unindent() << "};\n";
+
+  os << "{\n";
+  os.indent();
+
+  os << formatv("auto either_operand0 = {0}.getODSOperands({1});\n", opName,
+                operandIndex - 2);
+  os << formatv("auto either_operand1 = {0}.getODSOperands({1});\n", opName,
+                operandIndex - 1);
+
+  os << formatv("if(failed({0}(either_operand0, either_operand1)) && "
+                "failed({0}(either_operand1, "
+                "either_operand0)))\n",
+                lambda);
+  os.indent() << "return failure();\n";
+
+  os.unindent().unindent() << "}\n";
 }
 
 void PatternEmitter::emitAttributeMatch(DagNode tree, StringRef opName,
                                         int argIndex, int depth) {
   Operator &op = tree.getDialectOp(opMap);
   auto *namedAttr = op.getArg(argIndex).get<NamedAttribute *>();
   const auto &attr = namedAttr->attr;