[Bug c++/66584] New: gcc differs in static, branch-prediction cost from icc in switch.

[Bug c++/66584] New: gcc differs in static, branch-prediction cost from icc in switch.

[jmcguiness at liquidcapital dot com]

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

            Bug ID: 66584
           Summary: gcc differs in static, branch-prediction cost from icc
                    in switch.
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jmcguiness at liquidcapital dot com
  Target Milestone: ---

This means that code optimised for icc is sub-optimal for icc and the reverse
is true. I feel that this feature should be more clearly documented in the web
pages & man pages.

For the following code:

extern void bar1();
extern void bar2();
extern void bar3();

void foo(int i) {
  switch(i) {
  case 1:
    bar1(); // gcc: least likely | icc: most likely
    break;
  case 2:
    bar2(); // gcc: less likely | icc: less likely
    break;
  default:
    bar3(); // gcc: most likely | icc: least likely
  }
}

gcc v4.8.2 & v5.10 for -O2 & -O3 produce:

foo(int):
        cmpl    $1, %edi
        je      .L3
        cmpl    $2, %edi
        jne     .L8
        jmp     bar2()
.L8:
        jmp     bar3()
.L3:
        jmp     bar1()

>From which the static probabilities are quoted, above.

Conversely icc produces:

foo(int):
        cmpl      $1, %edi                                      #9.10
        jne       ..B1.3        # Prob 67%                      #9.10
        jmp       bar1()                                      #11.2
..B1.3:                         # Preds ..B1.1
        cmpl      $2, %edi                                      #9.10
        jne       ..B1.5        # Prob 50%                      #9.10
        jmp       bar2()                                      #14.5
..B1.5:                         # Preds ..B1.3
        jmp       bar3()                                      #17.5

>From which the static probabilities are quoted, above.

Please not: I feel this is *only* a bug in the documentation!

It would be nice if my optimised (for speed) code would be optimised (for
speed) on both platforms in the same way, so that I wouldn't have to optimise
my code, but that is only my taste.

[Bug c++/66584] gcc differs in static, branch-prediction cost from icc in switch.

[ebotcazou at gcc dot gnu.org]

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

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING
   Last reconfirmed|                            |2015-06-18
                 CC|                            |ebotcazou at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #2 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
What would you like us to document exactly?  How are we supposed to track the
evolution of ICC over time?  Why not simply ask ICC to change its heuristics?

[Bug c++/66584] gcc differs in static, branch-prediction cost from icc in switch.

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |RESOLVED
         Resolution|---                         |INVALID

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
More than that, documenting gcc's branch heuristics is just in the code. And
you can see it what gcc figures out via debug dumps. It is also harder to
document this due to different things. For an example if your case 2 contained
a call to call function, it would change gcc's choices too.

[Bug c++/66584] gcc differs in static, branch-prediction cost from icc in switch.

[jmcguiness at liquidcapital dot com]

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

--- Comment #4 from Jason McG <jmcguiness at liquidcapital dot com> ---
(In reply to Eric Botcazou from comment #2)
> What would you like us to document exactly?  How are we supposed to track
...

Perhaps I was unclear. I am asking that you point out to me in the gcc
documentation where it comments regarding code generation for
switch-statements, and that it might make clear that the lexographic "top-down"
approach nor the default label are preferred but other, more complex heuristics
are used that defeat static branch-prediction analysis. I do not think this is
unreasonable. So I disagree entirely that this is invalid.

[Bug c++/66584] gcc differs in static, branch-prediction cost from icc in switch.

[jmcguiness at liquidcapital dot com]

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

Jason McG <jmcguiness at liquidcapital dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|INVALID                     |---

--- Comment #5 from Jason McG <jmcguiness at liquidcapital dot com> ---
(In reply to Andrew Pinski from comment #3)
> More than that, documenting gcc's branch heuristics is just in the code. And
...

I am sorry, but I do not agree. As per my other reply, in comment 4, I think it
is entirely reasonable to request that an additional statement along the lines
of "code generation for switch statements may not follow a top-down approach
nor prefer the default case (if it exists) in terms of static
branch-prediction. The __builtin_expected() intrinsic has no effect" is
included in the web-based documentation in a suitable sub-section. If some
algorithm were used, then adding a link to the web site to the appropriate
paper might be a quick remedy?

This would ensure that developers are not mislead by the argument that
__builtin_expected() takes thinking they could use that, nor would they be
mislead by lore assuming that the default or a lexographic top-down approach to
static branch-prediction were used.

[Bug c++/66584] gcc differs in static, branch-prediction cost from icc in switch.

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
If someone cares so much about the static branch predictor, they would be a
compiler developer. This is the first time I have seen a non-compiler developer
care about documenting gcc heuristics. Note there is no one paper. Also if
branches are 50/50, the decision can change based on adding another statement
and is hard to document otherwise.

[Bug c++/66584] gcc differs in static, branch-prediction cost from icc in switch.

[jmcguiness at liquidcapital dot com]

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

--- Comment #7 from Jason McG <jmcguiness at liquidcapital dot com> ---
(In reply to Andrew Pinski from comment #6)
> If someone cares so much about the static branch predictor, they would be a
...

I am not a compiler developer and I do care about this in the code I work upon.

I occasionally have switch statements that I statically know have a more
commonly used case label (e.g. could be made the default) that static
branch-prediction would reduce the cost of calling. It would have saved me some
time if the documentation I was requesting were present in a more accessible
form that writing test code & reviewing the assembler that gcc generates.

Aside: I have read
https://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf and no-where
does this article describe, apart from in passing, the effect of mis-predicted
branches that using static branch-prediction could avoid by clearly
implementing a "preferred branch" e.g. the default upon their cost models. If I
had time I'd research this, unfortunately I do not.

[Bug c++/66584] gcc differs in static, branch-prediction cost from icc in switch.

[jmcguiness at liquidcapital dot com]

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

--- Comment #8 from Jason McG <jmcguiness at liquidcapital dot com> ---
(In reply to Andrew Pinski from comment #6)
...
> compiler developer. This is the first time I have seen a non-compiler
> developer care about documenting gcc heuristics. Note there is no one paper.
...

See comment 5. The documentation I am proposing is pretty trivial, I repeat:
"code generation for switch statements may not follow a top-down approach nor
prefer the default case (if it exists) in terms of static branch-prediction.
The __builtin_expected() intrinsic has no effect". I find it had to understand
how that documentation could be considered contentious.