[globalisel][tblgen] Add support for ComplexPatterns

Summary:
Adds a new kind of MachineOperand: MO_Placeholder.
This operand must not appear in the MIR and only exists as a way of
creating an 'uninitialized' operand until a matcher function overwrites it.

Depends on D30046, D29712

Reviewers: t.p.northover, ab, rovka, aditya_nandakumar, javed.absar, qcolombet

Reviewed By: qcolombet

Subscribers: dberris, kristof.beyls, llvm-commits

Differential Revision: https://reviews.llvm.org/D30089

llvm-svn: 297782

15 files changed, 481 insertions, 18 deletions

diff --git a/llvm/include/llvm/CodeGen/MachineOperand.h b/llvm/include/llvm/CodeGen/MachineOperand.h
index 3fc05f7784a..bde72bf7530 100644
--- a/llvm/include/llvm/CodeGen/MachineOperand.h
+++ b/llvm/include/llvm/CodeGen/MachineOperand.h
@@ -65,6 +65,7 @@ public:
     MO_CFIIndex,          ///< MCCFIInstruction index.
     MO_IntrinsicID,       ///< Intrinsic ID for ISel
     MO_Predicate,         ///< Generic predicate for ISel
+    MO_Placeholder,       ///< Placeholder for GlobalISel ComplexPattern result.
   };
 
 private:
@@ -767,6 +768,11 @@ public:
     return Op;
   }
 
+  static MachineOperand CreatePlaceholder() {
+    MachineOperand Op(MachineOperand::MO_Placeholder);
+    return Op;
+  }
+
   friend class MachineInstr;
   friend class MachineRegisterInfo;
 private:
diff --git a/llvm/include/llvm/Target/GlobalISel/SelectionDAGCompat.td b/llvm/include/llvm/Target/GlobalISel/SelectionDAGCompat.td
index 60fdf1c3dd3..a166c80bc29 100644
--- a/llvm/include/llvm/Target/GlobalISel/SelectionDAGCompat.td
+++ b/llvm/include/llvm/Target/GlobalISel/SelectionDAGCompat.td
@@ -43,3 +43,9 @@ def : GINodeEquiv<G_SREM, srem>;
 def : GINodeEquiv<G_UREM, urem>;
 
 def : GINodeEquiv<G_BR, br>;
+
+// Specifies the GlobalISel equivalents for SelectionDAG's ComplexPattern.
+// Should be used on defs that subclass GIComplexOperandMatcher<>.
+class GIComplexPatternEquiv<ComplexPattern seldag> {
+  ComplexPattern SelDAGEquivalent = seldag;
+}
diff --git a/llvm/include/llvm/Target/GlobalISel/Target.td b/llvm/include/llvm/Target/GlobalISel/Target.td
new file mode 100644
index 00000000000..b4ca2f88fb3
--- /dev/null
+++ b/llvm/include/llvm/Target/GlobalISel/Target.td
@@ -0,0 +1,55 @@
+//===- Target.td - Define GlobalISel rules -----------------*- tablegen -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the target-independent interfaces used to support
+// SelectionDAG instruction selection patterns (specified in
+// TargetSelectionDAG.td) when generating GlobalISel instruction selectors.
+//
+// This is intended as a compatibility layer, to enable reuse of target
+// descriptions written for SelectionDAG without requiring explicit GlobalISel
+// support.  It will eventually supersede SelectionDAG patterns.
+//
+//===----------------------------------------------------------------------===//
+
+// Definitions that inherit from LLT define types that will be used in the
+// GlobalISel matcher.
+class LLT;
+
+def s32 : LLT;
+
+// Defines a matcher for complex operands. This is analogous to ComplexPattern
+// from SelectionDAG.
+//
+// Definitions that inherit from this may also inherit from
+// GIComplexPatternEquiv to enable the import of SelectionDAG patterns involving
+// those ComplexPatterns.
+class GIComplexOperandMatcher<LLT type, dag operands, string matcherfn> {
+  // The expected type of the root of the match.
+  //
+  // TODO: We should probably support, any-type, any-scalar, and multiple types
+  //       in the future.
+  LLT Type = type;
+
+  // The operands that result from a successful match
+  // Should be of the form '(ops ty1, ty2, ...)' where ty1/ty2 are definitions
+  // that inherit from Operand.
+  //
+  // FIXME: Which definition is used for ty1/ty2 doesn't actually matter at the
+  //        moment. Only the number of operands is used.
+  dag Operands = operands;
+
+  // The function that determines whether the operand matches. It should be of
+  // the form:
+  //   bool select(const MatchOperand &Root, MatchOperand &Result1)
+  // and should have the same number of ResultX arguments as the number of
+  // result operands. It must return true on successful match and false
+  // otherwise. If it returns true, then all the ResultX arguments must be
+  // overwritten.
+  string MatcherFn = matcherfn;
+}
diff --git a/llvm/include/llvm/Target/Target.td b/llvm/include/llvm/Target/Target.td
index 76de6647361..3d9ca95cf9f 100644
--- a/llvm/include/llvm/Target/Target.td
+++ b/llvm/include/llvm/Target/Target.td
@@ -1357,6 +1357,11 @@ include "llvm/Target/TargetSelectionDAG.td"
 include "llvm/Target/GlobalISel/RegisterBank.td"
 
 //===----------------------------------------------------------------------===//
