[Bug middle-end/59521] __builtin_expect not effective in switch

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

--- Comment #20 from Martin Liška  ---
Author: marxin
Date: Mon Sep  3 07:51:56 2018
New Revision: 264050

URL: https://gcc.gnu.org/viewcvs?rev=264050=gcc=rev
Log:
Make __builtin_expect effective in switch statements (PR middle-end/PR59521).

2018-09-03  Martin Liska  

  PR middle-end/59521
* predict.c (set_even_probabilities): Add likely_edges
argument and handle cases where we have precisely one
likely edge.
(combine_predictions_for_bb): Catch also likely_edges.
(tree_predict_by_opcode): Handle gswitch statements.
* tree-cfg.h (find_case_label_for_value): New declaration.
(find_taken_edge_switch_expr): Likewise.
* tree-switch-conversion.c (switch_decision_tree::balance_case_nodes):
Find pivot in decision tree based on probabily, not by number of
nodes.
2018-09-03  Martin Liska  

  PR middle-end/59521
* c-c++-common/pr59521-1.c: New test.
* c-c++-common/pr59521-2.c: New test.
* gcc.dg/tree-prof/pr59521-3.c: New test.

Added:
trunk/gcc/testsuite/c-c++-common/pr59521-1.c
trunk/gcc/testsuite/c-c++-common/pr59521-2.c
trunk/gcc/testsuite/gcc.dg/tree-prof/pr59521-3.c
Modified:
trunk/gcc/ChangeLog
trunk/gcc/predict.c
trunk/gcc/testsuite/ChangeLog
trunk/gcc/tree-cfg.c
trunk/gcc/tree-cfg.h
trunk/gcc/tree-switch-conversion.c

[Bug middle-end/59521] __builtin_expect not effective in switch

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

Martin Liška  changed:

   What|Removed |Added

 Status|ASSIGNED|RESOLVED
 Resolution|--- |FIXED

--- Comment #21 from Martin Liška  ---
Done.

[Bug middle-end/59521] __builtin_expect not effective in switch

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

