LiveVariables.cpp revision 14f8b4ff660bcaa763974b8d0fae81857c594495 
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// details.
8//
9//===----------------------------------------------------------------------===//
10//
11// This file implements Live Variables analysis for source-level CFGs.
12//
13//===----------------------------------------------------------------------===//
14
15#include "clang/Analysis/Analyses/LiveVariables.h"
16#include "clang/Basic/SourceManager.h"
17#include "clang/AST/Expr.h"
18#include "clang/AST/CFG.h"
19#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
20#include "clang/Analysis/FlowSensitive/DataflowSolver.h"
21#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/Support/Compiler.h"
24
25#include <string.h>
26#include <stdio.h>
27
28using namespace clang;
29
30//===----------------------------------------------------------------------===//
31// Useful constants.
32//===----------------------------------------------------------------------===//
33
34static const bool Alive = true;
35static const bool Dead = false;
36
37//===----------------------------------------------------------------------===//
38// Dataflow initialization logic.
39//===----------------------------------------------------------------------===//
40
41namespace {
42class VISIBILITY_HIDDEN RegisterDecls
43  : public CFGRecStmtDeclVisitor<RegisterDecls> {
44
45  LiveVariables::AnalysisDataTy& AD;
46
47  typedef llvm::SmallVector<VarDecl*, 20> AlwaysLiveTy;
48  AlwaysLiveTy AlwaysLive;
49
50
51public:
52  RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
53
54  ~RegisterDecls() {
55
56    AD.AlwaysLive.resetValues(AD);
57
58    for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end();
59         I != E; ++ I)
60      AD.AlwaysLive(*I, AD) = Alive;
61  }
62
63  void VisitImplicitParamDecl(ImplicitParamDecl* IPD) {
64    // Register the VarDecl for tracking.
65    AD.Register(IPD);
66  }
67
68  void VisitVarDecl(VarDecl* VD) {
69    // Register the VarDecl for tracking.
70    AD.Register(VD);
71
72    // Does the variable have global storage?  If so, it is always live.
73    if (VD->hasGlobalStorage())
74      AlwaysLive.push_back(VD);
75  }
76
77  void VisitUnaryOperator(UnaryOperator* U) {
78    // Check for '&'.  Any VarDecl whose value has its address-taken we
79    // treat as always being live (flow-insensitive).
80
81    Expr* E = U->getSubExpr()->IgnoreParenCasts();
82
83    if (U->getOpcode() == UnaryOperator::AddrOf)
84      if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E))
85        if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
86          AD.Register(VD);
87          AlwaysLive.push_back(VD);
88          return;
89        }
90
91    Visit(E);
92  }
93
94  CFG& getCFG() { return AD.getCFG(); }
95};
96} // end anonymous namespace
97
98
99LiveVariables::LiveVariables(CFG& cfg) {
100  // Register all referenced VarDecls.
101  getAnalysisData().setCFG(&cfg);
102  RegisterDecls R(getAnalysisData());
103  cfg.VisitBlockStmts(R);
104}
105
106//===----------------------------------------------------------------------===//
107// Transfer functions.
108//===----------------------------------------------------------------------===//
109
110namespace {
111
112class VISIBILITY_HIDDEN TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
113  LiveVariables::AnalysisDataTy& AD;
114  LiveVariables::ValTy LiveState;
115public:
116  TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
117
118  LiveVariables::ValTy& getVal() { return LiveState; }
119  CFG& getCFG() { return AD.getCFG(); }
120
121  void VisitDeclRefExpr(DeclRefExpr* DR);
122  void VisitBinaryOperator(BinaryOperator* B);
123  void VisitAssign(BinaryOperator* B);
124  void VisitDeclStmt(DeclStmt* DS);
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 Expr* 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 TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
180  Expr *E = U->getSubExpr();
181
182  switch (U->getOpcode()) {
183  case UnaryOperator::SizeOf: return;
184  case UnaryOperator::PostInc:
185  case UnaryOperator::PostDec:
186  case UnaryOperator::PreInc:
187  case UnaryOperator::PreDec:
188    // Walk through the subexpressions, blasting through ParenExprs
189    // until we either find a DeclRefExpr or some non-DeclRefExpr
190    // expression.
191    if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens()))
192      if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
193        // Treat the --/++ operator as a kill.
194        if (AD.Observer) { AD.Observer->ObserverKill(DR); }
195        LiveState(VD, AD) = Alive;
196        return VisitDeclRefExpr(DR);
197      }
198
199    // Fall-through.
200
201  default:
202    return Visit(E);
203  }
204}
205
206void TransferFuncs::VisitAssign(BinaryOperator* B) {
207  Expr* LHS = B->getLHS();
208
209  // Assigning to a variable?
210  if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) {
211
212    // Update liveness inforamtion.
213    unsigned bit = AD.getIdx(DR->getDecl());
214    LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
215
216    if (AD.Observer) { AD.Observer->ObserverKill(DR); }
217
218    // Handle things like +=, etc., which also generate "uses"
219    // of a variable.  Do this just by visiting the subexpression.
220    if (B->getOpcode() != BinaryOperator::Assign)
221      VisitDeclRefExpr(DR);
222  }
223  else // Not assigning to a variable.  Process LHS as usual.
224    Visit(LHS);
225
226  Visit(B->getRHS());
227}
228
229void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
230  // Declarations effectively "kill" a variable since they cannot
231  // possibly be live before they are declared.
232  for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
233       DI != DE; ++DI)
234    if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) {
235
236      // Update liveness information.
237      unsigned bit = AD.getIdx(VD);
238      LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
239
240      if (Expr* Init = VD->getInit())
241        Visit(Init);
242    }
243}
244
245} // end anonymous namespace
246
247//===----------------------------------------------------------------------===//
248// Merge operator: if something is live on any successor block, it is live
249//  in the current block (a set union).
250//===----------------------------------------------------------------------===//
251
252namespace {
253
254struct Merge {
255  typedef ExprDeclBitVector_Types::ValTy ValTy;
256
257  void operator()(ValTy& Dst, const ValTy& Src) {
258    Dst.OrDeclBits(Src);
259    Dst.AndExprBits(Src);
260  }
261};
262
263typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver;
264} // end anonymous namespace
265
266//===----------------------------------------------------------------------===//
267// External interface to run Liveness analysis.
268//===----------------------------------------------------------------------===//
269
270void LiveVariables::runOnCFG(CFG& cfg) {
271  Solver S(*this);
272  S.runOnCFG(cfg);
273}
274
275void LiveVariables::runOnAllBlocks(const CFG& cfg,
276                                   LiveVariables::ObserverTy* Obs,
277                                   bool recordStmtValues) {
278  Solver S(*this);
279  ObserverTy* OldObserver = getAnalysisData().Observer;
280  getAnalysisData().Observer = Obs;
281  S.runOnAllBlocks(cfg, recordStmtValues);
282  getAnalysisData().Observer = OldObserver;
283}
284
285//===----------------------------------------------------------------------===//
286// liveness queries
287//
288
289bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
290  DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
291  return i.isValid() ? getBlockData(B).getBit(i) : false;
292}
293
294bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
295  DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
296  return i.isValid() ? Live.getBit(i) : false;
297}
298
299bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
300  return getStmtData(Loc)(StmtVal,getAnalysisData());
301}
302
303bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
304  return getStmtData(Loc)(D,getAnalysisData());
305}
306
307//===----------------------------------------------------------------------===//
308// printing liveness state for debugging
309//
310
311void LiveVariables::dumpLiveness(const ValTy& V, SourceManager& SM) const {
312  const AnalysisDataTy& AD = getAnalysisData();
313
314  for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
315                                     E = AD.end_decl(); I!=E; ++I)
316    if (V.getDeclBit(I->second)) {
317      SourceLocation PhysLoc = SM.getPhysicalLoc(I->first->getLocation());
318
319      fprintf(stderr, "  %s <%s:%u:%u>\n",
320              I->first->getIdentifier()->getName(),
321              SM.getSourceName(PhysLoc),
322              SM.getLineNumber(PhysLoc),
323              SM.getColumnNumber(PhysLoc));
324    }
325}
326
327void LiveVariables::dumpBlockLiveness(SourceManager& M) const {
328  for (BlockDataMapTy::iterator I = getBlockDataMap().begin(),
329       E = getBlockDataMap().end(); I!=E; ++I) {
330    fprintf(stderr, "\n[ B%d (live variables at block exit) ]\n",
331            I->first->getBlockID());
332
333    dumpLiveness(I->second,M);
334  }
335
336  fprintf(stderr,"\n");
337}
338