This patch rewrites the old VEC macro-based interface into a new one

based on the template class 'vec'.  The user-visible changes are
described in http://gcc.gnu.org/wiki/cxx-conversion/cxx-vec.

I have tested the patch pretty extensively:

- Regular bootstraps on x86_64, ppc, ia64, sparc and hppa.
- Bootstraps with --enable-checking=release
- Bootstraps with --enable-checking=gc,gcac
- Basic builds on all targets (using contrib/config-list.mk).

We no longer access the vectors via VEC_* macros.  The pattern is
"VEC_operation (T, A, V, args)" becomes "V.operation (args)".

The only thing I could not do is create proper ctors and dtors for the
vec class.  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<type, allocation, layout>::create() and another vec<type,
allocation, layout>::destroy() to allocate the internal vector.

For vectors that must be pointers, there is a family of free functions
that implement the operations that need to tolerate NULL vectors.
These functions all start with the prefix 'vec_safe_'.  See the wiki
page for details.

The gengtype change removes the special handling for VEC() that used
to exist in gengtype. Additionally, it allows gengtype to recognize
templates of more than one argument and introduces the concept of an
undefined type (useful for template arguments that may or may not be
types).

When a TYPE_UNDEFINED is reached, gengtype will ignore it if it
happens inside a type marked with GTY((user)).  Otherwise, it will
emit an error.

Finally, gengtype rejects root types marked GTY((user)) that are not
first class pointers.

