← 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/Utils/SSI.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/Utils/SSI.cpp
 
1
//===------------------- SSI.cpp - Creates SSI Representation -------------===//
 
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 pass converts a list of variables to the Static Single Information
 
11
// form. This is a program representation described by Scott Ananian in his
 
12
// Master Thesis: "The Static Single Information Form (1999)".
 
13
// We are building an on-demand representation, that is, we do not convert
 
14
// every single variable in the target function to SSI form. Rather, we receive
 
15
// a list of target variables that must be converted. We also do not
 
16
// completely convert a target variable to the SSI format. Instead, we only
 
17
// change the variable in the points where new information can be attached
 
18
// to its live range, that is, at branch points.
 
19
//
 
20
//===----------------------------------------------------------------------===//
 
21
 
 
22
#define DEBUG_TYPE "ssi"
 
23
 
 
24
#include "llvm/Transforms/Scalar.h"
 
25
#include "llvm/Transforms/Utils/SSI.h"
 
26
#include "llvm/ADT/Statistic.h"
 
27
#include "llvm/Analysis/Dominators.h"
 
28
 
 
29
using namespace llvm;
 
30
 
 
31
static const std::string SSI_PHI = "SSI_phi";
 
32
static const std::string SSI_SIG = "SSI_sigma";
 
33
 
 
34
STATISTIC(NumSigmaInserted, "Number of sigma functions inserted");
 
35
STATISTIC(NumPhiInserted, "Number of phi functions inserted");
 
36
 
 
37
void SSI::getAnalysisUsage(AnalysisUsage &AU) const {
 
38
  AU.addRequiredTransitive<DominanceFrontier>();
 
39
  AU.addRequiredTransitive<DominatorTree>();
 
40
  AU.setPreservesAll();
 
41
}
 
42
 
 
43
bool SSI::runOnFunction(Function &F) {
 
44
  DT_ = &getAnalysis<DominatorTree>();
 
45
  return false;
 
46
}
 
47
 
 
48
/// This methods creates the SSI representation for the list of values
 
49
/// received. It will only create SSI representation if a value is used
 
50
/// to decide a branch. Repeated values are created only once.
 
51
///
 
52
void SSI::createSSI(SmallVectorImpl<Instruction *> &value) {
 
53
  init(value);
 
54
 
 
55
  SmallPtrSet<Instruction*, 4> needConstruction;
 
56
  for (SmallVectorImpl<Instruction*>::iterator I = value.begin(),
 
57
       E = value.end(); I != E; ++I)
 
58
    if (created.insert(*I))
 
59
      needConstruction.insert(*I);
 
60
 
 
61
  insertSigmaFunctions(needConstruction);
 
62
 
 
63
  // Test if there is a need to transform to SSI
 
64
  if (!needConstruction.empty()) {
 
65
    insertPhiFunctions(needConstruction);
 
66
    renameInit(needConstruction);
 
67
    rename(DT_->getRoot());
 
68
    fixPhis();
 
69
  }
 
70
 
 
71
  clean();
 
72
}
 
73
 
 
74
/// Insert sigma functions (a sigma function is a phi function with one
 
75
/// operator)
 
76
///
 
77
void SSI::insertSigmaFunctions(SmallPtrSet<Instruction*, 4> &value) {
 
78
  for (SmallPtrSet<Instruction*, 4>::iterator I = value.begin(),
 
79
       E = value.end(); I != E; ++I) {
 
80
    for (Value::use_iterator begin = (*I)->use_begin(),
 
81
         end = (*I)->use_end(); begin != end; ++begin) {
 
82
      // Test if the Use of the Value is in a comparator
 
83
      if (CmpInst *CI = dyn_cast<CmpInst>(begin)) {
 
84
        // Iterates through all uses of CmpInst
 
85
        for (Value::use_iterator begin_ci = CI->use_begin(),
 
86
             end_ci = CI->use_end(); begin_ci != end_ci; ++begin_ci) {
 
87
          // Test if any use of CmpInst is in a Terminator
 
88
          if (TerminatorInst *TI = dyn_cast<TerminatorInst>(begin_ci)) {
 
89
            insertSigma(TI, *I);
 
90
          }
 
91
        }
 
92
      }
 
93
    }
 
94
  }
 
95
}
 
