Initial checkin of GCC 4.9.0 from trunk (r208799).

Change-Id: I48a3c08bb98542aa215912a75f03c0890e497dba

1 files changed, 1727 insertions, 0 deletions

diff --git a/gcc-4.9/gcc/vec.h b/gcc-4.9/gcc/vec.h
new file mode 100644
index 000000000..587302344
--- /dev/null
+++ b/gcc-4.9/gcc/vec.h
@@ -0,0 +1,1727 @@
+/* Vector API for GNU compiler.
+   Copyright (C) 2004-2014 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.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_VEC_H
+#define GCC_VEC_H
+
+/* FIXME - When compiling some of the gen* binaries, we cannot enable GC
+   support because the headers generated by gengtype are still not
+   present.  In particular, the header file gtype-desc.h is missing,
+   so compilation may fail if we try to include ggc.h.
+
+   Since we use some of those declarations, we need to provide them
+   (even if the GC-based templates are not used).  This is not a
+   problem because the code that runs before gengtype is built will
+   never need to use GC vectors.  But it does force us to declare
+   these functions more than once.  */
+#ifdef GENERATOR_FILE
+#define VEC_GC_ENABLED	0
+#else
+#define VEC_GC_ENABLED	1
+#endif	// GENERATOR_FILE
+
+#include "statistics.h"		// For CXX_MEM_STAT_INFO.
+
+#if VEC_GC_ENABLED
+#include "ggc.h"
+#else
+# ifndef GCC_GGC_H
+  /* Even if we think that GC is not enabled, the test that sets it is
+     weak.  There are files compiled with -DGENERATOR_FILE that already
+     include ggc.h.  We only need to provide these definitions if ggc.h
+     has not been included.  Sigh.  */
+  extern void ggc_free (void *);
+  extern size_t ggc_round_alloc_size (size_t requested_size);
+  extern void *ggc_realloc_stat (void *, size_t MEM_STAT_DECL);
+#  endif  // GCC_GGC_H
+#endif	// VEC_GC_ENABLED
+
+/* Templated vector type and associated interfaces.
+
+   The interface functions are typesafe and use inline functions,
+   sometimes backed by out-of-line generic functions.  The vectors are
+   designed to interoperate with the GTY machinery.
+
+   There are both 'index' and 'iterate' accessors.  The index accessor
+   is implemented by operator[].  The iterator returns a boolean
+   iteration condition and updates the iteration variable passed by
+   reference.  Because the iterator will be inlined, the address-of
+   can be optimized away.
+
+   Each operation that increases the number of active elements is
+   available in 'quick' and 'safe' variants.  The former presumes that
+   there is sufficient allocated space for the operation to succeed
+   (it dies if there is not).  The latter will reallocate the
+   vector, if needed.  Reallocation causes an exponential increase in
+   vector size.  If you know you will be adding N elements, it would
+   be more efficient to use the reserve operation before adding the
+   elements with the 'quick' operation.  This will ensure there are at
+   least as many elements as you ask for, it will exponentially
+   increase if there are too few spare slots.  If you want reserve a
+   specific number of slots, but do not want the exponential increase
+   (for instance, you know this is the last allocation), use the
+   reserve_exact operation.  You can also create a vector of a
+   specific size from the get go.
+
+   You should prefer the push and pop operations, as they append and
+   remove from the end of the vector. If you need to remove several
+   items in one go, use the truncate operation.  The insert and remove
+   operations allow you to change elements in the middle of the
+   vector.  There are two remove operations, one which preserves the
+   element ordering 'ordered_remove', and one which does not
+   'unordered_remove'.  The latter function copies the end element
+   into the removed slot, rather than invoke a memmove operation.  The
+   'lower_bound' function will determine where to place an item in the
+   array using insert that will maintain sorted order.
+
+   Vectors are template types with three arguments: the type of the
+   elements in the vector, the allocation strategy, and the physical
+   layout to use
+
+   Four allocation strategies are supported:
+
+	- Heap: allocation is done using malloc/free.  This is the
+	  default allocation strategy.
+
+  	- GC: allocation is done using ggc_alloc/ggc_free.
+
+  	- GC atomic: same as GC with the exception that the elements
+	  themselves are assumed to be of an atomic type that does
+	  not need to be garbage collected.  This means that marking
+	  routines do not need to traverse the array marking the
+	  individual elements.  This increases the performance of
+	  GC activities.
+
+   Two physical layouts are supported:
+
+	- Embedded: The vector is structured using the trailing array
+	  idiom.  The last member of the structure is an array of size
+	  1.  When the vector is initially allocated, a single memory
+	  block is created to hold the vector's control data and the
+	  array of elements.  These vectors cannot grow without
+	  reallocation (see discussion on embeddable vectors below).
+
+	- Space efficient: The vector is structured as a pointer to an
+	  embedded vector.  This is the default layout.  It means that
+	  vectors occupy a single word of storage before initial
+	  allocation.  Vectors are allowed to grow (the internal
+	  pointer is reallocated but the main vector instance does not
+	  need to relocate).
+
+   The type, allocation and layout are specified when the vector is
+   declared.
+
+   If you need to directly manipulate a vector, then the 'address'
+   accessor will return the address of the start of the vector.  Also
+   the 'space' predicate will tell you whether there is spare capacity
+   in the vector.  You will not normally need to use these two functions.
+
+   Notes on the different layout strategies
+
+   * Embeddable vectors (vec<T, A, vl_embed>)
+   
+     These vectors are suitable to be embedded in other data
+     structures so that they can be pre-allocated in a contiguous
+     memory block.
+
+     Embeddable vectors are implemented using the trailing array
+     idiom, thus they are not resizeable without changing the address
+     of the vector object itself.  This means you cannot have
+     variables or fields of embeddable vector type -- always use a
+     pointer to a vector.  The one exception is the final field of a
+     structure, which could be a vector type.
+
+     You will have to use the embedded_size & embedded_init calls to
+     create such objects, and they will not be resizeable (so the
+     'safe' allocation variants are not available).
+
+     Properties of embeddable vectors:
+
+	  - The whole vector and control data are allocated in a single
+	    contiguous block.  It uses the trailing-vector idiom, so
+	    allocation must reserve enough space for all the elements
+	    in the vector plus its control data.
+	  - The vector cannot be re-allocated.
+	  - The vector cannot grow nor shrink.
+	  - No indirections needed for access/manipulation.
+	  - It requires 2 words of storage (prior to vector allocation).
+
+
+   * Space efficient vector (vec<T, A, vl_ptr>)
+
+     These vectors can grow dynamically and are allocated together
+     with their control data.  They are suited to be included in data
+     structures.  Prior to initial allocation, they only take a single
+     word of storage.
+
+     These vectors are implemented as a pointer to embeddable vectors.
+     The semantics allow for this pointer to be NULL to represent
+     empty vectors.  This way, empty vectors occupy minimal space in
+     the structure containing them.
+
+     Properties:
+
+	- The whole vector and control data are allocated in a single
+	  contiguous block.
+  	- The whole vector may be re-allocated.
+  	- Vector data may grow and shrink.
+  	- Access and manipulation requires a pointer test and
+	  indirection.
+  	- It requires 1 word of storage (prior to vector allocation).
+
+   An example of their use would be,
+
+   struct my_struct {
+     // A space-efficient vector of tree pointers in GC memory.
+     vec<tree, va_gc, vl_ptr> v;
+   };
+
+   struct my_struct *s;
+
+   if (s->v.length ()) { we have some contents }
+   s->v.safe_push (decl); // append some decl onto the end
+   for (ix = 0; s->v.iterate (ix, &elt); ix++)
+     { do something with elt }
+*/
+
+/* Support function for statistics.  */
+extern void dump_vec_loc_statistics (void);
+
+
+/* Control data for vectors.  This contains the number of allocated
+   and used slots inside a vector.  */
+
+struct vec_prefix
+{
+  /* FIXME - These fields should be private, but we need to cater to
+	     compilers that have stricter notions of PODness for types.  */
+
+  /* Memory allocation support routines in vec.c.  */
+  void register_overhead (size_t, const char *, int, const char *);
+  void release_overhead (void);
+  static unsigned calculate_allocation (vec_prefix *, unsigned, bool);
+  static unsigned calculate_allocation_1 (unsigned, unsigned);
+
+  /* Note that vec_prefix should be a base class for vec, but we use
+     offsetof() on vector fields of tree structures (e.g.,
+     tree_binfo::base_binfos), and offsetof only supports base types.
+
+     To compensate, we make vec_prefix a field inside vec and make
+     vec a friend class of vec_prefix so it can access its fields.  */
+  template <typename, typename, typename> friend struct vec;
+
+  /* The allocator types also need access to our internals.  */
+  friend struct va_gc;
+  friend struct va_gc_atomic;
+  friend struct va_heap;
+
+  unsigned m_alloc : 31;
+  unsigned m_using_auto_storage : 1;
+  unsigned m_num;
+};
+
+/* Calculate the number of slots to reserve a vector, making sure that
+   RESERVE slots are free.  If EXACT grow exactly, otherwise grow
+   exponentially.  PFX is the control data for the vector.  */
+
+inline unsigned
+vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve,
+				  bool exact)
+{
+  if (exact)
+    return (pfx ? pfx->m_num : 0) + reserve;
+  else if (!pfx)
+    return MAX (4, reserve);
+  return calculate_allocation_1 (pfx->m_alloc, pfx->m_num + reserve);
+}
+
+template<typename, typename, typename> struct vec;
+
+/* Valid vector layouts
+
+   vl_embed	- Embeddable vector that uses the trailing array idiom.
+   vl_ptr	- Space efficient vector that uses a pointer to an
+		  embeddable vector.  */
+struct vl_embed { };
+struct vl_ptr { };
+
+
+/* Types of supported allocations
+
+   va_heap	- Allocation uses malloc/free.
+   va_gc	- Allocation uses ggc_alloc.
+   va_gc_atomic	- Same as GC, but individual elements of the array
+		  do not need to be marked during collection.  */
+
+/* Allocator type for heap vectors.  */
+struct va_heap
+{
+  /* Heap vectors are frequently regular instances, so use the vl_ptr
+     layout for them.  */
+  typedef vl_ptr default_layout;
+
+  template<typename T>
+  static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool
+		       CXX_MEM_STAT_INFO);
+
+  template<typename T>
+  static void release (vec<T, va_heap, vl_embed> *&);
+};
+
+
+/* Allocator for heap memory.  Ensure there are at least RESERVE free
+   slots in V.  If EXACT is true, grow exactly, else grow
+   exponentially.  As a special case, if the vector had not been
+   allocated and and RESERVE is 0, no vector will be created.  */
+
+template<typename T>
+inline void
+va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact
+		  MEM_STAT_DECL)
+{
+  unsigned alloc
+    = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
+  gcc_checking_assert (alloc);
+
+  if (GATHER_STATISTICS && v)
+    v->m_vecpfx.release_overhead ();
+
+  size_t size = vec<T, va_heap, vl_embed>::embedded_size (alloc);
+  unsigned nelem = v ? v->length () : 0;
+  v = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size));
+  v->embedded_init (alloc, nelem);
+
+  if (GATHER_STATISTICS)
+    v->m_vecpfx.register_overhead (size FINAL_PASS_MEM_STAT);
+}
+
+
+/* Free the heap space allocated for vector V.  */
+
+template<typename T>
+void
+va_heap::release (vec<T, va_heap, vl_embed> *&v)
+{
+  if (v == NULL)
+    return;
+
+  if (GATHER_STATISTICS)
+    v->m_vecpfx.release_overhead ();
+  ::free (v);
+  v = NULL;
+}
+
+
+/* Allocator type for GC vectors.  Notice that we need the structure
+   declaration even if GC is not enabled.  */
+
+struct va_gc
+{
+  /* Use vl_embed as the default layout for GC vectors.  Due to GTY
+     limitations, GC vectors must always be pointers, so it is more
+     efficient to use a pointer to the vl_embed layout, rather than
+     using a pointer to a pointer as would be the case with vl_ptr.  */
+  typedef vl_embed default_layout;
+
+  template<typename T, typename A>
+  static void reserve (vec<T, A, vl_embed> *&, unsigned, bool
+		       CXX_MEM_STAT_INFO);
+
+  template<typename T, typename A>
+  static void release (vec<T, A, vl_embed> *&v);
+};
+
+
+/* Free GC memory used by V and reset V to NULL.  */
+
+template<typename T, typename A>
+inline void
+va_gc::release (vec<T, A, vl_embed> *&v)
+{
+  if (v)
+    ::ggc_free (v);
+  v = NULL;
+}
+
+
+/* Allocator for GC memory.  Ensure there are at least RESERVE free
+   slots in V.  If EXACT is true, grow exactly, else grow
+   exponentially.  As a special case, if the vector had not been
+   allocated and and RESERVE is 0, no vector will be created.  */
+
+template<typename T, typename A>
+void
+va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
+		MEM_STAT_DECL)
+{
+  unsigned alloc
+    = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
+  if (!alloc)
+    {
+      ::ggc_free (v);
+      v = NULL;
+      return;
+    }
+
+  /* Calculate the amount of space we want.  */
+  size_t size = vec<T, A, vl_embed>::embedded_size (alloc);
+
+  /* Ask the allocator how much space it will really give us.  */
+  size = ::ggc_round_alloc_size (size);
+
+  /* Adjust the number of slots accordingly.  */
+  size_t vec_offset = sizeof (vec_prefix);
+  size_t elt_size = sizeof (T);
+  alloc = (size - vec_offset) / elt_size;
+
+  /* And finally, recalculate the amount of space we ask for.  */
+  size = vec_offset + alloc * elt_size;
+
+  unsigned nelem = v ? v->length () : 0;
+  v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc_stat (v, size
+							       PASS_MEM_STAT));
+  v->embedded_init (alloc, nelem);
+}
+
+
+/* Allocator type for GC vectors.  This is for vectors of types
+   atomics w.r.t. collection, so allocation and deallocation is
+   completely inherited from va_gc.  */
+struct va_gc_atomic : va_gc
+{
+};
+
+
+/* Generic vector template.  Default values for A and L indicate the
+   most commonly used strategies.
+
+   FIXME - Ideally, they would all be vl_ptr to encourage using regular
+           instances for vectors, but the existing GTY machinery is limited
+	   in that it can only deal with GC objects that are pointers
+	   themselves.
+
+	   This means that vector operations that need to deal with
+	   potentially NULL pointers, must be provided as free
+	   functions (see the vec_safe_* functions above).  */
+template<typename T,
+         typename A = va_heap,
+         typename L = typename A::default_layout>
+struct GTY((user)) vec
+{
+};
+
+/* Type to provide NULL values for vec<T, A, L>.  This is used to
+   provide nil initializers for vec instances.  Since vec must be
+   a POD, we cannot have proper ctor/dtor for it.  To initialize
+   a vec instance, you can assign it the value vNULL.  */
+struct vnull
+{
+  template <typename T, typename A, typename L>
+  operator vec<T, A, L> () { return vec<T, A, L>(); }
+};
+extern vnull vNULL;
+
+
+/* Embeddable vector.  These vectors are suitable to be embedded
+   in other data structures so that they can be pre-allocated in a
+   contiguous memory block.
+
+   Embeddable vectors are implemented using the trailing array idiom,
+   thus they are not resizeable without changing the address of the
+   vector object itself.  This means you cannot have variables or
+   fields of embeddable vector type -- always use a pointer to a
+   vector.  The one exception is the final field of a structure, which
+   could be a vector type.
+
+   You will have to use the embedded_size & embedded_init calls to
+   create such objects, and they will not be resizeable (so the 'safe'
+   allocation variants are not available).
+
+   Properties:
+
+	- The whole vector and control data are allocated in a single
+	  contiguous block.  It uses the trailing-vector idiom, so
+	  allocation must reserve enough space for all the elements
+  	  in the vector plus its control data.
+  	- The vector cannot be re-allocated.
+  	- The vector cannot grow nor shrink.
+  	- No indirections needed for access/manipulation.
+  	- It requires 2 words of storage (prior to vector allocation).  */
+
+template<typename T, typename A>
+struct GTY((user)) vec<T, A, vl_embed>
+{
+public:
+  unsigned allocated (void) const { return m_vecpfx.m_alloc; }
+  unsigned length (void) const { return m_vecpfx.m_num; }
+  bool is_empty (void) const { return m_vecpfx.m_num == 0; }
+  T *address (void) { return m_vecdata; }
+  const T *address (void) const { return m_vecdata; }
+  const T &operator[] (unsigned) const;
+  T &operator[] (unsigned);
+  T &last (void);
+  bool space (unsigned) const;
+  bool iterate (unsigned, T *) const;
+  bool iterate (unsigned, T **) const;
+  vec *copy (ALONE_CXX_MEM_STAT_INFO) const;
+  void splice (vec &);
+  void splice (vec *src);
+  T *quick_push (const T &);
+  T &pop (void);
+  void truncate (unsigned);
+  void quick_insert (unsigned, const T &);
+  void ordered_remove (unsigned);
+  void unordered_remove (unsigned);
+  void block_remove (unsigned, unsigned);
+  void qsort (int (*) (const void *, const void *));
+  T *bsearch (const void *key, int (*compar)(const void *, const void *));
+  unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
+  static size_t embedded_size (unsigned);
+  void embedded_init (unsigned, unsigned = 0, unsigned = 0);
+  void quick_grow (unsigned len);
+  void quick_grow_cleared (unsigned len);
+
+  /* vec class can access our internal data and functions.  */
+  template <typename, typename, typename> friend struct vec;
+
+  /* The allocator types also need access to our internals.  */
+  friend struct va_gc;
+  friend struct va_gc_atomic;
+  friend struct va_heap;
+
+  /* FIXME - These fields should be private, but we need to cater to
+	     compilers that have stricter notions of PODness for types.  */
+  vec_prefix m_vecpfx;
+  T m_vecdata[1];
+};
+
+
+/* Convenience wrapper functions to use when dealing with pointers to
+   embedded vectors.  Some functionality for these vectors must be
+   provided via free functions for these reasons:
+
+	1- The pointer may be NULL (e.g., before initial allocation).
+
+  	2- When the vector needs to grow, it must be reallocated, so
+  	   the pointer will change its value.
+
+   Because of limitations with the current GC machinery, all vectors
+   in GC memory *must* be pointers.  */
+
+
+/* If V contains no room for NELEMS elements, return false. Otherwise,
+   return true.  */
+template<typename T, typename A>
+inline bool
+vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems)
+{
+  return v ? v->space (nelems) : nelems == 0;
+}
+
+
+/* If V is NULL, return 0.  Otherwise, return V->length().  */
+template<typename T, typename A>
+inline unsigned
+vec_safe_length (const vec<T, A, vl_embed> *v)
+{
+  return v ? v->length () : 0;
+}
+
+
+/* If V is NULL, return NULL.  Otherwise, return V->address().  */
+template<typename T, typename A>
+inline T *
+vec_safe_address (vec<T, A, vl_embed> *v)
+{
+  return v ? v->address () : NULL;
+}
+
+
+/* If V is NULL, return true.  Otherwise, return V->is_empty().  */
+template<typename T, typename A>
+inline bool
+vec_safe_is_empty (vec<T, A, vl_embed> *v)
+{
+  return v ? v->is_empty () : true;
+}
+
+
+/* If V does not have space for NELEMS elements, call
+   V->reserve(NELEMS, EXACT).  */
+template<typename T, typename A>
+inline bool
+vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false
+		  CXX_MEM_STAT_INFO)
+{
+  bool extend = nelems ? !vec_safe_space (v, nelems) : false;
+  if (extend)
+    A::reserve (v, nelems, exact PASS_MEM_STAT);
+  return extend;
+}
+
+template<typename T, typename A>
+inline bool
+vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems
+			CXX_MEM_STAT_INFO)
+{
+  return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
+}
+
+
+/* Allocate GC memory for V with space for NELEMS slots.  If NELEMS
+   is 0, V is initialized to NULL.  */
+
+template<typename T, typename A>
+inline void
+vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO)
+{
+  v = NULL;
+  vec_safe_reserve (v, nelems, false PASS_MEM_STAT);
+}
+
+
+/* Free the GC memory allocated by vector V and set it to NULL.  */
+
+template<typename T, typename A>
+inline void
+vec_free (vec<T, A, vl_embed> *&v)
+{
+  A::release (v);
+}
+
+
+/* Grow V to length LEN.  Allocate it, if necessary.  */
+template<typename T, typename A>
+inline void
+vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO)
+{
+  unsigned oldlen = vec_safe_length (v);
+  gcc_checking_assert (len >= oldlen);
+  vec_safe_reserve_exact (v, len - oldlen PASS_MEM_STAT);
+  v->quick_grow (len);
+}
+
+
+/* If V is NULL, allocate it.  Call V->safe_grow_cleared(LEN).  */
+template<typename T, typename A>
+inline void
+vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO)
+{
+  unsigned oldlen = vec_safe_length (v);
+  vec_safe_grow (v, len PASS_MEM_STAT);
+  memset (&(v->address ()[oldlen]), 0, sizeof (T) * (len - oldlen));
+}
+
+
+/* If V is NULL return false, otherwise return V->iterate(IX, PTR).  */
+template<typename T, typename A>
+inline bool
+vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr)
+{
+  if (v)
+    return v->iterate (ix, ptr);
+  else
+    {
+      *ptr = 0;
+      return false;
+    }
+}
+
+template<typename T, typename A>
+inline bool
+vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr)
+{
+  if (v)
+    return v->iterate (ix, ptr);
+  else
+    {
+      *ptr = 0;
+      return false;
+    }
+}
+
+
+/* If V has no room for one more element, reallocate it.  Then call
+   V->quick_push(OBJ).  */
+template<typename T, typename A>
+inline T *
+vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO)
+{
+  vec_safe_reserve (v, 1, false PASS_MEM_STAT);
+  return v->quick_push (obj);
+}
+
+
+/* if V has no room for one more element, reallocate it.  Then call
+   V->quick_insert(IX, OBJ).  */
+template<typename T, typename A>
+inline void
+vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
+		 CXX_MEM_STAT_INFO)
+{
+  vec_safe_reserve (v, 1, false PASS_MEM_STAT);
+  v->quick_insert (ix, obj);
+}
+
+
+/* If V is NULL, do nothing.  Otherwise, call V->truncate(SIZE).  */
+template<typename T, typename A>
+inline void
+vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
+{
+  if (v)
+    v->truncate (size);
+}
+
+
+/* If SRC is not NULL, return a pointer to a copy of it.  */
+template<typename T, typename A>
+inline vec<T, A, vl_embed> *
+vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO)
+{
+  return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL;
+}
+
+/* Copy the elements from SRC to the end of DST as if by memcpy.
+   Reallocate DST, if necessary.  */
+template<typename T, typename A>
+inline void
+vec_safe_splice (vec<T, A, vl_embed> *&dst, vec<T, A, vl_embed> *src
+		 CXX_MEM_STAT_INFO)
+{
+  unsigned src_len = vec_safe_length (src);
+  if (src_len)
+    {
+      vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len
+			      PASS_MEM_STAT);
+      dst->splice (*src);
+    }
+}
+
+
+/* Index into vector.  Return the IX'th element.  IX must be in the
+   domain of the vector.  */
+
+template<typename T, typename A>
+inline const T &
+vec<T, A, vl_embed>::operator[] (unsigned ix) const
+{
+  gcc_checking_assert (ix < m_vecpfx.m_num);
+  return m_vecdata[ix];
+}
+
+template<typename T, typename A>
+inline T &
+vec<T, A, vl_embed>::operator[] (unsigned ix)
+{
+  gcc_checking_assert (ix < m_vecpfx.m_num);
+  return m_vecdata[ix];
+}
+
+
+/* Get the final element of the vector, which must not be empty.  */
+
+template<typename T, typename A>
+inline T &
+vec<T, A, vl_embed>::last (void)
+{
+  gcc_checking_assert (m_vecpfx.m_num > 0);
+  return (*this)[m_vecpfx.m_num - 1];
+}
+
+
+/* If this vector has space for NELEMS additional entries, return
+   true.  You usually only need to use this if you are doing your
+   own vector reallocation, for instance on an embedded vector.  This
+   returns true in exactly the same circumstances that vec::reserve
+   will.  */
+
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_embed>::space (unsigned nelems) const
+{
+  return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems;
+}
+
+
+/* Return iteration condition and update PTR to point to the IX'th
+   element of this vector.  Use this to iterate over the elements of a
+   vector as follows,
+
+     for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++)
+       continue;  */
+
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
+{
+  if (ix < m_vecpfx.m_num)
+    {
+      *ptr = m_vecdata[ix];
+      return true;
+    }
+  else
+    {
+      *ptr = 0;
+      return false;
+    }
+}
+
+
+/* Return iteration condition and update *PTR to point to the
+   IX'th element of this vector.  Use this to iterate over the
+   elements of a vector as follows,
+
+     for (ix = 0; v->iterate (ix, &ptr); ix++)
+       continue;
+
+   This variant is for vectors of objects.  */
+
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
+{
+  if (ix < m_vecpfx.m_num)
+    {
+      *ptr = CONST_CAST (T *, &m_vecdata[ix]);
+      return true;
+    }
+  else
+    {
+      *ptr = 0;
+      return false;
+    }
+}
+
+
+/* Return a pointer to a copy of this vector.  */
+
+template<typename T, typename A>
+inline vec<T, A, vl_embed> *
+vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
+{
+  vec<T, A, vl_embed> *new_vec = NULL;
+  unsigned len = length ();
+  if (len)
+    {
+      vec_alloc (new_vec, len PASS_MEM_STAT);
+      new_vec->embedded_init (len, len);
+      memcpy (new_vec->address (), m_vecdata, sizeof (T) * len);
+    }
+  return new_vec;
+}
+
+
+/* Copy the elements from SRC to the end of this vector as if by memcpy.
+   The vector must have sufficient headroom available.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::splice (vec<T, A, vl_embed> &src)
+{
+  unsigned len = src.length ();
+  if (len)
+    {
+      gcc_checking_assert (space (len));
+      memcpy (address () + length (), src.address (), len * sizeof (T));
+      m_vecpfx.m_num += len;
+    }
+}
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::splice (vec<T, A, vl_embed> *src)
+{
+  if (src)
+    splice (*src);
+}
+
+
+/* Push OBJ (a new element) onto the end of the vector.  There must be
+   sufficient space in the vector.  Return a pointer to the slot
+   where OBJ was inserted.  */
+
+template<typename T, typename A>
+inline T *
+vec<T, A, vl_embed>::quick_push (const T &obj)
+{
+  gcc_checking_assert (space (1));
+  T *slot = &m_vecdata[m_vecpfx.m_num++];
+  *slot = obj;
+  return slot;
+}
+
+
+/* Pop and return the last element off the end of the vector.  */
+
+template<typename T, typename A>
+inline T &
+vec<T, A, vl_embed>::pop (void)
+{
+  gcc_checking_assert (length () > 0);
+  return m_vecdata[--m_vecpfx.m_num];
+}
+
+
+/* Set the length of the vector to SIZE.  The new length must be less
+   than or equal to the current length.  This is an O(1) operation.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::truncate (unsigned size)
+{
+  gcc_checking_assert (length () >= size);
+  m_vecpfx.m_num = size;
+}
+
+
+/* Insert an element, OBJ, at the IXth position of this vector.  There
+   must be sufficient space.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
+{
+  gcc_checking_assert (length () < allocated ());
+  gcc_checking_assert (ix <= length ());
+  T *slot = &m_vecdata[ix];
+  memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T));
+  *slot = obj;
+}
+
+
+/* Remove an element from the IXth position of this vector.  Ordering of
+   remaining elements is preserved.  This is an O(N) operation due to
+   memmove.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::ordered_remove (unsigned ix)
+{
+  gcc_checking_assert (ix < length ());
+  T *slot = &m_vecdata[ix];
+  memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T));
+}
+
+
+/* Remove an element from the IXth position of this vector.  Ordering of
+   remaining elements is destroyed.  This is an O(1) operation.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::unordered_remove (unsigned ix)
+{
+  gcc_checking_assert (ix < length ());
+  m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num];
+}
+
+
+/* Remove LEN elements starting at the IXth.  Ordering is retained.
+   This is an O(N) operation due to memmove.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
+{
+  gcc_checking_assert (ix + len <= length ());
+  T *slot = &m_vecdata[ix];
+  m_vecpfx.m_num -= len;
+  memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T));
+}
+
+
+/* Sort the contents of this vector with qsort.  CMP is the comparison
+   function to pass to qsort.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
+{
+  if (length () > 1)
+    ::qsort (address (), length (), sizeof (T), cmp);
+}
+
+
+/* Search the contents of the sorted vector with a binary search.
+   CMP is the comparison function to pass to bsearch.  */
+
+template<typename T, typename A>
+inline T *
+vec<T, A, vl_embed>::bsearch (const void *key,
+			      int (*compar) (const void *, const void *))
+{
+  const void *base = this->address ();
+  size_t nmemb = this->length ();
+  size_t size = sizeof (T);
+  /* The following is a copy of glibc stdlib-bsearch.h.  */
+  size_t l, u, idx;
+  const void *p;
+  int comparison;
+
+  l = 0;
+  u = nmemb;
+  while (l < u)
+    {
+      idx = (l + u) / 2;
+      p = (const void *) (((const char *) base) + (idx * size));
+      comparison = (*compar) (key, p);
+      if (comparison < 0)
+	u = idx;
+      else if (comparison > 0)
+	l = idx + 1;
+      else
+	return (T *)const_cast<void *>(p);
+    }
+
+  return NULL;
+}
+
+
+/* Find and return the first position in which OBJ could be inserted
+   without changing the ordering of this vector.  LESSTHAN is a
+   function that returns true if the first argument is strictly less
+   than the second.  */
+
+template<typename T, typename A>
+unsigned
+vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
+  const
+{
+  unsigned int len = length ();
+  unsigned int half, middle;
+  unsigned int first = 0;
+  while (len > 0)
+    {
+      half = len / 2;
+      middle = first;
+      middle += half;
+      T middle_elem = (*this)[middle];
+      if (lessthan (middle_elem, obj))
+	{
+	  first = middle;
+	  ++first;
+	  len = len - half - 1;
+	}
+      else
+	len = half;
+    }
+  return first;
+}
+
+
+/* Return the number of bytes needed to embed an instance of an
+   embeddable vec inside another data structure.
+
+   Use these methods to determine the required size and initialization
+   of a vector V of type T embedded within another structure (as the
+   final member):
+
+   size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
+   void v->embedded_init (unsigned alloc, unsigned num);
+
+   These allow the caller to perform the memory allocation.  */
+
+template<typename T, typename A>
+inline size_t
+vec<T, A, vl_embed>::embedded_size (unsigned alloc)
+{
+  typedef vec<T, A, vl_embed> vec_embedded;
+  return offsetof (vec_embedded, m_vecdata) + alloc * sizeof (T);
+}
+
+
+/* Initialize the vector to contain room for ALLOC elements and
+   NUM active elements.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
+{
+  m_vecpfx.m_alloc = alloc;
+  m_vecpfx.m_using_auto_storage = aut;
+  m_vecpfx.m_num = num;
+}
+
+
+/* Grow the vector to a specific length.  LEN must be as long or longer than
+   the current length.  The new elements are uninitialized.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::quick_grow (unsigned len)
+{
+  gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
+  m_vecpfx.m_num = len;
+}
+
+
+/* Grow the vector to a specific length.  LEN must be as long or longer than
+   the current length.  The new elements are initialized to zero.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
+{
+  unsigned oldlen = length ();
+  quick_grow (len);
+  memset (&(address ()[oldlen]), 0, sizeof (T) * (len - oldlen));
+}
+
+
+/* Garbage collection support for vec<T, A, vl_embed>.  */
+
+template<typename T>
+void
+gt_ggc_mx (vec<T, va_gc> *v)
+{
+  extern void gt_ggc_mx (T &);
+  for (unsigned i = 0; i < v->length (); i++)
+    gt_ggc_mx ((*v)[i]);
+}
+
+template<typename T>
+void
+gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
+{
+  /* Nothing to do.  Vectors of atomic types wrt GC do not need to
+     be traversed.  */
+}
+
+
+/* PCH support for vec<T, A, vl_embed>.  */
+
+template<typename T, typename A>
+void
+gt_pch_nx (vec<T, A, vl_embed> *v)
+{
+  extern void gt_pch_nx (T &);
+  for (unsigned i = 0; i < v->length (); i++)
+    gt_pch_nx ((*v)[i]);
+}
+
+template<typename T, typename A>
+void
+gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
+{
+  for (unsigned i = 0; i < v->length (); i++)
+    op (&((*v)[i]), cookie);
+}
+
+template<typename T, typename A>
+void
+gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
+{
+  extern void gt_pch_nx (T *, gt_pointer_operator, void *);
+  for (unsigned i = 0; i < v->length (); i++)
+    gt_pch_nx (&((*v)[i]), op, cookie);
+}
+
+
+/* Space efficient vector.  These vectors can grow dynamically and are
+   allocated together with their control data.  They are suited to be
+   included in data structures.  Prior to initial allocation, they
+   only take a single word of storage.
+
+   These vectors are implemented as a pointer to an embeddable vector.
+   The semantics allow for this pointer to be NULL to represent empty
+   vectors.  This way, empty vectors occupy minimal space in the
+   structure containing them.
+
+   Properties:
+
+	- The whole vector and control data are allocated in a single
+	  contiguous block.
+  	- The whole vector may be re-allocated.
+  	- Vector data may grow and shrink.
+  	- Access and manipulation requires a pointer test and
+	  indirection.
+	- It requires 1 word of storage (prior to vector allocation).
+
+
+   Limitations:
+
+   These vectors must be PODs because they are stored in unions.
+   (http://en.wikipedia.org/wiki/Plain_old_data_structures).
+   As long as we use C++03, we cannot have constructors nor
+   destructors in classes that are stored in unions.  */
+
+template<typename T>
+struct vec<T, va_heap, vl_ptr>
+{
+public:
+  /* Memory allocation and deallocation for the embedded vector.
+     Needed because we cannot have proper ctors/dtors defined.  */
+  void create (unsigned nelems CXX_MEM_STAT_INFO);
+  void release (void);
+
+  /* Vector operations.  */
+  bool exists (void) const
+  { return m_vec != NULL; }
+
+  bool is_empty (void) const
+  { return m_vec ? m_vec->is_empty () : true; }
+
+  unsigned length (void) const
+  { return m_vec ? m_vec->length () : 0; }
+
+  T *address (void)
+  { return m_vec ? m_vec->m_vecdata : NULL; }
+
+  const T *address (void) const
+  { return m_vec ? m_vec->m_vecdata : NULL; }
+
+  const T &operator[] (unsigned ix) const
+  { return (*m_vec)[ix]; }
+
+  bool operator!=(const vec &other) const
+  { return !(*this == other); }
+
+  bool operator==(const vec &other) const
+  { return address () == other.address (); }
+
+  T &operator[] (unsigned ix)
+  { return (*m_vec)[ix]; }
+
+  T &last (void)
+  { return m_vec->last (); }
+
+  bool space (int nelems) const
+  { return m_vec ? m_vec->space (nelems) : nelems == 0; }
+
+  bool iterate (unsigned ix, T *p) const;
+  bool iterate (unsigned ix, T **p) const;
+  vec copy (ALONE_CXX_MEM_STAT_INFO) const;
+  bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
+  bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
+  void splice (vec &);
+  void safe_splice (vec & CXX_MEM_STAT_INFO);
+  T *quick_push (const T &);
+  T *safe_push (const T &CXX_MEM_STAT_INFO);
+  T &pop (void);
+  void truncate (unsigned);
+  void safe_grow (unsigned CXX_MEM_STAT_INFO);
+  void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO);
+  void quick_grow (unsigned);
+  void quick_grow_cleared (unsigned);
+  void quick_insert (unsigned, const T &);
+  void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
+  void ordered_remove (unsigned);
+  void unordered_remove (unsigned);
+  void block_remove (unsigned, unsigned);
+  void qsort (int (*) (const void *, const void *));
+  T *bsearch (const void *key, int (*compar)(const void *, const void *));
+  unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
+
+  bool using_auto_storage () const;
+
+  /* FIXME - This field should be private, but we need to cater to
+	     compilers that have stricter notions of PODness for types.  */
+  vec<T, va_heap, vl_embed> *m_vec;
+};
+
+
+/* auto_vec is a subclass of vec that automatically manages creating and
+   releasing the internal vector. If N is non zero then it has N elements of
+   internal storage.  The default is no internal storage, and you probably only
+   want to ask for internal storage for vectors on the stack because if the
+   size of the vector is larger than the internal storage that space is wasted.
+   */
+template<typename T, size_t N = 0>
+class auto_vec : public vec<T, va_heap>
+{
+public:
+  auto_vec ()
+  {
+    m_auto.embedded_init (MAX (N, 2), 0, 1);
+    this->m_vec = &m_auto;
+  }
+
+  ~auto_vec ()
+  {
+    this->release ();
+  }
+
+private:
+  vec<T, va_heap, vl_embed> m_auto;
+  T m_data[MAX (N - 1, 1)];
+};
+
+/* auto_vec is a sub class of vec whose storage is released when it is
+  destroyed. */
+template<typename T>
+class auto_vec<T, 0> : public vec<T, va_heap>
+{
+public:
+  auto_vec () { this->m_vec = NULL; }
+  auto_vec (size_t n) { this->create (n); }
+  ~auto_vec () { this->release (); }
+};
+
+
+/* Allocate heap memory for pointer V and create the internal vector
+   with space for NELEMS elements.  If NELEMS is 0, the internal
+   vector is initialized to empty.  */
+
+template<typename T>
+inline void
+vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO)
+{
+  v = new vec<T>;
+  v->create (nelems PASS_MEM_STAT);
+}
+
+
+/* Conditionally allocate heap memory for VEC and its internal vector.  */
+
+template<typename T>
+inline void
+vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO)
+{
+  if (!vec)
+    vec_alloc (vec, nelems PASS_MEM_STAT);
+}
+
+
+/* Free the heap memory allocated by vector V and set it to NULL.  */
+
+template<typename T>
+inline void
+vec_free (vec<T> *&v)
+{
+  if (v == NULL)
+    return;
+
+  v->release ();
+  delete v;
+  v = NULL;
+}
+
+
+/* Return iteration condition and update PTR to point to the IX'th
+   element of this vector.  Use this to iterate over the elements of a
+   vector as follows,
+
+     for (ix = 0; v.iterate (ix, &ptr); ix++)
+       continue;  */
+
+template<typename T>
+inline bool
+vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const
+{
+  if (m_vec)
+    return m_vec->iterate (ix, ptr);
+  else
+    {
+      *ptr = 0;
+      return false;
+    }
+}
+
+
+/* Return iteration condition and update *PTR to point to the
+   IX'th element of this vector.  Use this to iterate over the
+   elements of a vector as follows,
+
+     for (ix = 0; v->iterate (ix, &ptr); ix++)
+       continue;
+
+   This variant is for vectors of objects.  */
+
+template<typename T>
+inline bool
+vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const
+{
+  if (m_vec)
+    return m_vec->iterate (ix, ptr);
+  else
+    {
+      *ptr = 0;
+      return false;
+    }
+}
+
+
+/* Convenience macro for forward iteration.  */
+#define FOR_EACH_VEC_ELT(V, I, P)			\
+  for (I = 0; (V).iterate ((I), &(P)); ++(I))
+
+#define FOR_EACH_VEC_SAFE_ELT(V, I, P)			\
+  for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
+
+/* Likewise, but start from FROM rather than 0.  */
+#define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM)		\
+  for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
+
+/* Convenience macro for reverse iteration.  */
+#define FOR_EACH_VEC_ELT_REVERSE(V, I, P)		\
+  for (I = (V).length () - 1;				\
+       (V).iterate ((I), &(P));				\
+       (I)--)
+
+#define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P)		\
+  for (I = vec_safe_length (V) - 1;			\
+       vec_safe_iterate ((V), (I), &(P));	\
+       (I)--)
+
+
+/* Return a copy of this vector.  */
+
+template<typename T>
+inline vec<T, va_heap, vl_ptr>
+vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
+{
+  vec<T, va_heap, vl_ptr> new_vec = vNULL;
+  if (length ())
+    new_vec.m_vec = m_vec->copy ();
+  return new_vec;
+}
+
+
+/* Ensure that the vector has at least RESERVE slots available (if
+   EXACT is false), or exactly RESERVE slots available (if EXACT is
+   true).
+
+   This may create additional headroom if EXACT is false.
+
+   Note that this can cause the embedded vector to be reallocated.
+   Returns true iff reallocation actually occurred.  */
+
+template<typename T>
+inline bool
+vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
+{
+  if (space (nelems))
+    return false;
+
+  /* For now play a game with va_heap::reserve to hide our auto storage if any,
+     this is necessary because it doesn't have enough information to know the
+     embedded vector is in auto storage, and so should not be freed.  */
+  vec<T, va_heap, vl_embed> *oldvec = m_vec;
+  unsigned int oldsize = 0;
+  bool handle_auto_vec = m_vec && using_auto_storage ();
+  if (handle_auto_vec)
+    {
+      m_vec = NULL;
+      oldsize = oldvec->length ();
+      nelems += oldsize;
+    }
+
+  va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT);
+  if (handle_auto_vec)
+    {
+      memcpy (m_vec->address (), oldvec->address (), sizeof (T) * oldsize);
+      m_vec->m_vecpfx.m_num = oldsize;
+    }
+
+  return true;
+}
+
+
+/* Ensure that this vector has exactly NELEMS slots available.  This
+   will not create additional headroom.  Note this can cause the
+   embedded vector to be reallocated.  Returns true iff reallocation
+   actually occurred.  */
+
+template<typename T>
+inline bool
+vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
+{
+  return reserve (nelems, true PASS_MEM_STAT);
+}
+
+
+/* Create the internal vector and reserve NELEMS for it.  This is
+   exactly like vec::reserve, but the internal vector is
+   unconditionally allocated from scratch.  The old one, if it
+   existed, is lost.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
+{
+  m_vec = NULL;
+  if (nelems > 0)
+    reserve_exact (nelems PASS_MEM_STAT);
+}
+
+
+/* Free the memory occupied by the embedded vector.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::release (void)
+{
+  if (!m_vec)
+    return;
+
+  if (using_auto_storage ())
+    {
+      m_vec->m_vecpfx.m_num = 0;
+      return;
+    }
+
+  va_heap::release (m_vec);
+}
+
+/* Copy the elements from SRC to the end of this vector as if by memcpy.
+   SRC and this vector must be allocated with the same memory
+   allocation mechanism. This vector is assumed to have sufficient
+   headroom available.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::splice (vec<T, va_heap, vl_ptr> &src)
+{
+  if (src.m_vec)
+    m_vec->splice (*(src.m_vec));
+}
+
+
+/* Copy the elements in SRC to the end of this vector as if by memcpy.
+   SRC and this vector must be allocated with the same mechanism.
+   If there is not enough headroom in this vector, it will be reallocated
+   as needed.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::safe_splice (vec<T, va_heap, vl_ptr> &src
+				      MEM_STAT_DECL)
+{
+  if (src.length ())
+    {
+      reserve_exact (src.length ());
+      splice (src);
+    }
+}
+
+
+/* Push OBJ (a new element) onto the end of the vector.  There must be
+   sufficient space in the vector.  Return a pointer to the slot
+   where OBJ was inserted.  */
+
+template<typename T>
+inline T *
+vec<T, va_heap, vl_ptr>::quick_push (const T &obj)
+{
+  return m_vec->quick_push (obj);
+}
+
+
+/* Push a new element OBJ onto the end of this vector.  Reallocates
+   the embedded vector, if needed.  Return a pointer to the slot where
+   OBJ was inserted.  */
+
+template<typename T>
+inline T *
+vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
+{
+  reserve (1, false PASS_MEM_STAT);
+  return quick_push (obj);
+}
+
+
+/* Pop and return the last element off the end of the vector.  */
+
+template<typename T>
+inline T &
+vec<T, va_heap, vl_ptr>::pop (void)
+{
+  return m_vec->pop ();
+}
+
+
+/* Set the length of the vector to LEN.  The new length must be less
+   than or equal to the current length.  This is an O(1) operation.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::truncate (unsigned size)
+{
+  if (m_vec)
+    m_vec->truncate (size);
+  else
+    gcc_checking_assert (size == 0);
+}
+
+
+/* Grow the vector to a specific length.  LEN must be as long or
+   longer than the current length.  The new elements are
+   uninitialized.  Reallocate the internal vector, if needed.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL)
+{
+  unsigned oldlen = length ();
+  gcc_checking_assert (oldlen <= len);
+  reserve_exact (len - oldlen PASS_MEM_STAT);
+  m_vec->quick_grow (len);
+}
+
+
+/* Grow the embedded vector to a specific length.  LEN must be as
+   long or longer than the current length.  The new elements are
+   initialized to zero.  Reallocate the internal vector, if needed.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL)
+{
+  unsigned oldlen = length ();
+  safe_grow (len PASS_MEM_STAT);
+  memset (&(address ()[oldlen]), 0, sizeof (T) * (len - oldlen));
+}
+
+
+/* Same as vec::safe_grow but without reallocation of the internal vector.
+   If the vector cannot be extended, a runtime assertion will be triggered.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::quick_grow (unsigned len)
+{
+  gcc_checking_assert (m_vec);
+  m_vec->quick_grow (len);
+}
+
+
+/* Same as vec::quick_grow_cleared but without reallocation of the
+   internal vector. If the vector cannot be extended, a runtime
+   assertion will be triggered.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len)
+{
+  gcc_checking_assert (m_vec);
+  m_vec->quick_grow_cleared (len);
+}
+
+
+/* Insert an element, OBJ, at the IXth position of this vector.  There
+   must be sufficient space.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj)
+{
+  m_vec->quick_insert (ix, obj);
+}
+
+
+/* Insert an element, OBJ, at the IXth position of the vector.
+   Reallocate the embedded vector, if necessary.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
+{
+  reserve (1, false PASS_MEM_STAT);
+  quick_insert (ix, obj);
+}
+
+
+/* Remove an element from the IXth position of this vector.  Ordering of
+   remaining elements is preserved.  This is an O(N) operation due to
+   a memmove.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
+{
+  m_vec->ordered_remove (ix);
+}
+
+
+/* Remove an element from the IXth position of this vector.  Ordering
+   of remaining elements is destroyed.  This is an O(1) operation.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix)
+{
+  m_vec->unordered_remove (ix);
+}
+
+
+/* Remove LEN elements starting at the IXth.  Ordering is retained.
+   This is an O(N) operation due to memmove.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len)
+{
+  m_vec->block_remove (ix, len);
+}
+
+
+/* Sort the contents of this vector with qsort.  CMP is the comparison
+   function to pass to qsort.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
+{
+  if (m_vec)
+    m_vec->qsort (cmp);
+}
+
+
+/* Search the contents of the sorted vector with a binary search.
+   CMP is the comparison function to pass to bsearch.  */
+
+template<typename T>
+inline T *
+vec<T, va_heap, vl_ptr>::bsearch (const void *key,
+				  int (*cmp) (const void *, const void *))
+{
+  if (m_vec)
+    return m_vec->bsearch (key, cmp);
+  return NULL;
+}
+
+
+/* Find and return the first position in which OBJ could be inserted
+   without changing the ordering of this vector.  LESSTHAN is a
+   function that returns true if the first argument is strictly less
+   than the second.  */
+
+template<typename T>
+inline unsigned
+vec<T, va_heap, vl_ptr>::lower_bound (T obj,
+				      bool (*lessthan)(const T &, const T &))
+    const
+{
+  return m_vec ? m_vec->lower_bound (obj, lessthan) : 0;
+}
+
+template<typename T>
+inline bool
+vec<T, va_heap, vl_ptr>::using_auto_storage () const
+{
+  return m_vec->m_vecpfx.m_using_auto_storage;
+}
+
+#if (GCC_VERSION >= 3000)
+# pragma GCC poison m_vec m_vecpfx m_vecdata
+#endif
+
+#endif // GCC_VEC_H