TAOCP 1.4.1 Exercise 5
A linkage mechanism not using the J-register must supply the return address explicitly and must provide a way for the subroutine to transfer control back to that address without modifying program inst...
Exercise 5. [21] Suppose MIX did not have a J-register. Invent a means for subroutine linkage that does not use register J, and give an example of your invention by writing a MAX100 subroutine effectively equivalent to (1). State the characteristics of this subroutine in a fashion similar to (4). (Retain MIX's conventions of self-modifying code.)
Verified: yes
Solve time: 56s
Solution
A linkage mechanism not using the J-register must supply the return address explicitly and must provide a way for the subroutine to transfer control back to that address without modifying program instructions at the call site.
Introduce the following calling sequence for a call to MAX100:
JMP MAX100
CON RET
The word RET contains the return address, namely the location of the instruction following CON RET. Since this value is known at assembly time, it is placed in memory as a constant.
The subroutine uses index register I1 to hold the return address. Control is returned by an indirect jump through I1.
MAX100 without the J-register
MAX100 ENT1 *+1 I1 <- return address (RET)
JMP 1F skip return-address cell
STJ EXIT (not used; linkage removed)
1H ... begin body of MAX100 as in (1)
... unchanged maximum-finding code
...
JMP 0,1 return via I1
EXIT JMP 0,1 (unused label for structure completeness)
The body labeled “...” is exactly the coding of MAX100 in (1) except that the original linkage instruction STJ EXIT and the final EXIT JMP * are removed. Every exit from the body is replaced by JMP 0,1.
The instruction ENT1 *+1 sets I1 to the contents of the next memory location, which is the constant RET. The instruction JMP 1F advances control to the first instruction of the original subroutine body, thereby skipping the parameter cell.
Return is executed by JMP 0,1, which transfers control to the address contained in I1.
Characteristics of MAX100
Calling sequence: JMP MAX100
CON RET
Entry conditions: location RET contains the address of the instruction
immediately following CON RET
Exit conditions: rA = max_{1 ≤ k ≤ 100} CONTENTS(X + k)
rI2 = position of the maximum
rI1 = return address supplied by calling sequence
rI3 = 0
rJ is not used
CI is altered
Memory effects: no storage outside subroutine except RET supplied by caller
The linkage depends on the convention that each call reserves one memory cell containing the return address, and the subroutine returns by indirect transfer through I1. This replaces self-modifying return jumps while preserving the behavioral specification of MAX100. This completes the proof. ∎