This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

splay tree gty work

I've ported the patch you sent me from the pch-branch for the splay tree GC work to the top of the tree. It fell in effortlessly, most of the work was already in, making this fairly easy. I didn't include the alpha change below, as I don't have a good way to test that part of the change, aside from that, this is the balance of the work, plus one bug fix to gengtype.c, and one bug fix to ggc_splay_alloc.

I have completed a test on i586-pc-linux-gnu, should this go into mainline or bib?

2002-10-01 Mike Stump <mrs.apple.com>

* ggc-common.c (ggc_splay_alloc): Actually return the allocated area.
* gengtype.c (write_gc_structure_fields): Handle param[digit]_is.

2002-10-01 Geoffrey Keating <geoffk@apple.com>

The following changes are merged from pch-branch:

* ggc-common.c (ggc_splay_alloc): New.
(ggc_splay_dont_free): New.
* splay-tree.h (GTY): Define if undefined.
(splay_tree_allocate_fn): Return PTR for compatibility, not void *.
(struct splay_tree_node_s): Support gengtype.
(struct splay_tree_s): Likewise. Make allocate_data a PTR,
not a void *.
* ggc.h (splay_tree_new_ggc): New.
(ggc_splay_alloc): Declare.
(ggc_splay_dont_free): Declare.
* dwarf2asm.c: Include gt-dwarf2asm.h.
(mark_indirect_pool_entry): Delete.
(mark_indirect_pool): Delete.
(indirect_pool): Use gengtype to mark.
(dw2_force_const_mem): Don't use ggc_add_root.
* Makefile.in (dwarf2asm.o): Depend on gt-dwarf2asm.h.
(GTFILES): Add SPLAY_TREE_H, dwarf2asm.c.
(gt-dwarf2asm.h): Depend on s-gtype.

