The first effect is that it makes one additional general-purpose integer register unavailable for use for code. x86-64 has 16 general-purpose registers, but one of these is the stack pointer and basically can't be used for any other purpose; this would add a second reserved register for the frame pointer. This effect may cause slowdowns if the 15th register was critical for performance.
The second effect is on the ability to identify (and potentially unwind) the stack trace. With frame pointers, the pseudocode for computing a stack trace is essentially:
do
load return address, previous frame pointer from current frame pointer
print return address
move previous frame pointer into current frame pointer
until current frame pointer is invalid
Without frame pointers, the way you have to do this procedure is:
while current address has corresponding entry in unwind table:
parse unwind table entry to find a program to run
run this program on the current frame to generate return address
print return address
move return address to current address
It turns out that there is a full Turing-complete program described in the unwind tables to be able to generate a return address. This makes unwinding quite expensive, and also can create lots of security headaches if you want do something like unwind in the kernel (since the unwind table is arbitrary user code!). It can also be pretty unreliable at times, especially in cases where your program crashed due to stack smashing so that you have to expect that the data being randomly overwritten with garbage and thus horrifically inaccurate.
Does this provide there any benefit at all to the majority of machines which aren't intended to be used for development of binaries (i.e. user workstations, developers working with interpreted languages, and servers), what would be the use cases where frame pointers would help on those machines?
Like, even for developers, I assume a random web development shop using Ubuntu and hosting stuff on Ubuntu would likely not ever attempt debugging a binary executable, and likely don't have any employees who could do it if they wanted. Of course there are companies who can and do debugging and profiling of binaries running on their servers, but IMHO those who are capable and willing to do that a relatively small minority of users of Ubuntu systems.
Well, for a start you probably mean compiled for an arch with 16 registers. It doesn't actually matter what arch the compiler ran on (assuming modern cross-compiler like GCC).
If a program uses 16 registers then it needs 16 registers. But note it's the program itself that decides to use a frame pointer, it's not being reserved by the operating system or something. Programs don't even have to use the stack pointer as a stack pointer, they could use all 16 as general purpose, but in practice almost all programs use a call stack (I guess all C programs must do, but you might be able to disable it if you make no function calls?)
So the only change is that GCC and its toolkit will compile programs using a register as frame pointer by default? That seems like a very reasonable change. If having an extra general purpose register is critical for performance of then this can be disabled in that program's the makefile.
Correct and there are already known exceptions such as the python interpreter in which the “interpret function” function actually falls into this case and so for the foreseeable future python is going to continue to be compiled omitting frame pointers. But by default this destructive micro optimization is off by default until proven a performance bottleneck, just like any performance issue should be!
Not really? I mean, there are architectures with fewer than 16 GP registers (IA32 is one of them); if you can compile some C code on that architecture, then surely you can also compile it on x86_64 with 15 (well, 14, really, due to the stack pointer also being reserved) rather than 16 (15).
If someone is writing in assembly, then they've already decided if they're going to allocate a register for the frame pointer, and Ubuntu's change isn't going to affect that, as this is about compiled code, not assembled assembly.
The only real issue is performance: if a program has a particular hot-path function (or just many functions overall) that really benefit from having that extra register available, and would otherwise have to spill data into memory, then this change could have a big negative impact. But that's not really a big deal; the packager can decide to omit frame pointers just for that particular app or library.
I thought modern speculative cpu’s had way more registers than you can normally access. Why does it reserve these registers for speculative execution instead of exposing them to the program if it needs them?
That's not really how registers or speculative execution works. Intuitively, you can think of assembly as trying to describe a graph of instruction dependencies. Having 16 registers in the ISA allows you to have 16 live outputs at any given "time". Speculative execution allows instructions to execute out-of-order, and to enable this, it has ~140 registers that allow it to have 140 live outputs at once, so that it can run some code while a really long load is waiting for its data.
From the ISA perspective, however, adding more registers means you have to spend more bits naming a register. With 16 registers, you need 12 bits of your instruction just to name the operands of a typical 3-address instruction (rA = rB op rC). With 128 registers, that is now a whopping 21 bits, which means code density is a more pressing issue.
I get that there is a tradeoff with code density, although if you could have an encoding scheme or extended register mode to alleviate this. I was just thinking that if you have e.g a loop where you run out of registers, since you only have 16, then the compiler will swap the values to memory and reuse that register which creates an instruction dependency that doesnt really have to exist.
If the compiler could use the hidden registers, then the cpu would know that it could run this instruction ahead of time.
It is probably not worth it, since it adds a lot of complexity to an already complex system, which is why it isn’t done.
All AMD64 CPUs support at least SSE2 which means they have 16 (not 15 or 14!) XMM registers they can spill to. This is just as fast as a move between two GPRs.
There is a difference between registers and register names.
he AMD64 architecture only has 15 general-purpose registers (because the stack pointer is mostly treated as if it were a GPR as well). It is customary to use one of those (bp/ebp/rbp depending on mode) as a base pointer register. That leaves 14 GPR register names.
The physical CPU the code runs on might have 200 physical registers -- those are the ones that matter for speculative, out-of-order execution -- but the code itself can only refer to 14 (or 15) GPRs at a time and has to include instructions to transfer values to/from memory or to/from XMM registers if that's not enough. Those extra instructions take up space + might slow the code down.
The number of registers available to the program is fixed in the instruction set. The program cannot address more registers without recompiling it to an extended instruction set.
Because then it would need more registers for the other purpose?
But actually the decision about which general purpose registers to use for what is made at compile time (hence we're discussion a compiler flag here, the frame pointer is not a hardware dictated feature), so the question is actually kind of moot. If the compiler is out of registers to allocate and instead uses the stack, the CPU isn't reasonably going to be able to undo that.
Sure, but wouldn’t it make sense to extend the instruction set to allow the compiler to use these registers instead of reserving them for speculative / out-of-order execution? It was just a thought i had after watching a talk by a compiler guy: https://youtu.be/2EWejmkKlxs?feature=shared&t=2409
jcranmer got it right. Read that reply (and mine). And then maybe rewatch watch Chandler Carruth says.
The current practice allows for CPUs to transparently increase their physical register count (to gain performance) and still run old code -- and older CPUs can still run new code. That's usually quite practical...
Adding more register names takes more bits for the register numbers -- which leads to larger instructions. It also leads to more complicated encodings if we want backwards compatibility. AMD64 does that by adding an optional prefix byte that carries a payload of 4 more instruction bits. That's one bit each for the three possible register names encoded in a traditional IA32 instruction + a bit to indicate whether to operate on 32-bit or 64-bit data (the actual rules are a bit more complex). Intel published a whitepaper recently suggesting a future encoding with a different (optional) prefix that encodes 8 more bits -- so each of the three register names can be extended to 5 bits (32 register names). It all ends up being quite complicated + new code won't run on older CPUs, which is not great.
I think you are suggesting not just bigger register names but also doing away with register renaming -- that would be... less than entirely useful because you would lose almost all your out-of-order capability and thereby almost all your ability to hide cache misses. Cache misses are very, very hard to predict statically (before actually running the code on a real CPU with real data) so good luck trying to do magic ahead-of-time allocation of those registers...
Comments
There are two key effects of this decision.
The first effect is that it makes one additional general-purpose integer register unavailable for use for code. x86-64 has 16 general-purpose registers, but one of these is the stack pointer and basically can't be used for any other purpose; this would add a second reserved register for the frame pointer. This effect may cause slowdowns if the 15th register was critical for performance.
The second effect is on the ability to identify (and potentially unwind) the stack trace. With frame pointers, the pseudocode for computing a stack trace is essentially:
Without frame pointers, the way you have to do this procedure is: It turns out that there is a full Turing-complete program described in the unwind tables to be able to generate a return address. This makes unwinding quite expensive, and also can create lots of security headaches if you want do something like unwind in the kernel (since the unwind table is arbitrary user code!). It can also be pretty unreliable at times, especially in cases where your program crashed due to stack smashing so that you have to expect that the data being randomly overwritten with garbage and thus horrifically inaccurate.Does this provide there any benefit at all to the majority of machines which aren't intended to be used for development of binaries (i.e. user workstations, developers working with interpreted languages, and servers), what would be the use cases where frame pointers would help on those machines?
Like, even for developers, I assume a random web development shop using Ubuntu and hosting stuff on Ubuntu would likely not ever attempt debugging a binary executable, and likely don't have any employees who could do it if they wanted. Of course there are companies who can and do debugging and profiling of binaries running on their servers, but IMHO those who are capable and willing to do that a relatively small minority of users of Ubuntu systems.
No benefit, but no downside either, its effectively irrelevant, an implementation detail.
Since it hasn't been mentioned in this entire thread, frame pointers are required to get good high resolution flame graphs.
https://www.brendangregg.com/flamegraphs.html
With systems like Phlare/Pyroscope SRE can monitor application performance in a very granular way in realtime.
https://grafana.com/blog/2023/03/15/pyroscope-grafana-phlare...
https://github.com/grafana/pyroscope
Could programs compiled in architectures with 16 general purpose registers fail in one with 15?
Well, for a start you probably mean compiled for an arch with 16 registers. It doesn't actually matter what arch the compiler ran on (assuming modern cross-compiler like GCC).
If a program uses 16 registers then it needs 16 registers. But note it's the program itself that decides to use a frame pointer, it's not being reserved by the operating system or something. Programs don't even have to use the stack pointer as a stack pointer, they could use all 16 as general purpose, but in practice almost all programs use a call stack (I guess all C programs must do, but you might be able to disable it if you make no function calls?)
Ohh, I misunderstood what Ubuntu was doing.
So the only change is that GCC and its toolkit will compile programs using a register as frame pointer by default? That seems like a very reasonable change. If having an extra general purpose register is critical for performance of then this can be disabled in that program's the makefile.
Correct and there are already known exceptions such as the python interpreter in which the “interpret function” function actually falls into this case and so for the foreseeable future python is going to continue to be compiled omitting frame pointers. But by default this destructive micro optimization is off by default until proven a performance bottleneck, just like any performance issue should be!
Not really? I mean, there are architectures with fewer than 16 GP registers (IA32 is one of them); if you can compile some C code on that architecture, then surely you can also compile it on x86_64 with 15 (well, 14, really, due to the stack pointer also being reserved) rather than 16 (15).
If someone is writing in assembly, then they've already decided if they're going to allocate a register for the frame pointer, and Ubuntu's change isn't going to affect that, as this is about compiled code, not assembled assembly.
The only real issue is performance: if a program has a particular hot-path function (or just many functions overall) that really benefit from having that extra register available, and would otherwise have to spill data into memory, then this change could have a big negative impact. But that's not really a big deal; the packager can decide to omit frame pointers just for that particular app or library.
I thought modern speculative cpu’s had way more registers than you can normally access. Why does it reserve these registers for speculative execution instead of exposing them to the program if it needs them?
That's not really how registers or speculative execution works. Intuitively, you can think of assembly as trying to describe a graph of instruction dependencies. Having 16 registers in the ISA allows you to have 16 live outputs at any given "time". Speculative execution allows instructions to execute out-of-order, and to enable this, it has ~140 registers that allow it to have 140 live outputs at once, so that it can run some code while a really long load is waiting for its data.
From the ISA perspective, however, adding more registers means you have to spend more bits naming a register. With 16 registers, you need 12 bits of your instruction just to name the operands of a typical 3-address instruction (rA = rB op rC). With 128 registers, that is now a whopping 21 bits, which means code density is a more pressing issue.
I get that there is a tradeoff with code density, although if you could have an encoding scheme or extended register mode to alleviate this. I was just thinking that if you have e.g a loop where you run out of registers, since you only have 16, then the compiler will swap the values to memory and reuse that register which creates an instruction dependency that doesnt really have to exist.
If the compiler could use the hidden registers, then the cpu would know that it could run this instruction ahead of time.
It is probably not worth it, since it adds a lot of complexity to an already complex system, which is why it isn’t done.
All AMD64 CPUs support at least SSE2 which means they have 16 (not 15 or 14!) XMM registers they can spill to. This is just as fast as a move between two GPRs.
There is a difference between registers and register names.
he AMD64 architecture only has 15 general-purpose registers (because the stack pointer is mostly treated as if it were a GPR as well). It is customary to use one of those (bp/ebp/rbp depending on mode) as a base pointer register. That leaves 14 GPR register names.
The physical CPU the code runs on might have 200 physical registers -- those are the ones that matter for speculative, out-of-order execution -- but the code itself can only refer to 14 (or 15) GPRs at a time and has to include instructions to transfer values to/from memory or to/from XMM registers if that's not enough. Those extra instructions take up space + might slow the code down.
The number of registers available to the program is fixed in the instruction set. The program cannot address more registers without recompiling it to an extended instruction set.
Because then it would need more registers for the other purpose?
But actually the decision about which general purpose registers to use for what is made at compile time (hence we're discussion a compiler flag here, the frame pointer is not a hardware dictated feature), so the question is actually kind of moot. If the compiler is out of registers to allocate and instead uses the stack, the CPU isn't reasonably going to be able to undo that.
Sure, but wouldn’t it make sense to extend the instruction set to allow the compiler to use these registers instead of reserving them for speculative / out-of-order execution? It was just a thought i had after watching a talk by a compiler guy: https://youtu.be/2EWejmkKlxs?feature=shared&t=2409
jcranmer got it right. Read that reply (and mine). And then maybe rewatch watch Chandler Carruth says.
The current practice allows for CPUs to transparently increase their physical register count (to gain performance) and still run old code -- and older CPUs can still run new code. That's usually quite practical...
Adding more register names takes more bits for the register numbers -- which leads to larger instructions. It also leads to more complicated encodings if we want backwards compatibility. AMD64 does that by adding an optional prefix byte that carries a payload of 4 more instruction bits. That's one bit each for the three possible register names encoded in a traditional IA32 instruction + a bit to indicate whether to operate on 32-bit or 64-bit data (the actual rules are a bit more complex). Intel published a whitepaper recently suggesting a future encoding with a different (optional) prefix that encodes 8 more bits -- so each of the three register names can be extended to 5 bits (32 register names). It all ends up being quite complicated + new code won't run on older CPUs, which is not great.
I think you are suggesting not just bigger register names but also doing away with register renaming -- that would be... less than entirely useful because you would lose almost all your out-of-order capability and thereby almost all your ability to hide cache misses. Cache misses are very, very hard to predict statically (before actually running the code on a real CPU with real data) so good luck trying to do magic ahead-of-time allocation of those registers...