[InstCombine] Combine binary operator of two phi node

[StephenFan]

Summary

Combine binary operator of two phi node if there is at least one
specific constant value in phi0 and phi1's incoming values for each
same incoming block and this specific constant value can be used
to do optimization for specific binary operator.
For example:

%phi0 = phi i32 [0, %bb0], [%i, %bb1]
%phi1 = phi i32 [%j, %bb0], [0, %bb1]
%add = add i32 %phi0, %phi1
==>
%add = phi i32 [%j, %bb0], [%i, %bb1]

Fixes: https://github.com/llvm/llvm-project/issues/61137

[xbolva00]

This optimization can be more general, why only add?

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1324

call InstSimplify instead of matching this specific pattern?

[nikic]

In D145223#4166573, @xbolva00 wrote:

This optimization can be more general, why only add?

Right. This can be generalized at least to ConstantExpr::getBinOpIdentity(), but more generally to performing a simplification on all operands -- the latter might be expensive in terms of compile-time though.

[StephenFan]

In D145223#4166573, @xbolva00 wrote:

This optimization can be more general, why only add?

Yes, it can be more general. But I want to solve the issue first and left a TODO. Or if you strongly recommend implementing other binary operators in this patch, I am willing to do it.

[StephenFan]

In D145223#4166576, @nikic wrote:

In D145223#4166573, @xbolva00 wrote:

This optimization can be more general, why only add?

Right. This can be generalized at least to ConstantExpr::getBinOpIdentity(), but more generally to performing a simplification on all operands -- the latter might be expensive in terms of compile-time though.

Okay, let me try to generalize to ConstantExpr::getBinOpIdentity().

[StephenFan]

Support BinOp Identity.

[hiraditya]

This comment was removed by hiraditya.

[hiraditya]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1297

D

1314

nit: any remaining operators we are still missing?

[nikic]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1314

Might make more sense to mention generalization to inst simplify.

1318

Drop llvm::

1320

This indent is ugly, I'd suggest moving this function into a variable.

1328

No need to dyn_cast, just comparison is enough.

llvm/test/Transforms/InstCombine/phi.ll

1642

Add a test with sub to show that non-commutative operator is not folded?

[StephenFan]

Move function into a variable and add sub test.

[nikic]

LG

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1305

values -> value

1306

value -> values :)

1321

Drop braces

llvm/test/Transforms/InstCombine/phi.ll

1644

cannt -> cant or cannot

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 
 Instruction *InstCombinerImpl::foldBinopWithPhiOperands(BinaryOperator &BO) {
   // TODO: This should be similar to the incoming values check in foldOpIntoPhi:
   //       we are guarding against replicating the binop in >1 predecessor.
   //       This could miss matching a phi with 2 constant incoming values.
   auto *Phi0 = dyn_cast<PHINode>(BO.getOperand(0));
   auto *Phi1 = dyn_cast<PHINode>(BO.getOperand(1));
   if (!Phi0 || !Phi1 || !Phi0->hasOneUse() || !Phi1->hasOneUse() ||
-      Phi0->getNumOperands() != 2 || Phi1->getNumOperands() != 2)
+      Phi0->getNumOperands() != Phi1->getNumOperands())
     return nullptr;
 
   // TODO: Remove the restriction for binop being in the same block as the phis.
   if (BO.getParent() != Phi0->getParent() ||
       BO.getParent() != Phi1->getParent())
     return nullptr;
 
