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