1249423Sdim//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==// 2249423Sdim// 3249423Sdim// The LLVM Compiler Infrastructure 4249423Sdim// 5249423Sdim// This file is distributed under the University of Illinois Open Source 6249423Sdim// License. See LICENSE.TXT for details. 7249423Sdim// 8249423Sdim//===----------------------------------------------------------------------===// 9249423Sdim// 10249423Sdim// This file implements Live Variables analysis for source-level CFGs. 11249423Sdim// 12249423Sdim//===----------------------------------------------------------------------===// 13249423Sdim 14193326Sed#include "clang/Analysis/Analyses/LiveVariables.h" 15249423Sdim#include "clang/AST/Stmt.h" 16249423Sdim#include "clang/AST/StmtVisitor.h" 17234353Sdim#include "clang/Analysis/Analyses/PostOrderCFGView.h" 18249423Sdim#include "clang/Analysis/AnalysisContext.h" 19198092Srdivacky#include "clang/Analysis/CFG.h" 20249423Sdim#include "llvm/ADT/DenseMap.h" 21226633Sdim#include "llvm/ADT/PostOrderIterator.h" 22249423Sdim#include "llvm/Support/raw_ostream.h" 23226633Sdim#include <algorithm> 24226633Sdim#include <vector> 25193326Sed 26226633Sdimusing namespace clang; 27193326Sed 28193326Sednamespace { 29198092Srdivacky 30226633Sdimclass DataflowWorklist { 31226633Sdim SmallVector<const CFGBlock *, 20> worklist; 32226633Sdim llvm::BitVector enqueuedBlocks; 33234353Sdim PostOrderCFGView *POV; 34193326Sedpublic: 35234353Sdim DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx) 36226633Sdim : enqueuedBlocks(cfg.getNumBlockIDs()), 37234353Sdim POV(Ctx.getAnalysis<PostOrderCFGView>()) {} 38226633Sdim 39226633Sdim void enqueueBlock(const CFGBlock *block); 40226633Sdim void enqueueSuccessors(const CFGBlock *block); 41226633Sdim void enqueuePredecessors(const CFGBlock *block); 42193326Sed 43226633Sdim const CFGBlock *dequeue(); 44193326Sed 45226633Sdim void sortWorklist(); 46226633Sdim}; 47198092Srdivacky 48226633Sdim} 49193326Sed 50226633Sdimvoid DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { 51226633Sdim if (block && !enqueuedBlocks[block->getBlockID()]) { 52226633Sdim enqueuedBlocks[block->getBlockID()] = true; 53226633Sdim worklist.push_back(block); 54193326Sed } 55226633Sdim} 56226633Sdim 57226633Sdimvoid DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 58226633Sdim const unsigned OldWorklistSize = worklist.size(); 59226633Sdim for (CFGBlock::const_succ_iterator I = block->succ_begin(), 60226633Sdim E = block->succ_end(); I != E; ++I) { 61226633Sdim enqueueBlock(*I); 62226633Sdim } 63193326Sed 64226633Sdim if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 65226633Sdim return; 66198092Srdivacky 67226633Sdim sortWorklist(); 68226633Sdim} 69226633Sdim 70226633Sdimvoid DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { 71226633Sdim const unsigned OldWorklistSize = worklist.size(); 72226633Sdim for (CFGBlock::const_pred_iterator I = block->pred_begin(), 73226633Sdim E = block->pred_end(); I != E; ++I) { 74226633Sdim enqueueBlock(*I); 75193326Sed } 76226633Sdim 77226633Sdim if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 78226633Sdim return; 79198092Srdivacky 80226633Sdim sortWorklist(); 81226633Sdim} 82193326Sed 83226633Sdimvoid DataflowWorklist::sortWorklist() { 84234353Sdim std::sort(worklist.begin(), worklist.end(), POV->getComparator()); 85226633Sdim} 86198092Srdivacky 87226633Sdimconst CFGBlock *DataflowWorklist::dequeue() { 88226633Sdim if (worklist.empty()) 89226633Sdim return 0; 90263508Sdim const CFGBlock *b = worklist.pop_back_val(); 91226633Sdim enqueuedBlocks[b->getBlockID()] = false; 92226633Sdim return b; 93193326Sed} 94193326Sed 95226633Sdimnamespace { 96226633Sdimclass LiveVariablesImpl { 97226633Sdimpublic: 98234353Sdim AnalysisDeclContext &analysisContext; 99226633Sdim std::vector<LiveVariables::LivenessValues> cfgBlockValues; 100226633Sdim llvm::ImmutableSet<const Stmt *>::Factory SSetFact; 101226633Sdim llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; 102226633Sdim llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness; 103226633Sdim llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness; 104226633Sdim llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness; 105226633Sdim llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment; 106226633Sdim const bool killAtAssign; 107226633Sdim 108226633Sdim LiveVariables::LivenessValues 109226633Sdim merge(LiveVariables::LivenessValues valsA, 110226633Sdim LiveVariables::LivenessValues valsB); 111226633Sdim 112226633Sdim LiveVariables::LivenessValues runOnBlock(const CFGBlock *block, 113226633Sdim LiveVariables::LivenessValues val, 114226633Sdim LiveVariables::Observer *obs = 0); 115226633Sdim 116226633Sdim void dumpBlockLiveness(const SourceManager& M); 117226633Sdim 118234353Sdim LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) 119226633Sdim : analysisContext(ac), 120226633Sdim SSetFact(false), // Do not canonicalize ImmutableSets by default. 121226633Sdim DSetFact(false), // This is a *major* performance win. 122226633Sdim killAtAssign(KillAtAssign) {} 123226633Sdim}; 124226633Sdim} 125226633Sdim 126226633Sdimstatic LiveVariablesImpl &getImpl(void *x) { 127226633Sdim return *((LiveVariablesImpl *) x); 128226633Sdim} 129226633Sdim 130193326Sed//===----------------------------------------------------------------------===// 131226633Sdim// Operations and queries on LivenessValues. 132198092Srdivacky//===----------------------------------------------------------------------===// 133193326Sed 134226633Sdimbool LiveVariables::LivenessValues::isLive(const Stmt *S) const { 135226633Sdim return liveStmts.contains(S); 136226633Sdim} 137193326Sed 138226633Sdimbool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { 139226633Sdim return liveDecls.contains(D); 140226633Sdim} 141193326Sed 142226633Sdimnamespace { 143226633Sdim template <typename SET> 144226633Sdim SET mergeSets(SET A, SET B) { 145226633Sdim if (A.isEmpty()) 146226633Sdim return B; 147226633Sdim 148226633Sdim for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { 149226633Sdim A = A.add(*it); 150226633Sdim } 151226633Sdim return A; 152226633Sdim } 153226633Sdim} 154198092Srdivacky 155234353Sdimvoid LiveVariables::Observer::anchor() { } 156234353Sdim 157226633SdimLiveVariables::LivenessValues 158226633SdimLiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, 159226633Sdim LiveVariables::LivenessValues valsB) { 160201361Srdivacky 161226633Sdim llvm::ImmutableSetRef<const Stmt *> 162226633Sdim SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()), 163226633Sdim SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()); 164226633Sdim 165226633Sdim 166226633Sdim llvm::ImmutableSetRef<const VarDecl *> 167226633Sdim DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), 168226633Sdim DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); 169226633Sdim 170198092Srdivacky 171226633Sdim SSetRefA = mergeSets(SSetRefA, SSetRefB); 172226633Sdim DSetRefA = mergeSets(DSetRefA, DSetRefB); 173218893Sdim 174226633Sdim // asImmutableSet() canonicalizes the tree, allowing us to do an easy 175226633Sdim // comparison afterwards. 176226633Sdim return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), 177226633Sdim DSetRefA.asImmutableSet()); 178226633Sdim} 179198092Srdivacky 180226633Sdimbool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { 181226633Sdim return liveStmts == V.liveStmts && liveDecls == V.liveDecls; 182226633Sdim} 183198092Srdivacky 184226633Sdim//===----------------------------------------------------------------------===// 185226633Sdim// Query methods. 186226633Sdim//===----------------------------------------------------------------------===// 187198092Srdivacky 188226633Sdimstatic bool isAlwaysAlive(const VarDecl *D) { 189226633Sdim return D->hasGlobalStorage(); 190226633Sdim} 191198092Srdivacky 192226633Sdimbool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { 193226633Sdim return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); 194226633Sdim} 195201361Srdivacky 196226633Sdimbool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { 197226633Sdim return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); 198226633Sdim} 199198092Srdivacky 200226633Sdimbool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) { 201226633Sdim return getImpl(impl).stmtsToLiveness[Loc].isLive(S); 202226633Sdim} 203198092Srdivacky 204226633Sdim//===----------------------------------------------------------------------===// 205226633Sdim// Dataflow computation. 206226633Sdim//===----------------------------------------------------------------------===// 207198092Srdivacky 208226633Sdimnamespace { 209226633Sdimclass TransferFunctions : public StmtVisitor<TransferFunctions> { 210226633Sdim LiveVariablesImpl &LV; 211226633Sdim LiveVariables::LivenessValues &val; 212226633Sdim LiveVariables::Observer *observer; 213226633Sdim const CFGBlock *currentBlock; 214226633Sdimpublic: 215226633Sdim TransferFunctions(LiveVariablesImpl &im, 216226633Sdim LiveVariables::LivenessValues &Val, 217226633Sdim LiveVariables::Observer *Observer, 218226633Sdim const CFGBlock *CurrentBlock) 219226633Sdim : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} 220226633Sdim 221226633Sdim void VisitBinaryOperator(BinaryOperator *BO); 222226633Sdim void VisitBlockExpr(BlockExpr *BE); 223226633Sdim void VisitDeclRefExpr(DeclRefExpr *DR); 224226633Sdim void VisitDeclStmt(DeclStmt *DS); 225226633Sdim void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); 226226633Sdim void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); 227226633Sdim void VisitUnaryOperator(UnaryOperator *UO); 228226633Sdim void Visit(Stmt *S); 229226633Sdim}; 230226633Sdim} 231226633Sdim 232226633Sdimstatic const VariableArrayType *FindVA(QualType Ty) { 233226633Sdim const Type *ty = Ty.getTypePtr(); 234226633Sdim while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) { 235226633Sdim if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT)) 236226633Sdim if (VAT->getSizeExpr()) 237226633Sdim return VAT; 238226633Sdim 239226633Sdim ty = VT->getElementType().getTypePtr(); 240193326Sed } 241226633Sdim 242226633Sdim return 0; 243193326Sed} 244226633Sdim 245234353Sdimstatic const Stmt *LookThroughStmt(const Stmt *S) { 246234353Sdim while (S) { 247234353Sdim if (const Expr *Ex = dyn_cast<Expr>(S)) 248234353Sdim S = Ex->IgnoreParens(); 249234353Sdim if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(S)) { 250234353Sdim S = EWC->getSubExpr(); 251234353Sdim continue; 252234353Sdim } 253234353Sdim if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) { 254234353Sdim S = OVE->getSourceExpr(); 255234353Sdim continue; 256234353Sdim } 257234353Sdim break; 258234353Sdim } 259234353Sdim return S; 260234353Sdim} 261234353Sdim 262234353Sdimstatic void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set, 263234353Sdim llvm::ImmutableSet<const Stmt *>::Factory &F, 264234353Sdim const Stmt *S) { 265234353Sdim Set = F.add(Set, LookThroughStmt(S)); 266234353Sdim} 267234353Sdim 268226633Sdimvoid TransferFunctions::Visit(Stmt *S) { 269226633Sdim if (observer) 270226633Sdim observer->observeStmt(S, currentBlock, val); 271201361Srdivacky 272226633Sdim StmtVisitor<TransferFunctions>::Visit(S); 273226633Sdim 274226633Sdim if (isa<Expr>(S)) { 275226633Sdim val.liveStmts = LV.SSetFact.remove(val.liveStmts, S); 276226633Sdim } 277226633Sdim 278226633Sdim // Mark all children expressions live. 279226633Sdim 280226633Sdim switch (S->getStmtClass()) { 281226633Sdim default: 282226633Sdim break; 283226633Sdim case Stmt::StmtExprClass: { 284226633Sdim // For statement expressions, look through the compound statement. 285226633Sdim S = cast<StmtExpr>(S)->getSubStmt(); 286226633Sdim break; 287226633Sdim } 288226633Sdim case Stmt::CXXMemberCallExprClass: { 289226633Sdim // Include the implicit "this" pointer as being live. 290226633Sdim CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S); 291226633Sdim if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { 292234353Sdim AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj); 293226633Sdim } 294226633Sdim break; 295226633Sdim } 296239462Sdim case Stmt::ObjCMessageExprClass: { 297239462Sdim // In calls to super, include the implicit "self" pointer as being live. 298239462Sdim ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S); 299239462Sdim if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance) 300239462Sdim val.liveDecls = LV.DSetFact.add(val.liveDecls, 301239462Sdim LV.analysisContext.getSelfDecl()); 302239462Sdim break; 303239462Sdim } 304226633Sdim case Stmt::DeclStmtClass: { 305226633Sdim const DeclStmt *DS = cast<DeclStmt>(S); 306226633Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) { 307226633Sdim for (const VariableArrayType* VA = FindVA(VD->getType()); 308226633Sdim VA != 0; VA = FindVA(VA->getElementType())) { 309234353Sdim AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr()); 310226633Sdim } 311226633Sdim } 312226633Sdim break; 313226633Sdim } 314234353Sdim case Stmt::PseudoObjectExprClass: { 315234353Sdim // A pseudo-object operation only directly consumes its result 316234353Sdim // expression. 317234353Sdim Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr(); 318234353Sdim if (!child) return; 319234353Sdim if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child)) 320234353Sdim child = OV->getSourceExpr(); 321234353Sdim child = child->IgnoreParens(); 322234353Sdim val.liveStmts = LV.SSetFact.add(val.liveStmts, child); 323234353Sdim return; 324234353Sdim } 325234353Sdim 326226633Sdim // FIXME: These cases eventually shouldn't be needed. 327226633Sdim case Stmt::ExprWithCleanupsClass: { 328226633Sdim S = cast<ExprWithCleanups>(S)->getSubExpr(); 329226633Sdim break; 330226633Sdim } 331226633Sdim case Stmt::CXXBindTemporaryExprClass: { 332226633Sdim S = cast<CXXBindTemporaryExpr>(S)->getSubExpr(); 333226633Sdim break; 334226633Sdim } 335226633Sdim case Stmt::UnaryExprOrTypeTraitExprClass: { 336226633Sdim // No need to unconditionally visit subexpressions. 337226633Sdim return; 338226633Sdim } 339226633Sdim } 340226633Sdim 341226633Sdim for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end(); 342226633Sdim it != ei; ++it) { 343234353Sdim if (Stmt *child = *it) 344234353Sdim AddLiveStmt(val.liveStmts, LV.SSetFact, child); 345226633Sdim } 346201361Srdivacky} 347198092Srdivacky 348226633Sdimvoid TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { 349226633Sdim if (B->isAssignmentOp()) { 350226633Sdim if (!LV.killAtAssign) 351226633Sdim return; 352226633Sdim 353226633Sdim // Assigning to a variable? 354226633Sdim Expr *LHS = B->getLHS()->IgnoreParens(); 355226633Sdim 356226633Sdim if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) 357226633Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 358226633Sdim // Assignments to references don't kill the ref's address 359226633Sdim if (VD->getType()->isReferenceType()) 360226633Sdim return; 361198092Srdivacky 362226633Sdim if (!isAlwaysAlive(VD)) { 363226633Sdim // The variable is now dead. 364226633Sdim val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 365226633Sdim } 366193326Sed 367226633Sdim if (observer) 368226633Sdim observer->observerKill(DR); 369226633Sdim } 370226633Sdim } 371193326Sed} 372193326Sed 373226633Sdimvoid TransferFunctions::VisitBlockExpr(BlockExpr *BE) { 374234353Sdim AnalysisDeclContext::referenced_decls_iterator I, E; 375226633Sdim llvm::tie(I, E) = 376226633Sdim LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl()); 377199990Srdivacky for ( ; I != E ; ++I) { 378226633Sdim const VarDecl *VD = *I; 379226633Sdim if (isAlwaysAlive(VD)) 380226633Sdim continue; 381226633Sdim val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); 382199990Srdivacky } 383199990Srdivacky} 384198092Srdivacky 385226633Sdimvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { 386226633Sdim if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) 387226633Sdim if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) 388226633Sdim val.liveDecls = LV.DSetFact.add(val.liveDecls, D); 389193326Sed} 390193326Sed 391226633Sdimvoid TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 392226633Sdim for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); 393226633Sdim DI != DE; ++DI) 394226633Sdim if (VarDecl *VD = dyn_cast<VarDecl>(*DI)) { 395226633Sdim if (!isAlwaysAlive(VD)) 396226633Sdim val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 397226633Sdim } 398226633Sdim} 399198092Srdivacky 400226633Sdimvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { 401226633Sdim // Kill the iteration variable. 402226633Sdim DeclRefExpr *DR = 0; 403226633Sdim const VarDecl *VD = 0; 404193326Sed 405226633Sdim Stmt *element = OS->getElement(); 406226633Sdim if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) { 407193326Sed VD = cast<VarDecl>(DS->getSingleDecl()); 408193326Sed } 409226633Sdim else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) { 410226633Sdim VD = cast<VarDecl>(DR->getDecl()); 411226633Sdim } 412226633Sdim 413193326Sed if (VD) { 414226633Sdim val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 415226633Sdim if (observer && DR) 416226633Sdim observer->observerKill(DR); 417193326Sed } 418193326Sed} 419193326Sed 420226633Sdimvoid TransferFunctions:: 421226633SdimVisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) 422226633Sdim{ 423226633Sdim // While sizeof(var) doesn't technically extend the liveness of 'var', it 424226633Sdim // does extent the liveness of metadata if 'var' is a VariableArrayType. 425226633Sdim // We handle that special case here. 426226633Sdim if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) 427226633Sdim return; 428198092Srdivacky 429226633Sdim const Expr *subEx = UE->getArgumentExpr(); 430226633Sdim if (subEx->getType()->isVariableArrayType()) { 431226633Sdim assert(subEx->isLValue()); 432226633Sdim val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens()); 433226633Sdim } 434226633Sdim} 435198092Srdivacky 436226633Sdimvoid TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { 437226633Sdim // Treat ++/-- as a kill. 438226633Sdim // Note we don't actually have to do anything if we don't have an observer, 439226633Sdim // since a ++/-- acts as both a kill and a "use". 440226633Sdim if (!observer) 441226633Sdim return; 442226633Sdim 443226633Sdim switch (UO->getOpcode()) { 444226633Sdim default: 445226633Sdim return; 446212904Sdim case UO_PostInc: 447226633Sdim case UO_PostDec: 448212904Sdim case UO_PreInc: 449212904Sdim case UO_PreDec: 450226633Sdim break; 451193326Sed } 452226633Sdim 453226633Sdim if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) 454226633Sdim if (isa<VarDecl>(DR->getDecl())) { 455226633Sdim // Treat ++/-- as a kill. 456226633Sdim observer->observerKill(DR); 457226633Sdim } 458193326Sed} 459198092Srdivacky 460226633SdimLiveVariables::LivenessValues 461226633SdimLiveVariablesImpl::runOnBlock(const CFGBlock *block, 462226633Sdim LiveVariables::LivenessValues val, 463226633Sdim LiveVariables::Observer *obs) { 464193326Sed 465226633Sdim TransferFunctions TF(*this, val, obs, block); 466226633Sdim 467226633Sdim // Visit the terminator (if any). 468226633Sdim if (const Stmt *term = block->getTerminator()) 469226633Sdim TF.Visit(const_cast<Stmt*>(term)); 470226633Sdim 471226633Sdim // Apply the transfer function for all Stmts in the block. 472226633Sdim for (CFGBlock::const_reverse_iterator it = block->rbegin(), 473226633Sdim ei = block->rend(); it != ei; ++it) { 474226633Sdim const CFGElement &elem = *it; 475239462Sdim 476249423Sdim if (Optional<CFGAutomaticObjDtor> Dtor = 477249423Sdim elem.getAs<CFGAutomaticObjDtor>()) { 478239462Sdim val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl()); 479239462Sdim continue; 480239462Sdim } 481239462Sdim 482249423Sdim if (!elem.getAs<CFGStmt>()) 483226633Sdim continue; 484226633Sdim 485249423Sdim const Stmt *S = elem.castAs<CFGStmt>().getStmt(); 486226633Sdim TF.Visit(const_cast<Stmt*>(S)); 487226633Sdim stmtsToLiveness[S] = val; 488193326Sed } 489226633Sdim return val; 490226633Sdim} 491198092Srdivacky 492226633Sdimvoid LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { 493226633Sdim const CFG *cfg = getImpl(impl).analysisContext.getCFG(); 494226633Sdim for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) 495226633Sdim getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); 496193326Sed} 497193326Sed 498226633SdimLiveVariables::LiveVariables(void *im) : impl(im) {} 499204643Srdivacky 500226633SdimLiveVariables::~LiveVariables() { 501226633Sdim delete (LiveVariablesImpl*) impl; 502193326Sed} 503198092Srdivacky 504226633SdimLiveVariables * 505234353SdimLiveVariables::computeLiveness(AnalysisDeclContext &AC, 506226633Sdim bool killAtAssign) { 507193326Sed 508226633Sdim // No CFG? Bail out. 509226633Sdim CFG *cfg = AC.getCFG(); 510226633Sdim if (!cfg) 511226633Sdim return 0; 512193326Sed 513239462Sdim // The analysis currently has scalability issues for very large CFGs. 514239462Sdim // Bail out if it looks too large. 515239462Sdim if (cfg->getNumBlockIDs() > 300000) 516239462Sdim return 0; 517239462Sdim 518226633Sdim LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); 519193326Sed 520226633Sdim // Construct the dataflow worklist. Enqueue the exit block as the 521226633Sdim // start of the analysis. 522234353Sdim DataflowWorklist worklist(*cfg, AC); 523226633Sdim llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); 524193326Sed 525226633Sdim // FIXME: we should enqueue using post order. 526226633Sdim for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { 527226633Sdim const CFGBlock *block = *it; 528226633Sdim worklist.enqueueBlock(block); 529226633Sdim 530226633Sdim // FIXME: Scan for DeclRefExprs using in the LHS of an assignment. 531226633Sdim // We need to do this because we lack context in the reverse analysis 532226633Sdim // to determine if a DeclRefExpr appears in such a context, and thus 533226633Sdim // doesn't constitute a "use". 534226633Sdim if (killAtAssign) 535226633Sdim for (CFGBlock::const_iterator bi = block->begin(), be = block->end(); 536226633Sdim bi != be; ++bi) { 537249423Sdim if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) { 538249423Sdim if (const BinaryOperator *BO = 539249423Sdim dyn_cast<BinaryOperator>(cs->getStmt())) { 540226633Sdim if (BO->getOpcode() == BO_Assign) { 541226633Sdim if (const DeclRefExpr *DR = 542226633Sdim dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) { 543226633Sdim LV->inAssignment[DR] = 1; 544226633Sdim } 545226633Sdim } 546226633Sdim } 547226633Sdim } 548226633Sdim } 549226633Sdim } 550226633Sdim 551226633Sdim worklist.sortWorklist(); 552226633Sdim 553226633Sdim while (const CFGBlock *block = worklist.dequeue()) { 554226633Sdim // Determine if the block's end value has changed. If not, we 555226633Sdim // have nothing left to do for this block. 556226633Sdim LivenessValues &prevVal = LV->blocksEndToLiveness[block]; 557226633Sdim 558226633Sdim // Merge the values of all successor blocks. 559226633Sdim LivenessValues val; 560226633Sdim for (CFGBlock::const_succ_iterator it = block->succ_begin(), 561226633Sdim ei = block->succ_end(); it != ei; ++it) { 562226633Sdim if (const CFGBlock *succ = *it) { 563226633Sdim val = LV->merge(val, LV->blocksBeginToLiveness[succ]); 564226633Sdim } 565226633Sdim } 566226633Sdim 567226633Sdim if (!everAnalyzedBlock[block->getBlockID()]) 568226633Sdim everAnalyzedBlock[block->getBlockID()] = true; 569226633Sdim else if (prevVal.equals(val)) 570226633Sdim continue; 571193326Sed 572226633Sdim prevVal = val; 573226633Sdim 574226633Sdim // Update the dataflow value for the start of this block. 575226633Sdim LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); 576226633Sdim 577226633Sdim // Enqueue the value to the predecessors. 578226633Sdim worklist.enqueuePredecessors(block); 579226633Sdim } 580226633Sdim 581226633Sdim return new LiveVariables(LV); 582193326Sed} 583193326Sed 584226633Sdimstatic bool compare_entries(const CFGBlock *A, const CFGBlock *B) { 585226633Sdim return A->getBlockID() < B->getBlockID(); 586193326Sed} 587193326Sed 588226633Sdimstatic bool compare_vd_entries(const Decl *A, const Decl *B) { 589226633Sdim SourceLocation ALoc = A->getLocStart(); 590226633Sdim SourceLocation BLoc = B->getLocStart(); 591226633Sdim return ALoc.getRawEncoding() < BLoc.getRawEncoding(); 592193326Sed} 593193326Sed 594226633Sdimvoid LiveVariables::dumpBlockLiveness(const SourceManager &M) { 595226633Sdim getImpl(impl).dumpBlockLiveness(M); 596193326Sed} 597193326Sed 598226633Sdimvoid LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { 599226633Sdim std::vector<const CFGBlock *> vec; 600226633Sdim for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator 601226633Sdim it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); 602226633Sdim it != ei; ++it) { 603226633Sdim vec.push_back(it->first); 604226633Sdim } 605226633Sdim std::sort(vec.begin(), vec.end(), compare_entries); 606193326Sed 607226633Sdim std::vector<const VarDecl*> declVec; 608193326Sed 609226633Sdim for (std::vector<const CFGBlock *>::iterator 610226633Sdim it = vec.begin(), ei = vec.end(); it != ei; ++it) { 611226633Sdim llvm::errs() << "\n[ B" << (*it)->getBlockID() 612226633Sdim << " (live variables at block exit) ]\n"; 613226633Sdim 614226633Sdim LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; 615226633Sdim declVec.clear(); 616226633Sdim 617226633Sdim for (llvm::ImmutableSet<const VarDecl *>::iterator si = 618226633Sdim vals.liveDecls.begin(), 619226633Sdim se = vals.liveDecls.end(); si != se; ++si) { 620226633Sdim declVec.push_back(*si); 621226633Sdim } 622226633Sdim 623226633Sdim std::sort(declVec.begin(), declVec.end(), compare_vd_entries); 624226633Sdim 625226633Sdim for (std::vector<const VarDecl*>::iterator di = declVec.begin(), 626226633Sdim de = declVec.end(); di != de; ++di) { 627226633Sdim llvm::errs() << " " << (*di)->getDeclName().getAsString() 628226633Sdim << " <"; 629226633Sdim (*di)->getLocation().dump(M); 630198398Srdivacky llvm::errs() << ">\n"; 631193326Sed } 632226633Sdim } 633226633Sdim llvm::errs() << "\n"; 634198092Srdivacky} 635193326Sed 636226633Sdimconst void *LiveVariables::getTag() { static int x; return &x; } 637226633Sdimconst void *RelaxedLiveVariables::getTag() { static int x; return &x; } 638