This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[libmudflap] splay tree forking
- From: "Frank Ch. Eigler" <fche at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 29 Jun 2004 18:25:47 -0400
- Subject: [libmudflap] splay tree forking
Hi -
The following patch brings over a slightly modified copy
of splay-tree.[ch] from libiberty into libmudflap. I don't
forsee this is a long-term situation, but should give some
extra experimentation freedom for performance tuning. As
a first step, libmudflap runs in 15% less time than yesterday.
+2004-06-29 Frank Ch. Eigler <fche@redhat.com>
+
+ Splay tree implementation fork.
+ * splay-tree.c, splay-tree.h: Copied & modified from libiberty.
+ Use hard-coded comparison function for uintptr_t. Remove key/value
+ deallocation logic. Cache last splayed key for consecutive lookups.
+ * Makefile.am, Makefile.in: Use them, don't link to them.
+ * mf-runtime.c (__mf_object_tree): Adapt to simpler splay_tree_new.
+ (__mf_find_objects2): Flip successor/predecessor search sequence.
+ * ansidecl.h, libiberty.h: Removed dummy files.
Index: Makefile.am
===================================================================
RCS file: /cvs/gcc/gcc/libmudflap/Makefile.am,v
retrieving revision 1.7
diff -u -p -r1.7 Makefile.am
--- Makefile.am 24 Jun 2004 21:12:16 -0000 1.7
+++ Makefile.am 29 Jun 2004 22:22:01 -0000
@@ -20,14 +20,6 @@ endif
toolexeclib_LTLIBRARIES = libmudflap.la $(libmudflapth)
include_HEADERS = mf-runtime.h
-# Copy this out of libiberty's source tree, so it can be built here via libtool
-splay-tree.c:
- rm -f $@
- $(LN_S) $(srcdir)/../libiberty/splay-tree.c $@
-# Copy this so that top-level include/ does not have to be put into -I path
-splay-tree.h:
- rm -f $@
- $(LN_S) $(srcdir)/../include/splay-tree.h $@
libmudflap_la_SOURCES = \
mf-runtime.c \
@@ -40,7 +32,6 @@ libmudflap_la_DEPENDENCIES = $(libmudfla
clean-local:
rm -f pth/*.o pth/*.lo
- rm -f splay-tree.c splay-tree.h
pth/mf-runtime.lo: mf-runtime.c mf-runtime.h mf-impl.h splay-tree.c splay-tree.h
$(LTCOMPILE) -DLIBMUDFLAPTH -c $(srcdir)/mf-runtime.c -o $@
Index: mf-runtime.c
===================================================================
RCS file: /cvs/gcc/gcc/libmudflap/mf-runtime.c,v
retrieving revision 1.8
diff -u -p -r1.8 mf-runtime.c
--- mf-runtime.c 29 Jun 2004 09:53:50 -0000 1.8
+++ mf-runtime.c 29 Jun 2004 22:22:01 -0000
@@ -610,7 +610,7 @@ __mf_object_tree (int type)
static splay_tree trees [__MF_TYPE_MAX+1];
assert (type >= 0 && type <= __MF_TYPE_MAX);
if (UNLIKELY (trees[type] == NULL))
- trees[type] = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
+ trees[type] = splay_tree_new ();
return trees[type];
}
@@ -1390,7 +1390,7 @@ __mf_find_objects2 (uintptr_t ptr_low, u
{
__mf_object_t *obj;
- n = (direction == 0 ? splay_tree_predecessor (t, k) : splay_tree_successor (t, k));
+ n = (direction == 0 ? splay_tree_successor (t, k) : splay_tree_predecessor (t, k));
if (n == NULL) break;
obj = (__mf_object_t *) n->value;
--- ../libiberty/splay-tree.c 2004-06-28 14:41:45.000000000 -0400
+++ ./splay-tree.c 2004-06-29 15:45:34.000000000 -0400
@@ -1,6 +1,7 @@
/* A splay-tree datatype.
- Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+ Copyright (C) 1998, 1999, 2000, 2001, 2004 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
+ Adapted for libmudflap from libiberty.
This file is part of GNU CC.
@@ -9,6 +10,15 @@
the Free Software Foundation; either version 2, or (at your option)
any later version.
+In addition to the permissions in the GNU General Public License, the
+Free Software Foundation gives you unlimited permission to link the
+compiled version of this file into combinations with other programs,
+and to distribute those combinations without any restriction coming
+from the use of this file. (The General Public License restrictions
+do apply in other respects; for example, they cover modification of
+the file, and distribution when not linked into a combine
+executable.)
+
GNU CC 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
@@ -24,17 +34,8 @@
Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
Algorithms. Harper-Collins, Inc. 1991. */
-#ifdef HAVE_CONFIG_H
-#include "config.h"
-#endif
-
-#ifdef HAVE_STDLIB_H
#include <stdlib.h>
-#endif
-
#include <stdio.h>
-
-#include "libiberty.h"
#include "splay-tree.h"
static void splay_tree_delete_helper PARAMS((splay_tree,
@@ -52,6 +53,22 @@
splay_tree_foreach_fn,
void*));
+
+
+/* Inline comparison function specialized for libmudflap's key type. */
+static inline int
+compare_uintptr_t (splay_tree_key k1, splay_tree_key k2)
+{
+ if ((uintptr_t) k1 < (uintptr_t) k2)
+ return -1;
+ else if ((uintptr_t) k1 > (uintptr_t) k2)
+ return 1;
+ else
+ return 0;
+}
+
+
+
/* Deallocate NODE (a member of SP), and all its sub-trees. */
static void
@@ -64,12 +81,6 @@
splay_tree_delete_helper (sp, node->left);
splay_tree_delete_helper (sp, node->right);
-
- if (sp->delete_key)
- (*sp->delete_key)(node->key);
- if (sp->delete_value)
- (*sp->delete_value)(node->value);
-
(*sp->deallocate) ((char*) node, sp->allocate_data);
}
@@ -93,7 +104,7 @@
if (!n)
return *parent;
- comparison = (*sp->comp) (key, n->key);
+ comparison = compare_uintptr_t (key, n->key);
if (comparison == 0)
/* We've found the target. */
@@ -197,7 +208,7 @@
/* If we just splayed the tree with the same key, do nothing. */
if (sp->last_splayed_key_p &&
- (*sp->comp)(sp->last_splayed_key, key) == 0)
+ compare_uintptr_t (sp->last_splayed_key, key) == 0)
return;
splay_tree_splay_helper (sp, key, &sp->root,
@@ -261,37 +272,14 @@
nodes added. */
splay_tree
-splay_tree_new (compare_fn, delete_key_fn, delete_value_fn)
- splay_tree_compare_fn compare_fn;
- splay_tree_delete_key_fn delete_key_fn;
- splay_tree_delete_value_fn delete_value_fn;
-{
- return (splay_tree_new_with_allocator
- (compare_fn, delete_key_fn, delete_value_fn,
- splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
-}
-
-
-/* Allocate a new splay tree, using COMPARE_FN to compare nodes,
- DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
- values. */
-
-splay_tree
-splay_tree_new_with_allocator (compare_fn, delete_key_fn, delete_value_fn,
- allocate_fn, deallocate_fn, allocate_data)
- splay_tree_compare_fn compare_fn;
- splay_tree_delete_key_fn delete_key_fn;
- splay_tree_delete_value_fn delete_value_fn;
- splay_tree_allocate_fn allocate_fn;
- splay_tree_deallocate_fn deallocate_fn;
- void *allocate_data;
+splay_tree_new ()
{
+ splay_tree_allocate_fn allocate_fn = splay_tree_xmalloc_allocate;
+ splay_tree_deallocate_fn deallocate_fn = splay_tree_xmalloc_deallocate;
+ void *allocate_data = NULL;
splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s),
allocate_data);
sp->root = 0;
- sp->comp = compare_fn;
- sp->delete_key = delete_key_fn;
- sp->delete_value = delete_value_fn;
sp->allocate = allocate_fn;
sp->deallocate = deallocate_fn;
sp->allocate_data = allocate_data;
@@ -323,17 +311,14 @@
int comparison = 0;
splay_tree_splay (sp, key);
- sp->last_splayed_key_p = 0;
if (sp->root)
- comparison = (*sp->comp)(sp->root->key, key);
+ comparison = compare_uintptr_t (sp->root->key, key);
if (sp->root && comparison == 0)
{
/* If the root of the tree already has the indicated KEY, just
replace the value with VALUE. */
- if (sp->delete_value)
- (*sp->delete_value)(sp->root->value);
sp->root->value = value;
}
else
@@ -363,6 +348,7 @@
}
sp->root = node;
+ sp->last_splayed_key_p = 0;
}
return sp->root;
@@ -378,7 +364,7 @@
splay_tree_splay (sp, key);
sp->last_splayed_key_p = 0;
- if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
+ if (sp->root && compare_uintptr_t (sp->root->key, key) == 0)
{
splay_tree_node left, right;
@@ -386,8 +372,6 @@
right = sp->root->right;
/* Delete the root node itself. */
- if (sp->delete_value)
- (*sp->delete_value) (sp->root->value);
(*sp->deallocate) (sp->root, sp->allocate_data);
/* One of the children is now the root. Doesn't matter much
@@ -420,7 +404,7 @@
{
splay_tree_splay (sp, key);
- if (sp->root && (*sp->comp)(sp->root->key, key) == 0)
+ if (sp->root && compare_uintptr_t (sp->root->key, key) == 0)
return sp->root;
else
return 0;
@@ -478,7 +462,7 @@
/* Splay the tree around KEY. That will leave either the KEY
itself, its predecessor, or its successor at the root. */
splay_tree_splay (sp, key);
- comparison = (*sp->comp)(sp->root->key, key);
+ comparison = compare_uintptr_t (sp->root->key, key);
/* If the predecessor is at the root, just return it. */
if (comparison < 0)
@@ -511,7 +495,7 @@
/* Splay the tree around KEY. That will leave either the KEY
itself, its predecessor, or its successor at the root. */
splay_tree_splay (sp, key);
- comparison = (*sp->comp)(sp->root->key, key);
+ comparison = compare_uintptr_t (sp->root->key, key);
/* If the successor is at the root, just return it. */
if (comparison > 0)
@@ -539,33 +523,3 @@
{
return splay_tree_foreach_helper (sp, sp->root, fn, data);
}
-
-/* Splay-tree comparison function, treating the keys as ints. */
-
-int
-splay_tree_compare_ints (k1, k2)
- splay_tree_key k1;
- splay_tree_key k2;
-{
- if ((int) k1 < (int) k2)
- return -1;
- else if ((int) k1 > (int) k2)
- return 1;
- else
- return 0;
-}
-
-/* Splay-tree comparison function, treating the keys as pointers. */
-
-int
-splay_tree_compare_pointers (k1, k2)
- splay_tree_key k1;
- splay_tree_key k2;
-{
- if ((char*) k1 < (char*) k2)
- return -1;
- else if ((char*) k1 > (char*) k2)
- return 1;
- else
- return 0;
-}
--- ../include/splay-tree.h 2004-06-28 16:51:53.000000000 -0400
+++ ./splay-tree.h 2004-06-29 15:20:57.000000000 -0400
@@ -1,6 +1,7 @@
/* A splay-tree datatype.
Copyright 1998, 1999, 2000, 2002, 2004 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
+ Adapted for libmudflap from libiberty.
This file is part of GCC.
@@ -34,7 +35,9 @@
extern "C" {
#endif /* __cplusplus */
-#include "ansidecl.h"
+#define PARAMS(X) X
+#define PTR void *
+#define ATTRIBUTE_UNUSED __attribute__((__unused__))
#ifndef GTY
#define GTY(X)
@@ -44,24 +47,12 @@
these types, if necessary. These types should be sufficiently wide
that any pointer or scalar can be cast to these types, and then
cast back, without loss of precision. */
-typedef unsigned long int splay_tree_key;
-typedef unsigned long int splay_tree_value;
+typedef uintptr_t splay_tree_key;
+typedef void *splay_tree_value;
/* Forward declaration for a node in the tree. */
typedef struct splay_tree_node_s *splay_tree_node;
-/* The type of a function which compares two splay-tree keys. The
- function should return values as for qsort. */
-typedef int (*splay_tree_compare_fn) PARAMS((splay_tree_key, splay_tree_key));
-
-/* The type of a function used to deallocate any resources associated
- with the key. */
-typedef void (*splay_tree_delete_key_fn) PARAMS((splay_tree_key));
-
-/* The type of a function used to deallocate any resources associated
- with the value. */
-typedef void (*splay_tree_delete_value_fn) PARAMS((splay_tree_value));
-
/* The type of a function used to iterate over the tree. */
typedef int (*splay_tree_foreach_fn) PARAMS((splay_tree_node, void*));
@@ -97,15 +88,6 @@
/* The root of the tree. */
splay_tree_node GTY ((use_params)) root;
- /* The comparision function. */
- splay_tree_compare_fn comp;
-
- /* The deallocate-key function. NULL if no cleanup is necessary. */
- splay_tree_delete_key_fn delete_key;
-
- /* The deallocate-value function. NULL if no cleanup is necessary. */
- splay_tree_delete_value_fn delete_value;
-
/* Allocate/free functions, and a data pointer to pass to them. */
splay_tree_allocate_fn allocate;
splay_tree_deallocate_fn deallocate;
@@ -118,16 +100,7 @@
};
typedef struct splay_tree_s *splay_tree;
-extern splay_tree splay_tree_new PARAMS((splay_tree_compare_fn,
- splay_tree_delete_key_fn,
- splay_tree_delete_value_fn));
-extern splay_tree splay_tree_new_with_allocator
- PARAMS((splay_tree_compare_fn,
- splay_tree_delete_key_fn,
- splay_tree_delete_value_fn,
- splay_tree_allocate_fn,
- splay_tree_deallocate_fn,
- void *));
+extern splay_tree splay_tree_new PARAMS((void));
extern void splay_tree_delete PARAMS((splay_tree));
extern splay_tree_node splay_tree_insert
PARAMS((splay_tree,