https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128600
Bug ID: 128600
Summary: Wrong code with product of affine evolutions whose
chrec coefficients overflow
Product: gcc
Version: 17.0
Status: UNCONFIRMED
Keywords: wrong-code
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: konstantinos.eleftheriou at vrull dot eu
CC: ptomsich at gcc dot gnu.org
Target Milestone: ---
Target: aarch64-linux-gnu
Created attachment 66128
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=66128&action=edit
testcase
The attached testcase aborts at -O1 and above:
$ gcc -O2 testcase.c && ./a.out
Aborted
It passes at -O0, and with -fwrapv or -fno-aggressive-loop-optimizations.
-fsanitize=undefined reports nothing. Seen with trunk r17-6046-gbccef7957b59
and
with GCC 15.2.1.
For i = 0 and i = 1 the product is -32768 * 32767 = -1073709056 and
32768 * 65535 = 2147450880, both in range. chrec_fold_multiply_poly_poly folds
the product of two affine chrecs in the same loop as
{a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x
Here a = -32768, b = 65536, c = 32767 and d = 32768. The step a*d + b*c + b*d
is
3221159936, which does not fit in int and wraps to -1073807360, and 2*b*d is
2^32, which wraps to 0, so the evolution of the product is computed as
{-1073709056, +, -1073807360(OVF)}_1
This is correct modulo 2^32, but its value for i = 1, -2147516416, is out of
range. The step overflows even though no value of the product does. niter
analysis assumes that the statement does not overflow, so it can only execute
for i = 0. From the -O2 dumps:
Induction variable (int) -1073709056 + -1073807360(OVF) * iteration does not
wrap in statement _5 = _2 * _4;
Statement _5 = _2 * _4;
is executed at most 0(OVF) (bounded by 0) + 1 times in loop 1.
cunrolli then removes the loop after its first iteration:
testcase.c:9:21: optimized: loop with 1 iterations completely unrolled
(header execution count 268435456)
leaving f as
if (n_9(D) > 0)
g = -1073709056;
chrec_fold_plus_poly_poly gives up when a constant step overflows, and
chrec_fold_multiply redoes the product of a chrec and a constant in the
unsigned
type when the step overflows, but chrec_fold_multiply_poly_poly has no such
check.
Proposed fix: when overflow does not wrap and both factors have constant
coefficients, compute the coefficients of the product in a precision wide
enough
that they cannot overflow, and give up if one of them does not fit the type. A
prototype of this fixes the testcase and still folds products whose
coefficients
fit.
