#include "llvm/Pass.h"
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
+#include "llvm/ParameterAttributes.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
Instruction *visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
Instruction *LHS,
ConstantInt *RHS);
+ Instruction *FoldICmpDivCst(ICmpInst &ICI, BinaryOperator *DivI,
+ ConstantInt *DivRHS);
Instruction *FoldGEPICmp(User *GEPLHS, Value *RHS,
ICmpInst::Predicate Cond, Instruction &I);
private:
Instruction *visitCallSite(CallSite CS);
bool transformConstExprCastCall(CallSite CS);
+ Instruction *transformCallThroughTrampoline(CallSite CS);
public:
// InsertNewInstBefore - insert an instruction New before instruction Old
// could have the specified known zero and known one bits, returning them in
// min/max.
static void ComputeUnsignedMinMaxValuesFromKnownBits(const Type *Ty,
- const APInt& KnownZero,
- const APInt& KnownOne,
- APInt& Min,
- APInt& Max) {
- uint32_t BitWidth = cast<IntegerType>(Ty)->getBitWidth();
+ const APInt &KnownZero,
+ const APInt &KnownOne,
+ APInt &Min, APInt &Max) {
+ uint32_t BitWidth = cast<IntegerType>(Ty)->getBitWidth(); BitWidth = BitWidth;
assert(KnownZero.getBitWidth() == BitWidth &&
KnownOne.getBitWidth() == BitWidth &&
Min.getBitWidth() == BitWidth && Max.getBitWidth() &&
InsertNewInstBefore(cast<Instruction>(NewVal), *I);
return UpdateValueUsesWith(I, NewVal);
}
+
+ // If the sign bit is the only bit demanded by this ashr, then there is no
+ // need to do it, the shift doesn't change the high bit.
+ if (DemandedMask.isSignBit())
+ return UpdateValueUsesWith(I, I->getOperand(0));
if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
uint32_t ShiftAmt = SA->getLimitedValue(BitWidth);
break;
}
case Instruction::BitCast: {
- // Packed->packed casts only.
+ // Vector->vector casts only.
const VectorType *VTy = dyn_cast<VectorType>(I->getOperand(0)->getType());
if (!VTy) break;
unsigned InVWidth = VTy->getNumElements();
unsigned Ratio;
if (VWidth == InVWidth) {
- // If we are converting from <4x i32> -> <4 x f32>, we demand the same
+ // If we are converting from <4 x i32> -> <4 x f32>, we demand the same
// elements as are demanded of us.
Ratio = 1;
InputDemandedElts = DemandedElts;
return MadeChange ? I : 0;
}
-/// @returns true if the specified compare instruction is
+/// @returns true if the specified compare predicate is
/// true when both operands are equal...
-/// @brief Determine if the ICmpInst returns true if both operands are equal
-static bool isTrueWhenEqual(ICmpInst &ICI) {
- ICmpInst::Predicate pred = ICI.getPredicate();
+/// @brief Determine if the icmp Predicate is true when both operands are equal
+static bool isTrueWhenEqual(ICmpInst::Predicate pred) {
return pred == ICmpInst::ICMP_EQ || pred == ICmpInst::ICMP_UGE ||
pred == ICmpInst::ICMP_SGE || pred == ICmpInst::ICMP_ULE ||
pred == ICmpInst::ICMP_SLE;
}
+/// @returns true if the specified compare instruction is
+/// true when both operands are equal...
+/// @brief Determine if the ICmpInst returns true when both operands are equal
+static bool isTrueWhenEqual(ICmpInst &ICI) {
+ return isTrueWhenEqual(ICI.getPredicate());
+}
+
/// AssociativeOpt - Perform an optimization on an associative operator. This
/// function is designed to check a chain of associative operators for a
/// potential to apply a certain optimization. Since the optimization may be
if (I.getNumOperands() == 2) {
Constant *C = cast<Constant>(I.getOperand(1));
for (unsigned i = 0; i != NumPHIValues; ++i) {
- Value *InV;
+ Value *InV = 0;
if (Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i))) {
if (CmpInst *CI = dyn_cast<CmpInst>(&I))
InV = ConstantExpr::getCompare(CI->getPredicate(), InC, C);
if (RHSC->isNullValue())
return ReplaceInstUsesWith(I, LHS);
} else if (ConstantFP *CFP = dyn_cast<ConstantFP>(RHSC)) {
- if (CFP->isExactlyValue(-0.0))
+ if (CFP->isExactlyValue(ConstantFP::getNegativeZero
+ (I.getType())->getValueAPF()))
return ReplaceInstUsesWith(I, LHS);
}
Constant *CP1 = Subtract(ConstantInt::get(I.getType(), 1), C2);
return BinaryOperator::createMul(Op0, CP1);
}
+
+ // X - ((X / Y) * Y) --> X % Y
+ if (Op1I->getOpcode() == Instruction::Mul)
+ if (Instruction *I = dyn_cast<Instruction>(Op1I->getOperand(0)))
+ if (Op0 == I->getOperand(0) &&
+ Op1I->getOperand(1) == I->getOperand(1)) {
+ if (I->getOpcode() == Instruction::SDiv)
+ return BinaryOperator::createSRem(Op0, Op1I->getOperand(1));
+ if (I->getOpcode() == Instruction::UDiv)
+ return BinaryOperator::createURem(Op0, Op1I->getOperand(1));
+ }
}
}
return 0;
}
-/// isSignBitCheck - Given an exploded icmp instruction, return true if it
-/// really just returns true if the most significant (sign) bit is set.
-static bool isSignBitCheck(ICmpInst::Predicate pred, ConstantInt *RHS) {
+/// isSignBitCheck - Given an exploded icmp instruction, return true if the
+/// comparison only checks the sign bit. If it only checks the sign bit, set
+/// TrueIfSigned if the result of the comparison is true when the input value is
+/// signed.
+static bool isSignBitCheck(ICmpInst::Predicate pred, ConstantInt *RHS,
+ bool &TrueIfSigned) {
switch (pred) {
- case ICmpInst::ICMP_SLT:
- // True if LHS s< RHS and RHS == 0
- return RHS->isZero();
- case ICmpInst::ICMP_SLE:
- // True if LHS s<= RHS and RHS == -1
- return RHS->isAllOnesValue();
- case ICmpInst::ICMP_UGE:
- // True if LHS u>= RHS and RHS == high-bit-mask (2^7, 2^15, 2^31, etc)
- return RHS->getValue() ==
- APInt::getSignBit(RHS->getType()->getPrimitiveSizeInBits());
- case ICmpInst::ICMP_UGT:
- // True if LHS u> RHS and RHS == high-bit-mask - 1
- return RHS->getValue() ==
- APInt::getSignedMaxValue(RHS->getType()->getPrimitiveSizeInBits());
- default:
- return false;
+ case ICmpInst::ICMP_SLT: // True if LHS s< 0
+ TrueIfSigned = true;
+ return RHS->isZero();
+ case ICmpInst::ICMP_SLE: // True if LHS s<= RHS and RHS == -1
+ TrueIfSigned = true;
+ return RHS->isAllOnesValue();
+ case ICmpInst::ICMP_SGT: // True if LHS s> -1
+ TrueIfSigned = false;
+ return RHS->isAllOnesValue();
+ case ICmpInst::ICMP_UGT:
+ // True if LHS u> RHS and RHS == high-bit-mask - 1
+ TrueIfSigned = true;
+ return RHS->getValue() ==
+ APInt::getSignedMaxValue(RHS->getType()->getPrimitiveSizeInBits());
+ case ICmpInst::ICMP_UGE:
+ // True if LHS u>= RHS and RHS == high-bit-mask (2^7, 2^15, 2^31, etc)
+ TrueIfSigned = true;
+ return RHS->getValue() ==
+ APInt::getSignBit(RHS->getType()->getPrimitiveSizeInBits());
+ default:
+ return false;
}
}
// "In IEEE floating point, x*1 is not equivalent to x for nans. However,
// ANSI says we can drop signals, so we can do this anyway." (from GCC)
- if (Op1F->getValue() == 1.0)
- return ReplaceInstUsesWith(I, Op0); // Eliminate 'mul double %X, 1.0'
+ // We need a better interface for long double here.
+ if (Op1->getType() == Type::FloatTy || Op1->getType() == Type::DoubleTy)
+ if (Op1F->isExactlyValue(1.0))
+ return ReplaceInstUsesWith(I, Op0); // Eliminate 'mul double %X, 1.0'
}
if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0))
if (ICmpInst *SCI = dyn_cast<ICmpInst>(BoolCast->getOperand(0))) {
Value *SCIOp0 = SCI->getOperand(0), *SCIOp1 = SCI->getOperand(1);
const Type *SCOpTy = SCIOp0->getType();
-
+ bool TIS = false;
+
// If the icmp is true iff the sign bit of X is set, then convert this
// multiply into a shift/and combination.
if (isa<ConstantInt>(SCIOp1) &&
- isSignBitCheck(SCI->getPredicate(), cast<ConstantInt>(SCIOp1))) {
+ isSignBitCheck(SCI->getPredicate(), cast<ConstantInt>(SCIOp1), TIS) &&
+ TIS) {
// Shift the X value right to turn it into "all signbits".
Constant *Amt = ConstantInt::get(SCIOp0->getType(),
SCOpTy->getPrimitiveSizeInBits()-1);
// isMaxValueMinusOne - return true if this is Max-1
static bool isMaxValueMinusOne(const ConstantInt *C, bool isSigned) {
uint32_t TypeBits = C->getType()->getPrimitiveSizeInBits();
- if (isSigned) {
- // Calculate 0111111111..11111
- APInt Val(APInt::getSignedMaxValue(TypeBits));
- return C->getValue() == Val-1;
- }
- return C->getValue() == APInt::getAllOnesValue(TypeBits) - 1;
+ if (!isSigned)
+ return C->getValue() == APInt::getAllOnesValue(TypeBits) - 1;
+ return C->getValue() == APInt::getSignedMaxValue(TypeBits)-1;
}
// isMinValuePlusOne - return true if this is Min+1
static bool isMinValuePlusOne(const ConstantInt *C, bool isSigned) {
- if (isSigned) {
- // Calculate 1111111111000000000000
- uint32_t TypeBits = C->getType()->getPrimitiveSizeInBits();
- APInt Val(APInt::getSignedMinValue(TypeBits));
- return C->getValue() == Val+1;
- }
- return C->getValue() == 1; // unsigned
+ if (!isSigned)
+ return C->getValue() == 1; // unsigned
+
+ // Calculate 1111111111000000000000
+ uint32_t TypeBits = C->getType()->getPrimitiveSizeInBits();
+ return C->getValue() == APInt::getSignedMinValue(TypeBits)+1;
}
// isOneBitSet - Return true if there is exactly one bit set in the specified
/// getICmpValue - This is the complement of getICmpCode, which turns an
/// opcode and two operands into either a constant true or false, or a brand
-/// new /// ICmp instruction. The sign is passed in to determine which kind
+/// new ICmp instruction. The sign is passed in to determine which kind
/// of predicate to use in new icmp instructions.
static Value *getICmpValue(bool sign, unsigned code, Value *LHS, Value *RHS) {
switch (code) {
for (unsigned i = 1, e = ByteValues.size(); i != e; ++i)
if (ByteValues[i] != V)
return 0;
- const Type *Tys[] = { ITy, ITy };
+ const Type *Tys[] = { ITy };
Module *M = I.getParent()->getParent()->getParent();
- Function *F = Intrinsic::getDeclaration(M, Intrinsic::bswap, Tys, 2);
+ Function *F = Intrinsic::getDeclaration(M, Intrinsic::bswap, Tys, 1);
return new CallInst(F, V);
}
InsertNewInstBefore(BinaryOperator::createOr(V2, V3, "tmp"), I);
return BinaryOperator::createAnd(V1, Or);
}
-
- // (V1 & V3)|(V2 & ~V3) -> ((V1 ^ V2) & V3) ^ V2
- if (isOnlyUse(Op0) && isOnlyUse(Op1)) {
- // Try all combination of terms to find V3 and ~V3.
- if (A->hasOneUse() && match(A, m_Not(m_Value(V3)))) {
- if (V3 == B)
- V1 = D, V2 = C;
- else if (V3 == D)
- V1 = B, V2 = C;
- }
- if (B->hasOneUse() && match(B, m_Not(m_Value(V3)))) {
- if (V3 == A)
- V1 = C, V2 = D;
- else if (V3 == C)
- V1 = A, V2 = D;
- }
- if (C->hasOneUse() && match(C, m_Not(m_Value(V3)))) {
- if (V3 == B)
- V1 = D, V2 = A;
- else if (V3 == D)
- V1 = B, V2 = A;
- }
- if (D->hasOneUse() && match(D, m_Not(m_Value(V3)))) {
- if (V3 == A)
- V1 = C, V2 = B;
- else if (V3 == C)
- V1 = A, V2 = B;
- }
- if (V1) {
- A = InsertNewInstBefore(BinaryOperator::createXor(V1, V2, "tmp"), I);
- A = InsertNewInstBefore(BinaryOperator::createAnd(A, V3, "tmp"), I);
- return BinaryOperator::createXor(A, V2);
- }
- }
}
}
// xor X, X = 0, even if X is nested in a sequence of Xor's.
if (Instruction *Result = AssociativeOpt(I, XorSelf(Op1))) {
- assert(Result == &I && "AssociativeOpt didn't work?");
+ assert(Result == &I && "AssociativeOpt didn't work?"); Result=Result;
return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
}
if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
- // xor (icmp A, B), true = not (icmp A, B) = !icmp A, B
- if (ICmpInst *ICI = dyn_cast<ICmpInst>(Op0))
- if (RHS == ConstantInt::getTrue() && ICI->hasOneUse())
+ // xor (cmp A, B), true = not (cmp A, B) = !cmp A, B
+ if (RHS == ConstantInt::getTrue() && Op0->hasOneUse()) {
+ if (ICmpInst *ICI = dyn_cast<ICmpInst>(Op0))
return new ICmpInst(ICI->getInversePredicate(),
ICI->getOperand(0), ICI->getOperand(1));
+ if (FCmpInst *FCI = dyn_cast<FCmpInst>(Op0))
+ return new FCmpInst(FCI->getInversePredicate(),
+ FCI->getOperand(0), FCI->getOperand(1));
+ }
+
if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
// ~(c-X) == X-c-1 == X+(-c-1)
if (Op0I->getOpcode() == Instruction::Sub && RHS->isAllOnesValue())
if (NumDifferences == 0) // SAME GEP?
return ReplaceInstUsesWith(I, // No comparison is needed here.
- ConstantInt::get(Type::Int1Ty,
- Cond == ICmpInst::ICMP_EQ));
+ ConstantInt::get(Type::Int1Ty,
+ isTrueWhenEqual(Cond)));
+
else if (NumDifferences == 1) {
Value *LHSV = GEPLHS->getOperand(DiffOperand);
Value *RHSV = GEPRHS->getOperand(DiffOperand);
if (isa<UndefValue>(Op1)) // X icmp undef -> undef
return ReplaceInstUsesWith(I, UndefValue::get(Type::Int1Ty));
- // icmp of GlobalValues can never equal each other as long as they aren't
- // external weak linkage type.
- if (GlobalValue *GV0 = dyn_cast<GlobalValue>(Op0))
- if (GlobalValue *GV1 = dyn_cast<GlobalValue>(Op1))
- if (!GV0->hasExternalWeakLinkage() || !GV1->hasExternalWeakLinkage())
- return ReplaceInstUsesWith(I, ConstantInt::get(Type::Int1Ty,
- !isTrueWhenEqual(I)));
-
// icmp <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
// addresses never equal each other! We already know that Op0 != Op1.
if ((isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0) ||
// already been handled above, this requires little checking.
//
switch (I.getPredicate()) {
- default: break;
- case ICmpInst::ICMP_ULE:
- return new ICmpInst(ICmpInst::ICMP_ULT, Op0, AddOne(CI));
- case ICmpInst::ICMP_SLE:
- return new ICmpInst(ICmpInst::ICMP_SLT, Op0, AddOne(CI));
- case ICmpInst::ICMP_UGE:
- return new ICmpInst( ICmpInst::ICMP_UGT, Op0, SubOne(CI));
- case ICmpInst::ICMP_SGE:
- return new ICmpInst(ICmpInst::ICMP_SGT, Op0, SubOne(CI));
+ default: break;
+ case ICmpInst::ICMP_ULE:
+ return new ICmpInst(ICmpInst::ICMP_ULT, Op0, AddOne(CI));
+ case ICmpInst::ICMP_SLE:
+ return new ICmpInst(ICmpInst::ICMP_SLT, Op0, AddOne(CI));
+ case ICmpInst::ICMP_UGE:
+ return new ICmpInst( ICmpInst::ICMP_UGT, Op0, SubOne(CI));
+ case ICmpInst::ICMP_SGE:
+ return new ICmpInst(ICmpInst::ICMP_SGT, Op0, SubOne(CI));
}
// See if we can fold the comparison based on bits known to be zero or one
- // in the input.
+ // in the input. If this comparison is a normal comparison, it demands all
+ // bits, if it is a sign bit comparison, it only demands the sign bit.
+
+ bool UnusedBit;
+ bool isSignBit = isSignBitCheck(I.getPredicate(), CI, UnusedBit);
+
uint32_t BitWidth = cast<IntegerType>(Ty)->getBitWidth();
APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
- if (SimplifyDemandedBits(Op0, APInt::getAllOnesValue(BitWidth),
+ if (SimplifyDemandedBits(Op0,
+ isSignBit ? APInt::getSignBit(BitWidth)
+ : APInt::getAllOnesValue(BitWidth),
KnownZero, KnownOne, 0))
return &I;
return Changed ? &I : 0;
}
+
+/// FoldICmpDivCst - Fold "icmp pred, ([su]div X, DivRHS), CmpRHS" where DivRHS
+/// and CmpRHS are both known to be integer constants.
+Instruction *InstCombiner::FoldICmpDivCst(ICmpInst &ICI, BinaryOperator *DivI,
+ ConstantInt *DivRHS) {
+ ConstantInt *CmpRHS = cast<ConstantInt>(ICI.getOperand(1));
+ const APInt &CmpRHSV = CmpRHS->getValue();
+
+ // FIXME: If the operand types don't match the type of the divide
+ // then don't attempt this transform. The code below doesn't have the
+ // logic to deal with a signed divide and an unsigned compare (and
+ // vice versa). This is because (x /s C1) <s C2 produces different
+ // results than (x /s C1) <u C2 or (x /u C1) <s C2 or even
+ // (x /u C1) <u C2. Simply casting the operands and result won't
+ // work. :( The if statement below tests that condition and bails
+ // if it finds it.
+ bool DivIsSigned = DivI->getOpcode() == Instruction::SDiv;
+ if (!ICI.isEquality() && DivIsSigned != ICI.isSignedPredicate())
+ return 0;
+ if (DivRHS->isZero())
+ return 0; // The ProdOV computation fails on divide by zero.
+
+ // Compute Prod = CI * DivRHS. We are essentially solving an equation
+ // of form X/C1=C2. We solve for X by multiplying C1 (DivRHS) and
+ // C2 (CI). By solving for X we can turn this into a range check
+ // instead of computing a divide.
+ ConstantInt *Prod = Multiply(CmpRHS, DivRHS);
+
+ // Determine if the product overflows by seeing if the product is
+ // not equal to the divide. Make sure we do the same kind of divide
+ // as in the LHS instruction that we're folding.
+ bool ProdOV = (DivIsSigned ? ConstantExpr::getSDiv(Prod, DivRHS) :
+ ConstantExpr::getUDiv(Prod, DivRHS)) != CmpRHS;
+
+ // Get the ICmp opcode
+ ICmpInst::Predicate Pred = ICI.getPredicate();
+
+ // Figure out the interval that is being checked. For example, a comparison
+ // like "X /u 5 == 0" is really checking that X is in the interval [0, 5).
+ // Compute this interval based on the constants involved and the signedness of
+ // the compare/divide. This computes a half-open interval, keeping track of
+ // whether either value in the interval overflows. After analysis each
+ // overflow variable is set to 0 if it's corresponding bound variable is valid
+ // -1 if overflowed off the bottom end, or +1 if overflowed off the top end.
+ int LoOverflow = 0, HiOverflow = 0;
+ ConstantInt *LoBound = 0, *HiBound = 0;
+
+
+ if (!DivIsSigned) { // udiv
+ // e.g. X/5 op 3 --> [15, 20)
+ LoBound = Prod;
+ HiOverflow = LoOverflow = ProdOV;
+ if (!HiOverflow)
+ HiOverflow = AddWithOverflow(HiBound, LoBound, DivRHS, false);
+ } else if (DivRHS->getValue().isPositive()) { // Divisor is > 0.
+ if (CmpRHSV == 0) { // (X / pos) op 0
+ // Can't overflow. e.g. X/2 op 0 --> [-1, 2)
+ LoBound = cast<ConstantInt>(ConstantExpr::getNeg(SubOne(DivRHS)));
+ HiBound = DivRHS;
+ } else if (CmpRHSV.isPositive()) { // (X / pos) op pos
+ LoBound = Prod; // e.g. X/5 op 3 --> [15, 20)
+ HiOverflow = LoOverflow = ProdOV;
+ if (!HiOverflow)
+ HiOverflow = AddWithOverflow(HiBound, Prod, DivRHS, true);
+ } else { // (X / pos) op neg
+ // e.g. X/5 op -3 --> [-15-4, -15+1) --> [-19, -14)
+ Constant *DivRHSH = ConstantExpr::getNeg(SubOne(DivRHS));
+ LoOverflow = AddWithOverflow(LoBound, Prod,
+ cast<ConstantInt>(DivRHSH), true) ? -1 : 0;
+ HiBound = AddOne(Prod);
+ HiOverflow = ProdOV ? -1 : 0;
+ }
+ } else { // Divisor is < 0.
+ if (CmpRHSV == 0) { // (X / neg) op 0
+ // e.g. X/-5 op 0 --> [-4, 5)
+ LoBound = AddOne(DivRHS);
+ HiBound = cast<ConstantInt>(ConstantExpr::getNeg(DivRHS));
+ if (HiBound == DivRHS) { // -INTMIN = INTMIN
+ HiOverflow = 1; // [INTMIN+1, overflow)
+ HiBound = 0; // e.g. X/INTMIN = 0 --> X > INTMIN
+ }
+ } else if (CmpRHSV.isPositive()) { // (X / neg) op pos
+ // e.g. X/-5 op 3 --> [-19, -14)
+ HiOverflow = LoOverflow = ProdOV ? -1 : 0;
+ if (!LoOverflow)
+ LoOverflow = AddWithOverflow(LoBound, Prod, AddOne(DivRHS), true) ?-1:0;
+ HiBound = AddOne(Prod);
+ } else { // (X / neg) op neg
+ // e.g. X/-5 op -3 --> [15, 20)
+ LoBound = Prod;
+ LoOverflow = HiOverflow = ProdOV ? 1 : 0;
+ HiBound = Subtract(Prod, DivRHS);
+ }
+
+ // Dividing by a negative swaps the condition. LT <-> GT
+ Pred = ICmpInst::getSwappedPredicate(Pred);
+ }
+
+ Value *X = DivI->getOperand(0);
+ switch (Pred) {
+ default: assert(0 && "Unhandled icmp opcode!");
+ case ICmpInst::ICMP_EQ:
+ if (LoOverflow && HiOverflow)
+ return ReplaceInstUsesWith(ICI, ConstantInt::getFalse());
+ else if (HiOverflow)
+ return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE :
+ ICmpInst::ICMP_UGE, X, LoBound);
+ else if (LoOverflow)
+ return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT :
+ ICmpInst::ICMP_ULT, X, HiBound);
+ else
+ return InsertRangeTest(X, LoBound, HiBound, DivIsSigned, true, ICI);
+ case ICmpInst::ICMP_NE:
+ if (LoOverflow && HiOverflow)
+ return ReplaceInstUsesWith(ICI, ConstantInt::getTrue());
+ else if (HiOverflow)
+ return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT :
+ ICmpInst::ICMP_ULT, X, LoBound);
+ else if (LoOverflow)
+ return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE :
+ ICmpInst::ICMP_UGE, X, HiBound);
+ else
+ return InsertRangeTest(X, LoBound, HiBound, DivIsSigned, false, ICI);
+ case ICmpInst::ICMP_ULT:
+ case ICmpInst::ICMP_SLT:
+ if (LoOverflow == +1) // Low bound is greater than input range.
+ return ReplaceInstUsesWith(ICI, ConstantInt::getTrue());
+ if (LoOverflow == -1) // Low bound is less than input range.
+ return ReplaceInstUsesWith(ICI, ConstantInt::getFalse());
+ return new ICmpInst(Pred, X, LoBound);
+ case ICmpInst::ICMP_UGT:
+ case ICmpInst::ICMP_SGT:
+ if (HiOverflow == +1) // High bound greater than input range.
+ return ReplaceInstUsesWith(ICI, ConstantInt::getFalse());
+ else if (HiOverflow == -1) // High bound less than input range.
+ return ReplaceInstUsesWith(ICI, ConstantInt::getTrue());
+ if (Pred == ICmpInst::ICMP_UGT)
+ return new ICmpInst(ICmpInst::ICMP_UGE, X, HiBound);
+ else
+ return new ICmpInst(ICmpInst::ICMP_SGE, X, HiBound);
+ }
+}
+
+
/// visitICmpInstWithInstAndIntCst - Handle "icmp (instr, intcst)".
///
Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI,
}
break;
- case Instruction::Shl: // (icmp pred (shl X, ShAmt), CI)
- if (ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
- if (ICI.isEquality()) {
- uint32_t TypeBits = RHSV.getBitWidth();
-
- // Check that the shift amount is in range. If not, don't perform
- // undefined shifts. When the shift is visited it will be
- // simplified.
- if (ShAmt->uge(TypeBits))
- break;
-
- // If we are comparing against bits always shifted out, the
- // comparison cannot succeed.
- Constant *Comp =
- ConstantExpr::getShl(ConstantExpr::getLShr(RHS, ShAmt), ShAmt);
- if (Comp != RHS) {// Comparing against a bit that we know is zero.
- bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
- Constant *Cst = ConstantInt::get(Type::Int1Ty, IsICMP_NE);
- return ReplaceInstUsesWith(ICI, Cst);
- }
+ case Instruction::Shl: { // (icmp pred (shl X, ShAmt), CI)
+ ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1));
+ if (!ShAmt) break;
+
+ uint32_t TypeBits = RHSV.getBitWidth();
+
+ // Check that the shift amount is in range. If not, don't perform
+ // undefined shifts. When the shift is visited it will be
+ // simplified.
+ if (ShAmt->uge(TypeBits))
+ break;
+
+ if (ICI.isEquality()) {
+ // If we are comparing against bits always shifted out, the
+ // comparison cannot succeed.
+ Constant *Comp =
+ ConstantExpr::getShl(ConstantExpr::getLShr(RHS, ShAmt), ShAmt);
+ if (Comp != RHS) {// Comparing against a bit that we know is zero.
+ bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
+ Constant *Cst = ConstantInt::get(Type::Int1Ty, IsICMP_NE);
+ return ReplaceInstUsesWith(ICI, Cst);
+ }
+
+ if (LHSI->hasOneUse()) {
+ // Otherwise strength reduce the shift into an and.
+ uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits);
+ Constant *Mask =
+ ConstantInt::get(APInt::getLowBitsSet(TypeBits, TypeBits-ShAmtVal));
- if (LHSI->hasOneUse()) {
- // Otherwise strength reduce the shift into an and.
- uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits);
- Constant *Mask =
- ConstantInt::get(APInt::getLowBitsSet(TypeBits, TypeBits-ShAmtVal));
-
- Instruction *AndI =
- BinaryOperator::createAnd(LHSI->getOperand(0),
- Mask, LHSI->getName()+".mask");
- Value *And = InsertNewInstBefore(AndI, ICI);
- return new ICmpInst(ICI.getPredicate(), And,
- ConstantInt::get(RHSV.lshr(ShAmtVal)));
- }
+ Instruction *AndI =
+ BinaryOperator::createAnd(LHSI->getOperand(0),
+ Mask, LHSI->getName()+".mask");
+ Value *And = InsertNewInstBefore(AndI, ICI);
+ return new ICmpInst(ICI.getPredicate(), And,
+ ConstantInt::get(RHSV.lshr(ShAmtVal)));
}
}
+
+ // Otherwise, if this is a comparison of the sign bit, simplify to and/test.
+ bool TrueIfSigned = false;
+ if (LHSI->hasOneUse() &&
+ isSignBitCheck(ICI.getPredicate(), RHS, TrueIfSigned)) {
+ // (X << 31) <s 0 --> (X&1) != 0
+ Constant *Mask = ConstantInt::get(APInt(TypeBits, 1) <<
+ (TypeBits-ShAmt->getZExtValue()-1));
+ Instruction *AndI =
+ BinaryOperator::createAnd(LHSI->getOperand(0),
+ Mask, LHSI->getName()+".mask");
+ Value *And = InsertNewInstBefore(AndI, ICI);
+
+ return new ICmpInst(TrueIfSigned ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ,
+ And, Constant::getNullValue(And->getType()));
+ }
break;
+ }
case Instruction::LShr: // (icmp pred (shr X, ShAmt), CI)
- case Instruction::AShr:
- if (ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
- if (ICI.isEquality()) {
- // Check that the shift amount is in range. If not, don't perform
- // undefined shifts. When the shift is visited it will be
- // simplified.
- uint32_t TypeBits = RHSV.getBitWidth();
- if (ShAmt->uge(TypeBits))
- break;
- uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits);
-
- // If we are comparing against bits always shifted out, the
- // comparison cannot succeed.
- APInt Comp = RHSV << ShAmtVal;
- if (LHSI->getOpcode() == Instruction::LShr)
- Comp = Comp.lshr(ShAmtVal);
- else
- Comp = Comp.ashr(ShAmtVal);
-
- if (Comp != RHSV) { // Comparing against a bit that we know is zero.
- bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
- Constant *Cst = ConstantInt::get(Type::Int1Ty, IsICMP_NE);
- return ReplaceInstUsesWith(ICI, Cst);
- }
+ case Instruction::AShr: {
+ ConstantInt *ShAmt = dyn_cast<ConstantInt>(LHSI->getOperand(1));
+ if (!ShAmt) break;
+
+ if (ICI.isEquality()) {
+ // Check that the shift amount is in range. If not, don't perform
+ // undefined shifts. When the shift is visited it will be
+ // simplified.
+ uint32_t TypeBits = RHSV.getBitWidth();
+ if (ShAmt->uge(TypeBits))
+ break;
+ uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits);
+
+ // If we are comparing against bits always shifted out, the
+ // comparison cannot succeed.
+ APInt Comp = RHSV << ShAmtVal;
+ if (LHSI->getOpcode() == Instruction::LShr)
+ Comp = Comp.lshr(ShAmtVal);
+ else
+ Comp = Comp.ashr(ShAmtVal);
+
+ if (Comp != RHSV) { // Comparing against a bit that we know is zero.
+ bool IsICMP_NE = ICI.getPredicate() == ICmpInst::ICMP_NE;
+ Constant *Cst = ConstantInt::get(Type::Int1Ty, IsICMP_NE);
+ return ReplaceInstUsesWith(ICI, Cst);
+ }
+
+ if (LHSI->hasOneUse() || RHSV == 0) {
+ // Otherwise strength reduce the shift into an and.
+ APInt Val(APInt::getHighBitsSet(TypeBits, TypeBits - ShAmtVal));
+ Constant *Mask = ConstantInt::get(Val);
- if (LHSI->hasOneUse() || RHSV == 0) {
- // Otherwise strength reduce the shift into an and.
- APInt Val(APInt::getHighBitsSet(TypeBits, TypeBits - ShAmtVal));
- Constant *Mask = ConstantInt::get(Val);
-
- Instruction *AndI =
- BinaryOperator::createAnd(LHSI->getOperand(0),
- Mask, LHSI->getName()+".mask");
- Value *And = InsertNewInstBefore(AndI, ICI);
- return new ICmpInst(ICI.getPredicate(), And,
- ConstantExpr::getShl(RHS, ShAmt));
- }
+ Instruction *AndI =
+ BinaryOperator::createAnd(LHSI->getOperand(0),
+ Mask, LHSI->getName()+".mask");
+ Value *And = InsertNewInstBefore(AndI, ICI);
+ return new ICmpInst(ICI.getPredicate(), And,
+ ConstantExpr::getShl(RHS, ShAmt));
}
}
break;
+ }
case Instruction::SDiv:
case Instruction::UDiv:
// checked. If there is an overflow on the low or high side, remember
// it, otherwise compute the range [low, hi) bounding the new value.
// See: InsertRangeTest above for the kinds of replacements possible.
- if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
- // FIXME: If the operand types don't match the type of the divide
- // then don't attempt this transform. The code below doesn't have the
- // logic to deal with a signed divide and an unsigned compare (and
- // vice versa). This is because (x /s C1) <s C2 produces different
- // results than (x /s C1) <u C2 or (x /u C1) <s C2 or even
- // (x /u C1) <u C2. Simply casting the operands and result won't
- // work. :( The if statement below tests that condition and bails
- // if it finds it.
- bool DivIsSigned = LHSI->getOpcode() == Instruction::SDiv;
- if (!ICI.isEquality() && DivIsSigned != ICI.isSignedPredicate())
- break;
- if (DivRHS->isZero())
- break; // Don't hack on div by zero
-
- // Initialize the variables that will indicate the nature of the
- // range check.
- bool LoOverflow = false, HiOverflow = false;
- ConstantInt *LoBound = 0, *HiBound = 0;
-
- // Compute Prod = CI * DivRHS. We are essentially solving an equation
- // of form X/C1=C2. We solve for X by multiplying C1 (DivRHS) and
- // C2 (CI). By solving for X we can turn this into a range check
- // instead of computing a divide.
- ConstantInt *Prod = Multiply(RHS, DivRHS);
-
- // Determine if the product overflows by seeing if the product is
- // not equal to the divide. Make sure we do the same kind of divide
- // as in the LHS instruction that we're folding.
- bool ProdOV = (DivIsSigned ? ConstantExpr::getSDiv(Prod, DivRHS) :
- ConstantExpr::getUDiv(Prod, DivRHS)) != RHS;
-
- // Get the ICmp opcode
- ICmpInst::Predicate predicate = ICI.getPredicate();
-
- if (!DivIsSigned) { // udiv
- LoBound = Prod;
- LoOverflow = ProdOV;
- HiOverflow = ProdOV ||
- AddWithOverflow(HiBound, LoBound, DivRHS, false);
- } else if (DivRHS->getValue().isPositive()) { // Divisor is > 0.
- if (RHSV == 0) { // (X / pos) op 0
- // Can't overflow.
- LoBound = cast<ConstantInt>(ConstantExpr::getNeg(SubOne(DivRHS)));
- HiBound = DivRHS;
- } else if (RHSV.isPositive()) { // (X / pos) op pos
- LoBound = Prod;
- LoOverflow = ProdOV;
- HiOverflow = ProdOV ||
- AddWithOverflow(HiBound, Prod, DivRHS, true);
- } else { // (X / pos) op neg
- Constant *DivRHSH = ConstantExpr::getNeg(SubOne(DivRHS));
- LoOverflow = AddWithOverflow(LoBound, Prod,
- cast<ConstantInt>(DivRHSH), true);
- HiBound = AddOne(Prod);
- HiOverflow = ProdOV;
- }
- } else { // Divisor is < 0.
- if (RHSV == 0) { // (X / neg) op 0
- LoBound = AddOne(DivRHS);
- HiBound = cast<ConstantInt>(ConstantExpr::getNeg(DivRHS));
- if (HiBound == DivRHS)
- LoBound = 0; // - INTMIN = INTMIN
- } else if (RHSV.isPositive()) { // (X / neg) op pos
- HiOverflow = LoOverflow = ProdOV;
- if (!LoOverflow)
- LoOverflow = AddWithOverflow(LoBound, Prod, AddOne(DivRHS),
- true);
- HiBound = AddOne(Prod);
- } else { // (X / neg) op neg
- LoBound = Prod;
- LoOverflow = HiOverflow = ProdOV;
- HiBound = Subtract(Prod, DivRHS);
- }
-
- // Dividing by a negate swaps the condition.
- predicate = ICmpInst::getSwappedPredicate(predicate);
- }
-
- if (LoBound) {
- Value *X = LHSI->getOperand(0);
- switch (predicate) {
- default: assert(0 && "Unhandled icmp opcode!");
- case ICmpInst::ICMP_EQ:
- if (LoOverflow && HiOverflow)
- return ReplaceInstUsesWith(ICI, ConstantInt::getFalse());
- else if (HiOverflow)
- return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE :
- ICmpInst::ICMP_UGE, X, LoBound);
- else if (LoOverflow)
- return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT :
- ICmpInst::ICMP_ULT, X, HiBound);
- else
- return InsertRangeTest(X, LoBound, HiBound, DivIsSigned,
- true, ICI);
- case ICmpInst::ICMP_NE:
- if (LoOverflow && HiOverflow)
- return ReplaceInstUsesWith(ICI, ConstantInt::getTrue());
- else if (HiOverflow)
- return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SLT :
- ICmpInst::ICMP_ULT, X, LoBound);
- else if (LoOverflow)
- return new ICmpInst(DivIsSigned ? ICmpInst::ICMP_SGE :
- ICmpInst::ICMP_UGE, X, HiBound);
- else
- return InsertRangeTest(X, LoBound, HiBound, DivIsSigned,
- false, ICI);
- case ICmpInst::ICMP_ULT:
- case ICmpInst::ICMP_SLT:
- if (LoOverflow)
- return ReplaceInstUsesWith(ICI, ConstantInt::getFalse());
- return new ICmpInst(predicate, X, LoBound);
- case ICmpInst::ICMP_UGT:
- case ICmpInst::ICMP_SGT:
- if (HiOverflow)
- return ReplaceInstUsesWith(ICI, ConstantInt::getFalse());
- if (predicate == ICmpInst::ICMP_UGT)
- return new ICmpInst(ICmpInst::ICMP_UGE, X, HiBound);
- else
- return new ICmpInst(ICmpInst::ICMP_SGE, X, HiBound);
- }
- }
- }
+ if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1)))
+ if (Instruction *R = FoldICmpDivCst(ICI, cast<BinaryOperator>(LHSI),
+ DivRHS))
+ return R;
break;
}
assert(Val->getType() == Type::Int32Ty && "Unexpected allocation size type!");
if (ConstantInt *CI = dyn_cast<ConstantInt>(Val)) {
Offset = CI->getZExtValue();
- Scale = 1;
+ Scale = 0;
return ConstantInt::get(Type::Int32Ty, 0);
- } else if (Instruction *I = dyn_cast<Instruction>(Val)) {
- if (I->getNumOperands() == 2) {
- if (ConstantInt *CUI = dyn_cast<ConstantInt>(I->getOperand(1))) {
- if (I->getOpcode() == Instruction::Shl) {
- // This is a value scaled by '1 << the shift amt'.
- Scale = 1U << CUI->getZExtValue();
- Offset = 0;
- return I->getOperand(0);
- } else if (I->getOpcode() == Instruction::Mul) {
- // This value is scaled by 'CUI'.
- Scale = CUI->getZExtValue();
- Offset = 0;
- return I->getOperand(0);
- } else if (I->getOpcode() == Instruction::Add) {
- // We have X+C. Check to see if we really have (X*C2)+C1,
- // where C1 is divisible by C2.
- unsigned SubScale;
- Value *SubVal =
- DecomposeSimpleLinearExpr(I->getOperand(0), SubScale, Offset);
- Offset += CUI->getZExtValue();
- if (SubScale > 1 && (Offset % SubScale == 0)) {
- Scale = SubScale;
- return SubVal;
- }
- }
+ } else if (BinaryOperator *I = dyn_cast<BinaryOperator>(Val)) {
+ if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
+ if (I->getOpcode() == Instruction::Shl) {
+ // This is a value scaled by '1 << the shift amt'.
+ Scale = 1U << RHS->getZExtValue();
+ Offset = 0;
+ return I->getOperand(0);
+ } else if (I->getOpcode() == Instruction::Mul) {
+ // This value is scaled by 'RHS'.
+ Scale = RHS->getZExtValue();
+ Offset = 0;
+ return I->getOperand(0);
+ } else if (I->getOpcode() == Instruction::Add) {
+ // We have X+C. Check to see if we really have (X*C2)+C1,
+ // where C1 is divisible by C2.
+ unsigned SubScale;
+ Value *SubVal =
+ DecomposeSimpleLinearExpr(I->getOperand(0), SubScale, Offset);
+ Offset += RHS->getZExtValue();
+ Scale = SubScale;
+ return SubVal;
}
}
}
/// This is a truncation operation if Ty is smaller than V->getType(), or an
/// extension operation if Ty is larger.
static bool CanEvaluateInDifferentType(Value *V, const IntegerType *Ty,
- int &NumCastsRemoved) {
+ unsigned CastOpc, int &NumCastsRemoved) {
// We can always evaluate constants in another type.
if (isa<ConstantInt>(V))
return true;
const IntegerType *OrigTy = cast<IntegerType>(V->getType());
+ // If this is an extension or truncate, we can often eliminate it.
+ if (isa<TruncInst>(I) || isa<ZExtInst>(I) || isa<SExtInst>(I)) {
+ // If this is a cast from the destination type, we can trivially eliminate
+ // it, and this will remove a cast overall.
+ if (I->getOperand(0)->getType() == Ty) {
+ // If the first operand is itself a cast, and is eliminable, do not count
+ // this as an eliminable cast. We would prefer to eliminate those two
+ // casts first.
+ if (!isa<CastInst>(I->getOperand(0)))
+ ++NumCastsRemoved;
+ return true;
+ }
+ }
+
+ // We can't extend or shrink something that has multiple uses: doing so would
+ // require duplicating the instruction in general, which isn't profitable.
+ if (!I->hasOneUse()) return false;
+
switch (I->getOpcode()) {
case Instruction::Add:
case Instruction::Sub:
case Instruction::And:
case Instruction::Or:
case Instruction::Xor:
- if (!I->hasOneUse()) return false;
// These operators can all arbitrarily be extended or truncated.
- return CanEvaluateInDifferentType(I->getOperand(0), Ty, NumCastsRemoved) &&
- CanEvaluateInDifferentType(I->getOperand(1), Ty, NumCastsRemoved);
+ return CanEvaluateInDifferentType(I->getOperand(0), Ty, CastOpc,
+ NumCastsRemoved) &&
+ CanEvaluateInDifferentType(I->getOperand(1), Ty, CastOpc,
+ NumCastsRemoved);
case Instruction::Shl:
- if (!I->hasOneUse()) return false;
// If we are truncating the result of this SHL, and if it's a shift of a
// constant amount, we can always perform a SHL in a smaller type.
if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
uint32_t BitWidth = Ty->getBitWidth();
if (BitWidth < OrigTy->getBitWidth() &&
CI->getLimitedValue(BitWidth) < BitWidth)
- return CanEvaluateInDifferentType(I->getOperand(0), Ty,NumCastsRemoved);
+ return CanEvaluateInDifferentType(I->getOperand(0), Ty, CastOpc,
+ NumCastsRemoved);
}
break;
case Instruction::LShr:
- if (!I->hasOneUse()) return false;
// If this is a truncate of a logical shr, we can truncate it to a smaller
// lshr iff we know that the bits we would otherwise be shifting in are
// already zeros.
MaskedValueIsZero(I->getOperand(0),
APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) &&
CI->getLimitedValue(BitWidth) < BitWidth) {
- return CanEvaluateInDifferentType(I->getOperand(0), Ty,NumCastsRemoved);
+ return CanEvaluateInDifferentType(I->getOperand(0), Ty, CastOpc,
+ NumCastsRemoved);
}
}
break;
- case Instruction::Trunc:
case Instruction::ZExt:
case Instruction::SExt:
- // If this is a cast from the destination type, we can trivially eliminate
- // it, and this will remove a cast overall.
- if (I->getOperand(0)->getType() == Ty) {
- // If the first operand is itself a cast, and is eliminable, do not count
- // this as an eliminable cast. We would prefer to eliminate those two
- // casts first.
- if (isa<CastInst>(I->getOperand(0)))
- return true;
-
- ++NumCastsRemoved;
+ case Instruction::Trunc:
+ // If this is the same kind of case as our original (e.g. zext+zext), we
+ // can safely replace it. Note that replacing it does not reduce the number
+ // of casts in the input.
+ if (I->getOpcode() == CastOpc)
return true;
- }
+
break;
default:
// TODO: Can handle more cases here.
case Instruction::Trunc:
case Instruction::ZExt:
case Instruction::SExt:
- case Instruction::BitCast:
// If the source type of the cast is the type we're trying for then we can
- // just return the source. There's no need to insert it because its not new.
+ // just return the source. There's no need to insert it because it is not
+ // new.
if (I->getOperand(0)->getType() == Ty)
return I->getOperand(0);
- // Some other kind of cast, which shouldn't happen, so just ..
- // FALL THROUGH
+ // Otherwise, must be the same type of case, so just reinsert a new one.
+ Res = CastInst::create(cast<CastInst>(I)->getOpcode(), I->getOperand(0),
+ Ty, I->getName());
+ break;
default:
// TODO: Can handle more cases here.
assert(0 && "Unreachable!");
Instruction *InstCombiner::commonCastTransforms(CastInst &CI) {
Value *Src = CI.getOperand(0);
- // Casting undef to anything results in undef so might as just replace it and
- // get rid of the cast.
- if (isa<UndefValue>(Src)) // cast undef -> undef
- return ReplaceInstUsesWith(CI, UndefValue::get(CI.getType()));
-
// Many cases of "cast of a cast" are eliminable. If it's eliminable we just
// eliminate it now.
if (CastInst *CSrc = dyn_cast<CastInst>(Src)) { // A->B->C cast
// If we were able to index down into an element, create the GEP
// and bitcast the result. This eliminates one bitcast, potentially
// two.
- Instruction *NGEP = new GetElementPtrInst(OrigBase, &NewIndices[0],
- NewIndices.size(), "");
+ Instruction *NGEP = new GetElementPtrInst(OrigBase,
+ NewIndices.begin(),
+ NewIndices.end(), "");
InsertNewInstBefore(NGEP, CI);
NGEP->takeName(GEP);
int NumCastsRemoved = 0;
if (!isa<BitCastInst>(CI) &&
CanEvaluateInDifferentType(SrcI, cast<IntegerType>(DestTy),
- NumCastsRemoved)) {
+ CI.getOpcode(), NumCastsRemoved)) {
// If this cast is a truncate, evaluting in a different type always
- // eliminates the cast, so it is always a win. If this is a noop-cast
- // this just removes a noop cast which isn't pointful, but simplifies
- // the code. If this is a zero-extension, we need to do an AND to
- // maintain the clear top-part of the computation, so we require that
- // the input have eliminated at least one cast. If this is a sign
- // extension, we insert two new casts (to do the extension) so we
+ // eliminates the cast, so it is always a win. If this is a zero-extension,
+ // we need to do an AND to maintain the clear top-part of the computation,
+ // so we require that the input have eliminated at least one cast. If this
+ // is a sign extension, we insert two new casts (to do the extension) so we
// require that two casts have been eliminated.
bool DoXForm;
switch (CI.getOpcode()) {
case Instruction::SExt:
DoXForm = NumCastsRemoved >= 2;
break;
- case Instruction::BitCast:
- DoXForm = false;
- break;
}
if (DoXForm) {
// If we found a path from the src to dest, create the getelementptr now.
if (SrcElTy == DstElTy) {
SmallVector<Value*, 8> Idxs(NumZeros+1, ZeroUInt);
- return new GetElementPtrInst(Src, &Idxs[0], Idxs.size());
+ return new GetElementPtrInst(Src, Idxs.begin(), Idxs.end(), "",
+ ((Instruction*) NULL));
}
}
if (FCmpInst *FCI = dyn_cast<FCmpInst>(CondVal)) {
if (FCI->getOperand(0) == TrueVal && FCI->getOperand(1) == FalseVal) {
// Transform (X == Y) ? X : Y -> Y
- if (FCI->getPredicate() == FCmpInst::FCMP_OEQ)
+ if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) {
+ // This is not safe in general for floating point:
+ // consider X== -0, Y== +0.
+ // It becomes safe if either operand is a nonzero constant.
+ ConstantFP *CFPt, *CFPf;
+ if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) &&
+ !CFPt->getValueAPF().isZero()) ||
+ ((CFPf = dyn_cast<ConstantFP>(FalseVal)) &&
+ !CFPf->getValueAPF().isZero()))
return ReplaceInstUsesWith(SI, FalseVal);
+ }
// Transform (X != Y) ? X : Y -> X
if (FCI->getPredicate() == FCmpInst::FCMP_ONE)
return ReplaceInstUsesWith(SI, TrueVal);
} else if (FCI->getOperand(0) == FalseVal && FCI->getOperand(1) == TrueVal){
// Transform (X == Y) ? Y : X -> X
- if (FCI->getPredicate() == FCmpInst::FCMP_OEQ)
- return ReplaceInstUsesWith(SI, FalseVal);
+ if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) {
+ // This is not safe in general for floating point:
+ // consider X== -0, Y== +0.
+ // It becomes safe if either operand is a nonzero constant.
+ ConstantFP *CFPt, *CFPf;
+ if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) &&
+ !CFPt->getValueAPF().isZero()) ||
+ ((CFPf = dyn_cast<ConstantFP>(FalseVal)) &&
+ !CFPf->getValueAPF().isZero()))
+ return ReplaceInstUsesWith(SI, FalseVal);
+ }
// Transform (X != Y) ? Y : X -> Y
if (FCI->getPredicate() == FCmpInst::FCMP_ONE)
return ReplaceInstUsesWith(SI, TrueVal);
return 0;
}
-/// GetKnownAlignment - If the specified pointer has an alignment that we can
-/// determine, return it, otherwise return 0.
-static unsigned GetKnownAlignment(Value *V, TargetData *TD) {
+/// GetOrEnforceKnownAlignment - If the specified pointer has an alignment that
+/// we can determine, return it, otherwise return 0. If PrefAlign is specified,
+/// and it is more than the alignment of the ultimate object, see if we can
+/// increase the alignment of the ultimate object, making this check succeed.
+static unsigned GetOrEnforceKnownAlignment(Value *V, TargetData *TD,
+ unsigned PrefAlign = 0) {
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
unsigned Align = GV->getAlignment();
if (Align == 0 && TD)
Align = TD->getPrefTypeAlignment(GV->getType()->getElementType());
+
+ // If there is a large requested alignment and we can, bump up the alignment
+ // of the global.
+ if (PrefAlign > Align && GV->hasInitializer()) {
+ GV->setAlignment(PrefAlign);
+ Align = PrefAlign;
+ }
return Align;
} else if (AllocationInst *AI = dyn_cast<AllocationInst>(V)) {
unsigned Align = AI->getAlignment();
(unsigned)TD->getABITypeAlignment(Type::Int64Ty));
}
}
+
+ // If there is a requested alignment and if this is an alloca, round up. We
+ // don't do this for malloc, because some systems can't respect the request.
+ if (PrefAlign > Align && isa<AllocaInst>(AI)) {
+ AI->setAlignment(PrefAlign);
+ Align = PrefAlign;
+ }
return Align;
} else if (isa<BitCastInst>(V) ||
(isa<ConstantExpr>(V) &&
cast<ConstantExpr>(V)->getOpcode() == Instruction::BitCast)) {
- User *CI = cast<User>(V);
- if (isa<PointerType>(CI->getOperand(0)->getType()))
- return GetKnownAlignment(CI->getOperand(0), TD);
- return 0;
+ return GetOrEnforceKnownAlignment(cast<User>(V)->getOperand(0),
+ TD, PrefAlign);
} else if (User *GEPI = dyn_castGetElementPtr(V)) {
- unsigned BaseAlignment = GetKnownAlignment(GEPI->getOperand(0), TD);
- if (BaseAlignment == 0) return 0;
-
// If all indexes are zero, it is just the alignment of the base pointer.
bool AllZeroOperands = true;
for (unsigned i = 1, e = GEPI->getNumOperands(); i != e; ++i)
AllZeroOperands = false;
break;
}
- if (AllZeroOperands)
- return BaseAlignment;
-
+
+ if (AllZeroOperands) {
+ // Treat this like a bitcast.
+ return GetOrEnforceKnownAlignment(GEPI->getOperand(0), TD, PrefAlign);
+ }
+
+ unsigned BaseAlignment = GetOrEnforceKnownAlignment(GEPI->getOperand(0),TD);
+ if (BaseAlignment == 0) return 0;
+
// Otherwise, if the base alignment is >= the alignment we expect for the
// base pointer type, then we know that the resultant pointer is aligned at
// least as much as its type requires.
const Type *BasePtrTy = GEPI->getOperand(0)->getType();
const PointerType *PtrTy = cast<PointerType>(BasePtrTy);
- if (TD->getABITypeAlignment(PtrTy->getElementType())
- <= BaseAlignment) {
+ unsigned Align = TD->getABITypeAlignment(PtrTy->getElementType());
+ if (Align <= BaseAlignment) {
const Type *GEPTy = GEPI->getType();
const PointerType *GEPPtrTy = cast<PointerType>(GEPTy);
- return TD->getABITypeAlignment(GEPPtrTy->getElementType());
+ Align = std::min(Align, (unsigned)
+ TD->getABITypeAlignment(GEPPtrTy->getElementType()));
+ return Align;
}
return 0;
}
// If we can determine a pointer alignment that is bigger than currently
// set, update the alignment.
if (isa<MemCpyInst>(MI) || isa<MemMoveInst>(MI)) {
- unsigned Alignment1 = GetKnownAlignment(MI->getOperand(1), TD);
- unsigned Alignment2 = GetKnownAlignment(MI->getOperand(2), TD);
+ unsigned Alignment1 = GetOrEnforceKnownAlignment(MI->getOperand(1), TD);
+ unsigned Alignment2 = GetOrEnforceKnownAlignment(MI->getOperand(2), TD);
unsigned Align = std::min(Alignment1, Alignment2);
if (MI->getAlignment()->getZExtValue() < Align) {
MI->setAlignment(ConstantInt::get(Type::Int32Ty, Align));
Changed = true;
}
+
+ // If MemCpyInst length is 1/2/4/8 bytes then replace memcpy with
+ // load/store.
+ ConstantInt *MemOpLength = dyn_cast<ConstantInt>(CI.getOperand(3));
+ if (isa<MemCpyInst>(MI))
+ if (MemOpLength) {
+ unsigned Size = MemOpLength->getZExtValue();
+ unsigned Align = cast<ConstantInt>(CI.getOperand(4))->getZExtValue();
+ const PointerType *PTy = cast<PointerType>(CI.getOperand(1)->getType());
+ const Type *MTy = PTy->getElementType();
+ PointerType *NewPtrTy = NULL;
+ if (MTy == Type::Int8Ty) {
+ if (Size == 8)
+ NewPtrTy = PointerType::get(Type::Int64Ty);
+ else if (Size == 4)
+ NewPtrTy = PointerType::get(Type::Int32Ty);
+ else if (Size == 2)
+ NewPtrTy = PointerType::get(Type::Int16Ty);
+ else if (Size == 1)
+ NewPtrTy = PointerType::get(Type::Int8Ty);
+ } else if (MTy == Type::Int16Ty) {
+ if (Size == 4)
+ NewPtrTy = PointerType::get(Type::Int64Ty);
+ else if (Size == 2)
+ NewPtrTy = PointerType::get(Type::Int32Ty);
+ else if (Size == 1)
+ NewPtrTy = PointerType::get(Type::Int16Ty);
+ } else if (MTy == Type::Int32Ty) {
+ if (Size == 2)
+ NewPtrTy = PointerType::get(Type::Int64Ty);
+ else if (Size == 1)
+ NewPtrTy = PointerType::get(Type::Int32Ty);
+ } else if (MTy == Type::Int64Ty) {
+ if (Size == 1)
+ NewPtrTy = PointerType::get(Type::Int64Ty);
+ }
+ if (NewPtrTy) {
+ Value *Src =
+ InsertCastBefore(Instruction::BitCast,CI.getOperand(2),NewPtrTy,CI);
+ Value *Dest =
+ InsertCastBefore(Instruction::BitCast,CI.getOperand(1),NewPtrTy,CI);
+ Value *L = new LoadInst(Src, "tmp", false, Align, &CI);
+ Value *NS = new StoreInst(L, Dest, false, Align, &CI);
+ CI.replaceAllUsesWith(NS);
+ Changed = true;
+ return EraseInstFromFunction(CI);
+ }
+ }
} else if (isa<MemSetInst>(MI)) {
- unsigned Alignment = GetKnownAlignment(MI->getDest(), TD);
+ unsigned Alignment = GetOrEnforceKnownAlignment(MI->getDest(), TD);
if (MI->getAlignment()->getZExtValue() < Alignment) {
MI->setAlignment(ConstantInt::get(Type::Int32Ty, Alignment));
Changed = true;
case Intrinsic::x86_sse2_loadu_dq:
// Turn PPC lvx -> load if the pointer is known aligned.
// Turn X86 loadups -> load if the pointer is known aligned.
- if (GetKnownAlignment(II->getOperand(1), TD) >= 16) {
+ if (GetOrEnforceKnownAlignment(II->getOperand(1), TD, 16) >= 16) {
Value *Ptr = InsertCastBefore(Instruction::BitCast, II->getOperand(1),
PointerType::get(II->getType()), CI);
return new LoadInst(Ptr);
case Intrinsic::ppc_altivec_stvx:
case Intrinsic::ppc_altivec_stvxl:
// Turn stvx -> store if the pointer is known aligned.
- if (GetKnownAlignment(II->getOperand(2), TD) >= 16) {
+ if (GetOrEnforceKnownAlignment(II->getOperand(2), TD, 16) >= 16) {
const Type *OpPtrTy = PointerType::get(II->getOperand(1)->getType());
Value *Ptr = InsertCastBefore(Instruction::BitCast, II->getOperand(2),
OpPtrTy, CI);
case Intrinsic::x86_sse2_storeu_dq:
case Intrinsic::x86_sse2_storel_dq:
// Turn X86 storeu -> store if the pointer is known aligned.
- if (GetKnownAlignment(II->getOperand(1), TD) >= 16) {
+ if (GetOrEnforceKnownAlignment(II->getOperand(1), TD, 16) >= 16) {
const Type *OpPtrTy = PointerType::get(II->getOperand(2)->getType());
Value *Ptr = InsertCastBefore(Instruction::BitCast, II->getOperand(1),
OpPtrTy, CI);
return EraseInstFromFunction(*CS.getInstruction());
}
+ if (BitCastInst *BC = dyn_cast<BitCastInst>(Callee))
+ if (IntrinsicInst *In = dyn_cast<IntrinsicInst>(BC->getOperand(0)))
+ if (In->getIntrinsicID() == Intrinsic::init_trampoline)
+ return transformCallThroughTrampoline(CS);
+
const PointerType *PTy = cast<PointerType>(Callee->getType());
const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
if (FTy->isVarArg()) {
Instruction *NC;
if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
NC = new InvokeInst(Callee, II->getNormalDest(), II->getUnwindDest(),
- &Args[0], Args.size(), Caller->getName(), Caller);
- cast<InvokeInst>(II)->setCallingConv(II->getCallingConv());
+ Args.begin(), Args.end(), Caller->getName(), Caller);
+ cast<InvokeInst>(NC)->setCallingConv(II->getCallingConv());
} else {
- NC = new CallInst(Callee, &Args[0], Args.size(), Caller->getName(), Caller);
+ NC = new CallInst(Callee, Args.begin(), Args.end(),
+ Caller->getName(), Caller);
if (cast<CallInst>(Caller)->isTailCall())
cast<CallInst>(NC)->setTailCall();
cast<CallInst>(NC)->setCallingConv(cast<CallInst>(Caller)->getCallingConv());
return true;
}
+// transformCallThroughTrampoline - Turn a call to a function created by the
+// init_trampoline intrinsic into a direct call to the underlying function.
+//
+Instruction *InstCombiner::transformCallThroughTrampoline(CallSite CS) {
+ Value *Callee = CS.getCalledValue();
+ const PointerType *PTy = cast<PointerType>(Callee->getType());
+ const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
+
+ IntrinsicInst *Tramp =
+ cast<IntrinsicInst>(cast<BitCastInst>(Callee)->getOperand(0));
+
+ Function *NestF =
+ cast<Function>(IntrinsicInst::StripPointerCasts(Tramp->getOperand(2)));
+ const PointerType *NestFPTy = cast<PointerType>(NestF->getType());
+ const FunctionType *NestFTy = cast<FunctionType>(NestFPTy->getElementType());
+
+ if (const ParamAttrsList *NestAttrs = NestFTy->getParamAttrs()) {
+ unsigned NestIdx = 1;
+ const Type *NestTy = 0;
+ uint16_t NestAttr = 0;
+
+ // Look for a parameter marked with the 'nest' attribute.
+ for (FunctionType::param_iterator I = NestFTy->param_begin(),
+ E = NestFTy->param_end(); I != E; ++NestIdx, ++I)
+ if (NestAttrs->paramHasAttr(NestIdx, ParamAttr::Nest)) {
+ // Record the parameter type and any other attributes.
+ NestTy = *I;
+ NestAttr = NestAttrs->getParamAttrs(NestIdx);
+ break;
+ }
+
+ if (NestTy) {
+ Instruction *Caller = CS.getInstruction();
+ std::vector<Value*> NewArgs;
+ NewArgs.reserve(unsigned(CS.arg_end()-CS.arg_begin())+1);
+
+ // Insert the nest argument into the call argument list, which may
+ // mean appending it.
+ {
+ unsigned Idx = 1;
+ CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
+ do {
+ if (Idx == NestIdx) {
+ // Add the chain argument.
+ Value *NestVal = Tramp->getOperand(3);
+ if (NestVal->getType() != NestTy)
+ NestVal = new BitCastInst(NestVal, NestTy, "nest", Caller);
+ NewArgs.push_back(NestVal);
+ }
+
+ if (I == E)
+ break;
+
+ // Add the original argument.
+ NewArgs.push_back(*I);
+
+ ++Idx, ++I;
+ } while (1);
+ }
+
+ // The trampoline may have been bitcast to a bogus type (FTy).
+ // Handle this by synthesizing a new function type, equal to FTy
+ // with the chain parameter inserted. Likewise for attributes.
+
+ const ParamAttrsList *Attrs = FTy->getParamAttrs();
+ std::vector<const Type*> NewTypes;
+ ParamAttrsVector NewAttrs;
+ NewTypes.reserve(FTy->getNumParams()+1);
+
+ // Add any function result attributes.
+ uint16_t Attr = Attrs ? Attrs->getParamAttrs(0) : 0;
+ if (Attr)
+ NewAttrs.push_back (ParamAttrsWithIndex::get(0, Attr));
+
+ // Insert the chain's type into the list of parameter types, which may
+ // mean appending it. Likewise for the chain's attributes.
+ {
+ unsigned Idx = 1;
+ FunctionType::param_iterator I = FTy->param_begin(),
+ E = FTy->param_end();
+
+ do {
+ if (Idx == NestIdx) {
+ // Add the chain's type and attributes.
+ NewTypes.push_back(NestTy);
+ NewAttrs.push_back(ParamAttrsWithIndex::get(NestIdx, NestAttr));
+ }
+
+ if (I == E)
+ break;
+
+ // Add the original type and attributes.
+ NewTypes.push_back(*I);
+ Attr = Attrs ? Attrs->getParamAttrs(Idx) : 0;
+ if (Attr)
+ NewAttrs.push_back
+ (ParamAttrsWithIndex::get(Idx + (Idx >= NestIdx), Attr));
+
+ ++Idx, ++I;
+ } while (1);
+ }
+
+ // Replace the trampoline call with a direct call. Let the generic
+ // code sort out any function type mismatches.
+ FunctionType *NewFTy =
+ FunctionType::get(FTy->getReturnType(), NewTypes, FTy->isVarArg(),
+ ParamAttrsList::get(NewAttrs));
+ Constant *NewCallee = NestF->getType() == PointerType::get(NewFTy) ?
+ NestF : ConstantExpr::getBitCast(NestF, PointerType::get(NewFTy));
+
+ Instruction *NewCaller;
+ if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
+ NewCaller = new InvokeInst(NewCallee,
+ II->getNormalDest(), II->getUnwindDest(),
+ NewArgs.begin(), NewArgs.end(),
+ Caller->getName(), Caller);
+ cast<InvokeInst>(NewCaller)->setCallingConv(II->getCallingConv());
+ } else {
+ NewCaller = new CallInst(NewCallee, NewArgs.begin(), NewArgs.end(),
+ Caller->getName(), Caller);
+ if (cast<CallInst>(Caller)->isTailCall())
+ cast<CallInst>(NewCaller)->setTailCall();
+ cast<CallInst>(NewCaller)->
+ setCallingConv(cast<CallInst>(Caller)->getCallingConv());
+ }
+ if (Caller->getType() != Type::VoidTy && !Caller->use_empty())
+ Caller->replaceAllUsesWith(NewCaller);
+ Caller->eraseFromParent();
+ RemoveFromWorkList(Caller);
+ return 0;
+ }
+ }
+
+ // Replace the trampoline call with a direct call. Since there is no 'nest'
+ // parameter, there is no need to adjust the argument list. Let the generic
+ // code sort out any function type mismatches.
+ Constant *NewCallee =
+ NestF->getType() == PTy ? NestF : ConstantExpr::getBitCast(NestF, PTy);
+ CS.setCalledFunction(NewCallee);
+ return CS.getInstruction();
+}
+
/// FoldPHIArgBinOpIntoPHI - If we have something like phi [add (a,b), add(c,d)]
/// and if a/b/c/d and the add's all have a single use, turn this into two phi's
/// and a single binop.
// Remember this node, and if we find the cycle, return.
if (!PotentiallyDeadPHIs.insert(PN))
return true;
+
+ // Don't scan crazily complex things.
+ if (PotentiallyDeadPHIs.size() == 16)
+ return false;
if (PHINode *PU = dyn_cast<PHINode>(PN->use_back()))
return DeadPHICycle(PU, PotentiallyDeadPHIs);
// If this GEP instruction doesn't move the pointer, and if the input operand
// is a bitcast of another pointer, just replace the GEP with a bitcast of the
// real input to the dest type.
- if (GEP.hasAllZeroIndices() && isa<BitCastInst>(GEP.getOperand(0)))
- return new BitCastInst(cast<BitCastInst>(GEP.getOperand(0))->getOperand(0),
- GEP.getType());
-
+ if (GEP.hasAllZeroIndices()) {
+ if (BitCastInst *BCI = dyn_cast<BitCastInst>(GEP.getOperand(0))) {
+ // If the bitcast is of an allocation, and the allocation will be
+ // converted to match the type of the cast, don't touch this.
+ if (isa<AllocationInst>(BCI->getOperand(0))) {
+ // See if the bitcast simplifies, if so, don't nuke this GEP yet.
+ if (Instruction *I = visitBitCast(*BCI)) {
+ if (I != BCI) {
+ I->takeName(BCI);
+ BCI->getParent()->getInstList().insert(BCI, I);
+ ReplaceInstUsesWith(*BCI, I);
+ }
+ return &GEP;
+ }
+ }
+ return new BitCastInst(BCI->getOperand(0), GEP.getType());
+ }
+ }
+
// Combine Indices - If the source pointer to this getelementptr instruction
// is a getelementptr instruction, combine the indices of the two
// getelementptr instructions into a single instruction.
}
if (!Indices.empty())
- return new GetElementPtrInst(SrcGEPOperands[0], &Indices[0],
- Indices.size(), GEP.getName());
+ return new GetElementPtrInst(SrcGEPOperands[0], Indices.begin(),
+ Indices.end(), GEP.getName());
} else if (GlobalValue *GV = dyn_cast<GlobalValue>(PtrOp)) {
// GEP of global variable. If all of the indices for this GEP are
if (isa<ArrayType>(SrcElTy) &&
TD->getTypeSize(cast<ArrayType>(SrcElTy)->getElementType()) ==
TD->getTypeSize(ResElTy)) {
+ Value *Idx[2];
+ Idx[0] = Constant::getNullValue(Type::Int32Ty);
+ Idx[1] = GEP.getOperand(1);
Value *V = InsertNewInstBefore(
- new GetElementPtrInst(X, Constant::getNullValue(Type::Int32Ty),
- GEP.getOperand(1), GEP.getName()), GEP);
+ new GetElementPtrInst(X, Idx, Idx + 2, GEP.getName()), GEP);
// V and GEP are both pointer types --> BitCast
return new BitCastInst(V, GEP.getType());
}
}
// Insert the new GEP instruction.
+ Value *Idx[2];
+ Idx[0] = Constant::getNullValue(Type::Int32Ty);
+ Idx[1] = NewIdx;
Instruction *NewGEP =
- new GetElementPtrInst(X, Constant::getNullValue(Type::Int32Ty),
- NewIdx, GEP.getName());
+ new GetElementPtrInst(X, Idx, Idx + 2, GEP.getName());
NewGEP = InsertNewInstBefore(NewGEP, GEP);
// The NewGEP must be pointer typed, so must the old one -> BitCast
return new BitCastInst(NewGEP, GEP.getType());
// insert our getelementptr instruction...
//
Value *NullIdx = Constant::getNullValue(Type::Int32Ty);
- Value *V = new GetElementPtrInst(New, NullIdx, NullIdx,
+ Value *Idx[2];
+ Idx[0] = NullIdx;
+ Idx[1] = NullIdx;
+ Value *V = new GetElementPtrInst(New, Idx, Idx + 2,
New->getName()+".sub", It);
// Now make everything use the getelementptr instead of the original
/// specified pointer, we do a quick local scan of the basic block containing
/// ScanFrom, to determine if the address is already accessed.
static bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom) {
- // If it is an alloca or global variable, it is always safe to load from.
- if (isa<AllocaInst>(V) || isa<GlobalVariable>(V)) return true;
+ // If it is an alloca it is always safe to load from.
+ if (isa<AllocaInst>(V)) return true;
+
+ // If it is a global variable it is mostly safe to load from.
+ if (const GlobalValue *GV = dyn_cast<GlobalVariable>(V))
+ // Don't try to evaluate aliases. External weak GV can be null.
+ return !isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage();
// Otherwise, be a little bit agressive by scanning the local block where we
// want to check to see if the pointer is already being loaded or stored
return false;
}
+/// GetUnderlyingObject - Trace through a series of getelementptrs and bitcasts
+/// until we find the underlying object a pointer is referring to or something
+/// we don't understand. Note that the returned pointer may be offset from the
+/// input, because we ignore GEP indices.
+static Value *GetUnderlyingObject(Value *Ptr) {
+ while (1) {
+ if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
+ if (CE->getOpcode() == Instruction::BitCast ||
+ CE->getOpcode() == Instruction::GetElementPtr)
+ Ptr = CE->getOperand(0);
+ else
+ return Ptr;
+ } else if (BitCastInst *BCI = dyn_cast<BitCastInst>(Ptr)) {
+ Ptr = BCI->getOperand(0);
+ } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) {
+ Ptr = GEP->getOperand(0);
+ } else {
+ return Ptr;
+ }
+ }
+}
+
Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
Value *Op = LI.getOperand(0);
+ // Attempt to improve the alignment.
+ unsigned KnownAlign = GetOrEnforceKnownAlignment(Op, TD);
+ if (KnownAlign > LI.getAlignment())
+ LI.setAlignment(KnownAlign);
+
// load (cast X) --> cast (load X) iff safe
if (isa<CastInst>(Op))
if (Instruction *Res = InstCombineLoadCast(*this, LI))
return Res;
}
}
+
+ // If this load comes from anywhere in a constant global, and if the global
+ // is all undef or zero, we know what it loads.
+ if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GetUnderlyingObject(Op))) {
+ if (GV->isConstant() && GV->hasInitializer()) {
+ if (GV->getInitializer()->isNullValue())
+ return ReplaceInstUsesWith(LI, Constant::getNullValue(LI.getType()));
+ else if (isa<UndefValue>(GV->getInitializer()))
+ return ReplaceInstUsesWith(LI, UndefValue::get(LI.getType()));
+ }
+ }
if (Op->hasOneUse()) {
// Change select and PHI nodes to select values instead of addresses: this
}
}
+ // Attempt to improve the alignment.
+ unsigned KnownAlign = GetOrEnforceKnownAlignment(Ptr, TD);
+ if (KnownAlign > SI.getAlignment())
+ SI.setAlignment(KnownAlign);
+
// Do really simple DSE, to catch cases where there are several consequtive
// stores to the same location, separated by a few arithmetic operations. This
// situation often occurs with bitfield accesses.
// the pointer we're loading and is producing the pointer we're storing,
// then *this* store is dead (X = load P; store X -> P).
if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
- if (LI == Val && LI->getOperand(0) == Ptr) {
+ if (LI == Val && LI->getOperand(0) == Ptr && !SI.isVolatile()) {
EraseInstFromFunction(SI);
++NumCombined;
return 0;
Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) {
- // If packed val is undef, replace extract with scalar undef.
+ // If vector val is undef, replace extract with scalar undef.
if (isa<UndefValue>(EI.getOperand(0)))
return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType()));
- // If packed val is constant 0, replace extract with scalar 0.
+ // If vector val is constant 0, replace extract with scalar 0.
if (isa<ConstantAggregateZero>(EI.getOperand(0)))
return ReplaceInstUsesWith(EI, Constant::getNullValue(EI.getType()));
if (ConstantVector *C = dyn_cast<ConstantVector>(EI.getOperand(0))) {
- // If packed val is constant with uniform operands, replace EI
+ // If vector val is constant with uniform operands, replace EI
// with that operand
Constant *op0 = C->getOperand(0);
for (unsigned i = 1; i < C->getNumOperands(); ++i)
Inst->eraseFromParent();
continue;
}
-
+
IC.AddToWorkList(Inst);
}
}
assert(WorklistMap.empty() && "Worklist empty, but map not?");
+
+ // Do an explicit clear, this shrinks the map if needed.
+ WorklistMap.clear();
return Changed;
}