Initial revision
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/IPO/InlineSimple.cpp b/lib/Transforms/IPO/InlineSimple.cpp
new file mode 100644
index 0000000..a1e3156
--- /dev/null
+++ b/lib/Transforms/IPO/InlineSimple.cpp
@@ -0,0 +1,283 @@
+//===- MethodInlining.cpp - Code to perform method inlining ---------------===//
+//
+// This file implements inlining of methods.
+//
+// Specifically, this:
+// * Exports functionality to inline any method call
+// * Inlines methods that consist of a single basic block
+// * Is able to inline ANY method call
+// . Has a smart heuristic for when to inline a method
+//
+// Notice that:
+// * This pass has a habit of introducing duplicated constant pool entries,
+// and also opens up a lot of opportunities for constant propogation. It is
+// a good idea to to run a constant propogation pass, then a DCE pass
+// sometime after running this pass.
+//
+// TODO: Currently this throws away all of the symbol names in the method being
+// inlined to try to avoid name clashes. Use a name if it's not taken
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Module.h"
+#include "llvm/Method.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/iTerminators.h"
+#include "llvm/iOther.h"
+#include "llvm/Opt/AllOpts.h"
+#include <algorithm>
+#include <map>
+
+#include "llvm/Assembly/Writer.h"
+
+// RemapInstruction - Convert the instruction operands from referencing the
+// current values into those specified by ValueMap.
+//
+static inline void RemapInstruction(Instruction *I,
+ map<const Value *, Value*> &ValueMap) {
+
+ for (unsigned op = 0; const Value *Op = I->getOperand(op); op++) {
+ Value *V = ValueMap[Op];
+ if (!V && Op->getValueType() == Value::MethodVal)
+ continue; // Methods don't get relocated
+
+ if (!V) {
+ cerr << "Val = " << endl << Op << "Addr = " << (void*)Op << endl;
+ cerr << "Inst = " << I;
+ }
+ assert(V && "Referenced value not in value map!");
+ I->setOperand(op, V);
+ }
+}
+
+// InlineMethod - This function forcibly inlines the called method into the
+// basic block of the caller. This returns false if it is not possible to
+// inline this call. The program is still in a well defined state if this
+// occurs though.
+//
+// Note that this only does one level of inlining. For example, if the
+// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now
+// exists in the instruction stream. Similiarly this will inline a recursive
+// method by one level.
+//
+bool InlineMethod(BasicBlock::InstListType::iterator CIIt) {
+ assert((*CIIt)->getInstType() == Instruction::Call &&
+ "InlineMethod only works on CallInst nodes!");
+ assert((*CIIt)->getParent() && "Instruction not embedded in basic block!");
+ assert((*CIIt)->getParent()->getParent() && "Instruction not in method!");
+
+ CallInst *CI = (CallInst*)*CIIt;
+ const Method *CalledMeth = CI->getCalledMethod();
+ Method *CurrentMeth = CI->getParent()->getParent();
+
+ //cerr << "Inlining " << CalledMeth->getName() << " into "
+ // << CurrentMeth->getName() << endl;
+
+ BasicBlock *OrigBB = CI->getParent();
+
+ // Call splitBasicBlock - The original basic block now ends at the instruction
+ // immediately before the call. The original basic block now ends with an
+ // unconditional branch to NewBB, and NewBB starts with the call instruction.
+ //
+ BasicBlock *NewBB = OrigBB->splitBasicBlock(CIIt);
+
+ // Remove (unlink) the CallInst from the start of the new basic block.
+ NewBB->getInstList().remove(CI);
+
+ // If we have a return value generated by this call, convert it into a PHI
+ // node that gets values from each of the old RET instructions in the original
+ // method.
+ //
+ PHINode *PHI = 0;
+ if (CalledMeth->getReturnType() != Type::VoidTy) {
+ PHI = new PHINode(CalledMeth->getReturnType(), CI->getName());
+
+ // The PHI node should go at the front of the new basic block to merge all
+ // possible incoming values.
+ //
+ NewBB->getInstList().push_front(PHI);
+
+ // Anything that used the result of the function call should now use the PHI
+ // node as their operand.
+ //
+ CI->replaceAllUsesWith(PHI);
+ }
+
+ // Keep a mapping between the original method's values and the new duplicated
+ // code's values. This includes all of: Method arguments, instruction values,
+ // constant pool entries, and basic blocks.
+ //
+ map<const Value *, Value*> ValueMap;
+
+ // Add the method arguments to the mapping: (start counting at 1 to skip the
+ // method reference itself)
+ //
+ Method::ArgumentListType::const_iterator PTI =
+ CalledMeth->getArgumentList().begin();
+ for (unsigned a = 1; Value *Operand = CI->getOperand(a); ++a, ++PTI) {
+ ValueMap[*PTI] = Operand;
+ }
+
+
+ ValueMap[NewBB] = NewBB; // Returns get converted to reference NewBB
+
+ // Loop over all of the basic blocks in the method, inlining them as
+ // appropriate. Keep track of the first basic block of the method...
+ //
+ for (Method::BasicBlocksType::const_iterator BI =
+ CalledMeth->getBasicBlocks().begin();
+ BI != CalledMeth->getBasicBlocks().end(); BI++) {
+ const BasicBlock *BB = *BI;
+ assert(BB->getTerminator() && "BasicBlock doesn't have terminator!?!?");
+
+ // Create a new basic block to copy instructions into!
+ BasicBlock *IBB = new BasicBlock("", NewBB->getParent());
+
+ ValueMap[*BI] = IBB; // Add basic block mapping.
+
+ // Make sure to capture the mapping that a return will use...
+ // TODO: This assumes that the RET is returning a value computed in the same
+ // basic block as the return was issued from!
+ //
+ const TerminatorInst *TI = BB->getTerminator();
+
+ // Loop over all instructions copying them over...
+ Instruction *NewInst;
+ for (BasicBlock::InstListType::const_iterator II = BB->getInstList().begin();
+ II != (BB->getInstList().end()-1); II++) {
+ IBB->getInstList().push_back((NewInst = (*II)->clone()));
+ ValueMap[*II] = NewInst; // Add instruction map to value.
+ }
+
+ // Copy over the terminator now...
+ switch (TI->getInstType()) {
+ case Instruction::Ret: {
+ const ReturnInst *RI = (const ReturnInst*)TI;
+
+ if (PHI) { // The PHI node should include this value!
+ assert(RI->getReturnValue() && "Ret should have value!");
+ assert(RI->getReturnValue()->getType() == PHI->getType() &&
+ "Ret value not consistent in method!");
+ PHI->addIncoming((Value*)RI->getReturnValue());
+ }
+
+ // Add a branch to the code that was after the original Call.
+ IBB->getInstList().push_back(new BranchInst(NewBB));
+ break;
+ }
+ case Instruction::Br:
+ IBB->getInstList().push_back(TI->clone());
+ break;
+
+ default:
+ cerr << "MethodInlining: Don't know how to handle terminator: " << TI;
+ abort();
+ }
+ }
+
+
+ // Copy over the constant pool...
+ //
+ const ConstantPool &CP = CalledMeth->getConstantPool();
+ ConstantPool &NewCP = CurrentMeth->getConstantPool();
+ for (ConstantPool::plane_const_iterator PI = CP.begin(); PI != CP.end(); ++PI){
+ ConstantPool::PlaneType &Plane = **PI;
+ for (ConstantPool::PlaneType::const_iterator I = Plane.begin();
+ I != Plane.end(); ++I) {
+ ConstPoolVal *NewVal = (*I)->clone(); // Copy existing constant
+ NewCP.insert(NewVal); // Insert the new copy into local const pool
+ ValueMap[*I] = NewVal; // Keep track of constant value mappings
+ }
+ }
+
+ // Loop over all of the instructions in the method, fixing up operand
+ // references as we go. This uses ValueMap to do all the hard work.
+ //
+ for (Method::BasicBlocksType::const_iterator BI =
+ CalledMeth->getBasicBlocks().begin();
+ BI != CalledMeth->getBasicBlocks().end(); BI++) {
+ const BasicBlock *BB = *BI;
+ BasicBlock *NBB = (BasicBlock*)ValueMap[BB];
+
+ // Loop over all instructions, fixing each one as we find it...
+ //
+ for (BasicBlock::InstListType::iterator II = NBB->getInstList().begin();
+ II != NBB->getInstList().end(); II++)
+ RemapInstruction(*II, ValueMap);
+ }
+
+ if (PHI) RemapInstruction(PHI, ValueMap); // Fix the PHI node also...
+
+ // Change the branch that used to go to NewBB to branch to the first basic
+ // block of the inlined method.
+ //
+ TerminatorInst *Br = OrigBB->getTerminator();
+ assert(Br && Br->getInstType() == Instruction::Br &&
+ "splitBasicBlock broken!");
+ Br->setOperand(0, ValueMap[CalledMeth->getBasicBlocks().front()]);
+
+ // Since we are now done with the CallInst, we can finally delete it.
+ delete CI;
+ return true;
+}
+
+bool InlineMethod(CallInst *CI) {
+ assert(CI->getParent() && "CallInst not embeded in BasicBlock!");
+ BasicBlock *PBB = CI->getParent();
+
+ BasicBlock::InstListType::iterator CallIt = find(PBB->getInstList().begin(),
+ PBB->getInstList().end(),
+ CI);
+ assert(CallIt != PBB->getInstList().end() &&
+ "CallInst has parent that doesn't contain CallInst?!?");
+ return InlineMethod(CallIt);
+}
+
+static inline bool ShouldInlineMethod(const CallInst *CI, const Method *M) {
+ assert(CI->getParent() && CI->getParent()->getParent() &&
+ "Call not embedded into a method!");
+
+ // Don't inline a recursive call.
+ if (CI->getParent()->getParent() == M) return false;
+
+ // Don't inline something too big. This is a really crappy heuristic
+ if (M->getBasicBlocks().size() > 3) return false;
+
+ // Don't inline into something too big. This is a **really** crappy heuristic
+ if (CI->getParent()->getParent()->getBasicBlocks().size() > 10) return false;
+
+ // Go ahead and try just about anything else.
+ return true;
+}
+
+
+static inline bool DoMethodInlining(BasicBlock *BB) {
+ for (BasicBlock::InstListType::iterator I = BB->getInstList().begin();
+ I != BB->getInstList().end(); I++) {
+ if ((*I)->getInstType() == Instruction::Call) {
+ // Check to see if we should inline this method
+ CallInst *CI = (CallInst*)*I;
+ Method *M = CI->getCalledMethod();
+ if (ShouldInlineMethod(CI, M))
+ return InlineMethod(I);
+ }
+ }
+ return false;
+}
+
+bool DoMethodInlining(Method *M) {
+ Method::BasicBlocksType &BBs = M->getBasicBlocks();
+ bool Changed = false;
+
+ // Loop through now and inline instructions a basic block at a time...
+ for (Method::BasicBlocksType::iterator I = BBs.begin(); I != BBs.end(); )
+ if (DoMethodInlining(*I)) {
+ Changed = true;
+ // Iterator is now invalidated by new basic blocks inserted
+ I = BBs.begin();
+ } else {
+ ++I;
+ }
+
+ return Changed;
+}
diff --git a/lib/Transforms/Scalar/ConstantProp.cpp b/lib/Transforms/Scalar/ConstantProp.cpp
new file mode 100644
index 0000000..eef5a03
--- /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;
+}
diff --git a/lib/Transforms/Scalar/DCE.cpp b/lib/Transforms/Scalar/DCE.cpp
new file mode 100644
index 0000000..797edf5
--- /dev/null
+++ b/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/lib/Transforms/Scalar/SymbolStripping.cpp b/lib/Transforms/Scalar/SymbolStripping.cpp
new file mode 100644
index 0000000..af5f18f
--- /dev/null
+++ b/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());
+}