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 is distributed under the University of Illinois Open Source
00006 // 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, and marking functions 'nounwind' if they cannot throw.
00013 // It implements this as a bottom-up traversal of the call-graph.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #define DEBUG_TYPE "prune-eh"
00018 #include "llvm/Transforms/IPO.h"
00019 #include "llvm/CallGraphSCCPass.h"
00020 #include "llvm/Constants.h"
00021 #include "llvm/Function.h"
00022 #include "llvm/LLVMContext.h"
00023 #include "llvm/Instructions.h"
00024 #include "llvm/IntrinsicInst.h"
00025 #include "llvm/Analysis/CallGraph.h"
00026 #include "llvm/ADT/SmallPtrSet.h"
00027 #include "llvm/ADT/SmallVector.h"
00028 #include "llvm/ADT/Statistic.h"
00029 #include "llvm/Support/CFG.h"
00030 #include "llvm/Support/Compiler.h"
00031 #include <set>
00032 #include <algorithm>
00033 using namespace llvm;
00034 
00035 STATISTIC(NumRemoved, "Number of invokes removed");
00036 STATISTIC(NumUnreach, "Number of noreturn calls optimized");
00037 
00038 namespace {
00039   struct VISIBILITY_HIDDEN PruneEH : public CallGraphSCCPass {
00040     static char ID; // Pass identification, replacement for typeid
00041     PruneEH() : CallGraphSCCPass(&ID) {}
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 }
00050 
00051 char PruneEH::ID = 0;
00052 static RegisterPass<PruneEH>
00053 X("prune-eh", "Remove unused exception handling info");
00054 
00055 Pass *llvm::createPruneEHPass() { return new PruneEH(); }
00056 
00057 
00058 bool PruneEH::runOnSCC(const std::vector<CallGraphNode *> &SCC) {
00059   SmallPtrSet<CallGraphNode *, 8> SCCNodes;
00060   CallGraph &CG = getAnalysis<CallGraph>();
00061   bool MadeChange = false;
00062 
00063   // Fill SCCNodes with the elements of the SCC.  Used for quickly
00064   // looking up whether a given CallGraphNode is in this SCC.
00065   for (unsigned i = 0, e = SCC.size(); i != e; ++i)
00066     SCCNodes.insert(SCC[i]);
00067 
00068   // First pass, scan all of the functions in the SCC, simplifying them
00069   // according to what we know.
00070   for (unsigned i = 0, e = SCC.size(); i != e; ++i)
00071     if (Function *F = SCC[i]->getFunction())
00072       MadeChange |= SimplifyFunction(F);
00073 
00074   // Next, check to see if any callees might throw or if there are any external
00075   // functions in this SCC: if so, we cannot prune any functions in this SCC.
00076   // Definitions that are weak and not declared non-throwing might be 
00077   // overridden at linktime with something that throws, so assume that.
00078   // If this SCC includes the unwind instruction, we KNOW it throws, so
00079   // obviously the SCC might throw.
00080   //
00081   bool SCCMightUnwind = false, SCCMightReturn = false;
00082   for (unsigned i = 0, e = SCC.size();
00083        (!SCCMightUnwind || !SCCMightReturn) && i != e; ++i) {
00084     Function *F = SCC[i]->getFunction();
00085     if (F == 0) {
00086       SCCMightUnwind = true;
00087       SCCMightReturn = true;
00088     } else if (F->isDeclaration() || F->mayBeOverridden()) {
00089       SCCMightUnwind |= !F->doesNotThrow();
00090       SCCMightReturn |= !F->doesNotReturn();
00091     } else {
00092       bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow();
00093       bool CheckReturn = !SCCMightReturn && !F->doesNotReturn();
00094 
00095       if (!CheckUnwind && !CheckReturn)
00096         continue;
00097 
00098       // Check to see if this function performs an unwind or calls an
00099       // unwinding function.
00100       for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
00101         if (CheckUnwind && isa<UnwindInst>(BB->getTerminator())) {
00102           // Uses unwind!
00103           SCCMightUnwind = true;
00104         } else if (CheckReturn && isa<ReturnInst>(BB->getTerminator())) {
00105           SCCMightReturn = true;
00106         }
00107 
00108         // Invoke instructions don't allow unwinding to continue, so we are
00109         // only interested in call instructions.
00110         if (CheckUnwind && !SCCMightUnwind)
00111           for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
00112             if (CallInst *CI = dyn_cast<CallInst>(I)) {
00113               if (CI->doesNotThrow()) {
00114                 // This call cannot throw.
00115               } else if (Function *Callee = CI->getCalledFunction()) {
00116                 CallGraphNode *CalleeNode = CG[Callee];
00117                 // If the callee is outside our current SCC then we may
00118                 // throw because it might.
00119                 if (!SCCNodes.count(CalleeNode)) {
00120                   SCCMightUnwind = true;
00121                   break;
00122                 }
00123               } else {
00124                 // Indirect call, it might throw.
00125                 SCCMightUnwind = true;
00126                 break;
00127               }
00128             }
00129         if (SCCMightUnwind && SCCMightReturn) break;
00130       }
00131     }
00132   }
00133 
00134   // If the SCC doesn't unwind or doesn't throw, note this fact.
00135   if (!SCCMightUnwind || !SCCMightReturn)
00136     for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
00137       Attributes NewAttributes = Attribute::None;
00138 
00139       if (!SCCMightUnwind)
00140         NewAttributes |= Attribute::NoUnwind;
00141       if (!SCCMightReturn)
00142         NewAttributes |= Attribute::NoReturn;
00143 
00144       const AttrListPtr &PAL = SCC[i]->getFunction()->getAttributes();
00145       const AttrListPtr &NPAL = PAL.addAttr(~0, NewAttributes);
00146       if (PAL != NPAL) {
00147         MadeChange = true;
00148         SCC[i]->getFunction()->setAttributes(NPAL);
00149       }
00150     }
00151 
00152   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
00153     // Convert any invoke instructions to non-throwing functions in this node
00154     // into call instructions with a branch.  This makes the exception blocks
00155     // dead.
00156     if (Function *F = SCC[i]->getFunction())
00157       MadeChange |= SimplifyFunction(F);
00158   }
00159 
00160   return MadeChange;
00161 }
00162 
00163 
00164 // SimplifyFunction - Given information about callees, simplify the specified
00165 // function if we have invokes to non-unwinding functions or code after calls to
00166 // no-return functions.
00167 bool PruneEH::SimplifyFunction(Function *F) {
00168   CallGraph &CG = getAnalysis<CallGraph>();
00169   CallGraphNode *CGN = CG[F];
00170 
00171   bool MadeChange = false;
00172   for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
00173     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
00174       if (II->doesNotThrow()) {
00175         SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end());
00176         // Insert a call instruction before the invoke.
00177         CallInst *Call = CallInst::Create(II->getCalledValue(),
00178                                           Args.begin(), Args.end(), "", II);
00179         Call->takeName(II);
00180         Call->setCallingConv(II->getCallingConv());
00181         Call->setAttributes(II->getAttributes());
00182 
00183         // Anything that used the value produced by the invoke instruction
00184         // now uses the value produced by the call instruction.
00185         II->replaceAllUsesWith(Call);
00186         BasicBlock *UnwindBlock = II->getUnwindDest();
00187         UnwindBlock->removePredecessor(II->getParent());
00188 
00189         // Fix up the call graph.
00190         CGN->replaceCallSite(II, Call);
00191 
00192         // Insert a branch to the normal destination right before the
00193         // invoke.
00194         BranchInst::Create(II->getNormalDest(), II);
00195 
00196         // Finally, delete the invoke instruction!
00197         BB->getInstList().pop_back();
00198 
00199         // If the unwind block is now dead, nuke it.
00200         if (pred_begin(UnwindBlock) == pred_end(UnwindBlock))
00201           DeleteBasicBlock(UnwindBlock);  // Delete the new BB.
00202 
00203         ++NumRemoved;
00204         MadeChange = true;
00205       }
00206 
00207     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
00208       if (CallInst *CI = dyn_cast<CallInst>(I++))
00209         if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) {
00210           // This call calls a function that cannot return.  Insert an
00211           // unreachable instruction after it and simplify the code.  Do this
00212           // by splitting the BB, adding the unreachable, then deleting the
00213           // new BB.
00214           BasicBlock *New = BB->splitBasicBlock(I);
00215 
00216           // Remove the uncond branch and add an unreachable.
00217           BB->getInstList().pop_back();
00218           new UnreachableInst(BB->getContext(), BB);
00219 
00220           DeleteBasicBlock(New);  // Delete the new BB.
00221           MadeChange = true;
00222           ++NumUnreach;
00223           break;
00224         }
00225   }
00226 
00227   return MadeChange;
00228 }
00229 
00230 /// DeleteBasicBlock - remove the specified basic block from the program,
00231 /// updating the callgraph to reflect any now-obsolete edges due to calls that
00232 /// exist in the BB.
00233 void PruneEH::DeleteBasicBlock(BasicBlock *BB) {
00234   assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!");
00235   CallGraph &CG = getAnalysis<CallGraph>();
00236 
00237   CallGraphNode *CGN = CG[BB->getParent()];
00238   for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
00239     --I;
00240     if (CallInst *CI = dyn_cast<CallInst>(I)) {
00241       if (!isa<DbgInfoIntrinsic>(I))
00242         CGN->removeCallEdgeFor(CI);
00243     } else if (InvokeInst *II = dyn_cast<InvokeInst>(I))
00244       CGN->removeCallEdgeFor(II);
00245     if (!I->use_empty())
00246       I->replaceAllUsesWith(UndefValue::get(I->getType()));
00247   }
00248 
00249   // Get the list of successors of this block.
00250   std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));
00251 
00252   for (unsigned i = 0, e = Succs.size(); i != e; ++i)
00253     Succs[i]->removePredecessor(BB);
00254 
00255   BB->eraseFromParent();
00256 }