[CVP] Eliminate urem when LHS < RHS

[caojoshua]

Summary

Fixes https://github.com/llvm/llvm-project/issues/58408

X % Y -> X when X < Y

[caojoshua]

Most arithmetic optimizations that use ConstantRange data defer logic to
ConstantRange::binaryOp. ConstantRange::binaryOp can determine that
[0, 12) % [13, ...) -> [0, 12). If X is the LHS, the urem is just X, but
ConstantRange::binaryOp does not know that.

We can do this in either SCCP or CVP. I don't think we can do this in InstCombine or InstSimplify because they don't have ConstantRange data.

[caojoshua]

Check for vector type

[caojoshua]

ping

[nikic]

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

773

Already checked in processUDivOrURem.

780

I'd suggest writing this as CR1.icmp(ICmpInst::ICMP_ULT, CR2).

790

Already checked in processUDivOrURem

[caojoshua]

Change redundant ifs into asserts. Change constant range check to use CR1.icmp(icmp_ult, CR2).

[nikic]

llvm/test/Transforms/CorrelatedValuePropagation/urem.ll

157

Rerun update_test_checks.py please. It looks like you either manually wrote these or edited them.

[caojoshua]

update test with update_test_checks.py

[nikic]

LG

[caojoshua]

Can I get help merging this? I'm not a committer. I have the patch in https://github.com/caojoshua/llvm-project/commit/cac29ca43207f316e2b0904bee45d778d903a76e

llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
     if (BinOp->getOpcode() == Instruction::SDiv)
       BinOp->setIsExact(Instr->isExact());
 
   Instr->replaceAllUsesWith(Sext);
   Instr->eraseFromParent();
   return true;
 }
 
+static bool processURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
+  assert(Instr->getOpcode() == Instruction::URem);
+  // X % Y -> X for X < Y
+  if (LVI->getConstantRange(Instr->getOperand(0), Instr)
+          .getUnsignedMax()
+          .ult(LVI->getConstantRange(Instr->getOperand(1), Instr)
+                   .getUnsignedMin())) {
+    Instr->replaceAllUsesWith(Instr->getOperand(0));
+    Instr->eraseFromParent();
+    return true;
+  }
+  return false;
+}
+
 /// Try to shrink a udiv/urem's width down to the smallest power of two that's
 /// sufficient to contain its operands.
-static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
+static bool narrowUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
   assert(Instr->getOpcode() == Instruction::UDiv ||
          Instr->getOpcode() == Instruction::URem);
   if (Instr->getType()->isVectorTy())
     return false;
 
   // Find the smallest power of two bitwidth that's sufficient to hold Instr's
   // operands.
 
   // What is the smallest bit width that can accommodate the entire value ranges
   // of both of the operands?
   unsigned MaxActiveBits = 0;
if (auto *BinOp = dyn_cast<BinaryOperator>(BO))
     if (BinOp->getOpcode() == Instruction::UDiv)
       BinOp->setIsExact(Instr->isExact());
 
   Instr->replaceAllUsesWith(Zext);
   Instr->eraseFromParent();
   return true;
 }
 
+static bool processUDivOrURem(BinaryOperator *Instr, LazyValueInfo *LVI) {
+  assert(Instr->getOpcode() == Instruction::UDiv ||
+         Instr->getOpcode() == Instruction::URem);
+  if (Instr->getType()->isVectorTy())
+    return false;
+
+  if (Instr->getOpcode() == Instruction::URem && processURem(Instr, LVI))
+    return true;
+
+  return narrowUDivOrURem(Instr, LVI);
+}
+
 static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
   assert(SDI->getOpcode() == Instruction::SRem);
   if (SDI->getType()->isVectorTy())
     return false;
 
   struct Operand {
     Value *V;
     Domain D;

llvm/test/Transforms/CorrelatedValuePropagation/urem.ll

 bb:
   %div = srem i32 %n, 100
   br label %exit
 
 exit:
   ret void
 }
 
+declare void @llvm.assume(i1)
+
+define i16 @test7(i16 %x, i16 %y) {
+; CHECK-LABEL: @test7(
+; CHECK: ret i16 %x
+;
+  %above_range = icmp uge i16 %y, 13
+  call void @llvm.assume(i1 %above_range)
+
+  %below_range = icmp ult i16 %x, 13
+  call void @llvm.assume(i1 %below_range)
+
+  %r = urem i16 %x, %y
+  ret i16 %r
+}
+
 define void @non_power_of_2(i24 %n) {
 ; CHECK-LABEL: @non_power_of_2(
 ; CHECK-NEXT:    [[DIV:%.*]] = urem i24 [[N:%.*]], 42
 ; CHECK-NEXT:    ret void
 ;
   %div = urem i24 %n, 42
   ret void
 }