+// Pull in the common support for DAG isel generation.
+//
+include "llvm/Target/GlobalISel/Target.td"
+
+//===----------------------------------------------------------------------===//
 // Pull in the common support for the Global ISel DAG-based selector generation.
 //
 include "llvm/Target/GlobalISel/SelectionDAGCompat.td"
diff --git a/llvm/lib/CodeGen/MIRPrinter.cpp b/llvm/lib/CodeGen/MIRPrinter.cpp
index 469844666ec..899973488bb 100644
--- a/llvm/lib/CodeGen/MIRPrinter.cpp
+++ b/llvm/lib/CodeGen/MIRPrinter.cpp
@@ -906,6 +906,9 @@ void MIPrinter::print(const MachineOperand &Op, const TargetRegisterInfo *TRI,
        << CmpInst::getPredicateName(Pred) << ')';
     break;
   }
+  case MachineOperand::MO_Placeholder:
+    OS << "<placeholder>";
+    break;
   }
 }
 
diff --git a/llvm/lib/CodeGen/MachineInstr.cpp b/llvm/lib/CodeGen/MachineInstr.cpp
index 20ae830818a..7039aecc219 100644
--- a/llvm/lib/CodeGen/MachineInstr.cpp
+++ b/llvm/lib/CodeGen/MachineInstr.cpp
@@ -287,6 +287,8 @@ bool MachineOperand::isIdenticalTo(const MachineOperand &Other) const {
     return getIntrinsicID() == Other.getIntrinsicID();
   case MachineOperand::MO_Predicate:
     return getPredicate() == Other.getPredicate();
+  case MachineOperand::MO_Placeholder:
+    return true;
   }
   llvm_unreachable("Invalid machine operand type");
 }
@@ -335,6 +337,8 @@ hash_code llvm::hash_value(const MachineOperand &MO) {
     return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getIntrinsicID());
   case MachineOperand::MO_Predicate:
     return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getPredicate());
+  case MachineOperand::MO_Placeholder:
+    return hash_combine();
   }
   llvm_unreachable("Invalid machine operand type");
 }
@@ -504,7 +508,11 @@ void MachineOperand::print(raw_ostream &OS, ModuleSlotTracker &MST,
     auto Pred = static_cast<CmpInst::Predicate>(getPredicate());
     OS << '<' << (CmpInst::isIntPredicate(Pred) ? "intpred" : "floatpred")
        << CmpInst::getPredicateName(Pred) << '>';
+    break;
   }
+  case MachineOperand::MO_Placeholder:
+    OS << "<placeholder>";
+    break;
   }
   if (unsigned TF = getTargetFlags())
     OS << "[TF=" << TF << ']';
