]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/Transforms/IPO/PruneEH.cpp
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"
33 STATISTIC(NumRemoved
, "Number of invokes removed");
34 STATISTIC(NumUnreach
, "Number of noreturn calls optimized");
37 struct PruneEH
: public CallGraphSCCPass
{
38 static char ID
; // Pass identification, replacement for typeid
39 PruneEH() : CallGraphSCCPass(ID
) {
40 initializePruneEHPass(*PassRegistry::getPassRegistry());
43 // runOnSCC - Analyze the SCC, performing the transformation if possible.
44 bool runOnSCC(CallGraphSCC
&SCC
);
46 bool SimplifyFunction(Function
*F
);
47 void DeleteBasicBlock(BasicBlock
*BB
);
52 INITIALIZE_PASS_BEGIN(PruneEH
, "prune-eh",
53 "Remove unused exception handling info", false, false)
54 INITIALIZE_AG_DEPENDENCY(CallGraph
)
55 INITIALIZE_PASS_END(PruneEH
, "prune-eh",
56 "Remove unused exception handling info", false, false)
58 Pass
*llvm::createPruneEHPass() { return new PruneEH(); }
61 bool PruneEH::runOnSCC(CallGraphSCC
&SCC
) {
62 SmallPtrSet
<CallGraphNode
*, 8> SCCNodes
;
63 CallGraph
&CG
= getAnalysis
<CallGraph
>();
64 bool MadeChange
= false;
66 // Fill SCCNodes with the elements of the SCC. Used for quickly
67 // looking up whether a given CallGraphNode is in this SCC.
68 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
)
71 // First pass, scan all of the functions in the SCC, simplifying them
72 // according to what we know.
73 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
)
74 if (Function
*F
= (*I
)->getFunction())
75 MadeChange
|= SimplifyFunction(F
);
77 // Next, check to see if any callees might throw or if there are any external
78 // functions in this SCC: if so, we cannot prune any functions in this SCC.
79 // Definitions that are weak and not declared non-throwing might be
80 // overridden at linktime with something that throws, so assume that.
81 // If this SCC includes the unwind instruction, we KNOW it throws, so
82 // obviously the SCC might throw.
84 bool SCCMightUnwind
= false, SCCMightReturn
= false;
85 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end();
86 (!SCCMightUnwind
|| !SCCMightReturn
) && I
!= E
; ++I
) {
87 Function
*F
= (*I
)->getFunction();
89 SCCMightUnwind
= true;
90 SCCMightReturn
= true;
91 } else if (F
->isDeclaration() || F
->mayBeOverridden()) {
92 SCCMightUnwind
|= !F
->doesNotThrow();
93 SCCMightReturn
|= !F
->doesNotReturn();
95 bool CheckUnwind
= !SCCMightUnwind
&& !F
->doesNotThrow();
96 bool CheckReturn
= !SCCMightReturn
&& !F
->doesNotReturn();
98 if (!CheckUnwind
&& !CheckReturn
)
101 // Check to see if this function performs an unwind or calls an
102 // unwinding function.
103 for (Function::iterator BB
= F
->begin(), E
= F
->end(); BB
!= E
; ++BB
) {
104 if (CheckUnwind
&& isa
<ResumeInst
>(BB
->getTerminator())) {
105 // Uses unwind / resume!
106 SCCMightUnwind
= true;
107 } else if (CheckReturn
&& isa
<ReturnInst
>(BB
->getTerminator())) {
108 SCCMightReturn
= true;
111 // Invoke instructions don't allow unwinding to continue, so we are
112 // only interested in call instructions.
113 if (CheckUnwind
&& !SCCMightUnwind
)
114 for (BasicBlock::iterator I
= BB
->begin(), E
= BB
->end(); I
!= E
; ++I
)
115 if (CallInst
*CI
= dyn_cast
<CallInst
>(I
)) {
116 if (CI
->doesNotThrow()) {
117 // This call cannot throw.
118 } else if (Function
*Callee
= CI
->getCalledFunction()) {
119 CallGraphNode
*CalleeNode
= CG
[Callee
];
120 // If the callee is outside our current SCC then we may
121 // throw because it might.
122 if (!SCCNodes
.count(CalleeNode
)) {
123 SCCMightUnwind
= true;
127 // Indirect call, it might throw.
128 SCCMightUnwind
= true;
132 if (SCCMightUnwind
&& SCCMightReturn
) break;
137 // If the SCC doesn't unwind or doesn't throw, note this fact.
138 if (!SCCMightUnwind
|| !SCCMightReturn
)
139 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
140 Attributes NewAttributes
= Attribute::None
;
143 NewAttributes
|= Attribute::NoUnwind
;
145 NewAttributes
|= Attribute::NoReturn
;
147 Function
*F
= (*I
)->getFunction();
148 const AttrListPtr
&PAL
= F
->getAttributes();
149 const AttrListPtr
&NPAL
= PAL
.addAttr(~0, NewAttributes
);
152 F
->setAttributes(NPAL
);
156 for (CallGraphSCC::iterator I
= SCC
.begin(), E
= SCC
.end(); I
!= E
; ++I
) {
157 // Convert any invoke instructions to non-throwing functions in this node
158 // into call instructions with a branch. This makes the exception blocks
160 if (Function
*F
= (*I
)->getFunction())
161 MadeChange
|= SimplifyFunction(F
);
168 // SimplifyFunction - Given information about callees, simplify the specified
169 // function if we have invokes to non-unwinding functions or code after calls to
170 // no-return functions.
171 bool PruneEH::SimplifyFunction(Function
*F
) {
172 bool MadeChange
= false;
173 for (Function::iterator BB
= F
->begin(), E
= F
->end(); BB
!= E
; ++BB
) {
174 if (InvokeInst
*II
= dyn_cast
<InvokeInst
>(BB
->getTerminator()))
175 if (II
->doesNotThrow()) {
176 SmallVector
<Value
*, 8> Args(II
->op_begin(), II
->op_end() - 3);
177 // Insert a call instruction before the invoke.
178 CallInst
*Call
= CallInst::Create(II
->getCalledValue(), Args
, "", II
);
180 Call
->setCallingConv(II
->getCallingConv());
181 Call
->setAttributes(II
->getAttributes());
182 Call
->setDebugLoc(II
->getDebugLoc());
184 // Anything that used the value produced by the invoke instruction
185 // now uses the value produced by the call instruction. Note that we
186 // do this even for void functions and calls with no uses so that the
187 // callgraph edge is updated.
188 II
->replaceAllUsesWith(Call
);
189 BasicBlock
*UnwindBlock
= II
->getUnwindDest();
190 UnwindBlock
->removePredecessor(II
->getParent());
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
->getContext(), 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
<IntrinsicInst
>(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();