diff options
| -rw-r--r-- | gnu/egcs/gcc/Makefile.in | 4 | ||||
| -rw-r--r-- | gnu/egcs/gcc/cp/Makefile.in | 2 | ||||
| -rw-r--r-- | gnu/egcs/gcc/cse.c | 118 | ||||
| -rw-r--r-- | gnu/egcs/gcc/f/Makefile.in | 3 | ||||
| -rw-r--r-- | gnu/egcs/include/hashtab.h | 103 | ||||
| -rw-r--r-- | gnu/egcs/libiberty/Makefile.bsd-wrapper | 4 | ||||
| -rw-r--r-- | gnu/egcs/libiberty/shlib_version | 2 |
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 |