diff mbox series

[2/2] ifcvt: Make average_cost independent of arm order [PR125557]

Message ID 20260717132520.76497-2-ktkachov@nvidia.com
State New
Headers
Series [1/2] profile-count: Handle signed values in profile_probability::apply |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 success Build passed
linaro-tcwg-bot/tcwg_gcc_build--master-arm success Build passed
linaro-tcwg-bot/tcwg_simplebootstrap_build--master-aarch64-bootstrap success Build passed
linaro-tcwg-bot/tcwg_simplebootstrap_build--master-arm-bootstrap success Build passed
linaro-tcwg-bot/tcwg_gcc_check--master-arm success Test passed

Commit Message

Kyrylo Tkachov July 17, 2026, 1:25 p.m. UTC 
  From: Kyrylo Tkachov <ktkachov@nvidia.com>

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.

Bootstrapped and tested on aarch64-linux-gnu and x86_64-linux.
Ok for trunk?
Thanks,
Kyrill

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 <ktkachov@nvidia.com>
---
 gcc/ifcvt.cc                                  | 13 ++++++--
 .../gcc.target/i386/ifcvt-average-cost-1.c    | 32 +++++++++++++++++++
 2 files changed, 43 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/gcc.target/i386/ifcvt-average-cost-1.c

Comments

Kyrylo Tkachov July 24, 2026, 12:27 p.m. UTC | #1 
Ping.
Thanks,
Kyrill

> On 17 Jul 2026, at 15:25, Kyrylo Tkachov <ktkachov@nvidia.com> wrote:
> 
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
> 
> 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.
> 
> Bootstrapped and tested on aarch64-linux-gnu and x86_64-linux.
> Ok for trunk?
> Thanks,
> Kyrill
> 
> 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 <ktkachov@nvidia.com>
> ---
> gcc/ifcvt.cc                                  | 13 ++++++--
> .../gcc.target/i386/ifcvt-average-cost-1.c    | 32 +++++++++++++++++++
> 2 files changed, 43 insertions(+), 2 deletions(-)
> create mode 100644 gcc/testsuite/gcc.target/i386/ifcvt-average-cost-1.c
> 
> diff --git a/gcc/ifcvt.cc b/gcc/ifcvt.cc
> index 6a76fec66cb..928483a347c 100644
> --- a/gcc/ifcvt.cc
> +++ b/gcc/ifcvt.cc
> @@ -4309,11 +4309,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 00000000000..98ca361cb69
> --- /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} } } */
> -- 
> 2.50.1 (Apple Git-155)
>
Jeffrey Law July 24, 2026, 10:52 p.m. UTC | #2 
On 7/24/2026 6:27 AM, Kyrylo Tkachov wrote:
> Ping.
> Thanks,
> Kyrill
>
>> On 17 Jul 2026, at 15:25, Kyrylo Tkachov <ktkachov@nvidia.com> wrote:
>>
>> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>>
>> 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.
>>
>> Bootstrapped and tested on aarch64-linux-gnu and x86_64-linux.
>> Ok for trunk?
>> Thanks,
>> Kyrill
>>
>> 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 <ktkachov@nvidia.com>
OK.
jeff
Jeffrey Law July 25, 2026, 2:09 a.m. UTC | #3 
On 7/24/2026 6:27 AM, Kyrylo Tkachov wrote:
>> On 17 Jul 2026, at 15:25, Kyrylo Tkachov <ktkachov@nvidia.com> wrote:
>>
>> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>>
>> 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.
>>
>> Bootstrapped and tested on aarch64-linux-gnu and x86_64-linux.
>> Ok for trunk?
>> Thanks,
>> Kyrill
>>
>> 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 <ktkachov@nvidia.com>
OK.
jeff
Kyrylo Tkachov July 25, 2026, 8:14 a.m. UTC | #4 
> On 25 Jul 2026, at 04:09, Jeffrey Law <jeffrey.law@oss.qualcomm.com> wrote:
> 
> 
> 
> On 7/24/2026 6:27 AM, Kyrylo Tkachov wrote:
>>> On 17 Jul 2026, at 15:25, Kyrylo Tkachov <ktkachov@nvidia.com> wrote:
>>> 
>>> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>>> 
>>> 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.
>>> 
>>> Bootstrapped and tested on aarch64-linux-gnu and x86_64-linux.
>>> Ok for trunk?
>>> Thanks,
>>> Kyrill
>>> 
>>> 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 <ktkachov@nvidia.com>
> OK.

Thanks for the review Jeff. You seem to have ok’ed this patch twice.
Did you meant to ok patch [1/2] by any chance?
https://gcc.gnu.org/pipermail/gcc-patches/2026-July/724378.html
Kyrill

> jeff
diff mbox series

Patch

diff --git a/gcc/ifcvt.cc b/gcc/ifcvt.cc
index 6a76fec66cb..928483a347c 100644
--- a/gcc/ifcvt.cc
+++ b/gcc/ifcvt.cc
@@ -4309,11 +4309,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 00000000000..98ca361cb69
--- /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} } } */