[gcc r17-3423] ifcvt: Make average_cost independent of arm order [PR125557]

https://gcc.gnu.org/g:ee69b433860e8017974df2bb499924a5fd1c7894

commit r17-3423-gee69b433860e8017974df2bb499924a5fd1c7894
Author: Kyrylo Tkachov <[email protected]>
Date:   Thu Jul 16 12:54:59 2026 +0200

    ifcvt: Make average_cost independent of arm order [PR125557]
    
    average_cost computes
    
      ELSE_COST + P * (THEN_COST - ELSE_COST)
    
    profile_probability::apply now rounds signed initialized values to the nearest
    integer, with halfway values away from zero.  That signed rounding can still
    give different integer costs when equivalent CFG arms are reversed.  Unknown
    probabilities have the same issue for odd cost differences because apply
    truncates them toward zero.
    
    Write the documented weighted average as
    
      ELSE_COST + P * (THEN_COST - ELSE_COST)
    
    when THEN_COST is at least ELSE_COST, and as
    
      THEN_COST + (1 - P) * (ELSE_COST - THEN_COST)
    
    otherwise.  Both forms start with the cheaper arm and scale a nonnegative
    cost difference by the probability of the costlier arm.  Reversing the CFG
    arms therefore keeps the same base, magnitude, probability, and rounded
    result.  Cast the costlier arm to gcov_type before subtraction.
    
    Add an x86 test with the same costs and probabilities represented using
    reversed CFG arms.  The scaled cost difference is an exact halfway value.
    The apply-only compiler makes opposite profitability decisions for the two
    orientations.  With this change both forms convert to conditional moves.
    
    gcc/ChangeLog:
    
            PR tree-optimization/125557
            * ifcvt.cc (average_cost): Scale a nonnegative cost difference using
            the probability of the more expensive arm.
    
    gcc/testsuite/ChangeLog:
    
            PR tree-optimization/125557
            * gcc.target/i386/ifcvt-average-cost-1.c: New test.
    
    Signed-off-by: Kyrylo Tkachov <[email protected]>

Diff:
---
 gcc/ifcvt.cc                                       | 13 +++++++--
 .../gcc.target/i386/ifcvt-average-cost-1.c         | 32 ++++++++++++++++++++++
 2 files changed, 43 insertions(+), 2 deletions(-)

diff --git a/gcc/ifcvt.cc b/gcc/ifcvt.cc
index 722cd8c1bbe2..ecf59a21806e 100644
--- a/gcc/ifcvt.cc
+++ b/gcc/ifcvt.cc
@@ -4440,11 +4440,20 @@ bb_ok_for_noce_convert_multiple_sets (basic_block test_bb, unsigned *cost)
 /* Compute average of two given costs weighted by relative probabilities
    of respective basic blocks in an IF-THEN-ELSE.  E is the IF-THEN edge.
    With P as the probability to take the IF-THEN branch, return
-   P * THEN_COST + (1 - P) * ELSE_COST.  */
+   P * THEN_COST + (1 - P) * ELSE_COST.  Evaluate this as
+   ELSE_COST + P * (THEN_COST - ELSE_COST) when THEN_COST >= ELSE_COST, and
+   THEN_COST + (1 - P) * (ELSE_COST - THEN_COST) otherwise.  Both forms pass
+   a nonnegative value to profile_probability::apply and make its rounding
+   independent of the CFG arm order.  */
 static unsigned
 average_cost (unsigned then_cost, unsigned else_cost, edge e)
 {
-  return else_cost + e->probability.apply ((signed) (then_cost - else_cost));
+  if (then_cost < else_cost)
+    return then_cost
+      + e->probability.invert ().apply ((gcov_type) else_cost - then_cost);
+
+  return else_cost
+    + e->probability.apply ((gcov_type) then_cost - else_cost);
 }
 
 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
diff --git a/gcc/testsuite/gcc.target/i386/ifcvt-average-cost-1.c b/gcc/testsuite/gcc.target/i386/ifcvt-average-cost-1.c
new file mode 100644
index 000000000000..98ca361cb698
--- /dev/null
+++ b/gcc/testsuite/gcc.target/i386/ifcvt-average-cost-1.c
@@ -0,0 +1,32 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target lp64 } */
+/* { dg-options "-O2 -mtune=generic --param=max-rtl-if-conversion-unpredictable-cost=0 -fdump-rtl-ce1" } */
+
+/* These functions describe the same branch probabilities and arm costs with
+   the arms reversed.  The scaled cost difference is exactly halfway between
+   two integers.  */
+long
+then_cheaper (long c, long a, long b)
+{
+  long x;
+  if (__builtin_expect_with_probability (c != 0, 0, 0.9375))
+    x = a ^ b;
+  else
+    x = b * 3 + 1;
+  return x;
+}
+
+long
+then_costlier (long c, long a, long b)
+{
+  long x;
+  if (__builtin_expect_with_probability (c == 0, 1, 0.9375))
+    x = b * 3 + 1;
+  else
+    x = a ^ b;
+  return x;
+}
+
+/* { dg-final { scan-rtl-dump-times "if-conversion succeeded through noce_try_cmove_arith" 2 "ce1" } } */
+/* { dg-final { scan-assembler-times {\tcmov} 2 } } */
+/* { dg-final { scan-assembler-not {\tj(e|ne)\t} } } */