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]

Re: [patch] Add tree-ssa-loop.h and friends.


On 10/08/2013 09:18 AM, Richard Biener wrote:
On Tue, Oct 8, 2013 at 2:58 PM, Andrew MacLeod <amacleod@redhat.com> wrote:

I just took a quick stab at it...  I think its pretty involved and someone
with better loop comprehension should probably look at the followup of
removing that requirement. estimate_numbers_of_iterations_loop() in
particular uses last_stmt(), so it requires gimple.. and there is sprinkling
of gimple specific stuff all through it...  I have no idea how this is
suppose to work for rtl.

This is the way it is now, so at least by including that header, it
exposes the hidden problem and either I can revisit it later, or someone
else can tackle that.  it seems *really* messy.

OK as is for now?

Andrew
heh, make it available, and it will get used :-)  It hasn't been this that
way that long.
Well, that's just accessing already computed and preserved max-iteration.

That is, the accessors used by loop-*.c should probably be moved to
cfgloop.[ch].


huh, deeper than I intended to go but not too bad. OK... how about this as an add-on to the previous patch. I'd just check in the combination all at once. A couple of the functions needed to be separated... so I created get_estimated_loop_iterations() and get_max_loop_iterations()... hopefully I did that right. basically I pulled out everything but the scev estimating,a dn left that in the original. This bootstraps, and regression tests are running.

Assuming it all works out, is this ok?

Andrew

	* cfgloop.c (record_niter_bound, estimated_loop_iterations_int,
	max_stmt_executions_int): Move from tree-ssa-loop-niter.c.
	(get_estimated_loop_iterations): Factor out accessor from 
	estimated_loop_iterations in tree-ssa-loop-niter.c.
	(get_max_loop_iterations): Factor out accessor from _max_loop_iterations
	in tree-ssa-niter.c.
	* cfgloop.h: Add prototypes.
	(gcov_type_to_double_int): relocate from tree-ssa-loop.niter.c.
	* loop-iv.c: Don't include tree-ssa-niter.h.
	* loop-unroll.c: Don't include tree-ssa-niter.h.
	(decide_unroll_constant_iterations, decide_unroll_runtime_iterations,
	decide_peel_simple, decide_unroll_stupid): Use new get_* accessors.
	* loop-unswitch.c: Don't include tree-ssa-niter.h.
	* tree-ssa-loop-niter.c (record_niter_bound): Move to cfgloop.c/
	(gcov_type_to_double_int): Move to cfgloop.h.
	(estimated_loop_iterations): Factor out get_estimated_loop_iterations.
	(max_loop_iterations): Factor out get_max_loop_iterations.
	(estimated_loop_iterations_int, max_stmt_executions_int): Move to 
	cfgloop.c.
	* tree-ssa-loop-niter.h: Remove a few prototypes.

diff -cNp L/cfgloop.c ./cfgloop.c
*** L/cfgloop.c	2013-10-08 09:28:03.609369504 -0400
--- ./cfgloop.c	2013-10-08 09:48:17.867054642 -0400
*************** get_loop_location (struct loop *loop)
*** 1781,1783 ****
--- 1781,1893 ----
    return DECL_SOURCE_LOCATION (current_function_decl);
  }
  
