Make a major restructuring of the clang tree: introduce a top-level
lib dir and move all the libraries into it. This follows the main
llvm tree, and allows the libraries to be built in parallel. The
top level now enforces that all the libs are built before Driver,
but we don't care what order the libs are built in. This speeds
up parallel builds, particularly incremental ones.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@48402 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/BasicValueFactory.cpp b/lib/Analysis/BasicValueFactory.cpp
new file mode 100644
index 0000000..88b360d
--- /dev/null
+++ b/lib/Analysis/BasicValueFactory.cpp
@@ -0,0 +1,167 @@
+//=== BasicValueFactory.cpp - Basic values for Path Sens analysis --*- 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 BasicValueFactory, a class that manages the lifetime
+// of APSInt objects and symbolic constraints used by GRExprEngine
+// and related classes.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/PathSensitive/BasicValueFactory.h"
+
+using namespace clang;
+
+BasicValueFactory::~BasicValueFactory() {
+ // Note that the dstor for the contents of APSIntSet will never be called,
+ // so we iterate over the set and invoke the dstor for each APSInt. This
+ // frees an aux. memory allocated to represent very large constants.
+ for (APSIntSetTy::iterator I=APSIntSet.begin(), E=APSIntSet.end(); I!=E; ++I)
+ I->getValue().~APSInt();
+}
+
+const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
+ llvm::FoldingSetNodeID ID;
+ void* InsertPos;
+ typedef llvm::FoldingSetNodeWrapper<llvm::APSInt> FoldNodeTy;
+
+ X.Profile(ID);
+ FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
+
+ if (!P) {
+ P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
+ new (P) FoldNodeTy(X);
+ APSIntSet.InsertNode(P, InsertPos);
+ }
+
+ return *P;
+}
+
+const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
+ bool isUnsigned) {
+ llvm::APSInt V(BitWidth, isUnsigned);
+ V = X;
+ return getValue(V);
+}
+
+const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
+
+ unsigned bits = Ctx.getTypeSize(T);
+ llvm::APSInt V(bits, T->isUnsignedIntegerType());
+ V = X;
+ return getValue(V);
+}
+
+const SymIntConstraint&
+BasicValueFactory::getConstraint(SymbolID sym, BinaryOperator::Opcode Op,
+ const llvm::APSInt& V) {
+
+ llvm::FoldingSetNodeID ID;
+ SymIntConstraint::Profile(ID, sym, Op, V);
+ void* InsertPos;
+
+ SymIntConstraint* C = SymIntCSet.FindNodeOrInsertPos(ID, InsertPos);
+
+ if (!C) {
+ C = (SymIntConstraint*) BPAlloc.Allocate<SymIntConstraint>();
+ new (C) SymIntConstraint(sym, Op, V);
+ SymIntCSet.InsertNode(C, InsertPos);
+ }
+
+ return *C;
+}
+
+const llvm::APSInt*
+BasicValueFactory::EvaluateAPSInt(BinaryOperator::Opcode Op,
+ const llvm::APSInt& V1, const llvm::APSInt& V2) {
+
+ switch (Op) {
+ default:
+ assert (false && "Invalid Opcode.");
+
+ case BinaryOperator::Mul:
+ return &getValue( V1 * V2 );
+
+ case BinaryOperator::Div:
+ return &getValue( V1 / V2 );
+
+ case BinaryOperator::Rem:
+ return &getValue( V1 % V2 );
+
+ case BinaryOperator::Add:
+ return &getValue( V1 + V2 );
+
+ case BinaryOperator::Sub:
+ return &getValue( V1 - V2 );
+
+ case BinaryOperator::Shl: {
+
+ // FIXME: This logic should probably go higher up, where we can
+ // test these conditions symbolically.
+
+ // FIXME: Expand these checks to include all undefined behavior.
+
+ if (V2.isSigned() && V2.isNegative())
+ return NULL;
+
+ uint64_t Amt = V2.getZExtValue();
+
+ if (Amt > V1.getBitWidth())
+ return NULL;
+
+ return &getValue( V1.operator<<( (unsigned) Amt ));
+ }
+
+ case BinaryOperator::Shr: {
+
+ // FIXME: This logic should probably go higher up, where we can
+ // test these conditions symbolically.
+
+ // FIXME: Expand these checks to include all undefined behavior.
+
+ if (V2.isSigned() && V2.isNegative())
+ return NULL;
+
+ uint64_t Amt = V2.getZExtValue();
+
+ if (Amt > V1.getBitWidth())
+ return NULL;
+
+ return &getValue( V1.operator>>( (unsigned) Amt ));
+ }
+
+ case BinaryOperator::LT:
+ return &getTruthValue( V1 < V2 );
+
+ case BinaryOperator::GT:
+ return &getTruthValue( V1 > V2 );
+
+ case BinaryOperator::LE:
+ return &getTruthValue( V1 <= V2 );
+
+ case BinaryOperator::GE:
+ return &getTruthValue( V1 >= V2 );
+
+ case BinaryOperator::EQ:
+ return &getTruthValue( V1 == V2 );
+
+ case BinaryOperator::NE:
+ return &getTruthValue( V1 != V2 );
+
+ // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
+
+ case BinaryOperator::And:
+ return &getValue( V1 & V2 );
+
+ case BinaryOperator::Or:
+ return &getValue( V1 | V2 );
+
+ case BinaryOperator::Xor:
+ return &getValue( V1 ^ V2 );
+ }
+}
diff --git a/lib/Analysis/CFRefCount.cpp b/lib/Analysis/CFRefCount.cpp
new file mode 100644
index 0000000..77bbba2
--- /dev/null
+++ b/lib/Analysis/CFRefCount.cpp
@@ -0,0 +1,796 @@
+// CFRefCount.cpp - Transfer functions for tracking simple 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 defines the methods for CFRefCount, which implements
+// a reference count checker for Core Foundation (Mac OS X).
+//
+//===----------------------------------------------------------------------===//
+
+#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"
+#include <ostream>
+
+using namespace clang;
+
+namespace {
+ enum ArgEffect { IncRef, DecRef, DoNothing };
+ typedef std::vector<ArgEffect> ArgEffects;
+}
+
+namespace llvm {
+ template <> struct FoldingSetTrait<ArgEffects> {
+ 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(); }
+
+ ArgEffect getArg(unsigned idx) const {
+ assert (idx < getNumArgs());
+ return (*Args)[idx];
+ }
+
+ RetEffect getRet() const {
+ return Ret;
+ }
+
+ typedef ArgEffects::const_iterator arg_iterator;
+
+ arg_iterator begin_args() const { return Args->begin(); }
+ arg_iterator end_args() const { return Args->end(); }
+
+ 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);
+ }
+};
+
+
+class CFRefSummaryManager {
+ typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<ArgEffects> > AESetTy;
+ typedef llvm::FoldingSet<CFRefSummary> SummarySetTy;
+ typedef llvm::DenseMap<FunctionDecl*, CFRefSummary*> SummaryMapTy;
+
+ SummarySetTy SummarySet;
+ SummaryMapTy SummaryMap;
+ AESetTy AESet;
+ llvm::BumpPtrAllocator BPAlloc;
+
+ ArgEffects ScratchArgs;
+
+
+ ArgEffects* getArgEffects();
+
+ CFRefSummary* getCannedCFSummary(FunctionTypeProto* FT, bool isRetain);
+
+ CFRefSummary* getCFSummary(FunctionDecl* FD, const char* FName);
+
+ CFRefSummary* getCFSummaryCreateRule(FunctionTypeProto* FT);
+ CFRefSummary* getCFSummaryGetRule(FunctionTypeProto* FT);
+
+ CFRefSummary* getPersistentSummary(ArgEffects* AE, RetEffect RE);
+
+public:
+ CFRefSummaryManager() {}
+ ~CFRefSummaryManager();
+
+ CFRefSummary* getSummary(FunctionDecl* FD, ASTContext& Ctx);
+};
+
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// Implementation of checker data structures.
+//===----------------------------------------------------------------------===//
+
+CFRefSummaryManager::~CFRefSummaryManager() {
+
+ // 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();
+}
+
+ArgEffects* CFRefSummaryManager::getArgEffects() {
+
+ assert (!ScratchArgs.empty());
+
+ llvm::FoldingSetNodeID profile;
+ profile.Add(ScratchArgs);
+ void* InsertPos;
+
+ llvm::FoldingSetNodeWrapper<ArgEffects>* E =
+ AESet.FindNodeOrInsertPos(profile, InsertPos);
+
+ if (E) {
+ ScratchArgs.clear();
+ return &E->getValue();
+ }
+
+ E = (llvm::FoldingSetNodeWrapper<ArgEffects>*)
+ BPAlloc.Allocate<llvm::FoldingSetNodeWrapper<ArgEffects> >();
+
+ new (E) llvm::FoldingSetNodeWrapper<ArgEffects>(ScratchArgs);
+ AESet.InsertNode(E, InsertPos);
+
+ ScratchArgs.clear();
+ return &E->getValue();
+}
+
+CFRefSummary* CFRefSummaryManager::getPersistentSummary(ArgEffects* AE,
+ RetEffect RE) {
+
+ llvm::FoldingSetNodeID profile;
+ CFRefSummary::Profile(profile, AE, RE);
+ void* InsertPos;
+
+ CFRefSummary* Summ = SummarySet.FindNodeOrInsertPos(profile, InsertPos);
+
+ if (Summ)
+ return Summ;
+
+ Summ = (CFRefSummary*) BPAlloc.Allocate<CFRefSummary>();
+ new (Summ) CFRefSummary(AE, RE);
+ SummarySet.InsertNode(Summ, InsertPos);
+
+ return Summ;
+}
+
+
+CFRefSummary* CFRefSummaryManager::getSummary(FunctionDecl* FD,
+ ASTContext& Ctx) {
+
+ SourceLocation Loc = FD->getLocation();
+
+ if (!Loc.isFileID())
+ return NULL;
+
+ { // 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;
+ }
+
+#if 0
+ SourceManager& SrcMgr = Ctx.getSourceManager();
+ unsigned fid = Loc.getFileID();
+ const FileEntry* FE = SrcMgr.getFileEntryForID(fid);
+
+ if (!FE)
+ return NULL;
+
+ const char* DirName = FE->getDir()->getName();
+ assert (DirName);
+ assert (strlen(DirName) > 0);
+
+ if (!strstr(DirName, "CoreFoundation")) {
+ SummaryMap[FD] = NULL;
+ return NULL;
+ }
+#endif
+
+ const char* FName = FD->getIdentifier()->getName();
+
+ if (FName[0] == 'C' && FName[1] == 'F') {
+ CFRefSummary* S = getCFSummary(FD, FName);
+ SummaryMap[FD] = S;
+ return S;
+ }
+
+ return NULL;
+}
+
+CFRefSummary* CFRefSummaryManager::getCFSummary(FunctionDecl* FD,
+ const char* FName) {
+
+ // For now, only generate summaries for functions that have a prototype.
+
+ FunctionTypeProto* FT =
+ dyn_cast<FunctionTypeProto>(FD->getType().getTypePtr());
+
+ if (!FT)
+ return NULL;
+
+ FName += 2;
+
+ if (strcmp(FName, "Retain") == 0)
+ return getCannedCFSummary(FT, true);
+
+ if (strcmp(FName, "Release") == 0)
+ return getCannedCFSummary(FT, false);
+
+ assert (ScratchArgs.empty());
+ bool usesCreateRule = false;
+
+ if (strstr(FName, "Create"))
+ usesCreateRule = true;
+
+ if (!usesCreateRule && strstr(FName, "Copy"))
+ usesCreateRule = true;
+
+ if (usesCreateRule)
+ return getCFSummaryCreateRule(FT);
+
+ if (strstr(FName, "Get"))
+ return getCFSummaryGetRule(FT);
+
+ return NULL;
+}
+
+CFRefSummary* CFRefSummaryManager::getCannedCFSummary(FunctionTypeProto* FT,
+ bool isRetain) {
+
+ if (FT->getNumArgs() != 1)
+ return NULL;
+
+ TypedefType* ArgT = dyn_cast<TypedefType>(FT->getArgType(0).getTypePtr());
+
+ if (!ArgT)
+ return NULL;
+
+ // For CFRetain/CFRelease, the first (and only) argument is of type
+ // "CFTypeRef".
+
+ const char* TDName = ArgT->getDecl()->getIdentifier()->getName();
+ assert (TDName);
+
+ if (strcmp("CFTypeRef", TDName) == 0)
+ return NULL;
+
+ if (!ArgT->isPointerType())
+ return NULL;
+
+ // Check the return type. It should also be "CFTypeRef".
+
+ QualType RetTy = FT->getResultType();
+
+ if (RetTy.getTypePtr() != ArgT)
+ return NULL;
+
+ // The function's interface checks out. Generate a canned summary.
+
+ assert (ScratchArgs.empty());
+ ScratchArgs.push_back(isRetain ? IncRef : DecRef);
+
+ return getPersistentSummary(getArgEffects(), RetEffect::MakeAlias(0));
+}
+
+static bool isCFRefType(QualType T) {
+
+ if (!T->isPointerType())
+ return false;
+
+ // Check the typedef for the name "CF" and the substring "Ref".
+
+ TypedefType* TD = dyn_cast<TypedefType>(T.getTypePtr());
+
+ if (!TD)
+ return false;
+
+ const char* TDName = TD->getDecl()->getIdentifier()->getName();
+ assert (TDName);
+
+ if (TDName[0] != 'C' || TDName[1] != 'F')
+ return false;
+
+ if (strstr(TDName, "Ref") == 0)
+ return false;
+
+ return true;
+}
+
+
+CFRefSummary*
+CFRefSummaryManager::getCFSummaryCreateRule(FunctionTypeProto* FT) {
+
+ if (!isCFRefType(FT->getResultType()))
+ return NULL;
+
+ assert (ScratchArgs.empty());
+
+ // FIXME: Add special-cases for functions that retain/release. For now
+ // just handle the default case.
+
+ for (unsigned i = 0, n = FT->getNumArgs(); i != n; ++i)
+ ScratchArgs.push_back(DoNothing);
+
+ return getPersistentSummary(getArgEffects(), RetEffect::MakeOwned());
+}
+
+CFRefSummary*
+CFRefSummaryManager::getCFSummaryGetRule(FunctionTypeProto* FT) {
+
+ if (!isCFRefType(FT->getResultType()))
+ return NULL;
+
+ assert (ScratchArgs.empty());
+
+ // FIXME: Add special-cases for functions that retain/release. For now
+ // just handle the default case.
+
+ for (unsigned i = 0, n = FT->getNumArgs(); i != n; ++i)
+ ScratchArgs.push_back(DoNothing);
+
+ return getPersistentSummary(getArgEffects(), RetEffect::MakeNotOwned());
+}
+
+//===----------------------------------------------------------------------===//
+// Transfer functions.
+//===----------------------------------------------------------------------===//
+
+namespace {
+
+class RefVal {
+ unsigned Data;
+
+ RefVal(unsigned K, unsigned D) : Data((D << 3) | K) {
+ assert ((K & ~0x5) == 0x0);
+ }
+
+ RefVal(unsigned K) : Data(K) {
+ assert ((K & ~0x5) == 0x0);
+ }
+
+public:
+ enum Kind { Owned = 0, AcqOwned = 1, NotOwned = 2, Released = 3,
+ ErrorUseAfterRelease = 4, ErrorReleaseNotOwned = 5 };
+
+
+ Kind getKind() const { return (Kind) (Data & 0x5); }
+
+ unsigned getCount() const {
+ assert (getKind() == Owned || getKind() == AcqOwned);
+ return Data >> 3;
+ }
+
+ static bool isError(Kind k) { return k >= ErrorUseAfterRelease; }
+
+ static RefVal makeOwned(unsigned Count) { return RefVal(Owned, Count); }
+ static RefVal makeAcqOwned(unsigned Count) { return RefVal(AcqOwned, Count); }
+ static RefVal makeNotOwned() { return RefVal(NotOwned); }
+ static RefVal makeReleased() { return RefVal(Released); }
+ static RefVal makeUseAfterRelease() { return RefVal(ErrorUseAfterRelease); }
+ static RefVal makeReleaseNotOwned() { return RefVal(ErrorReleaseNotOwned); }
+
+ bool operator==(const RefVal& X) const { return Data == X.Data; }
+ void Profile(llvm::FoldingSetNodeID& ID) const { ID.AddInteger(Data); }
+
+ void print(std::ostream& Out) const;
+};
+
+void RefVal::print(std::ostream& Out) const {
+ switch (getKind()) {
+ default: assert(false);
+ case Owned:
+ Out << "Owned(" << getCount() << ")";
+ break;
+
+ case AcqOwned:
+ Out << "Acquired-Owned(" << getCount() << ")";
+ break;
+
+ case NotOwned:
+ Out << "Not-Owned";
+ break;
+
+ case Released:
+ Out << "Released";
+ break;
+
+ case ErrorUseAfterRelease:
+ Out << "Use-After-Release [ERROR]";
+ break;
+
+ case ErrorReleaseNotOwned:
+ Out << "Release of Not-Owned [ERROR]";
+ break;
+ }
+}
+
+class CFRefCount : public GRSimpleVals {
+
+ // Type definitions.
+
+ typedef llvm::ImmutableMap<SymbolID, RefVal> RefBindings;
+ typedef RefBindings::Factory RefBFactoryTy;
+
+ typedef llvm::SmallPtrSet<GRExprEngine::NodeTy*,2> UseAfterReleasesTy;
+ typedef llvm::SmallPtrSet<GRExprEngine::NodeTy*,2> ReleasesNotOwnedTy;
+
+ class BindingsPrinter : public ValueState::CheckerStatePrinter {
+ public:
+ virtual void PrintCheckerState(std::ostream& Out, void* State,
+ const char* nl, const char* sep);
+ };
+
+ // Instance variables.
+
+ CFRefSummaryManager Summaries;
+ RefBFactoryTy RefBFactory;
+
+ UseAfterReleasesTy UseAfterReleases;
+ ReleasesNotOwnedTy ReleasesNotOwned;
+
+ BindingsPrinter Printer;
+
+ // Private methods.
+
+ 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, RefVal V, ArgEffect E,
+ RefVal::Kind& hasError);
+
+
+public:
+ CFRefCount() {}
+ virtual ~CFRefCount() {}
+
+ virtual ValueState::CheckerStatePrinter* getCheckerStatePrinter() {
+ return &Printer;
+ }
+
+ // Calls.
+
+ virtual void EvalCall(ExplodedNodeSet<ValueState>& Dst,
+ GRExprEngine& Eng,
+ GRStmtNodeBuilder<ValueState>& Builder,
+ CallExpr* CE, LVal L,
+ ExplodedNode<ValueState>* Pred);
+};
+
+} // end anonymous namespace
+
+void CFRefCount::BindingsPrinter::PrintCheckerState(std::ostream& Out,
+ void* State, const char* nl,
+ const char* sep) {
+ RefBindings B((RefBindings::TreeTy*) State);
+
+ if (State)
+ Out << sep << nl;
+
+ for (RefBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
+ Out << (*I).first << " : ";
+ (*I).second.print(Out);
+ Out << nl;
+ }
+}
+
+void CFRefCount::EvalCall(ExplodedNodeSet<ValueState>& Dst,
+ GRExprEngine& Eng,
+ GRStmtNodeBuilder<ValueState>& Builder,
+ CallExpr* CE, LVal L,
+ ExplodedNode<ValueState>* Pred) {
+
+ ValueStateManager& StateMgr = Eng.getStateManager();
+
+ // 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<lval::FuncVal>(L) && "Not yet implemented.");
+
+ // Get the summary.
+
+ lval::FuncVal FV = cast<lval::FuncVal>(L);
+ FunctionDecl* FD = FV.getDecl();
+ CFRefSummary* Summ = Summaries.getSummary(FD, Eng.getContext());
+
+ // Get the state.
+
+ ValueState* St = Builder.GetState(Pred);
+
+ // Evaluate the effects of the call.
+
+ ValueState StVals = *St;
+ RefVal::Kind hasError = (RefVal::Kind) 0;
+
+ 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;
+
+ for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();
+ I != E; ++I) {
+
+ RVal V = StateMgr.GetRVal(St, *I);
+
+ if (isa<lval::SymbolVal>(V)) {
+ SymbolID Sym = cast<lval::SymbolVal>(V).getSymbol();
+ RefBindings B = GetRefBindings(StVals);
+ SetRefBindings(StVals, Remove(B, Sym));
+ }
+
+ if (isa<LVal>(V))
+ StateMgr.Unbind(StVals, cast<LVal>(V));
+ }
+
+ St = StateMgr.getPersistentState(StVals);
+
+ // Make up a symbol for the return value of this function.
+
+ if (CE->getType() != Eng.getContext().VoidTy) {
+ unsigned Count = Builder.getCurrentBlockCount();
+ SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(CE, Count);
+
+ RVal X = CE->getType()->isPointerType()
+ ? cast<RVal>(lval::SymbolVal(Sym))
+ : cast<RVal>(nonlval::SymbolVal(Sym));
+
+ St = StateMgr.SetRVal(St, CE, X, Eng.getCFG().isBlkExpr(CE), false);
+ }
+
+ Builder.Nodify(Dst, CE, Pred, St);
+ return;
+ }
+
+ // 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<lval::SymbolVal>(V)) {
+ SymbolID Sym = cast<lval::SymbolVal>(V).getSymbol();
+ RefBindings B = GetRefBindings(StVals);
+
+ if (RefBindings::TreeTy* T = B.SlimFind(Sym)) {
+ B = Update(B, Sym, T->getValue().second, Summ->getArg(idx), hasError);
+ SetRefBindings(StVals, B);
+ if (hasError) break;
+ }
+ }
+ }
+
+ if (hasError) {
+ St = StateMgr.getPersistentState(StVals);
+ GRExprEngine::NodeTy* N = Builder.generateNode(CE, St, Pred);
+
+ if (N) {
+ N->markAsSink();
+
+ switch (hasError) {
+ default: assert(false);
+ case RefVal::ErrorUseAfterRelease:
+ UseAfterReleases.insert(N);
+ break;
+
+ case RefVal::ErrorReleaseNotOwned:
+ ReleasesNotOwned.insert(N);
+ break;
+ }
+ }
+
+ return;
+ }
+
+ // Finally, consult the summary for the return value.
+
+ RetEffect RE = Summ->getRet();
+ St = StateMgr.getPersistentState(StVals);
+
+
+ switch (RE.getKind()) {
+ default:
+ assert (false && "Unhandled RetEffect."); break;
+
+ case RetEffect::Alias: {
+ unsigned idx = RE.getValue();
+ assert (idx < CE->getNumArgs());
+ RVal V = StateMgr.GetRVal(St, CE->getArg(idx));
+ St = StateMgr.SetRVal(St, CE, V, Eng.getCFG().isBlkExpr(CE), false);
+ break;
+ }
+
+ case RetEffect::OwnedSymbol: {
+ unsigned Count = Builder.getCurrentBlockCount();
+ SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(CE, Count);
+
+ ValueState StImpl = *St;
+ RefBindings B = GetRefBindings(StImpl);
+ SetRefBindings(StImpl, RefBFactory.Add(B, Sym, RefVal::makeOwned(1)));
+
+ St = StateMgr.SetRVal(StateMgr.getPersistentState(StImpl),
+ CE, lval::SymbolVal(Sym),
+ Eng.getCFG().isBlkExpr(CE), false);
+
+ break;
+ }
+
+ case RetEffect::NotOwnedSymbol: {
+ unsigned Count = Builder.getCurrentBlockCount();
+ SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(CE, Count);
+
+ ValueState StImpl = *St;
+ RefBindings B = GetRefBindings(StImpl);
+ SetRefBindings(StImpl, RefBFactory.Add(B, Sym, RefVal::makeNotOwned()));
+
+ St = StateMgr.SetRVal(StateMgr.getPersistentState(StImpl),
+ CE, lval::SymbolVal(Sym),
+ Eng.getCFG().isBlkExpr(CE), false);
+
+ break;
+ }
+ }
+
+ Builder.Nodify(Dst, CE, Pred, St);
+}
+
+
+CFRefCount::RefBindings CFRefCount::Update(RefBindings B, SymbolID sym,
+ RefVal V, ArgEffect E,
+ RefVal::Kind& hasError) {
+
+ // FIXME: This dispatch can potentially be sped up by unifiying it into
+ // a single switch statement. Opt for simplicity for now.
+
+ switch (E) {
+ default:
+ assert (false && "Unhandled CFRef transition.");
+
+ case DoNothing:
+ if (V.getKind() == RefVal::Released) {
+ V = RefVal::makeUseAfterRelease();
+ hasError = V.getKind();
+ break;
+ }
+
+ return B;
+
+ case IncRef:
+ switch (V.getKind()) {
+ default:
+ assert(false);
+
+ case RefVal::Owned:
+ V = RefVal::makeOwned(V.getCount()+1); break;
+
+ case RefVal::AcqOwned:
+ V = RefVal::makeAcqOwned(V.getCount()+1);
+ break;
+
+ case RefVal::NotOwned:
+ V = RefVal::makeAcqOwned(1);
+ break;
+
+ case RefVal::Released:
+ V = RefVal::makeUseAfterRelease();
+ hasError = V.getKind();
+ break;
+ }
+
+ case DecRef:
+ switch (V.getKind()) {
+ default:
+ assert (false);
+
+ case RefVal::Owned: {
+ unsigned Count = V.getCount() - 1;
+ V = Count ? RefVal::makeOwned(Count) : RefVal::makeReleased();
+ break;
+ }
+
+ case RefVal::AcqOwned: {
+ unsigned Count = V.getCount() - 1;
+ V = Count ? RefVal::makeAcqOwned(Count) : RefVal::makeNotOwned();
+ break;
+ }
+
+ case RefVal::NotOwned:
+ V = RefVal::makeReleaseNotOwned();
+ hasError = V.getKind();
+ break;
+
+ case RefVal::Released:
+ V = RefVal::makeUseAfterRelease();
+ hasError = V.getKind();
+ break;
+ }
+ }
+
+ return RefBFactory.Add(B, sym, V);
+}
+
+//===----------------------------------------------------------------------===//
+// Driver for the CFRefCount Checker.
+//===----------------------------------------------------------------------===//
+
+namespace clang {
+
+ void CheckCFRefCount(CFG& cfg, Decl& CD, ASTContext& Ctx,
+ Diagnostic& Diag) {
+
+ if (Diag.hasErrorOccurred())
+ return;
+
+ // FIXME: Refactor some day so this becomes a single function invocation.
+
+ GRCoreEngine<GRExprEngine> Eng(cfg, CD, Ctx);
+ GRExprEngine* CS = &Eng.getCheckerState();
+ CFRefCount TF;
+ CS->setTransferFunctions(TF);
+ Eng.ExecuteWorkList(20000);
+
+ }
+
+} // end clang namespace
diff --git a/lib/Analysis/DeadStores.cpp b/lib/Analysis/DeadStores.cpp
new file mode 100644
index 0000000..0848336
--- /dev/null
+++ b/lib/Analysis/DeadStores.cpp
@@ -0,0 +1,87 @@
+//==- DeadStores.cpp - Check for stores to dead variables --------*- 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 a DeadStores, a flow-sensitive checker that looks for
+// stores to variables that are no longer live.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/LocalCheckers.h"
+#include "clang/Analysis/Analyses/LiveVariables.h"
+#include "clang/Analysis/Visitors/CFGRecStmtVisitor.h"
+#include "clang/Basic/Diagnostic.h"
+#include "clang/AST/ASTContext.h"
+#include "llvm/Support/Compiler.h"
+
+using namespace clang;
+
+namespace {
+
+class VISIBILITY_HIDDEN DeadStoreObs : public LiveVariables::ObserverTy {
+ ASTContext &Ctx;
+ Diagnostic &Diags;
+public:
+ DeadStoreObs(ASTContext &ctx,Diagnostic &diags) : Ctx(ctx), Diags(diags){}
+ virtual ~DeadStoreObs() {}
+
+ virtual void ObserveStmt(Stmt* S,
+ const LiveVariables::AnalysisDataTy& AD,
+ const LiveVariables::ValTy& Live) {
+
+ if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
+ if (!B->isAssignmentOp()) return; // Skip non-assignments.
+
+ if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()))
+ if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
+ if (VD->hasLocalStorage() && !Live(VD,AD)) {
+ SourceRange R = B->getRHS()->getSourceRange();
+ Diags.Report(Ctx.getFullLoc(DR->getSourceRange().getBegin()),
+ diag::warn_dead_store, 0, 0, &R, 1);
+ }
+ }
+ else if(DeclStmt* DS = dyn_cast<DeclStmt>(S))
+ // Iterate through the decls. Warn if any initializers are complex
+ // expressions that are not live (never used).
+ for (VarDecl* V = cast<VarDecl>(DS->getDecl()); V != NULL ;
+ V = cast_or_null<VarDecl>(V->getNextDeclarator())) {
+ if (V->hasLocalStorage())
+ if (Expr* E = V->getInit()) {
+ if (!Live(DS->getDecl(),AD)) {
+ // Special case: check for initializations with constants.
+ //
+ // e.g. : int x = 0;
+ //
+ // If x is EVER assigned a new value later, don't issue
+ // a warning. This is because such initialization can be
+ // due to defensive programming.
+ if (!E->isConstantExpr(Ctx,NULL)) {
+ // Flag a warning.
+ SourceRange R = E->getSourceRange();
+ Diags.Report(Ctx.getFullLoc(V->getLocation()),
+ diag::warn_dead_store, 0, 0, &R, 1);
+ }
+ }
+ }
+ }
+ }
+};
+
+} // end anonymous namespace
+
+namespace clang {
+
+void CheckDeadStores(CFG& cfg, ASTContext &Ctx, Diagnostic &Diags) {
+
+ LiveVariables L(cfg);
+ L.runOnCFG(cfg);
+ DeadStoreObs A(Ctx, Diags);
+ L.runOnAllBlocks(cfg, &A);
+}
+
+} // end namespace clang
diff --git a/lib/Analysis/ExplodedGraph.cpp b/lib/Analysis/ExplodedGraph.cpp
new file mode 100644
index 0000000..2ba46d7
--- /dev/null
+++ b/lib/Analysis/ExplodedGraph.cpp
@@ -0,0 +1,227 @@
+//=-- ExplodedGraph.cpp - Local, Path-Sens. "Exploded Graph" -*- 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 the template classes ExplodedNode and ExplodedGraph,
+// which represent a path-sensitive, intra-procedural "exploded graph."
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/PathSensitive/ExplodedGraph.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include <vector>
+#include <list>
+
+using namespace clang;
+
+
+static inline std::vector<ExplodedNodeImpl*>& getVector(void* P) {
+ return *reinterpret_cast<std::vector<ExplodedNodeImpl*>*>(P);
+}
+
+void ExplodedNodeImpl::NodeGroup::addNode(ExplodedNodeImpl* N) {
+
+ assert ((reinterpret_cast<uintptr_t>(N) & Mask) == 0x0);
+ assert (!getFlag());
+
+ if (getKind() == Size1) {
+ if (ExplodedNodeImpl* NOld = getNode()) {
+ std::vector<ExplodedNodeImpl*>* V = new std::vector<ExplodedNodeImpl*>();
+ assert ((reinterpret_cast<uintptr_t>(V) & Mask) == 0x0);
+ V->push_back(NOld);
+ V->push_back(N);
+ P = reinterpret_cast<uintptr_t>(V) | SizeOther;
+ assert (getPtr() == (void*) V);
+ assert (getKind() == SizeOther);
+ }
+ else {
+ P = reinterpret_cast<uintptr_t>(N);
+ assert (getKind() == Size1);
+ }
+ }
+ else {
+ assert (getKind() == SizeOther);
+ getVector(getPtr()).push_back(N);
+ }
+}
+
+
+unsigned ExplodedNodeImpl::NodeGroup::size() const {
+ if (getFlag())
+ return 0;
+
+ if (getKind() == Size1)
+ return getNode() ? 1 : 0;
+ else
+ return getVector(getPtr()).size();
+}
+
+ExplodedNodeImpl** ExplodedNodeImpl::NodeGroup::begin() const {
+ if (getFlag())
+ return NULL;
+
+ if (getKind() == Size1)
+ return (ExplodedNodeImpl**) (getPtr() ? &P : NULL);
+ else
+ return const_cast<ExplodedNodeImpl**>(&*(getVector(getPtr()).begin()));
+}
+
+ExplodedNodeImpl** ExplodedNodeImpl::NodeGroup::end() const {
+ if (getFlag())
+ return NULL;
+
+ if (getKind() == Size1)
+ return (ExplodedNodeImpl**) (getPtr() ? &P+1 : NULL);
+ else
+ return const_cast<ExplodedNodeImpl**>(&*(getVector(getPtr()).end()));
+}
+
+ExplodedNodeImpl::NodeGroup::~NodeGroup() {
+ if (getKind() == SizeOther) delete &getVector(getPtr());
+}
+
+ExplodedGraphImpl* ExplodedGraphImpl::Trim(ExplodedNodeImpl** BeginSources,
+ ExplodedNodeImpl** EndSources) const{
+
+ typedef llvm::DenseMap<ExplodedNodeImpl*, ExplodedNodeImpl*> Pass1Ty;
+ typedef llvm::DenseMap<ExplodedNodeImpl*, ExplodedNodeImpl*> Pass2Ty;
+
+ Pass1Ty Pass1;
+ Pass2Ty Pass2;
+
+ llvm::SmallVector<ExplodedNodeImpl*, 10> WL2;
+
+ { // ===- Pass 1 (reverse BFS) -===
+
+ // Enqueue the source nodes to the first worklist.
+
+ std::list<std::pair<ExplodedNodeImpl*, ExplodedNodeImpl*> > WL1;
+
+ for (ExplodedNodeImpl** I = BeginSources; I != EndSources; ++I)
+ WL1.push_back(std::make_pair(*I, *I));
+
+ // Process the worklist.
+
+ while (!WL1.empty()) {
+
+ ExplodedNodeImpl* N = WL1.back().first;
+ ExplodedNodeImpl* Src = WL1.back().second;
+
+ WL1.pop_back();
+
+ if (Pass1.find(N) != Pass1.end())
+ continue;
+
+ bool PredHasSameSource = false;
+ bool VisitPreds = true;
+
+ for (ExplodedNodeImpl** I=N->Preds.begin(), **E=N->Preds.end();
+ I!=E; ++I) {
+
+ Pass1Ty::iterator pi = Pass1.find(*I);
+
+ if (pi == Pass1.end())
+ continue;
+
+ VisitPreds = false;
+
+ if (pi->second == Src) {
+ PredHasSameSource = true;
+ break;
+ }
+ }
+
+ if (VisitPreds || !PredHasSameSource) {
+
+ Pass1[N] = Src;
+
+ if (N->Preds.empty()) {
+ WL2.push_back(N);
+ continue;
+ }
+ }
+ else
+ Pass1[N] = NULL;
+
+ if (VisitPreds)
+ for (ExplodedNodeImpl** I=N->Preds.begin(), **E=N->Preds.end();
+ I!=E; ++I)
+ WL1.push_front(std::make_pair(*I, Src));
+ }
+ }
+
+ if (WL2.empty())
+ return NULL;
+
+ ExplodedGraphImpl* G = MakeEmptyGraph();
+
+ // ===- Pass 2 (forward DFS to construct the new graph) -===
+
+ while (!WL2.empty()) {
+
+ ExplodedNodeImpl* N = WL2.back();
+ WL2.pop_back();
+
+ // Skip this node if we have already processed it.
+
+ if (Pass2.find(N) != Pass2.end())
+ continue;
+
+ // Create the corresponding node in the new graph.
+
+ ExplodedNodeImpl* NewN = G->getNodeImpl(N->getLocation(), N->State, NULL);
+ Pass2[N] = NewN;
+
+ if (N->Preds.empty())
+ G->addRoot(NewN);
+
+ // In the case that some of the intended predecessors of NewN have already
+ // been created, we should hook them up as predecessors.
+
+ for (ExplodedNodeImpl **I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I) {
+
+ Pass2Ty::iterator PI = Pass2.find(*I);
+
+ if (PI == Pass2.end())
+ continue;
+
+ NewN->addPredecessor(PI->second);
+ }
+
+ // In the case that some of the intended successors of NewN have already
+ // been created, we should hook them up as successors. Otherwise, enqueue
+ // the new nodes from the original graph that should have nodes created
+ // in the new graph.
+
+ for (ExplodedNodeImpl **I=N->Succs.begin(), **E=N->Succs.end(); I!=E; ++I) {
+
+ Pass2Ty::iterator PI = Pass2.find(*I);
+
+ if (PI != Pass2.end()) {
+ PI->second->addPredecessor(NewN);
+ continue;
+ }
+
+ // Enqueue nodes to the worklist that were marked during pass 1.
+
+ Pass1Ty::iterator pi = Pass1.find(*I);
+
+ if (pi == Pass1.end() || pi->second == NULL)
+ continue;
+
+ WL2.push_back(*I);
+ }
+
+ if (N->isSink())
+ NewN->markAsSink();
+ }
+
+ return G;
+}
diff --git a/lib/Analysis/GRBlockCounter.cpp b/lib/Analysis/GRBlockCounter.cpp
new file mode 100644
index 0000000..3ecc39d
--- /dev/null
+++ b/lib/Analysis/GRBlockCounter.cpp
@@ -0,0 +1,54 @@
+//==- GRBlockCounter.h - ADT for counting block visits -------------*- 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 GRBlockCounter, an abstract data type used to count
+// the number of times a given block has been visited along a path
+// analyzed by GRCoreEngine.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/PathSensitive/GRBlockCounter.h"
+#include "llvm/ADT/ImmutableMap.h"
+
+using namespace clang;
+
+typedef llvm::ImmutableMap<unsigned,unsigned> CountMap;
+
+static inline CountMap GetMap(void* D) {
+ return CountMap(static_cast<CountMap::TreeTy*>(D));
+}
+
+static inline CountMap::Factory& GetFactory(void* F) {
+ return *static_cast<CountMap::Factory*>(F);
+}
+
+unsigned GRBlockCounter::getNumVisited(unsigned BlockID) const {
+ CountMap M = GetMap(Data);
+ CountMap::TreeTy* T = M.SlimFind(BlockID);
+ return T ? T->getValue().second : 0;
+}
+
+GRBlockCounter::Factory::Factory(llvm::BumpPtrAllocator& Alloc) {
+ F = new CountMap::Factory(Alloc);
+}
+
+GRBlockCounter::Factory::~Factory() {
+ delete static_cast<CountMap::Factory*>(F);
+}
+
+GRBlockCounter
+GRBlockCounter::Factory::IncrementCount(GRBlockCounter BC, unsigned BlockID) {
+ return GRBlockCounter(GetFactory(F).Add(GetMap(BC.Data), BlockID,
+ BC.getNumVisited(BlockID)+1).getRoot());
+}
+
+GRBlockCounter
+GRBlockCounter::Factory::GetEmptyCounter() {
+ return GRBlockCounter(GetFactory(F).GetEmptyMap().getRoot());
+}
diff --git a/lib/Analysis/GRCoreEngine.cpp b/lib/Analysis/GRCoreEngine.cpp
new file mode 100644
index 0000000..53831ed
--- /dev/null
+++ b/lib/Analysis/GRCoreEngine.cpp
@@ -0,0 +1,444 @@
+//==- GRCoreEngine.cpp - Path-Sensitive Dataflow Engine ----------------*- 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 a generic engine for intraprocedural, path-sensitive,
+// dataflow analysis via graph reachability engine.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/PathSensitive/GRCoreEngine.h"
+#include "clang/AST/Expr.h"
+#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/ADT/DenseMap.h"
+#include <vector>
+
+using llvm::cast;
+using llvm::isa;
+using namespace clang;
+
+namespace {
+ class VISIBILITY_HIDDEN DFS : public GRWorkList {
+ llvm::SmallVector<GRWorkListUnit,20> Stack;
+public:
+ virtual bool hasWork() const {
+ return !Stack.empty();
+ }
+
+ virtual void Enqueue(const GRWorkListUnit& U) {
+ Stack.push_back(U);
+ }
+
+ virtual GRWorkListUnit Dequeue() {
+ assert (!Stack.empty());
+ const GRWorkListUnit& U = Stack.back();
+ Stack.pop_back(); // This technically "invalidates" U, but we are fine.
+ return U;
+ }
+};
+} // end anonymous namespace
+
+// Place the dstor for GRWorkList here because it contains virtual member
+// functions, and we the code for the dstor generated in one compilation unit.
+GRWorkList::~GRWorkList() {}
+
+GRWorkList* GRWorkList::MakeDFS() { return new DFS(); }
+
+/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
+bool GRCoreEngineImpl::ExecuteWorkList(unsigned Steps) {
+
+ if (G->num_roots() == 0) { // Initialize the analysis by constructing
+ // the root if none exists.
+
+ CFGBlock* Entry = &getCFG().getEntry();
+
+ assert (Entry->empty() &&
+ "Entry block must be empty.");
+
+ assert (Entry->succ_size() == 1 &&
+ "Entry block must have 1 successor.");
+
+ // Get the solitary successor.
+ CFGBlock* Succ = *(Entry->succ_begin());
+
+ // Construct an edge representing the
+ // starting location in the function.
+ BlockEdge StartLoc(getCFG(), Entry, Succ);
+
+ // Set the current block counter to being empty.
+ WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
+
+ // Generate the root.
+ GenerateNode(StartLoc, getInitialState());
+ }
+
+ while (Steps && WList->hasWork()) {
+ --Steps;
+ const GRWorkListUnit& WU = WList->Dequeue();
+
+ // Set the current block counter.
+ WList->setBlockCounter(WU.getBlockCounter());
+
+ // Retrieve the node.
+ ExplodedNodeImpl* Node = WU.getNode();
+
+ // Dispatch on the location type.
+ switch (Node->getLocation().getKind()) {
+ default:
+ assert (isa<BlockEdge>(Node->getLocation()));
+ HandleBlockEdge(cast<BlockEdge>(Node->getLocation()), Node);
+ break;
+
+ case ProgramPoint::BlockEntranceKind:
+ HandleBlockEntrance(cast<BlockEntrance>(Node->getLocation()), Node);
+ break;
+
+ case ProgramPoint::BlockExitKind:
+ assert (false && "BlockExit location never occur in forward analysis.");
+ break;
+
+ case ProgramPoint::PostStmtKind:
+ HandlePostStmt(cast<PostStmt>(Node->getLocation()), WU.getBlock(),
+ WU.getIndex(), Node);
+ break;
+ }
+ }
+
+ return WList->hasWork();
+}
+
+void GRCoreEngineImpl::HandleBlockEdge(const BlockEdge& L,
+ ExplodedNodeImpl* Pred) {
+
+ CFGBlock* Blk = L.getDst();
+
+ // Check if we are entering the EXIT block.
+ if (Blk == &getCFG().getExit()) {
+
+ assert (getCFG().getExit().size() == 0
+ && "EXIT block cannot contain Stmts.");
+
+ // Process the final state transition.
+ void* State = ProcessEOP(Blk, Pred->State);
+
+ bool IsNew;
+ ExplodedNodeImpl* Node = G->getNodeImpl(BlockEntrance(Blk), State, &IsNew);
+ Node->addPredecessor(Pred);
+
+ // If the node was freshly created, mark it as an "End-Of-Path" node.
+ if (IsNew) G->addEndOfPath(Node);
+
+ // This path is done. Don't enqueue any more nodes.
+ return;
+ }
+
+ // FIXME: Should we allow ProcessBlockEntrance to also manipulate state?
+
+ if (ProcessBlockEntrance(Blk, Pred->State, WList->getBlockCounter()))
+ GenerateNode(BlockEntrance(Blk), Pred->State, Pred);
+}
+
+void GRCoreEngineImpl::HandleBlockEntrance(const BlockEntrance& L,
+ ExplodedNodeImpl* Pred) {
+
+ // Increment the block counter.
+ GRBlockCounter Counter = WList->getBlockCounter();
+ Counter = BCounterFactory.IncrementCount(Counter, L.getBlock()->getBlockID());
+ WList->setBlockCounter(Counter);
+
+ // Process the entrance of the block.
+ if (Stmt* S = L.getFirstStmt()) {
+ GRStmtNodeBuilderImpl Builder(L.getBlock(), 0, Pred, this);
+ ProcessStmt(S, Builder);
+ }
+ else
+ HandleBlockExit(L.getBlock(), Pred);
+}
+
+
+void GRCoreEngineImpl::HandleBlockExit(CFGBlock * B, ExplodedNodeImpl* Pred) {
+
+ if (Stmt* Term = B->getTerminator()) {
+ switch (Term->getStmtClass()) {
+ default:
+ assert(false && "Analysis for this terminator not implemented.");
+ break;
+
+ case Stmt::BinaryOperatorClass: // '&&' and '||'
+ HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
+ return;
+
+ case Stmt::ConditionalOperatorClass:
+ HandleBranch(cast<ConditionalOperator>(Term)->getCond(), Term, B, Pred);
+ return;
+
+ // FIXME: Use constant-folding in CFG construction to simplify this
+ // case.
+
+ case Stmt::ChooseExprClass:
+ HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
+ return;
+
+ case Stmt::DoStmtClass:
+ HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
+ return;
+
+ case Stmt::ForStmtClass:
+ HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
+ return;
+
+ case Stmt::ContinueStmtClass:
+ case Stmt::BreakStmtClass:
+ case Stmt::GotoStmtClass:
+ break;
+
+ case Stmt::IfStmtClass:
+ HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
+ return;
+
+ case Stmt::IndirectGotoStmtClass: {
+ // Only 1 successor: the indirect goto dispatch block.
+ assert (B->succ_size() == 1);
+
+ GRIndirectGotoNodeBuilderImpl
+ builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
+ *(B->succ_begin()), this);
+
+ ProcessIndirectGoto(builder);
+ return;
+ }
+
+ case Stmt::SwitchStmtClass: {
+ GRSwitchNodeBuilderImpl builder(Pred, B,
+ cast<SwitchStmt>(Term)->getCond(),
+ this);
+
+ ProcessSwitch(builder);
+ return;
+ }
+
+ case Stmt::WhileStmtClass:
+ HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
+ return;
+ }
+ }
+
+ assert (B->succ_size() == 1 &&
+ "Blocks with no terminator should have at most 1 successor.");
+
+ GenerateNode(BlockEdge(getCFG(),B,*(B->succ_begin())), Pred->State, Pred);
+}
+
+void GRCoreEngineImpl::HandleBranch(Expr* Cond, Stmt* Term, CFGBlock * B,
+ ExplodedNodeImpl* Pred) {
+ assert (B->succ_size() == 2);
+
+ GRBranchNodeBuilderImpl Builder(B, *(B->succ_begin()), *(B->succ_begin()+1),
+ Pred, this);
+
+ ProcessBranch(Cond, Term, Builder);
+}
+
+void GRCoreEngineImpl::HandlePostStmt(const PostStmt& L, CFGBlock* B,
+ unsigned StmtIdx, ExplodedNodeImpl* Pred) {
+
+ assert (!B->empty());
+
+ if (StmtIdx == B->size())
+ HandleBlockExit(B, Pred);
+ else {
+ GRStmtNodeBuilderImpl Builder(B, StmtIdx, Pred, this);
+ ProcessStmt((*B)[StmtIdx], Builder);
+ }
+}
+
+typedef llvm::DenseMap<Stmt*,Stmt*> ParentMapTy;
+/// PopulateParentMap - Recurse the AST starting at 'Parent' and add the
+/// mappings between child and parent to ParentMap.
+static void PopulateParentMap(Stmt* Parent, ParentMapTy& M) {
+ for (Stmt::child_iterator I=Parent->child_begin(),
+ E=Parent->child_end(); I!=E; ++I) {
+
+ assert (M.find(*I) == M.end());
+ M[*I] = Parent;
+ PopulateParentMap(*I, M);
+ }
+}
+
+/// 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) {
+
+ bool IsNew;
+ ExplodedNodeImpl* Node = G->getNodeImpl(Loc, State, &IsNew);
+
+ if (Pred)
+ Node->addPredecessor(Pred); // Link 'Node' with its predecessor.
+ else {
+ assert (IsNew);
+ G->addRoot(Node); // 'Node' has no predecessor. Make it a root.
+ }
+
+ // Only add 'Node' to the worklist if it was freshly generated.
+ if (IsNew) WList->Enqueue(Node);
+}
+
+GRStmtNodeBuilderImpl::GRStmtNodeBuilderImpl(CFGBlock* b, unsigned idx,
+ ExplodedNodeImpl* N, GRCoreEngineImpl* e)
+ : Eng(*e), B(*b), Idx(idx), Pred(N), LastNode(N), Populated(false) {
+ Deferred.insert(N);
+}
+
+GRStmtNodeBuilderImpl::~GRStmtNodeBuilderImpl() {
+ for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
+ if (!(*I)->isSink())
+ GenerateAutoTransition(*I);
+}
+
+void GRStmtNodeBuilderImpl::GenerateAutoTransition(ExplodedNodeImpl* N) {
+ assert (!N->isSink());
+
+ PostStmt Loc(getStmt());
+
+ if (Loc == N->getLocation()) {
+ // Note: 'N' should be a fresh node because otherwise it shouldn't be
+ // a member of Deferred.
+ Eng.WList->Enqueue(N, B, Idx+1);
+ return;
+ }
+
+ bool IsNew;
+ ExplodedNodeImpl* Succ = Eng.G->getNodeImpl(Loc, N->State, &IsNew);
+ Succ->addPredecessor(N);
+
+ if (IsNew)
+ Eng.WList->Enqueue(Succ, B, Idx+1);
+}
+
+ExplodedNodeImpl* GRStmtNodeBuilderImpl::generateNodeImpl(Stmt* S, void* State,
+ ExplodedNodeImpl* Pred) {
+
+ bool IsNew;
+ ExplodedNodeImpl* N = Eng.G->getNodeImpl(PostStmt(S), State, &IsNew);
+ N->addPredecessor(Pred);
+ Deferred.erase(Pred);
+
+ HasGeneratedNode = true;
+
+ if (IsNew) {
+ Deferred.insert(N);
+ LastNode = N;
+ return N;
+ }
+
+ LastNode = NULL;
+ return NULL;
+}
+
+ExplodedNodeImpl* GRBranchNodeBuilderImpl::generateNodeImpl(void* State,
+ bool branch) {
+ bool IsNew;
+
+ ExplodedNodeImpl* Succ =
+ Eng.G->getNodeImpl(BlockEdge(Eng.getCFG(), Src, branch ? DstT : DstF),
+ State, &IsNew);
+
+ Succ->addPredecessor(Pred);
+
+ if (branch) GeneratedTrue = true;
+ else GeneratedFalse = true;
+
+ if (IsNew) {
+ Deferred.push_back(Succ);
+ return Succ;
+ }
+
+ return NULL;
+}
+
+GRBranchNodeBuilderImpl::~GRBranchNodeBuilderImpl() {
+ if (!GeneratedTrue) generateNodeImpl(Pred->State, true);
+ if (!GeneratedFalse) generateNodeImpl(Pred->State, false);
+
+ for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
+ if (!(*I)->isSink()) Eng.WList->Enqueue(*I);
+}
+
+
+ExplodedNodeImpl*
+GRIndirectGotoNodeBuilderImpl::generateNodeImpl(const Iterator& I,
+ void* St,
+ bool isSink) {
+ bool IsNew;
+
+ ExplodedNodeImpl* Succ =
+ Eng.G->getNodeImpl(BlockEdge(Eng.getCFG(), Src, I.getBlock(), true),
+ St, &IsNew);
+
+ Succ->addPredecessor(Pred);
+
+ if (IsNew) {
+
+ if (isSink)
+ Succ->markAsSink();
+ else
+ Eng.WList->Enqueue(Succ);
+
+ return Succ;
+ }
+
+ return NULL;
+}
+
+
+ExplodedNodeImpl*
+GRSwitchNodeBuilderImpl::generateCaseStmtNodeImpl(const Iterator& I, void* St) {
+
+ bool IsNew;
+
+ ExplodedNodeImpl* Succ = Eng.G->getNodeImpl(BlockEdge(Eng.getCFG(), Src,
+ I.getBlock()),
+ St, &IsNew);
+ Succ->addPredecessor(Pred);
+
+ if (IsNew) {
+ Eng.WList->Enqueue(Succ);
+ return Succ;
+ }
+
+ return NULL;
+}
+
+
+ExplodedNodeImpl*
+GRSwitchNodeBuilderImpl::generateDefaultCaseNodeImpl(void* St, bool isSink) {
+
+ // Get the block for the default case.
+ assert (Src->succ_rbegin() != Src->succ_rend());
+ CFGBlock* DefaultBlock = *Src->succ_rbegin();
+
+ bool IsNew;
+
+ ExplodedNodeImpl* Succ = Eng.G->getNodeImpl(BlockEdge(Eng.getCFG(), Src,
+ DefaultBlock),
+ St, &IsNew);
+ Succ->addPredecessor(Pred);
+
+ if (IsNew) {
+ if (isSink)
+ Succ->markAsSink();
+ else
+ Eng.WList->Enqueue(Succ);
+
+ return Succ;
+ }
+
+ return NULL;
+}
diff --git a/lib/Analysis/GRExprEngine.cpp b/lib/Analysis/GRExprEngine.cpp
new file mode 100644
index 0000000..f1108df
--- /dev/null
+++ b/lib/Analysis/GRExprEngine.cpp
@@ -0,0 +1,1941 @@
+//=-- GRExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- 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 a meta-engine for path-sensitive dataflow analysis that
+// is built on GREngine, but provides the boilerplate to execute transfer
+// functions and build the ExplodedGraph at the expression level.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/PathSensitive/GRExprEngine.h"
+#include "clang/Basic/SourceManager.h"
+#include "llvm/Support/Streams.h"
+
+#ifndef NDEBUG
+#include "llvm/Support/GraphWriter.h"
+#include <sstream>
+#endif
+
+// SaveAndRestore - A utility class that uses RIIA to save and restore
+// the value of a variable.
+template<typename T>
+struct VISIBILITY_HIDDEN SaveAndRestore {
+ SaveAndRestore(T& x) : X(x), old_value(x) {}
+ ~SaveAndRestore() { X = old_value; }
+ T get() { return old_value; }
+
+ T& X;
+ T old_value;
+};
+
+using namespace clang;
+using llvm::dyn_cast;
+using llvm::cast;
+using llvm::APSInt;
+
+
+ValueState* GRExprEngine::getInitialState() {
+
+ // The LiveVariables information already has a compilation of all VarDecls
+ // used in the function. Iterate through this set, and "symbolicate"
+ // any VarDecl whose value originally comes from outside the function.
+
+ typedef LiveVariables::AnalysisDataTy LVDataTy;
+ LVDataTy& D = Liveness.getAnalysisData();
+
+ ValueState StateImpl = *StateMgr.getInitialState();
+
+ for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
+
+ VarDecl* VD = cast<VarDecl>(const_cast<ScopedDecl*>(I->first));
+
+ if (VD->hasGlobalStorage() || isa<ParmVarDecl>(VD)) {
+ RVal X = RVal::GetSymbolValue(SymMgr, VD);
+ StateMgr.BindVar(StateImpl, VD, X);
+ }
+ }
+
+ return StateMgr.getPersistentState(StateImpl);
+}
+
+ValueState* GRExprEngine::SetRVal(ValueState* St, Expr* Ex, RVal V) {
+
+ bool isBlkExpr = false;
+
+ if (Ex == CurrentStmt) {
+ isBlkExpr = getCFG().isBlkExpr(Ex);
+
+ if (!isBlkExpr)
+ return St;
+ }
+
+ return StateMgr.SetRVal(St, Ex, V, isBlkExpr, false);
+}
+
+ValueState* GRExprEngine::MarkBranch(ValueState* St, Stmt* Terminator,
+ bool branchTaken) {
+
+ switch (Terminator->getStmtClass()) {
+ default:
+ return St;
+
+ case Stmt::BinaryOperatorClass: { // '&&' and '||'
+
+ BinaryOperator* B = cast<BinaryOperator>(Terminator);
+ BinaryOperator::Opcode Op = B->getOpcode();
+
+ assert (Op == BinaryOperator::LAnd || Op == BinaryOperator::LOr);
+
+ // For &&, if we take the true branch, then the value of the whole
+ // expression is that of the RHS expression.
+ //
+ // For ||, if we take the false branch, then the value of the whole
+ // expression is that of the RHS expression.
+
+ Expr* Ex = (Op == BinaryOperator::LAnd && branchTaken) ||
+ (Op == BinaryOperator::LOr && !branchTaken)
+ ? B->getRHS() : B->getLHS();
+
+ return SetBlkExprRVal(St, B, UndefinedVal(Ex));
+ }
+
+ case Stmt::ConditionalOperatorClass: { // ?:
+
+ ConditionalOperator* C = cast<ConditionalOperator>(Terminator);
+
+ // For ?, if branchTaken == true then the value is either the LHS or
+ // the condition itself. (GNU extension).
+
+ Expr* Ex;
+
+ if (branchTaken)
+ Ex = C->getLHS() ? C->getLHS() : C->getCond();
+ else
+ Ex = C->getRHS();
+
+ return SetBlkExprRVal(St, C, UndefinedVal(Ex));
+ }
+
+ case Stmt::ChooseExprClass: { // ?:
+
+ ChooseExpr* C = cast<ChooseExpr>(Terminator);
+
+ Expr* Ex = branchTaken ? C->getLHS() : C->getRHS();
+ return SetBlkExprRVal(St, C, UndefinedVal(Ex));
+ }
+ }
+}
+
+bool GRExprEngine::ProcessBlockEntrance(CFGBlock* B, ValueState*,
+ GRBlockCounter BC) {
+
+ return BC.getNumVisited(B->getBlockID()) < 3;
+}
+
+void GRExprEngine::ProcessBranch(Expr* Condition, Stmt* Term,
+ BranchNodeBuilder& builder) {
+
+ // Remove old bindings for subexpressions.
+ ValueState* PrevState = StateMgr.RemoveSubExprBindings(builder.getState());
+
+ // Check for NULL conditions; e.g. "for(;;)"
+ if (!Condition) {
+ builder.markInfeasible(false);
+ return;
+ }
+
+ RVal V = GetRVal(PrevState, Condition);
+
+ switch (V.getBaseKind()) {
+ default:
+ break;
+
+ case RVal::UnknownKind:
+ builder.generateNode(MarkBranch(PrevState, Term, true), true);
+ builder.generateNode(MarkBranch(PrevState, Term, false), false);
+ return;
+
+ case RVal::UndefinedKind: {
+ NodeTy* N = builder.generateNode(PrevState, true);
+
+ if (N) {
+ N->markAsSink();
+ UndefBranches.insert(N);
+ }
+
+ builder.markInfeasible(false);
+ return;
+ }
+ }
+
+
+ // Process the true branch.
+
+ bool isFeasible = false;
+ ValueState* St = Assume(PrevState, V, true, isFeasible);
+
+ if (isFeasible)
+ builder.generateNode(MarkBranch(St, Term, true), true);
+ else
+ builder.markInfeasible(true);
+
+ // Process the false branch.
+
+ isFeasible = false;
+ St = Assume(PrevState, V, false, isFeasible);
+
+ if (isFeasible)
+ builder.generateNode(MarkBranch(St, Term, false), false);
+ else
+ builder.markInfeasible(false);
+}
+
+/// ProcessIndirectGoto - Called by GRCoreEngine. Used to generate successor
+/// nodes by processing the 'effects' of a computed goto jump.
+void GRExprEngine::ProcessIndirectGoto(IndirectGotoNodeBuilder& builder) {
+
+ ValueState* St = builder.getState();
+ RVal V = GetRVal(St, builder.getTarget());
+
+ // Three possibilities:
+ //
+ // (1) We know the computed label.
+ // (2) The label is NULL (or some other constant), or Undefined.
+ // (3) We have no clue about the label. Dispatch to all targets.
+ //
+
+ typedef IndirectGotoNodeBuilder::iterator iterator;
+
+ if (isa<lval::GotoLabel>(V)) {
+ LabelStmt* L = cast<lval::GotoLabel>(V).getLabel();
+
+ for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) {
+ if (I.getLabel() == L) {
+ builder.generateNode(I, St);
+ return;
+ }
+ }
+
+ assert (false && "No block with label.");
+ return;
+ }
+
+ if (isa<lval::ConcreteInt>(V) || isa<UndefinedVal>(V)) {
+ // Dispatch to the first target and mark it as a sink.
+ NodeTy* N = builder.generateNode(builder.begin(), St, true);
+ UndefBranches.insert(N);
+ return;
+ }
+
+ // This is really a catch-all. We don't support symbolics yet.
+
+ assert (V.isUnknown());
+
+ for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
+ builder.generateNode(I, St);
+}
+
+/// ProcessSwitch - Called by GRCoreEngine. Used to generate successor
+/// nodes by processing the 'effects' of a switch statement.
+void GRExprEngine::ProcessSwitch(SwitchNodeBuilder& builder) {
+
+ typedef SwitchNodeBuilder::iterator iterator;
+
+ ValueState* St = builder.getState();
+ Expr* CondE = builder.getCondition();
+ RVal CondV = GetRVal(St, CondE);
+
+ if (CondV.isUndef()) {
+ NodeTy* N = builder.generateDefaultCaseNode(St, true);
+ UndefBranches.insert(N);
+ return;
+ }
+
+ 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.
+
+ unsigned bits = getContext().getTypeSize(CondE->getType());
+
+ APSInt V1(bits, false);
+ APSInt V2 = V1;
+
+ for (iterator I = builder.begin(), EI = builder.end(); I != EI; ++I) {
+
+ CaseStmt* Case = cast<CaseStmt>(I.getCase());
+
+ // Evaluate the case.
+ if (!Case->getLHS()->isIntegerConstantExpr(V1, getContext(), 0, true)) {
+ assert (false && "Case condition must evaluate to an integer constant.");
+ return;
+ }
+
+ // Get the RHS of the case, if it exists.
+
+ if (Expr* E = Case->getRHS()) {
+ if (!E->isIntegerConstantExpr(V2, getContext(), 0, true)) {
+ assert (false &&
+ "Case condition (RHS) must evaluate to an integer constant.");
+ return ;
+ }
+
+ assert (V1 <= V2);
+ }
+ else V2 = V1;
+
+ // FIXME: Eventually we should replace the logic below with a range
+ // comparison, rather than concretize the values within the range.
+ // This should be easy once we have "ranges" for NonLVals.
+
+ do {
+ nonlval::ConcreteInt CaseVal(BasicVals.getValue(V1));
+
+ RVal Res = EvalBinOp(BinaryOperator::EQ, CondV, CaseVal);
+
+ // Now "assume" that the case matches.
+
+ bool isFeasible = false;
+ ValueState* StNew = Assume(St, Res, true, isFeasible);
+
+ if (isFeasible) {
+ builder.generateCaseStmtNode(I, StNew);
+
+ // If CondV evaluates to a constant, then we know that this
+ // is the *only* case that we can take, so stop evaluating the
+ // others.
+ if (isa<nonlval::ConcreteInt>(CondV))
+ return;
+ }
+
+ // Now "assume" that the case doesn't match. Add this state
+ // to the default state (if it is feasible).
+
+ isFeasible = false;
+ StNew = Assume(DefaultSt, Res, false, isFeasible);
+
+ if (isFeasible)
+ DefaultSt = StNew;
+
+ // Concretize the next value in the range.
+ ++V1;
+
+ } while (V1 < V2);
+ }
+
+ // If we reach here, than we know that the default branch is
+ // possible.
+ builder.generateDefaultCaseNode(DefaultSt);
+}
+
+
+void GRExprEngine::VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred,
+ NodeSet& Dst) {
+
+ assert (B->getOpcode() == BinaryOperator::LAnd ||
+ B->getOpcode() == BinaryOperator::LOr);
+
+ assert (B == CurrentStmt && getCFG().isBlkExpr(B));
+
+ ValueState* St = GetState(Pred);
+ RVal X = GetBlkExprRVal(St, B);
+
+ assert (X.isUndef());
+
+ Expr* Ex = (Expr*) cast<UndefinedVal>(X).getData();
+
+ assert (Ex);
+
+ if (Ex == B->getRHS()) {
+
+ X = GetBlkExprRVal(St, Ex);
+
+ // Handle undefined values.
+
+ if (X.isUndef()) {
+ Nodify(Dst, B, Pred, SetBlkExprRVal(St, B, X));
+ return;
+ }
+
+ // We took the RHS. Because the value of the '&&' or '||' expression must
+ // evaluate to 0 or 1, we must assume the value of the RHS evaluates to 0
+ // or 1. Alternatively, we could take a lazy approach, and calculate this
+ // value later when necessary. We don't have the machinery in place for
+ // this right now, and since most logical expressions are used for branches,
+ // the payoff is not likely to be large. Instead, we do eager evaluation.
+
+ bool isFeasible = false;
+ ValueState* NewState = Assume(St, X, true, isFeasible);
+
+ if (isFeasible)
+ Nodify(Dst, B, Pred, SetBlkExprRVal(NewState, B, MakeConstantVal(1U, B)));
+
+ isFeasible = false;
+ NewState = Assume(St, X, false, isFeasible);
+
+ if (isFeasible)
+ Nodify(Dst, B, Pred, SetBlkExprRVal(NewState, B, MakeConstantVal(0U, B)));
+ }
+ else {
+ // We took the LHS expression. Depending on whether we are '&&' or
+ // '||' we know what the value of the expression is via properties of
+ // the short-circuiting.
+
+ X = MakeConstantVal( B->getOpcode() == BinaryOperator::LAnd ? 0U : 1U, B);
+ Nodify(Dst, B, Pred, SetBlkExprRVal(St, B, X));
+ }
+}
+
+
+void GRExprEngine::ProcessStmt(Stmt* S, StmtNodeBuilder& builder) {
+
+ Builder = &builder;
+ StmtEntryNode = builder.getLastNode();
+ CurrentStmt = S;
+ NodeSet Dst;
+
+ // Create the cleaned state.
+
+ CleanedState = StateMgr.RemoveDeadBindings(StmtEntryNode->getState(),
+ CurrentStmt, Liveness);
+
+ Builder->SetCleanedState(CleanedState);
+
+ // Visit the statement.
+
+ Visit(S, StmtEntryNode, Dst);
+
+ // If no nodes were generated, generate a new node that has all the
+ // dead mappings removed.
+
+ if (Dst.size() == 1 && *Dst.begin() == StmtEntryNode)
+ builder.generateNode(S, GetState(StmtEntryNode), StmtEntryNode);
+
+ // NULL out these variables to cleanup.
+
+ CurrentStmt = NULL;
+ StmtEntryNode = NULL;
+ Builder = NULL;
+ CleanedState = NULL;
+}
+
+void GRExprEngine::VisitDeclRefExpr(DeclRefExpr* D, NodeTy* Pred, NodeSet& Dst){
+
+ if (D != CurrentStmt) {
+ Dst.Add(Pred); // No-op. Simply propagate the current state unchanged.
+ return;
+ }
+
+ // If we are here, we are loading the value of the decl and binding
+ // it to the block-level expression.
+
+ ValueState* St = GetState(Pred);
+ RVal X = RVal::MakeVal(BasicVals, D);
+ RVal Y = isa<lval::DeclVal>(X) ? GetRVal(St, cast<lval::DeclVal>(X)) : X;
+ Nodify(Dst, D, Pred, SetBlkExprRVal(St, D, Y));
+}
+
+void GRExprEngine::VisitCall(CallExpr* CE, NodeTy* Pred,
+ CallExpr::arg_iterator AI,
+ CallExpr::arg_iterator AE,
+ NodeSet& Dst) {
+
+ // Process the arguments.
+
+ if (AI != AE) {
+
+ NodeSet DstTmp;
+ Visit(*AI, Pred, DstTmp);
+ ++AI;
+
+ for (NodeSet::iterator DI=DstTmp.begin(), DE=DstTmp.end(); DI != DE; ++DI)
+ VisitCall(CE, *DI, AI, AE, Dst);
+
+ return;
+ }
+
+ // If we reach here we have processed all of the arguments. Evaluate
+ // the callee expression.
+
+ NodeSet DstTmp;
+ Expr* Callee = CE->getCallee()->IgnoreParenCasts();
+
+ VisitLVal(Callee, Pred, DstTmp);
+
+ if (DstTmp.empty())
+ DstTmp.Add(Pred);
+
+ // Finally, evaluate the function call.
+ for (NodeSet::iterator DI = DstTmp.begin(), DE = DstTmp.end(); DI!=DE; ++DI) {
+
+ ValueState* St = GetState(*DI);
+ RVal L = GetLVal(St, Callee);
+
+ // FIXME: Add support for symbolic function calls (calls involving
+ // function pointer values that are symbolic).
+
+ // Check for undefined control-flow or calls to NULL.
+
+ if (L.isUndef() || isa<lval::ConcreteInt>(L)) {
+ NodeTy* N = Builder->generateNode(CE, St, *DI);
+
+ if (N) {
+ N->markAsSink();
+ BadCalls.insert(N);
+ }
+
+ continue;
+ }
+
+ // Check for the "noreturn" attribute.
+
+ SaveAndRestore<bool> OldSink(Builder->BuildSinks);
+
+ if (isa<lval::FuncVal>(L)) {
+
+ FunctionDecl* FD = cast<lval::FuncVal>(L).getDecl();
+
+ if (FD->getAttr<NoReturnAttr>())
+ Builder->BuildSinks = true;
+ else {
+ // HACK: Some functions are not marked noreturn, and don't return.
+ // Here are a few hardwired ones. If this takes too long, we can
+ // potentially cache these results.
+ const char* s = FD->getIdentifier()->getName();
+ unsigned n = strlen(s);
+
+ switch (n) {
+ default:
+ break;
+
+ case 4:
+ if (!memcmp(s, "exit", 4)) Builder->BuildSinks = true;
+ break;
+
+ case 5:
+ if (!memcmp(s, "panic", 5)) Builder->BuildSinks = true;
+ break;
+ }
+ }
+ }
+
+ // Evaluate the call.
+
+
+ bool invalidateArgs = false;
+
+ if (L.isUnknown()) {
+ // Check for an "unknown" callee.
+ invalidateArgs = true;
+ }
+ else if (isa<lval::FuncVal>(L)) {
+
+ IdentifierInfo* Info = cast<lval::FuncVal>(L).getDecl()->getIdentifier();
+
+ if (unsigned id = Info->getBuiltinID()) {
+ switch (id) {
+ case Builtin::BI__builtin_expect: {
+ // For __builtin_expect, just return the value of the subexpression.
+ assert (CE->arg_begin() != CE->arg_end());
+ RVal X = GetRVal(St, *(CE->arg_begin()));
+ Nodify(Dst, CE, *DI, SetRVal(St, CE, X));
+ continue;
+ }
+
+ default:
+ invalidateArgs = true;
+ break;
+ }
+ }
+ }
+
+ if (invalidateArgs) {
+ // Invalidate all arguments passed in by reference (LVals).
+ for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();
+ I != E; ++I) {
+ RVal V = GetRVal(St, *I);
+
+ if (isa<LVal>(V))
+ St = SetRVal(St, cast<LVal>(V), UnknownVal());
+ }
+
+ Nodify(Dst, CE, *DI, St);
+ }
+ else {
+
+ // Check any arguments passed-by-value against being undefined.
+
+ bool badArg = false;
+
+ for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();
+ I != E; ++I) {
+
+ if (GetRVal(GetState(*DI), *I).isUndef()) {
+ NodeTy* N = Builder->generateNode(CE, GetState(*DI), *DI);
+
+ if (N) {
+ N->markAsSink();
+ UndefArgs[N] = *I;
+ }
+
+ badArg = true;
+ break;
+ }
+ }
+
+ if (badArg)
+ continue;
+
+ // Dispatch to the plug-in transfer function.
+
+ unsigned size = Dst.size();
+
+ EvalCall(Dst, CE, cast<LVal>(L), *DI);
+
+ if (!Builder->BuildSinks && Dst.size() == size)
+ Nodify(Dst, CE, *DI, St);
+ }
+ }
+}
+
+void GRExprEngine::VisitCast(Expr* CastE, Expr* Ex, NodeTy* Pred, NodeSet& Dst){
+
+ NodeSet S1;
+ QualType T = CastE->getType();
+
+ if (T->isReferenceType())
+ VisitLVal(Ex, Pred, S1);
+ else
+ Visit(Ex, Pred, S1);
+
+ // Check for redundant casts or casting to "void"
+ if (T->isVoidType() ||
+ Ex->getType() == T ||
+ (T->isPointerType() && Ex->getType()->isFunctionType())) {
+
+ for (NodeSet::iterator I1 = S1.begin(), E1 = S1.end(); I1 != E1; ++I1)
+ Dst.Add(*I1);
+
+ return;
+ }
+
+ for (NodeSet::iterator I1 = S1.begin(), E1 = S1.end(); I1 != E1; ++I1) {
+ NodeTy* N = *I1;
+ ValueState* St = GetState(N);
+
+ RVal V = T->isReferenceType() ? GetLVal(St, Ex) : GetRVal(St, Ex);
+
+ Nodify(Dst, CastE, N, SetRVal(St, CastE, EvalCast(V, CastE->getType())));
+ }
+}
+
+void GRExprEngine::VisitDeclStmt(DeclStmt* DS, GRExprEngine::NodeTy* Pred,
+ GRExprEngine::NodeSet& Dst) {
+
+ ValueState* St = GetState(Pred);
+
+ for (const ScopedDecl* D = DS->getDecl(); D; D = D->getNextDeclarator())
+ if (const VarDecl* VD = dyn_cast<VarDecl>(D)) {
+
+ // FIXME: Add support for local arrays.
+ if (VD->getType()->isArrayType())
+ continue;
+
+ const Expr* Ex = VD->getInit();
+
+ if (!VD->hasGlobalStorage() || VD->getStorageClass() == VarDecl::Static) {
+
+ // In this context, Static => Local variable.
+
+ assert (!VD->getStorageClass() == VarDecl::Static ||
+ !isa<FileVarDecl>(VD));
+
+ // If there is no initializer, set the value of the
+ // variable to "Undefined".
+ //
+ // FIXME: static variables may have an initializer, but the second
+ // time a function is called those values may not be current.
+
+ QualType T = VD->getType();
+
+ if ( VD->getStorageClass() == VarDecl::Static) {
+
+ // C99: 6.7.8 Initialization
+ // If an object that has static storage duration is not initialized
+ // explicitly, then:
+ // —if it has pointer type, it is initialized to a null pointer;
+ // —if it has arithmetic type, it is initialized to (positive or
+ // unsigned) zero;
+
+ // FIXME: Handle structs. Now we treat their values as unknown.
+
+ if (T->isPointerType()) {
+
+ St = SetRVal(St, lval::DeclVal(VD),
+ lval::ConcreteInt(BasicVals.getValue(0, T)));
+ }
+ else if (T->isIntegerType()) {
+
+ St = SetRVal(St, lval::DeclVal(VD),
+ nonlval::ConcreteInt(BasicVals.getValue(0, T)));
+ }
+
+
+ }
+ else {
+
+ // FIXME: Handle structs. Now we treat them as unknown. What
+ // we need to do is treat their members as unknown.
+
+ if (T->isPointerType() || T->isIntegerType())
+ St = SetRVal(St, lval::DeclVal(VD),
+ Ex ? GetRVal(St, Ex) : UndefinedVal());
+ }
+ }
+ }
+
+ Nodify(Dst, DS, Pred, St);
+}
+
+
+void GRExprEngine::VisitGuardedExpr(Expr* Ex, Expr* L, Expr* R,
+ NodeTy* Pred, NodeSet& Dst) {
+
+ assert (Ex == CurrentStmt && getCFG().isBlkExpr(Ex));
+
+ ValueState* St = GetState(Pred);
+ RVal X = GetBlkExprRVal(St, Ex);
+
+ assert (X.isUndef());
+
+ Expr* SE = (Expr*) cast<UndefinedVal>(X).getData();
+
+ assert (SE);
+
+ X = GetBlkExprRVal(St, SE);
+
+ // Make sure that we invalidate the previous binding.
+ Nodify(Dst, Ex, Pred, StateMgr.SetRVal(St, Ex, X, true, true));
+}
+
+/// VisitSizeOfAlignOfTypeExpr - Transfer function for sizeof(type).
+void GRExprEngine::VisitSizeOfAlignOfTypeExpr(SizeOfAlignOfTypeExpr* Ex,
+ NodeTy* Pred,
+ NodeSet& Dst) {
+
+ QualType T = Ex->getArgumentType();
+ uint64_t amt;
+
+ if (Ex->isSizeOf()) {
+
+ // FIXME: Add support for VLAs.
+ if (!T.getTypePtr()->isConstantSizeType())
+ return;
+
+ amt = 1; // Handle sizeof(void)
+
+ if (T != getContext().VoidTy)
+ amt = getContext().getTypeSize(T) / 8;
+
+ }
+ else // Get alignment of the type.
+ amt = getContext().getTypeAlign(T) / 8;
+
+ Nodify(Dst, Ex, Pred,
+ SetRVal(GetState(Pred), Ex,
+ NonLVal::MakeVal(BasicVals, amt, Ex->getType())));
+}
+
+void GRExprEngine::VisitDeref(UnaryOperator* U, NodeTy* Pred,
+ NodeSet& Dst, bool GetLVal) {
+
+ Expr* Ex = U->getSubExpr()->IgnoreParens();
+
+ NodeSet DstTmp;
+
+ if (isa<DeclRefExpr>(Ex))
+ DstTmp.Add(Pred);
+ else
+ Visit(Ex, Pred, DstTmp);
+
+ for (NodeSet::iterator I = DstTmp.begin(), DE = DstTmp.end(); I != DE; ++I) {
+
+ NodeTy* N = *I;
+ ValueState* St = GetState(N);
+
+ // FIXME: Bifurcate when dereferencing a symbolic with no constraints?
+
+ RVal V = GetRVal(St, Ex);
+
+ // Check for dereferences of undefined values.
+
+ if (V.isUndef()) {
+
+ NodeTy* Succ = Builder->generateNode(U, St, N);
+
+ if (Succ) {
+ Succ->markAsSink();
+ UndefDeref.insert(Succ);
+ }
+
+ continue;
+ }
+
+ // Check for dereferences of unknown values. Treat as No-Ops.
+
+ if (V.isUnknown()) {
+ Dst.Add(N);
+ continue;
+ }
+
+ // After a dereference, one of two possible situations arise:
+ // (1) A crash, because the pointer was NULL.
+ // (2) The pointer is not NULL, and the dereference works.
+ //
+ // We add these assumptions.
+
+ LVal LV = cast<LVal>(V);
+ bool isFeasibleNotNull;
+
+ // "Assume" that the pointer is Not-NULL.
+
+ ValueState* StNotNull = Assume(St, LV, true, isFeasibleNotNull);
+
+ if (isFeasibleNotNull) {
+
+ if (GetLVal) Nodify(Dst, U, N, SetRVal(StNotNull, U, LV));
+ else {
+
+ // FIXME: Currently symbolic analysis "generates" new symbols
+ // for the contents of values. We need a better approach.
+
+ Nodify(Dst, U, N, SetRVal(StNotNull, U,
+ GetRVal(StNotNull, LV, U->getType())));
+ }
+ }
+
+ bool isFeasibleNull;
+
+ // Now "assume" that the pointer is NULL.
+
+ ValueState* StNull = Assume(St, LV, false, isFeasibleNull);
+
+ if (isFeasibleNull) {
+
+ // We don't use "Nodify" here because the node will be a sink
+ // and we have no intention of processing it later.
+
+ NodeTy* NullNode = Builder->generateNode(U, StNull, N);
+
+ if (NullNode) {
+
+ NullNode->markAsSink();
+
+ if (isFeasibleNotNull) ImplicitNullDeref.insert(NullNode);
+ else ExplicitNullDeref.insert(NullNode);
+ }
+ }
+ }
+}
+
+void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* Pred,
+ NodeSet& Dst) {
+
+ NodeSet S1;
+
+ assert (U->getOpcode() != UnaryOperator::Deref);
+ assert (U->getOpcode() != UnaryOperator::SizeOf);
+ assert (U->getOpcode() != UnaryOperator::AlignOf);
+
+ bool use_GetLVal = false;
+
+ switch (U->getOpcode()) {
+ case UnaryOperator::PostInc:
+ case UnaryOperator::PostDec:
+ case UnaryOperator::PreInc:
+ case UnaryOperator::PreDec:
+ case UnaryOperator::AddrOf:
+ // Evalue subexpression as an LVal.
+ use_GetLVal = true;
+ VisitLVal(U->getSubExpr(), Pred, S1);
+ break;
+
+ default:
+ Visit(U->getSubExpr(), Pred, S1);
+ break;
+ }
+
+ for (NodeSet::iterator I1 = S1.begin(), E1 = S1.end(); I1 != E1; ++I1) {
+
+ NodeTy* N1 = *I1;
+ ValueState* St = GetState(N1);
+
+ RVal SubV = use_GetLVal ? GetLVal(St, U->getSubExpr()) :
+ GetRVal(St, U->getSubExpr());
+
+ if (SubV.isUnknown()) {
+ Dst.Add(N1);
+ continue;
+ }
+
+ if (SubV.isUndef()) {
+ Nodify(Dst, U, N1, SetRVal(St, U, SubV));
+ continue;
+ }
+
+ if (U->isIncrementDecrementOp()) {
+
+ // Handle ++ and -- (both pre- and post-increment).
+
+ LVal SubLV = cast<LVal>(SubV);
+ RVal V = GetRVal(St, SubLV, U->getType());
+
+ if (V.isUnknown()) {
+ Dst.Add(N1);
+ continue;
+ }
+
+ // Propagate undefined values.
+ if (V.isUndef()) {
+ Nodify(Dst, U, N1, SetRVal(St, U, V));
+ continue;
+ }
+
+ // Handle all other values.
+
+ BinaryOperator::Opcode Op = U->isIncrementOp() ? BinaryOperator::Add
+ : BinaryOperator::Sub;
+
+ RVal Result = EvalBinOp(Op, V, MakeConstantVal(1U, U));
+
+ if (U->isPostfix())
+ St = SetRVal(SetRVal(St, U, V), SubLV, Result);
+ else
+ St = SetRVal(SetRVal(St, U, Result), SubLV, Result);
+
+ Nodify(Dst, U, N1, St);
+ continue;
+ }
+
+ // Handle all other unary operators.
+
+ switch (U->getOpcode()) {
+
+ case UnaryOperator::Extension:
+ St = SetRVal(St, U, SubV);
+ break;
+
+ case UnaryOperator::Minus:
+ St = SetRVal(St, U, EvalMinus(U, cast<NonLVal>(SubV)));
+ break;
+
+ case UnaryOperator::Not:
+ St = SetRVal(St, U, EvalComplement(cast<NonLVal>(SubV)));
+ break;
+
+ case UnaryOperator::LNot:
+
+ // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
+ //
+ // Note: technically we do "E == 0", but this is the same in the
+ // transfer functions as "0 == E".
+
+ if (isa<LVal>(SubV)) {
+ lval::ConcreteInt V(BasicVals.getZeroWithPtrWidth());
+ RVal Result = EvalBinOp(BinaryOperator::EQ, cast<LVal>(SubV), V);
+ St = SetRVal(St, U, Result);
+ }
+ else {
+ Expr* Ex = U->getSubExpr();
+ nonlval::ConcreteInt V(BasicVals.getValue(0, Ex->getType()));
+ RVal Result = EvalBinOp(BinaryOperator::EQ, cast<NonLVal>(SubV), V);
+ St = SetRVal(St, U, Result);
+ }
+
+ break;
+
+ case UnaryOperator::AddrOf: {
+ assert (isa<LVal>(SubV));
+ St = SetRVal(St, U, SubV);
+ break;
+ }
+
+ default: ;
+ assert (false && "Not implemented.");
+ }
+
+ Nodify(Dst, U, N1, St);
+ }
+}
+
+void GRExprEngine::VisitSizeOfExpr(UnaryOperator* U, NodeTy* Pred,
+ NodeSet& Dst) {
+
+ QualType T = U->getSubExpr()->getType();
+
+ // FIXME: Add support for VLAs.
+ if (!T.getTypePtr()->isConstantSizeType())
+ return;
+
+ uint64_t size = getContext().getTypeSize(T) / 8;
+ ValueState* St = GetState(Pred);
+ St = SetRVal(St, U, NonLVal::MakeVal(BasicVals, size, U->getType()));
+
+ Nodify(Dst, U, Pred, St);
+}
+
+void GRExprEngine::VisitLVal(Expr* Ex, NodeTy* Pred, NodeSet& Dst) {
+
+ if (Ex != CurrentStmt && getCFG().isBlkExpr(Ex)) {
+ Dst.Add(Pred);
+ return;
+ }
+
+ Ex = Ex->IgnoreParens();
+
+ if (isa<DeclRefExpr>(Ex)) {
+ Dst.Add(Pred);
+ return;
+ }
+
+ if (UnaryOperator* U = dyn_cast<UnaryOperator>(Ex))
+ if (U->getOpcode() == UnaryOperator::Deref) {
+ VisitDeref(U, Pred, Dst, true);
+ return;
+ }
+
+ Visit(Ex, Pred, Dst);
+}
+
+void GRExprEngine::VisitBinaryOperator(BinaryOperator* B,
+ GRExprEngine::NodeTy* Pred,
+ GRExprEngine::NodeSet& Dst) {
+ NodeSet S1;
+
+ if (B->isAssignmentOp())
+ VisitLVal(B->getLHS(), Pred, S1);
+ else
+ Visit(B->getLHS(), Pred, S1);
+
+ for (NodeSet::iterator I1=S1.begin(), E1=S1.end(); I1 != E1; ++I1) {
+
+ NodeTy* N1 = *I1;
+
+ // When getting the value for the LHS, check if we are in an assignment.
+ // In such cases, we want to (initially) treat the LHS as an LVal,
+ // so we use GetLVal instead of GetRVal so that DeclRefExpr's are
+ // evaluated to LValDecl's instead of to an NonLVal.
+
+ RVal LeftV = B->isAssignmentOp() ? GetLVal(GetState(N1), B->getLHS())
+ : GetRVal(GetState(N1), B->getLHS());
+
+ // Visit the RHS...
+
+ NodeSet S2;
+ Visit(B->getRHS(), N1, S2);
+
+ // Process the binary operator.
+
+ for (NodeSet::iterator I2 = S2.begin(), E2 = S2.end(); I2 != E2; ++I2) {
+
+ NodeTy* N2 = *I2;
+ ValueState* St = GetState(N2);
+ Expr* RHS = B->getRHS();
+ RVal RightV = GetRVal(St, RHS);
+
+ BinaryOperator::Opcode Op = B->getOpcode();
+
+ if ((Op == BinaryOperator::Div || Op == BinaryOperator::Rem)
+ && RHS->getType()->isIntegerType()) {
+
+ // Check if the denominator is undefined.
+
+ if (!RightV.isUnknown()) {
+
+ if (RightV.isUndef()) {
+ NodeTy* DivUndef = Builder->generateNode(B, St, N2);
+
+ if (DivUndef) {
+ DivUndef->markAsSink();
+ ExplicitBadDivides.insert(DivUndef);
+ }
+
+ continue;
+ }
+
+ // Check for divide/remainder-by-zero.
+ //
+ // First, "assume" that the denominator is 0 or undefined.
+
+ bool isFeasibleZero = false;
+ ValueState* ZeroSt = Assume(St, RightV, false, isFeasibleZero);
+
+ // Second, "assume" that the denominator cannot be 0.
+
+ bool isFeasibleNotZero = false;
+ St = Assume(St, RightV, true, isFeasibleNotZero);
+
+ // Create the node for the divide-by-zero (if it occurred).
+
+ if (isFeasibleZero)
+ if (NodeTy* DivZeroNode = Builder->generateNode(B, ZeroSt, N2)) {
+ DivZeroNode->markAsSink();
+
+ if (isFeasibleNotZero)
+ ImplicitBadDivides.insert(DivZeroNode);
+ else
+ ExplicitBadDivides.insert(DivZeroNode);
+
+ }
+
+ if (!isFeasibleNotZero)
+ continue;
+ }
+
+ // Fall-through. The logic below processes the divide.
+ }
+
+
+ if (Op <= BinaryOperator::Or) {
+
+ // Process non-assignements except commas or short-circuited
+ // logical expressions (LAnd and LOr).
+
+ RVal Result = EvalBinOp(Op, LeftV, RightV);
+
+ if (Result.isUnknown()) {
+ Dst.Add(N2);
+ continue;
+ }
+
+ if (Result.isUndef() && !LeftV.isUndef() && !RightV.isUndef()) {
+
+ // The operands were not undefined, but the result is undefined.
+
+ if (NodeTy* UndefNode = Builder->generateNode(B, St, N2)) {
+ UndefNode->markAsSink();
+ UndefResults.insert(UndefNode);
+ }
+
+ continue;
+ }
+
+ Nodify(Dst, B, N2, SetRVal(St, B, Result));
+ continue;
+ }
+
+ // Process assignments.
+
+ switch (Op) {
+
+ case BinaryOperator::Assign: {
+
+ // Simple assignments.
+
+ if (LeftV.isUndef()) {
+ HandleUndefinedStore(B, N2);
+ continue;
+ }
+
+ // EXPERIMENTAL: "Conjured" symbols.
+
+ if (RightV.isUnknown()) {
+ unsigned Count = Builder->getCurrentBlockCount();
+ SymbolID Sym = SymMgr.getConjuredSymbol(B->getRHS(), Count);
+
+ RightV = B->getRHS()->getType()->isPointerType()
+ ? cast<RVal>(lval::SymbolVal(Sym))
+ : cast<RVal>(nonlval::SymbolVal(Sym));
+ }
+
+ // Even if the LHS evaluates to an unknown L-Value, the entire
+ // expression still evaluates to the RHS.
+
+ if (LeftV.isUnknown()) {
+ St = SetRVal(St, B, RightV);
+ break;
+ }
+
+ // Simulate the effects of a "store": bind the value of the RHS
+ // to the L-Value represented by the LHS.
+
+ St = SetRVal(SetRVal(St, B, RightV), cast<LVal>(LeftV), RightV);
+ break;
+ }
+
+ // Compound assignment operators.
+
+ default: {
+
+ assert (B->isCompoundAssignmentOp());
+
+ if (Op >= BinaryOperator::AndAssign)
+ ((int&) Op) -= (BinaryOperator::AndAssign - BinaryOperator::And);
+ else
+ ((int&) Op) -= BinaryOperator::MulAssign;
+
+ // Check if the LHS is undefined.
+
+ if (LeftV.isUndef()) {
+ HandleUndefinedStore(B, N2);
+ continue;
+ }
+
+ if (LeftV.isUnknown()) {
+ assert (isa<UnknownVal>(GetRVal(St, B)));
+ Dst.Add(N2);
+ continue;
+ }
+
+ // At this pointer we know that the LHS evaluates to an LVal
+ // that is neither "Unknown" or "Undefined."
+
+ LVal LeftLV = cast<LVal>(LeftV);
+
+ // Fetch the value of the LHS (the value of the variable, etc.).
+
+ RVal V = GetRVal(GetState(N1), LeftLV, B->getLHS()->getType());
+
+ // Propagate undefined value (left-side). We
+ // propogate undefined values for the RHS below when
+ // we also check for divide-by-zero.
+
+ if (V.isUndef()) {
+ St = SetRVal(St, B, V);
+ break;
+ }
+
+ // Propagate unknown values.
+
+ if (V.isUnknown()) {
+ // The value bound to LeftV is unknown. Thus we just
+ // propagate the current node (as "B" is already bound to nothing).
+ assert (isa<UnknownVal>(GetRVal(St, B)));
+ Dst.Add(N2);
+ continue;
+ }
+
+ if (RightV.isUnknown()) {
+ assert (isa<UnknownVal>(GetRVal(St, B)));
+ St = SetRVal(St, LeftLV, UnknownVal());
+ break;
+ }
+
+ // At this point:
+ //
+ // The LHS is not Undef/Unknown.
+ // The RHS is not Unknown.
+
+ // Get the computation type.
+ QualType CTy = cast<CompoundAssignOperator>(B)->getComputationType();
+
+ // Perform promotions.
+ V = EvalCast(V, CTy);
+ RightV = EvalCast(RightV, CTy);
+
+ // Evaluate operands and promote to result type.
+
+ if ((Op == BinaryOperator::Div || Op == BinaryOperator::Rem)
+ && RHS->getType()->isIntegerType()) {
+
+ // Check if the denominator is undefined.
+
+ if (RightV.isUndef()) {
+ NodeTy* DivUndef = Builder->generateNode(B, St, N2);
+
+ if (DivUndef) {
+ DivUndef->markAsSink();
+ ExplicitBadDivides.insert(DivUndef);
+ }
+
+ continue;
+ }
+
+ // First, "assume" that the denominator is 0.
+
+ bool isFeasibleZero = false;
+ ValueState* ZeroSt = Assume(St, RightV, false, isFeasibleZero);
+
+ // Second, "assume" that the denominator cannot be 0.
+
+ bool isFeasibleNotZero = false;
+ St = Assume(St, RightV, true, isFeasibleNotZero);
+
+ // Create the node for the divide-by-zero error (if it occurred).
+
+ if (isFeasibleZero) {
+ NodeTy* DivZeroNode = Builder->generateNode(B, ZeroSt, N2);
+
+ if (DivZeroNode) {
+ DivZeroNode->markAsSink();
+
+ if (isFeasibleNotZero)
+ ImplicitBadDivides.insert(DivZeroNode);
+ else
+ ExplicitBadDivides.insert(DivZeroNode);
+ }
+ }
+
+ if (!isFeasibleNotZero)
+ continue;
+
+ // Fall-through. The logic below processes the divide.
+ }
+ else {
+
+ // Propagate undefined values (right-side).
+
+ if (RightV.isUndef()) {
+ St = SetRVal(SetRVal(St, B, RightV), LeftLV, RightV);
+ break;
+ }
+
+ }
+
+ RVal Result = EvalCast(EvalBinOp(Op, V, RightV), B->getType());
+
+ if (Result.isUndef()) {
+
+ // The operands were not undefined, but the result is undefined.
+
+ if (NodeTy* UndefNode = Builder->generateNode(B, St, N2)) {
+ UndefNode->markAsSink();
+ UndefResults.insert(UndefNode);
+ }
+
+ continue;
+ }
+
+ St = SetRVal(SetRVal(St, B, Result), LeftLV, Result);
+ }
+ }
+
+ Nodify(Dst, B, N2, St);
+ }
+ }
+}
+
+void GRExprEngine::HandleUndefinedStore(Stmt* S, NodeTy* Pred) {
+ NodeTy* N = Builder->generateNode(S, GetState(Pred), Pred);
+ N->markAsSink();
+ UndefStores.insert(N);
+}
+
+void GRExprEngine::Visit(Stmt* S, NodeTy* Pred, NodeSet& Dst) {
+
+ // FIXME: add metadata to the CFG so that we can disable
+ // this check when we KNOW that there is no block-level subexpression.
+ // The motivation is that this check requires a hashtable lookup.
+
+ if (S != CurrentStmt && getCFG().isBlkExpr(S)) {
+ Dst.Add(Pred);
+ return;
+ }
+
+ switch (S->getStmtClass()) {
+
+ default:
+ // Cases we intentionally have "default" handle:
+ // AddrLabelExpr, IntegerLiteral, CharacterLiteral
+
+ Dst.Add(Pred); // No-op. Simply propagate the current state unchanged.
+ break;
+
+ case Stmt::BinaryOperatorClass: {
+ BinaryOperator* B = cast<BinaryOperator>(S);
+
+ if (B->isLogicalOp()) {
+ VisitLogicalExpr(B, Pred, Dst);
+ break;
+ }
+ else if (B->getOpcode() == BinaryOperator::Comma) {
+ ValueState* St = GetState(Pred);
+ Nodify(Dst, B, Pred, SetRVal(St, B, GetRVal(St, B->getRHS())));
+ break;
+ }
+
+ VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
+ break;
+ }
+
+ case Stmt::CallExprClass: {
+ CallExpr* C = cast<CallExpr>(S);
+ VisitCall(C, Pred, C->arg_begin(), C->arg_end(), Dst);
+ break;
+ }
+
+ case Stmt::CastExprClass: {
+ CastExpr* C = cast<CastExpr>(S);
+ VisitCast(C, C->getSubExpr(), Pred, Dst);
+ break;
+ }
+
+ // FIXME: ChooseExpr is really a constant. We need to fix
+ // the CFG do not model them as explicit control-flow.
+
+ case Stmt::ChooseExprClass: { // __builtin_choose_expr
+ ChooseExpr* C = cast<ChooseExpr>(S);
+ VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
+ break;
+ }
+
+ case Stmt::CompoundAssignOperatorClass:
+ VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
+ break;
+
+ case Stmt::ConditionalOperatorClass: { // '?' operator
+ ConditionalOperator* C = cast<ConditionalOperator>(S);
+ VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
+ break;
+ }
+
+ case Stmt::DeclRefExprClass:
+ VisitDeclRefExpr(cast<DeclRefExpr>(S), Pred, Dst);
+ break;
+
+ case Stmt::DeclStmtClass:
+ VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
+ break;
+
+ case Stmt::ImplicitCastExprClass: {
+ ImplicitCastExpr* C = cast<ImplicitCastExpr>(S);
+ VisitCast(C, C->getSubExpr(), Pred, Dst);
+ break;
+ }
+
+ case Stmt::ParenExprClass:
+ Visit(cast<ParenExpr>(S)->getSubExpr(), Pred, Dst);
+ break;
+
+ case Stmt::SizeOfAlignOfTypeExprClass:
+ VisitSizeOfAlignOfTypeExpr(cast<SizeOfAlignOfTypeExpr>(S), Pred, Dst);
+ break;
+
+ case Stmt::StmtExprClass: {
+ StmtExpr* SE = cast<StmtExpr>(S);
+
+ ValueState* St = GetState(Pred);
+
+ // FIXME: Not certain if we can have empty StmtExprs. If so, we should
+ // probably just remove these from the CFG.
+ assert (!SE->getSubStmt()->body_empty());
+
+ if (Expr* LastExpr = dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin()))
+ Nodify(Dst, SE, Pred, SetRVal(St, SE, GetRVal(St, LastExpr)));
+ else
+ Dst.Add(Pred);
+
+ break;
+ }
+
+ // FIXME: We may wish to always bind state to ReturnStmts so
+ // that users can quickly query what was the state at the
+ // exit points of a function.
+
+ case Stmt::ReturnStmtClass: {
+ if (Expr* R = cast<ReturnStmt>(S)->getRetValue())
+ Visit(R, Pred, Dst);
+ else
+ Dst.Add(Pred);
+
+ break;
+ }
+
+ case Stmt::UnaryOperatorClass: {
+ UnaryOperator* U = cast<UnaryOperator>(S);
+
+ switch (U->getOpcode()) {
+ case UnaryOperator::Deref: VisitDeref(U, Pred, Dst); break;
+ case UnaryOperator::Plus: Visit(U->getSubExpr(), Pred, Dst); break;
+ case UnaryOperator::SizeOf: VisitSizeOfExpr(U, Pred, Dst); break;
+ default: VisitUnaryOperator(U, Pred, Dst); break;
+ }
+
+ break;
+ }
+ }
+}
+
+//===----------------------------------------------------------------------===//
+// "Assume" logic.
+//===----------------------------------------------------------------------===//
+
+ValueState* GRExprEngine::Assume(ValueState* St, LVal Cond,
+ bool Assumption,
+ bool& isFeasible) {
+ switch (Cond.getSubKind()) {
+ default:
+ assert (false && "'Assume' not implemented for this LVal.");
+ return St;
+
+ case lval::SymbolValKind:
+ if (Assumption)
+ return AssumeSymNE(St, cast<lval::SymbolVal>(Cond).getSymbol(),
+ BasicVals.getZeroWithPtrWidth(), isFeasible);
+ else
+ return AssumeSymEQ(St, cast<lval::SymbolVal>(Cond).getSymbol(),
+ BasicVals.getZeroWithPtrWidth(), isFeasible);
+
+
+ case lval::DeclValKind:
+ case lval::FuncValKind:
+ case lval::GotoLabelKind:
+ isFeasible = Assumption;
+ return St;
+
+ case lval::ConcreteIntKind: {
+ bool b = cast<lval::ConcreteInt>(Cond).getValue() != 0;
+ isFeasible = b ? Assumption : !Assumption;
+ return St;
+ }
+ }
+}
+
+ValueState* GRExprEngine::Assume(ValueState* St, NonLVal Cond,
+ bool Assumption,
+ bool& isFeasible) {
+ switch (Cond.getSubKind()) {
+ default:
+ assert (false && "'Assume' not implemented for this NonLVal.");
+ return St;
+
+
+ case nonlval::SymbolValKind: {
+ nonlval::SymbolVal& SV = cast<nonlval::SymbolVal>(Cond);
+ SymbolID sym = SV.getSymbol();
+
+ if (Assumption)
+ return AssumeSymNE(St, sym, BasicVals.getValue(0, SymMgr.getType(sym)),
+ isFeasible);
+ else
+ return AssumeSymEQ(St, sym, BasicVals.getValue(0, SymMgr.getType(sym)),
+ isFeasible);
+ }
+
+ case nonlval::SymIntConstraintValKind:
+ return
+ AssumeSymInt(St, Assumption,
+ cast<nonlval::SymIntConstraintVal>(Cond).getConstraint(),
+ isFeasible);
+
+ case nonlval::ConcreteIntKind: {
+ bool b = cast<nonlval::ConcreteInt>(Cond).getValue() != 0;
+ isFeasible = b ? Assumption : !Assumption;
+ return St;
+ }
+ }
+}
+
+ValueState*
+GRExprEngine::AssumeSymNE(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)) {
+ isFeasible = *X != V;
+ return St;
+ }
+
+ // Second, determine if sym != V.
+ if (St->isNotEqual(sym, V)) {
+ isFeasible = true;
+ return St;
+ }
+
+ // If we reach here, sym is not a constant and we don't know if it is != V.
+ // Make that assumption.
+
+ isFeasible = true;
+ return StateMgr.AddNE(St, sym, V);
+}
+
+ValueState*
+GRExprEngine::AssumeSymEQ(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)) {
+ isFeasible = *X == V;
+ return St;
+ }
+
+ // Second, determine if sym != V.
+ if (St->isNotEqual(sym, V)) {
+ isFeasible = false;
+ return St;
+ }
+
+ // If we reach here, sym is not a constant and we don't know if it is == V.
+ // Make that assumption.
+
+ isFeasible = true;
+ return StateMgr.AddEQ(St, sym, V);
+}
+
+ValueState*
+GRExprEngine::AssumeSymInt(ValueState* St, bool Assumption,
+ const SymIntConstraint& C, bool& isFeasible) {
+
+ switch (C.getOpcode()) {
+ default:
+ // No logic yet for other operators.
+ isFeasible = true;
+ return St;
+
+ case BinaryOperator::EQ:
+ if (Assumption)
+ return AssumeSymEQ(St, C.getSymbol(), C.getInt(), isFeasible);
+ else
+ return AssumeSymNE(St, C.getSymbol(), C.getInt(), isFeasible);
+
+ case BinaryOperator::NE:
+ if (Assumption)
+ return AssumeSymNE(St, C.getSymbol(), C.getInt(), isFeasible);
+ else
+ return AssumeSymEQ(St, C.getSymbol(), C.getInt(), isFeasible);
+ }
+}
+
+//===----------------------------------------------------------------------===//
+// Visualization.
+//===----------------------------------------------------------------------===//
+
+#ifndef NDEBUG
+static GRExprEngine* GraphPrintCheckerState;
+static SourceManager* GraphPrintSourceManager;
+static ValueState::CheckerStatePrinter* GraphCheckerStatePrinter;
+
+namespace llvm {
+template<>
+struct VISIBILITY_HIDDEN DOTGraphTraits<GRExprEngine::NodeTy*> :
+ public DefaultDOTGraphTraits {
+
+ static void PrintVarBindings(std::ostream& Out, ValueState* St) {
+
+ Out << "Variables:\\l";
+
+ bool isFirst = true;
+
+ for (ValueState::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 PrintSubExprBindings(std::ostream& Out, ValueState* St){
+
+ bool isFirst = true;
+
+ for (ValueState::seb_iterator I=St->seb_begin(), E=St->seb_end();I!=E;++I) {
+
+ if (isFirst) {
+ Out << "\\l\\lSub-Expressions:\\l";
+ isFirst = false;
+ }
+ else
+ Out << "\\l";
+
+ Out << " (" << (void*) I.getKey() << ") ";
+ I.getKey()->printPretty(Out);
+ Out << " : ";
+ I.getData().print(Out);
+ }
+ }
+
+ static void PrintBlkExprBindings(std::ostream& Out, ValueState* St){
+
+ bool isFirst = true;
+
+ for (ValueState::beb_iterator I=St->beb_begin(), E=St->beb_end(); I!=E;++I){
+ if (isFirst) {
+ Out << "\\l\\lBlock-level Expressions:\\l";
+ isFirst = false;
+ }
+ else
+ Out << "\\l";
+
+ Out << " (" << (void*) I.getKey() << ") ";
+ I.getKey()->printPretty(Out);
+ Out << " : ";
+ I.getData().print(Out);
+ }
+ }
+
+ static void PrintEQ(std::ostream& Out, ValueState* St) {
+ ValueState::ConstEqTy CE = St->ConstEq;
+
+ if (CE.isEmpty())
+ return;
+
+ Out << "\\l\\|'==' constraints:";
+
+ for (ValueState::ConstEqTy::iterator I=CE.begin(), E=CE.end(); I!=E;++I)
+ Out << "\\l $" << I.getKey() << " : " << I.getData()->toString();
+ }
+
+ static void PrintNE(std::ostream& Out, ValueState* St) {
+ ValueState::ConstNotEqTy NE = St->ConstNotEq;
+
+ if (NE.isEmpty())
+ return;
+
+ Out << "\\l\\|'!=' constraints:";
+
+ for (ValueState::ConstNotEqTy::iterator I=NE.begin(), EI=NE.end();
+ I != EI; ++I){
+
+ Out << "\\l $" << I.getKey() << " : ";
+ bool isFirst = true;
+
+ ValueState::IntSetTy::iterator J=I.getData().begin(),
+ EJ=I.getData().end();
+ for ( ; J != EJ; ++J) {
+ if (isFirst) isFirst = false;
+ else Out << ", ";
+
+ Out << (*J)->toString();
+ }
+ }
+ }
+
+ static std::string getNodeAttributes(const GRExprEngine::NodeTy* N, void*) {
+
+ if (GraphPrintCheckerState->isImplicitNullDeref(N) ||
+ GraphPrintCheckerState->isExplicitNullDeref(N) ||
+ GraphPrintCheckerState->isUndefDeref(N) ||
+ GraphPrintCheckerState->isUndefStore(N) ||
+ GraphPrintCheckerState->isUndefControlFlow(N) ||
+ GraphPrintCheckerState->isExplicitBadDivide(N) ||
+ GraphPrintCheckerState->isImplicitBadDivide(N) ||
+ GraphPrintCheckerState->isUndefResult(N) ||
+ GraphPrintCheckerState->isBadCall(N) ||
+ GraphPrintCheckerState->isUndefArg(N))
+ return "color=\"red\",style=\"filled\"";
+
+ if (GraphPrintCheckerState->isNoReturnCall(N))
+ return "color=\"blue\",style=\"filled\"";
+
+ return "";
+ }
+
+ static std::string getNodeLabel(const GRExprEngine::NodeTy* N, void*) {
+ std::ostringstream Out;
+
+ // Program Location.
+ ProgramPoint Loc = N->getLocation();
+
+ switch (Loc.getKind()) {
+ case ProgramPoint::BlockEntranceKind:
+ Out << "Block Entrance: B"
+ << cast<BlockEntrance>(Loc).getBlock()->getBlockID();
+ break;
+
+ case ProgramPoint::BlockExitKind:
+ assert (false);
+ break;
+
+ case ProgramPoint::PostStmtKind: {
+ const PostStmt& L = cast<PostStmt>(Loc);
+ Stmt* S = L.getStmt();
+ SourceLocation SLoc = S->getLocStart();
+
+ Out << S->getStmtClassName() << ' ' << (void*) S << ' ';
+ S->printPretty(Out);
+
+ if (SLoc.isFileID()) {
+ Out << "\\lline="
+ << GraphPrintSourceManager->getLineNumber(SLoc) << " col="
+ << GraphPrintSourceManager->getColumnNumber(SLoc) << "\\l";
+ }
+
+ if (GraphPrintCheckerState->isImplicitNullDeref(N))
+ Out << "\\|Implicit-Null Dereference.\\l";
+ else if (GraphPrintCheckerState->isExplicitNullDeref(N))
+ Out << "\\|Explicit-Null Dereference.\\l";
+ else if (GraphPrintCheckerState->isUndefDeref(N))
+ Out << "\\|Dereference of undefialied value.\\l";
+ else if (GraphPrintCheckerState->isUndefStore(N))
+ Out << "\\|Store to Undefined LVal.";
+ else if (GraphPrintCheckerState->isExplicitBadDivide(N))
+ Out << "\\|Explicit divide-by zero or undefined value.";
+ else if (GraphPrintCheckerState->isImplicitBadDivide(N))
+ Out << "\\|Implicit divide-by zero or undefined value.";
+ else if (GraphPrintCheckerState->isUndefResult(N))
+ Out << "\\|Result of operation is undefined.";
+ else if (GraphPrintCheckerState->isNoReturnCall(N))
+ Out << "\\|Call to function marked \"noreturn\".";
+ else if (GraphPrintCheckerState->isBadCall(N))
+ Out << "\\|Call to NULL/Undefined.";
+ else if (GraphPrintCheckerState->isUndefArg(N))
+ Out << "\\|Argument in call is undefined";
+
+ break;
+ }
+
+ default: {
+ const BlockEdge& E = cast<BlockEdge>(Loc);
+ Out << "Edge: (B" << E.getSrc()->getBlockID() << ", B"
+ << E.getDst()->getBlockID() << ')';
+
+ if (Stmt* T = E.getSrc()->getTerminator()) {
+
+ SourceLocation SLoc = T->getLocStart();
+
+ Out << "\\|Terminator: ";
+
+ E.getSrc()->printTerminator(Out);
+
+ if (SLoc.isFileID()) {
+ Out << "\\lline="
+ << GraphPrintSourceManager->getLineNumber(SLoc) << " col="
+ << GraphPrintSourceManager->getColumnNumber(SLoc);
+ }
+
+ if (isa<SwitchStmt>(T)) {
+ Stmt* Label = E.getDst()->getLabel();
+
+ if (Label) {
+ if (CaseStmt* C = dyn_cast<CaseStmt>(Label)) {
+ Out << "\\lcase ";
+ C->getLHS()->printPretty(Out);
+
+ if (Stmt* RHS = C->getRHS()) {
+ Out << " .. ";
+ RHS->printPretty(Out);
+ }
+
+ Out << ":";
+ }
+ else {
+ assert (isa<DefaultStmt>(Label));
+ Out << "\\ldefault:";
+ }
+ }
+ else
+ Out << "\\l(implicit) default:";
+ }
+ else if (isa<IndirectGotoStmt>(T)) {
+ // FIXME
+ }
+ else {
+ Out << "\\lCondition: ";
+ if (*E.getSrc()->succ_begin() == E.getDst())
+ Out << "true";
+ else
+ Out << "false";
+ }
+
+ Out << "\\l";
+ }
+
+ if (GraphPrintCheckerState->isUndefControlFlow(N)) {
+ Out << "\\|Control-flow based on\\lUndefined value.\\l";
+ }
+ }
+ }
+
+ Out << "\\|StateID: " << (void*) N->getState() << "\\|";
+
+ N->getState()->printDOT(Out, GraphCheckerStatePrinter);
+
+ Out << "\\l";
+ return Out.str();
+ }
+};
+} // end llvm namespace
+#endif
+
+#ifndef NDEBUG
+
+template <typename ITERATOR>
+GRExprEngine::NodeTy* GetGraphNode(ITERATOR I) { return *I; }
+
+template <>
+GRExprEngine::NodeTy*
+GetGraphNode<llvm::DenseMap<GRExprEngine::NodeTy*, Expr*>::iterator>
+ (llvm::DenseMap<GRExprEngine::NodeTy*, Expr*>::iterator I) {
+ return I->first;
+}
+
+template <typename ITERATOR>
+static void AddSources(llvm::SmallVector<GRExprEngine::NodeTy*, 10>& Sources,
+ ITERATOR I, ITERATOR E) {
+
+ llvm::SmallPtrSet<void*,10> CachedSources;
+
+ for ( ; I != E; ++I ) {
+ GRExprEngine::NodeTy* N = GetGraphNode(I);
+ void* p = N->getLocation().getRawData();
+
+ if (CachedSources.count(p))
+ continue;
+
+ CachedSources.insert(p);
+
+ Sources.push_back(N);
+ }
+}
+#endif
+
+void GRExprEngine::ViewGraph(bool trim) {
+#ifndef NDEBUG
+ if (trim) {
+ llvm::SmallVector<NodeTy*, 10> Src;
+ AddSources(Src, null_derefs_begin(), null_derefs_end());
+ AddSources(Src, undef_derefs_begin(), undef_derefs_end());
+ AddSources(Src, explicit_bad_divides_begin(), explicit_bad_divides_end());
+ AddSources(Src, undef_results_begin(), undef_results_end());
+ AddSources(Src, bad_calls_begin(), bad_calls_end());
+ AddSources(Src, undef_arg_begin(), undef_arg_end());
+ AddSources(Src, undef_branches_begin(), undef_branches_end());
+
+ ViewGraph(&Src[0], &Src[0]+Src.size());
+ }
+ else {
+ GraphPrintCheckerState = this;
+ GraphPrintSourceManager = &getContext().getSourceManager();
+ GraphCheckerStatePrinter = TF->getCheckerStatePrinter();
+
+ llvm::ViewGraph(*G.roots_begin(), "GRExprEngine");
+
+ GraphPrintCheckerState = NULL;
+ GraphPrintSourceManager = NULL;
+ GraphCheckerStatePrinter = NULL;
+ }
+#endif
+}
+
+void GRExprEngine::ViewGraph(NodeTy** Beg, NodeTy** End) {
+#ifndef NDEBUG
+ GraphPrintCheckerState = this;
+ GraphPrintSourceManager = &getContext().getSourceManager();
+ GraphCheckerStatePrinter = TF->getCheckerStatePrinter();
+
+ GRExprEngine::GraphTy* TrimmedG = G.Trim(Beg, End);
+
+ if (!TrimmedG)
+ llvm::cerr << "warning: Trimmed ExplodedGraph is empty.\n";
+ else {
+ llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedGRExprEngine");
+ delete TrimmedG;
+ }
+
+ GraphPrintCheckerState = NULL;
+ GraphPrintSourceManager = NULL;
+ GraphCheckerStatePrinter = NULL;
+#endif
+}
diff --git a/lib/Analysis/GRSimpleVals.cpp b/lib/Analysis/GRSimpleVals.cpp
new file mode 100644
index 0000000..3777d53
--- /dev/null
+++ b/lib/Analysis/GRSimpleVals.cpp
@@ -0,0 +1,462 @@
+// GRSimpleVals.cpp - Transfer functions for tracking simple 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 defines GRSimpleVals, a sub-class of GRTransferFuncs that
+// provides transfer functions for performing simple value tracking with
+// limited support for symbolics.
+//
+//===----------------------------------------------------------------------===//
+
+#include "GRSimpleVals.h"
+#include "clang/Analysis/PathSensitive/ValueState.h"
+#include "clang/Basic/Diagnostic.h"
+#include <sstream>
+
+using namespace clang;
+
+namespace clang {
+
+template <typename ITERATOR>
+static inline ProgramPoint GetLocation(ITERATOR I) {
+ return (*I)->getLocation();
+}
+
+template <>
+inline ProgramPoint GetLocation(GRExprEngine::undef_arg_iterator I) {
+ return I->first->getLocation();
+}
+
+static inline Stmt* GetStmt(const ProgramPoint& P) {
+ if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) {
+ return PS->getStmt();
+ }
+ else if (const BlockEdge* BE = dyn_cast<BlockEdge>(&P)) {
+ return BE->getSrc()->getTerminator();
+ }
+
+ assert (false && "Unsupported ProgramPoint.");
+ return NULL;
+}
+
+template <typename ITERATOR>
+static void EmitDiag(Diagnostic& Diag, SourceManager& SrcMgr,
+ unsigned ErrorDiag, ITERATOR I) {
+
+ Stmt* S = GetStmt(GetLocation(I));
+ Diag.Report(FullSourceLoc(S->getLocStart(), SrcMgr), ErrorDiag);
+}
+
+
+template <>
+static void EmitDiag(Diagnostic& Diag, SourceManager& SrcMgr,
+ unsigned ErrorDiag, GRExprEngine::undef_arg_iterator I) {
+
+ Stmt* S1 = GetStmt(GetLocation(I));
+ Expr* E2 = cast<Expr>(I->second);
+
+ SourceLocation Loc = S1->getLocStart();
+ SourceRange R = E2->getSourceRange();
+ Diag.Report(FullSourceLoc(Loc, SrcMgr), ErrorDiag, 0, 0, &R, 1);
+}
+
+template <typename ITERATOR>
+void EmitWarning(Diagnostic& Diag, SourceManager& SrcMgr,
+ ITERATOR I, ITERATOR E, const char* msg) {
+
+ std::ostringstream Out;
+ Out << "[CHECKER] " << msg;
+ msg = Out.str().c_str();
+
+ bool isFirst = true;
+ unsigned ErrorDiag = 0;
+ llvm::SmallPtrSet<void*,10> CachedErrors;
+
+ for (; I != E; ++I) {
+
+ if (isFirst) {
+ isFirst = false;
+ ErrorDiag = Diag.getCustomDiagID(Diagnostic::Warning, msg);
+ }
+ else {
+
+ // HACK: Cache the location of the error. Don't emit the same
+ // warning for the same error type that occurs at the same program
+ // location but along a different path.
+ void* p = GetLocation(I).getRawData();
+
+ if (CachedErrors.count(p))
+ continue;
+
+ CachedErrors.insert(p);
+ }
+
+ EmitDiag(Diag, SrcMgr, ErrorDiag, I);
+ }
+}
+
+unsigned RunGRSimpleVals(CFG& cfg, Decl& CD, ASTContext& Ctx,
+ Diagnostic& Diag, bool Visualize, bool TrimGraph) {
+
+ if (Diag.hasErrorOccurred())
+ return 0;
+
+ GRCoreEngine<GRExprEngine> Eng(cfg, CD, Ctx);
+ GRExprEngine* CheckerState = &Eng.getCheckerState();
+ GRSimpleVals GRSV;
+ CheckerState->setTransferFunctions(GRSV);
+
+ // Execute the worklist algorithm.
+ Eng.ExecuteWorkList(100000);
+
+ SourceManager& SrcMgr = Ctx.getSourceManager();
+
+ EmitWarning(Diag, SrcMgr,
+ CheckerState->null_derefs_begin(),
+ CheckerState->null_derefs_end(),
+ "NULL pointer is dereferenced after it is checked for NULL.");
+
+ EmitWarning(Diag, SrcMgr,
+ CheckerState->undef_derefs_begin(),
+ CheckerState->undef_derefs_end(),
+ "Dereference of undefined value.");
+
+ EmitWarning(Diag, SrcMgr,
+ CheckerState->undef_derefs_begin(),
+ CheckerState->undef_derefs_end(),
+ "Dereference of undefined value.");
+
+ EmitWarning(Diag, SrcMgr,
+ CheckerState->explicit_bad_divides_begin(),
+ CheckerState->explicit_bad_divides_end(),
+ "Division by zero/undefined value.");
+
+ EmitWarning(Diag, SrcMgr,
+ CheckerState->undef_results_begin(),
+ CheckerState->undef_results_end(),
+ "Result of operation is undefined.");
+
+ EmitWarning(Diag, SrcMgr,
+ CheckerState->bad_calls_begin(),
+ CheckerState->bad_calls_end(),
+ "Call using a NULL or undefined function pointer value.");
+
+ EmitWarning(Diag, SrcMgr,
+ CheckerState->undef_arg_begin(),
+ CheckerState->undef_arg_end(),
+ "Pass-by-value argument in function or message expression is undefined.");
+
+ EmitWarning(Diag, SrcMgr,
+ CheckerState->undef_branches_begin(),
+ CheckerState->undef_branches_end(),
+ "Branch condition evaluates to an uninitialized value.");
+
+#ifndef NDEBUG
+ if (Visualize) CheckerState->ViewGraph(TrimGraph);
+#endif
+
+ return Eng.getGraph().size();
+}
+
+} // end clang namespace
+
+//===----------------------------------------------------------------------===//
+// Transfer function for Casts.
+//===----------------------------------------------------------------------===//
+
+RVal GRSimpleVals::EvalCast(GRExprEngine& Eng, NonLVal X, QualType T) {
+
+ if (!isa<nonlval::ConcreteInt>(X))
+ return UnknownVal();
+
+ BasicValueFactory& BasicVals = Eng.getBasicVals();
+
+ llvm::APSInt V = cast<nonlval::ConcreteInt>(X).getValue();
+ V.setIsUnsigned(T->isUnsignedIntegerType() || T->isPointerType()
+ || T->isObjCQualifiedIdType());
+ V.extOrTrunc(Eng.getContext().getTypeSize(T));
+
+ if (T->isPointerType())
+ return lval::ConcreteInt(BasicVals.getValue(V));
+ else
+ return nonlval::ConcreteInt(BasicVals.getValue(V));
+}
+
+// Casts.
+
+RVal GRSimpleVals::EvalCast(GRExprEngine& Eng, LVal X, QualType T) {
+
+ if (T->isPointerType() || T->isReferenceType() || T->isObjCQualifiedIdType())
+ return X;
+
+ assert (T->isIntegerType());
+
+ if (!isa<lval::ConcreteInt>(X))
+ return UnknownVal();
+
+ BasicValueFactory& BasicVals = Eng.getBasicVals();
+
+ llvm::APSInt V = cast<lval::ConcreteInt>(X).getValue();
+ V.setIsUnsigned(T->isUnsignedIntegerType() || T->isPointerType());
+ V.extOrTrunc(Eng.getContext().getTypeSize(T));
+
+ return nonlval::ConcreteInt(BasicVals.getValue(V));
+}
+
+// Unary operators.
+
+RVal GRSimpleVals::EvalMinus(GRExprEngine& Eng, UnaryOperator* U, NonLVal X){
+
+ switch (X.getSubKind()) {
+
+ case nonlval::ConcreteIntKind:
+ return cast<nonlval::ConcreteInt>(X).EvalMinus(Eng.getBasicVals(), U);
+
+ default:
+ return UnknownVal();
+ }
+}
+
+RVal GRSimpleVals::EvalComplement(GRExprEngine& Eng, NonLVal X) {
+
+ switch (X.getSubKind()) {
+
+ case nonlval::ConcreteIntKind:
+ return cast<nonlval::ConcreteInt>(X).EvalComplement(Eng.getBasicVals());
+
+ default:
+ return UnknownVal();
+ }
+}
+
+// Binary operators.
+
+RVal GRSimpleVals::EvalBinOp(GRExprEngine& Eng, BinaryOperator::Opcode Op,
+ NonLVal L, NonLVal R) {
+
+ BasicValueFactory& BasicVals = Eng.getBasicVals();
+
+ while (1) {
+
+ switch (L.getSubKind()) {
+ default:
+ return UnknownVal();
+
+ case nonlval::ConcreteIntKind:
+
+ if (isa<nonlval::ConcreteInt>(R)) {
+ const nonlval::ConcreteInt& L_CI = cast<nonlval::ConcreteInt>(L);
+ const nonlval::ConcreteInt& R_CI = cast<nonlval::ConcreteInt>(R);
+ return L_CI.EvalBinOp(BasicVals, Op, R_CI);
+ }
+ else {
+ NonLVal tmp = R;
+ R = L;
+ L = tmp;
+ continue;
+ }
+
+ case nonlval::SymbolValKind: {
+
+ if (isa<nonlval::ConcreteInt>(R)) {
+ const SymIntConstraint& C =
+ BasicVals.getConstraint(cast<nonlval::SymbolVal>(L).getSymbol(), Op,
+ cast<nonlval::ConcreteInt>(R).getValue());
+
+ return nonlval::SymIntConstraintVal(C);
+ }
+ else
+ return UnknownVal();
+ }
+ }
+ }
+}
+
+
+// Binary Operators (except assignments and comma).
+
+RVal GRSimpleVals::EvalBinOp(GRExprEngine& Eng, BinaryOperator::Opcode Op,
+ LVal L, LVal R) {
+
+ switch (Op) {
+
+ default:
+ return UnknownVal();
+
+ case BinaryOperator::EQ:
+ return EvalEQ(Eng, L, R);
+
+ case BinaryOperator::NE:
+ return EvalNE(Eng, L, R);
+ }
+}
+
+// Pointer arithmetic.
+
+RVal GRSimpleVals::EvalBinOp(GRExprEngine& Eng, BinaryOperator::Opcode Op,
+ LVal L, NonLVal R) {
+ return UnknownVal();
+}
+
+// Equality operators for LVals.
+
+RVal GRSimpleVals::EvalEQ(GRExprEngine& Eng, LVal L, LVal R) {
+
+ BasicValueFactory& BasicVals = Eng.getBasicVals();
+
+ switch (L.getSubKind()) {
+
+ default:
+ assert(false && "EQ not implemented for this LVal.");
+ return UnknownVal();
+
+ case lval::ConcreteIntKind:
+
+ if (isa<lval::ConcreteInt>(R)) {
+ bool b = cast<lval::ConcreteInt>(L).getValue() ==
+ cast<lval::ConcreteInt>(R).getValue();
+
+ return NonLVal::MakeIntTruthVal(BasicVals, b);
+ }
+ else if (isa<lval::SymbolVal>(R)) {
+
+ const SymIntConstraint& C =
+ BasicVals.getConstraint(cast<lval::SymbolVal>(R).getSymbol(),
+ BinaryOperator::EQ,
+ cast<lval::ConcreteInt>(L).getValue());
+
+ return nonlval::SymIntConstraintVal(C);
+ }
+
+ break;
+
+ case lval::SymbolValKind: {
+
+ if (isa<lval::ConcreteInt>(R)) {
+ const SymIntConstraint& C =
+ BasicVals.getConstraint(cast<lval::SymbolVal>(L).getSymbol(),
+ BinaryOperator::EQ,
+ cast<lval::ConcreteInt>(R).getValue());
+
+ return nonlval::SymIntConstraintVal(C);
+ }
+
+ // FIXME: Implement == for lval Symbols. This is mainly useful
+ // in iterator loops when traversing a buffer, e.g. while(z != zTerm).
+ // Since this is not useful for many checkers we'll punt on this for
+ // now.
+
+ return UnknownVal();
+ }
+
+ case lval::DeclValKind:
+ case lval::FuncValKind:
+ case lval::GotoLabelKind:
+ return NonLVal::MakeIntTruthVal(BasicVals, L == R);
+ }
+
+ return NonLVal::MakeIntTruthVal(BasicVals, false);
+}
+
+RVal GRSimpleVals::EvalNE(GRExprEngine& Eng, LVal L, LVal R) {
+
+ BasicValueFactory& BasicVals = Eng.getBasicVals();
+
+ switch (L.getSubKind()) {
+
+ default:
+ assert(false && "NE not implemented for this LVal.");
+ return UnknownVal();
+
+ case lval::ConcreteIntKind:
+
+ if (isa<lval::ConcreteInt>(R)) {
+ bool b = cast<lval::ConcreteInt>(L).getValue() !=
+ cast<lval::ConcreteInt>(R).getValue();
+
+ return NonLVal::MakeIntTruthVal(BasicVals, b);
+ }
+ else if (isa<lval::SymbolVal>(R)) {
+ const SymIntConstraint& C =
+ BasicVals.getConstraint(cast<lval::SymbolVal>(R).getSymbol(),
+ BinaryOperator::NE,
+ cast<lval::ConcreteInt>(L).getValue());
+
+ return nonlval::SymIntConstraintVal(C);
+ }
+
+ break;
+
+ case lval::SymbolValKind: {
+ if (isa<lval::ConcreteInt>(R)) {
+ const SymIntConstraint& C =
+ BasicVals.getConstraint(cast<lval::SymbolVal>(L).getSymbol(),
+ BinaryOperator::NE,
+ cast<lval::ConcreteInt>(R).getValue());
+
+ return nonlval::SymIntConstraintVal(C);
+ }
+
+ // FIXME: Implement != for lval Symbols. This is mainly useful
+ // in iterator loops when traversing a buffer, e.g. while(z != zTerm).
+ // Since this is not useful for many checkers we'll punt on this for
+ // now.
+
+ return UnknownVal();
+
+ break;
+ }
+
+ case lval::DeclValKind:
+ case lval::FuncValKind:
+ case lval::GotoLabelKind:
+ return NonLVal::MakeIntTruthVal(BasicVals, L != R);
+ }
+
+ return NonLVal::MakeIntTruthVal(BasicVals, true);
+}
+
+//===----------------------------------------------------------------------===//
+// Transfer function for Function Calls.
+//===----------------------------------------------------------------------===//
+
+void GRSimpleVals::EvalCall(ExplodedNodeSet<ValueState>& Dst,
+ GRExprEngine& Eng,
+ GRStmtNodeBuilder<ValueState>& Builder,
+ CallExpr* CE, LVal L,
+ ExplodedNode<ValueState>* Pred) {
+
+ ValueStateManager& StateMgr = Eng.getStateManager();
+ ValueState* St = Builder.GetState(Pred);
+
+ // Invalidate all arguments passed in by reference (LVals).
+
+ for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();
+ I != E; ++I) {
+
+ RVal V = StateMgr.GetRVal(St, *I);
+
+ if (isa<LVal>(V))
+ St = StateMgr.SetRVal(St, cast<LVal>(V), UnknownVal());
+ }
+
+ // Make up a symbol for the return value of this function.
+
+ if (CE->getType() != Eng.getContext().VoidTy) {
+ unsigned Count = Builder.getCurrentBlockCount();
+ SymbolID Sym = Eng.getSymbolManager().getConjuredSymbol(CE, Count);
+
+ RVal X = CE->getType()->isPointerType()
+ ? cast<RVal>(lval::SymbolVal(Sym))
+ : cast<RVal>(nonlval::SymbolVal(Sym));
+
+ St = StateMgr.SetRVal(St, CE, X, Eng.getCFG().isBlkExpr(CE), false);
+ }
+
+ Builder.Nodify(Dst, CE, Pred, St);
+}
diff --git a/lib/Analysis/GRSimpleVals.h b/lib/Analysis/GRSimpleVals.h
new file mode 100644
index 0000000..2b3d0fd
--- /dev/null
+++ b/lib/Analysis/GRSimpleVals.h
@@ -0,0 +1,71 @@
+// GRSimpleVals.h - Transfer functions for tracking simple 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 defines GRSimpleVals, a sub-class of GRTransferFuncs that
+// provides transfer functions for performing simple value tracking with
+// limited support for symbolics.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_GRSIMPLEVALS
+#define LLVM_CLANG_ANALYSIS_GRSIMPLEVALS
+
+#include "clang/Analysis/PathSensitive/GRTransferFuncs.h"
+#include "clang/Analysis/PathSensitive/GRExprEngine.h"
+
+namespace clang {
+
+class GRSimpleVals : public GRTransferFuncs {
+public:
+ GRSimpleVals() {}
+ virtual ~GRSimpleVals() {}
+
+ // Casts.
+
+ virtual RVal EvalCast(GRExprEngine& Engine, NonLVal V, QualType CastT);
+ virtual RVal EvalCast(GRExprEngine& Engine, LVal V, QualType CastT);
+
+ // Unary Operators.
+
+ virtual RVal EvalMinus(GRExprEngine& Engine, UnaryOperator* U, NonLVal X);
+
+ virtual RVal EvalComplement(GRExprEngine& Engine, NonLVal X);
+
+ // Binary Operators.
+
+ virtual RVal EvalBinOp(GRExprEngine& Engine, BinaryOperator::Opcode Op,
+ NonLVal L, NonLVal R);
+
+ virtual RVal EvalBinOp(GRExprEngine& Engine, BinaryOperator::Opcode Op,
+ LVal L, LVal R);
+
+ // Pointer arithmetic.
+
+ virtual RVal EvalBinOp(GRExprEngine& Engine, BinaryOperator::Opcode Op,
+ LVal L, NonLVal R);
+
+ // Calls.
+
+ virtual void EvalCall(ExplodedNodeSet<ValueState>& Dst,
+ GRExprEngine& Engine,
+ GRStmtNodeBuilder<ValueState>& Builder,
+ CallExpr* CE, LVal L,
+ ExplodedNode<ValueState>* Pred);
+
+protected:
+
+ // Equality operators for LVals.
+
+ RVal EvalEQ(GRExprEngine& Engine, LVal L, LVal R);
+ RVal EvalNE(GRExprEngine& Engine, LVal L, LVal R);
+};
+
+} // end clang namespace
+
+#endif
diff --git a/lib/Analysis/LiveVariables.cpp b/lib/Analysis/LiveVariables.cpp
new file mode 100644
index 0000000..e59a488
--- /dev/null
+++ b/lib/Analysis/LiveVariables.cpp
@@ -0,0 +1,246 @@
+//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+// details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements Live Variables analysis for source-level CFGs.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/Analyses/LiveVariables.h"
+#include "clang/Basic/SourceManager.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/CFG.h"
+#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
+#include "clang/Analysis/FlowSensitive/DataflowSolver.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Support/Compiler.h"
+
+#include <string.h>
+#include <stdio.h>
+
+using namespace clang;
+
+//===----------------------------------------------------------------------===//
+// Dataflow initialization logic.
+//===----------------------------------------------------------------------===//
+
+namespace {
+class VISIBILITY_HIDDEN RegisterDecls
+ : public CFGRecStmtDeclVisitor<RegisterDecls> {
+
+ LiveVariables::AnalysisDataTy& AD;
+public:
+ RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
+ void VisitVarDecl(VarDecl* VD) { AD.Register(VD); }
+ CFG& getCFG() { return AD.getCFG(); }
+};
+} // end anonymous namespace
+
+
+LiveVariables::LiveVariables(CFG& cfg) {
+ // Register all referenced VarDecls.
+ getAnalysisData().setCFG(&cfg);
+ RegisterDecls R(getAnalysisData());
+ cfg.VisitBlockStmts(R);
+}
+
+//===----------------------------------------------------------------------===//
+// Transfer functions.
+//===----------------------------------------------------------------------===//
+
+namespace {
+
+static const bool Alive = true;
+static const bool Dead = false;
+
+class VISIBILITY_HIDDEN TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
+ LiveVariables::AnalysisDataTy& AD;
+ LiveVariables::ValTy LiveState;
+public:
+ TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
+
+ LiveVariables::ValTy& getVal() { return LiveState; }
+ CFG& getCFG() { return AD.getCFG(); }
+
+ void VisitDeclRefExpr(DeclRefExpr* DR);
+ void VisitBinaryOperator(BinaryOperator* B);
+ void VisitAssign(BinaryOperator* B);
+ void VisitDeclStmt(DeclStmt* DS);
+ void VisitUnaryOperator(UnaryOperator* U);
+ void Visit(Stmt *S);
+};
+
+void TransferFuncs::Visit(Stmt *S) {
+ if (AD.Observer)
+ AD.Observer->ObserveStmt(S,AD,LiveState);
+
+ if (S == getCurrentBlkStmt()) {
+ if (getCFG().isBlkExpr(S)) LiveState(S,AD) = Dead;
+ StmtVisitor<TransferFuncs,void>::Visit(S);
+ }
+ else if (!getCFG().isBlkExpr(S))
+ StmtVisitor<TransferFuncs,void>::Visit(S);
+ else
+ // For block-level expressions, mark that they are live.
+ LiveState(S,AD) = Alive;
+}
+
+void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
+ if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
+ LiveState(V,AD) = Alive;
+}
+
+void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
+ if (B->isAssignmentOp()) VisitAssign(B);
+ else VisitStmt(B);
+}
+
+void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
+ Expr *E = U->getSubExpr();
+
+ switch (U->getOpcode()) {
+ case UnaryOperator::SizeOf: return;
+ case UnaryOperator::PostInc:
+ case UnaryOperator::PostDec:
+ case UnaryOperator::PreInc:
+ case UnaryOperator::PreDec:
+ case UnaryOperator::AddrOf:
+ // Walk through the subexpressions, blasting through ParenExprs
+ // until we either find a DeclRefExpr or some non-DeclRefExpr
+ // expression.
+ if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens()))
+ if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
+ // Treat the --/++/& operator as a kill.
+ LiveState(VD, AD) = Dead;
+ if (AD.Observer) { AD.Observer->ObserverKill(DR); }
+ return VisitDeclRefExpr(DR);
+ }
+
+ // Fall-through.
+
+ default:
+ return Visit(E);
+ }
+}
+
+void TransferFuncs::VisitAssign(BinaryOperator* B) {
+ Expr* LHS = B->getLHS();
+
+ // Assigning to a variable?
+ if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) {
+ LiveState(DR->getDecl(),AD) = Dead;
+ if (AD.Observer) { AD.Observer->ObserverKill(DR); }
+
+ // Handle things like +=, etc., which also generate "uses"
+ // of a variable. Do this just by visiting the subexpression.
+ if (B->getOpcode() != BinaryOperator::Assign)
+ VisitDeclRefExpr(DR);
+ }
+ else // Not assigning to a variable. Process LHS as usual.
+ Visit(LHS);
+
+ Visit(B->getRHS());
+}
+
+void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
+ // Declarations effectively "kill" a variable since they cannot
+ // possibly be live before they are declared.
+ for (ScopedDecl* D = DS->getDecl(); D != NULL; D = D->getNextDeclarator())
+ if (VarDecl* VD = dyn_cast<VarDecl>(D)) {
+ LiveState(D,AD) = Dead;
+
+ if (Expr* Init = VD->getInit())
+ Visit(Init);
+ }
+}
+
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// Merge operator: if something is live on any successor block, it is live
+// in the current block (a set union).
+//===----------------------------------------------------------------------===//
+
+namespace {
+typedef ExprDeclBitVector_Types::Union Merge;
+typedef DataflowSolver<LiveVariables,TransferFuncs,Merge> Solver;
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// External interface to run Liveness analysis.
+//===----------------------------------------------------------------------===//
+
+void LiveVariables::runOnCFG(CFG& cfg) {
+ Solver S(*this);
+ S.runOnCFG(cfg);
+}
+
+void LiveVariables::runOnAllBlocks(const CFG& cfg,
+ LiveVariables::ObserverTy* Obs,
+ bool recordStmtValues) {
+ Solver S(*this);
+ ObserverTy* OldObserver = getAnalysisData().Observer;
+ getAnalysisData().Observer = Obs;
+ S.runOnAllBlocks(cfg, recordStmtValues);
+ getAnalysisData().Observer = OldObserver;
+}
+
+//===----------------------------------------------------------------------===//
+// liveness queries
+//
+
+bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
+ DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
+ return i.isValid() ? getBlockData(B).getBit(i) : false;
+}
+
+bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
+ DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
+ return i.isValid() ? Live.getBit(i) : false;
+}
+
+bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
+ return getStmtData(Loc)(StmtVal,getAnalysisData());
+}
+
+bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
+ return getStmtData(Loc)(D,getAnalysisData());
+}
+
+//===----------------------------------------------------------------------===//
+// printing liveness state for debugging
+//
+
+void LiveVariables::dumpLiveness(const ValTy& V, SourceManager& SM) const {
+ const AnalysisDataTy& AD = getAnalysisData();
+
+ for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
+ E = AD.end_decl(); I!=E; ++I)
+ if (V.getDeclBit(I->second)) {
+ SourceLocation PhysLoc = SM.getPhysicalLoc(I->first->getLocation());
+
+ fprintf(stderr, " %s <%s:%u:%u>\n",
+ I->first->getIdentifier()->getName(),
+ SM.getSourceName(PhysLoc),
+ SM.getLineNumber(PhysLoc),
+ SM.getColumnNumber(PhysLoc));
+ }
+}
+
+void LiveVariables::dumpBlockLiveness(SourceManager& M) const {
+ for (BlockDataMapTy::iterator I = getBlockDataMap().begin(),
+ E = getBlockDataMap().end(); I!=E; ++I) {
+ fprintf(stderr, "\n[ B%d (live variables at block exit) ]\n",
+ I->first->getBlockID());
+
+ dumpLiveness(I->second,M);
+ }
+
+ fprintf(stderr,"\n");
+}
diff --git a/lib/Analysis/Makefile b/lib/Analysis/Makefile
new file mode 100644
index 0000000..b1d9178
--- /dev/null
+++ b/lib/Analysis/Makefile
@@ -0,0 +1,22 @@
+##===- clang/lib/Analysis/Makefile -------------------------*- Makefile -*-===##
+#
+# The LLVM Compiler Infrastructure
+#
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+#
+##===----------------------------------------------------------------------===##
+#
+# This implements analyses built on top of source-level CFGs.
+#
+##===----------------------------------------------------------------------===##
+
+LEVEL = ../../../..
+LIBRARYNAME := clangAnalysis
+BUILD_ARCHIVE = 1
+CXXFLAGS = -fno-rtti
+
+CPPFLAGS += -I$(PROJ_SRC_DIR)/../../include
+
+include $(LEVEL)/Makefile.common
+
diff --git a/lib/Analysis/ProgramPoint.cpp b/lib/Analysis/ProgramPoint.cpp
new file mode 100644
index 0000000..c089e48
--- /dev/null
+++ b/lib/Analysis/ProgramPoint.cpp
@@ -0,0 +1,65 @@
+//= ProgramPoint.cpp - Program Points for Path-Sensitive Analysis --*- C++ -*-//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements methods for subclasses of ProgramPoint.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/CFG.h"
+#include "clang/Analysis/ProgramPoint.h"
+
+using namespace clang;
+
+BlockEdge::BlockEdge(CFG& cfg, const CFGBlock* B1, const CFGBlock* B2) {
+ if (B1->succ_size() == 1) {
+ assert (*(B1->succ_begin()) == B2);
+ Data = reinterpret_cast<uintptr_t>(B1) | BlockEdgeSrcKind;
+ }
+ else if (B2->pred_size() == 1) {
+ assert (*(B2->pred_begin()) == B1);
+ Data = reinterpret_cast<uintptr_t>(B2) | BlockEdgeDstKind;
+ }
+ else
+ Data = reinterpret_cast<uintptr_t>(cfg.getBlockEdgeImpl(B1,B2))
+ | BlockEdgeAuxKind;
+}
+
+CFGBlock* BlockEdge::getSrc() const {
+ switch (getKind()) {
+ default:
+ assert (false && "Invalid BlockEdgeKind.");
+ return NULL;
+
+ case BlockEdgeSrcKind:
+ return reinterpret_cast<CFGBlock*>(getRawPtr());
+
+ case BlockEdgeDstKind:
+ return *(reinterpret_cast<CFGBlock*>(getRawPtr())->pred_begin());
+
+ case BlockEdgeAuxKind:
+ return reinterpret_cast<BPair*>(getRawPtr())->first;
+ }
+}
+
+CFGBlock* BlockEdge::getDst() const {
+ switch (getKind()) {
+ default:
+ assert (false && "Invalid BlockEdgeKind.");
+ return NULL;
+
+ case BlockEdgeSrcKind:
+ return *(reinterpret_cast<CFGBlock*>(getRawPtr())->succ_begin());
+
+ case BlockEdgeDstKind:
+ return reinterpret_cast<CFGBlock*>(getRawPtr());
+
+ case BlockEdgeAuxKind:
+ return reinterpret_cast<BPair*>(getRawPtr())->second;
+ }
+}
diff --git a/lib/Analysis/RValues.cpp b/lib/Analysis/RValues.cpp
new file mode 100644
index 0000000..a4b4649
--- /dev/null
+++ b/lib/Analysis/RValues.cpp
@@ -0,0 +1,389 @@
+//= RValues.cpp - Abstract RValues for Path-Sens. Value Tracking -*- 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 RVal, LVal, and NonLVal, classes that represent
+// abstract r-values for use with path-sensitive value tracking.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/PathSensitive/RValues.h"
+#include "llvm/Support/Streams.h"
+
+using namespace clang;
+using llvm::dyn_cast;
+using llvm::cast;
+using llvm::APSInt;
+
+//===----------------------------------------------------------------------===//
+// Symbol Iteration.
+//===----------------------------------------------------------------------===//
+
+RVal::symbol_iterator RVal::symbol_begin() const {
+ if (isa<lval::SymbolVal>(this))
+ return (symbol_iterator) (&Data);
+ else if (isa<nonlval::SymbolVal>(this))
+ return (symbol_iterator) (&Data);
+ else if (isa<nonlval::SymIntConstraintVal>(this)) {
+ const SymIntConstraint& C =
+ cast<nonlval::SymIntConstraintVal>(this)->getConstraint();
+
+ return (symbol_iterator) &C.getSymbol();
+ }
+
+ return NULL;
+}
+
+RVal::symbol_iterator RVal::symbol_end() const {
+ symbol_iterator X = symbol_begin();
+ return X ? X+1 : NULL;
+}
+
+//===----------------------------------------------------------------------===//
+// Transfer function dispatch for Non-LVals.
+//===----------------------------------------------------------------------===//
+
+RVal
+nonlval::ConcreteInt::EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
+ const nonlval::ConcreteInt& R) const {
+
+ const llvm::APSInt* X = BasicVals.EvaluateAPSInt(Op, getValue(), R.getValue());
+
+ if (X)
+ return nonlval::ConcreteInt(*X);
+ else
+ return UndefinedVal();
+}
+
+
+ // Bitwise-Complement.
+
+nonlval::ConcreteInt
+nonlval::ConcreteInt::EvalComplement(BasicValueFactory& BasicVals) const {
+ return BasicVals.getValue(~getValue());
+}
+
+ // Unary Minus.
+
+nonlval::ConcreteInt
+nonlval::ConcreteInt::EvalMinus(BasicValueFactory& BasicVals, UnaryOperator* U) const {
+ assert (U->getType() == U->getSubExpr()->getType());
+ assert (U->getType()->isIntegerType());
+ return BasicVals.getValue(-getValue());
+}
+
+//===----------------------------------------------------------------------===//
+// Transfer function dispatch for LVals.
+//===----------------------------------------------------------------------===//
+
+RVal
+lval::ConcreteInt::EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
+ const lval::ConcreteInt& R) const {
+
+ assert (Op == BinaryOperator::Add || Op == BinaryOperator::Sub ||
+ (Op >= BinaryOperator::LT && Op <= BinaryOperator::NE));
+
+ const llvm::APSInt* X = BasicVals.EvaluateAPSInt(Op, getValue(), R.getValue());
+
+ if (X)
+ return lval::ConcreteInt(*X);
+ else
+ return UndefinedVal();
+}
+
+NonLVal LVal::EQ(BasicValueFactory& BasicVals, const LVal& R) const {
+
+ switch (getSubKind()) {
+ default:
+ assert(false && "EQ not implemented for this LVal.");
+ break;
+
+ case lval::ConcreteIntKind:
+ if (isa<lval::ConcreteInt>(R)) {
+ bool b = cast<lval::ConcreteInt>(this)->getValue() ==
+ cast<lval::ConcreteInt>(R).getValue();
+
+ return NonLVal::MakeIntTruthVal(BasicVals, b);
+ }
+ else if (isa<lval::SymbolVal>(R)) {
+
+ const SymIntConstraint& C =
+ BasicVals.getConstraint(cast<lval::SymbolVal>(R).getSymbol(),
+ BinaryOperator::EQ,
+ cast<lval::ConcreteInt>(this)->getValue());
+
+ return nonlval::SymIntConstraintVal(C);
+ }
+
+ break;
+
+ case lval::SymbolValKind: {
+ if (isa<lval::ConcreteInt>(R)) {
+
+ const SymIntConstraint& C =
+ BasicVals.getConstraint(cast<lval::SymbolVal>(this)->getSymbol(),
+ BinaryOperator::EQ,
+ cast<lval::ConcreteInt>(R).getValue());
+
+ return nonlval::SymIntConstraintVal(C);
+ }
+
+ assert (!isa<lval::SymbolVal>(R) && "FIXME: Implement unification.");
+
+ break;
+ }
+
+ case lval::DeclValKind:
+ if (isa<lval::DeclVal>(R)) {
+ bool b = cast<lval::DeclVal>(*this) == cast<lval::DeclVal>(R);
+ return NonLVal::MakeIntTruthVal(BasicVals, b);
+ }
+
+ break;
+ }
+
+ return NonLVal::MakeIntTruthVal(BasicVals, false);
+}
+
+NonLVal LVal::NE(BasicValueFactory& BasicVals, const LVal& R) const {
+ switch (getSubKind()) {
+ default:
+ assert(false && "NE not implemented for this LVal.");
+ break;
+
+ case lval::ConcreteIntKind:
+ if (isa<lval::ConcreteInt>(R)) {
+ bool b = cast<lval::ConcreteInt>(this)->getValue() !=
+ cast<lval::ConcreteInt>(R).getValue();
+
+ return NonLVal::MakeIntTruthVal(BasicVals, b);
+ }
+ else if (isa<lval::SymbolVal>(R)) {
+
+ const SymIntConstraint& C =
+ BasicVals.getConstraint(cast<lval::SymbolVal>(R).getSymbol(),
+ BinaryOperator::NE,
+ cast<lval::ConcreteInt>(this)->getValue());
+
+ return nonlval::SymIntConstraintVal(C);
+ }
+
+ break;
+
+ case lval::SymbolValKind: {
+ if (isa<lval::ConcreteInt>(R)) {
+
+ const SymIntConstraint& C =
+ BasicVals.getConstraint(cast<lval::SymbolVal>(this)->getSymbol(),
+ BinaryOperator::NE,
+ cast<lval::ConcreteInt>(R).getValue());
+
+ return nonlval::SymIntConstraintVal(C);
+ }
+
+ assert (!isa<lval::SymbolVal>(R) && "FIXME: Implement sym !=.");
+
+ break;
+ }
+
+ case lval::DeclValKind:
+ if (isa<lval::DeclVal>(R)) {
+ bool b = cast<lval::DeclVal>(*this) == cast<lval::DeclVal>(R);
+ return NonLVal::MakeIntTruthVal(BasicVals, b);
+ }
+
+ break;
+ }
+
+ return NonLVal::MakeIntTruthVal(BasicVals, true);
+}
+
+//===----------------------------------------------------------------------===//
+// Utility methods for constructing Non-LVals.
+//===----------------------------------------------------------------------===//
+
+NonLVal NonLVal::MakeVal(BasicValueFactory& BasicVals, uint64_t X, QualType T) {
+ return nonlval::ConcreteInt(BasicVals.getValue(X, T));
+}
+
+NonLVal NonLVal::MakeVal(BasicValueFactory& BasicVals, IntegerLiteral* I) {
+
+ return nonlval::ConcreteInt(BasicVals.getValue(APSInt(I->getValue(),
+ I->getType()->isUnsignedIntegerType())));
+}
+
+NonLVal NonLVal::MakeIntTruthVal(BasicValueFactory& BasicVals, bool b) {
+ return nonlval::ConcreteInt(BasicVals.getTruthValue(b));
+}
+
+RVal RVal::GetSymbolValue(SymbolManager& SymMgr, VarDecl* D) {
+
+ QualType T = D->getType();
+
+ if (T->isPointerType() || T->isReferenceType())
+ return lval::SymbolVal(SymMgr.getSymbol(D));
+ else
+ return nonlval::SymbolVal(SymMgr.getSymbol(D));
+}
+
+//===----------------------------------------------------------------------===//
+// Utility methods for constructing LVals.
+//===----------------------------------------------------------------------===//
+
+LVal LVal::MakeVal(AddrLabelExpr* E) { return lval::GotoLabel(E->getLabel()); }
+
+//===----------------------------------------------------------------------===//
+// Utility methods for constructing RVals (both NonLVals and LVals).
+//===----------------------------------------------------------------------===//
+
+RVal RVal::MakeVal(BasicValueFactory& BasicVals, DeclRefExpr* E) {
+
+ ValueDecl* D = cast<DeclRefExpr>(E)->getDecl();
+
+ if (VarDecl* VD = dyn_cast<VarDecl>(D)) {
+ return lval::DeclVal(VD);
+ }
+ else if (EnumConstantDecl* ED = dyn_cast<EnumConstantDecl>(D)) {
+
+ // FIXME: Do we need to cache a copy of this enum, since it
+ // already has persistent storage? We do this because we
+ // are comparing states using pointer equality. Perhaps there is
+ // a better way, since APInts are fairly lightweight.
+
+ return nonlval::ConcreteInt(BasicVals.getValue(ED->getInitVal()));
+ }
+ else if (FunctionDecl* FD = dyn_cast<FunctionDecl>(D)) {
+ return lval::FuncVal(FD);
+ }
+
+ assert (false &&
+ "ValueDecl support for this ValueDecl not implemented.");
+
+ return UnknownVal();
+}
+
+//===----------------------------------------------------------------------===//
+// Pretty-Printing.
+//===----------------------------------------------------------------------===//
+
+void RVal::printStdErr() const { print(*llvm::cerr.stream()); }
+
+void RVal::print(std::ostream& Out) const {
+
+ switch (getBaseKind()) {
+
+ case UnknownKind:
+ Out << "Invalid"; break;
+
+ case NonLValKind:
+ cast<NonLVal>(this)->print(Out); break;
+
+ case LValKind:
+ cast<LVal>(this)->print(Out); break;
+
+ case UndefinedKind:
+ Out << "Undefined"; break;
+
+ default:
+ assert (false && "Invalid RVal.");
+ }
+}
+
+static void printOpcode(std::ostream& Out, BinaryOperator::Opcode Op) {
+
+ switch (Op) {
+ case BinaryOperator::Mul: Out << '*' ; break;
+ case BinaryOperator::Div: Out << '/' ; break;
+ case BinaryOperator::Rem: Out << '%' ; break;
+ case BinaryOperator::Add: Out << '+' ; break;
+ case BinaryOperator::Sub: Out << '-' ; break;
+ case BinaryOperator::Shl: Out << "<<" ; break;
+ case BinaryOperator::Shr: Out << ">>" ; break;
+ case BinaryOperator::LT: Out << "<" ; break;
+ case BinaryOperator::GT: Out << '>' ; break;
+ case BinaryOperator::LE: Out << "<=" ; break;
+ case BinaryOperator::GE: Out << ">=" ; break;
+ case BinaryOperator::EQ: Out << "==" ; break;
+ case BinaryOperator::NE: Out << "!=" ; break;
+ case BinaryOperator::And: Out << '&' ; break;
+ case BinaryOperator::Xor: Out << '^' ; break;
+ case BinaryOperator::Or: Out << '|' ; break;
+
+ default: assert(false && "Not yet implemented.");
+ }
+}
+
+void NonLVal::print(std::ostream& Out) const {
+
+ switch (getSubKind()) {
+
+ case nonlval::ConcreteIntKind:
+ Out << cast<nonlval::ConcreteInt>(this)->getValue().toString();
+
+ if (cast<nonlval::ConcreteInt>(this)->getValue().isUnsigned())
+ Out << 'U';
+
+ break;
+
+ case nonlval::SymbolValKind:
+ Out << '$' << cast<nonlval::SymbolVal>(this)->getSymbol();
+ break;
+
+ case nonlval::SymIntConstraintValKind: {
+ const nonlval::SymIntConstraintVal& C =
+ *cast<nonlval::SymIntConstraintVal>(this);
+
+ Out << '$' << C.getConstraint().getSymbol() << ' ';
+ printOpcode(Out, C.getConstraint().getOpcode());
+ Out << ' ' << C.getConstraint().getInt().toString();
+
+ if (C.getConstraint().getInt().isUnsigned())
+ Out << 'U';
+
+ break;
+ }
+
+ default:
+ assert (false && "Pretty-printed not implemented for this NonLVal.");
+ break;
+ }
+}
+
+void LVal::print(std::ostream& Out) const {
+
+ switch (getSubKind()) {
+
+ case lval::ConcreteIntKind:
+ Out << cast<lval::ConcreteInt>(this)->getValue().toString()
+ << " (LVal)";
+ break;
+
+ case lval::SymbolValKind:
+ Out << '$' << cast<lval::SymbolVal>(this)->getSymbol();
+ break;
+
+ case lval::GotoLabelKind:
+ Out << "&&"
+ << cast<lval::GotoLabel>(this)->getLabel()->getID()->getName();
+ break;
+
+ case lval::DeclValKind:
+ Out << '&'
+ << cast<lval::DeclVal>(this)->getDecl()->getIdentifier()->getName();
+ break;
+
+ case lval::FuncValKind:
+ Out << "function "
+ << cast<lval::FuncVal>(this)->getDecl()->getIdentifier()->getName();
+ break;
+
+ default:
+ assert (false && "Pretty-printing not implemented for this LVal.");
+ break;
+ }
+}
diff --git a/lib/Analysis/SymbolManager.cpp b/lib/Analysis/SymbolManager.cpp
new file mode 100644
index 0000000..f243fa66
--- /dev/null
+++ b/lib/Analysis/SymbolManager.cpp
@@ -0,0 +1,124 @@
+//== SymbolManager.h - Management of Symbolic 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 defines SymbolManager, a class that manages symbolic values
+// created for use by GRExprEngine and related classes.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/PathSensitive/SymbolManager.h"
+
+using namespace clang;
+
+SymbolID SymbolManager::getSymbol(VarDecl* D) {
+
+ assert (isa<ParmVarDecl>(D) || D->hasGlobalStorage());
+
+ llvm::FoldingSetNodeID profile;
+
+ ParmVarDecl* PD = dyn_cast<ParmVarDecl>(D);
+
+ if (PD)
+ SymbolDataParmVar::Profile(profile, PD);
+ else
+ SymbolDataGlobalVar::Profile(profile, D);
+
+ void* InsertPos;
+
+ SymbolData* SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
+
+ if (SD)
+ return SD->getSymbol();
+
+ if (PD) {
+ SD = (SymbolData*) BPAlloc.Allocate<SymbolDataParmVar>();
+ new (SD) SymbolDataParmVar(SymbolCounter, PD);
+ }
+ else {
+ SD = (SymbolData*) BPAlloc.Allocate<SymbolDataGlobalVar>();
+ new (SD) SymbolDataGlobalVar(SymbolCounter, D);
+ }
+
+ DataSet.InsertNode(SD, InsertPos);
+
+ DataMap[SymbolCounter] = SD;
+ return SymbolCounter++;
+}
+
+SymbolID SymbolManager::getContentsOfSymbol(SymbolID sym) {
+
+ llvm::FoldingSetNodeID profile;
+ SymbolDataContentsOf::Profile(profile, sym);
+ void* InsertPos;
+
+ SymbolData* SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
+
+ if (SD)
+ return SD->getSymbol();
+
+ SD = (SymbolData*) BPAlloc.Allocate<SymbolDataContentsOf>();
+ new (SD) SymbolDataContentsOf(SymbolCounter, sym);
+
+
+ DataSet.InsertNode(SD, InsertPos);
+ DataMap[SymbolCounter] = SD;
+
+ return SymbolCounter++;
+}
+
+SymbolID SymbolManager::getConjuredSymbol(Expr* E, unsigned Count) {
+
+ llvm::FoldingSetNodeID profile;
+ SymbolConjured::Profile(profile, E, Count);
+ void* InsertPos;
+
+ SymbolData* SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
+
+ if (SD)
+ return SD->getSymbol();
+
+ SD = (SymbolData*) BPAlloc.Allocate<SymbolConjured>();
+ new (SD) SymbolConjured(SymbolCounter, E, Count);
+
+ DataSet.InsertNode(SD, InsertPos);
+ DataMap[SymbolCounter] = SD;
+
+ return SymbolCounter++;
+}
+
+const SymbolData& SymbolManager::getSymbolData(SymbolID Sym) const {
+ DataMapTy::const_iterator I = DataMap.find(Sym);
+ assert (I != DataMap.end());
+ return *I->second;
+}
+
+
+QualType SymbolData::getType(const SymbolManager& SymMgr) const {
+ switch (getKind()) {
+ default:
+ assert (false && "getType() not implemented for this symbol.");
+
+ case ParmKind:
+ return cast<SymbolDataParmVar>(this)->getDecl()->getType();
+
+ case GlobalKind:
+ return cast<SymbolDataGlobalVar>(this)->getDecl()->getType();
+
+ case ContentsOfKind: {
+ SymbolID x = cast<SymbolDataContentsOf>(this)->getContainerSymbol();
+ QualType T = SymMgr.getSymbolData(x).getType(SymMgr);
+ return T->getAsPointerType()->getPointeeType();
+ }
+
+ case ConjuredKind:
+ return cast<SymbolConjured>(this)->getExpr()->getType();
+ }
+}
+
+SymbolManager::~SymbolManager() {}
diff --git a/lib/Analysis/UninitializedValues.cpp b/lib/Analysis/UninitializedValues.cpp
new file mode 100644
index 0000000..25a5ecb
--- /dev/null
+++ b/lib/Analysis/UninitializedValues.cpp
@@ -0,0 +1,277 @@
+//==- UninitializedValues.cpp - Find Unintialized 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 implements Uninitialized Values analysis for source-level CFGs.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/Analyses/UninitializedValues.h"
+#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
+#include "clang/Analysis/LocalCheckers.h"
+#include "clang/Basic/Diagnostic.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/Analysis/FlowSensitive/DataflowSolver.h"
+#include "llvm/Support/Compiler.h"
+
+#include "llvm/ADT/SmallPtrSet.h"
+
+using namespace clang;
+
+//===----------------------------------------------------------------------===//
+// Dataflow initialization logic.
+//===----------------------------------------------------------------------===//
+
+namespace {
+
+class VISIBILITY_HIDDEN RegisterDecls
+ : public CFGRecStmtDeclVisitor<RegisterDecls> {
+
+ UninitializedValues::AnalysisDataTy& AD;
+public:
+ RegisterDecls(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {}
+
+ void VisitBlockVarDecl(BlockVarDecl* VD) { AD.Register(VD); }
+ CFG& getCFG() { return AD.getCFG(); }
+};
+
+} // end anonymous namespace
+
+void UninitializedValues::InitializeValues(const CFG& cfg) {
+ RegisterDecls R(getAnalysisData());
+ cfg.VisitBlockStmts(R);
+}
+
+//===----------------------------------------------------------------------===//
+// Transfer functions.
+//===----------------------------------------------------------------------===//
+
+namespace {
+class VISIBILITY_HIDDEN TransferFuncs
+ : public CFGStmtVisitor<TransferFuncs,bool> {
+
+ UninitializedValues::ValTy V;
+ UninitializedValues::AnalysisDataTy& AD;
+public:
+ TransferFuncs(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {
+ V.resetValues(AD);
+ }
+
+ UninitializedValues::ValTy& getVal() { return V; }
+ CFG& getCFG() { return AD.getCFG(); }
+
+ bool VisitDeclRefExpr(DeclRefExpr* DR);
+ bool VisitBinaryOperator(BinaryOperator* B);
+ bool VisitUnaryOperator(UnaryOperator* U);
+ bool VisitStmt(Stmt* S);
+ bool VisitCallExpr(CallExpr* C);
+ bool VisitDeclStmt(DeclStmt* D);
+ bool VisitConditionalOperator(ConditionalOperator* C);
+
+ bool Visit(Stmt *S);
+ bool BlockStmt_VisitExpr(Expr* E);
+
+ BlockVarDecl* FindBlockVarDecl(Stmt* S);
+};
+
+static const bool Initialized = true;
+static const bool Uninitialized = false;
+
+bool TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
+ if (BlockVarDecl* VD = dyn_cast<BlockVarDecl>(DR->getDecl())) {
+ if (AD.Observer) AD.Observer->ObserveDeclRefExpr(V,AD,DR,VD);
+
+ // Pseudo-hack to prevent cascade of warnings. If an accessed variable
+ // is uninitialized, then we are already going to flag a warning for
+ // this variable, which a "source" of uninitialized values.
+ // We can otherwise do a full "taint" of uninitialized values. The
+ // client has both options by toggling AD.FullUninitTaint.
+
+ return AD.FullUninitTaint ? V(VD,AD) : Initialized;
+ }
+ else return Initialized;
+}
+
+BlockVarDecl* TransferFuncs::FindBlockVarDecl(Stmt *S) {
+ for (;;)
+ if (ParenExpr* P = dyn_cast<ParenExpr>(S)) {
+ S = P->getSubExpr(); continue;
+ }
+ else if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(S)) {
+ if (BlockVarDecl* VD = dyn_cast<BlockVarDecl>(DR->getDecl()))
+ return VD;
+ else
+ return NULL;
+ }
+ else return NULL;
+}
+
+bool TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
+ if (BlockVarDecl* VD = FindBlockVarDecl(B->getLHS()))
+ if (B->isAssignmentOp()) {
+ if (B->getOpcode() == BinaryOperator::Assign)
+ return V(VD,AD) = Visit(B->getRHS());
+ else // Handle +=, -=, *=, etc. We do want '&', not '&&'.
+ return V(VD,AD) = Visit(B->getLHS()) & Visit(B->getRHS());
+ }
+
+ return VisitStmt(B);
+}
+
+bool TransferFuncs::VisitDeclStmt(DeclStmt* S) {
+ for (ScopedDecl* D = S->getDecl(); D != NULL; D = D->getNextDeclarator())
+ if (BlockVarDecl* VD = dyn_cast<BlockVarDecl>(D)) {
+ if (Stmt* I = VD->getInit())
+ V(VD,AD) = AD.FullUninitTaint ? V(cast<Expr>(I),AD) : Initialized;
+ else {
+ // Special case for declarations of array types. For things like:
+ //
+ // char x[10];
+ //
+ // we should treat "x" as being initialized, because the variable
+ // "x" really refers to the memory block. Clearly x[1] is
+ // uninitialized, but expressions like "(char *) x" really do refer to
+ // an initialized value. This simple dataflow analysis does not reason
+ // about the contents of arrays, although it could be potentially
+ // extended to do so if the array were of constant size.
+ if (VD->getType()->isArrayType())
+ V(VD,AD) = Initialized;
+ else
+ V(VD,AD) = Uninitialized;
+ }
+ }
+
+ return Uninitialized; // Value is never consumed.
+}
+
+bool TransferFuncs::VisitCallExpr(CallExpr* C) {
+ VisitChildren(C);
+ return Initialized;
+}
+
+bool TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
+ switch (U->getOpcode()) {
+ case UnaryOperator::AddrOf:
+ if (BlockVarDecl* VD = FindBlockVarDecl(U->getSubExpr()))
+ return V(VD,AD) = Initialized;
+
+ break;
+
+ case UnaryOperator::SizeOf:
+ return Initialized;
+
+ default:
+ break;
+ }
+
+ return Visit(U->getSubExpr());
+}
+
+bool TransferFuncs::VisitConditionalOperator(ConditionalOperator* C) {
+ Visit(C->getCond());
+
+ bool rhsResult = Visit(C->getRHS());
+ // Handle the GNU extension for missing LHS.
+ if (Expr *lhs = C->getLHS())
+ return Visit(lhs) & rhsResult; // Yes: we want &, not &&.
+ else
+ return rhsResult;
+}
+
+bool TransferFuncs::VisitStmt(Stmt* S) {
+ bool x = Initialized;
+
+ // We don't stop at the first subexpression that is Uninitialized because
+ // evaluating some subexpressions may result in propogating "Uninitialized"
+ // or "Initialized" to variables referenced in the other subexpressions.
+ for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I)
+ if (*I && Visit(*I) == Uninitialized) x = Uninitialized;
+
+ return x;
+}
+
+bool TransferFuncs::Visit(Stmt *S) {
+ if (AD.isTracked(static_cast<Expr*>(S))) return V(static_cast<Expr*>(S),AD);
+ else return static_cast<CFGStmtVisitor<TransferFuncs,bool>*>(this)->Visit(S);
+}
+
+bool TransferFuncs::BlockStmt_VisitExpr(Expr* E) {
+ bool x = static_cast<CFGStmtVisitor<TransferFuncs,bool>*>(this)->Visit(E);
+ if (AD.isTracked(E)) V(E,AD) = x;
+ return x;
+}
+
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// Merge operator.
+//
+// In our transfer functions we take the approach that any
+// combination of unintialized values, e.g. Unitialized + ___ = Unitialized.
+//
+// Merges take the opposite approach.
+//
+// In the merge of dataflow values we prefer unsoundness, and
+// prefer false negatives to false positives. At merges, if a value for a
+// tracked Decl is EVER initialized in any of the predecessors we treat it as
+// initialized at the confluence point.
+//===----------------------------------------------------------------------===//
+
+namespace {
+ typedef ExprDeclBitVector_Types::Union Merge;
+ typedef DataflowSolver<UninitializedValues,TransferFuncs,Merge> Solver;
+}
+
+//===----------------------------------------------------------------------===//
+// Unitialized values checker. Scan an AST and flag variable uses
+//===----------------------------------------------------------------------===//
+
+UninitializedValues_ValueTypes::ObserverTy::~ObserverTy() {}
+
+namespace {
+class VISIBILITY_HIDDEN UninitializedValuesChecker
+ : public UninitializedValues::ObserverTy {
+
+ ASTContext &Ctx;
+ Diagnostic &Diags;
+ llvm::SmallPtrSet<BlockVarDecl*,10> AlreadyWarned;
+
+public:
+ UninitializedValuesChecker(ASTContext &ctx, Diagnostic &diags)
+ : Ctx(ctx), Diags(diags) {}
+
+ virtual void ObserveDeclRefExpr(UninitializedValues::ValTy& V,
+ UninitializedValues::AnalysisDataTy& AD,
+ DeclRefExpr* DR, BlockVarDecl* VD) {
+
+ assert ( AD.isTracked(VD) && "Unknown VarDecl.");
+
+ if (V(VD,AD) == Uninitialized)
+ if (AlreadyWarned.insert(VD))
+ Diags.Report(Ctx.getFullLoc(DR->getSourceRange().getBegin()),
+ diag::warn_uninit_val);
+ }
+};
+} // end anonymous namespace
+
+namespace clang {
+void CheckUninitializedValues(CFG& cfg, ASTContext &Ctx, Diagnostic &Diags,
+ bool FullUninitTaint) {
+
+ // Compute the unitialized values information.
+ UninitializedValues U(cfg);
+ U.getAnalysisData().FullUninitTaint = FullUninitTaint;
+ Solver S(U);
+ S.runOnCFG(cfg);
+
+ // Scan for DeclRefExprs that use uninitialized values.
+ UninitializedValuesChecker Observer(Ctx,Diags);
+ U.getAnalysisData().Observer = &Observer;
+ S.runOnAllBlocks(cfg);
+}
+} // end namespace clang
diff --git a/lib/Analysis/ValueState.cpp b/lib/Analysis/ValueState.cpp
new file mode 100644
index 0000000..c0ed7aa
--- /dev/null
+++ b/lib/Analysis/ValueState.cpp
@@ -0,0 +1,595 @@
+//= ValueState*cpp - Path-Sens. "State" for tracking valuues -----*- 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 SymbolID, ExprBindKey, and ValueState*
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/PathSensitive/ValueState.h"
+#include "llvm/ADT/SmallSet.h"
+
+using namespace clang;
+
+bool ValueState::isNotEqual(SymbolID sym, const llvm::APSInt& V) const {
+
+ // Retrieve the NE-set associated with the given symbol.
+ ConstNotEqTy::TreeTy* T = ConstNotEq.SlimFind(sym);
+
+ // See if V is present in the NE-set.
+ return T ? T->getValue().second.contains(&V) : false;
+}
+
+const llvm::APSInt* ValueState::getSymVal(SymbolID sym) const {
+ ConstEqTy::TreeTy* T = ConstEq.SlimFind(sym);
+ return T ? T->getValue().second : NULL;
+}
+
+ValueState*
+ValueStateManager::RemoveDeadBindings(ValueState* St, Stmt* Loc,
+ const LiveVariables& Liveness) {
+
+ // This code essentially performs a "mark-and-sweep" of the VariableBindings.
+ // The roots are any Block-level exprs and Decls that our liveness algorithm
+ // tells us are live. We then see what Decls they may reference, and keep
+ // those around. This code more than likely can be made faster, and the
+ // frequency of which this method is called should be experimented with
+ // for optimum performance.
+
+ llvm::SmallVector<ValueDecl*, 10> WList;
+ llvm::SmallPtrSet<ValueDecl*, 10> Marked;
+ llvm::SmallSet<SymbolID, 20> MarkedSymbols;
+
+ ValueState NewSt = *St;
+
+ // Drop bindings for subexpressions.
+ NewSt.SubExprBindings = EXFactory.GetEmptyMap();
+
+ // Iterate over the block-expr bindings.
+
+ for (ValueState::beb_iterator I = St->beb_begin(), E = St->beb_end();
+ I!=E ; ++I) {
+ Expr* BlkExpr = I.getKey();
+
+ if (Liveness.isLive(Loc, BlkExpr)) {
+ RVal X = I.getData();
+
+ if (isa<lval::DeclVal>(X)) {
+ lval::DeclVal LV = cast<lval::DeclVal>(X);
+ WList.push_back(LV.getDecl());
+ }
+
+ for (RVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
+ SI != SE; ++SI) {
+ MarkedSymbols.insert(*SI);
+ }
+ }
+ else {
+ RVal X = I.getData();
+
+ if (X.isUndef() && cast<UndefinedVal>(X).getData())
+ continue;
+
+ NewSt.BlockExprBindings = Remove(NewSt, BlkExpr);
+ }
+ }
+
+ // Iterate over the variable bindings.
+
+ for (ValueState::vb_iterator I = St->vb_begin(), E = St->vb_end(); I!=E ; ++I)
+ if (Liveness.isLive(Loc, I.getKey())) {
+ WList.push_back(I.getKey());
+
+ RVal X = I.getData();
+
+ for (RVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
+ SI != SE; ++SI) {
+ MarkedSymbols.insert(*SI);
+ }
+ }
+
+ // Perform the mark-and-sweep.
+
+ while (!WList.empty()) {
+
+ ValueDecl* V = WList.back();
+ WList.pop_back();
+
+ if (Marked.count(V))
+ continue;
+
+ Marked.insert(V);
+
+ if (V->getType()->isPointerType()) {
+
+ RVal X = GetRVal(St, lval::DeclVal(cast<VarDecl>(V)));
+
+ if (X.isUnknownOrUndef())
+ continue;
+
+ LVal LV = cast<LVal>(X);
+
+ for (RVal::symbol_iterator SI = LV.symbol_begin(), SE = LV.symbol_end();
+ SI != SE; ++SI) {
+ MarkedSymbols.insert(*SI);
+ }
+
+ if (!isa<lval::DeclVal>(LV))
+ continue;
+
+ const lval::DeclVal& LVD = cast<lval::DeclVal>(LV);
+ WList.push_back(LVD.getDecl());
+ }
+ }
+
+ // Remove dead variable bindings.
+ 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());
+
+ // Remove dead symbols.
+ for (ValueState::ce_iterator I = St->ce_begin(), E=St->ce_end(); I!=E; ++I)
+ if (!MarkedSymbols.count(I.getKey()))
+ NewSt.ConstEq = CEFactory.Remove(NewSt.ConstEq, I.getKey());
+
+ for (ValueState::cne_iterator I = St->cne_begin(), E=St->cne_end(); I!=E; ++I)
+ if (!MarkedSymbols.count(I.getKey()))
+ NewSt.ConstNotEq = CNEFactory.Remove(NewSt.ConstNotEq, I.getKey());
+
+ return getPersistentState(NewSt);
+}
+
+
+RVal ValueStateManager::GetRVal(ValueState* St, LVal LV, QualType T) {
+
+ if (isa<UnknownVal>(LV))
+ return UnknownVal();
+
+ assert (!isa<UndefinedVal>(LV));
+
+ switch (LV.getSubKind()) {
+ case lval::DeclValKind: {
+ ValueState::VarBindingsTy::TreeTy* T =
+ St->VarBindings.SlimFind(cast<lval::DeclVal>(LV).getDecl());
+
+ return T ? T->getValue().second : 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();
+
+ if (T->isPointerType())
+ return lval::SymbolVal(SymMgr.getContentsOfSymbol(SV.getSymbol()));
+ else
+ return nonlval::SymbolVal(SymMgr.getContentsOfSymbol(SV.getSymbol()));
+#endif
+
+ return UnknownVal();
+ }
+
+ default:
+ assert (false && "Invalid LVal.");
+ break;
+ }
+
+ return UnknownVal();
+}
+
+ValueState* ValueStateManager::AddNE(ValueState* St, SymbolID sym,
+ const llvm::APSInt& V) {
+
+ // First, retrieve the NE-set associated with the given symbol.
+ ValueState::ConstNotEqTy::TreeTy* T = St->ConstNotEq.SlimFind(sym);
+ ValueState::IntSetTy S = T ? T->getValue().second : ISetFactory.GetEmptySet();
+
+ // Now add V to the NE set.
+ S = ISetFactory.Add(S, &V);
+
+ // Create a new state with the old binding replaced.
+ ValueState NewSt = *St;
+ NewSt.ConstNotEq = CNEFactory.Add(NewSt.ConstNotEq, sym, S);
+
+ // Get the persistent copy.
+ return getPersistentState(NewSt);
+}
+
+ValueState* ValueStateManager::AddEQ(ValueState* St, SymbolID sym,
+ const llvm::APSInt& V) {
+
+ // Create a new state with the old binding replaced.
+ ValueState NewSt = *St;
+ NewSt.ConstEq = CEFactory.Add(NewSt.ConstEq, sym, &V);
+
+ // Get the persistent copy.
+ return getPersistentState(NewSt);
+}
+
+RVal ValueStateManager::GetRVal(ValueState* St, Expr* E) {
+
+ for (;;) {
+
+ switch (E->getStmtClass()) {
+
+ case Stmt::AddrLabelExprClass:
+ return LVal::MakeVal(cast<AddrLabelExpr>(E));
+
+ // ParenExprs are no-ops.
+
+ case Stmt::ParenExprClass:
+ E = cast<ParenExpr>(E)->getSubExpr();
+ continue;
+
+ // DeclRefExprs can either evaluate to an LVal or a Non-LVal
+ // (assuming an implicit "load") depending on the context. In this
+ // context we assume that we are retrieving the value contained
+ // within the referenced variables.
+
+ case Stmt::DeclRefExprClass: {
+
+ // Check if this expression is a block-level expression. If so,
+ // return its value.
+ ValueState::ExprBindingsTy::TreeTy* T=St->BlockExprBindings.SlimFind(E);
+ if (T) return T->getValue().second;
+
+ RVal X = RVal::MakeVal(BasicVals, cast<DeclRefExpr>(E));
+ return isa<lval::DeclVal>(X) ? GetRVal(St, cast<lval::DeclVal>(X)) : X;
+ }
+
+ case Stmt::CharacterLiteralClass: {
+ CharacterLiteral* C = cast<CharacterLiteral>(E);
+ return NonLVal::MakeVal(BasicVals, C->getValue(), C->getType());
+ }
+
+ case Stmt::IntegerLiteralClass: {
+ return NonLVal::MakeVal(BasicVals, cast<IntegerLiteral>(E));
+ }
+
+ // Casts where the source and target type are the same
+ // are no-ops. We blast through these to get the descendant
+ // subexpression that has a value.
+
+ case Stmt::ImplicitCastExprClass: {
+ ImplicitCastExpr* C = cast<ImplicitCastExpr>(E);
+ QualType CT = C->getType();
+
+ if (CT->isVoidType())
+ return UnknownVal();
+
+ QualType ST = C->getSubExpr()->getType();
+
+ if (CT == ST || (CT->isPointerType() && ST->isFunctionType())) {
+ E = C->getSubExpr();
+ continue;
+ }
+
+ break;
+ }
+
+ case Stmt::CastExprClass: {
+ CastExpr* C = cast<CastExpr>(E);
+ QualType CT = C->getType();
+ QualType ST = C->getSubExpr()->getType();
+
+ if (CT->isVoidType())
+ return UnknownVal();
+
+ if (CT == ST || (CT->isPointerType() && ST->isFunctionType())) {
+ E = C->getSubExpr();
+ continue;
+ }
+
+ break;
+ }
+
+ case Stmt::UnaryOperatorClass: {
+
+ UnaryOperator* U = cast<UnaryOperator>(E);
+
+ if (U->getOpcode() == UnaryOperator::Plus) {
+ E = U->getSubExpr();
+ continue;
+ }
+
+ break;
+ }
+
+ // Handle all other Expr* using a lookup.
+
+ default:
+ break;
+ };
+
+ break;
+ }
+
+ ValueState::ExprBindingsTy::TreeTy* T = St->SubExprBindings.SlimFind(E);
+
+ if (T)
+ return T->getValue().second;
+
+ T = St->BlockExprBindings.SlimFind(E);
+ return T ? T->getValue().second : UnknownVal();
+}
+
+RVal ValueStateManager::GetBlkExprRVal(ValueState* St, Expr* E) {
+
+ E = E->IgnoreParens();
+
+ switch (E->getStmtClass()) {
+ case Stmt::CharacterLiteralClass: {
+ CharacterLiteral* C = cast<CharacterLiteral>(E);
+ return NonLVal::MakeVal(BasicVals, C->getValue(), C->getType());
+ }
+
+ case Stmt::IntegerLiteralClass: {
+ return NonLVal::MakeVal(BasicVals, cast<IntegerLiteral>(E));
+ }
+
+ default: {
+ ValueState::ExprBindingsTy::TreeTy* T = St->BlockExprBindings.SlimFind(E);
+ return T ? T->getValue().second : UnknownVal();
+ }
+ }
+}
+
+RVal ValueStateManager::GetLVal(ValueState* St, Expr* E) {
+
+ E = E->IgnoreParens();
+
+ if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E)) {
+ ValueDecl* VD = DR->getDecl();
+
+ if (FunctionDecl* FD = dyn_cast<FunctionDecl>(VD))
+ return lval::FuncVal(FD);
+ else
+ return lval::DeclVal(cast<VarDecl>(DR->getDecl()));
+ }
+
+ if (UnaryOperator* U = dyn_cast<UnaryOperator>(E))
+ if (U->getOpcode() == UnaryOperator::Deref) {
+ E = U->getSubExpr()->IgnoreParens();
+
+ if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E)) {
+ lval::DeclVal X(cast<VarDecl>(DR->getDecl()));
+ return GetRVal(St, X);
+ }
+ else
+ return GetRVal(St, E);
+ }
+
+ return GetRVal(St, E);
+}
+
+ValueState*
+ValueStateManager::SetRVal(ValueState* St, Expr* E, RVal V,
+ bool isBlkExpr, bool Invalidate) {
+
+ assert (E);
+
+ if (V.isUnknown()) {
+
+ if (Invalidate) {
+
+ ValueState NewSt = *St;
+
+ if (isBlkExpr)
+ NewSt.BlockExprBindings = EXFactory.Remove(NewSt.BlockExprBindings, E);
+ else
+ NewSt.SubExprBindings = EXFactory.Remove(NewSt.SubExprBindings, E);
+
+ return getPersistentState(NewSt);
+ }
+
+ return St;
+ }
+
+ ValueState NewSt = *St;
+
+ if (isBlkExpr) {
+ NewSt.BlockExprBindings = EXFactory.Add(NewSt.BlockExprBindings, E, V);
+ }
+ else {
+ NewSt.SubExprBindings = EXFactory.Add(NewSt.SubExprBindings, E, V);
+ }
+
+ return getPersistentState(NewSt);
+}
+
+
+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(EXFactory.GetEmptyMap(),
+ VBFactory.GetEmptyMap(),
+ CNEFactory.GetEmptyMap(),
+ CEFactory.GetEmptyMap());
+
+ return getPersistentState(StateImpl);
+}
+
+ValueState* ValueStateManager::getPersistentState(ValueState& State) {
+
+ llvm::FoldingSetNodeID ID;
+ State.Profile(ID);
+ void* InsertPos;
+
+ if (ValueState* I = StateSet.FindNodeOrInsertPos(ID, InsertPos))
+ return I;
+
+ ValueState* I = (ValueState*) Alloc.Allocate<ValueState>();
+ new (I) ValueState(State);
+ StateSet.InsertNode(I, InsertPos);
+ return I;
+}
+
+void ValueState::printDOT(std::ostream& Out, CheckerStatePrinter* P) const {
+ print(Out, P, "\\l", "\\|");
+}
+
+void ValueState::printStdErr(CheckerStatePrinter* P) const {
+ print(*llvm::cerr, P);
+}
+
+void ValueState::print(std::ostream& Out, CheckerStatePrinter* P,
+ const char* nl, const char* sep) const {
+
+ // Print Variable Bindings
+ Out << "Variables:" << nl;
+
+ bool isFirst = true;
+
+ for (vb_iterator I = vb_begin(), E = vb_end(); I != E; ++I) {
+
+ if (isFirst) isFirst = false;
+ else Out << nl;
+
+ Out << ' ' << I.getKey()->getName() << " : ";
+ I.getData().print(Out);
+ }
+
+ // Print Subexpression bindings.
+
+ isFirst = true;
+
+ for (seb_iterator I = seb_begin(), E = seb_end(); I != E; ++I) {
+
+ if (isFirst) {
+ Out << nl << nl << "Sub-Expressions:" << nl;
+ isFirst = false;
+ }
+ else { Out << nl; }
+
+ Out << " (" << (void*) I.getKey() << ") ";
+ I.getKey()->printPretty(Out);
+ Out << " : ";
+ I.getData().print(Out);
+ }
+
+ // Print block-expression bindings.
+
+ isFirst = true;
+
+ for (beb_iterator I = beb_begin(), E = beb_end(); I != E; ++I) {
+
+ if (isFirst) {
+ Out << nl << nl << "Block-level Expressions:" << nl;
+ isFirst = false;
+ }
+ else { Out << nl; }
+
+ Out << " (" << (void*) I.getKey() << ") ";
+ I.getKey()->printPretty(Out);
+ Out << " : ";
+ I.getData().print(Out);
+ }
+
+ // Print equality constraints.
+
+ if (!ConstEq.isEmpty()) {
+
+ Out << nl << sep << "'==' constraints:";
+
+ for (ConstEqTy::iterator I = ConstEq.begin(),
+ E = ConstEq.end(); I!=E; ++I) {
+
+ Out << nl << " $" << I.getKey()
+ << " : " << I.getData()->toString();
+ }
+ }
+
+ // Print != constraints.
+
+ if (!ConstNotEq.isEmpty()) {
+
+ Out << nl << sep << "'!=' constraints:";
+
+ for (ConstNotEqTy::iterator I = ConstNotEq.begin(),
+ EI = ConstNotEq.end(); I != EI; ++I) {
+
+ Out << nl << " $" << I.getKey() << " : ";
+ isFirst = true;
+
+ IntSetTy::iterator J = I.getData().begin(), EJ = I.getData().end();
+
+ for ( ; J != EJ; ++J) {
+ if (isFirst) isFirst = false;
+ else Out << ", ";
+
+ Out << (*J)->toString();
+ }
+ }
+ }
+
+ // Print checker-specific data.
+
+ if (P && CheckerState)
+ P->PrintCheckerState(Out, CheckerState, nl, sep);
+}