PruneEH.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
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#include "llvm/Transforms/IPO.h" 18#include "llvm/ADT/SmallPtrSet.h" 19#include "llvm/ADT/SmallVector.h" 20#include "llvm/ADT/Statistic.h" 21#include "llvm/Analysis/CallGraph.h" 22#include "llvm/Analysis/CallGraphSCCPass.h" 23#include "llvm/IR/CFG.h" 24#include "llvm/IR/Constants.h" 25#include "llvm/IR/Function.h" 26#include "llvm/IR/Instructions.h" 27#include "llvm/IR/IntrinsicInst.h" 28#include "llvm/IR/LLVMContext.h" 29#include <algorithm> 30using namespace llvm; 31 32#define DEBUG_TYPE "prune-eh" 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 initializePruneEHPass(*PassRegistry::getPassRegistry()); 42 } 43 44 // runOnSCC - Analyze the SCC, performing the transformation if possible. 45 bool runOnSCC(CallGraphSCC &SCC) override; 46 47 bool SimplifyFunction(Function *F); 48 void DeleteBasicBlock(BasicBlock *BB); 49 }; 50} 51 52char PruneEH::ID = 0; 53INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh", 54 "Remove unused exception handling info", false, false) 55INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) 56INITIALIZE_PASS_END(PruneEH, "prune-eh", 57 "Remove unused exception handling info", false, false) 58 59Pass *llvm::createPruneEHPass() { return new PruneEH(); } 60 61 62bool PruneEH::runOnSCC(CallGraphSCC &SCC) { 63 SmallPtrSet<CallGraphNode *, 8> SCCNodes; 64 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph(); 65 bool MadeChange = false; 66 67 // Fill SCCNodes with the elements of the SCC. Used for quickly 68 // looking up whether a given CallGraphNode is in this SCC. 69 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 70 SCCNodes.insert(*I); 71 72 // First pass, scan all of the functions in the SCC, simplifying them 73 // according to what we know. 74 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 75 if (Function *F = (*I)->getFunction()) 76 MadeChange |= SimplifyFunction(F); 77 78 // Next, check to see if any callees might throw or if there are any external 79 // functions in this SCC: if so, we cannot prune any functions in this SCC. 80 // Definitions that are weak and not declared non-throwing might be 81 // overridden at linktime with something that throws, so assume that. 82 // If this SCC includes the unwind instruction, we KNOW it throws, so 83 // obviously the SCC might throw. 84 // 85 bool SCCMightUnwind = false, SCCMightReturn = false; 86 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); 87 (!SCCMightUnwind || !SCCMightReturn) && I != E; ++I) { 88 Function *F = (*I)->getFunction(); 89 if (!F) { 90 SCCMightUnwind = true; 91 SCCMightReturn = true; 92 } else if (F->isDeclaration() || F->mayBeOverridden()) { 93 SCCMightUnwind |= !F->doesNotThrow(); 94 SCCMightReturn |= !F->doesNotReturn(); 95 } else { 96 bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow(); 97 bool CheckReturn = !SCCMightReturn && !F->doesNotReturn(); 98 99 if (!CheckUnwind && !CheckReturn) 100 continue; 101 102 // Check to see if this function performs an unwind or calls an 103 // unwinding function. 104 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 105 if (CheckUnwind && 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 AttrBuilder NewAttributes; 142 143 if (!SCCMightUnwind) 144 NewAttributes.addAttribute(Attribute::NoUnwind); 145 if (!SCCMightReturn) 146 NewAttributes.addAttribute(Attribute::NoReturn); 147 148 Function *F = (*I)->getFunction(); 149 const AttributeSet &PAL = F->getAttributes().getFnAttributes(); 150 const AttributeSet &NPAL = AttributeSet::get( 151 F->getContext(), AttributeSet::FunctionIndex, NewAttributes); 152 153 if (PAL != NPAL) { 154 MadeChange = true; 155 F->addAttributes(AttributeSet::FunctionIndex, NPAL); 156 } 157 } 158 159 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 160 // Convert any invoke instructions to non-throwing functions in this node 161 // into call instructions with a branch. This makes the exception blocks 162 // dead. 163 if (Function *F = (*I)->getFunction()) 164 MadeChange |= SimplifyFunction(F); 165 } 166 167 return MadeChange; 168} 169 170 171// SimplifyFunction - Given information about callees, simplify the specified 172// function if we have invokes to non-unwinding functions or code after calls to 173// no-return functions. 174bool PruneEH::SimplifyFunction(Function *F) { 175 bool MadeChange = false; 176 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 177 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) 178 if (II->doesNotThrow()) { 179 SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3); 180 // Insert a call instruction before the invoke. 181 CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II); 182 Call->takeName(II); 183 Call->setCallingConv(II->getCallingConv()); 184 Call->setAttributes(II->getAttributes()); 185 Call->setDebugLoc(II->getDebugLoc()); 186 187 // Anything that used the value produced by the invoke instruction 188 // now uses the value produced by the call instruction. Note that we 189 // do this even for void functions and calls with no uses so that the 190 // callgraph edge is updated. 191 II->replaceAllUsesWith(Call); 192 BasicBlock *UnwindBlock = II->getUnwindDest(); 193 UnwindBlock->removePredecessor(II->getParent()); 194 195 // Insert a branch to the normal destination right before the 196 // invoke. 197 BranchInst::Create(II->getNormalDest(), II); 198 199 // Finally, delete the invoke instruction! 200 BB->getInstList().pop_back(); 201 202 // If the unwind block is now dead, nuke it. 203 if (pred_begin(UnwindBlock) == pred_end(UnwindBlock)) 204 DeleteBasicBlock(UnwindBlock); // Delete the new BB. 205 206 ++NumRemoved; 207 MadeChange = true; 208 } 209 210 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) 211 if (CallInst *CI = dyn_cast<CallInst>(I++)) 212 if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) { 213 // This call calls a function that cannot return. Insert an 214 // unreachable instruction after it and simplify the code. Do this 215 // by splitting the BB, adding the unreachable, then deleting the 216 // new BB. 217 BasicBlock *New = BB->splitBasicBlock(I); 218 219 // Remove the uncond branch and add an unreachable. 220 BB->getInstList().pop_back(); 221 new UnreachableInst(BB->getContext(), BB); 222 223 DeleteBasicBlock(New); // Delete the new BB. 224 MadeChange = true; 225 ++NumUnreach; 226 break; 227 } 228 } 229 230 return MadeChange; 231} 232 233/// DeleteBasicBlock - remove the specified basic block from the program, 234/// updating the callgraph to reflect any now-obsolete edges due to calls that 235/// exist in the BB. 236void PruneEH::DeleteBasicBlock(BasicBlock *BB) { 237 assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!"); 238 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph(); 239 240 CallGraphNode *CGN = CG[BB->getParent()]; 241 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) { 242 --I; 243 if (CallInst *CI = dyn_cast<CallInst>(I)) { 244 if (!isa<IntrinsicInst>(I)) 245 CGN->removeCallEdgeFor(CI); 246 } else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 247 CGN->removeCallEdgeFor(II); 248 if (!I->use_empty()) 249 I->replaceAllUsesWith(UndefValue::get(I->getType())); 250 } 251 252 // Get the list of successors of this block. 253 std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB)); 254 255 for (unsigned i = 0, e = Succs.size(); i != e; ++i) 256 Succs[i]->removePredecessor(BB); 257 258 BB->eraseFromParent(); 259} 260