| Message ID | alpine.LSU.2.11.1611161031530.5294@t29.fhfr.qr |
|---|---|
| State | New |
| Headers | show |
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 <rguenther@suse.de> > > 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 * ( -0x40000000 * a / ( -0x20000000 + b ) ) / -1; > + > + if (t != 4) __builtin_abort(); > + > + return 0; > +} >
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 <rguenther@suse.de> > > > > 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 * ( -0x40000000 * a / ( -0x20000000 + b ) ) / -1; > > + > > + if (t != 4) __builtin_abort(); > > + > > + return 0; > > +} > > > >
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 <rguenther@suse.de> >>> >>> 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.
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 <rguenther@suse.de> > > > > > > > > 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.
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 <rguenther@suse.de> >>>>> >>>>> 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.
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.
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.
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...
On November 16, 2016 5:22:17 PM GMT+01:00, Marc Glisse <marc.glisse@inria.fr> 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.
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 * ( -0x40000000 * a / ( -0x20000000 + b ) ) / -1; + + if (t != 4) __builtin_abort(); + + return 0; +}