[ConstantRanges] Use APInt for constant case for urem/srem.

[fhahn]

Summary

Currently UREM & SREM on constant ranges produces overly pessimistic
results for single element constant ranges.

Delegate to APInt's implementation if both operands are single element
constant ranges. We already do something similar for other binary
operators, like binary AND.o

Fixes PR49731.

[nikic]

What does this do if the single element on the RHS is zero?

[fhahn]

In D105115#2846981, @nikic wrote:

What does this do if the single element on the RHS is zero?

Oh, APInt::urem/srem assert that RHS is not zero. I updated the code to directly handle the case by return an empty range. I think we could further simplify the compares against UREM/SREM by 0, but currently that is not happening as we force empty ranges to overdefined when resolving undefs.

[lebedev.ri]

LG

[nikic]

llvm/lib/IR/ConstantRange.cpp

1224

This should be if (const APInt *RHSInt = RHS.getSingleElement()). Same for the other isSingleElement + getSingleElement combinations.

[fhahn]

Rebase & use getSingleElement in top-most if.

[fhahn]

llvm/lib/IR/ConstantRange.cpp

1224

Updated, thanks!

[lebedev.ri]

llvm/lib/IR/ConstantRange.cpp

1229–1230

Technically these also can be if(const APInt *LHSInt = getSingleElement()) return {LHSInt->urem(*RHSInt)};

[fhahn]

llvm/lib/IR/ConstantRange.cpp

1229–1230

yeah I 'll update that in the committed version

llvm/lib/IR/ConstantRange.cpp

if (contains(Zero) && (!PosR.isEmptySet() || !NegR.isEmptySet()))
     Res = Res.unionWith(ConstantRange(Zero));
   return Res;
 }
 
 ConstantRange ConstantRange::urem(const ConstantRange &RHS) const {
   if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
     return getEmpty();
 
+  if (const APInt *RHSInt = RHS.getSingleElement()) {
+    // UREM by null is UB.
+    if (RHSInt->isNullValue())
+      return getEmpty();
+    // Use APInt's implementation of UREM for single element ranges.
+    if (const APInt *LHSInt = getSingleElement())
+      return {LHSInt->urem(*RHSInt)};
+  }
+
   // L % R for L < R is L.
   if (getUnsignedMax().ult(RHS.getUnsignedMin()))
     return *this;
 
   // L % R is <= L and < R.
   APInt Upper = APIntOps::umin(getUnsignedMax(), RHS.getUnsignedMax() - 1) + 1;
   return getNonEmpty(APInt::getNullValue(getBitWidth()), std::move(Upper));
 }
 
 ConstantRange ConstantRange::srem(const ConstantRange &RHS) const {
   if (isEmptySet() || RHS.isEmptySet())
     return getEmpty();
 
+  if (const APInt *RHSInt = RHS.getSingleElement()) {
+    // SREM by null is UB.
+    if (RHSInt->isNullValue())
+      return getEmpty();
+    // Use APInt's implementation of SREM for single element ranges.
+    if (const APInt *LHSInt = getSingleElement())
+      return {LHSInt->srem(*RHSInt)};
+  }
+
   ConstantRange AbsRHS = RHS.abs();
   APInt MinAbsRHS = AbsRHS.getUnsignedMin();
   APInt MaxAbsRHS = AbsRHS.getUnsignedMax();
 
   // Modulus by zero is UB.
   if (MaxAbsRHS.isNullValue())
     return getEmpty();
 

llvm/test/Transforms/SCCP/binaryops-range-special-cases.ll

bb3:
   call void @use(i1 %c.0)
   %c.1 = icmp eq i32 %p, %d
   call void @use(i1 %c.1)
   ret void
 }
 
 define void @urem_cmp_constants() {
 ; CHECK-LABEL: @urem_cmp_constants(
-; CHECK-NEXT:    [[UREM_1:%.*]] = urem i16 12704, 12704
-; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i16 [[UREM_1]], 0
-; CHECK-NEXT:    call void @use(i1 [[C_1]])
-; CHECK-NEXT:    [[C_2:%.*]] = icmp eq i16 [[UREM_1]], 1
-; CHECK-NEXT:    call void @use(i1 [[C_2]])
-; CHECK-NEXT:    [[UREM_2:%.*]] = urem i16 12704, 3
-; CHECK-NEXT:    [[C_3:%.*]] = icmp eq i16 [[UREM_2]], 2
-; CHECK-NEXT:    call void @use(i1 [[C_3]])
-; CHECK-NEXT:    [[C_4:%.*]] = icmp eq i16 [[UREM_2]], 1
-; CHECK-NEXT:    call void @use(i1 [[C_4]])
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[UREM_3:%.*]] = urem i16 12704, 0
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp eq i16 [[UREM_3]], 1
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    ret void
 ;
   %sel = select i1 false, i16 0, i16 12704
   %urem.1 = urem i16 %sel, 12704
   %c.1 = icmp eq i16 %urem.1, 0
   call void @use(i1 %c.1)
   %c.2 = icmp eq i16 %urem.1, 1
   call void @use(i1 %c.2)
   %urem.2 = urem i16 %sel, 3
   %c.3 = icmp eq i16 %urem.2, 2
   call void @use(i1 %c.3)
   %c.4 = icmp eq i16 %urem.2, 1
   call void @use(i1 %c.4)
   %urem.3 = urem i16 %sel, 0
   %c.5 = icmp eq i16 %urem.3, 1
   call void @use(i1 %c.5)
   ret void
 }
 
 define void @srem_cmp_constants() {
 ; CHECK-LABEL: @srem_cmp_constants(
-; CHECK-NEXT:    [[SREM_1:%.*]] = srem i16 12704, 12704
-; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i16 [[SREM_1]], 0
-; CHECK-NEXT:    call void @use(i1 [[C_1]])
-; CHECK-NEXT:    [[C_2:%.*]] = icmp eq i16 [[SREM_1]], 1
-; CHECK-NEXT:    call void @use(i1 [[C_2]])
-; CHECK-NEXT:    [[SREM_2:%.*]] = srem i16 12704, 3
-; CHECK-NEXT:    [[C_3:%.*]] = icmp eq i16 [[SREM_2]], 2
-; CHECK-NEXT:    call void @use(i1 [[C_3]])
-; CHECK-NEXT:    [[C_4:%.*]] = icmp eq i16 [[SREM_2]], 1
-; CHECK-NEXT:    call void @use(i1 [[C_4]])
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[SREM_3:%.*]] = srem i16 12704, 0
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp eq i16 [[SREM_3]], 1
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    ret void
 ;
   %sel = select i1 false, i16 0, i16 12704
   %srem.1 = srem i16 %sel, 12704
   %c.1 = icmp eq i16 %srem.1, 0