LiveVariables.cpp revision 288943
1252492Swblock//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==// 2252492Swblock// 3252492Swblock// The LLVM Compiler Infrastructure 4252492Swblock// 5252492Swblock// This file is distributed under the University of Illinois Open Source 6252492Swblock// License. See LICENSE.TXT for details. 7252492Swblock// 8252492Swblock//===----------------------------------------------------------------------===// 9252492Swblock// 10252492Swblock// This file implements Live Variables analysis for source-level CFGs. 11252492Swblock// 12252492Swblock//===----------------------------------------------------------------------===// 13252492Swblock 14252492Swblock#include "clang/Analysis/Analyses/LiveVariables.h" 15252492Swblock#include "clang/AST/Stmt.h" 16252492Swblock#include "clang/AST/StmtVisitor.h" 17252492Swblock#include "clang/Analysis/Analyses/PostOrderCFGView.h" 18252492Swblock#include "clang/Analysis/AnalysisContext.h" 19252492Swblock#include "clang/Analysis/CFG.h" 20252492Swblock#include "llvm/ADT/DenseMap.h" 21252492Swblock#include "llvm/ADT/PostOrderIterator.h" 22252492Swblock#include "llvm/Support/raw_ostream.h" 23252492Swblock#include <algorithm> 24252492Swblock#include <vector> 25252492Swblock 26252492Swblockusing namespace clang; 27261522Swblock 28252492Swblocknamespace { 29252492Swblock 30252492Swblockclass DataflowWorklist { 31252492Swblock SmallVector<const CFGBlock *, 20> worklist; 32252492Swblock llvm::BitVector enqueuedBlocks; 33252492Swblock PostOrderCFGView *POV; 34252492Swblockpublic: 35252492Swblock DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx) 36252492Swblock : enqueuedBlocks(cfg.getNumBlockIDs()), 37252492Swblock POV(Ctx.getAnalysis<PostOrderCFGView>()) {} 38252492Swblock 39252492Swblock void enqueueBlock(const CFGBlock *block); 40252492Swblock void enqueuePredecessors(const CFGBlock *block); 41252492Swblock 42252492Swblock const CFGBlock *dequeue(); 43252492Swblock 44252492Swblock void sortWorklist(); 45252492Swblock}; 46252492Swblock 47252492Swblock} 48252492Swblock 49252492Swblockvoid DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { 50252492Swblock if (block && !enqueuedBlocks[block->getBlockID()]) { 51252492Swblock enqueuedBlocks[block->getBlockID()] = true; 52252492Swblock worklist.push_back(block); 53252492Swblock } 54252492Swblock} 55252492Swblock 56252492Swblockvoid DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { 57252492Swblock const unsigned OldWorklistSize = worklist.size(); 58252492Swblock for (CFGBlock::const_pred_iterator I = block->pred_begin(), 59252492Swblock E = block->pred_end(); I != E; ++I) { 60252492Swblock enqueueBlock(*I); 61252492Swblock } 62252492Swblock 63252492Swblock if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 64252492Swblock return; 65252492Swblock 66252492Swblock sortWorklist(); 67252492Swblock} 68252492Swblock 69252492Swblockvoid DataflowWorklist::sortWorklist() { 70252492Swblock std::sort(worklist.begin(), worklist.end(), POV->getComparator()); 71252492Swblock} 72252492Swblock 73252492Swblockconst CFGBlock *DataflowWorklist::dequeue() { 74252492Swblock if (worklist.empty()) 75252492Swblock return nullptr; 76252492Swblock const CFGBlock *b = worklist.pop_back_val(); 77252492Swblock enqueuedBlocks[b->getBlockID()] = false; 78252492Swblock return b; 79252492Swblock} 80252492Swblock 81252492Swblocknamespace { 82252492Swblockclass LiveVariablesImpl { 83252492Swblockpublic: 84252492Swblock AnalysisDeclContext &analysisContext; 85252492Swblock llvm::ImmutableSet<const Stmt *>::Factory SSetFact; 86252492Swblock llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; 87252492Swblock llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness; 88252492Swblock llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness; 89252492Swblock llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness; 90252492Swblock llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment; 91252492Swblock const bool killAtAssign; 92252492Swblock 93252492Swblock LiveVariables::LivenessValues 94252492Swblock merge(LiveVariables::LivenessValues valsA, 95252492Swblock LiveVariables::LivenessValues valsB); 96252492Swblock 97252492Swblock LiveVariables::LivenessValues 98252492Swblock runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, 99252492Swblock LiveVariables::Observer *obs = nullptr); 100252492Swblock 101252492Swblock void dumpBlockLiveness(const SourceManager& M); 102252492Swblock 103252492Swblock LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) 104252492Swblock : analysisContext(ac), 105252492Swblock SSetFact(false), // Do not canonicalize ImmutableSets by default. 106252492Swblock DSetFact(false), // This is a *major* performance win. 107252492Swblock killAtAssign(KillAtAssign) {} 108252492Swblock}; 109252492Swblock} 110252492Swblock 111252492Swblockstatic LiveVariablesImpl &getImpl(void *x) { 112252492Swblock return *((LiveVariablesImpl *) x); 113252492Swblock} 114252492Swblock 115252492Swblock//===----------------------------------------------------------------------===// 116252492Swblock// Operations and queries on LivenessValues. 117252492Swblock//===----------------------------------------------------------------------===// 118252492Swblock 119252492Swblockbool LiveVariables::LivenessValues::isLive(const Stmt *S) const { 120252492Swblock return liveStmts.contains(S); 121252492Swblock} 122252492Swblock 123252492Swblockbool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { 124252492Swblock return liveDecls.contains(D); 125252492Swblock} 126252492Swblock 127252492Swblocknamespace { 128252492Swblock template <typename SET> 129252492Swblock SET mergeSets(SET A, SET B) { 130252492Swblock if (A.isEmpty()) 131252492Swblock return B; 132252492Swblock 133252492Swblock for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { 134252492Swblock A = A.add(*it); 135252492Swblock } 136252492Swblock return A; 137252492Swblock } 138252492Swblock} 139252492Swblock 140252492Swblockvoid LiveVariables::Observer::anchor() { } 141252492Swblock 142252492SwblockLiveVariables::LivenessValues 143252492SwblockLiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, 144252492Swblock LiveVariables::LivenessValues valsB) { 145252492Swblock 146252492Swblock llvm::ImmutableSetRef<const Stmt *> 147252492Swblock SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()), 148252492Swblock SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()); 149252492Swblock 150252586Swblock 151252586Swblock llvm::ImmutableSetRef<const VarDecl *> 152252492Swblock DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), 153252492Swblock DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); 154252492Swblock 155252492Swblock 156252492Swblock SSetRefA = mergeSets(SSetRefA, SSetRefB); 157252492Swblock DSetRefA = mergeSets(DSetRefA, DSetRefB); 158252492Swblock 159252492Swblock // asImmutableSet() canonicalizes the tree, allowing us to do an easy 160252492Swblock // comparison afterwards. 161252492Swblock return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), 162252492Swblock DSetRefA.asImmutableSet()); 163252492Swblock} 164252492Swblock 165252492Swblockbool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { 166252492Swblock return liveStmts == V.liveStmts && liveDecls == V.liveDecls; 167252492Swblock} 168252492Swblock 169252492Swblock//===----------------------------------------------------------------------===// 170252492Swblock// Query methods. 171252492Swblock//===----------------------------------------------------------------------===// 172252492Swblock 173252492Swblockstatic bool isAlwaysAlive(const VarDecl *D) { 174252492Swblock return D->hasGlobalStorage(); 175252492Swblock} 176252492Swblock 177252492Swblockbool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { 178252492Swblock return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); 179252492Swblock} 180252492Swblock 181252492Swblockbool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { 182252492Swblock return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); 183252492Swblock} 184252586Swblock 185252492Swblockbool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) { 186252586Swblock return getImpl(impl).stmtsToLiveness[Loc].isLive(S); 187252492Swblock} 188252586Swblock 189252586Swblock//===----------------------------------------------------------------------===// 190252492Swblock// Dataflow computation. 191252492Swblock//===----------------------------------------------------------------------===// 192252492Swblock 193261522Swblocknamespace { 194261522Swblockclass TransferFunctions : public StmtVisitor<TransferFunctions> { 195261522Swblock LiveVariablesImpl &LV; 196261522Swblock LiveVariables::LivenessValues &val; 197252492Swblock LiveVariables::Observer *observer; 198252492Swblock const CFGBlock *currentBlock; 199252492Swblockpublic: 200252492Swblock TransferFunctions(LiveVariablesImpl &im, 201261522Swblock LiveVariables::LivenessValues &Val, 202261522Swblock LiveVariables::Observer *Observer, 203261522Swblock const CFGBlock *CurrentBlock) 204261522Swblock : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} 205252492Swblock 206252492Swblock void VisitBinaryOperator(BinaryOperator *BO); 207252492Swblock void VisitBlockExpr(BlockExpr *BE); 208252492Swblock void VisitDeclRefExpr(DeclRefExpr *DR); 209252492Swblock void VisitDeclStmt(DeclStmt *DS); 210252492Swblock void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); 211252492Swblock void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); 212252492Swblock void VisitUnaryOperator(UnaryOperator *UO); 213252492Swblock void Visit(Stmt *S); 214252492Swblock}; 215252492Swblock} 216252492Swblock 217252492Swblockstatic const VariableArrayType *FindVA(QualType Ty) { 218252492Swblock const Type *ty = Ty.getTypePtr(); 219252492Swblock while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) { 220252492Swblock if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT)) 221252492Swblock if (VAT->getSizeExpr()) 222252492Swblock return VAT; 223252492Swblock 224252492Swblock ty = VT->getElementType().getTypePtr(); 225252492Swblock } 226252492Swblock 227252492Swblock return nullptr; 228252492Swblock} 229252492Swblock 230252492Swblockstatic const Stmt *LookThroughStmt(const Stmt *S) { 231252492Swblock while (S) { 232252492Swblock if (const Expr *Ex = dyn_cast<Expr>(S)) 233252492Swblock S = Ex->IgnoreParens(); 234252492Swblock if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(S)) { 235252492Swblock S = EWC->getSubExpr(); 236252492Swblock continue; 237252492Swblock } 238252492Swblock if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) { 239252492Swblock S = OVE->getSourceExpr(); 240252492Swblock continue; 241252492Swblock } 242252492Swblock break; 243252492Swblock } 244267293Sjoel return S; 245267293Sjoel} 246 247static void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set, 248 llvm::ImmutableSet<const Stmt *>::Factory &F, 249 const Stmt *S) { 250 Set = F.add(Set, LookThroughStmt(S)); 251} 252 253void TransferFunctions::Visit(Stmt *S) { 254 if (observer) 255 observer->observeStmt(S, currentBlock, val); 256 257 StmtVisitor<TransferFunctions>::Visit(S); 258 259 if (isa<Expr>(S)) { 260 val.liveStmts = LV.SSetFact.remove(val.liveStmts, S); 261 } 262 263 // Mark all children expressions live. 264 265 switch (S->getStmtClass()) { 266 default: 267 break; 268 case Stmt::StmtExprClass: { 269 // For statement expressions, look through the compound statement. 270 S = cast<StmtExpr>(S)->getSubStmt(); 271 break; 272 } 273 case Stmt::CXXMemberCallExprClass: { 274 // Include the implicit "this" pointer as being live. 275 CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S); 276 if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { 277 AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj); 278 } 279 break; 280 } 281 case Stmt::ObjCMessageExprClass: { 282 // In calls to super, include the implicit "self" pointer as being live. 283 ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S); 284 if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance) 285 val.liveDecls = LV.DSetFact.add(val.liveDecls, 286 LV.analysisContext.getSelfDecl()); 287 break; 288 } 289 case Stmt::DeclStmtClass: { 290 const DeclStmt *DS = cast<DeclStmt>(S); 291 if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) { 292 for (const VariableArrayType* VA = FindVA(VD->getType()); 293 VA != nullptr; VA = FindVA(VA->getElementType())) { 294 AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr()); 295 } 296 } 297 break; 298 } 299 case Stmt::PseudoObjectExprClass: { 300 // A pseudo-object operation only directly consumes its result 301 // expression. 302 Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr(); 303 if (!child) return; 304 if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child)) 305 child = OV->getSourceExpr(); 306 child = child->IgnoreParens(); 307 val.liveStmts = LV.SSetFact.add(val.liveStmts, child); 308 return; 309 } 310 311 // FIXME: These cases eventually shouldn't be needed. 312 case Stmt::ExprWithCleanupsClass: { 313 S = cast<ExprWithCleanups>(S)->getSubExpr(); 314 break; 315 } 316 case Stmt::CXXBindTemporaryExprClass: { 317 S = cast<CXXBindTemporaryExpr>(S)->getSubExpr(); 318 break; 319 } 320 case Stmt::UnaryExprOrTypeTraitExprClass: { 321 // No need to unconditionally visit subexpressions. 322 return; 323 } 324 } 325 326 for (Stmt *Child : S->children()) { 327 if (Child) 328 AddLiveStmt(val.liveStmts, LV.SSetFact, Child); 329 } 330} 331 332void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { 333 if (B->isAssignmentOp()) { 334 if (!LV.killAtAssign) 335 return; 336 337 // Assigning to a variable? 338 Expr *LHS = B->getLHS()->IgnoreParens(); 339 340 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) 341 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 342 // Assignments to references don't kill the ref's address 343 if (VD->getType()->isReferenceType()) 344 return; 345 346 if (!isAlwaysAlive(VD)) { 347 // The variable is now dead. 348 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 349 } 350 351 if (observer) 352 observer->observerKill(DR); 353 } 354 } 355} 356 357void TransferFunctions::VisitBlockExpr(BlockExpr *BE) { 358 for (const VarDecl *VD : 359 LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) { 360 if (isAlwaysAlive(VD)) 361 continue; 362 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); 363 } 364} 365 366void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { 367 if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) 368 if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) 369 val.liveDecls = LV.DSetFact.add(val.liveDecls, D); 370} 371 372void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 373 for (const auto *DI : DS->decls()) 374 if (const auto *VD = dyn_cast<VarDecl>(DI)) { 375 if (!isAlwaysAlive(VD)) 376 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 377 } 378} 379 380void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { 381 // Kill the iteration variable. 382 DeclRefExpr *DR = nullptr; 383 const VarDecl *VD = nullptr; 384 385 Stmt *element = OS->getElement(); 386 if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) { 387 VD = cast<VarDecl>(DS->getSingleDecl()); 388 } 389 else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) { 390 VD = cast<VarDecl>(DR->getDecl()); 391 } 392 393 if (VD) { 394 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 395 if (observer && DR) 396 observer->observerKill(DR); 397 } 398} 399 400void TransferFunctions:: 401VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) 402{ 403 // While sizeof(var) doesn't technically extend the liveness of 'var', it 404 // does extent the liveness of metadata if 'var' is a VariableArrayType. 405 // We handle that special case here. 406 if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) 407 return; 408 409 const Expr *subEx = UE->getArgumentExpr(); 410 if (subEx->getType()->isVariableArrayType()) { 411 assert(subEx->isLValue()); 412 val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens()); 413 } 414} 415 416void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { 417 // Treat ++/-- as a kill. 418 // Note we don't actually have to do anything if we don't have an observer, 419 // since a ++/-- acts as both a kill and a "use". 420 if (!observer) 421 return; 422 423 switch (UO->getOpcode()) { 424 default: 425 return; 426 case UO_PostInc: 427 case UO_PostDec: 428 case UO_PreInc: 429 case UO_PreDec: 430 break; 431 } 432 433 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) 434 if (isa<VarDecl>(DR->getDecl())) { 435 // Treat ++/-- as a kill. 436 observer->observerKill(DR); 437 } 438} 439 440LiveVariables::LivenessValues 441LiveVariablesImpl::runOnBlock(const CFGBlock *block, 442 LiveVariables::LivenessValues val, 443 LiveVariables::Observer *obs) { 444 445 TransferFunctions TF(*this, val, obs, block); 446 447 // Visit the terminator (if any). 448 if (const Stmt *term = block->getTerminator()) 449 TF.Visit(const_cast<Stmt*>(term)); 450 451 // Apply the transfer function for all Stmts in the block. 452 for (CFGBlock::const_reverse_iterator it = block->rbegin(), 453 ei = block->rend(); it != ei; ++it) { 454 const CFGElement &elem = *it; 455 456 if (Optional<CFGAutomaticObjDtor> Dtor = 457 elem.getAs<CFGAutomaticObjDtor>()) { 458 val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl()); 459 continue; 460 } 461 462 if (!elem.getAs<CFGStmt>()) 463 continue; 464 465 const Stmt *S = elem.castAs<CFGStmt>().getStmt(); 466 TF.Visit(const_cast<Stmt*>(S)); 467 stmtsToLiveness[S] = val; 468 } 469 return val; 470} 471 472void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { 473 const CFG *cfg = getImpl(impl).analysisContext.getCFG(); 474 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) 475 getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); 476} 477 478LiveVariables::LiveVariables(void *im) : impl(im) {} 479 480LiveVariables::~LiveVariables() { 481 delete (LiveVariablesImpl*) impl; 482} 483 484LiveVariables * 485LiveVariables::computeLiveness(AnalysisDeclContext &AC, 486 bool killAtAssign) { 487 488 // No CFG? Bail out. 489 CFG *cfg = AC.getCFG(); 490 if (!cfg) 491 return nullptr; 492 493 // The analysis currently has scalability issues for very large CFGs. 494 // Bail out if it looks too large. 495 if (cfg->getNumBlockIDs() > 300000) 496 return nullptr; 497 498 LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); 499 500 // Construct the dataflow worklist. Enqueue the exit block as the 501 // start of the analysis. 502 DataflowWorklist worklist(*cfg, AC); 503 llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); 504 505 // FIXME: we should enqueue using post order. 506 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { 507 const CFGBlock *block = *it; 508 worklist.enqueueBlock(block); 509 510 // FIXME: Scan for DeclRefExprs using in the LHS of an assignment. 511 // We need to do this because we lack context in the reverse analysis 512 // to determine if a DeclRefExpr appears in such a context, and thus 513 // doesn't constitute a "use". 514 if (killAtAssign) 515 for (CFGBlock::const_iterator bi = block->begin(), be = block->end(); 516 bi != be; ++bi) { 517 if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) { 518 if (const BinaryOperator *BO = 519 dyn_cast<BinaryOperator>(cs->getStmt())) { 520 if (BO->getOpcode() == BO_Assign) { 521 if (const DeclRefExpr *DR = 522 dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) { 523 LV->inAssignment[DR] = 1; 524 } 525 } 526 } 527 } 528 } 529 } 530 531 worklist.sortWorklist(); 532 533 while (const CFGBlock *block = worklist.dequeue()) { 534 // Determine if the block's end value has changed. If not, we 535 // have nothing left to do for this block. 536 LivenessValues &prevVal = LV->blocksEndToLiveness[block]; 537 538 // Merge the values of all successor blocks. 539 LivenessValues val; 540 for (CFGBlock::const_succ_iterator it = block->succ_begin(), 541 ei = block->succ_end(); it != ei; ++it) { 542 if (const CFGBlock *succ = *it) { 543 val = LV->merge(val, LV->blocksBeginToLiveness[succ]); 544 } 545 } 546 547 if (!everAnalyzedBlock[block->getBlockID()]) 548 everAnalyzedBlock[block->getBlockID()] = true; 549 else if (prevVal.equals(val)) 550 continue; 551 552 prevVal = val; 553 554 // Update the dataflow value for the start of this block. 555 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); 556 557 // Enqueue the value to the predecessors. 558 worklist.enqueuePredecessors(block); 559 } 560 561 return new LiveVariables(LV); 562} 563 564void LiveVariables::dumpBlockLiveness(const SourceManager &M) { 565 getImpl(impl).dumpBlockLiveness(M); 566} 567 568void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { 569 std::vector<const CFGBlock *> vec; 570 for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator 571 it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); 572 it != ei; ++it) { 573 vec.push_back(it->first); 574 } 575 std::sort(vec.begin(), vec.end(), [](const CFGBlock *A, const CFGBlock *B) { 576 return A->getBlockID() < B->getBlockID(); 577 }); 578 579 std::vector<const VarDecl*> declVec; 580 581 for (std::vector<const CFGBlock *>::iterator 582 it = vec.begin(), ei = vec.end(); it != ei; ++it) { 583 llvm::errs() << "\n[ B" << (*it)->getBlockID() 584 << " (live variables at block exit) ]\n"; 585 586 LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; 587 declVec.clear(); 588 589 for (llvm::ImmutableSet<const VarDecl *>::iterator si = 590 vals.liveDecls.begin(), 591 se = vals.liveDecls.end(); si != se; ++si) { 592 declVec.push_back(*si); 593 } 594 595 std::sort(declVec.begin(), declVec.end(), [](const Decl *A, const Decl *B) { 596 return A->getLocStart() < B->getLocStart(); 597 }); 598 599 for (std::vector<const VarDecl*>::iterator di = declVec.begin(), 600 de = declVec.end(); di != de; ++di) { 601 llvm::errs() << " " << (*di)->getDeclName().getAsString() 602 << " <"; 603 (*di)->getLocation().dump(M); 604 llvm::errs() << ">\n"; 605 } 606 } 607 llvm::errs() << "\n"; 608} 609 610const void *LiveVariables::getTag() { static int x; return &x; } 611const void *RelaxedLiveVariables::getTag() { static int x; return &x; } 612