[LogicCombine 2/?] Add weight into node then use it to determine if we can combine the case need to create new value.

[bcl5980]

Summary

In this patch we involve two member variables into logical node: Weight , OneUseWeight.
Weight maintain how many instructions can we get the value based on original IR code.
OneUseWeightmeans if we rebuild the final instruction, how many instructions we need to keep for the child node without one-use.
After that we can measure the cost if we rebuild the instruction.

[bcl5980]

rebase

[bcl5980]

rebase code

[bcl5980]

rebase

[bcl5980]

Ping.

llvm/include/llvm/Analysis/ComplexLogicCombine.h

 //===----------- ComplexLogicCombine.h --------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "LogicalExpr.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
-#include "llvm/IR/InstrTypes.h"
-#include "llvm/IR/Instruction.h"
+#include "llvm/IR/IRBuilder.h"
 
 namespace llvm {
 
 class LogicalOpsHelper;
 
 class LogicalOpNode {
 private:
   LogicalOpsHelper *Helper;
   Value *Val;
   LogicalExpr Expr;
-  // TODO: Add weight to measure cost for more than one use value
+  unsigned Weight;
+  unsigned OneUseWeight;
 
   void printValue(raw_ostream &OS, Value *Val) const;
   void printAndChain(raw_ostream &OS, uint64_t LeafBits) const;
 
 public:
-  LogicalOpNode(LogicalOpsHelper *OpsHelper, Value *SrcVal,
-                const LogicalExpr &SrcExpr)
-      : Helper(OpsHelper), Val(SrcVal), Expr(SrcExpr) {}
+  LogicalOpNode(LogicalOpsHelper *Helper, Value *Val,
+                const LogicalExpr &SrcExpr, unsigned Weight,
+                unsigned OneUseWeight)
+      : Helper(Helper), Val(Val), Expr(SrcExpr), Weight(Weight),
+        OneUseWeight(OneUseWeight) {}
   ~LogicalOpNode() {}
 
   Value *getValue() const { return Val; }
   const LogicalExpr &getExpr() const { return Expr; }
+  unsigned getWeight() const { return Weight; }
+  unsigned getOneUseWeight() const { return OneUseWeight; }
+
+  bool worthToCombine(unsigned InstCnt) const {
+    return (OneUseWeight + InstCnt) < Weight;
+  }
   void print(raw_ostream &OS) const;
 };
 
 class LogicalOpsHelper {
 public:
   LogicalOpsHelper() {}
   ~LogicalOpsHelper() { clear(); }
 
   Value *simplify(Value *Root);
 
 private:
   friend class LogicalOpNode;
 
   SmallDenseMap<Value *, LogicalOpNode *, 16> LogicalOpNodes;
   SmallPtrSet<Value *, 8> LeafSet;
   SmallVector<Value *, 8> LeafValues;
 
   void clear();
 
   LogicalOpNode *visitLeafNode(Value *Val, unsigned Depth);
   LogicalOpNode *visitBinOp(BinaryOperator *BO, unsigned Depth);
   LogicalOpNode *getLogicalOpNode(Value *Val, unsigned Depth = 0);
   Value *logicalOpToValue(LogicalOpNode *Node);
+  Value *buildAndChain(IRBuilder<> &Builder, Type *Ty, uint64_t LeafBits);
 };
 
 inline raw_ostream &operator<<(raw_ostream &OS, const LogicalOpNode &I) {
   I.print(OS);
   return OS;
 }
 
 } // namespace llvm

llvm/lib/Analysis/ComplexLogicCombine.cpp

void LogicalOpNode::print(raw_ostream &OS) const {
   }
 
   for (auto I = ++Expr.begin(); I != Expr.end(); I++) {
     printAndChain(OS, *I);
     OS << " + ";
   }
 
   printAndChain(OS, *Expr.begin());
