This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] Dominator speedup.
- From: Andrew MacLeod <amacleod at redhat dot com>
- To: gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: 26 Sep 2003 09:09:03 -0400
- Subject: [tree-ssa] Dominator speedup.
This patch speeds the dominator optimization pass up. Similar to CCP, it
was spending a good portion of time looking up hash values for constants
and copies.it was on the order of 20%-25%. I've replaced the hash table
with a varray. Compile time in the dom. opts. on libjava/interpret.cc
drops from about 5.0 seconds to 3.7 seconds.
Bootstrapped on x86 and no new regressions.
Andrew
2003-09-26 Andrew MacLeod <amacloeod@redhat.com>
* tree-ssa-dom.c (struct var_value_d): Remove.
(const_and_copies): Change to a varray_type.
(tree_ssa_dominator_optimize): Initialize const_and_copies as a varray.
(optimize_block): Simply set the value in const_and_copies.
(dump_dominator_optimization_stats): No hash stats for const_and_copies.
(record_cond_is_true, record_cond_is_false,
simplify_rhs_and_lookup_avail_expr, update_rhs_and_lookup_avail_expr):
Parameter const_and_copies is now a varray_type.
(var_value_hash, var_value_eq): Remove.
(get_value_for, set_value_for): Access varray elements.
(get_eq_expr_value): Parameter const_and_copies is now a varray_type.
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.48
diff -c -p -r1.1.2.48 tree-ssa-dom.c
*** tree-ssa-dom.c 25 Sep 2003 18:13:20 -0000 1.1.2.48
--- tree-ssa-dom.c 26 Sep 2003 11:06:41 -0000
*************** Boston, MA 02111-1307, USA. */
*** 44,57 ****
static FILE *dump_file;
static int dump_flags;
- /* Structure to map variables to values. It's used to keep track of the
- available constants and copies. */
- struct var_value_d
- {
- tree var;
- tree value;
- };
-
/* Hash table with expressions made available during the renaming process.
When an assignment of the form X_i = EXPR is found, the statement is
stored in this table. If the same expression EXPR is later found on the
--- 44,49 ----
*************** struct var_value_d
*** 59,65 ****
global redundancy elimination). */
static htab_t avail_exprs;
! /* Hash table of constant values and copies indexed by SSA name. When the
renaming pass finds an assignment of a constant (X_i = C) or a copy
assignment from another SSA variable (X_i = Y_j), it creates a mapping
between X_i and the RHS in this table. This mapping is used later on,
--- 51,57 ----
global redundancy elimination). */
static htab_t avail_exprs;
! /* Table of constant values and copies indexed by SSA name. When the
renaming pass finds an assignment of a constant (X_i = C) or a copy
assignment from another SSA variable (X_i = Y_j), it creates a mapping
between X_i and the RHS in this table. This mapping is used later on,
*************** static htab_t avail_exprs;
*** 67,73 ****
table, instead of using X_i, we use the RHS of the statement stored in
this table (thus performing very simplistic copy and constant
propagation). */
! static htab_t const_and_copies;
/* Statistics for dominator optimizations. */
struct opt_stats_d
--- 59,65 ----
table, instead of using X_i, we use the RHS of the statement stored in
this table (thus performing very simplistic copy and constant
propagation). */
! static varray_type const_and_copies;
/* Statistics for dominator optimizations. */
struct opt_stats_d
*************** static varray_type redirection_targets;
*** 88,109 ****
/* Local functions. */
static void optimize_block (basic_block, tree, int, sbitmap, bool *);
static bool optimize_stmt (block_stmt_iterator, varray_type *, bool *);
! static tree get_value_for (tree, htab_t);
! static void set_value_for (tree, tree, htab_t);
! static hashval_t var_value_hash (const void *);
! static int var_value_eq (const void *, const void *);
! static tree lookup_avail_expr (tree, varray_type *, htab_t, bool);
! static tree get_eq_expr_value (tree, int, varray_type *, htab_t);
static hashval_t avail_expr_hash (const void *);
static int avail_expr_eq (const void *, const void *);
static void htab_statistics (FILE *, htab_t);
! static void record_cond_is_false (tree, varray_type *, htab_t);
! static void record_cond_is_true (tree, varray_type *, htab_t);
static void thread_edge (edge, basic_block);
static tree update_rhs_and_lookup_avail_expr (tree, tree, varray_type *,
! htab_t, stmt_ann_t, bool);
static tree simplify_rhs_and_lookup_avail_expr (tree, varray_type *,
! htab_t, stmt_ann_t, int);
/* Optimize function FNDECL based on the dominator tree. This does
simple const/copy propagation and redundant expression elimination using
--- 80,99 ----
/* Local functions. */
static void optimize_block (basic_block, tree, int, sbitmap, bool *);
static bool optimize_stmt (block_stmt_iterator, varray_type *, bool *);
! static inline tree get_value_for (tree, varray_type);
! static inline void set_value_for (tree, tree, varray_type);
! static tree lookup_avail_expr (tree, varray_type *, varray_type, bool);
! static tree get_eq_expr_value (tree, int, varray_type *, varray_type);
static hashval_t avail_expr_hash (const void *);
static int avail_expr_eq (const void *, const void *);
static void htab_statistics (FILE *, htab_t);
! static void record_cond_is_false (tree, varray_type *, varray_type);
! static void record_cond_is_true (tree, varray_type *, varray_type);
static void thread_edge (edge, basic_block);
static tree update_rhs_and_lookup_avail_expr (tree, tree, varray_type *,
! varray_type, stmt_ann_t, bool);
static tree simplify_rhs_and_lookup_avail_expr (tree, varray_type *,
! varray_type, stmt_ann_t, int);
/* Optimize function FNDECL based on the dominator tree. This does
simple const/copy propagation and redundant expression elimination using
*************** tree_ssa_dominator_optimize (tree fndecl
*** 128,135 ****
/* Set up debugging dump files. */
dump_file = dump_begin (phase, &dump_flags);
! /* Create our hash tables. */
! const_and_copies = htab_create (1024, var_value_hash, var_value_eq, free);
avail_exprs = htab_create (1024, avail_expr_hash, avail_expr_eq, NULL);
/* Build the dominator tree if necessary.
--- 118,124 ----
/* Set up debugging dump files. */
dump_file = dump_begin (phase, &dump_flags);
! /* Create our hash table. */
avail_exprs = htab_create (1024, avail_expr_hash, avail_expr_eq, NULL);
/* Build the dominator tree if necessary.
*************** tree_ssa_dominator_optimize (tree fndecl
*** 153,158 ****
--- 142,148 ----
free_dominance_info (idom);
}
+ VARRAY_TREE_INIT (const_and_copies, next_ssa_version, "const_and_copies");
VARRAY_EDGE_INIT (edges_to_redirect, 20, "edges_to_redirect");
VARRAY_BB_INIT (redirection_targets, 20, "redirection_targets");
*************** tree_ssa_dominator_optimize (tree fndecl
*** 168,176 ****
optimize_block (ENTRY_BLOCK_PTR, NULL, 0, vars_to_rename, &cfg_altered);
/* Wipe the hash tables. */
- htab_empty (const_and_copies);
htab_empty (avail_exprs);
/* If some edges were threaded in this iteration, then perform
the required redirections and recompute the dominators. */
if (VARRAY_ACTIVE_SIZE (edges_to_redirect) > 0)
--- 158,167 ----
optimize_block (ENTRY_BLOCK_PTR, NULL, 0, vars_to_rename, &cfg_altered);
/* Wipe the hash tables. */
htab_empty (avail_exprs);
+ VARRAY_CLEAR (const_and_copies);
+
/* If some edges were threaded in this iteration, then perform
the required redirections and recompute the dominators. */
if (VARRAY_ACTIVE_SIZE (edges_to_redirect) > 0)
*************** tree_ssa_dominator_optimize (tree fndecl
*** 220,226 ****
dump_end (phase, dump_file);
}
- htab_delete (const_and_copies);
htab_delete (avail_exprs);
VARRAY_FREE (edges_to_redirect);
--- 211,216 ----
*************** optimize_block (basic_block bb, tree par
*** 738,755 ****
while (VARRAY_ACTIVE_SIZE (block_const_and_copies) > 0)
{
tree prev_value, dest;
- struct var_value_d vm;
prev_value = VARRAY_TOP_TREE (block_const_and_copies);
VARRAY_POP (block_const_and_copies);
dest = VARRAY_TOP_TREE (block_const_and_copies);
VARRAY_POP (block_const_and_copies);
! vm.var = dest;
! if (prev_value)
! set_value_for (vm.var, prev_value, const_and_copies);
! else
! htab_remove_elt (const_and_copies, &vm);
}
/* Re-scan operands in all statements that may have had new symbols
--- 728,740 ----
while (VARRAY_ACTIVE_SIZE (block_const_and_copies) > 0)
{
tree prev_value, dest;
prev_value = VARRAY_TOP_TREE (block_const_and_copies);
VARRAY_POP (block_const_and_copies);
dest = VARRAY_TOP_TREE (block_const_and_copies);
VARRAY_POP (block_const_and_copies);
! set_value_for (dest, prev_value, const_and_copies);
}
/* Re-scan operands in all statements that may have had new symbols
*************** dump_dominator_optimization_stats (FILE
*** 793,801 ****
fprintf (file, " avail_exprs: ");
htab_statistics (file, avail_exprs);
- fprintf (file, " const_and_copies: ");
- htab_statistics (file, const_and_copies);
-
fprintf (file, "\n");
}
--- 778,783 ----
*************** htab_statistics (FILE *file, htab_t htab
*** 826,832 ****
static void
record_cond_is_true (tree cond,
varray_type *block_avail_exprs_p,
! htab_t const_and_copies)
{
tree stmt;
--- 808,814 ----
static void
record_cond_is_true (tree cond,
varray_type *block_avail_exprs_p,
! varray_type const_and_copies)
{
tree stmt;
*************** record_cond_is_true (tree cond,
*** 840,846 ****
static void
record_cond_is_false (tree cond,
varray_type *block_avail_exprs_p,
! htab_t const_and_copies)
{
tree stmt;
--- 822,828 ----
static void
record_cond_is_false (tree cond,
varray_type *block_avail_exprs_p,
! varray_type const_and_copies)
{
tree stmt;
*************** record_cond_is_false (tree cond,
*** 858,864 ****
static tree
simplify_rhs_and_lookup_avail_expr (tree stmt,
varray_type *block_avail_exprs_p,
! htab_t const_and_copies,
stmt_ann_t ann,
int insert)
{
--- 840,846 ----
static tree
simplify_rhs_and_lookup_avail_expr (tree stmt,
varray_type *block_avail_exprs_p,
! varray_type const_and_copies,
stmt_ann_t ann,
int insert)
{
*************** optimize_stmt (block_stmt_iterator si, v
*** 1475,1481 ****
static tree
update_rhs_and_lookup_avail_expr (tree stmt, tree new_rhs,
varray_type *block_avail_exprs_p,
! htab_t const_and_copies,
stmt_ann_t ann,
bool insert)
{
--- 1457,1463 ----
static tree
update_rhs_and_lookup_avail_expr (tree stmt, tree new_rhs,
varray_type *block_avail_exprs_p,
! varray_type const_and_copies,
stmt_ann_t ann,
bool insert)
{
*************** update_rhs_and_lookup_avail_expr (tree s
*** 1523,1587 ****
return cached_lhs;
}
- /* Hashing and equality functions for VAR_VALUE_D. */
-
- static hashval_t
- var_value_hash (const void *p)
- {
- return htab_hash_pointer
- ((const void *)((const struct var_value_d *)p)->var);
- }
-
- static int
- var_value_eq (const void *p1, const void *p2)
- {
- return ((const struct var_value_d *)p1)->var
- == ((const struct var_value_d *)p2)->var;
- }
-
/* Return the value associated with variable VAR in TABLE. */
! static tree
! get_value_for (tree var, htab_t table)
{
- struct var_value_d *vm_p, vm;
#if defined ENABLE_CHECKING
if (TREE_CODE (var) != SSA_NAME)
abort ();
#endif
!
! vm.var = var;
! vm_p = (struct var_value_d *) htab_find (table, (void *) &vm);
! return (vm_p) ? vm_p->value : NULL_TREE;
}
/* Associate VALUE to variable VAR in TABLE. */
! static void
! set_value_for (tree var, tree value, htab_t table)
{
- struct var_value_d *vm_p, vm;
- void **slot;
#if defined ENABLE_CHECKING
if (TREE_CODE (var) != SSA_NAME)
abort ();
#endif
! vm.var = var;
! slot = htab_find_slot (table, (void *) &vm, INSERT);
! if (*slot == NULL)
! {
! vm_p = xmalloc (sizeof *vm_p);
! vm_p->var = var;
! *slot = (void *) vm_p;
! }
! else
! vm_p = (struct var_value_d *) *slot;
!
! vm_p->value = value;
}
--- 1505,1536 ----
return cached_lhs;
}
/* Return the value associated with variable VAR in TABLE. */
! static inline tree
! get_value_for (tree var, varray_type table)
{
#if defined ENABLE_CHECKING
if (TREE_CODE (var) != SSA_NAME)
abort ();
#endif
! return VARRAY_TREE (table, SSA_NAME_VERSION (var));
}
/* Associate VALUE to variable VAR in TABLE. */
! static inline void
! set_value_for (tree var, tree value, varray_type table)
{
#if defined ENABLE_CHECKING
if (TREE_CODE (var) != SSA_NAME)
abort ();
#endif
! VARRAY_TREE (table, SSA_NAME_VERSION (var)) = value;
}
*************** set_value_for (tree var, tree value, hta
*** 1600,1606 ****
static tree
lookup_avail_expr (tree stmt,
varray_type *block_avail_exprs_p,
! htab_t const_and_copies,
bool insert)
{
void **slot;
--- 1549,1555 ----
static tree
lookup_avail_expr (tree stmt,
varray_type *block_avail_exprs_p,
! varray_type const_and_copies,
bool insert)
{
void **slot;
*************** lookup_avail_expr (tree stmt,
*** 1674,1681 ****
get back a constant indicating if the condition is true. */
static tree
! get_eq_expr_value (tree if_stmt, int true_arm,
! varray_type *block_avail_exprs_p, htab_t const_and_copies)
{
tree cond, value;
--- 1623,1630 ----
get back a constant indicating if the condition is true. */
static tree
! get_eq_expr_value (tree if_stmt, int true_arm, varray_type *block_avail_exprs_p,
! varray_type const_and_copies)
{
tree cond, value;