[globalisel][tblgen] Add support for iPTR and implement am_unscaled* and am_indexed*

[dsanders]

Summary

iPTR is a pointer of subtarget-specific size to any address space. Therefore
type checks on this size derive the SizeInBits from a subtarget hook.

At this point, we can import the simplests G_LOAD rules and select load
instructions using them. Further patches will support for the predicates to
enable additional loads as well as the stores.

Depends on D37457

[dsanders]

Rebase and ping

[qcolombet]

Looks good modulo what I said in https://reviews.llvm.org/D37457 regarding GIM_CheckPointerToAny

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

242

Don't we have a more direct way to access the target from the selector?
In particular something that doesn't depend on State.

(This is not wrong, it just looks weird.)

utils/TableGen/GlobalISelEmitter.cpp

975

Looks like this part could be already independently committed.

[dsanders]

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

242

Not that I know of, but it would probably look better if I assigned it to an MF variable first.

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

protected:
   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;
 
+  /// Return true if the specified operand is a G_GEP with a G_CONSTANT on the
+  /// right-hand side. GlobalISel's separation of pointer and integer types
+  /// means that we don't need to worry about G_OR with equivalent semantics.
+  bool isBaseWithConstantOffset(const MachineOperand &Root,
+                                const MachineRegisterInfo &MRI) const;
+
   bool isObviouslySafeToFold(MachineInstr &MI) const;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

