[globalisel][tablegen] Add support for importing 'imm' operands.

[dsanders]

Summary

This patch enables the import of rules containing 'imm' operands that do not
constrain the acceptable values using predicates. Support for ImmLeaf will
arrive in a later patch.

Depends on D35681

[rovka]

Seems fine.

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

352

You could also assert that the OldInsn is a G_CONSTANT.

353

It would be really easy to also handle .isImm() operands here. They can't appear if you always use MachineIRBuilder, but IIRC the MIRParser sometimes introduces them, so it wouldn't hurt to support them to avoid surprising people when they write tests.

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

30

Nit: Maybe test a negative constant instead, to make sure we do the right extension?

[dsanders]

Added assertion.
Added support for isImm() case.
Switched to negative number on the i32 test case.

• Fixed the issue preventing tablegen from matching either case and killed the C++ that made the test pass.
• Fixed a priority bug that was revealed after that fix. G_CONSTANT instructions need to be less important than specific constants.
  • I'm thinking that I should replace ConstantIntOperandMatcher with an appropriate instruction/opcode/literal-int matcher combination. I see no good reason for it to be special at this point. I'll leave that for another patch though.

[dsanders]

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

353

Ok.

IIRC the MIRParser sometimes introduces them, so it
wouldn't hurt to support them to avoid surprising people
when they write tests.

You get an isImm() operand when you write '123' instead of 'i32 123'.

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

30

Done. This revealed that a small mistake was preventing my code from being executed. The GIM_CheckNumOperands was checking for 1 operand instead of 2 (because Src had no children). The test only passed because the C++ was catching it. I've fixed this and killed the C++ that was handling it. I've also fixed a bug this revealed where ADD8ri had higher priority than INC8r on X86

This also turned up a small inconsistency between the old C++ and tablegen. The C++ uses ZExt but TableGen uses SExt. I haven't decided how to fix this one yet. For AArch64, I should presumably switch to ZExt but this is the wrong thing to do on some targets such as Mips where all register-width integers are signed.

[dsanders]

The C++ uses ZExt but TableGen uses SExt. I haven't decided how to fix this one yet.

I've mostly deferred this problem to a later date but I have made slight tweaks
to make the zero-extension explicit by renaming GIR_CopyConstantAsImm to
GIR_CopyConstantAsUImm. It's up to tablegen to decide whether to sign-extend or
zero-extend the constant but right now it can only choose zero-extend.

[rovka]

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

353

You forgot the == G_CONSTANT

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

30

Is there a reason why the old code would ZExt instead of SExt? SExt seems more natural in this context, but I admittedly haven't thought too much about it.

[dsanders]

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

353

Thanks. I guess I was seeing what I expected to see :-)

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

30

I'm not sure at the moment. It could be that it makes no difference either way aside from targets like Mips which specifies the value of bits that don't physically exist in an implementation (values are theoretically sign-extended to infinite-width) and relies on this for 32-bit code to work correctly on a 64-bit CPU.

One observation from the patches I've been working on this week is that ImmLeaf's sign-extend the constant internally so it would make sense for the same operator without any predicates (imm) to do the same. Unfortunately, that argument can be used the other way if you start from the PatFrag's which start with an SDNode and frequently zero-extend it.

[dsanders]

Fix == TargetOpcode::G_CONSTANT nit.

[dsanders]

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

30

SelectionDAG doesn't seem to extend at all for imm without predicates (it just morphs the node from ISD::Constant to AArch64::MOVi32imm, leaving the operands untouched) so I think it's safe to say it doesn't matter what we pick here.

Do you have a preference? If not, I'll stick with the zero-extend for now.

[rovka]

Well, considering that Mips prefers SExt and nothing (that we're aware of) prefers ZExt, it might be better to just use SExt from the start. But if you're feeling lazy ZExt is fine too :)

[dsanders]

That makes sense to me, I'll switch it over to sign-extend.

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

