[LogicCombine 3/?] Add i1 select instruction support

[bcl5980]

Summary

This patch involve "select" into complex logic combine.
And it trace the poison mismatch comes from "select" to make sure the transform is poison safe.

[bcl5980]

rebase

[bcl5980]

rebase

[bcl5980]

rebase

llvm/include/llvm/Analysis/LogicCombine.h

 class LogicalOpNode {
 private:
   LogicCombiner *Helper;
   Value *Val;
   LogicalExpr Expr;
   unsigned Weight;
   unsigned OneUseWeight;
   unsigned ProfitRebuildInstCnt;
+  uint64_t PoisonMaskSI; // Record Poison from Select Inst True/False Value
 
   void printAndChain(raw_ostream &OS, uint64_t LeafBits) const;
 
 public:
   LogicalOpNode(LogicCombiner *Helper, Value *Val, const LogicalExpr &SrcExpr,
                 unsigned Weight, unsigned OneUseWeight,
-                unsigned ProfitRebuildInstCnt)
+                unsigned ProfitRebuildInstCnt, uint64_t PoisonMaskSI)
       : Helper(Helper), Val(Val), Expr(SrcExpr), Weight(Weight),
-        OneUseWeight(OneUseWeight), ProfitRebuildInstCnt(ProfitRebuildInstCnt) {
-  }
+        OneUseWeight(OneUseWeight), ProfitRebuildInstCnt(ProfitRebuildInstCnt),
+        PoisonMaskSI(PoisonMaskSI) {}
   ~LogicalOpNode() {}
 
   Value *getValue() const { return Val; }
   const LogicalExpr &getExpr() const { return Expr; }
   unsigned getWeight() const { return Weight; }
   unsigned getOneUseWeight() const { return OneUseWeight; }
