//===- InstructionCombining.cpp - Combine multiple instructions -----------===//
//
// InstructionCombining - Combine instructions to form fewer, simple
-// instructions. This pass does not modify the CFG, and has a tendancy to
-// make instructions dead, so a subsequent DIE pass is useful. This pass is
-// where algebraic simplification happens.
+// instructions. This pass does not modify the CFG This pass is where algebraic
+// simplification happens.
//
// This pass combines things like:
// %Y = add int 1, %X
#include "Support/StatisticReporter.h"
#include <algorithm>
-static Statistic<> NumCombined("instcombine\t- Number of insts combined");
+static Statistic<> NumCombined ("instcombine\t- Number of insts combined");
+static Statistic<> NumConstProp("instcombine\t- Number of constant folds");
+static Statistic<> NumDeadInst ("instcombine\t- Number of dead inst eliminate");
namespace {
class InstCombiner : public FunctionPass,
WorkList.push_back(cast<Instruction>(*UI));
}
+ // removeFromWorkList - remove all instances of I from the worklist.
+ void removeFromWorkList(Instruction *I);
public:
virtual bool runOnFunction(Function &F);
// in the program. Add the new instruction to the worklist.
//
void InsertNewInstBefore(Instruction *New, Instruction &Old) {
+ assert(New && New->getParent() == 0 &&
+ "New instruction already inserted into a basic block!");
BasicBlock *BB = Old.getParent();
BB->getInstList().insert(&Old, New); // Insert inst
WorkList.push_back(New); // Add to worklist
// Simplify mul instructions with a constant RHS...
if (Constant *Op2 = dyn_cast<Constant>(I.getOperand(1))) {
- if (I.getType()->isIntegral() && cast<ConstantInt>(Op2)->equalsInt(1))
+ if (I.getType()->isInteger() && cast<ConstantInt>(Op2)->equalsInt(1))
return ReplaceInstUsesWith(I, Op1); // Eliminate 'mul int %X, 1'
- if (I.getType()->isIntegral() && cast<ConstantInt>(Op2)->equalsInt(2))
+ if (I.getType()->isInteger() && cast<ConstantInt>(Op2)->equalsInt(2))
// Convert 'mul int %X, 2' to 'add int %X, %X'
return BinaryOperator::create(Instruction::Add, Op1, Op1, I.getName());
if (RHS->isAllOnesValue())
return ReplaceInstUsesWith(I, Op0);
+ // and (not A), (not B) == not (or A, B)
+ if (Op0->use_size() == 1 && Op1->use_size() == 1)
+ if (Value *A = dyn_castNotInst(Op0))
+ if (Value *B = dyn_castNotInst(Op1)) {
+ Instruction *Or = BinaryOperator::create(Instruction::Or, A, B,
+ I.getName()+".demorgan");
+ InsertNewInstBefore(Or, I);
+ return BinaryOperator::createNot(Or, I.getName());
+ }
+
return Changed ? &I : 0;
}
if (Op1C->isNullValue())
return ReplaceInstUsesWith(I, Op0);
- // xor (xor X, -1), -1 = not (not X) = X
- if (Op1C->isAllOnesValue())
+ // Is this a "NOT" instruction?
+ if (Op1C->isAllOnesValue()) {
+ // xor (xor X, -1), -1 = not (not X) = X
if (Value *X = dyn_castNotInst(Op0))
return ReplaceInstUsesWith(I, X);
+
+ // xor (setcc A, B), true = not (setcc A, B) = setncc A, B
+ if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0))
+ if (SCI->use_size() == 1)
+ return new SetCondInst(SCI->getInverseCondition(),
+ SCI->getOperand(0), SCI->getOperand(1));
+ }
}
return Changed ? &I : 0;
// 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)
+ // int->float->int would not be allowed)
if (SrcTy == DstTy && SrcTy->isLosslesslyConvertableTo(MidTy))
return true;
// Allow free casting and conversion of sizes as long as the sign doesn't
// change...
- if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral() &&
- SrcTy->isSigned() == MidTy->isSigned() &&
- MidTy->isSigned() == DstTy->isSigned()) {
- // Only accept cases where we are either monotonically increasing the type
- // size, or monotonically decreasing it.
- //
+ if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral()) {
unsigned SrcSize = SrcTy->getPrimitiveSize();
unsigned MidSize = MidTy->getPrimitiveSize();
unsigned DstSize = DstTy->getPrimitiveSize();
- if (SrcSize < MidSize && MidSize < DstSize)
- return true;
- if (SrcSize > MidSize && MidSize > DstSize)
+ // Cases where we are monotonically decreasing the size of the type are
+ // always ok, regardless of what sign changes are going on.
+ //
+ if (SrcSize >= MidSize && MidSize >= DstSize)
return true;
+
+ // If we are monotonically growing, things are more complex.
+ //
+ if (SrcSize <= MidSize && MidSize <= DstSize) {
+ // We have eight combinations of signedness to worry about. Here's the
+ // table:
+ static const int SignTable[8] = {
+ // CODE, SrcSigned, MidSigned, DstSigned, Comment
+ 1, // U U U Always ok
+ 1, // U U S Always ok
+ 3, // U S U Ok iff SrcSize != MidSize
+ 3, // U S S Ok iff SrcSize != MidSize
+ 0, // S U U Never ok
+ 2, // S U S Ok iff MidSize == DstSize
+ 1, // S S U Always ok
+ 1, // S S S Always ok
+ };
+
+ // Choose an action based on the current entry of the signtable that this
+ // cast of cast refers to...
+ unsigned Row = SrcTy->isSigned()*4+MidTy->isSigned()*2+DstTy->isSigned();
+ switch (SignTable[Row]) {
+ case 0: return false; // Never ok
+ case 1: return true; // Always ok
+ case 2: return MidSize == DstSize; // Ok iff MidSize == DstSize
+ case 3: // Ok iff SrcSize != MidSize
+ return SrcSize != MidSize || SrcTy == Type::BoolTy;
+ default: assert(0 && "Bad entry in sign table!");
+ }
+ }
}
// Otherwise, we cannot succeed. Specifically we do not want to allow things
// to convert this into a logical 'and' instruction.
//
if (CSrc->getOperand(0)->getType() == CI.getType() &&
- CI.getType()->isIntegral() && CSrc->getType()->isIntegral() &&
+ CI.getType()->isInteger() && CSrc->getType()->isInteger() &&
CI.getType()->isUnsigned() && CSrc->getType()->isUnsigned() &&
CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()){
assert(CSrc->getType() != Type::ULongTy &&
//
Instruction *InstCombiner::visitPHINode(PHINode &PN) {
// If the PHI node only has one incoming value, eliminate the PHI node...
+ if (PN.getNumIncomingValues() == 0)
+ return ReplaceInstUsesWith(PN, Constant::getNullValue(PN.getType()));
if (PN.getNumIncomingValues() == 1)
return ReplaceInstUsesWith(PN, PN.getIncomingValue(0));
+
+ // Otherwise if all of the incoming values are the same for the PHI, replace
+ // the PHI node with the incoming value.
+ //
+ Value *InVal = 0;
+ for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
+ if (PN.getIncomingValue(i) != &PN) // Not the PHI node itself...
+ if (InVal && PN.getIncomingValue(i) != InVal)
+ return 0; // Not the same, bail out.
+ else
+ InVal = PN.getIncomingValue(i);
+
+ // The only case that could cause InVal to be null is if we have a PHI node
+ // that only has entries for itself. In this case, there is no entry into the
+ // loop, so kill the PHI.
+ //
+ if (InVal == 0) InVal = Constant::getNullValue(PN.getType());
- return 0;
+ // All of the incoming values are the same, replace the PHI node now.
+ return ReplaceInstUsesWith(PN, InVal);
}
// is a getelementptr instruction, combine the indices of the two
// getelementptr instructions into a single instruction.
//
- if (GetElementPtrInst *Src =
- dyn_cast<GetElementPtrInst>(GEP.getPointerOperand())) {
+ if (GetElementPtrInst *Src = dyn_cast<GetElementPtrInst>(GEP.getOperand(0))) {
std::vector<Value *> Indices;
// Can we combine the two pointer arithmetics offsets?
if (!Indices.empty())
return new GetElementPtrInst(Src->getOperand(0), Indices, GEP.getName());
+
+ } else if (GlobalValue *GV = dyn_cast<GlobalValue>(GEP.getOperand(0))) {
+ // GEP of global variable. If all of the indices for this GEP are
+ // constants, we can promote this to a constexpr instead of an instruction.
+
+ // Scan for nonconstants...
+ std::vector<Constant*> Indices;
+ User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end();
+ for (; I != E && isa<Constant>(*I); ++I)
+ Indices.push_back(cast<Constant>(*I));
+
+ if (I == E) { // If they are all constants...
+ ConstantExpr *CE =
+ ConstantExpr::getGetElementPtr(ConstantPointerRef::get(GV), Indices);
+
+ // Replace all uses of the GEP with the new constexpr...
+ return ReplaceInstUsesWith(GEP, CE);
+ }
}
return 0;
}
+void InstCombiner::removeFromWorkList(Instruction *I) {
+ WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
+ WorkList.end());
+}
+
bool InstCombiner::runOnFunction(Function &F) {
bool Changed = false;
Instruction *I = WorkList.back(); // Get an instruction from the worklist
WorkList.pop_back();
+ // Check to see if we can DCE or ConstantPropogate the instruction...
+ // Check to see if we can DIE the instruction...
+ if (isInstructionTriviallyDead(I)) {
+ // Add operands to the worklist...
+ for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
+ if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i)))
+ WorkList.push_back(Op);
+
+ ++NumDeadInst;
+ BasicBlock::iterator BBI = I;
+ if (dceInstruction(BBI)) {
+ removeFromWorkList(I);
+ continue;
+ }
+ }
+
+ // Instruction isn't dead, see if we can constant propogate it...
+ if (Constant *C = ConstantFoldInstruction(I)) {
+ // Add operands to the worklist...
+ for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
+ if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i)))
+ WorkList.push_back(Op);
+ I->replaceAllUsesWith(C);
+ ++NumConstProp;
+ BasicBlock::iterator BBI = I;
+ if (dceInstruction(BBI)) {
+ removeFromWorkList(I);
+ continue;
+ }
+ }
+
// Now that we have an instruction, try combining it to simplify it...
if (Instruction *Result = visit(*I)) {
++NumCombined;
if (Result != I) {
// Instructions can end up on the worklist more than once. Make sure
// we do not process an instruction that has been deleted.
- WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
- WorkList.end());
-
+ removeFromWorkList(I);
ReplaceInstWithInst(I, Result);
} else {
BasicBlock::iterator II = I;
if (dceInstruction(II)) {
// Instructions may end up in the worklist more than once. Erase them
// all.
- WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
- WorkList.end());
+ removeFromWorkList(I);
Result = 0;
}
}
projects / oota-llvm.git / blobdiff