LiveVariables.cpp revision e6d261e31fcc2204d4117ca753e843bc2c1164f4 
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) {
81  // Register all referenced VarDecls.
82  CFG &cfg = *AC.getCFG();
83  getAnalysisData().setCFG(cfg);
84  getAnalysisData().setContext(AC.getASTContext());
85  getAnalysisData().AC = &AC;
86
87  RegisterDecls R(getAnalysisData());
88  cfg.VisitBlockStmts(R);
89}
90
91//===----------------------------------------------------------------------===//
92// Transfer functions.
93//===----------------------------------------------------------------------===//
94
95namespace {
96
97class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
98  LiveVariables::AnalysisDataTy& AD;
99  LiveVariables::ValTy LiveState;
100public:
101  TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
102
103  LiveVariables::ValTy& getVal() { return LiveState; }
104  CFG& getCFG() { return AD.getCFG(); }
105
106  void VisitDeclRefExpr(DeclRefExpr* DR);
107  void VisitBinaryOperator(BinaryOperator* B);
108  void VisitBlockExpr(BlockExpr *B);
109  void VisitAssign(BinaryOperator* B);
110  void VisitDeclStmt(DeclStmt* DS);
111  void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S);
112  void VisitUnaryOperator(UnaryOperator* U);
113  void Visit(Stmt *S);
114  void VisitTerminator(CFGBlock* B);
115
116  /// VisitConditionVariableInit - Handle the initialization of condition
117  ///  variables at branches.  Valid statements include IfStmt, ForStmt,
118  ///  WhileStmt, and SwitchStmt.
119  void VisitConditionVariableInit(Stmt *S);
120
121  void SetTopValue(LiveVariables::ValTy& V) {
122    V = AD.AlwaysLive;
123  }
124
125};
126
127void TransferFuncs::Visit(Stmt *S) {
128
129  if (S == getCurrentBlkStmt()) {
130
131    if (AD.Observer)
132      AD.Observer->ObserveStmt(S,AD,LiveState);
133
134    if (getCFG().isBlkExpr(S))
135      LiveState(S, AD) = Dead;
136
137    StmtVisitor<TransferFuncs,void>::Visit(S);
138  }
139  else if (!getCFG().isBlkExpr(S)) {
140
141    if (AD.Observer)
142      AD.Observer->ObserveStmt(S,AD,LiveState);
143
144    StmtVisitor<TransferFuncs,void>::Visit(S);
145
146  }
147  else {
148    // For block-level expressions, mark that they are live.
149    LiveState(S,AD) = Alive;
150  }
151}
152
153void TransferFuncs::VisitConditionVariableInit(Stmt *S) {
154  assert(!getCFG().isBlkExpr(S));
155  CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S);
156}
157
158void TransferFuncs::VisitTerminator(CFGBlock* B) {
159
160  const Stmt* E = B->getTerminatorCondition();
161
162  if (!E)
163    return;
164
165  assert (getCFG().isBlkExpr(E));
166  LiveState(E, AD) = Alive;
167}
168
169void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
170  if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
171    LiveState(V, AD) = Alive;
172}
173
174void TransferFuncs::VisitBlockExpr(BlockExpr *BE) {
175  AnalysisContext::referenced_decls_iterator I, E;
176  llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl());
177  for ( ; I != E ; ++I) {
178    DeclBitVector_Types::Idx i = AD.getIdx(*I);
179    if (i.isValid())
180      LiveState.getBit(i) = Alive;
181  }
182}
183
184void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
185  if (B->isAssignmentOp()) VisitAssign(B);
186  else VisitStmt(B);
187}
188
189void
190TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
191
192  // This is a block-level expression.  Its value is 'dead' before this point.
193  LiveState(S, AD) = Dead;
194
195  // This represents a 'use' of the collection.
196  Visit(S->getCollection());
197
198  // This represents a 'kill' for the variable.
199  Stmt* Element = S->getElement();
200  DeclRefExpr* DR = 0;
201  VarDecl* VD = 0;
202
203  if (DeclStmt* DS = dyn_cast<DeclStmt>(Element))
204    VD = cast<VarDecl>(DS->getSingleDecl());
205  else {
206    Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens();
207    if ((DR = dyn_cast<DeclRefExpr>(ElemExpr)))
208      VD = cast<VarDecl>(DR->getDecl());
209    else {
210      Visit(ElemExpr);
211      return;
212    }
213  }
214
215  if (VD) {
216    LiveState(VD, AD) = Dead;
217    if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); }
218  }
219}
220
221
222void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
223  Expr *E = U->getSubExpr();
224
225  switch (U->getOpcode()) {
226  case UnaryOperator::PostInc:
227  case UnaryOperator::PostDec:
228  case UnaryOperator::PreInc:
229  case UnaryOperator::PreDec:
230    // Walk through the subexpressions, blasting through ParenExprs
231    // until we either find a DeclRefExpr or some non-DeclRefExpr
232    // expression.
233    if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens()))
234      if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
235        // Treat the --/++ operator as a kill.
236        if (AD.Observer) { AD.Observer->ObserverKill(DR); }
237        LiveState(VD, AD) = Alive;
238        return VisitDeclRefExpr(DR);
239      }
240
241    // Fall-through.
242
243  default:
244    return Visit(E);
245  }
246}
247
248void TransferFuncs::VisitAssign(BinaryOperator* B) {
249  Expr* LHS = B->getLHS();
250
251  // Assigning to a variable?
252  if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) {
253
254    // Update liveness inforamtion.
255    unsigned bit = AD.getIdx(DR->getDecl());
256    LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
257
258    if (AD.Observer) { AD.Observer->ObserverKill(DR); }
259
260    // Handle things like +=, etc., which also generate "uses"
261    // of a variable.  Do this just by visiting the subexpression.
262    if (B->getOpcode() != BinaryOperator::Assign)
263      VisitDeclRefExpr(DR);
264  }
265  else // Not assigning to a variable.  Process LHS as usual.
266    Visit(LHS);
267
268  Visit(B->getRHS());
269}
270
271void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
272  // Declarations effectively "kill" a variable since they cannot
273  // possibly be live before they are declared.
274  for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
275       DI != DE; ++DI)
276    if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) {
277      // The initializer is evaluated after the variable comes into scope.
278      // Since this is a reverse dataflow analysis, we must evaluate the
279      // transfer function for this expression first.
280      if (Expr* Init = VD->getInit())
281        Visit(Init);
282
283      if (const VariableArrayType* VT =
284            AD.getContext().getAsVariableArrayType(VD->getType())) {
285        StmtIterator I(const_cast<VariableArrayType*>(VT));
286        StmtIterator E;
287        for (; I != E; ++I) Visit(*I);
288      }
289
290      // Update liveness information by killing the VarDecl.
291      unsigned bit = AD.getIdx(VD);
292      LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
293    }
294}
295
296} // end anonymous namespace
297
298//===----------------------------------------------------------------------===//
299// Merge operator: if something is live on any successor block, it is live
300//  in the current block (a set union).
301//===----------------------------------------------------------------------===//
302
303namespace {
304  typedef StmtDeclBitVector_Types::Union Merge;
305  typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver;
306} // end anonymous namespace
307
308//===----------------------------------------------------------------------===//
309// External interface to run Liveness analysis.
310//===----------------------------------------------------------------------===//
311
312void LiveVariables::runOnCFG(CFG& cfg) {
313  Solver S(*this);
314  S.runOnCFG(cfg);
315}
316
317void LiveVariables::runOnAllBlocks(const CFG& cfg,
318                                   LiveVariables::ObserverTy* Obs,
319                                   bool recordStmtValues) {
320  Solver S(*this);
321  SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer,
322                                                   Obs);
323  S.runOnAllBlocks(cfg, recordStmtValues);
324}
325
326//===----------------------------------------------------------------------===//
327// liveness queries
328//
329
330bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
331  DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
332  return i.isValid() ? getBlockData(B).getBit(i) : false;
333}
334
335bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
336  DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
337  return i.isValid() ? Live.getBit(i) : false;
338}
339
340bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
341  return getStmtData(Loc)(StmtVal,getAnalysisData());
342}
343
344bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
345  return getStmtData(Loc)(D,getAnalysisData());
346}
347
348//===----------------------------------------------------------------------===//
349// printing liveness state for debugging
350//
351
352void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const {
353  const AnalysisDataTy& AD = getAnalysisData();
354
355  for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
356                                     E = AD.end_decl(); I!=E; ++I)
357    if (V.getDeclBit(I->second)) {
358      llvm::errs() << "  " << I->first->getIdentifier()->getName() << " <";
359      I->first->getLocation().dump(SM);
360      llvm::errs() << ">\n";
361    }
362}
363
364void LiveVariables::dumpBlockLiveness(const SourceManager& M) const {
365  for (BlockDataMapTy::const_iterator I = getBlockDataMap().begin(),
366       E = getBlockDataMap().end(); I!=E; ++I) {
367    llvm::errs() << "\n[ B" << I->first->getBlockID()
368                 << " (live variables at block exit) ]\n";
369    dumpLiveness(I->second,M);
370  }
371
372  llvm::errs() << "\n";
373}
374