blob: 98b1ee282096af11cec260fce251541cf25acae2 [file] [log] [blame]
Ted Kremenek11de5cb2007-09-20 21:42:55 +00001//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==//
Ted Kremeneke4e63342007-09-06 00:17:54 +00002//
3// The LLVM Compiler Infrastructure
4//
Chris Lattner0bc735f2007-12-29 19:59:25 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Ted Kremeneke4e63342007-09-06 00:17:54 +00007//
8//===----------------------------------------------------------------------===//
9//
10// This file implements Live Variables analysis for source-level CFGs.
11//
12//===----------------------------------------------------------------------===//
13
Ted Kremenekcf6e41b2007-12-21 21:42:19 +000014#include "clang/Analysis/Analyses/LiveVariables.h"
Ted Kremenek27b07c52007-09-06 21:26:58 +000015#include "clang/Basic/SourceManager.h"
Ted Kremeneke4e63342007-09-06 00:17:54 +000016#include "clang/AST/Expr.h"
17#include "clang/AST/CFG.h"
Ted Kremenekfdd225e2007-09-25 04:31:27 +000018#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
Ted Kremenek1de632b2007-09-25 21:00:24 +000019#include "clang/Analysis/FlowSensitive/DataflowSolver.h"
Ted Kremeneke4e63342007-09-06 00:17:54 +000020#include "llvm/ADT/SmallPtrSet.h"
Ted Kremenek7deed0c2008-04-15 18:35:30 +000021#include "llvm/ADT/SmallVector.h"
Ted Kremenekc2b51d82008-01-08 18:19:08 +000022#include "llvm/Support/Compiler.h"
Ted Kremeneke4e63342007-09-06 00:17:54 +000023
Ted Kremenek27b07c52007-09-06 21:26:58 +000024#include <string.h>
25#include <stdio.h>
Ted Kremeneke4e63342007-09-06 00:17:54 +000026
27using namespace clang;
28
29//===----------------------------------------------------------------------===//
Ted Kremenek7deed0c2008-04-15 18:35:30 +000030// Useful constants.
31//===----------------------------------------------------------------------===//
32
33static const bool Alive = true;
34static const bool Dead = false;
35
36//===----------------------------------------------------------------------===//
Ted Kremenekfdd225e2007-09-25 04:31:27 +000037// Dataflow initialization logic.
38//===----------------------------------------------------------------------===//
Ted Kremeneke4e63342007-09-06 00:17:54 +000039
40namespace {
Ted Kremenekc2b51d82008-01-08 18:19:08 +000041class VISIBILITY_HIDDEN RegisterDecls
42 : public CFGRecStmtDeclVisitor<RegisterDecls> {
43
Ted Kremenekfdd225e2007-09-25 04:31:27 +000044 LiveVariables::AnalysisDataTy& AD;
Ted Kremenek7deed0c2008-04-15 18:35:30 +000045
46 typedef llvm::SmallVector<VarDecl*, 20> AlwaysLiveTy;
47 AlwaysLiveTy AlwaysLive;
48
49
Ted Kremenekf63aa452007-09-28 20:38:59 +000050public:
Ted Kremenek7deed0c2008-04-15 18:35:30 +000051 RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
52
53 ~RegisterDecls() {
54
55 AD.AlwaysLive.resetValues(AD);
56
57 for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end();
58 I != E; ++ I)
59 AD.AlwaysLive(*I, AD) = Alive;
60 }
61
Chris Lattner41110242008-06-17 18:05:57 +000062 void VisitImplicitParamDecl(ImplicitParamDecl* IPD) {
63 // Register the VarDecl for tracking.
64 AD.Register(IPD);
65 }
66
Ted Kremenek7deed0c2008-04-15 18:35:30 +000067 void VisitVarDecl(VarDecl* VD) {
68 // Register the VarDecl for tracking.
69 AD.Register(VD);
70
71 // Does the variable have global storage? If so, it is always live.
72 if (VD->hasGlobalStorage())
73 AlwaysLive.push_back(VD);
74 }
75
76 void VisitUnaryOperator(UnaryOperator* U) {
77 // Check for '&'. Any VarDecl whose value has its address-taken we
78 // treat as always being live (flow-insensitive).
79
80 Expr* E = U->getSubExpr()->IgnoreParenCasts();
81
82 if (U->getOpcode() == UnaryOperator::AddrOf)
83 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E))
84 if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
85 AD.Register(VD);
86 AlwaysLive.push_back(VD);
87 return;
88 }
89
90 Visit(E);
91 }
92
Ted Kremenek9f9141c2007-11-20 03:01:58 +000093 CFG& getCFG() { return AD.getCFG(); }
Ted Kremenek11e72182007-10-01 20:33:52 +000094};
Ted Kremeneke4e63342007-09-06 00:17:54 +000095} // end anonymous namespace
96
Ted Kremenekbffaa832008-01-29 05:13:23 +000097
Ted Kremenek7cb15932008-03-13 16:55:07 +000098LiveVariables::LiveVariables(CFG& cfg) {
99 // Register all referenced VarDecls.
Ted Kremenekbffaa832008-01-29 05:13:23 +0000100 getAnalysisData().setCFG(&cfg);
Ted Kremenek11e72182007-10-01 20:33:52 +0000101 RegisterDecls R(getAnalysisData());
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000102 cfg.VisitBlockStmts(R);
103}
Ted Kremeneke4e63342007-09-06 00:17:54 +0000104
105//===----------------------------------------------------------------------===//
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000106// Transfer functions.
107//===----------------------------------------------------------------------===//
Ted Kremeneke4e63342007-09-06 00:17:54 +0000108
109namespace {
Ted Kremenekf63aa452007-09-28 20:38:59 +0000110
Ted Kremenekc2b51d82008-01-08 18:19:08 +0000111class VISIBILITY_HIDDEN TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000112 LiveVariables::AnalysisDataTy& AD;
Ted Kremenekf63aa452007-09-28 20:38:59 +0000113 LiveVariables::ValTy LiveState;
Ted Kremeneke4e63342007-09-06 00:17:54 +0000114public:
Ted Kremenek11e72182007-10-01 20:33:52 +0000115 TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000116
Ted Kremenekf63aa452007-09-28 20:38:59 +0000117 LiveVariables::ValTy& getVal() { return LiveState; }
Ted Kremenek9f9141c2007-11-20 03:01:58 +0000118 CFG& getCFG() { return AD.getCFG(); }
Ted Kremenekf1758052007-09-12 19:10:52 +0000119
Ted Kremeneke4e63342007-09-06 00:17:54 +0000120 void VisitDeclRefExpr(DeclRefExpr* DR);
121 void VisitBinaryOperator(BinaryOperator* B);
122 void VisitAssign(BinaryOperator* B);
Ted Kremenek27b07c52007-09-06 21:26:58 +0000123 void VisitDeclStmt(DeclStmt* DS);
Ted Kremenekbfcb7122008-11-12 21:58:46 +0000124 void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S);
Ted Kremenek27b07c52007-09-06 21:26:58 +0000125 void VisitUnaryOperator(UnaryOperator* U);
Ted Kremenek8f5aab62008-11-11 17:42:10 +0000126 void Visit(Stmt *S);
Ted Kremenek411cdee2008-04-16 21:10:48 +0000127 void VisitTerminator(CFGBlock* B);
Ted Kremenek7deed0c2008-04-15 18:35:30 +0000128
129 void SetTopValue(LiveVariables::ValTy& V) {
130 V = AD.AlwaysLive;
131 }
132
Ted Kremeneke4e63342007-09-06 00:17:54 +0000133};
Ted Kremenek11e72182007-10-01 20:33:52 +0000134
Ted Kremenek11e72182007-10-01 20:33:52 +0000135void TransferFuncs::Visit(Stmt *S) {
Ted Kremenekf63aa452007-09-28 20:38:59 +0000136
Ted Kremenek86946742008-01-17 20:48:37 +0000137 if (S == getCurrentBlkStmt()) {
Ted Kremenek03648652008-07-03 22:25:27 +0000138
139 if (AD.Observer)
140 AD.Observer->ObserveStmt(S,AD,LiveState);
141
Ted Kremenek1aa9a582008-03-05 19:26:46 +0000142 if (getCFG().isBlkExpr(S)) LiveState(S,AD) = Dead;
Ted Kremenek2a9da9c2008-01-18 00:40:21 +0000143 StmtVisitor<TransferFuncs,void>::Visit(S);
Ted Kremenek86946742008-01-17 20:48:37 +0000144 }
Ted Kremenek03648652008-07-03 22:25:27 +0000145 else if (!getCFG().isBlkExpr(S)) {
146
147 if (AD.Observer)
148 AD.Observer->ObserveStmt(S,AD,LiveState);
149
Ted Kremenek86946742008-01-17 20:48:37 +0000150 StmtVisitor<TransferFuncs,void>::Visit(S);
Ted Kremenek03648652008-07-03 22:25:27 +0000151
152 }
Ted Kremenek86946742008-01-17 20:48:37 +0000153 else
154 // For block-level expressions, mark that they are live.
155 LiveState(S,AD) = Alive;
Ted Kremenek11e72182007-10-01 20:33:52 +0000156}
Ted Kremenek37622082008-04-15 04:39:08 +0000157
Ted Kremenek411cdee2008-04-16 21:10:48 +0000158void TransferFuncs::VisitTerminator(CFGBlock* B) {
159
Ted Kremenek8ded8d82008-11-12 21:12:18 +0000160 const Stmt* E = B->getTerminatorCondition();
Ted Kremenek411cdee2008-04-16 21:10:48 +0000161
Ted Kremenek5cd24382008-04-16 17:07:59 +0000162 if (!E)
163 return;
164
Ted Kremenek5cd24382008-04-16 17:07:59 +0000165 assert (getCFG().isBlkExpr(E));
166 LiveState(E, AD) = Alive;
Ted Kremenek37622082008-04-15 04:39:08 +0000167}
168
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000169void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
170 if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
Ted Kremenekf63aa452007-09-28 20:38:59 +0000171 LiveState(V,AD) = Alive;
Ted Kremeneke4e63342007-09-06 00:17:54 +0000172}
Ted Kremeneke4e63342007-09-06 00:17:54 +0000173
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000174void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
Ted Kremenekf1758052007-09-12 19:10:52 +0000175 if (B->isAssignmentOp()) VisitAssign(B);
176 else VisitStmt(B);
Ted Kremeneke4e63342007-09-06 00:17:54 +0000177}
178
Ted Kremenekbfcb7122008-11-12 21:58:46 +0000179void
180TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
181
Ted Kremeneke97d9db2008-11-11 19:40:47 +0000182 // This represents a 'use' of the collection.
183 Visit(S->getCollection());
Ted Kremenek8f5aab62008-11-11 17:42:10 +0000184
185 // This represents a 'kill' for the variable.
Ted Kremeneke97d9db2008-11-11 19:40:47 +0000186 Stmt* Element = S->getElement();
Ted Kremenekf8cce1d2008-11-13 05:26:15 +0000187 DeclRefExpr *DR = 0;
Ted Kremeneke97d9db2008-11-11 19:40:47 +0000188 VarDecl* VD = 0;
189
190 if (DeclStmt* DS = dyn_cast<DeclStmt>(Element))
191 VD = cast<VarDecl>(DS->getSolitaryDecl());
192 else {
193 DR = cast<DeclRefExpr>(Element);
194 VD = cast<VarDecl>(DR->getDecl());
195 }
196
197 LiveState(VD, AD) = Dead;
198 if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); }
Ted Kremenek8f5aab62008-11-11 17:42:10 +0000199}
200
201
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000202void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
Ted Kremenek5e2b6092008-01-17 17:50:49 +0000203 Expr *E = U->getSubExpr();
Ted Kremenekbcb07d52007-09-28 21:29:33 +0000204
Ted Kremenek27b07c52007-09-06 21:26:58 +0000205 switch (U->getOpcode()) {
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000206 case UnaryOperator::PostInc:
207 case UnaryOperator::PostDec:
208 case UnaryOperator::PreInc:
209 case UnaryOperator::PreDec:
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000210 // Walk through the subexpressions, blasting through ParenExprs
211 // until we either find a DeclRefExpr or some non-DeclRefExpr
212 // expression.
Ted Kremenek56206312008-02-22 00:34:10 +0000213 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens()))
Ted Kremenekdace4c92008-04-15 04:08:54 +0000214 if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
215 // Treat the --/++ operator as a kill.
Ted Kremenek56206312008-02-22 00:34:10 +0000216 if (AD.Observer) { AD.Observer->ObserverKill(DR); }
Ted Kremenekdace4c92008-04-15 04:08:54 +0000217 LiveState(VD, AD) = Alive;
Ted Kremenek56206312008-02-22 00:34:10 +0000218 return VisitDeclRefExpr(DR);
219 }
Ted Kremenekbcb07d52007-09-28 21:29:33 +0000220
221 // Fall-through.
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000222
223 default:
Ted Kremenek5e2b6092008-01-17 17:50:49 +0000224 return Visit(E);
Ted Kremenek27b07c52007-09-06 21:26:58 +0000225 }
226}
Ted Kremenekbcb07d52007-09-28 21:29:33 +0000227
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000228void TransferFuncs::VisitAssign(BinaryOperator* B) {
Ted Kremenek5e2b6092008-01-17 17:50:49 +0000229 Expr* LHS = B->getLHS();
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000230
Ted Kremenekbcb07d52007-09-28 21:29:33 +0000231 // Assigning to a variable?
Ted Kremenek5e2b6092008-01-17 17:50:49 +0000232 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) {
Ted Kremenek7deed0c2008-04-15 18:35:30 +0000233
234 // Update liveness inforamtion.
235 unsigned bit = AD.getIdx(DR->getDecl());
236 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
237
Ted Kremenekf63aa452007-09-28 20:38:59 +0000238 if (AD.Observer) { AD.Observer->ObserverKill(DR); }
239
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000240 // Handle things like +=, etc., which also generate "uses"
241 // of a variable. Do this just by visiting the subexpression.
Ted Kremenekbcb07d52007-09-28 21:29:33 +0000242 if (B->getOpcode() != BinaryOperator::Assign)
243 VisitDeclRefExpr(DR);
Ted Kremeneke4e63342007-09-06 00:17:54 +0000244 }
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000245 else // Not assigning to a variable. Process LHS as usual.
Ted Kremenek27b07c52007-09-06 21:26:58 +0000246 Visit(LHS);
Ted Kremeneke4e63342007-09-06 00:17:54 +0000247
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000248 Visit(B->getRHS());
Ted Kremeneke4e63342007-09-06 00:17:54 +0000249}
250
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000251void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
252 // Declarations effectively "kill" a variable since they cannot
253 // possibly be live before they are declared.
Ted Kremenek14f8b4f2008-08-05 20:46:55 +0000254 for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
255 DI != DE; ++DI)
256 if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) {
Ted Kremenek84fa6b92008-09-26 05:52:45 +0000257 // The initializer is evaluated after the variable comes into scope.
258 // Since this is a reverse dataflow analysis, we must evaluate the
259 // transfer function for this expression first.
Ted Kremenek2bca5e42008-02-07 02:38:55 +0000260 if (Expr* Init = VD->getInit())
261 Visit(Init);
Ted Kremenek84fa6b92008-09-26 05:52:45 +0000262
263 // Update liveness information by killing the VarDecl.
264 unsigned bit = AD.getIdx(VD);
265 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
Ted Kremenekdcc48102008-02-25 22:28:54 +0000266 }
Ted Kremenek27b07c52007-09-06 21:26:58 +0000267}
Ted Kremenekf63aa452007-09-28 20:38:59 +0000268
Ted Kremeneke4e63342007-09-06 00:17:54 +0000269} // end anonymous namespace
270
Ted Kremenekf63aa452007-09-28 20:38:59 +0000271//===----------------------------------------------------------------------===//
272// Merge operator: if something is live on any successor block, it is live
273// in the current block (a set union).
274//===----------------------------------------------------------------------===//
Ted Kremeneke4e63342007-09-06 00:17:54 +0000275
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000276namespace {
Ted Kremenekfa59f1f2008-03-20 21:46:49 +0000277
278struct Merge {
Ted Kremenek8d798c72008-11-14 01:14:18 +0000279 typedef StmtDeclBitVector_Types::ValTy ValTy;
Ted Kremenekfa59f1f2008-03-20 21:46:49 +0000280
281 void operator()(ValTy& Dst, const ValTy& Src) {
282 Dst.OrDeclBits(Src);
Ted Kremenek8d798c72008-11-14 01:14:18 +0000283 Dst.AndBlkExprBits(Src);
Ted Kremenekfa59f1f2008-03-20 21:46:49 +0000284 }
285};
286
287typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver;
Ted Kremenekf63aa452007-09-28 20:38:59 +0000288} // end anonymous namespace
289
290//===----------------------------------------------------------------------===//
291// External interface to run Liveness analysis.
292//===----------------------------------------------------------------------===//
Ted Kremeneke4e63342007-09-06 00:17:54 +0000293
Ted Kremenek83c01da2008-01-11 00:40:29 +0000294void LiveVariables::runOnCFG(CFG& cfg) {
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000295 Solver S(*this);
296 S.runOnCFG(cfg);
297}
Ted Kremenek27b07c52007-09-06 21:26:58 +0000298
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000299void LiveVariables::runOnAllBlocks(const CFG& cfg,
Ted Kremenek79649df2008-01-17 18:25:22 +0000300 LiveVariables::ObserverTy* Obs,
301 bool recordStmtValues) {
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000302 Solver S(*this);
303 ObserverTy* OldObserver = getAnalysisData().Observer;
Ted Kremenek79649df2008-01-17 18:25:22 +0000304 getAnalysisData().Observer = Obs;
305 S.runOnAllBlocks(cfg, recordStmtValues);
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000306 getAnalysisData().Observer = OldObserver;
Ted Kremenek27b07c52007-09-06 21:26:58 +0000307}
308
309//===----------------------------------------------------------------------===//
310// liveness queries
311//
312
Ted Kremenekc0576ca2007-09-10 17:36:42 +0000313bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
Ted Kremenek7cb15932008-03-13 16:55:07 +0000314 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
315 return i.isValid() ? getBlockData(B).getBit(i) : false;
Ted Kremenek27b07c52007-09-06 21:26:58 +0000316}
317
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000318bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
Ted Kremenek7cb15932008-03-13 16:55:07 +0000319 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
320 return i.isValid() ? Live.getBit(i) : false;
Ted Kremenek055c2752007-09-06 23:00:42 +0000321}
322
Ted Kremenek86946742008-01-17 20:48:37 +0000323bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
324 return getStmtData(Loc)(StmtVal,getAnalysisData());
325}
326
Ted Kremenek2a9da9c2008-01-18 00:40:21 +0000327bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
328 return getStmtData(Loc)(D,getAnalysisData());
329}
330
Ted Kremenek055c2752007-09-06 23:00:42 +0000331//===----------------------------------------------------------------------===//
Ted Kremeneke4e63342007-09-06 00:17:54 +0000332// printing liveness state for debugging
333//
334
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000335void LiveVariables::dumpLiveness(const ValTy& V, SourceManager& SM) const {
336 const AnalysisDataTy& AD = getAnalysisData();
337
Ted Kremenekf63aa452007-09-28 20:38:59 +0000338 for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
339 E = AD.end_decl(); I!=E; ++I)
340 if (V.getDeclBit(I->second)) {
Ted Kremenek27b07c52007-09-06 21:26:58 +0000341 SourceLocation PhysLoc = SM.getPhysicalLoc(I->first->getLocation());
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000342
Ted Kremenek27b07c52007-09-06 21:26:58 +0000343 fprintf(stderr, " %s <%s:%u:%u>\n",
344 I->first->getIdentifier()->getName(),
345 SM.getSourceName(PhysLoc),
346 SM.getLineNumber(PhysLoc),
347 SM.getColumnNumber(PhysLoc));
Ted Kremeneke4e63342007-09-06 00:17:54 +0000348 }
Ted Kremeneke4e63342007-09-06 00:17:54 +0000349}
350
Ted Kremenek27b07c52007-09-06 21:26:58 +0000351void LiveVariables::dumpBlockLiveness(SourceManager& M) const {
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000352 for (BlockDataMapTy::iterator I = getBlockDataMap().begin(),
353 E = getBlockDataMap().end(); I!=E; ++I) {
354 fprintf(stderr, "\n[ B%d (live variables at block exit) ]\n",
Ted Kremenek27b07c52007-09-06 21:26:58 +0000355 I->first->getBlockID());
356
357 dumpLiveness(I->second,M);
358 }
Ted Kremenekc0576ca2007-09-10 17:36:42 +0000359
360 fprintf(stderr,"\n");
361}