Patchwork Fix PR56478

login
register
mail settings
Submitter Marek Polacek
Date March 8, 2013, 12:16 p.m.
Message ID <20130308121637.GB18923@redhat.com>
Download mbox | patch
Permalink /patch/226096/
State New
Headers show

Comments

Marek Polacek - March 8, 2013, 12:16 p.m.
On Thu, Mar 07, 2013 at 03:25:35PM +0100, Jakub Jelinek wrote:
> On Tue, Mar 05, 2013 at 10:07:50AM +0100, Marek Polacek wrote:
> > +      if (compare_count.scmp (double_int_zero) == -1)
> > +        compare_count = double_int_zero;
> > +      if (loop_count.scmp (double_int_zero) == -1)
> > +        loop_count = double_int_zero;
> 
> Use if (compare_count.is_negative ()) etc. instead?

Done.

> > -	probability = (double) REG_BR_PROB_BASE * compare_count / loop_count;
> > -      predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
> > +        {
> > +	  tem = compare_count.divmod_with_overflow (loop_count,
> > +						     0, TRUNC_DIV_EXPR,
> > +						     &mod, &of);
> 
> This is wrong.  As compare_count is < loop_count, this will always yield
> zero.
> 
> I guess you want something like:
>   /* If loop_count is too big, such that REG_BR_PROB_BASE * loop_count
>      could overflow, shift both loop_count and compare_count right a bit
>      so that it doesn't overflow.  Note both counts are known not to be
>      negative at this point.  */
>   int clz_bits = clz_hwi (loop_count.high);
>   gcc_assert (REG_BR_PROB_BASE < 32768);
>   if (clz_bits < 16)
>     {
>       loop_count.arshift (16 - clz_bits, HOST_BITS_PER_DOUBLE_INT);
>       compare_count.arshift (16 - clz_bits, HOST_BITS_PER_DOUBLE_INT);
>     }
>   tem = loop_count.mul_with_sign (double_int::from_shwi (REG_BR_PROB_BASE),
> 				  true, &of);
>   gcc_assert (!of);
>   tem = tem.divmod (loop_count, true, TRUNC_DIV_EXPR, &mod);
>   probability = tem.to_uhwi ();
>   predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);

Thanks.  How does it look now?  I've discovered that previous patch
caused a regression, so I had to find the bug and retest etc.
(There was loop_count instead of compare_count.)

Regtested/bootstrapped on x86_64-linux, ok for trunk?  Or do you want
me to change anything?

2013-03-08  Marek Polacek  <polacek@redhat.com>
	    Jakub Jelinek <jakub@redhat.com>

	PR tree-optimization/56478
	* predict.c (is_comparison_with_loop_invariant_p): Change the
	type of loop_step to tree.
	(predict_loops): Adjust.
	(predict_iv_comparison): Perform the computations on double_ints.

	* gcc.dg/torture/pr56478.c: New test.


	Marek
