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