PruneEH.cpp revision 134f6e5b6d7246384eaaeacbf5052a3a218cc887 
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(&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  // Definitions that are weak and not declared non-throwing might be
68  // overridden at linktime with something that throws, so assume that.
69  // If this SCC includes the unwind instruction, we KNOW it throws, so
70  // obviously the SCC might throw.
71  //
72  bool SCCMightUnwind = false, SCCMightReturn = false;
73  for (unsigned i = 0, e = SCC.size();
74       (!SCCMightUnwind || !SCCMightReturn) && i != e; ++i) {
75    Function *F = SCC[i]->getFunction();
76    if (F == 0) {
77      SCCMightUnwind = true;
78      SCCMightReturn = true;
79    } else if (F->isDeclaration() || F->hasWeakLinkage()) {
80      SCCMightUnwind |= !F->doesNotThrow();
81      SCCMightReturn |= !F->doesNotReturn();
82    } else {
83      bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow();
84      bool CheckReturn = !SCCMightReturn && !F->doesNotReturn();
85
86      if (!CheckUnwind && !CheckReturn)
87        continue;
88
89      // Check to see if this function performs an unwind or calls an
90      // unwinding function.
91      for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
92        if (CheckUnwind && isa<UnwindInst>(BB->getTerminator())) {
93          // Uses unwind!
94          SCCMightUnwind = true;
95        } else if (CheckReturn && isa<ReturnInst>(BB->getTerminator())) {
96          SCCMightReturn = true;
97        }
98
99        // Invoke instructions don't allow unwinding to continue, so we are
100        // only interested in call instructions.
101        if (CheckUnwind && !SCCMightUnwind)
102          for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
103            if (CallInst *CI = dyn_cast<CallInst>(I)) {
104              if (CI->doesNotThrow()) {
105                // This call cannot throw.
106              } else if (Function *Callee = CI->getCalledFunction()) {
107                CallGraphNode *CalleeNode = CG[Callee];
108                // If the callee is outside our current SCC then we may
109                // throw because it might.
110                if (std::find(SCC.begin(), SCC.end(), CalleeNode) == SCC.end()){
111                  SCCMightUnwind = true;
112                  break;
113                }
114              } else {
115                // Indirect call, it might throw.
116                SCCMightUnwind = true;
117                break;
118              }
119            }
120        if (SCCMightUnwind && SCCMightReturn) break;
121      }
122    }
123  }
124
125  // If the SCC doesn't unwind or doesn't throw, note this fact.
126  if (!SCCMightUnwind || !SCCMightReturn)
127    for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
128      ParameterAttributes NewAttributes = ParamAttr::None;
129
130      if (!SCCMightUnwind)
131        NewAttributes |= ParamAttr::NoUnwind;
132      if (!SCCMightReturn)
133        NewAttributes |= ParamAttr::NoReturn;
134
135      const PAListPtr &PAL = SCC[i]->getFunction()->getParamAttrs();
136      const PAListPtr &NPAL = PAL.addAttr(0, NewAttributes);
137      if (PAL != NPAL) {
138        MadeChange = true;
139        SCC[i]->getFunction()->setParamAttrs(NPAL);
140      }
141    }
142
143  for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
144    // Convert any invoke instructions to non-throwing functions in this node
145    // into call instructions with a branch.  This makes the exception blocks
146    // dead.
147    if (Function *F = SCC[i]->getFunction())
148      MadeChange |= SimplifyFunction(F);
149  }
150
151  return MadeChange;
152}
153
154
155// SimplifyFunction - Given information about callees, simplify the specified
156// function if we have invokes to non-unwinding functions or code after calls to
157// no-return functions.
158bool PruneEH::SimplifyFunction(Function *F) {
159  bool MadeChange = false;
160  for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
161    if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
162      if (II->doesNotThrow()) {
163        SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end());
164        // Insert a call instruction before the invoke.
165        CallInst *Call = CallInst::Create(II->getCalledValue(),
166                                          Args.begin(), Args.end(), "", II);
167        Call->takeName(II);
168        Call->setCallingConv(II->getCallingConv());
169        Call->setParamAttrs(II->getParamAttrs());
170
171        // Anything that used the value produced by the invoke instruction
172        // now uses the value produced by the call instruction.
173        II->replaceAllUsesWith(Call);
174        BasicBlock *UnwindBlock = II->getUnwindDest();
175        UnwindBlock->removePredecessor(II->getParent());
176
177        // Insert a branch to the normal destination right before the
178        // invoke.
179        BranchInst::Create(II->getNormalDest(), II);
180
181        // Finally, delete the invoke instruction!
182        BB->getInstList().pop_back();
183
184        // If the unwind block is now dead, nuke it.
185        if (pred_begin(UnwindBlock) == pred_end(UnwindBlock))
186          DeleteBasicBlock(UnwindBlock);  // Delete the new BB.
187
188        ++NumRemoved;
189        MadeChange = true;
190      }
191
192    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
193      if (CallInst *CI = dyn_cast<CallInst>(I++))
194        if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) {
195          // This call calls a function that cannot return.  Insert an
196          // unreachable instruction after it and simplify the code.  Do this
197          // by splitting the BB, adding the unreachable, then deleting the
198          // new BB.
199          BasicBlock *New = BB->splitBasicBlock(I);
200
201          // Remove the uncond branch and add an unreachable.
202          BB->getInstList().pop_back();
203          new UnreachableInst(BB);
204
205          DeleteBasicBlock(New);  // Delete the new BB.
206          MadeChange = true;
207          ++NumUnreach;
208          break;
209        }
210  }
211
212  return MadeChange;
213}
214
215/// DeleteBasicBlock - remove the specified basic block from the program,
216/// updating the callgraph to reflect any now-obsolete edges due to calls that
217/// exist in the BB.
218void PruneEH::DeleteBasicBlock(BasicBlock *BB) {
219  assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!");
220  CallGraph &CG = getAnalysis<CallGraph>();
221
222  CallGraphNode *CGN = CG[BB->getParent()];
223  for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
224    --I;
225    if (CallInst *CI = dyn_cast<CallInst>(I)) {
226      if (Function *Callee = CI->getCalledFunction())
227        CGN->removeCallEdgeTo(CG[Callee]);
228    } else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
229      if (Function *Callee = II->getCalledFunction())
230        CGN->removeCallEdgeTo(CG[Callee]);
231    }
232    if (!I->use_empty())
233      I->replaceAllUsesWith(UndefValue::get(I->getType()));
234  }
235
236  // Get the list of successors of this block.
237  std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));
238
239  for (unsigned i = 0, e = Succs.size(); i != e; ++i)
240    Succs[i]->removePredecessor(BB);
241
242  BB->eraseFromParent();
243}
244