diff --git a/llvm/lib/Target/AArch64/AArch64InstrFormats.td b/llvm/lib/Target/AArch64/AArch64InstrFormats.td
index 6bc301abef9..d57e1db1d33 100644
--- a/llvm/lib/Target/AArch64/AArch64InstrFormats.td
+++ b/llvm/lib/Target/AArch64/AArch64InstrFormats.td
@@ -689,6 +689,10 @@ def addsub_shifted_imm64 : addsub_shifted_imm<i64>;
 def addsub_shifted_imm32_neg : addsub_shifted_imm_neg<i32>;
 def addsub_shifted_imm64_neg : addsub_shifted_imm_neg<i64>;
 
+def gi_addsub_shifted_imm32 :
+    GIComplexOperandMatcher<s32, (ops i32imm, i32imm), "selectArithImmed">,
+    GIComplexPatternEquiv<addsub_shifted_imm32>;
+
 class neg_addsub_shifted_imm<ValueType Ty>
     : Operand<Ty>, ComplexPattern<Ty, 2, "SelectNegArithImmed", [imm]> {
   let PrintMethod = "printAddSubImm";
diff --git a/llvm/lib/Target/AArch64/AArch64InstructionSelector.cpp b/llvm/lib/Target/AArch64/AArch64InstructionSelector.cpp
index 1656b5c6efc..e4f3fa86c13 100644
--- a/llvm/lib/Target/AArch64/AArch64InstructionSelector.cpp
+++ b/llvm/lib/Target/AArch64/AArch64InstructionSelector.cpp
@@ -37,13 +37,20 @@ using namespace llvm;
 #error "You shouldn't build this"
 #endif
 
+#define GET_GLOBALISEL_IMPL
 #include "AArch64GenGlobalISel.inc"
+#undef GET_GLOBALISEL_IMPL
 
 AArch64InstructionSelector::AArch64InstructionSelector(
     const AArch64TargetMachine &TM, const AArch64Subtarget &STI,
     const AArch64RegisterBankInfo &RBI)
-  : InstructionSelector(), TM(TM), STI(STI), TII(*STI.getInstrInfo()),
-      TRI(*STI.getRegisterInfo()), RBI(RBI) {}
+    : InstructionSelector(), TM(TM), STI(STI), TII(*STI.getInstrInfo()),
+      TRI(*STI.getRegisterInfo()), RBI(RBI)
+#define GET_GLOBALISEL_TEMPORARIES_INIT
+#include "AArch64GenGlobalISel.inc"
+#undef GET_GLOBALISEL_TEMPORARIES_INIT
+{
+}
 
 // FIXME: This should be target-independent, inferred from the types declared
 // for each class in the bank.
@@ -1213,3 +1220,50 @@ bool AArch64InstructionSelector::select(MachineInstr &I) const {
 
   return false;
 }
+
+/// SelectArithImmed - Select an immediate value that can be represented as
+/// a 12-bit value shifted left by either 0 or 12.  If so, return true with
+/// Val set to the 12-bit value and Shift set to the shifter operand.
+bool AArch64InstructionSelector::selectArithImmed(
+    MachineOperand &Root, MachineOperand &Result1,
+    MachineOperand &Result2) const {
+  MachineInstr &MI = *Root.getParent();
+  MachineBasicBlock &MBB = *MI.getParent();
+  MachineFunction &MF = *MBB.getParent();
+  MachineRegisterInfo &MRI = MF.getRegInfo();
+
+  // This function is called from the addsub_shifted_imm ComplexPattern,
+  // which lists [imm] as the list of opcode it's interested in, however
+  // we still need to check whether the operand is actually an immediate
+  // here because the ComplexPattern opcode list is only used in
+  // root-level opcode matching.
+  uint64_t Immed;
+  if (Root.isImm())
+    Immed = Root.getImm();
+  else if (Root.isCImm())
+    Immed = Root.getCImm()->getZExtValue();
+  else if (Root.isReg()) {
+    MachineInstr *Def = MRI.getVRegDef(Root.getReg());
+    if (Def->getOpcode() != TargetOpcode::G_CONSTANT)
+      return false;
+    Immed = Def->getOperand(1).getImm();
+  } else
+    return false;
+
+  unsigned ShiftAmt;
+
+  if (Immed >> 12 == 0) {
+    ShiftAmt = 0;
+  } else if ((Immed & 0xfff) == 0 && Immed >> 24 == 0) {
+    ShiftAmt = 12;
+    Immed = Immed >> 12;
+  } else
+    return false;
+
+  unsigned ShVal = AArch64_AM::getShifterImm(AArch64_AM::LSL, ShiftAmt);
+  Result1.ChangeToImmediate(Immed);
+  Result1.clearParent();
+  Result2.ChangeToImmediate(ShVal);
+  Result2.clearParent();
+  return true;
+}
diff --git a/llvm/lib/Target/AArch64/AArch64InstructionSelector.h b/llvm/lib/Target/AArch64/AArch64InstructionSelector.h
index 3f38c9fcd1a..6c9339e05d6 100644
--- a/llvm/lib/Target/AArch64/AArch64InstructionSelector.h
+++ b/llvm/lib/Target/AArch64/AArch64InstructionSelector.h
@@ -15,6 +15,7 @@
 #define LLVM_LIB_TARGET_AARCH64_AARCH64INSTRUCTIONSELECTOR_H
 
 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
+#include "llvm/CodeGen/MachineOperand.h"
 
 namespace llvm {
 
@@ -23,6 +24,7 @@ class AArch64RegisterBankInfo;
 class AArch64RegisterInfo;
 class AArch64Subtarget;
 class AArch64TargetMachine;
+class MachineOperand;
 
 class MachineFunction;
 class MachineRegisterInfo;
@@ -45,11 +47,20 @@ private:
   /// the patterns that don't require complex C++.
   bool selectImpl(MachineInstr &I) const;
 
+  bool selectArithImmed(MachineOperand &Root, MachineOperand &Result1,
+                        MachineOperand &Result2) const;
+
   const AArch64TargetMachine &TM;
   const AArch64Subtarget &STI;
   const AArch64InstrInfo &TII;
   const AArch64RegisterInfo &TRI;
   const AArch64RegisterBankInfo &RBI;
+
+// We declare the temporaries used by selectImpl() in the class to minimize the
+// cost of constructing placeholder values.
+#define GET_GLOBALISEL_TEMPORARIES_DECL
+#include "AArch64GenGlobalISel.inc"
+#undef GET_GLOBALISEL_TEMPORARIES_DECL
 };
 
 } // end namespace llvm
