summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Analysis')
-rw-r--r--llvm/lib/Analysis/InstructionSimplify.cpp18
-rw-r--r--llvm/lib/Analysis/ValueTracking.cpp104
2 files changed, 111 insertions, 11 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;
}
OpenPOWER on IntegriCloud