[InstCombine] Change InstCombineAddSub to not perform constant folding when there is an intermediate use of the source register.

[dancgr]

Summary

The add/sub with constant folding does not provide substantial gains when there is an intermediate use of the initial result, resulting in the same number of instructions.

Also, this behaviour can interfere with other optimizations which sometimes can result in an extra instruction.

%a = load i32 ...
%b = load i32 ...

%1 = sub %a, 10
%2 = store %1
%3 = sub 0, %1
%4 = add %b, %3

-> The statement (%3 = sub 0, %1) will get folded as follows:

%1 = sub %a, 10
%2 = store %1
%3 = sub 0, %1 => %3 = sub 10, %a
%4 = add %b, %3

-> Preventing the combination of (%3 = sub 0, %1) and (%4 = add %b, %3) into (%3 = sub %b, %1)

[lebedev.ri]

-1 to adding more artificial one-use restrictions.
I agree there is a general problem of unability to see if
there exists a particular instruction already.

[dancgr]

In D70462#1752506, @lebedev.ri wrote:

-1 to adding more artificial one-use restrictions.
I agree there is a general problem of unability to see if
there exists a particular instruction already.

I'm wondering why we should avoid one-use restrictions. Is there any discussion that I'm not aware of?

In this case, we only want to apply the folding if there is only one use of first expression. If there is any more than that, the folding won't give any improvement or cause issues with other optimizations. How would you suggest that I avoid this issue without checking for one-use?

[lebedev.ri]

In D70462#1753932, @dancgr wrote:

In D70462#1752506, @lebedev.ri wrote:

-1 to adding more artificial one-use restrictions.
I agree there is a general problem of unability to see if
there exists a particular instruction already.

I'm wondering why we should avoid one-use restrictions. Is there any discussion that I'm not aware of?

I'm not aware of any concise write-up, but there are at least two things i can note:
Given

%t0 = add i32 %arg, 8
call void @use(i32 %t0)
%t1 = sub i32 2, %t0

That we currently transform into

%t0 = add i32 %arg, 8
call void @use(i32 %t0)
%t1 = sub i32 -6, %arg

1. %t1 no longer depends on %t0, which means %t1 does not have to wait until %t0 finishes executing - reduced dependency chain, improved computation parallelizm
2. We reduced use-count of %t0. There may be some other transform involving %t0 that was previously blocked because %t0 had other uses, which now may happen.

In this case, we only want to apply the folding if there is only one use of first expression.

More specifically, by introducing such limitation we no longer fold this pattern in tests,
which leaves extra instruction[s] which allows the motivational fold in the patch's description to happen.
(please add that test)

If there is any more than that, the folding won't give any improvement or cause issues with other optimizations.

How do we know that?

How would you suggest that I avoid this issue without checking for one-use?

I don't have a simple solution for the issue as described in the patch's description,
although i feel like noting that i believe i have seen similar cases myself.

This is generally impossible to solve with the existing instcombine design - it would need
to be something more similar to what VPlan is supposed to end up being - a list of
possible transforms that we can apply, from which we'd pick so that we end up with best results.

[dancgr]

• [Transform][InstCombine] Add new test case for the specified scenario.

[lebedev.ri]

In D70462#1754654, @lebedev.ri wrote:

In D70462#1753932, @dancgr wrote:

How would you suggest that I avoid this issue without checking for one-use?

I don't have a simple solution for the issue as described in the patch's description,
although i feel like noting that i believe i have seen similar cases myself.

