PruneEH.cpp revision 5a44ef9fd5f7c3964ad79b94778261175dea5c33 
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#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 <set>
31#include <algorithm>
32using namespace llvm;
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
42    // runOnSCC - Analyze the SCC, performing the transformation if possible.
43    bool runOnSCC(std::vector<CallGraphNode *> &SCC);
44
45    bool SimplifyFunction(Function *F);
46    void DeleteBasicBlock(BasicBlock *BB);
47  };
48}
49
50char PruneEH::ID = 0;
51static RegisterPass<PruneEH>
52X("prune-eh", "Remove unused exception handling info");
53
54Pass *llvm::createPruneEHPass() { return new PruneEH(); }
55
56
57bool PruneEH::runOnSCC(std::vector<CallGraphNode *> &SCC) {
58  SmallPtrSet<CallGraphNode *, 8> SCCNodes;
59  CallGraph &CG = getAnalysis<CallGraph>();
60  bool MadeChange = false;
61
62  // Fill SCCNodes with the elements of the SCC.  Used for quickly
63  // looking up whether a given CallGraphNode is in this SCC.
64  for (unsigned i = 0, e = SCC.size(); i != e; ++i)
65    SCCNodes.insert(SCC[i]);
66
67  // First pass, scan all of the functions in the SCC, simplifying them
68  // according to what we know.
69  for (unsigned i = 0, e = SCC.size(); i != e; ++i)
70    if (Function *F = SCC[i]->getFunction())
71      MadeChange |= SimplifyFunction(F);
72
73  // Next, check to see if any callees might throw or if there are any external
74  // functions in this SCC: if so, we cannot prune any functions in this SCC.
75  // Definitions that are weak and not declared non-throwing might be
76  // overridden at linktime with something that throws, so assume that.
77  // If this SCC includes the unwind instruction, we KNOW it throws, so
78  // obviously the SCC might throw.
79  //
80  bool SCCMightUnwind = false, SCCMightReturn = false;
81  for (unsigned i = 0, e = SCC.size();
82       (!SCCMightUnwind || !SCCMightReturn) && i != e; ++i) {
83    Function *F = SCC[i]->getFunction();
84    if (F == 0) {
85      SCCMightUnwind = true;
86      SCCMightReturn = true;
87    } else if (F->isDeclaration() || F->mayBeOverridden()) {
88      SCCMightUnwind |= !F->doesNotThrow();
89      SCCMightReturn |= !F->doesNotReturn();
90    } else {
91      bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow();
92      bool CheckReturn = !SCCMightReturn && !F->doesNotReturn();
93
94      if (!CheckUnwind && !CheckReturn)
95        continue;
96
97      // Check to see if this function performs an unwind or calls an
98      // unwinding function.
99      for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
100        if (CheckUnwind && isa<UnwindInst>(BB->getTerminator())) {
101          // Uses unwind!
102          SCCMightUnwind = true;
103        } else if (CheckReturn && isa<ReturnInst>(BB->getTerminator())) {
104          SCCMightReturn = true;
105        }
106
107        // Invoke instructions don't allow unwinding to continue, so we are
108        // only interested in call instructions.
109        if (CheckUnwind && !SCCMightUnwind)
110          for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
111            if (CallInst *CI = dyn_cast<CallInst>(I)) {
112              if (CI->doesNotThrow()) {
113                // This call cannot throw.
114              } else if (Function *Callee = CI->getCalledFunction()) {
115                CallGraphNode *CalleeNode = CG[Callee];
116                // If the callee is outside our current SCC then we may
117                // throw because it might.
118                if (!SCCNodes.count(CalleeNode)) {
119                  SCCMightUnwind = true;
120                  break;
121                }
122              } else {
123                // Indirect call, it might throw.
124                SCCMightUnwind = true;
125                break;
126              }
127            }
128        if (SCCMightUnwind && SCCMightReturn) break;
129      }
130    }
131  }
132
133  // If the SCC doesn't unwind or doesn't throw, note this fact.
134  if (!SCCMightUnwind || !SCCMightReturn)
135    for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
136      Attributes NewAttributes = Attribute::None;
137
138      if (!SCCMightUnwind)
139        NewAttributes |= Attribute::NoUnwind;
140      if (!SCCMightReturn)
141        NewAttributes |= Attribute::NoReturn;
142
143      const AttrListPtr &PAL = SCC[i]->getFunction()->getAttributes();
144      const AttrListPtr &NPAL = PAL.addAttr(~0, NewAttributes);
145      if (PAL != NPAL) {
146        MadeChange = true;
147        SCC[i]->getFunction()->setAttributes(NPAL);
148      }
149    }
150
151  for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
152    // Convert any invoke instructions to non-throwing functions in this node
153    // into call instructions with a branch.  This makes the exception blocks
154    // dead.
155    if (Function *F = SCC[i]->getFunction())
156      MadeChange |= SimplifyFunction(F);
157  }
158
159  return MadeChange;
160}
161
162
163// SimplifyFunction - Given information about callees, simplify the specified
164// function if we have invokes to non-unwinding functions or code after calls to
165// no-return functions.
166bool PruneEH::SimplifyFunction(Function *F) {
167  bool MadeChange = false;
168  for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
169    if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
170      if (II->doesNotThrow()) {
171        SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end());
172        // Insert a call instruction before the invoke.
173        CallInst *Call = CallInst::Create(II->getCalledValue(),
174                                          Args.begin(), Args.end(), "", II);
175        Call->takeName(II);
176        Call->setCallingConv(II->getCallingConv());
177        Call->setAttributes(II->getAttributes());
178
179        // Anything that used the value produced by the invoke instruction
180        // now uses the value produced by the call instruction.  Note that we
181        // do this even for void functions and calls with no uses so that the
182        // callgraph edge is updated.
183        II->replaceAllUsesWith(Call);
184        BasicBlock *UnwindBlock = II->getUnwindDest();
185        UnwindBlock->removePredecessor(II->getParent());
186
187        // Insert a branch to the normal destination right before the
188        // invoke.
189        BranchInst::Create(II->getNormalDest(), II);
190
191        // Finally, delete the invoke instruction!
192        BB->getInstList().pop_back();
193
194        // If the unwind block is now dead, nuke it.
195        if (pred_begin(UnwindBlock) == pred_end(UnwindBlock))
196          DeleteBasicBlock(UnwindBlock);  // Delete the new BB.
197
198        ++NumRemoved;
199        MadeChange = true;
200      }
201
202    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
203      if (CallInst *CI = dyn_cast<CallInst>(I++))
204        if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) {
205          // This call calls a function that cannot return.  Insert an
206          // unreachable instruction after it and simplify the code.  Do this
207          // by splitting the BB, adding the unreachable, then deleting the
208          // new BB.
209          BasicBlock *New = BB->splitBasicBlock(I);
210
211          // Remove the uncond branch and add an unreachable.
212          BB->getInstList().pop_back();
213          new UnreachableInst(BB->getContext(), BB);
214
215          DeleteBasicBlock(New);  // Delete the new BB.
216          MadeChange = true;
217          ++NumUnreach;
218          break;
219        }
220  }
221
222  return MadeChange;
223}
224
225/// DeleteBasicBlock - remove the specified basic block from the program,
226/// updating the callgraph to reflect any now-obsolete edges due to calls that
227/// exist in the BB.
228void PruneEH::DeleteBasicBlock(BasicBlock *BB) {
229  assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!");
230  CallGraph &CG = getAnalysis<CallGraph>();
231
232  CallGraphNode *CGN = CG[BB->getParent()];
233  for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
234    --I;
235    if (CallInst *CI = dyn_cast<CallInst>(I)) {
236      if (!isa<DbgInfoIntrinsic>(I))
237        CGN->removeCallEdgeFor(CI);
238    } else if (InvokeInst *II = dyn_cast<InvokeInst>(I))
239      CGN->removeCallEdgeFor(II);
240    if (!I->use_empty())
241      I->replaceAllUsesWith(UndefValue::get(I->getType()));
242  }
243
244  // Get the list of successors of this block.
245  std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));
246
247  for (unsigned i = 0, e = Succs.size(); i != e; ++i)
248    Succs[i]->removePredecessor(BB);
249
250  BB->eraseFromParent();
251}
252