re PR rtl-optimization/19210 (not using do-loop for some loops)

gcc:
2005-07-21  Paolo Bonzini  <bonzini@gnu.org>
            Zdenek Dvorak  <dvorakz@suse.cz>

	PR tree-optimization/19210
	* common.opt (Wunsafe-loop-optimizations, funsafe-loop-optimizations):
	New.
	* Makefile.in (tree-ssa-loop-niter.o): Depend intl.o.
	* loop-iv.c (get_simple_loop_desc): If -funsafe-loop-optimizations,
	rely on unproven assumptions.
	* predict.c (predict_loops): Adjust call to number_of_iterations_exit.
	* tree-flow.h (number_of_iterations_exit): Add final parameter.
	* tree-scalar-evolution.c (number_of_iterations_in_loop): Adjust call
	to number_of_iterations_exit.
	* tree-ssa-loop-ivcanon.c (empty_loop_p): Likewise.
	* tree-ssa-loop-ivopts.c (niter_for_exit): Likewise.
	* tree-ssa-loop-niter.c (find_loop_niter,
	estimate_numbers_of_iterations_loop): Likewise.
	(number_of_iterations_exit): Honor the new options.
	* doc/invoke.texi (Wunsafe-loop-optimizations,
	funsafe-loop-optimizations): Document them.

gcc/testsuite:
2005-07-21  Paolo Bonzini  <bonzini@gnu.org>

        * gcc.dg/tree-ssa/pr19210-1.c: New.
        * gcc.dg/tree-ssa/pr19210-2.c: New.

Co-Authored-By: Zdenek Dvorak <dvorakz@suse.cz>

From-SVN: r102225

14 files changed, 193 insertions, 14 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index e5e533f..2777cbd 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,24 @@
+2005-07-21  Paolo Bonzini  <bonzini@gnu.org>
+            Zdenek Dvorak  <dvorakz@suse.cz>
+
+	PR tree-optimization/19210
+	* common.opt (Wunsafe-loop-optimizations, funsafe-loop-optimizations):
+	New.
+	* Makefile.in (tree-ssa-loop-niter.o): Depend intl.o.
+	* loop-iv.c (get_simple_loop_desc): If -funsafe-loop-optimizations,
+	rely on unproven assumptions.
+	* predict.c (predict_loops): Adjust call to number_of_iterations_exit.
+	* tree-flow.h (number_of_iterations_exit): Add final parameter.
+	* tree-scalar-evolution.c (number_of_iterations_in_loop): Adjust call
+	to number_of_iterations_exit.
+	* tree-ssa-loop-ivcanon.c (empty_loop_p): Likewise.
+	* tree-ssa-loop-ivopts.c (niter_for_exit): Likewise.
+	* tree-ssa-loop-niter.c (find_loop_niter,
+	estimate_numbers_of_iterations_loop): Likewise.
+	(number_of_iterations_exit): Honor the new options.
+	* doc/invoke.texi (Wunsafe-loop-optimizations,
+	funsafe-loop-optimizations): Document them.
+
 2005-07-21  Richard Sandiford  <richard@codesourcery.com>
 
 	PR rtl-optimization/22167
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index cc52cc3..1cbdf68 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1869,7 +1869,7 @@ tree-ssa-loop-niter.o : tree-ssa-loop-niter.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(PARAMS_H) \
    tree-inline.h output.h $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
    $(FLAGS_H) tree-pass.h $(SCEV_H) $(TREE_DATA_REF_H) $(BASIC_BLOCK_H) \
-   $(GGC_H) hard-reg-set.h tree-chrec.h
+   $(GGC_H) hard-reg-set.h tree-chrec.h intl.h
 tree-ssa-loop-ivcanon.o : tree-ssa-loop-ivcanon.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(PARAMS_H) \
    tree-inline.h output.h $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
@@ -2288,7 +2288,7 @@ cfgloopanal.o : cfgloopanal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
    $(OBSTACK_H) output.h
 loop-iv.o : loop-iv.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(BASIC_BLOCK_H) \
    hard-reg-set.h $(CFGLOOP_H) $(EXPR_H) coretypes.h $(TM_H) $(OBSTACK_H) \
-   output.h
+   output.h intl.h
 loop-invariant.o : loop-invariant.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
    $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(EXPR_H) coretypes.h \
    $(TM_H) function.h $(FLAGS_H) $(DF_H) $(OBSTACK_H) output.h
diff --git a/gcc/common.opt b/gcc/common.opt
index c6ab109..cf138ee 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -93,6 +93,10 @@ Wlarger-than-
 Common RejectNegative Joined UInteger
 -Wlarger-than-<number>	Warn if an object is larger than <number> bytes
 
