diff mbox series

ifcvt: improve cost estimation (PR 87047)

Message ID alpine.LNX.2.20.13.1909301951260.10498@monopod.intra.ispras.ru
State New
Headers show
Series ifcvt: improve cost estimation (PR 87047) | expand

Commit Message

Alexander Monakov Sept. 30, 2019, 5:32 p.m. UTC 
Hi,

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?

Thanks.
Alexander

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

Comments

Alexander Monakov Sept. 30, 2019, 5:50 p.m. UTC | #1 
On Mon, 30 Sep 2019, Alexander Monakov wrote:

> +static unsigned
> +average_cost (unsigned then_cost, unsigned else_cost, edge e)
> +{
> +  return else_cost + e->probability.apply ((int) then_cost - else_cost);

Ugh, I made a wrong last-minute edit here, we want signed cost difference so
the argument to probability.apply should be

  (int) (then_cost - else_cost)

or

  (int) then_cost - (int) else_cost.

The patch I bootstrapped and passed Martin for testing correctly had

  (gcov_type) then_cost - else_cost

(gcov_type is int64).

Alexander
Richard Biener Oct. 1, 2019, 7:30 a.m. UTC | #2 
On Mon, Sep 30, 2019 at 7:51 PM Alexander Monakov <amonakov@ispras.ru> wrote:
>
> On Mon, 30 Sep 2019, Alexander Monakov wrote:
>
> > +static unsigned
> > +average_cost (unsigned then_cost, unsigned else_cost, edge e)
> > +{
> > +  return else_cost + e->probability.apply ((int) then_cost - else_cost);
>
> Ugh, I made a wrong last-minute edit here, we want signed cost difference so
> the argument to probability.apply should be
>
>   (int) (then_cost - else_cost)
>
> or
>
>   (int) then_cost - (int) else_cost.
>
> The patch I bootstrapped and passed Martin for testing correctly had
>
>   (gcov_type) then_cost - else_cost
>
> (gcov_type is int64).

OK for trunk with that fixed.  Not OK for backports.

Thanks,
Richard.

> Alexander
diff mbox series

Patch

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)
 				       &if_info->else_simple))
     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));
   else
     if_info->original_cost += then_cost + else_cost;