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::DeclStmtClass: {
    288       const DeclStmt *DS = cast<DeclStmt>(S);
    289       if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
    290         for (const VariableArrayType* VA = FindVA(VD->getType());
    291              VA != 0; VA = FindVA(VA->getElementType())) {
    292           AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr());
    293         }
    294       }
    295       break;
    296     }
    297     case Stmt::PseudoObjectExprClass: {
    298       // A pseudo-object operation only directly consumes its result
    299       // expression.
    300       Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
    301       if (!child) return;
    302       if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))
    303         child = OV->getSourceExpr();
    304       child = child->IgnoreParens();
    305       val.liveStmts = LV.SSetFact.add(val.liveStmts, child);
    306       return;
    307     }
    308 
    309     // FIXME: These cases eventually shouldn't be needed.
    310     case Stmt::ExprWithCleanupsClass: {
    311       S = cast<ExprWithCleanups>(S)->getSubExpr();
    312       break;
    313     }
    314     case Stmt::CXXBindTemporaryExprClass: {
    315       S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
    316       break;
    317     }
    318     case Stmt::UnaryExprOrTypeTraitExprClass: {
    319       // No need to unconditionally visit subexpressions.
    320       return;
    321     }
    322   }
    323 
    324   for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end();
    325        it != ei; ++it) {
    326     if (Stmt *child = *it)
    327       AddLiveStmt(val.liveStmts, LV.SSetFact, child);
    328   }
    329 }
    330 
    331 void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
    332   if (B->isAssignmentOp()) {
    333     if (!LV.killAtAssign)
    334       return;
    335 
    336     // Assigning to a variable?
    337     Expr *LHS = B->getLHS()->IgnoreParens();
    338 
    339     if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS))
    340       if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
    341         // Assignments to references don't kill the ref's address
    342         if (VD->getType()->isReferenceType())
    343           return;
    344 
    345         if (!isAlwaysAlive(VD)) {
    346           // The variable is now dead.
    347           val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
    348         }
    349 
    350         if (observer)
    351           observer->observerKill(DR);
    352       }
    353   }
    354 }
    355 
    356 void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
    357   AnalysisDeclContext::referenced_decls_iterator I, E;
    358   llvm::tie(I, E) =
    359     LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl());
    360   for ( ; I != E ; ++I) {
    361     const VarDecl *VD = *I;
    362     if (isAlwaysAlive(VD))
    363       continue;
    364     val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
    365   }
    366 }
    367 
    368 void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
    369   if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl()))
    370     if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end())
    371       val.liveDecls = LV.DSetFact.add(val.liveDecls, D);
    372 }
    373 
    374 void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
    375   for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
    376        DI != DE; ++DI)
    377     if (VarDecl *VD = dyn_cast<VarDecl>(*DI)) {
    378       if (!isAlwaysAlive(VD))
    379         val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
    380     }
    381 }
    382 
    383 void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
    384   // Kill the iteration variable.
    385   DeclRefExpr *DR = 0;
    386   const VarDecl *VD = 0;
    387 
    388   Stmt *element = OS->getElement();
    389   if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
    390     VD = cast<VarDecl>(DS->getSingleDecl());
    391   }
    392   else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
    393     VD = cast<VarDecl>(DR->getDecl());
    394   }
    395 
    396   if (VD) {
    397     val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
    398     if (observer && DR)
    399       observer->observerKill(DR);
    400   }
    401 }
    402 
    403 void TransferFunctions::
    404 VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
    405 {
    406   // While sizeof(var) doesn't technically extend the liveness of 'var', it
    407   // does extent the liveness of metadata if 'var' is a VariableArrayType.
    408   // We handle that special case here.
    409   if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
    410     return;
    411 
    412   const Expr *subEx = UE->getArgumentExpr();
    413   if (subEx->getType()->isVariableArrayType()) {
    414     assert(subEx->isLValue());
    415     val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens());
    416   }
    417 }
    418 
    419 void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
    420   // Treat ++/-- as a kill.
    421   // Note we don't actually have to do anything if we don't have an observer,
    422   // since a ++/-- acts as both a kill and a "use".
    423   if (!observer)
    424     return;
    425 
    426   switch (UO->getOpcode()) {
    427   default:
    428     return;
    429   case UO_PostInc:
    430   case UO_PostDec:
    431   case UO_PreInc:
    432   case UO_PreDec:
    433     break;
    434   }
    435 
    436   if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens()))
    437     if (isa<VarDecl>(DR->getDecl())) {
    438       // Treat ++/-- as a kill.
    439       observer->observerKill(DR);
    440     }
    441 }
    442 
    443 LiveVariables::LivenessValues
    444 LiveVariablesImpl::runOnBlock(const CFGBlock *block,
    445                               LiveVariables::LivenessValues val,
    446                               LiveVariables::Observer *obs) {
    447 
    448   TransferFunctions TF(*this, val, obs, block);
    449 
    450   // Visit the terminator (if any).
    451   if (const Stmt *term = block->getTerminator())
    452     TF.Visit(const_cast<Stmt*>(term));
    453 
    454   // Apply the transfer function for all Stmts in the block.
    455   for (CFGBlock::const_reverse_iterator it = block->rbegin(),
    456        ei = block->rend(); it != ei; ++it) {
    457     const CFGElement &elem = *it;
    458     if (!isa<CFGStmt>(elem))
    459       continue;
    460 
    461     const Stmt *S = cast<CFGStmt>(elem).getStmt();
    462     TF.Visit(const_cast<Stmt*>(S));
    463     stmtsToLiveness[S] = val;
    464   }
    465   return val;
    466 }
    467 
    468 void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
    469   const CFG *cfg = getImpl(impl).analysisContext.getCFG();
    470   for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
    471     getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
    472 }
    473 
    474 LiveVariables::LiveVariables(void *im) : impl(im) {}
    475 
    476 LiveVariables::~LiveVariables() {
    477   delete (LiveVariablesImpl*) impl;
    478 }
    479 
    480 LiveVariables *
    481 LiveVariables::computeLiveness(AnalysisDeclContext &AC,
    482                                  bool killAtAssign) {
    483 
    484   // No CFG?  Bail out.
    485   CFG *cfg = AC.getCFG();
    486   if (!cfg)
    487     return 0;
    488 
    489   LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
    490 
    491   // Construct the dataflow worklist.  Enqueue the exit block as the
    492   // start of the analysis.
    493   DataflowWorklist worklist(*cfg, AC);
    494   llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
    495 
    496   // FIXME: we should enqueue using post order.
    497   for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
    498     const CFGBlock *block = *it;
    499     worklist.enqueueBlock(block);
    500 
    501     // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
    502     // We need to do this because we lack context in the reverse analysis
    503     // to determine if a DeclRefExpr appears in such a context, and thus
    504     // doesn't constitute a "use".
    505     if (killAtAssign)
    506       for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
    507            bi != be; ++bi) {
    508         if (const CFGStmt *cs = bi->getAs<CFGStmt>()) {
    509           if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(cs->getStmt())) {
    510             if (BO->getOpcode() == BO_Assign) {
    511               if (const DeclRefExpr *DR =
    512                     dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
    513                 LV->inAssignment[DR] = 1;
    514               }
    515             }
    516           }
    517         }
    518       }
    519   }
    520 
    521   worklist.sortWorklist();
    522 
    523   while (const CFGBlock *block = worklist.dequeue()) {
    524     // Determine if the block's end value has changed.  If not, we
    525     // have nothing left to do for this block.
    526     LivenessValues &prevVal = LV->blocksEndToLiveness[block];
    527 
    528     // Merge the values of all successor blocks.
    529     LivenessValues val;
    530     for (CFGBlock::const_succ_iterator it = block->succ_begin(),
    531                                        ei = block->succ_end(); it != ei; ++it) {
    532       if (const CFGBlock *succ = *it) {
    533         val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
    534       }
    535     }
    536 
    537     if (!everAnalyzedBlock[block->getBlockID()])
    538       everAnalyzedBlock[block->getBlockID()] = true;
    539     else if (prevVal.equals(val))
    540       continue;
    541 
    542     prevVal = val;
    543 
    544     // Update the dataflow value for the start of this block.
    545     LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
    546 
    547     // Enqueue the value to the predecessors.
    548     worklist.enqueuePredecessors(block);
    549   }
    550 
    551   return new LiveVariables(LV);
    552 }
    553 
    554 static bool compare_entries(const CFGBlock *A, const CFGBlock *B) {
    555   return A->getBlockID() < B->getBlockID();
    556 }
    557 
    558 static bool compare_vd_entries(const Decl *A, const Decl *B) {
    559   SourceLocation ALoc = A->getLocStart();
    560   SourceLocation BLoc = B->getLocStart();
    561   return ALoc.getRawEncoding() < BLoc.getRawEncoding();
    562 }
    563 
    564 void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
    565   getImpl(impl).dumpBlockLiveness(M);
    566 }
    567 
    568 void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
    569   std::vector<const CFGBlock *> vec;
    570   for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
    571        it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
    572        it != ei; ++it) {
    573     vec.push_back(it->first);
    574   }
    575   std::sort(vec.begin(), vec.end(), compare_entries);
    576 
    577   std::vector<const VarDecl*> declVec;
    578 
    579   for (std::vector<const CFGBlock *>::iterator
    580         it = vec.begin(), ei = vec.end(); it != ei; ++it) {
    581     llvm::errs() << "\n[ B" << (*it)->getBlockID()
    582                  << " (live variables at block exit) ]\n";
    583 
    584     LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
    585     declVec.clear();
    586 
    587     for (llvm::ImmutableSet<const VarDecl *>::iterator si =
    588           vals.liveDecls.begin(),
    589           se = vals.liveDecls.end(); si != se; ++si) {
    590       declVec.push_back(*si);
    591     }
    592 
    593     std::sort(declVec.begin(), declVec.end(), compare_vd_entries);
    594 
    595     for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
    596          de = declVec.end(); di != de; ++di) {
    597       llvm::errs() << " " << (*di)->getDeclName().getAsString()
    598                    << " <";
    599       (*di)->getLocation().dump(M);
    600       llvm::errs() << ">\n";
    601     }
    602   }
    603   llvm::errs() << "\n";
    604 }
    605 
    606 const void *LiveVariables::getTag() { static int x; return &x; }
    607 const void *RelaxedLiveVariables::getTag() { static int x; return &x; }
    608