blob: 84e268f3fdaa3fb7acf97e874ad25a79c4972289 [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 Kremeneke0dbda12008-12-09 00:14:14 +000016#include "clang/AST/ASTContext.h"
Ted Kremeneke4e63342007-09-06 00:17:54 +000017#include "clang/AST/Expr.h"
Ted Kremeneke41611a2009-07-16 18:13:04 +000018#include "clang/Analysis/CFG.h"
Ted Kremenekfdd225e2007-09-25 04:31:27 +000019#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
Ted Kremenek1de632b2007-09-25 21:00:24 +000020#include "clang/Analysis/FlowSensitive/DataflowSolver.h"
Ted Kremenek31d8cad2009-11-07 05:57:35 +000021#include "clang/Analysis/Support/SaveAndRestore.h"
Ted Kremenekb1a7b652009-11-26 02:31:33 +000022#include "clang/Analysis/PathSensitive/AnalysisContext.h"
Ted Kremeneke4e63342007-09-06 00:17:54 +000023#include "llvm/ADT/SmallPtrSet.h"
Ted Kremenek7deed0c2008-04-15 18:35:30 +000024#include "llvm/ADT/SmallVector.h"
Daniel Dunbarc0d56722009-10-17 18:12:37 +000025#include "llvm/Support/raw_ostream.h"
Ted Kremeneke4e63342007-09-06 00:17:54 +000026
27using namespace clang;
28
29//===----------------------------------------------------------------------===//
Ted Kremenek7deed0c2008-04-15 18:35:30 +000030// Useful constants.
Mike Stump1eb44332009-09-09 15:08:12 +000031//===----------------------------------------------------------------------===//
Ted Kremenek7deed0c2008-04-15 18:35:30 +000032
33static const bool Alive = true;
Mike Stump1eb44332009-09-09 15:08:12 +000034static const bool Dead = false;
Ted Kremenek7deed0c2008-04-15 18:35:30 +000035
36//===----------------------------------------------------------------------===//
Ted Kremenekfdd225e2007-09-25 04:31:27 +000037// Dataflow initialization logic.
Mike Stump1eb44332009-09-09 15:08:12 +000038//===----------------------------------------------------------------------===//
Ted Kremeneke4e63342007-09-06 00:17:54 +000039
40namespace {
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000041class RegisterDecls
Ted Kremenekc2b51d82008-01-08 18:19:08 +000042 : public CFGRecStmtDeclVisitor<RegisterDecls> {
Mike Stump1eb44332009-09-09 15:08:12 +000043
Ted Kremenekfdd225e2007-09-25 04:31:27 +000044 LiveVariables::AnalysisDataTy& AD;
Mike Stump1eb44332009-09-09 15:08:12 +000045
Ted Kremenek7deed0c2008-04-15 18:35:30 +000046 typedef llvm::SmallVector<VarDecl*, 20> AlwaysLiveTy;
47 AlwaysLiveTy AlwaysLive;
48
Mike Stump1eb44332009-09-09 15:08:12 +000049
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);
Mike Stump1eb44332009-09-09 15:08:12 +000056
Ted Kremenek7deed0c2008-04-15 18:35:30 +000057 for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end();
Mike Stump1eb44332009-09-09 15:08:12 +000058 I != E; ++ I)
59 AD.AlwaysLive(*I, AD) = Alive;
Ted Kremenek7deed0c2008-04-15 18:35:30 +000060 }
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);
Mike Stump1eb44332009-09-09 15:08:12 +000070
Ted Kremenek7deed0c2008-04-15 18:35:30 +000071 // Does the variable have global storage? If so, it is always live.
72 if (VD->hasGlobalStorage())
Mike Stump1eb44332009-09-09 15:08:12 +000073 AlwaysLive.push_back(VD);
Ted Kremenek7deed0c2008-04-15 18:35:30 +000074 }
Mike Stump1eb44332009-09-09 15:08:12 +000075
Ted Kremenek9f9141c2007-11-20 03:01:58 +000076 CFG& getCFG() { return AD.getCFG(); }
Ted Kremenek11e72182007-10-01 20:33:52 +000077};
Ted Kremeneke4e63342007-09-06 00:17:54 +000078} // end anonymous namespace
79
Ted Kremenekb1a7b652009-11-26 02:31:33 +000080LiveVariables::LiveVariables(AnalysisContext &AC) {
Ted Kremenek7cb15932008-03-13 16:55:07 +000081 // Register all referenced VarDecls.
Ted Kremenekb1a7b652009-11-26 02:31:33 +000082 CFG &cfg = *AC.getCFG();
Ted Kremeneke0dbda12008-12-09 00:14:14 +000083 getAnalysisData().setCFG(cfg);
Ted Kremenekb1a7b652009-11-26 02:31:33 +000084 getAnalysisData().setContext(AC.getASTContext());
85 getAnalysisData().AC = &AC;
Mike Stump1eb44332009-09-09 15:08:12 +000086
Ted Kremenek11e72182007-10-01 20:33:52 +000087 RegisterDecls R(getAnalysisData());
Ted Kremenekfdd225e2007-09-25 04:31:27 +000088 cfg.VisitBlockStmts(R);
89}
Ted Kremeneke4e63342007-09-06 00:17:54 +000090
91//===----------------------------------------------------------------------===//
Ted Kremenekfdd225e2007-09-25 04:31:27 +000092// Transfer functions.
Mike Stump1eb44332009-09-09 15:08:12 +000093//===----------------------------------------------------------------------===//
Ted Kremeneke4e63342007-09-06 00:17:54 +000094
95namespace {
Ted Kremenekf63aa452007-09-28 20:38:59 +000096
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +000097class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
Ted Kremenekfdd225e2007-09-25 04:31:27 +000098 LiveVariables::AnalysisDataTy& AD;
Ted Kremenekf63aa452007-09-28 20:38:59 +000099 LiveVariables::ValTy LiveState;
Ted Kremeneke4e63342007-09-06 00:17:54 +0000100public:
Ted Kremenek11e72182007-10-01 20:33:52 +0000101 TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000102
Ted Kremenekf63aa452007-09-28 20:38:59 +0000103 LiveVariables::ValTy& getVal() { return LiveState; }
Ted Kremenek9f9141c2007-11-20 03:01:58 +0000104 CFG& getCFG() { return AD.getCFG(); }
Mike Stump1eb44332009-09-09 15:08:12 +0000105
Ted Kremeneke4e63342007-09-06 00:17:54 +0000106 void VisitDeclRefExpr(DeclRefExpr* DR);
107 void VisitBinaryOperator(BinaryOperator* B);
Ted Kremenekb1a7b652009-11-26 02:31:33 +0000108 void VisitBlockExpr(BlockExpr *B);
Ted Kremeneke4e63342007-09-06 00:17:54 +0000109 void VisitAssign(BinaryOperator* B);
Ted Kremenek27b07c52007-09-06 21:26:58 +0000110 void VisitDeclStmt(DeclStmt* DS);
Ted Kremenekbfcb7122008-11-12 21:58:46 +0000111 void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S);
Ted Kremenek27b07c52007-09-06 21:26:58 +0000112 void VisitUnaryOperator(UnaryOperator* U);
Mike Stump1eb44332009-09-09 15:08:12 +0000113 void Visit(Stmt *S);
114 void VisitTerminator(CFGBlock* B);
115
Ted Kremenek7deed0c2008-04-15 18:35:30 +0000116 void SetTopValue(LiveVariables::ValTy& V) {
Ted Kremenekbf98c992009-01-30 21:35:30 +0000117 V = AD.AlwaysLive;
Ted Kremenek7deed0c2008-04-15 18:35:30 +0000118 }
Mike Stump1eb44332009-09-09 15:08:12 +0000119
Ted Kremeneke4e63342007-09-06 00:17:54 +0000120};
Mike Stump1eb44332009-09-09 15:08:12 +0000121
Ted Kremenek11e72182007-10-01 20:33:52 +0000122void TransferFuncs::Visit(Stmt *S) {
Mike Stump1eb44332009-09-09 15:08:12 +0000123
Ted Kremenek86946742008-01-17 20:48:37 +0000124 if (S == getCurrentBlkStmt()) {
Mike Stump1eb44332009-09-09 15:08:12 +0000125
Ted Kremenek03648652008-07-03 22:25:27 +0000126 if (AD.Observer)
127 AD.Observer->ObserveStmt(S,AD,LiveState);
Mike Stump1eb44332009-09-09 15:08:12 +0000128
Ted Kremenek1aa9a582008-03-05 19:26:46 +0000129 if (getCFG().isBlkExpr(S)) LiveState(S,AD) = Dead;
Ted Kremenek2a9da9c2008-01-18 00:40:21 +0000130 StmtVisitor<TransferFuncs,void>::Visit(S);
Ted Kremenek86946742008-01-17 20:48:37 +0000131 }
Ted Kremenek03648652008-07-03 22:25:27 +0000132 else if (!getCFG().isBlkExpr(S)) {
Mike Stump1eb44332009-09-09 15:08:12 +0000133
Ted Kremenek03648652008-07-03 22:25:27 +0000134 if (AD.Observer)
135 AD.Observer->ObserveStmt(S,AD,LiveState);
Mike Stump1eb44332009-09-09 15:08:12 +0000136
Ted Kremenek86946742008-01-17 20:48:37 +0000137 StmtVisitor<TransferFuncs,void>::Visit(S);
Mike Stump1eb44332009-09-09 15:08:12 +0000138
Ted Kremenek03648652008-07-03 22:25:27 +0000139 }
Zhongxing Xu1b542212009-06-30 12:11:58 +0000140 else {
Ted Kremenek86946742008-01-17 20:48:37 +0000141 // For block-level expressions, mark that they are live.
142 LiveState(S,AD) = Alive;
Zhongxing Xu1b542212009-06-30 12:11:58 +0000143 }
Ted Kremenek11e72182007-10-01 20:33:52 +0000144}
Mike Stump1eb44332009-09-09 15:08:12 +0000145
Ted Kremenek411cdee2008-04-16 21:10:48 +0000146void TransferFuncs::VisitTerminator(CFGBlock* B) {
Mike Stump1eb44332009-09-09 15:08:12 +0000147
Ted Kremenek8ded8d82008-11-12 21:12:18 +0000148 const Stmt* E = B->getTerminatorCondition();
Ted Kremenek411cdee2008-04-16 21:10:48 +0000149
Ted Kremenek5cd24382008-04-16 17:07:59 +0000150 if (!E)
151 return;
Mike Stump1eb44332009-09-09 15:08:12 +0000152
Ted Kremenek5cd24382008-04-16 17:07:59 +0000153 assert (getCFG().isBlkExpr(E));
154 LiveState(E, AD) = Alive;
Ted Kremenek37622082008-04-15 04:39:08 +0000155}
156
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000157void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
Mike Stump1eb44332009-09-09 15:08:12 +0000158 if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
Ted Kremenekb1a7b652009-11-26 02:31:33 +0000159 LiveState(V, AD) = Alive;
160}
161
162void TransferFuncs::VisitBlockExpr(BlockExpr *BE) {
163 AnalysisContext::referenced_decls_iterator I, E;
164 llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl());
165 for ( ; I != E ; ++I) {
166 DeclBitVector_Types::Idx i = AD.getIdx(*I);
167 if (i.isValid())
168 LiveState.getBit(i) = Alive;
169 }
Ted Kremeneke4e63342007-09-06 00:17:54 +0000170}
Mike Stump1eb44332009-09-09 15:08:12 +0000171
172void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
Ted Kremenekf1758052007-09-12 19:10:52 +0000173 if (B->isAssignmentOp()) VisitAssign(B);
174 else VisitStmt(B);
Ted Kremeneke4e63342007-09-06 00:17:54 +0000175}
176
Ted Kremenekbfcb7122008-11-12 21:58:46 +0000177void
178TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
Mike Stump1eb44332009-09-09 15:08:12 +0000179
Ted Kremenek06529ae2008-11-14 21:07:14 +0000180 // This is a block-level expression. Its value is 'dead' before this point.
181 LiveState(S, AD) = Dead;
182
Ted Kremeneke97d9db2008-11-11 19:40:47 +0000183 // This represents a 'use' of the collection.
184 Visit(S->getCollection());
Mike Stump1eb44332009-09-09 15:08:12 +0000185
Ted Kremenek8f5aab62008-11-11 17:42:10 +0000186 // This represents a 'kill' for the variable.
Ted Kremeneke97d9db2008-11-11 19:40:47 +0000187 Stmt* Element = S->getElement();
Ted Kremenek8f646002008-11-14 01:58:12 +0000188 DeclRefExpr* DR = 0;
Ted Kremeneke97d9db2008-11-11 19:40:47 +0000189 VarDecl* VD = 0;
Mike Stump1eb44332009-09-09 15:08:12 +0000190
Ted Kremeneke97d9db2008-11-11 19:40:47 +0000191 if (DeclStmt* DS = dyn_cast<DeclStmt>(Element))
Chris Lattner7e24e822009-03-28 06:33:19 +0000192 VD = cast<VarDecl>(DS->getSingleDecl());
Ted Kremeneke97d9db2008-11-11 19:40:47 +0000193 else {
Mike Stump1eb44332009-09-09 15:08:12 +0000194 Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens();
Ted Kremenek8f646002008-11-14 01:58:12 +0000195 if ((DR = dyn_cast<DeclRefExpr>(ElemExpr)))
196 VD = cast<VarDecl>(DR->getDecl());
Ted Kremenek06529ae2008-11-14 21:07:14 +0000197 else {
198 Visit(ElemExpr);
199 return;
200 }
Ted Kremeneke97d9db2008-11-11 19:40:47 +0000201 }
202
Ted Kremenek8f646002008-11-14 01:58:12 +0000203 if (VD) {
204 LiveState(VD, AD) = Dead;
205 if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); }
206 }
Ted Kremenek8f5aab62008-11-11 17:42:10 +0000207}
208
Mike Stump1eb44332009-09-09 15:08:12 +0000209
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000210void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
Ted Kremenek5e2b6092008-01-17 17:50:49 +0000211 Expr *E = U->getSubExpr();
Mike Stump1eb44332009-09-09 15:08:12 +0000212
Ted Kremenek27b07c52007-09-06 21:26:58 +0000213 switch (U->getOpcode()) {
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000214 case UnaryOperator::PostInc:
215 case UnaryOperator::PostDec:
216 case UnaryOperator::PreInc:
217 case UnaryOperator::PreDec:
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000218 // Walk through the subexpressions, blasting through ParenExprs
219 // until we either find a DeclRefExpr or some non-DeclRefExpr
220 // expression.
Mike Stump1eb44332009-09-09 15:08:12 +0000221 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens()))
Ted Kremenekdace4c92008-04-15 04:08:54 +0000222 if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
223 // Treat the --/++ operator as a kill.
Ted Kremenek56206312008-02-22 00:34:10 +0000224 if (AD.Observer) { AD.Observer->ObserverKill(DR); }
Ted Kremenekdace4c92008-04-15 04:08:54 +0000225 LiveState(VD, AD) = Alive;
Ted Kremenek56206312008-02-22 00:34:10 +0000226 return VisitDeclRefExpr(DR);
227 }
Ted Kremenekbcb07d52007-09-28 21:29:33 +0000228
229 // Fall-through.
Mike Stump1eb44332009-09-09 15:08:12 +0000230
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000231 default:
Ted Kremenek5e2b6092008-01-17 17:50:49 +0000232 return Visit(E);
Ted Kremenek27b07c52007-09-06 21:26:58 +0000233 }
234}
Mike Stump1eb44332009-09-09 15:08:12 +0000235
236void TransferFuncs::VisitAssign(BinaryOperator* B) {
Ted Kremenek5e2b6092008-01-17 17:50:49 +0000237 Expr* LHS = B->getLHS();
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000238
Ted Kremenekbcb07d52007-09-28 21:29:33 +0000239 // Assigning to a variable?
Ted Kremenek5e2b6092008-01-17 17:50:49 +0000240 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) {
Mike Stump1eb44332009-09-09 15:08:12 +0000241
Ted Kremenek7deed0c2008-04-15 18:35:30 +0000242 // Update liveness inforamtion.
243 unsigned bit = AD.getIdx(DR->getDecl());
244 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
Mike Stump1eb44332009-09-09 15:08:12 +0000245
Ted Kremenekf63aa452007-09-28 20:38:59 +0000246 if (AD.Observer) { AD.Observer->ObserverKill(DR); }
Mike Stump1eb44332009-09-09 15:08:12 +0000247
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000248 // Handle things like +=, etc., which also generate "uses"
249 // of a variable. Do this just by visiting the subexpression.
Ted Kremenekbcb07d52007-09-28 21:29:33 +0000250 if (B->getOpcode() != BinaryOperator::Assign)
251 VisitDeclRefExpr(DR);
Ted Kremeneke4e63342007-09-06 00:17:54 +0000252 }
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000253 else // Not assigning to a variable. Process LHS as usual.
Ted Kremenek27b07c52007-09-06 21:26:58 +0000254 Visit(LHS);
Mike Stump1eb44332009-09-09 15:08:12 +0000255
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000256 Visit(B->getRHS());
Ted Kremeneke4e63342007-09-06 00:17:54 +0000257}
258
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000259void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
260 // Declarations effectively "kill" a variable since they cannot
261 // possibly be live before they are declared.
Ted Kremenek14f8b4f2008-08-05 20:46:55 +0000262 for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
263 DI != DE; ++DI)
264 if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) {
Ted Kremenek84fa6b92008-09-26 05:52:45 +0000265 // The initializer is evaluated after the variable comes into scope.
266 // Since this is a reverse dataflow analysis, we must evaluate the
267 // transfer function for this expression first.
Ted Kremenek2bca5e42008-02-07 02:38:55 +0000268 if (Expr* Init = VD->getInit())
269 Visit(Init);
Mike Stump1eb44332009-09-09 15:08:12 +0000270
Ted Kremeneke0dbda12008-12-09 00:14:14 +0000271 if (const VariableArrayType* VT =
272 AD.getContext().getAsVariableArrayType(VD->getType())) {
273 StmtIterator I(const_cast<VariableArrayType*>(VT));
Mike Stump1eb44332009-09-09 15:08:12 +0000274 StmtIterator E;
Ted Kremeneke0dbda12008-12-09 00:14:14 +0000275 for (; I != E; ++I) Visit(*I);
276 }
Mike Stump1eb44332009-09-09 15:08:12 +0000277
Ted Kremenek84fa6b92008-09-26 05:52:45 +0000278 // Update liveness information by killing the VarDecl.
279 unsigned bit = AD.getIdx(VD);
280 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
Ted Kremenekdcc48102008-02-25 22:28:54 +0000281 }
Ted Kremenek27b07c52007-09-06 21:26:58 +0000282}
Mike Stump1eb44332009-09-09 15:08:12 +0000283
Ted Kremeneke4e63342007-09-06 00:17:54 +0000284} // end anonymous namespace
285
Ted Kremenekf63aa452007-09-28 20:38:59 +0000286//===----------------------------------------------------------------------===//
287// Merge operator: if something is live on any successor block, it is live
288// in the current block (a set union).
Mike Stump1eb44332009-09-09 15:08:12 +0000289//===----------------------------------------------------------------------===//
Ted Kremeneke4e63342007-09-06 00:17:54 +0000290
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000291namespace {
Ted Kremenekfa59f1f2008-03-20 21:46:49 +0000292
293struct Merge {
Mike Stump1eb44332009-09-09 15:08:12 +0000294 typedef StmtDeclBitVector_Types::ValTy ValTy;
295
Ted Kremenekfa59f1f2008-03-20 21:46:49 +0000296 void operator()(ValTy& Dst, const ValTy& Src) {
297 Dst.OrDeclBits(Src);
Ted Kremenekbf98c992009-01-30 21:35:30 +0000298 Dst.OrBlkExprBits(Src);
Ted Kremenekfa59f1f2008-03-20 21:46:49 +0000299 }
300};
Mike Stump1eb44332009-09-09 15:08:12 +0000301
Ted Kremenekfa59f1f2008-03-20 21:46:49 +0000302typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver;
Ted Kremenekf63aa452007-09-28 20:38:59 +0000303} // end anonymous namespace
304
305//===----------------------------------------------------------------------===//
306// External interface to run Liveness analysis.
Mike Stump1eb44332009-09-09 15:08:12 +0000307//===----------------------------------------------------------------------===//
Ted Kremeneke4e63342007-09-06 00:17:54 +0000308
Ted Kremenek83c01da2008-01-11 00:40:29 +0000309void LiveVariables::runOnCFG(CFG& cfg) {
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000310 Solver S(*this);
311 S.runOnCFG(cfg);
312}
Ted Kremenek27b07c52007-09-06 21:26:58 +0000313
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000314void LiveVariables::runOnAllBlocks(const CFG& cfg,
Ted Kremenek79649df2008-01-17 18:25:22 +0000315 LiveVariables::ObserverTy* Obs,
316 bool recordStmtValues) {
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000317 Solver S(*this);
Ted Kremenek31d8cad2009-11-07 05:57:35 +0000318 SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer,
319 Obs);
Ted Kremenek79649df2008-01-17 18:25:22 +0000320 S.runOnAllBlocks(cfg, recordStmtValues);
Ted Kremenek27b07c52007-09-06 21:26:58 +0000321}
322
323//===----------------------------------------------------------------------===//
324// liveness queries
325//
326
Ted Kremenekc0576ca2007-09-10 17:36:42 +0000327bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
Ted Kremenek7cb15932008-03-13 16:55:07 +0000328 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
329 return i.isValid() ? getBlockData(B).getBit(i) : false;
Ted Kremenek27b07c52007-09-06 21:26:58 +0000330}
331
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000332bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
Ted Kremenek7cb15932008-03-13 16:55:07 +0000333 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
334 return i.isValid() ? Live.getBit(i) : false;
Ted Kremenek055c2752007-09-06 23:00:42 +0000335}
336
Ted Kremenek86946742008-01-17 20:48:37 +0000337bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
338 return getStmtData(Loc)(StmtVal,getAnalysisData());
339}
340
Ted Kremenek2a9da9c2008-01-18 00:40:21 +0000341bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
342 return getStmtData(Loc)(D,getAnalysisData());
343}
344
Ted Kremenek055c2752007-09-06 23:00:42 +0000345//===----------------------------------------------------------------------===//
Ted Kremeneke4e63342007-09-06 00:17:54 +0000346// printing liveness state for debugging
347//
348
Chris Lattnerabbbfd92009-11-06 18:01:14 +0000349void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const {
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000350 const AnalysisDataTy& AD = getAnalysisData();
Mike Stump1eb44332009-09-09 15:08:12 +0000351
Ted Kremenekf63aa452007-09-28 20:38:59 +0000352 for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
353 E = AD.end_decl(); I!=E; ++I)
Mike Stump1eb44332009-09-09 15:08:12 +0000354 if (V.getDeclBit(I->second)) {
Daniel Dunbar01eb9b92009-10-18 21:17:35 +0000355 llvm::errs() << " " << I->first->getIdentifier()->getName() << " <";
Chris Lattnerb9c3f962009-01-27 07:57:44 +0000356 I->first->getLocation().dump(SM);
Daniel Dunbarc0d56722009-10-17 18:12:37 +0000357 llvm::errs() << ">\n";
Ted Kremeneke4e63342007-09-06 00:17:54 +0000358 }
Mike Stump1eb44332009-09-09 15:08:12 +0000359}
Ted Kremeneke4e63342007-09-06 00:17:54 +0000360
Chris Lattnerabbbfd92009-11-06 18:01:14 +0000361void LiveVariables::dumpBlockLiveness(const SourceManager& M) const {
Jeffrey Yasskin3958b502009-11-10 01:17:45 +0000362 for (BlockDataMapTy::const_iterator I = getBlockDataMap().begin(),
Ted Kremenekfdd225e2007-09-25 04:31:27 +0000363 E = getBlockDataMap().end(); I!=E; ++I) {
Daniel Dunbarc0d56722009-10-17 18:12:37 +0000364 llvm::errs() << "\n[ B" << I->first->getBlockID()
365 << " (live variables at block exit) ]\n";
Ted Kremenek27b07c52007-09-06 21:26:58 +0000366 dumpLiveness(I->second,M);
367 }
Ted Kremenekc0576ca2007-09-10 17:36:42 +0000368
Daniel Dunbarc0d56722009-10-17 18:12:37 +0000369 llvm::errs() << "\n";
Ted Kremenekc0576ca2007-09-10 17:36:42 +0000370}