[tablegen][globalisel] Add support for nested instruction matching.

[dsanders]

Summary

Lift the restrictions that prevented the tree walking introduced in the
previous change and add support for patterns like:

(G_ADD (G_MUL (G_SEXT $src1), (G_SEXT $src2)), $src3) -> SMADDWrrr $dst, $src1, $src2, $src3

Also adds support for G_SEXT and G_ZEXT to support these cases.

One particular aspect of this that I should draw attention to is that I've
tried to be overly conservative in determining the safety of matches that
involve non-adjacent instructions and multiple basic blocks. This is intended
to be used as a cheap initial check and we may add a more expensive check in
the future. The current rules are:

• Reject if any instruction may load/store (we'd need to check for intervening memory operations.
• Reject if any instruction has implicit operands.
• Reject if any instruction has unmodelled side-effects.

See isObviouslySafeToFold().

[dsanders]

A small improvement to the isObviouslySafeToFold() check. There's no need to
check the root instruction since it isn't moving.

[kristof.beyls]

test/CodeGen/AArch64/GlobalISel/arm64-instructionselect-muladd.mir

2–4

I'm not sure if we need all 3 run lines for this specific test?
I don't see and of the IOS, LINUX-DEFAULT or LINUX-PIC check prefixes being used in this test, implying that there is no difference in expected behaviour for these environments, for this test.
Maybe best not to copy paste the 3 run lines into many different tests, to avoid unnecessarily increasing the number of processes needed to run the regression tests?
This question probably applies to the other newly added tests in this patch too.

6–7

I guess these comment lines can be dropped, given this is a test file specifically for muladd patterns?

utils/TableGen/GlobalISelEmitter.cpp

720

The other derived classes have a comment explaining what their intent roughly is. This one probably also should have a comment.

1052–1085

I was looking for a tablegen-regression test to understand the intended tablegen codegen changes, but I didn't find one in this patch. I guess we don't have tablegen backend regression tests yet?
The comment above makes me think that we really should have them, and maybe this patch is about the right time to create that?
I'm thinking about the input for a test being a small piece of tablegen, and the output being checked against being the generated C++ code by this backend.
I think that the complexity of this tablegen backend is slowly becoming too high to test it well using just users of that tablegen backend, like the AArch64 instruction selector.
I think I saw a similar comment in an earlier patch in this area, but I'm not sure what the conclusion was?

Does creating tablegen backend regression tests seem sensible, useful, and needed here?
If there isn't a framework yet for creating such tests, could you use some help in trying to create an initial framework for such tests?

[dsanders]

test/CodeGen/AArch64/GlobalISel/arm64-instructionselect-muladd.mir

2–4

Ok, I'll cut this down to one RUN line.

It also applies to the xor one from an earlier patch.

6–7

Yep :-). I've been copying the main test and editing it from there and have forgotten about the comments.

utils/TableGen/GlobalISelEmitter.cpp

720

Ok.

1052–1085

We have test/TableGen/GlobalISelEmitter.td but I'll add something there. However, it won't be able to test the detail of this comment since it's talking about the requirements of a more precise version of isObviouslySafeToFold().

The testing for the detail of this fixme is best done in test/CodeGen/AArch64/GlobalISel/arm64-instructionselect-*.mir by adding some unsafe cases and testing that they don't match.

[dsanders]

Add requested comments and test case. Removed unnecessary RUN lines and out of date comments.

[dsanders]

Add requested comments and test case. Removed unnecessary RUN lines and out of date comments.

Nearly forgot to mention it, also fixed an off-by-one error where it wouldn't call isObviouslySafeToFold() for two-insn patterns.

[kristof.beyls]

Thanks for the updates, Daniel!
I don't have further remarks, but I think it's best if someone who understands the details better (like @ab ?) would also have a look.

test/TableGen/GlobalISelEmitter.td

134

Thanks very much for this test. I find the test also works well as documentation for what the expected generated code is for a simple piece of tablegen input.
I'm assuming that this is the single test file that drives code coverage statistics at http://llvm.org/reports/coverage/utils/TableGen/GlobalISelEmitter.cpp.gcov.html. I was already happily surprised to see so much line coverage there. It seems only error reporting isn't well covered by this test file.

[dsanders]

Refresh and ping.
No longer selects code for dead intermediates due to r298224

[rovka]

lib/Target/AArch64/AArch64InstructionSelector.cpp

938

Aren't these handled by TableGen now?

test/CodeGen/AArch64/GlobalISel/select-xor.mir

1

Why is this change necessary?

utils/TableGen/GlobalISelEmitter.cpp

289

