2012-08-29 Basile Starynkevitch <basile@starynkevitch.net>

	MELT branch merged with trunk rev 190745 using svnmerge, notably
	C++ conversion.

[gcc/]
2012-08-29  Basile Starynkevitch  <basile@starynkevitch.net>
	{{merging with trunk, converted to C++}}

	* melt-runtime.h (MELT_FLEXIBLE_DIM): Set when C++.

	* melt-runtime.c (melt_tempdir_path): Don't use choose_tmpdir from
	libiberty.
	(meltgc_start_module_by_index): Use address-of & on VEC_index.
	(melt_really_initialize): When printing builtin settings, handle
	GCC 4.8 as with implicit ENABLE_BUILD_WITH_CXX.
	(meltgc_out_edge): Provide additional flag TDF_DETAILS for dump_edge_info.
	(melt_val2passflag): Handle PROP_referenced_vars only when defined.

	* melt-module.mk: Use GCCMELT_COMPILER instead of GCCMELT_CC.

	* melt-build-script.tpl: Transmit GCCMELT_COMPILER on every make
	using melt-module.mk and improve the error message.

	* melt-build-script.sh: Regenerate.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/melt-branch@190778 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 739 insertions, 1002 deletions

diff --git a/gcc/vec.h b/gcc/vec.h
index d47795879f1..1922616fc13 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -1,7 +1,8 @@
 /* Vector API for GNU compiler.
-   Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010
+   Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011, 2012
    Free Software Foundation, Inc.
    Contributed by Nathan Sidwell <nathan@codesourcery.com>
+   Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
 
 This file is part of GCC.
 
@@ -95,24 +96,25 @@ along with GCC; see the file COPYING3.  If not see
    the 'space' predicate will tell you whether there is spare capacity
    in the vector.  You will not normally need to use these two functions.
 
-   Vector types are defined using a DEF_VEC_{O,P,I}(TYPEDEF) macro, to
+   Vector types are defined using a DEF_VEC_{O,A,P,I}(TYPEDEF) macro, to
    get the non-memory allocation version, and then a
-   DEF_VEC_ALLOC_{O,P,I}(TYPEDEF,ALLOC) macro to get memory managed
+   DEF_VEC_ALLOC_{O,A,P,I}(TYPEDEF,ALLOC) macro to get memory managed
    vectors.  Variables of vector type are declared using a
    VEC(TYPEDEF,ALLOC) macro.  The ALLOC argument specifies the
    allocation strategy, and can be either 'gc' or 'heap' for garbage
    collected and heap allocated respectively.  It can be 'none' to get
    a vector that must be explicitly allocated (for instance as a
-   trailing array of another structure).  The characters O, P and I
-   indicate whether TYPEDEF is a pointer (P), object (O) or integral
-   (I) type.  Be careful to pick the correct one, as you'll get an
-   awkward and inefficient API if you use the wrong one.  There is a
-   check, which results in a compile-time warning, for the P and I
-   versions, but there is no check for the O versions, as that is not
-   possible in plain C.  Due to the way GTY works, you must annotate
-   any structures you wish to insert or reference from a vector with a
-   GTY(()) tag.  You need to do this even if you never declare the GC
-   allocated variants.
+   trailing array of another structure).  The characters O, A, P and I
+   indicate whether TYPEDEF is a pointer (P), object (O), atomic object
+   (A) or integral (I) type.  Be careful to pick the correct one, as
+   you'll get an awkward and inefficient API if you use the wrong one or
+   a even a crash if you pick the atomic object version when the object
+   version should have been chosen instead.  There is a check, which
+   results in a compile-time warning, for the P and I versions, but there
+   is no check for the O versions, as that is not possible in plain C.
+   Due to the way GTY works, you must annotate any structures you wish to
+   insert or reference from a vector with a GTY(()) tag.  You need to do
+   this even if you never declare the GC allocated variants.
 
    An example of their use would be,
 
@@ -133,6 +135,153 @@ along with GCC; see the file COPYING3.  If not see
 
 */
 
+#if ENABLE_CHECKING
+#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
+#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
+#define VEC_CHECK_PASS ,file_,line_,function_
+
+#define VEC_ASSERT(EXPR,OP,T,A) \
+  (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
+
+extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
+     ATTRIBUTE_NORETURN;
+#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
+#else
+#define VEC_CHECK_INFO
+#define VEC_CHECK_DECL
+#define VEC_CHECK_PASS
+#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
+#endif
+
+#define VEC(T,A) vec_t<T>
+
+enum vec_allocation_t { heap, gc, stack };
+
+struct vec_prefix
+{
+  unsigned num;
+  unsigned alloc;
+};
+
+/* Vector type, user visible.  */
+template<typename T>
+struct GTY(()) vec_t
+{
+  vec_prefix prefix;
+  T vec[1];
+};
+
+/* Garbage collection support for vec_t.  */
+
+template<typename T>
+void
+gt_ggc_mx (vec_t<T> *v)
+{
+  extern void gt_ggc_mx (T&);
+  for (unsigned i = 0; i < v->prefix.num; i++)
+    gt_ggc_mx (v->vec[i]);
+}
+
+
+/* PCH support for vec_t.  */
+
+template<typename T>
+void
+gt_pch_nx (vec_t<T> *v)
+{
+  extern void gt_pch_nx (T&);
+  for (unsigned i = 0; i < v->prefix.num; i++)
+    gt_pch_nx (v->vec[i]);
+}
+
+template<typename T>
+void
+gt_pch_nx (vec_t<T *> *v, gt_pointer_operator op, void *cookie)
+{
+  for (unsigned i = 0; i < v->prefix.num; i++)
+    op (&(v->vec[i]), cookie);
+}
+
+template<typename T>
+void
+gt_pch_nx (vec_t<T> *v, gt_pointer_operator op, void *cookie)
+{
+  extern void gt_pch_nx (T *, gt_pointer_operator, void *);
+  for (unsigned i = 0; i < v->prefix.num; i++)
+    gt_pch_nx (&(v->vec[i]), op, cookie);
+}
+
+
+/* FIXME cxx-conversion.  Remove these definitions and update all
+   calling sites.  */
+/* Vector of integer-like object.  */
+#define DEF_VEC_I(T)			struct vec_swallow_trailing_semi
+#define DEF_VEC_ALLOC_I(T,A)		struct vec_swallow_trailing_semi
+
+/* Vector of pointer to object.  */
+#define DEF_VEC_P(T)			struct vec_swallow_trailing_semi
+#define DEF_VEC_ALLOC_P(T,A)		struct vec_swallow_trailing_semi
+
+/* Vector of object.  */
+#define DEF_VEC_O(T)			struct vec_swallow_trailing_semi
+#define DEF_VEC_ALLOC_O(T,A)		struct vec_swallow_trailing_semi
+
+/* Vectors on the stack.  */
+#define DEF_VEC_ALLOC_P_STACK(T)	struct vec_swallow_trailing_semi
+#define DEF_VEC_ALLOC_O_STACK(T)	struct vec_swallow_trailing_semi
+#define DEF_VEC_ALLOC_I_STACK(T)	struct vec_swallow_trailing_semi
+
+/* Vectors of atomic types.  Atomic types do not need to have its
+   elements marked for GC and PCH.  To avoid unnecessary traversals,
+   we provide template instantiations for the GC/PCH functions that
+   do not traverse the vector.
+
+   FIXME cxx-conversion - Once vec_t users are converted this can
+   be provided in some other way (e.g., adding an additional template
+   parameter to the vec_t class).  */
+#define DEF_VEC_A(TYPE)						\
+template<typename T>						\
+void								\
+gt_ggc_mx (vec_t<TYPE> *v ATTRIBUTE_UNUSED)			\
+{								\
+}								\
+								\
+template<typename T>						\
+void								\
+gt_pch_nx (vec_t<TYPE> *v ATTRIBUTE_UNUSED)			\
+{								\
+}								\
+								\
+template<typename T>						\
+void								\
+gt_pch_nx (vec_t<TYPE> *v ATTRIBUTE_UNUSED,			\
+	   gt_pointer_operator op ATTRIBUTE_UNUSED,		\
+	   void *cookie ATTRIBUTE_UNUSED)			\
+{								\
+}								\
+struct vec_swallow_trailing_semi
+
+#define DEF_VEC_ALLOC_A(T,A)		struct vec_swallow_trailing_semi
+
+/* Support functions for stack vectors.  */
+extern void *vec_stack_p_reserve_exact_1 (int, void *);
+extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
+extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t
+					 MEM_STAT_DECL);
+extern void vec_stack_free (void *);
+
+/* Reallocate an array of elements with prefix.  */
+template<typename T, enum vec_allocation_t A>
+extern vec_t<T> *vec_reserve (vec_t<T> *, int MEM_STAT_DECL);
+
+template<typename T, enum vec_allocation_t A>
+extern vec_t<T> *vec_reserve_exact (vec_t<T> *, int MEM_STAT_DECL);
+
+extern void dump_vec_loc_statistics (void);
+extern void ggc_free (void *);
+extern void vec_heap_free (void *);
+
+
 /* Macros to invoke API calls.  A single macro works for both pointer
    and object vectors, but the argument and return types might well be
    different.  In each macro, T is the typedef of the vector elements,
@@ -147,7 +296,14 @@ along with GCC; see the file COPYING3.  If not see
    Return the number of active elements in V.  V can be NULL, in which
    case zero is returned.  */
 
