implement integer compare in mips fast-isel

[rkotler]

Summary

implement SelectCmp (integer compare ) in mips fast-isel

[rkotler]

Ran clang format on MipsFastISel.cpp

[dsanders]

LGTM with a few style and code duplication nits fixed along with an improvement to the testcase.

lib/Target/Mips/MipsFastISel.cpp

531

Style nit: This function needs some vertical spacing.

537–553

We've got some code duplication here. Both the LHS and the RHS are sign/zero extended in the same way, and we also duplicate the type checking that's inside EmitIntExt.

Can we factor it out?

611–626

These aren't needed. We already have a 'default: return false;'

test/CodeGen/Mips/Fast-ISel/icmpa.ll

22–23

Please check register numbers match between instructions using variables.

Likewise for the other tests below.

24

This instruction is redundant but we don't want to fix that in this patch. We might not want to fix it at all if it proves costly for compilation time. We should leave a comment on redundant instructions though.

Likewise for the others below

54

We ought to check that the operands appear in the right order. We can do this with variables by matching the loads first.

Likewise for the tests below

[dsanders]

lib/Target/Mips/MipsFastISel.cpp

531

What kind of vertical spacing? I'm using clang-format on this file.

I mean it needs some blank lines to break up the logical sections of the code. For example, a blank line between the LHS/RHS handling, and just before the switch would help readability.

537–553

What do you mean about duplicating tests inside of EmitIntExt?
Not sure what you are referring to.

At the moment, the caller is testing that LMVT is i8 or i16 and passes LMVT to EmitIntExt as the first argument. EmitIntExt also checks that first argument type is i8 or i16 (in its switch statement). It seems unnecessary to do it twice and have to maintain the list in both places. One possible solution is to call EmitIntExt unconditionally and have it simply return the input register when an extension isn't necessary (e.g. %1 = sext i32 %0 to i32).

[rkotler]

Make requested changes from previous review.

[rkotler]

Fix some cut and paste mistakes in the test case.

[dsanders]

Thanks. Your update fixes the most important comments but you've missed a couple. I've replied to each comment indicating whether I think it's been done or not.

lib/Target/Mips/MipsFastISel.cpp

531

This comment hasn't been handled by your update

537–553

Reed and I have chatted about the duplicate type checks and we've agreed to follow up on this in a later patch. This is because it requires refactoring EmitIntExt() so it supports i32->i32 without creating a temporary register.

The remaining part of this comment hasn't been handled by the update though. The LHS/RHS code duplication I'm referring to is:

if (LeftReg == 0)
  return false;
MVT LMVT = TLI.getValueType(Left->getType(), true).getSimpleVT();
if ((LMVT == MVT::i8) || (LMVT == MVT::i16)) {
  unsigned TempReg = createResultReg(&Mips::GPR32RegClass);
  if (!EmitIntExt(LMVT, LeftReg, MVT::i32, TempReg, IsUnsigned))
    return false;
  LeftReg = TempReg;
}

then following it is the same code with s/LeftReg/RightReg/ and s/LMVT/RMVT/. If it were only couple lines then I'd leave it but there's enough there that I'd prefer not to duplicate it.

611–626

Done

test/CodeGen/Mips/Fast-ISel/icmpa.ll

22–23

Done

24

This comment hasn't been handled.

54

Done

[rkotler]

1. Add comment as TBD to revisit the possibility of eliminating redundant andi instructions after SelectCmp
2. Refactor some code in the beginning of SelectCmp

[dsanders]

LGTM with the redundant instruction comments added to the test.

lib/Target/Mips/MipsFastISel.cpp

531

Done

537–553

Done. When you do follow up on the duplicate type checks in a later patch, I'm expecting most of getRegEnsuringSimpleIntegerWidening() to end up folded into EmitIntExt(). Please follow up on this fairly soon.

test/CodeGen/Mips/Fast-ISel/icmpa.ll

24

I think you've misunderstood me. The comment you've added to the implementation is good but I actually intended for a comment to be left on the redundant instructions of these tests. As in:

