← 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/LiveValues.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/LiveValues.cpp
 
1
//===- LiveValues.cpp - Liveness information for LLVM IR Values. ----------===//
 
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 defines the implementation for the LLVM IR Value liveness
 
11
// analysis pass.
 
12
//
 
13
//===----------------------------------------------------------------------===//
 
14
 
 
15
#include "llvm/Analysis/LiveValues.h"
 
16
#include "llvm/Analysis/Dominators.h"
 
17
#include "llvm/Analysis/LoopInfo.h"
 
18
using namespace llvm;
 
19
 
 
20
namespace llvm {
 
21
  FunctionPass *createLiveValuesPass() { return new LiveValues(); }
 
22
}
 
23
 
 
24
char LiveValues::ID = 0;
 
25
static RegisterPass<LiveValues>
 
26
X("live-values", "Value Liveness Analysis", false, true);
 
27
 
 
28
LiveValues::LiveValues() : FunctionPass(&ID) {}
 
29
 
 
30
void LiveValues::getAnalysisUsage(AnalysisUsage &AU) const {
 
31
  AU.addRequired<DominatorTree>();
 
32
  AU.addRequired<LoopInfo>();
 
33
  AU.setPreservesAll();
 
34
}
 
35
 
 
36
bool LiveValues::runOnFunction(Function &F) {
 
37
  DT = &getAnalysis<DominatorTree>();
 
38
  LI = &getAnalysis<LoopInfo>();
 
39
 
 
40
  // This pass' values are computed lazily, so there's nothing to do here.
 
41
 
 
42
  return false;
 
43
}
 
44
 
 
45
void LiveValues::releaseMemory() {
 
46
  Memos.clear();
 
47
}
 
48
 
 
49
/// isUsedInBlock - Test if the given value is used in the given block.
 
50
///
 
51
bool LiveValues::isUsedInBlock(const Value *V, const BasicBlock *BB) {
 
52
  Memo &M = getMemo(V);
 
53
  return M.Used.count(BB);
 
54
}
 
55
 
 
56
/// isLiveThroughBlock - Test if the given value is known to be
 
57
/// live-through the given block, meaning that the block is properly
 
58
/// dominated by the value's definition, and there exists a block
 
59
/// reachable from it that contains a use. This uses a conservative
 
60
/// approximation that errs on the side of returning false.
 
61
///
 
62
bool LiveValues::isLiveThroughBlock(const Value *V,
 
63
                                    const BasicBlock *BB) {
 
64
  Memo &M = getMemo(V);
 
65
  return M.LiveThrough.count(BB);
 
66
}
 
67
 
 
68
/// isKilledInBlock - Test if the given value is known to be killed in
 
69
/// the given block, meaning that the block contains a use of the value,
 
70
/// and no blocks reachable from the block contain a use. This uses a
 
71
/// conservative approximation that errs on the side of returning false.
 
72
///
 
73
bool LiveValues::isKilledInBlock(const Value *V, const BasicBlock *BB) {
 
74
  Memo &M = getMemo(V);
 
75
  return M.Killed.count(BB);
 
76
}
 
77
 
 
78
/// getMemo - Retrieve an existing Memo for the given value if one
 
79
/// is available, otherwise compute a new one.
 
80
///
 
81
LiveValues::Memo &LiveValues::getMemo(const Value *V) {
 
82
  DenseMap<const Value *, Memo>::iterator I = Memos.find(V);
 
83
  if (I != Memos.end())
 
84
    return I->second;
 
85
  return compute(V);
 
86
}
 
87
 
 
88
/// getImmediateDominator - A handy utility for the specific DominatorTree
 
89
/// query that we need here.
 
90
///
 
91
static const BasicBlock *getImmediateDominator(const BasicBlock *BB,
 
92
                                               const DominatorTree *DT) {
 
93
  DomTreeNode *Node = DT->getNode(const_cast<BasicBlock *>(BB))->getIDom();
 
94
  return Node ? Node->getBlock() : 0;
 
95
}
 
96
 
 
97
/// compute - Compute a new Memo for the given value.
 
98
///
 
