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