https://gcc.gnu.org/g:b58e9cec4c02e4e8b156dd1c875d37f87b85ddeb
commit r17-4987-gb58e9cec4c02e4e8b156dd1c875d37f87b85ddeb Author: Kyrylo Tkachov <[email protected]> Date: Tue Sep 29 16:58:50 2026 +0200 cprop: Cache find_bypass_set results per block [PR127661] find_bypass_set walks the chain of the sets of a register in the hash table until it finds one that is available at the end of a block. The testcase of the PR has N tests "if (v == K)", and each gives an implicit set of v, so the chain has N entries. Jump bypassing repeats the query for the source of an edge each time it moves the edge, about N*N/2 times in total, and after the previous patch this walk takes most of the time that is left in cprop. The set hash table and CPROP_AVOUT do not change while jumps are bypassed, so this patch caches the last query for each basic block and its result. The new test checks that two registers queried from the same block get their own sets. For the testcase at N=2048 on Grace the compile time drops by a further 30%. The generated code does not change. Bootstrapped and tested as a series on aarch64-linux-gnu and x86_64-linux-gnu. gcc/ChangeLog: PR rtl-optimization/127661 * cprop.cc (struct bypass_set_cache_entry): New. (bypass_set_cache): New variable. (find_bypass_set): Use and update it. (bypass_conditional_jumps): Allocate and free it. gcc/testsuite/ChangeLog: PR rtl-optimization/127661 * gcc.dg/pr127661-2.c: New test. Signed-off-by: Kyrylo Tkachov <[email protected]> Diff: --- gcc/cprop.cc | 39 ++++++++++++++++++++++++++++++++++++- gcc/testsuite/gcc.dg/pr127661-2.c | 41 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 79 insertions(+), 1 deletion(-) diff --git a/gcc/cprop.cc b/gcc/cprop.cc index 7250554c75cc..2db8990e634c 100644 --- a/gcc/cprop.cc +++ b/gcc/cprop.cc @@ -1457,15 +1457,42 @@ find_implicit_sets (void) static int bypass_last_basic_block; +/* A find_bypass_set query and its result. */ + +struct bypass_set_cache_entry +{ + /* The register number of the query, or -1 if there was no query. */ + int regno; + + /* The result of the query. */ + struct cprop_expr *set; +}; + +/* The last find_bypass_set query for each basic block with an index less + than bypass_last_basic_block. Jump bypassing can move an edge past a + long chain of blocks, and repeats the query for the source of the edge + at each step. */ + +static struct bypass_set_cache_entry *bypass_set_cache; + /* Find a set of REGNO to a constant that is available at the end of basic block BB. Return NULL if no such set is found. Based heavily upon - find_avail_set. */ + find_avail_set. The set hash table and CPROP_AVOUT do not change + during jump bypassing, so the result is cached in bypass_set_cache. */ static struct cprop_expr * find_bypass_set (int regno, int bb) { struct cprop_expr *result = 0; + gcc_checking_assert (bb < bypass_last_basic_block); + struct bypass_set_cache_entry *entry = &bypass_set_cache[bb]; + if (entry->regno == regno) + return entry->set; + + /* The loop below changes REGNO when it follows a copy. */ + entry->regno = regno; + for (;;) { rtx src; @@ -1490,6 +1517,8 @@ find_bypass_set (int regno, int bb) regno = REGNO (src); } + + entry->set = result; return result; } @@ -1746,6 +1775,11 @@ bypass_conditional_jumps (void) mark_dfs_back_edges (); + bypass_set_cache = XNEWVEC (struct bypass_set_cache_entry, + bypass_last_basic_block); + for (int i = 0; i < bypass_last_basic_block; i++) + bypass_set_cache[i].regno = -1; + changed = false; FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) @@ -1784,6 +1818,9 @@ bypass_conditional_jumps (void) } } + free (bypass_set_cache); + bypass_set_cache = NULL; + /* If we bypassed any register setting insns, we may have inserted copies of them on the redirected edges. These need to be committed. */ if (changed) diff --git a/gcc/testsuite/gcc.dg/pr127661-2.c b/gcc/testsuite/gcc.dg/pr127661-2.c new file mode 100644 index 000000000000..255a85bcf42e --- /dev/null +++ b/gcc/testsuite/gcc.dg/pr127661-2.c @@ -0,0 +1,41 @@ +/* PR rtl-optimization/127661 */ +/* { dg-do run } */ +/* { dg-options "-O2 -fno-thread-jumps" } */ + +int r; + +__attribute__ ((noipa)) void a (void) { r |= 1; } +__attribute__ ((noipa)) void b (void) { r |= 2; } +__attribute__ ((noipa)) void c (void) { r |= 4; } + +/* Jump bypassing moves the edge out of the call to A past the test of V + and then past the test of W. Each step must use the constant of the + register that it tests. */ + +__attribute__ ((noipa)) void +foo (int v, int w, int s) +{ + if (s) + { + v = 7; + w = 3; + a (); + } + if (v == 3) + b (); + if (w == 7) + c (); +} + +int +main () +{ + foo (3, 7, 1); + if (r != 1) + __builtin_abort (); + r = 0; + foo (3, 7, 0); + if (r != 6) + __builtin_abort (); + return 0; +}