96
 
 
97
/// Inserts Sigma Functions in every BasicBlock successor to Terminator
 
98
/// Instruction TI. All inserted Sigma Function are related to Instruction I.
 
99
///
 
100
void SSI::insertSigma(TerminatorInst *TI, Instruction *I) {
 
101
  // Basic Block of the Terminator Instruction
 
102
  BasicBlock *BB = TI->getParent();
 
103
  for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
 
104
    // Next Basic Block
 
105
    BasicBlock *BB_next = TI->getSuccessor(i);
 
106
    if (BB_next != BB &&
 
107
        BB_next->getSinglePredecessor() != NULL &&
 
108
        dominateAny(BB_next, I)) {
 
109
      PHINode *PN = PHINode::Create(I->getType(), SSI_SIG, BB_next->begin());
 
110
      PN->addIncoming(I, BB);
 
111
      sigmas[PN] = I;
 
112
      created.insert(PN);
 
113
      defsites[I].push_back(BB_next);
 
114
      ++NumSigmaInserted;
 
115
    }
 
116
  }
 
117
}
 
118
 
 
119
/// Insert phi functions when necessary
 
120
///
 
121
void SSI::insertPhiFunctions(SmallPtrSet<Instruction*, 4> &value) {
 
122
  DominanceFrontier *DF = &getAnalysis<DominanceFrontier>();
 
123
  for (SmallPtrSet<Instruction*, 4>::iterator I = value.begin(),
 
124
       E = value.end(); I != E; ++I) {
 
125
    // Test if there were any sigmas for this variable
 
126
    SmallPtrSet<BasicBlock *, 16> BB_visited;
 
127
 
 
128
    // Insert phi functions if there is any sigma function
 
129
    while (!defsites[*I].empty()) {
 
130
 
 
131
      BasicBlock *BB = defsites[*I].back();
 
132
 
 
133
      defsites[*I].pop_back();
 
134
      DominanceFrontier::iterator DF_BB = DF->find(BB);
 
135
 
 
136
      // The BB is unreachable. Skip it.
 
137
      if (DF_BB == DF->end())
 
138
        continue; 
 
139
 
 
140
      // Iterates through all the dominance frontier of BB
 
141
      for (std::set<BasicBlock *>::iterator DF_BB_begin =
 
142
           DF_BB->second.begin(), DF_BB_end = DF_BB->second.end();
 
143
           DF_BB_begin != DF_BB_end; ++DF_BB_begin) {
 
144
        BasicBlock *BB_dominated = *DF_BB_begin;
 
145
 
 
146
        // Test if has not yet visited this node and if the
 
147
        // original definition dominates this node
 
148
        if (BB_visited.insert(BB_dominated) &&
 
149
            DT_->properlyDominates(value_original[*I], BB_dominated) &&
 
150
            dominateAny(BB_dominated, *I)) {
 
151
          PHINode *PN = PHINode::Create(
 
152
              (*I)->getType(), SSI_PHI, BB_dominated->begin());
 
153
          phis.insert(std::make_pair(PN, *I));
 
154
          created.insert(PN);
 
155
 
 
156
          defsites[*I].push_back(BB_dominated);
 
157
          ++NumPhiInserted;
 
158
        }
 
159
      }
 
160
    }
 
161
    BB_visited.clear();
 
162
  }
 
163
}
 
164
 
 
165
/// Some initialization for the rename part
 
166
///
 
167
void SSI::renameInit(SmallPtrSet<Instruction*, 4> &value) {
 
168
  for (SmallPtrSet<Instruction*, 4>::iterator I = value.begin(),
 
169
       E = value.end(); I != E; ++I)
 
170
    value_stack[*I].push_back(*I);
 
171
}
 
