PruneEH.cpp revision 619acdc63ab0a47d125dca0591285c8ac4c9ed20
1//===- PruneEH.cpp - Pass which deletes unused exception handlers ---------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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, and marking functions 'nounwind' if they cannot throw. 13// It implements this as a bottom-up traversal of the 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/LLVMContext.h" 23#include "llvm/Instructions.h" 24#include "llvm/IntrinsicInst.h" 25#include "llvm/Analysis/CallGraph.h" 26#include "llvm/ADT/SmallPtrSet.h" 27#include "llvm/ADT/SmallVector.h" 28#include "llvm/ADT/Statistic.h" 29#include "llvm/Support/CFG.h" 30#include <set> 31#include <algorithm> 32using namespace llvm; 33 34STATISTIC(NumRemoved, "Number of invokes removed"); 35STATISTIC(NumUnreach, "Number of noreturn calls optimized"); 36 37namespace { 38 struct PruneEH : public CallGraphSCCPass { 39 static char ID; // Pass identification, replacement for typeid 40 PruneEH() : CallGraphSCCPass(&ID) {} 41 42 // runOnSCC - Analyze the SCC, performing the transformation if possible. 43 bool runOnSCC(CallGraphSCC &SCC); 44 45 bool SimplifyFunction(Function *F); 46 void DeleteBasicBlock(BasicBlock *BB); 47 }; 48} 49 50char PruneEH::ID = 0; 51INITIALIZE_PASS(PruneEH, "prune-eh", 52 "Remove unused exception handling info", false, false); 53 54Pass *llvm::createPruneEHPass() { return new PruneEH(); } 55 56 57bool PruneEH::runOnSCC(CallGraphSCC &SCC) { 58 SmallPtrSet<CallGraphNode *, 8> SCCNodes; 59 CallGraph &CG = getAnalysis<CallGraph>(); 60 bool MadeChange = false; 61 62 // Fill SCCNodes with the elements of the SCC. Used for quickly 63 // looking up whether a given CallGraphNode is in this SCC. 64 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 65 SCCNodes.insert(*I); 66 67 // First pass, scan all of the functions in the SCC, simplifying them 68 // according to what we know. 69 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 70 if (Function *F = (*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 // Definitions that are weak and not declared non-throwing might be 76 // overridden at linktime with something that throws, so assume that. 77 // If this SCC includes the unwind instruction, we KNOW it throws, so 78 // obviously the SCC might throw. 79 // 80 bool SCCMightUnwind = false, SCCMightReturn = false; 81 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); 82 (!SCCMightUnwind || !SCCMightReturn) && I != E; ++I) { 83 Function *F = (*I)->getFunction(); 84 if (F == 0) { 85 SCCMightUnwind = true; 86 SCCMightReturn = true; 87 } else if (F->isDeclaration() || F->mayBeOverridden()) { 88 SCCMightUnwind |= !F->doesNotThrow(); 89 SCCMightReturn |= !F->doesNotReturn(); 90 } else { 91 bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow(); 92 bool CheckReturn = !SCCMightReturn && !F->doesNotReturn(); 93 94 if (!CheckUnwind && !CheckReturn) 95 continue; 96 97 // Check to see if this function performs an unwind or calls an 98 // unwinding function. 99 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 100 if (CheckUnwind && isa<UnwindInst>(BB->getTerminator())) { 101 // Uses unwind! 102 SCCMightUnwind = true; 103 } else if (CheckReturn && isa<ReturnInst>(BB->getTerminator())) { 104 SCCMightReturn = true; 105 } 106 107 // Invoke instructions don't allow unwinding to continue, so we are 108 // only interested in call instructions. 109 if (CheckUnwind && !SCCMightUnwind) 110 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 111 if (CallInst *CI = dyn_cast<CallInst>(I)) { 112 if (CI->doesNotThrow()) { 113 // This call cannot throw. 114 } else if (Function *Callee = CI->getCalledFunction()) { 115 CallGraphNode *CalleeNode = CG[Callee]; 116 // If the callee is outside our current SCC then we may 117 // throw because it might. 118 if (!SCCNodes.count(CalleeNode)) { 119 SCCMightUnwind = true; 120 break; 121 } 122 } else { 123 // Indirect call, it might throw. 124 SCCMightUnwind = true; 125 break; 126 } 127 } 128 if (SCCMightUnwind && SCCMightReturn) break; 129 } 130 } 131 } 132 133 // If the SCC doesn't unwind or doesn't throw, note this fact. 134 if (!SCCMightUnwind || !SCCMightReturn) 135 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 136 Attributes NewAttributes = Attribute::None; 137 138 if (!SCCMightUnwind) 139 NewAttributes |= Attribute::NoUnwind; 140 if (!SCCMightReturn) 141 NewAttributes |= Attribute::NoReturn; 142 143 Function *F = (*I)->getFunction(); 144 const AttrListPtr &PAL = F->getAttributes(); 145 const AttrListPtr &NPAL = PAL.addAttr(~0, NewAttributes); 146 if (PAL != NPAL) { 147 MadeChange = true; 148 F->setAttributes(NPAL); 149 } 150 } 151 152 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 153 // Convert any invoke instructions to non-throwing functions in this node 154 // into call instructions with a branch. This makes the exception blocks 155 // dead. 156 if (Function *F = (*I)->getFunction()) 157 MadeChange |= SimplifyFunction(F); 158 } 159 160 return MadeChange; 161} 162 163 164// SimplifyFunction - Given information about callees, simplify the specified 165// function if we have invokes to non-unwinding functions or code after calls to 166// no-return functions. 167bool PruneEH::SimplifyFunction(Function *F) { 168 bool MadeChange = false; 169 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 170 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) 171 if (II->doesNotThrow()) { 172 SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3); 173 // Insert a call instruction before the invoke. 174 CallInst *Call = CallInst::Create(II->getCalledValue(), 175 Args.begin(), Args.end(), "", II); 176 Call->takeName(II); 177 Call->setCallingConv(II->getCallingConv()); 178 Call->setAttributes(II->getAttributes()); 179 180 // Anything that used the value produced by the invoke instruction 181 // now uses the value produced by the call instruction. Note that we 182 // do this even for void functions and calls with no uses so that the 183 // callgraph edge is updated. 184 II->replaceAllUsesWith(Call); 185 BasicBlock *UnwindBlock = II->getUnwindDest(); 186 UnwindBlock->removePredecessor(II->getParent()); 187 188 // Insert a branch to the normal destination right before the 189 // invoke. 190 BranchInst::Create(II->getNormalDest(), II); 191 192 // Finally, delete the invoke instruction! 193 BB->getInstList().pop_back(); 194 195 // If the unwind block is now dead, nuke it. 196 if (pred_begin(UnwindBlock) == pred_end(UnwindBlock)) 197 DeleteBasicBlock(UnwindBlock); // Delete the new BB. 198 199 ++NumRemoved; 200 MadeChange = true; 201 } 202 203 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) 204 if (CallInst *CI = dyn_cast<CallInst>(I++)) 205 if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) { 206 // This call calls a function that cannot return. Insert an 207 // unreachable instruction after it and simplify the code. Do this 208 // by splitting the BB, adding the unreachable, then deleting the 209 // new BB. 210 BasicBlock *New = BB->splitBasicBlock(I); 211 212 // Remove the uncond branch and add an unreachable. 213 BB->getInstList().pop_back(); 214 new UnreachableInst(BB->getContext(), BB); 215 216 DeleteBasicBlock(New); // Delete the new BB. 217 MadeChange = true; 218 ++NumUnreach; 219 break; 220 } 221 } 222 223 return MadeChange; 224} 225 226/// DeleteBasicBlock - remove the specified basic block from the program, 227/// updating the callgraph to reflect any now-obsolete edges due to calls that 228/// exist in the BB. 229void PruneEH::DeleteBasicBlock(BasicBlock *BB) { 230 assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!"); 231 CallGraph &CG = getAnalysis<CallGraph>(); 232 233 CallGraphNode *CGN = CG[BB->getParent()]; 234 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) { 235 --I; 236 if (CallInst *CI = dyn_cast<CallInst>(I)) { 237 if (!isa<DbgInfoIntrinsic>(I)) 238 CGN->removeCallEdgeFor(CI); 239 } else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 240 CGN->removeCallEdgeFor(II); 241 if (!I->use_empty()) 242 I->replaceAllUsesWith(UndefValue::get(I->getType())); 243 } 244 245 // Get the list of successors of this block. 246 std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB)); 247 248 for (unsigned i = 0, e = Succs.size(); i != e; ++i) 249 Succs[i]->removePredecessor(BB); 250 251 BB->eraseFromParent(); 252} 253