Subversion Repositories altor32

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

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

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

   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);

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

  friend struct va_stack;

  unsigned alloc_;

  unsigned num_;

};

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.

   va_stack     - Allocation uses alloca.  */

/* 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->vecpfx_ : 0, reserve, exact);

  if (!alloc)

    {

      release (v);

      return;

    }

  if (GATHER_STATISTICS && v)

    v->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->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->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) { 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->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

{

};

/* Allocator type for stack vectors.  */

struct va_stack

{

  /* Use vl_ptr as the default layout for stack vectors.  */

  typedef vl_ptr default_layout;

  template<typename T>

  static void alloc (vec<T, va_stack, vl_ptr>&, unsigned,

                     vec<T, va_stack, vl_embed> *);

  template <typename T>

  static void reserve (vec<T, va_stack, vl_embed> *&, unsigned, bool

                       CXX_MEM_STAT_INFO);

  template <typename T>

  static void release (vec<T, va_stack, vl_embed> *&);

};

/* 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 V which uses alloca for the initial allocation.

   SPACE is space allocated using alloca.  NELEMS is the number of

   entries allocated.  */

template<typename T>

void

va_stack::alloc (vec<T, va_stack, vl_ptr> &v, unsigned nelems,

                 vec<T, va_stack, vl_embed> *space)

{

  v.vec_ = space;

  register_stack_vec (static_cast<void *> (v.vec_));

  v.vec_->embedded_init (nelems, 0);

}

/* Reserve NELEMS slots for a vector initially allocated on the stack.

   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.  If EXACT is true, grow exactly, otherwise

   grow exponentially.  */

template<typename T>

void

va_stack::reserve (vec<T, va_stack, vl_embed> *&v, unsigned nelems, bool exact

                   MEM_STAT_DECL)

{

  int ix = stack_vec_register_index (static_cast<void *> (v));

  if (ix >= 0)

    unregister_stack_vec (ix);

  else

    {

      /* V is already on the heap.  */

      va_heap::reserve (reinterpret_cast<vec<T, va_heap, vl_embed> *&> (v),

                        nelems, exact PASS_MEM_STAT);

      return;

    }

  /* Move VEC_ to the heap.  */

  nelems += v->vecpfx_.num_;

  vec<T, va_stack, vl_embed> *oldvec = v;

  v = NULL;

  va_heap::reserve (reinterpret_cast<vec<T, va_heap, vl_embed> *&>(v), nelems,

                    exact PASS_MEM_STAT);

  if (v && oldvec)

    {

      v->vecpfx_.num_ = oldvec->length ();

      memcpy (v->vecdata_,

              oldvec->vecdata_,

              oldvec->length () * sizeof (T));

    }

}

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

   find it in the hash table.  */

template<typename T>

void

va_stack::release (vec<T, va_stack, vl_embed> *&v)

{

  if (v == NULL)

    return;

  int ix = stack_vec_register_index (static_cast<void *> (v));

  if (ix >= 0)

    {

      unregister_stack_vec (ix);

      v = NULL;

    }

  else

    {

      /* The vector was not on the list of vectors allocated on the stack, so it

         must be allocated on the heap.  */

      va_heap::release (reinterpret_cast<vec<T, va_heap, vl_embed> *&> (v));

    }

}

/* 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 vecpfx_.alloc_; }

  unsigned length (void) const { return vecpfx_.num_; }

  bool is_empty (void) const { return vecpfx_.num_ == 0; }

  T *address (void) { return vecdata_; }

  const T *address (void) const { return 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 *));

  unsigned lower_bound (T, bool (*)(const T &, const T &)) const;

  static size_t embedded_size (unsigned);

  void embedded_init (unsigned, 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;

  friend struct va_stack;

  /* FIXME - These fields should be private, but we need to cater to

             compilers that have stricter notions of PODness for types.  */

  vec_prefix vecpfx_;

  T 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