-#define VEC_length(T,V)	(VEC_OP(T,base,length)(VEC_BASE(V)))
+#define VEC_length(T,V)	(VEC_length_1<T> (V))
+
+template<typename T>
+static inline unsigned
+VEC_length_1 (const vec_t<T> *vec_)
+{
+  return vec_ ? vec_->prefix.num : 0;
+}
 
 
 /* Check if vector is empty
@@ -155,7 +311,30 @@ along with GCC; see the file COPYING3.  If not see
 
    Return nonzero if V is an empty vector (or V is NULL), zero otherwise.  */
 
-#define VEC_empty(T,V)	(VEC_length (T,V) == 0)
+#define VEC_empty(T,V)	(VEC_empty_1<T> (V))
+
+template<typename T>
+static inline bool
+VEC_empty_1 (const vec_t<T> *vec_)
+{
+  return VEC_length (T, vec_) == 0;
+}
+
+
+/* Get the address of the array of elements
+   T *VEC_T_address (VEC(T) v)
+
+   If you need to directly manipulate the array (for instance, you
+   want to feed it to qsort), use this accessor.  */
+
+#define VEC_address(T,V)	(VEC_address_1<T> (V))
+
+template<typename T>
+static inline T *
+VEC_address_1 (vec_t<T> *vec_)
+{
+  return vec_ ? vec_->vec : 0;
+}
 
 
 /* Get the final element of the vector.
@@ -165,16 +344,42 @@ along with GCC; see the file COPYING3.  If not see
 
    Return the final element.  V must not be empty.  */
 
-#define VEC_last(T,V)	(VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO))
+#define VEC_last(T,V)	(VEC_last_1<T> (V VEC_CHECK_INFO))
+
+template<typename T>
+static inline T&
+VEC_last_1 (vec_t<T> *vec_ VEC_CHECK_DECL)
+{
+  VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base);
+  return vec_->vec[vec_->prefix.num - 1];
+}
+
 
 /* Index into vector
    T VEC_T_index(VEC(T) *v, unsigned ix); // Integer
    T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer
    T *VEC_T_index(VEC(T) *v, unsigned ix); // Object
 
-   Return the IX'th element.  If IX must be in the domain of V.  */
+   Return the IX'th element.  IX must be in the domain of V.  */
+
+#define VEC_index(T,V,I) (VEC_index_1<T> (V, I VEC_CHECK_INFO))
+
+template<typename T>
+static inline T&
+VEC_index_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL)
+{
+  VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base);
+  return vec_->vec[ix_];
+}
+
+template<typename T>
+static inline const T&
+VEC_index_1 (const vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL)
+{
+  VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base);
+  return vec_->vec[ix_];
+}
 
-#define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO))
 
 /* Iterate over vector
    int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer
@@ -188,7 +393,39 @@ along with GCC; see the file COPYING3.  If not see
      for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
        continue;  */
 
-#define VEC_iterate(T,V,I,P)	(VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P)))
+#define VEC_iterate(T,V,I,P)	(VEC_iterate_1<T> (V, I, &(P)))
+
+template<typename T>
+static inline bool
+VEC_iterate_1 (const vec_t<T> *vec_, unsigned ix_, T *ptr)
+{
+  if (vec_ && ix_ < vec_->prefix.num)
+    {
+      *ptr = vec_->vec[ix_];
+      return true;
+    }
+  else
+    {
+      *ptr = 0;
+      return false;
+    }
+}
+
+template<typename T>
+static inline bool
+VEC_iterate_1 (vec_t<T> *vec_, unsigned ix_, T **ptr)
+{
+  if (vec_ && ix_ < vec_->prefix.num)
+    {
+      *ptr = &vec_->vec[ix_];
+      return true;
+    }
+  else
+    {
+      *ptr = 0;
+      return false;
+    }
+}
 
 /* Convenience macro for forward iteration.  */
 
@@ -207,31 +444,99 @@ along with GCC; see the file COPYING3.  If not see
        VEC_iterate (T, (V), (I), (P));	  \
        (I)--)
 
+
+/* Use these to determine the required size and initialization of a
+   vector embedded within another structure (as the final member).
+
+   size_t VEC_T_embedded_size(int reserve);
+   void VEC_T_embedded_init(VEC(T) *v, int reserve);
+
+   These allow the caller to perform the memory allocation.  */
+
+#define VEC_embedded_size(T,N)	 (VEC_embedded_size_1<T> (N))
+
+template<typename T>
+static inline size_t
+VEC_embedded_size_1 (int alloc_)
+{
+  return offsetof (vec_t<T>, vec) + alloc_ * sizeof (T);
+}
+
+#define VEC_embedded_init(T,O,N) (VEC_embedded_init_1<T> (O, N))
+
+template<typename T>
+static inline void
+VEC_embedded_init_1 (vec_t<T> *vec_, int alloc_)
+{
+  vec_->prefix.num = 0;
+  vec_->prefix.alloc = alloc_;
+}
+
+
 /* Allocate new vector.
    VEC(T,A) *VEC_T_A_alloc(int reserve);
 
    Allocate a new vector with space for RESERVE objects.  If RESERVE
-   is zero, NO vector is created.  */
+   is zero, NO vector is created.
+
+   We support a vector which starts out with space on the stack and
+   switches to heap space when forced to reallocate.  This works a
+   little differently.  In the case of stack vectors, VEC_alloc will
+   expand to a call to VEC_alloc_1 that calls XALLOCAVAR to request the
+   initial allocation.  This uses alloca to get the initial space.
+   Since alloca can not be usefully called in an inline function,
+   VEC_alloc must always be a macro.
+
+   Only the initial allocation will be made using alloca, so pass a
+   reasonable estimate that doesn't use too much stack space; don't
+   pass zero.  Don't return a VEC(TYPE,stack) vector from the function
+   which allocated it.  */
+
+#define VEC_alloc(T,A,N)					\
+  ((A == stack)							\
+    ? VEC_alloc_1 (N,						\
+ 		   XALLOCAVAR (vec_t<T>, 			\
+			       VEC_embedded_size_1<T> (N)))	\
+    : VEC_alloc_1<T, A> (N MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline vec_t<T> *
+VEC_alloc_1 (int alloc_ MEM_STAT_DECL)
+{
+  return vec_reserve_exact<T, A> (NULL, alloc_ PASS_MEM_STAT);
+}
+
+template<typename T>
+static inline vec_t<T> *
+VEC_alloc_1 (int alloc_, vec_t<T> *space)
+{
+  return (vec_t<T> *) vec_stack_p_reserve_exact_1 (alloc_, space);
+}
 
-#define VEC_alloc(T,A,N)	(VEC_OP(T,A,alloc)(N MEM_STAT_INFO))
 
 /* Free a vector.
    void VEC_T_A_free(VEC(T,A) *&);
 
    Free a vector and set it to NULL.  */
 
-#define VEC_free(T,A,V)	(VEC_OP(T,A,free)(&V))
+#define VEC_free(T,A,V)		(VEC_free_1<T, A> (&V))
 
-/* Use these to determine the required size and initialization of a
-   vector embedded within another structure (as the final member).
-
-   size_t VEC_T_embedded_size(int reserve);
-   void VEC_T_embedded_init(VEC(T) *v, int reserve);
-
-   These allow the caller to perform the memory allocation.  */
+template<typename T, enum vec_allocation_t A>
+static inline void
+VEC_free_1 (vec_t<T> **vec_)
+{
+  if (*vec_)
+    {
+      if (A == heap)
+	vec_heap_free (*vec_);
+      else if (A == gc)
+	ggc_free (*vec_);
+      else if (A == stack)
+	vec_stack_free (*vec_);
+    }
+  *vec_ = NULL;
+}
 
-#define VEC_embedded_size(T,N)	 (VEC_OP(T,base,embedded_size)(N))
-#define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N))
 
 /* Copy a vector.
    VEC(T,A) *VEC_T_A_copy(VEC(T) *);
@@ -239,7 +544,24 @@ along with GCC; see the file COPYING3.  If not see
    Copy the live elements of a vector into a new vector.  The new and
    old vectors need not be allocated by the same mechanism.  */
 
-#define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO))
+#define VEC_copy(T,A,V) (VEC_copy_1<T, A> (V MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline vec_t<T> *
+VEC_copy_1 (vec_t<T> *vec_ MEM_STAT_DECL)
+{
+  size_t len_ = vec_ ? vec_->prefix.num : 0;
+  vec_t<T> *new_vec_ = NULL;
+
+  if (len_)
+    {
+      new_vec_ = vec_reserve_exact<T, A> (NULL, len_ PASS_MEM_STAT);
+      new_vec_->prefix.num = len_;
+      memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_);
+    }
+  return new_vec_;
+}
+
 
 /* Determine if a vector has additional capacity.
 
@@ -251,8 +573,18 @@ along with GCC; see the file COPYING3.  If not see
    nonzero in exactly the same circumstances that VEC_T_reserve
    will.  */
 
-#define VEC_space(T,V,R) \
-	(VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO))
+#define VEC_space(T,V,R)	(VEC_space_1<T> (V, R VEC_CHECK_INFO))
+
+template<typename T>
+static inline int
+VEC_space_1 (vec_t<T> *vec_, int alloc_ VEC_CHECK_DECL)
+{
+  VEC_ASSERT (alloc_ >= 0, "space", T, base);
+  return vec_
+	 ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_
+	 : !alloc_;
+}
+
 
 /* Reserve space.
    int VEC_T_A_reserve(VEC(T,A) *&v, int reserve);
@@ -263,7 +595,20 @@ along with GCC; see the file COPYING3.  If not see
    occurred.  */
 
 #define VEC_reserve(T,A,V,R)	\
