[globalisel] Decouple src pattern operands from dst pattern operands.

[dsanders]

Summary

This isn't testable for AArch64 by itself so this patch also adds
support for constant immediates in the pattern and physical
register uses in the result.

The new IntOperandMatcher matches the constant in patterns such as
'(set $rd:GPR32, (G_XOR $rs:GPR32, -1))'. It's always safe to fold
immediates into an instruction so this is the first rule that will match
across multiple BB's.

The Renderer hierarchy is responsible for adding operands to the result
instruction. Renderers can copy operands (CopyRenderer) or add physical
registers (in particular %wzr and %xzr) to the result instruction
in any order (OperandMatchers now import the operand names from
SelectionDAG to allow renderers to access any operand). This allows us to
emit the result instruction for:

%1 = G_XOR %0, -1 --> %1 = ORNWrr %wzr, %0
%1 = G_XOR -1, %0 --> %1 = ORNWrr %wzr, %0

although the latter is untested since the matcher/importer has not been
taught about commutativity yet.

Added BuildMIAction which can build new instructions and mutate them where
possible. W.r.t the mutation aspect, MatchActions are now told the name of
an instruction they can recycle and BuildMIAction will emit mutation code
when the renderers are appropriate. They are appropriate when all operands
are rendered using CopyRenderer and the indices are the same as the matcher.
This currently assumes that all operands have at least one matcher.

Finally, this change also fixes a crash in
AArch64InstructionSelector::select() caused by an immediate operand
passing isImm() rather than isCImm(). This was uncovered by the other
changes and was detected by existing tests.

Depends on D29711

[dsanders]

This is currently missing a tablegen test. I'll add that soon.

[dsanders]

Tablegen test case and a fixed a compile error.

[rovka]

utils/TableGen/GlobalISelEmitter.cpp

449

Do you really need typename here or is it a leftover?

513

This and AddRegisterRenderer could each use a comment (either here or in the RendererKind enum).

595

Typo: built

636

Nit: Since emitCxxRenderStmts may emit more than one statement in the general case, I would move this into the function itself and let it deal with all the indentation and newlines that are needed.

862

This is very copy-pasted from above, would it make sense to extract it into, say, a processChildren() taking a Handler of some sort? Only if you think it won't make things more difficult in the future, ofc.

876

...or an MBB :)

[dsanders]

Addressed the review comments.

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

449

It's a copy/paste from predicates_begin(). It's needed there but isn't here.

862

The reason for separating the two is that the source pattern and destination pattern have different jobs and support different kinds of DAG. It's also possible for the two patterns to be very different in structure. For example:

 (add (mul $src1:GPR32, $src2:GPR32), $src3:GPR32)
=>
 (SMADDLrrr $src1:GPR32, $src2:GPR32, $src3:GPR32)

It might be possible to turn it into a processChildren() + handler setup. I'm going to be trying to turn this into a proper tree walker soon to support nested instructions.

876

Thanks. I should have changed that before splitting the loop into two :-)

[dsanders]

Just to double-check, is this ok to commit?

[rovka]

LGTM.

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

 /// This class is responsible for selecting machine instructions.
 /// It's implemented by the target. It's used by the InstructionSelect pass.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
 #define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
 
+#include <cstdint>
+
 namespace llvm {
 class MachineInstr;
+class MachineOperand;
+class MachineRegisterInfo;
 class RegisterBankInfo;
 class TargetInstrInfo;
 class TargetRegisterInfo;
 
 /// Provides the logic to select generic machine instructions.
 class InstructionSelector {
 public:
   virtual ~InstructionSelector() {}
protected:
   ///
   // FIXME: Not all instructions have the same number of operands. We should
   // probably expose a constrain helper per operand and let the target selector
   // 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;
 };
 
 } // End namespace llvm.
 
 #endif

lib/CodeGen/GlobalISel/InstructionSelect.cpp

