This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
PR2741
- To: gcc-patches at gcc dot gnu dot org
- Subject: PR2741
- From: Mark Mitchell <mark at codesourcery dot com>
- Date: Mon, 07 May 2001 08:43:37 -0700
- Organization: CodeSourcery, LLC
This patch fixes PR2741, a C++ regression from GCC 2.95.2. The
compiler would take huge amounts of memory and time to compile a class
with a large array.
Bootstrapped and tested on i686-pc-linux-gnu, applied on the mainline
and branch.
--
Mark Mitchell mark@codesourcery.com
CodeSourcery, LLC http://www.codesourcery.com
2001-05-07 Mark Mitchell <mark@codesourcery.com>
* splay-tree.h (splay_tree_max): New function.
(splay_tree_min): Likewise.
2001-05-07 Mark Mitchell <mark@codesourcery.com>
* class.c (walk_subobject_offsets): Add max_offset parameter.
(record_subobject_offsets): Adjust call.
(layout_conflict_p): Stop walking when we get past the last empty
subobject.
Index: include/splay-tree.h
===================================================================
RCS file: /cvs/gcc/gcc/include/splay-tree.h,v
retrieving revision 1.12
diff -c -p -r1.12 splay-tree.h
*** splay-tree.h 2000/09/10 21:28:21 1.12
--- splay-tree.h 2001/05/07 15:37:56
***************
*** 1,5 ****
/* A splay-tree datatype.
! Copyright (C) 1998, 2000 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
This file is part of GNU CC.
--- 1,5 ----
/* A splay-tree datatype.
! Copyright (C) 1998, 2000, 2001 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
This file is part of GNU CC.
*************** extern splay_tree_node splay_tree_predec
*** 110,115 ****
--- 110,119 ----
extern splay_tree_node splay_tree_successor
PARAMS((splay_tree,
splay_tree_key));
+ extern splay_tree_node splay_tree_max
+ PARAMS((splay_tree));
+ extern splay_tree_node splay_tree_min
+ PARAMS((splay_tree));
extern int splay_tree_foreach PARAMS((splay_tree,
splay_tree_foreach_fn,
void*));
Index: libiberty/splay-tree.c
===================================================================
RCS file: /cvs/gcc/gcc/libiberty/splay-tree.c,v
retrieving revision 1.17
diff -c -p -r1.17 splay-tree.c
*** splay-tree.c 2000/10/01 19:19:30 1.17
--- splay-tree.c 2001/05/07 15:37:58
***************
*** 1,5 ****
/* A splay-tree datatype.
! Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
This file is part of GNU CC.
--- 1,5 ----
/* A splay-tree datatype.
! Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
Contributed by Mark Mitchell (mark@markmitchell.com).
This file is part of GNU CC.
*************** splay_tree_lookup (sp, key)
*** 366,371 ****
--- 366,405 ----
return sp->root;
else
return 0;
+ }
+
+ /* Return the node in SP with the greatest key. */
+
+ splay_tree_node
+ splay_tree_max (sp)
+ splay_tree sp;
+ {
+ splay_tree_node n = sp->root;
+
+ if (!n)
+ return NULL;
+
+ while (n->right)
+ n = n->right;
+
+ return n;
+ }
+
+ /* Return the node in SP with the smallest key. */
+
+ splay_tree_node
+ splay_tree_min (sp)
+ splay_tree sp;
+ {
+ splay_tree_node n = sp->root;
+
+ if (!n)
+ return NULL;
+
+ while (n->left)
+ n = n->left;
+
+ return n;
}
/* Return the immediate predecessor KEY, or NULL if there is no
Index: gcc/cp/class.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/class.c,v
retrieving revision 1.358.2.16
diff -c -p -r1.358.2.16 class.c
*** class.c 2001/04/27 10:46:44 1.358.2.16
--- class.c 2001/05/07 15:38:02
*************** static tree dfs_get_primary_binfo PARAMS
*** 208,214 ****
static int record_subobject_offset PARAMS ((tree, tree, splay_tree));
static int check_subobject_offset PARAMS ((tree, tree, splay_tree));
static int walk_subobject_offsets PARAMS ((tree, subobject_offset_fn,
! tree, splay_tree, int));
static void record_subobject_offsets PARAMS ((tree, tree, splay_tree, int));
static int layout_conflict_p PARAMS ((tree, tree, splay_tree, int));
static int splay_tree_compare_integer_csts PARAMS ((splay_tree_key k1,
--- 208,214 ----
static int record_subobject_offset PARAMS ((tree, tree, splay_tree));
static int check_subobject_offset PARAMS ((tree, tree, splay_tree));
static int walk_subobject_offsets PARAMS ((tree, subobject_offset_fn,
! tree, splay_tree, tree, int));
static void record_subobject_offsets PARAMS ((tree, tree, splay_tree, int));
static int layout_conflict_p PARAMS ((tree, tree, splay_tree, int));
static int splay_tree_compare_integer_csts PARAMS ((splay_tree_key k1,
*************** check_subobject_offset (type, offset, of
*** 3823,3842 ****
/* Walk through all the subobjects of TYPE (located at OFFSET). Call
F for every subobject, passing it the type, offset, and table of
OFFSETS. If VBASES_P is non-zero, then even virtual non-primary
! bases should be traversed; otherwise, they are ignored. If F
! returns a non-zero value, the traversal ceases, and that value is
! returned. Otherwise, returns zero. */
static int
! walk_subobject_offsets (type, f, offset, offsets, vbases_p)
tree type;
subobject_offset_fn f;
tree offset;
splay_tree offsets;
int vbases_p;
{
int r = 0;
if (CLASS_TYPE_P (type))
{
tree field;
--- 3823,3852 ----
/* Walk through all the subobjects of TYPE (located at OFFSET). Call
F for every subobject, passing it the type, offset, and table of
OFFSETS. If VBASES_P is non-zero, then even virtual non-primary
! bases should be traversed; otherwise, they are ignored.
+ If MAX_OFFSET is non-NULL, then subobjects with an offset greater
+ than MAX_OFFSET will not be walked.
+
+ If F returns a non-zero value, the traversal ceases, and that value
+ is returned. Otherwise, returns zero. */
+
static int
! walk_subobject_offsets (type, f, offset, offsets, max_offset, vbases_p)
tree type;
subobject_offset_fn f;
tree offset;
splay_tree offsets;
+ tree max_offset;
int vbases_p;
{
int r = 0;
+ /* If this OFFSET is bigger than the MAX_OFFSET, then we should
+ stop. */
+ if (max_offset && INT_CST_LT (max_offset, offset))
+ return 0;
+
if (CLASS_TYPE_P (type))
{
tree field;
*************** walk_subobject_offsets (type, f, offset,
*** 3863,3868 ****
--- 3873,3879 ----
offset,
BINFO_OFFSET (binfo)),
offsets,
+ max_offset,
vbases_p);
if (r)
return r;
*************** walk_subobject_offsets (type, f, offset,
*** 3878,3883 ****
--- 3889,3895 ----
offset,
DECL_FIELD_OFFSET (field)),
offsets,
+ max_offset,
/*vbases_p=*/1);
if (r)
return r;
*************** walk_subobject_offsets (type, f, offset,
*** 3897,3907 ****
--- 3909,3925 ----
f,
offset,
offsets,
+ max_offset,
/*vbases_p=*/1);
if (r)
return r;
offset = size_binop (PLUS_EXPR, offset,
TYPE_SIZE_UNIT (TREE_TYPE (type)));
+ /* If this new OFFSET is bigger than the MAX_OFFSET, then
+ there's no point in iterating through the remaining
+ elements of the array. */
+ if (max_offset && INT_CST_LT (max_offset, offset))
+ break;
}
}
*************** record_subobject_offsets (type, offset,
*** 3920,3926 ****
int vbases_p;
{
walk_subobject_offsets (type, record_subobject_offset, offset,
! offsets, vbases_p);
}
/* Returns non-zero if any of the empty subobjects of TYPE (located at
--- 3938,3944 ----
int vbases_p;
{
walk_subobject_offsets (type, record_subobject_offset, offset,
! offsets, /*max_offset=*/NULL_TREE, vbases_p);
}
/* Returns non-zero if any of the empty subobjects of TYPE (located at
*************** layout_conflict_p (type, offset, offsets
*** 3934,3941 ****
splay_tree offsets;
int vbases_p;
{
return walk_subobject_offsets (type, check_subobject_offset, offset,
! offsets, vbases_p);
}
/* DECL is a FIELD_DECL corresponding either to a base subobject of a
--- 3952,3970 ----
splay_tree offsets;
int vbases_p;
{
+ splay_tree_node max_node;
+
+ /* Get the node in OFFSETS that indicates the maximum offset where
+ an empty subobject is located. */
+ max_node = splay_tree_max (offsets);
+ /* If there aren't any empty subobjects, then there's no point in
+ performing this check. */
+ if (!max_node)
+ return 0;
+
return walk_subobject_offsets (type, check_subobject_offset, offset,
! offsets, (tree) (max_node->key),
! vbases_p);
}
/* DECL is a FIELD_DECL corresponding either to a base subobject of a