enum {
   /// - InsnID - Instruction ID to modify
   /// - Imm - The immediate to add
   GIR_AddImm,
   /// Render complex operands to the specified instruction
   /// - InsnID - Instruction ID to modify
   /// - RendererID - The renderer to call
   GIR_ComplexRenderer,
 
+  /// Render a G_CONSTANT operator as a zero-extended immediate.
+  /// - NewInsnID - Instruction ID to modify
+  /// - OldInsnID - Instruction ID to copy from
+  /// The operand index is implicitly 1.
+  GIR_CopyConstantAsUImm,
+
   /// Constrain an instruction operand to a register class.
   /// - InsnID - Instruction ID to modify
   /// - OpIdx - Operand index
   /// - RCEnum - Register class enumeration value
   GIR_ConstrainOperandRC,
   /// Constrain an instructions operands according to the instruction
   /// description.
   /// - InsnID - Instruction ID to modify

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

case GIR_ComplexRenderer: {
       int64_t RendererID = MatchTable[CurrentIdx++];
       assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
       State.Renderers[RendererID](OutMIs[InsnID]);
       DEBUG(dbgs() << CurrentIdx << ": GIR_ComplexRenderer(OutMIs[" << InsnID
                    << "], " << RendererID << ")\n");
       break;
     }
 
+    case GIR_CopyConstantAsUImm: {
+      int64_t NewInsnID = MatchTable[CurrentIdx++];
+      int64_t OldInsnID = MatchTable[CurrentIdx++];
+      assert(OutMIs[NewInsnID] && "Attempted to add to undefined instruction");
+      assert(State.MIs[OldInsnID]->getOpcode() && "Expected G_CONSTANT");
+      if (State.MIs[OldInsnID]->getOperand(1).isCImm()) {
+        // FIXME: Some targets (e.g. Mips) should sign-extend instead of zero extend.
+        OutMIs[NewInsnID].addImm(
+            State.MIs[OldInsnID]->getOperand(1).getCImm()->getZExtValue());
+      } else if (State.MIs[OldInsnID]->getOperand(1).isImm())
+        OutMIs[NewInsnID].add(State.MIs[OldInsnID]->getOperand(1));
+      else
+        llvm_unreachable("Expected Imm or CImm operand");
+      DEBUG(dbgs() << CurrentIdx << ": GIR_CopyConstantAsUImm(OutMIs[" << NewInsnID
+                   << "], MIs[" << OldInsnID << "])\n");
+      break;
+    }
+
     case GIR_ConstrainOperandRC: {
       int64_t InsnID = MatchTable[CurrentIdx++];
       int64_t OpIdx = MatchTable[CurrentIdx++];
       int64_t RCEnum = MatchTable[CurrentIdx++];
       assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
       constrainOperandRegToRegClass(*OutMIs[InsnID].getInstr(), OpIdx,
                                     *TRI.getRegClass(RCEnum), TII, TRI, RBI);
       DEBUG(dbgs() << CurrentIdx << ": GIR_ConstrainOperandRC(OutMIs[" << InsnID

include/llvm/Target/GlobalISel/SelectionDAGCompat.td

 // These are defined in the same order as the G_* instructions.
 def : GINodeEquiv<G_ANYEXT, anyext>;
 def : GINodeEquiv<G_SEXT, sext>;
 def : GINodeEquiv<G_ZEXT, zext>;
 def : GINodeEquiv<G_TRUNC, trunc>;
 def : GINodeEquiv<G_BITCAST, bitconvert>;
 // G_INTTOPTR - SelectionDAG has no equivalent.
 // G_PTRTOINT - SelectionDAG has no equivalent.
-// G_CONSTANT - Not needed since constants aren't operators.
+def : GINodeEquiv<G_CONSTANT, imm>;
 // G_FCONSTANT - Not needed since constants aren't operators.
 def : GINodeEquiv<G_ADD, add>;
 def : GINodeEquiv<G_SUB, sub>;
 def : GINodeEquiv<G_MUL, mul>;
 def : GINodeEquiv<G_SDIV, sdiv>;
 def : GINodeEquiv<G_UDIV, udiv>;
 def : GINodeEquiv<G_SREM, srem>;
 def : GINodeEquiv<G_UREM, urem>;

lib/Target/AArch64/AArch64InstructionSelector.cpp

if (isFP) {
       }
 
       if (RB.getID() != AArch64::FPRRegBankID) {
         DEBUG(dbgs() << "Unable to materialize FP " << Ty
                      << " constant on bank: " << RB << ", expected: FPR\n");
         return false;
       }
     } else {
-      if (Ty != s32 && Ty != s64 && Ty != p0) {
+      // s32 and s64 are covered by tablegen.
+      if (Ty != p0) {
         DEBUG(dbgs() << "Unable to materialize integer " << Ty
                      << " constant, expected: " << s32 << ", " << s64 << ", or "
                      << p0 << '\n');
         return false;
       }
 
       if (RB.getID() != AArch64::GPRRegBankID) {
         DEBUG(dbgs() << "Unable to materialize integer " << Ty

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

+# RUN: llc -O0 -mtriple=aarch64-- -run-pass=instruction-select -verify-machineinstrs -global-isel %s -o - | FileCheck %s
+
+--- |
+  target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
+
+  define void @imm_s32_gpr() { ret void }
+  define void @imm_s64_gpr() { ret void }
+
+...
+
+---
+# Check that we select a 32-bit immediate into a MOVi32imm.
+# CHECK-LABEL: name: imm_s32_gpr
+name:            imm_s32_gpr
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr32, preferred-register: '' }
+registers:
+  - { id: 0, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = MOVi32imm 4294966062
+body:             |
+  bb.0:
+    liveins: %w0, %w1
+
+    %0(s32) = G_CONSTANT i32 -1234
+    %w0 = COPY %0(s32)
+...
+
+---
+# Check that we select a 64-bit immediate into a MOVi64imm.
+# CHECK-LABEL: name: imm_s64_gpr
+name:            imm_s64_gpr
+legalized:       true
+regBankSelected: true
+
+# CHECK:      registers:
+# CHECK-NEXT:  - { id: 0, class: gpr64, preferred-register: '' }
+registers:
+  - { id: 0, class: gpr }
+
+# CHECK:  body:
+# CHECK:    %0 = MOVi64imm 1234
+body:             |
+  bb.0:
+    liveins: %w0, %w1
+
+    %0(s64) = G_CONSTANT i64 1234
+    %w0 = COPY %0(s64)
+...

test/CodeGen/X86/GlobalISel/select-inc.mir

 
 ---
 name:            test_add_i8
 legalized:       true
 regBankSelected: true
 # ALL:      registers:
 # ALL-NEXT:  - { id: 0, class: gr8, preferred-register: '' }
 # INC-NEXT:  - { id: 1, class: gpr, preferred-register: '' }
-# ADD-NEXT:  - { id: 1, class: gr8, preferred-register: '' }
+# ADD-NEXT:  - { id: 1, class: gpr, preferred-register: '' }
 # ALL-NEXT:  - { id: 2, class: gr8, preferred-register: '' }
 registers:
   - { id: 0, class: gpr }
   - { id: 1, class: gpr }
   - { id: 2, class: gpr }
 # ALL:      %0 = COPY %al
 # INC-NEXT: %2 = INC8r %0
-# ADD-NEXT: %1 = MOV8ri 1
-# ADD-NEXT: %2 = ADD8rr %0, %1
+# ADD-NEXT: %2 = ADD8ri %0, 1
 body:             |
   bb.1 (%ir-block.0):
     liveins: %al
 
     %0(s8) = COPY %al
     %1(s8) = G_CONSTANT i8 1
     %2(s8) = G_ADD %0, %1
     %al = COPY %2(s8)
 
 ...

test/TableGen/GlobalISelEmitter.td

 // CHECK-NEXT:    GIR_MutateOpcode, /*InsnID*/0, /*RecycleInsnID*/0, /*Opcode*/TargetOpcode::COPY,
 // CHECK-NEXT:    GIR_ConstrainOperandRC, /*InsnID*/0, /*Op*/0, /*RC GPR32*/1,
 // CHECK-NEXT:    GIR_Done,
 // CHECK-NEXT:  // Label 14: @[[LABEL]]
 
 def : Pat<(i32 (bitconvert FPR32:$src1)),
           (COPY_TO_REGCLASS FPR32:$src1, GPR32)>;
 
-//===- Test a simple pattern with just a leaf immediate. ------------------===//
+//===- Test a simple pattern with just a specific leaf immediate. ---------===//
 
 // CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 15*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
 // CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_CONSTANT,
 // CHECK-NEXT:    // MIs[0] dst
 // CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT:    // MIs[0] Operand 1
 // CHECK-NEXT:    GIM_CheckLiteralInt, /*MI*/0, /*Op*/1, 1,
 // CHECK-NEXT:    // 1:i32  =>  (MOV1:i32)
 // CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::MOV1,
 // CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // CHECK-NEXT:    GIR_MergeMemOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
 // CHECK-NEXT:  // Label 15: @[[LABEL]]
 
 def MOV1 : I<(outs GPR32:$dst), (ins), [(set GPR32:$dst, 1)]>;
 
-//===- Test a pattern with an MBB operand. --------------------------------===//
+//===- Test a simple pattern with just a leaf immediate. ------------------===//
 
 // CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 16*/ [[LABEL:[0-9]+]],
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_CONSTANT,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] Operand 1
+// CHECK-NEXT:    // No predicates
+// CHECK-NEXT:    // (imm:i32):$imm =>  (MOVimm:i32 (imm:i32):$imm)
+// CHECK-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::MOVimm,
+// CHECK-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
+// CHECK-NEXT:    GIR_CopyConstantAsUImm, /*NewInsnID*/0, /*OldInsnID*/0, // imm
+// CHECK-NEXT:    GIR_MergeMemOperands, /*InsnID*/0,
+// CHECK-NEXT:    GIR_EraseFromParent, /*InsnID*/0,
+// CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
+// CHECK-NEXT:    GIR_Done,
+// CHECK-NEXT:  // Label 16: @[[LABEL]]
+
+def MOVimm : I<(outs GPR32:$dst), (ins i32imm:$imm), [(set GPR32:$dst, imm:$imm)]>;
+
+//===- Test a pattern with an MBB operand. --------------------------------===//
+
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 17*/ [[LABEL:[0-9]+]],
 // CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/1,
 // CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_BR,
 // CHECK-NEXT:    // MIs[0] target
 // CHECK-NEXT:    GIM_CheckIsMBB, /*MI*/0, /*Op*/0,
 // CHECK-NEXT:    // (br (bb:Other):$target) => (BR (bb:Other):$target)
 // CHECK-NEXT:    GIR_MutateOpcode, /*InsnID*/0, /*RecycleInsnID*/0, /*Opcode*/MyTarget::BR,
 // CHECK-NEXT:    GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
 // CHECK-NEXT:    GIR_Done,
-// CHECK-NEXT:  // Label 16: @[[LABEL]]
+// CHECK-NEXT:  // Label 17: @[[LABEL]]
+
+def BR : I<(outs), (ins unknown:$target),
+            [(br bb:$target)]>;
+
 // CHECK-NEXT:    GIM_Reject,
 // CHECK-NEXT:  };
 // CHECK-NEXT:  if (executeMatchTable(*this, OutMIs, State, MatcherInfo, MatchTable0, TII, MRI, TRI, RBI, AvailableFeatures)) {
 // CHECK-NEXT:    return true;
 // CHECK-NEXT:  }
-
-def BR : I<(outs), (ins unknown:$target),
-            [(br bb:$target)]>;

utils/TableGen/GlobalISelEmitter.cpp

class RuleMatcher {
   std::vector<Record *> RequiredFeatures;
 
 public:
   RuleMatcher()
       : Matchers(), Actions(), InsnVariableIDs(), NextInsnVarID(0) {}
   RuleMatcher(RuleMatcher &&Other) = default;
   RuleMatcher &operator=(RuleMatcher &&Other) = default;
 
-  InstructionMatcher &addInstructionMatcher();
+  InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
   void addRequiredFeature(Record *Feature);
   const std::vector<Record *> &getRequiredFeatures() const;
 
   template <class Kind, class... Args> Kind &addAction(Args &&... args);
 
   /// Define an instruction without emitting any code to do so.
   /// This is used for the root of the match.
   unsigned implicitlyDefineInsnVar(const InstructionMatcher &Matcher);
   /// Define an instruction and emit corresponding state-machine opcodes.
   unsigned defineInsnVar(MatchTable &Table, const InstructionMatcher &Matcher,
                          unsigned InsnVarID, unsigned OpIdx);
   unsigned getInsnVarID(const InstructionMatcher &InsnMatcher) const;
 
+  const InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
+
   void emitCaptureOpcodes(MatchTable &Table);
 
   void emit(MatchTable &Table);
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   bool isHigherPriorityThan(const RuleMatcher &B) const;
public:
   /// the predicate when generating the matcher code. Kinds with higher priority
   /// must be tested first.
   ///
   /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
   /// but OPM_Int must have priority over OPM_RegBank since constant integers
   /// are represented by a virtual register defined by a G_CONSTANT instruction.
   enum PredicateKind {
     OPM_ComplexPattern,
-    OPM_Instruction,
     OPM_IntrinsicID,
+    OPM_Instruction,
     OPM_Int,
     OPM_LiteralInt,
     OPM_LLT,
     OPM_RegBank,
     OPM_MBB,
   };
 
 protected:
public:
   /// Emit MatchTable opcodes that check the predicate for the given operand.
   virtual void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                                     unsigned InsnVarID,
                                     unsigned OpIdx) 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;
-  };
+  virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const;
 
   /// Report the maximum number of temporary operands needed by the predicate
   /// matcher.
   virtual unsigned countRendererFns() const { return 0; }
 };
 
 /// Generates code to check that an operand is a particular LLT.
 class LLTOperandMatcher : public OperandPredicateMatcher {
isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
     // 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;
   };
+
+  bool isConstantInstruction() const {
+    return I->TheDef->getName() == "G_CONSTANT";
+  }
 };
 
 /// 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:
   typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
 
   /// The operands to match. All rendered operands must be present even if the
   /// condition is always true.
   OperandVec Operands;
 
+  std::string SymbolicName;
+
 public:
+  InstructionMatcher(StringRef SymbolicName) : SymbolicName(SymbolicName) {}
+
   /// Add an operand to the matcher.
   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
                              unsigned AllocatedTemporariesBaseID) {
     Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
                                              AllocatedTemporariesBaseID));
     return *Operands.back();
   }
 
