This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Fix number_of_iterations_in_loop inconsistency
- 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;