// 5. add X, X is represented as (X*2) => (X << 1)
// 6. Multiplies with a power-of-two constant argument are transformed into
// shifts.
-// N. This list is incomplete
+// ... etc.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "instcombine"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/Instructions.h"
-#include "llvm/Intrinsics.h"
+#include "llvm/IntrinsicInst.h"
#include "llvm/Pass.h"
-#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CallSite.h"
+#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/InstVisitor.h"
-#include "Support/Debug.h"
-#include "Support/Statistic.h"
+#include "llvm/Support/PatternMatch.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
#include <algorithm>
using namespace llvm;
+using namespace llvm::PatternMatch;
namespace {
Statistic<> NumCombined ("instcombine", "Number of insts combined");
Statistic<> NumConstProp("instcombine", "Number of constant folds");
Statistic<> NumDeadInst ("instcombine", "Number of dead inst eliminated");
+ Statistic<> NumSunkInst ("instcombine", "Number of instructions sunk");
class InstCombiner : public FunctionPass,
public InstVisitor<InstCombiner, Instruction*> {
Instruction *visitOr (BinaryOperator &I);
Instruction *visitXor(BinaryOperator &I);
Instruction *visitSetCondInst(BinaryOperator &I);
+ Instruction *visitSetCondInstWithCastAndConstant(BinaryOperator&I,
+ CastInst*LHSI,
+ ConstantInt* CI);
+ Instruction *FoldGEPSetCC(User *GEPLHS, Value *RHS,
+ Instruction::BinaryOps Cond, Instruction &I);
Instruction *visitShiftInst(ShiftInst &I);
Instruction *visitCastInst(CastInst &CI);
+ Instruction *FoldSelectOpOp(SelectInst &SI, Instruction *TI,
+ Instruction *FI);
Instruction *visitSelectInst(SelectInst &CI);
Instruction *visitCallInst(CallInst &CI);
Instruction *visitInvokeInst(InvokeInst &II);
// InsertNewInstBefore - insert an instruction New before instruction Old
// in the program. Add the new instruction to the worklist.
//
- Value *InsertNewInstBefore(Instruction *New, Instruction &Old) {
+ Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
assert(New && New->getParent() == 0 &&
"New instruction already inserted into a basic block!");
BasicBlock *BB = Old.getParent();
return New;
}
+ /// InsertCastBefore - Insert a cast of V to TY before the instruction POS.
+ /// This also adds the cast to the worklist. Finally, this returns the
+ /// cast.
+ Value *InsertCastBefore(Value *V, const Type *Ty, Instruction &Pos) {
+ if (V->getType() == Ty) return V;
+
+ Instruction *C = new CastInst(V, Ty, V->getName(), &Pos);
+ WorkList.push_back(C);
+ return C;
+ }
+
// ReplaceInstUsesWith - This method is to be used when an instruction is
// found to be dead, replacable with another preexisting expression. Here
// we add all uses of I to the worklist, replace all uses of I with the new
} else {
// If we are replacing the instruction with itself, this must be in a
// segment of unreachable code, so just clobber the instruction.
- I.replaceAllUsesWith(Constant::getNullValue(I.getType()));
+ I.replaceAllUsesWith(UndefValue::get(I.getType()));
return &I;
}
}
assert(I.use_empty() && "Cannot erase instruction that is used!");
AddUsesToWorkList(I);
removeFromWorkList(&I);
- I.getParent()->getInstList().erase(&I);
+ I.eraseFromParent();
return 0; // Don't do anything with FI
}
Instruction *InsertBefore);
// SimplifyCommutative - This performs a few simplifications for commutative
- // operators...
+ // operators.
bool SimplifyCommutative(BinaryOperator &I);
+
+ // FoldOpIntoPhi - Given a binary operator or cast instruction which has a
+ // PHI node as operand #0, see if we can fold the instruction into the PHI
+ // (which is only possible if all operands to the PHI are constants).
+ Instruction *FoldOpIntoPhi(Instruction &I);
+
+ // FoldPHIArgOpIntoPHI - If all operands to a PHI node are the same "unary"
+ // operator and they all are only used by the PHI, PHI together their
+ // inputs, and do the operation once, to the result of the PHI.
+ Instruction *FoldPHIArgOpIntoPHI(PHINode &PN);
+
Instruction *OptAndOp(Instruction *Op, ConstantIntegral *OpRHS,
ConstantIntegral *AndRHS, BinaryOperator &TheAnd);
+
+ Instruction *InsertRangeTest(Value *V, Constant *Lo, Constant *Hi,
+ bool Inside, Instruction &IB);
};
RegisterOpt<InstCombiner> X("instcombine", "Combine redundant instructions");
}
// getComplexity: Assign a complexity or rank value to LLVM Values...
-// 0 -> Constant, 1 -> Other, 2 -> Argument, 2 -> Unary, 3 -> OtherInst
+// 0 -> undef, 1 -> Const, 2 -> Other, 3 -> Arg, 3 -> Unary, 4 -> OtherInst
static unsigned getComplexity(Value *V) {
if (isa<Instruction>(V)) {
if (BinaryOperator::isNeg(V) || BinaryOperator::isNot(V))
- return 2;
- return 3;
+ return 3;
+ return 4;
}
- if (isa<Argument>(V)) return 2;
- return isa<Constant>(V) ? 0 : 1;
+ if (isa<Argument>(V)) return 3;
+ return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
}
// isOnlyUse - Return true if this instruction will be deleted if we stop using
if (BinaryOperator::isNeg(V))
return BinaryOperator::getNegArgument(cast<BinaryOperator>(V));
- // Constants can be considered to be negated values if they can be folded...
- if (Constant *C = dyn_cast<Constant>(V))
+ // Constants can be considered to be negated values if they can be folded.
+ if (ConstantInt *C = dyn_cast<ConstantInt>(V))
return ConstantExpr::getNeg(C);
return 0;
}
// dyn_castFoldableMul - If this value is a multiply that can be folded into
// other computations (because it has a constant operand), return the
-// non-constant operand of the multiply.
+// non-constant operand of the multiply, and set CST to point to the multiplier.
+// Otherwise, return null.
//
-static inline Value *dyn_castFoldableMul(Value *V) {
+static inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) {
if (V->hasOneUse() && V->getType()->isInteger())
- if (Instruction *I = dyn_cast<Instruction>(V))
+ if (Instruction *I = dyn_cast<Instruction>(V)) {
if (I->getOpcode() == Instruction::Mul)
- if (isa<Constant>(I->getOperand(1)))
+ if ((CST = dyn_cast<ConstantInt>(I->getOperand(1))))
+ return I->getOperand(0);
+ if (I->getOpcode() == Instruction::Shl)
+ if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) {
+ // The multiplier is really 1 << CST.
+ Constant *One = ConstantInt::get(V->getType(), 1);
+ CST = cast<ConstantInt>(ConstantExpr::getShl(One, CST));
return I->getOperand(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);
+/// dyn_castGetElementPtr - If this is a getelementptr instruction or constant
+/// expression, return it.
+static User *dyn_castGetElementPtr(Value *V) {
+ if (isa<GetElementPtrInst>(V)) return cast<User>(V);
+ if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
+ if (CE->getOpcode() == Instruction::GetElementPtr)
+ return cast<User>(V);
+ return false;
}
// Log2 - Calculate the log base 2 for the specified value if it is exactly a
return Count;
}
+// AddOne, SubOne - Add or subtract a constant one from an integer constant...
+static ConstantInt *AddOne(ConstantInt *C) {
+ return cast<ConstantInt>(ConstantExpr::getAdd(C,
+ ConstantInt::get(C->getType(), 1)));
+}
+static ConstantInt *SubOne(ConstantInt *C) {
+ return cast<ConstantInt>(ConstantExpr::getSub(C,
+ ConstantInt::get(C->getType(), 1)));
+}
+
+// isTrueWhenEqual - Return true if the specified setcondinst instruction is
+// true when both operands are equal...
+//
+static bool isTrueWhenEqual(Instruction &I) {
+ return I.getOpcode() == Instruction::SetEQ ||
+ I.getOpcode() == Instruction::SetGE ||
+ I.getOpcode() == Instruction::SetLE;
+}
/// AssociativeOpt - Perform an optimization on an associative operator. This
/// function is designed to check a chain of associative operators for a
Constant *C2;
AddMaskingAnd(Constant *c) : C2(c) {}
bool shouldApply(Value *LHS) const {
- if (Constant *C1 = dyn_castMaskingAnd(LHS))
- return ConstantExpr::getAnd(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::createOr(Add.getOperand(0), Add.getOperand(1));
}
};
-static Value *FoldOperationIntoSelectOperand(Instruction &BI, Value *SO,
+static Value *FoldOperationIntoSelectOperand(Instruction &I, Value *SO,
InstCombiner *IC) {
+ if (isa<CastInst>(I)) {
+ if (Constant *SOC = dyn_cast<Constant>(SO))
+ return ConstantExpr::getCast(SOC, I.getType());
+
+ return IC->InsertNewInstBefore(new CastInst(SO, I.getType(),
+ SO->getName() + ".cast"), I);
+ }
+
// Figure out if the constant is the left or the right argument.
- bool ConstIsRHS = isa<Constant>(BI.getOperand(1));
- Constant *ConstOperand = cast<Constant>(BI.getOperand(ConstIsRHS));
+ bool ConstIsRHS = isa<Constant>(I.getOperand(1));
+ Constant *ConstOperand = cast<Constant>(I.getOperand(ConstIsRHS));
if (Constant *SOC = dyn_cast<Constant>(SO)) {
if (ConstIsRHS)
- return ConstantExpr::get(BI.getOpcode(), SOC, ConstOperand);
- return ConstantExpr::get(BI.getOpcode(), ConstOperand, SOC);
+ return ConstantExpr::get(I.getOpcode(), SOC, ConstOperand);
+ return ConstantExpr::get(I.getOpcode(), ConstOperand, SOC);
}
Value *Op0 = SO, *Op1 = ConstOperand;
if (!ConstIsRHS)
std::swap(Op0, Op1);
Instruction *New;
- if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&BI))
- New = BinaryOperator::create(BO->getOpcode(), Op0, Op1);
- else if (ShiftInst *SI = dyn_cast<ShiftInst>(&BI))
- New = new ShiftInst(SI->getOpcode(), Op0, Op1);
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&I))
+ New = BinaryOperator::create(BO->getOpcode(), Op0, Op1,SO->getName()+".op");
+ else if (ShiftInst *SI = dyn_cast<ShiftInst>(&I))
+ New = new ShiftInst(SI->getOpcode(), Op0, Op1, SO->getName()+".sh");
else {
assert(0 && "Unknown binary instruction type!");
abort();
}
- return IC->InsertNewInstBefore(New, BI);
+ return IC->InsertNewInstBefore(New, I);
}
-// FoldBinOpIntoSelect - Given an instruction with a select as one operand and a
+// FoldOpIntoSelect - Given an instruction with a select as one operand and a
// constant as the other operand, try to fold the binary operator into the
-// select arguments.
-static Instruction *FoldBinOpIntoSelect(Instruction &BI, SelectInst *SI,
- InstCombiner *IC) {
+// select arguments. This also works for Cast instructions, which obviously do
+// not have a second operand.
+static Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI,
+ InstCombiner *IC) {
// Don't modify shared select instructions
if (!SI->hasOneUse()) return 0;
Value *TV = SI->getOperand(1);
Value *FV = SI->getOperand(2);
if (isa<Constant>(TV) || isa<Constant>(FV)) {
- Value *SelectTrueVal = FoldOperationIntoSelectOperand(BI, TV, IC);
- Value *SelectFalseVal = FoldOperationIntoSelectOperand(BI, FV, IC);
+ Value *SelectTrueVal = FoldOperationIntoSelectOperand(Op, TV, IC);
+ Value *SelectFalseVal = FoldOperationIntoSelectOperand(Op, FV, IC);
return new SelectInst(SI->getCondition(), SelectTrueVal,
SelectFalseVal);
return 0;
}
+
+/// FoldOpIntoPhi - Given a binary operator or cast instruction which has a PHI
+/// node as operand #0, see if we can fold the instruction into the PHI (which
+/// is only possible if all operands to the PHI are constants).
+Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) {
+ PHINode *PN = cast<PHINode>(I.getOperand(0));
+ unsigned NumPHIValues = PN->getNumIncomingValues();
+ if (!PN->hasOneUse() || NumPHIValues == 0 ||
+ !isa<Constant>(PN->getIncomingValue(0))) return 0;
+
+ // Check to see if all of the operands of the PHI are constants. If not, we
+ // cannot do the transformation.
+ for (unsigned i = 1; i != NumPHIValues; ++i)
+ if (!isa<Constant>(PN->getIncomingValue(i)))
+ return 0;
+
+ // Okay, we can do the transformation: create the new PHI node.
+ PHINode *NewPN = new PHINode(I.getType(), I.getName());
+ I.setName("");
+ NewPN->reserveOperandSpace(PN->getNumOperands()/2);
+ InsertNewInstBefore(NewPN, *PN);
+
+ // Next, add all of the operands to the PHI.
+ if (I.getNumOperands() == 2) {
+ Constant *C = cast<Constant>(I.getOperand(1));
+ for (unsigned i = 0; i != NumPHIValues; ++i) {
+ Constant *InV = cast<Constant>(PN->getIncomingValue(i));
+ NewPN->addIncoming(ConstantExpr::get(I.getOpcode(), InV, C),
+ PN->getIncomingBlock(i));
+ }
+ } else {
+ assert(isa<CastInst>(I) && "Unary op should be a cast!");
+ const Type *RetTy = I.getType();
+ for (unsigned i = 0; i != NumPHIValues; ++i) {
+ Constant *InV = cast<Constant>(PN->getIncomingValue(i));
+ NewPN->addIncoming(ConstantExpr::getCast(InV, RetTy),
+ PN->getIncomingBlock(i));
+ }
+ }
+ return ReplaceInstUsesWith(I, NewPN);
+}
+
Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
bool Changed = SimplifyCommutative(I);
Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
+ // X + undef -> undef
+ if (isa<UndefValue>(RHS))
+ return ReplaceInstUsesWith(I, RHS);
+
// X + 0 --> X
if (!I.getType()->isFloatingPoint() && // -0 + +0 = +0, so it's not a noop
RHSC->isNullValue())
if (ConstantInt *CI = dyn_cast<ConstantInt>(RHSC)) {
unsigned NumBits = CI->getType()->getPrimitiveSize()*8;
uint64_t Val = CI->getRawValue() & (1ULL << NumBits)-1;
- if (Val == (1ULL << NumBits-1))
+ if (Val == (1ULL << (NumBits-1)))
return BinaryOperator::createXor(LHS, RHS);
}
+
+ if (isa<PHINode>(LHS))
+ if (Instruction *NV = FoldOpIntoPhi(I))
+ return NV;
}
// 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))
if (Value *V = dyn_castNegVal(RHS))
return BinaryOperator::createSub(LHS, V);
- // X*C + X --> X * (C+1)
- if (dyn_castFoldableMul(LHS) == RHS) {
- Constant *CP1 =
- ConstantExpr::getAdd(
- cast<Constant>(cast<Instruction>(LHS)->getOperand(1)),
- ConstantInt::get(I.getType(), 1));
- return BinaryOperator::createMul(RHS, CP1);
+ ConstantInt *C2;
+ if (Value *X = dyn_castFoldableMul(LHS, C2)) {
+ if (X == RHS) // X*C + X --> X * (C+1)
+ return BinaryOperator::createMul(RHS, AddOne(C2));
+
+ // X*C1 + X*C2 --> X * (C1+C2)
+ ConstantInt *C1;
+ if (X == dyn_castFoldableMul(RHS, C1))
+ return BinaryOperator::createMul(X, ConstantExpr::getAdd(C1, C2));
}
// X + X*C --> X * (C+1)
- if (dyn_castFoldableMul(RHS) == LHS) {
- Constant *CP1 =
- ConstantExpr::getAdd(
- cast<Constant>(cast<Instruction>(RHS)->getOperand(1)),
- ConstantInt::get(I.getType(), 1));
- return BinaryOperator::createMul(LHS, CP1);
- }
+ if (dyn_castFoldableMul(RHS, C2) == LHS)
+ return BinaryOperator::createMul(LHS, AddOne(C2));
+
// (A & C1)+(B & C2) --> (A & C1)|(B & C2) iff C1&C2 == 0
- if (Constant *C2 = dyn_castMaskingAnd(RHS))
+ 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::createSub(ConstantExpr::getSub(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;
+ 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);
+ }
+
+ // (X & FF00) + xx00 -> (X+xx00) & FF00
+ if (LHS->hasOneUse() && match(LHS, m_And(m_Value(X), m_ConstantInt(C2)))) {
+ Constant *Anded = ConstantExpr::getAnd(CRHS, C2);
+ if (Anded == CRHS) {
+ // See if all bits from the first bit set in the Add RHS up are included
+ // in the mask. First, get the rightmost bit.
+ uint64_t AddRHSV = CRHS->getRawValue();
+
+ // Form a mask of all bits from the lowest bit added through the top.
+ uint64_t AddRHSHighBits = ~((AddRHSV & -AddRHSV)-1);
+ AddRHSHighBits &= (1ULL << C2->getType()->getPrimitiveSize()*8)-1;
- default: break;
+ // See if the and mask includes all of these bits.
+ uint64_t AddRHSHighBitsAnd = AddRHSHighBits & C2->getRawValue();
+
+ if (AddRHSHighBits == AddRHSHighBitsAnd) {
+ // Okay, the xform is safe. Insert the new add pronto.
+ Value *NewAdd = InsertNewInstBefore(BinaryOperator::createAdd(X, CRHS,
+ LHS->getName()), I);
+ return BinaryOperator::createAnd(NewAdd, C2);
+ }
}
}
+
+ // Try to fold constant add into select arguments.
+ if (SelectInst *SI = dyn_cast<SelectInst>(LHS))
+ if (Instruction *R = FoldOpIntoSelect(I, SI, this))
+ return R;
}
return Changed ? &I : 0;
if (Value *V = dyn_castNegVal(Op1))
return BinaryOperator::createAdd(Op0, V);
+ if (isa<UndefValue>(Op0))
+ return ReplaceInstUsesWith(I, Op0); // undef - X -> undef
+ if (isa<UndefValue>(Op1))
+ return ReplaceInstUsesWith(I, Op1); // X - undef -> undef
+
if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) {
// Replace (-1 - A) with (~A)...
if (C->isAllOnesValue())
return BinaryOperator::createNot(Op1);
// C - ~X == X + (1+C)
- if (BinaryOperator::isNot(Op1))
- return BinaryOperator::createAdd(
- BinaryOperator::getNotArgument(cast<BinaryOperator>(Op1)),
+ 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)
// Try to fold constant sub into select arguments.
if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
- if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
+ if (Instruction *R = FoldOpIntoSelect(I, SI, this))
return R;
+
+ if (isa<PHINode>(Op0))
+ if (Instruction *NV = FoldOpIntoPhi(I))
+ return NV;
}
if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1))
return BinaryOperator::createAnd(Op0, NewNot);
}
+ // -(X sdiv C) -> (X sdiv -C)
+ if (Op1I->getOpcode() == Instruction::Div)
+ if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0))
+ if (CSI->getValue() == 0)
+ if (Constant *DivRHS = dyn_cast<Constant>(Op1I->getOperand(1)))
+ return BinaryOperator::createDiv(Op1I->getOperand(0),
+ ConstantExpr::getNeg(DivRHS));
+
// X - X*C --> X * (1-C)
- if (dyn_castFoldableMul(Op1I) == Op0) {
- Constant *CP1 =
- ConstantExpr::getSub(ConstantInt::get(I.getType(), 1),
- cast<Constant>(cast<Instruction>(Op1)->getOperand(1)));
- assert(CP1 && "Couldn't constant fold 1-C?");
+ ConstantInt *C2;
+ if (dyn_castFoldableMul(Op1I, C2) == Op0) {
+ Constant *CP1 =
+ ConstantExpr::getSub(ConstantInt::get(I.getType(), 1), C2);
return BinaryOperator::createMul(Op0, CP1);
}
}
- // X*C - X --> X * (C-1)
- if (dyn_castFoldableMul(Op0) == Op1) {
- Constant *CP1 =
- ConstantExpr::getSub(cast<Constant>(cast<Instruction>(Op0)->getOperand(1)),
- ConstantInt::get(I.getType(), 1));
- assert(CP1 && "Couldn't constant fold C - 1?");
- return BinaryOperator::createMul(Op1, CP1);
- }
+ if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0))
+ if (Op0I->getOpcode() == Instruction::Add)
+ if (!Op0->getType()->isFloatingPoint()) {
+ if (Op0I->getOperand(0) == Op1) // (Y+X)-Y == X
+ return ReplaceInstUsesWith(I, Op0I->getOperand(1));
+ else if (Op0I->getOperand(1) == Op1) // (X+Y)-Y == X
+ return ReplaceInstUsesWith(I, Op0I->getOperand(0));
+ }
+
+ ConstantInt *C1;
+ if (Value *X = dyn_castFoldableMul(Op0, C1)) {
+ if (X == Op1) { // X*C - X --> X * (C-1)
+ Constant *CP1 = ConstantExpr::getSub(C1, ConstantInt::get(I.getType(),1));
+ return BinaryOperator::createMul(Op1, CP1);
+ }
+ ConstantInt *C2; // X*C1 - X*C2 -> X * (C1-C2)
+ if (X == dyn_castFoldableMul(Op1, C2))
+ return BinaryOperator::createMul(Op1, ConstantExpr::getSub(C1, C2));
+ }
return 0;
}
bool Changed = SimplifyCommutative(I);
Value *Op0 = I.getOperand(0);
+ if (isa<UndefValue>(I.getOperand(1))) // undef * X -> 0
+ return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
+
// Simplify mul instructions with a constant RHS...
if (Constant *Op1 = dyn_cast<Constant>(I.getOperand(1))) {
if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
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);
// Try to fold constant mul into select arguments.
if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
- if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
+ if (Instruction *R = FoldOpIntoSelect(I, SI, this))
return R;
+
+ if (isa<PHINode>(Op0))
+ if (Instruction *NV = FoldOpIntoPhi(I))
+ return NV;
}
if (Value *Op0v = dyn_castNegVal(Op0)) // -X * -Y = X*Y
}
Instruction *InstCombiner::visitDiv(BinaryOperator &I) {
- if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) {
+ Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
+
+ if (isa<UndefValue>(Op0)) // undef / X -> 0
+ return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
+ if (isa<UndefValue>(Op1))
+ return ReplaceInstUsesWith(I, Op1); // X / undef -> undef
+
+ if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
// div X, 1 == X
if (RHS->equalsInt(1))
- return ReplaceInstUsesWith(I, I.getOperand(0));
+ return ReplaceInstUsesWith(I, Op0);
// div X, -1 == -X
if (RHS->isAllOnesValue())
- return BinaryOperator::createNeg(I.getOperand(0));
+ return BinaryOperator::createNeg(Op0);
+
+ if (Instruction *LHS = dyn_cast<Instruction>(Op0))
+ if (LHS->getOpcode() == Instruction::Div)
+ if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) {
+ // (X / C1) / C2 -> X / (C1*C2)
+ return BinaryOperator::createDiv(LHS->getOperand(0),
+ ConstantExpr::getMul(RHS, LHSRHS));
+ }
// Check to see if this is an unsigned division with an exact power of 2,
// if so, convert to a right shift.
if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
if (uint64_t Val = C->getValue()) // Don't break X / 0
if (uint64_t C = Log2(Val))
- return new ShiftInst(Instruction::Shr, I.getOperand(0),
+ return new ShiftInst(Instruction::Shr, Op0,
ConstantUInt::get(Type::UByteTy, C));
+
+ // -X/C -> X/-C
+ if (RHS->getType()->isSigned())
+ if (Value *LHSNeg = dyn_castNegVal(Op0))
+ return BinaryOperator::createDiv(LHSNeg, ConstantExpr::getNeg(RHS));
+
+ if (!RHS->isNullValue()) {
+ if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
+ if (Instruction *R = FoldOpIntoSelect(I, SI, this))
+ return R;
+ if (isa<PHINode>(Op0))
+ if (Instruction *NV = FoldOpIntoPhi(I))
+ return NV;
+ }
}
+ // If this is 'udiv X, (Cond ? C1, C2)' where C1&C2 are powers of two,
+ // transform this into: '(Cond ? (udiv X, C1) : (udiv X, C2))'.
+ if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
+ if (ConstantUInt *STO = dyn_cast<ConstantUInt>(SI->getOperand(1)))
+ if (ConstantUInt *SFO = dyn_cast<ConstantUInt>(SI->getOperand(2))) {
+ if (STO->getValue() == 0) { // Couldn't be this argument.
+ I.setOperand(1, SFO);
+ return &I;
+ } else if (SFO->getValue() == 0) {
+ I.setOperand(1, STO);
+ return &I;
+ }
+
+ if (uint64_t TSA = Log2(STO->getValue()))
+ if (uint64_t FSA = Log2(SFO->getValue())) {
+ Constant *TC = ConstantUInt::get(Type::UByteTy, TSA);
+ Instruction *TSI = new ShiftInst(Instruction::Shr, Op0,
+ TC, SI->getName()+".t");
+ TSI = InsertNewInstBefore(TSI, I);
+
+ Constant *FC = ConstantUInt::get(Type::UByteTy, FSA);
+ Instruction *FSI = new ShiftInst(Instruction::Shr, Op0,
+ FC, SI->getName()+".f");
+ FSI = InsertNewInstBefore(FSI, I);
+ return new SelectInst(SI->getOperand(0), TSI, FSI);
+ }
+ }
+
// 0 / X == 0, we don't need to preserve faults!
- if (ConstantInt *LHS = dyn_cast<ConstantInt>(I.getOperand(0)))
+ if (ConstantInt *LHS = dyn_cast<ConstantInt>(Op0))
if (LHS->equalsInt(0))
return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
Instruction *InstCombiner::visitRem(BinaryOperator &I) {
+ Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
if (I.getType()->isSigned())
- if (Value *RHSNeg = dyn_castNegVal(I.getOperand(1)))
+ if (Value *RHSNeg = dyn_castNegVal(Op1))
if (!isa<ConstantSInt>(RHSNeg) ||
- cast<ConstantSInt>(RHSNeg)->getValue() >= 0) {
+ 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 (isa<UndefValue>(Op0)) // undef % X -> 0
+ return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
+ if (isa<UndefValue>(Op1))
+ return ReplaceInstUsesWith(I, Op1); // X % undef -> undef
+
+ if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
if (RHS->equalsInt(1)) // X % 1 == 0
return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
if (uint64_t Val = C->getValue()) // Don't break X % 0 (divide by zero)
if (!(Val & (Val-1))) // Power of 2
- return BinaryOperator::createAnd(I.getOperand(0),
- ConstantUInt::get(I.getType(), Val-1));
+ return BinaryOperator::createAnd(Op0,
+ ConstantUInt::get(I.getType(), Val-1));
+
+ if (!RHS->isNullValue()) {
+ if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
+ if (Instruction *R = FoldOpIntoSelect(I, SI, this))
+ return R;
+ if (isa<PHINode>(Op0))
+ if (Instruction *NV = FoldOpIntoPhi(I))
+ return NV;
+ }
}
+ // If this is 'urem X, (Cond ? C1, C2)' where C1&C2 are powers of two,
+ // transform this into: '(Cond ? (urem X, C1) : (urem X, C2))'.
+ if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
+ if (ConstantUInt *STO = dyn_cast<ConstantUInt>(SI->getOperand(1)))
+ if (ConstantUInt *SFO = dyn_cast<ConstantUInt>(SI->getOperand(2))) {
+ if (STO->getValue() == 0) { // Couldn't be this argument.
+ I.setOperand(1, SFO);
+ return &I;
+ } else if (SFO->getValue() == 0) {
+ I.setOperand(1, STO);
+ return &I;
+ }
+
+ if (!(STO->getValue() & (STO->getValue()-1)) &&
+ !(SFO->getValue() & (SFO->getValue()-1))) {
+ Value *TrueAnd = InsertNewInstBefore(BinaryOperator::createAnd(Op0,
+ SubOne(STO), SI->getName()+".t"), I);
+ Value *FalseAnd = InsertNewInstBefore(BinaryOperator::createAnd(Op0,
+ SubOne(SFO), SI->getName()+".f"), I);
+ return new SelectInst(SI->getOperand(0), TrueAnd, FalseAnd);
+ }
+ }
+
// 0 % X == 0, we don't need to preserve faults!
- if (ConstantInt *LHS = dyn_cast<ConstantInt>(I.getOperand(0)))
+ if (ConstantInt *LHS = dyn_cast<ConstantInt>(Op0))
if (LHS->equalsInt(0))
return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
return V && (V & (V-1)) == 0;
}
+#if 0 // Currently unused
+// isLowOnes - Return true if the constant is of the form 0+1+.
+static bool isLowOnes(const ConstantInt *CI) {
+ uint64_t V = CI->getRawValue();
+
+ // There won't be bits set in parts that the type doesn't contain.
+ V &= ConstantInt::getAllOnesValue(CI->getType())->getRawValue();
+
+ uint64_t U = V+1; // If it is low ones, this should be a power of two.
+ return U && V && (U & V) == 0;
+}
+#endif
+
+// isHighOnes - Return true if the constant is of the form 1+0+.
+// This is the same as lowones(~X).
+static bool isHighOnes(const ConstantInt *CI) {
+ uint64_t V = ~CI->getRawValue();
+
+ // There won't be bits set in parts that the type doesn't contain.
+ V &= ConstantInt::getAllOnesValue(CI->getType())->getRawValue();
+
+ uint64_t U = V+1; // If it is low ones, this should be a power of two.
+ return U && V && (U & V) == 0;
+}
+
+
/// getSetCondCode - Encode a setcc opcode into a three bit mask. These bits
/// are carefully arranged to allow folding of expressions such as:
///
};
+/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
+/// this predicate to simplify operations downstream. V and Mask are known to
+/// be the same type.
+static bool MaskedValueIsZero(Value *V, ConstantIntegral *Mask) {
+ if (isa<UndefValue>(V) || Mask->isNullValue())
+ return true;
+ if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(V))
+ return ConstantExpr::getAnd(CI, Mask)->isNullValue();
+
+ if (Instruction *I = dyn_cast<Instruction>(V)) {
+ switch (I->getOpcode()) {
+ case Instruction::And:
+ // (X & C1) & C2 == 0 iff C1 & C2 == 0.
+ if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(I->getOperand(1)))
+ if (ConstantExpr::getAnd(CI, Mask)->isNullValue())
+ return true;
+ break;
+ case Instruction::Or:
+ // If the LHS and the RHS are MaskedValueIsZero, the result is also zero.
+ return MaskedValueIsZero(I->getOperand(1), Mask) &&
+ MaskedValueIsZero(I->getOperand(0), Mask);
+ case Instruction::Select:
+ // If the T and F values are MaskedValueIsZero, the result is also zero.
+ return MaskedValueIsZero(I->getOperand(2), Mask) &&
+ MaskedValueIsZero(I->getOperand(1), Mask);
+ case Instruction::Cast: {
+ const Type *SrcTy = I->getOperand(0)->getType();
+ if (SrcTy->isIntegral()) {
+ // (cast <ty> X to int) & C2 == 0 iff <ty> could not have contained C2.
+ if (SrcTy->isUnsigned() && // Only handle zero ext.
+ ConstantExpr::getCast(Mask, SrcTy)->isNullValue())
+ return true;
+
+ // If this is a noop cast, recurse.
+ if (SrcTy != Type::BoolTy)
+ if ((SrcTy->isSigned() && SrcTy->getUnsignedVersion() ==I->getType()) ||
+ SrcTy->getSignedVersion() == I->getType()) {
+ Constant *NewMask =
+ ConstantExpr::getCast(Mask, I->getOperand(0)->getType());
+ return MaskedValueIsZero(I->getOperand(0),
+ cast<ConstantIntegral>(NewMask));
+ }
+ }
+ break;
+ }
+ case Instruction::Shl:
+ // (shl X, C1) & C2 == 0 iff (-1 << C1) & C2 == 0
+ if (ConstantUInt *SA = dyn_cast<ConstantUInt>(I->getOperand(1))) {
+ Constant *C1 = ConstantIntegral::getAllOnesValue(I->getType());
+ C1 = ConstantExpr::getShl(C1, SA);
+ C1 = ConstantExpr::getAnd(C1, Mask);
+ if (C1->isNullValue())
+ return true;
+ }
+ break;
+ case Instruction::Shr:
+ // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
+ if (ConstantUInt *SA = dyn_cast<ConstantUInt>(I->getOperand(1)))
+ if (I->getType()->isUnsigned()) {
+ Constant *C1 = ConstantIntegral::getAllOnesValue(I->getType());
+ C1 = ConstantExpr::getShr(C1, SA);
+ C1 = ConstantExpr::getAnd(C1, Mask);
+ if (C1->isNullValue())
+ return true;
+ }
+ break;
+ }
+ }
+
+ return false;
+}
+
// OptAndOp - This handles expressions of the form ((val OP C1) & C2). Where
// the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. Op is
// guaranteed to be either a shift instruction or a binary operator.
switch (Op->getOpcode()) {
case Instruction::Xor:
- if (Together->isNullValue()) {
- // (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0
- return BinaryOperator::createAnd(X, AndRHS);
- } else if (Op->hasOneUse()) {
+ if (Op->hasOneUse()) {
// (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
std::string OpName = Op->getName(); Op->setName("");
Instruction *And = BinaryOperator::createAnd(X, AndRHS, OpName);
}
break;
case Instruction::Or:
- // (X | C1) & C2 --> X & C2 iff C1 & C1 == 0
- if (Together->isNullValue())
- return BinaryOperator::createAnd(X, AndRHS);
- else {
- if (Together == AndRHS) // (X | C) & C --> C
- return ReplaceInstUsesWith(TheAnd, AndRHS);
+ 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::createOr(X, Together, Op0Name);
- InsertNewInstBefore(Or, TheAnd);
- return BinaryOperator::createAnd(Or, AndRHS);
- }
+ if (Op->hasOneUse() && Together != OpRHS) {
+ // (X | C1) & C2 --> (X | (C1&C2)) & C2
+ std::string Op0Name = Op->getName(); Op->setName("");
+ Instruction *Or = BinaryOperator::createOr(X, Together, Op0Name);
+ InsertNewInstBefore(Or, TheAnd);
+ return BinaryOperator::createAnd(Or, AndRHS);
}
break;
case Instruction::Add:
// the anded constant includes them, clear them now!
//
Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
- Constant *CI = ConstantExpr::getAnd(AndRHS,
- ConstantExpr::getShl(AllOne, OpRHS));
- if (CI != AndRHS) {
+ Constant *ShlMask = ConstantExpr::getShl(AllOne, OpRHS);
+ Constant *CI = ConstantExpr::getAnd(AndRHS, ShlMask);
+
+ if (CI == ShlMask) { // Masking out bits that the shift already masks
+ return ReplaceInstUsesWith(TheAnd, Op); // No need for the and.
+ } else if (CI != AndRHS) { // Reducing bits set in and.
TheAnd.setOperand(1, CI);
return &TheAnd;
}
//
if (AndRHS->getType()->isUnsigned()) {
Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
- Constant *CI = ConstantExpr::getAnd(AndRHS,
- ConstantExpr::getShr(AllOne, OpRHS));
- if (CI != AndRHS) {
- TheAnd.setOperand(1, CI);
+ Constant *ShrMask = ConstantExpr::getShr(AllOne, OpRHS);
+ Constant *CI = ConstantExpr::getAnd(AndRHS, ShrMask);
+
+ if (CI == ShrMask) { // Masking out bits that the shift already masks.
+ return ReplaceInstUsesWith(TheAnd, Op);
+ } else if (CI != AndRHS) {
+ TheAnd.setOperand(1, CI); // Reduce bits set in and cst.
return &TheAnd;
}
+ } else { // Signed shr.
+ // See if this is shifting in some sign extension, then masking it out
+ // with an and.
+ if (Op->hasOneUse()) {
+ Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
+ Constant *ShrMask = ConstantExpr::getUShr(AllOne, OpRHS);
+ Constant *CI = ConstantExpr::getAnd(AndRHS, ShrMask);
+ if (CI == AndRHS) { // Masking out bits shifted in.
+ // Make the argument unsigned.
+ Value *ShVal = Op->getOperand(0);
+ ShVal = InsertCastBefore(ShVal,
+ ShVal->getType()->getUnsignedVersion(),
+ TheAnd);
+ ShVal = InsertNewInstBefore(new ShiftInst(Instruction::Shr, ShVal,
+ OpRHS, Op->getName()),
+ TheAnd);
+ Value *AndRHS2 = ConstantExpr::getCast(AndRHS, ShVal->getType());
+ ShVal = InsertNewInstBefore(BinaryOperator::createAnd(ShVal, AndRHS2,
+ TheAnd.getName()),
+ TheAnd);
+ return new CastInst(ShVal, Op->getType());
+ }
+ }
}
break;
}
}
+/// InsertRangeTest - Emit a computation of: (V >= Lo && V < Hi) if Inside is
+/// true, otherwise (V < Lo || V >= Hi). In pratice, we emit the more efficient
+/// (V-Lo) <u Hi-Lo. This method expects that Lo <= Hi. IB is the location to
+/// insert new instructions.
+Instruction *InstCombiner::InsertRangeTest(Value *V, Constant *Lo, Constant *Hi,
+ bool Inside, Instruction &IB) {
+ assert(cast<ConstantBool>(ConstantExpr::getSetLE(Lo, Hi))->getValue() &&
+ "Lo is not <= Hi in range emission code!");
+ if (Inside) {
+ if (Lo == Hi) // Trivially false.
+ return new SetCondInst(Instruction::SetNE, V, V);
+ if (cast<ConstantIntegral>(Lo)->isMinValue())
+ return new SetCondInst(Instruction::SetLT, V, Hi);
+
+ Constant *AddCST = ConstantExpr::getNeg(Lo);
+ Instruction *Add = BinaryOperator::createAdd(V, AddCST,V->getName()+".off");
+ InsertNewInstBefore(Add, IB);
+ // Convert to unsigned for the comparison.
+ const Type *UnsType = Add->getType()->getUnsignedVersion();
+ Value *OffsetVal = InsertCastBefore(Add, UnsType, IB);
+ AddCST = ConstantExpr::getAdd(AddCST, Hi);
+ AddCST = ConstantExpr::getCast(AddCST, UnsType);
+ return new SetCondInst(Instruction::SetLT, OffsetVal, AddCST);
+ }
+
+ if (Lo == Hi) // Trivially true.
+ return new SetCondInst(Instruction::SetEQ, V, V);
+
+ Hi = SubOne(cast<ConstantInt>(Hi));
+ if (cast<ConstantIntegral>(Lo)->isMinValue()) // V < 0 || V >= Hi ->'V > Hi-1'
+ return new SetCondInst(Instruction::SetGT, V, Hi);
+
+ // Emit X-Lo > Hi-Lo-1
+ Constant *AddCST = ConstantExpr::getNeg(Lo);
+ Instruction *Add = BinaryOperator::createAdd(V, AddCST, V->getName()+".off");
+ InsertNewInstBefore(Add, IB);
+ // Convert to unsigned for the comparison.
+ const Type *UnsType = Add->getType()->getUnsignedVersion();
+ Value *OffsetVal = InsertCastBefore(Add, UnsType, IB);
+ AddCST = ConstantExpr::getAdd(AddCST, Hi);
+ AddCST = ConstantExpr::getCast(AddCST, UnsType);
+ return new SetCondInst(Instruction::SetGT, OffsetVal, AddCST);
+}
+
+
Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
bool Changed = SimplifyCommutative(I);
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
- // and X, X = X and X, 0 == 0
- if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
+ if (isa<UndefValue>(Op1)) // X & undef -> 0
+ return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
+
+ // and X, X = X
+ if (Op0 == Op1)
return ReplaceInstUsesWith(I, Op1);
- // and X, -1 == X
- if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
- if (RHS->isAllOnesValue())
+ if (ConstantIntegral *AndRHS = dyn_cast<ConstantIntegral>(Op1)) {
+ // and X, -1 == X
+ if (AndRHS->isAllOnesValue())
+ return ReplaceInstUsesWith(I, Op0);
+
+ if (MaskedValueIsZero(Op0, AndRHS)) // LHS & RHS == 0
+ return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
+
+ // If the mask is not masking out any bits, there is no reason to do the
+ // and in the first place.
+ ConstantIntegral *NotAndRHS =
+ cast<ConstantIntegral>(ConstantExpr::getNot(AndRHS));
+ if (MaskedValueIsZero(Op0, NotAndRHS))
return ReplaceInstUsesWith(I, Op0);
// Optimize a variety of ((val OP C1) & C2) combinations...
if (isa<BinaryOperator>(Op0) || isa<ShiftInst>(Op0)) {
Instruction *Op0I = cast<Instruction>(Op0);
- Value *X = Op0I->getOperand(0);
+ Value *Op0LHS = Op0I->getOperand(0);
+ Value *Op0RHS = Op0I->getOperand(1);
+ switch (Op0I->getOpcode()) {
+ case Instruction::Xor:
+ case Instruction::Or:
+ // (X ^ V) & C2 --> (X & C2) iff (V & C2) == 0
+ // (X | V) & C2 --> (X & C2) iff (V & C2) == 0
+ if (MaskedValueIsZero(Op0LHS, AndRHS))
+ return BinaryOperator::createAnd(Op0RHS, AndRHS);
+ if (MaskedValueIsZero(Op0RHS, AndRHS))
+ return BinaryOperator::createAnd(Op0LHS, AndRHS);
+
+ // If the mask is only needed on one incoming arm, push it up.
+ if (Op0I->hasOneUse()) {
+ if (MaskedValueIsZero(Op0LHS, NotAndRHS)) {
+ // Not masking anything out for the LHS, move to RHS.
+ Instruction *NewRHS = BinaryOperator::createAnd(Op0RHS, AndRHS,
+ Op0RHS->getName()+".masked");
+ InsertNewInstBefore(NewRHS, I);
+ return BinaryOperator::create(
+ cast<BinaryOperator>(Op0I)->getOpcode(), Op0LHS, NewRHS);
+ }
+ if (!isa<Constant>(NotAndRHS) &&
+ MaskedValueIsZero(Op0RHS, NotAndRHS)) {
+ // Not masking anything out for the RHS, move to LHS.
+ Instruction *NewLHS = BinaryOperator::createAnd(Op0LHS, AndRHS,
+ Op0LHS->getName()+".masked");
+ InsertNewInstBefore(NewLHS, I);
+ return BinaryOperator::create(
+ cast<BinaryOperator>(Op0I)->getOpcode(), NewLHS, Op0RHS);
+ }
+ }
+
+ break;
+ case Instruction::And:
+ // (X & V) & C2 --> 0 iff (V & C2) == 0
+ if (MaskedValueIsZero(Op0LHS, AndRHS) ||
+ MaskedValueIsZero(Op0RHS, AndRHS))
+ return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
+ break;
+ }
+
if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
- if (Instruction *Res = OptAndOp(Op0I, Op0CI, RHS, I))
+ if (Instruction *Res = OptAndOp(Op0I, Op0CI, AndRHS, I))
return Res;
+ } else if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
+ const Type *SrcTy = CI->getOperand(0)->getType();
+
+ // If this is an integer sign or zero extension instruction.
+ if (SrcTy->isIntegral() &&
+ SrcTy->getPrimitiveSize() < CI->getType()->getPrimitiveSize()) {
+
+ if (SrcTy->isUnsigned()) {
+ // See if this and is clearing out bits that are known to be zero
+ // anyway (due to the zero extension).
+ Constant *Mask = ConstantIntegral::getAllOnesValue(SrcTy);
+ Mask = ConstantExpr::getZeroExtend(Mask, CI->getType());
+ Constant *Result = ConstantExpr::getAnd(Mask, AndRHS);
+ if (Result == Mask) // The "and" isn't doing anything, remove it.
+ return ReplaceInstUsesWith(I, CI);
+ if (Result != AndRHS) { // Reduce the and RHS constant.
+ I.setOperand(1, Result);
+ return &I;
+ }
+
+ } else {
+ if (CI->hasOneUse() && SrcTy->isInteger()) {
+ // We can only do this if all of the sign bits brought in are masked
+ // out. Compute this by first getting 0000011111, then inverting
+ // it.
+ Constant *Mask = ConstantIntegral::getAllOnesValue(SrcTy);
+ Mask = ConstantExpr::getZeroExtend(Mask, CI->getType());
+ Mask = ConstantExpr::getNot(Mask); // 1's in the new bits.
+ if (ConstantExpr::getAnd(Mask, AndRHS)->isNullValue()) {
+ // If the and is clearing all of the sign bits, change this to a
+ // zero extension cast. To do this, cast the cast input to
+ // unsigned, then to the requested size.
+ Value *CastOp = CI->getOperand(0);
+ Instruction *NC =
+ new CastInst(CastOp, CastOp->getType()->getUnsignedVersion(),
+ CI->getName()+".uns");
+ NC = InsertNewInstBefore(NC, I);
+ // Finally, insert a replacement for CI.
+ NC = new CastInst(NC, CI->getType(), CI->getName());
+ CI->setName("");
+ NC = InsertNewInstBefore(NC, I);
+ WorkList.push_back(CI); // Delete CI later.
+ I.setOperand(0, NC);
+ return &I; // The AND operand was modified.
+ }
+ }
+ }
+ }
}
// Try to fold constant and into select arguments.
if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
- if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
+ if (Instruction *R = FoldOpIntoSelect(I, SI, this))
return R;
+ if (isa<PHINode>(Op0))
+ if (Instruction *NV = FoldOpIntoPhi(I))
+ return NV;
}
Value *Op0NotVal = dyn_castNotVal(Op0);
if (Op0NotVal == Op1 || Op1NotVal == Op0) // A & ~A == ~A & A == 0
return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
- // (~A & ~B) == (~(A | B)) - Demorgan's Law
+ // (~A & ~B) == (~(A | B)) - De Morgan's Law
if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
Instruction *Or = BinaryOperator::createOr(Op0NotVal, Op1NotVal,
I.getName()+".demorgan");
return BinaryOperator::createNot(Or);
}
- // (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
- if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
+ if (SetCondInst *RHS = dyn_cast<SetCondInst>(Op1)) {
+ // (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
return R;
- return Changed ? &I : 0;
-}
+ Value *LHSVal, *RHSVal;
+ ConstantInt *LHSCst, *RHSCst;
+ Instruction::BinaryOps LHSCC, RHSCC;
+ if (match(Op0, m_SetCond(LHSCC, m_Value(LHSVal), m_ConstantInt(LHSCst))))
+ if (match(RHS, m_SetCond(RHSCC, m_Value(RHSVal), m_ConstantInt(RHSCst))))
+ if (LHSVal == RHSVal && // Found (X setcc C1) & (X setcc C2)
+ // Set[GL]E X, CST is folded to Set[GL]T elsewhere.
+ LHSCC != Instruction::SetGE && LHSCC != Instruction::SetLE &&
+ RHSCC != Instruction::SetGE && RHSCC != Instruction::SetLE) {
+ // Ensure that the larger constant is on the RHS.
+ Constant *Cmp = ConstantExpr::getSetGT(LHSCst, RHSCst);
+ SetCondInst *LHS = cast<SetCondInst>(Op0);
+ if (cast<ConstantBool>(Cmp)->getValue()) {
+ std::swap(LHS, RHS);
+ std::swap(LHSCst, RHSCst);
+ std::swap(LHSCC, RHSCC);
+ }
+ // At this point, we know we have have two setcc instructions
+ // comparing a value against two constants and and'ing the result
+ // together. Because of the above check, we know that we only have
+ // SetEQ, SetNE, SetLT, and SetGT here. We also know (from the
+ // FoldSetCCLogical check above), that the two constants are not
+ // equal.
+ assert(LHSCst != RHSCst && "Compares not folded above?");
+ switch (LHSCC) {
+ default: assert(0 && "Unknown integer condition code!");
+ case Instruction::SetEQ:
+ switch (RHSCC) {
+ default: assert(0 && "Unknown integer condition code!");
+ case Instruction::SetEQ: // (X == 13 & X == 15) -> false
+ case Instruction::SetGT: // (X == 13 & X > 15) -> false
+ return ReplaceInstUsesWith(I, ConstantBool::False);
+ case Instruction::SetNE: // (X == 13 & X != 15) -> X == 13
+ case Instruction::SetLT: // (X == 13 & X < 15) -> X == 13
+ return ReplaceInstUsesWith(I, LHS);
+ }
+ case Instruction::SetNE:
+ switch (RHSCC) {
+ default: assert(0 && "Unknown integer condition code!");
+ case Instruction::SetLT:
+ if (LHSCst == SubOne(RHSCst)) // (X != 13 & X < 14) -> X < 13
+ return new SetCondInst(Instruction::SetLT, LHSVal, LHSCst);
+ break; // (X != 13 & X < 15) -> no change
+ case Instruction::SetEQ: // (X != 13 & X == 15) -> X == 15
+ case Instruction::SetGT: // (X != 13 & X > 15) -> X > 15
+ return ReplaceInstUsesWith(I, RHS);
+ case Instruction::SetNE:
+ if (LHSCst == SubOne(RHSCst)) {// (X != 13 & X != 14) -> X-13 >u 1
+ Constant *AddCST = ConstantExpr::getNeg(LHSCst);
+ Instruction *Add = BinaryOperator::createAdd(LHSVal, AddCST,
+ LHSVal->getName()+".off");
+ InsertNewInstBefore(Add, I);
+ const Type *UnsType = Add->getType()->getUnsignedVersion();
+ Value *OffsetVal = InsertCastBefore(Add, UnsType, I);
+ AddCST = ConstantExpr::getSub(RHSCst, LHSCst);
+ AddCST = ConstantExpr::getCast(AddCST, UnsType);
+ return new SetCondInst(Instruction::SetGT, OffsetVal, AddCST);
+ }
+ break; // (X != 13 & X != 15) -> no change
+ }
+ break;
+ case Instruction::SetLT:
+ switch (RHSCC) {
+ default: assert(0 && "Unknown integer condition code!");
+ case Instruction::SetEQ: // (X < 13 & X == 15) -> false
+ case Instruction::SetGT: // (X < 13 & X > 15) -> false
+ return ReplaceInstUsesWith(I, ConstantBool::False);
+ case Instruction::SetNE: // (X < 13 & X != 15) -> X < 13
+ case Instruction::SetLT: // (X < 13 & X < 15) -> X < 13
+ return ReplaceInstUsesWith(I, LHS);
+ }
+ case Instruction::SetGT:
+ switch (RHSCC) {
+ default: assert(0 && "Unknown integer condition code!");
+ case Instruction::SetEQ: // (X > 13 & X == 15) -> X > 13
+ return ReplaceInstUsesWith(I, LHS);
+ case Instruction::SetGT: // (X > 13 & X > 15) -> X > 15
+ return ReplaceInstUsesWith(I, RHS);
+ case Instruction::SetNE:
+ if (RHSCst == AddOne(LHSCst)) // (X > 13 & X != 14) -> X > 14
+ return new SetCondInst(Instruction::SetGT, LHSVal, RHSCst);
+ break; // (X > 13 & X != 15) -> no change
+ case Instruction::SetLT: // (X > 13 & X < 15) -> (X-14) <u 1
+ return InsertRangeTest(LHSVal, AddOne(LHSCst), RHSCst, true, I);
+ }
+ }
+ }
+ }
+
+ return Changed ? &I : 0;
+}
Instruction *InstCombiner::visitOr(BinaryOperator &I) {
bool Changed = SimplifyCommutative(I);
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
+ if (isa<UndefValue>(Op1))
+ return ReplaceInstUsesWith(I, // X | undef -> -1
+ ConstantIntegral::getAllOnesValue(I.getType()));
+
// or X, X = X or X, 0 == X
if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
return ReplaceInstUsesWith(I, Op0);
// or X, -1 == -1
if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
- 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::createOr(Op0I->getOperand(0), RHS,
- Op0Name);
- InsertNewInstBefore(Or, I);
- return BinaryOperator::createAnd(Or, ConstantExpr::getOr(RHS, Op0CI));
- }
+ // If X is known to only contain bits that already exist in RHS, just
+ // replace this instruction with RHS directly.
+ if (MaskedValueIsZero(Op0,
+ cast<ConstantIntegral>(ConstantExpr::getNot(RHS))))
+ return ReplaceInstUsesWith(I, RHS);
+
+ 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::createOr(Op0I->getOperand(0), RHS,
- Op0Name);
- InsertNewInstBefore(Or, I);
- return BinaryOperator::createXor(Or,
- ConstantExpr::getAnd(Op0CI,
- ConstantExpr::getNot(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.
if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
- if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
+ if (Instruction *R = FoldOpIntoSelect(I, SI, this))
return R;
+ if (isa<PHINode>(Op0))
+ if (Instruction *NV = FoldOpIntoPhi(I))
+ return NV;
}
// (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::createAnd(LHS->getOperand(0),
- ConstantExpr::getOr(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)) {
- Value *And = InsertNewInstBefore(
- BinaryOperator::createAnd(Op0NotVal,
- Op1NotVal,I.getName()+".demorgan"),I);
- 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)
- if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
+ if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1))) {
if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
return R;
+ Value *LHSVal, *RHSVal;
+ ConstantInt *LHSCst, *RHSCst;
+ Instruction::BinaryOps LHSCC, RHSCC;
+ if (match(Op0, m_SetCond(LHSCC, m_Value(LHSVal), m_ConstantInt(LHSCst))))
+ if (match(RHS, m_SetCond(RHSCC, m_Value(RHSVal), m_ConstantInt(RHSCst))))
+ if (LHSVal == RHSVal && // Found (X setcc C1) | (X setcc C2)
+ // Set[GL]E X, CST is folded to Set[GL]T elsewhere.
+ LHSCC != Instruction::SetGE && LHSCC != Instruction::SetLE &&
+ RHSCC != Instruction::SetGE && RHSCC != Instruction::SetLE) {
+ // Ensure that the larger constant is on the RHS.
+ Constant *Cmp = ConstantExpr::getSetGT(LHSCst, RHSCst);
+ SetCondInst *LHS = cast<SetCondInst>(Op0);
+ if (cast<ConstantBool>(Cmp)->getValue()) {
+ std::swap(LHS, RHS);
+ std::swap(LHSCst, RHSCst);
+ std::swap(LHSCC, RHSCC);
+ }
+
+ // At this point, we know we have have two setcc instructions
+ // comparing a value against two constants and or'ing the result
+ // together. Because of the above check, we know that we only have
+ // SetEQ, SetNE, SetLT, and SetGT here. We also know (from the
+ // FoldSetCCLogical check above), that the two constants are not
+ // equal.
+ assert(LHSCst != RHSCst && "Compares not folded above?");
+
+ switch (LHSCC) {
+ default: assert(0 && "Unknown integer condition code!");
+ case Instruction::SetEQ:
+ switch (RHSCC) {
+ default: assert(0 && "Unknown integer condition code!");
+ case Instruction::SetEQ:
+ if (LHSCst == SubOne(RHSCst)) {// (X == 13 | X == 14) -> X-13 <u 2
+ Constant *AddCST = ConstantExpr::getNeg(LHSCst);
+ Instruction *Add = BinaryOperator::createAdd(LHSVal, AddCST,
+ LHSVal->getName()+".off");
+ InsertNewInstBefore(Add, I);
+ const Type *UnsType = Add->getType()->getUnsignedVersion();
+ Value *OffsetVal = InsertCastBefore(Add, UnsType, I);
+ AddCST = ConstantExpr::getSub(AddOne(RHSCst), LHSCst);
+ AddCST = ConstantExpr::getCast(AddCST, UnsType);
+ return new SetCondInst(Instruction::SetLT, OffsetVal, AddCST);
+ }
+ break; // (X == 13 | X == 15) -> no change
+
+ case Instruction::SetGT:
+ if (LHSCst == SubOne(RHSCst)) // (X == 13 | X > 14) -> X > 13
+ return new SetCondInst(Instruction::SetGT, LHSVal, LHSCst);
+ break; // (X == 13 | X > 15) -> no change
+ case Instruction::SetNE: // (X == 13 | X != 15) -> X != 15
+ case Instruction::SetLT: // (X == 13 | X < 15) -> X < 15
+ return ReplaceInstUsesWith(I, RHS);
+ }
+ break;
+ case Instruction::SetNE:
+ switch (RHSCC) {
+ default: assert(0 && "Unknown integer condition code!");
+ case Instruction::SetLT: // (X != 13 | X < 15) -> X < 15
+ return ReplaceInstUsesWith(I, RHS);
+ case Instruction::SetEQ: // (X != 13 | X == 15) -> X != 13
+ case Instruction::SetGT: // (X != 13 | X > 15) -> X != 13
+ return ReplaceInstUsesWith(I, LHS);
+ case Instruction::SetNE: // (X != 13 | X != 15) -> true
+ return ReplaceInstUsesWith(I, ConstantBool::True);
+ }
+ break;
+ case Instruction::SetLT:
+ switch (RHSCC) {
+ default: assert(0 && "Unknown integer condition code!");
+ case Instruction::SetEQ: // (X < 13 | X == 14) -> no change
+ break;
+ case Instruction::SetGT: // (X < 13 | X > 15) -> (X-13) > 2
+ return InsertRangeTest(LHSVal, LHSCst, AddOne(RHSCst), false, I);
+ case Instruction::SetNE: // (X < 13 | X != 15) -> X != 15
+ case Instruction::SetLT: // (X < 13 | X < 15) -> X < 15
+ return ReplaceInstUsesWith(I, RHS);
+ }
+ break;
+ case Instruction::SetGT:
+ switch (RHSCC) {
+ default: assert(0 && "Unknown integer condition code!");
+ case Instruction::SetEQ: // (X > 13 | X == 15) -> X > 13
+ case Instruction::SetGT: // (X > 13 | X > 15) -> X > 13
+ return ReplaceInstUsesWith(I, LHS);
+ case Instruction::SetNE: // (X > 13 | X != 15) -> true
+ case Instruction::SetLT: // (X > 13 | X < 15) -> true
+ return ReplaceInstUsesWith(I, ConstantBool::True);
+ }
+ }
+ }
+ }
return Changed ? &I : 0;
}
bool Changed = SimplifyCommutative(I);
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
+ if (isa<UndefValue>(Op1))
+ return ReplaceInstUsesWith(I, Op1); // X ^ undef -> undef
+
// 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?");
// Try to fold constant and into select arguments.
if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
- if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
+ if (Instruction *R = FoldOpIntoSelect(I, SI, this))
return R;
+ if (isa<PHINode>(Op0))
+ if (Instruction *NV = FoldOpIntoPhi(I))
+ return NV;
}
if (Value *X = dyn_castNotVal(Op0)) // ~A ^ A == -1
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::getAnd(C1, C2)->isNullValue())
- return BinaryOperator::createOr(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)))
return Changed ? &I : 0;
}
-// AddOne, SubOne - Add or subtract a constant one from an integer constant...
-static Constant *AddOne(ConstantInt *C) {
- return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
+/// MulWithOverflow - Compute Result = In1*In2, returning true if the result
+/// overflowed for this type.
+static bool MulWithOverflow(ConstantInt *&Result, ConstantInt *In1,
+ ConstantInt *In2) {
+ Result = cast<ConstantInt>(ConstantExpr::getMul(In1, In2));
+ return !In2->isNullValue() && ConstantExpr::getDiv(Result, In2) != In1;
}
-static Constant *SubOne(ConstantInt *C) {
- return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
+
+static bool isPositive(ConstantInt *C) {
+ return cast<ConstantSInt>(C)->getValue() >= 0;
}
-// isTrueWhenEqual - Return true if the specified setcondinst instruction is
-// true when both operands are equal...
-//
-static bool isTrueWhenEqual(Instruction &I) {
- return I.getOpcode() == Instruction::SetEQ ||
- I.getOpcode() == Instruction::SetGE ||
- I.getOpcode() == Instruction::SetLE;
+/// AddWithOverflow - Compute Result = In1+In2, returning true if the result
+/// overflowed for this type.
+static bool AddWithOverflow(ConstantInt *&Result, ConstantInt *In1,
+ ConstantInt *In2) {
+ Result = cast<ConstantInt>(ConstantExpr::getAdd(In1, In2));
+
+ if (In1->getType()->isUnsigned())
+ return cast<ConstantUInt>(Result)->getValue() <
+ cast<ConstantUInt>(In1)->getValue();
+ if (isPositive(In1) != isPositive(In2))
+ return false;
+ if (isPositive(In1))
+ return cast<ConstantSInt>(Result)->getValue() <
+ cast<ConstantSInt>(In1)->getValue();
+ return cast<ConstantSInt>(Result)->getValue() >
+ cast<ConstantSInt>(In1)->getValue();
+}
+
+/// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the
+/// code necessary to compute the offset from the base pointer (without adding
+/// in the base pointer). Return the result as a signed integer of intptr size.
+static Value *EmitGEPOffset(User *GEP, Instruction &I, InstCombiner &IC) {
+ TargetData &TD = IC.getTargetData();
+ gep_type_iterator GTI = gep_type_begin(GEP);
+ const Type *UIntPtrTy = TD.getIntPtrType();
+ const Type *SIntPtrTy = UIntPtrTy->getSignedVersion();
+ Value *Result = Constant::getNullValue(SIntPtrTy);
+
+ // Build a mask for high order bits.
+ uint64_t PtrSizeMask = ~0ULL;
+ PtrSizeMask >>= 64-(TD.getPointerSize()*8);
+
+ for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i, ++GTI) {
+ Value *Op = GEP->getOperand(i);
+ uint64_t Size = TD.getTypeSize(GTI.getIndexedType()) & PtrSizeMask;
+ Constant *Scale = ConstantExpr::getCast(ConstantUInt::get(UIntPtrTy, Size),
+ SIntPtrTy);
+ if (Constant *OpC = dyn_cast<Constant>(Op)) {
+ if (!OpC->isNullValue()) {
+ OpC = ConstantExpr::getCast(OpC, SIntPtrTy);
+ Scale = ConstantExpr::getMul(OpC, Scale);
+ if (Constant *RC = dyn_cast<Constant>(Result))
+ Result = ConstantExpr::getAdd(RC, Scale);
+ else {
+ // Emit an add instruction.
+ Result = IC.InsertNewInstBefore(
+ BinaryOperator::createAdd(Result, Scale,
+ GEP->getName()+".offs"), I);
+ }
+ }
+ } else {
+ // Convert to correct type.
+ Op = IC.InsertNewInstBefore(new CastInst(Op, SIntPtrTy,
+ Op->getName()+".c"), I);
+ if (Size != 1)
+ // We'll let instcombine(mul) convert this to a shl if possible.
+ Op = IC.InsertNewInstBefore(BinaryOperator::createMul(Op, Scale,
+ GEP->getName()+".idx"), I);
+
+ // Emit an add instruction.
+ Result = IC.InsertNewInstBefore(BinaryOperator::createAdd(Op, Result,
+ GEP->getName()+".offs"), I);
+ }
+ }
+ return Result;
}
+/// FoldGEPSetCC - Fold comparisons between a GEP instruction and something
+/// else. At this point we know that the GEP is on the LHS of the comparison.
+Instruction *InstCombiner::FoldGEPSetCC(User *GEPLHS, Value *RHS,
+ Instruction::BinaryOps Cond,
+ Instruction &I) {
+ assert(dyn_castGetElementPtr(GEPLHS) && "LHS is not a getelementptr!");
+
+ if (CastInst *CI = dyn_cast<CastInst>(RHS))
+ if (isa<PointerType>(CI->getOperand(0)->getType()))
+ RHS = CI->getOperand(0);
+
+ Value *PtrBase = GEPLHS->getOperand(0);
+ if (PtrBase == RHS) {
+ // As an optimization, we don't actually have to compute the actual value of
+ // OFFSET if this is a seteq or setne comparison, just return whether each
+ // index is zero or not.
+ if (Cond == Instruction::SetEQ || Cond == Instruction::SetNE) {
+ Instruction *InVal = 0;
+ gep_type_iterator GTI = gep_type_begin(GEPLHS);
+ for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i, ++GTI) {
+ bool EmitIt = true;
+ if (Constant *C = dyn_cast<Constant>(GEPLHS->getOperand(i))) {
+ if (isa<UndefValue>(C)) // undef index -> undef.
+ return ReplaceInstUsesWith(I, UndefValue::get(I.getType()));
+ if (C->isNullValue())
+ EmitIt = false;
+ else if (TD->getTypeSize(GTI.getIndexedType()) == 0) {
+ EmitIt = false; // This is indexing into a zero sized array?
+ } else if (isa<ConstantInt>(C))
+ return ReplaceInstUsesWith(I, // No comparison is needed here.
+ ConstantBool::get(Cond == Instruction::SetNE));
+ }
+
+ if (EmitIt) {
+ Instruction *Comp =
+ new SetCondInst(Cond, GEPLHS->getOperand(i),
+ Constant::getNullValue(GEPLHS->getOperand(i)->getType()));
+ if (InVal == 0)
+ InVal = Comp;
+ else {
+ InVal = InsertNewInstBefore(InVal, I);
+ InsertNewInstBefore(Comp, I);
+ if (Cond == Instruction::SetNE) // True if any are unequal
+ InVal = BinaryOperator::createOr(InVal, Comp);
+ else // True if all are equal
+ InVal = BinaryOperator::createAnd(InVal, Comp);
+ }
+ }
+ }
+
+ if (InVal)
+ return InVal;
+ else
+ ReplaceInstUsesWith(I, // No comparison is needed here, all indexes = 0
+ ConstantBool::get(Cond == Instruction::SetEQ));
+ }
+
+ // Only lower this if the setcc is the only user of the GEP or if we expect
+ // the result to fold to a constant!
+ if (isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) {
+ // ((gep Ptr, OFFSET) cmp Ptr) ---> (OFFSET cmp 0).
+ Value *Offset = EmitGEPOffset(GEPLHS, I, *this);
+ return new SetCondInst(Cond, Offset,
+ Constant::getNullValue(Offset->getType()));
+ }
+ } else if (User *GEPRHS = dyn_castGetElementPtr(RHS)) {
+ if (PtrBase != GEPRHS->getOperand(0))
+ return 0;
+
+ // If one of the GEPs has all zero indices, recurse.
+ bool AllZeros = true;
+ for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i)
+ if (!isa<Constant>(GEPLHS->getOperand(i)) ||
+ !cast<Constant>(GEPLHS->getOperand(i))->isNullValue()) {
+ AllZeros = false;
+ break;
+ }
+ if (AllZeros)
+ return FoldGEPSetCC(GEPRHS, GEPLHS->getOperand(0),
+ SetCondInst::getSwappedCondition(Cond), I);
+
+ // If the other GEP has all zero indices, recurse.
+ AllZeros = true;
+ for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
+ if (!isa<Constant>(GEPRHS->getOperand(i)) ||
+ !cast<Constant>(GEPRHS->getOperand(i))->isNullValue()) {
+ AllZeros = false;
+ break;
+ }
+ if (AllZeros)
+ return FoldGEPSetCC(GEPLHS, GEPRHS->getOperand(0), Cond, I);
+
+ if (GEPLHS->getNumOperands() == GEPRHS->getNumOperands()) {
+ // If the GEPs only differ by one index, compare it.
+ unsigned NumDifferences = 0; // Keep track of # differences.
+ unsigned DiffOperand = 0; // The operand that differs.
+ for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
+ if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
+ if (GEPLHS->getOperand(i)->getType()->getPrimitiveSize() !=
+ GEPRHS->getOperand(i)->getType()->getPrimitiveSize()) {
+ // Irreconcilable differences.
+ NumDifferences = 2;
+ break;
+ } else {
+ if (NumDifferences++) break;
+ DiffOperand = i;
+ }
+ }
+
+ if (NumDifferences == 0) // SAME GEP?
+ return ReplaceInstUsesWith(I, // No comparison is needed here.
+ ConstantBool::get(Cond == Instruction::SetEQ));
+ else if (NumDifferences == 1) {
+ Value *LHSV = GEPLHS->getOperand(DiffOperand);
+ Value *RHSV = GEPRHS->getOperand(DiffOperand);
+ if (LHSV->getType() != RHSV->getType())
+ LHSV = InsertNewInstBefore(new CastInst(LHSV, RHSV->getType(),
+ LHSV->getName()+".c"), I);
+ return new SetCondInst(Cond, LHSV, RHSV);
+ }
+ }
+
+ // Only lower this if the setcc is the only user of the GEP or if we expect
+ // the result to fold to a constant!
+ if ((isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) &&
+ (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
+ // ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2) ---> (OFFSET1 cmp OFFSET2)
+ Value *L = EmitGEPOffset(GEPLHS, I, *this);
+ Value *R = EmitGEPOffset(GEPRHS, I, *this);
+ return new SetCondInst(Cond, L, R);
+ }
+ }
+ return 0;
+}
+
+
Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) {
bool Changed = SimplifyCommutative(I);
Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
if (Op0 == Op1)
return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I)));
- // setcc <global/alloca*>, 0 - Global/Stack value addresses are never null!
- if (isa<ConstantPointerNull>(Op1) &&
- (isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0)))
- return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I)));
+ if (isa<UndefValue>(Op1)) // X setcc undef -> undef
+ return ReplaceInstUsesWith(I, UndefValue::get(Type::BoolTy));
+ // setcc <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
+ // addresses never equal each other! We already know that Op0 != Op1.
+ if ((isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0) ||
+ isa<ConstantPointerNull>(Op0)) &&
+ (isa<GlobalValue>(Op1) || isa<AllocaInst>(Op1) ||
+ isa<ConstantPointerNull>(Op1)))
+ return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I)));
// setcc's with boolean values can always be turned into bitwise operations
if (Ty == Type::BoolTy) {
- // If this is <, >, or !=, we can change this into a simple xor instruction
- if (!isTrueWhenEqual(I))
- 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:
- //
- // seteq bool %A, %B -> ~(A^B)
- // setle bool %A, %B -> ~A | B
- // setge bool %A, %B -> A | ~B
- //
- if (I.getOpcode() == Instruction::SetEQ) { // seteq case
+ switch (I.getOpcode()) {
+ default: assert(0 && "Invalid setcc instruction!");
+ case Instruction::SetEQ: { // seteq bool %A, %B -> ~(A^B)
Instruction *Xor = BinaryOperator::createXor(Op0, Op1, I.getName()+"tmp");
InsertNewInstBefore(Xor, I);
return BinaryOperator::createNot(Xor);
}
+ case Instruction::SetNE:
+ return BinaryOperator::createXor(Op0, Op1);
- // Handle the setXe cases...
- assert(I.getOpcode() == Instruction::SetGE ||
- I.getOpcode() == Instruction::SetLE);
-
- if (I.getOpcode() == Instruction::SetGE)
+ case Instruction::SetGT:
+ std::swap(Op0, Op1); // Change setgt -> setlt
+ // FALL THROUGH
+ case Instruction::SetLT: { // setlt bool A, B -> ~X & Y
+ Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
+ InsertNewInstBefore(Not, I);
+ return BinaryOperator::createAnd(Not, Op1);
+ }
+ case Instruction::SetGE:
std::swap(Op0, Op1); // Change setge -> setle
-
- // Now we just have the SetLE case.
- Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
- InsertNewInstBefore(Not, I);
- return BinaryOperator::createOr(Not, Op1);
+ // FALL THROUGH
+ case Instruction::SetLE: { // setle bool %A, %B -> ~A | B
+ Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
+ InsertNewInstBefore(Not, I);
+ return BinaryOperator::createOr(Not, Op1);
+ }
+ }
}
// 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)) {
+ // Check to see if we are comparing against the minimum or maximum value...
+ if (CI->isMinValue()) {
+ if (I.getOpcode() == Instruction::SetLT) // A < MIN -> FALSE
+ return ReplaceInstUsesWith(I, ConstantBool::False);
+ if (I.getOpcode() == Instruction::SetGE) // A >= MIN -> TRUE
+ return ReplaceInstUsesWith(I, ConstantBool::True);
+ if (I.getOpcode() == Instruction::SetLE) // A <= MIN -> A == MIN
+ return BinaryOperator::createSetEQ(Op0, Op1);
+ if (I.getOpcode() == Instruction::SetGT) // A > MIN -> A != MIN
+ return BinaryOperator::createSetNE(Op0, Op1);
+
+ } else if (CI->isMaxValue()) {
+ if (I.getOpcode() == Instruction::SetGT) // A > MAX -> FALSE
+ return ReplaceInstUsesWith(I, ConstantBool::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::createSetEQ(Op0, Op1);
+ if (I.getOpcode() == Instruction::SetLT) // A < MAX -> A != MAX
+ 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::createSetEQ(Op0, SubOne(CI));
+ if (I.getOpcode() == Instruction::SetGE) // A >= MIN-1 -> A != MIN
+ return BinaryOperator::createSetNE(Op0, SubOne(CI));
+
+ } else if (isMaxValueMinusOne(CI)) {
+ if (I.getOpcode() == Instruction::SetGT) // A > MAX-1 -> A == MAX
+ return BinaryOperator::createSetEQ(Op0, AddOne(CI));
+ if (I.getOpcode() == Instruction::SetLE) // A <= MAX-1 -> A != MAX
+ return BinaryOperator::createSetNE(Op0, AddOne(CI));
+ }
+
+ // If we still have a setle or setge instruction, turn it into the
+ // appropriate setlt or setgt instruction. Since the border cases have
+ // already been handled above, this requires little checking.
+ //
+ if (I.getOpcode() == Instruction::SetLE)
+ return BinaryOperator::createSetLT(Op0, AddOne(CI));
+ if (I.getOpcode() == Instruction::SetGE)
+ return BinaryOperator::createSetGT(Op0, SubOne(CI));
+
if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
- if (LHSI->hasOneUse())
- switch (LHSI->getOpcode()) {
- case Instruction::And:
- if (isa<ConstantInt>(LHSI->getOperand(1))) {
+ switch (LHSI->getOpcode()) {
+ case Instruction::PHI:
+ if (Instruction *NV = FoldOpIntoPhi(I))
+ return NV;
+ break;
+ case Instruction::And:
+ if (LHSI->hasOneUse() && 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) {
+ Constant *NewCst;
+ if (Shift->getOpcode() == Instruction::Shl)
+ NewCst = ConstantExpr::getUShr(CI, ShAmt);
+ else
+ NewCst = ConstantExpr::getShl(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);
+ Constant *NewAndCST;
+ if (Shift->getOpcode() == Instruction::Shl)
+ NewAndCST = ConstantExpr::getUShr(AndCST, ShAmt);
+ else
+ NewAndCST = ConstantExpr::getShl(AndCST, ShAmt);
+ LHSI->setOperand(1, NewAndCST);
+ LHSI->setOperand(0, Shift->getOperand(0));
+ WorkList.push_back(Shift); // Shift is dead.
+ AddUsesToWorkList(I);
+ return &I;
+ }
+ }
+ }
+ }
+ break;
+
+ // (setcc (cast X to larger), CI)
+ case Instruction::Cast:
+ if (Instruction *R =
+ visitSetCondInstWithCastAndConstant(I,cast<CastInst>(LHSI),CI))
+ return R;
+ break;
- // 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.
- if (LHSI->getOperand(0)->hasOneUse())
- if (ShiftInst *Shift = dyn_cast<ShiftInst>(LHSI->getOperand(0)))
- if (ConstantUInt *ShAmt =
- dyn_cast<ConstantUInt>(Shift->getOperand(1))) {
- ConstantInt *AndCST = cast<ConstantInt>(LHSI->getOperand(1));
-
- // 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.
- const Type *Ty = Shift->getType();
- if (Shift->getOpcode() != Instruction::Shr ||
- Shift->getType()->isUnsigned() ||
- // To test for the bad case of the signed shr, see if any
- // of the bits shifted in could be tested after the mask.
- ConstantExpr::getAnd(ConstantExpr::getShl(ConstantInt::getAllOnesValue(Ty), ConstantUInt::get(Type::UByteTy, Ty->getPrimitiveSize()*8-ShAmt->getValue())), AndCST)->isNullValue()) {
- unsigned ShiftOp = Shift->getOpcode() == Instruction::Shl
- ? Instruction::Shr : Instruction::Shl;
- I.setOperand(1, ConstantExpr::get(ShiftOp, CI, ShAmt));
- LHSI->setOperand(1,ConstantExpr::get(ShiftOp,AndCST,ShAmt));
- LHSI->setOperand(0, Shift->getOperand(0));
- WorkList.push_back(Shift); // Shift is probably dead.
- AddUsesToWorkList(I);
- return &I;
- }
- }
+ case Instruction::Shl: // (setcc (shl X, ShAmt), CI)
+ if (ConstantUInt *ShAmt = dyn_cast<ConstantUInt>(LHSI->getOperand(1))) {
+ switch (I.getOpcode()) {
+ default: break;
+ case Instruction::SetEQ:
+ case Instruction::SetNE: {
+ // If we are comparing against bits always shifted out, the
+ // comparison cannot succeed.
+ Constant *Comp =
+ ConstantExpr::getShl(ConstantExpr::getShr(CI, ShAmt), ShAmt);
+ if (Comp != CI) {// Comparing against a bit that we know is zero.
+ bool IsSetNE = I.getOpcode() == Instruction::SetNE;
+ Constant *Cst = ConstantBool::get(IsSetNE);
+ return ReplaceInstUsesWith(I, Cst);
+ }
+
+ if (LHSI->hasOneUse()) {
+ // Otherwise strength reduce the shift into an and.
+ unsigned ShAmtVal = (unsigned)ShAmt->getValue();
+ unsigned TypeBits = CI->getType()->getPrimitiveSize()*8;
+ uint64_t Val = (1ULL << (TypeBits-ShAmtVal))-1;
+
+ Constant *Mask;
+ if (CI->getType()->isUnsigned()) {
+ Mask = ConstantUInt::get(CI->getType(), Val);
+ } else if (ShAmtVal != 0) {
+ Mask = ConstantSInt::get(CI->getType(), Val);
+ } else {
+ Mask = ConstantInt::getAllOnesValue(CI->getType());
+ }
+
+ Instruction *AndI =
+ BinaryOperator::createAnd(LHSI->getOperand(0),
+ Mask, LHSI->getName()+".mask");
+ Value *And = InsertNewInstBefore(AndI, I);
+ return new SetCondInst(I.getOpcode(), And,
+ ConstantExpr::getUShr(CI, ShAmt));
+ }
}
- 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;
+ }
+ break;
+
+ case Instruction::Shr: // (setcc (shr X, ShAmt), CI)
+ if (ConstantUInt *ShAmt = dyn_cast<ConstantUInt>(LHSI->getOperand(1))) {
+ switch (I.getOpcode()) {
+ default: break;
+ case Instruction::SetEQ:
+ case Instruction::SetNE: {
+ // If we are comparing against bits always shifted out, the
+ // comparison cannot succeed.
+ Constant *Comp =
+ ConstantExpr::getShr(ConstantExpr::getShl(CI, ShAmt), ShAmt);
+
+ if (Comp != CI) {// Comparing against a bit that we know is zero.
+ bool IsSetNE = I.getOpcode() == Instruction::SetNE;
+ Constant *Cst = ConstantBool::get(IsSetNE);
+ return ReplaceInstUsesWith(I, Cst);
+ }
+
+ if (LHSI->hasOneUse() || CI->isNullValue()) {
+ unsigned ShAmtVal = (unsigned)ShAmt->getValue();
+
+ // Otherwise strength reduce the shift into an and.
+ uint64_t Val = ~0ULL; // All ones.
+ Val <<= ShAmtVal; // Shift over to the right spot.
+
+ Constant *Mask;
+ if (CI->getType()->isUnsigned()) {
+ unsigned TypeBits = CI->getType()->getPrimitiveSize()*8;
+ Val &= (1ULL << TypeBits)-1;
+ Mask = ConstantUInt::get(CI->getType(), Val);
+ } else {
+ Mask = ConstantSInt::get(CI->getType(), Val);
+ }
+
+ Instruction *AndI =
+ BinaryOperator::createAnd(LHSI->getOperand(0),
+ Mask, LHSI->getName()+".mask");
+ Value *And = InsertNewInstBefore(AndI, I);
+ return new SetCondInst(I.getOpcode(), And,
+ ConstantExpr::getShl(CI, ShAmt));
+ }
+ break;
+ }
+ }
+ }
+ break;
+
+ case Instruction::Div:
+ // Fold: (div X, C1) op C2 -> range check
+ if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
+ // Fold this div into the comparison, producing a range check.
+ // Determine, based on the divide type, what the range is being
+ // checked. If there is an overflow on the low or high side, remember
+ // it, otherwise compute the range [low, hi) bounding the new value.
+ bool LoOverflow = false, HiOverflow = 0;
+ ConstantInt *LoBound = 0, *HiBound = 0;
+
+ ConstantInt *Prod;
+ bool ProdOV = MulWithOverflow(Prod, CI, DivRHS);
+
+ Instruction::BinaryOps Opcode = I.getOpcode();
+
+ if (DivRHS->isNullValue()) { // Don't hack on divide by zeros.
+ } else if (LHSI->getType()->isUnsigned()) { // udiv
+ LoBound = Prod;
+ LoOverflow = ProdOV;
+ HiOverflow = ProdOV || AddWithOverflow(HiBound, LoBound, DivRHS);
+ } else if (isPositive(DivRHS)) { // Divisor is > 0.
+ if (CI->isNullValue()) { // (X / pos) op 0
+ // Can't overflow.
+ LoBound = cast<ConstantInt>(ConstantExpr::getNeg(SubOne(DivRHS)));
+ HiBound = DivRHS;
+ } else if (isPositive(CI)) { // (X / pos) op pos
+ LoBound = Prod;
+ LoOverflow = ProdOV;
+ HiOverflow = ProdOV || AddWithOverflow(HiBound, Prod, DivRHS);
+ } else { // (X / pos) op neg
+ Constant *DivRHSH = ConstantExpr::getNeg(SubOne(DivRHS));
+ LoOverflow = AddWithOverflow(LoBound, Prod,
+ cast<ConstantInt>(DivRHSH));
+ HiBound = Prod;
+ HiOverflow = ProdOV;
+ }
+ } else { // Divisor is < 0.
+ if (CI->isNullValue()) { // (X / neg) op 0
+ LoBound = AddOne(DivRHS);
+ HiBound = cast<ConstantInt>(ConstantExpr::getNeg(DivRHS));
+ } else if (isPositive(CI)) { // (X / neg) op pos
+ HiOverflow = LoOverflow = ProdOV;
+ if (!LoOverflow)
+ LoOverflow = AddWithOverflow(LoBound, Prod, AddOne(DivRHS));
+ HiBound = AddOne(Prod);
+ } else { // (X / neg) op neg
+ LoBound = Prod;
+ LoOverflow = HiOverflow = ProdOV;
+ HiBound = cast<ConstantInt>(ConstantExpr::getSub(Prod, DivRHS));
+ }
+
+ // Dividing by a negate swaps the condition.
+ Opcode = SetCondInst::getSwappedCondition(Opcode);
+ }
+
+ if (LoBound) {
+ Value *X = LHSI->getOperand(0);
+ switch (Opcode) {
+ default: assert(0 && "Unhandled setcc opcode!");
+ case Instruction::SetEQ:
+ if (LoOverflow && HiOverflow)
+ return ReplaceInstUsesWith(I, ConstantBool::False);
+ else if (HiOverflow)
+ return new SetCondInst(Instruction::SetGE, X, LoBound);
+ else if (LoOverflow)
+ return new SetCondInst(Instruction::SetLT, X, HiBound);
+ else
+ return InsertRangeTest(X, LoBound, HiBound, true, I);
+ case Instruction::SetNE:
+ if (LoOverflow && HiOverflow)
+ return ReplaceInstUsesWith(I, ConstantBool::True);
+ else if (HiOverflow)
+ return new SetCondInst(Instruction::SetLT, X, LoBound);
+ else if (LoOverflow)
+ return new SetCondInst(Instruction::SetGE, X, HiBound);
+ else
+ return InsertRangeTest(X, LoBound, HiBound, false, I);
+ case Instruction::SetLT:
+ if (LoOverflow)
+ return ReplaceInstUsesWith(I, ConstantBool::False);
+ return new SetCondInst(Instruction::SetLT, X, LoBound);
+ case Instruction::SetGT:
+ if (HiOverflow)
+ return ReplaceInstUsesWith(I, ConstantBool::False);
+ return new SetCondInst(Instruction::SetGE, X, HiBound);
+ }
+ }
+ }
+ 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 (LHSI->hasOneUse()) {
if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1))) {
// Fold the known value into the constant operand.
Op1 = ConstantExpr::get(I.getOpcode(), C, CI);
LHSI->getOperand(1), CI,
I.getName()), I);
}
-
- if (Op1)
- return new SelectInst(LHSI->getOperand(0), Op1, Op2);
- break;
}
-
+
+ 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) {
case Instruction::Add:
// 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));
+ if (BO->hasOneUse())
+ 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.
// If 'X' is not signed, insert a cast now...
if (!BOC->getType()->isSigned()) {
const Type *DestTy = BOC->getType()->getSignedVersion();
- CastInst *NewCI = new CastInst(X,DestTy,X->getName()+".signed");
- InsertNewInstBefore(NewCI, I);
- X = NewCI;
+ X = InsertCastBefore(X, DestTy, I);
}
return new SetCondInst(isSetNE ? Instruction::SetLT :
Instruction::SetGE, X,
Constant::getNullValue(X->getType()));
}
+
+ // ((X & ~7) == 0) --> X < 8
+ if (CI->isNullValue() && isHighOnes(BOC)) {
+ Value *X = BO->getOperand(0);
+ Constant *NegX = ConstantExpr::getNeg(BOC);
+
+ // If 'X' is signed, insert a cast now.
+ if (NegX->getType()->isSigned()) {
+ const Type *DestTy = NegX->getType()->getUnsignedVersion();
+ X = InsertCastBefore(X, DestTy, I);
+ NegX = ConstantExpr::getCast(NegX, DestTy);
+ }
+
+ return new SetCondInst(isSetNE ? Instruction::SetGE :
+ Instruction::SetLT, X, NegX);
+ }
+
}
default: break;
}
}
}
}
-
- // Check to see if we are comparing against the minimum or maximum value...
- if (CI->isMinValue()) {
- if (I.getOpcode() == Instruction::SetLT) // A < MIN -> FALSE
- return ReplaceInstUsesWith(I, ConstantBool::False);
- if (I.getOpcode() == Instruction::SetGE) // A >= MIN -> TRUE
- return ReplaceInstUsesWith(I, ConstantBool::True);
- if (I.getOpcode() == Instruction::SetLE) // A <= MIN -> A == MIN
- return BinaryOperator::createSetEQ(Op0, Op1);
- if (I.getOpcode() == Instruction::SetGT) // A > MIN -> A != MIN
- return BinaryOperator::createSetNE(Op0, Op1);
-
- } else if (CI->isMaxValue()) {
- if (I.getOpcode() == Instruction::SetGT) // A > MAX -> FALSE
- return ReplaceInstUsesWith(I, ConstantBool::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::createSetEQ(Op0, Op1);
- if (I.getOpcode() == Instruction::SetLT) // A < MAX -> A != MAX
- 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::createSetEQ(Op0, SubOne(CI));
- if (I.getOpcode() == Instruction::SetGE) // A >= MIN-1 -> A != MIN
- return BinaryOperator::createSetNE(Op0, SubOne(CI));
-
- } else if (isMaxValueMinusOne(CI)) {
- if (I.getOpcode() == Instruction::SetGT) // A > MAX-1 -> A == MAX
- return BinaryOperator::createSetEQ(Op0, AddOne(CI));
- if (I.getOpcode() == Instruction::SetLE) // A <= MAX-1 -> A != MAX
- return BinaryOperator::createSetNE(Op0, AddOne(CI));
- }
-
- // If we still have a setle or setge instruction, turn it into the
- // appropriate setlt or setgt instruction. Since the border cases have
- // already been handled above, this requires little checking.
- //
- if (I.getOpcode() == Instruction::SetLE)
- return BinaryOperator::createSetLT(Op0, AddOne(CI));
- if (I.getOpcode() == Instruction::SetGE)
- return BinaryOperator::createSetGT(Op0, SubOne(CI));
}
+ // If we can optimize a 'setcc GEP, P' or 'setcc P, GEP', do so now.
+ if (User *GEP = dyn_castGetElementPtr(Op0))
+ if (Instruction *NI = FoldGEPSetCC(GEP, Op1, I.getOpcode(), I))
+ return NI;
+ if (User *GEP = dyn_castGetElementPtr(Op1))
+ if (Instruction *NI = FoldGEPSetCC(GEP, Op0,
+ SetCondInst::getSwappedCondition(I.getOpcode()), I))
+ return NI;
+
// Test to see if the operands of the setcc are casted versions of other
// values. If the cast can be stripped off both arguments, we do so now.
if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
return Changed ? &I : 0;
}
+// visitSetCondInstWithCastAndConstant - this method is part of the
+// visitSetCondInst method. It handles the situation where we have:
+// (setcc (cast X to larger), CI)
+// It tries to remove the cast and even the setcc if the CI value
+// and range of the cast allow it.
+Instruction *
+InstCombiner::visitSetCondInstWithCastAndConstant(BinaryOperator&I,
+ CastInst* LHSI,
+ ConstantInt* CI) {
+ const Type *SrcTy = LHSI->getOperand(0)->getType();
+ const Type *DestTy = LHSI->getType();
+ if (!SrcTy->isIntegral() || !DestTy->isIntegral())
+ return 0;
+
+ unsigned SrcBits = SrcTy->getPrimitiveSize()*8;
+ unsigned DestBits = DestTy->getPrimitiveSize()*8;
+ if (SrcTy == Type::BoolTy)
+ SrcBits = 1;
+ if (DestTy == Type::BoolTy)
+ DestBits = 1;
+ if (SrcBits < DestBits) {
+ // There are fewer bits in the source of the cast than in the result
+ // of the cast. Any other case doesn't matter because the constant
+ // value won't have changed due to sign extension.
+ Constant *NewCst = ConstantExpr::getCast(CI, SrcTy);
+ if (ConstantExpr::getCast(NewCst, DestTy) == CI) {
+ // The constant value operand of the setCC before and after a
+ // cast to the source type of the cast instruction is the same
+ // value, so we just replace with the same setcc opcode, but
+ // using the source value compared to the constant casted to the
+ // source type.
+ if (SrcTy->isSigned() && DestTy->isUnsigned()) {
+ CastInst* Cst = new CastInst(LHSI->getOperand(0),
+ SrcTy->getUnsignedVersion(),
+ LHSI->getName());
+ InsertNewInstBefore(Cst,I);
+ return new SetCondInst(I.getOpcode(), Cst,
+ ConstantExpr::getCast(CI,
+ SrcTy->getUnsignedVersion()));
+ }
+ return new SetCondInst(I.getOpcode(), LHSI->getOperand(0),NewCst);
+ }
+
+ // The constant value before and after a cast to the source type
+ // is different, so various cases are possible depending on the
+ // opcode and the signs of the types involved in the cast.
+ switch (I.getOpcode()) {
+ case Instruction::SetLT: {
+ return 0;
+ Constant* Max = ConstantIntegral::getMaxValue(SrcTy);
+ Max = ConstantExpr::getCast(Max, DestTy);
+ return ReplaceInstUsesWith(I, ConstantExpr::getSetLT(Max, CI));
+ }
+ case Instruction::SetGT: {
+ return 0; // FIXME! RENABLE. This breaks for (cast sbyte to uint) > 255
+ Constant* Min = ConstantIntegral::getMinValue(SrcTy);
+ Min = ConstantExpr::getCast(Min, DestTy);
+ return ReplaceInstUsesWith(I, ConstantExpr::getSetGT(Min, CI));
+ }
+ case Instruction::SetEQ:
+ // We're looking for equality, and we know the values are not
+ // equal so replace with constant False.
+ return ReplaceInstUsesWith(I, ConstantBool::False);
+ case Instruction::SetNE:
+ // We're testing for inequality, and we know the values are not
+ // equal so replace with constant True.
+ return ReplaceInstUsesWith(I, ConstantBool::True);
+ case Instruction::SetLE:
+ case Instruction::SetGE:
+ assert(0 && "SetLE and SetGE should be handled elsewhere");
+ default:
+ assert(0 && "unknown integer comparison");
+ }
+ }
+ return 0;
+}
Instruction *InstCombiner::visitShiftInst(ShiftInst &I) {
Op0 == Constant::getNullValue(Op0->getType()))
return ReplaceInstUsesWith(I, Op0);
+ if (isa<UndefValue>(Op0)) { // undef >>s X -> undef
+ if (!isLeftShift && I.getType()->isSigned())
+ return ReplaceInstUsesWith(I, Op0);
+ else // undef << X -> 0 AND undef >>u X -> 0
+ return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
+ }
+ if (isa<UndefValue>(Op1)) {
+ if (isLeftShift || I.getType()->isUnsigned())
+ return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
+ else
+ return ReplaceInstUsesWith(I, Op0); // X >>s undef -> X
+ }
+
// shr int -1, X = -1 (for any arithmetic shift rights of ~0)
if (!isLeftShift)
if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0))
// Try to fold constant and into select arguments.
if (isa<Constant>(Op0))
if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
- if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
+ if (Instruction *R = FoldOpIntoSelect(I, SI, this))
return R;
if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) {
// Try to fold constant and into select arguments.
if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
- if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
+ if (Instruction *R = FoldOpIntoSelect(I, SI, this))
return R;
+ if (isa<PHINode>(Op0))
+ if (Instruction *NV = FoldOpIntoPhi(I))
+ return NV;
+
+ if (Op0->hasOneUse()) {
+ // If this is a SHL of a sign-extending cast, see if we can turn the input
+ // into a zero extending cast (a simple strength reduction).
+ if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
+ const Type *SrcTy = CI->getOperand(0)->getType();
+ if (isLeftShift && SrcTy->isInteger() && SrcTy->isSigned() &&
+ SrcTy->getPrimitiveSize() < CI->getType()->getPrimitiveSize()) {
+ // We can change it to a zero extension if we are shifting out all of
+ // the sign extended bits. To check this, form a mask of all of the
+ // sign extend bits, then shift them left and see if we have anything
+ // left.
+ Constant *Mask = ConstantIntegral::getAllOnesValue(SrcTy); // 1111
+ Mask = ConstantExpr::getZeroExtend(Mask, CI->getType()); // 00001111
+ Mask = ConstantExpr::getNot(Mask); // 1's in the sign bits: 11110000
+ if (ConstantExpr::getShl(Mask, CUI)->isNullValue()) {
+ // If the shift is nuking all of the sign bits, change this to a
+ // zero extension cast. To do this, cast the cast input to
+ // unsigned, then to the requested size.
+ Value *CastOp = CI->getOperand(0);
+ Instruction *NC =
+ new CastInst(CastOp, CastOp->getType()->getUnsignedVersion(),
+ CI->getName()+".uns");
+ NC = InsertNewInstBefore(NC, I);
+ // Finally, insert a replacement for CI.
+ NC = new CastInst(NC, CI->getType(), CI->getName());
+ CI->setName("");
+ NC = InsertNewInstBefore(NC, I);
+ WorkList.push_back(CI); // Delete CI later.
+ I.setOperand(0, NC);
+ return &I; // The SHL operand was modified.
+ }
+ }
+ }
- // If the operand is an bitwise operator with a constant RHS, and the
- // shift is the only use, we can pull it out of the shift.
- if (Op0->hasOneUse())
+ // If the operand is an bitwise operator with a constant RHS, and the
+ // shift is the only use, we can pull it out of the shift.
if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0))
if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
bool isValid = true; // Valid only for And, Or, Xor
switch (Op0BO->getOpcode()) {
default: isValid = false; break; // Do not perform transform!
+ case Instruction::Add:
+ isValid = isLeftShift;
+ break;
case Instruction::Or:
case Instruction::Xor:
highBitSet = false;
NewRHS);
}
}
+ }
// If this is a shift of a shift, see if we can fold the two together...
if (ShiftInst *Op0SI = dyn_cast<ShiftInst>(Op0))
if (ConstantUInt *ShiftAmt1C =
dyn_cast<ConstantUInt>(Op0SI->getOperand(1))) {
- unsigned ShiftAmt1 = ShiftAmt1C->getValue();
- unsigned ShiftAmt2 = CUI->getValue();
+ unsigned ShiftAmt1 = (unsigned)ShiftAmt1C->getValue();
+ unsigned ShiftAmt2 = (unsigned)CUI->getValue();
// Check for (A << c1) << c2 and (A >> c1) >> c2
if (I.getOpcode() == Op0SI->getOpcode()) {
// 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;
// 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->trunc always ok, signext->zeroext never ok
+ 2, 5, 2, 4, // signext->zeroext never ok
// First cast is a zero ext
- 3, 5, 3, 3, // zeroext->trunc always ok
+ 3, 5, 3, 3,
};
unsigned Result = CastResult[FirstCast*4+SecondCast];
case 4:
return false; // Not possible to eliminate this here.
case 5:
- // Sign or zero extend followed by truncate is always ok
- return true;
+ // 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;
}
}
return false;
if (CI.getType() == Src->getType())
return ReplaceInstUsesWith(CI, Src);
+ if (isa<UndefValue>(Src)) // cast undef -> undef
+ return ReplaceInstUsesWith(CI, UndefValue::get(CI.getType()));
+
// If casting the result of another cast instruction, try to eliminate this
// one!
//
- if (CastInst *CSrc = dyn_cast<CastInst>(Src)) {
- if (isEliminableCastOfCast(CSrc->getOperand(0)->getType(),
- CSrc->getType(), CI.getType(), TD)) {
+ if (CastInst *CSrc = dyn_cast<CastInst>(Src)) { // A->B->C cast
+ Value *A = CSrc->getOperand(0);
+ if (isEliminableCastOfCast(A->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));
// If this is an A->B->A cast, and we are dealing with integral types, try
// to convert this into a logical 'and' instruction.
//
- if (CSrc->getOperand(0)->getType() == CI.getType() &&
+ if (A->getType()->isInteger() &&
CI.getType()->isInteger() && CSrc->getType()->isInteger() &&
- CI.getType()->isUnsigned() && CSrc->getType()->isUnsigned() &&
- CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()){
+ CSrc->getType()->isUnsigned() && // B->A cast must zero extend
+ CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()&&
+ A->getType()->getPrimitiveSize() == CI.getType()->getPrimitiveSize()) {
assert(CSrc->getType() != Type::ULongTy &&
"Cannot have type bigger than ulong!");
uint64_t AndValue = (1ULL << CSrc->getType()->getPrimitiveSize()*8)-1;
- Constant *AndOp = ConstantUInt::get(CI.getType(), AndValue);
- return BinaryOperator::createAnd(CSrc->getOperand(0), AndOp);
+ Constant *AndOp = ConstantUInt::get(A->getType()->getUnsignedVersion(),
+ AndValue);
+ AndOp = ConstantExpr::getCast(AndOp, A->getType());
+ Instruction *And = BinaryOperator::createAnd(CSrc->getOperand(0), AndOp);
+ if (And->getType() != CI.getType()) {
+ And->setName(CSrc->getName()+".mask");
+ InsertNewInstBefore(And, CI);
+ And = new CastInst(And, CI.getType());
+ }
+ return And;
}
}
-
+
// 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),
const Type *AllocElTy = AI->getAllocatedType();
const Type *CastElTy = PTy->getElementType();
if (AllocElTy->isSized() && CastElTy->isSized()) {
- unsigned AllocElTySize = TD->getTypeSize(AllocElTy);
- unsigned CastElTySize = TD->getTypeSize(CastElTy);
+ uint64_t AllocElTySize = TD->getTypeSize(AllocElTy);
+ uint64_t CastElTySize = TD->getTypeSize(CastElTy);
// If the allocation is for an even multiple of the cast type size
if (CastElTySize && (AllocElTySize % CastElTySize == 0)) {
}
}
+ if (SelectInst *SI = dyn_cast<SelectInst>(Src))
+ if (Instruction *NV = FoldOpIntoSelect(CI, SI, this))
+ return NV;
+ if (isa<PHINode>(Src))
+ if (Instruction *NV = FoldOpIntoPhi(CI))
+ return NV;
+
// If the source value is an instruction with only this use, we can attempt to
// propagate the cast into the instruction. Also, only handle integral types
// for now.
}
}
+/// FoldSelectOpOp - Here we have (select c, TI, FI), and we know that TI and FI
+/// have the same opcode and only one use each. Try to simplify this.
+Instruction *InstCombiner::FoldSelectOpOp(SelectInst &SI, Instruction *TI,
+ Instruction *FI) {
+ if (TI->getNumOperands() == 1) {
+ // If this is a non-volatile load or a cast from the same type,
+ // merge.
+ if (TI->getOpcode() == Instruction::Cast) {
+ if (TI->getOperand(0)->getType() != FI->getOperand(0)->getType())
+ return 0;
+ } else {
+ return 0; // unknown unary op.
+ }
+
+ // Fold this by inserting a select from the input values.
+ SelectInst *NewSI = new SelectInst(SI.getCondition(), TI->getOperand(0),
+ FI->getOperand(0), SI.getName()+".v");
+ InsertNewInstBefore(NewSI, SI);
+ return new CastInst(NewSI, TI->getType());
+ }
+
+ // Only handle binary operators here.
+ if (!isa<ShiftInst>(TI) && !isa<BinaryOperator>(TI))
+ return 0;
+
+ // Figure out if the operations have any operands in common.
+ Value *MatchOp, *OtherOpT, *OtherOpF;
+ bool MatchIsOpZero;
+ if (TI->getOperand(0) == FI->getOperand(0)) {
+ MatchOp = TI->getOperand(0);
+ OtherOpT = TI->getOperand(1);
+ OtherOpF = FI->getOperand(1);
+ MatchIsOpZero = true;
+ } else if (TI->getOperand(1) == FI->getOperand(1)) {
+ MatchOp = TI->getOperand(1);
+ OtherOpT = TI->getOperand(0);
+ OtherOpF = FI->getOperand(0);
+ MatchIsOpZero = false;
+ } else if (!TI->isCommutative()) {
+ return 0;
+ } else if (TI->getOperand(0) == FI->getOperand(1)) {
+ MatchOp = TI->getOperand(0);
+ OtherOpT = TI->getOperand(1);
+ OtherOpF = FI->getOperand(0);
+ MatchIsOpZero = true;
+ } else if (TI->getOperand(1) == FI->getOperand(0)) {
+ MatchOp = TI->getOperand(1);
+ OtherOpT = TI->getOperand(0);
+ OtherOpF = FI->getOperand(1);
+ MatchIsOpZero = true;
+ } else {
+ return 0;
+ }
+
+ // If we reach here, they do have operations in common.
+ SelectInst *NewSI = new SelectInst(SI.getCondition(), OtherOpT,
+ OtherOpF, SI.getName()+".v");
+ InsertNewInstBefore(NewSI, SI);
+
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TI)) {
+ if (MatchIsOpZero)
+ return BinaryOperator::create(BO->getOpcode(), MatchOp, NewSI);
+ else
+ return BinaryOperator::create(BO->getOpcode(), NewSI, MatchOp);
+ } else {
+ if (MatchIsOpZero)
+ return new ShiftInst(cast<ShiftInst>(TI)->getOpcode(), MatchOp, NewSI);
+ else
+ return new ShiftInst(cast<ShiftInst>(TI)->getOpcode(), NewSI, MatchOp);
+ }
+}
+
Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
Value *CondVal = SI.getCondition();
Value *TrueVal = SI.getTrueValue();
if (TrueVal == FalseVal)
return ReplaceInstUsesWith(SI, TrueVal);
+ if (isa<UndefValue>(TrueVal)) // select C, undef, X -> X
+ return ReplaceInstUsesWith(SI, FalseVal);
+ if (isa<UndefValue>(FalseVal)) // select C, X, undef -> X
+ return ReplaceInstUsesWith(SI, TrueVal);
+ if (isa<UndefValue>(CondVal)) { // select undef, X, Y -> X or Y
+ if (isa<Constant>(TrueVal))
+ return ReplaceInstUsesWith(SI, TrueVal);
+ else
+ return ReplaceInstUsesWith(SI, FalseVal);
+ }
+
if (SI.getType() == Type::BoolTy)
if (ConstantBool *C = dyn_cast<ConstantBool>(TrueVal)) {
if (C == ConstantBool::True) {
}
}
+ if (Instruction *TI = dyn_cast<Instruction>(TrueVal))
+ if (Instruction *FI = dyn_cast<Instruction>(FalseVal))
+ if (TI->hasOneUse() && FI->hasOneUse()) {
+ bool isInverse = false;
+ Instruction *AddOp = 0, *SubOp = 0;
+
+ // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
+ if (TI->getOpcode() == FI->getOpcode())
+ if (Instruction *IV = FoldSelectOpOp(SI, TI, FI))
+ return IV;
+
+ // Turn select C, (X+Y), (X-Y) --> (X+(select C, Y, (-Y))). This is
+ // even legal for FP.
+ if (TI->getOpcode() == Instruction::Sub &&
+ FI->getOpcode() == Instruction::Add) {
+ AddOp = FI; SubOp = TI;
+ } else if (FI->getOpcode() == Instruction::Sub &&
+ TI->getOpcode() == Instruction::Add) {
+ AddOp = TI; SubOp = FI;
+ }
+
+ if (AddOp) {
+ Value *OtherAddOp = 0;
+ if (SubOp->getOperand(0) == AddOp->getOperand(0)) {
+ OtherAddOp = AddOp->getOperand(1);
+ } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) {
+ OtherAddOp = AddOp->getOperand(0);
+ }
+
+ if (OtherAddOp) {
+ // So at this point we know we have:
+ // select C, (add X, Y), (sub X, ?)
+ // We can do the transform profitably if either 'Y' = '?' or '?' is
+ // a constant.
+ if (SubOp->getOperand(1) == AddOp ||
+ isa<Constant>(SubOp->getOperand(1))) {
+ Value *NegVal;
+ if (Constant *C = dyn_cast<Constant>(SubOp->getOperand(1))) {
+ NegVal = ConstantExpr::getNeg(C);
+ } else {
+ NegVal = InsertNewInstBefore(
+ BinaryOperator::createNeg(SubOp->getOperand(1)), SI);
+ }
+
+ Value *NewTrueOp = OtherAddOp;
+ Value *NewFalseOp = NegVal;
+ if (AddOp != TI)
+ std::swap(NewTrueOp, NewFalseOp);
+ Instruction *NewSel =
+ new SelectInst(CondVal, NewTrueOp,NewFalseOp,SI.getName()+".p");
+
+ NewSel = InsertNewInstBefore(NewSel, SI);
+ return BinaryOperator::createAdd(SubOp->getOperand(0), NewSel);
+ }
+ }
+ }
+ }
+
// See if we can fold the select into one of our operands.
if (SI.getType()->isInteger()) {
// See the comment above GetSelectFoldableOperands for a description of the
}
}
}
-
+
if (Instruction *FVI = dyn_cast<Instruction>(FalseVal))
if (FVI->hasOneUse() && FVI->getNumOperands() == 2 &&
!isa<Constant>(TrueVal))
Instruction *InstCombiner::visitCallInst(CallInst &CI) {
// Intrinsics cannot occur in an invoke, so handle them here instead of in
// visitCallSite.
- if (Function *F = CI.getCalledFunction())
- switch (F->getIntrinsicID()) {
- case Intrinsic::memmove:
- case Intrinsic::memcpy:
- case Intrinsic::memset:
- // memmove/cpy/set of zero bytes is a noop.
- if (Constant *NumBytes = dyn_cast<Constant>(CI.getOperand(3))) {
- if (NumBytes->isNullValue())
- return EraseInstFromFunction(CI);
- }
- break;
- default:
- break;
+ if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(&CI)) {
+ bool Changed = false;
+
+ // memmove/cpy/set of zero bytes is a noop.
+ if (Constant *NumBytes = dyn_cast<Constant>(MI->getLength())) {
+ if (NumBytes->isNullValue()) return EraseInstFromFunction(CI);
+
+ // FIXME: Increase alignment here.
+
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(NumBytes))
+ if (CI->getRawValue() == 1) {
+ // Replace the instruction with just byte operations. We would
+ // transform other cases to loads/stores, but we don't know if
+ // alignment is sufficient.
+ }
}
+ // If we have a memmove and the source operation is a constant global,
+ // then the source and dest pointers can't alias, so we can change this
+ // into a call to memcpy.
+ if (MemMoveInst *MMI = dyn_cast<MemMoveInst>(MI))
+ if (GlobalVariable *GVSrc = dyn_cast<GlobalVariable>(MMI->getSource()))
+ if (GVSrc->isConstant()) {
+ Module *M = CI.getParent()->getParent()->getParent();
+ Function *MemCpy = M->getOrInsertFunction("llvm.memcpy",
+ CI.getCalledFunction()->getFunctionType());
+ CI.setOperand(0, MemCpy);
+ Changed = true;
+ }
+
+ if (Changed) return &CI;
+ } else if (DbgStopPointInst *SPI = dyn_cast<DbgStopPointInst>(&CI)) {
+ // If this stoppoint is at the same source location as the previous
+ // stoppoint in the chain, it is not needed.
+ if (DbgStopPointInst *PrevSPI =
+ dyn_cast<DbgStopPointInst>(SPI->getChain()))
+ if (SPI->getLineNo() == PrevSPI->getLineNo() &&
+ SPI->getColNo() == PrevSPI->getColNo()) {
+ SPI->replaceAllUsesWith(PrevSPI);
+ return EraseInstFromFunction(CI);
+ }
+ }
+
return visitCallSite(&CI);
}
if (transformConstExprCastCall(CS)) return 0;
Value *Callee = CS.getCalledValue();
+
+ if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
+ // This instruction is not reachable, just remove it. We insert a store to
+ // undef so that we know that this code is not reachable, despite the fact
+ // that we can't modify the CFG here.
+ new StoreInst(ConstantBool::True,
+ UndefValue::get(PointerType::get(Type::BoolTy)),
+ CS.getInstruction());
+
+ if (!CS.getInstruction()->use_empty())
+ CS.getInstruction()->
+ replaceAllUsesWith(UndefValue::get(CS.getInstruction()->getType()));
+
+ if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) {
+ // Don't break the CFG, insert a dummy cond branch.
+ new BranchInst(II->getNormalDest(), II->getUnwindDest(),
+ ConstantBool::True, II);
+ }
+ return EraseInstFromFunction(*CS.getInstruction());
+ }
+
const PointerType *PTy = cast<PointerType>(Callee->getType());
const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
if (FTy->isVarArg()) {
}
AddUsersToWorkList(*Caller);
} else {
- NV = Constant::getNullValue(Caller->getType());
+ NV = UndefValue::get(Caller->getType());
}
}
}
+// FoldPHIArgOpIntoPHI - If all operands to a PHI node are the same "unary"
+// operator and they all are only used by the PHI, PHI together their
+// inputs, and do the operation once, to the result of the PHI.
+Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) {
+ Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
+
+ // Scan the instruction, looking for input operations that can be folded away.
+ // If all input operands to the phi are the same instruction (e.g. a cast from
+ // the same type or "+42") we can pull the operation through the PHI, reducing
+ // code size and simplifying code.
+ Constant *ConstantOp = 0;
+ const Type *CastSrcTy = 0;
+ if (isa<CastInst>(FirstInst)) {
+ CastSrcTy = FirstInst->getOperand(0)->getType();
+ } else if (isa<BinaryOperator>(FirstInst) || isa<ShiftInst>(FirstInst)) {
+ // Can fold binop or shift if the RHS is a constant.
+ ConstantOp = dyn_cast<Constant>(FirstInst->getOperand(1));
+ if (ConstantOp == 0) return 0;
+ } else {
+ return 0; // Cannot fold this operation.
+ }
+
+ // Check to see if all arguments are the same operation.
+ for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
+ if (!isa<Instruction>(PN.getIncomingValue(i))) return 0;
+ Instruction *I = cast<Instruction>(PN.getIncomingValue(i));
+ if (!I->hasOneUse() || I->getOpcode() != FirstInst->getOpcode())
+ return 0;
+ if (CastSrcTy) {
+ if (I->getOperand(0)->getType() != CastSrcTy)
+ return 0; // Cast operation must match.
+ } else if (I->getOperand(1) != ConstantOp) {
+ return 0;
+ }
+ }
+
+ // Okay, they are all the same operation. Create a new PHI node of the
+ // correct type, and PHI together all of the LHS's of the instructions.
+ PHINode *NewPN = new PHINode(FirstInst->getOperand(0)->getType(),
+ PN.getName()+".in");
+ NewPN->reserveOperandSpace(PN.getNumOperands()/2);
+
+ Value *InVal = FirstInst->getOperand(0);
+ NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
+
+ // Add all operands to the new PHI.
+ for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
+ Value *NewInVal = cast<Instruction>(PN.getIncomingValue(i))->getOperand(0);
+ if (NewInVal != InVal)
+ InVal = 0;
+ NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
+ }
+
+ Value *PhiVal;
+ if (InVal) {
+ // The new PHI unions all of the same values together. This is really
+ // common, so we handle it intelligently here for compile-time speed.
+ PhiVal = InVal;
+ delete NewPN;
+ } else {
+ InsertNewInstBefore(NewPN, PN);
+ PhiVal = NewPN;
+ }
+
+ // Insert and return the new operation.
+ if (isa<CastInst>(FirstInst))
+ return new CastInst(PhiVal, PN.getType());
+ else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(FirstInst))
+ return BinaryOperator::create(BinOp->getOpcode(), PhiVal, ConstantOp);
+ else
+ return new ShiftInst(cast<ShiftInst>(FirstInst)->getOpcode(),
+ PhiVal, ConstantOp);
+}
+
+/// DeadPHICycle - Return true if this PHI node is only used by a PHI node cycle
+/// that is dead.
+static bool DeadPHICycle(PHINode *PN, std::set<PHINode*> &PotentiallyDeadPHIs) {
+ if (PN->use_empty()) return true;
+ if (!PN->hasOneUse()) return false;
+
+ // Remember this node, and if we find the cycle, return.
+ if (!PotentiallyDeadPHIs.insert(PN).second)
+ return true;
+
+ if (PHINode *PU = dyn_cast<PHINode>(PN->use_back()))
+ return DeadPHICycle(PU, PotentiallyDeadPHIs);
+
+ return false;
+}
// PHINode simplification
//
Instruction *InstCombiner::visitPHINode(PHINode &PN) {
- if (Value *V = hasConstantValue(&PN))
- return ReplaceInstUsesWith(PN, V);
+ if (Value *V = hasConstantValue(&PN)) {
+ // If V is an instruction, we have to be certain that it dominates PN.
+ // However, because we don't have dom info, we can't do a perfect job.
+ if (Instruction *I = dyn_cast<Instruction>(V)) {
+ // We know that the instruction dominates the PHI if there are no undef
+ // values coming in.
+ if (I->getParent() != &I->getParent()->getParent()->front() ||
+ isa<InvokeInst>(I))
+ for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
+ if (isa<UndefValue>(PN.getIncomingValue(i))) {
+ V = 0;
+ break;
+ }
+ }
+
+ if (V)
+ return ReplaceInstUsesWith(PN, V);
+ }
// If the only user of this instruction is a cast instruction, and all of the
// incoming values are constants, change this PHI to merge together the casted
return &PN; // PN is now dead!
}
}
+
+ // If all PHI operands are the same operation, pull them through the PHI,
+ // reducing code size.
+ if (isa<Instruction>(PN.getIncomingValue(0)) &&
+ PN.getIncomingValue(0)->hasOneUse())
+ if (Instruction *Result = FoldPHIArgOpIntoPHI(PN))
+ return Result;
+
+ // If this is a trivial cycle in the PHI node graph, remove it. Basically, if
+ // this PHI only has a single use (a PHI), and if that PHI only has one use (a
+ // PHI)... break the cycle.
+ if (PN.hasOneUse())
+ if (PHINode *PU = dyn_cast<PHINode>(PN.use_back())) {
+ std::set<PHINode*> PotentiallyDeadPHIs;
+ PotentiallyDeadPHIs.insert(&PN);
+ if (DeadPHICycle(PU, PotentiallyDeadPHIs))
+ return ReplaceInstUsesWith(PN, UndefValue::get(PN.getType()));
+ }
+
return 0;
}
InstCombiner *IC) {
unsigned PS = IC->getTargetData().getPointerSize();
const Type *VTy = V->getType();
- Instruction *Cast;
if (!VTy->isSigned() && VTy->getPrimitiveSize() < PS)
// We must insert a cast to ensure we sign-extend.
V = IC->InsertNewInstBefore(new CastInst(V, VTy->getSignedVersion(),
if (GEP.getNumOperands() == 1)
return ReplaceInstUsesWith(GEP, PtrOp);
+ if (isa<UndefValue>(GEP.getOperand(0)))
+ return ReplaceInstUsesWith(GEP, UndefValue::get(GEP.getType()));
+
bool HasZeroPointerIndex = false;
if (Constant *C = dyn_cast<Constant>(GEP.getOperand(1)))
HasZeroPointerIndex = C->isNullValue();
// getelementptr instructions into a single instruction.
//
std::vector<Value*> SrcGEPOperands;
- if (GetElementPtrInst *Src = dyn_cast<GetElementPtrInst>(PtrOp)) {
+ if (User *Src = dyn_castGetElementPtr(PtrOp))
SrcGEPOperands.assign(Src->op_begin(), Src->op_end());
- } 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
GO1 = ConstantExpr::getCast(GO1C, SO1->getType());
} else {
unsigned PS = TD->getPointerSize();
- Instruction *Cast;
if (SO1->getType()->getPrimitiveSize() == PS) {
// Convert GO1 to SO1's type.
GO1 = InsertSignExtendToPtrTy(GO1, SO1->getType(), &GEP, this);
GEP.setOperand(0, X);
return &GEP;
}
+ } else if (GEP.getNumOperands() == 2 &&
+ isa<PointerType>(CE->getOperand(0)->getType())) {
+ // Transform things like:
+ // %t = getelementptr ubyte* cast ([2 x sbyte]* %str to ubyte*), uint %V
+ // into: %t1 = getelementptr [2 x sbyte*]* %str, int 0, uint %V; cast
+ Constant *X = CE->getOperand(0);
+ const Type *SrcElTy = cast<PointerType>(X->getType())->getElementType();
+ const Type *ResElTy =cast<PointerType>(CE->getType())->getElementType();
+ if (isa<ArrayType>(SrcElTy) &&
+ TD->getTypeSize(cast<ArrayType>(SrcElTy)->getElementType()) ==
+ TD->getTypeSize(ResElTy)) {
+ Value *V = InsertNewInstBefore(
+ new GetElementPtrInst(X, Constant::getNullValue(Type::IntTy),
+ GEP.getOperand(1), GEP.getName()), GEP);
+ return new CastInst(V, GEP.getType());
+ }
}
}
}
// Now make everything use the getelementptr instead of the original
// allocation.
return ReplaceInstUsesWith(AI, V);
+ } else if (isa<UndefValue>(AI.getArraySize())) {
+ return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
}
// If alloca'ing a zero byte object, replace the alloca with a null pointer.
return &FI;
}
+ // free undef -> unreachable.
+ if (isa<UndefValue>(Op)) {
+ // Insert a new store to null because we cannot modify the CFG here.
+ new StoreInst(ConstantBool::True,
+ UndefValue::get(PointerType::get(Type::BoolTy)), &FI);
+ return EraseInstFromFunction(FI);
+ }
+
// If we have 'free null' delete the instruction. This can happen in stl code
// when lots of inlining happens.
if (isa<ConstantPointerNull>(Op))
ConstantUInt *CU = cast<ConstantUInt>(I.getOperand());
assert(CU->getValue() < STy->getNumElements() &&
"Struct index out of range!");
+ unsigned El = (unsigned)CU->getValue();
if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
- C = cast<Constant>(CS->getValues()[CU->getValue()]);
+ C = CS->getOperand(El);
} else if (isa<ConstantAggregateZero>(C)) {
- C = Constant::getNullValue(STy->getElementType(CU->getValue()));
+ C = Constant::getNullValue(STy->getElementType(El));
+ } else if (isa<UndefValue>(C)) {
+ C = UndefValue::get(STy->getElementType(El));
} else {
return 0;
}
const ArrayType *ATy = cast<ArrayType>(*I);
if ((uint64_t)CI->getRawValue() >= ATy->getNumElements()) return 0;
if (ConstantArray *CA = dyn_cast<ConstantArray>(C))
- C = cast<Constant>(CA->getValues()[CI->getRawValue()]);
+ C = CA->getOperand((unsigned)CI->getRawValue());
else if (isa<ConstantAggregateZero>(C))
C = Constant::getNullValue(ATy->getElementType());
+ else if (isa<UndefValue>(C))
+ C = UndefValue::get(ATy->getElementType());
else
return 0;
} else {
static Instruction *InstCombineLoadCast(InstCombiner &IC, LoadInst &LI) {
User *CI = cast<User>(LI.getOperand(0));
+ Value *CastOp = CI->getOperand(0);
const Type *DestPTy = cast<PointerType>(CI->getType())->getElementType();
- if (const PointerType *SrcTy =
- dyn_cast<PointerType>(CI->getOperand(0)->getType())) {
+ if (const PointerType *SrcTy = dyn_cast<PointerType>(CastOp->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());
+
+ if (DestPTy->isInteger() || isa<PointerType>(DestPTy)) {
+ // If the source is an array, the code below will not succeed. Check to
+ // see if a trivial 'gep P, 0, 0' will help matters. Only do this for
+ // constants.
+ if (const ArrayType *ASrcTy = dyn_cast<ArrayType>(SrcPTy))
+ if (Constant *CSrc = dyn_cast<Constant>(CastOp))
+ if (ASrcTy->getNumElements() != 0) {
+ std::vector<Value*> Idxs(2, Constant::getNullValue(Type::IntTy));
+ CastOp = ConstantExpr::getGetElementPtr(CSrc, Idxs);
+ SrcTy = cast<PointerType>(CastOp->getType());
+ SrcPTy = SrcTy->getElementType();
+ }
+
+ if ((SrcPTy->isInteger() || isa<PointerType>(SrcPTy)) &&
+ IC.getTargetData().getTypeSize(SrcPTy) ==
+ IC.getTargetData().getTypeSize(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(CastOp,
+ CI->getName(),
+ LI.isVolatile()),LI);
+ // Now cast the result of the load.
+ return new CastInst(NewLoad, LI.getType());
+ }
}
}
return 0;
}
+/// isSafeToLoadUnconditionally - Return true if we know that executing a load
+/// from this value cannot trap. If it is not obviously safe to load from the
+/// specified pointer, we do a quick local scan of the basic block containing
+/// ScanFrom, to determine if the address is already accessed.
+static bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom) {
+ // If it is an alloca or global variable, it is always safe to load from.
+ if (isa<AllocaInst>(V) || isa<GlobalVariable>(V)) return true;
+
+ // Otherwise, be a little bit agressive by scanning the local block where we
+ // want to check to see if the pointer is already being loaded or stored
+ // from/to. If so, the previous load or store would have already trapped,
+ // so there is no harm doing an extra load (also, CSE will later eliminate
+ // the load entirely).
+ BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin();
+
+ while (BBI != E) {
+ --BBI;
+
+ if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
+ if (LI->getOperand(0) == V) return true;
+ } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
+ if (SI->getOperand(1) == V) return true;
+
+ }
+ return false;
+}
+
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()));
- // Instcombine load (constant global) into the value loaded...
- if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Op))
- if (GV->isConstant() && !GV->isExternal())
- return ReplaceInstUsesWith(LI, GV->getInitializer());
-
- // Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded...
- if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op))
- 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;
+ if (Constant *C = dyn_cast<Constant>(Op)) {
+ if ((C->isNullValue() || isa<UndefValue>(C)) &&
+ !LI.isVolatile()) { // load null/undef -> undef
+ // Insert a new store to null instruction before the load to indicate that
+ // this code is not reachable. We do this instead of inserting an
+ // unreachable instruction directly because we cannot modify the CFG.
+ new StoreInst(UndefValue::get(LI.getType()), C, &LI);
+ return ReplaceInstUsesWith(LI, UndefValue::get(LI.getType()));
}
+ // Instcombine load (constant global) into the value loaded.
+ if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Op))
+ if (GV->isConstant() && !GV->isExternal())
+ return ReplaceInstUsesWith(LI, GV->getInitializer());
+
+ // Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded.
+ if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op))
+ 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))
if (Instruction *Res = InstCombineLoadCast(*this, LI))
return Res;
+ if (!LI.isVolatile() && Op->hasOneUse()) {
+ // Change select and PHI nodes to select values instead of addresses: this
+ // helps alias analysis out a lot, allows many others simplifications, and
+ // exposes redundancy in the code.
+ //
+ // Note that we cannot do the transformation unless we know that the
+ // introduced loads cannot trap! Something like this is valid as long as
+ // the condition is always false: load (select bool %C, int* null, int* %G),
+ // but it would not be valid if we transformed it to load from null
+ // unconditionally.
+ //
+ if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
+ // load (select (Cond, &V1, &V2)) --> select(Cond, load &V1, load &V2).
+ if (isSafeToLoadUnconditionally(SI->getOperand(1), SI) &&
+ isSafeToLoadUnconditionally(SI->getOperand(2), SI)) {
+ Value *V1 = InsertNewInstBefore(new LoadInst(SI->getOperand(1),
+ SI->getOperand(1)->getName()+".val"), LI);
+ Value *V2 = InsertNewInstBefore(new LoadInst(SI->getOperand(2),
+ SI->getOperand(2)->getName()+".val"), LI);
+ return new SelectInst(SI->getCondition(), V1, V2);
+ }
+
+ // load (select (cond, null, P)) -> load P
+ if (Constant *C = dyn_cast<Constant>(SI->getOperand(1)))
+ if (C->isNullValue()) {
+ LI.setOperand(0, SI->getOperand(2));
+ return &LI;
+ }
+
+ // load (select (cond, P, null)) -> load P
+ if (Constant *C = dyn_cast<Constant>(SI->getOperand(2)))
+ if (C->isNullValue()) {
+ LI.setOperand(0, SI->getOperand(1));
+ return &LI;
+ }
+
+ } else if (PHINode *PN = dyn_cast<PHINode>(Op)) {
+ // load (phi (&V1, &V2, &V3)) --> phi(load &V1, load &V2, load &V3)
+ bool Safe = PN->getParent() == LI.getParent();
+
+ // Scan all of the instructions between the PHI and the load to make
+ // sure there are no instructions that might possibly alter the value
+ // loaded from the PHI.
+ if (Safe) {
+ BasicBlock::iterator I = &LI;
+ for (--I; !isa<PHINode>(I); --I)
+ if (isa<StoreInst>(I) || isa<CallInst>(I)) {
+ Safe = false;
+ break;
+ }
+ }
+
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e && Safe; ++i)
+ if (!isSafeToLoadUnconditionally(PN->getIncomingValue(i),
+ PN->getIncomingBlock(i)->getTerminator()))
+ Safe = false;
+
+ if (Safe) {
+ // Create the PHI.
+ PHINode *NewPN = new PHINode(LI.getType(), PN->getName());
+ InsertNewInstBefore(NewPN, *PN);
+ std::map<BasicBlock*,Value*> LoadMap; // Don't insert duplicate loads
+
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+ BasicBlock *BB = PN->getIncomingBlock(i);
+ Value *&TheLoad = LoadMap[BB];
+ if (TheLoad == 0) {
+ Value *InVal = PN->getIncomingValue(i);
+ TheLoad = InsertNewInstBefore(new LoadInst(InVal,
+ InVal->getName()+".val"),
+ *BB->getTerminator());
+ }
+ NewPN->addIncoming(TheLoad, BB);
+ }
+ return ReplaceInstUsesWith(LI, NewPN);
+ }
+ }
+ }
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;
}
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)),
+ SI.setOperand(i,ConstantExpr::getSub(cast<Constant>(SI.getOperand(i)),
AddRHS));
SI.setOperand(0, I->getOperand(0));
WorkList.push_back(I);
WorkList.end());
}
+
+/// TryToSinkInstruction - Try to move the specified instruction from its
+/// current block into the beginning of DestBlock, which can only happen if it's
+/// safe to move the instruction past all of the instructions between it and the
+/// end of its block.
+static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
+ assert(I->hasOneUse() && "Invariants didn't hold!");
+
+ // Cannot move control-flow-involving instructions.
+ if (isa<PHINode>(I) || isa<InvokeInst>(I) || isa<CallInst>(I)) return false;
+
+ // Do not sink alloca instructions out of the entry block.
+ if (isa<AllocaInst>(I) && I->getParent() == &DestBlock->getParent()->front())
+ return false;
+
+ // We can only sink load instructions if there is nothing between the load and
+ // the end of block that could change the value.
+ if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
+ if (LI->isVolatile()) return false; // Don't sink volatile loads.
+
+ for (BasicBlock::iterator Scan = LI, E = LI->getParent()->end();
+ Scan != E; ++Scan)
+ if (Scan->mayWriteToMemory())
+ return false;
+ }
+
+ BasicBlock::iterator InsertPos = DestBlock->begin();
+ while (isa<PHINode>(InsertPos)) ++InsertPos;
+
+ BasicBlock *SrcBlock = I->getParent();
+ DestBlock->getInstList().splice(InsertPos, SrcBlock->getInstList(), I);
+ ++NumSunkInst;
+ return true;
+}
+
bool InstCombiner::runOnFunction(Function &F) {
bool Changed = false;
TD = &getAnalysis<TargetData>();
AddUsesToWorkList(*I);
++NumDeadInst;
- I->getParent()->getInstList().erase(I);
+ DEBUG(std::cerr << "IC: DCE: " << *I);
+
+ I->eraseFromParent();
removeFromWorkList(I);
continue;
}
// Instruction isn't dead, see if we can constant propagate it...
if (Constant *C = ConstantFoldInstruction(I)) {
+ Value* Ptr = I->getOperand(0);
+ if (isa<GetElementPtrInst>(I) &&
+ cast<Constant>(Ptr)->isNullValue() &&
+ !isa<ConstantPointerNull>(C) &&
+ cast<PointerType>(Ptr->getType())->getElementType()->isSized()) {
+ // If this is a constant expr gep that is effectively computing an
+ // "offsetof", fold it into 'cast int X to T*' instead of 'gep 0, 0, 12'
+ bool isFoldableGEP = true;
+ for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i)
+ if (!isa<ConstantInt>(I->getOperand(i)))
+ isFoldableGEP = false;
+ if (isFoldableGEP) {
+ uint64_t Offset = TD->getIndexedOffset(Ptr->getType(),
+ std::vector<Value*>(I->op_begin()+1, I->op_end()));
+ C = ConstantUInt::get(Type::ULongTy, Offset);
+ C = ConstantExpr::getCast(C, TD->getIntPtrType());
+ C = ConstantExpr::getCast(C, I->getType());
+ }
+ }
+
+ DEBUG(std::cerr << "IC: ConstFold to: " << *C << " from: " << *I);
+
// Add operands to the worklist...
AddUsesToWorkList(*I);
ReplaceInstUsesWith(*I, C);
continue;
}
+ // See if we can trivially sink this instruction to a successor basic block.
+ if (I->hasOneUse()) {
+ BasicBlock *BB = I->getParent();
+ BasicBlock *UserParent = cast<Instruction>(I->use_back())->getParent();
+ if (UserParent != BB) {
+ bool UserIsSuccessor = false;
+ // See if the user is one of our successors.
+ for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
+ if (*SI == UserParent) {
+ UserIsSuccessor = true;
+ break;
+ }
+
+ // If the user is one of our immediate successors, and if that successor
+ // only has us as a predecessors (we'd have to split the critical edge
+ // otherwise), we can keep going.
+ if (UserIsSuccessor && !isa<PHINode>(I->use_back()) &&
+ next(pred_begin(UserParent)) == pred_end(UserParent))
+ // Okay, the CFG is simple enough, try to sink this instruction.
+ Changed |= TryToSinkInstruction(I, UserParent);
+ }
+ }
+
// Now that we have an instruction, try combining it to simplify it...
if (Instruction *Result = visit(*I)) {
++NumCombined;
// Insert the new instruction into the basic block...
BasicBlock *InstParent = I->getParent();
- InstParent->getInstList().insert(I, Result);
+ BasicBlock::iterator InsertPos = I;
+
+ if (!isa<PHINode>(Result)) // If combining a PHI, don't insert
+ while (isa<PHINode>(InsertPos)) // middle of a block of PHIs.
+ ++InsertPos;
+
+ InstParent->getInstList().insert(InsertPos, Result);
// Make sure that we reprocess all operands now that we reduced their
// use counts.
return Changed;
}
-Pass *llvm::createInstructionCombiningPass() {
+FunctionPass *llvm::createInstructionCombiningPass() {
return new InstCombiner();
}
projects / oota-llvm.git / blobdiff