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]

[PATCH] Use number of iteration analysis from VRP


This makes VRP use number of iteration analysis to derive upper bounds
for loop induction variables.  Currently we only use SCEV to determine
the initial value and drop the upper bound to INF when iterating the
PHI node during propagation.

A first variant uncovered may out-of-bound array accesses (you saw
my patches to the testsuite), one somewhere in Boehm-GC.  Those
were all turned into infinite loops by optimizing away the exit
test ... I figured that's not a good idea and thus added a flag
to number of iteration analysis to disregard deriving bounds from
out-of-bound accesses and other undefined behavior.

The following patch still miscompiles CXB3014 due to PR45427, so
the patch is a good test for our number of iteration analysis ...

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Comments welcome - I have to wait until PR45427 is fixed anyways.

Thanks,
Richard.

2010-08-27  Richard Guenther  <rguenther@suse.de>

	* tree-vrp.c (adjust_range_with_scev): Use number of iteration
	estimate.
	(vrp_visit_phi_node): Delay using SCEV till we balloon the
	range.
	(execute_vrp): Compute number of iteration estimates.
	* cfgloop.h (estimate_numbers_of_iterations_loop): Adjust prototype.
	* tree-flow.h (estimate_numbers_of_iterations): Likewise.
	* tree-data-ref.c (estimated_loop_iterations): Adjust.
	* tree-ssa-loop-niter.c (estimate_numbers_of_iterations_loop):
	Infer loop bounds from undefined behavior based on a new
	parameter.
	(estimate_numbers_of_iterations): Likewise.
	(scev_probably_wraps_p): Adjust.
	* tree-ssa-loop.c (tree_ssa_loop_bounds): Likewise.

	* gcc.dg/vect/vect-outer-fir.c: Adjust.
	* gcc.dg/tree-ssa/vrp54.c: New testcase.

Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c.orig	2010-08-27 11:08:30.000000000 +0200
--- gcc/tree-vrp.c	2010-08-27 13:12:14.000000000 +0200
*************** adjust_range_with_scev (value_range_t *v
*** 3382,3387 ****
--- 3382,3419 ----
    else
      tmax = TYPE_MAX_VALUE (type);
  
+   /* Try to use estimated number of iterations for the loop to constrain the
+      final value in the evolution.
+      We are interested in the number of executions of the latch, while
+      nb_iterations_upper_bound includes the last execution of the exit test.  */
+   if (TREE_CODE (step) == INTEGER_CST
+       && loop->any_upper_bound
+       && !double_int_zero_p (loop->nb_iterations_upper_bound)
+       && is_gimple_val (init)
+       && (TREE_CODE (init) != SSA_NAME
+ 	  || get_value_range (init)->type == VR_RANGE))
+     {
+       value_range_t maxvr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+       double_int dtmp;
+       dtmp = double_int_mul (tree_to_double_int (step),
+ 			     double_int_sub (loop->nb_iterations_upper_bound,
+ 					     double_int_one));
+       tem = double_int_to_tree (TREE_TYPE (init), dtmp);
+       /* If the multiplication overflowed we can't do a meaningful
+ 	 adjustment.  */
+       if (double_int_equal_p (dtmp, tree_to_double_int (tem)))
+ 	{
+ 	  extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
+ 					  TREE_TYPE (init), init, tem);
+ 	  /* Likewise if the addition did.  */
+ 	  if (maxvr.type == VR_RANGE)
+ 	    {
+ 	      tmin = maxvr.min;
+ 	      tmax = maxvr.max;
+ 	    }
+ 	}
+     }
+ 
    if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
      {
        min = tmin;
*************** adjust_range_with_scev (value_range_t *v
*** 3414,3453 ****
  	  /* INIT is the maximum value.  If INIT is lower than VR->MAX
  	     but no smaller than VR->MIN, set VR->MAX to INIT.  */
  	  if (compare_values (init, max) == -1)
! 	    {
! 	      max = init;
! 
! 	      /* If we just created an invalid range with the minimum
! 		 greater than the maximum, we fail conservatively.
! 		 This should happen only in unreachable
! 		 parts of code, or for invalid programs.  */
! 	      if (compare_values (min, max) == 1)
! 		return;
! 	    }
  
  	  /* According to the loop information, the variable does not
  	     overflow.  If we think it does, probably because of an
  	     overflow due to arithmetic on a different INF value,
  	     reset now.  */
! 	  if (is_negative_overflow_infinity (min))
  	    min = tmin;
  	}
        else
  	{
  	  /* If INIT is bigger than VR->MIN, set VR->MIN to INIT.  */
  	  if (compare_values (init, min) == 1)
! 	    {
! 	      min = init;
  
! 	      /* Again, avoid creating invalid range by failing.  */
! 	      if (compare_values (min, max) == 1)
! 		return;
! 	    }
! 
! 	  if (is_positive_overflow_infinity (max))
  	    max = tmax;
  	}
  
        set_value_range (vr, VR_RANGE, min, max, vr->equiv);
      }
  }
