X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;ds=sidebyside;f=gcc%2Ftree-scalar-evolution.c;h=06fd39eaaf5106eade0a15bcb0fd8091ff7e73c7;hb=9a34200da273acd28cd55db9db5194395ea568c0;hp=bf564d8dab537f59479481df3e7c0964e2d0ede7;hpb=8e3cb73bc66100e137b20bcd98316bc415b6e53c;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index bf564d8dab5..06fd39eaaf5 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -257,20 +257,12 @@ along with GCC; see the file COPYING3. If not see #include "config.h" #include "system.h" #include "coretypes.h" -#include "tm.h" -#include "ggc.h" -#include "tree.h" -#include "basic-block.h" -#include "tree-pretty-print.h" #include "gimple-pretty-print.h" #include "tree-flow.h" -#include "tree-dump.h" -#include "timevar.h" #include "cfgloop.h" #include "tree-chrec.h" #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); @@ -314,7 +306,7 @@ new_scev_info_str (basic_block instantiated_below, tree var) { struct scev_info_str *res; - res = GGC_NEW (struct scev_info_str); + res = ggc_alloc_scev_info_str (); res->var = var; res->chrec = chrec_not_analyzed_yet; res->instantiated_below = instantiated_below; @@ -385,19 +377,17 @@ chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb) if (is_gimple_min_invariant (chrec)) return false; - if (TREE_CODE (chrec) == VAR_DECL - || TREE_CODE (chrec) == PARM_DECL - || TREE_CODE (chrec) == FUNCTION_DECL - || TREE_CODE (chrec) == LABEL_DECL - || TREE_CODE (chrec) == RESULT_DECL - || TREE_CODE (chrec) == FIELD_DECL) - return true; - if (TREE_CODE (chrec) == SSA_NAME) { - gimple def = SSA_NAME_DEF_STMT (chrec); - struct loop *def_loop = loop_containing_stmt (def); - struct loop *loop = get_loop (loop_nb); + gimple def; + loop_p def_loop, loop; + + if (SSA_NAME_IS_DEFAULT_DEF (chrec)) + return false; + + def = SSA_NAME_DEF_STMT (chrec); + def_loop = loop_containing_stmt (def); + loop = get_loop (loop_nb); if (def_loop == NULL) return false; @@ -509,65 +499,6 @@ compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) 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 @@ -582,7 +513,7 @@ set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec) 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", @@ -610,7 +541,7 @@ get_scalar_evolution (basic_block instantiated_below, tree scalar) if (dump_file) { - if (dump_flags & TDF_DETAILS) + if (dump_flags & TDF_SCEV) { fprintf (dump_file, "(get_scalar_evolution \n"); fprintf (dump_file, " (scalar = "); @@ -638,7 +569,7 @@ get_scalar_evolution (basic_block instantiated_below, tree scalar) break; } - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, " (scalar_evolution = "); print_generic_expr (dump_file, res, 0); @@ -871,7 +802,7 @@ add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, /* 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); @@ -889,7 +820,7 @@ add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code, 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); @@ -915,7 +846,7 @@ get_loop_exit_condition (const struct loop *loop) gimple 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) @@ -927,7 +858,7 @@ get_loop_exit_condition (const struct loop *loop) res = stmt; } - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) { print_gimple_stmt (dump_file, res, 0, 0); fprintf (dump_file, ")\n"); @@ -1170,6 +1101,24 @@ follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr, halting_phi, evolution_of_loop, limit); break; + case ADDR_EXPR: + /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */ + if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF) + { + expr = TREE_OPERAND (expr, 0); + rhs0 = TREE_OPERAND (expr, 0); + rhs1 = TREE_OPERAND (expr, 1); + type = TREE_TYPE (rhs0); + STRIP_USELESS_TYPE_CONVERSION (rhs0); + STRIP_USELESS_TYPE_CONVERSION (rhs1); + res = follow_ssa_edge_binary (loop, at_stmt, type, + rhs0, POINTER_PLUS_EXPR, rhs1, + halting_phi, evolution_of_loop, limit); + } + else + res = t_false; + break; + 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. */ @@ -1391,7 +1340,7 @@ follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi, 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)) + if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY)) return t_dont_know; def_loop = loop_containing_stmt (def); @@ -1453,7 +1402,7 @@ analyze_evolution_in_loop (gimple loop_phi_node, struct loop *loop = loop_containing_stmt (loop_phi_node); basic_block bb; - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, "(analyze_evolution_in_loop \n"); fprintf (dump_file, " (loop_phi_node = "); @@ -1509,7 +1458,7 @@ analyze_evolution_in_loop (gimple loop_phi_node, evolution_function = chrec_merge (evolution_function, ev_fn); } - 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); @@ -1533,7 +1482,7 @@ analyze_initial_condition (gimple loop_phi_node) 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"); @@ -1585,7 +1534,7 @@ analyze_initial_condition (gimple loop_phi_node) init_cond = res; } - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, " (init_cond = "); print_generic_expr (dump_file, init_cond, 0); @@ -1634,8 +1583,8 @@ interpret_loop_phi (struct loop *loop, gimple loop_phi_node) 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; } @@ -1699,17 +1648,27 @@ interpret_rhs_expr (struct loop *loop, gimple at_stmt, return chrec_convert (type, analyze_scalar_evolution (loop, rhs1), at_stmt); } - - return chrec_dont_know; } 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. */ + 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); res = chrec_fold_plus (type, chrec1, chrec2); break; @@ -1778,7 +1737,8 @@ interpret_expr (struct loop *loop, gimple at_stmt, tree expr) 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); @@ -1816,13 +1776,18 @@ 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); } @@ -1919,7 +1884,7 @@ analyze_scalar_evolution (struct loop *loop, tree var) { tree res; - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, "(analyze_scalar_evolution \n"); fprintf (dump_file, " (loop_nb = %d)\n", loop->num); @@ -1931,7 +1896,7 @@ analyze_scalar_evolution (struct loop *loop, tree var) 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 (dump_file && (dump_flags & TDF_SCEV)) fprintf (dump_file, ")\n"); return res; @@ -2161,20 +2126,34 @@ instantiate_scev_name (basic_block instantiate_below, result again. */ res = analyze_scalar_evolution (def_loop, chrec); - /* Don't instantiate loop-closed-ssa phi nodes. */ + /* Don't instantiate default definitions. */ 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)))) + && SSA_NAME_IS_DEFAULT_DEF (res)) + ; + + /* Don't instantiate loop-closed-ssa phi nodes. */ + else if (TREE_CODE (res) == SSA_NAME + && 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 - || !dominated_by_p (CDI_DOMINATORS, instantiate_below, - gimple_bb (SSA_NAME_DEF_STMT (res)))) + /* When there is no loop_closed_phi_def, it means that the + variable is not used after the loop: try to still compute the + value of the variable when exiting the loop. */ + if (res == NULL_TREE) + { + 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); + } + else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below, + gimple_bb (SSA_NAME_DEF_STMT (res)))) res = chrec_dont_know; } @@ -2185,7 +2164,6 @@ instantiate_scev_name (basic_block instantiate_below, /* Store the correct value to the cache. */ set_instantiated_value (cache, instantiate_below, chrec, res); return res; - } /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW @@ -2303,6 +2281,41 @@ instantiate_scev_binary (basic_block instantiate_below, /* 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. + + 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_array_ref (basic_block instantiate_below, + struct loop *evolution_loop, tree chrec, + bool fold_conversions, htab_t cache, 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. @@ -2537,7 +2550,8 @@ instantiate_scev_r (basic_block instantiate_below, if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) return chrec_dont_know; - if (automatically_generated_chrec_p (chrec) + if (chrec == NULL_TREE + || automatically_generated_chrec_p (chrec) || is_gimple_min_invariant (chrec)) return chrec; @@ -2573,12 +2587,17 @@ instantiate_scev_r (basic_block instantiate_below, TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); + case ADDR_EXPR: 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; } @@ -2624,7 +2643,7 @@ instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop, 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); @@ -2637,7 +2656,7 @@ instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop, res = instantiate_scev_r (instantiate_below, evolution_loop, chrec, false, cache, 0); - 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); @@ -2703,7 +2722,7 @@ number_of_latch_executions (struct loop *loop) 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; @@ -2728,7 +2747,7 @@ number_of_latch_executions (struct loop *loop) 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); @@ -2778,7 +2797,7 @@ number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions) unsigned nb_static_loops = 0; gimple cond; - for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++) + FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond) { tree res = number_of_latch_executions (loop_containing_stmt (cond)); if (chrec_contains_undetermined (res)) @@ -2932,7 +2951,7 @@ analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple,heap) **exit_conditi reset_chrecs_counters (&stats); - for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++) + FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond) { struct loop *loop; basic_block bb; @@ -3017,12 +3036,9 @@ scev_initialize (void) loop_iterator li; struct loop *loop; - scalar_evolution_info = htab_create_alloc (100, - hash_scev_info, - eq_scev_info, - del_scev_info, - ggc_calloc, - ggc_free); + + scalar_evolution_info = htab_create_ggc (100, hash_scev_info, eq_scev_info, + del_scev_info); initialize_scalar_evolutions_analyzer (); @@ -3097,8 +3113,8 @@ simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op, 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,