Re: -funsafe-loop-optimizations

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> > 	While we discuss whether this should be the default or enabled at
> > any optimization level, can we agree that users should be able to assert
> > with a commandline option that they want less strict induction variable
> > semantics?
> 
> And/or a -W option that warns for these sorts of loops so that
> (a) we can see how often this happens, really, (b) so that users
> can fix the presumed mistake.

here is a prototype for the patch with warning, in the case someone
would like to play with it.  It shows 132 distinct warnings for build of
gcc (c only) -- in fact a bit less due to duplicates between tree and
rtl level warnings.

Note that especially tree level warnings tend to be repeated many times,
since # of iterations analysis is often called several times for one
loop (mostly unnecessarily,
http://gcc.gnu.org/ml/gcc-patches/2004-10/msg00136.html is a fix for
this inefficiency).

Zdenek

Index: common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.59
diff -c -3 -p -r1.59 common.opt
*** common.opt	28 Oct 2004 03:42:22 -0000	1.59
--- common.opt	1 Jan 2005 22:49:37 -0000
*************** Wlarger-than-
*** 89,94 ****
--- 89,98 ----
  Common RejectNegative Joined UInteger
  -Wlarger-than-<number>	Warn if an object is larger than <number> bytes
  
+ Wloop-assumptions
+ Common Var(warn_loop_assumptions)
+ 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))
*************** funroll-all-loops
*** 896,901 ****
--- 900,912 ----
  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"
Index: loop-iv.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop-iv.c,v
retrieving revision 2.26
diff -c -3 -p -r2.26 loop-iv.c
*** loop-iv.c	28 Dec 2004 10:33:39 -0000	2.26
--- loop-iv.c	1 Jan 2005 22:49:37 -0000
*************** get_simple_loop_desc (struct loop *loop)
*** 2690,2695 ****
--- 2690,2735 ----
    find_simple_exit (loop, desc);
    loop->aux = desc;
  
+   if (desc->simple_p)
+     {
+       if (warn_loop_assumptions)
+ 	{
+ 	  bool warned = false;
+ 	  const char *wording = (flag_unsafe_loop_optimizations
+ 				 ? "ignored"
+ 				 : "may prevent loop optimizations");
+ 
+ 	  if (desc->assumptions)
+ 	    {
+ 	      warning ("Overflow assumptions %s.", wording);
+ 	      debug_rtx (desc->assumptions);
+ 	      warned = true;
+ 	    }
+ 
+ 	  if (desc->infinite)
+ 	    {
+ 	      warning ("Infinite loop assumptions %s.", wording);
+ 	      debug_rtx (desc->infinite);
+ 	      warned = true;
+ 	    }
+ 
+ 	  if (warned && debug_info_level > DINFO_LEVEL_TERSE)
+ 	    {
+ 	      rtx exit = BB_END (desc->out_edge->src);
+ 
+ 	      if (INSN_LOCATOR (exit) > 0)
+ 		warning ("At %s:%d", insn_file (exit), insn_line (exit));
+ 	    }
+ 	}
+ 
+       if (flag_unsafe_loop_optimizations)
+ 	{
+ 	  /* Assume that no overflow happens and that the loop is finite.  */
+ 	  desc->assumptions = NULL_RTX;
+ 	  desc->infinite = NULL_RTX;
+ 	}
+     }
+ 
    return desc;
  }
  