Err, i mean, other than ensuring that the fold you are looking for happens before this constant-folding.
But a bit of a warning: such fold reordering pretty much always exposes other missed folds that will need to be added first.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombiner::foldAddWithConstant(BinaryOperator &Add) {
   if (Instruction *NV = foldBinOpIntoSelectOrPhi(Add))
     return NV;
 
   Value *X;
   Constant *Op00C;
 
   // add (sub C1, X), C2 --> sub (add C1, C2), X
   if (match(Op0, m_Sub(m_Constant(Op00C), m_Value(X))))
+      if (Op0->hasOneUse())
         return BinaryOperator::CreateSub(ConstantExpr::getAdd(Op00C, Op1C), X);
 
+  // add (add C1, X), C2 -> add (C1, C2), X
+  if (match(Op0, m_Add(m_Constant(Op00C), m_Value(X))))
+      if (Op0->hasOneUse())
+        return BinaryOperator::CreateAdd(ConstantExpr::getAdd(Op00C, Op1C), X);
+
   Value *Y;
 
   // add (sub X, Y), -1 --> add (not Y), X
   if (match(Op0, m_OneUse(m_Sub(m_Value(X), m_Value(Y)))) &&
       match(Op1, m_AllOnes()))
     return BinaryOperator::CreateAdd(Builder.CreateNot(Y), X);
 
   // zext(bool) + C -> bool ? C + 1 : C
if (Constant *C = dyn_cast<Constant>(Op0)) {
     if (PHINode *PN = dyn_cast<PHINode>(Op1))
       if (Instruction *R = foldOpIntoPhi(I, PN))
         return R;
 
     Constant *C2;
 
     // C-(C2-X) --> X+(C-C2)
     if (match(Op1, m_Sub(m_Constant(C2), m_Value(X))))
+      // Skip combine if Op1 (C2-X) is used somewhere else, as it will add an extra unnecessary instruction, since the original (C2-X) won't be able to be removed.
+      if (Op1->hasOneUse())
         return BinaryOperator::CreateAdd(X, ConstantExpr::getSub(C, C2));
 
     // C-(X+C2) --> (C-C2)-X
     if (match(Op1, m_Add(m_Value(X), m_Constant(C2))))
+      // Skip combine if Op1 (X+C2) is used somewhere else, as it will add an extra unnecessary instruction, since the original (X+C2) won't be able to be removed.
+      if (Op1->hasOneUse())
         return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
   }
 
   const APInt *Op0C;
   if (match(Op0, m_APInt(Op0C))) {
 
     if (Op0C->isNullValue()) {
       Value *Op1Wide;
       match(Op1, m_TruncOrSelf(m_Value(Op1Wide)));

llvm/test/Transforms/InstCombine/addsub-constant-folding.ll

;
   %t1 = sub i32 2, %t0
   ret i32 %t1
 }
 
 define i32 @add_const_const_sub_extrause(i32 %arg) {
 ; CHECK-LABEL: @add_const_const_sub_extrause(
 ; CHECK-NEXT:    [[T0:%.*]] = add i32 [[ARG:%.*]], 8
 ; CHECK-NEXT:    call void @use(i32 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = sub i32 -6, [[ARG]]
+; CHECK-NEXT:    [[T1:%.*]] = sub i32 2, [[T0:%.*]]
 ; CHECK-NEXT:    ret i32 [[T1]]
 ;
   %t0 = add i32 %arg, 8
   call void @use(i32 %t0)
   %t1 = sub i32 2, %t0
   ret i32 %t1
 }
 
 define <4 x i32> @vec_add_const_const_sub(<4 x i32> %arg) {
 ; CHECK-LABEL: @vec_add_const_const_sub(
 ; CHECK-NEXT:    [[T1:%.*]] = sub <4 x i32> <i32 -6, i32 -6, i32 -6, i32 -6>, [[ARG:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T1]]
 ;
   %t0 = add <4 x i32> %arg, <i32 8, i32 8, i32 8, i32 8>
   %t1 = sub <4 x i32> <i32 2, i32 2, i32 2, i32 2>, %t0
   ret <4 x i32> %t1
 }
 
 define <4 x i32> @vec_add_const_const_sub_extrause(<4 x i32> %arg) {
 ; CHECK-LABEL: @vec_add_const_const_sub_extrause(
 ; CHECK-NEXT:    [[T0:%.*]] = add <4 x i32> [[ARG:%.*]], <i32 8, i32 8, i32 8, i32 8>
 ; CHECK-NEXT:    call void @vec_use(<4 x i32> [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = sub <4 x i32> <i32 -6, i32 -6, i32 -6, i32 -6>, [[ARG]]
+; CHECK-NEXT:    [[T1:%.*]] = sub <4 x i32> <i32 2, i32 2, i32 2, i32 2>, [[T0:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T1]]
 ;
   %t0 = add <4 x i32> %arg, <i32 8, i32 8, i32 8, i32 8>
   call void @vec_use(<4 x i32> %t0)
   %t1 = sub <4 x i32> <i32 2, i32 2, i32 2, i32 2>, %t0
   ret <4 x i32> %t1
 }
 
;
   %t1 = sub i32 2, %t0
   ret i32 %t1
 }
 
 define i32 @sub_const_const_sub_extrause(i32 %arg) {
 ; CHECK-LABEL: @sub_const_const_sub_extrause(
 ; CHECK-NEXT:    [[T0:%.*]] = add i32 [[ARG:%.*]], -8
 ; CHECK-NEXT:    call void @use(i32 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = sub i32 10, [[ARG]]
+; CHECK-NEXT:    [[T1:%.*]] = sub i32 2, [[T0:%.*]]
 ; CHECK-NEXT:    ret i32 [[T1]]
 ;
   %t0 = sub i32 %arg, 8
   call void @use(i32 %t0)
   %t1 = sub i32 2, %t0
   ret i32 %t1
 }
 
+define i32 @sub_const_const_sub_neg(i32 %arg) {
+; CHECK-LABEL: @sub_const_const_sub_neg(
+; CHECK-NEXT:    [[T0:%.*]] = add i32 [[ARG:%.*]], -10
+; CHECK-NEXT:    call void @use(i32 [[T0]])
+; CHECK-NEXT:    [[T1:%.*]] = sub i32 0, [[T0:%.*]]
+; CHECK-NEXT:    ret i32 [[T1]]
+;
+  %t0 = sub i32 %arg, 10
+  call void @use(i32 %t0)
+  %t1 = sub i32 0, %t0
+  %t2 = add i32 8, %t1
+  ret i32 %t1
+}
+
 define <4 x i32> @vec_sub_const_const_sub(<4 x i32> %arg) {
 ; CHECK-LABEL: @vec_sub_const_const_sub(
 ; CHECK-NEXT:    [[T1:%.*]] = sub <4 x i32> <i32 10, i32 10, i32 10, i32 10>, [[ARG:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T1]]
 ;
   %t0 = sub <4 x i32> %arg, <i32 8, i32 8, i32 8, i32 8>
   %t1 = sub <4 x i32> <i32 2, i32 2, i32 2, i32 2>, %t0
   ret <4 x i32> %t1
 }
 
 define <4 x i32> @vec_sub_const_const_sub_extrause(<4 x i32> %arg) {
 ; CHECK-LABEL: @vec_sub_const_const_sub_extrause(
 ; CHECK-NEXT:    [[T0:%.*]] = add <4 x i32> [[ARG:%.*]], <i32 -8, i32 -8, i32 -8, i32 -8>
 ; CHECK-NEXT:    call void @vec_use(<4 x i32> [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = sub <4 x i32> <i32 10, i32 10, i32 10, i32 10>, [[ARG]]
+; CHECK-NEXT:    [[T1:%.*]] = sub <4 x i32> <i32 2, i32 2, i32 2, i32 2>, [[T0:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T1]]
 ;
   %t0 = sub <4 x i32> %arg, <i32 8, i32 8, i32 8, i32 8>
   call void @vec_use(<4 x i32> %t0)
   %t1 = sub <4 x i32> <i32 2, i32 2, i32 2, i32 2>, %t0
   ret <4 x i32> %t1
 }
 
;
   %t1 = add i32 %t0, 2
   ret i32 %t1
 }
 
 define i32 @const_sub_add_const_extrause(i32 %arg) {
 ; CHECK-LABEL: @const_sub_add_const_extrause(
 ; CHECK-NEXT:    [[T0:%.*]] = sub i32 8, [[ARG:%.*]]
 ; CHECK-NEXT:    call void @use(i32 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = sub i32 10, [[ARG]]
+; CHECK-NEXT:    [[T1:%.*]] = add i32 [[T0:%.*]], 2
 ; CHECK-NEXT:    ret i32 [[T1]]
 ;
   %t0 = sub i32 8, %arg
   call void @use(i32 %t0)
   %t1 = add i32 %t0, 2
   ret i32 %t1
 }
 
 define <4 x i32> @vec_const_sub_add_const(<4 x i32> %arg) {
 ; CHECK-LABEL: @vec_const_sub_add_const(
 ; CHECK-NEXT:    [[T1:%.*]] = sub <4 x i32> <i32 10, i32 10, i32 10, i32 10>, [[ARG:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T1]]
 ;
   %t0 = sub <4 x i32> <i32 8, i32 8, i32 8, i32 8>, %arg
   %t1 = add <4 x i32> %t0, <i32 2, i32 2, i32 2, i32 2>
   ret <4 x i32> %t1
 }
 
 define <4 x i32> @vec_const_sub_add_const_extrause(<4 x i32> %arg) {
 ; CHECK-LABEL: @vec_const_sub_add_const_extrause(
 ; CHECK-NEXT:    [[T0:%.*]] = sub <4 x i32> <i32 8, i32 8, i32 8, i32 8>, [[ARG:%.*]]
 ; CHECK-NEXT:    call void @vec_use(<4 x i32> [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = sub <4 x i32> <i32 10, i32 10, i32 10, i32 10>, [[ARG]]
+; CHECK-NEXT:    [[T1:%.*]] = add <4 x i32> [[T0:%.*]], <i32 2, i32 2, i32 2, i32 2>
 ; CHECK-NEXT:    ret <4 x i32> [[T1]]
 ;
   %t0 = sub <4 x i32> <i32 8, i32 8, i32 8, i32 8>, %arg
   call void @vec_use(<4 x i32> %t0)
   %t1 = add <4 x i32> %t0, <i32 2, i32 2, i32 2, i32 2>
   ret <4 x i32> %t1
 }
 
;
   %t1 = sub i32 %t0, 2
   ret i32 %t1
 }
 
 define i32 @const_sub_sub_const_extrause(i32 %arg) {
 ; CHECK-LABEL: @const_sub_sub_const_extrause(
 ; CHECK-NEXT:    [[T0:%.*]] = sub i32 8, [[ARG:%.*]]
 ; CHECK-NEXT:    call void @use(i32 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = sub i32 6, [[ARG]]
+; CHECK-NEXT:    [[T1:%.*]] = add i32 [[T0:%.*]], -2
 ; CHECK-NEXT:    ret i32 [[T1]]
 ;
   %t0 = sub i32 8, %arg
   call void @use(i32 %t0)
   %t1 = sub i32 %t0, 2
   ret i32 %t1
 }
 
 define <4 x i32> @vec_const_sub_sub_const(<4 x i32> %arg) {
 ; CHECK-LABEL: @vec_const_sub_sub_const(
 ; CHECK-NEXT:    [[T1:%.*]] = sub <4 x i32> <i32 6, i32 6, i32 6, i32 6>, [[ARG:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T1]]
 ;
   %t0 = sub <4 x i32> <i32 8, i32 8, i32 8, i32 8>, %arg
   %t1 = sub <4 x i32> %t0, <i32 2, i32 2, i32 2, i32 2>
   ret <4 x i32> %t1
 }
 
 define <4 x i32> @vec_const_sub_sub_const_extrause(<4 x i32> %arg) {
 ; CHECK-LABEL: @vec_const_sub_sub_const_extrause(
 ; CHECK-NEXT:    [[T0:%.*]] = sub <4 x i32> <i32 8, i32 8, i32 8, i32 8>, [[ARG:%.*]]
 ; CHECK-NEXT:    call void @vec_use(<4 x i32> [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = sub <4 x i32> <i32 6, i32 6, i32 6, i32 6>, [[ARG]]
+; CHECK-NEXT:    [[T1:%.*]] = add <4 x i32> [[T0:%.*]], <i32 -2, i32 -2, i32 -2, i32 -2>
 ; CHECK-NEXT:    ret <4 x i32> [[T1]]
 ;
   %t0 = sub <4 x i32> <i32 8, i32 8, i32 8, i32 8>, %arg
   call void @vec_use(<4 x i32> %t0)
   %t1 = sub <4 x i32> %t0, <i32 2, i32 2, i32 2, i32 2>
   ret <4 x i32> %t1
 }
 
;
   %t1 = sub i32 2, %t0
   ret i32 %t1
 }
 
 define i32 @const_sub_const_sub_extrause(i32 %arg) {
 ; CHECK-LABEL: @const_sub_const_sub_extrause(
 ; CHECK-NEXT:    [[T0:%.*]] = sub i32 8, [[ARG:%.*]]
 ; CHECK-NEXT:    call void @use(i32 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = add i32 [[ARG]], -6
+; CHECK-NEXT:    [[T1:%.*]] = sub i32 2, [[T0:%.*]]
 ; CHECK-NEXT:    ret i32 [[T1]]
 ;
   %t0 = sub i32 8, %arg
   call void @use(i32 %t0)
   %t1 = sub i32 2, %t0
   ret i32 %t1
 }
 
 define <4 x i32> @vec_const_sub_const_sub(<4 x i32> %arg) {
 ; CHECK-LABEL: @vec_const_sub_const_sub(
 ; CHECK-NEXT:    [[T1:%.*]] = add <4 x i32> [[ARG:%.*]], <i32 -6, i32 -6, i32 -6, i32 -6>
 ; CHECK-NEXT:    ret <4 x i32> [[T1]]
 ;
   %t0 = sub <4 x i32> <i32 8, i32 8, i32 8, i32 8>, %arg
   %t1 = sub <4 x i32> <i32 2, i32 2, i32 2, i32 2>, %t0
   ret <4 x i32> %t1
 }
 
 define <4 x i32> @vec_const_sub_const_sub_extrause(<4 x i32> %arg) {
 ; CHECK-LABEL: @vec_const_sub_const_sub_extrause(
 ; CHECK-NEXT:    [[T0:%.*]] = sub <4 x i32> <i32 8, i32 8, i32 8, i32 8>, [[ARG:%.*]]
 ; CHECK-NEXT:    call void @vec_use(<4 x i32> [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = add <4 x i32> [[ARG]], <i32 -6, i32 -6, i32 -6, i32 -6>
+; CHECK-NEXT:    [[T1:%.*]] = sub <4 x i32> <i32 2, i32 2, i32 2, i32 2>, [[T0:%.*]]
 ; CHECK-NEXT:    ret <4 x i32> [[T1]]
 ;
   %t0 = sub <4 x i32> <i32 8, i32 8, i32 8, i32 8>, %arg
   call void @vec_use(<4 x i32> %t0)
   %t1 = sub <4 x i32> <i32 2, i32 2, i32 2, i32 2>, %t0
   ret <4 x i32> %t1
 }