1a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==// 2a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer// 3a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer// The LLVM Compiler Infrastructure 4a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer// 5a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer// This file is distributed under the University of Illinois Open Source 6a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer// License. See LICENSE.TXT for details. 7a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer// 8a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer//===----------------------------------------------------------------------===// 9a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer// 10a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer// This file implements Live Variables analysis for source-level CFGs. 11a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer// 12a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer//===----------------------------------------------------------------------===// 13a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer 14cf6e41baf2b23b6b56f0f79fff5554b7745737acTed Kremenek#include "clang/Analysis/Analyses/LiveVariables.h" 15a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer#include "clang/AST/Stmt.h" 16882998923889a2fcce9b49696506c499e22cf38fTed Kremenek#include "clang/AST/StmtVisitor.h" 1755fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/Analysis/Analyses/PostOrderCFGView.h" 1855fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/Analysis/AnalysisContext.h" 1955fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/Analysis/CFG.h" 2087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek#include "llvm/ADT/DenseMap.h" 21a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer#include "llvm/ADT/PostOrderIterator.h" 22a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer#include "llvm/Support/raw_ostream.h" 23882998923889a2fcce9b49696506c499e22cf38fTed Kremenek#include <algorithm> 24882998923889a2fcce9b49696506c499e22cf38fTed Kremenek#include <vector> 25e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 26e4e633400b1993c1174b47b774fa015220fa695cTed Kremenekusing namespace clang; 27e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 28882998923889a2fcce9b49696506c499e22cf38fTed Kremeneknamespace { 2987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 3087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekclass DataflowWorklist { 3187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SmallVector<const CFGBlock *, 20> worklist; 3287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::BitVector enqueuedBlocks; 33edb186399e19d84c93f25440435ab9a695138e79Ted Kremenek PostOrderCFGView *POV; 3487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekpublic: 351d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx) 3687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek : enqueuedBlocks(cfg.getNumBlockIDs()), 37edb186399e19d84c93f25440435ab9a695138e79Ted Kremenek POV(Ctx.getAnalysis<PostOrderCFGView>()) {} 3887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 3987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek void enqueueBlock(const CFGBlock *block); 4087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek void enqueuePredecessors(const CFGBlock *block); 4187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 4287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek const CFGBlock *dequeue(); 4387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 4487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek void sortWorklist(); 4587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek}; 4687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 4787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek} 4887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 4987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekvoid DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { 5087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (block && !enqueuedBlocks[block->getBlockID()]) { 5187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek enqueuedBlocks[block->getBlockID()] = true; 5287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek worklist.push_back(block); 5387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek } 5487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek} 5587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 5687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekvoid DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { 5787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek const unsigned OldWorklistSize = worklist.size(); 5887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek for (CFGBlock::const_pred_iterator I = block->pred_begin(), 5987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek E = block->pred_end(); I != E; ++I) { 6087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek enqueueBlock(*I); 6187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek } 6287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 6387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 6487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek return; 6587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 6687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek sortWorklist(); 6787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek} 6887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 6987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekvoid DataflowWorklist::sortWorklist() { 70edb186399e19d84c93f25440435ab9a695138e79Ted Kremenek std::sort(worklist.begin(), worklist.end(), POV->getComparator()); 7187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek} 7287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 7387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekconst CFGBlock *DataflowWorklist::dequeue() { 7487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (worklist.empty()) 756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 76344472ebeded2fca2ed5013b9e87f81d09bfa908Robert Wilhelm const CFGBlock *b = worklist.pop_back_val(); 7787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek enqueuedBlocks[b->getBlockID()] = false; 7887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek return b; 7987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek} 8087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 8187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremeneknamespace { 8287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekclass LiveVariablesImpl { 8387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekpublic: 841d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &analysisContext; 8587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek std::vector<LiveVariables::LivenessValues> cfgBlockValues; 8687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::ImmutableSet<const Stmt *>::Factory SSetFact; 8787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; 8887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness; 8987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness; 9087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness; 9187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment; 9287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek const bool killAtAssign; 9387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 9487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek LiveVariables::LivenessValues 9587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek merge(LiveVariables::LivenessValues valsA, 9687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek LiveVariables::LivenessValues valsB); 976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines LiveVariables::LivenessValues 996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, 1006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines LiveVariables::Observer *obs = nullptr); 10187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 10287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek void dumpBlockLiveness(const SourceManager& M); 10387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 1041d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) 1053c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek : analysisContext(ac), 1063c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek SSetFact(false), // Do not canonicalize ImmutableSets by default. 1073c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek DSetFact(false), // This is a *major* performance win. 1083c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek killAtAssign(KillAtAssign) {} 10987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek}; 110882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1117deed0c65b315cac037539401c49586283158d9fTed Kremenek 1129c378f705405d37f49795d5e915989de774fe11fTed Kremenekstatic LiveVariablesImpl &getImpl(void *x) { 113882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return *((LiveVariablesImpl *) x); 114882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1157deed0c65b315cac037539401c49586283158d9fTed Kremenek 1167deed0c65b315cac037539401c49586283158d9fTed Kremenek//===----------------------------------------------------------------------===// 117882998923889a2fcce9b49696506c499e22cf38fTed Kremenek// Operations and queries on LivenessValues. 1181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump//===----------------------------------------------------------------------===// 119e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 120882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::LivenessValues::isLive(const Stmt *S) const { 121882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return liveStmts.contains(S); 122882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1237deed0c65b315cac037539401c49586283158d9fTed Kremenek 124882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { 125882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return liveDecls.contains(D); 126882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 128882998923889a2fcce9b49696506c499e22cf38fTed Kremeneknamespace { 129882998923889a2fcce9b49696506c499e22cf38fTed Kremenek template <typename SET> 13087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SET mergeSets(SET A, SET B) { 13187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (A.isEmpty()) 13287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek return B; 13387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 134882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { 13587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek A = A.add(*it); 136882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 137882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return A; 138882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 139882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1407deed0c65b315cac037539401c49586283158d9fTed Kremenek 14199ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikievoid LiveVariables::Observer::anchor() { } 14299ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 143882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables::LivenessValues 144882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, 145882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues valsB) { 14687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 14787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::ImmutableSetRef<const Stmt *> 14887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()), 14987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()); 15087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 15187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 15287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::ImmutableSetRef<const VarDecl *> 15387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), 15487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); 15587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 15687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 15787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SSetRefA = mergeSets(SSetRefA, SSetRefB); 15887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek DSetRefA = mergeSets(DSetRefA, DSetRefB); 15987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 1603c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek // asImmutableSet() canonicalizes the tree, allowing us to do an easy 1613c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek // comparison afterwards. 16287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), 16387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek DSetRefA.asImmutableSet()); 164882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1657deed0c65b315cac037539401c49586283158d9fTed Kremenek 166882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { 167882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return liveStmts == V.liveStmts && liveDecls == V.liveDecls; 168882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 170882998923889a2fcce9b49696506c499e22cf38fTed Kremenek//===----------------------------------------------------------------------===// 171882998923889a2fcce9b49696506c499e22cf38fTed Kremenek// Query methods. 172882998923889a2fcce9b49696506c499e22cf38fTed Kremenek//===----------------------------------------------------------------------===// 1737deed0c65b315cac037539401c49586283158d9fTed Kremenek 174882998923889a2fcce9b49696506c499e22cf38fTed Kremenekstatic bool isAlwaysAlive(const VarDecl *D) { 175882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return D->hasGlobalStorage(); 176882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1774111024be81e7c0525e42dadcc126d27e5bf2425Chris Lattner 178882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { 179882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); 180882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 182882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { 183882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); 184882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 186882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) { 187882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return getImpl(impl).stmtsToLiveness[Loc].isLive(S); 188e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek} 189e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 190e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek//===----------------------------------------------------------------------===// 191882998923889a2fcce9b49696506c499e22cf38fTed Kremenek// Dataflow computation. 1921eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump//===----------------------------------------------------------------------===// 193e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 194e4e633400b1993c1174b47b774fa015220fa695cTed Kremeneknamespace { 195882998923889a2fcce9b49696506c499e22cf38fTed Kremenekclass TransferFunctions : public StmtVisitor<TransferFunctions> { 196882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariablesImpl &LV; 197882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues &val; 198882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::Observer *observer; 199882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFGBlock *currentBlock; 200882998923889a2fcce9b49696506c499e22cf38fTed Kremenekpublic: 201882998923889a2fcce9b49696506c499e22cf38fTed Kremenek TransferFunctions(LiveVariablesImpl &im, 202882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues &Val, 203882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::Observer *Observer, 204882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFGBlock *CurrentBlock) 205882998923889a2fcce9b49696506c499e22cf38fTed Kremenek : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} 206882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 207882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitBinaryOperator(BinaryOperator *BO); 208882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitBlockExpr(BlockExpr *BE); 209882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitDeclRefExpr(DeclRefExpr *DR); 210882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitDeclStmt(DeclStmt *DS); 211882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); 212882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); 213882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitUnaryOperator(UnaryOperator *UO); 214882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void Visit(Stmt *S); 215882998923889a2fcce9b49696506c499e22cf38fTed Kremenek}; 216882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 2171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 218f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenekstatic const VariableArrayType *FindVA(QualType Ty) { 219f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek const Type *ty = Ty.getTypePtr(); 220f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) { 221f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT)) 222f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek if (VAT->getSizeExpr()) 223f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek return VAT; 224f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek 225f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek ty = VT->getElementType().getTypePtr(); 226f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 2276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 229f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek} 230f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek 231ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenekstatic const Stmt *LookThroughStmt(const Stmt *S) { 2326bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek while (S) { 2336bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek if (const Expr *Ex = dyn_cast<Expr>(S)) 2346bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek S = Ex->IgnoreParens(); 235f3fb5c5395d382ffd24ec2675237fa9bdff6266eJohn McCall if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(S)) { 236f3fb5c5395d382ffd24ec2675237fa9bdff6266eJohn McCall S = EWC->getSubExpr(); 237f3fb5c5395d382ffd24ec2675237fa9bdff6266eJohn McCall continue; 238f3fb5c5395d382ffd24ec2675237fa9bdff6266eJohn McCall } 2396bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) { 2406bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek S = OVE->getSourceExpr(); 2416bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek continue; 2426bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek } 2436bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek break; 2446bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek } 245ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek return S; 246ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek} 247ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek 248ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenekstatic void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set, 249ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek llvm::ImmutableSet<const Stmt *>::Factory &F, 250ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek const Stmt *S) { 251ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek Set = F.add(Set, LookThroughStmt(S)); 252ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek} 253ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek 254882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::Visit(Stmt *S) { 255882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (observer) 256882998923889a2fcce9b49696506c499e22cf38fTed Kremenek observer->observeStmt(S, currentBlock, val); 257882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 258882998923889a2fcce9b49696506c499e22cf38fTed Kremenek StmtVisitor<TransferFunctions>::Visit(S); 259882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 260882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (isa<Expr>(S)) { 261882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveStmts = LV.SSetFact.remove(val.liveStmts, S); 26286946745225096243f6969dc745267b78fc211a6Ted Kremenek } 2631eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 264882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Mark all children expressions live. 265882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 266882998923889a2fcce9b49696506c499e22cf38fTed Kremenek switch (S->getStmtClass()) { 267882998923889a2fcce9b49696506c499e22cf38fTed Kremenek default: 268882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 269882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case Stmt::StmtExprClass: { 270882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // For statement expressions, look through the compound statement. 271882998923889a2fcce9b49696506c499e22cf38fTed Kremenek S = cast<StmtExpr>(S)->getSubStmt(); 272882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 273882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 274882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case Stmt::CXXMemberCallExprClass: { 275882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Include the implicit "this" pointer as being live. 276882998923889a2fcce9b49696506c499e22cf38fTed Kremenek CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S); 277c80850353f4051f36be9f5be9738cf877406311aTed Kremenek if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { 278ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj); 279c80850353f4051f36be9f5be9738cf877406311aTed Kremenek } 280882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 281882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 282c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks case Stmt::ObjCMessageExprClass: { 283c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks // In calls to super, include the implicit "self" pointer as being live. 284c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S); 285c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance) 286c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks val.liveDecls = LV.DSetFact.add(val.liveDecls, 287c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks LV.analysisContext.getSelfDecl()); 288c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks break; 289c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks } 290f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek case Stmt::DeclStmtClass: { 291f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek const DeclStmt *DS = cast<DeclStmt>(S); 292f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) { 293f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek for (const VariableArrayType* VA = FindVA(VD->getType()); 2946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines VA != nullptr; VA = FindVA(VA->getElementType())) { 295ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr()); 296f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 297f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 298f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek break; 299f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 3004b9c2d235fb9449e249d74f48ecfec601650de93John McCall case Stmt::PseudoObjectExprClass: { 3014b9c2d235fb9449e249d74f48ecfec601650de93John McCall // A pseudo-object operation only directly consumes its result 3024b9c2d235fb9449e249d74f48ecfec601650de93John McCall // expression. 3034b9c2d235fb9449e249d74f48ecfec601650de93John McCall Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr(); 3044b9c2d235fb9449e249d74f48ecfec601650de93John McCall if (!child) return; 3054b9c2d235fb9449e249d74f48ecfec601650de93John McCall if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child)) 3064b9c2d235fb9449e249d74f48ecfec601650de93John McCall child = OV->getSourceExpr(); 3074b9c2d235fb9449e249d74f48ecfec601650de93John McCall child = child->IgnoreParens(); 3084b9c2d235fb9449e249d74f48ecfec601650de93John McCall val.liveStmts = LV.SSetFact.add(val.liveStmts, child); 3094b9c2d235fb9449e249d74f48ecfec601650de93John McCall return; 3104b9c2d235fb9449e249d74f48ecfec601650de93John McCall } 3114b9c2d235fb9449e249d74f48ecfec601650de93John McCall 312882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // FIXME: These cases eventually shouldn't be needed. 313882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case Stmt::ExprWithCleanupsClass: { 314882998923889a2fcce9b49696506c499e22cf38fTed Kremenek S = cast<ExprWithCleanups>(S)->getSubExpr(); 315882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 316882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 317882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case Stmt::CXXBindTemporaryExprClass: { 318882998923889a2fcce9b49696506c499e22cf38fTed Kremenek S = cast<CXXBindTemporaryExpr>(S)->getSubExpr(); 319882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 320882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 321f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek case Stmt::UnaryExprOrTypeTraitExprClass: { 322f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek // No need to unconditionally visit subexpressions. 323f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek return; 324f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 3251b54221f6865b0daae1b8eb8f84bf5d291e8b864Zhongxing Xu } 326bfbcefb7e99905218b3f0a895b7bc1992203123bTed Kremenek 327882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end(); 328882998923889a2fcce9b49696506c499e22cf38fTed Kremenek it != ei; ++it) { 329ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek if (Stmt *child = *it) 330ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek AddLiveStmt(val.liveStmts, LV.SSetFact, child); 331882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 332bfbcefb7e99905218b3f0a895b7bc1992203123bTed Kremenek} 3331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 334882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { 335882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (B->isAssignmentOp()) { 336882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!LV.killAtAssign) 337882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 338882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 339882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Assigning to a variable? 340882998923889a2fcce9b49696506c499e22cf38fTed Kremenek Expr *LHS = B->getLHS()->IgnoreParens(); 341882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 3429c378f705405d37f49795d5e915989de774fe11fTed Kremenek if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) 343882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 344882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Assignments to references don't kill the ref's address 345882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (VD->getType()->isReferenceType()) 346882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 347882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 348882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!isAlwaysAlive(VD)) { 349882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // The variable is now dead. 350882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 351882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 352882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 353882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (observer) 354882998923889a2fcce9b49696506c499e22cf38fTed Kremenek observer->observerKill(DR); 355882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 356882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 35737622081d8a139a3249613acaa80106ec97261fbTed Kremenek} 35837622081d8a139a3249613acaa80106ec97261fbTed Kremenek 359882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitBlockExpr(BlockExpr *BE) { 36015ce164836472bfba88b30e53aa3f6ac0fb8a95dTed Kremenek AnalysisDeclContext::referenced_decls_iterator I, E; 361651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines std::tie(I, E) = 36215ce164836472bfba88b30e53aa3f6ac0fb8a95dTed Kremenek LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl()); 36315ce164836472bfba88b30e53aa3f6ac0fb8a95dTed Kremenek for ( ; I != E ; ++I) { 36415ce164836472bfba88b30e53aa3f6ac0fb8a95dTed Kremenek const VarDecl *VD = *I; 365882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (isAlwaysAlive(VD)) 366882998923889a2fcce9b49696506c499e22cf38fTed Kremenek continue; 367882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); 368b1a7b65231e86f7da6aacbf00bcdc16c56350e65Ted Kremenek } 369e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek} 3701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 371882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { 372882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) 373882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) 374882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.add(val.liveDecls, D); 375e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek} 376e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 377882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 378651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (const auto *DI : DS->decls()) 379651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (const auto *VD = dyn_cast<VarDecl>(DI)) { 380882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!isAlwaysAlive(VD)) 381882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 382882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 383882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 3841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 385882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { 386882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Kill the iteration variable. 3876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines DeclRefExpr *DR = nullptr; 3886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const VarDecl *VD = nullptr; 3891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 390882998923889a2fcce9b49696506c499e22cf38fTed Kremenek Stmt *element = OS->getElement(); 391882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) { 3927e24e82a70a2c681f4291a3397bcd1e1005f251aChris Lattner VD = cast<VarDecl>(DS->getSingleDecl()); 3938f5aab696173cc6e9c9963635d91dc2e83d54442Ted Kremenek } 394882998923889a2fcce9b49696506c499e22cf38fTed Kremenek else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) { 395882998923889a2fcce9b49696506c499e22cf38fTed Kremenek VD = cast<VarDecl>(DR->getDecl()); 396882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 397882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 3988f646002d8493ad7647d28b0acc7be425360f990Ted Kremenek if (VD) { 399882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 400882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (observer && DR) 401882998923889a2fcce9b49696506c499e22cf38fTed Kremenek observer->observerKill(DR); 4028f646002d8493ad7647d28b0acc7be425360f990Ted Kremenek } 4038f5aab696173cc6e9c9963635d91dc2e83d54442Ted Kremenek} 4048f5aab696173cc6e9c9963635d91dc2e83d54442Ted Kremenek 405882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions:: 406882998923889a2fcce9b49696506c499e22cf38fTed KremenekVisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) 407882998923889a2fcce9b49696506c499e22cf38fTed Kremenek{ 408882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // While sizeof(var) doesn't technically extend the liveness of 'var', it 409882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // does extent the liveness of metadata if 'var' is a VariableArrayType. 410882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // We handle that special case here. 411882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) 412882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 413882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 414f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek const Expr *subEx = UE->getArgumentExpr(); 415f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek if (subEx->getType()->isVariableArrayType()) { 416f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek assert(subEx->isLValue()); 417f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens()); 418f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 419882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 4201eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 421882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { 422882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Treat ++/-- as a kill. 423882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Note we don't actually have to do anything if we don't have an observer, 424882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // since a ++/-- acts as both a kill and a "use". 425882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!observer) 426882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 427882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 428882998923889a2fcce9b49696506c499e22cf38fTed Kremenek switch (UO->getOpcode()) { 429882998923889a2fcce9b49696506c499e22cf38fTed Kremenek default: 430882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 4312de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PostInc: 432882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case UO_PostDec: 4332de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PreInc: 4342de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PreDec: 435882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 436e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek } 437882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 438882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) 439882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (isa<VarDecl>(DR->getDecl())) { 440882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Treat ++/-- as a kill. 441882998923889a2fcce9b49696506c499e22cf38fTed Kremenek observer->observerKill(DR); 442dcc48100ef7c224cecf5b9ccdd5c0d39e476468aTed Kremenek } 443f63aa45ca9d4f4782aa236415c63e00f7ffaf185Ted Kremenek} 4441eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 445882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables::LivenessValues 446882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariablesImpl::runOnBlock(const CFGBlock *block, 447882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues val, 448882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::Observer *obs) { 449e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 450882998923889a2fcce9b49696506c499e22cf38fTed Kremenek TransferFunctions TF(*this, val, obs, block); 451882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 452882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Visit the terminator (if any). 453882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (const Stmt *term = block->getTerminator()) 454882998923889a2fcce9b49696506c499e22cf38fTed Kremenek TF.Visit(const_cast<Stmt*>(term)); 455882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 456882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Apply the transfer function for all Stmts in the block. 457882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFGBlock::const_reverse_iterator it = block->rbegin(), 458882998923889a2fcce9b49696506c499e22cf38fTed Kremenek ei = block->rend(); it != ei; ++it) { 459882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFGElement &elem = *it; 460d7f1d134a03ace51f8d142fbb7f436330704ede5Jordan Rose 461b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (Optional<CFGAutomaticObjDtor> Dtor = 462b07805485c603be3d8011f72611465324c9e664bDavid Blaikie elem.getAs<CFGAutomaticObjDtor>()) { 463b07805485c603be3d8011f72611465324c9e664bDavid Blaikie val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl()); 464d7f1d134a03ace51f8d142fbb7f436330704ede5Jordan Rose continue; 465d7f1d134a03ace51f8d142fbb7f436330704ede5Jordan Rose } 466d7f1d134a03ace51f8d142fbb7f436330704ede5Jordan Rose 467fdf6a279c9a75c778eba382d9a156697092982a1David Blaikie if (!elem.getAs<CFGStmt>()) 468882998923889a2fcce9b49696506c499e22cf38fTed Kremenek continue; 469882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 470fdf6a279c9a75c778eba382d9a156697092982a1David Blaikie const Stmt *S = elem.castAs<CFGStmt>().getStmt(); 471882998923889a2fcce9b49696506c499e22cf38fTed Kremenek TF.Visit(const_cast<Stmt*>(S)); 472882998923889a2fcce9b49696506c499e22cf38fTed Kremenek stmtsToLiveness[S] = val; 473882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 474882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return val; 475fdd225ed6f362a8550e597eb875d9c402b8a309cTed Kremenek} 47627b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek 477882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { 478882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFG *cfg = getImpl(impl).analysisContext.getCFG(); 479882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) 480882998923889a2fcce9b49696506c499e22cf38fTed Kremenek getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); 48127b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek} 48227b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek 483882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables::LiveVariables(void *im) : impl(im) {} 48427b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek 485882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables::~LiveVariables() { 486882998923889a2fcce9b49696506c499e22cf38fTed Kremenek delete (LiveVariablesImpl*) impl; 48727b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek} 48827b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek 489882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables * 4901d26f48dc2eea1c07431ca1519d7034a21b9bcffTed KremenekLiveVariables::computeLiveness(AnalysisDeclContext &AC, 491882998923889a2fcce9b49696506c499e22cf38fTed Kremenek bool killAtAssign) { 492882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 493882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // No CFG? Bail out. 494882998923889a2fcce9b49696506c499e22cf38fTed Kremenek CFG *cfg = AC.getCFG(); 495882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!cfg) 4966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 497882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 498d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek // The analysis currently has scalability issues for very large CFGs. 499d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek // Bail out if it looks too large. 500d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek if (cfg->getNumBlockIDs() > 300000) 5016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 502d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek 503882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); 504882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 505882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Construct the dataflow worklist. Enqueue the exit block as the 506882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // start of the analysis. 507edb186399e19d84c93f25440435ab9a695138e79Ted Kremenek DataflowWorklist worklist(*cfg, AC); 508882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); 509882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 510882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // FIXME: we should enqueue using post order. 511882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { 512882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFGBlock *block = *it; 513882998923889a2fcce9b49696506c499e22cf38fTed Kremenek worklist.enqueueBlock(block); 514882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 515882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // FIXME: Scan for DeclRefExprs using in the LHS of an assignment. 516882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // We need to do this because we lack context in the reverse analysis 517882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // to determine if a DeclRefExpr appears in such a context, and thus 518882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // doesn't constitute a "use". 519882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (killAtAssign) 520882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFGBlock::const_iterator bi = block->begin(), be = block->end(); 521882998923889a2fcce9b49696506c499e22cf38fTed Kremenek bi != be; ++bi) { 522b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) { 523b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (const BinaryOperator *BO = 524b07805485c603be3d8011f72611465324c9e664bDavid Blaikie dyn_cast<BinaryOperator>(cs->getStmt())) { 525882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (BO->getOpcode() == BO_Assign) { 526882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (const DeclRefExpr *DR = 527882998923889a2fcce9b49696506c499e22cf38fTed Kremenek dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) { 528882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LV->inAssignment[DR] = 1; 529882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 530882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 531882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 532882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 533882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 534882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 535882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 53687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek worklist.sortWorklist(); 53787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 53887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek while (const CFGBlock *block = worklist.dequeue()) { 539882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Determine if the block's end value has changed. If not, we 540882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // have nothing left to do for this block. 541882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LivenessValues &prevVal = LV->blocksEndToLiveness[block]; 542882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 543882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Merge the values of all successor blocks. 544882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LivenessValues val; 545882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFGBlock::const_succ_iterator it = block->succ_begin(), 546882998923889a2fcce9b49696506c499e22cf38fTed Kremenek ei = block->succ_end(); it != ei; ++it) { 54787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (const CFGBlock *succ = *it) { 548882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val = LV->merge(val, LV->blocksBeginToLiveness[succ]); 54987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek } 550882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 551882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 552882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!everAnalyzedBlock[block->getBlockID()]) 553882998923889a2fcce9b49696506c499e22cf38fTed Kremenek everAnalyzedBlock[block->getBlockID()] = true; 554882998923889a2fcce9b49696506c499e22cf38fTed Kremenek else if (prevVal.equals(val)) 555882998923889a2fcce9b49696506c499e22cf38fTed Kremenek continue; 556882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 557882998923889a2fcce9b49696506c499e22cf38fTed Kremenek prevVal = val; 558882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 559882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Update the dataflow value for the start of this block. 560882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); 561882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 562882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Enqueue the value to the predecessors. 56387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek worklist.enqueuePredecessors(block); 564882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 565882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 566882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return new LiveVariables(LV); 567055c275fabcbe1ef246942c8b5f7d49b3a173500Ted Kremenek} 568055c275fabcbe1ef246942c8b5f7d49b3a173500Ted Kremenek 569882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid LiveVariables::dumpBlockLiveness(const SourceManager &M) { 570882998923889a2fcce9b49696506c499e22cf38fTed Kremenek getImpl(impl).dumpBlockLiveness(M); 5712a9da9c85fbe559299a3d123180ed07a53b533c6Ted Kremenek} 5722a9da9c85fbe559299a3d123180ed07a53b533c6Ted Kremenek 573882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { 574882998923889a2fcce9b49696506c499e22cf38fTed Kremenek std::vector<const CFGBlock *> vec; 575882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator 576882998923889a2fcce9b49696506c499e22cf38fTed Kremenek it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); 577882998923889a2fcce9b49696506c499e22cf38fTed Kremenek it != ei; ++it) { 578882998923889a2fcce9b49696506c499e22cf38fTed Kremenek vec.push_back(it->first); 579882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 580651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines std::sort(vec.begin(), vec.end(), [](const CFGBlock *A, const CFGBlock *B) { 581651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return A->getBlockID() < B->getBlockID(); 582651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines }); 583e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 584882998923889a2fcce9b49696506c499e22cf38fTed Kremenek std::vector<const VarDecl*> declVec; 5851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 586882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (std::vector<const CFGBlock *>::iterator 587882998923889a2fcce9b49696506c499e22cf38fTed Kremenek it = vec.begin(), ei = vec.end(); it != ei; ++it) { 588882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::errs() << "\n[ B" << (*it)->getBlockID() 589882998923889a2fcce9b49696506c499e22cf38fTed Kremenek << " (live variables at block exit) ]\n"; 590882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 591882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; 592882998923889a2fcce9b49696506c499e22cf38fTed Kremenek declVec.clear(); 593882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 594882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (llvm::ImmutableSet<const VarDecl *>::iterator si = 595882998923889a2fcce9b49696506c499e22cf38fTed Kremenek vals.liveDecls.begin(), 596882998923889a2fcce9b49696506c499e22cf38fTed Kremenek se = vals.liveDecls.end(); si != se; ++si) { 597882998923889a2fcce9b49696506c499e22cf38fTed Kremenek declVec.push_back(*si); 598882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 599651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 600651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines std::sort(declVec.begin(), declVec.end(), [](const Decl *A, const Decl *B) { 601651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return A->getLocStart() < B->getLocStart(); 602651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines }); 603651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 604882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (std::vector<const VarDecl*>::iterator di = declVec.begin(), 605882998923889a2fcce9b49696506c499e22cf38fTed Kremenek de = declVec.end(); di != de; ++di) { 606882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::errs() << " " << (*di)->getDeclName().getAsString() 607882998923889a2fcce9b49696506c499e22cf38fTed Kremenek << " <"; 608882998923889a2fcce9b49696506c499e22cf38fTed Kremenek (*di)->getLocation().dump(M); 609c0d567279f861844c9e7da492729425a90c03397Daniel Dunbar llvm::errs() << ">\n"; 610e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek } 61127b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek } 612882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::errs() << "\n"; 613c0576ca6c6ba136e583985041bd324b0acc38f40Ted Kremenek} 614882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 615a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenekconst void *LiveVariables::getTag() { static int x; return &x; } 616a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenekconst void *RelaxedLiveVariables::getTag() { static int x; return &x; } 617