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(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(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 bool MadeChange
= false;
169 for (Function::iterator BB
= F
->begin(), E
= F
->end(); BB
!= E
; ++BB
) {
170 if (InvokeInst
*II
= dyn_cast
<InvokeInst
>(BB
->getTerminator()))
171 if (II
->doesNotThrow()) {
172 SmallVector
<Value
*, 8> Args(II
->op_begin()+3, II
->op_end());
173 // Insert a call instruction before the invoke.
174 CallInst
*Call
= CallInst::Create(II
->getCalledValue(),
175 Args
.begin(), Args
.end(), "", II
);
177 Call
->setCallingConv(II
->getCallingConv());
178 Call
->setAttributes(II
->getAttributes());
180 // Anything that used the value produced by the invoke instruction
181 // now uses the value produced by the call instruction. Note that we
182 // do this even for void functions and calls with no uses so that the
183 // callgraph edge is updated.
184 II
->replaceAllUsesWith(Call
);
185 BasicBlock
*UnwindBlock
= II
->getUnwindDest();
186 UnwindBlock
->removePredecessor(II
->getParent());
188 // Insert a branch to the normal destination right before the
190 BranchInst::Create(II
->getNormalDest(), II
);
192 // Finally, delete the invoke instruction!
193 BB
->getInstList().pop_back();
195 // If the unwind block is now dead, nuke it.
196 if (pred_begin(UnwindBlock
) == pred_end(UnwindBlock
))
197 DeleteBasicBlock(UnwindBlock
); // Delete the new BB.
203 for (BasicBlock::iterator I
= BB
->begin(), E
= BB
->end(); I
!= E
; )
204 if (CallInst
*CI
= dyn_cast
<CallInst
>(I
++))
205 if (CI
->doesNotReturn() && !isa
<UnreachableInst
>(I
)) {
206 // This call calls a function that cannot return. Insert an
207 // unreachable instruction after it and simplify the code. Do this
208 // by splitting the BB, adding the unreachable, then deleting the
210 BasicBlock
*New
= BB
->splitBasicBlock(I
);
212 // Remove the uncond branch and add an unreachable.
213 BB
->getInstList().pop_back();
214 new UnreachableInst(BB
->getContext(), BB
);
216 DeleteBasicBlock(New
); // Delete the new BB.
226 /// DeleteBasicBlock - remove the specified basic block from the program,
227 /// updating the callgraph to reflect any now-obsolete edges due to calls that
229 void PruneEH::DeleteBasicBlock(BasicBlock
*BB
) {
230 assert(pred_begin(BB
) == pred_end(BB
) && "BB is not dead!");
231 CallGraph
&CG
= getAnalysis
<CallGraph
>();
233 CallGraphNode
*CGN
= CG
[BB
->getParent()];
234 for (BasicBlock::iterator I
= BB
->end(), E
= BB
->begin(); I
!= E
; ) {
236 if (CallInst
*CI
= dyn_cast
<CallInst
>(I
)) {
237 if (!isa
<DbgInfoIntrinsic
>(I
))
238 CGN
->removeCallEdgeFor(CI
);
239 } else if (InvokeInst
*II
= dyn_cast
<InvokeInst
>(I
))
240 CGN
->removeCallEdgeFor(II
);
242 I
->replaceAllUsesWith(UndefValue::get(I
->getType()));
245 // Get the list of successors of this block.
246 std::vector
<BasicBlock
*> Succs(succ_begin(BB
), succ_end(BB
));
248 for (unsigned i
= 0, e
= Succs
.size(); i
!= e
; ++i
)
249 Succs
[i
]->removePredecessor(BB
);
251 BB
->eraseFromParent();