← 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/Analysis/ProfileEstimatorPass.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/Analysis/ProfileEstimatorPass.cpp
 
1
//===- ProfileEstimatorPass.cpp - LLVM Pass to estimate profile info ------===//
 
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 concrete implementation of profiling information that
 
11
// estimates the profiling information in a very crude and unimaginative way.
 
12
//
 
13
//===----------------------------------------------------------------------===//
 
14
#define DEBUG_TYPE "profile-estimator"
 
15
#include "llvm/Pass.h"
 
16
#include "llvm/Analysis/Passes.h"
 
17
#include "llvm/Analysis/ProfileInfo.h"
 
18
#include "llvm/Analysis/LoopInfo.h"
 
19
#include "llvm/Support/CommandLine.h"
 
20
#include "llvm/Support/Debug.h"
 
21
#include "llvm/Support/raw_ostream.h"
 
22
#include "llvm/Support/Format.h"
 
23
using namespace llvm;
 
24
 
 
25
static cl::opt<double>
 
26
LoopWeight(
 
27
    "profile-estimator-loop-weight", cl::init(10),
 
28
    cl::value_desc("loop-weight"),
 
29
    cl::desc("Number of loop executions used for profile-estimator")
 
30
);
 
31
 
 
32
namespace {
 
33
  class ProfileEstimatorPass : public FunctionPass, public ProfileInfo {
 
34
    double ExecCount;
 
35
    LoopInfo *LI;
 
36
    std::set<BasicBlock*>  BBToVisit;
 
37
    std::map<Loop*,double> LoopExitWeights;
 
38
    std::map<Edge,double>  MinimalWeight;
 
39
  public:
 
40
    static char ID; // Class identification, replacement for typeinfo
 
41
    explicit ProfileEstimatorPass(const double execcount = 0)
 
42
      : FunctionPass(&ID), ExecCount(execcount) {
 
43
      if (execcount == 0) ExecCount = LoopWeight;
 
44
    }
 
45
 
 
46
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
47
      AU.setPreservesAll();
 
48
      AU.addRequired<LoopInfo>();
 
49
    }
 
50
 
 
51
    virtual const char *getPassName() const {
 
52
      return "Profiling information estimator";
 
53
    }
 
54
 
 
55
    /// run - Estimate the profile information from the specified file.
 
56
    virtual bool runOnFunction(Function &F);
 
57
 
 
58
    /// getAdjustedAnalysisPointer - This method is used when a pass implements
 
59
    /// an analysis interface through multiple inheritance.  If needed, it
 
60
    /// should override this to adjust the this pointer as needed for the
 
61
    /// specified pass info.
 
62
    virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) {
 
63
      if (PI->isPassID(&ProfileInfo::ID))
 
64
        return (ProfileInfo*)this;
 
65
      return this;
 
66
    }
 
67
    
 
68
    virtual void recurseBasicBlock(BasicBlock *BB);
 
69
 
 
70
    void inline printEdgeWeight(Edge);
 
71
  };
 
72
}  // End of anonymous namespace
 
73
 
 
74
char ProfileEstimatorPass::ID = 0;
 
75
static RegisterPass<ProfileEstimatorPass>
 
76
X("profile-estimator", "Estimate profiling information", false, true);
 
77
 
 
78
static RegisterAnalysisGroup<ProfileInfo> Y(X);
 
79
 
 
80
namespace llvm {
 
81
  const PassInfo *ProfileEstimatorPassID = &X;
 
82
 
 
83
  FunctionPass *createProfileEstimatorPass() {
 
84
    return new ProfileEstimatorPass();
 
85
  }
 
86
 
 
87
  /// createProfileEstimatorPass - This function returns a Pass that estimates
 
88
  /// profiling information using the given loop execution count.
 
89
  Pass *createProfileEstimatorPass(const unsigned execcount) {
 
90
    return new ProfileEstimatorPass(execcount);
 
91
  }
 
92
}
 
93
 
 
94
static double ignoreMissing(double w) {
 
95
  if (w == ProfileInfo::MissingValue) return 0;
 
96
  return w;
 
97
}
 
