https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128070
Bug ID: 128070
Summary: [compile-time-hog] -O3 cunrolli growth on many small
loops, super-linear compile time and memory
Product: gcc
Version: 17.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: yuki.tanaka at defaultcase dot de
Target Milestone: ---
Created attachment 65916
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65916&action=edit
cunrolli-hog.c
The attached testcase (cunrolli-hog.c) contains N 13x13x13 loop nests (set with
-DN_COPIES=N). At -O3 cunrolli completely unrolls the innermost loops of every
nest; compile time and memory then grow super-linearly with N.
-fdisable-tree-cunrolli brings it back close to -O2.
$ xgcc -v
Using built-in specs.
COLLECT_GCC=./build/gcc/xgcc
Target: arm-none-eabi
Configured with: ../gcc/configure --target=arm-none-eabi
--with-multilib-list=rmprofile --enable-languages=c --without-headers
--with-newlib --enable-checking=release
Thread model: single
Supported LTO compression algorithms: zlib
gcc version 17.0.0 20261020 (experimental) (GCC)
Measured with:
CC="build/gcc/xgcc -B build/gcc -mcpu=cortex-m3 -mthumb"
for n in 25 50 75 100; do
for v in "-O2" "-O3 -fdisable-tree-cunrolli" "-O3"; do
/usr/bin/time -f "%e s / %M KB" -o t.txt timeout 600 $CC $v -DN_COPIES=$n
-S cunrolli-hog.c -o /dev/null 2>/dev/null; rc=$?
echo "N=$n [$v]: rc=$rc $(tail -1 t.txt)"
done
done
Output (wall time / max RSS):
N=25 [-O2]: rc=0 1.23 s / 135180 KB
N=25 [-O3 -fdisable-tree-cunrolli]: rc=0 2.10 s / 188380 KB
N=25 [-O3]: rc=0 12.48 s / 310208 KB
N=50 [-O2]: rc=0 3.74 s / 205956 KB
N=50 [-O3 -fdisable-tree-cunrolli]: rc=0 5.63 s / 292572 KB
N=50 [-O3]: rc=0 61.67 s / 753272 KB
N=75 [-O2]: rc=0 8.27 s / 312188 KB
N=75 [-O3 -fdisable-tree-cunrolli]: rc=0 11.24 s / 443548 KB
N=75 [-O3]: rc=0 152.02 s / 1554664 KB
N=100 [-O2]: rc=0 16.82 s / 442188 KB
N=100 [-O3 -fdisable-tree-cunrolli]: rc=0 21.68 s / 649592 KB
N=100 [-O3]: rc=0 276.78 s / 2586340 KB
At -O3 cunrolli completely unrolls the innermost loop of every nest (150 loops
for N=75, 13 iterations each, see -fdump-tree-cunrolli-details). Each of them
is below max-completely-peeled-insns, but the limit is checked per loop only;
nothing limits the total growth of the function. Most of the compile time is
then spent in "alias stmt walking" (see -ftime-report below), and compile time
and memory grow faster than linearly with N.
-ftime-report at -O3 (N=75, same compiler as above):
Time variable wall GGC
phase setup : 0.01 ( 0%) 3115k ( 0%)
phase parsing : 0.16 ( 0%) 27M ( 3%)
phase opt and generate : 156.81 (100%) 771M ( 96%)
garbage collection : 0.05 ( 0%) 0 ( 0%)
callgraph construction : 0.01 ( 0%) 8343k ( 1%)
callgraph functions expansion : 156.49 (100%) 725M ( 90%)
callgraph ipa passes : 0.19 ( 0%) 3473k ( 0%)
cfg cleanup : 0.04 ( 0%) 3062k ( 0%)
trivially dead code : 0.02 ( 0%) 0 ( 0%)
df scan insns : 0.01 ( 0%) 96 ( 0%)
df reaching defs : 0.09 ( 0%) 0 ( 0%)
df live regs : 0.17 ( 0%) 0 ( 0%)
df live&initialized regs : 0.04 ( 0%) 0 ( 0%)
df use-def / def-use chains : 0.01 ( 0%) 0 ( 0%)
df reg dead/unused notes : 0.10 ( 0%) 857k ( 0%)
register information : 0.02 ( 0%) 0 ( 0%)
alias analysis : 0.10 ( 0%) 6694k ( 1%)
alias stmt walking : 133.90 ( 85%) 24M ( 3%)
register scan : 0.01 ( 0%) 15k ( 0%)
rebuild jump labels : 0.01 ( 0%) 0 ( 0%)
preprocessing : 0.03 ( 0%) 8021k ( 1%)
lexical analysis : 0.01 ( 0%) 0 ( 0%)
parser function body : 0.12 ( 0%) 19M ( 2%)
tree gimplify : 0.06 ( 0%) 10M ( 1%)
tree CFG construction : 0.05 ( 0%) 23M ( 3%)
tree CFG cleanup : 0.09 ( 0%) 348k ( 0%)
tree VRP : 0.41 ( 0%) 2401k ( 0%)
tree Early VRP : 0.04 ( 0%) 387k ( 0%)
tree copy propagation : 0.03 ( 0%) 0 ( 0%)
tree PTA : 0.02 ( 0%) 312 ( 0%)
tree SSA incremental : 0.43 ( 0%) 2748k ( 0%)
tree operand scan : 0.02 ( 0%) 2742k ( 0%)
dominator optimization : 0.39 ( 0%) 2750k ( 0%)
backwards jump threading : 0.38 ( 0%) 54k ( 0%)
tree CCP : 0.09 ( 0%) 243k ( 0%)
tree reassociation : 0.01 ( 0%) 189k ( 0%)
tree PRE : 10.15 ( 6%) 443M ( 55%)
tree FRE : 0.28 ( 0%) 2033k ( 0%)
tree RPO VN : 1.44 ( 1%) 1565k ( 0%)
tree code sinking : 0.01 ( 0%) 84k ( 0%)
tree linearize phis : 0.01 ( 0%) 39k ( 0%)
tree forward propagate : 0.04 ( 0%) 372k ( 0%)
tree conservative DCE : 0.01 ( 0%) 8024 ( 0%)
tree aggressive DCE : 0.01 ( 0%) 110k ( 0%)
tree DSE : 0.07 ( 0%) 64M ( 8%)
tree loop invariant motion : 0.03 ( 0%) 45k ( 0%)
tree loop interchange : 0.11 ( 0%) 5137k ( 1%)
tree canonical iv : 0.01 ( 0%) 116k ( 0%)
scev constant prop : 0.15 ( 0%) 3600 ( 0%)
tree loop unswitching : 0.27 ( 0%) 115k ( 0%)
unroll and jam : 0.09 ( 0%) 2538k ( 0%)
complete unrolling : 0.91 ( 1%) 9239k ( 1%)
tree vectorization : 1.06 ( 1%) 40M ( 5%)
tree slp vectorization : 0.26 ( 0%) 15M ( 2%)
tree loop distribution : 0.33 ( 0%) 9378k ( 1%)
tree iv optimization : 0.64 ( 0%) 29M ( 4%)
predictive commoning : 0.18 ( 0%) 4706k ( 1%)
tree copy headers : 0.17 ( 0%) 301k ( 0%)
tree strlen optimization : 0.13 ( 0%) 1072 ( 0%)
dominance computation : 0.02 ( 0%) 0 ( 0%)
out of ssa : 0.09 ( 0%) 6336 ( 0%)
expand vars : 0.00 ( 0%) 1556k ( 0%)
expand : 0.14 ( 0%) 6289k ( 1%)
lower subreg : 0.02 ( 0%) 917k ( 0%)
forward prop : 0.04 ( 0%) 241k ( 0%)
CSE : 0.19 ( 0%) 623k ( 0%)
dead code elimination : 0.02 ( 0%) 0 ( 0%)
dead store elim1 : 0.02 ( 0%) 1119k ( 0%)
dead store elim2 : 0.02 ( 0%) 1080k ( 0%)
loop init : 0.02 ( 0%) 3834k ( 0%)
loop versioning : 0.13 ( 0%) 0 ( 0%)
loop invariant motion : 0.02 ( 0%) 39k ( 0%)
CPROP : 0.08 ( 0%) 2645k ( 0%)
PRE : 0.39 ( 0%) 40k ( 0%)
CSE 2 : 0.09 ( 0%) 222k ( 0%)
branch prediction : 0.01 ( 0%) 201k ( 0%)
combiner : 0.31 ( 0%) 7234k ( 1%)
late combiner : 0.04 ( 0%) 683k ( 0%)
scheduling : 0.18 ( 0%) 1183k ( 0%)
integrated RA : 0.41 ( 0%) 13M ( 2%)
LRA non-specific : 0.08 ( 0%) 104k ( 0%)
LRA virtuals elimination : 0.01 ( 0%) 28k ( 0%)
LRA reload inheritance : 0.01 ( 0%) 1078k ( 0%)
LRA create live ranges : 0.03 ( 0%) 9384 ( 0%)
LRA hard reg assignment : 0.02 ( 0%) 0 ( 0%)
LRA rematerialization : 0.01 ( 0%) 0 ( 0%)
reload CSE regs : 0.09 ( 0%) 1883k ( 0%)
load CSE after reload : 0.20 ( 0%) 13k ( 0%)
peephole 2 : 0.01 ( 0%) 97k ( 0%)
hard reg cprop : 0.01 ( 0%) 0 ( 0%)
scheduling 2 : 0.08 ( 0%) 115k ( 0%)
machine dep reorg : 0.01 ( 0%) 115k ( 0%)
shorten branches : 0.01 ( 0%) 0 ( 0%)
final : 0.02 ( 0%) 48 ( 0%)
tree loop if-conversion : 0.22 ( 0%) 8838k ( 1%)
access analysis : 0.16 ( 0%) 48 ( 0%)
ext dce : 0.06 ( 0%) 0 ( 0%)
fold mem offsets : 0.01 ( 0%) 0 ( 0%)
rest of compilation : 0.49 ( 0%) 244k ( 0%)
remove unused locals : 0.01 ( 0%) 0 ( 0%)
TOTAL : 156.98 802M
