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