98
 
 
99
static void inline printEdgeError(ProfileInfo::Edge e, const char *M) {
 
100
  DEBUG(dbgs() << "-- Edge " << e << " is not calculated, " << M << "\n");
 
101
}
 
102
 
 
103
void inline ProfileEstimatorPass::printEdgeWeight(Edge E) {
 
104
  DEBUG(dbgs() << "-- Weight of Edge " << E << ":"
 
105
               << format("%20.20g", getEdgeWeight(E)) << "\n");
 
106
}
 
107
 
 
108
// recurseBasicBlock() - This calculates the ProfileInfo estimation for a
 
109
// single block and then recurses into the successors.
 
110
// The algorithm preserves the flow condition, meaning that the sum of the
 
111
// weight of the incoming edges must be equal the block weight which must in
 
112
// turn be equal to the sume of the weights of the outgoing edges.
 
113
// Since the flow of an block is deterimined from the current state of the
 
114
// flow, once an edge has a flow assigned this flow is never changed again,
 
115
// otherwise it would be possible to violate the flow condition in another
 
116
// block.
 
117
void ProfileEstimatorPass::recurseBasicBlock(BasicBlock *BB) {
 
118
 
 
119
  // Break the recursion if this BasicBlock was already visited.
 
120
  if (BBToVisit.find(BB) == BBToVisit.end()) return;
 
121
 
 
122
  // Read the LoopInfo for this block.
 
123
  bool  BBisHeader = LI->isLoopHeader(BB);
 
124
  Loop* BBLoop     = LI->getLoopFor(BB);
 
125
 
 
126
  // To get the block weight, read all incoming edges.
 
127
  double BBWeight = 0;
 
128
  std::set<BasicBlock*> ProcessedPreds;
 
129
  for ( pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 
130
        bbi != bbe; ++bbi ) {
 
131
    // If this block was not considered already, add weight.
 
132
    Edge edge = getEdge(*bbi,BB);
 
133
    double w = getEdgeWeight(edge);
 
134
    if (ProcessedPreds.insert(*bbi).second) {
 
135
      BBWeight += ignoreMissing(w);
 
136
    }
 
137
    // If this block is a loop header and the predecessor is contained in this
 
138
    // loop, thus the edge is a backedge, continue and do not check if the
 
139
    // value is valid.
 
140
    if (BBisHeader && BBLoop->contains(*bbi)) {
 
141
      printEdgeError(edge, "but is backedge, continueing");
 
142
      continue;
 
143
    }
 
144
    // If the edges value is missing (and this is no loop header, and this is
 
145
    // no backedge) return, this block is currently non estimatable.
 
146
    if (w == MissingValue) {
 
147
      printEdgeError(edge, "returning");
 
148
      return;
 
149
    }
 
150
  }
 
151
  if (getExecutionCount(BB) != MissingValue) {
 
152
    BBWeight = getExecutionCount(BB);
 
153
  }
 
154
 
 
155
  // Fetch all necessary information for current block.
 
156
  SmallVector<Edge, 8> ExitEdges;
 
157
  SmallVector<Edge, 8> Edges;
 
158
  if (BBLoop) {
 
159
    BBLoop->getExitEdges(ExitEdges);
 
160
  }
 
161
 
 
162
  // If this is a loop header, consider the following:
 
163
  // Exactly the flow that is entering this block, must exit this block too. So
 
164
  // do the following: 
 
165
  // *) get all the exit edges, read the flow that is already leaving this
 
166
  // loop, remember the edges that do not have any flow on them right now.
 
167
  // (The edges that have already flow on them are most likely exiting edges of
 
168
  // other loops, do not touch those flows because the previously caclulated
 
169
  // loopheaders would not be exact anymore.)
 
170
  // *) In case there is not a single exiting edge left, create one at the loop
 
171
  // latch to prevent the flow from building up in the loop.
 
172
  // *) Take the flow that is not leaving the loop already and distribute it on
 
173
  // the remaining exiting edges.
 
174
  // (This ensures that all flow that enters the loop also leaves it.)
 
175
  // *) Increase the flow into the loop by increasing the weight of this block.
 
176
  // There is at least one incoming backedge that will bring us this flow later
 
177
  // on. (So that the flow condition in this node is valid again.)
 
178
  if (BBisHeader) {
 
179
    double incoming = BBWeight;
 
180
    // Subtract the flow leaving the loop.
 
181
    std::set<Edge> ProcessedExits;
 
182
    for (SmallVector<Edge, 8>::iterator ei = ExitEdges.begin(),
 
183
         ee = ExitEdges.end(); ei != ee; ++ei) {
 
184
      if (ProcessedExits.insert(*ei).second) {
 
185
        double w = getEdgeWeight(*ei);
 
186
        if (w == MissingValue) {
 
187
          Edges.push_back(*ei);
 
188
          // Check if there is a necessary minimal weight, if yes, subtract it 
 
189
          // from weight.
 
190
          if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
 
191
            incoming -= MinimalWeight[*ei];
 
192
            DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
 
193
          }
 
194
        } else {
 
195
          incoming -= w;
 
196
        }
 
197
      }
 
198
    }
 
199
    // If no exit edges, create one:
 
200
    if (Edges.size() == 0) {
 
201
      BasicBlock *Latch = BBLoop->getLoopLatch();
 
202
      if (Latch) {
 
203
        Edge edge = getEdge(Latch,0);
 
204
        EdgeInformation[BB->getParent()][edge] = BBWeight;
 
205
        printEdgeWeight(edge);
 
206
        edge = getEdge(Latch, BB);
 
207
        EdgeInformation[BB->getParent()][edge] = BBWeight * ExecCount;
 
208
        printEdgeWeight(edge);
 
209
      }
 
210
    }
 
211
 
 
212
    // Distribute remaining weight to the exting edges. To prevent fractions
 
213
    // from building up and provoking precision problems the weight which is to
 
214
    // be distributed is split and the rounded, the last edge gets a somewhat
 
215
    // bigger value, but we are close enough for an estimation.
 
216
    double fraction = floor(incoming/Edges.size());
 
217
    for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
 
218
         ei != ee; ++ei) {
 
219
      double w = 0;
 
220
      if (ei != (ee-1)) {
 
221
        w = fraction;
 
222
        incoming -= fraction;
 
223
      } else {
 
224
        w = incoming;
 
225
      }
 
226
      EdgeInformation[BB->getParent()][*ei] += w;
 
227
      // Read necessary minimal weight.
 
228
      if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
 
229
        EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei];
 