+Wunsafe-loop-optimizations
+Common Var(warn_unsafe_loop_optimizations)
+Warn if the loop cannot be optimized due to nontrivial assumptions.
+
 Wmissing-noreturn
 Common Var(warn_missing_noreturn)
 Warn about functions which might be candidates for __attribute__((noreturn))
@@ -402,6 +406,10 @@ fforce-mem
 Common Report Var(flag_force_mem)
 Copy memory operands into registers before use
 
+fforward-propagate
+Common Report Var(flag_forward_propagate)
+Perform a forward propagation pass on RTL
+
 ; Nonzero means don't put addresses of constant functions in registers.
 ; Used for compiling the Unix kernel, where strange substitutions are
 ; done on the assembly output.
@@ -963,6 +971,13 @@ funroll-all-loops
 Common Report Var(flag_unroll_all_loops)
 Perform loop unrolling for all loops
 
+; Nonzero means that loop optimizer may assume that the induction variables
+; that control loops do not overflow and that the loops with nontrivial
+; exit condition are not infinite
+funsafe-loop-optimizations
+Common Report Var(flag_unsafe_loop_optimizations)
+Allow loop optimizations to assume that the loops behave in normal way
+
 ; Nonzero means that unsafe floating-point math optimizations are allowed
 ; for the sake of speed.  IEEE compliance is not guaranteed, and operations
 ; are allowed to assume that their arguments and results are "normal"
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 45e2a25..4685c63 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -230,7 +230,7 @@ Objective-C and Objective-C++ Dialects}.
 -Wimport  -Wno-import  -Winit-self  -Winline @gol
 -Wno-int-to-pointer-cast @gol
 -Wno-invalid-offsetof  -Winvalid-pch @gol
--Wlarger-than-@var{len}  -Wlong-long @gol
+-Wlarger-than-@var{len}  -Wunsafe-loop-optimizations  -Wlong-long @gol
 -Wmain  -Wmissing-braces  -Wmissing-field-initializers @gol
 -Wmissing-format-attribute  -Wmissing-include-dirs @gol
 -Wmissing-noreturn @gol
@@ -311,7 +311,7 @@ Objective-C and Objective-C++ Dialects}.
 -fno-default-inline  -fno-defer-pop -floop-optimize2 -fmove-loop-invariants @gol
 -fno-function-cse  -fno-guess-branch-probability @gol
 -fno-inline  -fno-math-errno  -fno-peephole  -fno-peephole2 @gol
--funsafe-math-optimizations  -ffinite-math-only @gol
+-funsafe-math-optimizations  -funsafe-loop-optimizations  -ffinite-math-only @gol
 -fno-trapping-math  -fno-zero-initialized-in-bss @gol
 -fomit-frame-pointer  -foptimize-register-move @gol
 -foptimize-sibling-calls  -fprefetch-loop-arrays @gol
@@ -2988,6 +2988,13 @@ global variable or whenever a built-in function is shadowed.
 @opindex Wlarger-than
 Warn whenever an object of larger than @var{len} bytes is defined.
 
+@item -Wunsafe-loop-optimizations
+@opindex Wunsafe-loop-optimizations
+Warn if the loop cannot be optimized because the compiler could not
+assume anything on the bounds of the loop indices.  With
+@option{-funsafe-loop-optimizations} warn if the compiler made
+such assumptions.
+
 @item -Wpointer-arith
 @opindex Wpointer-arith
 Warn about anything that depends on the ``size of'' a function type or
@@ -4728,6 +4735,15 @@ Perform loop optimizations using the new loop optimizer.  The optimizations
 (loop unrolling, peeling and unswitching, loop invariant motion) are enabled
 by separate flags.
 
+@item -funsafe-loop-optimizations
+@opindex funsafe-loop-optimizations
+If given, the loop optimizer will assume that loop indices do not
+overflow, and that the loops with nontrivial exit condition are not
+infinite.  This enables a wider range of loop optimizations even if
+the loop optimizer itself cannot prove that these assumptions are valid.
+Using @option{-Wunsafe-loop-optimizations}, the compiler will warn you
+if it finds this kind of loop.
+
 @item -fcrossjumping
 @opindex crossjumping
 Perform cross-jumping transformation.  This transformation unifies equivalent code and save code size.  The
diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c
index 48bae0b..7c7a5de 100644
--- a/gcc/loop-iv.c
+++ b/gcc/loop-iv.c
@@ -57,7 +57,9 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "basic-block.h"
 #include "cfgloop.h"
 #include "expr.h"
+#include "intl.h"
 #include "output.h"
+#include "toplev.h"
 
 /* The insn information.  */
 
