1 //=- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements Live Variables analysis for source-level CFGs.
12 //===----------------------------------------------------------------------===//
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"
27 using namespace clang;
29 //===----------------------------------------------------------------------===//
31 //===----------------------------------------------------------------------===//
33 static const bool Alive = true;
34 static const bool Dead = false;
36 //===----------------------------------------------------------------------===//
37 // Dataflow initialization logic.
38 //===----------------------------------------------------------------------===//
42 : public CFGRecStmtDeclVisitor<RegisterDecls> {
44 LiveVariables::AnalysisDataTy& AD;
46 typedef llvm::SmallVector<VarDecl*, 20> AlwaysLiveTy;
47 AlwaysLiveTy AlwaysLive;
51 RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
55 AD.AlwaysLive.resetValues(AD);
57 for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end();
59 AD.AlwaysLive(*I, AD) = Alive;
62 void VisitImplicitParamDecl(ImplicitParamDecl* IPD) {
63 // Register the VarDecl for tracking.
67 void VisitVarDecl(VarDecl* VD) {
68 // Register the VarDecl for tracking.
71 // Does the variable have global storage? If so, it is always live.
72 if (VD->hasGlobalStorage())
73 AlwaysLive.push_back(VD);
76 CFG& getCFG() { return AD.getCFG(); }
78 } // end anonymous namespace
80 LiveVariables::LiveVariables(AnalysisContext &AC, bool killAtAssign) {
81 // Register all referenced VarDecls.
82 CFG &cfg = *AC.getCFG();
83 getAnalysisData().setCFG(cfg);
84 getAnalysisData().setContext(AC.getASTContext());
85 getAnalysisData().AC = &AC;
86 getAnalysisData().killAtAssign = killAtAssign;
88 RegisterDecls R(getAnalysisData());
89 cfg.VisitBlockStmts(R);
91 // Register all parameters even if they didn't occur in the function body.
92 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(AC.getDecl()))
93 for (FunctionDecl::param_const_iterator PI = FD->param_begin(),
94 PE = FD->param_end(); PI != PE; ++PI)
95 getAnalysisData().Register(*PI);
98 //===----------------------------------------------------------------------===//
99 // Transfer functions.
100 //===----------------------------------------------------------------------===//
104 class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
105 LiveVariables::AnalysisDataTy& AD;
106 LiveVariables::ValTy LiveState;
108 TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
110 LiveVariables::ValTy& getVal() { return LiveState; }
111 CFG& getCFG() { return AD.getCFG(); }
113 void VisitDeclRefExpr(DeclRefExpr* DR);
114 void VisitBinaryOperator(BinaryOperator* B);
115 void VisitBlockExpr(BlockExpr *B);
116 void VisitAssign(BinaryOperator* B);
117 void VisitDeclStmt(DeclStmt* DS);
118 void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S);
119 void VisitUnaryOperator(UnaryOperator* U);
121 void VisitTerminator(CFGBlock* B);
123 /// VisitConditionVariableInit - Handle the initialization of condition
124 /// variables at branches. Valid statements include IfStmt, ForStmt,
125 /// WhileStmt, and SwitchStmt.
126 void VisitConditionVariableInit(Stmt *S);
128 void SetTopValue(LiveVariables::ValTy& V) {
134 void TransferFuncs::Visit(Stmt *S) {
136 if (S == getCurrentBlkStmt()) {
139 AD.Observer->ObserveStmt(S,AD,LiveState);
141 if (getCFG().isBlkExpr(S))
142 LiveState(S, AD) = Dead;
144 StmtVisitor<TransferFuncs,void>::Visit(S);
146 else if (!getCFG().isBlkExpr(S)) {
149 AD.Observer->ObserveStmt(S,AD,LiveState);
151 StmtVisitor<TransferFuncs,void>::Visit(S);
155 // For block-level expressions, mark that they are live.
156 LiveState(S,AD) = Alive;
160 void TransferFuncs::VisitConditionVariableInit(Stmt *S) {
161 assert(!getCFG().isBlkExpr(S));
162 CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S);
165 void TransferFuncs::VisitTerminator(CFGBlock* B) {
167 const Stmt* E = B->getTerminatorCondition();
172 assert (getCFG().isBlkExpr(E));
173 LiveState(E, AD) = Alive;
176 void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
177 if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
178 LiveState(V, AD) = Alive;
181 void TransferFuncs::VisitBlockExpr(BlockExpr *BE) {
182 AnalysisContext::referenced_decls_iterator I, E;
183 llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl());
184 for ( ; I != E ; ++I) {
185 DeclBitVector_Types::Idx i = AD.getIdx(*I);
187 LiveState.getBit(i) = Alive;
191 void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
192 if (B->isAssignmentOp()) VisitAssign(B);
197 TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
199 // This is a block-level expression. Its value is 'dead' before this point.
200 LiveState(S, AD) = Dead;
202 // This represents a 'use' of the collection.
203 Visit(S->getCollection());
205 // This represents a 'kill' for the variable.
206 Stmt* Element = S->getElement();
210 if (DeclStmt* DS = dyn_cast<DeclStmt>(Element))
211 VD = cast<VarDecl>(DS->getSingleDecl());
213 Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens();
214 if ((DR = dyn_cast<DeclRefExpr>(ElemExpr)))
215 VD = cast<VarDecl>(DR->getDecl());
223 LiveState(VD, AD) = Dead;
224 if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); }
229 void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
230 Expr *E = U->getSubExpr();
232 switch (U->getOpcode()) {
237 // Walk through the subexpressions, blasting through ParenExprs
238 // until we either find a DeclRefExpr or some non-DeclRefExpr
240 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens()))
241 if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
242 // Treat the --/++ operator as a kill.
243 if (AD.Observer) { AD.Observer->ObserverKill(DR); }
244 LiveState(VD, AD) = Alive;
245 return VisitDeclRefExpr(DR);
255 void TransferFuncs::VisitAssign(BinaryOperator* B) {
256 Expr* LHS = B->getLHS();
258 // Assigning to a variable?
259 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) {
260 // Assignments to references don't kill the ref's address
261 if (DR->getDecl()->getType()->isReferenceType()) {
262 VisitDeclRefExpr(DR);
264 if (AD.killAtAssign) {
265 // Update liveness inforamtion.
266 unsigned bit = AD.getIdx(DR->getDecl());
267 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
269 if (AD.Observer) { AD.Observer->ObserverKill(DR); }
271 // Handle things like +=, etc., which also generate "uses"
272 // of a variable. Do this just by visiting the subexpression.
273 if (B->getOpcode() != BO_Assign)
274 VisitDeclRefExpr(DR);
277 else // Not assigning to a variable. Process LHS as usual.
283 void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
284 // Declarations effectively "kill" a variable since they cannot
285 // possibly be live before they are declared.
286 for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
288 if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) {
289 // Update liveness information by killing the VarDecl.
290 unsigned bit = AD.getIdx(VD);
291 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
293 // The initializer is evaluated after the variable comes into scope, but
294 // before the DeclStmt (which binds the value to the variable).
295 // Since this is a reverse dataflow analysis, we must evaluate the
296 // transfer function for this expression after the DeclStmt. If the
297 // initializer references the variable (which is bad) then we extend
299 if (Expr* Init = VD->getInit())
302 if (const VariableArrayType* VT =
303 AD.getContext().getAsVariableArrayType(VD->getType())) {
304 StmtIterator I(const_cast<VariableArrayType*>(VT));
306 for (; I != E; ++I) Visit(*I);
311 } // end anonymous namespace
313 //===----------------------------------------------------------------------===//
314 // Merge operator: if something is live on any successor block, it is live
315 // in the current block (a set union).
316 //===----------------------------------------------------------------------===//
319 typedef StmtDeclBitVector_Types::Union Merge;
320 typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver;
321 } // end anonymous namespace
323 //===----------------------------------------------------------------------===//
324 // External interface to run Liveness analysis.
325 //===----------------------------------------------------------------------===//
327 void LiveVariables::runOnCFG(CFG& cfg) {
332 void LiveVariables::runOnAllBlocks(const CFG& cfg,
333 LiveVariables::ObserverTy* Obs,
334 bool recordStmtValues) {
336 SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer,
338 S.runOnAllBlocks(cfg, recordStmtValues);
341 //===----------------------------------------------------------------------===//
345 bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
346 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
347 return i.isValid() ? getBlockData(B).getBit(i) : false;
350 bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
351 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
352 return i.isValid() ? Live.getBit(i) : false;
355 bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
356 return getStmtData(Loc)(StmtVal,getAnalysisData());
359 bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
360 return getStmtData(Loc)(D,getAnalysisData());
363 //===----------------------------------------------------------------------===//
364 // printing liveness state for debugging
367 void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const {
368 const AnalysisDataTy& AD = getAnalysisData();
370 for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
371 E = AD.end_decl(); I!=E; ++I)
372 if (V.getDeclBit(I->second)) {
373 llvm::errs() << " " << I->first->getIdentifier()->getName() << " <";
374 I->first->getLocation().dump(SM);
375 llvm::errs() << ">\n";
379 void LiveVariables::dumpBlockLiveness(const SourceManager& M) const {
380 for (BlockDataMapTy::const_iterator I = getBlockDataMap().begin(),
381 E = getBlockDataMap().end(); I!=E; ++I) {
382 llvm::errs() << "\n[ B" << I->first->getBlockID()
383 << " (live variables at block exit) ]\n";
384 dumpLiveness(I->second,M);
387 llvm::errs() << "\n";