230
        DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
 
231
      }
 
232
      printEdgeWeight(*ei);
 
233
      
 
234
      // Add minimal weight to paths to all exit edges, this is used to ensure
 
235
      // that enough flow is reaching this edges.
 
236
      Path p;
 
237
      const BasicBlock *Dest = GetPath(BB, (*ei).first, p, GetPathToDest);
 
238
      while (Dest != BB) {
 
239
        const BasicBlock *Parent = p.find(Dest)->second;
 
240
        Edge e = getEdge(Parent, Dest);
 
241
        if (MinimalWeight.find(e) == MinimalWeight.end()) {
 
242
          MinimalWeight[e] = 0;
 
243
        }
 
244
        MinimalWeight[e] += w;
 
245
        DEBUG(dbgs() << "Minimal Weight for " << e << ": " << format("%.20g",MinimalWeight[e]) << "\n");
 
246
        Dest = Parent;
 
247
      }
 
248
    }
 
249
    // Increase flow into the loop.
 
250
    BBWeight *= (ExecCount+1);
 
251
  }
 
252
 
 
253
  BlockInformation[BB->getParent()][BB] = BBWeight;
 
254
  // Up until now we considered only the loop exiting edges, now we have a
 
255
  // definite block weight and must distribute this onto the outgoing edges.
 
256
  // Since there may be already flow attached to some of the edges, read this
 
257
  // flow first and remember the edges that have still now flow attached.
 
258
  Edges.clear();
 
259
  std::set<BasicBlock*> ProcessedSuccs;
 
