Index: llvm/lib/Transforms/Scalar/SCCP.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/SCCP.cpp
+++ llvm/lib/Transforms/Scalar/SCCP.cpp
@@ -154,6 +154,53 @@
   return true;
 }
 
+/// Try to replace signed instructions with their unsigned equivalent.
+static bool replaceSignedInst(SCCPSolver &Solver,
+                              SmallPtrSetImpl<Value *> &InsertedValues,
+                              Instruction &Inst) {
+  // Determine if a signed value is known to be >= 0.
+  auto isNonNegative = [&Solver](Value *V) {
+    const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
+    return IV.isConstantRange(/*UndefAllowed=*/false) &&
+           IV.getConstantRange().isAllNonNegative();
+  };
+
+  Instruction *NewInst = nullptr;
+  switch (Inst.getOpcode()) {
+  case Instruction::SExt: {
+    // If the source value is not negative, this is a zext.
+    Value *Op0 = Inst.getOperand(0);
+    if (isa<Constant>(Op0) || InsertedValues.count(Op0) || !isNonNegative(Op0))
+      return false;
+    NewInst = new ZExtInst(Op0, Inst.getType(), "", &Inst);
+    break;
+  }
+  case Instruction::SDiv:
+  case Instruction::SRem: {
+    // If both operands are not negative, this is the same as udiv/urem.
+    Value *Op0 = Inst.getOperand(0), *Op1 = Inst.getOperand(1);
+    if (InsertedValues.count(Op0) || InsertedValues.count(Op1) ||
+        !isNonNegative(Op0) || !isNonNegative(Op1))
+      return false;
+    auto NewOpcode = Inst.getOpcode() == Instruction::SDiv ? Instruction::UDiv
+                                                           : Instruction::URem;
+    NewInst = BinaryOperator::Create(NewOpcode, Op0, Op1, "", &Inst);
+    break;
+  }
+  default:
+    return false;
+  }
+
+  // Wire up the new instruction and update state.
+  assert(NewInst && "Expected replacement instruction");
+  NewInst->takeName(&Inst);
+  InsertedValues.insert(NewInst);
+  Inst.replaceAllUsesWith(NewInst);
+  Solver.removeLatticeValueFor(&Inst);
+  Inst.eraseFromParent();
+  return true;
+}
+
 static bool simplifyInstsInBlock(SCCPSolver &Solver, BasicBlock &BB,
                                  SmallPtrSetImpl<Value *> &InsertedValues,
                                  Statistic &InstRemovedStat,
@@ -168,23 +215,9 @@
 
       MadeChanges = true;
       ++InstRemovedStat;
-    } else if (isa<SExtInst>(&Inst)) {
-      Value *ExtOp = Inst.getOperand(0);
-      if (isa<Constant>(ExtOp) || InsertedValues.count(ExtOp))
-        continue;
-      const ValueLatticeElement &IV = Solver.getLatticeValueFor(ExtOp);
-      if (!IV.isConstantRange(/*UndefAllowed=*/false))
-        continue;
-      if (IV.getConstantRange().isAllNonNegative()) {
-        auto *ZExt = new ZExtInst(ExtOp, Inst.getType(), "", &Inst);
-        ZExt->takeName(&Inst);
-        InsertedValues.insert(ZExt);
-        Inst.replaceAllUsesWith(ZExt);
-        Solver.removeLatticeValueFor(&Inst);
-        Inst.eraseFromParent();
-        InstReplacedStat++;
-        MadeChanges = true;
-      }
+    } else if (replaceSignedInst(Solver, InsertedValues, Inst)) {
+      MadeChanges = true;
+      ++InstReplacedStat;
     }
   }
   return MadeChanges;
Index: llvm/test/Transforms/PhaseOrdering/srem.ll
===================================================================
--- llvm/test/Transforms/PhaseOrdering/srem.ll
+++ llvm/test/Transforms/PhaseOrdering/srem.ll
@@ -3,13 +3,16 @@
 ; RUN: opt -O2 -S < %s | FileCheck %s
 ; RUN: opt -O3 -S < %s | FileCheck %s
 
+; srem should be folded based on branch conditions
+; This can be done by IPSCCP or CVP.
+
 define i32 @PR57472(i32 noundef %x) {
 ; CHECK-LABEL: @PR57472(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[X]], 16
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[REM]], i32 42
-; CHECK-NEXT:    ret i32 [[COND]]
+; CHECK-NEXT:    [[REM:%.*]] = and i32 [[X]], 15
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[CMP]], i32 [[REM]], i32 42
+; CHECK-NEXT:    ret i32 [[SPEC_SELECT]]
 ;
 entry:
   %x.addr = alloca i32, align 4
Index: llvm/test/Transforms/SCCP/binaryops-range-special-cases.ll
===================================================================
--- llvm/test/Transforms/SCCP/binaryops-range-special-cases.ll
+++ llvm/test/Transforms/SCCP/binaryops-range-special-cases.ll
@@ -130,7 +130,7 @@
 ; 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:    [[SREM_3:%.*]] = urem 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