--- 3446,3480 ----
  	  /* INIT is the maximum value.  If INIT is lower than VR->MAX
  	     but no smaller than VR->MIN, set VR->MAX to INIT.  */
  	  if (compare_values (init, max) == -1)
! 	    max = init;
  
  	  /* According to the loop information, the variable does not
  	     overflow.  If we think it does, probably because of an
  	     overflow due to arithmetic on a different INF value,
  	     reset now.  */
! 	  if (is_negative_overflow_infinity (min)
! 	      || compare_values (min, tmin) == -1)
  	    min = tmin;
+ 
  	}
        else
  	{
  	  /* If INIT is bigger than VR->MIN, set VR->MIN to INIT.  */
  	  if (compare_values (init, min) == 1)
! 	    min = init;
  
! 	  if (is_positive_overflow_infinity (max)
! 	      || compare_values (tmax, max) == -1)
  	    max = tmax;
  	}
  
+       /* If we just created an invalid range with the minimum
+ 	 greater than the maximum, we fail conservatively.
+ 	 This should happen only in unreachable
+ 	 parts of code, or for invalid programs.  */
+       if (compare_values (min, max) == 1)
+ 	return;
+ 
        set_value_range (vr, VR_RANGE, min, max, vr->equiv);
      }
  }
*************** vrp_visit_phi_node (gimple phi)
*** 6509,6516 ****
    int edges, old_edges;
    struct loop *l;
  
-   copy_value_range (&vr_result, lhs_vr);
- 
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
        fprintf (dump_file, "\nVisiting PHI node: ");
--- 6536,6541 ----
*************** vrp_visit_phi_node (gimple phi)
*** 6571,6583 ****
  	}
      }
  
-   /* If this is a loop PHI node SCEV may known more about its
-      value-range.  */
-   if (current_loops
-       && (l = loop_containing_stmt (phi))
-       && l->header == gimple_bb (phi))
-     adjust_range_with_scev (&vr_result, l, phi, lhs);
- 
    if (vr_result.type == VR_VARYING)
      goto varying;
  
--- 6596,6601 ----
*************** vrp_visit_phi_node (gimple phi)
*** 6589,6649 ****
       previous one.  We don't do this if we have seen a new executable
       edge; this helps us avoid an overflow infinity for conditionals
       which are not in a loop.  */
!   if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE
!       && edges <= old_edges)
      {
!       if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
! 	{
! 	  int cmp_min = compare_values (lhs_vr->min, vr_result.min);
! 	  int cmp_max = compare_values (lhs_vr->max, vr_result.max);
  
! 	  /* If the new minimum is smaller or larger than the previous
! 	     one, go all the way to -INF.  In the first case, to avoid
! 	     iterating millions of times to reach -INF, and in the
! 	     other case to avoid infinite bouncing between different
! 	     minimums.  */
! 	  if (cmp_min > 0 || cmp_min < 0)
! 	    {
! 	      /* If we will end up with a (-INF, +INF) range, set it to
! 		 VARYING.  Same if the previous max value was invalid for
! 		 the type and we'd end up with vr_result.min > vr_result.max.  */
! 	      if (vrp_val_is_max (vr_result.max)
! 		  || compare_values (TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)),
! 				     vr_result.max) > 0)
! 		goto varying;
! 
! 	      if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))
! 		  || !vrp_var_may_overflow (lhs, phi))
! 		vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
! 	      else if (supports_overflow_infinity (TREE_TYPE (vr_result.min)))
! 		vr_result.min =
! 		  negative_overflow_infinity (TREE_TYPE (vr_result.min));
! 	      else
! 		goto varying;
! 	    }
! 
! 	  /* Similarly, if the new maximum is smaller or larger than
! 	     the previous one, go all the way to +INF.  */
! 	  if (cmp_max < 0 || cmp_max > 0)
! 	    {
! 	      /* If we will end up with a (-INF, +INF) range, set it to
! 		 VARYING.  Same if the previous min value was invalid for
! 		 the type and we'd end up with vr_result.max < vr_result.min.  */
! 	      if (vrp_val_is_min (vr_result.min)
! 		  || compare_values (TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)),
! 				     vr_result.min) < 0)
! 		goto varying;
! 
! 	      if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))
! 		  || !vrp_var_may_overflow (lhs, phi))
! 		vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
! 	      else if (supports_overflow_infinity (TREE_TYPE (vr_result.max)))
! 		vr_result.max =
! 		  positive_overflow_infinity (TREE_TYPE (vr_result.max));
! 	      else
! 		goto varying;
! 	    }
! 	}
      }
  
    /* If the new range is different than the previous value, keep
--- 6607,6669 ----
       previous one.  We don't do this if we have seen a new executable
       edge; this helps us avoid an overflow infinity for conditionals
       which are not in a loop.  */
