[RISCV] Add patterns to MIR sign-extension removal pass.

[mohammed-nurulhoque]

Summary

This patch adds a few instruction patterns that generate sign-extended values or propagate them, adding to the pass introduced in https://reviews.llvm.org/D116397

[mohammed-nurulhoque]

Noticed one of my patterns was redundant (merged)
Combined the independent if-statements with the switch-statement
Added tests where this patch removes sext.w that previously were not.

[mohammed-nurulhoque]

This is my first patch submission for LLVM and I'd appreciate your feedback if I should have done some things differently.

[craig.topper]

llvm/lib/Target/RISCV/RISCVSExtWRemoval.cpp

95

Please upload patches with full context using -U999999 as noted here https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

112

ANDI was already handled in an if statement right below this switch. That code is now dead.

180

This doesn't work for DIVU

0xffffffffffffffff / 2 = 0x7fffffffffffffff

0xffffffffffffffff has all sign bits, but 0x7fffffffffffffff only has 1 sign bit.

It doesn't work for REMU either
0xffffffffffffffff % 0x8000000000000000 = 0x7fffffffffffffff

[craig.topper]

llvm/lib/Target/RISCV/RISCVSExtWRemoval.cpp

176

SDIV doesn't work, but not for the reason cited. If the dividend has 32 sign bits, then it isn't INT64_MIN so the overflow case of INT64_MIN/-1 can't happen.

The reason it doesn't work is because the SDIV instruction returns -2^63 for division by 0. That only has 1 sign bit. Division by 0 isn't undefined behavior at the MI level since the instruction has a definition.

[mohammed-nurulhoque]

Thank you for your feedback. I fixed these errors now.
In the comment about DIV, by saying (long)0x8000 0000, I meant 0xffff fffff 8000 0000 which is a valid counter-example.
It turns out REMU doesn't work if only the dividend is sign-extended as you pointed out, but it propagates the sign-extension if both arguments are sign-extended.
I verified REM and REMU using https://alive2.llvm.org/ce/ with the following snippets. (Used i8/i16 instead of i32/i64 because it would time out otherwise, but it's the same principle).

REM:

define i16 @src(i8 %arg1, i16 %arg2) nounwind {
        %1 = sext i8 %arg1 to i16
        %2 = srem i16 %1, %arg2
        %3 = trunc i16 %2 to i8
        %4 = sext i8 %3 to i16
        ret i16 %4
}

define i16 @tgt(i8 %arg1, i16 %arg2) nounwind {
        %1 = sext i8 %arg1 to i16
        %2 = srem i16 %1, %arg2
        ret i16 %2
}

REMU:

define i16 @src(i8 %arg1, i8 %arg2) nounwind {
        %1 = sext i8 %arg1 to i16
        %2 = sext i8 %arg2 to i16
        %3 = urem i16 %1, %2
        %4 = trunc i16 %3 to i8
        %5 = sext i8 %4 to i16
        ret i16 %5
}
define i16 @tgt(i8 %arg1, i8 %arg2) nounwind {
        %1 = sext i8 %arg1 to i16
        %2 = sext i8 %arg2 to i16
        %3 = urem i16 %1, %2
        ret i16 %3
}

[craig.topper]

LGTM

[mohammed-nurulhoque]

Thanks. Could you please commit the changes as I don't have commit access?

[craig.topper]

In D117465#3254034, @mohammed-nurulhoque wrote:

Thanks. Could you please commit the changes as I don't have commit access?

Yes. Can you provide your name and email as you'd like it in the git log.

[mohammed-nurulhoque]

Mohammed Nurul Hoque
[e-mail]

llvm/lib/Target/RISCV/RISCVSExtWRemoval.cpp

static bool isSignExtendingOpW(const MachineInstr &MI) {
   case RISCV::FCVT_WU_H:
   case RISCV::FCVT_W_S:
   case RISCV::FCVT_WU_S:
   case RISCV::FCVT_W_D:
   case RISCV::FCVT_WU_D:
   // The following aren't W instructions, but are either sign extended from a
   // smaller size or put zeros in bits 63:31.
   case RISCV::LBU:
   case RISCV::LHU:
   case RISCV::LB:
   case RISCV::LH:
+  case RISCV::SLT:
+  case RISCV::SLTI:
+  case RISCV::SLTU:
+  case RISCV::SLTIU:
   case RISCV::SEXTB:
   case RISCV::SEXTH:
   case RISCV::ZEXTH_RV64:
     return true;
-  }
-
+  // shifting right sufficiently makes the value 32-bit sign-extended
+  case RISCV::SRAI:
+    return MI.getOperand(2).getImm() >= 32;
+  case RISCV::SRLI:
+    return MI.getOperand(2).getImm() > 32;
   // The LI pattern ADDI rd, X0, imm is sign extended.
