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 enqueuePredecessors(const CFGBlock *block); 41193326Sed 42226633Sdim const CFGBlock *dequeue(); 43193326Sed 44226633Sdim void sortWorklist(); 45226633Sdim}; 46198092Srdivacky 47226633Sdim} 48193326Sed 49226633Sdimvoid DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { 50226633Sdim if (block && !enqueuedBlocks[block->getBlockID()]) { 51226633Sdim enqueuedBlocks[block->getBlockID()] = true; 52226633Sdim worklist.push_back(block); 53193326Sed } 54226633Sdim} 55193326Sed 56226633Sdimvoid DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { 57226633Sdim const unsigned OldWorklistSize = worklist.size(); 58226633Sdim for (CFGBlock::const_pred_iterator I = block->pred_begin(), 59226633Sdim E = block->pred_end(); I != E; ++I) { 60226633Sdim enqueueBlock(*I); 61193326Sed } 62226633Sdim 63226633Sdim if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 64226633Sdim return; 65198092Srdivacky 66226633Sdim sortWorklist(); 67226633Sdim} 68193326Sed 69226633Sdimvoid DataflowWorklist::sortWorklist() { 70234353Sdim std::sort(worklist.begin(), worklist.end(), POV->getComparator()); 71226633Sdim} 72198092Srdivacky 73226633Sdimconst CFGBlock *DataflowWorklist::dequeue() { 74226633Sdim if (worklist.empty()) 75276479Sdim return nullptr; 76261991Sdim const CFGBlock *b = worklist.pop_back_val(); 77226633Sdim enqueuedBlocks[b->getBlockID()] = false; 78226633Sdim return b; 79193326Sed} 80193326Sed 81226633Sdimnamespace { 82226633Sdimclass LiveVariablesImpl { 83226633Sdimpublic: 84234353Sdim AnalysisDeclContext &analysisContext; 85226633Sdim llvm::ImmutableSet<const Stmt *>::Factory SSetFact; 86226633Sdim llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; 87226633Sdim llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness; 88226633Sdim llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness; 89226633Sdim llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness; 90226633Sdim llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment; 91226633Sdim const bool killAtAssign; 92226633Sdim 93226633Sdim LiveVariables::LivenessValues 94226633Sdim merge(LiveVariables::LivenessValues valsA, 95226633Sdim LiveVariables::LivenessValues valsB); 96226633Sdim 97276479Sdim LiveVariables::LivenessValues 98276479Sdim runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, 99276479Sdim LiveVariables::Observer *obs = nullptr); 100276479Sdim 101226633Sdim void dumpBlockLiveness(const SourceManager& M); 102226633Sdim 103234353Sdim LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) 104226633Sdim : analysisContext(ac), 105226633Sdim SSetFact(false), // Do not canonicalize ImmutableSets by default. 106226633Sdim DSetFact(false), // This is a *major* performance win. 107226633Sdim killAtAssign(KillAtAssign) {} 108226633Sdim}; 109226633Sdim} 110226633Sdim 111226633Sdimstatic LiveVariablesImpl &getImpl(void *x) { 112226633Sdim return *((LiveVariablesImpl *) x); 113226633Sdim} 114226633Sdim 115193326Sed//===----------------------------------------------------------------------===// 116226633Sdim// Operations and queries on LivenessValues. 117198092Srdivacky//===----------------------------------------------------------------------===// 118193326Sed 119226633Sdimbool LiveVariables::LivenessValues::isLive(const Stmt *S) const { 120226633Sdim return liveStmts.contains(S); 121226633Sdim} 122193326Sed 123226633Sdimbool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { 124226633Sdim return liveDecls.contains(D); 125226633Sdim} 126193326Sed 127226633Sdimnamespace { 128226633Sdim template <typename SET> 129226633Sdim SET mergeSets(SET A, SET B) { 130226633Sdim if (A.isEmpty()) 131226633Sdim return B; 132226633Sdim 133226633Sdim for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { 134226633Sdim A = A.add(*it); 135226633Sdim } 136226633Sdim return A; 137226633Sdim } 138226633Sdim} 139198092Srdivacky 140234353Sdimvoid LiveVariables::Observer::anchor() { } 141234353Sdim 142226633SdimLiveVariables::LivenessValues 143226633SdimLiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, 144226633Sdim LiveVariables::LivenessValues valsB) { 145201361Srdivacky 146226633Sdim llvm::ImmutableSetRef<const Stmt *> 147226633Sdim SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()), 148226633Sdim SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()); 149226633Sdim 150226633Sdim 151226633Sdim llvm::ImmutableSetRef<const VarDecl *> 152226633Sdim DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), 153226633Sdim DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); 154226633Sdim 155198092Srdivacky 156226633Sdim SSetRefA = mergeSets(SSetRefA, SSetRefB); 157226633Sdim DSetRefA = mergeSets(DSetRefA, DSetRefB); 158218893Sdim 159226633Sdim // asImmutableSet() canonicalizes the tree, allowing us to do an easy 160226633Sdim // comparison afterwards. 161226633Sdim return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), 162226633Sdim DSetRefA.asImmutableSet()); 163226633Sdim} 164198092Srdivacky 165226633Sdimbool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { 166226633Sdim return liveStmts == V.liveStmts && liveDecls == V.liveDecls; 167226633Sdim} 168198092Srdivacky 169226633Sdim//===----------------------------------------------------------------------===// 170226633Sdim// Query methods. 171226633Sdim//===----------------------------------------------------------------------===// 172198092Srdivacky 173226633Sdimstatic bool isAlwaysAlive(const VarDecl *D) { 174226633Sdim return D->hasGlobalStorage(); 175226633Sdim} 176198092Srdivacky 177226633Sdimbool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { 178226633Sdim return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); 179226633Sdim} 180201361Srdivacky 181226633Sdimbool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { 182226633Sdim return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); 183226633Sdim} 184198092Srdivacky 185226633Sdimbool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) { 186226633Sdim return getImpl(impl).stmtsToLiveness[Loc].isLive(S); 187226633Sdim} 188198092Srdivacky 189226633Sdim//===----------------------------------------------------------------------===// 190226633Sdim// Dataflow computation. 191226633Sdim//===----------------------------------------------------------------------===// 192198092Srdivacky 193226633Sdimnamespace { 194226633Sdimclass TransferFunctions : public StmtVisitor<TransferFunctions> { 195226633Sdim LiveVariablesImpl &LV; 196226633Sdim LiveVariables::LivenessValues &val; 197226633Sdim LiveVariables::Observer *observer; 198226633Sdim const CFGBlock *currentBlock; 199226633Sdimpublic: 200226633Sdim TransferFunctions(LiveVariablesImpl &im, 201226633Sdim LiveVariables::LivenessValues &Val, 202226633Sdim LiveVariables::Observer *Observer, 203226633Sdim const CFGBlock *CurrentBlock) 204226633Sdim : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} 205226633Sdim 206226633Sdim void VisitBinaryOperator(BinaryOperator *BO); 207226633Sdim void VisitBlockExpr(BlockExpr *BE); 208226633Sdim void VisitDeclRefExpr(DeclRefExpr *DR); 209226633Sdim void VisitDeclStmt(DeclStmt *DS); 210226633Sdim void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); 211226633Sdim void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); 212226633Sdim void VisitUnaryOperator(UnaryOperator *UO); 213226633Sdim void Visit(Stmt *S); 214226633Sdim}; 215226633Sdim} 216226633Sdim 217226633Sdimstatic const VariableArrayType *FindVA(QualType Ty) { 218226633Sdim const Type *ty = Ty.getTypePtr(); 219226633Sdim while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) { 220226633Sdim if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT)) 221226633Sdim if (VAT->getSizeExpr()) 222226633Sdim return VAT; 223226633Sdim 224226633Sdim ty = VT->getElementType().getTypePtr(); 225193326Sed } 226276479Sdim 227276479Sdim return nullptr; 228193326Sed} 229226633Sdim 230234353Sdimstatic const Stmt *LookThroughStmt(const Stmt *S) { 231234353Sdim while (S) { 232234353Sdim if (const Expr *Ex = dyn_cast<Expr>(S)) 233234353Sdim S = Ex->IgnoreParens(); 234234353Sdim if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(S)) { 235234353Sdim S = EWC->getSubExpr(); 236234353Sdim continue; 237234353Sdim } 238234353Sdim if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) { 239234353Sdim S = OVE->getSourceExpr(); 240234353Sdim continue; 241234353Sdim } 242234353Sdim break; 243234353Sdim } 244234353Sdim return S; 245234353Sdim} 246234353Sdim 247234353Sdimstatic void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set, 248234353Sdim llvm::ImmutableSet<const Stmt *>::Factory &F, 249234353Sdim const Stmt *S) { 250234353Sdim Set = F.add(Set, LookThroughStmt(S)); 251234353Sdim} 252234353Sdim 253226633Sdimvoid TransferFunctions::Visit(Stmt *S) { 254226633Sdim if (observer) 255226633Sdim observer->observeStmt(S, currentBlock, val); 256201361Srdivacky 257226633Sdim StmtVisitor<TransferFunctions>::Visit(S); 258226633Sdim 259226633Sdim if (isa<Expr>(S)) { 260226633Sdim val.liveStmts = LV.SSetFact.remove(val.liveStmts, S); 261226633Sdim } 262226633Sdim 263226633Sdim // Mark all children expressions live. 264226633Sdim 265226633Sdim switch (S->getStmtClass()) { 266226633Sdim default: 267226633Sdim break; 268226633Sdim case Stmt::StmtExprClass: { 269226633Sdim // For statement expressions, look through the compound statement. 270226633Sdim S = cast<StmtExpr>(S)->getSubStmt(); 271226633Sdim break; 272226633Sdim } 273226633Sdim case Stmt::CXXMemberCallExprClass: { 274226633Sdim // Include the implicit "this" pointer as being live. 275226633Sdim CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S); 276226633Sdim if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { 277234353Sdim AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj); 278226633Sdim } 279226633Sdim break; 280226633Sdim } 281239462Sdim case Stmt::ObjCMessageExprClass: { 282239462Sdim // In calls to super, include the implicit "self" pointer as being live. 283239462Sdim ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S); 284239462Sdim if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance) 285239462Sdim val.liveDecls = LV.DSetFact.add(val.liveDecls, 286239462Sdim LV.analysisContext.getSelfDecl()); 287239462Sdim break; 288239462Sdim } 289226633Sdim case Stmt::DeclStmtClass: { 290226633Sdim const DeclStmt *DS = cast<DeclStmt>(S); 291226633Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) { 292226633Sdim for (const VariableArrayType* VA = FindVA(VD->getType()); 293276479Sdim VA != nullptr; VA = FindVA(VA->getElementType())) { 294234353Sdim AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr()); 295226633Sdim } 296226633Sdim } 297226633Sdim break; 298226633Sdim } 299234353Sdim case Stmt::PseudoObjectExprClass: { 300234353Sdim // A pseudo-object operation only directly consumes its result 301234353Sdim // expression. 302234353Sdim Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr(); 303234353Sdim if (!child) return; 304234353Sdim if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child)) 305234353Sdim child = OV->getSourceExpr(); 306234353Sdim child = child->IgnoreParens(); 307234353Sdim val.liveStmts = LV.SSetFact.add(val.liveStmts, child); 308234353Sdim return; 309234353Sdim } 310234353Sdim 311226633Sdim // FIXME: These cases eventually shouldn't be needed. 312226633Sdim case Stmt::ExprWithCleanupsClass: { 313226633Sdim S = cast<ExprWithCleanups>(S)->getSubExpr(); 314226633Sdim break; 315226633Sdim } 316226633Sdim case Stmt::CXXBindTemporaryExprClass: { 317226633Sdim S = cast<CXXBindTemporaryExpr>(S)->getSubExpr(); 318226633Sdim break; 319226633Sdim } 320226633Sdim case Stmt::UnaryExprOrTypeTraitExprClass: { 321226633Sdim // No need to unconditionally visit subexpressions. 322226633Sdim return; 323226633Sdim } 324226633Sdim } 325288943Sdim 326288943Sdim for (Stmt *Child : S->children()) { 327288943Sdim if (Child) 328288943Sdim AddLiveStmt(val.liveStmts, LV.SSetFact, Child); 329226633Sdim } 330201361Srdivacky} 331198092Srdivacky 332226633Sdimvoid TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { 333226633Sdim if (B->isAssignmentOp()) { 334226633Sdim if (!LV.killAtAssign) 335226633Sdim return; 336226633Sdim 337226633Sdim // Assigning to a variable? 338226633Sdim Expr *LHS = B->getLHS()->IgnoreParens(); 339226633Sdim 340226633Sdim if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) 341226633Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 342226633Sdim // Assignments to references don't kill the ref's address 343226633Sdim if (VD->getType()->isReferenceType()) 344226633Sdim return; 345198092Srdivacky 346226633Sdim if (!isAlwaysAlive(VD)) { 347226633Sdim // The variable is now dead. 348226633Sdim val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 349226633Sdim } 350193326Sed 351226633Sdim if (observer) 352226633Sdim observer->observerKill(DR); 353226633Sdim } 354226633Sdim } 355193326Sed} 356193326Sed 357226633Sdimvoid TransferFunctions::VisitBlockExpr(BlockExpr *BE) { 358288943Sdim for (const VarDecl *VD : 359288943Sdim LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) { 360226633Sdim if (isAlwaysAlive(VD)) 361226633Sdim continue; 362226633Sdim val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); 363199990Srdivacky } 364199990Srdivacky} 365198092Srdivacky 366226633Sdimvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { 367226633Sdim if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) 368226633Sdim if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) 369226633Sdim val.liveDecls = LV.DSetFact.add(val.liveDecls, D); 370193326Sed} 371193326Sed 372226633Sdimvoid TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 373276479Sdim for (const auto *DI : DS->decls()) 374276479Sdim if (const auto *VD = dyn_cast<VarDecl>(DI)) { 375226633Sdim if (!isAlwaysAlive(VD)) 376226633Sdim val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 377226633Sdim } 378226633Sdim} 379198092Srdivacky 380226633Sdimvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { 381226633Sdim // Kill the iteration variable. 382276479Sdim DeclRefExpr *DR = nullptr; 383276479Sdim const VarDecl *VD = nullptr; 384193326Sed 385226633Sdim Stmt *element = OS->getElement(); 386226633Sdim if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) { 387193326Sed VD = cast<VarDecl>(DS->getSingleDecl()); 388193326Sed } 389226633Sdim else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) { 390226633Sdim VD = cast<VarDecl>(DR->getDecl()); 391226633Sdim } 392226633Sdim 393193326Sed if (VD) { 394226633Sdim val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 395226633Sdim if (observer && DR) 396226633Sdim observer->observerKill(DR); 397193326Sed } 398193326Sed} 399193326Sed 400226633Sdimvoid TransferFunctions:: 401226633SdimVisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) 402226633Sdim{ 403226633Sdim // While sizeof(var) doesn't technically extend the liveness of 'var', it 404226633Sdim // does extent the liveness of metadata if 'var' is a VariableArrayType. 405226633Sdim // We handle that special case here. 406226633Sdim if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) 407226633Sdim return; 408198092Srdivacky 409226633Sdim const Expr *subEx = UE->getArgumentExpr(); 410226633Sdim if (subEx->getType()->isVariableArrayType()) { 411226633Sdim assert(subEx->isLValue()); 412226633Sdim val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens()); 413226633Sdim } 414226633Sdim} 415198092Srdivacky 416226633Sdimvoid TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { 417226633Sdim // Treat ++/-- as a kill. 418226633Sdim // Note we don't actually have to do anything if we don't have an observer, 419226633Sdim // since a ++/-- acts as both a kill and a "use". 420226633Sdim if (!observer) 421226633Sdim return; 422226633Sdim 423226633Sdim switch (UO->getOpcode()) { 424226633Sdim default: 425226633Sdim return; 426212904Sdim case UO_PostInc: 427226633Sdim case UO_PostDec: 428212904Sdim case UO_PreInc: 429212904Sdim case UO_PreDec: 430226633Sdim break; 431193326Sed } 432226633Sdim 433226633Sdim if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) 434226633Sdim if (isa<VarDecl>(DR->getDecl())) { 435226633Sdim // Treat ++/-- as a kill. 436226633Sdim observer->observerKill(DR); 437226633Sdim } 438193326Sed} 439198092Srdivacky 440226633SdimLiveVariables::LivenessValues 441226633SdimLiveVariablesImpl::runOnBlock(const CFGBlock *block, 442226633Sdim LiveVariables::LivenessValues val, 443226633Sdim LiveVariables::Observer *obs) { 444193326Sed 445226633Sdim TransferFunctions TF(*this, val, obs, block); 446226633Sdim 447226633Sdim // Visit the terminator (if any). 448226633Sdim if (const Stmt *term = block->getTerminator()) 449226633Sdim TF.Visit(const_cast<Stmt*>(term)); 450226633Sdim 451226633Sdim // Apply the transfer function for all Stmts in the block. 452226633Sdim for (CFGBlock::const_reverse_iterator it = block->rbegin(), 453226633Sdim ei = block->rend(); it != ei; ++it) { 454226633Sdim const CFGElement &elem = *it; 455239462Sdim 456249423Sdim if (Optional<CFGAutomaticObjDtor> Dtor = 457249423Sdim elem.getAs<CFGAutomaticObjDtor>()) { 458239462Sdim val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl()); 459239462Sdim continue; 460239462Sdim } 461239462Sdim 462249423Sdim if (!elem.getAs<CFGStmt>()) 463226633Sdim continue; 464226633Sdim 465249423Sdim const Stmt *S = elem.castAs<CFGStmt>().getStmt(); 466226633Sdim TF.Visit(const_cast<Stmt*>(S)); 467226633Sdim stmtsToLiveness[S] = val; 468193326Sed } 469226633Sdim return val; 470226633Sdim} 471198092Srdivacky 472226633Sdimvoid LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { 473226633Sdim const CFG *cfg = getImpl(impl).analysisContext.getCFG(); 474226633Sdim for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) 475226633Sdim getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); 476193326Sed} 477193326Sed 478226633SdimLiveVariables::LiveVariables(void *im) : impl(im) {} 479204643Srdivacky 480226633SdimLiveVariables::~LiveVariables() { 481226633Sdim delete (LiveVariablesImpl*) impl; 482193326Sed} 483198092Srdivacky 484226633SdimLiveVariables * 485234353SdimLiveVariables::computeLiveness(AnalysisDeclContext &AC, 486226633Sdim bool killAtAssign) { 487193326Sed 488226633Sdim // No CFG? Bail out. 489226633Sdim CFG *cfg = AC.getCFG(); 490226633Sdim if (!cfg) 491276479Sdim return nullptr; 492193326Sed 493239462Sdim // The analysis currently has scalability issues for very large CFGs. 494239462Sdim // Bail out if it looks too large. 495239462Sdim if (cfg->getNumBlockIDs() > 300000) 496276479Sdim return nullptr; 497239462Sdim 498226633Sdim LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); 499193326Sed 500226633Sdim // Construct the dataflow worklist. Enqueue the exit block as the 501226633Sdim // start of the analysis. 502234353Sdim DataflowWorklist worklist(*cfg, AC); 503226633Sdim llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); 504193326Sed 505226633Sdim // FIXME: we should enqueue using post order. 506226633Sdim for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { 507226633Sdim const CFGBlock *block = *it; 508226633Sdim worklist.enqueueBlock(block); 509226633Sdim 510226633Sdim // FIXME: Scan for DeclRefExprs using in the LHS of an assignment. 511226633Sdim // We need to do this because we lack context in the reverse analysis 512226633Sdim // to determine if a DeclRefExpr appears in such a context, and thus 513226633Sdim // doesn't constitute a "use". 514226633Sdim if (killAtAssign) 515226633Sdim for (CFGBlock::const_iterator bi = block->begin(), be = block->end(); 516226633Sdim bi != be; ++bi) { 517249423Sdim if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) { 518249423Sdim if (const BinaryOperator *BO = 519249423Sdim dyn_cast<BinaryOperator>(cs->getStmt())) { 520226633Sdim if (BO->getOpcode() == BO_Assign) { 521226633Sdim if (const DeclRefExpr *DR = 522226633Sdim dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) { 523226633Sdim LV->inAssignment[DR] = 1; 524226633Sdim } 525226633Sdim } 526226633Sdim } 527226633Sdim } 528226633Sdim } 529226633Sdim } 530226633Sdim 531226633Sdim worklist.sortWorklist(); 532226633Sdim 533226633Sdim while (const CFGBlock *block = worklist.dequeue()) { 534226633Sdim // Determine if the block's end value has changed. If not, we 535226633Sdim // have nothing left to do for this block. 536226633Sdim LivenessValues &prevVal = LV->blocksEndToLiveness[block]; 537226633Sdim 538226633Sdim // Merge the values of all successor blocks. 539226633Sdim LivenessValues val; 540226633Sdim for (CFGBlock::const_succ_iterator it = block->succ_begin(), 541226633Sdim ei = block->succ_end(); it != ei; ++it) { 542226633Sdim if (const CFGBlock *succ = *it) { 543226633Sdim val = LV->merge(val, LV->blocksBeginToLiveness[succ]); 544226633Sdim } 545226633Sdim } 546226633Sdim 547226633Sdim if (!everAnalyzedBlock[block->getBlockID()]) 548226633Sdim everAnalyzedBlock[block->getBlockID()] = true; 549226633Sdim else if (prevVal.equals(val)) 550226633Sdim continue; 551193326Sed 552226633Sdim prevVal = val; 553226633Sdim 554226633Sdim // Update the dataflow value for the start of this block. 555226633Sdim LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); 556226633Sdim 557226633Sdim // Enqueue the value to the predecessors. 558226633Sdim worklist.enqueuePredecessors(block); 559226633Sdim } 560226633Sdim 561226633Sdim return new LiveVariables(LV); 562193326Sed} 563193326Sed 564226633Sdimvoid LiveVariables::dumpBlockLiveness(const SourceManager &M) { 565226633Sdim getImpl(impl).dumpBlockLiveness(M); 566193326Sed} 567193326Sed 568226633Sdimvoid LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { 569226633Sdim std::vector<const CFGBlock *> vec; 570226633Sdim for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator 571226633Sdim it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); 572226633Sdim it != ei; ++it) { 573226633Sdim vec.push_back(it->first); 574226633Sdim } 575276479Sdim std::sort(vec.begin(), vec.end(), [](const CFGBlock *A, const CFGBlock *B) { 576276479Sdim return A->getBlockID() < B->getBlockID(); 577276479Sdim }); 578193326Sed 579226633Sdim std::vector<const VarDecl*> declVec; 580193326Sed 581226633Sdim for (std::vector<const CFGBlock *>::iterator 582226633Sdim it = vec.begin(), ei = vec.end(); it != ei; ++it) { 583226633Sdim llvm::errs() << "\n[ B" << (*it)->getBlockID() 584226633Sdim << " (live variables at block exit) ]\n"; 585226633Sdim 586226633Sdim LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; 587226633Sdim declVec.clear(); 588226633Sdim 589226633Sdim for (llvm::ImmutableSet<const VarDecl *>::iterator si = 590226633Sdim vals.liveDecls.begin(), 591226633Sdim se = vals.liveDecls.end(); si != se; ++si) { 592226633Sdim declVec.push_back(*si); 593226633Sdim } 594276479Sdim 595276479Sdim std::sort(declVec.begin(), declVec.end(), [](const Decl *A, const Decl *B) { 596276479Sdim return A->getLocStart() < B->getLocStart(); 597276479Sdim }); 598276479Sdim 599226633Sdim for (std::vector<const VarDecl*>::iterator di = declVec.begin(), 600226633Sdim de = declVec.end(); di != de; ++di) { 601226633Sdim llvm::errs() << " " << (*di)->getDeclName().getAsString() 602226633Sdim << " <"; 603226633Sdim (*di)->getLocation().dump(M); 604198398Srdivacky llvm::errs() << ">\n"; 605193326Sed } 606226633Sdim } 607226633Sdim llvm::errs() << "\n"; 608198092Srdivacky} 609193326Sed 610226633Sdimconst void *LiveVariables::getTag() { static int x; return &x; } 611226633Sdimconst void *RelaxedLiveVariables::getTag() { static int x; return &x; } 612