Add a type-safe hash table, hash_table.  Uses of this table replace uses
of libiberty's htab_t.  The benefits include less boiler-plate code,
full type safety, and improved performance.

As proof of concept, this patch changes eight uses of htab_t to
hash_table, one in coverage.c and seven in tree-ssa-*.  Most of the
remaining 117 gcc files can be converted incrementally.  The compile
time of the compiler building itself, with the seven changed tables,
is nominally 0.536% better (with an 90% confidence of being in the range
of .287% to .784%).

The type-safe hash table is a template, taking the element type and the
operational functions as template parameters.  Passing the operational
functions as template parameters, rather than function pointers, exposes
the calls to inlining at -O2.  A side effect is that declarations of
hash tables move to after the declarations of those functions.  A further
side effect is that the control block shrinks from 108 bytes to 44 bytes.
There is otherwise no effect on data size.

Null function pointers are not acceptable as template arguments, which has
two effects.  First, we eliminate the dynamic tests for null pointers.
Second, the patch provides template functions that serve the effect of
doing nothing.

Static functions are also not acceptable as template arguments, so this
patch externalizes the functions.  To avoid potential name conflicts,
the function names have been prefixed.

Final hash_table template parameter is an allocator class.  It provides
the functions for allocating and freeing memory, both as control blocks
and as data blocks.  The default template parameter will serve most uses,
so little actual specification is necessary.

Operations on the tables are member functions rather than global
functions.  The callers have been adjusted to match.  These functions
preserve the original names, with the exception of htab_delete, which
becomes .dispose because 'delete' is a C++ keyword.  The .dispose member
function also nulls the pointer to the control block, which otherwise
would have needed to be done by clients.

Since the hash_table is not exposed as a pointer, there is a new boolean
query member function, is_created.

The new hash table is algorithmically identical to htab_t, so there is
no semantic effect to replacing uses of htab_t with hash_table.

Because libcpp was using a typedef hash_table, that typedef has been
renamed cpp_hash_table and uses of it have changed.


Index: gcc/ChangeLog.cxx-conversion

2012-06-01   Lawrence Crowl  <crowl@google.com>

	* hash-table.h: New. Implementation borrowed from libiberty/hashtab.c.
	* hash-table.c: Likewise.
	* tree-ssa-tail-merge.c: Include hash-table.h instead of hashtab.h.
	(static htab_t same_succ_htab): Change type to hash_table;
	move specification of helper functions from create call to declaration.
	Change users to invoke member functions.
	(same_succ_print_traverse): Make extern ssa_.... Change callers.
	Remove void* casting.
	(same_succ_hash): Likewise.
	(same_succ_equal): Likewise.
	(same_succ_delete): Likewise.
	* tree-ssa-threadupdate.c: Include hash-table.h.
	(struct local_info): Rename to ssa_local_info_t to avoid overloading
	the type name local_info with the variable name local_info.
	(static htab_t redirection_data): Change type to hash_table.
	Move specification of helper functions from create call to declaration.
	Change users to invoke member functions.
	(redirection_data_hash): Make extern ssa_.... Change callers.
	Remove void* casting.
	(redirection_data_eq): Likewise.
	(fix_duplicate_block_edges): Likewise.
	(create_duplicates): Likewise.
	(fixup_template_block): Likewise.
	(redirect_edges): Likewise.
	(lookup_redirection_data): Change types associated with the hash table
	from void* to their actual type. Remove unnecessary casts.
	* tree-ssa-ccp.c: Include hash-table.h.
	(typedef gimple_htab): New.  Uses hash_table.  Replace specific uses
	of htab_t with gimple_htab.  Change users to invoke member functions.
	Move specification of helper functions from create call to declaration.
	* tree-ssa-coalesce.c: Include hash-table.h instead of hashtab.h.
	(hash_ssa_name_by_var): Make extern. Remove void* casting.
	(eq_ssa_name_by_var): Likewise.
	(coalesce_ssa_name): Change type of local static htab_t ssa_name_hash
	to hash_table. Change users to invoke member functions.
	Move specification of helper functions from create call to declaration.
	* coverage.c: Include hash-table.h instead of hashtab.h.
	(static htab_t counts_hash): Change type to hash_table;
	move specification of helper functions from create call to declaration.
	Change users to invoke member functions.
	(htab_counts_entry_hash): Make extern. Rename with coverage_... instead
	of htab_... Remove void* casting.
	(htab_counts_entry_eq): Likewise.
	(htab_counts_entry_del): Likewise.
	* tree-ssa-pre.c: Include hash-table.h instead of hashtab.h.
	(static htab_t expression_to_id): Change type to hash_table.
	Move specification of helper functions from create call to declaration.
	Change users to invoke member functions.
	(static htab_t phi_translate_table): Likewise.
	(pre_expr_eq): Make extern ssa_.... Change callers.
	Remove void* casting.
	(pre_expr_hash): Likewise.
	(expr_pred_trans_hash): Likewise.
	(expr_pred_trans_eq): Likewise.
	(alloc_expression_id): Change types associated with the hash table
	from void* to their actual type. Remove unnecessary casts.
	(lookup_expression_id): Likewise.
	(phi_trans_lookup): Likewise.
	(phi_trans_add): Likewise.
	* stringpool.c: Rename uses of libcpp typedef hash_table to
	cpp_hash_table.
	* Makefile.in: Add hash-table.o to OBJS-libcommon-target.
	Add $(HASH_TABLE_H). Add new dependences on $(HASH_TABLE_H).

Index: libcpp/ChangeLog.cxx-conversion

2012-06-01   Lawrence Crowl  <crowl@google.com>

	* include/symtab.h (typedef struct ht hash_table): Change the typedef
	name to cpp_hash_table.  Update all users of the typedef.




git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/cxx-conversion@188129 138bc75d-0d04-0410-961f-82ee72b054a4