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]

pretty-ipa merge 15: loop finiteness testing


Hi,
this patch adds finite_loop_p I would like to use in pure/const and cd-dce later.
It is basically same logic as in niter, just bit relaxed in three ways:

  1) It is not working hard enough to find minimal number of iterations
  2) In pure/const functions it assumes that all loops must be finite.
  3) It also assume for flag_unsafe_loop_optimizations.

I would hope that later we will add more tricks.

I also wonder why !just_once_each_iteration_p is needed here?  It does
not matter if the exit sits inside nested loop, right?

As for flag_unsafe_loop_optimizations, I would recall that there is really no
sane code possible that deals with this case of infinite loops.  The infinite
loop we are trying to disprove here is loop that do have exit edge, but its
conditional is never true for non-obvious reasons and it has absolutely no side
effects.  So even waiting for volatile variable to change or something is not
empty loop.  Only sane code would be to have such infinite loop interrupted by
signal and unrolled through, but then it is not sane to write it with
non-obvious exit condition.  Other compilers would remove such loops too based
on cd-dce algorithm.

Bootstrapped/regtested i686-linux, OK?

Honza

	* cfgloop.h (finite_loop_p): New function.
	* tree-ssa-loop-niter.c (finite_loop_p): New predicate.
	* tree-ssa-loop-ivcanon.c (empty_loop_p): Use it.

*** cfgloop.h	Sat Apr 25 10:54:48 2009
--- /aux/hubicka/pretty-ipa/gcc/cfgloop.h	Sat Apr 25 01:20:27 2009
*************** enum
*** 640,644 ****
--- 640,645 ----
  extern void unroll_and_peel_loops (int);
  extern void doloop_optimize_loops (void);
  extern void move_loop_invariants (void);
+ extern bool finite_loop_p (struct loop *);
  
  #endif /* GCC_CFGLOOP_H */
*** tree-ssa-loop-niter.c	Fri Apr  3 13:21:53 2009
--- /aux/hubicka/pretty-ipa/gcc/tree-ssa-loop-niter.c	Wed Apr 22 20:07:02 2009
*************** find_loop_niter (struct loop *loop, edge
*** 1953,1958 ****
--- 1953,2003 ----
    return niter ? niter : chrec_dont_know;
  }
  
+ /* Return true if loop is known to be finite.  */
+ 
+ bool
+ finite_loop_p (struct loop *loop)
+ {
+   unsigned i;
+   VEC (edge, heap) *exits = get_loop_exit_edges (loop);
+   edge ex;
+   struct tree_niter_desc desc;
+   bool finite = false;
+ 
+   if (flag_unsafe_loop_optimizations)
+     return true;
+   if ((TREE_READONLY (current_function_decl)
+        || DECL_PURE_P (current_function_decl))
+       && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
+     {
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
+ 		 loop->num);
+       return true;
+     }
+    
+   exits = get_loop_exit_edges (loop);
+   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
+     {
+       if (!just_once_each_iteration_p (loop, ex->src))
+ 	continue;
+ 
+       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;
+ 	}
+     }
+   VEC_free (edge, heap, exits);
+   return finite;
+ }
+ 
  /*
  
     Analysis of a number of iterations of a loop by a brute-force evaluation.
*** tree-ssa-loop-ivcanon.c	Fri Apr  3 13:21:53 2009
--- /aux/hubicka/pretty-ipa/gcc/tree-ssa-loop-ivcanon.c	Wed Apr 22 20:07:02 2009
*************** static bool
*** 395,401 ****
  empty_loop_p (struct loop *loop)
  {
    edge exit;
-   struct tree_niter_desc niter;
    basic_block *body;
    gimple_stmt_iterator gsi;
    unsigned i;
--- 395,400 ----
*************** empty_loop_p (struct loop *loop)
*** 408,414 ****
      return false;
  
    /* The loop must be finite.  */
!   if (!number_of_iterations_exit (loop, exit, &niter, false))
      return false;
  
    /* Values of all loop exit phi nodes must be invariants.  */
--- 407,413 ----
      return false;
  
    /* The loop must be finite.  */
!   if (!finite_loop_p (loop))
      return false;
  
    /* Values of all loop exit phi nodes must be invariants.  */


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