Hi Ted, see below.
On 06.10.2009, at 17:42, Ted Kremenek wrote: > Author: kremenek > Date: Tue Oct 6 19:42:52 2009 > New Revision: 83439 > > URL: http://llvm.org/viewvc/llvm-project?rev=83439&view=rev > Log: > 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. > > Added: > cfe/trunk/include/clang/Analysis/Support/BumpVector.h > Modified: > cfe/trunk/include/clang/Analysis/PathSensitive/ExplodedGraph.h > cfe/trunk/lib/Analysis/BugReporter.cpp > cfe/trunk/lib/Analysis/ExplodedGraph.cpp > cfe/trunk/lib/Analysis/GRCoreEngine.cpp > > Modified: cfe/trunk/include/clang/Analysis/PathSensitive/ > ExplodedGraph.h > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/Analysis/PathSensitive/ExplodedGraph.h?rev=83439&r1=83438&r2=83439&view=diff > > = > = > = > = > = > = > = > = > ====================================================================== > --- cfe/trunk/include/clang/Analysis/PathSensitive/ExplodedGraph.h > (original) > +++ cfe/trunk/include/clang/Analysis/PathSensitive/ExplodedGraph.h > Tue Oct 6 19:42:52 2009 > @@ -26,12 +26,14 @@ > #include "llvm/ADT/GraphTraits.h" > #include "llvm/ADT/DepthFirstIterator.h" > #include "llvm/Support/Casting.h" > +#include "clang/Analysis/Support/BumpVector.h" > > namespace clang { > > class GRState; > class CFG; > class ASTContext; > +class ExplodedGraph; > > // > = > = > = > ----------------------------------------------------------------------= > ==// > // ExplodedGraph "implementation" classes. These classes are not > typed to > @@ -68,20 +70,18 @@ > public: > NodeGroup() : P(0) {} > > - ~NodeGroup(); > + ExplodedNode **begin() const; > > - ExplodedNode** begin() const; > - > - ExplodedNode** end() const; > + ExplodedNode **end() const; > > unsigned size() const; > > - bool empty() const { return size() == 0; } > + bool empty() const { return (P & ~Mask) == 0; } > > - void addNode(ExplodedNode* N); > + void addNode(ExplodedNode* N, ExplodedGraph &G); > > void setFlag() { > - assert (P == 0); > + assert(P == 0); > P = AuxFlag; > } > > @@ -131,7 +131,10 @@ > const T* getLocationAs() const { return llvm::dyn_cast<T> > (&Location); } > > static void Profile(llvm::FoldingSetNodeID &ID, > - const ProgramPoint& Loc, const GRState* state); > + const ProgramPoint& Loc, const GRState* > state) { > + ID.Add(Loc); > + ID.AddPointer(state); > + } > > void Profile(llvm::FoldingSetNodeID& ID) const { > Profile(ID, getLocation(), getState()); > @@ -139,7 +142,7 @@ > > /// addPredeccessor - Adds a predecessor to the current node, and > /// in tandem add this node as a successor of the other node. > - void addPredecessor(ExplodedNode* V); > + void addPredecessor(ExplodedNode* V, ExplodedGraph &G); > > unsigned succ_size() const { return Succs.size(); } > unsigned pred_size() const { return Preds.size(); } > @@ -229,8 +232,9 @@ > /// Nodes - The nodes in the graph. > llvm::FoldingSet<ExplodedNode> Nodes; > > - /// Allocator - BumpPtrAllocator to create nodes. > - llvm::BumpPtrAllocator Allocator; > + /// BVC - Allocator and context for allocating nodes and their > predecessor > + /// and successor groups. > + BumpVectorContext BVC; > > /// Ctx - The ASTContext used to "interpret" CodeDecl. > ASTContext& Ctx; > @@ -265,7 +269,7 @@ > > ExplodedGraph(ASTContext& ctx) : Ctx(ctx), NumNodes(0) {} > > - virtual ~ExplodedGraph() {} > + ~ExplodedGraph() {} > > unsigned num_roots() const { return Roots.size(); } > unsigned num_eops() const { return EndNodes.size(); } > @@ -307,7 +311,8 @@ > > const_eop_iterator eop_end() const { return EndNodes.end(); } > > - llvm::BumpPtrAllocator& getAllocator() { return Allocator; } > + llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator > (); } > + BumpVectorContext &getNodeAllocator() { return BVC; } > > ASTContext& getContext() { return Ctx; } > > > Added: cfe/trunk/include/clang/Analysis/Support/BumpVector.h > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/Analysis/Support/BumpVector.h?rev=83439&view=auto > > = > = > = > = > = > = > = > = > ====================================================================== > --- cfe/trunk/include/clang/Analysis/Support/BumpVector.h (added) > +++ cfe/trunk/include/clang/Analysis/Support/BumpVector.h Tue Oct 6 > 19:42:52 2009 > @@ -0,0 +1,200 @@ > +//===-- BumpVector.h - Vector-like ADT that uses bump allocation -- > *- C++ -*-=// > +// > +// The LLVM Compiler Infrastructure > +// > +// This file is distributed under the University of Illinois Open > Source > +// License. See LICENSE.TXT for details. > +// > +// > = > = > = > ----------------------------------------------------------------------= > ==// > +// > +// This file provides BumpVector, a vector-like ADT whose contents > are > +// allocated from a BumpPtrAllocator. > +// > +// > = > = > = > ----------------------------------------------------------------------= > ==// > + > +// FIXME: Most of this is copy-and-paste from SmallVector.h. We can > +// refactor this core logic into something common that is shared > between > +// the two. The main thing that is different is the allocation > strategy. > + > +#ifndef LLVM_CLANG_BUMP_VECTOR > +#define LLVM_CLANG_BUMP_VECTOR > + > +#include "llvm/Support/type_traits.h" > +#include "llvm/Support/Allocator.h" > +#include <algorithm> > + > +namespace clang { > + > +class BumpVectorContext { > + llvm::BumpPtrAllocator Alloc; > +public: > + llvm::BumpPtrAllocator &getAllocator() { return Alloc; } > +}; > + > +template<typename T> > +class BumpVector { > + T *Begin, *End, *Capacity; > +public: > + // Default ctor - Initialize to empty. > + explicit BumpVector(BumpVectorContext &C, unsigned N) > + : Begin(NULL), End(NULL), Capacity(NULL) { > + reserve(C, N); > + } > + > + ~BumpVector() { > + if (llvm::is_class<T>::value) { > + // Destroy the constructed elements in the vector. > + destroy_range(Begin, End); > + } > + } > + > + typedef size_t size_type; > + typedef ptrdiff_t difference_type; > + typedef T value_type; > + typedef T* iterator; > + typedef const T* const_iterator; > + > + typedef std::reverse_iterator<const_iterator> > const_reverse_iterator; > + typedef std::reverse_iterator<iterator> reverse_iterator; > + > + typedef T& reference; > + typedef const T& const_reference; > + typedef T* pointer; > + typedef const T* const_pointer; > + > + // forward iterator creation methods. > + iterator begin() { return Begin; } > + const_iterator begin() const { return Begin; } > + iterator end() { return End; } > + const_iterator end() const { return End; } > + > + // reverse iterator creation methods. > + reverse_iterator rbegin() { return reverse_iterator(end > ()); } > + const_reverse_iterator rbegin() const{ return > const_reverse_iterator(end()); } > + reverse_iterator rend() { return reverse_iterator > (begin()); } > + const_reverse_iterator rend() const { return > const_reverse_iterator(begin());} > + > + bool empty() const { return Begin == End; } > + size_type size() const { return End-Begin; } > + > + reference operator[](unsigned idx) { > + assert(Begin + idx < End); > + return Begin[idx]; > + } > + const_reference operator[](unsigned idx) const { > + assert(Begin + idx < End); > + return Begin[idx]; > + } > + > + reference front() { > + return begin()[0]; > + } > + const_reference front() const { > + return begin()[0]; > + } > + > + reference back() { > + return end()[-1]; > + } > + const_reference back() const { > + return end()[-1]; > + } > + > + void pop_back() { > + --End; > + End->~T(); > + } > + > + T pop_back_val() { > + T Result = back(); > + pop_back(); > + return Result; > + } > + > + void clear() { > + if (llvm::is_class<T>::value) { > + destroy_range(Begin, End); > + } > + End = Begin; > + } > + > + /// data - Return a pointer to the vector's buffer, even if empty > (). > + pointer data() { > + return pointer(Begin); > + } > + > + /// data - Return a pointer to the vector's buffer, even if empty > (). > + const_pointer data() const { > + return const_pointer(Begin); > + } > + > + void push_back(const_reference Elt, BumpVectorContext &C) { > + if (End < Capacity) { > + Retry: > + new (End) T(Elt); > + ++End; > + return; > + } > + grow(C); > + goto Retry; > + } > + > + void reserve(BumpVectorContext &C, unsigned N) { > + if (unsigned(Capacity-Begin) < N) > + grow(C, N); > + } > + > + /// capacity - Return the total number of elements in the > currently allocated > + /// buffer. > + size_t capacity() const { return Capacity - Begin; } > + > +private: > + /// grow - double the size of the allocated memory, guaranteeing > space for at > + /// least one more element or MinSize if specified. > + void grow(BumpVectorContext &C, size_type MinSize = 0); > + > + void construct_range(T *S, T *E, const T &Elt) { > + for (; S != E; ++S) > + new (S) T(Elt); > + } > + > + void destroy_range(T *S, T *E) { > + while (S != E) { > + --E; > + E->~T(); > + } > + } > +}; > + > +// Define this out-of-line to dissuade the C++ compiler from > inlining it. > +template <typename T> > +void BumpVector<T>::grow(BumpVectorContext &C, size_t MinSize) { > + size_t CurCapacity = Capacity-Begin; > + size_t CurSize = size(); > + size_t NewCapacity = 2*CurCapacity; > + if (NewCapacity < MinSize) > + NewCapacity = MinSize; > + > + // Allocate the memory from the BumpPtrAllocator. > + T *NewElts = C.getAllocator().Allocate<T>(NewCapacity); This gives the following error on my system (standard Leopard gcc 4.0.1): /Users/thakis/src/llvm/tools/clang/lib/Analysis/../../include/clang/ Analysis/Support/BumpVector.h: In member function ‘void clang::BumpVector<T>::grow(clang::BumpVectorContext&, size_t)’: /Users/thakis/src/llvm/tools/clang/lib/Analysis/../../include/clang/ Analysis/Support/BumpVector.h:179: error: expected primary-expression before ‘>’ token make[4]: *** [/Users/thakis/src/llvm/tools/clang/lib/Analysis/Debug/ AnalysisManager.o] Error 1 Nico > + > + // Copy the elements over. > + if (llvm::is_class<T>::value) { > + std::uninitialized_copy(Begin, End, NewElts); > + // Destroy the original elements. > + destroy_range(Begin, End); > + } > + else { > + // Use memcpy for PODs (std::uninitialized_copy optimizes to > memmove). > + memcpy(NewElts, Begin, CurSize * sizeof(T)); > + } > + > + // For now, leak 'Begin'. We can add it back to a freelist in > + // BumpVectorContext. > + Begin = NewElts; > + End = NewElts+CurSize; > + Capacity = Begin+NewCapacity; > +} > + > +} // end: clang namespace > +#endif // end: LLVM_CLANG_BUMP_VECTOR > > Modified: cfe/trunk/lib/Analysis/BugReporter.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Analysis/BugReporter.cpp?rev=83439&r1=83438&r2=83439&view=diff > > = > = > = > = > = > = > = > = > ====================================================================== > --- cfe/trunk/lib/Analysis/BugReporter.cpp (original) > +++ cfe/trunk/lib/Analysis/BugReporter.cpp Tue Oct 6 19:42:52 2009 > @@ -1432,7 +1432,7 @@ > > // Link up the new node with the previous node. > if (Last) > - NewN->addPredecessor(Last); > + NewN->addPredecessor(Last, *GNew); > > Last = NewN; > > > Modified: cfe/trunk/lib/Analysis/ExplodedGraph.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Analysis/ExplodedGraph.cpp?rev=83439&r1=83438&r2=83439&view=diff > > = > = > = > = > = > = > = > = > ====================================================================== > --- cfe/trunk/lib/Analysis/ExplodedGraph.cpp (original) > +++ cfe/trunk/lib/Analysis/ExplodedGraph.cpp Tue Oct 6 19:42:52 2009 > @@ -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; > } > > > Modified: cfe/trunk/lib/Analysis/GRCoreEngine.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/Analysis/GRCoreEngine.cpp?rev=83439&r1=83438&r2=83439&view=diff > > = > = > = > = > = > = > = > = > ====================================================================== > --- cfe/trunk/lib/Analysis/GRCoreEngine.cpp (original) > +++ cfe/trunk/lib/Analysis/GRCoreEngine.cpp Tue Oct 6 19:42:52 2009 > @@ -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); > > > _______________________________________________ > cfe-commits mailing list > [email protected] > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
