This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: PR c++/5504: Optimization breaks wei-ku-1 from blitz
- From: Richard Henderson <rth at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 9 Apr 2002 14:02:08 -0700
- Subject: Re: PR c++/5504: Optimization breaks wei-ku-1 from blitz
- References: <20020326050034.GA29663@tornado.toronto.redhat.com> <wvlhempwz9b.fsf@prospero.cambridge.redhat.com> <20020409000042.A7972@redhat.com>
Here's the patch I committed to the 3.1 branch.
Tested on i686 and alphaev6 linux.
Problem 1: Linear search on exception_handler_labels.
Solved by setting LABEL_PRESERVE_P on the labels.
(for jump.c and can_delete_label_p), or using a
different check for the existence of eh handlers
(sched-rgn.c).
There's one remaining iteration over eh labels in loop.c.
I don't think there's a way to get rid of it without Jan
and Zdenek's loop rewrite from cfg-branch. As it happens,
it doesn't impact this test case because the bulk of the
eh regions have been removed by the time we get to loop.
Problem 2: Linear search on eh regions looking for eh labels.
Solved by creating a hash table mapping CODE_LABEL_NUMBER
to eh region.
Problem 2b: Bug in hashtab.c given a table of size 2.
The hash table created above was sized by the number of
live eh regions. When less than 3 regions, the hashtab
uses size 2. Except that the rehash uses % (size - 2),
so we divide by zero.
Solved by making 7 the minimum hash table size.
I also rearranged two functions to avoid the extra
division if possible. Similar to what Zack did with
htab_find_with_hash earlier.
Problem 3: Linear search on eh regions looking for reparented
region numbers.
Solved by adding an "aka" bitmap to the region.
Problem 4: Quadratic behaviour in delete_unreachable_blocks.
We'd call flow_delete_block, which would call expunge_block,
which would copy down all following blocks to fill the hole.
If there are lots and lots of dead blocks, we have O(N) * O(N)
copies.
Solved by creating new block deletion functions that do not
compact the array, and then have delete_unreachable_blocks
do the compaction itself while removing the dead wood.
r~
* basic-block.h (flow_delete_block_noexpunge): Declare.
(expunge_block_nocompact): Declare.
* cfg.c (expunge_block_nocompact): Split out from ...
(expunge_block): ... here.
* cfgrtl.c (can_delete_label_p): Don't use exception_handler_labels.
(flow_delete_block_noexpunge): Split out from ...
(flow_delete_block): ... here.
* cfgcleanup.c (delete_unreachable_blocks): Compact while
removing dead blocks.
* except.c (exception_handler_labels): Remove.
(exception_handler_label_map): New.
(struct eh_region): Add aka member.
(mark_ehl_map_entry, mark_ehl_map, free_region): New.
(ehl_hash, ehl_eq, ehl_free, add_ehl_entry): New.
(for_each_eh_label, for_each_eh_label_1): New.
(init_eh): Register exception_handler_label_map.
(free_eh_status): Use free_region.
(find_exception_handler_labels): Use the map, not the list.
(remove_exception_handler_label): Likewise.
(maybe_remove_eh_handler): Likewise.
(remove_eh_handler): Use the region aka bitmap.
* except.h (exception_handler_labels): Remove.
(for_each_eh_label): Declare.
* jump.c (rebuild_jump_labels): Don't check exception_handler_labels.
* loop.c (invalidate_loops_containing_label): New.
(find_and_verify_loops): Use it. Use for_each_eh_label.
* sched-rgn.c (is_cfg_nonregular): Use
current_function_has_exception_handlers.
* hashtab.c (higher_prime_number): Use 7 as minimum.
(find_empty_slot_for_expand): Don't compute hash2 unless needed.
(htab_find_slot_with_hash): Likewise.
Index: gcc/basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.134.2.1
diff -c -p -d -r1.134.2.1 basic-block.h
*** gcc/basic-block.h 18 Mar 2002 17:46:57 -0000 1.134.2.1
--- gcc/basic-block.h 9 Apr 2002 20:27:11 -0000
***************
*** 1,5 ****
/* Define control and data flow tables, and regsets.
! Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001
Free Software Foundation, Inc.
This file is part of GCC.
--- 1,5 ----
/* Define control and data flow tables, and regsets.
! Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001, 2002
Free Software Foundation, Inc.
This file is part of GCC.
*************** extern void redirect_edge_pred PARAMS (
*** 311,316 ****
--- 311,317 ----
extern basic_block create_basic_block_structure PARAMS ((int, rtx, rtx, rtx));
extern basic_block create_basic_block PARAMS ((int, rtx, rtx));
extern int flow_delete_block PARAMS ((basic_block));
+ extern int flow_delete_block_noexpunge PARAMS ((basic_block));
extern void merge_blocks_nomove PARAMS ((basic_block, basic_block));
extern void tidy_fallthru_edge PARAMS ((edge, basic_block,
basic_block));
*************** extern void debug_regset PARAMS ((regse
*** 629,634 ****
--- 630,636 ----
extern void allocate_reg_life_data PARAMS ((void));
extern void allocate_bb_life_data PARAMS ((void));
extern void expunge_block PARAMS ((basic_block));
+ extern void expunge_block_nocompact PARAMS ((basic_block));
extern basic_block alloc_block PARAMS ((void));
extern void find_unreachable_blocks PARAMS ((void));
extern void delete_noop_moves PARAMS ((rtx));
Index: gcc/cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.18
diff -c -p -d -r1.18 cfg.c
*** gcc/cfg.c 22 Dec 2001 15:51:07 -0000 1.18
--- gcc/cfg.c 9 Apr 2002 20:27:12 -0000
***************
*** 1,6 ****
/* Control flow graph manipulation code for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
! 1999, 2000, 2001 Free Software Foundation, Inc.
This file is part of GCC.
--- 1,6 ----
/* Control flow graph manipulation code for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
! 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
This file is part of GCC.
*************** alloc_block ()
*** 222,231 ****
/* Remove block B from the basic block array and compact behind it. */
void
expunge_block (b)
basic_block b;
{
! int i, n = n_basic_blocks;
for (i = b->index; i + 1 < n; ++i)
{
--- 222,243 ----
/* Remove block B from the basic block array and compact behind it. */
void
+ expunge_block_nocompact (b)
+ basic_block b;
+ {
+ /* Invalidate data to make bughunting easier. */
+ memset (b, 0, sizeof *b);
+ b->index = -3;
+ basic_block_info->num_elements--;
+ b->succ = (edge) first_deleted_block;
+ first_deleted_block = (basic_block) b;
+ }
+
+ void
expunge_block (b)
basic_block b;
{
! int i, n = n_basic_blocks--;
for (i = b->index; i + 1 < n; ++i)
{
*************** expunge_block (b)
*** 234,246 ****
x->index = i;
}
! /* Invalidate data to make bughunting easier. */
! memset (b, 0, sizeof *b);
! b->index = -3;
! basic_block_info->num_elements--;
! n_basic_blocks--;
! b->succ = (edge) first_deleted_block;
! first_deleted_block = (basic_block) b;
}
/* Create an edge connecting SRC and DST with FLAGS optionally using
--- 246,252 ----
x->index = i;
}
! expunge_block_nocompact (b);
}
/* Create an edge connecting SRC and DST with FLAGS optionally using
Index: gcc/cfgcleanup.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgcleanup.c,v
retrieving revision 1.38.2.1
diff -c -p -d -r1.38.2.1 cfgcleanup.c
*** gcc/cfgcleanup.c 22 Mar 2002 15:17:35 -0000 1.38.2.1
--- gcc/cfgcleanup.c 9 Apr 2002 20:27:12 -0000
***************
*** 1,6 ****
/* Control flow optimization code for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
! 1999, 2000, 2001 Free Software Foundation, Inc.
This file is part of GCC.
--- 1,6 ----
/* Control flow optimization code for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
! 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
This file is part of GCC.
*************** try_optimize_cfg (mode)
*** 1729,1750 ****
static bool
delete_unreachable_blocks ()
{
! int i;
bool changed = false;
find_unreachable_blocks ();
! /* Delete all unreachable basic blocks. Count down so that we
! don't interfere with the block renumbering that happens in
! flow_delete_block. */
! for (i = n_basic_blocks - 1; i >= 0; --i)
{
basic_block b = BASIC_BLOCK (i);
if (!(b->flags & BB_REACHABLE))
! flow_delete_block (b), changed = true;
}
if (changed)
tidy_fallthru_edges ();
--- 1729,1760 ----
static bool
delete_unreachable_blocks ()
{
! int i, j;
bool changed = false;
find_unreachable_blocks ();
! /* Delete all unreachable basic blocks. Do compaction concurrently,
! as otherwise we can wind up with O(N^2) behaviour here when we
! have oodles of dead code. */
! for (i = j = 0; i < n_basic_blocks; ++i)
{
basic_block b = BASIC_BLOCK (i);
if (!(b->flags & BB_REACHABLE))
! {
! flow_delete_block_noexpunge (b);
! expunge_block_nocompact (b);
! changed = true;
! }
! else
! {
! BASIC_BLOCK (j) = b;
! b->index = j++;
! }
}
+ n_basic_blocks = j;
if (changed)
tidy_fallthru_edges ();
Index: gcc/cfgrtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgrtl.c,v
retrieving revision 1.29.2.3
diff -c -p -d -r1.29.2.3 cfgrtl.c
*** gcc/cfgrtl.c 27 Mar 2002 21:53:13 -0000 1.29.2.3
--- gcc/cfgrtl.c 9 Apr 2002 20:27:12 -0000
***************
*** 1,6 ****
/* Control flow graph manipulation code for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
! 1999, 2000, 2001 Free Software Foundation, Inc.
This file is part of GCC.
--- 1,6 ----
/* Control flow graph manipulation code for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
! 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
This file is part of GCC.
*************** can_delete_label_p (label)
*** 101,108 ****
/* User declared labels must be preserved. */
&& LABEL_NAME (label) == 0
&& !in_expr_list_p (forced_labels, label)
! && !in_expr_list_p (label_value_list, label)
! && !in_expr_list_p (exception_handler_labels, label));
}
/* Delete INSN by patching it out. Return the next insn. */
--- 101,107 ----
/* User declared labels must be preserved. */
&& LABEL_NAME (label) == 0
&& !in_expr_list_p (forced_labels, label)
! && !in_expr_list_p (label_value_list, label));
}
/* Delete INSN by patching it out. Return the next insn. */
*************** create_basic_block (index, head, end)
*** 323,329 ****
to post-process the stream to remove empty blocks, loops, ranges, etc. */
int
! flow_delete_block (b)
basic_block b;
{
int deleted_handler = 0;
--- 322,328 ----
to post-process the stream to remove empty blocks, loops, ranges, etc. */
int
! flow_delete_block_noexpunge (b)
basic_block b;
{
int deleted_handler = 0;
*************** flow_delete_block (b)
*** 372,377 ****
--- 371,385 ----
b->pred = NULL;
b->succ = NULL;
+ return deleted_handler;
+ }
+
+ int
+ flow_delete_block (b)
+ basic_block b;
+ {
+ int deleted_handler = flow_delete_block_noexpunge (b);
+
/* Remove the basic block from the array, and compact behind it. */
expunge_block (b);
Index: gcc/except.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/except.c,v
retrieving revision 1.212.2.1
diff -c -p -d -r1.212.2.1 except.c
*** gcc/except.c 20 Mar 2002 01:04:38 -0000 1.212.2.1
--- gcc/except.c 9 Apr 2002 20:27:12 -0000
*************** int (*lang_eh_type_covers) PARAMS ((tree
*** 97,104 ****
/* Map a type to a runtime object to match type. */
tree (*lang_eh_runtime_type) PARAMS ((tree));
! /* A list of labels used for exception handlers. */
! rtx exception_handler_labels;
static int call_site_base;
static unsigned int sjlj_funcdef_number;
--- 97,111 ----
/* Map a type to a runtime object to match type. */
tree (*lang_eh_runtime_type) PARAMS ((tree));
! /* A hash table of label to region number. */
!
! struct ehl_map_entry
! {
! rtx label;
! struct eh_region *region;
! };
!
! static htab_t exception_handler_label_map;
static int call_site_base;
static unsigned int sjlj_funcdef_number;
*************** struct eh_region
*** 125,130 ****
--- 132,141 ----
/* An identifier for this region. */
int region_number;
+ /* When a region is deleted, its parents inherit the REG_EH_REGION
+ numbers already assigned. */
+ bitmap aka;
+
/* Each region does exactly one thing. */
enum eh_region_type
{
*************** struct eh_status
*** 247,252 ****
--- 258,267 ----
static void mark_eh_region PARAMS ((struct eh_region *));
+ static int mark_ehl_map_entry PARAMS ((PTR *, PTR));
+ static void mark_ehl_map PARAMS ((void *));
+
+ static void free_region PARAMS ((struct eh_region *));
static int t2r_eq PARAMS ((const PTR,
const PTR));
*************** static void sjlj_emit_dispatch_table
*** 297,304 ****
--- 312,326 ----
PARAMS ((rtx, struct sjlj_lp_info *));
static void sjlj_build_landing_pads PARAMS ((void));
+ static hashval_t ehl_hash PARAMS ((const PTR));
+ static int ehl_eq PARAMS ((const PTR,
+ const PTR));
+ static void ehl_free PARAMS ((PTR));
+ static void add_ehl_entry PARAMS ((rtx,
+ struct eh_region *));
static void remove_exception_handler_label PARAMS ((rtx));
static void remove_eh_handler PARAMS ((struct eh_region *));
+ static int for_each_eh_label_1 PARAMS ((PTR *, PTR));
struct reachable_info;
*************** doing_eh (do_warn)
*** 369,375 ****
void
init_eh ()
{
! ggc_add_rtx_root (&exception_handler_labels, 1);
if (! flag_exceptions)
return;
--- 391,397 ----
void
init_eh ()
{
! ggc_add_root (&exception_handler_label_map, 1, 1, mark_ehl_map);
if (! flag_exceptions)
return;
*************** mark_eh_region (region)
*** 515,520 ****
--- 537,561 ----
ggc_mark_rtx (region->post_landing_pad);
}
+ static int
+ mark_ehl_map_entry (pentry, data)
+ PTR *pentry;
+ PTR data ATTRIBUTE_UNUSED;
+ {
+ struct ehl_map_entry *entry = *(struct ehl_map_entry **) pentry;
+ ggc_mark_rtx (entry->label);
+ return 1;
+ }
+
+ static void
+ mark_ehl_map (pp)
+ void *pp;
+ {
+ htab_t map = *(htab_t *) pp;
+ if (map)
+ htab_traverse (map, mark_ehl_map_entry, NULL);
+ }
+
void
mark_eh_status (eh)
struct eh_status *eh;
*************** mark_eh_status (eh)
*** 577,582 ****
--- 618,633 ----
ggc_mark_rtx (eh->sjlj_exit_after);
}
+ static inline void
+ free_region (r)
+ struct eh_region *r;
+ {
+ /* Note that the aka bitmap is freed by regset_release_memory. But if
+ we ever replace with a non-obstack implementation, this would be
+ the place to do it. */
+ free (r);
+ }
+
void
free_eh_status (f)
struct function *f;
*************** free_eh_status (f)
*** 591,597 ****
struct eh_region *r = eh->region_array[i];
/* Mind we don't free a region struct more than once. */
if (r && r->region_number == i)
! free (r);
}
free (eh->region_array);
}
--- 642,648 ----
struct eh_region *r = eh->region_array[i];
/* Mind we don't free a region struct more than once. */
if (r && r->region_number == i)
! free_region (r);
}
free (eh->region_array);
}
*************** free_eh_status (f)
*** 605,624 ****
else if (r->next_peer)
{
next = r->next_peer;
! free (r);
r = next;
}
else
{
do {
next = r->outer;
! free (r);
r = next;
if (r == NULL)
goto tree_done;
} while (r->next_peer == NULL);
next = r->next_peer;
! free (r);
r = next;
}
}
--- 656,675 ----
else if (r->next_peer)
{
next = r->next_peer;
! free_region (r);
r = next;
}
else
{
do {
next = r->outer;
! free_region (r);
r = next;
if (r == NULL)
goto tree_done;
} while (r->next_peer == NULL);
next = r->next_peer;
! free_region (r);
r = next;
}
}
*************** free_eh_status (f)
*** 633,639 ****
free (eh);
f->eh = NULL;
! exception_handler_labels = NULL;
}
--- 684,695 ----
free (eh);
f->eh = NULL;
!
! if (exception_handler_label_map)
! {
! htab_delete (exception_handler_label_map);
! exception_handler_label_map = NULL;
! }
}
*************** convert_from_eh_region_ranges ()
*** 1366,1378 ****
remove_unreachable_regions (insns);
}
void
find_exception_handler_labels ()
{
- rtx list = NULL_RTX;
int i;
! free_EXPR_LIST_list (&exception_handler_labels);
if (cfun->eh->region_tree == NULL)
return;
--- 1422,1471 ----
remove_unreachable_regions (insns);
}
+ static void
+ add_ehl_entry (label, region)
+ rtx label;
+ struct eh_region *region;
+ {
+ struct ehl_map_entry **slot, *entry;
+
+ LABEL_PRESERVE_P (label) = 1;
+
+ entry = (struct ehl_map_entry *) xmalloc (sizeof (*entry));
+ entry->label = label;
+ entry->region = region;
+
+ slot = (struct ehl_map_entry **)
+ htab_find_slot (exception_handler_label_map, entry, INSERT);
+ if (*slot)
+ abort ();
+ *slot = entry;
+ }
+
+ static void
+ ehl_free (pentry)
+ PTR pentry;
+ {
+ struct ehl_map_entry *entry = (struct ehl_map_entry *)pentry;
+ LABEL_PRESERVE_P (entry->label) = 0;
+ free (entry);
+ }
+
void
find_exception_handler_labels ()
{
int i;
! if (exception_handler_label_map)
! htab_empty (exception_handler_label_map);
! else
! {
! /* ??? The expansion factor here (3/2) must be greater than the htab
! occupancy factor (4/3) to avoid unnecessary resizing. */
! exception_handler_label_map
! = htab_create (cfun->eh->last_region_number * 3 / 2,
! ehl_hash, ehl_eq, ehl_free);
! }
if (cfun->eh->region_tree == NULL)
return;
*************** find_exception_handler_labels ()
*** 1390,1404 ****
lab = region->label;
if (lab)
! list = alloc_EXPR_LIST (0, lab, list);
}
/* For sjlj exceptions, need the return label to remain live until
after landing pad generation. */
if (USING_SJLJ_EXCEPTIONS && ! cfun->eh->built_landing_pads)
! list = alloc_EXPR_LIST (0, return_label, list);
!
! exception_handler_labels = list;
}
bool
--- 1483,1495 ----
lab = region->label;
if (lab)
! add_ehl_entry (lab, region);
}
/* For sjlj exceptions, need the return label to remain live until
after landing pad generation. */
if (USING_SJLJ_EXCEPTIONS && ! cfun->eh->built_landing_pads)
! add_ehl_entry (return_label, NULL);
}
bool
*************** finish_eh_generation ()
*** 2484,2511 ****
cleanup_cfg (CLEANUP_PRE_LOOP);
}
/* This section handles removing dead code for flow. */
! /* Remove LABEL from the exception_handler_labels list. */
static void
remove_exception_handler_label (label)
rtx label;
{
! rtx *pl, l;
! /* If exception_handler_labels was not built yet,
there is nothing to do. */
! if (exception_handler_labels == NULL)
return;
! for (pl = &exception_handler_labels, l = *pl;
! XEXP (l, 0) != label;
! pl = &XEXP (l, 1), l = *pl)
! continue;
! *pl = XEXP (l, 1);
! free_EXPR_LIST_node (l);
}
/* Splice REGION from the region tree etc. */
--- 2575,2624 ----
cleanup_cfg (CLEANUP_PRE_LOOP);
}
+ static hashval_t
+ ehl_hash (pentry)
+ const PTR pentry;
+ {
+ struct ehl_map_entry *entry = (struct ehl_map_entry *) pentry;
+
+ /* 2^32 * ((sqrt(5) - 1) / 2) */
+ const hashval_t scaled_golden_ratio = 0x9e3779b9;
+ return CODE_LABEL_NUMBER (entry->label) * scaled_golden_ratio;
+ }
+
+ static int
+ ehl_eq (pentry, pdata)
+ const PTR pentry;
+ const PTR pdata;
+ {
+ struct ehl_map_entry *entry = (struct ehl_map_entry *) pentry;
+ struct ehl_map_entry *data = (struct ehl_map_entry *) pdata;
+
+ return entry->label == data->label;
+ }
+
/* This section handles removing dead code for flow. */
! /* Remove LABEL from exception_handler_label_map. */
static void
remove_exception_handler_label (label)
rtx label;
{
! struct ehl_map_entry **slot, tmp;
! /* If exception_handler_label_map was not built yet,
there is nothing to do. */
! if (exception_handler_label_map == NULL)
return;
! tmp.label = label;
! slot = (struct ehl_map_entry **)
! htab_find_slot (exception_handler_label_map, &tmp, NO_INSERT);
! if (! slot)
! abort ();
! htab_clear_slot (exception_handler_label_map, (void **) slot);
}
/* Splice REGION from the region tree etc. */
*************** remove_eh_handler (region)
*** 2516,2531 ****
{
struct eh_region **pp, *p;
rtx lab;
- int i;
/* For the benefit of efficiently handling REG_EH_REGION notes,
replace this region in the region array with its containing
region. Note that previous region deletions may result in
! multiple copies of this region in the array, so we have to
! search the whole thing. */
! for (i = cfun->eh->last_region_number; i > 0; --i)
! if (cfun->eh->region_array[i] == region)
! cfun->eh->region_array[i] = region->outer;
if (cfun->eh->built_landing_pads)
lab = region->landing_pad;
--- 2629,2657 ----
{
struct eh_region **pp, *p;
rtx lab;
/* For the benefit of efficiently handling REG_EH_REGION notes,
replace this region in the region array with its containing
region. Note that previous region deletions may result in
! multiple copies of this region in the array, so we have a
! list of alternate numbers by which we are known. */
!
! cfun->eh->region_array[region->region_number] = region->outer;
! if (region->aka)
! {
! int i;
! EXECUTE_IF_SET_IN_BITMAP (region->aka, 0, i,
! { cfun->eh->region_array[i] = region->outer; });
! }
!
! if (region->outer)
! {
! if (!region->outer->aka)
! region->outer->aka = BITMAP_XMALLOC ();
! if (region->aka)
! bitmap_a_or_b (region->outer->aka, region->outer->aka, region->aka);
! bitmap_set_bit (region->outer->aka, region->region_number);
! }
if (cfun->eh->built_landing_pads)
lab = region->landing_pad;
*************** remove_eh_handler (region)
*** 2580,2586 ****
}
}
! free (region);
}
/* LABEL heads a basic block that is about to be deleted. If this
--- 2706,2712 ----
}
}
! free_region (region);
}
/* LABEL heads a basic block that is about to be deleted. If this
*************** void
*** 2591,2597 ****
maybe_remove_eh_handler (label)
rtx label;
{
! int i;
/* ??? After generating landing pads, it's not so simple to determine
if the region data is completely unused. One must examine the
--- 2717,2724 ----
maybe_remove_eh_handler (label)
rtx label;
{
! struct ehl_map_entry **slot, tmp;
! struct eh_region *region;
/* ??? After generating landing pads, it's not so simple to determine
if the region data is completely unused. One must examine the
*************** maybe_remove_eh_handler (label)
*** 2600,2626 ****
if (cfun->eh->built_landing_pads)
return;
! for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *region = cfun->eh->region_array[i];
! if (region && region->label == label)
! {
! /* Flow will want to remove MUST_NOT_THROW regions as unreachable
! because there is no path to the fallback call to terminate.
! But the region continues to affect call-site data until there
! are no more contained calls, which we don't see here. */
! if (region->type == ERT_MUST_NOT_THROW)
! {
! remove_exception_handler_label (region->label);
! region->label = NULL_RTX;
! }
! else
! remove_eh_handler (region);
! break;
! }
}
}
/* This section describes CFG exception edges for flow. */
--- 2727,2776 ----
if (cfun->eh->built_landing_pads)
return;
! tmp.label = label;
! slot = (struct ehl_map_entry **)
! htab_find_slot (exception_handler_label_map, &tmp, NO_INSERT);
! if (! slot)
! return;
! region = (*slot)->region;
! if (! region)
! return;
!
! /* Flow will want to remove MUST_NOT_THROW regions as unreachable
! because there is no path to the fallback call to terminate.
! But the region continues to affect call-site data until there
! are no more contained calls, which we don't see here. */
! if (region->type == ERT_MUST_NOT_THROW)
{
! htab_clear_slot (exception_handler_label_map, (void **) slot);
! region->label = NULL_RTX;
}
+ else
+ remove_eh_handler (region);
}
+ /* Invokes CALLBACK for every exception handler label. Only used by old
+ loop hackery; should not be used by new code. */
+
+ void
+ for_each_eh_label (callback)
+ void (*callback) PARAMS ((rtx));
+ {
+ htab_traverse (exception_handler_label_map, for_each_eh_label_1,
+ (void *)callback);
+ }
+
+ static int
+ for_each_eh_label_1 (pentry, data)
+ PTR *pentry;
+ PTR data;
+ {
+ struct ehl_map_entry *entry = *(struct ehl_map_entry **)pentry;
+ void (*callback) PARAMS ((rtx)) = (void (*) PARAMS ((rtx))) data;
+
+ (*callback) (entry->label);
+ return 1;
+ }
/* This section describes CFG exception edges for flow. */
Index: gcc/except.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/except.h,v
retrieving revision 1.61.4.1
diff -c -p -d -r1.61.4.1 except.h
*** gcc/except.h 20 Mar 2002 01:04:39 -0000 1.61.4.1
--- gcc/except.h 9 Apr 2002 20:27:12 -0000
***************
*** 1,5 ****
/* Exception Handling interface routines.
! Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001
Free Software Foundation, Inc.
Contributed by Mike Stump <mrs@cygnus.com>.
--- 1,5 ----
/* Exception Handling interface routines.
! Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002
Free Software Foundation, Inc.
Contributed by Mike Stump <mrs@cygnus.com>.
*************** extern void add_partial_entry PARAMS (
*** 96,104 ****
add_partial_entry. */
extern void end_protect_partials PARAMS ((void));
!
! /* A list of labels used for exception handlers. */
! extern rtx exception_handler_labels;
/* Determine if the given INSN can throw an exception. */
extern bool can_throw_internal PARAMS ((rtx));
--- 96,104 ----
add_partial_entry. */
extern void end_protect_partials PARAMS ((void));
! /* Invokes CALLBACK for every exception handler label. Only used by old
! loop hackery; should not be used by new code. */
! extern void for_each_eh_label PARAMS ((void (*) (rtx)));
/* Determine if the given INSN can throw an exception. */
extern bool can_throw_internal PARAMS ((rtx));
Index: gcc/jump.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/jump.c,v
retrieving revision 1.205
diff -c -p -d -r1.205 jump.c
*** gcc/jump.c 21 Feb 2002 22:47:58 -0000 1.205
--- gcc/jump.c 9 Apr 2002 20:27:12 -0000
***************
*** 1,6 ****
/* Optimize jump instructions, for GNU compiler.
Copyright (C) 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997
! 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
This file is part of GCC.
--- 1,6 ----
/* Optimize jump instructions, for GNU compiler.
Copyright (C) 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997
! 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
This file is part of GCC.
*************** rebuild_jump_labels (f)
*** 89,101 ****
count doesn't drop to zero. */
for (insn = forced_labels; insn; insn = XEXP (insn, 1))
- if (GET_CODE (XEXP (insn, 0)) == CODE_LABEL)
- LABEL_NUSES (XEXP (insn, 0))++;
-
- /* Keep track of labels used for marking handlers for exception
- regions; they cannot usually be deleted. */
-
- for (insn = exception_handler_labels; insn; insn = XEXP (insn, 1))
if (GET_CODE (XEXP (insn, 0)) == CODE_LABEL)
LABEL_NUSES (XEXP (insn, 0))++;
}
--- 89,94 ----
Index: gcc/loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.389.2.3
diff -c -p -d -r1.389.2.3 loop.c
*** gcc/loop.c 3 Apr 2002 07:53:49 -0000 1.389.2.3
--- gcc/loop.c 9 Apr 2002 20:27:12 -0000
*************** FILE *loop_dump_stream;
*** 235,240 ****
--- 235,241 ----
/* Forward declarations. */
+ static void invalidate_loops_containing_label PARAMS ((rtx));
static void find_and_verify_loops PARAMS ((rtx, struct loops *));
static void mark_loop_jump PARAMS ((rtx, struct loop *));
static void prescan_loop PARAMS ((struct loop *));
*************** prescan_loop (loop)
*** 2608,2613 ****
--- 2609,2625 ----
}
}
+ /* Invalidate all loops containing LABEL. */
+
+ static void
+ invalidate_loops_containing_label (label)
+ rtx label;
+ {
+ struct loop *loop;
+ for (loop = uid_loop[INSN_UID (label)]; loop; loop = loop->outer)
+ loop->invalid = 1;
+ }
+
/* Scan the function looking for loops. Record the start and end of each loop.
Also mark as invalid loops any loops that contain a setjmp or are branched
to from outside the loop. */
*************** find_and_verify_loops (f, loops)
*** 2694,2716 ****
/* Any loop containing a label used in an initializer must be invalidated,
because it can be jumped into from anywhere. */
-
for (label = forced_labels; label; label = XEXP (label, 1))
! {
! for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
! loop; loop = loop->outer)
! loop->invalid = 1;
! }
/* Any loop containing a label used for an exception handler must be
invalidated, because it can be jumped into from anywhere. */
!
! for (label = exception_handler_labels; label; label = XEXP (label, 1))
! {
! for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
! loop; loop = loop->outer)
! loop->invalid = 1;
! }
/* Now scan all insn's in the function. If any JUMP_INSN branches into a
loop that it is not contained within, that loop is marked invalid.
--- 2706,2717 ----
/* Any loop containing a label used in an initializer must be invalidated,
because it can be jumped into from anywhere. */
for (label = forced_labels; label; label = XEXP (label, 1))
! invalidate_loops_containing_label (XEXP (label, 0));
/* Any loop containing a label used for an exception handler must be
invalidated, because it can be jumped into from anywhere. */
! for_each_eh_label (invalidate_loops_containing_label);
/* Now scan all insn's in the function. If any JUMP_INSN branches into a
loop that it is not contained within, that loop is marked invalid.
*************** find_and_verify_loops (f, loops)
*** 2734,2744 ****
{
rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
if (note)
! {
! for (loop = uid_loop[INSN_UID (XEXP (note, 0))];
! loop; loop = loop->outer)
! loop->invalid = 1;
! }
}
if (GET_CODE (insn) != JUMP_INSN)
--- 2735,2741 ----
{
rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
if (note)
! invalidate_loops_containing_label (XEXP (note, 0));
}
if (GET_CODE (insn) != JUMP_INSN)
Index: gcc/sched-rgn.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/sched-rgn.c,v
retrieving revision 1.32.2.2
diff -c -p -d -r1.32.2.2 sched-rgn.c
*** gcc/sched-rgn.c 3 Apr 2002 17:49:49 -0000 1.32.2.2
--- gcc/sched-rgn.c 9 Apr 2002 20:27:12 -0000
*************** is_cfg_nonregular ()
*** 339,345 ****
/* If we have exception handlers, then we consider the cfg not well
structured. ?!? We should be able to handle this now that flow.c
computes an accurate cfg for EH. */
! if (exception_handler_labels)
return 1;
/* If we have non-jumping insns which refer to labels, then we consider
--- 339,345 ----
/* If we have exception handlers, then we consider the cfg not well
structured. ?!? We should be able to handle this now that flow.c
computes an accurate cfg for EH. */
! if (current_function_has_exception_handlers ())
return 1;
/* If we have non-jumping insns which refer to labels, then we consider
Index: libiberty/hashtab.c
===================================================================
RCS file: /cvs/gcc/gcc/libiberty/hashtab.c,v
retrieving revision 1.25
diff -c -p -d -r1.25 hashtab.c
*** libiberty/hashtab.c 7 Oct 2001 14:45:04 -0000 1.25
--- libiberty/hashtab.c 9 Apr 2002 20:27:12 -0000
***************
*** 1,5 ****
/* An expandable hash tables datatype.
! Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
Contributed by Vladimir Makarov (vmakarov@cygnus.com).
This file is part of the libiberty library.
--- 1,5 ----
/* An expandable hash tables datatype.
! Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
Contributed by Vladimir Makarov (vmakarov@cygnus.com).
This file is part of the libiberty library.
*************** higher_prime_number (n)
*** 81,87 ****
/* These are primes that are near, but slightly smaller than, a
power of two. */
static const unsigned long primes[] = {
- (unsigned long) 2,
(unsigned long) 7,
(unsigned long) 13,
(unsigned long) 31,
--- 81,86 ----
*************** find_empty_slot_for_expand (htab, hash)
*** 264,284 ****
hashval_t hash;
{
size_t size = htab->size;
- hashval_t hash2 = 1 + hash % (size - 2);
unsigned int index = hash % size;
for (;;)
{
! PTR *slot = htab->entries + index;
if (*slot == EMPTY_ENTRY)
return slot;
else if (*slot == DELETED_ENTRY)
abort ();
-
- index += hash2;
- if (index >= size)
- index -= size;
}
}
--- 263,289 ----
hashval_t hash;
{
size_t size = htab->size;
unsigned int index = hash % size;
+ PTR *slot = htab->entries + index;
+ hashval_t hash2;
+
+ if (*slot == EMPTY_ENTRY)
+ return slot;
+ else if (*slot == DELETED_ENTRY)
+ abort ();
+ hash2 = 1 + hash % (size - 2);
for (;;)
{
! index += hash2;
! if (index >= size)
! index -= size;
+ slot = htab->entries + index;
if (*slot == EMPTY_ENTRY)
return slot;
else if (*slot == DELETED_ENTRY)
abort ();
}
}
*************** htab_find_slot_with_hash (htab, element,
*** 405,454 ****
unsigned int index;
hashval_t hash2;
size_t size;
if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
&& htab_expand (htab) == 0)
return NULL;
size = htab->size;
- hash2 = 1 + hash % (size - 2);
index = hash % size;
htab->searches++;
first_deleted_slot = NULL;
for (;;)
{
! PTR entry = htab->entries[index];
if (entry == EMPTY_ENTRY)
! {
! if (insert == NO_INSERT)
! return NULL;
!
! htab->n_elements++;
!
! if (first_deleted_slot)
! {
! *first_deleted_slot = EMPTY_ENTRY;
! return first_deleted_slot;
! }
!
! return &htab->entries[index];
! }
!
! if (entry == DELETED_ENTRY)
{
if (!first_deleted_slot)
first_deleted_slot = &htab->entries[index];
}
! else if ((*htab->eq_f) (entry, element))
return &htab->entries[index];
-
- htab->collisions++;
- index += hash2;
- if (index >= size)
- index -= size;
}
}
/* Like htab_find_slot_with_hash, but compute the hash value from the
--- 410,468 ----
unsigned int index;
hashval_t hash2;
size_t size;
+ PTR entry;
if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
&& htab_expand (htab) == 0)
return NULL;
size = htab->size;
index = hash % size;
htab->searches++;
first_deleted_slot = NULL;
+ entry = htab->entries[index];
+ if (entry == EMPTY_ENTRY)
+ goto empty_entry;
+ else if (entry == DELETED_ENTRY)
+ first_deleted_slot = &htab->entries[index];
+ else if ((*htab->eq_f) (entry, element))
+ return &htab->entries[index];
+
+ hash2 = 1 + hash % (size - 2);
for (;;)
{
! htab->collisions++;
! index += hash2;
! if (index >= size)
! index -= size;
!
! entry = htab->entries[index];
if (entry == EMPTY_ENTRY)
! goto empty_entry;
! else if (entry == DELETED_ENTRY)
{
if (!first_deleted_slot)
first_deleted_slot = &htab->entries[index];
}
! else if ((*htab->eq_f) (entry, element))
return &htab->entries[index];
}
+
+ empty_entry:
+ if (insert == NO_INSERT)
+ return NULL;
+
+ htab->n_elements++;
+
+ if (first_deleted_slot)
+ {
+ *first_deleted_slot = EMPTY_ENTRY;
+ return first_deleted_slot;
+ }
+
+ return &htab->entries[index];
}
/* Like htab_find_slot_with_hash, but compute the hash value from the