From 528df313f6d941cde12c12bdeb20d6d24e05ba4b Mon Sep 17 00:00:00 2001 From: Dimitar Dimitrov Date: Fri, 5 Dec 2025 21:57:58 -0700 Subject: [PATCH] [PATCH v3] rtl-optimization: Fix BB edge ordering [PR122675] Starting with r16-4438-ga93f80feeef744, the edge sorting order was switched to lowest execution frequency first. But the "bbro" optimization pass chooses the first edge as a fallthrough. Thus the most unlikely branches were optimized to fallthroughs. Fix by restoring the sorting order prior to r16-4438-ga93f80feeef744. Now the branches most likely to be executed are picked as fallthroughs. There are no regressions for C and C++ on x86_64-pc-linux-gnu. The new tests fail for the respective targets without this patch, and pass with it. PR rtl-optimization/122675 gcc/ChangeLog: * bb-reorder.cc (edge_order): Fix BB edge ordering to be descending. gcc/testsuite/ChangeLog: * gcc.target/aarch64/pr122675-1.c: New test. * gcc.target/i386/pr122675-1.c: New test. * gcc.target/riscv/pr122675-1.c: New test. Signed-off-by: Dimitar Dimitrov --- gcc/bb-reorder.cc | 13 +++++- gcc/testsuite/gcc.target/aarch64/pr122675-1.c | 31 ++++++++++++++ gcc/testsuite/gcc.target/i386/pr122675-1.c | 33 +++++++++++++++ gcc/testsuite/gcc.target/riscv/pr122675-1.c | 42 +++++++++++++++++++ 4 files changed, 117 insertions(+), 2 deletions(-) create mode 100644 gcc/testsuite/gcc.target/aarch64/pr122675-1.c create mode 100644 gcc/testsuite/gcc.target/i386/pr122675-1.c create mode 100644 gcc/testsuite/gcc.target/riscv/pr122675-1.c diff --git a/gcc/bb-reorder.cc b/gcc/bb-reorder.cc index e4efdee0b16..0bcd0e57128 100644 --- a/gcc/bb-reorder.cc +++ b/gcc/bb-reorder.cc @@ -2377,7 +2377,11 @@ reorder_basic_blocks_software_trace_cache (void) FREE (bbd); } -/* Order edges by execution frequency, higher first. */ +/* Order edges by execution frequency, higher first. + Return: + 1 iff frequency (VE1) < frequency (VE2) + 0 iff frequency (VE1) == frequency (VE2) + -1 iff frequency (VE1) > frequency (VE2) */ static int edge_order (const void *ve1, const void *ve2) @@ -2392,7 +2396,12 @@ edge_order (const void *ve1, const void *ve2) gcov_type gc1 = c1.initialized_p () ? c1.to_gcov_type () : 0; gcov_type gc2 = c2.initialized_p () ? c2.to_gcov_type () : 0; gcov_type m = MAX (gc1, gc2); - return (m == gc1) - (m == gc2); + int low_to_high_cmp = (m == gc1) - (m == gc2); + /* gcc_stablesort sorts values in low-to-high order. But edges should + be sorted in the opposite order - with highest execution frequency first. + So return an inverted comparison to trick gcc_stablesort into + performing a reversed sorting order. */ + return -1 * low_to_high_cmp; } /* Reorder basic blocks using the "simple" algorithm. This tries to diff --git a/gcc/testsuite/gcc.target/aarch64/pr122675-1.c b/gcc/testsuite/gcc.target/aarch64/pr122675-1.c new file mode 100644 index 00000000000..8d2982ac21e --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/pr122675-1.c @@ -0,0 +1,31 @@ +/* Verify that the most likely BB edges are optimized as fallthroughs. */ +/* { dg-do compile } */ +/* { dg-options "-O1 -fno-pic -mtune=generic -march=armv8-a" } */ +/* Keep labels and directives ('.cfi_startproc', '.cfi_endproc'). */ +/* { dg-final { check-function-bodies "**" "" "" { target *-*-* } {^\t?\.} } } */ + +/* +**test: +**.LFB[0-9]+: +** .cfi_startproc +**... +** cbz w0, .L[0-9]* +**... +** bl f1 +**... +** ret +**.L[0-9]+: +**... +** ret +**... +*/ + +int f1(void); + +int test(int a) +{ + if (__builtin_expect(!!a, 1)) { + return f1(); + } + return a; +} diff --git a/gcc/testsuite/gcc.target/i386/pr122675-1.c b/gcc/testsuite/gcc.target/i386/pr122675-1.c new file mode 100644 index 00000000000..fb41f5b2788 --- /dev/null +++ b/gcc/testsuite/gcc.target/i386/pr122675-1.c @@ -0,0 +1,33 @@ +/* Verify that the most likely BB edges are optimized as fallthroughs. */ +/* { dg-do compile } */ +/* { dg-options "-O1 -fno-pic -march=x86-64 -mtune=generic -mgeneral-regs-only" } */ +/* Keep labels and directives ('.cfi_startproc', '.cfi_endproc'). */ +/* { dg-final { check-function-bodies "**" "" "" { target lp64 } {^\t?\.} } } */ + +/* +**test: +**.LFB[0-9]+: +** .cfi_startproc +** testl %edi, %edi +** je .L[0-9]* +** subq \$[0-9]*, %rsp +** .cfi_def_cfa_offset [0-9]* +** call f1 +** addq \$[0-9]*, %rsp +** .cfi_def_cfa_offset [0-9]* +** ret +**.L[0-9]+: +** movl %edi, %eax +** ret +**... +*/ + +int f1(void); + +int test(int a) +{ + if (__builtin_expect(!!a, 1)) { + return f1(); + } + return a; +} diff --git a/gcc/testsuite/gcc.target/riscv/pr122675-1.c b/gcc/testsuite/gcc.target/riscv/pr122675-1.c new file mode 100644 index 00000000000..6f49ef3b5d8 --- /dev/null +++ b/gcc/testsuite/gcc.target/riscv/pr122675-1.c @@ -0,0 +1,42 @@ +/* Verify that the most likely BB edges are optimized as fallthroughs. */ +/* { dg-do compile } */ +/* { dg-options "-O1 -fno-pic -march=rv64gc -mabi=lp64d" } */ +/* Keep labels and directives ('.cfi_startproc', '.cfi_endproc'). */ +/* { dg-final { check-function-bodies "**" "" "" { target *-*-* } {^\t?\.} } } */ + +/* +**test: +**... +**.LFB[0-9]+: +**... +** .cfi_startproc +**... +** beq a0,zero,.L[0-9]* +**... +** call f1 +**... +** ( +** jr ra +** | +** ret +** ) +**... +**.L[0-9]+: +**... +** ( +** jr ra +** | +** ret +** ) +**... +*/ + +int f1(void); + +int test(int a) +{ + if (__builtin_expect(!!a, 1)) { + return f1(); + } + return a; +} -- 2.47.3