X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-scalar-evolution.c;h=cc80794c5d9cab5d0f42ca51b0cdb033ca377c62;hb=a83c17ce39a912f8076f4a4af63b19a734285407;hp=48da0d25575bb8fa30e19fb19162407ff9055c59;hpb=5c9dae644b7021a01fd40612afb035b71fa4ec93;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 48da0d25575..cc80794c5d9 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -1,12 +1,12 @@ /* Scalar evolution detector. - Copyright (C) 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc. Contributed by Sebastian Pop 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 +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -15,9 +15,8 @@ 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, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ /* Description: @@ -48,7 +47,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA Given a scalar variable to be analyzed, follow the SSA edge to its definition: - - When the definition is a MODIFY_EXPR: if the right hand side + - When the definition is a GIMPLE_MODIFY_STMT: if the right hand side (RHS) of the definition cannot be statically analyzed, the answer of the analyzer is: "don't know". Otherwise, for all the variables that are not yet analyzed in the @@ -235,9 +234,9 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "system.h" #include "coretypes.h" #include "tm.h" -#include "errors.h" #include "ggc.h" #include "tree.h" +#include "real.h" /* These RTL headers are needed for basic-block.h. */ #include "rtl.h" @@ -251,14 +250,14 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "tree-scalar-evolution.h" #include "tree-pass.h" #include "flags.h" +#include "params.h" static tree analyze_scalar_evolution_1 (struct loop *, tree, tree); -static tree resolve_mixers (struct loop *, tree); /* The cached information about a ssa name VAR, claiming that inside LOOP, the value of VAR can be expressed as CHREC. */ -struct scev_info_str +struct scev_info_str GTY(()) { tree var; tree chrec; @@ -285,7 +284,7 @@ tree chrec_known; static bitmap already_instantiated; -static htab_t scalar_evolution_info; +static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info; /* Constructs a new SCEV_INFO_STR structure. */ @@ -295,7 +294,7 @@ new_scev_info_str (tree var) { struct scev_info_str *res; - res = xmalloc (sizeof (struct scev_info_str)); + res = GGC_NEW (struct scev_info_str); res->var = var; res->chrec = chrec_not_analyzed_yet; @@ -307,7 +306,7 @@ new_scev_info_str (tree var) static hashval_t hash_scev_info (const void *elt) { - return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var); + return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var); } /* Compares database elements E1 and E2. */ @@ -315,8 +314,8 @@ hash_scev_info (const void *elt) static int eq_scev_info (const void *e1, const void *e2) { - const struct scev_info_str *elt1 = e1; - const struct scev_info_str *elt2 = e2; + const struct scev_info_str *elt1 = (const struct scev_info_str *) e1; + const struct scev_info_str *elt2 = (const struct scev_info_str *) e2; return elt1->var == elt2->var; } @@ -326,12 +325,12 @@ eq_scev_info (const void *e1, const void *e2) static void del_scev_info (void *e) { - free (e); + ggc_free (e); } /* Get the index corresponding to VAR in the current LOOP. If it's the first time we ask for this VAR, then we return - chrec_not_analysed_yet for this VAR and return its index. */ + chrec_not_analyzed_yet for this VAR and return its index. */ static tree * find_var_scev_info (tree var) @@ -345,44 +344,19 @@ find_var_scev_info (tree var) if (!*slot) *slot = new_scev_info_str (var); - res = *slot; + res = (struct scev_info_str *) *slot; return &res->chrec; } -/* Tries to express CHREC in wider type TYPE. */ - -tree -count_ev_in_wider_type (tree type, tree chrec) -{ - tree base, step; - struct loop *loop; - - if (!evolution_function_is_affine_p (chrec)) - return fold_convert (type, chrec); - - base = CHREC_LEFT (chrec); - step = CHREC_RIGHT (chrec); - loop = current_loops->parray[CHREC_VARIABLE (chrec)]; - - /* TODO -- if we knew the statement at that the conversion occurs, - we could pass it to can_count_iv_in_wider_type and get a better - result. */ - step = can_count_iv_in_wider_type (loop, type, base, step, NULL_TREE); - if (!step) - return fold_convert (type, chrec); - base = chrec_convert (type, base); - - return build_polynomial_chrec (CHREC_VARIABLE (chrec), - base, step); -} - /* Return true when CHREC contains symbolic names defined in LOOP_NB. */ bool -chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb) +chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb) { + int i, n; + if (chrec == NULL_TREE) return false; @@ -401,7 +375,7 @@ chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb) { tree def = SSA_NAME_DEF_STMT (chrec); struct loop *def_loop = loop_containing_stmt (def); - struct loop *loop = current_loops->parray[loop_nb]; + struct loop *loop = get_loop (loop_nb); if (def_loop == NULL) return false; @@ -412,26 +386,12 @@ chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb) return false; } - switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) - { - case 3: - if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2), - loop_nb)) - return true; - - case 2: - if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1), - loop_nb)) - return true; - - case 1: - if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0), - loop_nb)) - return true; - - default: - return false; - } + n = TREE_OPERAND_LENGTH (chrec); + for (i = 0; i < n; i++) + if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i), + loop_nb)) + return true; + return false; } /* Return true when PHI is a loop-phi-node. */ @@ -491,11 +451,12 @@ compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC) { - if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num) + struct loop *inner_loop = get_chrec_loop (evolution_fn); + + if (inner_loop == loop + || flow_loop_nested_p (loop, inner_loop)) { - struct loop *inner_loop = - current_loops->parray[CHREC_VARIABLE (evolution_fn)]; - tree nb_iter = number_of_iterations_in_loop (inner_loop); + tree nb_iter = number_of_latch_executions (inner_loop); if (nb_iter == chrec_dont_know) return chrec_dont_know; @@ -503,13 +464,6 @@ compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) { tree res; - /* Number of iterations is off by one (the ssa name we - analyze must be defined before the exit). */ - nb_iter = chrec_fold_minus (chrec_type (nb_iter), - nb_iter, - fold_convert (chrec_type (nb_iter), - integer_one_node)); - /* evolution_fn is the evolution function in LOOP. Get its value in the nb_iter-th iteration. */ res = chrec_apply (inner_loop->num, evolution_fn, nb_iter); @@ -537,10 +491,8 @@ compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) bool chrec_is_positive (tree chrec, bool *value) { - bool value0, value1; - bool value2; - tree end_value; - tree nb_iter; + bool value0, value1, value2; + tree end_value, nb_iter; switch (TREE_CODE (chrec)) { @@ -563,23 +515,15 @@ chrec_is_positive (tree chrec, bool *value) if (!evolution_function_is_affine_p (chrec)) return false; - nb_iter = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec)]); - + nb_iter = number_of_latch_executions (get_chrec_loop (chrec)); if (chrec_contains_undetermined (nb_iter)) return false; - nb_iter = chrec_fold_minus - (chrec_type (nb_iter), nb_iter, - build_int_cst (chrec_type (nb_iter), 1)); - #if 0 /* TODO -- If the test is after the exit, we may decrease the number of iterations by one. */ if (after_exit) - nb_iter = chrec_fold_minus - (chrec_type (nb_iter), nb_iter, - build_int_cst (chrec_type (nb_iter), 1)); + nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1)); #endif end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter); @@ -656,6 +600,7 @@ get_scalar_evolution (tree scalar) break; case REAL_CST: + case FIXED_CST: case INTEGER_CST: res = scalar; break; @@ -686,25 +631,31 @@ get_scalar_evolution (tree scalar) part for this loop. */ static tree -add_to_evolution_1 (unsigned loop_nb, - tree chrec_before, - tree to_add) +add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, + tree at_stmt) { + tree type, left, right; + struct loop *loop = get_loop (loop_nb), *chloop; + switch (TREE_CODE (chrec_before)) { case POLYNOMIAL_CHREC: - if (CHREC_VARIABLE (chrec_before) <= loop_nb) + chloop = get_chrec_loop (chrec_before); + if (chloop == loop + || flow_loop_nested_p (chloop, loop)) { unsigned var; - tree left, right; - tree type = chrec_type (chrec_before); + + type = chrec_type (chrec_before); /* When there is no evolution part in this loop, build it. */ - if (CHREC_VARIABLE (chrec_before) < loop_nb) + if (chloop != loop) { var = loop_nb; left = chrec_before; - right = build_int_cst (type, 0); + right = SCALAR_FLOAT_TYPE_P (type) + ? build_real (type, dconst0) + : build_int_cst (type, 0); } else { @@ -713,21 +664,32 @@ add_to_evolution_1 (unsigned loop_nb, right = CHREC_RIGHT (chrec_before); } - return build_polynomial_chrec - (var, left, chrec_fold_plus (type, right, to_add)); + to_add = chrec_convert (type, to_add, at_stmt); + right = chrec_convert_rhs (type, right, at_stmt); + right = chrec_fold_plus (chrec_type (right), right, to_add); + return build_polynomial_chrec (var, left, right); } else - /* Search the evolution in LOOP_NB. */ - return build_polynomial_chrec - (CHREC_VARIABLE (chrec_before), - add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add), - CHREC_RIGHT (chrec_before)); + { + gcc_assert (flow_loop_nested_p (loop, chloop)); + + /* Search the evolution in LOOP_NB. */ + left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), + to_add, at_stmt); + right = CHREC_RIGHT (chrec_before); + right = chrec_convert_rhs (chrec_type (left), right, at_stmt); + return build_polynomial_chrec (CHREC_VARIABLE (chrec_before), + left, right); + } default: /* These nodes do not depend on a loop. */ if (chrec_before == chrec_dont_know) return chrec_dont_know; - return build_polynomial_chrec (loop_nb, chrec_before, to_add); + + left = chrec_before; + right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt); + return build_polynomial_chrec (loop_nb, left, right); } } @@ -866,10 +828,8 @@ add_to_evolution_1 (unsigned loop_nb, */ static tree -add_to_evolution (unsigned loop_nb, - tree chrec_before, - enum tree_code code, - tree to_add) +add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, + tree to_add, tree at_stmt) { tree type = chrec_type (to_add); tree res = NULL_TREE; @@ -895,10 +855,11 @@ add_to_evolution (unsigned loop_nb, } if (code == MINUS_EXPR) - to_add = chrec_fold_multiply (type, to_add, - fold_convert (type, integer_minus_one_node)); + to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type) + ? build_real (type, dconstm1) + : build_int_cst_type (type, -1)); - res = add_to_evolution_1 (loop_nb, chrec_before, to_add); + res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -916,15 +877,6 @@ static inline tree set_nb_iterations_in_loop (struct loop *loop, tree res) { - res = chrec_fold_plus (chrec_type (res), res, integer_one_node); - /* FIXME HWI: However we want to store one iteration less than the - count of the loop in order to be compatible with the other - nb_iter computations in loop-iv. This also allows the - representation of nb_iters that are equal to MAX_INT. */ - if ((TREE_CODE (res) == INTEGER_CST && TREE_INT_CST_LOW (res) == 0) - || TREE_OVERFLOW (res)) - res = chrec_dont_know; - if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " (set_nb_iterations_in_loop = "); @@ -946,7 +898,7 @@ set_nb_iterations_in_loop (struct loop *loop, EXPR. */ static bool -analyzable_condition (tree expr) +analyzable_condition (const_tree expr) { tree condition; @@ -958,9 +910,6 @@ analyzable_condition (tree expr) switch (TREE_CODE (condition)) { case SSA_NAME: - /* Volatile expressions are not analyzable. */ - if (TREE_THIS_VOLATILE (SSA_NAME_VAR (condition))) - return false; return true; case LT_EXPR: @@ -969,22 +918,7 @@ analyzable_condition (tree expr) case GE_EXPR: case EQ_EXPR: case NE_EXPR: - { - tree opnd0, opnd1; - - opnd0 = TREE_OPERAND (condition, 0); - opnd1 = TREE_OPERAND (condition, 1); - - if (TREE_CODE (opnd0) == SSA_NAME - && TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd0))) - return false; - - if (TREE_CODE (opnd1) == SSA_NAME - && TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd1))) - return false; - - return true; - } + return true; default: return false; @@ -998,11 +932,10 @@ analyzable_condition (tree expr) analyze, then give up. */ tree -get_loop_exit_condition (struct loop *loop) +get_loop_exit_condition (const struct loop *loop) { tree res = NULL_TREE; - edge exit_edge = loop->single_exit; - + edge exit_edge = single_exit (loop); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "(get_loop_exit_condition \n "); @@ -1029,7 +962,7 @@ get_loop_exit_condition (struct loop *loop) static void get_exit_conditions_rec (struct loop *loop, - varray_type *exit_conditions) + VEC(tree,heap) **exit_conditions) { if (!loop) return; @@ -1038,23 +971,22 @@ get_exit_conditions_rec (struct loop *loop, get_exit_conditions_rec (loop->inner, exit_conditions); get_exit_conditions_rec (loop->next, exit_conditions); - if (loop->single_exit) + if (single_exit (loop)) { tree loop_condition = get_loop_exit_condition (loop); if (loop_condition) - VARRAY_PUSH_TREE (*exit_conditions, loop_condition); + VEC_safe_push (tree, heap, *exit_conditions, loop_condition); } } /* Select the candidate loop nests for the analysis. This function - initializes the EXIT_CONDITIONS array. */ + initializes the EXIT_CONDITIONS array. */ static void -select_loops_exit_conditions (struct loops *loops, - varray_type *exit_conditions) +select_loops_exit_conditions (VEC(tree,heap) **exit_conditions) { - struct loop *function_body = loops->parray[0]; + struct loop *function_body = current_loops->tree_root; get_exit_conditions_rec (function_body->inner, exit_conditions); } @@ -1062,48 +994,59 @@ select_loops_exit_conditions (struct loops *loops, /* Depth first search algorithm. */ -static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *); +typedef enum t_bool { + t_false, + t_true, + t_dont_know +} t_bool; + + +static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int); /* Follow the ssa edge into the right hand side RHS of an assignment. Return true if the strongly connected component has been found. */ -static bool -follow_ssa_edge_in_rhs (struct loop *loop, - tree rhs, - tree halting_phi, - tree *evolution_of_loop) +static t_bool +follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs, + tree halting_phi, tree *evolution_of_loop, int limit) { - bool res = false; + t_bool res = t_false; tree rhs0, rhs1; tree type_rhs = TREE_TYPE (rhs); + tree evol; + enum tree_code code; /* The RHS is one of the following cases: - an SSA_NAME, - an INTEGER_CST, - a PLUS_EXPR, + - a POINTER_PLUS_EXPR, - a MINUS_EXPR, - - other cases are not yet handled. - */ - switch (TREE_CODE (rhs)) + - an ASSERT_EXPR, + - other cases are not yet handled. */ + code = TREE_CODE (rhs); + switch (code) { case NOP_EXPR: /* This assignment is under the form "a_1 = (cast) rhs. */ - res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi, - evolution_of_loop); - *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop); + res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0), + halting_phi, evolution_of_loop, limit); + *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), + *evolution_of_loop, at_stmt); break; case INTEGER_CST: /* This assignment is under the form "a_1 = 7". */ - res = false; + res = t_false; break; case SSA_NAME: /* This assignment is under the form: "a_1 = b_2". */ res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop); + (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit); break; + case POINTER_PLUS_EXPR: case PLUS_EXPR: /* This case is under the form "rhs0 + rhs1". */ rhs0 = TREE_OPERAND (rhs, 0); @@ -1117,28 +1060,41 @@ follow_ssa_edge_in_rhs (struct loop *loop, { /* Match an assignment under the form: "a = b + c". */ + + /* We want only assignments of form "name + name" contribute to + LIMIT, as the other cases do not necessarily contribute to + the complexity of the expression. */ + limit++; + + evol = *evolution_of_loop; res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, - evolution_of_loop); + &evol, limit); - if (res) + if (res == t_true) *evolution_of_loop = add_to_evolution (loop->num, - chrec_convert (type_rhs, *evolution_of_loop), - PLUS_EXPR, rhs1); + chrec_convert (type_rhs, evol, at_stmt), + code, rhs1, at_stmt); - else + else if (res == t_false) { res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, - evolution_of_loop); + evolution_of_loop, limit); - if (res) + if (res == t_true) *evolution_of_loop = add_to_evolution (loop->num, - chrec_convert (type_rhs, *evolution_of_loop), - PLUS_EXPR, rhs0); + chrec_convert (type_rhs, *evolution_of_loop, at_stmt), + code, rhs0, at_stmt); + + else if (res == t_dont_know) + *evolution_of_loop = chrec_dont_know; } + + else if (res == t_dont_know) + *evolution_of_loop = chrec_dont_know; } else @@ -1147,11 +1103,15 @@ follow_ssa_edge_in_rhs (struct loop *loop, "a = b + ...". */ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, - evolution_of_loop); - if (res) + evolution_of_loop, limit); + if (res == t_true) *evolution_of_loop = add_to_evolution - (loop->num, chrec_convert (type_rhs, *evolution_of_loop), - PLUS_EXPR, rhs1); + (loop->num, chrec_convert (type_rhs, *evolution_of_loop, + at_stmt), + code, rhs1, at_stmt); + + else if (res == t_dont_know) + *evolution_of_loop = chrec_dont_know; } } @@ -1161,18 +1121,22 @@ follow_ssa_edge_in_rhs (struct loop *loop, "a = ... + c". */ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, - evolution_of_loop); - if (res) + evolution_of_loop, limit); + if (res == t_true) *evolution_of_loop = add_to_evolution - (loop->num, chrec_convert (type_rhs, *evolution_of_loop), - PLUS_EXPR, rhs0); + (loop->num, chrec_convert (type_rhs, *evolution_of_loop, + at_stmt), + code, rhs0, at_stmt); + + else if (res == t_dont_know) + *evolution_of_loop = chrec_dont_know; } else /* Otherwise, match an assignment under the form: "a = ... + ...". */ /* And there is nothing to do. */ - res = false; + res = t_false; break; @@ -1185,138 +1149,49 @@ follow_ssa_edge_in_rhs (struct loop *loop, if (TREE_CODE (rhs0) == SSA_NAME) { - if (TREE_CODE (rhs1) == SSA_NAME) - { - /* Match an assignment under the form: - "a = b - c". */ - res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, - evolution_of_loop); - - if (res) - *evolution_of_loop = add_to_evolution - (loop->num, chrec_convert (type_rhs, *evolution_of_loop), - MINUS_EXPR, rhs1); - - else - { - res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, - evolution_of_loop); - - if (res) - *evolution_of_loop = add_to_evolution - (loop->num, - chrec_fold_multiply (type_rhs, - *evolution_of_loop, - fold_convert (type_rhs, - integer_minus_one_node)), - PLUS_EXPR, rhs0); - } - } - - else - { - /* Match an assignment under the form: - "a = b - ...". */ - res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, - evolution_of_loop); - if (res) - *evolution_of_loop = add_to_evolution - (loop->num, chrec_convert (type_rhs, *evolution_of_loop), - MINUS_EXPR, rhs1); - } - } - - else if (TREE_CODE (rhs1) == SSA_NAME) - { /* Match an assignment under the form: - "a = ... - c". */ - res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, - evolution_of_loop); - if (res) + "a = b - ...". */ + + /* We want only assignments of form "name - name" contribute to + LIMIT, as the other cases do not necessarily contribute to + the complexity of the expression. */ + if (TREE_CODE (rhs1) == SSA_NAME) + limit++; + + res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, + evolution_of_loop, limit); + if (res == t_true) *evolution_of_loop = add_to_evolution - (loop->num, - chrec_fold_multiply (type_rhs, - *evolution_of_loop, - fold_convert (type_rhs, integer_minus_one_node)), - PLUS_EXPR, rhs0); + (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt), + MINUS_EXPR, rhs1, at_stmt); + + else if (res == t_dont_know) + *evolution_of_loop = chrec_dont_know; } - else /* Otherwise, match an assignment under the form: "a = ... - ...". */ /* And there is nothing to do. */ - res = false; + res = t_false; break; - case MULT_EXPR: - /* This case is under the form "opnd0 = rhs0 * rhs1". */ - rhs0 = TREE_OPERAND (rhs, 0); - rhs1 = TREE_OPERAND (rhs, 1); - STRIP_TYPE_NOPS (rhs0); - STRIP_TYPE_NOPS (rhs1); + case ASSERT_EXPR: + { + /* This assignment is of the form: "a_1 = ASSERT_EXPR " + It must be handled as a copy assignment of the form a_1 = a_2. */ + tree op0 = ASSERT_EXPR_VAR (rhs); + if (TREE_CODE (op0) == SSA_NAME) + res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0), + halting_phi, evolution_of_loop, limit); + else + res = t_false; + break; + } - if (TREE_CODE (rhs0) == SSA_NAME) - { - if (TREE_CODE (rhs1) == SSA_NAME) - { - /* Match an assignment under the form: - "a = b * c". */ - res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, - evolution_of_loop); - - if (res) - *evolution_of_loop = chrec_dont_know; - - else - { - res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, - evolution_of_loop); - - if (res) - *evolution_of_loop = chrec_dont_know; - } - } - - else - { - /* Match an assignment under the form: - "a = b * ...". */ - res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, - evolution_of_loop); - if (res) - *evolution_of_loop = chrec_dont_know; - } - } - - else if (TREE_CODE (rhs1) == SSA_NAME) - { - /* Match an assignment under the form: - "a = ... * c". */ - res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, - evolution_of_loop); - if (res) - *evolution_of_loop = chrec_dont_know; - } - - else - /* Otherwise, match an assignment under the form: - "a = ... * ...". */ - /* And there is nothing to do. */ - res = false; - - break; default: - res = false; + res = t_false; break; } @@ -1326,9 +1201,9 @@ follow_ssa_edge_in_rhs (struct loop *loop, /* Checks whether the I-th argument of a PHI comes from a backedge. */ static bool -backedge_phi_arg_p (tree phi, int i) +backedge_phi_arg_p (const_tree phi, int i) { - edge e = PHI_ARG_EDGE (phi, i); + const_edge e = PHI_ARG_EDGE (phi, i); /* We would in fact like to test EDGE_DFS_BACK here, but we do not care about updating it anywhere, and this should work as well most of the @@ -1343,13 +1218,13 @@ backedge_phi_arg_p (tree phi, int i) true if the strongly connected component has been found following this path. */ -static inline bool +static inline t_bool follow_ssa_edge_in_condition_phi_branch (int i, struct loop *loop, tree condition_phi, tree halting_phi, tree *evolution_of_branch, - tree init_cond) + tree init_cond, int limit) { tree branch = PHI_ARG_DEF (condition_phi, i); *evolution_of_branch = chrec_dont_know; @@ -1357,13 +1232,13 @@ follow_ssa_edge_in_condition_phi_branch (int i, /* Do not follow back edges (they must belong to an irreducible loop, which we really do not want to worry about). */ if (backedge_phi_arg_p (condition_phi, i)) - return false; + return t_false; if (TREE_CODE (branch) == SSA_NAME) { *evolution_of_branch = init_cond; return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi, - evolution_of_branch); + evolution_of_branch, limit); } /* This case occurs when one of the condition branches sets @@ -1373,42 +1248,53 @@ follow_ssa_edge_in_condition_phi_branch (int i, FIXME: This case have to be refined correctly: in some cases it is possible to say something better than chrec_dont_know, for example using a wrap-around notation. */ - return false; + return t_false; } /* This function merges the branches of a condition-phi-node in a loop. */ -static bool +static t_bool follow_ssa_edge_in_condition_phi (struct loop *loop, tree condition_phi, tree halting_phi, - tree *evolution_of_loop) + tree *evolution_of_loop, int limit) { int i; tree init = *evolution_of_loop; tree evolution_of_branch; + t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi, + halting_phi, + &evolution_of_branch, + init, limit); + if (res == t_false || res == t_dont_know) + return res; - if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi, - halting_phi, - &evolution_of_branch, - init)) - return false; *evolution_of_loop = evolution_of_branch; + /* If the phi node is just a copy, do not increase the limit. */ + if (PHI_NUM_ARGS (condition_phi) > 1) + limit++; + for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++) { - if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi, - halting_phi, - &evolution_of_branch, - init)) - return false; + /* Quickly give up when the evolution of one of the branches is + not known. */ + if (*evolution_of_loop == chrec_dont_know) + return t_true; + + res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi, + halting_phi, + &evolution_of_branch, + init, limit); + if (res == t_false || res == t_dont_know) + return res; *evolution_of_loop = chrec_merge (*evolution_of_loop, evolution_of_branch); } - return true; + return t_true; } /* Follow an SSA edge in an inner loop. It computes the overall @@ -1416,11 +1302,11 @@ follow_ssa_edge_in_condition_phi (struct loop *loop, it follows the edges in the parent loop. The inner loop is considered as a single statement. */ -static bool +static t_bool follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, tree loop_phi_node, tree halting_phi, - tree *evolution_of_loop) + tree *evolution_of_loop, int limit) { struct loop *loop = loop_containing_stmt (loop_phi_node); tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node)); @@ -1429,7 +1315,7 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, result of the analysis is a symbolic parameter. */ if (ev == PHI_RESULT (loop_phi_node)) { - bool res = false; + t_bool res = t_false; int i; for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++) @@ -1440,12 +1326,15 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, /* Follow the edges that exit the inner loop. */ bb = PHI_ARG_EDGE (loop_phi_node, i)->src; if (!flow_bb_inside_loop_p (loop, bb)) - res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi, - evolution_of_loop); + res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, + arg, halting_phi, + evolution_of_loop, limit); + if (res == t_true) + break; } /* If the path crosses this loop-phi, give up. */ - if (res == true) + if (res == t_true) *evolution_of_loop = chrec_dont_know; return res; @@ -1453,23 +1342,25 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, /* Otherwise, compute the overall effect of the inner loop. */ ev = compute_overall_effect_of_inner_loop (loop, ev); - return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi, - evolution_of_loop); + return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi, + evolution_of_loop, limit); } /* Follow an SSA edge from a loop-phi-node to itself, constructing a path that is analyzed on the return walk. */ -static bool -follow_ssa_edge (struct loop *loop, - tree def, - tree halting_phi, - tree *evolution_of_loop) +static t_bool +follow_ssa_edge (struct loop *loop, tree def, tree halting_phi, + tree *evolution_of_loop, int limit) { struct loop *def_loop; if (TREE_CODE (def) == NOP_EXPR) - return false; + return t_false; + + /* Give up if the path is longer than the MAX that we allow. */ + if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) + return t_dont_know; def_loop = loop_containing_stmt (def); @@ -1482,39 +1373,39 @@ follow_ssa_edge (struct loop *loop, information and set the approximation to the main variable. */ return follow_ssa_edge_in_condition_phi - (loop, def, halting_phi, evolution_of_loop); + (loop, def, halting_phi, evolution_of_loop, limit); /* When the analyzed phi is the halting_phi, the depth-first search is over: we have found a path from the halting_phi to itself in the loop. */ if (def == halting_phi) - return true; + return t_true; /* Otherwise, the evolution of the HALTING_PHI depends on the evolution of another loop-phi-node, i.e. the evolution function is a higher degree polynomial. */ if (def_loop == loop) - return false; + return t_false; /* Inner loop. */ if (flow_loop_nested_p (loop, def_loop)) return follow_ssa_edge_inner_loop_phi - (loop, def, halting_phi, evolution_of_loop); + (loop, def, halting_phi, evolution_of_loop, limit + 1); /* Outer loop. */ - return false; + return t_false; - case MODIFY_EXPR: - return follow_ssa_edge_in_rhs (loop, - TREE_OPERAND (def, 1), + case GIMPLE_MODIFY_STMT: + return follow_ssa_edge_in_rhs (loop, def, + GIMPLE_STMT_OPERAND (def, 1), halting_phi, - evolution_of_loop); + evolution_of_loop, limit); default: /* At this level of abstraction, the program is just a set - of MODIFY_EXPRs and PHI_NODEs. In principle there is no + of GIMPLE_MODIFY_STMTs and PHI_NODEs. In principle there is no other node to be handled. */ - return false; + return t_false; } } @@ -1544,7 +1435,7 @@ analyze_evolution_in_loop (tree loop_phi_node, { tree arg = PHI_ARG_DEF (loop_phi_node, i); tree ssa_chain, ev_fn; - bool res; + t_bool res; /* Select the edges that enter the loop body. */ bb = PHI_ARG_EDGE (loop_phi_node, i)->src; @@ -1557,10 +1448,10 @@ analyze_evolution_in_loop (tree loop_phi_node, /* Pass in the initial condition to the follow edge function. */ ev_fn = init_cond; - res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn); + res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0); } else - res = false; + res = t_false; /* When it is impossible to go back on the same loop_phi_node by following the ssa edges, the @@ -1568,7 +1459,7 @@ analyze_evolution_in_loop (tree loop_phi_node, first iteration, EV_FN has the value INIT_COND, then all the other iterations it has the value of ARG. For the moment, PEELED_CHREC nodes are not built. */ - if (!res) + if (res != t_true) ev_fn = chrec_dont_know; /* When there are multiple back edges of the loop (which in fact never @@ -1663,7 +1554,7 @@ interpret_loop_phi (struct loop *loop, tree loop_phi_node) (phi_loop, PHI_RESULT (loop_phi_node)); /* Dive one level deeper. */ - subloop = superloop_at_depth (phi_loop, loop->depth + 1); + subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1); /* Interpret the subloop. */ res = compute_overall_effect_of_inner_loop (subloop, evolution_fn); @@ -1706,31 +1597,41 @@ interpret_condition_phi (struct loop *loop, tree condition_phi) return res; } -/* Interpret the right hand side of a modify_expr OPND1. If we didn't - analyzed this node before, follow the definitions until ending - either on an analyzed modify_expr, or on a loop-phi-node. On the +/* Interpret the right hand side of a GIMPLE_MODIFY_STMT OPND1. If we didn't + analyze this node before, follow the definitions until ending + either on an analyzed GIMPLE_MODIFY_STMT, or on a loop-phi-node. On the return path, this function propagates evolutions (ala constant copy propagation). OPND1 is not a GIMPLE expression because we could analyze the effect of an inner loop: see interpret_loop_phi. */ static tree -interpret_rhs_modify_expr (struct loop *loop, - tree opnd1, tree type) +interpret_rhs_modify_stmt (struct loop *loop, tree at_stmt, + tree opnd1, tree type) { tree res, opnd10, opnd11, chrec10, chrec11; - + if (is_gimple_min_invariant (opnd1)) - return chrec_convert (type, opnd1); - + return chrec_convert (type, opnd1, at_stmt); + switch (TREE_CODE (opnd1)) { + case POINTER_PLUS_EXPR: + opnd10 = TREE_OPERAND (opnd1, 0); + opnd11 = TREE_OPERAND (opnd1, 1); + chrec10 = analyze_scalar_evolution (loop, opnd10); + chrec11 = analyze_scalar_evolution (loop, opnd11); + chrec10 = chrec_convert (type, chrec10, at_stmt); + chrec11 = chrec_convert (sizetype, chrec11, at_stmt); + res = chrec_fold_plus (type, chrec10, chrec11); + break; + case PLUS_EXPR: opnd10 = TREE_OPERAND (opnd1, 0); opnd11 = TREE_OPERAND (opnd1, 1); chrec10 = analyze_scalar_evolution (loop, opnd10); chrec11 = analyze_scalar_evolution (loop, opnd11); - chrec10 = chrec_convert (type, chrec10); - chrec11 = chrec_convert (type, chrec11); + chrec10 = chrec_convert (type, chrec10, at_stmt); + chrec11 = chrec_convert (type, chrec11, at_stmt); res = chrec_fold_plus (type, chrec10, chrec11); break; @@ -1739,16 +1640,18 @@ interpret_rhs_modify_expr (struct loop *loop, opnd11 = TREE_OPERAND (opnd1, 1); chrec10 = analyze_scalar_evolution (loop, opnd10); chrec11 = analyze_scalar_evolution (loop, opnd11); - chrec10 = chrec_convert (type, chrec10); - chrec11 = chrec_convert (type, chrec11); + chrec10 = chrec_convert (type, chrec10, at_stmt); + chrec11 = chrec_convert (type, chrec11, at_stmt); res = chrec_fold_minus (type, chrec10, chrec11); break; case NEGATE_EXPR: opnd10 = TREE_OPERAND (opnd1, 0); chrec10 = analyze_scalar_evolution (loop, opnd10); - chrec10 = chrec_convert (type, chrec10); - res = chrec_fold_minus (type, build_int_cst (type, 0), chrec10); + chrec10 = chrec_convert (type, chrec10, at_stmt); + /* TYPE may be integer, real or complex, so use fold_convert. */ + res = chrec_fold_multiply (type, chrec10, + fold_convert (type, integer_minus_one_node)); break; case MULT_EXPR: @@ -1756,20 +1659,27 @@ interpret_rhs_modify_expr (struct loop *loop, opnd11 = TREE_OPERAND (opnd1, 1); chrec10 = analyze_scalar_evolution (loop, opnd10); chrec11 = analyze_scalar_evolution (loop, opnd11); - chrec10 = chrec_convert (type, chrec10); - chrec11 = chrec_convert (type, chrec11); + chrec10 = chrec_convert (type, chrec10, at_stmt); + chrec11 = chrec_convert (type, chrec11, at_stmt); res = chrec_fold_multiply (type, chrec10, chrec11); break; case SSA_NAME: - res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1)); + res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1), + at_stmt); + break; + + case ASSERT_EXPR: + opnd10 = ASSERT_EXPR_VAR (opnd1); + res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10), + at_stmt); break; case NOP_EXPR: case CONVERT_EXPR: opnd10 = TREE_OPERAND (opnd1, 0); chrec10 = analyze_scalar_evolution (loop, opnd10); - res = chrec_convert (type, chrec10); + res = chrec_convert (type, chrec10, at_stmt); break; default: @@ -1800,7 +1710,7 @@ compute_scalar_evolution_in_loop (struct loop *wrto_loop, if (def_loop == wrto_loop) return ev; - def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1); + def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1); res = compute_overall_effect_of_inner_loop (def_loop, ev); return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet); @@ -1815,11 +1725,11 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) basic_block bb; struct loop *def_loop; - if (loop == NULL) + if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE) return chrec_dont_know; if (TREE_CODE (var) != SSA_NAME) - return interpret_rhs_modify_expr (loop, var, type); + return interpret_rhs_modify_stmt (loop, NULL_TREE, var, type); def = SSA_NAME_DEF_STMT (var); bb = bb_for_stmt (def); @@ -1852,8 +1762,9 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) switch (TREE_CODE (def)) { - case MODIFY_EXPR: - res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1), type); + case GIMPLE_MODIFY_STMT: + res = interpret_rhs_modify_stmt (loop, def, + GIMPLE_STMT_OPERAND (def, 1), type); break; case PHI_NODE: @@ -1923,19 +1834,28 @@ analyze_scalar_evolution (struct loop *loop, tree var) /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to WRTO_LOOP (which should be a superloop of both USE_LOOP and definition - of VERSION). */ + of VERSION). + + FOLDED_CASTS is set to true if resolve_mixers used + chrec_convert_aggressive (TODO -- not really, we are way too conservative + at the moment in order to keep things simple). */ static tree analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop, - tree version) + tree version, bool *folded_casts) { bool val = false; - tree ev = version; + tree ev = version, tmp; + if (folded_casts) + *folded_casts = false; while (1) { - ev = analyze_scalar_evolution (use_loop, ev); - ev = resolve_mixers (use_loop, ev); + tmp = analyze_scalar_evolution (use_loop, ev); + ev = resolve_mixers (use_loop, tmp); + + if (folded_casts && tmp != ev) + *folded_casts = true; if (use_loop == wrto_loop) return ev; @@ -1947,28 +1867,100 @@ analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop, || !val) return chrec_dont_know; - use_loop = use_loop->outer; + use_loop = loop_outer (use_loop); } } +/* Returns instantiated value for VERSION in CACHE. */ + +static tree +get_instantiated_value (htab_t cache, tree version) +{ + struct scev_info_str *info, pattern; + + pattern.var = version; + info = (struct scev_info_str *) htab_find (cache, &pattern); + + if (info) + return info->chrec; + else + return NULL_TREE; +} + +/* Sets instantiated value for VERSION to VAL in CACHE. */ + +static void +set_instantiated_value (htab_t cache, tree version, tree val) +{ + struct scev_info_str *info, pattern; + PTR *slot; + + pattern.var = version; + slot = htab_find_slot (cache, &pattern, INSERT); + + if (!*slot) + *slot = new_scev_info_str (version); + info = (struct scev_info_str *) *slot; + info->chrec = val; +} + +/* Return the closed_loop_phi node for VAR. If there is none, return + NULL_TREE. */ + +static tree +loop_closed_phi_def (tree var) +{ + struct loop *loop; + edge exit; + tree phi; + + if (var == NULL_TREE + || TREE_CODE (var) != SSA_NAME) + return NULL_TREE; + + loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var)); + exit = single_exit (loop); + if (!exit) + return NULL_TREE; + + for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi)) + if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var) + return PHI_RESULT (phi); + + return NULL_TREE; +} + /* Analyze all the parameters of the chrec that were left under a symbolic form, - with respect to LOOP. CHREC is the chrec to instantiate. If - ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with - outer loop chrecs is done. */ + with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache + of already instantiated values. FLAGS modify the way chrecs are + instantiated. SIZE_EXPR is used for computing the size of the expression to + be instantiated, and to stop if it exceeds some limit. */ +/* Values for FLAGS. */ +enum +{ + INSERT_SUPERLOOP_CHRECS = 1, /* Loop invariants are replaced with chrecs + in outer loops. */ + FOLD_CONVERSIONS = 2 /* The conversions that may wrap in + signed/pointer type are folded, as long as the + value of the chrec is preserved. */ +}; + static tree -instantiate_parameters_1 (struct loop *loop, tree chrec, - bool allow_superloop_chrecs) +instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache, + int size_expr) { tree res, op0, op1, op2; basic_block def_bb; struct loop *def_loop; - - if (chrec == NULL_TREE - || automatically_generated_chrec_p (chrec)) - return chrec; - - if (is_gimple_min_invariant (chrec)) + tree type = chrec_type (chrec); + + /* Give up if the expression is larger than the MAX that we allow. */ + if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) + return chrec_dont_know; + + if (automatically_generated_chrec_p (chrec) + || is_gimple_min_invariant (chrec)) return chrec; switch (TREE_CODE (chrec)) @@ -1979,77 +1971,174 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, /* A parameter (or loop invariant and we do not want to include evolutions in outer loops), nothing to do. */ if (!def_bb - || (!allow_superloop_chrecs + || (!(flags & INSERT_SUPERLOOP_CHRECS) && !flow_bb_inside_loop_p (loop, def_bb))) return chrec; - /* Don't instantiate the SSA_NAME if it is in a mixer + /* We cache the value of instantiated variable to avoid exponential + time complexity due to reevaluations. We also store the convenient + value in the cache in order to prevent infinite recursion -- we do + not want to instantiate the SSA_NAME if it is in a mixer structure. This is used for avoiding the instantiation of recursively defined functions, such as: | a_2 -> {0, +, 1, +, a_2}_1 */ - + + res = get_instantiated_value (cache, chrec); + if (res) + return res; + + /* Store the convenient value for chrec in the structure. If it + is defined outside of the loop, we may just leave it in symbolic + form, otherwise we need to admit that we do not know its behavior + inside the loop. */ + res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know; + set_instantiated_value (cache, chrec, res); + + /* To make things even more complicated, instantiate_parameters_1 + calls analyze_scalar_evolution that may call # of iterations + analysis that may in turn call instantiate_parameters_1 again. + To prevent the infinite recursion, keep also the bitmap of + ssa names that are being instantiated globally. */ if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec))) - { - if (!flow_bb_inside_loop_p (loop, def_bb)) - { - /* We may keep the loop invariant in symbolic form. */ - return chrec; - } - else - { - /* Something with unknown behavior in LOOP. */ - return chrec_dont_know; - } - } + return res; def_loop = find_common_loop (loop, def_bb->loop_father); /* If the analysis yields a parametric chrec, instantiate the - result again. Avoid the cyclic instantiation in mixers. */ + result again. */ bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); res = analyze_scalar_evolution (def_loop, chrec); - res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs); + + /* Don't instantiate loop-closed-ssa phi nodes. */ + if (TREE_CODE (res) == SSA_NAME + && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL + || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res))) + > loop_depth (def_loop)))) + { + if (res == chrec) + res = loop_closed_phi_def (chrec); + else + res = chrec; + + if (res == NULL_TREE) + res = chrec_dont_know; + } + + else if (res != chrec_dont_know) + res = instantiate_parameters_1 (loop, res, flags, cache, size_expr); + bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); + + /* Store the correct value to the cache. */ + set_instantiated_value (cache, chrec, res); return res; case POLYNOMIAL_CHREC: op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec), - allow_superloop_chrecs); + flags, cache, size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec), - allow_superloop_chrecs); - return build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); + flags, cache, size_expr); + if (op1 == chrec_dont_know) + return chrec_dont_know; + if (CHREC_LEFT (chrec) != op0 + || CHREC_RIGHT (chrec) != op1) + { + op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL_TREE); + chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); + } + return chrec; + + case POINTER_PLUS_EXPR: case PLUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs); + flags, cache, size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), - allow_superloop_chrecs); - return chrec_fold_plus (TREE_TYPE (chrec), op0, op1); + flags, cache, size_expr); + if (op1 == chrec_dont_know) + return chrec_dont_know; + + if (TREE_OPERAND (chrec, 0) != op0 + || TREE_OPERAND (chrec, 1) != op1) + { + op0 = chrec_convert (type, op0, NULL_TREE); + op1 = chrec_convert_rhs (type, op1, NULL_TREE); + chrec = chrec_fold_plus (type, op0, op1); + } + return chrec; case MINUS_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs); + flags, cache, size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), - allow_superloop_chrecs); - return chrec_fold_minus (TREE_TYPE (chrec), op0, op1); + flags, cache, size_expr); + if (op1 == chrec_dont_know) + return chrec_dont_know; + + if (TREE_OPERAND (chrec, 0) != op0 + || TREE_OPERAND (chrec, 1) != op1) + { + op0 = chrec_convert (type, op0, NULL_TREE); + op1 = chrec_convert (type, op1, NULL_TREE); + chrec = chrec_fold_minus (type, op0, op1); + } + return chrec; case MULT_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs); + flags, cache, size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), - allow_superloop_chrecs); - return chrec_fold_multiply (TREE_TYPE (chrec), op0, op1); + flags, cache, size_expr); + if (op1 == chrec_dont_know) + return chrec_dont_know; + + if (TREE_OPERAND (chrec, 0) != op0 + || TREE_OPERAND (chrec, 1) != op1) + { + op0 = chrec_convert (type, op0, NULL_TREE); + op1 = chrec_convert (type, op1, NULL_TREE); + chrec = chrec_fold_multiply (type, op0, op1); + } + return chrec; case NOP_EXPR: case CONVERT_EXPR: case NON_LVALUE_EXPR: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs); + flags, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - return chrec_convert (TREE_TYPE (chrec), op0); + if (flags & FOLD_CONVERSIONS) + { + tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0); + if (tmp) + return tmp; + } + + if (op0 == TREE_OPERAND (chrec, 0)) + return chrec; + + /* If we used chrec_convert_aggressive, we can no longer assume that + signed chrecs do not overflow, as chrec_convert does, so avoid + calling it in that case. */ + if (flags & FOLD_CONVERSIONS) + return fold_convert (TREE_TYPE (chrec), op0); + + return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE); case SCEV_NOT_KNOWN: return chrec_dont_know; @@ -2061,38 +2150,57 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, break; } + gcc_assert (!VL_EXP_CLASS_P (chrec)); switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) { case 3: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs); + flags, cache, size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), - allow_superloop_chrecs); + flags, cache, size_expr); + if (op1 == chrec_dont_know) + return chrec_dont_know; + op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2), - allow_superloop_chrecs); - if (op0 == chrec_dont_know - || op1 == chrec_dont_know - || op2 == chrec_dont_know) + flags, cache, size_expr); + if (op2 == chrec_dont_know) return chrec_dont_know; - return fold (build (TREE_CODE (chrec), - TREE_TYPE (chrec), op0, op1, op2)); + + if (op0 == TREE_OPERAND (chrec, 0) + && op1 == TREE_OPERAND (chrec, 1) + && op2 == TREE_OPERAND (chrec, 2)) + return chrec; + + return fold_build3 (TREE_CODE (chrec), + TREE_TYPE (chrec), op0, op1, op2); case 2: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs); + flags, cache, size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1), - allow_superloop_chrecs); - if (op0 == chrec_dont_know - || op1 == chrec_dont_know) + flags, cache, size_expr); + if (op1 == chrec_dont_know) return chrec_dont_know; - return fold (build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1)); + + if (op0 == TREE_OPERAND (chrec, 0) + && op1 == TREE_OPERAND (chrec, 1)) + return chrec; + return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); case 1: op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0), - allow_superloop_chrecs); + flags, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - return fold (build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0)); + if (op0 == TREE_OPERAND (chrec, 0)) + return chrec; + return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0); case 0: return chrec; @@ -2114,6 +2222,7 @@ instantiate_parameters (struct loop *loop, tree chrec) { tree res; + htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -2124,7 +2233,8 @@ instantiate_parameters (struct loop *loop, fprintf (dump_file, ")\n"); } - res = instantiate_parameters_1 (loop, chrec, true); + res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache, + 0); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -2132,17 +2242,24 @@ instantiate_parameters (struct loop *loop, print_generic_expr (dump_file, res, 0); fprintf (dump_file, "))\n"); } + + htab_delete (cache); return res; } /* Similar to instantiate_parameters, but does not introduce the - evolutions in outer loops for LOOP invariants in CHREC. */ + evolutions in outer loops for LOOP invariants in CHREC, and does not + care about causing overflows, as long as they do not affect value + of an expression. */ -static tree +tree resolve_mixers (struct loop *loop, tree chrec) { - return instantiate_parameters_1 (loop, chrec, false); + htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); + tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0); + htab_delete (cache); + return ret; } /* Entry point for the analysis of the number of iterations pass. @@ -2166,7 +2283,7 @@ resolve_mixers (struct loop *loop, tree chrec) the loop body has been executed 6 times. */ tree -number_of_iterations_in_loop (struct loop *loop) +number_of_latch_executions (struct loop *loop) { tree res, type; edge exit; @@ -2182,11 +2299,11 @@ number_of_iterations_in_loop (struct loop *loop) if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "(number_of_iterations_in_loop\n"); - exit = loop->single_exit; + exit = single_exit (loop); if (!exit) goto end; - if (!number_of_iterations_exit (loop, exit, &niter_desc)) + if (!number_of_iterations_exit (loop, exit, &niter_desc, false)) goto end; type = TREE_TYPE (niter_desc.niter); @@ -2201,21 +2318,48 @@ end: return set_nb_iterations_in_loop (loop, res); } +/* Returns the number of executions of the exit condition of LOOP, + i.e., the number by one higher than number_of_latch_executions. + Note that unline number_of_latch_executions, this number does + not necessarily fit in the unsigned variant of the type of + the control variable -- if the number of iterations is a constant, + we return chrec_dont_know if adding one to number_of_latch_executions + overflows; however, in case the number of iterations is symbolic + expression, the caller is responsible for dealing with this + the possible overflow. */ + +tree +number_of_exit_cond_executions (struct loop *loop) +{ + tree ret = number_of_latch_executions (loop); + tree type = chrec_type (ret); + + if (chrec_contains_undetermined (ret)) + return ret; + + ret = chrec_fold_plus (type, ret, build_int_cst (type, 1)); + if (TREE_CODE (ret) == INTEGER_CST + && TREE_OVERFLOW (ret)) + return chrec_dont_know; + + return ret; +} + /* One of the drivers for testing the scalar evolutions analysis. This function computes the number of iterations for all the loops from the EXIT_CONDITIONS array. */ static void -number_of_iterations_for_all_loops (varray_type exit_conditions) +number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions) { unsigned int i; unsigned nb_chrec_dont_know_loops = 0; unsigned nb_static_loops = 0; + tree cond; - for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++) + for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) { - tree res = number_of_iterations_in_loop - (loop_containing_stmt (VARRAY_TREE (exit_conditions, i))); + tree res = number_of_latch_executions (loop_containing_stmt (cond)); if (chrec_contains_undetermined (res)) nb_chrec_dont_know_loops++; else @@ -2228,7 +2372,7 @@ number_of_iterations_for_all_loops (varray_type exit_conditions) fprintf (dump_file, "-----------------------------------------\n"); fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops); fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops); - fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num); + fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ()); fprintf (dump_file, "-----------------------------------------\n"); fprintf (dump_file, ")\n\n"); @@ -2317,7 +2461,7 @@ gather_chrec_stats (tree chrec, struct chrec_stats *stats) fprintf (dump_file, " affine_univariate\n"); stats->nb_affine++; } - else if (evolution_function_is_affine_multivariate_p (chrec)) + else if (evolution_function_is_affine_multivariate_p (chrec, 0)) { if (dump_file && (dump_flags & TDF_STATS)) fprintf (dump_file, " affine_multivariate\n"); @@ -2358,23 +2502,24 @@ gather_chrec_stats (tree chrec, struct chrec_stats *stats) index. This allows the parallelization of the loop. */ static void -analyze_scalar_evolution_for_all_loop_phi_nodes (varray_type exit_conditions) +analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions) { unsigned int i; struct chrec_stats stats; + tree cond; reset_chrecs_counters (&stats); - for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++) + for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) { struct loop *loop; basic_block bb; tree phi, chrec; - loop = loop_containing_stmt (VARRAY_TREE (exit_conditions, i)); + loop = loop_containing_stmt (cond); bb = loop->header; - for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi)) + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) if (is_gimple_reg (PHI_RESULT (phi))) { chrec = instantiate_parameters @@ -2396,9 +2541,9 @@ analyze_scalar_evolution_for_all_loop_phi_nodes (varray_type exit_conditions) static int gather_stats_on_scev_database_1 (void **slot, void *stats) { - struct scev_info_str *entry = *slot; + struct scev_info_str *entry = (struct scev_info_str *) *slot; - gather_chrec_stats (entry->chrec, stats); + gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats); return 1; } @@ -2434,28 +2579,33 @@ initialize_scalar_evolutions_analyzer (void) chrec_not_analyzed_yet = NULL_TREE; chrec_dont_know = make_node (SCEV_NOT_KNOWN); chrec_known = make_node (SCEV_KNOWN); - TREE_TYPE (chrec_dont_know) = NULL_TREE; - TREE_TYPE (chrec_known) = NULL_TREE; + TREE_TYPE (chrec_dont_know) = void_type_node; + TREE_TYPE (chrec_known) = void_type_node; } } /* Initialize the analysis of scalar evolutions for LOOPS. */ void -scev_initialize (struct loops *loops) +scev_initialize (void) { - unsigned i; - current_loops = loops; + loop_iterator li; + struct loop *loop; - scalar_evolution_info = htab_create (100, hash_scev_info, - eq_scev_info, del_scev_info); - already_instantiated = BITMAP_XMALLOC (); + scalar_evolution_info = htab_create_alloc (100, + hash_scev_info, + eq_scev_info, + del_scev_info, + ggc_calloc, + ggc_free); + already_instantiated = BITMAP_ALLOC (NULL); initialize_scalar_evolutions_analyzer (); - for (i = 1; i < loops->num; i++) - if (loops->parray[i]) - loops->parray[i]->nb_iterations = NULL_TREE; + FOR_EACH_LOOP (li, loop, 0) + { + loop->nb_iterations = NULL_TREE; + } } /* Cleans up the information cached by the scalar evolutions analysis. */ @@ -2463,46 +2613,53 @@ scev_initialize (struct loops *loops) void scev_reset (void) { - unsigned i; + loop_iterator li; struct loop *loop; if (!scalar_evolution_info || !current_loops) return; htab_empty (scalar_evolution_info); - for (i = 1; i < current_loops->num; i++) + FOR_EACH_LOOP (li, loop, 0) { - loop = current_loops->parray[i]; - if (loop) - loop->nb_iterations = NULL_TREE; + loop->nb_iterations = NULL_TREE; } } /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns - its BASE and STEP if possible. */ + its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we + want step to be invariant in LOOP. Otherwise we require it to be an + integer constant. IV->no_overflow is set to true if we are sure the iv cannot + overflow (e.g. because it is computed in signed arithmetics). */ bool -simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step) +simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv, + bool allow_nonconstant_step) { basic_block bb = bb_for_stmt (stmt); tree type, ev; + bool folded_casts; - *base = NULL_TREE; - *step = NULL_TREE; + iv->base = NULL_TREE; + iv->step = NULL_TREE; + iv->no_overflow = false; type = TREE_TYPE (op); if (TREE_CODE (type) != INTEGER_TYPE && TREE_CODE (type) != POINTER_TYPE) return false; - ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op); + ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op, + &folded_casts); if (chrec_contains_undetermined (ev)) return false; if (tree_does_not_contain_chrecs (ev) && !chrec_contains_symbols_defined_in_loop (ev, loop->num)) { - *base = ev; + iv->base = ev; + iv->step = build_int_cst (TREE_TYPE (ev), 0); + iv->no_overflow = true; return true; } @@ -2510,14 +2667,23 @@ simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step) || CHREC_VARIABLE (ev) != (unsigned) loop->num) return false; - *step = CHREC_RIGHT (ev); - if (TREE_CODE (*step) != INTEGER_CST) + iv->step = CHREC_RIGHT (ev); + if (allow_nonconstant_step) + { + if (tree_contains_chrecs (iv->step, NULL) + || chrec_contains_symbols_defined_in_loop (iv->step, loop->num)) + return false; + } + else if (TREE_CODE (iv->step) != INTEGER_CST) return false; - *base = CHREC_LEFT (ev); - if (tree_contains_chrecs (*base) - || chrec_contains_symbols_defined_in_loop (*base, loop->num)) + + iv->base = CHREC_LEFT (ev); + if (tree_contains_chrecs (iv->base, NULL) + || chrec_contains_symbols_defined_in_loop (iv->base, loop->num)) return false; + iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type); + return true; } @@ -2526,16 +2692,16 @@ simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step) void scev_analysis (void) { - varray_type exit_conditions; + VEC(tree,heap) *exit_conditions; - VARRAY_GENERIC_PTR_INIT (exit_conditions, 37, "exit_conditions"); - select_loops_exit_conditions (current_loops, &exit_conditions); + exit_conditions = VEC_alloc (tree, heap, 37); + select_loops_exit_conditions (&exit_conditions); if (dump_file && (dump_flags & TDF_STATS)) - analyze_scalar_evolution_for_all_loop_phi_nodes (exit_conditions); + analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions); - number_of_iterations_for_all_loops (exit_conditions); - VARRAY_CLEAR (exit_conditions); + number_of_iterations_for_all_loops (&exit_conditions); + VEC_free (tree, heap, exit_conditions); } /* Finalize the scalar evolution analysis. */ @@ -2543,7 +2709,156 @@ scev_analysis (void) void scev_finalize (void) { + if (!scalar_evolution_info) + return; htab_delete (scalar_evolution_info); - BITMAP_XFREE (already_instantiated); + BITMAP_FREE (already_instantiated); + scalar_evolution_info = NULL; +} + +/* Replace ssa names for that scev can prove they are constant by the + appropriate constants. Also perform final value replacement in loops, + in case the replacement expressions are cheap. + + We only consider SSA names defined by phi nodes; rest is left to the + ordinary constant propagation pass. */ + +unsigned int +scev_const_prop (void) +{ + basic_block bb; + tree name, phi, next_phi, type, ev; + struct loop *loop, *ex_loop; + bitmap ssa_names_to_remove = NULL; + unsigned i; + loop_iterator li; + + if (number_of_loops () <= 1) + return 0; + + FOR_EACH_BB (bb) + { + loop = bb->loop_father; + + for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + { + name = PHI_RESULT (phi); + + if (!is_gimple_reg (name)) + continue; + + type = TREE_TYPE (name); + + if (!POINTER_TYPE_P (type) + && !INTEGRAL_TYPE_P (type)) + continue; + + ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name)); + if (!is_gimple_min_invariant (ev) + || !may_propagate_copy (name, ev)) + continue; + + /* Replace the uses of the name. */ + if (name != ev) + replace_uses_by (name, ev); + + if (!ssa_names_to_remove) + ssa_names_to_remove = BITMAP_ALLOC (NULL); + bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name)); + } + } + + /* Remove the ssa names that were replaced by constants. We do not + remove them directly in the previous cycle, since this + invalidates scev cache. */ + if (ssa_names_to_remove) + { + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi) + { + name = ssa_name (i); + phi = SSA_NAME_DEF_STMT (name); + + gcc_assert (TREE_CODE (phi) == PHI_NODE); + remove_phi_node (phi, NULL, true); + } + + BITMAP_FREE (ssa_names_to_remove); + scev_reset (); + } + + /* Now the regular final value replacement. */ + FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) + { + edge exit; + tree def, rslt, ass, niter; + block_stmt_iterator bsi; + + /* If we do not know exact number of iterations of the loop, we cannot + replace the final value. */ + exit = single_exit (loop); + if (!exit) + continue; + + niter = number_of_latch_executions (loop); + /* We used to check here whether the computation of NITER is expensive, + and avoided final value elimination if that is the case. The problem + is that it is hard to evaluate whether the expression is too + expensive, as we do not know what optimization opportunities the + the elimination of the final value may reveal. Therefore, we now + eliminate the final values of induction variables unconditionally. */ + if (niter == chrec_dont_know) + continue; + + /* Ensure that it is possible to insert new statements somewhere. */ + if (!single_pred_p (exit->dest)) + split_loop_exit_edge (exit); + bsi = bsi_after_labels (exit->dest); + + ex_loop = superloop_at_depth (loop, + loop_depth (exit->dest->loop_father) + 1); + + for (phi = phi_nodes (exit->dest); phi; phi = next_phi) + { + next_phi = PHI_CHAIN (phi); + rslt = PHI_RESULT (phi); + def = PHI_ARG_DEF_FROM_EDGE (phi, exit); + if (!is_gimple_reg (def)) + continue; + + if (!POINTER_TYPE_P (TREE_TYPE (def)) + && !INTEGRAL_TYPE_P (TREE_TYPE (def))) + continue; + + def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL); + def = compute_overall_effect_of_inner_loop (ex_loop, def); + if (!tree_does_not_contain_chrecs (def) + || chrec_contains_symbols_defined_in_loop (def, ex_loop->num) + /* Moving the computation from the loop may prolong life range + of some ssa names, which may cause problems if they appear + on abnormal edges. */ + || contains_abnormal_ssa_name_p (def)) + continue; + + /* Eliminate the PHI node and replace it by a computation outside + the loop. */ + def = unshare_expr (def); + remove_phi_node (phi, NULL_TREE, false); + + ass = build_gimple_modify_stmt (rslt, NULL_TREE); + SSA_NAME_DEF_STMT (rslt) = ass; + { + block_stmt_iterator dest = bsi; + bsi_insert_before (&dest, ass, BSI_NEW_STMT); + def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE, + true, BSI_SAME_STMT); + } + GIMPLE_STMT_OPERAND (ass, 1) = def; + update_stmt (ass); + } + } + return 0; } +#include "gt-tree-scalar-evolution.h"