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