Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 1 | //===- PruneEH.cpp - Pass which deletes unused exception handlers ---------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 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. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 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 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 17 | #define DEBUG_TYPE "prune-eh" |
Chris Lattner | 1e2385b | 2003-11-21 21:54:22 +0000 | [diff] [blame] | 18 | #include "llvm/Transforms/IPO.h" |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 19 | #include "llvm/CallGraphSCCPass.h" |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 20 | #include "llvm/Constants.h" |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 21 | #include "llvm/Function.h" |
| 22 | #include "llvm/Intrinsics.h" |
Misha Brukman | 47b14a4 | 2004-07-29 17:30:56 +0000 | [diff] [blame] | 23 | #include "llvm/Instructions.h" |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 24 | #include "llvm/Analysis/CallGraph.h" |
Chris Lattner | 93e985f | 2007-02-13 02:10:56 +0000 | [diff] [blame] | 25 | #include "llvm/ADT/SmallVector.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 26 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 27 | #include "llvm/Support/CFG.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 28 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 29 | #include <set> |
Chris Lattner | f26801b | 2004-10-18 15:43:46 +0000 | [diff] [blame] | 30 | #include <algorithm> |
Chris Lattner | 1e2385b | 2003-11-21 21:54:22 +0000 | [diff] [blame] | 31 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 32 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 33 | STATISTIC(NumRemoved, "Number of invokes removed"); |
| 34 | STATISTIC(NumUnreach, "Number of noreturn calls optimized"); |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 35 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 36 | namespace { |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 37 | struct VISIBILITY_HIDDEN PruneEH : public CallGraphSCCPass { |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame^] | 38 | static char ID; // Pass identifcation, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 39 | PruneEH() : CallGraphSCCPass((intptr_t)&ID) {} |
| 40 | |
Chris Lattner | bc9fa58 | 2005-04-26 23:53:25 +0000 | [diff] [blame] | 41 | /// DoesNotUnwind - This set contains all of the functions which we have |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 42 | /// determined cannot unwind. |
Chris Lattner | bc9fa58 | 2005-04-26 23:53:25 +0000 | [diff] [blame] | 43 | std::set<CallGraphNode*> DoesNotUnwind; |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 44 | |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 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 | |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 49 | // runOnSCC - Analyze the SCC, performing the transformation if possible. |
| 50 | bool runOnSCC(const std::vector<CallGraphNode *> &SCC); |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 51 | |
| 52 | bool SimplifyFunction(Function *F); |
| 53 | void DeleteBasicBlock(BasicBlock *BB); |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 54 | }; |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 55 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame^] | 56 | char PruneEH::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 57 | RegisterPass<PruneEH> X("prune-eh", "Remove unused exception handling info"); |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 58 | } |
| 59 | |
Devang Patel | c71ca3c | 2007-01-26 00:47:38 +0000 | [diff] [blame] | 60 | Pass *llvm::createPruneEHPass() { return new PruneEH(); } |
Chris Lattner | f6fb96f | 2003-08-31 16:30:07 +0000 | [diff] [blame] | 61 | |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 62 | |
| 63 | bool PruneEH::runOnSCC(const std::vector<CallGraphNode *> &SCC) { |
| 64 | CallGraph &CG = getAnalysis<CallGraph>(); |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 65 | bool MadeChange = false; |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 66 | |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 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 |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 74 | // functions in this SCC: if so, we cannot prune any functions in this SCC. |
Chris Lattner | ee5457c | 2003-09-08 19:44:26 +0000 | [diff] [blame] | 75 | // If this SCC includes the unwind instruction, we KNOW it throws, so |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 76 | // obviously the SCC might throw. |
| 77 | // |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 78 | bool SCCMightUnwind = false, SCCMightReturn = false; |
| 79 | for (unsigned i = 0, e = SCC.size(); |
| 80 | (!SCCMightUnwind || !SCCMightReturn) && i != e; ++i) { |
Chris Lattner | d08ddd3 | 2004-04-12 04:06:38 +0000 | [diff] [blame] | 81 | Function *F = SCC[i]->getFunction(); |
Reid Spencer | 5cbf985 | 2007-01-30 20:08:39 +0000 | [diff] [blame] | 82 | if (F == 0 || (F->isDeclaration() && !F->getIntrinsicID())) { |
Chris Lattner | bc9fa58 | 2005-04-26 23:53:25 +0000 | [diff] [blame] | 83 | SCCMightUnwind = true; |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 84 | SCCMightReturn = true; |
Chris Lattner | d08ddd3 | 2004-04-12 04:06:38 +0000 | [diff] [blame] | 85 | } else { |
Reid Spencer | 5cbf985 | 2007-01-30 20:08:39 +0000 | [diff] [blame] | 86 | if (F->isDeclaration()) |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 87 | SCCMightReturn = true; |
| 88 | |
Chris Lattner | d08ddd3 | 2004-04-12 04:06:38 +0000 | [diff] [blame] | 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! |
Chris Lattner | bc9fa58 | 2005-04-26 23:53:25 +0000 | [diff] [blame] | 93 | SCCMightUnwind = true; |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 94 | } else if (isa<ReturnInst>(BB->getTerminator())) { |
| 95 | SCCMightReturn = true; |
Chris Lattner | d08ddd3 | 2004-04-12 04:06:38 +0000 | [diff] [blame] | 96 | } |
Chris Lattner | e0def04 | 2004-02-08 21:15:59 +0000 | [diff] [blame] | 97 | |
Chris Lattner | d08ddd3 | 2004-04-12 04:06:38 +0000 | [diff] [blame] | 98 | // Invoke instructions don't allow unwinding to continue, so we are |
| 99 | // only interested in call instructions. |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 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. |
Chris Lattner | bc9fa58 | 2005-04-26 23:53:25 +0000 | [diff] [blame] | 114 | SCCMightUnwind = true; |
Chris Lattner | e0def04 | 2004-02-08 21:15:59 +0000 | [diff] [blame] | 115 | break; |
| 116 | } |
| 117 | } |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 118 | if (SCCMightUnwind && SCCMightReturn) break; |
Chris Lattner | ad9b5f3 | 2003-09-15 02:22:50 +0000 | [diff] [blame] | 119 | } |
Chris Lattner | d08ddd3 | 2004-04-12 04:06:38 +0000 | [diff] [blame] | 120 | } |
| 121 | } |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 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]); |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 130 | |
| 131 | for (unsigned i = 0, e = SCC.size(); i != e; ++i) { |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 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()) |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 136 | MadeChange |= SimplifyFunction(F); |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 137 | } |
| 138 | |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 139 | return MadeChange; |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 140 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 141 | |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 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. |
| 146 | bool 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])) { |
Chris Lattner | 93e985f | 2007-02-13 02:10:56 +0000 | [diff] [blame] | 153 | SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); |
Chris Lattner | 046800a | 2007-02-11 01:08:35 +0000 | [diff] [blame] | 154 | // Insert a call instruction before the invoke. |
Chris Lattner | f201dbc | 2005-05-09 01:05:50 +0000 | [diff] [blame] | 155 | CallInst *Call = new CallInst(II->getCalledValue(), |
Chris Lattner | 93e985f | 2007-02-13 02:10:56 +0000 | [diff] [blame] | 156 | &Args[0], Args.size(), "", II); |
Chris Lattner | 046800a | 2007-02-11 01:08:35 +0000 | [diff] [blame] | 157 | Call->takeName(II); |
Chris Lattner | f201dbc | 2005-05-09 01:05:50 +0000 | [diff] [blame] | 158 | Call->setCallingConv(II->getCallingConv()); |
Jeff Cohen | 00b16889 | 2005-07-27 06:12:32 +0000 | [diff] [blame] | 159 | |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 160 | // Anything that used the value produced by the invoke instruction |
| 161 | // now uses the value produced by the call instruction. |
| 162 | II->replaceAllUsesWith(Call); |
| 163 | BasicBlock *UnwindBlock = II->getUnwindDest(); |
| 164 | UnwindBlock->removePredecessor(II->getParent()); |
Jeff Cohen | 00b16889 | 2005-07-27 06:12:32 +0000 | [diff] [blame] | 165 | |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 166 | // Insert a branch to the normal destination right before the |
| 167 | // invoke. |
| 168 | new BranchInst(II->getNormalDest(), II); |
Jeff Cohen | 00b16889 | 2005-07-27 06:12:32 +0000 | [diff] [blame] | 169 | |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 170 | // Finally, delete the invoke instruction! |
| 171 | BB->getInstList().pop_back(); |
| 172 | |
| 173 | // If the unwind block is now dead, nuke it. |
| 174 | if (pred_begin(UnwindBlock) == pred_end(UnwindBlock)) |
| 175 | DeleteBasicBlock(UnwindBlock); // Delete the new BB. |
Jeff Cohen | 00b16889 | 2005-07-27 06:12:32 +0000 | [diff] [blame] | 176 | |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 177 | ++NumRemoved; |
| 178 | MadeChange = true; |
| 179 | } |
| 180 | |
Chris Lattner | 209a0ae | 2005-04-27 20:12:17 +0000 | [diff] [blame] | 181 | for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 182 | if (CallInst *CI = dyn_cast<CallInst>(I++)) |
| 183 | if (Function *Callee = CI->getCalledFunction()) |
| 184 | if (DoesNotReturn.count(CG[Callee]) && !isa<UnreachableInst>(I)) { |
| 185 | // This call calls a function that cannot return. Insert an |
| 186 | // unreachable instruction after it and simplify the code. Do this |
| 187 | // by splitting the BB, adding the unreachable, then deleting the |
| 188 | // new BB. |
| 189 | BasicBlock *New = BB->splitBasicBlock(I); |
| 190 | |
| 191 | // Remove the uncond branch and add an unreachable. |
| 192 | BB->getInstList().pop_back(); |
| 193 | new UnreachableInst(BB); |
| 194 | |
| 195 | DeleteBasicBlock(New); // Delete the new BB. |
| 196 | MadeChange = true; |
| 197 | ++NumUnreach; |
| 198 | break; |
| 199 | } |
| 200 | |
| 201 | } |
| 202 | return MadeChange; |
| 203 | } |
| 204 | |
| 205 | /// DeleteBasicBlock - remove the specified basic block from the program, |
| 206 | /// updating the callgraph to reflect any now-obsolete edges due to calls that |
| 207 | /// exist in the BB. |
| 208 | void PruneEH::DeleteBasicBlock(BasicBlock *BB) { |
| 209 | assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!"); |
| 210 | CallGraph &CG = getAnalysis<CallGraph>(); |
| 211 | |
| 212 | CallGraphNode *CGN = CG[BB->getParent()]; |
| 213 | for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) { |
| 214 | --I; |
| 215 | if (CallInst *CI = dyn_cast<CallInst>(I)) { |
| 216 | if (Function *Callee = CI->getCalledFunction()) |
| 217 | CGN->removeCallEdgeTo(CG[Callee]); |
| 218 | } else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) { |
| 219 | if (Function *Callee = II->getCalledFunction()) |
| 220 | CGN->removeCallEdgeTo(CG[Callee]); |
| 221 | } |
| 222 | if (!I->use_empty()) |
| 223 | I->replaceAllUsesWith(UndefValue::get(I->getType())); |
| 224 | } |
| 225 | |
| 226 | // Get the list of successors of this block. |
| 227 | std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB)); |
| 228 | |
| 229 | for (unsigned i = 0, e = Succs.size(); i != e; ++i) |
| 230 | Succs[i]->removePredecessor(BB); |
Jeff Cohen | 00b16889 | 2005-07-27 06:12:32 +0000 | [diff] [blame] | 231 | |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 232 | BB->eraseFromParent(); |
| 233 | } |