//===- 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;
}
// 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();
// 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 &&
}
+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;
}
}