[ValueTracking] Improve isImpliedCondition for conditions with matching operands.

This patch improves SimplifyCFG to catch cases like:

  if (a < b) {
    if (a > b) <- known to be false
      unreachable;
  }

Phabricator Revision: http://reviews.llvm.org/D18905

llvm-svn: 266767

4 files changed, 121 insertions, 16 deletions

diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
index cefa18712dd..ca3ab1058a8 100644
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -2131,14 +2131,16 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
       if (match(RHS, m_Zero()))
         return LHS;
       break;
-    case ICmpInst::ICMP_UGE:
+    case ICmpInst::ICMP_UGE: {
       // X >=u 1 -> X
       if (match(RHS, m_One()))
         return LHS;
-      if (isImpliedCondition(RHS, LHS, Q.DL))
+      bool ImpliedTrue;
+      if (isImpliedCondition(RHS, LHS, ImpliedTrue, Q.DL) && ImpliedTrue)
         return getTrue(ITy);
       break;
-    case ICmpInst::ICMP_SGE:
+    }
+    case ICmpInst::ICMP_SGE: {
       /// For signed comparison, the values for an i1 are 0 and -1
       /// respectively. This maps into a truth table of:
       /// LHS | RHS | LHS >=s RHS   | LHS implies RHS
@@ -2146,9 +2148,11 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
       ///  0  |  1  |  1 (0 >= -1)  |  1
       ///  1  |  0  |  0 (-1 >= 0)  |  0
       ///  1  |  1  |  1 (-1 >= -1) |  1
-      if (isImpliedCondition(LHS, RHS, Q.DL))
+      bool ImpliedTrue;
+      if (isImpliedCondition(LHS, RHS, ImpliedTrue, Q.DL) && ImpliedTrue)
         return getTrue(ITy);
       break;
+    }
     case ICmpInst::ICMP_SLT:
       // X <s 0 -> X
       if (match(RHS, m_Zero()))
@@ -2159,11 +2163,13 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
       if (match(RHS, m_One()))
         return LHS;
       break;
-    case ICmpInst::ICMP_ULE:
-      if (isImpliedCondition(LHS, RHS, Q.DL))
+    case ICmpInst::ICMP_ULE: {
+      bool ImpliedTrue;
+      if (isImpliedCondition(LHS, RHS, ImpliedTrue, Q.DL) && ImpliedTrue)
         return getTrue(ITy);
       break;
     }
+    }
   }
 
   // If we are comparing with zero then try hard since this is a common case.
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index 55aa24dab18..bea414a34b3 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -3788,16 +3788,104 @@ static bool isImpliedCondOperands(CmpInst::Predicate Pred, Value *ALHS,
   }
 }
 
