4 ms·

So every function call will need to spill even more call-clobbered registers to the stack! Like, I get that leaf functions with truly huge computational cores

So every function call will need to spill even more call-clobbered registers to the stack! Like, I get that leaf functions with truly huge computational cores are a thing that would benefit from more ISA-visible registers, but... don't we have GPUs for that now? And TPUs? NPUs? Whatever those things are called?

throwaway17_17 9mo ago
Why does having more more registers lead to spilling? I would assume (probably) incorrectly, that more registers means less spill. Are you talking about calls inside other calls which cause the outer scope arguments to be preemptively spilled so the inner scope data can be pre placed in registers?
- CamelCaseCondo 9mo ago
  op is probably referring to the push all/pop all approach.
  - Joker_vD 9mo ago
    No, I don't. I use a common "spill definitely reused call-invariant registers at the prologue, spill call-clobbered registers that need to survive a call at precisely the call site" approach, see the sibling comment for the arithmetic.
    - saagarjha 9mo ago
      That’s the push all/pop all approach.
- Joker_vD 9mo ago
  So, let's take a function with 40 alive temporaries at a point where it needs to call a helper function of, say, two arguments. On a 16 register machine with 9 call-clobbered registers and 7 call-invariant ones (one of which is the stack pointer) we put 6 temporaries into call-invariant registers (so there are 6 spills in the prologue of this big function), another 9 into the call-clobbered registers; 2 of those 9 are the helper function's arguments, but 7 other temporaries have to be spilled to survive the call. And the rest 25 temporaries live on the stack in the first place. If we instead take a machine with 31 registers, 19 being call-clobbered and 12 call-invariant ones (one of which is a stack pointer), we can put 11 temporaries into call-invariant registers (so there are 11 spills in the prologue of this big function), and another 19 into the call-clobbered registers; 2 of those 19 are the helper function's arguments, so 17 other temporaries have to be spilled to survive the call. And the rest of 10 temporaries live on the stack in the first place. So, there seems to be more spilling/reloading whether you count pre-emptive spills or the on-demand-at-the-call-site spills, at least to me.
  - cv5005 9mo ago
    A good compiler will only do that if the register spilling is more efficient than using more stack varibles, so I don't really see the problem.
    - Joker_vD 9mo ago
      You can't operate on stack variables without loading them into the registers first, not on RISCs anyway. My main point is that this memory-shuffling traffic is unavoidable in non-leaf functions, so an extremely large amount of available registers doesn't really help them.
  - mjevans 9mo ago
    I recalled there were some new instructions added that greatly help with this. Unfortunately I'm not finding any good _webpages_ that describe the operation generally to give me a good overview / refresher. Everything seems to either directly quote published PDF documents or otherwise not actually present the information in it's effective for end use form. E.G. https://www.felixcloutier.com/x86/ https://www.felixcloutier.com/x86/ -- However availability is problematic for even slightly older silicon https://en.wikipedia.org/wiki/X86-64 https://en.wikipedia.org/wiki/X86-64 - XSAVE / XRSTOR - XSAVEOPT / XRSTOR - XSAVEC / XRSTOR - XSAVES / XRSTORS
    - Joker_vD 9mo ago
      Eh, pretty much nobody uses them (outside of OS kernels?); and mind you, RISC-V with its 32 registers has nothing similar to those, which is why 14-instruction long prologues (adjust sp, save lr and s0 through s12) and epilogues are not that uncommon there.
  - csjh 9mo ago
    You’re missing the fact that the compiler isn’t forced to fill every register in the first place. If it was less efficient to use more registers, the compiler simply wouldn’t use more registers. The actual counter proof here would be that in either case, the temporaries have to end up on the stack at some point anyways, so you’d need to look at the total number of loads/stores in the proximity of the call site in general.
- BeeOnRope 9mo ago
  More registers leads to less spilling not more, unless the compiler is making some really bad choices. Any easy way to see that is that the system with more registers can always use the same register allocation as the one with fewer, ignoring the extra registers, if that's profitable (i.e. it's not forced into using extra caller-saved registers if it doesn't want to).
  - adrian_b 9mo ago
    Yes, the argument for increasing the number of GPRs is precisely to eliminate the register spilling that in necessary in x86-64 programs whenever a program has already used all available architectural registers, a register spilling that does not happen whenever the same program is compiled for Aarch64 or IBM POWER.
