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