--- Comment #19 from Martin Liška  ---
(In reply to Eric Gallager from comment #18)
> (In reply to Martin Liška from comment #17)
> > Unfortunately I decided to postpone it to GCC 9.x.
> 
> GCC 9.x development is ongoing now.

Yes, I've just installed first part of switch enhancement patches. I'm
definitely planning to do this PR in GCC 9.1.

[Bug middle-end/59521] __builtin_expect not effective in switch

[egallager at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

--- Comment #18 from Eric Gallager  ---
(In reply to Martin Liška from comment #17)
> Unfortunately I decided to postpone it to GCC 9.x.

GCC 9.x development is ongoing now.

[Bug middle-end/59521] __builtin_expect not effective in switch

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

Martin Liška  changed:

   What|Removed |Added

   Target Milestone|--- |9.0

[Bug middle-end/59521] __builtin_expect not effective in switch

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

--- Comment #17 from Martin Liška  ---
Unfortunately I decided to postpone it to GCC 9.x.

[Bug middle-end/59521] __builtin_expect not effective in switch

[ygribov at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

Yury Gribov  changed:

   What|Removed |Added

 CC||ygribov at gcc dot gnu.org

--- Comment #16 from Yury Gribov  ---
(In reply to Daniel Fruzynski from comment #15)
> +1 for this, I wanted to request this today too. I see that some patch is
> ready, how is review going?

This work was picked up by Martin, I'm not sure if it's already in trunk (see
his presentation in
https://slideslive.com/38902416/switch-lowering-improvements).

[Bug middle-end/59521] __builtin_expect not effective in switch

[bugzi...@poradnik-webmastera.com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

Daniel Fruzynski  changed:

   What|Removed |Added

 CC||bugzilla@poradnik-webmaster
   ||a.com

--- Comment #15 from Daniel Fruzynski  ---
+1 for this, I wanted to request this today too. I see that some patch is
ready, how is review going?

[Bug middle-end/59521] __builtin_expect not effective in switch

[tetra2005 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

--- Comment #14 from Yuri Gribov  ---
Patch posted in https://gcc.gnu.org/ml/gcc-patches/2017-07/msg01016.html

[Bug middle-end/59521] __builtin_expect not effective in switch

[tetra2005 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

Yuri Gribov  changed:

   What|Removed |Added

  Attachment #41737|0   |1
is obsolete||

--- Comment #13 from Yuri Gribov  ---
Created attachment 41770
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=41770=edit
Yet another patch

Ok, this one works both for __builtin_expect and -fprofile-generate and
survives bootstrap on x64. I've modified switch decision tree creation to
select pivot value based on probabilities rather than number of values on left
and right (somewhat similar to ID3 algorithm for decision trees).

If patch looks fine in general, I'll add tests and submit for review.

[Bug middle-end/59521] __builtin_expect not effective in switch

[drepper.fsp at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

--- Comment #12 from Ulrich Drepper  ---
On Fri, Jul 14, 2017 at 2:17 PM, marxin at gcc dot gnu.org
 wrote:
> Maybe I miss something, but I would expect to sort all branches in
> emit_case_decision_tree as either predictors can sort branches, or one have a
> profile feedback. Having a chain of equal comparisons, that should be always
> beneficial, or?

I agree.  There seems to be no negative effect.  If you use a stable
sort algorithm the programmer can have influence when needed since the
program's order is preserved.  If the compiler has probability
information it should use it.  Note, I just mean the order of the
tests.  Deciding about placing code in cold sections is a different
story but this isn't what we're talking about here, right?

[Bug middle-end/59521] __builtin_expect not effective in switch

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

--- Comment #11 from Martin Liška  ---
(In reply to Yuri Gribov from comment #10)
> (In reply to Martin Liška from comment #9)
> > The patch works for me for the described case, but does not for PGO, which
> > should do the same based on real numbers:
> 
> Problem here is that we optimize only very_likely edges.  They requires
> 99.95% probability whereas in your testcase we only get 90%.  Changing mods
> to "% 1" and "% 100" results in desired asm:
> 
> cmpl$1, %eax
> je  .L3
> cmpl$10, %eax
> je  .L4
> cmpl$100, %eax
> je  .L5

Maybe I miss something, but I would expect to sort all branches in
emit_case_decision_tree as either predictors can sort branches, or one have a
profile feedback. Having a chain of equal comparisons, that should be always
beneficial, or?

> 
> > Just a small note, Honza's planning to rewrite switch expansion to happen on
> > tree level. Maybe (hopefully) such transformations
> > will be easier on tree level?
> 
> Thanks, that's important to consider.  I'll send patch for review and Cc him
> to maybe comment.  Probly I'll just rebase when his work is in.

Actually he was convincing me to rewrite it, but I still have more unfinished
tasks from history which I should start with ;)

[Bug middle-end/59521] __builtin_expect not effective in switch

[tetra2005 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

--- Comment #10 from Yuri Gribov  ---
(In reply to Martin Liška from comment #9)
> The patch works for me for the described case, but does not for PGO, which
> should do the same based on real numbers:

Problem here is that we optimize only very_likely edges.  They requires 99.95%
probability whereas in your testcase we only get 90%.  Changing mods to "%
1" and "% 100" results in desired asm:

cmpl$1, %eax
je  .L3
cmpl$10, %eax
je  .L4
cmpl$100, %eax
je  .L5

> Just a small note, Honza's planning to rewrite switch expansion to happen on
> tree level. Maybe (hopefully) such transformations
> will be easier on tree level?

Thanks, that's important to consider.  I'll send patch for review and Cc him to
maybe comment.  Probly I'll just rebase when his work is in.

[Bug middle-end/59521] __builtin_expect not effective in switch

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

--- Comment #9 from Martin Liška  ---
(In reply to Yuri Gribov from comment #8)
> Created attachment 41737 [details]
> New draft patch
> 
> How about this? I added edge attribute for builtin_expect and later used it
> in emit_case_decision_tree to emit expected comparison prior to decision
> tree for other case values.
> 
> With this patch GCC optimizes original example. If it's not too ugly I'll do
> proper testing and send to gcc-patches.

The patch works for me for the described case, but does not for PGO, which
should do the same based on real numbers:

$ cat pr59521-profile.c
#include 
void
f(int ch) {
  switch (ch) {
case 100: puts("100"); break;   
case 10: puts("10"); break; 
case 1: puts("1"); break; 
} 
}

int main()
{
  for (int i = 0; i < 1; i++)
  {
int v;
if (i % 100 == 0)
  v = 100;
else if(i % 10 == 0)
  v = 10;
else
  v = 1;
f(v);
  }
}

$ gcc pr59521-profile.c -fprofile-generate && ./a.out && gcc pr59521-profile.c
-fprofile-use -S -fdump-tree-optimized=/dev/stdout

...
f (int ch)
{
   [100.00%] [count: 1]:
  switch (ch_2(D))  [0.00%] [count: 0], case 1:  [90.00%]
[count: 9000], case 10:  [9.00%] [count: 900], case 100:  [1.00%]
[count: 100]>
...

But assembly looks as follows:

cmpl$10, %eax
je  .L3
cmpl$100, %eax
je  .L4
cmpl$1, %eax
je  .L5
jmp .L6

Just a small note, Honza's planning to rewrite switch expansion to happen on
tree level. Maybe (hopefully) such transformations
will be easier on tree level?

[Bug middle-end/59521] __builtin_expect not effective in switch

[tetra2005 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

Yuri Gribov  changed:

   What|Removed |Added

  Attachment #41698|0   |1
is obsolete||

--- Comment #8 from Yuri Gribov  ---
Created attachment 41737
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=41737=edit
New draft patch

How about this? I added edge attribute for builtin_expect and later used it in
emit_case_decision_tree to emit expected comparison prior to decision tree for
other case values.

With this patch GCC optimizes original example. If it's not too ugly I'll do
proper testing and send to gcc-patches.

[Bug middle-end/59521] __builtin_expect not effective in switch

[tetra2005 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

--- Comment #7 from Yuri Gribov  ---
(In reply to Martin Liška from comment #5)
> Apart from that I added code that preserves
> that probability in combine_predictions_for_bb.

Yes, I did pretty much the same locally)

> But still there's a missing piece that will rearrange switch statement so
> that case 333 will be first:

Right, I'll take it from there then.

[Bug middle-end/59521] __builtin_expect not effective in switch

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

--- Comment #6 from Martin Liška  ---
Created attachment 41713
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=41713=edit
Semi-working patch

[Bug middle-end/59521] __builtin_expect not effective in switch

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

--- Comment #5 from Martin Liška  ---
Ok, your patch is definitely needed to properly propagate the builtin
probability to a proper edge. Apart from that I added code that preserves that
probability incombine_predictions_for_bb. Having that we're quite close:

$ ./xgcc -B. ~/Programming/testcases/pr59521.c -O2 -c -S
-fdump-tree-optimized=/dev/stdout

;; Function f (f, funcdef_no=11, decl_uid=2306, cgraph_uid=11, symbol_order=11)

Removing basic block 7
f (int ch)
{
   [100.00%] [count: INV]:
  switch (ch_4(D))  [3.33%] [count: INV], case 3:  [3.33%]
[count: INV], case 42:  [3.33%] [count: INV], case 333:  [90.00%]
[count: INV]>

But still there's a missing piece that will rearrange switch statement so that
case 333 will be first:

f:
.LFB11:
.cfi_startproc
cmpl$42, %edi
je  .L3
cmpl$333, %edi
jne .L8
movl$.LC2, %edi
jmp puts

Can you please Yuri take a look?

[Bug middle-end/59521] __builtin_expect not effective in switch

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

Martin Liška  changed:

   What|Removed |Added

 Status|NEW |ASSIGNED
   Assignee|unassigned at gcc dot gnu.org  |marxin at gcc dot 
gnu.org

--- Comment #4 from Martin Liška  ---
I'll take a look.

[Bug middle-end/59521] __builtin_expect not effective in switch

[tetra2005 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

Yuri Gribov  changed:

   What|Removed |Added

 CC||marxin at gcc dot gnu.org

--- Comment #3 from Yuri Gribov  ---
Cc Martin to comment, as he added the problematic part in
combine_predictions_for_bb.

[Bug middle-end/59521] __builtin_expect not effective in switch

[tetra2005 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

Yuri Gribov  changed:

   What|Removed |Added

 CC||tetra2005 at gmail dot com

--- Comment #2 from Yuri Gribov  ---
Created attachment 41698
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=41698=edit
Draft patch (not working)

This can be added easily but I ran into a block in combine_predictions_for_bb
which resets predictions whenever block has more than one outgoing edge and
predictor is not strong enough (like e.g. noreturn predictor).

[Bug middle-end/59521] __builtin_expect not effective in switch

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

Richard Biener rguenth at gcc dot gnu.org changed:

   What|Removed |Added

   Severity|normal  |enhancement

[Bug middle-end/59521] __builtin_expect not effective in switch

[mpolacek at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521

Marek Polacek mpolacek at gcc dot gnu.org changed:

   What|Removed |Added

 Status|UNCONFIRMED |NEW
   Last reconfirmed||2013-12-16
 CC||mpolacek at gcc dot gnu.org
 Ever confirmed|0   |1

--- Comment #1 from Marek Polacek mpolacek at gcc dot gnu.org ---
Confirmed.