[ValueTracking] recognize sub X, (X % Y) as not overflowing

[spatel]

Summary

I fixed some poison-safety violations on related patterns in InstCombine and noticed that we missed adding nsw/nuw on them, so this adds clauses to the underlying analysis for that.
We need the undef input restriction to make this safe according to Alive2:
https://alive2.llvm.org/ce/z/48g9K8

[nikic]

LGTM

There are a lot more cases we could handle here (at least for the unsigned case) -- in particular a lot of the cases starting at https://github.com/llvm/llvm-project/blob/6d53d35efd3b876d2cc70a776fb168d6debfeba5/llvm/lib/Analysis/InstructionSimplify.cpp#L3023 are relevant. We have quite a few operations (urem, udiv, shr, and) that are non-increasing functions, often of both operands. Though I'm also not sure whether its worthwhile to try particularly hard to infer nuw here.

[spatel]

In D125500#3510991, @nikic wrote:

LGTM

There are a lot more cases we could handle here (at least for the unsigned case) -- in particular a lot of the cases starting at https://github.com/llvm/llvm-project/blob/6d53d35efd3b876d2cc70a776fb168d6debfeba5/llvm/lib/Analysis/InstructionSimplify.cpp#L3023 are relevant. We have quite a few operations (urem, udiv, shr, and) that are non-increasing functions, often of both operands. Though I'm also not sure whether its worthwhile to try particularly hard to infer nuw here.

Yes, we also miss cases where an existing nuw could be used to simplify patterns with those ops:
https://alive2.llvm.org/ce/z/UFHE5_

I'll put a TODO comment in there.

llvm/lib/Analysis/ValueTracking.cpp

 }
 
 OverflowResult llvm::computeOverflowForUnsignedSub(const Value *LHS,
                                                    const Value *RHS,
                                                    const DataLayout &DL,
                                                    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,
             m_Intrinsic<Intrinsic::usub_with_overflow>(m_Value(), m_Value())))
     if (auto C =
             isImpliedByDomCondition(CmpInst::ICMP_UGE, LHS, RHS, CxtI, DL)) {
       if (*C)
         return OverflowResult::NeverOverflows;
       return OverflowResult::AlwaysOverflowsLow;
     }
   ConstantRange LHSRange = computeConstantRangeIncludingKnownBits(
       LHS, /*ForSigned=*/false, DL, /*Depth=*/0, AC, CxtI, DT);
   ConstantRange RHSRange = computeConstantRangeIncludingKnownBits(
       RHS, /*ForSigned=*/false, DL, /*Depth=*/0, AC, CxtI, DT);
   return mapOverflowResult(LHSRange.unsignedSubMayOverflow(RHSRange));
 }
 
 OverflowResult llvm::computeOverflowForSignedSub(const Value *LHS,
                                                  const Value *RHS,
                                                  const DataLayout &DL,
                                                  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 &&
       ComputeNumSignBits(RHS, DL, 0, AC, CxtI, DT) > 1)
     return OverflowResult::NeverOverflows;
 
   ConstantRange LHSRange = computeConstantRangeIncludingKnownBits(
       LHS, /*ForSigned=*/true, DL, /*Depth=*/0, AC, CxtI, DT);

llvm/test/Transforms/InstCombine/add4.ll

;
   ret i64 %t4
 }
 
 define i32 @not_match_overflow(i32 %x) {
 ; CHECK-LABEL: @not_match_overflow(
 ; 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]]
 ;
   %t = urem i32 %x, 299
   %t1 = udiv i32 %x, 299
   %t2 = urem i32 %t1, 147483647
   %t3 = mul i32 %t2, 299
   %t4 = add i32 %t, %t3
   ret i32 %t4
 }

llvm/test/Transforms/InstCombine/exact.ll

;
   %y = sdiv exact <2 x i32> %x, <i32 128, i32 128>
   ret <2 x i32> %y
 }
 
 define i32 @sdiv3(i32 %x) {
 ; 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
   %z = mul i32 %y, 3
   ret i32 %z
 }
 
 define i32 @sdiv4(i32 %x) {

llvm/test/Transforms/InstCombine/rem.ll

;
   %C = sub i8 %B, %x
   ret i8 %C
 }
 
 define i8 @urem3(i8 %x) {
 ; 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]]
 ;
   %A = udiv i8 %x, 3
   %B = mul i8 %A, -3
   %C = sub i8 %x, %B
   ret i8 %C
 }

llvm/test/Transforms/InstCombine/sub.ll

;
   %add = add nsw i32 11, %b
   %sub1 = sub i32 %sub, %add
   ret i32 %sub1
 }
 
 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
   %sub = sub i8 %x, %rem
   ret i8 %sub
 }
 
 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
   %sub = sub <2 x i5> %x, %rem
   ret <2 x i5> %sub
 }