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