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