xref: /llvm-project/clang/lib/Analysis/LiveVariables.cpp (revision 73c72f2c6505d5bc8b47bb0420f6cba5b24270fe)
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