Any reason why this needs to be [...]ForOperand instead of just emitCxxCaptureStmts?

655

This TODO should be obsolete now.

[dsanders]

lib/Target/AArch64/AArch64InstructionSelector.cpp

938

Good point. I've forgotten to delete the C++ implementation

test/CodeGen/AArch64/GlobalISel/select-xor.mir

1

I think this appeared as a result rebasing over an upstream change but it shows up in my local copy of this patch too. I'll undo it.

utils/TableGen/GlobalISelEmitter.cpp

289

I don't recall a good reason for this. I think I did it to make it easier to navigate around the source.

655

Thanks for noticing this. I'll remove it.

[ab]

Assuming Kristof and Diana agree, LGTM with Diana's comments (and a couple more of my own) addressed.

test/CodeGen/AArch64/GlobalISel/arm64-instructionselect-muladd.mir

1

Rename the tests to match the others, "test/CodeGen/AArch64/select-*.mir" ?

10

Stale comment?

test/CodeGen/AArch64/GlobalISel/arm64-instructionselect-sext.mir

6

We already have select-int-ext.mir. Can you keep the tests together? (there are enough to keep them in separate files now, though)

12

-> sext_s32_s16_gpr to match the operand order? (and more importantly, the existing tests!)

test/CodeGen/AArch64/GlobalISel/select-xor.mir

1

Can you fix the new tests as well?

utils/TableGen/GlobalISelEmitter.cpp

289

Can you undo it?

[ab]

test/TableGen/GlobalISelEmitter.td

85

On second thought, I'm not sure this is sufficient: don't we need to merge the memops?

[dsanders]

lib/Target/AArch64/AArch64InstructionSelector.cpp

938

It turns out that these are still doing something useful. They're needed for the sext_inreg/zext_inreg operator from SelectionDAG since this hasn't been mapped to GlobalISel yet

test/CodeGen/AArch64/GlobalISel/arm64-instructionselect-sext.mir

6

I've merged these tests in with the recently-added select-int-ext.mir tests.

12

Both orders make sense from different perspectives (mine was derived from LLVM-IR's sext/zext instruction) but I've renamed mine to match the ones that were recently committed.

test/TableGen/GlobalISelEmitter.td

85

I spotted another issue with this yesterday. It's unusual but some targets may choose to lower a load to a non-load and in this case we shouldn't copy the memory operands across otherwise the MachineVerifier will object.

I'll have a quick look at merging the operands.

[dsanders]

test/TableGen/GlobalISelEmitter.td

85

I've made a minor change to make it merge memops from all input instructions and committed.

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

protected:
   // constrain individual registers, like fast-isel.
   bool constrainSelectedInstRegOperands(MachineInstr &I,
                                         const TargetInstrInfo &TII,
                                         const TargetRegisterInfo &TRI,
                                         const RegisterBankInfo &RBI) const;
 
   bool isOperandImmEqual(const MachineOperand &MO, int64_t Value,
                          const MachineRegisterInfo &MRI) const;
+
+  bool isObviouslySafeToFold(MachineInstr &MI) const;
 };
 
 } // End namespace llvm.
 
 #endif

include/llvm/Target/GlobalISel/SelectionDAGCompat.td

 // Declare that a generic Instruction is 'equivalent' to an SDNode, that is,
 // SelectionDAG patterns involving the SDNode can be transformed to match the
 // Instruction instead.
 class GINodeEquiv<Instruction i, SDNode node> {
   Instruction I = i;
   SDNode Node = node;
 }
 
+def : GINodeEquiv<G_ZEXT, zext>;
+def : GINodeEquiv<G_SEXT, sext>;
 def : GINodeEquiv<G_ADD, add>;
 def : GINodeEquiv<G_SUB, sub>;
 def : GINodeEquiv<G_MUL, mul>;
 
 def : GINodeEquiv<G_OR, or>;
 def : GINodeEquiv<G_XOR, xor>;
 def : GINodeEquiv<G_AND, and>;
 

lib/CodeGen/GlobalISel/InstructionSelector.cpp

if (MO.isReg()) {
     assert(Def->getOperand(1).isCImm() &&
            "G_CONSTANT values must be constants");
     const ConstantInt &Imm = *Def->getOperand(1).getCImm();
     return Imm.getBitWidth() <= 64 && Imm.getSExtValue() == Value;
   }
 
   return false;
 }
+
+bool InstructionSelector::isObviouslySafeToFold(MachineInstr &MI) const {
+  return !MI.mayLoadOrStore() && !MI.hasUnmodeledSideEffects() &&
+         MI.implicit_operands().begin() == MI.implicit_operands().end();
+}

