TAOCP 1.4.3.2 Exercise 4
Assume that the trace routine is tracing itself, and that the two instructions ENTX LEAVEX JMP *+1 have been inserted immediately before `ENTER`.
Section 1.4.3.2: Trace Routines
Exercise 4. [25] What would happen if the trace routine were tracing itself? Specifically, consider the behavior if the two instructions ENTX LEAVEX; JMP *+1 were placed just before ENTER.
Verified: no
Solve time: -
Solution
Assume that the trace routine is tracing itself, and that the two instructions
ENTX LEAVEX
JMP *+1
have been inserted immediately before ENTER. The purpose of this insertion is to arrange that when the trace routine eventually executes LEAVEX JMP *, the index register $rX$ contains the address of LEAVEX$, so that the tracing process will not terminate immediately. Instead, control will continue at the instruction following LEAVEX`.
The behavior may be analyzed by following the first few iterations of the tracing cycle.
The inserted instruction ENTX LEAVEX is traced first. Since it is not a jump instruction, lines 29-30 do not alter it. At line 34 the instruction is executed normally, so $rX$ receives the address of LEAVEX. After line 38, control returns to CYCLE, and the simulated program counter advances to the next instruction, namely JMP *+1.
The instruction JMP *+1 is then traced. Since it is a jump instruction, lines 29-30 replace its address field by JUMP; thus the executed instruction becomes effectively
JMP JUMP
At line 40 the routine determines that a jump has occurred. Since the original instruction was JMP, not JSJ, lines 43-45 update the simulated J-register. Line 46 then transfers control to the target address of the jump, namely the location one step beyond JMP *+1$, which is ENTER`.
Hence the trace routine enters itself. A second copy of the tracing process now begins execution, but the first copy has not terminated.
The same phenomenon repeats indefinitely. The second trace begins by tracing ENTX LEAVEX, then JMP *+1, and thereby invokes a third copy of the trace routine. In general, whenever a copy reaches JMP *+1, it transfers control to ENTER, thereby creating another active level of tracing.
No copy ever reaches LEAVE, because before the original trace routine can proceed far enough to terminate, execution has already entered a new copy of the same routine. The nesting depth therefore increases without bound.
Eventually the routine destroys itself by violating restriction (a): locations used by the trace program are overwritten. Each active copy modifies shared storage such as AREG, PREG, INST, and JREG. Since these locations are not private to a given invocation, later copies overwrite the saved state of earlier ones. The trace therefore ceases to represent any coherent execution history.
Thus, tracing the trace routine causes an infinite regress of nested tracing operations. The program repeatedly re-enters ENTER, never returns normally, and ultimately corrupts its own working storage. $\boxed{\text{The trace routine goes into an endless self-tracing recursion and destroys its own state.}}$