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