X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FADCE.cpp;h=e2e9e86216cde540bbc4536f86660ad47cb47857;hb=0006bd75201f340b95c1dbf71e50dc5de5ed9425;hp=862ec5a39170242f0676019b46dd082979d8443c;hpb=84369b323e51ced9070659cadb15e2aacb5d0ea5;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp index 862ec5a3917..e2e9e86216c 100644 --- a/lib/Transforms/Scalar/ADCE.cpp +++ b/lib/Transforms/Scalar/ADCE.cpp @@ -8,24 +8,23 @@ #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/StatisticReporter.h" +#include "Support/Statistic.h" #include -#include using std::cerr; - -static Statistic<> NumBlockRemoved("adce\t\t- Number of basic blocks removed"); -static Statistic<> NumInstRemoved ("adce\t\t- Number of instructions removed"); +using std::vector; namespace { + Statistic<> NumBlockRemoved("adce", "Number of basic blocks removed"); + Statistic<> NumInstRemoved ("adce", "Number of instructions removed"); //===----------------------------------------------------------------------===// // ADCE Class @@ -42,12 +41,10 @@ class ADCE : public FunctionPass { // The public interface for this class // public: - const char *getPassName() const { return "Aggressive Dead Code Elimination"; } - // Execute the Aggressive Dead Code Elimination Algorithm // - virtual bool runOnFunction(Function *F) { - Func = F; + virtual bool runOnFunction(Function &F) { + Func = &F; bool Changed = doADCE(); assert(WorkList.empty()); LiveSet.clear(); @@ -56,8 +53,8 @@ public: // getAnalysisUsage - We require post dominance frontiers (aka Control // Dependence Graph) virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(DominatorTree::PostDomID); - AU.addRequired(DominanceFrontier::PostDomID); + AU.addRequired(); + AU.addRequired(); } @@ -72,6 +69,12 @@ private: 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; DEBUG(cerr << "Insn Live: " << I); @@ -85,22 +88,21 @@ private: } }; + RegisterOpt X("adce", "Aggressive Dead Code Elimination"); } // End of anonymous namespace 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... // - DominanceFrontier &CDG = - getAnalysis(DominanceFrontier::PostDomID); + PostDominanceFrontier &CDG = getAnalysis(); - DominanceFrontier::const_iterator It = CDG.find(BB); + PostDominanceFrontier::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; + const PostDominanceFrontier::DomSetType &CDB = It->second; for_each(CDB.begin(), CDB.end(), // Mark all their terminators as live bind_obj(this, &ADCE::markTerminatorLive)); } @@ -109,6 +111,32 @@ void ADCE::markBlockAlive(BasicBlock *BB) { 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. @@ -126,14 +154,12 @@ bool ADCE::doADCE() { 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(I)) { + } else if (isInstructionTriviallyDead(II)) { // Remove the instruction from it's basic block... - delete BB->getInstList().remove(II); + II = BB->getInstList().erase(II); ++NumInstRemoved; MadeChanges = true; } else { @@ -185,9 +211,8 @@ bool ADCE::doADCE() { 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 "; + for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE; ++BI){ + if (LiveSet.count(BI)) cerr << "X "; cerr << *BI; } } @@ -195,15 +220,28 @@ bool ADCE::doADCE() { // Find the first postdominator of the entry node that is alive. Make it the // new entry node... // - DominatorTree &DT = getAnalysis(DominatorTree::PostDomID); - - // If there are some blocks dead... - if (AliveBlocks.size() != Func->size()) { - // Insert a new entry node to eliminate the entry node as a special case. - BasicBlock *NewEntry = new BasicBlock(); - NewEntry->getInstList().push_back(new BranchInst(Func->front())); - Func->getBasicBlocks().push_front(NewEntry); - AliveBlocks.insert(NewEntry); // This block is always alive! + 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 @@ -211,45 +249,76 @@ bool ADCE::doADCE() { // the block to reflect this. // for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) - if (AliveBlocks.count(*I)) { - BasicBlock *BB = *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 - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) + // 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... // - DominatorTree::Node *LastNode = DT[TI->getSuccessor(i)]; - DominatorTree::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. + 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. // - 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); + 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); + } } } @@ -258,17 +327,14 @@ bool ADCE::doADCE() { // sweep over the program can safely delete dead instructions without // other dead instructions still refering to them. // - for (BasicBlock::iterator I = BB->begin(), E = BB->end()-1; I != E; ++I) - if (!LiveSet.count(*I)) // Is this instruction alive? - (*I)->dropAllReferences(); // Nope, drop references... + dropReferencesOfDeadInstructionsInLiveBlock(BB); } } // Loop over all of the basic blocks in the function, dropping references of // the dead basic blocks // - for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) { - BasicBlock *BB = *I; + 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. @@ -283,11 +349,10 @@ bool ADCE::doADCE() { } // Delete the old terminator instruction... - delete BB->getInstList().remove(BB->end()-1); + BB->getInstList().pop_back(); const Type *RetTy = Func->getReturnType(); - Instruction *New = new ReturnInst(RetTy != Type::VoidTy ? - Constant::getNullValue(RetTy) : 0); - BB->getInstList().push_back(New); + BB->getInstList().push_back(new ReturnInst(RetTy != Type::VoidTy ? + Constant::getNullValue(RetTy) : 0)); } BB->dropAllReferences(); @@ -302,14 +367,13 @@ bool ADCE::doADCE() { // instructions from alive blocks. // for (Function::iterator BI = Func->begin(); BI != Func->end(); ) - if (!AliveBlocks.count(*BI)) - delete Func->getBasicBlocks().remove(BI); - else { - BasicBlock *BB = *BI; - for (BasicBlock::iterator II = BB->begin(); II != BB->end()-1; ) - if (!LiveSet.count(*II)) { // Is this instruction alive? + 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... - delete BB->getInstList().remove(II); + II = BI->getInstList().erase(II); ++NumInstRemoved; MadeChanges = true; } else {