1 //=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements Live Variables analysis for source-level CFGs.
11 //===----------------------------------------------------------------------===//
13 #include "clang/Analysis/Analyses/LiveVariables.h"
14 #include "clang/AST/Stmt.h"
15 #include "clang/AST/StmtVisitor.h"
16 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
17 #include "clang/Analysis/AnalysisDeclContext.h"
18 #include "clang/Analysis/CFG.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/PostOrderIterator.h"
21 #include "llvm/ADT/PriorityQueue.h"
22 #include "llvm/Support/raw_ostream.h"
26 using namespace clang;
30 class DataflowWorklist {
31 llvm::BitVector enqueuedBlocks;
32 PostOrderCFGView *POV;
33 llvm::PriorityQueue<const CFGBlock *, SmallVector<const CFGBlock *, 20>,
34 PostOrderCFGView::BlockOrderCompare> worklist;
37 DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx)
38 : enqueuedBlocks(cfg.getNumBlockIDs()),
39 POV(Ctx.getAnalysis<PostOrderCFGView>()),
40 worklist(POV->getComparator()) {}
42 void enqueueBlock(const CFGBlock *block);
43 void enqueuePredecessors(const CFGBlock *block);
45 const CFGBlock *dequeue();
50 void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) {
51 if (block && !enqueuedBlocks[block->getBlockID()]) {
52 enqueuedBlocks[block->getBlockID()] = true;
57 void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) {
58 for (CFGBlock::const_pred_iterator I = block->pred_begin(),
59 E = block->pred_end(); I != E; ++I) {
64 const CFGBlock *DataflowWorklist::dequeue() {
67 const CFGBlock *b = worklist.top();
69 enqueuedBlocks[b->getBlockID()] = false;
74 class LiveVariablesImpl {
76 AnalysisDeclContext &analysisContext;
77 llvm::ImmutableSet<const Stmt *>::Factory SSetFact;
78 llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
79 llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact;
80 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
81 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
82 llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
83 llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
84 const bool killAtAssign;
86 LiveVariables::LivenessValues
87 merge(LiveVariables::LivenessValues valsA,
88 LiveVariables::LivenessValues valsB);
90 LiveVariables::LivenessValues
91 runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val,
92 LiveVariables::Observer *obs = nullptr);
94 void dumpBlockLiveness(const SourceManager& M);
95 void dumpStmtLiveness(const SourceManager& M);
97 LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
98 : analysisContext(ac),
99 SSetFact(false), // Do not canonicalize ImmutableSets by default.
100 DSetFact(false), // This is a *major* performance win.
102 killAtAssign(KillAtAssign) {}
106 static LiveVariablesImpl &getImpl(void *x) {
107 return *((LiveVariablesImpl *) x);
110 //===----------------------------------------------------------------------===//
111 // Operations and queries on LivenessValues.
112 //===----------------------------------------------------------------------===//
114 bool LiveVariables::LivenessValues::isLive(const Stmt *S) const {
115 return liveStmts.contains(S);
118 bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {
119 if (const auto *DD = dyn_cast<DecompositionDecl>(D)) {
121 for (const BindingDecl *BD : DD->bindings())
122 alive |= liveBindings.contains(BD);
125 return liveDecls.contains(D);
129 template <typename SET>
130 SET mergeSets(SET A, SET B) {
134 for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
141 void LiveVariables::Observer::anchor() { }
143 LiveVariables::LivenessValues
144 LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
145 LiveVariables::LivenessValues valsB) {
147 llvm::ImmutableSetRef<const Stmt *>
148 SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()),
149 SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory());
152 llvm::ImmutableSetRef<const VarDecl *>
153 DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
154 DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
156 llvm::ImmutableSetRef<const BindingDecl *>
157 BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()),
158 BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory());
160 SSetRefA = mergeSets(SSetRefA, SSetRefB);
161 DSetRefA = mergeSets(DSetRefA, DSetRefB);
162 BSetRefA = mergeSets(BSetRefA, BSetRefB);
164 // asImmutableSet() canonicalizes the tree, allowing us to do an easy
165 // comparison afterwards.
166 return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),
167 DSetRefA.asImmutableSet(),
168 BSetRefA.asImmutableSet());
171 bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const {
172 return liveStmts == V.liveStmts && liveDecls == V.liveDecls;
175 //===----------------------------------------------------------------------===//
177 //===----------------------------------------------------------------------===//
179 static bool isAlwaysAlive(const VarDecl *D) {
180 return D->hasGlobalStorage();
183 bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
184 return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
187 bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
188 return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
191 bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) {
192 return getImpl(impl).stmtsToLiveness[Loc].isLive(S);
195 //===----------------------------------------------------------------------===//
196 // Dataflow computation.
197 //===----------------------------------------------------------------------===//
200 class TransferFunctions : public StmtVisitor<TransferFunctions> {
201 LiveVariablesImpl &LV;
202 LiveVariables::LivenessValues &val;
203 LiveVariables::Observer *observer;
204 const CFGBlock *currentBlock;
206 TransferFunctions(LiveVariablesImpl &im,
207 LiveVariables::LivenessValues &Val,
208 LiveVariables::Observer *Observer,
209 const CFGBlock *CurrentBlock)
210 : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
212 void VisitBinaryOperator(BinaryOperator *BO);
213 void VisitBlockExpr(BlockExpr *BE);
214 void VisitDeclRefExpr(DeclRefExpr *DR);
215 void VisitDeclStmt(DeclStmt *DS);
216 void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
217 void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
218 void VisitUnaryOperator(UnaryOperator *UO);
223 static const VariableArrayType *FindVA(QualType Ty) {
224 const Type *ty = Ty.getTypePtr();
225 while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
226 if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
227 if (VAT->getSizeExpr())
230 ty = VT->getElementType().getTypePtr();
236 static const Stmt *LookThroughStmt(const Stmt *S) {
238 if (const Expr *Ex = dyn_cast<Expr>(S))
239 S = Ex->IgnoreParens();
240 if (const FullExpr *FE = dyn_cast<FullExpr>(S)) {
241 S = FE->getSubExpr();
244 if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) {
245 S = OVE->getSourceExpr();
253 static void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set,
254 llvm::ImmutableSet<const Stmt *>::Factory &F,
256 Set = F.add(Set, LookThroughStmt(S));
259 void TransferFunctions::Visit(Stmt *S) {
261 observer->observeStmt(S, currentBlock, val);
263 StmtVisitor<TransferFunctions>::Visit(S);
266 val.liveStmts = LV.SSetFact.remove(val.liveStmts, S);
269 // Mark all children expressions live.
271 switch (S->getStmtClass()) {
274 case Stmt::StmtExprClass: {
275 // For statement expressions, look through the compound statement.
276 S = cast<StmtExpr>(S)->getSubStmt();
279 case Stmt::CXXMemberCallExprClass: {
280 // Include the implicit "this" pointer as being live.
281 CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
282 if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
283 AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj);
287 case Stmt::ObjCMessageExprClass: {
288 // In calls to super, include the implicit "self" pointer as being live.
289 ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S);
290 if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance)
291 val.liveDecls = LV.DSetFact.add(val.liveDecls,
292 LV.analysisContext.getSelfDecl());
295 case Stmt::DeclStmtClass: {
296 const DeclStmt *DS = cast<DeclStmt>(S);
297 if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
298 for (const VariableArrayType* VA = FindVA(VD->getType());
299 VA != nullptr; VA = FindVA(VA->getElementType())) {
300 AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr());
305 case Stmt::PseudoObjectExprClass: {
306 // A pseudo-object operation only directly consumes its result
308 Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
310 if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))
311 child = OV->getSourceExpr();
312 child = child->IgnoreParens();
313 val.liveStmts = LV.SSetFact.add(val.liveStmts, child);
317 // FIXME: These cases eventually shouldn't be needed.
318 case Stmt::ExprWithCleanupsClass: {
319 S = cast<ExprWithCleanups>(S)->getSubExpr();
322 case Stmt::CXXBindTemporaryExprClass: {
323 S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
326 case Stmt::UnaryExprOrTypeTraitExprClass: {
327 // No need to unconditionally visit subexpressions.
330 case Stmt::IfStmtClass: {
331 // If one of the branches is an expression rather than a compound
332 // statement, it will be bad if we mark it as live at the terminator
333 // of the if-statement (i.e., immediately after the condition expression).
334 AddLiveStmt(val.liveStmts, LV.SSetFact, cast<IfStmt>(S)->getCond());
337 case Stmt::WhileStmtClass: {
338 // If the loop body is an expression rather than a compound statement,
339 // it will be bad if we mark it as live at the terminator of the loop
340 // (i.e., immediately after the condition expression).
341 AddLiveStmt(val.liveStmts, LV.SSetFact, cast<WhileStmt>(S)->getCond());
344 case Stmt::DoStmtClass: {
345 // If the loop body is an expression rather than a compound statement,
346 // it will be bad if we mark it as live at the terminator of the loop
347 // (i.e., immediately after the condition expression).
348 AddLiveStmt(val.liveStmts, LV.SSetFact, cast<DoStmt>(S)->getCond());
351 case Stmt::ForStmtClass: {
352 // If the loop body is an expression rather than a compound statement,
353 // it will be bad if we mark it as live at the terminator of the loop
354 // (i.e., immediately after the condition expression).
355 AddLiveStmt(val.liveStmts, LV.SSetFact, cast<ForStmt>(S)->getCond());
361 for (Stmt *Child : S->children()) {
363 AddLiveStmt(val.liveStmts, LV.SSetFact, Child);
367 static bool writeShouldKill(const VarDecl *VD) {
368 return VD && !VD->getType()->isReferenceType() &&
372 void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
373 if (B->isAssignmentOp()) {
374 if (!LV.killAtAssign)
377 // Assigning to a variable?
378 Expr *LHS = B->getLHS()->IgnoreParens();
380 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
381 const Decl* D = DR->getDecl();
384 if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
385 Killed = !BD->getType()->isReferenceType();
387 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
388 } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
389 Killed = writeShouldKill(VD);
391 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
395 if (Killed && observer)
396 observer->observerKill(DR);
401 void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
402 for (const VarDecl *VD :
403 LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {
404 if (isAlwaysAlive(VD))
406 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
410 void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
411 const Decl* D = DR->getDecl();
412 bool InAssignment = LV.inAssignment[DR];
413 if (const auto *BD = dyn_cast<BindingDecl>(D)) {
415 val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);
416 } else if (const auto *VD = dyn_cast<VarDecl>(D)) {
417 if (!InAssignment && !isAlwaysAlive(VD))
418 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
422 void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
423 for (const auto *DI : DS->decls()) {
424 if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
425 for (const auto *BD : DD->bindings())
426 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
427 } else if (const auto *VD = dyn_cast<VarDecl>(DI)) {
428 if (!isAlwaysAlive(VD))
429 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
434 void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
435 // Kill the iteration variable.
436 DeclRefExpr *DR = nullptr;
437 const VarDecl *VD = nullptr;
439 Stmt *element = OS->getElement();
440 if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
441 VD = cast<VarDecl>(DS->getSingleDecl());
443 else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
444 VD = cast<VarDecl>(DR->getDecl());
448 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
450 observer->observerKill(DR);
454 void TransferFunctions::
455 VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
457 // While sizeof(var) doesn't technically extend the liveness of 'var', it
458 // does extent the liveness of metadata if 'var' is a VariableArrayType.
459 // We handle that special case here.
460 if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
463 const Expr *subEx = UE->getArgumentExpr();
464 if (subEx->getType()->isVariableArrayType()) {
465 assert(subEx->isLValue());
466 val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens());
470 void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
471 // Treat ++/-- as a kill.
472 // Note we don't actually have to do anything if we don't have an observer,
473 // since a ++/-- acts as both a kill and a "use".
477 switch (UO->getOpcode()) {
487 if (auto *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) {
488 const Decl *D = DR->getDecl();
489 if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
490 // Treat ++/-- as a kill.
491 observer->observerKill(DR);
496 LiveVariables::LivenessValues
497 LiveVariablesImpl::runOnBlock(const CFGBlock *block,
498 LiveVariables::LivenessValues val,
499 LiveVariables::Observer *obs) {
501 TransferFunctions TF(*this, val, obs, block);
503 // Visit the terminator (if any).
504 if (const Stmt *term = block->getTerminatorStmt())
505 TF.Visit(const_cast<Stmt*>(term));
507 // Apply the transfer function for all Stmts in the block.
508 for (CFGBlock::const_reverse_iterator it = block->rbegin(),
509 ei = block->rend(); it != ei; ++it) {
510 const CFGElement &elem = *it;
512 if (Optional<CFGAutomaticObjDtor> Dtor =
513 elem.getAs<CFGAutomaticObjDtor>()) {
514 val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());
518 if (!elem.getAs<CFGStmt>())
521 const Stmt *S = elem.castAs<CFGStmt>().getStmt();
522 TF.Visit(const_cast<Stmt*>(S));
523 stmtsToLiveness[S] = val;
528 void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
529 const CFG *cfg = getImpl(impl).analysisContext.getCFG();
530 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
531 getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
534 LiveVariables::LiveVariables(void *im) : impl(im) {}
536 LiveVariables::~LiveVariables() {
537 delete (LiveVariablesImpl*) impl;
541 LiveVariables::computeLiveness(AnalysisDeclContext &AC,
545 CFG *cfg = AC.getCFG();
549 // The analysis currently has scalability issues for very large CFGs.
550 // Bail out if it looks too large.
551 if (cfg->getNumBlockIDs() > 300000)
554 LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
556 // Construct the dataflow worklist. Enqueue the exit block as the
557 // start of the analysis.
558 DataflowWorklist worklist(*cfg, AC);
559 llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
561 // FIXME: we should enqueue using post order.
562 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
563 const CFGBlock *block = *it;
564 worklist.enqueueBlock(block);
566 // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
567 // We need to do this because we lack context in the reverse analysis
568 // to determine if a DeclRefExpr appears in such a context, and thus
569 // doesn't constitute a "use".
571 for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
573 if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) {
574 const Stmt* stmt = cs->getStmt();
575 if (const auto *BO = dyn_cast<BinaryOperator>(stmt)) {
576 if (BO->getOpcode() == BO_Assign) {
578 dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
579 LV->inAssignment[DR] = 1;
587 while (const CFGBlock *block = worklist.dequeue()) {
588 // Determine if the block's end value has changed. If not, we
589 // have nothing left to do for this block.
590 LivenessValues &prevVal = LV->blocksEndToLiveness[block];
592 // Merge the values of all successor blocks.
594 for (CFGBlock::const_succ_iterator it = block->succ_begin(),
595 ei = block->succ_end(); it != ei; ++it) {
596 if (const CFGBlock *succ = *it) {
597 val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
601 if (!everAnalyzedBlock[block->getBlockID()])
602 everAnalyzedBlock[block->getBlockID()] = true;
603 else if (prevVal.equals(val))
608 // Update the dataflow value for the start of this block.
609 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
611 // Enqueue the value to the predecessors.
612 worklist.enqueuePredecessors(block);
615 return new LiveVariables(LV);
618 void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
619 getImpl(impl).dumpBlockLiveness(M);
622 void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
623 std::vector<const CFGBlock *> vec;
624 for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
625 it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
627 vec.push_back(it->first);
629 llvm::sort(vec, [](const CFGBlock *A, const CFGBlock *B) {
630 return A->getBlockID() < B->getBlockID();
633 std::vector<const VarDecl*> declVec;
635 for (std::vector<const CFGBlock *>::iterator
636 it = vec.begin(), ei = vec.end(); it != ei; ++it) {
637 llvm::errs() << "\n[ B" << (*it)->getBlockID()
638 << " (live variables at block exit) ]\n";
640 LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
643 for (llvm::ImmutableSet<const VarDecl *>::iterator si =
644 vals.liveDecls.begin(),
645 se = vals.liveDecls.end(); si != se; ++si) {
646 declVec.push_back(*si);
649 llvm::sort(declVec, [](const Decl *A, const Decl *B) {
650 return A->getBeginLoc() < B->getBeginLoc();
653 for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
654 de = declVec.end(); di != de; ++di) {
655 llvm::errs() << " " << (*di)->getDeclName().getAsString()
657 (*di)->getLocation().print(llvm::errs(), M);
658 llvm::errs() << ">\n";
661 llvm::errs() << "\n";
664 void LiveVariables::dumpStmtLiveness(const SourceManager &M) {
665 getImpl(impl).dumpStmtLiveness(M);
668 void LiveVariablesImpl::dumpStmtLiveness(const SourceManager &M) {
669 // Don't iterate over blockEndsToLiveness directly because it's not sorted.
670 for (auto I : *analysisContext.getCFG()) {
672 llvm::errs() << "\n[ B" << I->getBlockID()
673 << " (live statements at block exit) ]\n";
674 for (auto S : blocksEndToLiveness[I].liveStmts) {
675 llvm::errs() << "\n";
678 llvm::errs() << "\n";
682 const void *LiveVariables::getTag() { static int x; return &x; }
683 const void *RelaxedLiveVariables::getTag() { static int x; return &x; }