public:
 
   const OperandMatcher &getOperand(StringRef SymbolicName) const {
     Optional<const OperandMatcher *>OM = getOptionalOperand(SymbolicName);
     if (OM.hasValue())
       return *OM.getValue();
     llvm_unreachable("Failed to lookup operand");
   }
 
+  StringRef getSymbolicName() const { return SymbolicName; }
   unsigned getNumOperands() const { return Operands.size(); }
   OperandVec::iterator operands_begin() { return Operands.begin(); }
   OperandVec::iterator operands_end() { return Operands.end(); }
   iterator_range<OperandVec::iterator> operands() {
     return make_range(operands_begin(), operands_end());
   }
   OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
   OperandVec::const_iterator operands_end() const { return Operands.end(); }
return std::accumulate(predicates().begin(), predicates().end(), 0,
                              return A + Predicate->countRendererFns();
                            }) +
            std::accumulate(
                Operands.begin(), Operands.end(), 0,
                [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
                  return A + Operand->countRendererFns();
                });
   }
+
+  bool isConstantInstruction() const {
+    for (const auto &P : predicates())
+      if (const InstructionOpcodeMatcher *Opcode =
+              dyn_cast<InstructionOpcodeMatcher>(P.get()))
+        return Opcode->isConstantInstruction();
+    return false;
+  }
 };
 
 /// Generates code to check that the operand is a register defined by an
 /// instruction that matches the given instruction matcher.
 ///
 /// For example, the pattern:
 ///   (set $dst, (G_MUL (G_ADD $src1, $src2), $src3))
 /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match
 /// the:
 ///   (G_ADD $src1, $src2)
 /// subpattern.
 class InstructionOperandMatcher : public OperandPredicateMatcher {
 protected:
   std::unique_ptr<InstructionMatcher> InsnMatcher;
 
 public:
-  InstructionOperandMatcher()
+  InstructionOperandMatcher(StringRef SymbolicName)
       : OperandPredicateMatcher(OPM_Instruction),
-        InsnMatcher(new InstructionMatcher()) {}
+        InsnMatcher(new InstructionMatcher(SymbolicName)) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_Instruction;
   }
 
   InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
 
   Optional<const OperandMatcher *>

 };
 
 //===- Actions ------------------------------------------------------------===//
 class OperandRenderer {
 public:
   enum RendererKind {
     OR_Copy,
     OR_CopySubReg,
+    OR_CopyConstantAsImm,
     OR_Imm,
     OR_Register,
     OR_ComplexPattern
   };
 
 protected:
   RendererKind Kind;
 
protected:
   const InstructionMatcher &Matched;
   /// The name of the operand.
   const StringRef SymbolicName;
 
 public:
   CopyRenderer(unsigned NewInsnID, const InstructionMatcher &Matched,
                StringRef SymbolicName)
       : OperandRenderer(OR_Copy), NewInsnID(NewInsnID), Matched(Matched),
-        SymbolicName(SymbolicName) {}
+        SymbolicName(SymbolicName) {
+    assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
+  }
 
   static bool classof(const OperandRenderer *R) {
     return R->getKind() == OR_Copy;
   }
 
   const StringRef getSymbolicName() const { return SymbolicName; }
 
   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
     const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
     Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
           << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
           << MatchTable::IntValue(Operand.getOperandIndex())
           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
   }
 };
 
