This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Fix PR56478
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.
--- 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;
+}
Marek