if (!TPC.isGlobalISelAbortEnabled() && (Failed || MF.size() != NumBlocks)) {
     MF.getProperties().set(MachineFunctionProperties::Property::FailedISel);
     return false;
   }
   assert(MF.size() == NumBlocks && "Inserting blocks is not supported yet");
 
   // FIXME: Should we accurately track changes?
   return true;
 }
+
+bool InstructionSelector::isOperandImmEqual(
+    const MachineOperand &MO, int64_t Value,
+    const MachineRegisterInfo &MRI) const {
+  // TODO: We should also test isImm() and isCImm() too but this isn't required
+  //       until a DAGCombine equivalent is implemented.
+
+  if (MO.isReg()) {
+    MachineInstr *Def = MRI.getVRegDef(MO.getReg());
+    if (Def->getOpcode() != TargetOpcode::G_CONSTANT)
+      return false;
+    assert(Def->getOperand(1).isImm() && "G_CONSTANT values must be constants");
+    return Def->getOperand(1).getImm() == Value;
+  }
+
+  return false;
+}

lib/Target/AArch64/AArch64InstructionSelector.cpp

if (isFP) {
         DEBUG(dbgs() << "Failed to constrain G_FCONSTANT def operand\n");
         return false;
       }
 
       MachineOperand &ImmOp = I.getOperand(1);
       // FIXME: Is going through int64_t always correct?
       ImmOp.ChangeToImmediate(
           ImmOp.getFPImm()->getValueAPF().bitcastToAPInt().getZExtValue());