-  if (MI.getOpcode() == RISCV::ADDI && MI.getOperand(1).isReg() &&
-      MI.getOperand(1).getReg() == RISCV::X0)
-    return true;
-
+  case RISCV::ADDI:
+    return MI.getOperand(1).isReg() && MI.getOperand(1).getReg() == RISCV::X0;
   // An ANDI with an 11 bit immediate will zero bits 63:11.
-  if (MI.getOpcode() == RISCV::ANDI && isUInt<11>(MI.getOperand(2).getImm()))
-    return true;
-
+  case RISCV::ANDI:
+    return isUInt<11>(MI.getOperand(2).getImm());
+  // An ORI with an >11 bit immediate (negative 12-bit) will set bits 63:11.
+  case RISCV::ORI:
+    return !isUInt<11>(MI.getOperand(2).getImm());
   // Copying from X0 produces zero.
-  if (MI.getOpcode() == RISCV::COPY && MI.getOperand(1).getReg() == RISCV::X0)
-    return true;
+  case RISCV::COPY:
+    return MI.getOperand(1).getReg() == RISCV::X0;
+  }
 
   return false;
 }
 
 static bool isSignExtendedW(const MachineInstr &OrigMI,
                             MachineRegisterInfo &MRI) {
 
   SmallPtrSet<const MachineInstr *, 4> Visited;
case RISCV::COPY: {
       const MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
       if (!SrcMI)
         return false;
 
       // Add SrcMI to the worklist.
       Worklist.push_back(SrcMI);
       break;
     }
+    case RISCV::REM:
     case RISCV::ANDI:
     case RISCV::ORI:
     case RISCV::XORI: {
+      // |Remainder| is always <= |Dividend|. If D is 32-bit, then so is R.
+      // DIV doesn't work because of the edge case 0xf..f 8000 0000 / (long)-1
       // Logical operations use a sign extended 12-bit immediate. We just need
       // to check if the other operand is sign extended.
       Register SrcReg = MI->getOperand(1).getReg();
       if (!SrcReg.isVirtual())
         return false;
       const MachineInstr *SrcMI = MRI.getVRegDef(SrcReg);
       if (!SrcMI)
         return false;
 
       // Add SrcMI to the worklist.
       Worklist.push_back(SrcMI);
       break;
     }
+    case RISCV::REMU:
     case RISCV::AND:
     case RISCV::OR:
     case RISCV::XOR:
     case RISCV::ANDN:
     case RISCV::ORN:
     case RISCV::XNOR:
     case RISCV::MAX:
     case RISCV::MAXU:

llvm/test/CodeGen/RISCV/sextw-removal.ll

bb2:                                              ; preds = %bb2, %bb
   %i5 = fptosi float %i4 to i32
   %i6 = fcmp oeq float %i4, zeroinitializer
   br i1 %i6, label %bb7, label %bb2
 
 bb7:                                              ; preds = %bb2
   ret void
 }
 declare float @baz(i32 signext %i3)
