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