diff options
| -rw-r--r-- | include/clang/Analysis/PathSensitive/BasicStore.h | 27 | ||||
| -rw-r--r-- | include/clang/Analysis/PathSensitive/ExplodedGraph.h | 27 | ||||
| -rw-r--r-- | include/clang/Analysis/PathSensitive/GRCoreEngine.h | 71 | ||||
| -rw-r--r-- | include/clang/Analysis/PathSensitive/GRExprEngine.h | 73 | ||||
| -rw-r--r-- | include/clang/Analysis/PathSensitive/GRTransferFuncs.h | 10 | ||||
| -rw-r--r-- | include/clang/Analysis/PathSensitive/Store.h | 34 | ||||
| -rw-r--r-- | include/clang/Analysis/PathSensitive/ValueState.h | 113 | ||||
| -rw-r--r-- | lib/Analysis/BasicObjCFoundationChecks.cpp | 6 | ||||
| -rw-r--r-- | lib/Analysis/BasicStore.cpp | 141 | ||||
| -rw-r--r-- | lib/Analysis/BugReporter.cpp | 6 | ||||
| -rw-r--r-- | lib/Analysis/CFRefCount.cpp | 62 | ||||
| -rw-r--r-- | lib/Analysis/GRCoreEngine.cpp | 18 | ||||
| -rw-r--r-- | lib/Analysis/GRExprEngine.cpp | 133 | ||||
| -rw-r--r-- | lib/Analysis/GRSimpleVals.cpp | 10 | ||||
| -rw-r--r-- | lib/Analysis/GRTransferFuncs.cpp | 2 | ||||
| -rw-r--r-- | lib/Analysis/ValueState.cpp | 151 |
16 files changed, 519 insertions, 365 deletions
diff --git a/include/clang/Analysis/PathSensitive/BasicStore.h b/include/clang/Analysis/PathSensitive/BasicStore.h new file mode 100644 index 0000000000..88ac9ce381 --- /dev/null +++ b/include/clang/Analysis/PathSensitive/BasicStore.h @@ -0,0 +1,27 @@ +//== BasicStore.h - Basic map from Locations to Values ----------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defined the BasicStore and BasicStoreManager classes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_BASICSTORE_H +#define LLVM_CLANG_ANALYSIS_BASICSTORE_H + +#include "clang/Analysis/PathSensitive/Store.h" + +namespace llvm { + class llvm::BumpPtrAllocator; +} + +namespace clang { + StoreManager* CreateBasicStoreManager(llvm::BumpPtrAllocator& Alloc); +} + +#endif diff --git a/include/clang/Analysis/PathSensitive/ExplodedGraph.h b/include/clang/Analysis/PathSensitive/ExplodedGraph.h index 39a064d4c6..71043f0ef6 100644 --- a/include/clang/Analysis/PathSensitive/ExplodedGraph.h +++ b/include/clang/Analysis/PathSensitive/ExplodedGraph.h @@ -95,10 +95,8 @@ protected: /// with this node. const ProgramPoint Location; - /// State - The state associated with this node. Normally this value - /// is immutable, but we anticipate there will be times when algorithms - /// that directly manipulate the analysis graph will need to change it. - void* State; + /// State - The state associated with this node. + const void* State; /// Preds - The predecessors of this node. NodeGroup Preds; @@ -107,7 +105,7 @@ protected: NodeGroup Succs; /// Construct a ExplodedNodeImpl with the provided location and state. - explicit ExplodedNodeImpl(const ProgramPoint& loc, void* state) + explicit ExplodedNodeImpl(const ProgramPoint& loc, const void* state) : Location(loc), State(state) {} /// addPredeccessor - Adds a predecessor to the current node, and @@ -146,19 +144,19 @@ class ExplodedNode : public ExplodedNodeImpl { public: /// Construct a ExplodedNodeImpl with the given node ID, program edge, /// and state. - explicit ExplodedNode(const ProgramPoint& loc, StateTy* St) + explicit ExplodedNode(const ProgramPoint& loc, const StateTy* St) : ExplodedNodeImpl(loc, St) {} /// getState - Returns the state associated with the node. - inline StateTy* getState() const { - return static_cast<StateTy*>(State); + inline const StateTy* getState() const { + return static_cast<const StateTy*>(State); } // Profiling (for FoldingSet). static inline void Profile(llvm::FoldingSetNodeID& ID, const ProgramPoint& Loc, - StateTy* state) { + const StateTy* state) { ID.Add(Loc); GRTrait<StateTy>::Profile(ID, state); } @@ -241,7 +239,8 @@ protected: /// getNodeImpl - Retrieve the node associated with a (Location,State) /// pair, where 'State' is represented as an opaque void*. This method /// is intended to be used only by GRCoreEngineImpl. - virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, void* State, + virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, + const void* State, bool* IsNew) = 0; virtual ExplodedGraphImpl* MakeEmptyGraph() const = 0; @@ -300,9 +299,10 @@ protected: protected: virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, - void* State, bool* IsNew) { + const void* State, + bool* IsNew) { - return getNode(L, static_cast<StateTy*>(State), IsNew); + return getNode(L, static_cast<const StateTy*>(State), IsNew); } virtual ExplodedGraphImpl* MakeEmptyGraph() const { @@ -317,7 +317,8 @@ public: /// where the 'Location' is a ProgramPoint in the CFG. If no node for /// this pair exists, it is created. IsNew is set to true if /// the node was freshly created. - NodeTy* getNode(const ProgramPoint& L, StateTy* State, bool* IsNew = NULL) { + NodeTy* getNode(const ProgramPoint& L, const StateTy* State, + bool* IsNew = NULL) { // Profile 'State' to determine if we already have an existing node. llvm::FoldingSetNodeID profile; diff --git a/include/clang/Analysis/PathSensitive/GRCoreEngine.h b/include/clang/Analysis/PathSensitive/GRCoreEngine.h index 19028ee875..32fe9d3342 100644 --- a/include/clang/Analysis/PathSensitive/GRCoreEngine.h +++ b/include/clang/Analysis/PathSensitive/GRCoreEngine.h @@ -61,14 +61,14 @@ protected: /// number of times different CFGBlocks have been visited along a path. GRBlockCounter::Factory BCounterFactory; - void GenerateNode(const ProgramPoint& Loc, void* State, + void GenerateNode(const ProgramPoint& Loc, const void* State, ExplodedNodeImpl* Pred = NULL); /// getInitialState - Gets the void* representing the initial 'state' /// of the analysis. This is simply a wrapper (implemented /// in GRCoreEngine) that performs type erasure on the initial /// state returned by the checker object. - virtual void* getInitialState() = 0; + virtual const void* getInitialState() = 0; void HandleBlockEdge(const BlockEdge& E, ExplodedNodeImpl* Pred); void HandleBlockEntrance(const BlockEntrance& E, ExplodedNodeImpl* Pred); @@ -81,7 +81,7 @@ protected: virtual void ProcessEndPath(GREndPathNodeBuilderImpl& Builder) = 0; - virtual bool ProcessBlockEntrance(CFGBlock* Blk, void* State, + virtual bool ProcessBlockEntrance(CFGBlock* Blk, const void* State, GRBlockCounter BC) = 0; virtual void ProcessStmt(Stmt* S, GRStmtNodeBuilderImpl& Builder) = 0; @@ -142,11 +142,11 @@ public: } ExplodedNodeImpl* - generateNodeImpl(Stmt* S, void* State, ExplodedNodeImpl* Pred, + generateNodeImpl(Stmt* S, const void* State, ExplodedNodeImpl* Pred, ProgramPoint::Kind K = ProgramPoint::PostStmtKind); ExplodedNodeImpl* - generateNodeImpl(Stmt* S, void* State, + generateNodeImpl(Stmt* S, const void* State, ProgramPoint::Kind K = ProgramPoint::PostStmtKind) { ExplodedNodeImpl* N = getLastNode(); assert (N && "Predecessor of new node is infeasible."); @@ -169,7 +169,7 @@ class GRStmtNodeBuilder { typedef ExplodedNode<StateTy> NodeTy; GRStmtNodeBuilderImpl& NB; - StateTy* CleanedState; + const StateTy* CleanedState; GRAuditor<StateTy> **CallExprAuditBeg, **CallExprAuditEnd; GRAuditor<StateTy> **ObjCMsgExprAuditBeg, **ObjCMsgExprAuditEnd; @@ -201,7 +201,7 @@ public: } NodeTy* - generateNode(Stmt* S, StateTy* St, NodeTy* Pred, + generateNode(Stmt* S, const StateTy* St, NodeTy* Pred, ProgramPoint::Kind K = ProgramPoint::PostStmtKind) { HasGeneratedNode = true; @@ -210,7 +210,7 @@ public: } NodeTy* - generateNode(Stmt* S, StateTy* St, + generateNode(Stmt* S, const StateTy* St, ProgramPoint::Kind K = ProgramPoint::PostStmtKind) { HasGeneratedNode = true; @@ -226,21 +226,21 @@ public: return NB.getCurrentBlockCount(); } - StateTy* GetState(NodeTy* Pred) const { + const StateTy* GetState(NodeTy* Pred) const { if ((ExplodedNodeImpl*) Pred == NB.getBasePredecessor()) return CleanedState; else return Pred->getState(); } - void SetCleanedState(StateTy* St) { + void SetCleanedState(const StateTy* St) { CleanedState = St; } NodeTy* MakeNode(ExplodedNodeSet<StateTy>& Dst, Stmt* S, - NodeTy* Pred, StateTy* St) { + NodeTy* Pred, const StateTy* St) { - StateTy* PredState = GetState(Pred); + const StateTy* PredState = GetState(Pred); GRAuditor<StateTy> **AB = NULL, **AE = NULL; @@ -309,7 +309,7 @@ public: const ExplodedGraphImpl& getGraph() const { return *Eng.G; } GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();} - ExplodedNodeImpl* generateNodeImpl(void* State, bool branch); + ExplodedNodeImpl* generateNodeImpl(const void* State, bool branch); CFGBlock* getTargetBlock(bool branch) const { return branch ? DstT : DstF; @@ -340,11 +340,11 @@ public: return static_cast<NodeTy*>(NB.getPredecessor()); } - StateTy* getState() const { + const StateTy* getState() const { return getPredecessor()->getState(); } - NodeTy* generateNode(StateTy* St, bool branch) { + NodeTy* generateNode(const StateTy* St, bool branch) { return static_cast<NodeTy*>(NB.generateNodeImpl(St, branch)); } @@ -396,11 +396,11 @@ public: Iterator begin() { return Iterator(DispatchBlock.succ_begin()); } Iterator end() { return Iterator(DispatchBlock.succ_end()); } - ExplodedNodeImpl* generateNodeImpl(const Iterator& I, void* State, + ExplodedNodeImpl* generateNodeImpl(const Iterator& I, const void* State, bool isSink); Expr* getTarget() const { return E; } - void* getState() const { return Pred->State; } + const void* getState() const { return Pred->State; } }; template<typename STATE> @@ -421,12 +421,12 @@ public: Expr* getTarget() const { return NB.getTarget(); } - NodeTy* generateNode(const iterator& I, StateTy* St, bool isSink=false){ + NodeTy* generateNode(const iterator& I, const StateTy* St, bool isSink=false){ return static_cast<NodeTy*>(NB.generateNodeImpl(I, St, isSink)); } - StateTy* getState() const { - return static_cast<StateTy*>(NB.getState()); + const StateTy* getState() const { + return static_cast<const StateTy*>(NB.getState()); } }; @@ -462,11 +462,14 @@ public: Iterator begin() { return Iterator(Src->succ_rbegin()+1); } Iterator end() { return Iterator(Src->succ_rend()); } - ExplodedNodeImpl* generateCaseStmtNodeImpl(const Iterator& I, void* State); - ExplodedNodeImpl* generateDefaultCaseNodeImpl(void* State, bool isSink); + ExplodedNodeImpl* generateCaseStmtNodeImpl(const Iterator& I, + const void* State); + + ExplodedNodeImpl* generateDefaultCaseNodeImpl(const void* State, + bool isSink); Expr* getCondition() const { return Condition; } - void* getState() const { return Pred->State; } + const void* getState() const { return Pred->State; } }; template<typename STATE> @@ -487,16 +490,16 @@ public: Expr* getCondition() const { return NB.getCondition(); } - NodeTy* generateCaseStmtNode(const iterator& I, StateTy* St) { + NodeTy* generateCaseStmtNode(const iterator& I, const StateTy* St) { return static_cast<NodeTy*>(NB.generateCaseStmtNodeImpl(I, St)); } - NodeTy* generateDefaultCaseNode(StateTy* St, bool isSink = false) { + NodeTy* generateDefaultCaseNode(const StateTy* St, bool isSink = false) { return static_cast<NodeTy*>(NB.generateDefaultCaseNodeImpl(St, isSink)); } - StateTy* getState() const { - return static_cast<StateTy*>(NB.getState()); + const StateTy* getState() const { + return static_cast<const StateTy*>(NB.getState()); } }; @@ -522,7 +525,7 @@ public: return getBlockCounter().getNumVisited(B.getBlockID()); } - ExplodedNodeImpl* generateNodeImpl(void* State); + ExplodedNodeImpl* generateNodeImpl(const void* State); CFGBlock* getBlock() const { return &B; } }; @@ -550,11 +553,11 @@ public: return NB.getCurrentBlockCount(); } - StateTy* getState() const { + const StateTy* getState() const { return getPredecessor()->getState(); } - NodeTy* MakeNode(StateTy* St) { + NodeTy* MakeNode(const StateTy* St) { return static_cast<NodeTy*>(NB.generateNodeImpl(St)); } }; @@ -571,7 +574,7 @@ public: protected: SubEngineTy& SubEngine; - virtual void* getInitialState() { + virtual const void* getInitialState() { return SubEngine.getInitialState(); } @@ -585,9 +588,11 @@ protected: SubEngine.ProcessStmt(S, Builder); } - virtual bool ProcessBlockEntrance(CFGBlock* Blk, void* State, + virtual bool ProcessBlockEntrance(CFGBlock* Blk, const void* State, GRBlockCounter BC) { - return SubEngine.ProcessBlockEntrance(Blk, static_cast<StateTy*>(State),BC); + return SubEngine.ProcessBlockEntrance(Blk, + static_cast<const StateTy*>(State), + BC); } virtual void ProcessBranch(Expr* Condition, Stmt* Terminator, diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h index 6dfd428bf4..97699ca902 100644 --- a/include/clang/Analysis/PathSensitive/GRExprEngine.h +++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h @@ -86,7 +86,7 @@ protected: /// CleanedState - The state for EntryNode "cleaned" of all dead /// variables and symbols (as determined by a liveness analysis). - ValueState* CleanedState; + const ValueState* CleanedState; /// CurrentStmt - The current block-level statement. Stmt* CurrentStmt; @@ -210,7 +210,7 @@ public: /// getInitialState - Return the initial state used for the root vertex /// in the ExplodedGraph. - ValueState* getInitialState(); + const ValueState* getInitialState(); GraphTy& getGraph() { return G; } const GraphTy& getGraph() const { return G; } @@ -370,7 +370,8 @@ public: /// ProcessBlockEntrance - Called by GRCoreEngine when start processing /// a CFGBlock. This method returns true if the analysis should continue /// exploring the given path, and false otherwise. - bool ProcessBlockEntrance(CFGBlock* B, ValueState* St, GRBlockCounter BC); + bool ProcessBlockEntrance(CFGBlock* B, const ValueState* St, + GRBlockCounter BC); /// ProcessBranch - Called by GRCoreEngine. Used to generate successor /// nodes by processing the 'effects' of a branch condition. @@ -401,7 +402,7 @@ public: protected: - ValueState* GetState(NodeTy* N) { + const ValueState* GetState(NodeTy* N) { return N == EntryNode ? CleanedState : N->getState(); } @@ -409,35 +410,35 @@ public: // FIXME: Maybe make these accesible only within the StmtBuilder? - ValueState* SetRVal(ValueState* St, Expr* Ex, RVal V); + const ValueState* SetRVal(const ValueState* St, Expr* Ex, RVal V); - ValueState* SetRVal(ValueState* St, const Expr* Ex, RVal V) { + const ValueState* SetRVal(const ValueState* St, const Expr* Ex, RVal V) { return SetRVal(St, const_cast<Expr*>(Ex), V); } protected: - ValueState* SetBlkExprRVal(ValueState* St, Expr* Ex, RVal V) { + const ValueState* SetBlkExprRVal(const ValueState* St, Expr* Ex, RVal V) { return StateMgr.SetRVal(St, Ex, V, true, false); } - ValueState* SetRVal(ValueState* St, LVal LV, RVal V) { + const ValueState* SetRVal(const ValueState* St, LVal LV, RVal V) { return StateMgr.SetRVal(St, LV, V); } - RVal GetRVal(ValueState* St, Expr* Ex) { + RVal GetRVal(const ValueState* St, Expr* Ex) { return StateMgr.GetRVal(St, Ex); } - RVal GetRVal(ValueState* St, const Expr* Ex) { + RVal GetRVal(const ValueState* St, const Expr* Ex) { return GetRVal(St, const_cast<Expr*>(Ex)); } - RVal GetBlkExprRVal(ValueState* St, Expr* Ex) { + RVal GetBlkExprRVal(const ValueState* St, Expr* Ex) { return StateMgr.GetBlkExprRVal(St, Ex); } - RVal GetRVal(ValueState* St, LVal LV, QualType T = QualType()) { + RVal GetRVal(const ValueState* St, LVal LV, QualType T = QualType()) { return StateMgr.GetRVal(St, LV, T); } @@ -447,8 +448,8 @@ protected: /// Assume - Create new state by assuming that a given expression /// is true or false. - ValueState* Assume(ValueState* St, RVal Cond, bool Assumption, - bool& isFeasible) { + const ValueState* Assume(const ValueState* St, RVal Cond, bool Assumption, + bool& isFeasible) { if (Cond.isUnknown()) { isFeasible = true; @@ -461,28 +462,28 @@ protected: return Assume(St, cast<NonLVal>(Cond), Assumption, isFeasible); } - ValueState* Assume(ValueState* St, LVal Cond, bool Assumption, - bool& isFeasible); + const ValueState* Assume(const ValueState* St, LVal Cond, bool Assumption, + bool& isFeasible); - ValueState* AssumeAux(ValueState* St, LVal Cond, bool Assumption, - bool& isFeasible); + const ValueState* AssumeAux(const ValueState* St, LVal Cond, bool Assumption, + bool& isFeasible); - ValueState* Assume(ValueState* St, NonLVal Cond, bool Assumption, - bool& isFeasible); + const ValueState* Assume(const ValueState* St, NonLVal Cond, bool Assumption, + bool& isFeasible); - ValueState* AssumeAux(ValueState* St, NonLVal Cond, bool Assumption, - bool& isFeasible); + const ValueState* AssumeAux(const ValueState* St, NonLVal Cond, + bool Assumption, bool& isFeasible); - ValueState* AssumeSymNE(ValueState* St, SymbolID sym, const llvm::APSInt& V, - bool& isFeasible); + const ValueState* AssumeSymNE(const ValueState* St, SymbolID sym, + const llvm::APSInt& V, bool& isFeasible); - ValueState* AssumeSymEQ(ValueState* St, SymbolID sym, const llvm::APSInt& V, - bool& isFeasible); + const ValueState* AssumeSymEQ(const ValueState* St, SymbolID sym, + const llvm::APSInt& V, bool& isFeasible); - ValueState* AssumeSymInt(ValueState* St, bool Assumption, - const SymIntConstraint& C, bool& isFeasible); + const ValueState* AssumeSymInt(const ValueState* St, bool Assumption, + const SymIntConstraint& C, bool& isFeasible); - NodeTy* MakeNode(NodeSet& Dst, Stmt* S, NodeTy* Pred, ValueState* St) { + NodeTy* MakeNode(NodeSet& Dst, Stmt* S, NodeTy* Pred, const ValueState* St) { assert (Builder && "GRStmtNodeBuilder not present."); return Builder->MakeNode(Dst, S, Pred, St); } @@ -568,7 +569,8 @@ protected: void VisitUnaryOperator(UnaryOperator* B, NodeTy* Pred, NodeSet& Dst, bool asLVal); - bool CheckDivideZero(Expr* Ex, ValueState* St, NodeTy* Pred, RVal Denom); + bool CheckDivideZero(Expr* Ex, const ValueState* St, NodeTy* Pred, + RVal Denom); RVal EvalCast(RVal X, QualType CastT) { if (X.isUnknownOrUndef()) @@ -634,21 +636,22 @@ protected: TF->EvalObjCMessageExpr(Dst, *this, *Builder, ME, Pred); } - void EvalStore(NodeSet& Dst, Expr* E, NodeTy* Pred, ValueState* St, + void EvalStore(NodeSet& Dst, Expr* E, NodeTy* Pred, const ValueState* St, RVal TargetLV, RVal Val); // FIXME: The "CheckOnly" option exists only because Array and Field // loads aren't fully implemented. Eventually this option will go away. void EvalLoad(NodeSet& Dst, Expr* Ex, NodeTy* Pred, - ValueState* St, RVal location, bool CheckOnly = false); + const ValueState* St, RVal location, bool CheckOnly = false); - ValueState* EvalLocation(Expr* Ex, NodeTy* Pred, - ValueState* St, RVal location, bool isLoad = false); + const ValueState* EvalLocation(Expr* Ex, NodeTy* Pred, + const ValueState* St, RVal location, + bool isLoad = false); void EvalReturn(NodeSet& Dst, ReturnStmt* s, NodeTy* Pred); - ValueState* MarkBranch(ValueState* St, Stmt* Terminator, bool branchTaken); + const ValueState* MarkBranch(const ValueState* St, Stmt* Terminator, bool branchTaken); }; } // end clang namespace diff --git a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h index 323358e0c3..4e267f8859 100644 --- a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h +++ b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h @@ -82,7 +82,7 @@ public: GRExprEngine& Engine, GRStmtNodeBuilder<ValueState>& Builder, Expr* E, ExplodedNode<ValueState>* Pred, - ValueState* St, RVal TargetLV, RVal Val); + const ValueState* St, RVal TargetLV, RVal Val); // End-of-path and dead symbol notification. @@ -96,7 +96,7 @@ public: GRStmtNodeBuilder<ValueState>& Builder, ExplodedNode<ValueState>* Pred, Stmt* S, - ValueState* St, + const ValueState* St, const ValueStateManager::DeadSymbolsTy& Dead) {} // Return statements. @@ -109,8 +109,10 @@ public: // Assumptions. - virtual ValueState* EvalAssume(GRExprEngine& Engine, ValueState* St, - RVal Cond, bool Assumption, bool& isFeasible) { + virtual const ValueState* EvalAssume(GRExprEngine& Engine, + const ValueState* St, + RVal Cond, bool Assumption, + bool& isFeasible) { return St; } }; diff --git a/include/clang/Analysis/PathSensitive/Store.h b/include/clang/Analysis/PathSensitive/Store.h new file mode 100644 index 0000000000..adf9cf8eae --- /dev/null +++ b/include/clang/Analysis/PathSensitive/Store.h @@ -0,0 +1,34 @@ +//== Store.h - Interface for maps from Locations to Values ------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defined the types Store and StoreManager. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_STORE_H +#define LLVM_CLANG_ANALYSIS_STORE_H + +#include "clang/Analysis/PathSensitive/RValues.h" + +namespace clang { + +typedef const void* Store; + +class StoreManager { +public: + virtual ~StoreManager() {} + virtual RVal GetRVal(Store St, LVal LV, QualType T) = 0; + virtual Store SetRVal(Store St, LVal LV, RVal V) = 0; + virtual Store Remove(Store St, LVal LV) = 0; + virtual Store getInitialStore() = 0; +}; + +} // end clang namespace + +#endif diff --git a/include/clang/Analysis/PathSensitive/ValueState.h b/include/clang/Analysis/PathSensitive/ValueState.h index ab9b4a8b32..36bfdff5b9 100644 --- a/include/clang/Analysis/PathSensitive/ValueState.h +++ b/include/clang/Analysis/PathSensitive/ValueState.h @@ -17,6 +17,7 @@ // FIXME: Reduce the number of includes. #include "clang/Analysis/PathSensitive/Environment.h" +#include "clang/Analysis/PathSensitive/Store.h" #include "clang/Analysis/PathSensitive/RValues.h" #include "clang/Analysis/PathSensitive/GRCoreEngine.h" #include "clang/AST/Expr.h" @@ -54,7 +55,6 @@ class ValueState : public llvm::FoldingSetNode { public: // Typedefs. typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; - typedef llvm::ImmutableMap<VarDecl*,RVal> VarBindingsTy; typedef llvm::ImmutableMap<SymbolID,IntSetTy> ConstNotEqTy; typedef llvm::ImmutableMap<SymbolID,const llvm::APSInt*> ConstEqTy; @@ -64,10 +64,10 @@ private: friend class ValueStateManager; Environment Env; + Store St; // FIXME: Make these private. public: - VarBindingsTy VarBindings; ConstNotEqTy ConstNotEq; ConstEqTy ConstEq; void* CheckerState; @@ -75,10 +75,10 @@ public: public: /// This ctor is used when creating the first ValueState object. - ValueState(const Environment& env, VarBindingsTy VB, + ValueState(const Environment& env, Store st, ConstNotEqTy CNE, ConstEqTy CE) : Env(env), - VarBindings(VB), + St(st), ConstNotEq(CNE), ConstEq(CE), CheckerState(NULL) {} @@ -88,7 +88,7 @@ public: ValueState(const ValueState& RHS) : llvm::FoldingSetNode(), Env(RHS.Env), - VarBindings(RHS.VarBindings), + St(RHS.St), ConstNotEq(RHS.ConstNotEq), ConstEq(RHS.ConstEq), CheckerState(RHS.CheckerState) {} @@ -97,11 +97,15 @@ public: /// The environment is the mapping from expressions to values. const Environment& getEnvironment() const { return Env; } + /// getStore - Return the store associated with this state. The store + /// is a mapping from locations to values. + Store getStore() const { return St; } + /// Profile - Profile the contents of a ValueState object for use /// in a FoldingSet. static void Profile(llvm::FoldingSetNodeID& ID, const ValueState* V) { V->Env.Profile(ID); - V->VarBindings.Profile(ID); + ID.AddPointer(V->St); V->ConstNotEq.Profile(ID); V->ConstEq.Profile(ID); ID.AddPointer(V->CheckerState); @@ -124,9 +128,18 @@ public: // Iterators. + // FIXME: We'll be removing the VarBindings iterator very soon. Right now + // it assumes that Store is a VarBindingsTy. + typedef llvm::ImmutableMap<VarDecl*,RVal> VarBindingsTy; typedef VarBindingsTy::iterator vb_iterator; - vb_iterator vb_begin() const { return VarBindings.begin(); } - vb_iterator vb_end() const { return VarBindings.end(); } + vb_iterator vb_begin() const { + VarBindingsTy B(static_cast<const VarBindingsTy::TreeTy*>(St)); + return B.begin(); + } + vb_iterator vb_end() const { + VarBindingsTy B(static_cast<const VarBindingsTy::TreeTy*>(St)); + return B.end(); + } typedef Environment::seb_iterator seb_iterator; seb_iterator seb_begin() const { return Env.seb_begin(); } @@ -173,8 +186,8 @@ template<> struct GRTrait<ValueState*> { class ValueStateManager { private: EnvironmentManager EnvMgr; + llvm::OwningPtr<StoreManager> StMgr; ValueState::IntSetTy::Factory ISetFactory; - ValueState::VarBindingsTy::Factory VBFactory; ValueState::ConstNotEqTy::Factory CNEFactory; ValueState::ConstEqTy::Factory CEFactory; @@ -196,58 +209,53 @@ private: Environment RemoveBlkExpr(const Environment& Env, Expr* E) { return EnvMgr.RemoveBlkExpr(Env, E); } - - ValueState::VarBindingsTy Remove(ValueState::VarBindingsTy B, VarDecl* V) { - return VBFactory.Remove(B, V); - } - - ValueState::VarBindingsTy Remove(const ValueState& V, VarDecl* D) { - return Remove(V.VarBindings, D); + + // FIXME: Remove when we do lazy initializaton of variable bindings. + const ValueState* BindVar(const ValueState* St, VarDecl* D, RVal V) { + return SetRVal(St, lval::DeclVal(D), V); } - - ValueState* BindVar(ValueState* St, VarDecl* D, RVal V); - ValueState* UnbindVar(ValueState* St, VarDecl* D); - + public: - ValueStateManager(ASTContext& Ctx, llvm::BumpPtrAllocator& alloc) - : EnvMgr(alloc), - ISetFactory(alloc), - VBFactory(alloc), - CNEFactory(alloc), - CEFactory(alloc), - BasicVals(Ctx, alloc), - SymMgr(alloc), - Alloc(alloc) {} - - ValueState* getInitialState(); + ValueStateManager(ASTContext& Ctx, StoreManager* stmgr, + llvm::BumpPtrAllocator& alloc) + : EnvMgr(alloc), + StMgr(stmgr), + ISetFactory(alloc), + CNEFactory(alloc), + CEFactory(alloc), + BasicVals(Ctx, alloc), + SymMgr(alloc), + Alloc(alloc) {} + + const ValueState* getInitialState(); BasicValueFactory& getBasicValueFactory() { return BasicVals; } SymbolManager& getSymbolManager() { return SymMgr; } typedef llvm::DenseSet<SymbolID> DeadSymbolsTy; - ValueState* RemoveDeadBindings(ValueState* St, Stmt* Loc, - const LiveVariables& Liveness, - DeadSymbolsTy& DeadSymbols); + const ValueState* RemoveDeadBindings(const ValueState* St, Stmt* Loc, + const LiveVariables& Liveness, + DeadSymbolsTy& DeadSymbols); - ValueState* RemoveSubExprBindings(ValueState* St) { + const ValueState* RemoveSubExprBindings(const ValueState* St) { ValueState NewSt = *St; NewSt.Env = EnvMgr.RemoveSubExprBindings(NewSt.Env); - return getPersistentState(NewSt); + return getPersistentState(NewSt); } // Methods that query & manipulate the Environment. - RVal GetRVal(ValueState* St, Expr* Ex) { + RVal GetRVal(const ValueState* St, Expr* Ex) { return St->getEnvironment().GetRVal(Ex, BasicVals); } - RVal GetBlkExprRVal(ValueState* St, Expr* Ex) { + RVal GetBlkExprRVal(const ValueState* St, Expr* Ex) { return St->getEnvironment().GetBlkExprRVal(Ex, BasicVals); } - ValueState* SetRVal(ValueState* St, Expr* Ex, RVal V, bool isBlkExpr, - bool Invalidate) { + const ValueState* SetRVal(const ValueState* St, Expr* Ex, RVal V, + bool isBlkExpr, bool Invalidate) { const Environment& OldEnv = St->getEnvironment(); Environment NewEnv = EnvMgr.SetRVal(OldEnv, Ex, V, isBlkExpr, Invalidate); @@ -262,18 +270,29 @@ public: // Methods that query & manipulate the Store. - RVal GetRVal(ValueState* St, LVal LV, QualType T = QualType()); + RVal GetRVal(const ValueState* St, LVal LV, QualType T = QualType()) { + return StMgr->GetRVal(St->getStore(), LV, T); + } - ValueState* SetRVal(ValueState* St, LVal LV, RVal V); + void SetRVal(ValueState& St, LVal LV, RVal V) { + St.St = StMgr->SetRVal(St.St, LV, V); + } + + const ValueState* SetRVal(const ValueState* St, LVal LV, RVal V); - void BindVar(ValueState& StImpl, VarDecl* D, RVal V); + void Unbind(ValueState& St, LVal LV) { + St.St = StMgr->Remove(St.St, LV); + } - void Unbind(ValueState& StImpl, LVal LV); + const ValueState* Unbind(const ValueState* St, LVal LV); - ValueState* getPersistentState(ValueState& Impl); + const ValueState* getPersistentState(ValueState& Impl); - ValueState* AddEQ(ValueState* St, SymbolID sym, const llvm::APSInt& V); - ValueState* AddNE(ValueState* St, SymbolID sym, const llvm::APSInt& V); + const ValueState* AddEQ(const ValueState* St, SymbolID sym, + const llvm::APSInt& V); + + const ValueState* AddNE(const ValueState* St, SymbolID sym, + const llvm::APSInt& V); }; } // end clang namespace diff --git a/lib/Analysis/BasicObjCFoundationChecks.cpp b/lib/Analysis/BasicObjCFoundationChecks.cpp index 1667a21494..4475ed2bc5 100644 --- a/lib/Analysis/BasicObjCFoundationChecks.cpp +++ b/lib/Analysis/BasicObjCFoundationChecks.cpp @@ -107,7 +107,7 @@ class VISIBILITY_HIDDEN BasicObjCFoundationChecks : public GRSimpleAPICheck { typedef std::vector<BugReport*> ErrorsTy; ErrorsTy Errors; - RVal GetRVal(ValueState* St, Expr* E) { return VMgr->GetRVal(St, E); } + RVal GetRVal(const ValueState* St, Expr* E) { return VMgr->GetRVal(St, E); } bool isNSString(ObjCInterfaceType* T, const char* suffix); bool AuditNSString(NodeTy* N, ObjCMessageExpr* ME); @@ -338,8 +338,8 @@ class VISIBILITY_HIDDEN AuditCFNumberCreate : public GRSimpleAPICheck { IdentifierInfo* II; ValueStateManager* VMgr; - RVal GetRVal(ValueState* St, Expr* E) { return VMgr->GetRVal(St, E); } - RVal GetRVal(ValueState* St, LVal LV) { return VMgr->GetRVal(St, LV); } + RVal GetRVal(const ValueState* St, Expr* E) { return VMgr->GetRVal(St, E); } + RVal GetRVal(const ValueState* St, LVal LV) { return VMgr->GetRVal(St, LV); } public: diff --git a/lib/Analysis/BasicStore.cpp b/lib/Analysis/BasicStore.cpp new file mode 100644 index 0000000000..38c1db70f1 --- /dev/null +++ b/lib/Analysis/BasicStore.cpp @@ -0,0 +1,141 @@ +//== BasicStore.cpp - Basic map from Locations to Values --------*- C++ -*--==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defined the BasicStore and BasicStoreManager classes. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/PathSensitive/BasicStore.h" +#include "llvm/ADT/ImmutableMap.h" +#include "llvm/Support/Compiler.h" + +using namespace clang; + +namespace { + +class VISIBILITY_HIDDEN BasicStoreManager : public StoreManager { + typedef llvm::ImmutableMap<VarDecl*,RVal> VarBindingsTy; + VarBindingsTy::Factory VBFactory; + +public: + BasicStoreManager(llvm::BumpPtrAllocator& A) : VBFactory(A) {} + virtual ~BasicStoreManager() {} + + virtual RVal GetRVal(Store St, LVal LV, QualType T); + virtual Store SetRVal(Store St, LVal LV, RVal V); + virtual Store Remove(Store St, LVal LV); + + virtual Store getInitialStore() { + return VBFactory.GetEmptyMap().getRoot(); + } +}; + +} // end anonymous namespace + + +StoreManager* clang::CreateBasicStoreManager(llvm::BumpPtrAllocator& A) { + return new BasicStoreManager(A); +} + +RVal BasicStoreManager::GetRVal(Store St, LVal LV, QualType T) { + + if (isa<UnknownVal>(LV)) + return UnknownVal(); + + assert (!isa<UndefinedVal>(LV)); + + switch (LV.getSubKind()) { + + case lval::DeclValKind: { + VarBindingsTy B(static_cast<const VarBindingsTy::TreeTy*>(St)); + VarBindingsTy::data_type* T = B.lookup(cast<lval::DeclVal>(LV).getDecl()); + return T ? *T : UnknownVal(); + } + + case lval::SymbolValKind: { + + // FIXME: This is a broken representation of memory, and is prone + // to crashing the analyzer when addresses to symbolic values are + // passed through casts. We need a better representation of symbolic + // memory (or just memory in general); probably we should do this + // as a plugin class (similar to GRTransferFuncs). + +#if 0 + const lval::SymbolVal& SV = cast<lval::SymbolVal>(LV); + assert (T.getTypePtr()); + + // Punt on "symbolic" function pointers. + if (T->isFunctionType()) + return UnknownVal(); + + if (T->isPointerType()) + return lval::SymbolVal(SymMgr.getContentsOfSymbol(SV.getSymbol())); + else + return nonlval::SymbolVal(SymMgr.getContentsOfSymbol(SV.getSymbol())); +#endif + + return UnknownVal(); + } + + case lval::ConcreteIntKind: + // Some clients may call GetRVal with such an option simply because + // they are doing a quick scan through their LVals (potentially to + // invalidate their bindings). Just return Undefined. + return UndefinedVal(); + + case lval::ArrayOffsetKind: + case lval::FieldOffsetKind: + return UnknownVal(); + + case lval::FuncValKind: + return LV; + + case lval::StringLiteralValKind: + // FIXME: Implement better support for fetching characters from strings. + return UnknownVal(); + + default: + assert (false && "Invalid LVal."); + break; + } + + return UnknownVal(); +} + +Store BasicStoreManager::SetRVal(Store St, LVal LV, RVal V) { + + VarBindingsTy B(static_cast<const VarBindingsTy::TreeTy*>(St)); + + switch (LV.getSubKind()) { + + case lval::DeclValKind: + return V.isUnknown() + ? VBFactory.Remove(B,cast<lval::DeclVal>(LV).getDecl()).getRoot() + : VBFactory.Add(B, cast<lval::DeclVal>(LV).getDecl(), V).getRoot(); + + default: + assert ("SetRVal for given LVal type not yet implemented."); + return St; + } +} + +Store BasicStoreManager::Remove(Store St, LVal LV) { + + VarBindingsTy B(static_cast<const VarBindingsTy::TreeTy*>(St)); + + switch (LV.getSubKind()) { + + case lval::DeclValKind: + return VBFactory.Remove(B,cast<lval::DeclVal>(LV).getDecl()).getRoot(); + + default: + assert ("Remove for given LVal type not yet implemented."); + return St; + } +} diff --git a/lib/Analysis/BugReporter.cpp b/lib/Analysis/BugReporter.cpp index fba31f81af..081e7925ee 100644 --- a/lib/Analysis/BugReporter.cpp +++ b/lib/Analysis/BugReporter.cpp @@ -327,7 +327,7 @@ static void HandleNotableSymbol(ExplodedNode<ValueState>* N, Stmt* S, PathDiagnostic& PD) { ExplodedNode<ValueState>* Pred = N->pred_empty() ? 0 : *N->pred_begin(); - ValueState* PrevSt = Pred ? Pred->getState() : 0; + const ValueState* PrevSt = Pred ? Pred->getState() : 0; if (!PrevSt) return; @@ -335,7 +335,7 @@ static void HandleNotableSymbol(ExplodedNode<ValueState>* N, Stmt* S, // Look at the variable bindings of the current state that map to the // specified symbol. Are any of them not in the previous state. - ValueState* St = N->getState(); + const ValueState* St = N->getState(); ValueStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager(); // FIXME: Later generalize for a broader memory model. @@ -633,7 +633,7 @@ void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD, if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) { - ValueState* St = N->getState(); + const ValueState* St = N->getState(); // Scan the lval bindings, and see if a "notable" symbol has a new // lval binding. diff --git a/lib/Analysis/CFRefCount.cpp b/lib/Analysis/CFRefCount.cpp index 1a57306f86..4de91daa1b 100644 --- a/lib/Analysis/CFRefCount.cpp +++ b/lib/Analysis/CFRefCount.cpp @@ -1135,8 +1135,8 @@ private: public: - static RefBindings GetRefBindings(ValueState& StImpl) { - return RefBindings((RefBindings::TreeTy*) StImpl.CheckerState); + static RefBindings GetRefBindings(const ValueState& StImpl) { + return RefBindings((const RefBindings::TreeTy*) StImpl.CheckerState); } private: @@ -1156,14 +1156,15 @@ private: GRStmtNodeBuilder<ValueState>& Builder, Expr* NodeExpr, Expr* ErrorExpr, ExplodedNode<ValueState>* Pred, - ValueState* St, + const ValueState* St, RefVal::Kind hasErr, SymbolID Sym); - ValueState* HandleSymbolDeath(ValueStateManager& VMgr, ValueState* St, - SymbolID sid, RefVal V, bool& hasLeak); + const ValueState* HandleSymbolDeath(ValueStateManager& VMgr, + const ValueState* St, + SymbolID sid, RefVal V, bool& hasLeak); - ValueState* NukeBinding(ValueStateManager& VMgr, ValueState* St, - SymbolID sid); + const ValueState* NukeBinding(ValueStateManager& VMgr, const ValueState* St, + SymbolID sid); public: @@ -1226,7 +1227,7 @@ public: GRExprEngine& Engine, GRStmtNodeBuilder<ValueState>& Builder, Expr* E, ExplodedNode<ValueState>* Pred, - ValueState* St, RVal TargetLV, RVal Val); + const ValueState* St, RVal TargetLV, RVal Val); // End-of-path. virtual void EvalEndPath(GRExprEngine& Engine, @@ -1237,7 +1238,7 @@ public: GRStmtNodeBuilder<ValueState>& Builder, ExplodedNode<ValueState>* Pred, Stmt* S, - ValueState* St, + const ValueState* St, const ValueStateManager::DeadSymbolsTy& Dead); // Return statements. @@ -1249,8 +1250,9 @@ public: // Assumptions. - virtual ValueState* EvalAssume(GRExprEngine& Engine, ValueState* St, - RVal Cond, bool Assumption, bool& isFeasible); + virtual const ValueState* EvalAssume(GRExprEngine& Engine, + const ValueState* St, RVal Cond, + bool Assumption, bool& isFeasible); // Error iterators. @@ -1304,7 +1306,7 @@ void CFRefCount::ProcessNonLeakError(ExplodedNodeSet<ValueState>& Dst, GRStmtNodeBuilder<ValueState>& Builder, Expr* NodeExpr, Expr* ErrorExpr, ExplodedNode<ValueState>* Pred, - ValueState* St, + const ValueState* St, RefVal::Kind hasErr, SymbolID Sym) { Builder.BuildSinks = true; GRExprEngine::NodeTy* N = Builder.MakeNode(Dst, NodeExpr, Pred, St); @@ -1368,7 +1370,7 @@ void CFRefCount::EvalSummary(ExplodedNodeSet<ValueState>& Dst, // Get the state. ValueStateManager& StateMgr = Eng.getStateManager(); - ValueState* St = Builder.GetState(Pred); + const ValueState* St = Builder.GetState(Pred); // Evaluate the effect of the arguments. ValueState StVals = *St; @@ -1429,7 +1431,7 @@ void CFRefCount::EvalSummary(ExplodedNodeSet<ValueState>& Dst, unsigned Count = Builder.getCurrentBlockCount(); SymbolID NewSym = Eng.getSymbolManager().getConjuredSymbol(*I, Count); - StateMgr.BindVar(StVals, DV->getDecl(), + StateMgr.SetRVal(StVals, *DV, LVal::IsLValType(DV->getDecl()->getType()) ? cast<RVal>(lval::SymbolVal(NewSym)) : cast<RVal>(nonlval::SymbolVal(NewSym))); @@ -1596,7 +1598,7 @@ void CFRefCount::EvalObjCMessageExpr(ExplodedNodeSet<ValueState>& Dst, // FIXME: Wouldn't it be great if this code could be reduced? It's just // a chain of lookups. - ValueState* St = Builder.GetState(Pred); + const ValueState* St = Builder.GetState(Pred); RVal V = Eng.getStateManager().GetRVal(St, Receiver ); if (isa<lval::SymbolVal>(V)) { @@ -1630,7 +1632,7 @@ void CFRefCount::EvalStore(ExplodedNodeSet<ValueState>& Dst, GRExprEngine& Eng, GRStmtNodeBuilder<ValueState>& Builder, Expr* E, ExplodedNode<ValueState>* Pred, - ValueState* St, RVal TargetLV, RVal Val) { + const ValueState* St, RVal TargetLV, RVal Val) { // Check if we have a binding for "Val" and if we are storing it to something // we don't understand or otherwise the value "escapes" the function. @@ -1663,8 +1665,9 @@ void CFRefCount::EvalStore(ExplodedNodeSet<ValueState>& Dst, } -ValueState* CFRefCount::NukeBinding(ValueStateManager& VMgr, ValueState* St, - SymbolID sid) { +const ValueState* CFRefCount::NukeBinding(ValueStateManager& VMgr, + const ValueState* St, + SymbolID sid) { ValueState StImpl = *St; RefBindings B = GetRefBindings(StImpl); StImpl.CheckerState = RefBFactory.Remove(B, sid).getRoot(); @@ -1673,8 +1676,8 @@ ValueState* CFRefCount::NukeBinding(ValueStateManager& VMgr, ValueState* St, // End-of-path. -ValueState* CFRefCount::HandleSymbolDeath(ValueStateManager& VMgr, - ValueState* St, SymbolID sid, +const ValueState* CFRefCount::HandleSymbolDeath(ValueStateManager& VMgr, + const ValueState* St, SymbolID sid, RefVal V, bool& hasLeak) { hasLeak = V.isOwned() || @@ -1693,7 +1696,7 @@ ValueState* CFRefCount::HandleSymbolDeath(ValueStateManager& VMgr, void CFRefCount::EvalEndPath(GRExprEngine& Eng, GREndPathNodeBuilder<ValueState>& Builder) { - ValueState* St = Builder.getState(); + const ValueState* St = Builder.getState(); RefBindings B = GetRefBindings(*St); llvm::SmallVector<SymbolID, 10> Leaked; @@ -1731,7 +1734,7 @@ void CFRefCount::EvalDeadSymbols(ExplodedNodeSet<ValueState>& Dst, GRStmtNodeBuilder<ValueState>& Builder, ExplodedNode<ValueState>* Pred, Stmt* S, - ValueState* St, + const ValueState* St, const ValueStateManager::DeadSymbolsTy& Dead) { // FIXME: a lot of copy-and-paste from EvalEndPath. Refactor. @@ -1784,7 +1787,7 @@ void CFRefCount::EvalReturn(ExplodedNodeSet<ValueState>& Dst, if (!RetE) return; ValueStateManager& StateMgr = Eng.getStateManager(); - ValueState* St = Builder.GetState(Pred); + const ValueState* St = Builder.GetState(Pred); RVal V = StateMgr.GetRVal(St, RetE); if (!isa<lval::SymbolVal>(V)) @@ -1831,9 +1834,10 @@ void CFRefCount::EvalReturn(ExplodedNodeSet<ValueState>& Dst, // Assumptions. -ValueState* CFRefCount::EvalAssume(GRExprEngine& Eng, ValueState* St, - RVal Cond, bool Assumption, - bool& isFeasible) { +const ValueState* CFRefCount::EvalAssume(GRExprEngine& Eng, + const ValueState* St, + RVal Cond, bool Assumption, + bool& isFeasible) { // FIXME: We may add to the interface of EvalAssume the list of symbols // whose assumptions have changed. For now we just iterate through the @@ -2136,8 +2140,8 @@ PathDiagnosticPiece* CFRefReport::VisitNode(ExplodedNode<ValueState>* N, // Check if the type state has changed. - ValueState* PrevSt = PrevN->getState(); - ValueState* CurrSt = N->getState(); + const ValueState* PrevSt = PrevN->getState(); + const ValueState* CurrSt = N->getState(); CFRefCount::RefBindings PrevB = CFRefCount::GetRefBindings(*PrevSt); CFRefCount::RefBindings CurrB = CFRefCount::GetRefBindings(*CurrSt); @@ -2275,7 +2279,7 @@ GetAllocationSite(ExplodedNode<ValueState>* N, SymbolID Sym) { VarDecl* FirstDecl = 0; while (N) { - ValueState* St = N->getState(); + const ValueState* St = N->getState(); RefBindings B = RefBindings((RefBindings::TreeTy*) St->CheckerState); if (!B.lookup(Sym)) diff --git a/lib/Analysis/GRCoreEngine.cpp b/lib/Analysis/GRCoreEngine.cpp index a4bb7fa631..548c4bf161 100644 --- a/lib/Analysis/GRCoreEngine.cpp +++ b/lib/Analysis/GRCoreEngine.cpp @@ -255,8 +255,8 @@ void GRCoreEngineImpl::HandlePostStmt(const PostStmt& L, CFGBlock* B, /// GenerateNode - Utility method to generate nodes, hook up successors, /// and add nodes to the worklist. -void GRCoreEngineImpl::GenerateNode(const ProgramPoint& Loc, void* State, - ExplodedNodeImpl* Pred) { +void GRCoreEngineImpl::GenerateNode(const ProgramPoint& Loc, const void* State, + ExplodedNodeImpl* Pred) { bool IsNew; ExplodedNodeImpl* Node = G->getNodeImpl(Loc, State, &IsNew); @@ -321,7 +321,7 @@ static inline ProgramPoint GetPostLoc(Stmt* S, ProgramPoint::Kind K) { } ExplodedNodeImpl* -GRStmtNodeBuilderImpl::generateNodeImpl(Stmt* S, void* State, +GRStmtNodeBuilderImpl::generateNodeImpl(Stmt* S, const void* State, ExplodedNodeImpl* Pred, ProgramPoint::Kind K) { @@ -342,7 +342,7 @@ GRStmtNodeBuilderImpl::generateNodeImpl(Stmt* S, void* State, return NULL; } -ExplodedNodeImpl* GRBranchNodeBuilderImpl::generateNodeImpl(void* State, +ExplodedNodeImpl* GRBranchNodeBuilderImpl::generateNodeImpl(const void* State, bool branch) { bool IsNew; @@ -374,7 +374,7 @@ GRBranchNodeBuilderImpl::~GRBranchNodeBuilderImpl() { ExplodedNodeImpl* GRIndirectGotoNodeBuilderImpl::generateNodeImpl(const Iterator& I, - void* St, + const void* St, bool isSink) { bool IsNew; @@ -399,7 +399,8 @@ GRIndirectGotoNodeBuilderImpl::generateNodeImpl(const Iterator& I, ExplodedNodeImpl* -GRSwitchNodeBuilderImpl::generateCaseStmtNodeImpl(const Iterator& I, void* St) { +GRSwitchNodeBuilderImpl::generateCaseStmtNodeImpl(const Iterator& I, + const void* St) { bool IsNew; @@ -418,7 +419,8 @@ GRSwitchNodeBuilderImpl::generateCaseStmtNodeImpl(const Iterator& I, void* St) { ExplodedNodeImpl* -GRSwitchNodeBuilderImpl::generateDefaultCaseNodeImpl(void* St, bool isSink) { +GRSwitchNodeBuilderImpl::generateDefaultCaseNodeImpl(const void* St, + bool isSink) { // Get the block for the default case. assert (Src->succ_rbegin() != Src->succ_rend()); @@ -448,7 +450,7 @@ GREndPathNodeBuilderImpl::~GREndPathNodeBuilderImpl() { if (!HasGeneratedNode) generateNodeImpl(Pred->State); } -ExplodedNodeImpl* GREndPathNodeBuilderImpl::generateNodeImpl(void* State) { +ExplodedNodeImpl* GREndPathNodeBuilderImpl::generateNodeImpl(const void* State){ HasGeneratedNode = true; bool IsNew; diff --git a/lib/Analysis/GRExprEngine.cpp b/lib/Analysis/GRExprEngine.cpp index c4eddb9993..96e7fae7e3 100644 --- a/lib/Analysis/GRExprEngine.cpp +++ b/lib/Analysis/GRExprEngine.cpp @@ -18,6 +18,8 @@ #include "clang/Basic/SourceManager.h" #include "llvm/Support/Streams.h" +#include "clang/Analysis/PathSensitive/BasicStore.h" + #ifndef NDEBUG #include "llvm/Support/GraphWriter.h" #include <sstream> @@ -44,7 +46,8 @@ GRExprEngine::GRExprEngine(CFG& cfg, Decl& CD, ASTContext& Ctx, G(CoreEngine.getGraph()), Liveness(L), Builder(NULL), - StateMgr(G.getContext(), G.getAllocator()), + StateMgr(G.getContext(), CreateBasicStoreManager(G.getAllocator()), + G.getAllocator()), BasicVals(StateMgr.getBasicValueFactory()), TF(NULL), // FIXME SymMgr(StateMgr.getSymbolManager()), @@ -127,7 +130,7 @@ void GRExprEngine::AddObjCMessageExprCheck(GRSimpleAPICheck* A) { MsgExprChecks.push_back(A); } -ValueState* GRExprEngine::getInitialState() { +const ValueState* GRExprEngine::getInitialState() { // The LiveVariables information already has a compilation of all VarDecls // used in the function. Iterate through this set, and "symbolicate" @@ -144,11 +147,11 @@ ValueState* GRExprEngine::getInitialState() { if (VarDecl* VD = dyn_cast<VarDecl>(SD)) { if (VD->hasGlobalStorage() || isa<ParmVarDecl>(VD)) { RVal X = RVal::GetSymbolValue(SymMgr, VD); - StateMgr.BindVar(StateImpl, VD, X); + StateMgr.SetRVal(StateImpl, lval::DeclVal(VD), X); } } else if (ImplicitParamDecl *IPD = dyn_cast<ImplicitParamDecl>(SD)) { RVal X = RVal::GetSymbolValue(SymMgr, IPD); - StateMgr.BindVar(StateImpl, IPD, X); + StateMgr.SetRVal(StateImpl, lval::DeclVal(IPD), X); } @@ -157,7 +160,8 @@ ValueState* GRExprEngine::getInitialState() { return StateMgr.getPersistentState(StateImpl); } -ValueState* GRExprEngine::SetRVal(ValueState* St, Expr* Ex, RVal V) { +const ValueState* GRExprEngine::SetRVal(const ValueState* St, Expr* Ex, + RVal V) { bool isBlkExpr = false; @@ -285,7 +289,7 @@ void GRExprEngine::Visit(Stmt* S, NodeTy* Pred, NodeSet& Dst) { break; } else if (B->getOpcode() == BinaryOperator::Comma) { - ValueState* St = GetState(Pred); + const ValueState* St = GetState(Pred); MakeNode(Dst, B, Pred, SetRVal(St, B, GetRVal(St, B->getRHS()))); break; } @@ -364,7 +368,7 @@ void GRExprEngine::Visit(Stmt* S, NodeTy* Pred, NodeSet& Dst) { case Stmt::StmtExprClass: { StmtExpr* SE = cast<StmtExpr>(S); - ValueState* St = GetState(Pred); + const ValueState* St = GetState(Pred); // FIXME: Not certain if we can have empty StmtExprs. If so, we should // probably just remove these from the CFG. @@ -420,7 +424,7 @@ void GRExprEngine::VisitLVal(Expr* Ex, NodeTy* Pred, NodeSet& Dst) { // Block entrance. (Update counters). //===----------------------------------------------------------------------===// -bool GRExprEngine::ProcessBlockEntrance(CFGBlock* B, ValueState*, +bool GRExprEngine::ProcessBlockEntrance(CFGBlock* B, const ValueState*, GRBlockCounter BC) { return BC.getNumVisited(B->getBlockID()) < 3; @@ -430,8 +434,9 @@ bool GRExprEngine::ProcessBlockEntrance(CFGBlock* B, ValueState*, // Branch processing. //===----------------------------------------------------------------------===// -ValueState* GRExprEngine::MarkBranch(ValueState* St, Stmt* Terminator, - bool branchTaken) { +const ValueState* GRExprEngine::MarkBranch(const ValueState* St, + Stmt* Terminator, + bool branchTaken) { switch (Terminator->getStmtClass()) { default: @@ -488,7 +493,8 @@ void GRExprEngine::ProcessBranch(Expr* Condition, Stmt* Term, BranchNodeBuilder& builder) { // Remove old bindings for subexpressions. - ValueState* PrevState = StateMgr.RemoveSubExprBindings(builder.getState()); + const ValueState* PrevState = + StateMgr.RemoveSubExprBindings(builder.getState()); // Check for NULL conditions; e.g. "for(;;)" if (!Condition) { @@ -523,7 +529,7 @@ void GRExprEngine::ProcessBranch(Expr* Condition, Stmt* Term, // Process the true branch. bool isFeasible = false; - ValueState* St = Assume(PrevState, V, true, isFeasible); + const ValueState* St = Assume(PrevState, V, true, isFeasible); if (isFeasible) builder.generateNode(MarkBranch(St, Term, true), true); @@ -545,7 +551,7 @@ void GRExprEngine::ProcessBranch(Expr* Condition, Stmt* Term, /// nodes by processing the 'effects' of a computed goto jump. void GRExprEngine::ProcessIndirectGoto(IndirectGotoNodeBuilder& builder) { - ValueState* St = builder.getState(); + const ValueState* St = builder.getState(); RVal V = GetRVal(St, builder.getTarget()); // Three possibilities: @@ -592,7 +598,7 @@ void GRExprEngine::VisitGuardedExpr(Expr* Ex, Expr* L, Expr* R, assert (Ex == CurrentStmt && getCFG().isBlkExpr(Ex)); - ValueState* St = GetState(Pred); + const ValueState* St = GetState(Pred); RVal X = GetBlkExprRVal(St, Ex); assert (X.isUndef()); @@ -613,7 +619,7 @@ void GRExprEngine::ProcessSwitch(SwitchNodeBuilder& builder) { typedef SwitchNodeBuilder::iterator iterator; - ValueState* St = builder.getState(); + const ValueState* St = builder.getState(); Expr* CondE = builder.getCondition(); RVal CondV = GetRVal(St, CondE); @@ -623,7 +629,7 @@ void GRExprEngine::ProcessSwitch(SwitchNodeBuilder& builder) { return; } - ValueState* DefaultSt = St; + const ValueState* DefaultSt = St; // While most of this can be assumed (such as the signedness), having it // just computed makes sure everything makes the same assumptions end-to-end. @@ -670,7 +676,7 @@ void GRExprEngine::ProcessSwitch(SwitchNodeBuilder& builder) { // Now "assume" that the case matches. bool isFeasible = false; - ValueState* StNew = Assume(St, Res, true, isFeasible); + const ValueState* StNew = Assume(St, Res, true, isFeasible); if (isFeasible) { builder.generateCaseStmtNode(I, StNew); @@ -720,7 +726,7 @@ void GRExprEngine::VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred, assert (B == CurrentStmt && getCFG().isBlkExpr(B)); - ValueState* St = GetState(Pred); + const ValueState* St = GetState(Pred); RVal X = GetBlkExprRVal(St, B); assert (X.isUndef()); @@ -748,7 +754,7 @@ void GRExprEngine::VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred, // the payoff is not likely to be large. Instead, we do eager evaluation. bool isFeasible = false; - ValueState* NewState = Assume(St, X, true, isFeasible); + const ValueState* NewState = Assume(St, X, true, isFeasible); if (isFeasible) MakeNode(Dst, B, Pred, @@ -778,7 +784,7 @@ void GRExprEngine::VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred, void GRExprEngine::VisitDeclRefExpr(DeclRefExpr* D, NodeTy* Pred, NodeSet& Dst, bool asLVal) { - ValueState* St = GetState(Pred); + const ValueState* St = GetState(Pred); RVal X = RVal::MakeVal(BasicVals, D); if (asLVal) @@ -814,7 +820,7 @@ void GRExprEngine::VisitArraySubscriptExpr(ArraySubscriptExpr* A, NodeTy* Pred, for (NodeSet::iterator I2=Tmp2.begin(), E2=Tmp2.end(); I2!=E2; ++I2) { - ValueState* St = GetState(*I2); + const ValueState* St = GetState(*I2); RVal BaseV = GetRVal(St, Base); RVal IdxV = GetRVal(St, Idx); @@ -853,7 +859,7 @@ void GRExprEngine::VisitMemberExpr(MemberExpr* M, NodeTy* Pred, VisitLVal(Base, Pred, Tmp); for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { - ValueState* St = GetState(*I); + const ValueState* St = GetState(*I); RVal BaseV = GetRVal(St, Base); RVal V = lval::FieldOffset::Make(BasicVals, GetRVal(St, Base), @@ -871,7 +877,7 @@ void GRExprEngine::VisitMemberExpr(MemberExpr* M, NodeTy* Pred, for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { - ValueState* St = GetState(*I); + const ValueState* St = GetState(*I); RVal BaseV = GetRVal(St, Base); if (LVal::IsLValType(Base->getType())) { @@ -900,7 +906,7 @@ void GRExprEngine::VisitMemberExpr(MemberExpr* M, NodeTy* Pred, } void GRExprEngine::EvalStore(NodeSet& Dst, Expr* Ex, NodeTy* Pred, - ValueState* St, RVal location, RVal Val) { + const ValueState* St, RVal location, RVal Val) { assert (Builder && "GRStmtNodeBuilder must be defined."); @@ -930,7 +936,8 @@ void GRExprEngine::EvalStore(NodeSet& Dst, Expr* Ex, NodeTy* Pred, } void GRExprEngine::EvalLoad(NodeSet& Dst, Expr* Ex, NodeTy* Pred, - ValueState* St, RVal location, bool CheckOnly) { + const ValueState* St, RVal location, + bool CheckOnly) { // Evaluate the location (checks for bad dereferences). @@ -958,9 +965,9 @@ void GRExprEngine::EvalLoad(NodeSet& Dst, Expr* Ex, NodeTy* Pred, Ex->getType()))); } -ValueState* GRExprEngine::EvalLocation(Expr* Ex, NodeTy* Pred, - ValueState* St, RVal location, - bool isLoad) { +const ValueState* GRExprEngine::EvalLocation(Expr* Ex, NodeTy* Pred, + const ValueState* St, + RVal location, bool isLoad) { // Check for loads/stores from/to undefined values. if (location.isUndef()) { @@ -990,12 +997,12 @@ ValueState* GRExprEngine::EvalLocation(Expr* Ex, NodeTy* Pred, // "Assume" that the pointer is not NULL. bool isFeasibleNotNull = false; - ValueState* StNotNull = Assume(St, LV, true, isFeasibleNotNull); + const ValueState* StNotNull = Assume(St, LV, true, isFeasibleNotNull); // "Assume" that the pointer is NULL. bool isFeasibleNull = false; - ValueState* StNull = Assume(St, LV, false, isFeasibleNull); + const ValueState* StNull = Assume(St, LV, false, isFeasibleNull); if (isFeasibleNull) { @@ -1053,7 +1060,7 @@ void GRExprEngine::VisitCall(CallExpr* CE, NodeTy* Pred, // Finally, evaluate the function call. for (NodeSet::iterator DI = DstTmp.begin(), DE = DstTmp.end(); DI!=DE; ++DI) { - ValueState* St = GetState(*DI); + const ValueState* St = GetState(*DI); RVal L = GetRVal(St, Callee); // FIXME: Add support for symbolic function calls (calls involving @@ -1246,7 +1253,7 @@ void GRExprEngine::VisitObjCMessageExprDispatchHelper(ObjCMessageExpr* ME, // FIXME: More logic for the processing the method call. - ValueState* St = GetState(Pred); + const ValueState* St = GetState(Pred); bool RaisesException = false; @@ -1391,7 +1398,7 @@ void GRExprEngine::VisitCast(Expr* CastE, Expr* Ex, NodeTy* Pred, NodeSet& Dst){ for (NodeSet::iterator I1 = S1.begin(), E1 = S1.end(); I1 != E1; ++I1) { NodeTy* N = *I1; - ValueState* St = GetState(N); + const ValueState* St = GetState(N); RVal V = GetRVal(St, Ex); // Unknown? @@ -1470,7 +1477,7 @@ void GRExprEngine::VisitDeclStmtAux(DeclStmt* DS, ScopedDecl* D, for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { - ValueState* St = GetState(*I); + const ValueState* St = GetState(*I); if (!Ex && VD->hasGlobalStorage()) { @@ -1601,7 +1608,7 @@ void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* Pred, for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { - ValueState* St = GetState(*I); + const ValueState* St = GetState(*I); RVal location = GetRVal(St, Ex); if (asLVal) @@ -1630,7 +1637,7 @@ void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* Pred, // For all other types, UnaryOperator::Real is an identity operation. assert (U->getType() == Ex->getType()); - ValueState* St = GetState(*I); + const ValueState* St = GetState(*I); MakeNode(Dst, U, *I, SetRVal(St, U, GetRVal(St, Ex))); } @@ -1653,7 +1660,7 @@ void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* Pred, // For all other types, UnaryOperator::Float returns 0. assert (Ex->getType()->isIntegerType()); - ValueState* St = GetState(*I); + const ValueState* St = GetState(*I); RVal X = NonLVal::MakeVal(BasicVals, 0, Ex->getType()); MakeNode(Dst, U, *I, SetRVal(St, U, X)); } @@ -1679,7 +1686,7 @@ void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* Pred, Visit(Ex, Pred, Tmp); for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { - ValueState* St = GetState(*I); + const ValueState* St = GetState(*I); MakeNode(Dst, U, *I, SetRVal(St, U, GetRVal(St, Ex))); } @@ -1694,7 +1701,7 @@ void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* Pred, VisitLVal(Ex, Pred, Tmp); for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { - ValueState* St = GetState(*I); + const ValueState* St = GetState(*I); RVal V = GetRVal(St, Ex); St = SetRVal(St, U, V); MakeNode(Dst, U, *I, St); @@ -1713,7 +1720,7 @@ void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* Pred, Visit(Ex, Pred, Tmp); for (NodeSet::iterator I=Tmp.begin(), E=Tmp.end(); I!=E; ++I) { - ValueState* St = GetState(*I); + const ValueState* St = GetState(*I); RVal V = GetRVal(St, Ex); if (V.isUnknownOrUndef()) { @@ -1771,7 +1778,7 @@ void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* Pred, return; uint64_t size = getContext().getTypeSize(T) / 8; - ValueState* St = GetState(Pred); + const ValueState* St = GetState(Pred); St = SetRVal(St, U, NonLVal::MakeVal(BasicVals, size, U->getType())); MakeNode(Dst, U, Pred, St); @@ -1788,7 +1795,7 @@ void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* Pred, for (NodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I!=E; ++I) { - ValueState* St = GetState(*I); + const ValueState* St = GetState(*I); RVal V1 = GetRVal(St, Ex); // Perform a load. @@ -1855,7 +1862,7 @@ void GRExprEngine::VisitAsmStmtHelperInputs(AsmStmt* A, // which interprets the inline asm and stores proper results in the // outputs. - ValueState* St = GetState(Pred); + const ValueState* St = GetState(Pred); for (AsmStmt::outputs_iterator OI = A->begin_outputs(), OE = A->end_outputs(); OI != OE; ++OI) { @@ -1949,7 +1956,7 @@ void GRExprEngine::VisitReturnStmt(ReturnStmt* S, NodeTy* Pred, NodeSet& Dst) { // Transfer functions: Binary operators. //===----------------------------------------------------------------------===// -bool GRExprEngine::CheckDivideZero(Expr* Ex, ValueState* St, +bool GRExprEngine::CheckDivideZero(Expr* Ex, const ValueState* St, NodeTy* Pred, RVal Denom) { // Divide by undefined? (potentially zero) @@ -1969,7 +1976,7 @@ bool GRExprEngine::CheckDivideZero(Expr* Ex, ValueState* St, // First, "assume" that the denominator is 0 or undefined. bool isFeasibleZero = false; - ValueState* ZeroSt = Assume(St, Denom, false, isFeasibleZero); + const ValueState* ZeroSt = Assume(St, Denom, false, isFeasibleZero); // Second, "assume" that the denominator cannot be 0. @@ -2018,7 +2025,7 @@ void GRExprEngine::VisitBinaryOperator(BinaryOperator* B, for (NodeSet::iterator I2=Tmp2.begin(), E2=Tmp2.end(); I2 != E2; ++I2) { - ValueState* St = GetState(*I2); + const ValueState* St = GetState(*I2); RVal RightV = GetRVal(St, RHS); BinaryOperator::Opcode Op = B->getOpcode(); @@ -2175,8 +2182,8 @@ void GRExprEngine::VisitBinaryOperator(BinaryOperator* B, // "Assume" logic. //===----------------------------------------------------------------------===// -ValueState* GRExprEngine::Assume(ValueState* St, LVal Cond, - bool Assumption, bool& isFeasible) { +const ValueState* GRExprEngine::Assume(const ValueState* St, LVal Cond, + bool Assumption, bool& isFeasible) { St = AssumeAux(St, Cond, Assumption, isFeasible); @@ -2184,8 +2191,8 @@ ValueState* GRExprEngine::Assume(ValueState* St, LVal Cond, : St; } -ValueState* GRExprEngine::AssumeAux(ValueState* St, LVal Cond, - bool Assumption, bool& isFeasible) { +const ValueState* GRExprEngine::AssumeAux(const ValueState* St, LVal Cond, + bool Assumption, bool& isFeasible) { switch (Cond.getSubKind()) { default: @@ -2224,8 +2231,8 @@ ValueState* GRExprEngine::AssumeAux(ValueState* St, LVal Cond, } } -ValueState* GRExprEngine::Assume(ValueState* St, NonLVal Cond, - bool Assumption, bool& isFeasible) { +const ValueState* GRExprEngine::Assume(const ValueState* St, NonLVal Cond, + bool Assumption, bool& isFeasible) { St = AssumeAux(St, Cond, Assumption, isFeasible); @@ -2233,8 +2240,8 @@ ValueState* GRExprEngine::Assume(ValueState* St, NonLVal Cond, : St; } -ValueState* GRExprEngine::AssumeAux(ValueState* St, NonLVal Cond, - bool Assumption, bool& isFeasible) { +const ValueState* GRExprEngine::AssumeAux(const ValueState* St, NonLVal Cond, + bool Assumption, bool& isFeasible) { switch (Cond.getSubKind()) { default: assert (false && "'Assume' not implemented for this NonLVal."); @@ -2272,9 +2279,9 @@ ValueState* GRExprEngine::AssumeAux(ValueState* St, NonLVal Cond, } } -ValueState* -GRExprEngine::AssumeSymNE(ValueState* St, SymbolID sym, - const llvm::APSInt& V, bool& isFeasible) { +const ValueState* GRExprEngine::AssumeSymNE(const ValueState* St, + SymbolID sym, const llvm::APSInt& V, + bool& isFeasible) { // First, determine if sym == X, where X != V. if (const llvm::APSInt* X = St->getSymVal(sym)) { @@ -2295,9 +2302,8 @@ GRExprEngine::AssumeSymNE(ValueState* St, SymbolID sym, return StateMgr.AddNE(St, sym, V); } -ValueState* -GRExprEngine::AssumeSymEQ(ValueState* St, SymbolID sym, - const llvm::APSInt& V, bool& isFeasible) { +const ValueState* GRExprEngine::AssumeSymEQ(const ValueState* St, SymbolID sym, + const llvm::APSInt& V, bool& isFeasible) { // First, determine if sym == X, where X != V. if (const llvm::APSInt* X = St->getSymVal(sym)) { @@ -2318,9 +2324,10 @@ GRExprEngine::AssumeSymEQ(ValueState* St, SymbolID sym, return StateMgr.AddEQ(St, sym, V); } -ValueState* -GRExprEngine::AssumeSymInt(ValueState* St, bool Assumption, - const SymIntConstraint& C, bool& isFeasible) { +const ValueState* GRExprEngine::AssumeSymInt(const ValueState* St, + bool Assumption, + const SymIntConstraint& C, + bool& isFeasible) { switch (C.getOpcode()) { default: diff --git a/lib/Analysis/GRSimpleVals.cpp b/lib/Analysis/GRSimpleVals.cpp index 926bcc8e58..7d7afe39af 100644 --- a/lib/Analysis/GRSimpleVals.cpp +++ b/lib/Analysis/GRSimpleVals.cpp @@ -265,9 +265,9 @@ namespace { struct VISIBILITY_HIDDEN FindUndefExpr { ValueStateManager& VM; - ValueState* St; + const ValueState* St; - FindUndefExpr(ValueStateManager& V, ValueState* S) : VM(V), St(S) {} + FindUndefExpr(ValueStateManager& V, const ValueState* S) : VM(V), St(S) {} Expr* FindExpr(Expr* Ex) { @@ -319,7 +319,7 @@ void UndefBranch::EmitWarnings(BugReporter& BR) { ExplodedNode<ValueState> *N = *(*I)->pred_begin(); ProgramPoint P = N->getLocation(); - ValueState* St = (*I)->getState(); + const ValueState* St = (*I)->getState(); if (PostStmt* PS = dyn_cast<PostStmt>(&P)) if (PS->getStmt() == Ex) @@ -652,7 +652,7 @@ void GRSimpleVals::EvalCall(ExplodedNodeSet<ValueState>& Dst, ExplodedNode<ValueState>* Pred) { ValueStateManager& StateMgr = Eng.getStateManager(); - ValueState* St = Builder.GetState(Pred); + const ValueState* St = Builder.GetState(Pred); // Invalidate all arguments passed in by reference (LVals). @@ -700,7 +700,7 @@ void GRSimpleVals::EvalObjCMessageExpr(ExplodedNodeSet<ValueState>& Dst, // We just invalidate all arguments passed in by references. ValueStateManager& StateMgr = Eng.getStateManager(); - ValueState* St = Builder.GetState(Pred); + const ValueState* St = Builder.GetState(Pred); for (ObjCMessageExpr::arg_iterator I = ME->arg_begin(), E = ME->arg_end(); I != E; ++I) { diff --git a/lib/Analysis/GRTransferFuncs.cpp b/lib/Analysis/GRTransferFuncs.cpp index 9c96e3d981..a31f8aaa1b 100644 --- a/lib/Analysis/GRTransferFuncs.cpp +++ b/lib/Analysis/GRTransferFuncs.cpp @@ -23,7 +23,7 @@ void GRTransferFuncs::EvalStore(ExplodedNodeSet<ValueState>& Dst, GRExprEngine& Eng, GRStmtNodeBuilder<ValueState>& Builder, Expr* E, ExplodedNode<ValueState>* Pred, - ValueState* St, RVal TargetLV, RVal Val) { + const ValueState* St, RVal TargetLV, RVal Val) { // This code basically matches the "safety-net" logic of GRExprEngine: // bind Val to TargetLV, and create a new node. We replicate it here diff --git a/lib/Analysis/ValueState.cpp b/lib/Analysis/ValueState.cpp index cc77edc826..72ff498adb 100644 --- a/lib/Analysis/ValueState.cpp +++ b/lib/Analysis/ValueState.cpp @@ -30,8 +30,8 @@ const llvm::APSInt* ValueState::getSymVal(SymbolID sym) const { return T ? *T : NULL; } -ValueState* -ValueStateManager::RemoveDeadBindings(ValueState* St, Stmt* Loc, +const ValueState* +ValueStateManager::RemoveDeadBindings(const ValueState* St, Stmt* Loc, const LiveVariables& Liveness, DeadSymbolsTy& DeadSymbols) { @@ -126,7 +126,7 @@ ValueStateManager::RemoveDeadBindings(ValueState* St, Stmt* Loc, for (ValueState::vb_iterator I = St->vb_begin(), E = St->vb_end(); I!=E ; ++I) if (!Marked.count(I.getKey())) { - NewSt.VarBindings = Remove(NewSt, I.getKey()); + NewSt.St = StMgr->Remove(NewSt.St, lval::DeclVal(I.getKey())); RVal X = I.getData(); @@ -160,77 +160,35 @@ ValueStateManager::RemoveDeadBindings(ValueState* St, Stmt* Loc, return getPersistentState(NewSt); } - -RVal ValueStateManager::GetRVal(ValueState* St, LVal LV, QualType T) { +const ValueState* ValueStateManager::SetRVal(const ValueState* St, LVal LV, + RVal V) { - if (isa<UnknownVal>(LV)) - return UnknownVal(); + Store OldStore = St->getStore(); + Store NewStore = StMgr->SetRVal(OldStore, LV, V); - assert (!isa<UndefinedVal>(LV)); + if (NewStore == OldStore) + return St; - switch (LV.getSubKind()) { - case lval::DeclValKind: { - ValueState::VarBindingsTy::data_type* T = - St->VarBindings.lookup(cast<lval::DeclVal>(LV).getDecl()); - - return T ? *T : UnknownVal(); - } - - // FIXME: We should limit how far a "ContentsOf" will go... - - case lval::SymbolValKind: { - - - // FIXME: This is a broken representation of memory, and is prone - // to crashing the analyzer when addresses to symbolic values are - // passed through casts. We need a better representation of symbolic - // memory (or just memory in general); probably we should do this - // as a plugin class (similar to GRTransferFuncs). - -#if 0 - const lval::SymbolVal& SV = cast<lval::SymbolVal>(LV); - assert (T.getTypePtr()); - - // Punt on "symbolic" function pointers. - if (T->isFunctionType()) - return UnknownVal(); + ValueState NewSt = *St; + NewSt.St = NewStore; + return getPersistentState(NewSt); +} - if (T->isPointerType()) - return lval::SymbolVal(SymMgr.getContentsOfSymbol(SV.getSymbol())); - else - return nonlval::SymbolVal(SymMgr.getContentsOfSymbol(SV.getSymbol())); -#endif - - return UnknownVal(); - } - - case lval::ConcreteIntKind: - // Some clients may call GetRVal with such an option simply because - // they are doing a quick scan through their LVals (potentially to - // invalidate their bindings). Just return Undefined. - return UndefinedVal(); - - case lval::ArrayOffsetKind: - case lval::FieldOffsetKind: - return UnknownVal(); - - case lval::FuncValKind: - return LV; - - case lval::StringLiteralValKind: - // FIXME: Implement better support for fetching characters from strings. - return UnknownVal(); - - default: - assert (false && "Invalid LVal."); - break; - } +const ValueState* ValueStateManager::Unbind(const ValueState* St, LVal LV) { + Store OldStore = St->getStore(); + Store NewStore = StMgr->Remove(OldStore, LV); - return UnknownVal(); + if (NewStore == OldStore) + return St; + + ValueState NewSt = *St; + NewSt.St = NewStore; + return getPersistentState(NewSt); } -ValueState* ValueStateManager::AddNE(ValueState* St, SymbolID sym, - const llvm::APSInt& V) { + +const ValueState* ValueStateManager::AddNE(const ValueState* St, SymbolID sym, + const llvm::APSInt& V) { // First, retrieve the NE-set associated with the given symbol. ValueState::ConstNotEqTy::data_type* T = St->ConstNotEq.lookup(sym); @@ -247,8 +205,8 @@ ValueState* ValueStateManager::AddNE(ValueState* St, SymbolID sym, return getPersistentState(NewSt); } -ValueState* ValueStateManager::AddEQ(ValueState* St, SymbolID sym, - const llvm::APSInt& V) { +const ValueState* ValueStateManager::AddEQ(const ValueState* St, SymbolID sym, + const llvm::APSInt& V) { // Create a new state with the old binding replaced. ValueState NewSt = *St; @@ -258,66 +216,17 @@ ValueState* ValueStateManager::AddEQ(ValueState* St, SymbolID sym, return getPersistentState(NewSt); } +const ValueState* ValueStateManager::getInitialState() { -ValueState* ValueStateManager::SetRVal(ValueState* St, LVal LV, RVal V) { - - switch (LV.getSubKind()) { - - case lval::DeclValKind: - return V.isUnknown() - ? UnbindVar(St, cast<lval::DeclVal>(LV).getDecl()) - : BindVar(St, cast<lval::DeclVal>(LV).getDecl(), V); - - default: - assert ("SetRVal for given LVal type not yet implemented."); - return St; - } -} - -void ValueStateManager::BindVar(ValueState& StImpl, VarDecl* D, RVal V) { - StImpl.VarBindings = VBFactory.Add(StImpl.VarBindings, D, V); -} - -ValueState* ValueStateManager::BindVar(ValueState* St, VarDecl* D, RVal V) { - - // Create a new state with the old binding removed. - ValueState NewSt = *St; - NewSt.VarBindings = VBFactory.Add(NewSt.VarBindings, D, V); - - // Get the persistent copy. - return getPersistentState(NewSt); -} - -ValueState* ValueStateManager::UnbindVar(ValueState* St, VarDecl* D) { - - // Create a new state with the old binding removed. - ValueState NewSt = *St; - NewSt.VarBindings = VBFactory.Remove(NewSt.VarBindings, D); - - // Get the persistent copy. - return getPersistentState(NewSt); -} - -void ValueStateManager::Unbind(ValueState& StImpl, LVal LV) { - - if (isa<lval::DeclVal>(LV)) - StImpl.VarBindings = VBFactory.Remove(StImpl.VarBindings, - cast<lval::DeclVal>(LV).getDecl()); - -} - -ValueState* ValueStateManager::getInitialState() { - - // Create a state with empty variable bindings. ValueState StateImpl(EnvMgr.getInitialEnvironment(), - VBFactory.GetEmptyMap(), + StMgr->getInitialStore(), CNEFactory.GetEmptyMap(), CEFactory.GetEmptyMap()); return getPersistentState(StateImpl); } -ValueState* ValueStateManager::getPersistentState(ValueState& State) { +const ValueState* ValueStateManager::getPersistentState(ValueState& State) { llvm::FoldingSetNodeID ID; State.Profile(ID); |