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]

Fix PR 22018


We were mishandling multiplication of ranges in
extract_range_from_binary_expr.  In adding proper support for
MULT_EXPR, I realized that instead of figuring out the mix of
signs beforehand, it is actually easier and quicker to do the
4 operations pairing each limit of each range and then figure out
the minimum and maximum value.  This results in fewer calls to
compare_values and we rarely need to actually perform all 4
operations.

Also, when not using wrapping arithmetic, the handling of
overflowed values was wrong.  We need to know in which direction
the operation was moving to determine if we get -INF or +INF.
All that handling is now inside vrp_int_const_binop.

Bootstrapped and tested x86, ia64, ppc64 and x86-64.


Diego.

	PR 22018
	* tree-vrp.c (vrp_int_const_binop): New.
	(extract_range_from_binary_expr): Call it.
	Unify handling division and multiplication.

testsuite/ChangeLog

	PR 22018
	* gcc.dg/tree-ssa/vrp13.c: Add multiplication tests.
	* gcc.dg/tree-ssa/pr22018.c: New test.

Index: tree-vrp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vrp.c,v
retrieving revision 2.27
diff -d -u -p -d -c -p -r2.27 tree-vrp.c
*** tree-vrp.c	14 Jun 2005 21:26:33 -0000	2.27
--- tree-vrp.c	15 Jun 2005 11:00:33 -0000
*************** extract_range_from_ssa_name (value_range
*** 969,974 ****
--- 969,1018 ----
  }
  
  
+ /* Wrapper around int_const_binop.  If the operation overflows and we
+    are not using wrapping arithmetic, then adjust the result to be
+    -INF or +INF depending on CODE, VAL1 and VAL2.  */
+ 
+ static inline tree
+ vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
+ {
+   tree res;
+ 
+   if (flag_wrapv)
+     return int_const_binop (code, val1, val2, 0);
+ 
+   /* If we are not using wrapping arithmetic, operate symbolically
+      on -INF and +INF.  */
+   res = int_const_binop (code, val1, val2, 0);
+ 
+   /* If the operation overflowed but neither VAL1 nor VAL2 are
+      overflown, return -INF or +INF depending on whether VAL1 CODE
+      VAL2 is a growing function or not.  */
+   if (TREE_OVERFLOW (res)
+       && !TREE_OVERFLOW (val1)
+       && !TREE_OVERFLOW (val2))
+     {
+       bool grows = false;
+       int sgn1 = tree_int_cst_sgn (val1);
+       int sgn2 = tree_int_cst_sgn (val2);
+ 
+       /* Notice that we only need to handle the restricted set of
+ 	 operations handled by extract_range_from_binary_expr.  */
+       if (((code == PLUS_EXPR || code == MAX_EXPR) && sgn2 >= 0)
+ 	  || (code == MULT_EXPR && sgn1 == sgn2)
+ 	  || (code == MINUS_EXPR && sgn2 < 0))
+ 	grows = true;
+ 
+       if (grows)
+ 	return TYPE_MAX_VALUE (TREE_TYPE (res));
+       else
+ 	return TYPE_MIN_VALUE (TREE_TYPE (res));
+     }
+ 
+   return res;
+ }
+ 
+ 
  /* Extract range information from a binary expression EXPR based on
     the ranges of each of its operands and the expression code.  */
  
*************** extract_range_from_binary_expr (value_ra
*** 1076,1171 ****
        max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
      }
    else if (code == PLUS_EXPR
- 	   || code == MULT_EXPR
  	   || code == MIN_EXPR
  	   || code == MAX_EXPR)
      {
        /* For operations that make the resulting range directly
  	 proportional to the original ranges, apply the operation to
  	 the same end of each range.  */
!       min = int_const_binop (code, vr0.min, vr1.min, 0);
!       max = int_const_binop (code, vr0.max, vr1.max, 0);
      }
!   else if (code == TRUNC_DIV_EXPR
  	   || code == FLOOR_DIV_EXPR
  	   || code == CEIL_DIV_EXPR
  	   || code == EXACT_DIV_EXPR
  	   || code == ROUND_DIV_EXPR)
      {
!       tree zero;
  
!       /* Divisions are a bit tricky to handle, depending on the mix of
! 	 signs we have in the two range, we will need to divide
! 	 different values to get the minimum and maximum values for
! 	 the new range.  If VR1 includes zero, the result is VARYING.  */
!       if (range_includes_zero_p (&vr1))
  	{
  	  set_value_range_to_varying (vr);
  	  return;
  	}
  
!       /* We have three main variations to handle for VR0: all negative
! 	 values, all positive values and a mix of negative and
! 	 positive.  For each of these, we need to consider if VR1 is
! 	 all negative or all positive.  In total, there are 6
! 	 combinations to handle.  */
!       zero = build_int_cst (TREE_TYPE (expr), 0);
!       if (compare_values (vr0.max, zero) == -1)
! 	{
! 	  /* VR0 is all negative.  */
! 	  if (compare_values (vr1.min, zero) == 1)
! 	    {
! 	      /* If VR1 is all positive, the new range is obtained
! 		 with [VR0.MIN / VR1.MIN, VR0.MAX / VR1.MAX].  */
! 	      min = int_const_binop (code, vr0.min, vr1.min, 0);
! 	      max = int_const_binop (code, vr0.max, vr1.max, 0);
! 	    }
! 	  else
! 	    {
! 	      /* If VR1 is all negative, the new range is obtained
! 		 with [VR0.MAX / VR1.MIN, VR0.MIN / VR1.MAX].  */
! 	      gcc_assert (compare_values (vr1.max, zero) == -1);
! 	      min = int_const_binop (code, vr0.max, vr1.min, 0);
! 	      max = int_const_binop (code, vr0.min, vr1.max, 0);
! 	    }
! 	}
!       else if (range_includes_zero_p (&vr0))
! 	{
! 	  /* VR0 is a mix of negative and positive values.  */
! 	  if (compare_values (vr1.min, zero) == 1)
! 	    {
! 	      /* If VR1 is all positive, the new range is obtained
! 		 with [VR0.MIN / VR1.MIN, VR0.MAX / VR1.MIN].  */
! 	      min = int_const_binop (code, vr0.min, vr1.min, 0);
! 	      max = int_const_binop (code, vr0.max, vr1.min, 0);
! 	    }
! 	  else
! 	    {
! 	      /* If VR1 is all negative, the new range is obtained
! 		 with [VR0.MAX / VR1.MAX, VR0.MIN / VR1.MAX].  */
! 	      gcc_assert (compare_values (vr1.max, zero) == -1);
! 	      min = int_const_binop (code, vr0.max, vr1.max, 0);
! 	      max = int_const_binop (code, vr0.min, vr1.max, 0);
! 	    }
! 	}
!       else
  	{
! 	  /* VR0 is all positive.  */
! 	  gcc_assert (compare_values (vr0.min, zero) == 1);
! 	  if (compare_values (vr1.min, zero) == 1)
! 	    {
! 	      /* If VR1 is all positive, the new range is obtained
! 		 with [VR0.MIN / VR1.MAX, VR0.MAX / VR1.MIN].  */
! 	      min = int_const_binop (code, vr0.min, vr1.max, 0);
! 	      max = int_const_binop (code, vr0.max, vr1.min, 0);
! 	    }
! 	  else
  	    {
! 	      /* If VR1 is all negative, the new range is obtained
! 		 with [VR0.MAX / VR1.MAX, VR0.MIN / VR1.MIN].  */
! 	      gcc_assert (compare_values (vr1.max, zero) == -1);
! 	      min = int_const_binop (code, vr0.max, vr1.max, 0);
! 	      max = int_const_binop (code, vr0.min, vr1.min, 0);
  	    }
  	}
      }
--- 1120,1204 ----
        max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
      }
    else if (code == PLUS_EXPR
  	   || code == MIN_EXPR
  	   || code == MAX_EXPR)
      {
        /* For operations that make the resulting range directly
  	 proportional to the original ranges, apply the operation to
  	 the same end of each range.  */
!       min = vrp_int_const_binop (code, vr0.min, vr1.min);
!       max = vrp_int_const_binop (code, vr0.max, vr1.max);
      }
