[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/LogicCombine.h

 //===------------------ LogicCombine.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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_LOGICCOMBINE_H
 #define LLVM_ANALYSIS_LOGICCOMBINE_H
 
 #include "LogicalExpr.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
-#include "llvm/IR/InstrTypes.h"
-#include "llvm/IR/Instruction.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/Support/Allocator.h"
 
 namespace llvm {
 
 class LogicCombiner;
 
 class LogicalOpNode {
 private:
   LogicCombiner *Helper;
   Value *Val;
   LogicalExpr Expr;
-  // TODO: Add weight to measure cost for more than one use value
+  unsigned Weight;
+  unsigned OneUseWeight;
+  unsigned ProfitRebuildInstCnt;
 
   void printAndChain(raw_ostream &OS, uint64_t LeafBits) const;
 
 public:
-  LogicalOpNode(LogicCombiner *OpsHelper, Value *SrcVal,
-                const LogicalExpr &SrcExpr)
-      : Helper(OpsHelper), Val(SrcVal), Expr(SrcExpr) {}
+  LogicalOpNode(LogicCombiner *Helper, Value *Val, const LogicalExpr &SrcExpr,
+                unsigned Weight, unsigned OneUseWeight,
+                unsigned ProfitRebuildInstCnt)
+      : Helper(Helper), Val(Val), Expr(SrcExpr), Weight(Weight),
+        OneUseWeight(OneUseWeight), ProfitRebuildInstCnt(ProfitRebuildInstCnt) {
+  }
   ~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 InstCnt < ProfitRebuildInstCnt;
+  }
   void print(raw_ostream &OS) const;
 };
 
 class LogicCombiner {
 public:
   LogicCombiner() {}
   ~LogicCombiner() { clear(); }
 
   Value *simplify(Value *Root);
 
 private:
   friend class LogicalOpNode;
 
   SpecificBumpPtrAllocator<LogicalOpNode> Alloc;
   SmallDenseMap<Value *, LogicalOpNode *, 16> LogicalOpNodes;
   SmallSetVector<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
 
 #endif // LLVM_ANALYSIS_LOGICCOMBINE_H

llvm/lib/Analysis/LogicCombine.cpp

void LogicalOpNode::print(raw_ostream &OS) const {
   }
 
   ListSeparator LS(" + ");
   for (auto I = Expr.begin(); I != Expr.end(); I++) {
     OS << LS;
     printAndChain(OS, *I);
   }
 
-  OS << "\n";
+  OS << "\nWeight: " << Weight << "; OneUseWeight: " << OneUseWeight
+     << "ProfitRebuildInstCnt: " << ProfitRebuildInstCnt << ";\n\n";
 }
 
 void LogicCombiner::clear() {
   LogicalOpNodes.clear();
   LeafValues.clear();
 }
 
 LogicalOpNode *LogicCombiner::visitLeafNode(Value *Val, unsigned Depth) {
   // Depth is 0 means the root is not logical operation. We can't
   // do anything for that.
   if (Depth == 0 || LeafValues.size() >= MaxLogicOpLeafsToScan)
     return nullptr;
 
   uint64_t ExprVal = 1ULL << LeafValues.size();
   // Constant Zero,AllOne are special leaf nodes. They involve
   // LogicalExpr's calculation so we must detect them at first.
   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)
     LeafValues.insert(Val);
-  LogicalOpNode *Node =
-      new (Alloc.Allocate()) LogicalOpNode(this, Val, LogicalExpr(ExprVal));
+  LogicalOpNode *Node = new (Alloc.Allocate())
+      LogicalOpNode(this, Val, LogicalExpr(ExprVal), 0, 0, 0);
   LogicalOpNodes[Val] = Node;
   return Node;
 }
 
 LogicalOpNode *LogicCombiner::visitBinOp(BinaryOperator *BO, unsigned Depth) {
   if (!BO->isBitwiseLogicOp())
     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;
+  unsigned Weight = LHS->getWeight() + RHS->getWeight() + 1;
+  unsigned OneUseWeight = LHS->getOneUseWeight() + RHS->getOneUseWeight();
+  unsigned ProfitRebuildInstCnt = Weight - OneUseWeight;
+  if (!BO->hasOneUse())
+    OneUseWeight = Weight;
+
+  LogicalExpr NewExpr;
   if (BO->getOpcode() == Instruction::And)
-    Node = new (Alloc.Allocate())
-        LogicalOpNode(this, BO, LHS->getExpr() & RHS->getExpr());
+    NewExpr = LHS->getExpr() & RHS->getExpr();
   else if (BO->getOpcode() == Instruction::Or)
-    Node = new (Alloc.Allocate())
-        LogicalOpNode(this, BO, LHS->getExpr() | RHS->getExpr());
+    NewExpr = LHS->getExpr() | RHS->getExpr();
   else
-    Node = new (Alloc.Allocate())
-        LogicalOpNode(this, BO, LHS->getExpr() ^ RHS->getExpr());
+    NewExpr = LHS->getExpr() ^ RHS->getExpr();
+  LogicalOpNode *Node = new (Alloc.Allocate()) LogicalOpNode(
+      this, BO, NewExpr, Weight, OneUseWeight, ProfitRebuildInstCnt);
   LogicalOpNodes[BO] = Node;
   return Node;
 }
 
 LogicalOpNode *LogicCombiner::getLogicalOpNode(Value *Val, unsigned Depth) {
   if (Depth == MaxDepthLogicOpsToScan)
     return nullptr;
 

 }
 
 Value *LogicCombiner::logicalOpToValue(LogicalOpNode *Node) {
   const LogicalExpr &Expr = Node->getExpr();
   // Empty when all leaf bits are erased 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());
-
-    if (popcount(LeafBits) == 1)
-      return LeafValues[Log2_64(LeafBits)];
+    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);
+      return buildAndChain(Builder, Ty, LeafBits);
+    }
   }
 
   // TODO: find the simplest form from logical expression when it is not
   // only an "and" chain.
 
   return nullptr;
 }
 
+Value *LogicCombiner::buildAndChain(IRBuilder<> &Builder, Type *Ty,
+                                    uint64_t LeafBits) {
+  if (LeafBits == 0)
+    return Constant::getNullValue(Ty);
+
+  // ExprAllOne is not in the LeafValues
+  if (LeafBits == LogicalExpr::ExprAllOne)
+    return Constant::getAllOnesValue(Ty);
+
+  unsigned LeafCnt = popcount(LeafBits);
+  if (LeafCnt == 1)
+    return LeafValues[Log2_64(LeafBits)];
+
+  unsigned LeafIdx = countr_zero(LeafBits);
+  Value *AndChain = LeafValues[LeafIdx];
+  LeafBits -= (1ULL << LeafIdx);
+  for (unsigned I = 1; I < LeafCnt; I++) {
+    LeafIdx = countr_zero(LeafBits);
+    AndChain = Builder.CreateAnd(AndChain, LeafValues[LeafIdx]);
+    LeafBits -= (1ULL << LeafIdx);
+  }
+  return AndChain;
+}
+
 Value *LogicCombiner::simplify(Value *Root) {
   assert(MaxLogicOpLeafsToScan <= 63 &&
          "Logical leaf node can't be larger than 63.");
   LogicalOpNode *RootNode = getLogicalOpNode(Root);
   if (RootNode == nullptr)
     return nullptr;
 
   Value *NewRoot = logicalOpToValue(RootNode);
   if (NewRoot == nullptr || NewRoot == Root)
     return nullptr;
 
   LogicalOpNodes.erase(Root);
   NumLogicalOpsSimplified++;
   return NewRoot;
 }

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

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