+
+define void @test8(i32 signext %arg, i32 signext %arg1) nounwind {
+; CHECK-LABEL: test8:
+; CHECK:       # %bb.0: # %bb
+; CHECK-NEXT:    addi sp, sp, -16
+; CHECK-NEXT:    sd ra, 8(sp) # 8-byte Folded Spill
+; CHECK-NEXT:    sraw a0, a0, a1
+; CHECK-NEXT:  .LBB6_1: # %bb2
+; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    call foo@plt
+; CHECK-NEXT:    ori a0, a0, -256
+; CHECK-NEXT:    bnez a0, .LBB6_1
+; CHECK-NEXT:  # %bb.2: # %bb7
+; CHECK-NEXT:    ld ra, 8(sp) # 8-byte Folded Reload
+; CHECK-NEXT:    addi sp, sp, 16
+; CHECK-NEXT:    ret
+;
+; NOREMOVAL-LABEL: test8:
+; NOREMOVAL:       # %bb.0: # %bb
+; NOREMOVAL-NEXT:    addi sp, sp, -16
+; NOREMOVAL-NEXT:    sd ra, 8(sp) # 8-byte Folded Spill
+; NOREMOVAL-NEXT:    sraw a0, a0, a1
+; NOREMOVAL-NEXT:  .LBB6_1: # %bb2
+; NOREMOVAL-NEXT:    # =>This Inner Loop Header: Depth=1
+; NOREMOVAL-NEXT:    sext.w a0, a0
+; NOREMOVAL-NEXT:    call foo@plt
+; NOREMOVAL-NEXT:    ori a0, a0, -256
+; NOREMOVAL-NEXT:    bnez a0, .LBB6_1
+; NOREMOVAL-NEXT:  # %bb.2: # %bb7
+; NOREMOVAL-NEXT:    ld ra, 8(sp) # 8-byte Folded Reload
+; NOREMOVAL-NEXT:    addi sp, sp, 16
+; NOREMOVAL-NEXT:    ret
+bb:
+  %i = ashr i32 %arg, %arg1
+  br label %bb2
+
+bb2:                                              ; preds = %bb2, %bb
+  %i3 = phi i32 [ %i, %bb ], [ %i6, %bb2 ]
+  %i4 = tail call signext i64 @foo(i32 signext %i3)
+  %i5 = or i64 %i4, -256
+  %i6 = trunc i64 %i5 to i32
+  %i7 = icmp eq i32 %i6, 0
+  br i1 %i7, label %bb7, label %bb2
+
+bb7:                                              ; preds = %bb2
+  ret void
+}
+
+declare i64 @foo(i32 signext)
+
+define void @test9(i32 signext %arg, i32 signext %arg1) nounwind {
+; CHECK-LABEL: test9:
+; CHECK:       # %bb.0: # %bb
+; CHECK-NEXT:    addi sp, sp, -16
+; CHECK-NEXT:    sd ra, 8(sp) # 8-byte Folded Spill
+; CHECK-NEXT:    sd s0, 0(sp) # 8-byte Folded Spill
+; CHECK-NEXT:    sraw a0, a0, a1
+; CHECK-NEXT:    li s0, 254
+; CHECK-NEXT:  .LBB7_1: # %bb2
+; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    call bar@plt
+; CHECK-NEXT:    mv a1, a0
+; CHECK-NEXT:    slti a0, a0, 255
+; CHECK-NEXT:    blt s0, a1, .LBB7_1
+; CHECK-NEXT:  # %bb.2: # %bb7
+; CHECK-NEXT:    ld ra, 8(sp) # 8-byte Folded Reload
+; CHECK-NEXT:    ld s0, 0(sp) # 8-byte Folded Reload
+; CHECK-NEXT:    addi sp, sp, 16
+; CHECK-NEXT:    ret
+;
+; NOREMOVAL-LABEL: test9:
+; NOREMOVAL:       # %bb.0: # %bb
+; NOREMOVAL-NEXT:    addi sp, sp, -16
+; NOREMOVAL-NEXT:    sd ra, 8(sp) # 8-byte Folded Spill
+; NOREMOVAL-NEXT:    sd s0, 0(sp) # 8-byte Folded Spill
+; NOREMOVAL-NEXT:    sraw a1, a0, a1
+; NOREMOVAL-NEXT:    li s0, 254
+; NOREMOVAL-NEXT:  .LBB7_1: # %bb2
+; NOREMOVAL-NEXT:    # =>This Inner Loop Header: Depth=1
+; NOREMOVAL-NEXT:    sext.w a0, a1
+; NOREMOVAL-NEXT:    call bar@plt
+; NOREMOVAL-NEXT:    slti a1, a0, 255
+; NOREMOVAL-NEXT:    blt s0, a0, .LBB7_1
+; NOREMOVAL-NEXT:  # %bb.2: # %bb7
+; NOREMOVAL-NEXT:    ld ra, 8(sp) # 8-byte Folded Reload
+; NOREMOVAL-NEXT:    ld s0, 0(sp) # 8-byte Folded Reload
+; NOREMOVAL-NEXT:    addi sp, sp, 16
+; NOREMOVAL-NEXT:    ret
+bb:
+  %i = ashr i32 %arg, %arg1
+  br label %bb2
+
+bb2:                                              ; preds = %bb2, %bb
+  %i3 = phi i32 [ %i, %bb ], [ %i7, %bb2 ]
+  %i4 = tail call signext i32 @bar(i32 signext %i3)
+  %i5 = icmp slt i32 %i4, 255
+  %i6 = sext i1 %i5 to i32
+  %i7 = sub i32 0, %i6
+  br i1 %i5, label %bb7, label %bb2
+
+bb7:                                              ; preds = %bb2
+  ret void
+}