1//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements Live Variables analysis for source-level CFGs.
10//
11//===----------------------------------------------------------------------===//
12
13#include "clang/Analysis/Analyses/LiveVariables.h"
14#include "clang/AST/Stmt.h"
15#include "clang/AST/StmtVisitor.h"
16#include "clang/Analysis/Analyses/PostOrderCFGView.h"
17#include "clang/Analysis/AnalysisDeclContext.h"
18#include "clang/Analysis/CFG.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/PostOrderIterator.h"
21#include "llvm/ADT/PriorityQueue.h"
22#include "llvm/Support/raw_ostream.h"
23#include <algorithm>
24#include <vector>
25
26using namespace clang;
27
28namespace {
29
30class DataflowWorklist {
31  llvm::BitVector enqueuedBlocks;
32  PostOrderCFGView *POV;
33  llvm::PriorityQueue<const CFGBlock *, SmallVector<const CFGBlock *, 20>,
34                      PostOrderCFGView::BlockOrderCompare> worklist;
35
36public:
37  DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx)
38    : enqueuedBlocks(cfg.getNumBlockIDs()),
39      POV(Ctx.getAnalysis<PostOrderCFGView>()),
40      worklist(POV->getComparator()) {}
41
42  void enqueueBlock(const CFGBlock *block);
43  void enqueuePredecessors(const CFGBlock *block);
44
45  const CFGBlock *dequeue();
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(block);
54  }
55}
56
57void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) {
58  for (CFGBlock::const_pred_iterator I = block->pred_begin(),
59       E = block->pred_end(); I != E; ++I) {
60    enqueueBlock(*I);
61  }
62}
63
64const CFGBlock *DataflowWorklist::dequeue() {
65  if (worklist.empty())
66    return nullptr;
67  const CFGBlock *b = worklist.top();
68  worklist.pop();
69  enqueuedBlocks[b->getBlockID()] = false;
70  return b;
71}
72
73namespace {
74class LiveVariablesImpl {
75public:
76  AnalysisDeclContext &analysisContext;
77  llvm::ImmutableSet<const Stmt *>::Factory SSetFact;
78  llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
79  llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact;
80  llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
81  llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
82  llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
83  llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
84  const bool killAtAssign;
85
86  LiveVariables::LivenessValues
87  merge(LiveVariables::LivenessValues valsA,
88        LiveVariables::LivenessValues valsB);
89
90  LiveVariables::LivenessValues
91  runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val,
92             LiveVariables::Observer *obs = nullptr);
93
94  void dumpBlockLiveness(const SourceManager& M);
95  void dumpStmtLiveness(const SourceManager& M);
96
97  LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
98    : analysisContext(ac),
99      SSetFact(false), // Do not canonicalize ImmutableSets by default.
100      DSetFact(false), // This is a *major* performance win.
101      BSetFact(false),
102      killAtAssign(KillAtAssign) {}
103};
104}
105
106static LiveVariablesImpl &getImpl(void *x) {
107  return *((LiveVariablesImpl *) x);
108}
109
110//===----------------------------------------------------------------------===//
111// Operations and queries on LivenessValues.
112//===----------------------------------------------------------------------===//
113
114bool LiveVariables::LivenessValues::isLive(const Stmt *S) const {
115  return liveStmts.contains(S);
116}
117
118bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {
119  if (const auto *DD = dyn_cast<DecompositionDecl>(D)) {
120    bool alive = false;
121    for (const BindingDecl *BD : DD->bindings())
122      alive |= liveBindings.contains(BD);
123    return alive;
124  }
125  return liveDecls.contains(D);
126}
127
128namespace {
129  template <typename SET>
130  SET mergeSets(SET A, SET B) {
131    if (A.isEmpty())
132      return B;
133
134    for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
135      A = A.add(*it);
136    }
137    return A;
138  }
139}
140
141void LiveVariables::Observer::anchor() { }
142
143LiveVariables::LivenessValues
144LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
145                         LiveVariables::LivenessValues valsB) {
146
147  llvm::ImmutableSetRef<const Stmt *>
148    SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()),
149    SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory());
150
151
152  llvm::ImmutableSetRef<const VarDecl *>
153    DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
154    DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
155
156  llvm::ImmutableSetRef<const BindingDecl *>
157    BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()),
158    BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory());
159
160  SSetRefA = mergeSets(SSetRefA, SSetRefB);
161  DSetRefA = mergeSets(DSetRefA, DSetRefB);
162  BSetRefA = mergeSets(BSetRefA, BSetRefB);
163
164  // asImmutableSet() canonicalizes the tree, allowing us to do an easy
165  // comparison afterwards.
166  return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),
167                                       DSetRefA.asImmutableSet(),
168                                       BSetRefA.asImmutableSet());
169}
170
171bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const {
172  return liveStmts == V.liveStmts && liveDecls == V.liveDecls;
173}
174
175//===----------------------------------------------------------------------===//
176// Query methods.
177//===----------------------------------------------------------------------===//
178
179static bool isAlwaysAlive(const VarDecl *D) {
180  return D->hasGlobalStorage();
181}
182
183bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
184  return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
185}
186
187bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
188  return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
189}
190
191bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) {
192  return getImpl(impl).stmtsToLiveness[Loc].isLive(S);
193}
194
195//===----------------------------------------------------------------------===//
196// Dataflow computation.
197//===----------------------------------------------------------------------===//
198
199namespace {
200class TransferFunctions : public StmtVisitor<TransferFunctions> {
201  LiveVariablesImpl &LV;
202  LiveVariables::LivenessValues &val;
203  LiveVariables::Observer *observer;
204  const CFGBlock *currentBlock;
205public:
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
223static 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 nullptr;
234}
235
236static 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 FullExpr *FE = dyn_cast<FullExpr>(S)) {
241      S = FE->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
253static 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
259void 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 != nullptr; 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    case Stmt::IfStmtClass: {
331      // If one of the branches is an expression rather than a compound
332      // statement, it will be bad if we mark it as live at the terminator
333      // of the if-statement (i.e., immediately after the condition expression).
334      AddLiveStmt(val.liveStmts, LV.SSetFact, cast<IfStmt>(S)->getCond());
335      return;
336    }
337    case Stmt::WhileStmtClass: {
338      // If the loop body is an expression rather than a compound statement,
339      // it will be bad if we mark it as live at the terminator of the loop
340      // (i.e., immediately after the condition expression).
341      AddLiveStmt(val.liveStmts, LV.SSetFact, cast<WhileStmt>(S)->getCond());
342      return;
343    }
344    case Stmt::DoStmtClass: {
345      // If the loop body is an expression rather than a compound statement,
346      // it will be bad if we mark it as live at the terminator of the loop
347      // (i.e., immediately after the condition expression).
348      AddLiveStmt(val.liveStmts, LV.SSetFact, cast<DoStmt>(S)->getCond());
349      return;
350    }
351    case Stmt::ForStmtClass: {
352      // If the loop body is an expression rather than a compound statement,
353      // it will be bad if we mark it as live at the terminator of the loop
354      // (i.e., immediately after the condition expression).
355      AddLiveStmt(val.liveStmts, LV.SSetFact, cast<ForStmt>(S)->getCond());
356      return;
357    }
358
359  }
360
361  for (Stmt *Child : S->children()) {
362    if (Child)
363      AddLiveStmt(val.liveStmts, LV.SSetFact, Child);
364  }
365}
366
367static bool writeShouldKill(const VarDecl *VD) {
368  return VD && !VD->getType()->isReferenceType() &&
369    !isAlwaysAlive(VD);
370}
371
372void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
373  if (B->isAssignmentOp()) {
374    if (!LV.killAtAssign)
375      return;
376
377    // Assigning to a variable?
378    Expr *LHS = B->getLHS()->IgnoreParens();
379
380    if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
381      const Decl* D = DR->getDecl();
382      bool Killed = false;
383
384      if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
385        Killed = !BD->getType()->isReferenceType();
386        if (Killed)
387          val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
388      } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
389        Killed = writeShouldKill(VD);
390        if (Killed)
391          val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
392
393      }
394
395      if (Killed && observer)
396        observer->observerKill(DR);
397    }
398  }
399}
400
401void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
402  for (const VarDecl *VD :
403       LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
404    if (isAlwaysAlive(VD))
405      continue;
406    val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
407  }
408}
409
410void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
411  const Decl* D = DR->getDecl();
412  bool InAssignment = LV.inAssignment[DR];
413  if (const auto *BD = dyn_cast<BindingDecl>(D)) {
414    if (!InAssignment)
415      val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);
416  } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
417    if (!InAssignment && !isAlwaysAlive(VD))
418      val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
419  }
420}
421
422void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
423  for (const auto *DI : DS->decls()) {
424    if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
425      for (const auto *BD : DD->bindings())
426        val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
427    } else if (const auto *VD = dyn_cast<VarDecl>(DI)) {
428      if (!isAlwaysAlive(VD))
429        val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
430    }
431  }
432}
433
434void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
435  // Kill the iteration variable.
436  DeclRefExpr *DR = nullptr;
437  const VarDecl *VD = nullptr;
438
439  Stmt *element = OS->getElement();
440  if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
441    VD = cast<VarDecl>(DS->getSingleDecl());
442  }
443  else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
444    VD = cast<VarDecl>(DR->getDecl());
445  }
446
447  if (VD) {
448    val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
449    if (observer && DR)
450      observer->observerKill(DR);
451  }
452}
453
454void TransferFunctions::
455VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
456{
457  // While sizeof(var) doesn't technically extend the liveness of 'var', it
458  // does extent the liveness of metadata if 'var' is a VariableArrayType.
459  // We handle that special case here.
460  if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
461    return;
462
463  const Expr *subEx = UE->getArgumentExpr();
464  if (subEx->getType()->isVariableArrayType()) {
465    assert(subEx->isLValue());
466    val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens());
467  }
468}
469
470void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
471  // Treat ++/-- as a kill.
472  // Note we don't actually have to do anything if we don't have an observer,
473  // since a ++/-- acts as both a kill and a "use".
474  if (!observer)
475    return;
476
477  switch (UO->getOpcode()) {
478  default:
479    return;
480  case UO_PostInc:
481  case UO_PostDec:
482  case UO_PreInc:
483  case UO_PreDec:
484    break;
485  }
486
487  if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) {
488    const Decl *D = DR->getDecl();
489    if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
490      // Treat ++/-- as a kill.
491      observer->observerKill(DR);
492    }
493  }
494}
495
496LiveVariables::LivenessValues
497LiveVariablesImpl::runOnBlock(const CFGBlock *block,
498                              LiveVariables::LivenessValues val,
499                              LiveVariables::Observer *obs) {
500
501  TransferFunctions TF(*this, val, obs, block);
502
503  // Visit the terminator (if any).
504  if (const Stmt *term = block->getTerminatorStmt())
505    TF.Visit(const_cast<Stmt*>(term));
506
507  // Apply the transfer function for all Stmts in the block.
508  for (CFGBlock::const_reverse_iterator it = block->rbegin(),
509       ei = block->rend(); it != ei; ++it) {
510    const CFGElement &elem = *it;
511
512    if (Optional<CFGAutomaticObjDtor> Dtor =
513            elem.getAs<CFGAutomaticObjDtor>()) {
514      val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());
515      continue;
516    }
517
518    if (!elem.getAs<CFGStmt>())
519      continue;
520
521    const Stmt *S = elem.castAs<CFGStmt>().getStmt();
522    TF.Visit(const_cast<Stmt*>(S));
523    stmtsToLiveness[S] = val;
524  }
525  return val;
526}
527
528void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
529  const CFG *cfg = getImpl(impl).analysisContext.getCFG();
530  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
531    getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
532}
533
534LiveVariables::LiveVariables(void *im) : impl(im) {}
535
536LiveVariables::~LiveVariables() {
537  delete (LiveVariablesImpl*) impl;
538}
539
540LiveVariables *
541LiveVariables::computeLiveness(AnalysisDeclContext &AC,
542                                 bool killAtAssign) {
543
544  // No CFG?  Bail out.
545  CFG *cfg = AC.getCFG();
546  if (!cfg)
547    return nullptr;
548
549  // The analysis currently has scalability issues for very large CFGs.
550  // Bail out if it looks too large.
551  if (cfg->getNumBlockIDs() > 300000)
552    return nullptr;
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, AC);
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 (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) {
574          const Stmt* stmt = cs->getStmt();
575          if (const auto *BO = dyn_cast<BinaryOperator>(stmt)) {
576            if (BO->getOpcode() == BO_Assign) {
577              if (const auto *DR =
578                    dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
579                LV->inAssignment[DR] = 1;
580              }
581            }
582          }
583        }
584      }
585  }
586
587  while (const CFGBlock *block = worklist.dequeue()) {
588    // Determine if the block's end value has changed.  If not, we
589    // have nothing left to do for this block.
590    LivenessValues &prevVal = LV->blocksEndToLiveness[block];
591
592    // Merge the values of all successor blocks.
593    LivenessValues val;
594    for (CFGBlock::const_succ_iterator it = block->succ_begin(),
595                                       ei = block->succ_end(); it != ei; ++it) {
596      if (const CFGBlock *succ = *it) {
597        val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
598      }
599    }
600
601    if (!everAnalyzedBlock[block->getBlockID()])
602      everAnalyzedBlock[block->getBlockID()] = true;
603    else if (prevVal.equals(val))
604      continue;
605
606    prevVal = val;
607
608    // Update the dataflow value for the start of this block.
609    LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
610
611    // Enqueue the value to the predecessors.
612    worklist.enqueuePredecessors(block);
613  }
614
615  return new LiveVariables(LV);
616}
617
618void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
619  getImpl(impl).dumpBlockLiveness(M);
620}
621
622void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
623  std::vector<const CFGBlock *> vec;
624  for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
625       it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
626       it != ei; ++it) {
627    vec.push_back(it->first);
628  }
629  llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) {
630    return A->getBlockID() < B->getBlockID();
631  });
632
633  std::vector<const VarDecl*> declVec;
634
635  for (std::vector<const CFGBlock *>::iterator
636        it = vec.begin(), ei = vec.end(); it != ei; ++it) {
637    llvm::errs() << "\n[ B" << (*it)->getBlockID()
638                 << " (live variables at block exit) ]\n";
639
640    LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
641    declVec.clear();
642
643    for (llvm::ImmutableSet<const VarDecl *>::iterator si =
644          vals.liveDecls.begin(),
645          se = vals.liveDecls.end(); si != se; ++si) {
646      declVec.push_back(*si);
647    }
648
649    llvm::sort(declVec, [](const Decl *A, const Decl *B) {
650      return A->getBeginLoc() < B->getBeginLoc();
651    });
652
653    for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
654         de = declVec.end(); di != de; ++di) {
655      llvm::errs() << " " << (*di)->getDeclName().getAsString()
656                   << " <";
657      (*di)->getLocation().print(llvm::errs(), M);
658      llvm::errs() << ">\n";
659    }
660  }
661  llvm::errs() << "\n";
662}
663
664void LiveVariables::dumpStmtLiveness(const SourceManager &M) {
665  getImpl(impl).dumpStmtLiveness(M);
666}
667
668void LiveVariablesImpl::dumpStmtLiveness(const SourceManager &M) {
669  // Don't iterate over blockEndsToLiveness directly because it's not sorted.
670  for (auto I : *analysisContext.getCFG()) {
671
672    llvm::errs() << "\n[ B" << I->getBlockID()
673                 << " (live statements at block exit) ]\n";
674    for (auto S : blocksEndToLiveness[I].liveStmts) {
675      llvm::errs() << "\n";
676      S->dump();
677    }
678    llvm::errs() << "\n";
679  }
680}
681
682const void *LiveVariables::getTag() { static int x; return &x; }
683const void *RelaxedLiveVariables::getTag() { static int x; return &x; }
684