Index: predict.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.c,v
retrieving revision 1.135
diff -c -3 -p -r1.135 predict.c
*** predict.c	22 Nov 2004 17:14:00 -0000	1.135
--- predict.c	1 Jan 2005 22:49:37 -0000
*************** predict_loops (struct loops *loops_info,
*** 623,629 ****
  	    {
  	      tree niter = NULL;
  
! 	      if (number_of_iterations_exit (loop, exits[j], &niter_desc))
  		niter = niter_desc.niter;
  	      if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
  	        niter = loop_niter_by_eval (loop, exits[j]);
--- 623,629 ----
  	    {
  	      tree niter = NULL;
  
! 	      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]);
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.75
diff -c -3 -p -r2.75 tree-flow.h
*** tree-flow.h	10 Dec 2004 21:54:41 -0000	2.75
--- tree-flow.h	1 Jan 2005 22:49:37 -0000
*************** void tree_ssa_iv_optimize (struct loops 
*** 661,667 ****
  void number_of_iterations_cond (tree, tree, tree, enum tree_code, tree, tree,
  				struct tree_niter_desc *);
  bool number_of_iterations_exit (struct loop *, edge,
! 				struct tree_niter_desc *niter);
  tree loop_niter_by_eval (struct loop *, edge);
  tree find_loop_niter_by_eval (struct loop *, edge *);
  void estimate_numbers_of_iterations (struct loops *);
--- 661,667 ----
  void number_of_iterations_cond (tree, tree, tree, enum tree_code, tree, tree,
  				struct tree_niter_desc *);
  bool number_of_iterations_exit (struct loop *, edge,
! 				struct tree_niter_desc *niter, bool);
  tree loop_niter_by_eval (struct loop *, edge);
  tree find_loop_niter_by_eval (struct loop *, edge *);
  void estimate_numbers_of_iterations (struct loops *);
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.14
diff -c -3 -p -r2.14 tree-scalar-evolution.c
*** tree-scalar-evolution.c	31 Dec 2004 18:03:28 -0000	2.14
--- tree-scalar-evolution.c	1 Jan 2005 22:49:37 -0000
*************** number_of_iterations_in_loop (struct loo
*** 2150,2156 ****
    if (!exit)
      goto end;
  
!   if (!number_of_iterations_exit (loop, exit, &niter_desc))
      goto end;
  
    type = TREE_TYPE (niter_desc.niter);
--- 2150,2156 ----
    if (!exit)
      goto end;
  
!   if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
      goto end;
  
    type = TREE_TYPE (niter_desc.niter);
Index: tree-ssa-dce.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dce.c,v
retrieving revision 2.29
diff -c -3 -p -r2.29 tree-ssa-dce.c
*** tree-ssa-dce.c	13 Dec 2004 16:03:40 -0000	2.29
--- tree-ssa-dce.c	1 Jan 2005 22:49:37 -0000
*************** find_obviously_necessary_stmts (struct e
*** 489,498 ****
        bb->flags &= ~BB_VISITED;
      }
  
!   if (el)
      {
        /* Prevent the loops from being removed.  We must keep the infinite loops,
! 	 and we currently do not have a means to recognize the finite ones.  */
        FOR_EACH_BB (bb)
  	{
  	  edge_iterator ei;
--- 489,501 ----
        bb->flags &= ~BB_VISITED;
      }
  
!   if (el && !flag_unsafe_loop_optimizations)
      {
        /* Prevent the loops from being removed.  We must keep the infinite loops,
! 	 and we currently do not have a means to recognize the finite ones.
! 	 
! 	 With -funsafe-loop-optimizations we assume that the loops are not
! 	 infinite.  */
        FOR_EACH_BB (bb)
  	{
  	  edge_iterator ei;
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.39
diff -c -3 -p -r2.39 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c	25 Dec 2004 22:53:54 -0000	2.39
--- tree-ssa-loop-ivopts.c	1 Jan 2005 22:49:37 -0000
*************** determine_number_of_iterations (struct i
*** 1020,1026 ****
    if (!exit)
      return;
  
!   number_of_iterations_exit (loop, exit, &loop_data (loop)->niter);
  }
  
  /* For each ssa name defined in LOOP determines whether it is an induction
--- 1020,1026 ----
    if (!exit)
      return;
  
!   number_of_iterations_exit (loop, exit, &loop_data (loop)->niter, true);
  }
  
  /* For each ssa name defined in LOOP determines whether it is an induction
*************** may_eliminate_iv (struct loop *loop,
*** 3210,3216 ****
      return false;
  
    niter.niter = NULL_TREE;
!   number_of_iterations_exit (loop, exit, &niter);
    if (!niter.niter
        || !integer_nonzerop (niter.assumptions)
        || !integer_zerop (niter.may_be_zero))
--- 3210,3216 ----
      return false;
  
    niter.niter = NULL_TREE;
!   number_of_iterations_exit (loop, exit, &niter, true);
    if (!niter.niter
        || !integer_nonzerop (niter.assumptions)
        || !integer_zerop (niter.may_be_zero))
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.18
diff -c -3 -p -r2.18 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c	23 Nov 2004 01:27:42 -0000	2.18
--- tree-ssa-loop-niter.c	1 Jan 2005 22:49:37 -0000
*************** simplify_using_initial_conditions (struc
*** 748,758 ****
     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.  */
  
  bool
  number_of_iterations_exit (struct loop *loop, edge exit,
! 			   struct tree_niter_desc *niter)
  {
    tree stmt, cond, type;
    tree op0, base0, step0;
--- 748,760 ----
     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.  If WARN is true,
!    warning is emited for assumptions if -Wloop-assumptions.  */
  
  bool
  number_of_iterations_exit (struct loop *loop, edge exit,
! 			   struct tree_niter_desc *niter,
! 			   bool warn)
  {
    tree stmt, cond, type;
    tree op0, base0, step0;
*************** number_of_iterations_exit (struct loop *
*** 820,826 ****
  	  = simplify_using_initial_conditions (loop,
  					       niter->may_be_zero,
  					       &niter->additional_info);
!   return integer_onep (niter->assumptions);
  }
  
  /*
--- 822,858 ----
  	  = simplify_using_initial_conditions (loop,
  					       niter->may_be_zero,
  					       &niter->additional_info);
! 
!   /* 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 (warn
!       && warn_loop_assumptions
!       && !integer_onep (niter->assumptions))
!     {
!       const char *wording = (flag_unsafe_loop_optimizations
! 			     ? "ignored"
! 			     : "may prevent loop optimizations");
!       location_t loc = EXPR_LOCATION (stmt);
! 
!       if (LOCATION_LINE (loc) > 0)
! 	warning ("Overflow assumptions %s in %H.", wording, &loc);
!       else
! 	warning ("Overflow assumptions %s.", wording);
!       debug_generic_stmt (niter->assumptions);
!     }
! 
!   if (flag_unsafe_loop_optimizations)
!     {
!       /* With -funsafe-loop-optimizations we assume that nothing bad can
! 	 happen.  */
!       niter->assumptions = boolean_true_node;
!       return true;
!     }
!   else
!     return integer_onep (niter->assumptions);
  }
  
  /*
*************** estimate_numbers_of_iterations_loop (str
*** 1115,1121 ****
    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))
  	continue;
  
        niter = niter_desc.niter;
--- 1147,1153 ----
    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, false))
  	continue;
  
        niter = niter_desc.niter;
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.563
diff -c -3 -p -r1.563 invoke.texi
*** doc/invoke.texi	28 Dec 2004 04:24:30 -0000	1.563
--- doc/invoke.texi	1 Jan 2005 22:49:38 -0000
*************** Objective-C and Objective-C++ Dialects}.
*** 223,229 ****
  -Wimplicit  -Wimplicit-function-declaration  -Wimplicit-int @gol
  -Wimport  -Wno-import  -Winit-self  -Winline @gol
  -Wno-invalid-offsetof  -Winvalid-pch @gol
! -Wlarger-than-@var{len}  -Wlong-long @gol
  -Wmain  -Wmissing-braces  -Wmissing-field-initializers @gol
  -Wmissing-format-attribute  -Wmissing-include-dirs @gol
  -Wmissing-noreturn @gol
--- 223,229 ----
  -Wimplicit  -Wimplicit-function-declaration  -Wimplicit-int @gol
  -Wimport  -Wno-import  -Winit-self  -Winline @gol
  -Wno-invalid-offsetof  -Winvalid-pch @gol
! -Wlarger-than-@var{len}  -Wloop-assumptions -Wlong-long @gol
  -Wmain  -Wmissing-braces  -Wmissing-field-initializers @gol
  -Wmissing-format-attribute  -Wmissing-include-dirs @gol
  -Wmissing-noreturn @gol
*************** Objective-C and Objective-C++ Dialects}.
*** 298,304 ****
  -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
  -fno-trapping-math  -fno-zero-initialized-in-bss @gol
  -fomit-frame-pointer  -foptimize-register-move @gol
  -foptimize-sibling-calls  -fprefetch-loop-arrays @gol
--- 298,304 ----
  -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  -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
*************** global variable or whenever a built-in f
*** 2866,2871 ****
--- 2866,2877 ----
  @opindex Wlarger-than
  Warn whenever an object of larger than @var{len} bytes is defined.
  
+ @item -Wloop-assumptions
+ @opindex Wloop-assumptions
+ Warn if the loop cannot be optimized due to assumptions whose correctness
+ cannot be proved in compile time.  With @option{-funsafe-loop-optimizations}
+ warn if such assumption was ignored.
+ 
  @item -Wpointer-arith
  @opindex Wpointer-arith
  Warn about anything that depends on the ``size of'' a function type or
*************** Perform loop optimizations using the new
*** 4464,4469 ****
--- 4470,4483 ----
  (loop unrolling, peeling and unswitching, loop invariant motion) are enabled
  by separate flags.
  
+ @item -funsafe-loop-optimizations
+ @opindex funsafe-loop-optimizations
+ 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.  This enables wider range of loop
+ optimizations even in the case loop optimizer itself is unable to disprove
+ that some of these improbable events happen.
+ 
  @item -fcrossjumping
  @opindex crossjumping
  Perform cross-jumping transformation.  This transformation unifies equivalent code and save code size.  The