Added --trim-path-graph to the driver to trim paths from the ExplodedGraph
that are not related to error nodes.
Fixed bug where we did not detect some NULL dereferences.
Added "ExplodedGraph::Trim" to trim all nodes that cannot transitively reach
a set of provided nodes.
Fixed subtle bug in ExplodedNodeImpl where we could create predecessor
iterators that included the mangled "sink" bit. The better fix is to integrate
this bit into the void* for the wrapped State, not the NodeGroups representing
a node's predecessors and successors.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@48036 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/Analysis/ExplodedGraph.cpp b/Analysis/ExplodedGraph.cpp
index 274565b..421b9e3 100644
--- a/Analysis/ExplodedGraph.cpp
+++ b/Analysis/ExplodedGraph.cpp
@@ -13,6 +13,9 @@
//===----------------------------------------------------------------------===//
#include "clang/Analysis/PathSensitive/ExplodedGraph.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
#include <vector>
using namespace clang;
@@ -25,6 +28,7 @@
void ExplodedNodeImpl::NodeGroup::addNode(ExplodedNodeImpl* N) {
assert ((reinterpret_cast<uintptr_t>(N) & Mask) == 0x0);
+ assert (!getFlag());
if (getKind() == Size1) {
if (ExplodedNodeImpl* NOld = getNode()) {
@@ -47,14 +51,11 @@
}
}
-bool ExplodedNodeImpl::NodeGroup::empty() const {
- if (getKind() == Size1)
- return getNode() ? false : true;
- else
- return getVector(getPtr()).empty();
-}
unsigned ExplodedNodeImpl::NodeGroup::size() const {
+ if (getFlag())
+ return 0;
+
if (getKind() == Size1)
return getNode() ? 1 : 0;
else
@@ -62,15 +63,21 @@
}
ExplodedNodeImpl** ExplodedNodeImpl::NodeGroup::begin() const {
+ if (getFlag())
+ return NULL;
+
if (getKind() == Size1)
- return (ExplodedNodeImpl**) &P;
+ 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**) (P ? &P+1 : &P);
+ return (ExplodedNodeImpl**) (getPtr() ? &P+1 : NULL);
else
return const_cast<ExplodedNodeImpl**>(&*(getVector(getPtr()).end()));
}
@@ -78,3 +85,110 @@
ExplodedNodeImpl::NodeGroup::~NodeGroup() {
if (getKind() == SizeOther) delete &getVector(getPtr());
}
+
+ExplodedGraphImpl* ExplodedGraphImpl::Trim(ExplodedNodeImpl** BeginSources,
+ ExplodedNodeImpl** EndSources) const{
+
+ typedef llvm::DenseSet<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.
+
+ llvm::SmallVector<ExplodedNodeImpl*, 10> WL1;
+
+ for (ExplodedNodeImpl** I = BeginSources; I != EndSources; ++I)
+ WL1.push_back(*I);
+
+ // Process the worklist.
+
+ while (!WL1.empty()) {
+
+ ExplodedNodeImpl* N = WL1.back();
+ WL1.pop_back();
+
+ if (Pass1.count(N))
+ continue;
+
+ Pass1.insert(N);
+
+ if (N->Preds.empty()) {
+ WL2.push_back(N);
+ continue;
+ }
+
+ for (ExplodedNodeImpl** I=N->Preds.begin(), **E=N->Preds.end(); I!=E; ++I)
+ WL1.push_back(*I);
+ }
+ }
+
+ 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.
+
+ if (Pass1.count(*I))
+ WL2.push_back(*I);
+ }
+
+ if (N->isSink())
+ NewN->markAsSink();
+ }
+
+ return G;
+}
diff --git a/Analysis/GRExprEngine.cpp b/Analysis/GRExprEngine.cpp
index aaef2f8..3bf0151 100644
--- a/Analysis/GRExprEngine.cpp
+++ b/Analysis/GRExprEngine.cpp
@@ -732,7 +732,8 @@
}
-void GRExprEngine::VisitDeref(UnaryOperator* U, NodeTy* Pred, NodeSet& Dst) {
+void GRExprEngine::VisitDeref(UnaryOperator* U, NodeTy* Pred,
+ NodeSet& Dst, bool GetLVal) {
Expr* Ex = U->getSubExpr()->IgnoreParens();
@@ -787,12 +788,16 @@
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.
- // 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())));
+ Nodify(Dst, U, N, SetRVal(StNotNull, U,
+ GetRVal(StNotNull, LV, U->getType())));
+ }
}
bool isFeasibleNull;
@@ -975,18 +980,11 @@
return;
}
- if (UnaryOperator* U = dyn_cast<UnaryOperator>(Ex)) {
+ if (UnaryOperator* U = dyn_cast<UnaryOperator>(Ex))
if (U->getOpcode() == UnaryOperator::Deref) {
- Ex = U->getSubExpr()->IgnoreParens();
-
- if (isa<DeclRefExpr>(Ex))
- Dst.Add(Pred);
- else
- Visit(Ex, Pred, Dst);
-
+ VisitDeref(U, Pred, Dst, true);
return;
}
- }
Visit(Ex, Pred, Dst);
}
@@ -1810,11 +1808,40 @@
} // end llvm namespace
#endif
-void GRExprEngine::ViewGraph() {
+#ifndef NDEBUG
+template <typename ITERATOR>
+static void AddSources(llvm::SmallVector<GRExprEngine::NodeTy*, 10>& Sources,
+ ITERATOR I, ITERATOR E) {
+
+ for ( ; I != E; ++I )
+ Sources.push_back(*I);
+}
+#endif
+
+void GRExprEngine::ViewGraph(bool trim) {
#ifndef NDEBUG
GraphPrintCheckerState = this;
GraphPrintSourceManager = &getContext().getSourceManager();
- llvm::ViewGraph(*G.roots_begin(), "GRExprEngine");
+
+ if (trim) {
+ llvm::SmallVector<NodeTy*, 10> Sources;
+ AddSources(Sources, null_derefs_begin(), null_derefs_end());
+ AddSources(Sources, undef_derefs_begin(), undef_derefs_end());
+
+ GRExprEngine::GraphTy* TrimmedG = G.Trim(&Sources[0],
+ &Sources[0]+Sources.size());
+
+ if (!TrimmedG)
+ llvm::cerr << "warning: Trimmed ExplodedGraph is empty.\n";
+ else {
+ llvm::ViewGraph(*TrimmedG->roots_begin(), "TrimmedGRExprEngine");
+ delete TrimmedG;
+ }
+ }
+ else
+ llvm::ViewGraph(*G.roots_begin(), "GRExprEngine");
+
+
GraphPrintCheckerState = NULL;
GraphPrintSourceManager = NULL;
#endif
diff --git a/Analysis/GRSimpleVals.cpp b/Analysis/GRSimpleVals.cpp
index c18610d..efe435b 100644
--- a/Analysis/GRSimpleVals.cpp
+++ b/Analysis/GRSimpleVals.cpp
@@ -90,7 +90,7 @@
}
unsigned RunGRSimpleVals(CFG& cfg, FunctionDecl& FD, ASTContext& Ctx,
- Diagnostic& Diag, bool Visualize) {
+ Diagnostic& Diag, bool Visualize, bool TrimGraph) {
if (Diag.hasErrorOccurred())
return 0;
@@ -141,7 +141,7 @@
"Pass-by-value argument in function or message expression is undefined.");
#ifndef NDEBUG
- if (Visualize) CheckerState->ViewGraph();
+ if (Visualize) CheckerState->ViewGraph(TrimGraph);
#endif
return Engine.getGraph().size();