PruneEH.cpp revision 193323
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/Instructions.h" 23#include "llvm/IntrinsicInst.h" 24#include "llvm/Analysis/CallGraph.h" 25#include "llvm/ADT/SmallPtrSet.h" 26#include "llvm/ADT/SmallVector.h" 27#include "llvm/ADT/Statistic.h" 28#include "llvm/Support/CFG.h" 29#include "llvm/Support/Compiler.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 VISIBILITY_HIDDEN 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(const 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(const 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 CallGraph &CG = getAnalysis<CallGraph>(); 168 CallGraphNode *CGN = CG[F]; 169 170 bool MadeChange = false; 171 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 172 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) 173 if (II->doesNotThrow()) { 174 SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); 175 // Insert a call instruction before the invoke. 176 CallInst *Call = CallInst::Create(II->getCalledValue(), 177 Args.begin(), Args.end(), "", II); 178 Call->takeName(II); 179 Call->setCallingConv(II->getCallingConv()); 180 Call->setAttributes(II->getAttributes()); 181 182 // Anything that used the value produced by the invoke instruction 183 // now uses the value produced by the call instruction. 184 II->replaceAllUsesWith(Call); 185 BasicBlock *UnwindBlock = II->getUnwindDest(); 186 UnwindBlock->removePredecessor(II->getParent()); 187 188 // Fix up the call graph. 189 CGN->replaceCallSite(II, Call); 190 191 // Insert a branch to the normal destination right before the 192 // invoke. 193 BranchInst::Create(II->getNormalDest(), II); 194 195 // Finally, delete the invoke instruction! 196 BB->getInstList().pop_back(); 197 198 // If the unwind block is now dead, nuke it. 199 if (pred_begin(UnwindBlock) == pred_end(UnwindBlock)) 200 DeleteBasicBlock(UnwindBlock); // Delete the new BB. 201 202 ++NumRemoved; 203 MadeChange = true; 204 } 205 206 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) 207 if (CallInst *CI = dyn_cast<CallInst>(I++)) 208 if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) { 209 // This call calls a function that cannot return. Insert an 210 // unreachable instruction after it and simplify the code. Do this 211 // by splitting the BB, adding the unreachable, then deleting the 212 // new BB. 213 BasicBlock *New = BB->splitBasicBlock(I); 214 215 // Remove the uncond branch and add an unreachable. 216 BB->getInstList().pop_back(); 217 new UnreachableInst(BB); 218 219 DeleteBasicBlock(New); // Delete the new BB. 220 MadeChange = true; 221 ++NumUnreach; 222 break; 223 } 224 } 225 226 return MadeChange; 227} 228 229/// DeleteBasicBlock - remove the specified basic block from the program, 230/// updating the callgraph to reflect any now-obsolete edges due to calls that 231/// exist in the BB. 232void PruneEH::DeleteBasicBlock(BasicBlock *BB) { 233 assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!"); 234 CallGraph &CG = getAnalysis<CallGraph>(); 235 236 CallGraphNode *CGN = CG[BB->getParent()]; 237 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) { 238 --I; 239 if (CallInst *CI = dyn_cast<CallInst>(I)) { 240 if (!isa<DbgInfoIntrinsic>(I)) 241 CGN->removeCallEdgeFor(CI); 242 } else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 243 CGN->removeCallEdgeFor(II); 244 if (!I->use_empty()) 245 I->replaceAllUsesWith(UndefValue::get(I->getType())); 246 } 247 248 // Get the list of successors of this block. 249 std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB)); 250 251 for (unsigned i = 0, e = Succs.size(); i != e; ++i) 252 Succs[i]->removePredecessor(BB); 253 254 BB->eraseFromParent(); 255} 256