blob: eef5a039f035b1421f73ce2ce223fa8f7aabc0a7 [file] [log] [blame]
//===- ConstantProp.cpp - Code to perform Constant Propogation ------------===//
//
// This file implements constant propogation and merging:
//
// Specifically, this:
// * Folds multiple identical constants in the constant pool together
// Note that if one is named and the other is not, that the result gets the
// original name.
// * Converts instructions like "add int %1, %2" into a direct def of %3 in
// the constant pool
// * Converts conditional branches on a constant boolean value into direct
// branches.
// * Converts phi nodes with one incoming def to the incoming def directly
// . Converts switch statements with one entry into a test & conditional
// branch
// . Converts switches on constant values into an unconditional branch.
//
// Notice that:
// * This pass has a habit of making definitions be dead. It is a good idea
// to to run a DCE pass sometime after running this pass.
//
//===----------------------------------------------------------------------===//
#include "llvm/Module.h"
#include "llvm/Method.h"
#include "llvm/BasicBlock.h"
#include "llvm/iTerminators.h"
#include "llvm/iOther.h"
#include "llvm/ConstPoolVals.h"
#include "llvm/ConstantPool.h"
#include "llvm/Opt/AllOpts.h"
#include "llvm/Opt/ConstantHandling.h"
// Merge identical constant values in the constant pool.
//
// TODO: We can do better than this simplistic N^2 algorithm...
//
static bool MergeConstantPoolReferences(ConstantPool &CP) {
bool Modified = false;
for (ConstantPool::plane_iterator PI = CP.begin(); PI != CP.end(); ++PI) {
for (ConstantPool::PlaneType::iterator I = (*PI)->begin();
I != (*PI)->end(); I++) {
ConstPoolVal *C = *I;
ConstantPool::PlaneType::iterator J = I;
for (++J; J != (*PI)->end(); J++) {
if (C->equals(*J)) {
Modified = true;
// Okay we know that *I == *J. So now we need to make all uses of *I
// point to *J.
//
C->replaceAllUsesWith(*J);
(*PI)->remove(I); // Remove C from constant pool...
if (C->hasName() && !(*J)->hasName()) // The merged constant inherits
(*J)->setName(C->getName()); // the old name...
delete C; // Delete the constant itself.
break; // Break out of inner for loop
}
}
}
}
return Modified;
}
inline static bool
ConstantFoldUnaryInst(Method *M, Method::inst_iterator &DI,
UnaryOperator *Op, ConstPoolVal *D) {
ConstPoolVal *ReplaceWith = 0;
switch (Op->getInstType()) {
case Instruction::Not: ReplaceWith = !*D; break;
case Instruction::Neg: ReplaceWith = -*D; break;
}
if (!ReplaceWith) return false; // Nothing new to change...
// Add the new value to the constant pool...
M->getConstantPool().insert(ReplaceWith);
// Replaces all of the uses of a variable with uses of the constant.
Op->replaceAllUsesWith(ReplaceWith);
// Remove the operator from the list of definitions...
Op->getParent()->getInstList().remove(DI.getInstructionIterator());
// The new constant inherits the old name of the operator...
if (Op->hasName()) ReplaceWith->setName(Op->getName());
// Delete the operator now...
delete Op;
return true;
}
inline static bool
ConstantFoldBinaryInst(Method *M, Method::inst_iterator &DI,
BinaryOperator *Op,
ConstPoolVal *D1, ConstPoolVal *D2) {
ConstPoolVal *ReplaceWith = 0;
switch (Op->getInstType()) {
case Instruction::Add: ReplaceWith = *D1 + *D2; break;
case Instruction::Sub: ReplaceWith = *D1 - *D2; break;
case Instruction::SetEQ: ReplaceWith = *D1 == *D2; break;
case Instruction::SetNE: ReplaceWith = *D1 != *D2; break;
case Instruction::SetLE: ReplaceWith = *D1 <= *D2; break;
case Instruction::SetGE: ReplaceWith = *D1 >= *D2; break;
case Instruction::SetLT: ReplaceWith = *D1 < *D2; break;
case Instruction::SetGT: ReplaceWith = *D1 > *D2; break;
}
if (!ReplaceWith) return false; // Nothing new to change...
// Add the new value to the constant pool...
M->getConstantPool().insert(ReplaceWith);
// Replaces all of the uses of a variable with uses of the constant.
Op->replaceAllUsesWith(ReplaceWith);
// Remove the operator from the list of definitions...
Op->getParent()->getInstList().remove(DI.getInstructionIterator());
// The new constant inherits the old name of the operator...
if (Op->hasName()) ReplaceWith->setName(Op->getName());
// Delete the operator now...
delete Op;
return true;
}
inline static bool ConstantFoldTerminator(TerminatorInst *T) {
// Branch - See if we are conditional jumping on constant
if (T->getInstType() == Instruction::Br) {
BranchInst *BI = (BranchInst*)T;
if (!BI->isUnconditional() && // Are we branching on constant?
BI->getOperand(2)->getValueType() == Value::ConstantVal) {
// YES. Change to unconditional branch...
ConstPoolBool *Cond = (ConstPoolBool*)BI->getOperand(2);
Value *Destination = BI->getOperand(Cond->getValue() ? 0 : 1);
BI->setOperand(0, Destination); // Set the unconditional destination
BI->setOperand(1, 0); // Clear the conditional destination
BI->setOperand(2, 0); // Clear the condition...
return true;
}
}
return false;
}
// ConstantFoldInstruction - If an instruction references constants, try to fold
// them together...
//
inline static bool
ConstantFoldInstruction(Method *M, Method::inst_iterator &II) {
Instruction *Inst = *II;
if (Inst->isBinaryOp()) {
Value *D1, *D2;
if (((D1 = Inst->getOperand(0))->getValueType() == Value::ConstantVal) &
((D2 = Inst->getOperand(1))->getValueType() == Value::ConstantVal))
return ConstantFoldBinaryInst(M, II, (BinaryOperator*)Inst,
(ConstPoolVal*)D1, (ConstPoolVal*)D2);
} else if (Inst->isUnaryOp()) {
Value *D;
if ((D = Inst->getOperand(0))->getValueType() == Value::ConstantVal)
return ConstantFoldUnaryInst(M, II, (UnaryOperator*)Inst,
(ConstPoolVal*)D);
} else if (Inst->isTerminator()) {
return ConstantFoldTerminator((TerminatorInst*)Inst);
} else if (Inst->getInstType() == Instruction::PHINode) {
PHINode *PN = (PHINode*)Inst; // If it's a PHI node and only has one operand
// Then replace it directly with that operand.
assert(PN->getOperand(0) && "PHI Node must have at least one operand!");
if (PN->getOperand(1) == 0) { // If the PHI Node has exactly 1 operand
Value *V = PN->getOperand(0);
PN->replaceAllUsesWith(V); // Replace all uses of this PHI
// Unlink from basic block
PN->getParent()->getInstList().remove(II.getInstructionIterator());
if (PN->hasName()) V->setName(PN->getName()); // Inherit PHINode name
delete PN; // Finally, delete the node...
return true;
}
}
return false;
}
// DoConstPropPass - Propogate constants and do constant folding on instructions
// this returns true if something was changed, false if nothing was changed.
//
static bool DoConstPropPass(Method *M) {
bool SomethingChanged = false;
#if 1
Method::inst_iterator It = M->inst_begin();
while (It != M->inst_end())
if (ConstantFoldInstruction(M, It)) {
SomethingChanged = true; // If returned true, iter is already incremented
// Incrementing the iterator in an unchecked manner could mess up the
// internals of 'It'. To make sure everything is happy, tell it we might
// have broken it.
It.resyncInstructionIterator();
} else {
++It;
}
#else
Method::BasicBlocksType::iterator BBIt = M->getBasicBlocks().begin();
for (; BBIt != M->getBasicBlocks().end(); BBIt++) {
BasicBlock *BB = *BBIt;
BasicBlock::InstListType::iterator DI = BB->getInstList().begin();
for (; DI != BB->getInstList().end(); DI++)
SomethingChanged |= ConstantFoldInstruction(M, DI);
}
#endif
return SomethingChanged;
}
// returns true on failure, false on success...
//
bool DoConstantPropogation(Method *M) {
bool Modified = false;
// Fold constants until we make no progress...
while (DoConstPropPass(M)) Modified = true;
// Merge identical constants last: this is important because we may have just
// introduced constants that already exist!
//
Modified |= MergeConstantPoolReferences(M->getConstantPool());
return Modified;
}