Index: llvm/include/llvm/Analysis/ComplexLogicCombine.h
===================================================================
--- llvm/include/llvm/Analysis/ComplexLogicCombine.h
+++ llvm/include/llvm/Analysis/ComplexLogicCombine.h
@@ -52,7 +52,8 @@
 class LogicalOpsHelper {
 public:
   LogicalOpsHelper()
-      : LogicalOpNodes(), LeafSet(), LeafValues(), LeafsMayPoison() {}
+      : LogicalOpNodes(), LeafSet(), LeafValues(), LeafsMayPoison(),
+        ConstantLeafs() {}
   ~LogicalOpsHelper() { clear(); }
 
   Value *simplify(Value *Root);
@@ -64,6 +65,9 @@
   SmallPtrSet<Value *, 8> LeafSet;
   SmallVector<Value *, 8> LeafValues;
   uint64_t LeafsMayPoison;
+  uint64_t ConstantLeafs;
+  Constant *ConstAllOne;
+  Constant *ConstZero;
 
   void clear();
 
Index: llvm/lib/Analysis/ComplexLogicCombine.cpp
===================================================================
--- llvm/lib/Analysis/ComplexLogicCombine.cpp
+++ llvm/lib/Analysis/ComplexLogicCombine.cpp
@@ -107,6 +107,7 @@
   for (auto node : LogicalOpNodes)
     delete node.second;
   LeafsMayPoison = 0;
+  ConstantLeafs = 0;
   LogicalOpNodes.clear();
   LeafSet.clear();
   LeafValues.clear();
@@ -131,6 +132,8 @@
       LeafSet.insert(Val).second) {
     if (!isGuaranteedNotToBeUndefOrPoison(Val))
       LeafsMayPoison |= ExprVal;
+    if (isa<Constant>(Val))
+      ConstantLeafs |= ExprVal;
     LeafValues.push_back(Val);
   }
   LogicalOpNode *Node =
@@ -253,12 +256,17 @@
   Instruction *I = cast<Instruction>(Node->getValue());
   Type *Ty = I->getType();
   IRBuilder<> Builder(I);
+  auto GetInstCnt = [this](uint64_t LeafBits) {
+    uint64_t ConstLeafCnt = llvm::popcount(LeafBits & ConstantLeafs);
+    uint64_t ConstFoldedCnt = ConstLeafCnt > 1 ? ConstLeafCnt - 1 : 0;
+    return llvm::popcount(LeafBits) - 1 - ConstFoldedCnt;
+  };
+
   if (Expr.size() == 1) {
     uint64_t LeafBits = *Expr.begin();
-    unsigned InstCnt = llvm::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))
+    if (Node->worthToCombine(GetInstCnt(LeafBits)))
       return buildAndChain(Builder, Ty, LeafBits);
   }
 
@@ -274,8 +282,8 @@
       if (RHS == 0)
         RHS = LogicalExpr::ExprAllOne;
     }
-    unsigned InstCnt = llvm::popcount(CommonAnd) + llvm::popcount(LHS) +
-                       llvm::popcount(RHS) - 1;
+    unsigned InstCnt =
+        GetInstCnt(CommonAnd) + GetInstCnt(LHS) + GetInstCnt(RHS) + 2;
     if (Node->worthToCombine(InstCnt)) {
       Value *LHSV = buildAndChain(Builder, Ty, LHS);
       Value *RHSV = buildAndChain(Builder, Ty, RHS);
@@ -294,24 +302,34 @@
 Value *LogicalOpsHelper::buildAndChain(IRBuilder<> &Builder, Type *Ty,
                                        uint64_t LeafBits) {
   if (LeafBits == 0)
-    return Constant::getNullValue(Ty);
+    return ConstZero;
 
   // ExprAllOne is not in the LeafValues
   if (LeafBits == LogicalExpr::ExprAllOne)
-    return Constant::getAllOnesValue(Ty);
+    return ConstAllOne;
 
   unsigned LeafCnt = llvm::popcount(LeafBits);
   if (LeafCnt == 1)
     return LeafValues[llvm::Log2_64(LeafBits)];
 
-  unsigned LeafIdx = llvm::countr_zero(LeafBits);
-  Value *AndChain = LeafValues[LeafIdx];
-  LeafBits -= (1ULL << LeafIdx);
-  for (unsigned I = 1; I < LeafCnt; I++) {
-    LeafIdx = llvm::countr_zero(LeafBits);
-    AndChain = Builder.CreateAnd(AndChain, LeafValues[LeafIdx]);
-    LeafBits -= (1ULL << LeafIdx);
-  }
+  Value *AndChain = ConstAllOne;
+  auto CreateAndChain = [this, &Builder, LeafCnt](Value *AndChain,
+                                                  uint64_t LeafBits,
+                                                  bool BuildConst) {
+    unsigned LeafIdx;
+    for (unsigned I = 0; I < LeafCnt; I++) {
+      LeafIdx = llvm::countr_zero(LeafBits);
+      Value *LeafVal = LeafValues[LeafIdx];
+      if (BuildConst == isa<Constant>(LeafVal))
+        AndChain = Builder.CreateAnd(LeafVal, AndChain);
+      LeafBits -= (1ULL << LeafIdx);
+    }
+    return AndChain;
+  };
+
+  if (llvm::popcount(ConstantLeafs) > 1)
+    AndChain = CreateAndChain(AndChain, LeafBits, true);
+  AndChain = CreateAndChain(AndChain, LeafBits, false);
   return AndChain;
 }
 
@@ -322,6 +340,9 @@
   if (RootNode == nullptr)
     return nullptr;
 
+  ConstAllOne = Constant::getAllOnesValue(Root->getType());
+  ConstZero = Constant::getNullValue(Root->getType());
+
   Value *NewRoot = logicalOpToValue(RootNode);
   if (NewRoot == Root)
     return nullptr;
Index: llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll
===================================================================
--- llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll
+++ llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll
@@ -43,6 +43,16 @@
   ret i1 %or
 }
 
+define i8 @leaf1_and_const_fold(i8 %a)  {
+; CHECK-LABEL: @leaf1_and_const_chain(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 15, [[A:%.*]]
+; CHECK-NEXT:    ret i8 [[TMP1]]
+;
+  %and1 = and i8 %a, 111
+  %and2 = and i8 %and1, 31
+  ret i8 %and2
+}
+
 define i1 @leaf2_xor(i1 %a, i1 %b)  {
 ; CHECK-LABEL: @leaf2_xor(
 ; CHECK-NEXT:    ret i1 [[B:%.*]]
@@ -117,6 +127,21 @@
   ret i1 %xor
 }
 
+define i8 @leaf2_ret_const_fold(i8 %a, i8 %b)  {
+; CHECK-LABEL: @leaf4_complex_ret_const(
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[B:%.*]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[A:%.*]], 18
+; CHECK-NEXT:    [[TMP3:%.*]] = and i8 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    ret i8 [[TMP3]]
+;
+  %and1 = and i8 %a, 122
+  %or = or i8 %and1, %b
+  %and2 = and i8 %or, 23
+  %and3 = and i8 %b, 23
+  %r = xor i8 %and2, %and3
+  ret i8 %r
+}
+
 define i1 @leaf3_complex_ret_const_false(i1 %a, i1 %b, i1 %c)  {
 ; CHECK-LABEL: @leaf3_complex_ret_const_false(
 ; CHECK-NEXT:    ret i1 false