[InstCombine] add support for multi-use Y of (X op Y) op Z --> (Y op Z) op X

[Chenbing.Zheng]

Summary

For (X op Y) op Z --> (Y op Z) op X
we can still do transform when Y is multi-use. In D131356
limit it to one-use, this patch remove this limit.

This is still not a complete solution, I add a todo test to show it.
In this case, X and Y are both multi use, we can't differentiate how to convert based on this.
But, At least the branch we added won't make the code worse，and it solves half the scenarios

[bcl5980]

I agree this change help to get more opportune to combine. But I still feel a little strange for the non-deterministic transform here.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1754–1755

m_BinOp is enough?

[Chenbing.Zheng]

address comment

[Chenbing.Zheng]

In D132783#3754025, @bcl5980 wrote:

I agree this change help to get more opportune to combine. But I still feel a little strange for the non-deterministic transform here.

Yer, this change will not directly optimize，and the information provided here is limited. When X, Y are both multi-use, We don't know how to transform so that the code is optimized.
But at least this provides more opportunities here.

[spatel]

I agree that this patch is taking the transform further into "-reassociate" territory, but I don't see a specific problem with the minor enhancement, so LGTM.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1758

Move this comment line down, so it is above the corresponding code.
Add another comment for:

// (X op Y) opZ --> (X op Z) op Y

[Chenbing.Zheng]

I commit this patch https://reviews.llvm.org/rG35a3048c2501, but forget associate this patch and I will close this.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1758

OK, I will modify it when I commit.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

 
 /// Try to reassociate a pair of binops so that values with one use only are
 /// part of the same instruction. This may enable folds that are limited with
 /// multi-use restrictions and makes it more likely to match other patterns that
 /// are looking for a common operand.
 static Instruction *reassociateForUses(BinaryOperator &BO,
                                        InstCombinerImpl::BuilderTy &Builder) {
   Instruction::BinaryOps Opcode = BO.getOpcode();
   Value *X, *Y, *Z;
-  if (match(&BO, m_c_BinOp(Opcode,
-                           m_OneUse(m_c_BinOp(Opcode, m_Value(X),
-                                              m_OneUse(m_Value(Y)))),
-                           m_OneUse(m_Value(Z))))) {
+  if (match(&BO,
+            m_c_BinOp(Opcode, m_OneUse(m_BinOp(Opcode, m_Value(X), m_Value(Y))),
     // (X op Y) op Z --> (Y op Z) op X
-    if (!isa<Constant>(X) && !isa<Constant>(Y) && !isa<Constant>(Z) &&
-        !X->hasOneUse()) {
+    if (!isa<Constant>(X) && !isa<Constant>(Y) && !isa<Constant>(Z)) {
+      if (!X->hasOneUse()) {
         Value *YZ = Builder.CreateBinOp(Opcode, Y, Z);
         return BinaryOperator::Create(Opcode, YZ, X);
       }
+      if (!Y->hasOneUse()) {
+        Value *XZ = Builder.CreateBinOp(Opcode, X, Z);
+        return BinaryOperator::Create(Opcode, XZ, Y);
+      }
+    }
   }
 
   return nullptr;
 }
 
 // Match
 // (X + C2) | C
 // (X + C2) ^ C

llvm/test/Transforms/InstCombine/and-or-not.ll

;
   %r = and <2 x i4> %x, %not_xyz
   ret <2 x i4> %r
 }
 
 ; TODO: This should simplify.
 
 define i4 @simplify_and_common_op_use1(i4 %x, i4 %y, i4 %z)  {
 ; CHECK-LABEL: @simplify_and_common_op_use1(
-; CHECK-NEXT:    [[XY:%.*]] = or i4 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    call void @use(i4 [[Y]])
-; CHECK-NEXT:    [[XYZ:%.*]] = or i4 [[XY]], [[Z:%.*]]
-; CHECK-NEXT:    [[NOT_XYZ:%.*]] = xor i4 [[XYZ]], -1
-; CHECK-NEXT:    [[R:%.*]] = and i4 [[NOT_XYZ]], [[X]]
-; CHECK-NEXT:    ret i4 [[R]]
+; CHECK-NEXT:    call void @use(i4 [[Y:%.*]])
+; CHECK-NEXT:    ret i4 0
 ;
   %xy = or i4 %x, %y
   call void @use(i4 %y)
   %xyz = or i4 %xy, %z
   %not_xyz = xor i4 %xyz, -1
   %r = and i4 %not_xyz, %x
   ret i4 %r
 }
 
 ; TODO: This should simplify.
 
 define i4 @simplify_and_common_op_use2(i4 %x, i4 %y, i4 %z)  {
 ; CHECK-LABEL: @simplify_and_common_op_use2(
+; CHECK-NEXT:    call void @use(i4 [[Y:%.*]])
+; CHECK-NEXT:    [[TMP1:%.*]] = or i4 [[X:%.*]], [[Z:%.*]]
+; CHECK-NEXT:    [[XYZ:%.*]] = or i4 [[TMP1]], [[Y]]
+; CHECK-NEXT:    [[NOT_XYZ:%.*]] = xor i4 [[XYZ]], -1
+; CHECK-NEXT:    [[R:%.*]] = and i4 [[NOT_XYZ]], [[X]]
+; CHECK-NEXT:    ret i4 [[R]]
+;
+  %xy = or i4 %y, %x
+  call void @use(i4 %y)
+  %xyz = or i4 %xy, %z
+  %not_xyz = xor i4 %xyz, -1
+  %r = and i4 %not_xyz, %x
+  ret i4 %r
+}
+
+; TODO: This should simplify.
+
+define i4 @simplify_and_common_op_use3(i4 %x, i4 %y, i4 %z)  {
+; CHECK-LABEL: @simplify_and_common_op_use3(
 ; CHECK-NEXT:    [[XY:%.*]] = or i4 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[XYZ:%.*]] = or i4 [[XY]], [[Z:%.*]]
 ; CHECK-NEXT:    call void @use(i4 [[Z]])
 ; CHECK-NEXT:    [[NOT_XYZ:%.*]] = xor i4 [[XYZ]], -1
 ; CHECK-NEXT:    [[R:%.*]] = and i4 [[NOT_XYZ]], [[X]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %xy = or i4 %x, %y