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(V: E);
69}
70
71bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {
72 if (const auto *DD = dyn_cast<DecompositionDecl>(Val: D)) {
73 bool alive = false;
74 for (const BindingDecl *BD : DD->bindings())
75 alive |= liveBindings.contains(V: 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(V: DD);
81 return alive;
82 }
83 return liveDecls.contains(V: 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(A: SSetRefA, B: SSetRefB);
119 DSetRefA = mergeSets(A: DSetRefA, B: DSetRefB);
120 BSetRefA = mergeSets(A: BSetRefA, B: 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(x: impl).blocksEndToLiveness[B].isLive(D);
143}
144
145bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
146 return isAlwaysAlive(D) || getImpl(x: impl).stmtsToLiveness[S].isLive(D);
147}
148
149bool LiveVariables::isLive(const Stmt *Loc, const Expr *Val) {
150 return getImpl(x: impl).stmtsToLiveness[Loc].isLive(E: 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>(Val: ty)) {
184 if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(Val: 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>(Val: E))
197 E = Ex->IgnoreParens();
198 if (const FullExpr *FE = dyn_cast<FullExpr>(Val: E)) {
199 E = FE->getSubExpr();
200 continue;
201 }
202 if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Val: 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(Old: Set, V: LookThroughExpr(E));
215}
216
217void TransferFunctions::Visit(Stmt *S) {
218 if (observer)
219 observer->observeStmt(S, currentBlock, V: val);
220
221 StmtVisitor<TransferFunctions>::Visit(S);
222
223 if (const auto *E = dyn_cast<Expr>(Val: S)) {
224 val.liveExprs = LV.ESetFact.remove(Old: val.liveExprs, V: 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>(Val: S)->getSubStmt();
235 break;
236 }
237 case Stmt::CXXMemberCallExprClass: {
238 // Include the implicit "this" pointer as being live.
239 CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(Val: S);
240 if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
241 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E: 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>(Val: S);
248 if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance)
249 val.liveDecls = LV.DSetFact.add(Old: val.liveDecls,
250 V: LV.analysisContext.getSelfDecl());
251 break;
252 }
253 case Stmt::DeclStmtClass: {
254 const DeclStmt *DS = cast<DeclStmt>(Val: S);
255 if (const VarDecl *VD = dyn_cast<VarDecl>(Val: DS->getSingleDecl())) {
256 for (const VariableArrayType* VA = FindVA(Ty: VD->getType());
257 VA != nullptr; VA = FindVA(Ty: VA->getElementType())) {
258 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E: 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>(Val: S)->getResultExpr();
267 if (!child) return;
268 if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(Val: child))
269 child = OV->getSourceExpr();
270 child = child->IgnoreParens();
271 val.liveExprs = LV.ESetFact.add(Old: val.liveExprs, V: child);
272 return;
273 }
274
275 // FIXME: These cases eventually shouldn't be needed.
276 case Stmt::ExprWithCleanupsClass: {
277 S = cast<ExprWithCleanups>(Val: S)->getSubExpr();
278 break;
279 }
280 case Stmt::CXXBindTemporaryExprClass: {
281 S = cast<CXXBindTemporaryExpr>(Val: 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(Set&: val.liveExprs, F&: LV.ESetFact, E: cast<IfStmt>(Val: 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(Set&: val.liveExprs, F&: LV.ESetFact, E: cast<WhileStmt>(Val: 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(Set&: val.liveExprs, F&: LV.ESetFact, E: cast<DoStmt>(Val: 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(Set&: val.liveExprs, F&: LV.ESetFact, E: cast<ForStmt>(Val: 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>(Val: Child))
324 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E);
325 }
326}
327
328static bool writeShouldKill(const VarDecl *VD) {
329 return VD && !VD->getType()->isReferenceType() &&
330 !isAlwaysAlive(D: VD);
331}
332
333void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
334 if (LV.killAtAssign && B->getOpcode() == BO_Assign) {
335 if (const auto *DR = dyn_cast<DeclRefExpr>(Val: 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>(Val: LHS)) {
347 const Decl* D = DR->getDecl();
348 bool Killed = false;
349
350 if (const BindingDecl* BD = dyn_cast<BindingDecl>(Val: D)) {
351 Killed = !BD->getType()->isReferenceType();
352 if (Killed) {
353 if (const auto *HV = BD->getHoldingVar())
354 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: HV);
355
356 val.liveBindings = LV.BSetFact.remove(Old: val.liveBindings, V: BD);
357 }
358 } else if (const auto *VD = dyn_cast<VarDecl>(Val: D)) {
359 Killed = writeShouldKill(VD);
360 if (Killed)
361 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: 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(BD: BE->getBlockDecl())) {
374 if (isAlwaysAlive(D: VD))
375 continue;
376 val.liveDecls = LV.DSetFact.add(Old: val.liveDecls, V: 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>(Val: D)) {
384 if (!InAssignment) {
385 if (const auto *HV = BD->getHoldingVar())
386 val.liveDecls = LV.DSetFact.add(Old: val.liveDecls, V: HV);
387
388 val.liveBindings = LV.BSetFact.add(Old: val.liveBindings, V: BD);
389 }
390 } else if (const auto *VD = dyn_cast<VarDecl>(Val: D)) {
391 if (!InAssignment && !isAlwaysAlive(D: VD))
392 val.liveDecls = LV.DSetFact.add(Old: val.liveDecls, V: VD);
393 }
394}
395
396void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
397 for (const auto *DI : DS->decls()) {
398 if (const auto *DD = dyn_cast<DecompositionDecl>(Val: DI)) {
399 for (const auto *BD : DD->bindings()) {
400 if (const auto *HV = BD->getHoldingVar())
401 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: HV);
402
403 val.liveBindings = LV.BSetFact.remove(Old: val.liveBindings, V: 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(Old: val.liveDecls, V: DD);
409 } else if (const auto *VD = dyn_cast<VarDecl>(Val: DI)) {
410 if (!isAlwaysAlive(D: VD))
411 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: 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>(Val: element)) {
423 VD = cast<VarDecl>(Val: DS->getSingleDecl());
424 }
425 else if ((DR = dyn_cast<DeclRefExpr>(Val: cast<Expr>(Val: element)->IgnoreParens()))) {
426 VD = cast<VarDecl>(Val: DR->getDecl());
427 }
428
429 if (VD) {
430 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: 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(Old: val.liveExprs, V: 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>(Val: UO->getSubExpr()->IgnoreParens())) {
470 const Decl *D = DR->getDecl();
471 if (isa<VarDecl>(Val: D) || isa<BindingDecl>(Val: 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(S: 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(Old: val.liveDecls, V: 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(S: 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(x: impl).analysisContext.getCFG();
512 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
513 getImpl(x: impl).runOnBlock(block: *it, val: getImpl(x: impl).blocksEndToLiveness[*it], obs: &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(Block: 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(valsA: val, valsB: LV->blocksBeginToLiveness[succ]);
558 }
559 }
560
561 if (!everAnalyzedBlock[block->getBlockID()])
562 everAnalyzedBlock[block->getBlockID()] = true;
563 else if (prevVal.equals(V: 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: block);
573 }
574
575 return std::unique_ptr<LiveVariables>(new LiveVariables(LV));
576}
577
578void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
579 getImpl(x: 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(x: it->first);
588 }
589 llvm::sort(C&: vec, Comp: [](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(x: *si);
607 }
608
609 llvm::sort(C&: declVec, Comp: [](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(OS&: llvm::errs(), SM: M);
618 llvm::errs() << ">\n";
619 }
620 }
621 llvm::errs() << "\n";
622}
623
624void LiveVariables::dumpExprLiveness(const SourceManager &M) {
625 getImpl(x: 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