clang 19.0.0git
LiveVariables.cpp
Go to the documentation of this file.
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
14#include "clang/AST/Stmt.h"
17#include "clang/Analysis/CFG.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/Support/raw_ostream.h"
21#include <algorithm>
22#include <optional>
23#include <vector>
24
25using namespace clang;
26
27namespace {
28class LiveVariablesImpl {
29public:
30 AnalysisDeclContext &analysisContext;
31 llvm::ImmutableSet<const Expr *>::Factory ESetFact;
32 llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
33 llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact;
34 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
35 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
36 llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
37 llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
38 const bool killAtAssign;
39
43
46 LiveVariables::Observer *obs = nullptr);
47
48 void dumpBlockLiveness(const SourceManager& M);
49 void dumpExprLiveness(const SourceManager& M);
50
51 LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
52 : analysisContext(ac),
53 ESetFact(false), // Do not canonicalize ImmutableSets by default.
54 DSetFact(false), // This is a *major* performance win.
55 BSetFact(false), killAtAssign(KillAtAssign) {}
56};
57} // namespace
58
59static LiveVariablesImpl &getImpl(void *x) {
60 return *((LiveVariablesImpl *) x);
61}
62
63//===----------------------------------------------------------------------===//
64// Operations and queries on LivenessValues.
65//===----------------------------------------------------------------------===//
66
68 return liveExprs.contains(E);
69}
70
72 if (const auto *DD = dyn_cast<DecompositionDecl>(D)) {
73 bool alive = false;
74 for (const BindingDecl *BD : DD->bindings())
75 alive |= liveBindings.contains(BD);
76
77 // Note: the only known case this condition is necessary, is when a bindig
78 // to a tuple-like structure is created. The HoldingVar initializers have a
79 // DeclRefExpr to the DecompositionDecl.
80 alive |= liveDecls.contains(DD);
81 return alive;
82 }
83 return liveDecls.contains(D);
84}
85
86namespace {
87 template <typename SET>
88 SET mergeSets(SET A, SET B) {
89 if (A.isEmpty())
90 return B;
91
92 for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
93 A = A.add(*it);
94 }
95 return A;
96 }
97} // namespace
98
99void LiveVariables::Observer::anchor() { }
100
102LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
104
105 llvm::ImmutableSetRef<const Expr *> SSetRefA(
106 valsA.liveExprs.getRootWithoutRetain(), ESetFact.getTreeFactory()),
107 SSetRefB(valsB.liveExprs.getRootWithoutRetain(),
108 ESetFact.getTreeFactory());
109
110 llvm::ImmutableSetRef<const VarDecl *>
111 DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
112 DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
113
114 llvm::ImmutableSetRef<const BindingDecl *>
115 BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()),
116 BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory());
117
118 SSetRefA = mergeSets(SSetRefA, SSetRefB);
119 DSetRefA = mergeSets(DSetRefA, DSetRefB);
120 BSetRefA = mergeSets(BSetRefA, BSetRefB);
121
122 // asImmutableSet() canonicalizes the tree, allowing us to do an easy
123 // comparison afterwards.
124 return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),
125 DSetRefA.asImmutableSet(),
126 BSetRefA.asImmutableSet());
127}
128
130 return liveExprs == V.liveExprs && liveDecls == V.liveDecls;
131}
132
133//===----------------------------------------------------------------------===//
134// Query methods.
135//===----------------------------------------------------------------------===//
136
137static bool isAlwaysAlive(const VarDecl *D) {
138 return D->hasGlobalStorage();
139}
140
141bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
142 return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
143}
144
145bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
146 return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
147}
148
149bool LiveVariables::isLive(const Stmt *Loc, const Expr *Val) {
150 return getImpl(impl).stmtsToLiveness[Loc].isLive(Val);
151}
152
153//===----------------------------------------------------------------------===//
154// Dataflow computation.
155//===----------------------------------------------------------------------===//
156
157namespace {
158class TransferFunctions : public StmtVisitor<TransferFunctions> {
159 LiveVariablesImpl &LV;
161 LiveVariables::Observer *observer;
162 const CFGBlock *currentBlock;
163public:
164 TransferFunctions(LiveVariablesImpl &im,
166 LiveVariables::Observer *Observer,
167 const CFGBlock *CurrentBlock)
168 : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
169
170 void VisitBinaryOperator(BinaryOperator *BO);
171 void VisitBlockExpr(BlockExpr *BE);
172 void VisitDeclRefExpr(DeclRefExpr *DR);
173 void VisitDeclStmt(DeclStmt *DS);
174 void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
175 void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
176 void VisitUnaryOperator(UnaryOperator *UO);
177 void Visit(Stmt *S);
178};
179} // namespace
180
182 const Type *ty = Ty.getTypePtr();
183 while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
184 if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
185 if (VAT->getSizeExpr())
186 return VAT;
187
188 ty = VT->getElementType().getTypePtr();
189 }
190
191 return nullptr;
192}
193
194static const Expr *LookThroughExpr(const Expr *E) {
195 while (E) {
196 if (const Expr *Ex = dyn_cast<Expr>(E))
197 E = Ex->IgnoreParens();
198 if (const FullExpr *FE = dyn_cast<FullExpr>(E)) {
199 E = FE->getSubExpr();
200 continue;
201 }
202 if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(E)) {
203 E = OVE->getSourceExpr();
204 continue;
205 }
206 break;
207 }
208 return E;
209}
210
211static void AddLiveExpr(llvm::ImmutableSet<const Expr *> &Set,
212 llvm::ImmutableSet<const Expr *>::Factory &F,
213 const Expr *E) {
214 Set = F.add(Set, LookThroughExpr(E));
215}
216
217void TransferFunctions::Visit(Stmt *S) {
218 if (observer)
219 observer->observeStmt(S, currentBlock, val);
220
222
223 if (const auto *E = dyn_cast<Expr>(S)) {
224 val.liveExprs = LV.ESetFact.remove(val.liveExprs, E);
225 }
226
227 // Mark all children expressions live.
228
229 switch (S->getStmtClass()) {
230 default:
231 break;
232 case Stmt::StmtExprClass: {
233 // For statement expressions, look through the compound statement.
234 S = cast<StmtExpr>(S)->getSubStmt();
235 break;
236 }
237 case Stmt::CXXMemberCallExprClass: {
238 // Include the implicit "this" pointer as being live.
239 CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
240 if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
241 AddLiveExpr(val.liveExprs, LV.ESetFact, ImplicitObj);
242 }
243 break;
244 }
245 case Stmt::ObjCMessageExprClass: {
246 // In calls to super, include the implicit "self" pointer as being live.
247 ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S);
249 val.liveDecls = LV.DSetFact.add(val.liveDecls,
250 LV.analysisContext.getSelfDecl());
251 break;
252 }
253 case Stmt::DeclStmtClass: {
254 const DeclStmt *DS = cast<DeclStmt>(S);
255 if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
256 for (const VariableArrayType* VA = FindVA(VD->getType());
257 VA != nullptr; VA = FindVA(VA->getElementType())) {
258 AddLiveExpr(val.liveExprs, LV.ESetFact, VA->getSizeExpr());
259 }
260 }
261 break;
262 }
263 case Stmt::PseudoObjectExprClass: {
264 // A pseudo-object operation only directly consumes its result
265 // expression.
266 Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
267 if (!child) return;
268 if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))
269 child = OV->getSourceExpr();
270 child = child->IgnoreParens();
271 val.liveExprs = LV.ESetFact.add(val.liveExprs, child);
272 return;
273 }
274
275 // FIXME: These cases eventually shouldn't be needed.
276 case Stmt::ExprWithCleanupsClass: {
277 S = cast<ExprWithCleanups>(S)->getSubExpr();
278 break;
279 }
280 case Stmt::CXXBindTemporaryExprClass: {
281 S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
282 break;
283 }
284 case Stmt::UnaryExprOrTypeTraitExprClass: {
285 // No need to unconditionally visit subexpressions.
286 return;
287 }
288 case Stmt::IfStmtClass: {
289 // If one of the branches is an expression rather than a compound
290 // statement, it will be bad if we mark it as live at the terminator
291 // of the if-statement (i.e., immediately after the condition expression).
292 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<IfStmt>(S)->getCond());
293 return;
294 }
295 case Stmt::WhileStmtClass: {
296 // If the loop body is an expression rather than a compound statement,
297 // it will be bad if we mark it as live at the terminator of the loop
298 // (i.e., immediately after the condition expression).
299 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<WhileStmt>(S)->getCond());
300 return;
301 }
302 case Stmt::DoStmtClass: {
303 // If the loop body is an expression rather than a compound statement,
304 // it will be bad if we mark it as live at the terminator of the loop
305 // (i.e., immediately after the condition expression).
306 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<DoStmt>(S)->getCond());
307 return;
308 }
309 case Stmt::ForStmtClass: {
310 // If the loop body is an expression rather than a compound statement,
311 // it will be bad if we mark it as live at the terminator of the loop
312 // (i.e., immediately after the condition expression).
313 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<ForStmt>(S)->getCond());
314 return;
315 }
316
317 }
318
319 // HACK + FIXME: What is this? One could only guess that this is an attempt to
320 // fish for live values, for example, arguments from a call expression.
321 // Maybe we could take inspiration from UninitializedVariable analysis?
322 for (Stmt *Child : S->children()) {
323 if (const auto *E = dyn_cast_or_null<Expr>(Child))
324 AddLiveExpr(val.liveExprs, LV.ESetFact, E);
325 }
326}
327
328static bool writeShouldKill(const VarDecl *VD) {
329 return VD && !VD->getType()->isReferenceType() &&
330 !isAlwaysAlive(VD);
331}
332
333void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
334 if (LV.killAtAssign && B->getOpcode() == BO_Assign) {
335 if (const auto *DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParens())) {
336 LV.inAssignment[DR] = 1;
337 }
338 }
339 if (B->isAssignmentOp()) {
340 if (!LV.killAtAssign)
341 return;
342
343 // Assigning to a variable?
344 Expr *LHS = B->getLHS()->IgnoreParens();
345
346 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
347 const Decl* D = DR->getDecl();
348 bool Killed = false;
349
350 if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
351 Killed = !BD->getType()->isReferenceType();
352 if (Killed) {
353 if (const auto *HV = BD->getHoldingVar())
354 val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);
355
356 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
357 }
358 } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
359 Killed = writeShouldKill(VD);
360 if (Killed)
361 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
362
363 }
364
365 if (Killed && observer)
366 observer->observerKill(DR);
367 }
368 }
369}
370
371void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
372 for (const VarDecl *VD :
373 LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
374 if (isAlwaysAlive(VD))
375 continue;
376 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
377 }
378}
379
380void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
381 const Decl* D = DR->getDecl();
382 bool InAssignment = LV.inAssignment[DR];
383 if (const auto *BD = dyn_cast<BindingDecl>(D)) {
384 if (!InAssignment) {
385 if (const auto *HV = BD->getHoldingVar())
386 val.liveDecls = LV.DSetFact.add(val.liveDecls, HV);
387
388 val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);
389 }
390 } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
391 if (!InAssignment && !isAlwaysAlive(VD))
392 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
393 }
394}
395
396void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
397 for (const auto *DI : DS->decls()) {
398 if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
399 for (const auto *BD : DD->bindings()) {
400 if (const auto *HV = BD->getHoldingVar())
401 val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);
402
403 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
404 }
405
406 // When a bindig to a tuple-like structure is created, the HoldingVar
407 // initializers have a DeclRefExpr to the DecompositionDecl.
408 val.liveDecls = LV.DSetFact.remove(val.liveDecls, DD);
409 } else if (const auto *VD = dyn_cast<VarDecl>(DI)) {
410 if (!isAlwaysAlive(VD))
411 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
412 }
413 }
414}
415
416void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
417 // Kill the iteration variable.
418 DeclRefExpr *DR = nullptr;
419 const VarDecl *VD = nullptr;
420
421 Stmt *element = OS->getElement();
422 if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
423 VD = cast<VarDecl>(DS->getSingleDecl());
424 }
425 else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
426 VD = cast<VarDecl>(DR->getDecl());
427 }
428
429 if (VD) {
430 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
431 if (observer && DR)
432 observer->observerKill(DR);
433 }
434}
435
436void TransferFunctions::
437VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
438{
439 // While sizeof(var) doesn't technically extend the liveness of 'var', it
440 // does extent the liveness of metadata if 'var' is a VariableArrayType.
441 // We handle that special case here.
442 if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
443 return;
444
445 const Expr *subEx = UE->getArgumentExpr();
446 if (subEx->getType()->isVariableArrayType()) {
447 assert(subEx->isLValue());
448 val.liveExprs = LV.ESetFact.add(val.liveExprs, subEx->IgnoreParens());
449 }
450}
451
452void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
453 // Treat ++/-- as a kill.
454 // Note we don't actually have to do anything if we don't have an observer,
455 // since a ++/-- acts as both a kill and a "use".
456 if (!observer)
457 return;
458
459 switch (UO->getOpcode()) {
460 default:
461 return;
462 case UO_PostInc:
463 case UO_PostDec:
464 case UO_PreInc:
465 case UO_PreDec:
466 break;
467 }
468
469 if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) {
470 const Decl *D = DR->getDecl();
471 if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
472 // Treat ++/-- as a kill.
473 observer->observerKill(DR);
474 }
475 }
476}
477
479LiveVariablesImpl::runOnBlock(const CFGBlock *block,
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(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(val.liveDecls, 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(const_cast<Stmt*>(S));
505 stmtsToLiveness[S] = val;
506 }
507 return val;
508}
509
511 const CFG *cfg = getImpl(impl).analysisContext.getCFG();
512 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
513 getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
514}
515
516LiveVariables::LiveVariables(void *im) : impl(im) {}
517
519 delete (LiveVariablesImpl*) impl;
520}
521
522std::unique_ptr<LiveVariables>
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(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 (CFGBlock::const_succ_iterator it = block->succ_begin(),
555 ei = block->succ_end(); it != ei; ++it) {
556 if (const CFGBlock *succ = *it) {
557 val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
558 }
559 }
560
561 if (!everAnalyzedBlock[block->getBlockID()])
562 everAnalyzedBlock[block->getBlockID()] = true;
563 else if (prevVal.equals(val))
564 continue;
565
566 prevVal = val;
567
568 // Update the dataflow value for the start of this block.
569 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
570
571 // Enqueue the value to the predecessors.
572 worklist.enqueuePredecessors(block);
573 }
574
575 return std::unique_ptr<LiveVariables>(new LiveVariables(LV));
576}
577
579 getImpl(impl).dumpBlockLiveness(M);
580}
581
582void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
583 std::vector<const CFGBlock *> vec;
584 for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
585 it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
586 it != ei; ++it) {
587 vec.push_back(it->first);
588 }
589 llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) {
590 return A->getBlockID() < B->getBlockID();
591 });
592
593 std::vector<const VarDecl*> declVec;
594
595 for (std::vector<const CFGBlock *>::iterator
596 it = vec.begin(), ei = vec.end(); it != ei; ++it) {
597 llvm::errs() << "\n[ B" << (*it)->getBlockID()
598 << " (live variables at block exit) ]\n";
599
600 LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
601 declVec.clear();
602
603 for (llvm::ImmutableSet<const VarDecl *>::iterator si =
604 vals.liveDecls.begin(),
605 se = vals.liveDecls.end(); si != se; ++si) {
606 declVec.push_back(*si);
607 }
608
609 llvm::sort(declVec, [](const Decl *A, const Decl *B) {
610 return A->getBeginLoc() < B->getBeginLoc();
611 });
612
613 for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
614 de = declVec.end(); di != de; ++di) {
615 llvm::errs() << " " << (*di)->getDeclName().getAsString()
616 << " <";
617 (*di)->getLocation().print(llvm::errs(), M);
618 llvm::errs() << ">\n";
619 }
620 }
621 llvm::errs() << "\n";
622}
623
625 getImpl(impl).dumpExprLiveness(M);
626}
627
628void LiveVariablesImpl::dumpExprLiveness(const SourceManager &M) {
629 // Don't iterate over blockEndsToLiveness directly because it's not sorted.
630 for (const CFGBlock *B : *analysisContext.getCFG()) {
631
632 llvm::errs() << "\n[ B" << B->getBlockID()
633 << " (live expressions at block exit) ]\n";
634 for (const Expr *E : blocksEndToLiveness[B].liveExprs) {
635 llvm::errs() << "\n";
636 E->dump();
637 }
638 llvm::errs() << "\n";
639 }
640}
641
642const void *LiveVariables::getTag() { static int x; return &x; }
643const void *RelaxedLiveVariables::getTag() { static int x; return &x; }
#define V(N, I)
Definition: ASTContext.h:3285
This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...
static const VariableArrayType * FindVA(const Type *t)
Definition: CFG.cpp:1413
static bool writeShouldKill(const VarDecl *VD)
static void AddLiveExpr(llvm::ImmutableSet< const Expr * > &Set, llvm::ImmutableSet< const Expr * >::Factory &F, const Expr *E)
static LiveVariablesImpl & getImpl(void *x)
static const Expr * LookThroughExpr(const Expr *E)
static bool isAlwaysAlive(const VarDecl *D)
const CFGBlock * CurrentBlock
Definition: Logger.cpp:26
SourceLocation Loc
Definition: SemaObjC.cpp:755
static bool runOnBlock(const CFGBlock *block, const CFG &cfg, AnalysisDeclContext &ac, CFGBlockValues &vals, const ClassifyRefs &classification, llvm::BitVector &wasAnalyzed, UninitVariablesHandler &handler)
AnalysisDeclContext contains the context data for the function, method or block under analysis.
Represents an array type, per C99 6.7.5.2 - Array Declarators.
Definition: Type.h:3518
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3840
Expr * getLHS() const
Definition: Expr.h:3889
static bool isAssignmentOp(Opcode Opc)
Definition: Expr.h:3975
Opcode getOpcode() const
Definition: Expr.h:3884
A binding in a decomposition declaration.
Definition: DeclCXX.h:4107
BlockExpr - Adaptor class for mixing a BlockDecl with expressions.
Definition: Expr.h:6173
const BlockDecl * getBlockDecl() const
Definition: Expr.h:6185
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
Definition: CFG.h:417
Represents a single basic block in a source-level CFG.
Definition: CFG.h:604
succ_iterator succ_end()
Definition: CFG.h:985
reverse_iterator rbegin()
Definition: CFG.h:909
reverse_iterator rend()
Definition: CFG.h:910
succ_iterator succ_begin()
Definition: CFG.h:984
Stmt * getTerminatorStmt()
Definition: CFG.h:1081
unsigned getBlockID() const
Definition: CFG.h:1105
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:960
Represents a top-level expression in a basic block.
Definition: CFG.h:55
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type.
Definition: CFG.h:99
std::optional< T > getAs() const
Convert to the specified CFGElement type, returning std::nullopt if this CFGElement is not of the des...
Definition: CFG.h:109
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1214
iterator end()
Definition: CFG.h:1295
iterator begin()
Definition: CFG.h:1294
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:1402
llvm::iterator_range< iterator > nodes()
Definition: CFG.h:1302
Represents a call to a member function that may be written either with member call syntax (e....
Definition: ExprCXX.h:176
Expr * getImplicitObjectArgument() const
Retrieve the implicit object argument for the member call.
Definition: ExprCXX.cpp:654
void enqueueBlock(const CFGBlock *Block)
const CFGBlock * dequeue()
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:1260
ValueDecl * getDecl()
Definition: Expr.h:1328
DeclStmt - Adaptor class for mixing declarations with statements and expressions.
Definition: Stmt.h:1497
decl_range decls()
Definition: Stmt.h:1545
const Decl * getSingleDecl() const
Definition: Stmt.h:1512
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
static void add(Kind k)
Definition: DeclBase.cpp:202
void dump() const
Definition: ASTDumper.cpp:220
SourceLocation getBeginLoc() const LLVM_READONLY
Definition: DeclBase.h:437
This represents one expression.
Definition: Expr.h:110
Expr * IgnoreParens() LLVM_READONLY
Skip past any parentheses which might surround this expression until reaching a fixed point.
Definition: Expr.cpp:3055
bool isLValue() const
isLValue - True if this expression is an "l-value" according to the rules of the current language.
Definition: Expr.h:277
QualType getType() const
Definition: Expr.h:142
FullExpr - Represents a "full-expression" node.
Definition: Expr.h:1039
llvm::ImmutableSet< const BindingDecl * > liveBindings
Definition: LiveVariables.h:35
llvm::ImmutableSet< const Expr * > liveExprs
Definition: LiveVariables.h:33
llvm::ImmutableSet< const VarDecl * > liveDecls
Definition: LiveVariables.h:34
bool isLive(const Expr *E) const
bool equals(const LivenessValues &V) const
void dumpExprLiveness(const SourceManager &M)
Print to stderr the expression liveness information associated with each basic block.
void dumpBlockLiveness(const SourceManager &M)
Print to stderr the variable liveness information associated with each basic block.
void runOnAllBlocks(Observer &obs)
static const void * getTag()
bool isLive(const CFGBlock *B, const VarDecl *D)
Return true if a variable is live at the end of a specified block.
static std::unique_ptr< LiveVariables > computeLiveness(AnalysisDeclContext &analysisContext, bool killAtAssign)
Compute the liveness information for a given CFG.
Represents Objective-C's collection statement.
Definition: StmtObjC.h:23
An expression that sends a message to the given Objective-C object or class.
Definition: ExprObjC.h:945
@ SuperInstance
The receiver is the instance of the superclass object.
Definition: ExprObjC.h:959
ReceiverKind getReceiverKind() const
Determine the kind of receiver that this message is being sent to.
Definition: ExprObjC.h:1234
OpaqueValueExpr - An expression referring to an opaque object of a fixed type and value class.
Definition: Expr.h:1168
A (possibly-)qualified type.
Definition: Type.h:940
const Type * getTypePtr() const
Retrieves a pointer to the underlying (unqualified) type.
Definition: Type.h:7359
static const void * getTag()
This class handles loading and caching of source files into memory.
RetTy Visit(PTR(Stmt) S, ParamTys... P)
Definition: StmtVisitor.h:44
StmtVisitor - This class implements a simple visitor for Stmt subclasses.
Definition: StmtVisitor.h:185
Stmt - This represents one statement.
Definition: Stmt.h:84
The base class of the type hierarchy.
Definition: Type.h:1813
bool isReferenceType() const
Definition: Type.h:7624
bool isVariableArrayType() const
Definition: Type.h:7690
UnaryExprOrTypeTraitExpr - expression with either a type or (unevaluated) expression operand.
Definition: Expr.h:2568
bool isArgumentType() const
Definition: Expr.h:2610
UnaryExprOrTypeTrait getKind() const
Definition: Expr.h:2600
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
Definition: Expr.h:2183
Expr * getSubExpr() const
Definition: Expr.h:2228
Opcode getOpcode() const
Definition: Expr.h:2223
QualType getType() const
Definition: Decl.h:717
Represents a variable declaration or definition.
Definition: Decl.h:918
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
Definition: Decl.h:1213
Represents a C array with a specified size that is not an integer-constant-expression.
Definition: Type.h:3747
The JSON file list parser is used to communicate input to InstallAPI.
#define false
Definition: stdbool.h:26
A worklist implementation for backward dataflow analysis.
void enqueuePredecessors(const CFGBlock *Block)