[EarlyCSE] Propagate conditions of AND and OR instructions

This patches teaches EarlyCSE to figure out that if `and i1 %x, %y` is true then both
`%x` and `%y` are true in the taken branch, and if `or i1 %x, %y` is false then both
`%x` and `%y` are false in non-taken branch. Fix for PR37635.

Differential Revision: https://reviews.llvm.org/D47574
Reviewed By: reames

llvm-svn: 334707

1 files changed, 43 insertions, 14 deletions

diff --git a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
index a331129e379..80739a02e9f 100644
--- a/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
+++ b/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
@@ -719,22 +719,51 @@ bool EarlyCSE::handleBranchCondition(Instruction *CondInst,
   auto *TorF = (BI->getSuccessor(0) == BB)
                    ? ConstantInt::getTrue(BB->getContext())
                    : ConstantInt::getFalse(BB->getContext());
-  AvailableValues.insert(CondInst, TorF);
-  LLVM_DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
-                    << CondInst->getName() << "' as " << *TorF << " in "
-                    << BB->getName() << "\n");
-  if (!DebugCounter::shouldExecute(CSECounter)) {
-    LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
-  } else {
-    // Replace all dominated uses with the known value.
-    if (unsigned Count = replaceDominatedUsesWith(CondInst, TorF, DT,
-                                                  BasicBlockEdge(Pred, BB))) {
-
-      NumCSECVP += Count;
-      return true;
+  auto IsAnd = [](Instruction *I) {
+    if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(I))
+      return BOp->getOpcode() == Instruction::And;
+    return false;
+  };
+  auto IsOr = [](Instruction *I) {
+    if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(I))
+      return BOp->getOpcode() == Instruction::Or;
+    return false;
+  };
+  // If the condition is AND operation, we can propagate its operands into the
+  // true branch. If it is OR operation, we can propagate them into the false
+  // branch.
+  auto CanPropagateOperands = (BI->getSuccessor(0) == BB) ? IsAnd : IsOr;
+
+  bool MadeChanges = false;
+  SmallVector<Instruction *, 4> WorkList;
+  SmallPtrSet<Instruction *, 4> Visited;
+  WorkList.push_back(CondInst);
+  while (!WorkList.empty()) {
+    Instruction *Curr = WorkList.pop_back_val();
+
+    AvailableValues.insert(Curr, TorF);
+    LLVM_DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
+                      << Curr->getName() << "' as " << *TorF << " in "
+                      << BB->getName() << "\n");
+    if (!DebugCounter::shouldExecute(CSECounter)) {
+      LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
+    } else {
+      // Replace all dominated uses with the known value.
+      if (unsigned Count = replaceDominatedUsesWith(Curr, TorF, DT,
+                                                    BasicBlockEdge(Pred, BB))) {
+        NumCSECVP += Count;
+        MadeChanges = true;
+      }
     }
+
+    if (CanPropagateOperands(Curr))
+      for (auto &Op : cast<BinaryOperator>(Curr)->operands())
+        if (Instruction *OPI = dyn_cast<Instruction>(Op))
+          if (SimpleValue::canHandle(OPI) && Visited.insert(OPI).second)
+            WorkList.push_back(OPI);
   }
-  return false;
+
+  return MadeChanges;
 }
 
 bool EarlyCSE::processNode(DomTreeNode *Node) {