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) {
81 // Register all referenced VarDecls.
82 CFG &cfg = *AC.getCFG();
83 getAnalysisData().setCFG(cfg);
84 getAnalysisData().setContext(AC.getASTContext());
85 getAnalysisData().AC = &AC;
87 RegisterDecls R(getAnalysisData());
88 cfg.VisitBlockStmts(R);
90 // Register all parameters even if they didn't occur in the function body.
91 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(AC.getDecl()))
92 for (FunctionDecl::param_const_iterator PI = FD->param_begin(),
93 PE = FD->param_end(); PI != PE; ++PI)
94 getAnalysisData().Register(*PI);
97 //===----------------------------------------------------------------------===//
98 // Transfer functions.
99 //===----------------------------------------------------------------------===//
103 class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
104 LiveVariables::AnalysisDataTy& AD;
105 LiveVariables::ValTy LiveState;
107 TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
109 LiveVariables::ValTy& getVal() { return LiveState; }
110 CFG& getCFG() { return AD.getCFG(); }
112 void VisitDeclRefExpr(DeclRefExpr* DR);
113 void VisitBinaryOperator(BinaryOperator* B);
114 void VisitBlockExpr(BlockExpr *B);
115 void VisitAssign(BinaryOperator* B);
116 void VisitDeclStmt(DeclStmt* DS);
117 void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S);
118 void VisitUnaryOperator(UnaryOperator* U);
120 void VisitTerminator(CFGBlock* B);
122 /// VisitConditionVariableInit - Handle the initialization of condition
123 /// variables at branches. Valid statements include IfStmt, ForStmt,
124 /// WhileStmt, and SwitchStmt.
125 void VisitConditionVariableInit(Stmt *S);
127 void SetTopValue(LiveVariables::ValTy& V) {
133 void TransferFuncs::Visit(Stmt *S) {
135 if (S == getCurrentBlkStmt()) {
138 AD.Observer->ObserveStmt(S,AD,LiveState);
140 if (getCFG().isBlkExpr(S))
141 LiveState(S, AD) = Dead;
143 StmtVisitor<TransferFuncs,void>::Visit(S);
145 else if (!getCFG().isBlkExpr(S)) {
148 AD.Observer->ObserveStmt(S,AD,LiveState);
150 StmtVisitor<TransferFuncs,void>::Visit(S);
154 // For block-level expressions, mark that they are live.
155 LiveState(S,AD) = Alive;
159 void TransferFuncs::VisitConditionVariableInit(Stmt *S) {
160 assert(!getCFG().isBlkExpr(S));
161 CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S);
164 void TransferFuncs::VisitTerminator(CFGBlock* B) {
166 const Stmt* E = B->getTerminatorCondition();
171 assert (getCFG().isBlkExpr(E));
172 LiveState(E, AD) = Alive;
175 void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
176 if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
177 LiveState(V, AD) = Alive;
180 void TransferFuncs::VisitBlockExpr(BlockExpr *BE) {
181 AnalysisContext::referenced_decls_iterator I, E;
182 llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl());
183 for ( ; I != E ; ++I) {
184 DeclBitVector_Types::Idx i = AD.getIdx(*I);
186 LiveState.getBit(i) = Alive;
190 void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
191 if (B->isAssignmentOp()) VisitAssign(B);
196 TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
198 // This is a block-level expression. Its value is 'dead' before this point.
199 LiveState(S, AD) = Dead;
201 // This represents a 'use' of the collection.
202 Visit(S->getCollection());
204 // This represents a 'kill' for the variable.
205 Stmt* Element = S->getElement();
209 if (DeclStmt* DS = dyn_cast<DeclStmt>(Element))
210 VD = cast<VarDecl>(DS->getSingleDecl());
212 Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens();
213 if ((DR = dyn_cast<DeclRefExpr>(ElemExpr)))
214 VD = cast<VarDecl>(DR->getDecl());
222 LiveState(VD, AD) = Dead;
223 if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); }
228 void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
229 Expr *E = U->getSubExpr();
231 switch (U->getOpcode()) {
232 case UnaryOperator::PostInc:
233 case UnaryOperator::PostDec:
234 case UnaryOperator::PreInc:
235 case UnaryOperator::PreDec:
236 // Walk through the subexpressions, blasting through ParenExprs
237 // until we either find a DeclRefExpr or some non-DeclRefExpr
239 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens()))
240 if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
241 // Treat the --/++ operator as a kill.
242 if (AD.Observer) { AD.Observer->ObserverKill(DR); }
243 LiveState(VD, AD) = Alive;
244 return VisitDeclRefExpr(DR);
254 void TransferFuncs::VisitAssign(BinaryOperator* B) {
255 Expr* LHS = B->getLHS();
257 // Assigning to a variable?
258 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) {
260 // Update liveness inforamtion.
261 unsigned bit = AD.getIdx(DR->getDecl());
262 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
264 if (AD.Observer) { AD.Observer->ObserverKill(DR); }
266 // Handle things like +=, etc., which also generate "uses"
267 // of a variable. Do this just by visiting the subexpression.
268 if (B->getOpcode() != BinaryOperator::Assign)
269 VisitDeclRefExpr(DR);
271 else // Not assigning to a variable. Process LHS as usual.
277 void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
278 // Declarations effectively "kill" a variable since they cannot
279 // possibly be live before they are declared.
280 for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
282 if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) {
283 // Update liveness information by killing the VarDecl.
284 unsigned bit = AD.getIdx(VD);
285 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
287 // The initializer is evaluated after the variable comes into scope, but
288 // before the DeclStmt (which binds the value to the variable).
289 // Since this is a reverse dataflow analysis, we must evaluate the
290 // transfer function for this expression after the DeclStmt. If the
291 // initializer references the variable (which is bad) then we extend
293 if (Expr* Init = VD->getInit())
296 if (const VariableArrayType* VT =
297 AD.getContext().getAsVariableArrayType(VD->getType())) {
298 StmtIterator I(const_cast<VariableArrayType*>(VT));
300 for (; I != E; ++I) Visit(*I);
305 } // end anonymous namespace
307 //===----------------------------------------------------------------------===//
308 // Merge operator: if something is live on any successor block, it is live
309 // in the current block (a set union).
310 //===----------------------------------------------------------------------===//
313 typedef StmtDeclBitVector_Types::Union Merge;
314 typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver;
315 } // end anonymous namespace
317 //===----------------------------------------------------------------------===//
318 // External interface to run Liveness analysis.
319 //===----------------------------------------------------------------------===//
321 void LiveVariables::runOnCFG(CFG& cfg) {
326 void LiveVariables::runOnAllBlocks(const CFG& cfg,
327 LiveVariables::ObserverTy* Obs,
328 bool recordStmtValues) {
330 SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer,
332 S.runOnAllBlocks(cfg, recordStmtValues);
335 //===----------------------------------------------------------------------===//
339 bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
340 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
341 return i.isValid() ? getBlockData(B).getBit(i) : false;
344 bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
345 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
346 return i.isValid() ? Live.getBit(i) : false;
349 bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
350 return getStmtData(Loc)(StmtVal,getAnalysisData());
353 bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
354 return getStmtData(Loc)(D,getAnalysisData());
357 //===----------------------------------------------------------------------===//
358 // printing liveness state for debugging
361 void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const {
362 const AnalysisDataTy& AD = getAnalysisData();
364 for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
365 E = AD.end_decl(); I!=E; ++I)
366 if (V.getDeclBit(I->second)) {
367 llvm::errs() << " " << I->first->getIdentifier()->getName() << " <";
368 I->first->getLocation().dump(SM);
369 llvm::errs() << ">\n";
373 void LiveVariables::dumpBlockLiveness(const SourceManager& M) const {
374 for (BlockDataMapTy::const_iterator I = getBlockDataMap().begin(),
375 E = getBlockDataMap().end(); I!=E; ++I) {
376 llvm::errs() << "\n[ B" << I->first->getBlockID()
377 << " (live variables at block exit) ]\n";
378 dumpLiveness(I->second,M);
381 llvm::errs() << "\n";