https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128580
Bug ID: 128580
Summary: chrec_fold_multiply_poly_poly does not scale the step
for chrecs of nested loops
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-unknown-linux-gnu
The attached testcase stores a[i * k + j] = i in a nest of three loops
over i, k and j, and aborts with -O3 -fno-tree-loop-im -fno-tree-pre:
$ gcc -O3 -fno-tree-loop-im -fno-tree-pre testcase.c && ./a.out
Aborted
Seen with trunk r17-6046-gbccef7957b59 and with GCC 15.2.1.
The access function of a[i * k + j] is computed as
{{0, +, 1}_2, +, 1}_3, that is k + j. It does not depend on i, so loop
interchange swaps the loops over i and k:
Loop_pair<outer:1, inner:2> is interchanged
i * k is a MULT_EXPR of two SSA names defined outside loop 3, and
instantiating it multiplies {0, +, 1}_1 by {0, +, 1}_2.
chrec_fold_multiply_poly_poly handles chrecs of nested loops as
{a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2
{a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2
The chrec of the outer loop is invariant in the inner loop, so it should
scale the step as well: {c*{a, +, b}_1, +, d*{a, +, b}_1}_2. Here the
product comes out as {0, +, 1}_2 (k) instead of {0, +, {0, +, 1}_1}_2
(i * k). With the step multiplied, the access function becomes
{{0, +, {0, +, 1}_1}_2, +, 1}_3 and the testcase passes.