172
 
 
173
/// Renames all variables in the specified BasicBlock.
 
174
/// Only variables that need to be rename will be.
 
175
///
 
176
void SSI::rename(BasicBlock *BB) {
 
177
  SmallPtrSet<Instruction*, 8> defined;
 
178
 
 
179
  // Iterate through instructions and make appropriate renaming.
 
180
  // For SSI_PHI (b = PHI()), store b at value_stack as a new
 
181
  // definition of the variable it represents.
 
182
  // For SSI_SIG (b = PHI(a)), substitute a with the current
 
183
  // value of a, present in the value_stack.
 
184
  // Then store bin the value_stack as the new definition of a.
 
185
  // For all other instructions (b = OP(a, c, d, ...)), we need to substitute
 
186
  // all operands with its current value, present in value_stack.
 
187
  for (BasicBlock::iterator begin = BB->begin(), end = BB->end();
 
188
       begin != end; ++begin) {
 
189
    Instruction *I = begin;
 
190
    if (PHINode *PN = dyn_cast<PHINode>(I)) { // Treat PHI functions
 
191
      Instruction* position;
 
192
 
 
193
      // Treat SSI_PHI
 
194
      if ((position = getPositionPhi(PN))) {
 
195
        value_stack[position].push_back(PN);
 
196
        defined.insert(position);
 
197
      // Treat SSI_SIG
 
198
      } else if ((position = getPositionSigma(PN))) {
 
199
        substituteUse(I);
 
200
        value_stack[position].push_back(PN);
 
201
        defined.insert(position);
 
202
      }
 
203
 
 
204
      // Treat all other PHI functions
 
205
      else {
 
206
        substituteUse(I);
 
207
      }
 
208
    }
 
209
 
 
210
    // Treat all other functions
 
211
    else {
 
212
      substituteUse(I);
 
213
    }
 
214
  }
 
215
 
 
216
  // This loop iterates in all BasicBlocks that are successors of the current
 
217
  // BasicBlock. For each SSI_PHI instruction found, insert an operand.
 
218
  // This operand is the current operand in value_stack for the variable
 
219
  // in "position". And the BasicBlock this operand represents is the current
 
220
  // BasicBlock.
 
221
  for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) {
 
222
    BasicBlock *BB_succ = *SI;
 
223
 
 
224
    for (BasicBlock::iterator begin = BB_succ->begin(),
 
225
         notPhi = BB_succ->getFirstNonPHI(); begin != *notPhi; ++begin) {
 
226
      Instruction *I = begin;
 
227
      PHINode *PN = dyn_cast<PHINode>(I);
 
228
      Instruction* position;
 
229
      if (PN && ((position = getPositionPhi(PN)))) {
 
230
        PN->addIncoming(value_stack[position].back(), BB);
 
231
      }
 
232
    }
 
233
  }
 
234
 
 
235
  // This loop calls rename on all children from this block. This time children
 
236
  // refers to a successor block in the dominance tree.
 
237
  DomTreeNode *DTN = DT_->getNode(BB);
 
238
  for (DomTreeNode::iterator begin = DTN->begin(), end = DTN->end();
 
239
       begin != end; ++begin) {
 
240
    DomTreeNodeBase<BasicBlock> *DTN_children = *begin;
 
241
    BasicBlock *BB_children = DTN_children->getBlock();
 
242
    rename(BB_children);
 
243
  }
 
244
 
 
245
  // Now we remove all inserted definitions of a variable from the top of
 
246
  // the stack leaving the previous one as the top.
 
247
  for (SmallPtrSet<Instruction*, 8>::iterator DI = defined.begin(),
 
248
       DE = defined.end(); DI != DE; ++DI)
 
249
    value_stack[*DI].pop_back();
 
250
}
 
251
 
 
252
/// Substitute any use in this instruction for the last definition of
 
253
/// the variable
 
254
///
 
