[InstCombine] Add A - B + B << 1 --> A + B

[rtaylor]

Summary

Add instcombine transform A - B + B << 1 --> A + B

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1396

This can be make dramatically more generic:
https://alive2.llvm.org/ce/z/6aKx_e
https://alive2.llvm.org/ce/z/GqhncR

Something along the following lines:

  auto ScaleConst = [&](std::optional<unsigned> Opc,
                        const APInt *C) -> std::optional<APInt> {
    if (!Opc)
      return APInt::getZero(BitWidth);
    if (Opc == Instruction::Mul)
      return *C;
    if (Opc == Instruction::Shl)
      return APInt::getOne(BitWidth).shl(*C);
    return std::nullopt;
  };
// A - B case
// Todo: A + B case.
if(match(m_Sub(m_Value(A), m_Value(B1))) &&
   match(m_c_Add(m_Specific(A), m_Value(B2))) {
    std::optional<APInt> C1, C2;
    std::optional<unsigned> Opc1, Opc2;
    Value * Mul1, *Mul2;
    if (match(B1, m_c_BinOp(Opc1, m_Value(D), m_APInt(MatchC1))) &&
        match(B2, m_c_BinOp(Opc2, m_Specific(D), m_APInt(MatchC2)))) {
      C1 = ScaleConst(Opc1, MatchC1);
      C2 = ScaleConst(Opc2, MatchC2);
    } else if (match(B1, m_c_BinOp(Opc1, m_Specific(B2), m_APInt(MatchC1)))) {
      C1 = ScaleConst(Opc1, MatchC1);
      C2 = ScaleConst(Opc2, MatchC2);
      D = B2;
    } else if (match(B2, m_c_BinOp(Opc2, m_Specific(B1), m_APInt(MatchC2)))) {
      C1 = ScaleConst(Opc1, MatchC1);
      C2 = ScaleConst(Opc2, MatchC2);
      D = B1;
    }

    // Result if Add(A, (C2 - C1) * D
   }

llvm/test/Transforms/InstCombine/add.ll

2945

Can you split the creation of new tests to a new patch (w.o the new instcombe logic) so we can see the dif generated.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

 //===- InstCombineAddSub.cpp ------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
Instruction *InstCombinerImpl::visitAdd(BinaryOperator &I) {
   if (LHS == RHS) {
     auto *Shl = BinaryOperator::CreateShl(LHS, ConstantInt::get(Ty, 1));
     Shl->setHasNoSignedWrap(I.hasNoSignedWrap());
     Shl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
     return Shl;
   }
 
   Value *A, *B;
+
+  // A - B + B << 1 -> A + B
+  if (match(LHS, m_Sub(m_Value(A), m_Value(B))) &&
+      match(RHS, m_Shl(m_Value(B), m_One())) &&
+      LHS->hasOneUse() && RHS->hasOneUse())
+    return BinaryOperator::CreateAdd(A, B);
+
   if (match(LHS, m_Neg(m_Value(A)))) {
     // -A + -B --> -(A + B)
     if (match(RHS, m_Neg(m_Value(B))))
       return BinaryOperator::CreateNeg(Builder.CreateAdd(A, B));
 
     // -A + B --> B - A
     return BinaryOperator::CreateSub(RHS, A);
   }

llvm/test/Transforms/InstCombine/add.ll

 ; CHECK-NEXT:    ret <2 x i32> [[C]]
 ;
   %o = or <2 x i8> %x, <i8 8, i8 8>
   %a = add <2 x i8> %o, <i8 -1, i8 -1>
   %b = zext <2 x i8> %a to <2 x i32>
   %c = add <2 x i32> %b, <i32 1, i32 poison>
   ret <2 x i32> %c
 }
 
+define i32 @add_shl_sub(i32 %a, i32 %b) {
+; CHECK-LABEL: @add_shl_sub
+; CHECK-NEXT: %add = add i32 %a, %b
+; CHECK-NEXT: ret i32 %add
+  %sub = sub i32 %a, %b
+  %mul = shl nsw i32 %b, 1
+  %add = add nsw i32 %sub, %mul
+  ret i32 %add
+}
+
 declare void @llvm.assume(i1)