[LogicCombine 4/?] Support combine xor chain with 2 elements

llvm/lib/Analysis/LogicCombine.cpp

Value *LogicCombiner::logicalOpToValue(LogicalOpNode *Node) {
   if (Expr.size() == 0)
     return Constant::getNullValue(Node->getValue()->getType());
 
   if (Node->getPoisonMaskSI() != 0)
     return nullptr;
 
   Instruction *I = cast<Instruction>(Node->getValue());
   Type *Ty = I->getType();
+  IRBuilder<> Builder(I);
   if (Expr.size() == 1) {
     uint64_t LeafBits = *Expr.begin();
     unsigned InstCnt = popcount(LeafBits) - 1;
     // TODO: For now we assume we can't reuse any node from old instruction.
     // Later we can search if we can reuse the node is not one use.
-    if (Node->worthToCombine(InstCnt)) {
-      IRBuilder<> Builder(I);
+    if (Node->worthToCombine(InstCnt))
       return buildAndChain(Builder, Ty, LeafBits);
-    }
+
+  if (Expr.size() == 2) {
+    uint64_t LHS = *Expr.begin();
+    uint64_t RHS = *(++Expr.begin());
+    uint64_t CommonAnd = LHS & RHS;
+    if (CommonAnd) {
+      LHS &= ~CommonAnd;
+      if (LHS == 0)
+        LHS = LogicalExpr::ExprAllOne;
+      RHS &= ~CommonAnd;
+      if (RHS == 0)
+        RHS = LogicalExpr::ExprAllOne;
+    }
+    unsigned InstCnt = popcount(CommonAnd) + popcount(LHS) + popcount(RHS) - 1;
+    if (Node->worthToCombine(InstCnt)) {
+      Value *LHSV = buildAndChain(Builder, Ty, LHS);
+      Value *RHSV = buildAndChain(Builder, Ty, RHS);
+      Value *Ret = Builder.CreateXor(LHSV, RHSV);
+      if (CommonAnd)
+        Ret = Builder.CreateAnd(Ret, buildAndChain(Builder, Ty, CommonAnd));
+      return Ret;
+    }
   }
 
-  // TODO: find the simplest form from logical expression when it is not
-  // only an "and" chain.
+  // TODO: find the simplest form from logical expression when it has more than
+  // 2 and chains.
 
   return nullptr;
 }
 
 Value *LogicCombiner::buildAndChain(IRBuilder<> &Builder, Type *Ty,
                                     uint64_t LeafBits) {
   if (LeafBits == 0)
     return Constant::getNullValue(Ty);

llvm/test/Transforms/AggressiveInstCombine/logic-combine.ll

 ; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i8 [[TMP1]]
 ;
   %ab = and i8 %a, %b
   %and.ab.a = and i8 %ab, %a
   ret i8 %and.ab.a
 }
 
+define i16 @leaf2_ret_xor(i16 %a, i16 %b)  {
+; CHECK-LABEL: @leaf2_ret_xor(
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i16 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i16 [[TMP1]]
+;
+  %or.ab = or i16 %a, %b
+  %and.ab = and i16 %a, %b
+  %xor = xor i16 %or.ab, %and.ab
+  ret i16 %xor
+}
+
 define i8 @leaf3_complex_ret_const_false(i8 %a, i8 %b, i8 %c)  {
 ; CHECK-LABEL: @leaf3_complex_ret_const_false(
 ; CHECK-NEXT:    ret i8 0
 ;
   %ab = or i8 %a, %b
   %abc = or i8 %ab, %c
   %not.abc = xor i8 %abc, -1
   %r = and i8 %not.abc, %a
;
   %or2 = or i1 %or1, %c
   %xor = xor i1 %or2, %a
   %or3 = or i1 %not.a, %c
   %or4 = select i1 %or3, i1 true, i1 %b
   %cond = xor i1 %xor, %or4
   ret i1 %cond
 }
 
+define i7 @leaf4_complex_ret_xor(i7 %a, i7 %b, i7 %c, i7 %d)  {
+; CHECK-LABEL: @leaf4_complex_ret_xor(
+; CHECK-NEXT:    [[XOR_BD:%.*]] = xor i7 [[B:%.*]], [[D:%.*]]
+; CHECK-NEXT:    ret i7 [[XOR_BD]]
+;
+  %bd = and i7 %b, %d
+  %xor = xor i7 %bd, %c
+  %not.bd = xor i7 %xor, -1
+  %xor.ab = xor i7 %a, %b
+  %or1 = or i7 %xor.ab, %c
+  %or2 = or i7 %or1, %not.bd
+  %or3 = or i7 %or2, %a
+  %and = and i7 %or3, %b
+  %xor.bd = xor i7 %and, %d
+  ret i7 %xor.bd
+}
+
+define i7 @leaf4_complex_ret_xor_oneside_and(i7 %a, i7 %b, i7 %c, i7 %d)  {
+; CHECK-LABEL: @leaf4_complex_ret_xor_oneside_and(
+; CHECK-NEXT:    [[AND2:%.*]] = and i7 [[D:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[XOR_BD:%.*]] = xor i7 [[B]], [[AND2]]
+; CHECK-NEXT:    ret i7 [[XOR_BD]]
+;
+  %bd = and i7 %b, %d
+  %xor = xor i7 %bd, %c
+  %not.bd = xor i7 %xor, -1
+  %xor.ab = xor i7 %a, %b
+  %or1 = or i7 %xor.ab, %c
+  %or2 = or i7 %or1, %not.bd
+  %or3 = or i7 %or2, %a
+  %and = and i7 %or3, %b
+  %and2 = and i7 %d, %b
+  %xor.bd = xor i7 %and, %and2
+  ret i7 %xor.bd
+}
+
+define i7 @leaf4_complex_ret_xor_both_and(i7 %a, i7 %b, i7 %c, i7 %d)  {
+; CHECK-LABEL: @leaf4_complex_ret_xor_both_and(
+; CHECK-NEXT:    [[AND2:%.*]] = and i7 [[A:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i7 [[D:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[XOR_BD:%.*]] = xor i7 [[AND2]], [[AND3]]
+; CHECK-NEXT:    ret i7 [[XOR_BD]]
+;
+  %bd = and i7 %b, %d
+  %xor = xor i7 %bd, %c
+  %not.bd = xor i7 %xor, -1
+  %xor.ab = xor i7 %a, %b
+  %or1 = or i7 %xor.ab, %c
+  %or2 = or i7 %or1, %not.bd
+  %or3 = or i7 %or2, %a
+  %and = and i7 %or3, %b
+  %and2 = and i7 %a, %c
+  %and3 = and i7 %d, %and
+  %xor.bd = xor i7 %and2, %and3
+  ret i7 %xor.bd
+}
+
 declare void @use8(i8)
 declare void @use32(i32)