-	(VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
+  	(VEC_reserve_1<T, A> (&(V), (int)(R) VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline int
+VEC_reserve_1 (vec_t<T> **vec_, int alloc_  VEC_CHECK_DECL MEM_STAT_DECL)
+{
+  int extend = !VEC_space_1 (*vec_, alloc_ VEC_CHECK_PASS);
+
+  if (extend)
+    *vec_ = vec_reserve<T, A> (*vec_, alloc_ PASS_MEM_STAT);
+
+  return extend;
+}
+
 
 /* Reserve space exactly.
    int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve);
@@ -274,7 +619,20 @@ along with GCC; see the file COPYING3.  If not see
    occurred.  */
 
 #define VEC_reserve_exact(T,A,V,R)	\
-	(VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
+	(VEC_reserve_exact_1<T, A> (&(V), R VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline int
+VEC_reserve_exact_1 (vec_t<T> **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)
+{
+  int extend = !VEC_space_1 (*vec_, alloc_ VEC_CHECK_PASS);
+
+  if (extend)
+    *vec_ = vec_reserve_exact<T, A> (*vec_, alloc_ PASS_MEM_STAT);
+
+  return extend;
+}
+
 
 /* Copy elements with no reallocation
    void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Integer
@@ -286,8 +644,23 @@ along with GCC; see the file COPYING3.  If not see
    often will be.  DST is assumed to have sufficient headroom
    available.  */
 
-#define VEC_splice(T,DST,SRC)			\
-  (VEC_OP(T,base,splice)(VEC_BASE(DST), VEC_BASE(SRC) VEC_CHECK_INFO))
+#define VEC_splice(T,DST,SRC)	(VEC_splice_1<T> (DST, SRC VEC_CHECK_INFO))
+
+template<typename T>
+static inline void
+VEC_splice_1 (vec_t<T> *dst_, vec_t<T> *src_ VEC_CHECK_DECL)
+{
+  if (src_)
+    {
+      unsigned len_ = src_->prefix.num;
+      VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice",
+		  T, base);
+
+      memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T));
+      dst_->prefix.num += len_;
+    }
+}
+
 
 /* Copy elements with reallocation
    void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Integer
@@ -300,7 +673,21 @@ along with GCC; see the file COPYING3.  If not see
    reallocated if needed.  */
 
 #define VEC_safe_splice(T,A,DST,SRC)					\
-  (VEC_OP(T,A,safe_splice)(&(DST), VEC_BASE(SRC) VEC_CHECK_INFO MEM_STAT_INFO))
+	(VEC_safe_splice_1<T, A> (&(DST), SRC VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline void
+VEC_safe_splice_1 (vec_t<T> **dst_, vec_t<T> *src_ VEC_CHECK_DECL MEM_STAT_DECL)
+{
+  if (src_)
+    {
+      VEC_reserve_exact_1<T, A> (dst_, src_->prefix.num
+				 VEC_CHECK_PASS MEM_STAT_INFO);
+
+      VEC_splice_1 (*dst_, src_ VEC_CHECK_PASS);
+    }
+}
+
   
 /* Push object with no reallocation
    T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer
@@ -312,8 +699,31 @@ along with GCC; see the file COPYING3.  If not see
    case NO initialization is performed.  There must
    be sufficient space in the vector.  */
 
-#define VEC_quick_push(T,V,O)	\
-	(VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO))
+#define VEC_quick_push(T,V,O)	(VEC_quick_push_1<T> (V, O VEC_CHECK_INFO))
+
+template<typename T>
+static inline T &
+VEC_quick_push_1 (vec_t<T> *vec_, T obj_ VEC_CHECK_DECL)
+{
+  VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base);
+  vec_->vec[vec_->prefix.num] = obj_;
+  T &val_ = vec_->vec[vec_->prefix.num];
+  vec_->prefix.num++;
+  return val_;
+}
+
+template<typename T>
+static inline T *
+VEC_quick_push_1 (vec_t<T> *vec_, const T *ptr_ VEC_CHECK_DECL)
+{
+  T *slot_;
+  VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base);
+  slot_ = &vec_->vec[vec_->prefix.num++];
+  if (ptr_)
+    *slot_ = *ptr_;
+  return slot_;
+}
+
 
 /* Push object with reallocation
    T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer
@@ -325,7 +735,24 @@ along with GCC; see the file COPYING3.  If not see
    case NO initialization is performed.  Reallocates V, if needed.  */
 
 #define VEC_safe_push(T,A,V,O)		\
-	(VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO))
+	(VEC_safe_push_1<T, A> (&(V), O VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline T &
+VEC_safe_push_1 (vec_t<T> **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)
+{
+  VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);
+  return VEC_quick_push_1 (*vec_, obj_ VEC_CHECK_PASS);
+}
+
+template<typename T, enum vec_allocation_t A>
+static inline T *
+VEC_safe_push_1 (vec_t<T> **vec_, const T *ptr_ VEC_CHECK_DECL MEM_STAT_DECL)
+{
+  VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);
+  return VEC_quick_push_1 (*vec_, ptr_ VEC_CHECK_PASS);
+}
+
 
 /* Pop element off end
    T VEC_T_pop (VEC(T) *v);		// Integer
@@ -335,7 +762,16 @@ along with GCC; see the file COPYING3.  If not see
    Pop the last element off the end. Returns the element popped, for
    pointer vectors.  */
 
-#define VEC_pop(T,V)	(VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO))
+#define VEC_pop(T,V)	(VEC_pop_1<T> (V VEC_CHECK_INFO))
+
+template<typename T>
+static inline T&
+VEC_pop_1 (vec_t<T> *vec_ VEC_CHECK_DECL)
+{
+  VEC_ASSERT (vec_->prefix.num, "pop", T, base);
+  return vec_->vec[--vec_->prefix.num];
+}
+
 
 /* Truncate to specific length
    void VEC_T_truncate (VEC(T) *v, unsigned len);
@@ -343,8 +779,18 @@ along with GCC; see the file COPYING3.  If not see
    Set the length as specified.  The new length must be less than or
    equal to the current length.  This is an O(1) operation.  */
 
-#define VEC_truncate(T,V,I)		\
-	(VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO))
+#define VEC_truncate(T,V,I)	\
+	(VEC_truncate_1<T> (V, (unsigned)(I) VEC_CHECK_INFO))
+
+template<typename T>
+static inline void
+VEC_truncate_1 (vec_t<T> *vec_, unsigned size_ VEC_CHECK_DECL)
+{
+  VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base);
+  if (vec_)
+    vec_->prefix.num = size_;
+}
+
 
 /* Grow to a specific length.
    void VEC_T_A_safe_grow (VEC(T,A) *&v, int len);
@@ -354,7 +800,20 @@ along with GCC; see the file COPYING3.  If not see
    uninitialized.  */
 
 #define VEC_safe_grow(T,A,V,I)		\
