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