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