From fee017b3be70565c42f30e18a84e3ae9fc20183b Mon Sep 17 00:00:00 2001 From: rguenth Date: Thu, 12 Apr 2012 08:35:01 +0000 Subject: [PATCH] 2012-04-12 Richard Guenther * cfgloop.h (estimated_loop_iterations_int): Ditch 'conservative' parameter. (max_stmt_executions_int): Likewise. (estimated_loop_iterations): Likewise. (max_stmt_executions): Likewise. (max_loop_iterations): Declare. (max_loop_iterations_int): Likewise. (estimated_stmt_executions): Likewise. (estimated_stmt_executions_int): Likewise. * tree-ssa-loop-niter.c (estimated_loop_iterations): Split parts to ... (max_loop_iterations): ... this. (estimated_loop_iterations_int): Split parts to ... (max_loop_iterations_int): ... this. (max_stmt_executions_int): Split parts to ... (estimated_stmt_executions_int): ... this. (max_stmt_executions): Split parts to ... (estimated_stmt_executions): ... this. * graphite-sese-to-poly.c (build_loop_iteration_domains): Adjust. * predict.c (predict_loops): Likewise. * tree-data-ref.c (max_stmt_executions_tree): Likewise. (analyze_siv_subscript_cst_affine): Likewise. (compute_overlap_steps_for_affine_1_2): Likewise. (analyze_subscript_affine_affine): Likewise. (init_omega_for_ddr_1): Likewise. * tree-parloops.c (parallelize_loops): Likewise. * tree-ssa-loop-ivopts.c (avg_loop_niter): Likewise. (may_eliminate_iv): Likewise. * tree-ssa-loop-prefetch.c (determine_loop_nest_reuse): Likewise. (loop_prefetch_arrays): Likewise. * tree-vrp.c (adjust_range_with_scev): Likewise. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@186372 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 34 ++++++++++++++ gcc/cfgloop.h | 12 +++-- gcc/graphite-sese-to-poly.c | 2 +- gcc/predict.c | 2 +- gcc/tree-data-ref.c | 27 ++++++----- gcc/tree-parloops.c | 2 +- gcc/tree-ssa-loop-ivopts.c | 4 +- gcc/tree-ssa-loop-niter.c | 106 +++++++++++++++++++++++++++++++++---------- gcc/tree-ssa-loop-prefetch.c | 4 +- gcc/tree-vrp.c | 2 +- 10 files changed, 146 insertions(+), 49 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index c5e54d3..d702e02 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,37 @@ +2012-04-12 Richard Guenther + + * cfgloop.h (estimated_loop_iterations_int): Ditch + 'conservative' parameter. + (max_stmt_executions_int): Likewise. + (estimated_loop_iterations): Likewise. + (max_stmt_executions): Likewise. + (max_loop_iterations): Declare. + (max_loop_iterations_int): Likewise. + (estimated_stmt_executions): Likewise. + (estimated_stmt_executions_int): Likewise. + * tree-ssa-loop-niter.c (estimated_loop_iterations): + Split parts to ... + (max_loop_iterations): ... this. + (estimated_loop_iterations_int): Split parts to ... + (max_loop_iterations_int): ... this. + (max_stmt_executions_int): Split parts to ... + (estimated_stmt_executions_int): ... this. + (max_stmt_executions): Split parts to ... + (estimated_stmt_executions): ... this. + * graphite-sese-to-poly.c (build_loop_iteration_domains): Adjust. + * predict.c (predict_loops): Likewise. + * tree-data-ref.c (max_stmt_executions_tree): Likewise. + (analyze_siv_subscript_cst_affine): Likewise. + (compute_overlap_steps_for_affine_1_2): Likewise. + (analyze_subscript_affine_affine): Likewise. + (init_omega_for_ddr_1): Likewise. + * tree-parloops.c (parallelize_loops): Likewise. + * tree-ssa-loop-ivopts.c (avg_loop_niter): Likewise. + (may_eliminate_iv): Likewise. + * tree-ssa-loop-prefetch.c (determine_loop_nest_reuse): Likewise. + (loop_prefetch_arrays): Likewise. + * tree-vrp.c (adjust_range_with_scev): Likewise. + 2012-04-12 Oleg Endo * config/sh/sh.h (RETURN_ADDR_RTX): Use NULL_RTX instead of 0. diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 510bc10..82c8881 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -279,10 +279,14 @@ extern unsigned expected_loop_iterations (const struct loop *); extern rtx doloop_condition_get (rtx); void estimate_numbers_of_iterations_loop (struct loop *, bool); -HOST_WIDE_INT estimated_loop_iterations_int (struct loop *, bool); -HOST_WIDE_INT max_stmt_executions_int (struct loop *, bool); -bool estimated_loop_iterations (struct loop *, bool, double_int *); -bool max_stmt_executions (struct loop *, bool, double_int *); +bool estimated_loop_iterations (struct loop *, double_int *); +bool max_loop_iterations (struct loop *, double_int *); +HOST_WIDE_INT estimated_loop_iterations_int (struct loop *); +HOST_WIDE_INT max_loop_iterations_int (struct loop *); +bool max_stmt_executions (struct loop *, double_int *); +bool estimated_stmt_executions (struct loop *, double_int *); +HOST_WIDE_INT max_stmt_executions_int (struct loop *); +HOST_WIDE_INT estimated_stmt_executions_int (struct loop *); /* Loop manipulation. */ extern bool can_duplicate_loop_p (const struct loop *loop); diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index d9bcf27..4a2ca40 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -1092,7 +1092,7 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop, scan_tree_for_params (SCOP_REGION (scop), nb_iters, ub_expr, one); mpz_clear (one); - if (max_stmt_executions (loop, true, &nit)) + if (max_stmt_executions (loop, &nit)) add_upper_bounds_from_estimated_nit (scop, nit, dim, ub_expr); /* loop_i <= expr_nb_iters */ diff --git a/gcc/predict.c b/gcc/predict.c index c12b45f..8ed2e83 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -994,7 +994,7 @@ predict_loops (void) the loop, use it to predict this exit. */ else if (n_exits == 1) { - nitercst = max_stmt_executions_int (loop, false); + nitercst = estimated_stmt_executions_int (loop); if (nitercst < 0) continue; if (nitercst > max) diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 6fb0d23..c4e78f3 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -1709,7 +1709,7 @@ max_stmt_executions_tree (struct loop *loop) { double_int nit; - if (!max_stmt_executions (loop, true, &nit)) + if (!max_stmt_executions (loop, &nit)) return chrec_dont_know; if (!double_int_fits_to_tree_p (unsigned_type_node, nit)) @@ -1791,7 +1791,7 @@ analyze_siv_subscript_cst_affine (tree chrec_a, /* Perform weak-zero siv test to see if overlap is outside the loop bounds. */ - numiter = max_stmt_executions_int (loop, true); + numiter = max_stmt_executions_int (loop); if (numiter >= 0 && compare_tree_int (tmp, numiter) > 0) @@ -1869,7 +1869,7 @@ analyze_siv_subscript_cst_affine (tree chrec_a, /* Perform weak-zero siv test to see if overlap is outside the loop bounds. */ - numiter = max_stmt_executions_int (loop, true); + numiter = max_stmt_executions_int (loop); if (numiter >= 0 && compare_tree_int (tmp, numiter) > 0) @@ -2049,10 +2049,9 @@ 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)); - niter_x = - max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a)), true); - niter_y = max_stmt_executions_int (get_chrec_loop (chrec_a), true); - niter_z = max_stmt_executions_int (get_chrec_loop (chrec_b), true); + niter_x = max_stmt_executions_int (get_chrec_loop (CHREC_LEFT (chrec_a))); + niter_y = max_stmt_executions_int (get_chrec_loop (chrec_a)); + niter_z = max_stmt_executions_int (get_chrec_loop (chrec_b)); if (niter_x < 0 || niter_y < 0 || niter_z < 0) { @@ -2377,8 +2376,8 @@ analyze_subscript_affine_affine (tree chrec_a, HOST_WIDE_INT niter, niter_a, niter_b; affine_fn ova, ovb; - niter_a = max_stmt_executions_int (get_chrec_loop (chrec_a), true); - niter_b = max_stmt_executions_int (get_chrec_loop (chrec_b), true); + niter_a = max_stmt_executions_int (get_chrec_loop (chrec_a)); + niter_b = max_stmt_executions_int (get_chrec_loop (chrec_b)); niter = MIN (niter_a, niter_b); step_a = int_cst_value (CHREC_RIGHT (chrec_a)); step_b = int_cst_value (CHREC_RIGHT (chrec_b)); @@ -2485,10 +2484,10 @@ analyze_subscript_affine_affine (tree chrec_a, if (i1 > 0 && j1 > 0) { - HOST_WIDE_INT niter_a = max_stmt_executions_int - (get_chrec_loop (chrec_a), true); - HOST_WIDE_INT niter_b = max_stmt_executions_int - (get_chrec_loop (chrec_b), true); + HOST_WIDE_INT niter_a + = max_stmt_executions_int (get_chrec_loop (chrec_a)); + HOST_WIDE_INT niter_b + = max_stmt_executions_int (get_chrec_loop (chrec_b)); HOST_WIDE_INT niter = MIN (niter_a, niter_b); /* (X0, Y0) is a solution of the Diophantine equation: @@ -3782,7 +3781,7 @@ init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb, for (i = 0; i <= DDR_INNER_LOOP (ddr) && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++) { - HOST_WIDE_INT nbi = max_stmt_executions_int (loopi, true); + HOST_WIDE_INT nbi = max_stmt_executions_int (loopi); /* 0 <= loop_x */ ineq = omega_add_zero_geq (pb, omega_black); diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c index abae3fd..a7f4f90 100644 --- a/gcc/tree-parloops.c +++ b/gcc/tree-parloops.c @@ -2192,7 +2192,7 @@ parallelize_loops (void) header-copied loops correctly - see PR46886. */ || !do_while_loop_p (loop)) continue; - estimated = max_stmt_executions_int (loop, false); + estimated = estimated_stmt_executions_int (loop); /* FIXME: Bypass this check as graphite doesn't update the count and frequency correctly now. */ if (!flag_loop_parallelize_all diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 527c911..3c11c0e 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -115,7 +115,7 @@ along with GCC; see the file COPYING3. If not see static inline HOST_WIDE_INT avg_loop_niter (struct loop *loop) { - HOST_WIDE_INT niter = max_stmt_executions_int (loop, false); + HOST_WIDE_INT niter = estimated_stmt_executions_int (loop); if (niter == -1) return AVG_LOOP_NITER (loop); @@ -4694,7 +4694,7 @@ may_eliminate_iv (struct ivopts_data *data, /* See if we can take advantage of infered loop bound information. */ if (data->loop_single_exit_p) { - if (!estimated_loop_iterations (loop, true, &max_niter)) + if (!max_loop_iterations (loop, &max_niter)) return false; /* The loop bound is already adjusted by adding 1. */ if (double_int_ucmp (max_niter, period_value) > 0) diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 4acfc67..2529b36 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -3052,25 +3052,28 @@ estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p) the function returns false, otherwise returns true. */ bool -estimated_loop_iterations (struct loop *loop, bool conservative, - double_int *nit) +estimated_loop_iterations (struct loop *loop, double_int *nit) { estimate_numbers_of_iterations_loop (loop, true); - if (conservative) - { - if (!loop->any_upper_bound) - return false; + if (!loop->any_estimate) + return false; - *nit = loop->nb_iterations_upper_bound; - } - else - { - if (!loop->any_estimate) - return false; + *nit = loop->nb_iterations_estimate; + return true; +} - *nit = loop->nb_iterations_estimate; - } +/* Sets NIT to an upper bound for the maximum number of executions of the + latch of the LOOP. If we have no reliable estimate, the function returns + false, otherwise returns true. */ + +bool +max_loop_iterations (struct loop *loop, double_int *nit) +{ + estimate_numbers_of_iterations_loop (loop, true); + if (!loop->any_upper_bound) + return false; + *nit = loop->nb_iterations_upper_bound; return true; } @@ -3079,12 +3082,32 @@ estimated_loop_iterations (struct loop *loop, bool conservative, 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) +estimated_loop_iterations_int (struct loop *loop) +{ + double_int nit; + HOST_WIDE_INT hwi_nit; + + if (!estimated_loop_iterations (loop, &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 max_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 +max_loop_iterations_int (struct loop *loop) { double_int nit; HOST_WIDE_INT hwi_nit; - if (!estimated_loop_iterations (loop, conservative, &nit)) + if (!max_loop_iterations (loop, &nit)) return -1; if (!double_int_fits_in_shwi_p (nit)) @@ -3099,9 +3122,9 @@ estimated_loop_iterations_int (struct loop *loop, bool conservative) the number of execution of the latch by one. */ HOST_WIDE_INT -max_stmt_executions_int (struct loop *loop, bool conservative) +max_stmt_executions_int (struct loop *loop) { - HOST_WIDE_INT nit = estimated_loop_iterations_int (loop, conservative); + HOST_WIDE_INT nit = max_loop_iterations_int (loop); HOST_WIDE_INT snit; if (nit == -1) @@ -3113,17 +3136,54 @@ max_stmt_executions_int (struct loop *loop, bool conservative) return snit < 0 ? -1 : snit; } +/* Returns an estimate for the number of executions of statements + in the LOOP. For statements before the loop exit, this exceeds + the number of execution of the latch by one. */ + +HOST_WIDE_INT +estimated_stmt_executions_int (struct loop *loop) +{ + HOST_WIDE_INT nit = estimated_loop_iterations_int (loop); + HOST_WIDE_INT snit; + + if (nit == -1) + return -1; + + snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1); + + /* If the computation overflows, return -1. */ + return snit < 0 ? -1 : snit; +} + +/* Sets NIT to the estimated maximum number of executions of the latch of the + LOOP, plus one. If we have no reliable estimate, the function returns + false, otherwise returns true. */ + +bool +max_stmt_executions (struct loop *loop, double_int *nit) +{ + double_int nit_minus_one; + + if (!max_loop_iterations (loop, nit)) + return false; + + nit_minus_one = *nit; + + *nit = double_int_add (*nit, double_int_one); + + return double_int_ucmp (*nit, nit_minus_one) > 0; +} + /* Sets NIT to the estimated number of executions of the latch of the - LOOP, plus one. 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. */ + LOOP, plus one. If we have no reliable estimate, the function returns + false, otherwise returns true. */ bool -max_stmt_executions (struct loop *loop, bool conservative, double_int *nit) +estimated_stmt_executions (struct loop *loop, double_int *nit) { double_int nit_minus_one; - if (!estimated_loop_iterations (loop, conservative, nit)) + if (!estimated_loop_iterations (loop, nit)) return false; nit_minus_one = *nit; diff --git a/gcc/tree-ssa-loop-prefetch.c b/gcc/tree-ssa-loop-prefetch.c index 264d97b..eab1fff 100644 --- a/gcc/tree-ssa-loop-prefetch.c +++ b/gcc/tree-ssa-loop-prefetch.c @@ -1548,7 +1548,7 @@ determine_loop_nest_reuse (struct loop *loop, struct mem_ref_group *refs, continue; aloop = VEC_index (loop_p, vloops, i); - vol = max_stmt_executions_int (aloop, false); + vol = estimated_stmt_executions_int (aloop); if (vol < 0) vol = expected_loop_iterations (aloop); volume *= vol; @@ -1800,7 +1800,7 @@ loop_prefetch_arrays (struct loop *loop) return false; ahead = (PREFETCH_LATENCY + time - 1) / time; - est_niter = max_stmt_executions_int (loop, false); + est_niter = estimated_stmt_executions_int (loop); /* Prefetching is not likely to be profitable if the trip count to ahead ratio is too small. */ diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index ae0ef4d..a53ceeb 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -3420,7 +3420,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *loop, { double_int nit; - if (estimated_loop_iterations (loop, true, &nit)) + if (max_loop_iterations (loop, &nit)) { value_range_t maxvr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }; double_int dtmp; -- 2.7.4