[ValueTracking] Make isImpliedCondition return an Optional<bool>. NFC.

[mcrosier]

Summary

This is follow up from D18905. Thanks, Chad.

[junbuml]

lib/Analysis/ValueTracking.cpp

3939–3940

Please update the comment.

[mcrosier]

Address Jun's feedback.

[sanjoy]

lgtm

(Didn't look too closely, since this is a straightforward refactoring change)

[mcrosier]

Thanks, Sanjoy. Committed r266904.

include/llvm/Analysis/ValueTracking.h

template <typename T> class ArrayRef;
   SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS,
                                          Instruction::CastOps *CastOp = nullptr);
 
   /// Parse out a conservative ConstantRange from !range metadata.
   ///
   /// E.g. if RangeMD is !{i32 0, i32 10, i32 15, i32 20} then return [0, 20).
   ConstantRange getConstantRangeFromMetadata(MDNode &RangeMD);
 
-  /// Return true if RHS is known to be implied by LHS.  The implication may be
-  /// either true or false depending on what is returned in ImpliedTrue.
+  /// Return true if RHS is known to be implied true by LHS.  Return false if
+  /// RHS is known to be implied false by LHS.  Otherwise, return None if no
+  /// implication can be made.
   /// A & B must be i1 (boolean) values or a vector of such values. Note that
   /// the truth table for implication is the same as <=u on i1 values (but not
   /// <=s!).  The truth table for both is:
   ///    | T | F (B)
   ///  T | T | F
   ///  F | T | T
   /// (A)
-  bool isImpliedCondition(Value *LHS, Value *RHS, bool &ImpliedTrue,
+  Optional<bool> isImpliedCondition(Value *LHS, Value *RHS,
                                     const DataLayout &DL, unsigned Depth = 0,
                                     AssumptionCache *AC = nullptr,
                                     const Instruction *CxtI = nullptr,
                                     const DominatorTree *DT = nullptr);
 } // end namespace llvm
 
 #endif

lib/Analysis/InstructionSimplify.cpp

case ICmpInst::ICMP_UGT:
       // X >u 0 -> X
       if (match(RHS, m_Zero()))
         return LHS;
       break;
     case ICmpInst::ICMP_UGE: {
       // X >=u 1 -> X
       if (match(RHS, m_One()))
         return LHS;
-      bool ImpliedTrue;
-      if (isImpliedCondition(RHS, LHS, ImpliedTrue, Q.DL) && ImpliedTrue)
+      if (isImpliedCondition(RHS, LHS, Q.DL).getValueOr(false))
         return getTrue(ITy);
       break;
     }
     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
       ///  0  |  0  |  1 (0 >= 0)   |  1
       ///  0  |  1  |  1 (0 >= -1)  |  1
       ///  1  |  0  |  0 (-1 >= 0)  |  0
       ///  1  |  1  |  1 (-1 >= -1) |  1
-      bool ImpliedTrue;
-      if (isImpliedCondition(LHS, RHS, ImpliedTrue, Q.DL) && ImpliedTrue)
+      if (isImpliedCondition(LHS, RHS, Q.DL).getValueOr(false))
         return getTrue(ITy);
       break;
     }
     case ICmpInst::ICMP_SLT:
       // X <s 0 -> X
       if (match(RHS, m_Zero()))
         return LHS;
       break;
     case ICmpInst::ICMP_SLE:
       // X <=s -1 -> X
       if (match(RHS, m_One()))
         return LHS;
       break;
     case ICmpInst::ICMP_ULE: {
-      bool ImpliedTrue;
-      if (isImpliedCondition(LHS, RHS, ImpliedTrue, Q.DL) && ImpliedTrue)
+      if (isImpliedCondition(LHS, RHS, Q.DL).getValueOr(false))
         return getTrue(ITy);
       break;
     }
     }
   }
 
   // If we are comparing with zero then try hard since this is a common case.
   if (match(RHS, m_Zero())) {

lib/Analysis/ValueTracking.cpp

if (MatchNUWAddsToSameValue(LHS, RHS, X, CLHS, CRHS))
       return CLHS->ule(*CRHS);
 
     return false;
   }
   }
 }
 
 /// Return true if "icmp Pred BLHS BRHS" is true whenever "icmp Pred
