Mercurial > hg > CbC > CbC_gcc
diff gcc/tree-scalar-evolution.c @ 111:04ced10e8804
gcc 7
| author | kono |
|---|---|
| date | Fri, 27 Oct 2017 22:46:09 +0900 |
| parents | f6334be47118 |
| children | 84e7813d76e9 |
line wrap: on
line diff
--- a/gcc/tree-scalar-evolution.c Sun Aug 21 07:07:55 2011 +0900 +++ b/gcc/tree-scalar-evolution.c Fri Oct 27 22:46:09 2017 +0900 @@ -1,6 +1,5 @@ /* Scalar evolution detector. - Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 - Free Software Foundation, Inc. + Copyright (C) 2003-2017 Free Software Foundation, Inc. Contributed by Sebastian Pop <s.pop@laposte.net> This file is part of GCC. @@ -257,23 +256,42 @@ #include "config.h" #include "system.h" #include "coretypes.h" +#include "backend.h" +#include "rtl.h" +#include "tree.h" +#include "gimple.h" +#include "ssa.h" #include "gimple-pretty-print.h" -#include "tree-flow.h" +#include "fold-const.h" +#include "gimplify.h" +#include "gimple-iterator.h" +#include "gimplify-me.h" +#include "tree-cfg.h" +#include "tree-ssa-loop-ivopts.h" +#include "tree-ssa-loop-manip.h" +#include "tree-ssa-loop-niter.h" +#include "tree-ssa-loop.h" +#include "tree-ssa.h" #include "cfgloop.h" #include "tree-chrec.h" +#include "tree-affine.h" #include "tree-scalar-evolution.h" -#include "tree-pass.h" +#include "dumpfile.h" #include "params.h" - -static tree analyze_scalar_evolution_1 (struct loop *, tree, tree); - -/* The cached information about an SSA name VAR, claiming that below - basic block INSTANTIATED_BELOW, the value of VAR can be expressed - as CHREC. */ - -struct GTY(()) scev_info_str { - basic_block instantiated_below; - tree var; +#include "tree-ssa-propagate.h" +#include "gimple-fold.h" + +static tree analyze_scalar_evolution_1 (struct loop *, tree); +static tree analyze_scalar_evolution_for_address_of (struct loop *loop, + tree var); + +/* The cached information about an SSA name with version NAME_VERSION, + claiming that below basic block with index INSTANTIATED_BELOW, the + value of the SSA name can be expressed as CHREC. */ + +struct GTY((for_user)) scev_info_str { + unsigned int name_version; + int instantiated_below; tree chrec; }; @@ -296,7 +314,13 @@ happen, then it qualifies it with chrec_known. */ tree chrec_known; -static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info; +struct scev_info_hasher : ggc_ptr_hash<scev_info_str> +{ + static hashval_t hash (scev_info_str *i); + static bool equal (const scev_info_str *a, const scev_info_str *b); +}; + +static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info; /* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ @@ -306,42 +330,31 @@ { struct scev_info_str *res; - res = ggc_alloc_scev_info_str (); - res->var = var; + res = ggc_alloc<scev_info_str> (); + res->name_version = SSA_NAME_VERSION (var); res->chrec = chrec_not_analyzed_yet; - res->instantiated_below = instantiated_below; + res->instantiated_below = instantiated_below->index; return res; } /* Computes a hash function for database element ELT. */ -static hashval_t -hash_scev_info (const void *elt) +hashval_t +scev_info_hasher::hash (scev_info_str *elt) { - return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var); + return elt->name_version ^ elt->instantiated_below; } /* Compares database elements E1 and E2. */ -static int -eq_scev_info (const void *e1, const void *e2) +bool +scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2) { - 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 + return (elt1->name_version == elt2->name_version && elt1->instantiated_below == elt2->instantiated_below); } -/* Deletes database element E. */ - -static void -del_scev_info (void *e) -{ - ggc_free (e); -} - /* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block. A first query on VAR returns chrec_not_analyzed_yet. */ @@ -350,15 +363,14 @@ { struct scev_info_str *res; struct scev_info_str tmp; - PTR *slot; - - tmp.var = var; - tmp.instantiated_below = instantiated_below; - slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT); + + tmp.name_version = SSA_NAME_VERSION (var); + tmp.instantiated_below = instantiated_below->index; + scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT); if (!*slot) *slot = new_scev_info_str (instantiated_below, var); - res = (struct scev_info_str *) *slot; + res = *slot; return &res->chrec; } @@ -379,7 +391,7 @@ if (TREE_CODE (chrec) == SSA_NAME) { - gimple def; + gimple *def; loop_p def_loop, loop; if (SSA_NAME_IS_DEFAULT_DEF (chrec)) @@ -387,7 +399,7 @@ def = SSA_NAME_DEF_STMT (chrec); def_loop = loop_containing_stmt (def); - loop = get_loop (loop_nb); + loop = get_loop (cfun, loop_nb); if (def_loop == NULL) return false; @@ -409,7 +421,7 @@ /* Return true when PHI is a loop-phi-node. */ static bool -loop_phi_node_p (gimple phi) +loop_phi_node_p (gimple *phi) { /* The implementation of this function is based on the following property: "all the loop-phi-nodes of a loop are contained in the @@ -499,65 +511,6 @@ return chrec_dont_know; } -/* Determine whether the CHREC is always positive/negative. If the expression - cannot be statically analyzed, return false, otherwise set the answer into - VALUE. */ - -bool -chrec_is_positive (tree chrec, bool *value) -{ - bool value0, value1, value2; - tree end_value, nb_iter; - - switch (TREE_CODE (chrec)) - { - case POLYNOMIAL_CHREC: - if (!chrec_is_positive (CHREC_LEFT (chrec), &value0) - || !chrec_is_positive (CHREC_RIGHT (chrec), &value1)) - return false; - - /* FIXME -- overflows. */ - if (value0 == value1) - { - *value = value0; - return true; - } - - /* Otherwise the chrec is under the form: "{-197, +, 2}_1", - and the proof consists in showing that the sign never - changes during the execution of the loop, from 0 to - loop->nb_iterations. */ - if (!evolution_function_is_affine_p (chrec)) - return false; - - nb_iter = number_of_latch_executions (get_chrec_loop (chrec)); - if (chrec_contains_undetermined (nb_iter)) - return false; - -#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 (type, nb_iter, build_int_cst (type, 1)); -#endif - - end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter); - - if (!chrec_is_positive (end_value, &value2)) - return false; - - *value = value0; - return value0 == value1; - - case INTEGER_CST: - *value = (tree_int_cst_sgn (chrec) == 1); - return true; - - default: - return false; - } -} - /* Associate CHREC to SCALAR. */ static void @@ -572,15 +525,15 @@ if (dump_file) { - if (dump_flags & TDF_DETAILS) + if (dump_flags & TDF_SCEV) { fprintf (dump_file, "(set_scalar_evolution \n"); fprintf (dump_file, " instantiated_below = %d \n", instantiated_below->index); fprintf (dump_file, " (scalar = "); - print_generic_expr (dump_file, scalar, 0); + print_generic_expr (dump_file, scalar); fprintf (dump_file, ")\n (scalar_evolution = "); - print_generic_expr (dump_file, chrec, 0); + print_generic_expr (dump_file, chrec); fprintf (dump_file, "))\n"); } if (dump_flags & TDF_STATS) @@ -600,38 +553,46 @@ if (dump_file) { - if (dump_flags & TDF_DETAILS) + if (dump_flags & TDF_SCEV) { fprintf (dump_file, "(get_scalar_evolution \n"); fprintf (dump_file, " (scalar = "); - print_generic_expr (dump_file, scalar, 0); + print_generic_expr (dump_file, scalar); fprintf (dump_file, ")\n"); } if (dump_flags & TDF_STATS) nb_get_scev++; } - switch (TREE_CODE (scalar)) - { - case SSA_NAME: - res = *find_var_scev_info (instantiated_below, scalar); - break; - - case REAL_CST: - case FIXED_CST: - case INTEGER_CST: - res = scalar; - break; - - default: - res = chrec_not_analyzed_yet; - break; - } - - if (dump_file && (dump_flags & TDF_DETAILS)) + if (VECTOR_TYPE_P (TREE_TYPE (scalar)) + || TREE_CODE (TREE_TYPE (scalar)) == COMPLEX_TYPE) + /* For chrec_dont_know we keep the symbolic form. */ + res = scalar; + else + switch (TREE_CODE (scalar)) + { + case SSA_NAME: + if (SSA_NAME_IS_DEFAULT_DEF (scalar)) + res = scalar; + else + res = *find_var_scev_info (instantiated_below, scalar); + break; + + case REAL_CST: + case FIXED_CST: + case INTEGER_CST: + res = scalar; + break; + + default: + res = chrec_not_analyzed_yet; + break; + } + + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, " (scalar_evolution = "); - print_generic_expr (dump_file, res, 0); + print_generic_expr (dump_file, res); fprintf (dump_file, "))\n"); } @@ -650,10 +611,10 @@ static tree add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add, - gimple at_stmt) + gimple *at_stmt) { tree type, left, right; - struct loop *loop = get_loop (loop_nb), *chloop; + struct loop *loop = get_loop (cfun, loop_nb), *chloop; switch (TREE_CODE (chrec_before)) { @@ -847,7 +808,7 @@ static tree add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, - tree to_add, gimple at_stmt) + tree to_add, gimple *at_stmt) { tree type = chrec_type (to_add); tree res = NULL_TREE; @@ -861,14 +822,14 @@ /* This should not happen. */ return chrec_dont_know; - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, "(add_to_evolution \n"); fprintf (dump_file, " (loop_nb = %d)\n", loop_nb); fprintf (dump_file, " (chrec_before = "); - print_generic_expr (dump_file, chrec_before, 0); + print_generic_expr (dump_file, chrec_before); fprintf (dump_file, ")\n (to_add = "); - print_generic_expr (dump_file, to_add, 0); + print_generic_expr (dump_file, to_add); fprintf (dump_file, ")\n"); } @@ -879,10 +840,10 @@ res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt); - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, " (res = "); - print_generic_expr (dump_file, res, 0); + print_generic_expr (dump_file, res); fprintf (dump_file, "))\n"); } @@ -899,85 +860,54 @@ guards the exit edge. If the expression is too difficult to analyze, then give up. */ -gimple +gcond * get_loop_exit_condition (const struct loop *loop) { - gimple res = NULL; + gcond *res = NULL; edge exit_edge = single_exit (loop); - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) fprintf (dump_file, "(get_loop_exit_condition \n "); if (exit_edge) { - gimple stmt; + gimple *stmt; stmt = last_stmt (exit_edge->src); - if (gimple_code (stmt) == GIMPLE_COND) - res = stmt; + if (gcond *cond_stmt = dyn_cast <gcond *> (stmt)) + res = cond_stmt; } - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) { - print_gimple_stmt (dump_file, res, 0, 0); + print_gimple_stmt (dump_file, res, 0); fprintf (dump_file, ")\n"); } return res; } -/* Recursively determine and enqueue the exit conditions for a loop. */ - -static void -get_exit_conditions_rec (struct loop *loop, - VEC(gimple,heap) **exit_conditions) -{ - if (!loop) - return; - - /* Recurse on the inner loops, then on the next (sibling) loops. */ - get_exit_conditions_rec (loop->inner, exit_conditions); - get_exit_conditions_rec (loop->next, exit_conditions); - - if (single_exit (loop)) - { - gimple loop_condition = get_loop_exit_condition (loop); - - if (loop_condition) - VEC_safe_push (gimple, heap, *exit_conditions, loop_condition); - } -} - -/* Select the candidate loop nests for the analysis. This function - initializes the EXIT_CONDITIONS array. */ - -static void -select_loops_exit_conditions (VEC(gimple,heap) **exit_conditions) -{ - struct loop *function_body = current_loops->tree_root; - - get_exit_conditions_rec (function_body->inner, exit_conditions); -} - /* Depth first search algorithm. */ -typedef enum t_bool { +enum t_bool { t_false, t_true, t_dont_know -} t_bool; - - -static t_bool follow_ssa_edge (struct loop *loop, gimple, gimple, tree *, int); +}; + + +static t_bool follow_ssa_edge (struct loop *loop, gimple *, gphi *, + tree *, int); /* Follow the ssa edge into the binary expression RHS0 CODE RHS1. Return true if the strongly connected component has been found. */ static t_bool -follow_ssa_edge_binary (struct loop *loop, gimple at_stmt, +follow_ssa_edge_binary (struct loop *loop, gimple *at_stmt, tree type, tree rhs0, enum tree_code code, tree rhs1, - gimple halting_phi, tree *evolution_of_loop, int limit) + gphi *halting_phi, tree *evolution_of_loop, + int limit) { t_bool res = t_false; tree evol; @@ -999,27 +929,25 @@ limit++; evol = *evolution_of_loop; - res = follow_ssa_edge - (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit); - - if (res == t_true) - *evolution_of_loop = add_to_evolution + evol = add_to_evolution (loop->num, chrec_convert (type, evol, at_stmt), code, rhs1, at_stmt); - + res = follow_ssa_edge + (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit); + if (res == t_true) + *evolution_of_loop = evol; else if (res == t_false) { + *evolution_of_loop = add_to_evolution + (loop->num, + chrec_convert (type, *evolution_of_loop, at_stmt), + code, rhs0, at_stmt); res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, evolution_of_loop, limit); - if (res == t_true) - *evolution_of_loop = add_to_evolution - (loop->num, - chrec_convert (type, *evolution_of_loop, at_stmt), - code, rhs0, at_stmt); - + ; else if (res == t_dont_know) *evolution_of_loop = chrec_dont_know; } @@ -1032,15 +960,15 @@ { /* Match an assignment under the form: "a = b + ...". */ + *evolution_of_loop = add_to_evolution + (loop->num, chrec_convert (type, *evolution_of_loop, + at_stmt), + code, rhs1, at_stmt); 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_convert (type, *evolution_of_loop, - at_stmt), - code, rhs1, at_stmt); - + ; else if (res == t_dont_know) *evolution_of_loop = chrec_dont_know; } @@ -1050,15 +978,15 @@ { /* Match an assignment under the form: "a = ... + c". */ + *evolution_of_loop = add_to_evolution + (loop->num, chrec_convert (type, *evolution_of_loop, + at_stmt), + code, rhs0, at_stmt); res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, evolution_of_loop, limit); if (res == t_true) - *evolution_of_loop = add_to_evolution - (loop->num, chrec_convert (type, *evolution_of_loop, - at_stmt), - code, rhs0, at_stmt); - + ; else if (res == t_dont_know) *evolution_of_loop = chrec_dont_know; } @@ -1083,13 +1011,13 @@ if (TREE_CODE (rhs1) == SSA_NAME) limit++; + *evolution_of_loop = add_to_evolution + (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt), + MINUS_EXPR, rhs1, at_stmt); 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_convert (type, *evolution_of_loop, at_stmt), - MINUS_EXPR, rhs1, at_stmt); - + ; else if (res == t_dont_know) *evolution_of_loop = chrec_dont_know; } @@ -1111,8 +1039,9 @@ Return true if the strongly connected component has been found. */ static t_bool -follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr, - gimple halting_phi, tree *evolution_of_loop, int limit) +follow_ssa_edge_expr (struct loop *loop, gimple *at_stmt, tree expr, + gphi *halting_phi, tree *evolution_of_loop, + int limit) { enum tree_code code = TREE_CODE (expr); tree type = TREE_TYPE (expr), rhs0, rhs1; @@ -1201,8 +1130,9 @@ Return true if the strongly connected component has been found. */ static t_bool -follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt, - gimple halting_phi, tree *evolution_of_loop, int limit) +follow_ssa_edge_in_rhs (struct loop *loop, gimple *stmt, + gphi *halting_phi, tree *evolution_of_loop, + int limit) { enum tree_code code = gimple_assign_rhs_code (stmt); tree type = gimple_expr_type (stmt), rhs1, rhs2; @@ -1242,7 +1172,7 @@ /* Checks whether the I-th argument of a PHI comes from a backedge. */ static bool -backedge_phi_arg_p (gimple phi, int i) +backedge_phi_arg_p (gphi *phi, int i) { const_edge e = gimple_phi_arg_edge (phi, i); @@ -1262,8 +1192,8 @@ static inline t_bool follow_ssa_edge_in_condition_phi_branch (int i, struct loop *loop, - gimple condition_phi, - gimple halting_phi, + gphi *condition_phi, + gphi *halting_phi, tree *evolution_of_branch, tree init_cond, int limit) { @@ -1297,8 +1227,8 @@ static t_bool follow_ssa_edge_in_condition_phi (struct loop *loop, - gimple condition_phi, - gimple halting_phi, + gphi *condition_phi, + gphi *halting_phi, tree *evolution_of_loop, int limit) { int i, n; @@ -1344,8 +1274,8 @@ static t_bool follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, - gimple loop_phi_node, - gimple halting_phi, + gphi *loop_phi_node, + gphi *halting_phi, tree *evolution_of_loop, int limit) { struct loop *loop = loop_containing_stmt (loop_phi_node); @@ -1390,7 +1320,7 @@ path that is analyzed on the return walk. */ static t_bool -follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi, +follow_ssa_edge (struct loop *loop, gimple *def, gphi *halting_phi, tree *evolution_of_loop, int limit) { struct loop *def_loop; @@ -1413,7 +1343,8 @@ information and set the approximation to the main variable. */ return follow_ssa_edge_in_condition_phi - (loop, def, halting_phi, evolution_of_loop, limit); + (loop, as_a <gphi *> (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 @@ -1430,7 +1361,8 @@ /* Inner loop. */ if (flow_loop_nested_p (loop, def_loop)) return follow_ssa_edge_inner_loop_phi - (loop, def, halting_phi, evolution_of_loop, limit + 1); + (loop, as_a <gphi *> (def), halting_phi, evolution_of_loop, + limit + 1); /* Outer loop. */ return t_false; @@ -1448,31 +1380,90 @@ } +/* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP. + Handle below case and return the corresponding POLYNOMIAL_CHREC: + + # i_17 = PHI <i_13(5), 0(3)> + # _20 = PHI <_5(5), start_4(D)(3)> + ... + i_13 = i_17 + 1; + _5 = start_4(D) + i_13; + + Though variable _20 appears as a PEELED_CHREC in the form of + (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP. + + See PR41488. */ + +static tree +simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond) +{ + aff_tree aff1, aff2; + tree ev, left, right, type, step_val; + hash_map<tree, name_expansion *> *peeled_chrec_map = NULL; + + ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg)); + if (ev == NULL_TREE || TREE_CODE (ev) != POLYNOMIAL_CHREC) + return chrec_dont_know; + + left = CHREC_LEFT (ev); + right = CHREC_RIGHT (ev); + type = TREE_TYPE (left); + step_val = chrec_fold_plus (type, init_cond, right); + + /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP + if "left" equals to "init + right". */ + if (operand_equal_p (left, step_val, 0)) + { + if (dump_file && (dump_flags & TDF_SCEV)) + fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n"); + + return build_polynomial_chrec (loop->num, init_cond, right); + } + + /* Try harder to check if they are equal. */ + tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map); + tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map); + free_affine_expand_cache (&peeled_chrec_map); + aff_combination_scale (&aff2, -1); + aff_combination_add (&aff1, &aff2); + + /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP + if "left" equals to "init + right". */ + if (aff_combination_zero_p (&aff1)) + { + if (dump_file && (dump_flags & TDF_SCEV)) + fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n"); + + return build_polynomial_chrec (loop->num, init_cond, right); + } + return chrec_dont_know; +} /* Given a LOOP_PHI_NODE, this function determines the evolution function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */ static tree -analyze_evolution_in_loop (gimple loop_phi_node, +analyze_evolution_in_loop (gphi *loop_phi_node, tree init_cond) { int i, n = gimple_phi_num_args (loop_phi_node); tree evolution_function = chrec_not_analyzed_yet; struct loop *loop = loop_containing_stmt (loop_phi_node); basic_block bb; - - if (dump_file && (dump_flags & TDF_DETAILS)) + static bool simplify_peeled_chrec_p = true; + + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, "(analyze_evolution_in_loop \n"); fprintf (dump_file, " (loop_phi_node = "); - print_gimple_stmt (dump_file, loop_phi_node, 0, 0); + print_gimple_stmt (dump_file, loop_phi_node, 0); fprintf (dump_file, ")\n"); } for (i = 0; i < n; i++) { tree arg = PHI_ARG_DEF (loop_phi_node, i); - gimple ssa_chain; + gimple *ssa_chain; tree ev_fn; t_bool res; @@ -1510,23 +1501,66 @@ all the other iterations it has the value of ARG. For the moment, PEELED_CHREC nodes are not built. */ if (res != t_true) - ev_fn = chrec_dont_know; + { + ev_fn = chrec_dont_know; + /* Try to recognize POLYNOMIAL_CHREC which appears in + the form of PEELED_CHREC, but guard the process with + a bool variable to keep the analyzer from infinite + recurrence for real PEELED_RECs. */ + if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME) + { + simplify_peeled_chrec_p = false; + ev_fn = simplify_peeled_chrec (loop, arg, init_cond); + simplify_peeled_chrec_p = true; + } + } /* When there are multiple back edges of the loop (which in fact never happens currently, but nevertheless), merge their evolutions. */ evolution_function = chrec_merge (evolution_function, ev_fn); + + if (evolution_function == chrec_dont_know) + break; } - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, " (evolution_function = "); - print_generic_expr (dump_file, evolution_function, 0); + print_generic_expr (dump_file, evolution_function); fprintf (dump_file, "))\n"); } return evolution_function; } +/* Looks to see if VAR is a copy of a constant (via straightforward assignments + or degenerate phi's). If so, returns the constant; else, returns VAR. */ + +static tree +follow_copies_to_constant (tree var) +{ + tree res = var; + while (TREE_CODE (res) == SSA_NAME) + { + gimple *def = SSA_NAME_DEF_STMT (res); + if (gphi *phi = dyn_cast <gphi *> (def)) + { + if (tree rhs = degenerate_phi_result (phi)) + res = rhs; + else + break; + } + else if (gimple_assign_single_p (def)) + /* Will exit loop if not an SSA_NAME. */ + res = gimple_assign_rhs1 (def); + else + break; + } + if (CONSTANT_CLASS_P (res)) + return res; + return var; +} + /* Given a loop-phi-node, return the initial conditions of the variable on entry of the loop. When the CCP has propagated constants into the loop-phi-node, the initial condition is @@ -1535,17 +1569,17 @@ loop, and leaves this task to the on-demand tree reconstructor. */ static tree -analyze_initial_condition (gimple loop_phi_node) +analyze_initial_condition (gphi *loop_phi_node) { int i, n; tree init_cond = chrec_not_analyzed_yet; struct loop *loop = loop_containing_stmt (loop_phi_node); - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, "(analyze_initial_condition \n"); fprintf (dump_file, " (loop_phi_node = \n"); - print_gimple_stmt (dump_file, loop_phi_node, 0, 0); + print_gimple_stmt (dump_file, loop_phi_node, 0); fprintf (dump_file, ")\n"); } @@ -1579,24 +1613,14 @@ if (init_cond == chrec_not_analyzed_yet) init_cond = chrec_dont_know; - /* During early loop unrolling we do not have fully constant propagated IL. - Handle degenerate PHIs here to not miss important unrollings. */ - if (TREE_CODE (init_cond) == SSA_NAME) - { - gimple def = SSA_NAME_DEF_STMT (init_cond); - tree res; - if (gimple_code (def) == GIMPLE_PHI - && (res = degenerate_phi_result (def)) != NULL_TREE - /* Only allow invariants here, otherwise we may break - loop-closed SSA form. */ - && is_gimple_min_invariant (res)) - init_cond = res; - } - - if (dump_file && (dump_flags & TDF_DETAILS)) + /* We may not have fully constant propagated IL. Handle degenerate PHIs here + to not miss important early loop unrollings. */ + init_cond = follow_copies_to_constant (init_cond); + + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, " (init_cond = "); - print_generic_expr (dump_file, init_cond, 0); + print_generic_expr (dump_file, init_cond); fprintf (dump_file, "))\n"); } @@ -1606,25 +1630,13 @@ /* Analyze the scalar evolution for LOOP_PHI_NODE. */ static tree -interpret_loop_phi (struct loop *loop, gimple loop_phi_node) +interpret_loop_phi (struct loop *loop, gphi *loop_phi_node) { tree res; struct loop *phi_loop = loop_containing_stmt (loop_phi_node); tree init_cond; - if (phi_loop != loop) - { - struct loop *subloop; - tree evolution_fn = analyze_scalar_evolution - (phi_loop, PHI_RESULT (loop_phi_node)); - - /* Dive one level deeper. */ - subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1); - - /* Interpret the subloop. */ - res = compute_overall_effect_of_inner_loop (subloop, evolution_fn); - return res; - } + gcc_assert (phi_loop == loop); /* Otherwise really interpret the loop phi. */ init_cond = analyze_initial_condition (loop_phi_node); @@ -1642,8 +1654,8 @@ else if (TREE_CODE (res) == POLYNOMIAL_CHREC) new_init = CHREC_LEFT (res); STRIP_USELESS_TYPE_CONVERSION (new_init); - gcc_assert (TREE_CODE (new_init) != POLYNOMIAL_CHREC); - if (!operand_equal_p (init_cond, new_init, 0)) + if (TREE_CODE (new_init) == POLYNOMIAL_CHREC + || !operand_equal_p (init_cond, new_init, 0)) return chrec_dont_know; } @@ -1655,7 +1667,7 @@ analyzed. */ static tree -interpret_condition_phi (struct loop *loop, gimple condition_phi) +interpret_condition_phi (struct loop *loop, gphi *condition_phi) { int i, n = gimple_phi_num_args (condition_phi); tree res = chrec_not_analyzed_yet; @@ -1674,6 +1686,8 @@ (loop, PHI_ARG_DEF (condition_phi, i)); res = chrec_merge (res, branch_chrec); + if (res == chrec_dont_know) + break; } return res; @@ -1687,10 +1701,11 @@ analyze the effect of an inner loop: see interpret_loop_phi. */ static tree -interpret_rhs_expr (struct loop *loop, gimple at_stmt, +interpret_rhs_expr (struct loop *loop, gimple *at_stmt, tree type, tree rhs1, enum tree_code code, tree rhs2) { - tree res, chrec1, chrec2; + tree res, chrec1, chrec2, ctype; + gimple *def; if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) { @@ -1712,53 +1727,141 @@ switch (code) { case ADDR_EXPR: - /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */ - if (TREE_CODE (TREE_OPERAND (rhs1, 0)) != MEM_REF) - { - res = chrec_dont_know; - break; - } - - rhs2 = TREE_OPERAND (TREE_OPERAND (rhs1, 0), 1); - rhs1 = TREE_OPERAND (TREE_OPERAND (rhs1, 0), 0); - /* Fall through. */ + if (TREE_CODE (TREE_OPERAND (rhs1, 0)) == MEM_REF + || handled_component_p (TREE_OPERAND (rhs1, 0))) + { + machine_mode mode; + HOST_WIDE_INT bitsize, bitpos; + int unsignedp, reversep; + int volatilep = 0; + tree base, offset; + tree chrec3; + tree unitpos; + + base = get_inner_reference (TREE_OPERAND (rhs1, 0), + &bitsize, &bitpos, &offset, &mode, + &unsignedp, &reversep, &volatilep); + + if (TREE_CODE (base) == MEM_REF) + { + rhs2 = TREE_OPERAND (base, 1); + rhs1 = TREE_OPERAND (base, 0); + + chrec1 = analyze_scalar_evolution (loop, rhs1); + chrec2 = analyze_scalar_evolution (loop, rhs2); + chrec1 = chrec_convert (type, chrec1, at_stmt); + chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt); + chrec1 = instantiate_parameters (loop, chrec1); + chrec2 = instantiate_parameters (loop, chrec2); + res = chrec_fold_plus (type, chrec1, chrec2); + } + else + { + chrec1 = analyze_scalar_evolution_for_address_of (loop, base); + chrec1 = chrec_convert (type, chrec1, at_stmt); + res = chrec1; + } + + if (offset != NULL_TREE) + { + chrec2 = analyze_scalar_evolution (loop, offset); + chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt); + chrec2 = instantiate_parameters (loop, chrec2); + res = chrec_fold_plus (type, res, chrec2); + } + + if (bitpos != 0) + { + gcc_assert ((bitpos % BITS_PER_UNIT) == 0); + + unitpos = size_int (bitpos / BITS_PER_UNIT); + chrec3 = analyze_scalar_evolution (loop, unitpos); + chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt); + chrec3 = instantiate_parameters (loop, chrec3); + res = chrec_fold_plus (type, res, chrec3); + } + } + else + res = chrec_dont_know; + break; case POINTER_PLUS_EXPR: chrec1 = analyze_scalar_evolution (loop, rhs1); chrec2 = analyze_scalar_evolution (loop, rhs2); chrec1 = chrec_convert (type, chrec1, at_stmt); - chrec2 = chrec_convert (sizetype, chrec2, at_stmt); + chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt); + chrec1 = instantiate_parameters (loop, chrec1); + chrec2 = instantiate_parameters (loop, chrec2); res = chrec_fold_plus (type, chrec1, chrec2); break; case PLUS_EXPR: chrec1 = analyze_scalar_evolution (loop, rhs1); chrec2 = analyze_scalar_evolution (loop, rhs2); - chrec1 = chrec_convert (type, chrec1, at_stmt); - chrec2 = chrec_convert (type, chrec2, at_stmt); - res = chrec_fold_plus (type, chrec1, chrec2); + ctype = type; + /* When the stmt is conditionally executed re-write the CHREC + into a form that has well-defined behavior on overflow. */ + if (at_stmt + && INTEGRAL_TYPE_P (type) + && ! TYPE_OVERFLOW_WRAPS (type) + && ! dominated_by_p (CDI_DOMINATORS, loop->latch, + gimple_bb (at_stmt))) + ctype = unsigned_type_for (type); + chrec1 = chrec_convert (ctype, chrec1, at_stmt); + chrec2 = chrec_convert (ctype, chrec2, at_stmt); + chrec1 = instantiate_parameters (loop, chrec1); + chrec2 = instantiate_parameters (loop, chrec2); + res = chrec_fold_plus (ctype, chrec1, chrec2); + if (type != ctype) + res = chrec_convert (type, res, at_stmt); break; case MINUS_EXPR: chrec1 = analyze_scalar_evolution (loop, rhs1); chrec2 = analyze_scalar_evolution (loop, rhs2); - chrec1 = chrec_convert (type, chrec1, at_stmt); - chrec2 = chrec_convert (type, chrec2, at_stmt); - res = chrec_fold_minus (type, chrec1, chrec2); + ctype = type; + /* When the stmt is conditionally executed re-write the CHREC + into a form that has well-defined behavior on overflow. */ + if (at_stmt + && INTEGRAL_TYPE_P (type) + && ! TYPE_OVERFLOW_WRAPS (type) + && ! dominated_by_p (CDI_DOMINATORS, + loop->latch, gimple_bb (at_stmt))) + ctype = unsigned_type_for (type); + chrec1 = chrec_convert (ctype, chrec1, at_stmt); + chrec2 = chrec_convert (ctype, chrec2, at_stmt); + chrec1 = instantiate_parameters (loop, chrec1); + chrec2 = instantiate_parameters (loop, chrec2); + res = chrec_fold_minus (ctype, chrec1, chrec2); + if (type != ctype) + res = chrec_convert (type, res, at_stmt); break; case NEGATE_EXPR: chrec1 = analyze_scalar_evolution (loop, rhs1); - chrec1 = chrec_convert (type, chrec1, at_stmt); + ctype = type; + /* When the stmt is conditionally executed re-write the CHREC + into a form that has well-defined behavior on overflow. */ + if (at_stmt + && INTEGRAL_TYPE_P (type) + && ! TYPE_OVERFLOW_WRAPS (type) + && ! dominated_by_p (CDI_DOMINATORS, + loop->latch, gimple_bb (at_stmt))) + ctype = unsigned_type_for (type); + chrec1 = chrec_convert (ctype, chrec1, at_stmt); /* TYPE may be integer, real or complex, so use fold_convert. */ - res = chrec_fold_multiply (type, chrec1, - fold_convert (type, integer_minus_one_node)); + chrec1 = instantiate_parameters (loop, chrec1); + res = chrec_fold_multiply (ctype, chrec1, + fold_convert (ctype, integer_minus_one_node)); + if (type != ctype) + res = chrec_convert (type, res, at_stmt); break; case BIT_NOT_EXPR: /* Handle ~X as -1 - X. */ chrec1 = analyze_scalar_evolution (loop, rhs1); chrec1 = chrec_convert (type, chrec1, at_stmt); + chrec1 = instantiate_parameters (loop, chrec1); res = chrec_fold_minus (type, fold_convert (type, integer_minus_one_node), chrec1); @@ -1767,14 +1870,96 @@ case MULT_EXPR: chrec1 = analyze_scalar_evolution (loop, rhs1); chrec2 = analyze_scalar_evolution (loop, rhs2); - chrec1 = chrec_convert (type, chrec1, at_stmt); - chrec2 = chrec_convert (type, chrec2, at_stmt); - res = chrec_fold_multiply (type, chrec1, chrec2); + ctype = type; + /* When the stmt is conditionally executed re-write the CHREC + into a form that has well-defined behavior on overflow. */ + if (at_stmt + && INTEGRAL_TYPE_P (type) + && ! TYPE_OVERFLOW_WRAPS (type) + && ! dominated_by_p (CDI_DOMINATORS, + loop->latch, gimple_bb (at_stmt))) + ctype = unsigned_type_for (type); + chrec1 = chrec_convert (ctype, chrec1, at_stmt); + chrec2 = chrec_convert (ctype, chrec2, at_stmt); + chrec1 = instantiate_parameters (loop, chrec1); + chrec2 = instantiate_parameters (loop, chrec2); + res = chrec_fold_multiply (ctype, chrec1, chrec2); + if (type != ctype) + res = chrec_convert (type, res, at_stmt); + break; + + case LSHIFT_EXPR: + { + /* Handle A<<B as A * (1<<B). */ + tree uns = unsigned_type_for (type); + chrec1 = analyze_scalar_evolution (loop, rhs1); + chrec2 = analyze_scalar_evolution (loop, rhs2); + chrec1 = chrec_convert (uns, chrec1, at_stmt); + chrec1 = instantiate_parameters (loop, chrec1); + chrec2 = instantiate_parameters (loop, chrec2); + + tree one = build_int_cst (uns, 1); + chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2); + res = chrec_fold_multiply (uns, chrec1, chrec2); + res = chrec_convert (type, res, at_stmt); + } break; CASE_CONVERT: - chrec1 = analyze_scalar_evolution (loop, rhs1); - res = chrec_convert (type, chrec1, at_stmt); + /* In case we have a truncation of a widened operation that in + the truncated type has undefined overflow behavior analyze + the operation done in an unsigned type of the same precision + as the final truncation. We cannot derive a scalar evolution + for the widened operation but for the truncated result. */ + if (TREE_CODE (type) == INTEGER_TYPE + && TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE + && TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1)) + && TYPE_OVERFLOW_UNDEFINED (type) + && TREE_CODE (rhs1) == SSA_NAME + && (def = SSA_NAME_DEF_STMT (rhs1)) + && is_gimple_assign (def) + && TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary + && TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST) + { + tree utype = unsigned_type_for (type); + chrec1 = interpret_rhs_expr (loop, at_stmt, utype, + gimple_assign_rhs1 (def), + gimple_assign_rhs_code (def), + gimple_assign_rhs2 (def)); + } + else + chrec1 = analyze_scalar_evolution (loop, rhs1); + res = chrec_convert (type, chrec1, at_stmt, true, rhs1); + break; + + case BIT_AND_EXPR: + /* Given int variable A, handle A&0xffff as (int)(unsigned short)A. + If A is SCEV and its value is in the range of representable set + of type unsigned short, the result expression is a (no-overflow) + SCEV. */ + res = chrec_dont_know; + if (tree_fits_uhwi_p (rhs2)) + { + int precision; + unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2); + + val ++; + /* Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or + it's not the maximum value of a smaller type than rhs1. */ + if (val != 0 + && (precision = exact_log2 (val)) > 0 + && (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1))) + { + tree utype = build_nonstandard_integer_type (precision, 1); + + if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1))) + { + chrec1 = analyze_scalar_evolution (loop, rhs1); + chrec1 = chrec_convert (utype, chrec1, at_stmt); + res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt); + } + } + } break; default: @@ -1788,7 +1973,7 @@ /* Interpret the expression EXPR. */ static tree -interpret_expr (struct loop *loop, gimple at_stmt, tree expr) +interpret_expr (struct loop *loop, gimple *at_stmt, tree expr) { enum tree_code code; tree type = TREE_TYPE (expr), op0, op1; @@ -1796,7 +1981,8 @@ if (automatically_generated_chrec_p (expr)) return expr; - if (TREE_CODE (expr) == POLYNOMIAL_CHREC) + if (TREE_CODE (expr) == POLYNOMIAL_CHREC + || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS) return chrec_dont_know; extract_ops_from_tree (expr, &code, &op0, &op1); @@ -1808,7 +1994,7 @@ /* Interpret the rhs of the assignment STMT. */ static tree -interpret_gimple_assign (struct loop *loop, gimple stmt) +interpret_gimple_assign (struct loop *loop, gimple *stmt) { tree type = TREE_TYPE (gimple_assign_lhs (stmt)); enum tree_code code = gimple_assign_rhs_code (stmt); @@ -1826,71 +2012,38 @@ - instantiate_parameters. */ -/* Compute and return the evolution function in WRTO_LOOP, the nearest - common ancestor of DEF_LOOP and USE_LOOP. */ - -static tree -compute_scalar_evolution_in_loop (struct loop *wrto_loop, - struct loop *def_loop, - tree ev) -{ - bool val; - tree res; - - if (def_loop == wrto_loop) - return ev; - - def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1); - res = compute_overall_effect_of_inner_loop (def_loop, ev); - - if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val) - return res; - - return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet); -} - /* Helper recursive function. */ static tree -analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) +analyze_scalar_evolution_1 (struct loop *loop, tree var) { - tree type = TREE_TYPE (var); - gimple def; + gimple *def; basic_block bb; struct loop *def_loop; - - if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE) - return chrec_dont_know; + tree res; if (TREE_CODE (var) != SSA_NAME) return interpret_expr (loop, NULL, var); def = SSA_NAME_DEF_STMT (var); bb = gimple_bb (def); - def_loop = bb ? bb->loop_father : NULL; - - if (bb == NULL - || !flow_bb_inside_loop_p (loop, bb)) + def_loop = bb->loop_father; + + if (!flow_bb_inside_loop_p (loop, bb)) { - /* Keep the symbolic form. */ - res = var; - goto set_and_end; - } - - if (res != chrec_not_analyzed_yet) - { - if (loop != bb->loop_father) - res = compute_scalar_evolution_in_loop - (find_common_loop (loop, bb->loop_father), bb->loop_father, res); - + /* Keep symbolic form, but look through obvious copies for constants. */ + res = follow_copies_to_constant (var); goto set_and_end; } if (loop != def_loop) { - res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet); - res = compute_scalar_evolution_in_loop (loop, def_loop, res); - + res = analyze_scalar_evolution_1 (def_loop, var); + struct loop *loop_to_skip = superloop_at_depth (def_loop, + loop_depth (loop) + 1); + res = compute_overall_effect_of_inner_loop (loop_to_skip, res); + if (chrec_contains_symbols_defined_in_loop (res, loop->num)) + res = analyze_scalar_evolution_1 (loop, res); goto set_and_end; } @@ -1902,9 +2055,9 @@ case GIMPLE_PHI: if (loop_phi_node_p (def)) - res = interpret_loop_phi (loop, def); + res = interpret_loop_phi (loop, as_a <gphi *> (def)); else - res = interpret_condition_phi (loop, def); + res = interpret_condition_phi (loop, as_a <gphi *> (def)); break; default: @@ -1942,24 +2095,37 @@ { tree res; - if (dump_file && (dump_flags & TDF_DETAILS)) + /* ??? Fix callers. */ + if (! loop) + return var; + + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, "(analyze_scalar_evolution \n"); fprintf (dump_file, " (loop_nb = %d)\n", loop->num); fprintf (dump_file, " (scalar = "); - print_generic_expr (dump_file, var, 0); + print_generic_expr (dump_file, var); fprintf (dump_file, ")\n"); } res = get_scalar_evolution (block_before_loop (loop), var); - res = analyze_scalar_evolution_1 (loop, var, res); - - if (dump_file && (dump_flags & TDF_DETAILS)) + if (res == chrec_not_analyzed_yet) + res = analyze_scalar_evolution_1 (loop, var); + + if (dump_file && (dump_flags & TDF_SCEV)) fprintf (dump_file, ")\n"); return res; } +/* Analyzes and returns the scalar evolution of VAR address in LOOP. */ + +static tree +analyze_scalar_evolution_for_address_of (struct loop *loop, tree var) +{ + return analyze_scalar_evolution (loop, build_fold_addr_expr (var)); +} + /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to WRTO_LOOP (which should be a superloop of USE_LOOP) @@ -2020,7 +2186,7 @@ /* We cannot just do tmp = analyze_scalar_evolution (use_loop, version); - ev = resolve_mixers (wrto_loop, tmp); + ev = resolve_mixers (wrto_loop, tmp, folded_casts); as resolve_mixers would query the scalar evolution with respect to wrto_loop. For example, in the situation described in the function @@ -2029,9 +2195,9 @@ analyze_scalar_evolution (use_loop, version) = k2 - and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1 - is 100, which is a wrong result, since we are interested in the - value in loop 3. + and resolve_mixers (loop1, k2, folded_casts) finds that the value of + k2 in loop 1 is 100, which is a wrong result, since we are interested + in the value in loop 3. Instead, we need to proceed from use_loop to wrto_loop loop by loop, each time checking that there is no evolution in the inner loop. */ @@ -2041,10 +2207,7 @@ while (1) { tmp = analyze_scalar_evolution (use_loop, ev); - ev = resolve_mixers (use_loop, tmp); - - if (folded_casts && tmp != ev) - *folded_casts = true; + ev = resolve_mixers (use_loop, tmp, folded_casts); if (use_loop == wrto_loop) return ev; @@ -2060,45 +2223,82 @@ } } -/* Returns from CACHE the value for VERSION instantiated below - INSTANTIATED_BELOW block. */ - -static tree -get_instantiated_value (htab_t cache, basic_block instantiated_below, - tree version) + +/* Hashtable helpers for a temporary hash-table used when + instantiating a CHREC or resolving mixers. For this use + instantiated_below is always the same. */ + +struct instantiate_cache_type +{ + htab_t map; + vec<scev_info_str> entries; + + instantiate_cache_type () : map (NULL), entries (vNULL) {} + ~instantiate_cache_type (); + tree get (unsigned slot) { return entries[slot].chrec; } + void set (unsigned slot, tree chrec) { entries[slot].chrec = chrec; } +}; + +instantiate_cache_type::~instantiate_cache_type () { - struct scev_info_str *info, pattern; - - pattern.var = version; - pattern.instantiated_below = instantiated_below; - info = (struct scev_info_str *) htab_find (cache, &pattern); - - if (info) - return info->chrec; - else - return NULL_TREE; + if (map != NULL) + { + htab_delete (map); + entries.release (); + } +} + +/* Cache to avoid infinite recursion when instantiating an SSA name. + Live during the outermost instantiate_scev or resolve_mixers call. */ +static instantiate_cache_type *global_cache; + +/* Computes a hash function for database element ELT. */ + +static inline hashval_t +hash_idx_scev_info (const void *elt_) +{ + unsigned idx = ((size_t) elt_) - 2; + return scev_info_hasher::hash (&global_cache->entries[idx]); } -/* Sets in CACHE the value of VERSION instantiated below basic block - INSTANTIATED_BELOW to VAL. */ - -static void -set_instantiated_value (htab_t cache, basic_block instantiated_below, - tree version, tree val) +/* Compares database elements E1 and E2. */ + +static inline int +eq_idx_scev_info (const void *e1, const void *e2) +{ + unsigned idx1 = ((size_t) e1) - 2; + return scev_info_hasher::equal (&global_cache->entries[idx1], + (const scev_info_str *) e2); +} + +/* Returns from CACHE the slot number of the cached chrec for NAME. */ + +static unsigned +get_instantiated_value_entry (instantiate_cache_type &cache, + tree name, edge instantiate_below) { - struct scev_info_str *info, pattern; - PTR *slot; - - pattern.var = version; - pattern.instantiated_below = instantiated_below; - slot = htab_find_slot (cache, &pattern, INSERT); - + if (!cache.map) + { + cache.map = htab_create (10, hash_idx_scev_info, eq_idx_scev_info, NULL); + cache.entries.create (10); + } + + scev_info_str e; + e.name_version = SSA_NAME_VERSION (name); + e.instantiated_below = instantiate_below->dest->index; + void **slot = htab_find_slot_with_hash (cache.map, &e, + scev_info_hasher::hash (&e), INSERT); if (!*slot) - *slot = new_scev_info_str (instantiated_below, version); - info = (struct scev_info_str *) *slot; - info->chrec = val; + { + e.chrec = chrec_not_analyzed_yet; + *slot = (void *)(size_t)(cache.entries.length () + 2); + cache.entries.safe_push (e); + } + + return ((size_t)*slot) - 2; } + /* Return the closed_loop_phi node for VAR. If there is none, return NULL_TREE. */ @@ -2107,8 +2307,8 @@ { struct loop *loop; edge exit; - gimple phi; - gimple_stmt_iterator psi; + gphi *phi; + gphi_iterator psi; if (var == NULL_TREE || TREE_CODE (var) != SSA_NAME) @@ -2121,7 +2321,7 @@ for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi)) { - phi = gsi_stmt (psi); + phi = psi.phi (); if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var) return PHI_RESULT (phi); } @@ -2129,8 +2329,8 @@ return NULL_TREE; } -static tree instantiate_scev_r (basic_block, struct loop *, tree, bool, - htab_t, int); +static tree instantiate_scev_r (edge, struct loop *, struct loop *, + tree, bool *, int); /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. @@ -2139,27 +2339,28 @@ CACHE is the cache of already instantiated values. - FOLD_CONVERSIONS should be set to true when the conversions that - may wrap in signed/pointer type are folded, as long as the value of - the chrec is preserved. + Variable pointed by FOLD_CONVERSIONS is set to TRUE when the + conversions that may wrap in signed/pointer type are folded, as long + as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL + then we don't do such fold. SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_name (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, - bool fold_conversions, htab_t cache, int size_expr) +instantiate_scev_name (edge instantiate_below, + struct loop *evolution_loop, struct loop *inner_loop, + tree chrec, + bool *fold_conversions, + int size_expr) { tree res; struct loop *def_loop; basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec)); - /* A parameter (or loop invariant and we do not want to include - evolutions in outer loops), nothing to do. */ + /* A parameter, nothing to do. */ if (!def_bb - || loop_depth (def_bb->loop_father) == 0 - || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb)) + || !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest)) return chrec; /* We cache the value of instantiated variable to avoid exponential @@ -2171,15 +2372,61 @@ | a_2 -> {0, +, 1, +, a_2}_1 */ - res = get_instantiated_value (cache, instantiate_below, chrec); - if (res) - return res; - - res = chrec_dont_know; - set_instantiated_value (cache, instantiate_below, chrec, res); + unsigned si = get_instantiated_value_entry (*global_cache, + chrec, instantiate_below); + if (global_cache->get (si) != chrec_not_analyzed_yet) + return global_cache->get (si); + + /* On recursion return chrec_dont_know. */ + global_cache->set (si, chrec_dont_know); def_loop = find_common_loop (evolution_loop, def_bb->loop_father); + if (! dominated_by_p (CDI_DOMINATORS, + def_loop->header, instantiate_below->dest)) + { + gimple *def = SSA_NAME_DEF_STMT (chrec); + if (gassign *ass = dyn_cast <gassign *> (def)) + { + switch (gimple_assign_rhs_class (ass)) + { + case GIMPLE_UNARY_RHS: + { + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, + inner_loop, gimple_assign_rhs1 (ass), + fold_conversions, size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + res = fold_build1 (gimple_assign_rhs_code (ass), + TREE_TYPE (chrec), op0); + break; + } + case GIMPLE_BINARY_RHS: + { + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, + inner_loop, gimple_assign_rhs1 (ass), + fold_conversions, size_expr); + if (op0 == chrec_dont_know) + return chrec_dont_know; + tree op1 = instantiate_scev_r (instantiate_below, evolution_loop, + inner_loop, gimple_assign_rhs2 (ass), + fold_conversions, size_expr); + if (op1 == chrec_dont_know) + return chrec_dont_know; + res = fold_build2 (gimple_assign_rhs_code (ass), + TREE_TYPE (chrec), op0, op1); + break; + } + default: + res = chrec_dont_know; + } + } + else + res = chrec_dont_know; + global_cache->set (si, res); + return res; + } + /* If the analysis yields a parametric chrec, instantiate the result again. */ res = analyze_scalar_evolution (def_loop, chrec); @@ -2207,20 +2454,31 @@ loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec)); res = analyze_scalar_evolution (loop, chrec); res = compute_overall_effect_of_inner_loop (loop, res); - res = instantiate_scev_r (instantiate_below, evolution_loop, res, - fold_conversions, cache, size_expr); + res = instantiate_scev_r (instantiate_below, evolution_loop, + inner_loop, res, + fold_conversions, size_expr); } - else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below, - gimple_bb (SSA_NAME_DEF_STMT (res)))) + else if (dominated_by_p (CDI_DOMINATORS, + gimple_bb (SSA_NAME_DEF_STMT (res)), + instantiate_below->dest)) res = chrec_dont_know; } else if (res != chrec_dont_know) - res = instantiate_scev_r (instantiate_below, evolution_loop, res, - fold_conversions, cache, size_expr); + { + if (inner_loop + && def_bb->loop_father != inner_loop + && !flow_loop_nested_p (def_bb->loop_father, inner_loop)) + /* ??? We could try to compute the overall effect of the loop here. */ + res = chrec_dont_know; + else + res = instantiate_scev_r (instantiate_below, evolution_loop, + inner_loop, res, + fold_conversions, size_expr); + } /* Store the correct value to the cache. */ - set_instantiated_value (cache, instantiate_below, chrec, res); + global_cache->set (si, res); return res; } @@ -2231,27 +2489,30 @@ CACHE is the cache of already instantiated values. - FOLD_CONVERSIONS should be set to true when the conversions that - may wrap in signed/pointer type are folded, as long as the value of - the chrec is preserved. + Variable pointed by FOLD_CONVERSIONS is set to TRUE when the + conversions that may wrap in signed/pointer type are folded, as long + as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL + then we don't do such fold. SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_poly (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, - bool fold_conversions, htab_t cache, int size_expr) +instantiate_scev_poly (edge instantiate_below, + struct loop *evolution_loop, struct loop *, + tree chrec, bool *fold_conversions, int size_expr) { tree op1; tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, - CHREC_LEFT (chrec), fold_conversions, cache, + get_chrec_loop (chrec), + CHREC_LEFT (chrec), fold_conversions, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; op1 = instantiate_scev_r (instantiate_below, evolution_loop, - CHREC_RIGHT (chrec), fold_conversions, cache, + get_chrec_loop (chrec), + CHREC_RIGHT (chrec), fold_conversions, size_expr); if (op1 == chrec_dont_know) return chrec_dont_know; @@ -2259,19 +2520,8 @@ if (CHREC_LEFT (chrec) != op0 || CHREC_RIGHT (chrec) != op1) { - unsigned var = CHREC_VARIABLE (chrec); - - /* When the instantiated stride or base has an evolution in an - innermost loop, return chrec_dont_know, as this is not a - valid SCEV representation. In the reduced testcase for - PR40281 we would have {0, +, {1, +, 1}_2}_1 that has no - meaning. */ - if ((tree_is_chrec (op0) && CHREC_VARIABLE (op0) > var) - || (tree_is_chrec (op1) && CHREC_VARIABLE (op1) > var)) - return chrec_dont_know; - op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL); - chrec = build_polynomial_chrec (var, op0, op1); + chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1); } return chrec; @@ -2284,29 +2534,29 @@ CACHE is the cache of already instantiated values. - FOLD_CONVERSIONS should be set to true when the conversions that - may wrap in signed/pointer type are folded, as long as the value of - the chrec is preserved. + Variable pointed by FOLD_CONVERSIONS is set to TRUE when the + conversions that may wrap in signed/pointer type are folded, as long + as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL + then we don't do such fold. SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_binary (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, enum tree_code code, +instantiate_scev_binary (edge instantiate_below, + struct loop *evolution_loop, struct loop *inner_loop, + tree chrec, enum tree_code code, tree type, tree c0, tree c1, - bool fold_conversions, htab_t cache, int size_expr) + bool *fold_conversions, int size_expr) { tree op1; - tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, - c0, fold_conversions, cache, - size_expr); + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop, + c0, fold_conversions, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - op1 = instantiate_scev_r (instantiate_below, evolution_loop, - c1, fold_conversions, cache, - size_expr); + op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop, + c1, fold_conversions, size_expr); if (op1 == chrec_dont_know) return chrec_dont_know; @@ -2339,81 +2589,50 @@ /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. - "CHREC" is an array reference to be instantiated. + "CHREC" that stands for a convert expression "(TYPE) OP" is to be + instantiated. CACHE is the cache of already instantiated values. - FOLD_CONVERSIONS should be set to true when the conversions that - may wrap in signed/pointer type are folded, as long as the value of - the chrec is preserved. + Variable pointed by FOLD_CONVERSIONS is set to TRUE when the + conversions that may wrap in signed/pointer type are folded, as long + as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL + then we don't do such fold. SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_array_ref (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, - bool fold_conversions, htab_t cache, int size_expr) +instantiate_scev_convert (edge instantiate_below, + struct loop *evolution_loop, struct loop *inner_loop, + tree chrec, tree type, tree op, + bool *fold_conversions, int size_expr) { - tree res; - tree index = TREE_OPERAND (chrec, 1); - tree op1 = instantiate_scev_r (instantiate_below, evolution_loop, index, - fold_conversions, cache, size_expr); - - if (op1 == chrec_dont_know) - return chrec_dont_know; - - if (chrec && op1 == index) - return chrec; - - res = unshare_expr (chrec); - TREE_OPERAND (res, 1) = op1; - return res; -} - -/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW - and EVOLUTION_LOOP, that were left under a symbolic form. - - "CHREC" that stands for a convert expression "(TYPE) OP" is to be - instantiated. - - CACHE is the cache of already instantiated values. - - FOLD_CONVERSIONS should be set to true when the conversions that - may wrap in signed/pointer type are folded, as long as the value of - the chrec is preserved. - - SIZE_EXPR is used for computing the size of the expression to be - instantiated, and to stop if it exceeds some limit. */ - -static tree -instantiate_scev_convert (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, - tree type, tree op, - bool fold_conversions, htab_t cache, int size_expr) -{ - tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op, - fold_conversions, cache, size_expr); + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, + inner_loop, op, + fold_conversions, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; if (fold_conversions) { - tree tmp = chrec_convert_aggressive (type, op0); + tree tmp = chrec_convert_aggressive (type, op0, fold_conversions); if (tmp) return tmp; + + /* 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 (*fold_conversions) + { + if (chrec && op0 == op) + return chrec; + + return fold_convert (type, op0); + } } - if (chrec && op0 == op) - 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 (fold_conversions) - return fold_convert (type, op0); - return chrec_convert (type, op0, NULL); } @@ -2426,21 +2645,24 @@ CACHE is the cache of already instantiated values. - FOLD_CONVERSIONS should be set to true when the conversions that - may wrap in signed/pointer type are folded, as long as the value of - the chrec is preserved. + Variable pointed by FOLD_CONVERSIONS is set to TRUE when the + conversions that may wrap in signed/pointer type are folded, as long + as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL + then we don't do such fold. SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_not (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, +instantiate_scev_not (edge instantiate_below, + struct loop *evolution_loop, struct loop *inner_loop, + tree chrec, enum tree_code code, tree type, tree op, - bool fold_conversions, htab_t cache, int size_expr) + bool *fold_conversions, int size_expr) { - tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, op, - fold_conversions, cache, size_expr); + tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, + inner_loop, op, + fold_conversions, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; @@ -2470,139 +2692,23 @@ /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. - CHREC is an expression with 3 operands to be instantiated. + CHREC is the scalar evolution to instantiate. CACHE is the cache of already instantiated values. - FOLD_CONVERSIONS should be set to true when the conversions that - may wrap in signed/pointer type are folded, as long as the value of - the chrec is preserved. - - SIZE_EXPR is used for computing the size of the expression to be - instantiated, and to stop if it exceeds some limit. */ - -static tree -instantiate_scev_3 (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, - bool fold_conversions, htab_t cache, int size_expr) -{ - tree op1, op2; - tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), - fold_conversions, cache, size_expr); - if (op0 == chrec_dont_know) - return chrec_dont_know; - - op1 = instantiate_scev_r (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 1), - fold_conversions, cache, size_expr); - if (op1 == chrec_dont_know) - return chrec_dont_know; - - op2 = instantiate_scev_r (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 2), - fold_conversions, cache, size_expr); - if (op2 == chrec_dont_know) - return chrec_dont_know; - - 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); -} - -/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW - and EVOLUTION_LOOP, that were left under a symbolic form. - - CHREC is an expression with 2 operands to be instantiated. - - CACHE is the cache of already instantiated values. - - FOLD_CONVERSIONS should be set to true when the conversions that - may wrap in signed/pointer type are folded, as long as the value of - the chrec is preserved. + Variable pointed by FOLD_CONVERSIONS is set to TRUE when the + conversions that may wrap in signed/pointer type are folded, as long + as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL + then we don't do such fold. SIZE_EXPR is used for computing the size of the expression to be instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_2 (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, - bool fold_conversions, htab_t cache, int size_expr) -{ - tree op1; - tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), - fold_conversions, cache, size_expr); - if (op0 == chrec_dont_know) - return chrec_dont_know; - - op1 = instantiate_scev_r (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 1), - fold_conversions, cache, size_expr); - if (op1 == chrec_dont_know) - return chrec_dont_know; - - if (op0 == TREE_OPERAND (chrec, 0) - && op1 == TREE_OPERAND (chrec, 1)) - return chrec; - - return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); -} - -/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW - and EVOLUTION_LOOP, that were left under a symbolic form. - - CHREC is an expression with 2 operands to be instantiated. - - CACHE is the cache of already instantiated values. - - FOLD_CONVERSIONS should be set to true when the conversions that - may wrap in signed/pointer type are folded, as long as the value of - the chrec is preserved. - - SIZE_EXPR is used for computing the size of the expression to be - instantiated, and to stop if it exceeds some limit. */ - -static tree -instantiate_scev_1 (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, - bool fold_conversions, htab_t cache, int size_expr) -{ - tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, - TREE_OPERAND (chrec, 0), - fold_conversions, cache, size_expr); - - if (op0 == chrec_dont_know) - return chrec_dont_know; - - if (op0 == TREE_OPERAND (chrec, 0)) - return chrec; - - return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0); -} - -/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW - and EVOLUTION_LOOP, that were left under a symbolic form. - - CHREC is the scalar evolution to instantiate. - - CACHE is the cache of already instantiated values. - - FOLD_CONVERSIONS should be set to true when the conversions that - may wrap in signed/pointer type are folded, as long as the value of - the chrec is preserved. - - SIZE_EXPR is used for computing the size of the expression to be - instantiated, and to stop if it exceeds some limit. */ - -static tree -instantiate_scev_r (basic_block instantiate_below, - struct loop *evolution_loop, tree chrec, - bool fold_conversions, htab_t cache, int size_expr) +instantiate_scev_r (edge instantiate_below, + struct loop *evolution_loop, struct loop *inner_loop, + tree chrec, + bool *fold_conversions, int size_expr) { /* Give up if the expression is larger than the MAX that we allow. */ if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) @@ -2616,75 +2722,55 @@ switch (TREE_CODE (chrec)) { case SSA_NAME: - return instantiate_scev_name (instantiate_below, evolution_loop, chrec, - fold_conversions, cache, size_expr); + return instantiate_scev_name (instantiate_below, evolution_loop, + inner_loop, chrec, + fold_conversions, size_expr); case POLYNOMIAL_CHREC: - return instantiate_scev_poly (instantiate_below, evolution_loop, chrec, - fold_conversions, cache, size_expr); + return instantiate_scev_poly (instantiate_below, evolution_loop, + inner_loop, chrec, + fold_conversions, size_expr); case POINTER_PLUS_EXPR: case PLUS_EXPR: case MINUS_EXPR: case MULT_EXPR: - return instantiate_scev_binary (instantiate_below, evolution_loop, chrec, + return instantiate_scev_binary (instantiate_below, evolution_loop, + inner_loop, chrec, TREE_CODE (chrec), chrec_type (chrec), TREE_OPERAND (chrec, 0), TREE_OPERAND (chrec, 1), - fold_conversions, cache, size_expr); + fold_conversions, size_expr); CASE_CONVERT: - return instantiate_scev_convert (instantiate_below, evolution_loop, chrec, + return instantiate_scev_convert (instantiate_below, evolution_loop, + inner_loop, chrec, TREE_TYPE (chrec), TREE_OPERAND (chrec, 0), - fold_conversions, cache, size_expr); + fold_conversions, size_expr); case NEGATE_EXPR: case BIT_NOT_EXPR: - return instantiate_scev_not (instantiate_below, evolution_loop, chrec, + return instantiate_scev_not (instantiate_below, evolution_loop, + inner_loop, chrec, TREE_CODE (chrec), TREE_TYPE (chrec), TREE_OPERAND (chrec, 0), - fold_conversions, cache, size_expr); - + fold_conversions, size_expr); + + case ADDR_EXPR: + if (is_gimple_min_invariant (chrec)) + return chrec; + /* Fallthru. */ case SCEV_NOT_KNOWN: return chrec_dont_know; case SCEV_KNOWN: return chrec_known; - case ARRAY_REF: - return instantiate_array_ref (instantiate_below, evolution_loop, chrec, - fold_conversions, cache, size_expr); - default: - break; + if (CONSTANT_CLASS_P (chrec)) + return chrec; + return chrec_dont_know; } - - if (VL_EXP_CLASS_P (chrec)) - return chrec_dont_know; - - switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) - { - case 3: - return instantiate_scev_3 (instantiate_below, evolution_loop, chrec, - fold_conversions, cache, size_expr); - - case 2: - return instantiate_scev_2 (instantiate_below, evolution_loop, chrec, - fold_conversions, cache, size_expr); - - case 1: - return instantiate_scev_1 (instantiate_below, evolution_loop, chrec, - fold_conversions, cache, size_expr); - - case 0: - return chrec; - - default: - break; - } - - /* Too complicated to handle. */ - return chrec_dont_know; } /* Analyze all the parameters of the chrec that were left under a @@ -2694,34 +2780,46 @@ a function parameter. */ tree -instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop, +instantiate_scev (edge instantiate_below, struct loop *evolution_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)) + + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, "(instantiate_scev \n"); - fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index); - fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num); + fprintf (dump_file, " (instantiate_below = %d -> %d)\n", + instantiate_below->src->index, instantiate_below->dest->index); + if (evolution_loop) + fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num); fprintf (dump_file, " (chrec = "); - print_generic_expr (dump_file, chrec, 0); + print_generic_expr (dump_file, chrec); fprintf (dump_file, ")\n"); } - res = instantiate_scev_r (instantiate_below, evolution_loop, chrec, false, - cache, 0); - - if (dump_file && (dump_flags & TDF_DETAILS)) + bool destr = false; + if (!global_cache) + { + global_cache = new instantiate_cache_type; + destr = true; + } + + res = instantiate_scev_r (instantiate_below, evolution_loop, + NULL, chrec, NULL, 0); + + if (destr) + { + delete global_cache; + global_cache = NULL; + } + + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, " (res = "); - print_generic_expr (dump_file, res, 0); + print_generic_expr (dump_file, res); fprintf (dump_file, "))\n"); } - htab_delete (cache); - return res; } @@ -2731,12 +2829,28 @@ of an expression. */ tree -resolve_mixers (struct loop *loop, tree chrec) +resolve_mixers (struct loop *loop, tree chrec, bool *folded_casts) { - htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); - tree ret = instantiate_scev_r (block_before_loop (loop), loop, chrec, true, - cache, 0); - htab_delete (cache); + bool destr = false; + bool fold_conversions = false; + if (!global_cache) + { + global_cache = new instantiate_cache_type; + destr = true; + } + + tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL, + chrec, &fold_conversions, 0); + + if (folded_casts && !*folded_casts) + *folded_casts = fold_conversions; + + if (destr) + { + delete global_cache; + global_cache = NULL; + } + return ret; } @@ -2779,7 +2893,7 @@ may_be_zero = NULL_TREE; - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) fprintf (dump_file, "(number_of_iterations_in_loop = \n"); res = chrec_dont_know; @@ -2804,79 +2918,16 @@ else res = chrec_dont_know; - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, " (set_nb_iterations_in_loop = "); - print_generic_expr (dump_file, res, 0); + print_generic_expr (dump_file, res); fprintf (dump_file, "))\n"); } loop->nb_iterations = res; return 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 unlike 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 (VEC(gimple,heap) **exit_conditions) -{ - unsigned int i; - unsigned nb_chrec_dont_know_loops = 0; - unsigned nb_static_loops = 0; - gimple cond; - - FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond) - { - tree res = number_of_latch_executions (loop_containing_stmt (cond)); - if (chrec_contains_undetermined (res)) - nb_chrec_dont_know_loops++; - else - nb_static_loops++; - } - - if (dump_file) - { - fprintf (dump_file, "\n(\n"); - 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", number_of_loops ()); - fprintf (dump_file, "-----------------------------------------\n"); - fprintf (dump_file, ")\n\n"); - - print_loops (dump_file, 3); - } -} - /* Counters for the stats. */ @@ -2922,7 +2973,7 @@ stats->nb_undetermined); fprintf (file, "-----------------------------------------\n"); fprintf (file, "%d\tchrecs in the scev database\n", - (int) htab_elements (scalar_evolution_info)); + (int) scalar_evolution_info->elements ()); fprintf (file, "%d\tsets in the scev database\n", nb_set_scev); fprintf (file, "%d\tgets in the scev database\n", nb_get_scev); fprintf (file, "-----------------------------------------\n"); @@ -2937,7 +2988,7 @@ if (dump_file && (dump_flags & TDF_STATS)) { fprintf (dump_file, "(classify_chrec "); - print_generic_expr (dump_file, chrec, 0); + print_generic_expr (dump_file, chrec); fprintf (dump_file, "\n"); } @@ -2988,67 +3039,6 @@ fprintf (dump_file, ")\n"); } -/* One of the drivers for testing the scalar evolutions analysis. - This function analyzes the scalar evolution of all the scalars - defined as loop phi nodes in one of the loops from the - EXIT_CONDITIONS array. - - TODO Optimization: A loop is in canonical form if it contains only - a single scalar loop phi node. All the other scalars that have an - evolution in the loop are rewritten in function of this single - index. This allows the parallelization of the loop. */ - -static void -analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple,heap) **exit_conditions) -{ - unsigned int i; - struct chrec_stats stats; - gimple cond, phi; - gimple_stmt_iterator psi; - - reset_chrecs_counters (&stats); - - FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond) - { - struct loop *loop; - basic_block bb; - tree chrec; - - loop = loop_containing_stmt (cond); - bb = loop->header; - - for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) - { - phi = gsi_stmt (psi); - if (is_gimple_reg (PHI_RESULT (phi))) - { - chrec = instantiate_parameters - (loop, - analyze_scalar_evolution (loop, PHI_RESULT (phi))); - - if (dump_file && (dump_flags & TDF_STATS)) - gather_chrec_stats (chrec, &stats); - } - } - } - - if (dump_file && (dump_flags & TDF_STATS)) - dump_chrecs_stats (dump_file, &stats); -} - -/* Callback for htab_traverse, gathers information on chrecs in the - hashtable. */ - -static int -gather_stats_on_scev_database_1 (void **slot, void *stats) -{ - struct scev_info_str *entry = (struct scev_info_str *) *slot; - - gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats); - - return 1; -} - /* Classify the chrecs of the whole database. */ void @@ -3061,8 +3051,11 @@ reset_chrecs_counters (&stats); - htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1, - &stats); + hash_table<scev_info_hasher>::iterator iter; + scev_info_str *elt; + FOR_EACH_HASH_TABLE_ELEMENT (*scalar_evolution_info, elt, scev_info_str *, + iter) + gather_chrec_stats (elt->chrec, &stats); dump_chrecs_stats (dump_file, &stats); } @@ -3090,21 +3083,28 @@ void scev_initialize (void) { - loop_iterator li; struct loop *loop; - - scalar_evolution_info = htab_create_ggc (100, hash_scev_info, eq_scev_info, - del_scev_info); + gcc_assert (! scev_initialized_p ()); + + scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100); initialize_scalar_evolutions_analyzer (); - FOR_EACH_LOOP (li, loop, 0) + FOR_EACH_LOOP (loop, 0) { loop->nb_iterations = NULL_TREE; } } +/* Return true if SCEV is initialized. */ + +bool +scev_initialized_p (void) +{ + return scalar_evolution_info != NULL; +} + /* Cleans up the information cached by the scalar evolutions analysis in the hash table. */ @@ -3114,7 +3114,7 @@ if (!scalar_evolution_info) return; - htab_empty (scalar_evolution_info); + scalar_evolution_info->empty (); } /* Cleans up the information cached by the scalar evolutions analysis @@ -3123,20 +3123,150 @@ void scev_reset (void) { - loop_iterator li; struct loop *loop; scev_reset_htab (); - if (!current_loops) - return; - - FOR_EACH_LOOP (li, loop, 0) + FOR_EACH_LOOP (loop, 0) { loop->nb_iterations = NULL_TREE; } } +/* Return true if the IV calculation in TYPE can overflow based on the knowledge + of the upper bound on the number of iterations of LOOP, the BASE and STEP + of IV. + + We do not use information whether TYPE can overflow so it is safe to + use this test even for derived IVs not computed every iteration or + hypotetical IVs to be inserted into code. */ + +bool +iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step) +{ + widest_int nit; + wide_int base_min, base_max, step_min, step_max, type_min, type_max; + signop sgn = TYPE_SIGN (type); + + if (integer_zerop (step)) + return false; + + if (TREE_CODE (base) == INTEGER_CST) + base_min = base_max = wi::to_wide (base); + else if (TREE_CODE (base) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (base)) + && get_range_info (base, &base_min, &base_max) == VR_RANGE) + ; + else + return true; + + if (TREE_CODE (step) == INTEGER_CST) + step_min = step_max = wi::to_wide (step); + else if (TREE_CODE (step) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (step)) + && get_range_info (step, &step_min, &step_max) == VR_RANGE) + ; + else + return true; + + if (!get_max_loop_iterations (loop, &nit)) + return true; + + type_min = wi::min_value (type); + type_max = wi::max_value (type); + + /* Just sanity check that we don't see values out of the range of the type. + In this case the arithmetics bellow would overflow. */ + gcc_checking_assert (wi::ge_p (base_min, type_min, sgn) + && wi::le_p (base_max, type_max, sgn)); + + /* Account the possible increment in the last ieration. */ + bool overflow = false; + nit = wi::add (nit, 1, SIGNED, &overflow); + if (overflow) + return true; + + /* NIT is typeless and can exceed the precision of the type. In this case + overflow is always possible, because we know STEP is non-zero. */ + if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type)) + return true; + wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED); + + /* If step can be positive, check that nit*step <= type_max-base. + This can be done by unsigned arithmetic and we only need to watch overflow + in the multiplication. The right hand side can always be represented in + the type. */ + if (sgn == UNSIGNED || !wi::neg_p (step_max)) + { + bool overflow = false; + if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow), + type_max - base_max) + || overflow) + return true; + } + /* If step can be negative, check that nit*(-step) <= base_min-type_min. */ + if (sgn == SIGNED && wi::neg_p (step_min)) + { + bool overflow = false, overflow2 = false; + if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2), + nit2, UNSIGNED, &overflow), + base_min - type_min) + || overflow || overflow2) + return true; + } + + return false; +} + +/* Given EV with form of "(type) {inner_base, inner_step}_loop", this + function tries to derive condition under which it can be simplified + into "{(type)inner_base, (type)inner_step}_loop". The condition is + the maximum number that inner iv can iterate. */ + +static tree +derive_simple_iv_with_niters (tree ev, tree *niters) +{ + if (!CONVERT_EXPR_P (ev)) + return ev; + + tree inner_ev = TREE_OPERAND (ev, 0); + if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC) + return ev; + + tree init = CHREC_LEFT (inner_ev); + tree step = CHREC_RIGHT (inner_ev); + if (TREE_CODE (init) != INTEGER_CST + || TREE_CODE (step) != INTEGER_CST || integer_zerop (step)) + return ev; + + tree type = TREE_TYPE (ev); + tree inner_type = TREE_TYPE (inner_ev); + if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type)) + return ev; + + /* Type conversion in "(type) {inner_base, inner_step}_loop" can be + folded only if inner iv won't overflow. We compute the maximum + number the inner iv can iterate before overflowing and return the + simplified affine iv. */ + tree delta; + init = fold_convert (type, init); + step = fold_convert (type, step); + ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step); + if (tree_int_cst_sign_bit (step)) + { + tree bound = lower_bound_in_type (inner_type, inner_type); + delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound)); + step = fold_build1 (NEGATE_EXPR, type, step); + } + else + { + tree bound = upper_bound_in_type (inner_type, inner_type); + delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init); + } + *niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step); + return ev; +} + /* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with respect to WRTO_LOOP and returns its base and step in IV if possible (see analyze_scalar_evolution_in_loop for more details on USE_LOOP @@ -3154,24 +3284,42 @@ not wrap by some other argument. Otherwise, this might introduce undefined behavior, and - for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step)) - - must be used instead. */ + i = iv->base; + for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step)) + + must be used instead. + + When IV_NITERS is not NULL, this function also checks case in which OP + is a conversion of an inner simple iv of below form: + + (outer_type){inner_base, inner_step}_loop. + + If type of inner iv has smaller precision than outer_type, it can't be + folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because + the inner iv could overflow/wrap. In this case, we derive a condition + under which the inner iv won't overflow/wrap and do the simplification. + The derived condition normally is the maximum number the inner iv can + iterate, and will be stored in IV_NITERS. This is useful in loop niter + analysis, to derive break conditions when a loop must terminate, when is + infinite. */ bool -simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, - affine_iv *iv, bool allow_nonconstant_step) +simple_iv_with_niters (struct loop *wrto_loop, struct loop *use_loop, + tree op, affine_iv *iv, tree *iv_niters, + bool allow_nonconstant_step) { - tree type, ev; - bool folded_casts; + enum tree_code code; + tree type, ev, base, e; + wide_int extreme; + bool folded_casts, overflow; 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) + if (!POINTER_TYPE_P (type) + && !INTEGRAL_TYPE_P (type)) return false; ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op, @@ -3188,8 +3336,14 @@ return true; } - if (TREE_CODE (ev) != POLYNOMIAL_CHREC - || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num) + /* If we can derive valid scalar evolution with assumptions. */ + if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC) + ev = derive_simple_iv_with_niters (ev, iv_niters); + + if (TREE_CODE (ev) != POLYNOMIAL_CHREC) + return false; + + if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num) return false; iv->step = CHREC_RIGHT (ev); @@ -3201,26 +3355,100 @@ if (tree_contains_chrecs (iv->base, NULL)) return false; - iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type); - + iv->no_overflow = !folded_casts && nowrap_type_p (type); + + if (!iv->no_overflow + && !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step)) + iv->no_overflow = true; + + /* Try to simplify iv base: + + (signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T + == (signed T)(unsigned T)base + step + == base + step + + If we can prove operation (base + step) doesn't overflow or underflow. + Specifically, we try to prove below conditions are satisfied: + + base <= UPPER_BOUND (type) - step ;;step > 0 + base >= LOWER_BOUND (type) - step ;;step < 0 + + This is done by proving the reverse conditions are false using loop's + initial conditions. + + The is necessary to make loop niter, or iv overflow analysis easier + for below example: + + int foo (int *a, signed char s, signed char l) + { + signed char i; + for (i = s; i < l; i++) + a[i] = 0; + return 0; + } + + Note variable I is firstly converted to type unsigned char, incremented, + then converted back to type signed char. */ + + if (wrto_loop->num != use_loop->num) + return true; + + if (!CONVERT_EXPR_P (iv->base) || TREE_CODE (iv->step) != INTEGER_CST) + return true; + + type = TREE_TYPE (iv->base); + e = TREE_OPERAND (iv->base, 0); + if (TREE_CODE (e) != PLUS_EXPR + || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST + || !tree_int_cst_equal (iv->step, + fold_convert (type, TREE_OPERAND (e, 1)))) + return true; + e = TREE_OPERAND (e, 0); + if (!CONVERT_EXPR_P (e)) + return true; + base = TREE_OPERAND (e, 0); + if (!useless_type_conversion_p (type, TREE_TYPE (base))) + return true; + + if (tree_int_cst_sign_bit (iv->step)) + { + code = LT_EXPR; + extreme = wi::min_value (type); + } + else + { + code = GT_EXPR; + extreme = wi::max_value (type); + } + overflow = false; + extreme = wi::sub (extreme, wi::to_wide (iv->step), + TYPE_SIGN (type), &overflow); + if (overflow) + return true; + e = fold_build2 (code, boolean_type_node, base, + wide_int_to_tree (type, extreme)); + e = simplify_using_initial_conditions (use_loop, e); + if (!integer_zerop (e)) + return true; + + if (POINTER_TYPE_P (TREE_TYPE (base))) + code = POINTER_PLUS_EXPR; + else + code = PLUS_EXPR; + + iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step); return true; } -/* Runs the analysis of scalar evolutions. */ - -void -scev_analysis (void) +/* Like simple_iv_with_niters, but return TRUE when OP behaves as a simple + affine iv unconditionally. */ + +bool +simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, + affine_iv *iv, bool allow_nonconstant_step) { - VEC(gimple,heap) *exit_conditions; - - exit_conditions = VEC_alloc (gimple, 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); - - number_of_iterations_for_all_loops (&exit_conditions); - VEC_free (gimple, heap, exit_conditions); + return simple_iv_with_niters (wrto_loop, use_loop, op, iv, + NULL, allow_nonconstant_step); } /* Finalize the scalar evolution analysis. */ @@ -3230,8 +3458,9 @@ { if (!scalar_evolution_info) return; - htab_delete (scalar_evolution_info); + scalar_evolution_info->empty (); scalar_evolution_info = NULL; + free_numbers_of_iterations_estimates (cfun); } /* Returns true if the expression EXPR is considered to be too expensive @@ -3278,6 +3507,131 @@ } } +/* Do final value replacement for LOOP. */ + +void +final_value_replacement_loop (struct loop *loop) +{ + /* If we do not know exact number of iterations of the loop, we cannot + replace the final value. */ + edge exit = single_exit (loop); + if (!exit) + return; + + tree niter = number_of_latch_executions (loop); + if (niter == chrec_dont_know) + return; + + /* Ensure that it is possible to insert new statements somewhere. */ + if (!single_pred_p (exit->dest)) + split_loop_exit_edge (exit); + + /* Set stmt insertion pointer. All stmts are inserted before this point. */ + gimple_stmt_iterator gsi = gsi_after_labels (exit->dest); + + struct loop *ex_loop + = superloop_at_depth (loop, + loop_depth (exit->dest->loop_father) + 1); + + gphi_iterator psi; + for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); ) + { + gphi *phi = psi.phi (); + tree rslt = PHI_RESULT (phi); + tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit); + if (virtual_operand_p (def)) + { + gsi_next (&psi); + continue; + } + + if (!POINTER_TYPE_P (TREE_TYPE (def)) + && !INTEGRAL_TYPE_P (TREE_TYPE (def))) + { + gsi_next (&psi); + continue; + } + + bool folded_casts; + def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, + &folded_casts); + 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) + /* Do not emit expensive expressions. The rationale is that + when someone writes a code like + + while (n > 45) n -= 45; + + he probably knows that n is not large, and does not want it + to be turned into n %= 45. */ + || expression_expensive_p (def)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "not replacing:\n "); + print_gimple_stmt (dump_file, phi, 0); + fprintf (dump_file, "\n"); + } + gsi_next (&psi); + continue; + } + + /* Eliminate the PHI node and replace it by a computation outside + the loop. */ + if (dump_file) + { + fprintf (dump_file, "\nfinal value replacement:\n "); + print_gimple_stmt (dump_file, phi, 0); + fprintf (dump_file, " with\n "); + } + def = unshare_expr (def); + remove_phi_node (&psi, false); + + /* If def's type has undefined overflow and there were folded + casts, rewrite all stmts added for def into arithmetics + with defined overflow behavior. */ + if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def)) + && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def))) + { + gimple_seq stmts; + gimple_stmt_iterator gsi2; + def = force_gimple_operand (def, &stmts, true, NULL_TREE); + gsi2 = gsi_start (stmts); + while (!gsi_end_p (gsi2)) + { + gimple *stmt = gsi_stmt (gsi2); + gimple_stmt_iterator gsi3 = gsi2; + gsi_next (&gsi2); + gsi_remove (&gsi3, false); + if (is_gimple_assign (stmt) + && arith_code_with_undefined_signed_overflow + (gimple_assign_rhs_code (stmt))) + gsi_insert_seq_before (&gsi, + rewrite_to_defined_overflow (stmt), + GSI_SAME_STMT); + else + gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); + } + } + else + def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE, + true, GSI_SAME_STMT); + + gassign *ass = gimple_build_assign (rslt, def); + gsi_insert_before (&gsi, ass, GSI_SAME_STMT); + if (dump_file) + { + print_gimple_stmt (dump_file, ass, 0); + fprintf (dump_file, "\n"); + } + } +} + /* 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. @@ -3290,26 +3644,25 @@ { basic_block bb; tree name, type, ev; - gimple phi, ass; - struct loop *loop, *ex_loop; + gphi *phi; + struct loop *loop; bitmap ssa_names_to_remove = NULL; unsigned i; - loop_iterator li; - gimple_stmt_iterator psi; - - if (number_of_loops () <= 1) + gphi_iterator psi; + + if (number_of_loops (cfun) <= 1) return 0; - FOR_EACH_BB (bb) + FOR_EACH_BB_FN (bb, cfun) { loop = bb->loop_father; for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) { - phi = gsi_stmt (psi); + phi = psi.phi (); name = PHI_RESULT (phi); - if (!is_gimple_reg (name)) + if (virtual_operand_p (name)) continue; type = TREE_TYPE (name); @@ -3318,14 +3671,25 @@ && !INTEGRAL_TYPE_P (type)) continue; - ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name)); + ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name), + NULL); 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 (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Replacing uses of: "); + print_generic_expr (dump_file, name); + fprintf (dump_file, " with: "); + print_generic_expr (dump_file, ev); + fprintf (dump_file, "\n"); + } + replace_uses_by (name, ev); + } if (!ssa_names_to_remove) ssa_names_to_remove = BITMAP_ALLOC (NULL); @@ -3344,7 +3708,7 @@ { gimple_stmt_iterator psi; name = ssa_name (i); - phi = SSA_NAME_DEF_STMT (name); + phi = as_a <gphi *> (SSA_NAME_DEF_STMT (name)); gcc_assert (gimple_code (phi) == GIMPLE_PHI); psi = gsi_for_stmt (phi); @@ -3356,80 +3720,9 @@ } /* Now the regular final value replacement. */ - FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) - { - edge exit; - tree def, rslt, niter; - gimple_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); - 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 = gsi_after_labels (exit->dest); - - ex_loop = superloop_at_depth (loop, - loop_depth (exit->dest->loop_father) + 1); - - for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); ) - { - phi = gsi_stmt (psi); - rslt = PHI_RESULT (phi); - def = PHI_ARG_DEF_FROM_EDGE (phi, exit); - if (!is_gimple_reg (def)) - { - gsi_next (&psi); - continue; - } - - if (!POINTER_TYPE_P (TREE_TYPE (def)) - && !INTEGRAL_TYPE_P (TREE_TYPE (def))) - { - gsi_next (&psi); - 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) - /* Do not emit expensive expressions. The rationale is that - when someone writes a code like - - while (n > 45) n -= 45; - - he probably knows that n is not large, and does not want it - to be turned into n %= 45. */ - || expression_expensive_p (def)) - { - gsi_next (&psi); - continue; - } - - /* Eliminate the PHI node and replace it by a computation outside - the loop. */ - def = unshare_expr (def); - remove_phi_node (&psi, false); - - def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE, - true, GSI_SAME_STMT); - ass = gimple_build_assign (rslt, def); - gsi_insert_before (&bsi, ass, GSI_SAME_STMT); - } - } + FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) + final_value_replacement_loop (loop); + return 0; }