-    } else {
+    } else if (I.getOperand(1).isCImm()) {
       uint64_t Val = I.getOperand(1).getCImm()->getZExtValue();
       I.getOperand(1).ChangeToImmediate(Val);
+    } else if (I.getOperand(1).isImm()) {
+      uint64_t Val = I.getOperand(1).getImm();
+      I.getOperand(1).ChangeToImmediate(Val);
     }
 
     constrainSelectedInstRegOperands(I, TII, TRI, RBI);
     return true;
   }
 
   case TargetOpcode::G_FRAME_INDEX: {
     // allocas and G_FRAME_INDEX are only supported in addrspace(0).

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

+# RUN: llc -O0 -mtriple=aarch64-apple-ios -run-pass=instruction-select -verify-machineinstrs -global-isel %s -o - | FileCheck %s -check-prefix=CHECK -check-prefix=IOS
+# RUN: llc -O0 -mtriple=aarch64-linux-gnu -run-pass=instruction-select -verify-machineinstrs -global-isel %s -o - | FileCheck %s -check-prefix=CHECK -check-prefix=LINUX-DEFAULT
+# RUN: llc -O0 -mtriple=aarch64-linux-gnu -relocation-model=pic -run-pass=instruction-select -verify-machineinstrs -global-isel %s -o - | FileCheck %s -check-prefix=CHECK -check-prefix=LINUX-PIC
+
+# Test the instruction selector.
+# As we support more instructions, we need to split this up.
+
+--- |
+  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 }
+  define void @xor_constant_n1_s32_gpr_2bb() { ret void }
+
+...
+
+---
+# Check that we select a 32-bit GPR G_XOR into EORWrr on GPR32.
+# Also check that we constrain the register class of the COPY to GPR32.
+# CHECK-LABEL: name: xor_s32_gpr
+name:            xor_s32_gpr
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr32 }
+# CHECK-NEXT:  - { id: 1, class: gpr32 }
+# CHECK-NEXT:  - { id: 2, class: gpr32 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+  - { id: 2, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %w0
+# CHECK:    %1 = COPY %w1
+# CHECK:    %2 = EORWrr %0, %1
+body:             |
+  bb.0:
+    liveins: %w0, %w1
+
+    %0(s32) = COPY %w0
+    %1(s32) = COPY %w1
+    %2(s32) = G_XOR %0, %1
+...
+
+---
+# Same as xor_s64_gpr, for 64-bit operations.
+# CHECK-LABEL: name: xor_s64_gpr
+name:            xor_s64_gpr
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr64 }
+# CHECK-NEXT:  - { id: 1, class: gpr64 }
+# CHECK-NEXT:  - { id: 2, class: gpr64 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+  - { id: 2, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %x0
+# CHECK:    %1 = COPY %x1
+# CHECK:    %2 = EORXrr %0, %1
+body:             |
+  bb.0:
+    liveins: %x0, %x1
+
+    %0(s64) = COPY %x0
+    %1(s64) = COPY %x1
+    %2(s64) = G_XOR %0, %1
+...
+
+---
+# Check that we select a 32-bit GPR G_XOR into EORWrr on GPR32.
+# Also check that we constrain the register class of the COPY to GPR32.
+# CHECK-LABEL: name: xor_constant_n1_s32_gpr
+name:            xor_constant_n1_s32_gpr
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr32 }
+# CHECK-NEXT:  - { id: 1, class: gpr32 }
+# CHECK-NEXT:  - { id: 2, class: gpr32 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+  - { id: 2, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %w0
+# CHECK:    %2 = ORNWrr %wzr, %0
+body:             |
+  bb.0:
+    liveins: %w0
+
+    %0(s32) = COPY %w0
+    %1(s32) = G_CONSTANT -1
+    %2(s32) = G_XOR %0, %1
+...
+
+---
+# Same as xor_constant_n1_s64_gpr, for 64-bit operations.
+# CHECK-LABEL: name: xor_constant_n1_s64_gpr
+name:            xor_constant_n1_s64_gpr
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr64 }
+# CHECK-NEXT:  - { id: 1, class: gpr64 }
+# CHECK-NEXT:  - { id: 2, class: gpr64 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+  - { id: 2, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %x0
+# CHECK:    %2 = ORNXrr %xzr, %0
+body:             |
+  bb.0:
+    liveins: %x0
+
+    %0(s64) = COPY %x0
+    %1(s64) = G_CONSTANT -1
+    %2(s64) = G_XOR %0, %1
+...
+
+---
+# Check that we can obtain constants from other basic blocks.
+# CHECK-LABEL: name: xor_constant_n1_s32_gpr_2bb
+name:            xor_constant_n1_s32_gpr_2bb
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr32 }
+# CHECK-NEXT:  - { id: 1, class: gpr32 }
+# CHECK-NEXT:  - { id: 2, class: gpr32 }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+  - { id: 2, class: gpr }
+
+# CHECK:  body:
+# CHECK:    B %bb.1
+# CHECK:    %0 = COPY %w0
+# CHECK:    %2 = ORNWrr %wzr, %0
+
+body:             |
+  bb.0:
+    liveins: %w0, %w1
+    successors: %bb.1
+    %1(s32) = G_CONSTANT -1
+    G_BR %bb.1
+  bb.1:
+    %0(s32) = COPY %w0
+    %2(s32) = G_XOR %0, %1
+...
+

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

--- |
 
   define void @sub_s32_gpr() { ret void }
   define void @sub_s64_gpr() { ret void }
 
   define void @or_s32_gpr() { ret void }
   define void @or_s64_gpr() { ret void }
   define void @or_v2s32_fpr() { ret void }
 
-  define void @xor_s32_gpr() { ret void }
-  define void @xor_s64_gpr() { ret void }
-
   define void @and_s32_gpr() { ret void }
   define void @and_s64_gpr() { ret void }
 
   define void @shl_s32_gpr() { ret void }
   define void @shl_s64_gpr() { ret void }
 
   define void @lshr_s32_gpr() { ret void }
   define void @lshr_s64_gpr() { ret void }
bb.0:
     liveins: %d0, %d1
 
       %0(<2 x s32>) = COPY %d0
       %1(<2 x s32>) = COPY %d1
       %2(<2 x s32>) = G_OR %0, %1
 ...
 
 ---
