//===- 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;
// a signed value.
//
if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) {
- unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8;
- if (CUI->getValue() >= TypeBits &&
- !(Op0->getType()->isSigned() && I.getOpcode() == Instruction::Shr))
- return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
+ if (I.getOpcode() == Instruction::Shr) {
+ unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8;
+ if (CUI->getValue() >= TypeBits && !(Op0->getType()->isSigned()))
+ return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
+ }
+
+ // Check to see if we are shifting left by 1. If so, turn it into an add
+ // instruction.
+ if (I.getOpcode() == Instruction::Shl && CUI->equalsInt(1))
+ // Convert 'shl int %X, 2' to 'add int %X, %X'
+ return BinaryOperator::create(Instruction::Add, Op0, Op0, I.getName());
+
}
return 0;
}
-// isCIntegral - For the purposes of casting, we allow conversion of sizes and
-// stuff as long as the value type acts basically integral like.
-//
-static bool isCIntegral(const Type *Ty) {
- return Ty->isIntegral() || Ty == Type::BoolTy;
-}
-
// isEliminableCastOfCast - Return true if it is valid to eliminate the CI
// instruction.
//
// Allow free casting and conversion of sizes as long as the sign doesn't
// change...
- if (isCIntegral(SrcTy) && isCIntegral(MidTy) && isCIntegral(DstTy)) {
+ if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral()) {
unsigned SrcSize = SrcTy->getPrimitiveSize();
unsigned MidSize = MidTy->getPrimitiveSize();
unsigned DstSize = DstTy->getPrimitiveSize();
return SrcSize != MidSize || SrcTy == Type::BoolTy;
default: assert(0 && "Bad entry in sign table!");
}
- return false; // NOT REACHED
}
}
// 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