diff options
| -rw-r--r-- | gcc/ChangeLog | 13 | ||||
| -rw-r--r-- | gcc/tree-ssa-dom.c | 99 |
2 files changed, 91 insertions, 21 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b6ae90a..0902a1d 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,18 @@ 2004-09-21 Jeff Law <law@redhat.com> + * tree-ssa-dom.c (opt_stats): Move so that it lives just after + the opt_stats_d structure. + (vrp_data): Change from a varray into a hash table. + (vrp_hash_elt): New structure for elements in the vrp hash table. + (vrp_hash, vrp_eq):New functions for hashing and testing equality + in the vrp hash table. + (tree_ssa_dominator_optimize): Initialize VRP_DATA. Reorganize + initialization slightly to make it easier to read. No longer need + to grow/clear the varray. Instead empty and delete the hash table. + (dom_opt_finalize_block): Update due to change of VRP_DATA from + a varray to a hash table. + (simplify_cond_and_loop_avail_expr, record_range): Similarly. + * tree-ssa-ccp.c (get_default_value): If we have a constant value recorded for an SSA_NAME, then use that constant as the initial lattice value. diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index a0acd5d..057e72a 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -141,6 +141,8 @@ struct opt_stats_d long num_re; }; +static struct opt_stats_d opt_stats; + /* Value range propagation record. Each time we encounter a conditional of the form SSA_NAME COND CONST we create a new vrp_element to record how the condition affects the possible values SSA_NAME may have. @@ -192,11 +194,20 @@ struct vrp_element basic_block bb; }; -static struct opt_stats_d opt_stats; +/* A hash table holding value range records (VRP_ELEMENTs) for a given + SSA_NAME. We used to use a varray indexed by SSA_NAME_VERSION, but + that gets awful wasteful, particularly since the density objects + with useful information is very low. */ +static htab_t vrp_data; + +/* An entry in the VRP_DATA hash table. We record the variable and a + varray of VRP_ELEMENT records associated with that variable. */ -/* A virtual array holding value range records for the variable identified - by the index, SSA_VERSION. */ -static varray_type vrp_data; +struct vrp_hash_elt +{ + tree var; + varray_type records; +}; /* Array of variables which have their values constrained by operations in this basic block. We use this during finalization to know @@ -221,6 +232,8 @@ static void optimize_stmt (struct dom_walk_data *, block_stmt_iterator); static tree lookup_avail_expr (tree, bool); static struct eq_expr_value get_eq_expr_value (tree, int, basic_block); +static hashval_t vrp_hash (const void *); +static int vrp_eq (const void *, const void *); static hashval_t avail_expr_hash (const void *); static hashval_t real_avail_expr_hash (const void *); static int avail_expr_eq (const void *, const void *); @@ -291,15 +304,15 @@ tree_ssa_dominator_optimize (void) /* Create our hash tables. */ avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free); + vrp_data = htab_create (ceil_log2 (num_ssa_names), vrp_hash, vrp_eq, free); VARRAY_TREE_INIT (avail_exprs_stack, 20, "Available expression stack"); VARRAY_TREE_INIT (block_defs_stack, 20, "Block DEFS stack"); VARRAY_TREE_INIT (const_and_copies_stack, 20, "Block const_and_copies stack"); VARRAY_TREE_INIT (nonzero_vars_stack, 20, "Block nonzero_vars stack"); VARRAY_TREE_INIT (vrp_variables_stack, 20, "Block vrp_variables stack"); + VARRAY_TREE_INIT (stmts_to_rescan, 20, "Statements to rescan"); nonzero_vars = BITMAP_XMALLOC (); - VARRAY_GENERIC_PTR_INIT (vrp_data, num_ssa_names, "vrp_data"); need_eh_cleanup = BITMAP_XMALLOC (); - VARRAY_TREE_INIT (stmts_to_rescan, 20, "Statements to rescan"); /* Setup callbacks for the generic dominator tree walker. */ walk_data.walk_stmts_backward = false; @@ -363,13 +376,10 @@ tree_ssa_dominator_optimize (void) rewrite_ssa_into_ssa (); - if (VARRAY_ACTIVE_SIZE (vrp_data) <= num_ssa_names) - VARRAY_GROW (vrp_data, num_ssa_names); - /* Reinitialize the various tables. */ bitmap_clear (nonzero_vars); htab_empty (avail_exprs); - VARRAY_CLEAR (vrp_data); + htab_empty (vrp_data); for (i = 0; i < num_referenced_vars; i++) var_ann (referenced_var (i))->current_def = NULL; @@ -382,6 +392,7 @@ tree_ssa_dominator_optimize (void) /* We emptied the hash table earlier, now delete it completely. */ htab_delete (avail_exprs); + htab_delete (vrp_data); /* It is not necessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA, CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom @@ -949,6 +960,8 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb) while (VARRAY_ACTIVE_SIZE (vrp_variables_stack) > 0) { tree var = VARRAY_TOP_TREE (vrp_variables_stack); + struct vrp_hash_elt vrp_hash_elt; + void **slot; /* Each variable has a stack of value range records. We want to invalidate those associated with our basic block. So we walk @@ -962,7 +975,12 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb) if (var == NULL) break; - var_vrp_records = VARRAY_GENERIC_PTR (vrp_data, SSA_NAME_VERSION (var)); + vrp_hash_elt.var = var; + vrp_hash_elt.records = NULL; + + slot = htab_find_slot (vrp_data, &vrp_hash_elt, NO_INSERT); + + var_vrp_records = (*(struct vrp_hash_elt **)slot)->records; while (VARRAY_ACTIVE_SIZE (var_vrp_records) > 0) { struct vrp_element *element @@ -973,7 +991,6 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb) VARRAY_POP (var_vrp_records); } - } /* If we queued any statements to rescan in this block, then @@ -1859,6 +1876,8 @@ simplify_cond_and_lookup_avail_expr (tree stmt, int lowequal, highequal, swapped, no_overlap, subset, cond_inverted; varray_type vrp_records; struct vrp_element *element; + struct vrp_hash_elt vrp_hash_elt; + void **slot; /* First see if we have test of an SSA_NAME against a constant where the SSA_NAME is defined by an earlier typecast which @@ -1901,7 +1920,13 @@ simplify_cond_and_lookup_avail_expr (tree stmt, Also note the vast majority of conditionals are not testing a variable which has had its range constrained by an earlier conditional. So this filter avoids a lot of unnecessary work. */ - vrp_records = VARRAY_GENERIC_PTR (vrp_data, SSA_NAME_VERSION (op0)); + vrp_hash_elt.var = op0; + vrp_hash_elt.records = NULL; + slot = htab_find_slot (vrp_data, &vrp_hash_elt, NO_INSERT); + if (slot == NULL) + return NULL; + + vrp_records = (*(struct vrp_hash_elt **)slot)->records; if (vrp_records == NULL) return NULL; @@ -2947,22 +2972,31 @@ record_range (tree cond, basic_block bb) && TREE_CODE (cond) != NE_EXPR && TREE_CODE (TREE_TYPE (TREE_OPERAND (cond, 1))) == INTEGER_TYPE) { - struct vrp_element *element = ggc_alloc (sizeof (struct vrp_element)); - int ssa_version = SSA_NAME_VERSION (TREE_OPERAND (cond, 0)); + struct vrp_hash_elt *vrp_hash_elt; + struct vrp_element *element; + varray_type *vrp_records_p; + void **slot; + + + vrp_hash_elt = xmalloc (sizeof (struct vrp_hash_elt)); + vrp_hash_elt->var = TREE_OPERAND (cond, 0); + vrp_hash_elt->records = NULL; + slot = htab_find_slot (vrp_data, vrp_hash_elt, INSERT); - varray_type *vrp_records_p - = (varray_type *)&VARRAY_GENERIC_PTR (vrp_data, ssa_version); + if (*slot == NULL) + *slot = (void *)vrp_hash_elt; + vrp_hash_elt = *(struct vrp_hash_elt **)slot; + vrp_records_p = &vrp_hash_elt->records; + + element = ggc_alloc (sizeof (struct vrp_element)); element->low = NULL; element->high = NULL; element->cond = cond; element->bb = bb; if (*vrp_records_p == NULL) - { - VARRAY_GENERIC_PTR_INIT (*vrp_records_p, 2, "vrp records"); - VARRAY_GENERIC_PTR (vrp_data, ssa_version) = *vrp_records_p; - } + VARRAY_GENERIC_PTR_INIT (*vrp_records_p, 2, "vrp records"); VARRAY_PUSH_GENERIC_PTR (*vrp_records_p, element); VARRAY_PUSH_TREE (vrp_variables_stack, TREE_OPERAND (cond, 0)); @@ -3093,6 +3127,29 @@ get_eq_expr_value (tree if_stmt, return retval; } +/* Hashing and equality functions for VRP_DATA. + + Since this hash table is addressed by SSA_NAMEs, we can hash on + their version number and equality can be determined with a + pointer comparison. */ + +static hashval_t +vrp_hash (const void *p) +{ + tree var = ((struct vrp_hash_elt *)p)->var; + + return SSA_NAME_VERSION (var); +} + +static int +vrp_eq (const void *p1, const void *p2) +{ + tree var1 = ((struct vrp_hash_elt *)p1)->var; + tree var2 = ((struct vrp_hash_elt *)p2)->var; + + return var1 == var2; +} + /* Hashing and equality functions for AVAIL_EXPRS. The table stores MODIFY_EXPR statements. We compute a value number for expressions using the code of the expression and the SSA numbers of its operands. */ |