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