//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "instsimplify"
-#include "llvm/GlobalAlias.h"
-#include "llvm/Operator.h"
-#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/ValueTracking.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);
// 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()))
}
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),
- /*isSigned=*/true);
- continue;
- }
-
- APInt TypeSize(IntPtrWidth, TD.getTypeAllocSize(GTI.getIndexedType()),
- /*isSigned=*/true);
- 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()->isPointerTy());
+
+ // 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();
+ 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 (!accumulateGEPOffset(TD, GEP, Offset))
+ if (!GEP->isInBounds() || !GEP->accumulateConstantOffset(*TD, Offset))
break;
V = GEP->getPointerOperand();
} else if (Operator::getOpcode(V) == Instruction::BitCast) {
assert(V->getType()->isPointerTy() && "Unexpected operand type!");
} while (Visited.insert(V));
- Type *IntPtrTy = TD.getIntPtrType(V->getContext());
+ Type *IntPtrTy = TD->getIntPtrType(V->getContext());
return ConstantInt::get(IntPtrTy, Offset);
}
/// \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);
}
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),
}
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 DataLayout *TD,
+ CmpInst::Predicate Pred,
+ Value *LHS, Value *RHS) {
+ // 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;
+ }
+
+ Constant *LHSOffset = stripAndComputeConstantOffsets(TD, LHS);
+ Constant *RHSOffset = stripAndComputeConstantOffsets(TD, RHS);
+
+ // 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;
+
+ return ConstantExpr::getICmp(Pred, LHSOffset, RHSOffset);
+}
/// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
/// fold the result. If not, this returns null.
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);
+ // incoming argument, unless they're both null or they belong to
+ // different functions. The latter happens during inlining.
+ if (Instruction *LHSInst = dyn_cast<Instruction>(LHSPtr))
+ if (Argument *RHSArg = dyn_cast<Argument>(RHSPtr))
+ if (LHSInst->getParent()->getParent() == RHSArg->getParent() &&
+ Pred == CmpInst::ICMP_EQ)
+ return ConstantInt::get(ITy, false);
}
// Assume that the constant null is on the right.
else if (Pred == CmpInst::ICMP_NE)
return ConstantInt::get(ITy, true);
}
- } else if (
isa<Argument>(LHSPtr)) {
+ } else if (
Argument *LHSArg = dyn_cast<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);
+ // An alloca can't be equal to an argument unless they come from separate
+ // functions via inlining.
+ if (AllocaInst *RHSInst = dyn_cast<AllocaInst>(RHSPtr)) {
+ if (LHSArg->getParent() == RHSInst->getParent()->getParent()) {
+ if (Pred == CmpInst::ICMP_EQ)
+ return ConstantInt::get(ITy, false);
+ else if (Pred == CmpInst::ICMP_NE)
+ return ConstantInt::get(ITy, true);
+ }
}
}
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;
}
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, Pred, LHS, RHS))
+ return C;
+
if (GetElementPtrInst *GLHS = dyn_cast<GetElementPtrInst>(LHS)) {
if (GEPOperator *GRHS = dyn_cast<GEPOperator>(RHS)) {
if (GLHS->getPointerOperand() == GRHS->getPointerOperand() &&
}
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 &) {
+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>(CI->getCalledValue()))
- return UndefValue::get(CI->getType());
+ if (isa<UndefValue>(V))
+ return UndefValue::get(FTy->getReturnType());
- return 0;
+ Function *F = dyn_cast<Function>(V);
+ if (!F)
+ return 0;
+
+ 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;
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<Instruction>(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<Instruction *, 8> 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<Instruction>(*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);
+ }
+
+ // 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;
+
+ Simplified = true;
- // Recursively simplify this user to the new value.
- ReplaceAndSimplifyAllUses(User, SimplifiedVal, TD, TLI, DT);
- From = dyn_cast_or_null<Instruction>((Value*)FromHandle);
- To = ToHandle;
+ // 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<Instruction>(*UI));
- assert(ToHandle && "To value deleted by recursive simplification?");
+ // Replace the instruction with its simplified value.
+ I->replaceAllUsesWith(SimpleV);
- // If the recursive simplification ended up revisiting and deleting
- // 'From' then we're done.
- if (From == 0)
- return;
+ // 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);
}
projects / oota-llvm.git / blobdiff