From: Kyrylo Tkachov <[email protected]>
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 <[email protected]>
---
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)
