From 016f52fe934394f7b6a68d35e698acaf23c6a1e5 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Fri, 8 Feb 2008 21:10:02 +0000 Subject: [PATCH] Split off expression-bindings in ValueState from variable-bindings. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@46892 91177308-0d34-0410-b5e6-96231b3b80d8 --- Analysis/GRConstants.cpp | 56 +++++++++++-------- Analysis/ValueState.cpp | 113 ++++++++++++++++++++++++--------------- Analysis/ValueState.h | 93 +++++++++++--------------------- 3 files changed, 135 insertions(+), 127 deletions(-) diff --git a/Analysis/GRConstants.cpp b/Analysis/GRConstants.cpp index cc8f75cf6f..eba0619b24 100644 --- a/Analysis/GRConstants.cpp +++ b/Analysis/GRConstants.cpp @@ -351,7 +351,7 @@ void GRConstants::ProcessBranch(Expr* Condition, Stmt* Term, StateTy PrevState = builder.getState(); // Remove old bindings for subexpressions. - for (StateTy::vb_iterator I=PrevState.begin(), E=PrevState.end(); I!=E; ++I) + for (StateTy::eb_iterator I=PrevState.eb_begin(), E=PrevState.eb_end(); I!=E; ++I) if (I.getKey().isSubExpr()) PrevState = StateMgr.Remove(PrevState, I.getKey()); @@ -1123,38 +1123,52 @@ struct VISIBILITY_HIDDEN DOTGraphTraits : static void PrintKindLabel(std::ostream& Out, ExprBindKey::Kind kind) { switch (kind) { case ExprBindKey::IsSubExpr: Out << "Sub-Expressions:\\l"; break; - case ExprBindKey::IsDecl: Out << "Variables:\\l"; break; case ExprBindKey::IsBlkExpr: Out << "Block-level Expressions:\\l"; break; default: assert (false && "Unknown ExprBindKey type."); } } - static void PrintKind(std::ostream& Out, GRConstants::StateTy M, - ExprBindKey::Kind kind, bool isFirstGroup = false) { + + static void PrintVarBindings(std::ostream& Out, GRConstants::StateTy St) { + + Out << "Variables:\\l"; + bool isFirst = true; - for (GRConstants::StateTy::vb_iterator I=M.begin(), E=M.end();I!=E;++I) { + for (GRConstants::StateTy::vb_iterator I=St.vb_begin(), + E=St.vb_end(); I!=E;++I) { + + if (isFirst) + isFirst = false; + else + Out << "\\l"; + + Out << ' ' << I.getKey()->getName() << " : "; + I.getData().print(Out); + } + + } + + static void PrintExprBindings(std::ostream& Out, GRConstants::StateTy St, + ExprBindKey::Kind kind) { + bool isFirst = true; + + for (GRConstants::StateTy::eb_iterator I=St.eb_begin(), + E=St.eb_end(); I!=E;++I) { + if (I.getKey().getKind() != kind) continue; if (isFirst) { - if (!isFirstGroup) Out << "\\l\\l"; + Out << "\\l\\l"; PrintKindLabel(Out, kind); isFirst = false; } else Out << "\\l"; - - Out << ' '; - - if (ValueDecl* V = dyn_cast(I.getKey())) - Out << V->getName(); - else { - Stmt* E = cast(I.getKey()); - Out << " (" << (void*) E << ") "; - E->printPretty(Out); - } - + + Out << " (" << (void*) I.getKey().getExpr() << ") "; + I.getKey().getExpr()->printPretty(Out); Out << " : "; I.getData().print(Out); } @@ -1260,10 +1274,10 @@ struct VISIBILITY_HIDDEN DOTGraphTraits : } Out << "\\|StateID: " << (void*) N->getState().getImpl() << "\\|"; - - PrintKind(Out, N->getState(), ExprBindKey::IsDecl, true); - PrintKind(Out, N->getState(), ExprBindKey::IsBlkExpr); - PrintKind(Out, N->getState(), ExprBindKey::IsSubExpr); + + PrintVarBindings(Out, N->getState()); + PrintExprBindings(Out, N->getState(), ExprBindKey::IsBlkExpr); + PrintExprBindings(Out, N->getState(), ExprBindKey::IsSubExpr); PrintEQ(Out, N->getState()); PrintNE(Out, N->getState()); diff --git a/Analysis/ValueState.cpp b/Analysis/ValueState.cpp index 5f42e11e7a..6a9023af64 100644 --- a/Analysis/ValueState.cpp +++ b/Analysis/ValueState.cpp @@ -43,34 +43,34 @@ ValueStateManager::RemoveDeadBindings(ValueState St, Stmt* Loc, // for optimum performance. llvm::SmallVector WList; - - for (StateTy::vb_iterator I = St.begin(), E = St.end(); I!=E ; ++I) { + + for (StateTy::eb_iterator I = St.eb_begin(), E = St.eb_end(); I!=E ; ++I) { + + ExprBindKey K = I.getKey(); // Remove old bindings for subexpressions. - if (I.getKey().isSubExpr()) { - St = Remove(St, I.getKey()); + if (K.isSubExpr()) { + St = Remove(St, K); continue; } - if (I.getKey().isBlkExpr()) { - if (Liveness.isLive(Loc, cast(I.getKey()))) { - if (isa(I.getData())) { - lval::DeclVal LV = cast(I.getData()); - WList.push_back(LV.getDecl()); - } + assert (I.getKey().isBlkExpr()); + + if (Liveness.isLive(Loc, K.getExpr())) { + if (isa(I.getData())) { + lval::DeclVal LV = cast(I.getData()); + WList.push_back(LV.getDecl()); } - else - St = Remove(St, I.getKey()); - - continue; } + else + St = Remove(St, K); - assert (I.getKey().isDecl()); - - if (VarDecl* V = dyn_cast(cast(I.getKey()))) - if (Liveness.isLive(Loc, V)) - WList.push_back(V); + continue; } + + for (StateTy::vb_iterator I = St.vb_begin(), E = St.vb_end(); I!=E ; ++I) + if (Liveness.isLive(Loc, I.getKey())) + WList.push_back(I.getKey()); llvm::SmallPtrSet Marked; @@ -94,11 +94,9 @@ ValueStateManager::RemoveDeadBindings(ValueState St, Stmt* Loc, } } - for (StateTy::vb_iterator I = St.begin(), E = St.end(); I!=E ; ++I) - if (I.getKey().isDecl()) - if (VarDecl* V = dyn_cast(cast(I.getKey()))) - if (!Marked.count(V)) - St = Remove(St, V); + for (StateTy::vb_iterator I = St.vb_begin(), E = St.vb_end(); I!=E ; ++I) + if (!Marked.count(I.getKey())) + St = Remove(St, I.getKey()); return St; } @@ -112,7 +110,9 @@ RValue ValueStateManager::GetValue(const StateTy& St, const LValue& LV, switch (LV.getSubKind()) { case lval::DeclValKind: { StateTy::VarBindingsTy::TreeTy* T = - St.getImpl()->VarBindings.SlimFind(cast(LV).getDecl()); + // FIXME: We should make lval::DeclVal only contain VarDecl + St.getImpl()->VarBindings.SlimFind( + cast(cast(LV).getDecl())); return T ? T->getValue().second : UnknownVal(); } @@ -222,8 +222,8 @@ RValue ValueStateManager::GetValue(const StateTy& St, Expr* S, bool* hasVal) { break; } - StateTy::VarBindingsTy::TreeTy* T = - St.getImpl()->VarBindings.SlimFind(S); + StateTy::ExprBindingsTy::TreeTy* T = + St.getImpl()->ExprBindings.SlimFind(S); if (T) { if (hasVal) *hasVal = true; @@ -235,28 +235,28 @@ RValue ValueStateManager::GetValue(const StateTy& St, Expr* S, bool* hasVal) { } } -LValue ValueStateManager::GetLValue(const StateTy& St, Expr* S) { +LValue ValueStateManager::GetLValue(const StateTy& St, Expr* E) { - while (ParenExpr* P = dyn_cast(S)) - S = P->getSubExpr(); + while (ParenExpr* P = dyn_cast(E)) + E = P->getSubExpr(); - if (DeclRefExpr* DR = dyn_cast(S)) + if (DeclRefExpr* DR = dyn_cast(E)) return lval::DeclVal(DR->getDecl()); - if (UnaryOperator* U = dyn_cast(S)) + if (UnaryOperator* U = dyn_cast(E)) if (U->getOpcode() == UnaryOperator::Deref) return cast(GetValue(St, U->getSubExpr())); - return cast(GetValue(St, S)); + return cast(GetValue(St, E)); } ValueStateManager::StateTy -ValueStateManager::SetValue(StateTy St, Expr* S, bool isBlkExpr, +ValueStateManager::SetValue(StateTy St, Expr* E, bool isBlkExpr, const RValue& V) { - assert (S); - return V.isKnown() ? Add(St, ExprBindKey(S, isBlkExpr), V) : St; + assert (E); + return V.isKnown() ? Add(St, ExprBindKey(E, isBlkExpr), V) : St; } ValueStateManager::StateTy @@ -264,8 +264,9 @@ ValueStateManager::SetValue(StateTy St, const LValue& LV, const RValue& V) { switch (LV.getSubKind()) { case lval::DeclValKind: - return V.isKnown() ? Add(St, cast(LV).getDecl(), V) - : Remove(St, cast(LV).getDecl()); + return V.isKnown() // FIXME: Have DeclVal only contain VarDecl + ? Add(St, cast(cast(LV).getDecl()), V) + : Remove(St, cast(cast(LV).getDecl())); default: assert ("SetValue for given LValue type not yet implemented."); @@ -273,36 +274,60 @@ ValueStateManager::SetValue(StateTy St, const LValue& LV, const RValue& V) { } } +ValueStateManager::StateTy +ValueStateManager::Add(StateTy St, ExprBindKey K, const RValue& V) { + + // Create a new state with the old binding removed. + ValueStateImpl NewStateImpl = *St.getImpl(); + NewStateImpl.ExprBindings = + EXFactory.Add(NewStateImpl.ExprBindings, K, V); + + // Get the persistent copy. + return getPersistentState(NewStateImpl); +} + ValueStateManager::StateTy ValueStateManager::Remove(StateTy St, ExprBindKey K) { + + // Create a new state with the old binding removed. + ValueStateImpl NewStateImpl = *St.getImpl(); + NewStateImpl.ExprBindings = + EXFactory.Remove(NewStateImpl.ExprBindings, K); + + // Get the persistent copy. + return getPersistentState(NewStateImpl); +} +ValueStateManager::StateTy +ValueStateManager::Add(StateTy St, VarDecl* D, const RValue& V) { + // Create a new state with the old binding removed. ValueStateImpl NewStateImpl = *St.getImpl(); NewStateImpl.VarBindings = - VBFactory.Remove(NewStateImpl.VarBindings, K); - + VBFactory.Add(NewStateImpl.VarBindings, D, V); + // Get the persistent copy. return getPersistentState(NewStateImpl); } ValueStateManager::StateTy -ValueStateManager::Add(StateTy St, ExprBindKey K, const RValue& V) { +ValueStateManager::Remove(StateTy St, VarDecl* D) { // Create a new state with the old binding removed. ValueStateImpl NewStateImpl = *St.getImpl(); NewStateImpl.VarBindings = - VBFactory.Add(NewStateImpl.VarBindings, K, V); + VBFactory.Remove(NewStateImpl.VarBindings, D); // Get the persistent copy. return getPersistentState(NewStateImpl); } - ValueStateManager::StateTy ValueStateManager::getInitialState() { // Create a state with empty variable bindings. - ValueStateImpl StateImpl(VBFactory.GetEmptyMap(), + ValueStateImpl StateImpl(EXFactory.GetEmptyMap(), + VBFactory.GetEmptyMap(), CNEFactory.GetEmptyMap(), CEFactory.GetEmptyMap()); diff --git a/Analysis/ValueState.h b/Analysis/ValueState.h index 1e3730ff4b..3d7a2e6bef 100644 --- a/Analysis/ValueState.h +++ b/Analysis/ValueState.h @@ -39,30 +39,25 @@ namespace clang { -/// ExprBindKey - A variant smart pointer that wraps either a ValueDecl* or a -/// Stmt*. Use cast<> or dyn_cast<> to get actual pointer type class ExprBindKey { uintptr_t Raw; void operator=(const ExprBindKey& RHS); // Do not implement. + inline void* getPtr() const { + return reinterpret_cast(Raw & ~Mask); + } + public: - enum Kind { IsSubExpr=0x0, IsBlkExpr=0x1, IsDecl=0x2, // L-Value Bindings. - IsSymbol=0x3, // Symbol Bindings. - Mask=0x3 }; + enum Kind { IsSubExpr=0x0, IsBlkExpr=0x1, Mask=0x1 }; inline Kind getKind() const { return (Kind) (Raw & Mask); } - - inline void* getPtr() const { - return reinterpret_cast(Raw & ~Mask); - } - - ExprBindKey(const ValueDecl* VD) - : Raw(reinterpret_cast(VD) | IsDecl) { - assert(VD && "ValueDecl cannot be NULL."); + + inline Expr* getExpr() const { + return (Expr*) getPtr(); } - + ExprBindKey(Expr* E, bool isBlkExpr = false) : Raw(reinterpret_cast(E) | (isBlkExpr ? IsBlkExpr : IsSubExpr)){ assert(E && "Tracked statement cannot be NULL."); @@ -71,12 +66,6 @@ public: bool isSubExpr() const { return getKind() == IsSubExpr; } bool isBlkExpr() const { return getKind() == IsBlkExpr; } - - - - bool isDecl() const { return getKind() == IsDecl; } - bool isStmt() const { return getKind() <= IsBlkExpr; } - inline void Profile(llvm::FoldingSetNodeID& ID) const { ID.AddPointer(getPtr()); } @@ -101,7 +90,8 @@ public: namespace vstate { typedef llvm::ImmutableSet IntSetTy; - typedef llvm::ImmutableMap VarBindingsTy; + typedef llvm::ImmutableMap ExprBindingsTy; + typedef llvm::ImmutableMap VarBindingsTy; typedef llvm::ImmutableMap ConstantNotEqTy; typedef llvm::ImmutableMap ConstantEqTy; } @@ -115,20 +105,23 @@ private: void operator=(const ValueStateImpl& R) const; public: + vstate::ExprBindingsTy ExprBindings; vstate::VarBindingsTy VarBindings; vstate::ConstantNotEqTy ConstantNotEq; vstate::ConstantEqTy ConstantEq; /// This ctor is used when creating the first ValueStateImpl object. - ValueStateImpl(vstate::VarBindingsTy VB, + ValueStateImpl(vstate::ExprBindingsTy EB, + vstate::VarBindingsTy VB, vstate::ConstantNotEqTy CNE, vstate::ConstantEqTy CE) - : VarBindings(VB), ConstantNotEq(CNE), ConstantEq(CE) {} + : ExprBindings(EB), VarBindings(VB), ConstantNotEq(CNE), ConstantEq(CE) {} /// Copy ctor - We must explicitly define this or else the "Next" ptr /// in FoldingSetNode will also get copied. ValueStateImpl(const ValueStateImpl& RHS) : llvm::FoldingSetNode(), + ExprBindings(RHS.ExprBindings), VarBindings(RHS.VarBindings), ConstantNotEq(RHS.ConstantNotEq), ConstantEq(RHS.ConstantEq) {} @@ -138,6 +131,7 @@ public: /// Profile - Profile the contents of a ValueStateImpl object for use /// in a FoldingSet. static void Profile(llvm::FoldingSetNodeID& ID, const ValueStateImpl& V) { + V.ExprBindings.Profile(ID); V.VarBindings.Profile(ID); V.ConstantNotEq.Profile(ID); V.ConstantEq.Profile(ID); @@ -169,7 +163,8 @@ public: // Typedefs. typedef vstate::IntSetTy IntSetTy; - typedef vstate::VarBindingsTy VarBindingsTy; + typedef vstate::ExprBindingsTy ExprBindingsTy; + typedef vstate::VarBindingsTy VarBindingsTy; typedef vstate::ConstantNotEqTy ConstantNotEqTy; typedef vstate::ConstantEqTy ConstantEqTy; @@ -183,8 +178,12 @@ public: // Iterators. typedef VarBindingsTy::iterator vb_iterator; - vb_iterator begin() { return Data->VarBindings.begin(); } - vb_iterator end() { return Data->VarBindings.end(); } + vb_iterator vb_begin() { return Data->VarBindings.begin(); } + vb_iterator vb_end() { return Data->VarBindings.end(); } + + typedef ExprBindingsTy::iterator eb_iterator; + eb_iterator eb_begin() { return Data->ExprBindings.begin(); } + eb_iterator eb_end() { return Data->ExprBindings.end(); } // Profiling and equality testing. @@ -217,7 +216,8 @@ public: private: ValueState::IntSetTy::Factory ISetFactory; - ValueState::VarBindingsTy::Factory VBFactory; + ValueState::ExprBindingsTy::Factory EXFactory; + ValueState::VarBindingsTy::Factory VBFactory; ValueState::ConstantNotEqTy::Factory CNEFactory; ValueState::ConstantEqTy::Factory CEFactory; @@ -255,11 +255,12 @@ public: RValue GetValue(const StateTy& St, const LValue& LV, QualType* T = NULL); LValue GetLValue(const StateTy& St, Expr* S); - - - StateTy Add(StateTy St, ExprBindKey K, const RValue& V); StateTy Remove(StateTy St, ExprBindKey K); + + StateTy Add(StateTy St, VarDecl* D, const RValue& V); + StateTy Remove(StateTy St, VarDecl* D); + StateTy getPersistentState(const ValueStateImpl& Impl); StateTy AddEQ(StateTy St, SymbolID sym, const llvm::APSInt& V); @@ -268,36 +269,4 @@ public: } // end clang namespace -//==------------------------------------------------------------------------==// -// Casting machinery to get cast<> and dyn_cast<> working with ExprBindKey. -//==------------------------------------------------------------------------==// - -namespace llvm { - - template<> inline bool - isa(const clang::ExprBindKey& V) { - return V.getKind() == clang::ExprBindKey::IsDecl; - } - - template<> inline bool - isa(const clang::ExprBindKey& V) { - return ((unsigned) V.getKind()) < clang::ExprBindKey::IsDecl; - } - - template<> struct cast_retty_impl { - typedef const clang::ValueDecl* ret_type; - }; - - template<> struct cast_retty_impl { - typedef const clang::Stmt* ret_type; - }; - - template<> struct simplify_type { - typedef void* SimpleType; - static inline SimpleType getSimplifiedValue(const clang::ExprBindKey &V) { - return V.getPtr(); - } - }; -} // end llvm namespace - #endif -- 2.50.1