-# Same as add_s32_gpr, for G_XOR operations.
-# CHECK-LABEL: name: xor_s32_gpr
-name:            xor_s32_gpr
-legalized:       true
-regBankSelected: true
-
-# CHECK:      registers:
-# CHECK-NEXT:  - { id: 0, class: gpr32 }
-# CHECK-NEXT:  - { id: 1, class: gpr32 }
-# CHECK-NEXT:  - { id: 2, class: gpr32 }
-registers:
-  - { id: 0, class: gpr }
-  - { id: 1, class: gpr }
-  - { id: 2, class: gpr }
-
-# CHECK:  body:
-# CHECK:    %0 = COPY %w0
-# CHECK:    %1 = COPY %w1
-# CHECK:    %2 = EORWrr %0, %1
-body:             |
-  bb.0:
-    liveins: %w0, %w1
-
-    %0(s32) = COPY %w0
-    %1(s32) = COPY %w1
-    %2(s32) = G_XOR %0, %1
-...
-
----
-# Same as add_s64_gpr, for G_XOR operations.
-# CHECK-LABEL: name: xor_s64_gpr
-name:            xor_s64_gpr
-legalized:       true
-regBankSelected: true
-
-# CHECK:      registers:
-# CHECK-NEXT:  - { id: 0, class: gpr64 }
-# CHECK-NEXT:  - { id: 1, class: gpr64 }
-# CHECK-NEXT:  - { id: 2, class: gpr64 }
-registers:
-  - { id: 0, class: gpr }
-  - { id: 1, class: gpr }
-  - { id: 2, class: gpr }
-
-# CHECK:  body:
-# CHECK:    %0 = COPY %x0
-# CHECK:    %1 = COPY %x1
-# CHECK:    %2 = EORXrr %0, %1
-body:             |
-  bb.0:
-    liveins: %x0, %x1
-
-    %0(s64) = COPY %x0
-    %1(s64) = COPY %x1
-    %2(s64) = G_XOR %0, %1
-...
-
----
 # Same as add_s32_gpr, for G_AND operations.
 # CHECK-LABEL: name: and_s32_gpr
 name:            and_s32_gpr
 legalized:       true
 regBankSelected: true
 
 # CHECK:      registers:
 # CHECK-NEXT:  - { id: 0, class: gpr32 }

utils/TableGen/GlobalISelEmitter.cpp

public:
   ///
   /// When all more important distinctions between rules are equal, the order of
   /// these definitions is the order the matches will be attempted.
   ///
   /// The only one that's known to matter at the moment is that OPM_Int must
   /// have priority over OPM_RegBank. This is because gMIR represents constants
   /// as a register def'd by a G_CONSTANT instruction.
   enum PredicateKind {
+    OPM_Int,
     OPM_LLT,
     OPM_RegBank,
     OPM_MBB,
   };
 
 protected:
   PredicateKind Kind;
 
public:
   }
 
   void emitCxxPredicateExpr(raw_ostream &OS,
                             const 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,
+                            const 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:
   unsigned OpIdx;
+  std::string SymbolicName;
 
 public:
-  OperandMatcher(unsigned OpIdx) : OpIdx(OpIdx) {}
+  OperandMatcher(unsigned OpIdx, const std::string &SymbolicName)
+      : 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(" + std::to_string(OpIdx) + ")").str();
   }
 
   /// 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 {
