https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128102
--- Comment #4 from 颜森道 <yansendao at 126 dot com> --- Comment on attachment 65952 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65952 propose patch >From f7fcf3d07a3a9c3b4ffd534f1163866cbbac652a Mon Sep 17 00:00:00 2001 From: Sendao Yan <[email protected]> Date: Sun, 25 Oct 2026 20:45:39 +0800 Subject: [PATCH] tree-optimization/128102 - relax the duplication limits for threads through a loop latch The backward threader only exempts a thread from the max-jump-thread-duplication-stmts limit when the path goes through the loop latch _and_ the threaded branch is a multi-way branch. The multi-way test looks at the branch statement of the block the path starts in, so it does not recognize a finite state machine whose state dispatch has already been lowered into a chain of conditional branches. Such a path is rejected even though it is exactly the case the exemption was written for. This can be seen on a byte-at-a-time loop with a four-state machine (a reduction of binascii_a2b_base64 from CPython): - GCC 11 replicates the loop body and constant-folds the state switch away, 2.23 cycles/byte; - GCC 12 and later keep the four-way dispatch on every iteration, 4.10 cycles/byte on trunk; - building trunk with --param=fsm-scale-path-stmts=1 accepts the path again and gives 2.10 cycles/byte, i.e. the duplication budget is what blocks the thread. A path that crosses the loop latch is a finite state machine path whether or not the branch statement happens to be a GIMPLE_SWITCH at the point the threader runs, so use that as the condition instead of the multi-way branch test. The path is still bounded by max-fsm-thread-path-insns, and for -Os/-Oz the m_speed_p check in profitable_path_p still rejects any path with net_insns() > 1. Tested on x86_64-pc-linux-gnu: - the testcase above goes from 0xe3 bytes / 1 copy of the '=' test / 4.10 cycles/byte to 0x14b bytes / 3 copies / 3.06 cycles/byte at -O3, and from 4.12 to 3.03 cycles/byte at -O2 (median of 3 runs); - the full gcc testsuite shows no new failures: 221784 expected passes, and the remaining unexpected failures also occur with an unpatched compiler. gcc/ChangeLog: PR tree-optimization/128102 * tree-ssa-threadbackward.cc (back_threader_profitability::possibly_profitable_path_p): Do not apply the max-jump-thread-duplication-stmts limit to a path that threads through the loop latch. (back_threader_profitability::profitable_path_p): Likewise. gcc/testsuite/ChangeLog: PR tree-optimization/128102 * gcc.dg/tree-ssa/pr128102.c: New test. Signed-off-by: Sendao Yan <[email protected]> --- gcc/testsuite/gcc.dg/tree-ssa/pr128102.c | 69 ++++++++++++++++++++++++ gcc/tree-ssa-threadbackward.cc | 12 ++--- 2 files changed, 75 insertions(+), 6 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr128102.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr128102.c b/gcc/testsuite/gcc.dg/tree-ssa/pr128102.c new file mode 100644 index 00000000000..b71f1508666 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr128102.c @@ -0,0 +1,69 @@ +/* PR tree-optimization/128102 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +typedef __SIZE_TYPE__ 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) +{ + static u8 src[256], dst[256]; + + for (int i = 0; i < 256; i++) + table_a2b_base64[i] = (u8) (i & 63); + + return (int) decode_b64 (src, sizeof src, dst); +} + +/* Threading the loop back edge replicates the loop body, and quad_pos + becomes a constant on every copy, so the '=' test of the source loop + is left 4 times. Without the fix the loop stays rolled and the test + appears only once. */ +/* { dg-final { scan-tree-dump-times "== 61" 4 "optimized" } } */ diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc index c9902d0dc68..14fb059742f 100644 --- a/gcc/tree-ssa-threadbackward.cc +++ b/gcc/tree-ssa-threadbackward.cc @@ -742,9 +742,10 @@ back_threader_profitability::possibly_profitable_path_p to copy. We don't know yet whether we will thread through the latch so we have to be permissive and continue threading, but indicate to the caller the thread, if final, wouldn't be profitable. */ - if ((!m_threaded_multiway_branch - || !loop->latch - || loop->latch->index == EXIT_BLOCK) + if (!m_stats.threaded_through_latch + && (!m_threaded_multiway_branch + || !loop->latch + || loop->latch->index == EXIT_BLOCK) && (net_insns () * param_fsm_scale_path_stmts >= param_max_jump_thread_duplication_stmts)) { @@ -754,8 +755,7 @@ back_threader_profitability::possibly_profitable_path_p "many statements.\n"); return false; } - *large_non_fsm = (!(m_stats.threaded_through_latch - && m_threaded_multiway_branch) + *large_non_fsm = (!m_stats.threaded_through_latch && (net_insns () * param_fsm_scale_path_stmts >= param_max_jump_thread_duplication_stmts)); @@ -845,7 +845,7 @@ back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path, existing threading path to reduce code duplication. So for that case, drastically reduce the number of statements we are allowed to copy. */ - if (!(m_stats.threaded_through_latch && m_threaded_multiway_branch) + if (!m_stats.threaded_through_latch && (net_insns () * param_fsm_scale_path_stmts >= param_max_jump_thread_duplication_stmts)) { -- 2.34.1
