← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp
 
1
//===- SimplifyCFGPass.cpp - CFG Simplification Pass ----------------------===//
 
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 dead code elimination and basic block merging, along
 
11
// with a collection of other peephole control flow optimizations.  For example:
 
12
//
 
13
//   * Removes basic blocks with no predecessors.
 
14
//   * Merges a basic block into its predecessor if there is only one and the
 
15
//     predecessor only has one successor.
 
16
//   * Eliminates PHI nodes for basic blocks with a single predecessor.
 
17
//   * Eliminates a basic block that only contains an unconditional branch.
 
18
//   * Changes invoke instructions to nounwind functions to be calls.
 
19
//   * Change things like "if (x) if (y)" into "if (x&y)".
 
20
//   * etc..
 
21
//
 
22
//===----------------------------------------------------------------------===//
 
23
 
 
24
#define DEBUG_TYPE "simplifycfg"
 
25
#include "llvm/Transforms/Scalar.h"
 
26
#include "llvm/Transforms/Utils/Local.h"
 
27
#include "llvm/Constants.h"
 
28
#include "llvm/Instructions.h"
 
29
#include "llvm/Module.h"
 
30
#include "llvm/Attributes.h"
 
31
#include "llvm/Support/CFG.h"
 
32
#include "llvm/Pass.h"
 
33
#include "llvm/Target/TargetData.h"
 
34
#include "llvm/ADT/SmallVector.h"
 
35
#include "llvm/ADT/SmallPtrSet.h"
 
36
#include "llvm/ADT/Statistic.h"
 
37
using namespace llvm;
 
38
 
 
39
STATISTIC(NumSimpl, "Number of blocks simplified");
 
40
 
 
41
namespace {
 
42
  struct CFGSimplifyPass : public FunctionPass {
 
43
    static char ID; // Pass identification, replacement for typeid
 
44
    CFGSimplifyPass() : FunctionPass(&ID) {}
 
45
 
 
46
    virtual bool runOnFunction(Function &F);
 
47
  };
 
48
}
 
49
 
 
50
char CFGSimplifyPass::ID = 0;
 
51
static RegisterPass<CFGSimplifyPass> X("simplifycfg", "Simplify the CFG");
 
52
 
 
53
// Public interface to the CFGSimplification pass
 
54
FunctionPass *llvm::createCFGSimplificationPass() {
 
55
  return new CFGSimplifyPass();
 
56
}
 
57
 
 
58
/// ChangeToUnreachable - Insert an unreachable instruction before the specified
 
59
/// instruction, making it and the rest of the code in the block dead.
 
60
static void ChangeToUnreachable(Instruction *I) {
 
61
  BasicBlock *BB = I->getParent();
 
62
  // Loop over all of the successors, removing BB's entry from any PHI
 
63
  // nodes.
 
64
  for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
 
65
    (*SI)->removePredecessor(BB);
 
66
  
 
67
  new UnreachableInst(I->getContext(), I);
 
68
  
 
69
  // All instructions after this are dead.
 
70
  BasicBlock::iterator BBI = I, BBE = BB->end();
 
71
  while (BBI != BBE) {
 
72
    if (!BBI->use_empty())
 
73
      BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
 
74
    BB->getInstList().erase(BBI++);
 
75
  }
 
76
}
 
77
 
 
78
/// ChangeToCall - Convert the specified invoke into a normal call.
 
79
static void ChangeToCall(InvokeInst *II) {
 
80
  BasicBlock *BB = II->getParent();
 
81
  SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end());
 
82
  CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args.begin(),
 
83
                                       Args.end(), "", II);
 
84
  NewCall->takeName(II);
 
85
  NewCall->setCallingConv(II->getCallingConv());
 
86
  NewCall->setAttributes(II->getAttributes());
 
87
  II->replaceAllUsesWith(NewCall);
 
88
 
 
89
  // Follow the call by a branch to the normal destination.
 
90
  BranchInst::Create(II->getNormalDest(), II);
 
91
 
 
92
  // Update PHI nodes in the unwind destination
 
93
  II->getUnwindDest()->removePredecessor(BB);
 
94
  BB->getInstList().erase(II);
 
95
}
 
