search

jkotlinski / durexforth

Modern C64 Forth
Other
233 stars 28 forks source link

Document tail call elimination #278

Closed jkotlinski closed 2 years ago

jkotlinski commented 4 years ago

What is it and when is it guaranteed to happen?

burnsauce commented 2 years ago

My understanding is this:

Tail call elimination is a compile optimization that replaces the final jsr/rts of a word with a jmp to save code size and improve performance.

Some words are not eligible for tail call elimination when they occur as the last word in a word's definition.

From what I can tell, the following are the only words without tail call elimination: ], :, unloop, >r, r>, r@

The rationale for some of these is that they do not end with rts or jsr, hence there is no opportunity to jump to them knowing that they will return properly.

Some of them I don't know the reason.

jkotlinski commented 2 years ago

>r, r>, r@ and unloop directly manipulate the return stack. They assume that the top of return stack contains a return adress. As such, they need to be called using jsr, as a jmp will not push a return address to the return stack.

jkotlinski commented 2 years ago

immediate words are not subject to tail-call elimination. The reason is that immediate words have custom compile-time behavior. As such, it cannot be assumed that tail-call elimination applies.

jkotlinski commented 2 years ago

] is not subject to tail-call elimination, since it does not compile a jsr. Consider the following word definition:

: nop [ ] ;

Replacing the last jsr with jmp would fail, since no jsr has been compiled.

jkotlinski commented 2 years ago

: is not subject to tail-call elimination, since it does not compile a jsr. Consider the following word definition:

: nop ;

Replacing the last jsr with a jmp would fail, since no jsr has been compiled.

jkotlinski commented 2 years ago

I think those are all the facts, that need to be served...

burnsauce commented 2 years ago

Great! I'll put that in TeX format.

jkotlinski commented 2 years ago

Maybe the particular explanations why certain words are exempt from TCE belong more in source code than manual. I will do that, it should not be much work.

jkotlinski commented 2 years ago

...it might be fine to mention some of these words in manual, but everything seems like a bit much maybe.

burnsauce commented 2 years ago

Hmm. The manual has a few more pressing shortcomings that make any further elaboration on tail call elimination a bit unnecessary.

Thanks for the source docs! They were enlightening, for sure.

jkotlinski commented 2 years ago

If further documentation is a bit unnecessary, perhaps this issue can be now closed?