Modernize loop_finite_p

Submitted by Jan Hubicka on Oct. 31, 2012, 12:23 p.m.

Details

Message ID 20121031122307.GB15866@kam.mff.cuni.cz
State New
Headers show

Commit Message

Jan Hubicka Oct. 31, 2012, 12:23 p.m.
Hi,
this patch changes finite_loop_p to use max_loop_iterations.  Long time ago I made
finite_loop_p as rip-off from the max_loop_iterations skipping parts that are not
exactly related to the number of iteration estimates.  It went out of date since then
completelly missing the bounds derived from overflows and array bounds that are quite
useful.

So I guess these days it is better to simply implement it using max_loop_iterations,
we do not save that much of effort and we can store the result.

Bootstrapped/regtested x86_64, OK?

Honza

	* tree-ssa-loop-niter.c (finite_loop_p): Reorg to use max_loop_iterations.

Comments

Richard Guenther Oct. 31, 2012, 12:34 p.m.
On Wed, 31 Oct 2012, Jan Hubicka wrote:

> Hi,
> this patch changes finite_loop_p to use max_loop_iterations.  Long time ago I made
> finite_loop_p as rip-off from the max_loop_iterations skipping parts that are not
> exactly related to the number of iteration estimates.  It went out of date since then
> completelly missing the bounds derived from overflows and array bounds that are quite
> useful.
> 
> So I guess these days it is better to simply implement it using max_loop_iterations,
> we do not save that much of effort and we can store the result.
> 
> Bootstrapped/regtested x86_64, OK?
> 
> Honza
> 
> 	* tree-ssa-loop-niter.c (finite_loop_p): Reorg to use max_loop_iterations.
> Index: tree-ssa-loop-niter.c
> ===================================================================
> --- tree-ssa-loop-niter.c	(revision 192991)
> +++ tree-ssa-loop-niter.c	(working copy)
> @@ -1993,11 +1990,7 @@ find_loop_niter (struct loop *loop, edge
>  bool
>  finite_loop_p (struct loop *loop)
>  {
> -  unsigned i;
> -  VEC (edge, heap) *exits;
> -  edge ex;
> -  struct tree_niter_desc desc;
> -  bool finite = false;
> +  double_int nit;
>    int flags;
>  
>    if (flag_unsafe_loop_optimizations)
> @@ -2011,26 +2004,22 @@ finite_loop_p (struct loop *loop)
>        return true;
>      }
>  
> -  exits = get_loop_exit_edges (loop);
> -  FOR_EACH_VEC_ELT (edge, exits, i, ex)
> +  if (loop->any_upper_bound)
>      {
> -      if (!just_once_each_iteration_p (loop, ex->src))
> -	continue;
> +      if (dump_file && (dump_flags & TDF_DETAILS))
> +	fprintf (dump_file, "Found loop %i to be finite: upper bound is recorded.\n",
> +		 loop->num);
> +      return true;
> +    }

This looks redundant with ...

> -      if (number_of_iterations_exit (loop, ex, &desc, false))
> -        {
> -	  if (dump_file && (dump_flags & TDF_DETAILS))
> -	    {
> -	      fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
> -	      print_generic_expr (dump_file, desc.niter, TDF_SLIM);
> -	      fprintf (dump_file, " times\n");
> -	    }
> -	  finite = true;
> -	  break;
> -	}
> +  if (max_loop_iterations (loop, &nit))
> +    {

... this.  If you want to short-circuit max_loop_iterations ()
then why not

   if (loop->any_upper_bound
       || max_loop_iterations (loop, &nit))
     {
       ...

?  The different dumping seems not a good reason to obfuscate it.

Richard.

> +      if (dump_file && (dump_flags & TDF_DETAILS))
> +	fprintf (dump_file, "Found loop %i to be finite: upper bound found.\n",
> +		 loop->num);
> +      return true;
>      }
> -  VEC_free (edge, heap, exits);
> -  return finite;
> +  return false;
>  }
>  
>  /*
Jan Hubicka Oct. 31, 2012, 2:02 p.m.
> > -  FOR_EACH_VEC_ELT (edge, exits, i, ex)
> > +  if (loop->any_upper_bound)
> >      {
> > -      if (!just_once_each_iteration_p (loop, ex->src))
> > -	continue;
> > +      if (dump_file && (dump_flags & TDF_DETAILS))
> > +	fprintf (dump_file, "Found loop %i to be finite: upper bound is recorded.\n",
> > +		 loop->num);
> > +      return true;
> > +    }
> 
> This looks redundant with ...
> 
> > -      if (number_of_iterations_exit (loop, ex, &desc, false))
> > -        {
> > -	  if (dump_file && (dump_flags & TDF_DETAILS))
> > -	    {
> > -	      fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
> > -	      print_generic_expr (dump_file, desc.niter, TDF_SLIM);
> > -	      fprintf (dump_file, " times\n");
> > -	    }
> > -	  finite = true;
> > -	  break;
> > -	}
> > +  if (max_loop_iterations (loop, &nit))
> > +    {
> 
> ... this.  If you want to short-circuit max_loop_iterations ()
> then why not
> 
>    if (loop->any_upper_bound
>        || max_loop_iterations (loop, &nit))
>      {
>        ...
> 
> ?  The different dumping seems not a good reason to obfuscate it.
> 

Sounds good to me.  I only wanted to avoid max_loop_iterations re-trying to
derrive the bound when it is already known to be finite.  I think I will
eventually make max_loop_iterations and friends to do the hard work only once
per loop optimizer queue or when asked to collect the current bounds (since
the pointers to statements are hard to maintain).

OK with that change?
Honza
Richard Guenther Oct. 31, 2012, 2:04 p.m.
On Wed, 31 Oct 2012, Jan Hubicka wrote:

> > > -  FOR_EACH_VEC_ELT (edge, exits, i, ex)
> > > +  if (loop->any_upper_bound)
> > >      {
> > > -      if (!just_once_each_iteration_p (loop, ex->src))
> > > -	continue;
> > > +      if (dump_file && (dump_flags & TDF_DETAILS))
> > > +	fprintf (dump_file, "Found loop %i to be finite: upper bound is recorded.\n",
> > > +		 loop->num);
> > > +      return true;
> > > +    }
> > 
> > This looks redundant with ...
> > 
> > > -      if (number_of_iterations_exit (loop, ex, &desc, false))
> > > -        {
> > > -	  if (dump_file && (dump_flags & TDF_DETAILS))
> > > -	    {
> > > -	      fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
> > > -	      print_generic_expr (dump_file, desc.niter, TDF_SLIM);
> > > -	      fprintf (dump_file, " times\n");
> > > -	    }
> > > -	  finite = true;
> > > -	  break;
> > > -	}
> > > +  if (max_loop_iterations (loop, &nit))
> > > +    {
> > 
> > ... this.  If you want to short-circuit max_loop_iterations ()
> > then why not
> > 
> >    if (loop->any_upper_bound
> >        || max_loop_iterations (loop, &nit))
> >      {
> >        ...
> > 
> > ?  The different dumping seems not a good reason to obfuscate it.
> > 
> 
> Sounds good to me.  I only wanted to avoid max_loop_iterations re-trying to
> derrive the bound when it is already known to be finite.  I think I will
> eventually make max_loop_iterations and friends to do the hard work only once
> per loop optimizer queue or when asked to collect the current bounds (since
> the pointers to statements are hard to maintain).
> 
> OK with that change?

Ok.

Thanks,
Richard.

Patch hide | download patch | download mbox

Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c	(revision 192991)
+++ tree-ssa-loop-niter.c	(working copy)
@@ -1993,11 +1990,7 @@  find_loop_niter (struct loop *loop, edge
 bool
 finite_loop_p (struct loop *loop)
 {
-  unsigned i;
-  VEC (edge, heap) *exits;
-  edge ex;
-  struct tree_niter_desc desc;
-  bool finite = false;
+  double_int nit;
   int flags;
 
   if (flag_unsafe_loop_optimizations)
@@ -2011,26 +2004,22 @@  finite_loop_p (struct loop *loop)
       return true;
     }
 
-  exits = get_loop_exit_edges (loop);
-  FOR_EACH_VEC_ELT (edge, exits, i, ex)
+  if (loop->any_upper_bound)
     {
-      if (!just_once_each_iteration_p (loop, ex->src))
-	continue;
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Found loop %i to be finite: upper bound is recorded.\n",
+		 loop->num);
+      return true;
+    }
 
-      if (number_of_iterations_exit (loop, ex, &desc, false))
-        {
-	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    {
-	      fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
-	      print_generic_expr (dump_file, desc.niter, TDF_SLIM);
-	      fprintf (dump_file, " times\n");
-	    }
-	  finite = true;
-	  break;
-	}
+  if (max_loop_iterations (loop, &nit))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "Found loop %i to be finite: upper bound found.\n",
+		 loop->num);
+      return true;
     }
-  VEC_free (edge, heap, exits);
-  return finite;
+  return false;
 }
 
 /*