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