X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FADCE.cpp;h=e2e9e86216cde540bbc4536f86660ad47cb47857;hb=0006bd75201f340b95c1dbf71e50dc5de5ed9425;hp=5a951078609d81ed574edb987c50d7e2f6aa4797;hpb=dfe81ab87aa44e51635b60c964ff6a792dcbc9d3;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp index 5a951078609..e2e9e86216c 100644 --- a/lib/Transforms/Scalar/ADCE.cpp +++ b/lib/Transforms/Scalar/ADCE.cpp @@ -1,59 +1,60 @@ -//===- 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/Transforms/Scalar/DCE.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Type.h" -#include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/Writer.h" +#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 -#include using std::cerr; - -#define DEBUG_ADCE 1 +using std::vector; 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 : 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 - bool MadeChanges; //===--------------------------------------------------------------------===// // The public interface for this class // public: - const char *getPassName() const { return "Aggressive Dead Code Elimination"; } - - // doADCE - Execute the Agressive Dead Code Elimination Algorithm + // Execute the Aggressive Dead Code Elimination Algorithm // - virtual bool runOnFunction(Function *F) { - Func = F; MadeChanges = false; - doADCE(getAnalysis(DominanceFrontier::PostDomID)); + virtual bool runOnFunction(Function &F) { + Func = &F; + bool Changed = doADCE(); assert(WorkList.empty()); LiveSet.clear(); - return MadeChanges; + return Changed; } // getAnalysisUsage - We require post dominance frontiers (aka Control // Dependence Graph) virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(DominanceFrontier::PostDomID); + AU.addRequired(); + AU.addRequired(); } @@ -61,48 +62,87 @@ public: // The implementation of this class // private: - // doADCE() - Run the Agressive Dead Code Elimination algorithm, returning + // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning // true if the function was modified. // - void doADCE(DominanceFrontier &CDG); + 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; -#ifdef DEBUG_ADCE - cerr << "Insn Live: " << I; -#endif + DEBUG(cerr << "Insn Live: " << I); LiveSet.insert(I); WorkList.push_back(I); } inline void markTerminatorLive(const BasicBlock *BB) { -#ifdef DEBUG_ADCE - cerr << "Terminat Live: " << BB->getTerminator(); -#endif + DEBUG(cerr << "Terminat Live: " << BB->getTerminator()); markInstructionLive((Instruction*)BB->getTerminator()); } - - // fixupCFG - Walk the CFG in depth first order, eliminating references to - // dead blocks. - // - BasicBlock *fixupCFG(BasicBlock *Head, std::set &VisitedBlocks, - const std::set &AliveBlocks); }; + RegisterOpt X("adce", "Aggressive Dead Code Elimination"); } // End of anonymous namespace -Pass *createAgressiveDCEPass() { - return new ADCE(); +Pass *createAggressiveDCEPass() { return new ADCE(); } + +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 Agressive Dead Code Elimination algorithm, returning +// doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning // true if the function was modified. // -void ADCE::doADCE(DominanceFrontier &CDG) { -#ifdef DEBUG_ADCE - cerr << "Function: " << Func; -#endif +bool ADCE::doADCE() { + 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 @@ -114,27 +154,21 @@ void ADCE::doADCE(DominanceFrontier &CDG) { BBI != BBE; ++BBI) { BasicBlock *BB = *BBI; for (BasicBlock::iterator II = BB->begin(), EI = BB->end(); II != EI; ) { - Instruction *I = *II; - - if (I->hasSideEffects() || I->getOpcode() == Instruction::Ret) { - markInstructionLive(I); + 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 { - // Check to see if anything is trivially dead - if (I->use_size() == 0 && I->getType() != Type::VoidTy) { - // Remove the instruction from it's basic block... - delete BB->getInstList().remove(II); - MadeChanges = true; - continue; // Don't increment the iterator past the current slot - } + ++II; // Increment the inst iterator if the inst wasn't deleted } - - ++II; // Increment the inst iterator if the inst wasn't deleted } } -#ifdef DEBUG_ADCE - cerr << "Processing work list\n"; -#endif + DEBUG(cerr << "Processing work list\n"); // AliveBlocks - Set of basic blocks that we know have instructions that are // alive in them... @@ -150,160 +184,204 @@ void ADCE::doADCE(DominanceFrontier &CDG) { WorkList.pop_back(); BasicBlock *BB = I->getParent(); - if (AliveBlocks.count(BB) == 0) { // Basic block not alive yet... - // Mark the basic block as being newly ALIVE... and mark all branches that - // this block is control dependant on as being alive also... - // - AliveBlocks.insert(BB); // Block is now ALIVE! - DominanceFrontier::const_iterator It = CDG.find(BB); - if (It != CDG.end()) { - // Get the blocks that this node is control dependant on... - const DominanceFrontier::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); + 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) { + for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op) if (Instruction *Operand = dyn_cast(I->getOperand(op))) markInstructionLive(Operand); - } } -#ifdef DEBUG_ADCE - 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; - } -#endif - - // After the worklist is processed, recursively walk the CFG in depth first - // order, patching up references to dead blocks... - // - std::set VisitedBlocks; - BasicBlock *EntryBlock = fixupCFG(Func->front(), VisitedBlocks, AliveBlocks); - if (EntryBlock && EntryBlock != Func->front()) { - if (isa(EntryBlock->front())) { - // Cannot make the first block be a block with a PHI node in it! Instead, - // strip the first basic block of the function to contain no instructions, - // then add a simple branch to the "real" entry node... - // - BasicBlock *E = Func->front(); - if (!isa(E->front()) || // Check for an actual change... - cast(E->front())->getNumSuccessors() != 1 || - cast(E->front())->getSuccessor(0) != EntryBlock) { - E->getInstList().delete_all(); // Delete all instructions in block - E->getInstList().push_back(new BranchInst(EntryBlock)); - MadeChanges = true; + 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; } - AliveBlocks.insert(E); + } - // Next we need to change any PHI nodes in the entry block to refer to the - // new predecessor node... + // Find the first postdominator of the entry node that is alive. Make it the + // new entry node... + // + PostDominatorTree &DT = getAnalysis(); - } else { - // We need to move the new entry block to be the first bb of the function - Function::iterator EBI = find(Func->begin(), Func->end(), EntryBlock); - std::swap(*EBI, *Func->begin()); // Exchange old location with start of fn - MadeChanges = true; + 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); + + // 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); + } } - // Now go through and tell dead blocks to drop all of their references so they - // can be safely deleted. + // Loop over all of the basic blocks in the function, dropping references of + // the dead basic blocks // - for (Function::iterator BI = Func->begin(), BE = Func->end(); BI != BE; ++BI){ - BasicBlock *BB = *BI; + for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB) { if (!AliveBlocks.count(BB)) { - BB->dropAllReferences(); - } - } + // 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)); + } - // Now loop through all of the blocks and delete them. 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... - // - for (Function::iterator BI = Func->begin(); BI != Func->end();) { - if (!AliveBlocks.count(*BI)) { - delete Func->getBasicBlocks().remove(BI); + BB->dropAllReferences(); + ++NumBlockRemoved; MadeChanges = true; - continue; // Don't increment iterator } - ++BI; // Increment iterator... } -} - -// fixupCFG - Walk the CFG in depth first order, eliminating references to -// dead blocks: -// If the BB is alive (in AliveBlocks): -// 1. Eliminate all dead instructions in the BB -// 2. Recursively traverse all of the successors of the BB: -// - If the returned successor is non-null, update our terminator to -// reference the returned BB -// 3. Return 0 (no update needed) -// -// If the BB is dead (not in AliveBlocks): -// 1. Add the BB to the dead set -// 2. Recursively traverse all of the successors of the block: -// - Only one shall return a nonnull value (or else this block should have -// been in the alive set). -// 3. Return the nonnull child, or 0 if no non-null children. -// -BasicBlock *ADCE::fixupCFG(BasicBlock *BB, std::set &VisitedBlocks, - const std::set &AliveBlocks) { - if (VisitedBlocks.count(BB)) return 0; // Revisiting a node? No update. - VisitedBlocks.insert(BB); // We have now visited this node! - -#ifdef DEBUG_ADCE - cerr << "Fixing up BB: " << BB; -#endif - - if (AliveBlocks.count(BB)) { // Is the block alive? - // Yes it's alive: loop through and eliminate all dead instructions in block - for (BasicBlock::iterator II = BB->begin(); II != BB->end()-1; ) { - Instruction *I = *II; - if (!LiveSet.count(I)) { // Is this instruction alive? - // Nope... remove the instruction from it's basic block... - delete BB->getInstList().remove(II); - MadeChanges = true; - continue; // Don't increment II - } - ++II; + // 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... } - // Recursively traverse successors of this basic block. - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) { - BasicBlock *Succ = *SI; - BasicBlock *Repl = fixupCFG(Succ, VisitedBlocks, AliveBlocks); - if (Repl && Repl != Succ) { // We have to replace the successor - Succ->replaceAllUsesWith(Repl); - MadeChanges = true; - } - } - return BB; - } else { // Otherwise the block is dead... - BasicBlock *ReturnBB = 0; // Default to nothing live down here - - // Recursively traverse successors of this basic block. - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) { - BasicBlock *RetBB = fixupCFG(*SI, VisitedBlocks, AliveBlocks); - if (RetBB) { - assert(ReturnBB == 0 && "One one live child allowed!"); - ReturnBB = RetBB; - } - } - return ReturnBB; // Return the result of traversal - } + return MadeChanges; } -