[InstCombine] Transform `(add (shl (neg X), Cnt))` -> `(sub (shl X, Cnt))`

[goldstein.w.n]

Summary

Just a simple instruction save.

Proof: https://alive2.llvm.org/ce/z/Vb484j

[nikic]

We have a general Negator infrastructure, which we could use to fold add X, Y to sub X, -Y if the latter is free. However, given how we currently use it to fold sub X, Y to add X, -Y, actually trying to do that would probably result in many new and exiting infinite combine loops, so I'm happy to take the one-off pattern...

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1167

Can this function be reduced to something along the lines of this?

if (match(I, m_c_Add(m_OneUse(m_Shl(m_OneUse(m_Neg(m_Value(X))), m_Value(Cnt))),
                     m_Value(X))) {
  Value *NewShl = Builder.CreateShl(X, Cnt);
  return BinaryOperator::CreateSub(Other, NewShl);
}

llvm/test/Transforms/InstCombine/add-shift.ll

62–80

This only covers one of the one-use conditions.

[goldstein.w.n]

Simplify logic greatly

[goldstein.w.n]

N/A

[nikic]

LG

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1151

Y -> Cnt to match the name in the implementation.

1162

This is probably small enough to inline now.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

static Instruction *foldToUnsignedSaturatedAdd(BinaryOperator &I) {
   const APInt *C, *NotC;
   if (match(&I, m_Add(m_UMin(m_Value(X), m_APInt(NotC)), m_APInt(C))) &&
       *C == ~*NotC)
     return CallInst::Create(getUAddSat(), { X, ConstantInt::get(Ty, *C) });
 
   return nullptr;
 }
 
+// Transform:
+//  (add A, (shl (neg B), Y))
+//      -> (sub A, (shl B, Y))
+static Instruction *combineAddSubWithShlAddSub(InstCombiner::BuilderTy &Builder,
+                                               const BinaryOperator &I) {
+  Value *A, *B, *Cnt;
+  if (match(&I,
+            m_c_Add(m_OneUse(m_Shl(m_OneUse(m_Neg(m_Value(B))), m_Value(Cnt))),
+                    m_Value(A)))) {
+    Value *NewShl = Builder.CreateShl(B, Cnt);
+    return BinaryOperator::CreateSub(A, NewShl);
+  }
+  return nullptr;
+}
+
 /// Try to reduce signed division by power-of-2 to an arithmetic shift right.
 static Instruction *foldAddToAshr(BinaryOperator &Add) {
   // Division must be by power-of-2, but not the minimum signed value.
   Value *X;
   const APInt *DivC;
   if (!match(Add.getOperand(0), m_SDiv(m_Value(X), m_Power2(DivC))) ||
       DivC->isNegative())
     return nullptr;
 
   // Rounding is done by adding -1 if the dividend (X) is negative and has any
   // low bits set. The canonical pattern for that is an "ugt" compare with SMIN:
   // sext (icmp ugt (X & (DivC - 1)), SMIN)
if (Instruction *X = foldAddWithConstant(I))
     return X;
 
   if (Instruction *X = foldNoWrapAdd(I, Builder))
     return X;
 
   if (Instruction *R = foldBinOpShiftWithShift(I))
     return R;
 
+  if (Instruction *R = combineAddSubWithShlAddSub(Builder, I))
+    return R;
+
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   Type *Ty = I.getType();
   if (Ty->isIntOrIntVectorTy(1))
     return BinaryOperator::CreateXor(LHS, RHS);
 
   // X + X --> X << 1
   if (LHS == RHS) {
     auto *Shl = BinaryOperator::CreateShl(LHS, ConstantInt::get(Ty, 1));

llvm/test/Transforms/InstCombine/add-shift.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 3
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 define i8 @flip_add_of_shift_neg(i8 %v, i8 %sh, i8 %x) {
 ; CHECK-LABEL: define i8 @flip_add_of_shift_neg
 ; CHECK-SAME: (i8 [[V:%.*]], i8 [[SH:%.*]], i8 [[X:%.*]]) {
-; CHECK-NEXT:    [[NV:%.*]] = sub i8 0, [[V]]
-; CHECK-NEXT:    [[SV:%.*]] = shl nuw nsw i8 [[NV]], [[SH]]
-; CHECK-NEXT:    [[R:%.*]] = add i8 [[SV]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[V]], [[SH]]
+; CHECK-NEXT:    [[R:%.*]] = sub i8 [[X]], [[TMP1]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %nv = sub i8 0, %v
   %sv = shl nuw nsw i8 %nv, %sh
   %r = add i8 %sv, %x
   ret i8 %r
 }
 
 define <2 x i8> @flip_add_of_shift_neg_vec(<2 x i8> %v, <2 x i8> %sh, <2 x i8> %xx) {
 ; CHECK-LABEL: define <2 x i8> @flip_add_of_shift_neg_vec
 ; CHECK-SAME: (<2 x i8> [[V:%.*]], <2 x i8> [[SH:%.*]], <2 x i8> [[XX:%.*]]) {
 ; CHECK-NEXT:    [[X:%.*]] = mul <2 x i8> [[XX]], [[XX]]
-; CHECK-NEXT:    [[NV:%.*]] = sub <2 x i8> zeroinitializer, [[V]]
-; CHECK-NEXT:    [[SV:%.*]] = shl <2 x i8> [[NV]], [[SH]]
-; CHECK-NEXT:    [[R:%.*]] = add <2 x i8> [[X]], [[SV]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i8> [[V]], [[SH]]
+; CHECK-NEXT:    [[R:%.*]] = sub <2 x i8> [[X]], [[TMP1]]
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %x = mul <2 x i8> %xx, %xx
   %nv = sub <2 x i8> zeroinitializer, %v
   %sv = shl <2 x i8> %nv, %sh
   %r = add <2 x i8> %x, %sv
   ret <2 x i8> %r
 }

 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %x = mul <2 x i8> %xx, %xx
   %nv = sub <2 x i8> zeroinitializer, %v
   %sv = shl <2 x i8> %nv, %sh
   call void @use.v2i8(<2 x i8> %nv)
   %r = add <2 x i8> %x, %sv
   ret <2 x i8> %r
 }
 
 define <2 x i8> @flip_add_of_shift_neg_vec_fail_multiuse_shift(<2 x i8> %v, <2 x i8> %sh, <2 x i8> %xx) {
 ; CHECK-LABEL: define <2 x i8> @flip_add_of_shift_neg_vec_fail_multiuse_shift
 ; CHECK-SAME: (<2 x i8> [[V:%.*]], <2 x i8> [[SH:%.*]], <2 x i8> [[XX:%.*]]) {
 ; CHECK-NEXT:    [[X:%.*]] = mul <2 x i8> [[XX]], [[XX]]
 ; CHECK-NEXT:    [[NV:%.*]] = sub <2 x i8> zeroinitializer, [[V]]
 ; CHECK-NEXT:    [[SV:%.*]] = shl <2 x i8> [[NV]], [[SH]]
 ; CHECK-NEXT:    call void @use.v2i8(<2 x i8> [[SV]])
 ; CHECK-NEXT:    [[R:%.*]] = add <2 x i8> [[X]], [[SV]]
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %x = mul <2 x i8> %xx, %xx
   %nv = sub <2 x i8> zeroinitializer, %v
   %sv = shl <2 x i8> %nv, %sh
   call void @use.v2i8(<2 x i8> %sv)
   %r = add <2 x i8> %x, %sv
   ret <2 x i8> %r
 }