[RFC] VEC interface overhaul

[RFC] VEC interface overhaul

[Diego Novillo]

[-- Attachment #1: Type: text/plain, Size: 2981 bytes --]

I have overhauled the interface to VEC over the last few
weeks.  I implemented most of the plan I outlined in
http://gcc.gnu.org/ml/gcc/2012-08/msg00268.html.

I have implemented the embedded and space-efficient vectors.  The
diff for vec.[ch] is sufficiently confusing that I'm just
attaching both files for review.

In this message, I want to outline the major changes I've done.
The patch still does not work (gengtype is giving me a LOT of
problems because vectors are not pointers anymore).

There are two new types:

1- Embedded vectors: vec_e<element_type>

   These are fixed-size vectors useful to be embedded in
   structures.  For instance, tree_binfo::base_binfos.  They use
   the trailing array idiom.  Once allocated, they cannot be
   re-sized.


2- Space efficient vectors: vec_s<element_type, allocation>

   These are the traditional VECs we have always used.  They are
   implemented as a pointer to a vec_e<element_type>.  The
   difference with traditional VECs is that they no longer need
   to be pointer themselves, so their address does not change if
   the internal vector needs to be re-allocated.  They still use
   just a single word of storage before allocation, so they can
   be embedded in data structures without altering their size.

I have not yet implemented the "fast" vectors from my proposal.
Those would be useful for free variables or structures that can
tolerate an extra word of storage.

Needless to say the patch is gigantic: 2.4 Mb, 334 files
changed, 10718 insertions(+), 11536 deletions(-).  But it is
largely mechanic.

We no longer access the vectors via VEC_* macros.  The pattern is
"VEC_operation (T, A, V, args)" becomes "V.operation (args)".
That is mostly why you see ~800 fewer lines in the patch.

The only thing I could not do is create proper ctors and dtors
for the vec_s/vec_e classes.  Since these vectors are stored in
unions, we have to keep them as PODs (C++03 does not allow
non-PODs in unions).

This means that creation and destruction must be explicit.  There
is a new method vec_s<type, allocation>::create() and another
vec_s<type, allocation>::destroy() to allocate the internal
vector.

My next steps are:

- Fix gengtype issues.  Since the GTY(()) vectors are not
  pointers, gengtype is ignoring them, not adding roots and
  marking functions.  I think I've almost fixed it, but it will
  take me another day or two.

- Test on all affected architectures and compilation modes.

- Make sure memory consumption and performance are still on par
  with the current implementation.

Things I want to change (that I may do in subsequent patches):

- The allocation strategy ought to be an allocator type not an
  enum.

- vec_s<T, A>::iterate should disappear.  Instead, we want to use
  standard iterator idioms.


Please take a look at vec.[ch].  I have also pushed my changes to
the git branch git://gcc.gnu.org/git/gcc.git/dnovillo/vec-rewrite
(it's based on today's trunk).

Comments?


Thanks.  Diego.

[-- Attachment #2: vec.c --]
[-- Type: text/x-csrc, Size: 8821 bytes --]

/* Vector API for GNU compiler.
   Copyright (C) 2004, 2005, 2006, 2007, 2008, 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.

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/>.  */

/* This file is compiled twice: once for the generator programs
   once for the compiler.  */
#ifdef GENERATOR_FILE
#include "bconfig.h"
#else
#include "config.h"
#endif

#include "system.h"
#include "coretypes.h"
#include "ggc.h"
#include "vec.h"
#include "diagnostic-core.h"
#include "hashtab.h"

/* Store information about each particular vector.  */
struct vec_descriptor
{
  const char *function;
  const char *file;
  int line;
  size_t allocated;
  size_t times;
  size_t peak;
};


/* Hashtable mapping vec addresses to descriptors.  */
static htab_t vec_desc_hash;

/* Hashtable helpers.  */
static hashval_t
hash_descriptor (const void *p)
{
  const struct vec_descriptor *const d =
    (const struct vec_descriptor *) p;
  return htab_hash_pointer (d->file) + d->line;
}
static int
eq_descriptor (const void *p1, const void *p2)
{
  const struct vec_descriptor *const d = (const struct vec_descriptor *) p1;
  const struct vec_descriptor *const l = (const struct vec_descriptor *) p2;
  return d->file == l->file && d->function == l->function && d->line == l->line;
}

/* Hashtable converting address of allocated field to loc descriptor.  */
static htab_t ptr_hash;
struct ptr_hash_entry
{
  void *ptr;
  struct vec_descriptor *loc;
  size_t allocated;
};

/* Hash table helpers functions.  */
static hashval_t
hash_ptr (const void *p)
{
  const struct ptr_hash_entry *const d = (const struct ptr_hash_entry *) p;

  return htab_hash_pointer (d->ptr);
}

static int
eq_ptr (const void *p1, const void *p2)
{
  const struct ptr_hash_entry *const p = (const struct ptr_hash_entry *) p1;

  return (p->ptr == p2);
}

/* Return descriptor for given call site, create new one if needed.  */
static struct vec_descriptor *
vec_descriptor (const char *name, int line, const char *function)
{
  struct vec_descriptor loc;
  struct vec_descriptor **slot;

  loc.file = name;
  loc.line = line;
  loc.function = function;
  if (!vec_desc_hash)
    vec_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);

  slot = (struct vec_descriptor **) htab_find_slot (vec_desc_hash, &loc,
						    INSERT);
  if (*slot)
    return *slot;
  *slot = XCNEW (struct vec_descriptor);
  (*slot)->file = name;
  (*slot)->line = line;
  (*slot)->function = function;
  (*slot)->allocated = 0;
  (*slot)->peak = 0;
  return *slot;
}

/* Account the overhead.  */

void
vec_prefix::register_overhead (size_t size, const char *name, int line,
			       const char *function)
{
  struct vec_descriptor *loc = vec_descriptor (name, line, function);
  struct ptr_hash_entry *p = XNEW (struct ptr_hash_entry);
  PTR *slot;

  p->ptr = this;
  p->loc = loc;
  p->allocated = size;
  if (!ptr_hash)
    ptr_hash = htab_create (10, hash_ptr, eq_ptr, NULL);
  slot = htab_find_slot_with_hash (ptr_hash, this, htab_hash_pointer (this),
				   INSERT);
  gcc_assert (!*slot);
  *slot = p;

  loc->allocated += size;
  if (loc->peak < loc->allocated)
    loc->peak += loc->allocated;
  loc->times++;
}


/* Notice that the memory allocated for the vector has been freed.  */

void
vec_prefix::free_overhead (void)
{
  PTR *slot = htab_find_slot_with_hash (ptr_hash, this,
					htab_hash_pointer (this),
					NO_INSERT);
  struct ptr_hash_entry *p = (struct ptr_hash_entry *) *slot;
  p->loc->allocated -= p->allocated;
  htab_clear_slot (ptr_hash, slot);
  free (p);
}


/* 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.  */

unsigned
vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve, bool exact)
{
  unsigned alloc = 0;
  unsigned num = 0;

  if (pfx)
    {
      alloc = pfx->alloc_;
      num = pfx->num_;
    }
  else if (!reserve)
    /* If there's no vector, and we've not requested anything, then we
       will create a NULL vector.  */
    return 0;

  /* We must have run out of room.  */
  gcc_assert (alloc - num < reserve);

  if (exact)
    /* Exact size.  */
    alloc = num + reserve;
  else
    {
      /* Exponential growth. */
      if (!alloc)
	alloc = 4;
      else if (alloc < 16)
	/* Double when small.  */
	alloc = alloc * 2;
      else
	/* Grow slower when large.  */
	alloc = (alloc * 3 / 2);

      /* If this is still too small, set it to the right size. */
      if (alloc < num + reserve)
	alloc = num + reserve;
    }
  return alloc;
}


