diff options
| -rw-r--r-- | gcc/ChangeLog | 23 | ||||
| -rw-r--r-- | gcc/cfgloop.h | 4 | ||||
| -rw-r--r-- | gcc/doc/loop.texi | 28 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 4 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/loop-17.c | 2 | ||||
| -rw-r--r-- | gcc/tree-data-ref.c | 2 | ||||
| -rw-r--r-- | gcc/tree-scalar-evolution.c | 61 | ||||
| -rw-r--r-- | gcc/tree-scalar-evolution.h | 3 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-ivcanon.c | 8 | ||||
| -rw-r--r-- | gcc/tree-vect-analyze.c | 2 |
10 files changed, 83 insertions, 54 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index cef245c68a1..b069e0ff809 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,26 @@ +2006-12-10 Zdenek Dvorak <dvorakz@suse.cz> + + * doc/loop.texi: Document number_of_latch_executions and + number_of_cond_exit_executions. + * tree-scalar-evolution.c (compute_overall_effect_of_inner_loop, + chrec_is_positive, number_of_iterations_for_all_loops, + scev_const_prop): Use number_of_latch_executions. + (set_nb_iterations_in_loop): Do not increase the value of the + number of iterations. + (number_of_iterations_in_loop): Renamed to ... + (number_of_latch_executions): ... this. + (number_of_exit_cond_executions): New function. + * tree-scalar-evolution.h (number_of_iterations_in_loop): Declaration + removed. + (number_of_latch_executions, number_of_exit_cond_executions): Declare. + * tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables): Use + number_of_latch_executions. + * tree-data-ref.c (get_number_of_iters_for_loop): Use + number_of_exit_cond_executions. + * tree-vect-analyze.c (vect_get_loop_niters): Ditto. + * cfgloop.h (struct loop): Improve description of the nb_iterations + field. + 2006-12-10 Daniel Berlin <dberlin@dberlin.org> * tree-ssa-alias.c (compact_name_tags): Use sort_tags_by_id. diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index d523acf001c..4a13a6ac06b 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -119,10 +119,10 @@ struct loop /* Auxiliary info specific to a pass. */ void *aux; - /* The probable number of times the loop is executed at runtime. + /* The number of times the latch of the loop is executed. This is an INTEGER_CST or an expression containing symbolic names. Don't access this field directly: - number_of_iterations_in_loop computes and caches the computed + number_of_latch_executions computes and caches the computed information in this field. */ tree nb_iterations; diff --git a/gcc/doc/loop.texi b/gcc/doc/loop.texi index 354241f14c7..1b189c778fd 100644 --- a/gcc/doc/loop.texi +++ b/gcc/doc/loop.texi @@ -397,13 +397,15 @@ calculations. @cindex Number of iterations analysis Both on GIMPLE and on RTL, there are functions available to determine -the number of iterations of a loop, with a similar interface. In many -cases, it is not possible to determine number of iterations -unconditionally -- the determined number is correct only if some -assumptions are satisfied. The analysis tries to verify these -conditions using the information contained in the program; if it fails, -the conditions are returned together with the result. The following -information and conditions are provided by the analysis: +the number of iterations of a loop, with a similar interface. The +number of iterations of a loop in GCC is defined as the number of +executions of the loop latch. In many cases, it is not possible to +determine the number of iterations unconditionally -- the determined +number is correct only if some assumptions are satisfied. The analysis +tries to verify these conditions using the information contained in the +program; if it fails, the conditions are returned together with the +result. The following information and conditions are provided by the +analysis: @itemize @item @code{assumptions}: If this condition is false, the rest of @@ -431,16 +433,16 @@ number of iterations -- @code{find_loop_niter} on GIMPLE and @code{find_simple_exit} on RTL. Finally, there are functions that provide the same information, but additionally cache it, so that repeated calls to number of iterations are not so costly -- -@code{number_of_iterations_in_loop} on GIMPLE and -@code{get_simple_loop_desc} on RTL. +@code{number_of_latch_executions} on GIMPLE and @code{get_simple_loop_desc} +on RTL. Note that some of these functions may behave slightly differently than others -- some of them return only the expression for the number of iterations, and fail if there are some assumptions. The function -@code{number_of_iterations_in_loop} works only for single-exit loops, -and it returns the value for number of iterations higher by one with -respect to all other functions (i.e., it returns number of executions of -the exit statement, not of the loop latch). +@code{number_of_latch_executions} works only for single-exit loops. +The function @code{number_of_cond_exit_executions} can be used to +determine number of executions of the exit condition of a single-exit +loop (i.e., the @code{number_of_latch_executions} increased by one). @node Dependency analysis @section Data Dependency Analysis diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index cfdc64b5132..0b9b664feba 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2006-12-10 Zdenek Dvorak <dvorakz@suse.cz> + + * gcc.dg/tree-ssa/loop-17.c: Update outcome. + 2006-12-10 Tobias Burnus <burnus@net-b.de> PR fortran/23994 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-17.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-17.c index 26e49862091..d2903cef234 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/loop-17.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-17.c @@ -15,5 +15,5 @@ int foo (int *p) return i; } -/* { dg-final { scan-tree-dump "set_nb_iterations_in_loop = 2" "sccp" } } */ +/* { dg-final { scan-tree-dump "set_nb_iterations_in_loop = 1" "sccp" } } */ /* { dg-final { cleanup-tree-dump "sccp" } } */ diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 96d57a06e73..fdaaaafac93 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -2305,7 +2305,7 @@ static tree get_number_of_iters_for_loop (int loopnum) { struct loop *loop = get_loop (loopnum); - tree numiter = number_of_iterations_in_loop (loop); + tree numiter = number_of_exit_cond_executions (loop); if (TREE_CODE (numiter) == INTEGER_CST) return numiter; diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index c668bf22ddf..10d5da5d271 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -468,20 +468,14 @@ compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn) if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num) { struct loop *inner_loop = get_chrec_loop (evolution_fn); - tree nb_iter = number_of_iterations_in_loop (inner_loop); + tree nb_iter = number_of_latch_executions (inner_loop); if (nb_iter == chrec_dont_know) return chrec_dont_know; else { tree res; - tree type = chrec_type (nb_iter); - /* Number of iterations is off by one (the ssa name we - analyze must be defined before the exit). */ - nb_iter = chrec_fold_minus (type, nb_iter, - build_int_cst (type, 1)); - /* evolution_fn is the evolution function in LOOP. Get its value in the nb_iter-th iteration. */ res = chrec_apply (inner_loop->num, evolution_fn, nb_iter); @@ -510,7 +504,7 @@ bool chrec_is_positive (tree chrec, bool *value) { bool value0, value1, value2; - tree type, end_value, nb_iter; + tree end_value, nb_iter; switch (TREE_CODE (chrec)) { @@ -533,13 +527,10 @@ chrec_is_positive (tree chrec, bool *value) if (!evolution_function_is_affine_p (chrec)) return false; - nb_iter = number_of_iterations_in_loop (get_chrec_loop (chrec)); + nb_iter = number_of_latch_executions (get_chrec_loop (chrec)); if (chrec_contains_undetermined (nb_iter)) return false; - type = chrec_type (nb_iter); - nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1)); - #if 0 /* TODO -- If the test is after the exit, we may decrease the number of iterations by one. */ @@ -892,19 +883,6 @@ static inline tree set_nb_iterations_in_loop (struct loop *loop, tree res) { - tree type = chrec_type (res); - - res = chrec_fold_plus (type, res, build_int_cst (type, 1)); - - /* FIXME HWI: However we want to store one iteration less than the - count of the loop in order to be compatible with the other - nb_iter computations in loop-iv. This also allows the - representation of nb_iters that are equal to MAX_INT. */ - if (TREE_CODE (res) == INTEGER_CST - && (TREE_INT_CST_LOW (res) == 0 - || TREE_OVERFLOW (res))) - res = chrec_dont_know; - if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " (set_nb_iterations_in_loop = "); @@ -2465,7 +2443,7 @@ resolve_mixers (struct loop *loop, tree chrec) the loop body has been executed 6 times. */ tree -number_of_iterations_in_loop (struct loop *loop) +number_of_latch_executions (struct loop *loop) { tree res, type; edge exit; @@ -2500,6 +2478,33 @@ end: return set_nb_iterations_in_loop (loop, 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 unline 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. */ @@ -2514,7 +2519,7 @@ number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions) for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) { - tree res = number_of_iterations_in_loop (loop_containing_stmt (cond)); + tree res = number_of_latch_executions (loop_containing_stmt (cond)); if (chrec_contains_undetermined (res)) nb_chrec_dont_know_loops++; else @@ -2956,7 +2961,7 @@ scev_const_prop (void) if (!exit) continue; - niter = number_of_iterations_in_loop (loop); + niter = number_of_latch_executions (loop); if (niter == chrec_dont_know /* If computing the number of iterations is expensive, it may be better not to introduce computations involving it. */ diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h index 98855b93e26..464fe8fc519 100644 --- a/gcc/tree-scalar-evolution.h +++ b/gcc/tree-scalar-evolution.h @@ -22,7 +22,8 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #ifndef GCC_TREE_SCALAR_EVOLUTION_H #define GCC_TREE_SCALAR_EVOLUTION_H -extern tree number_of_iterations_in_loop (struct loop *); +extern tree number_of_latch_executions (struct loop *); +extern tree number_of_exit_cond_executions (struct loop *); extern tree get_loop_exit_condition (struct loop *); extern void scev_initialize (void); diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c index 63268017670..c26727a808d 100644 --- a/gcc/tree-ssa-loop-ivcanon.c +++ b/gcc/tree-ssa-loop-ivcanon.c @@ -279,18 +279,12 @@ canonicalize_loop_induction_variables (struct loop *loop, edge exit = NULL; tree niter; - niter = number_of_iterations_in_loop (loop); + niter = number_of_latch_executions (loop); if (TREE_CODE (niter) == INTEGER_CST) { exit = single_exit (loop); if (!just_once_each_iteration_p (loop, exit->src)) return false; - - /* The result of number_of_iterations_in_loop is by one higher than - we expect (i.e. it returns number of executions of the exit - condition, not of the loop latch edge). */ - niter = fold_build2 (MINUS_EXPR, TREE_TYPE (niter), niter, - build_int_cst (TREE_TYPE (niter), 1)); } else { diff --git a/gcc/tree-vect-analyze.c b/gcc/tree-vect-analyze.c index 31895733534..7506150b6ad 100644 --- a/gcc/tree-vect-analyze.c +++ b/gcc/tree-vect-analyze.c @@ -2393,7 +2393,7 @@ vect_get_loop_niters (struct loop *loop, tree *number_of_iterations) if (vect_print_dump_info (REPORT_DETAILS)) fprintf (vect_dump, "=== get_loop_niters ==="); - niters = number_of_iterations_in_loop (loop); + niters = number_of_exit_cond_executions (loop); if (niters != NULL_TREE && niters != chrec_dont_know) |