diff options
Diffstat (limited to 'gcc/tree-scalar-evolution.c')
| -rw-r--r-- | gcc/tree-scalar-evolution.c | 406 |
1 files changed, 116 insertions, 290 deletions
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 8459793a01b..b6c1fcef6a1 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -281,7 +281,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-propagate.h" #include "gimple-fold.h" -static tree analyze_scalar_evolution_1 (struct loop *, tree, tree); +static tree analyze_scalar_evolution_1 (struct loop *, tree); static tree analyze_scalar_evolution_for_address_of (struct loop *loop, tree var); @@ -564,22 +564,30 @@ get_scalar_evolution (basic_block instantiated_below, tree scalar) nb_get_scev++; } - switch (TREE_CODE (scalar)) - { - case SSA_NAME: - res = *find_var_scev_info (instantiated_below, scalar); - break; + 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; + case REAL_CST: + case FIXED_CST: + case INTEGER_CST: + res = scalar; + break; - default: - res = chrec_not_analyzed_yet; - break; - } + default: + res = chrec_not_analyzed_yet; + break; + } if (dump_file && (dump_flags & TDF_SCEV)) { @@ -1628,19 +1636,7 @@ interpret_loop_phi (struct loop *loop, gphi *loop_phi_node) 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); @@ -2016,73 +2012,38 @@ interpret_gimple_assign (struct loop *loop, gimple *stmt) - 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; basic_block bb; struct loop *def_loop; - - if (loop == NULL - || TREE_CODE (type) == VECTOR_TYPE - || TREE_CODE (type) == COMPLEX_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; + def_loop = bb->loop_father; - if (bb == NULL - || !flow_bb_inside_loop_p (loop, bb)) + if (!flow_bb_inside_loop_p (loop, bb)) { /* Keep symbolic form, but look through obvious copies for constants. */ res = follow_copies_to_constant (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); - - 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; } @@ -2134,6 +2095,10 @@ analyze_scalar_evolution (struct loop *loop, tree var) { tree res; + /* ??? Fix callers. */ + if (! loop) + return var; + if (dump_file && (dump_flags & TDF_SCEV)) { fprintf (dump_file, "(analyze_scalar_evolution \n"); @@ -2144,7 +2109,8 @@ 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 (res == chrec_not_analyzed_yet) + res = analyze_scalar_evolution_1 (loop, var); if (dump_file && (dump_flags & TDF_SCEV)) fprintf (dump_file, ")\n"); @@ -2309,7 +2275,7 @@ eq_idx_scev_info (const void *e1, const void *e2) static unsigned get_instantiated_value_entry (instantiate_cache_type &cache, - tree name, basic_block instantiate_below) + tree name, edge instantiate_below) { if (!cache.map) { @@ -2319,7 +2285,7 @@ get_instantiated_value_entry (instantiate_cache_type &cache, scev_info_str e; e.name_version = SSA_NAME_VERSION (name); - e.instantiated_below = instantiate_below->index; + 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) @@ -2363,7 +2329,7 @@ loop_closed_phi_def (tree var) return NULL_TREE; } -static tree instantiate_scev_r (basic_block, struct loop *, struct loop *, +static tree instantiate_scev_r (edge, struct loop *, struct loop *, tree, bool *, int); /* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW @@ -2382,7 +2348,7 @@ static tree instantiate_scev_r (basic_block, struct loop *, struct loop *, instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_name (basic_block instantiate_below, +instantiate_scev_name (edge instantiate_below, struct loop *evolution_loop, struct loop *inner_loop, tree chrec, bool *fold_conversions, @@ -2396,7 +2362,7 @@ instantiate_scev_name (basic_block instantiate_below, evolutions in outer loops), 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 @@ -2418,6 +2384,51 @@ instantiate_scev_name (basic_block instantiate_below, 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); @@ -2449,8 +2460,9 @@ instantiate_scev_name (basic_block instantiate_below, 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; } @@ -2488,7 +2500,7 @@ instantiate_scev_name (basic_block instantiate_below, instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_poly (basic_block instantiate_below, +instantiate_scev_poly (edge instantiate_below, struct loop *evolution_loop, struct loop *, tree chrec, bool *fold_conversions, int size_expr) { @@ -2533,7 +2545,7 @@ instantiate_scev_poly (basic_block instantiate_below, instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_binary (basic_block instantiate_below, +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, @@ -2579,43 +2591,6 @@ 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. - - 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, struct loop *inner_loop, - tree chrec, bool *fold_conversions, int size_expr) -{ - tree res; - tree index = TREE_OPERAND (chrec, 1); - tree op1 = instantiate_scev_r (instantiate_below, evolution_loop, - inner_loop, index, - fold_conversions, 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. @@ -2630,7 +2605,7 @@ instantiate_array_ref (basic_block instantiate_below, instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_convert (basic_block instantiate_below, +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) @@ -2681,7 +2656,7 @@ instantiate_scev_convert (basic_block instantiate_below, instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_not (basic_block instantiate_below, +instantiate_scev_not (edge instantiate_below, struct loop *evolution_loop, struct loop *inner_loop, tree chrec, enum tree_code code, tree type, tree op, @@ -2719,130 +2694,6 @@ instantiate_scev_not (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 expression with 3 operands to be instantiated. - - CACHE is the cache of already instantiated values. - - 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_3 (basic_block instantiate_below, - struct loop *evolution_loop, struct loop *inner_loop, - tree chrec, - bool *fold_conversions, int size_expr) -{ - tree op1, op2; - tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, - inner_loop, TREE_OPERAND (chrec, 0), - fold_conversions, size_expr); - if (op0 == chrec_dont_know) - return chrec_dont_know; - - op1 = instantiate_scev_r (instantiate_below, evolution_loop, - inner_loop, TREE_OPERAND (chrec, 1), - fold_conversions, size_expr); - if (op1 == chrec_dont_know) - return chrec_dont_know; - - op2 = instantiate_scev_r (instantiate_below, evolution_loop, - inner_loop, TREE_OPERAND (chrec, 2), - fold_conversions, 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. - - 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, struct loop *inner_loop, - tree chrec, - bool *fold_conversions, int size_expr) -{ - tree op1; - tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, - inner_loop, TREE_OPERAND (chrec, 0), - fold_conversions, size_expr); - if (op0 == chrec_dont_know) - return chrec_dont_know; - - op1 = instantiate_scev_r (instantiate_below, evolution_loop, - inner_loop, TREE_OPERAND (chrec, 1), - fold_conversions, 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. - - 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_1 (basic_block instantiate_below, - struct loop *evolution_loop, struct loop *inner_loop, - tree chrec, - bool *fold_conversions, int size_expr) -{ - tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, - inner_loop, TREE_OPERAND (chrec, 0), - fold_conversions, 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. @@ -2856,7 +2707,7 @@ instantiate_scev_1 (basic_block instantiate_below, instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_r (basic_block instantiate_below, +instantiate_scev_r (edge instantiate_below, struct loop *evolution_loop, struct loop *inner_loop, tree chrec, bool *fold_conversions, int size_expr) @@ -2908,50 +2759,20 @@ instantiate_scev_r (basic_block instantiate_below, 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, - inner_loop, chrec, - fold_conversions, size_expr); - - default: - break; - } - - 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, - inner_loop, chrec, - fold_conversions, size_expr); - - case 2: - return instantiate_scev_2 (instantiate_below, evolution_loop, - inner_loop, chrec, - fold_conversions, size_expr); - - case 1: - return instantiate_scev_1 (instantiate_below, evolution_loop, - inner_loop, chrec, - fold_conversions, size_expr); - - case 0: - return chrec; - default: - break; + if (CONSTANT_CLASS_P (chrec)) + return chrec; + return chrec_dont_know; } - - /* Too complicated to handle. */ - return chrec_dont_know; } /* Analyze all the parameters of the chrec that were left under a @@ -2961,7 +2782,7 @@ instantiate_scev_r (basic_block instantiate_below, 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; @@ -2969,8 +2790,10 @@ instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop, 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); fprintf (dump_file, ")\n"); @@ -3018,7 +2841,7 @@ resolve_mixers (struct loop *loop, tree chrec, bool *folded_casts) destr = true; } - tree ret = instantiate_scev_r (block_before_loop (loop), loop, NULL, + tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL, chrec, &fold_conversions, 0); if (folded_casts && !*folded_casts) @@ -3264,6 +3087,8 @@ scev_initialize (void) { struct loop *loop; + gcc_assert (! scev_initialized_p ()); + scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (100); initialize_scalar_evolutions_analyzer (); @@ -3329,7 +3154,7 @@ iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step) return false; if (TREE_CODE (base) == INTEGER_CST) - base_min = base_max = base; + 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) @@ -3338,7 +3163,7 @@ iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step) return true; if (TREE_CODE (step) == INTEGER_CST) - step_min = step_max = step; + 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) @@ -3598,7 +3423,8 @@ simple_iv_with_niters (struct loop *wrto_loop, struct loop *use_loop, extreme = wi::max_value (type); } overflow = false; - extreme = wi::sub (extreme, iv->step, TYPE_SIGN (type), &overflow); + 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, |