lib/Target/AArch64/AArch64InstructionSelector.cpp

case TargetOpcode::G_UMULH: {
     unsigned NewOpc = I.getOpcode() == TargetOpcode::G_SMULH ? AArch64::SMULHrr
                                                              : AArch64::UMULHrr;
     I.setDesc(TII.get(NewOpc));
 
     // Now that we selected an opcode, we need to constrain the register
     // operands to use appropriate classes.
     return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
   }
-  case TargetOpcode::G_MUL: {
-    // Reject the various things we don't support yet.
-    if (unsupportedBinOp(I, RBI, MRI, TRI))
-      return false;
-
-    const unsigned DefReg = I.getOperand(0).getReg();
-    const RegisterBank &RB = *RBI.getRegBank(DefReg, MRI, TRI);
-
-    if (RB.getID() != AArch64::GPRRegBankID) {
-      DEBUG(dbgs() << "G_MUL on bank: " << RB << ", expected: GPR\n");
-      return false;
-    }
-
-    unsigned ZeroReg;
-    unsigned NewOpc;
-    if (Ty.isScalar() && Ty.getSizeInBits() <= 32) {
-      NewOpc = AArch64::MADDWrrr;
-      ZeroReg = AArch64::WZR;
-    } else if (Ty == LLT::scalar(64)) {
-      NewOpc = AArch64::MADDXrrr;
-      ZeroReg = AArch64::XZR;
-    } else {
-      DEBUG(dbgs() << "G_MUL has type: " << Ty << ", expected: "
-                   << LLT::scalar(32) << " or " << LLT::scalar(64) << '\n');
-      return false;
-    }
-
-    I.setDesc(TII.get(NewOpc));
-
-    I.addOperand(MachineOperand::CreateReg(ZeroReg, /*isDef=*/false));
-
-    // Now that we selected an opcode, we need to constrain the register
-    // operands to use appropriate classes.
-    return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
-  }
-
   case TargetOpcode::G_FADD:
   case TargetOpcode::G_FSUB:
   case TargetOpcode::G_FMUL:
   case TargetOpcode::G_FDIV:
 
   case TargetOpcode::G_OR:
   case TargetOpcode::G_SHL:
   case TargetOpcode::G_LSHR:
if (DstSize > 32) {
           .addUse(SrcReg)
           .addImm(AArch64::sub_32);
       I.getOperand(1).setReg(ExtSrc);
     }
     return selectCopy(I, TII, MRI, TRI, RBI);
   }
 
   case TargetOpcode::G_ZEXT:
   case TargetOpcode::G_SEXT: {
     unsigned Opcode = I.getOpcode();
     const LLT DstTy = MRI.getType(I.getOperand(0).getReg()),
               SrcTy = MRI.getType(I.getOperand(1).getReg());
     const bool isSigned = Opcode == TargetOpcode::G_SEXT;
     const unsigned DefReg = I.getOperand(0).getReg();
     const unsigned SrcReg = I.getOperand(1).getReg();
     const RegisterBank &RB = *RBI.getRegBank(DefReg, MRI, TRI);
 

test/CodeGen/AArch64/GlobalISel/arm64-instructionselect-muladd.mir

+# RUN: llc -O0 -mtriple=aarch64-linux-gnu -run-pass=instruction-select -verify-machineinstrs -global-isel %s -o - | FileCheck %s
+
+--- |
+  target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+  define void @SMADDLrrr_gpr() { ret void }
+...
+
+---
+#  =>  (SMADDLrrr:i64 GPR32:i32:$Rn, GPR32:i32:$Rm, GPR64:i64:$Ra)
+
+# CHECK-LABEL: name: SMADDLrrr_gpr
+name:            SMADDLrrr_gpr
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr64 }
+# CHECK-NEXT:  - { id: 1, class: gpr32 }
+# CHECK-NEXT:  - { id: 2, class: gpr32 }
+# CHECK-NEXT:  - { id: 3, class: gpr }
+# CHECK-NEXT:  - { id: 4, class: gpr }
+# CHECK-NEXT:  - { id: 5, class: gpr }
+# CHECK-NEXT:  - { id: 6, class: gpr64 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+  - { id: 2, class: gpr }
+  - { id: 3, class: gpr }
+  - { id: 4, class: gpr }
+  - { id: 5, class: gpr }
+  - { id: 6, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %x0
+# CHECK:    %1 = COPY %w1
+# CHECK:    %2 = COPY %w2
+# CHECK:    %6 = SMADDLrrr %1, %2, %0
+body:             |
+  bb.0:
+    liveins: %x0, %w1, %w2
+
+    %0(s64) = COPY %x0
+    %1(s32) = COPY %w1
+    %2(s32) = COPY %w2
+    %3(s64) = G_SEXT %1
+    %4(s64) = G_SEXT %2
+    %5(s64) = G_MUL %3, %4
+    %6(s64) = G_ADD %0, %5
+    %x0 = COPY %6
+...
+

test/CodeGen/AArch64/GlobalISel/arm64-instructionselect-sext.mir

+# RUN: llc -O0 -mtriple=aarch64-linux-gnu -run-pass=instruction-select -verify-machineinstrs -global-isel %s -o - | FileCheck %s
+
+--- |
+  target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+  define void @sext_s16_s32_gpr() { ret void }
+  define void @sext_s32_s64_gpr() { ret void }
+
+...
+
+---
+# CHECK-LABEL: name: sext_s16_s32_gpr
+name:            sext_s16_s32_gpr
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr32 }
+# CHECK-NEXT:  - { id: 1, class: gpr32 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %w0
+# CHECK:    %1 = SBFMWri %0, 0, 15
+body:             |
+  bb.0:
+    liveins: %w0
+
+    %0(s16) = COPY %w0
+    %1(s32) = G_SEXT %0
+    %w0 = COPY %1
+...
+
+---
+# CHECK-LABEL: name: sext_s32_s64_gpr
+name:            sext_s32_s64_gpr
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr32 }
+# CHECK-NEXT:  - { id: 1, class: gpr64 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %w0
+# CHECK:    %2 = SUBREG_TO_REG 0, %0, {{[0-9]+}}
+# CHECK:    %1 = SBFMXri %2, 0, 31
+body:             |
+  bb.0:
+    liveins: %w0
+
+    %0(s32) = COPY %w0
+    %1(s64) = G_SEXT %0
+    %w0 = COPY %1
+...