260
 
 
261
  succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 
262
  // Also check for (BB,0) edges that may already contain some flow. (But only
 
263
  // in case there are no successors.)
 
264
  if (bbi == bbe) {
 
265
    Edge edge = getEdge(BB,0);
 
266
    EdgeInformation[BB->getParent()][edge] = BBWeight;
 
267
    printEdgeWeight(edge);
 
268
  }
 
269
  for ( ; bbi != bbe; ++bbi ) {
 
270
    if (ProcessedSuccs.insert(*bbi).second) {
 
271
      Edge edge = getEdge(BB,*bbi);
 
272
      double w = getEdgeWeight(edge);
 
273
      if (w != MissingValue) {
 
274
        BBWeight -= getEdgeWeight(edge);
 
275
      } else {
 
276
        Edges.push_back(edge);
 
277
        // If minimal weight is necessary, reserve weight by subtracting weight
 
278
        // from block weight, this is readded later on.
 
279
        if (MinimalWeight.find(edge) != MinimalWeight.end()) {
 
280
          BBWeight -= MinimalWeight[edge];
 
281
          DEBUG(dbgs() << "Reserving " << format("%.20g",MinimalWeight[edge]) << " at " << edge << "\n");
 
282
        }
 
283
      }
 
284
    }
 
285
  }
 
286
 
 
287
  double fraction = floor(BBWeight/Edges.size());
 
288
  // Finally we know what flow is still not leaving the block, distribute this
 
289
  // flow onto the empty edges.
 
290
  for (SmallVector<Edge, 8>::iterator ei = Edges.begin(), ee = Edges.end();
 
291
       ei != ee; ++ei) {
 
292
    if (ei != (ee-1)) {
 
293
      EdgeInformation[BB->getParent()][*ei] += fraction;
 
294
      BBWeight -= fraction;
 
295
    } else {
 
296
      EdgeInformation[BB->getParent()][*ei] += BBWeight;
 
297
    }
 
298
    // Readd minial necessary weight.
 
299
    if (MinimalWeight.find(*ei) != MinimalWeight.end()) {
 
300
      EdgeInformation[BB->getParent()][*ei] += MinimalWeight[*ei];
 
301
      DEBUG(dbgs() << "Additionally " << format("%.20g",MinimalWeight[*ei]) << " at " << (*ei) << "\n");
 
302
    }
 
303
    printEdgeWeight(*ei);
 
304
  }
 
305
 
 
306
  // This block is visited, mark this before the recursion.
 
307
  BBToVisit.erase(BB);
 
308
 
 
309
  // Recurse into successors.
 
310
  for (succ_iterator bbi = succ_begin(BB), bbe = succ_end(BB);
 
311
       bbi != bbe; ++bbi) {
 
312
    recurseBasicBlock(*bbi);
 
313
  }
 
314
}
 
