lower-bitint: Fix up maximum addition/subtraction/multiplication result computations
Checks
Commit Message
Hi!
When debugging PR112750, I've noticed some issues in the computation
of precisions and the following patch attempts to fix those.
The pass uses range_to_prec function, which possibly using ranger returns
minimum precision of some operand in the style that libgcc _BitInt
entrypoints expect, i.e. for operands with unsigned types either the
precision of that type or with help of ranger
wi::min_precision (upper_bound, UNSIGNED) (done both if the types
are really unsigned or even when lower_bound is non-negative), while
for operands with signed types either negated precision of that type or
with help of ranger negated value of maximum of SIGNED min_precisions
of lower and upper bound.
Because _BitInt in C only supports unsigned precisions >= 1 and signed
precisions >= 2, the function also ensures that 0 is never returned (returns
1 instead) and should ensure that -1 is never returned (should return -2).
That is the first bug I found though, for the ranger case it ensured that,
but if an operand would be signed 1-bit precision (that means
non-BITINT_TYPE) operand, it could return -1.
Another thing is that both lower_addsub_overflow and lower_mul_overflow
compute from the prec0 and prec1 of the operands (returned by range_to_prec
with the above value meanings) prec2, which is how many bits of the result
we actually need to compute to know the infinite precision result.
This is then used by arith_overflow function together with prec
(TYPE_PRECISION (type)), type (type of the result), prec0 and prec1 to
compute which range of bits should be tested (if any, or that there is never
an overflow) and with which kind (require those bits to be zero vs.
check if all those bits together all all zeros/ones).
The arith_overflow function has one special case, when
prec0 >= 0 && prec1 >= 0 and operation is not .SUB_OVERFLOW; in that case
we treat prec2 as minimum precision to express any infinite precision
unsigned result (the result is never negative in that case), while
in all other cases prec2 is treated as minimum precision to express
any infinite precision signed result (because the result can be also
negative).
The computations of those values were apparently incorrect for all of
.{ADD,SUB}_OVERFLOW (in that case only if one operand was signed and
the other unsigned) and for .MUL_OVERFLOW it was sometimes too large.
It took me a while to get to the right expression how to compute that,
I've started with writing into the comment the possible results for
different prec0 and prec1 values (used just 8/-8/10/-10 as placeholders
for equal or different absolute values of the 2 precisions and cases
with positive and/or negative signs) and then turned into the attached
test program that actually printed what I was writing to make sure
I didn't make mistakes in it and in the end also verified the computation,
this time for all combinations of 1..14 and -2..-14 precisions.
The UNSIGNED vs. SIGNED in the table is what arith_overflow expects
the prec2 to be (see above mentioned exception).
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
2023-12-01 Jakub Jelinek <jakub@redhat.com>
* gimple-lower-bitint.cc (range_to_prec): Don't return -1 for
signed types.
(bitint_large_huge::lower_addsub_overflow): Fix up computation of
prec2.
(bitint_large_huge::lower_mul_overflow): Likewise.
Jakub
int
main ()
{
int p[] = {
1, 0, 0x1,
2, 0, 0x3,
3, 0, 0x7,
4, 0, 0xf,
5, 0, 0x1f,
6, 0, 0x3f,
7, 0, 0x7f,
8, 0, 0xff,
9, 0, 0x1ff,
10, 0, 0x3ff,
11, 0, 0x7ff,
12, 0, 0xfff,
13, 0, 0x1fff,
14, 0, 0x3fff,
-2, -0x2, 0x1,
-3, -0x4, 0x3,
-4, -0x8, 0x7,
-5, -0x10, 0xf,
-6, -0x20, 0x1f,
-7, -0x40, 0x3f,
-8, -0x80, 0x7f,
-9, -0x100, 0xff,
-10, -0x200, 0x1ff,
-11, -0x400, 0x3ff,
-12, -0x800, 0x7ff,
-13, -0x1000, 0xfff,
-14, -0x2000, 0x1fff
};
for (int op = 0; op <= 2; op++)
for (int a = 0; a < 27; ++a)
for (int b = 0; b < 27; ++b)
{
int mina = p[3 * a + 1];
int maxa = p[3 * a + 2];
int minb = p[3 * b + 1];
int maxb = p[3 * b + 2];
int prec0 = p[3 * a];
int prec1 = p[3 * b];
long long int min, max;
if (op == 0)
{
max = min = mina + minb;
if (min > maxa + minb) min = maxa + minb;
if (min > mina + maxb) min = mina + maxb;
if (min > maxa + maxb) min = maxa + maxb;
if (max < maxa + minb) max = maxa + minb;
if (max < mina + maxb) max = mina + maxb;
if (max < maxa + maxb) max = maxa + maxb;
}
else if (op == 1)
{
max = min = mina - minb;
if (min > maxa - minb) min = maxa - minb;
if (min > mina - maxb) min = mina - maxb;
if (min > maxa - maxb) min = maxa - maxb;
if (max < maxa - minb) max = maxa - minb;
if (max < mina - maxb) max = mina - maxb;
if (max < maxa - maxb) max = maxa - maxb;
}
else
{
max = min = ((long long) mina) * minb;
if (min > ((long long) maxa) * minb) min = ((long long) maxa) * minb;
if (min > ((long long) mina) * maxb) min = ((long long) mina) * maxb;
if (min > ((long long) maxa) * maxb) min = ((long long) maxa) * maxb;
if (max < ((long long) maxa) * minb) max = ((long long) maxa) * minb;
if (max < ((long long) mina) * maxb) max = ((long long) mina) * maxb;
if (max < ((long long) maxa) * maxb) max = ((long long) maxa) * maxb;
}
int uns = op != 1 && prec0 > 0 && prec1 > 0;
int prec;
if (uns)
{
if (min != 0)
__builtin_abort ();
prec = 64 - __builtin_clzll (max);
}
else
{
prec = 64 - __builtin_clrsbll (min);
if (prec < 64 - __builtin_clrsbll (max))
prec = 64 - __builtin_clrsbll (max);
}
char buf[32];
if (min == 0)
__builtin_sprintf (buf, "0");
else
__builtin_sprintf (buf, "-0x%llx", -min);
__builtin_printf (" %3d %c %3d [%s,0x%llx] %2d %sSIGNED\n",
prec0, op == 0 ? '+' : op == 1 ? '-' : '*', prec1, buf,
max, prec, uns ? "UN" : "");
#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
int prec2 = MAX (prec0 < 0 ? -prec0 : prec0, prec1 < 0 ? -prec1 : prec1);
if (op != 2)
prec2 = (((prec0 < 0) == (prec1 < 0)
|| (prec0 < 0 ? (prec2 == -prec0 && prec2 != prec1)
: (prec2 == -prec1 && prec2 != prec0)))
? prec2 + 1 : prec2 + 2);
if (op == 2)
{
prec2 = (prec0 < 0 ? -prec0 : prec0) + (prec1 < 0 ? -prec1 : prec1);
if (prec0 == 1 || prec1 == 1)
--prec2;
}
if (prec2 != prec)
__builtin_abort ();
}
}
Comments
On Fri, 1 Dec 2023, Jakub Jelinek wrote:
> Hi!
>
> When debugging PR112750, I've noticed some issues in the computation
> of precisions and the following patch attempts to fix those.
>
> The pass uses range_to_prec function, which possibly using ranger returns
> minimum precision of some operand in the style that libgcc _BitInt
> entrypoints expect, i.e. for operands with unsigned types either the
> precision of that type or with help of ranger
> wi::min_precision (upper_bound, UNSIGNED) (done both if the types
> are really unsigned or even when lower_bound is non-negative), while
> for operands with signed types either negated precision of that type or
> with help of ranger negated value of maximum of SIGNED min_precisions
> of lower and upper bound.
> Because _BitInt in C only supports unsigned precisions >= 1 and signed
> precisions >= 2, the function also ensures that 0 is never returned (returns
> 1 instead) and should ensure that -1 is never returned (should return -2).
> That is the first bug I found though, for the ranger case it ensured that,
> but if an operand would be signed 1-bit precision (that means
> non-BITINT_TYPE) operand, it could return -1.
>
> Another thing is that both lower_addsub_overflow and lower_mul_overflow
> compute from the prec0 and prec1 of the operands (returned by range_to_prec
> with the above value meanings) prec2, which is how many bits of the result
> we actually need to compute to know the infinite precision result.
> This is then used by arith_overflow function together with prec
> (TYPE_PRECISION (type)), type (type of the result), prec0 and prec1 to
> compute which range of bits should be tested (if any, or that there is never
> an overflow) and with which kind (require those bits to be zero vs.
> check if all those bits together all all zeros/ones).
> The arith_overflow function has one special case, when
> prec0 >= 0 && prec1 >= 0 and operation is not .SUB_OVERFLOW; in that case
> we treat prec2 as minimum precision to express any infinite precision
> unsigned result (the result is never negative in that case), while
> in all other cases prec2 is treated as minimum precision to express
> any infinite precision signed result (because the result can be also
> negative).
> The computations of those values were apparently incorrect for all of
> .{ADD,SUB}_OVERFLOW (in that case only if one operand was signed and
> the other unsigned) and for .MUL_OVERFLOW it was sometimes too large.
>
> It took me a while to get to the right expression how to compute that,
> I've started with writing into the comment the possible results for
> different prec0 and prec1 values (used just 8/-8/10/-10 as placeholders
> for equal or different absolute values of the 2 precisions and cases
> with positive and/or negative signs) and then turned into the attached
> test program that actually printed what I was writing to make sure
> I didn't make mistakes in it and in the end also verified the computation,
> this time for all combinations of 1..14 and -2..-14 precisions.
> The UNSIGNED vs. SIGNED in the table is what arith_overflow expects
> the prec2 to be (see above mentioned exception).
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
OK.
Richard.
> 2023-12-01 Jakub Jelinek <jakub@redhat.com>
>
> * gimple-lower-bitint.cc (range_to_prec): Don't return -1 for
> signed types.
> (bitint_large_huge::lower_addsub_overflow): Fix up computation of
> prec2.
> (bitint_large_huge::lower_mul_overflow): Likewise.
>
> --- gcc/gimple-lower-bitint.cc.jj 2023-11-30 12:46:34.715093396 +0100
> +++ gcc/gimple-lower-bitint.cc 2023-11-30 17:24:59.828026693 +0100
> @@ -1963,7 +1963,7 @@ range_to_prec (tree op, gimple *stmt)
> if (TYPE_UNSIGNED (type))
> return prec;
> else
> - return -prec;
> + return MIN ((int) -prec, -2);
> }
>
> if (!TYPE_UNSIGNED (TREE_TYPE (op)))
> @@ -3792,11 +3792,45 @@ bitint_large_huge::lower_addsub_overflow
> int prec = TYPE_PRECISION (type);
> int prec0 = range_to_prec (arg0, stmt);
> int prec1 = range_to_prec (arg1, stmt);
> - int prec2 = ((prec0 < 0) == (prec1 < 0)
> - ? MAX (prec0 < 0 ? -prec0 : prec0,
> - prec1 < 0 ? -prec1 : prec1) + 1
> - : MAX (prec0 < 0 ? -prec0 : prec0 + 1,
> - prec1 < 0 ? -prec1 : prec1 + 1) + 1);
> + /* If PREC0 >= 0 && PREC1 >= 0 and CODE is not MINUS_EXPR, PREC2 is
> + the be minimum unsigned precision of any possible operation's
> + result, otherwise it is minimum signed precision.
> + Some examples:
> + If PREC0 or PREC1 is 8, it means that argument is [0, 0xff],
> + if PREC0 or PREC1 is 10, it means that argument is [0, 0x3ff],
> + if PREC0 or PREC1 is -8, it means that argument is [-0x80, 0x7f],
> + if PREC0 or PREC1 is -10, it means that argument is [-0x200, 0x1ff].
> + PREC0 CODE PREC1 RESULT PREC2 SIGNED vs. UNSIGNED
> + 8 + 8 [0, 0x1fe] 9 UNSIGNED
> + 8 + 10 [0, 0x4fe] 11 UNSIGNED
> + -8 + -8 [-0x100, 0xfe] 9 SIGNED
> + -8 + -10 [-0x280, 0x27e] 11 SIGNED
> + 8 + -8 [-0x80, 0x17e] 10 SIGNED
> + 8 + -10 [-0x200, 0x2fe] 11 SIGNED
> + 10 + -8 [-0x80, 0x47e] 12 SIGNED
> + 8 - 8 [-0xff, 0xff] 9 SIGNED
> + 8 - 10 [-0x3ff, 0xff] 11 SIGNED
> + 10 - 8 [-0xff, 0x3ff] 11 SIGNED
> + -8 - -8 [-0xff, 0xff] 9 SIGNED
> + -8 - -10 [-0x27f, 0x27f] 11 SIGNED
> + -10 - -8 [-0x27f, 0x27f] 11 SIGNED
> + 8 - -8 [-0x7f, 0x17f] 10 SIGNED
> + 8 - -10 [-0x1ff, 0x2ff] 11 SIGNED
> + 10 - -8 [-0x7f, 0x47f] 12 SIGNED
> + -8 - 8 [-0x17f, 0x7f] 10 SIGNED
> + -8 - 10 [-0x47f, 0x7f] 12 SIGNED
> + -10 - 8 [-0x2ff, 0x1ff] 11 SIGNED */
> + int prec2 = MAX (prec0 < 0 ? -prec0 : prec0,
> + prec1 < 0 ? -prec1 : prec1);
> + /* If operands are either both signed or both unsigned,
> + we need just one additional bit. */
> + prec2 = (((prec0 < 0) == (prec1 < 0)
> + /* If one operand is signed and one unsigned and
> + the signed one has larger precision, we need
> + just one extra bit, otherwise two. */
> + || (prec0 < 0 ? (prec2 == -prec0 && prec2 != prec1)
> + : (prec2 == -prec1 && prec2 != prec0)))
> + ? prec2 + 1 : prec2 + 2);
> int prec3 = MAX (prec0 < 0 ? -prec0 : prec0,
> prec1 < 0 ? -prec1 : prec1);
> prec3 = MAX (prec3, prec);
> @@ -4201,8 +4235,9 @@ bitint_large_huge::lower_mul_overflow (t
> arg0 = handle_operand_addr (arg0, stmt, NULL, &prec0);
> arg1 = handle_operand_addr (arg1, stmt, NULL, &prec1);
> int prec2 = ((prec0 < 0 ? -prec0 : prec0)
> - + (prec1 < 0 ? -prec1 : prec1)
> - + ((prec0 < 0) != (prec1 < 0)));
> + + (prec1 < 0 ? -prec1 : prec1));
> + if (prec0 == 1 || prec1 == 1)
> + --prec2;
> tree var = NULL_TREE;
> tree orig_obj = obj;
> bool force_var = false;
>
> Jakub
>
@@ -1963,7 +1963,7 @@ range_to_prec (tree op, gimple *stmt)
if (TYPE_UNSIGNED (type))
return prec;
else
- return -prec;
+ return MIN ((int) -prec, -2);
}
if (!TYPE_UNSIGNED (TREE_TYPE (op)))
@@ -3792,11 +3792,45 @@ bitint_large_huge::lower_addsub_overflow
int prec = TYPE_PRECISION (type);
int prec0 = range_to_prec (arg0, stmt);
int prec1 = range_to_prec (arg1, stmt);
- int prec2 = ((prec0 < 0) == (prec1 < 0)
- ? MAX (prec0 < 0 ? -prec0 : prec0,
- prec1 < 0 ? -prec1 : prec1) + 1
- : MAX (prec0 < 0 ? -prec0 : prec0 + 1,
- prec1 < 0 ? -prec1 : prec1 + 1) + 1);
+ /* If PREC0 >= 0 && PREC1 >= 0 and CODE is not MINUS_EXPR, PREC2 is
+ the be minimum unsigned precision of any possible operation's
+ result, otherwise it is minimum signed precision.
+ Some examples:
+ If PREC0 or PREC1 is 8, it means that argument is [0, 0xff],
+ if PREC0 or PREC1 is 10, it means that argument is [0, 0x3ff],
+ if PREC0 or PREC1 is -8, it means that argument is [-0x80, 0x7f],
+ if PREC0 or PREC1 is -10, it means that argument is [-0x200, 0x1ff].
+ PREC0 CODE PREC1 RESULT PREC2 SIGNED vs. UNSIGNED
+ 8 + 8 [0, 0x1fe] 9 UNSIGNED
+ 8 + 10 [0, 0x4fe] 11 UNSIGNED
+ -8 + -8 [-0x100, 0xfe] 9 SIGNED
+ -8 + -10 [-0x280, 0x27e] 11 SIGNED
+ 8 + -8 [-0x80, 0x17e] 10 SIGNED
+ 8 + -10 [-0x200, 0x2fe] 11 SIGNED
+ 10 + -8 [-0x80, 0x47e] 12 SIGNED
+ 8 - 8 [-0xff, 0xff] 9 SIGNED
+ 8 - 10 [-0x3ff, 0xff] 11 SIGNED
+ 10 - 8 [-0xff, 0x3ff] 11 SIGNED
+ -8 - -8 [-0xff, 0xff] 9 SIGNED
+ -8 - -10 [-0x27f, 0x27f] 11 SIGNED
+ -10 - -8 [-0x27f, 0x27f] 11 SIGNED
+ 8 - -8 [-0x7f, 0x17f] 10 SIGNED
+ 8 - -10 [-0x1ff, 0x2ff] 11 SIGNED
+ 10 - -8 [-0x7f, 0x47f] 12 SIGNED
+ -8 - 8 [-0x17f, 0x7f] 10 SIGNED
+ -8 - 10 [-0x47f, 0x7f] 12 SIGNED
+ -10 - 8 [-0x2ff, 0x1ff] 11 SIGNED */
+ int prec2 = MAX (prec0 < 0 ? -prec0 : prec0,
+ prec1 < 0 ? -prec1 : prec1);
+ /* If operands are either both signed or both unsigned,
+ we need just one additional bit. */
+ prec2 = (((prec0 < 0) == (prec1 < 0)
+ /* If one operand is signed and one unsigned and
+ the signed one has larger precision, we need
+ just one extra bit, otherwise two. */
+ || (prec0 < 0 ? (prec2 == -prec0 && prec2 != prec1)
+ : (prec2 == -prec1 && prec2 != prec0)))
+ ? prec2 + 1 : prec2 + 2);
int prec3 = MAX (prec0 < 0 ? -prec0 : prec0,
prec1 < 0 ? -prec1 : prec1);
prec3 = MAX (prec3, prec);
@@ -4201,8 +4235,9 @@ bitint_large_huge::lower_mul_overflow (t
arg0 = handle_operand_addr (arg0, stmt, NULL, &prec0);
arg1 = handle_operand_addr (arg1, stmt, NULL, &prec1);
int prec2 = ((prec0 < 0 ? -prec0 : prec0)
- + (prec1 < 0 ? -prec1 : prec1)
- + ((prec0 < 0) != (prec1 < 0)));
+ + (prec1 < 0 ? -prec1 : prec1));
+ if (prec0 == 1 || prec1 == 1)
+ --prec2;
tree var = NULL_TREE;
tree orig_obj = obj;
bool force_var = false;