+ /* Records that every statement in LOOP is executed I_BOUND times.
+    REALISTIC is true if I_BOUND is expected to be close to the real number
+    of iterations.  UPPER is true if we are sure the loop iterates at most
+    I_BOUND times.  */
+ 
+ void
+ record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
+ 		    bool upper)
+ {
+   /* Update the bounds only when there is no previous estimation, or when the
+      current estimation is smaller.  */
+   if (upper
+       && (!loop->any_upper_bound
+ 	  || i_bound.ult (loop->nb_iterations_upper_bound)))
+     {
+       loop->any_upper_bound = true;
+       loop->nb_iterations_upper_bound = i_bound;
+     }
+   if (realistic
+       && (!loop->any_estimate
+ 	  || i_bound.ult (loop->nb_iterations_estimate)))
+     {
+       loop->any_estimate = true;
+       loop->nb_iterations_estimate = i_bound;
+     }
+ 
+   /* If an upper bound is smaller than the realistic estimate of the
+      number of iterations, use the upper bound instead.  */
+   if (loop->any_upper_bound
+       && loop->any_estimate
+       && loop->nb_iterations_upper_bound.ult (loop->nb_iterations_estimate))
+     loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
+ }
+ 
+ /* Similar to estimated_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
+ estimated_loop_iterations_int (struct loop *loop)
+ {
+   double_int nit;
+   HOST_WIDE_INT hwi_nit;
+ 
+   if (!estimated_loop_iterations (loop, &nit))
+     return -1;
+ 
+   if (!nit.fits_shwi ())
+     return -1;
+   hwi_nit = nit.to_shwi ();
+ 
+   return hwi_nit < 0 ? -1 : hwi_nit;
+ }
+ 
+ /* Returns an upper bound on 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
+ max_stmt_executions_int (struct loop *loop)
+ {
+   HOST_WIDE_INT nit = max_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 number of executions of the latch of the
+    LOOP.  If we have no reliable estimate, the function returns false, otherwise
+    returns true.  */
+ 
+ bool
+ get_estimated_loop_iterations (struct loop *loop, double_int *nit)
+ {
+   /* Even if the bound is not recorded, possibly we can derrive one from
+      profile.  */
+   if (!loop->any_estimate)
+     {
+       if (loop->header->count)
+ 	{
+           *nit = gcov_type_to_double_int
+ 		   (expected_loop_iterations_unbounded (loop) + 1);
+ 	  return true;
+ 	}
+       return false;
+     }
+ 
+   *nit = loop->nb_iterations_estimate;
+   return true;
+ }
+ 
+ /* 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
+ get_max_loop_iterations (struct loop *loop, double_int *nit)
+ {
+   if (!loop->any_upper_bound)
+     return false;
+ 
+   *nit = loop->nb_iterations_upper_bound;
+   return true;
+ }
diff -cNp L/cfgloop.h ./cfgloop.h
*** L/cfgloop.h	2013-10-08 09:28:03.609369504 -0400
--- ./cfgloop.h	2013-10-08 09:53:27.530942881 -0400
*************** loop_outermost (struct loop *loop)
*** 739,743 ****
--- 739,764 ----
    return (*loop->superloops)[1];
  }
  
+ extern void record_niter_bound (struct loop *, double_int, bool, bool);
+ extern HOST_WIDE_INT estimated_loop_iterations_int (struct loop *);
+ extern HOST_WIDE_INT max_loop_iterations_int (struct loop *);
+ extern bool get_estimated_loop_iterations (struct loop *loop, double_int *nit);
+ extern bool get_max_loop_iterations (struct loop *loop, double_int *nit);
  
+ /* Converts VAL to double_int.  */
+ 
+ static inline double_int
+ gcov_type_to_double_int (gcov_type val)
+ {
+   double_int ret;
+ 
+   ret.low = (unsigned HOST_WIDE_INT) val;
+   /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
+      the size of type.  */
+   val >>= HOST_BITS_PER_WIDE_INT - 1;
+   val >>= 1;
+   ret.high = (unsigned HOST_WIDE_INT) val;
+ 
+   return ret;
+ }
  #endif /* GCC_CFGLOOP_H */
diff -cNp L/loop-iv.c ./loop-iv.c
*** L/loop-iv.c	2013-10-08 09:28:03.658369491 -0400
--- ./loop-iv.c	2013-10-08 09:28:07.577368487 -0400
*************** along with GCC; see the file COPYING3.
*** 62,68 ****
  #include "df.h"
  #include "hash-table.h"
  #include "dumpfile.h"
- #include "tree-ssa-loop-niter.h"
  
  /* Possible return values of iv_get_reaching_def.  */
  
--- 62,67 ----
diff -cNp L/loop-unroll.c ./loop-unroll.c
*** L/loop-unroll.c	2013-10-08 09:28:03.658369491 -0400
--- ./loop-unroll.c	2013-10-08 09:42:26.258153423 -0400
*************** along with GCC; see the file COPYING3.
*** 32,38 ****
  #include "recog.h"
  #include "target.h"
  #include "dumpfile.h"
