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