LiveVariables.cpp revision 208954
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 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 // 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 101namespace { 102 103class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{ 104 LiveVariables::AnalysisDataTy& AD; 105 LiveVariables::ValTy LiveState; 106public: 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 133void 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 159void TransferFuncs::VisitConditionVariableInit(Stmt *S) { 160 assert(!getCFG().isBlkExpr(S)); 161 CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S); 162} 163 164void 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 175void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { 176 if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl())) 177 LiveState(V, AD) = Alive; 178} 179 180void 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 190void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { 191 if (B->isAssignmentOp()) VisitAssign(B); 192 else VisitStmt(B); 193} 194 195void 196TransferFuncs::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 228void 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 254void 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 260 // Update liveness inforamtion. 261 unsigned bit = AD.getIdx(DR->getDecl()); 262 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); 263 264 if (AD.Observer) { AD.Observer->ObserverKill(DR); } 265 266 // Handle things like +=, etc., which also generate "uses" 267 // of a variable. Do this just by visiting the subexpression. 268 if (B->getOpcode() != BinaryOperator::Assign) 269 VisitDeclRefExpr(DR); 270 } 271 else // Not assigning to a variable. Process LHS as usual. 272 Visit(LHS); 273 274 Visit(B->getRHS()); 275} 276 277void TransferFuncs::VisitDeclStmt(DeclStmt* DS) { 278 // Declarations effectively "kill" a variable since they cannot 279 // possibly be live before they are declared. 280 for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); 281 DI != DE; ++DI) 282 if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) { 283 // Update liveness information by killing the VarDecl. 284 unsigned bit = AD.getIdx(VD); 285 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); 286 287 // The initializer is evaluated after the variable comes into scope, but 288 // before the DeclStmt (which binds the value to the variable). 289 // Since this is a reverse dataflow analysis, we must evaluate the 290 // transfer function for this expression after the DeclStmt. If the 291 // initializer references the variable (which is bad) then we extend 292 // its liveness. 293 if (Expr* Init = VD->getInit()) 294 Visit(Init); 295 296 if (const VariableArrayType* VT = 297 AD.getContext().getAsVariableArrayType(VD->getType())) { 298 StmtIterator I(const_cast<VariableArrayType*>(VT)); 299 StmtIterator E; 300 for (; I != E; ++I) Visit(*I); 301 } 302 } 303} 304 305} // end anonymous namespace 306 307//===----------------------------------------------------------------------===// 308// Merge operator: if something is live on any successor block, it is live 309// in the current block (a set union). 310//===----------------------------------------------------------------------===// 311 312namespace { 313 typedef StmtDeclBitVector_Types::Union Merge; 314 typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver; 315} // end anonymous namespace 316 317//===----------------------------------------------------------------------===// 318// External interface to run Liveness analysis. 319//===----------------------------------------------------------------------===// 320 321void LiveVariables::runOnCFG(CFG& cfg) { 322 Solver S(*this); 323 S.runOnCFG(cfg); 324} 325 326void LiveVariables::runOnAllBlocks(const CFG& cfg, 327 LiveVariables::ObserverTy* Obs, 328 bool recordStmtValues) { 329 Solver S(*this); 330 SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer, 331 Obs); 332 S.runOnAllBlocks(cfg, recordStmtValues); 333} 334 335//===----------------------------------------------------------------------===// 336// liveness queries 337// 338 339bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const { 340 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); 341 return i.isValid() ? getBlockData(B).getBit(i) : false; 342} 343 344bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const { 345 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); 346 return i.isValid() ? Live.getBit(i) : false; 347} 348 349bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const { 350 return getStmtData(Loc)(StmtVal,getAnalysisData()); 351} 352 353bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const { 354 return getStmtData(Loc)(D,getAnalysisData()); 355} 356 357//===----------------------------------------------------------------------===// 358// printing liveness state for debugging 359// 360 361void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const { 362 const AnalysisDataTy& AD = getAnalysisData(); 363 364 for (AnalysisDataTy::decl_iterator I = AD.begin_decl(), 365 E = AD.end_decl(); I!=E; ++I) 366 if (V.getDeclBit(I->second)) { 367 llvm::errs() << " " << I->first->getIdentifier()->getName() << " <"; 368 I->first->getLocation().dump(SM); 369 llvm::errs() << ">\n"; 370 } 371} 372 373void LiveVariables::dumpBlockLiveness(const SourceManager& M) const { 374 for (BlockDataMapTy::const_iterator I = getBlockDataMap().begin(), 375 E = getBlockDataMap().end(); I!=E; ++I) { 376 llvm::errs() << "\n[ B" << I->first->getBlockID() 377 << " (live variables at block exit) ]\n"; 378 dumpLiveness(I->second,M); 379 } 380 381 llvm::errs() << "\n"; 382} 383