This is a summary of discussions relative to the merge request created by
Christopher Bazley (chris.bazley) <[email protected]> titled
Handle divisor bigger than dividend in can_div_away_from_zero_p
since its creation.
Description: PR middle-end/125767
When the magnitude of the divisor is known to be bigger
than that of the dividend, the output quotient should be 1
when divisor and dividend have the same sign or -1
when they have opposite signs.
Previously, can_div_away_from_zero_p was overreliant on
can_div_trunc_p: if can_div_trunc_p returned a failure
indication then can_div_away_from_zero_p did likewise.
This matters because can_div_away_from_zero_p is commonly
used to answer questions such as "How many registers does
this value occupy?" If the register has a scalable vector
type, then the answer should be 1 if the number of bits
occupied by the value is known to be not greater than
the minimum number of bits in the vector type (as well as
if the number of bits occupied by the value is known to be
smaller). Previously, can_div_away_from_zero_p had to be
used with care to avoid wrongly concluding that a value of
type V16QI would not fit in a register of type VNx16QI.
That could cause selection of inefficient instruction
sequences or even an ICE in cases where V8QI in VNx16QI
behaved as expected.
Because polynomial division truncated toward zero can
fail to produce a constant quotient in cases where
polynomial division rounded away from zero can produce a
constant quotient, it is not sufficient for the
implementation of can_div_away_from_zero_p to simply adjust
the quotient produced by can_div_trunc_p.
can_div_trunc_p requires |b * Q| <= |a| whereas
can_div_away_from_zero_p requires |b * Q| >= |a|. The
latter can be proven in cases where the former cannot.
For example, when a = 16 + 0i and b = 16 + 16i, |b * Q|
cannot be smaller than |a| unless Q = 0, which would
violate a common requirement that |a - b * Q| < |b|
(because |a| >= 16 and |b| >= 16). In contrast, |b * Q|
is bigger than |a| if Q > 1 or i > 0. Crucially, it's
impossible to know the value of i at compile time, so
can_div_trunc_p must conservatively return false.
Another way of looking at it is:
Q = (16 + 0i) / (16 + 16i)
= 16 / (16 + 16i)
= 1 / (1 + i)
which is not "some constant Q" that these functions must
find in order to return true; however, we can be sure that
whatever the unknowable value of 1 / (1 + i) is, it lies
within the range 0 < Q <= 1. We cannot know whether that
answer should be truncated to zero, but we can know that
it should be rounded to one.
gcc/ChangeLog:
* poly-int.h (can_div_away_from_zero_p):
Exit early if |a| <= |b| instead of calling
can_div_trunc_p and returning false if it
returned false.
gcc/testsuite/ChangeLog:
* gcc.dg/plugin/poly-int-tests.h: New test cases.
CC: [email protected], [email protected], [email protected]
The full and up to date discussion can be found at
https://forge.sourceware.org/gcc/gcc-TEST/pulls/176
The merge request has been closed without being merged directly on the forge
repository.
On 2026-06-13 08:22:58+00:00, Richard Sandiford (rsandifo)
<[email protected]> requested changes to the code:
How did you test this? When I tried bootstrapping with it locally, I got:
```
In file included from .../gcc/coretypes.h:491,
from .../gcc/emit-rtl.cc:36:
.../gcc/poly-int.h: In instantiation of ‘typename if_nonpoly<Cb, bool>::type
maybe_le(const poly_int<N, C>&, const Cb&) [with unsigned int N = 1; Ca = long
unsigned int; Cb = int; typename if_nonpoly<Cb, bool>::type = bool]’:
.../gcc/poly-int.h:2433:8: required from ‘typename if_nonpoly<Cq, bool>::type
can_div_away_from_zero_p(const poly_int<N, C>&, const poly_int<N, Cb>&, Cq*)
[with unsigned int N = 1; Ca = long unsigned int; Cb = long unsigned int; Cq =
unsigned int; typename if_nonpoly<Cq, bool>::type = bool]’
1351 | #define known_gt(A, B) (!maybe_le (A, B))
| ~~~~~~~~~^~~~~~
.../gcc/emit-rtl.cc:1611:37: required from here
1611 | if (!can_div_away_from_zero_p (msize, regsize, &mregs)
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
.../gcc/poly-int.h:1275:22: error: comparison of integer expressions of
different signedness: ‘const long unsigned int’ and ‘const int’
[-Werror=sign-compare]
1275 | return a.coeffs[0] <= b;
| ~~~~~~~~~~~~^~~~
```
The suggestion below includes a snippet that uses `POLY_INT_TYPE` to avoid
that.
> +++ gcc/testsuite/gcc.dg/plugin/poly-int-tests.h
> @@ -2161,6 +2161,14 @@ test_can_div_away_from_zero_p ()
> ph::make (4, 5, 6),
> &const_quot));
> ASSERT_EQ (const_quot, C (0));
> + ASSERT_TRUE (can_div_away_from_zero_p (ph::make (16, 0, 0),
It would be good to test the third coefficient for something other than 0, at
least in some of the tests.
The way the tests work is that the function is instantiated for N==1, N==2, and
N==3. Testing something in the third coefficient would leave the N==2 case
unaffected, i.e. it would still be `[16, 0] / [16, 16]`.
> +++ gcc/poly-int.h
> @@ -2423,0 +2450,4 @@
> + (1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
> + (2) |7| <= |-9| OR |-7| <= |9|
> + (3) |-2| < |-9| OR |2| < |9| */
> + if ((known_lt (a, 0) && known_le (-a, b))
Negating a negative value could lead to signed overflow at the extremes. Also,
the `known_*` conditions aren't trivial, especially for wide-int-based types,
so it would be better not to repeat them if possible.
How about replacing these two blocks with:
```
/* If both a and b have fixed signs, test 0 < |a| <= |b|. (2) is then
satisfied with |Q| == 1. Choose Q as 1 or -1 such that a and b * Q
have the same sign. Together, these two conditions guarantee that
|b * Q - a| = |b * Q| - |a|. Then:
|r| = |a - b * Q|
= |b * Q - a|
= |b * Q| - |a|
= |b| - |a|
< |b| using 0 < |a| above
Only negate values that are known to be positive, to avoid signed
overflow. */
if (known_lt (a, POLY_INT_TYPE (Ca) (0)))
{
if (known_le (b, a))
{
*quotient = 1;
return true;
}
if (known_gt (b, POLY_INT_TYPE (Cb) (0)) && known_le (-b, a))
{
*quotient = -1;
return true;
}
}
else if (known_gt (a, POLY_INT_TYPE (Ca) (0)))
{
if (known_ge (b, a))
{
*quotient = 1;
return true;
}
if (known_lt (b, POLY_INT_TYPE (Cb) (0)) && known_le (b, -a))
{
*quotient = -1;
return true;
}
}
```
I have a feeling there's a more elegant way to write it, but…
> +++ gcc/poly-int.h
> @@ -2423,0 +2450,4 @@
> + (1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
> + (2) |7| <= |-9| OR |-7| <= |9|
> + (3) |-2| < |-9| OR |2| < |9| */
> + if ((known_lt (a, 0) && known_le (-a, b))
@rsandifo wrote in
https://forge.sourceware.org/gcc/gcc-TEST/pulls/176#issuecomment-6316:
> Negating a negative value could lead to signed overflow at the extremes.
Hi Richard, thanks for your review.
I was aware of this issue when I wrote the first version of this patch, and
initially followed the same practice as you (only negate positive numbers).
e.g., this code was part of my initial version:
```
/* If |a| <= |b| and 'a' and 'b' have opposite signs then Q = -1 satisfies the
constraints of this function, which simplify to
(1) r = a - b * Q
r = a + b
(2) |a| <= |-b|
|a| <= |b|
(3) |a + b| < |b|
e.g., a = 7, b = -9 OR a = -7, b = 9
(1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
(2) |7| <= |-9| OR |-7| <= |9|
(3) |-2| < |-9| OR |2| < |9|
Avoid negating negative numbers to avoid 2's complement overflow.
*/
if ((known_gt (a, 0) && known_ge (-a, b))
|| (known_gt (b, 0) && known_ge (a, -b)))
{
*quotient = -1;
return true;
}
```
I gave up on that approach because it did not work for unsigned coefficients.
e.g.
```
unsigned int a = 2, b = 3;
known_gt (a, 0) is true because 2u > 0.
known_ge (-a, b) is true because UINT_MAX - a + 1u == UINT_MAX - 1u and
UINT_MAX - 1u >= 3u.
```
I considered using type traits to check the signedness of Ca and Cb, but then I
started to think that my concern about overflow was outweighed by the
complexity of avoiding it (and I wasn't sure that the overloaded - operator had
the danger I was concerned about anyway).
How have you solved that issue in your version?
> +++ gcc/poly-int.h
> @@ -2423,0 +2450,4 @@
> + (1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
> + (2) |7| <= |-9| OR |-7| <= |9|
> + (3) |-2| < |-9| OR |2| < |9| */
> + if ((known_lt (a, 0) && known_le (-a, b))
In my code, `(known_lt (a, 0) && known_le (-a, b)` implies
```
a < 0
b > 0
|a| <= b
```
In your proposed replacement, the equivalent check is
```
if (known_lt (a, POLY_INT_TYPE (Ca) (0)))
...
if (known_gt (b, POLY_INT_TYPE (Cb) (0)) && known_le (-b, a))
```
which implies
```
a < 0
b > 0
-b <= a
0 <= a + b
-a <= b
|a| <= b
```
I think it's equivalent, but it needs one more comparison. The other difference
is that it does not negate a negative number.
> +++ gcc/poly-int.h
> @@ -2423,0 +2450,4 @@
> + (1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
> + (2) |7| <= |-9| OR |-7| <= |9|
> + (3) |-2| < |-9| OR |2| < |9| */
> + if ((known_lt (a, 0) && known_le (-a, b))
@rsandifo wrote in
https://forge.sourceware.org/gcc/gcc-TEST/pulls/176/files#issuecomment-6316:
> Negating a negative value could lead to signed overflow at the extremes.
> Also, the `known_*` conditions aren't trivial, especially for wide-int-based
> types, so it would be better not to repeat them if possible.
>
> How about replacing these two blocks with:
>
> ```text
> /* If both a and b have fixed signs, test 0 < |a| <= |b|. (2) is then
> satisfied with |Q| == 1. Choose Q as 1 or -1 such that a and b * Q
> have the same sign. Together, these two conditions guarantee that
> |b * Q - a| = |b * Q| - |a|. Then:
>
> |r| = |a - b * Q|
> = |b * Q - a|
> = |b * Q| - |a|
> = |b| - |a|
> < |b| using 0 < |a| above
>
> Only negate values that are known to be positive, to avoid signed
> overflow. */
> if (known_lt (a, POLY_INT_TYPE (Ca) (0)))
> {
> if (known_le (b, a))
> {
> *quotient = 1;
> return true;
> }
> if (known_gt (b, POLY_INT_TYPE (Cb) (0)) && known_le (-b, a))
> {
> *quotient = -1;
> return true;
> }
> }
> else if (known_gt (a, POLY_INT_TYPE (Ca) (0)))
> {
> if (known_ge (b, a))
> {
> *quotient = 1;
> return true;
> }
> if (known_lt (b, POLY_INT_TYPE (Cb) (0)) && known_le (b, -a))
> {
> *quotient = -1;
> return true;
> }
> }
> ```
In my code, `(known_gt (a, 0) && known_lt (b, 0) && known_le (a, -b))`
implies
```
a > 0
b < 0
a <= -b
a <= |b|
```
In your proposed replacement, the equivalent check is
```
if (known_gt (a, POLY_INT_TYPE (Ca) (0)))
...
if (known_lt (b, POLY_INT_TYPE (Cb) (0)) && known_le (b, -a))
```
which implies
```
a > 0
b < 0
b <= -a
a + b <= 0
a <= -b
a <= |b|
```
So I think they are equivalent too.
> +++ gcc/poly-int.h
> @@ -2423,0 +2450,4 @@
> + (1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
> + (2) |7| <= |-9| OR |-7| <= |9|
> + (3) |-2| < |-9| OR |2| < |9| */
> + if ((known_lt (a, 0) && known_le (-a, b))
@chris.bazley wrote in
https://forge.sourceware.org/gcc/gcc-TEST/pulls/176#issuecomment-6325:
> @rsandifo wrote in #176 (comment):
>
> > Negating a negative value could lead to signed overflow at the extremes.
>
> Hi Richard, thanks for your review.
>
> I was aware of this issue when I wrote the first version of this patch, and
> initially followed the same practice as you (only negate positive numbers).
> e.g., this code was part of my initial version:
>
> ```text
> /* If |a| <= |b| and 'a' and 'b' have opposite signs then Q = -1 satisfies
> the
> constraints of this function, which simplify to
> (1) r = a - b * Q
> r = a + b
> (2) |a| <= |-b|
> |a| <= |b|
> (3) |a + b| < |b|
> e.g., a = 7, b = -9 OR a = -7, b = 9
> (1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
> (2) |7| <= |-9| OR |-7| <= |9|
> (3) |-2| < |-9| OR |2| < |9|
> Avoid negating negative numbers to avoid 2's complement overflow.
> */
> if ((known_gt (a, 0) && known_ge (-a, b))
> || (known_gt (b, 0) && known_ge (a, -b)))
> {
> *quotient = -1;
> return true;
> }
> ```
>
> I gave up on that approach because it did not work for unsigned coefficients.
> e.g.
>
> ```text
> unsigned int a = 2, b = 3;
> known_gt (a, 0) is true because 2u > 0.
> known_ge (-a, b) is true because UINT_MAX - a + 1u == UINT_MAX - 1u and
> UINT_MAX - 1u >= 3u.
> ```
>
> I considered using type traits to check the signedness of Ca and Cb, but then
> I started to think that my concern about overflow was outweighed by the
> complexity of avoiding it (and I wasn't sure that the overloaded - operator
> had the danger I was concerned about anyway).
>
> How have you solved that issue in your version?
Would you prefer !std::is_unsigned<Ca>::value or known_lt (-a, a) for this
purpose? I assume that the former is cheaper.
> +++ gcc/poly-int.h
> @@ -2423,0 +2450,4 @@
> + (1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
> + (2) |7| <= |-9| OR |-7| <= |9|
> + (3) |-2| < |-9| OR |2| < |9| */
> + if ((known_lt (a, 0) && known_le (-a, b))
@chris.bazley wrote in
https://forge.sourceware.org/gcc/gcc-TEST/pulls/176#issuecomment-6343:
> @chris.bazley wrote in #176 (comment):
>
> > @rsandifo wrote in #176 (comment):
> > > Negating a negative value could lead to signed overflow at the extremes.
> >
> >
> > Hi Richard, thanks for your review.
> > I was aware of this issue when I wrote the first version of this patch, and
> > initially followed the same practice as you (only negate positive numbers).
> > e.g., this code was part of my initial version:
> > ```text
> > /* If |a| <= |b| and 'a' and 'b' have opposite signs then Q = -1
> > satisfies the
> > constraints of this function, which simplify to
> > (1) r = a - b * Q
> > r = a + b
> > (2) |a| <= |-b|
> > |a| <= |b|
> > (3) |a + b| < |b|
> > e.g., a = 7, b = -9 OR a = -7, b = 9
> > (1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
> > (2) |7| <= |-9| OR |-7| <= |9|
> > (3) |-2| < |-9| OR |2| < |9|
> > Avoid negating negative numbers to avoid 2's complement overflow.
> > */
> > if ((known_gt (a, 0) && known_ge (-a, b))
> > || (known_gt (b, 0) && known_ge (a, -b)))
> > {
> > *quotient = -1;
> > return true;
> > }
> > ```
> >
> > I gave up on that approach because it did not work for unsigned
> > coefficients. e.g.
> > ```text
> > unsigned int a = 2, b = 3;
> > known_gt (a, 0) is true because 2u > 0.
> > known_ge (-a, b) is true because UINT_MAX - a + 1u == UINT_MAX - 1u and
> > UINT_MAX - 1u >= 3u.
> > ```
> >
> > I considered using type traits to check the signedness of Ca and Cb, but
> > then I started to think that my concern about overflow was outweighed by
> > the complexity of avoiding it (and I wasn't sure that the overloaded -
> > operator had the danger I was concerned about anyway).
> > How have you solved that issue in your version?
>
> Would you prefer !std::is_unsigned::value or known_lt (-a, a) for this
> purpose? I assume that the former is cheaper.
Scratch that, I think wi::neg() is the way.
> +++ gcc/poly-int.h
> @@ -2423,0 +2450,4 @@
> + (1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
> + (2) |7| <= |-9| OR |-7| <= |9|
> + (3) |-2| < |-9| OR |2| < |9| */
> + if ((known_lt (a, 0) && known_le (-a, b))
Implementing support for mixed-signedness coefficients is much harder than I
first realised. Even an expression such as known_le (b, a) can give the wrong
result if the type of b is signed but the type of a is unsigned, or vice versa.
I am wondering why the fundamental comparison operations aren't defined like
this:
template<unsigned int N, typename Ca, typename Cb>
inline typename if_nonpoly<Cb, bool>::type
maybe_lt (const poly_int<N, Ca> &a, const Cb &b)
{
typedef POLY_CAST (Ca, Cb) NCa;
typedef POLY_CAST (Cb, Ca) NCb;
if (N >= 2)
for (unsigned int i = 1; i < N; i++)
if (NCa (a.coeffs[i]) < NCa (0))
return true;
return NCa (a.coeffs[0]) < NCb (b);
}
> +++ gcc/poly-int.h
> @@ -2423,0 +2450,4 @@
> + (1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
> + (2) |7| <= |-9| OR |-7| <= |9|
> + (3) |-2| < |-9| OR |2| < |9| */
> + if ((known_lt (a, 0) && known_le (-a, b))
I now have an upgrade for maybe_lt and friends that I am happy with, but there
is still the issue that can_div_away_from_zero_p can fall back to using
can_div_trunc_p, which does not handle mixed signed/unsigned types.
> +++ gcc/poly-int.h
> @@ -2423,0 +2450,4 @@
> + (1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
> + (2) |7| <= |-9| OR |-7| <= |9|
> + (3) |-2| < |-9| OR |2| < |9| */
> + if ((known_lt (a, 0) && known_le (-a, b))
@chris.bazley wrote in
https://forge.sourceware.org/gcc/gcc-TEST/pulls/176#issuecomment-6360:
> I now have an upgrade for maybe_lt and friends that I am happy with, but
> there is still the issue that can_div_away_from_zero_p can fall back to using
> can_div_trunc_p, which does not handle mixed signed/unsigned types.
Please see https://forge.sourceware.org/gcc/gcc-TEST/pulls/179 and
https://forge.sourceware.org/gcc/gcc-TEST/pulls/180
> +++ gcc/poly-int.h
> @@ -2423,0 +2450,4 @@
> + (1) r = 7 + -9 = -2 OR r = -7 + 9 = 2
> + (2) |7| <= |-9| OR |-7| <= |9|
> + (3) |-2| < |-9| OR |2| < |9| */
> + if ((known_lt (a, 0) && known_le (-a, b))
I don't have more time to spend on this so I have simply copied and pasted your
code. Here are the scenarios in which I expect it to return the wrong result:
```
-1 / 2u
-1 < 0 // known_lt (a, POLY_INT_TYPE (Ca) (0))
2u <= (unsigned)-1 // known_le (b, a)
return quotient = 1 (should be -1)
1u / -2
1u >= 0u // NOT known_lt (a, POLY_INT_TYPE (Ca) (0))
1u > 0u // known_gt (a, POLY_INT_TYPE (Ca) (0))
(unsigned)-2 >= 1u // known_ge (b, a)
return quotient = 1 (should be -1)
-2 / 1u
-2 < 0 // known_lt (a, POLY_INT_TYPE (Ca) (0))
1u <= (unsigned)-2 // known_le (b, a)
return quotient = 1 (should be -2)
2u / -1
2u >= 0 // NOT known_lt (a, POLY_INT_TYPE (Ca) (0))
2u > 0 // known_gt (a, POLY_INT_TYPE (Ca) (0))
(unsigned)-1 >= 2u // known_ge (b, a)
return quotient = 1 (should be -2)
```
However, I cannot actually see any examples of such inputs in GCC, so maybe it
does not matter.
On 2026-06-18 17:55:04+00:00, Christopher Bazley (chris.bazley)
<[email protected]> commented on the code:
> +++ gcc/poly-int.h
> @@ -2423,0 +2440,4 @@
> + }
> + if (known_gt (b, POLY_INT_TYPE (Cb) (0)))
> + {
> + wi::overflow_type ovf;
I'm not sure you'll like this solution, so I'll also push an alternative.
On 2026-06-30 08:55:08+00:00, Christopher Bazley (chris.bazley)
<[email protected]> commented on the code:
Pushed to upstream/master as 87c2f1ce7ce4b3e1792d4acdc98fc7132c7ab9c7
