[Bug tree-optimization/105973] New: Wrong branch prediction for if (COND) { if(x) noreturn1(); else noreturn2(); }

[Bug tree-optimization/105973] New: Wrong branch prediction for if (COND) { if(x) noreturn1(); else noreturn2(); }

[redi at gcc dot gnu.org]

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

            Bug ID: 105973
           Summary: Wrong branch prediction for if (COND) { if(x)
                    noreturn1(); else noreturn2(); }
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redi at gcc dot gnu.org
  Target Milestone: ---

Given this code:

__attribute__((noreturn)) void throw1();
__attribute__((noreturn)) void throw2();

typedef decltype(sizeof(0)) size_t;

#if defined LIKELY
# define PREDICT(C) __builtin_expect(C,1)
#elif defined UNLIKELY
# define PREDICT(C) __builtin_expect(C,0)
#else
# define PREDICT(C) (C)
#endif

template<typename T>
T* allocate(size_t n)
{
  if (PREDICT(n > (__PTRDIFF_MAX__ / sizeof(T))))
  {
    if (n > (__SIZE_MAX__ / sizeof(T)))
      throw1();
    throw2();
  }

  return (T*) ::operator new(n * sizeof(T));
}

int* alloc_int(size_t n)
{
  return allocate<int>(n);
}


The condition decorated with PREDICT is compiled to different code with
-DLIKELY and -DUNLIKELY, as expected.

However with neither macro defined, the result is the same as -DLIKELY (for any
optimization level > -O0). i.e. the calls to throw1 and throw1 come first and
the return statement requires a branch:

_Z9alloc_intm:
.LFB1:
        .cfi_startproc
        movq    %rdi, %rax
        shrq    $61, %rax
        je      .L2
        subq    $8, %rsp
        .cfi_def_cfa_offset 16
        shrq    $62, %rdi
        je      .L3
        call    _Z6throw1v
        .p2align 4,,10
        .p2align 3
.L3:
        call    _Z6throw2v
        .p2align 4,,10
        .p2align 3
.L2:
        .cfi_def_cfa_offset 8
        salq    $2, %rdi
        jmp     _Znwm
        .cfi_endproc


Surely this is wrong?

If calling a noreturn function is considered unlikely, then surely entering a
block that always calls a noreturn function should also be unlikely?

Clang gets this right, generating the same code as UNLIKELY by default, and
only requiring a branch for the return value when LIKELY is defined.


This code is reduced from std::allocator in libstdc++ and I thought I should be
able to remove a redundant __builtin_expect, but it's needed due to this.

[Bug tree-optimization/105973] Wrong branch prediction for if (COND) { if(x) noreturn1(); else noreturn2(); }

[redi at gcc dot gnu.org]

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

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
In fact we get it wrong even if both branches call the same noreturn function:

  if (PREDICT(n > (__PTRDIFF_MAX__ / sizeof(T))))
  {
    if (n > (__SIZE_MAX__ / sizeof(T)))
      throw1();
    throw1();
  }


This is not compiled to the same code as:

  if (PREDICT(n > (__PTRDIFF_MAX__ / sizeof(T))))
  {
    throw1();
  }

even though it has identical effects.

[Bug tree-optimization/105973] Wrong branch prediction for if (COND) { if(x) noreturn1(); else noreturn2(); }

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
https://godbolt.org/z/asecWe6KK

[Bug tree-optimization/105973] Wrong branch prediction for if (COND) { if(x) noreturn1(); else noreturn2(); }

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hubicka at gcc dot gnu.org

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
possibly the noreturn predictor doesn't trigger here

[Bug tree-optimization/105973] Wrong branch prediction for if (COND) { if(x) noreturn1(); else noreturn2(); }

[hubicka at kam dot mff.cuni.cz]

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

--- Comment #4 from hubicka at kam dot mff.cuni.cz ---
> possibly the noreturn predictor doesn't trigger here
The problem here is that we handle throw1 and throw2 as two independent
reason for code path to be unlikely.  This makes us to look for
conditional controling the code path and we predict the inner if both
ways as unlikely so they cancel out.

I suppose we could be smarter here and teach path predictor to check for
this situation and if both directions of a branch are considered bad for
same reason continue propagating up.  This shoudl not be hard to
implement.

[Bug tree-optimization/105973] Wrong branch prediction for if (COND) { if(x) noreturn1(); else noreturn2(); }

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
If the two noreturn functions are replaced with throwing exceptions, I get the
behaviour I expect:

  if (n > (__PTRDIFF_MAX__ / sizeof(T)))
  {
    if (n > (__SIZE_MAX__ / sizeof(T)))
      throw 1;
    throw 2L;
  }

This is correctly treated as unlikely. So the problem only seems to happen
because of libstdc++'s convention of using named noreturn functions to throw
exceptions (which is done to simplify -fno-exceptions cases). This probably
doesn't affect much user code.

It also seem that if I explicitly add the 'cold' attribute to those noreturn
functions, I get the behaviour I expect.

So maybe it's not worth spending any effort on this, and I should just change
__attribute__((__noreturn__)) to __attribute__((__noreturn__,__cold)) for every
function in libstdc++-v3/include/bits/functexcept.h

[Bug tree-optimization/105973] Wrong branch prediction for if (COND) { if(x) noreturn1(); else noreturn2(); }

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |marxin at gcc dot gnu.org
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2022-06-16
           Assignee|unassigned at gcc dot gnu.org      |marxin at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #6 from Martin Liška <marxin at gcc dot gnu.org> ---
I can try implementing that.

[Bug tree-optimization/105973] Wrong branch prediction for if (COND) { if(x) noreturn1(); else noreturn2(); }

[hubicka at kam dot mff.cuni.cz]

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

--- Comment #7 from hubicka at kam dot mff.cuni.cz ---
> I can try implementing that.
That would be nice.  I think if path predictor logic hits the same
predictor both ways, it can simply predict that basic block with the
same predictor (i.e. recurse on that block).   It will need to keep
track what basic blocks were already predicted to handle cycles.

Honza

[Bug tree-optimization/105973] Wrong branch prediction for if (COND) { if(x) noreturn1(); else noreturn2(); }

[marxin at gcc dot gnu.org]

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

--- Comment #8 from Martin Liška <marxin at gcc dot gnu.org> ---
Thinking about it, we would likely need a "data flow" algorithm, where we want
to transitively propagate equal predicates that occur in both successors of a
basic block. Once we "merge" such a predictor, a new merging opportunity can
happen.

Honza, do you know about a feasible framework I should use? Or should I create
an ad-hoc work queue approach in this situation?

[Bug tree-optimization/105973] Wrong branch prediction for if (COND) { if(x) noreturn1(); else noreturn2(); }

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|marxin at gcc dot gnu.org          |unassigned at gcc dot gnu.org
             Status|ASSIGNED                    |NEW