[Bug c++/66573] New: Unexpected change in static, branch-prediction cost from O1 to O2.

[jmcguiness at liquidcapital dot com]

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

            Bug ID: 66573
           Summary: Unexpected change in static, branch-prediction cost
                    from O1 to O2.
           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: ---

For the following versions of gcc: 4.8.2, 4.9.0 and 5.10 with the following
code sequence:

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

void foo(bool i) {
  if (i)
        bar1();
  else
    bar2();
}

I have examined the assembler output for -O0, -O1, -O2 and -O3.

For all versions with -O0 & -O1 I get this:

foo(bool):
        subq    $8, %rsp
        testb   %dil, %dil
        je      .L2
        call    bar1()
        jmp     .L1
.L2:
        call    bar2()
.L1:
        addq    $8, %rsp
        ret

For all version with -O2 and -O3 I get this:

foo(bool):
        testb   %dil, %dil
        jne     .L4
        jmp     bar2()
.L4:
        jmp     bar1()

Note how the calls to bar1() and bar2() have been swapped. (I realise that the
condition has been swapped too, so that the generated code is correct.)

According to:

https://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts/

Forward jumps are not taken. So what has happened is that for -O0 and -O1 the
static branch-prediction has given no mis-prediction if bar1() is called, i.e.
the condition is usually true. But this flips for -O2 and -O3 so that now
bar2() suffers no mis-prediction if the condition is usually false.

The result is that if one codes so that one minimises the mis-predition cost
for -O0 and -O1 this becomes a pessimisation for -O2 and -O3. A rather
unexpected result.

Note that icc v13.0.1 generates the following assembly sequence:

foo(bool):
        testb     %dil, %dil                                    #5.7
        je        ..B1.3        # Prob 50%                      #5.7
        jmp       bar1()                                      #6.2
..B1.3:                         # Preds ..B1.1
        jmp       bar2()                                      #8.5

Which is stable for all optimisation levels, and works as one might expect: the
if-branch is the predicted branch, the else not.

(Yes I am aware of __builtin_expected(), but that is beside the point. One
would expect that the cost should reduce with increasing levels of optimisation
not increase!)