jandrewrogers 9mo ago
Most function calls are aggressively inlined by the compiler such that they are no longer "function calls". More registers will make that even more effective.
- burnt-resistor 9mo ago
  That depends on if something like LTO is possible and a function isn't declared to use one of the plethora of calling conventions. What it means is that new calling conventions will be needed and that this new platform will be able to use pass by register for higher arity functions.
  - menaerus 9mo ago
    LTO is orthogonal to inlining functions.
bjourne 9mo ago
Most modern compilers for modern languages do an insane amount of inlining so the problem you're mentioning isn't a big issue. And, basically, GPUs and TPUs can't handle branches. CPUs can.
cvoss 9mo ago
With an increase in available registers, every value that a compiler might newly choose to keep in a register was a value that would previously have lived in the local stack frame anyway. It's up to the compiler to decide how many registers it needs to preserve at a call. It's also up to the compiler to decide which registers shall be the call-clobbered ones. "None" is a valid choice here, if you wish.
- guenthert 9mo ago
  > It's up to the compiler to decide how many registers it needs to preserve at a call. But the compiler is bound by the ABI, isn't it? (at least for externally visible entrance points / calls to sub routines external to the current compilation unit)
  - cvoss 9mo ago
    Someone decides how to define the ABI too, and that is a free choice. CPU register count doesn't constrain this particular system design question.
adrian_b 9mo ago
ARM Aarch64, IBM POWER and most RISC CPUs have had 32 general-purpose registers for many decades, and this has always been an advantage for them, not a disadvantage. So there already is plenty of experience with ABIs using 32 GPRs. Even so, unnecessary spilling could be avoided, but that would require some changes in programmer habits. For instance, one could require an ordering of the compilation of source files, e.g. to always compile the dependencies of a program module before it. Then the compiler could annotate the module interfaces with register usage and then use this annotations when compiling a program that imports the modules. This would avoid the need to define an ABI that is never optimal in most cases, by either saving too many or too few registers.
- Joker_vD 9mo ago
  Yeah, this approach has been proposed, in an even more aggressive form, see David W. Wall, "Global Register Allocation at Link Time", 1986 [0], specifically for machines with large number of registers: the paper straight up says that it's much less of a problem if you a) have less registers, b) don't compile things separately. And this problem with large register files has been predicted long before, see wonderfully named "How to Use 1000 Registers", 1979 by Richard L. Sites (he would later go work on VAX and design Alpha ISA at DEC). [0] https://dl.acm.org/doi/10.1145/12276.13338 https://dl.acm.org/doi/10.1145/12276.13338 [1] https://files01.core.ac.uk/download/pdf/9412584.pdf https://files01.core.ac.uk/download/pdf/9412584.pdf
  - adrian_b 9mo ago
    Thanks for the links. Register allocation at link time would work only for ISAs where all registers are equivalent or they are partitioned only in a small number of equivalence classes. It cannot work for an ISA like x86-64, where register allocation and instruction choice are extremely interdependent (e.g. the 16 Intel-AMD general-purpose registers are partitioned into 11 equivalence classes, instead of in at most 2 to 4 equivalence classes, like in the majority of other ISAs, where only a stack pointer and perhaps a return link pointer and/or a null register may have a special behavior). With such an ISA, the compiler must know the exact register allocation before choosing instructions, otherwise the generated program can be much worse than an optimum program. Moreover, an ideal optimizing compiler for x86-64 might need to generate instructions for several alternative register allocations, then select the best allocation and generate the definitive instruction sequence. With such a non-orthogonal ISA, like x86-64, for the best results you need to allocate registers based on the register usage of the invoked procedures, as assembly programmers typically do, instead of using a uniform sub-optimal ABI, like most compilers.
