← Back to branch summary

~ubuntu-branches/ubuntu/feisty/clamav/feisty

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Transforms/IPO/PruneEH.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2007-02-20 10:33:44 UTC
  • mto: This revision was merged to the branch mainline in revision 16.
  • Revision ID: james.westby@ubuntu.com-20070220103344-zgcu2psnx9d98fpa
Tags: upstream-0.90
Import upstream version 0.90

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Transforms/IPO/PruneEH.cpp
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>
32
 
using namespace llvm;
33
 
 
34
 
STATISTIC(NumRemoved, "Number of invokes removed");
35
 
STATISTIC(NumUnreach, "Number of noreturn calls optimized");
36
 
 
37
 
namespace {
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(CallGraphSCC &SCC);
44
 
 
45
 
    bool SimplifyFunction(Function *F);
46
 
    void DeleteBasicBlock(BasicBlock *BB);
47
 
  };
48
 
}
49
 
 
50
 
char PruneEH::ID = 0;
51
 
INITIALIZE_PASS(PruneEH, "prune-eh",
52
 
                "Remove unused exception handling info", false, false);
53
 
 
54
 
Pass *llvm::createPruneEHPass() { return new PruneEH(); }
55
 
 
56
 
 
57
 
bool PruneEH::runOnSCC(CallGraphSCC &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 (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
65
 
    SCCNodes.insert(*I);
66
 
 
67
 
  // First pass, scan all of the functions in the SCC, simplifying them
68
 
  // according to what we know.
69
 
  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
70
 
    if (Function *F = (*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 (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); 
82
 
       (!SCCMightUnwind || !SCCMightReturn) && I != E; ++I) {
83
 
    Function *F = (*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 (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); 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
 
      Function *F = (*I)->getFunction();
144
 
      const AttrListPtr &PAL = F->getAttributes();
145
 
      const AttrListPtr &NPAL = PAL.addAttr(~0, NewAttributes);
146
 
      if (PAL != NPAL) {
147
 
        MadeChange = true;
148
 
        F->setAttributes(NPAL);
149
 
      }
150
 
    }
151
 
 
152
 
  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
153
 
    // Convert any invoke instructions to non-throwing functions in this node
154
 
    // into call instructions with a branch.  This makes the exception blocks
155
 
    // dead.
156
 
    if (Function *F = (*I)->getFunction())
157
 
      MadeChange |= SimplifyFunction(F);
158
 
  }
159
 
 
160
 
  return MadeChange;
161
 
}
162
 
 
163
 
 
164
 
// SimplifyFunction - Given information about callees, simplify the specified
165
 
// function if we have invokes to non-unwinding functions or code after calls to
166
 
// no-return functions.
167
 
bool PruneEH::SimplifyFunction(Function *F) {
168
 
  bool MadeChange = false;
169
 
  for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
170
 
    if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
171
 
      if (II->doesNotThrow()) {
172
 
        SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
173
 
        // Insert a call instruction before the invoke.
174
 
        CallInst *Call = CallInst::Create(II->getCalledValue(),
175
 
                                          Args.begin(), Args.end(), "", II);
176
 
        Call->takeName(II);
177
 
        Call->setCallingConv(II->getCallingConv());
178
 
        Call->setAttributes(II->getAttributes());
179
 
 
180
 
        // Anything that used the value produced by the invoke instruction
181
 
        // now uses the value produced by the call instruction.  Note that we
182
 
        // do this even for void functions and calls with no uses so that the
183
 
        // callgraph edge is updated.
184
 
        II->replaceAllUsesWith(Call);
185
 
        BasicBlock *UnwindBlock = II->getUnwindDest();
186
 
        UnwindBlock->removePredecessor(II->getParent());
187
 
 
188
 
        // Insert a branch to the normal destination right before the
189
 
        // invoke.
190
 
        BranchInst::Create(II->getNormalDest(), II);
191
 
 
192
 
        // Finally, delete the invoke instruction!
193
 
        BB->getInstList().pop_back();
194
 
 
195
 
        // If the unwind block is now dead, nuke it.
196
 
        if (pred_begin(UnwindBlock) == pred_end(UnwindBlock))
197
 
          DeleteBasicBlock(UnwindBlock);  // Delete the new BB.
198
 
 
199
 
        ++NumRemoved;
200
 
        MadeChange = true;
201
 
      }
202
 
 
203
 
    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
204
 
      if (CallInst *CI = dyn_cast<CallInst>(I++))
205
 
        if (CI->doesNotReturn() && !isa<UnreachableInst>(I)) {
206
 
          // This call calls a function that cannot return.  Insert an
207
 
          // unreachable instruction after it and simplify the code.  Do this
208
 
          // by splitting the BB, adding the unreachable, then deleting the
209
 
          // new BB.
210
 
          BasicBlock *New = BB->splitBasicBlock(I);
211
 
 
212
 
          // Remove the uncond branch and add an unreachable.
213
 
          BB->getInstList().pop_back();
214
 
          new UnreachableInst(BB->getContext(), BB);
215
 
 
216
 
          DeleteBasicBlock(New);  // Delete the new BB.
217
 
          MadeChange = true;
218
 
          ++NumUnreach;
219
 
          break;
220
 
        }
221
 
  }
222
 
 
223
 
  return MadeChange;
224
 
}
225
 
 
226
 
/// DeleteBasicBlock - remove the specified basic block from the program,
227
 
/// updating the callgraph to reflect any now-obsolete edges due to calls that
228
 
/// exist in the BB.
229
 
void PruneEH::DeleteBasicBlock(BasicBlock *BB) {
230
 
  assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!");
231
 
  CallGraph &CG = getAnalysis<CallGraph>();
232
 
 
233
 
  CallGraphNode *CGN = CG[BB->getParent()];
234
 
  for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
235
 
    --I;
236
 
    if (CallInst *CI = dyn_cast<CallInst>(I)) {
237
 
      if (!isa<DbgInfoIntrinsic>(I))
238
 
        CGN->removeCallEdgeFor(CI);
239
 
    } else if (InvokeInst *II = dyn_cast<InvokeInst>(I))
240
 
      CGN->removeCallEdgeFor(II);
241
 
    if (!I->use_empty())
242
 
      I->replaceAllUsesWith(UndefValue::get(I->getType()));
243
 
  }
244
 
 
245
 
  // Get the list of successors of this block.
246
 
  std::vector<BasicBlock*> Succs(succ_begin(BB), succ_end(BB));
247
 
 
248
 
  for (unsigned i = 0, e = Succs.size(); i != e; ++i)
249
 
    Succs[i]->removePredecessor(BB);
250
 
 
251
 
  BB->eraseFromParent();
252
 
}