This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Lazily allocate varrays
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 25 Nov 2003 20:20:26 -0700
- Subject: [tree-ssa] Lazily allocate varrays
- Reply-to: law at redhat dot com
The dominator optimizer creates lots of virtual arrays; however, not all
of them are needed for each and every block.
This patch lazily allocates those virtual arrays resulting in another
4-5M of memory savings and a small speedup for Gerald's testcase. It
is also a small speedup across a larger range of tests.
I changed one aspect of the dominator walker interface, specifically
the dominator walker will indicate to the block local data initialization
routine whether or not the block local data is new or recycled. This is
much nicer than having to guess by looking at the contents of the
underlying datastructure to see if it had already been used/initialized.
I made a similar change to the rewriter. The gains there are smaller
simply because it needs fewer varrays (~200k) But it was a trivial change to
make and well, there's no sense in wasting memory for no good reason.
Bootstrapped and regression tested.
* domwalk.c (walk_dominator_tree): Indicate to the block local
data initializer if the block local data is new or recycled.
* domwalk.h (struct dom_walk_data): Corresponding changes.
* tree-ssa-dom.c (dom_opt_initialize_block_local_data): Accept and use
"recycled" argument. For recycled structures, only clear varrays
that have been initialized. For new blocks, do not initialize
varrays here.
(dom_opt_finalize_block): When threading across edges, if the
true/false varrays have not been initialized, then the limit is zero.
Only clear block local varrays that have been initialized.
(record_equivalences_from_incoming_edge): If necessary, initialize
block local const_and_copies.
(dom_opt_walk_stmts): If necessary, initialize block local
stmts_to_rescan.
(record_var_is_nonzero): If necessary, initialize block local
nonzero_vars.
(record_cond_is_true): If necessary, initialize block local
true_exprs.
(record_cond_is_false): If necessary, initialize block local
false_exprs.
(lookup_avail_expr): If necessary, initialize block local
avail_exprs.
(record_range): If necessary, initialize block local vrp_varaibles.
* tree-ssa.c
* tree-ssa.c (rewrite_initialize_block_local_data): Accept and use
"recycled" argument. For recycled structures, only clear varrays
that have been initialized. For new blocks, do not initialize
varrays here.
(rewrite_finalize_block): Only clear block local varrays that have
been initialized.
(register_new_def): If necessary, initialize block local defs.
Index: domwalk.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/domwalk.c,v
retrieving revision 1.1.2.4
diff -c -3 -p -r1.1.2.4 domwalk.c
*** domwalk.c 22 Nov 2003 04:13:49 -0000 1.1.2.4
--- domwalk.c 26 Nov 2003 03:17:44 -0000
*************** walk_dominator_tree (struct dom_walk_dat
*** 66,88 ****
/* Callback to initialize the local data structure. */
if (walk_data->initialize_block_local_data)
{
/* First get some local data, reusing any local data pointer we may
have saved. */
if (VARRAY_ACTIVE_SIZE (walk_data->free_block_data) > 0)
{
bd = VARRAY_TOP_GENERIC_PTR (walk_data->free_block_data);
VARRAY_POP (walk_data->free_block_data);
}
else
{
bd = xcalloc (1, walk_data->block_local_data_size);
}
/* Push the local data into the local data stack. */
VARRAY_PUSH_GENERIC_PTR (walk_data->block_data_stack, bd);
/* Call the initializer. */
! walk_data->initialize_block_local_data (walk_data, bb, last);
}
--- 66,92 ----
/* Callback to initialize the local data structure. */
if (walk_data->initialize_block_local_data)
{
+ bool recycled;
+
/* First get some local data, reusing any local data pointer we may
have saved. */
if (VARRAY_ACTIVE_SIZE (walk_data->free_block_data) > 0)
{
bd = VARRAY_TOP_GENERIC_PTR (walk_data->free_block_data);
VARRAY_POP (walk_data->free_block_data);
+ recycled = 1;
}
else
{
bd = xcalloc (1, walk_data->block_local_data_size);
+ recycled = 0;
}
/* Push the local data into the local data stack. */
VARRAY_PUSH_GENERIC_PTR (walk_data->block_data_stack, bd);
/* Call the initializer. */
! walk_data->initialize_block_local_data (walk_data, bb, recycled);
}
Index: domwalk.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/domwalk.h,v
retrieving revision 1.1.2.3
diff -c -3 -p -r1.1.2.3 domwalk.h
*** domwalk.h 22 Nov 2003 04:13:49 -0000 1.1.2.3
--- domwalk.h 26 Nov 2003 03:17:44 -0000
*************** struct dom_walk_data
*** 35,41 ****
that allows your optimizer to re-use those arrays rather than
creating new ones. */
void (*initialize_block_local_data) (struct dom_walk_data *,
! basic_block, tree);
/* Function to call before the statement walk occurring before the
recursive walk of the dominator children.
--- 35,41 ----
that allows your optimizer to re-use those arrays rather than
creating new ones. */
void (*initialize_block_local_data) (struct dom_walk_data *,
! basic_block, bool);
/* Function to call before the statement walk occurring before the
recursive walk of the dominator children.
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.87
diff -c -3 -p -r1.1.2.87 tree-ssa-dom.c
*** tree-ssa-dom.c 25 Nov 2003 21:25:20 -0000 1.1.2.87
--- tree-ssa-dom.c 26 Nov 2003 03:17:56 -0000
*************** static void record_equivalences_from_stm
*** 232,238 ****
static void thread_across_edge (edge);
static void dom_opt_finalize_block (struct dom_walk_data *, basic_block,
tree);
static void dom_opt_initialize_block_local_data (struct dom_walk_data *,
! basic_block, tree);
static void dom_opt_initialize_block (struct dom_walk_data *,
basic_block, tree);
static void dom_opt_walk_stmts (struct dom_walk_data *, basic_block, tree);
--- 232,238 ----
static void thread_across_edge (edge);
static void dom_opt_finalize_block (struct dom_walk_data *, basic_block,
tree);
static void dom_opt_initialize_block_local_data (struct dom_walk_data *,
! basic_block, bool);
static void dom_opt_initialize_block (struct dom_walk_data *,
basic_block, tree);
static void dom_opt_walk_stmts (struct dom_walk_data *, basic_block, tree);
*************** thread_across_edge (edge e)
*** 635,641 ****
static void
dom_opt_initialize_block_local_data (struct dom_walk_data *walk_data,
basic_block bb ATTRIBUTE_UNUSED,
! tree parent_block_last_stmt ATTRIBUTE_UNUSED)
{
struct dom_walk_block_data *bd
= (struct dom_walk_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->
block_data_stack);
--- 635,641 ----
static void
dom_opt_initialize_block_local_data (struct dom_walk_data *walk_data,
basic_block bb ATTRIBUTE_UNUSED,
! bool recycled)
{
struct dom_walk_block_data *bd
= (struct dom_walk_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->
block_data_stack);
*************** dom_opt_initialize_block_local_data (str
*** 644,670 ****
cleared, then we are re-using a previously allocated entry. In
that case, we can also re-use the underlying virtual arrays. Just
make sure we clear them before using them! */
! if (bd->avail_exprs)
{
! VARRAY_CLEAR (bd->avail_exprs);
! VARRAY_CLEAR (bd->true_exprs);
! VARRAY_CLEAR (bd->false_exprs);
! VARRAY_CLEAR (bd->const_and_copies);
! VARRAY_CLEAR (bd->nonzero_vars);
! VARRAY_CLEAR (bd->stmts_to_rescan);
! VARRAY_CLEAR (bd->vrp_variables);
! }
! else
! {
! /* The allocator gave us a new block data structure, so we must
! initialize new arrays. */
! VARRAY_TREE_INIT (bd->avail_exprs, 20, "block_avail_exprs");
! VARRAY_TREE_INIT (bd->true_exprs, 2, "block_true_exprs");
! VARRAY_TREE_INIT (bd->false_exprs, 2, "block_false_exprs");
! VARRAY_TREE_INIT (bd->const_and_copies, 2, "block_const_and_copies");
! VARRAY_TREE_INIT (bd->nonzero_vars, 2, "block_nonzero_vars");
! VARRAY_TREE_INIT (bd->stmts_to_rescan, 20, "stmts_to_rescan");
! VARRAY_TREE_INIT (bd->vrp_variables, 2, "vrp_variables");
}
}
--- 644,665 ----
cleared, then we are re-using a previously allocated entry. In
that case, we can also re-use the underlying virtual arrays. Just
make sure we clear them before using them! */
! if (recycled)
{
! if (bd->avail_exprs)
! VARRAY_CLEAR (bd->avail_exprs);
! if (bd->true_exprs)
! VARRAY_CLEAR (bd->true_exprs);
! if (bd->false_exprs)
! VARRAY_CLEAR (bd->false_exprs);
! if (bd->const_and_copies)
! VARRAY_CLEAR (bd->const_and_copies);
! if (bd->nonzero_vars)
! VARRAY_CLEAR (bd->nonzero_vars);
! if (bd->stmts_to_rescan)
! VARRAY_CLEAR (bd->stmts_to_rescan);
! if (bd->vrp_variables)
! VARRAY_CLEAR (bd->vrp_variables);
}
}
*************** dom_opt_finalize_block (struct dom_walk_
*** 751,758 ****
if (! dom_children (bb)
|| ! bitmap_bit_p (dom_children (bb), true_edge->dest->index))
{
! unsigned true_limit = VARRAY_ACTIVE_SIZE (bd->true_exprs);
! unsigned false_limit = VARRAY_ACTIVE_SIZE (bd->true_exprs);
record_cond_is_true (cond, &bd->true_exprs);
record_cond_is_false (inverted, &bd->false_exprs);
thread_across_edge (true_edge);
--- 746,759 ----
if (! dom_children (bb)
|| ! bitmap_bit_p (dom_children (bb), true_edge->dest->index))
{
! unsigned true_limit;
! unsigned false_limit;
!
! true_limit
! = bd->true_exprs ? VARRAY_ACTIVE_SIZE (bd->true_exprs) : 0;
! false_limit
! = bd->false_exprs ? VARRAY_ACTIVE_SIZE (bd->false_exprs) : 0;
!
record_cond_is_true (cond, &bd->true_exprs);
record_cond_is_false (inverted, &bd->false_exprs);
thread_across_edge (true_edge);
*************** dom_opt_finalize_block (struct dom_walk_
*** 772,779 ****
if (! dom_children (bb)
|| ! bitmap_bit_p (dom_children (bb), false_edge->dest->index))
{
! unsigned true_limit = VARRAY_ACTIVE_SIZE (bd->true_exprs);
! unsigned false_limit = VARRAY_ACTIVE_SIZE (bd->false_exprs);
record_cond_is_false (cond, &bd->false_exprs);
record_cond_is_true (inverted, &bd->true_exprs);
thread_across_edge (false_edge);
--- 773,786 ----
if (! dom_children (bb)
|| ! bitmap_bit_p (dom_children (bb), false_edge->dest->index))
{
! unsigned true_limit;
! unsigned false_limit;
!
! true_limit
! = bd->true_exprs ? VARRAY_ACTIVE_SIZE (bd->true_exprs) : 0;
! false_limit
! = bd->false_exprs ? VARRAY_ACTIVE_SIZE (bd->false_exprs) : 0;
!
record_cond_is_false (cond, &bd->false_exprs);
record_cond_is_true (inverted, &bd->true_exprs);
thread_across_edge (false_edge);
*************** dom_opt_finalize_block (struct dom_walk_
*** 791,811 ****
}
/* Remove all the expressions made available in this block. */
! while (VARRAY_ACTIVE_SIZE (block_true_exprs) > 0)
{
tree cond = VARRAY_TOP_TREE (block_true_exprs);
VARRAY_POP (block_true_exprs);
htab_remove_elt (true_exprs, cond);
}
! while (VARRAY_ACTIVE_SIZE (block_false_exprs) > 0)
{
tree cond = VARRAY_TOP_TREE (block_false_exprs);
VARRAY_POP (block_false_exprs);
htab_remove_elt (false_exprs, cond);
}
! while (VARRAY_ACTIVE_SIZE (block_avail_exprs) > 0)
{
tree stmt = VARRAY_TOP_TREE (block_avail_exprs);
VARRAY_POP (block_avail_exprs);
--- 798,818 ----
}
/* Remove all the expressions made available in this block. */
! while (block_true_exprs && VARRAY_ACTIVE_SIZE (block_true_exprs) > 0)
{
tree cond = VARRAY_TOP_TREE (block_true_exprs);
VARRAY_POP (block_true_exprs);
htab_remove_elt (true_exprs, cond);
}
! while (block_false_exprs && VARRAY_ACTIVE_SIZE (block_false_exprs) > 0)
{
tree cond = VARRAY_TOP_TREE (block_false_exprs);
VARRAY_POP (block_false_exprs);
htab_remove_elt (false_exprs, cond);
}
! while (block_avail_exprs && VARRAY_ACTIVE_SIZE (block_avail_exprs) > 0)
{
tree stmt = VARRAY_TOP_TREE (block_avail_exprs);
VARRAY_POP (block_avail_exprs);
*************** dom_opt_finalize_block (struct dom_walk_
*** 813,819 ****
}
/* Also remove equivalences created by EQ_EXPR_VALUE. */
! while (VARRAY_ACTIVE_SIZE (block_const_and_copies) > 0)
{
tree prev_value, dest;
--- 820,827 ----
}
/* Also remove equivalences created by EQ_EXPR_VALUE. */
! while (block_const_and_copies
! && VARRAY_ACTIVE_SIZE (block_const_and_copies) > 0)
{
tree prev_value, dest;
*************** dom_opt_finalize_block (struct dom_walk_
*** 826,832 ****
}
/* Also remove block local expressions which created nonzero values. */
! while (VARRAY_ACTIVE_SIZE (block_nonzero_vars) > 0)
{
tree prev_value, dest;
--- 834,840 ----
}
/* Also remove block local expressions which created nonzero values. */
! while (block_nonzero_vars && VARRAY_ACTIVE_SIZE (block_nonzero_vars) > 0)
{
tree prev_value, dest;
*************** dom_opt_finalize_block (struct dom_walk_
*** 844,850 ****
To be efficient, we note which variables have had their values
constrained in this block. So walk over each variable in the
VRP_VARIABLEs array. */
! while (VARRAY_ACTIVE_SIZE (vrp_variables) > 0)
{
tree var = VARRAY_TOP_TREE (vrp_variables);
--- 852,858 ----
To be efficient, we note which variables have had their values
constrained in this block. So walk over each variable in the
VRP_VARIABLEs array. */
! while (vrp_variables && VARRAY_ACTIVE_SIZE (vrp_variables) > 0)
{
tree var = VARRAY_TOP_TREE (vrp_variables);
*************** dom_opt_finalize_block (struct dom_walk_
*** 872,878 ****
/* Re-scan operands in all statements that may have had new symbols
exposed. */
! while (VARRAY_ACTIVE_SIZE (stmts_to_rescan) > 0)
{
tree stmt = VARRAY_TOP_TREE (stmts_to_rescan);
VARRAY_POP (stmts_to_rescan);
--- 880,886 ----
/* Re-scan operands in all statements that may have had new symbols
exposed. */
! while (stmts_to_rescan && VARRAY_ACTIVE_SIZE (stmts_to_rescan) > 0)
{
tree stmt = VARRAY_TOP_TREE (stmts_to_rescan);
VARRAY_POP (stmts_to_rescan);
*************** record_equivalences_from_incoming_edge (
*** 1047,1052 ****
--- 1055,1062 ----
/* Record the destination and its previous value so that we can
reset them as we leave this block. */
+ if (! bd->const_and_copies)
+ VARRAY_TREE_INIT (bd->const_and_copies, 2, "block_const_and_copies");
VARRAY_PUSH_TREE (bd->const_and_copies, dest);
VARRAY_PUSH_TREE (bd->const_and_copies, prev_value);
}
*************** dom_opt_walk_stmts (struct dom_walk_data
*** 1101,1107 ****
if (optimize_stmt (si,
&bd->avail_exprs,
&bd->nonzero_vars))
! VARRAY_PUSH_TREE (bd->stmts_to_rescan, bsi_stmt (si));
}
}
--- 1111,1121 ----
if (optimize_stmt (si,
&bd->avail_exprs,
&bd->nonzero_vars))
! {
! if (! bd->stmts_to_rescan)
! VARRAY_TREE_INIT (bd->stmts_to_rescan, 20, "stmts_to_rescan");
! VARRAY_PUSH_TREE (bd->stmts_to_rescan, bsi_stmt (si));
! }
}
}
*************** record_var_is_nonzero (tree var, varray_
*** 1260,1265 ****
--- 1274,1281 ----
/* Record the destination and its previous value so that we can
reset them as we leave this block. */
+ if (! *block_nonzero_vars_p)
+ VARRAY_TREE_INIT (*block_nonzero_vars_p, 2, "block_nonzero_vars");
VARRAY_PUSH_TREE (*block_nonzero_vars_p, var);
VARRAY_PUSH_TREE (*block_nonzero_vars_p, prev_value);
}
*************** record_cond_is_true (tree cond, varray_t
*** 1277,1282 ****
--- 1293,1300 ----
if (*slot == NULL)
{
*slot = (void *) cond;
+ if (! *block_true_exprs_p)
+ VARRAY_TREE_INIT (*block_true_exprs_p, 2, "block_true_exprs");
VARRAY_PUSH_TREE (*block_true_exprs_p, cond);
}
}
*************** record_cond_is_false (tree cond, varray_
*** 1293,1298 ****
--- 1311,1318 ----
if (*slot == NULL)
{
*slot = (void *) cond;
+ if (! *block_false_exprs_p)
+ VARRAY_TREE_INIT (*block_false_exprs_p, 2, "block_false_exprs");
VARRAY_PUSH_TREE (*block_false_exprs_p, cond);
}
}
*************** lookup_avail_expr (tree stmt, varray_typ
*** 2412,2417 ****
--- 2432,2439 ----
if (*slot == NULL)
{
*slot = (void *) stmt;
+ if (! *block_avail_exprs_p)
+ VARRAY_TREE_INIT (*block_avail_exprs_p, 20, "block_avail_exprs");
VARRAY_PUSH_TREE (*block_avail_exprs_p, stmt);
return NULL_TREE;
}
*************** record_range (tree cond, basic_block bb,
*** 2529,2534 ****
--- 2551,2558 ----
}
VARRAY_PUSH_GENERIC_PTR (*vrp_records_p, element);
+ if (! *vrp_variables_p)
+ VARRAY_TREE_INIT (*vrp_variables_p, 2, "vrp_variables");
VARRAY_PUSH_TREE (*vrp_variables_p, TREE_OPERAND (cond, 0));
}
}
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.164
diff -c -3 -p -r1.1.4.164 tree-ssa.c
*** tree-ssa.c 25 Nov 2003 18:26:15 -0000 1.1.4.164
--- tree-ssa.c 26 Nov 2003 03:18:03 -0000
*************** static sbitmap vars_to_rename;
*** 173,179 ****
/* Local functions. */
static void rewrite_finalize_block (struct dom_walk_data *, basic_block,
tree);
static void rewrite_initialize_block_local_data (struct dom_walk_data *,
! basic_block, tree);
static void rewrite_initialize_block (struct dom_walk_data *,
basic_block, tree);
static void rewrite_walk_stmts (struct dom_walk_data *, basic_block, tree);
--- 173,179 ----
/* Local functions. */
static void rewrite_finalize_block (struct dom_walk_data *, basic_block,
tree);
static void rewrite_initialize_block_local_data (struct dom_walk_data *,
! basic_block, bool);
static void rewrite_initialize_block (struct dom_walk_data *,
basic_block, tree);
static void rewrite_walk_stmts (struct dom_walk_data *, basic_block, tree);
*************** insert_phi_nodes (bitmap *dfs)
*** 832,838 ****
static void
rewrite_initialize_block_local_data (struct dom_walk_data *walk_data,
basic_block bb ATTRIBUTE_UNUSED,
! tree parent_block_last_stmt ATTRIBUTE_UNUSED)
{
struct rewrite_block_data *bd
= (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->
block_data_stack);
--- 832,838 ----
static void
rewrite_initialize_block_local_data (struct dom_walk_data *walk_data,
basic_block bb ATTRIBUTE_UNUSED,
! bool recycled)
{
struct rewrite_block_data *bd
= (struct rewrite_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->
block_data_stack);
*************** rewrite_initialize_block_local_data (str
*** 841,850 ****
not cleared, then we are re-using a previously allocated entry. In
that case, we can also re-use the underlying virtal arrays. Just
make sure we clear them before using them! */
! if (bd->block_defs)
VARRAY_CLEAR (bd->block_defs);
- else
- VARRAY_TREE_INIT (bd->block_defs, 20, "block_defs");
}
/* SSA Rewriting Step 1. Initialization, create a block local stack
--- 841,848 ----
not cleared, then we are re-using a previously allocated entry. In
that case, we can also re-use the underlying virtal arrays. Just
make sure we clear them before using them! */
! if (recycled && bd->block_defs)
VARRAY_CLEAR (bd->block_defs);
}
/* SSA Rewriting Step 1. Initialization, create a block local stack
*************** rewrite_finalize_block (struct dom_walk_
*** 938,944 ****
/* Step 5. Restore the current reaching definition for each variable
referenced in the block (in reverse order). */
! while (VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
{
tree var;
tree saved_def = VARRAY_TOP_TREE (bd->block_defs);
--- 936,942 ----
/* Step 5. Restore the current reaching definition for each variable
referenced in the block (in reverse order). */
! while (bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
{
tree var;
tree saved_def = VARRAY_TOP_TREE (bd->block_defs);
*************** static void
*** 2934,2939 ****
--- 2932,2940 ----
register_new_def (tree var, tree def, varray_type *block_defs_p)
{
tree currdef = get_value_for (var, currdefs);
+
+ if (! *block_defs_p)
+ VARRAY_TREE_INIT (*block_defs_p, 20, "block_defs");
/* If the current reaching definition is NULL, push the variable itself
so that the dominator tree callbacks know what variable is associated