[InstCombine] Transform sub(sext(add(X, Y)), sext(add(X, Z))) to sub(Y, Z) given nsw adds

[dmgreen]

Summary

This adds combines for sext(X +nsw Y) - sext(X +nsw Z) -> sext(Y) - sext(Z) and zext(X +nuw Y) - zext(X +nuw Z) -> zext(Y) - zext(Z). This is especially useful when Y and Z are constants.

See https://alive2.llvm.org/ce/z/XEazaS and https://alive2.llvm.org/ce/z/kHGPtU.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2474

This assumes the common operand is on the LHS. This will be the case for constants, but may not hold for non-constants. We should handle the commuted case as well.

2477

It looks like it's legal to transfer the nsw flag to the sub here (https://alive2.llvm.org/ce/z/cYJh4x). But not in the nuw case (https://alive2.llvm.org/ce/z/jHsEcP).

llvm/test/Transforms/InstCombine/sub-ext-add.ll

4

Drop data layout.

13

Could you please change the variable names to something more meaningful?

92

Please add multi-use tests. I think this fold needs one-use checks.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2477

Okay, I see in the tests that the nsw will get inferred anyway, so I guess there's no need to make it explicit.

[dmgreen]

Thanks for the review. Updated for one use checks and commutivity. This might start to get stranger in a followup but this part should hopefully be sensible enough on it's own.

[nikic]

LGTM

llvm/test/Transforms/InstCombine/sub-ext-add.ll

7–8

This test case looks the same as subaddnuw_c1?

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (I.hasNoUnsignedWrap() || I.hasNoSignedWrap()) {
       Value *Sub =
           Builder.CreateSub(X, Y, "sub", /*HasNUW=*/false, /*HasNSW=*/true);
       Value *Call =
           Builder.CreateBinaryIntrinsic(Intrinsic::abs, Sub, Builder.getTrue());
       return replaceInstUsesWith(I, Call);
     }
   }
 
+  // sext(X + Y) - sext(X + Z) -> sext(Y) - sext(Z)
+  if (match(Op0, m_SExt(m_NSWAdd(m_Value(X), m_Value(Y)))) &&
+      match(Op1, m_SExt(m_NSWAdd(m_Specific(X), m_Value(Z))))) {
+    Value *S1 = Builder.CreateSExt(Y, Ty);
+    Value *S2 = Builder.CreateSExt(Z, Ty);
+    return BinaryOperator::CreateSub(S1, S2);
+  }
+  if (match(Op0, m_ZExt(m_NUWAdd(m_Value(X), m_Value(Y)))) &&
+      match(Op1, m_ZExt(m_NUWAdd(m_Specific(X), m_Value(Z))))) {
+    Value *S1 = Builder.CreateZExt(Y, Ty);
+    Value *S2 = Builder.CreateZExt(Z, Ty);
+    return BinaryOperator::CreateSub(S1, S2);
+  }
+
   if (Instruction *Res = foldBinOpOfSelectAndCastOfSelectCondition(I))
     return Res;
 
   return TryToNarrowDeduceFlags();
 }
 
 /// This eliminates floating-point negation in either 'fneg(X)' or
 /// 'fsub(-0.0, X)' form by combining into a constant operand.

