PruneEH.cpp revision f5588dc4ec43da1e4423e5ff2394669c0f000350
1//===- PruneEH.cpp - Pass which deletes unused exception handlers ---------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements a simple interprocedural pass which walks the 11// call-graph, turning invoke instructions into calls, iff the callee cannot 12// throw an exception. It implements this as a bottom-up traversal of the 13// call-graph. 14// 15//===----------------------------------------------------------------------===// 16 17#define DEBUG_TYPE "prune-eh" 18#include "llvm/Transforms/IPO.h" 19#include "llvm/CallGraphSCCPass.h" 20#include "llvm/Constants.h" 21#include "llvm/Function.h" 22#include "llvm/Intrinsics.h" 23#include "llvm/Instructions.h" 24#include "llvm/Analysis/CallGraph.h" 25#include "llvm/ADT/SmallVector.h" 26#include "llvm/ADT/Statistic.h" 27#include "llvm/Support/CFG.h" 28#include "llvm/Support/Compiler.h" 29#include <set> 30#include <algorithm> 31using namespace llvm; 32 33STATISTIC(NumRemoved, "Number of invokes removed"); 34STATISTIC(NumUnreach, "Number of noreturn calls optimized"); 35 36namespace { 37 struct VISIBILITY_HIDDEN PruneEH : public CallGraphSCCPass { 38 static char ID; // Pass identification, replacement for typeid 39 PruneEH() : CallGraphSCCPass((intptr_t)&ID) {} 40 41 /// DoesNotUnwind - This set contains all of the functions which we have 42 /// determined cannot unwind. 43 std::set<CallGraphNode*> DoesNotUnwind; 44 45 /// DoesNotReturn - This set contains all of the functions which we have 46 /// determined cannot return normally (but might unwind). 47 std::set<CallGraphNode*> DoesNotReturn; 48 49 // runOnSCC - Analyze the SCC, performing the transformation if possible. 50 bool runOnSCC(const std::vector<CallGraphNode *> &SCC); 51 52 bool SimplifyFunction(Function *F); 53 void DeleteBasicBlock(BasicBlock *BB); 54 }; 55 56 char PruneEH::ID = 0; 57 RegisterPass<PruneEH> X("prune-eh", "Remove unused exception handling info"); 58} 59 60Pass *llvm::createPruneEHPass() { return new PruneEH(); } 61 62 63bool PruneEH::runOnSCC(const std::vector<CallGraphNode *> &SCC) { 64 CallGraph &CG = getAnalysis<CallGraph>(); 65 bool MadeChange = false; 66 67 // First pass, scan all of the functions in the SCC, simplifying them 68 // according to what we know. 69 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 70 if (Function *F = SCC[i]->getFunction()) 71 MadeChange |= SimplifyFunction(F); 72 73 // Next, check to see if any callees might throw or if there are any external 74 // functions in this SCC: if so, we cannot prune any functions in this SCC. 75 // If this SCC includes the unwind instruction, we KNOW it throws, so 76 // obviously the SCC might throw. 77 // 78 bool SCCMightUnwind = false, SCCMightReturn = false; 79 for (unsigned i = 0, e = SCC.size(); 80 (!SCCMightUnwind || !SCCMightReturn) && i != e; ++i) { 81 Function *F = SCC[i]->getFunction(); 82 if (F == 0 || (F->isDeclaration() && !F->getIntrinsicID())) { 83 SCCMightUnwind = true; 84 SCCMightReturn = true; 85 } else { 86 if (F->isDeclaration()) 87 SCCMightReturn = true; 88 89 // Check to see if this function performs an unwind or calls an 90 // unwinding function. 91 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 92 if (isa<UnwindInst>(BB->getTerminator())) { // Uses unwind! 93 SCCMightUnwind = true; 94 } else if (isa<ReturnInst>(BB->getTerminator())) { 95 SCCMightReturn = true; 96 } 97 98 // Invoke instructions don't allow unwinding to continue, so we are 99 // only interested in call instructions. 100 if (!SCCMightUnwind) 101 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 102 if (CallInst *CI = dyn_cast<CallInst>(I)) { 103 if (Function *Callee = CI->getCalledFunction()) { 104 CallGraphNode *CalleeNode = CG[Callee]; 105 // If the callee is outside our current SCC, or if it is not 106 // known to throw, then we might throw also. 107 if (std::find(SCC.begin(), SCC.end(), CalleeNode) == SCC.end()&& 108 !DoesNotUnwind.count(CalleeNode)) { 109 SCCMightUnwind = true; 110 break; 111 } 112 } else { 113 // Indirect call, it might throw. 114 SCCMightUnwind = true; 115 break; 116 } 117 } 118 if (SCCMightUnwind && SCCMightReturn) break; 119 } 120 } 121 } 122 123 // If the SCC doesn't unwind or doesn't throw, note this fact. 124 if (!SCCMightUnwind) 125 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 126 DoesNotUnwind.insert(SCC[i]); 127 if (!SCCMightReturn) 128 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 129 DoesNotReturn.insert(SCC[i]); 130 131 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 132 // Convert any invoke instructions to non-throwing functions in this node 133 // into call instructions with a branch. This makes the exception blocks 134 // dead. 135 if (Function *F = SCC[i]->getFunction()) 136 MadeChange |= SimplifyFunction(F); 137 } 138 139 return MadeChange; 140} 141 142 143// SimplifyFunction - Given information about callees, simplify the specified 144// function if we have invokes to non-unwinding functions or code after calls to 145// no-return functions. 146bool PruneEH::SimplifyFunction(Function *F) { 147 CallGraph &CG = getAnalysis<CallGraph>(); 148 bool MadeChange = false; 149 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 150 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) 151 if (Function *F = II->getCalledFunction()) 152 if (DoesNotUnwind.count(CG[F])) { 153 SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); 154 // Insert a call instruction before the invoke. 155 CallInst *Call = new CallInst(II->getCalledValue(), 156 Args.begin(), Args.end(), "", II); 157 Call->takeName(II); 158 Call->setCallingConv(II->getCallingConv()); 159 Call->setParamAttrs(II->getParamAttrs()); 160 161 // Anything that used the value produced by the invoke instruction 162 // now uses the value produced by the call instruction. 163 II->replaceAllUsesWith(Call); 164 BasicBlock *UnwindBlock = II->getUnwindDest(); 165 UnwindBlock->removePredecessor(II->getParent()); 166 167 // Insert a branch to the normal destination right before the 168 // invoke. 169 new BranchInst(II->getNormalDest(), II); 170 171 // Finally, delete the invoke instruction! 172 BB->getInstList().pop_back(); 173 174 // If the unwind block is now dead, nuke it. 175 if (pred_begin(UnwindBlock) == pred_end(UnwindBlock)) 176 DeleteBasicBlock(UnwindBlock); // Delete the new BB. 177 178 ++NumRemoved; 179 MadeChange = true; 180 } 181 182 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) 183 if (CallInst *CI = dyn_cast<CallInst>(I++)) 184 if (Function *Callee = CI->getCalledFunction()) 185 if (DoesNotReturn.count(CG[Callee]) && !isa<UnreachableInst>(I)) { 186 // This call calls a function that cannot return. Insert an 187 // unreachable instruction after it and simplify the code. Do this 188 // by splitting the BB, adding the unreachable, then deleting the 189 // new BB. 190 BasicBlock *New = BB->splitBasicBlock(I); 191 192 // Remove the uncond branch and add an unreachable. 193 BB->getInstList().pop_back(); 194 new UnreachableInst(BB); 195 196 DeleteBasicBlock(New); // Delete the new BB. 197 MadeChange = true; 198 ++NumUnreach; 199 break; 200 } 201 202 } 203 return MadeChange; 204} 205 206/// DeleteBasicBlock - remove the specified basic block from the program, 207/// updating the callgraph to reflect any now-obsolete edges due to calls that 208/// exist in the BB. 209void PruneEH::DeleteBasicBlock(BasicBlock *BB) { 210 assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!"); 211 CallGraph &CG = getAnalysis<CallGraph>(); 212 213 CallGraphNode *CGN = CG[BB->getParent()]; 214 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) { 215 --I; 216 if (CallInst *CI = dyn_cast<CallInst>(I)) { 217 if (Function *Callee = CI->getCalledFunction()) 218 CGN->removeCallEdgeTo(CG[Callee]); 219 } else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) { 220 if (Function *Callee = II->getCalledFunction()) 221 CGN->removeCallEdgeTo(CG[Callee]); 222 } 223 if (!I->use_empty()) 224 I->replaceAllUsesWith(UndefValue::get(I->getType())); 225 } 226 227 // Get the list of successors of this block. 228 std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB)); 229 230 for (unsigned i = 0, e = Succs.size(); i != e; ++i) 231 Succs[i]->removePredecessor(BB); 232 233 BB->eraseFromParent(); 234} 235