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]

[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;
  


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]