* [PATCH] Fix wide_int unsigned division (PR tree-optimization/69546)
@ 2016-01-29 14:20 Jakub Jelinek
2016-01-30 12:31 ` Richard Sandiford
0 siblings, 1 reply; 6+ messages in thread
From: Jakub Jelinek @ 2016-01-29 14:20 UTC (permalink / raw)
To: Mike Stump, Richard Sandiford, Richard Biener; +Cc: gcc-patches
Hi!
As the testcase shows, wide_int unsigned division is broken for > 64bit
precision division of unsigned dividend which have 63rd bit set, and all
higher bits cleared (thus is normalized as 2 HWIs, first with MSB set,
the second 0) and divisor of 1, we return just a single HWI, which is
equivalent to all higher bits set too. If the divisor is > 1, there is
no such problem, as the MSB will not be set after the division.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
2016-01-29 Jakub Jelinek <jakub@redhat.com>
PR tree-optimization/69546
* wide-int.cc (wi::divmod_internal): For unsigned division
where both operands fit into uhwi, if o1 is 1 and o0 has
msb set, if divident_prec is larger than bits per hwi,
clear another quotient word and return 2 instead of 1.
* gcc.dg/torture/pr69546.c: New test.
--- gcc/wide-int.cc.jj 2016-01-26 11:46:39.000000000 +0100
+++ gcc/wide-int.cc 2016-01-29 11:59:33.348852003 +0100
@@ -1788,15 +1788,25 @@ wi::divmod_internal (HOST_WIDE_INT *quot
{
unsigned HOST_WIDE_INT o0 = dividend.to_uhwi ();
unsigned HOST_WIDE_INT o1 = divisor.to_uhwi ();
+ unsigned int quotient_len = 1;
if (quotient)
- quotient[0] = o0 / o1;
+ {
+ quotient[0] = o0 / o1;
+ if (o1 == 1
+ && (HOST_WIDE_INT) o0 < 0
+ && dividend_prec > HOST_BITS_PER_WIDE_INT)
+ {
+ quotient[1] = 0;
+ quotient_len = 2;
+ }
+ }
if (remainder)
{
remainder[0] = o0 % o1;
*remainder_len = 1;
}
- return 1;
+ return quotient_len;
}
/* Make the divisor and dividend positive and remember what we
--- gcc/testsuite/gcc.dg/torture/pr69546.c.jj 2016-01-29 12:06:03.148516651 +0100
+++ gcc/testsuite/gcc.dg/torture/pr69546.c 2016-01-29 12:08:17.847672967 +0100
@@ -0,0 +1,26 @@
+/* PR tree-optimization/69546 */
+/* { dg-do run { target int128 } } */
+
+unsigned __int128 __attribute__ ((noinline, noclone))
+foo (unsigned long long x)
+{
+ unsigned __int128 y = ~0ULL;
+ x >>= 63;
+ return y / (x | 1);
+}
+
+unsigned __int128 __attribute__ ((noinline, noclone))
+bar (unsigned long long x)
+{
+ unsigned __int128 y = ~33ULL;
+ x >>= 63;
+ return y / (x | 1);
+}
+
+int
+main ()
+{
+ if (foo (1) != ~0ULL || bar (17) != ~33ULL)
+ __builtin_abort ();
+ return 0;
+}
Jakub
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH] Fix wide_int unsigned division (PR tree-optimization/69546)
2016-01-29 14:20 [PATCH] Fix wide_int unsigned division (PR tree-optimization/69546) Jakub Jelinek
@ 2016-01-30 12:31 ` Richard Sandiford
2016-01-30 13:15 ` [PATCH] Fix wide_int unsigned division (PR tree-optimization/69546, take 2) Jakub Jelinek
0 siblings, 1 reply; 6+ messages in thread
From: Richard Sandiford @ 2016-01-30 12:31 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Mike Stump, Richard Biener, gcc-patches
Jakub Jelinek <jakub@redhat.com> writes:
> As the testcase shows, wide_int unsigned division is broken for > 64bit
> precision division of unsigned dividend which have 63rd bit set, and all
> higher bits cleared (thus is normalized as 2 HWIs, first with MSB set,
> the second 0) and divisor of 1, we return just a single HWI, which is
> equivalent to all higher bits set too. If the divisor is > 1, there is
> no such problem, as the MSB will not be set after the division.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
>
> 2016-01-29 Jakub Jelinek <jakub@redhat.com>
>
> PR tree-optimization/69546
> * wide-int.cc (wi::divmod_internal): For unsigned division
> where both operands fit into uhwi, if o1 is 1 and o0 has
> msb set, if divident_prec is larger than bits per hwi,
> clear another quotient word and return 2 instead of 1.
>
> * gcc.dg/torture/pr69546.c: New test.
>
> --- gcc/wide-int.cc.jj 2016-01-26 11:46:39.000000000 +0100
> +++ gcc/wide-int.cc 2016-01-29 11:59:33.348852003 +0100
> @@ -1788,15 +1788,25 @@ wi::divmod_internal (HOST_WIDE_INT *quot
> {
> unsigned HOST_WIDE_INT o0 = dividend.to_uhwi ();
> unsigned HOST_WIDE_INT o1 = divisor.to_uhwi ();
> + unsigned int quotient_len = 1;
>
> if (quotient)
> - quotient[0] = o0 / o1;
> + {
> + quotient[0] = o0 / o1;
> + if (o1 == 1
> + && (HOST_WIDE_INT) o0 < 0
> + && dividend_prec > HOST_BITS_PER_WIDE_INT)
> + {
> + quotient[1] = 0;
> + quotient_len = 2;
> + }
> + }
> if (remainder)
> {
> remainder[0] = o0 % o1;
> *remainder_len = 1;
> }
> - return 1;
> + return quotient_len;
> }
Might be wrong, but couldn't the same thing happen for the remainder,
e.g. for 0xfffffffe % 0xffffffff ? Maybe we should have a helper
function to handle storing uhwis in an array and returning the length.
Certainly seems like this function has had its fair share of bugs.
Thanks for fixing another.
Richard
^ permalink raw reply [flat|nested] 6+ messages in thread* [PATCH] Fix wide_int unsigned division (PR tree-optimization/69546, take 2)
2016-01-30 12:31 ` Richard Sandiford
@ 2016-01-30 13:15 ` Jakub Jelinek
2016-01-30 14:04 ` Richard Sandiford
0 siblings, 1 reply; 6+ messages in thread
From: Jakub Jelinek @ 2016-01-30 13:15 UTC (permalink / raw)
To: Mike Stump, Richard Biener, gcc-patches, rdsandiford
On Sat, Jan 30, 2016 at 12:31:05PM +0000, Richard Sandiford wrote:
> Might be wrong, but couldn't the same thing happen for the remainder,
> e.g. for 0xfffffffe % 0xffffffff ?
You're right, that is broken too. Adjusted patch below.
> Maybe we should have a helper
> function to handle storing uhwis in an array and returning the length.
Any suggestion how to call it, whether to put it in wi namespace, somewhere
else etc.? Can that be done as a follow-up? Certainly it would need
to take the uhwi to store, pointer to the array of hwis, and precision.
2016-01-30 Jakub Jelinek <jakub@redhat.com>
PR tree-optimization/69546
* wide-int.cc (wi::divmod_internal): For unsigned division
where both operands fit into uhwi, if o1 is 1 and o0 has
msb set, if divident_prec is larger than bits per hwi,
clear another quotient word and return 2 instead of 1.
Similarly for remainder with msb in HWI set, if dividend_prec
is larger than bits per hwi.
* gcc.dg/torture/pr69546.c: New test.
--- gcc/wide-int.cc.jj 2016-01-29 12:12:43.486930641 +0100
+++ gcc/wide-int.cc 2016-01-30 14:08:18.293537813 +0100
@@ -1788,15 +1788,32 @@ wi::divmod_internal (HOST_WIDE_INT *quot
{
unsigned HOST_WIDE_INT o0 = dividend.to_uhwi ();
unsigned HOST_WIDE_INT o1 = divisor.to_uhwi ();
+ unsigned int quotient_len = 1;
if (quotient)
- quotient[0] = o0 / o1;
+ {
+ quotient[0] = o0 / o1;
+ if (o1 == 1
+ && (HOST_WIDE_INT) o0 < 0
+ && dividend_prec > HOST_BITS_PER_WIDE_INT)
+ {
+ quotient[1] = 0;
+ quotient_len = 2;
+ }
+ }
if (remainder)
{
remainder[0] = o0 % o1;
- *remainder_len = 1;
+ if ((HOST_WIDE_INT) remainder[0] < 0
+ && dividend_prec > HOST_BITS_PER_WIDE_INT)
+ {
+ remainder[1] = 0;
+ *remainder_len = 2;
+ }
+ else
+ *remainder_len = 1;
}
- return 1;
+ return quotient_len;
}
/* Make the divisor and dividend positive and remember what we
--- gcc/testsuite/gcc.dg/torture/pr69546-1.c.jj 2016-01-30 13:58:25.925056607 +0100
+++ gcc/testsuite/gcc.dg/torture/pr69546-1.c 2016-01-30 13:58:25.925056607 +0100
@@ -0,0 +1,26 @@
+/* PR tree-optimization/69546 */
+/* { dg-do run { target int128 } } */
+
+unsigned __int128 __attribute__ ((noinline, noclone))
+foo (unsigned long long x)
+{
+ unsigned __int128 y = ~0ULL;
+ x >>= 63;
+ return y / (x | 1);
+}
+
+unsigned __int128 __attribute__ ((noinline, noclone))
+bar (unsigned long long x)
+{
+ unsigned __int128 y = ~33ULL;
+ x >>= 63;
+ return y / (x | 1);
+}
+
+int
+main ()
+{
+ if (foo (1) != ~0ULL || bar (17) != ~33ULL)
+ __builtin_abort ();
+ return 0;
+}
--- gcc/testsuite/gcc.dg/torture/pr69546-2.c.jj 2016-01-30 14:09:40.403364637 +0100
+++ gcc/testsuite/gcc.dg/torture/pr69546-2.c 2016-01-30 14:10:15.591861868 +0100
@@ -0,0 +1,18 @@
+/* PR tree-optimization/69546 */
+/* { dg-do run { target int128 } } */
+
+unsigned __int128
+foo (void)
+{
+ unsigned __int128 a = 0xfffffffffffffffeULL;
+ unsigned __int128 b = 0xffffffffffffffffULL;
+ return a % b;
+}
+
+int
+main ()
+{
+ if (foo () != 0xfffffffffffffffeULL)
+ __builtin_abort ();
+ return 0;
+}
Jakub
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH] Fix wide_int unsigned division (PR tree-optimization/69546, take 2)
2016-01-30 13:15 ` [PATCH] Fix wide_int unsigned division (PR tree-optimization/69546, take 2) Jakub Jelinek
@ 2016-01-30 14:04 ` Richard Sandiford
2016-02-01 20:25 ` Jakub Jelinek
0 siblings, 1 reply; 6+ messages in thread
From: Richard Sandiford @ 2016-01-30 14:04 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Mike Stump, Richard Biener, gcc-patches
Jakub Jelinek <jakub@redhat.com> writes:
> On Sat, Jan 30, 2016 at 12:31:05PM +0000, Richard Sandiford wrote:
>> Might be wrong, but couldn't the same thing happen for the remainder,
>> e.g. for 0xfffffffe % 0xffffffff ?
>
> You're right, that is broken too. Adjusted patch below.
>
>> Maybe we should have a helper
>> function to handle storing uhwis in an array and returning the length.
>
> Any suggestion how to call it, whether to put it in wi namespace, somewhere
> else etc.?
I think it should be local to wide-int.cc rather than in wi::. Users of
the public interface should always be using wi::uhwi (...). We only get
into this mess because we're trying to operate on the arrays directly,
rather than using the abstractions in the public interface.
Not sure what to call it. Maybe canonize_uhwi? Like canonize, except
that it takes a uhwi instead of a length.
> Can that be done as a follow-up? Certainly it would need
> to take the uhwi to store, pointer to the array of hwis, and precision.
Yeah, guess it can wait.
> 2016-01-30 Jakub Jelinek <jakub@redhat.com>
>
> PR tree-optimization/69546
> * wide-int.cc (wi::divmod_internal): For unsigned division
> where both operands fit into uhwi, if o1 is 1 and o0 has
> msb set, if divident_prec is larger than bits per hwi,
> clear another quotient word and return 2 instead of 1.
> Similarly for remainder with msb in HWI set, if dividend_prec
> is larger than bits per hwi.
>
> * gcc.dg/torture/pr69546.c: New test.
>
> --- gcc/wide-int.cc.jj 2016-01-29 12:12:43.486930641 +0100
> +++ gcc/wide-int.cc 2016-01-30 14:08:18.293537813 +0100
> @@ -1788,15 +1788,32 @@ wi::divmod_internal (HOST_WIDE_INT *quot
> {
> unsigned HOST_WIDE_INT o0 = dividend.to_uhwi ();
> unsigned HOST_WIDE_INT o1 = divisor.to_uhwi ();
> + unsigned int quotient_len = 1;
>
> if (quotient)
> - quotient[0] = o0 / o1;
> + {
> + quotient[0] = o0 / o1;
> + if (o1 == 1
> + && (HOST_WIDE_INT) o0 < 0
> + && dividend_prec > HOST_BITS_PER_WIDE_INT)
> + {
> + quotient[1] = 0;
> + quotient_len = 2;
> + }
> + }
> if (remainder)
> {
> remainder[0] = o0 % o1;
> - *remainder_len = 1;
> + if ((HOST_WIDE_INT) remainder[0] < 0
> + && dividend_prec > HOST_BITS_PER_WIDE_INT)
> + {
> + remainder[1] = 0;
> + *remainder_len = 2;
> + }
> + else
> + *remainder_len = 1;
> }
> - return 1;
> + return quotient_len;
> }
LGTM, thanks.
Richard
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH] Fix wide_int unsigned division (PR tree-optimization/69546, take 2)
2016-01-30 14:04 ` Richard Sandiford
@ 2016-02-01 20:25 ` Jakub Jelinek
2016-02-02 15:49 ` Richard Sandiford
0 siblings, 1 reply; 6+ messages in thread
From: Jakub Jelinek @ 2016-02-01 20:25 UTC (permalink / raw)
To: Mike Stump, Richard Biener, gcc-patches, rdsandiford
On Sat, Jan 30, 2016 at 02:04:45PM +0000, Richard Sandiford wrote:
> Not sure what to call it. Maybe canonize_uhwi? Like canonize, except
> that it takes a uhwi instead of a length.
>
> > Can that be done as a follow-up? Certainly it would need
> > to take the uhwi to store, pointer to the array of hwis, and precision.
>
> Yeah, guess it can wait.
So like this?
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
2016-02-01 Jakub Jelinek <jakub@redhat.com>
* wide-int.cc (canonize_uhwi): New function.
(wi::divmod_internal): Use it.
--- gcc/wide-int.cc.jj 2016-01-30 19:03:35.000000000 +0100
+++ gcc/wide-int.cc 2016-02-01 12:28:23.501519292 +0100
@@ -118,6 +118,20 @@ canonize (HOST_WIDE_INT *val, unsigned i
return 1;
}
+/* VAL[0] is unsigned result of operation. Canonize it by adding
+ another 0 block if needed, and return number of blocks needed. */
+
+static inline unsigned int
+canonize_uhwi (HOST_WIDE_INT *val, unsigned int precision)
+{
+ if (val[0] < 0 && precision > HOST_BITS_PER_WIDE_INT)
+ {
+ val[1] = 0;
+ return 2;
+ }
+ return 1;
+}
+
/*
* Conversion routines in and out of wide_int.
*/
@@ -1793,25 +1807,12 @@ wi::divmod_internal (HOST_WIDE_INT *quot
if (quotient)
{
quotient[0] = o0 / o1;
- if (o1 == 1
- && (HOST_WIDE_INT) o0 < 0
- && dividend_prec > HOST_BITS_PER_WIDE_INT)
- {
- quotient[1] = 0;
- quotient_len = 2;
- }
+ quotient_len = canonize_uhwi (quotient, dividend_prec);
}
if (remainder)
{
remainder[0] = o0 % o1;
- if ((HOST_WIDE_INT) remainder[0] < 0
- && dividend_prec > HOST_BITS_PER_WIDE_INT)
- {
- remainder[1] = 0;
- *remainder_len = 2;
- }
- else
- *remainder_len = 1;
+ *remainder_len = canonize_uhwi (remainder, dividend_prec);
}
return quotient_len;
}
Jakub
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH] Fix wide_int unsigned division (PR tree-optimization/69546, take 2)
2016-02-01 20:25 ` Jakub Jelinek
@ 2016-02-02 15:49 ` Richard Sandiford
0 siblings, 0 replies; 6+ messages in thread
From: Richard Sandiford @ 2016-02-02 15:49 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Mike Stump, Richard Biener, gcc-patches, nd
Jakub Jelinek <jakub@redhat.com> writes:
> On Sat, Jan 30, 2016 at 02:04:45PM +0000, Richard Sandiford wrote:
>> Not sure what to call it. Maybe canonize_uhwi? Like canonize, except
>> that it takes a uhwi instead of a length.
>>
>> > Can that be done as a follow-up? Certainly it would need
>> > to take the uhwi to store, pointer to the array of hwis, and precision.
>>
>> Yeah, guess it can wait.
>
> So like this?
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
>
> 2016-02-01 Jakub Jelinek <jakub@redhat.com>
>
> * wide-int.cc (canonize_uhwi): New function.
> (wi::divmod_internal): Use it.
>
> --- gcc/wide-int.cc.jj 2016-01-30 19:03:35.000000000 +0100
> +++ gcc/wide-int.cc 2016-02-01 12:28:23.501519292 +0100
> @@ -118,6 +118,20 @@ canonize (HOST_WIDE_INT *val, unsigned i
> return 1;
> }
>
> +/* VAL[0] is unsigned result of operation. Canonize it by adding
> + another 0 block if needed, and return number of blocks needed. */
> +
> +static inline unsigned int
> +canonize_uhwi (HOST_WIDE_INT *val, unsigned int precision)
s/is unsigned result of operation/is the unsigned result of an operation/
LGTM otherwise, thanks.
Richard
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2016-02-02 15:49 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-01-29 14:20 [PATCH] Fix wide_int unsigned division (PR tree-optimization/69546) Jakub Jelinek
2016-01-30 12:31 ` Richard Sandiford
2016-01-30 13:15 ` [PATCH] Fix wide_int unsigned division (PR tree-optimization/69546, take 2) Jakub Jelinek
2016-01-30 14:04 ` Richard Sandiford
2016-02-01 20:25 ` Jakub Jelinek
2016-02-02 15:49 ` Richard Sandiford
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).