diff --git a/llvm/lib/Target/ARM/ARMExpandPseudoInsts.cpp b/llvm/lib/Target/ARM/ARMExpandPseudoInsts.cpp
index 78a9144bd32..e0aecff2633 100644
--- a/llvm/lib/Target/ARM/ARMExpandPseudoInsts.cpp
+++ b/llvm/lib/Target/ARM/ARMExpandPseudoInsts.cpp
@@ -661,6 +661,7 @@ static bool IsAnAddressOperand(const MachineOperand &MO) {
     return false;
   case MachineOperand::MO_IntrinsicID:
   case MachineOperand::MO_Predicate:
+  case MachineOperand::MO_Placeholder:
     llvm_unreachable("should not exist post-isel");
   }
   llvm_unreachable("unhandled machine operand type");
diff --git a/llvm/lib/Target/X86/X86InstructionSelector.cpp b/llvm/lib/Target/X86/X86InstructionSelector.cpp
index 0927c96abaa..2dbe4b4834e 100644
--- a/llvm/lib/Target/X86/X86InstructionSelector.cpp
+++ b/llvm/lib/Target/X86/X86InstructionSelector.cpp
@@ -35,12 +35,19 @@ using namespace llvm;
 #error "You shouldn't build this"
 #endif
 
+#define GET_GLOBALISEL_IMPL
 #include "X86GenGlobalISel.inc"
