Grab hashtab.c from the development version of gcc, add it to libiberty.

Make sure that g++ and g77 link against libiberty (fixed in dev. sources
as well).

Use hashtab functions instead of splay-trees in cse.c.

This is worth a 10% compiling speed increase on some arches, including
sparc, hppa...

7 files changed, 192 insertions, 44 deletions

diff --git a/gnu/egcs/gcc/Makefile.in b/gnu/egcs/gcc/Makefile.in
index cab7cd7143c..aba4ebfde4a 100644
--- a/gnu/egcs/gcc/Makefile.in
+++ b/gnu/egcs/gcc/Makefile.in
@@ -684,7 +684,7 @@ OBJS = toplev.o version.o tree.o print-tree.o stor-layout.o fold-const.o \
  insn-peep.o reorg.o $(SCHED_PREFIX)sched.o final.o recog.o reg-stack.o \
  insn-opinit.o insn-recog.o insn-extract.o insn-output.o insn-emit.o lcm.o \
  profile.o insn-attrtab.o $(out_object_file) getpwd.o $(EXTRA_OBJS) convert.o \
- mbchar.o dyn-string.o splay-tree.o graph.o sbitmap.o resource.o hash.o
+ mbchar.o dyn-string.o graph.o sbitmap.o resource.o hash.o 
 
 # GEN files are listed separately, so they can be built before doing parallel
 #  makes for cc1 or cc1plus.  Otherwise sequent parallel make attempts to load
@@ -1529,7 +1529,7 @@ stupid.o : stupid.c $(CONFIG_H) system.h $(RTL_H) $(REGS_H) hard-reg-set.h \
 
 cse.o : cse.c $(CONFIG_H) system.h $(RTL_H) $(REGS_H) hard-reg-set.h flags.h \
    real.h insn-config.h $(RECOG_H) $(EXPR_H) toplev.h output.h \
-   $(srcdir)/../include/splay-tree.h
+   $(srcdir)/../include/hashtab.h
 gcse.o : gcse.c $(CONFIG_H) system.h $(RTL_H) $(REGS_H) hard-reg-set.h \
    flags.h real.h insn-config.h $(RECOG_H) $(EXPR_H) $(BASIC_BLOCK_H) \
    output.h toplev.h
diff --git a/gnu/egcs/gcc/cp/Makefile.in b/gnu/egcs/gcc/cp/Makefile.in
index 9fa7860a5e5..b0cccf2a9f3 100644
--- a/gnu/egcs/gcc/cp/Makefile.in
+++ b/gnu/egcs/gcc/cp/Makefile.in
@@ -161,7 +161,7 @@ SUBDIR_MALLOC = `if [ x$(MALLOC) != x ]; then echo ../$(MALLOC); else true; fi`
 # How to link with both our special library facilities
 # and the system's installed libraries.
 LIBS = $(SUBDIR_OBSTACK) $(SUBDIR_USE_ALLOCA) $(SUBDIR_MALLOC) \
-  $(INTLLIBS) $(CLIB)
+  $(INTLLIBS) $(CLIB) $(LIBIBERTY)
 
 # Specify the directories to be searched for header files.
 # Both . and srcdir are used, in that order,
diff --git a/gnu/egcs/gcc/cse.c b/gnu/egcs/gcc/cse.c
index 5fc6c7889a2..35dfaa79028 100644
--- a/gnu/egcs/gcc/cse.c
+++ b/gnu/egcs/gcc/cse.c
@@ -34,7 +34,7 @@ Boston, MA 02111-1307, USA.  */
 #include "expr.h"
 #include "toplev.h"
 #include "output.h"
-#include "splay-tree.h"
+#include "hashtab.h"
 
 /* The basic idea of common subexpression elimination is to go
    through the code, keeping a record of expressions that would
@@ -287,14 +287,12 @@ static int *reg_next_eqv;
 static int *reg_prev_eqv;
 
 struct cse_reg_info {
-  union {
-    /* The number of times the register has been altered in the current
-       basic block.  */
-    int reg_tick;
-    
-    /* The next cse_reg_info structure in the free list.  */
-    struct cse_reg_info* next;
-  } variant;
+  /* The number of times the register has been altered in the current
+     basic block.  */
+  int reg_tick;
+
+  /* The next cse_reg_info structure in the free or used list.  */
+  struct cse_reg_info* next;
 
   /* The REG_TICK value at which rtx's containing this register are
      valid in the hash table.  If this does not equal the current
@@ -304,13 +302,20 @@ struct cse_reg_info {
 
   /* The quantity number of the register's current contents.  */
   int reg_qty;
