Initial revision
llvm-svn: 2
diff --git a/llvm/lib/Transforms/Scalar/ConstantProp.cpp b/llvm/lib/Transforms/Scalar/ConstantProp.cpp
new file mode 100644
index 0000000..eef5a03
--- /dev/null
+++ b/llvm/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;
+}
diff --git a/llvm/lib/Transforms/Scalar/DCE.cpp b/llvm/lib/Transforms/Scalar/DCE.cpp
new file mode 100644
index 0000000..797edf5
--- /dev/null
+++ b/llvm/lib/Transforms/Scalar/DCE.cpp
@@ -0,0 +1,193 @@
+//===- DCE.cpp - Code to perform dead code elimination --------------------===//
+//
+// This file implements dead code elimination and basic block merging.
+//
+// Specifically, this:
+// * removes definitions with no uses (including unused constants)
+// * removes basic blocks with no predecessors
+// * merges a basic block into its predecessor if there is only one and the
+// predecessor only has one successor.
+//
+// TODO: This should REALLY be recursive instead of iterative. Right now, we
+// scan linearly through values, removing unused ones as we go. The problem is
+// that this may cause other earlier values to become unused. To make sure that
+// we get them all, we iterate until things stop changing. Instead, when
+// removing a value, recheck all of its operands to see if they are now unused.
+// Piece of cake, and more efficient as well.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Module.h"
+#include "llvm/Method.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/iTerminators.h"
+#include "llvm/Opt/AllOpts.h"
+
+struct ConstPoolDCE {
+ enum { EndOffs = 0 };
+ static bool isDCEable(const Value *) { return true; }
+};
+
+struct BasicBlockDCE {
+ enum { EndOffs = 1 };
+ static bool isDCEable(const Instruction *I) {
+ return !I->hasSideEffects();
+ }
+};
+
+template<class ValueSubclass, class ItemParentType, class DCEController>
+static bool RemoveUnusedDefs(ValueHolder<ValueSubclass, ItemParentType> &Vals,
+ DCEController DCEControl) {
+ bool Changed = false;
+ typedef ValueHolder<ValueSubclass, ItemParentType> Container;
+
+ int Offset = DCEController::EndOffs;
+ for (Container::iterator DI = Vals.begin(); DI != Vals.end()-Offset; ) {
+ // Look for un"used" definitions...
+ if ((*DI)->use_empty() && DCEController::isDCEable(*DI)) {
+ // Bye bye
+ delete Vals.remove(DI);
+ Changed = true;
+ } else {
+ DI++;
+ }
+ }
+ return Changed;
+}
+
+
+bool DoRemoveUnusedConstants(SymTabValue *S) {
+ bool Changed = false;
+ ConstantPool &CP = S->getConstantPool();
+ for (ConstantPool::plane_iterator PI = CP.begin(); PI != CP.end(); ++PI)
+ Changed |= RemoveUnusedDefs(**PI, ConstPoolDCE());
+ return Changed;
+}
+
+
+static void ReplaceUsesWithConstant(Instruction *I) {
+ // Get the method level constant pool
+ ConstantPool &CP = I->getParent()->getParent()->getConstantPool();
+
+ ConstPoolVal *CPV = 0;
+ ConstantPool::PlaneType *P;
+ if (!CP.getPlane(I->getType(), P)) { // Does plane exist?
+ // Yes, is it empty?
+ if (!P->empty()) CPV = P->front();
+ }
+
+ if (CPV == 0) { // We don't have an existing constant to reuse. Just add one.
+ CPV = ConstPoolVal::getNullConstant(I->getType()); // Create a new constant
+
+ // Add the new value to the constant pool...
+ CP.insert(CPV);
+ }
+
+ // Make all users of this instruction reference the constant instead
+ I->replaceAllUsesWith(CPV);
+}
+
+static bool DoDCEPass(Method *M) {
+ Method::BasicBlocksType::iterator BBIt;
+ Method::BasicBlocksType &BBs = M->getBasicBlocks();
+ bool Changed = false;
+
+ // Loop through now and remove instructions that have no uses...
+ for (BBIt = BBs.begin(); BBIt != BBs.end(); BBIt++)
+ Changed |= RemoveUnusedDefs((*BBIt)->getInstList(), BasicBlockDCE());
+
+ // Scan through and remove basic blocks that have no predecessors (except,
+ // of course, the first one. :) (so skip first block)
+ //
+ for (BBIt = BBs.begin(), ++BBIt; BBIt != BBs.end(); BBIt++) {
+ BasicBlock *BB = *BBIt;
+ assert(BB->getTerminator() &&
+ "Degenerate basic block encountered!"); // Empty bb???
+
+ if (BB->pred_begin() == BB->pred_end() &&
+ !BB->hasConstantPoolReferences()) {
+
+ while (!BB->getInstList().empty()) {
+ Instruction *I = BB->getInstList().front();
+ // If this instruction is used, replace uses with an arbitrary
+ // constant value. Because control flow can't get here, we don't care
+ // what we replace the value with.
+ if (!I->use_empty()) ReplaceUsesWithConstant(I);
+
+ // Remove the instruction from the basic block
+ BasicBlock::InstListType::iterator f = BB->getInstList().begin();
+ delete BB->getInstList().remove(f);
+ }
+
+ delete BBs.remove(BBIt);
+ ++BBIt; // remove puts use on the previous block, we want the next one
+ Changed = true;
+ }
+ }
+
+ // Loop through an merge basic blocks into their predecessor if there is only
+ // one, and if there is only one successor of the predecessor.
+ //
+ for (BBIt = BBs.begin(); BBIt != BBs.end(); BBIt++) {
+ BasicBlock *BB = *BBIt;
+
+ // Is there exactly one predecessor to this block?
+ BasicBlock::pred_iterator PI(BB->pred_begin());
+ if (PI != BB->pred_end() && ++PI == BB->pred_end() &&
+ !BB->hasConstantPoolReferences()) {
+ BasicBlock *Pred = *BB->pred_begin();
+ TerminatorInst *Term = Pred->getTerminator();
+ if (Term == 0) continue; // Err... malformed basic block!
+
+ // Is it an unconditional branch?
+ if (Term->getInstType() != Instruction::Br ||
+ !((BranchInst*)Term)->isUnconditional())
+ continue; // Nope, maybe next time...
+
+ Changed = true;
+
+ // Make all branches to the predecessor now point to the successor...
+ Pred->replaceAllUsesWith(BB);
+
+ // Move all definitions in the predecessor to the successor...
+ BasicBlock::InstListType::iterator DI = Pred->getInstList().end();
+ assert(Pred->getTerminator() &&
+ "Degenerate basic block encountered!"); // Empty bb???
+ delete Pred->getInstList().remove(--DI); // Remove terminator
+
+ while (Pred->getInstList().begin() != (DI = Pred->getInstList().end())) {
+ Instruction *Def = Pred->getInstList().remove(--DI); // Remove from end
+ BB->getInstList().push_front(Def); // Add to front...
+ }
+
+ // Remove basic block from the method...
+ BBs.remove(Pred);
+
+ // Always inherit predecessors name if it exists...
+ if (Pred->hasName()) BB->setName(Pred->getName());
+
+ // So long you waste of a basic block you...
+ delete Pred;
+ }
+ }
+
+ // Remove unused constants
+ Changed |= DoRemoveUnusedConstants(M);
+ return Changed;
+}
+
+
+// It is possible that we may require multiple passes over the code to fully
+// eliminate dead code. Iterate until we are done.
+//
+bool DoDeadCodeElimination(Method *M) {
+ bool Changed = false;
+ while (DoDCEPass(M)) Changed = true;
+ return Changed;
+}
+
+bool DoDeadCodeElimination(Module *C) {
+ bool Val = ApplyOptToAllMethods(C, DoDeadCodeElimination);
+ while (DoRemoveUnusedConstants(C)) Val = true;
+ return Val;
+}
diff --git a/llvm/lib/Transforms/Scalar/SymbolStripping.cpp b/llvm/lib/Transforms/Scalar/SymbolStripping.cpp
new file mode 100644
index 0000000..af5f18f
--- /dev/null
+++ b/llvm/lib/Transforms/Scalar/SymbolStripping.cpp
@@ -0,0 +1,55 @@
+//===- SymbolStripping.cpp - Code to string symbols for methods and modules -=//
+//
+// This file implements stripping symbols out of symbol tables.
+//
+// Specifically, this allows you to strip all of the symbols out of:
+// * A method
+// * All methods in a module
+// * All symbols in a module (all method symbols + all module scope symbols)
+//
+// Notice that:
+// * This pass makes code much less readable, so it should only be used in
+// situations where the 'strip' utility would be used (such as reducing
+// code size, and making it harder to reverse engineer code).
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Module.h"
+#include "llvm/Method.h"
+#include "llvm/SymbolTable.h"
+#include "llvm/Opt/AllOpts.h"
+
+static bool StripSymbolTable(SymbolTable *SymTab) {
+ if (SymTab == 0) return false; // No symbol table? No problem.
+ bool RemovedSymbol = false;
+
+ for (SymbolTable::iterator I = SymTab->begin(); I != SymTab->end(); I++) {
+ map<const string, Value *> &Plane = I->second;
+
+ map<const string, Value *>::iterator B;
+ while ((B = Plane.begin()) != Plane.end()) { // Found nonempty type plane!
+ B->second->setName(""); // Set name to "", removing from symbol table!
+ RemovedSymbol = true;
+ assert(Plane.begin() != B);
+ }
+ }
+
+ return RemovedSymbol;
+}
+
+
+// DoSymbolStripping - Remove all symbolic information from a method
+//
+bool DoSymbolStripping(Method *M) {
+ return StripSymbolTable(M->getSymbolTable());
+}
+
+// DoFullSymbolStripping - Remove all symbolic information from all methods
+// in a module, and all module level symbols. (method names, etc...)
+//
+bool DoFullSymbolStripping(Module *M) {
+ // Remove all symbols from methods in this module... and then strip all of the
+ // symbols in this module...
+ //
+ return DoSymbolStripping(M) | StripSymbolTable(M->getSymbolTable());
+}