From 6b3a0f72137570d5fd93a8919abe16cbc9359d31 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Tue, 11 Mar 2008 06:39:11 +0000 Subject: [PATCH] Added main skeleton for CFRetain transfer function logic. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@48214 91177308-0d34-0410-b5e6-96231b3b80d8 --- Analysis/CFRefCount.cpp | 279 ++++++++++++++++-- Analysis/CFRefCount.h | 39 --- Analysis/ValueState.cpp | 8 + .../clang/Analysis/PathSensitive/ValueState.h | 3 + 4 files changed, 270 insertions(+), 59 deletions(-) delete mode 100644 Analysis/CFRefCount.h diff --git a/Analysis/CFRefCount.cpp b/Analysis/CFRefCount.cpp index 72e085b4b2..93de1dcfd1 100644 --- a/Analysis/CFRefCount.cpp +++ b/Analysis/CFRefCount.cpp @@ -12,35 +12,188 @@ // //===----------------------------------------------------------------------===// -#include "CFRefCount.h" +#include "GRSimpleVals.h" #include "clang/Analysis/PathSensitive/ValueState.h" #include "clang/Basic/Diagnostic.h" #include "clang/Analysis/LocalCheckers.h" - +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/ImmutableMap.h" using namespace clang; +namespace { + enum ArgEffect { IncRef, DecRef, DoNothing }; + typedef std::vector ArgEffects; +} -namespace clang { +namespace llvm { + template <> struct FoldingSetTrait { + static void Profile(const ArgEffects& X, FoldingSetNodeID ID) { + for (ArgEffects::const_iterator I = X.begin(), E = X.end(); I!= E; ++I) + ID.AddInteger((unsigned) *I); + } + + static void Profile(ArgEffects& X, FoldingSetNodeID ID) { + Profile(X, ID); + } + }; +} // end llvm namespace + +namespace { + +class RetEffect { +public: + enum Kind { Alias = 0x0, OwnedSymbol = 0x1, NotOwnedSymbol = 0x2 }; + +private: + unsigned Data; + RetEffect(Kind k, unsigned D) { Data = (Data << 2) | (unsigned) k; } + +public: + + Kind getKind() const { return (Kind) (Data & 0x3); } + + unsigned getValue() const { + assert(getKind() == Alias); + return Data & ~0x3; + } + + static RetEffect MakeAlias(unsigned Idx) { return RetEffect(Alias, Idx); } + + static RetEffect MakeOwned() { return RetEffect(OwnedSymbol, 0); } + + static RetEffect MakeNotOwned() { return RetEffect(NotOwnedSymbol, 0); } + + operator Kind() const { return getKind(); } + + void Profile(llvm::FoldingSetNodeID& ID) const { ID.AddInteger(Data); } +}; + + +class CFRefSummary : public llvm::FoldingSetNode { + ArgEffects* Args; + RetEffect Ret; +public: + + CFRefSummary(ArgEffects* A, RetEffect R) : Args(A), Ret(R) {} + + unsigned getNumArgs() const { return Args->size(); } + + typedef ArgEffects::const_iterator arg_iterator; + + arg_iterator begin_args() const { return Args->begin(); } + arg_iterator end_args() const { return Args->end(); } -void CheckCFRefCount(CFG& cfg, FunctionDecl& FD, ASTContext& Ctx, - Diagnostic& Diag) { + static void Profile(llvm::FoldingSetNodeID& ID, ArgEffects* A, RetEffect R) { + ID.AddPointer(A); + ID.Add(R); + } + + void Profile(llvm::FoldingSetNodeID& ID) const { + Profile(ID, Args, Ret); + } +}; + - if (Diag.hasErrorOccurred()) - return; +class CFRefSummaryManager { + typedef llvm::FoldingSet > AESetTy; + typedef llvm::FoldingSet SummarySetTy; + typedef llvm::DenseMap SummaryMapTy; + + SummarySetTy SummarySet; + SummaryMapTy SummaryMap; + AESetTy AESet; + llvm::BumpPtrAllocator BPAlloc; + + ArgEffects ScratchArgs; + +public: + CFRefSummaryManager() {} + ~CFRefSummaryManager(); - // FIXME: Refactor some day so this becomes a single function invocation. + CFRefSummary* getSummary(FunctionDecl* FD); +}; + +} // end anonymous namespace + +//===----------------------------------------------------------------------===// +// Implementation of checker data structures. +//===----------------------------------------------------------------------===// + +CFRefSummaryManager::~CFRefSummaryManager() { - GRCoreEngine Engine(cfg, FD, Ctx); - GRExprEngine* CS = &Engine.getCheckerState(); - CFRefCount TF; - CS->setTransferFunctions(TF); - Engine.ExecuteWorkList(20000); + // FIXME: The ArgEffects could eventually be allocated from BPAlloc, + // mitigating the need to do explicit cleanup of the + // Argument-Effect summaries. + for (AESetTy::iterator I = AESet.begin(), E = AESet.end(); I!=E; ++I) + I->getValue().~ArgEffects(); } + +CFRefSummary* CFRefSummaryManager::getSummary(FunctionDecl* FD) { + + { // Look into our cache of summaries to see if we have already computed + // a summary for this FunctionDecl. + + SummaryMapTy::iterator I = SummaryMap.find(FD); + + if (I != SummaryMap.end()) + return I->second; + } + + // + + return NULL; } +//===----------------------------------------------------------------------===// +// Transfer functions. +//===----------------------------------------------------------------------===// + +typedef unsigned RefState; // FIXME + +namespace { + +class CFRefCount : public GRSimpleVals { + typedef llvm::ImmutableMap RefBindings; + typedef RefBindings::Factory RefBFactoryTy; + + CFRefSummaryManager Summaries; + RefBFactoryTy RefBFactory; + + static RefBindings GetRefBindings(ValueState& StImpl) { + return RefBindings((RefBindings::TreeTy*) StImpl.CheckerState); + } + + static void SetRefBindings(ValueState& StImpl, RefBindings B) { + StImpl.CheckerState = B.getRoot(); + } + + RefBindings Remove(RefBindings B, SymbolID sym) { + return RefBFactory.Remove(B, sym); + } + + RefBindings Update(RefBindings B, SymbolID sym, + CFRefSummary* Summ, unsigned ArgIdx); + +public: + CFRefCount() {} + virtual ~CFRefCount() {} + + // Calls. + + virtual void EvalCall(ExplodedNodeSet& Dst, + ValueStateManager& StateMgr, + GRStmtNodeBuilder& Builder, + BasicValueFactory& BasicVals, + CallExpr* CE, LVal L, + ExplodedNode* Pred); +}; + +} // end anonymous namespace + void CFRefCount::EvalCall(ExplodedNodeSet& Dst, ValueStateManager& StateMgr, GRStmtNodeBuilder& Builder, @@ -48,18 +201,104 @@ void CFRefCount::EvalCall(ExplodedNodeSet& Dst, CallExpr* CE, LVal L, ExplodedNode* Pred) { - ValueState* St = Pred->getState(); + // FIXME: Support calls to things other than lval::FuncVal. At the very + // least we should stop tracking ref-state for ref-counted objects passed + // to these functions. + + assert (isa(L) && "Not yet implemented."); - // Invalidate all arguments passed in by reference (LVals). + // Get the summary. - for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); - I != E; ++I) { + lval::FuncVal FV = cast(L); + FunctionDecl* FD = FV.getDecl(); + CFRefSummary* Summ = Summaries.getSummary(FD); - RVal V = StateMgr.GetRVal(St, *I); + // Get the state. + + ValueState* St = Builder.GetState(Pred); + + // Evaluate the effects of the call. + + ValueState StVals = *St; + + if (!Summ) { + + // This function has no summary. Invalidate all reference-count state + // for arguments passed to this function, and also nuke the values of + // arguments passed-by-reference. + + ValueState StVals = *St; - if (isa(V)) - St = StateMgr.SetRVal(St, cast(V), UnknownVal()); + for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end(); + I != E; ++I) { + + RVal V = StateMgr.GetRVal(St, *I); + + if (isa(V)) { + SymbolID Sym = cast(V).getSymbol(); + RefBindings B = GetRefBindings(StVals); + SetRefBindings(StVals, Remove(B, Sym)); + } + + if (isa(V)) + StateMgr.Unbind(StVals, cast(V)); + } } + else { + + // This function has a summary. Evaluate the effect of the arguments. + + unsigned idx = 0; + + for (CallExpr::arg_iterator I=CE->arg_begin(), E=CE->arg_end(); + I!=E; ++I, ++idx) { + + RVal V = StateMgr.GetRVal(St, *I); + + if (isa(V)) { + SymbolID Sym = cast(V).getSymbol(); + RefBindings B = GetRefBindings(StVals); + SetRefBindings(StVals, Update(B, Sym, Summ, idx)); + } + } + } + + St = StateMgr.getPersistentState(StVals); Builder.Nodify(Dst, CE, Pred, St); } + + +CFRefCount::RefBindings CFRefCount::Update(RefBindings B, SymbolID sym, + CFRefSummary* Summ, unsigned ArgIdx){ + + assert (Summ); + + // FIXME: Implement. + + return B; +} + +//===----------------------------------------------------------------------===// +// Driver for the CFRefCount Checker. +//===----------------------------------------------------------------------===// + +namespace clang { + + void CheckCFRefCount(CFG& cfg, FunctionDecl& FD, ASTContext& Ctx, + Diagnostic& Diag) { + + if (Diag.hasErrorOccurred()) + return; + + // FIXME: Refactor some day so this becomes a single function invocation. + + GRCoreEngine Engine(cfg, FD, Ctx); + GRExprEngine* CS = &Engine.getCheckerState(); + CFRefCount TF; + CS->setTransferFunctions(TF); + Engine.ExecuteWorkList(20000); + + } + +} // end clang namespace diff --git a/Analysis/CFRefCount.h b/Analysis/CFRefCount.h deleted file mode 100644 index 4a47881f6e..0000000000 --- a/Analysis/CFRefCount.h +++ /dev/null @@ -1,39 +0,0 @@ -// CFRefCount.h - Transfer functions for the CF Ref. Count checker -*- C++ -*--- -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines CFRefCount, which defines the transfer functions -// to implement the Core Foundation reference count checker. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_GRREFCOUNT -#define LLVM_CLANG_ANALYSIS_GRREFCOUNT - -#include "GRSimpleVals.h" - -namespace clang { - -class CFRefCount : public GRSimpleVals { -public: - CFRefCount() {} - virtual ~CFRefCount() {} - - // Calls. - - virtual void EvalCall(ExplodedNodeSet& Dst, - ValueStateManager& StateMgr, - GRStmtNodeBuilder& Builder, - BasicValueFactory& BasicVals, - CallExpr* CE, LVal L, - ExplodedNode* Pred); -}; - -} // end clang namespace - -#endif diff --git a/Analysis/ValueState.cpp b/Analysis/ValueState.cpp index 4b097ee4a4..1d428f199b 100644 --- a/Analysis/ValueState.cpp +++ b/Analysis/ValueState.cpp @@ -442,6 +442,14 @@ ValueState* ValueStateManager::UnbindVar(ValueState* St, VarDecl* D) { return getPersistentState(NewSt); } +void ValueStateManager::Unbind(ValueState& StImpl, LVal LV) { + + if (isa(LV)) + StImpl.VarBindings = VBFactory.Remove(StImpl.VarBindings, + cast(LV).getDecl()); + +} + ValueState* ValueStateManager::getInitialState() { // Create a state with empty variable bindings. diff --git a/include/clang/Analysis/PathSensitive/ValueState.h b/include/clang/Analysis/PathSensitive/ValueState.h index a2ebe147e7..8cd8f511e8 100644 --- a/include/clang/Analysis/PathSensitive/ValueState.h +++ b/include/clang/Analysis/PathSensitive/ValueState.h @@ -234,6 +234,9 @@ public: RVal GetBlkExprRVal(ValueState* St, Expr* Ex); void BindVar(ValueState& StImpl, VarDecl* D, RVal V); + + void Unbind(ValueState& StImpl, LVal LV); + ValueState* getPersistentState(ValueState& Impl); ValueState* AddEQ(ValueState* St, SymbolID sym, const llvm::APSInt& V); -- 2.40.0