← 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/BasicBlockPlacement.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/BasicBlockPlacement.cpp
 
1
//===-- BasicBlockPlacement.cpp - Basic Block Code Layout optimization ----===//
 
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 very simple profile guided basic block placement
 
11
// algorithm.  The idea is to put frequently executed blocks together at the
 
12
// start of the function, and hopefully increase the number of fall-through
 
13
// conditional branches.  If there is no profile information for a particular
 
14
// function, this pass basically orders blocks in depth-first order
 
15
//
 
16
// The algorithm implemented here is basically "Algo1" from "Profile Guided Code
 
17
// Positioning" by Pettis and Hansen, except that it uses basic block counts
 
18
// instead of edge counts.  This should be improved in many ways, but is very
 
19
// simple for now.
 
20
//
 
21
// Basically we "place" the entry block, then loop over all successors in a DFO,
 
22
// placing the most frequently executed successor until we run out of blocks.  I
 
23
// told you this was _extremely_ simplistic. :) This is also much slower than it
 
24
// could be.  When it becomes important, this pass will be rewritten to use a
 
25
// better algorithm, and then we can worry about efficiency.
 
26
//
 
27
//===----------------------------------------------------------------------===//
 
28
 
 
29
#define DEBUG_TYPE "block-placement"
 
30
#include "llvm/Analysis/ProfileInfo.h"
 
31
#include "llvm/Function.h"
 
32
#include "llvm/Pass.h"
 
33
#include "llvm/Support/CFG.h"
 
34
#include "llvm/ADT/Statistic.h"
 
35
#include "llvm/Transforms/Scalar.h"
 
36
#include <set>
 
37
using namespace llvm;
 
38
 
 
39
STATISTIC(NumMoved, "Number of basic blocks moved");
 
40
 
 
41
namespace {
 
42
  struct BlockPlacement : public FunctionPass {
 
43
    static char ID; // Pass identification, replacement for typeid
 
44
    BlockPlacement() : FunctionPass(&ID) {}
 
45
 
 
46
    virtual bool runOnFunction(Function &F);
 
47
 
 
48
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
49
      AU.setPreservesCFG();
 
50
      AU.addRequired<ProfileInfo>();
 
51
      //AU.addPreserved<ProfileInfo>();  // Does this work?
 
52
    }
 
53
  private:
 
54
    /// PI - The profile information that is guiding us.
 
55
    ///
 
56
    ProfileInfo *PI;
 
57
 
 
58
    /// NumMovedBlocks - Every time we move a block, increment this counter.
 
59
    ///
 
60
    unsigned NumMovedBlocks;
 
61
 
 
62
    /// PlacedBlocks - Every time we place a block, remember it so we don't get
 
63
    /// into infinite loops.
 
64
    std::set<BasicBlock*> PlacedBlocks;
 
65
 
 
66
    /// InsertPos - This an iterator to the next place we want to insert a
 
67
    /// block.
 
68
    Function::iterator InsertPos;
 
69
 
 
70
    /// PlaceBlocks - Recursively place the specified blocks and any unplaced
 
71
    /// successors.
 
72
    void PlaceBlocks(BasicBlock *BB);
 
73
  };
 
74
}
 
75
 
 
76
char BlockPlacement::ID = 0;
 
77
static RegisterPass<BlockPlacement>
 
78
X("block-placement", "Profile Guided Basic Block Placement");
 
79
 
 
80
FunctionPass *llvm::createBlockPlacementPass() { return new BlockPlacement(); }
 
81
 
 
82
bool BlockPlacement::runOnFunction(Function &F) {
 
83
  PI = &getAnalysis<ProfileInfo>();
 
84
 
 
85
  NumMovedBlocks = 0;
 
86
  InsertPos = F.begin();
 
87
 
 
88
  // Recursively place all blocks.
 
89
  PlaceBlocks(F.begin());
 
90
 
 
91
  PlacedBlocks.clear();
 
92
  NumMoved += NumMovedBlocks;
 
93
  return NumMovedBlocks != 0;
 
94
}
 
95
 
 
96
 
 
97
/// PlaceBlocks - Recursively place the specified blocks and any unplaced
 
98
/// successors.
 
99
void BlockPlacement::PlaceBlocks(BasicBlock *BB) {
 
100
  assert(!PlacedBlocks.count(BB) && "Already placed this block!");
 
101
  PlacedBlocks.insert(BB);
 
102
 
 
103
  // Place the specified block.
 
104
  if (&*InsertPos != BB) {
 
105
    // Use splice to move the block into the right place.  This avoids having to
 
106
    // remove the block from the function then readd it, which causes a bunch of
 
107
    // symbol table traffic that is entirely pointless.
 
108
    Function::BasicBlockListType &Blocks = BB->getParent()->getBasicBlockList();
 
109
    Blocks.splice(InsertPos, Blocks, BB);
 
110
 
 
111
    ++NumMovedBlocks;
 
112
  } else {
 
113
    // This block is already in the right place, we don't have to do anything.
 
114
    ++InsertPos;
 
115
  }
 
116
 
 
117
  // Keep placing successors until we run out of ones to place.  Note that this
 
118
  // loop is very inefficient (N^2) for blocks with many successors, like switch
 
119
  // statements.  FIXME!
 
120
  while (1) {
 
121
    // Okay, now place any unplaced successors.
 
122
    succ_iterator SI = succ_begin(BB), E = succ_end(BB);
 
123
 
 
124
    // Scan for the first unplaced successor.
 
125
    for (; SI != E && PlacedBlocks.count(*SI); ++SI)
 
126
      /*empty*/;
 
127
    if (SI == E) return;  // No more successors to place.
 
128
 
 
129
    double MaxExecutionCount = PI->getExecutionCount(*SI);
 
130
    BasicBlock *MaxSuccessor = *SI;
 
131
 
 
132
    // Scan for more frequently executed successors
 
133
    for (; SI != E; ++SI)
 
134
      if (!PlacedBlocks.count(*SI)) {
 
135
        double Count = PI->getExecutionCount(*SI);
 
136
        if (Count > MaxExecutionCount ||
 
137
            // Prefer to not disturb the code.
 
138
            (Count == MaxExecutionCount && *SI == &*InsertPos)) {
 
139
          MaxExecutionCount = Count;
 
140
          MaxSuccessor = *SI;
 
141
        }
 
142
      }
 
143
 
 
144
    // Now that we picked the maximally executed successor, place it.
 
145
    PlaceBlocks(MaxSuccessor);
 
146
  }
 
147
}