-    OS << "(/* Operand " << OpIdx << " */ ";
+    OS << "(/* ";
+    if (SymbolicName.empty())
+      OS << "Operand " << OpIdx;
+    else
+      OS << SymbolicName;
+    OS << " */ ";
     emitCxxPredicateListExpr(OS, 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 {
public:
   void emitCxxPredicateExpr(raw_ostream &OS,
                             const StringRef InsnVarName) const override {
     OS << InsnVarName << ".getOpcode() == " << I->Namespace
        << "::" << I->TheDef->getName();
   }
 
   /// Compare the priority of this object and B.
   ///
-  /// Returns true if  is more important than B.
+  /// Returns true if this object is more important than B.
   bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
     if (InstructionPredicateMatcher::isHigherPriorityThan(B))
       return true;
 
     // Prioritize opcodes for cosmetic reasons in the generated source. Although
     // this is cosmetic at the moment, we may want to drive a similar ordering
     // using instruction frequency information to improve compile time.
     if (const InstructionOpcodeMatcher *BO =
             dyn_cast<InstructionOpcodeMatcher>(&B))
       return I->TheDef->getName() < BO->I->TheDef->getName();
 
     return false;
   };
 };
 
 /// Generates code to check that a set of predicates and operands match for a
 /// particular instruction.
 ///
 /// Typical predicates include:
 /// * Has a specific opcode.
 /// * Has an nsw/nuw flag or doesn't.
 class InstructionMatcher
     : public PredicateListMatcher<InstructionPredicateMatcher> {
 protected:
-  std::vector<OperandMatcher> Operands;
+  typedef std::vector<OperandMatcher> OperandVec;
+
+  /// 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) {
-    Operands.emplace_back(OpIdx);
+  OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName) {
+    Operands.emplace_back(OpIdx, SymbolicName);
     return Operands.back();
   }
 
+  const OperandMatcher &getOperand(const 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;
+    llvm_unreachable("Failed to lookup operand");
+  }
+
+  unsigned getNumOperands() const { return Operands.size(); }
+  typename OperandVec::const_iterator operands_begin() const {
+    return Operands.begin();
+  }
+  typename OperandVec::const_iterator operands_end() const {
+    return Operands.end();
+  }
+  iterator_range<typename OperandVec::const_iterator> operands() const {
+    return make_range(operands_begin(), operands_end());
+  }
+
   /// 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, const StringRef InsnVarName) const {
     emitCxxPredicateListExpr(OS, InsnVarName);
     for (const auto &Operand : Operands) {
       OS << " &&\n(";
       Operand.emitCxxPredicateExpr(OS, InsnVarName);
       OS << ")";
public:
   };
 };
 
 } // end anonymous namespace
 
 //===- Actions ------------------------------------------------------------===//
 
 namespace {
+class OperandRenderer {
+public:
+  enum RendererKind { OR_Copy, OR_Register };
+
+protected:
+  RendererKind Kind;
+
+public:
+  OperandRenderer(RendererKind Kind) : Kind(Kind) {}
+  virtual ~OperandRenderer() {}
+
+  RendererKind getKind() const { return Kind; }
+
+  virtual void emitCxxRenderStmts(raw_ostream &OS) const = 0;
+};
+
+class CopyRenderer : public OperandRenderer {
+protected:
+  const InstructionMatcher &Matched;
+  const StringRef InsnVarName;
+  const StringRef SymbolicName;
+
+public:
+  CopyRenderer(const InstructionMatcher &Matched, const StringRef InsnVarName,
+               const StringRef SymbolicName)
+      : OperandRenderer(OR_Copy), Matched(Matched), InsnVarName(InsnVarName),
+        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);
+    OS << "MIB.add(" << OperandExpr << "/*" << SymbolicName << "*/);";
+  }
+};
+
+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 {
+    OS << "MIB.addReg(" << RegisterDef->getValueAsString("Namespace")
+       << "::" << RegisterDef->getName() << ");";
+  }
+};
+
 /// 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() {}
-  virtual void emitCxxActionStmts(raw_ostream &OS) const = 0;
+
+  /// 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;
 };
 
 /// 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) {}
 
   virtual void emitCxxActionStmts(raw_ostream &OS) const {
     OS << "// " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern();
   }
 };
 