+
+  /* Search key */
+  int regno;
 };
 
 /* A free list of cse_reg_info entries.  */
 static struct cse_reg_info *cse_reg_info_free_list;
 
+/* A used list of cse_reg_info entries.  */
+static struct cse_reg_info *cse_reg_info_used_list;
+static struct cse_reg_info *cse_reg_info_used_list_end;
+
 /* A mapping from registers to cse_reg_info data structures.  */
-static splay_tree cse_reg_info_tree;
+static hash_table_t cse_reg_info_tree;
 
 /* The last lookup we did into the cse_reg_info_tree.  This allows us
    to cache repeated lookups.  */
@@ -506,7 +511,7 @@ struct table_elt
 /* Get the number of times this register has been updated in this
    basic block.  */
 
-#define REG_TICK(N) ((GET_CSE_REG_INFO (N))->variant.reg_tick)
+#define REG_TICK(N) ((GET_CSE_REG_INFO (N))->reg_tick)
 
 /* Get the point at which REG was recorded in the table.  */
 
@@ -690,7 +695,10 @@ static void count_reg_usage	PROTO((rtx, int *, rtx, int));
 extern void dump_class          PROTO((struct table_elt*));
 static void check_fold_consts	PROTO((PTR));
 static struct cse_reg_info* get_cse_reg_info PROTO((int));
-static void free_cse_reg_info   PROTO((splay_tree_value));
+static unsigned int hash_cse_reg_info PROTO((hash_table_entry_t));
+static int cse_reg_info_equal_p	PROTO((hash_table_entry_t,
+				       hash_table_entry_t));
+
 static void flush_hash_table	PROTO((void));
 
 extern int rtx_equal_function_value_matters;
