[Bug c++/110396] New: Compile-time hog with -O2 and -O3

[Bug c++/110396] New: Compile-time hog with -O2 and -O3

[luydorarko at vusra dot com]

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

            Bug ID: 110396
           Summary: Compile-time hog with -O2 and -O3
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: luydorarko at vusra dot com
  Target Milestone: ---

Created attachment 55397
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55397&action=edit
Preprocessed file created by `-O2 -save-temps`

Compile time hog behavior can be reproduced with:
```
g++ -O2 tmp.cpp 
```
Also same behavior with `-O3`.

Compiler takes far too long (more than one hour in one case) and was killed
after a while.

Output of `g++ -v`:
```
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-pc-linux-gnu/13.1.1/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /build/gcc/src/gcc/configure
--enable-languages=ada,c,c++,d,fortran,go,lto,objc,obj-c++ --enable-bootstrap
--prefix=/usr --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man
--infodir=/usr/share/info --with-bugurl=https://bugs.archlinux.org/
--with-build-config=bootstrap-lto --with-linker-hash-style=gnu
--with-system-zlib --enable-__cxa_atexit --enable-cet=auto
--enable-checking=release --enable-clocale=gnu --enable-default-pie
--enable-default-ssp --enable-gnu-indirect-function --enable-gnu-unique-object
--enable-libstdcxx-backtrace --enable-link-serialization=1
--enable-linker-build-id --enable-lto --enable-multilib --enable-plugin
--enable-shared --enable-threads=posix --disable-libssp --disable-libstdcxx-pch
--disable-werror
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 13.1.1 20230429 (GCC) 
```

Attachment: a-tmp.ii file created with `g++ -O2 tmp.cpp -save-temps`