-/// Generates code to set the opcode (really, the MCInstrDesc) of a matched
-/// instruction to a given Instruction.
-class MutateOpcodeAction : public MatchAction {
+/// 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;
+  const InstructionMatcher &Matched;
+  std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
+
+  /// True if the instruction can be build solely by mutating the opcode.
+  bool canMutate() const {
+    for (const auto &Renderer : enumerate(OperandRenderers)) {
+      if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.Value)) {
+        if (Matched.getOperand(Copy->getSymbolicName()).getOperandIndex() !=
+            Renderer.Index)
+          return false;
+      } else
+        return false;
+    }
+
+    return true;
+  }
 
 public:
-  MutateOpcodeAction(const CodeGenInstruction *I) : I(I) {}
+  BuildMIAction(const CodeGenInstruction *I, const InstructionMatcher &Matched)
+      : I(I), Matched(Matched) {}
 
-  virtual void emitCxxActionStmts(raw_ostream &OS) const {
+  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 {
+    if (canMutate()) {
       OS << "I.setDesc(TII.get(" << I->Namespace << "::" << I->TheDef->getName()
-       << "));";
+         << "));\n";
+      OS << "    MachineInstr &NewI = I;\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) {
+      OS << "    ";
+      Renderer->emitCxxRenderStmts(OS);
+      OS << "\n";
+    }
+    OS << "    MIB.setMemRefs(I.memoperands_begin(), I.memoperands_end());\n";
+    OS << "    " << InsnVarName << ".eraseFromParent();\n";
+    OS << "    MachineInstr &NewI = *MIB;\n";
   }
 };
 
 /// 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
void emit(raw_ostream &OS) const {
     // 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 << ") {\n";
 
     for (const auto &MA : Actions) {
       OS << "    ";
-      MA->emitCxxActionStmts(OS);
+      MA->emitCxxActionStmts(OS, "I");
       OS << "\n";
     }
 
-    OS << "    constrainSelectedInstRegOperands(I, TII, TRI, RBI);\n";
+    OS << "    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);\n";
     OS << "    return true;\n";
     OS << "  }\n\n";
   }
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   bool isHigherPriorityThan(const RuleMatcher &B) const {
GlobalISelEmitter::runOnPattern(std::vector<RuleMatcher> &Rules,
   auto SrcGIOrNull = findNodeEquiv(Src->getOperator());
   if (!SrcGIOrNull)
     return SkipReason{"Pattern operator lacks an equivalent Instruction"};
   auto &SrcGI = *SrcGIOrNull;
 
   // The operators look good: match the opcode and mutate it to the new one.
   InstructionMatcher &InsnMatcher = M.addInstructionMatcher();
   InsnMatcher.addPredicate<InstructionOpcodeMatcher>(&SrcGI);
-  M.addAction<MutateOpcodeAction>(&DstI);
+  auto &DstMIBuilder = M.addAction<BuildMIAction>(&DstI, InsnMatcher);
 
   // Next, analyze the children, only accepting patterns that don't require
   // any change to operands.
   if (Src->getNumChildren() != Dst->getNumChildren())
     return SkipReason{"Src/dst patterns have a different # of children"};
 
   unsigned OpIdx = 0;
 
   // Start with the defined operands (i.e., the results of the root operator).
   if (DstI.Operands.NumDefs != Src->getExtTypes().size())
     return SkipReason{"Src pattern results and dst MI defs are different"};
 
   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
-    Record *DstIOpRec = DstI.Operands[OpIdx].Rec;
+    const auto &DstIOperand = DstI.Operands[OpIdx];
+    Record *DstIOpRec = DstIOperand.Rec;
     if (!DstIOpRec->isSubClassOf("RegisterClass"))
       return SkipReason{"Dst MI def isn't a register class"};
 
     auto OpTyOrNone = MVTToLLT(Ty.getConcrete());
     if (!OpTyOrNone)
       return SkipReason{"Dst operand has an unsupported type"};
 
-    OperandMatcher &OM = InsnMatcher.addOperand(OpIdx);
+    OperandMatcher &OM = InsnMatcher.addOperand(OpIdx, DstIOperand.Name);
     OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
     OM.addPredicate<RegisterBankOperandMatcher>(
         Target.getRegisterClass(DstIOpRec));
+    DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, "I", 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);
-    auto *DstChild = Dst->getChild(i);
 
-    // Patterns can reorder operands.  Ignore those for now.
-    if (SrcChild->getName() != DstChild->getName())
-      return SkipReason{"Src/dst pattern children not in same order"};
+    OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, SrcChild->getName());
 
     // 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 (!SrcChild->isLeaf()) {