2012-11-16  Diego Novillo  <dnovillo@google.com>

	VEC API overhaul (http://gcc.gnu.org/wiki/cxx-conversion/cxx-vec)

	* vec.c (register_overhead): Convert it into
	member function of vec_prefix.
	(release_overhead): Likewise.
	(calculate_allocation): Likewise.
	(vec_heap_free): Remove.
	(vec_gc_o_reserve_1): Remove.
	(vec_heap_o_reserve_1): Remove.
	(vec_stack_o_reserve_1): Remove.
	(vec_stack_o_reserve_exact): Remove.
	(register_stack_vec): New.
	(stack_vec_register_index): New.
	(unregister_stack_vec): New.
	(vec_assert_fail): Remove.
	* vec.h: Conditionally include ggc.h.  Document conditional
	hackery.
	Update top-level documentation.
	(ALONE_VEC_CHECK_INFO): Remove.
	(VEC_CHECK_INFO): Remove.
	(ALONE_VEC_CHECK_DECL): Remove.
	(VEC_CHECK_DECL): Remove.
	(ALONE_VEC_CHECK_PASS): Remove.
	(VEC_CHECK_PASS): Remove.
	(VEC_ASSERT): Remove.
	(vec_prefix): Add friends va_gc, va_gc_atomic, va_heap and
	va_stack.
	Mark fields alloc_ and num_ as protected.
	(struct vec_t): Remove.  Remove all function members.
	(struct vl_embed): Declare.
	(struct vl_ptr): Declare.
	(free): Remove.
	(reserve_exact): Remove.
	(reserve): Remove.
	(safe_splice): Remove.
	(safe_push): Remove.
	(safe_grow): Remove.
	(safe_grow_cleared): Remove.
	(safe_insert): Remove.
	(DEF_VEC_I): Remove.
	(DEF_VEC_ALLOC_I): Remove.
	(DEF_VEC_P): Remove.
	(DEF_VEC_ALLOC_P): Remove.
	(DEF_VEC_O): Remove.
	(DEF_VEC_ALLOC_O): Remove.
	(DEF_VEC_ALLOC_P_STACK): Remove.
	(DEF_VEC_ALLOC_O_STACK): Remove.
	(DEF_VEC_ALLOC_I_STACK): Remove.
	(DEF_VEC_A): Remove.
	(DEF_VEC_ALLOC_A): Remove.
	(vec_stack_p_reserve_exact_1): Remove.
	(vec_stack_o_reserve): Remove.
	(vec_stack_o_reserve_exact): Remove.
	(VEC_length): Remove.
	(VEC_empty): Remove.
	(VEC_address): Remove.
	(vec_address): Remove.
	(VEC_last): Remove.
	(VEC_index): Remove.
	(VEC_iterate): Remove.
	(VEC_embedded_size): Remove.
	(VEC_embedded_init): Remove.
	(VEC_free): Remove.
	(VEC_copy): Remove.
	(VEC_space): Remove.
	(VEC_reserve): Remove.
	(VEC_reserve_exact): Remove.
	(VEC_splice): Remove.
	(VEC_safe_splice): Remove.
	(VEC_quick_push): Remove.
	(VEC_safe_push): Remove.
	(VEC_pop): Remove.
	(VEC_truncate): Remove.
	(VEC_safe_grow): Remove.
	(VEC_replace): Remove.
	(VEC_quick_insert): Remove.
	(VEC_safe_insert): Remove.
	(VEC_ordered_remove): Remove.
	(VEC_unordered_remove): Remove.
	(VEC_block_remove): Remove.
	(VEC_lower_bound): Remove.
	(VEC_alloc): Remove.
	(VEC_qsort): Remove.

	(va_heap): Declare.
	(va_heap::default_layout): New typedef to vl_ptr.
	(va_heap::reserve): New.
	(va_heap::release): New.
	(va_gc): Declare.
	(va_gc::default_layout): New typedef to vl_embed.
	(va_gc::reserve): New.
	(va_gc::release): New.
	(va_gc_atomic): Declare.  Inherit from va_gc.
	(va_stack): Declare.
	(va_stack::default_layout): New typedef to vl_ptr.
	(va_stack::alloc): New.
	(va_stack::reserve): New.
	(va_stack::release): New.
	(register_stack_vec): Declare.
	(stack_vec_register_index): Declare.
	(unregister_stack_vec): Declare.

	(vec<T, A = va_heap, L = typename A::default_layout>): Declare
	empty vec template.
	(vec<T, A, vl_embed>): Partial specialization for embedded
	layout.
	(vec<T, A, vl_embed>::allocated): New.
	(vec<T, A, vl_embed>::length): New.
	(vec<T, A, vl_embed>::is_empty): New.
	(vec<T, A, vl_embed>::address): New.
	(vec<T, A, vl_embed>::operator[]): New.
	(vec<T, A, vl_embed>::last New.
	(vec<T, A, vl_embed>::space): New.
	(vec<T, A, vl_embed>::iterate): New.
	(vec<T, A, vl_embed>::iterate): New.
	(vec<T, A, vl_embed>::copy): New.
	(vec<T, A, vl_embed>::splice): New.
	(vec<T, A, vl_embed>::quick_push New.
	(vec<T, A, vl_embed>::pop New.
	(vec<T, A, vl_embed>::truncate): New.
	(vec<T, A, vl_embed>::quick_insert): New.
	(vec<T, A, vl_embed>::ordered_remove): New.
	(vec<T, A, vl_embed>::unordered_remove): New.
	(vec<T, A, vl_embed>::block_remove): New.
	(vec<T, A, vl_embed>::qsort): New.
	(vec<T, A, vl_embed>::lower_bound): New.
	(vec<T, A, vl_embed>::embedded_size): New.
	(vec<T, A, vl_embed>::embedded_init): New.
	(vec<T, A, vl_embed>::quick_grow): New.
	(vec<T, A, vl_embed>::quick_grow_cleared): New.
	(vec_safe_space): New.
	(vec_safe_length): New.
	(vec_safe_address): New.
	(vec_safe_is_empty): New.
	(vec_safe_reserve): New.
	(vec_safe_reserve_exact): New.
	(vec_alloc): New.
	(vec_free): New.
	(vec_safe_grow): New.
	(vec_safe_grow_cleared): New.
	(vec_safe_iterate): New.
	(vec_safe_push): New.
	(vec_safe_insert): New.
	(vec_safe_truncate): New.
	(vec_safe_copy): New.
	(vec_safe_splice): New.

	(vec<T, A, vl_ptr>): New partial specialization for the space
	efficient layout.
	(vec<T, A, vl_ptr>::exists): New.
	(vec<T, A, vl_ptr>::is_empty): New.
	(vec<T, A, vl_ptr>::length): New.
	(vec<T, A, vl_ptr>::address): New.
	(vec<T, A, vl_ptr>::operator[]): New.
	(vec<T, A, vl_ptr>::operator!=): New.
	(vec<T, A, vl_ptr>::operator==): New.
	(vec<T, A, vl_ptr>::last): New.
	(vec<T, A, vl_ptr>::space): New.
	(vec<T, A, vl_ptr>::iterate): New.
	(vec<T, A, vl_ptr>::copy): New.
	(vec<T, A, vl_ptr>::reserve): New.
	(vec<T, A, vl_ptr>::reserve_exact): New.
	(vec<T, A, vl_ptr>::splice): New.
	(vec<T, A, vl_ptr>::safe_splice): New.
	(vec<T, A, vl_ptr>::quick_push): New.
	(vec<T, A, vl_ptr>::safe_push): New.
	(vec<T, A, vl_ptr>::pop): New.
	(vec<T, A, vl_ptr>::truncate): New.
	(vec<T, A, vl_ptr>::safe_grow): New.
	(vec<T, A, vl_ptr>::safe_grow_cleared): New.
	(vec<T, A, vl_ptr>::quick_grow): New.
	(vec<T, A, vl_ptr>::quick_grow_cleared): New.
	(vec<T, A, vl_ptr>::quick_insert): New.
	(vec<T, A, vl_ptr>::safe_insert): New.
	(vec<T, A, vl_ptr>::ordered_remove): New.
	(vec<T, A, vl_ptr>::unordered_remove): New.
	(vec<T, A, vl_ptr>::block_remove): New.
	(vec<T, A, vl_ptr>::qsort): New.
	(vec<T, A, vl_ptr>::lower_bound): New.
	(vec_stack_alloc): Define.
	(FOR_EACH_VEC_SAFE_ELT): Define.
	* vecir.h: Remove.  Update all users.
	* vecprim.h: Remove.  Update all users.
	Move uchar to coretypes.h.

	* Makefile.in (VEC_H): Add $(GGC_H).
	Remove vecir.h and vecprim.h dependencies everywhere.

2012-11-16  Diego Novillo  <dnovillo@google.com>

	* gengtype-lex.l (VEC): Remove.
	Add characters in the set [\!\>\.-].
	* gengtype-parse.c (token_names): Remove "VEC".
	(require_template_declaration): Remove handling of VEC_TOKEN.
	(type): Likewise.
	Call create_user_defined_type when parsing GTY((user)).
	* gengtype-state.c (type_lineloc): handle TYPE_UNDEFINED.
	(write_state_undefined_type): New.
	(write_state_type): Call write_state_undefined_type for
	TYPE_UNDEFINED.
	(read_state_type): Call read_state_undefined_type for
	TYPE_UNDEFINED.
	* gengtype.c (dbgprint_count_type_at): Handle TYPE_UNDEFINED.
	(create_user_defined_type): Make extern.
	(type_for_name): Factor out of resolve_typedef.
	(create_undefined_type): New
	(resolve_typedef): Call it when we cannot find a previous
	typedef and the type is not a template.
	(find_structure): Accept TYPE_UNDEFINED.
	(set_gc_used_type): Add argument ALLOWED_UNDEFINED_TYPES,
	default to false.
	Emit an error for TYPE_UNDEFINED unless LEVEL is GC_UNUSED or
	ALLOWED_UNDEFINED_TYPES is set.
	Set ALLOWED_UNDEFINED_TYPES to true for TYPE_USER_STRUCT.
	(filter_type_name): Accept templates with more than one
	argument.
	(output_mangled_typename): Handle TYPE_UNDEFINED
	(walk_type): Likewise.
	(write_types_process_field): Likewise.
	(write_func_for_structure): If CHAIN_NEXT is set, ORIG_S
	should not be a user-defined type.
	(write_types_local_user_process_field): Handle TYPE_ARRAY,
	TYPE_NONE and TYPE_UNDEFINED.
	(write_types_local_process_field): Likewise.
	(contains_scalar_p): Return 0 for TYPE_USER_STRUCT.
	(write_root): Reject user-defined types that are not pointers.
	Handle TYPE_NONE, TYPE_UNDEFINED, TYPE_UNION, TYPE_LANG_STRUCT
	and TYPE_PARAM_STRUCT.
	(output_typename): Handle TYPE_NONE, TYPE_UNDEFINED, and
	TYPE_ARRAY.
	(dump_typekind): Handle TYPE_UNDEFINED.
	* gengtype.h (enum typekind): Add TYPE_UNDEFINED.
	(create_user_defined_type): Declare.
	(enum gty_token): Remove VEC_TOKEN.

2012-11-16  Diego Novillo  <dnovillo@google.com>

	Adjust for new vec API (http://gcc.gnu.org/wiki/cxx-conversion/cxx-vec)

	* coretypes.h (uchar): Define.
	* alias.c: Use new vec API in vec.h.
	* asan.c: Likewise.
	* attribs.c: Likewise.
	* basic-block.h: Likewise.
	* bb-reorder.c: Likewise.
	* builtins.c: Likewise.
	* calls.c: Likewise.
	* cfg.c: Likewise.
	* cfganal.c: Likewise.
	* cfgcleanup.c: Likewise.
	* cfgexpand.c: Likewise.
	* cfghooks.c: Likewise.
	* cfghooks.h: Likewise.
	* cfgloop.c: Likewise.
	* cfgloop.h: Likewise.
	* cfgloopanal.c: Likewise.
	* cfgloopmanip.c: Likewise.
	* cfgrtl.c: Likewise.
	* cgraph.c: Likewise.
	* cgraph.h: Likewise.
	* cgraphclones.c: Likewise.
	* cgraphunit.c: Likewise.
	* combine.c: Likewise.
	* compare-elim.c: Likewise.
	* coverage.c: Likewise.
	* cprop.c: Likewise.
	* data-streamer.h: Likewise.
	* dbxout.c: Likewise.
	* dce.c: Likewise.
	* df-core.c: Likewise.
	* df-problems.c: Likewise.
	* df-scan.c: Likewise.
	* dominance.c: Likewise.
	* domwalk.c: Likewise.
	* domwalk.h: Likewise.
	* dse.c: Likewise.
	* dwarf2cfi.c: Likewise.
	* dwarf2out.c: Likewise.
	* dwarf2out.h: Likewise.
	* emit-rtl.c: Likewise.
	* except.c: Likewise.
	* except.h: Likewise.
	* expr.c: Likewise.
	* expr.h: Likewise.
	* final.c: Likewise.
	* fold-const.c: Likewise.
	* function.c: Likewise.
	* function.h: Likewise.
	* fwprop.c: Likewise.
	* gcc.c: Likewise.
	* gcse.c: Likewise.
	* genattr.c: Likewise.
	* genattrtab.c: Likewise.
	* genautomata.c: Likewise.
	* genextract.c: Likewise.
	* genopinit.c: Likewise
	* ggc-common.c: Likewise.
	* ggc.h: Likewise.
	* gimple-low.c: Likewise.
	* gimple-ssa-strength-reduction.c: Likewise.
	* gimple-streamer-in.c: Likewise.
	* gimple.c: Likewise.
	* gimple.h: Likewise.
	* gimplify.c: Likewise.
	* graph.c: Likewise.
	* graphds.c: Likewise.
	* graphds.h: Likewise.
	* graphite-blocking.c: Likewise.
	* graphite-clast-to-gimple.c: Likewise.
	* graphite-dependences.c: Likewise.
	* graphite-interchange.c: Likewise.
	* graphite-optimize-isl.c: Likewise.
	* graphite-poly.c: Likewise.
	* graphite-poly.h: Likewise.
	* graphite-scop-detection.c: Likewise.
	* graphite-scop-detection.h: Likewise.
	* graphite-sese-to-poly.c: Likewise.
	* graphite.c: Likewise.
	* godump.c: Likewise.
	* haifa-sched.c: Likewise.
	* hw-doloop.c: Likewise.
	* hw-doloop.h: Likewise.
	* ifcvt.c: Likewise.
	* insn-addr.h: Likewise.
	* ipa-cp.c: Likewise.
	* ipa-inline-analysis.c: Likewise.
	* ipa-inline-transform.c: Likewise.
	* ipa-inline.c: Likewise.
	* ipa-inline.h: Likewise.
	* ipa-prop.c: Likewise.
	* ipa-prop.h: Likewise.
	* ipa-pure-const.c: Likewise.
	* ipa-ref-inline.h: Likewise.
	* ipa-ref.c: Likewise.
	* ipa-ref.h: Likewise.
	* ipa-reference.c: Likewise.
	* ipa-split.c: Likewise.
	* ipa-utils.c: Likewise.
	* ipa-utils.h: Likewise.
	* ipa.c: Likewise.
	* ira-build.c: Likewise.
	* ira-color.c: Likewise.
	* ira-emit.c: Likewise.
	* ira-int.h: Likewise.
	* ira.c: Likewise.
	* loop-invariant.c: Likewise.
	* loop-unroll.c: Likewise.
	* lower-subreg.c: Likewise.
	* lra-lives.c: Likewise.
	* lra.c: Likewise.
	* lto-cgraph.c: Likewise.
	* lto-section-out.c: Likewise.
	* lto-streamer-in.c: Likewise.
	* lto-streamer-out.c: Likewise.
	* lto-streamer.h: Likewise.
	* lto-symtab.c: Likewise.
	* mcf.c: Likewise.
	* modulo-sched.c: Likewise.
	* omp-low.c: Likewise.
	* opts-common.c: Likewise.
	* opts-global.c: Likewise.
	* opts.c: Likewise.
	* opts.h: Likewise.
	* passes.c: Likewise.
	* predict.c: Likewise.
	* print-tree.c: Likewise.
	* profile.c: Likewise.
	* profile.h: Likewise.
	* read-rtl.c: Likewise.
	* ree.c: Likewise.
	* reg-stack.c: Likewise.
	* regrename.c: Likewise.
	* regrename.h: Likewise.
	* reload.c: Likewise.
	* reload.h: Likewise.
	* reload1.c: Likewise.
	* rtl.h: Likewise.
	* sched-deps.c: Likewise.
	* sched-int.h: Likewise.
	* sdbout.c: Likewise.
	* sel-sched-dump.c: Likewise.
	* sel-sched-ir.c: Likewise.
	* sel-sched-ir.h: Likewise.
	* sel-sched.c: Likewise.
	* sese.c: Likewise.
	* sese.h: Likewise.
	* statistics.h: Likewise.
	* stmt.c: Likewise.
	* stor-layout.c: Likewise.
	* store-motion.c: Likewise.
	* tlink.c: Likewise.
	* toplev.c: Likewise.
	* trans-mem.c: Likewise.
	* tree-browser.c: Likewise.
	* tree-call-cdce.c: Likewise.
	* tree-cfg.c: Likewise.
	* tree-cfgcleanup.c: Likewise.
	* tree-chrec.c: Likewise.
	* tree-chrec.h: Likewise.
	* tree-complex.c: Likewise.
	* tree-data-ref.c: Likewise.
	* tree-data-ref.h: Likewise.
	* tree-dfa.c: Likewise.
	* tree-diagnostic.c: Likewise.
	* tree-dump.c: Likewise.
	* tree-eh.c: Likewise.
	* tree-emutls.c: Likewise.
	* tree-flow.h: Likewise.
	* tree-if-conv.c: Likewise.
	* tree-inline.c: Likewise.
	* tree-inline.h: Likewise.
	* tree-into-ssa.c: Likewise.
	* tree-iterator.c: Likewise.
	* tree-loop-distribution.c: Likewise.
	* tree-mudflap.c: Likewise.
	* tree-optimize.c: Likewise.
	* tree-outof-ssa.c: Likewise.
	* tree-parloops.c: Likewise.
	* tree-phinodes.c: Likewise.
	* tree-predcom.c: Likewise.
	* tree-pretty-print.c: Likewise.
	* tree-scalar-evolution.c: Likewise.
	* tree-sra.c: Likewise.
	* tree-ssa-address.c: Likewise.
	* tree-ssa-alias.c: Likewise.
	* tree-ssa-ccp.c: Likewise.
	* tree-ssa-coalesce.c: Likewise.
	* tree-ssa-dce.c: Likewise.
	* tree-ssa-dom.c: Likewise.
	* tree-ssa-forwprop.c: Likewise.
	* tree-ssa-live.c: Likewise.
	* tree-ssa-live.h: Likewise.
	* tree-ssa-loop-im.c: Likewise.
	* tree-ssa-loop-ivcanon.c: Likewise.
	* tree-ssa-loop-ivopts.c: Likewise.
	* tree-ssa-loop-manip.c: Likewise.
	* tree-ssa-loop-niter.c: Likewise.
	* tree-ssa-loop-prefetch.c: Likewise.
	* tree-ssa-math-opts.c: Likewise.
	* tree-ssa-operands.c: Likewise.
	* tree-ssa-phiopt.c: Likewise.
	* tree-ssa-phiprop.c: Likewise.
	* tree-ssa-pre.c: Likewise.
	* tree-ssa-propagate.c: Likewise.
	* tree-ssa-reassoc.c: Likewise.
	* tree-ssa-sccvn.c: Likewise.
	* tree-ssa-sccvn.h: Likewise.
	* tree-ssa-strlen.c: Likewise.
	* tree-ssa-structalias.c: Likewise.
	* tree-ssa-tail-merge.c: Likewise.
	* tree-ssa-threadedge.c: Likewise.
	* tree-ssa-threadupdate.c: Likewise.
	* tree-ssa-uncprop.c: Likewise.
	* tree-ssa-uninit.c: Likewise.
	* tree-ssa.c: Likewise.
	* tree-ssanames.c: Likewise.
	* tree-stdarg.c: Likewise.
	* tree-streamer-in.c: Likewise.
	* tree-streamer-out.c: Likewise.
	* tree-streamer.c: Likewise.
	* tree-streamer.h: Likewise.
	* tree-switch-conversion.c: Likewise.
	* tree-vect-data-refs.c: Likewise.
	* tree-vect-generic.c: Likewise.
	* tree-vect-loop-manip.c: Likewise.
	* tree-vect-loop.c: Likewise.
	* tree-vect-patterns.c: Likewise.
	* tree-vect-slp.c: Likewise.
	* tree-vect-stmts.c: Likewise.
	* tree-vectorizer.c: Likewise.
	* tree-vectorizer.h: Likewise.
	* tree-vrp.c: Likewise.
	* tree.c: Likewise.
	* tree.h: Likewise.
	* value-prof.c: Likewise.
	* value-prof.h: Likewise.
	* var-tracking.c: Likewise.
	* varasm.c: Likewise.
	* varpool.c: Likewise.
	* vmsdbgout.c: Likewise.
	* config/bfin/bfin.c: Likewise.
	* config/c6x/c6x.c: Likewise.
	* config/darwin.c: Likewise.
	* config/i386/i386.c: Likewise.
	* config/ia64/ia64.c: Likewise.
	* config/mep/mep.c: Likewise.
	* config/mips/mips.c: Likewise.
	* config/pa/pa.c: Likewise.
	* config/rs6000/rs6000-c.c: Likewise.
	* config/rs6000/rs6000.c: Likewise.
	* config/rx/rx.c: Likewise.
	* config/spu/spu-c.c: Likewise.
	* config/vms/vms.c: Likewise.
	* config/vxworks.c: Likewise.
	* config/epiphany/resolve-sw-modes.c: Likewise.

git-svn-id: https://gcc.gnu.org/svn/gcc/trunk@193595 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 1309 insertions, 648 deletions

diff --git a/gcc/vec.h b/gcc/vec.h
index 8858f6afea1..b9be85c293a 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -23,7 +23,39 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_VEC_H
 #define GCC_VEC_H
 
-#include "statistics.h"		/* For MEM_STAT_DECL.  */
+/* 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_internal_cleared_alloc_stat (size_t MEM_STAT_DECL)
+    ATTRIBUTE_MALLOC;
+  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.
 
@@ -37,18 +69,6 @@ along with GCC; see the file COPYING3.  If not see
    reference.  Because the iterator will be inlined, the address-of
    can be optimized away.
 
-   The 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
-   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 probably not be resizeable (so
-   don't use the 'safe' allocation variants).  The trailing array
-   idiom is used (rather than a pointer to an array of data), because,
-   if we allow NULL to also represent an empty vector, empty vectors
-   occupy minimal space in the structure containing them.
-
    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
@@ -75,438 +95,745 @@ along with GCC; see the file COPYING3.  If not see
    'lower_bound' function will determine where to place an item in the
    array using insert that will maintain sorted order.
 
-   When a vector type is defined, first a non-memory managed version
-   is created.  You can then define either or both garbage collected
-   and heap allocated versions.  The allocation mechanism is specified
-   when the vector is allocated.  This can occur via the VEC_alloc
-   call or one of the VEC_safe_* functions that add elements to a
-   vector.  If the vector is NULL, it will be allocated using the
-   allocation strategy selected in the call.  The valid allocations
-   are defined in enum vec_allocation_t.
+   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.
 
-   Variables of vector type are of type vec_t<ETYPE> where ETYPE is
-   the type of the elements of the vector. Due to the way GTY works,
-   you must annotate any structures you wish to insert or reference
-   from a vector with a GTY(()) tag.  You need to do this even if you
-   never use the GC allocated variants.
+   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 {
-     vec_t<tree> *v;      // A (pointer to) a vector of tree pointers.
+     // A space-efficient vector of tree pointers in GC memory.
+     vec<tree, va_gc, vl_ptr> v;
    };
 
    struct my_struct *s;
 
-   if (VEC_length(tree,s->v)) { we have some contents }
-   VEC_safe_push(tree,gc,s->v,decl); // append some decl onto the end
-   for (ix = 0; VEC_iterate(tree,s->v,ix,elt); ix++)
+   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 }
 */
 
-#if ENABLE_CHECKING
-#define ALONE_VEC_CHECK_INFO __FILE__, __LINE__, __FUNCTION__
-#define VEC_CHECK_INFO , ALONE_VEC_CHECK_INFO
-#define ALONE_VEC_CHECK_DECL const char *file_, unsigned line_, const char *function_
-#define VEC_CHECK_DECL , ALONE_VEC_CHECK_DECL
-#define ALONE_VEC_CHECK_PASS file_, line_, function_
-#define VEC_CHECK_PASS , ALONE_VEC_CHECK_PASS
-
-#define VEC_ASSERT(EXPR,OP,T,A) \
-  (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
-
-extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
-     ATTRIBUTE_NORETURN;
-#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
-#else
-#define ALONE_VEC_CHECK_INFO
-#define VEC_CHECK_INFO
-#define ALONE_VEC_CHECK_DECL void
-#define VEC_CHECK_DECL
-#define ALONE_VEC_CHECK_PASS
-#define VEC_CHECK_PASS
-#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
-#endif
+/* Support function for statistics.  */
+extern void dump_vec_loc_statistics (void);
 
-#define VEC(T,A) vec_t<T>
 
-enum vec_allocation_t { heap, gc, stack };
+/* Control data for vectors.  This contains the number of allocated
+   and used slots inside a vector.  */
 
-struct vec_prefix
+class vec_prefix
 {
-  unsigned num_;
+protected:
+  /* 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 class 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_;
 };
 
-/* Vector type, user visible.  */
-template<typename T>
-struct GTY(()) vec_t
-{
-  unsigned length (void) const;
-  bool empty (void) const;
-  T *address (void);
-  T &last (ALONE_VEC_CHECK_DECL);
-  const T &operator[] (unsigned) const;
-  T &operator[] (unsigned);
-  void embedded_init (int, int = 0);
-
-  template<enum vec_allocation_t A>
-  vec_t<T> *copy (ALONE_MEM_STAT_DECL);
-
-  bool space (int VEC_CHECK_DECL);
-  void splice (vec_t<T> * VEC_CHECK_DECL);
-  T *quick_push (const T & VEC_CHECK_DECL);
-  T &pop (ALONE_VEC_CHECK_DECL);
-  void truncate (unsigned VEC_CHECK_DECL);
-  void replace (unsigned, const T & VEC_CHECK_DECL);
-  void quick_insert (unsigned, const T & VEC_CHECK_DECL);
-  void ordered_remove (unsigned VEC_CHECK_DECL);
-  void unordered_remove (unsigned VEC_CHECK_DECL);
-  void block_remove (unsigned, unsigned VEC_CHECK_DECL);
-  unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
+template<typename, typename, typename> class vec;
 
-  /* Class-static member functions.  Some of these will become member
-     functions of a future handler class wrapping vec_t.  */
-  static size_t embedded_size (int);
+/* Valid vector layouts
 
-  template<enum vec_allocation_t A>
-  static vec_t<T> *alloc (int MEM_STAT_DECL);
+   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 { };
 
-  static vec_t<T> *alloc (int, vec_t<T> *);
 
-  template<enum vec_allocation_t A>
-  static void free (vec_t<T> **);
+/* Types of supported allocations
 
-  template<enum vec_allocation_t A>
-  static vec_t<T> *reserve_exact (vec_t<T> *, int MEM_STAT_DECL);
+   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.  */
 
-  template<enum vec_allocation_t A>
-  static bool reserve_exact (vec_t<T> **, int VEC_CHECK_DECL MEM_STAT_DECL);
+/* 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<enum vec_allocation_t A>
-  static vec_t<T> *reserve (vec_t<T> *, int MEM_STAT_DECL);
+  template<typename T>
+  static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool
+		       CXX_MEM_STAT_INFO);
 
-  template<enum vec_allocation_t A>
-  static bool reserve (vec_t<T> **, int VEC_CHECK_DECL MEM_STAT_DECL);
+  template<typename T>
+  static void release (vec<T, va_heap, vl_embed> *&);
+};
 
-  template<enum vec_allocation_t A>
-  static void safe_splice (vec_t<T> **, vec_t<T> * VEC_CHECK_DECL
-			   MEM_STAT_DECL);
 
-  template<enum vec_allocation_t A>
-  static T *safe_push (vec_t<T> **, const T & VEC_CHECK_DECL MEM_STAT_DECL);
+/* 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<enum vec_allocation_t A>
-  static void safe_grow (vec_t<T> **, int VEC_CHECK_DECL MEM_STAT_DECL);
+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->pfx_ : 0, reserve,
+						     exact);
+  if (!alloc)
+    {
+      release (v);
+      return;
+    }
+
+  if (GATHER_STATISTICS && v)
+    v->pfx_.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->pfx_.register_overhead (size FINAL_PASS_MEM_STAT);
+}
+
+
+/* Free the heap space allocated for vector V.  */
 
-  template<enum vec_allocation_t A>
-  static void safe_grow_cleared (vec_t<T> **, int VEC_CHECK_DECL MEM_STAT_DECL);
+template<typename T>
+void
+va_heap::release (vec<T, va_heap, vl_embed> *&v)
+{
+  if (GATHER_STATISTICS)
+    v->pfx_.release_overhead ();
+  ::free (v);
+  v = NULL;
+}
 
-  template<enum vec_allocation_t A>
-  static void safe_insert (vec_t<T> **, unsigned, const T & VEC_CHECK_DECL
-			   MEM_STAT_DECL);
 
-  static bool iterate (const vec_t<T> *, unsigned, T *);
-  static bool iterate (const vec_t<T> *, unsigned, T **);
+/* Allocator type for GC vectors.  Notice that we need the structure
+   declaration even if GC is not enabled.  */
 
-  vec_prefix prefix_;
-  T vec_[1];
+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; }
 };
 
 
-/* Garbage collection support for vec_t.  */
+/* 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>
+template<typename T, typename A>
 void
-gt_ggc_mx (vec_t<T> *v)
+va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact
+		MEM_STAT_DECL)
 {
-  extern void gt_ggc_mx (T &);
-  for (unsigned i = 0; i < v->length (); i++)
-    gt_ggc_mx ((*v)[i]);
+  unsigned alloc = vec_prefix::calculate_allocation (v ? &v->pfx_ : 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));
+  v->embedded_init (alloc, nelem);
 }
 
 
-/* PCH support for vec_t.  */
+/* 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
-gt_pch_nx (vec_t<T> *v)
+va_stack::alloc (vec<T, va_stack, vl_ptr> &v, unsigned nelems,
+		 vec<T, va_stack, vl_embed> *space)
 {
-  extern void gt_pch_nx (T &);
-  for (unsigned i = 0; i < v->length (); i++)
-    gt_pch_nx ((*v)[i]);
+  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
-gt_pch_nx (vec_t<T *> *v, gt_pointer_operator op, void *cookie)
+va_stack::reserve (vec<T, va_stack, vl_embed> *&v, unsigned nelems, bool exact
+		   MEM_STAT_DECL)
 {
-  for (unsigned i = 0; i < v->length (); i++)
-    op (&((*v)[i]), cookie);
+  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);
+      return;
+    }
+
+  /* Move VEC_ to the heap.  */
+  nelems += v->pfx_.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);
+  if (v && oldvec)
+    {
+      v->pfx_.num_ = oldvec->length ();
+      memcpy (v->data_, oldvec->data_, 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
-gt_pch_nx (vec_t<T> *v, gt_pointer_operator op, void *cookie)
+va_stack::release (vec<T, va_stack, vl_embed> *&v)
 {
-  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);
+  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));
+    }
 }
 
 
-/* FIXME.  Remove these definitions and update all calling sites after
-   the handler class for vec_t is implemented.  */
-
-/* Vector of integer-like object.  */
-#define DEF_VEC_I(T)			struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_I(T,A)		struct vec_swallow_trailing_semi
-
-/* Vector of pointer to object.  */
-#define DEF_VEC_P(T)			struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_P(T,A)		struct vec_swallow_trailing_semi
-
-/* Vector of object.  */
-#define DEF_VEC_O(T)			struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_O(T,A)		struct vec_swallow_trailing_semi
-
-/* Vectors on the stack.  */
-#define DEF_VEC_ALLOC_P_STACK(T)	struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_O_STACK(T)	struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_I_STACK(T)	struct vec_swallow_trailing_semi
-
-/* Vectors of atomic types.  Atomic types do not need to have its
-   elements marked for GC and PCH.  To avoid unnecessary traversals,
-   we provide template instantiations for the GC/PCH functions that
-   do not traverse the vector.
-
-   FIXME cxx-conversion - Once vec_t users are converted this can
-   be provided in some other way (e.g., adding an additional template
-   parameter to the vec_t class).  */
-#define DEF_VEC_A(TYPE)						\
-template<typename T>						\
-void								\
-gt_ggc_mx (vec_t<TYPE> *v ATTRIBUTE_UNUSED)			\
-{								\
-}								\
-								\
-template<typename T>						\
-void								\
-gt_pch_nx (vec_t<TYPE> *v ATTRIBUTE_UNUSED)			\
-{								\
-}								\
-								\
-template<typename T>						\
-void								\
-gt_pch_nx (vec_t<TYPE> *v ATTRIBUTE_UNUSED,			\
-	   gt_pointer_operator op ATTRIBUTE_UNUSED,		\
-	   void *cookie ATTRIBUTE_UNUSED)			\
-{								\
-}								\
-struct vec_swallow_trailing_semi
-
-#define DEF_VEC_ALLOC_A(T,A)		struct vec_swallow_trailing_semi
-
-/* Support functions for stack vectors.  */
-extern void *vec_stack_p_reserve_exact_1 (int, void *);
-extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
-extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t
-					 MEM_STAT_DECL);
-extern void vec_stack_free (void *);
-
-extern void dump_vec_loc_statistics (void);
-extern void ggc_free (void *);
-extern void vec_heap_free (void *);
+/* 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.
 
-/* API compatibility macros (to be removed).  */
-#define VEC_length(T,V)							\
-	((V) ? (V)->length () : 0)
+	   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>
+class GTY((user)) vec
+{
+};
 
-#define VEC_empty(T,V)							\
-	((V) ? (V)->empty () : true)
 
-#define VEC_address(T,V)						\
-	vec_address<T> (V)
+/* 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.
 
-/* FIXME.  For now, we need to continue expanding VEC_address into a
-   function call.  Otherwise, the warning machinery for -Wnonnull gets
-   confused thinking that VEC_address may return null in calls to
-   memcpy and qsort.  This will disappear once vec_address becomes
-   a member function for a handler class wrapping vec_t.  */
+   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.
 
-template<typename T>
-static inline T *
-vec_address (vec_t<T> *vec)
+   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>
+class GTY((user)) vec<T, A, vl_embed>
 {
-  return vec ? vec->address() : NULL;
-}
+public:
+  unsigned allocated (void) const { return pfx_.alloc_; }
+  unsigned length (void) const { return pfx_.num_; }
+  bool is_empty (void) const { return pfx_.num_ == 0; }
+  T *address (void) { return data_; }
+  const T *address (void) const { return data_; }
+  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_MEM_STAT_DECL) 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 class 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;
+
+private:
+  vec_prefix pfx_;
+  T data_[1];
+};
 
