From: Kyrylo Tkachov <[email protected]>
[This has already been approved by Jeff, sending it here as it is in the
middle of the series]
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-none-linux and x86_64-linux.
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 5ea25f8fbe7..b6ce4da8fe3 100644
--- a/gcc/ifcvt.cc
+++ b/gcc/ifcvt.cc
@@ -4436,11 +4436,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)