test/CodeGen/AArch64/GlobalISel/arm64-instructionselect-zext.mir

+# RUN: llc -O0 -mtriple=aarch64-linux-gnu -run-pass=instruction-select -verify-machineinstrs -global-isel %s -o - | FileCheck %s
+
+--- |
+  target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+  define void @zext_s16_s32_gpr() { ret void }
+  define void @zext_s32_s64_gpr() { ret void }
+
+...
+
+---
+# CHECK-LABEL: name: zext_s16_s32_gpr
+name:            zext_s16_s32_gpr
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr32 }
+# CHECK-NEXT:  - { id: 1, class: gpr32 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %w0
+# CHECK:    %1 = UBFMWri %0, 0, 15
+body:             |
+  bb.0:
+    liveins: %w0
+
+    %0(s16) = COPY %w0
+    %1(s32) = G_ZEXT %0
+    %w0 = COPY %1
+...
+
+---
+# CHECK-LABEL: name: zext_s32_s64_gpr
+name:            zext_s32_s64_gpr
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr32 }
+# CHECK-NEXT:  - { id: 1, class: gpr64 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %w0
+# CHECK:    %2 = SUBREG_TO_REG 0, %0, {{[0-9]+}}
+# CHECK:    %1 = UBFMXri %2, 0, 31
+body:             |
+  bb.0:
+    liveins: %w0
+
+    %0(s32) = COPY %w0
+    %1(s64) = G_ZEXT %0
+    %w0 = COPY %1
+...

test/CodeGen/AArch64/GlobalISel/select-xor.mir

-# RUN: llc -O0 -mtriple=aarch64-- -run-pass=instruction-select -verify-machineinstrs -global-isel %s -o - | FileCheck %s
+# RUN: llc -O0 -mtriple=aarch64-linux-gnu -run-pass=instruction-select -verify-machineinstrs -global-isel %s -o - | FileCheck %s
 
 --- |
   target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
 
   define void @xor_s32_gpr() { ret void }
   define void @xor_s64_gpr() { ret void }
   define void @xor_constant_n1_s32_gpr() { ret void }
   define void @xor_constant_n1_s64_gpr() { ret void }

test/TableGen/GlobalISelEmitter.td

 // CHECK-NEXT:    }
 // CHECK-NEXT:    return false;
 // CHECK-NEXT:  }()) { return true; }
 
 
 def ADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2),
             [(set GPR32:$dst, (add GPR32:$src1, GPR32:$src2))]>;
 
