TargetData *TD;
bool MustPreserveLCSSA;
public:
- static const char ID; // Pass identifcation, replacement for typeid
+ static char ID; // Pass identification, replacement for typeid
InstCombiner() : FunctionPass((intptr_t)&ID) {}
/// AddToWorkList - Add the specified instruction to the worklist if it
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);
Value *EvaluateInDifferentType(Value *V, const Type *Ty, bool isSigned);
};
- const char InstCombiner::ID = 0;
+ char InstCombiner::ID = 0;
RegisterPass<InstCombiner> X("instcombine", "Combine redundant instructions");
}
if (const IntegerType* ITy = dyn_cast<IntegerType>(Ty)) {
if (ITy->getBitWidth() < 32)
return Type::Int32Ty;
- } else if (Ty == Type::FloatTy)
- return Type::DoubleTy;
+ }
return Ty;
}
// 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);
// Signed shift right.
APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
+ // If any of the "high bits" are demanded, we should set the sign bit as
+ // demanded.
+ if (DemandedMask.countLeadingZeros() <= ShiftAmt)
+ DemandedMaskIn.set(BitWidth-1);
if (SimplifyDemandedBits(I->getOperand(0),
DemandedMaskIn,
RHSKnownZero, RHSKnownOne, Depth+1))
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;
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);
return BinaryOperator::createMul(LHS, AddOne(C2));
// X + ~X --> -1 since ~X = -X-1
- if (dyn_castNotVal(LHS) == RHS ||
- dyn_castNotVal(RHS) == LHS)
- return ReplaceInstUsesWith(I, ConstantInt::getAllOnesValue(I.getType()));
+ if (dyn_castNotVal(LHS) == RHS || dyn_castNotVal(RHS) == LHS)
+ return ReplaceInstUsesWith(I, Constant::getAllOnesValue(I.getType()));
// (A & C1)+(B & C2) --> (A & C1)|(B & C2) iff C1&C2 == 0
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;
}
}
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
return &I;
} else {
if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) {
- if (CP->isAllOnesValue())
+ if (CP->isAllOnesValue()) // X & <-1,-1> -> X
return ReplaceInstUsesWith(I, I.getOperand(0));
+ } else if (isa<ConstantAggregateZero>(Op1)) {
+ return ReplaceInstUsesWith(I, Op1); // X & <0,0> -> <0,0>
}
}
}
{
- Value *A = 0, *B = 0;
- if (match(Op0, m_Or(m_Value(A), m_Value(B))))
+ Value *A = 0, *B = 0, *C = 0, *D = 0;
+ if (match(Op0, m_Or(m_Value(A), m_Value(B)))) {
if (A == Op1 || B == Op1) // (A | ?) & A --> A
return ReplaceInstUsesWith(I, Op1);
- if (match(Op1, m_Or(m_Value(A), m_Value(B))))
+
+ // (A|B) & ~(A&B) -> A^B
+ if (match(Op1, m_Not(m_And(m_Value(C), m_Value(D))))) {
+ if ((A == C && B == D) || (A == D && B == C))
+ return BinaryOperator::createXor(A, B);
+ }
+ }
+
+ if (match(Op1, m_Or(m_Value(A), m_Value(B)))) {
if (A == Op0 || B == Op0) // A & (A | ?) --> A
return ReplaceInstUsesWith(I, Op0);
+
+ // ~(A&B) & (A|B) -> A^B
+ if (match(Op0, m_Not(m_And(m_Value(C), m_Value(D))))) {
+ if ((A == C && B == D) || (A == D && B == C))
+ return BinaryOperator::createXor(A, B);
+ }
+ }
if (Op0->hasOneUse() &&
match(Op0, m_Xor(m_Value(A), m_Value(B)))) {
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);
}
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
if (isa<UndefValue>(Op1)) // X | undef -> -1
- return ReplaceInstUsesWith(I, ConstantInt::getAllOnesValue(I.getType()));
+ return ReplaceInstUsesWith(I, Constant::getAllOnesValue(I.getType()));
// or X, X = X
if (Op0 == Op1)
if (SimplifyDemandedBits(&I, APInt::getAllOnesValue(BitWidth),
KnownZero, KnownOne))
return &I;
+ } else if (isa<ConstantAggregateZero>(Op1)) {
+ return ReplaceInstUsesWith(I, Op0); // X | <0,0> -> X
+ } else if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) {
+ if (CP->isAllOnesValue()) // X | <-1,-1> -> <-1,-1>
+ return ReplaceInstUsesWith(I, I.getOperand(1));
}
+
+
// or X, -1 == -1
if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
}
// (A & C)|(B & D)
- Value *C, *D;
+ Value *C = 0, *D = 0;
if (match(Op0, m_And(m_Value(A), m_Value(C))) &&
match(Op1, m_And(m_Value(B), m_Value(D)))) {
Value *V1 = 0, *V2 = 0, *V3 = 0;
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);
- }
- }
}
}
if (match(Op0, m_Not(m_Value(A)))) { // ~A | Op1
if (A == Op1) // ~A | A == -1
- return ReplaceInstUsesWith(I,
- ConstantInt::getAllOnesValue(I.getType()));
+ return ReplaceInstUsesWith(I, Constant::getAllOnesValue(I.getType()));
} else {
A = 0;
}
// Note, A is still live here!
if (match(Op1, m_Not(m_Value(B)))) { // Op0 | ~B
if (Op0 == B)
- return ReplaceInstUsesWith(I,
- ConstantInt::getAllOnesValue(I.getType()));
+ return ReplaceInstUsesWith(I, Constant::getAllOnesValue(I.getType()));
// (~A | ~B) == (~(A & B)) - De Morgan's Law
if (A && isOnlyUse(Op0) && isOnlyUse(Op1)) {
LHSCC != ICmpInst::ICMP_UGE && LHSCC != ICmpInst::ICMP_ULE &&
RHSCC != ICmpInst::ICMP_UGE && RHSCC != ICmpInst::ICMP_ULE &&
LHSCC != ICmpInst::ICMP_SGE && LHSCC != ICmpInst::ICMP_SLE &&
- RHSCC != ICmpInst::ICMP_SGE && RHSCC != ICmpInst::ICMP_SLE) {
+ RHSCC != ICmpInst::ICMP_SGE && RHSCC != ICmpInst::ICMP_SLE &&
+ // We can't fold (ugt x, C) | (sgt x, C2).
+ PredicatesFoldable(LHSCC, RHSCC)) {
// Ensure that the larger constant is on the RHS.
- ICmpInst::Predicate GT = ICmpInst::isSignedPredicate(LHSCC) ?
- ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
- Constant *Cmp = ConstantExpr::getICmp(GT, LHSCst, RHSCst);
ICmpInst *LHS = cast<ICmpInst>(Op0);
- if (cast<ConstantInt>(Cmp)->getZExtValue()) {
+ bool NeedsSwap;
+ if (ICmpInst::isSignedPredicate(LHSCC))
+ NeedsSwap = LHSCst->getValue().sgt(RHSCst->getValue());
+ else
+ NeedsSwap = LHSCst->getValue().ugt(RHSCst->getValue());
+
+ if (NeedsSwap) {
std::swap(LHS, RHS);
std::swap(LHSCst, RHSCst);
std::swap(LHSCC, RHSCC);
// 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 (SimplifyDemandedBits(&I, APInt::getAllOnesValue(BitWidth),
KnownZero, KnownOne))
return &I;
+ } else if (isa<ConstantAggregateZero>(Op1)) {
+ return ReplaceInstUsesWith(I, Op0); // X ^ <0,0> -> X
}
+ // Is this a ~ operation?
+ if (Value *NotOp = dyn_castNotVal(&I)) {
+ // ~(~X & Y) --> (X | ~Y) - De Morgan's Law
+ // ~(~X | Y) === (X & ~Y) - De Morgan's Law
+ if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(NotOp)) {
+ if (Op0I->getOpcode() == Instruction::And ||
+ Op0I->getOpcode() == Instruction::Or) {
+ if (dyn_castNotVal(Op0I->getOperand(1))) Op0I->swapOperands();
+ if (Value *Op0NotVal = dyn_castNotVal(Op0I->getOperand(0))) {
+ Instruction *NotY =
+ BinaryOperator::createNot(Op0I->getOperand(1),
+ Op0I->getOperand(1)->getName()+".not");
+ InsertNewInstBefore(NotY, I);
+ if (Op0I->getOpcode() == Instruction::And)
+ return BinaryOperator::createOr(Op0NotVal, NotY);
+ else
+ return BinaryOperator::createAnd(Op0NotVal, NotY);
+ }
+ }
+ }
+ }
+
+
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())
ConstantInt::get(I.getType(), 1));
return BinaryOperator::createAdd(Op0I->getOperand(1), ConstantRHS);
}
-
- // ~(~X & Y) --> (X | ~Y)
- if (Op0I->getOpcode() == Instruction::And && RHS->isAllOnesValue()) {
- if (dyn_castNotVal(Op0I->getOperand(1))) Op0I->swapOperands();
- if (Value *Op0NotVal = dyn_castNotVal(Op0I->getOperand(0))) {
- Instruction *NotY =
- BinaryOperator::createNot(Op0I->getOperand(1),
- Op0I->getOperand(1)->getName()+".not");
- InsertNewInstBefore(NotY, I);
- return BinaryOperator::createOr(Op0NotVal, NotY);
- }
- }
if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
if (Op0I->getOpcode() == Instruction::Add) {
if (Value *X = dyn_castNotVal(Op0)) // ~A ^ A == -1
if (X == Op1)
- return ReplaceInstUsesWith(I,
- ConstantInt::getAllOnesValue(I.getType()));
+ return ReplaceInstUsesWith(I, Constant::getAllOnesValue(I.getType()));
if (Value *X = dyn_castNotVal(Op1)) // A ^ ~A == -1
if (X == Op0)
- return ReplaceInstUsesWith(I, ConstantInt::getAllOnesValue(I.getType()));
+ return ReplaceInstUsesWith(I, Constant::getAllOnesValue(I.getType()));
BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1);
// 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;
}
const Type *DestTy = LHSCI->getType();
Value *RHSCIOp;
- // We only handle extension cast instructions, so far. Enforce this.
+ // Turn icmp (ptrtoint x), (ptrtoint/c) into a compare of the input if the
+ // integer type is the same size as the pointer type.
+ if (LHSCI->getOpcode() == Instruction::PtrToInt &&
+ getTargetData().getPointerSizeInBits() ==
+ cast<IntegerType>(DestTy)->getBitWidth()) {
+ Value *RHSOp = 0;
+ if (Constant *RHSC = dyn_cast<Constant>(ICI.getOperand(1))) {
+ RHSOp = ConstantExpr::getIntToPtr(RHSC, SrcTy);
+ } else if (PtrToIntInst *RHSC = dyn_cast<PtrToIntInst>(ICI.getOperand(1))) {
+ RHSOp = RHSC->getOperand(0);
+ // If the pointer types don't match, insert a bitcast.
+ if (LHSCIOp->getType() != RHSOp->getType())
+ RHSOp = InsertCastBefore(Instruction::BitCast, RHSOp,
+ LHSCIOp->getType(), ICI);
+ }
+
+ if (RHSOp)
+ return new ICmpInst(ICI.getPredicate(), LHSCIOp, RHSOp);
+ }
+
+ // The code below only handles extension cast instructions, so far.
+ // Enforce this.
if (LHSCI->getOpcode() != Instruction::ZExt &&
LHSCI->getOpcode() != Instruction::SExt)
return 0;
/// 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 its eliminable we just
+ // 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 (Instruction::CastOps opc =
if (GEPIdxTy->isSized()) {
SmallVector<Value*, 8> NewIndices;
- // Start with the index over the outer type.
+ // Start with the index over the outer type. Note that the type size
+ // might be zero (even if the offset isn't zero) if the indexed type
+ // is something like [0 x {int, int}]
const Type *IntPtrTy = TD->getIntPtrType();
- int64_t TySize = TD->getTypeSize(GEPIdxTy);
- int64_t FirstIdx = Offset/TySize;
- Offset %= TySize;
+ int64_t FirstIdx = 0;
+ if (int64_t TySize = TD->getTypeSize(GEPIdxTy)) {
+ FirstIdx = Offset/TySize;
+ Offset %= TySize;
- // Handle silly modulus not returning values values [0..TySize).
- if (Offset < 0) {
- --FirstIdx;
- Offset += TySize;
- assert(Offset >= 0);
+ // Handle silly modulus not returning values values [0..TySize).
+ if (Offset < 0) {
+ --FirstIdx;
+ Offset += TySize;
+ assert(Offset >= 0);
+ }
+ assert((uint64_t)Offset < (uint64_t)TySize &&"Out of range offset");
}
NewIndices.push_back(ConstantInt::get(IntPtrTy, FirstIdx));
- assert((uint64_t)Offset < (uint64_t)TySize && "Out of range offset");
// Index into the types. If we fail, set OrigBase to null.
while (Offset) {
if (const StructType *STy = dyn_cast<StructType>(GEPIdxTy)) {
const StructLayout *SL = TD->getStructLayout(STy);
- unsigned Elt = SL->getElementContainingOffset(Offset);
- NewIndices.push_back(ConstantInt::get(Type::Int32Ty, Elt));
+ if (Offset < (int64_t)SL->getSizeInBytes()) {
+ unsigned Elt = SL->getElementContainingOffset(Offset);
+ NewIndices.push_back(ConstantInt::get(Type::Int32Ty, Elt));
- Offset -= SL->getElementOffset(Elt);
- GEPIdxTy = STy->getElementType(Elt);
+ Offset -= SL->getElementOffset(Elt);
+ GEPIdxTy = STy->getElementType(Elt);
+ } else {
+ // Otherwise, we can't index into this, bail out.
+ Offset = 0;
+ OrigBase = 0;
+ }
} else if (isa<ArrayType>(GEPIdxTy) || isa<VectorType>(GEPIdxTy)) {
const SequentialType *STy = cast<SequentialType>(GEPIdxTy);
- uint64_t EltSize = TD->getTypeSize(STy->getElementType());
- NewIndices.push_back(ConstantInt::get(IntPtrTy, Offset/EltSize));
- Offset %= EltSize;
+ if (uint64_t EltSize = TD->getTypeSize(STy->getElementType())) {
+ NewIndices.push_back(ConstantInt::get(IntPtrTy,Offset/EltSize));
+ Offset %= EltSize;
+ } else {
+ NewIndices.push_back(ConstantInt::get(IntPtrTy, 0));
+ }
GEPIdxTy = STy->getElementType();
} else {
// Otherwise, we can't index into this, bail out.
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 (Instruction *V = PromoteCastOfAllocation(CI, *AI))
return V;
- // If the source and destination are pointers, and this cast is equivalent to
- // a getelementptr X, 0, 0, 0... turn it into the appropriate getelementptr.
+ // If the source and destination are pointers, and this cast is equivalent
+ // to a getelementptr X, 0, 0, 0... turn it into the appropriate gep.
// This can enhance SROA and other transforms that want type-safe pointers.
Constant *ZeroUInt = Constant::getNullValue(Type::Int32Ty);
unsigned NumZeros = 0;
case Instruction::AShr:
return Constant::getNullValue(I->getType());
case Instruction::And:
- return ConstantInt::getAllOnesValue(I->getType());
+ return Constant::getAllOnesValue(I->getType());
case Instruction::Mul:
return ConstantInt::get(I->getType(), 1);
}
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;
}
} 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);
const FunctionType *FT = Callee->getFunctionType();
const Type *OldRetTy = Caller->getType();
+ const FunctionType *ActualFT =
+ cast<FunctionType>(cast<PointerType>(CE->getType())->getElementType());
+
+ // If the parameter attributes don't match up, don't do the xform. We don't
+ // want to lose an sret attribute or something.
+ if (FT->getParamAttrs() != ActualFT->getParamAttrs())
+ return false;
+
// Check to see if we are changing the return type...
if (OldRetTy != FT->getReturnType()) {
if (Callee->isDeclaration() && !Caller->use_empty() &&
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 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.
if (!OtherStore || OtherStore->getOperand(1) != SI.getOperand(1))
return false;
} else {
- // Otherwise, the other block ended with a conditional branch. If one of the
+ // Otherwise, the other block ended with a conditional branch. If one of the
// destinations is StoreBB, then we have the if/then case.
if (OtherBr->getSuccessor(0) != StoreBB &&
OtherBr->getSuccessor(1) != StoreBB)
return false;
// Okay, we know that OtherBr now goes to Dest and StoreBB, so this is an
- // if/then triangle. See if there is a store to the same ptr as SI that lives
- // in OtherBB.
+ // if/then triangle. See if there is a store to the same ptr as SI that
+ // lives in OtherBB.
for (;; --BBI) {
// Check to see if we find the matching store.
if ((OtherStore = dyn_cast<StoreInst>(BBI))) {
return false;
break;
}
- // If we find something that may be using the stored value, or if we run out
- // of instructions, we can't do the xform.
+ // If we find something that may be using the stored value, or if we run
+ // out of instructions, we can't do the xform.
if (isa<LoadInst>(BBI) || BBI->mayWriteToMemory() ||
BBI == OtherBB->begin())
return false;
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;
}
projects / oota-llvm.git / blobdiff