[cxx-conversion] New Hash Table

[Lawrence Crowl, 2012-05-24 16:43:45]

Add a type-safe hash table, typed_htab.  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
typed_htab, 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 0.66% better.

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


Index: gcc/ChangeLog.cxx-conversion

2012-05-23   Lawrence Crowl  <crowl@google.com>

	* typed-hashtab.h: New. Implementation borrowed from
	libiberty/hashtab.c.
	* typed-hashtab.c: Likewise.
	* tree-ssa-tail-merge.c: Include typed-hashtab.h.
	(static htab_t same_succ_htab): Change type to typed_htab;
	move specification of helper functions from create call to declaration.
	(same_succ_print_traverse): Make extern ssa_...; change callers;
	remove void* casting.
	(same_succ_hash): Likewise.
	(same_succ_equal): Likewise.
	* tree-ssa-threadupdate.c: Include typed-hashtab.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 typed_htab;
	move specification of helper functions from create call to declaration.
	(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-coalesce.c: Include typed-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 typed_htab.
	* coverage.c: Include typed-hashtab.h.
	(static htab_t counts_hash): Change type to typed_htab;
	move specification of helper functions from create call to declaration.
	(coverage_counts_entry_hash): Make extern; remove void* casting.
	(htab_counts_entry_eq): Likewise.
	(coverage_counts_entry_del): Likewise.
	* tree-ssa-pre.c: Include typed-hashtab.h.
	(static htab_t expression_to_id): Change type to typed_htab;
	move specification of helper functions from create call to declaration.
	(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.
	* Makefile.in: Add typed-hashtab.o to OBJS-libcommon-target.
	Add $(TYPED_HASHTAB_H). Add new dependences on $(TYPED_HASHTAB_H).


Index: gcc/tree-ssa-tail-merge.c
===================================================================
--- gcc/tree-ssa-tail-merge.c	(revision 187816)
+++ gcc/tree-ssa-tail-merge.c	(working copy)
@@ -196,7 +196,7 @@ along with GCC; see the file COPYING3.  
 #include "tree-ssa-alias.h"
 #include "params.h"
 #include "tree-pretty-print.h"
-#include "hashtab.h"
+#include "typed-hashtab.h"
 #include "gimple-pretty-print.h"
 #include "tree-ssa-sccvn.h"
 #include "tree-dump.h"
@@ -367,11 +367,10 @@ same_succ_print (FILE *file, const same_
 
 /* Prints same_succ VE to VFILE.  */
 
-static int
-same_succ_print_traverse (void **ve, void *vfile)
+inline int
+ssa_same_succ_print_traverse (same_succ *pe, FILE *file)
 {
-  const same_succ e = *((const same_succ *)ve);
-  FILE *file = ((FILE*)vfile);
+  const same_succ e = *pe;
   same_succ_print (file, e);
   return 1;
 }
@@ -415,10 +414,9 @@ stmt_update_dep_bb (gimple stmt)
 
 /* Calculates hash value for same_succ VE.  */
 
-static hashval_t
-same_succ_hash (const void *ve)
+hashval_t
+ssa_same_succ_hash (const_same_succ e)
 {
-  const_same_succ e = (const_same_succ)ve;
   hashval_t hashval = bitmap_hash (e->succs);
   int flags;
   unsigned int i;
@@ -514,11 +512,9 @@ inverse_flags (const_same_succ e1, const
 
 /* Compares SAME_SUCCs VE1 and VE2.  */
 
-static int
-same_succ_equal (const void *ve1, const void *ve2)
+int
+ssa_same_succ_equal (const_same_succ e1, const_same_succ e2)
 {
-  const_same_succ e1 = (const_same_succ)ve1;
-  const_same_succ e2 = (const_same_succ)ve2;
   unsigned int i, first1, first2;
   gimple_stmt_iterator gsi1, gsi2;
   gimple s1, s2;
@@ -589,17 +585,15 @@ same_succ_alloc (void)
 
 /* Delete same_succ VE.  */
 
-static void
-same_succ_delete (void *ve)
+inline void
+ssa_same_succ_delete (same_succ e)
 {
-  same_succ e = (same_succ)ve;
-
   BITMAP_FREE (e->bbs);
   BITMAP_FREE (e->succs);
   BITMAP_FREE (e->inverse);
   VEC_free (int, heap, e->succ_flags);
 
-  XDELETE (ve);
+  XDELETE (e);
 }
 
 /* Reset same_succ SAME.  */
@@ -615,7 +609,9 @@ same_succ_reset (same_succ same)
 
 /* Hash table with all same_succ entries.  */
 
-static htab_t same_succ_htab;
+static typed_htab <struct same_succ_def, ssa_same_succ_hash,
+		   ssa_same_succ_equal, ssa_same_succ_delete>
+		  same_succ_htab;
 
 /* Array that is used to store the edge flags for a successor.  */
 
@@ -636,7 +632,7 @@ extern void debug_same_succ (void);
 DEBUG_FUNCTION void
 debug_same_succ ( void)
 {
-  htab_traverse (same_succ_htab, same_succ_print_traverse, stderr);
+  same_succ_htab.traverse <FILE *, ssa_same_succ_print_traverse> (stderr);
 }
 
 DEF_VEC_P (same_succ);
@@ -695,10 +691,9 @@ find_same_succ_bb (basic_block bb, same_
   EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
     VEC_safe_push (int, heap, same->succ_flags, same_succ_edge_flags[j]);
 
-  same->hashval = same_succ_hash (same);
+  same->hashval = ssa_same_succ_hash (same);
 
-  slot = (same_succ *) htab_find_slot_with_hash (same_succ_htab, same,
-						   same->hashval, INSERT);
+  slot = same_succ_htab.find_slot_with_hash (same, same->hashval, INSERT);
   if (*slot == NULL)
     {
       *slot = same;
@@ -732,7 +727,7 @@ find_same_succ (void)
 	same = same_succ_alloc ();
     }
 
-  same_succ_delete (same);
+  ssa_same_succ_delete (same);
 }
 
 /* Initializes worklist administration.  */
@@ -741,9 +736,7 @@ static void
 init_worklist (void)
 {
   alloc_aux_for_blocks (sizeof (struct aux_bb_info));
-  same_succ_htab
-    = htab_create (n_basic_blocks, same_succ_hash, same_succ_equal,
-		   same_succ_delete);
+  same_succ_htab.create (n_basic_blocks);
   same_succ_edge_flags = XCNEWVEC (int, last_basic_block);
   deleted_bbs = BITMAP_ALLOC (NULL);
   deleted_bb_preds = BITMAP_ALLOC (NULL);
@@ -763,8 +756,7 @@ static void
 delete_worklist (void)
 {
   free_aux_for_blocks ();
-  htab_delete (same_succ_htab);
-  same_succ_htab = NULL;
+  same_succ_htab.dispose ();
   XDELETEVEC (same_succ_edge_flags);
   same_succ_edge_flags = NULL;
   BITMAP_FREE (deleted_bbs);
@@ -794,7 +786,7 @@ same_succ_flush_bb (basic_block bb)
   same_succ same = BB_SAME_SUCC (bb);
   BB_SAME_SUCC (bb) = NULL;
   if (bitmap_single_bit_set_p (same->bbs))
-    htab_remove_elt_with_hash (same_succ_htab, same, same->hashval);
+    same_succ_htab.remove_elt_with_hash (same, same->hashval);
   else
     bitmap_clear_bit (same->bbs, bb->index);
 }
@@ -867,7 +859,7 @@ update_worklist (void)
       if (same == NULL)
 	same = same_succ_alloc ();
     }
-  same_succ_delete (same);
+  ssa_same_succ_delete (same);
   bitmap_clear (deleted_bb_preds);
 }
 
@@ -1628,7 +1620,7 @@ tail_merge_optimize (unsigned int todo)
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "htab collision / search: %f\n",
-	     htab_collisions (same_succ_htab));
+	     same_succ_htab.collisions ());
 
   if (nr_bbs_removed_total > 0)
     {
Index: gcc/tree-ssa-threadupdate.c
===================================================================
--- gcc/tree-ssa-threadupdate.c	(revision 187816)
+++ gcc/tree-ssa-threadupdate.c	(working copy)
@@ -32,6 +32,7 @@ along with GCC; see the file COPYING3.  
 #include "tree-dump.h"
 #include "tree-pass.h"
 #include "cfgloop.h"
+#include "typed-hashtab.h"
 
 /* Given a block B, update the CFG and SSA graph to reflect redirecting
    one or more in-edges to B to instead reach the destination of an
@@ -128,11 +129,8 @@ struct redirection_data
   struct el *incoming_edges;
 };
 
-/* Main data structure to hold information for duplicates of BB.  */
-static htab_t redirection_data;
-
 /* Data structure of information to pass to hash table traversal routines.  */
-struct local_info
+struct ssa_local_info_t
 {
   /* The current block we are working on.  */
   basic_block bb;
@@ -222,24 +220,32 @@ create_block_for_threading (basic_block 
 }
 
 /* Hashing and equality routines for our hash table.  */
-static hashval_t
-redirection_data_hash (const void *p)
+inline hashval_t
+ssa_redirection_data_hash (const struct redirection_data *p)
 {
-  edge e = ((const struct redirection_data *)p)->outgoing_edge;
+  edge e = p->outgoing_edge;
   return e->dest->index;
 }
 
-static int
-redirection_data_eq (const void *p1, const void *p2)
+inline int
+ssa_redirection_data_eq (const struct redirection_data *p1,
+			 const struct redirection_data *p2)
 {
-  edge e1 = ((const struct redirection_data *)p1)->outgoing_edge;
-  edge e2 = ((const struct redirection_data *)p2)->outgoing_edge;
-  edge e3 = ((const struct redirection_data *)p1)->intermediate_edge;
-  edge e4 = ((const struct redirection_data *)p2)->intermediate_edge;
+  edge e1 = p1->outgoing_edge;
+  edge e2 = p2->outgoing_edge;
+  edge e3 = p1->intermediate_edge;
+  edge e4 = p2->intermediate_edge;
 
   return e1 == e2 && e3 == e4;
 }
 
+/* Main data structure to hold information for duplicates of BB.  */
+
+static typed_htab <struct redirection_data, ssa_redirection_data_hash,
+		   ssa_redirection_data_eq,
+		   typed_free_remove<struct redirection_data> >
+		  redirection_data;
+
 /* Given an outgoing edge E lookup and return its entry in our hash table.
 
    If INSERT is true, then we insert the entry into the hash table if
@@ -249,7 +255,7 @@ redirection_data_eq (const void *p1, con
 static struct redirection_data *
 lookup_redirection_data (edge e, enum insert_option insert)
 {
-  void **slot;
+  struct redirection_data **slot;
   struct redirection_data *elt;
 
  /* Build a hash table element so we can see if E is already
@@ -261,7 +267,7 @@ lookup_redirection_data (edge e, enum in
   elt->dup_block = NULL;
   elt->incoming_edges = NULL;
 
-  slot = htab_find_slot (redirection_data, elt, insert);
+  slot = redirection_data.find_slot (elt, insert);
 
   /* This will only happen if INSERT is false and the entry is not
      in the hash table.  */
@@ -275,7 +281,7 @@ lookup_redirection_data (edge e, enum in
      INSERT is true.  */
   if (*slot == NULL)
     {
-      *slot = (void *)elt;
+      *slot = elt;
       elt->incoming_edges = XNEW (struct el);
       elt->incoming_edges->e = e;
       elt->incoming_edges->next = NULL;
@@ -289,7 +295,7 @@ lookup_redirection_data (edge e, enum in
       free (elt);
 
       /* Get the entry stored in the hash table.  */
-      elt = (struct redirection_data *) *slot;
+      elt = *slot;
 
       /* If insertion was requested, then we need to add INCOMING_EDGE
 	 to the list of incoming edges associated with E.  */
@@ -377,9 +383,9 @@ create_edge_and_update_destination_phis 
 
 /* Wire up the outgoing edges from the duplicate block and
    update any PHIs as needed.  */
-static void
-fix_duplicate_block_edges (struct redirection_data *rd,
-			   struct local_info *local_info)
+void
+ssa_fix_duplicate_block_edges (struct redirection_data *rd,
+			       ssa_local_info_t *local_info)
 {
   /* If we were threading through an joiner block, then we want
      to keep its control statement and redirect an outgoing edge.
@@ -414,11 +420,11 @@ fix_duplicate_block_edges (struct redire
 }
 /* Hash table traversal callback routine to create duplicate blocks.  */
 
-static int
-create_duplicates (void **slot, void *data)
+int
+ssa_create_duplicates (struct redirection_data **slot,
+		       ssa_local_info_t *local_info)
 {
-  struct redirection_data *rd = (struct redirection_data *) *slot;
-  struct local_info *local_info = (struct local_info *)data;
+  struct redirection_data *rd = *slot;
 
   /* Create a template block if we have not done so already.  Otherwise
      use the template to create a new block.  */
@@ -437,7 +443,7 @@ create_duplicates (void **slot, void *da
 
       /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
 	 block.   */
-      fix_duplicate_block_edges (rd, local_info);
+      ssa_fix_duplicate_block_edges (rd, local_info);
     }
 
   /* Keep walking the hash table.  */
@@ -448,11 +454,11 @@ create_duplicates (void **slot, void *da
    block creation.  This hash table traversal callback creates the
    outgoing edge for the template block.  */
 
-static int
-fixup_template_block (void **slot, void *data)
+inline int
+ssa_fixup_template_block (struct redirection_data **slot,
+			  ssa_local_info_t *local_info)
 {
-  struct redirection_data *rd = (struct redirection_data *) *slot;
-  struct local_info *local_info = (struct local_info *)data;
+  struct redirection_data *rd = *slot;
 
   /* If this is the template block halt the traversal after updating
      it appropriately.
@@ -463,7 +469,7 @@ fixup_template_block (void **slot, void 
      a new outgoing edge.  In both cases we may need to update PHIs.  */
   if (rd->dup_block && rd->dup_block == local_info->template_block)
     {
-      fix_duplicate_block_edges (rd, local_info);
+      ssa_fix_duplicate_block_edges (rd, local_info);
       return 0;
     }
 
@@ -473,11 +479,11 @@ fixup_template_block (void **slot, void 
 /* Hash table traversal callback to redirect each incoming edge
    associated with this hash table element to its new destination.  */
 
-static int
-redirect_edges (void **slot, void *data)
+int
+ssa_redirect_edges (struct redirection_data **slot,
+		    ssa_local_info_t *local_info)
 {
-  struct redirection_data *rd = (struct redirection_data *) *slot;
-  struct local_info *local_info = (struct local_info *)data;
+  struct redirection_data *rd = *slot;
   struct el *next, *el;
 
   /* Walk over all the incoming edges associated associated with this
@@ -596,17 +602,14 @@ thread_block (basic_block bb, bool noloo
      redirect to a duplicate of BB.  */
   edge e, e2;
   edge_iterator ei;
-  struct local_info local_info;
+  ssa_local_info_t local_info;
   struct loop *loop = bb->loop_father;
 
   /* To avoid scanning a linear array for the element we need we instead
      use a hash table.  For normal code there should be no noticeable
      difference.  However, if we have a block with a large number of
      incoming and outgoing edges such linear searches can get expensive.  */
-  redirection_data = htab_create (EDGE_COUNT (bb->succs),
-				  redirection_data_hash,
-				  redirection_data_eq,
-				  free);
+  redirection_data.create (EDGE_COUNT (bb->succs));
 
   /* If we thread the latch of the loop to its exit, the loop ceases to
      exist.  Make sure we do not restrict ourselves in order to preserve
@@ -680,24 +683,26 @@ thread_block (basic_block bb, bool noloo
   local_info.template_block = NULL;
   local_info.bb = bb;
   local_info.jumps_threaded = false;
-  htab_traverse (redirection_data, create_duplicates, &local_info);
+  redirection_data.traverse <ssa_local_info_t *, ssa_create_duplicates>
+			    (&local_info);
 
   /* The template does not have an outgoing edge.  Create that outgoing
      edge and update PHI nodes as the edge's target as necessary.
 
      We do this after creating all the duplicates to avoid creating
      unnecessary edges.  */
-  htab_traverse (redirection_data, fixup_template_block, &local_info);
+  redirection_data.traverse <ssa_local_info_t *, ssa_fixup_template_block>
+			    (&local_info);
 
   /* The hash table traversals above created the duplicate blocks (and the
      statements within the duplicate blocks).  This loop creates PHI nodes for
      the duplicated blocks and redirects the incoming edges into BB to reach
      the duplicates of BB.  */
-  htab_traverse (redirection_data, redirect_edges, &local_info);
+  redirection_data.traverse <ssa_local_info_t *, ssa_redirect_edges>
+			    (&local_info);
 
   /* Done with this block.  Clear REDIRECTION_DATA.  */
-  htab_delete (redirection_data);
-  redirection_data = NULL;
+  redirection_data.dispose ();
 
   if (noloop_only
       && bb == bb->loop_father->header)
Index: gcc/typed-hashtab.c
===================================================================
--- gcc/typed-hashtab.c	(revision 0)
+++ gcc/typed-hashtab.c	(revision 0)
@@ -0,0 +1,190 @@
+/* A type-safe hash table template.
+   Copyright (C) 2012
+   Free Software Foundation, Inc.
+   Contributed by Lawrence Crowl <crowl@google.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+
+/* This file implements a typed hash table.
+   The implementation borrows from libiberty's hashtab.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "typed-hashtab.h"
+
+
+/* Table of primes and multiplicative inverses.
+
+   Note that these are not minimally reduced inverses.  Unlike when generating
+   code to divide by a constant, we want to be able to use the same algorithm
+   all the time.  All of these inverses (are implied to) have bit 32 set.
+
+   For the record, here's the function that computed the table; it's a 
+   vastly simplified version of the function of the same name from gcc.  */
+
+#if 0
+unsigned int
+ceil_log2 (unsigned int x)
+{
+  int i;
+  for (i = 31; i >= 0 ; --i)
+    if (x > (1u << i))
+      return i+1;
+  abort ();
+}
+
+unsigned int
+choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp)
+{
+  unsigned long long mhigh;
+  double nx;
+  int lgup, post_shift;
+  int pow, pow2;
+  int n = 32, precision = 32;
+
+  lgup = ceil_log2 (d);
+  pow = n + lgup;
+  pow2 = n + lgup - precision;
+
+  nx = ldexp (1.0, pow) + ldexp (1.0, pow2);
+  mhigh = nx / d;
+
+  *shiftp = lgup - 1;
+  *mlp = mhigh;
+  return mhigh >> 32;
+}
+#endif
+
+struct prime_ent const prime_tab[] = {
+  {          7, 0x24924925, 0x9999999b, 2 },
+  {         13, 0x3b13b13c, 0x745d1747, 3 },
+  {         31, 0x08421085, 0x1a7b9612, 4 },
+  {         61, 0x0c9714fc, 0x15b1e5f8, 5 },
+  {        127, 0x02040811, 0x0624dd30, 6 },
+  {        251, 0x05197f7e, 0x073260a5, 7 },
+  {        509, 0x01824366, 0x02864fc8, 8 },
+  {       1021, 0x00c0906d, 0x014191f7, 9 },
+  {       2039, 0x0121456f, 0x0161e69e, 10 },
+  {       4093, 0x00300902, 0x00501908, 11 },
+  {       8191, 0x00080041, 0x00180241, 12 },
+  {      16381, 0x000c0091, 0x00140191, 13 },
+  {      32749, 0x002605a5, 0x002a06e6, 14 },
+  {      65521, 0x000f00e2, 0x00110122, 15 },
+  {     131071, 0x00008001, 0x00018003, 16 },
+  {     262139, 0x00014002, 0x0001c004, 17 },
+  {     524287, 0x00002001, 0x00006001, 18 },
+  {    1048573, 0x00003001, 0x00005001, 19 },
+  {    2097143, 0x00004801, 0x00005801, 20 },
+  {    4194301, 0x00000c01, 0x00001401, 21 },
+  {    8388593, 0x00001e01, 0x00002201, 22 },
+  {   16777213, 0x00000301, 0x00000501, 23 },
+  {   33554393, 0x00001381, 0x00001481, 24 },
+  {   67108859, 0x00000141, 0x000001c1, 25 },
+  {  134217689, 0x000004e1, 0x00000521, 26 },
+  {  268435399, 0x00000391, 0x000003b1, 27 },
+  {  536870909, 0x00000019, 0x00000029, 28 },
+  { 1073741789, 0x0000008d, 0x00000095, 29 },
+  { 2147483647, 0x00000003, 0x00000007, 30 },
+  /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
+  { 0xfffffffb, 0x00000006, 0x00000008, 31 }
+};
+
+/* The following function returns an index into the above table of the
+   nearest prime number which is greater than N, and near a power of two. */
+
+unsigned int
+typed_htab_higher_prime_index (unsigned long n)
+{
+  unsigned int low = 0;
+  unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);
+
+  while (low != high)
+    {
+      unsigned int mid = low + (high - low) / 2;
+      if (n > prime_tab[mid].prime)
+	low = mid + 1;
+      else
+	high = mid;
+    }
+
+  /* If we've run out of primes, abort.  */
+  if (n > prime_tab[low].prime)
+    {
+      fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
+      abort ();
+    }
+
+  return low;
+}
+
+/* Return X % Y using multiplicative inverse values INV and SHIFT.
+
+   The multiplicative inverses computed above are for 32-bit types,
+   and requires that we be able to compute a highpart multiply.
+
+   FIX: I am not at all convinced that
+     3 loads, 2 multiplications, 3 shifts, and 3 additions
+   will be faster than
+     1 load and 1 modulus
+   on modern systems running a compiler.  */
+
+#ifdef UNSIGNED_64BIT_TYPE
+static inline hashval_t
+mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
+{
+  __extension__ typedef UNSIGNED_64BIT_TYPE ull;
+   hashval_t t1, t2, t3, t4, q, r;
+
+   t1 = ((ull)x * inv) >> 32;
+   t2 = x - t1;
+   t3 = t2 >> 1;
+   t4 = t1 + t3;
+   q  = t4 >> shift;
+   r  = x - (q * y);
+
+   return r;
+}
+#endif
+
+/* Compute the primary table index for HASH given current prime index.  */
+
+hashval_t
+typed_htab_mod1 (hashval_t hash, unsigned int index)
+{
+  const struct prime_ent *p = &prime_tab[index];
+#ifdef UNSIGNED_64BIT_TYPE
+  if (sizeof (hashval_t) * CHAR_BIT <= 32)
+    return mul_mod (hash, p->prime, p->inv, p->shift);
+#endif
+  return hash % p->prime;
+}
+
+
+/* Compute the secondary table index for HASH given current prime index.  */
+
+hashval_t
+typed_htab_mod2 (hashval_t hash, unsigned int index)
+{
+  const struct prime_ent *p = &prime_tab[index];
+#ifdef UNSIGNED_64BIT_TYPE
+  if (sizeof (hashval_t) * CHAR_BIT <= 32)
+    return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift);
+#endif
+  return 1 + hash % (p->prime - 2);
+}
Index: gcc/typed-hashtab.h
===================================================================
--- gcc/typed-hashtab.h	(revision 0)
+++ gcc/typed-hashtab.h	(revision 0)
@@ -0,0 +1,711 @@
+/* A type-safe hash table template.
+   Copyright (C) 2012
+   Free Software Foundation, Inc.
+   Contributed by Lawrence Crowl <crowl@google.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+
+/* This file implements a typed hash table.
+   The implementation borrows from libiberty's hashtab.  */
+
+
+#ifndef TYPED_HASHTAB_H
+#define TYPED_HASHTAB_H
+
+#include "hashtab.h"
+
+
+/* The ordinary memory allocator.  */
+/* FIXME (crowl): This allocator may be extracted for wider sharing later.  */
+
+template <typename Type>
+struct xcallocator
+{
+
+  /* Allocate memory for COUNT control blocks.  */
+
+  static Type *control_alloc (size_t count)
+  { return static_cast <Type *> (xcalloc (count, sizeof (Type))); }
+  
+
+  /* Allocate memory for COUNT data blocks.  */ 
+
+  static Type *data_alloc (size_t count)
+  { return static_cast <Type *> (xcalloc (count, sizeof (Type))); }
+
+
+  /* Free memory for control blocks.  */
+
+  static void control_free (Type *memory)
+  { return ::free (memory); }
+  
+  /* Free memory for data blocks.  */
+
+  static void data_free (Type *memory)
+  { return ::free (memory); }
+  
+};
+
+
+/* A common function for hashing a CANDIDATE typed pointer.  */
+
+template <typename Element>
+inline hashval_t
+typed_pointer_hash (const Element *candidate)
+{
+  /* This is a really poor hash function, but it is what the current code
uses,
+     so I am reusing it to avoid an additional axis in testing.  */
+  return (hashval_t) ((intptr_t)candidate >> 3);
+}
+
+
+/* A common function for comparing an EXISTING and CANDIDATE typed pointers
+   for equality. */
+
+template <typename Element>
+inline int
+typed_pointer_equal (const Element *existing, const Element * candidate)
+{
+  return existing == candidate;
+}
+
+
+/* A common function for doing nothing on removing a RETIRED slot.  */
+
+template <typename Element>
+inline void
+typed_null_remove (Element *retired ATTRIBUTE_UNUSED)
+{
+}
+
+
+/* A common function for using free on removing a RETIRED slot.  */
+
+template <typename Element>
+inline void
+typed_free_remove (Element *retired)
+{
+  free (retired);
+}
+
+
+/* Table of primes and their inversion information.  */
+
+struct prime_ent
+{
+  hashval_t prime;
+  hashval_t inv;
+  hashval_t inv_m2;     /* inverse of prime-2 */
+  hashval_t shift;
+};
+
+extern struct prime_ent const prime_tab[];
+
+
+/* Functions for computing hash table indexes.  */
+
+extern unsigned int typed_htab_higher_prime_index (unsigned long n);
+extern hashval_t typed_htab_mod1 (hashval_t hash, unsigned int index);
+extern hashval_t typed_htab_mod2 (hashval_t hash, unsigned int index);
+
+
+/* Internal implementation type.  */
+
+template <typename Element>
+struct typed_htab_control
+{
+  /* Table itself.  */
+  Element **entries;
+
+  /* Current size (in entries) of the hash table.  */
+  size_t size;
+
+  /* Current number of elements including also deleted elements.  */
+  size_t n_elements;
+
+  /* Current number of deleted elements in the table.  */
+  size_t n_deleted;
+
+  /* The following member is used for debugging. Its value is number
+     of all calls of `htab_find_slot' for the hash table. */
+  unsigned int searches;
+
+  /* The following member is used for debugging.  Its value is number
+     of collisions fixed for time of work with the hash table. */
+  unsigned int collisions;
+
+  /* Current size (in entries) of the hash table, as an index into the
+     table of primes.  */
+  unsigned int size_prime_index;
+};
+
+
+/* User-facing hash table type.
+
+   The table stores elements of type Element.
+
+   It hashes elements with the Hash function.
+     The table currently works with relatively weak hash functions.
+     Use typed_pointer_hash <Element> when hashing pointers instead of
objects.
+
+   It compares elements with the Equal function.
+     Two elements with the same hash may not be equal.
+     Use typed_pointer_equal <Element> when hashing pointers instead of
objects.
+
+   It removes elements with the Remove function.
+     This feature is useful for freeing memory.
+     Use typed_null_remove <Element> when not freeing objects.
+     Use typed_free_remove <Element> when doing a simple object free.
+
+   Use the Allocator template to allocate and free memory.
+     The default is xcallocator.
+
+*/
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator = xcallocator>
+struct typed_htab
+{
+
+private:
+
+  typed_htab_control <Element> *htab;
+
+
+  Element **find_empty_slot_for_expand (hashval_t hash);
+  void expand ();
+
+public:
+
+  void create (size_t initial_slots);
+  void dispose ();
+  Element *find_with_hash (Element *comparable, hashval_t hash);
+  Element **find_slot_with_hash (Element *comparable, hashval_t hash,
+				 enum insert_option insert);
+  void empty ();
+  void clear_slot (Element **slot);
+  void remove_elt_with_hash (Element *comparable, hashval_t hash);
+
+  template <typename Argument,
+	    int (*Callback) (Element **slot, Argument argument)>
+  void traverse_noresize (Argument argument);
+
+  template <typename Argument,
+	    int (*Callback) (Element **slot, Argument argument)>
+  void traverse (Argument argument);
+
+
+  /* Construct the hash table.  The only useful operation next is create.  */
+
+  typed_htab ()
+  : htab (NULL)
+  {
+  }
+
+
+  /* See if the table has been created, as opposed to constructed.  */
+
+  bool is_created ()
+  {
+    return htab != NULL;
+  }
+
+
+  /* Like find_with_hash, but compute the hash value from the element.  */
+
+  Element *find (Element *comparable)
+  {
+    return find_with_hash (comparable, Hash (comparable));
+  }
+
+
+  /* Like find_slot_with_hash, but compute the hash value from the element. 
*/
+
+  Element **find_slot (Element *comparable, enum insert_option insert)
+  {
+    return find_slot_with_hash (comparable, Hash (comparable), insert);
+  }
+
+
+  /* Like remove_elt_with_hash, but compute the hash value from the element. 
*/
+
+  void remove_elt (Element *comparable)
+  {
+    remove_elt_with_hash (comparable, Hash (comparable));
+  }
+
+
+
+  /* Return the current size of this hash table.  */
+
+  size_t size()
+  {
+    return htab->size;
+  }
+
+
+  /* Return the current number of elements in this hash table. */
+
+  size_t elements()
+  {
+    return htab->n_elements - htab->n_deleted;
+  }
+
+
+  /* Return the fraction of fixed collisions during all work with given
+     hash table. */
+
+  double collisions()
+  {
+    if (htab->searches == 0)
+      return 0.0;
+
+    return static_cast <double> (htab->collisions) / htab->searches;
+  }
+
+};
+
+
+/* Create a hash table with at least the given number of INITIAL_SLOTS.  */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+void
+typed_htab <Element, Hash, Equal, Remove, Allocator>
+::create (size_t size)
+{
+  unsigned int size_prime_index;
+
+  size_prime_index = typed_htab_higher_prime_index (size);
+  size = prime_tab[size_prime_index].prime;
+
+  htab = Allocator <typed_htab_control <Element> > ::control_alloc (1);
+  gcc_assert (htab != NULL);
+  htab->entries = Allocator <Element*> ::data_alloc (size);
+  gcc_assert (htab->entries != NULL);
+  htab->size = size;
+  htab->size_prime_index = size_prime_index;
+}
+
+
+/* Dispose of a hash table.  Free all memory and return this hash table to
+   the non-created state.  Naturally the hash table must already exist.  */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+void
+typed_htab <Element, Hash, Equal, Remove, Allocator>
+::dispose ()
+{
+  size_t size = htab->size;
+  Element **entries = htab->entries;
+
+  for (int i = size - 1; i >= 0; i--)
+    if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
+      Remove (entries[i]);
+
+  Allocator <Element *> ::data_free (entries);
+  Allocator <typed_htab_control <Element> > ::control_free (htab);
+  htab = NULL;
+}
+
+
+/* Similar to find_slot, but without several unwanted side effects:
+    - Does not call Equal when it finds an existing entry.
+    - Does not change the count of elements/searches/collisions in the
+      hash table.
+   This function also assumes there are no deleted entries in the table.
+   HASH is the hash value for the element to be inserted.  */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+Element **
+typed_htab <Element, Hash, Equal, Remove, Allocator>
+::find_empty_slot_for_expand (hashval_t hash)
+{
+  hashval_t index = typed_htab_mod1 (hash, htab->size_prime_index);
+  size_t size = htab->size;
+  Element **slot = htab->entries + index;
+  hashval_t hash2;
+
+  if (*slot == HTAB_EMPTY_ENTRY)
+    return slot;
+  else if (*slot == HTAB_DELETED_ENTRY)
+    abort ();
+
+  hash2 = typed_htab_mod2 (hash, htab->size_prime_index);
+  for (;;)
+    {
+      index += hash2;
+      if (index >= size)
+        index -= size;
+
+      slot = htab->entries + index;
+      if (*slot == HTAB_EMPTY_ENTRY)
+        return slot;
+      else if (*slot == HTAB_DELETED_ENTRY)
+        abort ();
+    }
+}
+
+
+/* The following function changes size of memory allocated for the
+   entries and repeatedly inserts the table elements.  The occupancy
+   of the table after the call will be about 50%.  Naturally the hash
+   table must already exist.  Remember also that the place of the
+   table entries is changed.  If memory allocation fails, this function
+   will abort.  */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+void
+typed_htab <Element, Hash, Equal, Remove, Allocator>
+::expand ()
+{
+  Element **oentries;
+  Element **olimit;
+  Element **p;
+  Element **nentries;
+  size_t nsize, osize, elts;
+  unsigned int oindex, nindex;
+
+  oentries = htab->entries;
+  oindex = htab->size_prime_index;
+  osize = htab->size;
+  olimit = oentries + osize;
+  elts = elements ();
+
+  /* Resize only when table after removal of unused elements is either
+     too full or too empty.  */
+  if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
+    {
+      nindex = typed_htab_higher_prime_index (elts * 2);
+      nsize = prime_tab[nindex].prime;
+    }
+  else
+    {
+      nindex = oindex;
+      nsize = osize;
+    }
+
+  nentries = Allocator <Element *> ::data_alloc (nsize);
+  gcc_assert (nentries != NULL);
+  htab->entries = nentries;
+  htab->size = nsize;
+  htab->size_prime_index = nindex;
+  htab->n_elements -= htab->n_deleted;
+  htab->n_deleted = 0;
+
+  p = oentries;
+  do
+    {
+      Element *x = *p;
+
+      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
+        {
+          Element **q = find_empty_slot_for_expand (Hash (x));
+
+          *q = x;
+        }
+
+      p++;
+    }
+  while (p < olimit);
+
+  Allocator <Element *> ::data_free (oentries);
+}
+
+
+/* This function searches for a hash table entry equal to the given
+   COMPARABLE element starting with the given HASH value.  It cannot
+   be used to insert or delete an element. */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+Element *
+typed_htab <Element, Hash, Equal, Remove, Allocator>
+::find_with_hash (Element *comparable, hashval_t hash)
+{
+  hashval_t index, hash2;
+  size_t size;
+  Element *entry;
+
+  htab->searches++;
+  size = htab->size;
+  index = typed_htab_mod1 (hash, htab->size_prime_index);
+
+  entry = htab->entries[index];
+  if (entry == HTAB_EMPTY_ENTRY
+      || (entry != HTAB_DELETED_ENTRY && Equal (entry, comparable)))
+    return entry;
+
+  hash2 = typed_htab_mod2 (hash, htab->size_prime_index);
+  for (;;)
+    {
+      htab->collisions++;
+      index += hash2;
+      if (index >= size)
+        index -= size;
+
+      entry = htab->entries[index];
+      if (entry == HTAB_EMPTY_ENTRY
+          || (entry != HTAB_DELETED_ENTRY && Equal (entry, comparable)))
+        return entry;
+    }
+}
+
+
+/* This function searches for a hash table slot containing an entry
+   equal to the given COMPARABLE element and starting with the given
+   HASH.  To delete an entry, call this with insert=NO_INSERT, then
+   call clear_slot on the slot returned (possibly after doing some
+   checks).  To insert an entry, call this with insert=INSERT, then
+   write the value you want into the returned slot.  When inserting an
+   entry, NULL may be returned if memory allocation fails. */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+Element **
+typed_htab <Element, Hash, Equal, Remove, Allocator>
+::find_slot_with_hash (Element *comparable, hashval_t hash,
+		       enum insert_option insert)
+{
+  Element **first_deleted_slot;
+  hashval_t index, hash2;
+  size_t size;
+  Element *entry;
+
+  size = htab->size;
+  if (insert == INSERT && size * 3 <= htab->n_elements * 4)
+    {
+      expand ();
+      size = htab->size;
+    }
+
+  index = typed_htab_mod1 (hash, htab->size_prime_index);
+
+  htab->searches++;
+  first_deleted_slot = NULL;
+
+  entry = htab->entries[index];
+  if (entry == HTAB_EMPTY_ENTRY)
+    goto empty_entry;
+  else if (entry == HTAB_DELETED_ENTRY)
+    first_deleted_slot = &htab->entries[index];
+  else if (Equal (entry, comparable))
+    return &htab->entries[index];
+      
+  hash2 = typed_htab_mod2 (hash, htab->size_prime_index);
+  for (;;)
+    {
+      htab->collisions++;
+      index += hash2;
+      if (index >= size)
+	index -= size;
+      
+      entry = htab->entries[index];
+      if (entry == HTAB_EMPTY_ENTRY)
+	goto empty_entry;
+      else if (entry == HTAB_DELETED_ENTRY)
+	{
+	  if (!first_deleted_slot)
+	    first_deleted_slot = &htab->entries[index];
+	}
+      else if (Equal (entry, comparable))
+	return &htab->entries[index];
+    }
+
+ empty_entry:
+  if (insert == NO_INSERT)
+    return NULL;
+
+  if (first_deleted_slot)
+    {
+      htab->n_deleted--;
+      *first_deleted_slot = static_cast <Element *> (HTAB_EMPTY_ENTRY);
+      return first_deleted_slot;
+    }
+
+  htab->n_elements++;
+  return &htab->entries[index];
+}
+
+
+/* This function clears all entries in the given hash table.  */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+void
+typed_htab <Element, Hash, Equal, Remove, Allocator>
+::empty ()
+{
+  size_t size = htab_size (htab);
+  Element **entries = htab->entries;
+  int i;
+
+  for (i = size - 1; i >= 0; i--)
+    if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
+      Remove (entries[i]);
+
+  /* Instead of clearing megabyte, downsize the table.  */
+  if (size > 1024*1024 / sizeof (PTR))
+    {
+      int nindex = typed_htab_higher_prime_index (1024 / sizeof (PTR));
+      int nsize = prime_tab[nindex].prime;
+
+      Allocator <Element *> ::data_free (htab->entries);
+      htab->entries = Allocator <Element *> ::data_alloc (nsize);
+      htab->size = nsize;
+      htab->size_prime_index = nindex;
+    }
+  else
+    memset (entries, 0, size * sizeof (Element *));
+  htab->n_deleted = 0;
+  htab->n_elements = 0;
+}
+
+
+/* This function clears a specified SLOT in a hash table.  It is
+   useful when you've already done the lookup and don't want to do it
+   again. */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+void
+typed_htab <Element, Hash, Equal, Remove, Allocator>
+::clear_slot (Element **slot)
+{
+  if (slot < htab->entries || slot >= htab->entries + htab->size
+      || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
+    abort ();
+
+  Remove (*slot);
+
+  *slot = HTAB_DELETED_ENTRY;
+  htab->n_deleted++;
+}
+
+
+/* This function deletes an element with the given COMPARABLE value
+   from hash table starting with the given HASH.  If there is no
+   matching element in the hash table, this function does nothing. */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+void
+typed_htab <Element, Hash, Equal, Remove, Allocator>
+::remove_elt_with_hash (Element *comparable, hashval_t hash)
+{
+  Element **slot;
+
+  slot = find_slot_with_hash (comparable, hash, NO_INSERT);
+  if (*slot == HTAB_EMPTY_ENTRY)
+    return;
+
+  Remove (*slot);
+
+  *slot = static_cast <Element *> (HTAB_DELETED_ENTRY);
+  htab->n_deleted++;
+}
+
+
+/* This function scans over the entire hash table calling CALLBACK for
+   each live entry.  If CALLBACK returns false, the iteration stops.
+   ARGUMENT is passed as CALLBACK's second argument. */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+template <typename Argument,
+	  int (*Callback) (Element **slot, Argument argument)>
+void
+typed_htab <Element, Hash, Equal, Remove, Allocator>
+::traverse_noresize (Argument argument)
+{
+  Element **slot;
+  Element **limit;
+
+  slot = htab->entries;
+  limit = slot + htab->size;
+
+  do
+    {
+      Element *x = *slot;
+
+      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
+        if (! Callback (slot, argument))
+          break;
+    }
+  while (++slot < limit);
+}
+
+
+/* Like traverse_noresize, but does resize the table when it is too empty
+   to improve effectivity of subsequent calls.  */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+template <typename Argument,
+	  int (*Callback) (Element **slot, Argument argument)>
+void
+typed_htab <Element, Hash, Equal, Remove, Allocator>
+::traverse (Argument argument)
+{
+  size_t size = htab->size;
+  if (elements () * 8 < size && size > 32)
+    expand ();
+
+  traverse_noresize <Argument, Callback> (argument);
+}
+
+#endif /* TYPED_HASHTAB_H */
Index: gcc/tree-ssa-ccp.c
===================================================================
--- gcc/tree-ssa-ccp.c	(revision 187816)
+++ gcc/tree-ssa-ccp.c	(working copy)
@@ -134,6 +134,7 @@ along with GCC; see the file COPYING3.  
 #include "dbgcnt.h"
 #include "gimple-fold.h"
 #include "params.h"
+#include "typed-hashtab.h"
 
 
 /* Possible lattice values.  */
@@ -1686,11 +1687,17 @@ evaluate_stmt (gimple stmt)
   return val;
 }
 
+typedef typed_htab <gimple_statement_d,
typed_pointer_hash<gimple_statement_d>,
+		    typed_pointer_equal<gimple_statement_d>,
+		    typed_null_remove<gimple_statement_d> >
+		   gimple_htab;
+
 /* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
    each matching BUILT_IN_STACK_RESTORE.  Mark visited phis in VISITED.  */
 
 static void
-insert_clobber_before_stack_restore (tree saved_val, tree var, htab_t
*visited)
+insert_clobber_before_stack_restore (tree saved_val, tree var,
+				     gimple_htab *visited)
 {
   gimple stmt, clobber_stmt;
   tree clobber;
@@ -1710,10 +1717,10 @@ insert_clobber_before_stack_restore (tre
       }
     else if (gimple_code (stmt) == GIMPLE_PHI)
       {
-	if (*visited == NULL)
-	  *visited = htab_create (10, htab_hash_pointer, htab_eq_pointer, NULL);
+	if (!visited->is_created ())
+	  visited->create (10);
 
-	slot = (gimple *)htab_find_slot (*visited, stmt, INSERT);
+	slot = visited->find_slot (stmt, INSERT);
 	if (*slot != NULL)
 	  continue;
 
@@ -1756,7 +1763,7 @@ insert_clobbers_for_var (gimple_stmt_ite
 {
   gimple stmt;
   tree saved_val;
-  htab_t visited = NULL;
+  gimple_htab visited;
 
   for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i))
     {
@@ -1773,8 +1780,8 @@ insert_clobbers_for_var (gimple_stmt_ite
       break;
     }
 
-  if (visited != NULL)
-    htab_delete (visited);
+  if (visited.is_created ())
+    visited.dispose ();
 }
 
 /* Detects a __builtin_alloca_with_align with constant size argument. 
Declares
Index: gcc/tree-ssa-coalesce.c
===================================================================
--- gcc/tree-ssa-coalesce.c	(revision 187816)
+++ gcc/tree-ssa-coalesce.c	(working copy)
@@ -28,7 +28,7 @@ along with GCC; see the file COPYING3.  
 #include "tree-pretty-print.h"
 #include "bitmap.h"
 #include "tree-flow.h"
-#include "hashtab.h"
+#include "typed-hashtab.h"
 #include "tree-dump.h"
 #include "tree-ssa-live.h"
 #include "diagnostic-core.h"
@@ -1324,22 +1324,19 @@ coalesce_partitions (var_map map, ssa_co
     }
 }
 
-/* Returns a hash code for P.  */
+/* Returns a hash code for N.  */
 
-static hashval_t
-hash_ssa_name_by_var (const void *p)
+inline hashval_t
+hash_ssa_name_by_var (const_tree n)
 {
-  const_tree n = (const_tree) p;
   return (hashval_t) htab_hash_pointer (SSA_NAME_VAR (n));
 }
 
-/* Returns nonzero if P1 and P2 are equal.  */
+/* Returns nonzero if N1 and N2 are equal.  */
 
-static int
-eq_ssa_name_by_var (const void *p1, const void *p2)
+inline int
+eq_ssa_name_by_var (const_tree n1, const_tree n2)
 {
-  const_tree n1 = (const_tree) p1;
-  const_tree n2 = (const_tree) p2;
   return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
 }
 
@@ -1355,7 +1352,9 @@ coalesce_ssa_name (void)
   bitmap used_in_copies = BITMAP_ALLOC (NULL);
   var_map map;
   unsigned int i;
-  static htab_t ssa_name_hash;
+  static typed_htab <tree_node, hash_ssa_name_by_var, eq_ssa_name_by_var,
+		     typed_null_remove<tree_node> >
+		    ssa_name_hash;
 
   cl = create_coalesce_list ();
   map = create_outofssa_var_map (cl, used_in_copies);
@@ -1364,8 +1363,7 @@ coalesce_ssa_name (void)
      so debug info remains undisturbed.  */
   if (!optimize)
     {
-      ssa_name_hash = htab_create (10, hash_ssa_name_by_var,
-      				   eq_ssa_name_by_var, NULL);
+      ssa_name_hash.create (10);
       for (i = 1; i < num_ssa_names; i++)
 	{
 	  tree a = ssa_name (i);
@@ -1375,7 +1373,7 @@ coalesce_ssa_name (void)
 	      && !DECL_IGNORED_P (SSA_NAME_VAR (a))
 	      && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)))
 	    {
-	      tree *slot = (tree *) htab_find_slot (ssa_name_hash, a, INSERT);
+	      tree *slot = ssa_name_hash.find_slot (a, INSERT);
 
 	      if (!*slot)
 		*slot = a;
@@ -1388,7 +1386,7 @@ coalesce_ssa_name (void)
 		}
 	    }
 	}
-      htab_delete (ssa_name_hash);
+      ssa_name_hash.dispose ();
     }
   if (dump_file && (dump_flags & TDF_DETAILS))
     dump_var_map (dump_file, map);
Index: gcc/coverage.c
===================================================================
--- gcc/coverage.c	(revision 187816)
+++ gcc/coverage.c	(working copy)
@@ -43,7 +43,7 @@ along with GCC; see the file COPYING3.  
 #include "ggc.h"
 #include "coverage.h"
 #include "langhooks.h"
-#include "hashtab.h"
+#include "typed-hashtab.h"
 #include "tree-iterator.h"
 #include "cgraph.h"
 #include "tree-pass.h"
@@ -104,17 +104,11 @@ static char *bbg_file_name;
 /* Name of the count data file.  */
 static char *da_file_name;
 
-/* Hash table of count data.  */
-static htab_t counts_hash = NULL;
-
 /* The names of merge functions for counters.  */
 static const char *const ctr_merge_functions[GCOV_COUNTERS] =
GCOV_MERGE_FUNCTIONS;
 static const char *const ctr_names[GCOV_COUNTERS] = GCOV_COUNTER_NAMES;
 
 /* Forward declarations.  */
-static hashval_t htab_counts_entry_hash (const void *);
-static int htab_counts_entry_eq (const void *, const void *);
-static void htab_counts_entry_del (void *);
 static void read_counts_file (void);
 static tree build_var (tree, tree, int);
 static void build_fn_info_type (tree, unsigned, tree);
@@ -144,32 +138,31 @@ get_gcov_unsigned_t (void)
   return lang_hooks.types.type_for_mode (mode, true);
 }
 
-static hashval_t
-htab_counts_entry_hash (const void *of)
+inline hashval_t
+coverage_counts_entry_hash (const counts_entry_t *entry)
 {
-  const counts_entry_t *const entry = (const counts_entry_t *) of;
-
   return entry->ident * GCOV_COUNTERS + entry->ctr;
 }
 
-static int
-htab_counts_entry_eq (const void *of1, const void *of2)
+inline int
+coverage_counts_entry_eq (const counts_entry_t *entry1,
+                          const counts_entry_t *entry2)
 {
-  const counts_entry_t *const entry1 = (const counts_entry_t *) of1;
-  const counts_entry_t *const entry2 = (const counts_entry_t *) of2;
-
   return entry1->ident == entry2->ident && entry1->ctr == entry2->ctr;
 }
 
-static void
-htab_counts_entry_del (void *of)
+inline void
+coverage_counts_entry_del (counts_entry_t *entry)
 {
-  counts_entry_t *const entry = (counts_entry_t *) of;
-
   free (entry->counts);
   free (entry);
 }
 
+/* Hash table of count data.  */
+static typed_htab <counts_entry_t, coverage_counts_entry_hash,
+		   coverage_counts_entry_eq, coverage_counts_entry_del>
+		  counts_hash;
+
 /* Read in the counts file, if available.  */
 
 static void
@@ -208,9 +201,7 @@ read_counts_file (void)
   /* Read and discard the stamp.  */
   gcov_read_unsigned ();
 
-  counts_hash = htab_create (10,
-			     htab_counts_entry_hash, htab_counts_entry_eq,
-			     htab_counts_entry_del);
+  counts_hash.create (10);
   while ((tag = gcov_read_unsigned ()))
     {
       gcov_unsigned_t length;
@@ -258,8 +249,7 @@ read_counts_file (void)
 	  elt.ident = fn_ident;
 	  elt.ctr = GCOV_COUNTER_FOR_TAG (tag);
 
-	  slot = (counts_entry_t **) htab_find_slot
-	    (counts_hash, &elt, INSERT);
+	  slot = counts_hash.find_slot (&elt, INSERT);
 	  entry = *slot;
 	  if (!entry)
 	    {
@@ -279,14 +269,14 @@ read_counts_file (void)
 	      error ("checksum is (%x,%x) instead of (%x,%x)",
 		     entry->lineno_checksum, entry->cfg_checksum,
 		     lineno_checksum, cfg_checksum);
-	      htab_delete (counts_hash);
+	      counts_hash.dispose ();
 	      break;
 	    }
 	  else if (entry->summary.num != n_counts)
 	    {
 	      error ("Profile data for function %u is corrupted", fn_ident);
 	      error ("number of counters is %d instead of %d", entry->summary.num,
n_counts);
-	      htab_delete (counts_hash);
+	      counts_hash.dispose ();
 	      break;
 	    }
 	  else if (elt.ctr >= GCOV_COUNTERS_SUMMABLE)
@@ -312,7 +302,7 @@ read_counts_file (void)
 	{
 	  error (is_error < 0 ? "%qs has overflowed" : "%qs is corrupted",
 		 da_file_name);
-	  htab_delete (counts_hash);
+	  counts_hash.dispose ();
 	  break;
 	}
     }
@@ -330,7 +320,7 @@ get_coverage_counts (unsigned counter, u
   counts_entry_t *entry, elt;
 
   /* No hash table, no counts.  */
-  if (!counts_hash)
+  if (!counts_hash.is_created ())
     {
       static int warned = 0;
 
@@ -344,7 +334,7 @@ get_coverage_counts (unsigned counter, u
 
   elt.ident = current_function_funcdef_no + 1;
   elt.ctr = counter;
-  entry = (counts_entry_t *) htab_find (counts_hash, &elt);
+  entry = counts_hash.find (&elt);
   if (!entry || !entry->summary.num)
     /* The function was not emitted, or is weak and not chosen in the
        final executable.  Silently fail, because there's nothing we
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c	(revision 187816)
+++ gcc/tree-ssa-pre.c	(working copy)
@@ -34,7 +34,7 @@ along with GCC; see the file COPYING3.  
 #include "tree-dump.h"
 #include "timevar.h"
 #include "fibheap.h"
-#include "hashtab.h"
+#include "typed-hashtab.h"
 #include "tree-iterator.h"
 #include "alloc-pool.h"
 #include "obstack.h"
@@ -181,12 +181,11 @@ typedef struct pre_expr_d
 #define PRE_EXPR_REFERENCE(e) (e)->u.reference
 #define PRE_EXPR_CONSTANT(e) (e)->u.constant
 
-static int
-pre_expr_eq (const void *p1, const void *p2)
-{
-  const struct pre_expr_d *e1 = (const struct pre_expr_d *) p1;
-  const struct pre_expr_d *e2 = (const struct pre_expr_d *) p2;
+/* Compare E1 and E1 for equality.  */
 
+inline int
+ssa_pre_expr_eq (const struct pre_expr_d *e1, const struct pre_expr_d *e2)
+{
   if (e1->kind != e2->kind)
     return false;
 
@@ -207,10 +206,11 @@ pre_expr_eq (const void *p1, const void 
     }
 }
 
-static hashval_t
-pre_expr_hash (const void *p1)
+/* Hash E.  */
+
+inline hashval_t
+ssa_pre_expr_hash (const struct pre_expr_d *e)
 {
-  const struct pre_expr_d *e = (const struct pre_expr_d *) p1;
   switch (e->kind)
     {
     case CONSTANT:
@@ -226,7 +226,6 @@ pre_expr_hash (const void *p1)
     }
 }
 
-
 /* Next global expression id number.  */
 static unsigned int next_expression_id;
 
@@ -234,7 +233,9 @@ static unsigned int next_expression_id;
 DEF_VEC_P (pre_expr);
 DEF_VEC_ALLOC_P (pre_expr, heap);
 static VEC(pre_expr, heap) *expressions;
-static htab_t expression_to_id;
+static typed_htab <pre_expr_d, ssa_pre_expr_hash, ssa_pre_expr_eq,
+		   typed_null_remove<pre_expr_d> >
+		  expression_to_id;
 static VEC(unsigned, heap) *name_to_id;
 
 /* Allocate an expression id for EXPR.  */
@@ -242,7 +243,7 @@ static VEC(unsigned, heap) *name_to_id;
 static inline unsigned int
 alloc_expression_id (pre_expr expr)
 {
-  void **slot;
+  struct pre_expr_d **slot;
   /* Make sure we won't overflow. */
   gcc_assert (next_expression_id + 1 > next_expression_id);
   expr->id = next_expression_id++;
@@ -260,7 +261,7 @@ alloc_expression_id (pre_expr expr)
     }
   else
     {
-      slot = htab_find_slot (expression_to_id, expr, INSERT);
+      slot = expression_to_id.find_slot (expr, INSERT);
       gcc_assert (!*slot);
       *slot = expr;
     }
@@ -278,7 +279,7 @@ get_expression_id (const pre_expr expr)
 static inline unsigned int
 lookup_expression_id (const pre_expr expr)
 {
-  void **slot;
+  struct pre_expr_d **slot;
 
   if (expr->kind == NAME)
     {
@@ -289,7 +290,7 @@ lookup_expression_id (const pre_expr exp
     }
   else
     {
-      slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
+      slot = expression_to_id.find_slot (expr, NO_INSERT);
       if (!slot)
 	return 0;
       return ((pre_expr)*slot)->id;
@@ -490,11 +491,6 @@ static bitmap need_eh_cleanup;
 /* Set of blocks with statements that have had their AB properties changed. 
*/
 static bitmap need_ab_cleanup;
 
-/* The phi_translate_table caches phi translations for a given
-   expression and predecessor.  */
-
-static htab_t phi_translate_table;
-
 /* A three tuple {e, pred, v} used to cache phi translations in the
    phi_translate_table.  */
 
@@ -517,21 +513,19 @@ typedef const struct expr_pred_trans_d *
 
 /* Return the hash value for a phi translation table entry.  */
 
-static hashval_t
-expr_pred_trans_hash (const void *p)
+inline hashval_t
+ssa_expr_pred_trans_hash (const expr_pred_trans_d *ve)
 {
-  const_expr_pred_trans_t const ve = (const_expr_pred_trans_t) p;
   return ve->hashcode;
 }
 
 /* Return true if two phi translation table entries are the same.
    P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
 
-static int
-expr_pred_trans_eq (const void *p1, const void *p2)
+inline int
+ssa_expr_pred_trans_eq (const expr_pred_trans_d *ve1,
+			const expr_pred_trans_d *ve2)
 {
-  const_expr_pred_trans_t const ve1 = (const_expr_pred_trans_t) p1;
-  const_expr_pred_trans_t const ve2 = (const_expr_pred_trans_t) p2;
   basic_block b1 = ve1->pred;
   basic_block b2 = ve2->pred;
 
@@ -539,9 +533,17 @@ expr_pred_trans_eq (const void *p1, cons
      be equal.  */
   if (b1 != b2)
     return false;
-  return pre_expr_eq (ve1->e, ve2->e);
+  return ssa_pre_expr_eq (ve1->e, ve2->e);
 }
 
+/* The phi_translate_table caches phi translations for a given
+   expression and predecessor.  */
+
+static typed_htab <expr_pred_trans_d, ssa_expr_pred_trans_hash,
+		   ssa_expr_pred_trans_eq,
+		   typed_free_remove <expr_pred_trans_d> >
+		  phi_translate_table;
+
 /* Search in the phi translation table for the translation of
    expression E in basic block PRED.
    Return the translated value, if found, NULL otherwise.  */
@@ -549,18 +551,18 @@ expr_pred_trans_eq (const void *p1, cons
 static inline pre_expr
 phi_trans_lookup (pre_expr e, basic_block pred)
 {
-  void **slot;
+  expr_pred_trans_t *slot;
   struct expr_pred_trans_d ept;
 
   ept.e = e;
   ept.pred = pred;
-  ept.hashcode = iterative_hash_hashval_t (pre_expr_hash (e), pred->index);
-  slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
+  ept.hashcode = iterative_hash_hashval_t (ssa_pre_expr_hash (e),
pred->index);
+  slot = phi_translate_table.find_slot_with_hash (&ept, ept.hashcode,
 				   NO_INSERT);
   if (!slot)
     return NULL;
   else
-    return ((expr_pred_trans_t) *slot)->v;
+    return (*slot)->v;
 }
 
 
@@ -570,18 +572,18 @@ phi_trans_lookup (pre_expr e, basic_bloc
 static inline void
 phi_trans_add (pre_expr e, pre_expr v, basic_block pred)
 {
-  void **slot;
+  expr_pred_trans_t *slot;
   expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
   new_pair->e = e;
   new_pair->pred = pred;
   new_pair->v = v;
-  new_pair->hashcode = iterative_hash_hashval_t (pre_expr_hash (e),
+  new_pair->hashcode = iterative_hash_hashval_t (ssa_pre_expr_hash (e),
 						 pred->index);
 
-  slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
+  slot = phi_translate_table.find_slot_with_hash (new_pair,
 				   new_pair->hashcode, INSERT);
   free (*slot);
-  *slot = (void *) new_pair;
+  *slot = new_pair;
 }
 
 
@@ -3543,7 +3545,7 @@ do_regular_insertion (basic_block block,
 		    do_insertion = true;
 		  if (first_s == NULL)
 		    first_s = edoubleprime;
-		  else if (!pre_expr_eq (first_s, edoubleprime))
+		  else if (!ssa_pre_expr_eq (first_s, edoubleprime))
 		    all_same = false;
 		}
 	    }
@@ -4849,11 +4851,8 @@ init_pre (bool do_fre)
   calculate_dominance_info (CDI_DOMINATORS);
 
   bitmap_obstack_initialize (&grand_bitmap_obstack);
-  phi_translate_table = htab_create (5110, expr_pred_trans_hash,
-				     expr_pred_trans_eq, free);
-  expression_to_id = htab_create (num_ssa_names * 3,
-				  pre_expr_hash,
-				  pre_expr_eq, NULL);
+  phi_translate_table.create (5110);
+  expression_to_id.create (num_ssa_names * 3);
   bitmap_set_pool = create_alloc_pool ("Bitmap sets",
 				       sizeof (struct bitmap_set), 30);
   pre_expr_pool = create_alloc_pool ("pre_expr nodes",
@@ -4886,8 +4885,8 @@ fini_pre (bool do_fre)
   bitmap_obstack_release (&grand_bitmap_obstack);
   free_alloc_pool (bitmap_set_pool);
   free_alloc_pool (pre_expr_pool);
-  htab_delete (phi_translate_table);
-  htab_delete (expression_to_id);
+  phi_translate_table.dispose ();
+  expression_to_id.dispose ();
   VEC_free (unsigned, heap, name_to_id);
 
   free_aux_for_blocks ();
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 187816)
+++ gcc/Makefile.in	(working copy)
@@ -840,6 +840,7 @@ endif
 
 # Shorthand variables for dependency lists.
 VEC_H = vec.h statistics.h
+TYPED_HASHTAB_H = $(HASHTAB_H) typed-hashtab.h
 EXCEPT_H = except.h $(HASHTAB_H) vecprim.h vecir.h
 TARGET_DEF = target.def target-hooks-macros.h
 C_TARGET_DEF = c-family/c-target.def target-hooks-macros.h
@@ -1470,7 +1471,8 @@ OBJS-libcommon = diagnostic.o pretty-pri
 # Objects in libcommon-target.a, used by drivers and by the core
 # compiler and containing target-dependent code.
 OBJS-libcommon-target = $(common_out_object_file) prefix.o params.o \
-	opts.o opts-common.o options.o vec.o hooks.o common/common-targhooks.o
+	opts.o opts-common.o options.o vec.o hooks.o common/common-targhooks.o \
+	typed-hashtab.o
 
 # This lists all host objects for the front ends.
 ALL_HOST_FRONTEND_OBJS = $(C_OBJS) \
@@ -2302,7 +2304,7 @@ stor-layout.o : stor-layout.c $(CONFIG_H
 tree-ssa-tail-merge.o: tree-ssa-tail-merge.c \
    $(SYSTEM_H) $(CONFIG_H) coretypes.h $(TM_H) $(BITMAP_H) \
    $(FLAGS_H) $(TM_P_H) $(BASIC_BLOCK_H) output.h \
-   $(TREE_H) $(TREE_FLOW_H) $(TREE_INLINE_H) \
+   $(TREE_H) $(TREE_FLOW_H) $(TREE_INLINE_H) $(TYPED_HASHTAB_H) \
    $(GIMPLE_H) $(FUNCTION_H) \
    $(TIMEVAR_H) tree-ssa-sccvn.h \
    $(CGRAPH_H) gimple-pretty-print.h tree-pretty-print.h $(PARAMS_H)
@@ -2339,7 +2341,7 @@ tree-ssa-ter.o : tree-ssa-ter.c $(TREE_F
    gimple-pretty-print.h
 tree-ssa-coalesce.o : tree-ssa-coalesce.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(TREE_H) $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
-   $(TREE_SSA_LIVE_H) $(BITMAP_H) $(FLAGS_H) $(HASHTAB_H) \
+   $(TREE_SSA_LIVE_H) $(BITMAP_H) $(FLAGS_H) $(TYPED_HASHTAB_H) \
    tree-pretty-print.h
 tree-outof-ssa.o : tree-outof-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
    $(TREE_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
@@ -2401,7 +2403,7 @@ tree-ssa-threadedge.o : tree-ssa-threade
    $(TREE_PASS_H) tree-ssa-propagate.h langhooks.h \
    $(PARAMS_H)
 tree-ssa-threadupdate.o : tree-ssa-threadupdate.c $(TREE_FLOW_H) $(CONFIG_H) \
-   $(SYSTEM_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h \
+   $(SYSTEM_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h $(TYPED_HASHTAB_H) \
    $(DIAGNOSTIC_H) $(FUNCTION_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
    $(BASIC_BLOCK_H) $(FLAGS_H) $(TREE_PASS_H) $(CFGLOOP_H)
 tree-ssanames.o : tree-ssanames.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
@@ -2423,7 +2425,7 @@ tree-ssa-copyrename.o : tree-ssa-copyren
 tree-ssa-pre.o : tree-ssa-pre.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(TREE_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) $(FIBHEAP_H) \
    $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_PASS_H) $(FLAGS_H) langhooks.h \
-   $(CFGLOOP_H) alloc-pool.h $(BASIC_BLOCK_H) $(BITMAP_H) $(HASHTAB_H) \
+   $(CFGLOOP_H) alloc-pool.h $(BASIC_BLOCK_H) $(BITMAP_H) $(TYPED_HASHTAB_H) \
    $(GIMPLE_H) $(TREE_INLINE_H) tree-iterator.h tree-ssa-sccvn.h $(PARAMS_H) \
    $(DBGCNT_H) tree-scalar-evolution.h tree-pretty-print.h \
    gimple-pretty-print.h
@@ -3020,8 +3022,9 @@ ipa-pure-const.o : ipa-pure-const.c $(CO
    gimple-pretty-print.h $(DATA_STREAMER_H) $(TREE_STREAMER_H)
 coverage.o : coverage.c $(GCOV_IO_H) $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    $(TM_H) $(RTL_H) $(TREE_H) $(FLAGS_H) output.h $(REGS_H) $(EXPR_H) \
-   $(FUNCTION_H) $(BASIC_BLOCK_H) toplev.h $(DIAGNOSTIC_CORE_H) $(GGC_H)
langhooks.h $(COVERAGE_H) \
-   $(HASHTAB_H) tree-iterator.h $(CGRAPH_H) $(TREE_PASS_H) gcov-io.c $(TM_P_H)
\
+   $(FUNCTION_H) $(BASIC_BLOCK_H) toplev.h $(DIAGNOSTIC_CORE_H) $(GGC_H) \
+   $(TYPED_HASHTAB_H) langhooks.h $(COVERAGE_H) \
+   tree-iterator.h $(CGRAPH_H) $(TREE_PASS_H) gcov-io.c $(TM_P_H) \
    $(DIAGNOSTIC_CORE_H) intl.h gt-coverage.h $(TARGET_H)
 cselib.o : cselib.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h $(RECOG_H) \
@@ -3094,7 +3097,8 @@ tree-ssa-ccp.o : tree-ssa-ccp.c $(TREE_F
    $(SYSTEM_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h \
    $(DIAGNOSTIC_H) $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h \
    $(TREE_DUMP_H) $(BASIC_BLOCK_H) $(TREE_PASS_H) langhooks.h  $(PARAMS_H) \
-   tree-ssa-propagate.h value-prof.h $(FLAGS_H) $(TARGET_H)
$(DIAGNOSTIC_CORE_H) \
+   tree-ssa-propagate.h value-prof.h $(FLAGS_H) $(TARGET_H) \
+   $(DIAGNOSTIC_CORE_H) $(TYPED_HASHTAB_H) \
    $(DBGCNT_H) tree-pretty-print.h gimple-pretty-print.h gimple-fold.h
 tree-ssa-strlen.o : tree-ssa-strlen.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    $(TREE_FLOW_H) $(TREE_PASS_H) domwalk.h alloc-pool.h tree-ssa-propagate.h \
@@ -3248,6 +3252,8 @@ bitmap.o : bitmap.c $(CONFIG_H) $(SYSTEM
    $(GGC_H) gt-bitmap.h $(BITMAP_H) $(OBSTACK_H) $(HASHTAB_H)
 vec.o : vec.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(VEC_H) $(GGC_H) \
    toplev.h $(DIAGNOSTIC_CORE_H) $(HASHTAB_H)
+typed-hashtab.o : typed-hashtab.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
+   $(HASHTAB_H)
 reload.o : reload.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_ERROR_H)
\
    $(FLAGS_H) output.h $(EXPR_H) $(OPTABS_H) reload.h $(RECOG_H) \
    hard-reg-set.h insn-config.h $(REGS_H) $(FUNCTION_H) real.h \

--
This patch is available for review at http://codereview.appspot.com/6244048

[jakub_redhat.com, 2012-05-25 06:25:28]

On Thu, May 24, 2012 at 09:43:42AM -0700, Lawrence Crowl wrote:
> Add a type-safe hash table, typed_htab.  Uses of this table replace
> uses of libiberty's htab_t.  The benefits include less boiler-plate
> code, full type safety, and improved performance.

You haven't looked at the most important problem of that approach -
code bloat.  hashtab.o .text is currently ~ 4KB on x86_64, in your version
only very small part out of it is shared.  In a cc1plus binary I count
roughly 179 htab_create{,_ggc} calls, ignoring the first parameter (initial
size) that is roughly 139 unique hash/eq/del fn combinations, thus you'll
end up with over hundred copies of most of the hashtab code, in many of the
cases performance critical and thus its I-cache friendliness is quite
important.

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

Ugh.  I guess the C++ way around this would be to put the functions into
anonymous namespace.

> +  /* Return the current size of this hash table.  */
> +
> +  size_t size()
> +  {
> +    return htab->size;
> +  }

(and various other places) - formatting is wrong, missing space between (.

> +void
> +typed_htab <Element, Hash, Equal, Remove, Allocator>
> +::dispose ()

Do we want to format methods this way?

	Jakub

[matz_suse.de, 2012-05-25 12:17:12]

Hi,

On Fri, 25 May 2012, Jakub Jelinek wrote:

> > +  /* Return the current size of this hash table.  */
> > +
> > +  size_t size()
> > +  {
> > +    return htab->size;
> > +  }
> 
> (and various other places) - formatting is wrong, missing space between (.

And it doesn't start at the first column, and type isn't on a separate 
line.  I realize that this is a member method, hence indenting and C GNU 
coding standards conflict, but the latter do have some nice properties 
(for instance that 'grep ^func_name *.c' finds only the definition, not 
all the calls to func_name).

I think we need a discussion about style, now that actually people are 
working on this.

> > +void
> > +typed_htab <Element, Hash, Equal, Remove, Allocator>
> > +::dispose ()
> 
> Do we want to format methods this way?

Don't know, but at least it starts at the first column, and grepping for 
^:: will give only C++ methods, 'grep -B1 ^::' even including class.  So 
it's no too horrible, despite the syntactic C++ noise.


Ciao,
Michael.

[Lawrence Crowl, 2012-05-25 21:05:12]

On 5/25/12, Michael Matz <matz@suse.de> wrote:
> On Fri, 25 May 2012, Jakub Jelinek wrote:
> > > +  /* Return the current size of this hash table.  */
> > > +
> > > +  size_t size()
> > > +  {
> > > +    return htab->size;
> > > +  }
> >
> > (and various other places) - formatting is wrong, missing space
> > between (.

Yes, an omission that's a consequence of dealing with several
coding conventions.

> And it doesn't start at the first column, and type isn't on a
> separate line.  I realize that this is a member method, hence
> indenting and C GNU coding standards conflict, but the latter do
> have some nice properties (for instance that 'grep ^func_name *.c'
> finds only the definition, not all the calls to func_name).

We can address this issue by requiring all function definitions
to appear outside the class definition.  The code is more verbose,
but livable.

> I think we need a discussion about style, now that actually people
> are working on this.

Yes.

> > > +void
> > > +typed_htab <Element, Hash, Equal, Remove, Allocator>
> > > +::dispose ()
> >
> > Do we want to format methods this way?
>
> Don't know, but at least it starts at the first column, and
> grepping for ^:: will give only C++ methods, 'grep -B1 ^::' even
> including class.  So it's no too horrible, despite the syntactic
> C++ noise.

For template classes, the specification of an out-of-line member
function is going to be long, so a single-line specification is
likely to overflow often.  Whatever we chose, it should be reasonably
extended to multiple lines.

-- 
Lawrence Crowl

[Lawrence Crowl, 2012-05-25 21:42:39]

On 5/24/12, Jakub Jelinek <jakub@redhat.com> wrote:
> On Thu, May 24, 2012 at 09:43:42AM -0700, Lawrence Crowl wrote:
> > Add a type-safe hash table, typed_htab.  Uses of this table
> > replace uses of libiberty's htab_t.  The benefits include less
> > boiler-plate code, full type safety, and improved performance.
>
> You haven't looked at the most important problem of that approach
> - code bloat.

Are you claiming that the size of the binary is more important than
run-time performance, type safety, and source code size?

> hashtab.o .text is currently ~ 4KB on x86_64, in your version
> only very small part out of it is shared.  In a cc1plus binary
> I count roughly 179 htab_create{,_ggc} calls, ignoring the first
> parameter (initial size) that is roughly 139 unique hash/eq/del
> fn combinations, thus you'll end up with over hundred copies of
> most of the hashtab code,

First, the new hash table code is smaller because it avoid supporting
special cases that we are not using in practice.  What was formerly
conditional is now unconditional, leading to tighter binaries for
a given function.

As you say, there will be more functions in the source, leading to
an increased executable size.  Setting aside run-time performance,
why is that size important?

> in many of the cases performance critical and thus its I-cache
> friendliness is quite important.

It is precisely the performance critical code that needs the template
approach.  The approach avoids two indirect calls, which go across
translation units.  The optimizer has no ability to inline the often
trivial actions within those indirect calls.  This problem is most
severe in the traverse functions, because the optimize cannot see
enough to do anything useful with the loop.  The inliner also has no
ability to elide comparisons for null function pointers.  In short,
with the libiberty code, the operations must span a large number
of completely useless operations.  Those operations disappear with
the template approach.  The result is that the working set in the
cache is much smaller.

That said, if you think code size is important for tables that
are not performance critical, I can provide a version of the code
that simply reuses libiberty and gets the type safety without
the performance.  I don't have a good intuition for which of those
tables are performance-critical, so please give me an idea of which
they are.

-- 
Lawrence Crowl

[jakub_redhat.com, 2012-05-28 11:49:55]

On Fri, May 25, 2012 at 02:42:39PM -0700, Lawrence Crowl wrote:
> On 5/24/12, Jakub Jelinek <jakub@redhat.com> wrote:
> > On Thu, May 24, 2012 at 09:43:42AM -0700, Lawrence Crowl wrote:
> > > Add a type-safe hash table, typed_htab.  Uses of this table
> > > replace uses of libiberty's htab_t.  The benefits include less
> > > boiler-plate code, full type safety, and improved performance.
> >
> > You haven't looked at the most important problem of that approach
> > - code bloat.
> 
> Are you claiming that the size of the binary is more important than
> run-time performance, type safety, and source code size?

Runtime performance goes in hand with the size of the binary, at least
size of frequently used code.  By converting just a couple of hash tables
you can't really measure it, you'd need to convert a significant number of
them, then you can see what effect it has on runtime performance.
As said earlier, GCC has lots of hash tables, and many of them are used
in performance critical code, by increasing the I-cache footprint of
that performance criticial code there is risk of reducing performance.
The common C++ programming techniques often lead to significant code bloat
which really shouldn't be ignored.

	Jakub

[Lawrence Crowl, 2012-05-28 21:04:36]

On 5/28/12, Jakub Jelinek <jakub@redhat.com> wrote:
> On Fri, May 25, 2012 at 02:42:39PM -0700, Lawrence Crowl wrote:
> > On 5/24/12, Jakub Jelinek <jakub@redhat.com> wrote:
> > > On Thu, May 24, 2012 at 09:43:42AM -0700, Lawrence Crowl wrote:
> > > > Add a type-safe hash table, typed_htab.  Uses of this table
> > > > replace uses of libiberty's htab_t.  The benefits include
> > > > less boiler-plate code, full type safety, and improved
> > > > performance.
> > >
> > > You haven't looked at the most important problem of that
> > > approach - code bloat.
> >
> > Are you claiming that the size of the binary is more important
> > than run-time performance, type safety, and source code size?
>
> Runtime performance goes in hand with the size of the binary,
> at least size of frequently used code.

Well, yes and no.  We need to worry about total size, memory resident
size, and cache resident size.  The patch clearly increases total
size, but I doubt that is much of a factor because most systems
lazily load pages from the image.  I don't think we have enough
information to assess the memory resident size, and I don't think it
matters because large compilations are large because the data space
is much larger than the code space.  The patch reduces the cache
resident size because the dynamic path of instructions is shorter.

> By converting just a couple of hash tables you can't really
> measure it, you'd need to convert a significant number of them,
> then you can see what effect it has on runtime performance.

Well, I have a performance improvement with eight of them, of which
one isn't exercised in the bootstrap.

> As said earlier, GCC has lots of hash tables, and many of them
> are used in performance critical code, by increasing the I-cache
> footprint of that performance criticial code there is risk of
> reducing performance.  The common C++ programming techniques often
> lead to significant code bloat which really shouldn't be ignored.

But the patch potentially reduces the I-cache footprint.  The new
implementation eliminates pointer tests, it turns indirect
function calls into direct function calls, it enables inlining
those functions, etc.  If the compiler is suboptimal in dealing
with that, we should fix the compiler.  (I think the compiler is
behaving reasonably.)

If changing a table does not deliver performance, we can choose
not to convert that table.  We do not need to convert all of them.

-- 
Lawrence Crowl

[mikestump_comcast.net, 2012-05-29 11:50:47]

On May 25, 2012, at 2:42 PM, Lawrence Crowl wrote:
> On 5/24/12, Jakub Jelinek <jakub@redhat.com> wrote:
>> 
>> You haven't looked at the most important problem of that approach
>> - code bloat.
> 
> Are you claiming that the size of the binary is more important than
> run-time performance, type safety, and source code size?

I just look at it as a nice commoning problem in search of a nice solution.

[Lawrence Crowl, 2012-06-01 22:37:47]

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.


Index: gcc/tree-ssa-tail-merge.c
===================================================================
--- gcc/tree-ssa-tail-merge.c	(revision 188124)
+++ gcc/tree-ssa-tail-merge.c	(working copy)
@@ -196,7 +196,7 @@ along with GCC; see the file COPYING3.  
 #include "tree-ssa-alias.h"
 #include "params.h"
 #include "tree-pretty-print.h"
-#include "hashtab.h"
+#include "hash-table.h"
 #include "gimple-pretty-print.h"
 #include "tree-ssa-sccvn.h"
 #include "tree-dump.h"
@@ -367,11 +367,10 @@ same_succ_print (FILE *file, const same_
 
 /* Prints same_succ VE to VFILE.  */
 
-static int
-same_succ_print_traverse (void **ve, void *vfile)
+inline int
+ssa_same_succ_print_traverse (same_succ *pe, FILE *file)
 {
-  const same_succ e = *((const same_succ *)ve);
-  FILE *file = ((FILE*)vfile);
+  const same_succ e = *pe;
   same_succ_print (file, e);
   return 1;
 }
@@ -415,10 +414,9 @@ stmt_update_dep_bb (gimple stmt)
 
 /* Calculates hash value for same_succ VE.  */
 
-static hashval_t
-same_succ_hash (const void *ve)
+hashval_t
+ssa_same_succ_hash (const_same_succ e)
 {
-  const_same_succ e = (const_same_succ)ve;
   hashval_t hashval = bitmap_hash (e->succs);
   int flags;
   unsigned int i;
@@ -514,11 +512,9 @@ inverse_flags (const_same_succ e1, const
 
 /* Compares SAME_SUCCs VE1 and VE2.  */
 
-static int
-same_succ_equal (const void *ve1, const void *ve2)
+int
+ssa_same_succ_equal (const_same_succ e1, const_same_succ e2)
 {
-  const_same_succ e1 = (const_same_succ)ve1;
-  const_same_succ e2 = (const_same_succ)ve2;
   unsigned int i, first1, first2;
   gimple_stmt_iterator gsi1, gsi2;
   gimple s1, s2;
@@ -589,17 +585,15 @@ same_succ_alloc (void)
 
 /* Delete same_succ VE.  */
 
-static void
-same_succ_delete (void *ve)
+inline void
+ssa_same_succ_delete (same_succ e)
 {
-  same_succ e = (same_succ)ve;
-
   BITMAP_FREE (e->bbs);
   BITMAP_FREE (e->succs);
   BITMAP_FREE (e->inverse);
   VEC_free (int, heap, e->succ_flags);
 
-  XDELETE (ve);
+  XDELETE (e);
 }
 
 /* Reset same_succ SAME.  */
@@ -615,7 +609,9 @@ same_succ_reset (same_succ same)
 
 /* Hash table with all same_succ entries.  */
 
-static htab_t same_succ_htab;
+static hash_table <struct same_succ_def, ssa_same_succ_hash,
+		   ssa_same_succ_equal, ssa_same_succ_delete>
+		  same_succ_htab;
 
 /* Array that is used to store the edge flags for a successor.  */
 
@@ -636,7 +632,7 @@ extern void debug_same_succ (void);
 DEBUG_FUNCTION void
 debug_same_succ ( void)
 {
-  htab_traverse (same_succ_htab, same_succ_print_traverse, stderr);
+  same_succ_htab.traverse <FILE *, ssa_same_succ_print_traverse> (stderr);
 }
 
 DEF_VEC_P (same_succ);
@@ -695,10 +691,9 @@ find_same_succ_bb (basic_block bb, same_
   EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
     VEC_safe_push (int, heap, same->succ_flags, same_succ_edge_flags[j]);
 
-  same->hashval = same_succ_hash (same);
+  same->hashval = ssa_same_succ_hash (same);
 
-  slot = (same_succ *) htab_find_slot_with_hash (same_succ_htab, same,
-						   same->hashval, INSERT);
+  slot = same_succ_htab.find_slot_with_hash (same, same->hashval, INSERT);
   if (*slot == NULL)
     {
       *slot = same;
@@ -732,7 +727,7 @@ find_same_succ (void)
 	same = same_succ_alloc ();
     }
 
-  same_succ_delete (same);
+  ssa_same_succ_delete (same);
 }
 
 /* Initializes worklist administration.  */
@@ -741,9 +736,7 @@ static void
 init_worklist (void)
 {
   alloc_aux_for_blocks (sizeof (struct aux_bb_info));
-  same_succ_htab
-    = htab_create (n_basic_blocks, same_succ_hash, same_succ_equal,
-		   same_succ_delete);
+  same_succ_htab.create (n_basic_blocks);
   same_succ_edge_flags = XCNEWVEC (int, last_basic_block);
   deleted_bbs = BITMAP_ALLOC (NULL);
   deleted_bb_preds = BITMAP_ALLOC (NULL);
@@ -763,8 +756,7 @@ static void
 delete_worklist (void)
 {
   free_aux_for_blocks ();
-  htab_delete (same_succ_htab);
-  same_succ_htab = NULL;
+  same_succ_htab.dispose ();
   XDELETEVEC (same_succ_edge_flags);
   same_succ_edge_flags = NULL;
   BITMAP_FREE (deleted_bbs);
@@ -794,7 +786,7 @@ same_succ_flush_bb (basic_block bb)
   same_succ same = BB_SAME_SUCC (bb);
   BB_SAME_SUCC (bb) = NULL;
   if (bitmap_single_bit_set_p (same->bbs))
-    htab_remove_elt_with_hash (same_succ_htab, same, same->hashval);
+    same_succ_htab.remove_elt_with_hash (same, same->hashval);
   else
     bitmap_clear_bit (same->bbs, bb->index);
 }
@@ -867,7 +859,7 @@ update_worklist (void)
       if (same == NULL)
 	same = same_succ_alloc ();
     }
-  same_succ_delete (same);
+  ssa_same_succ_delete (same);
   bitmap_clear (deleted_bb_preds);
 }
 
@@ -1628,7 +1620,7 @@ tail_merge_optimize (unsigned int todo)
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "htab collision / search: %f\n",
-	     htab_collisions (same_succ_htab));
+	     same_succ_htab.collisions ());
 
   if (nr_bbs_removed_total > 0)
     {
Index: gcc/tree-ssa-threadupdate.c
===================================================================
--- gcc/tree-ssa-threadupdate.c	(revision 188124)
+++ gcc/tree-ssa-threadupdate.c	(working copy)
@@ -32,6 +32,7 @@ along with GCC; see the file COPYING3.  
 #include "tree-dump.h"
 #include "tree-pass.h"
 #include "cfgloop.h"
+#include "hash-table.h"
 
 /* Given a block B, update the CFG and SSA graph to reflect redirecting
    one or more in-edges to B to instead reach the destination of an
@@ -128,11 +129,8 @@ struct redirection_data
   struct el *incoming_edges;
 };
 
-/* Main data structure to hold information for duplicates of BB.  */
-static htab_t redirection_data;
-
 /* Data structure of information to pass to hash table traversal routines.  */
-struct local_info
+struct ssa_local_info_t
 {
   /* The current block we are working on.  */
   basic_block bb;
@@ -222,24 +220,32 @@ create_block_for_threading (basic_block 
 }
 
 /* Hashing and equality routines for our hash table.  */
-static hashval_t
-redirection_data_hash (const void *p)
+inline hashval_t
+ssa_redirection_data_hash (const struct redirection_data *p)
 {
-  edge e = ((const struct redirection_data *)p)->outgoing_edge;
+  edge e = p->outgoing_edge;
   return e->dest->index;
 }
 
-static int
-redirection_data_eq (const void *p1, const void *p2)
+inline int
+ssa_redirection_data_eq (const struct redirection_data *p1,
+			 const struct redirection_data *p2)
 {
-  edge e1 = ((const struct redirection_data *)p1)->outgoing_edge;
-  edge e2 = ((const struct redirection_data *)p2)->outgoing_edge;
-  edge e3 = ((const struct redirection_data *)p1)->intermediate_edge;
-  edge e4 = ((const struct redirection_data *)p2)->intermediate_edge;
+  edge e1 = p1->outgoing_edge;
+  edge e2 = p2->outgoing_edge;
+  edge e3 = p1->intermediate_edge;
+  edge e4 = p2->intermediate_edge;
 
   return e1 == e2 && e3 == e4;
 }
 
+/* Main data structure to hold information for duplicates of BB.  */
+
+static hash_table <struct redirection_data, ssa_redirection_data_hash,
+		   ssa_redirection_data_eq,
+		   typed_free_remove<struct redirection_data> >
+		  redirection_data;
+
 /* Given an outgoing edge E lookup and return its entry in our hash table.
 
    If INSERT is true, then we insert the entry into the hash table if
@@ -249,7 +255,7 @@ redirection_data_eq (const void *p1, con
 static struct redirection_data *
 lookup_redirection_data (edge e, enum insert_option insert)
 {
-  void **slot;
+  struct redirection_data **slot;
   struct redirection_data *elt;
 
  /* Build a hash table element so we can see if E is already
@@ -261,7 +267,7 @@ lookup_redirection_data (edge e, enum in
   elt->dup_block = NULL;
   elt->incoming_edges = NULL;
 
-  slot = htab_find_slot (redirection_data, elt, insert);
+  slot = redirection_data.find_slot (elt, insert);
 
   /* This will only happen if INSERT is false and the entry is not
      in the hash table.  */
@@ -275,7 +281,7 @@ lookup_redirection_data (edge e, enum in
      INSERT is true.  */
   if (*slot == NULL)
     {
-      *slot = (void *)elt;
+      *slot = elt;
       elt->incoming_edges = XNEW (struct el);
       elt->incoming_edges->e = e;
       elt->incoming_edges->next = NULL;
@@ -289,7 +295,7 @@ lookup_redirection_data (edge e, enum in
       free (elt);
 
       /* Get the entry stored in the hash table.  */
-      elt = (struct redirection_data *) *slot;
+      elt = *slot;
 
       /* If insertion was requested, then we need to add INCOMING_EDGE
 	 to the list of incoming edges associated with E.  */
@@ -377,9 +383,9 @@ create_edge_and_update_destination_phis 
 
 /* Wire up the outgoing edges from the duplicate block and
    update any PHIs as needed.  */
-static void
-fix_duplicate_block_edges (struct redirection_data *rd,
-			   struct local_info *local_info)
+void
+ssa_fix_duplicate_block_edges (struct redirection_data *rd,
+			       ssa_local_info_t *local_info)
 {
   /* If we were threading through an joiner block, then we want
      to keep its control statement and redirect an outgoing edge.
@@ -414,11 +420,11 @@ fix_duplicate_block_edges (struct redire
 }
 /* Hash table traversal callback routine to create duplicate blocks.  */
 
-static int
-create_duplicates (void **slot, void *data)
+int
+ssa_create_duplicates (struct redirection_data **slot,
+		       ssa_local_info_t *local_info)
 {
-  struct redirection_data *rd = (struct redirection_data *) *slot;
-  struct local_info *local_info = (struct local_info *)data;
+  struct redirection_data *rd = *slot;
 
   /* Create a template block if we have not done so already.  Otherwise
      use the template to create a new block.  */
@@ -437,7 +443,7 @@ create_duplicates (void **slot, void *da
 
       /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
 	 block.   */
-      fix_duplicate_block_edges (rd, local_info);
+      ssa_fix_duplicate_block_edges (rd, local_info);
     }
 
   /* Keep walking the hash table.  */
@@ -448,11 +454,11 @@ create_duplicates (void **slot, void *da
    block creation.  This hash table traversal callback creates the
    outgoing edge for the template block.  */
 
-static int
-fixup_template_block (void **slot, void *data)
+inline int
+ssa_fixup_template_block (struct redirection_data **slot,
+			  ssa_local_info_t *local_info)
 {
-  struct redirection_data *rd = (struct redirection_data *) *slot;
-  struct local_info *local_info = (struct local_info *)data;
+  struct redirection_data *rd = *slot;
 
   /* If this is the template block halt the traversal after updating
      it appropriately.
@@ -463,7 +469,7 @@ fixup_template_block (void **slot, void 
      a new outgoing edge.  In both cases we may need to update PHIs.  */
   if (rd->dup_block && rd->dup_block == local_info->template_block)
     {
-      fix_duplicate_block_edges (rd, local_info);
+      ssa_fix_duplicate_block_edges (rd, local_info);
       return 0;
     }
 
@@ -473,11 +479,11 @@ fixup_template_block (void **slot, void 
 /* Hash table traversal callback to redirect each incoming edge
    associated with this hash table element to its new destination.  */
 
-static int
-redirect_edges (void **slot, void *data)
+int
+ssa_redirect_edges (struct redirection_data **slot,
+		    ssa_local_info_t *local_info)
 {
-  struct redirection_data *rd = (struct redirection_data *) *slot;
-  struct local_info *local_info = (struct local_info *)data;
+  struct redirection_data *rd = *slot;
   struct el *next, *el;
 
   /* Walk over all the incoming edges associated associated with this
@@ -596,17 +602,14 @@ thread_block (basic_block bb, bool noloo
      redirect to a duplicate of BB.  */
   edge e, e2;
   edge_iterator ei;
-  struct local_info local_info;
+  ssa_local_info_t local_info;
   struct loop *loop = bb->loop_father;
 
   /* To avoid scanning a linear array for the element we need we instead
      use a hash table.  For normal code there should be no noticeable
      difference.  However, if we have a block with a large number of
      incoming and outgoing edges such linear searches can get expensive.  */
-  redirection_data = htab_create (EDGE_COUNT (bb->succs),
-				  redirection_data_hash,
-				  redirection_data_eq,
-				  free);
+  redirection_data.create (EDGE_COUNT (bb->succs));
 
   /* If we thread the latch of the loop to its exit, the loop ceases to
      exist.  Make sure we do not restrict ourselves in order to preserve
@@ -680,24 +683,26 @@ thread_block (basic_block bb, bool noloo
   local_info.template_block = NULL;
   local_info.bb = bb;
   local_info.jumps_threaded = false;
-  htab_traverse (redirection_data, create_duplicates, &local_info);
+  redirection_data.traverse <ssa_local_info_t *, ssa_create_duplicates>
+			    (&local_info);
 
   /* The template does not have an outgoing edge.  Create that outgoing
      edge and update PHI nodes as the edge's target as necessary.
 
      We do this after creating all the duplicates to avoid creating
      unnecessary edges.  */
-  htab_traverse (redirection_data, fixup_template_block, &local_info);
+  redirection_data.traverse <ssa_local_info_t *, ssa_fixup_template_block>
+			    (&local_info);
 
   /* The hash table traversals above created the duplicate blocks (and the
      statements within the duplicate blocks).  This loop creates PHI nodes for
      the duplicated blocks and redirects the incoming edges into BB to reach
      the duplicates of BB.  */
-  htab_traverse (redirection_data, redirect_edges, &local_info);
+  redirection_data.traverse <ssa_local_info_t *, ssa_redirect_edges>
+			    (&local_info);
 
   /* Done with this block.  Clear REDIRECTION_DATA.  */
-  htab_delete (redirection_data);
-  redirection_data = NULL;
+  redirection_data.dispose ();
 
   if (noloop_only
       && bb == bb->loop_father->header)
Index: gcc/tree-ssa-ccp.c
===================================================================
--- gcc/tree-ssa-ccp.c	(revision 188124)
+++ gcc/tree-ssa-ccp.c	(working copy)
@@ -134,6 +134,7 @@ along with GCC; see the file COPYING3.  
 #include "dbgcnt.h"
 #include "gimple-fold.h"
 #include "params.h"
+#include "hash-table.h"
 
 
 /* Possible lattice values.  */
@@ -1686,11 +1687,17 @@ evaluate_stmt (gimple stmt)
   return val;
 }
 
+typedef hash_table <gimple_statement_d,
typed_pointer_hash<gimple_statement_d>,
+		    typed_pointer_equal<gimple_statement_d>,
+		    typed_null_remove<gimple_statement_d> >
+		   gimple_htab;
+
 /* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
    each matching BUILT_IN_STACK_RESTORE.  Mark visited phis in VISITED.  */
 
 static void
-insert_clobber_before_stack_restore (tree saved_val, tree var, htab_t
*visited)
+insert_clobber_before_stack_restore (tree saved_val, tree var,
+				     gimple_htab *visited)
 {
   gimple stmt, clobber_stmt;
   tree clobber;
@@ -1710,10 +1717,10 @@ insert_clobber_before_stack_restore (tre
       }
     else if (gimple_code (stmt) == GIMPLE_PHI)
       {
-	if (*visited == NULL)
-	  *visited = htab_create (10, htab_hash_pointer, htab_eq_pointer, NULL);
+	if (!visited->is_created ())
+	  visited->create (10);
 
-	slot = (gimple *)htab_find_slot (*visited, stmt, INSERT);
+	slot = visited->find_slot (stmt, INSERT);
 	if (*slot != NULL)
 	  continue;
 
@@ -1756,7 +1763,7 @@ insert_clobbers_for_var (gimple_stmt_ite
 {
   gimple stmt;
   tree saved_val;
-  htab_t visited = NULL;
+  gimple_htab visited;
 
   for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i))
     {
@@ -1773,8 +1780,8 @@ insert_clobbers_for_var (gimple_stmt_ite
       break;
     }
 
-  if (visited != NULL)
-    htab_delete (visited);
+  if (visited.is_created ())
+    visited.dispose ();
 }
 
 /* Detects a __builtin_alloca_with_align with constant size argument. 
Declares
Index: gcc/hash-table.c
===================================================================
--- gcc/hash-table.c	(revision 0)
+++ gcc/hash-table.c	(revision 0)
@@ -0,0 +1,190 @@
+/* A type-safe hash table template.
+   Copyright (C) 2012
+   Free Software Foundation, Inc.
+   Contributed by Lawrence Crowl <crowl@google.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+
+/* This file implements a typed hash table.
+   The implementation borrows from libiberty's hashtab.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "hash-table.h"
+
+
+/* Table of primes and multiplicative inverses.
+
+   Note that these are not minimally reduced inverses.  Unlike when generating
+   code to divide by a constant, we want to be able to use the same algorithm
+   all the time.  All of these inverses (are implied to) have bit 32 set.
+
+   For the record, here's the function that computed the table; it's a 
+   vastly simplified version of the function of the same name from gcc.  */
+
+#if 0
+unsigned int
+ceil_log2 (unsigned int x)
+{
+  int i;
+  for (i = 31; i >= 0 ; --i)
+    if (x > (1u << i))
+      return i+1;
+  abort ();
+}
+
+unsigned int
+choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp)
+{
+  unsigned long long mhigh;
+  double nx;
+  int lgup, post_shift;
+  int pow, pow2;
+  int n = 32, precision = 32;
+
+  lgup = ceil_log2 (d);
+  pow = n + lgup;
+  pow2 = n + lgup - precision;
+
+  nx = ldexp (1.0, pow) + ldexp (1.0, pow2);
+  mhigh = nx / d;
+
+  *shiftp = lgup - 1;
+  *mlp = mhigh;
+  return mhigh >> 32;
+}
+#endif
+
+struct prime_ent const prime_tab[] = {
+  {          7, 0x24924925, 0x9999999b, 2 },
+  {         13, 0x3b13b13c, 0x745d1747, 3 },
+  {         31, 0x08421085, 0x1a7b9612, 4 },
+  {         61, 0x0c9714fc, 0x15b1e5f8, 5 },
+  {        127, 0x02040811, 0x0624dd30, 6 },
+  {        251, 0x05197f7e, 0x073260a5, 7 },
+  {        509, 0x01824366, 0x02864fc8, 8 },
+  {       1021, 0x00c0906d, 0x014191f7, 9 },
+  {       2039, 0x0121456f, 0x0161e69e, 10 },
+  {       4093, 0x00300902, 0x00501908, 11 },
+  {       8191, 0x00080041, 0x00180241, 12 },
+  {      16381, 0x000c0091, 0x00140191, 13 },
+  {      32749, 0x002605a5, 0x002a06e6, 14 },
+  {      65521, 0x000f00e2, 0x00110122, 15 },
+  {     131071, 0x00008001, 0x00018003, 16 },
+  {     262139, 0x00014002, 0x0001c004, 17 },
+  {     524287, 0x00002001, 0x00006001, 18 },
+  {    1048573, 0x00003001, 0x00005001, 19 },
+  {    2097143, 0x00004801, 0x00005801, 20 },
+  {    4194301, 0x00000c01, 0x00001401, 21 },
+  {    8388593, 0x00001e01, 0x00002201, 22 },
+  {   16777213, 0x00000301, 0x00000501, 23 },
+  {   33554393, 0x00001381, 0x00001481, 24 },
+  {   67108859, 0x00000141, 0x000001c1, 25 },
+  {  134217689, 0x000004e1, 0x00000521, 26 },
+  {  268435399, 0x00000391, 0x000003b1, 27 },
+  {  536870909, 0x00000019, 0x00000029, 28 },
+  { 1073741789, 0x0000008d, 0x00000095, 29 },
+  { 2147483647, 0x00000003, 0x00000007, 30 },
+  /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
+  { 0xfffffffb, 0x00000006, 0x00000008, 31 }
+};
+
+/* The following function returns an index into the above table of the
+   nearest prime number which is greater than N, and near a power of two. */
+
+unsigned int
+hash_table_higher_prime_index (unsigned long n)
+{
+  unsigned int low = 0;
+  unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);
+
+  while (low != high)
+    {
+      unsigned int mid = low + (high - low) / 2;
+      if (n > prime_tab[mid].prime)
+	low = mid + 1;
+      else
+	high = mid;
+    }
+
+  /* If we've run out of primes, abort.  */
+  if (n > prime_tab[low].prime)
+    {
+      fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
+      abort ();
+    }
+
+  return low;
+}
+
+/* Return X % Y using multiplicative inverse values INV and SHIFT.
+
+   The multiplicative inverses computed above are for 32-bit types,
+   and requires that we be able to compute a highpart multiply.
+
+   FIX: I am not at all convinced that
+     3 loads, 2 multiplications, 3 shifts, and 3 additions
+   will be faster than
+     1 load and 1 modulus
+   on modern systems running a compiler.  */
+
+#ifdef UNSIGNED_64BIT_TYPE
+static inline hashval_t
+mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift)
+{
+  __extension__ typedef UNSIGNED_64BIT_TYPE ull;
+   hashval_t t1, t2, t3, t4, q, r;
+
+   t1 = ((ull)x * inv) >> 32;
+   t2 = x - t1;
+   t3 = t2 >> 1;
+   t4 = t1 + t3;
+   q  = t4 >> shift;
+   r  = x - (q * y);
+
+   return r;
+}
+#endif
+
+/* Compute the primary table index for HASH given current prime index.  */
+
+hashval_t
+hash_table_mod1 (hashval_t hash, unsigned int index)
+{
+  const struct prime_ent *p = &prime_tab[index];
+#ifdef UNSIGNED_64BIT_TYPE
+  if (sizeof (hashval_t) * CHAR_BIT <= 32)
+    return mul_mod (hash, p->prime, p->inv, p->shift);
+#endif
+  return hash % p->prime;
+}
+
+
+/* Compute the secondary table index for HASH given current prime index.  */
+
+hashval_t
+hash_table_mod2 (hashval_t hash, unsigned int index)
+{
+  const struct prime_ent *p = &prime_tab[index];
+#ifdef UNSIGNED_64BIT_TYPE
+  if (sizeof (hashval_t) * CHAR_BIT <= 32)
+    return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift);
+#endif
+  return 1 + hash % (p->prime - 2);
+}
Index: gcc/hash-table.h
===================================================================
--- gcc/hash-table.h	(revision 0)
+++ gcc/hash-table.h	(revision 0)
@@ -0,0 +1,711 @@
+/* A type-safe hash table template.
+   Copyright (C) 2012
+   Free Software Foundation, Inc.
+   Contributed by Lawrence Crowl <crowl@google.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+
+/* This file implements a typed hash table.
+   The implementation borrows from libiberty's hashtab.  */
+
+
+#ifndef TYPED_HASHTAB_H
+#define TYPED_HASHTAB_H
+
+#include "hashtab.h"
+
+
+/* The ordinary memory allocator.  */
+/* FIXME (crowl): This allocator may be extracted for wider sharing later.  */
+
+template <typename Type>
+struct xcallocator
+{
+
+  /* Allocate memory for COUNT control blocks.  */
+
+  static Type *control_alloc (size_t count)
+  { return static_cast <Type *> (xcalloc (count, sizeof (Type))); }
+  
+
+  /* Allocate memory for COUNT data blocks.  */ 
+
+  static Type *data_alloc (size_t count)
+  { return static_cast <Type *> (xcalloc (count, sizeof (Type))); }
+
+
+  /* Free memory for control blocks.  */
+
+  static void control_free (Type *memory)
+  { return ::free (memory); }
+  
+  /* Free memory for data blocks.  */
+
+  static void data_free (Type *memory)
+  { return ::free (memory); }
+  
+};
+
+
+/* A common function for hashing a CANDIDATE typed pointer.  */
+
+template <typename Element>
+inline hashval_t
+typed_pointer_hash (const Element *candidate)
+{
+  /* This is a really poor hash function, but it is what the current code
uses,
+     so I am reusing it to avoid an additional axis in testing.  */
+  return (hashval_t) ((intptr_t)candidate >> 3);
+}
+
+
+/* A common function for comparing an EXISTING and CANDIDATE typed pointers
+   for equality. */
+
+template <typename Element>
+inline int
+typed_pointer_equal (const Element *existing, const Element * candidate)
+{
+  return existing == candidate;
+}
+
+
+/* A common function for doing nothing on removing a RETIRED slot.  */
+
+template <typename Element>
+inline void
+typed_null_remove (Element *retired ATTRIBUTE_UNUSED)
+{
+}
+
+
+/* A common function for using free on removing a RETIRED slot.  */
+
+template <typename Element>
+inline void
+typed_free_remove (Element *retired)
+{
+  free (retired);
+}
+
+
+/* Table of primes and their inversion information.  */
+
+struct prime_ent
+{
+  hashval_t prime;
+  hashval_t inv;
+  hashval_t inv_m2;     /* inverse of prime-2 */
+  hashval_t shift;
+};
+
+extern struct prime_ent const prime_tab[];
+
+
+/* Functions for computing hash table indexes.  */
+
+extern unsigned int hash_table_higher_prime_index (unsigned long n);
+extern hashval_t hash_table_mod1 (hashval_t hash, unsigned int index);
+extern hashval_t hash_table_mod2 (hashval_t hash, unsigned int index);
+
+
+/* Internal implementation type.  */
+
+template <typename Element>
+struct hash_table_control
+{
+  /* Table itself.  */
+  Element **entries;
+
+  /* Current size (in entries) of the hash table.  */
+  size_t size;
+
+  /* Current number of elements including also deleted elements.  */
+  size_t n_elements;
+
+  /* Current number of deleted elements in the table.  */
+  size_t n_deleted;
+
+  /* The following member is used for debugging. Its value is number
+     of all calls of `htab_find_slot' for the hash table. */
+  unsigned int searches;
+
+  /* The following member is used for debugging.  Its value is number
+     of collisions fixed for time of work with the hash table. */
+  unsigned int collisions;
+
+  /* Current size (in entries) of the hash table, as an index into the
+     table of primes.  */
+  unsigned int size_prime_index;
+};
+
+
+/* User-facing hash table type.
+
+   The table stores elements of type Element.
+
+   It hashes elements with the Hash function.
+     The table currently works with relatively weak hash functions.
+     Use typed_pointer_hash <Element> when hashing pointers instead of
objects.
+
+   It compares elements with the Equal function.
+     Two elements with the same hash may not be equal.
+     Use typed_pointer_equal <Element> when hashing pointers instead of
objects.
+
+   It removes elements with the Remove function.
+     This feature is useful for freeing memory.
+     Use typed_null_remove <Element> when not freeing objects.
+     Use typed_free_remove <Element> when doing a simple object free.
+
+   Use the Allocator template to allocate and free memory.
+     The default is xcallocator.
+
+*/
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator = xcallocator>
+struct hash_table
+{
+
+private:
+
+  hash_table_control <Element> *htab;
+
+
+  Element **find_empty_slot_for_expand (hashval_t hash);
+  void expand ();
+
+public:
+
+  void create (size_t initial_slots);
+  void dispose ();
+  Element *find_with_hash (Element *comparable, hashval_t hash);
+  Element **find_slot_with_hash (Element *comparable, hashval_t hash,
+				 enum insert_option insert);
+  void empty ();
+  void clear_slot (Element **slot);
+  void remove_elt_with_hash (Element *comparable, hashval_t hash);
+
+  template <typename Argument,
+	    int (*Callback) (Element **slot, Argument argument)>
+  void traverse_noresize (Argument argument);
+
+  template <typename Argument,
+	    int (*Callback) (Element **slot, Argument argument)>
+  void traverse (Argument argument);
+
+
+  /* Construct the hash table.  The only useful operation next is create.  */
+
+  hash_table ()
+  : htab (NULL)
+  {
+  }
+
+
+  /* See if the table has been created, as opposed to constructed.  */
+
+  bool is_created ()
+  {
+    return htab != NULL;
+  }
+
+
+  /* Like find_with_hash, but compute the hash value from the element.  */
+
+  Element *find (Element *comparable)
+  {
+    return find_with_hash (comparable, Hash (comparable));
+  }
+
+
+  /* Like find_slot_with_hash, but compute the hash value from the element. 
*/
+
+  Element **find_slot (Element *comparable, enum insert_option insert)
+  {
+    return find_slot_with_hash (comparable, Hash (comparable), insert);
+  }
+
+
+  /* Like remove_elt_with_hash, but compute the hash value from the element. 
*/
+
+  void remove_elt (Element *comparable)
+  {
+    remove_elt_with_hash (comparable, Hash (comparable));
+  }
+
+
+
+  /* Return the current size of this hash table.  */
+
+  size_t size()
+  {
+    return htab->size;
+  }
+
+
+  /* Return the current number of elements in this hash table. */
+
+  size_t elements()
+  {
+    return htab->n_elements - htab->n_deleted;
+  }
+
+
+  /* Return the fraction of fixed collisions during all work with given
+     hash table. */
+
+  double collisions()
+  {
+    if (htab->searches == 0)
+      return 0.0;
+
+    return static_cast <double> (htab->collisions) / htab->searches;
+  }
+
+};
+
+
+/* Create a hash table with at least the given number of INITIAL_SLOTS.  */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+void
+hash_table <Element, Hash, Equal, Remove, Allocator>
+::create (size_t size)
+{
+  unsigned int size_prime_index;
+
+  size_prime_index = hash_table_higher_prime_index (size);
+  size = prime_tab[size_prime_index].prime;
+
+  htab = Allocator <hash_table_control <Element> > ::control_alloc (1);
+  gcc_assert (htab != NULL);
+  htab->entries = Allocator <Element*> ::data_alloc (size);
+  gcc_assert (htab->entries != NULL);
+  htab->size = size;
+  htab->size_prime_index = size_prime_index;
+}
+
+
+/* Dispose of a hash table.  Free all memory and return this hash table to
+   the non-created state.  Naturally the hash table must already exist.  */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+void
+hash_table <Element, Hash, Equal, Remove, Allocator>
+::dispose ()
+{
+  size_t size = htab->size;
+  Element **entries = htab->entries;
+
+  for (int i = size - 1; i >= 0; i--)
+    if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
+      Remove (entries[i]);
+
+  Allocator <Element *> ::data_free (entries);
+  Allocator <hash_table_control <Element> > ::control_free (htab);
+  htab = NULL;
+}
+
+
+/* Similar to find_slot, but without several unwanted side effects:
+    - Does not call Equal when it finds an existing entry.
+    - Does not change the count of elements/searches/collisions in the
+      hash table.
+   This function also assumes there are no deleted entries in the table.
+   HASH is the hash value for the element to be inserted.  */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+Element **
+hash_table <Element, Hash, Equal, Remove, Allocator>
+::find_empty_slot_for_expand (hashval_t hash)
+{
+  hashval_t index = hash_table_mod1 (hash, htab->size_prime_index);
+  size_t size = htab->size;
+  Element **slot = htab->entries + index;
+  hashval_t hash2;
+
+  if (*slot == HTAB_EMPTY_ENTRY)
+    return slot;
+  else if (*slot == HTAB_DELETED_ENTRY)
+    abort ();
+
+  hash2 = hash_table_mod2 (hash, htab->size_prime_index);
+  for (;;)
+    {
+      index += hash2;
+      if (index >= size)
+        index -= size;
+
+      slot = htab->entries + index;
+      if (*slot == HTAB_EMPTY_ENTRY)
+        return slot;
+      else if (*slot == HTAB_DELETED_ENTRY)
+        abort ();
+    }
+}
+
+
+/* The following function changes size of memory allocated for the
+   entries and repeatedly inserts the table elements.  The occupancy
+   of the table after the call will be about 50%.  Naturally the hash
+   table must already exist.  Remember also that the place of the
+   table entries is changed.  If memory allocation fails, this function
+   will abort.  */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+void
+hash_table <Element, Hash, Equal, Remove, Allocator>
+::expand ()
+{
+  Element **oentries;
+  Element **olimit;
+  Element **p;
+  Element **nentries;
+  size_t nsize, osize, elts;
+  unsigned int oindex, nindex;
+
+  oentries = htab->entries;
+  oindex = htab->size_prime_index;
+  osize = htab->size;
+  olimit = oentries + osize;
+  elts = elements ();
+
+  /* Resize only when table after removal of unused elements is either
+     too full or too empty.  */
+  if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
+    {
+      nindex = hash_table_higher_prime_index (elts * 2);
+      nsize = prime_tab[nindex].prime;
+    }
+  else
+    {
+      nindex = oindex;
+      nsize = osize;
+    }
+
+  nentries = Allocator <Element *> ::data_alloc (nsize);
+  gcc_assert (nentries != NULL);
+  htab->entries = nentries;
+  htab->size = nsize;
+  htab->size_prime_index = nindex;
+  htab->n_elements -= htab->n_deleted;
+  htab->n_deleted = 0;
+
+  p = oentries;
+  do
+    {
+      Element *x = *p;
+
+      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
+        {
+          Element **q = find_empty_slot_for_expand (Hash (x));
+
+          *q = x;
+        }
+
+      p++;
+    }
+  while (p < olimit);
+
+  Allocator <Element *> ::data_free (oentries);
+}
+
+
+/* This function searches for a hash table entry equal to the given
+   COMPARABLE element starting with the given HASH value.  It cannot
+   be used to insert or delete an element. */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+Element *
+hash_table <Element, Hash, Equal, Remove, Allocator>
+::find_with_hash (Element *comparable, hashval_t hash)
+{
+  hashval_t index, hash2;
+  size_t size;
+  Element *entry;
+
+  htab->searches++;
+  size = htab->size;
+  index = hash_table_mod1 (hash, htab->size_prime_index);
+
+  entry = htab->entries[index];
+  if (entry == HTAB_EMPTY_ENTRY
+      || (entry != HTAB_DELETED_ENTRY && Equal (entry, comparable)))
+    return entry;
+
+  hash2 = hash_table_mod2 (hash, htab->size_prime_index);
+  for (;;)
+    {
+      htab->collisions++;
+      index += hash2;
+      if (index >= size)
+        index -= size;
+
+      entry = htab->entries[index];
+      if (entry == HTAB_EMPTY_ENTRY
+          || (entry != HTAB_DELETED_ENTRY && Equal (entry, comparable)))
+        return entry;
+    }
+}
+
+
+/* This function searches for a hash table slot containing an entry
+   equal to the given COMPARABLE element and starting with the given
+   HASH.  To delete an entry, call this with insert=NO_INSERT, then
+   call clear_slot on the slot returned (possibly after doing some
+   checks).  To insert an entry, call this with insert=INSERT, then
+   write the value you want into the returned slot.  When inserting an
+   entry, NULL may be returned if memory allocation fails. */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+Element **
+hash_table <Element, Hash, Equal, Remove, Allocator>
+::find_slot_with_hash (Element *comparable, hashval_t hash,
+		       enum insert_option insert)
+{
+  Element **first_deleted_slot;
+  hashval_t index, hash2;
+  size_t size;
+  Element *entry;
+
+  size = htab->size;
+  if (insert == INSERT && size * 3 <= htab->n_elements * 4)
+    {
+      expand ();
+      size = htab->size;
+    }
+
+  index = hash_table_mod1 (hash, htab->size_prime_index);
+
+  htab->searches++;
+  first_deleted_slot = NULL;
+
+  entry = htab->entries[index];
+  if (entry == HTAB_EMPTY_ENTRY)
+    goto empty_entry;
+  else if (entry == HTAB_DELETED_ENTRY)
+    first_deleted_slot = &htab->entries[index];
+  else if (Equal (entry, comparable))
+    return &htab->entries[index];
+      
+  hash2 = hash_table_mod2 (hash, htab->size_prime_index);
+  for (;;)
+    {
+      htab->collisions++;
+      index += hash2;
+      if (index >= size)
+	index -= size;
+      
+      entry = htab->entries[index];
+      if (entry == HTAB_EMPTY_ENTRY)
+	goto empty_entry;
+      else if (entry == HTAB_DELETED_ENTRY)
+	{
+	  if (!first_deleted_slot)
+	    first_deleted_slot = &htab->entries[index];
+	}
+      else if (Equal (entry, comparable))
+	return &htab->entries[index];
+    }
+
+ empty_entry:
+  if (insert == NO_INSERT)
+    return NULL;
+
+  if (first_deleted_slot)
+    {
+      htab->n_deleted--;
+      *first_deleted_slot = static_cast <Element *> (HTAB_EMPTY_ENTRY);
+      return first_deleted_slot;
+    }
+
+  htab->n_elements++;
+  return &htab->entries[index];
+}
+
+
+/* This function clears all entries in the given hash table.  */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+void
+hash_table <Element, Hash, Equal, Remove, Allocator>
+::empty ()
+{
+  size_t size = htab_size (htab);
+  Element **entries = htab->entries;
+  int i;
+
+  for (i = size - 1; i >= 0; i--)
+    if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
+      Remove (entries[i]);
+
+  /* Instead of clearing megabyte, downsize the table.  */
+  if (size > 1024*1024 / sizeof (PTR))
+    {
+      int nindex = hash_table_higher_prime_index (1024 / sizeof (PTR));
+      int nsize = prime_tab[nindex].prime;
+
+      Allocator <Element *> ::data_free (htab->entries);
+      htab->entries = Allocator <Element *> ::data_alloc (nsize);
+      htab->size = nsize;
+      htab->size_prime_index = nindex;
+    }
+  else
+    memset (entries, 0, size * sizeof (Element *));
+  htab->n_deleted = 0;
+  htab->n_elements = 0;
+}
+
+
+/* This function clears a specified SLOT in a hash table.  It is
+   useful when you've already done the lookup and don't want to do it
+   again. */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+void
+hash_table <Element, Hash, Equal, Remove, Allocator>
+::clear_slot (Element **slot)
+{
+  if (slot < htab->entries || slot >= htab->entries + htab->size
+      || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
+    abort ();
+
+  Remove (*slot);
+
+  *slot = HTAB_DELETED_ENTRY;
+  htab->n_deleted++;
+}
+
+
+/* This function deletes an element with the given COMPARABLE value
+   from hash table starting with the given HASH.  If there is no
+   matching element in the hash table, this function does nothing. */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+void
+hash_table <Element, Hash, Equal, Remove, Allocator>
+::remove_elt_with_hash (Element *comparable, hashval_t hash)
+{
+  Element **slot;
+
+  slot = find_slot_with_hash (comparable, hash, NO_INSERT);
+  if (*slot == HTAB_EMPTY_ENTRY)
+    return;
+
+  Remove (*slot);
+
+  *slot = static_cast <Element *> (HTAB_DELETED_ENTRY);
+  htab->n_deleted++;
+}
+
+
+/* This function scans over the entire hash table calling CALLBACK for
+   each live entry.  If CALLBACK returns false, the iteration stops.
+   ARGUMENT is passed as CALLBACK's second argument. */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+template <typename Argument,
+	  int (*Callback) (Element **slot, Argument argument)>
+void
+hash_table <Element, Hash, Equal, Remove, Allocator>
+::traverse_noresize (Argument argument)
+{
+  Element **slot;
+  Element **limit;
+
+  slot = htab->entries;
+  limit = slot + htab->size;
+
+  do
+    {
+      Element *x = *slot;
+
+      if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
+        if (! Callback (slot, argument))
+          break;
+    }
+  while (++slot < limit);
+}
+
+
+/* Like traverse_noresize, but does resize the table when it is too empty
+   to improve effectivity of subsequent calls.  */
+
+template <typename Element,
+	  hashval_t (*Hash) (const Element *candidate),
+	  int (*Equal) (const Element *existing, const Element * candidate),
+	  void (*Remove) (Element *retired),
+	  template <typename Type> class Allocator>
+template <typename Argument,
+	  int (*Callback) (Element **slot, Argument argument)>
+void
+hash_table <Element, Hash, Equal, Remove, Allocator>
+::traverse (Argument argument)
+{
+  size_t size = htab->size;
+  if (elements () * 8 < size && size > 32)
+    expand ();
+
+  traverse_noresize <Argument, Callback> (argument);
+}
+
+#endif /* TYPED_HASHTAB_H */
Index: gcc/tree-ssa-coalesce.c
===================================================================
--- gcc/tree-ssa-coalesce.c	(revision 188124)
+++ gcc/tree-ssa-coalesce.c	(working copy)
@@ -28,7 +28,7 @@ along with GCC; see the file COPYING3.  
 #include "tree-pretty-print.h"
 #include "bitmap.h"
 #include "tree-flow.h"
-#include "hashtab.h"
+#include "hash-table.h"
 #include "tree-dump.h"
 #include "tree-ssa-live.h"
 #include "diagnostic-core.h"
@@ -1324,22 +1324,19 @@ coalesce_partitions (var_map map, ssa_co
     }
 }
 
-/* Returns a hash code for P.  */
+/* Returns a hash code for N.  */
 
-static hashval_t
-hash_ssa_name_by_var (const void *p)
+inline hashval_t
+hash_ssa_name_by_var (const_tree n)
 {
-  const_tree n = (const_tree) p;
   return (hashval_t) htab_hash_pointer (SSA_NAME_VAR (n));
 }
 
-/* Returns nonzero if P1 and P2 are equal.  */
+/* Returns nonzero if N1 and N2 are equal.  */
 
-static int
-eq_ssa_name_by_var (const void *p1, const void *p2)
+inline int
+eq_ssa_name_by_var (const_tree n1, const_tree n2)
 {
-  const_tree n1 = (const_tree) p1;
-  const_tree n2 = (const_tree) p2;
   return SSA_NAME_VAR (n1) == SSA_NAME_VAR (n2);
 }
 
@@ -1355,7 +1352,9 @@ coalesce_ssa_name (void)
   bitmap used_in_copies = BITMAP_ALLOC (NULL);
   var_map map;
   unsigned int i;
-  static htab_t ssa_name_hash;
+  static hash_table <tree_node, hash_ssa_name_by_var, eq_ssa_name_by_var,
+		     typed_null_remove<tree_node> >
+		    ssa_name_hash;
 
   cl = create_coalesce_list ();
   map = create_outofssa_var_map (cl, used_in_copies);
@@ -1364,8 +1363,7 @@ coalesce_ssa_name (void)
      so debug info remains undisturbed.  */
   if (!optimize)
     {
-      ssa_name_hash = htab_create (10, hash_ssa_name_by_var,
-      				   eq_ssa_name_by_var, NULL);
+      ssa_name_hash.create (10);
       for (i = 1; i < num_ssa_names; i++)
 	{
 	  tree a = ssa_name (i);
@@ -1375,7 +1373,7 @@ coalesce_ssa_name (void)
 	      && !DECL_IGNORED_P (SSA_NAME_VAR (a))
 	      && (!has_zero_uses (a) || !SSA_NAME_IS_DEFAULT_DEF (a)))
 	    {
-	      tree *slot = (tree *) htab_find_slot (ssa_name_hash, a, INSERT);
+	      tree *slot = ssa_name_hash.find_slot (a, INSERT);
 
 	      if (!*slot)
 		*slot = a;
@@ -1388,7 +1386,7 @@ coalesce_ssa_name (void)
 		}
 	    }
 	}
-      htab_delete (ssa_name_hash);
+      ssa_name_hash.dispose ();
     }
   if (dump_file && (dump_flags & TDF_DETAILS))
     dump_var_map (dump_file, map);
Index: gcc/coverage.c
===================================================================
--- gcc/coverage.c	(revision 188124)
+++ gcc/coverage.c	(working copy)
@@ -43,7 +43,7 @@ along with GCC; see the file COPYING3.  
 #include "ggc.h"
 #include "coverage.h"
 #include "langhooks.h"
-#include "hashtab.h"
+#include "hash-table.h"
 #include "tree-iterator.h"
 #include "cgraph.h"
 #include "tree-pass.h"
@@ -104,17 +104,11 @@ static char *bbg_file_name;
 /* Name of the count data file.  */
 static char *da_file_name;
 
-/* Hash table of count data.  */
-static htab_t counts_hash = NULL;
-
 /* The names of merge functions for counters.  */
 static const char *const ctr_merge_functions[GCOV_COUNTERS] =
GCOV_MERGE_FUNCTIONS;
 static const char *const ctr_names[GCOV_COUNTERS] = GCOV_COUNTER_NAMES;
 
 /* Forward declarations.  */
-static hashval_t htab_counts_entry_hash (const void *);
-static int htab_counts_entry_eq (const void *, const void *);
-static void htab_counts_entry_del (void *);
 static void read_counts_file (void);
 static tree build_var (tree, tree, int);
 static void build_fn_info_type (tree, unsigned, tree);
@@ -144,32 +138,31 @@ get_gcov_unsigned_t (void)
   return lang_hooks.types.type_for_mode (mode, true);
 }
 
-static hashval_t
-htab_counts_entry_hash (const void *of)
+inline hashval_t
+coverage_counts_entry_hash (const counts_entry_t *entry)
 {
-  const counts_entry_t *const entry = (const counts_entry_t *) of;
-
   return entry->ident * GCOV_COUNTERS + entry->ctr;
 }
 
-static int
-htab_counts_entry_eq (const void *of1, const void *of2)
+inline int
+coverage_counts_entry_eq (const counts_entry_t *entry1,
+                          const counts_entry_t *entry2)
 {
-  const counts_entry_t *const entry1 = (const counts_entry_t *) of1;
-  const counts_entry_t *const entry2 = (const counts_entry_t *) of2;
-
   return entry1->ident == entry2->ident && entry1->ctr == entry2->ctr;
 }
 
-static void
-htab_counts_entry_del (void *of)
+inline void
+coverage_counts_entry_del (counts_entry_t *entry)
 {
-  counts_entry_t *const entry = (counts_entry_t *) of;
-
   free (entry->counts);
   free (entry);
 }
 
+/* Hash table of count data.  */
+static hash_table <counts_entry_t, coverage_counts_entry_hash,
+		   coverage_counts_entry_eq, coverage_counts_entry_del>
+		  counts_hash;
+
 /* Read in the counts file, if available.  */
 
 static void
@@ -208,9 +201,7 @@ read_counts_file (void)
   /* Read and discard the stamp.  */
   gcov_read_unsigned ();
 
-  counts_hash = htab_create (10,
-			     htab_counts_entry_hash, htab_counts_entry_eq,
-			     htab_counts_entry_del);
+  counts_hash.create (10);
   while ((tag = gcov_read_unsigned ()))
     {
       gcov_unsigned_t length;
@@ -258,8 +249,7 @@ read_counts_file (void)
 	  elt.ident = fn_ident;
 	  elt.ctr = GCOV_COUNTER_FOR_TAG (tag);
 
-	  slot = (counts_entry_t **) htab_find_slot
-	    (counts_hash, &elt, INSERT);
+	  slot = counts_hash.find_slot (&elt, INSERT);
 	  entry = *slot;
 	  if (!entry)
 	    {
@@ -279,14 +269,14 @@ read_counts_file (void)
 	      error ("checksum is (%x,%x) instead of (%x,%x)",
 		     entry->lineno_checksum, entry->cfg_checksum,
 		     lineno_checksum, cfg_checksum);
-	      htab_delete (counts_hash);
+	      counts_hash.dispose ();
 	      break;
 	    }
 	  else if (entry->summary.num != n_counts)
 	    {
 	      error ("Profile data for function %u is corrupted", fn_ident);
 	      error ("number of counters is %d instead of %d", entry->summary.num,
n_counts);
-	      htab_delete (counts_hash);
+	      counts_hash.dispose ();
 	      break;
 	    }
 	  else if (elt.ctr >= GCOV_COUNTERS_SUMMABLE)
@@ -312,7 +302,7 @@ read_counts_file (void)
 	{
 	  error (is_error < 0 ? "%qs has overflowed" : "%qs is corrupted",
 		 da_file_name);
-	  htab_delete (counts_hash);
+	  counts_hash.dispose ();
 	  break;
 	}
     }
@@ -330,7 +320,7 @@ get_coverage_counts (unsigned counter, u
   counts_entry_t *entry, elt;
 
   /* No hash table, no counts.  */
-  if (!counts_hash)
+  if (!counts_hash.is_created ())
     {
       static int warned = 0;
 
@@ -344,7 +334,7 @@ get_coverage_counts (unsigned counter, u
 
   elt.ident = current_function_funcdef_no + 1;
   elt.ctr = counter;
-  entry = (counts_entry_t *) htab_find (counts_hash, &elt);
+  entry = counts_hash.find (&elt);
   if (!entry || !entry->summary.num)
     /* The function was not emitted, or is weak and not chosen in the
        final executable.  Silently fail, because there's nothing we
Index: gcc/stringpool.c
===================================================================
--- gcc/stringpool.c	(revision 188124)
+++ gcc/stringpool.c	(working copy)
@@ -49,7 +49,7 @@ static const char digit_vector[] = {
 
 struct ht *ident_hash;
 
-static hashnode alloc_node (hash_table *);
+static hashnode alloc_node (cpp_hash_table *);
 static int mark_ident (struct cpp_reader *, hashnode, const void *);
 
 static void *
@@ -70,7 +70,7 @@ init_stringpool (void)
 
 /* Allocate a hash node.  */
 static hashnode
-alloc_node (hash_table *table ATTRIBUTE_UNUSED)
+alloc_node (cpp_hash_table *table ATTRIBUTE_UNUSED)
 {
   return GCC_IDENT_TO_HT_IDENT (make_node (IDENTIFIER_NODE));
 }
Index: gcc/tree-ssa-pre.c
===================================================================
--- gcc/tree-ssa-pre.c	(revision 188124)
+++ gcc/tree-ssa-pre.c	(working copy)
@@ -34,7 +34,7 @@ along with GCC; see the file COPYING3.  
 #include "tree-dump.h"
 #include "timevar.h"
 #include "fibheap.h"
-#include "hashtab.h"
+#include "hash-table.h"
 #include "tree-iterator.h"
 #include "alloc-pool.h"
 #include "obstack.h"
@@ -181,12 +181,11 @@ typedef struct pre_expr_d
 #define PRE_EXPR_REFERENCE(e) (e)->u.reference
 #define PRE_EXPR_CONSTANT(e) (e)->u.constant
 
-static int
-pre_expr_eq (const void *p1, const void *p2)
-{
-  const struct pre_expr_d *e1 = (const struct pre_expr_d *) p1;
-  const struct pre_expr_d *e2 = (const struct pre_expr_d *) p2;
+/* Compare E1 and E1 for equality.  */
 
+inline int
+ssa_pre_expr_eq (const struct pre_expr_d *e1, const struct pre_expr_d *e2)
+{
   if (e1->kind != e2->kind)
     return false;
 
@@ -207,10 +206,11 @@ pre_expr_eq (const void *p1, const void 
     }
 }
 
-static hashval_t
-pre_expr_hash (const void *p1)
+/* Hash E.  */
+
+inline hashval_t
+ssa_pre_expr_hash (const struct pre_expr_d *e)
 {
-  const struct pre_expr_d *e = (const struct pre_expr_d *) p1;
   switch (e->kind)
     {
     case CONSTANT:
@@ -226,7 +226,6 @@ pre_expr_hash (const void *p1)
     }
 }
 
-
 /* Next global expression id number.  */
 static unsigned int next_expression_id;
 
@@ -234,7 +233,9 @@ static unsigned int next_expression_id;
 DEF_VEC_P (pre_expr);
 DEF_VEC_ALLOC_P (pre_expr, heap);
 static VEC(pre_expr, heap) *expressions;
-static htab_t expression_to_id;
+static hash_table <pre_expr_d, ssa_pre_expr_hash, ssa_pre_expr_eq,
+		   typed_null_remove <pre_expr_d> >
+		  expression_to_id;
 static VEC(unsigned, heap) *name_to_id;
 
 /* Allocate an expression id for EXPR.  */
@@ -242,7 +243,7 @@ static VEC(unsigned, heap) *name_to_id;
 static inline unsigned int
 alloc_expression_id (pre_expr expr)
 {
-  void **slot;
+  struct pre_expr_d **slot;
   /* Make sure we won't overflow. */
   gcc_assert (next_expression_id + 1 > next_expression_id);
   expr->id = next_expression_id++;
@@ -260,7 +261,7 @@ alloc_expression_id (pre_expr expr)
     }
   else
     {
-      slot = htab_find_slot (expression_to_id, expr, INSERT);
+      slot = expression_to_id.find_slot (expr, INSERT);
       gcc_assert (!*slot);
       *slot = expr;
     }
@@ -278,7 +279,7 @@ get_expression_id (const pre_expr expr)
 static inline unsigned int
 lookup_expression_id (const pre_expr expr)
 {
-  void **slot;
+  struct pre_expr_d **slot;
 
   if (expr->kind == NAME)
     {
@@ -289,7 +290,7 @@ lookup_expression_id (const pre_expr exp
     }
   else
     {
-      slot = htab_find_slot (expression_to_id, expr, NO_INSERT);
+      slot = expression_to_id.find_slot (expr, NO_INSERT);
       if (!slot)
 	return 0;
       return ((pre_expr)*slot)->id;
@@ -490,11 +491,6 @@ static bitmap need_eh_cleanup;
 /* Set of blocks with statements that have had their AB properties changed. 
*/
 static bitmap need_ab_cleanup;
 
-/* The phi_translate_table caches phi translations for a given
-   expression and predecessor.  */
-
-static htab_t phi_translate_table;
-
 /* A three tuple {e, pred, v} used to cache phi translations in the
    phi_translate_table.  */
 
@@ -517,21 +513,19 @@ typedef const struct expr_pred_trans_d *
 
 /* Return the hash value for a phi translation table entry.  */
 
-static hashval_t
-expr_pred_trans_hash (const void *p)
+inline hashval_t
+ssa_expr_pred_trans_hash (const expr_pred_trans_d *ve)
 {
-  const_expr_pred_trans_t const ve = (const_expr_pred_trans_t) p;
   return ve->hashcode;
 }
 
 /* Return true if two phi translation table entries are the same.
    P1 and P2 should point to the expr_pred_trans_t's to be compared.*/
 
-static int
-expr_pred_trans_eq (const void *p1, const void *p2)
+inline int
+ssa_expr_pred_trans_eq (const expr_pred_trans_d *ve1,
+			const expr_pred_trans_d *ve2)
 {
-  const_expr_pred_trans_t const ve1 = (const_expr_pred_trans_t) p1;
-  const_expr_pred_trans_t const ve2 = (const_expr_pred_trans_t) p2;
   basic_block b1 = ve1->pred;
   basic_block b2 = ve2->pred;
 
@@ -539,9 +533,17 @@ expr_pred_trans_eq (const void *p1, cons
      be equal.  */
   if (b1 != b2)
     return false;
-  return pre_expr_eq (ve1->e, ve2->e);
+  return ssa_pre_expr_eq (ve1->e, ve2->e);
 }
 
+/* The phi_translate_table caches phi translations for a given
+   expression and predecessor.  */
+
+static hash_table <expr_pred_trans_d, ssa_expr_pred_trans_hash,
+		   ssa_expr_pred_trans_eq,
+		   typed_free_remove <expr_pred_trans_d> >
+		  phi_translate_table;
+
 /* Search in the phi translation table for the translation of
    expression E in basic block PRED.
    Return the translated value, if found, NULL otherwise.  */
@@ -549,18 +551,18 @@ expr_pred_trans_eq (const void *p1, cons
 static inline pre_expr
 phi_trans_lookup (pre_expr e, basic_block pred)
 {
-  void **slot;
+  expr_pred_trans_t *slot;
   struct expr_pred_trans_d ept;
 
   ept.e = e;
   ept.pred = pred;
-  ept.hashcode = iterative_hash_hashval_t (pre_expr_hash (e), pred->index);
-  slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
+  ept.hashcode = iterative_hash_hashval_t (ssa_pre_expr_hash (e),
pred->index);
+  slot = phi_translate_table.find_slot_with_hash (&ept, ept.hashcode,
 				   NO_INSERT);
   if (!slot)
     return NULL;
   else
-    return ((expr_pred_trans_t) *slot)->v;
+    return (*slot)->v;
 }
 
 
@@ -570,18 +572,18 @@ phi_trans_lookup (pre_expr e, basic_bloc
 static inline void
 phi_trans_add (pre_expr e, pre_expr v, basic_block pred)
 {
-  void **slot;
+  expr_pred_trans_t *slot;
   expr_pred_trans_t new_pair = XNEW (struct expr_pred_trans_d);
   new_pair->e = e;
   new_pair->pred = pred;
   new_pair->v = v;
-  new_pair->hashcode = iterative_hash_hashval_t (pre_expr_hash (e),
+  new_pair->hashcode = iterative_hash_hashval_t (ssa_pre_expr_hash (e),
 						 pred->index);
 
-  slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
+  slot = phi_translate_table.find_slot_with_hash (new_pair,
 				   new_pair->hashcode, INSERT);
   free (*slot);
-  *slot = (void *) new_pair;
+  *slot = new_pair;
 }
 
 
@@ -3543,7 +3545,7 @@ do_regular_insertion (basic_block block,
 		    do_insertion = true;
 		  if (first_s == NULL)
 		    first_s = edoubleprime;
-		  else if (!pre_expr_eq (first_s, edoubleprime))
+		  else if (!ssa_pre_expr_eq (first_s, edoubleprime))
 		    all_same = false;
 		}
 	    }
@@ -4849,11 +4851,8 @@ init_pre (bool do_fre)
   calculate_dominance_info (CDI_DOMINATORS);
 
   bitmap_obstack_initialize (&grand_bitmap_obstack);
-  phi_translate_table = htab_create (5110, expr_pred_trans_hash,
-				     expr_pred_trans_eq, free);
-  expression_to_id = htab_create (num_ssa_names * 3,
-				  pre_expr_hash,
-				  pre_expr_eq, NULL);
+  phi_translate_table.create (5110);
+  expression_to_id.create (num_ssa_names * 3);
   bitmap_set_pool = create_alloc_pool ("Bitmap sets",
 				       sizeof (struct bitmap_set), 30);
   pre_expr_pool = create_alloc_pool ("pre_expr nodes",
@@ -4886,8 +4885,8 @@ fini_pre (bool do_fre)
   bitmap_obstack_release (&grand_bitmap_obstack);
   free_alloc_pool (bitmap_set_pool);
   free_alloc_pool (pre_expr_pool);
-  htab_delete (phi_translate_table);
-  htab_delete (expression_to_id);
+  phi_translate_table.dispose ();
+  expression_to_id.dispose ();
   VEC_free (unsigned, heap, name_to_id);
 
   free_aux_for_blocks ();
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 188124)
+++ gcc/Makefile.in	(working copy)
@@ -840,6 +840,7 @@ endif
 
 # Shorthand variables for dependency lists.
 VEC_H = vec.h statistics.h
+HASH_TABLE_H = $(HASHTAB_H) hash-table.h
 EXCEPT_H = except.h $(HASHTAB_H) vecprim.h vecir.h
 TARGET_DEF = target.def target-hooks-macros.h
 C_TARGET_DEF = c-family/c-target.def target-hooks-macros.h
@@ -1470,7 +1471,8 @@ OBJS-libcommon = diagnostic.o pretty-pri
 # Objects in libcommon-target.a, used by drivers and by the core
 # compiler and containing target-dependent code.
 OBJS-libcommon-target = $(common_out_object_file) prefix.o params.o \
-	opts.o opts-common.o options.o vec.o hooks.o common/common-targhooks.o
+	opts.o opts-common.o options.o vec.o hooks.o common/common-targhooks.o \
+	hash-table.o
 
 # This lists all host objects for the front ends.
 ALL_HOST_FRONTEND_OBJS = $(C_OBJS) \
@@ -2302,7 +2304,7 @@ stor-layout.o : stor-layout.c $(CONFIG_H
 tree-ssa-tail-merge.o: tree-ssa-tail-merge.c \
    $(SYSTEM_H) $(CONFIG_H) coretypes.h $(TM_H) $(BITMAP_H) \
    $(FLAGS_H) $(TM_P_H) $(BASIC_BLOCK_H) output.h \
-   $(TREE_H) $(TREE_FLOW_H) $(TREE_INLINE_H) \
+   $(TREE_H) $(TREE_FLOW_H) $(TREE_INLINE_H) $(HASH_TABLE_H) \
    $(GIMPLE_H) $(FUNCTION_H) \
    $(TIMEVAR_H) tree-ssa-sccvn.h \
    $(CGRAPH_H) gimple-pretty-print.h tree-pretty-print.h $(PARAMS_H)
@@ -2339,7 +2341,7 @@ tree-ssa-ter.o : tree-ssa-ter.c $(TREE_F
    gimple-pretty-print.h
 tree-ssa-coalesce.o : tree-ssa-coalesce.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(TREE_H) $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
-   $(TREE_SSA_LIVE_H) $(BITMAP_H) $(FLAGS_H) $(HASHTAB_H) \
+   $(TREE_SSA_LIVE_H) $(BITMAP_H) $(FLAGS_H) $(HASH_TABLE_H) \
    tree-pretty-print.h
 tree-outof-ssa.o : tree-outof-ssa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
    $(TREE_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
@@ -2401,7 +2403,7 @@ tree-ssa-threadedge.o : tree-ssa-threade
    $(TREE_PASS_H) tree-ssa-propagate.h langhooks.h \
    $(PARAMS_H)
 tree-ssa-threadupdate.o : tree-ssa-threadupdate.c $(TREE_FLOW_H) $(CONFIG_H) \
-   $(SYSTEM_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h \
+   $(SYSTEM_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h $(HASH_TABLE_H) \
    $(DIAGNOSTIC_H) $(FUNCTION_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
    $(BASIC_BLOCK_H) $(FLAGS_H) $(TREE_PASS_H) $(CFGLOOP_H)
 tree-ssanames.o : tree-ssanames.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
@@ -2423,7 +2425,7 @@ tree-ssa-copyrename.o : tree-ssa-copyren
 tree-ssa-pre.o : tree-ssa-pre.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(TREE_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) $(FIBHEAP_H) \
    $(TM_H) coretypes.h $(TREE_DUMP_H) $(TREE_PASS_H) $(FLAGS_H) langhooks.h \
-   $(CFGLOOP_H) alloc-pool.h $(BASIC_BLOCK_H) $(BITMAP_H) $(HASHTAB_H) \
+   $(CFGLOOP_H) alloc-pool.h $(BASIC_BLOCK_H) $(BITMAP_H) $(HASH_TABLE_H) \
    $(GIMPLE_H) $(TREE_INLINE_H) tree-iterator.h tree-ssa-sccvn.h $(PARAMS_H) \
    $(DBGCNT_H) tree-scalar-evolution.h tree-pretty-print.h \
    gimple-pretty-print.h
@@ -3020,8 +3022,9 @@ ipa-pure-const.o : ipa-pure-const.c $(CO
    gimple-pretty-print.h $(DATA_STREAMER_H) $(TREE_STREAMER_H)
 coverage.o : coverage.c $(GCOV_IO_H) $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    $(TM_H) $(RTL_H) $(TREE_H) $(FLAGS_H) output.h $(REGS_H) $(EXPR_H) \
-   $(FUNCTION_H) $(BASIC_BLOCK_H) toplev.h $(DIAGNOSTIC_CORE_H) $(GGC_H)
langhooks.h $(COVERAGE_H) \
-   $(HASHTAB_H) tree-iterator.h $(CGRAPH_H) $(TREE_PASS_H) gcov-io.c $(TM_P_H)
\
+   $(FUNCTION_H) $(BASIC_BLOCK_H) toplev.h $(DIAGNOSTIC_CORE_H) $(GGC_H) \
+   $(HASH_TABLE_H) langhooks.h $(COVERAGE_H) \
+   tree-iterator.h $(CGRAPH_H) $(TREE_PASS_H) gcov-io.c $(TM_P_H) \
    $(DIAGNOSTIC_CORE_H) intl.h gt-coverage.h $(TARGET_H)
 cselib.o : cselib.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h $(RECOG_H) \
@@ -3094,7 +3097,8 @@ tree-ssa-ccp.o : tree-ssa-ccp.c $(TREE_F
    $(SYSTEM_H) $(TREE_H) $(TM_P_H) $(EXPR_H) output.h \
    $(DIAGNOSTIC_H) $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) coretypes.h \
    $(TREE_DUMP_H) $(BASIC_BLOCK_H) $(TREE_PASS_H) langhooks.h  $(PARAMS_H) \
-   tree-ssa-propagate.h value-prof.h $(FLAGS_H) $(TARGET_H)
$(DIAGNOSTIC_CORE_H) \
+   tree-ssa-propagate.h value-prof.h $(FLAGS_H) $(TARGET_H) \
+   $(DIAGNOSTIC_CORE_H) $(HASH_TABLE_H) \
    $(DBGCNT_H) tree-pretty-print.h gimple-pretty-print.h gimple-fold.h
 tree-ssa-strlen.o : tree-ssa-strlen.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    $(TREE_FLOW_H) $(TREE_PASS_H) domwalk.h alloc-pool.h tree-ssa-propagate.h \
@@ -3248,6 +3252,8 @@ bitmap.o : bitmap.c $(CONFIG_H) $(SYSTEM
    $(GGC_H) gt-bitmap.h $(BITMAP_H) $(OBSTACK_H) $(HASHTAB_H)
 vec.o : vec.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(VEC_H) $(GGC_H) \
    toplev.h $(DIAGNOSTIC_CORE_H) $(HASHTAB_H)
+hash-table.o : hash-table.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
+   $(HASHTAB_H)
 reload.o : reload.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_ERROR_H)
\
    $(FLAGS_H) output.h $(EXPR_H) $(OPTABS_H) reload.h $(RECOG_H) \
    hard-reg-set.h insn-config.h $(REGS_H) $(FUNCTION_H) real.h \
Index: libcpp/symtab.c
===================================================================
--- libcpp/symtab.c	(revision 188124)
+++ libcpp/symtab.c	(working copy)
@@ -31,7 +31,7 @@ along with this program; see the file CO
    existing entry with a potential new one.  */
 
 static unsigned int calc_hash (const unsigned char *, size_t);
-static void ht_expand (hash_table *);
+static void ht_expand (cpp_hash_table *);
 static double approx_sqrt (double);
 
 /* A deleted entry.  */
@@ -53,13 +53,13 @@ calc_hash (const unsigned char *str, siz
 
 /* Initialize an identifier hashtable.  */
 
-hash_table *
+cpp_hash_table *
 ht_create (unsigned int order)
 {
   unsigned int nslots = 1 << order;
-  hash_table *table;
+  cpp_hash_table *table;
 
-  table = XCNEW (hash_table);
+  table = XCNEW (cpp_hash_table);
 
   /* Strings need no alignment.  */
   _obstack_begin (&table->stack, 0, 0,
@@ -77,7 +77,7 @@ ht_create (unsigned int order)
 /* Frees all memory associated with a hash table.  */
 
 void
-ht_destroy (hash_table *table)
+ht_destroy (cpp_hash_table *table)
 {
   obstack_free (&table->stack, NULL);
   if (table->entries_owned)
@@ -91,7 +91,7 @@ ht_destroy (hash_table *table)
    returns NULL.  Otherwise insert and returns a new entry.  A new
    string is allocated.  */
 hashnode
-ht_lookup (hash_table *table, const unsigned char *str, size_t len,
+ht_lookup (cpp_hash_table *table, const unsigned char *str, size_t len,
 	   enum ht_lookup_option insert)
 {
   return ht_lookup_with_hash (table, str, len, calc_hash (str, len),
@@ -99,7 +99,7 @@ ht_lookup (hash_table *table, const unsi
 }
 
 hashnode
-ht_lookup_with_hash (hash_table *table, const unsigned char *str,
+ht_lookup_with_hash (cpp_hash_table *table, const unsigned char *str,
 		     size_t len, unsigned int hash,
 		     enum ht_lookup_option insert)
 {
@@ -182,7 +182,7 @@ ht_lookup_with_hash (hash_table *table, 
 /* Double the size of a hash table, re-hashing existing entries.  */
 
 static void
-ht_expand (hash_table *table)
+ht_expand (cpp_hash_table *table)
 {
   hashnode *nentries, *p, *limit;
   unsigned int size, sizemask;
@@ -224,7 +224,7 @@ ht_expand (hash_table *table)
 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
    the node, and V.  */
 void
-ht_forall (hash_table *table, ht_cb cb, const void *v)
+ht_forall (cpp_hash_table *table, ht_cb cb, const void *v)
 {
   hashnode *p, *limit;
 
@@ -242,7 +242,7 @@ ht_forall (hash_table *table, ht_cb cb, 
 /* Like ht_forall, but a nonzero return from the callback means that
    the entry should be removed from the table.  */
 void
-ht_purge (hash_table *table, ht_cb cb, const void *v)
+ht_purge (cpp_hash_table *table, ht_cb cb, const void *v)
 {
   hashnode *p, *limit;
 
@@ -259,7 +259,7 @@ ht_purge (hash_table *table, ht_cb cb, c
 
 /* Restore the hash table.  */
 void
-ht_load (hash_table *ht, hashnode *entries,
+ht_load (cpp_hash_table *ht, hashnode *entries,
 	 unsigned int nslots, unsigned int nelements,
 	 bool own)
 {
@@ -274,7 +274,7 @@ ht_load (hash_table *ht, hashnode *entri
 /* Dump allocation statistics to stderr.  */
 
 void
-ht_dump_statistics (hash_table *table)
+ht_dump_statistics (cpp_hash_table *table)
 {
   size_t nelts, nids, overhead, headers;
   size_t total_bytes, longest, deleted = 0;
Index: libcpp/include/symtab.h
===================================================================
--- libcpp/include/symtab.h	(revision 188124)
+++ libcpp/include/symtab.h	(working copy)
@@ -38,7 +38,7 @@ struct GTY(()) ht_identifier {
 #define HT_LEN(NODE) ((NODE)->len)
 #define HT_STR(NODE) ((NODE)->str)
 
-typedef struct ht hash_table;
+typedef struct ht cpp_hash_table;
 typedef struct ht_identifier *hashnode;
 
 enum ht_lookup_option {HT_NO_INSERT = 0, HT_ALLOC};
@@ -51,7 +51,7 @@ struct ht
 
   hashnode *entries;
   /* Call back, allocate a node.  */
-  hashnode (*alloc_node) (hash_table *);
+  hashnode (*alloc_node) (cpp_hash_table *);
   /* Call back, allocate something that hangs off a node like a cpp_macro.  
      NULL means use the usual allocator.  */
   void * (*alloc_subobject) (size_t);
@@ -71,14 +71,14 @@ struct ht
 };
 
 /* Initialize the hashtable with 2 ^ order entries.  */
-extern hash_table *ht_create (unsigned int order);
+extern cpp_hash_table *ht_create (unsigned int order);
 
 /* Frees all memory associated with a hash table.  */
-extern void ht_destroy (hash_table *);
+extern void ht_destroy (cpp_hash_table *);
 
-extern hashnode ht_lookup (hash_table *, const unsigned char *,
+extern hashnode ht_lookup (cpp_hash_table *, const unsigned char *,
 			   size_t, enum ht_lookup_option);
-extern hashnode ht_lookup_with_hash (hash_table *, const unsigned char *,
+extern hashnode ht_lookup_with_hash (cpp_hash_table *, const unsigned char *,
                                      size_t, unsigned int,
                                      enum ht_lookup_option);
 #define HT_HASHSTEP(r, c) ((r) * 67 + ((c) - 113));
@@ -88,17 +88,17 @@ extern hashnode ht_lookup_with_hash (has
    TABLE->PFILE, the node, and a PTR, and the callback sequence stops
    if the callback returns zero.  */
 typedef int (*ht_cb) (struct cpp_reader *, hashnode, const void *);
-extern void ht_forall (hash_table *, ht_cb, const void *);
+extern void ht_forall (cpp_hash_table *, ht_cb, const void *);
 
 /* For all nodes in TABLE, call the callback.  If the callback returns
    a nonzero value, the node is removed from the table.  */
-extern void ht_purge (hash_table *, ht_cb, const void *);
+extern void ht_purge (cpp_hash_table *, ht_cb, const void *);
 
 /* Restore the hash table.  */
-extern void ht_load (hash_table *ht, hashnode *entries,
+extern void ht_load (cpp_hash_table *ht, hashnode *entries,
 		     unsigned int nslots, unsigned int nelements, bool own);
 
 /* Dump allocation statistics to stderr.  */
-extern void ht_dump_statistics (hash_table *);
+extern void ht_dump_statistics (cpp_hash_table *);
 
 #endif /* LIBCPP_SYMTAB_H */
Index: libcpp/init.c
===================================================================
--- libcpp/init.c	(revision 188124)
+++ libcpp/init.c	(working copy)
@@ -149,7 +149,7 @@ init_library (void)
 
 /* Initialize a cpp_reader structure.  */
 cpp_reader *
-cpp_create_reader (enum c_lang lang, hash_table *table,
+cpp_create_reader (enum c_lang lang, cpp_hash_table *table,
 		   struct line_maps *line_table)
 {
   cpp_reader *pfile;
Index: libcpp/identifiers.c
===================================================================
--- libcpp/identifiers.c	(revision 188124)
+++ libcpp/identifiers.c	(working copy)
@@ -28,12 +28,12 @@ along with this program; see the file CO
 #include "cpplib.h"
 #include "internal.h"
 
-static hashnode alloc_node (hash_table *);
+static hashnode alloc_node (cpp_hash_table *);
 
 /* Return an identifier node for hashtable.c.  Used by cpplib except
    when integrated with the C front ends.  */
 static hashnode
-alloc_node (hash_table *table)
+alloc_node (cpp_hash_table *table)
 {
   cpp_hashnode *node;
 
@@ -45,7 +45,7 @@ alloc_node (hash_table *table)
 /* Set up the identifier hash table.  Use TABLE if non-null, otherwise
    create our own.  */
 void
-_cpp_init_hashtable (cpp_reader *pfile, hash_table *table)
+_cpp_init_hashtable (cpp_reader *pfile, cpp_hash_table *table)
 {
   struct spec_nodes *s;
 
Index: libcpp/internal.h
===================================================================
--- libcpp/internal.h	(revision 188124)
+++ libcpp/internal.h	(working copy)
@@ -615,7 +615,7 @@ extern void _cpp_push_token_context (cpp
 extern void _cpp_backup_tokens_direct (cpp_reader *, unsigned int);
 
 /* In identifiers.c */
-extern void _cpp_init_hashtable (cpp_reader *, hash_table *);
+extern void _cpp_init_hashtable (cpp_reader *, cpp_hash_table *);
 extern void _cpp_destroy_hashtable (cpp_reader *);
 
 /* In files.c */

--
This patch is available for review at http://codereview.appspot.com/6244048

[tromey_redhat.com, 2012-06-04 19:30:09]

>>>>> "Lawrence" == Lawrence Crowl <crowl@google.com> writes:

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

The libcpp changes are ok.

Tom