[InstCombine] ((A + B) + C) + A --> (A << 1) + (B + C)

[Chenbing.Zheng]

Summary

This patch deal with 3 add sequences, which include the same op
in firse add and third add:
((A + B) + C) + A --> (A << 1) + (B + C)
((A + B) + C) + B --> (B << 1) + (A + C)

[RKSimon]

What's the motiviation for this patch? I notice we already get the shift+add pattern: https://clang.godbolt.org/z/58c6e9jbj

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1356

Slightly tidier to minimise CreateAdd calls?

Value *ADD = Builder.CreateAdd(RHS == A ? B : A, C, "reass.add")

[Chenbing.Zheng]

In D125198#3499998, @RKSimon wrote:

What's the motiviation for this patch? I notice we already get the shift+add pattern: https://clang.godbolt.org/z/58c6e9jbj

I just notice the 'todo' left in add.ll. According to what you describe, we already have pattern to implement it, so I will abandant this patch.

[spatel]

In D125198#3500072, @Chenbing.Zheng wrote:

In D125198#3499998, @RKSimon wrote:

What's the motiviation for this patch? I notice we already get the shift+add pattern: https://clang.godbolt.org/z/58c6e9jbj

I just notice the 'todo' left in add.ll. According to what you describe, we already have pattern to implement it, so I will abandant this patch.

This is another example where -reassociate can handle the problem more generally. It recognizes the common operand and forms a multiply. If we do not have a real benchmark or application that shows a problem for this kind of pattern, then it would be fine to replace that "TODO" comment with an explanation like:

