Firstly it's important to be clear this is about adding support for a frame chain for unwinding.

A frame pointer is something different since it is used for addressing local variables. Historically Arm compilers only supported a frame pointer, not a frame chain for unwinding. So different Arm backends use different frame pointer registers and there is no defined layout since it is not designed for unwinding.

Why does this matter? Well as your examples show, if you want to emit a frame chain using standard push/pop, it typically ends up pointing to the top of the frame. That is the worst possible position for a frame pointer on Thumb - while Arm supports negative immediate offsets up to 4KB, Thumb-1 doesn't support negative offsets at all, and Thumb-2 supports offsets up to -255 but only with 32-bit instructions. So the result of conflating the frame chain and frame pointer implies a terrible codesize hit for Thumb.

There is also an issue with using r7 as the frame chain in that you're now reserving a precious low register callee-save and just use it once in a typical function. So using r7 is a very bad idea for Thumb.

Your examples suggest LLVM suffers from both of these issues, and IIRC it still uses r11 on Arm but r7 on Thumb. That is way too inefficient/incorrect to consider a defacto standard.

Good point on frame pointers vs a frame chain for unwinding. I'm looking for the unwindable frame chain.

Wilco:
> Why does this matter? Well as your examples show, if you want to emit a frame
> chain using standard push/pop, it typically ends up pointing to the top of the
> frame. That is the worst possible position for a frame pointer on Thumb - while
> Arm supports negative immediate offsets up to 4KB, Thumb-1 doesn't support
> negative offsets at all, and Thumb-2 supports offsets up to -255 but only with
> 32-bit instructions. So the result of conflating the frame chain and frame
> pointer implies a terrible codesize hit for Thumb.

Well, there's really no need for a frame pointer for efficiency, since the stack frame can be efficiently accessed with positive immediate accesses relative to the stack pointer. There are even special encodings for Thumb-2 16-bit LDR/STR which allow an immediate offset of 0 to 1020 when relative to SP - much larger than other registers. You're saying using a frame pointer implies a terrible codesize hit for Thumb, but I don't see how that can be - stack access will continue to go through SP, and the only code size hit should be pushing/popping R7 (~2 cycles), computing R7 as a frame pointer (~1 cycle), and potential register spills due to one less register available. That's a pretty small amount of overhead for a non-leaf function.

> Your examples suggest LLVM suffers from both of these issues, and IIRC it still
> uses r11 on Arm but r7 on Thumb. That is way too inefficient/incorrect to consider
> a defacto standard.

Using R11 in ARM and R7 on Thumb is mandated by the AAPCS I believe. I don't think the overhead is likely to be particularly different in Thumb vs ARM.

Numbers talk, so I collected some benchmarks on some production firmware used in self-driving cars. This code is executing on a Cortex-R5F MCU, processing a large amount of data, with a wide variety of function sizes. Unfortunately precise benchmarking on this MCU is difficult - there seem to be swings of a few percent in performance due to changes in code alignment, but the rough results have been reliable. I'm collecting .text size and time spent in computation. Unfortunately we're using a pretty old version of gcc, but the frame pointer generation doesn't seem to have changed in newer releases.

Baseline: With gcc 4.7, -fomit-frame-pointer, -mthumb: 384016 bytes, 110.943 s.
With gcc 4.7, -fno-omit-frame-pointer, -mthumb: 396688 bytes, 113.539 s.
This shows a +3.2% size overhead and +2.3% time overhead for enabling frame pointers in Thumb-2 code.

With gcc 4.7, -fomit-frame-pointer, ARM mode: 487152 bytes, 113.874 s.
That's +26.9% size and +2.6% time over -mthumb.
With gcc 4.7, -fno-omit-frame-pointer, ARM mode: 498064 bytes, 116.936 s.
This shows a +2.7% size overhead and +2.7% time overhead for enabling frame pointers in Thumb-2 code.
Within margin of error, it appears the frame pointer overhead is comparable in Thumb-2 and ARM code.

