LLVM API Documentation

PruneEH.cpp

Go to the documentation of this file.
00001 //===- PruneEH.cpp - Pass which deletes unused exception handlers ---------===//
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 a simple interprocedural pass which walks the
00011 // call-graph, turning invoke instructions into calls, iff the callee cannot
00012 // throw an exception.  It implements this as a bottom-up traversal of the
00013 // call-graph.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #include "llvm/Transforms/IPO.h"
00018 #include "llvm/CallGraphSCCPass.h"
00019 #include "llvm/Constants.h"
00020 #include "llvm/Function.h"
00021 #include "llvm/Intrinsics.h"
00022 #include "llvm/Instructions.h"
00023 #include "llvm/Analysis/CallGraph.h"
00024 #include "llvm/ADT/Statistic.h"
00025 #include "llvm/Support/CFG.h"
00026 #include <set>
00027 #include <algorithm>
00028 using namespace llvm;
00029 
00030 namespace {
00031   Statistic<> NumRemoved("prune-eh", "Number of invokes removed");
00032   Statistic<> NumUnreach("prune-eh", "Number of noreturn calls optimized");
00033 
00034   struct PruneEH : public CallGraphSCCPass {
00035     /// DoesNotUnwind - This set contains all of the functions which we have
00036     /// determined cannot unwind.
00037     std::set<CallGraphNode*> DoesNotUnwind;
00038 
00039     /// DoesNotReturn - This set contains all of the functions which we have
00040     /// determined cannot return normally (but might unwind).
00041     std::set<CallGraphNode*> DoesNotReturn;
00042 
00043     // runOnSCC - Analyze the SCC, performing the transformation if possible.
00044     bool runOnSCC(const std::vector<CallGraphNode *> &SCC);
00045 
00046     bool SimplifyFunction(Function *F);
00047     void DeleteBasicBlock(BasicBlock *BB);
00048   };
00049   RegisterOpt<PruneEH> X("prune-eh", "Remove unused exception handling info");
00050 }
00051 
00052 ModulePass *llvm::createPruneEHPass() { return new PruneEH(); }
00053 
00054 
00055 bool PruneEH::runOnSCC(const std::vector<CallGraphNode *> &SCC) {
00056   CallGraph &CG = getAnalysis<CallGraph>();
00057   bool MadeChange = false;
00058 
00059   // First pass, scan all of the functions in the SCC, simplifying them
00060   // according to what we know.
00061   for (unsigned i = 0, e = SCC.size(); i != e; ++i)
00062     if (Function *F = SCC[i]->getFunction())
00063       MadeChange |= SimplifyFunction(F);
00064 
00065   // Next, check to see if any callees might throw or if there are any external
00066   // functions in this SCC: if so, we cannot prune any functions in this SCC.
00067   // If this SCC includes the unwind instruction, we KNOW it throws, so
00068   // obviously the SCC might throw.
00069   //
00070   bool SCCMightUnwind = false, SCCMightReturn = false;
00071   for (unsigned i = 0, e = SCC.size();
00072        (!SCCMightUnwind || !SCCMightReturn) && i != e; ++i) {
00073     Function *F = SCC[i]->getFunction();
00074     if (F == 0 || (F->isExternal() && !F->getIntrinsicID())) {
00075       SCCMightUnwind = true;
00076       SCCMightReturn = true;
00077     } else {
00078       if (F->isExternal())
00079         SCCMightReturn = true;
00080 
00081       // Check to see if this function performs an unwind or calls an
00082       // unwinding function.
00083       for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
00084         if (isa<UnwindInst>(BB->getTerminator())) {  // Uses unwind!
00085           SCCMightUnwind = true;
00086         } else if (isa<ReturnInst>(BB->getTerminator())) {
00087           SCCMightReturn = true;
00088         }
00089 
00090         // Invoke instructions don't allow unwinding to continue, so we are
00091         // only interested in call instructions.
00092         if (!SCCMightUnwind)
00093           for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
00094             if (CallInst *CI = dyn_cast<CallInst>(I)) {
00095               if (Function *Callee = CI->getCalledFunction()) {
00096                 CallGraphNode *CalleeNode = CG[Callee];
00097                 // If the callee is outside our current SCC, or if it is not
00098                 // known to throw, then we might throw also.
00099                 if (std::find(SCC.begin(), SCC.end(), CalleeNode) == SCC.end()&&
00100                     !DoesNotUnwind.count(CalleeNode)) {
00101                   SCCMightUnwind = true;
00102                   break;
00103                 }
00104               } else {
00105                 // Indirect call, it might throw.
00106                 SCCMightUnwind = true;
00107                 break;
00108               }
00109             }
00110         if (SCCMightUnwind && SCCMightReturn) break;
00111       }
00112     }
00113   }
00114 
00115   // If the SCC doesn't unwind or doesn't throw, note this fact.
00116   if (!SCCMightUnwind)
00117     for (unsigned i = 0, e = SCC.size(); i != e; ++i)
00118       DoesNotUnwind.insert(SCC[i]);
00119   if (!SCCMightReturn)
00120     for (unsigned i = 0, e = SCC.size(); i != e; ++i)
00121       DoesNotReturn.insert(SCC[i]);
00122 
00123   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
00124     // Convert any invoke instructions to non-throwing functions in this node
00125     // into call instructions with a branch.  This makes the exception blocks
00126     // dead.
00127     if (Function *F = SCC[i]->getFunction())
00128       MadeChange |= SimplifyFunction(F);
00129   }
00130 
00131   return MadeChange;
00132 }
00133 
00134 
00135 // SimplifyFunction - Given information about callees, simplify the specified
00136 // function if we have invokes to non-unwinding functions or code after calls to
00137 // no-return functions.
00138 bool PruneEH::SimplifyFunction(Function *F) {
00139   CallGraph &CG = getAnalysis<CallGraph>();
00140   bool MadeChange = false;
00141   for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
00142     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
00143       if (Function *F = II->getCalledFunction())
00144         if (DoesNotUnwind.count(CG[F])) {
00145           // Insert a call instruction before the invoke...
00146           std::string Name = II->getName();  II->setName("");
00147           CallInst *Call = new CallInst(II->getCalledValue(),
00148                                         std::vector<Value*>(II->op_begin()+3,
00149                                                             II->op_end()),
00150                                         Name, II);
00151           Call->setCallingConv(II->getCallingConv());
00152 
00153           // Anything that used the value produced by the invoke instruction
00154           // now uses the value produced by the call instruction.
00155           II->replaceAllUsesWith(Call);
00156           BasicBlock *UnwindBlock = II->getUnwindDest();
00157           UnwindBlock->removePredecessor(II->getParent());
00158 
00159           // Insert a branch to the normal destination right before the
00160           // invoke.
00161           new BranchInst(II->getNormalDest(), II);
00162 
00163           // Finally, delete the invoke instruction!
00164           BB->getInstList().pop_back();
00165 
00166           // If the unwind block is now dead, nuke it.
00167           if (pred_begin(UnwindBlock) == pred_end(UnwindBlock))
00168             DeleteBasicBlock(UnwindBlock);  // Delete the new BB.
00169 
00170           ++NumRemoved;
00171           MadeChange = true;
00172         }
00173 
00174     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
00175       if (CallInst *CI = dyn_cast<CallInst>(I++))
00176         if (Function *Callee = CI->getCalledFunction())
00177           if (DoesNotReturn.count(CG[Callee]) && !isa<UnreachableInst>(I)) {
00178             // This call calls a function that cannot return.  Insert an
00179             // unreachable instruction after it and simplify the code.  Do this
00180             // by splitting the BB, adding the unreachable, then deleting the
00181             // new BB.
00182             BasicBlock *New = BB->splitBasicBlock(I);
00183 
00184             // Remove the uncond branch and add an unreachable.
00185             BB->getInstList().pop_back();
00186             new UnreachableInst(BB);
00187 
00188             DeleteBasicBlock(New);  // Delete the new BB.
00189             MadeChange = true;
00190             ++NumUnreach;
00191             break;
00192           }
00193 
00194   }
00195   return MadeChange;
00196 }
00197 
00198 /// DeleteBasicBlock - remove the specified basic block from the program,
00199 /// updating the callgraph to reflect any now-obsolete edges due to calls that
00200 /// exist in the BB.
00201 void PruneEH::DeleteBasicBlock(BasicBlock *BB) {
00202   assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!");
00203   CallGraph &CG = getAnalysis<CallGraph>();
00204 
00205   CallGraphNode *CGN = CG[BB->getParent()];
00206   for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
00207     --I;
00208     if (CallInst *CI = dyn_cast<CallInst>(I)) {
00209       if (Function *Callee = CI->getCalledFunction())
00210         CGN->removeCallEdgeTo(CG[Callee]);
00211     } else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
00212       if (Function *Callee = II->getCalledFunction())
00213         CGN->removeCallEdgeTo(CG[Callee]);
00214     }
00215     if (!I->use_empty())
00216       I->replaceAllUsesWith(UndefValue::get(I->getType()));
00217   }
00218 
00219   // Get the list of successors of this block.
00220   std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));
00221 
00222   for (unsigned i = 0, e = Succs.size(); i != e; ++i)
00223     Succs[i]->removePredecessor(BB);
00224 
00225   BB->eraseFromParent();
00226 }