!   if (edges > 0
!       && edges == old_edges)
      {
!       int cmp_min = compare_values (lhs_vr->min, vr_result.min);
!       int cmp_max = compare_values (lhs_vr->max, vr_result.max);
  
!       /* For non VR_RANGE or for pointers fall back to varying if
! 	 the range changed.  */
!       if ((lhs_vr->type != VR_RANGE || vr_result.type != VR_RANGE
! 	   || POINTER_TYPE_P (TREE_TYPE (lhs)))
! 	  && (cmp_min != 0 || cmp_max != 0))
! 	goto varying;
! 
!       /* If the new minimum is smaller or larger than the previous
! 	 one, go all the way to -INF.  In the first case, to avoid
! 	 iterating millions of times to reach -INF, and in the
! 	 other case to avoid infinite bouncing between different
! 	 minimums.  */
!       if (cmp_min > 0 || cmp_min < 0)
! 	{
! 	  if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))
! 	      || !vrp_var_may_overflow (lhs, phi))
! 	    vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
! 	  else if (supports_overflow_infinity (TREE_TYPE (vr_result.min)))
! 	    vr_result.min =
! 		negative_overflow_infinity (TREE_TYPE (vr_result.min));
! 	}
! 
!       /* Similarly, if the new maximum is smaller or larger than
! 	 the previous one, go all the way to +INF.  */
!       if (cmp_max < 0 || cmp_max > 0)
! 	{
! 	  if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))
! 	      || !vrp_var_may_overflow (lhs, phi))
! 	    vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
! 	  else if (supports_overflow_infinity (TREE_TYPE (vr_result.max)))
! 	    vr_result.max =
! 		positive_overflow_infinity (TREE_TYPE (vr_result.max));
! 	}
! 
!       /* If we dropped either bound to +-INF then if this is a loop
! 	 PHI node SCEV may known more about its value-range.  */
!       if ((cmp_min > 0 || cmp_min < 0
! 	   || cmp_max < 0 || cmp_max > 0)
! 	  && current_loops
! 	  && (l = loop_containing_stmt (phi))
! 	  && l->header == gimple_bb (phi))
! 	adjust_range_with_scev (&vr_result, l, phi, lhs);
! 
!       /* If we will end up with a (-INF, +INF) range, set it to
! 	 VARYING.  Same if the previous max value was invalid for
! 	 the type and we end up with vr_result.min > vr_result.max.  */
!       if ((vrp_val_is_max (vr_result.max)
! 	   && vrp_val_is_min (vr_result.min))
! 	  || compare_values (vr_result.min,
! 			     vr_result.max) > 0)
! 	goto varying;
      }
  
    /* If the new range is different than the previous value, keep
*************** execute_vrp (void)
*** 7650,7655 ****
--- 7670,7681 ----
    rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
    scev_initialize ();
  
+   /* Estimate number of iterations - but do not use undefined behavior
+      for this.  We can't do this lazily as other functions may compute
+      this using undefined behavior.  */
+   free_numbers_of_iterations_estimates ();
+   estimate_numbers_of_iterations (false);
+ 
    insert_range_assertions ();
  
    to_remove_edges = VEC_alloc (edge, heap, 10);