crest 9mo ago
Big non-trivial functions generally profit from having more registers. They don't have to saved and restored by functions that don't use them. Not every computationally intense application has just a few numerical kernels that can be pushed on to GPUs and fit the GPU uarch well. Just have a look at the difference between optimized compiler generated ia32 and amd64 code how much difference more registers can make. You could argue that 16 (integer) registers is a sweet spot, but you failed to state a proper argument.

throwaway17_17 9mo ago

Why does having more more registers lead to spilling? I would assume (probably) incorrectly, that more registers means less spill. Are you talking about calls inside other calls which cause the outer scope arguments to be preemptively spilled so the inner scope data can be pre placed in registers?

CamelCaseCondo 9mo ago
op is probably referring to the push all/pop all approach.
- Joker_vD 9mo ago
  No, I don't. I use a common "spill definitely reused call-invariant registers at the prologue, spill call-clobbered registers that need to survive a call at precisely the call site" approach, see the sibling comment for the arithmetic.
  - saagarjha 9mo ago
    That’s the push all/pop all approach.
Joker_vD 9mo ago
So, let's take a function with 40 alive temporaries at a point where it needs to call a helper function of, say, two arguments. On a 16 register machine with 9 call-clobbered registers and 7 call-invariant ones (one of which is the stack pointer) we put 6 temporaries into call-invariant registers (so there are 6 spills in the prologue of this big function), another 9 into the call-clobbered registers; 2 of those 9 are the helper function's arguments, but 7 other temporaries have to be spilled to survive the call. And the rest 25 temporaries live on the stack in the first place. If we instead take a machine with 31 registers, 19 being call-clobbered and 12 call-invariant ones (one of which is a stack pointer), we can put 11 temporaries into call-invariant registers (so there are 11 spills in the prologue of this big function), and another 19 into the call-clobbered registers; 2 of those 19 are the helper function's arguments, so 17 other temporaries have to be spilled to survive the call. And the rest of 10 temporaries live on the stack in the first place. So, there seems to be more spilling/reloading whether you count pre-emptive spills or the on-demand-at-the-call-site spills, at least to me.
- cv5005 9mo ago
  A good compiler will only do that if the register spilling is more efficient than using more stack varibles, so I don't really see the problem.
  - Joker_vD 9mo ago
    You can't operate on stack variables without loading them into the registers first, not on RISCs anyway. My main point is that this memory-shuffling traffic is unavoidable in non-leaf functions, so an extremely large amount of available registers doesn't really help them.
- mjevans 9mo ago
  I recalled there were some new instructions added that greatly help with this. Unfortunately I'm not finding any good _webpages_ that describe the operation generally to give me a good overview / refresher. Everything seems to either directly quote published PDF documents or otherwise not actually present the information in it's effective for end use form. E.G. https://www.felixcloutier.com/x86/ https://www.felixcloutier.com/x86/ -- However availability is problematic for even slightly older silicon https://en.wikipedia.org/wiki/X86-64 https://en.wikipedia.org/wiki/X86-64 - XSAVE / XRSTOR - XSAVEOPT / XRSTOR - XSAVEC / XRSTOR - XSAVES / XRSTORS
  - Joker_vD 9mo ago
    Eh, pretty much nobody uses them (outside of OS kernels?); and mind you, RISC-V with its 32 registers has nothing similar to those, which is why 14-instruction long prologues (adjust sp, save lr and s0 through s12) and epilogues are not that uncommon there.
- csjh 9mo ago
  You’re missing the fact that the compiler isn’t forced to fill every register in the first place. If it was less efficient to use more registers, the compiler simply wouldn’t use more registers. The actual counter proof here would be that in either case, the temporaries have to end up on the stack at some point anyways, so you’d need to look at the total number of loads/stores in the proximity of the call site in general.
BeeOnRope 9mo ago
More registers leads to less spilling not more, unless the compiler is making some really bad choices. Any easy way to see that is that the system with more registers can always use the same register allocation as the one with fewer, ignoring the extra registers, if that's profitable (i.e. it's not forced into using extra caller-saved registers if it doesn't want to).
- adrian_b 9mo ago
  Yes, the argument for increasing the number of GPRs is precisely to eliminate the register spilling that in necessary in x86-64 programs whenever a program has already used all available architectural registers, a register spilling that does not happen whenever the same program is compiled for Aarch64 or IBM POWER.

