[AArch64][GlobalISel] Use TST for comparisons when possible

[paquette]

Summary

Porting over the part of emitComparison in AArch64ISelLowering where we use TST to represent a compare.

• Rename tryOptCMN to tryFoldIntegerCompare, since it now also emits TSTs when possible.
• Add a utility function for emitting a TST with register operands.
• Rename opt-fold-cmn.mir to opt-fold-compare.mir, since it now also tests the TST fold as well.

[aemerson]

LGTM with comment fix and minor nit.

llvm/lib/Target/AArch64/AArch64InstructionSelector.cpp

810

Can just make this default block return false and kill the return after the switch.

llvm/lib/Target/AArch64/AArch64InstructionSelector.cpp

private:
   MachineInstr *emitVectorConcat(Optional<Register> Dst, Register Op1,
                                  Register Op2,
                                  MachineIRBuilder &MIRBuilder) const;
   MachineInstr *emitIntegerCompare(MachineOperand &LHS, MachineOperand &RHS,
                                    MachineOperand &Predicate,
                                    MachineIRBuilder &MIRBuilder) const;
   MachineInstr *emitCMN(MachineOperand &LHS, MachineOperand &RHS,
                         MachineIRBuilder &MIRBuilder) const;
+  MachineInstr *emitTST(const Register &LHS, const Register &RHS,
+                        MachineIRBuilder &MIRBuilder) const;
   MachineInstr *emitExtractVectorElt(Optional<Register> DstReg,
                                      const RegisterBank &DstRB, LLT ScalarTy,
                                      Register VecReg, unsigned LaneIdx,
                                      MachineIRBuilder &MIRBuilder) const;
 
   /// Helper function for selecting G_FCONSTANT. If the G_FCONSTANT can be
   /// materialized using a FMOV instruction, then update MI and return it.
   /// Otherwise, do nothing and return a nullptr.
MachineInstr *findMIFromReg(unsigned Reg, unsigned Opc,
     if (!Def || Def->getOpcode() != Opc)
       return nullptr;
     return Def;
   }
 
   bool tryOptVectorShuffle(MachineInstr &I) const;
   bool tryOptVectorDup(MachineInstr &MI) const;
   bool tryOptSelect(MachineInstr &MI) const;