+/// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
+/// an extended immediate operand.
+class CopyConstantAsImmRenderer : public OperandRenderer {
+protected:
+  unsigned NewInsnID;
+  /// The name of the operand.
+  const std::string SymbolicName;
+  bool Signed;
+
+public:
+  CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
+      : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
+        SymbolicName(SymbolicName), Signed(false) {}
+
+  static bool classof(const OperandRenderer *R) {
+    return R->getKind() == OR_CopyConstantAsImm;
+  }
+
+  const StringRef getSymbolicName() const { return SymbolicName; }
+
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    const InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
+    unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
+    Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
+                                       : "GIR_CopyConstantAsUImm")
+          << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
+          << MatchTable::Comment("OldInsnID")
+          << MatchTable::IntValue(OldInsnVarID)
+          << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
+  }
+};
+
 /// A CopySubRegRenderer emits code to copy a single register operand from an
 /// existing instruction to the one being built and indicate that only a
 /// subregister should be copied.
 class CopySubRegRenderer : public OperandRenderer {
 protected:
   unsigned NewInsnID;
   /// 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
void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule,
     Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
           << MatchTable::Comment("RC " + RC.getName())
           << MatchTable::IntValue(RC.EnumValue) << MatchTable::LineBreak;
   }
 };
 
-InstructionMatcher &RuleMatcher::addInstructionMatcher() {
-  Matchers.emplace_back(new InstructionMatcher());
+InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
+  Matchers.emplace_back(new InstructionMatcher(SymbolicName));
   return *Matchers.back();
 }
 
 void RuleMatcher::addRequiredFeature(Record *Feature) {
   RequiredFeatures.push_back(Feature);
 }
 
 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {

 
 unsigned RuleMatcher::getInsnVarID(const InstructionMatcher &InsnMatcher) const {
   const auto &I = InsnVariableIDs.find(&InsnMatcher);
   if (I != InsnVariableIDs.end())
     return I->second;
   llvm_unreachable("Matched Insn was not captured in a local variable");
 }
 
+const InstructionMatcher &
+RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
+  for (const auto &I : InsnVariableIDs)
+    if (I.first->getSymbolicName() == SymbolicName)
+      return *I.first;
+  llvm_unreachable(
+      ("Failed to lookup instruction " + SymbolicName).str().c_str());
+}
+
 /// Emit MatchTable opcodes to check the shape of the match and capture
 /// instructions into local variables.
 void RuleMatcher::emitCaptureOpcodes(MatchTable &Table) {
   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
   unsigned InsnVarID = implicitlyDefineInsnVar(*Matchers.front());
   Matchers.front()->emitCaptureOpcodes(Table, *this, InsnVarID);
 }
 

 unsigned RuleMatcher::countRendererFns() const {
   return std::accumulate(
       Matchers.begin(), Matchers.end(), 0,
       [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) {
         return A + Matcher->countRendererFns();
       });
 }
 