+#undef GET_GLOBALISEL_IMPL
 
 X86InstructionSelector::X86InstructionSelector(const X86Subtarget &STI,
                                                const X86RegisterBankInfo &RBI)
     : InstructionSelector(), STI(STI), TII(*STI.getInstrInfo()),
-      TRI(*STI.getRegisterInfo()), RBI(RBI) {}
+      TRI(*STI.getRegisterInfo()), RBI(RBI)
+#define GET_GLOBALISEL_TEMPORARIES_INIT
+#include "X86GenGlobalISel.inc"
+#undef GET_GLOBALISEL_TEMPORARIES_INIT
+{
+}
 
 // FIXME: This should be target-independent, inferred from the types declared
 // for each class in the bank.
diff --git a/llvm/lib/Target/X86/X86InstructionSelector.h b/llvm/lib/Target/X86/X86InstructionSelector.h
index 19f34fc6168..205c8626656 100644
--- a/llvm/lib/Target/X86/X86InstructionSelector.h
+++ b/llvm/lib/Target/X86/X86InstructionSelector.h
@@ -14,6 +14,7 @@
 #define LLVM_LIB_TARGET_X86_X86INSTRUCTIONSELECTOR_H
 
 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
+#include "llvm/CodeGen/MachineOperand.h"
 
 namespace llvm {
 
@@ -49,6 +50,10 @@ private:
   const X86InstrInfo &TII;
   const X86RegisterInfo &TRI;
   const X86RegisterBankInfo &RBI;
+
+#define GET_GLOBALISEL_TEMPORARIES_DECL
+#include "X86GenGlobalISel.inc"
+#undef GET_GLOBALISEL_TEMPORARIES_DECL
 };
 
 } // end namespace llvm
diff --git a/llvm/test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir b/llvm/test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir
index 879b45bdf6d..c41e599ec96 100644
--- a/llvm/test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir
+++ b/llvm/test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir
@@ -11,6 +11,9 @@
   define void @add_s32_gpr() { ret void }
   define void @add_s64_gpr() { ret void }
 
+  define void @add_imm_s32_gpr() { ret void }
+  define void @add_imm_s32_gpr_bb() { ret void }
+
   define void @sub_s32_gpr() { ret void }
   define void @sub_s64_gpr() { ret void }
 
@@ -204,6 +207,69 @@ body:             |
 ...
 
 ---
