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