+//===- Test a nested instruction match. -----------------------------------===//
+
+// CHECK-LABEL: if ([&]() {
+// CHECK-NEXT:    MachineInstr &MI0 = I;
+// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
+// CHECK-NEXT:      return false;
+// CHECK-NEXT:    if (!MI0.getOperand(1).isReg())
+// CHECK-NEXT:      return false;
+// CHECK-NEXT:    MachineInstr &MI1 = *MRI.getVRegDef(MI0.getOperand(1).getReg());
+// CHECK-NEXT:    if (MI1.getNumOperands() < 3)
+// CHECK-NEXT:      return false;
+// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_MUL) &&
+// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
+// CHECK-NEXT:        ((/* Operand 1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:        (((MI1.getOpcode() == TargetOpcode::G_ADD) &&
+// CHECK-NEXT:        ((/* Operand 0 */ (MRI.getType(MI1.getOperand(0).getReg()) == (LLT::scalar(32))))) &&
+// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI1.getOperand(1).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI1.getOperand(1).getReg(), MRI, TRI))))) &&
+// CHECK-NEXT:        ((/* src2 */ (MRI.getType(MI1.getOperand(2).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI1.getOperand(2).getReg(), MRI, TRI))))))
+// CHECK-NEXT:        ))) &&
+// CHECK-NEXT:        ((/* src3 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(2).getReg(), MRI, TRI)))))) {
+// CHECK-NEXT:        if (!isObviouslySafeToFold(MI1)) return false;
+// CHECK-NEXT:        // (mul:i32 (add:i32 GPR32:i32:$src1, GPR32:i32:$src2), GPR32:i32:$src3)  =>  (MULADD:i32 GPR32:i32:$src1, GPR32:i32:$src2, GPR32:i32:$src3)
+// CHECK-NEXT:     MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::MULADD));
+// CHECK-NEXT:     MIB.add(MI0.getOperand(0)/*dst*/);
+// CHECK-NEXT:     MIB.add(MI1.getOperand(1)/*src1*/);
+// CHECK-NEXT:     MIB.add(MI1.getOperand(2)/*src2*/);
+// CHECK-NEXT:     MIB.add(MI0.getOperand(2)/*src3*/);
+// CHECK-NEXT:     MIB.setMemRefs(I.memoperands_begin(), I.memoperands_end());
+// CHECK-NEXT:     I.eraseFromParent();
+// CHECK-NEXT:     MachineInstr &NewI = *MIB;
+// CHECK-NEXT:     constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:     return true;
+// CHECK-NEXT:   }
+
+// We also get a second rule by commutativity.
+// CHECK-LABEL: if ([&]() {
+// CHECK-NEXT:    MachineInstr &MI0 = I;
+// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
+// CHECK-NEXT:      return false;
+// CHECK-NEXT:    if (!MI0.getOperand(2).isReg())
+// CHECK-NEXT:      return false;
+// CHECK-NEXT:    MachineInstr &MI1 = *MRI.getVRegDef(MI0.getOperand(2).getReg());
+// CHECK-NEXT:    if (MI1.getNumOperands() < 3)
+// CHECK-NEXT:      return false;
+// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_MUL) &&
+// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
+// CHECK-NEXT:        ((/* src3 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
+// CHECK-NEXT:        ((/* Operand 2 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:        (((MI1.getOpcode() == TargetOpcode::G_ADD) &&
+// CHECK-NEXT:        ((/* Operand 0 */ (MRI.getType(MI1.getOperand(0).getReg()) == (LLT::scalar(32))))) &&
+// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI1.getOperand(1).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI1.getOperand(1).getReg(), MRI, TRI))))) &&
+// CHECK-NEXT:        ((/* src2 */ (MRI.getType(MI1.getOperand(2).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI1.getOperand(2).getReg(), MRI, TRI))))))
+// CHECK-NEXT:        )))) {
+// CHECK-NEXT:        if (!isObviouslySafeToFold(MI1)) return false;
+// CHECK-NEXT:        // (mul:i32 GPR32:i32:$src3, (add:i32 GPR32:i32:$src1, GPR32:i32:$src2))  =>  (MULADD:i32 GPR32:i32:$src1, GPR32:i32:$src2, GPR32:i32:$src3)
+// CHECK-NEXT:     MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::MULADD));
+// CHECK-NEXT:     MIB.add(MI0.getOperand(0)/*dst*/);
+// CHECK-NEXT:     MIB.add(MI1.getOperand(1)/*src1*/);
+// CHECK-NEXT:     MIB.add(MI1.getOperand(2)/*src2*/);
+// CHECK-NEXT:     MIB.add(MI0.getOperand(1)/*src3*/);
+// CHECK-NEXT:     MIB.setMemRefs(I.memoperands_begin(), I.memoperands_end());
+// CHECK-NEXT:     I.eraseFromParent();
+// CHECK-NEXT:     MachineInstr &NewI = *MIB;
+// CHECK-NEXT:     constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:     return true;
+// CHECK-NEXT:   }
+
+def MULADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2, GPR32:$src3),
+               [(set GPR32:$dst,
+                     (mul (add GPR32:$src1, GPR32:$src2), GPR32:$src3))]>;
+
+//===- Test another simple pattern with regclass operands. ----------------===//
+
 // CHECK-LABEL: if ([&]() {
 // CHECK-NEXT:    MachineInstr &MI0 = I;
 // CHECK-NEXT:    if (MI0.getNumOperands() < 3)
 // CHECK-NEXT:      return false;
 // CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_MUL) &&
 // CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
 // CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
 // CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&