315
 
 
316
bool ProfileEstimatorPass::runOnFunction(Function &F) {
 
317
  if (F.isDeclaration()) return false;
 
318
 
 
319
  // Fetch LoopInfo and clear ProfileInfo for this function.
 
320
  LI = &getAnalysis<LoopInfo>();
 
321
  FunctionInformation.erase(&F);
 
322
  BlockInformation[&F].clear();
 
323
  EdgeInformation[&F].clear();
 
324
 
 
325
  // Mark all blocks as to visit.
 
326
  for (Function::iterator bi = F.begin(), be = F.end(); bi != be; ++bi)
 
327
    BBToVisit.insert(bi);
 
328
 
 
329
  // Clear Minimal Edges.
 
330
  MinimalWeight.clear();
 
331
 
 
332
  DEBUG(dbgs() << "Working on function " << F.getNameStr() << "\n");
 
333
 
 
334
  // Since the entry block is the first one and has no predecessors, the edge
 
335
  // (0,entry) is inserted with the starting weight of 1.
 
336
  BasicBlock *entry = &F.getEntryBlock();
 
337
  BlockInformation[&F][entry] = pow(2.0, 32.0);
 
338
  Edge edge = getEdge(0,entry);
 
339
  EdgeInformation[&F][edge] = BlockInformation[&F][entry];
 
340
  printEdgeWeight(edge);
 
341
 
 
342
  // Since recurseBasicBlock() maybe returns with a block which was not fully
 
343
  // estimated, use recurseBasicBlock() until everything is calculated.
 
344
  bool cleanup = false;
 
345
  recurseBasicBlock(entry);
 
346
  while (BBToVisit.size() > 0 && !cleanup) {
 
347
    // Remember number of open blocks, this is later used to check if progress
 
348
    // was made.
 
349
    unsigned size = BBToVisit.size();
 
350
 
 
351
    // Try to calculate all blocks in turn.
 
352
    for (std::set<BasicBlock*>::iterator bi = BBToVisit.begin(),
 
353
         be = BBToVisit.end(); bi != be; ++bi) {
 
354
      recurseBasicBlock(*bi);
 
355
      // If at least one block was finished, break because iterator may be
 
356
      // invalid.
 
357
      if (BBToVisit.size() < size) break;
 
358
    }
 
359
 
 
360
    // If there was not a single block resolved, make some assumptions.
 
361
    if (BBToVisit.size() == size) {
 
362
      bool found = false;
 
363
      for (std::set<BasicBlock*>::iterator BBI = BBToVisit.begin(), BBE = BBToVisit.end(); 
 
364
           (BBI != BBE) && (!found); ++BBI) {
 
365
        BasicBlock *BB = *BBI;
 
366
        // Try each predecessor if it can be assumend.
 
367
        for (pred_iterator bbi = pred_begin(BB), bbe = pred_end(BB);
 
368
             (bbi != bbe) && (!found); ++bbi) {
 
369
          Edge e = getEdge(*bbi,BB);
 
370
          double w = getEdgeWeight(e);
 
371
          // Check that edge from predecessor is still free.
 
372
          if (w == MissingValue) {
 
373
            // Check if there is a circle from this block to predecessor.
 
374
            Path P;
 
375
            const BasicBlock *Dest = GetPath(BB, *bbi, P, GetPathToDest);
 
376
            if (Dest != *bbi) {
 
377
              // If there is no circle, just set edge weight to 0
 
378
              EdgeInformation[&F][e] = 0;
 
379
              DEBUG(dbgs() << "Assuming edge weight: ");
 
380
              printEdgeWeight(e);
 
381
              found = true;
 
382
            }
 
383
          }
 
384
        }
 
385
      }
 
386
      if (!found) {
 
387
        cleanup = true;
 
388
        DEBUG(dbgs() << "No assumption possible in Fuction "<<F.getName()<<", setting all to zero\n");
 
389
      }
 
390
    }
 
391
  }
 
392
  // In case there was no safe way to assume edges, set as a last measure, 
 
393
  // set _everything_ to zero.
 
394
  if (cleanup) {
 
395
    FunctionInformation[&F] = 0;
 
396
    BlockInformation[&F].clear();
 
397
    EdgeInformation[&F].clear();
 
398
    for (Function::const_iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
 
399
      const BasicBlock *BB = &(*FI);
 
400
      BlockInformation[&F][BB] = 0;
 
401
      pred_const_iterator predi = pred_begin(BB), prede = pred_end(BB);
 
402
      if (predi == prede) {
 
403
        Edge e = getEdge(0,BB);
 
404
        setEdgeWeight(e,0);
 
405
      }
 
406
      for (;predi != prede; ++predi) {
 
407
        Edge e = getEdge(*predi,BB);
 
408
        setEdgeWeight(e,0);
 
409
      }
 
410
      succ_const_iterator succi = succ_begin(BB), succe = succ_end(BB);
 
411
      if (succi == succe) {
 
412
        Edge e = getEdge(BB,0);
 
413
        setEdgeWeight(e,0);
 
414
      }
 
415
      for (;succi != succe; ++succi) {
 
416
        Edge e = getEdge(*succi,BB);
 
417
        setEdgeWeight(e,0);
 
418
      }
 
419
    }
 
420
  }
 
421
 
 
422
  return false;
 
423
}