contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp

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