+# Check that we select a 32-bit GPR G_ADD into ADDWrr on GPR32.
+# Also check that we constrain the register class of the COPY to GPR32.
+# CHECK-LABEL: name: add_imm_s32_gpr
+name:            add_imm_s32_gpr
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr32sp }
+# CHECK-NEXT:  - { id: 1, class: gpr32 }
+# CHECK-NEXT:  - { id: 2, class: gpr32sp }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+  - { id: 2, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %w0
+# CHECK:    %2 = ADDWri %0, 1, 0
+body:             |
+  bb.0:
+    liveins: %w0, %w1
+
+    %0(s32) = COPY %w0
+    %1(s32) = G_CONSTANT 1
+    %2(s32) = G_ADD %0, %1
+...
+
+---
+# Check that we select a 32-bit GPR G_ADD into ADDWrr on GPR32.
+# Also check that we constrain the register class of the COPY to GPR32.
+# CHECK-LABEL: name: add_imm_s32_gpr_bb
+name:            add_imm_s32_gpr_bb
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr32sp }
+# CHECK-NEXT:  - { id: 1, class: gpr32 }
+# CHECK-NEXT:  - { id: 2, class: gpr32sp }
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: gpr }
+  - { id: 2, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = COPY %w0
+# CHECK:  bb.1:
+# CHECK:    %2 = ADDWri %0, 1, 0
+body:             |
+  bb.0:
+    liveins: %w0, %w1
+    successors: %bb.1
+
+    %0(s32) = COPY %w0
+    %1(s32) = G_CONSTANT 1
+    G_BR %bb.1
+
+  bb.1:
+    %2(s32) = G_ADD %0, %1
+...
+
+---
 # Same as add_s32_gpr, for G_SUB operations.
 # CHECK-LABEL: name: sub_s32_gpr
 name:            sub_s32_gpr
diff --git a/llvm/test/TableGen/GlobalISelEmitter.td b/llvm/test/TableGen/GlobalISelEmitter.td
index 636fd012fb3..a11e8d34c53 100644
--- a/llvm/test/TableGen/GlobalISelEmitter.td
+++ b/llvm/test/TableGen/GlobalISelEmitter.td
@@ -21,7 +21,8 @@ class I<dag OOps, dag IOps, list<dag> Pat>
 //===- Test the function definition boilerplate. --------------------------===//
 
 // CHECK: bool MyTargetInstructionSelector::selectImpl(MachineInstr &I) const {
-// CHECK: const MachineRegisterInfo &MRI = I.getParent()->getParent()->getRegInfo();
+// CHECK: MachineFunction &MF = *I.getParent()->getParent();
+// CHECK: const MachineRegisterInfo &MRI = MF.getRegInfo();
 
 //===- Test a simple pattern with regclass operands. ----------------------===//
 
diff --git a/llvm/utils/TableGen/GlobalISelEmitter.cpp b/llvm/utils/TableGen/GlobalISelEmitter.cpp
index 58504cdb8e3..e396093e4f6 100644
--- a/llvm/utils/TableGen/GlobalISelEmitter.cpp
+++ b/llvm/utils/TableGen/GlobalISelEmitter.cpp
@@ -42,6 +42,7 @@
 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/TableGenBackend.h"
 #include <string>
+#include <numeric>
 using namespace llvm;
 
 #define DEBUG_TYPE "gisel-emitter"
@@ -80,6 +81,55 @@ public:
     }
     llvm_unreachable("Unhandled LLT");
   }
+
+  const LLT &get() const { return Ty; }
+};
+
+class InstructionMatcher;
+class OperandPlaceholder {
+private:
+  enum PlaceholderKind {
+    OP_MatchReference,
+    OP_Temporary,
+  } Kind;
+
+  struct MatchReferenceData {
+    InstructionMatcher *InsnMatcher;
+    StringRef InsnVarName;
+    StringRef SymbolicName;
+  };
+
+  struct TemporaryData {
+    unsigned OpIdx;
+  };
+
+  union {
+    struct MatchReferenceData MatchReference;
+    struct TemporaryData Temporary;
+  };
+
+  OperandPlaceholder(PlaceholderKind Kind) : Kind(Kind) {}
+
+public:
+  ~OperandPlaceholder() {}
+
+  static OperandPlaceholder
+  CreateMatchReference(InstructionMatcher *InsnMatcher,
+                       const StringRef InsnVarName, const StringRef SymbolicName) {
+    OperandPlaceholder Result(OP_MatchReference);
+    Result.MatchReference.InsnMatcher = InsnMatcher;
+    Result.MatchReference.InsnVarName = InsnVarName;
+    Result.MatchReference.SymbolicName = SymbolicName;
+    return Result;
+  }
+
+  static OperandPlaceholder CreateTemporary(unsigned OpIdx) {
+    OperandPlaceholder Result(OP_Temporary);
+    Result.Temporary.OpIdx = OpIdx;
+    return Result;
+  }
+
+  void emitCxxValueExpr(raw_ostream &OS) const;
 };
 
 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
@@ -154,6 +204,7 @@ public:
   /// 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_Int,
     OPM_LLT,
     OPM_RegBank,
@@ -179,6 +230,10 @@ public:
   virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const {
     return Kind < B.Kind;
   };
+
+  /// Report the maximum number of temporary operands needed by the predicate
+  /// matcher.
+  virtual unsigned countTemporaryOperands() const { return 0; }
 };
 
 /// Generates code to check that an operand is a particular LLT.
@@ -202,6 +257,39 @@ public:
   }
 };
 