-  OS << "\n";
+  OS << "\nWeight: " << Weight << "; OneUseWeight: " << OneUseWeight << ";\n\n";
 }
 
 void LogicalOpsHelper::clear() {
   for (auto node : LogicalOpNodes)
     delete node.second;
   LogicalOpNodes.clear();
   LeafSet.clear();
   LeafValues.clear();
if (auto ConstVal = dyn_cast<ConstantInt>(Val)) {
     if (ConstVal->isZero())
       ExprVal = 0;
     else if (ConstVal->isAllOnesValue())
       ExprVal = LogicalExpr::ExprAllOne;
   }
   if (ExprVal != LogicalExpr::ExprAllOne && ExprVal != 0 &&
       LeafSet.insert(Val).second)
     LeafValues.push_back(Val);
-  LogicalOpNode *Node = new LogicalOpNode(this, Val, LogicalExpr(ExprVal));
+  LogicalOpNode *Node =
+      new LogicalOpNode(this, Val, LogicalExpr(ExprVal), 0, 0);
   LogicalOpNodes[Val] = Node;
   return Node;
 }
 
 LogicalOpNode *LogicalOpsHelper::visitBinOp(BinaryOperator *BO,
                                             unsigned Depth) {
   // We can only to simpilfy and, or , xor in the binary operator
   if (BO->getOpcode() != Instruction::And &&
       BO->getOpcode() != Instruction::Or && BO->getOpcode() != Instruction::Xor)
     return visitLeafNode(BO, Depth);
 
   LogicalOpNode *LHS = getLogicalOpNode(BO->getOperand(0), Depth + 1);
   if (LHS == nullptr)
     return nullptr;
 
   LogicalOpNode *RHS = getLogicalOpNode(BO->getOperand(1), Depth + 1);
   if (RHS == nullptr)
     return nullptr;
 
-  LogicalOpNode *Node;
+  // TODO: We can reduce the weight if th node can be simplified even if
+  // it is not the root node.
+  unsigned Weight = LHS->getWeight() + RHS->getWeight() + 1;
+  unsigned OneUseWeight = Weight;
+  if (BO->hasOneUse())
+    OneUseWeight = LHS->getOneUseWeight() + RHS->getOneUseWeight();
+
+  LogicalExpr NewExpr;
   if (BO->getOpcode() == Instruction::And)
-    Node = new LogicalOpNode(this, BO, LHS->getExpr() & RHS->getExpr());
+    NewExpr = LHS->getExpr() & RHS->getExpr();
   else if (BO->getOpcode() == Instruction::Or)
-    Node = new LogicalOpNode(this, BO, LHS->getExpr() | RHS->getExpr());
+    NewExpr = LHS->getExpr() | RHS->getExpr();
   else
-    Node = new LogicalOpNode(this, BO, LHS->getExpr() ^ RHS->getExpr());
+    NewExpr = LHS->getExpr() ^ RHS->getExpr();
+  LogicalOpNode *Node =
+      new LogicalOpNode(this, BO, NewExpr, Weight, OneUseWeight);
   LogicalOpNodes[BO] = Node;
   return Node;
 }
 
 LogicalOpNode *LogicalOpsHelper::getLogicalOpNode(Value *Val, unsigned Depth) {
   if (Depth == MaxDepthLogicOpsToScan)
     return nullptr;
 

 }
 
 Value *LogicalOpsHelper::logicalOpToValue(LogicalOpNode *Node) {
   const LogicalExpr &Expr = Node->getExpr();
   // Empty when all leaf bits are earsed from the set because a ^ a = 0.
   if (Expr.size() == 0)
     return Constant::getNullValue(Node->getValue()->getType());
 
+  Instruction *I = cast<Instruction>(Node->getValue());
+  Type *Ty = I->getType();
   if (Expr.size() == 1) {
     uint64_t LeafBits = *Expr.begin();
-    if (LeafBits == 0)
-      return Constant::getNullValue(Node->getValue()->getType());
-    // ExprAllOne is not in the LeafValues
-    if (LeafBits == LogicalExpr::ExprAllOne)
-      return Constant::getAllOnesValue(Node->getValue()->getType());
+    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)) {
+      IRBuilder<> Builder(I);
+      return buildAndChain(Builder, Ty, LeafBits);
+    }
+  }
+  // TODO: complex pattern simpilify
+
+  return nullptr;
+}
+
+Value *LogicalOpsHelper::buildAndChain(IRBuilder<> &Builder, Type *Ty,
+                                       uint64_t LeafBits) {
+    return Constant::getNullValue(Ty);
+
+    return Constant::getAllOnesValue(Ty);
 
-    if (llvm::popcount(LeafBits) == 1)
-      return LeafValues[llvm::Log2_64(LeafBits)];
-  }
+  unsigned LeafCnt = llvm::popcount(LeafBits);
+  if (LeafCnt == 1)
 