; "-reassociate" can optimize this even if "-instcombine" does not.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombinerImpl::visitAdd(BinaryOperator &I) {
   if (match(LHS, m_OneUse(m_c_Add(m_Value(A), m_Specific(RHS)))))
     return BinaryOperator::CreateAdd(A, Builder.CreateShl(RHS, 1, "reass.add"));
 
   // LHS + (A + LHS) --> A + (LHS << 1)
   if (match(RHS, m_OneUse(m_c_Add(m_Value(A), m_Specific(LHS)))))
     return BinaryOperator::CreateAdd(A, Builder.CreateShl(LHS, 1, "reass.add"));
 
   {
+    // ((A + B) + C) + A --> (A << 1) + (B + C)
+    // ((A + B) + C) + B --> (B << 1) + (A + C)
+    Value *A, *B, *C;
+    if (match(LHS, m_OneUse(m_c_Add(m_OneUse(m_c_Add(m_Value(A), m_Value(B))),
+                                    m_Value(C))))) {
+      if (RHS == A || RHS == B) {
+        Value *SHL = Builder.CreateShl(RHS, 1, "reass.add");
+        Value *ADD = RHS == A ? Builder.CreateAdd(B, C, "reass.add")
+                              : Builder.CreateAdd(A, C, "reass.add");
+        return BinaryOperator::CreateAdd(SHL, ADD);
+      }
+    }
+  }
+
+  {
     // (A + C1) + (C2 - B) --> (A - B) + (C1 + C2)
     Constant *C1, *C2;
     if (match(&I, m_c_Add(m_Add(m_Value(A), m_ImmConstant(C1)),
                           m_Sub(m_ImmConstant(C2), m_Value(B)))) &&
         (LHS->hasOneUse() || RHS->hasOneUse())) {
       Value *Sub = Builder.CreateSub(A, B);
       return BinaryOperator::CreateAdd(Sub, ConstantExpr::getAdd(C1, C2));
     }

llvm/test/Transforms/InstCombine/add.ll

 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a = add i8 %y, %x
   call void @use(i8 %a)
   %r = add i8 %a, %x
   ret i8 %r
 }
 
-;; TODO: shl A, 1?
 define i32 @test13(i32 %A, i32 %B, i32 %C) {
 ; CHECK-LABEL: @test13(
-; CHECK-NEXT:    [[D_OK:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[E_OK:%.*]] = add i32 [[D_OK]], [[C:%.*]]
-; CHECK-NEXT:    [[F:%.*]] = add i32 [[E_OK]], [[A]]
+; CHECK-NEXT:    [[REASS_ADD:%.*]] = shl i32 [[A:%.*]], 1
+; CHECK-NEXT:    [[REASS_ADD1:%.*]] = add i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[F:%.*]] = add i32 [[REASS_ADD]], [[REASS_ADD1]]
 ; CHECK-NEXT:    ret i32 [[F]]
 ;
   %D_OK = add i32 %A, %B
   %E_OK = add i32 %D_OK, %C
   %F = add i32 %E_OK, %A
   ret i32 %F
 }
 
;
   %and = and i8 %x, %y
   call void @use(i8 %and)
   %xor = xor i8 %and, %y
   call void @use(i8 %xor)
   %add = add i8 %xor, %x
   ret i8 %add
 }
 
-define i32 @add_add_add(i32 %A, i32 %B, i32 %C, i32 %D) {
+define i32 @add_add_add(i32 %A, i32 %B, i32 %C) {
 ; CHECK-LABEL: @add_add_add(
-; CHECK-NEXT:    [[E:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[F:%.*]] = add i32 [[E]], [[C:%.*]]
-; CHECK-NEXT:    [[G:%.*]] = add i32 [[F]], [[D:%.*]]
+; CHECK-NEXT:    [[REASS_ADD:%.*]] = shl i32 [[B:%.*]], 1
+; CHECK-NEXT:    [[REASS_ADD1:%.*]] = add i32 [[A:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[G:%.*]] = add i32 [[REASS_ADD]], [[REASS_ADD1]]
 ; CHECK-NEXT:    ret i32 [[G]]
 ;
   %E = add i32 %A, %B
   %F = add i32 %E, %C
-  %G = add i32 %F, %D
+  %G = add i32 %F, %B
   ret i32 %G
 }
 
-define i32 @add_add_add_commute1(i32 %A, i32 %B, i32 %C, i32 %D) {
+define i32 @add_add_add_commute1(i32 %A, i32 %B, i32 %C) {
 ; CHECK-LABEL: @add_add_add_commute1(
-; CHECK-NEXT:    [[E:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[F:%.*]] = add i32 [[E]], [[C:%.*]]
-; CHECK-NEXT:    [[G:%.*]] = add i32 [[F]], [[D:%.*]]
+; CHECK-NEXT:    [[REASS_ADD:%.*]] = shl i32 [[B:%.*]], 1
+; CHECK-NEXT:    [[REASS_ADD1:%.*]] = add i32 [[A:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[G:%.*]] = add i32 [[REASS_ADD]], [[REASS_ADD1]]
 ; CHECK-NEXT:    ret i32 [[G]]
 ;
   %E = add i32 %B, %A
   %F = add i32 %E, %C
-  %G = add i32 %F, %D
+  %G = add i32 %B, %F
   ret i32 %G
 }
 
-define i32 @add_add_add_commute2(i32 %A, i32 %B, i32 %C, i32 %D) {
+define i32 @add_add_add_commute2(i32 %A, i32 %B, i32 %C) {
 ; CHECK-LABEL: @add_add_add_commute2(
-; CHECK-NEXT:    [[E:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[F:%.*]] = add i32 [[E]], [[C:%.*]]
-; CHECK-NEXT:    [[G:%.*]] = add i32 [[F]], [[D:%.*]]
+; CHECK-NEXT:    [[REASS_ADD:%.*]] = shl i32 [[A:%.*]], 1
+; CHECK-NEXT:    [[REASS_ADD1:%.*]] = add i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[G:%.*]] = add i32 [[REASS_ADD]], [[REASS_ADD1]]
 ; CHECK-NEXT:    ret i32 [[G]]
 ;
   %E = add i32 %B, %A
   %F = add i32 %C, %E
-  %G = add i32 %F, %D
-  ret i32 %G
-}
-
-define i32 @add_add_add_commute3(i32 %A, i32 %B, i32 %C, i32 %D) {
-; CHECK-LABEL: @add_add_add_commute3(
-; CHECK-NEXT:    [[E:%.*]] = add i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[F:%.*]] = add i32 [[E]], [[C:%.*]]
-; CHECK-NEXT:    [[G:%.*]] = add i32 [[F]], [[D:%.*]]
-; CHECK-NEXT:    ret i32 [[G]]
-;
-  %E = add i32 %B, %A
-  %F = add i32 %C, %E
-  %G = add i32 %D, %F
+  %G = add i32 %A, %F
   ret i32 %G
 }