; FIXME: This instruction is redundant. The sltiu can only produce 0 and 1.
; CHECK: andi ${{[0-9]+}}, $[[REG2]], 1

The aim is to clearly mark parts of the test that are suboptimal or undesirable but we've temporarily compromised on. This helps us to remember issues we need to come back to and also helps anyone who accidentally affects this test in some way.

[rkotler]

Revision satisfying condition for LGTM.

Added comment to test case to look into possibility of removing redundant instruction during fast-isel code generation.

lib/Target/Mips/MipsFastISel.cpp

private:
   bool SelectLoad(const Instruction *I);
   bool SelectRet(const Instruction *I);
   bool SelectStore(const Instruction *I);
   bool SelectIntExt(const Instruction *I);
   bool SelectTrunc(const Instruction *I);
   bool SelectFPExt(const Instruction *I);
   bool SelectFPTrunc(const Instruction *I);
   bool SelectFPToI(const Instruction *I, bool IsSigned);
+  bool SelectCmp(const Instruction *I);
 
   bool isTypeLegal(Type *Ty, MVT &VT);
   bool isLoadTypeLegal(Type *Ty, MVT &VT);
 
+  unsigned getRegEnsuringSimpleIntegerWidening(const Value *, bool IsUnsigned);
+
   unsigned MaterializeFP(const ConstantFP *CFP, MVT VT);
   unsigned MaterializeGV(const GlobalValue *GV, MVT VT);
   unsigned MaterializeInt(const Constant *C, MVT VT);
   unsigned Materialize32BitInt(int64_t Imm, const TargetRegisterClass *RC);
 
   bool EmitIntExt(MVT SrcVT, unsigned SrcReg, MVT DestVT, unsigned DestReg,
                   bool IsZExt);
 
bool MipsFastISel::ComputeAddress(const Value *Obj, Address &Addr) {
   if (isa<Instruction>(Obj))
     return false;
   else if (isa<ConstantExpr>(Obj))
     return false;
   Addr.Base.Reg = getRegForValue(Obj);
   return Addr.Base.Reg != 0;
 }
 