jandrewrogers 9mo ago

Most function calls are aggressively inlined by the compiler such that they are no longer "function calls". More registers will make that even more effective.

burnt-resistor 9mo ago
That depends on if something like LTO is possible and a function isn't declared to use one of the plethora of calling conventions. What it means is that new calling conventions will be needed and that this new platform will be able to use pass by register for higher arity functions.
- menaerus 9mo ago
  LTO is orthogonal to inlining functions.

bjourne 9mo ago

Most modern compilers for modern languages do an insane amount of inlining so the problem you're mentioning isn't a big issue. And, basically, GPUs and TPUs can't handle branches. CPUs can.

cvoss 9mo ago

With an increase in available registers, every value that a compiler might newly choose to keep in a register was a value that would previously have lived in the local stack frame anyway. It's up to the compiler to decide how many registers it needs to preserve at a call. It's also up to the compiler to decide which registers shall be the call-clobbered ones. "None" is a valid choice here, if you wish.

guenthert 9mo ago
> It's up to the compiler to decide how many registers it needs to preserve at a call. But the compiler is bound by the ABI, isn't it? (at least for externally visible entrance points / calls to sub routines external to the current compilation unit)
- cvoss 9mo ago
  Someone decides how to define the ABI too, and that is a free choice. CPU register count doesn't constrain this particular system design question.

adrian_b 9mo ago

ARM Aarch64, IBM POWER and most RISC CPUs have had 32 general-purpose registers for many decades, and this has always been an advantage for them, not a disadvantage. So there already is plenty of experience with ABIs using 32 GPRs. Even so, unnecessary spilling could be avoided, but that would require some changes in programmer habits. For instance, one could require an ordering of the compilation of source files, e.g. to always compile the dependencies of a program module before it. Then the compiler could annotate the module interfaces with register usage and then use this annotations when compiling a program that imports the modules. This would avoid the need to define an ABI that is never optimal in most cases, by either saving too many or too few registers.

Joker_vD 9mo ago
Yeah, this approach has been proposed, in an even more aggressive form, see David W. Wall, "Global Register Allocation at Link Time", 1986 [0], specifically for machines with large number of registers: the paper straight up says that it's much less of a problem if you a) have less registers, b) don't compile things separately. And this problem with large register files has been predicted long before, see wonderfully named "How to Use 1000 Registers", 1979 by Richard L. Sites (he would later go work on VAX and design Alpha ISA at DEC). [0] https://dl.acm.org/doi/10.1145/12276.13338 https://dl.acm.org/doi/10.1145/12276.13338 [1] https://files01.core.ac.uk/download/pdf/9412584.pdf https://files01.core.ac.uk/download/pdf/9412584.pdf
- adrian_b 9mo ago
  Thanks for the links. Register allocation at link time would work only for ISAs where all registers are equivalent or they are partitioned only in a small number of equivalence classes. It cannot work for an ISA like x86-64, where register allocation and instruction choice are extremely interdependent (e.g. the 16 Intel-AMD general-purpose registers are partitioned into 11 equivalence classes, instead of in at most 2 to 4 equivalence classes, like in the majority of other ISAs, where only a stack pointer and perhaps a return link pointer and/or a null register may have a special behavior). With such an ISA, the compiler must know the exact register allocation before choosing instructions, otherwise the generated program can be much worse than an optimum program. Moreover, an ideal optimizing compiler for x86-64 might need to generate instructions for several alternative register allocations, then select the best allocation and generate the definitive instruction sequence. With such a non-orthogonal ISA, like x86-64, for the best results you need to allocate registers based on the register usage of the invoked procedures, as assembly programmers typically do, instead of using a uniform sub-optimal ABI, like most compilers.

crest 9mo ago

Big non-trivial functions generally profit from having more registers. They don't have to saved and restored by functions that don't use them. Not every computationally intense application has just a few numerical kernels that can be pushed on to GPUs and fit the GPU uarch well. Just have a look at the difference between optimized compiler generated ia32 and amd64 code how much difference more registers can make. You could argue that 16 (integer) registers is a sweet spot, but you failed to state a proper argument.