utils/TableGen/GlobalISelEmitter.cpp

 }
 
 static bool isTrivialOperatorNode(const TreePatternNode *N) {
   return !N->isLeaf() && !N->hasAnyPredicate() && !N->getTransformFn();
 }
 
 //===- Matchers -----------------------------------------------------------===//
 
+class OperandMatcher;
 class MatchAction;
 
 /// Generates code to check that a match rule matches.
 class RuleMatcher {
   /// A list of matchers that all need to succeed for the current rule to match.
   /// FIXME: This currently supports a single match position but could be
   /// extended to support multiple positions to support div/rem fusion or
   /// load-multiple instructions.
public:
   /// the predicate when generating the matcher code. Kinds with higher priority
   /// must be tested first.
   ///
   /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
   /// but OPM_Int must have priority over OPM_RegBank since constant integers
   /// are represented by a virtual register defined by a G_CONSTANT instruction.
   enum PredicateKind {
     OPM_ComplexPattern,
+    OPM_Instruction,
     OPM_Int,
     OPM_LLT,
     OPM_RegBank,
     OPM_MBB,
   };
 
 protected:
   PredicateKind Kind;
 
 public:
   OperandPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
   virtual ~OperandPredicateMatcher() {}
 
   PredicateKind getKind() const { return Kind; }
 
+  /// Return the OperandMatcher for the specified operand or nullptr if there
+  /// isn't one by that name in this operand predicate matcher.
+  ///
+  /// InstructionOperandMatcher is the only subclass that can return non-null
+  /// for this.
+  virtual Optional<const OperandMatcher *>
+  getOptionalOperand(const StringRef SymbolicName) const {
+    assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
+    return None;
+  }
+
+  /// Emit C++ statements to capture instructions into local variables.
+  ///
+  /// Only InstructionOperandMatcher needs to do anything for this method.
+  virtual void emitCxxCaptureStmtsForOperand(raw_ostream &OS, RuleMatcher &Rule,
+                                             StringRef Expr) const {}
+
   /// Emit a C++ expression that checks the predicate for the given operand.
   virtual void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
                                     StringRef OperandExpr) const = 0;
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const {
void setSymbolicName(StringRef Name) {
     SymbolicName = Name;
   }
   unsigned getOperandIndex() const { return OpIdx; }
 
   std::string getOperandExpr(const StringRef InsnVarName) const {
     return (InsnVarName + ".getOperand(" + llvm::to_string(OpIdx) + ")").str();
   }
 
+  Optional<const OperandMatcher *>
+  getOptionalOperand(StringRef DesiredSymbolicName) const {
+    assert(!DesiredSymbolicName.empty() && "Cannot lookup unnamed operand");
+    if (DesiredSymbolicName == SymbolicName)
+      return this;
+    for (const auto &OP : predicates()) {
+      const auto &MaybeOperand = OP->getOptionalOperand(DesiredSymbolicName);
+      if (MaybeOperand.hasValue())
+        return MaybeOperand.getValue();
+    }
+    return None;
+  }
+
   InstructionMatcher &getInstructionMatcher() const { return Insn; }
 
+  /// Emit C++ statements to capture instructions into local variables.
+  void emitCxxCaptureStmtsForOperand(raw_ostream &OS, RuleMatcher &Rule,
+                                     StringRef OperandExpr) const {
+    for (const auto &Predicate : predicates())
+      Predicate->emitCxxCaptureStmtsForOperand(OS, Rule, OperandExpr);
+  }
+
   /// Emit a C++ expression that tests whether the instruction named in
   /// InsnVarName matches all the predicate and all the operands.
   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
                             const StringRef InsnVarName) const {
     OS << "(/* ";
     if (SymbolicName.empty())
       OS << "Operand " << OpIdx;
     else
auto I = std::find_if(Operands.begin(), Operands.end(),
                           [&OpIdx](const OperandMatcher &X) {
                             return X.getOperandIndex() == OpIdx;
                           });
     if (I != Operands.end())
       return *I;
     llvm_unreachable("Failed to lookup operand");
   }
 
