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