-#define VEC_last(T,V)							\
-	((V)->last (ALONE_VEC_CHECK_INFO))
 
-#define VEC_index(T,V,I)						\
-	((*(V))[I])
+/* 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:
 
-#define VEC_iterate(T,V,I,P)						\
-	(vec_t<T>::iterate(V, I, &(P)))
+	1- The pointer may be NULL (e.g., before initial allocation).
 
-#define VEC_embedded_size(T,N)						\
-	(vec_t<T>::embedded_size (N))
+  	2- When the vector needs to grow, it must be reallocated, so
+  	   the pointer will change its value.
 
-#define VEC_embedded_init(T,V,N)					\
-	((V)->embedded_init (N))
+   Because of limitations with the current GC machinery, all vectors
+   in GC memory *must* be pointers.  */
 
-#define VEC_free(T,A,V)							\
-	(vec_t<T>::free<A> (&(V)))
 
-#define VEC_copy(T,A,V)							\
-	((V)->copy<A> (ALONE_MEM_STAT_INFO))
+/* 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;
+}
 
-#define VEC_space(T,V,R)						\
-	((V) ? (V)->space (R VEC_CHECK_INFO) : (R) == 0)
 
-#define VEC_reserve(T,A,V,R)						\
-	(vec_t<T>::reserve<A> (&(V), (int)(R) VEC_CHECK_INFO MEM_STAT_INFO))
+/* 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;
+}
 
-#define VEC_reserve_exact(T,A,V,R)					\
-	(vec_t<T>::reserve_exact<A> (&(V), R VEC_CHECK_INFO MEM_STAT_INFO))
 
-#define VEC_splice(T,DST,SRC)	        				\
-	(DST)->splice (SRC VEC_CHECK_INFO)
+/* 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;
+}
 
-#define VEC_safe_splice(T,A,DST,SRC)					\
-	 vec_t<T>::safe_splice<A> (&(DST), SRC VEC_CHECK_INFO MEM_STAT_INFO)
 
-#define VEC_quick_push(T,V,O)						\
-	((V)->quick_push (O VEC_CHECK_INFO))
+/* 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;
+}
 
-#define VEC_safe_push(T,A,V,O)						\
-	(vec_t<T>::safe_push<A> (&(V), O VEC_CHECK_INFO MEM_STAT_INFO))
 
-#define VEC_pop(T,V)							\
-	((V)->pop (ALONE_VEC_CHECK_INFO))
+/* 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
+		  MEM_STAT_DECL)
+{
+  bool extend = nelems ? !vec_safe_space (v, nelems) : false;
+  if (extend)
+    A::reserve (v, nelems, exact PASS_MEM_STAT);
+  return extend;
+}
 
-#define VEC_truncate(T,V,I)						\
-	(V								\
-	 ? (V)->truncate ((unsigned)(I) VEC_CHECK_INFO)			\
-	 : gcc_assert ((I) == 0))
+template<typename T, typename A>
+inline bool
+vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems MEM_STAT_DECL)
+{
+  return vec_safe_reserve (v, nelems, true PASS_MEM_STAT);
+}
 
-#define VEC_safe_grow(T,A,V,I)						\
-	(vec_t<T>::safe_grow<A> (&(V), (int)(I) VEC_CHECK_INFO MEM_STAT_INFO))
 
-#define VEC_safe_grow_cleared(T,A,V,I)					\
-	(vec_t<T>::safe_grow_cleared<A> (&(V), (int)(I)			\
-				         VEC_CHECK_INFO MEM_STAT_INFO))
+/* Allocate GC memory for V with space for NELEMS slots.  If NELEMS
+   is 0, V is initialized to NULL.  */
 
