X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=gcc%2Fvec.h;h=cbdd439571b97fe920d121332514557c72e4852c;hb=6566b0fb86addb5c28d3ff8b2631f7f9516d4054;hp=afde351a79650a8746b93f16883c585836bfc758;hpb=00f96dc9a9a505ef2d439a808e66226fb8b93baf;p=gcc.git diff --git a/gcc/vec.h b/gcc/vec.h index afde351a796..cbdd439571b 100644 --- a/gcc/vec.h +++ b/gcc/vec.h @@ -1,5 +1,5 @@ /* Vector API for GNU compiler. - Copyright (C) 2004-2013 Free Software Foundation, Inc. + Copyright (C) 2004-2017 Free Software Foundation, Inc. Contributed by Nathan Sidwell Re-implemented in C++ by Diego Novillo @@ -22,37 +22,14 @@ along with GCC; see the file COPYING3. If not see #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 +/* Some gen* file have no ggc support as the header file gtype-desc.h is + missing. Provide these definitions in case ggc.h has not been included. + This is not a problem because any code that runs before gengtype is built + will never need to use GC vectors.*/ + +extern void ggc_free (void *); +extern size_t ggc_round_alloc_size (size_t requested_size); +extern void *ggc_realloc (void *, size_t MEM_STAT_DECL); /* Templated vector type and associated interfaces. @@ -205,6 +182,8 @@ along with GCC; see the file COPYING3. If not see /* Support function for statistics. */ extern void dump_vec_loc_statistics (void); +/* Hashtable mapping vec addresses to descriptors. */ +extern htab_t vec_mem_usage_hash; /* Control data for vectors. This contains the number of allocated and used slots inside a vector. */ @@ -215,9 +194,10 @@ struct vec_prefix 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); + void register_overhead (void *, size_t, size_t CXX_MEM_STAT_INFO); + void release_overhead (void *, size_t, bool CXX_MEM_STAT_INFO); 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., @@ -233,10 +213,25 @@ struct vec_prefix friend struct va_heap; unsigned m_alloc : 31; - unsigned m_has_auto_buf : 1; + 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 struct vec; /* Valid vector layouts @@ -274,7 +269,7 @@ struct va_heap /* 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. */ + allocated and RESERVE is 0, no vector will be created. */ template inline void @@ -283,10 +278,10 @@ va_heap::reserve (vec *&v, unsigned reserve, bool exact { unsigned alloc = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact); - gcc_assert (alloc); + gcc_checking_assert (alloc); if (GATHER_STATISTICS && v) - v->m_vecpfx.release_overhead (); + v->m_vecpfx.release_overhead (v, v->allocated (), false); size_t size = vec::embedded_size (alloc); unsigned nelem = v ? v->length () : 0; @@ -294,7 +289,7 @@ va_heap::reserve (vec *&v, unsigned reserve, bool exact v->embedded_init (alloc, nelem); if (GATHER_STATISTICS) - v->m_vecpfx.register_overhead (size FINAL_PASS_MEM_STAT); + v->m_vecpfx.register_overhead (v, alloc, nelem PASS_MEM_STAT); } @@ -308,7 +303,7 @@ va_heap::release (vec *&v) return; if (GATHER_STATISTICS) - v->m_vecpfx.release_overhead (); + v->m_vecpfx.release_overhead (v, v->allocated (), true); ::free (v); v = NULL; } @@ -349,7 +344,7 @@ va_gc::release (vec *&v) /* 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. */ + allocated and RESERVE is 0, no vector will be created. */ template void @@ -380,7 +375,7 @@ va_gc::reserve (vec *&v, unsigned reserve, bool exact size = vec_offset + alloc * elt_size; unsigned nelem = v ? v->length () : 0; - v = static_cast *> (::ggc_realloc_stat (v, size + v = static_cast *> (::ggc_realloc (v, size PASS_MEM_STAT)); v->embedded_init (alloc, nelem); } @@ -412,14 +407,36 @@ struct GTY((user)) vec { }; +/* Default-construct N elements in DST. */ + +template +inline void +vec_default_construct (T *dst, unsigned n) +{ + for ( ; n; ++dst, --n) + ::new (static_cast(dst)) T (); +} + +/* Copy-construct N elements in DST from *SRC. */ + +template +inline void +vec_copy_construct (T *dst, const T *src, unsigned n) +{ + for ( ; n; ++dst, ++src, --n) + ::new (static_cast(dst)) T (*src); +} + /* Type to provide NULL values for vec. 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. */ + a vec instance, you can assign it the value vNULL. This isn't + needed for file-scope and function-local static vectors, which + are zero-initialized by default. */ struct vnull { template - operator vec () { return vec(); } + CONSTEXPR operator vec () { return vec(); } }; extern vnull vNULL; @@ -459,6 +476,10 @@ public: 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; } + T *begin () { return address (); } + const T *begin () const { return address (); } + T *end () { return address () + length (); } + const T *end () const { return address () + length (); } const T &operator[] (unsigned) const; T &operator[] (unsigned); T &last (void); @@ -466,8 +487,8 @@ public: 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); + void splice (const vec &); + void splice (const vec *src); T *quick_push (const T &); T &pop (void); void truncate (unsigned); @@ -476,9 +497,11 @@ public: 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 contains (const T &search) const; static size_t embedded_size (unsigned); - void embedded_init (unsigned, unsigned = 0); + void embedded_init (unsigned, unsigned = 0, unsigned = 0); void quick_grow (unsigned len); void quick_grow_cleared (unsigned len); @@ -546,7 +569,6 @@ vec_safe_is_empty (vec *v) return v ? v->is_empty () : true; } - /* If V does not have space for NELEMS elements, call V->reserve(NELEMS, EXACT). */ template @@ -610,7 +632,7 @@ vec_safe_grow_cleared (vec *&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)); + vec_default_construct (v->address () + oldlen, len - oldlen); } @@ -678,16 +700,16 @@ vec_safe_truncate (vec *v, unsigned size) /* If SRC is not NULL, return a pointer to a copy of it. */ template inline vec * -vec_safe_copy (vec *src) +vec_safe_copy (vec *src CXX_MEM_STAT_INFO) { - return src ? src->copy () : NULL; + 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 inline void -vec_safe_splice (vec *&dst, vec *src +vec_safe_splice (vec *&dst, const vec *src CXX_MEM_STAT_INFO) { unsigned src_len = vec_safe_length (src); @@ -699,6 +721,15 @@ vec_safe_splice (vec *&dst, vec *src } } +/* Return true if SEARCH is an element of V. Note that this is O(N) in the + size of the vector and so should be used with care. */ + +template +inline bool +vec_safe_contains (vec *v, const T &search) +{ + return v ? v->contains (search) : false; +} /* Index into vector. Return the IX'th element. IX must be in the domain of the vector. */ @@ -807,7 +838,7 @@ vec::copy (ALONE_MEM_STAT_DECL) const { vec_alloc (new_vec, len PASS_MEM_STAT); new_vec->embedded_init (len, len); - memcpy (new_vec->address (), m_vecdata, sizeof (T) * len); + vec_copy_construct (new_vec->address (), m_vecdata, len); } return new_vec; } @@ -818,20 +849,20 @@ vec::copy (ALONE_MEM_STAT_DECL) const template inline void -vec::splice (vec &src) +vec::splice (const vec &src) { unsigned len = src.length (); if (len) { gcc_checking_assert (space (len)); - memcpy (address () + length (), src.address (), len * sizeof (T)); + vec_copy_construct (end (), src.address (), len); m_vecpfx.m_num += len; } } template inline void -vec::splice (vec *src) +vec::splice (const vec *src) { if (src) splice (*src); @@ -938,10 +969,60 @@ template inline void vec::qsort (int (*cmp) (const void *, const void *)) { - ::qsort (address (), length (), sizeof (T), cmp); + 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 +inline T * +vec::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(p); + } + + return NULL; +} + +/* Return true if SEARCH is an element of V. Note that this is O(N) in the + size of the vector and so should be used with care. */ + +template +inline bool +vec::contains (const T &search) const +{ + unsigned int len = length (); + for (unsigned int i = 0; i < len; i++) + if ((*this)[i] == search) + return true; + + return false; +} + /* 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 @@ -1000,10 +1081,10 @@ vec::embedded_size (unsigned alloc) template inline void -vec::embedded_init (unsigned alloc, unsigned num) +vec::embedded_init (unsigned alloc, unsigned num, unsigned aut) { m_vecpfx.m_alloc = alloc; - m_vecpfx.m_has_auto_buf = 0; + m_vecpfx.m_using_auto_storage = aut; m_vecpfx.m_num = num; } @@ -1028,11 +1109,12 @@ inline void vec::quick_grow_cleared (unsigned len) { unsigned oldlen = length (); + size_t growby = len - oldlen; quick_grow (len); - memset (&(address ()[oldlen]), 0, sizeof (T) * (len - oldlen)); + if (growby != 0) + vec_default_construct (address () + oldlen, growby); } - /* Garbage collection support for vec. */ template @@ -1135,6 +1217,10 @@ public: const T *address (void) const { return m_vec ? m_vec->m_vecdata : NULL; } + T *begin () { return address (); } + const T *begin () const { return address (); } + T *end () { return begin () + length (); } + const T *end () const { return begin () + length (); } const T &operator[] (unsigned ix) const { return (*m_vec)[ix]; } @@ -1158,8 +1244,8 @@ public: 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); + void splice (const vec &); + void safe_splice (const vec & CXX_MEM_STAT_INFO); T *quick_push (const T &); T *safe_push (const T &CXX_MEM_STAT_INFO); T &pop (void); @@ -1174,7 +1260,9 @@ public: 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 contains (const T &search) const; bool using_auto_storage () const; @@ -1196,10 +1284,20 @@ class auto_vec : public vec public: auto_vec () { - m_header.m_alloc = N; - m_header.m_has_auto_buf = 1; - m_header.m_num = 0; - this->m_vec = reinterpret_cast *> (&m_header); + m_auto.embedded_init (MAX (N, 2), 0, 1); + this->m_vec = &m_auto; + } + + auto_vec (size_t s) + { + if (s > N) + { + this->create (s); + return; + } + + m_auto.embedded_init (MAX (N, 2), 0, 1); + this->m_vec = &m_auto; } ~auto_vec () @@ -1208,10 +1306,8 @@ public: } private: - friend class vec; - - vec_prefix m_header; - T m_data[N]; + vec m_auto; + T m_data[MAX (N - 1, 1)]; }; /* auto_vec is a sub class of vec whose storage is released when it is @@ -1358,7 +1454,7 @@ template inline bool vec::reserve (unsigned nelems, bool exact MEM_STAT_DECL) { - if (!nelems || space (nelems)) + if (space (nelems)) return false; /* For now play a game with va_heap::reserve to hide our auto storage if any, @@ -1377,7 +1473,7 @@ vec::reserve (unsigned nelems, bool exact MEM_STAT_DECL) va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT); if (handle_auto_vec) { - memcpy (m_vec->address (), oldvec->address (), sizeof (T) * oldsize); + vec_copy_construct (m_vec->address (), oldvec->address (), oldsize); m_vec->m_vecpfx.m_num = oldsize; } @@ -1424,7 +1520,7 @@ vec::release (void) if (using_auto_storage ()) { - static_cast *> (this)->m_header.m_num = 0; + m_vec->m_vecpfx.m_num = 0; return; } @@ -1438,7 +1534,7 @@ vec::release (void) template inline void -vec::splice (vec &src) +vec::splice (const vec &src) { if (src.m_vec) m_vec->splice (*(src.m_vec)); @@ -1452,7 +1548,7 @@ vec::splice (vec &src) template inline void -vec::safe_splice (vec &src +vec::safe_splice (const vec &src MEM_STAT_DECL) { if (src.length ()) @@ -1523,7 +1619,10 @@ vec::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); + if (m_vec) + m_vec->quick_grow (len); + else + gcc_checking_assert (len == 0); } @@ -1536,8 +1635,10 @@ inline void vec::safe_grow_cleared (unsigned len MEM_STAT_DECL) { unsigned oldlen = length (); + size_t growby = len - oldlen; safe_grow (len PASS_MEM_STAT); - memset (&(address ()[oldlen]), 0, sizeof (T) * (len - oldlen)); + if (growby != 0) + vec_default_construct (address () + oldlen, growby); } @@ -1635,6 +1736,20 @@ vec::qsort (int (*cmp) (const void *, const void *)) } +/* Search the contents of the sorted vector with a binary search. + CMP is the comparison function to pass to bsearch. */ + +template +inline T * +vec::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 @@ -1649,16 +1764,33 @@ vec::lower_bound (T obj, return m_vec ? m_vec->lower_bound (obj, lessthan) : 0; } +/* Return true if SEARCH is an element of V. Note that this is O(N) in the + size of the vector and so should be used with care. */ + +template +inline bool +vec::contains (const T &search) const +{ + return m_vec ? m_vec->contains (search) : false; +} + template inline bool vec::using_auto_storage () const { - if (!m_vec->m_vecpfx.m_has_auto_buf) - return false; + return m_vec->m_vecpfx.m_using_auto_storage; +} + +/* Release VEC and call release of all element vectors. */ + +template +inline void +release_vec_vec (vec > &vec) +{ + for (unsigned i = 0; i < vec.length (); i++) + vec[i].release (); - const vec_prefix *auto_header - = &static_cast *> (this)->m_header; - return reinterpret_cast (m_vec) == auto_header; + vec.release (); } #if (GCC_VERSION >= 3000)