This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa] More dominator optimizer compile-time improvements
- From: law at redhat dot com
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 13 Apr 2004 09:01:47 -0600
- Subject: [tree-ssa] More dominator optimizer compile-time improvements
- Reply-to: law at redhat dot com
This change slightly improves the compile-time performance of the
dominator optimizer when checking is enabled.
The major component of this patch is avoiding redundant calls into the
available expression hash routine (avail_expr_hash). We avoid the redundant
calls by saving the expression's hash value in its associated hash table
entry itself.
We also avoid many thousands of calls to is_gimple_stmt in Gerald's testcase
by using [V]DEF_OPS instead of STMT_[V]DEF_OPS.
Finally, this patch cleans up clearing the various tables before the next
iteration of the optimizer. I don't think this will have any performance
impact, it's strictly to make the code easier to read.
Bootstrapped and regression tested i686-pc-linux-gnu.
* tree-ssa-dom.c (struct expr_hash_elt): Add new field for hash value.
(initialize_hash_element): New LHS argument. Callers changed.
Initialize the hash value field.
(remove_local_expressions_from_table): Use htab_remove_elt_with_hash.
(update_rhs_and_lookup_avail_expr): Similary.
(lookup_avail_expr): Use htab_find_slot_with_hash. Simplify slightly
and pass LHS to initialize_hash_element.
(record_cond): Also use htab_find_slot_with_hash. Initialize the
hash table entry with initialize_hash_element.
(avail_expr_eq): Use the saved hash value rather than calling into
the hash functions again.
* tree-ssa-dom.c (tree_ssa_dominator_optimize): Slightly rearrange
code to clear tables before each iteration to be clearer.
* tree-ssa-dom.c (redirect_edges_and_update_ssa_graph): Use
DEF_OPS and VDEF_OPS instead of STMT_DEF_OPS and STMT_VDEF_OPS.
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.153
diff -c -p -r1.1.2.153 tree-ssa-dom.c
*** tree-ssa-dom.c 12 Apr 2004 20:04:12 -0000 1.1.2.153
--- tree-ssa-dom.c 13 Apr 2004 14:51:47 -0000
*************** struct expr_hash_elt
*** 74,79 ****
--- 74,82 ----
/* The annotation if this element corresponds to a statement. */
stmt_ann_t ann;
+
+ /* The hash value for RHS/ann. */
+ hashval_t hash;
};
/* Table of constant values and copies indexed by SSA name. When the
*************** redirect_edges_and_update_ssa_graph (var
*** 378,397 ****
def_optype defs;
vdef_optype vdefs;
tree stmt = bsi_stmt (bsi);
if (TREE_CODE (stmt) == COND_EXPR)
break;
get_stmt_operands (stmt);
! defs = STMT_DEF_OPS (stmt);
for (j = 0; j < NUM_DEFS (defs); j++)
{
tree op = SSA_NAME_VAR (DEF_OP (defs, j));
bitmap_set_bit (vars_to_rename, var_ann (op)->uid);
}
! vdefs = STMT_VDEF_OPS (stmt);
for (j = 0; j < NUM_VDEFS (vdefs); j++)
{
tree op = VDEF_RESULT (vdefs, j);
--- 381,401 ----
def_optype defs;
vdef_optype vdefs;
tree stmt = bsi_stmt (bsi);
+ stmt_ann_t ann = stmt_ann (stmt);
if (TREE_CODE (stmt) == COND_EXPR)
break;
get_stmt_operands (stmt);
! defs = DEF_OPS (ann);
for (j = 0; j < NUM_DEFS (defs); j++)
{
tree op = SSA_NAME_VAR (DEF_OP (defs, j));
bitmap_set_bit (vars_to_rename, var_ann (op)->uid);
}
! vdefs = VDEF_OPS (ann);
for (j = 0; j < NUM_VDEFS (vdefs); j++)
{
tree op = VDEF_RESULT (vdefs, j);
*************** tree_ssa_dominator_optimize (void)
*** 604,613 ****
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
/* Wipe the hash tables. */
- htab_empty (avail_exprs);
-
- VARRAY_CLEAR (const_and_copies);
- bitmap_clear (nonzero_vars);
if (VARRAY_ACTIVE_SIZE (redirection_edges) > 0)
redirect_edges_and_update_ssa_graph (redirection_edges);
--- 608,613 ----
*************** tree_ssa_dominator_optimize (void)
*** 632,645 ****
{
rewrite_into_ssa ();
bitmap_clear (vars_to_rename);
VARRAY_GROW (const_and_copies, highest_ssa_version);
VARRAY_GROW (vrp_data, highest_ssa_version);
- VARRAY_GROW (currdefs, num_referenced_vars);
- VARRAY_CLEAR (const_and_copies);
- VARRAY_CLEAR (vrp_data);
- bitmap_clear (nonzero_vars);
- VARRAY_CLEAR (currdefs);
}
}
while (cfg_altered);
--- 632,654 ----
{
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);
VARRAY_GROW (vrp_data, highest_ssa_version);
}
+
+ /* Reinitialize the various tables. */
+ bitmap_clear (nonzero_vars);
+ htab_empty (avail_exprs);
+ VARRAY_CLEAR (const_and_copies);
+ VARRAY_CLEAR (vrp_data);
+ VARRAY_CLEAR (currdefs);
}
while (cfg_altered);
*************** tree_ssa_dominator_optimize (void)
*** 650,661 ****
if (dump_file && (dump_flags & TDF_STATS))
dump_dominator_optimization_stats (dump_file);
htab_delete (avail_exprs);
! VARRAY_CLEAR (redirection_edges);
! VARRAY_CLEAR (currdefs);
!
! BITMAP_XFREE (nonzero_vars);
/* And finalize the dominator walker. */
fini_walk_dominator_tree (&walk_data);
--- 659,670 ----
if (dump_file && (dump_flags & TDF_STATS))
dump_dominator_optimization_stats (dump_file);
+ /* We emptyed the hash table earlier, now delete it completely. */
htab_delete (avail_exprs);
! /* It is not nocessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
! CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
! of the do-while loop above. */
/* And finalize the dominator walker. */
fini_walk_dominator_tree (&walk_data);
*************** dom_opt_initialize_block (struct dom_wal
*** 1024,1030 ****
initialize the hash table element pointed by by ELEMENT. */
static void
! initialize_hash_element (tree expr, struct expr_hash_elt *element)
{
/* Hash table elements may be based on conditional expressions or
statements.
--- 1033,1039 ----
initialize the hash table element pointed by by ELEMENT. */
static void
! initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)
{
/* Hash table elements may be based on conditional expressions or
statements.
*************** initialize_hash_element (tree expr, stru
*** 1058,1064 ****
element->rhs = TREE_OPERAND (expr, 1);
}
! element->lhs = NULL;
}
/* Remove all the expressions in LOCALS from TABLE, stopping when there are
--- 1067,1074 ----
element->rhs = TREE_OPERAND (expr, 1);
}
! element->lhs = lhs;
! element->hash = avail_expr_hash (element);
}
/* Remove all the expressions in LOCALS from TABLE, stopping when there are
*************** remove_local_expressions_from_table (var
*** 1079,1086 ****
tree expr = VARRAY_TOP_TREE (locals);
VARRAY_POP (locals);
! initialize_hash_element (expr, &element);
! htab_remove_elt (table, &element);
}
}
--- 1089,1096 ----
tree expr = VARRAY_TOP_TREE (locals);
VARRAY_POP (locals);
! initialize_hash_element (expr, NULL, &element);
! htab_remove_elt_with_hash (table, &element, element.hash);
}
}
*************** record_cond (tree cond, tree value, varr
*** 1570,1580 ****
struct expr_hash_elt *element = xmalloc (sizeof (struct expr_hash_elt));
void **slot;
! element->rhs = cond;
! element->lhs = value;
! element->ann = NULL;
! slot = htab_find_slot (avail_exprs, (void *)element, true);
if (*slot == NULL)
{
*slot = (void *) element;
--- 1580,1589 ----
struct expr_hash_elt *element = xmalloc (sizeof (struct expr_hash_elt));
void **slot;
! initialize_hash_element (cond, value, element);
! slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
! element->hash, true);
if (*slot == NULL)
{
*slot = (void *) element;
*************** update_rhs_and_lookup_avail_expr (tree s
*** 2663,2670 ****
{
struct expr_hash_elt element;
! initialize_hash_element (stmt, &element);
! htab_remove_elt (avail_exprs, &element);
}
/* Now update the RHS of the assignment. */
--- 2672,2679 ----
{
struct expr_hash_elt element;
! initialize_hash_element (stmt, NULL, &element);
! htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
}
/* Now update the RHS of the assignment. */
*************** lookup_avail_expr (tree stmt, varray_typ
*** 2724,2731 ****
tree temp;
struct expr_hash_elt *element = xcalloc (sizeof (struct expr_hash_elt), 1);
! initialize_hash_element (stmt, element);
/* Don't bother remembering constant assignments and copy operations.
Constants and copy operations are handled by the constant/copy
propagator
--- 2733,2741 ----
tree temp;
struct expr_hash_elt *element = xcalloc (sizeof (struct expr_hash_elt), 1);
+ lhs = TREE_CODE (stmt) == MODIFY_EXPR ? TREE_OPERAND (stmt, 0) : NULL;
! initialize_hash_element (stmt, lhs, element);
/* Don't bother remembering constant assignments and copy operations.
Constants and copy operations are handled by the constant/copy
propagator
*************** lookup_avail_expr (tree stmt, varray_typ
*** 2737,2746 ****
return NULL_TREE;
}
- /* If STMT is a MODIFY_EXPR, then we want to record its LHS as well. */
- if (TREE_CODE (stmt) == MODIFY_EXPR)
- element->lhs = TREE_OPERAND (stmt, 0);
-
/* If this is an equality test against zero, see if we have recorded a
nonzero value for the variable in question. */
if ((TREE_CODE (element->rhs) == EQ_EXPR
--- 2747,2752 ----
*************** lookup_avail_expr (tree stmt, varray_typ
*** 2762,2768 ****
}
/* Finally try to find the expression in the main expression hash table.
*/
! slot = htab_find_slot (avail_exprs, element, (insert ? INSERT :
NO_INSERT));
if (slot == NULL)
{
free (element);
--- 2768,2775 ----
}
/* Finally try to find the expression in the main expression hash table.
*/
! slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
! (insert ? INSERT : NO_INSERT));
if (slot == NULL)
{
free (element);
*************** avail_expr_eq (const void *p1, const voi
*** 3108,3114 ****
return false;
#ifdef ENABLE_CHECKING
! if (avail_expr_hash (p1) != avail_expr_hash (p2))
abort ();
#endif
return true;
--- 3115,3122 ----
return false;
#ifdef ENABLE_CHECKING
! if (((struct expr_hash_elt *)p1)->hash
! != ((struct expr_hash_elt *)p2)->hash)
abort ();
#endif
return true;