[tablegen][globalisel] Capture instructions into locals and related infrastructure for multiple instructions matches.

[dsanders]

Summary

Prepare the way for nested instruction matching support by having actions
like CopyRenderer look up operands in the RuleMatcher rather than a
specific InstructionMatcher. This allows actions to reference any operand
from any matched instruction.

It works by checking the 'shape' of the match and capturing
each matched instruction to a local variable. If the shape is wrong
(not enough operands, leaf nodes where non-leafs are expected, etc.), then
the rule exits early without checking the predicates. Once we've captured
the instructions, we then test the predicates as before (except using the
local variables). If the match is successful, then we render the new
instruction as before using the local variables.

It's not noticable in this patch but by the time we support multiple
instruction matching, this patch will also cause a significant improvement
to readability of the emitted code since
MRI.getVRegDef(I->getOperand(0).getReg()) will simply be MI1 after
emitCxxCaptureStmts().

This isn't quite NFC because I've also fixed a bug that I'm surprised we
haven't encountered yet. It now checks there are at least the expected
number of operands before accessing them with getOperand().

Depends on D30531

[dsanders]

ping

[rovka]

I think this looks ok overall, just a few nits.

There's a typo in the summary (I assume the first "capturing each" is superfluous):

It works by capturing each checking the 'shape' of the match and capturing
each matched instruction to a local variable

test/TableGen/GlobalISelEmitter.td

46 ↗