Index: llvm/test/Transforms/SCCP/divrem.ll
===================================================================
--- llvm/test/Transforms/SCCP/divrem.ll
+++ llvm/test/Transforms/SCCP/divrem.ll
@@ -5,7 +5,7 @@
 ; CHECK-LABEL: @sdiv_nonneg0_nonneg1(
 ; CHECK-NEXT:    [[PX:%.*]] = and i8 [[X:%.*]], 127
 ; CHECK-NEXT:    [[PY:%.*]] = lshr i8 [[Y:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = sdiv i8 [[PX]], [[PY]]
+; CHECK-NEXT:    [[R:%.*]] = udiv i8 [[PX]], [[PY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %px = and i8 %x, 127
@@ -17,7 +17,7 @@
 define i8 @sdiv_nonnegconst0_nonneg1(i7 %y) {
 ; CHECK-LABEL: @sdiv_nonnegconst0_nonneg1(
 ; CHECK-NEXT:    [[PY:%.*]] = zext i7 [[Y:%.*]] to i8
-; CHECK-NEXT:    [[R:%.*]] = sdiv i8 42, [[PY]]
+; CHECK-NEXT:    [[R:%.*]] = udiv i8 42, [[PY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %py = zext i7 %y to i8
@@ -25,6 +25,8 @@
   ret i8 %r
 }
 
+; TODO: This can be converted to udiv.
+
 define i8 @sdiv_nonneg0_nonnegconst1(i8 %x) {
 ; CHECK-LABEL: @sdiv_nonneg0_nonnegconst1(
 ; CHECK-NEXT:    [[PX:%.*]] = mul nsw i8 [[X:%.*]], [[X]]
@@ -36,6 +38,8 @@
   ret i8 %r
 }
 
+; negative test
+
 define i8 @sdiv_unknown0_nonneg1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @sdiv_unknown0_nonneg1(
 ; CHECK-NEXT:    [[PY:%.*]] = lshr i8 [[Y:%.*]], 1
@@ -47,6 +51,8 @@
   ret i8 %r
 }
 
+; negative test
+
 define i8 @sdiv_nonnegconst0_unknown1(i7 %y) {
 ; CHECK-LABEL: @sdiv_nonnegconst0_unknown1(
 ; CHECK-NEXT:    [[SY:%.*]] = sext i7 [[Y:%.*]] to i8
@@ -58,6 +64,8 @@
   ret i8 %r
 }
 
+; negative test
+
 define i8 @sdiv_unknown0_nonnegconst1(i8 %x) {
 ; CHECK-LABEL: @sdiv_unknown0_nonnegconst1(
 ; CHECK-NEXT:    [[SX:%.*]] = mul i8 [[X:%.*]], [[X]]
@@ -73,7 +81,7 @@
 ; CHECK-LABEL: @srem_nonneg0_nonneg1(
 ; CHECK-NEXT:    [[PX:%.*]] = and i8 [[X:%.*]], 127
 ; CHECK-NEXT:    [[PY:%.*]] = lshr i8 [[Y:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = srem i8 [[PX]], [[PY]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[PX]], [[PY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %px = and i8 %x, 127
@@ -85,7 +93,7 @@
 define i8 @srem_nonnegconst0_nonneg1(i8 %y) {
 ; CHECK-LABEL: @srem_nonnegconst0_nonneg1(
 ; CHECK-NEXT:    [[PY:%.*]] = and i8 [[Y:%.*]], 127
-; CHECK-NEXT:    [[R:%.*]] = srem i8 42, [[PY]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 42, [[PY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %py = and i8 %y, 127
@@ -96,7 +104,7 @@
 define i8 @srem_nonneg0_nonnegconst1(i7 %x) {
 ; CHECK-LABEL: @srem_nonneg0_nonnegconst1(
 ; CHECK-NEXT:    [[PX:%.*]] = zext i7 [[X:%.*]] to i8
-; CHECK-NEXT:    [[R:%.*]] = srem i8 [[PX]], 42
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[PX]], 42
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %px = zext i7 %x to i8
@@ -104,6 +112,8 @@
   ret i8 %r
 }
 
+; negative test
+
 define i8 @srem_unknown0_nonneg1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @srem_unknown0_nonneg1(
 ; CHECK-NEXT:    [[PY:%.*]] = lshr i8 [[Y:%.*]], 1
@@ -115,6 +125,8 @@
   ret i8 %r
 }
 
+; negative test
+
 define i8 @srem_nonnegconst0_unknown1(i7 %y) {
 ; CHECK-LABEL: @srem_nonnegconst0_unknown1(
 ; CHECK-NEXT:    [[SY:%.*]] = sext i7 [[Y:%.*]] to i8
@@ -126,6 +138,8 @@
   ret i8 %r
 }
 
+; negative test
+
 define i8 @srem_unknown0_nonnegconst1(i8 %x) {
 ; CHECK-LABEL: @srem_unknown0_nonnegconst1(
 ; CHECK-NEXT:    [[SX:%.*]] = mul i8 [[X:%.*]], [[X]]
@@ -137,13 +151,15 @@
   ret i8 %r
 }
 
+; x is known non-negative in t block
+
 define i32 @PR57472(i32 %x) {
 ; CHECK-LABEL: @PR57472(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       t:
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[X]], 16
+; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[X]], 16
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       f:
 ; CHECK-NEXT:    br label [[EXIT]]
@@ -167,6 +183,8 @@
   ret i32 %cond
 }
 
+; x is known non-negative in f block
+
 define i32 @PR57472_alt(i32 %x) {
 ; CHECK-LABEL: @PR57472_alt(
 ; CHECK-NEXT:  entry:
@@ -175,7 +193,7 @@
 ; CHECK:       t:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       f:
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 16, [[X]]
+; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 16, [[X]]
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ -42, [[T]] ], [ [[DIV]], [[F]] ]