/* Stack vectors are a little different.  VEC_alloc turns into a call
   to vec_s<T, A>::stack_reserve and passes in space allocated via a
   call to alloca.  We record that pointer so that we know that we
   shouldn't free it.  If the vector is resized, we resize it on the
   heap.  We record the pointers in a vector and search it in LIFO
   order--i.e., we look for the newest stack vectors first.  We don't
   expect too many stack vectors at any one level, and searching from
   the end should normally be efficient even if they are used in a
   recursive function.  */

static vec_s<void *> stack_vecs;

/* Add a stack vector to STACK_VECS.  */

void
register_stack_vec (void *vec)
{
  stack_vecs.safe_push (vec);
}


/* If VEC is registered in STACK_VECS, return its index.
   Otherwise, return -1.  */

int
stack_vec_register_index (void *vec)
{
  for (unsigned ix = stack_vecs.length (); ix > 0; --ix)
    if (stack_vecs[ix - 1] == vec)
      return static_cast<int> (ix - 1);
  return -1;
}


/* Remove vector at slot IX from the list of registered stack vectors.  */

void
unregister_stack_vec (unsigned ix)
{
  stack_vecs.unordered_remove (ix);
}


/* Helper for qsort; sort descriptors by amount of memory consumed.  */

static int
cmp_statistic (const void *loc1, const void *loc2)
{
  const struct vec_descriptor *const l1 =
    *(const struct vec_descriptor *const *) loc1;
  const struct vec_descriptor *const l2 =
    *(const struct vec_descriptor *const *) loc2;
  long diff;
  diff = l1->allocated - l2->allocated;
  if (!diff)
    diff = l1->peak - l2->peak;
  if (!diff)
    diff = l1->times - l2->times;
  return diff > 0 ? 1 : diff < 0 ? -1 : 0;
}


/* Collect array of the descriptors from hashtable.  */

static struct vec_descriptor **loc_array;
static int
add_statistics (void **slot, void *b)
{
  int *n = (int *)b;
  loc_array[*n] = (struct vec_descriptor *) *slot;
  (*n)++;
  return 1;
}

/* Dump per-site memory statistics.  */

void
dump_vec_loc_statistics (void)
{
  int nentries = 0;
  char s[4096];
  size_t allocated = 0;
  size_t times = 0;
  int i;

  if (! GATHER_STATISTICS)
    return;

  loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
  fprintf (stderr, "Heap vectors:\n");
  fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
	   "source location", "Leak", "Peak", "Times");
  fprintf (stderr, "-------------------------------------------------------\n");
  htab_traverse (vec_desc_hash, add_statistics, &nentries);
  qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
  for (i = 0; i < nentries; i++)
    {
      struct vec_descriptor *d = loc_array[i];
      allocated += d->allocated;
      times += d->times;
    }
  for (i = 0; i < nentries; i++)
    {
      struct vec_descriptor *d = loc_array[i];
      const char *s1 = d->file;
      const char *s2;
      while ((s2 = strstr (s1, "gcc/")))
	s1 = s2 + 4;
      sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
      s[48] = 0;
      fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
	       (long)d->allocated,
	       (d->allocated) * 100.0 / allocated,
	       (long)d->peak,
	       (long)d->times,
	       (d->times) * 100.0 / times);
    }
  fprintf (stderr, "%-48s %10ld                        %10ld\n",
	   "Total", (long)allocated, (long)times);
  fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
	   "source location", "Leak", "Peak", "Times");
  fprintf (stderr, "-------------------------------------------------------\n");
}