-  Optional<const OperandMatcher *> getOptionalOperand(StringRef SymbolicName) const {
+  Optional<const OperandMatcher *>
+  getOptionalOperand(StringRef SymbolicName) const {
     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
-    const auto &I = std::find_if(Operands.begin(), Operands.end(),
-                                 [&SymbolicName](const OperandMatcher &X) {
-                                   return X.getSymbolicName() == SymbolicName;
-                                 });
-    if (I != Operands.end())
-      return &*I;
+    for (const auto &Operand : Operands) {
+      const auto &OM = Operand.getOptionalOperand(SymbolicName);
+      if (OM.hasValue())
+        return OM.getValue();
+    }
     return None;
   }
 
   const OperandMatcher &getOperand(const StringRef SymbolicName) const {
     Optional<const OperandMatcher *>OM = getOptionalOperand(SymbolicName);
     if (OM.hasValue())
       return *OM.getValue();
     llvm_unreachable("Failed to lookup operand");
   }
 
   unsigned getNumOperands() const { return Operands.size(); }
+  OperandVec::iterator operands_begin() { return Operands.begin(); }
+  OperandVec::iterator operands_end() { return Operands.end(); }
+  iterator_range<OperandVec::iterator> operands() {
+    return make_range(operands_begin(), operands_end());
+  }
   OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
   OperandVec::const_iterator operands_end() const { return Operands.end(); }
   iterator_range<OperandVec::const_iterator> operands() const {
     return make_range(operands_begin(), operands_end());
   }
 
   /// Emit C++ statements to check the shape of the match and capture
   /// instructions into local variables.
   ///
   /// TODO: When nested instruction matching is implemented, this function will
   ///       descend into the operands and capture variables.
   void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule, StringRef Expr) {
     OS << "if (" << Expr << ".getNumOperands() < " << getNumOperands() << ")\n"
        << "  return false;\n";
+    for (const auto &Operand : Operands) {
+      Operand.emitCxxCaptureStmtsForOperand(OS, Rule,
+                                            Operand.getOperandExpr(Expr));
+    }
   }
 
   /// Emit a C++ expression that tests whether the instruction named in
   /// InsnVarName matches all the predicates and all the operands.
   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
                             StringRef InsnVarName) const {
     emitCxxPredicateListExpr(OS, Rule, InsnVarName);
     for (const auto &Operand : Operands) {
return std::accumulate(predicates().begin(), predicates().end(), 0,
                            }) +
            std::accumulate(Operands.begin(), Operands.end(), 0,
                            [](unsigned A, const OperandMatcher &Operand) {
                              return A + Operand.countTemporaryOperands();
                            });
   }
 };
 
