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