3 ms·

I don't understand the point about tail call optimizations not being a part of C... Sure, but you can just rewrite the tail call into a loop and get the exact e

I don't understand the point about tail call optimizations not being a part of C... Sure, but you can just rewrite the tail call into a loop and get the exact effect, no?

moonchild 6y ago
I'm not sure what he was talking about, but I can make a guess. According to the sysv abi, every function has to have a stack frame; so for strict conformance (e.g. for unwinding the stack), you should have a stack frame for every function. In practice, this is kinda dumb. Gcc/clang will do TCO (and won't even generate a stack frame if you pass -fomit-frame-pointer). There's no particular reason why the generated code should abide internally by the sysv abi, only that it be able to call external code written according to said abi (and pass callbacks to said external code, but you'd need thunks for that anyway to account for closures).
- hyperion2010 6y ago
  I just wanted to record for posterity that after 14 years of reading it as fomit frame pointer this is the post where I finally realized that it is -f omit frame pointer. What are are fomit pointers and what do they do!? Well now I know.
  - agumonkey 6y ago
    And now I wonder what -f orce are
- yvdriess 6y ago
  (for context: -fomit-frame-pointer causes the FP to not be saved on the stack, stack unwinding then relies on DWARF or compiler-internal information to unwind the stack.) I don't see how that would have an effect on TCO, as the storing or not of the FP (beyond in a register) is not part of the calling convention AFAIK. - Only externally linked functions have to conform, so I can understand if TCO does not apply to mutually recursive external functions. Perhaps with LTO it can? - Even an external function that calls itself in tail-position should be TCO-able under -fno-omit-frame-pointer. The compiler reuses the same frame and generates a jump instead of a full function call.
  - moonchild 6y ago
    > I don't see how that would have an effect on TCO, as the storing or not of the FP (beyond in a register) is not part of the calling convention AFAIK Sysv abi[1], section 3.2.2: > In addition to registers, each function has a frame on the run-time stack So it is part of the calling convention. But again, this is IMO pedantry that doesn't really matter. > Even an external function that calls itself in tail-position should be TCO-able under -fno-omit-frame-pointer. The compiler reuses the same frame and generates a jump instead of a full function call Yes, I agree. Just interpreting what I think he meant. 1. https://raw.githubusercontent.com/wiki/hjl-tools/x86-psABI/x86-64-psABI-1.0.pdf https://raw.githubusercontent.com/wiki/hjl-tools/x86-psABI/x...
betterunix2 6y ago
No, because TCO only results in a loop when you have recursion, but there are other situations in which TCO can be applied to create an unconditional jump. TCO can also be applied when there is a pointer to a function (jump to a pointer target), and so in theory can be used for the C++ vtable. In some sense the reverse of what you said would be a better strategy: rewrite loops as tail calls. Doing that as part of the CPS conversion, and combining with TCO and a garbage collector, gives you a simple non-optimizing compiler for functional languages (but theoretically can be used for imperative languages like C, hence the conversion of a loop to a tail call).
Joker_vD 6y ago
Not unless it's the loop is made out several function calls. For example: def even(x): return x == 0 ? True : odd(x - 1) def odd(x): return x == 0 ? False : even(x - 1) print(even(17)) Properly implemented TCO means that the call to 'even(17)' should use only one stack frame.
- phoe-krk 6y ago
  > Properly implemented TCO Such is the case e.g. in Erlang/BEAM.

I don't understand the point about tail call optimizations not being a part of C... Sure, but you can just rewrite the tail call into a loop and get the exact effect, no?

moonchild 6y ago

I'm not sure what he was talking about, but I can make a guess. According to the sysv abi, every function has to have a stack frame; so for strict conformance (e.g. for unwinding the stack), you should have a stack frame for every function. In practice, this is kinda dumb. Gcc/clang will do TCO (and won't even generate a stack frame if you pass -fomit-frame-pointer). There's no particular reason why the generated code should abide internally by the sysv abi, only that it be able to call external code written according to said abi (and pass callbacks to said external code, but you'd need thunks for that anyway to account for closures).

hyperion2010 6y ago
I just wanted to record for posterity that after 14 years of reading it as fomit frame pointer this is the post where I finally realized that it is -f omit frame pointer. What are are fomit pointers and what do they do!? Well now I know.
- agumonkey 6y ago
  And now I wonder what -f orce are
yvdriess 6y ago
(for context: -fomit-frame-pointer causes the FP to not be saved on the stack, stack unwinding then relies on DWARF or compiler-internal information to unwind the stack.) I don't see how that would have an effect on TCO, as the storing or not of the FP (beyond in a register) is not part of the calling convention AFAIK. - Only externally linked functions have to conform, so I can understand if TCO does not apply to mutually recursive external functions. Perhaps with LTO it can? - Even an external function that calls itself in tail-position should be TCO-able under -fno-omit-frame-pointer. The compiler reuses the same frame and generates a jump instead of a full function call.
- moonchild 6y ago
  > I don't see how that would have an effect on TCO, as the storing or not of the FP (beyond in a register) is not part of the calling convention AFAIK Sysv abi[1], section 3.2.2: > In addition to registers, each function has a frame on the run-time stack So it is part of the calling convention. But again, this is IMO pedantry that doesn't really matter. > Even an external function that calls itself in tail-position should be TCO-able under -fno-omit-frame-pointer. The compiler reuses the same frame and generates a jump instead of a full function call Yes, I agree. Just interpreting what I think he meant. 1. https://raw.githubusercontent.com/wiki/hjl-tools/x86-psABI/x86-64-psABI-1.0.pdf https://raw.githubusercontent.com/wiki/hjl-tools/x86-psABI/x...

betterunix2 6y ago

No, because TCO only results in a loop when you have recursion, but there are other situations in which TCO can be applied to create an unconditional jump. TCO can also be applied when there is a pointer to a function (jump to a pointer target), and so in theory can be used for the C++ vtable. In some sense the reverse of what you said would be a better strategy: rewrite loops as tail calls. Doing that as part of the CPS conversion, and combining with TCO and a garbage collector, gives you a simple non-optimizing compiler for functional languages (but theoretically can be used for imperative languages like C, hence the conversion of a loop to a tail call).

Joker_vD 6y ago

Not unless it's the loop is made out several function calls. For example: def even(x): return x == 0 ? True : odd(x - 1) def odd(x): return x == 0 ? False : even(x - 1) print(even(17)) Properly implemented TCO means that the call to 'even(17)' should use only one stack frame.

phoe-krk 6y ago
> Properly implemented TCO Such is the case e.g. in Erlang/BEAM.