@@ -2692,6 +2694,41 @@ get_simple_loop_desc (struct loop *loop)
   find_simple_exit (loop, desc);
   loop->aux = desc;
 
+  if (desc->simple_p && (desc->assumptions || desc->infinite))
+    {
+      const char *wording; 
+
+      /* Assume that no overflow happens and that the loop is finite.  
+	 We already warned at the tree level if we ran optimizations there.  */
+      if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
+	{
+	  if (desc->infinite)
+	    {
+	      wording = 
+		flag_unsafe_loop_optimizations
+		? N_("assuming that the loop is not infinite")
+		: N_("cannot optimize possibly infinite loops");
+	      warning (OPT_Wunsafe_loop_optimizations, "%s",
+		       gettext (wording));
+	    }
+	  if (desc->assumptions)
+	    {
+	      wording = 
+		flag_unsafe_loop_optimizations
+		? N_("assuming that the loop counter does not overflow")
+		: N_("cannot optimize loop, the loop counter may overflow");
+	      warning (OPT_Wunsafe_loop_optimizations, "%s",
+		       gettext (wording));
+	    }
+	}
+
+      if (flag_unsafe_loop_optimizations)
+	{
+	  desc->assumptions = NULL_RTX;
+	  desc->infinite = NULL_RTX;
+	}
+    }
+
   return desc;
 }
 
diff --git a/gcc/predict.c b/gcc/predict.c
index a448c04..9fc8f45 100644
--- a/gcc/predict.c
+++ b/gcc/predict.c
@@ -643,7 +643,7 @@ predict_loops (struct loops *loops_info, bool rtlsimpleloops)
 	    {
 	      tree niter = NULL;
 
-	      if (number_of_iterations_exit (loop, exits[j], &niter_desc))
+	      if (number_of_iterations_exit (loop, exits[j], &niter_desc, false))
 		niter = niter_desc.niter;
 	      if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
 	        niter = loop_niter_by_eval (loop, exits[j]);
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 99b9c79..7e4f35b 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2005-07-21  Paolo Bonzini  <bonzini@gnu.org>
+
+        * gcc.dg/tree-ssa/pr19210-1.c: New.
+        * gcc.dg/tree-ssa/pr19210-2.c: New.
+
 2005-07-21  Richard Sandiford  <richard@codesourcery.com>
 
 	PR rtl-optimization/22167
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr19210-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr19210-1.c
new file mode 100644
index 0000000..4d6100a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr19210-1.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -Wunsafe-loop-optimizations" } */
+extern void g(void);
+
+void
+f (unsigned n)
+{
+  unsigned k;
+  for(k = 0;k <= n;k++) /* { dg-warning "cannot optimize.*infinite loops" } */
+    g();
+
+  for(k = 0;k <= n;k += 4) /* { dg-warning "cannot optimize.*overflow" } */
+    g();
+
+  for(k = 5;k <= n;k += 5) /* { dg-warning "cannot optimize.*overflow" } */
+    g();
+
+  for(k = 15;k >= n;k--) /* { dg-warning "cannot optimize.*infinite" } */
+    g();
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr19210-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr19210-2.c
new file mode 100644
index 0000000..498c658
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr19210-2.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -funsafe-loop-optimizations -Wunsafe-loop-optimizations" } */
+extern void g(void);
+
+void
+f (unsigned n)
+{
+  unsigned k;
+  for(k = 0;k <= n;k++) /* { dg-warning "assuming.*not infinite" } */
+    g();
+
+  for(k = 5;k <= n;k += 4) /* { dg-warning "assuming.*not overflow" } */
+    g();
+
+  for(k = 5;k <= n;k += 5) /* { dg-warning "assuming.*not overflow" } */
+    g();
+
+  for(k = 15;k >= n;k--) /* { dg-warning "assuming.*not infinite" } */
+    g();
+
+}
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index 16bcb80..d41a79c 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -722,7 +722,7 @@ void remove_empty_loops (struct loops *);
 void tree_ssa_iv_optimize (struct loops *);
 
 bool number_of_iterations_exit (struct loop *, edge,
-				struct tree_niter_desc *niter);
+				struct tree_niter_desc *niter, bool);
 tree find_loop_niter (struct loop *, edge *);
 tree loop_niter_by_eval (struct loop *, edge);
 tree find_loop_niter_by_eval (struct loop *, edge *);
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index 2470cc1..f12ec09 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -2235,7 +2235,7 @@ number_of_iterations_in_loop (struct loop *loop)
   if (!exit)
     goto end;
 
-  if (!number_of_iterations_exit (loop, exit, &niter_desc))
+  if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
     goto end;
 
   type = TREE_TYPE (niter_desc.niter);
diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c
index 4d02baa..e8a94d6 100644
--- a/gcc/tree-ssa-loop-ivcanon.c
+++ b/gcc/tree-ssa-loop-ivcanon.c
@@ -393,7 +393,7 @@ empty_loop_p (struct loop *loop)
     return false;
 
   /* The loop must be finite.  */
-  if (!number_of_iterations_exit (loop, exit, &niter))
+  if (!number_of_iterations_exit (loop, exit, &niter, false))
     return false;
 
   /* Values of all loop exit phi nodes must be invariants.  */
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index 84c68ab..fda17f9 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -712,7 +712,8 @@ niter_for_exit (struct ivopts_data *data, edge exit)
       nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
       nfe_desc->exit = exit;
       nfe_desc->valid_p = number_of_iterations_exit (data->current_loop,
-						     exit, &nfe_desc->niter);
+						     exit, &nfe_desc->niter,
+						     true);
       *slot = nfe_desc;
     }
   else
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index c99aa38..891dc0c 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -29,6 +29,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "basic-block.h"
 #include "output.h"
 #include "diagnostic.h"
