LiveVariables.cpp revision 87aa1250a90af9d92ad9d6b7b65610a45bf478c1 
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), killAtAssign(KillAtAssign) {}
209};
210}
211
212static LiveVariablesImpl &getImpl(void *x) {
213  return *((LiveVariablesImpl *) x);
214}
215
216//===----------------------------------------------------------------------===//
217// Operations and queries on LivenessValues.
218//===----------------------------------------------------------------------===//
219
220bool LiveVariables::LivenessValues::isLive(const Stmt *S) const {
221  return liveStmts.contains(S);
222}
223
224bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {
225  return liveDecls.contains(D);
226}
227
228namespace {
229  template <typename SET>
230  SET mergeSets(SET A, SET B) {
231    if (A.isEmpty())
232      return B;
233
234    for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
235      A = A.add(*it);
236    }
237    return A;
238  }
239}
240
241LiveVariables::LivenessValues
242LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
243                         LiveVariables::LivenessValues valsB) {
244
245  llvm::ImmutableSetRef<const Stmt *>
246    SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()),
247    SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory());
248
249
250  llvm::ImmutableSetRef<const VarDecl *>
251    DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
252    DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
253
254
255  SSetRefA = mergeSets(SSetRefA, SSetRefB);
256  DSetRefA = mergeSets(DSetRefA, DSetRefB);
257
258  return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),
259                                       DSetRefA.asImmutableSet());
260}
261
262bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const {
263  return liveStmts == V.liveStmts && liveDecls == V.liveDecls;
264}
265
266//===----------------------------------------------------------------------===//
267// Query methods.
268//===----------------------------------------------------------------------===//
269
270static bool isAlwaysAlive(const VarDecl *D) {
271  return D->hasGlobalStorage();
272}
273
274bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
275  return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
276}
277
278bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
279  return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
280}
281
282bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) {
283  return getImpl(impl).stmtsToLiveness[Loc].isLive(S);
284}
285
286//===----------------------------------------------------------------------===//
287// Dataflow computation.
288//===----------------------------------------------------------------------===//
289
290namespace {
291class TransferFunctions : public StmtVisitor<TransferFunctions> {
292  LiveVariablesImpl &LV;
293  LiveVariables::LivenessValues &val;
294  LiveVariables::Observer *observer;
295  const CFGBlock *currentBlock;
296public:
297  TransferFunctions(LiveVariablesImpl &im,
298                    LiveVariables::LivenessValues &Val,
299                    LiveVariables::Observer *Observer,
300                    const CFGBlock *CurrentBlock)
301  : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
302
303  void VisitBinaryOperator(BinaryOperator *BO);
304  void VisitBlockExpr(BlockExpr *BE);
305  void VisitDeclRefExpr(DeclRefExpr *DR);
306  void VisitDeclStmt(DeclStmt *DS);
307  void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
308  void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
309  void VisitUnaryOperator(UnaryOperator *UO);
310  void Visit(Stmt *S);
311};
312}
313
314static const VariableArrayType *FindVA(QualType Ty) {
315  const Type *ty = Ty.getTypePtr();
316  while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
317    if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
318      if (VAT->getSizeExpr())
319        return VAT;
320
321    ty = VT->getElementType().getTypePtr();
322  }
323
324  return 0;
325}
326
327void TransferFunctions::Visit(Stmt *S) {
328  if (observer)
329    observer->observeStmt(S, currentBlock, val);
330
331  StmtVisitor<TransferFunctions>::Visit(S);
332
333  if (isa<Expr>(S)) {
334    val.liveStmts = LV.SSetFact.remove(val.liveStmts, S);
335  }
336
337  // Mark all children expressions live.
338
339  switch (S->getStmtClass()) {
340    default:
341      break;
342    case Stmt::StmtExprClass: {
343      // For statement expressions, look through the compound statement.
344      S = cast<StmtExpr>(S)->getSubStmt();
345      break;
346    }
347    case Stmt::CXXMemberCallExprClass: {
348      // Include the implicit "this" pointer as being live.
349      CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
350      val.liveStmts =
351        LV.SSetFact.add(val.liveStmts,
352                        CE->getImplicitObjectArgument()->IgnoreParens());
353      break;
354    }
355    case Stmt::DeclStmtClass: {
356      const DeclStmt *DS = cast<DeclStmt>(S);
357      if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
358        for (const VariableArrayType* VA = FindVA(VD->getType());
359             VA != 0; VA = FindVA(VA->getElementType())) {
360          val.liveStmts = LV.SSetFact.add(val.liveStmts,
361                                          VA->getSizeExpr()->IgnoreParens());
362        }
363      }
364      break;
365    }
366    // FIXME: These cases eventually shouldn't be needed.
367    case Stmt::ExprWithCleanupsClass: {
368      S = cast<ExprWithCleanups>(S)->getSubExpr();
369      break;
370    }
371    case Stmt::CXXBindTemporaryExprClass: {
372      S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
373      break;
374    }
375    case Stmt::MaterializeTemporaryExprClass: {
376      S = cast<MaterializeTemporaryExpr>(S)->GetTemporaryExpr();
377      break;
378    }
379    case Stmt::UnaryExprOrTypeTraitExprClass: {
380      // No need to unconditionally visit subexpressions.
381      return;
382    }
383  }
384
385  for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end();
386       it != ei; ++it) {
387    if (Stmt *child = *it) {
388      if (Expr *Ex = dyn_cast<Expr>(child))
389        child = Ex->IgnoreParens();
390
391      val.liveStmts = LV.SSetFact.add(val.liveStmts, child);
392    }
393  }
394}
395
396void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
397  if (B->isAssignmentOp()) {
398    if (!LV.killAtAssign)
399      return;
400
401    // Assigning to a variable?
402    Expr *LHS = B->getLHS()->IgnoreParens();
403
404    if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS))
405      if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
406        // Assignments to references don't kill the ref's address
407        if (VD->getType()->isReferenceType())
408          return;
409
410        if (!isAlwaysAlive(VD)) {
411          // The variable is now dead.
412          val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
413        }
414
415        if (observer)
416          observer->observerKill(DR);
417      }
418  }
419}
420
421void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
422  AnalysisContext::referenced_decls_iterator I, E;
423  llvm::tie(I, E) =
424    LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl());
425  for ( ; I != E ; ++I) {
426    const VarDecl *VD = *I;
427    if (isAlwaysAlive(VD))
428      continue;
429    val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
430  }
431}
432
433void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
434  if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl()))
435    if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end())
436      val.liveDecls = LV.DSetFact.add(val.liveDecls, D);
437}
438
439void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
440  for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
441       DI != DE; ++DI)
442    if (VarDecl *VD = dyn_cast<VarDecl>(*DI)) {
443      if (!isAlwaysAlive(VD))
444        val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
445    }
446}
447
448void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
449  // Kill the iteration variable.
450  DeclRefExpr *DR = 0;
451  const VarDecl *VD = 0;
452
453  Stmt *element = OS->getElement();
454  if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
455    VD = cast<VarDecl>(DS->getSingleDecl());
456  }
457  else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
458    VD = cast<VarDecl>(DR->getDecl());
459  }
460
461  if (VD) {
462    val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
463    if (observer && DR)
464      observer->observerKill(DR);
465  }
466}
467
468void TransferFunctions::
469VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
470{
471  // While sizeof(var) doesn't technically extend the liveness of 'var', it
472  // does extent the liveness of metadata if 'var' is a VariableArrayType.
473  // We handle that special case here.
474  if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
475    return;
476
477  const Expr *subEx = UE->getArgumentExpr();
478  if (subEx->getType()->isVariableArrayType()) {
479    assert(subEx->isLValue());
480    val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens());
481  }
482}
483
484void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
485  // Treat ++/-- as a kill.
486  // Note we don't actually have to do anything if we don't have an observer,
487  // since a ++/-- acts as both a kill and a "use".
488  if (!observer)
489    return;
490
491  switch (UO->getOpcode()) {
492  default:
493    return;
494  case UO_PostInc:
495  case UO_PostDec:
496  case UO_PreInc:
497  case UO_PreDec:
498    break;
499  }
500
501  if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens()))
502    if (isa<VarDecl>(DR->getDecl())) {
503      // Treat ++/-- as a kill.
504      observer->observerKill(DR);
505    }
506}
507
508LiveVariables::LivenessValues
509LiveVariablesImpl::runOnBlock(const CFGBlock *block,
510                              LiveVariables::LivenessValues val,
511                              LiveVariables::Observer *obs) {
512
513  TransferFunctions TF(*this, val, obs, block);
514
515  // Visit the terminator (if any).
516  if (const Stmt *term = block->getTerminator())
517    TF.Visit(const_cast<Stmt*>(term));
518
519  // Apply the transfer function for all Stmts in the block.
520  for (CFGBlock::const_reverse_iterator it = block->rbegin(),
521       ei = block->rend(); it != ei; ++it) {
522    const CFGElement &elem = *it;
523    if (!isa<CFGStmt>(elem))
524      continue;
525
526    const Stmt *S = cast<CFGStmt>(elem).getStmt();
527    TF.Visit(const_cast<Stmt*>(S));
528    stmtsToLiveness[S] = val;
529  }
530  return val;
531}
532
533void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
534  const CFG *cfg = getImpl(impl).analysisContext.getCFG();
535  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
536    getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
537}
538
539LiveVariables::LiveVariables(void *im) : impl(im) {}
540
541LiveVariables::~LiveVariables() {
542  delete (LiveVariablesImpl*) impl;
543}
544
545LiveVariables *
546LiveVariables::computeLiveness(AnalysisContext &AC,
547                                 bool killAtAssign) {
548
549  // No CFG?  Bail out.
550  CFG *cfg = AC.getCFG();
551  if (!cfg)
552    return 0;
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);
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 (const CFGStmt *cs = bi->getAs<CFGStmt>()) {
574          if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(cs->getStmt())) {
575            if (BO->getOpcode() == BO_Assign) {
576              if (const DeclRefExpr *DR =
577                    dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
578                LV->inAssignment[DR] = 1;
579              }
580            }
581          }
582        }
583      }
584  }
585
586  worklist.sortWorklist();
587
588  while (const CFGBlock *block = worklist.dequeue()) {
589    // Determine if the block's end value has changed.  If not, we
590    // have nothing left to do for this block.
591    LivenessValues &prevVal = LV->blocksEndToLiveness[block];
592
593    // Merge the values of all successor blocks.
594    LivenessValues val;
595    for (CFGBlock::const_succ_iterator it = block->succ_begin(),
596                                       ei = block->succ_end(); it != ei; ++it) {
597      if (const CFGBlock *succ = *it) {
598        val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
599      }
600    }
601
602    if (!everAnalyzedBlock[block->getBlockID()])
603      everAnalyzedBlock[block->getBlockID()] = true;
604    else if (prevVal.equals(val))
605      continue;
606
607    prevVal = val;
608
609    // Update the dataflow value for the start of this block.
610    LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
611
612    // Enqueue the value to the predecessors.
613    worklist.enqueuePredecessors(block);
614  }
615
616  return new LiveVariables(LV);
617}
618
619static bool compare_entries(const CFGBlock *A, const CFGBlock *B) {
620  return A->getBlockID() < B->getBlockID();
621}
622
623static bool compare_vd_entries(const Decl *A, const Decl *B) {
624  SourceLocation ALoc = A->getLocStart();
625  SourceLocation BLoc = B->getLocStart();
626  return ALoc.getRawEncoding() < BLoc.getRawEncoding();
627}
628
629void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
630  getImpl(impl).dumpBlockLiveness(M);
631}
632
633void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
634  std::vector<const CFGBlock *> vec;
635  for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
636       it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
637       it != ei; ++it) {
638    vec.push_back(it->first);
639  }
640  std::sort(vec.begin(), vec.end(), compare_entries);
641
642  std::vector<const VarDecl*> declVec;
643
644  for (std::vector<const CFGBlock *>::iterator
645        it = vec.begin(), ei = vec.end(); it != ei; ++it) {
646    llvm::errs() << "\n[ B" << (*it)->getBlockID()
647                 << " (live variables at block exit) ]\n";
648
649    LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
650    declVec.clear();
651
652    for (llvm::ImmutableSet<const VarDecl *>::iterator si =
653          vals.liveDecls.begin(),
654          se = vals.liveDecls.end(); si != se; ++si) {
655      declVec.push_back(*si);
656    }
657
658    std::sort(declVec.begin(), declVec.end(), compare_vd_entries);
659
660    for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
661         de = declVec.end(); di != de; ++di) {
662      llvm::errs() << " " << (*di)->getDeclName().getAsString()
663                   << " <";
664      (*di)->getLocation().dump(M);
665      llvm::errs() << ">\n";
666    }
667  }
668  llvm::errs() << "\n";
669}
670
671