2 files changed, 218 insertions, 13 deletions

diff --git a/include/clang/Analysis/PathSensitive/ExplodedGraph.h b/include/clang/Analysis/PathSensitive/ExplodedGraph.h
index d8659c2302..a7bbdf939f 100644
--- a/include/clang/Analysis/PathSensitive/ExplodedGraph.h
+++ b/include/clang/Analysis/PathSensitive/ExplodedGraph.h
@@ -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 @@ class ExplodedNode : public llvm::FoldingSetNode {
   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 @@ public:
   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 @@ public:
 
   /// 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 @@ protected:
   /// 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 @@ public:
 
   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 @@ public:
 
   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; }
 
diff --git a/include/clang/Analysis/Support/BumpVector.h b/include/clang/Analysis/Support/BumpVector.h
new file mode 100644
index 0000000000..d1c6d4ba4a
--- /dev/null
+++ b/include/clang/Analysis/Support/BumpVector.h
@@ -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);
+  
+  // 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