X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FADCE.cpp;h=e2e9e86216cde540bbc4536f86660ad47cb47857;hb=0006bd75201f340b95c1dbf71e50dc5de5ed9425;hp=add18d581964ebc862e8bf8ca90458ad9eed8dac;hpb=02e90d59c8aa99c2c921a7f82a5fc9019efb98e6;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp index add18d58196..e2e9e86216c 100644 --- a/lib/Transforms/Scalar/ADCE.cpp +++ b/lib/Transforms/Scalar/ADCE.cpp @@ -1,126 +1,387 @@ -//===- ADCE.cpp - Code to perform agressive dead code elimination ---------===// +//===- ADCE.cpp - Code to perform aggressive dead code elimination --------===// // -// This file implements "agressive" dead code elimination. ADCE is DCe where +// This file implements "aggressive" dead code elimination. ADCE is DCe where // values are assumed to be dead until proven otherwise. This is similar to // SCCP, except applied to the liveness of values. // //===----------------------------------------------------------------------===// -#include "llvm/Optimizations/DCE.h" -#include "llvm/Instruction.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Type.h" -#include +#include "llvm/Analysis/PostDominators.h" +#include "llvm/iTerminators.h" +#include "llvm/iPHINode.h" +#include "llvm/Constant.h" +#include "llvm/Support/CFG.h" +#include "Support/STLExtras.h" +#include "Support/DepthFirstIterator.h" +#include "Support/Statistic.h" +#include +using std::cerr; +using std::vector; -#include "llvm/Assembly/Writer.h" +namespace { + Statistic<> NumBlockRemoved("adce", "Number of basic blocks removed"); + Statistic<> NumInstRemoved ("adce", "Number of instructions removed"); //===----------------------------------------------------------------------===// // ADCE Class // -// This class does all of the work of Agressive Dead Code Elimination. +// This class does all of the work of Aggressive Dead Code Elimination. // It's public interface consists of a constructor and a doADCE() method. // -class ADCE { - Method *M; // The method that we are working on... - vector WorkList; // Instructions that just became live - set LiveSet; // The set of live instructions +class ADCE : public FunctionPass { + Function *Func; // The function that we are working on + std::vector WorkList; // Instructions that just became live + std::set LiveSet; // The set of live instructions //===--------------------------------------------------------------------===// // The public interface for this class // public: - // ADCE Ctor - Save the method to operate on... - inline ADCE(Method *m) : M(m) {} + // Execute the Aggressive Dead Code Elimination Algorithm + // + virtual bool runOnFunction(Function &F) { + Func = &F; + bool Changed = doADCE(); + assert(WorkList.empty()); + LiveSet.clear(); + return Changed; + } + // getAnalysisUsage - We require post dominance frontiers (aka Control + // Dependence Graph) + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.addRequired(); + } - // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning - // true if the method was modified. - bool doADCE(); //===--------------------------------------------------------------------===// // The implementation of this class // private: + // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning + // true if the function was modified. + // + bool doADCE(); + + void markBlockAlive(BasicBlock *BB); + + + // dropReferencesOfDeadInstructionsInLiveBlock - Loop over all of the + // instructions in the specified basic block, dropping references on + // instructions that are dead according to LiveSet. + bool dropReferencesOfDeadInstructionsInLiveBlock(BasicBlock *BB); + inline void markInstructionLive(Instruction *I) { if (LiveSet.count(I)) return; - cerr << "Insn Live: " << I; + DEBUG(cerr << "Insn Live: " << I); LiveSet.insert(I); WorkList.push_back(I); } - + inline void markTerminatorLive(const BasicBlock *BB) { + DEBUG(cerr << "Terminat Live: " << BB->getTerminator()); + markInstructionLive((Instruction*)BB->getTerminator()); + } }; + RegisterOpt X("adce", "Aggressive Dead Code Elimination"); +} // End of anonymous namespace +Pass *createAggressiveDCEPass() { return new ADCE(); } -// doADCE() - Run the Agressive Dead Code Elimination algorithm, returning -// true if the method was modified. +void ADCE::markBlockAlive(BasicBlock *BB) { + // Mark the basic block as being newly ALIVE... and mark all branches that + // this block is control dependant on as being alive also... + // + PostDominanceFrontier &CDG = getAnalysis(); + + PostDominanceFrontier::const_iterator It = CDG.find(BB); + if (It != CDG.end()) { + // Get the blocks that this node is control dependant on... + const PostDominanceFrontier::DomSetType &CDB = It->second; + for_each(CDB.begin(), CDB.end(), // Mark all their terminators as live + bind_obj(this, &ADCE::markTerminatorLive)); + } + + // If this basic block is live, then the terminator must be as well! + markTerminatorLive(BB); +} + +// dropReferencesOfDeadInstructionsInLiveBlock - Loop over all of the +// instructions in the specified basic block, dropping references on +// instructions that are dead according to LiveSet. +bool ADCE::dropReferencesOfDeadInstructionsInLiveBlock(BasicBlock *BB) { + bool Changed = false; + for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ) + if (!LiveSet.count(I)) { // Is this instruction alive? + I->dropAllReferences(); // Nope, drop references... + if (PHINode *PN = dyn_cast(&*I)) { + // We don't want to leave PHI nodes in the program that have + // #arguments != #predecessors, so we remove them now. + // + PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); + + // Delete the instruction... + I = BB->getInstList().erase(I); + Changed = true; + } else { + ++I; + } + } else { + ++I; + } + return Changed; +} + + +// doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning +// true if the function was modified. // bool ADCE::doADCE() { - // Iterate over all of the instructions in the method, eliminating trivially + bool MadeChanges = false; + + // Iterate over all of the instructions in the function, eliminating trivially // dead instructions, and marking instructions live that are known to be - // needed. + // needed. Perform the walk in depth first order so that we avoid marking any + // instructions live in basic blocks that are unreachable. These blocks will + // be eliminated later, along with the instructions inside. // - for (Method::inst_iterator II = M->inst_begin(); II != M->inst_end(); ) { - Instruction *I = *II; - switch (I->getInstType()) { - case Instruction::Call: - case Instruction::Store: - markInstructionLive(I); - break; - default: - if (I->getType() == Type::VoidTy) { - markInstructionLive(I); // Catches terminators and friends + for (df_iterator BBI = df_begin(Func), BBE = df_end(Func); + BBI != BBE; ++BBI) { + BasicBlock *BB = *BBI; + for (BasicBlock::iterator II = BB->begin(), EI = BB->end(); II != EI; ) { + if (II->hasSideEffects() || II->getOpcode() == Instruction::Ret) { + markInstructionLive(II); + ++II; // Increment the inst iterator if the inst wasn't deleted + } else if (isInstructionTriviallyDead(II)) { + // Remove the instruction from it's basic block... + II = BB->getInstList().erase(II); + ++NumInstRemoved; + MadeChanges = true; } else { - if (I->use_size() == 0) { // Check to see if anything is trivially dead - // Remove the instruction from it's basic block... - BasicBlock *BB = I->getParent(); - delete BB->getInstList().remove(II.getInstructionIterator()); - - // Make sure to sync up the iterator again... - II.resyncInstructionIterator(); - continue; // Don't increment the iterator past the current slot - } + ++II; // Increment the inst iterator if the inst wasn't deleted } } - - ++II; // Increment the iterator } + DEBUG(cerr << "Processing work list\n"); - cerr << "Processing work list\n"; + // AliveBlocks - Set of basic blocks that we know have instructions that are + // alive in them... + // + std::set AliveBlocks; // Process the work list of instructions that just became live... if they // became live, then that means that all of their operands are neccesary as // well... make them live as well. // while (!WorkList.empty()) { - Instruction *I = WorkList.back(); + Instruction *I = WorkList.back(); // Get an instruction that became live... WorkList.pop_back(); - for (unsigned op = 0; Value *Op = I->getOperand(op); ++op) { - Instruction *Operand = Op->castInstruction(); - if (Operand) markInstructionLive(Operand); + BasicBlock *BB = I->getParent(); + if (!AliveBlocks.count(BB)) { // Basic block not alive yet... + AliveBlocks.insert(BB); // Block is now ALIVE! + markBlockAlive(BB); // Make it so now! } + + // PHI nodes are a special case, because the incoming values are actually + // defined in the predecessor nodes of this block, meaning that the PHI + // makes the predecessors alive. + // + if (PHINode *PN = dyn_cast(I)) + for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) + if (!AliveBlocks.count(*PI)) { + AliveBlocks.insert(BB); // Block is now ALIVE! + markBlockAlive(*PI); + } + + // Loop over all of the operands of the live instruction, making sure that + // they are known to be alive as well... + // + for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op) + if (Instruction *Operand = dyn_cast(I->getOperand(op))) + markInstructionLive(Operand); } - // After the worklist is processed, loop through the instructions again, - // removing any that are not live... by the definition of the LiveSet. + if (DebugFlag) { + cerr << "Current Function: X = Live\n"; + for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) + for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE; ++BI){ + if (LiveSet.count(BI)) cerr << "X "; + cerr << *BI; + } + } + + // Find the first postdominator of the entry node that is alive. Make it the + // new entry node... // - for (Method::inst_iterator II = M->inst_begin(); II != M->inst_end(); ) { - Instruction *I = *II; - if (!LiveSet.count(I)) { - cerr << "Instruction Dead: " << I; + PostDominatorTree &DT = getAnalysis(); + + + if (AliveBlocks.size() == Func->size()) { // No dead blocks? + for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) + // Loop over all of the instructions in the function, telling dead + // instructions to drop their references. This is so that the next sweep + // over the program can safely delete dead instructions without other dead + // instructions still refering to them. + // + dropReferencesOfDeadInstructionsInLiveBlock(I); + + } else { // If there are some blocks dead... + // If the entry node is dead, insert a new entry node to eliminate the entry + // node as a special case. + // + if (!AliveBlocks.count(&Func->front())) { + BasicBlock *NewEntry = new BasicBlock(); + NewEntry->getInstList().push_back(new BranchInst(&Func->front())); + Func->getBasicBlockList().push_front(NewEntry); + AliveBlocks.insert(NewEntry); // This block is always alive! } + + // Loop over all of the alive blocks in the function. If any successor + // blocks are not alive, we adjust the outgoing branches to branch to the + // first live postdominator of the live block, adjusting any PHI nodes in + // the block to reflect this. + // + for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) + if (AliveBlocks.count(I)) { + BasicBlock *BB = I; + TerminatorInst *TI = BB->getTerminator(); + + // Loop over all of the successors, looking for ones that are not alive. + // We cannot save the number of successors in the terminator instruction + // here because we may remove them if we don't have a postdominator... + // + for (unsigned i = 0; i != TI->getNumSuccessors(); ++i) + if (!AliveBlocks.count(TI->getSuccessor(i))) { + // Scan up the postdominator tree, looking for the first + // postdominator that is alive, and the last postdominator that is + // dead... + // + PostDominatorTree::Node *LastNode = DT[TI->getSuccessor(i)]; + + // There is a special case here... if there IS no post-dominator for + // the block we have no owhere to point our branch to. Instead, + // convert it to a return. This can only happen if the code + // branched into an infinite loop. Note that this may not be + // desirable, because we _are_ altering the behavior of the code. + // This is a well known drawback of ADCE, so in the future if we + // choose to revisit the decision, this is where it should be. + // + if (LastNode == 0) { // No postdominator! + // Call RemoveSuccessor to transmogrify the terminator instruction + // to not contain the outgoing branch, or to create a new + // terminator if the form fundementally changes (ie unconditional + // branch to return). Note that this will change a branch into an + // infinite loop into a return instruction! + // + RemoveSuccessor(TI, i); + + // RemoveSuccessor may replace TI... make sure we have a fresh + // pointer... and e variable. + // + TI = BB->getTerminator(); + + // Rescan this successor... + --i; + } else { + PostDominatorTree::Node *NextNode = LastNode->getIDom(); + + while (!AliveBlocks.count(NextNode->getNode())) { + LastNode = NextNode; + NextNode = NextNode->getIDom(); + } + + // Get the basic blocks that we need... + BasicBlock *LastDead = LastNode->getNode(); + BasicBlock *NextAlive = NextNode->getNode(); + + // Make the conditional branch now go to the next alive block... + TI->getSuccessor(i)->removePredecessor(BB); + TI->setSuccessor(i, NextAlive); - ++II; // Increment the iterator + // If there are PHI nodes in NextAlive, we need to add entries to + // the PHI nodes for the new incoming edge. The incoming values + // should be identical to the incoming values for LastDead. + // + for (BasicBlock::iterator II = NextAlive->begin(); + PHINode *PN = dyn_cast(&*II); ++II) { + // Get the incoming value for LastDead... + int OldIdx = PN->getBasicBlockIndex(LastDead); + assert(OldIdx != -1 && "LastDead is not a pred of NextAlive!"); + Value *InVal = PN->getIncomingValue(OldIdx); + + // Add an incoming value for BB now... + PN->addIncoming(InVal, BB); + } + } + } + + // Now loop over all of the instructions in the basic block, telling + // dead instructions to drop their references. This is so that the next + // sweep over the program can safely delete dead instructions without + // other dead instructions still refering to them. + // + dropReferencesOfDeadInstructionsInLiveBlock(BB); + } } - return false; -} + // Loop over all of the basic blocks in the function, dropping references of + // the dead basic blocks + // + for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB) { + if (!AliveBlocks.count(BB)) { + // Remove all outgoing edges from this basic block and convert the + // terminator into a return instruction. + vector Succs(succ_begin(BB), succ_end(BB)); + + if (!Succs.empty()) { + // Loop over all of the successors, removing this block from PHI node + // entries that might be in the block... + while (!Succs.empty()) { + Succs.back()->removePredecessor(BB); + Succs.pop_back(); + } + + // Delete the old terminator instruction... + BB->getInstList().pop_back(); + const Type *RetTy = Func->getReturnType(); + BB->getInstList().push_back(new ReturnInst(RetTy != Type::VoidTy ? + Constant::getNullValue(RetTy) : 0)); + } + + BB->dropAllReferences(); + ++NumBlockRemoved; + MadeChanges = true; + } + } + + // Now loop through all of the blocks and delete the dead ones. We can safely + // do this now because we know that there are no references to dead blocks + // (because they have dropped all of their references... we also remove dead + // instructions from alive blocks. + // + for (Function::iterator BI = Func->begin(); BI != Func->end(); ) + if (!AliveBlocks.count(BI)) { // Delete dead blocks... + BI = Func->getBasicBlockList().erase(BI); + } else { // Scan alive blocks... + for (BasicBlock::iterator II = BI->begin(); II != --BI->end(); ) + if (!LiveSet.count(II)) { // Is this instruction alive? + // Nope... remove the instruction from it's basic block... + II = BI->getInstList().erase(II); + ++NumInstRemoved; + MadeChanges = true; + } else { + ++II; + } + ++BI; // Increment iterator... + } -// DoADCE - Execute the Agressive Dead Code Elimination Algorithm -// -bool opt::DoADCE(Method *M) { - ADCE DCE(M); - return DCE.doADCE(); + return MadeChanges; }