-/// ALHS ARHS" is true.
-static bool isImpliedCondOperands(CmpInst::Predicate Pred, Value *ALHS,
-                                  Value *ARHS, Value *BLHS, Value *BRHS,
-                                  const DataLayout &DL, unsigned Depth,
-                                  AssumptionCache *AC, const Instruction *CxtI,
-                                  const DominatorTree *DT) {
+/// ALHS ARHS" is true.  Otherwise, return None.
+static Optional<bool>
+isImpliedCondOperands(CmpInst::Predicate Pred, Value *ALHS, Value *ARHS,
+                      Value *BLHS, Value *BRHS, const DataLayout &DL,
+                      unsigned Depth, AssumptionCache *AC,
+                      const Instruction *CxtI, const DominatorTree *DT) {
   switch (Pred) {
   default:
-    return false;
+    return None;
 
   case CmpInst::ICMP_SLT:
   case CmpInst::ICMP_SLE:
-    return isTruePredicate(CmpInst::ICMP_SLE, BLHS, ALHS, DL, Depth, AC, CxtI,
-                           DT) &&
-           isTruePredicate(CmpInst::ICMP_SLE, ARHS, BRHS, DL, Depth, AC, CxtI,
-                           DT);
+    if (isTruePredicate(CmpInst::ICMP_SLE, BLHS, ALHS, DL, Depth, AC, CxtI,
+        isTruePredicate(CmpInst::ICMP_SLE, ARHS, BRHS, DL, Depth, AC, CxtI, DT))
+      return true;
+    return None;
 
   case CmpInst::ICMP_ULT:
   case CmpInst::ICMP_ULE:
-    return isTruePredicate(CmpInst::ICMP_ULE, BLHS, ALHS, DL, Depth, AC, CxtI,
-                           DT) &&
-           isTruePredicate(CmpInst::ICMP_ULE, ARHS, BRHS, DL, Depth, AC, CxtI,
-                           DT);
+    if (isTruePredicate(CmpInst::ICMP_ULE, BLHS, ALHS, DL, Depth, AC, CxtI,
+        isTruePredicate(CmpInst::ICMP_ULE, ARHS, BRHS, DL, Depth, AC, CxtI, DT))
+      return true;
+    return None;
   }
 }
 
-/// 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) {
+/// Return true if "icmp1 APred ALHS ARHS" implies "icmp2 BPred BLHS BRHS" is
+/// true.  Return false if "icmp1 APred ALHS ARHS" implies "icmp2 BPred BLHS
+/// BRHS" is false.  Otherwise, return None if we can't infer anything.
+static Optional<bool> isImpliedCondMatchingOperands(CmpInst::Predicate APred,
+                                                    Value *ALHS, Value *ARHS,
+                                                    CmpInst::Predicate BPred,
+                                                    Value *BLHS, Value *BRHS) {
   // 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;
+    return None;
 
   // 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;
+  if (APred == BPred)
     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 (CmpInst::getInversePredicate(APred) == BPred)
+    return false;
 
   // 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;
+      return false;
     }
   }
 
   // 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;
+    return None;
 
   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;
-    }
+    if (CmpInst::isFalseWhenEqual(BPred))
+      return false;
+
     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;
-    }
+    if (BPred == CmpInst::ICMP_EQ)
+      return false;
+
     // A > B implies A != B is true.
     // A < B implies A != B is true.
-    if (BPred == CmpInst::ICMP_NE) {
-      ImpliedTrue = true;
+    if (BPred == CmpInst::ICMP_NE)
       return true;
-    }
     break;
   }
-  return false;
+  return None;
 }
 
