1 //===- PruneEH.cpp - Pass which deletes unused exception handlers ---------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
15 //===----------------------------------------------------------------------===//
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 "llvm/Support/Compiler.h"
35 STATISTIC(NumRemoved, "Number of invokes removed");
36 STATISTIC(NumUnreach, "Number of noreturn calls optimized");
39 struct VISIBILITY_HIDDEN PruneEH : public CallGraphSCCPass {
40 static char ID; // Pass identification, replacement for typeid
41 PruneEH() : CallGraphSCCPass(&ID) {}
43 // runOnSCC - Analyze the SCC, performing the transformation if possible.
44 bool runOnSCC(const std::vector<CallGraphNode *> &SCC);
46 bool SimplifyFunction(Function *F);
47 void DeleteBasicBlock(BasicBlock *BB);
52 static RegisterPass<PruneEH>
53 X("prune-eh", "Remove unused exception handling info");
55 Pass *llvm::createPruneEHPass() { return new PruneEH(); }
58 bool PruneEH::runOnSCC(const std::vector<CallGraphNode *> &SCC) {
59 SmallPtrSet<CallGraphNode *, 8> SCCNodes;
60 CallGraph &CG = getAnalysis<CallGraph>();
61 bool MadeChange = false;
63 // Fill SCCNodes with the elements of the SCC. Used for quickly
64 // looking up whether a given CallGraphNode is in this SCC.
65 for (unsigned i = 0, e = SCC.size(); i != e; ++i)
66 SCCNodes.insert(SCC[i]);
68 // First pass, scan all of the functions in the SCC, simplifying them
69 // according to what we know.
70 for (unsigned i = 0, e = SCC.size(); i != e; ++i)
71 if (Function *F = SCC[i]->getFunction())
72 MadeChange |= SimplifyFunction(F);
74 // Next, check to see if any callees might throw or if there are any external
75 // functions in this SCC: if so, we cannot prune any functions in this SCC.
76 // Definitions that are weak and not declared non-throwing might be
77 // overridden at linktime with something that throws, so assume that.
78 // If this SCC includes the unwind instruction, we KNOW it throws, so
79 // obviously the SCC might throw.
81 bool SCCMightUnwind = false, SCCMightReturn = false;
82 for (unsigned i = 0, e = SCC.size();
83 (!SCCMightUnwind || !SCCMightReturn) && i != e; ++i) {
84 Function *F = SCC[i]->getFunction();
86 SCCMightUnwind = true;
87 SCCMightReturn = true;
88 } else if (F->isDeclaration() || F->mayBeOverridden()) {
89 SCCMightUnwind |= !F->doesNotThrow();
90 SCCMightReturn |= !F->doesNotReturn();
92 bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow();
93 bool CheckReturn = !SCCMightReturn && !F->doesNotReturn();
95 if (!CheckUnwind && !CheckReturn)
98 // Check to see if this function performs an unwind or calls an
99 // unwinding function.
100 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
101 if (CheckUnwind && isa<UnwindInst>(BB->getTerminator())) {
103 SCCMightUnwind = true;
104 } else if (CheckReturn && isa<ReturnInst>(BB->getTerminator())) {
105 SCCMightReturn = true;
108 // Invoke instructions don't allow unwinding to continue, so we are
109 // only interested in call instructions.
110 if (CheckUnwind && !SCCMightUnwind)
111 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
112 if (CallInst *CI = dyn_cast<CallInst>(I)) {
113 if (CI->doesNotThrow()) {
114 // This call cannot throw.
115 } else if (Function *Callee = CI->getCalledFunction()) {
116 CallGraphNode *CalleeNode = CG[Callee];
117 // If the callee is outside our current SCC then we may
118 // throw because it might.
119 if (!SCCNodes.count(CalleeNode)) {
120 SCCMightUnwind = true;
124 // Indirect call, it might throw.
125 SCCMightUnwind = true;
129 if (SCCMightUnwind && SCCMightReturn) break;
134 // If the SCC doesn't unwind or doesn't throw, note this fact.
135 if (!SCCMightUnwind || !SCCMightReturn)
136 for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
137 Attributes NewAttributes = Attribute::None;
140 NewAttributes |= Attribute::NoUnwind;
142 NewAttributes |= Attribute::NoReturn;
144 const AttrListPtr &PAL = SCC[i]->getFunction()->getAttributes();
145 const AttrListPtr &NPAL = PAL.addAttr(~0, NewAttributes);
148 SCC[i]->getFunction()->setAttributes(NPAL);
152 for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
153 // Convert any invoke instructions to non-throwing functions in this node
154 // into call instructions with a branch. This makes the exception blocks
156 if (Function *F = SCC[i]->getFunction())
157 MadeChange |= SimplifyFunction(F);
164 // SimplifyFunction - Given information about callees, simplify the specified
165 // function if we have invokes to non-unwinding functions or code after calls to
166 // no-return functions.
167 bool PruneEH::SimplifyFunction(Function *F) {
168 CallGraph &CG = getAnalysis<CallGraph>();
169 CallGraphNode *CGN = CG[F];
171 bool MadeChange = false;
172 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
173 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
174 if (II->doesNotThrow()) {
175 SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end());
176 // Insert a call instruction before the invoke.
177 CallInst *Call = CallInst::Create(II->getCalledValue(),
178 Args.begin(), Args.end(), "", II);
180 Call->setCallingConv(II->getCallingConv());
181 Call->setAttributes(II->getAttributes());
183 // Anything that used the value produced by the invoke instruction
184 // now uses the value produced by the call instruction.
185 II->replaceAllUsesWith(Call);
186 BasicBlock *UnwindBlock = II->getUnwindDest();
187 UnwindBlock->removePredecessor(II->getParent());
189 // Fix up the call graph.
190 CGN->replaceCallSite(II, Call);
192 // Insert a branch to the normal destination right before the
194 BranchInst::Create(II->getNormalDest(), II);
196 // Finally, delete the invoke instruction!
197 BB->getInstList().pop_back();
199 // If the unwind block is now dead, nuke it.
200 if (pred_begin(UnwindBlock) == pred_end(UnwindBlock))
201 DeleteBasicBlock(UnwindBlock); // Delete the new BB.
207 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
208 if (CallInst *CI = dyn_cast<CallInst>(I++))
209 if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) {
210 // This call calls a function that cannot return. Insert an
211 // unreachable instruction after it and simplify the code. Do this
212 // by splitting the BB, adding the unreachable, then deleting the
214 BasicBlock *New = BB->splitBasicBlock(I);
216 // Remove the uncond branch and add an unreachable.
217 BB->getInstList().pop_back();
218 new UnreachableInst(BB);
220 DeleteBasicBlock(New); // Delete the new BB.
230 /// DeleteBasicBlock - remove the specified basic block from the program,
231 /// updating the callgraph to reflect any now-obsolete edges due to calls that
233 void PruneEH::DeleteBasicBlock(BasicBlock *BB) {
234 assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!");
235 CallGraph &CG = getAnalysis<CallGraph>();
237 CallGraphNode *CGN = CG[BB->getParent()];
238 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
240 if (CallInst *CI = dyn_cast<CallInst>(I)) {
241 if (!isa<DbgInfoIntrinsic>(I))
242 CGN->removeCallEdgeFor(CI);
243 } else if (InvokeInst *II = dyn_cast<InvokeInst>(I))
244 CGN->removeCallEdgeFor(II);
246 I->replaceAllUsesWith(UndefValue::get(I->getType()));
249 // Get the list of successors of this block.
250 std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));
252 for (unsigned i = 0, e = Succs.size(); i != e; ++i)
253 Succs[i]->removePredecessor(BB);
255 BB->eraseFromParent();