diff options
20 files changed, 2065 insertions, 1867 deletions
diff --git a/include/clang/Analysis/Analyses/LiveVariables.h b/include/clang/Analysis/Analyses/LiveVariables.h index fbbd2613e7..6a1bae03be 100644 --- a/include/clang/Analysis/Analyses/LiveVariables.h +++ b/include/clang/Analysis/Analyses/LiveVariables.h @@ -1,4 +1,4 @@ -//===- LiveVariables.h - Live Variable Analysis for Source CFGs -*- C++ --*-===// +//===- LiveVariables.h - Live Variable Analysis for Source CFGs -*- C++ --*-// // // The LLVM Compiler Infrastructure // @@ -15,109 +15,89 @@ #define LLVM_CLANG_LIVEVARIABLES_H #include "clang/AST/Decl.h" -#include "clang/Analysis/Support/BlkExprDeclBitVector.h" -#include "clang/Analysis/FlowSensitive/DataflowValues.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/ImmutableSet.h" namespace clang { +class CFG; +class CFGBlock; class Stmt; class DeclRefExpr; class SourceManager; class AnalysisContext; - -struct LiveVariables_ValueTypes { - - struct ObserverTy; - - // We keep dataflow state for declarations and block-level expressions; - typedef StmtDeclBitVector_Types::ValTy ValTy; - - // We need to keep track of both declarations and CFGBlock-level expressions, - // (so that we don't explore such expressions twice). We also want - // to compute liveness information for block-level expressions, since these - // act as "temporary" values. - - struct AnalysisDataTy : public StmtDeclBitVector_Types::AnalysisDataTy { - ObserverTy* Observer; - ValTy AlwaysLive; - AnalysisContext *AC; - bool killAtAssign; - - AnalysisDataTy() : Observer(NULL), AC(NULL), killAtAssign(true) {} + +class LiveVariables { +public: + class LivenessValues { + public: + + llvm::ImmutableSet<const Stmt *> liveStmts; + llvm::ImmutableSet<const VarDecl *> liveDecls; + + bool equals(const LivenessValues &V) const; + + LivenessValues() + : liveStmts(0), liveDecls(0) {} + + LivenessValues(llvm::ImmutableSet<const Stmt *> LiveStmts, + llvm::ImmutableSet<const VarDecl *> LiveDecls) + : liveStmts(LiveStmts), liveDecls(LiveDecls) {} + + ~LivenessValues() {} + + bool isLive(const Stmt *S) const; + bool isLive(const VarDecl *D) const; + + friend class LiveVariables; }; - - //===-----------------------------------------------------===// - // ObserverTy - Observer for uninitialized values queries. - //===-----------------------------------------------------===// - - struct ObserverTy { - virtual ~ObserverTy() {} - - /// ObserveStmt - A callback invoked right before invoking the + + struct Observer { + virtual ~Observer() {} + + /// A callback invoked right before invoking the /// liveness transfer function on the given statement. - virtual void ObserveStmt(Stmt* S, const CFGBlock *currentBlock, - const AnalysisDataTy& AD, - const ValTy& V) {} - - virtual void ObserverKill(DeclRefExpr* DR) {} - }; -}; - -class LiveVariables : public DataflowValues<LiveVariables_ValueTypes, - dataflow::backward_analysis_tag> { - - -public: - typedef LiveVariables_ValueTypes::ObserverTy ObserverTy; - - LiveVariables(AnalysisContext &AC, bool killAtAssign = true); - - /// IsLive - Return true if a variable is live at the end of a + virtual void observeStmt(const Stmt* S, + const CFGBlock *currentBlock, + const LivenessValues& V) {} + + /// Called when the live variables analysis registers + /// that a variable is killed. + virtual void observerKill(const DeclRefExpr* DR) {} + }; + + + ~LiveVariables(); + + /// Compute the liveness information for a given CFG. + static LiveVariables *computeLiveness(AnalysisContext &analysisContext, + bool killAtAssign = true); + + /// Return true if a variable is live at the end of a /// specified block. - bool isLive(const CFGBlock* B, const VarDecl* D) const; - - /// IsLive - Returns true if a variable is live at the beginning of the + bool isLive(const CFGBlock* B, const VarDecl* D); + + /// Returns true if a variable is live at the beginning of the /// the statement. This query only works if liveness information /// has been recorded at the statement level (see runOnAllBlocks), and /// only returns liveness information for block-level expressions. - bool isLive(const Stmt* S, const VarDecl* D) const; - - /// IsLive - Returns true the block-level expression "value" is live + bool isLive(const Stmt* S, const VarDecl* D); + + /// Returns true the block-level expression "value" is live /// before the given block-level expression (see runOnAllBlocks). - bool isLive(const Stmt* Loc, const Stmt* StmtVal) const; + bool isLive(const Stmt* Loc, const Stmt* StmtVal); + + /// Print to stderr the liveness information associated with + /// each basic block. + void dumpBlockLiveness(const SourceManager& M); - /// IsLive - Return true if a variable is live according to the - /// provided livness bitvector. - bool isLive(const ValTy& V, const VarDecl* D) const; + void runOnAllBlocks(Observer &obs); - /// dumpLiveness - Print to stderr the liveness information encoded - /// by a specified bitvector. - void dumpLiveness(const ValTy& V, const SourceManager& M) const; - - /// dumpBlockLiveness - Print to stderr the liveness information - /// associated with each basic block. - void dumpBlockLiveness(const SourceManager& M) const; - - /// getNumDecls - Return the number of variables (declarations) that - /// whose liveness status is being tracked by the dataflow - /// analysis. - unsigned getNumDecls() const { return getAnalysisData().getNumDecls(); } - - /// IntializeValues - This routine can perform extra initialization, but - /// for LiveVariables this does nothing since all that logic is in - /// the constructor. - void InitializeValues(const CFG& cfg) {} - - void runOnCFG(CFG& cfg); - - /// runOnAllBlocks - Propagate the dataflow values once for each block, - /// starting from the current dataflow values. 'recordStmtValues' indicates - /// whether the method should store dataflow values per each individual - /// block-level expression. - void runOnAllBlocks(const CFG& cfg, ObserverTy* Obs, - bool recordStmtValues=false); +private: + LiveVariables(void *impl); + void *impl; }; - + } // end namespace clang #endif diff --git a/include/clang/Analysis/CFG.h b/include/clang/Analysis/CFG.h index 87f32a5166..2f6c4b3640 100644 --- a/include/clang/Analysis/CFG.h +++ b/include/clang/Analysis/CFG.h @@ -545,8 +545,13 @@ public: return alwaysAddMask[stmt->getStmtClass()]; } - BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass) { - alwaysAddMask[stmtClass] = true; + BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) { + alwaysAddMask[stmtClass] = val; + return *this; + } + + BuildOptions &setAllAlwaysAdd() { + alwaysAddMask.set(); return *this; } diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h index 0cb4ad992b..66ecba7dcf 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h @@ -19,9 +19,11 @@ #include "clang/AST/Expr.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Basic/LLVM.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h" #include "llvm/Support/DataTypes.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/DenseMap.h" namespace llvm { class BumpPtrAllocator; @@ -40,10 +42,10 @@ namespace ento { class SymExpr : public llvm::FoldingSetNode { public: - enum Kind { BEGIN_SYMBOLS, - RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, + enum Kind { RegionValueKind, ConjuredKind, DerivedKind, ExtentKind, MetadataKind, - END_SYMBOLS, + BEGIN_SYMBOLS = RegionValueKind, + END_SYMBOLS = MetadataKind, SymIntKind, SymSymKind }; private: Kind K; @@ -84,7 +86,7 @@ public: // Implement isa<T> support. static inline bool classof(const SymExpr* SE) { Kind k = SE->getKind(); - return k > BEGIN_SYMBOLS && k < END_SYMBOLS; + return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS; } }; @@ -419,10 +421,13 @@ class SymbolReaper { const LocationContext *LCtx; const Stmt *Loc; SymbolManager& SymMgr; + StoreRef reapedStore; + llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache; public: - SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr) - : LCtx(ctx), Loc(s), SymMgr(symmgr) {} + SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr, + StoreManager &storeMgr) + : LCtx(ctx), Loc(s), SymMgr(symmgr), reapedStore(0, storeMgr) {} ~SymbolReaper() {} @@ -431,7 +436,7 @@ public: bool isLive(SymbolRef sym); bool isLive(const Stmt *ExprVal) const; - bool isLive(const VarRegion *VR) const; + bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const; // markLive - Unconditionally marks a symbol as live. This should never be // used by checkers, only by the state infrastructure such as the store and @@ -464,6 +469,10 @@ public: bool isDead(SymbolRef sym) const { return TheDead.count(sym); } + + /// Set to the value of the symbolic store after + /// StoreManager::removeDeadBindings has been called. + void setReapedStore(StoreRef st) { reapedStore = st; } }; class SymbolVisitor { diff --git a/lib/Analysis/AnalysisContext.cpp b/lib/Analysis/AnalysisContext.cpp index 7ee247da00..5a85899389 100644 --- a/lib/Analysis/AnalysisContext.cpp +++ b/lib/Analysis/AnalysisContext.cpp @@ -177,25 +177,14 @@ PseudoConstantAnalysis *AnalysisContext::getPseudoConstantAnalysis() { } LiveVariables *AnalysisContext::getLiveVariables() { - if (!liveness) { - if (CFG *c = getCFG()) { - liveness.reset(new LiveVariables(*this)); - liveness->runOnCFG(*c); - liveness->runOnAllBlocks(*c, 0, true); - } - } - + if (!liveness) + liveness.reset(LiveVariables::computeLiveness(*this)); return liveness.get(); } LiveVariables *AnalysisContext::getRelaxedLiveVariables() { if (!relaxedLiveness) - if (CFG *c = getCFG()) { - relaxedLiveness.reset(new LiveVariables(*this, false)); - relaxedLiveness->runOnCFG(*c); - relaxedLiveness->runOnAllBlocks(*c, 0, true); - } - + relaxedLiveness.reset(LiveVariables::computeLiveness(*this, false)); return relaxedLiveness.get(); } diff --git a/lib/Analysis/LiveVariables.cpp b/lib/Analysis/LiveVariables.cpp index b7ae141781..f81019e2c9 100644 --- a/lib/Analysis/LiveVariables.cpp +++ b/lib/Analysis/LiveVariables.cpp @@ -1,392 +1,486 @@ -//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements Live Variables analysis for source-level CFGs. -// -//===----------------------------------------------------------------------===// - #include "clang/Analysis/Analyses/LiveVariables.h" -#include "clang/Basic/SourceManager.h" -#include "clang/AST/ASTContext.h" -#include "clang/AST/Expr.h" +#include "clang/AST/Stmt.h" #include "clang/Analysis/CFG.h" -#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" -#include "clang/Analysis/FlowSensitive/DataflowSolver.h" -#include "clang/Analysis/Support/SaveAndRestore.h" #include "clang/Analysis/AnalysisContext.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/Support/raw_ostream.h" +#include "clang/AST/StmtVisitor.h" + +#include <deque> +#include <algorithm> +#include <vector> using namespace clang; -//===----------------------------------------------------------------------===// -// Useful constants. -//===----------------------------------------------------------------------===// +namespace { + class LiveVariablesImpl { + public: + AnalysisContext &analysisContext; + std::vector<LiveVariables::LivenessValues> cfgBlockValues; + llvm::ImmutableSet<const Stmt *>::Factory SSetFact; + llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; + llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness; + llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness; + llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness; + llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment; + const bool killAtAssign; + + LiveVariables::LivenessValues + merge(LiveVariables::LivenessValues valsA, + LiveVariables::LivenessValues valsB); + + LiveVariables::LivenessValues runOnBlock(const CFGBlock *block, + LiveVariables::LivenessValues val, + LiveVariables::Observer *obs = 0); + + void dumpBlockLiveness(const SourceManager& M); + + LiveVariablesImpl(AnalysisContext &ac, bool KillAtAssign) + : analysisContext(ac), killAtAssign(KillAtAssign) {} + }; +} -static const bool Alive = true; -static const bool Dead = false; +static LiveVariablesImpl &getImpl(void* x) { + return *((LiveVariablesImpl *) x); +} //===----------------------------------------------------------------------===// -// Dataflow initialization logic. +// Operations and queries on LivenessValues. //===----------------------------------------------------------------------===// -namespace { -class RegisterDecls - : public CFGRecStmtDeclVisitor<RegisterDecls> { - - LiveVariables::AnalysisDataTy& AD; - - typedef SmallVector<VarDecl*, 20> AlwaysLiveTy; - AlwaysLiveTy AlwaysLive; +bool LiveVariables::LivenessValues::isLive(const Stmt *S) const { + return liveStmts.contains(S); +} +bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { + return liveDecls.contains(D); +} -public: - RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} +namespace { + template <typename SET> + SET mergeSets(typename SET::Factory &F, SET A, SET B) { + for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { + A = F.add(A, *it); + } + return A; + } +} - ~RegisterDecls() { +LiveVariables::LivenessValues +LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, + LiveVariables::LivenessValues valsB) { + return LiveVariables::LivenessValues(mergeSets(SSetFact, valsA.liveStmts, valsB.liveStmts), + mergeSets(DSetFact, valsA.liveDecls, valsB.liveDecls)); +} - AD.AlwaysLive.resetValues(AD); +bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { + return liveStmts == V.liveStmts && liveDecls == V.liveDecls; +} - for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end(); - I != E; ++ I) - AD.AlwaysLive(*I, AD) = Alive; - } +//===----------------------------------------------------------------------===// +// Query methods. +//===----------------------------------------------------------------------===// - void VisitImplicitParamDecl(ImplicitParamDecl* IPD) { - // Register the VarDecl for tracking. - AD.Register(IPD); - } +static bool isAlwaysAlive(const VarDecl *D) { + return D->hasGlobalStorage(); +} - void VisitVarDecl(VarDecl* VD) { - // Register the VarDecl for tracking. - AD.Register(VD); +bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { + return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); +} - // Does the variable have global storage? If so, it is always live. - if (VD->hasGlobalStorage()) - AlwaysLive.push_back(VD); - } +bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { + return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); +} - CFG& getCFG() { return AD.getCFG(); } -}; -} // end anonymous namespace - -LiveVariables::LiveVariables(AnalysisContext &AC, bool killAtAssign) { - // Register all referenced VarDecls. - CFG &cfg = *AC.getCFG(); - getAnalysisData().setCFG(cfg); - getAnalysisData().setContext(AC.getASTContext()); - getAnalysisData().AC = &AC; - getAnalysisData().killAtAssign = killAtAssign; - - RegisterDecls R(getAnalysisData()); - cfg.VisitBlockStmts(R); - - // Register all parameters even if they didn't occur in the function body. - if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(AC.getDecl())) - for (FunctionDecl::param_const_iterator PI = FD->param_begin(), - PE = FD->param_end(); PI != PE; ++PI) - getAnalysisData().Register(*PI); +bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) { + return getImpl(impl).stmtsToLiveness[Loc].isLive(S); } //===----------------------------------------------------------------------===// -// Transfer functions. +// Dataflow computation. //===----------------------------------------------------------------------===// namespace { - -class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{ - LiveVariables::AnalysisDataTy& AD; - LiveVariables::ValTy LiveState; - const CFGBlock *currentBlock; +class Worklist { + llvm::BitVector isBlockEnqueued; + std::deque<const CFGBlock *> workListContents; public: - TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad), currentBlock(0) {} - - LiveVariables::ValTy& getVal() { return LiveState; } - CFG& getCFG() { return AD.getCFG(); } - - void VisitDeclRefExpr(DeclRefExpr* DR); - void VisitBinaryOperator(BinaryOperator* B); - void VisitBlockExpr(BlockExpr *B); - void VisitAssign(BinaryOperator* B); - void VisitDeclStmt(DeclStmt* DS); - void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S); - void VisitUnaryOperator(UnaryOperator* U); - void Visit(Stmt *S); - void VisitTerminator(CFGBlock* B); + Worklist(CFG &cfg) : isBlockEnqueued(cfg.getNumBlockIDs()) {} - /// VisitConditionVariableInit - Handle the initialization of condition - /// variables at branches. Valid statements include IfStmt, ForStmt, - /// WhileStmt, and SwitchStmt. - void VisitConditionVariableInit(Stmt *S); - - void SetTopValue(LiveVariables::ValTy& V) { - V = AD.AlwaysLive; + bool empty() const { return workListContents.empty(); } + + const CFGBlock *getNextItem() { + const CFGBlock *block = workListContents.front(); + workListContents.pop_front(); + isBlockEnqueued[block->getBlockID()] = false; + return block; } - void setCurrentBlock(const CFGBlock *block) { - currentBlock = block; + void enqueueBlock(const CFGBlock *block) { + if (!isBlockEnqueued[block->getBlockID()]) { + isBlockEnqueued[block->getBlockID()] = true; + workListContents.push_back(block); + } } }; + +class TransferFunctions : public StmtVisitor<TransferFunctions> { + LiveVariablesImpl &LV; + LiveVariables::LivenessValues &val; + LiveVariables::Observer *observer; + const CFGBlock *currentBlock; +public: + TransferFunctions(LiveVariablesImpl &im, + LiveVariables::LivenessValues &Val, + LiveVariables::Observer *Observer, + const CFGBlock *CurrentBlock) + : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} + + void VisitBinaryOperator(BinaryOperator *BO); + void VisitBlockExpr(BlockExpr *BE); + void VisitDeclRefExpr(DeclRefExpr *DR); + void VisitDeclStmt(DeclStmt *DS); + void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); + void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); + void VisitUnaryOperator(UnaryOperator *UO); + void Visit(Stmt *S); +}; +} -void TransferFuncs::Visit(Stmt *S) { - - if (S == getCurrentBlkStmt()) { - - if (AD.Observer) - AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState); - - if (getCFG().isBlkExpr(S)) - LiveState(S, AD) = Dead; - - StmtVisitor<TransferFuncs,void>::Visit(S); +void TransferFunctions::Visit(Stmt *S) { + if (observer) + observer->observeStmt(S, currentBlock, val); + + StmtVisitor<TransferFunctions>::Visit(S); + + if (isa<Expr>(S)) { + val.liveStmts = LV.SSetFact.remove(val.liveStmts, S); } - else if (!getCFG().isBlkExpr(S)) { - - if (AD.Observer) - AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState); - StmtVisitor<TransferFuncs,void>::Visit(S); - - } - else { - // For block-level expressions, mark that they are live. - LiveState(S, AD) = Alive; + // Mark all children expressions live. + + switch (S->getStmtClass()) { + default: + break; + case Stmt::StmtExprClass: { + // For statement expressions, look through the compound statement. + S = cast<StmtExpr>(S)->getSubStmt(); + break; + } + case Stmt::CXXMemberCallExprClass: { + // Include the implicit "this" pointer as being live. + CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S); + val.liveStmts = + LV.SSetFact.add(val.liveStmts, + CE->getImplicitObjectArgument()->IgnoreParens()); + break; + } + // FIXME: These cases eventually shouldn't be needed. + case Stmt::ExprWithCleanupsClass: { + S = cast<ExprWithCleanups>(S)->getSubExpr(); + break; + } + case Stmt::CXXBindTemporaryExprClass: { + S = cast<CXXBindTemporaryExpr>(S)->getSubExpr(); + break; + } + case Stmt::MaterializeTemporaryExprClass: { + S = cast<MaterializeTemporaryExpr>(S)->GetTemporaryExpr(); + break; + } } -} -void TransferFuncs::VisitConditionVariableInit(Stmt *S) { - assert(!getCFG().isBlkExpr(S)); - CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S); + for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end(); + it != ei; ++it) { + if (Stmt *child = *it) { + if (Expr *Ex = dyn_cast<Expr>(child)) + child = Ex->IgnoreParens(); + + val.liveStmts = LV.SSetFact.add(val.liveStmts, child); + } + } } -void TransferFuncs::VisitTerminator(CFGBlock* B) { - - const Stmt* E = B->getTerminatorCondition(); - - if (!E) - return; - - assert (getCFG().isBlkExpr(E)); - LiveState(E, AD) = Alive; +void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { + if (B->isAssignmentOp()) { + if (!LV.killAtAssign) + return; + + // Assigning to a variable? + Expr *LHS = B->getLHS()->IgnoreParens(); + + if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) + if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { + // Assignments to references don't kill the ref's address + if (VD->getType()->isReferenceType()) + return; + + if (!isAlwaysAlive(VD)) { + // The variable is now dead. + val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); + } + + if (observer) + observer->observerKill(DR); + } + } } -void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { - if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl())) - LiveState(V, AD) = Alive; -} - -void TransferFuncs::VisitBlockExpr(BlockExpr *BE) { +void TransferFunctions::VisitBlockExpr(BlockExpr *BE) { AnalysisContext::referenced_decls_iterator I, E; - llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl()); + llvm::tie(I, E) = + LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl()); for ( ; I != E ; ++I) { - DeclBitVector_Types::Idx i = AD.getIdx(*I); - if (i.isValid()) - LiveState.getBit(i) = Alive; + const VarDecl *VD = *I; + if (isAlwaysAlive(VD)) + continue; + val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); } } -void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { - if (B->isAssignmentOp()) VisitAssign(B); - else VisitStmt(B); +void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { + if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) + if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) + val.liveDecls = LV.DSetFact.add(val.liveDecls, D); } -void -TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { - - // This is a block-level expression. Its value is 'dead' before this point. - LiveState(S, AD) = Dead; - - // This represents a 'use' of the collection. - Visit(S->getCollection()); +void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { + for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); + DI != DE; ++DI) + if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) { + if (!isAlwaysAlive(VD)) + val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); + } +} - // This represents a 'kill' for the variable. - Stmt* Element = S->getElement(); - DeclRefExpr* DR = 0; - VarDecl* VD = 0; +void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { + // Kill the iteration variable. + DeclRefExpr *DR = 0; + const VarDecl *VD = 0; - if (DeclStmt* DS = dyn_cast<DeclStmt>(Element)) + Stmt *element = OS->getElement(); + if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) { VD = cast<VarDecl>(DS->getSingleDecl()); - else { - Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens(); - if ((DR = dyn_cast<DeclRefExpr>(ElemExpr))) - VD = cast<VarDecl>(DR->getDecl()); - else { - Visit(ElemExpr); - return; - } } - + else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) { + VD = cast<VarDecl>(DR->getDecl()); + } + if (VD) { - LiveState(VD, AD) = Dead; - if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); } + val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); + if (observer && DR) + observer->observerKill(DR); } } +void TransferFunctions:: +VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) +{ + // While sizeof(var) doesn't technically extend the liveness of 'var', it + // does extent the liveness of metadata if 'var' is a VariableArrayType. + // We handle that special case here. + if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) + return; + + const DeclRefExpr *DR = + dyn_cast<DeclRefExpr>(UE->getArgumentExpr()->IgnoreParens()); + + if (!DR) + return; + + const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()); -void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { - Expr *E = U->getSubExpr(); + if (VD && VD->getType()->isVariableArrayType()) + val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); +} - switch (U->getOpcode()) { +void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { + // Treat ++/-- as a kill. + // Note we don't actually have to do anything if we don't have an observer, + // since a ++/-- acts as both a kill and a "use". + if (!observer) + return; + + switch (UO->getOpcode()) { + default: + return; case UO_PostInc: - case UO_PostDec: + case UO_PostDec: case UO_PreInc: case UO_PreDec: - // Walk through the subexpressions, blasting through ParenExprs - // until we either find a DeclRefExpr or some non-DeclRefExpr - // expression. - if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens())) - if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) { - // Treat the --/++ operator as a kill. - if (AD.Observer) { AD.Observer->ObserverKill(DR); } - LiveState(VD, AD) = Alive; - return VisitDeclRefExpr(DR); - } - - // Fall-through. - - default: - return Visit(E); - } -} - -void TransferFuncs::VisitAssign(BinaryOperator* B) { - Expr* LHS = B->getLHS(); - - // Assigning to a variable? - if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) { - // Assignments to references don't kill the ref's address - if (DR->getDecl()->getType()->isReferenceType()) { - VisitDeclRefExpr(DR); - } else { - if (AD.killAtAssign) { - // Update liveness inforamtion. - unsigned bit = AD.getIdx(DR->getDecl()); - LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); - - if (AD.Observer) { AD.Observer->ObserverKill(DR); } - } - // Handle things like +=, etc., which also generate "uses" - // of a variable. Do this just by visiting the subexpression. - if (B->getOpcode() != BO_Assign) - VisitDeclRefExpr(DR); - } + break; } - else // Not assigning to a variable. Process LHS as usual. - Visit(LHS); - - Visit(B->getRHS()); -} - -void TransferFuncs::VisitDeclStmt(DeclStmt* DS) { - // Declarations effectively "kill" a variable since they cannot - // possibly be live before they are declared. - for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); - DI != DE; ++DI) - if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) { - // Update liveness information by killing the VarDecl. - unsigned bit = AD.getIdx(VD); - LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); - - // The initializer is evaluated after the variable comes into scope, but - // before the DeclStmt (which binds the value to the variable). - // Since this is a reverse dataflow analysis, we must evaluate the - // transfer function for this expression after the DeclStmt. If the - // initializer references the variable (which is bad) then we extend - // its liveness. - if (Expr* Init = VD->getInit()) - Visit(Init); - - if (const VariableArrayType* VT = - AD.getContext().getAsVariableArrayType(VD->getType())) { - StmtIterator I(const_cast<VariableArrayType*>(VT)); - StmtIterator E; - for (; I != E; ++I) Visit(*I); - } + + if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) + if (isa<VarDecl>(DR->getDecl())) { + // Treat ++/-- as a kill. + observer->observerKill(DR); } } -} // end anonymous namespace - -//===----------------------------------------------------------------------===// -// Merge operator: if something is live on any successor block, it is live -// in the current block (a set union). -//===----------------------------------------------------------------------===// +LiveVariables::LivenessValues +LiveV |