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