diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/tree-ssa-copy.c')
| -rw-r--r-- | gcc-4.2.1-5666.3/gcc/tree-ssa-copy.c | 1162 |
1 files changed, 1162 insertions, 0 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/tree-ssa-copy.c b/gcc-4.2.1-5666.3/gcc/tree-ssa-copy.c new file mode 100644 index 000000000..f1b67b5bf --- /dev/null +++ b/gcc-4.2.1-5666.3/gcc/tree-ssa-copy.c @@ -0,0 +1,1162 @@ +/* Copy propagation and SSA_NAME replacement support routines. + Copyright (C) 2004, 2005 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to +the Free Software Foundation, 51 Franklin Street, Fifth Floor, +Boston, MA 02110-1301, USA. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "tree.h" +#include "flags.h" +#include "rtl.h" +#include "tm_p.h" +#include "ggc.h" +#include "basic-block.h" +#include "output.h" +#include "expr.h" +#include "function.h" +#include "diagnostic.h" +#include "timevar.h" +#include "tree-dump.h" +#include "tree-flow.h" +#include "tree-pass.h" +#include "tree-ssa-propagate.h" +#include "langhooks.h" + +/* This file implements the copy propagation pass and provides a + handful of interfaces for performing const/copy propagation and + simple expression replacement which keep variable annotations + up-to-date. + + We require that for any copy operation where the RHS and LHS have + a non-null memory tag the memory tag be the same. It is OK + for one or both of the memory tags to be NULL. + + We also require tracking if a variable is dereferenced in a load or + store operation. + + We enforce these requirements by having all copy propagation and + replacements of one SSA_NAME with a different SSA_NAME to use the + APIs defined in this file. */ + +/* Return true if we may propagate ORIG into DEST, false otherwise. */ + +bool +may_propagate_copy (tree dest, tree orig) +{ + tree type_d = TREE_TYPE (dest); + tree type_o = TREE_TYPE (orig); + + /* Do not copy between types for which we *do* need a conversion. */ + if (!tree_ssa_useless_type_conversion_1 (type_d, type_o)) + return false; + + /* FIXME. GIMPLE is allowing pointer assignments and comparisons of + pointers that have different alias sets. This means that these + pointers will have different memory tags associated to them. + + If we allow copy propagation in these cases, statements de-referencing + the new pointer will now have a reference to a different memory tag + with potentially incorrect SSA information. + + This was showing up in libjava/java/util/zip/ZipFile.java with code + like: + + struct java.io.BufferedInputStream *T.660; + struct java.io.BufferedInputStream *T.647; + struct java.io.InputStream *is; + struct java.io.InputStream *is.662; + [ ... ] + T.660 = T.647; + is = T.660; <-- This ought to be type-casted + is.662 = is; + + Also, f/name.c exposed a similar problem with a COND_EXPR predicate + that was causing DOM to generate and equivalence with two pointers of + alias-incompatible types: + + struct _ffename_space *n; + struct _ffename *ns; + [ ... ] + if (n == ns) + goto lab; + ... + lab: + return n; + + I think that GIMPLE should emit the appropriate type-casts. For the + time being, blocking copy-propagation in these cases is the safe thing + to do. */ + if (TREE_CODE (dest) == SSA_NAME + && TREE_CODE (orig) == SSA_NAME + && POINTER_TYPE_P (type_d) + && POINTER_TYPE_P (type_o)) + { + tree mt_dest = var_ann (SSA_NAME_VAR (dest))->symbol_mem_tag; + tree mt_orig = var_ann (SSA_NAME_VAR (orig))->symbol_mem_tag; + if (mt_dest && mt_orig && mt_dest != mt_orig) + return false; + else if (!lang_hooks.types_compatible_p (type_d, type_o)) + return false; + else if (get_alias_set (TREE_TYPE (type_d)) != + get_alias_set (TREE_TYPE (type_o))) + return false; + + /* Also verify flow-sensitive information is compatible. */ + if (SSA_NAME_PTR_INFO (orig) && SSA_NAME_PTR_INFO (dest)) + { + struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig); + struct ptr_info_def *dest_ptr_info = SSA_NAME_PTR_INFO (dest); + + if (orig_ptr_info->name_mem_tag + && dest_ptr_info->name_mem_tag + && orig_ptr_info->pt_vars + && dest_ptr_info->pt_vars + && !bitmap_intersect_p (dest_ptr_info->pt_vars, + orig_ptr_info->pt_vars)) + return false; + } + } + + /* If the destination is a SSA_NAME for a virtual operand, then we have + some special cases to handle. */ + if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest)) + { + /* If both operands are SSA_NAMEs referring to virtual operands, then + we can always propagate. */ + if (TREE_CODE (orig) == SSA_NAME + && !is_gimple_reg (orig)) + return true; + + /* We have a "copy" from something like a constant into a virtual + operand. Reject these. */ + return false; + } + + /* If ORIG flows in from an abnormal edge, it cannot be propagated. */ + if (TREE_CODE (orig) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)) + return false; + + /* If DEST is an SSA_NAME that flows from an abnormal edge, then it + cannot be replaced. */ + if (TREE_CODE (dest) == SSA_NAME + && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest)) + return false; + + /* Anything else is OK. */ + return true; +} + +/* Similarly, but we know that we're propagating into an ASM_EXPR. */ + +bool +may_propagate_copy_into_asm (tree dest) +{ + /* Hard register operands of asms are special. Do not bypass. */ + return !(TREE_CODE (dest) == SSA_NAME + && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL + && DECL_HARD_REGISTER (SSA_NAME_VAR (dest))); +} + + +/* Given two SSA_NAMEs pointers ORIG and NEW such that we are copy + propagating NEW into ORIG, consolidate aliasing information so that + they both share the same memory tags. */ + +void +merge_alias_info (tree orig, tree new) +{ + tree new_sym = SSA_NAME_VAR (new); + tree orig_sym = SSA_NAME_VAR (orig); + var_ann_t new_ann = var_ann (new_sym); + var_ann_t orig_ann = var_ann (orig_sym); + + gcc_assert (POINTER_TYPE_P (TREE_TYPE (orig))); + gcc_assert (POINTER_TYPE_P (TREE_TYPE (new))); + +#if defined ENABLE_CHECKING + gcc_assert (lang_hooks.types_compatible_p (TREE_TYPE (orig), + TREE_TYPE (new))); + + /* If the pointed-to alias sets are different, these two pointers + would never have the same memory tag. In this case, NEW should + not have been propagated into ORIG. */ + gcc_assert (get_alias_set (TREE_TYPE (TREE_TYPE (new_sym))) + == get_alias_set (TREE_TYPE (TREE_TYPE (orig_sym)))); +#endif + + /* Synchronize the symbol tags. If both pointers had a tag and they + are different, then something has gone wrong. Symbol tags can + always be merged because they are flow insensitive, all the SSA + names of the same base DECL share the same symbol tag. */ + if (new_ann->symbol_mem_tag == NULL_TREE) + new_ann->symbol_mem_tag = orig_ann->symbol_mem_tag; + else if (orig_ann->symbol_mem_tag == NULL_TREE) + orig_ann->symbol_mem_tag = new_ann->symbol_mem_tag; + else + gcc_assert (new_ann->symbol_mem_tag == orig_ann->symbol_mem_tag); + + /* Check that flow-sensitive information is compatible. Notice that + we may not merge flow-sensitive information here. This function + is called when propagating equivalences dictated by the IL, like + a copy operation P_i = Q_j, and from equivalences dictated by + control-flow, like if (P_i == Q_j). + + In the former case, P_i and Q_j are equivalent in every block + dominated by the assignment, so their flow-sensitive information + is always the same. However, in the latter case, the pointers + P_i and Q_j are only equivalent in one of the sub-graphs out of + the predicate, so their flow-sensitive information is not the + same in every block dominated by the predicate. + + Since we cannot distinguish one case from another in this + function, we can only make sure that if P_i and Q_j have + flow-sensitive information, they should be compatible. */ + if (SSA_NAME_PTR_INFO (orig) && SSA_NAME_PTR_INFO (new)) + { + struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig); + struct ptr_info_def *new_ptr_info = SSA_NAME_PTR_INFO (new); + + /* Note that pointer NEW and ORIG may actually have different + pointed-to variables (e.g., PR 18291 represented in + testsuite/gcc.c-torture/compile/pr18291.c). However, since + NEW is being copy-propagated into ORIG, it must always be + true that the pointed-to set for pointer NEW is the same, or + a subset, of the pointed-to set for pointer ORIG. If this + isn't the case, we shouldn't have been able to do the + propagation of NEW into ORIG. */ + if (orig_ptr_info->name_mem_tag + && new_ptr_info->name_mem_tag + && orig_ptr_info->pt_vars + && new_ptr_info->pt_vars) + gcc_assert (bitmap_intersect_p (new_ptr_info->pt_vars, + orig_ptr_info->pt_vars)); + } +} + + +/* Common code for propagate_value and replace_exp. + + Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the + replacement is done to propagate a value or not. */ + +static void +replace_exp_1 (use_operand_p op_p, tree val, + bool for_propagation ATTRIBUTE_UNUSED) +{ + tree op = USE_FROM_PTR (op_p); + +#if defined ENABLE_CHECKING + gcc_assert (!(for_propagation + && TREE_CODE (op) == SSA_NAME + && TREE_CODE (val) == SSA_NAME + && !may_propagate_copy (op, val))); +#endif + + if (TREE_CODE (val) == SSA_NAME) + { + if (TREE_CODE (op) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (op))) + merge_alias_info (op, val); + SET_USE (op_p, val); + } + else + SET_USE (op_p, unsave_expr_now (val)); +} + + +/* Propagate the value VAL (assumed to be a constant or another SSA_NAME) + into the operand pointed to by OP_P. + + Use this version for const/copy propagation as it will perform additional + checks to ensure validity of the const/copy propagation. */ + +void +propagate_value (use_operand_p op_p, tree val) +{ + replace_exp_1 (op_p, val, true); +} + + +/* Propagate the value VAL (assumed to be a constant or another SSA_NAME) + into the tree pointed to by OP_P. + + Use this version for const/copy propagation when SSA operands are not + available. It will perform the additional checks to ensure validity of + the const/copy propagation, but will not update any operand information. + Be sure to mark the stmt as modified. */ + +void +propagate_tree_value (tree *op_p, tree val) +{ +#if defined ENABLE_CHECKING + gcc_assert (!(TREE_CODE (val) == SSA_NAME + && TREE_CODE (*op_p) == SSA_NAME + && !may_propagate_copy (*op_p, val))); +#endif + + if (TREE_CODE (val) == SSA_NAME) + { + if (TREE_CODE (*op_p) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (*op_p))) + merge_alias_info (*op_p, val); + *op_p = val; + } + else + *op_p = unsave_expr_now (val); +} + + +/* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME). + + Use this version when not const/copy propagating values. For example, + PRE uses this version when building expressions as they would appear + in specific blocks taking into account actions of PHI nodes. */ + +void +replace_exp (use_operand_p op_p, tree val) +{ + replace_exp_1 (op_p, val, false); +} + + +/*--------------------------------------------------------------------------- + Copy propagation +---------------------------------------------------------------------------*/ +/* During propagation, we keep chains of variables that are copies of + one another. If variable X_i is a copy of X_j and X_j is a copy of + X_k, COPY_OF will contain: + + COPY_OF[i].VALUE = X_j + COPY_OF[j].VALUE = X_k + COPY_OF[k].VALUE = X_k + + After propagation, the copy-of value for each variable X_i is + converted into the final value by walking the copy-of chains and + updating COPY_OF[i].VALUE to be the last element of the chain. */ +static prop_value_t *copy_of; + +/* Used in set_copy_of_val to determine if the last link of a copy-of + chain has changed. */ +static tree *cached_last_copy_of; + +/* True if we are doing copy propagation on loads and stores. */ +static bool do_store_copy_prop; + + +/* Return true if this statement may generate a useful copy. */ + +static bool +stmt_may_generate_copy (tree stmt) +{ + tree lhs, rhs; + stmt_ann_t ann; + + if (TREE_CODE (stmt) == PHI_NODE) + return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (stmt)); + + if (TREE_CODE (stmt) != MODIFY_EXPR) + return false; + + lhs = TREE_OPERAND (stmt, 0); + rhs = TREE_OPERAND (stmt, 1); + ann = stmt_ann (stmt); + + /* If the statement has volatile operands, it won't generate a + useful copy. */ + if (ann->has_volatile_ops) + return false; + + /* If we are not doing store copy-prop, statements with loads and/or + stores will never generate a useful copy. */ + if (!do_store_copy_prop + && !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) + return false; + + /* Otherwise, the only statements that generate useful copies are + assignments whose RHS is just an SSA name that doesn't flow + through abnormal edges. */ + return (do_store_copy_prop + && TREE_CODE (lhs) == SSA_NAME) + || (TREE_CODE (rhs) == SSA_NAME + && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)); +} + + +/* Return the copy-of value for VAR. */ + +static inline prop_value_t * +get_copy_of_val (tree var) +{ + prop_value_t *val = ©_of[SSA_NAME_VERSION (var)]; + + if (val->value == NULL_TREE + && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var))) + { + /* If the variable will never generate a useful copy relation, + make it its own copy. */ + val->value = var; + val->mem_ref = NULL_TREE; + } + + return val; +} + + +/* Return last link in the copy-of chain for VAR. */ + +static tree +get_last_copy_of (tree var) +{ + tree last; + int i; + + /* Traverse COPY_OF starting at VAR until we get to the last + link in the chain. Since it is possible to have cycles in PHI + nodes, the copy-of chain may also contain cycles. + + To avoid infinite loops and to avoid traversing lengthy copy-of + chains, we artificially limit the maximum number of chains we are + willing to traverse. + + The value 5 was taken from a compiler and runtime library + bootstrap and a mixture of C and C++ code from various sources. + More than 82% of all copy-of chains were shorter than 5 links. */ +#define LIMIT 5 + + last = var; + for (i = 0; i < LIMIT; i++) + { + tree copy = copy_of[SSA_NAME_VERSION (last)].value; + if (copy == NULL_TREE || copy == last) + break; + last = copy; + } + + /* If we have reached the limit, then we are either in a copy-of + cycle or the copy-of chain is too long. In this case, just + return VAR so that it is not considered a copy of anything. */ + return (i < LIMIT ? last : var); +} + + +/* Set FIRST to be the first variable in the copy-of chain for DEST. + If DEST's copy-of value or its copy-of chain has changed, return + true. + + MEM_REF is the memory reference where FIRST is stored. This is + used when DEST is a non-register and we are copy propagating loads + and stores. */ + +static inline bool +set_copy_of_val (tree dest, tree first, tree mem_ref) +{ + unsigned int dest_ver = SSA_NAME_VERSION (dest); + tree old_first, old_last, new_last; + + /* Set FIRST to be the first link in COPY_OF[DEST]. If that + changed, return true. */ + old_first = copy_of[dest_ver].value; + copy_of[dest_ver].value = first; + copy_of[dest_ver].mem_ref = mem_ref; + + if (old_first != first) + return true; + + /* If FIRST and OLD_FIRST are the same, we need to check whether the + copy-of chain starting at FIRST ends in a different variable. If + the copy-of chain starting at FIRST ends up in a different + variable than the last cached value we had for DEST, then return + true because DEST is now a copy of a different variable. + + This test is necessary because even though the first link in the + copy-of chain may not have changed, if any of the variables in + the copy-of chain changed its final value, DEST will now be the + copy of a different variable, so we have to do another round of + propagation for everything that depends on DEST. */ + old_last = cached_last_copy_of[dest_ver]; + new_last = get_last_copy_of (dest); + cached_last_copy_of[dest_ver] = new_last; + + return (old_last != new_last); +} + + +/* Dump the copy-of value for variable VAR to FILE. */ + +static void +dump_copy_of (FILE *file, tree var) +{ + tree val; + sbitmap visited; + + print_generic_expr (file, var, dump_flags); + + if (TREE_CODE (var) != SSA_NAME) + return; + + visited = sbitmap_alloc (num_ssa_names); + sbitmap_zero (visited); + SET_BIT (visited, SSA_NAME_VERSION (var)); + + fprintf (file, " copy-of chain: "); + + val = var; + print_generic_expr (file, val, 0); + fprintf (file, " "); + while (copy_of[SSA_NAME_VERSION (val)].value) + { + fprintf (file, "-> "); + val = copy_of[SSA_NAME_VERSION (val)].value; + print_generic_expr (file, val, 0); + fprintf (file, " "); + if (TEST_BIT (visited, SSA_NAME_VERSION (val))) + break; + SET_BIT (visited, SSA_NAME_VERSION (val)); + } + + val = get_copy_of_val (var)->value; + if (val == NULL_TREE) + fprintf (file, "[UNDEFINED]"); + else if (val != var) + fprintf (file, "[COPY]"); + else + fprintf (file, "[NOT A COPY]"); + + sbitmap_free (visited); +} + + +/* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS + value and store the LHS into *RESULT_P. If STMT generates more + than one name (i.e., STMT is an aliased store), it is enough to + store the first name in the V_MAY_DEF list into *RESULT_P. After + all, the names generated will be VUSEd in the same statements. */ + +static enum ssa_prop_result +copy_prop_visit_assignment (tree stmt, tree *result_p) +{ + tree lhs, rhs; + prop_value_t *rhs_val; + + lhs = TREE_OPERAND (stmt, 0); + rhs = TREE_OPERAND (stmt, 1); + + gcc_assert (TREE_CODE (rhs) == SSA_NAME); + + rhs_val = get_copy_of_val (rhs); + + if (TREE_CODE (lhs) == SSA_NAME) + { + /* Straight copy between two SSA names. First, make sure that + we can propagate the RHS into uses of LHS. */ + if (!may_propagate_copy (lhs, rhs)) + return SSA_PROP_VARYING; + + /* Notice that in the case of assignments, we make the LHS be a + copy of RHS's value, not of RHS itself. This avoids keeping + unnecessary copy-of chains (assignments cannot be in a cycle + like PHI nodes), speeding up the propagation process. + This is different from what we do in copy_prop_visit_phi_node. + In those cases, we are interested in the copy-of chains. */ + *result_p = lhs; + if (set_copy_of_val (*result_p, rhs_val->value, rhs_val->mem_ref)) + return SSA_PROP_INTERESTING; + else + return SSA_PROP_NOT_INTERESTING; + } + else if (stmt_makes_single_store (stmt)) + { + /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands + to be a copy of RHS. */ + ssa_op_iter i; + tree vdef; + bool changed; + + /* This should only be executed when doing store copy-prop. */ + gcc_assert (do_store_copy_prop); + + /* Set the value of every VDEF to RHS_VAL. */ + changed = false; + FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS) + changed |= set_copy_of_val (vdef, rhs_val->value, lhs); + + /* Note that for propagation purposes, we are only interested in + visiting statements that load the exact same memory reference + stored here. Those statements will have the exact same list + of virtual uses, so it is enough to set the output of this + statement to be its first virtual definition. */ + *result_p = first_vdef (stmt); + + if (changed) + return SSA_PROP_INTERESTING; + else + return SSA_PROP_NOT_INTERESTING; + } + + + return SSA_PROP_VARYING; +} + + +/* Visit the COND_EXPR STMT. Return SSA_PROP_INTERESTING + if it can determine which edge will be taken. Otherwise, return + SSA_PROP_VARYING. */ + +static enum ssa_prop_result +copy_prop_visit_cond_stmt (tree stmt, edge *taken_edge_p) +{ + enum ssa_prop_result retval; + tree cond; + + cond = COND_EXPR_COND (stmt); + retval = SSA_PROP_VARYING; + + /* The only conditionals that we may be able to compute statically + are predicates involving two SSA_NAMEs. */ + if (COMPARISON_CLASS_P (cond) + && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME + && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME) + { + tree op0 = get_last_copy_of (TREE_OPERAND (cond, 0)); + tree op1 = get_last_copy_of (TREE_OPERAND (cond, 1)); + + /* See if we can determine the predicate's value. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Trying to determine truth value of "); + fprintf (dump_file, "predicate "); + print_generic_stmt (dump_file, cond, 0); + } + + /* We can fold COND and get a useful result only when we have + the same SSA_NAME on both sides of a comparison operator. */ + if (op0 == op1) + { + tree folded_cond = fold_binary (TREE_CODE (cond), boolean_type_node, + op0, op1); + if (folded_cond) + { + basic_block bb = bb_for_stmt (stmt); + *taken_edge_p = find_taken_edge (bb, folded_cond); + if (*taken_edge_p) + retval = SSA_PROP_INTERESTING; + } + } + } + + if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p) + fprintf (dump_file, "\nConditional will always take edge %d->%d\n", + (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index); + + return retval; +} + + +/* Evaluate statement STMT. If the statement produces a new output + value, return SSA_PROP_INTERESTING and store the SSA_NAME holding + the new value in *RESULT_P. + + If STMT is a conditional branch and we can determine its truth + value, set *TAKEN_EDGE_P accordingly. + + If the new value produced by STMT is varying, return + SSA_PROP_VARYING. */ + +static enum ssa_prop_result +copy_prop_visit_stmt (tree stmt, edge *taken_edge_p, tree *result_p) +{ + enum ssa_prop_result retval; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\nVisiting statement:\n"); + print_generic_stmt (dump_file, stmt, dump_flags); + fprintf (dump_file, "\n"); + } + + if (TREE_CODE (stmt) == MODIFY_EXPR + && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME + && (do_store_copy_prop + || TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)) + { + /* If the statement is a copy assignment, evaluate its RHS to + see if the lattice value of its output has changed. */ + retval = copy_prop_visit_assignment (stmt, result_p); + } + else if (TREE_CODE (stmt) == MODIFY_EXPR + && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME + && do_store_copy_prop + && stmt_makes_single_load (stmt)) + { + /* If the statement is a copy assignment with a memory load + on the RHS, see if we know the value of this load and + update the lattice accordingly. */ + prop_value_t *val = get_value_loaded_by (stmt, copy_of); + if (val + && val->mem_ref + && is_gimple_reg (val->value) + && operand_equal_p (val->mem_ref, TREE_OPERAND (stmt, 1), 0)) + { + bool changed; + changed = set_copy_of_val (TREE_OPERAND (stmt, 0), + val->value, val->mem_ref); + if (changed) + { + *result_p = TREE_OPERAND (stmt, 0); + retval = SSA_PROP_INTERESTING; + } + else + retval = SSA_PROP_NOT_INTERESTING; + } + else + retval = SSA_PROP_VARYING; + } + else if (TREE_CODE (stmt) == COND_EXPR) + { + /* See if we can determine which edge goes out of a conditional + jump. */ + retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p); + } + else + retval = SSA_PROP_VARYING; + + if (retval == SSA_PROP_VARYING) + { + tree def; + ssa_op_iter i; + + /* Any other kind of statement is not interesting for constant + propagation and, therefore, not worth simulating. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "No interesting values produced.\n"); + + /* The assignment is not a copy operation. Don't visit this + statement again and mark all the definitions in the statement + to be copies of nothing. */ + FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS) + set_copy_of_val (def, def, NULL_TREE); + } + + return retval; +} + + +/* Visit PHI node PHI. If all the arguments produce the same value, + set it to be the value of the LHS of PHI. */ + +static enum ssa_prop_result +copy_prop_visit_phi_node (tree phi) +{ + enum ssa_prop_result retval; + int i; + tree lhs; + prop_value_t phi_val = { 0, NULL_TREE, NULL_TREE }; + + lhs = PHI_RESULT (phi); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\nVisiting PHI node: "); + print_generic_expr (dump_file, phi, dump_flags); + fprintf (dump_file, "\n\n"); + } + + for (i = 0; i < PHI_NUM_ARGS (phi); i++) + { + prop_value_t *arg_val; + tree arg = PHI_ARG_DEF (phi, i); + edge e = PHI_ARG_EDGE (phi, i); + + /* We don't care about values flowing through non-executable + edges. */ + if (!(e->flags & EDGE_EXECUTABLE)) + continue; + + /* Constants in the argument list never generate a useful copy. + Similarly, names that flow through abnormal edges cannot be + used to derive copies. */ + if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg)) + { + phi_val.value = lhs; + break; + } + + /* Avoid copy propagation from an inner into an outer loop. + Otherwise, this may move loop variant variables outside of + their loops and prevent coalescing opportunities. If the + value was loop invariant, it will be hoisted by LICM and + exposed for copy propagation. */ + if (loop_depth_of_name (arg) > loop_depth_of_name (lhs)) + { + phi_val.value = lhs; + break; + } + + /* If the LHS appears in the argument list, ignore it. It is + irrelevant as a copy. */ + if (arg == lhs || get_last_copy_of (arg) == lhs) + continue; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\tArgument #%d: ", i); + dump_copy_of (dump_file, arg); + fprintf (dump_file, "\n"); + } + + arg_val = get_copy_of_val (arg); + + /* If the LHS didn't have a value yet, make it a copy of the + first argument we find. Notice that while we make the LHS be + a copy of the argument itself, we take the memory reference + from the argument's value so that we can compare it to the + memory reference of all the other arguments. */ + if (phi_val.value == NULL_TREE) + { + phi_val.value = arg; + phi_val.mem_ref = arg_val->mem_ref; + continue; + } + + /* If PHI_VAL and ARG don't have a common copy-of chain, then + this PHI node cannot be a copy operation. Also, if we are + copy propagating stores and these two arguments came from + different memory references, they cannot be considered + copies. */ + if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg) + || (do_store_copy_prop + && phi_val.mem_ref + && arg_val->mem_ref + && simple_cst_equal (phi_val.mem_ref, arg_val->mem_ref) != 1)) + { + phi_val.value = lhs; + break; + } + } + + if (phi_val.value && set_copy_of_val (lhs, phi_val.value, phi_val.mem_ref)) + retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING; + else + retval = SSA_PROP_NOT_INTERESTING; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\nPHI node "); + dump_copy_of (dump_file, lhs); + fprintf (dump_file, "\nTelling the propagator to "); + if (retval == SSA_PROP_INTERESTING) + fprintf (dump_file, "add SSA edges out of this PHI and continue."); + else if (retval == SSA_PROP_VARYING) + fprintf (dump_file, "add SSA edges out of this PHI and never visit again."); + else + fprintf (dump_file, "do nothing with SSA edges and keep iterating."); + fprintf (dump_file, "\n\n"); + } + + return retval; +} + + +/* Initialize structures used for copy propagation. PHIS_ONLY is true + if we should only consider PHI nodes as generating copy propagation + opportunities. */ + +static void +init_copy_prop (void) +{ + basic_block bb; + + copy_of = XNEWVEC (prop_value_t, num_ssa_names); + memset (copy_of, 0, num_ssa_names * sizeof (*copy_of)); + + cached_last_copy_of = XNEWVEC (tree, num_ssa_names); + memset (cached_last_copy_of, 0, num_ssa_names * sizeof (*cached_last_copy_of)); + + FOR_EACH_BB (bb) + { + block_stmt_iterator si; + tree phi, def; + int depth = bb->loop_depth; + + for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) + { + tree stmt = bsi_stmt (si); + ssa_op_iter iter; + + /* The only statements that we care about are those that may + generate useful copies. We also need to mark conditional + jumps so that their outgoing edges are added to the work + lists of the propagator. + + Avoid copy propagation from an inner into an outer loop. + Otherwise, this may move loop variant variables outside of + their loops and prevent coalescing opportunities. If the + value was loop invariant, it will be hoisted by LICM and + exposed for copy propagation. */ + if (stmt_ends_bb_p (stmt)) + DONT_SIMULATE_AGAIN (stmt) = false; + else if (stmt_may_generate_copy (stmt) + && loop_depth_of_name (TREE_OPERAND (stmt, 1)) <= depth) + DONT_SIMULATE_AGAIN (stmt) = false; + else + DONT_SIMULATE_AGAIN (stmt) = true; + + /* Mark all the outputs of this statement as not being + the copy of anything. */ + FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) + if (DONT_SIMULATE_AGAIN (stmt)) + set_copy_of_val (def, def, NULL_TREE); + else + cached_last_copy_of[SSA_NAME_VERSION (def)] = def; + } + + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + { + def = PHI_RESULT (phi); + if (!do_store_copy_prop && !is_gimple_reg (def)) + DONT_SIMULATE_AGAIN (phi) = true; + else + DONT_SIMULATE_AGAIN (phi) = false; + + if (DONT_SIMULATE_AGAIN (phi)) + set_copy_of_val (def, def, NULL_TREE); + else + cached_last_copy_of[SSA_NAME_VERSION (def)] = def; + } + } +} + + +/* Deallocate memory used in copy propagation and do final + substitution. */ + +static void +fini_copy_prop (void) +{ + size_t i; + prop_value_t *tmp; + + /* Set the final copy-of value for each variable by traversing the + copy-of chains. */ + tmp = XNEWVEC (prop_value_t, num_ssa_names); + memset (tmp, 0, num_ssa_names * sizeof (*tmp)); + for (i = 1; i < num_ssa_names; i++) + { + tree var = ssa_name (i); + if (var && copy_of[i].value && copy_of[i].value != var) + tmp[i].value = get_last_copy_of (var); + } + + substitute_and_fold (tmp, false); + + free (cached_last_copy_of); + free (copy_of); + free (tmp); +} + + +/* Main entry point to the copy propagator. + + PHIS_ONLY is true if we should only consider PHI nodes as generating + copy propagation opportunities. + + The algorithm propagates the value COPY-OF using ssa_propagate. For + every variable X_i, COPY-OF(X_i) indicates which variable is X_i created + from. The following example shows how the algorithm proceeds at a + high level: + + 1 a_24 = x_1 + 2 a_2 = PHI <a_24, x_1> + 3 a_5 = PHI <a_2> + 4 x_1 = PHI <x_298, a_5, a_2> + + The end result should be that a_2, a_5, a_24 and x_1 are a copy of + x_298. Propagation proceeds as follows. + + Visit #1: a_24 is copy-of x_1. Value changed. + Visit #2: a_2 is copy-of x_1. Value changed. + Visit #3: a_5 is copy-of x_1. Value changed. + Visit #4: x_1 is copy-of x_298. Value changed. + Visit #1: a_24 is copy-of x_298. Value changed. + Visit #2: a_2 is copy-of x_298. Value changed. + Visit #3: a_5 is copy-of x_298. Value changed. + Visit #4: x_1 is copy-of x_298. Stable state reached. + + When visiting PHI nodes, we only consider arguments that flow + through edges marked executable by the propagation engine. So, + when visiting statement #2 for the first time, we will only look at + the first argument (a_24) and optimistically assume that its value + is the copy of a_24 (x_1). + + The problem with this approach is that it may fail to discover copy + relations in PHI cycles. Instead of propagating copy-of + values, we actually propagate copy-of chains. For instance: + + A_3 = B_1; + C_9 = A_3; + D_4 = C_9; + X_i = D_4; + + In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }. + Obviously, we are only really interested in the last value of the + chain, however the propagator needs to access the copy-of chain + when visiting PHI nodes. + + To represent the copy-of chain, we use the array COPY_CHAINS, which + holds the first link in the copy-of chain for every variable. + If variable X_i is a copy of X_j, which in turn is a copy of X_k, + the array will contain: + + COPY_CHAINS[i] = X_j + COPY_CHAINS[j] = X_k + COPY_CHAINS[k] = X_k + + Keeping copy-of chains instead of copy-of values directly becomes + important when visiting PHI nodes. Suppose that we had the + following PHI cycle, such that x_52 is already considered a copy of + x_53: + + 1 x_54 = PHI <x_53, x_52> + 2 x_53 = PHI <x_898, x_54> + + Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53) + Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53, + so it is considered irrelevant + as a copy). + Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and + x_52 is a copy of x_53, so + they don't match) + Visit #2: x_53 is copy-of nothing + + This problem is avoided by keeping a chain of copies, instead of + the final copy-of value. Propagation will now only keep the first + element of a variable's copy-of chain. When visiting PHI nodes, + arguments are considered equal if their copy-of chains end in the + same variable. So, as long as their copy-of chains overlap, we + know that they will be a copy of the same variable, regardless of + which variable that may be). + + Propagation would then proceed as follows (the notation a -> b + means that a is a copy-of b): + + Visit #1: x_54 = PHI <x_53, x_52> + x_53 -> x_53 + x_52 -> x_53 + Result: x_54 -> x_53. Value changed. Add SSA edges. + + Visit #1: x_53 = PHI <x_898, x_54> + x_898 -> x_898 + x_54 -> x_53 + Result: x_53 -> x_898. Value changed. Add SSA edges. + + Visit #2: x_54 = PHI <x_53, x_52> + x_53 -> x_898 + x_52 -> x_53 -> x_898 + Result: x_54 -> x_898. Value changed. Add SSA edges. + + Visit #2: x_53 = PHI <x_898, x_54> + x_898 -> x_898 + x_54 -> x_898 + Result: x_53 -> x_898. Value didn't change. Stable state + + Once the propagator stabilizes, we end up with the desired result + x_53 and x_54 are both copies of x_898. */ + +static void +execute_copy_prop (bool store_copy_prop) +{ + do_store_copy_prop = store_copy_prop; + init_copy_prop (); + ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node); + fini_copy_prop (); +} + + +static bool +gate_copy_prop (void) +{ + return flag_tree_copy_prop != 0; +} + +static unsigned int +do_copy_prop (void) +{ + execute_copy_prop (false); + return 0; +} + +struct tree_opt_pass pass_copy_prop = +{ + "copyprop", /* name */ + gate_copy_prop, /* gate */ + do_copy_prop, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_COPY_PROP, /* tv_id */ + PROP_ssa | PROP_alias | PROP_cfg, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_cleanup_cfg + | TODO_dump_func + | TODO_ggc_collect + | TODO_verify_ssa + | TODO_update_ssa, /* todo_flags_finish */ + 0 /* letter */ +}; + +static bool +gate_store_copy_prop (void) +{ + /* STORE-COPY-PROP is enabled only with -ftree-store-copy-prop, but + when -fno-tree-store-copy-prop is specified, we should run + regular COPY-PROP. That's why the pass is enabled with either + flag. */ + return flag_tree_store_copy_prop != 0 || flag_tree_copy_prop != 0; +} + +static unsigned int +store_copy_prop (void) +{ + /* If STORE-COPY-PROP is not enabled, we just run regular COPY-PROP. */ + execute_copy_prop (flag_tree_store_copy_prop != 0); + return 0; +} + +struct tree_opt_pass pass_store_copy_prop = +{ + "store_copyprop", /* name */ + gate_store_copy_prop, /* gate */ + store_copy_prop, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_STORE_COPY_PROP, /* tv_id */ + PROP_ssa | PROP_alias | PROP_cfg, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func + | TODO_cleanup_cfg + | TODO_ggc_collect + | TODO_verify_ssa + | TODO_update_ssa, /* todo_flags_finish */ + 0 /* letter */ +}; |