This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Kill quadratic bottleneck in duplicate_eh_regions
- From: Jan Hubicka <jh at suse dot cz>
- To: gcc-patches at gcc dot gnu dot org, rth at redhat dot com
- Date: Sat, 11 Jun 2005 23:50:50 +0200
- Subject: Kill quadratic bottleneck in duplicate_eh_regions
Hi,
tramp3d with leafify (=a lot of inlining) triggers quadratic bottleneck in
duplicate_eh_regions where region_array is always reallocated and recomputed
from the scratch. This patch replace it by growing array and save rougly
30% of memory consumption and 15% of compilation time.
Bootstrapped/regtested i686-pc-gnu-linux, OK?
Honza
2005-06-11 Jan Hubicka <jh@suse.cz>
* except.c (struct eh_status): Turn region_array into varray.
(expand_resx_expr, collect_eh_region_array, remove_unreachable_regions,
convert_from_eh_region_ranges, find_exception_handler_labels,
current_function_has_exception_handlers, assign_filter_values,
build_post_landing_pads, dw2_build_landing_pads,
sjlj_find_directly_reachable_regions, sjlj_mark_call_sites,
sjlj_emit_dispatch_table, remove_eh_handler, for_each_eh_region,
foreach_reachable_handler, can_throw_internal_1,
convert_to_eh_region_ranges, verify_eh_tree): Update uses of
region_array.
(duplicate_eh_region_1): Update region_array.
(duplicate_eh_regions): Resize region_array and avoid recomputing.
Index: except.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/except.c,v
retrieving revision 1.308
diff -c -3 -p -r1.308 except.c
*** except.c 1 Jun 2005 12:07:40 -0000 1.308
--- except.c 11 Jun 2005 12:21:02 -0000
*************** struct eh_status GTY(())
*** 210,216 ****
struct eh_region *region_tree;
/* The same information as an indexable array. */
! struct eh_region ** GTY ((length ("%h.last_region_number"))) region_array;
/* The most recently open region. */
struct eh_region *cur_region;
--- 210,216 ----
struct eh_region *region_tree;
/* The same information as an indexable array. */
! varray_type GTY((param_is (struct eh_region))) region_array;
/* The most recently open region. */
struct eh_region *cur_region;
*************** void
*** 560,567 ****
expand_resx_expr (tree exp)
{
int region_nr = TREE_INT_CST_LOW (TREE_OPERAND (exp, 0));
! struct eh_region *reg = cfun->eh->region_array[region_nr];
reg->resume = emit_jump_insn (gen_rtx_RESX (VOIDmode, region_nr));
emit_barrier ();
}
--- 560,568 ----
expand_resx_expr (tree exp)
{
int region_nr = TREE_INT_CST_LOW (TREE_OPERAND (exp, 0));
! struct eh_region *reg = VARRAY_GENERIC_PTR (cfun->eh->region_array, region_nr);
+ gcc_assert (!reg->resume);
reg->resume = emit_jump_insn (gen_rtx_RESX (VOIDmode, region_nr));
emit_barrier ();
}
*************** get_exception_filter (struct function *f
*** 623,641 ****
void
collect_eh_region_array (void)
{
! struct eh_region **array, *i;
i = cfun->eh->region_tree;
if (! i)
return;
! array = ggc_alloc_cleared ((cfun->eh->last_region_number + 1)
! * sizeof (*array));
! cfun->eh->region_array = array;
!
while (1)
{
! array[i->region_number] = i;
/* If there are sub-regions, process them. */
if (i->inner)
--- 624,641 ----
void
collect_eh_region_array (void)
{
! struct eh_region *i;
i = cfun->eh->region_tree;
if (! i)
return;
! VARRAY_GENERIC_PTR_INIT (cfun->eh->region_array,
! cfun->eh->last_region_number + 1,
! "region array");
while (1)
{
! VARRAY_GENERIC_PTR (cfun->eh->region_array, i->region_number) = i;
/* If there are sub-regions, process them. */
if (i->inner)
*************** remove_unreachable_regions (rtx insns)
*** 671,677 ****
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! r = cfun->eh->region_array[i];
if (!r || r->region_number != i)
continue;
--- 671,677 ----
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! r = VARRAY_GENERIC_PTR (cfun->eh->region_array, i);
if (!r || r->region_number != i)
continue;
*************** remove_unreachable_regions (rtx insns)
*** 692,698 ****
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! r = cfun->eh->region_array[i];
if (r && r->region_number == i && !reachable[i])
{
bool kill_it = true;
--- 692,698 ----
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! r = VARRAY_GENERIC_PTR (cfun->eh->region_array, i);
if (r && r->region_number == i && !reachable[i])
{
bool kill_it = true;
*************** convert_from_eh_region_ranges (void)
*** 753,759 ****
we allocated earlier. */
for (i = 1; i <= n; ++i)
{
! struct eh_region *region = cfun->eh->region_array[i];
if (region && region->tree_label)
region->label = DECL_RTL_IF_SET (region->tree_label);
}
--- 753,761 ----
we allocated earlier. */
for (i = 1; i <= n; ++i)
{
! struct eh_region *region;
!
! region = VARRAY_GENERIC_PTR (cfun->eh->region_array, i);
if (region && region->tree_label)
region->label = DECL_RTL_IF_SET (region->tree_label);
}
*************** find_exception_handler_labels (void)
*** 805,813 ****
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *region = cfun->eh->region_array[i];
rtx lab;
if (! region || region->region_number != i)
continue;
if (cfun->eh->built_landing_pads)
--- 807,816 ----
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *region;
rtx lab;
+ region = VARRAY_GENERIC_PTR (cfun->eh->region_array, i);
if (! region || region->region_number != i)
continue;
if (cfun->eh->built_landing_pads)
*************** current_function_has_exception_handlers
*** 832,839 ****
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *region = cfun->eh->region_array[i];
if (! region || region->region_number != i)
continue;
if (region->type != ERT_THROW)
--- 835,843 ----
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *region;
+ region = VARRAY_GENERIC_PTR (cfun->eh->region_array, i);
if (! region || region->region_number != i)
continue;
if (region->type != ERT_THROW)
*************** duplicate_eh_region_1 (struct eh_region
*** 851,856 ****
--- 855,861 ----
*n = *o;
n->region_number = o->region_number + cfun->eh->last_region_number;
+ VARRAY_GENERIC_PTR (cfun->eh->region_array, n->region_number) = n;
gcc_assert (!o->aka);
return n;
*************** duplicate_eh_regions (struct function *i
*** 911,929 ****
return 0;
n_array = xcalloc (ifun_last_region_number + 1, sizeof (*n_array));
/* Search for the containing ERT_TRY region to fix up
the prev_try short-cuts for ERT_CLEANUP regions. */
prev_try = NULL;
if (outer_region > 0)
! for (prev_try = cfun->eh->region_array[outer_region];
prev_try && prev_try->type != ERT_TRY;
prev_try = prev_try->outer)
;
for (i = 1; i <= ifun_last_region_number; ++i)
{
! cur = ifun->eh->region_array[i];
if (!cur || cur->region_number != i)
continue;
n_array[i] = duplicate_eh_region_1 (cur);
--- 916,941 ----
return 0;
n_array = xcalloc (ifun_last_region_number + 1, sizeof (*n_array));
+ if (cfun->eh->region_array)
+ VARRAY_GROW (cfun->eh->region_array,
+ cfun->eh->last_region_number + 1 + ifun_last_region_number);
+ else
+ VARRAY_GENERIC_PTR_INIT (cfun->eh->region_array,
+ ifun_last_region_number + 1,
+ "region array");
/* Search for the containing ERT_TRY region to fix up
the prev_try short-cuts for ERT_CLEANUP regions. */
prev_try = NULL;
if (outer_region > 0)
! for (prev_try = VARRAY_GENERIC_PTR (cfun->eh->region_array, outer_region);
prev_try && prev_try->type != ERT_TRY;
prev_try = prev_try->outer)
;
for (i = 1; i <= ifun_last_region_number; ++i)
{
! cur = VARRAY_GENERIC_PTR (ifun->eh->region_array, i);
if (!cur || cur->region_number != i)
continue;
n_array[i] = duplicate_eh_region_1 (cur);
*************** duplicate_eh_regions (struct function *i
*** 937,943 ****
}
for (i = 1; i <= ifun_last_region_number; ++i)
{
! cur = ifun->eh->region_array[i];
if (!cur || cur->region_number != i)
continue;
duplicate_eh_region_2 (cur, n_array, prev_try);
--- 949,955 ----
}
for (i = 1; i <= ifun_last_region_number; ++i)
{
! cur = VARRAY_GENERIC_PTR (ifun->eh->region_array, i);
if (!cur || cur->region_number != i)
continue;
duplicate_eh_region_2 (cur, n_array, prev_try);
*************** duplicate_eh_regions (struct function *i
*** 947,953 ****
gcc_assert (root->outer == NULL);
if (outer_region > 0)
{
! struct eh_region *cur = cfun->eh->region_array[outer_region];
struct eh_region *p = cur->inner;
if (p)
--- 959,966 ----
gcc_assert (root->outer == NULL);
if (outer_region > 0)
{
! struct eh_region *cur
! = VARRAY_GENERIC_PTR (cfun->eh->region_array, outer_region);
struct eh_region *p = cur->inner;
if (p)
*************** duplicate_eh_regions (struct function *i
*** 980,987 ****
i = cfun->eh->last_region_number;
cfun->eh->last_region_number = i + ifun_last_region_number;
- collect_eh_region_array ();
-
return i;
}
--- 993,998 ----
*************** assign_filter_values (void)
*** 1161,1167 ****
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *r = cfun->eh->region_array[i];
/* Mind we don't process a region more than once. */
if (!r || r->region_number != i)
--- 1172,1180 ----
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *r;
!
! r = VARRAY_GENERIC_PTR (cfun->eh->region_array, i);
/* Mind we don't process a region more than once. */
if (!r || r->region_number != i)
*************** build_post_landing_pads (void)
*** 1254,1262 ****
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *region = cfun->eh->region_array[i];
rtx seq;
/* Mind we don't process a region more than once. */
if (!region || region->region_number != i)
continue;
--- 1267,1276 ----
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *region;
rtx seq;
+ region = VARRAY_GENERIC_PTR (cfun->eh->region_array, i);
/* Mind we don't process a region more than once. */
if (!region || region->region_number != i)
continue;
*************** connect_post_landing_pads (void)
*** 1373,1383 ****
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *region = cfun->eh->region_array[i];
struct eh_region *outer;
rtx seq;
rtx barrier;
/* Mind we don't process a region more than once. */
if (!region || region->region_number != i)
continue;
--- 1387,1398 ----
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *region;
struct eh_region *outer;
rtx seq;
rtx barrier;
+ region = VARRAY_GENERIC_PTR (cfun->eh->region_array, i);
/* Mind we don't process a region more than once. */
if (!region || region->region_number != i)
continue;
*************** dw2_build_landing_pads (void)
*** 1450,1461 ****
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *region = cfun->eh->region_array[i];
rtx seq;
basic_block bb;
bool clobbers_hard_regs = false;
edge e;
/* Mind we don't process a region more than once. */
if (!region || region->region_number != i)
continue;
--- 1465,1477 ----
for (i = cfun->eh->last_region_number; i > 0; --i)
{
! struct eh_region *region;
rtx seq;
basic_block bb;
bool clobbers_hard_regs = false;
edge e;
+ region = VARRAY_GENERIC_PTR (cfun->eh->region_array, i);
/* Mind we don't process a region more than once. */
if (!region || region->region_number != i)
continue;
*************** sjlj_find_directly_reachable_regions (st
*** 1551,1557 ****
if (!note || INTVAL (XEXP (note, 0)) <= 0)
continue;
! region = cfun->eh->region_array[INTVAL (XEXP (note, 0))];
type_thrown = NULL_TREE;
if (region->type == ERT_THROW)
--- 1567,1573 ----
if (!note || INTVAL (XEXP (note, 0)) <= 0)
continue;
! region = VARRAY_GENERIC_PTR (cfun->eh->region_array, INTVAL (XEXP (note, 0)));
type_thrown = NULL_TREE;
if (region->type == ERT_THROW)
*************** sjlj_assign_call_site_values (rtx dispat
*** 1593,1599 ****
for (i = cfun->eh->last_region_number; i > 0; --i)
if (lp_info[i].directly_reachable)
{
! struct eh_region *r = cfun->eh->region_array[i];
r->landing_pad = dispatch_label;
lp_info[i].action_index = collect_one_action_chain (ar_hash, r);
if (lp_info[i].action_index != -1)
--- 1609,1616 ----
for (i = cfun->eh->last_region_number; i > 0; --i)
if (lp_info[i].directly_reachable)
{
! struct eh_region *r = VARRAY_GENERIC_PTR (cfun->eh->region_array, i);
!
r->landing_pad = dispatch_label;
lp_info[i].action_index = collect_one_action_chain (ar_hash, r);
if (lp_info[i].action_index != -1)
*************** sjlj_mark_call_sites (struct sjlj_lp_inf
*** 1679,1685 ****
if (INTVAL (XEXP (note, 0)) <= 0)
continue;
! region = cfun->eh->region_array[INTVAL (XEXP (note, 0))];
this_call_site = lp_info[region->region_number].call_site_index;
}
--- 1696,1702 ----
if (INTVAL (XEXP (note, 0)) <= 0)
continue;
! region = VARRAY_GENERIC_PTR (cfun->eh->region_array, INTVAL (XEXP (note, 0)));
this_call_site = lp_info[region->region_number].call_site_index;
}
*************** sjlj_emit_dispatch_table (rtx dispatch_l
*** 1894,1906 ****
emit_cmp_and_jump_insns (dispatch, GEN_INT (lp_info[i].dispatch_index),
EQ, NULL_RTX, TYPE_MODE (integer_type_node), 0,
! cfun->eh->region_array[i]->post_landing_pad);
}
seq = get_insns ();
end_sequence ();
! before = cfun->eh->region_array[first_reachable]->post_landing_pad;
bb = emit_to_new_bb_before (seq, before);
e = make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
--- 1911,1925 ----
emit_cmp_and_jump_insns (dispatch, GEN_INT (lp_info[i].dispatch_index),
EQ, NULL_RTX, TYPE_MODE (integer_type_node), 0,
! ((struct eh_region *)VARRAY_GENERIC_PTR (cfun->eh->region_array, i))
! ->post_landing_pad);
}
seq = get_insns ();
end_sequence ();
! before = (((struct eh_region *)VARRAY_GENERIC_PTR (cfun->eh->region_array, first_reachable))
! ->post_landing_pad);
bb = emit_to_new_bb_before (seq, before);
e = make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
*************** remove_eh_handler (struct eh_region *reg
*** 2052,2058 ****
list of alternate numbers by which we are known. */
outer = region->outer;
! cfun->eh->region_array[region->region_number] = outer;
if (region->aka)
{
unsigned i;
--- 2071,2077 ----
list of alternate numbers by which we are known. */
outer = region->outer;
! VARRAY_GENERIC_PTR (cfun->eh->region_array, region->region_number) = outer;
if (region->aka)
{
unsigned i;
*************** remove_eh_handler (struct eh_region *reg
*** 2060,2066 ****
EXECUTE_IF_SET_IN_BITMAP (region->aka, 0, i, bi)
{
! cfun->eh->region_array[i] = outer;
}
}
--- 2079,2085 ----
EXECUTE_IF_SET_IN_BITMAP (region->aka, 0, i, bi)
{
! VARRAY_GENERIC_PTR (cfun->eh->region_array, i) = outer;
}
}
*************** for_each_eh_region (void (*callback) (st
*** 2194,2200 ****
int i, n = cfun->eh->last_region_number;
for (i = 1; i <= n; ++i)
{
! struct eh_region *region = cfun->eh->region_array[i];
if (region)
(*callback) (region);
}
--- 2213,2221 ----
int i, n = cfun->eh->last_region_number;
for (i = 1; i <= n; ++i)
{
! struct eh_region *region;
!
! region = VARRAY_GENERIC_PTR (cfun->eh->region_array, i);
if (region)
(*callback) (region);
}
*************** foreach_reachable_handler (int region_nu
*** 2444,2450 ****
info.callback = callback;
info.callback_data = callback_data;
! region = cfun->eh->region_array[region_number];
type_thrown = NULL_TREE;
if (is_resx)
--- 2465,2471 ----
info.callback = callback;
info.callback_data = callback_data;
! region = VARRAY_GENERIC_PTR (cfun->eh->region_array, region_number);
type_thrown = NULL_TREE;
if (is_resx)
*************** can_throw_internal_1 (int region_number,
*** 2533,2539 ****
struct eh_region *region;
tree type_thrown;
! region = cfun->eh->region_array[region_number];
type_thrown = NULL_TREE;
if (is_resx)
--- 2554,2560 ----
struct eh_region *region;
tree type_thrown;
! region = VARRAY_GENERIC_PTR (cfun->eh->region_array, region_number);
type_thrown = NULL_TREE;
if (is_resx)
*************** can_throw_external_1 (int region_number,
*** 2593,2599 ****
struct eh_region *region;
tree type_thrown;
! region = cfun->eh->region_array[region_number];
type_thrown = NULL_TREE;
if (is_resx)
--- 2614,2620 ----
struct eh_region *region;
tree type_thrown;
! region = VARRAY_GENERIC_PTR (cfun->eh->region_array, region_number);
type_thrown = NULL_TREE;
if (is_resx)
*************** convert_to_eh_region_ranges (void)
*** 3124,3130 ****
{
if (INTVAL (XEXP (note, 0)) <= 0)
continue;
! region = cfun->eh->region_array[INTVAL (XEXP (note, 0))];
this_action = collect_one_action_chain (ar_hash, region);
}
--- 3145,3151 ----
{
if (INTVAL (XEXP (note, 0)) <= 0)
continue;
! region = VARRAY_GENERIC_PTR (cfun->eh->region_array, INTVAL (XEXP (note, 0)));
this_action = collect_one_action_chain (ar_hash, region);
}
*************** verify_eh_tree (struct function *fun)
*** 3656,3665 ****
if (! i)
return;
for (j = fun->eh->last_region_number; j > 0; --j)
! if (fun->eh->region_array[j])
{
count++;
! if (fun->eh->region_array[j]->region_number != j)
{
error ("region_array is corrupted for region %i", i->region_number);
err = true;
--- 3677,3686 ----
if (! i)
return;
for (j = fun->eh->last_region_number; j > 0; --j)
! if ((i = VARRAY_GENERIC_PTR (cfun->eh->region_array, j)))
{
count++;
! if (i->region_number != j)
{
error ("region_array is corrupted for region %i", i->region_number);
err = true;
*************** verify_eh_tree (struct function *fun)
*** 3668,3674 ****
while (1)
{
! if (fun->eh->region_array[i->region_number] != i)
{
error ("region_array is corrupted for region %i", i->region_number);
err = true;
--- 3689,3695 ----
while (1)
{
! if (VARRAY_GENERIC_PTR (cfun->eh->region_array, i->region_number) != i)
{
error ("region_array is corrupted for region %i", i->region_number);
err = true;