This is the mail archive of the
`gcc-patches@gcc.gnu.org`
mailing list for the GCC project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>*To*: gcc-patches at gcc dot gnu dot org*Date*: Mon, 11 Dec 2006 00:38:13 +0100*Subject*: [patch] Fix number_of_iterations_in_loop inconsistency

Hello, number_of_iterations_in_loop returns number of iterations by 1 higher than all the remaining functions. This is a bit confusing, and also inefficient (since the most common uses of number_of_iterations_in_loop, the returned number is immediatelly decreased by one). The patch fixes the problem by replacing this function with two new ones (number_of_latch_executions and number_of_exit_cond_executions), whose names are hopefully a bit less ambiguous about what they are doing. Bootstrapped & regtested on x86_64, commited. Zdenek Index: ChangeLog =================================================================== *** ChangeLog (revision 119717) --- ChangeLog (working copy) *************** *** 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. Index: testsuite/ChangeLog =================================================================== *** testsuite/ChangeLog (revision 119717) --- testsuite/ChangeLog (working copy) *************** *** 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 Index: doc/loop.texi =================================================================== *** doc/loop.texi (revision 119717) --- doc/loop.texi (working copy) *************** calculations. *** 397,409 **** @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: @itemize @item @code{assumptions}: If this condition is false, the rest of --- 397,411 ---- @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. 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 *************** number of iterations -- @code{find_loop_ *** 431,446 **** @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. 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). @node Dependency analysis @section Data Dependency Analysis --- 433,448 ---- @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_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_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 Index: tree-scalar-evolution.c =================================================================== *** tree-scalar-evolution.c (revision 119717) --- tree-scalar-evolution.c (working copy) *************** compute_overall_effect_of_inner_loop (st *** 468,487 **** 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); 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); --- 468,481 ---- if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num) { struct loop *inner_loop = get_chrec_loop (evolution_fn); ! tree nb_iter = number_of_latch_executions (inner_loop); if (nb_iter == chrec_dont_know) return chrec_dont_know; else { tree res; /* 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); *************** bool *** 510,516 **** chrec_is_positive (tree chrec, bool *value) { bool value0, value1, value2; ! tree type, end_value, nb_iter; switch (TREE_CODE (chrec)) { --- 504,510 ---- chrec_is_positive (tree chrec, bool *value) { bool value0, value1, value2; ! tree end_value, nb_iter; switch (TREE_CODE (chrec)) { *************** chrec_is_positive (tree chrec, bool *val *** 533,545 **** if (!evolution_function_is_affine_p (chrec)) return false; ! nb_iter = number_of_iterations_in_loop (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. */ --- 527,536 ---- 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. */ *************** static inline tree *** 892,910 **** 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 = "); --- 883,888 ---- *************** resolve_mixers (struct loop *loop, tree *** 2465,2471 **** the loop body has been executed 6 times. */ tree ! number_of_iterations_in_loop (struct loop *loop) { tree res, type; edge exit; --- 2443,2449 ---- the loop body has been executed 6 times. */ tree ! number_of_latch_executions (struct loop *loop) { tree res, type; edge exit; *************** end: *** 2500,2505 **** --- 2478,2510 ---- 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. */ *************** number_of_iterations_for_all_loops (VEC( *** 2514,2520 **** for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) { ! tree res = number_of_iterations_in_loop (loop_containing_stmt (cond)); if (chrec_contains_undetermined (res)) nb_chrec_dont_know_loops++; else --- 2519,2525 ---- for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++) { ! tree res = number_of_latch_executions (loop_containing_stmt (cond)); if (chrec_contains_undetermined (res)) nb_chrec_dont_know_loops++; else *************** scev_const_prop (void) *** 2956,2962 **** if (!exit) continue; ! niter = number_of_iterations_in_loop (loop); if (niter == chrec_dont_know /* If computing the number of iterations is expensive, it may be better not to introduce computations involving it. */ --- 2961,2967 ---- if (!exit) continue; ! 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. */ Index: tree-scalar-evolution.h =================================================================== *** tree-scalar-evolution.h (revision 119717) --- tree-scalar-evolution.h (working copy) *************** Software Foundation, 51 Franklin Street, *** 22,28 **** #ifndef GCC_TREE_SCALAR_EVOLUTION_H #define GCC_TREE_SCALAR_EVOLUTION_H ! extern tree number_of_iterations_in_loop (struct loop *); extern tree get_loop_exit_condition (struct loop *); extern void scev_initialize (void); --- 22,29 ---- #ifndef GCC_TREE_SCALAR_EVOLUTION_H #define GCC_TREE_SCALAR_EVOLUTION_H ! 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); Index: testsuite/gcc.dg/tree-ssa/loop-17.c =================================================================== *** testsuite/gcc.dg/tree-ssa/loop-17.c (revision 119717) --- testsuite/gcc.dg/tree-ssa/loop-17.c (working copy) *************** int foo (int *p) *** 15,19 **** return i; } ! /* { dg-final { scan-tree-dump "set_nb_iterations_in_loop = 2" "sccp" } } */ /* { dg-final { cleanup-tree-dump "sccp" } } */ --- 15,19 ---- return i; } ! /* { dg-final { scan-tree-dump "set_nb_iterations_in_loop = 1" "sccp" } } */ /* { dg-final { cleanup-tree-dump "sccp" } } */ Index: tree-ssa-loop-ivcanon.c =================================================================== *** tree-ssa-loop-ivcanon.c (revision 119717) --- tree-ssa-loop-ivcanon.c (working copy) *************** canonicalize_loop_induction_variables (s *** 279,296 **** edge exit = NULL; tree niter; ! niter = number_of_iterations_in_loop (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 { --- 279,290 ---- edge exit = NULL; tree niter; ! 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; } else { Index: tree-data-ref.c =================================================================== *** tree-data-ref.c (revision 119717) --- tree-data-ref.c (working copy) *************** static tree *** 2305,2311 **** get_number_of_iters_for_loop (int loopnum) { struct loop *loop = get_loop (loopnum); ! tree numiter = number_of_iterations_in_loop (loop); if (TREE_CODE (numiter) == INTEGER_CST) return numiter; --- 2305,2311 ---- get_number_of_iters_for_loop (int loopnum) { struct loop *loop = get_loop (loopnum); ! tree numiter = number_of_exit_cond_executions (loop); if (TREE_CODE (numiter) == INTEGER_CST) return numiter; Index: tree-vect-analyze.c =================================================================== *** tree-vect-analyze.c (revision 119717) --- tree-vect-analyze.c (working copy) *************** vect_get_loop_niters (struct loop *loop, *** 2393,2399 **** if (vect_print_dump_info (REPORT_DETAILS)) fprintf (vect_dump, "=== get_loop_niters ==="); ! niters = number_of_iterations_in_loop (loop); if (niters != NULL_TREE && niters != chrec_dont_know) --- 2393,2399 ---- if (vect_print_dump_info (REPORT_DETAILS)) fprintf (vect_dump, "=== get_loop_niters ==="); ! niters = number_of_exit_cond_executions (loop); if (niters != NULL_TREE && niters != chrec_dont_know) Index: cfgloop.h =================================================================== *** cfgloop.h (revision 119717) --- cfgloop.h (working copy) *************** struct loop *** 119,128 **** /* Auxiliary info specific to a pass. */ void *aux; ! /* The probable number of times the loop is executed at runtime. 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 information in this field. */ tree nb_iterations; --- 119,128 ---- /* Auxiliary info specific to a pass. */ void *aux; ! /* 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_latch_executions computes and caches the computed information in this field. */ tree nb_iterations;

**Follow-Ups**:**Re: [patch] Fix number_of_iterations_in_loop inconsistency***From:*Sebastian Pop

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |