3 ms·

When the calling convention is such that the caller owns the function arguments, the callee can’t remove/replace them on the stack, but has to keep them across

by layer8 2mo ago

When the calling convention is such that the caller owns the function arguments, the callee can’t remove/replace them on the stack, but has to keep them across the tail call. In turn, it means that the callee has to clean up the arguments to the tail call, and thus can’t actually make a tail call, unless the argument list happens to be identical to the original call.

fluoridation 2mo ago
But the compiler controls both the caller and callee. It doesn't need to respect any calling convention during a TCO. In fact it won't; it'll jump instead of calling.
- uecker 2mo ago
  It is usually assumed that it does not control the callee and the jump has to preserve the calling convention for a call.
  - fluoridation 2mo ago
    If it doesn't control both then TCO is impossible, because the stack will grow with each recursive step, as it's just performing a normal call.
    - layer8 2mo ago
      It's possible for calling conventions where the callee is responsible for stack cleanup before return.
    - uecker 2mo ago
      Have your mind blown: https://godbolt.org/z/xnn3PPxvW https://godbolt.org/z/xnn3PPxvW
      - fluoridation 2mo ago
        Extremely specific example is uncompelling.
        uecker 2mo ago
        It is a simple counterexample to your incorrect statement.
        fluoridation 2mo ago
        It's still impossible in the general case, where not all arguments are passable by registers.
        uecker 2mo ago
        You are right that there are cases where it is not possible. But it also works when arguments are not passed in registers. The condition then is that there are less stack slots used than in the caller. https://godbolt.org/z/M4Eqzh3YE https://godbolt.org/z/M4Eqzh3YE
- toast0 2mo ago
  > But the compiler controls both the caller and callee. Why? In functional languages, it's common for an exported function from one compilation context to tail call into an exported function from another.
  - fluoridation 2mo ago
    Functional languages may be designed to support TCO from the ground up, up to supporting it across module boundaries. C is not like that, and calling into an external module necessarily grows the stack.
    - toast0 2mo ago
      > C is not like that, and calling into an external module necessarily grows the stack. This is because of the calling convention, yes? (and to some extent, if you want an accurate stack trace, but I find it acceptable that TCO also includes stack trace erasure)
      - fluoridation 2mo ago
        Yyyyes... But like I said, TCO cannot make use of the calling convention, because it doesn't involve calling. That means you can't have TCO loops crossing module boundaries (or function pointers for that matter). So we're back to my original question: what does it matter what the calling convention is if the compiler has the liberty to compile both functions however it pleases?
        toast0 2mo ago
        With the right calling convention, tail calls could conform to the convention. A tail call certainly can't use a CALL instruction, because it would set the wrong return address. But that doesn't mean it's not a call; architectures without CALL/RETURN instructions exist, but you can still call into functions and return from them, the compiler just has to do different work. In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee. The original caller and the tail callee would be none the wiser. I don't know enough to really evaluate calling conventions against each other, but it's pretty clear that caller cleanup makes tail call optimization more intrusive.
- layer8 2mo ago
  If the callee is an exported symbol, the compiler has no choice but to adhere to the calling convention. For the C model of translation units that's the default, only local (declared "static") functions are exempted, and usually also only if their address is not taken. More generally, when the tail call crosses the boundaries of modularization that are supported by separate compilation, a recompilation step at the module-linking level would be required. The other complication is function pointers, which assume a specific calling convention, so either you have to have different function-pointer types with different calling conventions, or the compiler has to generate thunks or similar that translate between different calling conventions. Of course, a language implementation can arrange for all that; but clearly, calling conventions are relevant here.
  - fluoridation 2mo ago
    Do you often find yourself doing mutual recursion between functions crossing compilation units/modules? I'm not going to say it can't happen, I just don't see it as much of a problem.
    - layer8 2mo ago
      The point is that the compiler has to deal with it and has to check if the function is exported or its address is taken. So it’s a problem when implementing the compiler and adjacent tooling, you can’t just add it naively. You also have to document the side conditions under which TCO will or won’t happen, which the programmer will have to take into account. If on the other hand the regular calling convention is compatible with TCO, then everything becomes much simpler, because it fits in with the existing model.
      - fluoridation 2mo ago
        >The point is that the compiler has to deal with it and has to check if the function is exported or its address is taken. Like I said in a different comment below, these are not obstacles for TCO. The compiler can simply emit a second copy of the function that doesn't need to honor a calling convention. >So it’s a problem when implementing the compiler and adjacent tooling Yeah, implementing a compiler is difficult work. Who ever said otherwise? I originally responded to a comment talking about TCO being incompatible with certain calling conventions. I.e. if your platform uses a certain calling convention then TCO is impossible. That's what it means for two things to be incompatible: you can have either one or the other, but not both at the same time.