Jakub Jelinek - March 8, 2013, 12:30 p.m.
On Fri, Mar 08, 2013 at 01:16:37PM +0100, Marek Polacek wrote:
> --- gcc/predict.c.mp	2013-03-07 20:01:01.078417558 +0100
> +++ gcc/predict.c	2013-03-08 11:35:05.227603993 +0100
> @@ -1028,13 +1028,13 @@ static bool
>  is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop,
>  				     tree *loop_invariant,
>  				     enum tree_code *compare_code,
> -				     int *loop_step,
> +				     tree *loop_step,
>  				     tree *loop_iv_base)
>  {
>    tree op0, op1, bound, base;
>    affine_iv iv0, iv1;
>    enum tree_code code;
> -  int step;
> +  tree step;
>  
>    code = gimple_cond_code (stmt);
>    *loop_invariant = NULL;
> @@ -1077,7 +1077,7 @@ is_comparison_with_loop_invariant_p (gim
>        bound = iv0.base;
>        base = iv1.base;
>        if (host_integerp (iv1.step, 0))
> -	step = tree_low_cst (iv1.step, 0);
> +	step = iv1.step;
>        else
>  	return false;
>      }
> @@ -1086,7 +1086,7 @@ is_comparison_with_loop_invariant_p (gim
>        bound = iv1.base;
>        base = iv0.base;
>        if (host_integerp (iv0.step, 0))
> -	step = tree_low_cst (iv0.step, 0);  
> +	step = iv0.step;
>        else
>  	return false;
>      }

If the callers use double_int computation, perhaps there is
no reason for the host_integerp checks and all we could verify is
that the trees have TREE_CODE (iv0.step) etc. == INTEGER_CST
(and perhaps that if the type of them is unsigned, then they don't
have the msb set (i.e.
!TYPE_UNSIGNED (TREE_TYPE (iv0.step))
|| !tree_to_double_int (iv0.step).is_negative () ).
But perhaps that can be left for 4.9 as an improvement?

> @@ -1224,34 +1224,78 @@ predict_iv_comparison (struct loop *loop
>        && host_integerp (compare_base, 0))

Ditto the host_integerp checks above.

> +      if ((compare_step.scmp (double_int_zero) == 1)

I believe compare_step should be known not to be zero here (there are
integer_zerop checks earlier, aren't they), so this could be also
!compare_step.is_negative ()
?

Other than that it looks good to me, Richard, is this fine for you too?

	Jakub
Richard Guenther - March 8, 2013, 1:10 p.m.
On Fri, Mar 8, 2013 at 1:30 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Fri, Mar 08, 2013 at 01:16:37PM +0100, Marek Polacek wrote:
>> --- gcc/predict.c.mp  2013-03-07 20:01:01.078417558 +0100
>> +++ gcc/predict.c     2013-03-08 11:35:05.227603993 +0100
>> @@ -1028,13 +1028,13 @@ static bool
>>  is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop,
>>                                    tree *loop_invariant,
>>                                    enum tree_code *compare_code,
>> -                                  int *loop_step,
>> +                                  tree *loop_step,
>>                                    tree *loop_iv_base)
>>  {
>>    tree op0, op1, bound, base;
>>    affine_iv iv0, iv1;
>>    enum tree_code code;
>> -  int step;
>> +  tree step;
>>
>>    code = gimple_cond_code (stmt);
>>    *loop_invariant = NULL;
>> @@ -1077,7 +1077,7 @@ is_comparison_with_loop_invariant_p (gim
>>        bound = iv0.base;
>>        base = iv1.base;
>>        if (host_integerp (iv1.step, 0))
>> -     step = tree_low_cst (iv1.step, 0);
>> +     step = iv1.step;
>>        else
>>       return false;
>>      }
>> @@ -1086,7 +1086,7 @@ is_comparison_with_loop_invariant_p (gim
>>        bound = iv1.base;
>>        base = iv0.base;
>>        if (host_integerp (iv0.step, 0))
>> -     step = tree_low_cst (iv0.step, 0);
>> +     step = iv0.step;
>>        else
>>       return false;
>>      }
>
> If the callers use double_int computation, perhaps there is
> no reason for the host_integerp checks and all we could verify is
> that the trees have TREE_CODE (iv0.step) etc. == INTEGER_CST
> (and perhaps that if the type of them is unsigned, then they don't
> have the msb set (i.e.
> !TYPE_UNSIGNED (TREE_TYPE (iv0.step))
> || !tree_to_double_int (iv0.step).is_negative () ).
> But perhaps that can be left for 4.9 as an improvement?
>
>> @@ -1224,34 +1224,78 @@ predict_iv_comparison (struct loop *loop
>>        && host_integerp (compare_base, 0))
>
> Ditto the host_integerp checks above.
>
>> +      if ((compare_step.scmp (double_int_zero) == 1)
>
> I believe compare_step should be known not to be zero here (there are
> integer_zerop checks earlier, aren't they), so this could be also
> !compare_step.is_negative ()
> ?
>
> Other than that it looks good to me, Richard, is this fine for you too?

Yes.

Thanks,
Richard.

>         Jakub

Patch

--- gcc/predict.c.mp	2013-03-07 20:01:01.078417558 +0100
+++ gcc/predict.c	2013-03-08 11:35:05.227603993 +0100
@@ -1028,13 +1028,13 @@  static bool
 is_comparison_with_loop_invariant_p (gimple stmt, struct loop *loop,
 				     tree *loop_invariant,
 				     enum tree_code *compare_code,
-				     int *loop_step,
+				     tree *loop_step,
 				     tree *loop_iv_base)
 {
   tree op0, op1, bound, base;
   affine_iv iv0, iv1;
   enum tree_code code;
-  int step;
+  tree step;
 
   code = gimple_cond_code (stmt);
   *loop_invariant = NULL;
@@ -1077,7 +1077,7 @@  is_comparison_with_loop_invariant_p (gim
       bound = iv0.base;
       base = iv1.base;
       if (host_integerp (iv1.step, 0))
-	step = tree_low_cst (iv1.step, 0);
+	step = iv1.step;
       else
 	return false;
     }
@@ -1086,7 +1086,7 @@  is_comparison_with_loop_invariant_p (gim
       bound = iv1.base;
       base = iv0.base;
       if (host_integerp (iv0.step, 0))
-	step = tree_low_cst (iv0.step, 0);  
+	step = iv0.step;
       else
 	return false;
     }
@@ -1178,7 +1178,7 @@  predict_iv_comparison (struct loop *loop
   gimple stmt;
   tree compare_var, compare_base;
   enum tree_code compare_code;
-  int compare_step;
+  tree compare_step_var;
   edge then_edge;
   edge_iterator ei;
 
@@ -1192,7 +1192,7 @@  predict_iv_comparison (struct loop *loop
     return;
   if (!is_comparison_with_loop_invariant_p (stmt, loop, &compare_var,
 					    &compare_code,
-					    &compare_step,
+					    &compare_step_var,
 					    &compare_base))
     return;
 
@@ -1224,34 +1224,78 @@  predict_iv_comparison (struct loop *loop
       && host_integerp (compare_base, 0))
     {
       int probability;
-      HOST_WIDE_INT compare_count;
-      HOST_WIDE_INT loop_bound = tree_low_cst (loop_bound_var, 0);
-      HOST_WIDE_INT compare_bound = tree_low_cst (compare_var, 0);
-      HOST_WIDE_INT base = tree_low_cst (compare_base, 0);
-      HOST_WIDE_INT loop_count = (loop_bound - base) / compare_step;
+      bool of, overflow = false;
+      double_int mod, compare_count, tem, loop_count;
 
-      if ((compare_step > 0)
+      double_int loop_bound = tree_to_double_int (loop_bound_var);
+      double_int compare_bound = tree_to_double_int (compare_var);
+      double_int base = tree_to_double_int (compare_base);
+      double_int compare_step = tree_to_double_int (compare_step_var);
+
+      /* (loop_bound - base) / compare_step */
+      tem = loop_bound.sub_with_overflow (base, &of);
+      overflow |= of;
+      loop_count = tem.divmod_with_overflow (compare_step,
+					      0, TRUNC_DIV_EXPR,
+					      &mod, &of);
+      overflow |= of;
+
+      if ((compare_step.scmp (double_int_zero) == 1)
           ^ (compare_code == LT_EXPR || compare_code == LE_EXPR))
-	compare_count = (loop_bound - compare_bound) / compare_step;
+	{
+	  /* (loop_bound - compare_bound) / compare_step */
+	  tem = loop_bound.sub_with_overflow (compare_bound, &of);
+	  overflow |= of;
+	  compare_count = tem.divmod_with_overflow (compare_step,
+						     0, TRUNC_DIV_EXPR,
+						     &mod, &of);
+	  overflow |= of;
+	}
       else
-	compare_count = (compare_bound - base) / compare_step;
-
+        {
+	  /* (compare_bound - base) / compare_step */
+	  tem = compare_bound.sub_with_overflow (base, &of);
+	  overflow |= of;
+          compare_count = tem.divmod_with_overflow (compare_step,
+						     0, TRUNC_DIV_EXPR,
+						     &mod, &of);
+	  overflow |= of;
+	}
       if (compare_code == LE_EXPR || compare_code == GE_EXPR)
-	compare_count ++;
+	++compare_count;
       if (loop_bound_code == LE_EXPR || loop_bound_code == GE_EXPR)
-	loop_count ++;
-      if (compare_count < 0)
-	compare_count = 0;
-      if (loop_count < 0)
-	loop_count = 0;
-
-      if (loop_count == 0)
+	++loop_count;
+      if (compare_count.is_negative ())
+        compare_count = double_int_zero;
+      if (loop_count.is_negative ())
+        loop_count = double_int_zero;
+      if (loop_count.is_zero ())
 	probability = 0;
-      else if (compare_count > loop_count)
+      else if (compare_count.scmp (loop_count) == 1)
 	probability = REG_BR_PROB_BASE;
       else
-	probability = (double) REG_BR_PROB_BASE * compare_count / loop_count;
-      predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
+        {
+	  /* If loop_count is too big, such that REG_BR_PROB_BASE * loop_count
+	     could overflow, shift both loop_count and compare_count right
+	     a bit so that it doesn't overflow.  Note both counts are known not
+	     to be negative at this point.  */
+	  int clz_bits = clz_hwi (loop_count.high);
+	  gcc_assert (REG_BR_PROB_BASE < 32768);
+	  if (clz_bits < 16)
+	    {
+	      loop_count.arshift (16 - clz_bits, HOST_BITS_PER_DOUBLE_INT);
+	      compare_count.arshift (16 - clz_bits, HOST_BITS_PER_DOUBLE_INT);
+	    }
+	  tem = compare_count.mul_with_sign (double_int::from_shwi
+					    (REG_BR_PROB_BASE), true, &of);
+	  gcc_assert (!of);
+	  tem = tem.divmod (loop_count, true, TRUNC_DIV_EXPR, &mod);
+	  probability = tem.to_uhwi ();
+	}
+
+      if (!overflow)
+        predict_edge (then_edge, PRED_LOOP_IV_COMPARE, probability);
+
       return;
     }
 
@@ -1402,7 +1446,7 @@  predict_loops (void)
       edge ex;
       struct nb_iter_bound *nb_iter;
       enum tree_code loop_bound_code = ERROR_MARK;
-      int loop_bound_step = 0;
+      tree loop_bound_step = NULL;
       tree loop_bound_var = NULL;
       tree loop_iv_base = NULL;
       gimple stmt = NULL;
@@ -1549,7 +1593,7 @@  predict_loops (void)
 	  if (loop_bound_var)
 	    predict_iv_comparison (loop, bb, loop_bound_var, loop_iv_base,
 				   loop_bound_code,
-				   loop_bound_step);
+				   tree_low_cst (loop_bound_step, 0));
 	}
 
       /* Free basic blocks from get_loop_body.  */
--- gcc/testsuite/gcc.dg/torture/pr56478.c.mp	2013-03-08 11:35:55.763742165 +0100
+++ gcc/testsuite/gcc.dg/torture/pr56478.c	2013-03-08 11:35:05.228603996 +0100
@@ -0,0 +1,12 @@ 
+/* PR tree-optimization/56478 */
+/* { dg-do compile } */
+
+int a;
+
+void
+foo ()
+{
+  int b;
+  for (b = 0;; b++)
+    a = 0 < -__LONG_LONG_MAX__ - 1 - b ? : 0;
+}