+#include "intl.h"
 #include "tree-flow.h"
 #include "tree-dump.h"
 #include "cfgloop.h"
@@ -39,6 +40,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "tree-data-ref.h"
 #include "params.h"
 #include "flags.h"
+#include "toplev.h"
 #include "tree-inline.h"
 
 #define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
@@ -906,11 +908,14 @@ simplify_using_outer_evolutions (struct loop *loop, tree expr)
    EXIT (an exit edge of the LOOP) in NITER.  Returns true if some
    useful information could be derived (and fields of NITER has
    meaning described in comments at struct tree_niter_desc
-   declaration), false otherwise.  */
+   declaration), false otherwise.  If WARN is true and
+   -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
+   potentially unsafe assumptions.  */
 
 bool
 number_of_iterations_exit (struct loop *loop, edge exit,
-			   struct tree_niter_desc *niter)
+			   struct tree_niter_desc *niter,
+			   bool warn)
 {
   tree stmt, cond, type;
   tree op0, base0, step0;
@@ -990,7 +995,45 @@ number_of_iterations_exit (struct loop *loop, edge exit,
 	  = simplify_using_initial_conditions (loop,
 					       niter->may_be_zero,
 					       &niter->additional_info);
-  return integer_onep (niter->assumptions);
+
+  if (integer_onep (niter->assumptions))
+    return true;
+
+  /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
+     But if we can prove that there is overflow or some other source of weird
+     behavior, ignore the loop even with -funsafe-loop-optimizations.  */
+  if (integer_zerop (niter->assumptions))
+    return false;
+
+  if (flag_unsafe_loop_optimizations)
+    niter->assumptions = boolean_true_node;
+
+  if (warn)
+    {
+      const char *wording;
+      location_t loc = EXPR_LOCATION (stmt);
+  
+      /* We can provide a more specific warning if one of the operator is
+	 constant and the other advances by +1 or -1.  */
+      if (step1 ? !step0 && (integer_onep (step1) || integer_all_onesp (step1))
+	  	: step0 && (integer_onep (step0) || integer_all_onesp (step0)))
+        wording =
+          flag_unsafe_loop_optimizations
+          ? N_("assuming that the loop is not infinite")
+          : N_("cannot optimize possibly infinite loops");
+      else
+	wording = 
+	  flag_unsafe_loop_optimizations
+	  ? N_("assuming that the loop counter does not overflow")
+	  : N_("cannot optimize loop, the loop counter may overflow");
+
+      if (LOCATION_LINE (loc) > 0)
+	warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
+      else
+	warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
+    }
+
+  return flag_unsafe_loop_optimizations;
 }
 
 /* Try to determine the number of iterations of LOOP.  If we succeed,
@@ -1014,7 +1057,7 @@ find_loop_niter (struct loop *loop, edge *exit)
       if (!just_once_each_iteration_p (loop, ex->src))
 	continue;
 
-      if (!number_of_iterations_exit (loop, ex, &desc))
+      if (!number_of_iterations_exit (loop, ex, &desc, false))
 	continue;
 
       if (nonzero_p (desc.may_be_zero))
@@ -1360,7 +1403,7 @@ estimate_numbers_of_iterations_loop (struct loop *loop)
   exits = get_loop_exit_edges (loop, &n_exits);
   for (i = 0; i < n_exits; i++)
     {
-      if (!number_of_iterations_exit (loop, exits[i], &niter_desc))
+      if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false))
 	continue;
 
       niter = niter_desc.niter;