+bool OperandPredicateMatcher::isHigherPriorityThan(
+    const OperandPredicateMatcher &B) const {
+  // Generally speaking, an instruction is more important than an Int or a
+  // LiteralInt because it can cover more nodes but theres an exception to
+  // this. G_CONSTANT's are less important than either of those two because they
+  // are more permissive.
+  if (const InstructionOperandMatcher *AOM =
+          dyn_cast<InstructionOperandMatcher>(this)) {
+    if (AOM->getInsnMatcher().isConstantInstruction()) {
+      if (B.Kind == OPM_Int) {
+        return false;
+      }
+    }
+  }
+  if (const InstructionOperandMatcher *BOM =
+          dyn_cast<InstructionOperandMatcher>(&B)) {
+    if (BOM->getInsnMatcher().isConstantInstruction()) {
+      if (Kind == OPM_Int) {
+        return true;
+      }
+    }
+  }
+
+  return Kind < B.Kind;
+};
+
 //===- GlobalISelEmitter class --------------------------------------------===//
 
 class GlobalISelEmitter {
 public:
   explicit GlobalISelEmitter(RecordKeeper &RK);
   void run(raw_ostream &OS);
 
 private:
if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
       OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
       OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
     } else
       return failedImport(
           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
   } else {
     assert(SrcGIOrNull &&
            "Expected to have already found an equivalent Instruction");
+    if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT") {
+      // imm still has an operand but we don't need to do anything with it
+      // here since we don't support ImmLeaf predicates yet. However, we still
+      // need to note the hidden operand to get GIM_CheckNumOperands correct.
+      InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
+      return InsnMatcher;
+    }
+
     // Match the used operands (i.e. the children of the operator).
     for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
       TreePatternNode *SrcChild = Src->getChild(i);
 
       // For G_INTRINSIC, the operand immediately following the defs is an
       // intrinsic ID.
       if (SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" && i == 0) {
         if (const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP)) {
Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
   if (!OpTyOrNone)
     return failedImport("Src operand has an unsupported type (" + to_string(*SrcChild) + ")");
   OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
 
   // Check for nested instructions.
   if (!SrcChild->isLeaf()) {
     // Map the node to a gMIR instruction.
     InstructionOperandMatcher &InsnOperand =
-        OM.addPredicate<InstructionOperandMatcher>();
+        OM.addPredicate<InstructionOperandMatcher>(SrcChild->getName());
     auto InsnMatcherOrError = createAndImportSelDAGMatcher(
         InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
     if (auto Error = InsnMatcherOrError.takeError())
       return Error;
 
     return Error::success();
   }
 
Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
   }
 
   return failedImport("Src pattern child is an unsupported kind");
 }
 
 Error GlobalISelEmitter::importExplicitUseRenderer(
     BuildMIAction &DstMIBuilder, TreePatternNode *DstChild,
     const InstructionMatcher &InsnMatcher) const {
-  // 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()) {
+    // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
+    // inline, but in MI it's just another operand.
     if (DstChild->getOperator()->isSubClassOf("SDNode")) {
       auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
         DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher,
                                                DstChild->getName());
         return Error::success();
       }
     }
