// 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.
//
//===----------------------------------------------------------------------===//
#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 "llvm/Support/PatternMatch.h"
-#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
#include <algorithm>
using namespace llvm;
using namespace llvm::PatternMatch;
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);
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
}
// (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);
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_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
// power of 2.
static unsigned Log2(uint64_t Val) {
}
};
-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);
+}
+
+// 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. 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(Op, TV, IC);
+ Value *SelectFalseVal = FoldOperationIntoSelectOperand(Op, FV, IC);
+
+ return new SelectInst(SI->getCondition(), SelectTrueVal,
+ SelectFalseVal);
+ }
+ return 0;
}
/// is only possible if all operands to the PHI are constants).
Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) {
PHINode *PN = cast<PHINode>(I.getOperand(0));
- if (!PN->hasOneUse()) return 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 = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+ 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->op_reserve(PN->getNumOperands());
+ 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, e = PN->getNumIncomingValues(); i != e; ++i) {
+ 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, e = PN->getNumIncomingValues(); i != e; ++i) {
+ 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);
}
-// FoldBinOpIntoSelect - 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) {
- // 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);
-
- return new SelectInst(SI->getCondition(), SelectTrueVal,
- SelectFalseVal);
- }
- return 0;
-}
-
Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
bool Changed = SimplifyCommutative(I);
Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
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 (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
- ConstantInt *C2;
if (match(RHS, m_And(m_Value(), m_ConstantInt(C2))))
if (Instruction *R = AssociativeOpt(I, AddMaskingAnd(C2))) return R;
}
}
-
// Try to fold constant add into select arguments.
if (SelectInst *SI = dyn_cast<SelectInst>(LHS))
- if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
+ if (Instruction *R = FoldOpIntoSelect(I, SI, this))
return R;
}
// 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))
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;
}
// 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))
}
Instruction *InstCombiner::visitDiv(BinaryOperator &I) {
- if (isa<UndefValue>(I.getOperand(0))) // undef / X -> 0
+ 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>(I.getOperand(1)))
- return ReplaceInstUsesWith(I, I.getOperand(1)); // X / undef -> undef
+ if (isa<UndefValue>(Op1))
+ return ReplaceInstUsesWith(I, Op1); // X / undef -> undef
- if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) {
+ 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>(I.getOperand(0)))
+ 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)
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(I.getOperand(0)))
+ if (Value *LHSNeg = dyn_castNegVal(Op0))
return BinaryOperator::createDiv(LHSNeg, ConstantExpr::getNeg(RHS));
- if (isa<PHINode>(I.getOperand(0)) && !RHS->isNullValue())
- if (Instruction *NV = FoldOpIntoPhi(I))
- return NV;
+ 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) {
// X % -Y -> X % Y
return &I;
}
- if (isa<UndefValue>(I.getOperand(0))) // undef % X -> 0
+ if (isa<UndefValue>(Op0)) // undef % X -> 0
return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
- if (isa<UndefValue>(I.getOperand(1)))
- return ReplaceInstUsesWith(I, I.getOperand(1)); // X % undef -> undef
+ if (isa<UndefValue>(Op1))
+ return ReplaceInstUsesWith(I, Op1); // X % undef -> undef
- if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) {
+ 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));
- if (isa<PHINode>(I.getOperand(0)) && !RHS->isNullValue())
- if (Instruction *NV = FoldOpIntoPhi(I))
- return NV;
+ 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()));
};
+/// 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:
if (isa<UndefValue>(Op1)) // X & undef -> 0
return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
- // and X, X = X and X, 0 == 0
- if (Op0 == Op1 || Op1 == 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))
// or X, -1 == -1
if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
- if (RHS->isAllOnesValue())
- return ReplaceInstUsesWith(I, Op1);
+ // 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)
// 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))
// 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))
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 (isa<UndefValue>(Op1)) // X setcc undef -> undef
return ReplaceInstUsesWith(I, UndefValue::get(Type::BoolTy));
- // setcc <global/alloca*>, 0 - Global/Stack value addresses are never null!
- if (isa<ConstantPointerNull>(Op1) &&
- (isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0)))
+ // 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) {
switch (I.getOpcode()) {
}
break;
- case Instruction::Cast: { // (setcc (cast X to larger), CI)
- const Type *SrcTy = LHSI->getOperand(0)->getType();
- if (SrcTy->isIntegral() && LHSI->getType()->isIntegral()) {
- unsigned SrcBits = SrcTy->getPrimitiveSize()*8;
- if (SrcTy == Type::BoolTy) SrcBits = 1;
- unsigned DestBits = LHSI->getType()->getPrimitiveSize()*8;
- if (LHSI->getType() == Type::BoolTy) DestBits = 1;
- if (SrcBits < DestBits &&
- // FIXME: Reenable the code below for < and >. However, we have
- // to handle the cases when the source of the cast and the dest of
- // the cast have different signs. e.g:
- // (cast sbyte %X to uint) >u 255U -> X <s (sbyte)0
- (I.getOpcode() == Instruction::SetEQ ||
- I.getOpcode() == Instruction::SetNE)) {
- // Check to see if the comparison is always true or false.
- Constant *NewCst = ConstantExpr::getCast(CI, SrcTy);
- if (ConstantExpr::getCast(NewCst, LHSI->getType()) != CI) {
- switch (I.getOpcode()) {
- default: assert(0 && "unknown integer comparison");
-#if 0
- case Instruction::SetLT: {
- Constant *Max = ConstantIntegral::getMaxValue(SrcTy);
- Max = ConstantExpr::getCast(Max, LHSI->getType());
- return ReplaceInstUsesWith(I, ConstantExpr::getSetLT(Max, CI));
- }
- case Instruction::SetGT: {
- Constant *Min = ConstantIntegral::getMinValue(SrcTy);
- Min = ConstantExpr::getCast(Min, LHSI->getType());
- return ReplaceInstUsesWith(I, ConstantExpr::getSetGT(Min, CI));
- }
-#endif
- case Instruction::SetEQ:
- return ReplaceInstUsesWith(I, ConstantBool::False);
- case Instruction::SetNE:
- return ReplaceInstUsesWith(I, ConstantBool::True);
- }
- }
-
- return new SetCondInst(I.getOpcode(), LHSI->getOperand(0), NewCst);
- }
- }
+ // (setcc (cast X to larger), CI)
+ case Instruction::Cast:
+ if (Instruction *R =
+ visitSetCondInstWithCastAndConstant(I,cast<CastInst>(LHSI),CI))
+ return R;
break;
- }
+
case Instruction::Shl: // (setcc (shl X, ShAmt), CI)
if (ConstantUInt *ShAmt = dyn_cast<ConstantUInt>(LHSI->getOperand(1))) {
switch (I.getOpcode()) {
if (LHSI->hasOneUse()) {
// Otherwise strength reduce the shift into an and.
- unsigned ShAmtVal = ShAmt->getValue();
+ unsigned ShAmtVal = (unsigned)ShAmt->getValue();
unsigned TypeBits = CI->getType()->getPrimitiveSize()*8;
uint64_t Val = (1ULL << (TypeBits-ShAmtVal))-1;
}
if (LHSI->hasOneUse() || CI->isNullValue()) {
- unsigned ShAmtVal = ShAmt->getValue();
+ unsigned ShAmtVal = (unsigned)ShAmt->getValue();
// Otherwise strength reduce the shift into an and.
uint64_t Val = ~0ULL; // All ones.
}
}
+ // 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) {
// 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 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 (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 (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0))
if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
bool isValid = true; // Valid only for And, Or, Xor
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()) {
// 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;
}
}
+/// 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 (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 (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);
}
+// 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
//
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(),
// 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());
+ }
}
}
}
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 = CS->getOperand(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(CU->getValue()));
+ 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 = CA->getOperand(CI->getRawValue());
+ C = CA->getOperand((unsigned)CI->getRawValue());
else if (isa<ConstantAggregateZero>(C))
C = Constant::getNullValue(ATy->getElementType());
else if (isa<UndefValue>(C))
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.isVolatile()),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;
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>(I->getOperand(0))->isNullValue() &&
- !isa<ConstantPointerNull>(C)) {
+ 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;
if (!isa<ConstantInt>(I->getOperand(i)))
isFoldableGEP = false;
if (isFoldableGEP) {
- uint64_t Offset = TD->getIndexedOffset(I->getOperand(0)->getType(),
+ 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());
}
}
+ 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.
projects / oota-llvm.git / blobdiff