Index: include/llvm/Analysis/ValueTracking.h =================================================================== --- include/llvm/Analysis/ValueTracking.h +++ include/llvm/Analysis/ValueTracking.h @@ -446,8 +446,9 @@ /// 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: @@ -455,11 +456,11 @@ /// T | T | F /// F | T | T /// (A) - bool isImpliedCondition(Value *LHS, Value *RHS, bool &ImpliedTrue, - const DataLayout &DL, unsigned Depth = 0, - AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr); + Optional 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 Index: lib/Analysis/InstructionSimplify.cpp =================================================================== --- lib/Analysis/InstructionSimplify.cpp +++ lib/Analysis/InstructionSimplify.cpp @@ -2135,8 +2135,7 @@ // 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; } @@ -2148,8 +2147,7 @@ /// 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; } @@ -2164,8 +2162,7 @@ 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; } Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -3909,44 +3909,46 @@ } /// 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 +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, + DT) && + 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, + DT) && + 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 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) { @@ -3956,17 +3958,13 @@ // 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. @@ -3978,8 +3976,7 @@ case CmpInst::ICMP_ULT: // A u B is false. case CmpInst::ICMP_SGT: // A >s B implies A s B is false. - ImpliedTrue = false; - return true; + return false; } } @@ -3987,17 +3984,16 @@ // 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: @@ -4005,38 +4001,34 @@ 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, - const DataLayout &DL, unsigned Depth, - AssumptionCache *AC, const Instruction *CxtI, - const DominatorTree *DT) { +Optional llvm::isImpliedCondition(Value *LHS, Value *RHS, + 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) { - 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; @@ -4045,17 +4037,16 @@ 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 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; } Index: lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- lib/Transforms/Scalar/JumpThreading.cpp +++ lib/Transforms/Scalar/JumpThreading.cpp @@ -928,10 +928,11 @@ 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 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; } Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -2722,19 +2722,20 @@ // 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()) { - // Turn this into a branch on constant. - auto *OldCond = BI->getCondition(); - ConstantInt *CI = ImpliedTrue ? ConstantInt::getTrue(BB->getContext()) - : ConstantInt::getFalse(BB->getContext()); - BI->setCondition(CI); - RecursivelyDeleteTriviallyDeadInstructions(OldCond); - return true; // Nuke the branch on constant. + Optional Implication = + isImpliedCondition(PBI->getCondition(), BI->getCondition(), DL); + if (Implication) { + // Turn this into a branch on constant. + auto *OldCond = BI->getCondition(); + ConstantInt *CI = *Implication ? ConstantInt::getTrue(BB->getContext()) + : ConstantInt::getFalse(BB->getContext()); + BI->setCondition(CI); + RecursivelyDeleteTriviallyDeadInstructions(OldCond); + return true; // Nuke the branch on constant. + } } // If both branches are conditional and both contain stores to the same