+/// Generates code to check that the operand is a register defined by an
+/// instruction that matches the given instruction matcher.
+///
+/// For example, the pattern:
+///   (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
+/// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
+/// the:
+///   (G_ADD $src1, $src2)
+/// subpattern.
+class InstructionOperandMatcher : public OperandPredicateMatcher {
+protected:
+  std::unique_ptr<InstructionMatcher> InsnMatcher;
+
+public:
+  InstructionOperandMatcher()
+      : OperandPredicateMatcher(OPM_Instruction),
+        InsnMatcher(new InstructionMatcher()) {}
+
+  static bool classof(const OperandPredicateMatcher *P) {
+    return P->getKind() == OPM_Instruction;
+  }
+
+  InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
+
+  Optional<const OperandMatcher *>
+  getOptionalOperand(StringRef SymbolicName) const override {
+    assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
+    return InsnMatcher->getOptionalOperand(SymbolicName);
+  }
+
+  void emitCxxCaptureStmtsForOperand(raw_ostream &OS, RuleMatcher &Rule,
+                                     StringRef OperandExpr) const override {
+    OS << "if (!" << OperandExpr + ".isReg())\n"
+       << "  return false;\n";
+    std::string InsnVarName = Rule.defineInsnVar(
+        OS, *InsnMatcher,
+        ("*MRI.getVRegDef(" + OperandExpr + ".getReg())").str());
+    InsnMatcher->emitCxxCaptureStmts(OS, Rule, InsnVarName);
+  }
+
+  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
+                            StringRef OperandExpr) const override {
+    OperandExpr = Rule.getInsnVarName(*InsnMatcher);
+    OS << "(";
+    InsnMatcher->emitCxxPredicateExpr(OS, Rule, OperandExpr);
+    OS << ")\n";
+  }
+};
+
 //===- Actions ------------------------------------------------------------===//
 void OperandPlaceholder::emitCxxValueExpr(raw_ostream &OS) const {
   switch (Kind) {
   case OP_MatchReference:
     OS << MatchReference.InsnMatcher->getOperand(MatchReference.SymbolicName)
               .getOperandExpr(MatchReference.InsnVarName);
     break;
   case OP_Temporary:
void RuleMatcher::emit(raw_ostream &OS) {
 
   emitCxxCaptureStmts(OS, "I");
 
   OS << "    if (";
   Matchers.front()->emitCxxPredicateExpr(OS, *this,
                                          getInsnVarName(*Matchers.front()));
   OS << ") {\n";
 
+  // We must also check if it's safe to fold the matched instructions.
+  if (InsnVariableNames.size() >= 2) {
+    for (const auto &Pair : InsnVariableNames) {
+      // Skip the root node since it isn't moving anywhere. Everything else is
+      // sinking to meet it.
+      if (Pair.first == Matchers.front().get())
+        continue;
+
+      // Reject the difficult cases until we have a more accurate check.
+      OS << "      if (!isObviouslySafeToFold(" << Pair.second
+         << ")) return false;\n";
+
+      // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
+      //        account for unsafe cases.
+      //
+      //        Example:
+      //          MI1--> %0 = ...
+      //                 %1 = ... %0
+      //          MI0--> %2 = ... %0
+      //          It's not safe to erase MI1. We currently handle this by not
+      //          erasing %0 (even when it's dead).
+      //
+      //        Example:
+      //          MI1--> %0 = load volatile @a
+      //                 %1 = load volatile @a
+      //          MI0--> %2 = ... %0
+      //          It's not safe to sink %0's def past %1. We currently handle
+      //          this by rejecting all loads.
+      //
+      //        Example:
+      //          MI1--> %0 = load @a
+      //                 %1 = store @a
+      //          MI0--> %2 = ... %0
+      //          It's not safe to sink %0's def past %1. We currently handle
+      //          this by rejecting all loads.
+      //
+      //        Example:
+      //                   G_CONDBR %cond, @BB1
+      //                 BB0:
+      //          MI1-->   %0 = load @a
+      //                   G_BR @BB1
+      //                 BB1:
+      //          MI0-->   %2 = ... %0
+      //          It's not always safe to sink %0 across control flow. In this
+      //          case it may introduce a memory fault. We currentl handle this
+      //          by rejecting all loads.
+    }
+  }
+
   for (const auto &MA : Actions) {
     MA->emitCxxActionStmts(OS, *this, "I");
   }
 
   OS << "      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);\n";
   OS << "      return true;\n";
   OS << "    }\n";
   OS << "    return false;\n";
GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
   if (!SrcChild->isLeaf()) {
     if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
       auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
         OM.addPredicate<MBBOperandMatcher>();
         return true;
       }
     }
-
-    return failedImport("Src child operand is an unsupported type");
   }
 
   auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
   if (!OpTyOrNone)
     return failedImport("Src operand has an unsupported type");
   OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
 
+  // Check for nested instructions.
+  if (!SrcChild->isLeaf()) {
+    // Map the node to a gMIR instruction.
+    InstructionOperandMatcher &InsnOperand =
+        OM.addPredicate<InstructionOperandMatcher>();
+    auto InsnMatcherOrError =
+        importSelDAGMatcher(InsnOperand.getInsnMatcher(), SrcChild);
+    if (auto Error = InsnMatcherOrError.takeError())
+      return std::move(Error);
+
+    return true;
+  }
+
   // Check for constant immediates.
   if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
     OM.addPredicate<IntOperandMatcher>(ChildInt->getValue());
     return true;
   }
 
   // Check for def's like register classes or ComplexPattern's.
   if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
   TreePatternNode *Dst = P.getDstPattern();
 
   // If the root of either pattern isn't a simple operator, ignore it.
   if (!isTrivialOperatorNode(Dst))
     return failedImport("Dst pattern root isn't a trivial operator");
   if (!isTrivialOperatorNode(Src))
     return failedImport("Src pattern root isn't a trivial operator");
 
+  // Start with the defined operands (i.e., the results of the root operator).
   Record *DstOp = Dst->getOperator();
   if (!DstOp->isSubClassOf("Instruction"))
     return failedImport("Pattern operator isn't an instruction");
 
   auto &DstI = Target.getInstruction(DstOp);
   if (DstI.Operands.NumDefs != Src->getExtTypes().size())
     return failedImport("Src pattern results and dst MI defs are different");