+unsigned MipsFastISel::getRegEnsuringSimpleIntegerWidening(const Value *V,
+                                                           bool IsUnsigned) {
+  unsigned VReg = getRegForValue(V);
+  if (VReg == 0)
+    return 0;
+  MVT VMVT = TLI.getValueType(V->getType(), true).getSimpleVT();
+  if ((VMVT == MVT::i8) || (VMVT == MVT::i16)) {
+    unsigned TempReg = createResultReg(&Mips::GPR32RegClass);
+    if (!EmitIntExt(VMVT, VReg, MVT::i32, TempReg, IsUnsigned))
+      return 0;
+    VReg = TempReg;
+  }
+  return VReg;
+}
+
 bool MipsFastISel::EmitLoad(MVT VT, unsigned &ResultReg, Address &Addr,
                             unsigned Alignment) {
   //
   // more cases will be handled here in following patches.
   //
   unsigned Opc;
   switch (VT.SimpleTy) {
   case MVT::i32: {
if (!IsSigned)
     return false; // We don't handle this case yet. There is no native
                   // instruction for this but it can be synthesized.
   Type *DstTy = I->getType();
   if (!isTypeLegal(DstTy, DstVT))
     return false;
 
   if (DstVT != MVT::i32)
     return false;
 
   Value *Src = I->getOperand(0);
   Type *SrcTy = Src->getType();
   if (!isTypeLegal(SrcTy, SrcVT))
     return false;
 
   if (SrcVT != MVT::f32 && SrcVT != MVT::f64)
     return false;
 
   unsigned SrcReg = getRegForValue(Src);
   if (SrcReg == 0)
     return false;
 
   // Determine the opcode for the conversion, which takes place
   // entirely within FPRs.
   unsigned DestReg = createResultReg(&Mips::GPR32RegClass);
   unsigned TempReg = createResultReg(&Mips::FGR32RegClass);
   unsigned Opc;
 
   if (SrcVT == MVT::f32)
     Opc = Mips::TRUNC_W_S;
   else
     Opc = Mips::TRUNC_W_D32;
 
   // Generate the convert.
   EmitInst(Opc, TempReg).addReg(SrcReg);
 
   EmitInst(Mips::MFC1, DestReg).addReg(TempReg);
 
   updateValueMap(I, DestReg);
   return true;
 }
 
+//
+// Because of how SelectCmp is called with fast-isel, you can
+// end up with redundant "andi" instructions after the sequences emitted below.
+// We should try and solve this issue in the future.
+//
+bool MipsFastISel::SelectCmp(const Instruction *I) {
+  const CmpInst *CI = cast<CmpInst>(I);
+  bool IsUnsigned = CI->isUnsigned();
+  const Value *Left = I->getOperand(0), *Right = I->getOperand(1);
+
+  unsigned LeftReg = getRegEnsuringSimpleIntegerWidening(Left, IsUnsigned);
+  if (LeftReg == 0)
+    return false;
+  unsigned RightReg = getRegEnsuringSimpleIntegerWidening(Right, IsUnsigned);
+  if (RightReg == 0)
+    return false;
+  unsigned ResultReg = createResultReg(&Mips::GPR32RegClass);
+
+  switch (CI->getPredicate()) {
+  default:
+    return false;
+  case CmpInst::ICMP_EQ: {
+    unsigned TempReg = createResultReg(&Mips::GPR32RegClass);
+    EmitInst(Mips::XOR, TempReg).addReg(LeftReg).addReg(RightReg);
+    EmitInst(Mips::SLTiu, ResultReg).addReg(TempReg).addImm(1);
+    break;
+  }
+  case CmpInst::ICMP_NE: {
+    unsigned TempReg = createResultReg(&Mips::GPR32RegClass);
+    EmitInst(Mips::XOR, TempReg).addReg(LeftReg).addReg(RightReg);
+    EmitInst(Mips::SLTu, ResultReg).addReg(Mips::ZERO).addReg(TempReg);
+    break;
+  }
+  case CmpInst::ICMP_UGT: {
+    EmitInst(Mips::SLTu, ResultReg).addReg(RightReg).addReg(LeftReg);
+    break;
+  }
+  case CmpInst::ICMP_ULT: {
+    EmitInst(Mips::SLTu, ResultReg).addReg(LeftReg).addReg(RightReg);
+    break;
+  }
+  case CmpInst::ICMP_UGE: {
+    unsigned TempReg = createResultReg(&Mips::GPR32RegClass);
+    EmitInst(Mips::SLTu, TempReg).addReg(LeftReg).addReg(RightReg);
+    EmitInst(Mips::XORi, ResultReg).addReg(TempReg).addImm(1);
+    break;
+  }
+  case CmpInst::ICMP_ULE: {
+    unsigned TempReg = createResultReg(&Mips::GPR32RegClass);
+    EmitInst(Mips::SLTu, TempReg).addReg(RightReg).addReg(LeftReg);
+    EmitInst(Mips::XORi, ResultReg).addReg(TempReg).addImm(1);
+    break;
+  }
+  case CmpInst::ICMP_SGT: {
+    EmitInst(Mips::SLT, ResultReg).addReg(RightReg).addReg(LeftReg);
+    break;
+  }
+  case CmpInst::ICMP_SLT: {
+    EmitInst(Mips::SLT, ResultReg).addReg(LeftReg).addReg(RightReg);
+    break;
+  }
+  case CmpInst::ICMP_SGE: {
+    unsigned TempReg = createResultReg(&Mips::GPR32RegClass);
+    EmitInst(Mips::SLT, TempReg).addReg(LeftReg).addReg(RightReg);
+    EmitInst(Mips::XORi, ResultReg).addReg(TempReg).addImm(1);
+    break;
+  }
+  case CmpInst::ICMP_SLE: {
+    unsigned TempReg = createResultReg(&Mips::GPR32RegClass);
+    EmitInst(Mips::SLT, TempReg).addReg(RightReg).addReg(LeftReg);
+    EmitInst(Mips::XORi, ResultReg).addReg(TempReg).addImm(1);
+    break;
+  }
+  }
+  updateValueMap(I, ResultReg);
+  return true;
+}
+
 bool MipsFastISel::fastSelectInstruction(const Instruction *I) {
   if (!TargetSupported)
     return false;
   switch (I->getOpcode()) {
   default:
     break;
   case Instruction::Load:
     return SelectLoad(I);
bool MipsFastISel::fastSelectInstruction(const Instruction *I) {
   case Instruction::FPTrunc:
     return SelectFPTrunc(I);
   case Instruction::FPExt:
     return SelectFPExt(I);
   case Instruction::FPToSI:
     return SelectFPToI(I, /*isSigned*/ true);
   case Instruction::FPToUI:
     return SelectFPToI(I, /*isSigned*/ false);
+  case Instruction::ICmp:
+  case Instruction::FCmp:
+    return SelectCmp(I);
   }
   return false;
 }
 
 unsigned MipsFastISel::MaterializeFP(const ConstantFP *CFP, MVT VT) {
   if (UnsupportedFPMode)
     return 0;
   int64_t Imm = CFP->getValueAPF().bitcastToAPInt().getZExtValue();

test/CodeGen/Mips/Fast-ISel/icmpa.ll

+; RUN: llc -march=mipsel -relocation-model=pic -O0 -mips-fast-isel -fast-isel-abort -mcpu=mips32r2 \
+; RUN:     < %s | FileCheck %s
+; RUN: llc -march=mipsel -relocation-model=pic -O0 -mips-fast-isel -fast-isel-abort -mcpu=mips32 \
+; RUN:     < %s | FileCheck %s
+
+@c = global i32 4, align 4
+@d = global i32 9, align 4
+@uc = global i32 4, align 4
+@ud = global i32 9, align 4
+@b1 = common global i32 0, align 4
+
+; Function Attrs: nounwind
+define void @eq()  {
+entry:
+; CHECK-LABEL:  .ent  eq
+
+  %0 = load i32* @c, align 4
+  %1 = load i32* @d, align 4
+  %cmp = icmp eq i32 %0, %1
+  %conv = zext i1 %cmp to i32
+; CHECK-DAG:  lw  $[[REG_D_GOT:[0-9+]]], %got(d)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_C_GOT:[0-9+]]], %got(c)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_D:[0-9]+]], 0($[[REG_D_GOT]])
+; CHECK-DAG:  lw  $[[REG_C:[0-9]+]], 0($[[REG_C_GOT]])
+; CHECK:  xor  $[[REG1:[0-9]+]], $[[REG_C]], $[[REG_D]]
+; CHECK:  sltiu  $[[REG2:[0-9]+]], $[[REG1]], 1
+; FIXME: This instruction is redundant. The sltiu can only produce 0 and 1.
+; CHECK:  andi  ${{[0-9]+}}, $[[REG2]], 1
+
+  store i32 %conv, i32* @b1, align 4
+  ret void
+}
+
+; Function Attrs: nounwind
+define void @ne()  {
+entry:
+; CHECK-LABEL:  .ent  ne
+  %0 = load i32* @c, align 4
+  %1 = load i32* @d, align 4
+  %cmp = icmp ne i32 %0, %1
+  %conv = zext i1 %cmp to i32
+; CHECK-DAG:  lw  $[[REG_D_GOT:[0-9+]]], %got(d)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_C_GOT:[0-9+]]], %got(c)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_D:[0-9]+]], 0($[[REG_D_GOT]])
+; CHECK-DAG:  lw  $[[REG_C:[0-9]+]], 0($[[REG_C_GOT]])
+; CHECK:  xor  $[[REG1:[0-9]+]], $[[REG_C]], $[[REG_D]]
+; CHECK:  sltu  $[[REG2:[0-9]+]], $zero, $[[REG1]]
+; CHECK:  andi  ${{[0-9]+}}, $[[REG2]], 1
+
+  store i32 %conv, i32* @b1, align 4
+  ret void
+}
+
+; Function Attrs: nounwind
+define void @ugt()  {
+entry:
+; CHECK-LABEL:  .ent  ugt
+  %0 = load i32* @uc, align 4
+  %1 = load i32* @ud, align 4
+  %cmp = icmp ugt i32 %0, %1
+  %conv = zext i1 %cmp to i32
+; CHECK-DAG:  lw  $[[REG_UD_GOT:[0-9+]]], %got(ud)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_UC_GOT:[0-9+]]], %got(uc)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_UD:[0-9]+]], 0($[[REG_UD_GOT]])
+; CHECK-DAG:  lw  $[[REG_UC:[0-9]+]], 0($[[REG_UC_GOT]])
+; CHECK:  sltu  $[[REG1:[0-9]+]], $[[REG_UD]], $[[REG_UC]]
+; CHECK:  andi  ${{[0-9]+}}, $[[REG1]], 1
+
+  store i32 %conv, i32* @b1, align 4
+  ret void
+}
+
+; Function Attrs: nounwind
+define void @ult()  {
+entry:
+; CHECK-LABEL:  .ent  ult
+  %0 = load i32* @uc, align 4
+  %1 = load i32* @ud, align 4
+  %cmp = icmp ult i32 %0, %1
+  %conv = zext i1 %cmp to i32
+; CHECK-DAG:  lw  $[[REG_UD_GOT:[0-9+]]], %got(ud)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_UC_GOT:[0-9+]]], %got(uc)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_UD:[0-9]+]], 0($[[REG_UD_GOT]])
+; CHECK-DAG:  lw  $[[REG_UC:[0-9]+]], 0($[[REG_UC_GOT]])
+; CHECK:  sltu  $[[REG1:[0-9]+]], $[[REG_UC]], $[[REG_UD]]
+; CHECK:  andi  ${{[0-9]+}}, $[[REG1]], 1
+  store i32 %conv, i32* @b1, align 4
+  ret void
+}
+
+; Function Attrs: nounwind
+define void @uge()  {
+entry:
+; CHECK-LABEL:  .ent  uge
+  %0 = load i32* @uc, align 4
+  %1 = load i32* @ud, align 4
+  %cmp = icmp uge i32 %0, %1
+  %conv = zext i1 %cmp to i32
+; CHECK-DAG:  lw  $[[REG_UD_GOT:[0-9+]]], %got(ud)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_UC_GOT:[0-9+]]], %got(uc)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_UD:[0-9]+]], 0($[[REG_UD_GOT]])
+; CHECK-DAG:  lw  $[[REG_UC:[0-9]+]], 0($[[REG_UC_GOT]])
+; CHECK:  sltu  $[[REG1:[0-9]+]], $[[REG_UC]], $[[REG_UD]]
+; CHECK:  xori  $[[REG2:[0-9]+]], $[[REG1]], 1
+; CHECK:  andi  ${{[0-9]+}}, $[[REG2]], 1
+  store i32 %conv, i32* @b1, align 4
+  ret void
+}
+
+; Function Attrs: nounwind
+define void @ule()  {
+entry:
+; CHECK-LABEL:  .ent  ule
+  %0 = load i32* @uc, align 4
+  %1 = load i32* @ud, align 4
+  %cmp = icmp ule i32 %0, %1
+  %conv = zext i1 %cmp to i32
+; CHECK-DAG:  lw  $[[REG_UD_GOT:[0-9+]]], %got(ud)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_UC_GOT:[0-9+]]], %got(uc)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_UD:[0-9]+]], 0($[[REG_UD_GOT]])
+; CHECK-DAG:  lw  $[[REG_UC:[0-9]+]], 0($[[REG_UC_GOT]])
+; CHECK:  sltu  $[[REG1:[0-9]+]], $[[REG_UD]], $[[REG_UC]]
+; CHECK:  xori  $[[REG2:[0-9]+]], $[[REG1]], 1
+; CHECK:  andi  ${{[0-9]+}}, $[[REG2]], 1
+  store i32 %conv, i32* @b1, align 4
+  ret void
+}
+
+; Function Attrs: nounwind
+define void @sgt()  {
+entry:
+; CHECK-LABEL:  .ent sgt
+  %0 = load i32* @c, align 4
+  %1 = load i32* @d, align 4
+  %cmp = icmp sgt i32 %0, %1
+  %conv = zext i1 %cmp to i32
+; CHECK-DAG:  lw  $[[REG_D_GOT:[0-9+]]], %got(d)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_C_GOT:[0-9+]]], %got(c)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_D:[0-9]+]], 0($[[REG_D_GOT]])
+; CHECK-DAG:  lw  $[[REG_C:[0-9]+]], 0($[[REG_C_GOT]])
+; CHECK:  slt  $[[REG1:[0-9]+]], $[[REG_D]], $[[REG_C]]
+; CHECK:  andi  ${{[0-9]+}}, $[[REG1]], 1
+  store i32 %conv, i32* @b1, align 4
+  ret void
+}
+
+; Function Attrs: nounwind
+define void @slt()  {
+entry:
+; CHECK-LABEL:  .ent slt
+  %0 = load i32* @c, align 4
+  %1 = load i32* @d, align 4
+  %cmp = icmp slt i32 %0, %1
+  %conv = zext i1 %cmp to i32
+; CHECK-DAG:  lw  $[[REG_D_GOT:[0-9+]]], %got(d)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_C_GOT:[0-9+]]], %got(c)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_D:[0-9]+]], 0($[[REG_D_GOT]])
+; CHECK-DAG:  lw  $[[REG_C:[0-9]+]], 0($[[REG_C_GOT]])
+; CHECK:  slt  $[[REG1:[0-9]+]], $[[REG_C]], $[[REG_D]]
+; CHECK:  andi  ${{[0-9]+}}, $[[REG1]], 1
+  store i32 %conv, i32* @b1, align 4
+  ret void
+}
+
+; Function Attrs: nounwind
+define void @sge()  {
+entry:
+; CHECK-LABEL:  .ent sge
+  %0 = load i32* @c, align 4
+  %1 = load i32* @d, align 4
+  %cmp = icmp sge i32 %0, %1
+  %conv = zext i1 %cmp to i32
+  store i32 %conv, i32* @b1, align 4
+; CHECK-DAG:  lw  $[[REG_D_GOT:[0-9+]]], %got(d)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_C_GOT:[0-9+]]], %got(c)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_D:[0-9]+]], 0($[[REG_D_GOT]])
+; CHECK-DAG:  lw  $[[REG_C:[0-9]+]], 0($[[REG_C_GOT]])
+; CHECK:  slt  $[[REG1:[0-9]+]], $[[REG_C]], $[[REG_D]]
+; CHECK:  xori  $[[REG2:[0-9]+]], $[[REG1]], 1
+; CHECK:  andi  ${{[0-9]+}}, $[[REG2]], 1
+  ret void
+}
+
+; Function Attrs: nounwind
+define void @sle()  {
+entry:
+; CHECK-LABEL:  .ent sle
+  %0 = load i32* @c, align 4
+  %1 = load i32* @d, align 4
+  %cmp = icmp sle i32 %0, %1
+  %conv = zext i1 %cmp to i32
+; CHECK-DAG:  lw  $[[REG_D_GOT:[0-9+]]], %got(d)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_C_GOT:[0-9+]]], %got(c)(${{[0-9]+}})
+; CHECK-DAG:  lw  $[[REG_D:[0-9]+]], 0($[[REG_D_GOT]])
+; CHECK-DAG:  lw  $[[REG_C:[0-9]+]], 0($[[REG_C_GOT]])
+; CHECK:        slt     $[[REG1:[0-9]+]], $[[REG_D]], $[[REG_C]]
+; CHECK:        xori    $[[REG2:[0-9]+]], $[[REG1]], 1
+; CHECK:        andi    ${{[0-9]+}}, $[[REG2]], 1
+  store i32 %conv, i32* @b1, align 4
+  ret void
+}
+
+