LiveVariables.cpp revision fa59f1f053235e9adf32425f2b6049185771246d 
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/Support/Compiler.h"
23
24#include <string.h>
25#include <stdio.h>
26
27using namespace clang;
28
29//===----------------------------------------------------------------------===//
30// Dataflow initialization logic.
31//===----------------------------------------------------------------------===//
32
33namespace {
34class VISIBILITY_HIDDEN RegisterDecls
35  : public CFGRecStmtDeclVisitor<RegisterDecls> {
36
37  LiveVariables::AnalysisDataTy& AD;
38public:
39  RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
40  void VisitVarDecl(VarDecl* VD) { AD.Register(VD); }
41  CFG& getCFG() { return AD.getCFG(); }
42};
43} // end anonymous namespace
44
45
46LiveVariables::LiveVariables(CFG& cfg) {
47  // Register all referenced VarDecls.
48  getAnalysisData().setCFG(&cfg);
49  RegisterDecls R(getAnalysisData());
50  cfg.VisitBlockStmts(R);
51}
52
53//===----------------------------------------------------------------------===//
54// Transfer functions.
55//===----------------------------------------------------------------------===//
56
57namespace {
58
59static const bool Alive = true;
60static const bool Dead = false;
61
62class VISIBILITY_HIDDEN TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
63  LiveVariables::AnalysisDataTy& AD;
64  LiveVariables::ValTy LiveState;
65public:
66  TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
67
68  LiveVariables::ValTy& getVal() { return LiveState; }
69  CFG& getCFG() { return AD.getCFG(); }
70
71  void VisitDeclRefExpr(DeclRefExpr* DR);
72  void VisitBinaryOperator(BinaryOperator* B);
73  void VisitAssign(BinaryOperator* B);
74  void VisitDeclStmt(DeclStmt* DS);
75  void VisitUnaryOperator(UnaryOperator* U);
76  void Visit(Stmt *S);
77};
78
79void TransferFuncs::Visit(Stmt *S) {
80  if (AD.Observer)
81    AD.Observer->ObserveStmt(S,AD,LiveState);
82
83  if (S == getCurrentBlkStmt()) {
84    if (getCFG().isBlkExpr(S)) LiveState(S,AD) = Dead;
85    StmtVisitor<TransferFuncs,void>::Visit(S);
86  }
87  else if (!getCFG().isBlkExpr(S))
88    StmtVisitor<TransferFuncs,void>::Visit(S);
89  else
90    // For block-level expressions, mark that they are live.
91    LiveState(S,AD) = Alive;
92}
93
94void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
95  if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
96    LiveState(V,AD) = Alive;
97}
98
99void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
100  if (B->isAssignmentOp()) VisitAssign(B);
101  else VisitStmt(B);
102}
103
104void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
105  Expr *E = U->getSubExpr();
106
107  switch (U->getOpcode()) {
108  case UnaryOperator::SizeOf: return;
109  case UnaryOperator::PostInc:
110  case UnaryOperator::PostDec:
111  case UnaryOperator::PreInc:
112  case UnaryOperator::PreDec:
113  case UnaryOperator::AddrOf:
114    // Walk through the subexpressions, blasting through ParenExprs
115    // until we either find a DeclRefExpr or some non-DeclRefExpr
116    // expression.
117    if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens()))
118      if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
119        // Treat the --/++/& operator as a kill.
120        LiveState(VD, AD) = Dead;
121        if (AD.Observer) { AD.Observer->ObserverKill(DR); }
122        return VisitDeclRefExpr(DR);
123      }
124
125    // Fall-through.
126
127  default:
128    return Visit(E);
129  }
130}
131
132void TransferFuncs::VisitAssign(BinaryOperator* B) {
133  Expr* LHS = B->getLHS();
134
135  // Assigning to a variable?
136  if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) {
137    LiveState(DR->getDecl(),AD) = Dead;
138    if (AD.Observer) { AD.Observer->ObserverKill(DR); }
139
140    // Handle things like +=, etc., which also generate "uses"
141    // of a variable.  Do this just by visiting the subexpression.
142    if (B->getOpcode() != BinaryOperator::Assign)
143      VisitDeclRefExpr(DR);
144  }
145  else // Not assigning to a variable.  Process LHS as usual.
146    Visit(LHS);
147
148  Visit(B->getRHS());
149}
150
151void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
152  // Declarations effectively "kill" a variable since they cannot
153  // possibly be live before they are declared.
154  for (ScopedDecl* D = DS->getDecl(); D != NULL; D = D->getNextDeclarator())
155    if (VarDecl* VD = dyn_cast<VarDecl>(D)) {
156      LiveState(D,AD) = Dead;
157
158      if (Expr* Init = VD->getInit())
159        Visit(Init);
160    }
161}
162
163} // end anonymous namespace
164
165//===----------------------------------------------------------------------===//
166// Merge operator: if something is live on any successor block, it is live
167//  in the current block (a set union).
168//===----------------------------------------------------------------------===//
169
170namespace {
171
172struct Merge {
173  typedef ExprDeclBitVector_Types::ValTy ValTy;
174
175  void operator()(ValTy& Dst, const ValTy& Src) {
176    Dst.OrDeclBits(Src);
177    Dst.AndExprBits(Src);
178  }
179};
180
181typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver;
182} // end anonymous namespace
183
184//===----------------------------------------------------------------------===//
185// External interface to run Liveness analysis.
186//===----------------------------------------------------------------------===//
187
188void LiveVariables::runOnCFG(CFG& cfg) {
189  Solver S(*this);
190  S.runOnCFG(cfg);
191}
192
193void LiveVariables::runOnAllBlocks(const CFG& cfg,
194                                   LiveVariables::ObserverTy* Obs,
195                                   bool recordStmtValues) {
196  Solver S(*this);
197  ObserverTy* OldObserver = getAnalysisData().Observer;
198  getAnalysisData().Observer = Obs;
199  S.runOnAllBlocks(cfg, recordStmtValues);
200  getAnalysisData().Observer = OldObserver;
201}
202
203//===----------------------------------------------------------------------===//
204// liveness queries
205//
206
207bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
208  DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
209  return i.isValid() ? getBlockData(B).getBit(i) : false;
210}
211
212bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
213  DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
214  return i.isValid() ? Live.getBit(i) : false;
215}
216
217bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
218  return getStmtData(Loc)(StmtVal,getAnalysisData());
219}
220
221bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
222  return getStmtData(Loc)(D,getAnalysisData());
223}
224
225//===----------------------------------------------------------------------===//
226// printing liveness state for debugging
227//
228
229void LiveVariables::dumpLiveness(const ValTy& V, SourceManager& SM) const {
230  const AnalysisDataTy& AD = getAnalysisData();
231
232  for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
233                                     E = AD.end_decl(); I!=E; ++I)
234    if (V.getDeclBit(I->second)) {
235      SourceLocation PhysLoc = SM.getPhysicalLoc(I->first->getLocation());
236
237      fprintf(stderr, "  %s <%s:%u:%u>\n",
238              I->first->getIdentifier()->getName(),
239              SM.getSourceName(PhysLoc),
240              SM.getLineNumber(PhysLoc),
241              SM.getColumnNumber(PhysLoc));
242    }
243}
244
245void LiveVariables::dumpBlockLiveness(SourceManager& M) const {
246  for (BlockDataMapTy::iterator I = getBlockDataMap().begin(),
247       E = getBlockDataMap().end(); I!=E; ++I) {
248    fprintf(stderr, "\n[ B%d (live variables at block exit) ]\n",
249            I->first->getBlockID());
250
251    dumpLiveness(I->second,M);
252  }
253
254  fprintf(stderr,"\n");
255}
256