clang/lib/Analysis/LiveVariables.cpp

   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 void TransferFunctions::Visit(Stmt *S) {
 218   if (observer)
 219     observer->observeStmt(S, currentBlock, val);
 220
 221   StmtVisitor<TransferFunctions>::Visit(S);
 222
 223   if (const auto *E = dyn_cast<Expr>(S)) {
 224     val.liveExprs = LV.ESetFact.remove(val.liveExprs, E);
 225   }
 226
 227   // Mark all children expressions live.
 228
 229   switch (S->getStmtClass()) {
 230     default:
 231       break;
 232     case Stmt::StmtExprClass: {
 233       // For statement expressions, look through the compound statement.
 234       S = cast<StmtExpr>(S)->getSubStmt();
 235       break;
 236     }
 237     case Stmt::CXXMemberCallExprClass: {
 238       // Include the implicit "this" pointer as being live.
 239       CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
 240       if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
 241         AddLiveExpr(val.liveExprs, LV.ESetFact, ImplicitObj);
 242       }
 243       break;
 244     }
 245     case Stmt::ObjCMessageExprClass: {
 246       // In calls to super, include the implicit "self" pointer as being live.
 247       ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S);
 248       if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance)
 249         val.liveDecls = LV.DSetFact.add(val.liveDecls,
 250                                         LV.analysisContext.getSelfDecl());
 251       break;
 252     }
 253     case Stmt::DeclStmtClass: {
 254       const DeclStmt *DS = cast<DeclStmt>(S);
 255       if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
 256         for (const VariableArrayType* VA = FindVA(VD->getType());
 257              VA != nullptr; VA = FindVA(VA->getElementType())) {
 258           AddLiveExpr(val.liveExprs, LV.ESetFact, VA->getSizeExpr());
 259         }
 260       }
 261       break;
 262     }
 263     case Stmt::PseudoObjectExprClass: {
 264       // A pseudo-object operation only directly consumes its result
 265       // expression.
 266       Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
 267       if (!child) return;
 268       if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))
 269         child = OV->getSourceExpr();
 270       child = child->IgnoreParens();
 271       val.liveExprs = LV.ESetFact.add(val.liveExprs, child);
 272       return;
 273     }
 274
 275     // FIXME: These cases eventually shouldn't be needed.
 276     case Stmt::ExprWithCleanupsClass: {
 277       S = cast<ExprWithCleanups>(S)->getSubExpr();
 278       break;
 279     }
 280     case Stmt::CXXBindTemporaryExprClass: {
 281       S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
 282       break;
 283     }
 284     case Stmt::UnaryExprOrTypeTraitExprClass: {
 285       // No need to unconditionally visit subexpressions.
 286       return;
 287     }
 288     case Stmt::IfStmtClass: {
 289       // If one of the branches is an expression rather than a compound
 290       // statement, it will be bad if we mark it as live at the terminator
 291       // of the if-statement (i.e., immediately after the condition expression).
 292       AddLiveExpr(val.liveExprs, LV.ESetFact, cast<IfStmt>(S)->getCond());
 293       return;
 294     }
 295     case Stmt::WhileStmtClass: {
 296       // If the loop body is an expression rather than a compound statement,
 297       // it will be bad if we mark it as live at the terminator of the loop
 298       // (i.e., immediately after the condition expression).
 299       AddLiveExpr(val.liveExprs, LV.ESetFact, cast<WhileStmt>(S)->getCond());
 300       return;
 301     }
 302     case Stmt::DoStmtClass: {
 303       // If the loop body is an expression rather than a compound statement,
 304       // it will be bad if we mark it as live at the terminator of the loop
 305       // (i.e., immediately after the condition expression).
 306       AddLiveExpr(val.liveExprs, LV.ESetFact, cast<DoStmt>(S)->getCond());
 307       return;
 308     }
 309     case Stmt::ForStmtClass: {
 310       // If the loop body is an expression rather than a compound statement,
 311       // it will be bad if we mark it as live at the terminator of the loop
 312       // (i.e., immediately after the condition expression).
 313       AddLiveExpr(val.liveExprs, LV.ESetFact, cast<ForStmt>(S)->getCond());
 314       return;
 315     }
 316
 317   }
 318
 319   // HACK + FIXME: What is this? One could only guess that this is an attempt to
 320   // fish for live values, for example, arguments from a call expression.
 321   // Maybe we could take inspiration from UninitializedVariable analysis?
 322   for (Stmt *Child : S->children()) {
 323     if (const auto *E = dyn_cast_or_null<Expr>(Child))
 324       AddLiveExpr(val.liveExprs, LV.ESetFact, E);
 325   }
 326 }
 327
 328 static bool writeShouldKill(const VarDecl *VD) {
 329   return VD && !VD->getType()->isReferenceType() &&
 330     !isAlwaysAlive(VD);
 331 }
 332
 333 void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
 334   if (LV.killAtAssign && B->getOpcode() == BO_Assign) {
 335     if (const auto *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParens())) {
 336       LV.inAssignment[DR] = 1;
 337     }
 338   }
 339   if (B->isAssignmentOp()) {
 340     if (!LV.killAtAssign)
 341       return;
 342
 343     // Assigning to a variable?
 344     Expr *LHS = B->getLHS()->IgnoreParens();
 345
 346     if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
 347       const Decl* D = DR->getDecl();
 348       bool Killed = false;
 349
 350       if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
 351         Killed = !BD->getType()->isReferenceType();
 352         if (Killed) {
 353           if (const auto *HV = BD->getHoldingVar())
 354             val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);
 355
 356           val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
 357         }
 358       } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
 359         Killed = writeShouldKill(VD);
 360         if (Killed)
 361           val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
 362
 363       }
 364
 365       if (Killed && observer)
 366         observer->observerKill(DR);
 367     }
 368   }
 369 }
 370
 371 void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
 372   for (const VarDecl *VD :
 373        LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
 374     if (isAlwaysAlive(VD))
 375       continue;
 376     val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
 377   }
 378 }
 379
 380 void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
 381   const Decl* D = DR->getDecl();
 382   bool InAssignment = LV.inAssignment[DR];
 383   if (const auto *BD = dyn_cast<BindingDecl>(D)) {
 384     if (!InAssignment) {
 385       if (const auto *HV = BD->getHoldingVar())
 386         val.liveDecls = LV.DSetFact.add(val.liveDecls, HV);
 387
 388       val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);
 389     }
 390   } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
 391     if (!InAssignment && !isAlwaysAlive(VD))
 392       val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
 393   }
 394 }
 395
 396 void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
 397   for (const auto *DI : DS->decls()) {
 398     if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
 399       for (const auto *BD : DD->bindings()) {
 400         if (const auto *HV = BD->getHoldingVar())
 401           val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);
 402
 403         val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
 404       }
 405
 406       // When a bindig to a tuple-like structure is created, the HoldingVar
 407       // initializers have a DeclRefExpr to the DecompositionDecl.
 408       val.liveDecls = LV.DSetFact.remove(val.liveDecls, DD);
 409     } else if (const auto *VD = dyn_cast<VarDecl>(DI)) {
 410       if (!isAlwaysAlive(VD))
 411         val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
 412     }
 413   }
 414 }
 415
 416 void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
 417   // Kill the iteration variable.
 418   DeclRefExpr *DR = nullptr;
 419   const VarDecl *VD = nullptr;
 420
 421   Stmt *element = OS->getElement();
 422   if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
 423     VD = cast<VarDecl>(DS->getSingleDecl());
 424   }
 425   else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
 426     VD = cast<VarDecl>(DR->getDecl());
 427   }
 428
 429   if (VD) {
 430     val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
 431     if (observer && DR)
 432       observer->observerKill(DR);
 433   }
 434 }
 435
 436 void TransferFunctions::
 437 VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
 438 {
 439   // While sizeof(var) doesn't technically extend the liveness of 'var', it
 440   // does extent the liveness of metadata if 'var' is a VariableArrayType.
 441   // We handle that special case here.
 442   if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
 443     return;
 444
 445   const Expr *subEx = UE->getArgumentExpr();
 446   if (subEx->getType()->isVariableArrayType()) {
 447     assert(subEx->isLValue());
 448     val.liveExprs = LV.ESetFact.add(val.liveExprs, subEx->IgnoreParens());
 449   }
 450 }
 451
 452 void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
 453   // Treat ++/-- as a kill.
 454   // Note we don't actually have to do anything if we don't have an observer,
 455   // since a ++/-- acts as both a kill and a "use".
 456   if (!observer)
 457     return;
 458
 459   switch (UO->getOpcode()) {
 460   default:
 461     return;
 462   case UO_PostInc:
 463   case UO_PostDec:
 464   case UO_PreInc:
 465   case UO_PreDec:
 466     break;
 467   }
 468
 469   if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) {
 470     const Decl *D = DR->getDecl();
 471     if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
 472       // Treat ++/-- as a kill.
 473       observer->observerKill(DR);
 474     }
 475   }
 476 }
 477
 478 LiveVariables::LivenessValues
 479 LiveVariablesImpl::runOnBlock(const CFGBlock *block,
 480                               LiveVariables::LivenessValues val,
 481                               LiveVariables::Observer *obs) {
 482
 483   TransferFunctions TF(*this, val, obs, block);
 484
 485   // Visit the terminator (if any).
 486   if (const Stmt *term = block->getTerminatorStmt())
 487     TF.Visit(const_cast<Stmt*>(term));
 488
 489   // Apply the transfer function for all Stmts in the block.
 490   for (CFGBlock::const_reverse_iterator it = block->rbegin(),
 491        ei = block->rend(); it != ei; ++it) {
 492     const CFGElement &elem = *it;
 493
 494     if (std::optional<CFGAutomaticObjDtor> Dtor =
 495             elem.getAs<CFGAutomaticObjDtor>()) {
 496       val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());
 497       continue;
 498     }
 499
 500     if (!elem.getAs<CFGStmt>())
 501       continue;
 502
 503     const Stmt *S = elem.castAs<CFGStmt>().getStmt();
 504     TF.Visit(const_cast<Stmt*>(S));
 505     stmtsToLiveness[S] = val;
 506   }
 507   return val;
 508 }
 509
 510 void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
 511   const CFG *cfg = getImpl(impl).analysisContext.getCFG();
 512   for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
 513     getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
 514 }
 515
 516 LiveVariables::LiveVariables(void *im) : impl(im) {}
 517
 518 LiveVariables::~LiveVariables() {
 519   delete (LiveVariablesImpl*) impl;
 520 }
 521
 522 std::unique_ptr<LiveVariables>
 523 LiveVariables::computeLiveness(AnalysisDeclContext &AC, bool killAtAssign) {
 524
 525   // No CFG?  Bail out.
 526   CFG *cfg = AC.getCFG();
 527   if (!cfg)
 528     return nullptr;
 529
 530   // The analysis currently has scalability issues for very large CFGs.
 531   // Bail out if it looks too large.
 532   if (cfg->getNumBlockIDs() > 300000)
 533     return nullptr;
 534
 535   LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
 536
 537   // Construct the dataflow worklist.  Enqueue the exit block as the
 538   // start of the analysis.
 539   BackwardDataflowWorklist worklist(*cfg, AC);
 540   llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
 541
 542   // FIXME: we should enqueue using post order.
 543   for (const CFGBlock *B : cfg->nodes()) {
 544     worklist.enqueueBlock(B);
 545   }
 546
 547   while (const CFGBlock *block = worklist.dequeue()) {
 548     // Determine if the block's end value has changed.  If not, we
 549     // have nothing left to do for this block.
 550     LivenessValues &prevVal = LV->blocksEndToLiveness[block];
 551
 552     // Merge the values of all successor blocks.
 553     LivenessValues val;
 554     for (CFGBlock::const_succ_iterator it = block->succ_begin(),
 555                                        ei = block->succ_end(); it != ei; ++it) {
 556       if (const CFGBlock *succ = *it) {
 557         val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
 558       }
 559     }
 560
 561     if (!everAnalyzedBlock[block->getBlockID()])
 562       everAnalyzedBlock[block->getBlockID()] = true;
 563     else if (prevVal.equals(val))
 564       continue;
 565
 566     prevVal = val;
 567
 568     // Update the dataflow value for the start of this block.
 569     LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
 570
 571     // Enqueue the value to the predecessors.
 572     worklist.enqueuePredecessors(block);
 573   }
 574
 575   return std::unique_ptr<LiveVariables>(new LiveVariables(LV));
 576 }
 577
 578 void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
 579   getImpl(impl).dumpBlockLiveness(M);
 580 }
 581
 582 void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
 583   std::vector<const CFGBlock *> vec;
 584   for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
 585        it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
 586        it != ei; ++it) {
 587     vec.push_back(it->first);
 588   }
 589   llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) {
 590     return A->getBlockID() < B->getBlockID();
 591   });
 592
 593   std::vector<const VarDecl*> declVec;
 594
 595   for (std::vector<const CFGBlock *>::iterator
 596         it = vec.begin(), ei = vec.end(); it != ei; ++it) {
 597     llvm::errs() << "\n[ B" << (*it)->getBlockID()
 598                  << " (live variables at block exit) ]\n";
 599
 600     LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
 601     declVec.clear();
 602
 603     for (llvm::ImmutableSet<const VarDecl *>::iterator si =
 604           vals.liveDecls.begin(),
 605           se = vals.liveDecls.end(); si != se; ++si) {
 606       declVec.push_back(*si);
 607     }
 608
 609     llvm::sort(declVec, [](const Decl *A, const Decl *B) {
 610       return A->getBeginLoc() < B->getBeginLoc();
 611     });
 612
 613     for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
 614          de = declVec.end(); di != de; ++di) {
 615       llvm::errs() << " " << (*di)->getDeclName().getAsString()
 616                    << " <";
 617       (*di)->getLocation().print(llvm::errs(), M);
 618       llvm::errs() << ">\n";
 619     }
 620   }
 621   llvm::errs() << "\n";
 622 }
 623
 624 void LiveVariables::dumpExprLiveness(const SourceManager &M) {
 625   getImpl(impl).dumpExprLiveness(M);
 626 }
 627
 628 void LiveVariablesImpl::dumpExprLiveness(const SourceManager &M) {
 629   // Don't iterate over blockEndsToLiveness directly because it's not sorted.
 630   for (const CFGBlock *B : *analysisContext.getCFG()) {
 631
 632     llvm::errs() << "\n[ B" << B->getBlockID()
 633                  << " (live expressions at block exit) ]\n";
 634     for (const Expr *E : blocksEndToLiveness[B].liveExprs) {
 635       llvm::errs() << "\n";
 636       E->dump();
 637     }
 638     llvm::errs() << "\n";
 639   }
 640 }
 641
 642 const void *LiveVariables::getTag() { static int x; return &x; }
 643 const void *RelaxedLiveVariables::getTag() { static int x; return &x; }