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