-	(VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
+	(VEC_safe_grow_1<T, A> (&(V), (int)(I) VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline void
+VEC_safe_grow_1 (vec_t<T> **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)
+{
+  VEC_ASSERT (size_ >= 0 && VEC_length (T, *vec_) <= (unsigned)size_,
+	      "grow", T, A);
+  VEC_reserve_exact_1<T, A> (vec_,
+			     size_ - (int)(*vec_ ? (*vec_)->prefix.num : 0)
+			     VEC_CHECK_PASS PASS_MEM_STAT);
+  (*vec_)->prefix.num = size_;
+}
+
 
 /* Grow to a specific length.
    void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len);
@@ -363,8 +822,21 @@ along with GCC; see the file COPYING3.  If not see
    long or longer than the current length.  The new elements are
    initialized to zero.  */
 
-#define VEC_safe_grow_cleared(T,A,V,I)		\
-	(VEC_OP(T,A,safe_grow_cleared)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
+#define VEC_safe_grow_cleared(T,A,V,I)			\
+	(VEC_safe_grow_cleared_1<T,A> (&(V), (int)(I)	\
+				       VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline void
+VEC_safe_grow_cleared_1 (vec_t<T> **vec_, int size_ VEC_CHECK_DECL
+			 MEM_STAT_DECL)
+{
+  int oldsize = VEC_length (T, *vec_);
+  VEC_safe_grow_1<T, A> (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);
+  memset (&(VEC_address (T, *vec_)[oldsize]), 0,
+	  sizeof (T) * (size_ - oldsize));
+}
+
 
 /* Replace element
    T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer
@@ -378,20 +850,57 @@ along with GCC; see the file COPYING3.  If not see
    performed.  */
 
 #define VEC_replace(T,V,I,O)		\
-	(VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO))
+	(VEC_replace_1<T> (V, (unsigned)(I), O VEC_CHECK_INFO))
+
+template<typename T>
+static inline T&
+VEC_replace_1 (vec_t<T> *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)
+{
+  VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base);
+  vec_->vec[ix_] = obj_;
+  return vec_->vec[ix_];
+}
+
 
 /* Insert object with no reallocation
-   T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
-   T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
-   T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
+   void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
+   void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
+   void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
 
-   Insert an element, VAL, at the IXth position of V. Return a pointer
-   to the slot created.  For vectors of object, the new value can be
-   NULL, in which case no initialization of the inserted slot takes
-   place. There must be sufficient space.  */
+   Insert an element, VAL, at the IXth position of V.  For vectors of
+   object, the new value can be NULL, in which case no initialization
+   of the inserted slot takes place. There must be sufficient space.  */
 
 #define VEC_quick_insert(T,V,I,O)	\
-	(VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO))
+	(VEC_quick_insert_1<T> (V,I,O VEC_CHECK_INFO))
+
+template<typename T>
+static inline void
+VEC_quick_insert_1 (vec_t<T> *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)
+{
+  T *slot_;
+
+  VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base);
+  VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base);
+  slot_ = &vec_->vec[ix_];
+  memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T));
+  *slot_ = obj_;
+}
+
+template<typename T>
+static inline void
+VEC_quick_insert_1 (vec_t<T> *vec_, unsigned ix_, const T *ptr_ VEC_CHECK_DECL)
+{
+  T *slot_;
+
+  VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base);
+  VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base);
+  slot_ = &vec_->vec[ix_];
+  memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T));
+  if (ptr_)
+    *slot_ = *ptr_;
+}
+
 
 /* Insert object with reallocation
    T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer
@@ -404,31 +913,70 @@ along with GCC; see the file COPYING3.  If not see
    place. Reallocate V, if necessary.  */
 
 #define VEC_safe_insert(T,A,V,I,O)	\
-	(VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
+	(VEC_safe_insert_1<T, A> (&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline void
+VEC_safe_insert_1 (vec_t<T> **vec_, unsigned ix_, T obj_
+		   VEC_CHECK_DECL MEM_STAT_DECL)
+{
+  VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);
+  VEC_quick_insert_1 (*vec_, ix_, obj_ VEC_CHECK_PASS);
+}
+
+template<typename T, enum vec_allocation_t A>
+static inline void
+VEC_safe_insert_1 (vec_t<T> **vec_, unsigned ix_, T *ptr_
+		   VEC_CHECK_DECL MEM_STAT_DECL)
+{
+  VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);
+  VEC_quick_insert_1 (*vec_, ix_, ptr_ VEC_CHECK_PASS);
+}
+
+
 
 /* Remove element retaining order
-   T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
-   T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
+   void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
+   void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
    void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
 
    Remove an element from the IXth position of V. Ordering of
-   remaining elements is preserved.  For pointer vectors returns the
-   removed object.  This is an O(N) operation due to a memmove.  */
+   remaining elements is preserved.  This is an O(N) operation due to
+   a memmove.  */
 
 #define VEC_ordered_remove(T,V,I)	\
-	(VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
+	(VEC_ordered_remove_1<T> (V,I VEC_CHECK_INFO))
+
+template<typename T>
+static inline void
+VEC_ordered_remove_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL)
+{
+  T *slot_;
+  VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base);
+  slot_ = &vec_->vec[ix_];
+  memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T));
+}
+
 
 /* Remove element destroying order
-   T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
-   T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
+   void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
+   void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
    void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
 
-   Remove an element from the IXth position of V. Ordering of
-   remaining elements is destroyed.  For pointer vectors returns the
-   removed object.  This is an O(1) operation.  */
+   Remove an element from the IXth position of V.  Ordering of
+   remaining elements is destroyed.  This is an O(1) operation.  */
 
 #define VEC_unordered_remove(T,V,I)	\
-	(VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
+	(VEC_unordered_remove_1<T> (V,I VEC_CHECK_INFO))
+
+template<typename T>
+static inline void
+VEC_unordered_remove_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL)
+{
+  VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base);
+  vec_->vec[ix_] = vec_->vec[--vec_->prefix.num];
+}
+
 
 /* Remove a block of elements
    void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
@@ -437,22 +985,27 @@ along with GCC; see the file COPYING3.  If not see
    This is an O(N) operation due to memmove.  */
 
 #define VEC_block_remove(T,V,I,L)	\
-	(VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO))
+	(VEC_block_remove_1<T> (V, I, L VEC_CHECK_INFO))
 
-/* Get the address of the array of elements
-   T *VEC_T_address (VEC(T) v)
-
-   If you need to directly manipulate the array (for instance, you
-   want to feed it to qsort), use this accessor.  */
+template<typename T>
+static inline void
+VEC_block_remove_1 (vec_t<T> *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)
+{
+  T *slot_;
+  VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base);
+  slot_ = &vec_->vec[ix_];
+  vec_->prefix.num -= len_;
+  memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T));
+}
 
-#define VEC_address(T,V)		(VEC_OP(T,base,address)(VEC_BASE(V)))
 
 /* Conveniently sort the contents of the vector with qsort.
    void VEC_qsort (VEC(T) *v, int (*cmp_func)(const void *, const void *))  */
 
-#define VEC_qsort(T,V,CMP) qsort(VEC_address (T,V), VEC_length(T,V),	\
+#define VEC_qsort(T,V,CMP) qsort(VEC_address (T, V), VEC_length (T, V),	\
 				 sizeof (T), CMP)
 
+
 /* Find the first index in the vector not less than the object.
    unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
                                bool (*lessthan) (const T, const T)); // Integer
@@ -465,944 +1018,128 @@ along with GCC; see the file COPYING3.  If not see
    changing the ordering of V.  LESSTHAN is a function that returns
    true if the first argument is strictly less than the second.  */
 
-#define VEC_lower_bound(T,V,O,LT)    \
-       (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO))
+#define VEC_lower_bound(T,V,O,LT)	\
+        (VEC_lower_bound_1<T> (V, O, LT VEC_CHECK_INFO))
 
