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/Support/raw_ostream.h"
22 #include "llvm/Analysis/CallGraph.h"
23 #include "llvm/Analysis/CallGraphSCCPass.h"
24 #include "llvm/Analysis/LibCallSemantics.h"
25 #include "llvm/IR/CFG.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/IR/InlineAsm.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/IntrinsicInst.h"
31 #include "llvm/IR/LLVMContext.h"
32 #include <algorithm>
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "prune-eh"
36 
37 STATISTIC(NumRemoved, "Number of invokes removed");
38 STATISTIC(NumUnreach, "Number of noreturn calls optimized");
39 
40 namespace {
41   struct PruneEH : public CallGraphSCCPass {
42     static char ID; // Pass identification, replacement for typeid
43     PruneEH() : CallGraphSCCPass(ID) {
44       initializePruneEHPass(*PassRegistry::getPassRegistry());
45     }
46 
47     // runOnSCC - Analyze the SCC, performing the transformation if possible.
48     bool runOnSCC(CallGraphSCC &SCC) override;
49 
50     bool SimplifyFunction(Function *F);
51     void DeleteBasicBlock(BasicBlock *BB);
52   };
53 }
54 
55 char PruneEH::ID = 0;
56 INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh",
57                 "Remove unused exception handling info", false, false)
58 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
59 INITIALIZE_PASS_END(PruneEH, "prune-eh",
60                 "Remove unused exception handling info", false, false)
61 
62 Pass *llvm::createPruneEHPass() { return new PruneEH(); }
63 
64 
65 bool PruneEH::runOnSCC(CallGraphSCC &SCC) {
66   SmallPtrSet<CallGraphNode *, 8> SCCNodes;
67   CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
68   bool MadeChange = false;
69 
70   // Fill SCCNodes with the elements of the SCC.  Used for quickly
71   // looking up whether a given CallGraphNode is in this SCC.
72   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
73     SCCNodes.insert(*I);
74 
75   // First pass, scan all of the functions in the SCC, simplifying them
76   // according to what we know.
77   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
78     if (Function *F = (*I)->getFunction())
79       MadeChange |= SimplifyFunction(F);
80 
81   // Next, check to see if any callees might throw or if there are any external
82   // functions in this SCC: if so, we cannot prune any functions in this SCC.
83   // Definitions that are weak and not declared non-throwing might be
84   // overridden at linktime with something that throws, so assume that.
85   // If this SCC includes the unwind instruction, we KNOW it throws, so
86   // obviously the SCC might throw.
87   //
88   bool SCCMightUnwind = false, SCCMightReturn = false;
89   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end();
90        (!SCCMightUnwind || !SCCMightReturn) && I != E; ++I) {
91     Function *F = (*I)->getFunction();
92     if (!F) {
93       SCCMightUnwind = true;
94       SCCMightReturn = true;
95     } else if (F->isDeclaration() || F->mayBeOverridden()) {
96       SCCMightUnwind |= !F->doesNotThrow();
97       SCCMightReturn |= !F->doesNotReturn();
98     } else {
99       bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow();
100       bool CheckReturn = !SCCMightReturn && !F->doesNotReturn();
101       // Determine if we should scan for InlineAsm in a naked function as it
102       // is the only way to return without a ReturnInst.  Only do this for
103       // no-inline functions as functions which may be inlined cannot
104       // meaningfully return via assembly.
105       bool CheckReturnViaAsm = CheckReturn &&
106                                F->hasFnAttribute(Attribute::Naked) &&
107                                F->hasFnAttribute(Attribute::NoInline);
108 
109       if (!CheckUnwind && !CheckReturn)
110         continue;
111 
112       for (const BasicBlock &BB : *F) {
113         const TerminatorInst *TI = BB.getTerminator();
114         if (CheckUnwind && TI->mayThrow()) {
115           SCCMightUnwind = true;
116         } else if (CheckReturn && isa<ReturnInst>(TI)) {
117           SCCMightReturn = true;
118         }
119 
120         for (const Instruction &I : BB) {
121           if ((!CheckUnwind || SCCMightUnwind) &&
122               (!CheckReturnViaAsm || SCCMightReturn))
123             break;
124 
125           // Check to see if this function performs an unwind or calls an
126           // unwinding function.
127           if (CheckUnwind && !SCCMightUnwind && I.mayThrow()) {
128             bool InstMightUnwind = true;
129             if (const auto *CI = dyn_cast<CallInst>(&I)) {
130               if (Function *Callee = CI->getCalledFunction()) {
131                 CallGraphNode *CalleeNode = CG[Callee];
132                 // If the callee is outside our current SCC then we may throw
133                 // because it might.  If it is inside, do nothing.
134                 if (SCCNodes.count(CalleeNode) > 0)
135                   InstMightUnwind = false;
136               }
137             }
138             SCCMightUnwind |= InstMightUnwind;
139           }
140           if (CheckReturnViaAsm && !SCCMightReturn)
141             if (auto ICS = ImmutableCallSite(&I))
142               if (const auto *IA = dyn_cast<InlineAsm>(ICS.getCalledValue()))
143                 if (IA->hasSideEffects())
144                   SCCMightReturn = true;
145         }
146 
147         if (SCCMightUnwind && SCCMightReturn)
148           break;
149       }
150     }
151   }
152 
153   // If the SCC doesn't unwind or doesn't throw, note this fact.
154   if (!SCCMightUnwind || !SCCMightReturn)
155     for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
156       AttrBuilder NewAttributes;
157 
158       if (!SCCMightUnwind)
159         NewAttributes.addAttribute(Attribute::NoUnwind);
160       if (!SCCMightReturn)
161         NewAttributes.addAttribute(Attribute::NoReturn);
162 
163       Function *F = (*I)->getFunction();
164       const AttributeSet &PAL = F->getAttributes().getFnAttributes();
165       const AttributeSet &NPAL = AttributeSet::get(
166           F->getContext(), AttributeSet::FunctionIndex, NewAttributes);
167 
168       if (PAL != NPAL) {
169         MadeChange = true;
170         F->addAttributes(AttributeSet::FunctionIndex, NPAL);
171       }
172     }
173 
174   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
175     // Convert any invoke instructions to non-throwing functions in this node
176     // into call instructions with a branch.  This makes the exception blocks
177     // dead.
178     if (Function *F = (*I)->getFunction())
179       MadeChange |= SimplifyFunction(F);
180   }
181 
182   return MadeChange;
183 }
184 
185 
186 // SimplifyFunction - Given information about callees, simplify the specified
187 // function if we have invokes to non-unwinding functions or code after calls to
188 // no-return functions.
189 bool PruneEH::SimplifyFunction(Function *F) {
190   bool MadeChange = false;
191   for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
192     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
193       if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(F)) {
194         SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
195         // Insert a call instruction before the invoke.
196         CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II);
197         Call->takeName(II);
198         Call->setCallingConv(II->getCallingConv());
199         Call->setAttributes(II->getAttributes());
200         Call->setDebugLoc(II->getDebugLoc());
201 
202         // Anything that used the value produced by the invoke instruction
203         // now uses the value produced by the call instruction.  Note that we
204         // do this even for void functions and calls with no uses so that the
205         // callgraph edge is updated.
206         II->replaceAllUsesWith(Call);
207         BasicBlock *UnwindBlock = II->getUnwindDest();
208         UnwindBlock->removePredecessor(II->getParent());
209 
210         // Insert a branch to the normal destination right before the
211         // invoke.
212         BranchInst::Create(II->getNormalDest(), II);
213 
214         // Finally, delete the invoke instruction!
215         BB->getInstList().pop_back();
216 
217         // If the unwind block is now dead, nuke it.
218         if (pred_empty(UnwindBlock))
219           DeleteBasicBlock(UnwindBlock);  // Delete the new BB.
220 
221         ++NumRemoved;
222         MadeChange = true;
223       }
224 
225     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
226       if (CallInst *CI = dyn_cast<CallInst>(I++))
227         if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) {
228           // This call calls a function that cannot return.  Insert an
229           // unreachable instruction after it and simplify the code.  Do this
230           // by splitting the BB, adding the unreachable, then deleting the
231           // new BB.
232           BasicBlock *New = BB->splitBasicBlock(I);
233 
234           // Remove the uncond branch and add an unreachable.
235           BB->getInstList().pop_back();
236           new UnreachableInst(BB->getContext(), &*BB);
237 
238           DeleteBasicBlock(New);  // Delete the new BB.
239           MadeChange = true;
240           ++NumUnreach;
241           break;
242         }
243   }
244 
245   return MadeChange;
246 }
247 
248 /// DeleteBasicBlock - remove the specified basic block from the program,
249 /// updating the callgraph to reflect any now-obsolete edges due to calls that
250 /// exist in the BB.
251 void PruneEH::DeleteBasicBlock(BasicBlock *BB) {
252   assert(pred_empty(BB) && "BB is not dead!");
253   CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
254 
255   CallGraphNode *CGN = CG[BB->getParent()];
256   for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
257     --I;
258     if (CallInst *CI = dyn_cast<CallInst>(I)) {
259       if (!isa<IntrinsicInst>(I))
260         CGN->removeCallEdgeFor(CI);
261     } else if (InvokeInst *II = dyn_cast<InvokeInst>(I))
262       CGN->removeCallEdgeFor(II);
263     if (!I->use_empty())
264       I->replaceAllUsesWith(UndefValue::get(I->getType()));
265   }
266 
267   // Get the list of successors of this block.
268   std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));
269 
270   for (unsigned i = 0, e = Succs.size(); i != e; ++i)
271     Succs[i]->removePredecessor(BB);
272 
273   BB->eraseFromParent();
274 }
275