96
 
 
97
static bool MarkAliveBlocks(BasicBlock *BB,
 
98
                            SmallPtrSet<BasicBlock*, 128> &Reachable) {
 
99
  
 
100
  SmallVector<BasicBlock*, 128> Worklist;
 
101
  Worklist.push_back(BB);
 
102
  bool Changed = false;
 
103
  do {
 
104
    BB = Worklist.pop_back_val();
 
105
    
 
106
    if (!Reachable.insert(BB))
 
107
      continue;
 
108
 
 
109
    // Do a quick scan of the basic block, turning any obviously unreachable
 
110
    // instructions into LLVM unreachable insts.  The instruction combining pass
 
111
    // canonicalizes unreachable insts into stores to null or undef.
 
112
    for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){
 
113
      if (CallInst *CI = dyn_cast<CallInst>(BBI)) {
 
114
        if (CI->doesNotReturn()) {
 
115
          // If we found a call to a no-return function, insert an unreachable
 
116
          // instruction after it.  Make sure there isn't *already* one there
 
117
          // though.
 
118
          ++BBI;
 
119
          if (!isa<UnreachableInst>(BBI)) {
 
120
            ChangeToUnreachable(BBI);
 
121
            Changed = true;
 
122
          }
 
123
          break;
 
124
        }
 
125
      }
 
126
      
 
127
      // Store to undef and store to null are undefined and used to signal that
 
128
      // they should be changed to unreachable by passes that can't modify the
 
129
      // CFG.
 
130
      if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
 
131
        Value *Ptr = SI->getOperand(1);
 
132
        
 
133
        if (isa<UndefValue>(Ptr) ||
 
134
            (isa<ConstantPointerNull>(Ptr) &&
 
135
             SI->getPointerAddressSpace() == 0)) {
 
136
          ChangeToUnreachable(SI);
 
137
          Changed = true;
 
138
          break;
 
139
        }
 
140
      }
 
141
    }
 
142
 
 
143
    // Turn invokes that call 'nounwind' functions into ordinary calls.
 
144
    if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
 
145
      if (II->doesNotThrow()) {
 
146
        ChangeToCall(II);
 
147
        Changed = true;
 
148
      }
 
149
 
 
150
    Changed |= ConstantFoldTerminator(BB);
 
151
    for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
 
152
      Worklist.push_back(*SI);
 
153
  } while (!Worklist.empty());
 
154
  return Changed;
 
155
}
 
156
 
 
157
/// RemoveUnreachableBlocksFromFn - Remove blocks that are not reachable, even 
 
158
/// if they are in a dead cycle.  Return true if a change was made, false 
 
159
/// otherwise.
 
160
static bool RemoveUnreachableBlocksFromFn(Function &F) {
 
161
  SmallPtrSet<BasicBlock*, 128> Reachable;
 
162
  bool Changed = MarkAliveBlocks(F.begin(), Reachable);
 
163
  
 
164
  // If there are unreachable blocks in the CFG...
 
165
  if (Reachable.size() == F.size())
 
166
    return Changed;
 
167
  
 
168
  assert(Reachable.size() < F.size());
 
169
  NumSimpl += F.size()-Reachable.size();
 
170
  
 
171
  // Loop over all of the basic blocks that are not reachable, dropping all of
 
172
  // their internal references...
 
173
  for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) {
 
174
    if (Reachable.count(BB))
 
175
      continue;
 
176
    
 
177
    for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
 
178
      if (Reachable.count(*SI))
 
179
        (*SI)->removePredecessor(BB);
 
180
    BB->dropAllReferences();
 
181
  }
 
182
  
 
183
  for (Function::iterator I = ++F.begin(); I != F.end();)
 
184
    if (!Reachable.count(I))
 
185
      I = F.getBasicBlockList().erase(I);
 
186
    else
 
187
      ++I;
 
188
  
 
189
  return true;
 
190
}
 
191
 
 
192
/// MergeEmptyReturnBlocks - If we have more than one empty (other than phi
 
193
/// node) return blocks, merge them together to promote recursive block merging.
 
