LiveVariables.cpp revision 193326
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/AST/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 143void TransferFuncs::VisitTerminator(CFGBlock* B) { 144 145 const Stmt* E = B->getTerminatorCondition(); 146 147 if (!E) 148 return; 149 150 assert (getCFG().isBlkExpr(E)); 151 LiveState(E, AD) = Alive; 152} 153 154void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { 155 if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl())) 156 LiveState(V,AD) = Alive; 157} 158 159void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { 160 if (B->isAssignmentOp()) VisitAssign(B); 161 else VisitStmt(B); 162} 163 164void 165TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 166 167 // This is a block-level expression. Its value is 'dead' before this point. 168 LiveState(S, AD) = Dead; 169 170 // This represents a 'use' of the collection. 171 Visit(S->getCollection()); 172 173 // This represents a 'kill' for the variable. 174 Stmt* Element = S->getElement(); 175 DeclRefExpr* DR = 0; 176 VarDecl* VD = 0; 177 178 if (DeclStmt* DS = dyn_cast<DeclStmt>(Element)) 179 VD = cast<VarDecl>(DS->getSingleDecl()); 180 else { 181 Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens(); 182 if ((DR = dyn_cast<DeclRefExpr>(ElemExpr))) 183 VD = cast<VarDecl>(DR->getDecl()); 184 else { 185 Visit(ElemExpr); 186 return; 187 } 188 } 189 190 if (VD) { 191 LiveState(VD, AD) = Dead; 192 if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); } 193 } 194} 195 196 197void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { 198 Expr *E = U->getSubExpr(); 199 200 switch (U->getOpcode()) { 201 case UnaryOperator::PostInc: 202 case UnaryOperator::PostDec: 203 case UnaryOperator::PreInc: 204 case UnaryOperator::PreDec: 205 // Walk through the subexpressions, blasting through ParenExprs 206 // until we either find a DeclRefExpr or some non-DeclRefExpr 207 // expression. 208 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens())) 209 if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) { 210 // Treat the --/++ operator as a kill. 211 if (AD.Observer) { AD.Observer->ObserverKill(DR); } 212 LiveState(VD, AD) = Alive; 213 return VisitDeclRefExpr(DR); 214 } 215 216 // Fall-through. 217 218 default: 219 return Visit(E); 220 } 221} 222 223void TransferFuncs::VisitAssign(BinaryOperator* B) { 224 Expr* LHS = B->getLHS(); 225 226 // Assigning to a variable? 227 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) { 228 229 // Update liveness inforamtion. 230 unsigned bit = AD.getIdx(DR->getDecl()); 231 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); 232 233 if (AD.Observer) { AD.Observer->ObserverKill(DR); } 234 235 // Handle things like +=, etc., which also generate "uses" 236 // of a variable. Do this just by visiting the subexpression. 237 if (B->getOpcode() != BinaryOperator::Assign) 238 VisitDeclRefExpr(DR); 239 } 240 else // Not assigning to a variable. Process LHS as usual. 241 Visit(LHS); 242 243 Visit(B->getRHS()); 244} 245 246void TransferFuncs::VisitDeclStmt(DeclStmt* DS) { 247 // Declarations effectively "kill" a variable since they cannot 248 // possibly be live before they are declared. 249 for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); 250 DI != DE; ++DI) 251 if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) { 252 // The initializer is evaluated after the variable comes into scope. 253 // Since this is a reverse dataflow analysis, we must evaluate the 254 // transfer function for this expression first. 255 if (Expr* Init = VD->getInit()) 256 Visit(Init); 257 258 if (const VariableArrayType* VT = 259 AD.getContext().getAsVariableArrayType(VD->getType())) { 260 StmtIterator I(const_cast<VariableArrayType*>(VT)); 261 StmtIterator E; 262 for (; I != E; ++I) Visit(*I); 263 } 264 265 // Update liveness information by killing the VarDecl. 266 unsigned bit = AD.getIdx(VD); 267 LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); 268 } 269} 270 271} // end anonymous namespace 272 273//===----------------------------------------------------------------------===// 274// Merge operator: if something is live on any successor block, it is live 275// in the current block (a set union). 276//===----------------------------------------------------------------------===// 277 278namespace { 279 280struct Merge { 281 typedef StmtDeclBitVector_Types::ValTy ValTy; 282 283 void operator()(ValTy& Dst, const ValTy& Src) { 284 Dst.OrDeclBits(Src); 285 Dst.OrBlkExprBits(Src); 286 } 287}; 288 289typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver; 290} // end anonymous namespace 291 292//===----------------------------------------------------------------------===// 293// External interface to run Liveness analysis. 294//===----------------------------------------------------------------------===// 295 296void LiveVariables::runOnCFG(CFG& cfg) { 297 Solver S(*this); 298 S.runOnCFG(cfg); 299} 300 301void LiveVariables::runOnAllBlocks(const CFG& cfg, 302 LiveVariables::ObserverTy* Obs, 303 bool recordStmtValues) { 304 Solver S(*this); 305 ObserverTy* OldObserver = getAnalysisData().Observer; 306 getAnalysisData().Observer = Obs; 307 S.runOnAllBlocks(cfg, recordStmtValues); 308 getAnalysisData().Observer = OldObserver; 309} 310 311//===----------------------------------------------------------------------===// 312// liveness queries 313// 314 315bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const { 316 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); 317 return i.isValid() ? getBlockData(B).getBit(i) : false; 318} 319 320bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const { 321 DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); 322 return i.isValid() ? Live.getBit(i) : false; 323} 324 325bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const { 326 return getStmtData(Loc)(StmtVal,getAnalysisData()); 327} 328 329bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const { 330 return getStmtData(Loc)(D,getAnalysisData()); 331} 332 333//===----------------------------------------------------------------------===// 334// printing liveness state for debugging 335// 336 337void LiveVariables::dumpLiveness(const ValTy& V, SourceManager& SM) const { 338 const AnalysisDataTy& AD = getAnalysisData(); 339 340 for (AnalysisDataTy::decl_iterator I = AD.begin_decl(), 341 E = AD.end_decl(); I!=E; ++I) 342 if (V.getDeclBit(I->second)) { 343 fprintf(stderr, " %s <", I->first->getIdentifier()->getName()); 344 I->first->getLocation().dump(SM); 345 fprintf(stderr, ">\n"); 346 } 347} 348 349void LiveVariables::dumpBlockLiveness(SourceManager& M) const { 350 for (BlockDataMapTy::iterator I = getBlockDataMap().begin(), 351 E = getBlockDataMap().end(); I!=E; ++I) { 352 fprintf(stderr, "\n[ B%d (live variables at block exit) ]\n", 353 I->first->getBlockID()); 354 355 dumpLiveness(I->second,M); 356 } 357 358 fprintf(stderr,"\n"); 359} 360