!   else if (code == MULT_EXPR
! 	   || code == TRUNC_DIV_EXPR
  	   || code == FLOOR_DIV_EXPR
  	   || code == CEIL_DIV_EXPR
  	   || code == EXACT_DIV_EXPR
  	   || code == ROUND_DIV_EXPR)
      {
!       tree val[4];
!       size_t i;
  
!       /* Multiplications and divisions are a bit tricky to handle,
! 	 depending on the mix of signs we have in the two ranges, we
! 	 need to operate on different values to get the minimum and
! 	 maximum values for the new range.  One approach is to figure
! 	 out all the variations of range combinations and do the
! 	 operations.
! 
! 	 However, this involves several calls to compare_values and it
! 	 is pretty convoluted.  It's simpler to do the 4 operations
! 	 (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
! 	 MAX1) and then figure the smallest and largest values to form
! 	 the new range.  */
! 
!       /* Divisions by zero result in a VARYING value.  */
!       if (code != MULT_EXPR && range_includes_zero_p (&vr1))
  	{
  	  set_value_range_to_varying (vr);
  	  return;
  	}
  
!       /* Compute the 4 cross operations.  */
!       val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
! 
!       val[1] = (vr1.max != vr1.min)
! 	       ? vrp_int_const_binop (code, vr0.min, vr1.max)
! 	       : NULL_TREE;
! 
!       val[2] = (vr0.max != vr0.min)
! 	       ? vrp_int_const_binop (code, vr0.max, vr1.min)
! 	       : NULL_TREE;
! 
!       val[3] = (vr0.min != vr1.min && vr0.max != vr1.max)
! 	       ? vrp_int_const_binop (code, vr0.max, vr1.max)
! 	       : NULL_TREE;
! 
!       /* Set MIN to the minimum of VAL[i] and MAX to the maximum
! 	 of VAL[i].  */
!       min = val[0];
!       max = val[0];
!       for (i = 1; i < 4; i++)
  	{
! 	  if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
! 	    break;
! 
! 	  if (val[i])
  	    {
! 	      if (TREE_OVERFLOW (val[i]))
! 		{
! 		  /* If we found an overflowed value, set MIN and MAX
! 		     to it so that we set the resulting range to
! 		     VARYING.  */
! 		  min = max = val[i];
! 		  break;
! 		}
! 
! 	      if (compare_values (val[i], min) == -1)
! 		min = val[i];
! 
! 	      if (compare_values (val[i], max) == 1)
! 		max = val[i];
  	    }
  	}
      }