@@ -840,32 +848,38 @@ get_cse_reg_info (regno)
      int regno;
 {
   struct cse_reg_info *cri;
-  splay_tree_node n;
+  struct cse_reg_info **entry;
+  struct cse_reg_info temp;
 
   /* See if we already have this entry.  */
-  n = splay_tree_lookup (cse_reg_info_tree, 
-			(splay_tree_key) regno);
-  if (n)
-    cri = (struct cse_reg_info *) (n->value);
+  temp.regno = regno;
+  entry = (struct cse_reg_info **) find_hash_table_entry (cse_reg_info_tree,
+							  &temp, TRUE);
+
+  if (*entry)
+    cri = *entry;
   else 
     {
       /* Get a new cse_reg_info structure.  */
       if (cse_reg_info_free_list) 
 	{
 	  cri = cse_reg_info_free_list;
-	  cse_reg_info_free_list = cri->variant.next;
+	  cse_reg_info_free_list = cri->next;
 	}
       else
 	cri = (struct cse_reg_info *) xmalloc (sizeof (struct cse_reg_info));
 
       /* Initialize it.  */
-      cri->variant.reg_tick = 0;
+      cri->reg_tick = 0;
       cri->reg_in_table = -1;
       cri->reg_qty = regno;
-
-      splay_tree_insert (cse_reg_info_tree, 
-			 (splay_tree_key) regno, 
-			 (splay_tree_value) cri);
+      cri->regno = regno;
+      cri->next = cse_reg_info_used_list;
+      cse_reg_info_used_list = cri;
+      if (!cse_reg_info_used_list_end)
+	cse_reg_info_used_list_end = cri;
+      
+      *entry = cri;
     }
 
   /* Cache this lookup; we tend to be looking up information about the
@@ -876,14 +890,20 @@ get_cse_reg_info (regno)
   return cri;
 }
 
-static void
-free_cse_reg_info (v)
-     splay_tree_value v;
+static unsigned int
+hash_cse_reg_info (el_ptr)
+     hash_table_entry_t el_ptr;
 {
-  struct cse_reg_info *cri = (struct cse_reg_info *) v;
-  
-  cri->variant.next = cse_reg_info_free_list;
-  cse_reg_info_free_list = cri;
+  return ((struct cse_reg_info *) el_ptr)->regno;
+}
+
+static int
+cse_reg_info_equal_p (el_ptr1, el_ptr2)
+     hash_table_entry_t el_ptr1;
+     hash_table_entry_t el_ptr2;
+{
+  return (((struct cse_reg_info *) el_ptr1)->regno
+	  == ((struct cse_reg_info *) el_ptr2)->regno);
 }
 
 /* Clear the hash table and initialize each register with its own quantity,
@@ -898,12 +918,20 @@ new_basic_block ()
 
   if (cse_reg_info_tree) 
     {
-      splay_tree_delete (cse_reg_info_tree);
+      empty_hash_table (cse_reg_info_tree);
+      if (cse_reg_info_used_list)
+	{
+	  cse_reg_info_used_list_end->next = cse_reg_info_free_list;
+	  cse_reg_info_free_list = cse_reg_info_used_list;
+	  cse_reg_info_used_list = cse_reg_info_used_list_end = 0;
+	}
       cached_cse_reg_info = 0;
     }
-
-  cse_reg_info_tree = splay_tree_new (splay_tree_compare_ints, 0, 
-				      free_cse_reg_info);
+  else
+    {
+      cse_reg_info_tree = create_hash_table (0, hash_cse_reg_info,
+					     cse_reg_info_equal_p);
+    }
 
   CLEAR_HARD_REG_SET (hard_regs_in_table);
 
@@ -5861,7 +5889,15 @@ fold_rtx (x, insn)
 	     hence not save anything) or be incorrect.  */
 	  if (const_arg1 != 0 && GET_CODE (const_arg1) == CONST_INT
 	      && INTVAL (const_arg1) < 0
-	      && - INTVAL (const_arg1) >= 0
+	      /* This used to test
+
+	         - INTVAL (const_arg1) >= 0
+
+		 But The Sun V5.0 compilers mis-compiled that test.  So
+		 instead we test for the problematic value in a more direct
+		 manner and hope the Sun compilers get it correct.  */
+	      && INTVAL (const_arg1) !=
+	        ((HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))
 	      && GET_CODE (folded_arg1) == REG)
 	    {
 	      rtx new_const = GEN_INT (- INTVAL (const_arg1));
@@ -7483,9 +7519,12 @@ cse_insn (insn, libcall_insn)
 		 && GET_CODE (NEXT_INSN (p)) != BARRIER
 		 && GET_CODE (NEXT_INSN (p)) != CODE_LABEL)
 	    {
+	      /* Note, we must update P with the return value from
+		 delete_insn, otherwise we could get an infinite loop
+		 if NEXT_INSN (p) had INSN_DELETED_P set.  */
 	      if (GET_CODE (NEXT_INSN (p)) != NOTE
 		  || NOTE_LINE_NUMBER (NEXT_INSN (p)) == NOTE_INSN_DELETED)
-		delete_insn (NEXT_INSN (p));
+		p = PREV_INSN (delete_insn (NEXT_INSN (p)));
 	      else
 		p = NEXT_INSN (p);
 	    }
@@ -7607,7 +7646,12 @@ cse_insn (insn, libcall_insn)
 	    enum machine_mode mode
 	      = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
 
-	    if (sets[i].src_elt == 0)
+	    /* Don't put a hard register source into the table if this is
+	       the last insn of a libcall.  */
+	    if (sets[i].src_elt == 0
+		&& (GET_CODE (src) != REG
+		    || REGNO (src) >= FIRST_PSEUDO_REGISTER
+		    || ! find_reg_note (insn, REG_RETVAL, NULL_RTX)))
 	      {
 		register struct table_elt *elt;
 
diff --git a/gnu/egcs/gcc/f/Makefile.in b/gnu/egcs/gcc/f/Makefile.in
index 96975a5d7cd..a8828a5d31e 100644
--- a/gnu/egcs/gcc/f/Makefile.in
+++ b/gnu/egcs/gcc/f/Makefile.in
@@ -148,7 +148,8 @@ SUBDIR_MALLOC = `if [ x$(MALLOC) != x ]; then echo ../$(MALLOC); else true; fi`
 
 # How to link with both our special library facilities
 # and the system's installed libraries.
-LIBS = $(SUBDIR_OBSTACK) $(SUBDIR_USE_ALLOCA) $(SUBDIR_MALLOC) $(CLIB)
+LIBS = $(SUBDIR_OBSTACK) $(SUBDIR_USE_ALLOCA) $(SUBDIR_MALLOC) $(CLIB) \
+$(LIBIBERTY)
 
 # Specify the directories to be searched for header files.
 # Both . and srcdir are used, in that order,
diff --git a/gnu/egcs/include/hashtab.h b/gnu/egcs/include/hashtab.h
new file mode 100644
index 00000000000..67c37a284f7
--- /dev/null
+++ b/gnu/egcs/include/hashtab.h
@@ -0,0 +1,103 @@
+/* An expandable hash tables datatype.  
+   Copyright (C) 1999 Free Software Foundation, Inc.
+   Contributed by Vladimir Makarov (vmakarov@cygnus.com).
+
+This program 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 2 of the License, or
+(at your option) any later version.
+
+This program 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 this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+/* This package implements basic hash table functionality.  It is possible
+   to search for an entry, create an entry and destroy an entry.
+
+   Elements in the table are generic pointers.
+
+   The size of the table is not fixed; if the occupancy of the table
+   grows too high the hash table will be expanded.
+
+   The abstract data implementation is based on generalized Algorithm D
+   from Knuth's book "The art of computer programming".  Hash table is
+   expanded by creation of new hash table and transferring elements from
+   the old table to the new table.  */
+
+#ifndef __HASHTAB_H__
+#define __HASHTAB_H__
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* __cplusplus */
+
+#include <ansidecl.h>
+
+/* The hash table element is represented by the following type. */
+
+typedef const void *hash_table_entry_t;
+
+/* Hash tables are of the following type.  The structure
+   (implementation) of this type is not needed for using the hash
+   tables.  All work with hash table should be executed only through
+   functions mentioned below. */
+
+typedef struct
+{
+  /* Current size (in entries) of the hash table */
+  size_t size;
+  /* Current number of elements including also deleted elements */
+  size_t number_of_elements;
+  /* Current number of deleted elements in the table */
+  size_t number_of_deleted_elements;
+  /* The following member is used for debugging. Its value is number
+     of all calls of `find_hash_table_entry' for the hash table. */
+  int searches;
+  /* The following member is used for debugging.  Its value is number
+     of collisions fixed for time of work with the hash table. */
+  int collisions;
+  /* Pointer to function for evaluation of hash value (any unsigned value).
+     This function has one parameter of type hash_table_entry_t. */
+  unsigned (*hash_function) PARAMS ((hash_table_entry_t));
+  /* Pointer to function for test on equality of hash table elements (two
+     parameter of type hash_table_entry_t. */
+  int (*eq_function) PARAMS ((hash_table_entry_t, hash_table_entry_t));
+  /* Table itself */
+  hash_table_entry_t *entries;
+} *hash_table_t;
+
+
+/* The prototypes of the package functions. */
+
+extern hash_table_t create_hash_table
+  PARAMS ((size_t, unsigned (*) (hash_table_entry_t),
+	   int (*) (hash_table_entry_t, hash_table_entry_t)));
+
+extern void delete_hash_table PARAMS ((hash_table_t));
+
+extern void empty_hash_table PARAMS ((hash_table_t));
+
+extern hash_table_entry_t *find_hash_table_entry
+  PARAMS ((hash_table_t, hash_table_entry_t, int));
+
+extern void remove_element_from_hash_table_entry PARAMS ((hash_table_t,
+							  hash_table_entry_t));
+
+extern size_t hash_table_size PARAMS ((hash_table_t));
+
+extern size_t hash_table_elements_number PARAMS ((hash_table_t));
+
+extern int hash_table_collisions PARAMS ((hash_table_t));
+
+extern int all_hash_table_collisions ();
+
+#ifdef __cplusplus
+}
+#endif /* __cplusplus */
+
+#endif /* __HASHTAB_H */
diff --git a/gnu/egcs/libiberty/Makefile.bsd-wrapper b/gnu/egcs/libiberty/Makefile.bsd-wrapper
index fda9e6eacac..a7450789d9c 100644
--- a/gnu/egcs/libiberty/Makefile.bsd-wrapper
+++ b/gnu/egcs/libiberty/Makefile.bsd-wrapper
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile.bsd-wrapper,v 1.4 1999/09/30 12:10:56 espie Exp $
+#	$OpenBSD: Makefile.bsd-wrapper,v 1.5 1999/11/20 18:24:18 espie Exp $
 
 LIB=		iberty
 CPPFLAGS+=	-I$(.CURDIR) -I$(.CURDIR)/../include -I$(.OBJDIR)
@@ -17,7 +17,7 @@ HOST_FILES!=	cat $(.OBJDIR)/needed-list && echo
 .endif
 
 SRCS=		argv.c choose-temp.c concat.c cplus-dem.c \
-		fdmatch.c getopt.c getopt1.c getruntime.c hex.c \
+		fdmatch.c getopt.c getopt1.c getruntime.c hashtab.c hex.c \
 		floatformat.c obstack.c pexecute.c spaces.c splay-tree.c \
 		strerror.c strsignal.c xatexit.c xexit.c xmalloc.c \
 		xstrerror.c xstrdup.c \
diff --git a/gnu/egcs/libiberty/shlib_version b/gnu/egcs/libiberty/shlib_version
index b52599a164f..c6e3f4d3fc0 100644
--- a/gnu/egcs/libiberty/shlib_version
+++ b/gnu/egcs/libiberty/shlib_version
@@ -1,2 +1,2 @@
 major=2
-minor=0
+minor=1