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;
107 const CFGBlock *currentBlock;
109 TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad), currentBlock(0) {}
111 LiveVariables::ValTy& getVal() { return LiveState; }
112 CFG& getCFG() { return AD.getCFG(); }
114 void VisitDeclRefExpr(DeclRefExpr* DR);
115 void VisitBinaryOperator(BinaryOperator* B);
116 void VisitBlockExpr(BlockExpr *B);
117 void VisitAssign(BinaryOperator* B);
118 void VisitDeclStmt(DeclStmt* DS);
119 void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S);
120 void VisitUnaryOperator(UnaryOperator* U);
122 void VisitTerminator(CFGBlock* B);
124 /// VisitConditionVariableInit - Handle the initialization of condition
125 /// variables at branches. Valid statements include IfStmt, ForStmt,
126 /// WhileStmt, and SwitchStmt.
127 void VisitConditionVariableInit(Stmt *S);
129 void SetTopValue(LiveVariables::ValTy& V) {
133 void setCurrentBlock(const CFGBlock *block) {
134 currentBlock = block;
138 void TransferFuncs::Visit(Stmt *S) {
140 if (S == getCurrentBlkStmt()) {
143 AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState);
145 if (getCFG().isBlkExpr(S))
146 LiveState(S, AD) = Dead;
148 StmtVisitor<TransferFuncs,void>::Visit(S);
150 else if (!getCFG().isBlkExpr(S)) {
153 AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState);
155 StmtVisitor<TransferFuncs,void>::Visit(S);
159 // For block-level expressions, mark that they are live.
160 LiveState(S,AD) = Alive;
164 void TransferFuncs::VisitConditionVariableInit(Stmt *S) {
165 assert(!getCFG().isBlkExpr(S));
166 CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S);
169 void TransferFuncs::VisitTerminator(CFGBlock* B) {
171 const Stmt* E = B->getTerminatorCondition();
176 assert (getCFG().isBlkExpr(E));
177 LiveState(E, AD) = Alive;
180 void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
181 if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
182 LiveState(V, AD) = Alive;
185 void TransferFuncs::VisitBlockExpr(BlockExpr *BE) {
186 AnalysisContext::referenced_decls_iterator I, E;
187 llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl());
188 for ( ; I != E ; ++I) {
189 DeclBitVector_Types::Idx i = AD.getIdx(*I);
191 LiveState.getBit(i) = Alive;
195 void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
196 if (B->isAssignmentOp()) VisitAssign(B);
201 TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
203 // This is a block-level expression. Its value is 'dead' before this point.
204 LiveState(S, AD) = Dead;
206 // This represents a 'use' of the collection.
207 Visit(S->getCollection());
209 // This represents a 'kill' for the variable.
210 Stmt* Element = S->getElement();
214 if (DeclStmt* DS = dyn_cast<DeclStmt>(Element))
215 VD = cast<VarDecl>(DS->getSingleDecl());
217 Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens();
218 if ((DR = dyn_cast<DeclRefExpr>(ElemExpr)))
219 VD = cast<VarDecl>(DR->getDecl());
227 LiveState(VD, AD) = Dead;
228 if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); }
233 void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
234 Expr *E = U->getSubExpr();
236 switch (U->getOpcode()) {
241 // Walk through the subexpressions, blasting through ParenExprs
242 // until we either find a DeclRefExpr or some non-DeclRefExpr
244 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens()))
245 if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
246 // Treat the --/++ operator as a kill.
247 if (AD.Observer) { AD.Observer->ObserverKill(DR); }
248 LiveState(VD, AD) = Alive;
249 return VisitDeclRefExpr(DR);
259 void TransferFuncs::VisitAssign(BinaryOperator* B) {
260 Expr* LHS = B->getLHS();
262 // Assigning to a variable?
263 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) {
264 // Assignments to references don't kill the ref's address
265 if (DR->getDecl()->getType()->isReferenceType()) {
266 VisitDeclRefExpr(DR);
268 if (AD.killAtAssign) {
269 // Update liveness inforamtion.
270 unsigned bit = AD.getIdx(DR->getDecl());
271 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
273 if (AD.Observer) { AD.Observer->ObserverKill(DR); }
275 // Handle things like +=, etc., which also generate "uses"
276 // of a variable. Do this just by visiting the subexpression.
277 if (B->getOpcode() != BO_Assign)
278 VisitDeclRefExpr(DR);
281 else // Not assigning to a variable. Process LHS as usual.
287 void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
288 // Declarations effectively "kill" a variable since they cannot
289 // possibly be live before they are declared.
290 for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
292 if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) {
293 // Update liveness information by killing the VarDecl.
294 unsigned bit = AD.getIdx(VD);
295 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
297 // The initializer is evaluated after the variable comes into scope, but
298 // before the DeclStmt (which binds the value to the variable).
299 // Since this is a reverse dataflow analysis, we must evaluate the
300 // transfer function for this expression after the DeclStmt. If the
301 // initializer references the variable (which is bad) then we extend
303 if (Expr* Init = VD->getInit())
306 if (const VariableArrayType* VT =
307 AD.getContext().getAsVariableArrayType(VD->getType())) {
308 StmtIterator I(const_cast<VariableArrayType*>(VT));
310 for (; I != E; ++I) Visit(*I);
315 } // end anonymous namespace
317 //===----------------------------------------------------------------------===//
318 // Merge operator: if something is live on any successor block, it is live
319 // in the current block (a set union).
320 //===----------------------------------------------------------------------===//
323 typedef StmtDeclBitVector_Types::Union Merge;
324 typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver;
325 } // end anonymous namespace
327 //===----------------------------------------------------------------------===//
328 // External interface to run Liveness analysis.
329 //===----------------------------------------------------------------------===//
331 void LiveVariables::runOnCFG(CFG& cfg) {
336 void LiveVariables::runOnAllBlocks(const CFG& cfg,
337 LiveVariables::ObserverTy* Obs,
338 bool recordStmtValues) {
340 SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer,
342 S.runOnAllBlocks(cfg, recordStmtValues);
345 //===----------------------------------------------------------------------===//
349 bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
350 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
351 return i.isValid() ? getBlockData(B).getBit(i) : false;
354 bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
355 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
356 return i.isValid() ? Live.getBit(i) : false;
359 bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
360 return getStmtData(Loc)(StmtVal,getAnalysisData());
363 bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
364 return getStmtData(Loc)(D,getAnalysisData());
367 //===----------------------------------------------------------------------===//
368 // printing liveness state for debugging
371 void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const {
372 const AnalysisDataTy& AD = getAnalysisData();
374 for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
375 E = AD.end_decl(); I!=E; ++I)
376 if (V.getDeclBit(I->second)) {
377 llvm::errs() << " " << I->first->getIdentifier()->getName() << " <";
378 I->first->getLocation().dump(SM);
379 llvm::errs() << ">\n";
383 void LiveVariables::dumpBlockLiveness(const SourceManager& M) const {
384 for (BlockDataMapTy::const_iterator I = getBlockDataMap().begin(),
385 E = getBlockDataMap().end(); I!=E; ++I) {
386 llvm::errs() << "\n[ B" << I->first->getBlockID()
387 << " (live variables at block exit) ]\n";
388 dumpLiveness(I->second,M);
391 llvm::errs() << "\n";