-#define VEC_replace(T,V,I,O)						\
-	((V)->replace ((unsigned)(I), O VEC_CHECK_INFO))
+template<typename T, typename A>
+inline void
+vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems MEM_STAT_DECL)
+{
+  v = NULL;
+  vec_safe_reserve (v, nelems);
+}
 
-#define VEC_quick_insert(T,V,I,O)					\
-	((V)->quick_insert (I,O VEC_CHECK_INFO))
 
-#define VEC_safe_insert(T,A,V,I,O)					\
-	(vec_t<T>::safe_insert<A> (&(V), I, O VEC_CHECK_INFO MEM_STAT_INFO))
+/* Free the GC memory allocated by vector V and set it to NULL.  */
 
-#define VEC_ordered_remove(T,V,I)					\
-	((V)->ordered_remove (I VEC_CHECK_INFO))
+template<typename T, typename A>
+inline void
+vec_free (vec<T, A, vl_embed> *&v)
+{
+  A::release (v);
+}
 
-#define VEC_unordered_remove(T,V,I)					\
-	((V)->unordered_remove (I VEC_CHECK_INFO))
 
-#define VEC_block_remove(T,V,I,L)					\
-	((V)->block_remove (I, L VEC_CHECK_INFO))
+/* 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 MEM_STAT_DECL)
+{
+  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 PASS_MEM_STAT);
+}
 
-#define VEC_lower_bound(T,V,O,LT)					\
-	((V)->lower_bound (O, LT))
 
+/* 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 MEM_STAT_DECL)
+{
+  unsigned oldlen = vec_safe_length (v);
+  vec_safe_grow (v, len PASS_MEM_STAT);
+  memset (&(v->address()[oldlen]), 0, sizeof (T) * (len - oldlen));
+}
 
-/* Return the number of active elements in this vector.  */
 
