head 1.1; branch 1.1.1; access; symbols netbsd-11-0-RC4:1.1.1.9 netbsd-11-0-RC3:1.1.1.9 netbsd-11-0-RC2:1.1.1.9 netbsd-11-0-RC1:1.1.1.9 perseant-exfatfs-base-20250801:1.1.1.9 netbsd-11:1.1.1.9.0.10 netbsd-11-base:1.1.1.9 netbsd-10-1-RELEASE:1.1.1.9 perseant-exfatfs-base-20240630:1.1.1.9 perseant-exfatfs:1.1.1.9.0.8 perseant-exfatfs-base:1.1.1.9 netbsd-8-3-RELEASE:1.1.1.7 netbsd-9-4-RELEASE:1.1.1.8 netbsd-10-0-RELEASE:1.1.1.9 netbsd-10-0-RC6:1.1.1.9 netbsd-10-0-RC5:1.1.1.9 netbsd-10-0-RC4:1.1.1.9 netbsd-10-0-RC3:1.1.1.9 netbsd-10-0-RC2:1.1.1.9 netbsd-10-0-RC1:1.1.1.9 netbsd-10:1.1.1.9.0.6 netbsd-10-base:1.1.1.9 netbsd-9-3-RELEASE:1.1.1.8 cjep_sun2x:1.1.1.9.0.4 cjep_sun2x-base:1.1.1.9 cjep_staticlib_x-base1:1.1.1.9 netbsd-9-2-RELEASE:1.1.1.8 cjep_staticlib_x:1.1.1.9.0.2 cjep_staticlib_x-base:1.1.1.9 netbsd-9-1-RELEASE:1.1.1.8 phil-wifi-20200421:1.1.1.9 phil-wifi-20200411:1.1.1.9 phil-wifi-20200406:1.1.1.9 netbsd-8-2-RELEASE:1.1.1.7 netbsd-9-0-RELEASE:1.1.1.8 netbsd-9-0-RC2:1.1.1.8 netbsd-9-0-RC1:1.1.1.8 netbsd-9:1.1.1.8.0.2 netbsd-9-base:1.1.1.8 phil-wifi-20190609:1.1.1.8 netbsd-8-1-RELEASE:1.1.1.7 netbsd-8-1-RC1:1.1.1.7 pgoyette-compat-merge-20190127:1.1.1.7.12.1 pgoyette-compat-20190127:1.1.1.8 pgoyette-compat-20190118:1.1.1.8 pgoyette-compat-1226:1.1.1.8 pgoyette-compat-1126:1.1.1.8 pgoyette-compat-1020:1.1.1.8 pgoyette-compat-0930:1.1.1.8 pgoyette-compat-0906:1.1.1.8 netbsd-7-2-RELEASE:1.1.1.4.2.1 pgoyette-compat-0728:1.1.1.8 clang-337282:1.1.1.8 netbsd-8-0-RELEASE:1.1.1.7 phil-wifi:1.1.1.7.0.14 phil-wifi-base:1.1.1.7 pgoyette-compat-0625:1.1.1.7 netbsd-8-0-RC2:1.1.1.7 pgoyette-compat-0521:1.1.1.7 pgoyette-compat-0502:1.1.1.7 pgoyette-compat-0422:1.1.1.7 netbsd-8-0-RC1:1.1.1.7 pgoyette-compat-0415:1.1.1.7 pgoyette-compat-0407:1.1.1.7 pgoyette-compat-0330:1.1.1.7 pgoyette-compat-0322:1.1.1.7 pgoyette-compat-0315:1.1.1.7 netbsd-7-1-2-RELEASE:1.1.1.4.2.1 pgoyette-compat:1.1.1.7.0.12 pgoyette-compat-base:1.1.1.7 netbsd-7-1-1-RELEASE:1.1.1.4.2.1 clang-319952:1.1.1.7 matt-nb8-mediatek:1.1.1.7.0.10 matt-nb8-mediatek-base:1.1.1.7 clang-309604:1.1.1.7 perseant-stdc-iso10646:1.1.1.7.0.8 perseant-stdc-iso10646-base:1.1.1.7 netbsd-8:1.1.1.7.0.6 netbsd-8-base:1.1.1.7 prg-localcount2-base3:1.1.1.7 prg-localcount2-base2:1.1.1.7 prg-localcount2-base1:1.1.1.7 prg-localcount2:1.1.1.7.0.4 prg-localcount2-base:1.1.1.7 pgoyette-localcount-20170426:1.1.1.7 bouyer-socketcan-base1:1.1.1.7 pgoyette-localcount-20170320:1.1.1.7 netbsd-7-1:1.1.1.4.2.1.0.6 netbsd-7-1-RELEASE:1.1.1.4.2.1 netbsd-7-1-RC2:1.1.1.4.2.1 clang-294123:1.1.1.7 netbsd-7-nhusb-base-20170116:1.1.1.4.2.1 bouyer-socketcan:1.1.1.7.0.2 bouyer-socketcan-base:1.1.1.7 clang-291444:1.1.1.7 pgoyette-localcount-20170107:1.1.1.6 netbsd-7-1-RC1:1.1.1.4.2.1 pgoyette-localcount-20161104:1.1.1.6 netbsd-7-0-2-RELEASE:1.1.1.4.2.1 localcount-20160914:1.1.1.6 netbsd-7-nhusb:1.1.1.4.2.1.0.4 netbsd-7-nhusb-base:1.1.1.4.2.1 clang-280599:1.1.1.6 pgoyette-localcount-20160806:1.1.1.6 pgoyette-localcount-20160726:1.1.1.6 pgoyette-localcount:1.1.1.6.0.2 pgoyette-localcount-base:1.1.1.6 netbsd-7-0-1-RELEASE:1.1.1.4.2.1 clang-261930:1.1.1.6 netbsd-7-0:1.1.1.4.2.1.0.2 netbsd-7-0-RELEASE:1.1.1.4.2.1 netbsd-7-0-RC3:1.1.1.4.2.1 netbsd-7-0-RC2:1.1.1.4.2.1 netbsd-7-0-RC1:1.1.1.4.2.1 clang-237755:1.1.1.5 clang-232565:1.1.1.5 clang-227398:1.1.1.5 tls-maxphys-base:1.1.1.4 tls-maxphys:1.1.1.4.0.4 netbsd-7:1.1.1.4.0.2 netbsd-7-base:1.1.1.4 clang-215315:1.1.1.4 clang-209886:1.1.1.3 yamt-pagecache:1.1.1.2.0.4 yamt-pagecache-base9:1.1.1.2 tls-earlyentropy:1.1.1.2.0.2 tls-earlyentropy-base:1.1.1.3 riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.1.1.2 riastradh-drm2-base3:1.1.1.2 clang-202566:1.1.1.2 clang-201163:1.1.1.2 clang-199312:1.1.1.2 clang-198450:1.1.1.2 clang-196603:1.1.1.1 clang-195771:1.1.1.1 LLVM:1.1.1; locks; strict; comment @// @; 1.1 date 2013.11.28.14.14.49; author joerg; state Exp; branches 1.1.1.1; next ; commitid ow8OybrawrB1f3fx; 1.1.1.1 date 2013.11.28.14.14.49; author joerg; state Exp; branches; next 1.1.1.2; commitid ow8OybrawrB1f3fx; 1.1.1.2 date 2014.01.05.15.38.38; author joerg; state Exp; branches 1.1.1.2.2.1 1.1.1.2.4.1; next 1.1.1.3; commitid wh3aCSIWykURqWjx; 1.1.1.3 date 2014.05.30.18.14.40; author joerg; state Exp; branches; next 1.1.1.4; commitid 8q0kdlBlCn09GACx; 1.1.1.4 date 2014.08.10.17.08.27; author joerg; state Exp; branches 1.1.1.4.2.1 1.1.1.4.4.1; next 1.1.1.5; commitid N85tXAN6Ex9VZPLx; 1.1.1.5 date 2015.01.29.19.57.33; author joerg; state Exp; branches; next 1.1.1.6; commitid mlISSizlPKvepX7y; 1.1.1.6 date 2016.02.27.22.11.54; author joerg; state Exp; branches 1.1.1.6.2.1; next 1.1.1.7; commitid tIimz3oDlh1NpBWy; 1.1.1.7 date 2017.01.11.10.34.44; author joerg; state Exp; branches 1.1.1.7.12.1 1.1.1.7.14.1; next 1.1.1.8; commitid CNnUNfII1jgNmxBz; 1.1.1.8 date 2018.07.17.18.31.08; author joerg; state Exp; branches; next 1.1.1.9; commitid wDzL46ALjrCZgwKA; 1.1.1.9 date 2019.11.13.22.19.20; author joerg; state dead; branches; next ; commitid QD8YATxuNG34YJKB; 1.1.1.2.2.1 date 2014.08.10.07.08.07; author tls; state Exp; branches; next ; commitid t01A1TLTYxkpGMLx; 1.1.1.2.4.1 date 2014.01.05.15.38.38; author yamt; state dead; branches; next 1.1.1.2.4.2; commitid WSrDtL5nYAUyiyBx; 1.1.1.2.4.2 date 2014.05.22.16.18.26; author yamt; state Exp; branches; next ; commitid WSrDtL5nYAUyiyBx; 1.1.1.4.2.1 date 2015.06.04.20.04.27; author snj; state Exp; branches; next ; commitid yRnjq9fueSo6n9oy; 1.1.1.4.4.1 date 2014.08.10.17.08.27; author tls; state dead; branches; next 1.1.1.4.4.2; commitid jTnpym9Qu0o4R1Nx; 1.1.1.4.4.2 date 2014.08.19.23.47.26; author tls; state Exp; branches; next ; commitid jTnpym9Qu0o4R1Nx; 1.1.1.6.2.1 date 2017.03.20.06.52.36; author pgoyette; state Exp; branches; next ; commitid jjw7cAwgyKq7RfKz; 1.1.1.7.12.1 date 2018.07.28.04.33.16; author pgoyette; state Exp; branches; next ; commitid 1UP1xAIUxv1ZgRLA; 1.1.1.7.14.1 date 2019.06.10.21.45.20; author christos; state Exp; branches; next 1.1.1.7.14.2; commitid jtc8rnCzWiEEHGqB; 1.1.1.7.14.2 date 2020.04.13.07.46.31; author martin; state dead; branches; next ; commitid X01YhRUPVUDaec4C; desc @@ 1.1 log @Initial revision @ text @//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements Live Variables analysis for source-level CFGs. // //===----------------------------------------------------------------------===// #include "clang/Analysis/Analyses/LiveVariables.h" #include "clang/AST/Stmt.h" #include "clang/AST/StmtVisitor.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/Support/raw_ostream.h" #include #include using namespace clang; namespace { class DataflowWorklist { SmallVector worklist; llvm::BitVector enqueuedBlocks; PostOrderCFGView *POV; public: DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx) : enqueuedBlocks(cfg.getNumBlockIDs()), POV(Ctx.getAnalysis()) {} void enqueueBlock(const CFGBlock *block); void enqueueSuccessors(const CFGBlock *block); void enqueuePredecessors(const CFGBlock *block); const CFGBlock *dequeue(); void sortWorklist(); }; } void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { if (block && !enqueuedBlocks[block->getBlockID()]) { enqueuedBlocks[block->getBlockID()] = true; worklist.push_back(block); } } void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { const unsigned OldWorklistSize = worklist.size(); for (CFGBlock::const_succ_iterator I = block->succ_begin(), E = block->succ_end(); I != E; ++I) { enqueueBlock(*I); } if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) return; sortWorklist(); } void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { const unsigned OldWorklistSize = worklist.size(); for (CFGBlock::const_pred_iterator I = block->pred_begin(), E = block->pred_end(); I != E; ++I) { enqueueBlock(*I); } if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) return; sortWorklist(); } void DataflowWorklist::sortWorklist() { std::sort(worklist.begin(), worklist.end(), POV->getComparator()); } const CFGBlock *DataflowWorklist::dequeue() { if (worklist.empty()) return 0; const CFGBlock *b = worklist.pop_back_val(); enqueuedBlocks[b->getBlockID()] = false; return b; } namespace { class LiveVariablesImpl { public: AnalysisDeclContext &analysisContext; std::vector cfgBlockValues; llvm::ImmutableSet::Factory SSetFact; llvm::ImmutableSet::Factory DSetFact; llvm::DenseMap blocksEndToLiveness; llvm::DenseMap blocksBeginToLiveness; llvm::DenseMap stmtsToLiveness; llvm::DenseMap inAssignment; const bool killAtAssign; LiveVariables::LivenessValues merge(LiveVariables::LivenessValues valsA, LiveVariables::LivenessValues valsB); LiveVariables::LivenessValues runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, LiveVariables::Observer *obs = 0); void dumpBlockLiveness(const SourceManager& M); LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) : analysisContext(ac), SSetFact(false), // Do not canonicalize ImmutableSets by default. DSetFact(false), // This is a *major* performance win. killAtAssign(KillAtAssign) {} }; } static LiveVariablesImpl &getImpl(void *x) { return *((LiveVariablesImpl *) x); } //===----------------------------------------------------------------------===// // Operations and queries on LivenessValues. //===----------------------------------------------------------------------===// bool LiveVariables::LivenessValues::isLive(const Stmt *S) const { return liveStmts.contains(S); } bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { return liveDecls.contains(D); } namespace { template SET mergeSets(SET A, SET B) { if (A.isEmpty()) return B; for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { A = A.add(*it); } return A; } } void LiveVariables::Observer::anchor() { } LiveVariables::LivenessValues LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, LiveVariables::LivenessValues valsB) { llvm::ImmutableSetRef SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()), SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()); llvm::ImmutableSetRef DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); SSetRefA = mergeSets(SSetRefA, SSetRefB); DSetRefA = mergeSets(DSetRefA, DSetRefB); // asImmutableSet() canonicalizes the tree, allowing us to do an easy // comparison afterwards. return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), DSetRefA.asImmutableSet()); } bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { return liveStmts == V.liveStmts && liveDecls == V.liveDecls; } //===----------------------------------------------------------------------===// // Query methods. //===----------------------------------------------------------------------===// static bool isAlwaysAlive(const VarDecl *D) { return D->hasGlobalStorage(); } bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); } bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); } bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) { return getImpl(impl).stmtsToLiveness[Loc].isLive(S); } //===----------------------------------------------------------------------===// // Dataflow computation. //===----------------------------------------------------------------------===// namespace { class TransferFunctions : public StmtVisitor { LiveVariablesImpl &LV; LiveVariables::LivenessValues &val; LiveVariables::Observer *observer; const CFGBlock *currentBlock; void markLogicalExprLeaves(const Expr *E); public: TransferFunctions(LiveVariablesImpl &im, LiveVariables::LivenessValues &Val, LiveVariables::Observer *Observer, const CFGBlock *CurrentBlock) : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} void VisitBinaryOperator(BinaryOperator *BO); void VisitBlockExpr(BlockExpr *BE); void VisitDeclRefExpr(DeclRefExpr *DR); void VisitDeclStmt(DeclStmt *DS); void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); void VisitUnaryOperator(UnaryOperator *UO); void Visit(Stmt *S); }; } static const VariableArrayType *FindVA(QualType Ty) { const Type *ty = Ty.getTypePtr(); while (const ArrayType *VT = dyn_cast(ty)) { if (const VariableArrayType *VAT = dyn_cast(VT)) if (VAT->getSizeExpr()) return VAT; ty = VT->getElementType().getTypePtr(); } return 0; } static const Stmt *LookThroughStmt(const Stmt *S) { while (S) { if (const Expr *Ex = dyn_cast(S)) S = Ex->IgnoreParens(); if (const ExprWithCleanups *EWC = dyn_cast(S)) { S = EWC->getSubExpr(); continue; } if (const OpaqueValueExpr *OVE = dyn_cast(S)) { S = OVE->getSourceExpr(); continue; } break; } return S; } static void AddLiveStmt(llvm::ImmutableSet &Set, llvm::ImmutableSet::Factory &F, const Stmt *S) { Set = F.add(Set, LookThroughStmt(S)); } void TransferFunctions::Visit(Stmt *S) { if (observer) observer->observeStmt(S, currentBlock, val); StmtVisitor::Visit(S); if (isa(S)) { val.liveStmts = LV.SSetFact.remove(val.liveStmts, S); } // Mark all children expressions live. switch (S->getStmtClass()) { default: break; case Stmt::StmtExprClass: { // For statement expressions, look through the compound statement. S = cast(S)->getSubStmt(); break; } case Stmt::CXXMemberCallExprClass: { // Include the implicit "this" pointer as being live. CXXMemberCallExpr *CE = cast(S); if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj); } break; } case Stmt::ObjCMessageExprClass: { // In calls to super, include the implicit "self" pointer as being live. ObjCMessageExpr *CE = cast(S); if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance) val.liveDecls = LV.DSetFact.add(val.liveDecls, LV.analysisContext.getSelfDecl()); break; } case Stmt::DeclStmtClass: { const DeclStmt *DS = cast(S); if (const VarDecl *VD = dyn_cast(DS->getSingleDecl())) { for (const VariableArrayType* VA = FindVA(VD->getType()); VA != 0; VA = FindVA(VA->getElementType())) { AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr()); } } break; } case Stmt::PseudoObjectExprClass: { // A pseudo-object operation only directly consumes its result // expression. Expr *child = cast(S)->getResultExpr(); if (!child) return; if (OpaqueValueExpr *OV = dyn_cast(child)) child = OV->getSourceExpr(); child = child->IgnoreParens(); val.liveStmts = LV.SSetFact.add(val.liveStmts, child); return; } // FIXME: These cases eventually shouldn't be needed. case Stmt::ExprWithCleanupsClass: { S = cast(S)->getSubExpr(); break; } case Stmt::CXXBindTemporaryExprClass: { S = cast(S)->getSubExpr(); break; } case Stmt::UnaryExprOrTypeTraitExprClass: { // No need to unconditionally visit subexpressions. return; } } for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end(); it != ei; ++it) { if (Stmt *child = *it) AddLiveStmt(val.liveStmts, LV.SSetFact, child); } } void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { if (B->isAssignmentOp()) { if (!LV.killAtAssign) return; // Assigning to a variable? Expr *LHS = B->getLHS()->IgnoreParens(); if (DeclRefExpr *DR = dyn_cast(LHS)) if (const VarDecl *VD = dyn_cast(DR->getDecl())) { // Assignments to references don't kill the ref's address if (VD->getType()->isReferenceType()) return; if (!isAlwaysAlive(VD)) { // The variable is now dead. val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); } if (observer) observer->observerKill(DR); } } else if (B->isLogicalOp()) { // Leaf expressions in the logical operator tree are live until we reach the // outermost logical operator. Static analyzer relies on this behaviour. markLogicalExprLeaves(B->getLHS()->IgnoreParens()); markLogicalExprLeaves(B->getRHS()->IgnoreParens()); } } void TransferFunctions::markLogicalExprLeaves(const Expr *E) { const BinaryOperator *B = dyn_cast(E); if (!B || !B->isLogicalOp()) { val.liveStmts = LV.SSetFact.add(val.liveStmts, E); return; } markLogicalExprLeaves(B->getLHS()->IgnoreParens()); markLogicalExprLeaves(B->getRHS()->IgnoreParens()); } void TransferFunctions::VisitBlockExpr(BlockExpr *BE) { AnalysisDeclContext::referenced_decls_iterator I, E; llvm::tie(I, E) = LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl()); for ( ; I != E ; ++I) { const VarDecl *VD = *I; if (isAlwaysAlive(VD)) continue; val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); } } void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { if (const VarDecl *D = dyn_cast(DR->getDecl())) if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) val.liveDecls = LV.DSetFact.add(val.liveDecls, D); } void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); DI != DE; ++DI) if (VarDecl *VD = dyn_cast(*DI)) { if (!isAlwaysAlive(VD)) val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); } } void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { // Kill the iteration variable. DeclRefExpr *DR = 0; const VarDecl *VD = 0; Stmt *element = OS->getElement(); if (DeclStmt *DS = dyn_cast(element)) { VD = cast(DS->getSingleDecl()); } else if ((DR = dyn_cast(cast(element)->IgnoreParens()))) { VD = cast(DR->getDecl()); } if (VD) { val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); if (observer && DR) observer->observerKill(DR); } } void TransferFunctions:: VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) { // While sizeof(var) doesn't technically extend the liveness of 'var', it // does extent the liveness of metadata if 'var' is a VariableArrayType. // We handle that special case here. if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) return; const Expr *subEx = UE->getArgumentExpr(); if (subEx->getType()->isVariableArrayType()) { assert(subEx->isLValue()); val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens()); } } void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { // Treat ++/-- as a kill. // Note we don't actually have to do anything if we don't have an observer, // since a ++/-- acts as both a kill and a "use". if (!observer) return; switch (UO->getOpcode()) { default: return; case UO_PostInc: case UO_PostDec: case UO_PreInc: case UO_PreDec: break; } if (DeclRefExpr *DR = dyn_cast(UO->getSubExpr()->IgnoreParens())) if (isa(DR->getDecl())) { // Treat ++/-- as a kill. observer->observerKill(DR); } } LiveVariables::LivenessValues LiveVariablesImpl::runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, LiveVariables::Observer *obs) { TransferFunctions TF(*this, val, obs, block); // Visit the terminator (if any). if (const Stmt *term = block->getTerminator()) TF.Visit(const_cast(term)); // Apply the transfer function for all Stmts in the block. for (CFGBlock::const_reverse_iterator it = block->rbegin(), ei = block->rend(); it != ei; ++it) { const CFGElement &elem = *it; if (Optional Dtor = elem.getAs()) { val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl()); continue; } if (!elem.getAs()) continue; const Stmt *S = elem.castAs().getStmt(); TF.Visit(const_cast(S)); stmtsToLiveness[S] = val; } return val; } void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { const CFG *cfg = getImpl(impl).analysisContext.getCFG(); for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); } LiveVariables::LiveVariables(void *im) : impl(im) {} LiveVariables::~LiveVariables() { delete (LiveVariablesImpl*) impl; } LiveVariables * LiveVariables::computeLiveness(AnalysisDeclContext &AC, bool killAtAssign) { // No CFG? Bail out. CFG *cfg = AC.getCFG(); if (!cfg) return 0; // The analysis currently has scalability issues for very large CFGs. // Bail out if it looks too large. if (cfg->getNumBlockIDs() > 300000) return 0; LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); // Construct the dataflow worklist. Enqueue the exit block as the // start of the analysis. DataflowWorklist worklist(*cfg, AC); llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); // FIXME: we should enqueue using post order. for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { const CFGBlock *block = *it; worklist.enqueueBlock(block); // FIXME: Scan for DeclRefExprs using in the LHS of an assignment. // We need to do this because we lack context in the reverse analysis // to determine if a DeclRefExpr appears in such a context, and thus // doesn't constitute a "use". if (killAtAssign) for (CFGBlock::const_iterator bi = block->begin(), be = block->end(); bi != be; ++bi) { if (Optional cs = bi->getAs()) { if (const BinaryOperator *BO = dyn_cast(cs->getStmt())) { if (BO->getOpcode() == BO_Assign) { if (const DeclRefExpr *DR = dyn_cast(BO->getLHS()->IgnoreParens())) { LV->inAssignment[DR] = 1; } } } } } } worklist.sortWorklist(); while (const CFGBlock *block = worklist.dequeue()) { // Determine if the block's end value has changed. If not, we // have nothing left to do for this block. LivenessValues &prevVal = LV->blocksEndToLiveness[block]; // Merge the values of all successor blocks. LivenessValues val; for (CFGBlock::const_succ_iterator it = block->succ_begin(), ei = block->succ_end(); it != ei; ++it) { if (const CFGBlock *succ = *it) { val = LV->merge(val, LV->blocksBeginToLiveness[succ]); } } if (!everAnalyzedBlock[block->getBlockID()]) everAnalyzedBlock[block->getBlockID()] = true; else if (prevVal.equals(val)) continue; prevVal = val; // Update the dataflow value for the start of this block. LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); // Enqueue the value to the predecessors. worklist.enqueuePredecessors(block); } return new LiveVariables(LV); } static bool compare_entries(const CFGBlock *A, const CFGBlock *B) { return A->getBlockID() < B->getBlockID(); } static bool compare_vd_entries(const Decl *A, const Decl *B) { SourceLocation ALoc = A->getLocStart(); SourceLocation BLoc = B->getLocStart(); return ALoc.getRawEncoding() < BLoc.getRawEncoding(); } void LiveVariables::dumpBlockLiveness(const SourceManager &M) { getImpl(impl).dumpBlockLiveness(M); } void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { std::vector vec; for (llvm::DenseMap::iterator it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); it != ei; ++it) { vec.push_back(it->first); } std::sort(vec.begin(), vec.end(), compare_entries); std::vector declVec; for (std::vector::iterator it = vec.begin(), ei = vec.end(); it != ei; ++it) { llvm::errs() << "\n[ B" << (*it)->getBlockID() << " (live variables at block exit) ]\n"; LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; declVec.clear(); for (llvm::ImmutableSet::iterator si = vals.liveDecls.begin(), se = vals.liveDecls.end(); si != se; ++si) { declVec.push_back(*si); } std::sort(declVec.begin(), declVec.end(), compare_vd_entries); for (std::vector::iterator di = declVec.begin(), de = declVec.end(); di != de; ++di) { llvm::errs() << " " << (*di)->getDeclName().getAsString() << " <"; (*di)->getLocation().dump(M); llvm::errs() << ">\n"; } } llvm::errs() << "\n"; } const void *LiveVariables::getTag() { static int x; return &x; } const void *RelaxedLiveVariables::getTag() { static int x; return &x; } @ 1.1.1.1 log @Import Clang 3.4rc1 r195771. @ text @@ 1.1.1.2 log @Import clang 3.5svn r198450. @ text @d214 2 d372 13 d386 3 @ 1.1.1.2.2.1 log @Rebase. @ text @d40 1 d56 13 d89 1 a89 1 return nullptr; d111 4 a114 4 LiveVariables::LivenessValues runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, LiveVariables::Observer *obs = nullptr); d241 2 a242 2 return nullptr; d308 1 a308 1 VA != nullptr; VA = FindVA(VA->getElementType())) { d375 1 a375 1 std::tie(I, E) = d392 3 a394 2 for (const auto *DI : DS->decls()) if (const auto *VD = dyn_cast(DI)) { d402 2 a403 2 DeclRefExpr *DR = nullptr; const VarDecl *VD = nullptr; d511 1 a511 1 return nullptr; d516 1 a516 1 return nullptr; d584 10 d605 1 a605 3 std::sort(vec.begin(), vec.end(), [](const CFGBlock *A, const CFGBlock *B) { return A->getBlockID() < B->getBlockID(); }); d622 3 a624 5 std::sort(declVec.begin(), declVec.end(), [](const Decl *A, const Decl *B) { return A->getLocStart() < B->getLocStart(); }); @ 1.1.1.3 log @Import Clang 3.5svn r209886. @ text @d40 1 d56 13 d89 1 a89 1 return nullptr; d111 4 a114 4 LiveVariables::LivenessValues runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, LiveVariables::Observer *obs = nullptr); d241 2 a242 2 return nullptr; d308 1 a308 1 VA != nullptr; VA = FindVA(VA->getElementType())) { d375 1 a375 1 std::tie(I, E) = d392 3 a394 2 for (const auto *DI : DS->decls()) if (const auto *VD = dyn_cast(DI)) { d402 2 a403 2 DeclRefExpr *DR = nullptr; const VarDecl *VD = nullptr; d511 1 a511 1 return nullptr; d516 1 a516 1 return nullptr; d584 10 d605 1 a605 3 std::sort(vec.begin(), vec.end(), [](const CFGBlock *A, const CFGBlock *B) { return A->getBlockID() < B->getBlockID(); }); d622 3 a624 5 std::sort(declVec.begin(), declVec.end(), [](const Decl *A, const Decl *B) { return A->getLocStart() < B->getLocStart(); }); @ 1.1.1.4 log @Import clang 3.6svn r215315. @ text @d17 1 a17 1 #include "clang/Analysis/Analyses/DataflowWorklist.h" d21 1 d29 53 @ 1.1.1.4.2.1 log @Update LLVM to 3.6.1, requested by joerg in ticket 824. @ text @d17 1 a17 1 #include "clang/Analysis/Analyses/PostOrderCFGView.h" a20 1 #include "llvm/ADT/PostOrderIterator.h" a27 53 class DataflowWorklist { SmallVector worklist; llvm::BitVector enqueuedBlocks; PostOrderCFGView *POV; public: DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx) : enqueuedBlocks(cfg.getNumBlockIDs()), POV(Ctx.getAnalysis()) {} void enqueueBlock(const CFGBlock *block); void enqueuePredecessors(const CFGBlock *block); const CFGBlock *dequeue(); void sortWorklist(); }; } void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { if (block && !enqueuedBlocks[block->getBlockID()]) { enqueuedBlocks[block->getBlockID()] = true; worklist.push_back(block); } } void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { const unsigned OldWorklistSize = worklist.size(); for (CFGBlock::const_pred_iterator I = block->pred_begin(), E = block->pred_end(); I != E; ++I) { enqueueBlock(*I); } if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) return; sortWorklist(); } void DataflowWorklist::sortWorklist() { std::sort(worklist.begin(), worklist.end(), POV->getComparator()); } const CFGBlock *DataflowWorklist::dequeue() { if (worklist.empty()) return nullptr; const CFGBlock *b = worklist.pop_back_val(); enqueuedBlocks[b->getBlockID()] = false; return b; } namespace { d31 1 @ 1.1.1.5 log @Import Clang 3.6RC1 r227398. @ text @d17 1 a17 1 #include "clang/Analysis/Analyses/PostOrderCFGView.h" a20 1 #include "llvm/ADT/PostOrderIterator.h" a27 53 class DataflowWorklist { SmallVector worklist; llvm::BitVector enqueuedBlocks; PostOrderCFGView *POV; public: DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx) : enqueuedBlocks(cfg.getNumBlockIDs()), POV(Ctx.getAnalysis()) {} void enqueueBlock(const CFGBlock *block); void enqueuePredecessors(const CFGBlock *block); const CFGBlock *dequeue(); void sortWorklist(); }; } void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { if (block && !enqueuedBlocks[block->getBlockID()]) { enqueuedBlocks[block->getBlockID()] = true; worklist.push_back(block); } } void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { const unsigned OldWorklistSize = worklist.size(); for (CFGBlock::const_pred_iterator I = block->pred_begin(), E = block->pred_end(); I != E; ++I) { enqueueBlock(*I); } if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) return; sortWorklist(); } void DataflowWorklist::sortWorklist() { std::sort(worklist.begin(), worklist.end(), POV->getComparator()); } const CFGBlock *DataflowWorklist::dequeue() { if (worklist.empty()) return nullptr; const CFGBlock *b = worklist.pop_back_val(); enqueuedBlocks[b->getBlockID()] = false; return b; } namespace { d31 1 @ 1.1.1.6 log @Import Clang 3.8.0rc3 r261930. @ text @d325 5 a329 4 for (Stmt *Child : S->children()) { if (Child) AddLiveStmt(val.liveStmts, LV.SSetFact, Child); d359 5 a363 2 for (const VarDecl *VD : LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) { @ 1.1.1.6.2.1 log @Sync with HEAD @ text @a21 1 #include "llvm/ADT/PriorityQueue.h" d31 1 a33 3 llvm::PriorityQueue, PostOrderCFGView::BlockOrderCompare> worklist; d37 1 a37 2 POV(Ctx.getAnalysis()), worklist(POV->getComparator()) {} d43 2 d52 1 a52 1 worklist.push(block); d57 1 d62 9 d76 1 a76 2 const CFGBlock *b = worklist.top(); worklist.pop(); d531 2 @ 1.1.1.7 log @Import Clang pre-4.0.0 r291444. @ text @a21 1 #include "llvm/ADT/PriorityQueue.h" d31 1 a33 3 llvm::PriorityQueue, PostOrderCFGView::BlockOrderCompare> worklist; d37 1 a37 2 POV(Ctx.getAnalysis()), worklist(POV->getComparator()) {} d43 2 d52 1 a52 1 worklist.push(block); d57 1 d62 9 d76 1 a76 2 const CFGBlock *b = worklist.top(); worklist.pop(); d531 2 @ 1.1.1.7.14.1 log @Sync with HEAD @ text @d18 1 a18 1 #include "clang/Analysis/AnalysisDeclContext.h" a79 1 llvm::ImmutableSet::Factory BSetFact; a99 1 BSetFact(false), a116 6 if (const auto *DD = dyn_cast(D)) { bool alive = false; for (const BindingDecl *BD : DD->bindings()) alive |= liveBindings.contains(BD); return alive; } a147 3 llvm::ImmutableSetRef BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()), BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()); a150 1 BSetRefA = mergeSets(BSetRefA, BSetRefB); d155 1 a155 2 DSetRefA.asImmutableSet(), BSetRefA.asImmutableSet()); a324 5 static bool writeShouldKill(const VarDecl *VD) { return VD && !VD->getType()->isReferenceType() && !isAlwaysAlive(VD); } d332 6 d339 2 a340 11 if (DeclRefExpr *DR = dyn_cast(LHS)) { const Decl* D = DR->getDecl(); bool Killed = false; if (const BindingDecl* BD = dyn_cast(D)) { Killed = !BD->getType()->isReferenceType(); if (Killed) val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); } else if (const auto *VD = dyn_cast(D)) { Killed = writeShouldKill(VD); if (Killed) d342 1 d344 2 a346 4 if (Killed && observer) observer->observerKill(DR); } d360 3 a362 9 const Decl* D = DR->getDecl(); bool InAssignment = LV.inAssignment[DR]; if (const auto *BD = dyn_cast(D)) { if (!InAssignment) val.liveBindings = LV.BSetFact.add(val.liveBindings, BD); } else if (const auto *VD = dyn_cast(D)) { if (!InAssignment && !isAlwaysAlive(VD)) val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); } d366 2 a367 5 for (const auto *DI : DS->decls()) { if (const auto *DD = dyn_cast(DI)) { for (const auto *BD : DD->bindings()) val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); } else if (const auto *VD = dyn_cast(DI)) { a370 1 } d425 3 a427 4 if (auto *DR = dyn_cast(UO->getSubExpr()->IgnoreParens())) { const Decl *D = DR->getDecl(); if (isa(D) || isa(D)) { a430 1 } d511 2 a512 2 const Stmt* stmt = cs->getStmt(); if (const auto *BO = dyn_cast(stmt)) { d514 1 a514 1 if (const auto *DR = d566 1 a566 1 llvm::sort(vec.begin(), vec.end(), [](const CFGBlock *A, const CFGBlock *B) { d586 1 a586 2 llvm::sort(declVec.begin(), declVec.end(), [](const Decl *A, const Decl *B) { @ 1.1.1.7.14.2 log @Mostly merge changes from HEAD upto 20200411 @ text @@ 1.1.1.7.12.1 log @Sync with HEAD @ text @d18 1 a18 1 #include "clang/Analysis/AnalysisDeclContext.h" a79 1 llvm::ImmutableSet::Factory BSetFact; a99 1 BSetFact(false), a116 6 if (const auto *DD = dyn_cast(D)) { bool alive = false; for (const BindingDecl *BD : DD->bindings()) alive |= liveBindings.contains(BD); return alive; } a147 3 llvm::ImmutableSetRef BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()), BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()); a150 1 BSetRefA = mergeSets(BSetRefA, BSetRefB); d155 1 a155 2 DSetRefA.asImmutableSet(), BSetRefA.asImmutableSet()); a324 5 static bool writeShouldKill(const VarDecl *VD) { return VD && !VD->getType()->isReferenceType() && !isAlwaysAlive(VD); } d332 6 d339 2 a340 11 if (DeclRefExpr *DR = dyn_cast(LHS)) { const Decl* D = DR->getDecl(); bool Killed = false; if (const BindingDecl* BD = dyn_cast(D)) { Killed = !BD->getType()->isReferenceType(); if (Killed) val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); } else if (const auto *VD = dyn_cast(D)) { Killed = writeShouldKill(VD); if (Killed) d342 1 d344 2 a346 4 if (Killed && observer) observer->observerKill(DR); } d360 3 a362 9 const Decl* D = DR->getDecl(); bool InAssignment = LV.inAssignment[DR]; if (const auto *BD = dyn_cast(D)) { if (!InAssignment) val.liveBindings = LV.BSetFact.add(val.liveBindings, BD); } else if (const auto *VD = dyn_cast(D)) { if (!InAssignment && !isAlwaysAlive(VD)) val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); } d366 2 a367 5 for (const auto *DI : DS->decls()) { if (const auto *DD = dyn_cast(DI)) { for (const auto *BD : DD->bindings()) val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); } else if (const auto *VD = dyn_cast(DI)) { a370 1 } d425 3 a427 4 if (auto *DR = dyn_cast(UO->getSubExpr()->IgnoreParens())) { const Decl *D = DR->getDecl(); if (isa(D) || isa(D)) { a430 1 } d511 2 a512 2 const Stmt* stmt = cs->getStmt(); if (const auto *BO = dyn_cast(stmt)) { d514 1 a514 1 if (const auto *DR = d566 1 a566 1 llvm::sort(vec.begin(), vec.end(), [](const CFGBlock *A, const CFGBlock *B) { d586 1 a586 2 llvm::sort(declVec.begin(), declVec.end(), [](const Decl *A, const Decl *B) { @ 1.1.1.8 log @Import clang r337282 from trunk @ text @d18 1 a18 1 #include "clang/Analysis/AnalysisDeclContext.h" a79 1 llvm::ImmutableSet::Factory BSetFact; a99 1 BSetFact(false), a116 6 if (const auto *DD = dyn_cast(D)) { bool alive = false; for (const BindingDecl *BD : DD->bindings()) alive |= liveBindings.contains(BD); return alive; } a147 3 llvm::ImmutableSetRef BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()), BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()); a150 1 BSetRefA = mergeSets(BSetRefA, BSetRefB); d155 1 a155 2 DSetRefA.asImmutableSet(), BSetRefA.asImmutableSet()); a324 5 static bool writeShouldKill(const VarDecl *VD) { return VD && !VD->getType()->isReferenceType() && !isAlwaysAlive(VD); } d332 6 d339 2 a340 11 if (DeclRefExpr *DR = dyn_cast(LHS)) { const Decl* D = DR->getDecl(); bool Killed = false; if (const BindingDecl* BD = dyn_cast(D)) { Killed = !BD->getType()->isReferenceType(); if (Killed) val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); } else if (const auto *VD = dyn_cast(D)) { Killed = writeShouldKill(VD); if (Killed) d342 1 d344 2 a346 4 if (Killed && observer) observer->observerKill(DR); } d360 3 a362 9 const Decl* D = DR->getDecl(); bool InAssignment = LV.inAssignment[DR]; if (const auto *BD = dyn_cast(D)) { if (!InAssignment) val.liveBindings = LV.BSetFact.add(val.liveBindings, BD); } else if (const auto *VD = dyn_cast(D)) { if (!InAssignment && !isAlwaysAlive(VD)) val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); } d366 2 a367 5 for (const auto *DI : DS->decls()) { if (const auto *DD = dyn_cast(DI)) { for (const auto *BD : DD->bindings()) val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); } else if (const auto *VD = dyn_cast(DI)) { a370 1 } d425 3 a427 4 if (auto *DR = dyn_cast(UO->getSubExpr()->IgnoreParens())) { const Decl *D = DR->getDecl(); if (isa(D) || isa(D)) { a430 1 } d511 2 a512 2 const Stmt* stmt = cs->getStmt(); if (const auto *BO = dyn_cast(stmt)) { d514 1 a514 1 if (const auto *DR = d566 1 a566 1 llvm::sort(vec.begin(), vec.end(), [](const CFGBlock *A, const CFGBlock *B) { d586 1 a586 2 llvm::sort(declVec.begin(), declVec.end(), [](const Decl *A, const Decl *B) { @ 1.1.1.9 log @Mark old LLVM instance as dead. @ text @@ 1.1.1.4.4.1 log @file LiveVariables.cpp was added on branch tls-maxphys on 2014-08-19 23:47:26 +0000 @ text @d1 562 @ 1.1.1.4.4.2 log @Rebase to HEAD as of a few days ago. @ text @a0 562 //=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements Live Variables analysis for source-level CFGs. // //===----------------------------------------------------------------------===// #include "clang/Analysis/Analyses/LiveVariables.h" #include "clang/AST/Stmt.h" #include "clang/AST/StmtVisitor.h" #include "clang/Analysis/Analyses/DataflowWorklist.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" #include "llvm/ADT/DenseMap.h" #include "llvm/Support/raw_ostream.h" #include #include using namespace clang; namespace { class LiveVariablesImpl { public: AnalysisDeclContext &analysisContext; std::vector cfgBlockValues; llvm::ImmutableSet::Factory SSetFact; llvm::ImmutableSet::Factory DSetFact; llvm::DenseMap blocksEndToLiveness; llvm::DenseMap blocksBeginToLiveness; llvm::DenseMap stmtsToLiveness; llvm::DenseMap inAssignment; const bool killAtAssign; LiveVariables::LivenessValues merge(LiveVariables::LivenessValues valsA, LiveVariables::LivenessValues valsB); LiveVariables::LivenessValues runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, LiveVariables::Observer *obs = nullptr); void dumpBlockLiveness(const SourceManager& M); LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) : analysisContext(ac), SSetFact(false), // Do not canonicalize ImmutableSets by default. DSetFact(false), // This is a *major* performance win. killAtAssign(KillAtAssign) {} }; } static LiveVariablesImpl &getImpl(void *x) { return *((LiveVariablesImpl *) x); } //===----------------------------------------------------------------------===// // Operations and queries on LivenessValues. //===----------------------------------------------------------------------===// bool LiveVariables::LivenessValues::isLive(const Stmt *S) const { return liveStmts.contains(S); } bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { return liveDecls.contains(D); } namespace { template SET mergeSets(SET A, SET B) { if (A.isEmpty()) return B; for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { A = A.add(*it); } return A; } } void LiveVariables::Observer::anchor() { } LiveVariables::LivenessValues LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, LiveVariables::LivenessValues valsB) { llvm::ImmutableSetRef SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()), SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()); llvm::ImmutableSetRef DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); SSetRefA = mergeSets(SSetRefA, SSetRefB); DSetRefA = mergeSets(DSetRefA, DSetRefB); // asImmutableSet() canonicalizes the tree, allowing us to do an easy // comparison afterwards. return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), DSetRefA.asImmutableSet()); } bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { return liveStmts == V.liveStmts && liveDecls == V.liveDecls; } //===----------------------------------------------------------------------===// // Query methods. //===----------------------------------------------------------------------===// static bool isAlwaysAlive(const VarDecl *D) { return D->hasGlobalStorage(); } bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); } bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); } bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) { return getImpl(impl).stmtsToLiveness[Loc].isLive(S); } //===----------------------------------------------------------------------===// // Dataflow computation. //===----------------------------------------------------------------------===// namespace { class TransferFunctions : public StmtVisitor { LiveVariablesImpl &LV; LiveVariables::LivenessValues &val; LiveVariables::Observer *observer; const CFGBlock *currentBlock; public: TransferFunctions(LiveVariablesImpl &im, LiveVariables::LivenessValues &Val, LiveVariables::Observer *Observer, const CFGBlock *CurrentBlock) : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} void VisitBinaryOperator(BinaryOperator *BO); void VisitBlockExpr(BlockExpr *BE); void VisitDeclRefExpr(DeclRefExpr *DR); void VisitDeclStmt(DeclStmt *DS); void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); void VisitUnaryOperator(UnaryOperator *UO); void Visit(Stmt *S); }; } static const VariableArrayType *FindVA(QualType Ty) { const Type *ty = Ty.getTypePtr(); while (const ArrayType *VT = dyn_cast(ty)) { if (const VariableArrayType *VAT = dyn_cast(VT)) if (VAT->getSizeExpr()) return VAT; ty = VT->getElementType().getTypePtr(); } return nullptr; } static const Stmt *LookThroughStmt(const Stmt *S) { while (S) { if (const Expr *Ex = dyn_cast(S)) S = Ex->IgnoreParens(); if (const ExprWithCleanups *EWC = dyn_cast(S)) { S = EWC->getSubExpr(); continue; } if (const OpaqueValueExpr *OVE = dyn_cast(S)) { S = OVE->getSourceExpr(); continue; } break; } return S; } static void AddLiveStmt(llvm::ImmutableSet &Set, llvm::ImmutableSet::Factory &F, const Stmt *S) { Set = F.add(Set, LookThroughStmt(S)); } void TransferFunctions::Visit(Stmt *S) { if (observer) observer->observeStmt(S, currentBlock, val); StmtVisitor::Visit(S); if (isa(S)) { val.liveStmts = LV.SSetFact.remove(val.liveStmts, S); } // Mark all children expressions live. switch (S->getStmtClass()) { default: break; case Stmt::StmtExprClass: { // For statement expressions, look through the compound statement. S = cast(S)->getSubStmt(); break; } case Stmt::CXXMemberCallExprClass: { // Include the implicit "this" pointer as being live. CXXMemberCallExpr *CE = cast(S); if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj); } break; } case Stmt::ObjCMessageExprClass: { // In calls to super, include the implicit "self" pointer as being live. ObjCMessageExpr *CE = cast(S); if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance) val.liveDecls = LV.DSetFact.add(val.liveDecls, LV.analysisContext.getSelfDecl()); break; } case Stmt::DeclStmtClass: { const DeclStmt *DS = cast(S); if (const VarDecl *VD = dyn_cast(DS->getSingleDecl())) { for (const VariableArrayType* VA = FindVA(VD->getType()); VA != nullptr; VA = FindVA(VA->getElementType())) { AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr()); } } break; } case Stmt::PseudoObjectExprClass: { // A pseudo-object operation only directly consumes its result // expression. Expr *child = cast(S)->getResultExpr(); if (!child) return; if (OpaqueValueExpr *OV = dyn_cast(child)) child = OV->getSourceExpr(); child = child->IgnoreParens(); val.liveStmts = LV.SSetFact.add(val.liveStmts, child); return; } // FIXME: These cases eventually shouldn't be needed. case Stmt::ExprWithCleanupsClass: { S = cast(S)->getSubExpr(); break; } case Stmt::CXXBindTemporaryExprClass: { S = cast(S)->getSubExpr(); break; } case Stmt::UnaryExprOrTypeTraitExprClass: { // No need to unconditionally visit subexpressions. return; } } for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end(); it != ei; ++it) { if (Stmt *child = *it) AddLiveStmt(val.liveStmts, LV.SSetFact, child); } } void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { if (B->isAssignmentOp()) { if (!LV.killAtAssign) return; // Assigning to a variable? Expr *LHS = B->getLHS()->IgnoreParens(); if (DeclRefExpr *DR = dyn_cast(LHS)) if (const VarDecl *VD = dyn_cast(DR->getDecl())) { // Assignments to references don't kill the ref's address if (VD->getType()->isReferenceType()) return; if (!isAlwaysAlive(VD)) { // The variable is now dead. val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); } if (observer) observer->observerKill(DR); } } } void TransferFunctions::VisitBlockExpr(BlockExpr *BE) { AnalysisDeclContext::referenced_decls_iterator I, E; std::tie(I, E) = LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl()); for ( ; I != E ; ++I) { const VarDecl *VD = *I; if (isAlwaysAlive(VD)) continue; val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); } } void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { if (const VarDecl *D = dyn_cast(DR->getDecl())) if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) val.liveDecls = LV.DSetFact.add(val.liveDecls, D); } void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { for (const auto *DI : DS->decls()) if (const auto *VD = dyn_cast(DI)) { if (!isAlwaysAlive(VD)) val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); } } void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { // Kill the iteration variable. DeclRefExpr *DR = nullptr; const VarDecl *VD = nullptr; Stmt *element = OS->getElement(); if (DeclStmt *DS = dyn_cast(element)) { VD = cast(DS->getSingleDecl()); } else if ((DR = dyn_cast(cast(element)->IgnoreParens()))) { VD = cast(DR->getDecl()); } if (VD) { val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); if (observer && DR) observer->observerKill(DR); } } void TransferFunctions:: VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) { // While sizeof(var) doesn't technically extend the liveness of 'var', it // does extent the liveness of metadata if 'var' is a VariableArrayType. // We handle that special case here. if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) return; const Expr *subEx = UE->getArgumentExpr(); if (subEx->getType()->isVariableArrayType()) { assert(subEx->isLValue()); val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens()); } } void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { // Treat ++/-- as a kill. // Note we don't actually have to do anything if we don't have an observer, // since a ++/-- acts as both a kill and a "use". if (!observer) return; switch (UO->getOpcode()) { default: return; case UO_PostInc: case UO_PostDec: case UO_PreInc: case UO_PreDec: break; } if (DeclRefExpr *DR = dyn_cast(UO->getSubExpr()->IgnoreParens())) if (isa(DR->getDecl())) { // Treat ++/-- as a kill. observer->observerKill(DR); } } LiveVariables::LivenessValues LiveVariablesImpl::runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, LiveVariables::Observer *obs) { TransferFunctions TF(*this, val, obs, block); // Visit the terminator (if any). if (const Stmt *term = block->getTerminator()) TF.Visit(const_cast(term)); // Apply the transfer function for all Stmts in the block. for (CFGBlock::const_reverse_iterator it = block->rbegin(), ei = block->rend(); it != ei; ++it) { const CFGElement &elem = *it; if (Optional Dtor = elem.getAs()) { val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl()); continue; } if (!elem.getAs()) continue; const Stmt *S = elem.castAs().getStmt(); TF.Visit(const_cast(S)); stmtsToLiveness[S] = val; } return val; } void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { const CFG *cfg = getImpl(impl).analysisContext.getCFG(); for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); } LiveVariables::LiveVariables(void *im) : impl(im) {} LiveVariables::~LiveVariables() { delete (LiveVariablesImpl*) impl; } LiveVariables * LiveVariables::computeLiveness(AnalysisDeclContext &AC, bool killAtAssign) { // No CFG? Bail out. CFG *cfg = AC.getCFG(); if (!cfg) return nullptr; // The analysis currently has scalability issues for very large CFGs. // Bail out if it looks too large. if (cfg->getNumBlockIDs() > 300000) return nullptr; LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); // Construct the dataflow worklist. Enqueue the exit block as the // start of the analysis. DataflowWorklist worklist(*cfg, AC); llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); // FIXME: we should enqueue using post order. for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { const CFGBlock *block = *it; worklist.enqueueBlock(block); // FIXME: Scan for DeclRefExprs using in the LHS of an assignment. // We need to do this because we lack context in the reverse analysis // to determine if a DeclRefExpr appears in such a context, and thus // doesn't constitute a "use". if (killAtAssign) for (CFGBlock::const_iterator bi = block->begin(), be = block->end(); bi != be; ++bi) { if (Optional cs = bi->getAs()) { if (const BinaryOperator *BO = dyn_cast(cs->getStmt())) { if (BO->getOpcode() == BO_Assign) { if (const DeclRefExpr *DR = dyn_cast(BO->getLHS()->IgnoreParens())) { LV->inAssignment[DR] = 1; } } } } } } worklist.sortWorklist(); while (const CFGBlock *block = worklist.dequeue()) { // Determine if the block's end value has changed. If not, we // have nothing left to do for this block. LivenessValues &prevVal = LV->blocksEndToLiveness[block]; // Merge the values of all successor blocks. LivenessValues val; for (CFGBlock::const_succ_iterator it = block->succ_begin(), ei = block->succ_end(); it != ei; ++it) { if (const CFGBlock *succ = *it) { val = LV->merge(val, LV->blocksBeginToLiveness[succ]); } } if (!everAnalyzedBlock[block->getBlockID()]) everAnalyzedBlock[block->getBlockID()] = true; else if (prevVal.equals(val)) continue; prevVal = val; // Update the dataflow value for the start of this block. LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); // Enqueue the value to the predecessors. worklist.enqueuePredecessors(block); } return new LiveVariables(LV); } void LiveVariables::dumpBlockLiveness(const SourceManager &M) { getImpl(impl).dumpBlockLiveness(M); } void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { std::vector vec; for (llvm::DenseMap::iterator it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); it != ei; ++it) { vec.push_back(it->first); } std::sort(vec.begin(), vec.end(), [](const CFGBlock *A, const CFGBlock *B) { return A->getBlockID() < B->getBlockID(); }); std::vector declVec; for (std::vector::iterator it = vec.begin(), ei = vec.end(); it != ei; ++it) { llvm::errs() << "\n[ B" << (*it)->getBlockID() << " (live variables at block exit) ]\n"; LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; declVec.clear(); for (llvm::ImmutableSet::iterator si = vals.liveDecls.begin(), se = vals.liveDecls.end(); si != se; ++si) { declVec.push_back(*si); } std::sort(declVec.begin(), declVec.end(), [](const Decl *A, const Decl *B) { return A->getLocStart() < B->getLocStart(); }); for (std::vector::iterator di = declVec.begin(), de = declVec.end(); di != de; ++di) { llvm::errs() << " " << (*di)->getDeclName().getAsString() << " <"; (*di)->getLocation().dump(M); llvm::errs() << ">\n"; } } llvm::errs() << "\n"; } const void *LiveVariables::getTag() { static int x; return &x; } const void *RelaxedLiveVariables::getTag() { static int x; return &x; } @ 1.1.1.2.4.1 log @file LiveVariables.cpp was added on branch yamt-pagecache on 2014-05-22 16:18:26 +0000 @ text @d1 637 @ 1.1.1.2.4.2 log @sync with head. for a reference, the tree before this commit was tagged as yamt-pagecache-tag8. this commit was splitted into small chunks to avoid a limitation of cvs. ("Protocol error: too many arguments") @ text @a0 637 //=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file implements Live Variables analysis for source-level CFGs. // //===----------------------------------------------------------------------===// #include "clang/Analysis/Analyses/LiveVariables.h" #include "clang/AST/Stmt.h" #include "clang/AST/StmtVisitor.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/Support/raw_ostream.h" #include #include using namespace clang; namespace { class DataflowWorklist { SmallVector worklist; llvm::BitVector enqueuedBlocks; PostOrderCFGView *POV; public: DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx) : enqueuedBlocks(cfg.getNumBlockIDs()), POV(Ctx.getAnalysis()) {} void enqueueBlock(const CFGBlock *block); void enqueueSuccessors(const CFGBlock *block); void enqueuePredecessors(const CFGBlock *block); const CFGBlock *dequeue(); void sortWorklist(); }; } void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { if (block && !enqueuedBlocks[block->getBlockID()]) { enqueuedBlocks[block->getBlockID()] = true; worklist.push_back(block); } } void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { const unsigned OldWorklistSize = worklist.size(); for (CFGBlock::const_succ_iterator I = block->succ_begin(), E = block->succ_end(); I != E; ++I) { enqueueBlock(*I); } if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) return; sortWorklist(); } void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { const unsigned OldWorklistSize = worklist.size(); for (CFGBlock::const_pred_iterator I = block->pred_begin(), E = block->pred_end(); I != E; ++I) { enqueueBlock(*I); } if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) return; sortWorklist(); } void DataflowWorklist::sortWorklist() { std::sort(worklist.begin(), worklist.end(), POV->getComparator()); } const CFGBlock *DataflowWorklist::dequeue() { if (worklist.empty()) return 0; const CFGBlock *b = worklist.pop_back_val(); enqueuedBlocks[b->getBlockID()] = false; return b; } namespace { class LiveVariablesImpl { public: AnalysisDeclContext &analysisContext; std::vector cfgBlockValues; llvm::ImmutableSet::Factory SSetFact; llvm::ImmutableSet::Factory DSetFact; llvm::DenseMap blocksEndToLiveness; llvm::DenseMap blocksBeginToLiveness; llvm::DenseMap stmtsToLiveness; llvm::DenseMap inAssignment; const bool killAtAssign; LiveVariables::LivenessValues merge(LiveVariables::LivenessValues valsA, LiveVariables::LivenessValues valsB); LiveVariables::LivenessValues runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, LiveVariables::Observer *obs = 0); void dumpBlockLiveness(const SourceManager& M); LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) : analysisContext(ac), SSetFact(false), // Do not canonicalize ImmutableSets by default. DSetFact(false), // This is a *major* performance win. killAtAssign(KillAtAssign) {} }; } static LiveVariablesImpl &getImpl(void *x) { return *((LiveVariablesImpl *) x); } //===----------------------------------------------------------------------===// // Operations and queries on LivenessValues. //===----------------------------------------------------------------------===// bool LiveVariables::LivenessValues::isLive(const Stmt *S) const { return liveStmts.contains(S); } bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { return liveDecls.contains(D); } namespace { template SET mergeSets(SET A, SET B) { if (A.isEmpty()) return B; for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { A = A.add(*it); } return A; } } void LiveVariables::Observer::anchor() { } LiveVariables::LivenessValues LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, LiveVariables::LivenessValues valsB) { llvm::ImmutableSetRef SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()), SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()); llvm::ImmutableSetRef DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); SSetRefA = mergeSets(SSetRefA, SSetRefB); DSetRefA = mergeSets(DSetRefA, DSetRefB); // asImmutableSet() canonicalizes the tree, allowing us to do an easy // comparison afterwards. return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), DSetRefA.asImmutableSet()); } bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { return liveStmts == V.liveStmts && liveDecls == V.liveDecls; } //===----------------------------------------------------------------------===// // Query methods. //===----------------------------------------------------------------------===// static bool isAlwaysAlive(const VarDecl *D) { return D->hasGlobalStorage(); } bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); } bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); } bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) { return getImpl(impl).stmtsToLiveness[Loc].isLive(S); } //===----------------------------------------------------------------------===// // Dataflow computation. //===----------------------------------------------------------------------===// namespace { class TransferFunctions : public StmtVisitor { LiveVariablesImpl &LV; LiveVariables::LivenessValues &val; LiveVariables::Observer *observer; const CFGBlock *currentBlock; public: TransferFunctions(LiveVariablesImpl &im, LiveVariables::LivenessValues &Val, LiveVariables::Observer *Observer, const CFGBlock *CurrentBlock) : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} void VisitBinaryOperator(BinaryOperator *BO); void VisitBlockExpr(BlockExpr *BE); void VisitDeclRefExpr(DeclRefExpr *DR); void VisitDeclStmt(DeclStmt *DS); void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); void VisitUnaryOperator(UnaryOperator *UO); void Visit(Stmt *S); }; } static const VariableArrayType *FindVA(QualType Ty) { const Type *ty = Ty.getTypePtr(); while (const ArrayType *VT = dyn_cast(ty)) { if (const VariableArrayType *VAT = dyn_cast(VT)) if (VAT->getSizeExpr()) return VAT; ty = VT->getElementType().getTypePtr(); } return 0; } static const Stmt *LookThroughStmt(const Stmt *S) { while (S) { if (const Expr *Ex = dyn_cast(S)) S = Ex->IgnoreParens(); if (const ExprWithCleanups *EWC = dyn_cast(S)) { S = EWC->getSubExpr(); continue; } if (const OpaqueValueExpr *OVE = dyn_cast(S)) { S = OVE->getSourceExpr(); continue; } break; } return S; } static void AddLiveStmt(llvm::ImmutableSet &Set, llvm::ImmutableSet::Factory &F, const Stmt *S) { Set = F.add(Set, LookThroughStmt(S)); } void TransferFunctions::Visit(Stmt *S) { if (observer) observer->observeStmt(S, currentBlock, val); StmtVisitor::Visit(S); if (isa(S)) { val.liveStmts = LV.SSetFact.remove(val.liveStmts, S); } // Mark all children expressions live. switch (S->getStmtClass()) { default: break; case Stmt::StmtExprClass: { // For statement expressions, look through the compound statement. S = cast(S)->getSubStmt(); break; } case Stmt::CXXMemberCallExprClass: { // Include the implicit "this" pointer as being live. CXXMemberCallExpr *CE = cast(S); if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj); } break; } case Stmt::ObjCMessageExprClass: { // In calls to super, include the implicit "self" pointer as being live. ObjCMessageExpr *CE = cast(S); if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance) val.liveDecls = LV.DSetFact.add(val.liveDecls, LV.analysisContext.getSelfDecl()); break; } case Stmt::DeclStmtClass: { const DeclStmt *DS = cast(S); if (const VarDecl *VD = dyn_cast(DS->getSingleDecl())) { for (const VariableArrayType* VA = FindVA(VD->getType()); VA != 0; VA = FindVA(VA->getElementType())) { AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr()); } } break; } case Stmt::PseudoObjectExprClass: { // A pseudo-object operation only directly consumes its result // expression. Expr *child = cast(S)->getResultExpr(); if (!child) return; if (OpaqueValueExpr *OV = dyn_cast(child)) child = OV->getSourceExpr(); child = child->IgnoreParens(); val.liveStmts = LV.SSetFact.add(val.liveStmts, child); return; } // FIXME: These cases eventually shouldn't be needed. case Stmt::ExprWithCleanupsClass: { S = cast(S)->getSubExpr(); break; } case Stmt::CXXBindTemporaryExprClass: { S = cast(S)->getSubExpr(); break; } case Stmt::UnaryExprOrTypeTraitExprClass: { // No need to unconditionally visit subexpressions. return; } } for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end(); it != ei; ++it) { if (Stmt *child = *it) AddLiveStmt(val.liveStmts, LV.SSetFact, child); } } void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { if (B->isAssignmentOp()) { if (!LV.killAtAssign) return; // Assigning to a variable? Expr *LHS = B->getLHS()->IgnoreParens(); if (DeclRefExpr *DR = dyn_cast(LHS)) if (const VarDecl *VD = dyn_cast(DR->getDecl())) { // Assignments to references don't kill the ref's address if (VD->getType()->isReferenceType()) return; if (!isAlwaysAlive(VD)) { // The variable is now dead. val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); } if (observer) observer->observerKill(DR); } } } void TransferFunctions::VisitBlockExpr(BlockExpr *BE) { AnalysisDeclContext::referenced_decls_iterator I, E; llvm::tie(I, E) = LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl()); for ( ; I != E ; ++I) { const VarDecl *VD = *I; if (isAlwaysAlive(VD)) continue; val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); } } void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { if (const VarDecl *D = dyn_cast(DR->getDecl())) if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) val.liveDecls = LV.DSetFact.add(val.liveDecls, D); } void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); DI != DE; ++DI) if (VarDecl *VD = dyn_cast(*DI)) { if (!isAlwaysAlive(VD)) val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); } } void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { // Kill the iteration variable. DeclRefExpr *DR = 0; const VarDecl *VD = 0; Stmt *element = OS->getElement(); if (DeclStmt *DS = dyn_cast(element)) { VD = cast(DS->getSingleDecl()); } else if ((DR = dyn_cast(cast(element)->IgnoreParens()))) { VD = cast(DR->getDecl()); } if (VD) { val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); if (observer && DR) observer->observerKill(DR); } } void TransferFunctions:: VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) { // While sizeof(var) doesn't technically extend the liveness of 'var', it // does extent the liveness of metadata if 'var' is a VariableArrayType. // We handle that special case here. if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) return; const Expr *subEx = UE->getArgumentExpr(); if (subEx->getType()->isVariableArrayType()) { assert(subEx->isLValue()); val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens()); } } void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { // Treat ++/-- as a kill. // Note we don't actually have to do anything if we don't have an observer, // since a ++/-- acts as both a kill and a "use". if (!observer) return; switch (UO->getOpcode()) { default: return; case UO_PostInc: case UO_PostDec: case UO_PreInc: case UO_PreDec: break; } if (DeclRefExpr *DR = dyn_cast(UO->getSubExpr()->IgnoreParens())) if (isa(DR->getDecl())) { // Treat ++/-- as a kill. observer->observerKill(DR); } } LiveVariables::LivenessValues LiveVariablesImpl::runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, LiveVariables::Observer *obs) { TransferFunctions TF(*this, val, obs, block); // Visit the terminator (if any). if (const Stmt *term = block->getTerminator()) TF.Visit(const_cast(term)); // Apply the transfer function for all Stmts in the block. for (CFGBlock::const_reverse_iterator it = block->rbegin(), ei = block->rend(); it != ei; ++it) { const CFGElement &elem = *it; if (Optional Dtor = elem.getAs()) { val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl()); continue; } if (!elem.getAs()) continue; const Stmt *S = elem.castAs().getStmt(); TF.Visit(const_cast(S)); stmtsToLiveness[S] = val; } return val; } void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { const CFG *cfg = getImpl(impl).analysisContext.getCFG(); for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); } LiveVariables::LiveVariables(void *im) : impl(im) {} LiveVariables::~LiveVariables() { delete (LiveVariablesImpl*) impl; } LiveVariables * LiveVariables::computeLiveness(AnalysisDeclContext &AC, bool killAtAssign) { // No CFG? Bail out. CFG *cfg = AC.getCFG(); if (!cfg) return 0; // The analysis currently has scalability issues for very large CFGs. // Bail out if it looks too large. if (cfg->getNumBlockIDs() > 300000) return 0; LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); // Construct the dataflow worklist. Enqueue the exit block as the // start of the analysis. DataflowWorklist worklist(*cfg, AC); llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); // FIXME: we should enqueue using post order. for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { const CFGBlock *block = *it; worklist.enqueueBlock(block); // FIXME: Scan for DeclRefExprs using in the LHS of an assignment. // We need to do this because we lack context in the reverse analysis // to determine if a DeclRefExpr appears in such a context, and thus // doesn't constitute a "use". if (killAtAssign) for (CFGBlock::const_iterator bi = block->begin(), be = block->end(); bi != be; ++bi) { if (Optional cs = bi->getAs()) { if (const BinaryOperator *BO = dyn_cast(cs->getStmt())) { if (BO->getOpcode() == BO_Assign) { if (const DeclRefExpr *DR = dyn_cast(BO->getLHS()->IgnoreParens())) { LV->inAssignment[DR] = 1; } } } } } } worklist.sortWorklist(); while (const CFGBlock *block = worklist.dequeue()) { // Determine if the block's end value has changed. If not, we // have nothing left to do for this block. LivenessValues &prevVal = LV->blocksEndToLiveness[block]; // Merge the values of all successor blocks. LivenessValues val; for (CFGBlock::const_succ_iterator it = block->succ_begin(), ei = block->succ_end(); it != ei; ++it) { if (const CFGBlock *succ = *it) { val = LV->merge(val, LV->blocksBeginToLiveness[succ]); } } if (!everAnalyzedBlock[block->getBlockID()]) everAnalyzedBlock[block->getBlockID()] = true; else if (prevVal.equals(val)) continue; prevVal = val; // Update the dataflow value for the start of this block. LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); // Enqueue the value to the predecessors. worklist.enqueuePredecessors(block); } return new LiveVariables(LV); } static bool compare_entries(const CFGBlock *A, const CFGBlock *B) { return A->getBlockID() < B->getBlockID(); } static bool compare_vd_entries(const Decl *A, const Decl *B) { SourceLocation ALoc = A->getLocStart(); SourceLocation BLoc = B->getLocStart(); return ALoc.getRawEncoding() < BLoc.getRawEncoding(); } void LiveVariables::dumpBlockLiveness(const SourceManager &M) { getImpl(impl).dumpBlockLiveness(M); } void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { std::vector vec; for (llvm::DenseMap::iterator it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); it != ei; ++it) { vec.push_back(it->first); } std::sort(vec.begin(), vec.end(), compare_entries); std::vector declVec; for (std::vector::iterator it = vec.begin(), ei = vec.end(); it != ei; ++it) { llvm::errs() << "\n[ B" << (*it)->getBlockID() << " (live variables at block exit) ]\n"; LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; declVec.clear(); for (llvm::ImmutableSet::iterator si = vals.liveDecls.begin(), se = vals.liveDecls.end(); si != se; ++si) { declVec.push_back(*si); } std::sort(declVec.begin(), declVec.end(), compare_vd_entries); for (std::vector::iterator di = declVec.begin(), de = declVec.end(); di != de; ++di) { llvm::errs() << " " << (*di)->getDeclName().getAsString() << " <"; (*di)->getLocation().dump(M); llvm::errs() << ">\n"; } } llvm::errs() << "\n"; } const void *LiveVariables::getTag() { static int x; return &x; } const void *RelaxedLiveVariables::getTag() { static int x; return &x; } @