PruneEH.cpp revision 193323
138451Smsmith//===- PruneEH.cpp - Pass which deletes unused exception handlers ---------===// 238451Smsmith// 338451Smsmith// The LLVM Compiler Infrastructure 438451Smsmith// 538451Smsmith// This file is distributed under the University of Illinois Open Source 638451Smsmith// License. See LICENSE.TXT for details. 738451Smsmith// 838451Smsmith//===----------------------------------------------------------------------===// 938451Smsmith// 1038451Smsmith// This file implements a simple interprocedural pass which walks the 1138451Smsmith// call-graph, turning invoke instructions into calls, iff the callee cannot 1238451Smsmith// throw an exception, and marking functions 'nounwind' if they cannot throw. 1338451Smsmith// It implements this as a bottom-up traversal of the call-graph. 1438451Smsmith// 1538451Smsmith//===----------------------------------------------------------------------===// 1638451Smsmith 1738451Smsmith#define DEBUG_TYPE "prune-eh" 1838451Smsmith#include "llvm/Transforms/IPO.h" 1938451Smsmith#include "llvm/CallGraphSCCPass.h" 2038451Smsmith#include "llvm/Constants.h" 2138451Smsmith#include "llvm/Function.h" 2238451Smsmith#include "llvm/Instructions.h" 2338451Smsmith#include "llvm/IntrinsicInst.h" 2438451Smsmith#include "llvm/Analysis/CallGraph.h" 2538451Smsmith#include "llvm/ADT/SmallPtrSet.h" 2638451Smsmith#include "llvm/ADT/SmallVector.h" 2738451Smsmith#include "llvm/ADT/Statistic.h" 2838451Smsmith#include "llvm/Support/CFG.h" 2938451Smsmith#include "llvm/Support/Compiler.h" 3038451Smsmith#include <set> 3138451Smsmith#include <algorithm> 3238451Smsmithusing namespace llvm; 3338451Smsmith 3438451SmsmithSTATISTIC(NumRemoved, "Number of invokes removed"); 3538451SmsmithSTATISTIC(NumUnreach, "Number of noreturn calls optimized"); 3638451Smsmith 3738451Smsmithnamespace { 3838451Smsmith struct VISIBILITY_HIDDEN PruneEH : public CallGraphSCCPass { 3938451Smsmith static char ID; // Pass identification, replacement for typeid 4038451Smsmith PruneEH() : CallGraphSCCPass(&ID) {} 4138451Smsmith 4284221Sdillon // runOnSCC - Analyze the SCC, performing the transformation if possible. 4384221Sdillon bool runOnSCC(const std::vector<CallGraphNode *> &SCC); 4484221Sdillon 4538451Smsmith bool SimplifyFunction(Function *F); 4638451Smsmith void DeleteBasicBlock(BasicBlock *BB); 4738451Smsmith }; 4838451Smsmith} 4938451Smsmith 5038451Smsmithchar PruneEH::ID = 0; 5138451Smsmithstatic RegisterPass<PruneEH> 5238451SmsmithX("prune-eh", "Remove unused exception handling info"); 5338451Smsmith 5438451SmsmithPass *llvm::createPruneEHPass() { return new PruneEH(); } 5538451Smsmith 5638451Smsmith 5738451Smsmithbool PruneEH::runOnSCC(const std::vector<CallGraphNode *> &SCC) { 5838451Smsmith SmallPtrSet<CallGraphNode *, 8> SCCNodes; 5938451Smsmith CallGraph &CG = getAnalysis<CallGraph>(); 6038451Smsmith bool MadeChange = false; 6138451Smsmith 6238451Smsmith // Fill SCCNodes with the elements of the SCC. Used for quickly 6338451Smsmith // looking up whether a given CallGraphNode is in this SCC. 6438451Smsmith for (unsigned i = 0, e = SCC.size(); i != e; ++i) 6538451Smsmith SCCNodes.insert(SCC[i]); 6638451Smsmith 6738451Smsmith // First pass, scan all of the functions in the SCC, simplifying them 6838451Smsmith // according to what we know. 6938451Smsmith for (unsigned i = 0, e = SCC.size(); i != e; ++i) 7038451Smsmith if (Function *F = SCC[i]->getFunction()) 7138451Smsmith MadeChange |= SimplifyFunction(F); 7238451Smsmith 7338451Smsmith // Next, check to see if any callees might throw or if there are any external 7438451Smsmith // functions in this SCC: if so, we cannot prune any functions in this SCC. 7538451Smsmith // Definitions that are weak and not declared non-throwing might be 7638451Smsmith // overridden at linktime with something that throws, so assume that. 7738451Smsmith // If this SCC includes the unwind instruction, we KNOW it throws, so 7838451Smsmith // obviously the SCC might throw. 7938451Smsmith // 8038451Smsmith bool SCCMightUnwind = false, SCCMightReturn = false; 8138451Smsmith for (unsigned i = 0, e = SCC.size(); 8238451Smsmith (!SCCMightUnwind || !SCCMightReturn) && i != e; ++i) { 8338451Smsmith Function *F = SCC[i]->getFunction(); 8438451Smsmith if (F == 0) { 8538451Smsmith SCCMightUnwind = true; 8664527Sps SCCMightReturn = true; 8738451Smsmith } else if (F->isDeclaration() || F->mayBeOverridden()) { 8864527Sps SCCMightUnwind |= !F->doesNotThrow(); 8938451Smsmith SCCMightReturn |= !F->doesNotReturn(); 9038451Smsmith } else { 9192913Sobrien bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow(); 9238451Smsmith bool CheckReturn = !SCCMightReturn && !F->doesNotReturn(); 9338451Smsmith 9438451Smsmith if (!CheckUnwind && !CheckReturn) 9538451Smsmith continue; 9638451Smsmith 9738451Smsmith // Check to see if this function performs an unwind or calls an 9838451Smsmith // unwinding function. 9938451Smsmith for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 10038451Smsmith if (CheckUnwind && isa<UnwindInst>(BB->getTerminator())) { 10138451Smsmith // Uses unwind! 10238451Smsmith SCCMightUnwind = true; 10338451Smsmith } else if (CheckReturn && isa<ReturnInst>(BB->getTerminator())) { 10438451Smsmith SCCMightReturn = true; 10538451Smsmith } 10638451Smsmith 10738451Smsmith // Invoke instructions don't allow unwinding to continue, so we are 10838451Smsmith // only interested in call instructions. 10938451Smsmith if (CheckUnwind && !SCCMightUnwind) 11038451Smsmith for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 11138451Smsmith if (CallInst *CI = dyn_cast<CallInst>(I)) { 11238451Smsmith if (CI->doesNotThrow()) { 11338451Smsmith // This call cannot throw. 11438451Smsmith } else if (Function *Callee = CI->getCalledFunction()) { 11538451Smsmith CallGraphNode *CalleeNode = CG[Callee]; 11638451Smsmith // If the callee is outside our current SCC then we may 11738451Smsmith // throw because it might. 11838451Smsmith if (!SCCNodes.count(CalleeNode)) { 11938451Smsmith SCCMightUnwind = true; 12038451Smsmith break; 12138451Smsmith } 12238451Smsmith } else { 12338451Smsmith // Indirect call, it might throw. 12438451Smsmith SCCMightUnwind = true; 12538451Smsmith break; 12638451Smsmith } 12738451Smsmith } 12838451Smsmith if (SCCMightUnwind && SCCMightReturn) break; 12938451Smsmith } 13038451Smsmith } 13164527Sps } 13264527Sps 13364527Sps // If the SCC doesn't unwind or doesn't throw, note this fact. 13464527Sps if (!SCCMightUnwind || !SCCMightReturn) 13564527Sps for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 13664527Sps Attributes NewAttributes = Attribute::None; 13764527Sps 13864527Sps if (!SCCMightUnwind) 13964527Sps NewAttributes |= Attribute::NoUnwind; 14064527Sps if (!SCCMightReturn) 14164527Sps NewAttributes |= Attribute::NoReturn; 14264527Sps 14364527Sps const AttrListPtr &PAL = SCC[i]->getFunction()->getAttributes(); 14438451Smsmith const AttrListPtr &NPAL = PAL.addAttr(~0, NewAttributes); 14538451Smsmith if (PAL != NPAL) { 14638451Smsmith MadeChange = true; 14738451Smsmith SCC[i]->getFunction()->setAttributes(NPAL); 14838451Smsmith } 14938451Smsmith } 15038451Smsmith 15138451Smsmith for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 15238451Smsmith // Convert any invoke instructions to non-throwing functions in this node 15338451Smsmith // into call instructions with a branch. This makes the exception blocks 15438451Smsmith // dead. 15538451Smsmith if (Function *F = SCC[i]->getFunction()) 15638451Smsmith MadeChange |= SimplifyFunction(F); 15738451Smsmith } 15838451Smsmith 15938451Smsmith return MadeChange; 16038451Smsmith} 16138451Smsmith 16238451Smsmith 16338451Smsmith// SimplifyFunction - Given information about callees, simplify the specified 16438451Smsmith// function if we have invokes to non-unwinding functions or code after calls to 16538451Smsmith// no-return functions. 16638451Smsmithbool PruneEH::SimplifyFunction(Function *F) { 16738451Smsmith CallGraph &CG = getAnalysis<CallGraph>(); 16838451Smsmith CallGraphNode *CGN = CG[F]; 16938451Smsmith 17038451Smsmith bool MadeChange = false; 17138451Smsmith for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 17238451Smsmith if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) 17338451Smsmith if (II->doesNotThrow()) { 17438451Smsmith SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); 17538451Smsmith // Insert a call instruction before the invoke. 17638451Smsmith CallInst *Call = CallInst::Create(II->getCalledValue(), 17738451Smsmith Args.begin(), Args.end(), "", II); 17838451Smsmith Call->takeName(II); 17938451Smsmith Call->setCallingConv(II->getCallingConv()); 18064527Sps Call->setAttributes(II->getAttributes()); 18164527Sps 18264527Sps // Anything that used the value produced by the invoke instruction 18364527Sps // now uses the value produced by the call instruction. 18464527Sps II->replaceAllUsesWith(Call); 18564527Sps BasicBlock *UnwindBlock = II->getUnwindDest(); 18664527Sps UnwindBlock->removePredecessor(II->getParent()); 18738451Smsmith 18838451Smsmith // Fix up the call graph. 18938451Smsmith CGN->replaceCallSite(II, Call); 19038451Smsmith 19138451Smsmith // Insert a branch to the normal destination right before the 19238451Smsmith // invoke. 19338451Smsmith BranchInst::Create(II->getNormalDest(), II); 19438451Smsmith 19538451Smsmith // Finally, delete the invoke instruction! 19638451Smsmith BB->getInstList().pop_back(); 19738451Smsmith 19838451Smsmith // If the unwind block is now dead, nuke it. 19938451Smsmith if (pred_begin(UnwindBlock) == pred_end(UnwindBlock)) 20038451Smsmith DeleteBasicBlock(UnwindBlock); // Delete the new BB. 20138451Smsmith 20238451Smsmith ++NumRemoved; 20338451Smsmith MadeChange = true; 20438451Smsmith } 20538451Smsmith 20666134Sps for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) 20738451Smsmith if (CallInst *CI = dyn_cast<CallInst>(I++)) 20866134Sps if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) { 20938451Smsmith // This call calls a function that cannot return. Insert an 21038451Smsmith // unreachable instruction after it and simplify the code. Do this 21138451Smsmith // by splitting the BB, adding the unreachable, then deleting the 21238451Smsmith // new BB. 21338451Smsmith BasicBlock *New = BB->splitBasicBlock(I); 21438451Smsmith 21538451Smsmith // Remove the uncond branch and add an unreachable. 21638451Smsmith BB->getInstList().pop_back(); 21738451Smsmith new UnreachableInst(BB); 21838451Smsmith 21938451Smsmith DeleteBasicBlock(New); // Delete the new BB. 22038451Smsmith MadeChange = true; 22138451Smsmith ++NumUnreach; 22238451Smsmith break; 22338451Smsmith } 22438451Smsmith } 22538451Smsmith 22638451Smsmith return MadeChange; 22738451Smsmith} 22838451Smsmith 22938451Smsmith/// DeleteBasicBlock - remove the specified basic block from the program, 23038451Smsmith/// updating the callgraph to reflect any now-obsolete edges due to calls that 23138451Smsmith/// exist in the BB. 23238451Smsmithvoid PruneEH::DeleteBasicBlock(BasicBlock *BB) { 23338451Smsmith assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!"); 23438451Smsmith CallGraph &CG = getAnalysis<CallGraph>(); 23538451Smsmith 23638451Smsmith CallGraphNode *CGN = CG[BB->getParent()]; 23738451Smsmith for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) { 23838451Smsmith --I; 23938451Smsmith if (CallInst *CI = dyn_cast<CallInst>(I)) { 24038451Smsmith if (!isa<DbgInfoIntrinsic>(I)) 24138451Smsmith CGN->removeCallEdgeFor(CI); 24238451Smsmith } else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 24338451Smsmith CGN->removeCallEdgeFor(II); 24438451Smsmith if (!I->use_empty()) 24538451Smsmith I->replaceAllUsesWith(UndefValue::get(I->getType())); 24638451Smsmith } 24738451Smsmith 24838451Smsmith // Get the list of successors of this block. 24938451Smsmith std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB)); 25038451Smsmith 25138451Smsmith for (unsigned i = 0, e = Succs.size(); i != e; ++i) 25238451Smsmith Succs[i]->removePredecessor(BB); 25338451Smsmith 25438451Smsmith BB->eraseFromParent(); 25538451Smsmith} 25638451Smsmith