X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FADCE.cpp;h=e2e9e86216cde540bbc4536f86660ad47cb47857;hb=0006bd75201f340b95c1dbf71e50dc5de5ed9425;hp=06301971f73faaf618646cd6bfd1306a41fea18d;hpb=a59cbb2043c08f3cfb8fb379f0d336e21e070be8;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp index 06301971f73..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/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; using std::vector; -static Statistic<> NumBlockRemoved("adce\t\t- Number of basic blocks removed"); -static Statistic<> NumInstRemoved ("adce\t\t- Number of instructions removed"); - namespace { + Statistic<> NumBlockRemoved("adce", "Number of basic blocks removed"); + Statistic<> NumInstRemoved ("adce", "Number of instructions removed"); //===----------------------------------------------------------------------===// // ADCE Class @@ -54,8 +53,8 @@ public: // getAnalysisUsage - We require post dominance frontiers (aka Control // Dependence Graph) virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(PostDominatorTree::ID); - AU.addRequired(PostDominanceFrontier::ID); + AU.addRequired(); + AU.addRequired(); } @@ -70,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); @@ -106,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. @@ -191,13 +222,26 @@ bool ADCE::doADCE() { // PostDominatorTree &DT = getAnalysis(); - // 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->getBasicBlockList().push_front(NewEntry); - AliveBlocks.insert(NewEntry); // This block is always alive! + + 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 @@ -209,41 +253,72 @@ bool ADCE::doADCE() { 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... // PostDominatorTree::Node *LastNode = DT[TI->getSuccessor(i)]; - 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. + + // 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); + } } } @@ -252,9 +327,7 @@ 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(); I != E; ++I) - if (!LiveSet.count(I)) // Is this instruction alive? - I->dropAllReferences(); // Nope, drop references... + dropReferencesOfDeadInstructionsInLiveBlock(BB); } } @@ -278,9 +351,8 @@ bool ADCE::doADCE() { // Delete the old terminator instruction... 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(); @@ -295,9 +367,9 @@ bool ADCE::doADCE() { // instructions from alive blocks. // for (Function::iterator BI = Func->begin(); BI != Func->end(); ) - if (!AliveBlocks.count(BI)) + if (!AliveBlocks.count(BI)) { // Delete dead blocks... BI = Func->getBasicBlockList().erase(BI); - else { + } 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...