+/// 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,
+                            StringRef OperandExpr) const override {
+    OS << TheDef.getValueAsString("MatcherFn") << "(" << OperandExpr;
+    for (unsigned I = 0; I < getNumOperands(); ++I) {
+      OS << ", ";
+      OperandPlaceholder::CreateTemporary(BaseTemporaryID + I)
+          .emitCxxValueExpr(OS);
+    }
+    OS << ")";
+  }
+
+  unsigned countTemporaryOperands() const override {
+    return getNumOperands();
+  }
+};
+
 /// Generates code to check that an operand is in a particular register bank.
 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
 protected:
@@ -309,6 +397,17 @@ public:
 
     return false;
   };
+
+  /// Report the maximum number of temporary operands needed by the operand
+  /// matcher.
+  unsigned countTemporaryOperands() const {
+    return std::accumulate(
+        predicates().begin(), predicates().end(), 0,
+        [](unsigned A,
+           const std::unique_ptr<OperandPredicateMatcher> &Predicate) {
+          return A + Predicate->countTemporaryOperands();
+        });
+  }
 };
 
 /// Generates code to check a predicate on an instruction.
@@ -344,6 +443,10 @@ public:
   virtual bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
     return Kind < B.Kind;
   };
+
+  /// Report the maximum number of temporary operands needed by the predicate
+  /// matcher.
+  virtual unsigned countTemporaryOperands() const { return 0; }
 };
 
 /// Generates code to check the opcode of an instruction.
@@ -466,14 +569,40 @@ public:
 
     return false;
   };
+
+  /// Report the maximum number of temporary operands needed by the instruction
+  /// matcher.
+  unsigned countTemporaryOperands() const {
+    return std::accumulate(predicates().begin(), predicates().end(), 0,
+                           [](unsigned A,
+                              const std::unique_ptr<InstructionPredicateMatcher>
+                                  &Predicate) {
+                             return A + Predicate->countTemporaryOperands();
+                           }) +
+           std::accumulate(Operands.begin(), Operands.end(), 0,
+                           [](unsigned A, const OperandMatcher &Operand) {
+                             return A + Operand.countTemporaryOperands();
+                           });
+  }
 };
 
 //===- 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:
+    OS << "TempOp" << Temporary.OpIdx;
+    break;
+  }
+}
 
 namespace {
 class OperandRenderer {
 public:
-  enum RendererKind { OR_Copy, OR_Register };
+  enum RendererKind { OR_Copy, OR_Register, OR_ComplexPattern };
 
 protected:
   RendererKind Kind;
@@ -539,6 +668,34 @@ public:
   }
 };
 
+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 {
+    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:
@@ -701,6 +858,15 @@ public:
 
     return false;
   };
+
+  /// Report the maximum number of temporary operands needed by the rule
+  /// matcher.
+  unsigned countTemporaryOperands() const {
+    return std::accumulate(Matchers.begin(), Matchers.end(), 0,
+                           [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
+                             return A + Matcher->countTemporaryOperands();
+                           });
+  }
 };
 
 //===- GlobalISelEmitter class --------------------------------------------===//
@@ -719,6 +885,11 @@ private:
   /// This is defined using 'GINodeEquiv' in the target description.
   DenseMap<Record *, const CodeGenInstruction *> NodeEquivs;
 
+  /// Keep track of the equivalence between ComplexPattern's and
+  /// GIComplexOperandMatcher. Map entries are specified by subclassing
+  /// GIComplexPatternEquiv.
+  DenseMap<const Record *, const Record *> ComplexPatternEquivs;
+
   void gatherNodeEquivs();
   const CodeGenInstruction *findNodeEquiv(Record *N);
 