+  uint64_t getPoisonMaskSI() const { return PoisonMaskSI; }
 
   bool worthToCombine(unsigned InstCnt) const {
     return InstCnt < ProfitRebuildInstCnt;
   }
   void print(raw_ostream &OS) const;
 };
 
 class LogicCombiner {
 public:
-  LogicCombiner() {}
+  LogicCombiner() : LogicalOpNodes(), LeafValues(), LeafsMayPoison() {}
   ~LogicCombiner() { clear(); }
 
   Value *simplify(Value *Root);
 
 private:
   friend class LogicalOpNode;
 
   SpecificBumpPtrAllocator<LogicalOpNode> Alloc;
   SmallDenseMap<Value *, LogicalOpNode *, 16> LogicalOpNodes;
   SmallSetVector<Value *, 8> LeafValues;
+  uint64_t LeafsMayPoison;
 
   void clear();
 
   LogicalOpNode *visitLeafNode(Value *Val, unsigned Depth);
   LogicalOpNode *visitBinOp(BinaryOperator *BO, unsigned Depth);
+  LogicalOpNode *visitSelect(SelectInst *SI, 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/include/llvm/Analysis/LogicalExpr.h

 
 namespace llvm {
 // TODO: can we use APInt define the mask to enlarge the max leaf number?
 typedef SmallDenseSet<uint64_t, 8> ExprAddChain;
 
 class LogicalExpr {
 private:
   ExprAddChain AddChain;
+  uint64_t LeafMask;
+
+  void updateLeafMask() {
+    LeafMask = 0;
+    for (auto BitSet : AddChain)
+      LeafMask |= BitSet;
+  }
 
 public:
   static const uint64_t ExprAllOne = 0x8000000000000000;
 
   LogicalExpr() {}
   LogicalExpr(uint64_t BitSet) {
     if (BitSet != 0)
       AddChain.insert(BitSet);
+    LeafMask = BitSet;
   }
   LogicalExpr(const ExprAddChain &SrcAddChain) : AddChain(SrcAddChain) {
+    updateLeafMask();
   }
 
   unsigned size() const { return AddChain.size(); }
+  uint64_t getLeafMask() const { return LeafMask; }
+
   ExprAddChain::iterator begin() { return AddChain.begin(); }
   ExprAddChain::iterator end() { return AddChain.end(); }
   ExprAddChain::const_iterator begin() const { return AddChain.begin(); }
   ExprAddChain::const_iterator end() const { return AddChain.end(); }
 
   LogicalExpr &operator*=(const LogicalExpr &RHS) {
     ExprAddChain NewChain;
     for (auto LHS : AddChain) {
for (auto LHS : AddChain) {
         // a ^ a -> 0
         auto InsertPair = NewChain.insert(NewBitSet);
         if (!InsertPair.second)
           NewChain.erase(InsertPair.first);
       }
     }
 
     AddChain = NewChain;
+    updateLeafMask();
     return *this;
   }
 
   LogicalExpr &operator+=(const LogicalExpr &RHS) {
     for (auto RHS : RHS.AddChain) {
       // a ^ a -> 0
       auto InsertPair = AddChain.insert(RHS);
       if (!InsertPair.second)
         AddChain.erase(InsertPair.first);
     }
+    updateLeafMask();
     return *this;
   }
 };
 
 inline LogicalExpr operator*(LogicalExpr a, const LogicalExpr &b) {
   a *= b;
   return a;
 }

llvm/lib/Analysis/LogicCombine.cpp

 ///
 /// Reference: https://en.wikipedia.org/wiki/Boolean_ring
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LogicCombine.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "logic-combine"
 
void LogicalOpNode::print(raw_ostream &OS) const {
 
   ListSeparator LS(" + ");
   for (auto I = Expr.begin(); I != Expr.end(); I++) {
     OS << LS;
     printAndChain(OS, *I);
   }
 
   OS << "\nWeight: " << Weight << "; OneUseWeight: " << OneUseWeight
-     << "ProfitRebuildInstCnt: " << ProfitRebuildInstCnt << ";\n\n";
+     << "ProfitRebuildInstCnt: " << ProfitRebuildInstCnt << ";\n";
+  OS << "PoisonSrc: 0x"
+     << Twine::utohexstr(Expr.getLeafMask() & Helper->LeafsMayPoison)
+     << "; PoisonMaskSI: 0x" << Twine::utohexstr(PoisonMaskSI) << ";\n\n";
 }
 
 void LogicCombiner::clear() {
+  LeafsMayPoison = 0;
   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)
+  if (ExprVal != LogicalExpr::ExprAllOne && ExprVal != 0) {
+    if (!isGuaranteedNotToBeUndefOrPoison(Val))
+      LeafsMayPoison |= ExprVal;
     LeafValues.insert(Val);
+  }
   LogicalOpNode *Node = new (Alloc.Allocate())
-      LogicalOpNode(this, Val, LogicalExpr(ExprVal), 0, 0, 0);
+      LogicalOpNode(this, Val, LogicalExpr(ExprVal), 0, 0, 0, 0);
   LogicalOpNodes[Val] = Node;
   return Node;
 }
 
 LogicalOpNode *LogicCombiner::visitBinOp(BinaryOperator *BO, unsigned Depth) {
   if (!BO->isBitwiseLogicOp())
     return visitLeafNode(BO, Depth);
 
LogicalOpNode *LogicCombiner::visitBinOp(BinaryOperator *BO, unsigned Depth) {
 
   LogicalExpr NewExpr;
   if (BO->getOpcode() == Instruction::And)
     NewExpr = LHS->getExpr() & RHS->getExpr();
   else if (BO->getOpcode() == Instruction::Or)
     NewExpr = LHS->getExpr() | RHS->getExpr();
   else
     NewExpr = LHS->getExpr() ^ RHS->getExpr();
-  LogicalOpNode *Node = new (Alloc.Allocate()) LogicalOpNode(
-      this, BO, NewExpr, Weight, OneUseWeight, ProfitRebuildInstCnt);
+
+  uint64_t PoisonMaskSI = 0;
+  uint64_t LPI = LHS->getExpr().getLeafMask() ^ LHS->getPoisonMaskSI();
+  uint64_t RPI = RHS->getExpr().getLeafMask() ^ RHS->getPoisonMaskSI();
+  PoisonMaskSI =
+      ((~LPI) & RHS->getPoisonMaskSI()) | ((~RPI) & LHS->getPoisonMaskSI());
+  PoisonMaskSI &= NewExpr.getLeafMask() & LeafsMayPoison;
+
+  LogicalOpNode *Node = new (Alloc.Allocate())
+      LogicalOpNode(this, BO, NewExpr, Weight, OneUseWeight,
+                    ProfitRebuildInstCnt, PoisonMaskSI);
   LogicalOpNodes[BO] = Node;
   return Node;
 }
 
+LogicalOpNode *LogicCombiner::visitSelect(SelectInst *SI, unsigned Depth) {
+  if (!SI->getType()->isIntOrIntVectorTy(1))
+    return nullptr;
+
+  LogicalOpNode *Cond = getLogicalOpNode(SI->getCondition(), Depth + 1);
+  if (Cond == nullptr)
+    return nullptr;
+
+  LogicalOpNode *TrueVal = getLogicalOpNode(SI->getTrueValue(), Depth + 1);
+  if (TrueVal == nullptr)
+    return nullptr;
+
+  LogicalOpNode *FalseVal = getLogicalOpNode(SI->getFalseValue(), Depth + 1);
+  if (FalseVal == nullptr)
+    return nullptr;
+
+  LogicalExpr NewExpr = (Cond->getExpr() & TrueVal->getExpr()) ^
+                        ((~Cond->getExpr()) & FalseVal->getExpr());
+  unsigned Weight =
+      Cond->getWeight() + TrueVal->getWeight() + FalseVal->getWeight() + 1;
+  unsigned OneUseWeight = Cond->getOneUseWeight() + TrueVal->getOneUseWeight() +
+                          FalseVal->getOneUseWeight();
+  unsigned ProfitRebuildInstCnt = Weight - OneUseWeight;
+  if (!SI->hasOneUse())
+    OneUseWeight = Weight;
+
+  uint64_t PoisonMaskSI = NewExpr.getLeafMask() & LeafsMayPoison;
+  PoisonMaskSI &=
+      TrueVal->getExpr().getLeafMask() | FalseVal->getExpr().getLeafMask();
+
+  LogicalOpNode *Node = new (Alloc.Allocate())
+      LogicalOpNode(this, SI, NewExpr, Weight, OneUseWeight,
+                    ProfitRebuildInstCnt, PoisonMaskSI);
+  LogicalOpNodes[SI] = Node;
+  return Node;
+}
+
 LogicalOpNode *LogicCombiner::getLogicalOpNode(Value *Val, unsigned Depth) {
   if (Depth == MaxDepthLogicOpsToScan)
     return nullptr;
 
   if (LogicalOpNodes.find(Val) == LogicalOpNodes.end()) {
     LogicalOpNode *Node;
 
     // TODO: add select instruction support
     if (auto *BO = dyn_cast<BinaryOperator>(Val))
       Node = visitBinOp(BO, Depth);
+    else if (auto *SI = dyn_cast<SelectInst>(Val))
+      Node = visitSelect(SI, Depth);
     else
       Node = visitLeafNode(Val, Depth);
 
     if (!Node)
       return nullptr;
     LLVM_DEBUG(dbgs() << *Node);
   }
   return LogicalOpNodes[Val];
 }
 
 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());
 
+  if (Node->getPoisonMaskSI() != 0)
+    return nullptr;
+
   Instruction *I = cast<Instruction>(Node->getValue());
   Type *Ty = I->getType();
   if (Expr.size() == 1) {
     uint64_t LeafBits = *Expr.begin();
     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)) {

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

 ;
   %ab = and i32 %a, %b
   %bc = and i32 %b, %c
   call void @use32(i32 %bc)
   %abbc = and i32 %ab, %bc
   ret i32 %abbc
 }
 
+define i1 @leaf3_select_ret_and(i1 %a, i1 %b, i1 noundef %c) {
+; CHECK-LABEL: @leaf3_select_ret_and(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[A:%.*]], [[C:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+  %ab = and i1 %a, %b
+  %si = select i1 %a, i1 %c, i1 %b
+  %xor2 = xor i1 %si, %b
+  %cond = xor i1 %xor2, %ab
+  ret i1 %cond
+}
+
+define i1 @leaf3_select_ret_and2(i1 %a, i1 %b, i1 %c) {
+; CHECK-LABEL: @leaf3_select_ret_and2(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+  %ac = and i1 %a, %c
+  %si = select i1 %a, i1 %c, i1 %b
+  %xor2 = xor i1 %si, %b
+  %cond = xor i1 %xor2, %ac
+  ret i1 %cond
+}
+
+define i1 @leaf3_select_ret_leaf(i1 %a, i1 %b, i1 %c) {
+; CHECK-LABEL: @leaf3_select_ret_leaf(
+; CHECK-NEXT:    ret i1 [[B:%.*]]
+;
+  %ab = and i1 %a, %b
+  %ac = and i1 %a, %c
+  %si = select i1 %a, i1 %c, i1 %b
+  %xor2 = xor i1 %si, %ab
+  %cond = xor i1 %xor2, %ac
+  ret i1 %cond
+}
+
+; negative test, may have poison
+
+define i1 @leaf3_select_undef_ret_and(i1 %a, i1 %b, i1 %c) {
+; CHECK-LABEL: @leaf3_select_undef_ret_and(
+; CHECK-NEXT:    [[AB:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[SI:%.*]] = select i1 [[A]], i1 [[C:%.*]], i1 [[B]]
+; CHECK-NEXT:    [[XOR2:%.*]] = xor i1 [[SI]], [[B]]
+; CHECK-NEXT:    [[COND:%.*]] = xor i1 [[XOR2]], [[AB]]
+; CHECK-NEXT:    ret i1 [[COND]]
+;
+  %ab = and i1 %a, %b
+  %si = select i1 %a, i1 %c, i1 %b
+  %xor2 = xor i1 %si, %b
+  %cond = xor i1 %xor2, %ab
+  ret i1 %cond
+}
+
 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
;
   %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
 }
 
+define i1 @leaf4_select_noundef_complex_ret_leaf(i1 noundef %a, i1 %b, i1 %c, i1 %d)  {
+; CHECK-LABEL: @leaf4_select_noundef_complex_ret_leaf(
+; CHECK-NEXT:    ret i1 [[A:%.*]]
+;
+  %bd = select i1 %d, i1 %b, i1 false
+  %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, %a
+  ret i1 %and
+}
+
+define i1 @leaf4_select_noundef_complex_ret_and(i1 %a, i1 %b, i1 %c, i1 noundef %d) {
+; CHECK-LABEL: @leaf4_select_noundef_complex_ret_and(
+; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[B:%.*]], [[D:%.*]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+  %ab = and i1 %a, %b
+  %bc = and i1 %b, %c
+  %xor.ac = xor i1 %a, %c
+  %or = or i1 %ab, %xor.ac
+  %not.bc = xor i1 %bc, true
+  %and = and i1 %not.bc, %a
+  %xor = xor i1 %and, %or
+  %si = select i1 %b, i1 %d, i1 %xor
+  %xor2 = xor i1 %si, %c
+  %cond = xor i1 %xor2, %bc
+  ret i1 %cond
+}
+
+define i1 @leaf4_select_poison_masked_complex_ret_leaf(i1 %a, i1 %b, i1 %c, i1 %d)  {
+; CHECK-LABEL: @leaf4_select_poison_masked_complex_ret_leaf(
+; CHECK-NEXT:    ret i1 [[A:%.*]]
+;
+  %bd = select i1 %d, i1 %b, i1 false
+  %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, %a
+  ret i1 %and
+}
+
+define i1 @leaf4_select_poison_masked_complex_ret_leaf2(i1 %a, i1 %b, i1 %c)  {
+; CHECK-LABEL: @leaf4_select_poison_masked_complex_ret_leaf2(
+; CHECK-NEXT:    ret i1 [[A:%.*]]
+;
+  %not.a = xor i1 %a, true
+  %or1 = or i1 %not.a, %b
+  %or2 = or i1 %or1, %c
+  %xor = xor i1 %or2, %a
+  %or3 = or i1 %not.a, %c
+  %or4 = select i1 %or3, i1 true, i1 %b
+  %cond = xor i1 %xor, %or4
+  ret i1 %cond
+}
+
 declare void @use8(i8)
 declare void @use32(i32)