by layer8 2mo ago

fluoridation 2mo ago

But the compiler controls both the caller and callee. It doesn't need to respect any calling convention during a TCO. In fact it won't; it'll jump instead of calling.

uecker 2mo ago
It is usually assumed that it does not control the callee and the jump has to preserve the calling convention for a call.
- fluoridation 2mo ago
  If it doesn't control both then TCO is impossible, because the stack will grow with each recursive step, as it's just performing a normal call.
  - layer8 2mo ago
    It's possible for calling conventions where the callee is responsible for stack cleanup before return.
  - uecker 2mo ago
    Have your mind blown: https://godbolt.org/z/xnn3PPxvW https://godbolt.org/z/xnn3PPxvW
    - fluoridation 2mo ago
      Extremely specific example is uncompelling.
      - uecker 2mo ago
        It is a simple counterexample to your incorrect statement.
        fluoridation 2mo ago
        It's still impossible in the general case, where not all arguments are passable by registers.
        uecker 2mo ago
        You are right that there are cases where it is not possible. But it also works when arguments are not passed in registers. The condition then is that there are less stack slots used than in the caller. https://godbolt.org/z/M4Eqzh3YE https://godbolt.org/z/M4Eqzh3YE
toast0 2mo ago
> But the compiler controls both the caller and callee. Why? In functional languages, it's common for an exported function from one compilation context to tail call into an exported function from another.
- fluoridation 2mo ago
  Functional languages may be designed to support TCO from the ground up, up to supporting it across module boundaries. C is not like that, and calling into an external module necessarily grows the stack.
  - toast0 2mo ago
    > C is not like that, and calling into an external module necessarily grows the stack. This is because of the calling convention, yes? (and to some extent, if you want an accurate stack trace, but I find it acceptable that TCO also includes stack trace erasure)
    - fluoridation 2mo ago
      Yyyyes... But like I said, TCO cannot make use of the calling convention, because it doesn't involve calling. That means you can't have TCO loops crossing module boundaries (or function pointers for that matter). So we're back to my original question: what does it matter what the calling convention is if the compiler has the liberty to compile both functions however it pleases?
      - toast0 2mo ago
        With the right calling convention, tail calls could conform to the convention. A tail call certainly can't use a CALL instruction, because it would set the wrong return address. But that doesn't mean it's not a call; architectures without CALL/RETURN instructions exist, but you can still call into functions and return from them, the compiler just has to do different work. In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee. The original caller and the tail callee would be none the wiser. I don't know enough to really evaluate calling conventions against each other, but it's pretty clear that caller cleanup makes tail call optimization more intrusive.
layer8 2mo ago
If the callee is an exported symbol, the compiler has no choice but to adhere to the calling convention. For the C model of translation units that's the default, only local (declared "static") functions are exempted, and usually also only if their address is not taken. More generally, when the tail call crosses the boundaries of modularization that are supported by separate compilation, a recompilation step at the module-linking level would be required. The other complication is function pointers, which assume a specific calling convention, so either you have to have different function-pointer types with different calling conventions, or the compiler has to generate thunks or similar that translate between different calling conventions. Of course, a language implementation can arrange for all that; but clearly, calling conventions are relevant here.
- fluoridation 2mo ago
  Do you often find yourself doing mutual recursion between functions crossing compilation units/modules? I'm not going to say it can't happen, I just don't see it as much of a problem.
  - layer8 2mo ago
    The point is that the compiler has to deal with it and has to check if the function is exported or its address is taken. So it’s a problem when implementing the compiler and adjacent tooling, you can’t just add it naively. You also have to document the side conditions under which TCO will or won’t happen, which the programmer will have to take into account. If on the other hand the regular calling convention is compatible with TCO, then everything becomes much simpler, because it fits in with the existing model.
    - fluoridation 2mo ago
      >The point is that the compiler has to deal with it and has to check if the function is exported or its address is taken. Like I said in a different comment below, these are not obstacles for TCO. The compiler can simply emit a second copy of the function that doesn't need to honor a calling convention. >So it’s a problem when implementing the compiler and adjacent tooling Yeah, implementing a compiler is difficult work. Who ever said otherwise? I originally responded to a comment talking about TCO being incompatible with certain calling conventions. I.e. if your platform uses a certain calling convention then TCO is impossible. That's what it means for two things to be incompatible: you can have either one or the other, but not both at the same time.