#include "llvm/Operator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/ValueTracking.h"
// If we have a DominatorTree then do a precise test.
if (DT)
- return DT->dominates(I, P);
+ return !DT->isReachableFromEntry(P->getParent()) ||
+ !DT->isReachableFromEntry(I->getParent()) || DT->dominates(I, P);
// Otherwise, if the instruction is in the entry block, and is not an invoke,
// then it obviously dominates all phi nodes.
// the original comparison.
if (TCmp == FCmp)
return TCmp;
+
+ // The remaining cases only make sense if the select condition has the same
+ // type as the result of the comparison, so bail out if this is not so.
+ if (Cond->getType()->isVectorTy() != RHS->getType()->isVectorTy())
+ return 0;
// If the false value simplified to false, then the result of the compare
// is equal to "Cond && TCmp". This also catches the case when the false
// value simplified to false and the true value to true, returning "Cond".
return Op0;
// (X / Y) * Y -> X if the division is exact.
- Value *X = 0, *Y = 0;
- if ((match(Op0, m_IDiv(m_Value(X), m_Value(Y))) && Y == Op1) || // (X / Y) * Y
- (match(Op1, m_IDiv(m_Value(X), m_Value(Y))) && Y == Op0)) { // Y * (X / Y)
- PossiblyExactOperator *Div =
- cast<PossiblyExactOperator>(Y == Op1 ? Op0 : Op1);
- if (Div->isExact())
- return X;
- }
+ Value *X = 0;
+ if (match(Op0, m_Exact(m_IDiv(m_Value(X), m_Specific(Op1)))) || // (X / Y) * Y
+ match(Op1, m_Exact(m_IDiv(m_Value(X), m_Specific(Op0))))) // Y * (X / Y)
+ return X;
// i1 mul -> and.
if (MaxRecurse && Op0->getType()->isIntegerTy(1))
// (X >> A) << A -> X
Value *X;
- if (match(Op0, m_Shr(m_Value(X), m_Specific(Op1))) &&
- cast<PossiblyExactOperator>(Op0)->isExact())
+ if (match(Op0, m_Exact(m_Shr(m_Value(X), m_Specific(Op1)))))
return X;
return 0;
}
return 0;
}
+/// stripPointerAdjustments - This is like Value::stripPointerCasts, but also
+/// removes inbounds gep operations, regardless of their indices.
+static Value *stripPointerAdjustmentsImpl(Value *V,
+ SmallPtrSet<GEPOperator*, 8> &VisitedGEPs) {
+ GEPOperator *GEP = dyn_cast<GEPOperator>(V);
+ if (GEP == 0 || !GEP->isInBounds())
+ return V;
+
+ // If we've already seen this GEP, we will end up infinitely looping. This
+ // can happen in unreachable code.
+ if (!VisitedGEPs.insert(GEP))
+ return V;
+
+ return stripPointerAdjustmentsImpl(GEP->getOperand(0)->stripPointerCasts(),
+ VisitedGEPs);
+}
+
+static Value *stripPointerAdjustments(Value *V) {
+ SmallPtrSet<GEPOperator*, 8> VisitedGEPs;
+ return stripPointerAdjustmentsImpl(V, VisitedGEPs);
+}
+
+
/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
/// fold the result. If not, this returns null.
static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
}
}
- // icmp <alloca*>, <global/alloca*/null> - Different stack variables have
- // different addresses, and what's more the address of a stack variable is
- // never null or equal to the address of a global. Note that generalizing
- // to the case where LHS is a global variable address or null is pointless,
- // since if both LHS and RHS are constants then we already constant folded
- // the compare, and if only one of them is then we moved it to RHS already.
- if (isa<AllocaInst>(LHS) && (isa<GlobalValue>(RHS) || isa<AllocaInst>(RHS) ||
- isa<ConstantPointerNull>(RHS)))
- // We already know that LHS != RHS.
- return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
+ // icmp <object*>, <object*/null> - Different identified objects have
+ // different addresses (unless null), and what's more the address of an
+ // identified local is never equal to another argument (again, barring null).
+ // Note that generalizing to the case where LHS is a global variable address
+ // or null is pointless, since if both LHS and RHS are constants then we
+ // already constant folded the compare, and if only one of them is then we
+ // moved it to RHS already.
+ Value *LHSPtr = LHS->stripPointerCasts();
+ Value *RHSPtr = RHS->stripPointerCasts();
+ if (LHSPtr == RHSPtr)
+ return ConstantInt::get(ITy, CmpInst::isTrueWhenEqual(Pred));
+
+ // Be more aggressive about stripping pointer adjustments when checking a
+ // comparison of an alloca address to another object. We can rip off all
+ // inbounds GEP operations, even if they are variable.
+ LHSPtr = stripPointerAdjustments(LHSPtr);
+ if (llvm::isIdentifiedObject(LHSPtr)) {
+ RHSPtr = stripPointerAdjustments(RHSPtr);
+ if (llvm::isKnownNonNull(LHSPtr) || llvm::isKnownNonNull(RHSPtr)) {
+ // If both sides are different identified objects, they aren't equal
+ // unless they're null.
+ if (LHSPtr != RHSPtr && llvm::isIdentifiedObject(RHSPtr))
+ return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
+
+ // A local identified object (alloca or noalias call) can't equal any
+ // incoming argument, unless they're both null.
+ if (isa<Instruction>(LHSPtr) && isa<Argument>(RHSPtr))
+ return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
+ }
+
+ // Assume that the constant null is on the right.
+ if (llvm::isKnownNonNull(LHSPtr) && isa<ConstantPointerNull>(RHSPtr))
+ return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
+ } else if (isa<Argument>(LHSPtr)) {
+ RHSPtr = stripPointerAdjustments(RHSPtr);
+ // An alloca can't be equal to an argument.
+ if (isa<AllocaInst>(RHSPtr))
+ return ConstantInt::get(ITy, CmpInst::isFalseWhenEqual(Pred));
+ }
// If we are comparing with zero then try hard since this is a common case.
if (match(RHS, m_Zero())) {
bool LHSKnownNonNegative, LHSKnownNegative;
switch (Pred) {
- default:
- assert(false && "Unknown ICmp predicate!");
+ default: llvm_unreachable("Unknown ICmp predicate!");
case ICmpInst::ICMP_ULT:
return getFalse(ITy);
case ICmpInst::ICMP_UGE:
// there. Use this to work out the result of the comparison.
if (RExt != CI) {
switch (Pred) {
- default:
- assert(false && "Unknown ICmp predicate!");
+ default: llvm_unreachable("Unknown ICmp predicate!");
// LHS <u RHS.
case ICmpInst::ICMP_EQ:
case ICmpInst::ICMP_UGT:
// bits there. Use this to work out the result of the comparison.
if (RExt != CI) {
switch (Pred) {
- default:
- assert(false && "Unknown ICmp predicate!");
+ default: llvm_unreachable("Unknown ICmp predicate!");
case ICmpInst::ICMP_EQ:
return ConstantInt::getFalse(CI->getContext());
case ICmpInst::ICMP_NE:
return getFalse(ITy);
}
+ // Simplify comparisons of GEPs.
+ if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) {
+ if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) {
+ if (GLHS->getPointerOperand() == GRHS->getPointerOperand() &&
+ GLHS->hasAllConstantIndices() && GRHS->hasAllConstantIndices() &&
+ (ICmpInst::isEquality(Pred) ||
+ (GLHS->isInBounds() && GRHS->isInBounds() &&
+ Pred == ICmpInst::getSignedPredicate(Pred)))) {
+ // The bases are equal and the indices are constant. Build a constant
+ // expression GEP with the same indices and a null base pointer to see
+ // what constant folding can make out of it.
+ Constant *Null = Constant::getNullValue(GLHS->getPointerOperandType());
+ SmallVector<Value *, 4> IndicesLHS(GLHS->idx_begin(), GLHS->idx_end());
+ Constant *NewLHS = ConstantExpr::getGetElementPtr(Null, IndicesLHS);
+
+ SmallVector<Value *, 4> IndicesRHS(GRHS->idx_begin(), GRHS->idx_end());
+ Constant *NewRHS = ConstantExpr::getGetElementPtr(Null, IndicesRHS);
+ return ConstantExpr::getICmp(Pred, NewLHS, NewRHS);
+ }
+ }
+ }
+
// If the comparison is with the result of a select instruction, check whether
// comparing with either branch of the select always yields the same value.
if (isa<SelectInst>(LHS) || isa<SelectInst>(RHS))
projects / oota-llvm.git / blobdiff