5 ms·

Speaking of TCO constraints, all of the common C/C++ calling conventions[0] have a fixed size stack cleanup. Some are caller-cleanup and some are callee-cleanu

by KMag 6y ago

Speaking of TCO constraints, all of the common C/C++ calling conventions[0] have a fixed size stack cleanup. Some are caller-cleanup and some are callee-cleanup, but they all have amounts of stack cleanup that are constant (cdecl,stdcall,thiscal, etc.) or at least fixed at call time (varargs). This means that TCO can't be done across calls where the amount of stack space used for arguments in the callee is larger than that of the caller. (In cases where the stack space used by the callee is less than the caller, the caller just needs to leave "wasted" stack space as if amount of stack space used by arguments were the same.) It wouldn't be much of a point on architectures where the cdecl calling convention passes enough arguments in registers to cover the majority of functions, except that some of these ABIs (notably Windows x64 calling convetion, but not Linux x64_64 SysV ABI) require the caller to allocate shadow space on the stack for all register-passed arguments. (Edit: I was wrong, the Windows shadow space on the stack is a fixed 32 bytes, regardless of the number of register-passed arguments.) This motivates a couple of ABI questions: 1. Why does the Windows x64 ABI require the caller to pre-allocate "shadow space" to potentially spill register-passed arguments? It's wasteful if it's not needed (especially in ABIs with a redzone), and it reduces opportunities for TCO. (Edit: ahh, unlike Linux, the Windows x64 calling convention has no redzone. I guess this then becomes "Why doesn't Windows x64 provide a redzone?") 2. Why not define a calling convention that is callee-cleanup where the post-cleanup stack pointer is passed in a designated register (or at the top of the stack) to the callee? I understand that it might not make sense to pay the cost (fewer arguments passed in registers, and often an extra stack spill) for the majority of functions, but it seems an oversight that there's not a calling convention that (in the absence of destructors) always allows tail calls to be optimized. I guess the answer to both questions is that most TCO opportunities are within a single DLL, so the compiler is free to create non-exported versions of functions with custom calling conventions. Is this right? [0] https://en.wikipedia.org/wiki/X86_calling_conventions https://en.wikipedia.org/wiki/X86_calling_conventions plus their variants on other architectures

johncolanduoni 6y ago
> I guess the answer to both questions is that most TCO opportunities are within a single DLL, so the compiler is free to create non-exported versions of functions with custom calling conventions. Is this right? LLVM mostly follows this path: it allows full TCO only when using the “fastcc” (i.e. “whatever LLVM feels like generating”) and some calling conventions from functional languages (like GHC) that have a specific carve out for it.
DarkWiiPlayer 6y ago
Correct me if I'm saying something stupid, but: Shouldn't TCE be trivial with callee cleanup? When I (the function) get called, I get X bytes of stack in arguments, then start pushing variables and whatnot. When I return, I simply put my return value at the start of my stack space, pop everything else, then jump back. In a tail call, all I need to do is put the next functions arguments at the start of my stack space, pop everything else, then jump to its address. Obviously in IRL CPUs some of this data would be kept in registers instead of the stack, but the mechanism should be the same.
- KMag 6y ago
  You're correct, I did overgeneralize in the case of callee-cleanup calling conventions. Though, I'm still not aware of any callee-cleanup variadic calling conventions. printf, execl, etc. doen't actually get passed anything that directly indicates the number/size of arguments passed. In the article's printf example, the compiler is able to perform TCO only because it uses at most 5 pointer/integer arguments (with number of fp arguments passed in al) and at most 6 fp arguments, so it's caller-cleanup, but with no cleanup to perform. Under SvsV (Linux, etc.) x86_64 ABI, varargs calls, the number of fp arguments passed in XMMx registers is passed in al, but nothing to directly indicate how much stack space is used by arguments (and it's also obviously caller-cleanup). The printf example from the article works because all of the arguments fit in registers.

by KMag 6y ago

johncolanduoni 6y ago

> I guess the answer to both questions is that most TCO opportunities are within a single DLL, so the compiler is free to create non-exported versions of functions with custom calling conventions. Is this right? LLVM mostly follows this path: it allows full TCO only when using the “fastcc” (i.e. “whatever LLVM feels like generating”) and some calling conventions from functional languages (like GHC) that have a specific carve out for it.

DarkWiiPlayer 6y ago

Correct me if I'm saying something stupid, but: Shouldn't TCE be trivial with callee cleanup? When I (the function) get called, I get X bytes of stack in arguments, then start pushing variables and whatnot. When I return, I simply put my return value at the start of my stack space, pop everything else, then jump back. In a tail call, all I need to do is put the next functions arguments at the start of my stack space, pop everything else, then jump to its address. Obviously in IRL CPUs some of this data would be kept in registers instead of the stack, but the mechanism should be the same.

KMag 6y ago
You're correct, I did overgeneralize in the case of callee-cleanup calling conventions. Though, I'm still not aware of any callee-cleanup variadic calling conventions. printf, execl, etc. doen't actually get passed anything that directly indicates the number/size of arguments passed. In the article's printf example, the compiler is able to perform TCO only because it uses at most 5 pointer/integer arguments (with number of fp arguments passed in al) and at most 6 fp arguments, so it's caller-cleanup, but with no cleanup to perform. Under SvsV (Linux, etc.) x86_64 ABI, varargs calls, the number of fp arguments passed in XMMx registers is passed in al, but nothing to directly indicate how much stack space is used by arguments (and it's also obviously caller-cleanup). The printf example from the article works because all of the arguments fit in registers.