-      if (DstChild->isLeaf() ||
-          SrcChild->getOperator() != DstChild->getOperator())
-        return SkipReason{"Src/dst pattern child operator mismatch"};
-
       if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
         auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
         if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
-          InsnMatcher.addOperand(OpIdx++).addPredicate<MBBOperandMatcher>();
+          OM.addPredicate<MBBOperandMatcher>();
           continue;
         }
       }
-      return SkipReason{"Src pattern child isn't a leaf node"};
+      return SkipReason{"Src pattern child isn't a leaf node or an MBB"};
     }
 
-    if (SrcChild->getLeafValue() != DstChild->getLeafValue())
-      return SkipReason{"Src/dst pattern child leaf mismatch"};
-
-    // Otherwise, we're looking for a bog-standard RegisterClass operand.
     if (SrcChild->hasAnyPredicate())
       return SkipReason{"Src pattern child has predicate"};
-    auto *ChildRec = cast<DefInit>(SrcChild->getLeafValue())->getDef();
+
+    if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
+      OM.addPredicate<IntOperandMatcher>(ChildInt->getValue());
+      continue;
+    }
+
+    if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
+      auto *ChildRec = ChildDefInit->getDef();
+
+      // Otherwise, we're looking for a bog-standard RegisterClass operand.
       if (!ChildRec->isSubClassOf("RegisterClass"))
         return SkipReason{"Src pattern child isn't a RegisterClass"};
 
       ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
       if (ChildTypes.size() != 1)
         return SkipReason{"Src pattern child has multiple results"};
 
       auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
       if (!OpTyOrNone)
         return SkipReason{"Src operand has an unsupported type"};
 
-    OperandMatcher &OM = InsnMatcher.addOperand(OpIdx);
       OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
       OM.addPredicate<RegisterBankOperandMatcher>(
           Target.getRegisterClass(ChildRec));
-    ++OpIdx;
+      continue;
+    }
+
+    return SkipReason{"Src pattern child is an unsupported kind"};
+  }
+
+  // Finally render the used operands (i.e., the children of the root operator).
+  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",
+                                                 DstChild->getName());
+          continue;
+        }
+      }
+      return SkipReason{"Dst pattern child isn't a leaf node"};
+    }
+
+    // Otherwise, we're looking for a bog-standard RegisterClass operand.
+    if (DstChild->hasAnyPredicate())
+      return SkipReason{"Dst pattern child has predicate"};
+
+    if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
+      auto *ChildRec = ChildDefInit->getDef();
+
+      ArrayRef<EEVT::TypeSet> ChildTypes = DstChild->getExtTypes();
+      if (ChildTypes.size() != 1)
+        return SkipReason{"Dst pattern child has multiple results"};
+
+      auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
+      if (!OpTyOrNone)
+        return SkipReason{"Dst operand has an unsupported type"};
+
+      if (ChildRec->isSubClassOf("Register")) {
+        DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
+        continue;
+      }
+
+      if (ChildRec->isSubClassOf("RegisterClass")) {
+        DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, "I",
+                                               DstChild->getName());
+        continue;
+      }
+
+      return SkipReason{
+          "Dst pattern child def is an unsupported tablegen class"};
+    }
+
+    return SkipReason{"Src pattern child is an unsupported kind"};
   }
 
   Rules.push_back(std::move(M));
   ++NumPatternImported;
 
   return None;
 }