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