-/* Reallocate an array of elements with prefix.  */
-extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL);
-extern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL);
-extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
-extern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t
-				     MEM_STAT_DECL);
-extern void ggc_free (void *);
-#define vec_gc_free(V) ggc_free (V)
-extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL);
-extern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL);
-extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
-extern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t
-				       MEM_STAT_DECL);
-extern void dump_vec_loc_statistics (void);
-#ifdef GATHER_STATISTICS
-void vec_heap_free (void *);
-#else
-/* Avoid problems with frontends that #define free(x).  */
-#define vec_heap_free(V) (free) (V)
-#endif
-
-#if ENABLE_CHECKING
-#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
-#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
-#define VEC_CHECK_PASS ,file_,line_,function_
-
-#define VEC_ASSERT(EXPR,OP,T,A) \
-  (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
-
-extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
-     ATTRIBUTE_NORETURN;
-#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
-#else
-#define VEC_CHECK_INFO
-#define VEC_CHECK_DECL
-#define VEC_CHECK_PASS
-#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
-#endif
-
-/* Note: gengtype has hardwired knowledge of the expansions of the
-   VEC, DEF_VEC_*, and DEF_VEC_ALLOC_* macros.  If you change the
-   expansions of these macros you may need to change gengtype too.  */
-
-typedef struct GTY(()) vec_prefix
+template<typename T>
+static inline unsigned
+VEC_lower_bound_1 (vec_t<T> *vec_, T obj_,
+		   bool (*lessthan_)(T, T) VEC_CHECK_DECL)
 {
-  unsigned num;
-  unsigned alloc;
-} vec_prefix;
-
-#define VEC(T,A) VEC_##T##_##A
-#define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP
-
-/* Base of vector type, not user visible.  */
-#define VEC_T(T,B)							  \
-typedef struct VEC(T,B) 				 		  \
-{									  \
-  struct vec_prefix prefix;						  \
-  T vec[1];								  \
-} VEC(T,B)
-
-#define VEC_T_GTY(T,B)							  \
-typedef struct GTY(()) VEC(T,B)				 		  \
-{									  \
-  struct vec_prefix prefix;						  \
-  T GTY ((length ("%h.prefix.num"))) vec[1];				  \
-} VEC(T,B)
-
-/* Derived vector type, user visible.  */
-#define VEC_TA_GTY(T,B,A,GTY)						  \
-typedef struct GTY VEC(T,A)						  \
-{									  \
-  VEC(T,B) base;							  \
-} VEC(T,A)
-
-#define VEC_TA(T,B,A)							  \
-typedef struct VEC(T,A)							  \
-{									  \
-  VEC(T,B) base;							  \
-} VEC(T,A)
-
-/* Convert to base type.  */
-#if GCC_VERSION >= 4000
-#define VEC_BASE(P) \
-  ((offsetof (__typeof (*P), base) == 0 || (P)) ? &(P)->base : 0)
-#else
-#define VEC_BASE(P)  ((P) ? &(P)->base : 0)
-#endif
-
-/* Vector of integer-like object.  */
-#define DEF_VEC_I(T)							  \
-static inline void VEC_OP (T,must_be,integral_type) (void) 		  \
-{									  \
-  (void)~(T)0;								  \
-}									  \
-									  \
-VEC_T(T,base);								  \
-VEC_TA(T,base,none);							  \
-DEF_VEC_FUNC_P(T)							  \
-struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_I(T,A)						  \
-VEC_TA(T,base,A);							  \
-DEF_VEC_ALLOC_FUNC_I(T,A)						  \
-DEF_VEC_NONALLOC_FUNCS_I(T,A)						  \
-struct vec_swallow_trailing_semi
-
-/* Vector of pointer to object.  */
-#define DEF_VEC_P(T) 							  \
-static inline void VEC_OP (T,must_be,pointer_type) (void) 		  \
-{									  \
-  (void)((T)1 == (void *)1);						  \
-}									  \
-									  \
-VEC_T_GTY(T,base);							  \
-VEC_TA(T,base,none);							  \
-DEF_VEC_FUNC_P(T)							  \
-struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_P(T,A)						  \
-VEC_TA(T,base,A);							  \
-DEF_VEC_ALLOC_FUNC_P(T,A)						  \
-DEF_VEC_NONALLOC_FUNCS_P(T,A)						  \
-struct vec_swallow_trailing_semi
-
-#define DEF_VEC_FUNC_P(T)						  \
-static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_)   \
-{									  \
-  return vec_ ? vec_->prefix.num : 0;						  \
-}									  \
-									  \
-static inline T VEC_OP (T,base,last)					  \
-     (const VEC(T,base) *vec_ VEC_CHECK_DECL)				  \
-{									  \
-  VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base);			  \
-  									  \
-  return vec_->vec[vec_->prefix.num - 1];					  \
-}									  \
-									  \
-static inline T VEC_OP (T,base,index)					  \
-     (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)		  \
-{									  \
-  VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base);		  \
-  									  \
-  return vec_->vec[ix_];						  \
-}									  \
-									  \
-static inline int VEC_OP (T,base,iterate)			  	  \
-     (const VEC(T,base) *vec_, unsigned ix_, T *ptr)			  \
-{									  \
-  if (vec_ && ix_ < vec_->prefix.num)						  \
-    {									  \
-      *ptr = vec_->vec[ix_];						  \
-      return 1;								  \
-    }									  \
-  else									  \
-    {									  \
-      *ptr = (T) 0;							  \
-      return 0;								  \
-    }									  \
-}									  \
-									  \
-static inline size_t VEC_OP (T,base,embedded_size)			  \
-     (int alloc_)							  \
-{									  \
-  return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T);		  \
-}									  \
-									  \
-static inline void VEC_OP (T,base,embedded_init)			  \
-     (VEC(T,base) *vec_, int alloc_)					  \
-{									  \
-  vec_->prefix.num = 0;							  \
-  vec_->prefix.alloc = alloc_;							  \
-}									  \
-									  \
-static inline int VEC_OP (T,base,space)	       				  \
-     (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL)			  \
-{									  \
-  VEC_ASSERT (alloc_ >= 0, "space", T, base);				  \
-  return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ : !alloc_;	  \
-}									  \
-									  \
-static inline void VEC_OP(T,base,splice)				  \
-     (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL)		  \
-{									  \
-  if (src_)								  \
-    {									  \
-      unsigned len_ = src_->prefix.num;					  \
-      VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T, base);	  \
-									  \
-      memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T));	  \
-      dst_->prefix.num += len_;						  \
-    }									  \
-}									  \
-									  \
-static inline T *VEC_OP (T,base,quick_push)				  \
-     (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL)				  \
-{									  \
-  T *slot_;								  \
-  									  \
-  VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base);		  \
-  slot_ = &vec_->vec[vec_->prefix.num++];					  \
-  *slot_ = obj_;							  \
-  									  \
-  return slot_;								  \
-}									  \
-									  \
-static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL)	  \
-{									  \
-  T obj_;								  \
-									  \
-  VEC_ASSERT (vec_->prefix.num, "pop", T, base);				  \
-  obj_ = vec_->vec[--vec_->prefix.num];					  \
-									  \
-  return obj_;								  \
-}									  \
-									  \
-static inline void VEC_OP (T,base,truncate)				  \
-     (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL)			  \
-{									  \
-  VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base);	  \
-  if (vec_)								  \
-    vec_->prefix.num = size_;							  \
-}									  \
-									  \
-static inline T VEC_OP (T,base,replace)		  	     		  \
-     (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)		  \
-{									  \
-  T old_obj_;								  \
-									  \
-  VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base);			  \
-  old_obj_ = vec_->vec[ix_];						  \
-  vec_->vec[ix_] = obj_;						  \
-									  \
-  return old_obj_;							  \
-}									  \
-									  \
-static inline T *VEC_OP (T,base,quick_insert)				  \
-     (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)		  \
-{									  \
-  T *slot_;								  \
-									  \
-  VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base);		  \
-  VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base);			  \
-  slot_ = &vec_->vec[ix_];						  \
-  memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T));		  \
-  *slot_ = obj_;							  \
-  									  \
-  return slot_;								  \
-}									  \
-									  \
-static inline T VEC_OP (T,base,ordered_remove)				  \
-     (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)			  \
-{									  \
-  T *slot_;								  \
-  T obj_;								  \
-									  \
-  VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base);			  \
-  slot_ = &vec_->vec[ix_];						  \
-  obj_ = *slot_;							  \
-  memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T));     	  \
-									  \
-  return obj_;								  \
-}									  \
-									  \
-static inline T VEC_OP (T,base,unordered_remove)			  \
-     (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)			  \
-{									  \
-  T *slot_;								  \
-  T obj_;								  \
-									  \
-  VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base);			  \
-  slot_ = &vec_->vec[ix_];						  \
-  obj_ = *slot_;							  \
-  *slot_ = vec_->vec[--vec_->prefix.num];					  \
-									  \
-  return obj_;								  \
-}									  \
-									  \
-static inline void VEC_OP (T,base,block_remove)				  \
-     (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)	  \
-{									  \
-  T *slot_;								  \
-									  \
-  VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base);	  \
-  slot_ = &vec_->vec[ix_];						  \
-  vec_->prefix.num -= len_;							  \
-  memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T));	  \
-}									  \
-									  \
-static inline T *VEC_OP (T,base,address)				  \
-     (VEC(T,base) *vec_)						  \
-{									  \
-  return vec_ ? vec_->vec : 0;						  \
-}									  \
-									  \
-static inline unsigned VEC_OP (T,base,lower_bound)			  \
-     (VEC(T,base) *vec_, const T obj_,					  \
-      bool (*lessthan_)(const T, const T) VEC_CHECK_DECL)		  \
-{									  \
-   unsigned int len_ = VEC_OP (T,base, length) (vec_);			  \
-   unsigned int half_, middle_;						  \
-   unsigned int first_ = 0;						  \
-   while (len_ > 0)							  \
-     {									  \
-        T middle_elem_;							  \
-        half_ = len_ >> 1;						  \
-        middle_ = first_;						  \
-        middle_ += half_;						  \
-        middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
-        if (lessthan_ (middle_elem_, obj_))				  \
-          {								  \
-             first_ = middle_;						  \
-             ++first_;							  \
-             len_ = len_ - half_ - 1;					  \
-          }								  \
-        else								  \
-          len_ = half_;							  \
-     }									  \
-   return first_;							  \
-}
-
-#define DEF_VEC_ALLOC_FUNC_P(T,A)					  \
-static inline VEC(T,A) *VEC_OP (T,A,alloc)				  \
-     (int alloc_ MEM_STAT_DECL)						  \
-{									  \
-  return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_		  \
-						 PASS_MEM_STAT);	  \
+  unsigned int len_ = VEC_length (T, vec_);
+  unsigned int half_, middle_;
+  unsigned int first_ = 0;
+  while (len_ > 0)
+    {
+      T middle_elem_;
+      half_ = len_ >> 1;
+      middle_ = first_;
+      middle_ += half_;
+      middle_elem_ = VEC_index_1 (vec_, middle_ VEC_CHECK_PASS);
+      if (lessthan_ (middle_elem_, obj_))
+	{
+	  first_ = middle_;
+	  ++first_;
+	  len_ = len_ - half_ - 1;
+	}
+      else
+	len_ = half_;
+    }
+  return first_;
 }
 