-  MachineInstr *tryOptCMN(MachineOperand &LHS, MachineOperand &RHS,
+  MachineInstr *tryFoldIntegerCompare(MachineOperand &LHS, MachineOperand &RHS,
                                       MachineOperand &Predicate,
                                       MachineIRBuilder &MIRBuilder) const;
 
   const AArch64TargetMachine &TM;
   const AArch64Subtarget &STI;
   const AArch64InstrInfo &TII;
   const AArch64RegisterInfo &TRI;
   const AArch64RegisterBankInfo &RBI;
 
 #define GET_GLOBALISEL_PREDICATES_DECL
static unsigned selectFCMPOpc(MachineInstr &I, MachineRegisterInfo &MRI) {
   unsigned OpSize = MRI.getType(I.getOperand(2).getReg()).getSizeInBits();
   if (OpSize != 32 && OpSize != 64)
     return 0;
   unsigned CmpOpcTbl[2][2] = {{AArch64::FCMPSrr, AArch64::FCMPDrr},
                               {AArch64::FCMPSri, AArch64::FCMPDri}};
   return CmpOpcTbl[ShouldUseImm][OpSize == 64];
 }
 
+/// Returns true if \p P is an unsigned integer comparison predicate.
+static bool isUnsignedICMPPred(const CmpInst::Predicate P) {
+  switch (P) {
+  default:
+    break;
+  case CmpInst::ICMP_UGT:
+  case CmpInst::ICMP_UGE:
+  case CmpInst::ICMP_ULT:
+  case CmpInst::ICMP_ULE:
+    return true;
+  }
+  return false;
+}
+
 static AArch64CC::CondCode changeICMPPredToAArch64CC(CmpInst::Predicate P) {
   switch (P) {
   default:
     llvm_unreachable("Unknown condition code!");
   case CmpInst::ICMP_NE:
     return AArch64CC::NE;
   case CmpInst::ICMP_EQ:
     return AArch64CC::EQ;
AArch64InstructionSelector::emitCMN(MachineOperand &LHS, MachineOperand &RHS,
   } else {
     CmpMI.addUse(RHS.getReg());
   }
 
   constrainSelectedInstRegOperands(*CmpMI, TII, TRI, RBI);
   return &*CmpMI;
 }
 
+MachineInstr *
+AArch64InstructionSelector::emitTST(const Register &LHS, const Register &RHS,
+                                    MachineIRBuilder &MIRBuilder) const {
+  MachineRegisterInfo &MRI = MIRBuilder.getMF().getRegInfo();
+  unsigned RegSize = MRI.getType(LHS).getSizeInBits();
+  bool Is32Bit = (RegSize == 32);
+  static const unsigned OpcTable[2][2]{{AArch64::ANDSXrr, AArch64::ANDSXri},
+                                       {AArch64::ANDSWrr, AArch64::ANDSWri}};
+  Register ZReg = Is32Bit ? AArch64::WZR : AArch64::XZR;
+
+  // We might be able to fold in an immediate into the TST. We need to make sure
+  // it's a logical immediate though, since ANDS requires that.
+  auto ValAndVReg = getConstantVRegValWithLookThrough(RHS, MRI);
+  bool IsImmForm = ValAndVReg.hasValue() &&
+                   AArch64_AM::isLogicalImmediate(ValAndVReg->Value, RegSize);
+  unsigned Opc = OpcTable[Is32Bit][IsImmForm];
+  auto TstMI = MIRBuilder.buildInstr(Opc, {ZReg}, {LHS});
+
+  if (IsImmForm)
+    TstMI.addImm(
+        AArch64_AM::encodeLogicalImmediate(ValAndVReg->Value, RegSize));
+  else
+    TstMI.addUse(RHS);
+
+  constrainSelectedInstRegOperands(*TstMI, TII, TRI, RBI);
+  return &*TstMI;
+}
+
 MachineInstr *AArch64InstructionSelector::emitIntegerCompare(
     MachineOperand &LHS, MachineOperand &RHS, MachineOperand &Predicate,
     MachineIRBuilder &MIRBuilder) const {
   assert(LHS.isReg() && RHS.isReg() && "Expected LHS and RHS to be registers!");
   MachineRegisterInfo &MRI = MIRBuilder.getMF().getRegInfo();
 
-  // Fold the compare into a CMN if possible.
-  MachineInstr *Cmn = tryOptCMN(LHS, RHS, Predicate, MIRBuilder);
-  if (Cmn)
-    return Cmn;
+  // Fold the compare if possible.
+  MachineInstr *FoldCmp =
+      tryFoldIntegerCompare(LHS, RHS, Predicate, MIRBuilder);
+  if (FoldCmp)
+    return FoldCmp;
 
   // Can't fold into a CMN. Just emit a normal compare.
   unsigned CmpOpc = 0;
   Register ZReg;
 
   LLT CmpTy = MRI.getType(LHS.getReg());
   assert((CmpTy.isScalar() || CmpTy.isPointer()) &&
          "Expected scalar or pointer");
auto CSel =
       MIB.buildInstr(CSelOpc, {I.getOperand(0).getReg()},
                      {I.getOperand(2).getReg(), I.getOperand(3).getReg()})
           .addImm(CondCode);
   constrainSelectedInstRegOperands(*CSel, TII, TRI, RBI);
   I.eraseFromParent();
   return true;
 }
 
-MachineInstr *
-AArch64InstructionSelector::tryOptCMN(MachineOperand &LHS, MachineOperand &RHS,
-                                      MachineOperand &Predicate,
-                                      MachineIRBuilder &MIRBuilder) const {
+MachineInstr *AArch64InstructionSelector::tryFoldIntegerCompare(
+    MachineOperand &LHS, MachineOperand &RHS, MachineOperand &Predicate,
   assert(LHS.isReg() && RHS.isReg() && Predicate.isPredicate() &&
          "Unexpected MachineOperand");
   MachineRegisterInfo &MRI = *MIRBuilder.getMRI();
   // We want to find this sort of thing:
   // x = G_SUB 0, y
   // G_ICMP z, x
   //
   // In this case, we can fold the G_SUB into the G_ICMP using a CMN instead.
auto IsCMN = [&](MachineInstr *DefMI, const AArch64CC::CondCode &CC) {
 
     // This can safely be represented as a CMN.
     return true;
   };
 
   // Check if the RHS or LHS of the G_ICMP is defined by a SUB
   MachineInstr *LHSDef = FindDef(LHS.getReg());
   MachineInstr *RHSDef = FindDef(RHS.getReg());
-  const AArch64CC::CondCode CC =
-      changeICMPPredToAArch64CC((CmpInst::Predicate)Predicate.getPredicate());
-  bool DidFold = false;
-
-  MachineOperand CMNLHS = LHS;
-  MachineOperand CMNRHS = RHS;
-  if (IsCMN(LHSDef, CC)) {
-    // We're doing this:
-    //
-    // Given:
-    //
-    // x = G_SUB 0, y
-    // G_ICMP x, z
-    //
-    // Update the G_ICMP:
-    //
-    // G_ICMP y, z
-    CMNLHS = LHSDef->getOperand(2);
-    DidFold = true;
-  } else if (IsCMN(RHSDef, CC)) {
-    // Same idea here, but with the RHS of the compare instead:
-    //
-    // Given:
-    //
-    // x = G_SUB 0, y
-    // G_ICMP z, x
-    //
-    // Update the G_ICMP:
-    //
-    // G_ICMP z, y
-    CMNRHS = RHSDef->getOperand(2);
-    DidFold = true;
+  CmpInst::Predicate P = (CmpInst::Predicate)Predicate.getPredicate();
+  const AArch64CC::CondCode CC = changeICMPPredToAArch64CC(P);
+
+  // Given this:
+  // Produce this:
+  // cmn y, z
+  if (IsCMN(LHSDef, CC))
+    return emitCMN(LHSDef->getOperand(2), RHS, MIRBuilder);
+
+  // Given this:
+  // Produce this:
+  //
+  // cmn z, y
+  if (IsCMN(RHSDef, CC))
+    return emitCMN(LHS, RHSDef->getOperand(2), MIRBuilder);
+
+  // Given this:
+  //
+  // z = G_AND x, y
+  // G_ICMP z, 0
+  // Produce this if the compare is unsigned:
+  //
+  // tst x, y
+  if (!isUnsignedICMPPred(P) && LHSDef &&
+      LHSDef->getOpcode() == TargetOpcode::G_AND) {
+    // Make sure that the RHS is 0.
+    auto ValAndVReg = getConstantVRegValWithLookThrough(RHS.getReg(), MRI);
+    if (!ValAndVReg || ValAndVReg->Value != 0)
+      return nullptr;
+
+    return emitTST(LHSDef->getOperand(1).getReg(),
+                   LHSDef->getOperand(2).getReg(), MIRBuilder);
   }
 
-  if (DidFold)
-    return emitCMN(CMNLHS, CMNRHS, MIRBuilder);
   return nullptr;
 }
 
 bool AArch64InstructionSelector::tryOptVectorDup(MachineInstr &I) const {
   // Try to match a vector splat operation into a dup instruction.
   // We're looking for this pattern:
   //    %scalar:gpr(s64) = COPY $x0
   //    %undef:fpr(<2 x s64>) = G_IMPLICIT_DEF

llvm/test/CodeGen/AArch64/GlobalISel/opt-fold-compare.mir

 # NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
 # RUN: llc -mtriple aarch64-unknown-unknown -run-pass=instruction-select -verify-machineinstrs %s -o - | FileCheck %s
 #
-# Verify that we can fold G_SUB into G_ICMP when we have a pattern like this:
+# Verify folding operations into G_ICMP.
+#
+# E.g cmn/adds folding:
 #
 # x = G_SUB 0, y
 # G_ICMP intpred(something_safe) z, x
 #
+# Folds to:
+# adds z, y
+#
 # Where "something_safe" is ne or eq.
 #
+# ands/tst folding:
+#
+# z = G_AND x, y
+# G_ICMP z, 0
+#
+# Folds to:
+#
+# tst x, y
+#
+# When we have signed comparisons.
+#
 # Tests whose names start with cmn_ should use ADDS for the G_ICMP. Tests whose
-# names start with no_cmn should use SUBS.
+# names start with no_cmn should use SUBS. Similarly, tests whose names start
+# with TST should use ANDS for the G_ICMP.
 #
 
 ...
 ---
 name:            cmn_s32_rhs
 alignment:       2
 legalized:       true
 regBankSelected: true
bb.0:
     %3:gpr(s64) = G_SUB %2, %0
     %7:gpr(s32) = G_ICMP intpred(slt), %3(s64), %1
     %4:gpr(s1) = G_TRUNC %7(s32)
     %5:gpr(s64) = G_SELECT %4(s1), %6, %2
     $x0 = COPY %5(s64)
     RET_ReallyLR implicit $x0
 
 ...
+---
+name:            tst_s32
+alignment:       2
+legalized:       true
+regBankSelected: true
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $w0, $w1
+    ; CHECK-LABEL: name: tst_s32
+    ; CHECK: liveins: $w0, $w1
+    ; CHECK: [[COPY:%[0-9]+]]:gpr32 = COPY $w1
+    ; CHECK: [[MOVi32imm:%[0-9]+]]:gpr32 = MOVi32imm 0
+    ; CHECK: [[MOVi32imm1:%[0-9]+]]:gpr32 = MOVi32imm 1
+    ; CHECK: $wzr = ANDSWrr [[MOVi32imm]], [[COPY]], implicit-def $nzcv
+    ; CHECK: [[CSELWr:%[0-9]+]]:gpr32 = CSELWr [[MOVi32imm1]], [[MOVi32imm]], 0, implicit $nzcv
+    ; CHECK: $w0 = COPY [[CSELWr]]
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:gpr(s32) = COPY $w0
+    %1:gpr(s32) = COPY $w1
+    %2:gpr(s32) = G_CONSTANT i32 0
+    %6:gpr(s32) = G_CONSTANT i32 1
+    %3:gpr(s32) = G_AND %2, %1
+    %8:gpr(s32) = G_CONSTANT i32 0
+    %7:gpr(s32) = G_ICMP intpred(eq), %3(s32), %8
+    %4:gpr(s1) = G_TRUNC %7(s32)
+    %5:gpr(s32) = G_SELECT %4(s1), %6, %2
+    $w0 = COPY %5(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            tst_s64
+alignment:       2
+legalized:       true
+regBankSelected: true
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $x0, $x1
+    ; CHECK-LABEL: name: tst_s64
+    ; CHECK: liveins: $x0, $x1
+    ; CHECK: [[COPY:%[0-9]+]]:gpr64 = COPY $x1
+    ; CHECK: [[MOVi64imm:%[0-9]+]]:gpr64 = MOVi64imm 0
+    ; CHECK: [[MOVi64imm1:%[0-9]+]]:gpr64 = MOVi64imm 1
+    ; CHECK: $xzr = ANDSXrr [[MOVi64imm]], [[COPY]], implicit-def $nzcv
+    ; CHECK: [[CSELXr:%[0-9]+]]:gpr64 = CSELXr [[MOVi64imm1]], [[MOVi64imm]], 0, implicit $nzcv
+    ; CHECK: $x0 = COPY [[CSELXr]]
+    ; CHECK: RET_ReallyLR implicit $x0
+    %0:gpr(s64) = COPY $x0
+    %1:gpr(s64) = COPY $x1
+    %2:gpr(s64) = G_CONSTANT i64 0
+    %6:gpr(s64) = G_CONSTANT i64 1
+    %3:gpr(s64) = G_AND %2, %1
+    %8:gpr(s64) = G_CONSTANT i64 0
+    %7:gpr(s32) = G_ICMP intpred(eq), %3(s64), %8
+    %4:gpr(s1) = G_TRUNC %7(s32)
+    %5:gpr(s64) = G_SELECT %4(s1), %6, %2
+    $x0 = COPY %5(s64)
+    RET_ReallyLR implicit $x0
+
+...
+---
+name:            no_tst_unsigned_compare
+alignment:       2
+legalized:       true
+regBankSelected: true
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $w0, $w1
+    ; CHECK-LABEL: name: no_tst_unsigned_compare
+    ; CHECK: liveins: $w0, $w1
+    ; CHECK: [[COPY:%[0-9]+]]:gpr32 = COPY $w1
+    ; CHECK: [[MOVi32imm:%[0-9]+]]:gpr32 = MOVi32imm 0
+    ; CHECK: [[MOVi32imm1:%[0-9]+]]:gpr32 = MOVi32imm 1
+    ; CHECK: [[ANDWrr:%[0-9]+]]:gpr32common = ANDWrr [[MOVi32imm]], [[COPY]]
+    ; CHECK: $wzr = SUBSWri [[ANDWrr]], 0, 0, implicit-def $nzcv
+    ; CHECK: [[CSELWr:%[0-9]+]]:gpr32 = CSELWr [[MOVi32imm1]], [[MOVi32imm]], 8, implicit $nzcv
+    ; CHECK: $w0 = COPY [[CSELWr]]
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:gpr(s32) = COPY $w0
+    %1:gpr(s32) = COPY $w1
+    %2:gpr(s32) = G_CONSTANT i32 0
+    %6:gpr(s32) = G_CONSTANT i32 1
+    %3:gpr(s32) = G_AND %2, %1
+    %8:gpr(s32) = G_CONSTANT i32 0
+    %7:gpr(s32) = G_ICMP intpred(ugt), %3(s32), %8
+    %4:gpr(s1) = G_TRUNC %7(s32)
+    %5:gpr(s32) = G_SELECT %4(s1), %6, %2
+    $w0 = COPY %5(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            no_tst_nonzero
+alignment:       2
+legalized:       true
+regBankSelected: true
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $w0, $w1
+    ; CHECK-LABEL: name: no_tst_nonzero
+    ; CHECK: liveins: $w0, $w1
+    ; CHECK: [[COPY:%[0-9]+]]:gpr32 = COPY $w1
+    ; CHECK: [[MOVi32imm:%[0-9]+]]:gpr32 = MOVi32imm 0
+    ; CHECK: [[MOVi32imm1:%[0-9]+]]:gpr32 = MOVi32imm 1
+    ; CHECK: [[ANDWrr:%[0-9]+]]:gpr32common = ANDWrr [[MOVi32imm]], [[COPY]]
+    ; CHECK: $wzr = SUBSWri [[ANDWrr]], 42, 0, implicit-def $nzcv
+    ; CHECK: [[CSELWr:%[0-9]+]]:gpr32 = CSELWr [[MOVi32imm1]], [[MOVi32imm]], 8, implicit $nzcv
+    ; CHECK: $w0 = COPY [[CSELWr]]
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:gpr(s32) = COPY $w0
+    %1:gpr(s32) = COPY $w1
+    %2:gpr(s32) = G_CONSTANT i32 0
+    %6:gpr(s32) = G_CONSTANT i32 1
+    %3:gpr(s32) = G_AND %2, %1
+    %8:gpr(s32) = G_CONSTANT i32 42
+    %7:gpr(s32) = G_ICMP intpred(ugt), %3(s32), %8
+    %4:gpr(s1) = G_TRUNC %7(s32)
+    %5:gpr(s32) = G_SELECT %4(s1), %6, %2
+    $w0 = COPY %5(s32)
+    RET_ReallyLR implicit $w0
+
+...
+---
+name:            imm_tst
+alignment:       2
+legalized:       true
+regBankSelected: true
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $w0, $w1
+    ; CHECK-LABEL: name: imm_tst
+    ; CHECK: liveins: $w0, $w1
+    ; CHECK: [[COPY:%[0-9]+]]:gpr32 = COPY $w1
+    ; CHECK: $wzr = ANDSWri [[COPY]], 1, implicit-def $nzcv
+    ; CHECK: [[CSINCWr:%[0-9]+]]:gpr32 = CSINCWr $wzr, $wzr, 1, implicit $nzcv
+    ; CHECK: $w0 = COPY [[CSINCWr]]
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:gpr(s32) = COPY $w0
+    %1:gpr(s32) = COPY $w1
+    %2:gpr(s32) = G_CONSTANT i32 0
+    %3:gpr(s32) = G_CONSTANT i32 1
+
+    ; This can be represented as a logical immediate, so we can pull it into
+    ; the ANDS. We should get ANDSWri.
+    %4:gpr(s32) = G_CONSTANT i32 3
+
+    %5:gpr(s32) = G_AND %1, %4
+    %6:gpr(s32) = G_ICMP intpred(eq), %5(s32), %2
+    $w0 = COPY %6(s32)
+    RET_ReallyLR implicit $w0
+
+
+...
+---
+name:            no_imm_tst_not_logical_imm
+alignment:       2
+legalized:       true
+regBankSelected: true
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $w0, $w1
+    ; CHECK-LABEL: name: no_imm_tst_not_logical_imm
+    ; CHECK: liveins: $w0, $w1
+    ; CHECK: [[COPY:%[0-9]+]]:gpr32 = COPY $w1
+    ; CHECK: [[MOVi32imm:%[0-9]+]]:gpr32 = MOVi32imm -1
+    ; CHECK: $wzr = ANDSWrr [[COPY]], [[MOVi32imm]], implicit-def $nzcv
+    ; CHECK: [[CSINCWr:%[0-9]+]]:gpr32 = CSINCWr $wzr, $wzr, 1, implicit $nzcv
+    ; CHECK: $w0 = COPY [[CSINCWr]]
+    ; CHECK: RET_ReallyLR implicit $w0
+    %0:gpr(s32) = COPY $w0
+    %1:gpr(s32) = COPY $w1
+    %2:gpr(s32) = G_CONSTANT i32 0
+    %3:gpr(s32) = G_CONSTANT i32 1
+
+    ; This immediate can't be represented as a logical immediate. We shouldn't
+    ; select ANDSWri.
+    %4:gpr(s32) = G_CONSTANT i32 -1
+
+    %5:gpr(s32) = G_AND %1, %4
+    %6:gpr(s32) = G_ICMP intpred(eq), %5(s32), %2
+    $w0 = COPY %6(s32)
+    RET_ReallyLR implicit $w0