llvm/test/Transforms/InstCombine/sub-ext-add.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 target datalayout = "e-p:64:64:64-p1:16:16:16-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
 
 define i32 @subaddnuw(i8 %a, i8 %C1, i8 %C2) {
 ; CHECK-LABEL: @subaddnuw(
-; CHECK-NEXT:    [[L3619:%.*]] = add nuw i8 [[A:%.*]], [[C1:%.*]]
-; CHECK-NEXT:    [[L3620:%.*]] = zext i8 [[L3619]] to i32
-; CHECK-NEXT:    [[L3621:%.*]] = add nuw i8 [[A]], [[C2:%.*]]
-; CHECK-NEXT:    [[L3622:%.*]] = zext i8 [[L3621]] to i32
-; CHECK-NEXT:    [[L3623:%.*]] = sub nsw i32 [[L3622]], [[L3620]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[C2:%.*]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i8 [[C1:%.*]] to i32
+; CHECK-NEXT:    [[L3623:%.*]] = sub nsw i32 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i32 [[L3623]]
 ;
   %l3619 = add nuw i8 %a, %C1
   %l3620 = zext i8 %l3619 to i32
   %l3621 = add nuw i8 %a, %C2
   %l3622 = zext i8 %l3621 to i32
   %l3623 = sub i32 %l3622, %l3620
   ret i32 %l3623
 }
 
 define i32 @subaddnuw_c(i8 %a) {
 ; CHECK-LABEL: @subaddnuw_c(
-; CHECK-NEXT:    [[L3619:%.*]] = add nuw i8 [[A:%.*]], 1
-; CHECK-NEXT:    [[L3620:%.*]] = zext i8 [[L3619]] to i32
-; CHECK-NEXT:    [[L3621:%.*]] = add nuw i8 [[A]], 2
-; CHECK-NEXT:    [[L3622:%.*]] = zext i8 [[L3621]] to i32
-; CHECK-NEXT:    [[L3623:%.*]] = sub nsw i32 [[L3622]], [[L3620]]
-; CHECK-NEXT:    ret i32 [[L3623]]
+; CHECK-NEXT:    ret i32 1
 ;
   %l3619 = add nuw i8 %a, 1
   %l3620 = zext i8 %l3619 to i32
   %l3621 = add nuw i8 %a, 2
   %l3622 = zext i8 %l3621 to i32
   %l3623 = sub i32 %l3622, %l3620
   ret i32 %l3623
 }
 
 define i32 @subaddnsw(i8 %a, i8 %C1, i8 %C2) {
 ; CHECK-LABEL: @subaddnsw(
-; CHECK-NEXT:    [[L3619:%.*]] = add nsw i8 [[A:%.*]], [[C1:%.*]]
-; CHECK-NEXT:    [[L3620:%.*]] = sext i8 [[L3619]] to i32
-; CHECK-NEXT:    [[L3621:%.*]] = add nsw i8 [[A]], [[C2:%.*]]
-; CHECK-NEXT:    [[L3622:%.*]] = sext i8 [[L3621]] to i32
-; CHECK-NEXT:    [[L3623:%.*]] = sub nsw i32 [[L3622]], [[L3620]]
+; CHECK-NEXT:    [[TMP1:%.*]] = sext i8 [[C2:%.*]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = sext i8 [[C1:%.*]] to i32
+; CHECK-NEXT:    [[L3623:%.*]] = sub nsw i32 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret i32 [[L3623]]
 ;
   %l3619 = add nsw i8 %a, %C1
   %l3620 = sext i8 %l3619 to i32
   %l3621 = add nsw i8 %a, %C2
   %l3622 = sext i8 %l3621 to i32
   %l3623 = sub i32 %l3622, %l3620
   ret i32 %l3623
 }
 
 define i32 @subaddnsw_c(i8 %a) {
 ; CHECK-LABEL: @subaddnsw_c(
-; CHECK-NEXT:    [[L3619:%.*]] = add nsw i8 [[A:%.*]], 1
-; CHECK-NEXT:    [[L3620:%.*]] = sext i8 [[L3619]] to i32
-; CHECK-NEXT:    [[L3621:%.*]] = add nsw i8 [[A]], 2
-; CHECK-NEXT:    [[L3622:%.*]] = sext i8 [[L3621]] to i32
-; CHECK-NEXT:    [[L3623:%.*]] = sub nsw i32 [[L3622]], [[L3620]]
-; CHECK-NEXT:    ret i32 [[L3623]]
+; CHECK-NEXT:    ret i32 1
 ;
   %l3619 = add nsw i8 %a, 1
   %l3620 = sext i8 %l3619 to i32
   %l3621 = add nsw i8 %a, 2
   %l3622 = sext i8 %l3621 to i32
   %l3623 = sub i32 %l3622, %l3620
   ret i32 %l3623
 }

 ; CHECK-NEXT:    ret i32 [[L3623]]
 ;
   %l3619 = add i8 %a, %C1
   %l3620 = zext i8 %l3619 to i32
   %l3621 = add nuw i8 %a, %C2
   %l3622 = zext i8 %l3621 to i32
   %l3623 = sub i32 %l3622, %l3620
   ret i32 %l3623
 }