← Back to branch summary

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

« back to all changes in this revision

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