diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -4841,6 +4841,15 @@
                                                    AssumptionCache *AC,
                                                    const Instruction *CxtI,
                                                    const DominatorTree *DT) {
+  // X - (X % ?)
+  // The remainder of a value can't have greater magnitude than itself,
+  // so the subtraction can't overflow.
+  // TODO: There are other patterns like this.
+  //       See simplifyICmpWithBinOpOnLHS() for candidates.
+  if (match(RHS, m_URem(m_Specific(LHS), m_Value())) &&
+      isGuaranteedNotToBeUndefOrPoison(LHS, AC, CxtI, DT))
+    return OverflowResult::NeverOverflows;
+
   // Checking for conditions implied by dominating conditions may be expensive.
   // Limit it to usub_with_overflow calls for now.
   if (match(CxtI,
@@ -4864,6 +4873,13 @@
                                                  AssumptionCache *AC,
                                                  const Instruction *CxtI,
                                                  const DominatorTree *DT) {
+  // X - (X % ?)
+  // The remainder of a value can't have greater magnitude than itself,
+  // so the subtraction can't overflow.
+  if (match(RHS, m_SRem(m_Specific(LHS), m_Value())) &&
+      isGuaranteedNotToBeUndefOrPoison(LHS, AC, CxtI, DT))
+    return OverflowResult::NeverOverflows;
+
   // If LHS and RHS each have at least two sign bits, the subtraction
   // cannot overflow.
   if (ComputeNumSignBits(LHS, DL, 0, AC, CxtI, DT) > 1 &&
diff --git a/llvm/test/Transforms/InstCombine/add4.ll b/llvm/test/Transforms/InstCombine/add4.ll
--- a/llvm/test/Transforms/InstCombine/add4.ll
+++ b/llvm/test/Transforms/InstCombine/add4.ll
@@ -116,7 +116,7 @@
 ; CHECK-NEXT:    [[X_FR:%.*]] = freeze i32 [[X:%.*]]
 ; CHECK-NEXT:    [[T:%.*]] = urem i32 [[X_FR]], 299
 ; CHECK-NEXT:    [[TMP1:%.*]] = urem i32 [[X_FR]], 299
-; CHECK-NEXT:    [[T3:%.*]] = sub i32 [[X_FR]], [[TMP1]]
+; CHECK-NEXT:    [[T3:%.*]] = sub nuw i32 [[X_FR]], [[TMP1]]
 ; CHECK-NEXT:    [[T4:%.*]] = add i32 [[T]], [[T3]]
 ; CHECK-NEXT:    ret i32 [[T4]]
 ;
diff --git a/llvm/test/Transforms/InstCombine/exact.ll b/llvm/test/Transforms/InstCombine/exact.ll
--- a/llvm/test/Transforms/InstCombine/exact.ll
+++ b/llvm/test/Transforms/InstCombine/exact.ll
@@ -32,7 +32,7 @@
 ; CHECK-LABEL: @sdiv3(
 ; CHECK-NEXT:    [[X_FR:%.*]] = freeze i32 [[X:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = srem i32 [[X_FR]], 3
-; CHECK-NEXT:    [[Z:%.*]] = sub i32 [[X_FR]], [[TMP1]]
+; CHECK-NEXT:    [[Z:%.*]] = sub nsw i32 [[X_FR]], [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %y = sdiv i32 %x, 3
diff --git a/llvm/test/Transforms/InstCombine/rem.ll b/llvm/test/Transforms/InstCombine/rem.ll
--- a/llvm/test/Transforms/InstCombine/rem.ll
+++ b/llvm/test/Transforms/InstCombine/rem.ll
@@ -139,7 +139,7 @@
 ; CHECK-LABEL: @urem3(
 ; CHECK-NEXT:    [[X_FR:%.*]] = freeze i8 [[X:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = urem i8 [[X_FR]], 3
-; CHECK-NEXT:    [[B_NEG:%.*]] = sub i8 [[X_FR]], [[TMP1]]
+; CHECK-NEXT:    [[B_NEG:%.*]] = sub nuw i8 [[X_FR]], [[TMP1]]
 ; CHECK-NEXT:    [[C:%.*]] = add i8 [[B_NEG]], [[X_FR]]
 ; CHECK-NEXT:    ret i8 [[C]]
 ;
diff --git a/llvm/test/Transforms/InstCombine/sub.ll b/llvm/test/Transforms/InstCombine/sub.ll
--- a/llvm/test/Transforms/InstCombine/sub.ll
+++ b/llvm/test/Transforms/InstCombine/sub.ll
@@ -1705,7 +1705,7 @@
 define i8 @sub_srem(i8 noundef %x, i8 %y) {
 ; CHECK-LABEL: @sub_srem(
 ; CHECK-NEXT:    [[REM:%.*]] = srem i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[X]], [[REM]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i8 [[X]], [[REM]]
 ; CHECK-NEXT:    ret i8 [[SUB]]
 ;
   %rem = srem i8 %x, %y
@@ -1716,7 +1716,7 @@
 define <2 x i5> @sub_urem(<2 x i5> noundef %x, <2 x i5> %y) {
 ; CHECK-LABEL: @sub_urem(
 ; CHECK-NEXT:    [[REM:%.*]] = urem <2 x i5> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub <2 x i5> [[X]], [[REM]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub nuw <2 x i5> [[X]], [[REM]]
 ; CHECK-NEXT:    ret <2 x i5> [[SUB]]
 ;
   %rem = urem <2 x i5> %x, %y