[mips][FastISel] Implement shift ops for Mips Fast-Isel.

[vkalintiris]

Summary

Add shift operators implementation to Fast-Isel for Mips. These are shift ops
for non legal forms, i.e. i8 and i16.

Based on a patch by Reed Kotler.

[dsanders]

Testcase? Also, one common nit is that many of the comments lack capitalization.

From the patch summary:

Am reviewing this myself now but passes all of test-suite.

The patch summary is supposed to be the commit message you intend to use. This kind of thing ought to be a follow up comment.

lib/Target/Mips/MipsFastISel.cpp

1304–1324 ↗

(On Diff #17458)

Can you show me a test case that requires this? At the moment, the old code sounds correct to me and I think the consumers of this value should be sign/zero extending if they care about particular values of the undefined portion of the register.

1430 ↗

(On Diff #17458)

The first section of code needs some vertical whitespace to break up the logical parts. It's a page of solid code at the moment.

1443–1449 ↗

(On Diff #17458)

Just a comment:
I expect a lot of clutter could be eliminated by moving the createResultReg() and associated code inside the emit*() functions and returning the register or 0 for failure.

Then this code here would be something like:

MVT Op0MVT = ...;
Op0Reg = emitIntSExt(Op0MVT, ...);
if (!Op0Reg)
  return false;

It also allows the emit functions to handle nops by returning an operand register and constant 0 by returning $zero which will be useful in some cases.

1451–1452 ↗

(On Diff #17458)

Shouldn't this comment come just before the if-statement on line 1442?

Also, I don't think this is limited to AShr and we don't need to do it if the operand came from a SExtInst. I think LShr ought to be zero extending unless the operand comes from a ZExtInst.

1463–1465 ↗

(On Diff #17458)

Is this comment still true? You already have sign extension code for operand 0 above.

[rkotler]

Freshen up patch to tip of tree.

[echristo]

Hi Reed,

Inline comments. Also, everything Daniel said.

-eric

lib/Target/Mips/MipsFastISel.cpp

1297 ↗

(On Diff #20797)

I'd add this assert:

assert((DVT.SimpleTy != MVT::i32 && DVT.SimpleTy != MVT::i64) && "i64 and i32 should have been handled by target-independent fast-isel!");

1448 ↗

(On Diff #20797)

Is this an actual error or what?

1473 ↗

(On Diff #20797)

Is this an actual error or what?

[rkotler]

I am working on the make check test. Attached is the C code that was the original test case.

shftop.c684 BDownload

lib/Target/Mips/MipsFastISel.cpp

1304–1324 ↗

(On Diff #17458)

This is definitely there to fix some failure in test-suite that will show up without this. It's clearly not incorrect to add this code. The whole way that fast-isel skirts around not having a legalizer is dubious at times. I don't know how easy it will be to create a separate test case for this. So it's a problem with an earlier patch but only shows up if you add this patch to it.

So we clearly cannot check in the rest of the patch without this because test-suite will have failures. So I consider it to be part of implementing this patch.

1304–1324 ↗

(On Diff #17458)

My recollection is that other fast-isel ports do not implement the shift ops for non legalized types which is why they are not seeing this issue.

1451–1452 ↗

(On Diff #17458)

Yes, the comment needs to be moved above.

I don't think we need sign extension unless we have AShr. What is in the register is already an 8, 16 bit value. It's as if there was an 8, 16 bit register. These are treated as if they are legal types but they are not really legal. We want to use a 32 bit form of shift which will have the right semantics unless it's an AShr.

In the case of an Ashr, it will not behave properly unless we have sign extended the value into a 32 bit register.

This patch BTW passes all of test suite and there are tests where getting this semantics right counts.

1463–1465 ↗

(On Diff #17458)

Correct. The comment does not belong anymore.

[rkotler]

The C code for the test case was modified. I will finish it up tomorrow.

shftopm.ll4 KBDownload

This patch is so old I forgot that I had to modify it to create the proper clang IR for this test.

[rkotler]

Add test case/

[rkotler]

lib/Target/Mips/MipsFastISel.cpp

1297 ↗

(On Diff #20797)

If we want to add that then why not just a simple LLVM_Unreachable ??

1448 ↗

(On Diff #20797)

I think it should be impossible to get that because we are only calling this function upon seeing one of those instructions. I think I added that case to avoid compiler warnings when compiling this.

In fastSelectionInstruction

case Instruction::Shl:
case Instruction::LShr:
case Instruction::AShr:
  return selectShift(I);

1473 ↗

(On Diff #20797)

I think it should be impossible to get that because we are only calling this function upon seeing one of those instructions. I think I added that case to avoid compiler warnings when compiling this.

[echristo]

Replies inline.

-eric

lib/Target/Mips/MipsFastISel.cpp

1297 ↗

(On Diff #20797)

Because SimpleTy are more than the two you have there and you'd like to make sure that all of the possible types that come in are handled rather than say that you've handled all of them?

1448 ↗

(On Diff #20797)

Makes sense. Go ahead and make your comment more descriptive of what instructions you expect to see.

[dsanders]

lib/Target/Mips/MipsFastISel.cpp

1297 ↗

(On Diff #20797)

I assume Reed meant something like:

default:
  return false;
case MVT::i32:
case MVT::i64:
  llvm_unreachable("Text");
  return false;

I was recently informed that llvm_unreachable() is pretty much the same thing as assert(0 && "Text") and that they are removed in release builds (and even informs the optimizer that the path is unreachable). On that basis, an assert() is slightly preferable to a llvm_unreachable().

1304–1324 ↗

(On Diff #17458)

A separate test case is ideal, but pointing me at the test-suite failure and the bad assembly within it will suffice.

I'm not saying that I think the zero extension is unnecessary, I just suspect that the wrong LLVM-IR expansion is doing it.
My suspicion is that the consumer of the value is reading the whole register instead of either forcing a zero extension itself or reading just the bits it expects to operate on. It could well be selectShift() since it currently doesn't zero-extend the operand for a LShr.

For example:

%0 = trunc i32 %a to i16
%1 = trunc i32 %b to i16
%2 = add i16 %0, %1

clearly doesn't need either of the zero extensions this code will currently create but:

%0 = trunc i32 %a to i16
%1 = trunc i32 %b to i16
%2 = lshr i16 %0, i32 3

needs lshr to zero extend the input register before use.

1451–1452 ↗

(On Diff #17458)

Also, I don't think this is limited to AShr and we don't need to do it if the operand came from a SExtInst. I think LShr ought to be zero extending
unless the operand comes from a ZExtInst.

I don't think we need sign extension unless we have AShr. What is in the register is already an 8, 16 bit value. It's as if there was an 8, 16 bit
register. These are treated as if they are legal types but they are not really legal. We want to use a 32 bit form of shift which will have the right
semantics unless it's an AShr.

In the case of an Ashr, it will not behave properly unless we have sign extended the value into a 32 bit register.

I agree with the arguments and explanation here but I think you may have missed my key question. The question I'm trying to ask is: Why doesn't LShr zero extend the input register just like AShr sign extends the input register? Similarly to AShr it will be implementing this with a 32-bit shift right and surely therefore requires zero extension to i32 to happen first. I suspect the reason this currently passes the test suite is because the code in selectTrunc() that I've raised comments about is concealing the bug in selectShift() for LShr.

The secondary part of the comment is that we also don't need to sign-extend if the operand in question is already a suitable sign-extend operation.

[vkalintiris]

Sign/Zero extend operand for right arithmetic/logical shifts.

[dsanders]

Vasileios is going to be taking over our Fast ISel work since Reed is needed elsewhere. Vasileios's (and my) first priority is to clear out the patch backlog, then he'll move on to cleaning things up and removing some unnecessary restrictions (e.g. PIC is currently required even for operations that don't involve addresses).

@vkalintiris: Thanks for sorting out the inconsistency between sign/zero-extension handling. That was the main issue I had with the patch.

Could you change the subject and description to be more commit-message like? Also, could you add something like 'Based on a patch by Reed Kotler' or 'Patch by Reed Kotler with some changes by Vasileios Kalintiris'. Reed should still get credit for his work.

lib/Target/Mips/MipsFastISel.cpp

1390 ↗

(On Diff #23836)

Nit: Could you add some appropriate vertical whitespace here? It's quite a long block of code at the moment.

1402–1403 ↗

(On Diff #23836)

Nit: Capitalization and punctuation. Also the second comment line is blank

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

20 ↗

(On Diff #23836)

Nit: Could you switch this over to CHECK-LABEL? Also, it's more usual to check for 'sll:'.

29–30 ↗

(On Diff #23836)

Nit: Indentation. Likewise for a few other cases below

31 ↗

(On Diff #23836)

Nit: Not necessary if we use CHECK-LABEL for the start label.

136–208 ↗

(On Diff #23836)

Nit: Please remove this. It's not adding anything to the test.

209–217 ↗

(On Diff #23836)

Nit: We should be able to remove this too.

[vkalintiris]

Addressed nits.

[dsanders]

LGTM, Thanks.

llvm/trunk/lib/Target/Mips/MipsFastISel.cpp

private:
   bool selectBranch(const Instruction *I);
   bool selectCmp(const Instruction *I);
   bool selectFPExt(const Instruction *I);
   bool selectFPTrunc(const Instruction *I);
   bool selectFPToInt(const Instruction *I, bool IsSigned);
   bool selectRet(const Instruction *I);
   bool selectTrunc(const Instruction *I);
   bool selectIntExt(const Instruction *I);
+  bool selectShift(const Instruction *I);
 
   // Utility helper routines.
   bool isTypeLegal(Type *Ty, MVT &VT);
   bool isTypeSupported(Type *Ty, MVT &VT);
   bool isLoadTypeLegal(Type *Ty, MVT &VT);
   bool computeAddress(const Value *Obj, Address &Addr);
   bool computeCallAddress(const Value *V, Address &Addr);
   void simplifyAddress(Address &Addr);

 
 unsigned MipsFastISel::emitIntExt(MVT SrcVT, unsigned SrcReg, MVT DestVT,
                                   bool isZExt) {
   unsigned DestReg = createResultReg(&Mips::GPR32RegClass);
   bool Success = emitIntExt(SrcVT, SrcReg, DestVT, DestReg, isZExt);
   return Success ? DestReg : 0;
 }
 
+bool MipsFastISel::selectShift(const Instruction *I) {
+  MVT RetVT;
+
+  if (!isTypeSupported(I->getType(), RetVT))
+    return false;
+
+  unsigned ResultReg = createResultReg(&Mips::GPR32RegClass);
+  if (!ResultReg)
+    return false;
+
+  unsigned Opcode = I->getOpcode();
+  const Value *Op0 = I->getOperand(0);
+  unsigned Op0Reg = getRegForValue(Op0);
+  if (!Op0Reg)
+    return false;
+
+  // If AShr or LShr, then we need to make sure the operand0 is sign extended.
+  if (Opcode == Instruction::AShr || Opcode == Instruction::LShr) {
+    unsigned TempReg = createResultReg(&Mips::GPR32RegClass);
+    if (!TempReg)
+      return false;
+
+    MVT Op0MVT = TLI.getValueType(Op0->getType(), true).getSimpleVT();
+    bool IsZExt = Opcode == Instruction::LShr;
+    if (!emitIntExt(Op0MVT, Op0Reg, MVT::i32, TempReg, IsZExt))
+      return false;
+
+    Op0Reg = TempReg;
+  }
+
+  if (const auto *C = dyn_cast<ConstantInt>(I->getOperand(1))) {
+    uint64_t ShiftVal = C->getZExtValue();
+
+    switch (Opcode) {
+    default:
+      llvm_unreachable("Unexpected instruction.");
+    case Instruction::Shl:
+      Opcode = Mips::SLL;
+      break;
+    case Instruction::AShr:
+      Opcode = Mips::SRA;
+      break;
+    case Instruction::LShr:
+      Opcode = Mips::SRL;
+      break;
+    }
+
+    emitInst(Opcode, ResultReg).addReg(Op0Reg).addImm(ShiftVal);
+    updateValueMap(I, ResultReg);
+    return true;
+  }
+
+  unsigned Op1Reg = getRegForValue(I->getOperand(1));
+  if (!Op1Reg)
+    return false;
+
+  switch (Opcode) {
+  default:
+    llvm_unreachable("Unexpected instruction.");
+  case Instruction::Shl:
+    Opcode = Mips::SLLV;
+    break;
+  case Instruction::AShr:
+    Opcode = Mips::SRAV;
+    break;
+  case Instruction::LShr:
+    Opcode = Mips::SRLV;
+    break;
+  }
+
+  emitInst(Opcode, ResultReg).addReg(Op0Reg).addReg(Op1Reg);
+  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);
   case Instruction::Store:
     return selectStore(I);
+  case Instruction::Shl:
+  case Instruction::LShr:
+  case Instruction::AShr:
+    return selectShift(I);
   case Instruction::And:
   case Instruction::Or:
   case Instruction::Xor:
     return selectLogicalOp(I);
   case Instruction::Br:
     return selectBranch(I);
   case Instruction::Ret:
     return selectRet(I);

llvm/trunk/test/CodeGen/Mips/Fast-ISel/shftopm.ll

+; RUN: llc -march=mipsel -relocation-model=pic -O0 -mips-fast-isel \
+; RUN:     -fast-isel-abort=1 -mcpu=mips32r2  < %s | FileCheck %s
+; RUN: llc -march=mipsel -relocation-model=pic -O0 -mips-fast-isel \
+; RUN:     -fast-isel-abort=1 -mcpu=mips32 < %s | FileCheck %s
+
+@s1 = global i16 -89, align 2
+@s2 = global i16 4, align 2
+@us1 = global i16 -503, align 2
+@us2 = global i16 5, align 2
+@s3 = common global i16 0, align 2
+@us3 = common global i16 0, align 2
+
+define void @sll() {
+entry:
+  %0 = load i16, i16* @s1, align 2
+  %1 = load i16, i16* @s2, align 2
+  %shl = shl i16 %0, %1
+  store i16 %shl, i16* @s3, align 2
+; CHECK-LABEL:  sll:
+; CHECK:        lui     $[[REG_GPa:[0-9]+]], %hi(_gp_disp)
+; CHECK-DAG:    addiu   $[[REG_GPb:[0-9]+]], $[[REG_GPa]], %lo(_gp_disp)
+; CHECK-DAG:    addu    $[[REG_GP:[0-9]+]], $[[REG_GPb]], $25
+; CHECK-DAG:    lw      $[[S3_ADDR:[0-9]+]], %got(s3)($[[REG_GP]])
+; CHECK-DAG:    lw      $[[S2_ADDR:[0-9]+]], %got(s2)($[[REG_GP]])
+; CHECK-DAG:    lw      $[[S1_ADDR:[0-9]+]], %got(s1)($[[REG_GP]])
+; CHECK-DAG:    lhu     $[[S1:[0-9]+]], 0($[[S1_ADDR]])
+; CHECK-DAG:    lhu     $[[S2:[0-9]+]], 0($[[S2_ADDR]])
+; CHECK:        sllv    $[[RES:[0-9]+]], $[[S1]], $[[S2]]
+; CHECK:        sh      $[[RES]], 0($[[S3_ADDR]])
+  ret void
+}
+
+define void @slli() {
+entry:
+  %0 = load i16, i16* @s1, align 2
+  %shl = shl i16 %0, 5
+  store i16 %shl, i16* @s3, align 2
+; CHECK-LABEL:  slli:
+; CHECK:        lui     $[[REG_GPa:[0-9]+]], %hi(_gp_disp)
+; CHECK-DAG:    addiu   $[[REG_GPb:[0-9]+]], $[[REG_GPa]], %lo(_gp_disp)
+; CHECK-DAG:    addu    $[[REG_GP:[0-9]+]], $[[REG_GPb]], $25
+; CHECK-DAG:    lw      $[[S3_ADDR:[0-9]+]], %got(s3)($[[REG_GP]])
+; CHECK-DAG:    lw      $[[S1_ADDR:[0-9]+]], %got(s1)($[[REG_GP]])
+; CHECK-DAG:    lhu     $[[S1:[0-9]+]], 0($[[S1_ADDR]])
+; CHECK:        sll     $[[RES:[0-9]+]], $[[S1]],  5
+; CHECK:        sh      $[[RES]], 0($[[S3_ADDR]])
+  ret void
+}
+
+define void @srl() {
+entry:
+  %0 = load i16, i16* @us1, align 2
+  %1 = load i16, i16* @us2, align 2
+  %shr = lshr i16 %0, %1
+  store i16 %shr, i16* @us3, align 2
+  ret void
+; CHECK-LABEL:  srl:
+; CHECK:        lui     $[[REG_GPa:[0-9]+]], %hi(_gp_disp)
+; CHECK-DAG:    addiu   $[[REG_GPb:[0-9]+]], $[[REG_GPa]], %lo(_gp_disp)
+; CHECK-DAG:    addu    $[[REG_GP:[0-9]+]], $[[REG_GPb]], $25
+; CHECK-DAG:    lw      $[[US3_ADDR:[0-9]+]], %got(us3)($[[REG_GP]])
+; CHECK-DAG:    lw      $[[US2_ADDR:[0-9]+]], %got(us2)($[[REG_GP]])
+; CHECK-DAG:    lw      $[[US1_ADDR:[0-9]+]], %got(us1)($[[REG_GP]])
+; CHECK-DAG:    lhu     $[[US1:[0-9]+]], 0($[[US1_ADDR]])
+; CHECK-DAG:    lhu     $[[US2:[0-9]+]], 0($[[US2_ADDR]])
+; CHECK:        srlv    $[[RES:[0-9]+]], $[[US1]], $[[US2]]
+; CHECK:        sh      $[[RES]], 0($[[S3_ADDR]])
+}
+
+define void @srli() {
+entry:
+  %0 = load i16, i16* @us1, align 2
+  %shr = lshr i16 %0, 4
+  store i16 %shr, i16* @us3, align 2
+; CHECK-LABEL:  srli:
+; CHECK:        lui     $[[REG_GPa:[0-9]+]], %hi(_gp_disp)
+; CHECK-DAG:    addiu   $[[REG_GPb:[0-9]+]], $[[REG_GPa]], %lo(_gp_disp)
+; CHECK-DAG:    addu    $[[REG_GP:[0-9]+]], $[[REG_GPb]], $25
+; CHECK-DAG:    lw      $[[US3_ADDR:[0-9]+]], %got(us3)($[[REG_GP]])
+; CHECK-DAG:    lw      $[[US1_ADDR:[0-9]+]], %got(us1)($[[REG_GP]])
+; CHECK-DAG:    lhu     $[[US1:[0-9]+]], 0($[[US1_ADDR]])
+; CHECK:        srl     $[[RES:[0-9]+]], $[[US1]], 4
+; CHECK:        sh      $[[RES]], 0($[[S3_ADDR]])
+  ret void
+}
+
+define void @sra() {
+entry:
+  %0 = load i16, i16* @s1, align 2
+  %1 = load i16, i16* @s2, align 2
+  %shr = ashr i16 %0, %1
+  store i16 %shr, i16* @s3, align 2
+; CHECK-LABEL:  sra:
+; CHECK:        lui     $[[REG_GPa:[0-9]+]], %hi(_gp_disp)
+; CHECK-DAG:    addiu   $[[REG_GPb:[0-9]+]], $[[REG_GPa]], %lo(_gp_disp)
+; CHECK-DAG:    addu    $[[REG_GP:[0-9]+]], $[[REG_GPb]], $25
+; CHECK-DAG:    lw      $[[S3_ADDR:[0-9]+]], %got(s3)($[[REG_GP]])
+; CHECK-DAG:    lw      $[[S2_ADDR:[0-9]+]], %got(s2)($[[REG_GP]])
+; CHECK-DAG:    lw      $[[S1_ADDR:[0-9]+]], %got(s1)($[[REG_GP]])
+; CHECK-DAG:    lhu     $[[S1:[0-9]+]], 0($[[S1_ADDR]])
+; CHECK-DAG:    lhu     $[[S2:[0-9]+]], 0($[[S2_ADDR]])
+; CHECK:        srav    $[[RES:[0-9]+]], $[[S1]], $[[S2]]
+; CHECK:        sh      $[[RES]], 0($[[S3_ADDR]])
+  ret void
+}
+
+define void @srai() {
+entry:
+  %0 = load i16, i16* @s1, align 2
+  %shr = ashr i16 %0, 2
+  store i16 %shr, i16* @s3, align 2
+; CHECK-LABEL:  srai:
+; CHECK:        lui     $[[REG_GPa:[0-9]+]], %hi(_gp_disp)
+; CHECK-DAG:    addiu   $[[REG_GPb:[0-9]+]], $[[REG_GPa]], %lo(_gp_disp)
+; CHECK-DAG:    addu    $[[REG_GP:[0-9]+]], $[[REG_GPb]], $25
+; CHECK-DAG:    lw      $[[S3_ADDR:[0-9]+]], %got(s3)($[[REG_GP]])
+; CHECK-DAG:    lw      $[[S1_ADDR:[0-9]+]], %got(s1)($[[REG_GP]])
+; CHECK-DAG:    lhu     $[[S1:[0-9]+]], 0($[[S1_ADDR]])
+; CHECK:        sra     $[[RES:[0-9]+]], $[[S1]], 2
+; CHECK:        sh      $[[RES]], 0($[[S3_ADDR]])
+  ret void
+}