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 enqueueSuccessors(const CFGBlock *block); 4187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek void enqueuePredecessors(const CFGBlock *block); 4287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 4387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek const CFGBlock *dequeue(); 4487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 4587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek void sortWorklist(); 4687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek}; 4787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 4887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek} 4987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 5087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekvoid DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { 5187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (block && !enqueuedBlocks[block->getBlockID()]) { 5287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek enqueuedBlocks[block->getBlockID()] = true; 5387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek worklist.push_back(block); 5487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek } 5587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek} 5687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 5787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekvoid DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 5887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek const unsigned OldWorklistSize = worklist.size(); 5987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek for (CFGBlock::const_succ_iterator I = block->succ_begin(), 6087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek E = block->succ_end(); I != E; ++I) { 6187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek enqueueBlock(*I); 6287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek } 6387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 6487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 6587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek return; 6687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 6787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek sortWorklist(); 6887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek} 6987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 7087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekvoid DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { 7187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek const unsigned OldWorklistSize = worklist.size(); 7287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek for (CFGBlock::const_pred_iterator I = block->pred_begin(), 7387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek E = block->pred_end(); I != E; ++I) { 7487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek enqueueBlock(*I); 7587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek } 7687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 7787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 7887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek return; 7987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 8087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek sortWorklist(); 8187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek} 8287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 8387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekvoid DataflowWorklist::sortWorklist() { 84edb186399e19d84c93f25440435ab9a695138e79Ted Kremenek std::sort(worklist.begin(), worklist.end(), POV->getComparator()); 8587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek} 8687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 8787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekconst CFGBlock *DataflowWorklist::dequeue() { 8887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (worklist.empty()) 8987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek return 0; 9087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek const CFGBlock *b = worklist.back(); 9187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek worklist.pop_back(); 9287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek enqueuedBlocks[b->getBlockID()] = false; 9387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek return b; 9487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek} 9587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 9687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremeneknamespace { 9787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekclass LiveVariablesImpl { 9887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenekpublic: 991d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek AnalysisDeclContext &analysisContext; 10087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek std::vector<LiveVariables::LivenessValues> cfgBlockValues; 10187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::ImmutableSet<const Stmt *>::Factory SSetFact; 10287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; 10387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness; 10487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness; 10587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness; 10687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment; 10787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek const bool killAtAssign; 10887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 10987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek LiveVariables::LivenessValues 11087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek merge(LiveVariables::LivenessValues valsA, 11187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek LiveVariables::LivenessValues valsB); 11287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 11387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek LiveVariables::LivenessValues runOnBlock(const CFGBlock *block, 11487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek LiveVariables::LivenessValues val, 11587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek LiveVariables::Observer *obs = 0); 11687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 11787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek void dumpBlockLiveness(const SourceManager& M); 11887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 1191d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) 1203c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek : analysisContext(ac), 1213c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek SSetFact(false), // Do not canonicalize ImmutableSets by default. 1223c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek DSetFact(false), // This is a *major* performance win. 1233c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek killAtAssign(KillAtAssign) {} 12487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek}; 125882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1267deed0c65b315cac037539401c49586283158d9fTed Kremenek 1279c378f705405d37f49795d5e915989de774fe11fTed Kremenekstatic LiveVariablesImpl &getImpl(void *x) { 128882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return *((LiveVariablesImpl *) x); 129882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1307deed0c65b315cac037539401c49586283158d9fTed Kremenek 1317deed0c65b315cac037539401c49586283158d9fTed Kremenek//===----------------------------------------------------------------------===// 132882998923889a2fcce9b49696506c499e22cf38fTed Kremenek// Operations and queries on LivenessValues. 1331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump//===----------------------------------------------------------------------===// 134e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 135882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::LivenessValues::isLive(const Stmt *S) const { 136882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return liveStmts.contains(S); 137882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1387deed0c65b315cac037539401c49586283158d9fTed Kremenek 139882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { 140882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return liveDecls.contains(D); 141882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1421eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 143882998923889a2fcce9b49696506c499e22cf38fTed Kremeneknamespace { 144882998923889a2fcce9b49696506c499e22cf38fTed Kremenek template <typename SET> 14587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SET mergeSets(SET A, SET B) { 14687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (A.isEmpty()) 14787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek return B; 14887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 149882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { 15087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek A = A.add(*it); 151882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 152882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return A; 153882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 154882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1557deed0c65b315cac037539401c49586283158d9fTed Kremenek 15699ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikievoid LiveVariables::Observer::anchor() { } 15799ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 158882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables::LivenessValues 159882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, 160882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues valsB) { 16187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 16287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::ImmutableSetRef<const Stmt *> 16387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()), 16487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()); 16587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 16687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 16787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::ImmutableSetRef<const VarDecl *> 16887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), 16987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); 17087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 17187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 17287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SSetRefA = mergeSets(SSetRefA, SSetRefB); 17387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek DSetRefA = mergeSets(DSetRefA, DSetRefB); 17487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 1753c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek // asImmutableSet() canonicalizes the tree, allowing us to do an easy 1763c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek // comparison afterwards. 17787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), 17887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek DSetRefA.asImmutableSet()); 179882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1807deed0c65b315cac037539401c49586283158d9fTed Kremenek 181882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { 182882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return liveStmts == V.liveStmts && liveDecls == V.liveDecls; 183882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 185882998923889a2fcce9b49696506c499e22cf38fTed Kremenek//===----------------------------------------------------------------------===// 186882998923889a2fcce9b49696506c499e22cf38fTed Kremenek// Query methods. 187882998923889a2fcce9b49696506c499e22cf38fTed Kremenek//===----------------------------------------------------------------------===// 1887deed0c65b315cac037539401c49586283158d9fTed Kremenek 189882998923889a2fcce9b49696506c499e22cf38fTed Kremenekstatic bool isAlwaysAlive(const VarDecl *D) { 190882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return D->hasGlobalStorage(); 191882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1924111024be81e7c0525e42dadcc126d27e5bf2425Chris Lattner 193882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { 194882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); 195882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1961eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 197882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { 198882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); 199882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 2001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 201882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) { 202882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return getImpl(impl).stmtsToLiveness[Loc].isLive(S); 203e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek} 204e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 205e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek//===----------------------------------------------------------------------===// 206882998923889a2fcce9b49696506c499e22cf38fTed Kremenek// Dataflow computation. 2071eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump//===----------------------------------------------------------------------===// 208e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 209e4e633400b1993c1174b47b774fa015220fa695cTed Kremeneknamespace { 210882998923889a2fcce9b49696506c499e22cf38fTed Kremenekclass TransferFunctions : public StmtVisitor<TransferFunctions> { 211882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariablesImpl &LV; 212882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues &val; 213882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::Observer *observer; 214882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFGBlock *currentBlock; 215882998923889a2fcce9b49696506c499e22cf38fTed Kremenekpublic: 216882998923889a2fcce9b49696506c499e22cf38fTed Kremenek TransferFunctions(LiveVariablesImpl &im, 217882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues &Val, 218882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::Observer *Observer, 219882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFGBlock *CurrentBlock) 220882998923889a2fcce9b49696506c499e22cf38fTed Kremenek : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} 221882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 222882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitBinaryOperator(BinaryOperator *BO); 223882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitBlockExpr(BlockExpr *BE); 224882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitDeclRefExpr(DeclRefExpr *DR); 225882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitDeclStmt(DeclStmt *DS); 226882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); 227882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); 228882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitUnaryOperator(UnaryOperator *UO); 229882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void Visit(Stmt *S); 230882998923889a2fcce9b49696506c499e22cf38fTed Kremenek}; 231882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 2321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 233f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenekstatic const VariableArrayType *FindVA(QualType Ty) { 234f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek const Type *ty = Ty.getTypePtr(); 235f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) { 236f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT)) 237f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek if (VAT->getSizeExpr()) 238f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek return VAT; 239f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek 240f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek ty = VT->getElementType().getTypePtr(); 241f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 242f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek 243f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek return 0; 244f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek} 245f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek 246ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenekstatic const Stmt *LookThroughStmt(const Stmt *S) { 2476bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek while (S) { 2486bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek if (const Expr *Ex = dyn_cast<Expr>(S)) 2496bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek S = Ex->IgnoreParens(); 250f3fb5c5395d382ffd24ec2675237fa9bdff6266eJohn McCall if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(S)) { 251f3fb5c5395d382ffd24ec2675237fa9bdff6266eJohn McCall S = EWC->getSubExpr(); 252f3fb5c5395d382ffd24ec2675237fa9bdff6266eJohn McCall continue; 253f3fb5c5395d382ffd24ec2675237fa9bdff6266eJohn McCall } 2546bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) { 2556bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek S = OVE->getSourceExpr(); 2566bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek continue; 2576bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek } 2586bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek break; 2596bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek } 260ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek return S; 261ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek} 262ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek 263ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenekstatic void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set, 264ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek llvm::ImmutableSet<const Stmt *>::Factory &F, 265ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek const Stmt *S) { 266ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek Set = F.add(Set, LookThroughStmt(S)); 267ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek} 268ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek 269882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::Visit(Stmt *S) { 270882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (observer) 271882998923889a2fcce9b49696506c499e22cf38fTed Kremenek observer->observeStmt(S, currentBlock, val); 272882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 273882998923889a2fcce9b49696506c499e22cf38fTed Kremenek StmtVisitor<TransferFunctions>::Visit(S); 274882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 275882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (isa<Expr>(S)) { 276882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveStmts = LV.SSetFact.remove(val.liveStmts, S); 27786946745225096243f6969dc745267b78fc211a6Ted Kremenek } 2781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 279882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Mark all children expressions live. 280882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 281882998923889a2fcce9b49696506c499e22cf38fTed Kremenek switch (S->getStmtClass()) { 282882998923889a2fcce9b49696506c499e22cf38fTed Kremenek default: 283882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 284882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case Stmt::StmtExprClass: { 285882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // For statement expressions, look through the compound statement. 286882998923889a2fcce9b49696506c499e22cf38fTed Kremenek S = cast<StmtExpr>(S)->getSubStmt(); 287882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 288882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 289882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case Stmt::CXXMemberCallExprClass: { 290882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Include the implicit "this" pointer as being live. 291882998923889a2fcce9b49696506c499e22cf38fTed Kremenek CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S); 292c80850353f4051f36be9f5be9738cf877406311aTed Kremenek if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { 293ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj); 294c80850353f4051f36be9f5be9738cf877406311aTed Kremenek } 295882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 296882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 297c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks case Stmt::ObjCMessageExprClass: { 298c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks // In calls to super, include the implicit "self" pointer as being live. 299c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S); 300c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance) 301c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks val.liveDecls = LV.DSetFact.add(val.liveDecls, 302c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks LV.analysisContext.getSelfDecl()); 303c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks break; 304c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks } 305f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek case Stmt::DeclStmtClass: { 306f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek const DeclStmt *DS = cast<DeclStmt>(S); 307f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) { 308f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek for (const VariableArrayType* VA = FindVA(VD->getType()); 309f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek VA != 0; VA = FindVA(VA->getElementType())) { 310ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr()); 311f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 312f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 313f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek break; 314f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 3154b9c2d235fb9449e249d74f48ecfec601650de93John McCall case Stmt::PseudoObjectExprClass: { 3164b9c2d235fb9449e249d74f48ecfec601650de93John McCall // A pseudo-object operation only directly consumes its result 3174b9c2d235fb9449e249d74f48ecfec601650de93John McCall // expression. 3184b9c2d235fb9449e249d74f48ecfec601650de93John McCall Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr(); 3194b9c2d235fb9449e249d74f48ecfec601650de93John McCall if (!child) return; 3204b9c2d235fb9449e249d74f48ecfec601650de93John McCall if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child)) 3214b9c2d235fb9449e249d74f48ecfec601650de93John McCall child = OV->getSourceExpr(); 3224b9c2d235fb9449e249d74f48ecfec601650de93John McCall child = child->IgnoreParens(); 3234b9c2d235fb9449e249d74f48ecfec601650de93John McCall val.liveStmts = LV.SSetFact.add(val.liveStmts, child); 3244b9c2d235fb9449e249d74f48ecfec601650de93John McCall return; 3254b9c2d235fb9449e249d74f48ecfec601650de93John McCall } 3264b9c2d235fb9449e249d74f48ecfec601650de93John McCall 327882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // FIXME: These cases eventually shouldn't be needed. 328882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case Stmt::ExprWithCleanupsClass: { 329882998923889a2fcce9b49696506c499e22cf38fTed Kremenek S = cast<ExprWithCleanups>(S)->getSubExpr(); 330882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 331882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 332882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case Stmt::CXXBindTemporaryExprClass: { 333882998923889a2fcce9b49696506c499e22cf38fTed Kremenek S = cast<CXXBindTemporaryExpr>(S)->getSubExpr(); 334882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 335882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 336f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek case Stmt::UnaryExprOrTypeTraitExprClass: { 337f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek // No need to unconditionally visit subexpressions. 338f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek return; 339f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 3401b54221f6865b0daae1b8eb8f84bf5d291e8b864Zhongxing Xu } 341bfbcefb7e99905218b3f0a895b7bc1992203123bTed Kremenek 342882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end(); 343882998923889a2fcce9b49696506c499e22cf38fTed Kremenek it != ei; ++it) { 344ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek if (Stmt *child = *it) 345ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek AddLiveStmt(val.liveStmts, LV.SSetFact, child); 346882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 347bfbcefb7e99905218b3f0a895b7bc1992203123bTed Kremenek} 3481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 349882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { 350882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (B->isAssignmentOp()) { 351882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!LV.killAtAssign) 352882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 353882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 354882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Assigning to a variable? 355882998923889a2fcce9b49696506c499e22cf38fTed Kremenek Expr *LHS = B->getLHS()->IgnoreParens(); 356882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 3579c378f705405d37f49795d5e915989de774fe11fTed Kremenek if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) 358882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 359882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Assignments to references don't kill the ref's address 360882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (VD->getType()->isReferenceType()) 361882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 362882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 363882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!isAlwaysAlive(VD)) { 364882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // The variable is now dead. 365882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 366882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 367882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 368882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (observer) 369882998923889a2fcce9b49696506c499e22cf38fTed Kremenek observer->observerKill(DR); 370882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 371882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 37237622081d8a139a3249613acaa80106ec97261fbTed Kremenek} 37337622081d8a139a3249613acaa80106ec97261fbTed Kremenek 374882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitBlockExpr(BlockExpr *BE) { 37515ce164836472bfba88b30e53aa3f6ac0fb8a95dTed Kremenek AnalysisDeclContext::referenced_decls_iterator I, E; 37615ce164836472bfba88b30e53aa3f6ac0fb8a95dTed Kremenek llvm::tie(I, E) = 37715ce164836472bfba88b30e53aa3f6ac0fb8a95dTed Kremenek LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl()); 37815ce164836472bfba88b30e53aa3f6ac0fb8a95dTed Kremenek for ( ; I != E ; ++I) { 37915ce164836472bfba88b30e53aa3f6ac0fb8a95dTed Kremenek const VarDecl *VD = *I; 380882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (isAlwaysAlive(VD)) 381882998923889a2fcce9b49696506c499e22cf38fTed Kremenek continue; 382882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); 383b1a7b65231e86f7da6aacbf00bcdc16c56350e65Ted Kremenek } 384e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek} 3851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 386882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { 387882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) 388882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) 389882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.add(val.liveDecls, D); 390e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek} 391e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 392882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 393882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); 394882998923889a2fcce9b49696506c499e22cf38fTed Kremenek DI != DE; ++DI) 3959c378f705405d37f49795d5e915989de774fe11fTed Kremenek if (VarDecl *VD = dyn_cast<VarDecl>(*DI)) { 396882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!isAlwaysAlive(VD)) 397882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 398882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 399882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 4001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 401882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { 402882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Kill the iteration variable. 403882998923889a2fcce9b49696506c499e22cf38fTed Kremenek DeclRefExpr *DR = 0; 404882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const VarDecl *VD = 0; 4051eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 406882998923889a2fcce9b49696506c499e22cf38fTed Kremenek Stmt *element = OS->getElement(); 407882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) { 4087e24e82a70a2c681f4291a3397bcd1e1005f251aChris Lattner VD = cast<VarDecl>(DS->getSingleDecl()); 4098f5aab696173cc6e9c9963635d91dc2e83d54442Ted Kremenek } 410882998923889a2fcce9b49696506c499e22cf38fTed Kremenek else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) { 411882998923889a2fcce9b49696506c499e22cf38fTed Kremenek VD = cast<VarDecl>(DR->getDecl()); 412882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 413882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 4148f646002d8493ad7647d28b0acc7be425360f990Ted Kremenek if (VD) { 415882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 416882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (observer && DR) 417882998923889a2fcce9b49696506c499e22cf38fTed Kremenek observer->observerKill(DR); 4188f646002d8493ad7647d28b0acc7be425360f990Ted Kremenek } 4198f5aab696173cc6e9c9963635d91dc2e83d54442Ted Kremenek} 4208f5aab696173cc6e9c9963635d91dc2e83d54442Ted Kremenek 421882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions:: 422882998923889a2fcce9b49696506c499e22cf38fTed KremenekVisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) 423882998923889a2fcce9b49696506c499e22cf38fTed Kremenek{ 424882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // While sizeof(var) doesn't technically extend the liveness of 'var', it 425882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // does extent the liveness of metadata if 'var' is a VariableArrayType. 426882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // We handle that special case here. 427882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) 428882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 429882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 430f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek const Expr *subEx = UE->getArgumentExpr(); 431f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek if (subEx->getType()->isVariableArrayType()) { 432f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek assert(subEx->isLValue()); 433f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens()); 434f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 435882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 4361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 437882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { 438882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Treat ++/-- as a kill. 439882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Note we don't actually have to do anything if we don't have an observer, 440882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // since a ++/-- acts as both a kill and a "use". 441882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!observer) 442882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 443882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 444882998923889a2fcce9b49696506c499e22cf38fTed Kremenek switch (UO->getOpcode()) { 445882998923889a2fcce9b49696506c499e22cf38fTed Kremenek default: 446882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 4472de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PostInc: 448882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case UO_PostDec: 4492de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PreInc: 4502de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PreDec: 451882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 452e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek } 453882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 454882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) 455882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (isa<VarDecl>(DR->getDecl())) { 456882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Treat ++/-- as a kill. 457882998923889a2fcce9b49696506c499e22cf38fTed Kremenek observer->observerKill(DR); 458dcc48100ef7c224cecf5b9ccdd5c0d39e476468aTed Kremenek } 459f63aa45ca9d4f4782aa236415c63e00f7ffaf185Ted Kremenek} 4601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 461882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables::LivenessValues 462882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariablesImpl::runOnBlock(const CFGBlock *block, 463882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues val, 464882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::Observer *obs) { 465e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 466882998923889a2fcce9b49696506c499e22cf38fTed Kremenek TransferFunctions TF(*this, val, obs, block); 467882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 468882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Visit the terminator (if any). 469882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (const Stmt *term = block->getTerminator()) 470882998923889a2fcce9b49696506c499e22cf38fTed Kremenek TF.Visit(const_cast<Stmt*>(term)); 471882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 472882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Apply the transfer function for all Stmts in the block. 473882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFGBlock::const_reverse_iterator it = block->rbegin(), 474882998923889a2fcce9b49696506c499e22cf38fTed Kremenek ei = block->rend(); it != ei; ++it) { 475882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFGElement &elem = *it; 476d7f1d134a03ace51f8d142fbb7f436330704ede5Jordan Rose 477b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (Optional<CFGAutomaticObjDtor> Dtor = 478b07805485c603be3d8011f72611465324c9e664bDavid Blaikie elem.getAs<CFGAutomaticObjDtor>()) { 479b07805485c603be3d8011f72611465324c9e664bDavid Blaikie val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl()); 480d7f1d134a03ace51f8d142fbb7f436330704ede5Jordan Rose continue; 481d7f1d134a03ace51f8d142fbb7f436330704ede5Jordan Rose } 482d7f1d134a03ace51f8d142fbb7f436330704ede5Jordan Rose 483fdf6a279c9a75c778eba382d9a156697092982a1David Blaikie if (!elem.getAs<CFGStmt>()) 484882998923889a2fcce9b49696506c499e22cf38fTed Kremenek continue; 485882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 486fdf6a279c9a75c778eba382d9a156697092982a1David Blaikie const Stmt *S = elem.castAs<CFGStmt>().getStmt(); 487882998923889a2fcce9b49696506c499e22cf38fTed Kremenek TF.Visit(const_cast<Stmt*>(S)); 488882998923889a2fcce9b49696506c499e22cf38fTed Kremenek stmtsToLiveness[S] = val; 489882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 490882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return val; 491fdd225ed6f362a8550e597eb875d9c402b8a309cTed Kremenek} 49227b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek 493882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { 494882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFG *cfg = getImpl(impl).analysisContext.getCFG(); 495882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) 496882998923889a2fcce9b49696506c499e22cf38fTed Kremenek getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); 49727b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek} 49827b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek 499882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables::LiveVariables(void *im) : impl(im) {} 50027b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek 501882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables::~LiveVariables() { 502882998923889a2fcce9b49696506c499e22cf38fTed Kremenek delete (LiveVariablesImpl*) impl; 50327b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek} 50427b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek 505882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables * 5061d26f48dc2eea1c07431ca1519d7034a21b9bcffTed KremenekLiveVariables::computeLiveness(AnalysisDeclContext &AC, 507882998923889a2fcce9b49696506c499e22cf38fTed Kremenek bool killAtAssign) { 508882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 509882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // No CFG? Bail out. 510882998923889a2fcce9b49696506c499e22cf38fTed Kremenek CFG *cfg = AC.getCFG(); 511882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!cfg) 512882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return 0; 513882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 514d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek // The analysis currently has scalability issues for very large CFGs. 515d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek // Bail out if it looks too large. 516d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek if (cfg->getNumBlockIDs() > 300000) 517d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek return 0; 518d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek 519882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); 520882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 521882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Construct the dataflow worklist. Enqueue the exit block as the 522882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // start of the analysis. 523edb186399e19d84c93f25440435ab9a695138e79Ted Kremenek DataflowWorklist worklist(*cfg, AC); 524882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); 525882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 526882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // FIXME: we should enqueue using post order. 527882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { 528882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFGBlock *block = *it; 529882998923889a2fcce9b49696506c499e22cf38fTed Kremenek worklist.enqueueBlock(block); 530882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 531882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // FIXME: Scan for DeclRefExprs using in the LHS of an assignment. 532882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // We need to do this because we lack context in the reverse analysis 533882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // to determine if a DeclRefExpr appears in such a context, and thus 534882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // doesn't constitute a "use". 535882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (killAtAssign) 536882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFGBlock::const_iterator bi = block->begin(), be = block->end(); 537882998923889a2fcce9b49696506c499e22cf38fTed Kremenek bi != be; ++bi) { 538b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) { 539b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (const BinaryOperator *BO = 540b07805485c603be3d8011f72611465324c9e664bDavid Blaikie dyn_cast<BinaryOperator>(cs->getStmt())) { 541882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (BO->getOpcode() == BO_Assign) { 542882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (const DeclRefExpr *DR = 543882998923889a2fcce9b49696506c499e22cf38fTed Kremenek dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) { 544882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LV->inAssignment[DR] = 1; 545882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 546882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 547882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 548882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 549882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 550882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 551882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 55287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek worklist.sortWorklist(); 55387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 55487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek while (const CFGBlock *block = worklist.dequeue()) { 555882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Determine if the block's end value has changed. If not, we 556882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // have nothing left to do for this block. 557882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LivenessValues &prevVal = LV->blocksEndToLiveness[block]; 558882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 559882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Merge the values of all successor blocks. 560882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LivenessValues val; 561882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFGBlock::const_succ_iterator it = block->succ_begin(), 562882998923889a2fcce9b49696506c499e22cf38fTed Kremenek ei = block->succ_end(); it != ei; ++it) { 56387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (const CFGBlock *succ = *it) { 564882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val = LV->merge(val, LV->blocksBeginToLiveness[succ]); 56587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek } 566882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 567882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 568882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!everAnalyzedBlock[block->getBlockID()]) 569882998923889a2fcce9b49696506c499e22cf38fTed Kremenek everAnalyzedBlock[block->getBlockID()] = true; 570882998923889a2fcce9b49696506c499e22cf38fTed Kremenek else if (prevVal.equals(val)) 571882998923889a2fcce9b49696506c499e22cf38fTed Kremenek continue; 572882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 573882998923889a2fcce9b49696506c499e22cf38fTed Kremenek prevVal = val; 574882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 575882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Update the dataflow value for the start of this block. 576882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); 577882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 578882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Enqueue the value to the predecessors. 57987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek worklist.enqueuePredecessors(block); 580882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 581882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 582882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return new LiveVariables(LV); 583055c275fabcbe1ef246942c8b5f7d49b3a173500Ted Kremenek} 584055c275fabcbe1ef246942c8b5f7d49b3a173500Ted Kremenek 58539997fc2b8d300a85ead0a7d687964c6e63a8110Benjamin Kramerstatic bool compare_entries(const CFGBlock *A, const CFGBlock *B) { 586882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return A->getBlockID() < B->getBlockID(); 587882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 58839997fc2b8d300a85ead0a7d687964c6e63a8110Benjamin Kramer 58939997fc2b8d300a85ead0a7d687964c6e63a8110Benjamin Kramerstatic bool compare_vd_entries(const Decl *A, const Decl *B) { 590882998923889a2fcce9b49696506c499e22cf38fTed Kremenek SourceLocation ALoc = A->getLocStart(); 591882998923889a2fcce9b49696506c499e22cf38fTed Kremenek SourceLocation BLoc = B->getLocStart(); 592882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return ALoc.getRawEncoding() < BLoc.getRawEncoding(); 59386946745225096243f6969dc745267b78fc211a6Ted Kremenek} 59486946745225096243f6969dc745267b78fc211a6Ted Kremenek 595882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid LiveVariables::dumpBlockLiveness(const SourceManager &M) { 596882998923889a2fcce9b49696506c499e22cf38fTed Kremenek getImpl(impl).dumpBlockLiveness(M); 5972a9da9c85fbe559299a3d123180ed07a53b533c6Ted Kremenek} 5982a9da9c85fbe559299a3d123180ed07a53b533c6Ted Kremenek 599882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { 600882998923889a2fcce9b49696506c499e22cf38fTed Kremenek std::vector<const CFGBlock *> vec; 601882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator 602882998923889a2fcce9b49696506c499e22cf38fTed Kremenek it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); 603882998923889a2fcce9b49696506c499e22cf38fTed Kremenek it != ei; ++it) { 604882998923889a2fcce9b49696506c499e22cf38fTed Kremenek vec.push_back(it->first); 605882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 606882998923889a2fcce9b49696506c499e22cf38fTed Kremenek std::sort(vec.begin(), vec.end(), compare_entries); 607e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 608882998923889a2fcce9b49696506c499e22cf38fTed Kremenek std::vector<const VarDecl*> declVec; 6091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 610882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (std::vector<const CFGBlock *>::iterator 611882998923889a2fcce9b49696506c499e22cf38fTed Kremenek it = vec.begin(), ei = vec.end(); it != ei; ++it) { 612882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::errs() << "\n[ B" << (*it)->getBlockID() 613882998923889a2fcce9b49696506c499e22cf38fTed Kremenek << " (live variables at block exit) ]\n"; 614882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 615882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; 616882998923889a2fcce9b49696506c499e22cf38fTed Kremenek declVec.clear(); 617882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 618882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (llvm::ImmutableSet<const VarDecl *>::iterator si = 619882998923889a2fcce9b49696506c499e22cf38fTed Kremenek vals.liveDecls.begin(), 620882998923889a2fcce9b49696506c499e22cf38fTed Kremenek se = vals.liveDecls.end(); si != se; ++si) { 621882998923889a2fcce9b49696506c499e22cf38fTed Kremenek declVec.push_back(*si); 622882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 623882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 624882998923889a2fcce9b49696506c499e22cf38fTed Kremenek std::sort(declVec.begin(), declVec.end(), compare_vd_entries); 625882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 626882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (std::vector<const VarDecl*>::iterator di = declVec.begin(), 627882998923889a2fcce9b49696506c499e22cf38fTed Kremenek de = declVec.end(); di != de; ++di) { 628882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::errs() << " " << (*di)->getDeclName().getAsString() 629882998923889a2fcce9b49696506c499e22cf38fTed Kremenek << " <"; 630882998923889a2fcce9b49696506c499e22cf38fTed Kremenek (*di)->getLocation().dump(M); 631c0d567279f861844c9e7da492729425a90c03397Daniel Dunbar llvm::errs() << ">\n"; 632e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek } 63327b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek } 634882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::errs() << "\n"; 635c0576ca6c6ba136e583985041bd324b0acc38f40Ted Kremenek} 636882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 637a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenekconst void *LiveVariables::getTag() { static int x; return &x; } 638a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenekconst void *RelaxedLiveVariables::getTag() { static int x; return &x; } 639