Index: llvm/lib/Transforms/AggressiveInstCombine/ComplexLogicalOpsCombine.h
===================================================================
--- llvm/lib/Transforms/AggressiveInstCombine/ComplexLogicalOpsCombine.h
+++ llvm/lib/Transforms/AggressiveInstCombine/ComplexLogicalOpsCombine.h
@@ -38,6 +38,8 @@
   void print(raw_ostream &OS) const;
 
   LogicalExpr Expr;
+  unsigned Weight;
+  unsigned NUseWeight;
 };
 
 class LogicalOpsHelper {
@@ -60,6 +62,7 @@
   bool visitBinOp(LogicalOpNode *Node, BinaryOperator *BO, unsigned Depth);
   LogicalOpNode *getLogicalOpNode(Value *Val, unsigned Depth = 0);
   Value *logicalOpToValue(LogicalOpNode *Node);
+  Value *buildAndChain(Instruction *I, unsigned Mask);
 };
 
 inline raw_ostream &operator<<(raw_ostream &OS, const LogicalOpNode &I) {
Index: llvm/lib/Transforms/AggressiveInstCombine/ComplexLogicalOpsCombine.cpp
===================================================================
--- llvm/lib/Transforms/AggressiveInstCombine/ComplexLogicalOpsCombine.cpp
+++ llvm/lib/Transforms/AggressiveInstCombine/ComplexLogicalOpsCombine.cpp
@@ -33,6 +33,7 @@
 #include "ComplexLogicalOpsCombine.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 
@@ -152,6 +153,7 @@
 
   printAndChain(OS, *Expr.begin());
   OS << "\n";
+  OS << "Weight: " << Weight << "; NUseWeight: " << NUseWeight << ";\n";
 }
 
 void LogicalOpsHelper::clear() {
@@ -182,6 +184,8 @@
       LeafSet.insert(Val).second)
     LeafValues.push_back(Val);
   Node->Expr.insert(ExprVal);
+  Node->Weight = 0;
+  Node->NUseWeight = 0;
   LogicalOpNodes[Val] = Node;
   return true;
 }
@@ -207,6 +211,11 @@
     Node->Expr = exprOr(LHS->Expr, RHS->Expr);
   else
     Node->Expr = exprXor(LHS->Expr, RHS->Expr);
+  // TODO: We can reduce the weight if th node can be simplified even if
+  // it is not the root node.
+  Node->Weight = LHS->Weight + RHS->Weight + 1;
+  Node->NUseWeight =
+      BO->hasOneUse() ? (LHS->NUseWeight + RHS->NUseWeight) : Node->Weight;
   LogicalOpNodes[BO] = Node;
   return true;
 }
@@ -233,6 +242,20 @@
   return LogicalOpNodes[Val];
 }
 
+Value *LogicalOpsHelper::buildAndChain(Instruction *I, unsigned Mask) {
+  IRBuilder<> Builder(I);
+  unsigned ElementCnt = llvm::popcount(Mask);
+  unsigned MaskIdx = llvm::countTrailingZeros(Mask);
+  Value *AndChain = LeafValues[MaskIdx];
+  Mask -= (1 << MaskIdx);
+  for (unsigned I = 1; I < ElementCnt; I++) {
+    MaskIdx = llvm::countTrailingZeros(Mask);
+    AndChain = Builder.CreateAnd(AndChain, LeafValues[MaskIdx]);
+    Mask -= (1 << MaskIdx);
+  }
+  return AndChain;
+}
+
 Value *LogicalOpsHelper::logicalOpToValue(LogicalOpNode *Node) {
   if (Node == nullptr)
     return nullptr;
@@ -249,8 +272,16 @@
     if (ExprMask == ExprNegOne)
       return Constant::getAllOnesValue(Node->getValue()->getType());
 
-    if (llvm::popcount(ExprMask) == 1)
+    unsigned ElementCnt = llvm::popcount(ExprMask);
+    if (ElementCnt == 1)
       return LeafValues[llvm::Log2_32(ExprMask)];
+
+    unsigned ChainCnt = ElementCnt - 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->NUseWeight + ChainCnt) < Node->Weight)
+      return buildAndChain(cast<Instruction>(Node->getValue()), ExprMask);
+    return nullptr;
   }
 
   // TODO: complex pattern simpilify
Index: llvm/test/Transforms/AggressiveInstCombine/complex-logic-ops.ll
===================================================================
--- llvm/test/Transforms/AggressiveInstCombine/complex-logic-ops.ll
+++ llvm/test/Transforms/AggressiveInstCombine/complex-logic-ops.ll
@@ -53,4 +53,71 @@
   ret void
 }
 
+define void @test3(i1 %a, i1 %b, i1 %c, i1 %d)  {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[B:%.*]], [[D:%.*]]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    call void @usev()
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    ret void
+;
+  %bd = and i1 %b, %d
+  %xor = xor i1 %bd, %c
+  %not.bd = xor i1 %xor, true
+  %xor.ab = xor i1 %a, %b
+  %or1 = or i1 %xor.ab, %c
+  %or2 = or i1 %or1, %not.bd
+  %or3 = or i1 %or2, %a
+  %and = and i1 %or3, %b
+  %and2 = and i1 %and, %d
+  br i1 %and2, label %if.end, label %if.then
+
+if.then:
+  call void @usev()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+define void @test4(i1 %a, i1 %b, i1 %c, i1 %d)  {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:    [[BD:%.*]] = and i1 [[B:%.*]], [[D:%.*]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i1 [[BD]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT_BD:%.*]] = xor i1 [[XOR]], true
+; CHECK-NEXT:    [[XOR_AB:%.*]] = xor i1 [[A:%.*]], [[B]]
+; CHECK-NEXT:    [[OR1:%.*]] = or i1 [[XOR_AB]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i1 [[OR1]], [[NOT_BD]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[B]], [[D]]
+; CHECK-NEXT:    call void @use1(i1 [[OR2]])
+; CHECK-NEXT:    br i1 [[TMP1]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    call void @usev()
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    ret void
+;
+  %bd = and i1 %b, %d
+  %xor = xor i1 %bd, %c
+  %not.bd = xor i1 %xor, true
+  %xor.ab = xor i1 %a, %b
+  %or1 = or i1 %xor.ab, %c
+  %or2 = or i1 %or1, %not.bd
+  %or3 = or i1 %or2, %a
+  %and = and i1 %or3, %b
+  %and2 = and i1 %and, %d
+  call void @use1(i1 %or2)
+  br i1 %and2, label %if.end, label %if.then
+
+if.then:
+  call void @usev()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
 declare void @usev()
+declare void @use1(i1)