diff options
Diffstat (limited to 'lib/Transforms/Scalar/ConstantProp.cpp')
| -rw-r--r-- | lib/Transforms/Scalar/ConstantProp.cpp | 239 |
1 files changed, 239 insertions, 0 deletions
diff --git a/lib/Transforms/Scalar/ConstantProp.cpp b/lib/Transforms/Scalar/ConstantProp.cpp new file mode 100644 index 0000000000..eef5a039f0 --- /dev/null +++ b/lib/Transforms/Scalar/ConstantProp.cpp @@ -0,0 +1,239 @@ +//===- 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; +} |