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 llvm::ImmutableSet<const Stmt *>::Factory SSetFact; 8687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; 8787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness; 8887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness; 8987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness; 9087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment; 9187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek const bool killAtAssign; 9287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 9387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek LiveVariables::LivenessValues 9487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek merge(LiveVariables::LivenessValues valsA, 9587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek LiveVariables::LivenessValues valsB); 966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines LiveVariables::LivenessValues 986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val, 996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines LiveVariables::Observer *obs = nullptr); 10087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 10187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek void dumpBlockLiveness(const SourceManager& M); 10287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 1031d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenek LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) 1043c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek : analysisContext(ac), 1053c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek SSetFact(false), // Do not canonicalize ImmutableSets by default. 1063c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek DSetFact(false), // This is a *major* performance win. 1073c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek killAtAssign(KillAtAssign) {} 10887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek}; 109882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1107deed0c65b315cac037539401c49586283158d9fTed Kremenek 1119c378f705405d37f49795d5e915989de774fe11fTed Kremenekstatic LiveVariablesImpl &getImpl(void *x) { 112882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return *((LiveVariablesImpl *) x); 113882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1147deed0c65b315cac037539401c49586283158d9fTed Kremenek 1157deed0c65b315cac037539401c49586283158d9fTed Kremenek//===----------------------------------------------------------------------===// 116882998923889a2fcce9b49696506c499e22cf38fTed Kremenek// Operations and queries on LivenessValues. 1171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump//===----------------------------------------------------------------------===// 118e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 119882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::LivenessValues::isLive(const Stmt *S) const { 120882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return liveStmts.contains(S); 121882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1227deed0c65b315cac037539401c49586283158d9fTed Kremenek 123882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { 124882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return liveDecls.contains(D); 125882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1261eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 127882998923889a2fcce9b49696506c499e22cf38fTed Kremeneknamespace { 128882998923889a2fcce9b49696506c499e22cf38fTed Kremenek template <typename SET> 12987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SET mergeSets(SET A, SET B) { 13087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (A.isEmpty()) 13187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek return B; 13287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 133882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { 13487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek A = A.add(*it); 135882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 136882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return A; 137882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 138882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1397deed0c65b315cac037539401c49586283158d9fTed Kremenek 14099ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikievoid LiveVariables::Observer::anchor() { } 14199ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 142882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables::LivenessValues 143882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, 144882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues valsB) { 14587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 14687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::ImmutableSetRef<const Stmt *> 14787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()), 14887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()); 14987aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 15087aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 15187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek llvm::ImmutableSetRef<const VarDecl *> 15287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), 15387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); 15487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 15587aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 15687aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek SSetRefA = mergeSets(SSetRefA, SSetRefB); 15787aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek DSetRefA = mergeSets(DSetRefA, DSetRefB); 15887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 1593c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek // asImmutableSet() canonicalizes the tree, allowing us to do an easy 1603c2b5f7d6102bd1878c4ce7fcdd8f67ec9c37064Ted Kremenek // comparison afterwards. 16187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), 16287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek DSetRefA.asImmutableSet()); 163882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1647deed0c65b315cac037539401c49586283158d9fTed Kremenek 165882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { 166882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return liveStmts == V.liveStmts && liveDecls == V.liveDecls; 167882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 169882998923889a2fcce9b49696506c499e22cf38fTed Kremenek//===----------------------------------------------------------------------===// 170882998923889a2fcce9b49696506c499e22cf38fTed Kremenek// Query methods. 171882998923889a2fcce9b49696506c499e22cf38fTed Kremenek//===----------------------------------------------------------------------===// 1727deed0c65b315cac037539401c49586283158d9fTed Kremenek 173882998923889a2fcce9b49696506c499e22cf38fTed Kremenekstatic bool isAlwaysAlive(const VarDecl *D) { 174882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return D->hasGlobalStorage(); 175882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1764111024be81e7c0525e42dadcc126d27e5bf2425Chris Lattner 177882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { 178882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); 179882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 181882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { 182882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); 183882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 1841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 185882998923889a2fcce9b49696506c499e22cf38fTed Kremenekbool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) { 186882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return getImpl(impl).stmtsToLiveness[Loc].isLive(S); 187e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek} 188e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 189e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek//===----------------------------------------------------------------------===// 190882998923889a2fcce9b49696506c499e22cf38fTed Kremenek// Dataflow computation. 1911eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump//===----------------------------------------------------------------------===// 192e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 193e4e633400b1993c1174b47b774fa015220fa695cTed Kremeneknamespace { 194882998923889a2fcce9b49696506c499e22cf38fTed Kremenekclass TransferFunctions : public StmtVisitor<TransferFunctions> { 195882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariablesImpl &LV; 196882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues &val; 197882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::Observer *observer; 198882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFGBlock *currentBlock; 199882998923889a2fcce9b49696506c499e22cf38fTed Kremenekpublic: 200882998923889a2fcce9b49696506c499e22cf38fTed Kremenek TransferFunctions(LiveVariablesImpl &im, 201882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues &Val, 202882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::Observer *Observer, 203882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFGBlock *CurrentBlock) 204882998923889a2fcce9b49696506c499e22cf38fTed Kremenek : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} 205882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 206882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitBinaryOperator(BinaryOperator *BO); 207882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitBlockExpr(BlockExpr *BE); 208882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitDeclRefExpr(DeclRefExpr *DR); 209882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitDeclStmt(DeclStmt *DS); 210882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); 211882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); 212882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void VisitUnaryOperator(UnaryOperator *UO); 213882998923889a2fcce9b49696506c499e22cf38fTed Kremenek void Visit(Stmt *S); 214882998923889a2fcce9b49696506c499e22cf38fTed Kremenek}; 215882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 2161eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 217f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenekstatic const VariableArrayType *FindVA(QualType Ty) { 218f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek const Type *ty = Ty.getTypePtr(); 219f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) { 220f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT)) 221f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek if (VAT->getSizeExpr()) 222f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek return VAT; 223f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek 224f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek ty = VT->getElementType().getTypePtr(); 225f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 2266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 228f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek} 229f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek 230ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenekstatic const Stmt *LookThroughStmt(const Stmt *S) { 2316bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek while (S) { 2326bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek if (const Expr *Ex = dyn_cast<Expr>(S)) 2336bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek S = Ex->IgnoreParens(); 234f3fb5c5395d382ffd24ec2675237fa9bdff6266eJohn McCall if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(S)) { 235f3fb5c5395d382ffd24ec2675237fa9bdff6266eJohn McCall S = EWC->getSubExpr(); 236f3fb5c5395d382ffd24ec2675237fa9bdff6266eJohn McCall continue; 237f3fb5c5395d382ffd24ec2675237fa9bdff6266eJohn McCall } 2386bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) { 2396bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek S = OVE->getSourceExpr(); 2406bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek continue; 2416bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek } 2426bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek break; 2436bbecd5e96c2bfe6dcb935a3ca0deb06782a5b14Ted Kremenek } 244ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek return S; 245ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek} 246ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek 247ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenekstatic void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set, 248ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek llvm::ImmutableSet<const Stmt *>::Factory &F, 249ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek const Stmt *S) { 250ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek Set = F.add(Set, LookThroughStmt(S)); 251ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek} 252ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek 253882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::Visit(Stmt *S) { 254882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (observer) 255882998923889a2fcce9b49696506c499e22cf38fTed Kremenek observer->observeStmt(S, currentBlock, val); 256882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 257882998923889a2fcce9b49696506c499e22cf38fTed Kremenek StmtVisitor<TransferFunctions>::Visit(S); 258882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 259882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (isa<Expr>(S)) { 260882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveStmts = LV.SSetFact.remove(val.liveStmts, S); 26186946745225096243f6969dc745267b78fc211a6Ted Kremenek } 2621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 263882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Mark all children expressions live. 264882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 265882998923889a2fcce9b49696506c499e22cf38fTed Kremenek switch (S->getStmtClass()) { 266882998923889a2fcce9b49696506c499e22cf38fTed Kremenek default: 267882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 268882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case Stmt::StmtExprClass: { 269882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // For statement expressions, look through the compound statement. 270882998923889a2fcce9b49696506c499e22cf38fTed Kremenek S = cast<StmtExpr>(S)->getSubStmt(); 271882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 272882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 273882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case Stmt::CXXMemberCallExprClass: { 274882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Include the implicit "this" pointer as being live. 275882998923889a2fcce9b49696506c499e22cf38fTed Kremenek CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S); 276c80850353f4051f36be9f5be9738cf877406311aTed Kremenek if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { 277ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj); 278c80850353f4051f36be9f5be9738cf877406311aTed Kremenek } 279882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 280882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 281c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks case Stmt::ObjCMessageExprClass: { 282c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks // In calls to super, include the implicit "self" pointer as being live. 283c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S); 284c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance) 285c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks val.liveDecls = LV.DSetFact.add(val.liveDecls, 286c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks LV.analysisContext.getSelfDecl()); 287c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks break; 288c739406d37b9b1dc95bc3a3d899024e5ce31e5d5Anna Zaks } 289f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek case Stmt::DeclStmtClass: { 290f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek const DeclStmt *DS = cast<DeclStmt>(S); 291f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) { 292f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek for (const VariableArrayType* VA = FindVA(VD->getType()); 2936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines VA != nullptr; VA = FindVA(VA->getElementType())) { 294ddaec0dba69f2318d96f949b2f273b2befd1a5c2Ted Kremenek AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr()); 295f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 296f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 297f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek break; 298f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 2994b9c2d235fb9449e249d74f48ecfec601650de93John McCall case Stmt::PseudoObjectExprClass: { 3004b9c2d235fb9449e249d74f48ecfec601650de93John McCall // A pseudo-object operation only directly consumes its result 3014b9c2d235fb9449e249d74f48ecfec601650de93John McCall // expression. 3024b9c2d235fb9449e249d74f48ecfec601650de93John McCall Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr(); 3034b9c2d235fb9449e249d74f48ecfec601650de93John McCall if (!child) return; 3044b9c2d235fb9449e249d74f48ecfec601650de93John McCall if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child)) 3054b9c2d235fb9449e249d74f48ecfec601650de93John McCall child = OV->getSourceExpr(); 3064b9c2d235fb9449e249d74f48ecfec601650de93John McCall child = child->IgnoreParens(); 3074b9c2d235fb9449e249d74f48ecfec601650de93John McCall val.liveStmts = LV.SSetFact.add(val.liveStmts, child); 3084b9c2d235fb9449e249d74f48ecfec601650de93John McCall return; 3094b9c2d235fb9449e249d74f48ecfec601650de93John McCall } 3104b9c2d235fb9449e249d74f48ecfec601650de93John McCall 311882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // FIXME: These cases eventually shouldn't be needed. 312882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case Stmt::ExprWithCleanupsClass: { 313882998923889a2fcce9b49696506c499e22cf38fTed Kremenek S = cast<ExprWithCleanups>(S)->getSubExpr(); 314882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 315882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 316882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case Stmt::CXXBindTemporaryExprClass: { 317882998923889a2fcce9b49696506c499e22cf38fTed Kremenek S = cast<CXXBindTemporaryExpr>(S)->getSubExpr(); 318882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 319882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 320f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek case Stmt::UnaryExprOrTypeTraitExprClass: { 321f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek // No need to unconditionally visit subexpressions. 322f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek return; 323f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 3241b54221f6865b0daae1b8eb8f84bf5d291e8b864Zhongxing Xu } 32587d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar 32687d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar for (Stmt *Child : S->children()) { 32787d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar if (Child) 32887d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar AddLiveStmt(val.liveStmts, LV.SSetFact, Child); 329882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 330bfbcefb7e99905218b3f0a895b7bc1992203123bTed Kremenek} 3311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 332882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { 333882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (B->isAssignmentOp()) { 334882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!LV.killAtAssign) 335882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 336882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 337882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Assigning to a variable? 338882998923889a2fcce9b49696506c499e22cf38fTed Kremenek Expr *LHS = B->getLHS()->IgnoreParens(); 339882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 3409c378f705405d37f49795d5e915989de774fe11fTed Kremenek if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) 341882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 342882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Assignments to references don't kill the ref's address 343882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (VD->getType()->isReferenceType()) 344882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 345882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 346882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!isAlwaysAlive(VD)) { 347882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // The variable is now dead. 348882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 349882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 350882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 351882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (observer) 352882998923889a2fcce9b49696506c499e22cf38fTed Kremenek observer->observerKill(DR); 353882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 354882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 35537622081d8a139a3249613acaa80106ec97261fbTed Kremenek} 35637622081d8a139a3249613acaa80106ec97261fbTed Kremenek 357882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitBlockExpr(BlockExpr *BE) { 3580e2c34f92f00628d48968dfea096d36381f494cbStephen Hines for (const VarDecl *VD : 3590e2c34f92f00628d48968dfea096d36381f494cbStephen Hines LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) { 360882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (isAlwaysAlive(VD)) 361882998923889a2fcce9b49696506c499e22cf38fTed Kremenek continue; 362882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); 363b1a7b65231e86f7da6aacbf00bcdc16c56350e65Ted Kremenek } 364e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek} 3651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 366882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { 367882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) 368882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) 369882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.add(val.liveDecls, D); 370e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek} 371e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 372882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 373651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines for (const auto *DI : DS->decls()) 374651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines if (const auto *VD = dyn_cast<VarDecl>(DI)) { 375882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!isAlwaysAlive(VD)) 376882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 377882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 378882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 3791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 380882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { 381882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Kill the iteration variable. 3826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines DeclRefExpr *DR = nullptr; 3836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const VarDecl *VD = nullptr; 3841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 385882998923889a2fcce9b49696506c499e22cf38fTed Kremenek Stmt *element = OS->getElement(); 386882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) { 3877e24e82a70a2c681f4291a3397bcd1e1005f251aChris Lattner VD = cast<VarDecl>(DS->getSingleDecl()); 3888f5aab696173cc6e9c9963635d91dc2e83d54442Ted Kremenek } 389882998923889a2fcce9b49696506c499e22cf38fTed Kremenek else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) { 390882998923889a2fcce9b49696506c499e22cf38fTed Kremenek VD = cast<VarDecl>(DR->getDecl()); 391882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 392882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 3938f646002d8493ad7647d28b0acc7be425360f990Ted Kremenek if (VD) { 394882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 395882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (observer && DR) 396882998923889a2fcce9b49696506c499e22cf38fTed Kremenek observer->observerKill(DR); 3978f646002d8493ad7647d28b0acc7be425360f990Ted Kremenek } 3988f5aab696173cc6e9c9963635d91dc2e83d54442Ted Kremenek} 3998f5aab696173cc6e9c9963635d91dc2e83d54442Ted Kremenek 400882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions:: 401882998923889a2fcce9b49696506c499e22cf38fTed KremenekVisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) 402882998923889a2fcce9b49696506c499e22cf38fTed Kremenek{ 403882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // While sizeof(var) doesn't technically extend the liveness of 'var', it 404882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // does extent the liveness of metadata if 'var' is a VariableArrayType. 405882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // We handle that special case here. 406882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) 407882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 408882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 409f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek const Expr *subEx = UE->getArgumentExpr(); 410f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek if (subEx->getType()->isVariableArrayType()) { 411f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek assert(subEx->isLValue()); 412f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens()); 413f91a5b008d1a63630ae483247204c2651e512fa1Ted Kremenek } 414882998923889a2fcce9b49696506c499e22cf38fTed Kremenek} 4151eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 416882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { 417882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Treat ++/-- as a kill. 418882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Note we don't actually have to do anything if we don't have an observer, 419882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // since a ++/-- acts as both a kill and a "use". 420882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!observer) 421882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 422882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 423882998923889a2fcce9b49696506c499e22cf38fTed Kremenek switch (UO->getOpcode()) { 424882998923889a2fcce9b49696506c499e22cf38fTed Kremenek default: 425882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return; 4262de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PostInc: 427882998923889a2fcce9b49696506c499e22cf38fTed Kremenek case UO_PostDec: 4282de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PreInc: 4292de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PreDec: 430882998923889a2fcce9b49696506c499e22cf38fTed Kremenek break; 431e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek } 432882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 433882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) 434882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (isa<VarDecl>(DR->getDecl())) { 435882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Treat ++/-- as a kill. 436882998923889a2fcce9b49696506c499e22cf38fTed Kremenek observer->observerKill(DR); 437dcc48100ef7c224cecf5b9ccdd5c0d39e476468aTed Kremenek } 438f63aa45ca9d4f4782aa236415c63e00f7ffaf185Ted Kremenek} 4391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 440882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables::LivenessValues 441882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariablesImpl::runOnBlock(const CFGBlock *block, 442882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues val, 443882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::Observer *obs) { 444e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 445882998923889a2fcce9b49696506c499e22cf38fTed Kremenek TransferFunctions TF(*this, val, obs, block); 446882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 447882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Visit the terminator (if any). 448882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (const Stmt *term = block->getTerminator()) 449882998923889a2fcce9b49696506c499e22cf38fTed Kremenek TF.Visit(const_cast<Stmt*>(term)); 450882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 451882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Apply the transfer function for all Stmts in the block. 452882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFGBlock::const_reverse_iterator it = block->rbegin(), 453882998923889a2fcce9b49696506c499e22cf38fTed Kremenek ei = block->rend(); it != ei; ++it) { 454882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFGElement &elem = *it; 455d7f1d134a03ace51f8d142fbb7f436330704ede5Jordan Rose 456b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (Optional<CFGAutomaticObjDtor> Dtor = 457b07805485c603be3d8011f72611465324c9e664bDavid Blaikie elem.getAs<CFGAutomaticObjDtor>()) { 458b07805485c603be3d8011f72611465324c9e664bDavid Blaikie val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl()); 459d7f1d134a03ace51f8d142fbb7f436330704ede5Jordan Rose continue; 460d7f1d134a03ace51f8d142fbb7f436330704ede5Jordan Rose } 461d7f1d134a03ace51f8d142fbb7f436330704ede5Jordan Rose 462fdf6a279c9a75c778eba382d9a156697092982a1David Blaikie if (!elem.getAs<CFGStmt>()) 463882998923889a2fcce9b49696506c499e22cf38fTed Kremenek continue; 464882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 465fdf6a279c9a75c778eba382d9a156697092982a1David Blaikie const Stmt *S = elem.castAs<CFGStmt>().getStmt(); 466882998923889a2fcce9b49696506c499e22cf38fTed Kremenek TF.Visit(const_cast<Stmt*>(S)); 467882998923889a2fcce9b49696506c499e22cf38fTed Kremenek stmtsToLiveness[S] = val; 468882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 469882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return val; 470fdd225ed6f362a8550e597eb875d9c402b8a309cTed Kremenek} 47127b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek 472882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { 473882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFG *cfg = getImpl(impl).analysisContext.getCFG(); 474882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) 475882998923889a2fcce9b49696506c499e22cf38fTed Kremenek getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); 47627b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek} 47727b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek 478882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables::LiveVariables(void *im) : impl(im) {} 47927b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek 480882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables::~LiveVariables() { 481882998923889a2fcce9b49696506c499e22cf38fTed Kremenek delete (LiveVariablesImpl*) impl; 48227b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek} 48327b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek 484882998923889a2fcce9b49696506c499e22cf38fTed KremenekLiveVariables * 4851d26f48dc2eea1c07431ca1519d7034a21b9bcffTed KremenekLiveVariables::computeLiveness(AnalysisDeclContext &AC, 486882998923889a2fcce9b49696506c499e22cf38fTed Kremenek bool killAtAssign) { 487882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 488882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // No CFG? Bail out. 489882998923889a2fcce9b49696506c499e22cf38fTed Kremenek CFG *cfg = AC.getCFG(); 490882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!cfg) 4916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 492882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 493d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek // The analysis currently has scalability issues for very large CFGs. 494d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek // Bail out if it looks too large. 495d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek if (cfg->getNumBlockIDs() > 300000) 4966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 497d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek 498882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); 499882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 500882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Construct the dataflow worklist. Enqueue the exit block as the 501882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // start of the analysis. 502edb186399e19d84c93f25440435ab9a695138e79Ted Kremenek DataflowWorklist worklist(*cfg, AC); 503882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); 504882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 505882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // FIXME: we should enqueue using post order. 506882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { 507882998923889a2fcce9b49696506c499e22cf38fTed Kremenek const CFGBlock *block = *it; 508882998923889a2fcce9b49696506c499e22cf38fTed Kremenek worklist.enqueueBlock(block); 509882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 510882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // FIXME: Scan for DeclRefExprs using in the LHS of an assignment. 511882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // We need to do this because we lack context in the reverse analysis 512882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // to determine if a DeclRefExpr appears in such a context, and thus 513882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // doesn't constitute a "use". 514882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (killAtAssign) 515882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFGBlock::const_iterator bi = block->begin(), be = block->end(); 516882998923889a2fcce9b49696506c499e22cf38fTed Kremenek bi != be; ++bi) { 517b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) { 518b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (const BinaryOperator *BO = 519b07805485c603be3d8011f72611465324c9e664bDavid Blaikie dyn_cast<BinaryOperator>(cs->getStmt())) { 520882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (BO->getOpcode() == BO_Assign) { 521882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (const DeclRefExpr *DR = 522882998923889a2fcce9b49696506c499e22cf38fTed Kremenek dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) { 523882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LV->inAssignment[DR] = 1; 524882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 525882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 526882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 527882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 528882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 529882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 530882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 53187aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek worklist.sortWorklist(); 53287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek 53387aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek while (const CFGBlock *block = worklist.dequeue()) { 534882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Determine if the block's end value has changed. If not, we 535882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // have nothing left to do for this block. 536882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LivenessValues &prevVal = LV->blocksEndToLiveness[block]; 537882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 538882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Merge the values of all successor blocks. 539882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LivenessValues val; 540882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (CFGBlock::const_succ_iterator it = block->succ_begin(), 541882998923889a2fcce9b49696506c499e22cf38fTed Kremenek ei = block->succ_end(); it != ei; ++it) { 54287aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek if (const CFGBlock *succ = *it) { 543882998923889a2fcce9b49696506c499e22cf38fTed Kremenek val = LV->merge(val, LV->blocksBeginToLiveness[succ]); 54487aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek } 545882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 546882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 547882998923889a2fcce9b49696506c499e22cf38fTed Kremenek if (!everAnalyzedBlock[block->getBlockID()]) 548882998923889a2fcce9b49696506c499e22cf38fTed Kremenek everAnalyzedBlock[block->getBlockID()] = true; 549882998923889a2fcce9b49696506c499e22cf38fTed Kremenek else if (prevVal.equals(val)) 550882998923889a2fcce9b49696506c499e22cf38fTed Kremenek continue; 551882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 552882998923889a2fcce9b49696506c499e22cf38fTed Kremenek prevVal = val; 553882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 554882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Update the dataflow value for the start of this block. 555882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); 556882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 557882998923889a2fcce9b49696506c499e22cf38fTed Kremenek // Enqueue the value to the predecessors. 55887aa1250a90af9d92ad9d6b7b65610a45bf478c1Ted Kremenek worklist.enqueuePredecessors(block); 559882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 560882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 561882998923889a2fcce9b49696506c499e22cf38fTed Kremenek return new LiveVariables(LV); 562055c275fabcbe1ef246942c8b5f7d49b3a173500Ted Kremenek} 563055c275fabcbe1ef246942c8b5f7d49b3a173500Ted Kremenek 564882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid LiveVariables::dumpBlockLiveness(const SourceManager &M) { 565882998923889a2fcce9b49696506c499e22cf38fTed Kremenek getImpl(impl).dumpBlockLiveness(M); 5662a9da9c85fbe559299a3d123180ed07a53b533c6Ted Kremenek} 5672a9da9c85fbe559299a3d123180ed07a53b533c6Ted Kremenek 568882998923889a2fcce9b49696506c499e22cf38fTed Kremenekvoid LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { 569882998923889a2fcce9b49696506c499e22cf38fTed Kremenek std::vector<const CFGBlock *> vec; 570882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator 571882998923889a2fcce9b49696506c499e22cf38fTed Kremenek it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); 572882998923889a2fcce9b49696506c499e22cf38fTed Kremenek it != ei; ++it) { 573882998923889a2fcce9b49696506c499e22cf38fTed Kremenek vec.push_back(it->first); 574882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 575651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines std::sort(vec.begin(), vec.end(), [](const CFGBlock *A, const CFGBlock *B) { 576651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return A->getBlockID() < B->getBlockID(); 577651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines }); 578e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek 579882998923889a2fcce9b49696506c499e22cf38fTed Kremenek std::vector<const VarDecl*> declVec; 5801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 581882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (std::vector<const CFGBlock *>::iterator 582882998923889a2fcce9b49696506c499e22cf38fTed Kremenek it = vec.begin(), ei = vec.end(); it != ei; ++it) { 583882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::errs() << "\n[ B" << (*it)->getBlockID() 584882998923889a2fcce9b49696506c499e22cf38fTed Kremenek << " (live variables at block exit) ]\n"; 585882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 586882998923889a2fcce9b49696506c499e22cf38fTed Kremenek LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; 587882998923889a2fcce9b49696506c499e22cf38fTed Kremenek declVec.clear(); 588882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 589882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (llvm::ImmutableSet<const VarDecl *>::iterator si = 590882998923889a2fcce9b49696506c499e22cf38fTed Kremenek vals.liveDecls.begin(), 591882998923889a2fcce9b49696506c499e22cf38fTed Kremenek se = vals.liveDecls.end(); si != se; ++si) { 592882998923889a2fcce9b49696506c499e22cf38fTed Kremenek declVec.push_back(*si); 593882998923889a2fcce9b49696506c499e22cf38fTed Kremenek } 594651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 595651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines std::sort(declVec.begin(), declVec.end(), [](const Decl *A, const Decl *B) { 596651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines return A->getLocStart() < B->getLocStart(); 597651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines }); 598651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines 599882998923889a2fcce9b49696506c499e22cf38fTed Kremenek for (std::vector<const VarDecl*>::iterator di = declVec.begin(), 600882998923889a2fcce9b49696506c499e22cf38fTed Kremenek de = declVec.end(); di != de; ++di) { 601882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::errs() << " " << (*di)->getDeclName().getAsString() 602882998923889a2fcce9b49696506c499e22cf38fTed Kremenek << " <"; 603882998923889a2fcce9b49696506c499e22cf38fTed Kremenek (*di)->getLocation().dump(M); 604c0d567279f861844c9e7da492729425a90c03397Daniel Dunbar llvm::errs() << ">\n"; 605e4e633400b1993c1174b47b774fa015220fa695cTed Kremenek } 60627b07c5fb9926c9d69fa1d8239e96ad0b7a178f7Ted Kremenek } 607882998923889a2fcce9b49696506c499e22cf38fTed Kremenek llvm::errs() << "\n"; 608c0576ca6c6ba136e583985041bd324b0acc38f40Ted Kremenek} 609882998923889a2fcce9b49696506c499e22cf38fTed Kremenek 610a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenekconst void *LiveVariables::getTag() { static int x; return &x; } 611a5937bbfd19e61d651a58b0f0ffeef68457902a5Ted Kremenekconst void *RelaxedLiveVariables::getTag() { static int x; return &x; } 612