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