LiveVariables.cpp revision 199990
1193326Sed//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==// 2193326Sed// 3193326Sed// The LLVM Compiler Infrastructure 4193326Sed// 5193326Sed// This file is distributed under the University of Illinois Open Source 6193326Sed// License. See LICENSE.TXT for details. 7193326Sed// 8193326Sed//===----------------------------------------------------------------------===// 9193326Sed// 10193326Sed// This file implements Live Variables analysis for source-level CFGs. 11193326Sed// 12193326Sed//===----------------------------------------------------------------------===// 13193326Sed 14193326Sed#include "clang/Analysis/Analyses/LiveVariables.h" 15193326Sed#include "clang/Basic/SourceManager.h" 16193326Sed#include "clang/AST/ASTContext.h" 17193326Sed#include "clang/AST/Expr.h" 18198092Srdivacky#include "clang/Analysis/CFG.h" 19193326Sed#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 20193326Sed#include "clang/Analysis/FlowSensitive/DataflowSolver.h" 21199482Srdivacky#include "clang/Analysis/Support/SaveAndRestore.h" 22199990Srdivacky#include "clang/Analysis/PathSensitive/AnalysisContext.h" 23193326Sed#include "llvm/ADT/SmallPtrSet.h" 24193326Sed#include "llvm/ADT/SmallVector.h" 25198398Srdivacky#include "llvm/Support/raw_ostream.h" 26193326Sed 27193326Sedusing namespace clang; 28193326Sed 29193326Sed//===----------------------------------------------------------------------===// 30193326Sed// Useful constants. 31198092Srdivacky//===----------------------------------------------------------------------===// 32193326Sed 33193326Sedstatic const bool Alive = true; 34198092Srdivackystatic const bool Dead = false; 35193326Sed 36193326Sed//===----------------------------------------------------------------------===// 37193326Sed// Dataflow initialization logic. 38198092Srdivacky//===----------------------------------------------------------------------===// 39193326Sed 40193326Sednamespace { 41199990Srdivackyclass RegisterDecls 42193326Sed : public CFGRecStmtDeclVisitor<RegisterDecls> { 43198092Srdivacky 44193326Sed LiveVariables::AnalysisDataTy& AD; 45198092Srdivacky 46193326Sed typedef llvm::SmallVector<VarDecl*, 20> AlwaysLiveTy; 47193326Sed AlwaysLiveTy AlwaysLive; 48193326Sed 49198092Srdivacky 50193326Sedpublic: 51193326Sed RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} 52193326Sed 53193326Sed ~RegisterDecls() { 54193326Sed 55193326Sed AD.AlwaysLive.resetValues(AD); 56198092Srdivacky 57193326Sed for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end(); 58198092Srdivacky I != E; ++ I) 59198092Srdivacky AD.AlwaysLive(*I, AD) = Alive; 60193326Sed } 61193326Sed 62193326Sed void VisitImplicitParamDecl(ImplicitParamDecl* IPD) { 63193326Sed // Register the VarDecl for tracking. 64193326Sed AD.Register(IPD); 65193326Sed } 66193326Sed 67193326Sed void VisitVarDecl(VarDecl* VD) { 68193326Sed // Register the VarDecl for tracking. 69193326Sed AD.Register(VD); 70198092Srdivacky 71193326Sed // Does the variable have global storage? If so, it is always live. 72193326Sed if (VD->hasGlobalStorage()) 73198092Srdivacky AlwaysLive.push_back(VD); 74193326Sed } 75198092Srdivacky 76193326Sed CFG& getCFG() { return AD.getCFG(); } 77193326Sed}; 78193326Sed} // end anonymous namespace 79193326Sed 80199990SrdivackyLiveVariables::LiveVariables(AnalysisContext &AC) { 81193326Sed // Register all referenced VarDecls. 82199990Srdivacky CFG &cfg = *AC.getCFG(); 83193326Sed getAnalysisData().setCFG(cfg); 84199990Srdivacky getAnalysisData().setContext(AC.getASTContext()); 85199990Srdivacky getAnalysisData().AC = &AC; 86198092Srdivacky 87193326Sed RegisterDecls R(getAnalysisData()); 88193326Sed cfg.VisitBlockStmts(R); 89193326Sed} 90193326Sed 91193326Sed//===----------------------------------------------------------------------===// 92193326Sed// Transfer functions. 93198092Srdivacky//===----------------------------------------------------------------------===// 94193326Sed 95193326Sednamespace { 96193326Sed 97199990Srdivackyclass TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{ 98193326Sed LiveVariables::AnalysisDataTy& AD; 99193326Sed LiveVariables::ValTy LiveState; 100193326Sedpublic: 101193326Sed TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} 102193326Sed 103193326Sed LiveVariables::ValTy& getVal() { return LiveState; } 104193326Sed CFG& getCFG() { return AD.getCFG(); } 105198092Srdivacky 106193326Sed void VisitDeclRefExpr(DeclRefExpr* DR); 107193326Sed void VisitBinaryOperator(BinaryOperator* B); 108199990Srdivacky void VisitBlockExpr(BlockExpr *B); 109193326Sed void VisitAssign(BinaryOperator* B); 110193326Sed void VisitDeclStmt(DeclStmt* DS); 111193326Sed void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S); 112193326Sed void VisitUnaryOperator(UnaryOperator* U); 113198092Srdivacky void Visit(Stmt *S); 114198092Srdivacky void VisitTerminator(CFGBlock* B); 115198092Srdivacky 116193326Sed void SetTopValue(LiveVariables::ValTy& V) { 117193326Sed V = AD.AlwaysLive; 118193326Sed } 119198092Srdivacky 120193326Sed}; 121198092Srdivacky 122193326Sedvoid TransferFuncs::Visit(Stmt *S) { 123198092Srdivacky 124193326Sed if (S == getCurrentBlkStmt()) { 125198092Srdivacky 126193326Sed if (AD.Observer) 127193326Sed AD.Observer->ObserveStmt(S,AD,LiveState); 128198092Srdivacky 129193326Sed if (getCFG().isBlkExpr(S)) LiveState(S,AD) = Dead; 130193326Sed StmtVisitor<TransferFuncs,void>::Visit(S); 131193326Sed } 132193326Sed else if (!getCFG().isBlkExpr(S)) { 133198092Srdivacky 134193326Sed if (AD.Observer) 135193326Sed AD.Observer->ObserveStmt(S,AD,LiveState); 136198092Srdivacky 137193326Sed StmtVisitor<TransferFuncs,void>::Visit(S); 138198092Srdivacky 139193326Sed } 140195341Sed else { 141193326Sed // For block-level expressions, mark that they are live. 142193326Sed LiveState(S,AD) = Alive; 143195341Sed } 144193326Sed} 145198092Srdivacky 146193326Sedvoid TransferFuncs::VisitTerminator(CFGBlock* B) { 147198092Srdivacky 148193326Sed const Stmt* E = B->getTerminatorCondition(); 149193326Sed 150193326Sed if (!E) 151193326Sed return; 152198092Srdivacky 153193326Sed assert (getCFG().isBlkExpr(E)); 154193326Sed LiveState(E, AD) = Alive; 155193326Sed} 156193326Sed 157193326Sedvoid TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { 158198092Srdivacky if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl())) 159199990Srdivacky LiveState(V, AD) = Alive; 160193326Sed} 161199990Srdivacky 162199990Srdivackyvoid TransferFuncs::VisitBlockExpr(BlockExpr *BE) { 163199990Srdivacky AnalysisContext::referenced_decls_iterator I, E; 164199990Srdivacky llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl()); 165199990Srdivacky for ( ; I != E ; ++I) { 166199990Srdivacky DeclBitVector_Types::Idx i = AD.getIdx(*I); 167199990Srdivacky if (i.isValid()) 168199990Srdivacky LiveState.getBit(i) = Alive; 169199990Srdivacky } 170199990Srdivacky} 171198092Srdivacky 172198092Srdivackyvoid TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { 173193326Sed if (B->isAssignmentOp()) VisitAssign(B); 174193326Sed else VisitStmt(B); 175193326Sed} 176193326Sed 177193326Sedvoid 178193326SedTransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 179198092Srdivacky 180193326Sed // This is a block-level expression. Its value is 'dead' before this point. 181193326Sed LiveState(S, AD) = Dead; 182193326Sed 183193326Sed // This represents a 'use' of the collection. 184193326Sed Visit(S->getCollection()); 185198092Srdivacky 186193326Sed // This represents a 'kill' for the variable. 187193326Sed Stmt* Element = S->getElement(); 188193326Sed DeclRefExpr* DR = 0; 189193326Sed VarDecl* VD = 0; 190198092Srdivacky 191193326Sed if (DeclStmt* DS = dyn_cast<DeclStmt>(Element)) 192193326Sed VD = cast<VarDecl>(DS->getSingleDecl()); 193193326Sed else { 194198092Srdivacky Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens(); 195193326Sed if ((DR = dyn_cast<DeclRefExpr>(ElemExpr))) 196193326Sed VD = cast<VarDecl>(DR->getDecl()); 197193326Sed else { 198193326Sed Visit(ElemExpr); 199193326Sed return; 200193326Sed } 201193326Sed } 202193326Sed 203193326Sed if (VD) { 204193326Sed LiveState(VD, AD) = Dead; 205193326Sed if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); } 206193326Sed } 207193326Sed} 208193326Sed 209198092Srdivacky 210193326Sedvoid TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { 211193326Sed Expr *E = U->getSubExpr(); 212198092Srdivacky 213193326Sed switch (U->getOpcode()) { 214193326Sed case UnaryOperator::PostInc: 215193326Sed case UnaryOperator::PostDec: 216193326Sed case UnaryOperator::PreInc: 217193326Sed case UnaryOperator::PreDec: 218193326Sed // Walk through the subexpressions, blasting through ParenExprs 219193326Sed // until we either find a DeclRefExpr or some non-DeclRefExpr 220193326Sed // expression. 221198092Srdivacky if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens())) 222193326Sed if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) { 223193326Sed // Treat the --/++ operator as a kill. 224193326Sed if (AD.Observer) { AD.Observer->ObserverKill(DR); } 225193326Sed LiveState(VD, AD) = Alive; 226193326Sed return VisitDeclRefExpr(DR); 227193326Sed } 228193326Sed 229193326Sed // Fall-through. 230198092Srdivacky 231193326Sed default: 232193326Sed return Visit(E); 233193326Sed } 234193326Sed} 235198092Srdivacky 236198092Srdivackyvoid TransferFuncs::VisitAssign(BinaryOperator* B) { 237193326Sed Expr* LHS = B->getLHS(); 238193326Sed 239193326Sed // Assigning to a variable? 240193326Sed if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) { 241198092Srdivacky 242193326Sed // Update liveness inforamtion. 243193326Sed unsigned bit = AD.getIdx(DR->getDecl()); 244193326Sed LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); 245198092Srdivacky 246193326Sed if (AD.Observer) { AD.Observer->ObserverKill(DR); } 247198092Srdivacky 248193326Sed // Handle things like +=, etc., which also generate "uses" 249193326Sed // of a variable. Do this just by visiting the subexpression. 250193326Sed if (B->getOpcode() != BinaryOperator::Assign) 251193326Sed VisitDeclRefExpr(DR); 252193326Sed } 253193326Sed else // Not assigning to a variable. Process LHS as usual. 254193326Sed Visit(LHS); 255198092Srdivacky 256193326Sed Visit(B->getRHS()); 257193326Sed} 258193326Sed 259193326Sedvoid TransferFuncs::VisitDeclStmt(DeclStmt* DS) { 260193326Sed // Declarations effectively "kill" a variable since they cannot 261193326Sed // possibly be live before they are declared. 262193326Sed for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); 263193326Sed DI != DE; ++DI) 264193326Sed if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) { 265193326Sed // The initializer is evaluated after the variable comes into scope. 266193326Sed // Since this is a reverse dataflow analysis, we must evaluate the 267193326Sed // transfer function for this expression first. 268193326Sed if (Expr* Init = VD->getInit()) 269193326Sed Visit(Init); 270198092Srdivacky 271193326Sed if (const VariableArrayType* VT = 272193326Sed AD.getContext().getAsVariableArrayType(VD->getType())) { 273193326Sed StmtIterator I(const_cast<VariableArrayType*>(VT)); 274198092Srdivacky StmtIterator E; 275193326Sed for (; I != E; ++I) Visit(*I); 276193326Sed } 277198092Srdivacky 278193326Sed // Update liveness information by killing the VarDecl. 279193326Sed unsigned bit = AD.getIdx(VD); 280193326Sed LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); 281193326Sed } 282193326Sed} 283198092Srdivacky 284193326Sed} // end anonymous namespace 285193326Sed 286193326Sed//===----------------------------------------------------------------------===// 287193326Sed// Merge operator: if something is live on any successor block, it is live 288193326Sed// in the current block (a set union). 289198092Srdivacky//===----------------------------------------------------------------------===// 290193326Sed 291193326Sednamespace { 292193326Sed 293193326Sedstruct Merge { 294198092Srdivacky typedef StmtDeclBitVector_Types::ValTy ValTy; 295198092Srdivacky 296193326Sed void operator()(ValTy& Dst, const ValTy& Src) { 297193326Sed Dst.OrDeclBits(Src); 298193326Sed Dst.OrBlkExprBits(Src); 299193326Sed } 300193326Sed}; 301198092Srdivacky 302193326Sedtypedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver; 303193326Sed} // end anonymous namespace 304193326Sed 305193326Sed//===----------------------------------------------------------------------===// 306193326Sed// External interface to run Liveness analysis. 307198092Srdivacky//===----------------------------------------------------------------------===// 308193326Sed 309193326Sedvoid LiveVariables::runOnCFG(CFG& cfg) { 310193326Sed Solver S(*this); 311193326Sed S.runOnCFG(cfg); 312193326Sed} 313193326Sed 314193326Sedvoid LiveVariables::runOnAllBlocks(const CFG& cfg, 315193326Sed LiveVariables::ObserverTy* Obs, 316193326Sed bool recordStmtValues) { 317193326Sed Solver S(*this); 318199482Srdivacky SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer, 319199482Srdivacky Obs); 320193326Sed S.runOnAllBlocks(cfg, recordStmtValues); 321193326Sed} 322193326Sed 323193326Sed//===----------------------------------------------------------------------===// 324193326Sed// liveness queries 325193326Sed// 326193326Sed 327193326Sedbool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const { 328193326Sed DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); 329193326Sed return i.isValid() ? getBlockData(B).getBit(i) : false; 330193326Sed} 331193326Sed 332193326Sedbool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const { 333193326Sed DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); 334193326Sed return i.isValid() ? Live.getBit(i) : false; 335193326Sed} 336193326Sed 337193326Sedbool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const { 338193326Sed return getStmtData(Loc)(StmtVal,getAnalysisData()); 339193326Sed} 340193326Sed 341193326Sedbool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const { 342193326Sed return getStmtData(Loc)(D,getAnalysisData()); 343193326Sed} 344193326Sed 345193326Sed//===----------------------------------------------------------------------===// 346193326Sed// printing liveness state for debugging 347193326Sed// 348193326Sed 349199482Srdivackyvoid LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const { 350193326Sed const AnalysisDataTy& AD = getAnalysisData(); 351198092Srdivacky 352193326Sed for (AnalysisDataTy::decl_iterator I = AD.begin_decl(), 353193326Sed E = AD.end_decl(); I!=E; ++I) 354198092Srdivacky if (V.getDeclBit(I->second)) { 355198398Srdivacky llvm::errs() << " " << I->first->getIdentifier()->getName() << " <"; 356193326Sed I->first->getLocation().dump(SM); 357198398Srdivacky llvm::errs() << ">\n"; 358193326Sed } 359198092Srdivacky} 360193326Sed 361199482Srdivackyvoid LiveVariables::dumpBlockLiveness(const SourceManager& M) const { 362199482Srdivacky for (BlockDataMapTy::const_iterator I = getBlockDataMap().begin(), 363193326Sed E = getBlockDataMap().end(); I!=E; ++I) { 364198398Srdivacky llvm::errs() << "\n[ B" << I->first->getBlockID() 365198398Srdivacky << " (live variables at block exit) ]\n"; 366193326Sed dumpLiveness(I->second,M); 367193326Sed } 368193326Sed 369198398Srdivacky llvm::errs() << "\n"; 370193326Sed} 371