LLVM API Documentation

ADCE.cpp

Go to the documentation of this file.
00001 //===- ADCE.cpp - Code to perform aggressive dead code elimination --------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements "aggressive" dead code elimination.  ADCE is DCe where
00011 // values are assumed to be dead until proven otherwise.  This is similar to
00012 // SCCP, except applied to the liveness of values.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Transforms/Scalar.h"
00017 #include "llvm/Constants.h"
00018 #include "llvm/Instructions.h"
00019 #include "llvm/Analysis/AliasAnalysis.h"
00020 #include "llvm/Analysis/PostDominators.h"
00021 #include "llvm/Support/CFG.h"
00022 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00023 #include "llvm/Transforms/Utils/Local.h"
00024 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
00025 #include "llvm/Support/Debug.h"
00026 #include "llvm/ADT/DepthFirstIterator.h"
00027 #include "llvm/ADT/Statistic.h"
00028 #include "llvm/ADT/STLExtras.h"
00029 #include <algorithm>
00030 #include <iostream>
00031 using namespace llvm;
00032 
00033 namespace {
00034   Statistic<> NumBlockRemoved("adce", "Number of basic blocks removed");
00035   Statistic<> NumInstRemoved ("adce", "Number of instructions removed");
00036   Statistic<> NumCallRemoved ("adce", "Number of calls and invokes removed");
00037 
00038 //===----------------------------------------------------------------------===//
00039 // ADCE Class
00040 //
00041 // This class does all of the work of Aggressive Dead Code Elimination.
00042 // It's public interface consists of a constructor and a doADCE() method.
00043 //
00044 class ADCE : public FunctionPass {
00045   Function *Func;                       // The function that we are working on
00046   std::vector<Instruction*> WorkList;   // Instructions that just became live
00047   std::set<Instruction*>    LiveSet;    // The set of live instructions
00048 
00049   //===--------------------------------------------------------------------===//
00050   // The public interface for this class
00051   //
00052 public:
00053   // Execute the Aggressive Dead Code Elimination Algorithm
00054   //
00055   virtual bool runOnFunction(Function &F) {
00056     Func = &F;
00057     bool Changed = doADCE();
00058     assert(WorkList.empty());
00059     LiveSet.clear();
00060     return Changed;
00061   }
00062   // getAnalysisUsage - We require post dominance frontiers (aka Control
00063   // Dependence Graph)
00064   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00065     // We require that all function nodes are unified, because otherwise code
00066     // can be marked live that wouldn't necessarily be otherwise.
00067     AU.addRequired<UnifyFunctionExitNodes>();
00068     AU.addRequired<AliasAnalysis>();
00069     AU.addRequired<PostDominatorTree>();
00070     AU.addRequired<PostDominanceFrontier>();
00071   }
00072 
00073 
00074   //===--------------------------------------------------------------------===//
00075   // The implementation of this class
00076   //
00077 private:
00078   // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning
00079   // true if the function was modified.
00080   //
00081   bool doADCE();
00082 
00083   void markBlockAlive(BasicBlock *BB);
00084 
00085 
00086   // deleteDeadInstructionsInLiveBlock - Loop over all of the instructions in
00087   // the specified basic block, deleting ones that are dead according to
00088   // LiveSet.
00089   bool deleteDeadInstructionsInLiveBlock(BasicBlock *BB);
00090 
00091   TerminatorInst *convertToUnconditionalBranch(TerminatorInst *TI);
00092 
00093   inline void markInstructionLive(Instruction *I) {
00094     if (!LiveSet.insert(I).second) return;
00095     DEBUG(std::cerr << "Insn Live: " << *I);
00096     WorkList.push_back(I);
00097   }
00098 
00099   inline void markTerminatorLive(const BasicBlock *BB) {
00100     DEBUG(std::cerr << "Terminator Live: " << *BB->getTerminator());
00101     markInstructionLive(const_cast<TerminatorInst*>(BB->getTerminator()));
00102   }
00103 };
00104 
00105   RegisterOpt<ADCE> X("adce", "Aggressive Dead Code Elimination");
00106 } // End of anonymous namespace
00107 
00108 FunctionPass *llvm::createAggressiveDCEPass() { return new ADCE(); }
00109 
00110 void ADCE::markBlockAlive(BasicBlock *BB) {
00111   // Mark the basic block as being newly ALIVE... and mark all branches that
00112   // this block is control dependent on as being alive also...
00113   //
00114   PostDominanceFrontier &CDG = getAnalysis<PostDominanceFrontier>();
00115 
00116   PostDominanceFrontier::const_iterator It = CDG.find(BB);
00117   if (It != CDG.end()) {
00118     // Get the blocks that this node is control dependent on...
00119     const PostDominanceFrontier::DomSetType &CDB = It->second;
00120     for (PostDominanceFrontier::DomSetType::const_iterator I =
00121            CDB.begin(), E = CDB.end(); I != E; ++I)
00122       markTerminatorLive(*I);   // Mark all their terminators as live
00123   }
00124 
00125   // If this basic block is live, and it ends in an unconditional branch, then
00126   // the branch is alive as well...
00127   if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()))
00128     if (BI->isUnconditional())
00129       markTerminatorLive(BB);
00130 }
00131 
00132 // deleteDeadInstructionsInLiveBlock - Loop over all of the instructions in the
00133 // specified basic block, deleting ones that are dead according to LiveSet.
00134 bool ADCE::deleteDeadInstructionsInLiveBlock(BasicBlock *BB) {
00135   bool Changed = false;
00136   for (BasicBlock::iterator II = BB->begin(), E = --BB->end(); II != E; ) {
00137     Instruction *I = II++;
00138     if (!LiveSet.count(I)) {              // Is this instruction alive?
00139       if (!I->use_empty())
00140         I->replaceAllUsesWith(UndefValue::get(I->getType()));
00141 
00142       // Nope... remove the instruction from it's basic block...
00143       if (isa<CallInst>(I))
00144         ++NumCallRemoved;
00145       else
00146         ++NumInstRemoved;
00147       BB->getInstList().erase(I);
00148       Changed = true;
00149     }
00150   }
00151   return Changed;
00152 }
00153 
00154 
00155 /// convertToUnconditionalBranch - Transform this conditional terminator
00156 /// instruction into an unconditional branch because we don't care which of the
00157 /// successors it goes to.  This eliminate a use of the condition as well.
00158 ///
00159 TerminatorInst *ADCE::convertToUnconditionalBranch(TerminatorInst *TI) {
00160   BranchInst *NB = new BranchInst(TI->getSuccessor(0), TI);
00161   BasicBlock *BB = TI->getParent();
00162 
00163   // Remove entries from PHI nodes to avoid confusing ourself later...
00164   for (unsigned i = 1, e = TI->getNumSuccessors(); i != e; ++i)
00165     TI->getSuccessor(i)->removePredecessor(BB);
00166 
00167   // Delete the old branch itself...
00168   BB->getInstList().erase(TI);
00169   return NB;
00170 }
00171 
00172 
00173 // doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning
00174 // true if the function was modified.
00175 //
00176 bool ADCE::doADCE() {
00177   bool MadeChanges = false;
00178 
00179   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
00180 
00181 
00182   // Iterate over all invokes in the function, turning invokes into calls if
00183   // they cannot throw.
00184   for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB)
00185     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
00186       if (Function *F = II->getCalledFunction())
00187         if (AA.onlyReadsMemory(F)) {
00188           // The function cannot unwind.  Convert it to a call with a branch
00189           // after it to the normal destination.
00190           std::vector<Value*> Args(II->op_begin()+3, II->op_end());
00191           std::string Name = II->getName(); II->setName("");
00192           CallInst *NewCall = new CallInst(F, Args, Name, II);
00193           NewCall->setCallingConv(II->getCallingConv());
00194           II->replaceAllUsesWith(NewCall);
00195           new BranchInst(II->getNormalDest(), II);
00196 
00197           // Update PHI nodes in the unwind destination
00198           II->getUnwindDest()->removePredecessor(BB);
00199           BB->getInstList().erase(II);
00200 
00201           if (NewCall->use_empty()) {
00202             BB->getInstList().erase(NewCall);
00203             ++NumCallRemoved;
00204           }
00205         }
00206 
00207   // Iterate over all of the instructions in the function, eliminating trivially
00208   // dead instructions, and marking instructions live that are known to be
00209   // needed.  Perform the walk in depth first order so that we avoid marking any
00210   // instructions live in basic blocks that are unreachable.  These blocks will
00211   // be eliminated later, along with the instructions inside.
00212   //
00213   std::set<BasicBlock*> ReachableBBs;
00214   for (df_ext_iterator<BasicBlock*>
00215          BBI = df_ext_begin(&Func->front(), ReachableBBs),
00216          BBE = df_ext_end(&Func->front(), ReachableBBs); BBI != BBE; ++BBI) {
00217     BasicBlock *BB = *BBI;
00218     for (BasicBlock::iterator II = BB->begin(), EI = BB->end(); II != EI; ) {
00219       Instruction *I = II++;
00220       if (CallInst *CI = dyn_cast<CallInst>(I)) {
00221         Function *F = CI->getCalledFunction();
00222         if (F && AA.onlyReadsMemory(F)) {
00223           if (CI->use_empty()) {
00224             BB->getInstList().erase(CI);
00225             ++NumCallRemoved;
00226           }
00227         } else {
00228           markInstructionLive(I);
00229         }
00230       } else if (I->mayWriteToMemory() || isa<ReturnInst>(I) ||
00231                  isa<UnwindInst>(I) || isa<UnreachableInst>(I)) {
00232         // FIXME: Unreachable instructions should not be marked intrinsically
00233         // live here.
00234         markInstructionLive(I);
00235       } else if (isInstructionTriviallyDead(I)) {
00236         // Remove the instruction from it's basic block...
00237         BB->getInstList().erase(I);
00238         ++NumInstRemoved;
00239       }
00240     }
00241   }
00242 
00243   // Check to ensure we have an exit node for this CFG.  If we don't, we won't
00244   // have any post-dominance information, thus we cannot perform our
00245   // transformations safely.
00246   //
00247   PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
00248   if (DT[&Func->getEntryBlock()] == 0) {
00249     WorkList.clear();
00250     return MadeChanges;
00251   }
00252 
00253   // Scan the function marking blocks without post-dominance information as
00254   // live.  Blocks without post-dominance information occur when there is an
00255   // infinite loop in the program.  Because the infinite loop could contain a
00256   // function which unwinds, exits or has side-effects, we don't want to delete
00257   // the infinite loop or those blocks leading up to it.
00258   for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I)
00259     if (DT[I] == 0 && ReachableBBs.count(I))
00260       for (pred_iterator PI = pred_begin(I), E = pred_end(I); PI != E; ++PI)
00261         markInstructionLive((*PI)->getTerminator());
00262 
00263   DEBUG(std::cerr << "Processing work list\n");
00264 
00265   // AliveBlocks - Set of basic blocks that we know have instructions that are
00266   // alive in them...
00267   //
00268   std::set<BasicBlock*> AliveBlocks;
00269 
00270   // Process the work list of instructions that just became live... if they
00271   // became live, then that means that all of their operands are necessary as
00272   // well... make them live as well.
00273   //
00274   while (!WorkList.empty()) {
00275     Instruction *I = WorkList.back(); // Get an instruction that became live...
00276     WorkList.pop_back();
00277 
00278     BasicBlock *BB = I->getParent();
00279     if (!ReachableBBs.count(BB)) continue;
00280     if (AliveBlocks.insert(BB).second)     // Basic block not alive yet.
00281       markBlockAlive(BB);             // Make it so now!
00282 
00283     // PHI nodes are a special case, because the incoming values are actually
00284     // defined in the predecessor nodes of this block, meaning that the PHI
00285     // makes the predecessors alive.
00286     //
00287     if (PHINode *PN = dyn_cast<PHINode>(I)) {
00288       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00289         // If the incoming edge is clearly dead, it won't have control
00290         // dependence information.  Do not mark it live.
00291         BasicBlock *PredBB = PN->getIncomingBlock(i);
00292         if (ReachableBBs.count(PredBB)) {
00293           // FIXME: This should mark the control dependent edge as live, not
00294           // necessarily the predecessor itself!
00295           if (AliveBlocks.insert(PredBB).second)
00296             markBlockAlive(PN->getIncomingBlock(i));   // Block is newly ALIVE!
00297           if (Instruction *Op = dyn_cast<Instruction>(PN->getIncomingValue(i)))
00298             markInstructionLive(Op);
00299         }
00300       }
00301     } else {
00302       // Loop over all of the operands of the live instruction, making sure that
00303       // they are known to be alive as well.
00304       //
00305       for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op)
00306         if (Instruction *Operand = dyn_cast<Instruction>(I->getOperand(op)))
00307           markInstructionLive(Operand);
00308     }
00309   }
00310 
00311   DEBUG(
00312     std::cerr << "Current Function: X = Live\n";
00313     for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I){
00314       std::cerr << I->getName() << ":\t"
00315                 << (AliveBlocks.count(I) ? "LIVE\n" : "DEAD\n");
00316       for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE; ++BI){
00317         if (LiveSet.count(BI)) std::cerr << "X ";
00318         std::cerr << *BI;
00319       }
00320     });
00321 
00322   // All blocks being live is a common case, handle it specially.
00323   if (AliveBlocks.size() == Func->size()) {  // No dead blocks?
00324     for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) {
00325       // Loop over all of the instructions in the function deleting instructions
00326       // to drop their references.
00327       deleteDeadInstructionsInLiveBlock(I);
00328 
00329       // Check to make sure the terminator instruction is live.  If it isn't,
00330       // this means that the condition that it branches on (we know it is not an
00331       // unconditional branch), is not needed to make the decision of where to
00332       // go to, because all outgoing edges go to the same place.  We must remove
00333       // the use of the condition (because it's probably dead), so we convert
00334       // the terminator to an unconditional branch.
00335       //
00336       TerminatorInst *TI = I->getTerminator();
00337       if (!LiveSet.count(TI))
00338         convertToUnconditionalBranch(TI);
00339     }
00340 
00341     return MadeChanges;
00342   }
00343 
00344 
00345   // If the entry node is dead, insert a new entry node to eliminate the entry
00346   // node as a special case.
00347   //
00348   if (!AliveBlocks.count(&Func->front())) {
00349     BasicBlock *NewEntry = new BasicBlock();
00350     new BranchInst(&Func->front(), NewEntry);
00351     Func->getBasicBlockList().push_front(NewEntry);
00352     AliveBlocks.insert(NewEntry);    // This block is always alive!
00353     LiveSet.insert(NewEntry->getTerminator());  // The branch is live
00354   }
00355 
00356   // Loop over all of the alive blocks in the function.  If any successor
00357   // blocks are not alive, we adjust the outgoing branches to branch to the
00358   // first live postdominator of the live block, adjusting any PHI nodes in
00359   // the block to reflect this.
00360   //
00361   for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I)
00362     if (AliveBlocks.count(I)) {
00363       BasicBlock *BB = I;
00364       TerminatorInst *TI = BB->getTerminator();
00365 
00366       // If the terminator instruction is alive, but the block it is contained
00367       // in IS alive, this means that this terminator is a conditional branch on
00368       // a condition that doesn't matter.  Make it an unconditional branch to
00369       // ONE of the successors.  This has the side effect of dropping a use of
00370       // the conditional value, which may also be dead.
00371       if (!LiveSet.count(TI))
00372         TI = convertToUnconditionalBranch(TI);
00373 
00374       // Loop over all of the successors, looking for ones that are not alive.
00375       // We cannot save the number of successors in the terminator instruction
00376       // here because we may remove them if we don't have a postdominator.
00377       //
00378       for (unsigned i = 0; i != TI->getNumSuccessors(); ++i)
00379         if (!AliveBlocks.count(TI->getSuccessor(i))) {
00380           // Scan up the postdominator tree, looking for the first
00381           // postdominator that is alive, and the last postdominator that is
00382           // dead...
00383           //
00384           PostDominatorTree::Node *LastNode = DT[TI->getSuccessor(i)];
00385           PostDominatorTree::Node *NextNode = 0;
00386 
00387           if (LastNode) {
00388             NextNode = LastNode->getIDom();
00389             while (!AliveBlocks.count(NextNode->getBlock())) {
00390               LastNode = NextNode;
00391               NextNode = NextNode->getIDom();
00392               if (NextNode == 0) {
00393                 LastNode = 0;
00394                 break;
00395               }
00396             }
00397           }
00398 
00399           // There is a special case here... if there IS no post-dominator for
00400           // the block we have nowhere to point our branch to.  Instead, convert
00401           // it to a return.  This can only happen if the code branched into an
00402           // infinite loop.  Note that this may not be desirable, because we
00403           // _are_ altering the behavior of the code.  This is a well known
00404           // drawback of ADCE, so in the future if we choose to revisit the
00405           // decision, this is where it should be.
00406           //
00407           if (LastNode == 0) {        // No postdominator!
00408             if (!isa<InvokeInst>(TI)) {
00409               // Call RemoveSuccessor to transmogrify the terminator instruction
00410               // to not contain the outgoing branch, or to create a new
00411               // terminator if the form fundamentally changes (i.e.,
00412               // unconditional branch to return).  Note that this will change a
00413               // branch into an infinite loop into a return instruction!
00414               //
00415               RemoveSuccessor(TI, i);
00416 
00417               // RemoveSuccessor may replace TI... make sure we have a fresh
00418               // pointer.
00419               //
00420               TI = BB->getTerminator();
00421 
00422               // Rescan this successor...
00423               --i;
00424             } else {
00425 
00426             }
00427           } else {
00428             // Get the basic blocks that we need...
00429             BasicBlock *LastDead = LastNode->getBlock();
00430             BasicBlock *NextAlive = NextNode->getBlock();
00431 
00432             // Make the conditional branch now go to the next alive block...
00433             TI->getSuccessor(i)->removePredecessor(BB);
00434             TI->setSuccessor(i, NextAlive);
00435 
00436             // If there are PHI nodes in NextAlive, we need to add entries to
00437             // the PHI nodes for the new incoming edge.  The incoming values
00438             // should be identical to the incoming values for LastDead.
00439             //
00440             for (BasicBlock::iterator II = NextAlive->begin();
00441                  isa<PHINode>(II); ++II) {
00442               PHINode *PN = cast<PHINode>(II);
00443               if (LiveSet.count(PN)) {  // Only modify live phi nodes
00444                 // Get the incoming value for LastDead...
00445                 int OldIdx = PN->getBasicBlockIndex(LastDead);
00446                 assert(OldIdx != -1 &&"LastDead is not a pred of NextAlive!");
00447                 Value *InVal = PN->getIncomingValue(OldIdx);
00448 
00449                 // Add an incoming value for BB now...
00450                 PN->addIncoming(InVal, BB);
00451               }
00452             }
00453           }
00454         }
00455 
00456       // Now loop over all of the instructions in the basic block, deleting
00457       // dead instructions.  This is so that the next sweep over the program
00458       // can safely delete dead instructions without other dead instructions
00459       // still referring to them.
00460       //
00461       deleteDeadInstructionsInLiveBlock(BB);
00462     }
00463 
00464   // Loop over all of the basic blocks in the function, dropping references of
00465   // the dead basic blocks.  We must do this after the previous step to avoid
00466   // dropping references to PHIs which still have entries...
00467   //
00468   std::vector<BasicBlock*> DeadBlocks;
00469   for (Function::iterator BB = Func->begin(), E = Func->end(); BB != E; ++BB)
00470     if (!AliveBlocks.count(BB)) {
00471       // Remove PHI node entries for this block in live successor blocks.
00472       for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
00473         if (!SI->empty() && isa<PHINode>(SI->front()) && AliveBlocks.count(*SI))
00474           (*SI)->removePredecessor(BB);
00475 
00476       BB->dropAllReferences();
00477       MadeChanges = true;
00478       DeadBlocks.push_back(BB);
00479     }
00480 
00481   NumBlockRemoved += DeadBlocks.size();
00482 
00483   // Now loop through all of the blocks and delete the dead ones.  We can safely
00484   // do this now because we know that there are no references to dead blocks
00485   // (because they have dropped all of their references).
00486   for (std::vector<BasicBlock*>::iterator I = DeadBlocks.begin(),
00487          E = DeadBlocks.end(); I != E; ++I)
00488     Func->getBasicBlockList().erase(*I);
00489 
00490   return MadeChanges;
00491 }