-
-#define DEF_VEC_NONALLOC_FUNCS_P(T,A)					  \
-static inline void VEC_OP (T,A,free)					  \
-     (VEC(T,A) **vec_)							  \
-{									  \
-  if (*vec_)								  \
-    vec_##A##_free (*vec_);						  \
-  *vec_ = NULL;								  \
-}									  \
-									  \
-static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
-{									  \
-  size_t len_ = vec_ ? vec_->prefix.num : 0;					  \
-  VEC (T,A) *new_vec_ = NULL;						  \
-									  \
-  if (len_)								  \
-    {									  \
-      new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact		  \
-			       (NULL, len_ PASS_MEM_STAT));		  \
-									  \
-      new_vec_->base.prefix.num = len_;					  \
-      memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);	  \
-    }									  \
-  return new_vec_;							  \
-}									  \
-									  \
-static inline int VEC_OP (T,A,reserve)	       				  \
-     (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)		  \
-{									  \
-  int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_		  \
-				       VEC_CHECK_PASS);			  \
-		  							  \
-  if (extend)	  							  \
-    *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
-		  							  \
-  return extend;							  \
-}									  \
-									  \
-static inline int VEC_OP (T,A,reserve_exact)  				  \
-     (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)		  \
-{									  \
-  int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_		  \
-				       VEC_CHECK_PASS);			  \
-		  							  \
-  if (extend)	  							  \
-    *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_	  \
-						    PASS_MEM_STAT);	  \
-		  							  \
-  return extend;							  \
-}									  \
-									  \
-static inline void VEC_OP (T,A,safe_grow)				  \
-     (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)		  \
-{									  \
-  VEC_ASSERT (size_ >= 0						  \
-	      && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
-						 "grow", T, A);		  \
-  VEC_OP (T,A,reserve_exact) (vec_,					  \
-			      size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
-			      VEC_CHECK_PASS PASS_MEM_STAT);		  \
-  VEC_BASE (*vec_)->prefix.num = size_;					  \
-}									  \
-									  \
-static inline void VEC_OP (T,A,safe_grow_cleared)			  \
-     (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)		  \
-{									  \
-  int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);			  \
-  VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);	  \
-  memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,	  \
-	  sizeof (T) * (size_ - oldsize));				  \
-}									  \
-									  \
-static inline void VEC_OP(T,A,safe_splice)				  \
-     (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL)	  \
-{									  \
-  if (src_)								  \
-    {									  \
-      VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num			  \
-				  VEC_CHECK_PASS MEM_STAT_INFO);	  \
-									  \
-      VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_			  \
-			      VEC_CHECK_PASS);				  \
-    }									  \
-}									  \
-									  \
-static inline T *VEC_OP (T,A,safe_push)					  \
-     (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)       	  \
-{									  \
-  VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);		  \
-									  \
-  return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
-}									  \
-									  \
-static inline T *VEC_OP (T,A,safe_insert)		     	  	  \
-     (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)  \
-{									  \
-  VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);		  \
-									  \
-  return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_	  \
- 				       VEC_CHECK_PASS);			  \
-}
-
-/* Vector of object.  */
-#define DEF_VEC_O(T)							  \
-VEC_T_GTY(T,base);							  \
-VEC_TA(T,base,none);						  \
-DEF_VEC_FUNC_O(T)							  \
-struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_O(T,A)						  \
-VEC_TA(T,base,A);							  \
-DEF_VEC_ALLOC_FUNC_O(T,A)						  \
-DEF_VEC_NONALLOC_FUNCS_O(T,A)						  \
-struct vec_swallow_trailing_semi
-
-#define DEF_VEC_FUNC_O(T)						  \
-static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_)	  \
-{									  \
-  return vec_ ? vec_->prefix.num : 0;						  \
-}									  \
-									  \
-static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL)  \
-{									  \
-  VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base);			  \
-  									  \
-  return &vec_->vec[vec_->prefix.num - 1];					  \
-}									  \
-									  \
-static inline T *VEC_OP (T,base,index)					  \
-     (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)			  \
-{									  \
-  VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base);		  \
-  									  \
-  return &vec_->vec[ix_];						  \
-}									  \
-									  \
-static inline int VEC_OP (T,base,iterate)			     	  \
-     (VEC(T,base) *vec_, unsigned ix_, T **ptr)				  \
-{									  \
-  if (vec_ && ix_ < vec_->prefix.num)						  \
-    {									  \
-      *ptr = &vec_->vec[ix_];						  \
-      return 1;								  \
-    }									  \
-  else									  \
-    {									  \
-      *ptr = 0;								  \
-      return 0;								  \
-    }									  \
-}									  \
-									  \
-static inline size_t VEC_OP (T,base,embedded_size)			  \
-     (int alloc_)							  \
-{									  \
-  return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T);		  \
-}									  \
-									  \
-static inline void VEC_OP (T,base,embedded_init)			  \
-     (VEC(T,base) *vec_, int alloc_)					  \
-{									  \
-  vec_->prefix.num = 0;							  \
-  vec_->prefix.alloc = alloc_;							  \
-}									  \
-									  \
-static inline int VEC_OP (T,base,space)	       				  \
-     (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL)			  \
-{									  \
-  VEC_ASSERT (alloc_ >= 0, "space", T, base);				  \
-  return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ : !alloc_;	  \
-}									  \
-									  \
-static inline void VEC_OP(T,base,splice)				  \
-     (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL)		  \
-{									  \
-  if (src_)								  \
-    {									  \
-      unsigned len_ = src_->prefix.num;					  \
-      VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T, base);	  \
-									  \
-      memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T));	  \
-      dst_->prefix.num += len_;						  \
-    }									  \
-}									  \
-									  \
-static inline T *VEC_OP (T,base,quick_push)				  \
-     (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL)			  \
-{									  \
-  T *slot_;								  \
-  									  \
-  VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base);		  \
-  slot_ = &vec_->vec[vec_->prefix.num++];					  \
-  if (obj_)								  \
-    *slot_ = *obj_;							  \
-  									  \
-  return slot_;								  \
-}									  \
-									  \
-static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
-{									  \
-  VEC_ASSERT (vec_->prefix.num, "pop", T, base);				  \
-  --vec_->prefix.num;								  \
-}									  \
-									  \
-static inline void VEC_OP (T,base,truncate)				  \
-     (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL)			  \
-{									  \
-  VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base);	  \
-  if (vec_)								  \
-    vec_->prefix.num = size_;							  \
-}									  \
-									  \
-static inline T *VEC_OP (T,base,replace)				  \
-     (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL)	  \
-{									  \
-  T *slot_;								  \
-									  \
-  VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base);			  \
-  slot_ = &vec_->vec[ix_];						  \
-  if (obj_)								  \
-    *slot_ = *obj_;							  \
-									  \
-  return slot_;								  \
-}									  \
-									  \
-static inline T *VEC_OP (T,base,quick_insert)				  \
-     (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL)	  \
-{									  \
-  T *slot_;								  \
-									  \
-  VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base);		  \
-  VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base);			  \
-  slot_ = &vec_->vec[ix_];						  \
-  memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T));		  \
-  if (obj_)								  \
-    *slot_ = *obj_;							  \
-  									  \
-  return slot_;								  \
-}									  \
-									  \
-static inline void VEC_OP (T,base,ordered_remove)			  \
-     (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)			  \
-{									  \
-  T *slot_;								  \
-									  \
-  VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base);			  \
-  slot_ = &vec_->vec[ix_];						  \
-  memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T));		  \
-}									  \
-									  \
-static inline void VEC_OP (T,base,unordered_remove)			  \
-     (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)			  \
-{									  \
-  VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base);			  \
-  vec_->vec[ix_] = vec_->vec[--vec_->prefix.num];				  \
-}									  \
-									  \
-static inline void VEC_OP (T,base,block_remove)				  \
-     (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)	  \
-{									  \
-  T *slot_;								  \
-									  \
-  VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base);	  \
-  slot_ = &vec_->vec[ix_];						  \
-  vec_->prefix.num -= len_;							  \
-  memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T));	  \
-}									  \
-									  \
-static inline T *VEC_OP (T,base,address)				  \
-     (VEC(T,base) *vec_)						  \
-{									  \
-  return vec_ ? vec_->vec : 0;						  \
-}									  \
-									  \
-static inline unsigned VEC_OP (T,base,lower_bound)			  \
-     (VEC(T,base) *vec_, const T *obj_,					  \
-      bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL)		  \
-{									  \
-   unsigned int len_ = VEC_OP (T, base, length) (vec_);			  \
-   unsigned int half_, middle_;						  \
-   unsigned int first_ = 0;						  \
-   while (len_ > 0)							  \
-     {									  \
-        T *middle_elem_;						  \
-        half_ = len_ >> 1;						  \
-        middle_ = first_;						  \
-        middle_ += half_;						  \
-        middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
-        if (lessthan_ (middle_elem_, obj_))				  \
-          {								  \
-             first_ = middle_;						  \
-             ++first_;							  \
-             len_ = len_ - half_ - 1;					  \
-          }								  \
-        else								  \
-          len_ = half_;							  \
-     }									  \
-   return first_;							  \
-}
-
-#define DEF_VEC_ALLOC_FUNC_O(T,A)					  \
-static inline VEC(T,A) *VEC_OP (T,A,alloc)      			  \
-     (int alloc_ MEM_STAT_DECL)						  \
-{									  \
-  return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_,		  \
-						 offsetof (VEC(T,A),base.vec), \
-						 sizeof (T)		  \
-						 PASS_MEM_STAT);	  \
-}
-
-#define DEF_VEC_NONALLOC_FUNCS_O(T,A)					  \
-static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
-{									  \
-  size_t len_ = vec_ ? vec_->prefix.num : 0;					  \
-  VEC (T,A) *new_vec_ = NULL;						  \
-									  \
-  if (len_)								  \
-    {									  \
-      new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact		  \
-			       (NULL, len_,				  \
-				offsetof (VEC(T,A),base.vec), sizeof (T)  \
-				PASS_MEM_STAT));			  \
-									  \
-      new_vec_->base.prefix.num = len_;					  \
-      memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);	  \
-    }									  \
-  return new_vec_;							  \
-}									  \
-									  \
-static inline void VEC_OP (T,A,free)					  \
-     (VEC(T,A) **vec_)							  \
-{									  \
-  if (*vec_)								  \
-    vec_##A##_free (*vec_);						  \
-  *vec_ = NULL;								  \
-}									  \
-									  \
-static inline int VEC_OP (T,A,reserve)	   	    			  \
-     (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)		  \
-{									  \
-  int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_		  \
-				       VEC_CHECK_PASS);			  \
-									  \
-  if (extend)								  \
-    *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_,		  \
-			   		      offsetof (VEC(T,A),base.vec),\
- 					      sizeof (T)		  \
-			   		      PASS_MEM_STAT);		  \
-									  \
-  return extend;							  \
-}									  \
-									  \
-static inline int VEC_OP (T,A,reserve_exact)   	    			  \
-     (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)		  \
-{									  \
-  int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_		  \
-				       VEC_CHECK_PASS);			  \
-									  \
-  if (extend)								  \
-    *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact			  \
-			 (*vec_, alloc_,				  \
-			  offsetof (VEC(T,A),base.vec),			  \
-			  sizeof (T) PASS_MEM_STAT);			  \
-									  \
-  return extend;							  \
-}									  \
-									  \
-static inline void VEC_OP (T,A,safe_grow)				  \
-     (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)		  \
-{									  \
-  VEC_ASSERT (size_ >= 0						  \
-	      && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
-						 "grow", T, A);		  \
-  VEC_OP (T,A,reserve_exact) (vec_,					  \
-			      size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
-			      VEC_CHECK_PASS PASS_MEM_STAT);		  \
-  VEC_BASE (*vec_)->prefix.num = size_;					  \
-}									  \
-									  \
-static inline void VEC_OP (T,A,safe_grow_cleared)			  \
-     (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)		  \
-{									  \
-  int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);			  \
-  VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);	  \
-  memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,	  \
-	  sizeof (T) * (size_ - oldsize));				  \
-}									  \
-									  \
-static inline void VEC_OP(T,A,safe_splice)				  \
-     (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL)	  \
-{									  \
-  if (src_)								  \
-    {									  \
-      VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num			  \
-				  VEC_CHECK_PASS MEM_STAT_INFO);	  \
-									  \
-      VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_			  \
-			      VEC_CHECK_PASS);				  \
-    }									  \
-}									  \
-									  \
-static inline T *VEC_OP (T,A,safe_push)					  \
-     (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL)	  \
-{									  \
-  VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);		  \
-									  \
-  return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS);  \
-}									  \
-									  \
-static inline T *VEC_OP (T,A,safe_insert)		     	  	  \
-     (VEC(T,A) **vec_, unsigned ix_, const T *obj_			  \
- 		VEC_CHECK_DECL MEM_STAT_DECL)				  \
-{									  \
-  VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);		  \
-									  \
-  return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_	  \
-				       VEC_CHECK_PASS);			  \
-}
-
-#define DEF_VEC_ALLOC_FUNC_I(T,A)					  \
-static inline VEC(T,A) *VEC_OP (T,A,alloc)      			  \
-     (int alloc_ MEM_STAT_DECL)						  \
-{									  \
-  return (VEC(T,A) *) vec_##A##_o_reserve_exact				  \
-		      (NULL, alloc_, offsetof (VEC(T,A),base.vec),	  \
-		       sizeof (T) PASS_MEM_STAT);			  \
-}
-
-#define DEF_VEC_NONALLOC_FUNCS_I(T,A)					  \
-static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
-{									  \
-  size_t len_ = vec_ ? vec_->prefix.num : 0;					  \
-  VEC (T,A) *new_vec_ = NULL;						  \
-									  \
-  if (len_)								  \
-    {									  \
-      new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact		  \
-			       (NULL, len_,				  \
-				offsetof (VEC(T,A),base.vec), sizeof (T)  \
-				PASS_MEM_STAT));			  \
-									  \
-      new_vec_->base.prefix.num = len_;					  \
-      memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);	  \
-    }									  \
-  return new_vec_;							  \
-}									  \
-									  \
-static inline void VEC_OP (T,A,free)					  \
-     (VEC(T,A) **vec_)							  \
-{									  \
-  if (*vec_)								  \
-    vec_##A##_free (*vec_);						  \
-  *vec_ = NULL;								  \
-}									  \
-									  \
-static inline int VEC_OP (T,A,reserve)	   	    			  \
-     (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)		  \
-{									  \
-  int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_		  \
-				       VEC_CHECK_PASS);			  \
-									  \
-  if (extend)								  \
-    *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_,		  \
-			   		      offsetof (VEC(T,A),base.vec),\
- 					      sizeof (T)		  \
-			   		      PASS_MEM_STAT);		  \
-									  \
-  return extend;							  \
-}									  \
-									  \
-static inline int VEC_OP (T,A,reserve_exact)   	    			  \
-     (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)		  \
-{									  \
-  int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_		  \
-				       VEC_CHECK_PASS);			  \
-									  \
-  if (extend)								  \
-    *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact			  \
-			 (*vec_, alloc_, offsetof (VEC(T,A),base.vec),	  \
-			  sizeof (T) PASS_MEM_STAT);			  \
-									  \
-  return extend;							  \
-}									  \
-									  \
-static inline void VEC_OP (T,A,safe_grow)				  \
-     (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)		  \
-{									  \
-  VEC_ASSERT (size_ >= 0						  \
-	      && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
-						 "grow", T, A);		  \
-  VEC_OP (T,A,reserve_exact) (vec_,					  \
-			      size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
-			      VEC_CHECK_PASS PASS_MEM_STAT);		  \
-  VEC_BASE (*vec_)->prefix.num = size_;					  \
-}									  \
-									  \
-static inline void VEC_OP (T,A,safe_grow_cleared)			  \
-     (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)		  \
-{									  \
-  int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);			  \
-  VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);	  \
-  memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,	  \
-	  sizeof (T) * (size_ - oldsize));				  \
-}									  \
-									  \
-static inline void VEC_OP(T,A,safe_splice)				  \
-     (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL)	  \
-{									  \
-  if (src_)								  \
-    {									  \
-      VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num			  \
-				  VEC_CHECK_PASS MEM_STAT_INFO);	  \
-									  \
-      VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_			  \
-			      VEC_CHECK_PASS);				  \
-    }									  \
-}									  \
-									  \
-static inline T *VEC_OP (T,A,safe_push)					  \
-     (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL)	  \
-{									  \
-  VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);		  \
-									  \
-  return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS);  \
-}									  \
-									  \
-static inline T *VEC_OP (T,A,safe_insert)		     	  	  \
-     (VEC(T,A) **vec_, unsigned ix_, const T obj_			  \
- 		VEC_CHECK_DECL MEM_STAT_DECL)				  \
-{									  \
-  VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);		  \
-									  \
-  return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_	  \
-				       VEC_CHECK_PASS);			  \
+template<typename T>
+static inline unsigned
+VEC_lower_bound_1 (vec_t<T> *vec_, const T *ptr_,
+		   bool (*lessthan_)(const T*, const T*) VEC_CHECK_DECL)
+{
+  unsigned int len_ = VEC_length (T, vec_);
+  unsigned int half_, middle_;
+  unsigned int first_ = 0;
+  while (len_ > 0)
+    {
+      T *middle_elem_;
+      half_ = len_ >> 1;
+      middle_ = first_;
+      middle_ += half_;
+      middle_elem_ = &VEC_index_1 (vec_, middle_ VEC_CHECK_PASS);
+      if (lessthan_ (middle_elem_, ptr_))
+	{
+	  first_ = middle_;
+	  ++first_;
+	  len_ = len_ - half_ - 1;
+	}
+      else
+	len_ = half_;
+    }
+  return first_;
 }
 
