[Bug tree-optimization/127609] New: [graphite] -floop-nest-optimize expands a 720-store loop into 429496729820 iterations

[bouncy12578 at gmail dot com via Gcc-bugs]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=127609

            Bug ID: 127609
           Summary: [graphite] -floop-nest-optimize expands a 720-store
                    loop into 429496729820 iterations
           Product: gcc
           Version: 17.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: bouncy12578 at gmail dot com
  Target Milestone: ---

Created attachment 65686
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65686&action=edit
preprocessed input

-floop-nest-optimize makes the attached testcase take about 42m50s instead of
microseconds.  

Compiler Explorer: https://godbolt.org/z/8GxEh7bPj


$ gcc -O3 -floop-nest-optimize reduced.c -o g3 && time ./g3
checksum = FFFFFFEC
real    42m49.868s
user    42m49.536s
sys     0m0.029s


Expected: the output above, produced immediately

Actual: correct result, but 429496729820 loop iterations where 720 are needed. 
-fdump-tree-graphite-details shows the ISL scheduler fusing the two innermost
loops (s.f1 x u.f1) into one schedule dimension whose coefficient is 2^32+1:

  schedule: "[{ S_8[i8, i9, i10, i11] -> [(4294967297i10 + i11)] }]"
  [codegen] inserting statement in BB 32: _33 = _11 % 4294967297;

  [scheduler] AST generated by isl:
  for (int c2 = 0; c2 <= 21474836490; c2 += 1)
    if ((c2 + 4294967291) % 4294967297 >= 4294967291)
      S_8(c0, c1, (c2 + 4294967291) / 4294967297, ((c2 + 4294967291) %
4294967297) - 4294967291);

The emitted code keeps an int128_t induction variable starting at 4294967291
and compared against 25769803782 (movabsq $25769803782,%rbx): 21474836491
iterations per instance, each with a movabsq $4294967297,%rdx; call __modti3.


$ gcc -v
Target: x86_64-pc-linux-gnu
Configured with: ../gcc/configure
--prefix=/data/lenovo/compiler-build/gcc/gcc-install --disable-bootstrap
--enable-languages=c,c++ --disable-multilib --with-isl --enable-checking=all :
(reconfigured) ../gcc/configure
--prefix=/data/lenovo/compiler-build/gcc/gcc-install --disable-bootstrap
--enable-languages=c,c++ --disable-multilib --with-isl --enable-checking=all
gcc version 17.0.0 20260923 (experimental) (GCC)        [ISL: isl-0.24-GMP]

Code to Reproduce: gcc -floop-nest-optimize -O3

#include <stdio.h>
#include <stdint.h>

struct S { uint64_t f0; uint8_t f1; };
union U  { struct S f0; uint32_t f1; };

static int8_t   jv;
static int32_t  iv;
static struct S a[6];
static struct S s;
static union U  u;

static int64_t f(void){
    int i, j;

    for (i = 0; i < 1; i++)
    for (iv = 0; iv != -20; iv = (int32_t)((uint64_t)iv - 4)){
        for (jv = 3; jv >= 0; jv -= 1){
            for (s.f1 = 0; s.f1 <= 5; s.f1 += 1){
                for (j = 0; j < 1; j++)
                for (u.f1 = 0; u.f1 <= 5; u.f1 += 1){
                    a[u.f1] = a[0];
                }
            }
        }
    }

    return 0;
}

int main(void){
    f();
    printf("checksum = %X\n", (unsigned)iv);
    return 0;
}