(On Diff #90332)

I would check for the "return true" as well.

utils/TableGen/GlobalISelEmitter.cpp

577 ↗

(On Diff #90332)

Are you planning to add more checks here? If not, I would suggest naming this getOperand and renaming getOperand to getOperandOrNull (otherwise it's a bit unclear what it's checking without looking at the code).

595 ↗

(On Diff #90332)

This isn't capturing anything, it's just checking that we can capture. I would update the comment to reflect that, otherwise it looks a bit out-of-sync.
Ideally, we'd have a more expressive name for emitCxxCaptureStmts, but emitCxxCheckAndCaptureStmts is a bit long and I can't think of a better one, so just fixing the comments should do.

900 ↗

(On Diff #90332)

Why is this a lambda? If it's just for readability, wouldn't it be easier to just generate comments along the lines of "Code for <blah> rule" ?

903 ↗

(On Diff #90332)

I would move this comment to the emitCxxCaptureStmts declaration.

[dsanders]

test/TableGen/GlobalISelEmitter.td

46 ↗

(On Diff #90332)

Ok

utils/TableGen/GlobalISelEmitter.cpp

577 ↗

(On Diff #90332)

No, the 'Checked' is just to distinguish between the case that's allowed to fail and the one that isn't. I'll rename it.

What do you think about getOptionalOperand (returning an Optional<>) for the one that's allowed to fail? I think that might fit better with the support for OperandWithDefaultOps I'm looking into at the moment.

595 ↗

(On Diff #90332)

Good point. It's part of the code to capture the locals but the name is misleading in this case. I can't think of any good alternatives either so I'll update the comments.

900 ↗

(On Diff #90332)

The main thing is that it allows me to declare MachineOperands in the middle of the checks. There's no default constructor so I can't declare them and assign to them later and I didn't want to add redundant MachineOperand::CreatePlaceholder() calls.. The alternative was to use additional scopes and 'if (!condition) goto ruleN;' but I thought that looked worse.

903 ↗

(On Diff #90332)

Ok

[rovka]

LGTM.

utils/TableGen/GlobalISelEmitter.cpp

577 ↗

(On Diff #90332)

Ok, sounds good.

[dsanders]

Account for review comments

llvm/trunk/test/TableGen/GlobalISelEmitter.td

 //===- Test the function definition boilerplate. --------------------------===//
 
 // CHECK: bool MyTargetInstructionSelector::selectImpl(MachineInstr &I) const {
 // CHECK: MachineFunction &MF = *I.getParent()->getParent();
 // CHECK: const MachineRegisterInfo &MRI = MF.getRegInfo();
 
 //===- Test a simple pattern with regclass operands. ----------------------===//
 
-// CHECK-LABEL: if ((I.getOpcode() == TargetOpcode::G_ADD) &&
-// CHECK-NEXT: ((/* dst */ (MRI.getType(I.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:  ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT: ((/* src1 */ (MRI.getType(I.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:  ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT: ((/* src2 */ (MRI.getType(I.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:  ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(2).getReg(), MRI, TRI)))))) {
+// 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_ADD) &&
+// 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))) &&
+// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
+// CHECK-NEXT:        ((/* src2 */ (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:   // (add:i32 GPR32:i32:$src1, GPR32:i32:$src2) => (ADD:i32 GPR32:i32:$src1, GPR32:i32:$src2)
-// CHECK-NEXT:   I.setDesc(TII.get(MyTarget::ADD));
-// CHECK-NEXT:   MachineInstr &NewI = I;
-// CHECK:        constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:   return true;
-// CHECK-NEXT: }
+// CHECK-NEXT:      // (add:i32 GPR32:i32:$src1, GPR32:i32:$src2) => (ADD:i32 GPR32:i32:$src1, GPR32:i32:$src2)
+// CHECK-NEXT:      I.setDesc(TII.get(MyTarget::ADD));
+// CHECK-NEXT:      MachineInstr &NewI = I;
+// CHECK-NEXT:      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:      return true;
+// 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))]>;
 
-// CHECK-LABEL: if ((I.getOpcode() == TargetOpcode::G_MUL) &&
-// CHECK-NEXT: ((/* dst */ (MRI.getType(I.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:  ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT: ((/* src1 */ (MRI.getType(I.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:  ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT: ((/* src2 */ (MRI.getType(I.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:  ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(2).getReg(), MRI, TRI)))))) {
-
-// CHECK-NEXT:   // (mul:i32 GPR32:i32:$src1, GPR32:i32:$src2) => (MUL:i32 GPR32:i32:$src2, GPR32:i32:$src1)
-// CHECK-NEXT:   MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::MUL));
-// CHECK-NEXT:   MIB.add(I.getOperand(0)/*dst*/);
-// CHECK-NEXT:   MIB.add(I.getOperand(2)/*src2*/);
-// CHECK-NEXT:   MIB.add(I.getOperand(1)/*src1*/);
-// CHECK-NEXT:   MIB.setMemRefs(I.memoperands_begin(), I.memoperands_end());
-// CHECK-NEXT:   I.eraseFromParent();
-// CHECK-NEXT:   MachineInstr &NewI = *MIB;
-// CHECK:        constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:   return true;
-// CHECK-NEXT: }
+// 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))) &&
+// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
+// CHECK-NEXT:        ((/* src2 */ (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:      // (mul:i32 GPR32:i32:$src1, GPR32:i32:$src2) => (MUL:i32 GPR32:i32:$src2, GPR32:i32:$src1)
+// CHECK-NEXT:      MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::MUL));
+// CHECK-NEXT:      MIB.add(MI0.getOperand(0)/*dst*/);
+// CHECK-NEXT:      MIB.add(MI0.getOperand(2)/*src2*/);
+// CHECK-NEXT:      MIB.add(MI0.getOperand(1)/*src1*/);
+// 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:    }
+// CHECK-NEXT:    return false;
+// CHECK-NEXT:  }()) { return true; }
 
 def MUL : I<(outs GPR32:$dst), (ins GPR32:$src2, GPR32:$src1),
              [(set GPR32:$dst, (mul GPR32:$src1, GPR32:$src2))]>;
 
 //===- Test a simple pattern with constant immediate operands. ------------===//
 //
 // This must precede the 3-register variants because constant immediates have
 // priority over register banks.
 
-// CHECK-LABEL: if ((I.getOpcode() == TargetOpcode::G_XOR) &&
-// CHECK-NEXT: ((/* dst */ (MRI.getType(I.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:  ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT: ((/* Wm */ (MRI.getType(I.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:  ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT: ((/* Operand 2 */ (MRI.getType(I.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT: (isOperandImmEqual(I.getOperand(2), -1, MRI))))) {
-
-// CHECK-NEXT:   // (xor:i32 GPR32:i32:$Wm, -1:i32) => (ORN:i32 R0:i32, GPR32:i32:$Wm)
-// CHECK-NEXT:   MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::ORN));
-// CHECK-NEXT:   MIB.add(I.getOperand(0)/*dst*/);
-// CHECK-NEXT:   MIB.addReg(MyTarget::R0);
-// CHECK-NEXT:   MIB.add(I.getOperand(1)/*Wm*/);
-// CHECK-NEXT:   MIB.setMemRefs(I.memoperands_begin(), I.memoperands_end());
-// CHECK-NEXT:   I.eraseFromParent();
-// CHECK-NEXT:   MachineInstr &NewI = *MIB;
-// CHECK:        constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:   return true;
-// CHECK-NEXT: }
+// 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_XOR) &&
+// 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:        ((/* Wm */ (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:        (isOperandImmEqual(MI0.getOperand(2), -1, MRI))))) {
+// CHECK-NEXT:      // (xor:i32 GPR32:i32:$Wm, -1:i32) => (ORN:i32 R0:i32, GPR32:i32:$Wm)
+// CHECK-NEXT:      MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::ORN));
+// CHECK-NEXT:      MIB.add(MI0.getOperand(0)/*dst*/);
+// CHECK-NEXT:      MIB.addReg(MyTarget::R0);
+// CHECK-NEXT:      MIB.add(MI0.getOperand(1)/*Wm*/);
+// 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:    }
+// CHECK-NEXT:    return false;
+// CHECK-NEXT:  }()) { return true; }
 
 def ORN : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>;
 def : Pat<(not GPR32:$Wm), (ORN R0, GPR32:$Wm)>;
 
 //===- Test a pattern with an MBB operand. --------------------------------===//
 
-// CHECK-LABEL: if ((I.getOpcode() == TargetOpcode::G_BR) &&
-// CHECK-NEXT: ((/* target */ (I.getOperand(0).isMBB())))) {
+// CHECK-LABEL: if ([&]() {
+// CHECK-NEXT:      MachineInstr &MI0 = I;
+// CHECK-NEXT:      if (MI0.getNumOperands() < 1)
+// CHECK-NEXT:        return false;
+// CHECK-NEXT:      if ((MI0.getOpcode() == TargetOpcode::G_BR) &&
+// CHECK-NEXT:          ((/* target */ (MI0.getOperand(0).isMBB())))) {
                     
-// CHECK-NEXT:   // (br (bb:Other):$target) => (BR (bb:Other):$target)
-// CHECK-NEXT:   I.setDesc(TII.get(MyTarget::BR));
-// CHECK-NEXT:   MachineInstr &NewI = I;
-// CHECK:        constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:   return true;
-// CHECK-NEXT: }
+// CHECK-NEXT:       // (br (bb:Other):$target) => (BR (bb:Other):$target)
+// CHECK-NEXT:       I.setDesc(TII.get(MyTarget::BR));
+// CHECK-NEXT:       MachineInstr &NewI = I;
+// CHECK-NEXT:       constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:       return true;
+// CHECK-NEXT:    }
+// CHECK-NEXT:    return false;
+// CHECK-NEXT:  }()) { return true; }
 
 def BR : I<(outs), (ins unknown:$target),
             [(br bb:$target)]>;

llvm/trunk/utils/TableGen/GlobalISelEmitter.cpp

class RuleMatcher {
   /// extended to support multiple positions to support div/rem fusion or
   /// load-multiple instructions.
   std::vector<std::unique_ptr<InstructionMatcher>> Matchers;
 
   /// A list of actions that need to be taken when all predicates in this rule
   /// have succeeded.
   std::vector<std::unique_ptr<MatchAction>> Actions;
 
+  /// A map of instruction matchers to the local variables created by
+  /// emitCxxCaptureStmts().
+  std::map<const InstructionMatcher *, std::string> InsnVariableNames;
+
+  /// ID for the next instruction variable defined with defineInsnVar()
+  unsigned NextInsnVarID;
+
 public:
-  RuleMatcher() {}
+  RuleMatcher()
+      : Matchers(), Actions(), InsnVariableNames(), NextInsnVarID(0) {}
 
   InstructionMatcher &addInstructionMatcher();
 
   template <class Kind, class... Args> Kind &addAction(Args &&... args);
 
-  void emit(raw_ostream &OS) const;
+  std::string defineInsnVar(raw_ostream &OS, const InstructionMatcher &Matcher,
+                            StringRef Value);
+  StringRef getInsnVarName(const InstructionMatcher &InsnMatcher) const;
+
+  void emitCxxCaptureStmts(raw_ostream &OS, StringRef Expr);
+
+  void emit(raw_ostream &OS);
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   bool isHigherPriorityThan(const RuleMatcher &B) const;
 
   /// Report the maximum number of temporary operands needed by the rule
   /// matcher.

 
 public:
   OperandPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
   virtual ~OperandPredicateMatcher() {}
 
   PredicateKind getKind() const { return Kind; }
 
   /// Emit a C++ expression that checks the predicate for the given operand.
-  virtual void emitCxxPredicateExpr(raw_ostream &OS,
+  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 {
     return Kind < B.Kind;
   };

 public:
   LLTOperandMatcher(const LLTCodeGen &Ty)
       : OperandPredicateMatcher(OPM_LLT), Ty(Ty) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_LLT;
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS,
+  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
                             StringRef OperandExpr) const override {
     OS << "MRI.getType(" << OperandExpr << ".getReg()) == (";
     Ty.emitCxxConstructorCall(OS);
     OS << ")";
   }
 };
 
 /// Generates code to check that an operand is a particular target constant.
 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
 protected:
   const Record &TheDef;
   /// The index of the first temporary operand to allocate to this
   /// ComplexPattern.
   unsigned BaseTemporaryID;
 
   unsigned getNumOperands() const {
     return TheDef.getValueAsDag("Operands")->getNumArgs();
   }
 
 public:
   ComplexPatternOperandMatcher(const Record &TheDef, unsigned BaseTemporaryID)
       : OperandPredicateMatcher(OPM_ComplexPattern), TheDef(TheDef),
         BaseTemporaryID(BaseTemporaryID) {}
 
-  void emitCxxPredicateExpr(raw_ostream &OS,
+  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
                             StringRef OperandExpr) const override {
     OS << TheDef.getValueAsString("MatcherFn") << "(" << OperandExpr;
     for (unsigned I = 0; I < getNumOperands(); ++I) {
       OS << ", ";
       OperandPlaceholder::CreateTemporary(BaseTemporaryID + I)
           .emitCxxValueExpr(OS);
     }
     OS << ")";

 public:
   RegisterBankOperandMatcher(const CodeGenRegisterClass &RC)
       : OperandPredicateMatcher(OPM_RegBank), RC(RC) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_RegBank;
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS,
+  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
                             StringRef OperandExpr) const override {
     OS << "(&RBI.getRegBankFromRegClass(" << RC.getQualifiedName()
        << "RegClass) == RBI.getRegBank(" << OperandExpr
        << ".getReg(), MRI, TRI))";
   }
 };
 
 /// Generates code to check that an operand is a basic block.
 class MBBOperandMatcher : public OperandPredicateMatcher {
 public:
   MBBOperandMatcher() : OperandPredicateMatcher(OPM_MBB) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_MBB;
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS,
+  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
                             StringRef OperandExpr) const override {
     OS << OperandExpr << ".isMBB()";
   }
 };
 
 /// Generates code to check that an operand is a particular int.
 class IntOperandMatcher : public OperandPredicateMatcher {
 protected:
   int64_t Value;
 
 public:
   IntOperandMatcher(int64_t Value)
       : OperandPredicateMatcher(OPM_Int), Value(Value) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_Int;
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS,
+  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
                             StringRef OperandExpr) const override {
     OS << "isOperandImmEqual(" << OperandExpr << ", " << Value << ", MRI)";
   }
 };
 
 /// Generates code to check that a set of predicates match for a particular
 /// operand.
 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
 protected:
+  InstructionMatcher &Insn;
   unsigned OpIdx;
   std::string SymbolicName;
 
 public:
-  OperandMatcher(unsigned OpIdx, const std::string &SymbolicName)
-      : OpIdx(OpIdx), SymbolicName(SymbolicName) {}
+  OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
+                 const std::string &SymbolicName)
+      : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName) {}
 
   bool hasSymbolicName() const { return !SymbolicName.empty(); }
   const StringRef getSymbolicName() const { return SymbolicName; }
   unsigned getOperandIndex() const { return OpIdx; }
 
   std::string getOperandExpr(const StringRef InsnVarName) const {
     return (InsnVarName + ".getOperand(" + llvm::to_string(OpIdx) + ")").str();
   }
 
+  InstructionMatcher &getInstructionMatcher() const { return Insn; }
+
   /// 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, const StringRef InsnVarName) const {
+  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
+                            const StringRef InsnVarName) const {
     OS << "(/* ";
     if (SymbolicName.empty())
       OS << "Operand " << OpIdx;
     else
       OS << SymbolicName;
     OS << " */ ";
-    emitCxxPredicateListExpr(OS, getOperandExpr(InsnVarName));
+    emitCxxPredicateListExpr(OS, Rule, getOperandExpr(InsnVarName));
     OS << ")";
   }
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   bool isHigherPriorityThan(const OperandMatcher &B) const {
     // Operand matchers involving more predicates have higher priority.

 public:
   InstructionPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
   virtual ~InstructionPredicateMatcher() {}
 
   PredicateKind getKind() const { return Kind; }
 
   /// Emit a C++ expression that tests whether the instruction named in
   /// InsnVarName matches the predicate.
-  virtual void emitCxxPredicateExpr(raw_ostream &OS,
+  virtual void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
                                     StringRef InsnVarName) const = 0;
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   virtual bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
     return Kind < B.Kind;
   };

 public:
   InstructionOpcodeMatcher(const CodeGenInstruction *I)
       : InstructionPredicateMatcher(IPM_Opcode), I(I) {}
 
   static bool classof(const InstructionPredicateMatcher *P) {
     return P->getKind() == IPM_Opcode;
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS,
+  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
                             StringRef InsnVarName) const override {
     OS << InsnVarName << ".getOpcode() == " << I->Namespace
        << "::" << I->TheDef->getName();
   }
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
protected:
 
   /// The operands to match. All rendered operands must be present even if the
   /// condition is always true.
   OperandVec Operands;
 
 public:
   /// Add an operand to the matcher.
   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName) {
-    Operands.emplace_back(OpIdx, SymbolicName);
+    Operands.emplace_back(*this, OpIdx, SymbolicName);
     return Operands.back();
   }
 
-  const OperandMatcher &getOperand(const 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;
+      return &*I;
+    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::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";
+  }
+
   /// 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, StringRef InsnVarName) const {
-    emitCxxPredicateListExpr(OS, InsnVarName);
+  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
+                            StringRef InsnVarName) const {
+    emitCxxPredicateListExpr(OS, Rule, InsnVarName);
     for (const auto &Operand : Operands) {
       OS << " &&\n(";
-      Operand.emitCxxPredicateExpr(OS, InsnVarName);
+      Operand.emitCxxPredicateExpr(OS, Rule, InsnVarName);
       OS << ")";
     }
   }
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   bool isHigherPriorityThan(const InstructionMatcher &B) const {
protected:
   RendererKind Kind;
 
 public:
   OperandRenderer(RendererKind Kind) : Kind(Kind) {}
   virtual ~OperandRenderer() {}
 
   RendererKind getKind() const { return Kind; }
 
-  virtual void emitCxxRenderStmts(raw_ostream &OS) const = 0;
+  virtual void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const = 0;
 };
 
 /// A CopyRenderer emits code to copy a single operand from an existing
 /// instruction to the one being built.
 class CopyRenderer : public OperandRenderer {
 protected:
   /// The matcher for the instruction that this operand is copied from.
   /// This provides the facility for looking up an a operand by it's name so
   /// that it can be used as a source for the instruction being built.
   const InstructionMatcher &Matched;
-  /// The name of the instruction to copy from.
-  const StringRef InsnVarName;
   /// The name of the operand.
   const StringRef SymbolicName;
 
 public:
-  CopyRenderer(const InstructionMatcher &Matched, const StringRef InsnVarName,
-               const StringRef SymbolicName)
-      : OperandRenderer(OR_Copy), Matched(Matched), InsnVarName(InsnVarName),
-        SymbolicName(SymbolicName) {}
+  CopyRenderer(const InstructionMatcher &Matched, StringRef SymbolicName)
+      : OperandRenderer(OR_Copy), Matched(Matched), SymbolicName(SymbolicName) {
+  }
 
   static bool classof(const OperandRenderer *R) {
     return R->getKind() == OR_Copy;
   }
 
   const StringRef getSymbolicName() const { return SymbolicName; }
 
-  void emitCxxRenderStmts(raw_ostream &OS) const override {
-    std::string OperandExpr =
-        Matched.getOperand(SymbolicName).getOperandExpr(InsnVarName);
+  void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
+    const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
+    StringRef InsnVarName =
+        Rule.getInsnVarName(Operand.getInstructionMatcher());
+    std::string OperandExpr = Operand.getOperandExpr(InsnVarName);
     OS << "    MIB.add(" << OperandExpr << "/*" << SymbolicName << "*/);\n";
   }
 };
 
 /// Adds a specific physical register to the instruction being built.
 /// This is typically useful for WZR/XZR on AArch64.
 class AddRegisterRenderer : public OperandRenderer {
 protected:
   const Record *RegisterDef;
 
 public:
   AddRegisterRenderer(const Record *RegisterDef)
       : OperandRenderer(OR_Register), RegisterDef(RegisterDef) {}
 
   static bool classof(const OperandRenderer *R) {
     return R->getKind() == OR_Register;
   }
 
-  void emitCxxRenderStmts(raw_ostream &OS) const override {
+  void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
     OS << "    MIB.addReg(" << RegisterDef->getValueAsString("Namespace")
        << "::" << RegisterDef->getName() << ");\n";
   }
 };
 
 class RenderComplexPatternOperand : public OperandRenderer {
 private:
   const Record &TheDef;
   std::vector<OperandPlaceholder> Sources;
 
   unsigned getNumOperands() const {
     return TheDef.getValueAsDag("Operands")->getNumArgs();
   }
 
 public:
   RenderComplexPatternOperand(const Record &TheDef,
                               const ArrayRef<OperandPlaceholder> Sources)
       : OperandRenderer(OR_ComplexPattern), TheDef(TheDef), Sources(Sources) {}
 
   static bool classof(const OperandRenderer *R) {
     return R->getKind() == OR_ComplexPattern;
   }
 
-  void emitCxxRenderStmts(raw_ostream &OS) const override {
+  void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
     assert(Sources.size() == getNumOperands() && "Inconsistent number of operands");
     for (const auto &Source : Sources) {
       OS << "MIB.add(";
       Source.emitCxxValueExpr(OS);
       OS << ");\n";
     }
   }
 };
 
 /// An action taken when all Matcher predicates succeeded for a parent rule.
 ///
 /// Typical actions include:
 /// * Changing the opcode of an instruction.
 /// * Adding an operand to an instruction.
 class MatchAction {
 public:
   virtual ~MatchAction() {}
 
   /// Emit the C++ statements to implement the action.
   ///
-  /// \param InsnVarName If given, it's an instruction to recycle. The
-  ///                    requirements on the instruction vary from action to
-  ///                    action.
-  virtual void emitCxxActionStmts(raw_ostream &OS,
-                                  const StringRef InsnVarName) const = 0;
+  /// \param RecycleVarName If given, it's an instruction to recycle. The
+  ///                       requirements on the instruction vary from action to
+  ///                       action.
+  virtual void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
+                                  StringRef RecycleVarName) const = 0;
 };
 
 /// Generates a comment describing the matched rule being acted upon.
 class DebugCommentAction : public MatchAction {
 private:
   const PatternToMatch &P;
 
 public:
   DebugCommentAction(const PatternToMatch &P) : P(P) {}
 
-  void emitCxxActionStmts(raw_ostream &OS,
-                          const StringRef InsnVarName) const override {
-    OS << "// " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern();
+  void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
+                          StringRef RecycleVarName) const override {
+    OS << "// " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern() << "\n";
   }
 };
 
 /// Generates code to build an instruction or mutate an existing instruction
 /// into the desired instruction when this is possible.
 class BuildMIAction : public MatchAction {
 private:
   const CodeGenInstruction *I;
public:
 
   template <class Kind, class... Args>
   Kind &addRenderer(Args&&... args) {
     OperandRenderers.emplace_back(
         llvm::make_unique<Kind>(std::forward<Args>(args)...));
     return *static_cast<Kind *>(OperandRenderers.back().get());
   }
 
-  virtual void emitCxxActionStmts(raw_ostream &OS,
-                                  const StringRef InsnVarName) const {
+  void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
+                          StringRef RecycleVarName) const override {
     if (canMutate()) {
-      OS << "I.setDesc(TII.get(" << I->Namespace << "::" << I->TheDef->getName()
-         << "));\n";
-      OS << "    MachineInstr &NewI = I;\n";
+      OS << RecycleVarName << ".setDesc(TII.get(" << I->Namespace
+         << "::" << I->TheDef->getName() << "));\n";
+      OS << "    MachineInstr &NewI = " << RecycleVarName << ";\n";
       return;
     }
 
     // TODO: Simple permutation looks like it could be almost as common as
     //       mutation due to commutative operations.
 
     OS << "MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, "
           "I.getDebugLoc(), TII.get("
        << I->Namespace << "::" << I->TheDef->getName() << "));\n";
     for (const auto &Renderer : OperandRenderers)
-      Renderer->emitCxxRenderStmts(OS);
+      Renderer->emitCxxRenderStmts(OS, Rule);
     OS << "    MIB.setMemRefs(I.memoperands_begin(), I.memoperands_end());\n";
-    OS << "    " << InsnVarName << ".eraseFromParent();\n";
+    OS << "    " << RecycleVarName << ".eraseFromParent();\n";
     OS << "    MachineInstr &NewI = *MIB;\n";
   }
 };
 
 InstructionMatcher &RuleMatcher::addInstructionMatcher() {
   Matchers.emplace_back(new InstructionMatcher());
   return *Matchers.back();
 }
 
 template <class Kind, class... Args>
 Kind &RuleMatcher::addAction(Args &&... args) {
   Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
   return *static_cast<Kind *>(Actions.back().get());
 }
 
-void RuleMatcher::emit(raw_ostream &OS) const {
+std::string RuleMatcher::defineInsnVar(raw_ostream &OS,
+                                       const InstructionMatcher &Matcher,
+                                       StringRef Value) {
+  std::string InsnVarName = "MI" + llvm::to_string(NextInsnVarID++);
+  OS << "MachineInstr &" << InsnVarName << " = " << Value << ";\n";
+  InsnVariableNames[&Matcher] = InsnVarName;
+  return InsnVarName;
+}
+
+StringRef RuleMatcher::getInsnVarName(const InstructionMatcher &InsnMatcher) const {
+  const auto &I = InsnVariableNames.find(&InsnMatcher);
+  if (I != InsnVariableNames.end())
+    return I->second;
+  llvm_unreachable("Matched Insn was not captured in a local variable");
+}
+
+/// Emit C++ statements to check the shape of the match and capture
+/// instructions into local variables.
+void RuleMatcher::emitCxxCaptureStmts(raw_ostream &OS, StringRef Expr) {
+  assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
+  std::string InsnVarName = defineInsnVar(OS, *Matchers.front(), Expr);
+  Matchers.front()->emitCxxCaptureStmts(OS, *this, InsnVarName);
+}
+
+void RuleMatcher::emit(raw_ostream &OS) {
   if (Matchers.empty())
     llvm_unreachable("Unexpected empty matcher!");
 
   // The representation supports rules that require multiple roots such as:
   //    %ptr(p0) = ...
   //    %elt0(s32) = G_LOAD %ptr
   //    %1(p0) = G_ADD %ptr, 4
   //    %elt1(s32) = G_LOAD p0 %1
   // which could be usefully folded into:
   //    %ptr(p0) = ...
   //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
   // on some targets but we don't need to make use of that yet.
   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
-  OS << "  if (";
-  Matchers.front()->emitCxxPredicateExpr(OS, "I");
+  OS << "if ([&]() {\n";
+
+  emitCxxCaptureStmts(OS, "I");
+
+  OS << "    if (";
+  Matchers.front()->emitCxxPredicateExpr(OS, *this,
+                                         getInsnVarName(*Matchers.front()));
   OS << ") {\n";
 
   for (const auto &MA : Actions) {
-    OS << "    ";
-    MA->emitCxxActionStmts(OS, "I");
-    OS << "\n";
+    MA->emitCxxActionStmts(OS, *this, "I");
   }
 
-  OS << "    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);\n";
-  OS << "    return true;\n";
-  OS << "  }\n\n";
+  OS << "      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);\n";
+  OS << "      return true;\n";
+  OS << "    }\n";
+  OS << "    return false;\n";
+  OS << "  }()) { return true; }\n\n";
 }
 
 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
   // Rules involving more match roots have higher priority.
   if (Matchers.size() > B.Matchers.size())
     return true;
   if (Matchers.size() < B.Matchers.size())
     return false;
for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
     auto OpTyOrNone = MVTToLLT(Ty.getConcrete());
     if (!OpTyOrNone)
       return failedImport("Dst operand has an unsupported type");
 
     OperandMatcher &OM = InsnMatcher.addOperand(OpIdx, DstIOperand.Name);
     OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
     OM.addPredicate<RegisterBankOperandMatcher>(
         Target.getRegisterClass(DstIOpRec));
-    DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, "I", DstIOperand.Name);
+    DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstIOperand.Name);
     ++OpIdx;
   }
 
   // Finally match the used operands (i.e., the children of the root operator).
   for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
     auto *SrcChild = Src->getChild(i);
 
     OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, SrcChild->getName());