-/* We support a vector which starts out with space on the stack and
-   switches to heap space when forced to reallocate.  This works a
-   little differently.  Instead of DEF_VEC_ALLOC_P(TYPE, heap|gc), use
-   DEF_VEC_ALLOC_P_STACK(TYPE).  This uses alloca to get the initial
-   space; because alloca can not be usefully called in an inline
-   function, and because a macro can not define a macro, you must then
-   write a #define for each type:
 
-   #define VEC_{TYPE}_stack_alloc(alloc)                          \
-     VEC_stack_alloc({TYPE}, alloc)
+void *vec_heap_o_reserve_1 (void *, int, size_t, size_t, bool MEM_STAT_DECL);
+void *vec_gc_o_reserve_1 (void *, int, size_t, size_t, bool MEM_STAT_DECL);
 
-   This is really a hack and perhaps can be made better.  Note that
-   this macro will wind up evaluating the ALLOC parameter twice.
+/* Ensure there are at least RESERVE free slots in VEC_, growing
+   exponentially.  If RESERVE < 0 grow exactly, else grow
+   exponentially.  As a special case, if VEC_ is NULL, and RESERVE is
+   0, no vector will be created. */
 
-   Only the initial allocation will be made using alloca, so pass a
-   reasonable estimate that doesn't use too much stack space; don't
-   pass zero.  Don't return a VEC(TYPE,stack) vector from the function
-   which allocated it.  */
-
-extern void *vec_stack_p_reserve (void *, int MEM_STAT_DECL);
-extern void *vec_stack_p_reserve_exact (void *, int MEM_STAT_DECL);
-extern void *vec_stack_p_reserve_exact_1 (int, void *);
-extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
-extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t
-					 MEM_STAT_DECL);
-extern void vec_stack_free (void *);
-
-#ifdef GATHER_STATISTICS
-#define VEC_stack_alloc(T,alloc,name,line,function)			  \
-  (VEC_OP (T,stack,alloc1)						  \
-   (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
-#else
-#define VEC_stack_alloc(T,alloc)					  \
-  (VEC_OP (T,stack,alloc1)						  \
-   (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
-#endif
-
-#define DEF_VEC_ALLOC_P_STACK(T)					  \
-VEC_TA(T,base,stack);							  \
-DEF_VEC_ALLOC_FUNC_P_STACK(T)						  \
-DEF_VEC_NONALLOC_FUNCS_P(T,stack)					  \
-struct vec_swallow_trailing_semi
-
-#define DEF_VEC_ALLOC_FUNC_P_STACK(T)					  \
-static inline VEC(T,stack) *VEC_OP (T,stack,alloc1)			  \
-     (int alloc_, VEC(T,stack)* space)					  \
-{									  \
-  return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space);	  \
+template<typename T, enum vec_allocation_t A>
+vec_t<T> *
+vec_reserve (vec_t<T> *vec_, int reserve MEM_STAT_DECL)
+{
+  if (A == gc)
+    return (vec_t<T> *) vec_gc_o_reserve_1 (vec_, reserve,
+					    offsetof (vec_t<T>, vec),
+					    sizeof (T), false
+					    PASS_MEM_STAT);
+  else if (A == heap)
+    return (vec_t<T> *) vec_heap_o_reserve_1 (vec_, reserve,
+					      offsetof (vec_t<T>, vec),
+					      sizeof (T), false
+					      PASS_MEM_STAT);
+  else
+    return (vec_t<T> *) vec_stack_o_reserve (vec_, reserve,
+					     offsetof (vec_t<T>, vec),
+					     sizeof (T) PASS_MEM_STAT);
 }
 
-#define DEF_VEC_ALLOC_O_STACK(T)					  \
-VEC_TA(T,base,stack);							  \
-DEF_VEC_ALLOC_FUNC_O_STACK(T)						  \
-DEF_VEC_NONALLOC_FUNCS_O(T,stack)					  \
-struct vec_swallow_trailing_semi
 
-#define DEF_VEC_ALLOC_FUNC_O_STACK(T)					  \
-static inline VEC(T,stack) *VEC_OP (T,stack,alloc1)			  \
-     (int alloc_, VEC(T,stack)* space)					  \
-{									  \
-  return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space);	  \
-}
-
-#define DEF_VEC_ALLOC_I_STACK(T)					  \
-VEC_TA(T,base,stack);							  \
-DEF_VEC_ALLOC_FUNC_I_STACK(T)						  \
-DEF_VEC_NONALLOC_FUNCS_I(T,stack)					  \
-struct vec_swallow_trailing_semi
+/* Ensure there are at least RESERVE free slots in VEC_, growing
+   exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
+   a special case, if VEC_ is NULL, and RESERVE is 0, no vector will be
+   created. */
 
-#define DEF_VEC_ALLOC_FUNC_I_STACK(T)					  \
-static inline VEC(T,stack) *VEC_OP (T,stack,alloc1)			  \
-     (int alloc_, VEC(T,stack)* space)					  \
-{									  \
-  return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space);   \
+template<typename T, enum vec_allocation_t A>
+vec_t<T> *
+vec_reserve_exact (vec_t<T> *vec_, int reserve MEM_STAT_DECL)
+{
+  if (A == gc)
+    return (vec_t<T> *) vec_gc_o_reserve_1 (vec_, reserve,
+					    sizeof (struct vec_prefix),
+					    sizeof (T), true
+					    PASS_MEM_STAT);
+  else if (A == heap)
+    return (vec_t<T> *) vec_heap_o_reserve_1 (vec_, reserve,
+					      sizeof (struct vec_prefix),
+					      sizeof (T), true
+					      PASS_MEM_STAT);
+  else if (A == stack)
+    {
+      /* Only allow stack vectors when re-growing them.  The initial
+	 allocation of stack vectors must be done with VEC_alloc,
+	 because it uses alloca() for the allocation.  */
+      if (vec_ == NULL)
+	{
+	  fprintf (stderr, "Stack vectors must be initially allocated "
+		   "with VEC_stack_alloc.\n");
+	  gcc_unreachable ();
+	}
+      return (vec_t<T> *) vec_stack_o_reserve_exact (vec_, reserve,
+						     sizeof (struct vec_prefix),
+						     sizeof (T)
+						     PASS_MEM_STAT);
+    }
 }
 
 #endif /* GCC_VEC_H */