// simplification happens.
//
// This pass combines things like:
-// %Y = add int 1, %X
-// %Z = add int 1, %Y
+// %Y = add int %X, 1
+// %Z = add int %Y, 1
// into:
-// %Z = add int 2, %X
+// %Z = add int %X, 2
//
// This is a simple worklist driven algorithm.
//
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/InstVisitor.h"
+#include "llvm/Support/PatternMatch.h"
#include "Support/Debug.h"
#include "Support/Statistic.h"
#include <algorithm>
using namespace llvm;
+using namespace llvm::PatternMatch;
namespace {
Statistic<> NumCombined ("instcombine", "Number of insts combined");
Instruction *visitFreeInst(FreeInst &FI);
Instruction *visitLoadInst(LoadInst &LI);
Instruction *visitBranchInst(BranchInst &BI);
+ Instruction *visitSwitchInst(SwitchInst &SI);
// visitInstruction - Specify what to return for unhandled instructions...
Instruction *visitInstruction(Instruction &I) { return 0; }
return V->hasOneUse() || isa<Constant>(V);
}
-// getSignedIntegralType - Given an unsigned integral type, return the signed
-// version of it that has the same size.
-static const Type *getSignedIntegralType(const Type *Ty) {
- switch (Ty->getPrimitiveID()) {
- default: assert(0 && "Invalid unsigned integer type!"); abort();
- case Type::UByteTyID: return Type::SByteTy;
- case Type::UShortTyID: return Type::ShortTy;
- case Type::UIntTyID: return Type::IntTy;
- case Type::ULongTyID: return Type::LongTy;
- }
-}
-
-// getUnsignedIntegralType - Given an signed integral type, return the unsigned
-// version of it that has the same size.
-static const Type *getUnsignedIntegralType(const Type *Ty) {
- switch (Ty->getPrimitiveID()) {
- default: assert(0 && "Invalid signed integer type!"); abort();
- case Type::SByteTyID: return Type::UByteTy;
- case Type::ShortTyID: return Type::UShortTy;
- case Type::IntTyID: return Type::UIntTy;
- case Type::LongTyID: return Type::ULongTy;
- }
-}
-
// getPromotedType - Return the specified type promoted as it would be to pass
// though a va_arg area...
static const Type *getPromotedType(const Type *Ty) {
- switch (Ty->getPrimitiveID()) {
+ switch (Ty->getTypeID()) {
case Type::SByteTyID:
case Type::ShortTyID: return Type::IntTy;
case Type::UByteTyID:
// Constants can be considered to be negated values if they can be folded...
if (Constant *C = dyn_cast<Constant>(V))
- return ConstantExpr::get(Instruction::Sub,
- Constant::getNullValue(V->getType()), C);
+ return ConstantExpr::getNeg(C);
return 0;
}
-static Constant *NotConstant(Constant *C) {
- return ConstantExpr::get(Instruction::Xor, C,
- ConstantIntegral::getAllOnesValue(C->getType()));
-}
-
static inline Value *dyn_castNotVal(Value *V) {
if (BinaryOperator::isNot(V))
return BinaryOperator::getNotArgument(cast<BinaryOperator>(V));
// Constants can be considered to be not'ed values...
if (ConstantIntegral *C = dyn_cast<ConstantIntegral>(V))
- return NotConstant(C);
+ return ConstantExpr::getNot(C);
return 0;
}
return 0;
}
-// dyn_castMaskingAnd - If this value is an And instruction masking a value with
-// a constant, return the constant being anded with.
-//
-template<class ValueType>
-static inline Constant *dyn_castMaskingAnd(ValueType *V) {
- if (Instruction *I = dyn_cast<Instruction>(V))
- if (I->getOpcode() == Instruction::And)
- return dyn_cast<Constant>(I->getOperand(1));
-
- // If this is a constant, it acts just like we were masking with it.
- return dyn_cast<Constant>(V);
-}
-
// Log2 - Calculate the log base 2 for the specified value if it is exactly a
// power of 2.
static unsigned Log2(uint64_t Val) {
Constant *C2;
AddMaskingAnd(Constant *c) : C2(c) {}
bool shouldApply(Value *LHS) const {
- if (Constant *C1 = dyn_castMaskingAnd(LHS))
- return ConstantExpr::get(Instruction::And, C1, C2)->isNullValue();
- return false;
+ ConstantInt *C1;
+ return match(LHS, m_And(m_Value(), m_ConstantInt(C1))) &&
+ ConstantExpr::getAnd(C1, C2)->isNullValue();
}
Instruction *apply(BinaryOperator &Add) const {
- return BinaryOperator::create(Instruction::Or, Add.getOperand(0),
- Add.getOperand(1));
+ return BinaryOperator::createOr(Add.getOperand(0), Add.getOperand(1));
}
};
unsigned NumBits = CI->getType()->getPrimitiveSize()*8;
uint64_t Val = CI->getRawValue() & (1ULL << NumBits)-1;
if (Val == (1ULL << NumBits-1))
- return BinaryOperator::create(Instruction::Xor, LHS, RHS);
+ return BinaryOperator::createXor(LHS, RHS);
}
}
// X + X --> X << 1
- if (I.getType()->isInteger())
+ if (I.getType()->isInteger()) {
if (Instruction *Result = AssociativeOpt(I, AddRHS(RHS))) return Result;
+ }
// -A + B --> B - A
if (Value *V = dyn_castNegVal(LHS))
- return BinaryOperator::create(Instruction::Sub, RHS, V);
+ return BinaryOperator::createSub(RHS, V);
// A + -B --> A - B
if (!isa<Constant>(RHS))
if (Value *V = dyn_castNegVal(RHS))
- return BinaryOperator::create(Instruction::Sub, LHS, V);
+ return BinaryOperator::createSub(LHS, V);
// X*C + X --> X * (C+1)
if (dyn_castFoldableMul(LHS) == RHS) {
Constant *CP1 =
- ConstantExpr::get(Instruction::Add,
+ ConstantExpr::getAdd(
cast<Constant>(cast<Instruction>(LHS)->getOperand(1)),
ConstantInt::get(I.getType(), 1));
- return BinaryOperator::create(Instruction::Mul, RHS, CP1);
+ return BinaryOperator::createMul(RHS, CP1);
}
// X + X*C --> X * (C+1)
if (dyn_castFoldableMul(RHS) == LHS) {
Constant *CP1 =
- ConstantExpr::get(Instruction::Add,
+ ConstantExpr::getAdd(
cast<Constant>(cast<Instruction>(RHS)->getOperand(1)),
ConstantInt::get(I.getType(), 1));
- return BinaryOperator::create(Instruction::Mul, LHS, CP1);
+ return BinaryOperator::createMul(LHS, CP1);
}
// (A & C1)+(B & C2) --> (A & C1)|(B & C2) iff C1&C2 == 0
- if (Constant *C2 = dyn_castMaskingAnd(RHS))
+ ConstantInt *C2;
+ if (match(RHS, m_And(m_Value(), m_ConstantInt(C2))))
if (Instruction *R = AssociativeOpt(I, AddMaskingAnd(C2))) return R;
if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
- if (Instruction *ILHS = dyn_cast<Instruction>(LHS)) {
- switch (ILHS->getOpcode()) {
- case Instruction::Xor:
- // ~X + C --> (C-1) - X
- if (ConstantInt *XorRHS = dyn_cast<ConstantInt>(ILHS->getOperand(1)))
- if (XorRHS->isAllOnesValue())
- return BinaryOperator::create(Instruction::Sub,
- ConstantExpr::get(Instruction::Sub,
- CRHS, ConstantInt::get(I.getType(), 1)),
- ILHS->getOperand(0));
- break;
- case Instruction::Select:
- // Try to fold constant add into select arguments.
- if (Instruction *R = FoldBinOpIntoSelect(I,cast<SelectInst>(ILHS),this))
- return R;
-
- default: break;
- }
+ Value *X;
+ if (match(LHS, m_Not(m_Value(X)))) { // ~X + C --> (C-1) - X
+ Constant *C= ConstantExpr::getSub(CRHS, ConstantInt::get(I.getType(), 1));
+ return BinaryOperator::createSub(C, X);
}
+
+ // Try to fold constant add into select arguments.
+ if (SelectInst *SI = dyn_cast<SelectInst>(LHS))
+ if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
+ return R;
}
return Changed ? &I : 0;
// If this is a 'B = x-(-A)', change to B = x+A...
if (Value *V = dyn_castNegVal(Op1))
- return BinaryOperator::create(Instruction::Add, Op0, V);
+ return BinaryOperator::createAdd(Op0, V);
if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) {
// Replace (-1 - A) with (~A)...
return BinaryOperator::createNot(Op1);
// C - ~X == X + (1+C)
- if (BinaryOperator::isNot(Op1))
- return BinaryOperator::create(Instruction::Add,
- BinaryOperator::getNotArgument(cast<BinaryOperator>(Op1)),
- ConstantExpr::get(Instruction::Add, C,
- ConstantInt::get(I.getType(), 1)));
+ Value *X;
+ if (match(Op1, m_Not(m_Value(X))))
+ return BinaryOperator::createAdd(X,
+ ConstantExpr::getAdd(C, ConstantInt::get(I.getType(), 1)));
// -((uint)X >> 31) -> ((int)X >> 31)
// -((int)X >> 31) -> ((uint)X >> 31)
if (C->isNullValue()) {
if (ConstantUInt *CU = dyn_cast<ConstantUInt>(SI->getOperand(1))) {
const Type *NewTy;
if (SI->getType()->isSigned())
- NewTy = getUnsignedIntegralType(SI->getType());
+ NewTy = SI->getType()->getUnsignedVersion();
else
- NewTy = getSignedIntegralType(SI->getType());
+ NewTy = SI->getType()->getSignedVersion();
// Check to see if we are shifting out everything but the sign bit.
if (CU->getValue() == SI->getType()->getPrimitiveSize()*8-1) {
// Ok, the transformation is safe. Insert a cast of the incoming
Op1I->setOperand(1, IIOp0);
// Create the new top level add instruction...
- return BinaryOperator::create(Instruction::Add, Op0, Op1);
+ return BinaryOperator::createAdd(Op0, Op1);
}
// Replace (A - (A & B)) with (A & ~B) if this is the only use of (A&B)...
(Op1I->getOperand(0) == Op0 || Op1I->getOperand(1) == Op0)) {
Value *OtherOp = Op1I->getOperand(Op1I->getOperand(0) == Op0);
- Instruction *NewNot = BinaryOperator::createNot(OtherOp, "B.not", &I);
- return BinaryOperator::create(Instruction::And, Op0, NewNot);
+ Value *NewNot =
+ InsertNewInstBefore(BinaryOperator::createNot(OtherOp, "B.not"), I);
+ return BinaryOperator::createAnd(Op0, NewNot);
}
// X - X*C --> X * (1-C)
if (dyn_castFoldableMul(Op1I) == Op0) {
Constant *CP1 =
- ConstantExpr::get(Instruction::Sub,
- ConstantInt::get(I.getType(), 1),
+ ConstantExpr::getSub(ConstantInt::get(I.getType(), 1),
cast<Constant>(cast<Instruction>(Op1)->getOperand(1)));
assert(CP1 && "Couldn't constant fold 1-C?");
- return BinaryOperator::create(Instruction::Mul, Op0, CP1);
+ return BinaryOperator::createMul(Op0, CP1);
}
}
// X*C - X --> X * (C-1)
if (dyn_castFoldableMul(Op0) == Op1) {
Constant *CP1 =
- ConstantExpr::get(Instruction::Sub,
- cast<Constant>(cast<Instruction>(Op0)->getOperand(1)),
+ ConstantExpr::getSub(cast<Constant>(cast<Instruction>(Op0)->getOperand(1)),
ConstantInt::get(I.getType(), 1));
assert(CP1 && "Couldn't constant fold C - 1?");
- return BinaryOperator::create(Instruction::Mul, Op1, CP1);
+ return BinaryOperator::createMul(Op1, CP1);
}
return 0;
if (ShiftInst *SI = dyn_cast<ShiftInst>(Op0))
if (SI->getOpcode() == Instruction::Shl)
if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1)))
- return BinaryOperator::create(Instruction::Mul, SI->getOperand(0),
- ConstantExpr::get(Instruction::Shl, CI, ShOp));
+ return BinaryOperator::createMul(SI->getOperand(0),
+ ConstantExpr::getShl(CI, ShOp));
if (CI->isNullValue())
return ReplaceInstUsesWith(I, Op1); // X * 0 == 0
if (uint64_t C = Log2(Val)) // Replace X*(2^C) with X << C
return new ShiftInst(Instruction::Shl, Op0,
ConstantUInt::get(Type::UByteTy, C));
- } else {
- ConstantFP *Op1F = cast<ConstantFP>(Op1);
+ } else if (ConstantFP *Op1F = dyn_cast<ConstantFP>(Op1)) {
if (Op1F->isNullValue())
return ReplaceInstUsesWith(I, Op1);
if (Value *Op0v = dyn_castNegVal(Op0)) // -X * -Y = X*Y
if (Value *Op1v = dyn_castNegVal(I.getOperand(1)))
- return BinaryOperator::create(Instruction::Mul, Op0v, Op1v);
+ return BinaryOperator::createMul(Op0v, Op1v);
// If one of the operands of the multiply is a cast from a boolean value, then
// we know the bool is either zero or one, so this is a 'masking' multiply.
Constant *Amt = ConstantUInt::get(Type::UByteTy,
SCOpTy->getPrimitiveSize()*8-1);
if (SCIOp0->getType()->isUnsigned()) {
- const Type *NewTy = getSignedIntegralType(SCIOp0->getType());
+ const Type *NewTy = SCIOp0->getType()->getSignedVersion();
SCIOp0 = InsertNewInstBefore(new CastInst(SCIOp0, NewTy,
SCIOp0->getName()), I);
}
V = InsertNewInstBefore(new CastInst(V, I.getType(), V->getName()),I);
Value *OtherOp = Op0 == BoolCast ? I.getOperand(1) : Op0;
- return BinaryOperator::create(Instruction::And, V, OtherOp);
+ return BinaryOperator::createAnd(V, OtherOp);
}
}
}
Instruction *InstCombiner::visitRem(BinaryOperator &I) {
+ if (I.getType()->isSigned())
+ if (Value *RHSNeg = dyn_castNegVal(I.getOperand(1)))
+ if (!isa<ConstantSInt>(RHSNeg) ||
+ cast<ConstantSInt>(RHSNeg)->getValue() >= 0) {
+ // X % -Y -> X % Y
+ AddUsesToWorkList(I);
+ I.setOperand(1, RHSNeg);
+ return &I;
+ }
+
if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) {
if (RHS->equalsInt(1)) // X % 1 == 0
return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
- if (RHS->isAllOnesValue()) // X % -1 == 0
- return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
// Check to see if this is an unsigned remainder with an exact power of 2,
// if so, convert to a bitwise and.
if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
if (uint64_t Val = C->getValue()) // Don't break X % 0 (divide by zero)
- if (Log2(Val))
- return BinaryOperator::create(Instruction::And, I.getOperand(0),
+ if (!(Val & (Val-1))) // Power of 2
+ return BinaryOperator::createAnd(I.getOperand(0),
ConstantUInt::get(I.getType(), Val-1));
}
return CS->getValue() == Val+1;
}
+// isOneBitSet - Return true if there is exactly one bit set in the specified
+// constant.
+static bool isOneBitSet(const ConstantInt *CI) {
+ uint64_t V = CI->getRawValue();
+ return V && (V & (V-1)) == 0;
+}
+
/// getSetCondCode - Encode a setcc opcode into a three bit mask. These bits
/// are carefully arranged to allow folding of expressions such as:
///
Value *X = Op->getOperand(0);
Constant *Together = 0;
if (!isa<ShiftInst>(Op))
- Together = ConstantExpr::get(Instruction::And, AndRHS, OpRHS);
+ Together = ConstantExpr::getAnd(AndRHS, OpRHS);
switch (Op->getOpcode()) {
case Instruction::Xor:
if (Together->isNullValue()) {
// (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0
- return BinaryOperator::create(Instruction::And, X, AndRHS);
+ return BinaryOperator::createAnd(X, AndRHS);
} else if (Op->hasOneUse()) {
// (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
std::string OpName = Op->getName(); Op->setName("");
- Instruction *And = BinaryOperator::create(Instruction::And,
- X, AndRHS, OpName);
+ Instruction *And = BinaryOperator::createAnd(X, AndRHS, OpName);
InsertNewInstBefore(And, TheAnd);
- return BinaryOperator::create(Instruction::Xor, And, Together);
+ return BinaryOperator::createXor(And, Together);
}
break;
case Instruction::Or:
// (X | C1) & C2 --> X & C2 iff C1 & C1 == 0
if (Together->isNullValue())
- return BinaryOperator::create(Instruction::And, X, AndRHS);
+ return BinaryOperator::createAnd(X, AndRHS);
else {
if (Together == AndRHS) // (X | C) & C --> C
return ReplaceInstUsesWith(TheAnd, AndRHS);
if (Op->hasOneUse() && Together != OpRHS) {
// (X | C1) & C2 --> (X | (C1&C2)) & C2
std::string Op0Name = Op->getName(); Op->setName("");
- Instruction *Or = BinaryOperator::create(Instruction::Or, X,
- Together, Op0Name);
+ Instruction *Or = BinaryOperator::createOr(X, Together, Op0Name);
InsertNewInstBefore(Or, TheAnd);
- return BinaryOperator::create(Instruction::And, Or, AndRHS);
+ return BinaryOperator::createAnd(Or, AndRHS);
}
}
break;
// Adding a one to a single bit bit-field should be turned into an XOR
// of the bit. First thing to check is to see if this AND is with a
// single bit constant.
- unsigned long long AndRHSV = cast<ConstantInt>(AndRHS)->getRawValue();
+ uint64_t AndRHSV = cast<ConstantInt>(AndRHS)->getRawValue();
// Clear bits that are not part of the constant.
AndRHSV &= (1ULL << AndRHS->getType()->getPrimitiveSize()*8)-1;
// If there is only one bit set...
- if ((AndRHSV & (AndRHSV-1)) == 0) {
+ if (isOneBitSet(cast<ConstantInt>(AndRHS))) {
// Ok, at this point, we know that we are masking the result of the
// ADD down to exactly one bit. If the constant we are adding has
// no bits set below this bit, then we can eliminate the ADD.
- unsigned long long AddRHS = cast<ConstantInt>(OpRHS)->getRawValue();
+ uint64_t AddRHS = cast<ConstantInt>(OpRHS)->getRawValue();
// Check to see if any bits below the one bit set in AndRHSV are set.
if ((AddRHS & (AndRHSV-1)) == 0) {
} else {
std::string Name = Op->getName(); Op->setName("");
// Pull the XOR out of the AND.
- Instruction *NewAnd =
- BinaryOperator::create(Instruction::And, X, AndRHS, Name);
+ Instruction *NewAnd = BinaryOperator::createAnd(X, AndRHS, Name);
InsertNewInstBefore(NewAnd, TheAnd);
- return BinaryOperator::create(Instruction::Xor, NewAnd, AndRHS);
+ return BinaryOperator::createXor(NewAnd, AndRHS);
}
}
}
// the anded constant includes them, clear them now!
//
Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
- Constant *CI = ConstantExpr::get(Instruction::And, AndRHS,
- ConstantExpr::get(Instruction::Shl, AllOne, OpRHS));
+ Constant *CI = ConstantExpr::getAnd(AndRHS,
+ ConstantExpr::getShl(AllOne, OpRHS));
if (CI != AndRHS) {
TheAnd.setOperand(1, CI);
return &TheAnd;
//
if (AndRHS->getType()->isUnsigned()) {
Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
- Constant *CI = ConstantExpr::get(Instruction::And, AndRHS,
- ConstantExpr::get(Instruction::Shr, AllOne, OpRHS));
+ Constant *CI = ConstantExpr::getAnd(AndRHS,
+ ConstantExpr::getShr(AllOne, OpRHS));
if (CI != AndRHS) {
TheAnd.setOperand(1, CI);
return &TheAnd;
Value *Op0NotVal = dyn_castNotVal(Op0);
Value *Op1NotVal = dyn_castNotVal(Op1);
- // (~A & ~B) == (~(A | B)) - Demorgan's Law
+ if (Op0NotVal == Op1 || Op1NotVal == Op0) // A & ~A == ~A & A == 0
+ return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
+
+ // (~A & ~B) == (~(A | B)) - De Morgan's Law
if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
- Instruction *Or = BinaryOperator::create(Instruction::Or, Op0NotVal,
- Op1NotVal,I.getName()+".demorgan");
+ Instruction *Or = BinaryOperator::createOr(Op0NotVal, Op1NotVal,
+ I.getName()+".demorgan");
InsertNewInstBefore(Or, I);
return BinaryOperator::createNot(Or);
}
- if (Op0NotVal == Op1 || Op1NotVal == Op0) // A & ~A == ~A & A == 0
- return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
-
// (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
if (RHS->isAllOnesValue())
return ReplaceInstUsesWith(I, Op1);
- if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
- // (X & C1) | C2 --> (X | C2) & (C1|C2)
- if (Op0I->getOpcode() == Instruction::And && isOnlyUse(Op0))
- if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
- std::string Op0Name = Op0I->getName(); Op0I->setName("");
- Instruction *Or = BinaryOperator::create(Instruction::Or,
- Op0I->getOperand(0), RHS,
- Op0Name);
- InsertNewInstBefore(Or, I);
- return BinaryOperator::create(Instruction::And, Or,
- ConstantExpr::get(Instruction::Or, RHS, Op0CI));
- }
+ ConstantInt *C1; Value *X;
+ // (X & C1) | C2 --> (X | C2) & (C1|C2)
+ if (match(Op0, m_And(m_Value(X), m_ConstantInt(C1))) && isOnlyUse(Op0)) {
+ std::string Op0Name = Op0->getName(); Op0->setName("");
+ Instruction *Or = BinaryOperator::createOr(X, RHS, Op0Name);
+ InsertNewInstBefore(Or, I);
+ return BinaryOperator::createAnd(Or, ConstantExpr::getOr(RHS, C1));
+ }
- // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2)
- if (Op0I->getOpcode() == Instruction::Xor && isOnlyUse(Op0))
- if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
- std::string Op0Name = Op0I->getName(); Op0I->setName("");
- Instruction *Or = BinaryOperator::create(Instruction::Or,
- Op0I->getOperand(0), RHS,
- Op0Name);
- InsertNewInstBefore(Or, I);
- return BinaryOperator::create(Instruction::Xor, Or,
- ConstantExpr::get(Instruction::And, Op0CI,
- NotConstant(RHS)));
- }
+ // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2)
+ if (match(Op0, m_Xor(m_Value(X), m_ConstantInt(C1))) && isOnlyUse(Op0)) {
+ std::string Op0Name = Op0->getName(); Op0->setName("");
+ Instruction *Or = BinaryOperator::createOr(X, RHS, Op0Name);
+ InsertNewInstBefore(Or, I);
+ return BinaryOperator::createXor(Or,
+ ConstantExpr::getAnd(C1, ConstantExpr::getNot(RHS)));
}
// Try to fold constant and into select arguments.
}
// (A & C1)|(A & C2) == A & (C1|C2)
- if (Instruction *LHS = dyn_cast<BinaryOperator>(Op0))
- if (Instruction *RHS = dyn_cast<BinaryOperator>(Op1))
- if (LHS->getOperand(0) == RHS->getOperand(0))
- if (Constant *C0 = dyn_castMaskingAnd(LHS))
- if (Constant *C1 = dyn_castMaskingAnd(RHS))
- return BinaryOperator::create(Instruction::And, LHS->getOperand(0),
- ConstantExpr::get(Instruction::Or, C0, C1));
-
- Value *Op0NotVal = dyn_castNotVal(Op0);
- Value *Op1NotVal = dyn_castNotVal(Op1);
-
- if (Op1 == Op0NotVal) // ~A | A == -1
- return ReplaceInstUsesWith(I,
- ConstantIntegral::getAllOnesValue(I.getType()));
+ Value *A, *B; ConstantInt *C1, *C2;
+ if (match(Op0, m_And(m_Value(A), m_ConstantInt(C1))) &&
+ match(Op1, m_And(m_Value(B), m_ConstantInt(C2))) && A == B)
+ return BinaryOperator::createAnd(A, ConstantExpr::getOr(C1, C2));
+
+ if (match(Op0, m_Not(m_Value(A)))) { // ~A | Op1
+ if (A == Op1) // ~A | A == -1
+ return ReplaceInstUsesWith(I,
+ ConstantIntegral::getAllOnesValue(I.getType()));
+ } else {
+ A = 0;
+ }
- if (Op0 == Op1NotVal) // A | ~A == -1
- return ReplaceInstUsesWith(I,
- ConstantIntegral::getAllOnesValue(I.getType()));
+ if (match(Op1, m_Not(m_Value(B)))) { // Op0 | ~B
+ if (Op0 == B)
+ return ReplaceInstUsesWith(I,
+ ConstantIntegral::getAllOnesValue(I.getType()));
- // (~A | ~B) == (~(A & B)) - Demorgan's Law
- if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
- Instruction *And = BinaryOperator::create(Instruction::And, Op0NotVal,
- Op1NotVal,I.getName()+".demorgan",
- &I);
- WorkList.push_back(And);
- return BinaryOperator::createNot(And);
+ // (~A | ~B) == (~(A & B)) - De Morgan's Law
+ if (A && isOnlyUse(Op0) && isOnlyUse(Op1)) {
+ Value *And = InsertNewInstBefore(BinaryOperator::createAnd(A, B,
+ I.getName()+".demorgan"), I);
+ return BinaryOperator::createNot(And);
+ }
}
// (setcc1 A, B) | (setcc2 A, B) --> (setcc3 A, B)
// ~(c-X) == X-c-1 == X+(-c-1)
if (Op0I->getOpcode() == Instruction::Sub && RHS->isAllOnesValue())
if (Constant *Op0I0C = dyn_cast<Constant>(Op0I->getOperand(0))) {
- Constant *NegOp0I0C = ConstantExpr::get(Instruction::Sub,
- Constant::getNullValue(Op0I0C->getType()), Op0I0C);
- Constant *ConstantRHS = ConstantExpr::get(Instruction::Sub, NegOp0I0C,
+ Constant *NegOp0I0C = ConstantExpr::getNeg(Op0I0C);
+ Constant *ConstantRHS = ConstantExpr::getSub(NegOp0I0C,
ConstantInt::get(I.getType(), 1));
- return BinaryOperator::create(Instruction::Add, Op0I->getOperand(1),
- ConstantRHS);
+ 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)))
switch (Op0I->getOpcode()) {
case Instruction::Add:
// ~(X-c) --> (-c-1)-X
if (RHS->isAllOnesValue()) {
- Constant *NegOp0CI = ConstantExpr::get(Instruction::Sub,
- Constant::getNullValue(Op0CI->getType()), Op0CI);
- return BinaryOperator::create(Instruction::Sub,
- ConstantExpr::get(Instruction::Sub, NegOp0CI,
+ Constant *NegOp0CI = ConstantExpr::getNeg(Op0CI);
+ return BinaryOperator::createSub(
+ ConstantExpr::getSub(NegOp0CI,
ConstantInt::get(I.getType(), 1)),
Op0I->getOperand(0));
}
break;
case Instruction::And:
// (X & C1) ^ C2 --> (X & C1) | C2 iff (C1&C2) == 0
- if (ConstantExpr::get(Instruction::And, RHS, Op0CI)->isNullValue())
- return BinaryOperator::create(Instruction::Or, Op0, RHS);
+ if (ConstantExpr::getAnd(RHS, Op0CI)->isNullValue())
+ return BinaryOperator::createOr(Op0, RHS);
break;
case Instruction::Or:
// (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
- if (ConstantExpr::get(Instruction::And, RHS, Op0CI) == RHS)
- return BinaryOperator::create(Instruction::And, Op0,
- NotConstant(RHS));
+ if (ConstantExpr::getAnd(RHS, Op0CI) == RHS)
+ return BinaryOperator::createAnd(Op0, ConstantExpr::getNot(RHS));
break;
default: break;
}
if (Op0I->getOperand(0) == Op1) // (B|A)^B == (A|B)^B
cast<BinaryOperator>(Op0I)->swapOperands();
if (Op0I->getOperand(1) == Op1) { // (A|B)^B == A & ~B
- Value *NotB = BinaryOperator::createNot(Op1, Op1->getName()+".not", &I);
- WorkList.push_back(cast<Instruction>(NotB));
- return BinaryOperator::create(Instruction::And, Op0I->getOperand(0),
- NotB);
+ Value *NotB = InsertNewInstBefore(BinaryOperator::createNot(Op1,
+ Op1->getName()+".not"), I);
+ return BinaryOperator::createAnd(Op0I->getOperand(0), NotB);
}
} else if (Op0I->getOpcode() == Instruction::Xor) {
if (Op1 == Op0I->getOperand(0)) // (A^B)^A == B
return ReplaceInstUsesWith(I, Op0I->getOperand(0));
}
- // (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1^C2 == 0
- if (Constant *C1 = dyn_castMaskingAnd(Op0))
- if (Constant *C2 = dyn_castMaskingAnd(Op1))
- if (ConstantExpr::get(Instruction::And, C1, C2)->isNullValue())
- return BinaryOperator::create(Instruction::Or, Op0, Op1);
+ // (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
+ Value *A, *B; ConstantInt *C1, *C2;
+ if (match(Op0, m_And(m_Value(A), m_ConstantInt(C1))) &&
+ match(Op1, m_And(m_Value(B), m_ConstantInt(C2))) &&
+ ConstantExpr::getAnd(C1, C2)->isNullValue())
+ return BinaryOperator::createOr(Op0, Op1);
// (setcc1 A, B) ^ (setcc2 A, B) --> (setcc3 A, B)
if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
// AddOne, SubOne - Add or subtract a constant one from an integer constant...
static Constant *AddOne(ConstantInt *C) {
- Constant *Result = ConstantExpr::get(Instruction::Add, C,
- ConstantInt::get(C->getType(), 1));
- assert(Result && "Constant folding integer addition failed!");
- return Result;
+ return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
}
static Constant *SubOne(ConstantInt *C) {
- Constant *Result = ConstantExpr::get(Instruction::Sub, C,
- ConstantInt::get(C->getType(), 1));
- assert(Result && "Constant folding integer addition failed!");
- return Result;
+ return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
}
// isTrueWhenEqual - Return true if the specified setcondinst instruction is
if (Ty == Type::BoolTy) {
// If this is <, >, or !=, we can change this into a simple xor instruction
if (!isTrueWhenEqual(I))
- return BinaryOperator::create(Instruction::Xor, Op0, Op1);
+ return BinaryOperator::createXor(Op0, Op1);
// Otherwise we need to make a temporary intermediate instruction and insert
// it into the instruction stream. This is what we are after:
// setge bool %A, %B -> A | ~B
//
if (I.getOpcode() == Instruction::SetEQ) { // seteq case
- Instruction *Xor = BinaryOperator::create(Instruction::Xor, Op0, Op1,
- I.getName()+"tmp");
+ Instruction *Xor = BinaryOperator::createXor(Op0, Op1, I.getName()+"tmp");
InsertNewInstBefore(Xor, I);
return BinaryOperator::createNot(Xor);
}
// Now we just have the SetLE case.
Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
InsertNewInstBefore(Not, I);
- return BinaryOperator::create(Instruction::Or, Not, Op1);
+ return BinaryOperator::createOr(Not, Op1);
}
- // Check to see if we are doing one of many comparisons against constant
- // integers at the end of their ranges...
- //
+ // See if we are doing a comparison between a constant and an instruction that
+ // can be folded into the comparison.
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
+ if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
+ if (LHSI->hasOneUse())
+ switch (LHSI->getOpcode()) {
+ case Instruction::And:
+ if (isa<ConstantInt>(LHSI->getOperand(1)) &&
+ LHSI->getOperand(0)->hasOneUse()) {
+ // If this is: (X >> C1) & C2 != C3 (where any shift and any compare
+ // could exist), turn it into (X & (C2 << C1)) != (C3 << C1). This
+ // happens a LOT in code produced by the C front-end, for bitfield
+ // access.
+ ShiftInst *Shift = dyn_cast<ShiftInst>(LHSI->getOperand(0));
+ ConstantUInt *ShAmt;
+ ShAmt = Shift ? dyn_cast<ConstantUInt>(Shift->getOperand(1)) : 0;
+ ConstantInt *AndCST = cast<ConstantInt>(LHSI->getOperand(1));
+ const Type *Ty = LHSI->getType();
+
+ // We can fold this as long as we can't shift unknown bits
+ // into the mask. This can only happen with signed shift
+ // rights, as they sign-extend.
+ if (ShAmt) {
+ bool CanFold = Shift->getOpcode() != Instruction::Shr ||
+ Shift->getType()->isUnsigned();
+ if (!CanFold) {
+ // To test for the bad case of the signed shr, see if any
+ // of the bits shifted in could be tested after the mask.
+ Constant *OShAmt = ConstantUInt::get(Type::UByteTy,
+ Ty->getPrimitiveSize()*8-ShAmt->getValue());
+ Constant *ShVal =
+ ConstantExpr::getShl(ConstantInt::getAllOnesValue(Ty), OShAmt);
+ if (ConstantExpr::getAnd(ShVal, AndCST)->isNullValue())
+ CanFold = true;
+ }
+
+ if (CanFold) {
+ unsigned ShiftOp = Shift->getOpcode() == Instruction::Shl
+ ? Instruction::Shr : Instruction::Shl;
+ Constant *NewCst = ConstantExpr::get(ShiftOp, CI, ShAmt);
+
+ // Check to see if we are shifting out any of the bits being
+ // compared.
+ if (ConstantExpr::get(Shift->getOpcode(), NewCst, ShAmt) != CI){
+ // If we shifted bits out, the fold is not going to work out.
+ // As a special case, check to see if this means that the
+ // result is always true or false now.
+ if (I.getOpcode() == Instruction::SetEQ)
+ return ReplaceInstUsesWith(I, ConstantBool::False);
+ if (I.getOpcode() == Instruction::SetNE)
+ return ReplaceInstUsesWith(I, ConstantBool::True);
+ } else {
+ I.setOperand(1, NewCst);
+ LHSI->setOperand(1, ConstantExpr::get(ShiftOp, AndCST,ShAmt));
+ LHSI->setOperand(0, Shift->getOperand(0));
+ WorkList.push_back(Shift); // Shift is dead.
+ AddUsesToWorkList(I);
+ return &I;
+ }
+ }
+ }
+ }
+ break;
+ case Instruction::Div:
+ if (0 && isa<ConstantInt>(LHSI->getOperand(1))) {
+ std::cerr << "COULD FOLD: " << *LHSI;
+ std::cerr << "COULD FOLD: " << I << "\n";
+ }
+ break;
+ case Instruction::Select:
+ // If either operand of the select is a constant, we can fold the
+ // comparison into the select arms, which will cause one to be
+ // constant folded and the select turned into a bitwise or.
+ Value *Op1 = 0, *Op2 = 0;
+ if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1))) {
+ // Fold the known value into the constant operand.
+ Op1 = ConstantExpr::get(I.getOpcode(), C, CI);
+ // Insert a new SetCC of the other select operand.
+ Op2 = InsertNewInstBefore(new SetCondInst(I.getOpcode(),
+ LHSI->getOperand(2), CI,
+ I.getName()), I);
+ } else if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2))) {
+ // Fold the known value into the constant operand.
+ Op2 = ConstantExpr::get(I.getOpcode(), C, CI);
+ // Insert a new SetCC of the other select operand.
+ Op1 = InsertNewInstBefore(new SetCondInst(I.getOpcode(),
+ LHSI->getOperand(1), CI,
+ I.getName()), I);
+ }
+
+ if (Op1)
+ return new SelectInst(LHSI->getOperand(0), Op1, Op2);
+ break;
+ }
+
// Simplify seteq and setne instructions...
if (I.getOpcode() == Instruction::SetEQ ||
I.getOpcode() == Instruction::SetNE) {
// operand is a constant, simplify a bit.
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) {
switch (BO->getOpcode()) {
+ case Instruction::Rem:
+ // If we have a signed (X % (2^c)) == 0, turn it into an unsigned one.
+ if (CI->isNullValue() && isa<ConstantSInt>(BO->getOperand(1)) &&
+ BO->hasOneUse() &&
+ cast<ConstantSInt>(BO->getOperand(1))->getValue() > 1)
+ if (unsigned L2 =
+ Log2(cast<ConstantSInt>(BO->getOperand(1))->getValue())) {
+ const Type *UTy = BO->getType()->getUnsignedVersion();
+ Value *NewX = InsertNewInstBefore(new CastInst(BO->getOperand(0),
+ UTy, "tmp"), I);
+ Constant *RHSCst = ConstantUInt::get(UTy, 1ULL << L2);
+ Value *NewRem =InsertNewInstBefore(BinaryOperator::createRem(NewX,
+ RHSCst, BO->getName()), I);
+ return BinaryOperator::create(I.getOpcode(), NewRem,
+ Constant::getNullValue(UTy));
+ }
+ break;
+
case Instruction::Add:
- if (CI->isNullValue()) {
+ // Replace ((add A, B) != C) with (A != C-B) if B & C are constants.
+ if (ConstantInt *BOp1C = dyn_cast<ConstantInt>(BO->getOperand(1))) {
+ return new SetCondInst(I.getOpcode(), BO->getOperand(0),
+ ConstantExpr::getSub(CI, BOp1C));
+ } else if (CI->isNullValue()) {
// Replace ((add A, B) != 0) with (A != -B) if A or B is
// efficiently invertible, or if the add has just this one use.
Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1);
+
if (Value *NegVal = dyn_castNegVal(BOp1))
return new SetCondInst(I.getOpcode(), BOp0, NegVal);
else if (Value *NegVal = dyn_castNegVal(BOp0))
// the explicit xor.
if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1)))
return BinaryOperator::create(I.getOpcode(), BO->getOperand(0),
- ConstantExpr::get(Instruction::Xor, CI, BOC));
+ ConstantExpr::getXor(CI, BOC));
// FALLTHROUGH
case Instruction::Sub:
// If bits are being or'd in that are not present in the constant we
// are comparing against, then the comparison could never succeed!
if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) {
- Constant *NotCI = NotConstant(CI);
- if (!ConstantExpr::get(Instruction::And, BOC, NotCI)->isNullValue())
+ Constant *NotCI = ConstantExpr::getNot(CI);
+ if (!ConstantExpr::getAnd(BOC, NotCI)->isNullValue())
return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
}
break;
if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
// If bits are being compared against that are and'd out, then the
// comparison can never succeed!
- if (!ConstantExpr::get(Instruction::And, CI,
- NotConstant(BOC))->isNullValue())
+ if (!ConstantExpr::getAnd(CI,
+ ConstantExpr::getNot(BOC))->isNullValue())
return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
+ // If we have ((X & C) == C), turn it into ((X & C) != 0).
+ if (CI == BOC && isOneBitSet(CI))
+ return new SetCondInst(isSetNE ? Instruction::SetEQ :
+ Instruction::SetNE, Op0,
+ Constant::getNullValue(CI->getType()));
+
// Replace (and X, (1 << size(X)-1) != 0) with x < 0, converting X
// to be a signed value as appropriate.
if (isSignBit(BOC)) {
Value *X = BO->getOperand(0);
// If 'X' is not signed, insert a cast now...
if (!BOC->getType()->isSigned()) {
- const Type *DestTy = getSignedIntegralType(BOC->getType());
+ const Type *DestTy = BOC->getType()->getSignedVersion();
CastInst *NewCI = new CastInst(X,DestTy,X->getName()+".signed");
InsertNewInstBefore(NewCI, I);
X = NewCI;
// vicinity of zero.
if (I.getOpcode() == Instruction::SetLT && CI->isNullValue())
// X < 0 => x > 127
- return BinaryOperator::create(Instruction::SetGT, CastOp,
+ return BinaryOperator::createSetGT(CastOp,
ConstantUInt::get(SrcTy, (1ULL << (SrcTySize*8-1))-1));
else if (I.getOpcode() == Instruction::SetGT &&
cast<ConstantSInt>(CI)->getValue() == -1)
// X > -1 => x < 128
- return BinaryOperator::create(Instruction::SetLT, CastOp,
+ return BinaryOperator::createSetLT(CastOp,
ConstantUInt::get(SrcTy, 1ULL << (SrcTySize*8-1)));
} else {
ConstantUInt *CUI = cast<ConstantUInt>(CI);
if (I.getOpcode() == Instruction::SetLT &&
CUI->getValue() == 1ULL << (SrcTySize*8-1))
// X < 128 => X > -1
- return BinaryOperator::create(Instruction::SetGT, CastOp,
- ConstantSInt::get(SrcTy, -1));
+ return BinaryOperator::createSetGT(CastOp,
+ ConstantSInt::get(SrcTy, -1));
else if (I.getOpcode() == Instruction::SetGT &&
CUI->getValue() == (1ULL << (SrcTySize*8-1))-1)
// X > 127 => X < 0
- return BinaryOperator::create(Instruction::SetLT, CastOp,
- Constant::getNullValue(SrcTy));
+ return BinaryOperator::createSetLT(CastOp,
+ Constant::getNullValue(SrcTy));
}
}
}
if (I.getOpcode() == Instruction::SetGE) // A >= MIN -> TRUE
return ReplaceInstUsesWith(I, ConstantBool::True);
if (I.getOpcode() == Instruction::SetLE) // A <= MIN -> A == MIN
- return BinaryOperator::create(Instruction::SetEQ, Op0, Op1);
+ return BinaryOperator::createSetEQ(Op0, Op1);
if (I.getOpcode() == Instruction::SetGT) // A > MIN -> A != MIN
- return BinaryOperator::create(Instruction::SetNE, Op0, Op1);
+ return BinaryOperator::createSetNE(Op0, Op1);
} else if (CI->isMaxValue()) {
if (I.getOpcode() == Instruction::SetGT) // A > MAX -> FALSE
if (I.getOpcode() == Instruction::SetLE) // A <= MAX -> TRUE
return ReplaceInstUsesWith(I, ConstantBool::True);
if (I.getOpcode() == Instruction::SetGE) // A >= MAX -> A == MAX
- return BinaryOperator::create(Instruction::SetEQ, Op0, Op1);
+ return BinaryOperator::createSetEQ(Op0, Op1);
if (I.getOpcode() == Instruction::SetLT) // A < MAX -> A != MAX
- return BinaryOperator::create(Instruction::SetNE, Op0, Op1);
+ return BinaryOperator::createSetNE(Op0, Op1);
// Comparing against a value really close to min or max?
} else if (isMinValuePlusOne(CI)) {
if (I.getOpcode() == Instruction::SetLT) // A < MIN+1 -> A == MIN
- return BinaryOperator::create(Instruction::SetEQ, Op0, SubOne(CI));
+ return BinaryOperator::createSetEQ(Op0, SubOne(CI));
if (I.getOpcode() == Instruction::SetGE) // A >= MIN-1 -> A != MIN
- return BinaryOperator::create(Instruction::SetNE, Op0, SubOne(CI));
+ return BinaryOperator::createSetNE(Op0, SubOne(CI));
} else if (isMaxValueMinusOne(CI)) {
if (I.getOpcode() == Instruction::SetGT) // A > MAX-1 -> A == MAX
- return BinaryOperator::create(Instruction::SetEQ, Op0, AddOne(CI));
+ return BinaryOperator::createSetEQ(Op0, AddOne(CI));
if (I.getOpcode() == Instruction::SetLE) // A <= MAX-1 -> A != MAX
- return BinaryOperator::create(Instruction::SetNE, Op0, AddOne(CI));
+ return BinaryOperator::createSetNE(Op0, AddOne(CI));
}
// If we still have a setle or setge instruction, turn it into the
// already been handled above, this requires little checking.
//
if (I.getOpcode() == Instruction::SetLE)
- return BinaryOperator::create(Instruction::SetLT, Op0, AddOne(CI));
+ return BinaryOperator::createSetLT(Op0, AddOne(CI));
if (I.getOpcode() == Instruction::SetGE)
- return BinaryOperator::create(Instruction::SetGT, Op0, SubOne(CI));
+ return BinaryOperator::createSetGT(Op0, SubOne(CI));
}
// Test to see if the operands of the setcc are casted versions of other
if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0))
if (BO->getOpcode() == Instruction::Mul && isLeftShift)
if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1)))
- return BinaryOperator::create(Instruction::Mul, BO->getOperand(0),
- ConstantExpr::get(Instruction::Shl, BOOp, CUI));
+ return BinaryOperator::createMul(BO->getOperand(0),
+ ConstantExpr::getShl(BOOp, CUI));
// Try to fold constant and into select arguments.
if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
// Calculate bitmask for what gets shifted off the edge...
Constant *C = ConstantIntegral::getAllOnesValue(I.getType());
if (isLeftShift)
- C = ConstantExpr::get(Instruction::Shl, C, ShiftAmt1C);
+ C = ConstantExpr::getShl(C, ShiftAmt1C);
else
- C = ConstantExpr::get(Instruction::Shr, C, ShiftAmt1C);
+ C = ConstantExpr::getShr(C, ShiftAmt1C);
Instruction *Mask =
- BinaryOperator::create(Instruction::And, Op0SI->getOperand(0),
- C, Op0SI->getOperand(0)->getName()+".mask");
+ BinaryOperator::createAnd(Op0SI->getOperand(0), C,
+ Op0SI->getOperand(0)->getName()+".mask");
InsertNewInstBefore(Mask, I);
// Figure out what flavor of shift we should use...
return 0;
}
+enum CastType {
+ Noop = 0,
+ Truncate = 1,
+ Signext = 2,
+ Zeroext = 3
+};
+
+/// getCastType - In the future, we will split the cast instruction into these
+/// various types. Until then, we have to do the analysis here.
+static CastType getCastType(const Type *Src, const Type *Dest) {
+ assert(Src->isIntegral() && Dest->isIntegral() &&
+ "Only works on integral types!");
+ unsigned SrcSize = Src->getPrimitiveSize()*8;
+ if (Src == Type::BoolTy) SrcSize = 1;
+ unsigned DestSize = Dest->getPrimitiveSize()*8;
+ if (Dest == Type::BoolTy) DestSize = 1;
+
+ if (SrcSize == DestSize) return Noop;
+ if (SrcSize > DestSize) return Truncate;
+ if (Src->isSigned()) return Signext;
+ return Zeroext;
+}
+
// isEliminableCastOfCast - Return true if it is valid to eliminate the CI
// instruction.
//
static inline bool isEliminableCastOfCast(const Type *SrcTy, const Type *MidTy,
- const Type *DstTy) {
+ const Type *DstTy, TargetData *TD) {
// It is legal to eliminate the instruction if casting A->B->A if the sizes
// are identical and the bits don't get reinterpreted (for example
- // int->float->int would not be allowed)
+ // int->float->int would not be allowed).
if (SrcTy == DstTy && SrcTy->isLosslesslyConvertibleTo(MidTy))
return true;
+ // If we are casting between pointer and integer types, treat pointers as
+ // integers of the appropriate size for the code below.
+ if (isa<PointerType>(SrcTy)) SrcTy = TD->getIntPtrType();
+ if (isa<PointerType>(MidTy)) MidTy = TD->getIntPtrType();
+ if (isa<PointerType>(DstTy)) DstTy = TD->getIntPtrType();
+
// Allow free casting and conversion of sizes as long as the sign doesn't
// change...
if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral()) {
- unsigned SrcSize = SrcTy->getPrimitiveSize();
- unsigned MidSize = MidTy->getPrimitiveSize();
- unsigned DstSize = DstTy->getPrimitiveSize();
-
- // Cases where we are monotonically decreasing the size of the type are
- // always ok, regardless of what sign changes are going on.
- //
- if (SrcSize >= MidSize && MidSize >= DstSize)
- return true;
-
- // Cases where the source and destination type are the same, but the middle
- // type is bigger are noops.
- //
- if (SrcSize == DstSize && MidSize > SrcSize)
- return true;
-
- // If we are monotonically growing, things are more complex.
- //
- if (SrcSize <= MidSize && MidSize <= DstSize) {
- // We have eight combinations of signedness to worry about. Here's the
- // table:
- static const int SignTable[8] = {
- // CODE, SrcSigned, MidSigned, DstSigned, Comment
- 1, // U U U Always ok
- 1, // U U S Always ok
- 3, // U S U Ok iff SrcSize != MidSize
- 3, // U S S Ok iff SrcSize != MidSize
- 0, // S U U Never ok
- 2, // S U S Ok iff MidSize == DstSize
- 1, // S S U Always ok
- 1, // S S S Always ok
- };
-
- // Choose an action based on the current entry of the signtable that this
- // cast of cast refers to...
- unsigned Row = SrcTy->isSigned()*4+MidTy->isSigned()*2+DstTy->isSigned();
- switch (SignTable[Row]) {
- case 0: return false; // Never ok
- case 1: return true; // Always ok
- case 2: return MidSize == DstSize; // Ok iff MidSize == DstSize
- case 3: // Ok iff SrcSize != MidSize
- return SrcSize != MidSize || SrcTy == Type::BoolTy;
- default: assert(0 && "Bad entry in sign table!");
- }
+ CastType FirstCast = getCastType(SrcTy, MidTy);
+ CastType SecondCast = getCastType(MidTy, DstTy);
+
+ // Capture the effect of these two casts. If the result is a legal cast,
+ // the CastType is stored here, otherwise a special code is used.
+ static const unsigned CastResult[] = {
+ // First cast is noop
+ 0, 1, 2, 3,
+ // First cast is a truncate
+ 1, 1, 4, 4, // trunc->extend is not safe to eliminate
+ // First cast is a sign ext
+ 2, 5, 2, 4, // signext->zeroext never ok
+ // First cast is a zero ext
+ 3, 5, 3, 3,
+ };
+
+ unsigned Result = CastResult[FirstCast*4+SecondCast];
+ switch (Result) {
+ default: assert(0 && "Illegal table value!");
+ case 0:
+ case 1:
+ case 2:
+ case 3:
+ // FIXME: in the future, when LLVM has explicit sign/zeroextends and
+ // truncates, we could eliminate more casts.
+ return (unsigned)getCastType(SrcTy, DstTy) == Result;
+ case 4:
+ return false; // Not possible to eliminate this here.
+ case 5:
+ // Sign or zero extend followed by truncate is always ok if the result
+ // is a truncate or noop.
+ CastType ResultCast = getCastType(SrcTy, DstTy);
+ if (ResultCast == Noop || ResultCast == Truncate)
+ return true;
+ // Otherwise we are still growing the value, we are only safe if the
+ // result will match the sign/zeroextendness of the result.
+ return ResultCast == FirstCast;
}
}
-
- // Otherwise, we cannot succeed. Specifically we do not want to allow things
- // like: short -> ushort -> uint, because this can create wrong results if
- // the input short is negative!
- //
return false;
}
-static bool ValueRequiresCast(const Value *V, const Type *Ty) {
+static bool ValueRequiresCast(const Value *V, const Type *Ty, TargetData *TD) {
if (V->getType() == Ty || isa<Constant>(V)) return false;
if (const CastInst *CI = dyn_cast<CastInst>(V))
- if (isEliminableCastOfCast(CI->getOperand(0)->getType(), CI->getType(), Ty))
+ if (isEliminableCastOfCast(CI->getOperand(0)->getType(), CI->getType(), Ty,
+ TD))
return false;
return true;
}
//
if (CastInst *CSrc = dyn_cast<CastInst>(Src)) {
if (isEliminableCastOfCast(CSrc->getOperand(0)->getType(),
- CSrc->getType(), CI.getType())) {
+ CSrc->getType(), CI.getType(), TD)) {
// This instruction now refers directly to the cast's src operand. This
// has a good chance of making CSrc dead.
CI.setOperand(0, CSrc->getOperand(0));
"Cannot have type bigger than ulong!");
uint64_t AndValue = (1ULL << CSrc->getType()->getPrimitiveSize()*8)-1;
Constant *AndOp = ConstantUInt::get(CI.getType(), AndValue);
- return BinaryOperator::create(Instruction::And, CSrc->getOperand(0),
- AndOp);
+ return BinaryOperator::createAnd(CSrc->getOperand(0), AndOp);
}
}
+ // If this is a cast to bool, turn it into the appropriate setne instruction.
+ if (CI.getType() == Type::BoolTy)
+ return BinaryOperator::createSetNE(CI.getOperand(0),
+ Constant::getNullValue(CI.getOperand(0)->getType()));
+
// If casting the result of a getelementptr instruction with no offset, turn
// this into a cast of the original pointer!
//
if (const PointerType *PTy = dyn_cast<PointerType>(CI.getType())) {
// Get the type really allocated and the type casted to...
const Type *AllocElTy = AI->getAllocatedType();
- unsigned AllocElTySize = TD->getTypeSize(AllocElTy);
const Type *CastElTy = PTy->getElementType();
- unsigned CastElTySize = TD->getTypeSize(CastElTy);
+ if (AllocElTy->isSized() && CastElTy->isSized()) {
+ unsigned AllocElTySize = TD->getTypeSize(AllocElTy);
+ unsigned CastElTySize = TD->getTypeSize(CastElTy);
- // If the allocation is for an even multiple of the cast type size
- if (CastElTySize && (AllocElTySize % CastElTySize == 0)) {
- Value *Amt = ConstantUInt::get(Type::UIntTy,
+ // If the allocation is for an even multiple of the cast type size
+ if (CastElTySize && (AllocElTySize % CastElTySize == 0)) {
+ Value *Amt = ConstantUInt::get(Type::UIntTy,
AllocElTySize/CastElTySize);
- std::string Name = AI->getName(); AI->setName("");
- AllocationInst *New;
- if (isa<MallocInst>(AI))
- New = new MallocInst(CastElTy, Amt, Name);
- else
- New = new AllocaInst(CastElTy, Amt, Name);
- InsertNewInstBefore(New, *AI);
- return ReplaceInstUsesWith(CI, New);
+ std::string Name = AI->getName(); AI->setName("");
+ AllocationInst *New;
+ if (isa<MallocInst>(AI))
+ New = new MallocInst(CastElTy, Amt, Name);
+ else
+ New = new AllocaInst(CastElTy, Amt, Name);
+ InsertNewInstBefore(New, *AI);
+ return ReplaceInstUsesWith(CI, New);
+ }
}
}
// Don't insert two casts if they cannot be eliminated. We allow two
// casts to be inserted if the sizes are the same. This could only be
// converting signedness, which is a noop.
- if (DestBitSize == SrcBitSize || !ValueRequiresCast(Op1, DestTy) ||
- !ValueRequiresCast(Op0, DestTy)) {
+ if (DestBitSize == SrcBitSize || !ValueRequiresCast(Op1, DestTy,TD) ||
+ !ValueRequiresCast(Op0, DestTy, TD)) {
Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
Value *Op1c = InsertOperandCastBefore(Op1, DestTy, SrcI);
return BinaryOperator::create(cast<BinaryOperator>(SrcI)
if (ConstantBool *C = dyn_cast<ConstantBool>(TrueVal)) {
if (C == ConstantBool::True) {
// Change: A = select B, true, C --> A = or B, C
- return BinaryOperator::create(Instruction::Or, CondVal, FalseVal);
+ return BinaryOperator::createOr(CondVal, FalseVal);
} else {
// Change: A = select B, false, C --> A = and !B, C
Value *NotCond =
InsertNewInstBefore(BinaryOperator::createNot(CondVal,
"not."+CondVal->getName()), SI);
- return BinaryOperator::create(Instruction::And, NotCond, FalseVal);
+ return BinaryOperator::createAnd(NotCond, FalseVal);
}
} else if (ConstantBool *C = dyn_cast<ConstantBool>(FalseVal)) {
if (C == ConstantBool::False) {
// Change: A = select B, C, false --> A = and B, C
- return BinaryOperator::create(Instruction::And, CondVal, TrueVal);
+ return BinaryOperator::createAnd(CondVal, TrueVal);
} else {
// Change: A = select B, C, true --> A = or !B, C
Value *NotCond =
InsertNewInstBefore(BinaryOperator::createNot(CondVal,
"not."+CondVal->getName()), SI);
- return BinaryOperator::create(Instruction::Or, NotCond, TrueVal);
+ return BinaryOperator::createOr(NotCond, TrueVal);
}
}
"not."+CondVal->getName()), SI);
return new CastInst(NotCond, SI.getType());
}
+
+ // If one of the constants is zero (we know they can't both be) and we
+ // have a setcc instruction with zero, and we have an 'and' with the
+ // non-constant value, eliminate this whole mess. This corresponds to
+ // cases like this: ((X & 27) ? 27 : 0)
+ if (TrueValC->isNullValue() || FalseValC->isNullValue())
+ if (Instruction *IC = dyn_cast<Instruction>(SI.getCondition()))
+ if ((IC->getOpcode() == Instruction::SetEQ ||
+ IC->getOpcode() == Instruction::SetNE) &&
+ isa<ConstantInt>(IC->getOperand(1)) &&
+ cast<Constant>(IC->getOperand(1))->isNullValue())
+ if (Instruction *ICA = dyn_cast<Instruction>(IC->getOperand(0)))
+ if (ICA->getOpcode() == Instruction::And &&
+ isa<ConstantInt>(ICA->getOperand(1)) &&
+ (ICA->getOperand(1) == TrueValC ||
+ ICA->getOperand(1) == FalseValC) &&
+ isOneBitSet(cast<ConstantInt>(ICA->getOperand(1)))) {
+ // Okay, now we know that everything is set up, we just don't
+ // know whether we have a setne or seteq and whether the true or
+ // false val is the zero.
+ bool ShouldNotVal = !TrueValC->isNullValue();
+ ShouldNotVal ^= IC->getOpcode() == Instruction::SetNE;
+ Value *V = ICA;
+ if (ShouldNotVal)
+ V = InsertNewInstBefore(BinaryOperator::create(
+ Instruction::Xor, V, ICA->getOperand(1)), SI);
+ return ReplaceInstUsesWith(SI, V);
+ }
}
// See if we are selecting two values based on a comparison of the two values.
bool InstCombiner::transformConstExprCastCall(CallSite CS) {
if (!isa<ConstantExpr>(CS.getCalledValue())) return false;
ConstantExpr *CE = cast<ConstantExpr>(CS.getCalledValue());
- if (CE->getOpcode() != Instruction::Cast ||
- !isa<ConstantPointerRef>(CE->getOperand(0)))
+ if (CE->getOpcode() != Instruction::Cast || !isa<Function>(CE->getOperand(0)))
return false;
- ConstantPointerRef *CPR = cast<ConstantPointerRef>(CE->getOperand(0));
- if (!isa<Function>(CPR->getValue())) return false;
- Function *Callee = cast<Function>(CPR->getValue());
+ Function *Callee = cast<Function>(CE->getOperand(0));
Instruction *Caller = CS.getInstruction();
// Okay, this is a cast from a function to a different type. Unless doing so
Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
+ Value *PtrOp = GEP.getOperand(0);
// Is it 'getelementptr %P, long 0' or 'getelementptr %P'
// If so, eliminate the noop.
if (GEP.getNumOperands() == 1)
- return ReplaceInstUsesWith(GEP, GEP.getOperand(0));
+ return ReplaceInstUsesWith(GEP, PtrOp);
bool HasZeroPointerIndex = false;
if (Constant *C = dyn_cast<Constant>(GEP.getOperand(1)))
HasZeroPointerIndex = C->isNullValue();
if (GEP.getNumOperands() == 2 && HasZeroPointerIndex)
- return ReplaceInstUsesWith(GEP, GEP.getOperand(0));
+ return ReplaceInstUsesWith(GEP, PtrOp);
// Eliminate unneeded casts for indices.
bool MadeChange = false;
Value *Op = GEP.getOperand(i);
if (Op->getType()->getPrimitiveSize() > TD->getPointerSize())
if (Constant *C = dyn_cast<Constant>(Op)) {
- GEP.setOperand(i, ConstantExpr::getCast(C, TD->getIntPtrType()));
+ GEP.setOperand(i, ConstantExpr::getCast(C,
+ TD->getIntPtrType()->getSignedVersion()));
MadeChange = true;
} else {
Op = InsertNewInstBefore(new CastInst(Op, TD->getIntPtrType(),
GEP.setOperand(i, Op);
MadeChange = true;
}
+
+ // If this is a constant idx, make sure to canonicalize it to be a signed
+ // operand, otherwise CSE and other optimizations are pessimized.
+ if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op)) {
+ GEP.setOperand(i, ConstantExpr::getCast(CUI,
+ CUI->getType()->getSignedVersion()));
+ MadeChange = true;
+ }
}
if (MadeChange) return &GEP;
// getelementptr instructions into a single instruction.
//
std::vector<Value*> SrcGEPOperands;
- if (GetElementPtrInst *Src = dyn_cast<GetElementPtrInst>(GEP.getOperand(0))) {
+ if (GetElementPtrInst *Src = dyn_cast<GetElementPtrInst>(PtrOp)) {
SrcGEPOperands.assign(Src->op_begin(), Src->op_end());
- } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP.getOperand(0))) {
+ } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(PtrOp)) {
if (CE->getOpcode() == Instruction::GetElementPtr)
SrcGEPOperands.assign(CE->op_begin(), CE->op_end());
}
if (!SrcGEPOperands.empty()) {
+ // Note that if our source is a gep chain itself that we wait for that
+ // chain to be resolved before we perform this transformation. This
+ // avoids us creating a TON of code in some cases.
+ //
+ if (isa<GetElementPtrInst>(SrcGEPOperands[0]) &&
+ cast<Instruction>(SrcGEPOperands[0])->getNumOperands() == 2)
+ return 0; // Wait until our source is folded to completion.
+
std::vector<Value *> Indices;
+
+ // Find out whether the last index in the source GEP is a sequential idx.
+ bool EndsWithSequential = false;
+ for (gep_type_iterator I = gep_type_begin(*cast<User>(PtrOp)),
+ E = gep_type_end(*cast<User>(PtrOp)); I != E; ++I)
+ EndsWithSequential = !isa<StructType>(*I);
// Can we combine the two pointer arithmetics offsets?
- if (SrcGEPOperands.size() == 2 && isa<Constant>(SrcGEPOperands[1]) &&
- isa<Constant>(GEP.getOperand(1))) {
- Constant *SGC = cast<Constant>(SrcGEPOperands[1]);
- Constant *GC = cast<Constant>(GEP.getOperand(1));
- if (SGC->getType() != GC->getType()) {
- SGC = ConstantExpr::getSignExtend(SGC, Type::LongTy);
- GC = ConstantExpr::getSignExtend(GC, Type::LongTy);
- }
-
- // Replace: gep (gep %P, long C1), long C2, ...
- // With: gep %P, long (C1+C2), ...
- GEP.setOperand(0, SrcGEPOperands[0]);
- GEP.setOperand(1, ConstantExpr::getAdd(SGC, GC));
- if (Instruction *I = dyn_cast<Instruction>(GEP.getOperand(0)))
- AddUsersToWorkList(*I); // Reduce use count of Src
- return &GEP;
- } else if (SrcGEPOperands.size() == 2) {
+ if (EndsWithSequential) {
// Replace: gep (gep %P, long B), long A, ...
// With: T = long A+B; gep %P, T, ...
//
- // Note that if our source is a gep chain itself that we wait for that
- // chain to be resolved before we perform this transformation. This
- // avoids us creating a TON of code in some cases.
- //
- if (isa<GetElementPtrInst>(SrcGEPOperands[0]) &&
- cast<Instruction>(SrcGEPOperands[0])->getNumOperands() == 2)
- return 0; // Wait until our source is folded to completion.
-
- Value *Sum, *SO1 = SrcGEPOperands[1], *GO1 = GEP.getOperand(1);
+ Value *Sum, *SO1 = SrcGEPOperands.back(), *GO1 = GEP.getOperand(1);
if (SO1 == Constant::getNullValue(SO1->getType())) {
Sum = GO1;
} else if (GO1 == Constant::getNullValue(GO1->getType())) {
}
}
}
- Sum = BinaryOperator::create(Instruction::Add, SO1, GO1,
- GEP.getOperand(0)->getName()+".sum", &GEP);
- WorkList.push_back(cast<Instruction>(Sum));
+ if (isa<Constant>(SO1) && isa<Constant>(GO1))
+ Sum = ConstantExpr::getAdd(cast<Constant>(SO1), cast<Constant>(GO1));
+ else {
+ Sum = BinaryOperator::createAdd(SO1, GO1, PtrOp->getName()+".sum");
+ InsertNewInstBefore(cast<Instruction>(Sum), GEP);
+ }
+ }
+
+ // Recycle the GEP we already have if possible.
+ if (SrcGEPOperands.size() == 2) {
+ GEP.setOperand(0, SrcGEPOperands[0]);
+ GEP.setOperand(1, Sum);
+ return &GEP;
+ } else {
+ Indices.insert(Indices.end(), SrcGEPOperands.begin()+1,
+ SrcGEPOperands.end()-1);
+ Indices.push_back(Sum);
+ Indices.insert(Indices.end(), GEP.op_begin()+2, GEP.op_end());
}
- GEP.setOperand(0, SrcGEPOperands[0]);
- GEP.setOperand(1, Sum);
- return &GEP;
} else if (isa<Constant>(*GEP.idx_begin()) &&
cast<Constant>(*GEP.idx_begin())->isNullValue() &&
SrcGEPOperands.size() != 1) {
Indices.insert(Indices.end(), SrcGEPOperands.begin()+1,
SrcGEPOperands.end());
Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end());
- } else if (SrcGEPOperands.back() ==
- Constant::getNullValue(SrcGEPOperands.back()->getType())) {
- // We have to check to make sure this really is an ARRAY index we are
- // ending up with, not a struct index.
- generic_gep_type_iterator<std::vector<Value*>::iterator>
- GTI = gep_type_begin(SrcGEPOperands[0]->getType(),
- SrcGEPOperands.begin()+1, SrcGEPOperands.end());
- std::advance(GTI, SrcGEPOperands.size()-2);
- if (isa<SequentialType>(*GTI)) {
- // If the src gep ends with a constant array index, merge this get into
- // it, even if we have a non-zero array index.
- Indices.insert(Indices.end(), SrcGEPOperands.begin()+1,
- SrcGEPOperands.end()-1);
- Indices.insert(Indices.end(), GEP.idx_begin(), GEP.idx_end());
- }
}
if (!Indices.empty())
return new GetElementPtrInst(SrcGEPOperands[0], Indices, GEP.getName());
- } else if (GlobalValue *GV = dyn_cast<GlobalValue>(GEP.getOperand(0))) {
+ } else if (GlobalValue *GV = dyn_cast<GlobalValue>(PtrOp)) {
// GEP of global variable. If all of the indices for this GEP are
// constants, we can promote this to a constexpr instead of an instruction.
Indices.push_back(cast<Constant>(*I));
if (I == E) { // If they are all constants...
- Constant *CE =
- ConstantExpr::getGetElementPtr(ConstantPointerRef::get(GV), Indices);
+ Constant *CE = ConstantExpr::getGetElementPtr(GV, Indices);
// Replace all uses of the GEP with the new constexpr...
return ReplaceInstUsesWith(GEP, CE);
}
- } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP.getOperand(0))) {
+ } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(PtrOp)) {
if (CE->getOpcode() == Instruction::Cast) {
if (HasZeroPointerIndex) {
// transform: GEP (cast [10 x ubyte]* X to [0 x ubyte]*), long 0, ...
// If alloca'ing a zero byte object, replace the alloca with a null pointer.
// Note that we only do this for alloca's, because malloc should allocate and
// return a unique pointer, even for a zero byte allocation.
- if (isa<AllocaInst>(AI) && TD->getTypeSize(AI.getAllocatedType()) == 0)
+ if (isa<AllocaInst>(AI) && AI.getAllocatedType()->isSized() &&
+ TD->getTypeSize(AI.getAllocatedType()) == 0)
return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
return 0;
// Loop over all of the operands, tracking down which value we are
// addressing...
- for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i)
- if (ConstantUInt *CU = dyn_cast<ConstantUInt>(CE->getOperand(i))) {
- ConstantStruct *CS = dyn_cast<ConstantStruct>(C);
- if (CS == 0) return 0;
- if (CU->getValue() >= CS->getValues().size()) return 0;
- C = cast<Constant>(CS->getValues()[CU->getValue()]);
- } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) {
- ConstantArray *CA = dyn_cast<ConstantArray>(C);
- if (CA == 0) return 0;
- if ((uint64_t)CS->getValue() >= CA->getValues().size()) return 0;
- C = cast<Constant>(CA->getValues()[CS->getValue()]);
- } else
+ gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
+ for (++I; I != E; ++I)
+ if (const StructType *STy = dyn_cast<StructType>(*I)) {
+ ConstantUInt *CU = cast<ConstantUInt>(I.getOperand());
+ assert(CU->getValue() < STy->getNumElements() &&
+ "Struct index out of range!");
+ if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
+ C = CS->getOperand(CU->getValue());
+ } else if (isa<ConstantAggregateZero>(C)) {
+ C = Constant::getNullValue(STy->getElementType(CU->getValue()));
+ } else {
+ return 0;
+ }
+ } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) {
+ const ArrayType *ATy = cast<ArrayType>(*I);
+ if ((uint64_t)CI->getRawValue() >= ATy->getNumElements()) return 0;
+ if (ConstantArray *CA = dyn_cast<ConstantArray>(C))
+ C = CA->getOperand(CI->getRawValue());
+ else if (isa<ConstantAggregateZero>(C))
+ C = Constant::getNullValue(ATy->getElementType());
+ else
+ return 0;
+ } else {
return 0;
+ }
return C;
}
+static Instruction *InstCombineLoadCast(InstCombiner &IC, LoadInst &LI) {
+ User *CI = cast<User>(LI.getOperand(0));
+
+ const Type *DestPTy = cast<PointerType>(CI->getType())->getElementType();
+ if (const PointerType *SrcTy =
+ dyn_cast<PointerType>(CI->getOperand(0)->getType())) {
+ const Type *SrcPTy = SrcTy->getElementType();
+ if (SrcPTy->isSized() && DestPTy->isSized() &&
+ IC.getTargetData().getTypeSize(SrcPTy) ==
+ IC.getTargetData().getTypeSize(DestPTy) &&
+ (SrcPTy->isInteger() || isa<PointerType>(SrcPTy)) &&
+ (DestPTy->isInteger() || isa<PointerType>(DestPTy))) {
+ // Okay, we are casting from one integer or pointer type to another of
+ // the same size. Instead of casting the pointer before the load, cast
+ // the result of the loaded value.
+ Value *NewLoad = IC.InsertNewInstBefore(new LoadInst(CI->getOperand(0),
+ CI->getName()), LI);
+ // Now cast the result of the load.
+ return new CastInst(NewLoad, LI.getType());
+ }
+ }
+ return 0;
+}
+
Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
Value *Op = LI.getOperand(0);
if (LI.isVolatile()) return 0;
if (Constant *C = dyn_cast<Constant>(Op))
if (C->isNullValue()) // load null -> 0
return ReplaceInstUsesWith(LI, Constant::getNullValue(LI.getType()));
- else if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C))
- Op = CPR->getValue();
// Instcombine load (constant global) into the value loaded...
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Op))
// Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded...
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op))
- if (CE->getOpcode() == Instruction::GetElementPtr)
- if (ConstantPointerRef *G=dyn_cast<ConstantPointerRef>(CE->getOperand(0)))
- if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getValue()))
- if (GV->isConstant() && !GV->isExternal())
- if (Constant *V = GetGEPGlobalInitializer(GV->getInitializer(), CE))
- return ReplaceInstUsesWith(LI, V);
+ if (CE->getOpcode() == Instruction::GetElementPtr) {
+ if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
+ if (GV->isConstant() && !GV->isExternal())
+ if (Constant *V = GetGEPGlobalInitializer(GV->getInitializer(), CE))
+ return ReplaceInstUsesWith(LI, V);
+ } else if (CE->getOpcode() == Instruction::Cast) {
+ if (Instruction *Res = InstCombineLoadCast(*this, LI))
+ return Res;
+ }
// load (cast X) --> cast (load X) iff safe
- if (CastInst *CI = dyn_cast<CastInst>(Op)) {
- const Type *DestPTy = cast<PointerType>(CI->getType())->getElementType();
- if (const PointerType *SrcTy =
- dyn_cast<PointerType>(CI->getOperand(0)->getType())) {
- const Type *SrcPTy = SrcTy->getElementType();
- if (TD->getTypeSize(SrcPTy) == TD->getTypeSize(DestPTy) &&
- (SrcPTy->isInteger() || isa<PointerType>(SrcPTy)) &&
- (DestPTy->isInteger() || isa<PointerType>(DestPTy))) {
- // Okay, we are casting from one integer or pointer type to another of
- // the same size. Instead of casting the pointer before the load, cast
- // the result of the loaded value.
- Value *NewLoad = InsertNewInstBefore(new LoadInst(CI->getOperand(0),
- CI->getName()), LI);
- // Now cast the result of the load.
- return new CastInst(NewLoad, LI.getType());
- }
- }
- }
+ if (CastInst *CI = dyn_cast<CastInst>(Op))
+ if (Instruction *Res = InstCombineLoadCast(*this, LI))
+ return Res;
return 0;
}
Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
// Change br (not X), label True, label False to: br X, label False, True
- if (BI.isConditional() && !isa<Constant>(BI.getCondition())) {
- if (Value *V = dyn_castNotVal(BI.getCondition())) {
- BasicBlock *TrueDest = BI.getSuccessor(0);
- BasicBlock *FalseDest = BI.getSuccessor(1);
+ Value *X;
+ BasicBlock *TrueDest;
+ BasicBlock *FalseDest;
+ if (match(&BI, m_Br(m_Not(m_Value(X)), TrueDest, FalseDest)) &&
+ !isa<Constant>(X)) {
+ // Swap Destinations and condition...
+ BI.setCondition(X);
+ BI.setSuccessor(0, FalseDest);
+ BI.setSuccessor(1, TrueDest);
+ return &BI;
+ }
+
+ // Cannonicalize setne -> seteq
+ Instruction::BinaryOps Op; Value *Y;
+ if (match(&BI, m_Br(m_SetCond(Op, m_Value(X), m_Value(Y)),
+ TrueDest, FalseDest)))
+ if ((Op == Instruction::SetNE || Op == Instruction::SetLE ||
+ Op == Instruction::SetGE) && BI.getCondition()->hasOneUse()) {
+ SetCondInst *I = cast<SetCondInst>(BI.getCondition());
+ std::string Name = I->getName(); I->setName("");
+ Instruction::BinaryOps NewOpcode = SetCondInst::getInverseCondition(Op);
+ Value *NewSCC = BinaryOperator::create(NewOpcode, X, Y, Name, I);
// Swap Destinations and condition...
- BI.setCondition(V);
+ BI.setCondition(NewSCC);
BI.setSuccessor(0, FalseDest);
BI.setSuccessor(1, TrueDest);
+ removeFromWorkList(I);
+ I->getParent()->getInstList().erase(I);
+ WorkList.push_back(cast<Instruction>(NewSCC));
return &BI;
- } else if (SetCondInst *I = dyn_cast<SetCondInst>(BI.getCondition())) {
- // Cannonicalize setne -> seteq
- if ((I->getOpcode() == Instruction::SetNE ||
- I->getOpcode() == Instruction::SetLE ||
- I->getOpcode() == Instruction::SetGE) && I->hasOneUse()) {
- std::string Name = I->getName(); I->setName("");
- Instruction::BinaryOps NewOpcode =
- SetCondInst::getInverseCondition(I->getOpcode());
- Value *NewSCC = BinaryOperator::create(NewOpcode, I->getOperand(0),
- I->getOperand(1), Name, I);
- BasicBlock *TrueDest = BI.getSuccessor(0);
- BasicBlock *FalseDest = BI.getSuccessor(1);
- // Swap Destinations and condition...
- BI.setCondition(NewSCC);
- BI.setSuccessor(0, FalseDest);
- BI.setSuccessor(1, TrueDest);
- removeFromWorkList(I);
- I->getParent()->getInstList().erase(I);
- WorkList.push_back(cast<Instruction>(NewSCC));
- return &BI;
- }
}
+
+ return 0;
+}
+
+Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
+ Value *Cond = SI.getCondition();
+ if (Instruction *I = dyn_cast<Instruction>(Cond)) {
+ if (I->getOpcode() == Instruction::Add)
+ if (ConstantInt *AddRHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
+ // change 'switch (X+4) case 1:' into 'switch (X) case -3'
+ for (unsigned i = 2, e = SI.getNumOperands(); i != e; i += 2)
+ SI.setOperand(i, ConstantExpr::getSub(cast<Constant>(SI.getOperand(i)),
+ AddRHS));
+ SI.setOperand(0, I->getOperand(0));
+ WorkList.push_back(I);
+ return &SI;
+ }
}
return 0;
}
continue;
}
- // Check to see if any of the operands of this instruction are a
- // ConstantPointerRef. Since they sneak in all over the place and inhibit
- // optimization, we want to strip them out unconditionally!
- for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
- if (ConstantPointerRef *CPR =
- dyn_cast<ConstantPointerRef>(I->getOperand(i))) {
- I->setOperand(i, CPR->getValue());
- Changed = true;
- }
-
// Now that we have an instruction, try combining it to simplify it...
if (Instruction *Result = visit(*I)) {
++NumCombined;
DEBUG(std::cerr << "IC: Old = " << *I
<< " New = " << *Result);
- // Instructions can end up on the worklist more than once. Make sure
- // we do not process an instruction that has been deleted.
- removeFromWorkList(I);
+ // Everything uses the new instruction now.
+ I->replaceAllUsesWith(Result);
+
+ // Push the new instruction and any users onto the worklist.
+ WorkList.push_back(Result);
+ AddUsersToWorkList(*Result);
// Move the name to the new instruction first...
std::string OldName = I->getName(); I->setName("");
if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i)))
WorkList.push_back(OpI);
- // Everything uses the new instruction now...
- I->replaceAllUsesWith(Result);
+ // Instructions can end up on the worklist more than once. Make sure
+ // we do not process an instruction that has been deleted.
+ removeFromWorkList(I);
// Erase the old instruction.
InstParent->getInstList().erase(I);
// occurrances of this instruction.
removeFromWorkList(I);
I->getParent()->getInstList().erase(I);
- Result = 0;
+ } else {
+ WorkList.push_back(Result);
+ AddUsersToWorkList(*Result);
}
}
-
- if (Result) {
- WorkList.push_back(Result);
- AddUsersToWorkList(*Result);
- }
Changed = true;
}
}
return Changed;
}
-Pass *llvm::createInstructionCombiningPass() {
+FunctionPass *llvm::createInstructionCombiningPass() {
return new InstCombiner();
}
projects / oota-llvm.git / blobdiff