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