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