-bool llvm::isImpliedCondition(Value *LHS, Value *RHS, bool &ImpliedTrue,
+Optional<bool> llvm::isImpliedCondition(Value *LHS, Value *RHS,
                                         const DataLayout &DL, unsigned Depth,
-                              AssumptionCache *AC, const Instruction *CxtI,
+                                        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) {
-    ImpliedTrue = true;
+  if (LHS == RHS)
     return true;
-  }
 
   if (OpTy->isVectorTy())
     // TODO: extending the code below to handle vectors
-    return false;
+    return None;
   assert(OpTy->isIntegerTy(1) && "implied by above");
 
   ICmpInst::Predicate APred, BPred;
   Value *ALHS, *ARHS;
   Value *BLHS, *BRHS;
 
   if (!match(LHS, m_ICmp(APred, m_Value(ALHS), m_Value(ARHS))) ||
       !match(RHS, m_ICmp(BPred, m_Value(BLHS), m_Value(BRHS))))
-    return false;
+    return None;
 
-  if (isImpliedCondMatchingOperands(APred, ALHS, ARHS, BPred, BLHS, BRHS,
-                                    ImpliedTrue))
-    return true;
+  Optional<bool> Implication =
+      isImpliedCondMatchingOperands(APred, ALHS, ARHS, BPred, BLHS, BRHS);
+  if (Implication)
+    return Implication;
 
-  if (APred == BPred) {
-    ImpliedTrue = true;
+  if (APred == BPred)
     return isImpliedCondOperands(APred, ALHS, ARHS, BLHS, BRHS, DL, Depth, AC,
                                  CxtI, DT);
-  }
 
-  return false;
+  return None;
 }

lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreading::ProcessImpliedCondition(BasicBlock *BB) {
 
   auto &DL = BB->getModule()->getDataLayout();
 
   while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
     auto *PBI = dyn_cast<BranchInst>(CurrentPred->getTerminator());
     if (!PBI || !PBI->isConditional() || PBI->getSuccessor(0) != CurrentBB)
       return false;
 
-    bool ImpliedTrue;
-    if (isImpliedCondition(PBI->getCondition(), Cond, ImpliedTrue, DL)) {
-      BI->getSuccessor(ImpliedTrue ? 1 : 0)->removePredecessor(BB);
-      BranchInst::Create(BI->getSuccessor(ImpliedTrue ? 0 : 1), BI);
+    Optional<bool> Implication =
+        isImpliedCondition(PBI->getCondition(), Cond, DL);
+    if (Implication) {
+      BI->getSuccessor(*Implication ? 1 : 0)->removePredecessor(BB);
+      BranchInst::Create(BI->getSuccessor(*Implication ? 0 : 1), BI);
       BI->eraseFromParent();
       return true;
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }
 
   return false;

lib/Transforms/Utils/SimplifyCFG.cpp

static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
   }
 
   if (auto *CE = dyn_cast<ConstantExpr>(BI->getCondition()))
     if (CE->canTrap())
       return false;
 
   // 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(), ImpliedTrue,
-                         DL) &&
       PBI->getSuccessor(0) != PBI->getSuccessor(1) &&
       BB->getSinglePredecessor()) {
+    Optional<bool> Implication =
+        isImpliedCondition(PBI->getCondition(), BI->getCondition(), DL);
+    if (Implication) {
       // Turn this into a branch on constant.
       auto *OldCond = BI->getCondition();
-    ConstantInt *CI = ImpliedTrue ? ConstantInt::getTrue(BB->getContext())
+      ConstantInt *CI = *Implication ? ConstantInt::getTrue(BB->getContext())
                                      : ConstantInt::getFalse(BB->getContext());
       BI->setCondition(CI);
       RecursivelyDeleteTriviallyDeadInstructions(OldCond);
-    return true;  // Nuke the branch on constant.
+      return true; // Nuke the branch on constant.
     }
+  }
 
   // If both branches are conditional and both contain stores to the same
   // address, remove the stores from the conditionals and create a conditional
   // merged store at the end.
   if (MergeCondStores && mergeConditionalStores(PBI, BI))
     return true;
 
   // If this is a conditional branch in an empty block, and if any