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