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