[SelectionDAG][RISCV] Teach ComputeNumSignBits to handle SREM.

[craig.topper]

Summary

This also removes a pattern from RISCV that is no longer needed
since the sexti32 on the LHS of the srem in the pattern implies
the result is sign extended so the sign_extend_inreg should be
removed in DAG combine now.

[luismarques]

LGTM. Nice!

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

3877

This is a lot more relaxed than ValueTracking ?

[luismarques]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

3877

Interesting! ValueTracking seems to abort on !Denominator->isStrictlyPositive(). When I reviewed the logic of this code at first I thought there would be cases where it would break, but when I thought about it more deeply it all seemed fine. Now I'm curious about what may explain the divergence. Maybe the implementation in ValueTracking was considering modulus instead of remainder?

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

3877

The implementation in value tracking only handles constant right hand side. Looking at the history, its original implementation was incorrect and maybe thought the result was always positive at least from the the original comment.

I didn't handle constant here because I figured most targets would expand an srem by constant using BuildSDIV in TargetLowering.

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

3877

It might make sense to update ValueTracking to hanldle the non-constant case. Some experiments I did from C seemed to get helped by CorrelatedValuePropagation. For example a shl after an srem with extra sign bits can pick up an nsw flag through CVP. This allows InstSimplify/InstCombine to late remover a shl+ashr sign extend pair due to the nsw.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

3877

That sounds like a great followup but I'm happy for this to go ahead independently. Thanks for looking into this.

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

 //===- SelectionDAG.cpp - Implement the SelectionDAG data structures ------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (SignBitsOp0 == 1)
       break;
     unsigned SignBitsOp1 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
     if (SignBitsOp1 == 1)
       break;
     unsigned OutValidBits =
         (VTBits - SignBitsOp0 + 1) + (VTBits - SignBitsOp1 + 1);
     return OutValidBits > VTBits ? 1 : VTBits - OutValidBits + 1;
   }
+  case ISD::SREM:
+    // The sign bit is the LHS's sign bit, except when the result of the
+    // remainder is zero. The magnitude of the result should be less than or
+    // equal to the magnitude of the LHS. Therefore, the result should have
+    // at least as many sign bits as the left hand side.
+    return ComputeNumSignBits(Op.getOperand(0), DemandedElts, Depth + 1);
   case ISD::TRUNCATE: {
     // Check if the sign bits of source go down as far as the truncated value.
     unsigned NumSrcBits = Op.getOperand(0).getScalarValueSizeInBits();
     unsigned NumSrcSignBits = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
     if (NumSrcSignBits > (NumSrcBits - VTBits))
       return NumSrcSignBits - (NumSrcBits - VTBits);
     break;
   }

llvm/lib/Target/RISCV/RISCVInstrInfoM.td

def : Pat<(and (riscv_remuw (assertzexti32 GPR:$rs1),
                             (assertzexti32 GPR:$rs2)), 0xffffffff),
           (REMU GPR:$rs1, GPR:$rs2)>;
 
 // Although the sexti32 operands may not have originated from an i32 srem,
 // this pattern is safe as it is impossible for two sign extended inputs to
 // produce a result where res[63:32]=0 and res[31]=1.
 def : Pat<(srem (sexti32 GPR:$rs1), (sexti32 GPR:$rs2)),
           (REMW GPR:$rs1, GPR:$rs2)>;
-def : Pat<(sext_inreg (srem (sexti32 GPR:$rs1),
-                            (sexti32 GPR:$rs2)), i32),
-          (REMW GPR:$rs1, GPR:$rs2)>;
 } // Predicates = [HasStdExtM, IsRV64]

llvm/test/CodeGen/Mips/llvm-ir/srem.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=mips -mcpu=mips2 -relocation-model=pic \
-; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP32,GP32R0R2
+; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP32
 ; RUN: llc < %s -mtriple=mips -mcpu=mips32 -relocation-model=pic \
-; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP32,GP32R0R2
+; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP32
 ; RUN: llc < %s -mtriple=mips -mcpu=mips32r2 -relocation-model=pic \
-; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP32,GP32R2R5
+; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP32
 ; RUN: llc < %s -mtriple=mips -mcpu=mips32r3 -relocation-model=pic \
-; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP32,GP32R2R5
+; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP32
 ; RUN: llc < %s -mtriple=mips -mcpu=mips32r5 -relocation-model=pic \
-; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP32,GP32R2R5
+; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP32
 ; RUN: llc < %s -mtriple=mips -mcpu=mips32r6 -relocation-model=pic \
 ; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefix=GP32R6
 
 ; RUN: llc < %s -mtriple=mips64 -mcpu=mips3 -relocation-model=pic \
-; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP64,GP64R0R1
+; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP64
 ; RUN: llc < %s -mtriple=mips64 -mcpu=mips4 -relocation-model=pic \
-; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP64,GP64R0R1
+; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP64
 ; RUN: llc < %s -mtriple=mips64 -mcpu=mips64 -relocation-model=pic \
-; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP64,GP64R0R1
+; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP64
 ; RUN: llc < %s -mtriple=mips64 -mcpu=mips64r2 -relocation-model=pic \
-; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP64,GP64R2R5
+; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP64
 ; RUN: llc < %s -mtriple=mips64 -mcpu=mips64r3 -relocation-model=pic \
-; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP64,GP64R2R5
+; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP64
 ; RUN: llc < %s -mtriple=mips64 -mcpu=mips64r5 -relocation-model=pic \
-; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP64,GP64R2R5
+; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefixes=GP64
 ; RUN: llc < %s -mtriple=mips64 -mcpu=mips64r6 -relocation-model=pic \
 ; RUN:   -mips-jalr-reloc=false | FileCheck %s -check-prefix=GP64R6
 
 ; RUN: llc < %s -mtriple=mips -mcpu=mips32r3 -mattr=+micromips \
 ; RUN:   -relocation-model=pic -mips-jalr-reloc=false | \
 ; RUN:   FileCheck %s -check-prefix=MMR3
 ; RUN: llc < %s -mtriple=mips -mcpu=mips32r6 -mattr=+micromips \
 ; RUN:   -relocation-model=pic -mips-jalr-reloc=false | \

 ; MMR6-NEXT:    li16 $2, 0
 ; MMR6-NEXT:    jrc $ra
 entry:
   %r = srem i1 %a, %b
   ret i1 %r
 }
 
 define signext i8 @srem_i8(i8 signext %a, i8 signext %b) {
-; GP32R0R2-LABEL: srem_i8:
-; GP32R0R2:       # %bb.0: # %entry
-; GP32R0R2-NEXT:    div $zero, $4, $5
-; GP32R0R2-NEXT:    teq $5, $zero, 7
-; GP32R0R2-NEXT:    mfhi $1
-; GP32R0R2-NEXT:    sll $1, $1, 24
-; GP32R0R2-NEXT:    jr $ra
-; GP32R0R2-NEXT:    sra $2, $1, 24
-;
-; GP32R2R5-LABEL: srem_i8:
-; GP32R2R5:       # %bb.0: # %entry
-; GP32R2R5-NEXT:    div $zero, $4, $5
-; GP32R2R5-NEXT:    teq $5, $zero, 7
-; GP32R2R5-NEXT:    mfhi $1
-; GP32R2R5-NEXT:    jr $ra
-; GP32R2R5-NEXT:    seb $2, $1
+; GP32-LABEL: srem_i8:
+; GP32:       # %bb.0: # %entry
+; GP32-NEXT:    div $zero, $4, $5
+; GP32-NEXT:    teq $5, $zero, 7
+; GP32-NEXT:    jr $ra
+; GP32-NEXT:    mfhi $2
 ;
 ; GP32R6-LABEL: srem_i8:
 ; GP32R6:       # %bb.0: # %entry
-; GP32R6-NEXT:    mod $1, $4, $5
+; GP32R6-NEXT:    mod $2, $4, $5
 ; GP32R6-NEXT:    teq $5, $zero, 7
-; GP32R6-NEXT:    jr $ra
-; GP32R6-NEXT:    seb $2, $1
+; GP32R6-NEXT:    jrc $ra
 ;
-; GP64R0R1-LABEL: srem_i8:
-; GP64R0R1:       # %bb.0: # %entry
-; GP64R0R1-NEXT:    div $zero, $4, $5
-; GP64R0R1-NEXT:    teq $5, $zero, 7
-; GP64R0R1-NEXT:    mfhi $1
-; GP64R0R1-NEXT:    sll $1, $1, 24
-; GP64R0R1-NEXT:    jr $ra
-; GP64R0R1-NEXT:    sra $2, $1, 24
-;
-; GP64R2R5-LABEL: srem_i8:
-; GP64R2R5:       # %bb.0: # %entry
-; GP64R2R5-NEXT:    div $zero, $4, $5
-; GP64R2R5-NEXT:    teq $5, $zero, 7
-; GP64R2R5-NEXT:    mfhi $1
-; GP64R2R5-NEXT:    jr $ra
-; GP64R2R5-NEXT:    seb $2, $1
+; GP64-LABEL: srem_i8:
+; GP64:       # %bb.0: # %entry
+; GP64-NEXT:    div $zero, $4, $5
+; GP64-NEXT:    teq $5, $zero, 7
+; GP64-NEXT:    jr $ra
+; GP64-NEXT:    mfhi $2
 ;
 ; GP64R6-LABEL: srem_i8:
 ; GP64R6:       # %bb.0: # %entry
-; GP64R6-NEXT:    mod $1, $4, $5
+; GP64R6-NEXT:    mod $2, $4, $5
 ; GP64R6-NEXT:    teq $5, $zero, 7
-; GP64R6-NEXT:    jr $ra
-; GP64R6-NEXT:    seb $2, $1
+; GP64R6-NEXT:    jrc $ra
 ;
 ; MMR3-LABEL: srem_i8:
 ; MMR3:       # %bb.0: # %entry
 ; MMR3-NEXT:    div $zero, $4, $5
 ; MMR3-NEXT:    teq $5, $zero, 7
-; MMR3-NEXT:    mfhi16 $1
-; MMR3-NEXT:    jr $ra
-; MMR3-NEXT:    seb $2, $1
+; MMR3-NEXT:    mfhi16 $2
+; MMR3-NEXT:    jrc $ra
 ;
 ; MMR6-LABEL: srem_i8:
 ; MMR6:       # %bb.0: # %entry
-; MMR6-NEXT:    mod $1, $4, $5
+; MMR6-NEXT:    mod $2, $4, $5
 ; MMR6-NEXT:    teq $5, $zero, 7
-; MMR6-NEXT:    seb $2, $1
 ; MMR6-NEXT:    jrc $ra
 entry:
   %r = srem i8 %a, %b
   ret i8 %r
 }
 
 define signext i16 @srem_i16(i16 signext %a, i16 signext %b) {
-; GP32R0R2-LABEL: srem_i16:
-; GP32R0R2:       # %bb.0: # %entry
-; GP32R0R2-NEXT:    div $zero, $4, $5
-; GP32R0R2-NEXT:    teq $5, $zero, 7
-; GP32R0R2-NEXT:    mfhi $1
-; GP32R0R2-NEXT:    sll $1, $1, 16
-; GP32R0R2-NEXT:    jr $ra
-; GP32R0R2-NEXT:    sra $2, $1, 16
-;
-; GP32R2R5-LABEL: srem_i16:
-; GP32R2R5:       # %bb.0: # %entry
-; GP32R2R5-NEXT:    div $zero, $4, $5
-; GP32R2R5-NEXT:    teq $5, $zero, 7
-; GP32R2R5-NEXT:    mfhi $1
-; GP32R2R5-NEXT:    jr $ra
-; GP32R2R5-NEXT:    seh $2, $1
+; GP32-LABEL: srem_i16:
+; GP32:       # %bb.0: # %entry
+; GP32-NEXT:    div $zero, $4, $5
+; GP32-NEXT:    teq $5, $zero, 7
+; GP32-NEXT:    jr $ra
+; GP32-NEXT:    mfhi $2
 ;
 ; GP32R6-LABEL: srem_i16:
 ; GP32R6:       # %bb.0: # %entry
-; GP32R6-NEXT:    mod $1, $4, $5
+; GP32R6-NEXT:    mod $2, $4, $5
 ; GP32R6-NEXT:    teq $5, $zero, 7
-; GP32R6-NEXT:    jr $ra
-; GP32R6-NEXT:    seh $2, $1
+; GP32R6-NEXT:    jrc $ra
 ;
-; GP64R0R1-LABEL: srem_i16:
-; GP64R0R1:       # %bb.0: # %entry
-; GP64R0R1-NEXT:    div $zero, $4, $5
-; GP64R0R1-NEXT:    teq $5, $zero, 7
-; GP64R0R1-NEXT:    mfhi $1
-; GP64R0R1-NEXT:    sll $1, $1, 16
-; GP64R0R1-NEXT:    jr $ra
-; GP64R0R1-NEXT:    sra $2, $1, 16
-;
-; GP64R2R5-LABEL: srem_i16:
-; GP64R2R5:       # %bb.0: # %entry
-; GP64R2R5-NEXT:    div $zero, $4, $5
-; GP64R2R5-NEXT:    teq $5, $zero, 7
-; GP64R2R5-NEXT:    mfhi $1
-; GP64R2R5-NEXT:    jr $ra
-; GP64R2R5-NEXT:    seh $2, $1
+; GP64-LABEL: srem_i16:
+; GP64:       # %bb.0: # %entry
+; GP64-NEXT:    div $zero, $4, $5
+; GP64-NEXT:    teq $5, $zero, 7
+; GP64-NEXT:    jr $ra
+; GP64-NEXT:    mfhi $2
 ;
 ; GP64R6-LABEL: srem_i16:
 ; GP64R6:       # %bb.0: # %entry
-; GP64R6-NEXT:    mod $1, $4, $5
+; GP64R6-NEXT:    mod $2, $4, $5
 ; GP64R6-NEXT:    teq $5, $zero, 7
-; GP64R6-NEXT:    jr $ra
-; GP64R6-NEXT:    seh $2, $1
+; GP64R6-NEXT:    jrc $ra
 ;
 ; MMR3-LABEL: srem_i16:
 ; MMR3:       # %bb.0: # %entry
 ; MMR3-NEXT:    div $zero, $4, $5
 ; MMR3-NEXT:    teq $5, $zero, 7
-; MMR3-NEXT:    mfhi16 $1
-; MMR3-NEXT:    jr $ra
-; MMR3-NEXT:    seh $2, $1
+; MMR3-NEXT:    mfhi16 $2
+; MMR3-NEXT:    jrc $ra
 ;
 ; MMR6-LABEL: srem_i16:
 ; MMR6:       # %bb.0: # %entry
-; MMR6-NEXT:    mod $1, $4, $5
+; MMR6-NEXT:    mod $2, $4, $5
 ; MMR6-NEXT:    teq $5, $zero, 7
-; MMR6-NEXT:    seh $2, $1
 ; MMR6-NEXT:    jrc $ra
 entry:
   %r = srem i16 %a, %b
   ret i16 %r
 }
 
 define signext i32 @srem_i32(i32 signext %a, i32 signext %b) {
 ; GP32-LABEL: srem_i32:

llvm/test/CodeGen/RISCV/rv64m-exhaustive-w-insts.ll

; RV64IM-NEXT:    ret
   %1 = srem i32 %a, %b
   ret i32 %1
 }
 
 define signext i8 @sext_remw_sext_sext_i8(i8 signext %a, i8 signext %b) nounwind {
 ; RV64IM-LABEL: sext_remw_sext_sext_i8:
 ; RV64IM:       # %bb.0:
 ; RV64IM-NEXT:    remw a0, a0, a1
-; RV64IM-NEXT:    slli a0, a0, 56
-; RV64IM-NEXT:    srai a0, a0, 56
 ; RV64IM-NEXT:    ret
   %1 = srem i8 %a, %b
   ret i8 %1
 }
 
 define signext i16 @sext_remw_sext_sext_i16(i16 signext %a, i16 signext %b) nounwind {
 ; RV64IM-LABEL: sext_remw_sext_sext_i16:
 ; RV64IM:       # %bb.0:
 ; RV64IM-NEXT:    remw a0, a0, a1
-; RV64IM-NEXT:    slli a0, a0, 48
-; RV64IM-NEXT:    srai a0, a0, 48
 ; RV64IM-NEXT:    ret
   %1 = srem i16 %a, %b
   ret i16 %1
 }
 
 define signext i32 @sext_i32_remw_zext_sext_i16(i16 zeroext %0, i16 signext %1) nounwind {
 ; RV64IM-LABEL: sext_i32_remw_zext_sext_i16:
 ; RV64IM:       # %bb.0:
 ; RV64IM-NEXT:    rem a0, a0, a1
 ; RV64IM-NEXT:    slli a0, a0, 32
 ; RV64IM-NEXT:    srli a0, a0, 32
 ; RV64IM-NEXT:    ret
   %3 = sext i16 %1 to i32
   %4 = zext i16 %0 to i32
   %5 = srem i32 %4, %3
   ret i32 %5
 }
 
 define signext i32 @sext_i32_remw_sext_zext_i16(i16 signext %a, i16 zeroext %b) nounwind {
 ; RV64IM-LABEL: sext_i32_remw_sext_zext_i16:
 ; RV64IM:       # %bb.0:
 ; RV64IM-NEXT:    rem a0, a0, a1
-; RV64IM-NEXT:    sext.w a0, a0
 ; RV64IM-NEXT:    ret
   %1 = sext i16 %a to i32
   %2 = zext i16 %b to i32
   %3 = srem i32 %1, %2
   ret i32 %3
 }
 
 define i32 @aext_remuw_aext_aext(i32 %a, i32 %b) nounwind {