PruneEH.cpp revision e02ef8a6fcc83c39068e2baf33c7f55e4a5c9c20
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(std::vector<CallGraphNode *> &SCC); 44 45 bool SimplifyFunction(Function *F); 46 void DeleteBasicBlock(BasicBlock *BB); 47 }; 48} 49 50char PruneEH::ID = 0; 51static RegisterPass<PruneEH> 52X("prune-eh", "Remove unused exception handling info"); 53 54Pass *llvm::createPruneEHPass() { return new PruneEH(); } 55 56 57bool PruneEH::runOnSCC(std::vector<CallGraphNode *> &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 (unsigned i = 0, e = SCC.size(); i != e; ++i) 65 SCCNodes.insert(SCC[i]); 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 // 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 (unsigned i = 0, e = SCC.size(); 82 (!SCCMightUnwind || !SCCMightReturn) && i != e; ++i) { 83 Function *F = SCC[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 (unsigned i = 0, e = SCC.size(); 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 const AttrListPtr &PAL = SCC[i]->getFunction()->getAttributes(); 144 const AttrListPtr &NPAL = PAL.addAttr(~0, NewAttributes); 145 if (PAL != NPAL) { 146 MadeChange = true; 147 SCC[i]->getFunction()->setAttributes(NPAL); 148 } 149 } 150 151 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 152 // Convert any invoke instructions to non-throwing functions in this node 153 // into call instructions with a branch. This makes the exception blocks 154 // dead. 155 if (Function *F = SCC[i]->getFunction()) 156 MadeChange |= SimplifyFunction(F); 157 } 158 159 return MadeChange; 160} 161 162 163// SimplifyFunction - Given information about callees, simplify the specified 164// function if we have invokes to non-unwinding functions or code after calls to 165// no-return functions. 166bool PruneEH::SimplifyFunction(Function *F) { 167 bool MadeChange = false; 168 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 169 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) 170 if (II->doesNotThrow()) { 171 SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); 172 // Insert a call instruction before the invoke. 173 CallInst *Call = CallInst::Create(II->getCalledValue(), 174 Args.begin(), Args.end(), "", II); 175 Call->takeName(II); 176 Call->setCallingConv(II->getCallingConv()); 177 Call->setAttributes(II->getAttributes()); 178 179 // Anything that used the value produced by the invoke instruction 180 // now uses the value produced by the call instruction. Note that we 181 // do this even for void functions and calls with no uses so that the 182 // callgraph edge is updated. 183 II->replaceAllUsesWith(Call); 184 BasicBlock *UnwindBlock = II->getUnwindDest(); 185 UnwindBlock->removePredecessor(II->getParent()); 186 187 // Insert a branch to the normal destination right before the 188 // invoke. 189 BranchInst::Create(II->getNormalDest(), II); 190 191 // Finally, delete the invoke instruction! 192 BB->getInstList().pop_back(); 193 194 // If the unwind block is now dead, nuke it. 195 if (pred_begin(UnwindBlock) == pred_end(UnwindBlock)) 196 DeleteBasicBlock(UnwindBlock); // Delete the new BB. 197 198 ++NumRemoved; 199 MadeChange = true; 200 } 201 202 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) 203 if (CallInst *CI = dyn_cast<CallInst>(I++)) 204 if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) { 205 // This call calls a function that cannot return. Insert an 206 // unreachable instruction after it and simplify the code. Do this 207 // by splitting the BB, adding the unreachable, then deleting the 208 // new BB. 209 BasicBlock *New = BB->splitBasicBlock(I); 210 211 // Remove the uncond branch and add an unreachable. 212 BB->getInstList().pop_back(); 213 new UnreachableInst(BB->getContext(), BB); 214 215 DeleteBasicBlock(New); // Delete the new BB. 216 MadeChange = true; 217 ++NumUnreach; 218 break; 219 } 220 } 221 222 return MadeChange; 223} 224 225/// DeleteBasicBlock - remove the specified basic block from the program, 226/// updating the callgraph to reflect any now-obsolete edges due to calls that 227/// exist in the BB. 228void PruneEH::DeleteBasicBlock(BasicBlock *BB) { 229 assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!"); 230 CallGraph &CG = getAnalysis<CallGraph>(); 231 232 CallGraphNode *CGN = CG[BB->getParent()]; 233 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) { 234 --I; 235 if (CallInst *CI = dyn_cast<CallInst>(I)) { 236 if (!isa<DbgInfoIntrinsic>(I)) 237 CGN->removeCallEdgeFor(CI); 238 } else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 239 CGN->removeCallEdgeFor(II); 240 if (!I->use_empty()) 241 I->replaceAllUsesWith(UndefValue::get(I->getType())); 242 } 243 244 // Get the list of successors of this block. 245 std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB)); 246 247 for (unsigned i = 0, e = Succs.size(); i != e; ++i) 248 Succs[i]->removePredecessor(BB); 249 250 BB->eraseFromParent(); 251} 252