for (unsigned i = 0, e = Dst->getNumChildren(); i != e; ++i) {
     auto *DstChild = Dst->getChild(i);
 
     // The only non-leaf child we accept is 'bb': it's an operator because
     // BasicBlockSDNode isn't inline, but in MI it's just another operand.
     if (!DstChild->isLeaf()) {
       if (DstChild->getOperator()->isSubClassOf("SDNode")) {
         auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
         if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
-          DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, "I",
+          DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher,
                                                  DstChild->getName());
           continue;
         }
       }
       return failedImport("Dst pattern child isn't a leaf node or an MBB");
     }
 
     // Otherwise, we're looking for a bog-standard RegisterClass operand.
if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
         return failedImport("Dst operand has an unsupported type");
 
       if (ChildRec->isSubClassOf("Register")) {
         DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
         continue;
       }
 
       if (ChildRec->isSubClassOf("RegisterClass")) {
-        DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, "I",
+        DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher,
                                                DstChild->getName());
         continue;
       }
 
       if (ChildRec->isSubClassOf("ComplexPattern")) {
         const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
         if (ComplexPattern == ComplexPatternEquivs.end())
           return failedImport(
void GlobalISelEmitter::run(raw_ostream &OS) {
   OS << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
 
   OS << "#ifdef GET_GLOBALISEL_IMPL\n"
      << "bool " << Target.getName()
      << "InstructionSelector::selectImpl(MachineInstr &I) const {\n"
      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
      << "  const MachineRegisterInfo &MRI = MF.getRegInfo();\n";
 
-  for (const auto &Rule : Rules) {
+  for (auto &Rule : Rules) {
     Rule.emit(OS);
     ++NumPatternEmitted;
   }
 
   OS << "  return false;\n"
      << "}\n"
      << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
 }