About a week ago, Bruce Hoult <bruce@hoult.org> wrote:
+---------------
| Erik Naggum <erik@naggum.net> wrote:
| > As we investigate this, more and more context turns out to
| > to be required to determine whether we have a "final" function call.
|
| This is hardly surprising. At heart, the idea of tail-call merging
| comes from the observation that if the compiler generates code like...
| jsr foo
| ret
| ... then it can be replaced with:
| jmp foo
+---------------
Ooh!! Severe PDP-10 assembly-language flashback! (Or trivia attack,
whatever.) The DEC PDP-10 had several different subroutine call
instructions (more than any other machien I've worked on, actually),
but the one used most commonly for deep call chains was "PUSHJ P,FOO"
(push the current PC onto the stack P and jump to FOO). The corresponding
return was "POPJ P,0". The PDP-10 also had many different jump instructions
(way too many!), but the fastest was "JRST 0, FOO" (jump and restore,
but "JRST 0," didn't actually restore anything!). Assembly-language
programmers [note: almost all systems software on the PDP-10 was written
in assembler!] would routinely do tail-call merging manually, but to
avoid confusing other people they would document it in the code by using
a macro named "PJRST" (which just expanded to "JRST"). So the idiom for
the above merge in MACRO-10 syntax was:
PUSHJ P,FOO
POPJ P,0
becomes:
PJRST FOO
More complex forms were common as well, such as statically curried
functions [although nobody called it that back then]. Suppose you
had a function FOO that took three arguments in registers T0, T1,
and T2, but there were a lot of calls for which the third arg had a
particular value, say, "34" or "53". Then you might see specialized
routines such as these [note that the second PJRST is commented out!]:
FOO34: MOVEI T2, 34 ; T0, T1 already set
PJRST FOO
FOO53: MOVEI T2, 53 ; T0, T1 already set
;PJRST FOO ; (fall through)
FOO: ...
...
POPJ P,0
When passing args on the stack, though, you had the same problems
merging tail calls as discussed in the rest of this thread. Yeah,
there were occasionally some attempts to do it, but they were mostly
unsatisfying. [That is, "PUSH P,(P)" does a "dup" of the top of the stack,
and you could store the third arg where the return PC used to be, but
then how do you get the original caller to remove the extra arg when
FOO returns directly to him?]
-Rob
-----
Rob Warnock, 30-3-510 <rpw3@sgi.com>
SGI Network Engineering <http://www.meer.net/~rpw3/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
[Note: aaanalyst@sgi.com and zedwatch@sgi.com aren't for humans ]