Patchwork Modernize loop_finite_p

login
register
mail settings
Submitter Jan Hubicka
Date Oct. 31, 2012, 12:23 p.m.
Message ID <20121031122307.GB15866@kam.mff.cuni.cz>
Download mbox | patch
Permalink /patch/195859/
State New
Headers show

Comments

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.
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

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;
 }
 
 /*