case GIM_CheckType: {
           return false;
       }
       break;
     }
     case GIM_CheckPointerToAny: {
       int64_t InsnID = MatchTable[CurrentIdx++];
       int64_t OpIdx = MatchTable[CurrentIdx++];
       int64_t SizeInBits = MatchTable[CurrentIdx++];
+
       DEBUG(dbgs() << CurrentIdx << ": GIM_CheckPointerToAny(MIs[" << InsnID
                    << "]->getOperand(" << OpIdx
                    << "), SizeInBits=" << SizeInBits << ")\n");
       assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
+
+      // iPTR must be looked up in the target.
+      if (SizeInBits == 0)
+        SizeInBits = State.MIs[InsnID]->getParent()->getParent()->getDataLayout().getPointerSizeInBits(0);
+
+      assert(SizeInBits != 0 && "Pointer size must be known");
+
       const LLT &Ty = MRI.getType(State.MIs[InsnID]->getOperand(OpIdx).getReg());
       if (!Ty.isPointer() || Ty.getSizeInBits() != SizeInBits) {
         if (handleReject() == RejectAndGiveUp)
           return false;
       }
       break;
     }
     case GIM_CheckRegBankForClass: {

lib/CodeGen/GlobalISel/InstructionSelector.cpp

bool InstructionSelector::isOperandImmEqual(
     const MachineOperand &MO, int64_t Value,
     const MachineRegisterInfo &MRI) const {
   if (MO.isReg() && MO.getReg())
     if (auto VRegVal = getConstantVRegVal(MO.getReg(), MRI))
       return *VRegVal == Value;
   return false;
 }
 
+bool InstructionSelector::isBaseWithConstantOffset(
+    const MachineOperand &Root, const MachineRegisterInfo &MRI) const {
+  if (!Root.isReg())
+    return false;
+
+  MachineInstr *RootI = MRI.getVRegDef(Root.getReg());
+  if (RootI->getOpcode() != TargetOpcode::G_GEP)
+    return false;
+
+  MachineOperand &RHS = RootI->getOperand(2);
+  MachineInstr *RHSI = MRI.getVRegDef(RHS.getReg());
+  if (RHSI->getOpcode() != TargetOpcode::G_CONSTANT)
+    return false;
+
+  return true;
+}
+
 bool InstructionSelector::isObviouslySafeToFold(MachineInstr &MI) const {
   return !MI.mayLoadOrStore() && !MI.hasUnmodeledSideEffects() &&
          MI.implicit_operands().begin() == MI.implicit_operands().end();
 }

lib/Target/AArch64/AArch64InstrFormats.td

 // (unsigned immediate)
 // Indexed for 8-bit registers. offset is in range [0,4095].
 def am_indexed8 : ComplexPattern<i64, 2, "SelectAddrModeIndexed8", []>;
 def am_indexed16 : ComplexPattern<i64, 2, "SelectAddrModeIndexed16", []>;
 def am_indexed32 : ComplexPattern<i64, 2, "SelectAddrModeIndexed32", []>;
 def am_indexed64 : ComplexPattern<i64, 2, "SelectAddrModeIndexed64", []>;
 def am_indexed128 : ComplexPattern<i64, 2, "SelectAddrModeIndexed128", []>;
 
+def gi_am_indexed8 :
+    GIComplexOperandMatcher<s64, "selectAddrModeIndexed<8>">,
+    GIComplexPatternEquiv<am_indexed8>;
+def gi_am_indexed16 :
+    GIComplexOperandMatcher<s64, "selectAddrModeIndexed<16>">,
+    GIComplexPatternEquiv<am_indexed16>;
+def gi_am_indexed32 :
+    GIComplexOperandMatcher<s64, "selectAddrModeIndexed<32>">,
+    GIComplexPatternEquiv<am_indexed32>;
+def gi_am_indexed64 :
+    GIComplexOperandMatcher<s64, "selectAddrModeIndexed<64>">,
+    GIComplexPatternEquiv<am_indexed64>;
+def gi_am_indexed128 :
+    GIComplexOperandMatcher<s64, "selectAddrModeIndexed<128>">,
+    GIComplexPatternEquiv<am_indexed128>;
+
 class UImm12OffsetOperand<int Scale> : AsmOperandClass {
   let Name = "UImm12Offset" # Scale;
   let RenderMethod = "addUImm12OffsetOperands<" # Scale # ">";
   let PredicateMethod = "isUImm12Offset<" # Scale # ">";
   let DiagnosticType = "InvalidMemoryIndexed" # Scale;
 }
 
 def UImm12OffsetScale1Operand : UImm12OffsetOperand<1>;

 //---
 
 def am_unscaled8 :  ComplexPattern<i64, 2, "SelectAddrModeUnscaled8", []>;
 def am_unscaled16 : ComplexPattern<i64, 2, "SelectAddrModeUnscaled16", []>;
 def am_unscaled32 : ComplexPattern<i64, 2, "SelectAddrModeUnscaled32", []>;
 def am_unscaled64 : ComplexPattern<i64, 2, "SelectAddrModeUnscaled64", []>;
 def am_unscaled128 :ComplexPattern<i64, 2, "SelectAddrModeUnscaled128", []>;
 
+def gi_am_unscaled8 :
+    GIComplexOperandMatcher<s64, "selectAddrModeUnscaled8">,
+    GIComplexPatternEquiv<am_unscaled8>;
+def gi_am_unscaled16 :
+    GIComplexOperandMatcher<s64, "selectAddrModeUnscaled16">,
+    GIComplexPatternEquiv<am_unscaled16>;
+def gi_am_unscaled32 :
+    GIComplexOperandMatcher<s64, "selectAddrModeUnscaled32">,
+    GIComplexPatternEquiv<am_unscaled32>;
+def gi_am_unscaled64 :
+    GIComplexOperandMatcher<s64, "selectAddrModeUnscaled64">,
+    GIComplexPatternEquiv<am_unscaled64>;
+def gi_am_unscaled128 :
+    GIComplexOperandMatcher<s64, "selectAddrModeUnscaled128">,
+    GIComplexPatternEquiv<am_unscaled128>;
+
+
 class BaseLoadStoreUnscale<bits<2> sz, bit V, bits<2> opc, dag oops, dag iops,
                            string asm, list<dag> pattern>
     : I<oops, iops, asm, "\t$Rt, [$Rn, $offset]", "", pattern> {
   bits<5> Rt;
   bits<5> Rn;
   bits<9> offset;
   let Inst{31-30} = sz;
   let Inst{29-27} = 0b111;

lib/Target/AArch64/AArch64InstructionSelector.cpp

private:
   bool selectVaStartDarwin(MachineInstr &I, MachineFunction &MF,
                            MachineRegisterInfo &MRI) const;
 
   bool selectCompareBranch(MachineInstr &I, MachineFunction &MF,
                            MachineRegisterInfo &MRI) const;
 
   ComplexRendererFn selectArithImmed(MachineOperand &Root) const;
 
+  ComplexRendererFn selectAddrModeUnscaled(MachineOperand &Root,
+                                           unsigned Size) const;
+
+  ComplexRendererFn selectAddrModeUnscaled8(MachineOperand &Root) const {
+    return selectAddrModeUnscaled(Root, 1);
+  }
+  ComplexRendererFn selectAddrModeUnscaled16(MachineOperand &Root) const {
+    return selectAddrModeUnscaled(Root, 2);
+  }
+  ComplexRendererFn selectAddrModeUnscaled32(MachineOperand &Root) const {
+    return selectAddrModeUnscaled(Root, 4);
+  }
+  ComplexRendererFn selectAddrModeUnscaled64(MachineOperand &Root) const {
+    return selectAddrModeUnscaled(Root, 8);
+  }
+  ComplexRendererFn selectAddrModeUnscaled128(MachineOperand &Root) const {
+    return selectAddrModeUnscaled(Root, 16);
+  }
+
+  ComplexRendererFn selectAddrModeIndexed(MachineOperand &Root,
+                                          unsigned Size) const;
+  template <int Width>
+  ComplexRendererFn selectAddrModeIndexed(MachineOperand &Root) const {
+    return selectAddrModeIndexed(Root, Width / 8);
+  }
+
   const AArch64TargetMachine &TM;
   const AArch64Subtarget &STI;
   const AArch64InstrInfo &TII;
   const AArch64RegisterInfo &TRI;
   const AArch64RegisterBankInfo &RBI;
 
 #define GET_GLOBALISEL_PREDICATES_DECL
 #include "AArch64GenGlobalISel.inc"
AArch64InstructionSelector::selectArithImmed(MachineOperand &Root) const {
 
   unsigned ShVal = AArch64_AM::getShifterImm(AArch64_AM::LSL, ShiftAmt);
   return {{
       [=](MachineInstrBuilder &MIB) { MIB.addImm(Immed); },
       [=](MachineInstrBuilder &MIB) { MIB.addImm(ShVal); },
   }};
 }
 
+/// Select a "register plus unscaled signed 9-bit immediate" address.  This
+/// should only match when there is an offset that is not valid for a scaled
+/// immediate addressing mode.  The "Size" argument is the size in bytes of the
+/// memory reference, which is needed here to know what is valid for a scaled
+/// immediate.
+InstructionSelector::ComplexRendererFn
+AArch64InstructionSelector::selectAddrModeUnscaled(MachineOperand &Root,
+                                                   unsigned Size) const {
+  MachineRegisterInfo &MRI =
+      Root.getParent()->getParent()->getParent()->getRegInfo();
+
+  if (!Root.isReg())
+    return None;
+
+  if (!isBaseWithConstantOffset(Root, MRI))
+    return None;
+
+  MachineInstr *RootDef = MRI.getVRegDef(Root.getReg());
+  if (!RootDef)
+    return None;
+
+  MachineOperand &OffImm = RootDef->getOperand(2);
+  if (!OffImm.isReg())
+    return None;
+  MachineInstr *RHS = MRI.getVRegDef(OffImm.getReg());
+  if (!RHS || RHS->getOpcode() != TargetOpcode::G_CONSTANT)
+    return None;
+  int64_t RHSC;
+  MachineOperand &RHSOp1 = RHS->getOperand(1);
+  if (!RHSOp1.isCImm() || RHSOp1.getCImm()->getBitWidth() > 64)
+    return None;
+  RHSC = RHSOp1.getCImm()->getSExtValue();
+
+  // If the offset is valid as a scaled immediate, don't match here.
+  if ((RHSC & (Size - 1)) == 0 && RHSC >= 0 && RHSC < (0x1000 << Log2_32(Size)))
+    return None;
+  if (RHSC >= -256 && RHSC < 256) {
+    MachineOperand &Base = RootDef->getOperand(1);
+    return {{
+        [=](MachineInstrBuilder &MIB) { MIB.add(Base); },
+        [=](MachineInstrBuilder &MIB) { MIB.addImm(RHSC); },
+    }};
+  }
+  return None;
+}
+
+/// Select a "register plus scaled unsigned 12-bit immediate" address.  The
+/// "Size" argument is the size in bytes of the memory reference, which
+/// determines the scale.
+InstructionSelector::ComplexRendererFn
+AArch64InstructionSelector::selectAddrModeIndexed(MachineOperand &Root,
+                                                  unsigned Size) const {
+  MachineRegisterInfo &MRI =
+      Root.getParent()->getParent()->getParent()->getRegInfo();
+
+  if (!Root.isReg())
+    return None;
+
+  MachineInstr *RootDef = MRI.getVRegDef(Root.getReg());
+  if (!RootDef)
+    return None;
+
+  if (RootDef->getOpcode() == TargetOpcode::G_FRAME_INDEX) {
+    return {{
+        [=](MachineInstrBuilder &MIB) { MIB.add(RootDef->getOperand(1)); },
+        [=](MachineInstrBuilder &MIB) { MIB.addImm(0); },
+    }};
+  }
+
+  if (isBaseWithConstantOffset(Root, MRI)) {
+    MachineOperand &LHS = RootDef->getOperand(1);
+    MachineOperand &RHS = RootDef->getOperand(2);
+    MachineInstr *LHSDef = MRI.getVRegDef(LHS.getReg());
+    MachineInstr *RHSDef = MRI.getVRegDef(RHS.getReg());
+    if (LHSDef && RHSDef) {
+      int64_t RHSC = (int64_t)RHSDef->getOperand(1).getCImm()->getZExtValue();
+      unsigned Scale = Log2_32(Size);
+      if ((RHSC & (Size - 1)) == 0 && RHSC >= 0 && RHSC < (0x1000 << Scale)) {
+        if (LHSDef->getOpcode() == TargetOpcode::G_FRAME_INDEX)
+          LHSDef = MRI.getVRegDef(LHSDef->getOperand(1).getReg());
+        return {{
+            [=](MachineInstrBuilder &MIB) { MIB.add(LHS); },
+            [=](MachineInstrBuilder &MIB) { MIB.addImm(RHSC >> Scale); },
+        }};
+      }
+    }
+  }
+
+  // Before falling back to our general case, check if the unscaled
+  // instructions can handle this. If so, that's preferable.
+  if (selectAddrModeUnscaled(Root, Size).hasValue())
+    return None;
+
+  return {{
+      [=](MachineInstrBuilder &MIB) { MIB.add(Root); },
+      [=](MachineInstrBuilder &MIB) { MIB.addImm(0); },
+  }};
+}
+
 namespace llvm {
 InstructionSelector *
 createAArch64InstructionSelector(const AArch64TargetMachine &TM,
                                  AArch64Subtarget &Subtarget,
                                  AArch64RegisterBankInfo &RBI) {
   return new AArch64InstructionSelector(TM, Subtarget, RBI);
 }
 }

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

 # CHECK-NEXT:  - { id: 0, class: gpr64sp, preferred-register: '' }
 # CHECK-NEXT:  - { id: 1, class: fpr64, preferred-register: '' }
 registers:
   - { id: 0, class: gpr }
   - { id: 1, class: fpr }
 
 # CHECK:  body:
 # CHECK:    %0 = COPY %x0
-# CHECK:    %1 = LD1Onev2s %0
+# CHECK:    %1 = LDRDui %0, 0 :: (load 8 from %ir.addr)
 # CHECK:    %d0 = COPY %1
 body:             |
   bb.0:
     liveins: %x0
 
     %0(p0) = COPY %x0
-    %1(<2 x s32>) = G_LOAD %0 :: (load 4 from %ir.addr)
+    %1(<2 x s32>) = G_LOAD %0 :: (load 8 from %ir.addr)
     %d0 = COPY %1(<2 x s32>)
 ...

utils/TableGen/GlobalISelEmitter.cpp

 /// Generates code to check that an operand is a pointer to any address space.
 ///
 /// In SelectionDAG, the types did not describe pointers or address spaces. As a
 /// result, iN is used to describe a pointer of N bits to any address space and
 /// PatFrag predicates are typically used to constrain the address space. There's
 /// no reliable means to derive the missing type information from the pattern so
 /// imported rules must test the components of a pointer separately.
 ///
-/// SizeInBits must be non-zero and the matched pointer must be that size.
-/// TODO: Add support for iPTR via SizeInBits==0 and a subtarget query.
+/// If SizeInBits is zero, then the pointer size will be obtained from the
+/// subtarget.
 class PointerToAnyOperandMatcher : public OperandPredicateMatcher {
 protected:
   unsigned SizeInBits;
 
 public:
   PointerToAnyOperandMatcher(unsigned SizeInBits)
       : OperandPredicateMatcher(OPM_PointerToAny), SizeInBits(SizeInBits) {}
 
public:
   std::string getOperandExpr(unsigned InsnVarID) const {
     return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
            llvm::to_string(OpIdx) + ")";
   }
 
   InstructionMatcher &getInstructionMatcher() const { return Insn; }
 
   Error addTypeCheckPredicate(MVT::SimpleValueType Ty, bool OperandIsAPointer) {
+    if (Ty == MVT::iPTR && OperandIsAPointer) {
+      addPredicate<PointerToAnyOperandMatcher>(0);
+      return Error::success();
+    }
+
     auto OpTyOrNone = MVTToLLT(Ty);
     if (!OpTyOrNone)
       return failedImport("unsupported type");
     if (OperandIsAPointer)
       addPredicate<PointerToAnyOperandMatcher>(
           OpTyOrNone->get().getSizeInBits());
     else
       addPredicate<LLTOperandMatcher>(*OpTyOrNone);