Hi Nico, This should now be fixed:
http://lists.cs.uiuc.edu/pipermail/cfe-commits/Week-of-Mon-20091005/022071.html Sorry for the breakage. Please let me know if the problem persists. Ted On Oct 6, 2009, at 10:26 PM, Nico Weber wrote: > 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