255
void SSI::substituteUse(Instruction *I) {
 
256
  for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) {
 
257
    Value *operand = I->getOperand(i);
 
258
    for (DenseMap<Instruction*, SmallVector<Instruction*, 1> >::iterator
 
259
         VI = value_stack.begin(), VE = value_stack.end(); VI != VE; ++VI) {
 
260
      if (operand == VI->second.front() &&
 
261
          I != VI->second.back()) {
 
262
        PHINode *PN_I = dyn_cast<PHINode>(I);
 
263
        PHINode *PN_vs = dyn_cast<PHINode>(VI->second.back());
 
264
 
 
265
        // If a phi created in a BasicBlock is used as an operand of another
 
266
        // created in the same BasicBlock, this step marks this second phi,
 
267
        // to fix this issue later. It cannot be fixed now, because the
 
268
        // operands of the first phi are not final yet.
 
269
        if (PN_I && PN_vs &&
 
270
            VI->second.back()->getParent() == I->getParent()) {
 
271
 
 
272
          phisToFix.insert(PN_I);
 
273
        }
 
274
 
 
275
        I->setOperand(i, VI->second.back());
 
276
        break;
 
277
      }
 
278
    }
 
279
  }
 
280
}
 
281
 
 
282
/// Test if the BasicBlock BB dominates any use or definition of value.
 
283
/// If it dominates a phi instruction that is on the same BasicBlock,
 
284
/// that does not count.
 
285
///
 
286
bool SSI::dominateAny(BasicBlock *BB, Instruction *value) {
 
287
  for (Value::use_iterator begin = value->use_begin(),
 
288
       end = value->use_end(); begin != end; ++begin) {
 
289
    Instruction *I = cast<Instruction>(*begin);
 
290
    BasicBlock *BB_father = I->getParent();
 
291
    if (BB == BB_father && isa<PHINode>(I))
 
292
      continue;
 
293
    if (DT_->dominates(BB, BB_father)) {
 
294
      return true;
 
295
    }
 
296
  }
 
297
  return false;
 
298
}
 
299
 
 
300
/// When there is a phi node that is created in a BasicBlock and it is used
 
301
/// as an operand of another phi function used in the same BasicBlock,
 
302
/// LLVM looks this as an error. So on the second phi, the first phi is called
 
303
/// P and the BasicBlock it incomes is B. This P will be replaced by the value
 
304
/// it has for BasicBlock B. It also includes undef values for predecessors
 
305
/// that were not included in the phi.
 
306
///
 
307
void SSI::fixPhis() {
 
308
  for (SmallPtrSet<PHINode *, 1>::iterator begin = phisToFix.begin(),
 
309
       end = phisToFix.end(); begin != end; ++begin) {
 
310
    PHINode *PN = *begin;
 
311
    for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
 
312
      PHINode *PN_father = dyn_cast<PHINode>(PN->getIncomingValue(i));
 
313
      if (PN_father && PN->getParent() == PN_father->getParent() &&
 
314
          !DT_->dominates(PN->getParent(), PN->getIncomingBlock(i))) {
 
315
        BasicBlock *BB = PN->getIncomingBlock(i);
 
316
        int pos = PN_father->getBasicBlockIndex(BB);
 
317
        PN->setIncomingValue(i, PN_father->getIncomingValue(pos));
 
318
      }
 
319
    }
 
320
  }
 
321
 
 
322
  for (DenseMapIterator<PHINode *, Instruction*> begin = phis.begin(),
 
323
       end = phis.end(); begin != end; ++begin) {
 
324
    PHINode *PN = begin->first;
 
325
    BasicBlock *BB = PN->getParent();
 
326
    pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 
327
    SmallVector<BasicBlock*, 8> Preds(PI, PE);
 
328
    for (unsigned size = Preds.size();
 
329
         PI != PE && PN->getNumIncomingValues() != size; ++PI) {
 
330
      bool found = false;
 
331
      for (unsigned i = 0, pn_end = PN->getNumIncomingValues();
 
332
           i < pn_end; ++i) {
 
333
        if (PN->getIncomingBlock(i) == *PI) {
 
334
          found = true;
 
335
          break;
 
336
        }
 
337
      }
 
338
      if (!found) {
 
339
        PN->addIncoming(UndefValue::get(PN->getType()), *PI);
 
340
      }
 
341
    }
 
342
  }
 
