From ca072a31b75eacb8292cfa91fb779020ee5f6118 Mon Sep 17 00:00:00 2001 From: Daniel Berlin Date: Thu, 17 Jun 2004 12:53:33 +0000 Subject: [PATCH] tree-ssa-pre.c: Update comments. 2004-06-17 Daniel Berlin * tree-ssa-pre.c: Update comments. (val_expr_pair_eq): Factor code from here. (expr_pred_trans_eq): and here. (expressions_equal_p): To here. (print_value_set): Print value for expression. (phi_trans_lookup): Rename some variables. (lookup): Ditto. (value_exists_in_set_bitmap): Ditto. (value_remove_from_set_bitmap): Ditto. (value_insert_into_set_bitmap): Ditto. From-SVN: r83290 --- gcc/ChangeLog | 13 +++ gcc/tree-ssa-pre.c | 222 +++++++++++++++++++++++++++++++-------------- 2 files changed, 165 insertions(+), 70 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 17ffc884dcb..551a2ec8792 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,16 @@ +2004-06-17 Daniel Berlin + + * tree-ssa-pre.c: Update comments. + (val_expr_pair_eq): Factor code from here. + (expr_pred_trans_eq): and here. + (expressions_equal_p): To here. + (print_value_set): Print value for expression. + (phi_trans_lookup): Rename some variables. + (lookup): Ditto. + (value_exists_in_set_bitmap): Ditto. + (value_remove_from_set_bitmap): Ditto. + (value_insert_into_set_bitmap): Ditto. + 2004-06-17 Ulrich Weigand * config/s390/s390-modes.def (CCL3mode): New machine mode. diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index fe7738c185d..e98fbfc6025 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -182,19 +182,38 @@ Boston, MA 02111-1307, USA. */ expressions/constants/values. */ typedef struct value_set_node { + /* An expression. */ tree expr; + + /* A pointer to the next element of the value set. */ struct value_set_node *next; } *value_set_node_t; -/* A value set, which is the head of the linked list, and we also keep - the tail because we have to append for the topolofical sort. */ +/* A value set. This is a singly linked list of value_set_node + elements with a possible bitmap that tells us what values exist in + the set. This set must be kept in topologically sorted order. */ typedef struct value_set { + /* The head of the list. Used for iterating over the list in + order. */ value_set_node_t head; + + /* The tail of the list. Used for tail insertions, which are + necessary to keep the set in topologically sorted order because + of how the set is built. */ value_set_node_t tail; + + /* The length of the list. */ size_t length; + + /* True if the set is indexed, which means it contains a backing + bitmap for quick determination of whether certain values exist in the + set. */ bool indexed; + + /* The bitmap of values that exist in the set. May be NULL in an + empty or non-indexed set. */ bitmap values; } *value_set_t; @@ -202,13 +221,32 @@ typedef struct value_set /* All of the following sets, except for TMP_GEN, are indexed. TMP_GEN is only ever iterated over, we never check what values exist in it. */ + typedef struct bb_value_sets { + /* The EXP_GEN set, which represents expressions/values generated in + a basic block. */ value_set_t exp_gen; + + /* The PHI_GEN set, which represents PHI results generated in a + basic block. */ value_set_t phi_gen; + + /* The TMP_GEN set, which represents results/temporaries genererated + in a basic block. IE the LHS of an expression. */ value_set_t tmp_gen; + + /* The AVAIL_OUT set, which represents which values are available in + a given basic block. */ value_set_t avail_out; + + /* The ANTIC_IN set, which represents which values are anticiptable + in a given basic block. */ value_set_t antic_in; + + /* The NEW_SETS set, which is used during insertion to augment the + AVAIL_OUT set of blocks with the new insertions performed during + the current iteration. */ value_set_t new_sets; } *bb_value_sets_t; @@ -219,10 +257,17 @@ typedef struct bb_value_sets #define ANTIC_IN(BB) ((bb_value_sets_t) ((BB)->aux))->antic_in #define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets +/* This structure is used to keep track of statistics on what + optimization PRE was able to perform. */ static struct { + /* The number of RHS computations eliminated by PRE. */ int eliminations; + + /* The number of new expressions/temporaries generated by PRE. */ int insertions; + + /* The number of new PHI nodes added by PRE. */ int phis; } pre_stats; @@ -232,6 +277,7 @@ static void insert_into_set (value_set_t, tree); static void add_to_value (tree, tree); static value_set_t set_new (bool); static bool is_undefined_value (tree); +static bool expressions_equal_p (tree, tree); /* We can add and remove elements and entries to and from sets and hash tables, so we use alloc pools for them. */ @@ -242,12 +288,34 @@ static alloc_pool binary_node_pool; static alloc_pool unary_node_pool; /* The value table that maps expressions to values. */ + static htab_t value_table; /* The phi_translate_table caches phi translations for a given expression and predecessor. */ + static htab_t phi_translate_table; +/* Compare two expressions E1 and E2 and return true if they are + equal. */ + +static bool +expressions_equal_p (tree e1, tree e2) +{ + tree te1, te2; + + if (e1 == e2) + return true; + + te1 = TREE_TYPE (e1); + te2 = TREE_TYPE (e2); + + if (TREE_CODE (e1) == TREE_CODE (e2) + && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2)) + && operand_equal_p (e1, e2, 0)) + return true; + return false; +} /* Map expressions to values. These are simple pairs of expressions and the values they represent. To find the value represented by @@ -261,7 +329,9 @@ typedef struct val_expr_pair_d } *val_expr_pair_t; -/* Hash a {v,e} pair. We really only hash the expression. */ +/* Hash a {v,e} pair that is pointed to by P. + The hashcode is cached in the val_expr_pair, so we just return + that. */ static hashval_t val_expr_pair_hash (const void *p) @@ -271,34 +341,26 @@ val_expr_pair_hash (const void *p) } -/* Are {e2,v2} and {e1,v1} the same? Again, only the expression - matters. */ +/* Given two val_expr_pair_t's, return true if they represent the same + expression, false otherwise. + P1 and P2 should point to the val_expr_pair_t's to be compared. */ static int val_expr_pair_expr_eq (const void *p1, const void *p2) { const val_expr_pair_t ve1 = (val_expr_pair_t) p1; const val_expr_pair_t ve2 = (val_expr_pair_t) p2; - tree e1 = ve1->e; - tree e2 = ve2->e; - tree te1; - tree te2; - if (e1 == e2) - return true; - te1 = TREE_TYPE (e1); - te2 = TREE_TYPE (e2); - if (TREE_CODE (e1) == TREE_CODE (e2) - && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2)) - && operand_equal_p (e1, e2, 0)) + if (expressions_equal_p (ve1->e, ve2->e)) return true; - + return false; } /* Get the value handle of EXPR. This is the only correct way to get - the value handle for a "thing". */ + the value handle for a "thing". + Returns NULL if the value handle does not exist. */ tree get_value_handle (tree expr) @@ -328,7 +390,7 @@ get_value_handle (tree expr) } -/* Set the value handle for E to V */ +/* Set the value handle for expression E to value V */ void set_value_handle (tree e, tree v) @@ -348,9 +410,17 @@ set_value_handle (tree e, tree v) typedef struct expr_pred_trans_d { + /* The expression. */ tree e; + + /* The predecessor block along which we translated the expression. */ basic_block pred; + + /* The value that resulted from the translation. */ tree v; + + /* The hashcode for the expression, pred pair. This is cached for + speed reasons. */ hashval_t hashcode; } *expr_pred_trans_t; @@ -363,49 +433,44 @@ expr_pred_trans_hash (const void *p) return ve->hashcode; } -/* Return true if two phi translation table entries are the same. */ +/* Return true if two phi translation table entries are the same. + P1 and P2 should point to the expr_pred_trans_t's to be compared.*/ static int expr_pred_trans_eq (const void *p1, const void *p2) { const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1; const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2; - tree e1 = ve1->e; - tree e2 = ve2->e; basic_block b1 = ve1->pred; basic_block b2 = ve2->pred; - tree te1; - tree te2; + + /* If they are not translations for the same basic block, they can't + be equal. */ if (b1 != b2) return false; - if (e1 == e2) - return true; - - te1 = TREE_TYPE (e1); - te2 = TREE_TYPE (e2); - - if (TREE_CODE (e1) == TREE_CODE (e2) - && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2)) - && operand_equal_p (e1, e2, 0)) + /* If they are for the same basic block, determine if the + expressions are equal. */ + if (expressions_equal_p (ve1->e, ve2->e)) return true; return false; } -/* Search in the phi translation table for the translation of E in - PRED. Return the translated value, if found, NULL otherwise. */ +/* Search in the phi translation table for the translation of + expression E in basic block PRED. Return the translated value, if + found, NULL otherwise. */ static inline tree phi_trans_lookup (tree e, basic_block pred) { void **slot; - struct expr_pred_trans_d ugly; - ugly.e = e; - ugly.pred = pred; - ugly.hashcode = iterative_hash_expr (e, (unsigned long) pred); - slot = htab_find_slot_with_hash (phi_translate_table, &ugly, ugly.hashcode, + struct expr_pred_trans_d ept; + ept.e = e; + ept.pred = pred; + ept.hashcode = iterative_hash_expr (e, (unsigned long) pred); + slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode, NO_INSERT); if (!slot) return NULL; @@ -414,7 +479,8 @@ phi_trans_lookup (tree e, basic_block pred) } -/* Add the tuple mapping {e, pred}->v to the phi translation table. */ +/* Add the tuple mapping from {expression E, basic block PRED} to + value V, to the phi translation table. */ static inline void phi_trans_add (tree e, tree v, basic_block pred) @@ -439,17 +505,17 @@ static inline tree lookup (htab_t table, tree e) { void **slot; - struct val_expr_pair_d ugly = {NULL, NULL, 0}; - ugly.e = e; - ugly.hashcode = iterative_hash_expr (e,0); - slot = htab_find_slot_with_hash (table, &ugly, ugly.hashcode, NO_INSERT); + struct val_expr_pair_d vep = {NULL, NULL, 0}; + vep.e = e; + vep.hashcode = iterative_hash_expr (e,0); + slot = htab_find_slot_with_hash (table, &vep, vep.hashcode, NO_INSERT); if (!slot) return NULL_TREE; else return ((val_expr_pair_t) *slot)->v; } -/* Add E to the expression set of V. */ +/* Add expression E to the expression set of value V. */ static inline void add_to_value (tree v, tree e) @@ -480,7 +546,8 @@ add_to_value (tree v, tree e) #endif } -/* Insert E into TABLE with value V, and add E to the value set for V. */ +/* Insert E into TABLE with value V, and add expression E to the value + set for value V. */ static inline void add (htab_t table, tree e, tree v) @@ -502,9 +569,12 @@ add (htab_t table, tree e, tree v) } +/* A unique counter that is incremented every time we create a new + value. */ static int pre_uid; -/* Create a new value handle for EXPR. */ +/* Create a new value handle for expression EXPR. */ + static tree create_new_value (tree expr) { @@ -523,7 +593,10 @@ create_new_value (tree expr) return a; } -/* Like lookup, but adds V as the value for E if E does not have a value. */ +/* Like lookup, but creates a new value for expression E if E doesn't + already have a value. + Return the existing/created value for E. */ + static inline tree lookup_or_add (htab_t table, tree e) { @@ -540,25 +613,25 @@ lookup_or_add (htab_t table, tree e) } -/* Search in the bitmap for SET to see if E exists. */ +/* Return true if value V exists in the bitmap for SET. */ static inline bool -value_exists_in_set_bitmap (value_set_t set, tree e) +value_exists_in_set_bitmap (value_set_t set, tree v) { - if (TREE_CODE (e) != VAR_DECL) + if (TREE_CODE (v) != VAR_DECL) abort (); if (!set->values) return false; - return bitmap_bit_p (set->values, get_var_ann (e)->uid); + return bitmap_bit_p (set->values, get_var_ann (v)->uid); } -/* Remove E from the bitmap for SET. */ +/* Remove value V from the bitmap for SET. */ static void -value_remove_from_set_bitmap (value_set_t set, tree e) +value_remove_from_set_bitmap (value_set_t set, tree v) { - if (TREE_CODE (e) != VAR_DECL) + if (TREE_CODE (v) != VAR_DECL) abort (); #ifdef ENABLE_CHECKING if (!set->indexed) @@ -566,17 +639,17 @@ value_remove_from_set_bitmap (value_set_t set, tree e) #endif if (!set->values) return; - bitmap_clear_bit (set->values, get_var_ann (e)->uid); + bitmap_clear_bit (set->values, get_var_ann (v)->uid); } -/* Insert the value number E into the bitmap of values existing in +/* Insert the value number V into the bitmap of values existing in SET. */ static inline void -value_insert_into_set_bitmap (value_set_t set, tree e) +value_insert_into_set_bitmap (value_set_t set, tree v) { - if (TREE_CODE (e) != VAR_DECL) + if (TREE_CODE (v) != VAR_DECL) abort (); #ifdef ENABLE_CHECKING if (!set->indexed) @@ -587,7 +660,7 @@ value_insert_into_set_bitmap (value_set_t set, tree e) set->values = BITMAP_GGC_ALLOC (); bitmap_clear (set->values); } - bitmap_set_bit (set->values, get_var_ann (e)->uid); + bitmap_set_bit (set->values, get_var_ann (v)->uid); } /* Create a new set. */ @@ -824,6 +897,11 @@ print_value_set (FILE *outfile, value_set_t set, node = node->next) { print_generic_expr (outfile, node->expr, 0); + + fprintf (outfile, " ("); + print_generic_expr (outfile, get_value_handle (node->expr), 0); + fprintf (outfile, ") "); + if (node->next) fprintf (outfile, ", "); } @@ -921,9 +999,9 @@ phi_translate (tree expr, value_set_t set, basic_block pred, return NULL; if (newop1 != oldop1) { - newexpr = pool_alloc (unary_node_pool); + newexpr = pool_alloc (unary_node_pool); memcpy (newexpr, expr, tree_size (expr)); - create_expr_ann (newexpr); + create_expr_ann (newexpr); TREE_OPERAND (newexpr, 0) = get_value_handle (newop1); lookup_or_add (value_table, newexpr); expr = newexpr; @@ -1047,9 +1125,9 @@ valid_in_set (value_set_t set, tree expr) return false; } -/* Clean the set of expressions that are no longer valid in the - specified set. This means expressions that are made up of values - we have no leaders for in the current set, etc. */ +/* Clean the set of expressions that are no longer valid in SET. This + means expressions that are made up of values we have no leaders for + in SET. */ static void clean (value_set_t set) @@ -1179,6 +1257,7 @@ compute_antic_aux (basic_block block) value_insert_into_set (ANTIC_IN (block), node->expr); } clean (ANTIC_IN (block)); + if (!set_equal (old, ANTIC_IN (block))) changed = true; @@ -1274,12 +1353,12 @@ insert_aux (basic_block block) tree *avail; tree val; bool by_some = false; + bool cant_insert = false; bool all_same = true; tree first_s = NULL; edge pred; basic_block bprime; tree eprime; - bool cant_insert = false; val = get_value_handle (node->expr); if (set_contains_value (PHI_GEN (block), val)) @@ -1331,7 +1410,7 @@ insert_aux (basic_block block) else { avail[bprime->index] = edoubleprime; - by_some = true; + by_some = true; if (first_s == NULL) first_s = edoubleprime; else if (first_s != edoubleprime) @@ -1341,11 +1420,14 @@ insert_aux (basic_block block) abort (); } } - + /* If we can insert it, it's not the same value + already existing along every predecessor, and + it's defined by some predecessor, it is + partially redundant. */ if (!cant_insert && !all_same && by_some) { - tree temp; tree type = TREE_TYPE (avail[block->pred->src->index]); + tree temp; tree v; if (dump_file && (dump_flags & TDF_DETAILS)) -- 2.30.2