+
+    // Similarly, imm is an operator in TreePatternNode's view but must be
+    // rendered as operands.
+    // FIXME: The target should be able to choose sign-extended when appropriate
+    //        (e.g. on Mips).
+    if (DstChild->getOperator()->getName() == "imm") {
+      DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(0,
+                                                          DstChild->getName());
+      return Error::success();
+    }
+
     return failedImport("Dst pattern child isn't a leaf node or an MBB");
   }
 
   // Otherwise, we're looking for a bog-standard RegisterClass operand.
   if (DstChild->hasAnyPredicate())
     return failedImport("Dst pattern child has predicate (" +
                         explainPredicates(DstChild) + ")");
 
if (!DstOp->isSubClassOf("Instruction"))
     return failedImport("Pattern operator isn't an instruction");
 
   auto &DstI = Target.getInstruction(DstOp);
   if (DstI.Operands.NumDefs != Src->getExtTypes().size())
     return failedImport("Src pattern results and dst MI defs are different (" +
                         to_string(Src->getExtTypes().size()) + " def(s) vs " +
                         to_string(DstI.Operands.NumDefs) + " def(s))");
 
-  InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher();
+  InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
   unsigned TempOpIdx = 0;
   auto InsnMatcherOrError =
       createAndImportSelDAGMatcher(InsnMatcherTemp, Src, TempOpIdx);
   if (auto Error = InsnMatcherOrError.takeError())
     return std::move(Error);
   InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
 
   // The root of the match also has constraints on the register bank so that it