[Bug middle-end/49035] New: Avoid setting up stack frame for short, hot code paths

[Bug middle-end/49035] New: Avoid setting up stack frame for short, hot code paths

[scovich at gmail dot com]

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

           Summary: Avoid setting up stack frame for short, hot code paths
           Product: gcc
           Version: 4.5.2
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: scovich@gmail.com


I often find myself writing functions of the following form:

void foo () {
    if (common_case) {
        /* do a little work and return */
    }
    /* uncommon case: do a lot of work, call functions, etc. */
}

The resulting assembly code always sets up a stack frame in the function
prologue, even though the function usually executes as a leaf using few (or
zero) of the callee-save registers and stack slots it saves. 

Here's an example which is only slightly contrived:

=== rfe.cpp ============
struct link {
    link* prev;
    long go_slow;
    void frob(link* parent, link* grandparent);
};

link* foo(link* list) {
    link* prev = list->prev;
    while (__builtin_expect(prev->go_slow, 0)) {
        link* pprev = __sync_lock_test_and_set(&prev->prev, 0);
        pprev->frob(prev, list);
        prev = pprev;
    }
    return prev;
}
=== rfe.cpp ============

Compiling the above with `x86_64-unknown-linux-gnu-g++-4.5.2 -O3 -S' yields

_Z3fooP4link:
.LFB0:
        movq    %rbx, -24(%rsp)
        movq    %rbp, -16(%rsp)
        movq    %rdi, %rbx
        movq    %r12, -8(%rsp)
        subq    $24, %rsp
        movq    (%rdi), %rax
        cmpq    $0, 8(%rax)
        jne     .L8
.L2:
        movq    (%rsp), %rbx
        movq    8(%rsp), %rbp
        movq    16(%rsp), %r12
        addq    $24, %rsp
        ret
.L8:
        xorl    %r12d, %r12d
.L6:
        movq    %r12, %rbp
        xchgq   (%rax), %rbp
        movq    %rbx, %rdx
        movq    %rax, %rsi
        movq    %rbp, %rdi
        call    _ZN4link4frobEPS_S0_
        cmpq    $0, 8(%rbp)
        jne     .L4
        movq    %rbp, %rax
        jmp     .L2
.L4:
        movq    %rbp, %rax
        jmp     .L6


Ideally, it would look like this instead:

_Z3fooP4link:
.LFB0:
        ;; *** hot path executes as leaf ***
        movq    (%rdi), %rax
        cmpq    $0, 8(%rax)
        jne     .L8
        ret
.L8:
        ;; *** set up stack frame ***
        movq    %rbx, -24(%rsp)
        movq    %rbp, -16(%rsp)
        movq    %rdi, %rbx
        movq    %r12, -8(%rsp)
        subq    $24, %rsp
        ;; ***
        xorl    %r12d, %r12d
.L6:
        movq    %r12, %rbp
        xchgq   (%rax), %rbp
        movq    %rbx, %rdx
        movq    %rax, %rsi
        movq    %rbp, %rdi
        call    _ZN4link4frobEPS_S0_
        cmpq    $0, 8(%rbp)
        jne     .L4
        ;; *** tear down stack frame ***
        movq    %rbp, %rax
        movq    (%rsp), %rbx
        movq    8(%rsp), %rbp
        movq    16(%rsp), %r12
        addq    $24, %rsp
        ;; *** 
        ret
.L4:
        movq    %rbp, %rax
        jmp     .L6


The effect can sometimes be simulated using an inlined foo which includes the
fast path and a call to the (non-inlined) slow path, but the whims of function
inlining often conspire against it even when callers are able to inline foo
(e.g. foo is not a library function).

There's probably some overlap with partial inlining here: the ideal case
essentially splits the slow path off into its own function (called using tail
recursion); presumably partial inlining would inline the fast path while having
all callers jump to the same copy of the slow path function. However, the
optimization is arguably useful even if foo is never inlined at all.

Thoughts?
Ryan

[Bug middle-end/49035] Avoid setting up stack frame for short, hot code paths

[scovich at gmail dot com]

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

--- Comment #1 from Ryan Johnson <scovich at gmail dot com> 2011-05-18 02:56:23 UTC ---
Update: using __attribute__((noinline)) it is actually possible to force the
compiler to do the right thing, though it makes the code significantly less
readable:

=== example.cpp ============
struct link {
    link* prev;
    long go_slow;
    void frob(link* parent, link* grandparent);
};

link* __attribute__((noinline)) foo_slow(link* list, link* prev) {
    do {
        link* pprev = __sync_lock_test_and_set(&prev->prev, 0);
        pprev->frob(prev, list);
        prev = pprev;
    } while(__builtin_expect(prev->go_slow, 0));
    return prev;
}

link* foo_fast(link* list) {
    link* prev = list->prev;
    if (__builtin_expect(prev->go_slow, 0))
        return foo_slow(list, prev);
    return prev;
}
=== example.cpp ============

The above compiles down to something much better, though the calling convention
requires an extra movq and there are more jumps than required (the compiler
probably doesn't ever perform tail recursion using a conditional jump):

_Z8foo_fastP4link:
        movq    (%rdi), %rax
        cmpq    $0, 8(%rax)
        jne     .L7
        rep
        ret
.L7:
        movq    %rax, %rsi
        jmp     _Z8foo_slowP4linkS0_

_Z8foo_slowP4linkS0_:
        movq    %rbp, -16(%rsp)
        movq    %r12, -8(%rsp)
        xorl    %ebp, %ebp
        movq    %rbx, -24(%rsp)
        movq    %rdi, %r12
        subq    $24, %rsp
.L2:
        movq    %rbp, %rbx
        xchgq   (%rsi), %rbx
        movq    %r12, %rdx
        movq    %rbx, %rdi
        call    _ZN4link4frobEPS_S0_
        cmpq    $0, 8(%rbx)
        jne     .L3
        movq    %rbx, %rax
        movq    8(%rsp), %rbp
        movq    (%rsp), %rbx
        movq    16(%rsp), %r12
        addq    $24, %rsp
        ret
.L3:
        movq    %rbx, %rsi
        jmp     .L2

[Bug middle-end/49035] Avoid setting up stack frame for short, hot code paths

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |DUPLICATE

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-05-18 04:59:54 UTC ---
Dup of older bug which I filed.

*** This bug has been marked as a duplicate of bug 10474 ***