@@ -732,6 +903,14 @@ void GlobalISelEmitter::gatherNodeEquivs() {
   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
     NodeEquivs[Equiv->getValueAsDef("Node")] =
         &Target.getInstruction(Equiv->getValueAsDef("I"));
+
+  assert(ComplexPatternEquivs.empty());
+  for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
+    Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent");
+    if (!SelDAGEquiv)
+      continue;
+    ComplexPatternEquivs[SelDAGEquiv] = Equiv;
+ }
 }
 
 const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) {
@@ -749,6 +928,8 @@ static Error failedImport(const Twine &Reason) {
 }
 
 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
+  unsigned TempOpIdx = 0;
+
   // Keep track of the matchers and actions to emit.
   RuleMatcher M;
   M.addAction<DebugCommentAction>(P);
@@ -856,18 +1037,32 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
     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 failedImport("Src pattern child isn't a RegisterClass");
+      if (ChildRec->isSubClassOf("RegisterClass")) {
+        OM.addPredicate<RegisterBankOperandMatcher>(
+            Target.getRegisterClass(ChildRec));
+        continue;
+      }
 
-      OM.addPredicate<RegisterBankOperandMatcher>(
-          Target.getRegisterClass(ChildRec));
-      continue;
+      if (ChildRec->isSubClassOf("ComplexPattern")) {
+        const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
+        if (ComplexPattern == ComplexPatternEquivs.end())
+          return failedImport(
+              "SelectionDAG ComplexPattern not mapped to GlobalISel");
+
+        const auto &Predicate = OM.addPredicate<ComplexPatternOperandMatcher>(
+            *ComplexPattern->second, TempOpIdx);
+        TempOpIdx += Predicate.countTemporaryOperands();
+        continue;
+      }
+
+      return failedImport(
+          "Src pattern child def is an unsupported tablegen class");
     }
 
     return failedImport("Src pattern child is an unsupported kind");
   }
 
+  TempOpIdx = 0;
   // 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);
@@ -912,11 +1107,30 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
         continue;
       }
 
+      if (ChildRec->isSubClassOf("ComplexPattern")) {
+        const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
+        if (ComplexPattern == ComplexPatternEquivs.end())
+          return failedImport(
+              "SelectionDAG ComplexPattern not mapped to GlobalISel");
+
+        SmallVector<OperandPlaceholder, 2> RenderedOperands;
+        for (unsigned I = 0; I < InsnMatcher.getOperand(DstChild->getName())
+                                     .countTemporaryOperands();
+             ++I) {
+          RenderedOperands.push_back(OperandPlaceholder::CreateTemporary(I));
+          TempOpIdx++;
+        }
+        DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
+            *ComplexPattern->second,
+            RenderedOperands);
+        continue;
+      }
+
       return failedImport(
           "Dst pattern child def is an unsupported tablegen class");
     }
 
-    return failedImport("Src pattern child is an unsupported kind");
+    return failedImport("Dst pattern child is an unsupported kind");
   }
 
   // We're done with this pattern!  It's eligible for GISel emission; return it.
@@ -930,11 +1144,6 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
 
   emitSourceFileHeader(("Global Instruction Selector for the " +
                        Target.getName() + " target").str(), OS);
-  OS << "bool " << Target.getName()
-     << "InstructionSelector::selectImpl"
-        "(MachineInstr &I) const {\n  const MachineRegisterInfo &MRI = "
-        "I.getParent()->getParent()->getRegInfo();\n\n";
-
   std::vector<RuleMatcher> Rules;
   // Look through the SelectionDAG patterns we found, possibly emitting some.
   for (const PatternToMatch &Pat : CGP.ptms()) {
@@ -968,12 +1177,34 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
               return false;
             });
 
+  unsigned MaxTemporaries = 0;
+  for (const auto &Rule : Rules)
+    MaxTemporaries = std::max(MaxTemporaries, Rule.countTemporaryOperands());
+
+  OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n";
+  for (unsigned I = 0; I < MaxTemporaries; ++I)
+    OS << "  mutable MachineOperand TempOp" << I << ";\n";
+  OS << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
+
+  OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n";
+  for (unsigned I = 0; I < MaxTemporaries; ++I)
+    OS << ", TempOp" << I << "(MachineOperand::CreatePlaceholder())\n";
+  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) {
     Rule.emit(OS);
     ++NumPatternEmitted;
   }
 
-  OS << "  return false;\n}\n";
+  OS << "  return false;\n"
+     << "}\n"
+     << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
 }
 
 } // end anonymous namespace