Re: [PATCH] Fix PR78305
On November 16, 2016 5:22:17 PM GMT+01:00, Marc Glisse wrote: >On Wed, 16 Nov 2016, Michael Matz wrote: > >> Hi, >> >> On Wed, 16 Nov 2016, Marc Glisse wrote: >> > The first sentence about ORing the sign bit sounds strange (except >for a > sign-magnitude representation). With 2's complement, INT_MIN is >-2^31, the > divisors are the 2^k and -(2^k). -2 * 2^30 yields INT_MIN, but >your test > misses -2 as a possible divisor. On the other hand, 0b100...001 >(aka > -INT_MAX) > is not a divisor of INT_MIN but your test says the reverse. Yeah, but it handled the testcase ;) So I guess the easiest would >be to check integer_pow2p (abs (TREE_OPERAND (t, 0)) then, thus wi::popcount (wi::abs (TREE_OPERAND (t, 0))) == 1? >>> >>> Looks good to me, thanks. >> >> An integer X is a power of two if and only if >> X & -X == 0 (&& X != 0 if you want to exclude zero) >> which also nicely handles positive and negative numbers at the same >time. >> No need for popcounts or abs. > >There are bit tricks to test for powers of 2, but X & -X == 0 doesn't >quite work (X & -X == X is closer, but needs a tweak for negative >numbers). We could use >wi::pow2_p (wi::abs (TREE_OPERAND (t, 0))) >adding a new function pow2_p so it remains readable and we reduce the >risk >of using the wrong bit trick... Tree_pow2p uses wi::popcount Richard.
Re: [PATCH] Fix PR78305
On Wed, 16 Nov 2016, Michael Matz wrote: Hi, On Wed, 16 Nov 2016, Marc Glisse wrote: The first sentence about ORing the sign bit sounds strange (except for a sign-magnitude representation). With 2's complement, INT_MIN is -2^31, the divisors are the 2^k and -(2^k). -2 * 2^30 yields INT_MIN, but your test misses -2 as a possible divisor. On the other hand, 0b100...001 (aka -INT_MAX) is not a divisor of INT_MIN but your test says the reverse. Yeah, but it handled the testcase ;) So I guess the easiest would be to check integer_pow2p (abs (TREE_OPERAND (t, 0)) then, thus wi::popcount (wi::abs (TREE_OPERAND (t, 0))) == 1? Looks good to me, thanks. An integer X is a power of two if and only if X & -X == 0 (&& X != 0 if you want to exclude zero) which also nicely handles positive and negative numbers at the same time. No need for popcounts or abs. There are bit tricks to test for powers of 2, but X & -X == 0 doesn't quite work (X & -X == X is closer, but needs a tweak for negative numbers). We could use wi::pow2_p (wi::abs (TREE_OPERAND (t, 0))) adding a new function pow2_p so it remains readable and we reduce the risk of using the wrong bit trick... -- Marc Glisse
Re: [PATCH] Fix PR78305
Hi, On Wed, 16 Nov 2016, Michael Matz wrote: > > Looks good to me, thanks. > > An integer X is a power of two if and only if > X & -X == 0 (&& X != 0 if you want to exclude zero) Nonsense. It's X & -X == X (or X & (X-1) == 0) of course, and doesn't handle negative numbers. Still, no popcount needed. Ciao, Michael.
Re: [PATCH] Fix PR78305
Hi, On Wed, 16 Nov 2016, Marc Glisse wrote: > > > The first sentence about ORing the sign bit sounds strange (except for a > > > sign-magnitude representation). With 2's complement, INT_MIN is -2^31, the > > > divisors are the 2^k and -(2^k). -2 * 2^30 yields INT_MIN, but your test > > > misses -2 as a possible divisor. On the other hand, 0b100...001 (aka > > > -INT_MAX) > > > is not a divisor of INT_MIN but your test says the reverse. > > > > Yeah, but it handled the testcase ;) So I guess the easiest would be > > to check integer_pow2p (abs (TREE_OPERAND (t, 0)) then, thus > > wi::popcount (wi::abs (TREE_OPERAND (t, 0))) == 1? > > Looks good to me, thanks. An integer X is a power of two if and only if X & -X == 0 (&& X != 0 if you want to exclude zero) which also nicely handles positive and negative numbers at the same time. No need for popcounts or abs. Ciao, Michael.
Re: [PATCH] Fix PR78305
On Wed, 16 Nov 2016, Richard Biener wrote: On Wed, 16 Nov 2016, Marc Glisse wrote: On Wed, 16 Nov 2016, Richard Biener wrote: On Wed, 16 Nov 2016, Marc Glisse wrote: On Wed, 16 Nov 2016, Richard Biener wrote: I am testing the following to avoid undefined behavior when negating a multiplication (basically extending a previous fix to properly handle negative power of two). Bootstrap / regtest running on x86_64-unknown-linux-gnu. Richard. 2016-11-16 Richard Biener PR middle-end/78305 * fold-const.c (negate_expr_p): Fix multiplication case. * gcc.dg/torture/pr78305.c: New testcase. Index: gcc/fold-const.c === --- gcc/fold-const.c(revision 242471) +++ gcc/fold-const.c(working copy) @@ -450,13 +450,15 @@ negate_expr_p (tree t) if (TYPE_UNSIGNED (type)) break; /* INT_MIN/n * n doesn't overflow while negating one operand it does - if n is a power of two. */ + if n is a power of (minus) two. */ if n is (minus) a power of two. if n is a divisor of INT_MIN. n is a divisor of INT_MIN is correct. if (INTEGRAL_TYPE_P (TREE_TYPE (t)) && ! TYPE_OVERFLOW_WRAPS (TREE_TYPE (t)) && ! ((TREE_CODE (TREE_OPERAND (t, 0)) == INTEGER_CST -&& ! integer_pow2p (TREE_OPERAND (t, 0))) +&& (wi::popcount (TREE_OPERAND (t, 0)) +!= 1 + wi::neg_p (TREE_OPERAND (t, 0), SIGNED))) Is that supposed to test for (possibly negated) powers of 2? I don't see it. For -2, aka 0b11...110, popcount is 31 != 1 + 1. It's supposed to test for a power of two with the sign-bit ORed in. I believe those are which, when multiplied with some number can yield INT_MIN. That is, we look for a test that ensures that there exists no number when multiplied with X yields INT_MIN. The first sentence about ORing the sign bit sounds strange (except for a sign-magnitude representation). With 2's complement, INT_MIN is -2^31, the divisors are the 2^k and -(2^k). -2 * 2^30 yields INT_MIN, but your test misses -2 as a possible divisor. On the other hand, 0b100...001 (aka -INT_MAX) is not a divisor of INT_MIN but your test says the reverse. Yeah, but it handled the testcase ;) So I guess the easiest would be to check integer_pow2p (abs (TREE_OPERAND (t, 0)) then, thus wi::popcount (wi::abs (TREE_OPERAND (t, 0))) == 1? Looks good to me, thanks. -- Marc Glisse
Re: [PATCH] Fix PR78305
On Wed, 16 Nov 2016, Marc Glisse wrote: > On Wed, 16 Nov 2016, Richard Biener wrote: > > > On Wed, 16 Nov 2016, Marc Glisse wrote: > > > > > On Wed, 16 Nov 2016, Richard Biener wrote: > > > > > > > I am testing the following to avoid undefined behavior when negating > > > > a multiplication (basically extending a previous fix to properly handle > > > > negative power of two). > > > > > > > > Bootstrap / regtest running on x86_64-unknown-linux-gnu. > > > > > > > > Richard. > > > > > > > > 2016-11-16 Richard Biener > > > > > > > > PR middle-end/78305 > > > > * fold-const.c (negate_expr_p): Fix multiplication case. > > > > > > > > * gcc.dg/torture/pr78305.c: New testcase. > > > > > > > > Index: gcc/fold-const.c > > > > === > > > > --- gcc/fold-const.c(revision 242471) > > > > +++ gcc/fold-const.c(working copy) > > > > @@ -450,13 +450,15 @@ negate_expr_p (tree t) > > > > if (TYPE_UNSIGNED (type)) > > > > break; > > > > /* INT_MIN/n * n doesn't overflow while negating one operand it > > > > does > > > > - if n is a power of two. */ > > > > + if n is a power of (minus) two. */ > > > > > > if n is (minus) a power of two. > > > if n is a divisor of INT_MIN. > > > > n is a divisor of INT_MIN is correct. > > > > > > if (INTEGRAL_TYPE_P (TREE_TYPE (t)) > > > > && ! TYPE_OVERFLOW_WRAPS (TREE_TYPE (t)) > > > > && ! ((TREE_CODE (TREE_OPERAND (t, 0)) == INTEGER_CST > > > > -&& ! integer_pow2p (TREE_OPERAND (t, 0))) > > > > +&& (wi::popcount (TREE_OPERAND (t, 0)) > > > > +!= 1 + wi::neg_p (TREE_OPERAND (t, 0), SIGNED))) > > > > > > Is that supposed to test for (possibly negated) powers of 2? I don't see > > > it. > > > For -2, aka 0b11...110, popcount is 31 != 1 + 1. > > > > It's supposed to test for a power of two with the sign-bit ORed in. > > I believe those are which, when multiplied with some number can > > yield INT_MIN. That is, we look for a test that ensures that there > > exists no number when multiplied with X yields INT_MIN. > > The first sentence about ORing the sign bit sounds strange (except for a > sign-magnitude representation). With 2's complement, INT_MIN is -2^31, the > divisors are the 2^k and -(2^k). -2 * 2^30 yields INT_MIN, but your test > misses -2 as a possible divisor. On the other hand, 0b100...001 (aka -INT_MAX) > is not a divisor of INT_MIN but your test says the reverse. Yeah, but it handled the testcase ;) So I guess the easiest would be to check integer_pow2p (abs (TREE_OPERAND (t, 0)) then, thus wi::popcount (wi::abs (TREE_OPERAND (t, 0))) == 1? Thanks, Richard.
Re: [PATCH] Fix PR78305
On Wed, 16 Nov 2016, Richard Biener wrote: On Wed, 16 Nov 2016, Marc Glisse wrote: On Wed, 16 Nov 2016, Richard Biener wrote: I am testing the following to avoid undefined behavior when negating a multiplication (basically extending a previous fix to properly handle negative power of two). Bootstrap / regtest running on x86_64-unknown-linux-gnu. Richard. 2016-11-16 Richard Biener PR middle-end/78305 * fold-const.c (negate_expr_p): Fix multiplication case. * gcc.dg/torture/pr78305.c: New testcase. Index: gcc/fold-const.c === --- gcc/fold-const.c(revision 242471) +++ gcc/fold-const.c(working copy) @@ -450,13 +450,15 @@ negate_expr_p (tree t) if (TYPE_UNSIGNED (type)) break; /* INT_MIN/n * n doesn't overflow while negating one operand it does - if n is a power of two. */ + if n is a power of (minus) two. */ if n is (minus) a power of two. if n is a divisor of INT_MIN. n is a divisor of INT_MIN is correct. if (INTEGRAL_TYPE_P (TREE_TYPE (t)) && ! TYPE_OVERFLOW_WRAPS (TREE_TYPE (t)) && ! ((TREE_CODE (TREE_OPERAND (t, 0)) == INTEGER_CST -&& ! integer_pow2p (TREE_OPERAND (t, 0))) +&& (wi::popcount (TREE_OPERAND (t, 0)) +!= 1 + wi::neg_p (TREE_OPERAND (t, 0), SIGNED))) Is that supposed to test for (possibly negated) powers of 2? I don't see it. For -2, aka 0b11...110, popcount is 31 != 1 + 1. It's supposed to test for a power of two with the sign-bit ORed in. I believe those are which, when multiplied with some number can yield INT_MIN. That is, we look for a test that ensures that there exists no number when multiplied with X yields INT_MIN. The first sentence about ORing the sign bit sounds strange (except for a sign-magnitude representation). With 2's complement, INT_MIN is -2^31, the divisors are the 2^k and -(2^k). -2 * 2^30 yields INT_MIN, but your test misses -2 as a possible divisor. On the other hand, 0b100...001 (aka -INT_MAX) is not a divisor of INT_MIN but your test says the reverse. -- Marc Glisse
Re: [PATCH] Fix PR78305
On Wed, 16 Nov 2016, Marc Glisse wrote:
> On Wed, 16 Nov 2016, Richard Biener wrote:
>
> > I am testing the following to avoid undefined behavior when negating
> > a multiplication (basically extending a previous fix to properly handle
> > negative power of two).
> >
> > Bootstrap / regtest running on x86_64-unknown-linux-gnu.
> >
> > Richard.
> >
> > 2016-11-16 Richard Biener
> >
> > PR middle-end/78305
> > * fold-const.c (negate_expr_p): Fix multiplication case.
> >
> > * gcc.dg/torture/pr78305.c: New testcase.
> >
> > Index: gcc/fold-const.c
> > ===
> > --- gcc/fold-const.c(revision 242471)
> > +++ gcc/fold-const.c(working copy)
> > @@ -450,13 +450,15 @@ negate_expr_p (tree t)
> > if (TYPE_UNSIGNED (type))
> > break;
> > /* INT_MIN/n * n doesn't overflow while negating one operand it does
> > - if n is a power of two. */
> > + if n is a power of (minus) two. */
>
> if n is (minus) a power of two.
> if n is a divisor of INT_MIN.
n is a divisor of INT_MIN is correct.
> > if (INTEGRAL_TYPE_P (TREE_TYPE (t))
> > && ! TYPE_OVERFLOW_WRAPS (TREE_TYPE (t))
> > && ! ((TREE_CODE (TREE_OPERAND (t, 0)) == INTEGER_CST
> > -&& ! integer_pow2p (TREE_OPERAND (t, 0)))
> > +&& (wi::popcount (TREE_OPERAND (t, 0))
> > +!= 1 + wi::neg_p (TREE_OPERAND (t, 0), SIGNED)))
>
> Is that supposed to test for (possibly negated) powers of 2? I don't see it.
> For -2, aka 0b11...110, popcount is 31 != 1 + 1.
It's supposed to test for a power of two with the sign-bit ORed in.
I believe those are which, when multiplied with some number can
yield INT_MIN. That is, we look for a test that ensures that there
exists no number when multiplied with X yields INT_MIN.
Richard.
> > || (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST
> > - && ! integer_pow2p (TREE_OPERAND (t, 1)
> > + && (wi::popcount (TREE_OPERAND (t, 1))
> > + != 1 + wi::neg_p (TREE_OPERAND (t, 1), SIGNED)
> > break;
> >
> > /* Fall through. */
> > Index: gcc/testsuite/gcc.dg/torture/pr78305.c
> > ===
> > --- gcc/testsuite/gcc.dg/torture/pr78305.c (revision 0)
> > +++ gcc/testsuite/gcc.dg/torture/pr78305.c (working copy)
> > @@ -0,0 +1,14 @@
> > +/* { dg-require-effective-target int32plus } */
> > +/* { dg-do run } */
> > +
> > +int main ()
> > +{
> > + int a = 2;
> > + int b = 1;
> > +
> > + int t = -1 * ( -0x4000 * a / ( -0x2000 + b ) ) / -1;
> > +
> > + if (t != 4) __builtin_abort();
> > +
> > + return 0;
> > +}
> >
>
>
--
Richard Biener
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB
21284 (AG Nuernberg)
Re: [PATCH] Fix PR78305
On Wed, 16 Nov 2016, Richard Biener wrote:
I am testing the following to avoid undefined behavior when negating
a multiplication (basically extending a previous fix to properly handle
negative power of two).
Bootstrap / regtest running on x86_64-unknown-linux-gnu.
Richard.
2016-11-16 Richard Biener
PR middle-end/78305
* fold-const.c (negate_expr_p): Fix multiplication case.
* gcc.dg/torture/pr78305.c: New testcase.
Index: gcc/fold-const.c
===
--- gcc/fold-const.c(revision 242471)
+++ gcc/fold-const.c(working copy)
@@ -450,13 +450,15 @@ negate_expr_p (tree t)
if (TYPE_UNSIGNED (type))
break;
/* INT_MIN/n * n doesn't overflow while negating one operand it does
- if n is a power of two. */
+ if n is a power of (minus) two. */
if n is (minus) a power of two.
if n is a divisor of INT_MIN.
if (INTEGRAL_TYPE_P (TREE_TYPE (t))
&& ! TYPE_OVERFLOW_WRAPS (TREE_TYPE (t))
&& ! ((TREE_CODE (TREE_OPERAND (t, 0)) == INTEGER_CST
-&& ! integer_pow2p (TREE_OPERAND (t, 0)))
+&& (wi::popcount (TREE_OPERAND (t, 0))
+!= 1 + wi::neg_p (TREE_OPERAND (t, 0), SIGNED)))
Is that supposed to test for (possibly negated) powers of 2? I don't see
it. For -2, aka 0b11...110, popcount is 31 != 1 + 1.
|| (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST
- && ! integer_pow2p (TREE_OPERAND (t, 1)
+ && (wi::popcount (TREE_OPERAND (t, 1))
+ != 1 + wi::neg_p (TREE_OPERAND (t, 1), SIGNED)
break;
/* Fall through. */
Index: gcc/testsuite/gcc.dg/torture/pr78305.c
===
--- gcc/testsuite/gcc.dg/torture/pr78305.c (revision 0)
+++ gcc/testsuite/gcc.dg/torture/pr78305.c (working copy)
@@ -0,0 +1,14 @@
+/* { dg-require-effective-target int32plus } */
+/* { dg-do run } */
+
+int main ()
+{
+ int a = 2;
+ int b = 1;
+
+ int t = -1 * ( -0x4000 * a / ( -0x2000 + b ) ) / -1;
+
+ if (t != 4) __builtin_abort();
+
+ return 0;
+}
--
Marc Glisse
[PATCH] Fix PR78305
I am testing the following to avoid undefined behavior when negating
a multiplication (basically extending a previous fix to properly handle
negative power of two).
Bootstrap / regtest running on x86_64-unknown-linux-gnu.
Richard.
2016-11-16 Richard Biener
PR middle-end/78305
* fold-const.c (negate_expr_p): Fix multiplication case.
* gcc.dg/torture/pr78305.c: New testcase.
Index: gcc/fold-const.c
===
--- gcc/fold-const.c(revision 242471)
+++ gcc/fold-const.c(working copy)
@@ -450,13 +450,15 @@ negate_expr_p (tree t)
if (TYPE_UNSIGNED (type))
break;
/* INT_MIN/n * n doesn't overflow while negating one operand it does
- if n is a power of two. */
+ if n is a power of (minus) two. */
if (INTEGRAL_TYPE_P (TREE_TYPE (t))
&& ! TYPE_OVERFLOW_WRAPS (TREE_TYPE (t))
&& ! ((TREE_CODE (TREE_OPERAND (t, 0)) == INTEGER_CST
-&& ! integer_pow2p (TREE_OPERAND (t, 0)))
+&& (wi::popcount (TREE_OPERAND (t, 0))
+!= 1 + wi::neg_p (TREE_OPERAND (t, 0), SIGNED)))
|| (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST
- && ! integer_pow2p (TREE_OPERAND (t, 1)
+ && (wi::popcount (TREE_OPERAND (t, 1))
+ != 1 + wi::neg_p (TREE_OPERAND (t, 1), SIGNED)
break;
/* Fall through. */
Index: gcc/testsuite/gcc.dg/torture/pr78305.c
===
--- gcc/testsuite/gcc.dg/torture/pr78305.c (revision 0)
+++ gcc/testsuite/gcc.dg/torture/pr78305.c (working copy)
@@ -0,0 +1,14 @@
+/* { dg-require-effective-target int32plus } */
+/* { dg-do run } */
+
+int main ()
+{
+ int a = 2;
+ int b = 1;
+
+ int t = -1 * ( -0x4000 * a / ( -0x2000 + b ) ) / -1;
+
+ if (t != 4) __builtin_abort();
+
+ return 0;
+}