[-- Attachment #3: vec.h --]
[-- Type: text/x-chdr, Size: 36943 bytes --]

/* Vector API for GNU compiler.
   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.

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

#include "statistics.h"		/* For CXX_MEM_STAT_INFO.  */

/* 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 two arguments: the type of the
   elements in the vector and the allocation strategy to use.  Four
   allocation strategies are supported:

	- Heap: allocation is done using malloc/free.

  	- Stack: allocation is done using alloca.

  	- 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.

   The type and allocation mechanisms are specified when the vector
   is declared.  The valid allocation strategies are declared in
   enum vec_allocation.

   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.

   Two types of vectors are supported:
   
   * Embeddable vectors (vec_e<T>)
   
     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_s<T, A>)

     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 vector of tree pointers in GC memory.
     vec_s<tree, va_gc> 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);

/* Support for GC interaction.  This is needed because we cannot
   include ggc.h from vec.h.  This file is included from gen* code
   that is built before gengtype support files are generated.  In
   particular, gtype-desc.h is not always available.  None of these
   files will ever need GC vectors, so we just need the function
   signatures.  */
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);

/* 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.
   va_stack	- Allocation uses alloca.

   FIXME - The allocation strategy should be implemented as template
	   allocator types to be shared across all classes and
	   structures that need allocation (factor out of
	   hash-table.h).  */
enum vec_allocation { va_heap, va_gc, va_gc_atomic, va_stack };

template<typename T, enum vec_allocation A>
class vec_s;

/* Control data for vectors.  This contains the number of allocated
   and used slots inside a vector.  */

class vec_prefix
{
protected:
  /* Memory allocation support routines in vec.c.  */
  void register_overhead (size_t, const char *, int, const char *);
  void free_overhead (void);
  static unsigned calculate_allocation (vec_prefix *, unsigned, bool);

  unsigned alloc_;
  unsigned num_;
};


/* 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>
class GTY((user)) vec_e : public vec_prefix
{
public:
  unsigned allocated (void) const { return alloc_; }
  unsigned length (void) const { return num_; }
  bool is_empty (void) const { return num_ == 0; }
  T *address (void) { return vec_; }
  const T &operator[] (unsigned) const;
  T &operator[] (unsigned);
  T &last (void);
  bool space (unsigned);
  bool iterate (unsigned, T *);
  bool iterate (unsigned, T **);
  void splice (vec_e<T> &);
  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 *));
  unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
  static size_t embedded_size (unsigned);
  void embedded_init (unsigned, unsigned = 0);

  /* vec_s class can access our internal data and functions.  */
  template <typename, enum vec_allocation> friend struct vec_s;

private:
  T vec_[1];
};


/* Index into vector.  Return the IX'th element.  IX must be in the
   domain of the vector.  */

template<typename T>
inline const T &
vec_e<T>::operator[] (unsigned ix) const
{
  gcc_assert (ix < num_);
  return vec_[ix];
}

template<typename T>
inline T &
vec_e<T>::operator[] (unsigned ix)
{
  gcc_assert (ix < num_);
  return vec_[ix];
}


/* Get the final element of the vector, which must not be empty.  */