- #include "tree-ssa-loop-niter.h"
  
  /* This pass performs loop unrolling and peeling.  We only perform these
     optimizations on innermost loops (with single exception) because
--- 32,37 ----
*************** decide_unroll_constant_iterations (struc
*** 695,702 ****
       than one exit it may well loop less than determined maximal number
       of iterations.  */
    if (desc->niter < 2 * nunroll
!       || ((estimated_loop_iterations (loop, &iterations)
! 	   || max_loop_iterations (loop, &iterations))
  	  && iterations.ult (double_int::from_shwi (2 * nunroll))))
      {
        if (dump_file)
--- 694,701 ----
       than one exit it may well loop less than determined maximal number
       of iterations.  */
    if (desc->niter < 2 * nunroll
!       || ((get_estimated_loop_iterations (loop, &iterations)
! 	   || get_max_loop_iterations (loop, &iterations))
  	  && iterations.ult (double_int::from_shwi (2 * nunroll))))
      {
        if (dump_file)
*************** decide_unroll_runtime_iterations (struct
*** 1000,1007 ****
      }
  
    /* Check whether the loop rolls.  */
!   if ((estimated_loop_iterations (loop, &iterations)
!        || max_loop_iterations (loop, &iterations))
        && iterations.ult (double_int::from_shwi (2 * nunroll)))
      {
        if (dump_file)
--- 999,1006 ----
      }
  
    /* Check whether the loop rolls.  */
!   if ((get_estimated_loop_iterations (loop, &iterations)
!        || get_max_loop_iterations (loop, &iterations))
        && iterations.ult (double_int::from_shwi (2 * nunroll)))
      {
        if (dump_file)
*************** decide_peel_simple (struct loop *loop, i
*** 1389,1395 ****
      }
  
    /* If we have realistic estimate on number of iterations, use it.  */
!   if (estimated_loop_iterations (loop, &iterations))
      {
        if (double_int::from_shwi (npeel).ule (iterations))
  	{
--- 1388,1394 ----
      }
  
    /* If we have realistic estimate on number of iterations, use it.  */
!   if (get_estimated_loop_iterations (loop, &iterations))
      {
        if (double_int::from_shwi (npeel).ule (iterations))
  	{
*************** decide_peel_simple (struct loop *loop, i
*** 1407,1413 ****
      }
    /* If we have small enough bound on iterations, we can still peel (completely
       unroll).  */
!   else if (max_loop_iterations (loop, &iterations)
             && iterations.ult (double_int::from_shwi (npeel)))
      npeel = iterations.to_shwi () + 1;
    else
--- 1406,1412 ----
      }
    /* If we have small enough bound on iterations, we can still peel (completely
       unroll).  */
!   else if (get_max_loop_iterations (loop, &iterations)
             && iterations.ult (double_int::from_shwi (npeel)))
      npeel = iterations.to_shwi () + 1;
    else
*************** decide_unroll_stupid (struct loop *loop,
*** 1557,1564 ****
      }
  
    /* Check whether the loop rolls.  */
!   if ((estimated_loop_iterations (loop, &iterations)
!        || max_loop_iterations (loop, &iterations))
        && iterations.ult (double_int::from_shwi (2 * nunroll)))
      {
        if (dump_file)
--- 1556,1563 ----
      }
  
    /* Check whether the loop rolls.  */
!   if ((get_estimated_loop_iterations (loop, &iterations)
!        || get_max_loop_iterations (loop, &iterations))
        && iterations.ult (double_int::from_shwi (2 * nunroll)))
      {
        if (dump_file)
diff -cNp L/loop-unswitch.c ./loop-unswitch.c
*** L/loop-unswitch.c	2013-10-08 09:28:03.658369491 -0400
--- ./loop-unswitch.c	2013-10-08 09:28:07.579368487 -0400
*************** along with GCC; see the file COPYING3.
*** 29,35 ****
  #include "params.h"
  #include "expr.h"
  #include "dumpfile.h"
- #include "tree-ssa-loop-niter.h"
  
  /* This pass moves constant conditions out of loops, duplicating the loop
     in progress, i.e. this code:
--- 29,34 ----
diff -cNp L/tree-ssa-loop-niter.c ./tree-ssa-loop-niter.c
*** L/tree-ssa-loop-niter.c	2013-10-08 09:28:03.907369429 -0400
--- ./tree-ssa-loop-niter.c	2013-10-08 10:08:30.877510866 -0400
*************** derive_constant_upper_bound_ops (tree ty
*** 2507,2546 ****
      }
  }
  
- /* Records that every statement in LOOP is executed I_BOUND times.
-    REALISTIC is true if I_BOUND is expected to be close to the real number
-    of iterations.  UPPER is true if we are sure the loop iterates at most
-    I_BOUND times.  */
- 
- void
- record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
- 		    bool upper)
- {
-   /* Update the bounds only when there is no previous estimation, or when the
-      current estimation is smaller.  */
-   if (upper
-       && (!loop->any_upper_bound
- 	  || i_bound.ult (loop->nb_iterations_upper_bound)))
-     {
-       loop->any_upper_bound = true;
-       loop->nb_iterations_upper_bound = i_bound;
-     }
-   if (realistic
-       && (!loop->any_estimate
- 	  || i_bound.ult (loop->nb_iterations_estimate)))
-     {
-       loop->any_estimate = true;
-       loop->nb_iterations_estimate = i_bound;
-     }
- 
-   /* If an upper bound is smaller than the realistic estimate of the
-      number of iterations, use the upper bound instead.  */
-   if (loop->any_upper_bound
-       && loop->any_estimate
-       && loop->nb_iterations_upper_bound.ult (loop->nb_iterations_estimate))
-     loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
- }
- 
  /* Emit a -Waggressive-loop-optimizations warning if needed.  */
  
  static void
--- 2507,2512 ----
*************** infer_loop_bounds_from_undefined (struct
*** 3008,3029 ****
    free (bbs);
  }
  
- /* Converts VAL to double_int.  */
  
- static double_int
- gcov_type_to_double_int (gcov_type val)
- {
-   double_int ret;
- 
-   ret.low = (unsigned HOST_WIDE_INT) val;
-   /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
-      the size of type.  */
-   val >>= HOST_BITS_PER_WIDE_INT - 1;
-   val >>= 1;
-   ret.high = (unsigned HOST_WIDE_INT) val;
- 
-   return ret;
- }
  
  /* Compare double ints, callback for qsort.  */
  
--- 2974,2980 ----
*************** estimated_loop_iterations (struct loop *
*** 3433,3453 ****
    if (scev_initialized_p ())
      estimate_numbers_of_iterations_loop (loop);
  
!   /* Even if the bound is not recorded, possibly we can derrive one from
!      profile.  */
!   if (!loop->any_estimate)
!     {
!       if (loop->header->count)
! 	{
!           *nit = gcov_type_to_double_int
! 		   (expected_loop_iterations_unbounded (loop) + 1);
! 	  return true;
! 	}
!       return false;
!     }
! 
!   *nit = loop->nb_iterations_estimate;
!   return true;
  }
  
  /* Sets NIT to an upper bound for the maximum number of executions of the
--- 3384,3390 ----
    if (scev_initialized_p ())
      estimate_numbers_of_iterations_loop (loop);
  
!   return (get_estimated_loop_iterations (loop, nit));
  }
  
  /* Sets NIT to an upper bound for the maximum number of executions of the
*************** max_loop_iterations (struct loop *loop,
*** 3461,3491 ****
       estimate.  Otherwise just return whatever we recorded earlier.  */
    if (scev_initialized_p ())
      estimate_numbers_of_iterations_loop (loop);
-   if (!loop->any_upper_bound)
-     return false;
  
!   *nit = loop->nb_iterations_upper_bound;
!   return true;
! }
! 
! /* Similar to estimated_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
! estimated_loop_iterations_int (struct loop *loop)
! {
!   double_int nit;
!   HOST_WIDE_INT hwi_nit;
! 
!   if (!estimated_loop_iterations (loop, &nit))
!     return -1;
! 
!   if (!nit.fits_shwi ())
!     return -1;
!   hwi_nit = nit.to_shwi ();
! 
!   return hwi_nit < 0 ? -1 : hwi_nit;
  }
  
  /* Similar to max_loop_iterations, but returns the estimate only
--- 3398,3405 ----
       estimate.  Otherwise just return whatever we recorded earlier.  */
    if (scev_initialized_p ())
      estimate_numbers_of_iterations_loop (loop);
  
!   return get_max_loop_iterations (loop, nit);
  }
  
  /* Similar to max_loop_iterations, but returns the estimate only
*************** max_loop_iterations_int (struct loop *lo
*** 3508,3532 ****
    return hwi_nit < 0 ? -1 : hwi_nit;
  }
  
- /* Returns an upper bound on 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
- max_stmt_executions_int (struct loop *loop)
- {
-   HOST_WIDE_INT nit = max_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;
- }
- 
  /* 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.  */
--- 3422,3427 ----
diff -cNp L/tree-ssa-loop-niter.h ./tree-ssa-loop-niter.h
*** L/tree-ssa-loop-niter.h	2013-10-08 09:28:03.908369427 -0400
--- ./tree-ssa-loop-niter.h	2013-10-08 09:34:17.798274598 -0400
*************** extern tree find_loop_niter (struct loop
*** 29,38 ****
  extern bool finite_loop_p (struct loop *);
  extern tree loop_niter_by_eval (struct loop *, edge);
  extern tree find_loop_niter_by_eval (struct loop *, edge *);
- extern void record_niter_bound (struct loop *, double_int, bool, bool);
  extern bool estimated_loop_iterations (struct loop *, double_int *);
  extern bool max_loop_iterations (struct loop *, double_int *);
- extern HOST_WIDE_INT estimated_loop_iterations_int (struct loop *);
  extern HOST_WIDE_INT max_loop_iterations_int (struct loop *);
  extern HOST_WIDE_INT max_stmt_executions_int (struct loop *);
  extern HOST_WIDE_INT estimated_stmt_executions_int (struct loop *);
--- 29,36 ----
*************** extern tree find_loop_niter_by_eval (str
*** 81,88 ****
  extern void record_niter_bound (struct loop *, double_int, bool, bool);
  extern bool estimated_loop_iterations (struct loop *, double_int *);
  extern bool max_loop_iterations (struct loop *, double_int *);
- extern HOST_WIDE_INT estimated_loop_iterations_int (struct loop *);
- extern HOST_WIDE_INT max_loop_iterations_int (struct loop *);
  extern HOST_WIDE_INT max_stmt_executions_int (struct loop *);
  extern HOST_WIDE_INT estimated_stmt_executions_int (struct loop *);
  extern bool max_stmt_executions (struct loop *, double_int *);
--- 79,84 ----

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