https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128102
Bug ID: 128102
Summary: [12/13/14/15/16/17 Regression] GCC 12+ keeps a small
state-machine loop rolled, 1.85x slower than GCC 11 on
x86-64
Product: gcc
Version: 17.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: yansendao at 126 dot com
Target Milestone: ---
Created attachment 65933
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65933&action=edit
Reduced testcase, self-contained C (no #include)
A reduced testcase (from binascii_a2b_base64() in CPython) is a byte-at-a-time
loop containing a 4-state machine. GCC 11 replicates the loop body through
jump threading, so quad_pos is a compile-time constant on each replicated path
and the switch disappears from the hot loop. GCC 12 and later keep the loop
rolled and execute a 4-way dispatch on every input byte; the loop is then
1.85x slower on x86-64. No PGO or LTO is involved.
Host type: x86_64-pc-linux-gnu
Target type: x86_64-pc-linux-gnu
Build type: x86_64-pc-linux-gnu
GCC version: 17.0.0 20261023 (experimental)
Machine: Hygon C86-4G (OPN:7492H), 2.6 GHz, Linux 5.15.0-25-generic,
binutils 2.38.
Compile command:
gcc -v -save-temps -O3 -o repro b64dec_repro.c
gcc -v output:
Using built-in specs.
COLLECT_GCC=/data/yansendao/tmp/gcc17-install/bin/gcc
COLLECT_LTO_WRAPPER=/data/yansendao/tmp/gcc17-install/libexec/gcc/x86_64-pc-linux-gnu/17.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /data/yansendao/tmp/gcc17-src/configure
--prefix=/data/yansendao/tmp/gcc17-install --disable-bootstrap
--enable-languages=c --disable-multilib --disable-libsanitizer --disable-libssp
--disable-libquadmath --disable-libgomp --disable-libatomic --disable-nls
--disable-werror --with-system-zlib
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 17.0.0 20261023 (experimental) (GCC)
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-O3' '-o' 'repro' '-mtune=generic'
'-march=x86-64' '-dumpdir' 'repro-'
/data/yansendao/tmp/gcc17-install/libexec/gcc/x86_64-pc-linux-gnu/17.0.0/cc1 -E
-quiet -v -imultiarch x86_64-linux-gnu ../b64dec_repro.c -mtune=generic
-march=x86-64 -O3 -fpch-preprocess -o repro-b64dec_repro.i
ignoring nonexistent directory "/usr/local/include/x86_64-linux-gnu"
ignoring nonexistent directory
"/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0/../../../../x86_64-pc-linux-gnu/include"
#include "..." search starts here:
#include <...> search starts here:
/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0/include
/usr/local/include
/data/yansendao/tmp/gcc17-install/include
/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0/include-fixed/x86_64-linux-gnu
/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0/include-fixed
/usr/include/x86_64-linux-gnu
/usr/include
End of search list.
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-O3' '-o' 'repro' '-mtune=generic'
'-march=x86-64' '-dumpdir' 'repro-'
/data/yansendao/tmp/gcc17-install/libexec/gcc/x86_64-pc-linux-gnu/17.0.0/cc1
-fpreprocessed repro-b64dec_repro.i -quiet -dumpdir repro- -dumpbase
b64dec_repro.c -dumpbase-ext .c -mtune=generic -march=x86-64 -O3 -version -o
repro-b64dec_repro.s
GNU C23 (GCC) version 17.0.0 20261023 (experimental) (x86_64-pc-linux-gnu)
compiled by GNU C version 11.4.0, GMP version 6.3.0, MPFR version
4.1.0, MPC version 1.3.1, isl version isl-0.24-GMP
GGC heuristics: --param ggc-min-expand=30 --param ggc-min-heapsize=4096
Compiler executable checksum: e53601b82bc8e4f1360421dd3998966a
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-O3' '-o' 'repro' '-mtune=generic'
'-march=x86-64' '-dumpdir' 'repro-'
as -v --64 -o repro-b64dec_repro.o repro-b64dec_repro.s
GNU assembler version 2.38 (x86_64-linux-gnu) using BFD version (GNU
Binutils for Ubuntu) 2.38
COMPILER_PATH=/data/yansendao/tmp/gcc17-install/libexec/gcc/x86_64-pc-linux-gnu/17.0.0/:/data/yansendao/tmp/gcc17-install/libexec/gcc/x86_64-pc-linux-gnu/17.0.0/:/data/yansendao/tmp/gcc17-install/libexec/gcc/x86_64-pc-linux-gnu/:/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0/:/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/
LIBRARY_PATH=/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0/:/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0/../../../../lib64/:/lib/x86_64-linux-gnu/:/lib/../lib64/:/usr/lib/x86_64-linux-gnu/:/usr/lib/../lib64/:/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0/../../../:/lib/:/usr/lib/
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-O3' '-o' 'repro' '-mtune=generic'
'-march=x86-64' '-dumpdir' 'repro.'
/data/yansendao/tmp/gcc17-install/libexec/gcc/x86_64-pc-linux-gnu/17.0.0/collect2
-plugin
/data/yansendao/tmp/gcc17-install/libexec/gcc/x86_64-pc-linux-gnu/17.0.0/liblto_plugin.so
-plugin-opt=/data/yansendao/tmp/gcc17-install/libexec/gcc/x86_64-pc-linux-gnu/17.0.0/lto-wrapper
-plugin-opt=-fresolution=repro.res -plugin-opt=-pass-through=-lgcc
-plugin-opt=-pass-through=-lgcc_s_asneeded -plugin-opt=-pass-through=-lc
-plugin-opt=-pass-through=-lgcc -plugin-opt=-pass-through=-lgcc_s_asneeded
--eh-frame-hdr -m elf_x86_64 -dynamic-linker /lib64/ld-linux-x86-64.so.2 -o
repro /lib/x86_64-linux-gnu/crt1.o /lib/x86_64-linux-gnu/crti.o
/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0/crtbegin.o
-L/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0
-L/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0/../../../../lib64
-L/lib/x86_64-linux-gnu -L/lib/../lib64 -L/usr/lib/x86_64-linux-gnu
-L/usr/lib/../lib64
-L/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0/../../..
-L/lib -L/usr/lib repro-b64dec_repro.o -lgcc -lgcc_s_asneeded -lc -lgcc
-lgcc_s_asneeded
/data/yansendao/tmp/gcc17-install/lib/gcc/x86_64-pc-linux-gnu/17.0.0/crtend.o
/lib/x86_64-linux-gnu/crtn.o
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-O3' '-o' 'repro' '-mtune=generic'
'-march=x86-64' '-dumpdir' 'repro.'
Compiler output: none (exit status 0, no diagnostics).
Preprocessed source (repro-b64dec_repro.i, from -save-temps):
# 0 "../b64dec_repro.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3
# 0 "<command-line>" 2
# 1 "../b64dec_repro.c"
typedef long unsigned int size_t;
typedef unsigned char u8;
static u8 table_a2b_base64[256];
__attribute__ ((noinline, noclone)) size_t
decode_b64 (const u8 *restrict src, size_t len, u8 *restrict dst)
{
u8 *out = dst;
int quad_pos = 0;
u8 leftchar = 0;
for (size_t i = 0; i < len; i++)
{
u8 this_ch = src[i];
if (this_ch == '=')
continue;
this_ch = table_a2b_base64[this_ch];
if (this_ch >= 64)
continue;
switch (quad_pos)
{
case 0:
quad_pos = 1;
leftchar = this_ch;
break;
case 1:
quad_pos = 2;
*out++ = (u8) ((leftchar << 2) | (this_ch >> 4));
leftchar = this_ch & 0x0f;
break;
case 2:
quad_pos = 3;
*out++ = (u8) ((leftchar << 4) | (this_ch >> 2));
leftchar = this_ch & 0x03;
break;
case 3:
quad_pos = 0;
*out++ = (u8) ((leftchar << 6) | this_ch);
leftchar = 0;
break;
}
}
return (size_t) (out - dst);
}
int
main (void)
{
enum { N = 1 << 22, REPS = 20 };
static u8 src[N], dst[N];
static const char b64[] =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
size_t sum = 0;
for (int i = 0; i < 256; i++)
{
int v = 255;
if (i >= 'A' && i <= 'Z') v = i - 'A';
else if (i >= 'a' && i <= 'z') v = i - 'a' + 26;
else if (i >= '0' && i <= '9') v = i - '0' + 52;
else if (i == '+') v = 62;
else if (i == '/') v = 63;
table_a2b_base64[i] = (u8) v;
}
for (size_t i = 0; i < N; i++)
src[i] = (u8) b64[i & 63];
for (int r = 0; r < REPS; r++)
sum += decode_b64 (src, N, dst);
unsigned long long t0 = __builtin_ia32_rdtsc ();
for (int r = 0; r < REPS; r++)
sum += decode_b64 (src, N, dst);
unsigned long long t1 = __builtin_ia32_rdtsc ();
__builtin_printf ("%llu cycles for %d bytes, %.2f cycles/byte
(sum=%zu)\n",
t1 - t0, REPS * N, (double) (t1 - t0) / (REPS *
(double) N),
sum);
return 0;
}
Measurement (each binary run 3 times, pinned with numactl -m 5 -N 5,
rdtsc-timed, 84 MiB of input per run):
compiler decode_b64 size cmp $0x3d cycles/byte vs GCC
11
GCC 11.4.0 0x2c3 11 2.23
1.00
GCC 12.3.0 (Ubuntu) 0xdb 1 3.93
1.76x
GCC 12.3.0 (vanilla) 0xc3 1 3.72
1.67x
GCC 12.5.0 0xc3 1 3.67
1.65x
GCC 13.4.0 0xdb 1 3.57
1.60x
GCC 17.0.0 (trunk) 0xe3 1 4.12
1.85x
cmp $0x3d is the "this_ch == '='" test, executed once per input byte.
GCC 11 contains 11 copies of it because the loop body has been replicated and
the state variable is constant on every replicated path. GCC 12+ contains
exactly one copy, i.e. one 4-way dispatch per byte.
The same difference is present at -O2: GCC 11 2.83 cycles/byte,
GCC 12.3 4.47, GCC 17 4.07.
The code generated by GCC 12.3.0 (Ubuntu 12.3.0-1ubuntu1~22.04.3), by a
self-built vanilla 12.3.0, 12.5.0 and 13.4.0 is structurally identical to the
GCC 17 output below.
Disassembly
-----------
GCC 11.4.0: the switch is gone from the loop body; the decoder advances
through states 1 -> 2 -> 3 in straight-line code:
12f6: movzbl (%r9,%rdx,1),%ecx
12fb: cmp $0x3d,%cl
12fe: je 1420
1304: movzbl (%r11,%rcx,1),%ecx
1309: cmp $0x3f,%cl
130c: ja 1420
1312: push %rbx
1313: cmp $0x2,%edi ; only checked on entry to the
1316: je 14c8 ; replicated body
131c: cmp $0x3,%edi
131f: je 13e1
1325: cmp $0x1,%edi
1328: je 135c
132a: lea 0x1(%rdx),%rdi
132e: cmp %rdi,%r8
1331: jbe 1445
1337: movzbl 0x1(%r9,%rdx,1),%esi
133d: cmp $0x3d,%sil
...
135c: mov %ecx,%ebx ; state 1 -> 2, no dispatch
135e: shl $0x2,%esi
1365: shr $0x4,%bl
1368: or %ebx,%esi
136e: mov %sil,(%rax)
...
GCC 17.0.0 trunk: a 4-way dispatch is executed for every byte.
0000000000401300 <decode_b64>:
401300: mov %rdx,%r9
401303: test %rsi,%rsi
401306: je 4013e0 <decode_b64+0xe0>
40130c: lea (%rdi,%rsi,1),%r8
401310: mov %rdi,%rdx
401313: mov %r9,%rax
401316: xor %esi,%esi
401318: xor %edi,%edi
40131a: jmp 401369 <decode_b64+0x69>
401320: cmp $0x1,%edi
401323: jne 4013d0 <decode_b64+0xd0>
401329: mov %ecx,%edi
40132b: shl $0x2,%esi
40132e: add $0x1,%rax
401332: shr $0x4,%dil
401336: or %edi,%esi
401338: mov $0x2,%edi
40133d: mov %sil,-0x1(%rax)
401341: mov %ecx,%esi
401343: and $0xf,%esi
401360: add $0x1,%rdx
401364: cmp %rdx,%r8
401367: je 4013a1 <decode_b64+0xa1>
401369: movzbl (%rdx),%ecx
40136c: cmp $0x3d,%cl
40136f: je 401360 <decode_b64+0x60>
401371: movzbl 0xc04060(%rcx),%ecx
401378: cmp $0x3f,%cl
40137b: ja 401360 <decode_b64+0x60>
40137d: cmp $0x2,%edi ; dispatch on quad_pos,
401380: je 4013a8 <decode_b64+0xa8> ; every iteration
401382: cmp $0x3,%edi
401385: jne 401320 <decode_b64+0x20>
401387: shl $0x6,%esi
40138a: add $0x1,%rdx
40138e: add $0x1,%rax
401392: xor %edi,%edi
...
4013a8: mov %ecx,%edi
4013aa: shl $0x4,%esi
4013ad: add $0x1,%rax
4013b1: shr $0x2,%dil
4013b5: or %edi,%esi
4013b7: mov $0x3,%edi
4013bc: mov %sil,-0x1(%rax)
4013c0: mov %ecx,%esi
4013c2: and $0x3,%esi
4013c5: jmp 401360 <decode_b64+0x60>
Where the trees diverge
------------------------
-fdump-tree-all shows that in GCC 11 the duplication happens in the GIMPLE
jump threader: the number of "this_ch == 61" tests in the function is 2 up to
modref1, 5 after thread1, and 13 after thread2 (threading through the loop
back edge). In GCC 12.3 and GCC 17 the count stays at 2 through the whole
pipeline; only switchlower1 makes a second copy. The state-machine loop is
never threaded in GCC 12+.
I could not find a single -f option that disables the GCC 11 transformation:
-fno-unroll-loops, -fno-peel-loops and -fno-tree-loop-optimize all still
produce the 0x2c3 / 11-copy version, which points at jump threading rather
than loop unrolling.
Workaround / partial recovery
-----------------------------
-funroll-loops helps only partially and is far from GCC 11:
compiler cycles/byte (-O3) cycles/byte (-O3 -funroll-loops)
GCC 11.4.0 2.23 2.28
GCC 12.3.0 3.72 3.36
GCC 17.0.0 4.12 3.37
Real-world impact
-----------------
CPython 3.12 built with --enable-optimizations --with-lto on this machine:
binascii.a2b_base64 over 1 MB takes 21.4 ms with GCC 11.4 and 47.2 ms with
GCC 12.3 (2.2x); the pyperformance base64_large benchmark is 1.64x slower.
I have not bisected this to a specific commit; if that would help, I can do so.
