[CVP] Simplify SRem when constantrange abs(lhs) < abs(rhs)

[StephenFan]

Summary

For srem x, y, if abs(constant range of x) less than abs(constant
range of y), we can simplify it as:
srem x, y => x if y is guaranteed to be positive.
'srem x, y => -x' if y is guaranteed to be negative.

[nikic]

Proof: https://alive2.llvm.org/ce/z/ExGwu7

[nikic]

In D140405#4008361, @nikic wrote:

Proof: https://alive2.llvm.org/ce/z/ExGwu7

Actually, this shows that this is not correct as implemented: You should always simplify to LHS, independent of RHS sign. srem result has the same sign as LHS, not RHS.

[lebedev.ri]

In D140405#4008367, @nikic wrote:

In D140405#4008361, @nikic wrote:

Proof: https://alive2.llvm.org/ce/z/ExGwu7

Actually, this shows that this is not correct as implemented: You should always simplify to LHS, independent of RHS sign. srem result has the same sign as LHS, not RHS.

Looks like the srem.ll is missing such test, too.

[StephenFan]

Only simplify LHS.

[nikic]

LGTM

llvm/test/Transforms/CorrelatedValuePropagation/srem.ll

541

nit: I think it would be cleaner to return i32 %rem from these tests, rather than using in an icmp that doesn't really seem relevant.

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
   return narrowUDivOrURem(Instr, LVI);
 }
 
 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
   assert(SDI->getOpcode() == Instruction::SRem);
   if (SDI->getType()->isVectorTy())
     return false;
 
+  ConstantRange LCR = LVI->getConstantRange(SDI->getOperand(0), SDI);
+  ConstantRange RCR = LVI->getConstantRange(SDI->getOperand(1), SDI);
+
+  if (LCR.abs().icmp(CmpInst::ICMP_ULT, RCR.abs())) {
+    Value *NewV = nullptr;
+    Domain Divisor = getDomain(SDI->getOperand(1), LVI, SDI);
+    if (Divisor == Domain::NonNegative)
+      NewV = SDI->getOperand(0);
+    else if (Divisor == Domain::NonPositive)
+      NewV = BinaryOperator::CreateNeg(
+          SDI->getOperand(0), SDI->getOperand(0)->getName() + ".neg", SDI);
+
+    if (NewV) {
+      SDI->replaceAllUsesWith(NewV);
+      SDI->eraseFromParent();
+      return true;
+    }
+  }
+
   struct Operand {
     Value *V;
     Domain D;
   };
   std::array<Operand, 2> Ops;
 
   for (const auto I : zip(Ops, SDI->operands())) {
     Operand &Op = std::get<0>(I);

llvm/test/Transforms/CorrelatedValuePropagation/srem.ll

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X_CMP:%.*]] = icmp slt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[X_CMP2:%.*]] = icmp sgt i8 [[X]], -10
 ; CHECK-NEXT:    [[AND_X:%.*]] = and i1 [[X_CMP]], [[X_CMP2]]
 ; CHECK-NEXT:    [[Y_CMP:%.*]] = icmp sge i8 [[Y:%.*]], 10
 ; CHECK-NEXT:    [[AND_COND:%.*]] = and i1 [[AND_X]], [[Y_CMP]]
 ; CHECK-NEXT:    br i1 [[AND_COND]], label [[IF_ELSE:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[REM:%.*]] = srem i8 [[X]], [[Y]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[REM]], [[X]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[X]], [[X]]
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.then:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %x.cmp = icmp slt i8 %x, 10
   %x.cmp2 = icmp sgt i8 %x, -10
   %and.x = and i1 %x.cmp, %x.cmp2
   %y.cmp = icmp sge i8 %y, 10
   %and.cond = and i1 %and.x, %y.cmp
   br i1 %and.cond, label %if.else, label %if.then
 
 if.else:                                          ; preds = %entry
   %rem = srem i8 %x, %y
   %cmp = icmp ne i8 %rem, %x
   ret void
 
 if.then:                                          ; preds = %entry, %if.then6, %if.end4
   ret void
 }
 
 define dso_local void @abs_x_lt_abs_y_positive_unsigned_cmp(i8 %x, i8 %y) {
 ; CHECK-LABEL: @abs_x_lt_abs_y_positive_unsigned_cmp(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X_CMP:%.*]] = icmp slt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[X_CMP2:%.*]] = icmp sgt i8 [[X]], -10
 ; CHECK-NEXT:    [[AND_X:%.*]] = and i1 [[X_CMP]], [[X_CMP2]]
 ; CHECK-NEXT:    [[Y_CMP:%.*]] = icmp uge i8 [[Y:%.*]], 10
 ; CHECK-NEXT:    [[Y_CMP2:%.*]] = icmp ule i8 [[Y]], 20
 ; CHECK-NEXT:    [[AND_Y:%.*]] = and i1 [[Y_CMP]], [[Y_CMP2]]
 ; CHECK-NEXT:    [[AND_COND:%.*]] = and i1 [[AND_X]], [[AND_Y]]
 ; CHECK-NEXT:    br i1 [[AND_COND]], label [[IF_ELSE:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[REM:%.*]] = srem i8 [[X]], [[Y]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[REM]], [[X]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[X]], [[X]]
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.then:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %x.cmp = icmp slt i8 %x, 10
   %x.cmp2 = icmp sgt i8 %x, -10
   %and.x = and i1 %x.cmp, %x.cmp2

 ; CHECK-NEXT:    [[X_CMP2:%.*]] = icmp sgt i8 [[X]], -10
 ; CHECK-NEXT:    [[AND_X:%.*]] = and i1 [[X_CMP]], [[X_CMP2]]
 ; CHECK-NEXT:    [[Y_CMP:%.*]] = icmp sge i8 [[Y:%.*]], -20
 ; CHECK-NEXT:    [[Y_CMP2:%.*]] = icmp sle i8 [[Y]], -11
 ; CHECK-NEXT:    [[AND_Y:%.*]] = and i1 [[Y_CMP]], [[Y_CMP2]]
 ; CHECK-NEXT:    [[AND_COND:%.*]] = and i1 [[AND_X]], [[AND_Y]]
 ; CHECK-NEXT:    br i1 [[AND_COND]], label [[IF_ELSE:%.*]], label [[IF_THEN:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[REM:%.*]] = srem i8 [[X]], [[Y]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[REM]], [[X]]
+; CHECK-NEXT:    [[X_NEG:%.*]] = sub i8 0, [[X]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[X_NEG]], [[X]]
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.then:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %x.cmp = icmp slt i8 %x, 10
   %x.cmp2 = icmp sgt i8 %x, -10
   %and.x = and i1 %x.cmp, %x.cmp2