BAR: |
PUSHJ [BAR1]
|
<set up arguments for G>
| |
JUMP G
| |
BAR1: |
<save result from G>
|
PUSH [BAR2]
| |
<set up arguments for H>
| |
JUMP H
| |
BAR2: |
<use results from G and H for F>
|
JUMP F
|
We did not push a return address for F since the call to F is not an argument form. Notice that this uniform discipline lends itself to passing arguments on the stack, above the return address. The called procedure is then responsible for popping the arguments. On the other hand, if argument passing does not use the stack, we can permute the PUSH of the return address with the argument set-up code:
BAR: |
<set up arguments for G>
|
PUSHJ [BAR1]
| |
JUMP G
| |
BAR1: |
<save result from G>
|
PUSH [BAR2]
| |
<set up arguments for H>
| |
JUMP H
| |
BAR2: |
<use results from G and H for F>
|
JUMP F
|
If our machine has a PUSHJ instruction, then a peephole optimization [McK65] can now transform the PUSH/JUMP sequence into a single PUSHJ instruction. Thus we see that a procedure call can be uniformly treated as a GOTO, with the PUSHJ instruction considered an optimization (rather than vice versa!).
There are a couple of difficulties with this idea. One is that the stack is often used to hold information other than return addresses, such as stack-allocated data structures and intermediate results. This is no problem, as it turns out; it is merely necessary to clean up the stack just before calling F, rather than just after calling F; then the original PUSHJ F and the POPJ will be consecutive, and so can be expressed as a JUMP F. {Note Shuffle Arguments}
This leads to a second difficulty, which is that some languages would allow F to refer globally to stack-allocated structures within BAR, such as the dynamic values of X and Y. In this case we cannot clean up the stack until after calling F. There is, however, some evidence [Wul73] that such global variables are as "harmful" as GOTO statements; in any case it is a good idea to minimize their use, and to define variables to be lexical in scope by default. It turns out that in most programming languages (COBOL, PL/I, FORTRAN. and LISP in particular) the distinction between lexical and dynamic scoping doesn't matter most of the time anyway. We should leave the compiler free to produce the best possible code; only in cases where structures are explicitly declared to be dynamically referenced should the compiler be forced to leave them on the stack in an otherwise tail-recursive situation.
In general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly encoded as JUMP instructions. This is a simple, universal technique, to be contrasted with the more powerful recursion-removal techniques such as those in [Dar76]. Our approach results in all tail-recursive procedure calls being compiled as
