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 |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 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. |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 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" |
Misha Brukman | 47b14a4 | 2004-07-29 17:30:56 +0000 | [diff] [blame] | 22 | #include "llvm/Instructions.h" |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 23 | #include "llvm/Analysis/CallGraph.h" |
Chris Lattner | 93e985f | 2007-02-13 02:10:56 +0000 | [diff] [blame] | 24 | #include "llvm/ADT/SmallVector.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 25 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 26 | #include "llvm/Support/CFG.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 27 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 28 | #include <set> |
Chris Lattner | f26801b | 2004-10-18 15:43:46 +0000 | [diff] [blame] | 29 | #include <algorithm> |
Chris Lattner | 1e2385b | 2003-11-21 21:54:22 +0000 | [diff] [blame] | 30 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 31 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 32 | STATISTIC(NumRemoved, "Number of invokes removed"); |
| 33 | STATISTIC(NumUnreach, "Number of noreturn calls optimized"); |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 34 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 35 | namespace { |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 36 | struct VISIBILITY_HIDDEN PruneEH : public CallGraphSCCPass { |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 37 | static char ID; // Pass identification, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 38 | PruneEH() : CallGraphSCCPass((intptr_t)&ID) {} |
| 39 | |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 40 | // runOnSCC - Analyze the SCC, performing the transformation if possible. |
| 41 | bool runOnSCC(const std::vector<CallGraphNode *> &SCC); |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 42 | |
| 43 | bool SimplifyFunction(Function *F); |
| 44 | void DeleteBasicBlock(BasicBlock *BB); |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 45 | }; |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 46 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 47 | char PruneEH::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 48 | RegisterPass<PruneEH> X("prune-eh", "Remove unused exception handling info"); |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 49 | } |
| 50 | |
Devang Patel | c71ca3c | 2007-01-26 00:47:38 +0000 | [diff] [blame] | 51 | Pass *llvm::createPruneEHPass() { return new PruneEH(); } |
Chris Lattner | f6fb96f | 2003-08-31 16:30:07 +0000 | [diff] [blame] | 52 | |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 53 | |
| 54 | bool PruneEH::runOnSCC(const std::vector<CallGraphNode *> &SCC) { |
| 55 | CallGraph &CG = getAnalysis<CallGraph>(); |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 56 | bool MadeChange = false; |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 57 | |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 58 | // First pass, scan all of the functions in the SCC, simplifying them |
| 59 | // according to what we know. |
| 60 | for (unsigned i = 0, e = SCC.size(); i != e; ++i) |
| 61 | if (Function *F = SCC[i]->getFunction()) |
| 62 | MadeChange |= SimplifyFunction(F); |
| 63 | |
| 64 | // 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] | 65 | // 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] | 66 | // If this SCC includes the unwind instruction, we KNOW it throws, so |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 67 | // obviously the SCC might throw. |
| 68 | // |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 69 | bool SCCMightUnwind = false, SCCMightReturn = false; |
| 70 | for (unsigned i = 0, e = SCC.size(); |
| 71 | (!SCCMightUnwind || !SCCMightReturn) && i != e; ++i) { |
Chris Lattner | d08ddd3 | 2004-04-12 04:06:38 +0000 | [diff] [blame] | 72 | Function *F = SCC[i]->getFunction(); |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 73 | if (F == 0) { |
Chris Lattner | bc9fa58 | 2005-04-26 23:53:25 +0000 | [diff] [blame] | 74 | SCCMightUnwind = true; |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 75 | SCCMightReturn = true; |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 76 | } else if (F->isDeclaration()) { |
Duncan Sands | 2b0e899 | 2007-12-18 09:59:50 +0000 | [diff] [blame] | 77 | SCCMightUnwind |= !F->doesNotThrow(); |
| 78 | SCCMightReturn |= !F->doesNotReturn(); |
Chris Lattner | d08ddd3 | 2004-04-12 04:06:38 +0000 | [diff] [blame] | 79 | } else { |
Duncan Sands | 2b0e899 | 2007-12-18 09:59:50 +0000 | [diff] [blame] | 80 | bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow(); |
| 81 | bool CheckReturn = !SCCMightReturn && !F->doesNotReturn(); |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 82 | |
| 83 | if (!CheckUnwind && !CheckReturn) |
| 84 | continue; |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 85 | |
Chris Lattner | d08ddd3 | 2004-04-12 04:06:38 +0000 | [diff] [blame] | 86 | // Check to see if this function performs an unwind or calls an |
| 87 | // unwinding function. |
| 88 | for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 89 | if (CheckUnwind && isa<UnwindInst>(BB->getTerminator())) { |
| 90 | // Uses unwind! |
Chris Lattner | bc9fa58 | 2005-04-26 23:53:25 +0000 | [diff] [blame] | 91 | SCCMightUnwind = true; |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 92 | } else if (CheckReturn && isa<ReturnInst>(BB->getTerminator())) { |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 93 | SCCMightReturn = true; |
Chris Lattner | d08ddd3 | 2004-04-12 04:06:38 +0000 | [diff] [blame] | 94 | } |
Chris Lattner | e0def04 | 2004-02-08 21:15:59 +0000 | [diff] [blame] | 95 | |
Chris Lattner | d08ddd3 | 2004-04-12 04:06:38 +0000 | [diff] [blame] | 96 | // Invoke instructions don't allow unwinding to continue, so we are |
| 97 | // only interested in call instructions. |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 98 | if (CheckUnwind && !SCCMightUnwind) |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 99 | for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) |
| 100 | if (CallInst *CI = dyn_cast<CallInst>(I)) { |
Duncan Sands | 2b0e899 | 2007-12-18 09:59:50 +0000 | [diff] [blame] | 101 | if (CI->doesNotThrow()) { |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 102 | // This call cannot throw. |
| 103 | } else if (Function *Callee = CI->getCalledFunction()) { |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 104 | CallGraphNode *CalleeNode = CG[Callee]; |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 105 | // If the callee is outside our current SCC then we may |
| 106 | // throw because it might. |
| 107 | if (std::find(SCC.begin(), SCC.end(), CalleeNode) == SCC.end()){ |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 108 | SCCMightUnwind = true; |
| 109 | break; |
| 110 | } |
| 111 | } else { |
| 112 | // Indirect call, it might throw. |
Chris Lattner | bc9fa58 | 2005-04-26 23:53:25 +0000 | [diff] [blame] | 113 | SCCMightUnwind = true; |
Chris Lattner | e0def04 | 2004-02-08 21:15:59 +0000 | [diff] [blame] | 114 | break; |
| 115 | } |
| 116 | } |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 117 | if (SCCMightUnwind && SCCMightReturn) break; |
Chris Lattner | ad9b5f3 | 2003-09-15 02:22:50 +0000 | [diff] [blame] | 118 | } |
Chris Lattner | d08ddd3 | 2004-04-12 04:06:38 +0000 | [diff] [blame] | 119 | } |
| 120 | } |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 121 | |
| 122 | // If the SCC doesn't unwind or doesn't throw, note this fact. |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 123 | if (!SCCMightUnwind || !SCCMightReturn) |
| 124 | for (unsigned i = 0, e = SCC.size(); i != e; ++i) { |
Duncan Sands | f0c3354 | 2007-12-19 21:13:37 +0000 | [diff] [blame] | 125 | uint16_t NewAttributes = ParamAttr::None; |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 126 | |
| 127 | if (!SCCMightUnwind) |
Duncan Sands | f0c3354 | 2007-12-19 21:13:37 +0000 | [diff] [blame] | 128 | NewAttributes |= ParamAttr::NoUnwind; |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 129 | if (!SCCMightReturn) |
Duncan Sands | f0c3354 | 2007-12-19 21:13:37 +0000 | [diff] [blame] | 130 | NewAttributes |= ParamAttr::NoReturn; |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 131 | |
Duncan Sands | f0c3354 | 2007-12-19 21:13:37 +0000 | [diff] [blame] | 132 | const ParamAttrsList *PAL = SCC[i]->getFunction()->getParamAttrs(); |
| 133 | PAL = ParamAttrsList::includeAttrs(PAL, 0, NewAttributes); |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 134 | SCC[i]->getFunction()->setParamAttrs(PAL); |
| 135 | } |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 136 | |
| 137 | for (unsigned i = 0, e = SCC.size(); i != e; ++i) { |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 138 | // Convert any invoke instructions to non-throwing functions in this node |
| 139 | // into call instructions with a branch. This makes the exception blocks |
| 140 | // dead. |
| 141 | if (Function *F = SCC[i]->getFunction()) |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 142 | MadeChange |= SimplifyFunction(F); |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 143 | } |
| 144 | |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 145 | return MadeChange; |
Chris Lattner | 3e64b2e | 2003-08-31 02:47:32 +0000 | [diff] [blame] | 146 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 147 | |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 148 | |
| 149 | // SimplifyFunction - Given information about callees, simplify the specified |
| 150 | // function if we have invokes to non-unwinding functions or code after calls to |
| 151 | // no-return functions. |
| 152 | bool PruneEH::SimplifyFunction(Function *F) { |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 153 | bool MadeChange = false; |
| 154 | for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { |
| 155 | if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) |
Duncan Sands | 2b0e899 | 2007-12-18 09:59:50 +0000 | [diff] [blame] | 156 | if (II->doesNotThrow()) { |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 157 | SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); |
| 158 | // Insert a call instruction before the invoke. |
| 159 | CallInst *Call = new CallInst(II->getCalledValue(), |
| 160 | Args.begin(), Args.end(), "", II); |
| 161 | Call->takeName(II); |
| 162 | Call->setCallingConv(II->getCallingConv()); |
| 163 | Call->setParamAttrs(II->getParamAttrs()); |
Jeff Cohen | 00b16889 | 2005-07-27 06:12:32 +0000 | [diff] [blame] | 164 | |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 165 | // Anything that used the value produced by the invoke instruction |
| 166 | // now uses the value produced by the call instruction. |
| 167 | II->replaceAllUsesWith(Call); |
| 168 | BasicBlock *UnwindBlock = II->getUnwindDest(); |
| 169 | UnwindBlock->removePredecessor(II->getParent()); |
Jeff Cohen | 00b16889 | 2005-07-27 06:12:32 +0000 | [diff] [blame] | 170 | |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 171 | // Insert a branch to the normal destination right before the |
| 172 | // invoke. |
| 173 | new BranchInst(II->getNormalDest(), II); |
Jeff Cohen | 00b16889 | 2005-07-27 06:12:32 +0000 | [diff] [blame] | 174 | |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 175 | // Finally, delete the invoke instruction! |
| 176 | BB->getInstList().pop_back(); |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 177 | |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 178 | // If the unwind block is now dead, nuke it. |
| 179 | if (pred_begin(UnwindBlock) == pred_end(UnwindBlock)) |
| 180 | DeleteBasicBlock(UnwindBlock); // Delete the new BB. |
Jeff Cohen | 00b16889 | 2005-07-27 06:12:32 +0000 | [diff] [blame] | 181 | |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 182 | ++NumRemoved; |
| 183 | MadeChange = true; |
| 184 | } |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 185 | |
Chris Lattner | 209a0ae | 2005-04-27 20:12:17 +0000 | [diff] [blame] | 186 | for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 187 | if (CallInst *CI = dyn_cast<CallInst>(I++)) |
Duncan Sands | 2b0e899 | 2007-12-18 09:59:50 +0000 | [diff] [blame] | 188 | if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) { |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 189 | // This call calls a function that cannot return. Insert an |
| 190 | // unreachable instruction after it and simplify the code. Do this |
| 191 | // by splitting the BB, adding the unreachable, then deleting the |
| 192 | // new BB. |
| 193 | BasicBlock *New = BB->splitBasicBlock(I); |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 194 | |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 195 | // Remove the uncond branch and add an unreachable. |
| 196 | BB->getInstList().pop_back(); |
| 197 | new UnreachableInst(BB); |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 198 | |
Duncan Sands | cbb8bad | 2007-12-10 19:09:40 +0000 | [diff] [blame] | 199 | DeleteBasicBlock(New); // Delete the new BB. |
| 200 | MadeChange = true; |
| 201 | ++NumUnreach; |
| 202 | break; |
| 203 | } |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 204 | |
| 205 | } |
| 206 | return MadeChange; |
| 207 | } |
| 208 | |
| 209 | /// DeleteBasicBlock - remove the specified basic block from the program, |
| 210 | /// updating the callgraph to reflect any now-obsolete edges due to calls that |
| 211 | /// exist in the BB. |
| 212 | void PruneEH::DeleteBasicBlock(BasicBlock *BB) { |
| 213 | assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!"); |
| 214 | CallGraph &CG = getAnalysis<CallGraph>(); |
| 215 | |
| 216 | CallGraphNode *CGN = CG[BB->getParent()]; |
| 217 | for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) { |
| 218 | --I; |
| 219 | if (CallInst *CI = dyn_cast<CallInst>(I)) { |
| 220 | if (Function *Callee = CI->getCalledFunction()) |
| 221 | CGN->removeCallEdgeTo(CG[Callee]); |
| 222 | } else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) { |
| 223 | if (Function *Callee = II->getCalledFunction()) |
| 224 | CGN->removeCallEdgeTo(CG[Callee]); |
| 225 | } |
| 226 | if (!I->use_empty()) |
| 227 | I->replaceAllUsesWith(UndefValue::get(I->getType())); |
| 228 | } |
| 229 | |
| 230 | // Get the list of successors of this block. |
| 231 | std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB)); |
| 232 | |
| 233 | for (unsigned i = 0, e = Succs.size(); i != e; ++i) |
| 234 | Succs[i]->removePredecessor(BB); |
Jeff Cohen | 00b16889 | 2005-07-27 06:12:32 +0000 | [diff] [blame] | 235 | |
Chris Lattner | d651f44 | 2005-04-27 04:52:23 +0000 | [diff] [blame] | 236 | BB->eraseFromParent(); |
| 237 | } |