PruneEH.cpp revision 7e8958a9f3366d225ddff95a069efb61f9f3567a 
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  CallGraph &CG = getAnalysis<CallGraph>();
160  CallGraphNode *CGN = CG[F];
161
162  bool MadeChange = false;
163  for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
164    if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
165      if (II->doesNotThrow()) {
166        SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end());
167        // Insert a call instruction before the invoke.
168        CallInst *Call = CallInst::Create(II->getCalledValue(),
169                                          Args.begin(), Args.end(), "", II);
170        Call->takeName(II);
171        Call->setCallingConv(II->getCallingConv());
172        Call->setParamAttrs(II->getParamAttrs());
173
174        // Anything that used the value produced by the invoke instruction
175        // now uses the value produced by the call instruction.
176        II->replaceAllUsesWith(Call);
177        BasicBlock *UnwindBlock = II->getUnwindDest();
178        UnwindBlock->removePredecessor(II->getParent());
179
180        // Fix up the call graph.
181        CGN->replaceCallSite(II, Call);
182
183        // Insert a branch to the normal destination right before the
184        // invoke.
185        BranchInst::Create(II->getNormalDest(), II);
186
187        // Finally, delete the invoke instruction!
188        BB->getInstList().pop_back();
189
190        // If the unwind block is now dead, nuke it.
191        if (pred_begin(UnwindBlock) == pred_end(UnwindBlock))
192          DeleteBasicBlock(UnwindBlock);  // Delete the new BB.
193
194        ++NumRemoved;
195        MadeChange = true;
196      }
197
198    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
199      if (CallInst *CI = dyn_cast<CallInst>(I++))
200        if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) {
201          // This call calls a function that cannot return.  Insert an
202          // unreachable instruction after it and simplify the code.  Do this
203          // by splitting the BB, adding the unreachable, then deleting the
204          // new BB.
205          BasicBlock *New = BB->splitBasicBlock(I);
206
207          // Remove the uncond branch and add an unreachable.
208          BB->getInstList().pop_back();
209          new UnreachableInst(BB);
210
211          DeleteBasicBlock(New);  // Delete the new BB.
212          MadeChange = true;
213          ++NumUnreach;
214          break;
215        }
216  }
217
218  return MadeChange;
219}
220
221/// DeleteBasicBlock - remove the specified basic block from the program,
222/// updating the callgraph to reflect any now-obsolete edges due to calls that
223/// exist in the BB.
224void PruneEH::DeleteBasicBlock(BasicBlock *BB) {
225  assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!");
226  CallGraph &CG = getAnalysis<CallGraph>();
227
228  CallGraphNode *CGN = CG[BB->getParent()];
229  for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
230    --I;
231    if (CallInst *CI = dyn_cast<CallInst>(I)) {
232      if (Function *Callee = CI->getCalledFunction())
233        CGN->removeCallEdgeTo(CG[Callee]);
234    } else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) {
235      if (Function *Callee = II->getCalledFunction())
236        CGN->removeCallEdgeTo(CG[Callee]);
237    }
238    if (!I->use_empty())
239      I->replaceAllUsesWith(UndefValue::get(I->getType()));
240  }
241
242  // Get the list of successors of this block.
243  std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));
244
245  for (unsigned i = 0, e = Succs.size(); i != e; ++i)
246    Succs[i]->removePredecessor(BB);
247
248  BB->eraseFromParent();
249}
250