Index: gcc/testsuite/gcc.dg/vect/vect-outer-fir.c
===================================================================
*** gcc/testsuite/gcc.dg/vect/vect-outer-fir.c.orig	2010-08-27 11:08:30.000000000 +0200
--- gcc/testsuite/gcc.dg/vect/vect-outer-fir.c	2010-08-27 11:09:14.000000000 +0200
*************** float out[N];
*** 11,20 ****
  float fir_out[N];
  
  /* Should be vectorized. Fixed misaligment in the inner-loop.  */
- /* Currently not vectorized because we get too many BBs in the inner-loop,
-    because the compiler doesn't realize that the inner-loop executes at
-    least once (cause k<4), and so there's no need to create a guard code
-    to skip the inner-loop in case it doesn't execute.  */
  __attribute__ ((noinline))
  void foo (){
   int i,j,k;
--- 11,16 ----
*************** int main (void)
*** 74,79 ****
    return 0;
  }
  
! /* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 2 "vect" { xfail *-*-* } } } */
! /* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 1 "vect" { xfail vect_no_align } } } */
  /* { dg-final { cleanup-tree-dump "vect" } } */
--- 70,74 ----
    return 0;
  }
  
! /* { dg-final { scan-tree-dump-times "OUTER LOOP VECTORIZED" 2 "vect" { xfail vect_no_align } } } */
  /* { dg-final { cleanup-tree-dump "vect" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp54.c
===================================================================
*** /dev/null	1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp54.c	2010-08-27 11:45:43.000000000 +0200
***************
*** 0 ****
--- 1,34 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+ 
+ extern void link_error (void);
+ void foo (void)
+ {
+   int j = 256;
+   do
+     {
+       if (j < 0 || j > 256)
+ 	link_error ();
+       j--;
+     }
+   while (j >= 0);
+   if (j != -1)
+     link_error ();
+ }
+ extern void link_error (void);
+ void bar (void)
+ {
+   int j = 0;
+   do
+     {
+       if (j < 0 || j > 256)
+ 	link_error ();
+       j++;
+     }
+   while (j <= 256);
+   if (j != 257)
+     link_error ();
+ }
+ 
+ /* { dg-final { scan-tree-dump-not "link_error" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: gcc/cfgloop.h
===================================================================
*** gcc/cfgloop.h.orig	2010-08-12 12:31:31.000000000 +0200
--- gcc/cfgloop.h	2010-08-27 12:53:58.000000000 +0200
*************** gcov_type expected_loop_iterations_unbou
*** 276,282 ****
  extern unsigned expected_loop_iterations (const struct loop *);
  extern rtx doloop_condition_get (rtx);
  
! void estimate_numbers_of_iterations_loop (struct loop *);
  HOST_WIDE_INT estimated_loop_iterations_int (struct loop *, bool);
  bool estimated_loop_iterations (struct loop *, bool, double_int *);
  
--- 276,282 ----
  extern unsigned expected_loop_iterations (const struct loop *);
  extern rtx doloop_condition_get (rtx);
  
! void estimate_numbers_of_iterations_loop (struct loop *, bool);
  HOST_WIDE_INT estimated_loop_iterations_int (struct loop *, bool);
  bool estimated_loop_iterations (struct loop *, bool, double_int *);
  
Index: gcc/tree-data-ref.c
===================================================================
*** gcc/tree-data-ref.c.orig	2010-08-24 10:32:38.000000000 +0200
--- gcc/tree-data-ref.c	2010-08-27 12:54:13.000000000 +0200
*************** bool
*** 1716,1722 ****
  estimated_loop_iterations (struct loop *loop, bool conservative,
  			   double_int *nit)
  {
!   estimate_numbers_of_iterations_loop (loop);
    if (conservative)
      {
        if (!loop->any_upper_bound)
--- 1716,1722 ----
  estimated_loop_iterations (struct loop *loop, bool conservative,
  			   double_int *nit)
  {
!   estimate_numbers_of_iterations_loop (loop, true);
    if (conservative)
      {
        if (!loop->any_upper_bound)
Index: gcc/tree-flow.h
===================================================================
*** gcc/tree-flow.h.orig	2010-08-24 12:02:23.000000000 +0200
--- gcc/tree-flow.h	2010-08-27 13:06:31.000000000 +0200
*************** bool number_of_iterations_exit (struct l
*** 684,690 ****
  tree find_loop_niter (struct loop *, edge *);
  tree loop_niter_by_eval (struct loop *, edge);
  tree find_loop_niter_by_eval (struct loop *, edge *);
! void estimate_numbers_of_iterations (void);
  bool array_at_struct_end_p (tree);
  bool scev_probably_wraps_p (tree, tree, gimple, struct loop *, bool);
  bool convert_affine_scev (struct loop *, tree, tree *, tree *, gimple, bool);
--- 684,690 ----
  tree find_loop_niter (struct loop *, edge *);
  tree loop_niter_by_eval (struct loop *, edge);
  tree find_loop_niter_by_eval (struct loop *, edge *);
! void estimate_numbers_of_iterations (bool);
  bool array_at_struct_end_p (tree);
  bool scev_probably_wraps_p (tree, tree, gimple, struct loop *, bool);
  bool convert_affine_scev (struct loop *, tree, tree *, tree *, gimple, bool);
Index: gcc/tree-ssa-loop-niter.c
===================================================================
*** gcc/tree-ssa-loop-niter.c.orig	2010-08-24 12:02:23.000000000 +0200
--- gcc/tree-ssa-loop-niter.c	2010-08-27 13:05:45.000000000 +0200
*************** gcov_type_to_double_int (gcov_type val)
*** 2900,2909 ****
    return ret;
  }
  
! /* Records estimates on numbers of iterations of LOOP.  */
  
  void
