This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] ifcvt: improve cost estimation (PR 87047)


this patch corrects a problem where our cost estimation in if-conversion is
broken when the 'else' block is missing: we then take the cost of 'then' block,
which leads gcc willing to replace a conditionally-executed block with cost 80
with an unconditionally-executed block with cost 72.

Existing heuristic is clearly discontinuous: if the 'else' block wasn't missing
but instead had cost 1, we'd take the minimum of 1 and 80 and match replacement
cost against that.

A more sensible approach is to take average expected time of the if-then-else
(i.e. add costs of 'then' and 'else' scaled by their probabilities), e.g. in
the above example take 0.5*80 = 40 if we expect the block to be executed about
every other time.

Martin Jambor (thanks!) kindly benchmarked this for me on SPEC 2006 and 2017
(sans 521.wrf_r and 527.cam4_r).  There is a 2% improvement for 403.gcc and
3% for 433.milc, both on Skylake.

Considering also changes in 1..2% range, there might be a 1.5% regression on
526.blender_r on Zen 2, and 1.5% improvements for 520.omnetpp_r, 538.imagick_r
and 549.fotonik3d_r on Skylake.

In the PR Richi notes we sometimes won't get high-quality probability data
for such edges on RTL, but that shouldn't be a reason not to replace a broken
heuristic with a less broken one.

Bootstrapped on x86-64, ok for trunk?  For backports?


	* ifcvt.c (average_cost): New static function.  Use it...
	(noce_process_if_block): ... here.

diff --git a/gcc/ifcvt.c b/gcc/ifcvt.c
index e0c9522057a..283bb47f51a 100644
--- a/gcc/ifcvt.c
+++ b/gcc/ifcvt.c
@@ -3358,6 +3358,16 @@ bb_ok_for_noce_convert_multiple_sets (basic_block test_bb)
   return count > 1 && count <= param;
+/* 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.  */
+static unsigned
+average_cost (unsigned then_cost, unsigned else_cost, edge e)
+  return else_cost + e->probability.apply ((int) then_cost - else_cost);
 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
    it without using conditional execution.  Return TRUE if we were successful
    at converting the block.  */
@@ -3413,10 +3423,9 @@ noce_process_if_block (struct noce_if_info *if_info)
     return false;
-  if (else_bb == NULL)
-    if_info->original_cost += then_cost;
-  else if (speed_p)
-    if_info->original_cost += MIN (then_cost, else_cost);
+  if (speed_p)
+    if_info->original_cost += average_cost (then_cost, else_cost,
+					    find_edge (test_bb, then_bb));
     if_info->original_cost += then_cost + else_cost;

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]