+  // Fold if there is at least one specific constant values in phi0 or phi1's
+  // incoming value that comes from the same block and this specific constant
+  // value can be used to do optimization for specific binary operator.
+  // For example:
+  // %phi0 = phi i32 [0, %bb0], [%i, %bb1]
+  // %phi1 = phi i32 [%j, %bb0], [0, %bb1]
+  // %add = add i32 %phi0, %phi1
+  // ==>
+  // %add = phi i32 [%j, %bb0], [%i, %bb1]
+  // TODO: Support other binary operators
+  Constant *C = ConstantExpr::getBinOpIdentity(BO.getOpcode(), BO.getType(),
+                                               /*AllowRHSConstant*/ false);
+  if (C) {
+    llvm::SmallVector<Value *, 4> NewIncomingValues;
+    if (all_of(llvm::zip(Phi0->operands(), Phi1->operands()),
+               [&](std::tuple<llvm::Use &, llvm::Use &> T) {
+                 auto &Phi0Use = std::get<0>(T);
+                 auto &Phi1Use = std::get<1>(T);
+                 if (Phi0->getIncomingBlock(Phi0Use) !=
+                     Phi1->getIncomingBlock(Phi1Use))
+                   return false;
+                 Value *Phi0UseV = Phi0Use.get();
+                 Value *Phi1UseV = Phi1Use.get();
+                 if (dyn_cast<Constant>(Phi0UseV) == C)
+                   NewIncomingValues.push_back(Phi1UseV);
+                 else if (dyn_cast<Constant>(Phi1UseV) == C)
+                   NewIncomingValues.push_back(Phi0UseV);
+                 else
+                   return false;
+                 return true;
+               })) {
+      PHINode *NewPhi =
+          PHINode::Create(Phi0->getType(), Phi0->getNumOperands());
+      assert(NewIncomingValues.size() == Phi0->getNumOperands() &&
+             "The number of collected incoming values should equal the number "
+             "of the original PHINode operands!");
+      for (unsigned I = 0; I < Phi0->getNumOperands(); I++)
+        NewPhi->addIncoming(NewIncomingValues[I], Phi0->getIncomingBlock(I));
+      return NewPhi;
+    }
+  }
+
+  if (Phi0->getNumOperands() != 2 || Phi1->getNumOperands() != 2)
+    return nullptr;
+
   // Match a pair of incoming constants for one of the predecessor blocks.
   BasicBlock *ConstBB, *OtherBB;
   Constant *C0, *C1;
   if (match(Phi0->getIncomingValue(0), m_ImmConstant(C0))) {
     ConstBB = Phi0->getIncomingBlock(0);
     OtherBB = Phi0->getIncomingBlock(1);
   } else if (match(Phi0->getIncomingValue(1), m_ImmConstant(C0))) {
     ConstBB = Phi0->getIncomingBlock(1);

llvm/test/Transforms/InstCombine/phi.ll

 
 define i32 @add_two_phi_node_can_fold(i1 %c, i32 %i, i32 %j)  {
 ; CHECK-LABEL: @add_two_phi_node_can_fold(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[X:%.*]] = phi i32 [ 0, [[IF_THEN]] ], [ [[J:%.*]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[Y:%.*]] = phi i32 [ [[I:%.*]], [[IF_THEN]] ], [ 0, [[ENTRY]] ]
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = phi i32 [ [[I:%.*]], [[IF_THEN]] ], [ [[J:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
 entry:
   br i1 %c, label %if.then, label %if.end
 
 if.then:
   br label %if.end
 

 
 define i32 @or_two_phi_node_can_fold(i1 %c, i32 %i, i32 %j)  {
 ; CHECK-LABEL: @or_two_phi_node_can_fold(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[X:%.*]] = phi i32 [ 0, [[IF_THEN]] ], [ [[J:%.*]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[Y:%.*]] = phi i32 [ [[I:%.*]], [[IF_THEN]] ], [ 0, [[ENTRY]] ]
-; CHECK-NEXT:    [[ADD:%.*]] = or i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = phi i32 [ [[I:%.*]], [[IF_THEN]] ], [ [[J:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
 entry:
   br i1 %c, label %if.then, label %if.end
 
 if.then:
   br label %if.end
 
 if.end:
   %x = phi i32 [ 0, %if.then ], [ %j, %entry ]
   %y = phi i32 [ %i, %if.then ], [ 0, %entry ]
   %add = or i32 %y, %x
   ret i32 %add
 }
 
 define i32 @and_two_phi_node_can_fold(i1 %c, i32 %i, i32 %j)  {
 ; CHECK-LABEL: @and_two_phi_node_can_fold(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[X:%.*]] = phi i32 [ -1, [[IF_THEN]] ], [ [[J:%.*]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[Y:%.*]] = phi i32 [ [[I:%.*]], [[IF_THEN]] ], [ -1, [[ENTRY]] ]
-; CHECK-NEXT:    [[ADD:%.*]] = and i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = phi i32 [ [[I:%.*]], [[IF_THEN]] ], [ [[J:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
 entry:
   br i1 %c, label %if.then, label %if.end
 
 if.then:
   br label %if.end
 
 if.end:
   %x = phi i32 [ -1, %if.then ], [ %j, %entry ]
   %y = phi i32 [ %i, %if.then ], [ -1, %entry ]
   %add = and i32 %y, %x
   ret i32 %add
 }
 
 define i32 @mul_two_phi_node_can_fold(i1 %c, i32 %i, i32 %j)  {
 ; CHECK-LABEL: @mul_two_phi_node_can_fold(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[X:%.*]] = phi i32 [ 1, [[IF_THEN]] ], [ [[J:%.*]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[Y:%.*]] = phi i32 [ [[I:%.*]], [[IF_THEN]] ], [ 1, [[ENTRY]] ]
-; CHECK-NEXT:    [[ADD:%.*]] = mul i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = phi i32 [ [[I:%.*]], [[IF_THEN]] ], [ [[J:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
 entry:
   br i1 %c, label %if.then, label %if.end
 
 if.then:
   br label %if.end
 
 if.end:
   %x = phi i32 [ 1, %if.then ], [ %j, %entry ]
   %y = phi i32 [ %i, %if.then ], [ 1, %entry ]
   %add = mul i32 %y, %x
   ret i32 %add
 }
 
 define i32 @xor_two_phi_node_can_fold(i1 %c, i32 %i, i32 %j)  {
 ; CHECK-LABEL: @xor_two_phi_node_can_fold(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    [[X:%.*]] = phi i32 [ 0, [[IF_THEN]] ], [ [[J:%.*]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[Y:%.*]] = phi i32 [ [[I:%.*]], [[IF_THEN]] ], [ 0, [[ENTRY]] ]
-; CHECK-NEXT:    [[ADD:%.*]] = xor i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = phi i32 [ [[I:%.*]], [[IF_THEN]] ], [ [[J:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
 entry:
   br i1 %c, label %if.then, label %if.end
 
 if.then:
   br label %if.end
 
 if.end:
   %x = phi i32 [ 0, %if.then ], [ %j, %entry ]
   %y = phi i32 [ %i, %if.then ], [ 0, %entry ]
   %add = xor i32 %y, %x
   ret i32 %add
 }