! estimate_numbers_of_iterations_loop (struct loop *loop)
  {
    VEC (edge, heap) *exits;
    tree niter, type;
--- 2900,2910 ----
    return ret;
  }
  
! /* Records estimates on numbers of iterations of LOOP.  If USE_UNDEFINED_P
!    is true also use estimates derived from undefined behavior.  */
  
  void
! estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p)
  {
    VEC (edge, heap) *exits;
    tree niter, type;
*************** estimate_numbers_of_iterations_loop (str
*** 2937,2943 ****
      }
    VEC_free (edge, heap, exits);
  
!   infer_loop_bounds_from_undefined (loop);
  
    /* If we have a measured profile, use it to estimate the number of
       iterations.  */
--- 2938,2945 ----
      }
    VEC_free (edge, heap, exits);
  
!   if (use_undefined_p)
!     infer_loop_bounds_from_undefined (loop);
  
    /* If we have a measured profile, use it to estimate the number of
       iterations.  */
*************** estimate_numbers_of_iterations_loop (str
*** 2960,2966 ****
  /* Records estimates on numbers of iterations of loops.  */
  
  void
! estimate_numbers_of_iterations (void)
  {
    loop_iterator li;
    struct loop *loop;
--- 2962,2968 ----
  /* Records estimates on numbers of iterations of loops.  */
  
  void
! estimate_numbers_of_iterations (bool use_undefined_p)
  {
    loop_iterator li;
    struct loop *loop;
*************** estimate_numbers_of_iterations (void)
*** 2971,2977 ****
  
    FOR_EACH_LOOP (li, loop, 0)
      {
!       estimate_numbers_of_iterations_loop (loop);
      }
  
    fold_undefer_and_ignore_overflow_warnings ();
--- 2973,2979 ----
  
    FOR_EACH_LOOP (li, loop, 0)
      {
!       estimate_numbers_of_iterations_loop (loop, use_undefined_p);
      }
  
    fold_undefer_and_ignore_overflow_warnings ();
*************** scev_probably_wraps_p (tree base, tree s
*** 3167,3173 ****
  
    valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
  
!   estimate_numbers_of_iterations_loop (loop);
    for (bound = loop->bounds; bound; bound = bound->next)
      {
        if (n_of_executions_at_most (at_stmt, bound, valid_niter))
--- 3169,3175 ----
  
    valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
  
!   estimate_numbers_of_iterations_loop (loop, true);
    for (bound = loop->bounds; bound; bound = bound->next)
      {
        if (n_of_executions_at_most (at_stmt, bound, valid_niter))
Index: gcc/tree-ssa-loop.c
===================================================================
*** gcc/tree-ssa-loop.c.orig	2010-08-13 16:05:29.000000000 +0200
--- gcc/tree-ssa-loop.c	2010-08-27 13:08:37.000000000 +0200
*************** tree_ssa_loop_bounds (void)
*** 458,464 ****
    if (number_of_loops () <= 1)
      return 0;
  
!   estimate_numbers_of_iterations ();
    scev_reset ();
    return 0;
  }
--- 458,464 ----
    if (number_of_loops () <= 1)
      return 0;
  
!   estimate_numbers_of_iterations (true);
    scev_reset ();
    return 0;
  }


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