194
static bool MergeEmptyReturnBlocks(Function &F) {
 
195
  bool Changed = false;
 
196
  
 
197
  BasicBlock *RetBlock = 0;
 
198
  
 
199
  // Scan all the blocks in the function, looking for empty return blocks.
 
200
  for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) {
 
201
    BasicBlock &BB = *BBI++;
 
202
    
 
203
    // Only look at return blocks.
 
204
    ReturnInst *Ret = dyn_cast<ReturnInst>(BB.getTerminator());
 
205
    if (Ret == 0) continue;
 
206
    
 
207
    // Only look at the block if it is empty or the only other thing in it is a
 
208
    // single PHI node that is the operand to the return.
 
209
    if (Ret != &BB.front()) {
 
210
      // Check for something else in the block.
 
211
      BasicBlock::iterator I = Ret;
 
212
      --I;
 
213
      if (!isa<PHINode>(I) || I != BB.begin() ||
 
214
          Ret->getNumOperands() == 0 ||
 
215
          Ret->getOperand(0) != I)
 
216
        continue;
 
217
    }
 
218
    
 
219
    // If this is the first returning block, remember it and keep going.
 
220
    if (RetBlock == 0) {
 
221
      RetBlock = &BB;
 
222
      continue;
 
223
    }
 
224
    
 
225
    // Otherwise, we found a duplicate return block.  Merge the two.
 
226
    Changed = true;
 
227
    
 
228
    // Case when there is no input to the return or when the returned values
 
229
    // agree is trivial.  Note that they can't agree if there are phis in the
 
230
    // blocks.
 
231
    if (Ret->getNumOperands() == 0 ||
 
232
        Ret->getOperand(0) == 
 
233
          cast<ReturnInst>(RetBlock->getTerminator())->getOperand(0)) {
 
234
      BB.replaceAllUsesWith(RetBlock);
 
235
      BB.eraseFromParent();
 
236
      continue;
 
237
    }
 
238
    
 
239
    // If the canonical return block has no PHI node, create one now.
 
240
    PHINode *RetBlockPHI = dyn_cast<PHINode>(RetBlock->begin());
 
241
    if (RetBlockPHI == 0) {
 
242
      Value *InVal = cast<ReturnInst>(RetBlock->begin())->getOperand(0);
 
243
      RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(), "merge",
 
244
                                    &RetBlock->front());
 
245
      
 
246
      for (pred_iterator PI = pred_begin(RetBlock), E = pred_end(RetBlock);
 
247
           PI != E; ++PI)
 
248
        RetBlockPHI->addIncoming(InVal, *PI);
 
249
      RetBlock->getTerminator()->setOperand(0, RetBlockPHI);
 
250
    }
 
251
    
 
252
    // Turn BB into a block that just unconditionally branches to the return
 
253
    // block.  This handles the case when the two return blocks have a common
 
254
    // predecessor but that return different things.
 
255
    RetBlockPHI->addIncoming(Ret->getOperand(0), &BB);
 
256
    BB.getTerminator()->eraseFromParent();
 
257
    BranchInst::Create(RetBlock, &BB);
 
258
  }
 
259
  
 
260
  return Changed;
 
261
}
 
262
 
 
263
/// IterativeSimplifyCFG - Call SimplifyCFG on all the blocks in the function,
 
264
/// iterating until no more changes are made.
 
265
static bool IterativeSimplifyCFG(Function &F, const TargetData *TD) {
 
266
  bool Changed = false;
 
267
  bool LocalChange = true;
 
268
  while (LocalChange) {
 
269
    LocalChange = false;
 
270
    
 
271
    // Loop over all of the basic blocks (except the first one) and remove them
 
272
    // if they are unneeded...
 
273
    //
 
274
    for (Function::iterator BBIt = ++F.begin(); BBIt != F.end(); ) {
 
275
      if (SimplifyCFG(BBIt++, TD)) {
 
276
        LocalChange = true;
 
277
        ++NumSimpl;
 
278
      }
 
279
    }
 
280
    Changed |= LocalChange;
 
281
  }
 
282
  return Changed;
 
283
}
 
284
 
 
285
// It is possible that we may require multiple passes over the code to fully
 
286
// simplify the CFG.
 
287
//
 
288
bool CFGSimplifyPass::runOnFunction(Function &F) {
 
289
  const TargetData *TD = getAnalysisIfAvailable<TargetData>();
 
290
  bool EverChanged = RemoveUnreachableBlocksFromFn(F);
 
291
  EverChanged |= MergeEmptyReturnBlocks(F);
 
292
  EverChanged |= IterativeSimplifyCFG(F, TD);
 
293
 
 
294
  // If neither pass changed anything, we're done.
 
295
  if (!EverChanged) return false;
 
296
 
 
297
  // IterativeSimplifyCFG can (rarely) make some loops dead.  If this happens,
 
298
  // RemoveUnreachableBlocksFromFn is needed to nuke them, which means we should
 
299
  // iterate between the two optimizations.  We structure the code like this to
 
300
  // avoid reruning IterativeSimplifyCFG if the second pass of 
 
301
  // RemoveUnreachableBlocksFromFn doesn't do anything.
 
302
  if (!RemoveUnreachableBlocksFromFn(F))
 
303
    return true;
 
304
 
 
305
  do {
 
306
    EverChanged = IterativeSimplifyCFG(F, TD);
 
307
    EverChanged |= RemoveUnreachableBlocksFromFn(F);
 
308
  } while (EverChanged);
 
309
 
 
310
  return true;
 
311
}