X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FInstructionSimplify.cpp;h=4a3c74e9db356ca2fe8656692086e457feee39af;hb=3f7f8e814ef49b79b9c41e75df40be3bdb3612f5;hp=f8d159dc43847a2a514182cb5b94638df4f0e3f8;hpb=f72e0ca71507ab3d8566148e124fe21f4a051cd1;p=oota-llvm.git diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index f8d159dc438..4a3c74e9db3 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -18,19 +18,20 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "instsimplify" -#include "llvm/GlobalAlias.h" -#include "llvm/Operator.h" -#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/InstructionSimplify.h" -#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/Analysis/MemoryBuiltins.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/GlobalAlias.h" +#include "llvm/IR/Operator.h" #include "llvm/Support/ConstantRange.h" #include "llvm/Support/GetElementPtrTypeIterator.h" #include "llvm/Support/PatternMatch.h" #include "llvm/Support/ValueHandle.h" -#include "llvm/Target/TargetData.h" using namespace llvm; using namespace llvm::PatternMatch; @@ -41,12 +42,12 @@ STATISTIC(NumFactor , "Number of factorizations"); STATISTIC(NumReassoc, "Number of reassociations"); struct Query { - const TargetData *TD; + const DataLayout *TD; const TargetLibraryInfo *TLI; const DominatorTree *DT; - Query(const TargetData *td, const TargetLibraryInfo *tli, - const DominatorTree *dt) : TD(td), TLI(tli), DT(dt) {}; + Query(const DataLayout *td, const TargetLibraryInfo *tli, + const DominatorTree *dt) : TD(td), TLI(tli), DT(dt) {} }; static Value *SimplifyAndInst(Value *, Value *, const Query &, unsigned); @@ -95,6 +96,12 @@ static bool ValueDominatesPHI(Value *V, PHINode *P, const DominatorTree *DT) { // Arguments and constants dominate all instructions. return true; + // If we are processing instructions (and/or basic blocks) that have not been + // fully added to a function, the parent nodes may still be null. Simply + // return the conservative answer in these cases. + if (!I->getParent() || !P->getParent() || !I->getParent()->getParent()) + return false; + // If we have a DominatorTree then do a precise test. if (DT) { if (!DT->isReachableFromEntry(P->getParent())) @@ -644,57 +651,32 @@ static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, } Value *llvm::SimplifyAddInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, - const TargetData *TD, const TargetLibraryInfo *TLI, + const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyAddInst(Op0, Op1, isNSW, isNUW, Query (TD, TLI, DT), RecursionLimit); } -/// \brief Accumulate the constant integer offset a GEP represents. -/// -/// Given a getelementptr instruction/constantexpr, accumulate the constant -/// offset from the base pointer into the provided APInt 'Offset'. Returns true -/// if the GEP has all-constant indices. Returns false if any non-constant -/// index is encountered leaving the 'Offset' in an undefined state. The -/// 'Offset' APInt must be the bitwidth of the target's pointer size. -static bool accumulateGEPOffset(const TargetData &TD, GEPOperator *GEP, - APInt &Offset) { - unsigned IntPtrWidth = TD.getPointerSizeInBits(); - assert(IntPtrWidth == Offset.getBitWidth()); - - gep_type_iterator GTI = gep_type_begin(GEP); - for (User::op_iterator I = GEP->op_begin() + 1, E = GEP->op_end(); I != E; - ++I, ++GTI) { - ConstantInt *OpC = dyn_cast(*I); - if (!OpC) return false; - if (OpC->isZero()) continue; - - // Handle a struct index, which adds its field offset to the pointer. - if (StructType *STy = dyn_cast(*GTI)) { - unsigned ElementIdx = OpC->getZExtValue(); - const StructLayout *SL = TD.getStructLayout(STy); - Offset += APInt(IntPtrWidth, SL->getElementOffset(ElementIdx)); - continue; - } - - APInt TypeSize(IntPtrWidth, TD.getTypeAllocSize(GTI.getIndexedType())); - Offset += OpC->getValue().sextOrTrunc(IntPtrWidth) * TypeSize; - } - return true; -} - /// \brief Compute the base pointer and cumulative constant offsets for V. /// /// This strips all constant offsets off of V, leaving it the base pointer, and /// accumulates the total constant offset applied in the returned constant. It /// returns 0 if V is not a pointer, and returns the constant '0' if there are /// no constant offsets applied. -static Constant *stripAndComputeConstantOffsets(const TargetData &TD, +/// +/// This is very similar to GetPointerBaseWithConstantOffset except it doesn't +/// follow non-inbounds geps. This allows it to remain usable for icmp ult/etc. +/// folding. +static Constant *stripAndComputeConstantOffsets(const DataLayout *TD, Value *&V) { - if (!V->getType()->isPointerTy()) - return 0; + assert(V->getType()->getScalarType()->isPointerTy()); - unsigned IntPtrWidth = TD.getPointerSizeInBits(); + // Without DataLayout, just be conservative for now. Theoretically, more could + // be done in this case. + if (!TD) + return ConstantInt::get(IntegerType::get(V->getContext(), 64), 0); + + unsigned IntPtrWidth = TD->getPointerSizeInBits(); APInt Offset = APInt::getNullValue(IntPtrWidth); // Even though we don't look through PHI nodes, we could be called on an @@ -703,7 +685,7 @@ static Constant *stripAndComputeConstantOffsets(const TargetData &TD, Visited.insert(V); do { if (GEPOperator *GEP = dyn_cast(V)) { - if (!accumulateGEPOffset(TD, GEP, Offset)) + if (!GEP->isInBounds() || !GEP->accumulateConstantOffset(*TD, Offset)) break; V = GEP->getPointerOperand(); } else if (Operator::getOpcode(V) == Instruction::BitCast) { @@ -715,23 +697,24 @@ static Constant *stripAndComputeConstantOffsets(const TargetData &TD, } else { break; } - assert(V->getType()->isPointerTy() && "Unexpected operand type!"); + assert(V->getType()->getScalarType()->isPointerTy() && + "Unexpected operand type!"); } while (Visited.insert(V)); - Type *IntPtrTy = TD.getIntPtrType(V->getContext()); - return ConstantInt::get(IntPtrTy, Offset); + Type *IntPtrTy = TD->getIntPtrType(V->getContext()); + Constant *OffsetIntPtr = ConstantInt::get(IntPtrTy, Offset); + if (V->getType()->isVectorTy()) + return ConstantVector::getSplat(V->getType()->getVectorNumElements(), + OffsetIntPtr); + return OffsetIntPtr; } /// \brief Compute the constant difference between two pointer values. /// If the difference is not a constant, returns zero. -static Constant *computePointerDifference(const TargetData &TD, +static Constant *computePointerDifference(const DataLayout *TD, Value *LHS, Value *RHS) { Constant *LHSOffset = stripAndComputeConstantOffsets(TD, LHS); - if (!LHSOffset) - return 0; Constant *RHSOffset = stripAndComputeConstantOffsets(TD, RHS); - if (!RHSOffset) - return 0; // If LHS and RHS are not related via constant offsets to the same base // value, there is nothing we can do here. @@ -845,9 +828,9 @@ static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, return W; // Variations on GEP(base, I, ...) - GEP(base, i, ...) -> GEP(null, I-i, ...). - if (Q.TD && match(Op0, m_PtrToInt(m_Value(X))) && + if (match(Op0, m_PtrToInt(m_Value(X))) && match(Op1, m_PtrToInt(m_Value(Y)))) - if (Constant *Result = computePointerDifference(*Q.TD, X, Y)) + if (Constant *Result = computePointerDifference(Q.TD, X, Y)) return ConstantExpr::getIntegerCast(Result, Op0->getType(), true); // Mul distributes over Sub. Try some generic simplifications based on this. @@ -873,12 +856,118 @@ static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, } Value *llvm::SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, - const TargetData *TD, const TargetLibraryInfo *TLI, + const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifySubInst(Op0, Op1, isNSW, isNUW, Query (TD, TLI, DT), RecursionLimit); } +/// Given operands for an FAdd, see if we can fold the result. If not, this +/// returns null. +static Value *SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, + const Query &Q, unsigned MaxRecurse) { + if (Constant *CLHS = dyn_cast(Op0)) { + if (Constant *CRHS = dyn_cast(Op1)) { + Constant *Ops[] = { CLHS, CRHS }; + return ConstantFoldInstOperands(Instruction::FAdd, CLHS->getType(), + Ops, Q.TD, Q.TLI); + } + + // Canonicalize the constant to the RHS. + std::swap(Op0, Op1); + } + + // fadd X, -0 ==> X + if (match(Op1, m_NegZero())) + return Op0; + + // fadd X, 0 ==> X, when we know X is not -0 + if (match(Op1, m_Zero()) && + (FMF.noSignedZeros() || CannotBeNegativeZero(Op0))) + return Op0; + + // fadd [nnan ninf] X, (fsub [nnan ninf] 0, X) ==> 0 + // where nnan and ninf have to occur at least once somewhere in this + // expression + Value *SubOp = 0; + if (match(Op1, m_FSub(m_AnyZero(), m_Specific(Op0)))) + SubOp = Op1; + else if (match(Op0, m_FSub(m_AnyZero(), m_Specific(Op1)))) + SubOp = Op0; + if (SubOp) { + Instruction *FSub = cast(SubOp); + if ((FMF.noNaNs() || FSub->hasNoNaNs()) && + (FMF.noInfs() || FSub->hasNoInfs())) + return Constant::getNullValue(Op0->getType()); + } + + return 0; +} + +/// Given operands for an FSub, see if we can fold the result. If not, this +/// returns null. +static Value *SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, + const Query &Q, unsigned MaxRecurse) { + if (Constant *CLHS = dyn_cast(Op0)) { + if (Constant *CRHS = dyn_cast(Op1)) { + Constant *Ops[] = { CLHS, CRHS }; + return ConstantFoldInstOperands(Instruction::FSub, CLHS->getType(), + Ops, Q.TD, Q.TLI); + } + } + + // fsub X, 0 ==> X + if (match(Op1, m_Zero())) + return Op0; + + // fsub X, -0 ==> X, when we know X is not -0 + if (match(Op1, m_NegZero()) && + (FMF.noSignedZeros() || CannotBeNegativeZero(Op0))) + return Op0; + + // fsub 0, (fsub -0.0, X) ==> X + Value *X; + if (match(Op0, m_AnyZero())) { + if (match(Op1, m_FSub(m_NegZero(), m_Value(X)))) + return X; + if (FMF.noSignedZeros() && match(Op1, m_FSub(m_AnyZero(), m_Value(X)))) + return X; + } + + // fsub nnan ninf x, x ==> 0.0 + if (FMF.noNaNs() && FMF.noInfs() && Op0 == Op1) + return Constant::getNullValue(Op0->getType()); + + return 0; +} + +/// Given the operands for an FMul, see if we can fold the result +static Value *SimplifyFMulInst(Value *Op0, Value *Op1, + FastMathFlags FMF, + const Query &Q, + unsigned MaxRecurse) { + if (Constant *CLHS = dyn_cast(Op0)) { + if (Constant *CRHS = dyn_cast(Op1)) { + Constant *Ops[] = { CLHS, CRHS }; + return ConstantFoldInstOperands(Instruction::FMul, CLHS->getType(), + Ops, Q.TD, Q.TLI); + } + + // Canonicalize the constant to the RHS. + std::swap(Op0, Op1); + } + + // fmul X, 1.0 ==> X + if (match(Op1, m_FPOne())) + return Op0; + + // fmul nnan nsz X, 0 ==> 0 + if (FMF.noNaNs() && FMF.noSignedZeros() && match(Op1, m_AnyZero())) + return Op1; + + return 0; +} + /// SimplifyMulInst - Given operands for a Mul, see if we can /// fold the result. If not, this returns null. static Value *SimplifyMulInst(Value *Op0, Value *Op1, const Query &Q, @@ -944,7 +1033,27 @@ static Value *SimplifyMulInst(Value *Op0, Value *Op1, const Query &Q, return 0; } -Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const TargetData *TD, +Value *llvm::SimplifyFAddInst(Value *Op0, Value *Op1, FastMathFlags FMF, + const DataLayout *TD, const TargetLibraryInfo *TLI, + const DominatorTree *DT) { + return ::SimplifyFAddInst(Op0, Op1, FMF, Query (TD, TLI, DT), RecursionLimit); +} + +Value *llvm::SimplifyFSubInst(Value *Op0, Value *Op1, FastMathFlags FMF, + const DataLayout *TD, const TargetLibraryInfo *TLI, + const DominatorTree *DT) { + return ::SimplifyFSubInst(Op0, Op1, FMF, Query (TD, TLI, DT), RecursionLimit); +} + +Value *llvm::SimplifyFMulInst(Value *Op0, Value *Op1, + FastMathFlags FMF, + const DataLayout *TD, + const TargetLibraryInfo *TLI, + const DominatorTree *DT) { + return ::SimplifyFMulInst(Op0, Op1, FMF, Query (TD, TLI, DT), RecursionLimit); +} + +Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyMulInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit); @@ -1032,7 +1141,7 @@ static Value *SimplifySDivInst(Value *Op0, Value *Op1, const Query &Q, return 0; } -Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const TargetData *TD, +Value *llvm::SimplifySDivInst(Value *Op0, Value *Op1, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifySDivInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit); @@ -1048,7 +1157,7 @@ static Value *SimplifyUDivInst(Value *Op0, Value *Op1, const Query &Q, return 0; } -Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const TargetData *TD, +Value *llvm::SimplifyUDivInst(Value *Op0, Value *Op1, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyUDivInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit); @@ -1067,7 +1176,7 @@ static Value *SimplifyFDivInst(Value *Op0, Value *Op1, const Query &Q, return 0; } -Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const TargetData *TD, +Value *llvm::SimplifyFDivInst(Value *Op0, Value *Op1, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyFDivInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit); @@ -1137,7 +1246,7 @@ static Value *SimplifySRemInst(Value *Op0, Value *Op1, const Query &Q, return 0; } -Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const TargetData *TD, +Value *llvm::SimplifySRemInst(Value *Op0, Value *Op1, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifySRemInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit); @@ -1153,7 +1262,7 @@ static Value *SimplifyURemInst(Value *Op0, Value *Op1, const Query &Q, return 0; } -Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const TargetData *TD, +Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyURemInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit); @@ -1172,7 +1281,7 @@ static Value *SimplifyFRemInst(Value *Op0, Value *Op1, const Query &, return 0; } -Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, const TargetData *TD, +Value *llvm::SimplifyFRemInst(Value *Op0, Value *Op1, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyFRemInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit); @@ -1241,7 +1350,7 @@ static Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, } Value *llvm::SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, - const TargetData *TD, const TargetLibraryInfo *TLI, + const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyShlInst(Op0, Op1, isNSW, isNUW, Query (TD, TLI, DT), RecursionLimit); @@ -1268,7 +1377,7 @@ static Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, } Value *llvm::SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, - const TargetData *TD, + const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyLShrInst(Op0, Op1, isExact, Query (TD, TLI, DT), @@ -1300,7 +1409,7 @@ static Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, } Value *llvm::SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, - const TargetData *TD, + const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyAShrInst(Op0, Op1, isExact, Query (TD, TLI, DT), @@ -1357,9 +1466,9 @@ static Value *SimplifyAndInst(Value *Op0, Value *Op1, const Query &Q, // A & (-A) = A if A is a power of two or zero. if (match(Op0, m_Neg(m_Specific(Op1))) || match(Op1, m_Neg(m_Specific(Op0)))) { - if (isPowerOfTwo(Op0, Q.TD, /*OrZero*/true)) + if (isKnownToBeAPowerOfTwo(Op0, /*OrZero*/true)) return Op0; - if (isPowerOfTwo(Op1, Q.TD, /*OrZero*/true)) + if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/true)) return Op1; } @@ -1400,7 +1509,7 @@ static Value *SimplifyAndInst(Value *Op0, Value *Op1, const Query &Q, return 0; } -Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const TargetData *TD, +Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyAndInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit); @@ -1494,7 +1603,7 @@ static Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q, return 0; } -Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const TargetData *TD, +Value *llvm::SimplifyOrInst(Value *Op0, Value *Op1, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyOrInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit); @@ -1554,7 +1663,7 @@ static Value *SimplifyXorInst(Value *Op0, Value *Op1, const Query &Q, return 0; } -Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const TargetData *TD, +Value *llvm::SimplifyXorInst(Value *Op0, Value *Op1, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyXorInst(Op0, Op1, Query (TD, TLI, DT), RecursionLimit); @@ -1584,6 +1693,148 @@ static Value *ExtractEquivalentCondition(Value *V, CmpInst::Predicate Pred, return 0; } +// A significant optimization not implemented here is assuming that alloca +// addresses are not equal to incoming argument values. They don't *alias*, +// as we say, but that doesn't mean they aren't equal, so we take a +// conservative approach. +// +// This is inspired in part by C++11 5.10p1: +// "Two pointers of the same type compare equal if and only if they are both +// null, both point to the same function, or both represent the same +// address." +// +// This is pretty permissive. +// +// It's also partly due to C11 6.5.9p6: +// "Two pointers compare equal if and only if both are null pointers, both are +// pointers to the same object (including a pointer to an object and a +// subobject at its beginning) or function, both are pointers to one past the +// last element of the same array object, or one is a pointer to one past the +// end of one array object and the other is a pointer to the start of a +// different array object that happens to immediately follow the first array +// object in the address space.) +// +// C11's version is more restrictive, however there's no reason why an argument +// couldn't be a one-past-the-end value for a stack object in the caller and be +// equal to the beginning of a stack object in the callee. +// +// If the C and C++ standards are ever made sufficiently restrictive in this +// area, it may be possible to update LLVM's semantics accordingly and reinstate +// this optimization. +static Constant *computePointerICmp(const DataLayout *TD, + const TargetLibraryInfo *TLI, + CmpInst::Predicate Pred, + Value *LHS, Value *RHS) { + // First, skip past any trivial no-ops. + LHS = LHS->stripPointerCasts(); + RHS = RHS->stripPointerCasts(); + + // A non-null pointer is not equal to a null pointer. + if (llvm::isKnownNonNull(LHS) && isa(RHS) && + (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE)) + return ConstantInt::get(GetCompareTy(LHS), + !CmpInst::isTrueWhenEqual(Pred)); + + // We can only fold certain predicates on pointer comparisons. + switch (Pred) { + default: + return 0; + + // Equality comaprisons are easy to fold. + case CmpInst::ICMP_EQ: + case CmpInst::ICMP_NE: + break; + + // We can only handle unsigned relational comparisons because 'inbounds' on + // a GEP only protects against unsigned wrapping. + case CmpInst::ICMP_UGT: + case CmpInst::ICMP_UGE: + case CmpInst::ICMP_ULT: + case CmpInst::ICMP_ULE: + // However, we have to switch them to their signed variants to handle + // negative indices from the base pointer. + Pred = ICmpInst::getSignedPredicate(Pred); + break; + } + + // Strip off any constant offsets so that we can reason about them. + // It's tempting to use getUnderlyingObject or even just stripInBoundsOffsets + // here and compare base addresses like AliasAnalysis does, however there are + // numerous hazards. AliasAnalysis and its utilities rely on special rules + // governing loads and stores which don't apply to icmps. Also, AliasAnalysis + // doesn't need to guarantee pointer inequality when it says NoAlias. + Constant *LHSOffset = stripAndComputeConstantOffsets(TD, LHS); + Constant *RHSOffset = stripAndComputeConstantOffsets(TD, RHS); + + // If LHS and RHS are related via constant offsets to the same base + // value, we can replace it with an icmp which just compares the offsets. + if (LHS == RHS) + return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset); + + // Various optimizations for (in)equality comparisons. + if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) { + // Different non-empty allocations that exist at the same time have + // different addresses (if the program can tell). Global variables always + // exist, so they always exist during the lifetime of each other and all + // allocas. Two different allocas usually have different addresses... + // + // However, if there's an @llvm.stackrestore dynamically in between two + // allocas, they may have the same address. It's tempting to reduce the + // scope of the problem by only looking at *static* allocas here. That would + // cover the majority of allocas while significantly reducing the likelihood + // of having an @llvm.stackrestore pop up in the middle. However, it's not + // actually impossible for an @llvm.stackrestore to pop up in the middle of + // an entry block. Also, if we have a block that's not attached to a + // function, we can't tell if it's "static" under the current definition. + // Theoretically, this problem could be fixed by creating a new kind of + // instruction kind specifically for static allocas. Such a new instruction + // could be required to be at the top of the entry block, thus preventing it + // from being subject to a @llvm.stackrestore. Instcombine could even + // convert regular allocas into these special allocas. It'd be nifty. + // However, until then, this problem remains open. + // + // So, we'll assume that two non-empty allocas have different addresses + // for now. + // + // With all that, if the offsets are within the bounds of their allocations + // (and not one-past-the-end! so we can't use inbounds!), and their + // allocations aren't the same, the pointers are not equal. + // + // Note that it's not necessary to check for LHS being a global variable + // address, due to canonicalization and constant folding. + if (isa(LHS) && + (isa(RHS) || isa(RHS))) { + ConstantInt *LHSOffsetCI = dyn_cast(LHSOffset); + ConstantInt *RHSOffsetCI = dyn_cast(RHSOffset); + uint64_t LHSSize, RHSSize; + if (LHSOffsetCI && RHSOffsetCI && + getObjectSize(LHS, LHSSize, TD, TLI) && + getObjectSize(RHS, RHSSize, TD, TLI)) { + const APInt &LHSOffsetValue = LHSOffsetCI->getValue(); + const APInt &RHSOffsetValue = RHSOffsetCI->getValue(); + if (!LHSOffsetValue.isNegative() && + !RHSOffsetValue.isNegative() && + LHSOffsetValue.ult(LHSSize) && + RHSOffsetValue.ult(RHSSize)) { + return ConstantInt::get(GetCompareTy(LHS), + !CmpInst::isTrueWhenEqual(Pred)); + } + } + + // Repeat the above check but this time without depending on DataLayout + // or being able to compute a precise size. + if (!cast(LHS->getType())->isEmptyTy() && + !cast(RHS->getType())->isEmptyTy() && + LHSOffset->isNullValue() && + RHSOffset->isNullValue()) + return ConstantInt::get(GetCompareTy(LHS), + !CmpInst::isTrueWhenEqual(Pred)); + } + } + + // Otherwise, fail. + return 0; +} /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can /// fold the result. If not, this returns null. @@ -1647,56 +1898,6 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, } } - // icmp , - 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 = LHSPtr->stripInBoundsOffsets(); - if (llvm::isIdentifiedObject(LHSPtr)) { - RHSPtr = RHSPtr->stripInBoundsOffsets(); - 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) && - Pred == CmpInst::ICMP_EQ) - return ConstantInt::get(ITy, false); - - // A local identified object (alloca or noalias call) can't equal any - // incoming argument, unless they're both null. - if (isa(LHSPtr) && isa(RHSPtr) && - Pred == CmpInst::ICMP_EQ) - return ConstantInt::get(ITy, false); - } - - // Assume that the constant null is on the right. - if (llvm::isKnownNonNull(LHSPtr) && isa(RHSPtr)) { - if (Pred == CmpInst::ICMP_EQ) - return ConstantInt::get(ITy, false); - else if (Pred == CmpInst::ICMP_NE) - return ConstantInt::get(ITy, true); - } - } else if (isa(LHSPtr)) { - RHSPtr = RHSPtr->stripInBoundsOffsets(); - // An alloca can't be equal to an argument. - if (isa(RHSPtr)) { - if (Pred == CmpInst::ICMP_EQ) - return ConstantInt::get(ITy, false); - else if (Pred == CmpInst::ICMP_NE) - return ConstantInt::get(ITy, true); - } - } - // If we are comparing with zero then try hard since this is a common case. if (match(RHS, m_Zero())) { bool LHSKnownNonNegative, LHSKnownNegative; @@ -2013,8 +2214,25 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, if (A && C && (A == C || A == D || B == C || B == D) && NoLHSWrapProblem && NoRHSWrapProblem) { // Determine Y and Z in the form icmp (X+Y), (X+Z). - Value *Y = (A == C || A == D) ? B : A; - Value *Z = (C == A || C == B) ? D : C; + Value *Y, *Z; + if (A == C) { + // C + B == C + D -> B == D + Y = B; + Z = D; + } else if (A == D) { + // D + B == C + D -> B == C + Y = B; + Z = C; + } else if (B == C) { + // A + C == C + D -> A == D + Y = A; + Z = D; + } else { + assert(B == D); + // A + D == C + D -> A == C + Y = A; + Z = C; + } if (Value *V = SimplifyICmpInst(Pred, Y, Z, Q, MaxRecurse-1)) return V; } @@ -2304,7 +2522,12 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, return getFalse(ITy); } - // Simplify comparisons of GEPs. + // Simplify comparisons of related pointers using a powerful, recursive + // GEP-walk when we have target data available.. + if (LHS->getType()->isPointerTy()) + if (Constant *C = computePointerICmp(Q.TD, Q.TLI, Pred, LHS, RHS)) + return C; + if (GetElementPtrInst *GLHS = dyn_cast(LHS)) { if (GEPOperator *GRHS = dyn_cast(RHS)) { if (GLHS->getPointerOperand() == GRHS->getPointerOperand() && @@ -2342,7 +2565,7 @@ static Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, } Value *llvm::SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const TargetData *TD, + const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyICmpInst(Predicate, LHS, RHS, Query (TD, TLI, DT), @@ -2439,7 +2662,7 @@ static Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, } Value *llvm::SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const TargetData *TD, + const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyFCmpInst(Predicate, LHS, RHS, Query (TD, TLI, DT), @@ -2474,7 +2697,7 @@ static Value *SimplifySelectInst(Value *CondVal, Value *TrueVal, } Value *llvm::SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, - const TargetData *TD, + const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifySelectInst(Cond, TrueVal, FalseVal, Query (TD, TLI, DT), @@ -2522,7 +2745,7 @@ static Value *SimplifyGEPInst(ArrayRef Ops, const Query &Q, unsigned) { return ConstantExpr::getGetElementPtr(cast(Ops[0]), Ops.slice(1)); } -Value *llvm::SimplifyGEPInst(ArrayRef Ops, const TargetData *TD, +Value *llvm::SimplifyGEPInst(ArrayRef Ops, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyGEPInst(Ops, Query (TD, TLI, DT), RecursionLimit); @@ -2559,7 +2782,7 @@ static Value *SimplifyInsertValueInst(Value *Agg, Value *Val, Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val, ArrayRef Idxs, - const TargetData *TD, + const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyInsertValueInst(Agg, Val, Idxs, Query (TD, TLI, DT), @@ -2607,7 +2830,7 @@ static Value *SimplifyTruncInst(Value *Op, Type *Ty, const Query &Q, unsigned) { return 0; } -Value *llvm::SimplifyTruncInst(Value *Op, Type *Ty, const TargetData *TD, +Value *llvm::SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyTruncInst(Op, Ty, Query (TD, TLI, DT), RecursionLimit); @@ -2623,10 +2846,18 @@ static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, case Instruction::Add: return SimplifyAddInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, Q, MaxRecurse); + case Instruction::FAdd: + return SimplifyFAddInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); + case Instruction::Sub: return SimplifySubInst(LHS, RHS, /*isNSW*/false, /*isNUW*/false, Q, MaxRecurse); + case Instruction::FSub: + return SimplifyFSubInst(LHS, RHS, FastMathFlags(), Q, MaxRecurse); + case Instruction::Mul: return SimplifyMulInst (LHS, RHS, Q, MaxRecurse); + case Instruction::FMul: + return SimplifyFMulInst (LHS, RHS, FastMathFlags(), Q, MaxRecurse); case Instruction::SDiv: return SimplifySDivInst(LHS, RHS, Q, MaxRecurse); case Instruction::UDiv: return SimplifyUDivInst(LHS, RHS, Q, MaxRecurse); case Instruction::FDiv: return SimplifyFDivInst(LHS, RHS, Q, MaxRecurse); @@ -2673,7 +2904,7 @@ static Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, } Value *llvm::SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, - const TargetData *TD, const TargetLibraryInfo *TLI, + const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyBinOp(Opcode, LHS, RHS, Query (TD, TLI, DT), RecursionLimit); } @@ -2688,23 +2919,97 @@ static Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, } Value *llvm::SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const TargetData *TD, const TargetLibraryInfo *TLI, + const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { return ::SimplifyCmpInst(Predicate, LHS, RHS, Query (TD, TLI, DT), RecursionLimit); } -static Value *SimplifyCallInst(CallInst *CI, const Query &) { - // call undef -> undef - if (isa(CI->getCalledValue())) - return UndefValue::get(CI->getType()); +static bool IsIdempotent(Intrinsic::ID ID) { + switch (ID) { + default: return false; + + // Unary idempotent: f(f(x)) = f(x) + case Intrinsic::fabs: + case Intrinsic::floor: + case Intrinsic::ceil: + case Intrinsic::trunc: + case Intrinsic::rint: + case Intrinsic::nearbyint: + return true; + } +} + +template +static Value *SimplifyIntrinsic(Intrinsic::ID IID, IterTy ArgBegin, IterTy ArgEnd, + const Query &Q, unsigned MaxRecurse) { + // Perform idempotent optimizations + if (!IsIdempotent(IID)) + return 0; + + // Unary Ops + if (std::distance(ArgBegin, ArgEnd) == 1) + if (IntrinsicInst *II = dyn_cast(*ArgBegin)) + if (II->getIntrinsicID() == IID) + return II; return 0; } +template +static Value *SimplifyCall(Value *V, IterTy ArgBegin, IterTy ArgEnd, + const Query &Q, unsigned MaxRecurse) { + Type *Ty = V->getType(); + if (PointerType *PTy = dyn_cast(Ty)) + Ty = PTy->getElementType(); + FunctionType *FTy = cast(Ty); + + // call undef -> undef + if (isa(V)) + return UndefValue::get(FTy->getReturnType()); + + Function *F = dyn_cast(V); + if (!F) + return 0; + + if (unsigned IID = F->getIntrinsicID()) + if (Value *Ret = + SimplifyIntrinsic((Intrinsic::ID) IID, ArgBegin, ArgEnd, Q, MaxRecurse)) + return Ret; + + if (!canConstantFoldCallTo(F)) + return 0; + + SmallVector ConstantArgs; + ConstantArgs.reserve(ArgEnd - ArgBegin); + for (IterTy I = ArgBegin, E = ArgEnd; I != E; ++I) { + Constant *C = dyn_cast(*I); + if (!C) + return 0; + ConstantArgs.push_back(C); + } + + return ConstantFoldCall(F, ConstantArgs, Q.TLI); +} + +Value *llvm::SimplifyCall(Value *V, User::op_iterator ArgBegin, + User::op_iterator ArgEnd, const DataLayout *TD, + const TargetLibraryInfo *TLI, + const DominatorTree *DT) { + return ::SimplifyCall(V, ArgBegin, ArgEnd, Query(TD, TLI, DT), + RecursionLimit); +} + +Value *llvm::SimplifyCall(Value *V, ArrayRef Args, + const DataLayout *TD, const TargetLibraryInfo *TLI, + const DominatorTree *DT) { + return ::SimplifyCall(V, Args.begin(), Args.end(), Query(TD, TLI, DT), + RecursionLimit); +} + /// SimplifyInstruction - See if we can compute a simplified version of this /// instruction. If not, this returns null. -Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, +Value *llvm::SimplifyInstruction(Instruction *I, const DataLayout *TD, const TargetLibraryInfo *TLI, const DominatorTree *DT) { Value *Result; @@ -2713,18 +3018,30 @@ Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, default: Result = ConstantFoldInstruction(I, TD, TLI); break; + case Instruction::FAdd: + Result = SimplifyFAddInst(I->getOperand(0), I->getOperand(1), + I->getFastMathFlags(), TD, TLI, DT); + break; case Instruction::Add: Result = SimplifyAddInst(I->getOperand(0), I->getOperand(1), cast(I)->hasNoSignedWrap(), cast(I)->hasNoUnsignedWrap(), TD, TLI, DT); break; + case Instruction::FSub: + Result = SimplifyFSubInst(I->getOperand(0), I->getOperand(1), + I->getFastMathFlags(), TD, TLI, DT); + break; case Instruction::Sub: Result = SimplifySubInst(I->getOperand(0), I->getOperand(1), cast(I)->hasNoSignedWrap(), cast(I)->hasNoUnsignedWrap(), TD, TLI, DT); break; + case Instruction::FMul: + Result = SimplifyFMulInst(I->getOperand(0), I->getOperand(1), + I->getFastMathFlags(), TD, TLI, DT); + break; case Instruction::Mul: Result = SimplifyMulInst(I->getOperand(0), I->getOperand(1), TD, TLI, DT); break; @@ -2798,9 +3115,12 @@ Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, case Instruction::PHI: Result = SimplifyPHINode(cast(I), Query (TD, TLI, DT)); break; - case Instruction::Call: - Result = SimplifyCallInst(cast(I), Query (TD, TLI, DT)); + case Instruction::Call: { + CallSite CS(cast(I)); + Result = SimplifyCall(CS.getCalledValue(), CS.arg_begin(), CS.arg_end(), + TD, TLI, DT); break; + } case Instruction::Trunc: Result = SimplifyTruncInst(I->getOperand(0), I->getType(), TD, TLI, DT); break; @@ -2812,58 +3132,84 @@ Value *llvm::SimplifyInstruction(Instruction *I, const TargetData *TD, return Result == I ? UndefValue::get(I->getType()) : Result; } -/// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then -/// delete the From instruction. In addition to a basic RAUW, this does a -/// recursive simplification of the newly formed instructions. This catches -/// things where one simplification exposes other opportunities. This only -/// simplifies and deletes scalar operations, it does not change the CFG. +/// \brief Implementation of recursive simplification through an instructions +/// uses. /// -void llvm::ReplaceAndSimplifyAllUses(Instruction *From, Value *To, - const TargetData *TD, - const TargetLibraryInfo *TLI, - const DominatorTree *DT) { - assert(From != To && "ReplaceAndSimplifyAllUses(X,X) is not valid!"); - - // FromHandle/ToHandle - This keeps a WeakVH on the from/to values so that - // we can know if it gets deleted out from under us or replaced in a - // recursive simplification. - WeakVH FromHandle(From); - WeakVH ToHandle(To); - - while (!From->use_empty()) { - // Update the instruction to use the new value. - Use &TheUse = From->use_begin().getUse(); - Instruction *User = cast(TheUse.getUser()); - TheUse = To; - - // Check to see if the instruction can be folded due to the operand - // replacement. For example changing (or X, Y) into (or X, -1) can replace - // the 'or' with -1. - Value *SimplifiedVal; - { - // Sanity check to make sure 'User' doesn't dangle across - // SimplifyInstruction. - AssertingVH<> UserHandle(User); - - SimplifiedVal = SimplifyInstruction(User, TD, TLI, DT); - if (SimplifiedVal == 0) continue; - } +/// This is the common implementation of the recursive simplification routines. +/// If we have a pre-simplified value in 'SimpleV', that is forcibly used to +/// replace the instruction 'I'. Otherwise, we simply add 'I' to the list of +/// instructions to process and attempt to simplify it using +/// InstructionSimplify. +/// +/// This routine returns 'true' only when *it* simplifies something. The passed +/// in simplified value does not count toward this. +static bool replaceAndRecursivelySimplifyImpl(Instruction *I, Value *SimpleV, + const DataLayout *TD, + const TargetLibraryInfo *TLI, + const DominatorTree *DT) { + bool Simplified = false; + SmallSetVector Worklist; + + // If we have an explicit value to collapse to, do that round of the + // simplification loop by hand initially. + if (SimpleV) { + for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE; + ++UI) + if (*UI != I) + Worklist.insert(cast(*UI)); + + // Replace the instruction with its simplified value. + I->replaceAllUsesWith(SimpleV); + + // Gracefully handle edge cases where the instruction is not wired into any + // parent block. + if (I->getParent()) + I->eraseFromParent(); + } else { + Worklist.insert(I); + } - // Recursively simplify this user to the new value. - ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, TLI, DT); - From = dyn_cast_or_null((Value*)FromHandle); - To = ToHandle; + // Note that we must test the size on each iteration, the worklist can grow. + for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) { + I = Worklist[Idx]; + + // See if this instruction simplifies. + SimpleV = SimplifyInstruction(I, TD, TLI, DT); + if (!SimpleV) + continue; - assert(ToHandle && "To value deleted by recursive simplification?"); + Simplified = true; - // If the recursive simplification ended up revisiting and deleting - // 'From' then we're done. - if (From == 0) - return; + // Stash away all the uses of the old instruction so we can check them for + // recursive simplifications after a RAUW. This is cheaper than checking all + // uses of To on the recursive step in most cases. + for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE; + ++UI) + Worklist.insert(cast(*UI)); + + // Replace the instruction with its simplified value. + I->replaceAllUsesWith(SimpleV); + + // Gracefully handle edge cases where the instruction is not wired into any + // parent block. + if (I->getParent()) + I->eraseFromParent(); } + return Simplified; +} - // If 'From' has value handles referring to it, do a real RAUW to update them. - From->replaceAllUsesWith(To); +bool llvm::recursivelySimplifyInstruction(Instruction *I, + const DataLayout *TD, + const TargetLibraryInfo *TLI, + const DominatorTree *DT) { + return replaceAndRecursivelySimplifyImpl(I, 0, TD, TLI, DT); +} - From->eraseFromParent(); +bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, + const DataLayout *TD, + const TargetLibraryInfo *TLI, + const DominatorTree *DT) { + assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!"); + assert(SimpleV && "Must provide a simplified value."); + return replaceAndRecursivelySimplifyImpl(I, SimpleV, TD, TLI, DT); }