← 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/LiveValues.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/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
 
INITIALIZE_PASS(LiveValues, "live-values",
26
 
                "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::const_use_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
 
}