template<typename T>
inline T &
vec_e<T>::last (void)
{
  gcc_assert (num_ > 0);
  return (*this)[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_s::reserve
   will.  */

template<typename T>
inline bool
vec_e<T>::space (unsigned nelems)
{
  return alloc_ - 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_s<T, A>::iterate(v, ix, &ptr); ix++)
       continue;  */

template<typename T>
inline bool
vec_e<T>::iterate (unsigned ix, T *ptr)
{
  if (ix < num_)
    {
      *ptr = vec_[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>
inline bool
vec_e<T>::iterate (unsigned ix, T **ptr)
{
  if (ix < num_)
    {
      *ptr = CONST_CAST (T *, &vec_[ix]);
      return true;
    }
  else
    {
      *ptr = 0;
      return false;
    }
}


/* 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>
inline void
vec_e<T>::splice (vec_e<T> &src)
{
  unsigned len = src.length();
  if (len == 0)
    return;

  gcc_assert (space (len));

  memcpy (address() + length(), src.address(), len * sizeof (T));
  num_ += len;
}


/* 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_e<T>::quick_push (const T &obj)
{
  gcc_assert (space (1));
  T *slot = &vec_[num_++];
  *slot = obj;
  return slot;
}


/* Pop and return the last element off the end of the vector.  */

template<typename T>
inline T &
vec_e<T>::pop (void)
{
  gcc_assert (length () > 0);
  return vec_[--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>
inline void
vec_e<T>::truncate (unsigned size)
{
  gcc_assert (length () >= size);
  num_ = size;
}


/* Insert an element, OBJ, at the IXth position of this vector.  There
   must be sufficient space.  */

template<typename T>
inline void
vec_e<T>::quick_insert (unsigned ix, const T &obj)
{
  gcc_assert (length () < allocated ());
  gcc_assert (ix < length ());
  T *slot = &vec_[ix];
  memmove (slot + 1, slot, (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>
inline void
vec_e<T>::ordered_remove (unsigned ix)
{
  gcc_assert (ix < length());
  T *slot = &vec_[ix];
  memmove (slot, slot + 1, (--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>
inline void
vec_e<T>::unordered_remove (unsigned ix)
{
  gcc_assert (ix < length());
  vec_[ix] = vec_[--num_];
}


/* 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_e<T>::block_remove (unsigned ix, unsigned len)
{
  gcc_assert (ix + len <= length());
  T *slot = &vec_[ix];
  num_ -= len;
  memmove (slot, slot + len, (num_ - ix) * sizeof (T));
}


/* Sort the contents of this vector with qsort.  CMP is the comparison
   function to pass to qsort.  */

template<typename T>
inline void
vec_e<T>::qsort (int (*cmp) (const void *, const void *))
{
  ::qsort (address(), length(), sizeof (T), cmp);
}


/* 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>
unsigned
vec_e<T>::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 vec_e 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_e<T>::embedded_size (unsigned alloc);
   void v->embedded_init(unsigned alloc, unsigned num);

   These allow the caller to perform the memory allocation.  */

template<typename T>
inline size_t
vec_e<T>::embedded_size (unsigned alloc)
{
  return sizeof (vec_prefix) + alloc * sizeof (T);
}


/* Initialize the vector to contain room for ALLOC elements and
   NUM active elements.  */

template<typename T>
inline void
vec_e<T>::embedded_init (unsigned alloc, unsigned num)
{
  alloc_ = alloc;
  num_ = num;
}


/* Garbage collection support for vec_e.  */

template<typename T>
void
gt_ggc_mx (vec_e<T> *v)
{
  extern void gt_ggc_mx (T &);
  for (unsigned i = 0; i < v->length (); i++)
    gt_ggc_mx ((*v)[i]);
}


/* PCH support for vec_e.  */

template<typename T>
void
gt_pch_nx (vec_e<T> *v)
{
  extern void gt_pch_nx (T &);
  for (unsigned i = 0; i < v->length (); i++)
    gt_pch_nx ((*v)[i]);
}

template<typename T>
void
gt_pch_nx (vec_e<T *> *v, gt_pointer_operator op, void *cookie)
{
  for (unsigned i = 0; i < v->length (); i++)
    op (&((*v)[i]), cookie);
}

template<typename T>
void
gt_pch_nx (vec_e<T> *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 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).


   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, enum vec_allocation A = va_heap>
class GTY((user)) vec_s
{
public:
  /* Vector allocation.  */
  static vec_s<T, A> *alloc (unsigned CXX_MEM_STAT_INFO);
  static void free (vec_s<T, A> *&);

  /* Internal vector creation and initialization.  */
  static vec_s<T, A> create (unsigned CXX_MEM_STAT_INFO);
  static vec_s<T, A> create (unsigned, vec_e<T> *);
  void destroy (void);
  void init (void) { vec_ = NULL; }

  /* Vector operations.  */
  bool is_allocated (void) const
  { return vec_ != NULL; }

  bool is_empty (void) const
  { return vec_ ? vec_->is_empty() : true; }

  unsigned length (void) const
  { return vec_ ? vec_->length() : 0; }

  T *address (void) const
  { return vec_ ? vec_->vec_ : NULL; }

  vec_e<T> *embedded_vec (void) const
  { return vec_; }

  const T &operator[] (unsigned ix) const
  { return (*vec_)[ix]; }

  bool operator!=(const vec_s<T, A> &other) const
  { return !(*this == other); }

  bool operator==(const vec_s<T, A> &other) const
  { return address () == other.address (); }

  T &operator[] (unsigned ix)
  { return (*vec_)[ix]; }

  T &last (void)
  { return vec_->last(); }

  bool space (int nelems) const
  { return vec_ ? vec_->space (nelems) : nelems == 0; }

  bool iterate (unsigned ix, T *p) const;
  bool iterate (unsigned ix, T **p) const;
  vec_s<T, A> copy (ALONE_CXX_MEM_STAT_INFO);
  bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
  bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
  void splice (vec_s<T, A> &);
  void safe_splice (vec_s<T, A> & 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_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 *));
  unsigned lower_bound (T, bool (*)(const T &, const T &)) const;

private:
  void gc_reserve (unsigned, bool CXX_MEM_STAT_INFO);
  void heap_reserve (unsigned, bool CXX_MEM_STAT_INFO);
  void stack_reserve (vec_e<T> *, unsigned);
  void stack_grow (unsigned, bool CXX_MEM_STAT_INFO);
  void heap_free (void);
  void stack_free (void);

  vec_e<T> *vec_;
};


/* 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, enum vec_allocation A>
inline bool
vec_s<T, A>::iterate (unsigned ix, T *ptr) const
{
  if (vec_)
    return 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, enum vec_allocation A>
inline bool
vec_s<T, A>::iterate (unsigned ix, T **ptr) const
{
  if (vec_)
    return 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))

/* 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)--)


/* Allocate memory for a new vector and return a pointer to the
   newly allocated vector.  Additionally, call vec_s::create to reserve
   room in the internal vector for NELEMS objects.  */

template<typename T, enum vec_allocation A>
vec_s<T, A> *
vec_s<T, A>::alloc (unsigned nelems MEM_STAT_DECL)
{
  vec_s<T, A> *ptr;

  switch (A)
    {
      case va_gc:
      case va_gc_atomic:
	ptr = (vec_s<T, A> *) ggc_realloc_stat (0, sizeof (vec_s<T, A>));
	break;

      case va_heap:
	ptr = (vec_s<T, A> *) xmalloc (sizeof (vec_s<T, A>));
	break;

      case va_stack:
	gcc_unreachable ();
    }

  /* Now create the internal vector in PTR.  */
  ptr->create (nelems);

  return ptr;
}


/* Free the memory allocated for a vector V.  */

template<typename T, enum vec_allocation A>
void
vec_s<T, A>::free (vec_s<T, A> *&v)
{
  v->destroy ();

  switch (A)
    {
      case va_gc:
      case va_gc_atomic:
	ggc_free (v);
	break;

      case va_heap:
	::free (v);
	break;

      case va_stack:
	gcc_unreachable ();
    }
  v = NULL;
}


/* Construct a new vector with space for exactly NELEMS objects.  If
   NELEMS is zero, NO vector is created.

   Note that this does not allocate an instance of vec_s<T, A>.  It allocates
   the actual vector of elements (i.e., vec_e<T>) inside a vec_s<T, A>
   instance.

   Additionally, calling this method on stack vectors (i.e., A == va_stack)
   will produce a runtime error.  To allocate stack vectors, you must
   call VEC_stack_alloc.  */

template<typename T, enum vec_allocation A>
inline vec_s<T, A>
vec_s<T, A>::create (unsigned nelems MEM_STAT_DECL)
{
  vec_s<T, A> newvec;

  /* Ensure there are at least NELEMS free slots in the vector, growing
     exactly.  As a special case, if NELEMS is 0, no vector will be
     created.  */
  newvec.init ();
  if (nelems > 0)
    {
      switch (A)
	{
	case va_gc:
	case va_gc_atomic:
	  newvec.gc_reserve (nelems, true);
	  break;

	case va_heap:
	  newvec.heap_reserve (nelems, true);
	  break;

	case va_stack:
	  gcc_unreachable ();
	}
    }

  return newvec;
}


/* Allocate a new vector with space for exactly NELEMS objects.  If
   NELEMS is zero, NO vector is created.

   For the stack allocator, no memory is really allocated.  The vector
   is initialized to be at address SPACE and contain NELEMS slots.
   Memory allocation actually occurs in the expansion of VEC_alloc.

   Usage notes:

   * This does not allocate an instance of vec_s<T, A>.  It allocates the
     actual vector of elements (i.e., vec_e<T>) inside a vec_s<T, A>
     instance.

   * This allocator must always be a macro:

     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.

     Important limitations of stack vectors:

     - 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 stack-allocated vector from the function which
       allocated it.  */

#define VEC_stack_alloc(T,V,N)						\
    (V) = vec_s<T, va_stack>::create(N, XALLOCAVAR (vec_e<T>,		\
						  vec_e<T>::embedded_size (N)))

template<typename T, enum vec_allocation A>
inline vec_s<T, A>
vec_s<T, A>::create (unsigned nelems, vec_e<T> *space)
{
  gcc_assert (A == va_stack);
  vec_s<T, A> newvec;
  newvec.stack_reserve (space, nelems);
  return newvec;
}


/* Free the memory occupied by the embedded vector.  */

template<typename T, enum vec_allocation A>
inline void
vec_s<T, A>::destroy (void)
{
  if (!vec_)
    return;

  switch (A)
    {
      case va_heap:
	heap_free ();
	break;

      case va_gc:
      case va_gc_atomic:
	ggc_free (vec_);
	break;

      case va_stack:
	stack_free ();
	break;
    }
  init ();
}


/* Return a copy of this vector.  */

template<typename T, enum vec_allocation A>
inline vec_s<T, A>
vec_s<T, A>::copy (ALONE_MEM_STAT_DECL)
{
  unsigned len = length();
  vec_s<T, A> new_vec;

  if (len)
    {
      new_vec = vec_s<T, A>::create (len);
      new_vec.vec_->embedded_init (len, len);
      memcpy (new_vec.address (), vec_->vec_, sizeof (T) * len);
    }

  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, enum vec_allocation A>
inline bool
vec_s<T, A>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
{
  bool extend = nelems ? !space (nelems) : false;

  if (extend)
    {
      switch (A)
	{
	case va_gc:
	case va_gc_atomic:
	  gc_reserve (nelems, exact);
	  break;

	case va_heap:
	  heap_reserve (nelems, exact);
	  break;

	case va_stack:
	  stack_grow (nelems, exact);
	  break;
	}
    }

  return extend;
}


/* 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, enum vec_allocation A>
inline bool
vec_s<T, A>::reserve_exact (unsigned nelems MEM_STAT_DECL)
{
  return reserve (nelems, true);
}


/* 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, enum vec_allocation A>
inline void
vec_s<T, A>::splice (vec_s<T, A> &src)
{
  vec_->splice (*(src.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, enum vec_allocation A>
inline void
vec_s<T, A>::safe_splice (vec_s<T, A> &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, enum vec_allocation A>
inline T *
vec_s<T, A>::quick_push (const T &obj)
{
  return 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, vec_allocation A>
inline T *
vec_s<T, A>::safe_push (const T &obj MEM_STAT_DECL)
{
  reserve (1, false);
  return quick_push (obj);
}


/* Pop and return the last element off the end of the vector.  */

template<typename T, enum vec_allocation A>
inline T &
vec_s<T, A>::pop (void)
{
  return 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, enum vec_allocation A>
inline void
vec_s<T, A>::truncate (unsigned size)
{
  if (vec_)
    vec_->truncate (size);
  else
    gcc_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.  */

template<typename T, enum vec_allocation A>
inline void
vec_s<T, A>::safe_grow (unsigned size MEM_STAT_DECL)
{
  gcc_assert (size > 0 && length () <= size);
  reserve_exact (size - length ());
  vec_->num_ = size;
}


/* Grow the embedded vector to a specific length.  SIZE must be as
   long or longer than the current length.  The new elements are
   initialized to zero.  */

template<typename T, enum vec_allocation A>
inline void
vec_s<T, A>::safe_grow_cleared (unsigned size MEM_STAT_DECL)
{
  unsigned oldsize = length ();
  safe_grow (size);
  memset (&(address()[oldsize]), 0, sizeof (T) * (size - oldsize));
}


/* Insert an element, OBJ, at the IXth position of this vector.  There
   must be sufficient space.  */

template<typename T, enum vec_allocation A>
inline void
vec_s<T, A>::quick_insert (unsigned ix, const T &obj)
{
  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, enum vec_allocation A>
inline void
vec_s<T, A>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
{
  reserve (1, false);
  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, enum vec_allocation A>
inline void
vec_s<T, A>::ordered_remove (unsigned ix)
{
  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, enum vec_allocation A>
inline void
vec_s<T, A>::unordered_remove (unsigned ix)
{
  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, enum vec_allocation A>
inline void
vec_s<T, A>::block_remove (unsigned ix, unsigned len)
{
  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, enum vec_allocation A>
inline void
vec_s<T, A>::qsort (int (*cmp) (const void *, const void *))
{
  vec_->qsort (cmp);
}


/* 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, enum vec_allocation A>
inline unsigned
vec_s<T, A>::lower_bound (T obj, bool (*lessthan)(const T &, const T &)) const
{
  return vec_->lower_bound (obj, lessthan);
}


/* Garbage collection support for vec_s.  */

template<typename T, enum vec_allocation A>
void
gt_ggc_mx (vec_s<T, A> *v)
{
  gt_ggc_mx (v->embedded_vec());
}


/* PCH support for vec_s.  */

template<typename T, enum vec_allocation A>
void
gt_pch_nx (vec_s<T, A> *v)
{
  gt_pch_nx (v->embedded_vec());
}

template<typename T, enum vec_allocation A>
void
gt_pch_nx (vec_s<T, A> *v, gt_pointer_operator op, void *cookie)
{
  gt_pch_nx (v->embedded_vec(), op, cookie);
}

/* Free the heap space allocated for this vector.  */

template<typename T, enum vec_allocation A>
void
vec_s<T, A>::heap_free (void)
{
  if (GATHER_STATISTICS)
    vec_->free_overhead ();
  ::free (vec_);
  vec_ = NULL;
}


/* Allocator for GC memory.  Ensure there are at least RESERVE free
   slots in this vector.  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, enum vec_allocation A>
void
vec_s<T, A>::gc_reserve (unsigned reserve, bool exact MEM_STAT_DECL)
{
  unsigned alloc = vec_prefix::calculate_allocation (vec_, reserve, exact);
  if (!alloc)
    {
      ggc_free (vec_);
      return;
    }

  /* Calculate the amount of space we want.  */
  size_t size = vec_e<T>::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 = length ();
  vec_ = static_cast <vec_e<T> *> (ggc_realloc_stat (vec_, size));
  vec_->embedded_init (alloc, nelem);
}


/* Like vec_s<T, A>::gc_reserve, but for heap allocated vectors.  */

template<typename T, enum vec_allocation A>
void
vec_s<T, A>::heap_reserve (unsigned reserve, bool exact MEM_STAT_DECL)
{
  unsigned alloc = vec_prefix::calculate_allocation (vec_, reserve, exact);
  if (!alloc)
    {
      heap_free ();
      return;
    }

  if (GATHER_STATISTICS && vec_)
    vec_->free_overhead ();

  size_t size = vec_e<T>::embedded_size (alloc);
  unsigned nelem = length ();
  vec_ = static_cast <vec_e<T> *> (xrealloc (vec_, size));
  vec_->embedded_init (alloc, nelem);

  if (GATHER_STATISTICS)
    vec_->register_overhead (size FINAL_PASS_MEM_STAT);
}

/* Helper functions to keep track of vectors allocated on the stack.  */
void register_stack_vec (void *);
int stack_vec_register_index (void *);
void unregister_stack_vec (unsigned);


/* Allocate a vector which uses alloca for the initial allocation.
   SPACE is space allocated using alloca.  ALLOC is the number of
   entries allocated.  */

template<typename T, enum vec_allocation A>
void
vec_s<T, A>::stack_reserve (vec_e<T> *space, unsigned alloc)
{
  vec_ = space;
  register_stack_vec (static_cast<void *> (vec_));
  vec_->embedded_init (alloc, 0);
}


/* Free a vector allocated on the stack.  Don't actually free it if we
   find it in the hash table.  */

template<typename T, enum vec_allocation A>
void
vec_s<T, A>::stack_free (void)
{
  int ix = stack_vec_register_index (static_cast<void *> (vec_));
  if (ix >= 0)
    unregister_stack_vec (ix);
  else
    {
      /* The vector was not on the list of vecs allocated on the stack, so it
	 must be allocated on the heap.  */
      heap_free ();
    }
}


/* Grow a vector allocated using alloca.  When this happens, we switch
   back to heap allocation.  We remove the vector from stack_vecs, if
   it is there, since we no longer need to avoid freeing it.  */

template<typename T, enum vec_allocation A>
void
vec_s<T, A>::stack_grow (unsigned nelems, bool exact MEM_STAT_DECL)
{
  int ix = stack_vec_register_index (static_cast<void *> (vec_));
  if (ix >= 0)
    unregister_stack_vec (ix);
  else
    {
      /* VEC_ is already on the heap.  */
      heap_reserve (nelems, exact);
      return;
    }

  /* Move VEC_ to the heap.  */
  nelems += vec_->num_;
  vec_e<T> *oldvec = vec_;
  vec_ = NULL;
  heap_reserve (nelems, exact);
  if (vec_ && oldvec)
    {
      vec_->num_ = oldvec->length ();
      memcpy (vec_->vec_, oldvec->vec_, oldvec->length () * sizeof (T));
    }
}

#endif /* GCC_VEC_H */

Re: [RFC] VEC interface overhaul

[Richard Biener]

On Tue, 16 Oct 2012, Diego Novillo wrote:

> I have overhauled the interface to VEC over the last few
> weeks.  I implemented most of the plan I outlined in
> http://gcc.gnu.org/ml/gcc/2012-08/msg00268.html.
> 
> I have implemented the embedded and space-efficient vectors.  The
> diff for vec.[ch] is sufficiently confusing that I'm just
> attaching both files for review.
> 
> In this message, I want to outline the major changes I've done.
> The patch still does not work (gengtype is giving me a LOT of
> problems because vectors are not pointers anymore).
> 
> There are two new types:
> 
> 1- Embedded vectors: vec_e<element_type>
> 
>    These are fixed-size vectors useful to be embedded in
>    structures.  For instance, tree_binfo::base_binfos.  They use
>    the trailing array idiom.  Once allocated, they cannot be
>    re-sized.
>
> 
> 2- Space efficient vectors: vec_s<element_type, allocation>
>
>    These are the traditional VECs we have always used.  They are
>    implemented as a pointer to a vec_e<element_type>.  The
>    difference with traditional VECs is that they no longer need
>    to be pointer themselves, so their address does not change if
>    the internal vector needs to be re-allocated.  They still use
>    just a single word of storage before allocation, so they can
>    be embedded in data structures without altering their size.

Why change the name?  I'd have used vec<> ...

Can't we implement vec_e as vec<element_type, embedded> by
means of a partial specialization?

Sorry for the bike-shedding ;)

> I have not yet implemented the "fast" vectors from my proposal.
> Those would be useful for free variables or structures that can
> tolerate an extra word of storage.
> 
> Needless to say the patch is gigantic: 2.4 Mb, 334 files
> changed, 10718 insertions(+), 11536 deletions(-).  But it is
> largely mechanic.
> 
> We no longer access the vectors via VEC_* macros.  The pattern is
> "VEC_operation (T, A, V, args)" becomes "V.operation (args)".
> That is mostly why you see ~800 fewer lines in the patch.
> 
> The only thing I could not do is create proper ctors and dtors
> for the vec_s/vec_e classes.  Since these vectors are stored in
> unions, we have to keep them as PODs (C++03 does not allow
> non-PODs in unions).
> 
> This means that creation and destruction must be explicit.  There
> is a new method vec_s<type, allocation>::create() and another
> vec_s<type, allocation>::destroy() to allocate the internal
> vector.

::alloc() and ::free()?  I see you have those, too, but from

  /* Vector allocation.  */
  static vec_s<T, A> *alloc (unsigned CXX_MEM_STAT_INFO);
  static void free (vec_s<T, A> *&);

  /* Internal vector creation and initialization.  */
  static vec_s<T, A> create (unsigned CXX_MEM_STAT_INFO);
  static vec_s<T, A> create (unsigned, vec_e<T> *);
  void destroy (void);

I can't see how they differ and what users should use?  I suppose
::create and ::destroy are just implementation details?  Thus
you'd make them private?  Why is create not a member function?
It should be IMHO

template<typename T, enum vec_allocation A>
inline vec_s<T, A>&
vec_s<T, A>::create (unsigned nelems, vec_e<T> *space)
{
  gcc_assert (A == va_stack);
  this->stack_reserve (space, nelems);
  return *this;
}

Otherwise please use gcc_checking_assert in inline functions,
otherwise they won't be inlined due to size constraints in most
of the cases.

Likewise ::copy should mimic a copy constructor.  Not sure if
that will work out ... isn't it enough that vec_e is embeddable
into a union?

Otherwise thanks for working on this and sorry for the C++
bikeshedding - there are just so many more ways to do something
in C++ compared to C ;)

Richard.

> My next steps are:
> 
> - Fix gengtype issues.  Since the GTY(()) vectors are not
>   pointers, gengtype is ignoring them, not adding roots and
>   marking functions.  I think I've almost fixed it, but it will
>   take me another day or two.
> 
> - Test on all affected architectures and compilation modes.
> 
> - Make sure memory consumption and performance are still on par
>   with the current implementation.
> 
> Things I want to change (that I may do in subsequent patches):
> 
> - The allocation strategy ought to be an allocator type not an
>   enum.
> 
> - vec_s<T, A>::iterate should disappear.  Instead, we want to use
>   standard iterator idioms.
> 
> 
> Please take a look at vec.[ch].  I have also pushed my changes to
> the git branch git://gcc.gnu.org/git/gcc.git/dnovillo/vec-rewrite
> (it's based on today's trunk).
> 
> Comments?
> 
> 
> Thanks.  Diego.
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend

Re: [RFC] VEC interface overhaul

[Diego Novillo]

On 2012-10-17 06:14 , Richard Biener wrote:

> Can't we implement vec_e as vec<element_type, embedded> by
> means of a partial specialization?

Ah, yes, that's certainly possible and prevents renaming the types in 
the future.

>> I have not yet implemented the "fast" vectors from my proposal.
>> Those would be useful for free variables or structures that can
>> tolerate an extra word of storage.
>>
>> Needless to say the patch is gigantic: 2.4 Mb, 334 files
>> changed, 10718 insertions(+), 11536 deletions(-).  But it is
>> largely mechanic.
>>
>> We no longer access the vectors via VEC_* macros.  The pattern is
>> "VEC_operation (T, A, V, args)" becomes "V.operation (args)".
>> That is mostly why you see ~800 fewer lines in the patch.
>>
>> The only thing I could not do is create proper ctors and dtors
>> for the vec_s/vec_e classes.  Since these vectors are stored in
>> unions, we have to keep them as PODs (C++03 does not allow
>> non-PODs in unions).
>>
>> This means that creation and destruction must be explicit.  There
>> is a new method vec_s<type, allocation>::create() and another
>> vec_s<type, allocation>::destroy() to allocate the internal
>> vector.
>
> ::alloc() and ::free()?  I see you have those, too, but from
>
>    /* Vector allocation.  */
>    static vec_s<T, A> *alloc (unsigned CXX_MEM_STAT_INFO);
>    static void free (vec_s<T, A> *&);
>
>    /* Internal vector creation and initialization.  */
>    static vec_s<T, A> create (unsigned CXX_MEM_STAT_INFO);
>    static vec_s<T, A> create (unsigned, vec_e<T> *);
>    void destroy (void);
>
> I can't see how they differ and what users should use?  I suppose
> ::create and ::destroy are just implementation details?  Thus
> you'd make them private?  Why is create not a member function?
> It should be IMHO

This is the part I don't like too much.  The problem is that we can't 
use ctors/dtors here.  Both ::alloc() and ::free() allocate a pointer to 
a vec.  So they can't really be member functions.  We don't really have 
any calls to ::alloc/::free now (I added them for completeness), so 
leaving them out for now is certainly possible.

::create is special too not because it needs to allocate a pointer, but 
because it looked odd when used as a regular member function.  Consider:

foo(unsigned n)
{
   vec_s<tree> v = v.create(n);
   ...
}

We are calling ::create on an "uninitialized" object.  This will work, 
because ::create() allocates the internal vector and reads no state from 
'v'.  It just looked odd.  Ideally, this code would look like:

foo(unsigned n)
{
   vec<tree> v(n);
   ...
}

But we can't have constructors on vec (I'm tempted to add a vector class 
that cannot be put in unions but does provide ctors/dtors).

With the current syntax, we do:

foo(unsigned n)
{
   vec<tree> v = vec<tree>::create(n);
}

This has the problem of being overly verbose (particularly when the 
template arguments are long).  So, if we don't mind the slightly odd 
syntax in the first version, I could just change ::create to be a 
regular member function.


> template<typename T, enum vec_allocation A>
> inline vec_s<T, A>&
> vec_s<T, A>::create (unsigned nelems, vec_e<T> *space)
> {
>    gcc_assert (A == va_stack);
>    this->stack_reserve (space, nelems);
>    return *this;
> }
>
> Otherwise please use gcc_checking_assert in inline functions,
> otherwise they won't be inlined due to size constraints in most
> of the cases.

Good point.  Thanks.

> Likewise ::copy should mimic a copy constructor.  Not sure if
> that will work out ... isn't it enough that vec_e is embeddable
> into a union?

You want to make ::copy a static function?  Not sure I'm following you here.

> Otherwise thanks for working on this and sorry for the C++
> bikeshedding - there are just so many more ways to do something
> in C++ compared to C ;)

Heh, indeed.  Thanks for the review.


Diego.

Re: [RFC] VEC interface overhaul

[Diego Novillo]

I have added a wiki page to help with transitioning old VEC code to the new API.

http://gcc.gnu.org/wiki/cxx-conversion/cxx-vec

I am doing the final tests (only a handful of testsuite failures to
fix) and expect to commit the patch in the coming days.

I've included in this message everyone who seems to have outstanding
patches waiting to merge.  If your patch uses VEC(), this patch of
mine will break you.

If folks prefer, I can wait until everyone has committed their changes
before I send mine in.  I've gotten pretty good at fixing merge
conflicts on VEC() code, so it's not a big deal to me and may
facilitate merging other branches.  Please let me know.

Alternately, the transition guide should help with the conversion.


Thanks.  Diego.