 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
77.8% |
56 / 72 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
86.1% |
62 / 72 |
| |
|
Line Coverage: |
84.2% |
128 / 152 |
| |
 |
|
 |
1 : //=- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==//
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 Live Variables analysis for source-level CFGs.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "clang/Analysis/Analyses/LiveVariables.h"
15 : #include "clang/Basic/SourceManager.h"
16 : #include "clang/AST/ASTContext.h"
17 : #include "clang/AST/Expr.h"
18 : #include "clang/Analysis/CFG.h"
19 : #include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
20 : #include "clang/Analysis/FlowSensitive/DataflowSolver.h"
21 : #include "clang/Analysis/Support/SaveAndRestore.h"
22 : #include "clang/Analysis/AnalysisContext.h"
23 : #include "llvm/ADT/SmallPtrSet.h"
24 : #include "llvm/ADT/SmallVector.h"
25 : #include "llvm/Support/raw_ostream.h"
26 :
27 : using namespace clang;
28 :
29 : //===----------------------------------------------------------------------===//
30 : // Useful constants.
31 : //===----------------------------------------------------------------------===//
32 :
33 : static const bool Alive = true;
34 : static const bool Dead = false;
35 :
36 : //===----------------------------------------------------------------------===//
37 : // Dataflow initialization logic.
38 : //===----------------------------------------------------------------------===//
39 :
40 : namespace {
41 : class RegisterDecls
42 : : public CFGRecStmtDeclVisitor<RegisterDecls> {
43 :
44 : LiveVariables::AnalysisDataTy& AD;
45 :
46 : typedef llvm::SmallVector<VarDecl*, 20> AlwaysLiveTy;
47 : AlwaysLiveTy AlwaysLive;
48 :
49 :
50 : public:
51 1998: RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
52 :
53 1998: ~RegisterDecls() {
54 :
55 1998: AD.AlwaysLive.resetValues(AD);
56 :
332: branch 2 taken
1998: branch 3 taken
57 2330: for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end();
58 : I != E; ++ I)
59 332: AD.AlwaysLive(*I, AD) = Alive;
60 1998: }
61 :
62 255: void VisitImplicitParamDecl(ImplicitParamDecl* IPD) {
63 : // Register the VarDecl for tracking.
64 255: AD.Register(IPD);
65 255: }
66 :
67 8321: void VisitVarDecl(VarDecl* VD) {
68 : // Register the VarDecl for tracking.
69 8321: AD.Register(VD);
70 :
71 : // Does the variable have global storage? If so, it is always live.
332: branch 1 taken
7989: branch 2 taken
72 8321: if (VD->hasGlobalStorage())
73 332: AlwaysLive.push_back(VD);
74 8321: }
75 :
76 22749: CFG& getCFG() { return AD.getCFG(); }
77 : };
78 : } // end anonymous namespace
79 :
80 1998: LiveVariables::LiveVariables(AnalysisContext &AC) {
81 : // Register all referenced VarDecls.
82 1998: CFG &cfg = *AC.getCFG();
83 1998: getAnalysisData().setCFG(cfg);
84 1998: getAnalysisData().setContext(AC.getASTContext());
85 1998: getAnalysisData().AC = &AC;
86 :
87 1998: RegisterDecls R(getAnalysisData());
88 1998: cfg.VisitBlockStmts(R);
89 1998: }
90 :
91 : //===----------------------------------------------------------------------===//
92 : // Transfer functions.
93 : //===----------------------------------------------------------------------===//
94 :
95 : namespace {
96 :
97 4248: class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
98 : LiveVariables::AnalysisDataTy& AD;
99 : LiveVariables::ValTy LiveState;
100 : public:
101 4248: TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
102 :
103 50038: LiveVariables::ValTy& getVal() { return LiveState; }
104 98702: CFG& getCFG() { return AD.getCFG(); }
105 :
106 : void VisitDeclRefExpr(DeclRefExpr* DR);
107 : void VisitBinaryOperator(BinaryOperator* B);
108 : void VisitBlockExpr(BlockExpr *B);
109 : void VisitAssign(BinaryOperator* B);
110 : void VisitDeclStmt(DeclStmt* DS);
111 : void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S);
112 : void VisitUnaryOperator(UnaryOperator* U);
113 : void Visit(Stmt *S);
114 : void VisitTerminator(CFGBlock* B);
115 :
116 : /// VisitConditionVariableInit - Handle the initialization of condition
117 : /// variables at branches. Valid statements include IfStmt, ForStmt,
118 : /// WhileStmt, and SwitchStmt.
119 : void VisitConditionVariableInit(Stmt *S);
120 :
121 14957: void SetTopValue(LiveVariables::ValTy& V) {
122 14957: V = AD.AlwaysLive;
123 14957: }
124 :
125 : };
126 :
127 93161: void TransferFuncs::Visit(Stmt *S) {
128 :
30619: branch 1 taken
62542: branch 2 taken
129 93161: if (S == getCurrentBlkStmt()) {
130 :
1648: branch 0 taken
28971: branch 1 taken
131 30619: if (AD.Observer)
132 1648: AD.Observer->ObserveStmt(S,AD,LiveState);
133 :
16526: branch 2 taken
14093: branch 3 taken
134 30619: if (getCFG().isBlkExpr(S))
135 16526: LiveState(S, AD) = Dead;
136 :
137 30619: StmtVisitor<TransferFuncs,void>::Visit(S);
138 : }
56099: branch 2 taken
6443: branch 3 taken
139 62542: else if (!getCFG().isBlkExpr(S)) {
140 :
1591: branch 0 taken
54508: branch 1 taken
141 56099: if (AD.Observer)
142 1591: AD.Observer->ObserveStmt(S,AD,LiveState);
143 :
144 56099: StmtVisitor<TransferFuncs,void>::Visit(S);
145 :
146 : }
147 : else {
148 : // For block-level expressions, mark that they are live.
149 6443: LiveState(S,AD) = Alive;
150 : }
151 93161: }
152 :
153 28: void TransferFuncs::VisitConditionVariableInit(Stmt *S) {
0: branch 2 not taken
28: branch 3 taken
154 28: assert(!getCFG().isBlkExpr(S));
155 28: CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S);
156 28: }
157 :
158 25188: void TransferFuncs::VisitTerminator(CFGBlock* B) {
159 :
160 25188: const Stmt* E = B->getTerminatorCondition();
161 :
19675: branch 0 taken
5513: branch 1 taken
162 25188: if (!E)
163 19675: return;
164 :
0: branch 2 not taken
5513: branch 3 taken
165 5513: assert (getCFG().isBlkExpr(E));
166 5513: LiveState(E, AD) = Alive;
167 : }
168 :
169 21155: void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
17451: branch 2 taken
3704: branch 3 taken
170 21155: if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
171 17451: LiveState(V, AD) = Alive;
172 21155: }
173 :
174 196: void TransferFuncs::VisitBlockExpr(BlockExpr *BE) {
175 : AnalysisContext::referenced_decls_iterator I, E;
176 196: llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl());
246: branch 0 taken
196: branch 1 taken
177 442: for ( ; I != E ; ++I) {
178 246: DeclBitVector_Types::Idx i = AD.getIdx(*I);
220: branch 1 taken
26: branch 2 taken
179 246: if (i.isValid())
180 220: LiveState.getBit(i) = Alive;
181 : }
182 196: }
183 :
184 7995: void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
3520: branch 1 taken
4475: branch 2 taken
185 7995: if (B->isAssignmentOp()) VisitAssign(B);
186 4475: else VisitStmt(B);
187 7995: }
188 :
189 : void
190 43: TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
191 :
192 : // This is a block-level expression. Its value is 'dead' before this point.
193 43: LiveState(S, AD) = Dead;
194 :
195 : // This represents a 'use' of the collection.
196 43: Visit(S->getCollection());
197 :
198 : // This represents a 'kill' for the variable.
199 43: Stmt* Element = S->getElement();
200 43: DeclRefExpr* DR = 0;
201 43: VarDecl* VD = 0;
202 :
11: branch 1 taken
32: branch 2 taken
203 43: if (DeclStmt* DS = dyn_cast<DeclStmt>(Element))
204 11: VD = cast<VarDecl>(DS->getSingleDecl());
205 : else {
206 32: Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens();
32: branch 1 taken
0: branch 2 not taken
207 32: if ((DR = dyn_cast<DeclRefExpr>(ElemExpr)))
208 32: VD = cast<VarDecl>(DR->getDecl());
209 : else {
210 0: Visit(ElemExpr);
211 0: return;
212 : }
213 : }
214 :
43: branch 0 taken
0: branch 1 not taken
215 43: if (VD) {
216 43: LiveState(VD, AD) = Dead;
2: branch 0 taken
41: branch 1 taken
0: branch 2 not taken
2: branch 3 taken
217 43: if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); }
218 : }
219 : }
220 :
221 :
222 6394: void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
223 6394: Expr *E = U->getSubExpr();
224 :
1903: branch 1 taken
4491: branch 2 taken
225 6394: switch (U->getOpcode()) {
226 : case UnaryOperator::PostInc:
227 : case UnaryOperator::PostDec:
228 : case UnaryOperator::PreInc:
229 : case UnaryOperator::PreDec:
230 : // Walk through the subexpressions, blasting through ParenExprs
231 : // until we either find a DeclRefExpr or some non-DeclRefExpr
232 : // expression.
1875: branch 2 taken
28: branch 3 taken
233 1903: if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens()))
1875: branch 2 taken
0: branch 3 not taken
234 1875: if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
235 : // Treat the --/++ operator as a kill.
150: branch 0 taken
1725: branch 1 taken
236 1875: if (AD.Observer) { AD.Observer->ObserverKill(DR); }
237 1875: LiveState(VD, AD) = Alive;
238 1875: return VisitDeclRefExpr(DR);
239 : }
240 :
241 : // Fall-through.
242 :
243 : default:
244 4519: return Visit(E);
245 : }
246 : }
247 :
248 3520: void TransferFuncs::VisitAssign(BinaryOperator* B) {
249 3520: Expr* LHS = B->getLHS();
250 :
251 : // Assigning to a variable?
2176: branch 2 taken
1344: branch 3 taken
252 3520: if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) {
253 :
254 : // Update liveness inforamtion.
255 2176: unsigned bit = AD.getIdx(DR->getDecl());
256 2176: LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
257 :
131: branch 0 taken
2045: branch 1 taken
258 2176: if (AD.Observer) { AD.Observer->ObserverKill(DR); }
259 :
260 : // Handle things like +=, etc., which also generate "uses"
261 : // of a variable. Do this just by visiting the subexpression.
252: branch 1 taken
1924: branch 2 taken
262 2176: if (B->getOpcode() != BinaryOperator::Assign)
263 252: VisitDeclRefExpr(DR);
264 : }
265 : else // Not assigning to a variable. Process LHS as usual.
266 1344: Visit(LHS);
267 :
268 3520: Visit(B->getRHS());
269 3520: }
270 :
271 8147: void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
272 : // Declarations effectively "kill" a variable since they cannot
273 : // possibly be live before they are declared.
8147: branch 2 taken
8147: branch 3 taken
274 16294: for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
275 : DI != DE; ++DI)
7796: branch 1 taken
351: branch 2 taken
276 8147: if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) {
277 : // The initializer is evaluated after the variable comes into scope.
278 : // Since this is a reverse dataflow analysis, we must evaluate the
279 : // transfer function for this expression first.
5997: branch 1 taken
1799: branch 2 taken
280 7796: if (Expr* Init = VD->getInit())
281 5997: Visit(Init);
282 :
67: branch 0 taken
7729: branch 1 taken
283 7796: if (const VariableArrayType* VT =
284 7796: AD.getContext().getAsVariableArrayType(VD->getType())) {
285 67: StmtIterator I(const_cast<VariableArrayType*>(VT));
286 67: StmtIterator E;
67: branch 4 taken
67: branch 5 taken
287 67: for (; I != E; ++I) Visit(*I);
288 : }
289 :
290 : // Update liveness information by killing the VarDecl.
291 7796: unsigned bit = AD.getIdx(VD);
292 7796: LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
293 : }
294 8147: }
295 :
296 : } // end anonymous namespace
297 :
298 : //===----------------------------------------------------------------------===//
299 : // Merge operator: if something is live on any successor block, it is live
300 : // in the current block (a set union).
301 : //===----------------------------------------------------------------------===//
302 :
303 : namespace {
304 : typedef StmtDeclBitVector_Types::Union Merge;
305 : typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver;
306 : } // end anonymous namespace
307 :
308 : //===----------------------------------------------------------------------===//
309 : // External interface to run Liveness analysis.
310 : //===----------------------------------------------------------------------===//
311 :
312 1998: void LiveVariables::runOnCFG(CFG& cfg) {
313 1998: Solver S(*this);
314 1998: S.runOnCFG(cfg);
315 1998: }
316 :
317 : void LiveVariables::runOnAllBlocks(const CFG& cfg,
318 : LiveVariables::ObserverTy* Obs,
319 2250: bool recordStmtValues) {
320 2250: Solver S(*this);
321 : SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer,
322 2250: Obs);
323 2250: S.runOnAllBlocks(cfg, recordStmtValues);
324 2250: }
325 :
326 : //===----------------------------------------------------------------------===//
327 : // liveness queries
328 : //
329 :
330 0: bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
331 0: DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
0: branch 1 not taken
0: branch 2 not taken
332 0: return i.isValid() ? getBlockData(B).getBit(i) : false;
333 : }
334 :
335 0: bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
336 0: DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
0: branch 1 not taken
0: branch 2 not taken
337 0: return i.isValid() ? Live.getBit(i) : false;
338 : }
339 :
340 7980: bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
341 7980: return getStmtData(Loc)(StmtVal,getAnalysisData());
342 : }
343 :
344 18783: bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
345 18783: return getStmtData(Loc)(D,getAnalysisData());
346 : }
347 :
348 : //===----------------------------------------------------------------------===//
349 : // printing liveness state for debugging
350 : //
351 :
352 0: void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const {
353 0: const AnalysisDataTy& AD = getAnalysisData();
354 :
0: branch 3 not taken
0: branch 4 not taken
355 0: for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
356 0: E = AD.end_decl(); I!=E; ++I)
0: branch 4 not taken
0: branch 5 not taken
357 0: if (V.getDeclBit(I->second)) {
358 0: llvm::errs() << " " << I->first->getIdentifier()->getName() << " <";
359 0: I->first->getLocation().dump(SM);
360 0: llvm::errs() << ">\n";
361 : }
362 0: }
363 :
364 0: void LiveVariables::dumpBlockLiveness(const SourceManager& M) const {
0: branch 4 not taken
0: branch 5 not taken
365 0: for (BlockDataMapTy::const_iterator I = getBlockDataMap().begin(),
366 0: E = getBlockDataMap().end(); I!=E; ++I) {
367 : llvm::errs() << "\n[ B" << I->first->getBlockID()
368 0: << " (live variables at block exit) ]\n";
369 0: dumpLiveness(I->second,M);
370 : }
371 :
372 0: llvm::errs() << "\n";
373 0: }
Generated: 2010-02-10 01:31 by zcov