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