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 }
343
344 // Mark all child expressions live -- "normal" case.
345 for (Stmt *Child : S->children()) {
346 if (const auto *E = dyn_cast_or_null<Expr>(Val: Child))
347 AddLiveExpr(Set&: val.liveExprs, F&: LV.ESetFact, E);
348 }
349}
350
351static bool writeShouldKill(const VarDecl *VD) {
352 return VD && !VD->getType()->isReferenceType() &&
353 !isAlwaysAlive(D: VD);
354}
355
356void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
357 if (LV.killAtAssign && B->getOpcode() == BO_Assign) {
358 if (const auto *DR = dyn_cast<DeclRefExpr>(Val: B->getLHS()->IgnoreParens())) {
359 LV.inAssignment.insert(V: DR);
360 }
361 }
362 if (B->isAssignmentOp()) {
363 if (!LV.killAtAssign)
364 return;
365
366 // Assigning to a variable?
367 Expr *LHS = B->getLHS()->IgnoreParens();
368
369 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Val: LHS)) {
370 const Decl* D = DR->getDecl();
371 bool Killed = false;
372
373 if (const BindingDecl* BD = dyn_cast<BindingDecl>(Val: D)) {
374 Killed = !BD->getType()->isReferenceType();
375 if (Killed) {
376 if (const auto *HV = BD->getHoldingVar())
377 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: HV);
378
379 val.liveBindings = LV.BSetFact.remove(Old: val.liveBindings, V: BD);
380 }
381 } else if (const auto *VD = dyn_cast<VarDecl>(Val: D)) {
382 Killed = writeShouldKill(VD);
383 if (Killed)
384 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: VD);
385 }
386 }
387 }
388}
389
390void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
391 for (const VarDecl *VD :
392 LV.analysisContext.getReferencedBlockVars(BD: BE->getBlockDecl())) {
393 if (isAlwaysAlive(D: VD))
394 continue;
395 val.liveDecls = LV.DSetFact.add(Old: val.liveDecls, V: VD);
396 }
397}
398
399void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
400 const Decl* D = DR->getDecl();
401 bool InAssignment = LV.inAssignment.contains(V: DR);
402 if (const auto *BD = dyn_cast<BindingDecl>(Val: D)) {
403 if (!InAssignment) {
404 if (const auto *HV = BD->getHoldingVar())
405 val.liveDecls = LV.DSetFact.add(Old: val.liveDecls, V: HV);
406
407 val.liveBindings = LV.BSetFact.add(Old: val.liveBindings, V: BD);
408 }
409 } else if (const auto *VD = dyn_cast<VarDecl>(Val: D)) {
410 if (!InAssignment && !isAlwaysAlive(D: VD))
411 val.liveDecls = LV.DSetFact.add(Old: val.liveDecls, V: VD);
412 }
413}
414
415void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
416 for (const auto *DI : DS->decls()) {
417 if (const auto *DD = dyn_cast<DecompositionDecl>(Val: DI)) {
418 for (const auto *BD : DD->bindings()) {
419 if (const auto *HV = BD->getHoldingVar())
420 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: HV);
421
422 val.liveBindings = LV.BSetFact.remove(Old: val.liveBindings, V: BD);
423 }
424
425 // When a bindig to a tuple-like structure is created, the HoldingVar
426 // initializers have a DeclRefExpr to the DecompositionDecl.
427 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: DD);
428 } else if (const auto *VD = dyn_cast<VarDecl>(Val: DI)) {
429 if (!isAlwaysAlive(D: VD))
430 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: VD);
431 }
432 }
433}
434
435void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
436 // Kill the iteration variable.
437 DeclRefExpr *DR = nullptr;
438 const VarDecl *VD = nullptr;
439
440 Stmt *element = OS->getElement();
441 if (DeclStmt *DS = dyn_cast<DeclStmt>(Val: element)) {
442 VD = cast<VarDecl>(Val: DS->getSingleDecl());
443 }
444 else if ((DR = dyn_cast<DeclRefExpr>(Val: cast<Expr>(Val: element)->IgnoreParens()))) {
445 VD = cast<VarDecl>(Val: DR->getDecl());
446 }
447
448 if (VD) {
449 val.liveDecls = LV.DSetFact.remove(Old: val.liveDecls, V: VD);
450 }
451}
452
453void TransferFunctions::
454VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
455{
456 // While sizeof(var) doesn't technically extend the liveness of 'var', it
457 // does extent the liveness of metadata if 'var' is a VariableArrayType.
458 // We handle that special case here.
459 if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
460 return;
461
462 const Expr *subEx = UE->getArgumentExpr();
463 if (subEx->getType()->isVariableArrayType()) {
464 assert(subEx->isLValue());
465 val.liveExprs = LV.ESetFact.add(Old: val.liveExprs, V: subEx->IgnoreParens());
466 }
467}
468
469LiveVariables::LivenessValues
470LiveVariablesImpl::runOnBlock(const CFGBlock *block,
471 LiveVariables::LivenessValues val,
472 LiveVariables::Observer *obs) {
473
474 TransferFunctions TF(*this, val, obs, block);
475
476 // Visit the terminator (if any).
477 if (const Stmt *term = block->getTerminatorStmt())
478 TF.Visit(S: const_cast<Stmt*>(term));
479
480 // Apply the transfer function for all Stmts in the block.
481 for (CFGBlock::const_reverse_iterator it = block->rbegin(),
482 ei = block->rend(); it != ei; ++it) {
483 const CFGElement &elem = *it;
484
485 if (std::optional<CFGAutomaticObjDtor> Dtor =
486 elem.getAs<CFGAutomaticObjDtor>()) {
487 val.liveDecls = DSetFact.add(Old: val.liveDecls, V: Dtor->getVarDecl());
488 continue;
489 }
490
491 if (!elem.getAs<CFGStmt>())
492 continue;
493
494 const Stmt *S = elem.castAs<CFGStmt>().getStmt();
495 TF.Visit(S: const_cast<Stmt*>(S));
496 stmtsToLiveness[S] = val;
497 }
498 return val;
499}
500
501void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
502 const CFG *cfg = getImpl(x: impl).analysisContext.getCFG();
503 for (CFGBlock *B : *cfg)
504 getImpl(x: impl).runOnBlock(block: B, val: getImpl(x: impl).blocksEndToLiveness[B], obs: &obs);
505}
506
507LiveVariables::LiveVariables(void *im) : impl(im) {}
508
509LiveVariables::~LiveVariables() {
510 delete (LiveVariablesImpl*) impl;
511}
512
513std::unique_ptr<LiveVariables>
514LiveVariables::computeLiveness(AnalysisDeclContext &AC, bool killAtAssign) {
515
516 // No CFG? Bail out.
517 CFG *cfg = AC.getCFG();
518 if (!cfg)
519 return nullptr;
520
521 // The analysis currently has scalability issues for very large CFGs.
522 // Bail out if it looks too large.
523 if (cfg->getNumBlockIDs() > 300000)
524 return nullptr;
525
526 LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
527
528 // Construct the dataflow worklist. Enqueue the exit block as the
529 // start of the analysis.
530 BackwardDataflowWorklist worklist(*cfg, AC);
531 llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
532
533 // FIXME: we should enqueue using post order.
534 for (const CFGBlock *B : cfg->nodes()) {
535 worklist.enqueueBlock(Block: B);
536 }
537
538 while (const CFGBlock *block = worklist.dequeue()) {
539 // Determine if the block's end value has changed. If not, we
540 // have nothing left to do for this block.
541 LivenessValues &prevVal = LV->blocksEndToLiveness[block];
542
543 // Merge the values of all successor blocks.
544 LivenessValues val;
545 for (const CFGBlock *succ : block->succs()) {
546 if (succ) {
547 val = LV->merge(valsA: val, valsB: LV->blocksBeginToLiveness[succ]);
548 }
549 }
550
551 if (!everAnalyzedBlock[block->getBlockID()])
552 everAnalyzedBlock[block->getBlockID()] = true;
553 else if (prevVal == val)
554 continue;
555
556 prevVal = val;
557
558 // Update the dataflow value for the start of this block.
559 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
560
561 // Enqueue the value to the predecessors.
562 worklist.enqueuePredecessors(Block: block);
563 }
564
565 return std::unique_ptr<LiveVariables>(new LiveVariables(LV));
566}
567
568void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
569 getImpl(x: impl).dumpBlockLiveness(M);
570}
571
572void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
573 std::vector<const CFGBlock *> vec;
574 vec.reserve(n: blocksEndToLiveness.size());
575 llvm::append_range(C&: vec, R: llvm::make_first_range(c&: blocksEndToLiveness));
576 llvm::sort(C&: vec, Comp: [](const CFGBlock *A, const CFGBlock *B) {
577 return A->getBlockID() < B->getBlockID();
578 });
579
580 std::vector<const VarDecl*> declVec;
581
582 for (const CFGBlock *block : vec) {
583 llvm::errs() << "\n[ B" << block->getBlockID()
584 << " (live variables at block exit) ]\n";
585 declVec.clear();
586 llvm::append_range(C&: declVec, R&: blocksEndToLiveness[block].liveDecls);
587 llvm::sort(C&: declVec, Comp: [](const Decl *A, const Decl *B) {
588 return A->getBeginLoc() < B->getBeginLoc();
589 });
590
591 for (const VarDecl *VD : declVec) {
592 llvm::errs() << " " << VD->getDeclName().getAsString() << " <";
593 VD->getLocation().print(OS&: llvm::errs(), SM: M);
594 llvm::errs() << ">\n";
595 }
596 }
597 llvm::errs() << "\n";
598}
599
600void LiveVariables::dumpExprLiveness(const SourceManager &M) {
601 getImpl(x: impl).dumpExprLiveness(M);
602}
603
604void LiveVariablesImpl::dumpExprLiveness(const SourceManager &M) {
605 const ASTContext &Ctx = analysisContext.getASTContext();
606 auto ByIDs = [&Ctx](const Expr *L, const Expr *R) {
607 return L->getID(Context: Ctx) < R->getID(Context: Ctx);
608 };
609
610 // Don't iterate over blockEndsToLiveness directly because it's not sorted.
611 for (const CFGBlock *B : *analysisContext.getCFG()) {
612 llvm::errs() << "\n[ B" << B->getBlockID()
613 << " (live expressions at block exit) ]\n";
614 std::vector<const Expr *> LiveExprs;
615 llvm::append_range(C&: LiveExprs, R&: blocksEndToLiveness[B].liveExprs);
616 llvm::sort(C&: LiveExprs, Comp: ByIDs);
617 for (const Expr *E : LiveExprs) {
618 llvm::errs() << "\n";
619 E->dump();
620 }
621 llvm::errs() << "\n";
622 }
623}
624
625const void *LiveVariables::getTag() { static int x; return &x; }
626const void *RelaxedLiveVariables::getTag() { static int x; return &x; }
627