-template<typename T>
-inline unsigned
-vec_t<T>::length (void) const
+/* 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)
 {
-  return prefix_.num_;
+  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;
+    }
+}
 
-/* Return true if this vector has no active elements.  */
 
-template<typename T>
-inline bool
-vec_t<T>::empty (void) const
+/* If V has no room for one more element, reallocate it.  Then call
+   V->quick_push(OBJ).  */
+template<typename T, typename A>
+inline T *
+vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj MEM_STAT_DECL)
 {
-  return length () == 0;
+  vec_safe_reserve (v, 1, false PASS_MEM_STAT);
+  return v->quick_push (obj PASS_MEM_STAT);
 }
 
 
-/* Return the address of the array of elements.  If you need to
-   directly manipulate the array (for instance, you want to feed it
-   to qsort), use this accessor.  */
+/* if V has no room for one more element, reallocate it.  Then call
+   V->quick_insert(IX, OBJ).  */
+template<typename T, typename A>
+inline void
+vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj
+		 MEM_STAT_DECL)
+{
+  vec_safe_reserve (v, 1, false PASS_MEM_STAT);
+  v->quick_insert (ix, obj);
+}
+
 
-template<typename T>
-inline T *
-vec_t<T>::address (void)
+/* If V is NULL, do nothing.  Otherwise, call V->truncate(SIZE).  */
+template<typename T, typename A>
+inline void
+vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size)
 {
-  return vec_;
+  if (v)
+    v->truncate (size);
 }
 
 
-/* Get the final element of the vector, which must not be empty.  */
+/* If SRC is not NULL, return a pointer to a copy of it.  */
+template<typename T, typename A>
+inline vec<T, A, vl_embed> *
+vec_safe_copy (vec<T, A, vl_embed> *src)
+{
+  return src ? src->copy () : NULL;
+}
 
-template<typename T>
-T &
-vec_t<T>::last (ALONE_VEC_CHECK_DECL)
+/* Copy the elements from SRC to the end of DST as if by memcpy.
+   Reallocate DST, if necessary.  */
+template<typename T, typename A>
+inline void
+vec_safe_splice (vec<T, A, vl_embed> *&dst, vec<T, A, vl_embed> *src
+		 MEM_STAT_DECL)
 {
-  VEC_ASSERT (prefix_.num_, "last", T, base);
-  return (*this)[prefix_.num_ - 1];
+  unsigned src_len = vec_safe_length (src);
+  if (src_len)
+    {
+      vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len);
+      dst->splice (*src);
+    }
 }
 
 
 /* Index into vector.  Return the IX'th element.  IX must be in the
    domain of the vector.  */
 
-template<typename T>
-const T &
-vec_t<T>::operator[] (unsigned ix) const
+template<typename T, typename A>
+inline const T &
+vec<T, A, vl_embed>::operator[] (unsigned ix) const
 {
-  gcc_assert (ix < prefix_.num_);
-  return vec_[ix];
+  gcc_checking_assert (ix < pfx_.num_);
+  return data_[ix];
 }
 
-template<typename T>
-T &
-vec_t<T>::operator[] (unsigned ix)
+template<typename T, typename A>
+inline T &
+vec<T, A, vl_embed>::operator[] (unsigned ix)
 {
-  gcc_assert (ix < prefix_.num_);
-  return vec_[ix];
+  gcc_checking_assert (ix < pfx_.num_);
+  return data_[ix];
+}
+
+
+/* Get the final element of the vector, which must not be empty.  */
+
+template<typename T, typename A>
+inline T &
+vec<T, A, vl_embed>::last (void)
+{
+  gcc_checking_assert (pfx_.num_ > 0);
+  return (*this)[pfx_.num_ - 1];
+}
+
+
+/* If this vector has space for NELEMS additional entries, return
+   true.  You usually only need to use this if you are doing your
+   own vector reallocation, for instance on an embedded vector.  This
+   returns true in exactly the same circumstances that vec::reserve
+   will.  */
+
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_embed>::space (unsigned nelems) const
+{
+  return pfx_.alloc_ - pfx_.num_ >= nelems;
 }
 
 
 /* Return iteration condition and update PTR to point to the IX'th
-   element of VEC.  Use this to iterate over the elements of a vector
-   as follows,
+   element of this vector.  Use this to iterate over the elements of a
+   vector as follows,
 
-     for (ix = 0; vec_t<T>::iterate(v, ix, &ptr); ix++)
-       continue;
-   
-   FIXME.  This is a static member function because if VEC is NULL,
-   PTR should be initialized to NULL.  This will become a regular
-   member function of the handler class.  */
+     for (ix = 0; vec<T, A>::iterate(v, ix, &ptr); ix++)
+       continue;  */
 
-template<typename T>
-bool
-vec_t<T>::iterate (const vec_t<T> *vec, unsigned ix, T *ptr)
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const
 {
-  if (vec && ix < vec->prefix_.num_)
+  if (ix < pfx_.num_)
     {
-      *ptr = vec->vec_[ix];
+      *ptr = data_[ix];
       return true;
     }
   else
@@ -518,22 +845,21 @@ vec_t<T>::iterate (const vec_t<T> *vec, unsigned ix, T *ptr)
 
 
 /* Return iteration condition and update *PTR to point to the
-   IX'th element of VEC.  Use this to iterate over the elements of a
-   vector as follows,
+   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.  FIXME, to be removed
-   once the distinction between vec_t<T> and vec_t<T *> disappears.  */
+   This variant is for vectors of objects.  */
 
-template<typename T>
-bool
-vec_t<T>::iterate (const vec_t<T> *vec, unsigned ix, T **ptr)
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const
 {
-  if (vec && ix < vec->prefix_.num_)
+  if (ix < pfx_.num_)
     {
-      *ptr = CONST_CAST (T *, &vec->vec_[ix]);
+      *ptr = CONST_CAST (T *, &data_[ix]);
       return true;
     }
   else
@@ -544,500 +870,835 @@ vec_t<T>::iterate (const vec_t<T> *vec, unsigned ix, T **ptr)
 }
 
 
-/* Convenience macro for forward iteration.  */
+/* Return a pointer to a copy of this vector.  */
 
-#define FOR_EACH_VEC_ELT(T, V, I, P)			\
-  for (I = 0; VEC_iterate (T, (V), (I), (P)); ++(I))
+template<typename T, typename A>
+inline vec<T, A, vl_embed> *
+vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const
+{
+  vec<T, A, vl_embed> *new_vec = NULL;
+  unsigned len = length ();
+  if (len)
+    {
+      vec_alloc (new_vec, len PASS_MEM_STAT);
+      new_vec->embedded_init (len, len);
+      memcpy (new_vec->address(), data_, sizeof (T) * len);
+    }
+  return new_vec;
+}
 
-/* Likewise, but start from FROM rather than 0.  */
 
-#define FOR_EACH_VEC_ELT_FROM(T, V, I, P, FROM)		\
-  for (I = (FROM); VEC_iterate (T, (V), (I), (P)); ++(I))
+/* Copy the elements from SRC to the end of this vector as if by memcpy.
+   The vector must have sufficient headroom available.  */
 
-/* Convenience macro for reverse iteration.  */
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::splice (vec<T, A, vl_embed> &src)
+{
+  unsigned len = src.length();
+  if (len)
+    {
+      gcc_checking_assert (space (len));
+      memcpy (address() + length(), src.address(), len * sizeof (T));
+      pfx_.num_ += len;
+    }
+}
 
-#define FOR_EACH_VEC_ELT_REVERSE(T, V, I, P)		\
-  for (I = VEC_length (T, (V)) - 1;			\
-       VEC_iterate (T, (V), (I), (P));			\
-       (I)--)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::splice (vec<T, A, vl_embed> *src)
+{
+  if (src)
+    splice (*src);
+}
+
+
+/* Push OBJ (a new element) onto the end of the vector.  There must be
+   sufficient space in the vector.  Return a pointer to the slot
+   where OBJ was inserted.  */
+
+template<typename T, typename A>
+inline T *
+vec<T, A, vl_embed>::quick_push (const T &obj)
+{
+  gcc_checking_assert (space (1));
+  T *slot = &data_[pfx_.num_++];
+  *slot = obj;
+  return slot;
+}
+
+
+/* Pop and return the last element off the end of the vector.  */
+
+template<typename T, typename A>
+inline T &
+vec<T, A, vl_embed>::pop (void)
+{
+  gcc_checking_assert (length () > 0);
+  return data_[--pfx_.num_];
+}
+
+
+/* Set the length of the vector to SIZE.  The new length must be less
+   than or equal to the current length.  This is an O(1) operation.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::truncate (unsigned size)
+{
+  gcc_checking_assert (length () >= size);
+  pfx_.num_ = size;
+}
+
+
+/* Insert an element, OBJ, at the IXth position of this vector.  There
+   must be sufficient space.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
+{
+  gcc_checking_assert (length () < allocated ());
+  gcc_checking_assert (ix <= length ());
+  T *slot = &data_[ix];
+  memmove (slot + 1, slot, (pfx_.num_++ - ix) * sizeof (T));
+  *slot = obj;
+}
+
+
+/* Remove an element from the IXth position of this vector.  Ordering of
+   remaining elements is preserved.  This is an O(N) operation due to
+   memmove.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::ordered_remove (unsigned ix)
+{
+  gcc_checking_assert (ix < length());
+  T *slot = &data_[ix];
+  memmove (slot, slot + 1, (--pfx_.num_ - ix) * sizeof (T));
+}
+
+
+/* Remove an element from the IXth position of this vector.  Ordering of
+   remaining elements is destroyed.  This is an O(1) operation.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::unordered_remove (unsigned ix)
+{
+  gcc_checking_assert (ix < length());
+  data_[ix] = data_[--pfx_.num_];
+}
+
+
+/* Remove LEN elements starting at the IXth.  Ordering is retained.
+   This is an O(N) operation due to memmove.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
+{
+  gcc_checking_assert (ix + len <= length());
+  T *slot = &data_[ix];
+  pfx_.num_ -= len;
+  memmove (slot, slot + len, (pfx_.num_ - ix) * sizeof (T));
+}
+
+
+/* Sort the contents of this vector with qsort.  CMP is the comparison
+   function to pass to qsort.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
+{
+  ::qsort (address(), length(), sizeof (T), cmp);
+}
 
 
-/* Return the number of bytes needed to embed an instance of vec_t inside
-   another data structure.
+/* Find and return the first position in which OBJ could be inserted
+   without changing the ordering of this vector.  LESSTHAN is a
+   function that returns true if the first argument is strictly less
+   than the second.  */
+
+template<typename T, typename A>
+unsigned
+vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &))
+  const
+{
+  unsigned int len = length ();
+  unsigned int half, middle;
+  unsigned int first = 0;
+  while (len > 0)
+    {
+      half = len / 2;
+      middle = first;
+      middle += half;
+      T middle_elem = (*this)[middle];
+      if (lessthan (middle_elem, obj))
+	{
+	  first = middle;
+	  ++first;
+	  len = len - half - 1;
+	}
+      else
+	len = half;
+    }
+  return first;
+}
+
+
+/* Return the number of bytes needed to embed an instance of an
+   embeddable vec inside another data structure.
 
    Use these methods to determine the required size and initialization
    of a vector V of type T embedded within another structure (as the
    final member):
 
-   size_t vec_t<T>::embedded_size<T> (int reserve);
-   void v->embedded_init(int reserve, int active);
+   size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc);
+   void v->embedded_init(unsigned alloc, unsigned num);
 
    These allow the caller to perform the memory allocation.  */
 
