[tree-ssa] More into-ssa and dominator optimizer memory reductions
law@redhat.com
law@redhat.com
Wed Apr 21 18:01:00 GMT 2004
Both the into-ssa and dominator optimizer passes need to keep track of what
SSA_NAME is the current reaching definition for each _DECL.
Right now each allocates a varray indexed by _DECL uids and stores the
appropriate information into those varrays.
This means that every time we call the dominator optimizer and every
time we call the into-ssa code we allocate this relatively large varray.
[ In fact, we allocate more memory for the currdefs varrays than any other
varray! ]
Worse yet, the dominator optimizer itself calls the into-ssa code, so we
can actually have two instances of this varray at the same time which
increases peak memory usage.
Long term I want to see the the dominator optimizer inheriting structures
and data from the into-ssa pass (at which point they could share the varray
in their main dominator walker structures).
Until then, this is a medium term solution. Basically we move the one tidbit
of information into _DECL's annotation. This makes annotations one word
larger,
but we reduce the number of these large varrays we allocate and manage.
The net result is another 6M reduction in the amount of GC allocated
memory for Gerald's testcase and another tiny speedup.
Bootstrapped and regression tested on i686-pc-linux-gnu.
* tree-flow.h (var_ann_d): Add "current_def" field.
(register_new_def): Lose last argument (currdefs table).
* tree-into-ssa.c (currdefs): Remove.
(rewrite_into_ssa): Initialize current_def field on each variable's
annotation. Remove initialization/clearing of currdefs.
(set_value_for, get_value_for): Kill.
(rewrite_initialize_block): Update call to register_new_def.
(rewrite_stmt): Similarly.
(rewrite_finalize_block): Get/set a _DECL node's current
definition from its annotation.
(get_reaching_def): Similarly.
(register_new_def): Similarly. Lose last argument.
* tree-ssa-dom.c (currdefs): Remove.
(get_value_for, set_value_for): Simplify.
(tree_ssa_dominator_optimize): Initialize current_def on each
variable's annotation. Remove initialization/clearing of currdefs.
(thread_across_edge): Lose unnecessary argument to register_new_def.
(record_equivalences_from_phis): Likewise.
(register_definitions_for_stmt): Likewise.
(restore_currdefs_to_original_value): Get/set a _DECL node's current
definition from its annotation. Lose unnecessary "table" argument.
(dom_opt_finalize_block): Corresponding changes.
Index: gcc/tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.200
diff -c -p -r1.1.4.200 tree-flow.h
*** gcc/tree-flow.h 6 Apr 2004 22:14:49 -0000 1.1.4.200
--- gcc/tree-flow.h 21 Apr 2004 17:38:28 -0000
*************** struct var_ann_d GTY(())
*** 154,159 ****
--- 154,169 ----
USE or a VUSE. In those cases, the SSA renamer creates an SSA name
for this variable with an empty defining statement. */
tree default_def;
+
+ /* During into-ssa and the dominator optimizer, this field holds the
+ current version of this variable (an SSA_NAME).
+
+ This was previously two varrays (one in into-ssa the other in the
+ dominator optimizer). That is wasteful, particularly since the
+ dominator optimizer calls into-ssa resulting in having two varrays
+ live at the same time and this can happen for each call to the
+ dominator optimizer. */
+ tree current_def;
};
*************** extern bool tree_ssa_useless_type_conver
*** 541,547 ****
extern bool tree_ssa_useless_type_conversion_1 (tree, tree);
extern void verify_ssa (void);
extern void delete_tree_ssa (void);
! extern void register_new_def (tree, varray_type *, varray_type);
extern void walk_use_def_chains (tree, walk_use_def_chains_fn, void *);
/* In tree-into-ssa.c */
--- 551,557 ----
extern bool tree_ssa_useless_type_conversion_1 (tree, tree);
extern void verify_ssa (void);
extern void delete_tree_ssa (void);
! extern void register_new_def (tree, varray_type *);
extern void walk_use_def_chains (tree, walk_use_def_chains_fn, void *);
/* In tree-into-ssa.c */
Index: gcc/tree-into-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-into-ssa.c,v
retrieving revision 1.1.2.6
diff -c -p -r1.1.2.6 tree-into-ssa.c
*** gcc/tree-into-ssa.c 20 Apr 2004 19:27:41 -0000 1.1.2.6
--- gcc/tree-into-ssa.c 21 Apr 2004 17:38:29 -0000
*************** struct mark_def_sites_global_data
*** 90,100 ****
sbitmap kills;
};
- /* Table to store the current reaching definition for every variable in
- the function. Given a variable V, its entry will be its immediately
- reaching SSA_NAME node. */
- static varray_type currdefs;
-
struct rewrite_block_data
{
varray_type block_defs;
--- 90,95 ----
*************** static void rewrite_stmt (struct dom_wal
*** 121,128 ****
static inline void rewrite_operand (tree *);
static void insert_phi_nodes_for (tree, bitmap *, varray_type *);
static tree get_reaching_def (tree);
- static tree get_value_for (tree, varray_type);
- static void set_value_for (tree, tree, varray_type);
static hashval_t def_blocks_hash (const void *);
static int def_blocks_eq (const void *, const void *);
static void def_blocks_free (void *);
--- 116,121 ----
*************** static inline struct def_blocks_d *get_d
*** 131,154 ****
static inline struct def_blocks_d *find_def_blocks_for (tree);
static void htab_statistics (FILE *, htab_t);
- /* Return the value associated with variable VAR in TABLE. */
-
- static inline tree
- get_value_for (tree var, varray_type table)
- {
- return VARRAY_TREE (table, var_ann (var)->uid);
- }
-
-
- /* Associate VALUE to variable VAR in TABLE. */
-
- static inline void
- set_value_for (tree var, tree value, varray_type table)
- {
- VARRAY_TREE (table, var_ann (var)->uid) = value;
- }
-
-
/* Compute global livein information given the set of blockx where
an object is locally live at the start of the block (LIVEIN)
and the set of blocks where the object is defined (DEF_BLOCKS).
--- 124,129 ----
*************** rewrite_initialize_block (struct dom_wal
*** 519,525 ****
{
tree result = PHI_RESULT (phi);
! register_new_def (result, &bd->block_defs, currdefs);
}
}
--- 494,500 ----
{
tree result = PHI_RESULT (phi);
! register_new_def (result, &bd->block_defs);
}
}
*************** rewrite_finalize_block (struct dom_walk_
*** 584,590 ****
var = tmp;
}
! set_value_for (var, saved_def, currdefs);
}
}
--- 559,565 ----
var = tmp;
}
! var_ann (var)->current_def = saved_def;
}
}
*************** rewrite_stmt (struct dom_walk_data *walk
*** 780,786 ****
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
! register_new_def (*def_p, &bd->block_defs, currdefs);
}
/* Register new virtual definitions made by the statement. */
--- 755,761 ----
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
! register_new_def (*def_p, &bd->block_defs);
}
/* Register new virtual definitions made by the statement. */
*************** rewrite_stmt (struct dom_walk_data *walk
*** 794,800 ****
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
! register_new_def (VDEF_RESULT (vdefs, i), &bd->block_defs, currdefs);
}
}
--- 769,775 ----
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
! register_new_def (VDEF_RESULT (vdefs, i), &bd->block_defs);
}
}
*************** rewrite_operand (tree *op_p)
*** 815,821 ****
into the stack pointed by BLOCK_DEFS_P. */
void
! register_new_def (tree def, varray_type *block_defs_p, varray_type table)
{
tree var = SSA_NAME_VAR (def);
tree currdef;
--- 790,796 ----
into the stack pointed by BLOCK_DEFS_P. */
void
! register_new_def (tree def, varray_type *block_defs_p)
{
tree var = SSA_NAME_VAR (def);
tree currdef;
*************** register_new_def (tree def, varray_type
*** 830,840 ****
computed and available for us to use. */
if (var_ann (var)->need_phi_state == NEED_PHI_STATE_NO)
{
! set_value_for (var, def, table);
return;
}
! currdef = get_value_for (var, table);
if (! *block_defs_p)
VARRAY_TREE_INIT (*block_defs_p, 20, "block_defs");
--- 805,815 ----
computed and available for us to use. */
if (var_ann (var)->need_phi_state == NEED_PHI_STATE_NO)
{
! var_ann (var)->current_def = def;
return;
}
! currdef = var_ann (var)->current_def;
if (! *block_defs_p)
VARRAY_TREE_INIT (*block_defs_p, 20, "block_defs");
*************** register_new_def (tree def, varray_type
*** 846,852 ****
VARRAY_PUSH_TREE (*block_defs_p, currdef ? currdef : var);
/* Set the current reaching definition for VAR to be DEF. */
! set_value_for (var, def, table);
}
--- 821,827 ----
VARRAY_PUSH_TREE (*block_defs_p, currdef ? currdef : var);
/* Set the current reaching definition for VAR to be DEF. */
! var_ann (var)->current_def = def;
}
*************** get_reaching_def (tree var)
*** 863,869 ****
/* Lookup the current reaching definition for VAR. */
default_d = NULL_TREE;
! currdef_var = get_value_for (var, currdefs);
/* If there is no reaching definition for VAR, create and register a
default definition for it (if needed). */
--- 838,844 ----
/* Lookup the current reaching definition for VAR. */
default_d = NULL_TREE;
! currdef_var = var_ann (var)->current_def;
/* If there is no reaching definition for VAR, create and register a
default definition for it (if needed). */
*************** get_reaching_def (tree var)
*** 875,881 ****
default_d = make_ssa_name (var, build_empty_stmt ());
set_default_def (var, default_d);
}
! set_value_for (var, default_d, currdefs);
}
/* Return the current reaching definition for VAR, or the default
--- 850,856 ----
default_d = make_ssa_name (var, build_empty_stmt ());
set_default_def (var, default_d);
}
! var_ann (var)->current_def = default_d;
}
/* Return the current reaching definition for VAR, or the default
*************** rewrite_into_ssa (void)
*** 1061,1066 ****
--- 1036,1042 ----
basic_block bb;
struct dom_walk_data walk_data;
struct mark_def_sites_global_data mark_def_sites_global_data;
+ unsigned int i;
timevar_push (TV_TREE_SSA_OTHER);
*************** rewrite_into_ssa (void)
*** 1078,1085 ****
def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars),
def_blocks_hash, def_blocks_eq, def_blocks_free);
- VARRAY_TREE_INIT (currdefs, num_referenced_vars, "currdefs");
-
/* Initialize dominance frontier and immediate dominator bitmaps.
Also count the number of predecessors for each block. Doing so
can save significant time during PHI insertion for large graphs. */
--- 1054,1059 ----
*************** rewrite_into_ssa (void)
*** 1096,1101 ****
--- 1070,1078 ----
dfs[bb->index] = BITMAP_XMALLOC ();
}
+ for (i = 0; i < num_referenced_vars; i++)
+ var_ann (referenced_var (i))->current_def = NULL;
+
/* Ensure that the dominance information is OK. */
calculate_dominance_info (CDI_DOMINATORS);
*************** rewrite_into_ssa (void)
*** 1179,1185 ****
free (dfs);
htab_delete (def_blocks);
- VARRAY_CLEAR (currdefs);
timevar_pop (TV_TREE_SSA_OTHER);
}
--- 1156,1161 ----
Index: gcc/tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.158
diff -c -p -r1.1.2.158 tree-ssa-dom.c
*** gcc/tree-ssa-dom.c 20 Apr 2004 14:22:30 -0000 1.1.2.158
--- gcc/tree-ssa-dom.c 21 Apr 2004 17:38:36 -0000
*************** struct expr_hash_elt
*** 89,99 ****
propagation). */
static varray_type const_and_copies;
- /* Table to store the current reaching definition for every variable in
- the function. Given a variable V, its entry will be its immediately
- reaching SSA_NAME node. */
- static varray_type currdefs;
-
/* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
know their exact value. */
static bitmap nonzero_vars;
--- 89,94 ----
*************** struct dom_walk_block_data
*** 207,213 ****
which variables need their VRP data updated. */
varray_type vrp_variables;
! /* Array of tree pairs used to restore the globcal currdefs to its
original state after completing optimization of a block and its
dominator children. */
varray_type block_defs;
--- 202,208 ----
which variables need their VRP data updated. */
varray_type vrp_variables;
! /* Array of tree pairs used to restore the global currdefs to its
original state after completing optimization of a block and its
dominator children. */
varray_type block_defs;
*************** static void restore_vars_to_original_val
*** 265,272 ****
unsigned limit,
varray_type table);
static void restore_currdefs_to_original_value (varray_type locals,
! unsigned limit,
! varray_type table);
static void register_definitions_for_stmt (stmt_ann_t, varray_type *);
static void redirect_edges_and_update_ssa_graph (varray_type);
--- 260,266 ----
unsigned limit,
varray_type table);
static void restore_currdefs_to_original_value (varray_type locals,
! unsigned limit);
static void register_definitions_for_stmt (stmt_ann_t, varray_type *);
static void redirect_edges_and_update_ssa_graph (varray_type);
*************** local_fold (tree t)
*** 291,306 ****
static inline tree
get_value_for (tree var, varray_type table)
{
! unsigned int indx;
!
! if (TREE_CODE (var) == SSA_NAME)
! indx = SSA_NAME_VERSION (var);
! else if (DECL_P (var))
! indx = var_ann (var)->uid;
! else
! abort ();
!
! return VARRAY_TREE (table, indx);
}
/* Associate VALUE to variable VAR in TABLE. */
--- 285,291 ----
static inline tree
get_value_for (tree var, varray_type table)
{
! return VARRAY_TREE (table, SSA_NAME_VERSION (var));
}
/* Associate VALUE to variable VAR in TABLE. */
*************** get_value_for (tree var, varray_type tab
*** 308,323 ****
static inline void
set_value_for (tree var, tree value, varray_type table)
{
! unsigned int indx;
!
! if (TREE_CODE (var) == SSA_NAME)
! indx = SSA_NAME_VERSION (var);
! else if (DECL_P (var))
! indx = var_ann (var)->uid;
! else
! abort ();
!
! VARRAY_TREE (table, indx) = value;
}
/* REDIRECTION_EDGES contains edge pairs where we want to revector the
--- 293,299 ----
static inline void
set_value_for (tree var, tree value, varray_type table)
{
! VARRAY_TREE (table, SSA_NAME_VERSION (var)) = value;
}
/* REDIRECTION_EDGES contains edge pairs where we want to revector the
*************** tree_ssa_dominator_optimize (void)
*** 553,558 ****
--- 529,538 ----
{
basic_block bb;
struct dom_walk_data walk_data;
+ unsigned int i;
+
+ for (i = 0; i < num_referenced_vars; i++)
+ var_ann (referenced_var (i))->current_def = NULL;
/* Mark loop edges so we avoid threading across loop boundaries.
This may result in transforming natural loop into irreducible
*************** tree_ssa_dominator_optimize (void)
*** 565,572 ****
nonzero_vars = BITMAP_XMALLOC ();
VARRAY_EDGE_INIT (redirection_edges, 20, "redirection_edges");
VARRAY_GENERIC_PTR_INIT (vrp_data, highest_ssa_version, "vrp_data");
- VARRAY_TREE_INIT (currdefs, num_referenced_vars, "currdefs");
-
/* Setup callbacks for the generic dominator tree walker. */
walk_data.walk_stmts_backward = false;
--- 545,550 ----
*************** tree_ssa_dominator_optimize (void)
*** 633,642 ****
rewrite_into_ssa ();
bitmap_clear (vars_to_rename);
- /* The out-of SSA translation may have created new variables which
- affects the size of CURRDEFS. */
- VARRAY_GROW (currdefs, num_referenced_vars);
-
/* The into SSA translation may have created new SSA_NAMES whic
affect the size of CONST_AND_COPIES and VRP_DATA. */
VARRAY_GROW (const_and_copies, highest_ssa_version);
--- 611,616 ----
*************** tree_ssa_dominator_optimize (void)
*** 648,654 ****
htab_empty (avail_exprs);
VARRAY_CLEAR (const_and_copies);
VARRAY_CLEAR (vrp_data);
! VARRAY_CLEAR (currdefs);
}
while (cfg_altered);
--- 622,630 ----
htab_empty (avail_exprs);
VARRAY_CLEAR (const_and_copies);
VARRAY_CLEAR (vrp_data);
!
! for (i = 0; i < num_referenced_vars; i++)
! var_ann (referenced_var (i))->current_def = NULL;
}
while (cfg_altered);
*************** thread_across_edge (struct dom_walk_data
*** 712,718 ****
tree src = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, e));
tree dst = PHI_RESULT (phi);
record_const_or_copy (dst, src, &bd->const_and_copies);
! register_new_def (dst, &bd->block_defs, currdefs);
}
for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
--- 688,694 ----
tree src = PHI_ARG_DEF (phi, phi_arg_from_edge (phi, e));
tree dst = PHI_RESULT (phi);
record_const_or_copy (dst, src, &bd->const_and_copies);
! register_new_def (dst, &bd->block_defs);
}
for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
*************** thread_across_edge (struct dom_walk_data
*** 816,822 ****
/* If CACHED_LHS does not represent the current value of the undering
variable in CACHED_LHS/LHS, then we can not ignore this statement. */
! if (get_value_for (SSA_NAME_VAR (lhs), currdefs) != cached_lhs)
break;
/* If we got here, then we can ignore this statement and continue
--- 792,798 ----
/* If CACHED_LHS does not represent the current value of the undering
variable in CACHED_LHS/LHS, then we can not ignore this statement. */
! if (var_ann (SSA_NAME_VAR (lhs))->current_def != cached_lhs)
break;
/* If we got here, then we can ignore this statement and continue
*************** thread_across_edge (struct dom_walk_data
*** 827,833 ****
the result of this statement is used later we can copy propagate
suitably. */
record_const_or_copy (lhs, cached_lhs, &bd->const_and_copies);
! register_new_def (lhs, &bd->block_defs, currdefs);
}
/* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
--- 803,809 ----
the result of this statement is used later we can copy propagate
suitably. */
record_const_or_copy (lhs, cached_lhs, &bd->const_and_copies);
! register_new_def (lhs, &bd->block_defs);
}
/* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
*************** restore_vars_to_original_value (varray_t
*** 1140,1148 ****
/* Similar to restore_vars_to_original_value, except that it restores
CURRDEFS to its original value. */
static void
! restore_currdefs_to_original_value (varray_type locals,
! unsigned limit,
! varray_type table)
{
if (!locals)
return;
--- 1116,1122 ----
/* Similar to restore_vars_to_original_value, except that it restores
CURRDEFS to its original value. */
static void
! restore_currdefs_to_original_value (varray_type locals, unsigned limit)
{
if (!locals)
return;
*************** restore_currdefs_to_original_value (varr
*** 1170,1176 ****
var = tmp;
}
! set_value_for (var, saved_def, table);
}
}
--- 1144,1150 ----
var = tmp;
}
! var_ann (var)->current_def = saved_def;
}
}
*************** dom_opt_finalize_block (struct dom_walk_
*** 1258,1266 ****
restore_vars_to_original_value (bd->const_and_copies,
const_and_copies_limit,
const_and_copies);
! restore_currdefs_to_original_value (bd->block_defs,
! currdefs_limit,
! currdefs);
}
/* Similarly for the ELSE arm. */
--- 1232,1238 ----
restore_vars_to_original_value (bd->const_and_copies,
const_and_copies_limit,
const_and_copies);
! restore_currdefs_to_original_value (bd->block_defs, currdefs_limit);
}
/* Similarly for the ELSE arm. */
*************** dom_opt_finalize_block (struct dom_walk_
*** 1288,1294 ****
remove_local_expressions_from_table (bd->avail_exprs, 0, avail_exprs);
restore_nonzero_vars_to_original_value (bd->nonzero_vars, 0, nonzero_vars);
restore_vars_to_original_value (bd->const_and_copies, 0, const_and_copies);
! restore_currdefs_to_original_value (bd->block_defs, 0, currdefs);
/* Remove VRP records associated with this basic block. They are no
longer valid.
--- 1260,1266 ----
remove_local_expressions_from_table (bd->avail_exprs, 0, avail_exprs);
restore_nonzero_vars_to_original_value (bd->nonzero_vars, 0, nonzero_vars);
restore_vars_to_original_value (bd->const_and_copies, 0, const_and_copies);
! restore_currdefs_to_original_value (bd->block_defs, 0);
/* Remove VRP records associated with this basic block. They are no
longer valid.
*************** record_equivalences_from_phis (struct do
*** 1389,1395 ****
&& may_propagate_copy (lhs, rhs))
set_value_for (lhs, rhs, const_and_copies);
! register_new_def (lhs, &bd->block_defs, currdefs);
}
}
--- 1361,1367 ----
&& may_propagate_copy (lhs, rhs))
set_value_for (lhs, rhs, const_and_copies);
! register_new_def (lhs, &bd->block_defs);
}
}
*************** register_definitions_for_stmt (stmt_ann_
*** 3150,3156 ****
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
! register_new_def (def, block_defs_p, currdefs);
}
/* Register new virtual definitions made by the statement. */
--- 3122,3128 ----
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
! register_new_def (def, block_defs_p);
}
/* Register new virtual definitions made by the statement. */
*************** register_definitions_for_stmt (stmt_ann_
*** 3159,3165 ****
{
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
! register_new_def (VDEF_RESULT (vdefs, i), block_defs_p, currdefs);
}
}
--- 3131,3137 ----
{
/* FIXME: We shouldn't be registering new defs if the variable
doesn't need to be renamed. */
! register_new_def (VDEF_RESULT (vdefs, i), block_defs_p);
}
}
More information about the Gcc-patches
mailing list