With clang 7, -fomit-frame-pointer, -mthumb: 371008 bytes, 107.072 s.
That's -3.4% size and -3.5% time over gcc 4.7.
With clang 7, -fomit-frame-pointer, -mthumb: 377296 bytes, 110.868 s.
This shows a +1.7% size overhead and +3.5% time overhead for enabling frame pointers in Thumb-2 code for clang 7.
Within margin of error, it appears clang's frame pointer overhead is slightly higher than gcc's for Thumb-2, but not much.

With clang 7, -fomit-frame-pointer, ARM mode: 458592 bytes, 112.829 s.
That's +21.5% size +1.8% time over clang -mthumb.
With clang 7, -fno-omit-frame-pointer, ARM mode: 463440 bytes, 111.796 s.
That's +1.1% size -0.9% time over clang ARM without frame pointers. I'm a bit mystified by this result - I looked at the generated code and it does what I'd expect, so I think this is just benchmarking variation due to caches/alignment.

For my application, a ~2.5% performance hit is very worthwhile to gain the extra debugability of easy stack traces. I'll probably end up switching over to clang and frame pointers. It'd be nice if people using gcc for embedded ARM development had an easy option for generating stack traces.

(In reply to Seth LaForge from comment #2)

> Using R11 in ARM and R7 on Thumb is mandated by the AAPCS I believe. I don't
> think the overhead is likely to be particularly different in Thumb vs ARM.

No it doesn't.  The AAPCS for AArch32 makes no reference to a frame pointer, so there is no portable way defined for walking a frame other than by using dwarf records or C++ unwinding descriptions.  The latter are preferred, but only support unwinding from 'synchronous' unwind points (after the prologue and before the epilogue).

Compilers are, of course, free to use frame pointers internally, within a frame, but there is no frame chain that can be walked.

(In reply to Seth LaForge from comment #2)
> Good point on frame pointers vs a frame chain for unwinding. I'm looking for
> the unwindable frame chain.
> 
> Wilco:
> > Why does this matter? Well as your examples show, if you want to emit a frame
> > chain using standard push/pop, it typically ends up pointing to the top of the
> > frame. That is the worst possible position for a frame pointer on Thumb - while
> > Arm supports negative immediate offsets up to 4KB, Thumb-1 doesn't support
> > negative offsets at all, and Thumb-2 supports offsets up to -255 but only with
> > 32-bit instructions. So the result of conflating the frame chain and frame
> > pointer implies a terrible codesize hit for Thumb.
> 
> Well, there's really no need for a frame pointer for efficiency, since the
> stack frame can be efficiently accessed with positive immediate accesses
> relative to the stack pointer. There are even special encodings for Thumb-2
> 16-bit LDR/STR which allow an immediate offset of 0 to 1020 when relative to
> SP - much larger than other registers. You're saying using a frame pointer
> implies a terrible codesize hit for Thumb, but I don't see how that can be -
> stack access will continue to go through SP, and the only code size hit
> should be pushing/popping R7 (~2 cycles), computing R7 as a frame pointer
> (~1 cycle), and potential register spills due to one less register
> available. That's a pretty small amount of overhead for a non-leaf function.

On GCC10 the codesize overhead of -fno-omit-frame-pointer is 4.1% for Arm and 4.8% for Thumb-2 (measured on SPEC2006). That's already a large overhead, especially since this feature doesn't do anything useful besides adding overhead...

The key is that GCC uses the frame pointer for every stack access, and thus the placement of the frame pointer within a frame matters. Thumb compilers place the frame pointer at the bottom of the frame so they can efficiently access locals using positive offsets. Despite that the overhead is significant already.

If GCC would emit a frame chain like the LLVM sequence this means placing the frame pointer at the top of the stack. This forces negative frame offsets for all frame accesses. Getting a 10% overhead is being lucky, I've seen worse...

So this is something that needs to be properly designed and carefully implemented.

> Baseline: With gcc 4.7, -fomit-frame-pointer, -mthumb: 384016 bytes, 110.943
> s.

Thanks for posting actual numbers, but GCC 4.7?!? It might be time to try GCC9...

Richard:
> No it doesn't.  The AAPCS for AArch32 makes no reference to a frame pointer,
> so there is no portable way defined for walking a frame other than by using
> dwarf records or C++ unwinding descriptions.  The latter are preferred, but
> only support unwinding from 'synchronous' unwind points (after the prologue
> and before the epilogue).

...in other words, neither is suitable for generating stack traces in an embedded context, which is a genuinely useful feature.

You're right, AAPCS does not mention frame pointers. ATPCS does - I'm not sure if it's still normative. However, it says the thumb frame pointer is any of r4-r7, and dictates a frame pointer even *higher* on the stack - just above the saved LR. That's not what any compiler I know of does.

At this point it's entirely an argument from consistency:
- GCC ARM and Clang ARM use R11 for frame pointer, pointing to the stacked R11. Useful.
- Clang Thumb uses R7 for frame pointer, pointing to the stacked R7. Useful.
- GCC Thumb uses R7 for the frame pointer, pointing to an arbitrary location. Useless for stack traces.

Stack traces are a genuinely useful thing. Many language runtimes do them automatically all the time (e.g. Python). Many C/C++ development environments do them automatically on a crash, either via a debugger or something like libunwind. Many embedded devices would like to do them on a crash - they often have very little storage to store debugging information and relay it to some server, and something like libunwind is just too much for them.

> Compilers are, of course, free to use frame pointers internally, within a frame,
> but there is no frame chain that can be walked.

With clang, there is. With GCC and ARM mode, there is. I'm promoting making thumb mode work the same as ARM mode, thus making stack tracing possible.

Wilco:
> On GCC10 the codesize overhead of -fno-omit-frame-pointer is 4.1% for Arm and 4.8%
> for Thumb-2 (measured on SPEC2006). That's already a large overhead, especially
> since this feature doesn't do anything useful besides adding overhead...

Well, that's basically my point: as implemented, gcc frame pointers are useless on Thumb. There's no reason to enable them. With a small adjustment to behave the same as clang they are quite useful: software can create stack traces easily. Adding a small amount of overhead to a useless feature in order to make it useful seems like a very worthwhile tradeoff to me.

> The key is that GCC uses the frame pointer for every stack access, and thus the
> placement of the frame pointer within a frame matters.

It does? Why?!? The SP register is a better register to offset from in every case I can think of that doesn't involve alloca() or variable-size-arrays, which should be rare. Clang, when using frame pointers, uses SP to access local variables in most cases - compare the implementation of AccessLocal():

https://godbolt.org/z/3o4TlD

int AccessLocal(int a) {
    volatile int b = a;
    SimpleLeaf();
    return b;
}

GCC 8:
        push    {r7, lr}
        sub     sp, sp, #8
        add     r7, sp, #0
        str     r0, [r7, #4]
        ...

Clang 9:
        push    {r7, lr}
        mov     r7, sp
        sub     sp, #8
        str     r0, [sp, #4]
        ...

Same numer of instructions, same code size, same performance, but the clang version has an unwindable/traceable frame pointer.

> Thanks for posting actual numbers, but GCC 4.7?!? It might be time to try GCC9...

There are, sadly, compelling historical reasons. We're putting our effort into moving to clang instead.

(In reply to Seth LaForge from comment #5)

> GCC 8:
>         push    {r7, lr}
>         sub     sp, sp, #8
>         add     r7, sp, #0
>         str     r0, [r7, #4]
>         ...
> 
> Clang 9:
>         push    {r7, lr}
>         mov     r7, sp
>         sub     sp, #8
>         str     r0, [sp, #4]
>         ...

Crazy yes, but it's due to historical reasons. Originally GCC could only emit code using a frame pointer. Later the frame pointer could be switched off (hence -fomit-frame-pointer), but you still needed it for debug tables. Then there was Dwarf which didn't need a frame pointer anymore. And today the frame pointer is off by default globally in GCC.

> - GCC ARM and Clang ARM use R11 for frame pointer, pointing to the stacked R11. Useful.

Well Clang does this:

       push    {r4, r10, r11, lr}
       add     r11, sp, #8

but GCC does something different:

        push    {r4, r5, fp, lr}
        add     fp, sp, #12

Ie. FP points to saved LR with GCC but saved FP with Clang, so it's not possible for a generic unwinder to follow the chain, even ignoring Arm/Thumb interworking (which is a real issue when an application is Thumb-2 but various library functions use Arm assembly).