-template<typename T>
-size_t
-vec_t<T>::embedded_size (int nelems)
+template<typename T, typename A>
+inline size_t
+vec<T, A, vl_embed>::embedded_size (unsigned alloc)
 {
-  return offsetof (vec_t<T>, vec_) + nelems * sizeof (T);
+  typedef vec<T, A, vl_embed> vec_embedded;
+  return offsetof (vec_embedded, data_) + alloc * sizeof (T);
 }
 
 
-/* Initialize the vector to contain room for NELEMS elements and
-   ACTIVE active elements.  */
+/* Initialize the vector to contain room for ALLOC elements and
+   NUM active elements.  */
 
-template<typename T>
-void
-vec_t<T>::embedded_init (int nelems, int active)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num)
 {
-  prefix_.num_ = active;
-  prefix_.alloc_ = nelems;
+  pfx_.alloc_ = alloc;
+  pfx_.num_ = num;
 }
 
 
-/* Allocate a new vector with space for RESERVE objects.  If RESERVE
-   is zero, NO vector is created.
+/* Grow the vector to a specific length.  LEN must be as long or longer than
+   the current length.  The new elements are uninitialized.  */
 
-   Note that this allocator must always be a macro:
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::quick_grow (unsigned len)
+{
+  gcc_checking_assert (length () <= len && len <= pfx_.alloc_);
+  pfx_.num_ = len;
+}
 
-   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:
+/* Grow the vector to a specific length.  LEN must be as long or longer than
+   the current length.  The new elements are initialized to zero.  */
 
-   - 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.
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
+{
+  unsigned oldlen = length ();
+  quick_grow (len);
+  memset (&(address()[oldlen]), 0, sizeof (T) * (len - oldlen));
+}
 
-   - Don't return a stack-allocated vector from the function which
-     allocated it.  */
 
-#define VEC_alloc(T,A,N)						\
-  ((A == stack)								\
-    ? vec_t<T>::alloc (N, XALLOCAVAR (vec_t<T>, vec_t<T>::embedded_size (N)))\
-    : vec_t<T>::alloc<A> (N MEM_STAT_INFO))
+/* Garbage collection support for vec<T, A, vl_embed>.  */
 
 template<typename T>
-template<enum vec_allocation_t A>
-vec_t<T> *
-vec_t<T>::alloc (int nelems MEM_STAT_DECL)
+void
+gt_ggc_mx (vec<T, va_gc> *v)
 {
-  return reserve_exact<A> ((vec_t<T> *) NULL, nelems PASS_MEM_STAT);
+  extern void gt_ggc_mx (T &);
+  for (unsigned i = 0; i < v->length (); i++)
+    gt_ggc_mx ((*v)[i]);
 }
 
 template<typename T>
-vec_t<T> *
-vec_t<T>::alloc (int nelems, vec_t<T> *space)
+void
+gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
 {
-  return static_cast <vec_t<T> *> (vec_stack_p_reserve_exact_1 (nelems, space));
+  /* Nothing to do.  Vectors of atomic types wrt GC do not need to
+     be traversed.  */
 }
 
 
-/* Free vector *V and set it to NULL.  */
+/* PCH support for vec<T, A, vl_embed>.  */
 
-template<typename T>
-template<enum vec_allocation_t A>
+template<typename T, typename A>
 void
-vec_t<T>::free (vec_t<T> **v)
+gt_pch_nx (vec<T, A, vl_embed> *v)
 {
-  if (*v)
-    {
-      if (A == heap)
-	vec_heap_free (*v);
-      else if (A == gc)
-	ggc_free (*v);
-      else if (A == stack)
-	vec_stack_free (*v);
-    }
-  *v = NULL;
+  extern void gt_pch_nx (T &);
+  for (unsigned i = 0; i < v->length (); i++)
+    gt_pch_nx ((*v)[i]);
+}
+
+template<typename T, typename A>
+void
+gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
+{
+  for (unsigned i = 0; i < v->length (); i++)
+    op (&((*v)[i]), cookie);
+}
+
+template<typename T, typename A>
+void
+gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie)
+{
+  extern void gt_pch_nx (T *, gt_pointer_operator, void *);
+  for (unsigned i = 0; i < v->length (); i++)
+    gt_pch_nx (&((*v)[i]), op, cookie);
 }
 
 
-/* Return a copy of this vector.  The new and old vectors need not be
-   allocated by the same mechanism.  */
+/* Space efficient vector.  These vectors can grow dynamically and are
+   allocated together with their control data.  They are suited to be
+   included in data structures.  Prior to initial allocation, they
+   only take a single word of storage.
+
+   These vectors are implemented as a pointer to an embeddable vector.
+   The semantics allow for this pointer to be NULL to represent empty
+   vectors.  This way, empty vectors occupy minimal space in the
+   structure containing them.
+
+   Properties:
+
+	- The whole vector and control data are allocated in a single
+	  contiguous block.
+  	- The whole vector may be re-allocated.
+  	- Vector data may grow and shrink.
+  	- Access and manipulation requires a pointer test and
+	  indirection.
+	- It requires 1 word of storage (prior to vector allocation).
+
+
+   Limitations:
+
+   These vectors must be PODs because they are stored in unions.
+   (http://en.wikipedia.org/wiki/Plain_old_data_structures).
+   As long as we use C++03, we cannot have constructors nor
+   destructors in classes that are stored in unions.  */
+
+template<typename T, typename A>
+class vec<T, A, vl_ptr>
+{
+public:
+  /* Memory allocation and deallocation for the embedded vector.
+     Needed because we cannot have proper ctors/dtors defined.  */
+  void create (unsigned nelems CXX_MEM_STAT_INFO);
+  void release (void);
+
+  /* Vector operations.  */
+  bool exists (void) const
+  { return 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)
+  { return vec_ ? vec_->data_ : NULL; }
+
+  const T *address (void) const
+  { return vec_ ? vec_->data_ : NULL; }
+
+  const T &operator[] (unsigned ix) const
+  { return (*vec_)[ix]; }
+
+  bool operator!=(const vec &other) const
+  { return !(*this == other); }
+
+  bool operator==(const vec &other) const
+  { return address() == other.address(); }
+
+  T &operator[] (unsigned ix)
+  { return (*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 copy (ALONE_CXX_MEM_STAT_INFO) const;
+  bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
+  bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
+  void splice (vec &);
+  void safe_splice (vec & CXX_MEM_STAT_INFO);
+  T *quick_push (const T &);
+  T *safe_push (const T &CXX_MEM_STAT_INFO);
+  T &pop (void);
+  void truncate (unsigned);
+  void safe_grow (unsigned CXX_MEM_STAT_INFO);
+  void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO);
+  void quick_grow (unsigned);
+  void quick_grow_cleared (unsigned);
+  void quick_insert (unsigned, const T &);
+  void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
+  void ordered_remove (unsigned);
+  void unordered_remove (unsigned);
+  void block_remove (unsigned, unsigned);
+  void qsort (int (*) (const void *, const void *));
+  unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
+
+  template<typename T1>
+  friend void va_stack::alloc(vec<T1, va_stack, vl_ptr>&, unsigned,
+			      vec<T1, va_stack, vl_embed> *);
+
+private:
+  vec<T, A, vl_embed> *vec_;
+};
+
+
+/* Empty specialization for GC allocation.  This will prevent GC
+   vectors from using the vl_ptr layout.  FIXME: This is needed to
+   circumvent limitations in the GTY machinery.  */
 
 template<typename T>
-template<enum vec_allocation_t A>
-vec_t<T> *
-vec_t<T>::copy (ALONE_MEM_STAT_DECL)
+class vec<T, va_gc, vl_ptr>
 {
-  unsigned len = VEC_length (T, this);
-  vec_t<T> *new_vec = NULL;
+};
 
-  if (len)
-    {
-      new_vec = reserve_exact<A> (static_cast<vec_t<T> *> (NULL),
-				  len PASS_MEM_STAT);
-      new_vec->embedded_init (len, len);
-      memcpy (new_vec->address (), vec_, sizeof (T) * len);
-    }
 
-  return new_vec;
+/* Allocate heap memory for pointer V and create the internal vector
+   with space for NELEMS elements.  If NELEMS is 0, the internal
+   vector is initialized to empty.  */
+
+template<typename T>
+inline void
+vec_alloc (vec<T> *&v, unsigned nelems MEM_STAT_DECL)
+{
+  v = new vec<T>;
+  v->create (nelems PASS_MEM_STAT);
 }
 
 
-/* If this vector has space for RESERVE additional entries, return
-   true.  You usually only need to use this if you are doing your
-   own vector reallocation, for instance on an embedded vector.  This
-   returns true in exactly the same circumstances that vec_reserve
-   will.  */
+/* Conditionally allocate heap memory for VEC and its internal vector.  */
 
 template<typename T>
-bool
-vec_t<T>::space (int nelems VEC_CHECK_DECL)
+inline void
+vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems MEM_STAT_DECL)
 {
-  VEC_ASSERT (nelems >= 0, "space", T, base);
-  return prefix_.alloc_ - prefix_.num_ >= static_cast <unsigned> (nelems);
+  if (!vec)
+    vec_alloc (vec, nelems PASS_MEM_STAT);
 }
 
 
