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