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 E = E->IgnoreParens();
201 if (const FullExpr *FE = dyn_cast<FullExpr>(Val: E)) {
202 E = FE->getSubExpr();
203 continue;
204 }
205 if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Val: E)) {
206 E = OVE->getSourceExpr();
207 continue;
208 }
209 break;
210 }
211 return E;
212}
213
214static void AddLiveExpr(llvm::ImmutableSet<const Expr *> &Set,
215 llvm::ImmutableSet<const Expr *>::Factory &F,
216 const Expr *E) {
217 Set = F.add(Old: Set, V: LookThroughExpr(E));
218}
219
220/// Add as a live expression all individual conditions in a logical expression.
221/// For example, for the expression:
222/// "(a < b) || (c && d && ((e || f) != (g && h)))"
223/// the following expressions will be added as live:
224/// "a < b", "c", "d", "((e || f) != (g && h))"
225static void AddAllConditionalTerms(llvm::ImmutableSet<const Expr *> &Set,
226 llvm::ImmutableSet<const Expr *>::Factory &F,
227 const Expr *Cond) {
228 AddLiveExpr(Set, F, E: Cond);
229 if (auto const *BO = dyn_cast<BinaryOperator>(Val: Cond->IgnoreParens());
230 BO && BO->isLogicalOp()) {
231 AddAllConditionalTerms(Set, F, Cond: BO->getLHS());
232 AddAllConditionalTerms(Set, F, Cond: BO->getRHS());
233 }
234}
235
236void TransferFunctions::Visit(Stmt *S) {
237 if (observer)
238 observer->observeStmt(S, currentBlock, V: val);
239
240 StmtVisitor<TransferFunctions>::Visit(S);
241
242 if (const auto *E = dyn_cast<Expr>(Val: S)) {
243 val.liveExprs = LV.ESetFact.remove(Old: val.liveExprs, V: E);
244 }
245
246 // Mark all children expressions live.
247 // The "normal" case will be handled by iterating over 'S->children()' but
248 // before that we need this big 'switch' to handle the statement kinds where
249 // 'S->children()' isn't the exactly equal to the set of child expressions
250 // that we want to keep alive. (In some cases we need to skip some of the
251 // children, in other cases there are unusual child expressions that do not
252 // appear in 'S->children()'.)
253
254 switch (S->getStmtClass()) {
255 default:
256 break;
257 case Stmt::StmtExprClass: {
258 // For statement expressions, look through the compound statement.
259 S = cast<StmtExpr>(Val: S)->getSubStmt();
260 break;
261 }
262 case Stmt::CXXMemberCallExprClass: {
263 // Include the implicit "this" pointer as being live.
264 CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(Val: S);
265 if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
266 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E: ImplicitObj);
267 }
268 break;
269 }
270 case Stmt::ObjCMessageExprClass: {
271 // In calls to super, include the implicit "self" pointer as being live.
272 ObjCMessageExpr *CE = cast<ObjCMessageExpr>(Val: S);
273 if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance)
274 val.liveDecls = LV.DSetFact.add(Old: val.liveDecls,
275 V: LV.analysisContext.getSelfDecl());
276 break;
277 }
278 case Stmt::DeclStmtClass: {
279 const DeclStmt *DS = cast<DeclStmt>(Val: S);
280 if (const VarDecl *VD = dyn_cast<VarDecl>(Val: DS->getSingleDecl())) {
281 for (const VariableArrayType* VA = FindVA(Ty: VD->getType());
282 VA != nullptr; VA = FindVA(Ty: VA->getElementType())) {
283 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E: VA->getSizeExpr());
284 }
285 }
286 break;
287 }
288 case Stmt::AttributedStmtClass: {
289 // In an attributed statement, include the assumptions of the
290 // [[assume(...)]] attributes as being live.
291 AttributedStmt *AS = cast<AttributedStmt>(Val: S);
292 for (const auto *Attr : getSpecificAttrs<CXXAssumeAttr>(container: AS->getAttrs())) {
293 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E: Attr->getAssumption());
294 }
295 break;
296 }
297 case Stmt::PseudoObjectExprClass: {
298 // A pseudo-object operation only directly consumes its result
299 // expression.
300 Expr *child = cast<PseudoObjectExpr>(Val: S)->getResultExpr();
301 if (!child) return;
302 if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(Val: child))
303 child = OV->getSourceExpr();
304 child = child->IgnoreParens();
305 val.liveExprs = LV.ESetFact.add(Old: val.liveExprs, V: child);
306 return;
307 }
308
309 // FIXME: These cases eventually shouldn't be needed.
310 case Stmt::ExprWithCleanupsClass: {
311 S = cast<ExprWithCleanups>(Val: S)->getSubExpr();
312 break;
313 }
314 case Stmt::CXXBindTemporaryExprClass: {
315 S = cast<CXXBindTemporaryExpr>(Val: S)->getSubExpr();
316 break;
317 }
318 case Stmt::UnaryExprOrTypeTraitExprClass: {
319 // No need to unconditionally visit subexpressions.
320 return;
321 }
322 case Stmt::IfStmtClass: {
323 // If one of the branches is an expression rather than a compound
324 // statement, it will be bad if we mark it as live at the terminator
325 // of the if-statement (i.e., immediately after the condition expression).
326 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E: cast<IfStmt>(Val: S)->getCond());
327 return;
328 }
329 case Stmt::WhileStmtClass: {
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<WhileStmt>(Val: S)->getCond());
334 return;
335 }
336 case Stmt::DoStmtClass: {
337 // If the loop body is an expression rather than a compound statement,
338 // it will be bad if we mark it as live at the terminator of the loop
339 // (i.e., immediately after the condition expression).
340 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E: cast<DoStmt>(Val: S)->getCond());
341 return;
342 }
343 case Stmt::ForStmtClass: {
344 // If the loop body is an expression rather than a compound statement,
345 // it will be bad if we mark it as live at the terminator of the loop
346 // (i.e., immediately after the condition expression).
347 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E: cast<ForStmt>(Val: S)->getCond());
348 return;
349 }
350 case Stmt::ConditionalOperatorClass: {
351 // Keep not only direct children alive, but also all the short-circuited
352 // parts of the condition. Short-circuiting evaluation may cause the
353 // conditional operator evaluation to skip the evaluation of the entire
354 // condtion expression, so the value of the entire condition expression is
355 // never computed.
356 //
357 // This makes a difference when we compare exploded nodes coming from true
358 // and false expressions with no side effects: the only difference in the
359 // state is the value of (part of) the condition.
360 //
361 // BinaryConditionalOperatorClass ('x ?: y') is not affected because it
362 // explicitly calculates the value of the entire condition expression (to
363 // possibly use as a value for the "true expr") even if it is
364 // short-circuited.
365 auto const *CO = cast<ConditionalOperator>(Val: S);
366 AddAllConditionalTerms(Set&: val.liveExprs, F&: LV.ESetFact, Cond: CO->getCond());
367 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E: CO->getTrueExpr());
368 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E: CO->getFalseExpr());
369 return;
370 }
371 }
372
373 // Mark all child expressions live -- "normal" case.
374 for (Stmt *Child : S->children()) {
375 if (const auto *E = dyn_cast_or_null<Expr>(Val: Child))
376 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E);
377 }
378}
379
380static bool writeShouldKill(const VarDecl *VD) {
381 return VD && !VD->getType()->isReferenceType() &&
382 !isAlwaysAlive(D: VD);
383}
384
385void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
386 if (LV.killAtAssign && B->getOpcode() == BO_Assign) {
387 if (const auto *DR = dyn_cast<DeclRefExpr>(Val: B->getLHS()->IgnoreParens())) {
388 LV.inAssignment.insert(V: DR);
389 }
390 }
391 if (B->isAssignmentOp()) {
392 if (!LV.killAtAssign)
393 return;
394
395 // Assigning to a variable?
396 Expr *LHS = B->getLHS()->IgnoreParens();
397
398 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Val: LHS)) {
399 const Decl* D = DR->getDecl();
400 bool Killed = false;
401
402 if (const BindingDecl* BD = dyn_cast<BindingDecl>(Val: D)) {
403 Killed = !BD->getType()->isReferenceType();
404 if (Killed) {
405 if (const auto *HV = BD->getHoldingVar())
406 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: HV);
407
408 val.liveBindings = LV.BSetFact.remove(Old: val.liveBindings, V: BD);
409 }
410 } else if (const auto *VD = dyn_cast<VarDecl>(Val: D)) {
411 Killed = writeShouldKill(VD);
412 if (Killed)
413 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: VD);
414 }
415 }
416 }
417}
418
419void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
420 for (const VarDecl *VD :
421 LV.analysisContext.getReferencedBlockVars(BD: BE->getBlockDecl())) {
422 if (isAlwaysAlive(D: VD))
423 continue;
424 val.liveDecls = LV.DSetFact.add(Old: val.liveDecls, V: VD);
425 }
426}
427
428void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
429 const Decl* D = DR->getDecl();
430 bool InAssignment = LV.inAssignment.contains(V: DR);
431 if (const auto *BD = dyn_cast<BindingDecl>(Val: D)) {
432 if (!InAssignment) {
433 if (const auto *HV = BD->getHoldingVar())
434 val.liveDecls = LV.DSetFact.add(Old: val.liveDecls, V: HV);
435
436 val.liveBindings = LV.BSetFact.add(Old: val.liveBindings, V: BD);
437 }
438 } else if (const auto *VD = dyn_cast<VarDecl>(Val: D)) {
439 if (!InAssignment && !isAlwaysAlive(D: VD))
440 val.liveDecls = LV.DSetFact.add(Old: val.liveDecls, V: VD);
441 }
442}
443
444void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
445 for (const auto *DI : DS->decls()) {
446 if (const auto *DD = dyn_cast<DecompositionDecl>(Val: DI)) {
447 for (const auto *BD : DD->bindings()) {
448 if (const auto *HV = BD->getHoldingVar())
449 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: HV);
450
451 val.liveBindings = LV.BSetFact.remove(Old: val.liveBindings, V: BD);
452 }
453
454 // When a bindig to a tuple-like structure is created, the HoldingVar
455 // initializers have a DeclRefExpr to the DecompositionDecl.
456 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: DD);
457 } else if (const auto *VD = dyn_cast<VarDecl>(Val: DI)) {
458 if (!isAlwaysAlive(D: VD))
459 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: VD);
460 }
461 }
462}
463
464void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
465 // Kill the iteration variable.
466 DeclRefExpr *DR = nullptr;
467 const VarDecl *VD = nullptr;
468
469 Stmt *element = OS->getElement();
470 if (DeclStmt *DS = dyn_cast<DeclStmt>(Val: element)) {
471 VD = cast<VarDecl>(Val: DS->getSingleDecl());
472 }
473 else if ((DR = dyn_cast<DeclRefExpr>(Val: cast<Expr>(Val: element)->IgnoreParens()))) {
474 VD = cast<VarDecl>(Val: DR->getDecl());
475 }
476
477 if (VD) {
478 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: VD);
479 }
480}
481
482void TransferFunctions::
483VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
484{
485 // While sizeof(var) doesn't technically extend the liveness of 'var', it
486 // does extent the liveness of metadata if 'var' is a VariableArrayType.
487 // We handle that special case here.
488 if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
489 return;
490
491 const Expr *subEx = UE->getArgumentExpr();
492 if (subEx->getType()->isVariableArrayType()) {
493 assert(subEx->isLValue());
494 val.liveExprs = LV.ESetFact.add(Old: val.liveExprs, V: subEx->IgnoreParens());
495 }
496}
497
498LiveVariables::LivenessValues
499LiveVariablesImpl::runOnBlock(const CFGBlock *block,
500 LiveVariables::LivenessValues val,
501 LiveVariables::Observer *obs) {
502
503 TransferFunctions TF(*this, val, obs, block);
504
505 // Visit the terminator (if any).
506 if (const Stmt *term = block->getTerminatorStmt())
507 TF.Visit(S: const_cast<Stmt*>(term));
508
509 // Apply the transfer function for all Stmts in the block.
510 for (CFGBlock::const_reverse_iterator it = block->rbegin(),
511 ei = block->rend(); it != ei; ++it) {
512 const CFGElement &elem = *it;
513
514 if (std::optional<CFGAutomaticObjDtor> Dtor =
515 elem.getAs<CFGAutomaticObjDtor>()) {
516 val.liveDecls = DSetFact.add(Old: val.liveDecls, V: Dtor->getVarDecl());
517 continue;
518 }
519
520 if (!elem.getAs<CFGStmt>())
521 continue;
522
523 const Stmt *S = elem.castAs<CFGStmt>().getStmt();
524 TF.Visit(S: const_cast<Stmt*>(S));
525 stmtsToLiveness[S] = val;
526 }
527 return val;
528}
529
530void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
531 const CFG *cfg = getImpl(x: impl).analysisContext.getCFG();
532 for (CFGBlock *B : *cfg)
533 getImpl(x: impl).runOnBlock(block: B, val: getImpl(x: impl).blocksEndToLiveness[B], obs: &obs);
534}
535
536LiveVariables::LiveVariables(void *im) : impl(im) {}
537
538LiveVariables::~LiveVariables() {
539 delete (LiveVariablesImpl*) impl;
540}
541
542std::unique_ptr<LiveVariables>
543LiveVariables::computeLiveness(AnalysisDeclContext &AC, bool killAtAssign) {
544
545 // No CFG? Bail out.
546 CFG *cfg = AC.getCFG();
547 if (!cfg)
548 return nullptr;
549
550 // The analysis currently has scalability issues for very large CFGs.
551 // Bail out if it looks too large.
552 if (cfg->getNumBlockIDs() > 300000)
553 return nullptr;
554
555 LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
556
557 // Construct the dataflow worklist. Enqueue the exit block as the
558 // start of the analysis.
559 BackwardDataflowWorklist worklist(*cfg, AC);
560 llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
561
562 // FIXME: we should enqueue using post order.
563 for (const CFGBlock *B : cfg->nodes()) {
564 worklist.enqueueBlock(Block: B);
565 }
566
567 while (const CFGBlock *block = worklist.dequeue()) {
568 // Determine if the block's end value has changed. If not, we
569 // have nothing left to do for this block.
570 LivenessValues &prevVal = LV->blocksEndToLiveness[block];
571
572 // Merge the values of all successor blocks.
573 LivenessValues val;
574 for (const CFGBlock *succ : block->succs()) {
575 if (succ) {
576 val = LV->merge(valsA: val, valsB: LV->blocksBeginToLiveness[succ]);
577 }
578 }
579
580 if (!everAnalyzedBlock[block->getBlockID()])
581 everAnalyzedBlock[block->getBlockID()] = true;
582 else if (prevVal == val)
583 continue;
584
585 prevVal = val;
586
587 // Update the dataflow value for the start of this block.
588 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
589
590 // Enqueue the value to the predecessors.
591 worklist.enqueuePredecessors(Block: block);
592 }
593
594 return std::unique_ptr<LiveVariables>(new LiveVariables(LV));
595}
596
597void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
598 getImpl(x: impl).dumpBlockLiveness(M);
599}
600
601void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
602 std::vector<const CFGBlock *> vec;
603 vec.reserve(n: blocksEndToLiveness.size());
604 llvm::append_range(C&: vec, R: llvm::make_first_range(c&: blocksEndToLiveness));
605 llvm::sort(C&: vec, Comp: [](const CFGBlock *A, const CFGBlock *B) {
606 return A->getBlockID() < B->getBlockID();
607 });
608
609 std::vector<const VarDecl*> declVec;
610
611 for (const CFGBlock *block : vec) {
612 llvm::errs() << "\n[ B" << block->getBlockID()
613 << " (live variables at block exit) ]\n";
614 declVec.clear();
615 llvm::append_range(C&: declVec, R&: blocksEndToLiveness[block].liveDecls);
616 llvm::sort(C&: declVec, Comp: [](const Decl *A, const Decl *B) {
617 return A->getBeginLoc() < B->getBeginLoc();
618 });
619
620 for (const VarDecl *VD : declVec) {
621 llvm::errs() << " " << VD->getDeclName().getAsString() << " <";
622 VD->getLocation().print(OS&: llvm::errs(), SM: M);
623 llvm::errs() << ">\n";
624 }
625 }
626 llvm::errs() << "\n";
627}
628
629void LiveVariables::dumpExprLiveness(const SourceManager &M) {
630 getImpl(x: impl).dumpExprLiveness(M);
631}
632
633void LiveVariablesImpl::dumpExprLiveness(const SourceManager &M) {
634 const ASTContext &Ctx = analysisContext.getASTContext();
635 auto ByIDs = [&Ctx](const Expr *L, const Expr *R) {
636 return L->getID(Context: Ctx) < R->getID(Context: Ctx);
637 };
638
639 // Don't iterate over blockEndsToLiveness directly because it's not sorted.
640 for (const CFGBlock *B : *analysisContext.getCFG()) {
641 llvm::errs() << "\n[ B" << B->getBlockID()
642 << " (live expressions at block exit) ]\n";
643 std::vector<const Expr *> LiveExprs;
644 llvm::append_range(C&: LiveExprs, R&: blocksEndToLiveness[B].liveExprs);
645 llvm::sort(C&: LiveExprs, Comp: ByIDs);
646 for (const Expr *E : LiveExprs) {
647 llvm::errs() << "\n";
648 E->dump();
649 }
650 llvm::errs() << "\n";
651 }
652}
653
654const void *LiveVariables::getTag() { static int x; return &x; }
655const void *RelaxedLiveVariables::getTag() { static int x; return &x; }
656