← 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/Instrumentation/OptimalEdgeProfiling.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/Instrumentation/OptimalEdgeProfiling.cpp
 
1
//===- OptimalEdgeProfiling.cpp - Insert counters for opt. edge profiling -===//
 
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 instruments the specified program with counters for edge profiling.
 
11
// Edge profiling can give a reasonable approximation of the hot paths through a
 
12
// program, and is used for a wide variety of program transformations.
 
13
//
 
14
//===----------------------------------------------------------------------===//
 
15
#define DEBUG_TYPE "insert-optimal-edge-profiling"
 
16
#include "ProfilingUtils.h"
 
17
#include "llvm/Module.h"
 
18
#include "llvm/Pass.h"
 
19
#include "llvm/Analysis/Passes.h"
 
20
#include "llvm/Analysis/ProfileInfo.h"
 
21
#include "llvm/Analysis/ProfileInfoLoader.h"
 
22
#include "llvm/Support/raw_ostream.h"
 
23
#include "llvm/Support/Debug.h"
 
24
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
25
#include "llvm/Transforms/Instrumentation.h"
 
26
#include "llvm/ADT/DenseSet.h"
 
27
#include "llvm/ADT/Statistic.h"
 
28
#include "MaximumSpanningTree.h"
 
29
#include <set>
 
30
using namespace llvm;
 
31
 
 
32
STATISTIC(NumEdgesInserted, "The # of edges inserted.");
 
33
 
 
34
namespace {
 
35
  class OptimalEdgeProfiler : public ModulePass {
 
36
    bool runOnModule(Module &M);
 
37
  public:
 
38
    static char ID; // Pass identification, replacement for typeid
 
39
    OptimalEdgeProfiler() : ModulePass(&ID) {}
 
40
 
 
41
    void getAnalysisUsage(AnalysisUsage &AU) const {
 
42
      AU.addRequiredID(ProfileEstimatorPassID);
 
43
      AU.addRequired<ProfileInfo>();
 
44
    }
 
45
 
 
46
    virtual const char *getPassName() const {
 
47
      return "Optimal Edge Profiler";
 
48
    }
 
49
  };
 
50
}
 
51
 
 
52
char OptimalEdgeProfiler::ID = 0;
 
53
static RegisterPass<OptimalEdgeProfiler>
 
54
X("insert-optimal-edge-profiling", 
 
55
  "Insert optimal instrumentation for edge profiling");
 
56
 
 
57
ModulePass *llvm::createOptimalEdgeProfilerPass() {
 
58
  return new OptimalEdgeProfiler();
 
59
}
 
60
 
 
61
inline static void printEdgeCounter(ProfileInfo::Edge e,
 
62
                                    BasicBlock* b,
 
63
                                    unsigned i) {
 
64
  DEBUG(dbgs() << "--Edge Counter for " << (e) << " in " \
 
65
               << ((b)?(b)->getNameStr():"0") << " (# " << (i) << ")\n");
 
66
}
 
67
 
 
68
bool OptimalEdgeProfiler::runOnModule(Module &M) {
 
69
  Function *Main = M.getFunction("main");
 
70
  if (Main == 0) {
 
71
    errs() << "WARNING: cannot insert edge profiling into a module"
 
72
           << " with no main function!\n";
 
73
    return false;  // No main, no instrumentation!
 
74
  }
 
75
 
 
76
  // NumEdges counts all the edges that may be instrumented. Later on its
 
77
  // decided which edges to actually instrument, to achieve optimal profiling.
 
78
  // For the entry block a virtual edge (0,entry) is reserved, for each block
 
79
  // with no successors an edge (BB,0) is reserved. These edges are necessary
 
80
  // to calculate a truly optimal maximum spanning tree and thus an optimal
 
81
  // instrumentation.
 
82
  unsigned NumEdges = 0;
 
83
 
 
84
  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
 
85
    if (F->isDeclaration()) continue;
 
86
    // Reserve space for (0,entry) edge.
 
87
    ++NumEdges;
 
88
    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
 
89
      // Keep track of which blocks need to be instrumented.  We don't want to
 
90
      // instrument blocks that are added as the result of breaking critical
 
91
      // edges!
 
92
      if (BB->getTerminator()->getNumSuccessors() == 0) {
 
93
        // Reserve space for (BB,0) edge.
 
94
        ++NumEdges;
 
95
      } else {
 
96
        NumEdges += BB->getTerminator()->getNumSuccessors();
 
97
      }
 
98
    }
 
99
  }
 
100
 
 
101
  // In the profiling output a counter for each edge is reserved, but only few
 
102
  // are used. This is done to be able to read back in the profile without
 
103
  // calulating the maximum spanning tree again, instead each edge counter that
 
104
  // is not used is initialised with -1 to signal that this edge counter has to
 
105
  // be calculated from other edge counters on reading the profile info back
 
106
  // in.
 
107
 
 
108
  const Type *Int32 = Type::getInt32Ty(M.getContext());
 
109
  const ArrayType *ATy = ArrayType::get(Int32, NumEdges);
 
110
  GlobalVariable *Counters =
 
111
    new GlobalVariable(M, ATy, false, GlobalValue::InternalLinkage,
 
112
                       Constant::getNullValue(ATy), "OptEdgeProfCounters");
 
113
  NumEdgesInserted = 0;
 
114
 
 
115
  std::vector<Constant*> Initializer(NumEdges);
 
116
  Constant* Zero = ConstantInt::get(Int32, 0);
 
