LiveVariables.cpp revision 848ec83483ca4ba52ed72c7e29ebc330f8c87252 
1//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements Live Variables analysis for source-level CFGs.
11//
12//===----------------------------------------------------------------------===//
13
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"
26
27using namespace clang;
28
29//===----------------------------------------------------------------------===//
30// Useful constants.
31//===----------------------------------------------------------------------===//
32
33static const bool Alive = true;
34static const bool Dead = false;
35
36//===----------------------------------------------------------------------===//
37// Dataflow initialization logic.
38//===----------------------------------------------------------------------===//
39
40namespace {
41class RegisterDecls
42  : public CFGRecStmtDeclVisitor<RegisterDecls> {
43
44  LiveVariables::AnalysisDataTy& AD;
45
46  typedef llvm::SmallVector<VarDecl*, 20> AlwaysLiveTy;
47  AlwaysLiveTy AlwaysLive;
48
49
50public:
51  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
62  void VisitImplicitParamDecl(ImplicitParamDecl* IPD) {
63    // Register the VarDecl for tracking.
64    AD.Register(IPD);
65  }
66
67  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  CFG& getCFG() { return AD.getCFG(); }
77};
78} // end anonymous namespace
79
80LiveVariables::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;
87
88  RegisterDecls R(getAnalysisData());
89  cfg.VisitBlockStmts(R);
90
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);
96}
97
98//===----------------------------------------------------------------------===//
99// Transfer functions.
100//===----------------------------------------------------------------------===//
101
102namespace {
103
104class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
105  LiveVariables::AnalysisDataTy& AD;
106  LiveVariables::ValTy LiveState;
107  const CFGBlock *currentBlock;
108public:
109  TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad), currentBlock(0) {}
110
111  LiveVariables::ValTy& getVal() { return LiveState; }
112  CFG& getCFG() { return AD.getCFG(); }
113
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);
121  void Visit(Stmt *S);
122  void VisitTerminator(CFGBlock* B);
123
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);
128
129  void SetTopValue(LiveVariables::ValTy& V) {
130    V = AD.AlwaysLive;
131  }
132
133  void setCurrentBlock(const CFGBlock *block) {
134    currentBlock = block;
135  }
136};
137
138void TransferFuncs::Visit(Stmt *S) {
139
140  if (S == getCurrentBlkStmt()) {
141
142    if (AD.Observer)
143      AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState);
144
145    if (getCFG().isBlkExpr(S))
146      LiveState(S, AD) = Dead;
147
148    StmtVisitor<TransferFuncs,void>::Visit(S);
149  }
150  else if (!getCFG().isBlkExpr(S)) {
151
152    if (AD.Observer)
153      AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState);
154
155    StmtVisitor<TransferFuncs,void>::Visit(S);
156
157  }
158  else {
159    // For block-level expressions, mark that they are live.
160    LiveState(S,AD) = Alive;
161  }
162}
163
164void TransferFuncs::VisitConditionVariableInit(Stmt *S) {
165  assert(!getCFG().isBlkExpr(S));
166  CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S);
167}
168
169void TransferFuncs::VisitTerminator(CFGBlock* B) {
170
171  const Stmt* E = B->getTerminatorCondition();
172
173  if (!E)
174    return;
175
176  assert (getCFG().isBlkExpr(E));
177  LiveState(E, AD) = Alive;
178}
179
180void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
181  if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
182    LiveState(V, AD) = Alive;
183}
184
185void 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);
190    if (i.isValid())
191      LiveState.getBit(i) = Alive;
192  }
193}
194
195void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
196  if (B->isAssignmentOp()) VisitAssign(B);
197  else VisitStmt(B);
198}
199
200void
201TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
202
203  // This is a block-level expression.  Its value is 'dead' before this point.
204  LiveState(S, AD) = Dead;
205
206  // This represents a 'use' of the collection.
207  Visit(S->getCollection());
208
209  // This represents a 'kill' for the variable.
210  Stmt* Element = S->getElement();
211  DeclRefExpr* DR = 0;
212  VarDecl* VD = 0;
213
214  if (DeclStmt* DS = dyn_cast<DeclStmt>(Element))
215    VD = cast<VarDecl>(DS->getSingleDecl());
216  else {
217    Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens();
218    if ((DR = dyn_cast<DeclRefExpr>(ElemExpr)))
219      VD = cast<VarDecl>(DR->getDecl());
220    else {
221      Visit(ElemExpr);
222      return;
223    }
224  }
225
226  if (VD) {
227    LiveState(VD, AD) = Dead;
228    if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); }
229  }
230}
231
232
233void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
234  Expr *E = U->getSubExpr();
235
236  switch (U->getOpcode()) {
237  case UO_PostInc:
238  case UO_PostDec:
239  case UO_PreInc:
240  case UO_PreDec:
241    // Walk through the subexpressions, blasting through ParenExprs
242    // until we either find a DeclRefExpr or some non-DeclRefExpr
243    // expression.
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);
250      }
251
252    // Fall-through.
253
254  default:
255    return Visit(E);
256  }
257}
258
259void TransferFuncs::VisitAssign(BinaryOperator* B) {
260  Expr* LHS = B->getLHS();
261
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);
267    } else {
268      if (AD.killAtAssign) {
269        // Update liveness inforamtion.
270        unsigned bit = AD.getIdx(DR->getDecl());
271        LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
272
273        if (AD.Observer) { AD.Observer->ObserverKill(DR); }
274      }
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);
279    }
280  }
281  else // Not assigning to a variable.  Process LHS as usual.
282    Visit(LHS);
283
284  Visit(B->getRHS());
285}
286
287void 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();
291       DI != DE; ++DI)
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);
296
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
302      // its liveness.
303      if (Expr* Init = VD->getInit())
304        Visit(Init);
305
306      if (const VariableArrayType* VT =
307            AD.getContext().getAsVariableArrayType(VD->getType())) {
308        StmtIterator I(const_cast<VariableArrayType*>(VT));
309        StmtIterator E;
310        for (; I != E; ++I) Visit(*I);
311      }
312    }
313}
314
315} // end anonymous namespace
316
317//===----------------------------------------------------------------------===//
318// Merge operator: if something is live on any successor block, it is live
319//  in the current block (a set union).
320//===----------------------------------------------------------------------===//
321
322namespace {
323  typedef StmtDeclBitVector_Types::Union Merge;
324  typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver;
325} // end anonymous namespace
326
327//===----------------------------------------------------------------------===//
328// External interface to run Liveness analysis.
329//===----------------------------------------------------------------------===//
330
331void LiveVariables::runOnCFG(CFG& cfg) {
332  Solver S(*this);
333  S.runOnCFG(cfg);
334}
335
336void LiveVariables::runOnAllBlocks(const CFG& cfg,
337                                   LiveVariables::ObserverTy* Obs,
338                                   bool recordStmtValues) {
339  Solver S(*this);
340  SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer,
341                                                   Obs);
342  S.runOnAllBlocks(cfg, recordStmtValues);
343}
344
345//===----------------------------------------------------------------------===//
346// liveness queries
347//
348
349bool 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;
352}
353
354bool 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;
357}
358
359bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
360  return getStmtData(Loc)(StmtVal,getAnalysisData());
361}
362
363bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
364  return getStmtData(Loc)(D,getAnalysisData());
365}
366
367//===----------------------------------------------------------------------===//
368// printing liveness state for debugging
369//
370
371void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const {
372  const AnalysisDataTy& AD = getAnalysisData();
373
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";
380    }
381}
382
383void 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);
389  }
390
391  llvm::errs() << "\n";
392}
393