//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "instsimplify"
-#include "llvm/GlobalAlias.h"
-#include "llvm/Operator.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/SetVector.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;
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);
}
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<ConstantInt>(*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<StructType>(*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
Visited.insert(V);
do {
if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
- if (!GEP->isInBounds() || !accumulateGEPOffset(TD, GEP, Offset))
+ if (!GEP->isInBounds() || !GEP->accumulateConstantOffset(*TD, Offset))
break;
V = GEP->getPointerOperand();
} else if (Operator::getOpcode(V) == Instruction::BitCast) {
} 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.
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.
}
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<Constant>(Op0)) {
+ if (Constant *CRHS = dyn_cast<Constant>(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<Instruction>(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<Constant>(Op0)) {
+ if (Constant *CRHS = dyn_cast<Constant>(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<Constant>(Op0)) {
+ if (Constant *CRHS = dyn_cast<Constant>(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,
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);
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);
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);
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);
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);
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);
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);
}
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);
if (Value *V = SimplifyShift(Instruction::LShr, Op0, Op1, Q, MaxRecurse))
return V;
+ // X >> X -> 0
+ if (Op0 == Op1)
+ return Constant::getNullValue(Op0->getType());
+
// undef >>l X -> 0
if (match(Op0, m_Undef()))
return Constant::getNullValue(Op0->getType());
}
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),
if (Value *V = SimplifyShift(Instruction::AShr, Op0, Op1, Q, MaxRecurse))
return V;
+ // X >> X -> 0
+ if (Op0 == Op1)
+ return Constant::getNullValue(Op0->getType());
+
// all ones >>a X -> all ones
if (match(Op0, m_AllOnes()))
return Op0;
}
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),
// 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;
}
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);
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);
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);
return 0;
}
-static Constant *computePointerICmp(const TargetData &TD,
+// 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<ConstantPointerNull>(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:
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);
- 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.
- if (LHS != RHS)
- return 0;
+ // 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<AllocaInst>(LHS) &&
+ (isa<AllocaInst>(RHS) || isa<GlobalVariable>(RHS))) {
+ ConstantInt *LHSOffsetCI = dyn_cast<ConstantInt>(LHSOffset);
+ ConstantInt *RHSOffsetCI = dyn_cast<ConstantInt>(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));
+ }
+ }
- return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset);
+ // Repeat the above check but this time without depending on DataLayout
+ // or being able to compute a precise size.
+ if (!cast<PointerType>(LHS->getType())->isEmptyTy() &&
+ !cast<PointerType>(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
}
}
- // 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 = 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<Instruction>(LHSPtr) && isa<Argument>(RHSPtr) &&
- Pred == CmpInst::ICMP_EQ)
- return ConstantInt::get(ITy, false);
- }
-
- // Assume that the constant null is on the right.
- if (llvm::isKnownNonNull(LHSPtr) && isa<ConstantPointerNull>(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<Argument>(LHSPtr)) {
- RHSPtr = RHSPtr->stripInBoundsOffsets();
- // An alloca can't be equal to an argument.
- if (isa<AllocaInst>(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;
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;
}
}
+ // icmp pred (urem X, Y), Y
if (LBO && match(LBO, m_URem(m_Value(), m_Specific(RHS)))) {
bool KnownNonNegative, KnownNegative;
switch (Pred) {
break;
case ICmpInst::ICMP_SGT:
case ICmpInst::ICMP_SGE:
- ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.TD);
+ ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.TD);
if (!KnownNonNegative)
break;
// fall-through
return getFalse(ITy);
case ICmpInst::ICMP_SLT:
case ICmpInst::ICMP_SLE:
- ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.TD);
+ ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.TD);
if (!KnownNonNegative)
break;
// fall-through
return getTrue(ITy);
}
}
+
+ // icmp pred X, (urem Y, X)
if (RBO && match(RBO, m_URem(m_Value(), m_Specific(LHS)))) {
bool KnownNonNegative, KnownNegative;
switch (Pred) {
break;
case ICmpInst::ICMP_SGT:
case ICmpInst::ICMP_SGE:
- ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.TD);
+ ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.TD);
if (!KnownNonNegative)
break;
// fall-through
return getTrue(ITy);
case ICmpInst::ICMP_SLT:
case ICmpInst::ICMP_SLE:
- ComputeSignBit(RHS, KnownNonNegative, KnownNegative, Q.TD);
+ ComputeSignBit(LHS, KnownNonNegative, KnownNegative, Q.TD);
if (!KnownNonNegative)
break;
// fall-through
// Simplify comparisons of related pointers using a powerful, recursive
// GEP-walk when we have target data available..
- if (Q.TD && LHS->getType()->isPointerTy() && RHS->getType()->isPointerTy())
- if (Constant *C = computePointerICmp(*Q.TD, Pred, LHS, RHS))
+ if (LHS->getType()->isPointerTy())
+ if (Constant *C = computePointerICmp(Q.TD, Q.TLI, Pred, LHS, RHS))
return C;
if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) {
}
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),
}
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),
}
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),
return ConstantExpr::getGetElementPtr(cast<Constant>(Ops[0]), Ops.slice(1));
}
-Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const TargetData *TD,
+Value *llvm::SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout *TD,
const TargetLibraryInfo *TLI,
const DominatorTree *DT) {
return ::SimplifyGEPInst(Ops, Query (TD, TLI, DT), RecursionLimit);
Value *llvm::SimplifyInsertValueInst(Value *Agg, Value *Val,
ArrayRef<unsigned> Idxs,
- const TargetData *TD,
+ const DataLayout *TD,
const TargetLibraryInfo *TLI,
const DominatorTree *DT) {
return ::SimplifyInsertValueInst(Agg, Val, Idxs, Query (TD, TLI, DT),
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);
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);
}
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);
}
}
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<UndefValue>(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 <typename IterTy>
+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<IntrinsicInst>(*ArgBegin))
+ if (II->getIntrinsicID() == IID)
+ return II;
return 0;
}
+template <typename IterTy>
+static Value *SimplifyCall(Value *V, IterTy ArgBegin, IterTy ArgEnd,
+ const Query &Q, unsigned MaxRecurse) {
+ Type *Ty = V->getType();
+ if (PointerType *PTy = dyn_cast<PointerType>(Ty))
+ Ty = PTy->getElementType();
+ FunctionType *FTy = cast<FunctionType>(Ty);
+
+ // call undef -> undef
+ if (isa<UndefValue>(V))
+ return UndefValue::get(FTy->getReturnType());
+
+ Function *F = dyn_cast<Function>(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<Constant *, 4> ConstantArgs;
+ ConstantArgs.reserve(ArgEnd - ArgBegin);
+ for (IterTy I = ArgBegin, E = ArgEnd; I != E; ++I) {
+ Constant *C = dyn_cast<Constant>(*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<Value *> 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;
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<BinaryOperator>(I)->hasNoSignedWrap(),
cast<BinaryOperator>(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<BinaryOperator>(I)->hasNoSignedWrap(),
cast<BinaryOperator>(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;
case Instruction::PHI:
Result = SimplifyPHINode(cast<PHINode>(I), Query (TD, TLI, DT));
break;
- case Instruction::Call:
- Result = SimplifyCallInst(cast<CallInst>(I), Query (TD, TLI, DT));
+ case Instruction::Call: {
+ CallSite CS(cast<CallInst>(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;
/// 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 TargetData *TD,
+ const DataLayout *TD,
const TargetLibraryInfo *TLI,
const DominatorTree *DT) {
bool Simplified = false;
}
bool llvm::recursivelySimplifyInstruction(Instruction *I,
- const TargetData *TD,
+ const DataLayout *TD,
const TargetLibraryInfo *TLI,
const DominatorTree *DT) {
return replaceAndRecursivelySimplifyImpl(I, 0, TD, TLI, DT);
}
bool llvm::replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
- const TargetData *TD,
+ const DataLayout *TD,
const TargetLibraryInfo *TLI,
const DominatorTree *DT) {
assert(I != SimpleV && "replaceAndRecursivelySimplify(X,X) is not valid!");
projects / oota-llvm.git / blobdiff