diff options
Diffstat (limited to 'lib/Transforms')
-rw-r--r-- | lib/Transforms/IPO/InlineSimple.cpp | 283 | ||||
-rw-r--r-- | lib/Transforms/Scalar/ConstantProp.cpp | 239 | ||||
-rw-r--r-- | lib/Transforms/Scalar/DCE.cpp | 193 | ||||
-rw-r--r-- | lib/Transforms/Scalar/SymbolStripping.cpp | 55 |
4 files changed, 770 insertions, 0 deletions
diff --git a/lib/Transforms/IPO/InlineSimple.cpp b/lib/Transforms/IPO/InlineSimple.cpp new file mode 100644 index 0000000000..a1e3156b3b --- /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 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; +} diff --git a/lib/Transforms/Scalar/DCE.cpp b/lib/Transforms/Scalar/DCE.cpp new file mode 100644 index 0000000000..797edf5054 --- /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 0000000000..af5f18f305 --- /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()); +} |