-  // TODO: complex pattern simpilify
-
-  return nullptr;
+  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);
+  }
+  return AndChain;
 }
 
 Value *LogicalOpsHelper::simplify(Value *Root) {
   assert(MaxLogicOpLeafsToScan <= 63 &&
          "Logical leaf node can't larger than 63.");
   LogicalOpNode *RootNode = getLogicalOpNode(Root);
   if (RootNode == nullptr)
     return nullptr;

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

 ;
   %xor.ab = xor i4 %a, %b
   %not.a = xor i4 %a, -1
   %xor2 = xor i4 %not.a, %b
   %or = or i4 %xor2, %xor.ab
   ret i4 %or
 }
 
+define i1 @leaf2_ret_and(i1 %a, i1 %b)  {
+; CHECK-LABEL: @leaf2_ret_and(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+  %ab = and i1 %a, %b
+  %and.ab.a = and i1 %ab, %a
+  ret i1 %and.ab.a
+}
+
 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
 ;
   %ab = or i1 %a, %b
   %abc = or i1 %ab, %c
   %not.abc = xor i1 %abc, true
   %r = and i1 %not.abc, %a
;
   %xor.ac = xor i1 %a, %c
   %or = or i1 %ab, %xor.ac
   %not.bc = xor i1 %bc, true
   %and = and i1 %not.bc, %a
   %cond = xor i1 %and, %or
   ret i1 %cond
 }
 
+define i1 @leaf3_ret_and_chain(i1 %a, i1 %b, i1 %c)  {
+; CHECK-LABEL: @leaf3_ret_and_chain(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP1]], [[C:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP2]]
+;
+  %ab = and i1 %a, %b
+  %abc = and i1 %ab, %c
+  %aabc = and i1 %abc, %a
+  %aabcc = and i1 %aabc, %c
+  ret i1 %aabcc
+}
+
+; negative test, extra use cost is equal than it can save
+
+define i1 @leaf3_ret_and_chain_extra_use(i1 %a, i1 %b, i1 %c)  {
+; CHECK-LABEL: @leaf3_ret_and_chain_extra_use(
+; CHECK-NEXT:    [[AB:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[BC:%.*]] = and i1 [[B]], [[C:%.*]]
+; CHECK-NEXT:    call void @use1(i1 [[BC]])
+; CHECK-NEXT:    [[ABBC:%.*]] = and i1 [[AB]], [[BC]]
+; CHECK-NEXT:    ret i1 [[ABBC]]
+;
+  %ab = and i1 %a, %b
+  %bc = and i1 %b, %c
+  call void @use1(i1 %bc)
+  %abbc = and i1 %ab, %bc
+  ret i1 %abbc
+}
+
 define i1 @leaf4_ret_const_true(i1 %a, i1 %b, i1 %c, i1 %d)  {
 ; CHECK-LABEL: @leaf4_ret_const_true(
 ; CHECK-NEXT:    ret i1 true
 ;
   %bd = and i1 %b, %d
   %not.bd = xor i1 %bd, true
   %xor.ab = xor i1 %a, %b
   %or1 = or i1 %xor.ab, %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
   ret i1 %and
 }
+
+define i1 @leaf4_complex_ret_and_chain(i1 %a, i1 %b, i1 %c, i1 %d)  {
+; CHECK-LABEL: @leaf4_complex_ret_and_chain(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[B:%.*]], [[D:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+  %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
+  ret i1 %and2
+}
+
+define i1 @leaf4_complex_ret_and_chain_extra_use(i1 %a, i1 %b, i1 %c, i1 %d)  {
+; CHECK-LABEL: @leaf4_complex_ret_and_chain_extra_use(
+; 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:    ret i1 [[TMP1]]
+;
+  %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)
+  ret i1 %and2
+}
+
+declare void @use1(i1)