diff options
| -rw-r--r-- | gcc/ChangeLog | 23 | ||||
| -rw-r--r-- | gcc/cfgloop.c | 3 | ||||
| -rw-r--r-- | gcc/cfgloop.h | 3 | ||||
| -rw-r--r-- | gcc/predict.c | 40 | ||||
| -rw-r--r-- | gcc/predict.def | 10 | ||||
| -rw-r--r-- | gcc/tree-data-ref.c | 144 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-niter.c | 73 |
7 files changed, 231 insertions, 65 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 54d3ad52179..e835441970b 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,26 @@ +2007-02-25 Zdenek Dvorak <dvorakz@suse.cz> + + * tree-ssa-loop-niter.c (compute_estimated_nb_iterations): Fix + off-by-one error. + (array_at_struct_end_p): New function. + (idx_infer_loop_bounds): Use it. + (estimate_numbers_of_iterations_loop): Export. + * predict.c (predict_loops): Use estimated_loop_iterations_int. + Do not use PRED_LOOP_EXIT on exits predicted by # of iterations. + (tree_estimate_probability): Call record_loop_exits. + * tree-data-ref.c (get_number_of_iters_for_loop): Replaced by ... + (estimated_loop_iterations, estimated_loop_iterations_int, + estimated_loop_iterations_tree): New functions. + (analyze_siv_subscript_cst_affine, + compute_overlap_steps_for_affine_1_2, + analyze_subscript_affine_affine): Use estimated_loop_iterations_int. + (analyze_miv_subscript): Use estimated_loop_iterations_tree. + * predict.def (PRED_LOOP_ITERATIONS): Update comment. + (PRED_LOOP_ITERATIONS_GUESSED): New. + * cfgloop.c (record_loop_exits): Do nothing if there are no loops. + * cfgloop.h (estimate_numbers_of_iterations_loop, + estimated_loop_iterations_int): Declare. + 2007-02-25 Mark Mitchell <mark@codesourcery.com> * doc/extend.texi: Document optional priority argument to diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index 62ee79c6cd1..12ce92cdd9e 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -1038,6 +1038,9 @@ record_loop_exits (void) edge_iterator ei; edge e; + if (!current_loops) + return; + if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS) return; current_loops->state |= LOOPS_HAVE_RECORDED_EXITS; diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 09eef08ca3d..c6cd7221aa7 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -265,6 +265,9 @@ extern bool just_once_each_iteration_p (const struct loop *, basic_block); extern unsigned expected_loop_iterations (const struct loop *); extern rtx doloop_condition_get (rtx); +void estimate_numbers_of_iterations_loop (struct loop *); +HOST_WIDE_INT estimated_loop_iterations_int (struct loop *, bool); + /* Loop manipulation. */ extern bool can_duplicate_loop_p (struct loop *loop); diff --git a/gcc/predict.c b/gcc/predict.c index df5d3105953..0e86c527238 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -650,6 +650,10 @@ predict_loops (void) for (j = 0; VEC_iterate (edge, exits, j, ex); j++) { tree niter = NULL; + HOST_WIDE_INT nitercst; + int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS); + int probability; + enum br_predictor predictor; if (number_of_iterations_exit (loop, ex, &niter_desc, false)) niter = niter_desc.niter; @@ -658,20 +662,31 @@ predict_loops (void) if (TREE_CODE (niter) == INTEGER_CST) { - int probability; - int max = PARAM_VALUE (PARAM_MAX_PREDICTED_ITERATIONS); if (host_integerp (niter, 1) && compare_tree_int (niter, max-1) == -1) - { - HOST_WIDE_INT nitercst = tree_low_cst (niter, 1) + 1; - probability = ((REG_BR_PROB_BASE + nitercst / 2) - / nitercst); - } + nitercst = tree_low_cst (niter, 1) + 1; else - probability = ((REG_BR_PROB_BASE + max / 2) / max); + nitercst = max; + predictor = PRED_LOOP_ITERATIONS; + } + /* If we have just one exit and we can derive some information about + the number of iterations of the loop from the statements inside + the loop, use it to predict this exit. */ + else if (n_exits == 1) + { + nitercst = estimated_loop_iterations_int (loop, false); + if (nitercst < 0) + continue; + if (nitercst > max) + nitercst = max; - predict_edge (ex, PRED_LOOP_ITERATIONS, probability); + predictor = PRED_LOOP_ITERATIONS_GUESSED; } + else + continue; + + probability = ((REG_BR_PROB_BASE + nitercst / 2) / nitercst); + predict_edge (ex, predictor, probability); } VEC_free (edge, heap, exits); @@ -706,7 +721,11 @@ predict_loops (void) /* Loop exit heuristics - predict an edge exiting the loop if the conditional has no loop header successors as not taken. */ - if (!header_found) + if (!header_found + /* If we already used more reliable loop exit predictors, do not + bother with PRED_LOOP_EXIT. */ + && !predicted_by_p (bb, PRED_LOOP_ITERATIONS_GUESSED) + && !predicted_by_p (bb, PRED_LOOP_ITERATIONS)) { /* For loop with many exits we don't want to predict all exits with the pretty large probability, because if all exits are @@ -1258,6 +1277,7 @@ tree_estimate_probability (void) tree_bb_level_predictions (); mark_irreducible_loops (); + record_loop_exits (); if (current_loops) predict_loops (); diff --git a/gcc/predict.def b/gcc/predict.def index 997f4d2cc98..22474b3db40 100644 --- a/gcc/predict.def +++ b/gcc/predict.def @@ -52,9 +52,9 @@ DEF_PREDICTOR (PRED_NO_PREDICTION, "no prediction", PROB_ALWAYS, 0) DEF_PREDICTOR (PRED_UNCONDITIONAL, "unconditional jump", PROB_ALWAYS, PRED_FLAG_FIRST_MATCH) -/* Use number of loop iterations determined by loop unroller to set - probability. We don't want to use Dempster-Shaffer theory here, - as the predictions is exact. */ +/* Use number of loop iterations determined by # of iterations + analysis to set probability. We don't want to use Dempster-Shaffer + theory here, as the predictions is exact. */ DEF_PREDICTOR (PRED_LOOP_ITERATIONS, "loop iterations", PROB_ALWAYS, PRED_FLAG_FIRST_MATCH) @@ -62,6 +62,10 @@ DEF_PREDICTOR (PRED_LOOP_ITERATIONS, "loop iterations", PROB_ALWAYS, DEF_PREDICTOR (PRED_BUILTIN_EXPECT, "__builtin_expect", PROB_VERY_LIKELY, PRED_FLAG_FIRST_MATCH) +/* Use number of loop iterations guessed by the contents of the loop. */ +DEF_PREDICTOR (PRED_LOOP_ITERATIONS_GUESSED, "guessed loop iterations", + PROB_ALWAYS, PRED_FLAG_FIRST_MATCH) + /* Branch containing goto is probably not taken. */ DEF_PREDICTOR (PRED_CONTINUE, "continue", HITRATE (56), 0) diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 2f57c4f0203..b6750ee0021 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -2543,29 +2543,85 @@ analyze_ziv_subscript (tree chrec_a, fprintf (dump_file, ")\n"); } -/* Get the real or estimated number of iterations for LOOPNUM, whichever is - available. Return the number of iterations as a tree, or NULL_TREE if - we don't know. */ +/* Sets NIT to the estimated number of executions of the statements in + LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as + large as the number of iterations. If we have no reliable estimate, + the function returns false, otherwise returns true. */ -static tree -get_number_of_iters_for_loop (int loopnum) +static bool +estimated_loop_iterations (struct loop *loop, bool conservative, + double_int *nit) { - struct loop *loop = get_loop (loopnum); tree numiter = number_of_exit_cond_executions (loop); + /* If we have an exact value, use it. */ if (TREE_CODE (numiter) == INTEGER_CST) - return numiter; + { + *nit = tree_to_double_int (numiter); + return true; + } + /* If we have a measured profile and we do not ask for a conservative bound, + use it. */ + if (!conservative && loop->header->count != 0) + { + *nit = uhwi_to_double_int (expected_loop_iterations (loop) + 1); + return true; + } + + /* Finally, try using a reliable estimate on number of iterations according + to the size of the accessed data, if available. */ + estimate_numbers_of_iterations_loop (loop); if (loop->estimate_state == EST_AVAILABLE) { - tree type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true); - if (double_int_fits_to_tree_p (type, loop->estimated_nb_iterations)) - return double_int_to_tree (type, loop->estimated_nb_iterations); + *nit = loop->estimated_nb_iterations; + return true; } - return NULL_TREE; + return false; +} + +/* Similar to estimated_loop_iterations, but returns the estimate only + if it fits to HOST_WIDE_INT. If this is not the case, or the estimate + on the number of iterations of LOOP could not be derived, returns -1. */ + +HOST_WIDE_INT +estimated_loop_iterations_int (struct loop *loop, bool conservative) +{ + double_int nit; + HOST_WIDE_INT hwi_nit; + + if (!estimated_loop_iterations (loop, conservative, &nit)) + return -1; + + if (!double_int_fits_in_shwi_p (nit)) + return -1; + hwi_nit = double_int_to_shwi (nit); + + return hwi_nit < 0 ? -1 : hwi_nit; } +/* Similar to estimated_loop_iterations, but returns the estimate as a tree, + and only if it fits to the int type. If this is not the case, or the + estimate on the number of iterations of LOOP could not be derived, returns + chrec_dont_know. */ + +static tree +estimated_loop_iterations_tree (struct loop *loop, bool conservative) +{ + double_int nit; + tree type; + + if (!estimated_loop_iterations (loop, conservative, &nit)) + return chrec_dont_know; + + type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true); + if (!double_int_fits_to_tree_p (type, nit)) + return chrec_dont_know; + + return double_int_to_tree (type, nit); +} + /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a constant, and CHREC_B is an affine function. *OVERLAPS_A and *OVERLAPS_B are initialized to the functions that describe the @@ -2626,8 +2682,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a, if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference)) { - tree numiter; - int loopnum = CHREC_VARIABLE (chrec_b); + HOST_WIDE_INT numiter; + struct loop *loop = get_chrec_loop (chrec_b); *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node, @@ -2641,11 +2697,10 @@ analyze_siv_subscript_cst_affine (tree chrec_a, /* Perform weak-zero siv test to see if overlap is outside the loop bounds. */ - numiter = get_number_of_iters_for_loop (loopnum); + numiter = estimated_loop_iterations_int (loop, true); - if (numiter != NULL_TREE - && TREE_CODE (tmp) == INTEGER_CST - && tree_int_cst_lt (numiter, tmp)) + if (numiter >= 0 + && compare_tree_int (tmp, numiter) > 0) { free_conflict_function (*overlaps_a); free_conflict_function (*overlaps_b); @@ -2709,8 +2764,8 @@ analyze_siv_subscript_cst_affine (tree chrec_a, */ if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference)) { - tree numiter; - int loopnum = CHREC_VARIABLE (chrec_b); + HOST_WIDE_INT numiter; + struct loop *loop = get_chrec_loop (chrec_b); *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); tmp = fold_build2 (EXACT_DIV_EXPR, @@ -2721,11 +2776,10 @@ analyze_siv_subscript_cst_affine (tree chrec_a, /* Perform weak-zero siv test to see if overlap is outside the loop bounds. */ - numiter = get_number_of_iters_for_loop (loopnum); + numiter = estimated_loop_iterations_int (loop, true); - if (numiter != NULL_TREE - && TREE_CODE (tmp) == INTEGER_CST - && tree_int_cst_lt (numiter, tmp)) + if (numiter >= 0 + && compare_tree_int (tmp, numiter) > 0) { free_conflict_function (*overlaps_a); free_conflict_function (*overlaps_b); @@ -2852,8 +2906,7 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, { bool xz_p, yz_p, xyz_p; int step_x, step_y, step_z; - int niter_x, niter_y, niter_z, niter; - tree numiter_x, numiter_y, numiter_z; + HOST_WIDE_INT niter_x, niter_y, niter_z, niter; affine_fn overlaps_a_xz, overlaps_b_xz; affine_fn overlaps_a_yz, overlaps_b_yz; affine_fn overlaps_a_xyz, overlaps_b_xyz; @@ -2864,12 +2917,12 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, step_y = int_cst_value (CHREC_RIGHT (chrec_a)); step_z = int_cst_value (CHREC_RIGHT (chrec_b)); - numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a))); - numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); - numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b)); + niter_x = estimated_loop_iterations_int + (get_chrec_loop (CHREC_LEFT (chrec_a)), true); + niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), true); + niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), true); - if (numiter_x == NULL_TREE || numiter_y == NULL_TREE - || numiter_z == NULL_TREE) + if (niter_x < 0 || niter_y < 0 || niter_z < 0) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "overlap steps test failed: no iteration counts.\n"); @@ -2880,10 +2933,6 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, return; } - niter_x = int_cst_value (numiter_x); - niter_y = int_cst_value (numiter_y); - niter_z = int_cst_value (numiter_z); - niter = MIN (niter_x, niter_z); compute_overlap_steps_for_affine_univar (niter, step_x, step_z, &overlaps_a_xz, @@ -3029,13 +3078,14 @@ analyze_subscript_affine_affine (tree chrec_a, if (nb_vars_a == 1 && nb_vars_b == 1) { int step_a, step_b; - int niter, niter_a, niter_b; - tree numiter_a, numiter_b; + HOST_WIDE_INT niter, niter_a, niter_b; affine_fn ova, ovb; - numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); - numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b)); - if (numiter_a == NULL_TREE || numiter_b == NULL_TREE) + niter_a = estimated_loop_iterations_int + (get_chrec_loop (chrec_a), true); + niter_b = estimated_loop_iterations_int + (get_chrec_loop (chrec_b), true); + if (niter_a < 0 || niter_b < 0) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n"); @@ -3045,8 +3095,6 @@ analyze_subscript_affine_affine (tree chrec_a, goto end_analyze_subs_aa; } - niter_a = int_cst_value (numiter_a); - niter_b = int_cst_value (numiter_b); niter = MIN (niter_a, niter_b); step_a = int_cst_value (CHREC_RIGHT (chrec_a)); @@ -3140,12 +3188,13 @@ analyze_subscript_affine_affine (tree chrec_a, equation: chrec_a (X0) = chrec_b (Y0). */ int x0, y0; int niter, niter_a, niter_b; - tree numiter_a, numiter_b; - numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); - numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b)); + niter_a = estimated_loop_iterations_int + (get_chrec_loop (chrec_a), true); + niter_b = estimated_loop_iterations_int + (get_chrec_loop (chrec_b), true); - if (numiter_a == NULL_TREE || numiter_b == NULL_TREE) + if (niter_a < 0 || niter_b < 0) { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n"); @@ -3155,8 +3204,6 @@ analyze_subscript_affine_affine (tree chrec_a, goto end_analyze_subs_aa; } - niter_a = int_cst_value (numiter_a); - niter_b = int_cst_value (numiter_b); niter = MIN (niter_a, niter_b); i0 = U[0][0] * gamma / gcd_alpha_beta; @@ -3481,7 +3528,8 @@ analyze_miv_subscript (tree chrec_a, in the same order. */ *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node)); *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node)); - *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a)); + *last_conflicts = estimated_loop_iterations_tree + (get_chrec_loop (chrec_a), true); dependence_stats.num_miv_dependent++; } diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 56ef2e90e8c..018e9a80529 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -1752,6 +1752,8 @@ static void compute_estimated_nb_iterations (struct loop *loop) { struct nb_iter_bound *bound; + double_int bnd_val, delta; + edge exit; gcc_assert (loop->estimate_state == EST_NOT_AVAILABLE); @@ -1760,17 +1762,79 @@ compute_estimated_nb_iterations (struct loop *loop) if (!bound->realistic) continue; + bnd_val = bound->bound; + /* If bound->stmt is an exit, then every statement in the loop is + executed at most BND_VAL + 1 times. If it is not an exit, then + some of the statements before it could be executed BND_VAL + 2 + times, if an exit of LOOP is before stmt. */ + exit = single_exit (loop); + + if (bound->is_exit + || (exit != NULL + && dominated_by_p (CDI_DOMINATORS, + exit->src, bb_for_stmt (bound->stmt)))) + delta = double_int_one; + else + delta = double_int_two; + bnd_val = double_int_add (bnd_val, delta); + + /* If an overflow occured, ignore the result. */ + if (double_int_ucmp (bnd_val, delta) < 0) + continue; + /* Update only when there is no previous estimation, or when the current estimation is smaller. */ if (loop->estimate_state == EST_NOT_AVAILABLE - || double_int_ucmp (bound->bound, loop->estimated_nb_iterations) < 0) + || double_int_ucmp (bnd_val, loop->estimated_nb_iterations) < 0) { loop->estimate_state = EST_AVAILABLE; - loop->estimated_nb_iterations = bound->bound; + loop->estimated_nb_iterations = bnd_val; } } } +/* Returns true if REF is a reference to an array at the end of a dynamically + allocated structure. If this is the case, the array may be allocated larger + than its upper bound implies. */ + +static bool +array_at_struct_end_p (tree ref) +{ + tree base = get_base_address (ref); + tree parent, field; + + /* Unless the reference is through a pointer, the size of the array matches + its declaration. */ + if (!base || !INDIRECT_REF_P (base)) + return false; + + for (;handled_component_p (ref); ref = parent) + { + parent = TREE_OPERAND (ref, 0); + + if (TREE_CODE (ref) == COMPONENT_REF) + { + /* All fields of a union are at its end. */ + if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE) + continue; + + /* Unless the field is at the end of the struct, we are done. */ + field = TREE_OPERAND (ref, 1); + if (TREE_CHAIN (field)) + return false; + } + + /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR. + In all these cases, we might be accessing the last element, and + although in practice this will probably never happen, it is legal for + the indices of this last element to exceed the bounds of the array. + Therefore, continue checking. */ + } + + gcc_assert (INDIRECT_REF_P (ref)); + return true; +} + /* Determine information about number of iterations a LOOP from the index IDX of a data reference accessed in STMT. Callback for for_each_index. */ @@ -1789,7 +1853,8 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta) bool sign; struct loop *loop = data->loop; - if (TREE_CODE (base) != ARRAY_REF) + if (TREE_CODE (base) != ARRAY_REF + || array_at_struct_end_p (base)) return true; ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx)); @@ -1974,7 +2039,7 @@ infer_loop_bounds_from_undefined (struct loop *loop) /* Records estimates on numbers of iterations of LOOP. */ -static void +void estimate_numbers_of_iterations_loop (struct loop *loop) { VEC (edge, heap) *exits; |