-/* Ensure that the vector **VEC has at least RESERVE slots available.  This
-   will create additional headroom.  Note this can cause **VEC to
-   be reallocated.  Returns true iff reallocation actually occurred.  */
+/* Free the heap memory allocated by vector V and set it to NULL.  */
 
 template<typename T>
-template<enum vec_allocation_t A>
-bool
-vec_t<T>::reserve (vec_t<T> **vec, int nelems VEC_CHECK_DECL MEM_STAT_DECL)
+inline void
+vec_free (vec<T> *&v)
 {
-  bool extend = (*vec) ? !(*vec)->space (nelems VEC_CHECK_PASS) : nelems != 0;
+  if (v == NULL)
+    return;
 
-  if (extend)
-    *vec = reserve<A> (*vec, nelems PASS_MEM_STAT);
+  v->release ();
+  delete v;
+  v = NULL;
+}
 
-  return extend;
+
+/* Allocate a new stack 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<T, A>.  It allocates the
+     actual vector of elements (i.e., vec<T, A, vl_embed>) inside a
+     vec<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)						\
+  do {									\
+    typedef vec<T, va_stack, vl_embed> stackv;				\
+    va_stack::alloc (V, N, XALLOCAVAR (stackv, stackv::embedded_size (N)));\
+  } while (0)
+
+
+/* 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, typename A>
+inline bool
+vec<T, A, vl_ptr>::iterate (unsigned ix, T *ptr) const
+{
+  if (vec_)
+    return vec_->iterate (ix, ptr);
+  else
+    {
+      *ptr = 0;
+      return false;
+    }
 }
 
 
-/* Ensure that **VEC has at least NELEMS slots available.  This will not
-   create additional headroom.  Note this can cause VEC to be
-   reallocated.  Returns true iff reallocation actually occurred.  */
+/* 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,
 
-template<typename T>
-template<enum vec_allocation_t A>
-bool
-vec_t<T>::reserve_exact (vec_t<T> **vec, int nelems VEC_CHECK_DECL
-			 MEM_STAT_DECL)
+     for (ix = 0; v->iterate(ix, &ptr); ix++)
+       continue;
+
+   This variant is for vectors of objects.  */
+
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_ptr>::iterate (unsigned ix, T **ptr) const
 {
-  bool extend = (*vec) ? !(*vec)->space (nelems VEC_CHECK_PASS) : nelems != 0;
+  if (vec_)
+    return vec_->iterate (ix, ptr);
+  else
+    {
+      *ptr = 0;
+      return false;
+    }
+}
 
-  if (extend)
-    *vec = reserve_exact<A> (*vec, nelems PASS_MEM_STAT);
 
