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

[spatel]

Summary

This extends a similar pattern from D125500. If we know that operand 1 of a subtract is itself a non-overflowing subtract from operand 0, then the final/outer subtract is also non-overflowing:
https://alive2.llvm.org/ce/z/Bqan8v

InstCombine uses this analysis to trigger a narrowing optimization, so that is what the first changed test shows.

The last test models the motivating case from issue #48013. In that example, we determine 'nsw' on the first sub from the srem, then we determine that the 2nd sub can be narrowed, and that leads to eliminating both subtracts.

This works for unsigned sub too, but I left that out to keep the patch minimal. If this looks ok, I will follow up with that change. There are also several missing subtract narrowing optimizations demonstrated in the tests above the diffs shown here - those should be handled in InstCombine with another set of patches.

[nikic]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

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))
+
+  // X - (X -nsw ?)
+  // In the minimal case, this would simplify to "?", so there's no subtract
+  // at all. But if this analysis is used to peek through casts, for example,
+  // then determining no-overflow may allow other transforms.
+  if (match(RHS, m_SRem(m_Specific(LHS), m_Value())) ||
+      match(RHS, m_NSWSub(m_Specific(LHS), m_Value())))
+    if (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(

llvm/test/Transforms/InstCombine/sub.ll

;
   %zx = zext i8 %x to i32
   %zy = zext i7 %y to i32
   %s = sub nuw i32 %zx, %zy
   ret i32 %s
 }
 
 define i16 @sext_nsw_noundef(i8 noundef %x, i8 %y) {
 ; CHECK-LABEL: @sext_nsw_noundef(
-; CHECK-NEXT:    [[D:%.*]] = sub nsw i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[EX:%.*]] = sext i8 [[X]] to i16
-; CHECK-NEXT:    [[ED:%.*]] = sext i8 [[D]] to i16
-; CHECK-NEXT:    [[Z:%.*]] = sub nsw i16 [[EX]], [[ED]]
+; CHECK-NEXT:    [[Z:%.*]] = sext i8 [[Y:%.*]] to i16
 ; CHECK-NEXT:    ret i16 [[Z]]
 ;
   %d = sub nsw i8 %x, %y
   %ex = sext i8 %x to i16
   %ed = sext i8 %d to i16
   %z = sub i16 %ex, %ed
   ret i16 %z
 }
 
+; negative test - requires noundef
+
 define i16 @sext_nsw(i8 %x, i8 %y) {
 ; CHECK-LABEL: @sext_nsw(
 ; CHECK-NEXT:    [[D:%.*]] = sub nsw i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[EX:%.*]] = sext i8 [[X]] to i16
 ; CHECK-NEXT:    [[ED:%.*]] = sext i8 [[D]] to i16
 ; CHECK-NEXT:    [[Z:%.*]] = sub nsw i16 [[EX]], [[ED]]
 ; CHECK-NEXT:    ret i16 [[Z]]
 ;
   %d = sub nsw i8 %x, %y
   %ex = sext i8 %x to i16
   %ed = sext i8 %d to i16
   %z = sub i16 %ex, %ed
   ret i16 %z
 }
 
+; negative test - requires nsw
+
 define i16 @sext_noundef(i8 noundef %x, i8 %y) {
 ; CHECK-LABEL: @sext_noundef(
 ; CHECK-NEXT:    [[D:%.*]] = sub i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[EX:%.*]] = sext i8 [[X]] to i16
 ; CHECK-NEXT:    [[ED:%.*]] = sext i8 [[D]] to i16
 ; CHECK-NEXT:    [[Z:%.*]] = sub nsw i16 [[EX]], [[ED]]
 ; CHECK-NEXT:    ret i16 [[Z]]
 ;
   %d = sub i8 %x, %y
   %ex = sext i8 %x to i16
   %ed = sext i8 %d to i16
   %z = sub i16 %ex, %ed
   ret i16 %z
 }
 
+; negative test - must have common operand
+
 define i16 @sext_nsw_noundef_wrong_val(i8 noundef %x, i8 noundef %y, i8 noundef %q) {
 ; CHECK-LABEL: @sext_nsw_noundef_wrong_val(
 ; CHECK-NEXT:    [[D:%.*]] = sub nsw i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[EQ:%.*]] = sext i8 [[Q:%.*]] to i16
 ; CHECK-NEXT:    [[ED:%.*]] = sext i8 [[D]] to i16
 ; CHECK-NEXT:    [[Z:%.*]] = sub nsw i16 [[EQ]], [[ED]]
 ; CHECK-NEXT:    ret i16 [[Z]]
 ;
   %d = sub nsw i8 %x, %y
   %eq = sext i8 %q to i16
   %ed = sext i8 %d to i16
   %z = sub i16 %eq, %ed
   ret i16 %z
 }
 
+; two no-wrap analyses combine to allow reduction
+
 define i16 @srem_sext_noundef(i8 noundef %x, i8 %y) {
 ; CHECK-LABEL: @srem_sext_noundef(
 ; CHECK-NEXT:    [[R:%.*]] = srem i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[D:%.*]] = sub nsw i8 [[X]], [[R]]
-; CHECK-NEXT:    [[SD:%.*]] = sext i8 [[D]] to i16
-; CHECK-NEXT:    [[SX:%.*]] = sext i8 [[X]] to i16
-; CHECK-NEXT:    [[Z:%.*]] = sub nsw i16 [[SX]], [[SD]]
+; CHECK-NEXT:    [[Z:%.*]] = sext i8 [[R]] to i16
 ; CHECK-NEXT:    ret i16 [[Z]]
 ;
   %r = srem i8 %x, %y
   %d = sub i8 %x, %r
   %sd = sext i8 %d to i16
   %sx = sext i8 %x to i16
   %z = sub i16 %sx, %sd
   ret i16 %z
 }