[Bug tree-optimization/110396] Compile-time hog with -O2 and -O3

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c++                         |tree-optimization

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
#0  0x00000000012f8732 in hash_table_mod1 (index=5, hash=165) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/hash-table.h:344
#1  hash_table<scev_info_hasher, false, xcallocator>::find_slot_with_hash
(insert=INSERT, hash=165, comparable=<optimized out>, this=0x7ffff7600b28) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/hash-table.h:1051
#2  hash_table<scev_info_hasher, false, xcallocator>::find_slot (insert=INSERT,
value=<optimized out>, this=0x7ffff7600b28) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/hash-table.h:435
#3  find_var_scev_info (instantiated_below=0x7ffff5247b40, var=0x7ffff5159360)
at /home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:358
#4  0x00000000012f9312 in get_scalar_evolution (scalar=0x7ffff5159360,
instantiated_below=0x7ffff5247b40) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:556
#5  analyze_scalar_evolution (loop=0x7ffff514eaf0, var=0x7ffff5159360) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:2020
#6  0x00000000012f8aa7 in interpret_condition_phi
(condition_phi=0x7ffff51fbd00, loop=0x7ffff514eaf0) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1603
#7  analyze_scalar_evolution_1 (loop=0x7ffff514eaf0, var=0x7ffff51f5dc8) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1969
#8  0x00000000012f8b5b in analyze_scalar_evolution_1 (loop=0x7ffff514e960,
var=0x7ffff51f5dc8) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1950
#9  0x00000000012f94e5 in analyze_scalar_evolution (loop=0x7ffff514e960,
var=0x7ffff51f5dc8) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:2031
#10 0x00000000012f8aa7 in interpret_condition_phi
(condition_phi=0x7ffff5209400, loop=0x7ffff514e960) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1603
#11 analyze_scalar_evolution_1 (loop=0x7ffff514e960, var=0x7ffff5207870) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1969
#12 0x00000000012f8b5b in analyze_scalar_evolution_1 (loop=0x7ffff514e7d0,
var=0x7ffff5207870) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1950
#13 0x00000000012f94e5 in analyze_scalar_evolution (loop=0x7ffff514e7d0,
var=0x7ffff5207870) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:2031
#14 0x00000000012f8aa7 in interpret_condition_phi
(condition_phi=0x7ffff520ab00, loop=0x7ffff514e7d0) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1603
#15 analyze_scalar_evolution_1 (loop=0x7ffff514e7d0, var=0x7ffff5161900) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1969
#16 0x00000000012f8b5b in analyze_scalar_evolution_1 (loop=0x7ffff514e640,
var=0x7ffff5161900) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1950
#17 0x00000000012f94e5 in analyze_scalar_evolution (loop=0x7ffff514e640,
var=0x7ffff5161900) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:2031
#18 0x00000000012f8aa7 in interpret_condition_phi
(condition_phi=0x7ffff5172a00, loop=0x7ffff514e640) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1603
#19 analyze_scalar_evolution_1 (loop=0x7ffff514e640, var=0x7ffff5159318) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1969
#20 0x00000000012f8b5b in analyze_scalar_evolution_1 (loop=0x7ffff514e4b0,
var=0x7ffff5159318) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1950
#21 0x00000000012f94e5 in analyze_scalar_evolution (loop=0x7ffff514e4b0,
var=0x7ffff5159318) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:2031
#22 0x00000000012f8aa7 in interpret_condition_phi
(condition_phi=0x7ffff520d300, loop=0x7ffff514e4b0) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1603
#23 analyze_scalar_evolution_1 (loop=0x7ffff514e4b0, var=0x7ffff4d961b0) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1969
#24 0x00000000012f8b5b in analyze_scalar_evolution_1 (loop=0x7ffff514e320,
var=0x7ffff4d961b0) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1950
#25 0x00000000012f94e5 in analyze_scalar_evolution (loop=0x7ffff514e320,
var=0x7ffff4d961b0) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:2031
#26 0x00000000012f8aa7 in interpret_condition_phi
(condition_phi=0x7ffff520d500, loop=0x7ffff514e320) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1603
#27 analyze_scalar_evolution_1 (loop=0x7ffff514e320, var=0x7ffff505fd80) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1969
#28 0x00000000012f8b5b in analyze_scalar_evolution_1 (loop=0x7ffff514e190,
var=0x7ffff505fd80) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1950
#29 0x00000000012f94e5 in analyze_scalar_evolution (loop=0x7ffff514e190,
var=0x7ffff505fd80) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:2031
#30 0x00000000012f8aa7 in interpret_condition_phi
(condition_phi=0x7ffff520d700, loop=0x7ffff514e190) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1603
#31 analyze_scalar_evolution_1 (loop=0x7ffff514e190, var=0x7ffff4b2c048) at
/home/apinski/src/upstream-gcc-git/gcc/gcc/tree-scalar-evolution.cc:1969

[Bug tree-optimization/110396] Compile-time hog with -O2 and -O3

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |DUPLICATE
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This is basically a dup of bug 102253. The problem is there is a known
scalability issues with large loop depth.

How did you generate this testcase, is it from real code or just generated to
try to hit some compile bugs?

*** This bug has been marked as a duplicate of bug 102253 ***

[Bug tree-optimization/110396] Compile-time hog with -O2 and -O3

[luydorarko at vusra dot com]

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

--- Comment #3 from luydorarko at vusra dot com <luydorarko at vusra dot com> ---
(In reply to Andrew Pinski from comment #2)
> This is basically a dup of bug 102253. The problem is there is a known
> scalability issues with large loop depth.
> 
> How did you generate this testcase, is it from real code or just generated
> to try to hit some compile bugs?
> 
> *** This bug has been marked as a duplicate of bug 102253 ***

This is to solve a combinatorics problem: count all 8x8 matrices whose rows and
columns add up to 6. You can see the variable names refer to row and column
indices. 

The tedious loops in the C++ code were all generated by a Python script.

It is part of a bigger exploration for different orders and different row sums
/ column sums. A similar code for smaller row-sums and column-sums compiled and
ran quickly, and all smaller orders run quickly. This was the smallest problem
instance that exposed the time run.