*************** extract_range_from_binary_expr (value_ra
*** 1173,1214 ****
      {
        /* For MINUS_EXPR, apply the operation to the opposite ends of
  	 each range.  */
!       min = int_const_binop (code, vr0.min, vr1.max, 0);
!       max = int_const_binop (code, vr0.max, vr1.min, 0);
      }
    else
      gcc_unreachable ();
  
!   /* If MAX overflowed, then the result depends on whether we are
!      using wrapping arithmetic or not.  */
!   if (TREE_OVERFLOW (max))
!     {
!       /* If we are using wrapping arithmetic, set the result to
! 	 VARYING.  */
!       if (flag_wrapv)
! 	{
! 	  set_value_range_to_varying (vr);
! 	  return;
! 	}
! 
!       /* Otherwise, set MAX to +INF.  */
!       max = TYPE_MAX_VALUE (TREE_TYPE (expr));
!     }
! 
!   /* If MIN overflowed, then the result depends on whether we are
!      using wrapping arithmetic or not.  */
!   if (TREE_OVERFLOW (min))
      {
!       /* If we are using wrapping arithmetic, set the result to
! 	 VARYING.  */
!       if (flag_wrapv)
! 	{
! 	  set_value_range_to_varying (vr);
! 	  return;
! 	}
! 
!       /* Otherwise, set MIN to -INF.  */
!       min = TYPE_MIN_VALUE (TREE_TYPE (expr));
      }
  
    cmp = compare_values (min, max);
--- 1206,1223 ----
      {
        /* For MINUS_EXPR, apply the operation to the opposite ends of
  	 each range.  */
!       min = vrp_int_const_binop (code, vr0.min, vr1.max);
!       max = vrp_int_const_binop (code, vr0.max, vr1.min);
      }
    else
      gcc_unreachable ();
  
!   /* If either MIN or MAX overflowed, then set the resulting range to
!      VARYING.  */
!   if (TREE_OVERFLOW (min) || TREE_OVERFLOW (max))
      {
!       set_value_range_to_varying (vr);
!       return;
      }
  
    cmp = compare_values (min, max);
Index: testsuite/gcc.dg/tree-ssa/pr22018.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/pr22018.c
diff -N testsuite/gcc.dg/tree-ssa/pr22018.c
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.dg/tree-ssa/pr22018.c	15 Jun 2005 11:00:35 -0000
***************
*** 0 ****
--- 1,32 ----
+ /* { dg-do run }  */
+ /* { dg-options -O2 }  */
+ 
+ void abort (void);
+ void g(int);
+ void f(int l)
+ {
+   unsigned i;
+   for (i = 0; i < l; i++)
+     {
+       int y = i;
+       /* VRP was wrongfully computing z's range to be [0, 0] instead
+ 	 of [-INF, 0].  */
+       int z = y*-32;
+       g(z);
+     }
+ }
+ 
+ void g(int i)
+ {
+   static int x = 0;
+   if (i == 0)
+     x ++;
+   if (x > 1)
+     abort ();
+ }
+ 
+ int main(void)
+ {
+   f(3);
+   return 0;
+ }
Index: testsuite/gcc.dg/tree-ssa/vrp13.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/vrp13.c,v
retrieving revision 1.1
diff -d -u -p -d -c -p -r1.1 vrp13.c
*** testsuite/gcc.dg/tree-ssa/vrp13.c	2 Jun 2005 02:57:15 -0000	1.1
--- testsuite/gcc.dg/tree-ssa/vrp13.c	15 Jun 2005 11:00:35 -0000
***************
*** 3,9 ****
  
  extern void abort (void);
  
! foo (int i, int j)
  {
    int k;
  
--- 3,9 ----
  
  extern void abort (void);
  
! foo_div (int i, int j)
  {
    int k;
  
*************** foo (int i, int j)
*** 112,138 ****
  }
  
  
  main()
  {
!   if (foo (-10, 5) != -2)
      abort ();
  
!   if (foo (-16, 4) != -4)
      abort ();
  
!   if (foo (-15, -5) != 3)
      abort ();
  
!   if (foo (8, 2) != 4)
      abort ();
  
!   if (foo (10, -2) != -5)
      abort ();
  
!   if (foo (20, 5) != 4)
      abort ();
  
!   if (foo (15, -3) != -5)
      abort ();
  
    return 0;
--- 112,257 ----
  }
  
  
+ foo_mult (int i, int j)
+ {
+   int k;
+ 
+   /* [-20, -10] * [2, 10] should give [-200, -20].  */
+   if (i >= -20)
+     if (i <= -10)
+       if (j >= 2)
+ 	if (j <= 10)
+ 	  {
+ 	    k = i * j;
+ 	    if (k < -200)
+ 	      link_error ();
+ 	    if (k > -20)
+ 	      link_error ();
+ 
+ 	    return k;
+ 	  }
+ 
+   /* [-20, -10] * [-10, -2] should give [20, 200].  */
+   if (i >= -20)
+     if (i <= -10)
+       if (j >= -10)
+ 	if (j <= -2)
+ 	  {
+ 	    k = i * j;
+ 	    if (k < 20)
+ 	      link_error ();
+ 	    if (k > 200)
+ 	      link_error ();
+ 
+ 	    return k;
+ 	  }
+ 
+   /* [-20, 10] * [2, 10] should give [-200, 100].  */
+   if (i >= -20)
+     if (i <= 10)
+       if (j >= 2)
+ 	if (j <= 10)
+ 	  {
+ 	    k = i * j;
+ 	    if (k < -200)
+ 	      link_error ();
+ 	    if (k > 100)
+ 	      link_error ();
+ 
+ 	    return k;
+ 	  }
+ 
+   /* [-20, 10] * [-10, -2] should give [-100, 200].  */
+   if (i >= -20)
+     if (i <= 10)
+       if (j >= -10)
+ 	if (j <= -2)
+ 	  {
+ 	    k = i * j;
+ 	    if (k < -100)
+ 	      link_error ();
+ 	    if (k > 200)
+ 	      link_error ();
+ 
+ 	    return k;
+ 	  }
+ 
+   /* [10, 20] * [2, 10] should give [20, 200].  */
+   if (i >= 10)
+     if (i <= 20)
+       if (j >= 2)
+ 	if (j <= 10)
+ 	  {
+ 	    k = i * j;
+ 	    if (k < 20)
+ 	      link_error ();
+ 	    if (k > 200)
+ 	      link_error ();
+ 
+ 	    return k;
+ 	  }
+ 
+   /* [10, 20] * [-10, -2] should give [-200, -20].  */
+   if (i >= 10)
+     if (i <= 20)
+       if (j >= -10)
+ 	if (j <= -2)
+ 	  {
+ 	    k = i * j;
+ 	    if (k < -200)
+ 	      link_error ();
+ 	    if (k > -20)
+ 	      link_error ();
+ 
+ 	    return k;
+ 	  }
+ 
+   abort ();
+ }
+ 
+ 
  main()
  {
!   if (foo_div (-10, 5) != -2)
      abort ();
  
!   if (foo_div (-16, 4) != -4)
      abort ();
  
!   if (foo_div (-15, -5) != 3)
      abort ();
  
!   if (foo_div (8, 2) != 4)
      abort ();
  
!   if (foo_div (10, -2) != -5)
      abort ();
  
!   if (foo_div (20, 5) != 4)
      abort ();
  
!   if (foo_div (15, -3) != -5)
!     abort ();
! 
!   if (foo_mult (-10, 5) != -50)
!     abort ();
! 
!   if (foo_mult (-16, 4) != -64)
!     abort ();
! 
!   if (foo_mult (-15, -5) != 75)
!     abort ();
! 
!   if (foo_mult (8, 2) != 16)
!     abort ();
! 
!   if (foo_mult (10, -2) != -20)
!     abort ();
! 
!   if (foo_mult (20, 5) != 100)
!     abort ();
! 
!   if (foo_mult (15, -3) != -45)
      abort ();
  
    return 0;


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