Change ExplodedNode to have its NodeGroups all BumpPtrAllocated, avoiding malloc() traffic when adding successors/predecessors to a node. This was done by introducing BumpVector, which is essentially SmallVector with all memory being BumpPtrAllocated (this can certainly be cleaned up or moved into llvm/ADT).
This change yields a 1.8% speed increase when running the analyzer (with -analyzer-store=region) on a small benchmark file.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@83439 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/BugReporter.cpp b/lib/Analysis/BugReporter.cpp
index 064fff4..8235f4a 100644
--- a/lib/Analysis/BugReporter.cpp
+++ b/lib/Analysis/BugReporter.cpp
@@ -1432,7 +1432,7 @@
// Link up the new node with the previous node.
if (Last)
- NewN->addPredecessor(Last);
+ NewN->addPredecessor(Last, *GNew);
Last = NewN;
diff --git a/lib/Analysis/ExplodedGraph.cpp b/lib/Analysis/ExplodedGraph.cpp
index 463b171..0dc81a4 100644
--- a/lib/Analysis/ExplodedGraph.cpp
+++ b/lib/Analysis/ExplodedGraph.cpp
@@ -43,53 +43,48 @@
// ExplodedNode.
//===----------------------------------------------------------------------===//
-static inline std::vector<ExplodedNode*>& getVector(void* P) {
- return *reinterpret_cast<std::vector<ExplodedNode*>*>(P);
+static inline BumpVector<ExplodedNode*>& getVector(void* P) {
+ return *reinterpret_cast<BumpVector<ExplodedNode*>*>(P);
}
-void ExplodedNode::Profile(llvm::FoldingSetNodeID& ID,
- const ProgramPoint& Loc,
- const GRState* state) {
- ID.Add(Loc);
- ID.AddPointer(state);
-}
-
-void ExplodedNode::addPredecessor(ExplodedNode* V) {
+void ExplodedNode::addPredecessor(ExplodedNode* V, ExplodedGraph &G) {
assert (!V->isSink());
- Preds.addNode(V);
- V->Succs.addNode(this);
+ Preds.addNode(V, G);
+ V->Succs.addNode(this, G);
#ifndef NDEBUG
if (NodeAuditor) NodeAuditor->AddEdge(V, this);
#endif
}
-void ExplodedNode::NodeGroup::addNode(ExplodedNode* N) {
-
- assert ((reinterpret_cast<uintptr_t>(N) & Mask) == 0x0);
- assert (!getFlag());
+void ExplodedNode::NodeGroup::addNode(ExplodedNode* N, ExplodedGraph &G) {
+ assert((reinterpret_cast<uintptr_t>(N) & Mask) == 0x0);
+ assert(!getFlag());
if (getKind() == Size1) {
if (ExplodedNode* NOld = getNode()) {
- std::vector<ExplodedNode*>* V = new std::vector<ExplodedNode*>();
- assert ((reinterpret_cast<uintptr_t>(V) & Mask) == 0x0);
- V->push_back(NOld);
- V->push_back(N);
+ BumpVectorContext &Ctx = G.getNodeAllocator();
+ BumpVector<ExplodedNode*> *V =
+ G.getAllocator().Allocate<BumpVector<ExplodedNode*> >();
+ new (V) BumpVector<ExplodedNode*>(Ctx, 4);
+
+ assert((reinterpret_cast<uintptr_t>(V) & Mask) == 0x0);
+ V->push_back(NOld, Ctx);
+ V->push_back(N, Ctx);
P = reinterpret_cast<uintptr_t>(V) | SizeOther;
- assert (getPtr() == (void*) V);
- assert (getKind() == SizeOther);
+ assert(getPtr() == (void*) V);
+ assert(getKind() == SizeOther);
}
else {
P = reinterpret_cast<uintptr_t>(N);
- assert (getKind() == Size1);
+ assert(getKind() == Size1);
}
}
else {
- assert (getKind() == SizeOther);
- getVector(getPtr()).push_back(N);
+ assert(getKind() == SizeOther);
+ getVector(getPtr()).push_back(N, G.getNodeAllocator());
}
}
-
unsigned ExplodedNode::NodeGroup::size() const {
if (getFlag())
return 0;
@@ -100,7 +95,7 @@
return getVector(getPtr()).size();
}
-ExplodedNode** ExplodedNode::NodeGroup::begin() const {
+ExplodedNode **ExplodedNode::NodeGroup::begin() const {
if (getFlag())
return NULL;
@@ -119,14 +114,10 @@
else {
// Dereferencing end() is undefined behaviour. The vector is not empty, so
// we can dereference the last elem and then add 1 to the result.
- return const_cast<ExplodedNode**>(&getVector(getPtr()).back()) + 1;
+ return const_cast<ExplodedNode**>(getVector(getPtr()).end());
}
}
-ExplodedNode::NodeGroup::~NodeGroup() {
- if (getKind() == SizeOther) delete &getVector(getPtr());
-}
-
ExplodedNode *ExplodedGraph::getNode(const ProgramPoint& L,
const GRState* State, bool* IsNew) {
// Profile 'State' to determine if we already have an existing node.
@@ -138,7 +129,7 @@
if (!V) {
// Allocate a new node.
- V = (NodeTy*) Allocator.Allocate<NodeTy>();
+ V = (NodeTy*) getAllocator().Allocate<NodeTy>();
new (V) NodeTy(L, State);
// Insert the node into the node set and return it.
@@ -253,7 +244,7 @@
if (PI == Pass2.end())
continue;
- NewN->addPredecessor(PI->second);
+ NewN->addPredecessor(PI->second, *G);
}
// In the case that some of the intended successors of NewN have already
@@ -263,7 +254,7 @@
for (ExplodedNode **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);
+ PI->second->addPredecessor(NewN, *G);
continue;
}
diff --git a/lib/Analysis/GRCoreEngine.cpp b/lib/Analysis/GRCoreEngine.cpp
index 909f619..8747247 100644
--- a/lib/Analysis/GRCoreEngine.cpp
+++ b/lib/Analysis/GRCoreEngine.cpp
@@ -372,7 +372,7 @@
ExplodedNode* Node = G->getNode(Loc, State, &IsNew);
if (Pred)
- Node->addPredecessor(Pred); // Link 'Node' with its predecessor.
+ Node->addPredecessor(Pred, *G); // Link 'Node' with its predecessor.
else {
assert (IsNew);
G->addRoot(Node); // 'Node' has no predecessor. Make it a root.
@@ -412,7 +412,7 @@
bool IsNew;
ExplodedNode* Succ = Eng.G->getNode(Loc, N->State, &IsNew);
- Succ->addPredecessor(N);
+ Succ->addPredecessor(N, *Eng.G);
if (IsNew)
Eng.WList->Enqueue(Succ, B, Idx+1);
@@ -471,7 +471,7 @@
ExplodedNode* Pred) {
bool IsNew;
ExplodedNode* N = Eng.G->getNode(Loc, State, &IsNew);
- N->addPredecessor(Pred);
+ N->addPredecessor(Pred, *Eng.G);
Deferred.erase(Pred);
if (IsNew) {
@@ -497,7 +497,7 @@
Eng.G->getNode(BlockEdge(Src,branch ? DstT:DstF,Pred->getLocationContext()),
State, &IsNew);
- Succ->addPredecessor(Pred);
+ Succ->addPredecessor(Pred, *Eng.G);
if (branch)
GeneratedTrue = true;
@@ -529,7 +529,7 @@
ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(),
Pred->getLocationContext()), St, &IsNew);
- Succ->addPredecessor(Pred);
+ Succ->addPredecessor(Pred, *Eng.G);
if (IsNew) {
@@ -552,7 +552,7 @@
ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(),
Pred->getLocationContext()), St, &IsNew);
- Succ->addPredecessor(Pred);
+ Succ->addPredecessor(Pred, *Eng.G);
if (IsNew) {
Eng.WList->Enqueue(Succ);
@@ -574,7 +574,7 @@
ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock,
Pred->getLocationContext()), St, &IsNew);
- Succ->addPredecessor(Pred);
+ Succ->addPredecessor(Pred, *Eng.G);
if (IsNew) {
if (isSink)
@@ -602,7 +602,7 @@
ExplodedNode* Node = Eng.G->getNode(BlockEntrance(&B,
Pred->getLocationContext(), tag), State, &IsNew);
- Node->addPredecessor(P ? P : Pred);
+ Node->addPredecessor(P ? P : Pred, *Eng.G);
if (IsNew) {
Eng.G->addEndOfPath(Node);