[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/lib/Transforms/AggressiveInstCombine/ComplexLogicalOpsCombine.h

 
 class LogicalOpsHelper;
 
 class LogicalOpNode {
 private:
   LogicalOpsHelper *Helper;
   Value *Val;
   LogicalExpr Expr;
+  unsigned Weight;
+  unsigned OneUseWeight;
   // TODO: Add weight to measure cost for more than one use value
 
   void printValue(raw_ostream &OS, Value *Val) const;
   void printAndChain(raw_ostream &OS, uint64_t Mask) 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; }
+
   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(Instruction *I, uint64_t Mask);
 };
 
 inline raw_ostream &operator<<(raw_ostream &OS, const LogicalOpNode &I) {
   I.print(OS);
   return OS;
 }
 
 } // namespace llvm
 No newline at end of file

llvm/lib/Transforms/AggressiveInstCombine/ComplexLogicalOpsCombine.cpp

 //
 // Reference: https://en.wikipedia.org/wiki/Boolean_ring
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "aggressive-instcombine"
 
 STATISTIC(NumComplexLogicalOpsSimplified,
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 << "Weight: " << Weight << "; NUseWeight: " << 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 = LogicalExpr::ExprZero;
     else if (ConstVal->isAllOnesValue())
       ExprVal = LogicalExpr::ExprAllOne;
   }
   if (ExprVal != LogicalExpr::ExprAllOne && ExprVal != LogicalExpr::ExprZero &&
       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();
+  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) {
   if (Expr.size() == 1) {
     uint64_t ExprMask = *Expr.begin();
     // ExprZero/ExprAllOne is not in the LeafValues
     if (ExprMask == LogicalExpr::ExprZero)
       return Constant::getNullValue(Node->getValue()->getType());
     if (ExprMask == LogicalExpr::ExprAllOne)
       return Constant::getAllOnesValue(Node->getValue()->getType());
 
-    if (llvm::popcount(ExprMask) == 1)
+    unsigned ElementCnt = llvm::popcount(ExprMask);
+    if (ElementCnt == 1)
       return LeafValues[llvm::Log2_64(ExprMask)];
+
+    unsigned InstCnt = 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->getOneUseWeight() + InstCnt) < Node->getWeight())
+      return buildAndChain(cast<Instruction>(Node->getValue()), ExprMask);
+    return nullptr;
   }
 
   // TODO: complex pattern simpilify
 
   return nullptr;
 }
 
+Value *LogicalOpsHelper::buildAndChain(Instruction *I, uint64_t 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::simplify(Value *Root) {
   LogicalOpNode *RootNode = getLogicalOpNode(Root);
   Root = logicalOpToValue(RootNode);
   if (Root != nullptr)
     NumComplexLogicalOpsSimplified++;
   return Root;
 }

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

 if.then:
   tail 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:    [[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 @test5(i1 %a, i1 %b, i1 %c, i1 %d)  {
+; CHECK-LABEL: @test5(
+; 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)