117
  Constant* Uncounted = ConstantInt::get(Int32, ProfileInfoLoader::Uncounted);
 
118
 
 
119
  // Instrument all of the edges not in MST...
 
120
  unsigned i = 0;
 
121
  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
 
122
    if (F->isDeclaration()) continue;
 
123
    DEBUG(dbgs()<<"Working on "<<F->getNameStr()<<"\n");
 
124
 
 
125
    // Calculate a Maximum Spanning Tree with the edge weights determined by
 
126
    // ProfileEstimator. ProfileEstimator also assign weights to the virtual
 
127
    // edges (0,entry) and (BB,0) (for blocks with no successors) and this
 
128
    // edges also participate in the maximum spanning tree calculation. 
 
129
    // The third parameter of MaximumSpanningTree() has the effect that not the
 
130
    // actual MST is returned but the edges _not_ in the MST.
 
131
 
 
132
    ProfileInfo::EdgeWeights ECs = 
 
133
      getAnalysis<ProfileInfo>(*F).getEdgeWeights(F);
 
134
    std::vector<ProfileInfo::EdgeWeight> EdgeVector(ECs.begin(), ECs.end());
 
135
    MaximumSpanningTree<BasicBlock> MST (EdgeVector);
 
136
    std::stable_sort(MST.begin(),MST.end());
 
137
 
 
138
    // Check if (0,entry) not in the MST. If not, instrument edge
 
139
    // (IncrementCounterInBlock()) and set the counter initially to zero, if
 
140
    // the edge is in the MST the counter is initialised to -1.
 
141
 
 
142
    BasicBlock *entry = &(F->getEntryBlock());
 
143
    ProfileInfo::Edge edge = ProfileInfo::getEdge(0,entry);
 
144
    if (!std::binary_search(MST.begin(), MST.end(), edge)) {
 
145
      printEdgeCounter(edge,entry,i);
 
146
      IncrementCounterInBlock(entry, i, Counters); NumEdgesInserted++;
 
147
      Initializer[i++] = (Zero);
 
148
    } else{
 
149
      Initializer[i++] = (Uncounted);
 
150
    }
 
151
 
 
152
    // InsertedBlocks contains all blocks that were inserted for splitting an
 
153
    // edge, this blocks do not have to be instrumented.
 
154
    DenseSet<BasicBlock*> InsertedBlocks;
 
155
    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
 
156
      // Check if block was not inserted and thus does not have to be
 
157
      // instrumented.
 
158
      if (InsertedBlocks.count(BB)) continue;
 
159
 
 
160
      // Okay, we have to add a counter of each outgoing edge not in MST. If
 
161
      // the outgoing edge is not critical don't split it, just insert the
 
162
      // counter in the source or destination of the edge. Also, if the block
 
163
      // has no successors, the virtual edge (BB,0) is processed.
 
164
      TerminatorInst *TI = BB->getTerminator();
 
165
      if (TI->getNumSuccessors() == 0) {
 
166
        ProfileInfo::Edge edge = ProfileInfo::getEdge(BB,0);
 
167
        if (!std::binary_search(MST.begin(), MST.end(), edge)) {
 
168
          printEdgeCounter(edge,BB,i);
 
169
          IncrementCounterInBlock(BB, i, Counters); NumEdgesInserted++;
 
170
          Initializer[i++] = (Zero);
 
171
        } else{
 
172
          Initializer[i++] = (Uncounted);
 
173
        }
 
174
      }
 
175
      for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) {
 
176
        BasicBlock *Succ = TI->getSuccessor(s);
 
177
        ProfileInfo::Edge edge = ProfileInfo::getEdge(BB,Succ);
 
178
        if (!std::binary_search(MST.begin(), MST.end(), edge)) {
 
179
 
 
180
          // If the edge is critical, split it.
 
181
          bool wasInserted = SplitCriticalEdge(TI, s, this);
 
182
          Succ = TI->getSuccessor(s);
 
183
          if (wasInserted)
 
184
            InsertedBlocks.insert(Succ);
 
185
 
 
186
          // Okay, we are guaranteed that the edge is no longer critical.  If
 
187
          // we only have a single successor, insert the counter in this block,
 
188
          // otherwise insert it in the successor block.
 
189
          if (TI->getNumSuccessors() == 1) {
 
190
            // Insert counter at the start of the block
 
191
            printEdgeCounter(edge,BB,i);
 
192
            IncrementCounterInBlock(BB, i, Counters); NumEdgesInserted++;
 
193
          } else {
 
194
            // Insert counter at the start of the block
 
195
            printEdgeCounter(edge,Succ,i);
 
196
            IncrementCounterInBlock(Succ, i, Counters); NumEdgesInserted++;
 
197
          }
 
198
          Initializer[i++] = (Zero);
 
199
        } else {
 
200
          Initializer[i++] = (Uncounted);
 
201
        }
 
202
      }
 
203
    }
 
204
  }
 
205
 
 
206
  // Check if the number of edges counted at first was the number of edges we
 
207
  // considered for instrumentation.
 
208
  assert(i==NumEdges && "the number of edges in counting array is wrong");
 
209
 
 
210
  // Assing the now completely defined initialiser to the array.
 
211
  Constant *init = ConstantArray::get(ATy, Initializer);
 
212
  Counters->setInitializer(init);
 
213
 
 
214
  // Add the initialization call to main.
 
215
  InsertProfilingInitCall(Main, "llvm_start_opt_edge_profiling", Counters);
 
216
  return true;
 
217
}
 
218