343
}
 
344
 
 
345
/// Return which variable (position on the vector of variables) this phi
 
346
/// represents on the phis list.
 
347
///
 
348
Instruction* SSI::getPositionPhi(PHINode *PN) {
 
349
  DenseMap<PHINode *, Instruction*>::iterator val = phis.find(PN);
 
350
  if (val == phis.end())
 
351
    return 0;
 
352
  else
 
353
    return val->second;
 
354
}
 
355
 
 
356
/// Return which variable (position on the vector of variables) this phi
 
357
/// represents on the sigmas list.
 
358
///
 
359
Instruction* SSI::getPositionSigma(PHINode *PN) {
 
360
  DenseMap<PHINode *, Instruction*>::iterator val = sigmas.find(PN);
 
361
  if (val == sigmas.end())
 
362
    return 0;
 
363
  else
 
364
    return val->second;
 
365
}
 
366
 
 
367
/// Initializes
 
368
///
 
369
void SSI::init(SmallVectorImpl<Instruction *> &value) {
 
370
  for (SmallVectorImpl<Instruction *>::iterator I = value.begin(),
 
371
       E = value.end(); I != E; ++I) {
 
372
    value_original[*I] = (*I)->getParent();
 
373
    defsites[*I].push_back((*I)->getParent());
 
374
  }
 
375
}
 
376
 
 
377
/// Clean all used resources in this creation of SSI
 
378
///
 
379
void SSI::clean() {
 
380
  phis.clear();
 
381
  sigmas.clear();
 
382
  phisToFix.clear();
 
383
 
 
384
  defsites.clear();
 
385
  value_stack.clear();
 
386
  value_original.clear();
 
387
}
 
388
 
 
389
/// createSSIPass - The public interface to this file...
 
390
///
 
391
FunctionPass *llvm::createSSIPass() { return new SSI(); }
 
392
 
 
393
char SSI::ID = 0;
 
394
static RegisterPass<SSI> X("ssi", "Static Single Information Construction");
 
395
 
 
396
/// SSIEverything - A pass that runs createSSI on every non-void variable,
 
397
/// intended for debugging.
 
398
namespace {
 
399
  struct SSIEverything : public FunctionPass {
 
400
    static char ID; // Pass identification, replacement for typeid
 
401
    SSIEverything() : FunctionPass(&ID) {}
 
402
 
 
403
    bool runOnFunction(Function &F);
 
404
 
 
405
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
406
      AU.addRequired<SSI>();
 
407
    }
 
408
  };
 
409
}
 
410
 
 
411
bool SSIEverything::runOnFunction(Function &F) {
 
412
  SmallVector<Instruction *, 16> Insts;
 
413
  SSI &ssi = getAnalysis<SSI>();
 
414
 
 
415
  if (F.isDeclaration() || F.isIntrinsic()) return false;
 
416
 
 
417
  for (Function::iterator B = F.begin(), BE = F.end(); B != BE; ++B)
 
418
    for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I)
 
419
      if (!I->getType()->isVoidTy())
 
420
        Insts.push_back(I);
 
421
 
 
422
  ssi.createSSI(Insts);
 
423
  return true;
 
424
}
 
425
 
 
426
/// createSSIEverythingPass - The public interface to this file...
 
427
///
 
428
FunctionPass *llvm::createSSIEverythingPass() { return new SSIEverything(); }
 
429
 
 
430
char SSIEverything::ID = 0;
 
431
static RegisterPass<SSIEverything>
 
432
Y("ssi-everything", "Static Single Information Construction");