diff options
Diffstat (limited to 'gcc/tree-outof-ssa.c')
| -rw-r--r-- | gcc/tree-outof-ssa.c | 604 |
1 files changed, 0 insertions, 604 deletions
diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c index 279934d98e6..5edea642805 100644 --- a/gcc/tree-outof-ssa.c +++ b/gcc/tree-outof-ssa.c @@ -1121,610 +1121,6 @@ eliminate_virtual_phis (void) } -/* Temporary Expression Replacement (TER) - - Replace SSA version variables during out-of-ssa with their defining - expression if there is only one use of the variable. - - A pass is made through the function, one block at a time. No cross block - information is tracked. - - Variables which only have one use, and whose defining stmt is considered - a replaceable expression (see check_replaceable) are entered into - consideration by adding a list of dependent partitions to the version_info - vector for that ssa_name_version. This information comes from the partition - mapping for each USE. At the same time, the partition_dep_list vector for - these partitions have this version number entered into their lists. - - When the use of a replaceable ssa_variable is encountered, the dependence - list in version_info[] is moved to the "pending_dependence" list in case - the current expression is also replaceable. (To be determined later in - processing this stmt.) version_info[] for the version is then updated to - point to the defining stmt and the 'replaceable' bit is set. - - Any partition which is defined by a statement 'kills' any expression which - is dependent on this partition. Every ssa version in the partitions' - dependence list is removed from future consideration. - - All virtual references are lumped together. Any expression which is - dependent on any virtual variable (via a VUSE) has a dependence added - to the special partition defined by VIRTUAL_PARTITION. - - Whenever a V_MAY_DEF is seen, all expressions dependent this - VIRTUAL_PARTITION are removed from consideration. - - At the end of a basic block, all expression are removed from consideration - in preparation for the next block. - - The end result is a vector over SSA_NAME_VERSION which is passed back to - rewrite_out_of_ssa. As the SSA variables are being rewritten, instead of - replacing the SSA_NAME tree element with the partition it was assigned, - it is replaced with the RHS of the defining expression. */ - - -/* Dependency list element. This can contain either a partition index or a - version number, depending on which list it is in. */ - -typedef struct value_expr_d -{ - int value; - struct value_expr_d *next; -} *value_expr_p; - - -/* Temporary Expression Replacement (TER) table information. */ - -typedef struct temp_expr_table_d -{ - var_map map; - void **version_info; - bitmap *expr_vars; - value_expr_p *partition_dep_list; - bitmap replaceable; - bool saw_replaceable; - int virtual_partition; - bitmap partition_in_use; - value_expr_p free_list; - value_expr_p pending_dependence; -} *temp_expr_table_p; - -/* Used to indicate a dependency on V_MAY_DEFs. */ -#define VIRTUAL_PARTITION(table) (table->virtual_partition) - -static temp_expr_table_p new_temp_expr_table (var_map); -static tree *free_temp_expr_table (temp_expr_table_p); -static inline value_expr_p new_value_expr (temp_expr_table_p); -static inline void free_value_expr (temp_expr_table_p, value_expr_p); -static inline value_expr_p find_value_in_list (value_expr_p, int, - value_expr_p *); -static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int); -static inline void add_info_to_list (temp_expr_table_p, value_expr_p *, - value_expr_p); -static value_expr_p remove_value_from_list (value_expr_p *, int); -static void add_dependence (temp_expr_table_p, int, tree); -static bool check_replaceable (temp_expr_table_p, tree); -static void finish_expr (temp_expr_table_p, int, bool); -static void mark_replaceable (temp_expr_table_p, tree); -static inline void kill_expr (temp_expr_table_p, int, bool); -static inline void kill_virtual_exprs (temp_expr_table_p, bool); -static void find_replaceable_in_bb (temp_expr_table_p, basic_block); -static tree *find_replaceable_exprs (var_map); -static void dump_replaceable_exprs (FILE *, tree *); - - -/* Create a new TER table for MAP. */ - -static temp_expr_table_p -new_temp_expr_table (var_map map) -{ - temp_expr_table_p t; - - t = XNEW (struct temp_expr_table_d); - t->map = map; - - t->version_info = XCNEWVEC (void *, num_ssa_names + 1); - t->expr_vars = XCNEWVEC (bitmap, num_ssa_names + 1); - t->partition_dep_list = XCNEWVEC (value_expr_p, - num_var_partitions (map) + 1); - - t->replaceable = BITMAP_ALLOC (NULL); - t->partition_in_use = BITMAP_ALLOC (NULL); - - t->saw_replaceable = false; - t->virtual_partition = num_var_partitions (map); - t->free_list = NULL; - t->pending_dependence = NULL; - - return t; -} - - -/* Free TER table T. If there are valid replacements, return the expression - vector. */ - -static tree * -free_temp_expr_table (temp_expr_table_p t) -{ - value_expr_p p; - tree *ret = NULL; - unsigned i; - -#ifdef ENABLE_CHECKING - unsigned x; - for (x = 0; x <= num_var_partitions (t->map); x++) - gcc_assert (!t->partition_dep_list[x]); -#endif - - while ((p = t->free_list)) - { - t->free_list = p->next; - free (p); - } - - BITMAP_FREE (t->partition_in_use); - BITMAP_FREE (t->replaceable); - - for (i = 0; i <= num_ssa_names; i++) - if (t->expr_vars[i]) - BITMAP_FREE (t->expr_vars[i]); - free (t->expr_vars); - - free (t->partition_dep_list); - if (t->saw_replaceable) - ret = (tree *)t->version_info; - else - free (t->version_info); - - free (t); - return ret; -} - - -/* Allocate a new value list node. Take it from the free list in TABLE if - possible. */ - -static inline value_expr_p -new_value_expr (temp_expr_table_p table) -{ - value_expr_p p; - if (table->free_list) - { - p = table->free_list; - table->free_list = p->next; - } - else - p = (value_expr_p) xmalloc (sizeof (struct value_expr_d)); - - return p; -} - - -/* Add value list node P to the free list in TABLE. */ - -static inline void -free_value_expr (temp_expr_table_p table, value_expr_p p) -{ - p->next = table->free_list; - table->free_list = p; -} - - -/* Find VALUE if it's in LIST. Return a pointer to the list object if found, - else return NULL. If LAST_PTR is provided, it will point to the previous - item upon return, or NULL if this is the first item in the list. */ - -static inline value_expr_p -find_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr) -{ - value_expr_p curr; - value_expr_p last = NULL; - - for (curr = list; curr; last = curr, curr = curr->next) - { - if (curr->value == value) - break; - } - if (last_ptr) - *last_ptr = last; - return curr; -} - - -/* Add VALUE to LIST, if it isn't already present. TAB is the expression - table */ - -static inline void -add_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value) -{ - value_expr_p info; - - if (!find_value_in_list (*list, value, NULL)) - { - info = new_value_expr (tab); - info->value = value; - info->next = *list; - *list = info; - } -} - - -/* Add value node INFO if it's value isn't already in LIST. Free INFO if - it is already in the list. TAB is the expression table. */ - -static inline void -add_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info) -{ - if (find_value_in_list (*list, info->value, NULL)) - free_value_expr (tab, info); - else - { - info->next = *list; - *list = info; - } -} - - -/* Look for VALUE in LIST. If found, remove it from the list and return it's - pointer. */ - -static value_expr_p -remove_value_from_list (value_expr_p *list, int value) -{ - value_expr_p info, last; - - info = find_value_in_list (*list, value, &last); - if (!info) - return NULL; - if (!last) - *list = info->next; - else - last->next = info->next; - - return info; -} - - -/* Add a dependency between the def of ssa VERSION and VAR. If VAR is - replaceable by an expression, add a dependence each of the elements of the - expression. These are contained in the pending list. TAB is the - expression table. */ - -static void -add_dependence (temp_expr_table_p tab, int version, tree var) -{ - int i, x; - value_expr_p info; - - i = SSA_NAME_VERSION (var); - if (bitmap_bit_p (tab->replaceable, i)) - { - /* This variable is being substituted, so use whatever dependences - were queued up when we marked this as replaceable earlier. */ - while ((info = tab->pending_dependence)) - { - tab->pending_dependence = info->next; - /* Get the partition this variable was dependent on. Reuse this - object to represent the current expression instead. */ - x = info->value; - info->value = version; - add_info_to_list (tab, &(tab->partition_dep_list[x]), info); - add_value_to_list (tab, - (value_expr_p *)&(tab->version_info[version]), x); - bitmap_set_bit (tab->partition_in_use, x); - } - } - else - { - i = var_to_partition (tab->map, var); - gcc_assert (i != NO_PARTITION); - add_value_to_list (tab, &(tab->partition_dep_list[i]), version); - add_value_to_list (tab, - (value_expr_p *)&(tab->version_info[version]), i); - bitmap_set_bit (tab->partition_in_use, i); - } -} - - -/* Check if expression STMT is suitable for replacement in table TAB. If so, - create an expression entry. Return true if this stmt is replaceable. */ - -static bool -check_replaceable (temp_expr_table_p tab, tree stmt) -{ - tree var, def, basevar; - int version; - ssa_op_iter iter; - tree call_expr; - bitmap def_vars, use_vars; - - if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT) - return false; - - /* Punt if there is more than 1 def, or more than 1 use. */ - def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF); - if (!def) - return false; - - if (num_imm_uses (def) != 1) - return false; - - /* There must be no V_MAY_DEFS or V_MUST_DEFS. */ - if (!(ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF)))) - return false; - - /* Float expressions must go through memory if float-store is on. */ - if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE - (GENERIC_TREE_OPERAND (stmt, 1)))) - return false; - - /* Calls to functions with side-effects cannot be replaced. */ - if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE) - { - int call_flags = call_expr_flags (call_expr); - if (TREE_SIDE_EFFECTS (call_expr) - && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN))) - return false; - } - - version = SSA_NAME_VERSION (def); - basevar = SSA_NAME_VAR (def); - def_vars = BITMAP_ALLOC (NULL); - bitmap_set_bit (def_vars, DECL_UID (basevar)); - - /* Add this expression to the dependency list for each use partition. */ - FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) - { - add_dependence (tab, version, var); - - use_vars = tab->expr_vars[SSA_NAME_VERSION (var)]; - if (use_vars) - bitmap_ior_into (def_vars, use_vars); - } - tab->expr_vars[version] = def_vars; - - /* If there are VUSES, add a dependence on virtual defs. */ - if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE)) - { - add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]), - VIRTUAL_PARTITION (tab)); - add_value_to_list (tab, - &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]), - version); - bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab)); - } - - return true; -} - - -/* This function will remove the expression for VERSION from replacement - consideration.n table TAB If 'replace' is true, it is marked as - replaceable, otherwise not. */ - -static void -finish_expr (temp_expr_table_p tab, int version, bool replace) -{ - value_expr_p info, tmp; - int partition; - - /* Remove this expression from its dependent lists. The partition dependence - list is retained and transfered later to whomever uses this version. */ - for (info = (value_expr_p) tab->version_info[version]; info; info = tmp) - { - partition = info->value; - gcc_assert (tab->partition_dep_list[partition]); - tmp = remove_value_from_list (&(tab->partition_dep_list[partition]), - version); - gcc_assert (tmp); - free_value_expr (tab, tmp); - /* Only clear the bit when the dependency list is emptied via - a replacement. Otherwise kill_expr will take care of it. */ - if (!(tab->partition_dep_list[partition]) && replace) - bitmap_clear_bit (tab->partition_in_use, partition); - tmp = info->next; - if (!replace) - free_value_expr (tab, info); - } - - if (replace) - { - tab->saw_replaceable = true; - bitmap_set_bit (tab->replaceable, version); - } - else - { - gcc_assert (!bitmap_bit_p (tab->replaceable, version)); - tab->version_info[version] = NULL; - } -} - - -/* Mark the expression associated with VAR as replaceable, and enter - the defining stmt into the version_info table TAB. */ - -static void -mark_replaceable (temp_expr_table_p tab, tree var) -{ - value_expr_p info; - int version = SSA_NAME_VERSION (var); - finish_expr (tab, version, true); - - /* Move the dependence list to the pending list. */ - if (tab->version_info[version]) - { - info = (value_expr_p) tab->version_info[version]; - for ( ; info->next; info = info->next) - continue; - info->next = tab->pending_dependence; - tab->pending_dependence = (value_expr_p)tab->version_info[version]; - } - - tab->version_info[version] = SSA_NAME_DEF_STMT (var); -} - - -/* This function marks any expression in TAB which is dependent on PARTITION - as NOT replaceable. CLEAR_BIT is used to determine whether partition_in_use - should have its bit cleared. Since this routine can be called within an - EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared. */ - -static inline void -kill_expr (temp_expr_table_p tab, int partition, bool clear_bit) -{ - value_expr_p ptr; - - /* Mark every active expr dependent on this var as not replaceable. */ - while ((ptr = tab->partition_dep_list[partition]) != NULL) - finish_expr (tab, ptr->value, false); - - if (clear_bit) - bitmap_clear_bit (tab->partition_in_use, partition); -} - - -/* This function kills all expressions in TAB which are dependent on virtual - DEFs. CLEAR_BIT determines whether partition_in_use gets cleared. */ - -static inline void -kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit) -{ - kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit); -} - - -/* This function processes basic block BB, and looks for variables which can - be replaced by their expressions. Results are stored in TAB. */ - -static void -find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb) -{ - block_stmt_iterator bsi; - tree stmt, def, use; - stmt_ann_t ann; - int partition; - var_map map = tab->map; - value_expr_p p; - ssa_op_iter iter; - - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - { - stmt = bsi_stmt (bsi); - ann = stmt_ann (stmt); - - /* Determine if this stmt finishes an existing expression. */ - FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) - { - unsigned ver = SSA_NAME_VERSION (use); - - if (tab->version_info[ver]) - { - bool same_root_var = false; - ssa_op_iter iter2; - bitmap vars = tab->expr_vars[ver]; - - /* See if the root variables are the same. If they are, we - do not want to do the replacement to avoid problems with - code size, see PR tree-optimization/17549. */ - FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF) - { - if (bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def)))) - { - same_root_var = true; - break; - } - } - - /* Mark expression as replaceable unless stmt is volatile - or DEF sets the same root variable as STMT. */ - if (!ann->has_volatile_ops && !same_root_var) - mark_replaceable (tab, use); - else - finish_expr (tab, ver, false); - } - } - - /* Next, see if this stmt kills off an active expression. */ - FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) - { - partition = var_to_partition (map, def); - if (partition != NO_PARTITION && tab->partition_dep_list[partition]) - kill_expr (tab, partition, true); - } - - /* Now see if we are creating a new expression or not. */ - if (!ann->has_volatile_ops) - check_replaceable (tab, stmt); - - /* Free any unused dependency lists. */ - while ((p = tab->pending_dependence)) - { - tab->pending_dependence = p->next; - free_value_expr (tab, p); - } - - /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand. */ - if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) - kill_virtual_exprs (tab, true); - } -} - - -/* This function is the driver routine for replacement of temporary expressions - in the SSA->normal phase, operating on MAP. If there are replaceable - expressions, a table is returned which maps SSA versions to the - expressions they should be replaced with. A NULL_TREE indicates no - replacement should take place. If there are no replacements at all, - NULL is returned by the function, otherwise an expression vector indexed - by SSA_NAME version numbers. */ - -static tree * -find_replaceable_exprs (var_map map) -{ - basic_block bb; - unsigned i; - temp_expr_table_p table; - tree *ret; - - table = new_temp_expr_table (map); - FOR_EACH_BB (bb) - { - bitmap_iterator bi; - - find_replaceable_in_bb (table, bb); - EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi) - { - kill_expr (table, i, false); - } - } - - ret = free_temp_expr_table (table); - return ret; -} - - -/* Dump TER expression table EXPR to file F. */ - -static void -dump_replaceable_exprs (FILE *f, tree *expr) -{ - tree stmt, var; - int x; - fprintf (f, "\nReplacing Expressions\n"); - for (x = 0; x < (int)num_ssa_names + 1; x++) - if (expr[x]) - { - stmt = expr[x]; - var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF); - gcc_assert (var != NULL_TREE); - print_generic_expr (f, var, TDF_SLIM); - fprintf (f, " replace with --> "); - print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM); - fprintf (f, "\n"); - } - fprintf (f, "\n"); -} - - /* This function will rewrite the current program using the variable mapping found in MAP. If the replacement vector VALUES is provided, any occurrences of partitions with non-null entries in the vector will be |