99
LiveValues::Memo &LiveValues::compute(const Value *V) {
 
100
  Memo &M = Memos[V];
 
101
 
 
102
  // Determine the block containing the definition.
 
103
  const BasicBlock *DefBB;
 
104
  // Instructions define values with meaningful live ranges.
 
105
  if (const Instruction *I = dyn_cast<Instruction>(V))
 
106
    DefBB = I->getParent();
 
107
  // Arguments can be analyzed as values defined in the entry block.
 
108
  else if (const Argument *A = dyn_cast<Argument>(V))
 
109
    DefBB = &A->getParent()->getEntryBlock();
 
110
  // Constants and other things aren't meaningful here, so just
 
111
  // return having computed an empty Memo so that we don't come
 
112
  // here again. The assumption here is that client code won't
 
113
  // be asking about such values very often.
 
114
  else
 
115
    return M;
 
116
 
 
117
  // Determine if the value is defined inside a loop. This is used
 
118
  // to track whether the value is ever used outside the loop, so
 
119
  // it'll be set to null if the value is either not defined in a
 
120
  // loop or used outside the loop in which it is defined.
 
121
  const Loop *L = LI->getLoopFor(DefBB);
 
122
 
 
123
  // Track whether the value is used anywhere outside of the block
 
124
  // in which it is defined.
 
125
  bool LiveOutOfDefBB = false;
 
126
 
 
127
  // Examine each use of the value.
 
128
  for (Value::use_const_iterator I = V->use_begin(), E = V->use_end();
 
129
       I != E; ++I) {
 
130
    const User *U = *I;
 
131
    const BasicBlock *UseBB = cast<Instruction>(U)->getParent();
 
132
 
 
133
    // Note the block in which this use occurs.
 
134
    M.Used.insert(UseBB);
 
135
 
 
136
    // If the use block doesn't have successors, the value can be
 
137
    // considered killed.
 
138
    if (succ_begin(UseBB) == succ_end(UseBB))
 
139
      M.Killed.insert(UseBB);
 
140
 
 
141
    // Observe whether the value is used outside of the loop in which
 
142
    // it is defined. Switch to an enclosing loop if necessary.
 
143
    for (; L; L = L->getParentLoop())
 
144
      if (L->contains(UseBB))
 
145
        break;
 
146
 
 
147
    // Search for live-through blocks.
 
148
    const BasicBlock *BB;
 
149
    if (const PHINode *PHI = dyn_cast<PHINode>(U)) {
 
150
      // For PHI nodes, start the search at the incoming block paired with the
 
151
      // incoming value, which must be dominated by the definition.
 
152
      unsigned Num = PHI->getIncomingValueNumForOperand(I.getOperandNo());
 
153
      BB = PHI->getIncomingBlock(Num);
 
154
 
 
155
      // A PHI-node use means the value is live-out of it's defining block
 
156
      // even if that block also contains the only use.
 
157
      LiveOutOfDefBB = true;
 
158
    } else {
 
159
      // Otherwise just start the search at the use.
 
160
      BB = UseBB;
 
161
 
 
162
      // Note if the use is outside the defining block.
 
163
      LiveOutOfDefBB |= UseBB != DefBB;
 
164
    }
 
165
 
 
166
    // Climb the immediate dominator tree from the use to the definition
 
167
    // and mark all intermediate blocks as live-through.
 
168
    for (; BB != DefBB; BB = getImmediateDominator(BB, DT)) {
 
169
      if (BB != UseBB && !M.LiveThrough.insert(BB))
 
170
        break;
 
171
    }
 
172
  }
 
173
 
 
174
  // If the value is defined inside a loop and is not live outside
 
175
  // the loop, then each exit block of the loop in which the value
 
176
  // is used is a kill block.
 
177
  if (L) {
 
178
    SmallVector<BasicBlock *, 4> ExitingBlocks;
 
179
    L->getExitingBlocks(ExitingBlocks);
 
180
    for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
 
181
      const BasicBlock *ExitingBlock = ExitingBlocks[i];
 
182
      if (M.Used.count(ExitingBlock))
 
183
        M.Killed.insert(ExitingBlock);
 
184
    }
 
185
  }
 
186
 
 
187
  // If the value was never used outside the block in which it was
 
188
  // defined, it's killed in that block.
 
189
  if (!LiveOutOfDefBB)
 
190
    M.Killed.insert(DefBB);
 
191
 
 
192
  return M;
 
193
}