+/* Convenience macro for forward iteration.  */
+#define FOR_EACH_VEC_ELT(V, I, P)			\
+  for (I = 0; (V).iterate ((I), &(P)); ++(I))
+
+#define FOR_EACH_VEC_SAFE_ELT(V, I, P)			\
+  for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I))
+
+/* Likewise, but start from FROM rather than 0.  */
+#define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM)		\
+  for (I = (FROM); (V).iterate ((I), &(P)); ++(I))
+
+/* Convenience macro for reverse iteration.  */
+#define FOR_EACH_VEC_ELT_REVERSE(V, I, P)		\
+  for (I = (V).length () - 1;				\
+       (V).iterate ((I), &(P));				\
+       (I)--)
+
+#define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P)		\
+  for (I = vec_safe_length (V) - 1;			\
+       vec_safe_iterate ((V), (I), &(P));	\
+       (I)--)
+
+
+/* Return a copy of this vector.  */
+
+template<typename T, typename A>
+inline vec<T, A, vl_ptr>
+vec<T, A, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const
+{
+  vec<T, A, vl_ptr> new_vec = vec<T, A, vl_ptr>();
+  if (length ())
+    new_vec.vec_ = vec_->copy ();
+  return new_vec;
+}
+
+
+/* Ensure that the vector has at least RESERVE slots available (if
+   EXACT is false), or exactly RESERVE slots available (if EXACT is
+   true).
+
+   This may create additional headroom if EXACT is false.
+
+   Note that this can cause the embedded vector to be reallocated.
+   Returns true iff reallocation actually occurred.  */
+
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
+{
+  bool extend = nelems ? !space (nelems) : false;
+  if (extend)
+    A::reserve (vec_, nelems, exact PASS_MEM_STAT);
   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, typename A>
+inline bool
+vec<T, A, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL)
+{
+  return reserve (nelems, true PASS_MEM_STAT);
+}
+
+
+/* Create the internal vector and reserve NELEMS for it.  This is
+   exactly like vec::reserve, but the internal vector is
+   unconditionally allocated from scratch.  The old one, if it
+   existed, is lost.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::create (unsigned nelems MEM_STAT_DECL)
+{
+  vec_ = NULL;
+  if (nelems > 0)
+    reserve_exact (nelems PASS_MEM_STAT);
+}
+
+
+/* Free the memory occupied by the embedded vector.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::release (void)
+{
+  if (vec_)
+    A::release (vec_);
+}
+
+
 /* Copy the elements from SRC to the end of this vector as if by memcpy.
-   SRC and this vector need not be allocated with the same mechanism,
-   although they most often will be.  This vector is assumed to have
-   sufficient headroom available.  */
+   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>
-void
-vec_t<T>::splice (vec_t<T> *src VEC_CHECK_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::splice (vec<T, A, vl_ptr> &src)
 {
-  if (src)
-    {
-      unsigned len = VEC_length (T, src);
-      VEC_ASSERT (VEC_length (T, this) + len <= prefix_.alloc_, "splice", T,
-		  base);
-      memcpy (address () + VEC_length (T, this),
-	      src->address (),
-	      len * sizeof (T));
-      prefix_.num_ += len;
-    }
+  if (src.vec_)
+    vec_->splice (*(src.vec_));
 }
 
 
-/* Copy the elements in SRC to the end of DST as if by memcpy.  DST and
-   SRC need not be allocated with the same mechanism, although they most
-   often will be.  DST need not have sufficient headroom and will be
-   reallocated if needed.  */
+/* 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>
-template<enum vec_allocation_t A>
-void
-vec_t<T>::safe_splice (vec_t<T> **dst, vec_t<T> *src VEC_CHECK_DECL
-		       MEM_STAT_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::safe_splice (vec<T, A, vl_ptr> &src MEM_STAT_DECL)
 {
-  if (src)
+  if (src.length())
     {
-      reserve_exact<A> (dst, VEC_length (T, src) VEC_CHECK_PASS MEM_STAT_INFO);
-      (*dst)->splice (src VEC_CHECK_PASS);
+      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>
-T *
-vec_t<T>::quick_push (const T &obj VEC_CHECK_DECL)
+template<typename T, typename A>
+inline T *
+vec<T, A, vl_ptr>::quick_push (const T &obj)
 {
-  VEC_ASSERT (prefix_.num_ < prefix_.alloc_, "push", T, base);
-  T *slot = &vec_[prefix_.num_++];
-  *slot = obj;
-  return slot;
+  return vec_->quick_push (obj);
 }
 
 
-/* Push a new element OBJ onto the end of VEC.  Reallocates VEC, if
-   needed.  Return a pointer to the slot where OBJ was inserted.  */
+/* 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>
-template<enum vec_allocation_t A>
-T *
-vec_t<T>::safe_push (vec_t<T> **vec, const T &obj VEC_CHECK_DECL MEM_STAT_DECL)
+template<typename T, typename A>
+inline T *
+vec<T, A, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
 {
-  reserve<A> (vec, 1 VEC_CHECK_PASS PASS_MEM_STAT);
-  return (*vec)->quick_push (obj VEC_CHECK_PASS);
+  reserve (1, false PASS_MEM_STAT);
+  return quick_push (obj);
 }
 
 
 /* Pop and return the last element off the end of the vector.  */
 
-
-template<typename T>
-T &
-vec_t<T>::pop (ALONE_VEC_CHECK_DECL)
+template<typename T, typename A>
+inline T &
+vec<T, A, vl_ptr>::pop (void)
 {
-  VEC_ASSERT (prefix_.num_, "pop", T, base);
-  return vec_[--prefix_.num_];
+  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>
-void
-vec_t<T>::truncate (unsigned size VEC_CHECK_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::truncate (unsigned size)
 {
-  VEC_ASSERT (prefix_.num_ >= size, "truncate", T, base);
-  prefix_.num_ = size;
+  if (vec_)
+    vec_->truncate (size);
+  else
+    gcc_checking_assert (size == 0);
 }
 
 
-/* Grow the vector VEC to a specific length.  The LEN must be as
-   long or longer than the current length.  The new elements are
-   uninitialized.  */
+/* Grow the vector to a specific length.  LEN must be as long or
+   longer than the current length.  The new elements are
+   uninitialized.  Reallocate the internal vector, if needed.  */
 
-template<typename T>
-template<enum vec_allocation_t A>
-void
-vec_t<T>::safe_grow (vec_t<T> **vec, int size VEC_CHECK_DECL MEM_STAT_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL)
 {
-  VEC_ASSERT (size >= 0 && VEC_length (T, *vec) <= (unsigned)size,
-	      "grow", T, A);
-  reserve_exact<A> (vec, size - (int)VEC_length (T, *vec)
-		    VEC_CHECK_PASS PASS_MEM_STAT);
-  (*vec)->prefix_.num_ = size;
+  unsigned oldlen = length ();
+  gcc_checking_assert (oldlen <= len);
+  reserve_exact (len - oldlen PASS_MEM_STAT);
+  vec_->quick_grow (len);
 }
 
 
-/* Grow the vector *VEC to a specific length.  The LEN must be as
+/* Grow the embedded vector to a specific length.  LEN must be as
    long or longer than the current length.  The new elements are
-   initialized to zero.  */
+   initialized to zero.  Reallocate the internal vector, if needed.  */
 
-template<typename T>
-template<enum vec_allocation_t A>
-void
-vec_t<T>::safe_grow_cleared (vec_t<T> **vec, int size VEC_CHECK_DECL
-			     MEM_STAT_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL)
 {
-  int oldsize = VEC_length (T, *vec);
-  safe_grow<A> (vec, size VEC_CHECK_PASS PASS_MEM_STAT);
-  memset (&((*vec)->address ()[oldsize]), 0, sizeof (T) * (size - oldsize));
+  unsigned oldlen = length ();
+  safe_grow (len PASS_MEM_STAT);
+  memset (&(address()[oldlen]), 0, sizeof (T) * (len - oldlen));
 }
 
 
-/* Replace the IXth element of this vector with a new value, VAL.  */
+/* Same as vec::safe_grow but without reallocation of the internal vector.
+   If the vector cannot be extended, a runtime assertion will be triggered.  */
 
-template<typename T>
-void
-vec_t<T>::replace (unsigned ix, const T &obj VEC_CHECK_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::quick_grow (unsigned len)
 {
-  VEC_ASSERT (ix < prefix_.num_, "replace", T, base);
-  vec_[ix] = obj;
+  gcc_checking_assert (vec_);
+  vec_->quick_grow (len);
 }
 
 
-/* Insert an element, OBJ, at the IXth position of VEC.  There must be
-   sufficient space.  */
+/* Same as vec::quick_grow_cleared but without reallocation of the
+   internal vector. If the vector cannot be extended, a runtime
+   assertion will be triggered.  */
 
-template<typename T>
-void
-vec_t<T>::quick_insert (unsigned ix, const T &obj VEC_CHECK_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::quick_grow_cleared (unsigned len)
 {
-  VEC_ASSERT (prefix_.num_ < prefix_.alloc_, "insert", T, base);
-  VEC_ASSERT (ix <= prefix_.num_, "insert", T, base);
-  T *slot = &vec_[ix];
-  memmove (slot + 1, slot, (prefix_.num_++ - ix) * sizeof (T));
-  *slot = obj;
+  gcc_checking_assert (vec_);
+  vec_->quick_grow_cleared (len);
 }
 
 
-/* Insert an element, OBJ, at the IXth position of VEC. Reallocate
-   VEC, if necessary.  */
+/* Insert an element, OBJ, at the IXth position of this vector.  There
+   must be sufficient space.  */
 
-template<typename T>
-template<enum vec_allocation_t A>
-void
-vec_t<T>::safe_insert (vec_t<T> **vec, unsigned ix, const T &obj VEC_CHECK_DECL
-		       MEM_STAT_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::quick_insert (unsigned ix, const T &obj)
 {
-  reserve<A> (vec, 1 VEC_CHECK_PASS PASS_MEM_STAT);
-  (*vec)->quick_insert (ix, obj VEC_CHECK_PASS);
+  vec_->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.  */
+/* Insert an element, OBJ, at the IXth position of the vector.
+   Reallocate the embedded vector, if necessary.  */
 
-template<typename T>
-void
-vec_t<T>::ordered_remove (unsigned ix VEC_CHECK_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL)
 {
-  VEC_ASSERT (ix < prefix_.num_, "remove", T, base);
-  T *slot = &vec_[ix];
-  memmove (slot, slot + 1, (--prefix_.num_ - ix) * sizeof (T));
+  reserve (1, false PASS_MEM_STAT);
+  quick_insert (ix, obj);
 }
 
 
-/* Remove an element from the IXth position of VEC.  Ordering of
-   remaining elements is destroyed.  This is an O(1) operation.  */
+/* 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>
-void
-vec_t<T>::unordered_remove (unsigned ix VEC_CHECK_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::ordered_remove (unsigned ix)
 {
-  VEC_ASSERT (ix < prefix_.num_, "remove", T, base);
-  vec_[ix] = vec_[--prefix_.num_];
+  vec_->ordered_remove (ix);
 }
 
 
-/* Remove LEN elements starting at the IXth.  Ordering is retained.
-   This is an O(N) operation due to memmove.  */
+/* 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>
-void
-vec_t<T>::block_remove (unsigned ix, unsigned len VEC_CHECK_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::unordered_remove (unsigned ix)
 {
-  VEC_ASSERT (ix + len <= prefix_.num_, "block_remove", T, base);
-  T *slot = &vec_[ix];
-  prefix_.num_ -= len;
-  memmove (slot, slot + len, (prefix_.num_ - ix) * sizeof (T));
+  vec_->unordered_remove (ix);
 }
 
-/* Sort the contents of V with qsort.  Use CMP as the comparison function.  */
-#define VEC_qsort(T,V,CMP)						\
-	qsort (VEC_address (T, V), VEC_length (T, V), sizeof (T), CMP)
 
+/* Remove LEN elements starting at the IXth.  Ordering is retained.
+   This is an O(N) operation due to memmove.  */
 
-/* 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_t<T>::lower_bound (T obj, bool (*lessthan)(const T &, const T &)) const
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::block_remove (unsigned ix, unsigned len)
 {
-  unsigned int len = VEC_length (T, this);
-  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;
+  vec_->block_remove (ix, len);
 }
 
 
-void *vec_heap_o_reserve_1 (void *, int, size_t, size_t, bool MEM_STAT_DECL);
-void *vec_gc_o_reserve_1 (void *, int, size_t, size_t, bool MEM_STAT_DECL);
-
-/* Ensure there are at least RESERVE free slots in VEC_, growing
-   exponentially.  If RESERVE < 0 grow exactly, else grow
-   exponentially.  As a special case, if VEC_ is NULL, and RESERVE is
-   0, no vector will be created. */
+/* Sort the contents of this vector with qsort.  CMP is the comparison
+   function to pass to qsort.  */
 
-template<typename T>
-template<enum vec_allocation_t A>
-vec_t<T> *
-vec_t<T>::reserve (vec_t<T> *vec, int reserve MEM_STAT_DECL)
+template<typename T, typename A>
+inline void
+vec<T, A, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
 {
-  void *res = NULL;
-  size_t off = offsetof (vec_t<T>, vec_);
-  size_t sz = sizeof (T);
-
-  switch (A)
-    {
-      case gc:
-	res = vec_gc_o_reserve_1 (vec, reserve, off, sz, false PASS_MEM_STAT);
-	break;
-      case heap:
-	res = vec_heap_o_reserve_1 (vec, reserve, off, sz, false PASS_MEM_STAT);
-	break;
-      case stack:
-	res = vec_stack_o_reserve (vec, reserve, off, sz PASS_MEM_STAT);
-	break;
-    }
-
-  return static_cast <vec_t<T> *> (res);
+  if (vec_)
+    vec_->qsort (cmp);
 }
 
 
-/* Ensure there are at least RESERVE free slots in VEC, growing
-   exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
-   a special case, if VEC is NULL, and RESERVE is 0, no vector will be
-   created. */
+/* 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>
-template<enum vec_allocation_t A>
-vec_t<T> *
-vec_t<T>::reserve_exact (vec_t<T> *vec, int reserve MEM_STAT_DECL)
+template<typename T, typename A>
+inline unsigned
+vec<T, A, vl_ptr>::lower_bound (T obj, bool (*lessthan)(const T &, const T &)) const
 {
-  void *res = NULL;
-  size_t off = sizeof (struct vec_prefix);
-  size_t sz = sizeof (T);
-
-  gcc_assert (offsetof (vec_t<T>, vec_) == sizeof (struct vec_prefix));
-
-  switch (A)
-    {
-      case gc:
-	res = vec_gc_o_reserve_1 (vec, reserve, off, sz, true PASS_MEM_STAT);
-	break;
-      case heap:
-	res = vec_heap_o_reserve_1 (vec, reserve, off, sz, true PASS_MEM_STAT);
-	break;
-      case stack:
-	res = vec_stack_o_reserve_exact (vec, reserve, off, sz PASS_MEM_STAT);
-	break;
-    }
-
-  return static_cast <vec_t<T> *> (res);
+  return vec_ ? vec_->lower_bound (obj, lessthan) : 0;
 }
 
-#endif /* GCC_VEC_H */
+#endif // GCC_VEC_H