1 //=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements Live Variables analysis for source-level CFGs. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "clang/Analysis/Analyses/LiveVariables.h" 14 #include "clang/AST/Stmt.h" 15 #include "clang/AST/StmtVisitor.h" 16 #include "clang/Analysis/AnalysisDeclContext.h" 17 #include "clang/Analysis/CFG.h" 18 #include "clang/Analysis/FlowSensitive/DataflowWorklist.h" 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/Support/raw_ostream.h" 21 #include <algorithm> 22 #include <optional> 23 #include <vector> 24 25 using namespace clang; 26 27 namespace { 28 class LiveVariablesImpl { 29 public: 30 AnalysisDeclContext &analysisContext; 31 llvm::ImmutableSet<const Expr *>::Factory ESetFact; 32 llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; 33 llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact; 34 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness; 35 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness; 36 llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness; 37 llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment; 38 const bool killAtAssign; 39 40 LiveVariables::LivenessValues 41 merge(LiveVariables::LivenessValues valsA, 42 LiveVariables::LivenessValues valsB); 43 44 LiveVariables::LivenessValues 45 runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, 46 LiveVariables::Observer *obs = nullptr); 47 48 void dumpBlockLiveness(const SourceManager& M); 49 void dumpExprLiveness(const SourceManager& M); 50 51 LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) 52 : analysisContext(ac), 53 ESetFact(false), // Do not canonicalize ImmutableSets by default. 54 DSetFact(false), // This is a *major* performance win. 55 BSetFact(false), killAtAssign(KillAtAssign) {} 56 }; 57 } // namespace 58 59 static LiveVariablesImpl &getImpl(void *x) { 60 return *((LiveVariablesImpl *) x); 61 } 62 63 //===----------------------------------------------------------------------===// 64 // Operations and queries on LivenessValues. 65 //===----------------------------------------------------------------------===// 66 67 bool LiveVariables::LivenessValues::isLive(const Expr *E) const { 68 return liveExprs.contains(E); 69 } 70 71 bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { 72 if (const auto *DD = dyn_cast<DecompositionDecl>(D)) { 73 bool alive = false; 74 for (const BindingDecl *BD : DD->bindings()) 75 alive |= liveBindings.contains(BD); 76 77 // Note: the only known case this condition is necessary, is when a bindig 78 // to a tuple-like structure is created. The HoldingVar initializers have a 79 // DeclRefExpr to the DecompositionDecl. 80 alive |= liveDecls.contains(DD); 81 return alive; 82 } 83 return liveDecls.contains(D); 84 } 85 86 namespace { 87 template <typename SET> 88 SET mergeSets(SET A, SET B) { 89 if (A.isEmpty()) 90 return B; 91 92 for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { 93 A = A.add(*it); 94 } 95 return A; 96 } 97 } // namespace 98 99 void LiveVariables::Observer::anchor() { } 100 101 LiveVariables::LivenessValues 102 LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, 103 LiveVariables::LivenessValues valsB) { 104 105 llvm::ImmutableSetRef<const Expr *> SSetRefA( 106 valsA.liveExprs.getRootWithoutRetain(), ESetFact.getTreeFactory()), 107 SSetRefB(valsB.liveExprs.getRootWithoutRetain(), 108 ESetFact.getTreeFactory()); 109 110 llvm::ImmutableSetRef<const VarDecl *> 111 DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), 112 DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); 113 114 llvm::ImmutableSetRef<const BindingDecl *> 115 BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()), 116 BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()); 117 118 SSetRefA = mergeSets(SSetRefA, SSetRefB); 119 DSetRefA = mergeSets(DSetRefA, DSetRefB); 120 BSetRefA = mergeSets(BSetRefA, BSetRefB); 121 122 // asImmutableSet() canonicalizes the tree, allowing us to do an easy 123 // comparison afterwards. 124 return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), 125 DSetRefA.asImmutableSet(), 126 BSetRefA.asImmutableSet()); 127 } 128 129 bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { 130 return liveExprs == V.liveExprs && liveDecls == V.liveDecls; 131 } 132 133 //===----------------------------------------------------------------------===// 134 // Query methods. 135 //===----------------------------------------------------------------------===// 136 137 static bool isAlwaysAlive(const VarDecl *D) { 138 return D->hasGlobalStorage(); 139 } 140 141 bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { 142 return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); 143 } 144 145 bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { 146 return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); 147 } 148 149 bool LiveVariables::isLive(const Stmt *Loc, const Expr *Val) { 150 return getImpl(impl).stmtsToLiveness[Loc].isLive(Val); 151 } 152 153 //===----------------------------------------------------------------------===// 154 // Dataflow computation. 155 //===----------------------------------------------------------------------===// 156 157 namespace { 158 class TransferFunctions : public StmtVisitor<TransferFunctions> { 159 LiveVariablesImpl &LV; 160 LiveVariables::LivenessValues &val; 161 LiveVariables::Observer *observer; 162 const CFGBlock *currentBlock; 163 public: 164 TransferFunctions(LiveVariablesImpl &im, 165 LiveVariables::LivenessValues &Val, 166 LiveVariables::Observer *Observer, 167 const CFGBlock *CurrentBlock) 168 : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} 169 170 void VisitBinaryOperator(BinaryOperator *BO); 171 void VisitBlockExpr(BlockExpr *BE); 172 void VisitDeclRefExpr(DeclRefExpr *DR); 173 void VisitDeclStmt(DeclStmt *DS); 174 void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); 175 void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); 176 void VisitUnaryOperator(UnaryOperator *UO); 177 void Visit(Stmt *S); 178 }; 179 } // namespace 180 181 static const VariableArrayType *FindVA(QualType Ty) { 182 const Type *ty = Ty.getTypePtr(); 183 while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) { 184 if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT)) 185 if (VAT->getSizeExpr()) 186 return VAT; 187 188 ty = VT->getElementType().getTypePtr(); 189 } 190 191 return nullptr; 192 } 193 194 static const Expr *LookThroughExpr(const Expr *E) { 195 while (E) { 196 if (const Expr *Ex = dyn_cast<Expr>(E)) 197 E = Ex->IgnoreParens(); 198 if (const FullExpr *FE = dyn_cast<FullExpr>(E)) { 199 E = FE->getSubExpr(); 200 continue; 201 } 202 if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(E)) { 203 E = OVE->getSourceExpr(); 204 continue; 205 } 206 break; 207 } 208 return E; 209 } 210 211 static void AddLiveExpr(llvm::ImmutableSet<const Expr *> &Set, 212 llvm::ImmutableSet<const Expr *>::Factory &F, 213 const Expr *E) { 214 Set = F.add(Set, LookThroughExpr(E)); 215 } 216 217 /// Add as a live expression all individual conditions in a logical expression. 218 /// For example, for the expression: 219 /// "(a < b) || (c && d && ((e || f) != (g && h)))" 220 /// the following expressions will be added as live: 221 /// "a < b", "c", "d", "((e || f) != (g && h))" 222 static void AddAllConditionalTerms(llvm::ImmutableSet<const Expr *> &Set, 223 llvm::ImmutableSet<const Expr *>::Factory &F, 224 const Expr *Cond) { 225 AddLiveExpr(Set, F, Cond); 226 if (auto const *BO = dyn_cast<BinaryOperator>(Cond->IgnoreParens()); 227 BO && BO->isLogicalOp()) { 228 AddAllConditionalTerms(Set, F, BO->getLHS()); 229 AddAllConditionalTerms(Set, F, BO->getRHS()); 230 } 231 } 232 233 void TransferFunctions::Visit(Stmt *S) { 234 if (observer) 235 observer->observeStmt(S, currentBlock, val); 236 237 StmtVisitor<TransferFunctions>::Visit(S); 238 239 if (const auto *E = dyn_cast<Expr>(S)) { 240 val.liveExprs = LV.ESetFact.remove(val.liveExprs, E); 241 } 242 243 // Mark all children expressions live. 244 245 switch (S->getStmtClass()) { 246 default: 247 break; 248 case Stmt::StmtExprClass: { 249 // For statement expressions, look through the compound statement. 250 S = cast<StmtExpr>(S)->getSubStmt(); 251 break; 252 } 253 case Stmt::CXXMemberCallExprClass: { 254 // Include the implicit "this" pointer as being live. 255 CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S); 256 if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { 257 AddLiveExpr(val.liveExprs, LV.ESetFact, ImplicitObj); 258 } 259 break; 260 } 261 case Stmt::ObjCMessageExprClass: { 262 // In calls to super, include the implicit "self" pointer as being live. 263 ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S); 264 if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance) 265 val.liveDecls = LV.DSetFact.add(val.liveDecls, 266 LV.analysisContext.getSelfDecl()); 267 break; 268 } 269 case Stmt::DeclStmtClass: { 270 const DeclStmt *DS = cast<DeclStmt>(S); 271 if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) { 272 for (const VariableArrayType* VA = FindVA(VD->getType()); 273 VA != nullptr; VA = FindVA(VA->getElementType())) { 274 AddLiveExpr(val.liveExprs, LV.ESetFact, VA->getSizeExpr()); 275 } 276 } 277 break; 278 } 279 case Stmt::PseudoObjectExprClass: { 280 // A pseudo-object operation only directly consumes its result 281 // expression. 282 Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr(); 283 if (!child) return; 284 if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child)) 285 child = OV->getSourceExpr(); 286 child = child->IgnoreParens(); 287 val.liveExprs = LV.ESetFact.add(val.liveExprs, child); 288 return; 289 } 290 291 // FIXME: These cases eventually shouldn't be needed. 292 case Stmt::ExprWithCleanupsClass: { 293 S = cast<ExprWithCleanups>(S)->getSubExpr(); 294 break; 295 } 296 case Stmt::CXXBindTemporaryExprClass: { 297 S = cast<CXXBindTemporaryExpr>(S)->getSubExpr(); 298 break; 299 } 300 case Stmt::UnaryExprOrTypeTraitExprClass: { 301 // No need to unconditionally visit subexpressions. 302 return; 303 } 304 case Stmt::IfStmtClass: { 305 // If one of the branches is an expression rather than a compound 306 // statement, it will be bad if we mark it as live at the terminator 307 // of the if-statement (i.e., immediately after the condition expression). 308 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<IfStmt>(S)->getCond()); 309 return; 310 } 311 case Stmt::WhileStmtClass: { 312 // If the loop body is an expression rather than a compound statement, 313 // it will be bad if we mark it as live at the terminator of the loop 314 // (i.e., immediately after the condition expression). 315 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<WhileStmt>(S)->getCond()); 316 return; 317 } 318 case Stmt::DoStmtClass: { 319 // If the loop body is an expression rather than a compound statement, 320 // it will be bad if we mark it as live at the terminator of the loop 321 // (i.e., immediately after the condition expression). 322 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<DoStmt>(S)->getCond()); 323 return; 324 } 325 case Stmt::ForStmtClass: { 326 // If the loop body is an expression rather than a compound statement, 327 // it will be bad if we mark it as live at the terminator of the loop 328 // (i.e., immediately after the condition expression). 329 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<ForStmt>(S)->getCond()); 330 return; 331 } 332 case Stmt::ConditionalOperatorClass: { 333 // Keep not only direct children alive, but also all the short-circuited 334 // parts of the condition. Short-circuiting evaluation may cause the 335 // conditional operator evaluation to skip the evaluation of the entire 336 // condtion expression, so the value of the entire condition expression is 337 // never computed. 338 // 339 // This makes a difference when we compare exploded nodes coming from true 340 // and false expressions with no side effects: the only difference in the 341 // state is the value of (part of) the condition. 342 // 343 // BinaryConditionalOperatorClass ('x ?: y') is not affected because it 344 // explicitly calculates the value of the entire condition expression (to 345 // possibly use as a value for the "true expr") even if it is 346 // short-circuited. 347 auto const *CO = cast<ConditionalOperator>(S); 348 AddAllConditionalTerms(val.liveExprs, LV.ESetFact, CO->getCond()); 349 AddLiveExpr(val.liveExprs, LV.ESetFact, CO->getTrueExpr()); 350 AddLiveExpr(val.liveExprs, LV.ESetFact, CO->getFalseExpr()); 351 return; 352 } 353 } 354 355 // HACK + FIXME: What is this? One could only guess that this is an attempt to 356 // fish for live values, for example, arguments from a call expression. 357 // Maybe we could take inspiration from UninitializedVariable analysis? 358 for (Stmt *Child : S->children()) { 359 if (const auto *E = dyn_cast_or_null<Expr>(Child)) 360 AddLiveExpr(val.liveExprs, LV.ESetFact, E); 361 } 362 } 363 364 static bool writeShouldKill(const VarDecl *VD) { 365 return VD && !VD->getType()->isReferenceType() && 366 !isAlwaysAlive(VD); 367 } 368 369 void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { 370 if (LV.killAtAssign && B->getOpcode() == BO_Assign) { 371 if (const auto *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParens())) { 372 LV.inAssignment[DR] = 1; 373 } 374 } 375 if (B->isAssignmentOp()) { 376 if (!LV.killAtAssign) 377 return; 378 379 // Assigning to a variable? 380 Expr *LHS = B->getLHS()->IgnoreParens(); 381 382 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) { 383 const Decl* D = DR->getDecl(); 384 bool Killed = false; 385 386 if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) { 387 Killed = !BD->getType()->isReferenceType(); 388 if (Killed) { 389 if (const auto *HV = BD->getHoldingVar()) 390 val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV); 391 392 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); 393 } 394 } else if (const auto *VD = dyn_cast<VarDecl>(D)) { 395 Killed = writeShouldKill(VD); 396 if (Killed) 397 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 398 399 } 400 401 if (Killed && observer) 402 observer->observerKill(DR); 403 } 404 } 405 } 406 407 void TransferFunctions::VisitBlockExpr(BlockExpr *BE) { 408 for (const VarDecl *VD : 409 LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) { 410 if (isAlwaysAlive(VD)) 411 continue; 412 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); 413 } 414 } 415 416 void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { 417 const Decl* D = DR->getDecl(); 418 bool InAssignment = LV.inAssignment[DR]; 419 if (const auto *BD = dyn_cast<BindingDecl>(D)) { 420 if (!InAssignment) { 421 if (const auto *HV = BD->getHoldingVar()) 422 val.liveDecls = LV.DSetFact.add(val.liveDecls, HV); 423 424 val.liveBindings = LV.BSetFact.add(val.liveBindings, BD); 425 } 426 } else if (const auto *VD = dyn_cast<VarDecl>(D)) { 427 if (!InAssignment && !isAlwaysAlive(VD)) 428 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); 429 } 430 } 431 432 void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 433 for (const auto *DI : DS->decls()) { 434 if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) { 435 for (const auto *BD : DD->bindings()) { 436 if (const auto *HV = BD->getHoldingVar()) 437 val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV); 438 439 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); 440 } 441 442 // When a bindig to a tuple-like structure is created, the HoldingVar 443 // initializers have a DeclRefExpr to the DecompositionDecl. 444 val.liveDecls = LV.DSetFact.remove(val.liveDecls, DD); 445 } else if (const auto *VD = dyn_cast<VarDecl>(DI)) { 446 if (!isAlwaysAlive(VD)) 447 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 448 } 449 } 450 } 451 452 void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { 453 // Kill the iteration variable. 454 DeclRefExpr *DR = nullptr; 455 const VarDecl *VD = nullptr; 456 457 Stmt *element = OS->getElement(); 458 if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) { 459 VD = cast<VarDecl>(DS->getSingleDecl()); 460 } 461 else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) { 462 VD = cast<VarDecl>(DR->getDecl()); 463 } 464 465 if (VD) { 466 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 467 if (observer && DR) 468 observer->observerKill(DR); 469 } 470 } 471 472 void TransferFunctions:: 473 VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) 474 { 475 // While sizeof(var) doesn't technically extend the liveness of 'var', it 476 // does extent the liveness of metadata if 'var' is a VariableArrayType. 477 // We handle that special case here. 478 if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) 479 return; 480 481 const Expr *subEx = UE->getArgumentExpr(); 482 if (subEx->getType()->isVariableArrayType()) { 483 assert(subEx->isLValue()); 484 val.liveExprs = LV.ESetFact.add(val.liveExprs, subEx->IgnoreParens()); 485 } 486 } 487 488 void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { 489 // Treat ++/-- as a kill. 490 // Note we don't actually have to do anything if we don't have an observer, 491 // since a ++/-- acts as both a kill and a "use". 492 if (!observer) 493 return; 494 495 switch (UO->getOpcode()) { 496 default: 497 return; 498 case UO_PostInc: 499 case UO_PostDec: 500 case UO_PreInc: 501 case UO_PreDec: 502 break; 503 } 504 505 if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) { 506 const Decl *D = DR->getDecl(); 507 if (isa<VarDecl>(D) || isa<BindingDecl>(D)) { 508 // Treat ++/-- as a kill. 509 observer->observerKill(DR); 510 } 511 } 512 } 513 514 LiveVariables::LivenessValues 515 LiveVariablesImpl::runOnBlock(const CFGBlock *block, 516 LiveVariables::LivenessValues val, 517 LiveVariables::Observer *obs) { 518 519 TransferFunctions TF(*this, val, obs, block); 520 521 // Visit the terminator (if any). 522 if (const Stmt *term = block->getTerminatorStmt()) 523 TF.Visit(const_cast<Stmt*>(term)); 524 525 // Apply the transfer function for all Stmts in the block. 526 for (CFGBlock::const_reverse_iterator it = block->rbegin(), 527 ei = block->rend(); it != ei; ++it) { 528 const CFGElement &elem = *it; 529 530 if (std::optional<CFGAutomaticObjDtor> Dtor = 531 elem.getAs<CFGAutomaticObjDtor>()) { 532 val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl()); 533 continue; 534 } 535 536 if (!elem.getAs<CFGStmt>()) 537 continue; 538 539 const Stmt *S = elem.castAs<CFGStmt>().getStmt(); 540 TF.Visit(const_cast<Stmt*>(S)); 541 stmtsToLiveness[S] = val; 542 } 543 return val; 544 } 545 546 void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { 547 const CFG *cfg = getImpl(impl).analysisContext.getCFG(); 548 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) 549 getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); 550 } 551 552 LiveVariables::LiveVariables(void *im) : impl(im) {} 553 554 LiveVariables::~LiveVariables() { 555 delete (LiveVariablesImpl*) impl; 556 } 557 558 std::unique_ptr<LiveVariables> 559 LiveVariables::computeLiveness(AnalysisDeclContext &AC, bool killAtAssign) { 560 561 // No CFG? Bail out. 562 CFG *cfg = AC.getCFG(); 563 if (!cfg) 564 return nullptr; 565 566 // The analysis currently has scalability issues for very large CFGs. 567 // Bail out if it looks too large. 568 if (cfg->getNumBlockIDs() > 300000) 569 return nullptr; 570 571 LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); 572 573 // Construct the dataflow worklist. Enqueue the exit block as the 574 // start of the analysis. 575 BackwardDataflowWorklist worklist(*cfg, AC); 576 llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); 577 578 // FIXME: we should enqueue using post order. 579 for (const CFGBlock *B : cfg->nodes()) { 580 worklist.enqueueBlock(B); 581 } 582 583 while (const CFGBlock *block = worklist.dequeue()) { 584 // Determine if the block's end value has changed. If not, we 585 // have nothing left to do for this block. 586 LivenessValues &prevVal = LV->blocksEndToLiveness[block]; 587 588 // Merge the values of all successor blocks. 589 LivenessValues val; 590 for (CFGBlock::const_succ_iterator it = block->succ_begin(), 591 ei = block->succ_end(); it != ei; ++it) { 592 if (const CFGBlock *succ = *it) { 593 val = LV->merge(val, LV->blocksBeginToLiveness[succ]); 594 } 595 } 596 597 if (!everAnalyzedBlock[block->getBlockID()]) 598 everAnalyzedBlock[block->getBlockID()] = true; 599 else if (prevVal.equals(val)) 600 continue; 601 602 prevVal = val; 603 604 // Update the dataflow value for the start of this block. 605 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); 606 607 // Enqueue the value to the predecessors. 608 worklist.enqueuePredecessors(block); 609 } 610 611 return std::unique_ptr<LiveVariables>(new LiveVariables(LV)); 612 } 613 614 void LiveVariables::dumpBlockLiveness(const SourceManager &M) { 615 getImpl(impl).dumpBlockLiveness(M); 616 } 617 618 void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { 619 std::vector<const CFGBlock *> vec; 620 for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator 621 it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); 622 it != ei; ++it) { 623 vec.push_back(it->first); 624 } 625 llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) { 626 return A->getBlockID() < B->getBlockID(); 627 }); 628 629 std::vector<const VarDecl*> declVec; 630 631 for (std::vector<const CFGBlock *>::iterator 632 it = vec.begin(), ei = vec.end(); it != ei; ++it) { 633 llvm::errs() << "\n[ B" << (*it)->getBlockID() 634 << " (live variables at block exit) ]\n"; 635 636 LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; 637 declVec.clear(); 638 639 for (llvm::ImmutableSet<const VarDecl *>::iterator si = 640 vals.liveDecls.begin(), 641 se = vals.liveDecls.end(); si != se; ++si) { 642 declVec.push_back(*si); 643 } 644 645 llvm::sort(declVec, [](const Decl *A, const Decl *B) { 646 return A->getBeginLoc() < B->getBeginLoc(); 647 }); 648 649 for (std::vector<const VarDecl*>::iterator di = declVec.begin(), 650 de = declVec.end(); di != de; ++di) { 651 llvm::errs() << " " << (*di)->getDeclName().getAsString() 652 << " <"; 653 (*di)->getLocation().print(llvm::errs(), M); 654 llvm::errs() << ">\n"; 655 } 656 } 657 llvm::errs() << "\n"; 658 } 659 660 void LiveVariables::dumpExprLiveness(const SourceManager &M) { 661 getImpl(impl).dumpExprLiveness(M); 662 } 663 664 void LiveVariablesImpl::dumpExprLiveness(const SourceManager &M) { 665 // Don't iterate over blockEndsToLiveness directly because it's not sorted. 666 for (const CFGBlock *B : *analysisContext.getCFG()) { 667 668 llvm::errs() << "\n[ B" << B->getBlockID() 669 << " (live expressions at block exit) ]\n"; 670 for (const Expr *E : blocksEndToLiveness[B].liveExprs) { 671 llvm::errs() << "\n"; 672 E->dump(); 673 } 674 llvm::errs() << "\n"; 675 } 676 } 677 678 const void *LiveVariables::getTag() { static int x; return &x; } 679 const void *RelaxedLiveVariables::getTag() { static int x; return &x; } 680