summaryrefslogtreecommitdiffstats
path: root/clang/lib/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'clang/lib/Analysis')
-rw-r--r--clang/lib/Analysis/BasicValueFactory.cpp167
-rw-r--r--clang/lib/Analysis/CFRefCount.cpp796
-rw-r--r--clang/lib/Analysis/DeadStores.cpp87
-rw-r--r--clang/lib/Analysis/ExplodedGraph.cpp227
-rw-r--r--clang/lib/Analysis/GRBlockCounter.cpp54
-rw-r--r--clang/lib/Analysis/GRCoreEngine.cpp444
-rw-r--r--clang/lib/Analysis/GRExprEngine.cpp1941
-rw-r--r--clang/lib/Analysis/GRSimpleVals.cpp462
-rw-r--r--clang/lib/Analysis/GRSimpleVals.h71
-rw-r--r--clang/lib/Analysis/LiveVariables.cpp246
-rw-r--r--clang/lib/Analysis/Makefile22
-rw-r--r--clang/lib/Analysis/ProgramPoint.cpp65
-rw-r--r--clang/lib/Analysis/RValues.cpp389
-rw-r--r--clang/lib/Analysis/SymbolManager.cpp124
-rw-r--r--clang/lib/Analysis/UninitializedValues.cpp277
-rw-r--r--clang/lib/Analysis/ValueState.cpp595
16 files changed, 5967 insertions, 0 deletions
diff --git a/clang/lib/Analysis/BasicValueFactory.cpp b/clang/lib/Analysis/BasicValueFactory.cpp
new file mode 100644
index 00000000000..88b360d1d0e
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/CFRefCount.cpp b/clang/lib/Analysis/CFRefCount.cpp
new file mode 100644
index 00000000000..77bbba25ea3
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/DeadStores.cpp b/clang/lib/Analysis/DeadStores.cpp
new file mode 100644
index 00000000000..0848336e586
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/ExplodedGraph.cpp b/clang/lib/Analysis/ExplodedGraph.cpp
new file mode 100644
index 00000000000..2ba46d77d63
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/GRBlockCounter.cpp b/clang/lib/Analysis/GRBlockCounter.cpp
new file mode 100644
index 00000000000..3ecc39d3224
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/GRCoreEngine.cpp b/clang/lib/Analysis/GRCoreEngine.cpp
new file mode 100644
index 00000000000..53831ed06d5
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/GRExprEngine.cpp b/clang/lib/Analysis/GRExprEngine.cpp
new file mode 100644
index 00000000000..f1108df4051
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/GRSimpleVals.cpp b/clang/lib/Analysis/GRSimpleVals.cpp
new file mode 100644
index 00000000000..3777d53bf0b
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/GRSimpleVals.h b/clang/lib/Analysis/GRSimpleVals.h
new file mode 100644
index 00000000000..2b3d0fd00a2
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/LiveVariables.cpp b/clang/lib/Analysis/LiveVariables.cpp
new file mode 100644
index 00000000000..e59a4885911
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/Makefile b/clang/lib/Analysis/Makefile
new file mode 100644
index 00000000000..b1d91781823
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/ProgramPoint.cpp b/clang/lib/Analysis/ProgramPoint.cpp
new file mode 100644
index 00000000000..c089e486988
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/RValues.cpp b/clang/lib/Analysis/RValues.cpp
new file mode 100644
index 00000000000..a4b464949aa
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/SymbolManager.cpp b/clang/lib/Analysis/SymbolManager.cpp
new file mode 100644
index 00000000000..f243fa667b3
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/UninitializedValues.cpp b/clang/lib/Analysis/UninitializedValues.cpp
new file mode 100644
index 00000000000..25a5ecb4837
--- /dev/null
+++ b/clang/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/clang/lib/Analysis/ValueState.cpp b/clang/lib/Analysis/ValueState.cpp
new file mode 100644
index 00000000000..c0ed7aa882a
--- /dev/null
+++ b/clang/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);
+}
OpenPOWER on IntegriCloud