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 
LiveVariablesImpl(AnalysisDeclContext & ac,bool KillAtAssign)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 
getImpl(void * x)59 static LiveVariablesImpl &getImpl(void *x) {
60   return *((LiveVariablesImpl *) x);
61 }
62 
63 //===----------------------------------------------------------------------===//
64 // Operations and queries on LivenessValues.
65 //===----------------------------------------------------------------------===//
66 
isLive(const Expr * E) const67 bool LiveVariables::LivenessValues::isLive(const Expr *E) const {
68   return liveExprs.contains(E);
69 }
70 
isLive(const VarDecl * D) const71 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>
mergeSets(SET A,SET B)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 
anchor()99 void LiveVariables::Observer::anchor() { }
100 
101 LiveVariables::LivenessValues
merge(LiveVariables::LivenessValues valsA,LiveVariables::LivenessValues valsB)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 
equals(const LivenessValues & V) const129 bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const {
130   return liveExprs == V.liveExprs && liveDecls == V.liveDecls;
131 }
132 
133 //===----------------------------------------------------------------------===//
134 // Query methods.
135 //===----------------------------------------------------------------------===//
136 
isAlwaysAlive(const VarDecl * D)137 static bool isAlwaysAlive(const VarDecl *D) {
138   return D->hasGlobalStorage();
139 }
140 
isLive(const CFGBlock * B,const VarDecl * D)141 bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
142   return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
143 }
144 
isLive(const Stmt * S,const VarDecl * D)145 bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
146   return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
147 }
148 
isLive(const Stmt * Loc,const Expr * Val)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:
TransferFunctions(LiveVariablesImpl & im,LiveVariables::LivenessValues & Val,LiveVariables::Observer * Observer,const CFGBlock * CurrentBlock)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 
FindVA(QualType Ty)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 
LookThroughExpr(const Expr * E)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 
AddLiveExpr(llvm::ImmutableSet<const Expr * > & Set,llvm::ImmutableSet<const Expr * >::Factory & F,const Expr * E)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 
Visit(Stmt * S)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 
writeShouldKill(const VarDecl * VD)328 static bool writeShouldKill(const VarDecl *VD) {
329   return VD && !VD->getType()->isReferenceType() &&
330     !isAlwaysAlive(VD);
331 }
332 
VisitBinaryOperator(BinaryOperator * B)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 
VisitBlockExpr(BlockExpr * BE)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 
VisitDeclRefExpr(DeclRefExpr * DR)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 
VisitDeclStmt(DeclStmt * DS)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 
VisitObjCForCollectionStmt(ObjCForCollectionStmt * OS)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::
VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr * UE)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 
VisitUnaryOperator(UnaryOperator * UO)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
runOnBlock(const CFGBlock * block,LiveVariables::LivenessValues val,LiveVariables::Observer * obs)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 
runOnAllBlocks(LiveVariables::Observer & obs)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 
LiveVariables(void * im)516 LiveVariables::LiveVariables(void *im) : impl(im) {}
517 
~LiveVariables()518 LiveVariables::~LiveVariables() {
519   delete (LiveVariablesImpl*) impl;
520 }
521 
522 std::unique_ptr<LiveVariables>
computeLiveness(AnalysisDeclContext & AC,bool killAtAssign)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 
dumpBlockLiveness(const SourceManager & M)578 void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
579   getImpl(impl).dumpBlockLiveness(M);
580 }
581 
dumpBlockLiveness(const SourceManager & M)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 
dumpExprLiveness(const SourceManager & M)624 void LiveVariables::dumpExprLiveness(const SourceManager &M) {
625   getImpl(impl).dumpExprLiveness(M);
626 }
627 
dumpExprLiveness(const SourceManager & M)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 
getTag()642 const void *LiveVariables::getTag() { static int x; return &x; }
getTag()643 const void *RelaxedLiveVariables::getTag() { static int x; return &x; }
644