Doing diffs in Makefile.in.~1~:
*** Makefile.in.~1~ Fri Sep 27 23:25:52 2002
--- Makefile.in Tue Oct 1 11:16:20 2002
*************** dwarf2out.o : dwarf2out.c $(CONFIG_H) $(
*** 1453,1459 ****
hard-reg-set.h $(REGS_H) $(EXPR_H) libfuncs.h toplev.h dwarf2out.h varray.h \
$(GGC_H) except.h dwarf2asm.h $(TM_P_H) langhooks.h gt-dwarf2out.h
dwarf2asm.o : dwarf2asm.c $(CONFIG_H) $(SYSTEM_H) flags.h $(RTL_H) $(TREE_H) \
! output.h dwarf2asm.h $(TM_P_H) $(GGC_H)
vmsdbgout.o : vmsdbgout.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(RTL_H) flags.h \
output.h vmsdbg.h debug.h langhooks.h function.h
xcoffout.o : xcoffout.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(RTL_H) xcoffout.h \
--- 1453,1459 ----
hard-reg-set.h $(REGS_H) $(EXPR_H) libfuncs.h toplev.h dwarf2out.h varray.h \
$(GGC_H) except.h dwarf2asm.h $(TM_P_H) langhooks.h gt-dwarf2out.h
dwarf2asm.o : dwarf2asm.c $(CONFIG_H) $(SYSTEM_H) flags.h $(RTL_H) $(TREE_H) \
! output.h dwarf2asm.h $(TM_P_H) $(GGC_H) gt-dwarf2asm.h
vmsdbgout.o : vmsdbgout.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(RTL_H) flags.h \
output.h vmsdbg.h debug.h langhooks.h function.h
xcoffout.o : xcoffout.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(RTL_H) xcoffout.h \
*************** s-preds: genpreds$(build_exeext) $(srcdi
*** 1831,1845 ****
$(STAMP) s-preds

GTFILES = $(GCONFIG_H) $(srcdir)/location.h \
! $(HASHTAB_H) \
$(srcdir)/bitmap.h $(srcdir)/function.h $(srcdir)/rtl.h $(srcdir)/optabs.h \
$(srcdir)/tree.h $(srcdir)/libfuncs.h $(srcdir)/hashtable.h $(srcdir)/real.h \
$(srcdir)/varray.h $(srcdir)/ssa.h $(srcdir)/insn-addr.h $(srcdir)/cselib.h \
$(srcdir)/c-common.h $(srcdir)/c-tree.h \
$(srcdir)/basic-block.h \
$(srcdir)/alias.c $(srcdir)/bitmap.c $(srcdir)/cselib.c \
! $(srcdir)/dependence.c $(srcdir)/dwarf2out.c $(srcdir)/emit-rtl.c \
! $(srcdir)/except.c $(srcdir)/explow.c $(srcdir)/expr.c \
$(srcdir)/fold-const.c $(srcdir)/function.c \
$(srcdir)/gcse.c $(srcdir)/integrate.c $(srcdir)/lists.c $(srcdir)/optabs.c \
$(srcdir)/profile.c $(srcdir)/ra-build.c $(srcdir)/regclass.c \
--- 1831,1845 ----
$(STAMP) s-preds

GTFILES = $(GCONFIG_H) $(srcdir)/location.h \
! $(HASHTAB_H) $(SPLAY_TREE_H) \
$(srcdir)/bitmap.h $(srcdir)/function.h $(srcdir)/rtl.h $(srcdir)/optabs.h \
$(srcdir)/tree.h $(srcdir)/libfuncs.h $(srcdir)/hashtable.h $(srcdir)/real.h \
$(srcdir)/varray.h $(srcdir)/ssa.h $(srcdir)/insn-addr.h $(srcdir)/cselib.h \
$(srcdir)/c-common.h $(srcdir)/c-tree.h \
$(srcdir)/basic-block.h \
$(srcdir)/alias.c $(srcdir)/bitmap.c $(srcdir)/cselib.c \
! $(srcdir)/dependence.c $(srcdir)/dwarf2out.c $(srcdir)/dwarf2asm.c \
! $(srcdir)/emit-rtl.c $(srcdir)/except.c $(srcdir)/explow.c $(srcdir)/expr.c \
$(srcdir)/fold-const.c $(srcdir)/function.c \
$(srcdir)/gcse.c $(srcdir)/integrate.c $(srcdir)/lists.c $(srcdir)/optabs.c \
$(srcdir)/profile.c $(srcdir)/ra-build.c $(srcdir)/regclass.c \
*************** gt-integrate.h gt-stmt.h gt-tree.h gt-va
*** 1859,1865 ****
gt-explow.h gt-stor-layout.h gt-regclass.h gt-lists.h : s-gtype; @true
gt-alias.h gt-cselib.h gt-fold-const.h gt-gcse.h gt-profile.h : s-gtype; @true
gt-expr.h gt-sdbout.h gt-optabs.h gt-bitmap.h gt-dwarf2out.h : s-gtype ; @true
! gt-ra-build.h gt-reg-stack.h gt-dependence.h : s-gtype ; @true
gt-c-common.h gt-c-decl.h gt-c-parse.h gt-c-pragma.h : s-gtype; @true
gt-c-objc-common.h gtype-c.h gt-location.h : s-gtype ; @true

--- 1859,1865 ----
gt-explow.h gt-stor-layout.h gt-regclass.h gt-lists.h : s-gtype; @true
gt-alias.h gt-cselib.h gt-fold-const.h gt-gcse.h gt-profile.h : s-gtype; @true
gt-expr.h gt-sdbout.h gt-optabs.h gt-bitmap.h gt-dwarf2out.h : s-gtype ; @true
! gt-ra-build.h gt-reg-stack.h gt-dependence.h gt-dwarf2asm.h : s-gtype ; @true
gt-c-common.h gt-c-decl.h gt-c-parse.h gt-c-pragma.h : s-gtype; @true
gt-c-objc-common.h gtype-c.h gt-location.h : s-gtype ; @true

--------------
Doing diffs in dwarf2asm.c.~1~:
*** dwarf2asm.c.~1~ Fri Sep 13 18:01:28 2002
--- dwarf2asm.c Mon Sep 30 22:17:24 2002
*************** dw2_asm_output_delta_sleb128 VPARAMS ((c
*** 687,698 ****
VA_CLOSE (ap);
}


- static int mark_indirect_pool_entry PARAMS ((splay_tree_node, void *));
- static void mark_indirect_pool PARAMS ((PTR arg));
static rtx dw2_force_const_mem PARAMS ((rtx));
static int dw2_output_indirect_constant_1 PARAMS ((splay_tree_node, void *));

! static splay_tree indirect_pool;

#if defined(HAVE_GAS_HIDDEN) && defined(SUPPORTS_ONE_ONLY)
# define USE_LINKONCE_INDIRECT 1
--- 687,696 ----
VA_CLOSE (ap);
}


static rtx dw2_force_const_mem PARAMS ((rtx));
static int dw2_output_indirect_constant_1 PARAMS ((splay_tree_node, void *));

! static GTY((param1_is (char *), param2_is (tree))) splay_tree indirect_pool;

#if defined(HAVE_GAS_HIDDEN) && defined(SUPPORTS_ONE_ONLY)
# define USE_LINKONCE_INDIRECT 1
*************** static splay_tree indirect_pool;
*** 700,725 ****
# define USE_LINKONCE_INDIRECT 0
#endif

- /* Mark all indirect constants for GC. */
-
- static int
- mark_indirect_pool_entry (node, data)
- splay_tree_node node;
- void* data ATTRIBUTE_UNUSED;
- {
- ggc_mark_tree ((tree) node->value);
- return 0;
- }
-
- /* Mark all indirect constants for GC. */
-
- static void
- mark_indirect_pool (arg)
- PTR arg ATTRIBUTE_UNUSED;
- {
- splay_tree_foreach (indirect_pool, mark_indirect_pool_entry, NULL);
- }
-
/* Put X, a SYMBOL_REF, in memory. Return a SYMBOL_REF to the allocated
memory. Differs from force_const_mem in that a single pool is used for
the entire unit of translation, and the memory is not guaranteed to be
--- 698,703 ----
*************** dw2_force_const_mem (x)
*** 734,743 ****
tree decl;

if (! indirect_pool)
! {
! indirect_pool = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
! ggc_add_root (&indirect_pool, 1, sizeof indirect_pool, mark_indirect_pool);
! }

if (GET_CODE (x) != SYMBOL_REF)
abort ();
--- 712,718 ----
tree decl;

if (! indirect_pool)
! indirect_pool = splay_tree_new_ggc (splay_tree_compare_pointers);

if (GET_CODE (x) != SYMBOL_REF)
abort ();
*************** dw2_asm_output_encoded_addr_rtx VPARAMS
*** 905,907 ****
--- 880,884 ----

VA_CLOSE (ap);
}
+
+ #include "gt-dwarf2asm.h"
--------------
Doing diffs in gengtype.c.~1~:
*** gengtype.c.~1~ Mon Sep 30 23:54:38 2002
--- gengtype.c Tue Oct 1 16:25:54 2002
*************** write_gc_structure_fields (of, s, val, p
*** 1553,1558 ****
--- 1553,1562 ----
;
else if (strcmp (oo->name, "param_is") == 0)
;
+ else if (strncmp (oo->name, "param", 5) == 0
+ && ISDIGIT (oo->name[5])
+ && strcmp (oo->name + 6, "_is") == 0)
+ ;
else if (strncmp (oo->name, "use_param", 9) == 0
&& (oo->name[9] == '\0' || ISDIGIT (oo->name[9])))
use_param_num = oo->name[9] == '\0' ? 0 : oo->name[9] - '0';
--------------
Doing diffs in ggc-common.c.~1~:
*** ggc-common.c.~1~ Wed Sep 25 12:11:37 2002
--- ggc-common.c Tue Oct 1 18:03:07 2002
*************** ggc_calloc (s1, s2)
*** 170,175 ****
--- 170,195 ----
return ggc_alloc_cleared (s1 * s2);
}

+ /* These are for splay_tree_new_ggc. */
+ PTR
+ ggc_splay_alloc (sz, nl)
+ int sz;
+ PTR nl;
+ {
+ if (nl != NULL)
+ abort ();
+ return ggc_alloc (sz);
+ }
+
+ void
+ ggc_splay_dont_free (x, nl)
+ PTR x;
+ PTR nl ATTRIBUTE_UNUSED;
+ {
+ if (nl != NULL)
+ abort ();
+ }
+
/* Print statistics that are independent of the collector in use. */
#define SCALE(x) ((unsigned long) ((x) < 1024*10 \
? (x) \
--------------
Doing diffs in ggc-common.c.~2~:
--------------
Doing diffs in ggc.h.~1~:
*** ggc.h.~1~ Wed Sep 25 12:11:37 2002
--- ggc.h Mon Sep 30 22:17:47 2002
*************** extern void *ggc_calloc PARAMS ((size_t
*** 115,120 ****
--- 115,127 ----
#define htab_create_ggc(SIZE, HASH, EQ, DEL) \
htab_create_alloc (SIZE, HASH, EQ, DEL, ggc_calloc, NULL)

+ #define splay_tree_new_ggc(COMPARE) \
+ splay_tree_new_with_allocator (COMPARE, NULL, NULL, \
+ &ggc_splay_alloc, &ggc_splay_dont_free, \
+ NULL)
+ extern PTR ggc_splay_alloc PARAMS ((int, void *));
+ extern void ggc_splay_dont_free PARAMS ((void *, void *));
+
/* Allocate a gc-able string, and fill it with LENGTH bytes from CONTENTS.
If LENGTH is -1, then CONTENTS is assumed to be a
null-terminated string and the memory sized accordingly. */
--------------
Doing diffs in ../include/splay-tree.h.~1~:
*** ../include/splay-tree.h.~1~ Fri Jul 19 11:21:28 2002
--- ../include/splay-tree.h Mon Sep 30 22:17:51 2002
*************** extern "C" {
*** 36,41 ****
--- 36,45 ----

#include "ansidecl.h"

+ #ifndef GTY
+ #define GTY(X)
+ #endif
+
/* Use typedefs for the key and data types to facilitate changing
these types, if necessary. These types should be sufficiently wide
that any pointer or scalar can be cast to these types, and then
*************** typedef int (*splay_tree_foreach_fn) PAR
*** 65,71 ****
node structures. The first argument is the number of bytes needed;
the second is a data pointer the splay tree functions pass through
to the allocator. This function must never return zero. */
! typedef void *(*splay_tree_allocate_fn) PARAMS((int, void *));

/* The type of a function used to free memory allocated using the
corresponding splay_tree_allocate_fn. The first argument is the
--- 69,75 ----
node structures. The first argument is the number of bytes needed;
the second is a data pointer the splay tree functions pass through
to the allocator. This function must never return zero. */
! typedef PTR (*splay_tree_allocate_fn) PARAMS((int, void *));

/* The type of a function used to free memory allocated using the
corresponding splay_tree_allocate_fn. The first argument is the
*************** typedef void *(*splay_tree_allocate_fn)
*** 74,97 ****
typedef void (*splay_tree_deallocate_fn) PARAMS((void *, void *));

/* The nodes in the splay tree. */
! struct splay_tree_node_s
{
/* The key. */
! splay_tree_key key;

/* The value. */
! splay_tree_value value;

/* The left and right children, respectively. */
! splay_tree_node left;
! splay_tree_node right;
};

/* The splay tree itself. */
! typedef struct splay_tree_s
{
/* The root of the tree. */
! splay_tree_node root;

/* The comparision function. */
splay_tree_compare_fn comp;
--- 78,101 ----
typedef void (*splay_tree_deallocate_fn) PARAMS((void *, void *));

/* The nodes in the splay tree. */
! struct splay_tree_node_s GTY(())
{
/* The key. */
! splay_tree_key GTY ((use_param1 (""))) key;

/* The value. */
! splay_tree_value GTY ((use_param2 (""))) value;

/* The left and right children, respectively. */
! splay_tree_node GTY ((use_params (""))) left;
! splay_tree_node GTY ((use_params (""))) right;
};

/* The splay tree itself. */
! struct splay_tree_s GTY(())
{
/* The root of the tree. */
! splay_tree_node GTY ((use_params (""))) root;

/* The comparision function. */
splay_tree_compare_fn comp;
*************** typedef struct splay_tree_s
*** 105,113 ****
/* Allocate/free functions, and a data pointer to pass to them. */
splay_tree_allocate_fn allocate;
splay_tree_deallocate_fn deallocate;
! void *allocate_data;

! } *splay_tree;

extern splay_tree splay_tree_new PARAMS((splay_tree_compare_fn,
splay_tree_delete_key_fn,
--- 109,118 ----
/* Allocate/free functions, and a data pointer to pass to them. */
splay_tree_allocate_fn allocate;
splay_tree_deallocate_fn deallocate;
! PTR GTY((skip (""))) allocate_data;

! };
! typedef struct splay_tree_s *splay_tree;

extern splay_tree splay_tree_new PARAMS((splay_tree_compare_fn,
splay_tree_delete_key_fn,
--------------

Attachment: save2b.diffs
Description: Binary data

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]