-bool llvm::isImpliedCondition(Value *LHS, Value *RHS, const DataLayout &DL,
-                              unsigned Depth, AssumptionCache *AC,
-                              const Instruction *CxtI,
+/// Return true if "icmp2 BPred BLHS BRHS" is known to be implied by "icmp1
+/// APred ALHS ARHS".  The implication may be either true or false depending on
+/// the return value of ImpliedTrue.
+static bool isImpliedCondMatchingOperands(CmpInst::Predicate APred, Value *ALHS,
+                                          Value *ARHS, CmpInst::Predicate BPred,
+                                          Value *BLHS, Value *BRHS,
+                                          bool &ImpliedTrue) {
+  // The operands of the two compares must match.
+  bool IsMatchingOps = (ALHS == BLHS && ARHS == BRHS);
+  bool IsSwappedOps = (ALHS == BRHS && ARHS == BLHS);
+  if (!IsMatchingOps && !IsSwappedOps)
+    return false;
+
+  // Canonicalize the operands so they're matching.
+  if (IsSwappedOps) {
+    std::swap(BLHS, BRHS);
+    BPred = ICmpInst::getSwappedPredicate(BPred);
+  }
+
+  // If the predicates match, then we know the first condition implies the
+  // second is true.
+  if (APred == BPred) {
+    ImpliedTrue = true;
+    return true;
+  }
+
+  // If an inverted APred matches BPred, we can infer the second condition is
+  // false.
+  if (CmpInst::getInversePredicate(APred) == BPred) {
+    ImpliedTrue = false;
+    return true;
+  }
+
+  // If a swapped APred matches BPred, we can infer the second condition is
+  // false in many cases.
+  if (CmpInst::getSwappedPredicate(APred) == BPred) {
+    switch (APred) {
+    default:
+      break;
+    case CmpInst::ICMP_UGT: // A >u B implies A <u B is false.
+    case CmpInst::ICMP_ULT: // A <u B implies A >u B is false.
+    case CmpInst::ICMP_SGT: // A >s B implies A <s B is false.
+    case CmpInst::ICMP_SLT: // A <s B implies A >s B is false.
+      ImpliedTrue = false;
+      return true;
+    }
+  }
+
+  // The predicates must match sign or at least one of them must be an equality
+  // comparison (which is signless).
+  if (ICmpInst::isSigned(APred) != ICmpInst::isSigned(BPred) &&
+      !ICmpInst::isEquality(APred) && !ICmpInst::isEquality(BPred))
+    return false;
+
+  switch (APred) {
+  default:
+    break;
+  case CmpInst::ICMP_EQ:
+    // A == B implies A > B and A < B are false.
+    if (CmpInst::isFalseWhenEqual(BPred)) {
+      ImpliedTrue = false;
+      return true;
+    }
+    break;
+  case CmpInst::ICMP_UGT:
+  case CmpInst::ICMP_ULT:
+  case CmpInst::ICMP_SGT:
+  case CmpInst::ICMP_SLT:
+    // A > B implies A == B is false.
+    // A < B implies A == B is false.
+    if (BPred == CmpInst::ICMP_EQ) {
+      ImpliedTrue = false;
+      return true;
+    }
+    // A > B implies A != B is true.
+    // A < B implies A != B is true.
+    if (BPred == CmpInst::ICMP_NE) {
+      ImpliedTrue = true;
+      return true;
+    }
+    break;
+  }
+  return false;
+}
+
+bool llvm::isImpliedCondition(Value *LHS, Value *RHS, bool &ImpliedTrue,
+                              const DataLayout &DL, unsigned Depth,
+                              AssumptionCache *AC, const Instruction *CxtI,
                               const DominatorTree *DT) {
   assert(LHS->getType() == RHS->getType() && "mismatched type");
   Type *OpTy = LHS->getType();
   assert(OpTy->getScalarType()->isIntegerTy(1));
 
   // LHS ==> RHS by definition
-  if (LHS == RHS) return true;
+  if (LHS == RHS) {
+    ImpliedTrue = true;
+    return true;
+  }
 
   if (OpTy->isVectorTy())
     // TODO: extending the code below to handle vectors
@@ -3812,9 +3900,15 @@ bool llvm::isImpliedCondition(Value *LHS, Value *RHS, const DataLayout &DL,
       !match(RHS, m_ICmp(BPred, m_Value(BLHS), m_Value(BRHS))))
     return false;
 
-  if (APred == BPred)
+  if (isImpliedCondMatchingOperands(APred, ALHS, ARHS, BPred, BLHS, BRHS,
+                                    ImpliedTrue))
+    return true;
+
+  if (APred == BPred) {
+    ImpliedTrue = true;
     return isImpliedCondOperands(APred, ALHS, ARHS, BLHS, BRHS, DL, Depth, AC,
                                  CxtI, DT);
+  }
 
   return false;
 }
diff --git a/llvm/lib/Transforms/Scalar/JumpThreading.cpp b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
index 2def0b54c6d..d68dd140a80 100644
--- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp
+++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp
@@ -928,9 +928,10 @@ bool JumpThreading::ProcessImpliedCondition(BasicBlock *BB) {
     if (!PBI || !PBI->isConditional() || PBI->getSuccessor(0) != CurrentBB)
       return false;
 
-    if (isImpliedCondition(PBI->getCondition(), Cond, DL)) {
-      BI->getSuccessor(1)->removePredecessor(BB);
-      BranchInst::Create(BI->getSuccessor(0), BI);
+    bool ImpliedTrue;
+    if (isImpliedCondition(PBI->getCondition(), Cond, ImpliedTrue, DL)) {
+      BI->getSuccessor(ImpliedTrue ? 1 : 0)->removePredecessor(BB);
+      BranchInst::Create(BI->getSuccessor(ImpliedTrue ? 0 : 1), BI);
       BI->eraseFromParent();
       return true;
     }
diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index 1c27bc67cfb..4976893ad51 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -2722,13 +2722,17 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
 
   // If BI is reached from the true path of PBI and PBI's condition implies
   // BI's condition, we know the direction of the BI branch.
+  bool ImpliedTrue;
   if (PBI->getSuccessor(0) == BI->getParent() &&
-      isImpliedCondition(PBI->getCondition(), BI->getCondition(), DL) &&
+      isImpliedCondition(PBI->getCondition(), BI->getCondition(), ImpliedTrue,
+                         DL) &&
       PBI->getSuccessor(0) != PBI->getSuccessor(1) &&
       BB->getSinglePredecessor()) {
     // Turn this into a branch on constant.
     auto *OldCond = BI->getCondition();
-    BI->setCondition(ConstantInt::getTrue(BB->getContext()));
+    ConstantInt *CI = ImpliedTrue ? ConstantInt::getTrue(BB->getContext())
+                                  : ConstantInt::getFalse(BB->getContext());
+    BI->setCondition(CI);
     RecursivelyDeleteTriviallyDeadInstructions(OldCond);
     return true;  // Nuke the branch on constant.
   }